# Expectation Maximisation Algorithm: E Step

I was going through the wiki article of this algorithm. I got a hang of it by understanding what is happening in case of Mixture of Gaussian model.(Kind of soft clustering compared to Kmeans)

But, I am stuck in some of the basics of its derivation in E step.

\begin{align*} Q(\theta|\theta^{(t)}) &= \mathbb{E}_{\mathbf{Z}|\mathbf{X};\theta^{(t)}}[\log L(\theta;\mathbf{x},\mathbf{Z})]\\ &= \mathbb{E}_{\mathbf{Z}|\mathbf{X};\theta^{(t)}}[\log \prod_{i=1}^n f({x}_i,{Z}_i;\theta)]\\ &= \mathbb{E}_{\mathbf{Z}|\mathbf{X};\theta^{(t)}}[\sum_{i=1}^n \log f({x}_i,{Z}_i;\theta)]\\ &= \sum_{i=1}^n \mathbb{E}_{\mathbf{Z}|\mathbf{X};\theta^{(t)}}[\log f({x}_i,{Z}_i;\theta)]\\ &= \sum_{i=1}^n \sum_{j=1}^2 \mathbb{P}(Z_i=j|X=x_i,\theta^{(t)}) \log f({x}_i,j;\theta)\end{align*}

How did they jump from step 4 to step 5 in the link above?

I know what Expectation is, but how to interpret what is expectation w.r.t some distribution?

How do you say it, can someone explain?

Thank you!

• I would simply say that the expected value is always dependent on the distribution it is computed over. – Michael Chernick Nov 27 '16 at 14:20

## 3 Answers

The expectation operator $E[f(X,Y,\ldots)]$ takes the expected value of the thing inside the square brackets over the (joint) distribution of that thing. If that thing is discrete, the expectation comes down to taking a sum over all possible values $f(X,Y,\ldots)$ can have, of that value times the probability of that value. So, $$\text{E}[f(X,Y)] = E_{X,Y}[f(X,Y)] = \sum_{i}\sum_{j} f(x_i,y_i)\text{Prob}[X=x_i,Y=y_j]$$ The "default" expansion is to average out over the joint distribution of all random variable mentioned inside the square brackets. However, sometimes it is useful to use another distribution if additional information about $X$ and $Y$ is available. For example, suppose you know that $Y=y$, then you may be interested in the expected value of $f(X,Y)$ conditional on $Y=y$. Several notations exist: \begin{align*} \text{E}_{X|Y=y}[f(X,Y)] & = \text{E}[f(X,Y)|Y=y]\\ & = \sum_{i} f(x_i,y)\text{Prob}[X=x_i|Y=y]\\ & \neq \sum_{i} f(x_i,y)\text{Prob}[X=x_i] = \text{E}[f(X,y)]\\ \end{align*} In these situations where an expectation is taken over a distribution other than the default one (i.e. the joint distribution of all involved random variables), my advice is to always revert back to the probability notation by doing the expansion. Especially if you are in doubt what the $E[\ldots]$ really means.

In your specific case, the fourth line contains the expectation of a loglikelihood where the expectation is taken over the distribution of $\mathbf{Z}$ conditional on $\mathbf{X=\mathbf{x}_i}$ and on the parameter $\theta$ being $\theta^{(t)}$. The latter is not a random variable of course, but it is als something that "modifies" the probability distribution used in the expansion.

Incidently, on the fourth line, it would have been better to write $\text{E}_{Z_i|\mathbf{X};\theta^{(t)}}[\ldots]$ instead of $\text{E}_{\mathbf{Z}|\mathbf{X};\theta^{(t)}}[\ldots]$.

The proper writing of the sequence of equations is \begin{align*} Q(\theta|\theta^{(t)}) &= \mathbb{E}_{\mathbf{Z}|\mathbf{X};\theta^{(t)}}[\log L(\theta;\mathbf{x},\mathbf{Z})]\\ &= \mathbb{E}_{\mathbf{Z}|\mathbf{X};\theta^{(t)}}[\log \prod_{i=1}^n f({x}_i,{Z}_i;\theta)]\\ &= \mathbb{E}_{\mathbf{Z}|\mathbf{X};\theta^{(t)}}[\sum_{i=1}^n \log f({x}_i,{Z}_i;\theta)]\\ &= \sum_{i=1}^n \mathbb{E}_{\mathbf{Z}|\mathbf{X};\theta^{(t)}}[\log f({x}_i,{Z}_i;\theta)]\\ &= \sum_{i=1}^n \sum_{j=1}^2 \mathbb{P}(Z_i=j|X=x_i,\theta^{(t)}) \log f({x}_i,j;\theta)\end{align*} where capital letters like $X_i$ denote random variables and lower case letters like $x_i$ their realisation, and bold font symbols like $\mathbf{X}$ vectors. Hence,

1. in the first row, $\mathbf{x}$ is a vector and a realisation of the random vector $\mathbf{X}$, $\mathbf{Z}$ is a random variable with distribution $\mathbb{P}(\mathbf{Z}=\mathbf{z}|\mathbf{X}=\mathbf{x},\theta^{(t)}))$, conditional on the realisation of $\mathbf{X}$ and parameterised by the value of $\theta$ equal to $\theta^{(t)}$;
2. in the second row, $\mathbf{x}$ is decomposed as $\mathbf{x}=(x_1,ldots,x_n)$ and $\mathbf{Z}$ is decomposed as $\mathbf{Z}=(Z_1,\ldots,Z_n)$ and the joint density of $(\mathbf{X},\mathbf{Z})$ is the product of the densities of the pairs $(X_i,Z_i)$ as they are assumed iid;
3. the third row is a property of the logarithmic function;
4. the fourth row follows by linearity of the expectation, which is now also an expectation in $Z_i$ only, conditional on the realisation of ${X}_i$ and parameterised by the value of $\theta$ equal to $\theta^{(t)}$;
5. the fifth row is obtained by definition of the expectation in probability, which is the sum of the possible values of the variate weighted by its probabilities of occurrence, namely $\mathbb{P}(Z_i=j|X=x_i,\theta^{(t)})$.

The expectation of a distribution isn't really fundamentally different from the expectated value of a variable. Sticking with the variables as they are defined in the example you linked to, you're interested in the likelihood over some vector of parameters $\theta$. The likelihood over this vector depends on the values of certain hidden variables $Z$, as well as some observed data $X$. The problem, which EM tries to solve, is that $\theta$ depends on $Z$, and $Z$ depends on $\theta$. To solve this chicken-and-egg problem, EM does the following:

1. Initialize $\theta$ to some arbitrary value $\theta^{(t)}$
2. Define the probability distribution over possible states of $Z$ given the current parameter setting, i.e. $p(Z|X;\theta^{(t)})$
3. Compute the expectation over the log-likelihood function over $\theta$ under $p(Z|X;\theta^{(t)})$
4. Update $\theta^{(t)}$ to the most likely value under this expectation (the maximization step)
5. Iterate steps 2-4 until conversion

The step you're asking about it step 3, and you can think of this as computing the "average log-likelihood" given all possible states of the hidden variables $Z$. That is, given each possible state of $Z$, you figure out the log-likelihood function over $\theta$, you multiply this log-likelihood function by the probability of $Z$ (given the data and your current setting of $\theta^{(t)}$, and then you sum over all these log-likelihood functions weighted by their probabilities.

So in short, just as you can think of an expected value as the "average value" of a random variable that you get when summing or integrating over a distribution over that variable, you can think of an expectation of a distribution as the "average shape" of that distribution when you sum or integrate over the distributions over other variables that the target distribution depends on.