18
$\begingroup$

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)
$\endgroup$
0

8 Answers 8

13
$\begingroup$

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.

$\endgroup$
7
  • 8
    $\begingroup$ I want to push back on this answer. Overfitting is not unique to supervised learning. Random data can look structured simply due to randomness; overfitting refers to estimation procedures that mistake random noise for true structure. In particular, let's think about clustering. Suppose data comes from a Gaussian mixture with 5 clusters, but they are noisy and you estimate that there are 10 clusters. This is overfitting, regardless of the fact that there are no labels and you have no access to ground truth data. $\endgroup$ Sep 20, 2019 at 15:13
  • $\begingroup$ To decide whether a model is overfitting some data, the model must be firstly a parametric model. Because only parametric models need to fit some parameters, then use the fitted parameters to predict new data. For clustering, we can test using the fitted parameters to predict labels of training data and new data points, if the fitted model parameters works better for training data points than new data points, then overfitting occurs. This can be easily checked in 2 dimensional data. $\endgroup$ Dec 9, 2023 at 8:21
  • $\begingroup$ @MikeMathcook it's not true that only parametric models overfit. kNN or Gaussian process can easily overfit. $\endgroup$
    – Tim
    Dec 9, 2023 at 14:07
  • $\begingroup$ @ Tim Maybe you are right. But I cannot see a straightforward interpretation of overfitting in non-parametric models. Taking kNN as an example, what are you fitting in kNN? the k? $\endgroup$ Dec 9, 2023 at 15:50
  • $\begingroup$ @MikeMathcook Nothing in the definition of overfitting, nor the procedure you suggest, needs the model to be parametric. If you are unsure what we are fitting when using kNN, I recommend some general machine learning handbooks. We fit the model to the data, models do not need to be parametric for us to fit them. $\endgroup$
    – Tim
    Dec 10, 2023 at 15:39
4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ What's the theory behind this? Any papers that use posterior entropy as a measure of overfitting? I've never seen anything similar to this idea! "as you overfit, a lot of samples of high certainty appears, which would have their entropy close to zero" - I noticed this after observing lots of posterior distributions in Gaussian mixtures: components with zero variance (thus, way too concentrated and basically useless) tend to have posteriors like [0,0,0,1,0,0,...], but I never thought of calculating the entropy of these posteriors. $\endgroup$
    – ForceBru
    Jan 27, 2022 at 0:17
  • $\begingroup$ @ForceBru I dont know such papers AFAIK... But entropy is a generic statistics for describing uncertainty, and thus posteriors like [0,0,0,1] means the model is very certain about which component it exists, which is probably NOT a big problem by itself. The only problem comes when you have too many fragmented components, and AIC and BIC is a way to balance between model complexity and fitting goodness... But I guess entropy is still a good criteria to assess model goodness, if the desired properties is just the correctness of the predicted category, instead of log-likelihood. $\endgroup$
    – shouldsee
    Jan 27, 2022 at 13:49
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Classification is per se supervised. Many people who use classification for unsupervised learning are in deed looking for clustering techniques or for supervised learning. $\endgroup$
    – Ferdi
    Aug 3, 2017 at 13:00
  • $\begingroup$ @Ferdi - no. We hope that some who receive this document can help us in understanding these classes. AutoClass is an unsupervised classification systems. Experts may (optionally) interpret the results when the dust settles. $\endgroup$
    – krkeane
    Aug 3, 2017 at 13:09
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
-2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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