---
title: Learning Probabilistic Models
module: Learning
moduleNumber: 5
lessonNumber: 3
order: 503
summary: >
  A [Bayesian network](/artificial-intelligence/uncertainty/bayesian-networks) is
  useless until its numbers are filled in, and those numbers come from data. This
  first part casts learning itself as probabilistic inference: hypotheses carry a
  prior, data update it to a posterior, and predictions average over what remains.
  From that frame fall the standard estimators — maximum likelihood by counting,
  MAP with a conjugate prior, full Bayesian updating — for the case where every
  variable is observed. A second part takes up the harder case of hidden variables
  and the EM algorithm.
topics: [Learning]
sources:
  - book: AIMA
    ref: "Ch. 20 — Learning Probabilistic Models; §20.1 Statistical Learning; §20.2 Learning with Complete Data"
---


A [Bayesian network](/artificial-intelligence/uncertainty/bayesian-networks) 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**.[^stat] 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:

$$
\begin{aligned}
h_1&: 100\% \text{ cherry}, \\
h_2&: 75\% \text{ cherry} + 25\% \text{ lime}, \\
h_3&: 50\% \text{ cherry} + 50\% \text{ lime}, \\
h_4&: 25\% \text{ cherry} + 75\% \text{ lime}, \\
h_5&: 100\% \text{ lime}.
\end{aligned}
$$

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, \ldots, 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,

$$
P(h_i \mid \mathbf{d}) = \alpha\, P(\mathbf{d} \mid h_i)\, P(h_i),
$$

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,

$$
\mathbf{P}(X \mid \mathbf{d}) = \sum_i \mathbf{P}(X \mid h_i)\, P(h_i \mid \mathbf{d}).
$$

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,

$$
P(\mathbf{d} \mid h_i) = \prod_j P(d_j \mid h_i).
$$

Suppose the manufacturer advertises the prior $\langle 0.1, 0.2, 0.4, 0.2, 0.1
\rangle$ over $h_1, \ldots, 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.

$$
% caption: The posterior $P(h_i \mid d_1,\dots,d_N)$ as a run of lime candies is
% observed. Starting at the prior, mass drains from hypotheses that assign the data
% low likelihood ($h_1$ dies at the first lime) and piles onto $h_5$, the true bag.
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % axes
  \draw[->, black] (0,0) -- (7.9,0);
  \node[black, font=\footnotesize, anchor=north] at (3.6,-0.55) {observations N};
  \draw[->, black] (0,0) -- (0,4.1) node[anchor=east, black, font=\footnotesize, rotate=90, yshift=6mm] {posterior};
  \foreach \x/\l in {0/0, 2/2, 4/4, 6/6} \draw[black] (\x,0.05) -- (\x,-0.05) node[anchor=north, black, font=\scriptsize] {\l};
  \foreach \y/\l in {0/0, 2/0.5, 4/1} \draw[black] (0.05,\y) -- (-0.05,\y) node[anchor=east, black, font=\scriptsize] {\l};
  % h5 rising to 1
  \draw[acc, very thick] (0,0.8) .. controls (2,2.6) and (4,3.6) .. (6,3.9);
  \node[acc, anchor=west, font=\footnotesize] at (6.15,3.9) {h5};
  % h3 rise then fall
  \draw[red, thick] (0,3.2) .. controls (1.2,3.0) and (2.5,1.4) .. (6,0.7);
  \node[red, anchor=west, font=\footnotesize] at (6.15,0.7) {h3};
  % h4 modest bump then decline
  \draw[black, thick] (0,1.6) .. controls (1.5,2.0) and (3,1.1) .. (6,1.15);
  \node[black, anchor=west, font=\footnotesize] at (6.15,1.15) {h4};
  % h2 small then to zero
  \draw[black, dashed] (0,1.6) .. controls (1,0.9) and (3,0.2) .. (6,0.25);
  \node[black, anchor=west, font=\footnotesize] at (6.15,0.25) {h2};
  % h1 dies at first lime
  \draw[black, dotted, thick] (0,0.8) -- (0.6,0);
  \node[black, anchor=south west, font=\scriptsize] at (0.35,0.02) {h1};
\end{tikzpicture}
$$

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.

> **Definition (MAP hypothesis).** $h_{\text{MAP}} = \arg\max_{h_i} P(h_i \mid
> \mathbf{d}) = \arg\max_{h_i} P(\mathbf{d} \mid h_i)\, P(h_i)$. It maximizes the
> product of likelihood and prior, then predicts as if that hypothesis were the
> only one.

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

$$
-\log_2 P(\mathbf{d} \mid h_i) \; - \; \log_2 P(h_i).
$$

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}}$.

> **Definition (Maximum-likelihood hypothesis).** $h_{\text{ML}} = \arg\max_{h_i}
> P(\mathbf{d} \mid h_i)$, the hypothesis under which the observed data are most
> probable. It is the MAP hypothesis under a uniform prior.

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$.

$$
% caption: The candy model as a Bayesian network; the boxes hold the CPT
% parameters. (a) One parameter $\theta = P(Flavor = cherry)$. (b) Adding a wrapper
% color that depends on flavor gives a naive-Bayes model with three parameters:
% $\theta$, and $\theta_1 = P(red \mid cherry)$, $\theta_2 = P(red \mid lime)$.
\begin{tikzpicture}[>=stealth, font=\small,
  var/.style={draw, ellipse, minimum width=18mm, minimum height=8mm},
  cpt/.style={draw, black, font=\footnotesize, inner sep=3pt}]
  \definecolor{acc}{HTML}{2348F2}
  % (a)
  \node[var] (fa) at (0,0) {Flavor};
  \node[cpt, anchor=south] at (0,0.95) {t};
  \node[font=\footnotesize, black] at (0,-1.3) {(a)};
  % (b)
  \begin{scope}[xshift=6.4cm]
    \node[var] (fb) at (0,1.6) {Flavor};
    \node[var] (wb) at (0,-1.4) {Wrapper};
    \node[cpt, anchor=south] at (0,2.55) {t};
    \node[cpt, anchor=west, align=left] at (1.35,0.1) {t1, t2};
    \draw[->, acc, thick] (fb) -- (wb);
    \node[font=\footnotesize, black] at (0,-2.7) {(b)};
  \end{scope}
