Rather than choosing the most likely model or delineating the set of all models that are consistent with the training data, another approach is to compute the posterior probability of each model given the training examples.

The idea of Bayesian learning is to compute the posterior probability distribution of the target features of a new example conditioned on its input features and all the training examples.

Suppose a new case has inputs $X=x$ (which we write simply as $x$) and target features $Y$. The aim is to compute $P(Y\mid x\wedge E)$, where $E$ is the set of training examples. This is the probability distribution of the target variables given the particular inputs and the examples. The role of a model is to be the assumed generator of the examples. If we let $M$ be a set of disjoint and covering models, then reasoning by cases and the chain rule give

The first two equalities follow from the definition of conditional probability. The last equality relies on two assumptions: the model includes all the information about the examples that is necessary for a particular prediction, $P(Y\mid m\wedge x\wedge E)=P(Y\mid m\wedge x)$, and the model does not change depending on the inputs of the new example, $P(m\mid x\wedge E)=P(m\mid E)$. Instead of choosing the best model, Bayesian learning relies on model averaging, averaging over the predictions of all the models, where each model is weighted by its posterior probability given the training examples.

$P(m\mid E)$ can be computed using Bayes’ rule:

Thus, the weight of each model depends on how well it predicts the data (the likelihood) and its prior probability. The denominator, $P(E)$, is a normalizing constant to make sure the posterior probabilities of the models sum to 1. $P(E)$ is called the partition function. Computing $P(E)$ may be very difficult when there are many models.

A set $\{e_1,\mathrm{\dots },e_k\}$ of examples are independent and identically distributed (i.i.d.), given model $m$ if examples $e_i$ and $e_j$, for $i\ne j$, are independent given $m$. If the set of training examples $E$ is $\{e_1,\mathrm{\dots },e_k\}$, the assumption that the examples are i.i.d. implies

The i.i.d. assumption can be represented as a belief network, shown in Figure 10.10, where each of the $e_i$ are independent given model $m$.

If $m$ is made into a discrete variable, any of the inference methods of the previous chapter could be used for inference in this network. A standard reasoning technique in such a network is to condition on every observed $e_i$ and to query the model variable or an unobserved $e_i$ variable.

The set of models may include structurally different models in addition to models that differ in the values of the parameters. One of the techniques of Bayesian learning is to make the parameters of the model explicit and to determine the distribution over the parameters.

The distribution of this example is known as the beta distribution; it is parameterized by two counts, ${\alpha }_0$ and ${\alpha }_1$, and a probability $p$. Traditionally, the ${\alpha }_i$ parameters for the beta distribution are one more than the counts; thus, ${\alpha }_i=n_i+1$. The beta distribution is

where $Z$ is a normalizing constant that ensures the integral over all values is 1. Thus, the uniform distribution on $[0,1]$ is the beta distribution $Bet{a}^{1,1}$.

Suppose instead that $Y$ is a discrete variable with $k$ different values. The generalization of the beta distribution to cover this case is known as the Dirichlet distribution. The Dirichlet distribution with two sorts of parameters, the “counts” ${\alpha }_1,\mathrm{\dots },{\alpha }_k$, and the probability parameters $p_1,\mathrm{\dots },p_k$, is

where $p_i$ is the probability of the $i$th outcome (and so $0\le p_i\le 1$) and ${\alpha }_i$ is a non-negative real and $Z$ is a normalizing constant that ensures the integral over all the probability values is 1. We can think of $a_i$ as one more than the count of the $i$th outcome, ${\alpha }_i=n_i+1$. The Dirichlet distribution looks like Figure 10.11 along each dimension (i.e., as each $p_j$ varies between 0 and 1).

For many cases, averaging over all models weighted by their posterior distribution is difficult, because the models may be complicated (e.g., if they are decision trees or even belief networks). For the Dirichlet distribution, the expected value for outcome $i$ (averaging over all $p_j$) is

The reason that the ${\alpha }_i$ parameters are one more than the counts in the definitions of the beta and Dirichlet distributions is to make this formula simple. This fraction is well defined only when the ${\alpha }_j$ are all non-negative and not all are zero.

An agent does not have to start with a uniform prior; it could start with any prior distribution. If the agent starts with a prior that is a Dirichlet distribution, its posterior will be a Dirichlet distribution. The posterior distribution can be obtained by adding the observed counts to the ${\alpha }_i$ parameters of the prior distribution.

Thus, the beta and Dirichlet distributions provide a justification for using pseudocounts for estimating probabilities. The pseudocount represents the prior knowledge. A flat prior gives a pseudocount of 1. Thus, Laplace smoothing can be justified in terms of making predictions from initial ignorance.

In addition to using the posterior distribution of $\varphi$ to derive the expected value, we can use it to answer other questions such as: What is the probability that the posterior probability, $\varphi$, is in the range $[a,b]$? In other words, derive $P((\varphi \ge a\wedge \varphi \le b)\mid e)$. This is the problem that the Reverend Thomas Bayes solved more than 250 years ago [Bayes, 1763]. The solution he gave – although in much more cumbersome notation – was

This kind of knowledge is used in surveys when it may be reported that a survey is correct with an error of at most $5\%$, $19$ times out of $20$. It is also the same type of information that is used by probably approximately correct (PAC) learning, which guarantees an error at most $ϵ$ at least $1-\delta$ of the time. If an agent chooses the midpoint of the range $[a,b]$, namely $\frac{a+b}{2}$, as its hypothesis, it will have error less than or equal to $\frac{b-a}{2}$, just when the hypothesis is in $[a,b]$. The value $1-\delta$ corresponds to $P(\varphi \ge a\wedge \varphi \le b\mid e)$. If $ϵ=\frac{b-a}{2}$ and $\delta =1-P(\varphi \ge a\wedge \varphi \le b\mid e)$, choosing the midpoint will result in an error at most $ϵ$ in $1-\delta$ of the time. PAC learning gives worst-case results, whereas Bayesian learning gives the expected number. Typically, the Bayesian estimate is more accurate, but the PAC results give a guarantee of a bound on the error. The sample complexity, the number of samples required to obtain some given accuracy, for Bayesian learning is typically much less than that of PAC learning – many fewer examples are required to expect to achieve the desired accuracy than are needed to guarantee the desired accuracy.