论文笔记 – Unsupervised deep embedding for clustering analysis

Xie, Junyuan, Ross Girshick, and Ali Farhadi. “Unsupervised deep embedding for clustering analysis.” international conference on machine learning (2016): 478-487.

1. Intro

这篇论文依旧是深度聚类，想特征提取后，用特征聚类。

2. Related

深度聚类大致有两个流派：第一类是用自编码器或深度网络提取特征，再进行聚类、fintune；第二种是设计深度网络，使特征提取与聚类这两个任务可一起优化。第一种方法里，聚类的到的结果并不能用来监督特征提取网络。但是后一种方法往往会用前一种方法先做个预训练，让开局靠谱点。

第一类方法大致是这样发展的：

[1] 大概是 自编码器 + K-means

[2] 大概是 自编码器 + 谱聚类（将 k-means 里面的拉普拉斯矩阵换成了模块度矩阵，模块度矩阵的最优化就等价于谱聚类）

[3] 本文亦是同样思路，大概是 自编码器 + t-SNE 微调

3. Approach

首先，我们假设现在有了一个从原始数据空间 $x_i$ 到特征空间 $z_i$ 的一个 embedding $z_i = f_\theta(x_i)$，那么我们用 t 分布描述降维后第 i 个点 $z_i$ 和第 j 类的中心 $u_j$ 之间的相似度：

$$ q_{ij} = \frac{(1 + ||z_i – u_j||^2 / \alpha)^{-\frac{\alpha+2}{2}}} {\sum_{j’}(1 + ||z_i – u_{j’}||^2 / \alpha)^{-\frac{\alpha+2}{2}}}$$

其中 $\alpha$ 为 t 分布的自由度，控制分布曲线形态（高矮胖瘦）的。 $\alpha$ 没法调参，因此本文直接 $\alpha = 1$，所以

$$ q_{ij} = \frac{(1 + ||z_i – u_j||^2 )^{-1} }{\sum_{j’}(1 + ||z_i – u_{j’}||^2)^{-1}}$$

$q_{ij}$ 的计算其实就是 softmax，所以也就表示在当前的 embedding 情况下，第 i 个样本被分到第 j 类的概率。

那怎么评测现在的 embedding 好不好呢？本文受 t-SNE 的启发（t-SNE 可以看 [3] 的讲解），将特征提取过程中的优化问题设计为最小化 embedding 前后数据概率分布之间的 KL divergence，以此进行降维。因此损失函数：

$$ L = KL(P||Q) = \sum_i\sum_jp_{ij}log\frac{p_{ij}}{q_{ij}}$$

$q_{ij}$ 是 embedding 之后样本 i 属于 j 类的概率， $p_{ij}$ 是原始潜在目标分布中样本 i 属于 j 类的概率。$min KL$ 就是让这俩尽量接近。

那么现在就来到了最重要的问题：$p_{ij}$ 咋设计呢？作者提出，$p_{ij}$ 分布需要满足三个性质：

1. strengthen predictions (i.e., improve cluster purity)
2. put more emphasis on data points assigned with high confidence
3. normalize loss contribution of each centroid to prevent large clusters from distorting the hidden feature space.

根据此，设计出了 $p_{ij}$：

$$p_{ij} = \frac{q_{ij}^2 / f_j}{\sum_{j’}q_{ij’}^2 / f_{j’}}$$

其中，$f_j = \sum_iq_{ij}$，就表示第 $j$ 类的大小。因此设计这个的意思就是 $q_{ij}$ 先平方，再 normalize （对类的规模惩罚），再 softmax 的概率。

那么为什么要平方呢？我觉得是为了满足作者提出 $p_{ij}$ 分布需要满足的前两个性质：平方之后，让大的更大、小的更小，满足了 1；同时，如果样本 i 属于 j 类的概率 $q_{ij}$ 比其他样本属于 j 类的概率高得多，那么算出来的 $p_{ij}$ 也会大得多，这样就满足了 2。因此在最终的优化过程中，”DEC improves upon the initial estimate in each iteration by learning from high confidence predictions, which in turn helps to improve low confidence ones”。

作者画了一张图，横坐标是 $q_{ij}$ ，纵坐标是 $\frac{\partial L}{\partial x_i}$。从这张图就能看出来，$q_{ij}$ 大，即样本 i 更接近 j 类中心，比别的点更有可能属于 j 类，即 i 是 high confidence prediction，那么 i 点对于梯度的影响就很大。

4. Implementation

先预训练，一层一层训练堆栈自编码器（SAE），作为特征提取网络的初始参数。然后在这个 SAE 得到的特征空间里，直接 k-means，得到初始的 k 个 clusters 的中心 ${\mu_j}_{j=1}^k$

优化的过程用的动量 SGD：计算 $\frac{\partial L}{\partial z_i}$，训练特征提取网络参数；计算 $\frac{\partial L}{\partial \mu_j}$，更新聚类的中心。

当两个 iteration 之间，变化到不同类的样本数小于某个数的时候，就停止循环。

我用 [4] 的代码跑了一下，发现整个还是依靠自编码器，后面的优化过程只让性能好了一点点：

当然，这种用相对熵的优化还是要比之前 related 里面提到的 AE + k-means 好一些。

然后可能是由于有了 AE，后面优化可能是 O(n) 复杂度，所以这个算法真的非常快就结束了！

关于应该选几类，作者也是提出了一个我没见过的方法：

$$G = \frac{L_{train}}{L_{validation}}$$

G 太小就说明很可能过拟合，因此就找到 G 随 k 增加而骤降的那个点，就是比较好的 k ？

5. Conclution

很多深度聚类都是先 AE 提取特征，再 fintune。我感觉这篇论文的 fintune 就是用 t-SNE，让每类再紧一点。

6. References

[1] Tian, Fei, et al. “Learning Deep Representations for Graph Clustering.” AAAI. 2014.

[2] Yang, Liang, et al. “Modularity Based Community Detection with Deep Learning.” IJCAI. 2016.

[3] https://www.bilibili.com/video/BV1T4411T7ES

[4] https://github.com/XifengGuo/DEC-keras