14
$\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

5 Answers 5

14
$\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$
1
  • 4
    $\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
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
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$
-1
$\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 that you have read and understand our privacy policy and code of conduct.

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