Expectation Maximization (EM) is a powerful statistical technique used for finding maximum likelihood estimates when dealing with incomplete data or when the model depends on latent variables. One of the most illustrative examples of applying the EM algorithm is solving the problem of estimating the bias of a coin when the outcome is partially hidden. The coin toss model provides an excellent introduction to understanding the nuances and applications of the EM algorithm.

Basics of Expectation Maximization

The EM algorithm consists of two main steps, which are iteratively applied:

1. Expectation Step (E-Step): This step involves calculating the expected value of the latent variables, given the observed data and current estimate of the parameters.
2. Maximization Step (M-Step): This step updates the parameter estimates by maximizing the expected log-likelihood found in the E-step.

EM iteratively applies these two steps to converge to a local maximum of the likelihood function.

Coin Toss Experiment

Setup

Consider an experiment with two coins, $A$ and $B$, each with unknown biases $\theta_A$ and $\theta_B$. We have a batch of experiments where:

• For each experiment, a coin is chosen at random with hidden probability. • The chosen coin is tossed a fixed number of times, say 10. • You observe only the total number of heads from the toss, but not the specific coin used.

The goal is to estimate $\theta_A$ and $\theta_B$, the probability of heads for each coin, using the EM algorithm.

Technical Explanation

1. Initialization: • Choose initial guesses for $\theta_A$ and $\theta_B$, say $\theta_A^{(0)} = 0.6$ and $\theta_B^{(0)} = 0.5$.
2. E-Step: • For each observation (number of heads), compute the probability that coin $A$ was used and the probability that coin $B$ was used, given the observed number of heads. • This involves using Bayes' theorem to update our knowledge about which coin might have been picked, incorporating the current estimates of the coin biases.
3. M-Step: • With the probabilities from the E-step, update the estimates of $\theta_A$ and $\theta_B$. For instance, if the probability that coin $A$ was used in an experiment is $p_A$, and the experiment resulted in $h$ heads out of 10 tosses, the updated formula for $\theta_A$ might look like: $$\theta_A^{(t+1)} = \frac{\sum p_A \cdot h}{10 \sum p_A}$$ • Similar update is conducted for $\theta_B$.
4. Convergence: • Repeat the E-step and M-step until convergence, i.e., changes in $\theta_A$ and $\theta_B$ between iterations fall below a threshold.

Numerical Example

Consider data from 3 experiments with the following observed total heads:

Initialization:

• $\theta_A^{(0)} = 0.6$ • $\theta_B^{(0)} = 0.5$

E-Step (iteration 1):

Calculate the probability that each experiment used coin $A$ based on initial guesses.

M-Step (iteration 1):

Calculate new estimates for $\theta_A$ and $\theta_B$ using probabilities from the E-step.

The above table illustrates the iterative update process where $\theta_A$ and $\theta_B$ converge to values that maximize the log-likelihood.

Applications and Importance

The coin toss example exemplifies the broader application of EM in various fields, such as:

• Data Clustering: Discovering clusters in the data when the membership of data points is unknown. • Missing Data Problems: Estimating parameters where some data points are missing during a survey or experiment. • Gene Expression Analysis: Identifying gene patterns where the expression states are partially hidden or obscured.

The EM algorithm's ability to handle incomplete datasets makes it a crucial tool for statistical analysis, providing robust estimates in many practical situations.