Learning Probabilistic Models

A Bayesian network gives you exact and approximate inference once its conditional probability tables are filled in — but the previous lessons on uncertainty simply assumed those numbers. Where does $P(Alarm\mid Burglary,Earthquake)$ come from? An expert can supply a few, but in most domains the tables are learned from data. This lesson is about that step: estimating the parameters of a probabilistic model, and even its structure, from observations. The organizing idea: learning is a form of uncertain reasoning from observations.¹ The data are evidence; the hypotheses are probabilistic theories of the domain; and Bayes' rule tells you exactly how the evidence should move your belief.

Statistical learning

Start with a small example. A candy manufacturer sells bags of cherry and lime candy, each piece wrapped opaquely so you cannot see its flavor until you unwrap it. There are five kinds of bag, and from the outside they are indistinguishable:

Buy a bag and the type is an unobserved random variable $H$ ranging over $h_1$ through $h_5$. As you unwrap pieces you observe data $D_1,D_2,\dots ,D_N$, each $D_i$ taking the value cherry or lime. The task is to predict the flavor of the next piece.

Bayesian learning computes the probability of each hypothesis given the data, then predicts by using all the hypotheses weighted by their probabilities. Learning reduces to inference. Writing $\mathbf{d}$ for the observed data, Bayes' rule gives the posterior over hypotheses,

where $P(h_i)$ is the hypothesis prior and $P(\mathbf{d}\mid h_i)$ is the likelihood of the data under hypothesis $h_i$. A prediction about an unknown quantity $X$ is then the posterior-weighted average of each hypothesis's prediction,

The hypotheses act as intermediaries between the raw data and the prediction. Assuming the observations are independent and identically distributed, the likelihood factors into a product over the individual pieces,

Suppose the manufacturer advertises the prior $⟨0.1,0.2,0.4,0.2,0.1⟩$ over $h_1,\dots ,h_5$, the bag is really all lime ($h_5$), and every piece you unwrap is lime. Under $h_3$, each lime piece has probability $0.5$, so after ten limes $P(\mathbf{d}\mid h_3)=0.5^{10}$, a tiny number; under $h_5$ the likelihood stays $1$. The posterior therefore concentrates on $h_5$ as evidence accumulates.

Bayesian prediction has two strong properties. First, the Bayesian prediction eventually agrees with the true hypothesis: for any prior that does not rule the truth out, the posterior probability of every false hypothesis vanishes as data accumulate, because the chance of generating data uncharacteristic of the truth forever is vanishingly small. Second, the Bayesian prediction is optimal: given the prior, no other prediction is expected to be correct more often. The catch is cost. Real hypothesis spaces are large or infinite, and the sum over hypotheses (or the integral, in the continuous case) is usually intractable, forcing the approximations that occupy the rest of this lesson.

MAP: predicting from the single best hypothesis

The most common approximation predicts from a single most probable hypothesis — the $h_i$ that maximizes $P(h_i\mid \mathbf{d})$. This is the maximum a posteriori, or MAP, hypothesis $h_{\text{MAP}}$. Its predictions approximate the Bayesian ones to the extent that $\mathbf{P}(X\mid \mathbf{d})\approx \mathbf{P}(X\mid h_{\text{MAP}})$. In the candy example, after three limes in a row $h_5$ is already the MAP hypothesis, so the MAP learner predicts the fourth piece is lime with probability $1.0$ — a more confident (and more dangerous) claim than the Bayesian $0.8$. As data arrive the two converge, because the rivals to $h_{\text{MAP}}$ become ever less probable.

MAP is often far cheaper than full Bayesian learning: it is an optimization problem — find the best hypothesis — rather than a large summation problem.

The prior also controls overfitting. Overfitting happens when a hypothesis space is expressive enough to contain theories that fit the data too well. Rather than capping complexity by hand, Bayesian and MAP learning let the prior penalize complexity: more complex hypotheses typically carry lower prior probability. Take logarithms of the MAP objective and maximizing $P(\mathbf{d}\mid h_i)P(h_i)$ becomes minimizing

By the information-theoretic reading, $-{\log }_{2}P(h_i)$ is the number of bits to describe the hypothesis and $-{\log }_{2}P(\mathbf{d}\mid h_i)$ the extra bits to describe the data given it. MAP chooses the hypothesis that most compresses the data — the minimum description length principle in another guise, and a natural embodiment of Ockham's razor.

