UTCS Artificial Intelligence
courses
talks/events
demos
people
projects
publications
software/data
labs
areas
admin
A Preliminary PAC Analysis of Theory Revision (1995)
Raymond J. Mooney
This paper presents a preliminary analysis of the sample complexity of theory revision within the framework of PAC (Probably Approximately Correct) learnability theory. By formalizing the notion that the initial theory is ``close'' to the correct theory we show that the sample complexity of an optimal propositional Horn-clause theory revision algorithm is $O( ( ln 1 / delta + d ln (s_0 + d + n) ) / epsilon)$, where $d$ is the
syntactic distance
between the initial and correct theories, $s_0$ is the size of initial theory, $n$ is the number of observable features, and $epsilon$ and $delta$ are the standard PAC error and probability bounds. The paper also discusses the problems raised by the computational complexity of theory revision.
View:
PDF
,
PS
Citation:
In
Computational Learning Theory and Natural Learning Systems, Vol. 3
, T. Petsche and S. Hanson and Jude W. Shavlik (Eds.), pp. 43-53, Cambridge, MA 1995. MIT Press.
Bibtex:
@InCollection{mooney:bkchapter95, title={A Preliminary PAC Analysis of Theory Revision}, author={Raymond J. Mooney}, booktitle={Computational Learning Theory and Natural Learning Systems, Vol. 3}, editor={T. Petsche and S. Hanson and Jude W. Shavlik}, address={Cambridge, MA}, publisher={MIT Press}, key={theory refinement}, pages={43-53}, url="http://www.cs.utexas.edu/users/ai-lab/?mooney:bkchapter95", year={1995} }
People
Raymond J. Mooney
Faculty
mooney [at] cs utexas edu
Areas of Interest
Machine Learning
Theory and Knowledge Refinement
Labs
Machine Learning