What is the motivation for the entropy term in the proof of EM algorithm?

Question

Reading through the proof that EM algorithm monotonically increases the log-likelihood (until it converges), I noticed that the most important ingredient of the proof is the introduction of an entropy term $$ H(q(\cdot |t))=-\sum^{m}_{j=1}q(j|t)\log(q(j|t)) $$

The author described it as 'the entropy of the assignment distribution'. The term seems mathematically very similar to Shannon entropy the author introduced earlier. But still there is no explanation anywhere, and this term seems to be jumping out of a hat.

Can someone explain where is it coming from? What is the benefit to work with "any set of distributions over the underlying assignments, not necessarily the posterior assignments" instead of just the posterior probability $p^{(l)}(j|t)$? As a reference, this is also the same approach adopted in Elements of statistical learning (page 278), but there is also little motivation other than "expands the domain of the log-likelihood, to facilitate its maximization".

Answer 1

I would not say that the entropy is the most important piece of the proof. I will try to explain where the entropy term comes from in the following.

I will follow the notation used in the reference you provided. The goal of the EM algorithm is to maximize the log-likelihood function $l(D ; \theta)$ on a set of $n$ training examples $D = \{x_1, \dots, x_n\}$. Putting equations $(5)$ and $(6)$ from the reference together, we can write the log-likelihood function as follows: $$ l(D; \theta) = \sum_{i=1}^n \log \left( \sum_{j=1}^m P(j, x_i | \theta_j) \right) $$ Let $q_i(j)$ denote a distribution, specific to training example $x_i$, that has non-zero probability for all values of $j$; so we have that $\forall i, j, q_i(j) > 0$ and $\forall i, \sum_{j=1}^m q_i(j) = 1$. We can divide and multiply each term in the $\log$ by $q_i(j)$ in the previous equation to get the following ($q_i(j) > 0$ is required to avoid division by zero): $$ l(D; \theta) = \sum_{i=1}^n \log \left( \sum_{j=1}^m \frac{q_i(j) P(j, x_i | \theta_j)}{q_i(j)} \right) \tag{1} $$ $\log$ is a concave function and for any set of values $v_1, \dots, v_m$ and any discrete distribution on $m$ values $p(1), \dots, p(m)$ we have: $$ \log \left( \sum_{j=1}^m p(j) v_j \right) \geq \sum_{j=1}^m p(j) \log v_j $$ This follows from Jensen's inequality.

We can use the concavity of the $\log$ function in $(1)$ and write the following inequality for the log-likelihood function: $$ \begin{align} l(D; \theta) \geq & \sum_{i=1}^n \sum_{j=1}^m q_i(j) \log \left( \frac{P(j, x_i | \theta_j)}{q_i(j)} \right) \\ = & \sum_{i=1}^n \sum_{j=1}^m q_i(j) \log \left( P(j, x_i | \theta_j) \right) + H(q_i) \tag{2} \end{align} $$ As I mentioned before, the distributions $q_i$ can be arbitrarily chosen. However, when $q_i(j) = P(j | x_i; \theta)$ then the inequality in $(2)$ becomes an equality.

Answer 2

A bit late to add my contribution. I think there is another (longer) scheme to demonstrate the EM algorithm that uses the KL divergence. What is sure is that the Jensen inequality is also used in that scheme.

The EM algorithm seeks to maximize a lower bound of a likelihood.

Let $Y=(Y_1, ..., Y_n)$ be the set of possible observations. We want to discover hidden or latent variables $X=(X_1, ..., X_n)$. Each $X_i$ is actually associated to an observation $Y_i$, and we suppose here that the hidden variable are drawn from $\{1,...,c\}$.

We introduce $q=(q_1,...,q_n)$ s.t $\forall i \in \{1,...,n\}$, $q_i$ approximates somehow $P(X_i|Y_i, \theta)$. In the following, $P(X_{ij}|Y_i, \theta)$ is equivalent to $P(X_{i}=j|Y_i, \theta)$.

We denote by $\theta$ the hyperparameters of our probabilities.

We would like to maximize the following log-likelihood

\begin{equation} \mathcal{L}(\theta) = \sum\limits_{i=1}^n \text{log}(P(Y_i|\theta)) \end{equation}

However, solving directly on all the unknowns, the problem would be intractable since:

\begin{equation} \mathcal{L}(\theta) = \sum\limits_{i=1}^n \text{log}( \sum\limits_{j=1}^c P(Y_i, X_{ij}|\theta)) \end{equation}

Fortunately, it is possible to show that:

\begin{equation} \mathcal{L}(\theta) \geq \text{LB}(\theta) \end{equation}

With \begin{equation} \text{LB} = \mathcal{H}(q) + \mathcal{E}(Y, X, q, \theta) \end{equation}

• $\mathcal{H}(q)$ is an entropy term that will force the mass distribution of $q$ to spread, so it does not concentrate on a single location

• $\mathcal{E}(Y, X, q, \theta)$ is an energy term that encourages the mass distribution of $P(Y,X|\theta)$ to focus on location where the model puts high probability

I'd say the entropy term could be seen as a regularizer, that encourage solutions that do not overfit.

I'd say introducing the $q_i$ s help separate the unknowns and optimize them alternatively.

I think you can find more here, that is where I found a reliable explanation of those terms.

Expressions of those two terms can be found below.

---

Proof Sketch

We would like to maximize the following log-likelihood

\begin{equation} \mathcal{L}(\theta) = \sum\limits_{i=1}^n \text{log}(P(Y_i|\theta)) \end{equation}

Now let's focus on each term, using the lemma provided at the end, we have:

\begin{equation} \text{log}(P(Y_i|\theta)) =\text{KL}(q_i(X_i) || P(X_i|Y_i, \theta)) + \sum\limits_{j=1}^c q_{i}(X_{ij}) \, \text{log}(\frac{P(Y_i, X_{ij}|\theta)}{q_{i}(X_{ij})}) \end{equation}

Then: \begin{equation} \mathcal{L}(\theta) = \sum\limits_{i=1}^n \text{KL}(q_i || P(X_{i}|Y_i, \theta)) + \sum\limits_{i=1}^n \sum\limits_{j=1}^c q_{i}(X_{ij}) \, \text{log}(\frac{P(Y_i, X_{ij}|\theta)}{q_{i}(X_{ij})}) \end{equation}

Now the KL divergence is always non-negative, due to the Jensen Inequality, so :

\begin{equation} \mathcal{L}(\theta) \geq \sum\limits_{i=1}^n \sum\limits_{j=1}^c q_{i}(X_{ij}) \, \text{log}(\frac{P(Y_i, X_{ij}|\theta)}{q_{i}(X_{ij})}) \end{equation}

We can finally split this lower bound, let us call it LB, in two terms: \begin{equation} \text{LB} = \sum\limits_{i=1}^n \text{H}(q_i) + \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{c} q_i(X_{ij}) \text{log}(P(Y_i, X_{ij}|\theta)) \end{equation}

\begin{equation} \text{LB} = \mathcal{H}(q) + \mathcal{E}(Y, X, q, \theta) \end{equation}

Lemma

Let's show that the following holds:

\begin{equation} \text{log}(p(x)) = \text{KL}(q(z) || p(z|x)) + \mathbb{E}_{q(z)} [\text{log}(p(x,z) - log(q(z))] \end{equation}

with $p$, $q$ all probabilities.

Now let's focus on each term, we have:

\begin{equation} \text{log}(p(x)) = \sum\limits_{z} q(z) \, \text{log}(p(x)) \end{equation}

We next make use of Bayes' rule:

\begin{equation} \text{log}(p(x)) = \sum\limits_{z} q(z) \, \text{log}(\frac{p(x,z)}{p(z|x)}) \end{equation}

We can make use of a little trick:

\begin{equation} \text{log}(p(x)) = \sum\limits_{z} q(z) \, \text{log}(\frac{q(z) \, p(x,z)}{p(z|x) \, q(z)}) \end{equation}

We can separate into two terms: \begin{equation} \text{log}(p(x)) = \sum\limits_{z} q(z) \, \text{log}(\frac{q(z)}{p(z|x)}) + \sum\limits_{z} q(z) \, \text{log}(\frac{p(x,z)}{q(z)}) \end{equation}

We recognize the KL divergence... \begin{equation} \text{log}(p(x)) = \text{KL}(q(z)||p(z|x)) + \mathbb{E}_{q(z)} [\text{log}(p(x,z) - log(q(z))] \end{equation}