Maximum likelihood

Assume a uniform prior — no hypothesis preferred a priori — and MAP collapses to choosing the $h_i$ that maximizes the likelihood $P(\mathbf{d}\mid h_i)$ alone. This is the maximum-likelihood (ML) hypothesis, $h_{\text{ML}}$.

Maximum likelihood is the default in classical statistics, where the subjective choice of prior is often distrusted. It is a reasonable approximation to Bayesian and MAP learning when the data set is large enough to swamp the prior, but it has real trouble with small data sets — a point that returns when we reach priors.

Learning with complete data

Learning a probability model from data assumed to be generated by that model is called density estimation. Take the simplest case first: complete data, where every data point specifies a value for every variable in the model. The job is parameter learning — finding the numbers for a model whose structure is already fixed, such as the conditional probabilities of a Bayesian network with a known graph.

Maximum likelihood for discrete models

Buy a bag whose cherry proportion is completely unknown — anywhere from $0$ to $1$. Call that proportion the parameter $\theta$; the hypothesis is $h_{\theta }$, and a lime has probability $1-\theta$. Model it as a one-node Bayesian network with a single variable Flavor whose CPT is $P(Flavor=cherry)=\theta$.

Unwrap $N$ candies, of which $c$ are cherries and $\ell =N-c$ are limes. The likelihood of that data set is

The maximum-likelihood $\theta$ maximizes this. Products are awkward to differentiate, so maximize the log likelihood instead — the same maximizer, since $\log$ is monotone:

Differentiate, set to zero, and solve:

The maximum-likelihood estimate is the observed fraction of cherries. It confirms common sense, and it lays out the standard procedure for ML parameter learning, which carries far beyond this toy:

1. Write the likelihood of the data as a function of the parameters.
2. Take the log and differentiate with respect to each parameter.
3. Find the parameter values that make the derivatives zero.

Step 3 is the trickiest; here it was closed-form, but many models need iterative numerical optimization. And ML has a built-in hazard on small data: if an event has not yet been observed — no cherry unwrapped — its ML probability is zero, which then zeroes out any prediction that multiplies by it. A common patch initializes each count to $1$ instead of $0$.

Add a second variable and the same machinery decomposes cleanly. Suppose the wrapper color (red or green) is chosen probabilistically depending on flavor, with ${\theta }_1=P(red\mid cherry)$ and ${\theta }_2=P(red\mid lime)$. With counts $r_c,g_c$ of red/green cherry wrappers and $r_{\ell },g_{\ell }$ for limes, the log likelihood splits into three terms, one per parameter,

so setting the three derivatives to zero gives three independent solutions, $\hat{\theta }=c/(c+\ell )$, ${\hat{\theta }}_1=r_c/(r_c+g_c)$, and ${\hat{\theta }}_2=r_{\ell }/(r_{\ell }+g_{\ell })$. This is the general fact: with complete data, the ML parameter-learning problem for a Bayesian network decomposes into a separate problem for each parameter, and each CPT entry is just the observed frequency of its variable's value for the given parent setting.

Naive Bayes

The most widely used Bayesian-network model in machine learning is naive Bayes: a class variable $C$ at the root and attribute variables $X_1,\dots ,X_n$ as leaves, with the attributes assumed conditionally independent of one another given the class. The wrapper model above is naive Bayes with class Flavor and one attribute. Assuming Boolean variables, its parameters are

each learned by the same counting. Once trained, classify a new example with observed attributes $x_1,\dots ,x_n$ by

and predict the most probable class. With $n$ Boolean attributes there are just $2n+1$ parameters, no search is needed to find $h_{\text{ML}}$, and the method handles noisy or missing data gracefully. It scales to very large problems, and its independence assumption, though usually false, costs it little accuracy across a wide range of applications.

Maximum likelihood for a Gaussian

Continuous variables need continuous densities, but the recipe is unchanged. Take the single-variable Gaussian, whose parameters are the mean $\mu$ and standard deviation $\sigma$,

The normalizing constant depends on $\sigma$, so it cannot be ignored. For observed values $x_1,\dots ,x_N$ the log likelihood is

Setting the partial derivatives to zero gives the estimators every statistics course states without derivation:

