Occam learning

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In computational learning theory, Occam learning is a model of algorithmic learning where the objective of the learner is to output a succinct representation of received training data. This is closely related to probably approximately correct (PAC) learning, where the learner is evaluated on its predictive power of a test set. Occam learnability implies PAC learning, and for a wide variety of concept classes, the converse is also true: PAC learnability implies Occam learnability.

In computational learning theory, Occam learning is a model of algorithmic learning where the objective of the learner is to output a succinct representation of received training data. This is closely related to probably approximately correct (PAC) learning, where the learner is evaluated on its predictive power of a test set. Occam learnability implies PAC learning, and for a wide variety of concept classes, the converse is also true: PAC learnability implies Occam learnability.

Introduction

Occam Learning is named after Occam's razor, which is a principle stating that, given all other things being equal, a shorter explanation for observed data should be favored over a lengthier explanation. The theory of Occam learning is a formal and mathematical justification for this principle. It was first shown by Blumer, et al. that Occam learning implies PAC learning, which is the standard model of learning in computational learning theory. In other words, parsimony (of the output hypothesis) implies predictive power.

Definition of Occam learning

The succinctness of a concept c in concept class \mathcal{C} can be expressed by the length size(c) of the shortest bit string that can represent c in \mathcal{C} . Occam learning connects the succinctness of a learning algorithm's output to its predictive power on unseen data. Let \mathcal{C} and \mathcal{H} be concept classes containing target concepts and hypotheses respectively. Then, for constants \alpha \ge 0 and 0 \le \beta , a learning algorithm L is an (\alpha,\beta) -Occam algorithm for \mathcal{C} using \mathcal{H} iff, given a set S = \{ x_1, \dots, x_m \} of m samples labeled according to a concept c \in \mathcal{C} , L outputs a hypothesis h \in \mathcal{H} such that h is consistent with c on S (that is, h(x)=c(x),\forall x \in S ), and size(h) \le (n \cdot size(c))^\alpha m^\beta where n is the maximum length of any sample x \in S . An Occam algorithm is called efficient if it runs in time polynomial in n , m , and size(c). We say a concept class \mathcal{C} is Occam learnable with respect to a hypothesis class \mathcal{H} if there exists an efficient Occam algorithm for \mathcal{C} using \mathcal{H}.

The relation between Occam and PAC learning

Occam learnability implies PAC learnability, as the following theorem of Blumer, et al. shows:

Proof that Occam learning implies PAC learning

We first prove the Cardinality version. Call a hypothesis h\in \mathcal{H} bad if error(h) \geq \epsilon , where again error(h) is with respect to the true concept c and the underlying distribution \mathcal{D} . The probability that a set of samples S is consistent with h is at most (1 - \epsilon)^m , by the independence of the samples. By the union bound, the probability that there exists a bad hypothesis in \mathcal{H}_{n,m} is at most | \mathcal{H}_{n,m} | (1 - \epsilon)^m , which is less than \delta if \log | \mathcal{H}_{n,m} | \leq O(\epsilon m) - \log \frac{1}{\delta} . This concludes the proof of the second theorem above. Using the second theorem, we can prove the first theorem. Since we have a (\alpha,\beta) -Occam algorithm, this means that any hypothesis output by L can be represented by at most (n \cdot size(c))^\alpha m^\beta bits, and thus \log |\mathcal{H}_{n,m}| \leq (n \cdot size(c))^\alpha m^\beta . This is less than O(\epsilon m) - \log \frac{1}{\delta} if we set m \geq a \left( \frac 1 \epsilon \log \frac 1 \delta + \left(\frac {(n \cdot size(c))^\alpha)} \epsilon \right)^{\frac 1 {1-\beta}}\right) for some constant a > 0 . Thus, by the Cardinality version Theorem, L will output a consistent hypothesis h with probability at least 1 - \delta . This concludes the proof of the first theorem above.

Improving sample complexity for common problems

Though Occam and PAC learnability are equivalent, the Occam framework can be used to produce tighter bounds on the sample complexity of classical problems including conjunctions, conjunctions with few relevant variables, and decision lists.

See also

Computational learning theory Structural risk minimization

References

Further reading

Blumer, A.; Ehrenfeucht, A.; Haussler, D.; Warmuth, M. K. Learnability and the Vapnik-Chervonenkis dimension. Journal of the ACM, 36(4):929–865, 1989.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1333333149 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

Extracted from the cited revision's reference blocks; absent citations are not invented.