Naive Bayes, EM, Viterbi and Markov chains from scratch

Work in log space, always

Every model in this lesson multiplies probabilities: the likelihood of a hundred features, of a thousand observations, or of a path through two hundred hidden states. A product of two hundred numbers around 0.1 is 10⁻²⁰⁰; a product of four hundred is below the smallest float64 and rounds to zero. Once two competing products are both zero, you can no longer tell which is larger.

The remedy is the same in every case. Add log-probabilities instead of multiplying probabilities, and when you need a sum of probabilities, use the log-sum-exp from the stability lesson. Argmax is unchanged by the logarithm, so a classifier or a decoder never needs to leave log space at all.

Gaussian naive Bayes

Assume that, within each class, the features are independent and normally distributed. Fitting is then just counting: a prior per class, and a mean and variance per class and feature. Prediction picks the class with the largest log prior plus the sum over features of the log normal density. The independence assumption is almost never true, and the classifier often works anyway, because it only has to rank the classes correctly, not estimate their probabilities well.

One practical detail: a feature that is constant within a class has zero variance and an infinite density. scikit-learn adds a small amount, 10⁻⁹ times the largest feature variance, to every variance. Interviewers like to see that you know why.

Expectation–maximisation

A Gaussian mixture says each point came from one of K normal distributions, chosen with probabilities π_k. If we knew which component produced each point, fitting would be easy. EM alternates between guessing that and refitting:

• E-step: for each point, the responsibility r_ik is the posterior probability that component k produced it, computed in log space and normalised with log-sum-exp.
• M-step: refit each component as a weighted mean and variance, with the responsibilities as weights, and set π_k to the average responsibility.

Each iteration cannot decrease the likelihood. It can, however, converge to a poor local maximum, or let one component shrink onto a single point, where its variance goes to zero and the likelihood to infinity. Real implementations restart from several initialisations and put a floor under the variances.

Viterbi

A hidden Markov model has states you cannot see and observations you can. The Viterbi algorithm finds the single most likely sequence of hidden states. Checking every sequence costs S^T; dynamic programming brings it to S²T, by keeping, for each state, only the best path that ends there. A table of back-pointers recovers the path at the end.

cand = score[:, None] + log_trans     # cand[i, j]: best path to i, then move to j
back.append(cand.argmax(axis=0))
score = cand.max(axis=0) + log_emit[:, obs_t]

Stationary distributions

A Markov chain with transition matrix P settles, under mild conditions, into a distribution π that the chain leaves unchanged: πP = π. Quant interviews ask for it in disguise, as the long-run share of time a process spends in each regime. The equations πP = π are linearly dependent, since the rows of P sum to one, so replace one of them with Σπ_i = 1 and solve. Iterating π ← πP also works, slowly, and is the method to mention when the matrix is too large to factorise.

What interviewers listen for

• Log space before you are asked, and the reason.
• For naive Bayes, what the independence assumption costs and why it often does not matter.
• For EM, that the likelihood never decreases, and the two ways it fails.
• For Viterbi, the S²T cost and the back-pointers.