Relationships between PAC-Learning Algorithms and Weak Occam Algorithms


IEICE TRANSACTIONS on Information and Systems   Vol.E75-D   No.4   pp.442-448
Publication Date: 1992/07/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Algorithmic Learning Theory)
algorithm and computational complexity,  artificial intelligence and cognitive science,  

Full Text: PDF>>
Buy this Article

In the approximate learning model introduced by Valiant, it has been shown by Blumer et al. that an Occam algorithm is immediately a PAC-learning algorithm. An Occam algorithm is a polynomial time algorithm that produces, for any sequence of examples, a simple hypothesis consistent with the examples. So an Occam algorithm is thought of as a procedure that compresses information in the examples. Weakening the compressing ability of Occam algorithms, a notion of weak Occam algorithms is introduced and the relationship between weak Occam algorithms and PAC-learning algorithms is investigated. It is shown that although a weak Occam algorithm is immediately a (probably) consistent PAC-learning algorithm, the converse does not hold. On the other hand, we show how to construct a weak Occam algorithm from a PAC-learning algorithm under some natural conditions. This result implies the equivalence between the existence of a weak Occam algorithm and that of a PAC-learning algorithm. Since the weak Occam algorithms constructed from PAC-learning algorithms are deterministic, our result improves a result of Board and Pitt's that the existence of a PAC-learning algorithm is equivalent to that of a randomized Occam algorithm.