# EM algorithm increase after E step?

It might be a silly question, but here it goes. The short version of my question is whether the marginal likelihood calculated after every E steps should be increasing or not.

More details: Using the notation from Wikipedia, say I have $X$ observed data, $Z$ latent data. The likelihood I want to maximize is $P(X|\theta) = E[P(X, Z | \theta)]$.

In the E step I calculate the function $$Q(\theta | \theta^{(t)}) = E_{Z|X, \theta^{(t)}} [\log P(X, Z | \theta)]$$ which I maximize in the M step for $\theta$ to obtain $\theta^{(t+1)}$.

By the theory of the EM algorithm, each value of $\theta^{(t)}$ increases the marginal log-likelihood $\log P(X|\theta)$. What I am wondering is whether the sequence $$Q(\theta^{(t+1)} | \theta^{(t)}) = E_{Z|X, \theta^{(t)}} [\log P(X, Z | \theta^{(t)})]$$ should also be increasing at every $t$. My logic is that the marginal likelihood is very difficult to calculate in my problem, and it would be much easier for me to calculate it during the E step, instead of after the M step.

What I observe is that the parameters of interest seem to converge to some value, and so does the sequence of $Q(\theta^{(t+1)} | \theta^{(t)})$ eventually. However, it is not necessarily increasing.

In the best cases of the EM algorithm, $Q(\theta \vert \theta^t)$ is available in closed form. In the case described by the OP this may not be the case. If $Q$ is not available in closed form did you try Stochastic EM? Stochastic EM (SEM) approximates the expectation with a Monte Carlo sample. The samples are drawn from $\Pr(Z \vert X, \theta^t)$ and
$$\mathbb{E}_{Z \vert X, \theta^t}\left(log(\Pr(Z \vert X, \theta^t))\right)\approx \sum_{i=1}^N\left(log(\Pr(Z_i \vert X, \theta^t))\right).$$
In this case the estimated $Q$ function is then optimized numerically, unless the rare case when a closed form is actually available with this approximation.
Using the SEM your estimated are no-longer guaranteed to be strictly increasing the $Q$ function. The sequence of estimates $\theta^{t+1} \vert \theta^t$ now form a Markov chain and some interesting probabilistic statements can be made about the stochastic evolution of the Markov chain.