Computational Learning Theory and Natural Learning Systems, Vol. 3, T. Petsche, S. Judd, and S. Hanson (Eds.), MIT Press, 1995, pp. 43-53.
Paper ID: 41
Category: Theory and Knowledge Refinedment
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.
