# Apply K-means to the columns of the covariance matrix

In Section 5.3 of the paper distilling the knowledge in a neural network, it says

we apply a clustering algorithm to the covariance matrix of the predictions of our generalist model, so that a set of classes $$S^m$$ that are often predicted together will be used as targets for one of our specialist models, $$m$$. We applied an online version of the $$K$$-means algorithm to the columns of the covariance matrix, and obtained reasonable clusters (shown in Table 2). We tried several clustering algorithms which produced similar results.

I know how $$K$$-means is applied to a bunch of data, but here it says applying $$K$$-means to the columns of the covariance matrix, which is quite confusing to me.

My questions are:

1. What is the covariance matrix here? (or what are the random variables related to the covariance matrix?)
2. How is it computed?
3. How is the online $$K$$-means applied to the covariance matrix?
4. Why would they do that?

My personal answer to the first question is that the random variables related to the covariance matrix are the probabilities of each class. If that's the case, then the covariance matrix can be computed from samples (according to this). But this is not an online method and seems to take an extremely large amount of computation for a large dataset.

Any comments or partial answers that can help me make progress are appreciated.

To my understanding (I am not an author of the original paper, so I might be wrong):

1. The covariance matrix is computed from the class probabilities (see Eq. (1) in the paper) produced by the generalist model. To quote from the paper:

the covariance matrix of the predictions of our generalist model

1. The paper doesn't state it explicitly, so I'd assume the covariance matrix is computed in a standard way (see e.g. Wikipedia), taking the predicted class probabilities as the random variables.

2. The columns of the covariance matrix are high-dimensional feature vectors, each column representing one input observation (e.g. an image). Online $$K$$-Means takes these feature vectors, one-by-one, and updates the cluster centroids. Again, Wikipedia is a good starting point. But, $$K$$-means is not the key ingredient here, as the authors state:

We tried several clustering algorithms which produced similar results.

1. It seems to be a question of computational resources. Training a single, high-quality classifier would have taken too long. So, instead, they are happy when the first classifier (the "generalist") achieves some rough accuracy, e.g. correctly classifying cars as cars and vegetable as vegetable, but perhaps confusing Porsche with Lamborghini or onions with chives. To cope with confusions, they train specialised smaller networks (requiring less computing power) which then correctly classify Porsches as Porsches, Lamborghinis as Lamborghinis, and onions, chives, whales, bridges, galaxies etc. as "others".

The whole purpose of $$K$$-means (or any other clustering algorithm) is to recognise that Porsches and Lamborghinis are commonly confused, so that a specialised classifier can be trained specifically for them.