1
$\begingroup$

In today's lecture we learnt that k-means would be generative model.

I am really puzzled on this because in my intuition it would be more a discriminative model since there is no probability to predict the classes given a number of values and features. I tried to research on the web but I found very little and conflicting statements on this.

So why should k-means be a generative model and how could it be used to generate new data then?

$\endgroup$
2
  • $\begingroup$ “ discriminative model since there is no probability involved”—can you please explain this remark? $\endgroup$ Nov 18, 2021 at 19:25
  • $\begingroup$ I tried to clarify it $\endgroup$ Nov 18, 2021 at 19:46

1 Answer 1

2
$\begingroup$

I guess technically, you can interpret k-means as a generative model through the connection to mixture models, though this is a stretch that you can only make by seriously constraining the expressivity of your generative model.

A generative model is simply a model for the joint distribution over covariates and labels $(X, Y)$, then use Bayes' rule to calculate $P(Y\mid X)$ to perform inference:

$$\hat{Y} = \underset{Y}\arg\max\; P(Y \mid X)$$ $$\hat{Y} = \underset{Y}\arg\max\; P(X \mid Y)P(Y) / P(X)$$ $$\hat{Y} = \underset{Y}\arg\max\; P(X \mid Y)P(Y) \quad \text{(X is constant w.r.t. Y)}$$ $$\hat{Y} = \underset{Y}\arg\max\; P(X, Y) \quad \text{(by definition of conditional probability)}$$ which is the model the generative model fits in the first place.

So how is k-means a generative model? One way to interpret this is that k-means models the joint distribution over (X, Y) by optimizing over a certain (as in, w.p. 1) assignment of points $X$ to clusters corresponding to $Y$. Since k-means assigns each point to one cluster only, say, point $x^{(i)}$ to cluster $C(x^{(i)})$, we have that $P(x^{(i)}, C(x^{(i)})) = 1$, and $P(x^{(i)}, C(\cdot)) = 0$ for any other cluster. Using the method for inference in a generative model described above, k-means results in predictions that simply "look up" which cluster a point belongs to, which is what you do for k-means.

The more rigorous interpretation of this is through the connection between k-means and mixture models, which is often addressed via the EM-algorithm for a Gaussian mixture model with spherical clusters as described here. In the GMM case, it is also possible (and arguably more intuitive) to interpret the model as performing a "soft"/probabilistic assignment of points $X$ to clusters for $Y$.

Also, I don't understand the statement about a discriminative model not having probabilities to predict the number of classes -- logistic regression-based classifiers are discriminative models that output a "probability score," and by definition, discriminative models predict $P(Y \mid X)$.

Edit:" I forgot to answer your question about generating new data. Through the connection from k-means to a spherical Gaussian mixture model, you can select a cluster (i.e. pick $Y$), choose the Gaussian corresponding to the cluster, and generate data by drawing from that distribution (I think -- I've never done this myself). The centroid corresponds to the mean of the cluster.

The derivation is provided here. However, note that $\sigma$, i.e. the variance of underlying Gaussians in the mixture, is non-identifiable, as changing the variance does not impact the objective function.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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