Bayes Optimal Classifier & Gibbs Algorithm

Source: Unit 3 §8

The question it answers

MAP answers "what is the most probable hypothesis?" The Bayes Optimal Classifier answers a different and, for prediction, better question: "what is the most probable classification of a new instance?"

Those two questions have different answers, and this page is about the gap.

The Bayes optimal classifier

Combine the predictions of all hypotheses, weighted by their posterior probabilities. For possible classes $v_j \in V$:

$$P(v_j \mid D) = \sum_{h_i \in H} P(v_j \mid h_i) \cdot P(h_i \mid D)$$

The optimal classification is then the argmax over $v_j$:

$$\text{Bayes Optimal} = \arg\max_{v_j \in V} \sum_{h_i \in H} P(v_j \mid h_i) \cdot P(h_i \mid D)$$

Worked example: why it beats MAP

Three hypotheses with posteriors $P(h_1 \mid D) = 0.4$, $P(h_2 \mid D) = 0.3$, $P(h_3 \mid D) = 0.3$. On a new instance $x$: $h_1 \to +$, $h_2 \to -$, $h_3 \to -$.

	h₁ (0.4)	h₂ (0.3)	h₃ (0.3)	Σ
P(+|hᵢ)	1	0	0	0.4
P(−|hᵢ)	0	1	1	0.6

→StepsRunning the sum

1. For class +, only $h_1$ contributes: $1 \times 0.4 + 0 \times 0.3 + 0 \times 0.3 = \mathbf{0.4}$.
2. For class −, $h_2$ and $h_3$ contribute: $0 \times 0.4 + 1 \times 0.3 + 1 \times 0.3 = \mathbf{0.6}$.
3. Most probable classification is −, because $0.6 > 0.4$.

The single most probable hypothesis votes +, but the two less probable ones outweigh it together. Asking for the best classification is not the same question as asking for the best hypothesis.

⚠GotchaThe Bayes optimal classifier can disagree with the MAP hypothesis

The MAP hypothesis here is $h_1$, and $h_1$ predicts +. The Bayes optimal classification is −. They disagree, and the Bayes optimal answer is the correct one: it maximises the probability that the new instance is classified correctly, given the data, the hypothesis space and the priors. No other classification method using the same hypothesis space and prior knowledge can do better on average.

Gibbs algorithm

The Bayes optimal classifier is optimal but costly - it computes a posterior for every hypothesis in $H$ and then a weighted vote over all of them. The Gibbs algorithm is the cheap alternative.

Gibbs Algorithm:

1. Choose ONE hypothesis h from H at random, according to the posterior P(h|D).

2. Use that h to classify the next instance.

◎Exam cueThe surprising bound

Under certain conditions, the expected error of Gibbs is at most twice the expected error of the Bayes optimal classifier. One random draw from the posterior buys you within a factor of 2 of the theoretical optimum.

⇄CompareOptimal versus affordable

Bayes Optimal ClassifierWeighted vote over every hypothesis in H. Provably the best possible classification, and the cost scales with |H|, which is usually the reason you cannot use it.

Gibbs AlgorithmSample a single h from the posterior and let it decide. Costs one hypothesis instead of all of them, and the expected error is bounded by 2× the optimal.