【计算机视觉】【聚类】SeLa：同时进行聚类和表示学习的自标注算法

论文地址：https://arxiv.53yu.com/pdf/1911.05371.pdf

相关博客：
【自然语言处理】【聚类】基于神经网络的聚类算法DEC
【自然语言处理】【聚类】基于对比学习的聚类算法SCCL
【自然语言处理】【聚类】DCSC：利用基于对比学习的半监督聚类算法进行意图挖掘
【自然语言处理】【聚类】DeepAligned：使用深度对齐聚类发现新意图
【自然语言处理】【聚类】CDAC+：通过深度自适应聚类发现新意图
【计算机视觉】【聚类】DeepCluster：用于视觉特征无监督学习的深度聚类算法
【计算机视觉】【聚类】SwAV：基于对比簇分配的无监督视觉特征学习
【计算机视觉】【聚类】CC：对比聚类
【计算机视觉】【聚类】SeLa：同时进行聚类和表示学习的自标注算法
【自然语言处理】【聚类】ECIC：通过迭代分类增强短文本聚类
【自然语言处理】【聚类】TELL：可解释神经聚类

一、简介

​ 从无标注样本中学习可以极大的降低部署机器学习算法的代价，从而能够进一步提高机器学习算法对现实世界的影响。自监督是一种不使用标签进行学习的流行学习框架，其只使用原始数据来构建任务，但仍然能够改善神经网络的效果。

​ 许多自监督的研究主要是专注在设计新的自监督任务。然而，通过使用像$\text{ImageNet}$的监督数据并通过标准的交叉熵损失函数，仍然能够获得很好的预训练。这就表明，通过具有合适标签的分类任务进行预训练是充分的。在本文中，主要是通过设计子标注算法来自动获取标签。

​ 自动发现数据标签的同时进行深度神经网络学习，等价于同时进行聚类和表示学习。通过最小化交叉熵和使用现有的聚类算法可以实现，这也是$\text{DeepCluster}$采用的方式。然而，合并表示学习和聚类并不容易，特别是像$\text{DeepCluster}$那样合并最小化交叉熵和$\text{K-means}$。$\text{DeepCluster}$并没有将两个步骤合并至一个整体的目标函数来进行优化，而是通过特定的执行步骤来避免退化解。

​ 为了解决这个问题，本文提出了一种同时进行聚类和表示学习的新方法。一般来说，同时学习神经网络和估计数据的标签是通过半监督学习和多实例学习来实现的。然而，将这种方法单纯的应用在无监督的场景中会导致退化解的问题，即所有的样本被映射至相同的簇。本文通过添加均等划分约束来解决这个问题，并证明了其是数据索引和标注的最大化互信息。此外，本文还证明了得到的结果分配问题与最优运输问题等价，因此可以通过线性规划在多项式时间内求解。然而，实际中可能有数百万个数据和上千个标签，使用标准的方法求解运输问题是不够的。所以，本文提出使用快速版本算法$\text{Sinkhorn-Knopp}$来求解运输问题的近似解。

​ 相比于$\text{DeepCluster}$这样的方法，新的方法理论上更加的清晰且更容易证明该方法的各种性质。通过大量的实验证明，本文的方法结果显著优于$\text{DeepCluster}$，实现了表示学习的$\text{state-of-the-art}$。实际上，本方法的效果超越了其他使用单一类别监督信号进行自监督的方法，与最新的研究结果相当甚至更好。

二、自标注算法

​ 在计算机视觉领域，神经网络的预训练已经通过有监督的分类任务实现了。正式来说，给定一个将数据$I$映射至特征向量$\text{x}\in {\mathbb{R}}^D$的深度神经网络$\Phi$，即$\text{x}=\Phi (I)$。使用有$N$个样本$I_1,\dots ,I_N$且具有标签 y 1 , … , y N ∈ { 1 , … , K } y_1,\dots,y_N\in\{1,\dots,K\} y1​,…,yN​∈{
1,…,K}的数据集训练该模型。在获取的向量后跟一个分类头$h:{\mathbb{R}}^D\to {\mathbb{R}}^K$，从而将特征向量转化为一个类别分数向量。最后通过$\text{softmax}$将类别分数映射为类别概率
$$p(y=\cdot |{\text{x}}_i)=\text{softmax}(h\circ \Phi ({\text{x}}_i))$$
模型通过最小化平均交叉熵来学习
$$E(p|y_1,\dots ,y_N)=-\frac{1}{N}\sum _{i=1}^N\text{log}p(y_i|{\text{x}}_i)\text{\hspace{1em}(1)}$$
以损失函数$(1)$来训练模型是需要标注数据的。但是，在没有标注数据的情况下就需要一种”自标注”($\text{self-labelling}$)机制来自动生成标签。

