clustering with KL divergence

Question

Recently I read some papers which related to clustering.

The paper is https://xifengguo.github.io/papers/ICONIP17-DCEC.pdf

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?

Answer 1

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.