In the context of differentiation, I have a question about comparing the complexity for the "summation of logarithms" vs the "logarithm of summations".
To illustrate my question, I will use the example of Gaussian Mixture Models (GMM) and the EM Algorithm.
Part 1 (logarithm of summation): The full likelihood for a Gaussian Mixture Model is given by:
$$ L(\theta; X) = \prod_{i=1}^{N} \sum_{k=1}^{K} \pi_k \mathcal{N}(x_i; \mu_k, \Sigma_k) $$
The logarithm gives the log-likelihood:
$$ \log L(\theta; X) = \sum_{i=1}^{N} \log \left( \sum_{k=1}^{K} \pi_k \mathcal{N}(x_i; \mu_k, \Sigma_k) \right) $$
In the above case, this log-likelihood function is considered as "intractable" (I am not sure why exactly), and computing the derivatives of $log L(\theta; X)$ with respect to multiple $\theta$'s is said to be quite complicated due to the placement of the logarithm term (i.e. logarithm of summation)
Part 2 (summation of logarithms): The EM algorithm, apparently using Jensen's Inequality (I am not sure why exactly), we can show an equivalence between the log-likelihood from Part 1, and a different formulation of the log-likelihood based on latent variables $Z = \{z_1, z_2, ..., z_N\}$ indicating the component from which each observation originated:
$$ \log L_c(\theta; X, Z) = \sum_{i=1}^{N} \sum_{k=1}^{K} I(z_i = k) \left( \log \pi_k + \log \mathcal{N}(x_i; \mu_k, \Sigma_k) \right) = \sum_{i=1}^{N} \log \left( \sum_{k=1}^{K} \pi_k \mathcal{N}(x_i; \mu_k, \Sigma_k) \right) $$
We then compute the expected value of this log-likelihood ( conditional on $Z$). This results in a function $Q(\theta, \theta^{(t)})$, where $\theta^{(t)}$ are the current parameter estimates:
$$ Q(\theta, \theta^{(t)}) = E_{Z|X,\theta^{(t)}}[\log L_c(\theta; X, Z)] $$
Substituting the complete-data log-likelihood:
$$ Q(\theta, \theta^{(t)}) = E_{Z|X,\theta^{(t)}} \left[ \sum_{i=1}^{N} \sum_{k=1}^{K} I(z_i = k) \left( \log \pi_k + \log \mathcal{N}(x_i; \mu_k, \Sigma_k) \right) \right] $$
The expectation of a sum is the sum of the expectations, so we can move the expectation inside the sums:
$$ Q(\theta, \theta^{(t)}) = \sum_{i=1}^{N} \sum_{k=1}^{K} E_{Z|X,\theta^{(t)}}[I(z_i = k)] \left( \log \pi_k + \log \mathcal{N}(x_i; \mu_k, \Sigma_k) \right) $$
Using the fact that $E_{Z|X,\theta^{(t)}}[I(z_i = k)]$ is the posterior probability $w_{ik}$ = $P(z_i = k | x_i; \theta^{(t)})$:
$$ Q(\theta, \theta^{(t)}) = \sum_{i=1}^{N} \sum_{k=1}^{K} w_{ik}^{(t)} \left( \log \pi_k + \log \mathcal{N}(x_i; \mu_k, \Sigma_k) \right) $$
Thus, we can see that original likelihood has been re-written as the summation of logarithms, apparently making it easier to optimize.
My Question: In Part 1 and Part 2, we compared a function with the "summation of logarithms" and a function with the "logarithms of summations"
- $f(x, \theta)$ is a "logarithm of summation" function
$$ f(x, \theta) = \log \left( \sum_{k=1}^{K} h_k(x, \theta) \right) $$
- $g(x, \theta)$ is a "summation of logarithm" function: $$ g(x, \theta) = \sum_{k=1}^{K} \log \left( h_k(x, \theta) \right) $$
Now, I can see why the "summation of logarithm" function can be "slightly" easier to differentiate and optimize. From a chain rule perspective, each component of the "summation of logarithm" function can be individually differentiated and then summed - whereas the "logarithm of summation function", there are additional steps involved in sequentially applying the chain rule when evaluating derivatives.
But it seems to me that with modern computers, applying the chain rule in the "summation of logarithm" function should not be that much more complicated than directly differentiating the "logarithm of summation" function.
Thus, why go through all the extra effort? How exactly does the EM algorithm take an "allegedly intractable function" and make it "less intractable" by repositioning the placement of the summations and logarithms?
Thanks!