​ 在半监督学习中，”自标注”通常需要联合优化模型$h\circ \Phi$和标签$y_1,\dots ,y_N$。如果能够获取一部分的标签，那么该方法就可以使用。但是，在无监督常见中，该方法会导致退化解。也就是，可以通过将数据数据样本分配到同一个标签来实现等式$(1)$的最小化。为了解决该问题，通过将标签编码为后验分布$q(y|{\text{x}}_i)$来重写等式$(1)$
$$E(p,q)=-\frac{1}{N}\sum _{i=1}^N\sum _{y=1}^{K}q(y|{\text{x}}_i)\text{log}p(y|{\text{x}}_i)\text{\hspace{1em}(2)}$$
若后验概率分布$q(y|{\text{x}}_i)=\delta (y-y_i)$是确定的，那么等式$(1)$和等式$(2)$就是等价的，即$E(p,q)=E(p|y_1,\dots ,y_N)$。在本方法中，优化分布$q$就等价于重写分配标签，这会导致退化解。为了避免退化解问题，该方法为标签的重新分配添加了均等划分约束。正式来说，
min p , q    E ( p , q ) subject to ∀ y : q ( y ∣ x i ) ∈ { 0 , 1 }    and ∑ i = 1 N q ( y ∣ x i ) = N K (3) \mathop{\text{min}}_{p,q}\; E(p,q)\quad\text{subject to}\quad\forall y:q(y|\textbf{x}_i)\in\{0,1\}\;\text{and}\sum_{i=1}^N q(y|\textbf{x}_i)=\frac{N}{K} \tag{3} minp,q​E(p,q)subject to∀y:q(y∣xi​)∈{
0,1}andi=1∑N​q(y∣xi​)=KN​(3)

该约束意味着每个样本${\text{x}}_i$都会被均等的分配至每个标签上，也就是整体$N$个样本被均匀分配到$K$个类别上。

​ 优化目标函数$(3)$中的$q$是一个难以优化的组合优化问题。但是，其可以看做是一个相对容易求解的最优运输问题的实例。为了更清晰，令$P_{y_i}=q(y|{\text{x}}_i)\frac{1}{N}$表示由模型估计的、大小为$K\times N$的联合概率矩阵。类似地，令$Q_{y_i}=p(y|{\text{x}}_i)\frac{1}{N}$表示分配后的联合概率矩阵。这里放松矩阵$Q$为$\text{transportation polytope}$上的元素，即
U ( r , c ) : = { Q ∈ R + K × N ∣ Q 1 = r , Q ⊤ 1 = c } (4) U(r,c):=\{Q\in\mathbb{R}_+^{K\times N}|Q\textbf{1}=r,Q^\top\textbf{1}=c\} \tag{4} U(r,c):={
Q∈R+K×N​∣Q1=r,Q⊤1=c}(4)
其中， $\text{1}$表示具有合适维度的全1向量，所以$r$和$c$是矩阵$Q$在行和列上的投影。在本方法的例子中，需要$Q$是均等划分数据的条件概率分布矩阵，即需要满足
$$r=\frac{1}{K}\cdot \text{1},c=\frac{1}{N}\cdot \text{1}$$
使用新的符号重写等式$(3)$的目标函数为
$$E(p,q)+\text{log}N=⟨Q,-\text{log}P⟩\text{\hspace{1em}(5)}$$
其中，$⟨\cdot ⟩$是两个矩阵的$\text{Frobenius}$点积，$\text{log}$应用在每个元素上。

因此，基于目标函数$(3)$来优化$Q$等价于求解下面的问题
$${\min }_{Q\in U(r,c)}⟨Q,-\text{log}P⟩\text{\hspace{1em}(6)}$$
该问题是一个线性规划问题，可以在多项式时间内求解。