\end{tikzpicture}
$$

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

$$
P(\mathbf{d} \mid h_\theta) = \prod_{j=1}^{N} P(d_j \mid h_\theta)
  = \theta^{c} \, (1 - \theta)^{\ell}.
$$

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

$$
L(\mathbf{d} \mid h_\theta) = \log P(\mathbf{d} \mid h_\theta)
  = c \log \theta + \ell \log(1 - \theta).
$$

Differentiate, set to zero, and solve:

$$
\frac{dL}{d\theta} = \frac{c}{\theta} - \frac{\ell}{1 - \theta} = 0
  \quad\Longrightarrow\quad
  \hat\theta = \frac{c}{c + \ell} = \frac{c}{N}.
$$

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,

$$
L = \big[c \log\theta + \ell \log(1{-}\theta)\big]
  + \big[r_c \log\theta_1 + g_c \log(1{-}\theta_1)\big]
  + \big[r_\ell \log\theta_2 + g_\ell \log(1{-}\theta_2)\big],
$$

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, \ldots, 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

$$
\theta = P(C = true), \quad \theta_{i1} = P(X_i = true \mid C = true),
  \quad \theta_{i2} = P(X_i = true \mid C = false),
$$

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

$$
\mathbf{P}(C \mid x_1, \ldots, x_n) = \alpha \, \mathbf{P}(C) \prod_i \mathbf{P}(x_i \mid C),
$$

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$,

$$
P(x) = \frac{1}{\sqrt{2\pi}\,\sigma}\, e^{-\frac{(x - \mu)^2}{2\sigma^2}}.
$$

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

$$
L = N(-\log\sqrt{2\pi} - \log\sigma) - \sum_{j=1}^{N} \frac{(x_j - \mu)^2}{2\sigma^2}.
$$

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

$$
\hat\mu = \frac{\sum_j x_j}{N},
  \qquad
  \hat\sigma = \sqrt{\frac{\sum_j (x_j - \hat\mu)^2}{N}}.
$$

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$:

$$
\text{beta}[a, b](\theta) = \alpha \, \theta^{a-1} (1 - \theta)^{b-1},
  \qquad \theta \in [0, 1],
$$

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.

$$
% caption: The beta family for several $[a,b]$. beta$[1,1]$ is uniform; equal
% hyperparameters center the mass at $\theta{=}0.5$ and a larger sum sharpens the
% peak; unequal ones (e.g. $[30,10]$) push a tall peak toward the implied mean.
\begin{tikzpicture}[>=stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \draw[->, black] (0,0) -- (6.7,0);
  \node[black, font=\footnotesize, anchor=north] at (3.2,-0.55) {parameter t};
  \draw[->, black] (0,0) -- (0,4.2) node[anchor=east, black, font=\footnotesize, rotate=90, yshift=6mm] {density};
  \foreach \x/\l in {0/0, 3/0.5, 6/1} \draw[black] (\x,0.05) -- (\x,-0.05) node[anchor=north, black, font=\scriptsize] {\l};
  % beta[1,1] uniform
  \draw[black, dashed] (0,1.0) -- (6,1.0);
  \node[black, anchor=west, font=\scriptsize] at (6.1,1.0) {[1,1]};
  % beta[2,2] gentle hump at 0.5
  \draw[black!70, thick] (0,0) .. controls (1.5,1.9) and (4.5,1.9) .. (6,0);
  \node[black!70, anchor=south, font=\scriptsize] at (2.0,1.55) {[2,2]};
  % beta[5,5] tall peak at 0.5
  \draw[acc, very thick] (0,0) .. controls (2.4,3.3) and (3.6,3.3) .. (6,0);
  \node[acc, anchor=south, font=\scriptsize] at (2.5,3.05) {[5,5]};
  % beta[30,10] tall skewed peak toward 0.75
  \draw[red, thick] (2.4,0) .. controls (3.9,0.3) and (4.3,3.5) .. (4.7,3.5) .. controls (5.1,3.5) and (5.4,0.6) .. (5.9,0.05);
  \node[red, anchor=west, font=\scriptsize] at (5.0,3.3) {[30,10]};
\end{tikzpicture}
$$

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:

$$
P(\theta \mid D_1 = cherry) = \alpha'\, \theta \cdot \text{beta}[a,b](\theta)
  = \alpha'\, \theta^{a}(1-\theta)^{b-1} = \text{beta}[a+1, b](\theta).
$$

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.

> **Definition (Conjugate prior).** A prior family closed under Bayesian updating
> for a given likelihood: the posterior after observing data belongs to the _same_
> family, so updating reduces to adjusting hyperparameters. The beta is conjugate
> for Boolean data; the **Dirichlet** generalizes it to discrete multivalued
> variables, and the **Normal–Wishart** serves Gaussian parameters.

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](/artificial-intelligence/learning/expectation-maximization).

[^stat]: **AIMA**, Ch. 20 — Learning Probabilistic Models, §20.1 Statistical Learning: learning framed as Bayesian inference over hypotheses, with the candy-bag example, the hypothesis prior and likelihood, and the MAP and maximum-likelihood approximations to full Bayesian prediction.