Brute-Force MAP Learning & Find-S

Source: Unit 3 §6

The brute-force MAP learning algorithm

The algorithm is exactly what the definition of MAP says, taken literally.

For each hypothesis h ∈ H:

calculate the posterior P(h|D) = P(D|h)·P(h) / P(D)

Output h_MAP = argmax_{h∈H} P(h|D)

⚠GotchaIt applies Bayes' rule to every single hypothesis

For any realistic $H$ this is computationally infeasible - the loop is over the entire hypothesis space. Its value is not as something you run. It is a standard or benchmark: a concept learner is judged by whether it produces what brute-force MAP would have produced.

Relation to concept learning

Assume fixed instances $\langle x_1, \dots, x_m \rangle$ with classifications $D = \langle c(x_1), \dots, c(x_m) \rangle$. Now choose the two probability definitions:

≡FactsThe two choices that make this work

• Likelihood: P(D|h) = 1 if h is consistent with D, and 0 otherwise. A hypothesis either explains the data perfectly or not at all.
• Prior: P(h) is uniform over H. No hypothesis is favoured before the data arrives.

Under those two choices, every consistent hypothesis ends up with the same posterior, and every inconsistent one gets zero:

$$P(h \mid D) = \frac{1}{\lvert VS_{H,D} \rvert}$$

That is a uniform distribution over the version space.

The total probability is always 1. Every hypothesis an example rules out drops to zero and hands its share to the survivors, so the bars that remain get taller. Taller bars are what certainty looks like.

→StepsWhat the three panels are showing

1. Start: all hypotheses carry equal probability, because the prior is uniform.
2. As data accumulates: every hypothesis inconsistent with an example drops to probability zero.
3. The total probability, which is 1, is shared equally among the consistent hypotheses that remain.
4. Fewer survivors means a larger share each, so as data is added, certainty increases.

Consistent learners and the Bayesian view of inductive bias

◎Exam cueThe headline result

Every hypothesis consistent with $D$ is a MAP hypothesis, provided that (1) the prior over $H$ is uniform, and (2) the target concept $c \in H$ with deterministic, noise-free data.

The consequence is the interesting part: Find-S outputs a MAP hypothesis, even though Find-S uses no probabilities at all. An algorithm does not have to know it is doing Bayesian inference to be doing Bayesian inference.

≡FactsBayesian interpretation of inductive bias

An algorithm's inductive bias can be characterised by choosing an appropriate P(h) and P(D|h). The bias is not an informal preference sitting outside the maths - it is exactly the prior and likelihood that would make the algorithm's output the MAP hypothesis.