Efficience of Expectation-Maximization algorithm in function of learning dataset size

I have datasets of increasing sizes identically distributed. I have tried to fit a gaussian mixture to these datasets using Expectation-Maximization algorithm.

To check the quality of this fit, I have run goodness of fit tests between the density of the known points and the estimated density. It provides very good results. Tests hypothesis are accepted in more than 90% of the cases.

The acceptation rate first increases with the number of points in the learning dataset (as I was expected). And then for the last dataset size, the acceptation rate falls from 95% to about 85%... I have run tests many times and it is always the same...

Do you have some hints about what is going on ? Why would the quality of the model be so low (compared to other sizes) for one particular learning dataset size ?... Do you know articles where the behavior of Expectation-Maximization is studied in function of the sample size ?

EDIT : As I can simulate as many datasets as I want. I do not use cross-validation. To test the quality of the density estimated with a dataset $A$, I run the goodness-fo-fit tests between a test dataset $B$, simulated in the same way that dataset $A$ and a sample of points simulated from the estimated gaussian mixture. The size of the dataset $B$ is constant through my tests and thus does not depend on the size of dataset $A$.

• I'm not sure what an "adequation test" is. It's not a term I've heard before, and a google search almost solely returns results written in french. Is it the same as a peason's chi-squared test?
– Pat
Mar 5, 2014 at 9:25
• Sorry... I've edited my question. I'm talkin about goodness of fit tests, like Kolmogorov Smirnov or Cramér-Von Mises ones
– Pop
Mar 5, 2014 at 9:31

A few guesses why this may be happening:

If you're fitting a gaussian mixture model you must have some term in there to prevent components latching onto a datapoint and collapsing down to zero variance. Depending on what form this takes, its behaviour may change as the sample size grows.

• Your tests are becoming more powerful

For example, the accept/reject decision in a kolmogorov-smirnov test depends on $\sqrt{n}$ where $n$ is the sample size. As $n$ grows, differences between your model and the actual distribution which were hidden by the noise in the signal before may be becoming detectable.

• Computational issues

For example, maybe you're getting precision errors adding small values to large ones that didn't show up on smaller datasets (as with fewer samples the difference between the two was not so great). I think is is pretty unlikley though, unless your dataset size change is huge.

• There is something different about the last dataset.

Depending on how you've generated these datasets, this may be prety easily ruled out.

Something you don't mention - are you cross validating? If so, does that show a drop in likelihood on the holdout set at large sample sizes too?

• Thank you for your long answer. I've not been very specific in my question but I will edit.
– Pop
Mar 5, 2014 at 10:03
• I think I do not well understand your first point. I do not think there is any regularization term in EM algorithm. Furthermore I launch the algorithm with multiple initialization points and take the result with the best likelihood. As shown in my edit, your second point does not apply here because the sizer of the sample tests in constant. For you third point, I think it is unlikely to caused by precision errors but I can investigate it. Finally, the datasets are all created in the same and do not look very different...
– Pop
Mar 5, 2014 at 10:15
• Okay, your edit has ruled out quite a lot of what I suggested. Progress! :) "I do not think there is any regularization term in EM algorithm. Furthermore I launch the algorithm with multiple initialization points and take the result with the best likelihood." Hmm. Gaussian mixture models fit using pure maximum likelihood are prone to overfitting. Using multiple initialisations and selecting the mixture model with the highest likelihood, unless evaluated on a holdout set, will not fix this - and may make it worse! I don't see why this would only affect the largest dataset, though...
– Pat
Mar 5, 2014 at 11:33