Probabilistic ML & the credit-assignment theme (breadth)

Hidden Markov Models

A Hidden Markov Model (HMM) is a “doubly embedded stochastic process”: hidden states evolve by a Markov chain you cannot see, and each state stochastically emits an *observable* output. It is defined by states $S$, transition probabilities $a_{ij}=P(s_j\mid s_i)$, and emission probabilities $P(o\mid s_i)$. Speech is the canonical case — intended phonemes are hidden; the acoustic signal is observed.

The Viterbi algorithm

Given an observation sequence, Viterbi finds the single most-likely (MAP) hidden-state path by dynamic programming (it is to HMMs what A* is to search). It fills a table where $\text{viterbi}[s, t]$ is the best probability of reaching state $s$ at time $t$: $$\text{viterbi}[s_j, t] = \max_{s_i}\big(\text{viterbi}[s_i, t-1]\cdot P(s_j\mid s_i)\cdot P(o_t\mid s_j)\big),$$ keeping back-pointers, then traces back from the best final state. The Markov property is what licenses DP: the best path into a state depends only on the previous column, not the whole history. The exercise decodes a 2-state weather HMM.

EM — learning with hidden data

When some variables are unobserved you cannot just count frequencies. Expectation-Maximization (EM) alternates: the E-step fills in expected values of the hidden variables given the current parameters; the M-step re-estimates parameters as if those expectations were real counts. It is guaranteed to never *decrease* the data likelihood, converging to a local maximum (so it is run from several random restarts). Baum-Welch — HMM parameter learning — is EM in action.

The unifying theme: credit assignment

A single problem recurs across this whole module: when an outcome is delayed and indirect, which component deserves the credit or blame? Different algorithms, one question: - Backprop (L8.6) — the chain rule distributes output error back to hidden weights. - Temporal-difference / Q-learning — backs up value estimates across a trajectory to credit earlier actions. - Bucket brigade (classifier systems, L8.8) — passes payment backward along a chain of rule firings. - EM — allocates responsibility for an observation across latent causes *probabilistically*.

Different mathematics (calculus, Bellman equations, economics, probability), identical challenge.