
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Relationships between PACLearning Algorithms and Weak Occam Algorithms
Eiji TAKIMOTO Akira MARUOKA
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E75D
No.4
pp.442448 Publication Date: 1992/07/25
Online ISSN:
DOI:
Print ISSN: 09168532 Type of Manuscript: Special Section PAPER (Special Issue on Algorithmic Learning Theory) Category: Keyword: algorithm and computational complexity, artificial intelligence and cognitive science,
Full Text: PDF>>
Summary:
In the approximate learning model introduced by Valiant, it has been shown by Blumer et al. that an Occam algorithm is immediately a PAClearning 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 PAClearning algorithms is investigated. It is shown that although a weak Occam algorithm is immediately a (probably) consistent PAClearning algorithm, the converse does not hold. On the other hand, we show how to construct a weak Occam algorithm from a PAClearning algorithm under some natural conditions. This result implies the equivalence between the existence of a weak Occam algorithm and that of a PAClearning algorithm. Since the weak Occam algorithms constructed from PAClearning algorithms are deterministic, our result improves a result of Board and Pitt's that the existence of a PAClearning algorithm is equivalent to that of a randomized Occam algorithm.