这是一个线性规划问题，其可以在多项式时间内求解。在实际求解中，该线性规划可能涉及数百万个样本和上千个类别。传统求解运输问题的算法很难求解这种规模的问题，本文采用了一种称为$\text{Sinkhorn-Knopp}$的快速求解方法。这相当于引入正则化项
$${\min }_{Q\in U(r,c)}⟨Q,-\text{log}P⟩+\frac{1}{\lambda }\text{KL}(Q\parallel r{c}^{\top })\text{\hspace{1em}(7)}$$
其中，$\text{KL}$是$\text{Kullback-Leibler}$散度，$r{c}^{\top }$能够被看作是$K\times N$的概率矩阵。添加这个正则化项的好处是，最小化等式$(7)$能够被重写为
$$Q=\text{diag}(\alpha )P^{\lambda }\text{diag}(\beta )\text{\hspace{1em}(8)}$$
其中，指数操作是元素级别，$\alpha$和$\beta$是选择的缩放稀疏向量，因此得到的矩阵$Q$仍然是一个概率矩阵。通过简单的矩阵缩放迭代就能够获得向量$\alpha$和$\beta$。

​ 当$\lambda$非常大时，目标函数$(7)$等价于目标函数$(6)$。但是，即使只使用适度的$\lambda$，两个目标函数也往往具有类似的优化目标。$\lambda$的选择是收敛速度和运输问题求解精确度的一个折中。在本文中，使用一个固定的$\lambda$是合理的，因此本文感兴趣的是最终聚类和表示学习的结果，而不是准确的求解运输问题。

​ 最终的算法描述如下。通过求解等式$(6)$中的$Q$来学习模型$h\circ \Phi$和标签分配$Q$，其中$Q$是概率矩阵，而模型$h\circ \Phi$决定了预测结果$P_{y_i}={\text{softmax}}_y(h\circ \Phi ({\text{x}}_i))$。交替执行两面的两个步骤

• 步骤1：表示学习

  给定一个当前的标签分配$Q$，通过最小化等式$(6)$来更新$h\circ \Phi$的参数。这相当于普通分类问题的交叉熵损失函数。

• 步骤2：自标注

  给定当前的模型$h\circ \Phi$，计算对数概率$P$。然后通过使用等式$(8)$进行迭代更新来寻找$Q$
  $$\forall y:\alpha \leftarrow [P^{\lambda }\beta {]}_y^{-1}\forall i:{\beta }_i\leftarrow [{\alpha }^{\top }{P}^{\lambda }{]}_i^{-}1$$

每次迭代更新都涉及到$\mathcal{O}(NK)$复杂度的矩阵乘法。所以，在数百万样本和上千个标签的情况下，速度也很快。在实际训练中，在$\text{ImageNet}$上使用$\text{GPU}$的话，可以在2分钟内达到收敛。

三、解释

​ 如果将数据的索引$i$看作是概率为$p(i)=1/N$的均匀分布随机变量，且后验概率重写为数据索引$i$的概率$p(y|{\text{x}}_i)=p(y|i)$和$q(y|{\text{x}}_i)=q(y|i)$。那么，等式$(5)$可以重写为
$$E(p,q)+\text{log}N=-\sum _{i=1}^N\sum _{y=1}^{K}q(y,i)\text{log}p(y,i)=H(q,p)\text{\hspace{1em}(9)}$$
该式为标签和索引联合分布$p(y,i)$和$q(y,i)$的交叉熵。当$p==q$时，该等式能够获得关于$q$的最小值。即目标$E(q,q)+logN$等价于随机变量$y$和$i$的熵$H_q(y,i)$。此外，因为假设$q(i)=1/N$，边际熵$H_q(i)=\text{log}N$是一个常数，且由于均等划分的条件，所以$q(y)=1/K$，$H_q(y)=\text{log}K$也是常数。从最终的结果中减去这两个常数
$${\min }_{p}E(p,q)+\text{log}N=E(q,q)+\text{log}N=H_q(y,i)=H_q(y)+H_q(i)-I_q(y,i)=\text{const.}-I_q(y,i)$$
可以看到，最小化$E(p,q)$等价于最大化标签$y$和数据索引$i$间的互信息。

​ 在本文的公式中，上面的最大化是在均分约束下实现的。可以放松这个约束，并直接最大化互信息$I(y,i)$。然而，通过重新互信息为$I(y,i)=H(y)-H(y|i)$，可以发现$H(y|i)=0$的情况下得到最优解，其表明每个样本$i$都仅与一个标签相关联；此外，通过$H(y)=\text{ln}K$来以另一种方式表明均分条件。

​ 换句话说，本文的学习方法可以被看作是在精准执行均分条件的同时，最大化数据标签和索引间的互信息。相比于单独最大化熵和最大化互信息，避免了退化解。

