<figure><img src="image_1.png" /></figure>

HAL
open science

# An EM Stopping Rule for Avoiding Degeneracy in Gaussian-Based Clustering with Missing Data.

Christophe Biernacki, Vincent Vandewalle

► To cite this version:

Christophe Biernacki, Vincent Vandewalle. An EM Stopping Rule for Avoiding Degeneracy in Gaussian-Based Clustering with Missing Data.. Journée PS-MAASAI 2025, Apr 2025, Nice, France. hal-05423228

HAL Id: hal-05423228

https://inria.hal.science/hal-05423228v1

Submitted on 18 Dec 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /></figure>

# An EM Stopping Rule for Avoiding Degeneracy in Gaussian-based Clustering with Missing Data

C. Biernacki & V. Vandewalle

Séminaire MAASAI ∪ équipe Probabilité et Statistique du LJAD
Mardi 29 avril 2025,

<figure><img src="image_7.png" /></figure>

<figure><img src="image_8.png" /></figure>

<figure><img src="image_9.png" /></figure>

UNIVERSITÉ
CÔTE D'AZUR

<figure><img src="image_10.png" /></figure>
<figure><img src="image_11.png" /></figure>

<figure><img src="image_12.png" /></figure>

<figure><img src="image_13.png" /></figure>

<figure><img src="image_14.png" /></figure>

## Take home message

Missing data change preconceptions in Gaussian mixtures models

* EM has unexpected behaviour concerning degeneracy dynamic

* There is a need to adapt EM to such a pathological behaviour

* We propose an easy solution through a specific EM stopping rule

This topic is in the research agenda of Statisticians since:

The larger the datasets, the more missing data may appear...
<figure><img src="image_15.png" /></figure>

<figure><img src="image_16.png" /></figure>

<figure><img src="image_17.png" /></figure>

<figure><img src="image_18.png" /></figure>

# Outline

1. Introduction

2. Impact of MAR data on the EM algorithm

3. Proposed solution to avoid degeneracy

4. Concluding remarks
Missing data

■ Notations

x = {x_1, ..., x_n} the data, where x_i = (x_{i1}, ..., x_{id}) ∈ Y = R^d (i ∈ {1, ..., n})

O_i ⊆ {1, ..., d} the set of the observed variables from sample i

x^O = {x_1^O, ..., x_n^O} the whole observed data, with x_i^O the observed sample i

M_i the set of the missing variables for sample i

■ **Assumption on the missingness mecanism Missing At Randon (MAR):** the probability that a variable is missing does not depend on its own value given the observed variables.
<figure><img src="image_19.png" /></figure>

<figure><img src="image_20.png" /></figure>

<figure><img src="image_21.png" /></figure>

<figure><img src="image_22.png" /></figure>

Gaussian mixture model

■ Partition (K components): $z = (z_1 | \dots | z_n)' \in \{0, 1\}^{n \times K}$ where

■ $z_i = (z_{i1}, \dots, z_{iK}) \in \{0, 1\}^K$

■ $z_{ik} = 1$ if $x_i$ belongs to component $k$, $z_{ik} = 0$ otherwise

■ Mixture model: $x_1, \dots, x_n$ are i.i.d. from the d-variate Gaussian mixture

