Bayes' Theorem & Concept Learning

Source: Unit 3 §4

Why probability shows up in learning at all

Neural nets already hand back probabilities, not just labels. A sigmoid output lives in $[0, 1]$ and acts as a confidence index; a softmax layer returns an entire probability distribution over the classes. Winston's line that "AI is computational statistics" is the point: the error functions used so far are probabilistic at heart, even when they are not written that way.

≡FactsTwo words that mean different things

• Bayesian probability - probability read as a degree of partial belief, not as a long-run frequency.
• Bayesian estimation - the procedure that computes the validity of a proposition from prior estimates plus new evidence, producing a posterior estimate.

The Number Game

Learning what a word means is close to concept learning, which is close to binary classification: define f(x) = 1 if x ∈ C, else 0.

The setup: a teacher thinks of an arithmetic concept over {1, …, 100} - primes, even numbers, powers of two - and gives positive examples only.

→StepsWatching induction happen

1. Given D = {16}, an enormous number of concepts fit: powers of two, even numbers, squares, multiples of four, numbers between 10 and 20.
2. Given D = {16, 8, 2, 64}, you guess "powers of two". That leap is induction.
3. The subset of H still consistent with D is the version space. As examples accumulate the version space shrinks, and certainty rises.

⚠GotchaConsistency alone does not pick a hypothesis

After D = {16, 8, 2, 64}, "powers of two", "all even numbers" and "powers of two except 32" are all equally consistent with the data. Nothing about consistency separates them. To choose, you need two extra ingredients: a likelihood and a prior.

Likelihood and the size principle

Assume the examples are sampled uniformly at random from the numbers consistent with the hypothesis. That single assumption is enough to break the tie.

There are 6 powers of two at most 100, but 50 even numbers. So each draw costs $1/6$ under one hypothesis and $1/50$ under the other:

$$P(D \mid h_{\text{two}}) = \left(\tfrac{1}{6}\right)^{4} \qquad P(D \mid h_{\text{even}}) = \left(\tfrac{1}{50}\right)^{4}$$

The likelihood of $h_{\text{two}}$ is far higher - by a factor of $(50/6)^4 \approx 4800$.

Both hypotheses contain every observed example, so both are consistent. The smaller extension spreads the same unit of probability over fewer numbers, so each draw it explains is worth more.

◎Exam cueThe size principle

Favour the smallest hypothesis consistent with the data. Smaller hypotheses make sharper, therefore more likely, predictions. This is Occam's razor in probabilistic form, and it falls out of the likelihood rather than being bolted on as a preference.

Prior

The prior is how background knowledge enters the problem.

Some hypotheses are simply more natural than others. Given {1400, 1200, 1600, 1800}, a "multiples of 200"-ish concept feels more natural than a weird rule that happens to also include 1183. Based on prior experience, some hypotheses are a priori more probable, and the prior is where you say so.

Posterior = likelihood × prior

$$P(h \mid D) \;\propto\; P(D \mid h) \cdot P(h)$$

The posterior is not a new quantity - it is the prior reweighted by how well each hypothesis predicted the data. Drop the prior and you get maximum likelihood; make the prior uniform and you get the same thing.

≡FactsReading the proportionality

• Write I(D ∈ h) = 1 exactly when all the data lie in the extension of h, and 0 otherwise - that indicator is what the likelihood term collapses to for a strict concept.
• If the prior is uniform, the posterior is proportional to the likelihood, and the size principle alone decides.
• With enough data, the posterior becomes peaked on a single concept.

That peak has a name - the MAP estimate, the mode of the posterior:

$$\hat{h}_{\text{MAP}} = \arg\max_{h} P(h \mid D)$$