四、与同时进行表示学习和聚类的关系

​ “自标注”相当于将离散标签分配到数据上，能够看作是聚类。传统的聚类算法都是生成的。例如，$\text{K-means}$需要输入一个向量数据集${\text{x}}_1,\dots ,{\text{x}}_N$，并通过最小化重构误差将其划分至$K$个类别
$$E({\text{u}}_1,\dots ,{\text{u}}_K,y_1,\dots ,y_N)=\frac{1}{N}\sum _{i=1}^N\parallel {\text{x}}_i-{\text{u}}_i{\parallel }^2\text{\hspace{1em}(10)}$$
其中， y i ∈ { 1 , … , K } y_i\in\{1,\dots,K\} yi​∈{
1,…,K}是数据到簇的分配，${\text{u}}_y$对于簇的平均近似向量。

​ 像$\text{K-means}$这种聚类方法能否使用一个判别目标，从而合并至表示学习中。在这种情况下，特征向量$\text{x}=\Phi (I)$是由设计好的网络$\Phi$从数据$I$中抽取出来的。不幸的是，针对聚类和表示学习的参数来优化等式$(10)$的损失函数使没有意义的。因为，令所有样本的表示相同且所有簇的均值也相同的话，就能令$\text{K-means}$的重构误差为0。

​ 然而，$\text{DeepCluster}$成功的合并了$\text{K-means}$和表示学习。$\text{DeepCluster}$与本文方法的联系如下。在算法步骤1中，通过最小化交叉熵的进行表示学习是完全相同的。在算法步骤2中，即”自标注”，本文会求解一个最优运输问题来获得伪标签，而$\text{DeepCluster}$则是会在神经网络抽取的特征上执行$\text{K-means}$。

​ $\text{DeepCluster}$并没有得到退化解(退化解：所有数据被分配至相同的标签且学习到一个常量表示)，而是能够同时最小化步骤1的交叉熵损失函数和步骤2的$\text{K-means}$损失函数。$\text{DeepCluster}$能够避免退化解的原因是由于两个步骤间的特殊交互。首先，在步骤2中，特征${\text{x}}_i$是固定的，所以$\text{K-means}$并不能同时进行优化。其次，在分类的步骤中，簇分配$y_i$是固定的，通过交叉熵来优化特征${\text{x}}_i$是会倾向于将它们分开。

​ 然而，$\text{DeepCluster}$的缺点是没有一个单独的、很好定义的目标函数来优化，这意味着很难描述它的收敛性质。相比之下，本文的公式中，步骤1和步骤2同时优化相同的目标，其优点是保证收敛到局部最优。

五、数据增强

​ $\text{DeepCluster}$通过数据增强来扩展训练数据。在计算机视觉领域，数据增强等价于随机的扭曲和裁剪输入图像。增强数据的使用能够鼓励神经网络学习到一个具有转换不变性的函数。在实际应用中，数据增强对于学习一个好的簇和特征表示是至关重要的，本文也采取了数据增强。具体来说，数据增强通过$P_{y_i}={\mathbb{E}}_t[{\text{log softmax}}_{y}h\circ \Phi (t{\text{x}}_i)]$来实现，其中数据变换$t$是随机采样获得的。

六、多任务

​ 直觉上，相同的数据能够通过许多途径来进行聚类。例如，图像能够通过颜色、尺寸、类型、视角等熟悉被聚类。由于本文的目标是使用聚类来学习一个好的数据表征$\Phi$，所以这里使用了多任务的设置。相同的特征表示在几个不同的聚类任务上共享，这有助于捕获不同的、互补的聚类特征。

​ 在本文中，多任务很容易通过多头$h_1,\dots ,h_T$来实现，其$T$个聚类任务的个数。然后，优化每个聚类任务在等式$(6)$上的损失函数之和，其共享特征抽取器$\Phi$的参数。

七、总结

• 聚类和分类交替执行的方式是可以预训练模型的；
• 通过均等划分约束来避免退化解；
• 理论分析了均等划分约束的有效性，并分析了与$\text{DeepCluster}$的关系；
• 本文的均等约束聚类方式只适合进行模型预训练，无法进行聚类。因为，每个簇中都具有相同数量的样本，这不符合真实聚类的结果；

今天的文章【计算机视觉】【聚类】SeLa：同时进行聚类和表示学习的自标注算法分享到此就结束了，感谢您的阅读。