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.

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.

The succinctness of a concept ${\displaystyle c}$ in concept class ${\displaystyle {\mathcal {C}}}$ can be expressed by the length ${\displaystyle size(c)}$ of the shortest bit string that can represent ${\displaystyle c}$ in ${\displaystyle {\mathcal {C}}}$. Occam learning connects the succinctness of a learning algorithm's output to its predictive power on unseen data.

Let ${\displaystyle {\mathcal {C}}}$ and ${\displaystyle {\mathcal {H}}}$ be concept classes containing target concepts and hypotheses respectively. Then, for constants ${\displaystyle \alpha \geq 0}$ and ${\displaystyle 0\leq \beta <1}$, a learning algorithm ${\displaystyle L}$ is an ${\displaystyle (\alpha ,\beta )}$-Occam algorithm for ${\displaystyle {\mathcal {C}}}$ using ${\displaystyle {\mathcal {H}}}$ iff, given a set ${\displaystyle S=\{x_{1},\dots ,x_{m}\}}$ of ${\displaystyle m}$ samples labeled according to a concept ${\displaystyle c\in {\mathcal {C}}}$, ${\displaystyle L}$ outputs a hypothesis ${\displaystyle h\in {\mathcal {H}}}$ such that

where ${\displaystyle n}$ is the maximum length of any sample ${\displaystyle x\in S}$. An Occam algorithm is called efficient if it runs in time polynomial in ${\displaystyle n}$, ${\displaystyle m}$, and ${\displaystyle size(c).}$ We say a concept class ${\displaystyle {\mathcal {C}}}$ is Occam learnable with respect to a hypothesis class ${\displaystyle {\mathcal {H}}}$ if there exists an efficient Occam algorithm for ${\displaystyle {\mathcal {C}}}$ using ${\displaystyle {\mathcal {H}}.}$

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

Let ${\displaystyle L}$ be an efficient ${\displaystyle (\alpha ,\beta )}$-Occam algorithm for ${\displaystyle {\mathcal {C}}}$ using ${\displaystyle {\mathcal {H}}}$. Then there exists a constant ${\displaystyle a>0}$ such that for any ${\displaystyle 0<\epsilon ,\delta <1}$, for any distribution ${\displaystyle {\mathcal {D}}}$, given ${\displaystyle 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)}$ samples drawn from ${\displaystyle {\mathcal {D}}}$ and labelled according to a concept ${\displaystyle c\in {\mathcal {C}}}$ of length ${\displaystyle n}$ bits each, the algorithm ${\displaystyle L}$ will output a hypothesis ${\displaystyle h\in {\mathcal {H}}}$ such that ${\displaystyle error(h)\leq \epsilon }$ with probability at least ${\displaystyle 1-\delta }$ .