# EM-algorithm for categorical hidden variables

I have the following model: Let's say two indepentent weighted six-sided dice $X$ and $Y$ with unknown probabilities (i.e. probability of 1 is unkown etc) and they have not necessarily the same probability distribution.

However, these are hidden variables and we only observed the outcome $S = X + Y$. I now want to use the EM-algorithm to estimate these probabilities, so we gather some outcomes $D = s_{\{1:N \}}$.

The likelihood for one outcome $n$ is given by (here $\theta = \{p_{1,x},\dots,p_{6,x},p_{1,y},\dots,p_{6,y} \})$:

\begin{align*} p(s_n, X_n, Y_n | \theta) &= [\text{Use conditional properties}]\\ &= p(s_n \mid X_n, Y_n, \theta)\,p(X_n\mid\theta) p(Y_n \mid \theta)\\ &= \prod_{\ell=1}^6 \prod_{m=1}^6 [p(X_n = \ell\mid\theta) p(Y_n = m\mid \theta)]^{1(X_n = \ell, Y_n = m) + 1(s_n = \ell + m \mid X_n = \ell, Y_n = m)}\end{align*}

Here $1$ is the indicator function and the log likelihood is:

\begin{align*} L &= \log(p(s_n, X_n, Y_n | \theta)) \\ &= \sum_{\ell=1}^6 \sum_{m=1}^6 \left[ \begin{array}{l}\big[1(X_n = \ell, Y_n = m) + 1(s_n = \ell + m \mid X_n = \ell, Y_n = m)\big]\\ \qquad\times\big[\log(p(X_n = \ell \mid \theta)) + \log(p(Y_n = m\mid\theta))\big] \end{array}\right]\,.\end{align*}

However, now I'm not sure how to proceed, i.e. doing the E and M step. We want to estimate $p(X_n = \ell)$, for $\ell=1,\dots,6$ and $p(Y_n = m)$ for $m=1,\dots,6$.

In the E step, we want to compute

$$Q(\theta, \theta_t) = \sum_{n=1}^N E_{X_n, Y_n \mid s_n, \theta_t} [L] = ?$$

And in the M step we want to compute

$$\theta_{t+1} = \arg\max Q(\theta, \theta_t)\,.$$

Any ideas?

• Mabye should be moved to the math section (mod)? – E.P Dec 10 '16 at 19:35
• See this question and answer. It can be generalized from the bernoulli distribution over coin tosses to multinomial fairly easily. There is a small mistake in my response that "fixes" mixing weights at 1/2. That should be the initial guess and then updated at each iteration. – Nicholas Mancuso Dec 10 '16 at 22:03