Is overfitting a problem in unsupervised learning?

Question

Consider the density estimation problem for some training set $(x_1 ... x_N)$. A gaussian mixture model consisting of $N$ normal distributions centered on each $x_i$ with very small variances will "overfit": the likelihood will be very high on the training data, and very low on unseen data points.

My questions are:

• Is overfitting considered a problem in unsupervised learning, just as it is in supervised learning? (it is certainly not discussed as frequently!)
• Should cross-validation be used to prevent overfitting of unsupervised models?
• Are there theoretical results similar to the generalization bounds derived in the supervised setting? (results that would for example relate the expected likelihood, the likelihood on the training set, the sample size and the model complexity)

Answer 1

We talk about overfitting when the model performs better on training sample, then on validation sample. First of all, how would you define overfitting for unsupervised learning? If you conduct, say, clustering analysis of your data, then there is no objective criteria to say that some output is "correct". Even more, there is no "correct" clustering solution, as there is no labels in unsupervised scenario. How would you judge performance of clustering? How would you say that it performs "worse" on validation sample? The same applies to cross-validation. You can check how stable is some clustering solution as learned on multiple subsamples, but this has nothing to do with under, or overfitting.

On another hand, you can say about sort of overfitting in unsupervised case. If you fit $n$ clusters to $n$ cases, then you'd end up with (useless) clustering solution that does not translate to external data. In such case, clustering would overfitt by design, but this is not really measurable.

The same with density estimation. There is no single "correct" solution. On another hand, if you set bandwidth in kernel density estimation to zero, you'll end up with density estimate that fits perfectly to your data, but does not translate to external data. The whole trick in here is to find solution that is general enough to be useful, and detailed enough to share some specific features of your data--but there is no single best solution like this.

Answer 2

Overfitting is of course a practical problem in unsupervised-learning. It's more often discussed as "automatic determination of optimal cluster number", or model selection. Hence, cross-validation is not applicable in this setting.

If you are running a stochastic algorithm, such as fitting a latent-variable model (like GMM), you can potentially observe overfitting by measuring the stochasticity of the output model. The empirical measure I have used is the distribution of the per-sample entropy of the predicted labelling.

This idea comes from the notion of criticality in statistical physics. Basically if the temperature is too high then the model would be completely random. But if the temperature is too low, then the model will not learn any useful labelling. GMM actually is not the best model to describe this notion, but still worth trying. The notion of temperature in GMM is the variance parameter.

The entropy of the labelling is useful in the sense: as you overfit, a lot of samples of high certainty appears, which would have their entropy close to zero. On the contrary, if the temperature is too high, then you would have no certainty of the labelling at all, and hence high entropy.

Answer 3

An unsupervised approach to classification that does not overfit is described in:

• Cheeseman, Peter, et al. "Autoclass: A Bayesian classification system." Readings in knowledge acquisition and learning. Morgan Kaufmann Publishers Inc., 1993.

You will find several similarly titled related reports and articles. Scan several of these as the technical depth varies. Your desired model, a Gaussian mixture model, is a subset of the problem domain AutoClass addresses. Cheesman et. al. provide a very thorough theoretical framework for their solution.

The AutoClass software is available for downloading.

Answer 4

I tend to agree with the variance approach. Let's say you have a GMM or even a more complex structure like a Hidden Markov Model. Then from a practical point of view, for example in trading, you would like your model to have low variance so it performs well during live trading. So, overfitting in this unsupervised setting could be defined as high variance in the recovered structure when using bootstrapped samples (GMM) or rolling windows (HMM).

Answer 5

I would agree with @Tim's answer/question "how would you define overfitting for unsupervised learning?"

It doesn't make sense to divide an unlabelled dataset into training and validation sets, unlike in supervised learning, because then what are you validating? Clustering, or unsupervised learning, tries to find the underlying structure of the data set in question. A common definition is that it is

the task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more similar (in some sense or another) to each other than to those in other groups (clusters).

So in our question: what does applying the training set's clusters to the validation set tell you about the structure they revealed in the training set? It might be interesting to note that there are different clusters produced from the two sets, but that doesn't invalidate the clusters found in the training set.

That being said, there is (at least) one scenario where you might perform cluster analysis with labels: where you run a clustering algorithm against a benchmark dataset which includes class labels. Evaluating the resulting clustering using an external measure of quality, such as Purity or Rand measure, could then tell you if your algorithm of choice is capable of detecting the kind of structure you are interested in; e.g. k-means is not able to detect non-convex structures. Care must be taken still, however: as Färber et al. discuss, it is not necessarily the case that your labels correspond with the structure in the data.

EDIT: properly reference Tim's answer.