Problems in Computational Learning Theory

Jyrki Kivinen: Problems in Computational Learning Theory. PhD Thesis, Report A-1992-1, Department of Computer Science, University of Helsinki, 1992. 27+64 pages. <http://www.cs.helsinki.fi/TR/A-1992/1>

Full paper:
Metadata: XML file

Abstract

This thesis summarizes results on some computational learning problems within the probabilistic framework proposed by Valiant. We give a polynomial time learning algorithm for concepts that can be represented as hierarchical rule sets. These representations consist of an arbitrary number of rules 'if c then l' organized into a fixed number of levels. The rule means that an instance satisfying the condition c belongs to the class l. However, the rule can be overridden by a rule at a preceding level. If the instances are strings, the condition could be a test for the presence of a given substring in the instance. Instances could also be value assignments for a potentially infinite number of Boolean attributes, in which case the condition could be a Boolean conjunction of constant length. We also study reliable and probably useful learning, proposed by Rivest and Sloan. We derive upper and lower bounds for the sample complexity of reliable and probably useful learning in terms of combinatorial measures of the class of concepts to be learned. These measures resemble the Vapnik-Chervonenkis dimension. The results imply that monotone Boolean monomials cannot be learned reliably and probably usefully with a sample size that is polynomial in the number of variables. Rectangles cannot be learned reliably and probably usefully with any finite sample size. The sample complexity of reliable and probably useful learning remains high even if the examples are assumed to be drawn according to the uniform probability measure.

Index Terms

Categories and Subject Descriptors:
I.2.6

General Terms: Algorithms, Theory

Additional Key Words and Phrases: concept learning, inductive inference, Occam algorithms, sample complexity