Introduction

Expectation Maximization (EM) is a powerful statistical technique used to find maximum likelihood estimates of parameters in probabilistic models with latent variables. One of the classic examples to illustrate the workings of EM is the coin toss problem, where we determine the biases of coins given incomplete data about coin tosses.

Problem Setup

Imagine we have two coins, A and B, with biases $\pi_A$ and $\pi_B$ for heads, respectively. We perform a series of experiments where each experiment involves flipping one of these coins a number of times, but do not know which coin was used for each experiment. The goal of employing the EM algorithm is to estimate the biases $\pi_A$ and $\pi_B$ based on the observed data.

The EM Algorithm

The EM algorithm involves two main steps: Expectation (E-step) and Maximization (M-step). Initially, we start with an arbitrary guess of the parameter values and iterate through the E and M steps until convergence.

E-Step (Expectation)

In this step, we calculate the expected value of the latent variables given the current estimates of the parameters. For each experiment $i$, we calculate the likelihood of the outcomes being generated by each coin. We determine the expected proportion of heads and tails that are contributed to coin A or coin B. Formally, for a given experiment, we compute:

• $P_i$: The probability that experiment $i$ was performed with coin A.

Using Bayes' theorem, $P_i$ can be computed as:

$$P\_i(A | \text{data}) = \frac{L(\text{data} | \pi\_A)}{L(\text{data} | \pi\_A) + L(\text{data} | \pi\_B)}$$

where $L(\text{data} | \pi)$ is the likelihood of the data given the coin bias.

M-Step (Maximization)

Given the expected contributions calculated in the E-step, the M-step updates the parameters so that they maximize the expected log-likelihood. For the coin biases, we update $\pi_A$ and $\pi_B$ as follows:

$$\pi\_A^{\text{new}} = \frac{\sum\_i P\_i \times \text{heads}\_i}{\sum\_i P\_i \times (\text{heads}\_i + \text{tails}\_i)}$$

$$\pi\_B^{\text{new}} = \frac{\sum\_i (1 - P\_i) \times \text{heads}\_i}{\sum\_i (1 - P\_i) \times (\text{heads}\_i + \text{tails}\_i)}$$

where $\text{heads}_i$ and $\text{tails}_i$ are the number of heads and tails in experiment $i$.

An Example

Consider the following observed data from experiments where coins A and B are flipped, but we do not know which coin was used:

Initial Guess

Suppose we initialize with $\pi_A = 0.6$ and $\pi_B = 0.5$.

Iterating EM

First E-step: Calculate $P_i$ for each experiment using the initial guesses.

First M-step: Update $\pi_A$ and $\pi_B$ using the formulae provided.

Repeat these steps iteratively, updating the probabilities and biases until the estimates converge.

Convergence

The EM algorithm guarantees that the likelihood does not decrease with iteration, and it usually converges to a local maximum. In our coin toss problem, convergence means that the estimated biases of the coins stabilize.

Key Considerations

• Initialization: The choice of initial values can affect convergence and may lead to sub-optimal solutions. • Convergence Criteria: Commonly thresholding the improvement in the log-likelihood or changes in parameter estimates. • Global Optima: EM can converge to local optima. Multiple runs with different initializations can help verify solutions.

Summary Table

Conclusion

The EM algorithm is a versatile technique for parameter estimation in models with incomplete data. Its application to the coin toss example provides a clear and insightful introduction to its two-step iterative process. While EM guarantees non-decreasing likelihood, care must be taken with initialization and convergence verification to ensure meaningful results.