non-observable while Y is observable. Let y1,..., yr be arandom sample of size T drawn from the marginal distribution P ( Y = y | θ) = ∑ x P ( X = x,Y = y | θ). The MLE of θ is obtained by maximizing the likelihood Π 1 < i < T P ( y i | θ ) as a function of θ .

While m athematical formulation looks alike in both cases, the latter, ML estimation with incomplete data, is far more complicated and direct maximization is practically impossible in many cases.  People therefore looked to indirect approaches to tackle the problem of ML estimation with incomplete data to which the EM algorithm has been a standard solution (Dempster, Laird, & Rubin, 1977; McLachlan & Krishnan, 1997). It is an iterative algorithm applicable to a wide class of parameterized distributions including the multinomial distribution and the normal distribution such that the MLE computation is replaced by the iteration of two easier, more tractable steps. At n-th iteration, it first calculates the value of Q function introduced below using current parameter value θ ( n ) (E-step ) 10 :

$$Q\left(\,\theta\mid\theta^{\{n\,\}}\,\right)\,{\stackrel{\mathrm{def}}{=}}\,\sum_{x}\,P\left(\,x\,\mid y,\theta^{\{n\,\}}\,\right)\ln\,P\left(\,x,\,y\,\mid\theta\,\right).$$
$$(1)$$

Next, it maximizes Q(0 | 0(n) as a function of 0 and updates 0(n) (M-step):

$$\theta^{(n+1)}\,=\,\mathrm{arg\,max}_{\theta}Q\,(\,\theta\,\mid\theta^{(n)}\,).$$
$$\left(2\right)$$

Since the old value θ ( n ) and the updated value θ ( n +1) do not necessarily coincide, the E-steps and M-steps are iterated until convergence, during which the (log) likelihood is assured to increase monotonically (McLachlan & Krishnan, 1997).

Although the EM algorithm merely performs local maximization, it is used in a variety of settings due to its simplicity and relatively good performance. One must notice however that the EM algorithm is just a class name, taking different form depending on distributions and applications. The development of a concrete EM algorithm such as the Baum-Welch agorithm for HMMs (Rabiner, 1989) and the Inside-Outside algorithm for PCFGs (Baker, 1979) requires individual effort for each case.

$$\sum_{x}\,P(\,x\mid y,\theta^{(\,n\,)})\ln\,P(\,x\mid y,\theta\,)-\sum_{x}\,P(\,x\mid y,\theta^{(\,n\,)})\ln\,P(\,x\mid y,\theta^{(\,n\,)})\leq0\,$$
$\text{and}\,\text{hence}\,\text{th}\,\text{at}\,$. 
also need what  $$Q(\theta\mid\theta^{(n)})-Q(\theta^{(n)}\mid\theta^{(n)})$$ $$=\sum_{x}P(x\mid y,\theta^{(n)})\ln\ P(x\mid y,\theta)-\sum_{x}P(x\mid y,\theta^{(n)})\ln\ P(x\mid y,\theta^{(n)})+\ln\ P(y\mid\theta)-\ln\ P(y\mid\theta^{(n)})$$ $$\leq\ln\ P(y\mid\theta)-\ln\ P(y\mid\theta^{(n)}).$$
Consequently, we have  $$Q(\theta\mid\theta^{(n)})\geq Q(\theta^{(n)}\mid\theta^{(n)})\ \Rightarrow\ \ln\ p(\,y\mid\theta)\geq\ln\ p(\,y\mid\theta^{(n)})\ \Rightarrow\ \ p(\,y\mid\theta)\geq\ p(\,y\mid\theta^{(n)}).$$
