Machine Learning: Trying to understand an example of Expectation Maximization

Question

I'm trying to understand this example in EM:

I have a set of data points $x_1,...,x_n$ that are generated in the following way: First, a number $i$ in the range (0,31) is picked with a probability $p_i$. We then look at $i$'s representation and randomly (uniformly) pick 2 bits to be replaced by 2's. So for example, if $i = 31 = 11111$, I can end up with $x= 22111, x = 11122, x = 12121$ all with equal probability.

What I'm trying to understand exactly how this fits the EM model. Looking at the definition on Wikipedia, I see this: obviously $x_1,...,x_n$ is our data. Our parameter $\theta$ is $p_1,...p_n$. I can't quite see what my latent variable is supposed to be. Also, I can't really see a way to construct a likelihood function from this data.

I'm a little bit confused and would appreciate any help!

Answer 1

Presumably you want to recover the original number. So look at the problem from the opposite viewpoint, and it becomes clear what the 'latent variable' is:

I give you the (corrupted) $x=22111$. (The corrupted version is the data, not the original version!) You know there are four possible original numbers: $(00111, 01111, 10111, 11111)$, that is $(7, 15, 23, 31)$. Each of those has a known probability of originally being selected, $(p_7, p_{15}, p_{23}, p_{31})$, and all of them are equally likely to generate that corrupted number. That means we can recondition and determine their probability by dividing by the sum of those four probabilities.

The latent variable that maximizes the expectation is the one that had highest probability. If $p_7>p_{15}>p_{23}>p_{31}$, we would assume that it's a 7 since that's the possibility that maximizes the total likelihood.

If that seems clear to you, you can extend it by giving $1$s and $0$s different chances of being replaced, so that the 5 choose 2 corruptions of each original number have different probabilities. Then even if $p_7>p_{31}$, it could be the case that $p(7|22111)<p(31|22111)$ because $p(22111|7)<p(00122)$ to a significant enough degree.