Probabilistic & Bayesian Learning: Cheat Sheet

Assembled from the matching per-unit cheat-sheet slices. The whole topic compressed for the night before the exam.

Bayesian learning

≡FactsThe theorem and the two estimators

• Bayes: $P(h \mid D) = P(D \mid h)P(h) / P(D)$. Posterior ∝ Likelihood × Prior.
• MAP: $\arg\max_h P(D \mid h)P(h)$.
• ML: $\arg\max_h P(D \mid h)$, which equals MAP when the prior is uniform.
• Size principle: favour the smallest consistent hypothesis - Occam's razor in probabilistic form.

#NumbersThe cancer example, in one line

$P(+ \mid c)P(c) = 0.00784$ against $P(+ \mid \neg c)P(\neg c) = 0.02976$, so $h_{\text{MAP}} = \neg\text{cancer}$. Normalised, that is 0.21 / 0.79. Priors dominate.

≡FactsConsistent learners and least squares

• Brute-force MAP: a consistent h has P(h|D) = 1/|VS|, uniform over the version space.
• Find-S outputs a MAP hypothesis given a uniform prior and noise-free data, despite using no probabilities.
• ML = least squares under Gaussian noise: $h_{\text{ML}} = \arg\min_h \sum_i (d_i - h(x_i))^2$.
• For predicting probabilities, the same argument gives cross-entropy instead.

≡FactsBeyond a single hypothesis

• Bayes Optimal Classifier: $\arg\max_{v_j} \sum_i P(v_j \mid h_i) P(h_i \mid D)$ - combines all hypotheses and can beat MAP (the 0.4 / 0.6 example).
• Gibbs: pick one h at random by the posterior. Expected error at most 2× the Bayes optimal.

Naive Bayes

≡FactsThe classifier

• $v_{\text{NB}} = \arg\max_{v_j} P(v_j) \prod_i P(a_i \mid v_j)$, assuming conditional independence given the class.
• Play Tennis on (Sunny, Cool, High, Strong): YES ≈ 0.0053, NO ≈ 0.0206, so the answer is NO.
• Text: bag-of-words, and Laplace smoothing (count+1)/(words_in_class+|vocab|) fixes the zero-probability problem.

EM

≡FactsExpectation-Maximization

• MLE in the presence of latent variables. E-step: estimate the hidden data. M-step: maximise the parameters. Converges to a local maximum.
• K-means is EM: E assigns each point to the nearest centroid, M recomputes the centroids. GMM is the soft version, using responsibilities.
• Two coins: identities known means just counting, $\theta_1 = 0.8$ and $\theta_2 = 0.45$; identities unknown means EM.

Markov and HMM

≡FactsMarkov chains

• Markov property: the next state depends only on the current state - memoryless. Transition matrix rows sum to 1, row is FROM and column is TO.
• Weather sequence: $P(CSRCR) = P_C \cdot \prod \text{transitions} = \mathbf{0.00144}$.

≡FactsHMM structure and the three problems

• λ = (π, A, B): π is initial, A is transition, B is emission P(obs|state). Hidden states, observed emissions.
• Problem 1, Likelihood → Forward. Problem 2, Decoding → Viterbi. Problem 3, Learning → Baum-Welch (EM).

#NumbersThe recursions, and the canonical answer

• Forward: $\alpha_1(i) = \pi_i b_i(O_1)$; $\alpha_{t+1}(j) = [\sum_i \alpha_t(i) a_{ij}] b_j(O_{t+1})$; $P(O) = \sum_i \alpha_T(i)$. Worked example gives P(O) = 0.03532.
• Backward: $\beta_T = 1$; $\beta_t(i) = \sum_j a_{ij} b_j(O_{t+1}) \beta_{t+1}(j)$.
• Gamma: $\gamma_t(i) = \alpha_t(i)\beta_t(i) / P(O)$, and each column sums to 1. $P(O)$ is the α·β dot product of any column.
• Viterbi is Forward with max instead of sum, plus backpointers, giving the best state sequence.

---

End of Unit 3 notes. Every slide topic from the Unit 3 folder (L25 to L36) is covered across this topic.

⚠GotchaCorrections applied to the source slides

1. The Naive Bayes Play Tennis YES score is ≈ 0.0053; the slide showed 0.0211. The conclusion NO is unaffected.
2. All HMM forward, backward and gamma tables, and the cancer and text-classification numbers, were independently recomputed and verified.