# Conjectures regarding EM approximations of mixtures of multivariate normal distributions

Consider $$X\in\mathbb{R}^{N\times d}$$ containing data for $$N$$ points in $$d$$ dimensions drawn from a bimodal multivariate normal distribution, where any row $$x$$ of $$X$$ follows the mixed multivariate normal distribution $$X \sim P\big(x|(a_1,\mu_1,\Sigma_1),(a_2,\mu_2,\Sigma_2)\big) = a_1N_1(x|\mu_1,\Sigma_1)+ a_2 N_2(x|\mu_2,\Sigma_2)$$ where $$0\lt a_1,a_2\lt 1, a1+a2=1$$ and $$x,\mu_1,\mu_2\in\mathbb{R}^d$$ and $$\Sigma_1, \Sigma_2 \in \mathbb{R}^{d \times d}.$$ The matrix $$X$$ can be constructed by following the two step process: 1) choose a set of random class assignments $$z=\{z_1,\dots,z_N\}$$ where each $$z_i \in \{1,2\}$$ is assigned at random from a Bernoulli distribution with $$p=a_1$$ indicating the probability of assignment to class 1, and 2) for each $$z_i$$ instantiate the random $$x$$ from the multivariate normal $$N_{z_i}$$.

Conjecture: $$-\sum_{i=1}^N\log P(x_i|z_i,a,\mu,\Sigma) \le -\sum_{i=1}^N\log P(x_i|\hat{z}^{(2)}_i,a,\mu,\Sigma) \le -\sum_{i=1}^N\log P(x_i|\hat{\mu},\hat{\Sigma})$$

where $$a,\mu,\Sigma$$ indicate the list of values for both classes, e.g., $$a=\{a_1,a_2\}$$ and $$\hat{z}^{(2)}$$ is any assignment from a convergent Expectation-Maximization algorithm with $$(2)$$ centers. The upper bound is the one-component multivariate based on the sample mean $$\hat{\mu}$$ and sample covariance $$\hat{\Sigma}$$. In other words, EM establishes an upper bound for the value of the log-likelihood of the initially defined dataset, in which all $$z_i$$ class assignments are specified. Are there any cases when the EM algorithm is better (has lower negative log-likelihood) than the fully-specified case?

Question: Does this conjecture exist as a theorem?

$$BIC (X|z,a,\mu,\Sigma) \le BIC^{(2)} (X|\hat{z}^{(2)},a,\mu,\Sigma) \le BIC^{(k\ne 2)} (X|\hat{z}^{(k\ne2)},a,\mu,\Sigma),$$

where BIC is the Bayesian Information Criterion.

These seems like they might be theorems. (I'll cop to some wishful thinking, here, so I am at risk to being willfully blind to obvious counterexamples.)

• Yes, these parameters are definite and hard-coded in my simulations. My interest is to prove that a convergent EM algorithm can be trusted to be worse than the actual. Perhaps I should say "almost surely worse than the actual." Nov 25, 2020 at 15:52
• Thank you. I will search for some examples of this and will re-strategize appropriately. Nov 25, 2020 at 16:31
• The following Statistical Science paper is of potential help: Wu & Lange (2010) Nov 25, 2020 at 16:55

Some arguments why the inequality $$\sum_{i=1}^N\log P(x_i|z_i,\mu,\Sigma) \ge \sum_{i=1}^N\log P(x_i|\hat{z}_i,\mu,\Sigma) \ge \sum_{i=1}^N\log P(x_i|\hat a,\hat{\mu},\hat{\Sigma})$$ does not always hold:
1. the first term is one realisation of the random variable $$\sum_{i=1}^N\log P(x_i|Z_i,\mu,\Sigma)$$and the expectation of $$P(x_i|Z_i,\mu,\Sigma)$$ in $$Z_i$$ (unconditional on $$X_i$$) is $$P(x_i|a,\mu,\Sigma)$$Hence it is sometimes smaller and sometimes larger than $$\sum_{i=1}^N\log P(x_i|a,\mu,\Sigma)$$
2. the third term$$\sum_{i=1}^N\log P(x_i|\hat{\mu},\hat{\Sigma})$$is the log-likelihood at the MLE (assuming EM has converged to the global mode). Hence $$\sum_{i=1}^N\log P(x_i|\hat{\mu},\hat{\Sigma})\ge\sum_{i=1}^N\log P(x_i|a,{\mu},{\Sigma})$$ even though $$(a,{\mu},{\Sigma})$$ is the true parameter behind the sample of the $$x_i$$'s.
3. the EM algorithm increases the observed likelihood at each iteration, converging to the or a mode of the said likelihood but the computed $$\hat z_i$$'s are expectations, $$\hat z_i = \hat z_i(\hat a,\hat \mu, \hat \Sigma) =\mathbb E[Z_i|X_i,\hat a,\hat \mu, \hat \Sigma]$$ not maximisers of the complete likelihood function. There is thus no argument for the complete likelihood to increase between EM iterations.