$$f(x_i; \theta) = \sum_{k=1}^{K} \pi_k \underbrace{\frac{1}{(2\pi)^{d/2} |\Sigma_k|^{1/2}} \exp\left(-\frac{1}{2}(x_i - \mu_k)' \Sigma_k^{-1} (x_i - \mu_k)\right)}_{\phi(x_i; \mu_k, \Sigma_k)}$$

■ $\pi_k = p(z_{ik} = 1)$

■ $\theta = (\pi_1, \dots, \pi_K, \mu_1, \dots, \mu_K, \Sigma_1, \dots, \Sigma_K)$ is the whole mixture parameter

■ Specific notations for the missing data case

■ $\mu_{ik}^o$ the sub-vector of $\mu_k$ associated to index $O_i$ (the same for $M_i$)

■ $\Sigma_{ik}^{0M}$ the sub-matrix of $\Sigma_k$ associated to row $O_i$ and columns $M_i$ (the same for any other combination)
<figure><img src="image_23.png" /></figure>

<figure><img src="image_24.png" /></figure>

<figure><img src="image_25.png" /></figure>

<figure><img src="image_26.png" /></figure>

EM algorithm without/with missing data

$\theta$ and $\theta^+$ the parameters for two successive steps

■ E step

$$z_{ik}^{+} = P(z_{ik} = 1 | \mathbf{x}_{i}^{O}; \boldsymbol{\theta}) = \frac{\pi_{k} \phi(\mathbf{x}_{i}^{O}; \boldsymbol{\mu}_{k}, \boldsymbol{\Sigma}_{k})}{\sum_{\ell=1}^{K} \pi_{\ell} \phi(\mathbf{x}_{i}^{O}; \boldsymbol{\mu}_{\ell}, \boldsymbol{\Sigma}_{\ell})}$$

$$\mathbf{x}_{ik}^{M+} = E[\mathbf{x}_{i}^{M} | \mathbf{x}_{i}^{O}, z_{ik} = 1; \boldsymbol{\theta}] = \boldsymbol{\mu}_{ik}^{M} + \boldsymbol{\Sigma}_{ik}^{\text{MO}} (\boldsymbol{\Sigma}_{ik}^{\text{OO}})^{-1} (\mathbf{x}_{i}^{O} - \boldsymbol{\mu}_{ik}^{O}).$$

■ M step

$$\pi_k^+ = \frac{1}{n_k^+} \sum_{i=1}^n z_{ik}^+, \quad \mu_k^+ = \frac{1}{n_k^+} \sum_{i=1}^n z_{ik}^+ \mathbf{x}_{ik}^+$$

$$\boldsymbol{\Sigma}_{ik}^{+} = \frac{1}{n_k^+} \sum_{i=1}^{n} z_{ik}^{+} [(\mathbf{x}_{ik}^{+} - \boldsymbol{\mu}_k^{+})(\mathbf{x}_{ik}^{+} - \boldsymbol{\mu}_k^{+})' + \boldsymbol{\Sigma}_{ik}^{+}]$$

where $n_k^+ = \sum_{i=1}^n z_{ik}^+$, $\mathbf{x}_{ik}^+ = (\mathbf{x}_{i}^{O} \quad \mathbf{x}_{i}^{M+})$, $\boldsymbol{\Sigma}_{ik}^+ = (\mathbf{0}^{O} \quad \mathbf{0}^{OM})$, $\boldsymbol{\Sigma}_{ik}^{M+}$ with 0 the $d \times d$ null matrix, and $\boldsymbol{\Sigma}_{ik}^{\text{MO}} (\boldsymbol{\Sigma}_{ik}^{\text{OO}})^{-1} \boldsymbol{\Sigma}_{ik}^{\text{OM}}$.
<figure><img src="image_27.png" /></figure>

<figure><img src="image_28.png" /></figure>

<figure><img src="image_29.png" /></figure>

<figure><img src="image_30.png" /></figure>

# Degeneracy genesis: unbounded likelihood

* The log-likelihood is unbounded, both without/with missing data

$$ \ell(\theta; \mathbf{x}^0) = \log L(\theta; \mathbf{x}^0) = \sum_{i=1}^{n} \log \left( \sum_{k=1}^{K} \pi_k \phi(\mathbf{x}_i^0; \mu_k, \Sigma_k) \right) $$

* Example [Kiefer and Wolfowitz, 1956] [Day, 1969]

$$ \text{particular center } \mu_2 = \mathbf{x}_i^0 \text{ (with } M_i = \emptyset) \Rightarrow \lim_{|\Sigma_2| \to 0} \ell(\theta; \mathbf{x}^0) = +\infty $$

## Our question

The EM degeneracy dynamics is well-known for the complete data case ... but what about the MAR case?
<figure><img src="image_31.png" /></figure>

<figure><img src="image_32.png" /></figure>

<figure><img src="image_33.png" /></figure>

<figure><img src="image_34.png" /></figure>

# Outline

1. Introduction

2. Impact of MAR data on the EM algorithm

3. Proposed solution to avoid degeneracy

4. Concluding remarks
<figure><img src="image_35.png" /></figure>

<figure><img src="image_36.png" /></figure>

<figure><img src="image_37.png" /></figure>

<figure><img src="image_38.png" /></figure>

Reminder on EM without missing data: theoretical results

<figure><img src="image_39.png" /></figure>

$$u_0 = \left[ \frac{1}{p_{i_0 k_0}}, \{p_{i_0 k_0}\}_{i \neq i_0} \right]$$

degeneracy of component $k_0$ at $y_{i_0}$

$$\Leftrightarrow \|u_0\| \to 0$$

[Biernacki and Chrétien, 2003]

[Ingrassia and Rocci, 2009]

Proposition 1: Existence of a bassin of attraction

$\exists \epsilon > 0 \text{ s.t. if } \|u_0\| \le \epsilon \text{ then } \|u_0^+\| = o \|u_0\| \text{ with probability 1.}$

Proposition 2: Speed towards degeneracy is exponential

$\exists \epsilon > 0, \alpha > 0 \text{ and } \beta > 0 \text{ s.t. if } \|u_0\| \le \epsilon \text{ then, with probability 1,}$

$$|\Sigma_{k_0}^+| \le \alpha / |\Sigma_{k_0}| \cdot \exp(-\beta / |\Sigma_{k_0}|).$$
<figure><img src="image_40.png" /></figure>

<figure><img src="image_41.png" /></figure>

<figure><img src="image_42.png" /></figure>

<figure><img src="image_43.png" /></figure>

Reminder on EM without missing data: illustration

<figure><img src="image_44.png" /></figure>

■ degeneracy may occur even when starting from large variances

■ convergence can be slow when far from the degenerate limit

■ convergence extremely fast near degeneracy
<figure><img src="image_45.png" /></figure>

<figure><img src="image_46.png" /></figure>

<figure><img src="image_47.png" /></figure>

<figure><img src="image_48.png" /></figure>

MAR case: EM behaviour illustration

- Breast cancer tissue of the UCI database repository: 106 units, 9 variables.

- 10% of missing data randomly generated

- $K = 4$ clusters

<figure><img src="image_49.png" /><figcaption>Decrease of the log-determinant of the degenerated component</figcaption></figure>

<figure><img src="image_50.png" /></figure>
MAR case: detail from the illustration

<table><caption>Table: Data belonging to the degenerated component.</caption><thead><tr><th></th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th></tr></thead><tbody><tr><td>1</td><td>211.00</td><td></td><td>0.09</td><td>30.75</td><td>151.98</td><td>4.94</td><td>14.27</td><td>27.24</td><td>217.13</td></tr><tr><td>2</td><td>196.86</td><td>0.02</td><td>0.09</td><td>28.59</td><td>82.06</td><td>2.87</td><td>7.97</td><td>27.66</td><td>200.75</td></tr><tr><td>3</td><td>144.00</td><td>0.12</td><td>0.05</td><td>19.65</td><td>70.43</td><td>3.58</td><td></td><td>7.57</td><td>160.37</td></tr><tr><td>4</td><td>172.52</td><td>0.13</td><td>0.04</td><td></td><td>192.22</td><td>5.12</td><td>19.32</td><td>32.19</td><td>174.93</td></tr><tr><td>5</td><td>121.00</td><td>0.17</td><td>0.09</td><td>24.44</td><td>144.47</td><td>5.91</td><td>22.02</td><td>10.59</td><td>141.77</td></tr><tr><td>6</td><td>223.00</td><td>0.12</td><td>0.08</td><td>33.10</td><td>197.01</td><td>5.95</td><td>30.45</td><td>12.96</td><td>252.48</td></tr><tr><td>7</td><td></td><td>0.17</td><td>0.23</td><td>34.22</td><td>94.35</td><td>2.76</td><td>31.28</td><td>13.88</td><td>180.61</td></tr><tr><td>8</td><td>303.00</td><td>0.06</td><td>0.04</td><td>22.57</td><td></td><td>4.54</td><td>21.83</td><td>5.72</td><td>321.65</td></tr><tr><td>9</td><td>250.00</td><td>0.09</td><td>0.09</td><td>29.64</td><td>180.76</td><td>6.10</td><td>26.14</td><td>13.96</td><td>280.12</td></tr><tr><td>10</td><td>391.00</td><td>0.06</td><td>0.01</td><td>35.78</td><td></td><td>7.41</td><td>22.13</td><td>28.11</td><td>400.99</td></tr><tr><td>11</td><td>176.00</td><td>0.09</td><td>0.08</td><td>20.59</td><td>79.71</td><td></td><td>18.23</td><td>9.58</td><td>191.99</td></tr><tr><td>12</td><td>145.00</td><td></td><td>0.11</td><td>21.22</td><td>82.46</td><td>3.89</td><td>20.30</td><td>6.17</td><td>162.51</td></tr><tr><td>13</td><td>124.13</td><td>0.13</td><td>0.11</td><td>20.59</td><td></td><td></td><td>18.46</td><td>9.12</td><td>134.89</td></tr><tr><td>14</td><td>103.00</td><td>0.16</td><td>0.29</td><td>23.75</td><td>78.26</td><td>3.29</td><td>22.32</td><td>8.12</td><td>124.98</td></tr></tbody></table>

- Cvg. towards a degenerated component (no plateau of the log-likelihood)

- Degeneracy relatively slow: log-likelihood linear according to the nb of it.

- Number of points of the degenerated solution greater than the space dimension d (but the number of complete points lower than d)
<figure><img src="image_51.png" /></figure>

<figure><img src="image_52.png" /></figure>

<figure><img src="image_53.png" /></figure>

<figure><img src="image_54.png" /></figure>

MAR case: understanding degeneracy speed on a toy example

■ Univariate framework, no mixture, only one observed data: $x$

■ Maximum likelihood estimator (Unbounded likelihood!): $\mu = x$, $\sigma^2 = 0$

■ Suppose equivalently that $n-1$ data are unobserved (unchanged likelihood)

■ Here is one iteration of a (useless) EM algorithm (it. $q$)

$$ \mu^{(q+1)} = \frac{(n-1)\mu^{(q)} + x}{n} \quad \text{and} \quad \sigma^2(q+1) = \frac{(n-1)\sigma^2(q) + (x - \mu^{(q+1)})^2}{n} $$

Linear grow of the log-likelihood (have a look also when $n$ increases!)

$$ \ell(\theta^{(q)}; x) \sim -0.5q \log \frac{n-1}{n} $$

Geometrical convergence rate towards 0 for the variance

$$ \sigma^2(q) \sim \sigma^2(0) \left( \frac{n-1}{n} \right)^q $$
<figure><img src="image_55.png" /></figure>

<figure><img src="image_56.png" /></figure>

<figure><img src="image_57.png" /></figure>

<figure><img src="image_58.png" /></figure>

MAR case: influence of the missing data rate

<table><caption>Table: Frequency and speed of degeneracy (deg.) according to the rate of missing data on the breast cancer data set.</caption><thead><tr><th>% missing data</th><th>0</th><th>5</th><th>10</th><th>15</th><th>20</th><th>25</th><th>30</th></tr></thead><tbody><tr><th>% deg.</th><td>16</td><td>4</td><td>12</td><td>11</td><td>46</td><td>51</td><td>100</td></tr><tr><th>Average nb of iterations before deg.</th><td>2</td><td>13</td><td>13</td><td>82</td><td>304</td><td>138</td><td>215</td></tr></tbody></table>

When the rate of missing data increases:

- The rate of degeneracy increases

- The number of iterations before degeneracy seems to (globally) increase

It corresponds to a dangerous EM behaviour...

... since missing data are more and more frequent
<figure><img src="image_59.png" /></figure>

<figure><img src="image_60.png" /></figure>

<figure><img src="image_61.png" /></figure>

<figure><img src="image_62.png" /></figure>

Intermediate conclusion on the MAR case

Like the complete data x case

■ Likelihood is unbounded

■ EM can be attracted by degenerate solutions

Unlike the complete data x case

■ Risk to consider a degenerated solution as valid

■ Risk of losing a lot of time in useless iterations

Statisticians should be aware of such dangerous EM behaviour...

How to avoid it?
<figure><img src="image_63.png" /></figure>

<figure><img src="image_64.png" /></figure>

<figure><img src="image_65.png" /></figure>

<figure><img src="image_66.png" /></figure>

# Outline

1. Introduction

2. Impact of MAR data on the EM algorithm

3. Proposed solution to avoid degeneracy

4. Concluding remarks
<figure><img src="image_67.png" /></figure>

<figure><img src="image_68.png" /></figure>

<figure><img src="image_69.png" /></figure>

<figure><img src="image_70.png" /></figure>

Existing strategies for avoiding degeneracy<fnref n="1" />

* Constraining the covariance matrices (e.g. num. tol.):

$$ \forall k, |\Sigma_k| \ge \alpha(n) > 0 $$

[Tanaka and Takemura, 2006]

* Relative constraints between covariance matrices:

$$ \forall k \neq j, |\Sigma_k| \ge \beta |\Sigma_j| \quad (0 < \beta \le 1) $$

[Hathaway, 1985] [Ingrassia and Rocci, 2007]

* Bayesian approach: with a well-behaved prior $\gamma$, maximise

$$ \ln L(\theta; x) + \ln \gamma(\theta) $$

[Snoussi and Mahammad-Djafari, 2001] [Ciuperca et al., 2003]

Common difficulty

Additional information $\alpha$, $\beta$ or $\gamma$ is difficult to fix.

<footnote n="1">¹Remark: recently [Ranalli et al., 2020] proposed a (bounded) marginal likelihood estimating sequentially the variances and then the centers. However, we lose some Fisherian information and it is hardly implemented in the multivariate Gaussian case and for more than two components.</footnote>
<figure><img src="image_71.png" /></figure>

<figure><img src="image_72.png" /></figure>

<figure><img src="image_73.png" /></figure>

<figure><img src="image_74.png" /></figure>

Minimal partition information for avoiding degeneracy<fnref n="3" />

Key idea: transpose some natural constraints from the supervised case

Enough data should be available in each class to perform the parameter estimation
(an obvious requirement to obtain non-singular covariance matrices)

■ Complete data case [Policello, 1981]<fnref n="2" />:

■ $n_k = \sum_{i=1}^{n} z_{ik}$: the number of individuals in component $k$

■ $\mathcal{Z}^* = \{z: \forall k, n_k \ge d+1\}$: the set of partitions with at least $d+1$ elements by class

■ Result: $\ell(\theta; x|\mathcal{Z}^*)$ is bounded and leads to consistent mixture estimates

■ Extension to the missing data case:

■ $n_k^o = \sum_{i=0; i \le d} z_{ik}$: number of complete individuals in component $k$

■ $\mathcal{Z}^* = \{z: \forall k, n_k^o \ge d+1\}$: partitions with at least of $d+1$ complete individuals in $k$

Proposition

For $\mathcal{Z}^* = \{z: \forall k, n_k^o \ge d+1\}$ then $p(L(\theta; x^o, \mathcal{Z}^*) < \infty) = 1$

<footnote n="2">²In fact, [Policello, 1981] maximized the conditional likelihood $L(\theta; x|\mathcal{Z}^*)$ but joint and conditional likelihood are similar since $L(\theta; x, \mathcal{Z}^*) = L(\theta; x|\mathcal{Z}^*)p(\mathcal{Z}^*)$ and $p(\mathcal{Z}^*) \simeq 1$ even for moderate values of $n$. The joint likelihood is also more tractable from the computational point of view in the M step of EM.</footnote>

<footnote n="3">³Such an information has also to be used by [Biernacki and Castellan, 2014] for defining a probabilistic lower bound of the likelihood.</footnote>
<figure><img src="image_75.png" /></figure>

<figure><img src="image_76.png" /></figure>

<figure><img src="image_77.png" /></figure>

<figure><img src="image_78.png" /></figure>

Illustrating the effect of $\mathcal{Z}^*$ on the log-likelihood

A meaningful decomposition of the likelihood

$$ \ell(\boldsymbol{\theta}; \mathbf{x}^0) = \underbrace{\ell(\boldsymbol{\theta}; \mathbf{x}^0, \mathcal{Z}^*)}_{< \infty \text{ with proba. 1}} + \underbrace{\ell(\boldsymbol{\theta}; \mathbf{x}^0, \bar{\mathcal{Z}}^*)}_{\text{can degenerate}} $$

<figure><img src="image_79.png" /></figure>
A specific EM algorithm: EM*

■ E step: $t_{ik}^{*+} \propto \tau_{ik} t_{ik}^{+}$ with $\tau_{ik} = p(Z^*|X^o, z_{ik} = 1; \theta)$ and $t_{ik}^{+} = p(z_{ik} = 1|X^o; \theta)$

■ M step: standard formulas of EM where $t_{ik}^{+}$ is replaced by $t_{ik}^{*+}$

Detail of E step for $K = 2$

$$p(Z^*|\mathbf{X}, z_{1:K} = 1; \boldsymbol{\theta}) = 1 - \left( \prod_{j \neq i} t_{j2} + \prod_{j \neq i} t_{j1} + \sum_{j \neq 1} t_{j2} \prod_{h \neq 1, j} t_{h1} \right)$$

Combinatorial problem for $K > 2$ (Bell number involved)

Calculus of E step becomes infeasible for most situations...
<figure><img src="image_80.png" /></figure>

<figure><img src="image_81.png" /></figure>

<figure><img src="image_82.png" /></figure>

<figure><img src="image_83.png" /></figure>

EM vs. EM*: illustration

<figure><img src="image_84.png" /></figure>

Standard EM

Specific EM*
<figure><img src="image_85.png" /></figure>

<figure><img src="image_86.png" /></figure>

<figure><img src="image_87.png" /></figure>

<figure><img src="image_88.png" /></figure>

EM vs. EM*: example

$$\pi_1 = \pi_2 = 0.5$$

$$x_i | z_{i1} = 1 \sim N \left( \begin{pmatrix} 0 \\ 0 \end{pmatrix} ; \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \right)$$

$$x_i | z_{i2} = 1 \sim N \left( \begin{pmatrix} 2 \\ 2 \end{pmatrix} ; \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \right)$$

n = 30 data, p = 80% of missing data.

Results on 100 simulations, 300 iterations, 10 starting values.

<table><caption>Log-likelihood according to the number of iterations and the algorithm</caption><thead><tr><td>Algorithm</td><td>Adjusted Rand Index</td></tr></thead><tbody><tr><td>EM</td><td>0.171 (0.015)</td></tr><tr><td>EM*</td><td>0.200 (0.015)</td></tr></tbody></table>

<figure><img src="image_89.png" /></figure>
<figure><img src="image_90.png" /></figure>

<figure><img src="image_91.png" /></figure>

<figure><img src="image_92.png" /></figure>

<figure><img src="image_93.png" /></figure>

A simpler solution: an early EM stopping rule relying on $\mathcal{Z}^*$

* $\tau_{ik}$ is the pivotal quantity involved in our strategy

* The combinatorial problem only comes from the computation of $\tau_{ik}$

* Mostly $\tau_{ik} \approx 1$, except in some limited iterations close to degeneracy

Far from degeneracy

EM* = EM for most of iterations and computing $\tau_{ik}$ is mostly usefulness ($\tau_{ik} \approx 1$)

Close to degeneracy

$\tau_{ik} \approx 0$ for at least one value of the couple $(i, k)$, thus EM* $\neq$ EM, except if simultaneously the value of $t_{ik}^{+}$ is such that $t_{ik}^{+} \approx 0$
<figure><img src="image_94.png" /></figure>

<figure><img src="image_95.png" /></figure>

<figure><img src="image_96.png" /></figure>

<figure><img src="image_97.png" /></figure>

# A simpler solution: an early EM stopping rule relying on $\mathbb{Z}^*(\text{cont'd})$

## A 1st EM stopping rule strategy

1. Replace the calculus of each $\tau_{ik}$ by the (very simple) sampling of a partition value $z_{ik}$ drawn from $p(\mathbf{z}|\mathbf{x}^o, z_{ik} = 1; \theta)$

2. EM is stopped and then restarted as soon as $z_{ik} \notin \mathbb{Z}^*$ for at least one couple $(i, k)$, where $b_f z_{ik}$ is drawn from $p(\mathbf{z}|\mathbf{x}^o, z_{ik} = 1; \theta)$

However, this 1st strategy is expected to be too stringent since it could stop some runs where $t_{ik}^+ \simeq 0$ for some $(i, k)$ values, situation where $\tau_{ik} t_{ik}^+ \simeq t_{ik}^+$ even if $\tau_{ik} \simeq 0$.

## A 2nd (and final) EM stopping rule strategy

The principle is to consider the product $\tau_{ik} t_{ik}^+$ as a whole, instead of $\tau_{ik}$ individually.

1. Draw a value $z_{ik}$ from $t_{ik}^+$, for each $(i, k)$ (thus a full partition $\mathbf{z}$ from $p(\mathbf{z}|\mathbf{x}^o; \theta)$)

2. Only for each $(i, k)$ s.t. $z_{ik} = 1$, perform the 1st strategy previously described

This 2nd strategy is equivalent to the very simple procedure consisting finally to draw a $\mathbf{z}$ value from $p(\mathbf{z}|\mathbf{x}^o; \theta)$ and then to check if $\mathbf{z} \in \mathbb{Z}^*(\text{EM is not stopped})$ or $\mathbf{z} \notin \mathbb{Z}^*(\text{EM is stopped and re-run from another starting value})$.
<figure><img src="image_98.png" /></figure>

<figure><img src="image_99.png" /></figure>

<figure><img src="image_100.png" /></figure>

<figure><img src="image_101.png" /></figure>

Numerical experiments

■ 100 data sets generated from a 9-variate ($d = 9$) Gaussian mixture with $K = 2$

■ $\pi_1 = \pi_2 = 0.5$, $\Sigma_k$ are the identity, $\mu_1 = (0, 0, ..., 0)'$ and $\mu_2 = (6/\sqrt{d}, ..., 6/\sqrt{d})'$

■ $n = 150$ and the probability for a data-cell to be missing equals to 0.2

■ For each dataset, each algorithm is initialized once, with the same initialization for all the algorithms, and a total of 100 iterations

<table><caption>Table: Average ARI for EM and EM* (the frequency of each case is also given).</caption><thead><tr><th>Stopping rule (frequency)</th><th>EM</th><th>EM*</th></tr></thead><tbody><tr><td>Not activated (94)</td><td>0.909</td><td>0.915</td></tr><tr><td>Activated without EM degeneracy (5)</td><td>0.074</td><td>0.340</td></tr><tr><td>Activated with EM degeneracy (1)</td><td>-</td><td>0.604</td></tr></tbody></table>

■ When the stopping rule is not activated, EM and EM* give very close ARI values

■ When the stopping rule is activated, it appears to be justified either due to a degenerate run, or due to a poor partitioning output value run

■ These latter runs should possibly correspond to a degenerate run, but it is difficult to know since degeneracy could be quite very slow with missing data
<figure><img src="image_102.png" /></figure>

<figure><img src="image_103.png" /></figure>

<figure><img src="image_104.png" /></figure>

<figure><img src="image_105.png" /></figure>

# Outline

1. Introduction

2. Impact of MAR data on the EM algorithm

3. Proposed solution to avoid degeneracy

4. Concluding remarks
<figure><img src="image_106.png" /></figure>

<figure><img src="image_107.png" /></figure>

<figure><img src="image_108.png" /></figure>

<figure><img src="image_109.png" /></figure>

Conclusion

■ Unexpected degeneracy behaviour of the EM dynamics in case of missing data

■ Add information of a minimum number of complete data in each component<fnref n="4" />

■ It leads to a usually unfeasible EM algorithm (EM*)

■ We reformulate it as a classical EM with a specific stopping rule

■ First numerical experiments are encouraging but need to be confirmed

Great advantage of Strategy 2

Use a classical EM algorithm with an extremely simple stopping rule...

<footnote n="4">⁴If such information if unlikely true, i.e. P($\mathbb{Z}^*$) is too low, the proposed rule will automatically stop EM.</footnote>
<figure><img src="image_110.png" /></figure>

<figure><img src="image_111.png" /></figure>

<figure><img src="image_112.png" /></figure>

<figure><img src="image_113.png" /></figure>

Thanks!