0
$\begingroup$

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?

Additional conjecture:

$$ 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.)

$\endgroup$
3
  • $\begingroup$ 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." $\endgroup$ – Peter Leopold Nov 25 '20 at 15:52
  • 1
    $\begingroup$ Thank you. I will search for some examples of this and will re-strategize appropriately. $\endgroup$ – Peter Leopold Nov 25 '20 at 16:31
  • $\begingroup$ The following Statistical Science paper is of potential help: Wu & Lange (2010) $\endgroup$ – Xi'an Nov 25 '20 at 16:55
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.