Probabilistic Modeling
Learning Objectives
After reading this page, you should be able to:
- Derive the maximum likelihood estimate (MLE) of a model parameter.
- Explain why the MLE can overfit when data is limited.
- Derive the maximum a-posteriori (MAP) estimate of a model parameter.
- Explain how the prior influences the MAP estimate as the dataset grows.
1 Introduction
Probabilistic modeling is a central idea in machine learning that allows us to reason about uncertainty. The main idea is that we assume that observed data was generated from a distribution and we try to approximately learn this distribution (training). Once learned, we can use this distribution to make predictions (inference) or generate samples from that distribution.
Let’s use the following example to build some intuition. We play in a soccer league and have been recording our team’s wins and losses. For this example, let’s assume that each game results in a win or a loss (i.e., there are no draws). We note that our team has won \(14\) of the \(20\) games played. Based on these observations, what do you believe is the probability that our team wins the next game?
If you answered \(0.7\), which is \(14\) out of \(20\), you were using methods of probabilistic reasoning. Rather than accepting this intuitively, in this chapter, we will formally present the reasoning behind deriving this estimate.
2 A Probabilistic Model for Winning Games
Our goal is to estimate the probability that our team wins the next game. To do this, we need to define three things: a probabilistic model for the outcome of each game, the dataset of games we have observed, and our goal stated in terms of the model.
2.1 The Model
We will model the outcome of each soccer game using a probabilistic model. To start, let’s represent the outcome of one game with a binary random variable \(X\), which is \(1\) if our team wins the game, and \(0\) if our team loses the game: \[ \begin{aligned} & X \in \{0, 1\} \end{aligned} \] Since there are only two outcomes, a natural probabilistic model for the game outcome is the Bernoulli distribution.
Definition: A binary random variable \(X \in \{0, 1\}\) follows a Bernoulli distribution with parameter \(\theta \in [0, 1]\) if \(X = 1\) with probability \(\theta\) and \(X = 0\) with probability \(1 - \theta\): \[ \begin{aligned} & P(X = 1 \,;\, \theta) = \theta, \quad\quad P(X = 0 \,;\, \theta) = 1 - \theta \end{aligned} \tag{1}\] We write this as \[ \begin{aligned} & X \sim \mathrm{Bernoulli}(\theta) \end{aligned} \]
In our model, we assume that the outcome \(X\) of each game is drawn from a Bernoulli distribution, where the parameter \(\theta\) represents the probability that our team wins a game.
We can combine the probabilities of a win and a loss into one compact expression. We call this the exponent trick, because the exponent acts as a switch that selects which factor appears. \[ \begin{aligned} & P(X = x \,;\, \theta) = \theta^{x} (1 - \theta)^{1 - x}, \qquad \forall x \in \{0, 1\} \end{aligned} \tag{2}\]
Question: Prove that the expressions in Equation 1 and Equation 2 are equivalent.
Answer:
When \(X = 1\), we have \[ \begin{aligned} & P(X = 1 \,;\, \theta) = \theta^{1} (1 - \theta)^{1 - 1} \\ & = \theta \end{aligned} \]
Similarly, when \(X = 0\), we get \[ \begin{aligned} & P(X = 0 \,;\, \theta) = \theta^{0} (1 - \theta)^{1 - 0} \\ & = (1 - \theta) \end{aligned} \]
The exponents act as switches that select the right factor.
In machine learning, we write a semicolon instead of a vertical bar when conditioning on model parameters: \[ \begin{aligned} & P(X = x \,;\, \theta) = P(X = x \mid \theta) \end{aligned} \] Both expressions mean the probability that \(X = x\) when the parameter has the value \(\theta\). The semicolon emphasizes that \(\theta\) is a fixed value we want to learn, not a random variable. We use the semicolon only for model parameters. In MAP learning, where we treat \(\theta\) as a random variable, we will switch back to the vertical bar notation.
2.2 Inference
Suppose for a moment that we knew the value of \(\theta\). Then predicting the outcome of the next game would be easy. By our model, the probability that our team wins the next game is \[ \begin{aligned} & P(X = 1 \,;\, \theta) = \theta \end{aligned} \] This step of using the model to make predictions is called inference. The difficulty is that we do not know \(\theta\). Instead, we must estimate it from the games we have observed, which is the focus of the rest of this chapter.
2.3 The Dataset
In our example, our team won \(14\) out of the \(20\) games played. More generally, suppose our team has played \(N\) games. The outcomes of these \(N\) games become our dataset, which we formally represent as follows: \[ \begin{aligned} & \mathcal{D} = \{ x^{(1)}, x^{(2)}, \ldots, x^{(N)} \} \end{aligned} \] where \(x^{(i)}=1\) if our team won the \(i\)-th game and \(0\) otherwise. Each \(x^{(i)}\) is the observed outcome of one game, which we model using the Bernoulli distribution above.
2.4 The Goal
We can now restate our goal using the model. Given the observed outcomes in the dataset \(\mathcal{D}\), we want to estimate \(\theta\), the probability that our team wins a game.
3 The Maximum Likelihood Estimate (MLE)
Before defining the maximum likelihood estimate, let’s first understand the likelihood function.
3.1 Understanding the Likelihood Function
To estimate \(\theta\), we need a way to measure how well a particular value of \(\theta\) explains the observed outcomes. For this, we use the likelihood function.
Definition: The likelihood function is a function of the model parameters \(\theta\). It measures the probability of observing the data \(\mathcal{D}\) for a particular value of \(\theta\): \[ \begin{aligned} & L (\theta) = P(\mathcal{D} \,;\, \theta) \end{aligned} \]
For example, if \(\theta = 0\), the team never wins, so it is impossible to observe \(14\) wins out of \(20\) games. The likelihood is therefore zero for \(\theta = 0\).
Let’s derive an expression for the likelihood function for our example. The likelihood of our dataset \(\mathcal{D}\) is simply the joint probability of all the data points: \[ \begin{aligned} & L (\theta) = P(\mathcal{D} \,;\, \theta) \\ & = P(X^{(1)} = x^{(1)}, X^{(2)} = x^{(2)}, \ldots, X^{(N)} = x^{(N)} \,;\, \theta) \end{aligned} \] To simplify this joint probability, we make a standard assumption about how the data was generated.
Definition: The data points are independent and identically distributed (i.i.d.) if they satisfy two conditions. They are independent, meaning that the value of one data point does not change the probability of any other data point. They are identically distributed, meaning that every data point is drawn from the same distribution with the same parameters.
In our example, the i.i.d. assumption means that the outcome of one game does not affect the outcome of any other game, and that our team wins every game with the same probability \(\theta\).
The i.i.d. assumption lets us break the joint probability into simple pieces. Because the outcomes are independent, the joint probability is the product of the individual probabilities: \[ \begin{aligned} & P(X^{(1)} = x^{(1)}, X^{(2)} = x^{(2)}, \ldots, X^{(N)} = x^{(N)} \,;\, \theta) \\ & = \prod_{i=1}^{N} P(X^{(i)} = x^{(i)} \,;\, \theta) \end{aligned} \] Because the outcomes are identically distributed, every factor in this product comes from the same Bernoulli distribution with parameter \(\theta\). So we can drop the superscript on each random variable: \[ \begin{aligned} & P(X^{(i)} = x^{(i)} \,;\, \theta) = P(X = x^{(i)} \,;\, \theta), \qquad i = 1, \ldots, N \end{aligned} \] Applying Equation 2 to each factor, we get: \[ \begin{aligned} & L (\theta) = \prod_{i=1}^{N} P(X = x^{(i)} \,;\, \theta) = \prod_{i=1}^{N} \left[ \theta^{x^{(i)}} (1 - \theta)^{1 - x^{(i)}} \right] \end{aligned} \]
3.2 The MLE Criterion
The likelihood function motivates a natural approach for estimating the parameter \(\theta\). Can we pick the value for the parameter \(\theta\) to make the observed data the most probable? Answering this question requires us to compute the maximum likelihood estimate of the parameter \(\theta\).
Definition: The maximum likelihood estimate (MLE) of the parameter \(\theta\) is the value of \(\theta\) that maximizes the likelihood function: \[ \begin{aligned} & \hat{\theta}_{\text{MLE}} = \arg\max_{\theta \in [0, 1]} L(\theta) \\ & = \arg\max_{\theta \in [0, 1]} P(\mathcal{D} \,;\, \theta) \end{aligned} \]
3.3 Computing the MLE
If you answered \(0.7\) to the question in the introduction, you already know how to compute the MLE intuitively. The MLE is typically the empirical frequency of the outcome we care about, in our case the fraction of games our team won. In the rest of this section, we will formally derive the mathematical formula for this estimate. Going through the derivation explains why this intuitive approach makes sense, and it gives us a general method that we can apply to other models.
Once we have the estimate, we can use it for inference, as described in Section 2.2. Plugging the MLE into our model, we predict that our team wins the next game with probability \[ \begin{aligned} & P(X = 1 \,;\, \hat{\theta}_{\text{MLE}}) = \hat{\theta}_{\text{MLE}} \\ & = 0.7 \end{aligned} \]
3.4 The Log-Likelihood
In practice, we usually work with the log-likelihood \(\ell(\theta)\) instead. \[ \begin{aligned} & \hat{\theta}_{\text{MLE}} = \arg\max_{\theta \in [0, 1]} \ell(\theta) \end{aligned} \]
There are three good reasons to maximize the log-likelihood instead of the likelihood. First, because \(\log\) is strictly increasing, the log-likelihood has its maximum at exactly the same \(\theta\), so nothing is lost. Second, the log turns products into sums, which are efficient to compute and far easier to differentiate. Third, it is numerically stable. A product of many numbers in \([0,1]\) can underflow to \(0\), but a sum of their logs does not.
Try deriving an expression for the log-likelihood yourself. The question below provides the starting point and the final expression.
Question: Starting from the likelihood function \[ \begin{aligned} & L (\theta) = \prod_{i=1}^{N} \theta^{x^{(i)}} (1 - \theta)^{1 - x^{(i)}}, \end{aligned} \] show that the log-likelihood can be written as follows: \[ \begin{aligned} & \ell(\theta) = \log(\theta) \left( \sum_{i=1}^{N} x^{(i)} \right) \\ & \qquad + \log(1 - \theta) \left( \sum_{i=1}^{N} \left(1 - x^{(i)} \right) \right) \end{aligned} \]
Answer:
\[ \begin{aligned} \ell(\theta) & = \log L (\theta) \\[0.5em] & = \log \left[ \prod_{i=1}^{N} \left( \theta^{x^{(i)}} (1 - \theta)^{1 - x^{(i)}} \right) \right] \\[0.5em] & = \sum_{i=1}^{N} \log \left( \theta^{x^{(i)}} (1 - \theta)^{1 - x^{(i)}} \right) \\[0.5em] & = \sum_{i=1}^{N} \left[ x^{(i)} \log(\theta) + \left(1 - x^{(i)} \right) \log(1 - \theta) \right] \\[0.5em] & = \log(\theta) \left( \sum_{i=1}^{N} x^{(i)} \right) + \log(1 - \theta) \left( \sum_{i=1}^{N} \left(1 - x^{(i)} \right) \right) \end{aligned} \]
Note that the two sums in this expression have simple meanings. The first sum is essentially the number of “1”s in our dataset, or equivalently, the number of games our team won. Similarly, the second sum is simply the number of games lost. We denote these counts by \(N_{\text{win}}\) and \(N_{\text{loss}}\), respectively. \[ \begin{aligned} & N_{\text{win}} = \sum_{i=1}^{N} x^{(i)} \\ & N_{\text{loss}} = \sum_{i=1}^{N} \left(1 - x^{(i)}\right) \end{aligned} \] We can therefore simplify the above expression as follows. \[ \begin{aligned} & \ell(\theta) = \log(\theta) N_{\text{win}} + \log(1 - \theta) N_{\text{loss}} \end{aligned} \]
3.5 Deriving Maximum Likelihood Estimate
With the log-likelihood, we are ready to derive an expression for the maximum likelihood estimate. To find the value of \(\theta\) that maximizes the log-likelihood \(\ell(\theta)\), we need to take two steps. First, take the derivative of \(\ell(\theta)\) with respect to \(\theta\). \[ \begin{aligned} & \dfrac{\partial \, \ell(\theta)}{\partial \, \theta} \end{aligned} \] Second, set the derivative to \(0\) and solve for \(\theta\). \[ \begin{aligned} & \dfrac{\partial \, \ell(\theta)}{\partial \, \theta} = 0 \;\Rightarrow\; \hat{\theta}_{\text{MLE}} = \, ? \end{aligned} \]
We leave these two steps as exercises for you below.
Question: Starting from the log-likelihood \[ \begin{aligned} & \ell(\theta) = \log(\theta) N_{\text{win}} + \log(1 - \theta) N_{\text{loss}}, \end{aligned} \] show that its derivative with respect to \(\theta\) is: \[ \begin{aligned} & \frac{\partial \ell}{\partial \theta} = \frac{N_{\text{win}}}{\theta} - \frac{N_{\text{loss}}}{1 - \theta} \end{aligned} \]
Answer:
\[ \begin{aligned} \frac{\partial \ell}{\partial \theta} & = N_{\text{win}} \frac{\partial}{\partial \theta} \log(\theta) + N_{\text{loss}} \frac{\partial}{\partial \theta} \log(1 - \theta) \\[0.5em] & = N_{\text{win}} \cdot \frac{1}{\theta} + N_{\text{loss}} \cdot \frac{-1}{1 - \theta} \\[0.5em] & = \frac{N_{\text{win}}}{\theta} - \frac{N_{\text{loss}}}{1 - \theta} \end{aligned} \]
Question: Set the derivative of the log-likelihood to \(0\) and solve for \(\theta\). Show that \[ \begin{aligned} & \hat{\theta}_{\text{MLE}} = \frac{N_{\text{win}}}{N_{\text{win}} + N_{\text{loss}}} \end{aligned} \]
Answer:
\[ \begin{aligned} \frac{N_{\text{win}}}{\theta} - \frac{N_{\text{loss}}}{1 - \theta} & = 0 \\[0.5em] \frac{N_{\text{win}}}{\theta} & = \frac{N_{\text{loss}}}{1 - \theta} \\[0.5em] N_{\text{win}} (1 - \theta) & = \theta N_{\text{loss}} \\[0.5em] N_{\text{win}} & = \theta (N_{\text{win}} + N_{\text{loss}}) \\[0.5em] \theta & = \frac{N_{\text{win}}}{N_{\text{win}} + N_{\text{loss}}} \end{aligned} \]
Therefore, \(\hat{\theta}_{\text{MLE}}\) is the fraction of games that our team won, which matches the intuition behind our earlier answer.
Change the number of wins and losses in Figure 1 below and note how the shapes of the likelihood and log-likelihood change. Also, note how the MLE is the value that maximizes the likelihood (and equivalently the log-likelihood).
3.6 General Approach for Deriving the MLE
As mentioned earlier, the focus of this section is to develop a general approach for deriving the MLE given a probabilistic model, a dataset, and a parameter to estimate. Setting aside the algebra specific to the Bernoulli distribution, we can summarize the approach in four steps that apply to other distributions as well.
- Derive \(L(\theta)\), the likelihood of data given the parameter(s). \[ \begin{aligned} & L(\theta) = P(\mathcal{D} \,;\, \theta) = \prod_{i=1}^{N} P(x^{(i)} \,;\, \theta) \end{aligned} \]
- Derive \(\ell(\theta)\), the log-likelihood of data given the parameter(s). \[ \begin{aligned} & \ell(\theta) = \log L(\theta) = \sum_{i=1}^{N} \log P(x^{(i)} \,;\, \theta) \end{aligned} \]
- Take the derivative of the log-likelihood w.r.t. the parameter(s). \[ \begin{aligned} & \frac{\partial \, \ell(\theta)}{\partial \, \theta} \end{aligned} \]
- Set the derivative to \(0\) and solve for the parameter(s). \[ \begin{aligned} & \frac{\partial \, \ell(\theta)}{\partial \, \theta} = 0 \;\Rightarrow\; \hat{\theta}_{\text{MLE}} \end{aligned} \]
3.7 Limitations of MLE
The maximum likelihood estimate is intuitive to derive and easy to calculate, but it has a major pitfall. Imagine that our team has played two games and lost both. The maximum likelihood estimate says that the probability of our team winning a game is \(0\%\): \[ \begin{aligned} & \hat{\theta}_{\text{MLE}} = 0 \end{aligned} \] This is an absurd prediction because it asserts that winning a game is impossible.
This example reveals two major problems with MLE. First, MLE can overfit to the data, especially when the data is limited. Two losses are not enough evidence to conclude that our team can never win. Second, MLE only uses the observed data and ignores any prior beliefs. For example, before playing any games, we may believe that our team has a \(70\%\) chance of winning each game based on its performance last season. MLE doesn’t allow us to incorporate this belief into the estimate. In the next section, we will discuss another approach that allows us to incorporate prior beliefs.
4 Maximum-A-Posteriori (MAP) Learning
Maximum a-posteriori (MAP) learning addresses both limitations of MLE by allowing us to incorporate a prior belief about the parameter. Instead of choosing the value of \(\theta\) that maximizes the likelihood, MAP chooses the value of \(\theta\) that maximizes the posterior probability. Before defining the MAP estimate, let’s first understand what the posterior probability is.
4.1 Understanding the Posterior Probability
MAP learning relies on two probability distributions over the parameter \(\theta\), the prior and the posterior.
Definition: The prior \(P(\theta)\) is a probability distribution over the parameter \(\theta\). It represents our belief about \(\theta\) before we observe any data.
Definition: The posterior probability \(P(\theta \mid \mathcal{D})\) is a probability distribution over the parameter \(\theta\). It represents our updated belief about \(\theta\) after we observe the data \(\mathcal{D}\).
The posterior combines the likelihood of the observed data with our prior belief about \(\theta\). With the likelihood, we start by assuming a value of \(\theta\) and ask how well that value explains the observed data. With the posterior, we go in the opposite direction. After observing the data (hence the name), we ask how strongly we should believe a particular value of \(\theta\).
The two quantities answer different questions. The likelihood asks:
If our probability of winning is \(70\%\), how likely are we to observe these outcomes?
The posterior asks:
After observing these outcomes, how credible is the claim that our probability of winning is \(70\%\)?
We compute the posterior from the likelihood and the prior using Bayes’ rule.
Definition: Bayes’ rule expresses the posterior in terms of the likelihood, the prior and the evidence: \[ \begin{aligned} & \underbrace{P(\theta \mid \mathcal{D})}_{\text{posterior}} = \frac { \overbrace{P(\mathcal{D} \mid \theta)}^{\text{likelihood}} \quad \overbrace{P(\theta)}^{\text{prior}} } {\underbrace{P(\mathcal{D})}_{\text{evidence (marginal likelihood)}} } \end{aligned} \]
The posterior distribution represents our updated beliefs about \(\theta\). It is obtained by combining our prior beliefs with the evidence contained in the observed data. As more data is collected, the posterior increasingly reflects the information provided by the data rather than the prior assumptions.
4.2 The MAP Criterion
Now that we understand the idea of a posterior distribution, we can define the MAP estimate.
Definition: The maximum a-posteriori (MAP) estimate of the parameter \(\theta\) is the value of \(\theta\) that maximizes the posterior probability of \(\theta\) given the data: \[ \begin{aligned} & \hat{\theta}_{\text{MAP}} = \arg\max_{\theta \in [0, 1]} P(\theta \mid \mathcal{D}) \end{aligned} \]
Applying Bayes’ rule, we can rewrite the MAP estimate as: \[ \begin{aligned} & \hat{\theta}_{\text{MAP}} = \arg\max_{\theta \in [0, 1]} \frac{P(\mathcal{D} \mid \theta)\,P(\theta)}{P(\mathcal{D})} \end{aligned} \]
Notice that the denominator \(P(\mathcal{D})\) is constant with respect to \(\theta\) (i.e., it doesn’t depend on \(\theta\)), so for the purpose of maximizing over \(\theta\), we can drop it: \[ \begin{aligned} & P(\theta \mid \mathcal{D}) \overbrace{\;\propto\;}^{\text{proportional to}} P(\mathcal{D} \mid \theta)\,P(\theta) \end{aligned} \]
We can therefore calculate \(\hat{\theta}_{\text{MAP}}\) as follows:
\[ \begin{aligned} & \hat{\theta}_{\text{MAP}} = \arg\max_{\theta \in [0, 1]} P(\mathcal{D} \mid \theta)\,P(\theta) \end{aligned} \]
4.3 The Beta Distribution
To compute the MAP estimate, we need to choose a prior distribution \(P(\theta)\), which models our belief about the probability of winning a game, \(\theta\), before we observe any data. The prior should allow us to express statements such as,
How strongly do we believe that the winning probability \(\theta\) is \(0.8\)?
Since \(\theta\) is a probability, the prior must be a distribution over values in \([0, 1]\). It turns out that a good choice for modeling this prior belief is the Beta distribution, defined below.
Definition: A random variable \(\theta \in [0, 1]\) follows a Beta distribution with parameters \(\alpha\) and \(\beta\), which can be any positive real numbers, if its probability density is \[ \begin{aligned} & P(\theta \,;\, \alpha, \beta) \\ & = \frac{\Gamma(\alpha + \beta)}{\Gamma(\alpha)\Gamma(\beta)}\,\theta^{\,\alpha - 1}(1 - \theta)^{\,\beta - 1} \end{aligned} \] where \(\Gamma\) is the gamma function.
We use a semicolon in \(P(\theta \,;\, \alpha, \beta)\) rather than a conditioning bar because \(\alpha\) and \(\beta\) are fixed values that we choose, not random variables.
The leading \(\Gamma\) fraction is a normalizing constant that doesn’t depend on \(\theta\), so we can drop it for the purposes of calculating MAP: \[ \begin{aligned} & P(\theta \,;\, \alpha, \beta) \propto \theta^{\,\alpha - 1}(1 - \theta)^{\,\beta - 1} \end{aligned} \] The remaining term determines the shape of the distribution, and it looks very similar to our Bernoulli likelihood.
The Beta distribution is a convenient choice for two reasons. First, by changing the values of \(\alpha\) and \(\beta\), we can model a wide range of prior beliefs. Second, as we will see later, combining a Beta prior with the Bernoulli likelihood gives a posterior that is also a Beta distribution, which makes the math much simpler.
It is worthwhile to pause and understand how \(\alpha\) and \(\beta\) affect the shape of the Beta distribution. When \(\alpha = \beta\), the distribution is symmetric and centered at \(0.5\). In particular, when \(\alpha = \beta = 1\), we get the uniform distribution. When \(\alpha \neq \beta\), the distribution is skewed toward the larger parameter. Increasing \(\alpha\) shifts the distribution toward \(1\), and increasing \(\beta\) shifts it toward \(0\). Finally, as \(\alpha + \beta\) becomes larger, the distribution has a higher peak, meaning that it concentrates more of its density around a single value.
After deriving the MAP estimate, we will see that \(\alpha\) and \(\beta\) can be interpreted as pseudo-counts. We pretend to have observed \(\alpha - 1\) wins and \(\beta - 1\) losses before collecting any real data.
Use Figure 2 below to explore how the shape of the Beta distribution changes based on the values of \(\alpha\) and \(\beta\). Here are some examples to try:
- \(\alpha = 1, \; \beta = 1\): Uniform (no preference).
- \(\alpha = 2, \; \beta = 2\): A belief that our team is as likely to win as to lose.
- \(\alpha = 20, \; \beta = 20\): A strong belief that our team is as likely to win as to lose. Notice that the distribution has a higher peak.
- \(\alpha = 20, \; \beta = 1\): A strong belief that our team is likely to win.
- \(\alpha = 1, \; \beta = 20\): A strong belief that our team is likely to lose.
4.4 Computing the Posterior (Beta Meets Bernoulli)
Using our Beta prior, let’s derive an expression for the posterior probability.
Recall that our Beta prior without the constant term is given below: \[ \begin{aligned} & P(\theta) \propto \theta^{\,\alpha - 1}(1 - \theta)^{\,\beta - 1} \end{aligned} \]
To combine the prior with the likelihood, it helps to write the likelihood in a similar compact form, in terms of the number of wins and losses. Try deriving this form yourself in the exercise below.
Question: Show that the likelihood can be written as \[ \begin{aligned} & P(\mathcal{D} \mid \theta) = \theta^{N_{\text{win}}} (1 - \theta)^{N_{\text{loss}}} \end{aligned} \]
Answer:
\[ \begin{aligned} P(\mathcal{D} \mid \theta) & = \prod_{i=1}^{N} \theta^{x^{(i)}} (1 - \theta)^{1 - x^{(i)}} \\[0.5em] & = \theta^{\sum_{i=1}^{N} x^{(i)}} (1 - \theta)^{\sum_{i=1}^{N} (1 - x^{(i)})} \\[0.5em] & = \theta^{N_{\text{win}}} (1 - \theta)^{N_{\text{loss}}} \end{aligned} \]
We can derive an expression for the posterior probability by using Bayes’ rule: \[ \begin{aligned} P(\theta \mid \mathcal{D}) & \propto P(\mathcal{D} \mid \theta) \, P(\theta) \\[0.5em] & \propto \theta^{N_{\text{win}}} (1 - \theta)^{N_{\text{loss}}} \, \theta^{(\alpha - 1)} (1 - \theta)^{(\beta - 1)} \\[0.5em] & = \theta^{(N_{\text{win}} + \alpha - 1)} (1 - \theta)^{(N_{\text{loss}} + \beta - 1)} \end{aligned} \]
The result is another Beta distribution, now with the following parameters. \[ \begin{aligned} & \alpha + N_{\text{win}} \quad \text{and} \quad \beta + N_{\text{loss}} \end{aligned} \] Because the prior and posterior belong to the same family, the Beta is a conjugate prior for the Bernoulli likelihood.
Definition: A prior is a conjugate prior for a likelihood if the resulting posterior belongs to the same family of distributions as the prior.
Conjugate priors simplify the math because the posterior has a closed form in the same family as the prior, so updating our beliefs just means updating the prior’s parameters. Three well-known examples are the Beta prior for a Bernoulli likelihood, the Gaussian prior for the mean of a Gaussian likelihood with known variance, and the Gamma prior for a Poisson likelihood.
4.5 Deriving the MAP Estimate
With an expression for the posterior probability, we can now derive the MAP estimate \(\hat{\theta}_{\text{MAP}}\):
\[ \begin{aligned} \hat{\theta}_{\text{MAP}} & = \arg\max_{\theta \in [0, 1]} P(\theta \mid \mathcal{D}) \\[0.5em] & = \arg\max_{\theta \in [0, 1]} P(\mathcal{D} \mid \theta)\,P(\theta) \\[0.5em] & = \arg\max_{\theta \in [0, 1]} \; \theta^{(N_{\text{win}} + \alpha - 1)} (1 - \theta)^{(N_{\text{loss}} + \beta - 1)} \end{aligned} \]
Similar to how we derived the MLE, we start by taking the log of the posterior probability. Since the posterior is proportional to the expression above, its log equals the log of this expression plus a constant that does not depend on \(\theta\). Try deriving it yourself in the exercise below.
Question: Show that the log-posterior probability can be written as \[ \begin{aligned} & \log P(\theta \mid \mathcal{D}) \\ & = (N_{\text{win}} + \alpha - 1) \log (\theta) + (N_{\text{loss}} + \beta - 1) \log (1 - \theta) \\ & \qquad + \text{const} \end{aligned} \]
Answer:
\[ \begin{aligned} \log P(\theta \mid \mathcal{D}) & = \log \left[ \theta^{(N_{\text{win}} + \alpha - 1)} (1 - \theta)^{(N_{\text{loss}} + \beta - 1)} \right] + \text{const} \\[0.5em] & = \log \theta^{(N_{\text{win}} + \alpha - 1)} + \log (1 - \theta)^{(N_{\text{loss}} + \beta - 1)} + \text{const} \\[0.5em] & = (N_{\text{win}} + \alpha - 1) \log (\theta) + (N_{\text{loss}} + \beta - 1) \log (1 - \theta) \\ & \qquad + \text{const} \end{aligned} \]
Next, we take the derivative of the log-posterior with respect to \(\theta\), set it to \(0\), and solve for \(\theta\). Try these steps yourself in the exercise below.
Question: Show that the MAP estimate is \[ \begin{aligned} & \hat{\theta}_{\text{MAP}} = \frac{N_{\text{win}} + \alpha - 1}{N_{\text{win}} + N_{\text{loss}} + \alpha + \beta - 2} \end{aligned} \]
Answer:
We first take the derivative of the log-posterior with respect to \(\theta\). The constant term does not depend on \(\theta\), so its derivative is \(0\): \[ \begin{aligned} & \frac{\partial \log P(\theta \mid \mathcal{D})}{\partial \theta} \\ & = \frac{N_{\text{win}} + \alpha - 1}{\theta} - \frac{N_{\text{loss}} + \beta - 1}{1 - \theta} \end{aligned} \]
We then set the derivative to \(0\) and solve for \(\theta\): \[ \begin{aligned} \frac{N_{\text{win}} + \alpha - 1}{\theta} - \frac{N_{\text{loss}} + \beta - 1}{1 - \theta} & = 0 \\[0.5em] \frac{N_{\text{win}} + \alpha - 1}{\theta} & = \frac{N_{\text{loss}} + \beta - 1}{1 - \theta} \\[0.5em] (N_{\text{win}} + \alpha - 1)(1 - \theta) & = \theta (N_{\text{loss}} + \beta - 1) \\[0.5em] N_{\text{win}} + \alpha - 1 & = \theta (N_{\text{win}} + N_{\text{loss}} + \alpha + \beta - 2) \\[0.5em] \theta & = \frac{N_{\text{win}} + \alpha - 1}{N_{\text{win}} + N_{\text{loss}} + \alpha + \beta - 2} \end{aligned} \]
Notice that the MAP estimate adds \(\alpha - 1\) to \(N_{\text{win}}\) and \(\beta - 1\) to \(N_{\text{loss}}\). This is why we can think of \(\alpha\) and \(\beta\) as pseudo-counts. We pretend we saw an extra \(\alpha - 1\) wins and \(\beta - 1\) losses before playing any games. These pseudo-counts nudge the estimate away from the extremes.
Returning to our example of losing two games, with a “the game is roughly winnable” prior such as \(\alpha = \beta = 2\) (i.e., one pseudo-win and one pseudo-loss), our estimate becomes: \[ \begin{aligned} & \hat{\theta}_{\text{MAP}} = \frac{0 + 2 - 1}{0 + 2 + 2 + 2 - 2} = 0.25 \end{aligned} \] This is much more sensible than the MLE of \(0\).
Question: Suppose we pick the uniform distribution over \([0, 1]\) as our prior over \(\theta\). Derive the MAP estimate \(\hat{\theta}_{\text{MAP}}\) under this prior. How does it compare to the MLE?
Answer:
This is equivalent to picking a Beta distribution with \(\alpha = \beta = 1\), i.e., no pseudo-counts.
Based on our above derivation, \(\hat{\theta}_{\text{MAP}}\) is equal to \[ \begin{aligned} & \frac{N_{\text{win}}}{N_{\text{win}} + N_{\text{loss}}} \end{aligned} \] which, unsurprisingly, is the same as our earlier MLE.
4.6 General Approach for Deriving the MAP Estimate
The general approach for deriving the MAP estimate follows the same approach as the MLE. The only difference is that we add the log-prior to the objective and maximize the log-posterior instead of the log-likelihood.
- Write down \(P(\theta \mid \mathcal{D})\), the posterior probability of the parameter(s) given the data, using Bayes’ rule. \[ \begin{aligned} & P(\theta \mid \mathcal{D}) \propto P(\mathcal{D} \mid \theta)\,P(\theta) \end{aligned} \]
- Derive \(\log P(\theta \mid \mathcal{D})\), the log-posterior probability of the parameter(s) given the data. \[ \begin{aligned} & \log P(\theta \mid \mathcal{D}) = \log P(\mathcal{D} \mid \theta) + \log P(\theta) + \text{const} \end{aligned} \]
- Take the derivative of the log-posterior probability w.r.t. the parameter(s). \[ \begin{aligned} & \frac{\partial \log P(\theta \mid \mathcal{D})}{\partial \theta} \end{aligned} \]
- Set the derivative to \(0\) and solve for the parameter(s). \[ \begin{aligned} & \frac{\partial \log P(\theta \mid \mathcal{D})}{\partial \theta} = 0 \;\Rightarrow\; \hat{\theta}_{\text{MAP}} \end{aligned} \]
5 Connections between MLE and MAP
MLE and MAP are not two isolated approaches. In this section, we explore three connections between them.
As we alluded to earlier, MLE is a special case of MAP where the prior is the uniform distribution. A uniform prior assigns the same probability to every value of \(\theta\) in \([0, 1]\), so \(P(\theta)\) is a constant. As a result, maximizing the posterior with a uniform prior is equivalent to maximizing the likelihood. In other words, a uniform prior expresses no preference for any value of \(\theta\), so the estimate is determined by the data alone. We can also see this from our formula for the MAP estimate. The uniform distribution is the Beta distribution with \(\alpha = \beta = 1\), and substituting these values gives \[ \begin{aligned} \hat{\theta}_{\text{MAP}} & = \frac{N_{\text{win}} + 1 - 1}{N_{\text{win}} + N_{\text{loss}} + 1 + 1 - 2} \\[0.5em] & = \frac{N_{\text{win}}}{N_{\text{win}} + N_{\text{loss}}} \\[0.5em] & = \hat{\theta}_{\text{MLE}} \end{aligned} \]
The influence of the prior depends on how much data we have. With little data, the prior has a large effect. In our example of losing two games, MLE overfits and estimates that our team never wins, while the prior pulls the MAP estimate to a more reasonable \(0.25\). As our team plays more games, the pseudo-counts become negligible compared to the observed counts \(N_{\text{win}}\) and \(N_{\text{loss}}\). With a large enough dataset, the data dominates, the posterior becomes nearly identical to the likelihood, and MLE and MAP converge to the same estimate. Try increasing the number of wins and losses in Figure 3 to see this trend.
Why does the prior help when data is limited? We can interpret the prior as a regularizer, similar to the regularization we used to prevent overfitting in linear regression. Maximizing the log-posterior is equivalent to minimizing its negative, which splits into two terms: \[ \begin{aligned} & -\log P(\theta \mid \mathcal{D}) \\ & = \underbrace{-\log P(\mathcal{D} \mid \theta)}_{\text{fit to the data}} \; \underbrace{- \log P(\theta)}_{\text{penalty}} + \text{const} \end{aligned} \] The first term measures how well \(\theta\) explains the data, which is exactly what MLE optimizes. The second term is a penalty that is large for values of \(\theta\) that the prior considers unlikely. For our Beta prior with \(\alpha, \beta > 1\), the penalty grows without bound as \(\theta\) approaches \(0\) or \(1\). This is why the MAP estimate is pulled away from the extremes. The values of \(\alpha\) and \(\beta\) play a role similar to the regularization strength \(\lambda\). The larger they are, the stronger the penalty, and the more data we need before the estimate moves away from the prior.
Table 1 summarizes the comparison between MLE and MAP.
| MLE | MAP | |
|---|---|---|
| Objective | Maximize the likelihood \(P(\mathcal{D} \,;\, \theta)\) | Maximize the posterior \(P(\theta \mid \mathcal{D})\) |
| Incorporates prior beliefs? | No (MAP with a uniform prior) | Yes, through \(P(\theta)\) |
| Estimate \(\hat{\theta}\) | \(\frac{N_{\text{win}}}{N_{\text{win}} + N_{\text{loss}}}\) | \(\frac{N_{\text{win}} + \alpha - 1}{N_{\text{win}} + N_{\text{loss}} + \alpha + \beta - 2}\) |
| Limited data | Can overfit (high variance) | Pulled toward the prior’s peak |
| Large dataset | Same limit as MAP | Prior’s influence vanishes |
6 Summary
In this chapter, we introduced the basics of probabilistic modeling, which puts Fundamental Idea #5 (ML demands a probabilistic lens) into practice. The idea is to assume that the data were generated by a probability distribution with unknown parameters, and then use the observed data to estimate those parameters. Once we have estimated the parameters, we can use the model to make predictions (inference). We discussed two approaches for estimating the parameters.
The maximum likelihood estimate (MLE) chooses the parameters that make the observed data most likely. MLE is intuitive, but it relies only on the data and ignores anything we believed beforehand, so it can overfit when we have little data. For example, after two losses, MLE concludes that our team can never win.
The maximum a-posteriori (MAP) estimate also takes our prior beliefs into account. Using Bayes’ rule, we combined the likelihood of the data with our prior belief about the parameter to get the posterior. MAP chooses the parameter value that maximizes the posterior.
The two methods are closely related. MLE is the special case of MAP with a uniform prior, that is, a prior with no preference for any parameter value. When we have little data, the prior acts as a regularizer that pulls the estimate toward our prior beliefs. As we collect more data, the data outweighs the prior, and the MAP estimate gets closer and closer to the MLE. This reflects Fundamental Idea #2 (ML requires balancing tradeoffs in sources of error). A weak prior can lead to overfitting when data is limited, while a strong prior can lead us to rely too much on beliefs that may be wrong.
Both methods are also examples of Fundamental Idea #1 (learning is optimization). We learn the parameters by maximizing an objective function, either the likelihood or the posterior. Although we used a Bernoulli distribution throughout this chapter, the same steps apply to other distributions, such as the Gaussian distribution. We write down the log-likelihood or the log-posterior, take its derivative, set it to zero, and solve for the parameters.