# clustering with KL divergence

Recently I read some papers which related to clustering.

In this paper, they calculate Loss function as KL Divergence, KL(P||Q). They denote target distribution as P, and auxiliary distribution Q.

Definition of p and q is like this.

$$q_{ij} = \frac{(1+||z_i-\mu_i||^2/\alpha)^{-(\alpha+1)/2}}{\sum_{j'}(1+||z_i-\mu_{j'}||^2/\alpha)^{-(\alpha+1)/2}}$$

$$p_{ij} = \frac{q^2_{ij}/\sum_i q_{ij}}{\sum_{j'}q^2_{ij'}/\sum_i q_{ij'}}$$

My first question is that in paper, $$\ q_{ij}$$ can be interpreted as the probability of assigning sample i to cluster j. However I cannot interpret what $$\ p_{ij}$$ means.

Second question is that, how should I interpret KL(P||Q) and objective of this clustering method?

You're right that $$q_{ij}$$ is the probability of seeing the sample point $$z_i$$ in the cluster with centroid $$u_j$$ under the assumption that points are distributed by the Student t-distribution.

The target distribution, $$p_{ij}$$ represents ideal clusters. In the most extreme case, clusters could be defined by a delta distribution over a ball of a given radius around the cluster centroid (i.e. if the point is within the radius, it has probability 1 of being a member of the cluster). However, such a discontinuous definition is computationally impractical and makes the optimization problem difficult. Instead, the authors opted for a softer constraint that still puts most of the probability mass around the cluster centroid. They achieve this by looking at the squared Student t-distribution and normalizing by the relative frequency of the cluster, (a.k.a. the soft cluster frequency given by $$\sum_{i} q_{ij}$$).

In this context, the KL divergence, $$\text{KL}(P||Q)$$, is interpreted as the amount of information lost when you use the distribution Q to approximate the distribution P. Specifically, it is the error (in bits) of the observed distribution over the data points Q when you wanted the ideal cluster distribution P.

Finally, the authors consider points that might exist in a high dimensional space (the authors reference images), and seek to find a low dimensional representation of them (the features) which preserves local structure of the points but also identifies a grouping of the points into clusters. The authors capture this trade-off with a joint error function summing the reconstruction loss of the auto-encoder with the above clustering error.

• Thanks to your detailed explain. However, others question is left... As you know, the target distribution P and auxiliary distribution share centroid parameters. My point is that how can it be interpreted that the shorter the KL Divergence is, the better clustering is fitted in this case. – Gwan Jan 23 at 7:51
• I just guess that, Q is a distribution which we generally estimate, and P is a designed or assumed distribution which we want to fit with some condition.(In this paper, authors referred 3 conditions.) Thus, is it similar to the process in GMM based clustering of which objective function is Likelihood? – Gwan Jan 23 at 9:45