Occam learning

Key takeaways

Occam learning belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Occam learning to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Occam learning from memory before moving on to harder problems.

Reference excerpt

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 {\displaystyle c} in concept class C {\displaystyle {\mathcal {C}}} can be expressed by the length s i z e ( c ) {\displaystyle size(c)} of the shortest bit string that can represent c {\displaystyle c} in C {\displaystyle {\mathcal {C}}} . Occam learning connects the succinctness of a learning algorithm's output to its predictive power on unseen data. Let C {\displaystyle {\mathcal {C}}} and H {\displaystyle {\mathcal {H}}} be concept classes containing target concepts and hypotheses respectively. Then, for constants α ≥ 0 {\displaystyle \alpha \geq 0} and 0 ≤ β < 1 {\displaystyle 0\leq \beta <1} , a learning algorithm L {\displaystyle L} is an ( α , β ) {\displaystyle (\alpha ,\beta )} -Occam algorithm for C {\displaystyle {\mathcal {C}}} using H {\displaystyle {\mathcal {H}}} iff, given a set S = { x 1 , … , x m } {\displaystyle S=\{x_{1},\dots ,x_{m}\}} of m {\displaystyle m} samples labeled according to a concept c ∈ C {\displaystyle c\in {\mathcal {C}}} , L {\displaystyle L} outputs a hypothesis h ∈ H {\displaystyle h\in {\mathcal {H}}} such that

h {\displaystyle h} is consistent with c {\displaystyle c} on S {\displaystyle S} (that is, h ( x ) = c ( x ) , ∀ x ∈ S {\displaystyle h(x)=c(x),\forall x\in S} ), and

s i z e ( h ) ≤ ( n ⋅ s i z e ( c ) ) α m β {\displaystyle size(h)\leq (n\cdot size(c))^{\alpha }m^{\beta }} where n {\displaystyle n} is the maximum length of any sample x ∈ S {\displaystyle x\in S} . An Occam algorithm is called efficient if it runs in time polynomial in n {\displaystyle n} , m {\displaystyle m} , and s i z e ( c ) . {\displaystyle size(c).} We say a concept class C {\displaystyle {\mathcal {C}}} is Occam learnable with respect to a hypothesis class H {\displaystyle {\mathcal {H}}} if there exists an efficient Occam algorithm for C {\displaystyle {\mathcal {C}}} using H . {\displaystyle {\mathcal {H}}.}

The relation between Occam and PAC learning Occam learnability implies PAC learnability, as the following theorem of Blumer, et al. shows:

… excerpt ends here. Continue reading the full article.

Worked examples

Example 1 — a first encounter with Occam learning

Start with the simplest possible case. Write down what Occam learning claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Occam learning before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Occam learning ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Occam learning

In research: Occam learning appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Occam learning in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Occam learning is common in secondary-school and first-year university syllabi. It links to neighbouring topics Computational learning theory, Theoretical computer science, so understanding it makes those chapters shorter.
In everyday life: Look for Occam learning outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Occam learning in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Occam learning means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Occam learning out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Occam learning in simple terms?

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 pr…

Why does Occam learning matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Occam learning?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Occam learning.