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

I don't agree with some of the answers that say overfitting doesn't happen in unsupervised learning and that cross-validation can't be performed in unsupervised setting. Assume you split data in train and validation $x = x_{tr} \cup x_{vld}$ and the parameters are chosen as $\theta_{tr}^{\star} = \mathrm{argmax}_{\theta} p(x_{tr} ; \theta)$ where $p(\cdot; \theta)$ is some probabilistic model of the data (e.g. Gaussian mixture model in clustering). A more flexible model (e.g. with more clusters) will have a higher likelihood on the training data. We can test whether this is overfitting by computing $p(x_{vld}; \theta_{tr}^{\star})$ i.e. by the model's likelihood on the validation set -- this can be done for multiple settings e.g. the number of different clusters.

Answer 4

I focus on unsupervised classification i.e. clustering, as suggested by the question.

There is a major difference between supervised and unsupervised classification that needs to be kept in mind. This is that in supervised classification the existing true classes are known, and the problem is defined by the classes available for training. But in many or even most datasets there can be more than one legitimate and potentially meaningful classification. For example, data on people may be classified by gender, country, job, home ownership, party membership, smoker/non-smoker, any conceivable categorical variable really. In supervised classification it is fixed which classification we consider. In clustering it isn't, and which potentially legitimate classification we find is implied by our choice of clustering method and other choices such as variable selection, distance definition, standardisation and transformation. In this sense clustering is constructive, it is not about just passively discovering a unique truth.

Therefore any quality assessment of a clustering should make reference to the aim of clustering, the meaning of the data, and further relevant background information.

Any concept of "overfitting" would be relative to such choices. In fact I believe that the term "overfitting" can be applied to the following phenomenon. Interested in finding reasonably big meaningful data subsets, we may apply a Gaussian mixture model with BIC that in a small enough dataset can give an "intuitively reasonable" clustering, i.e., in line with data visualisation and subject matter knowledge and requirements. If the data set grows, there is more information in the data to discover that any meaningful and potentially well separated subset of the data that is potentially of interest is not exactly Gaussian, and eventually the BIC will decide to fit any such subset not with a single Gaussian, but with a mixture of more than one of these. If now every Gaussian component is interpreted as its own separate cluster, this may be inappropriate, as there may not be any meaningful difference between some clusters, rather only more than one Gaussian was fitted to emulate a non-Gaussian but still homogeneous shape. Note that this is a problem with the interpretation of the mixture rather than with the fit of the data itself.

The same mixture may do a good job as a density estimator without any interpretation of the individual components, but this is not what we are interested in. We may also be interested in a density estimate with a limited number of parameters and the BIC may ultimately tell us we should use too many, i.e., the trade-off between fit of the data and parsimony requirements motivated by the use we want to make of the model may play out differently than formalised in the BIC or potentially other criteria. The ICL for example will estimate fewer components in such a situation but may occasionally leave together what could be meaningfully split up.

Another formal problem with Gaussian mixtures that can be seen as connected with "overfitting" is the potential degeneration of the likelihood if so few observations are put in a cluster that an eigenvalue of the associated covariance matrix is (very close to) zero, assuming sufficiently flexible covariance matrices. Computing a maximum likelihood estimator as done by the EM-algorithm, this problem means that in fact we don't want to find a global optimum (as the likelihood can degenerate to infinity), but rather a good local optimum not too close to degeneration ("spurious clusters"). Also more constrained models (like assuming equal covariance matrices) can avoid this issue, i.e., a too flexible fit is problematic (although flexibility may be required to achieve a good fit with a low enough number of components).

A too flexible fit may also turn out to be problematic in some kind of cross-validation, namely splitting or bootstrapping the dataset, running clustering on both (or more than two) parts, and then checking whether the different clusterings are reasonably similar. If not, there is a stability problem, which may be caused by too flexible models (i.e., some kind of overfitting). More on validation based on data splitting in clustering is here: Ullmann, Hennig, and Boulesteix: Validation of cluster analysis results on validation data: A systematic framework.

In unsupervised learning, lack of supervision means that the data shouldn't be trusted to make all the decisions on their own. There may be over- or underfitting relative to what we need in a given situation.

Answer 5

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 6

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 7

Section 7.6 of the "Clustering with Neural Network and Index" paper provides another evidence of overfitting in unsupervised learning.

See:

https://arxiv.org/abs/2212.03853

Answer 8

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.