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?


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.

  • $\begingroup$ 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. $\endgroup$ – Gwan Jan 23 at 7:51
  • $\begingroup$ 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? $\endgroup$ – Gwan Jan 23 at 9:45

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.