The ML mean is the sample average and the ML standard deviation is the root of the sample variance. One consequence is worth stating because it connects to supervised regression: for a linear-Gaussian child $Y$ whose mean is ${\theta }_{1}x+{\theta }_2$ and whose variance is fixed, maximizing the likelihood over ${\theta }_1,{\theta }_2$ is identical to minimizing the squared error ${\sum }_j(y_j-({\theta }_1{x}_j+{\theta }_2){)}^2$. Least-squares linear regression is maximum-likelihood estimation under Gaussian noise of fixed variance — that is why minimizing sum of squared errors is the right thing to do.

Bayesian parameter learning

Maximum likelihood breaks down on small samples. Unwrap a single cherry and the ML hypothesis declares the bag $100\%$ cherry, $\hat{\theta }=1.0$ — an absurd conclusion from one data point. The Bayesian remedy is to start with a hypothesis prior over $\theta$ and update it to a posterior as data arrive, exactly as in the statistical-learning frame but now with a continuous parameter.

Here $\theta$ is the value of a random variable $\Theta$, and the prior is a density $\mathbf{P}(\Theta )$ nonzero on $[0,1]$ that integrates to $1$. The uniform density is one candidate, but the more useful family is the beta distributions, each fixed by two hyperparameters $a$ and $b$:

where $\alpha$ normalizes the density. The mean is $a/(a+b)$, so larger $a$ pushes belief toward $\theta$ near $1$; larger $a+b$ makes the distribution more peaked, encoding greater certainty.

The beta family has a property that makes the arithmetic collapse: it is a conjugate prior for a Boolean variable. Start with $\Theta \sim \text{beta}[a,b]$, observe one cherry, and the posterior is again a beta:

Observing a cherry increments $a$; observing a lime increments $b$. The hyperparameters act as virtual counts: a prior $\text{beta}[a,b]$ behaves as if you had started from a uniform $\text{beta}[1,1]$ and already seen $a-1$ cherries and $b-1$ limes. This corrects the single-cherry pathology — the prior's virtual counts keep the estimate reasonable until real data dominate. As $a$ and $b$ grow with the true proportion (the sequence $\text{beta}[3,1]$, $\text{beta}[6,2]$, $\text{beta}[30,10]$ for a $75\%$-cherry bag), the posterior converges to a narrow peak at the true value, and Bayesian learning agrees with maximum likelihood in the large-data limit.

With several parameters, one usually assumes parameter independence — $\mathbf{P}(\Theta ,{\Theta }_1,{\Theta }_2)=\mathbf{P}(\Theta )\mathbf{P}({\Theta }_1)\mathbf{P}({\Theta }_2)$ — so each gets its own beta, updated separately. The whole Bayesian learning process can then be drawn as one big Bayesian network: parameter nodes with no parents, and one observation node per data point that depends on the relevant parameter. Learning and prediction become a single inference problem in that network, which is why there is just one learning algorithm — the inference algorithm for Bayesian networks.

Learning Bayes-net structure

So far the graph was given and only the numbers were learned. When the causal structure itself is unknown or disputed, it too can be learned from data. The obvious approach is search over structures: begin from a graph with no links (or an initial guess), then add, delete, or reverse edges by hill-climbing or simulated annealing, refitting the parameters after each change and scoring the result. Cycles must be avoided, so many algorithms assume a variable ordering and let a node take parents only among earlier nodes.

Deciding when a structure is good enough splits two ways. One tests whether the conditional independences the structure asserts actually hold in the data, using a statistical significance test — a stricter test admits more links and risks overfitting. The other, more in keeping with this lesson, scores how well the model explains the data probabilistically. Pure maximum likelihood is no help here: adding a parent can never decrease the likelihood, so it would drive you to a fully connected graph. The fix is again to penalize complexity — a MAP or MDL penalty subtracted from the fitted likelihood of each structure, or a full Bayesian prior over structures with MCMC to sample the superexponentially many candidates.

Everything so far assumed complete data — every example fixes a value for every variable. Real data are rarely so tidy: a disease behind its symptoms, a cluster behind its points, a sender behind a message all stay hidden. Learning then cannot proceed by counting, because you cannot count what you cannot see. That case, and the algorithm that solves it, continue in Learning with Hidden Variables: The EM Algorithm.