Relationships between PAC-Learning Algorithms and Weak Occam Algorithms

Eiji TAKIMOTO; Akira MARUOKA

Relationships between PAC-Learning Algorithms and Weak Occam Algorithms

Eiji TAKIMOTO, Akira MARUOKA

Full Text Views

0

Share
Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Information Vol.E75-D No.4 pp.442-448

Publication Date: 1992/07/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Issue on Algorithmic Learning Theory)

Category

Cite this

Copy

Eiji TAKIMOTO, Akira MARUOKA, "Relationships between PAC-Learning Algorithms and Weak Occam Algorithms" in IEICE TRANSACTIONS on Information, vol. E75-D, no. 4, pp. 442-448, July 1992, doi: .
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/information/10.1587/e75-d_4_442/_p

Copy

@ARTICLE{e75-d_4_442,
author={Eiji TAKIMOTO, Akira MARUOKA, },
journal={IEICE TRANSACTIONS on Information},
title={Relationships between PAC-Learning Algorithms and Weak Occam Algorithms},
year={1992},
volume={E75-D},
number={4},
pages={442-448},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={July},}

Copy

TY - JOUR
TI - Relationships between PAC-Learning Algorithms and Weak Occam Algorithms
T2 - IEICE TRANSACTIONS on Information
SP - 442
EP - 448
AU - Eiji TAKIMOTO
AU - Akira MARUOKA
PY - 1992
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E75-D
IS - 4
JA - IEICE TRANSACTIONS on Information
Y1 - July 1992
AB - 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.
ER -