Unsupervised and Semi-Supervised Learning via ℓ1-Norm Graph

1 简介

文章来源：2011-ICCV

文章主旨:

由于图拉普拉斯无法直接得到好的聚类结构，后续需要利用$K$-means来进行聚类。然而$K$-means聚类容易局部收敛，且得到非唯一的聚类结果。

对于半监督学习来说，图拉普拉斯一般使用的都是采用的二次型的图嵌入（TODO），然而这种方式对噪声和异常值敏感。

作者提出一种$\ell_1$范数约束的谱聚类框架，且扩展了一个半监督学习模型，并证明了其收敛性。

2 基本框架

2.1 谱聚类

对于$Q = \left[q_{1}, q_{2}, \cdots, q_{c}\right] \in \mathbb{R}^{n \times c}$，$q_{k} \in \mathbb{R}^{n \times 1}$为$Q$的第$k$列。

Graph Ratio Cut：

$$\begin{gathered} \min _{Q^{T} Q=I} \operatorname{Tr}\left(Q^{T} L Q\right) \\ q_k = (0, \cdots, 0, \overbrace{\frac{1}{\sqrt{n_{k}}}, \cdots, \frac{1}{\sqrt{n_{k}}}}^{n_k}, 0, \cdots, 0)^{T} \end{gathered} \tag{1}$$

Graph Normalized Cut：

$$\begin{gathered} \min _{Q^{T}DQ=I} \operatorname{Tr}\left(Q^{T} L Q\right) \\ q_{k}=(0, \cdots, 0, \overbrace{\frac{1}{\sqrt{q_{k}^{T} D q_{k}}}, \cdots, \frac{1}{\sqrt{q_{k}^{T} D q_{k}}}}^{n_k}, 0, \cdots, 0)^{T} \end{gathered} \tag{2}$$

详情可参见谱聚类（spectral clustering）原理总结一文。

2.2 基本模型

将$(2)$式写为：

$$\min _{Q^{T} D Q=I} \sum_{i, j=1}^{n} W_{i j}\left\|q^{i}-q^{j}\right\|_{2}^{2} \tag{3}$$

$Q$的理想解就是当$x_i,x_j$属于同一类时，使得$q^i = q^j$。也就是说$Q$的许多行都是相等的，这样就有了很强的聚类结构。那么我们想要很多对$(i,j)$有$\left|q^{i}-q^{j}\right|_{2}=0$，那么用$\ell_1$范数来解决这个问题也是等价的：

$$\min _{Q^{T} D Q=I} \sum_{i, j=1}^{n} W_{i j}\left\|q^{i}-q^{j}\right\|_{2} \tag{4}$$

设一个$n^2$维向量$p$，其$((i-1)*n+j)$个元素为$W_{i j}\left|q^{i}-q^{j}\right|_{2}$。那么我们将$(4)$式写为：

$$\min _{Q^{T} D Q=I}\|p\|_{1} \tag{5}$$

这样我们可以直观地知道$p$的元素会由于$\ell_1$范数的约束而变得稀疏，也就为$Q$提供了一个理想的聚类结果。

2.3 优化算法

$(4)$式的拉格朗格日函数为：

$$\mathcal{L}(Q)=\sum_{i, j=1}^{n} W_{i j}\left\|q^{i}-q^{j}\right\|_{2}-\operatorname{Tr}\left(\Lambda\left(Q^{T} D Q-I\right)\right) \tag{6}$$

设拉普拉斯矩阵$\widetilde{L} = \widetilde{D} -\widetilde{W}$，$\widetilde{D}$为第$i$个元素为$\sum_j\widetilde{W}_{ij}$的对角阵，$\widetilde{W}$为：

$$\widetilde{W}_{i j}=\frac{W_{i j}}{2\left\|q^{i}-q^{j}\right\|_{2}} \tag{7}$$

那么$\mathcal{L}(Q)$对$Q$的偏导为零时，有：

$$\frac{\partial \mathcal{L}(Q)}{\partial Q}=\widetilde{L} Q-D Q \Lambda=\mathbf{0} \tag{8}$$

也就是说解$Q$为$D^{-1}\widetilde{L}$的特征值。注意到$D^{-1}\widetilde{L}$又依赖于$Q$，于是可以通过迭代来得到$Q$的局部最优解。

2.4 收敛性分析

引理1
对任意非零向量$q$，$q_t \in \mathcal{R}^c$，有：

$$\|q\|_{2}-\|q\|_{2}^{2} / 2\left\|q_{t}\right\|_{2} \leq\left\|q_{t}\right\|_{2}-\left\|q_{t}\right\|_{2}^{2} / 2\left\|q_{t}\right\|_{2} \tag{9}$$

我们需要利用引理1来证明算法可以收敛。

定理1
算法1会在每次迭代中单调地降低问题$(4)$的目标，并接近于问题的局部最优。

证明：

根据算法1的第二步，可知：

$$Q_{t+1}=\arg \min _{Q^{T} D Q=I} \sum_{i, j=1}^{n}(\widetilde{W}_{t})_{i j}\left\|q^{i}-q^{j}\right\|_{2}^{2} \tag{10}$$

又$\left(\widetilde{W}_{t}\right)_{i j}=\frac{W_{i j}}{2\left|q_{t}^{i}-q_{t}^{j}\right|_{2}}$，那么：

$$\sum_{i, j=1}^{n} \frac{W_{i j}\left\|q_{t+1}^{i}-q_{t+1}^{j}\right\|_{2}^{2}}{2\left\|q_{t}^{i}-q_{t}^{j}\right\|_{2}} \leq \sum_{i, j=1}^{n} \frac{W_{i j}\left\|q_{t}^{i}-q_{t}^{j}\right\|_{2}^{2}}{2\left\|q_{t}^{i}-q_{t}^{j}\right\|_{2}} \tag{11}$$

根据引理1，可得：

$$\begin{aligned} & \sum_{i, j=1}^{n} W_{i j}\left(\left\|q_{t+1}^{i}-q_{t+1}^{j}\right\|_{2}-\frac{\left\|q_{t+1}^{i}-q_{t+1}^{j}\right\|_{2}^{2}}{2\left\|q_{t}^{i}-q_{t}^{j}\right\|_{2}}\right) \\ & \leq \sum_{i, j=1}^{n} W_{i j}\left(\left\|q_{t}^{i}-q_{t}^{j}\right\|_{2}-\frac{\left\|q_{t}^{i}-q_{t}^{j}\right\|_{2}^{2}}{2\left\|q_{t}^{i}-q_{t}^{j}\right\|_{2}}\right) \end{aligned} \tag{12}$$

结合$(11)(12)$式，可得：

$$\sum_{i, j=1}^{n} W_{i j}\left\|q_{t+1}^{i}-q_{t+1}^{j}\right\|_{2} \leq \sum_{i, j=1}^{n} W_{i j}\left\|q_{t}^{i}-q_{t}^{j}\right\|_{2} \tag{13}$$

因此，算法1将在每次迭代$t$中单调地降低问题$(4)$的目标，直到算法收敛。当达到收敛时，$(13)$式等号成立，则$Q_t$和$\widetilde{L}_t$将满足$(8)$式，也就是问题$(4)$的$\text{KKT}$条件。定理1得证。

3 半监督框架

3.1 问题描述

设$Y=[\left(y^{1}\right)^{T},\left(y^{2}\right)^{T}, \cdots,\left(y^{n}\right)^{T}] \in \mathbb{R}^{n \times c}$为初始的标签矩阵。若$x_i$为无标签数据，则$y^i=0$。若$x_i$为$k$类，则$y^i$的第$k$个元素为1，否则为0。

传统的半监督学习需要解决的问题如下：

$$\min _{Q} \operatorname{Tr}\left(Q^{T} L Q\right)+\operatorname{Tr}(Q-Y)^{T} U(Q-Y) \tag{14}$$

其中$L$为拉普拉斯矩阵，$U$为控制$x_i$初始标签$y^i$的影响程度的对角阵（相当于超参），$Q \in \mathcal{R}^{n \times c}$为需要求解的标签矩阵。

类似的$(14)$式可写为：

$$\min _{Q} \sum_{i, j=1}^{n} W_{i j}\left\|q^{i}-q^{j}\right\|_{2}^{2}+\operatorname{Tr}(Q-Y)^{T} U(Q-Y) \tag{15}$$

为了得到最优解$Q$，我们需要解决以下半监督分类问题（注意这个用的是$\ell_1$范数）：

$$\min _{Q} \sum_{i, j=1}^{n} W_{i j}\left\|q^{i}-q^{j}\right\|_{2}+\operatorname{Tr}(Q-Y)^{T} U(Q-Y) \tag{16}$$

3.2 优化算法

$(16)$式对$Q$求偏导为零时有：

$$\widetilde{L} Q+U(Q-Y)=\mathbf{0} \Rightarrow Q=(\widetilde{L}+U)^{-1} U Y \tag{17}$$

3.3 收敛性分析

定理1
算法2会在每次迭代中单调地降低问题$(16)$的目标，并接近于问题的局部最优。

证明：

设$f(Q)=\operatorname{Tr}(Q-Y)^{T} U(Q-Y)$，据算法2的第二步可知：

$$Q_{t+1}=\arg \min _{Q} \sum_{i, j=1}^{n}\left(\tilde{W}_{t}\right)_{i j}\left\|q^{i}-q^{j}\right\|_{2}^{2}+f(Q) \tag{18}$$

注意到$(\tilde{W}_{t})_{i j}=\frac{W_{i j}}{2\left|q_{t}^{i}-q_{t}^{j}\right|_{2}}$，则：

$$\begin{aligned} & \sum_{i, j=1}^{n} \frac{W_{i j}\left\|q_{t+1}^{i}-q_{t+1}^{j}\right\|_{2}^{2}}{2\left\|q_{t}^{i}-q_{t}^{j}\right\|_{2}}+f\left(Q_{t+1}\right) \\ & \leq \sum_{i, j=1}^{n} \frac{W_{i j}\left\|q_{t}^{i}-q_{t}^{j}\right\|_{2}^{2}}{2\left\|q_{t}^{i}-q_{t}^{j}\right\|_{2}}+f\left(Q_{t}\right) \end{aligned} \tag{19}$$

将$(19)$式和$(12)$式两边求和，可得：

$$\begin{aligned} & \sum_{i, j=1}^{n} W_{i j}\left\|q_{t+1}^{i}-q_{t+1}^{j}\right\|_{2}+f\left(Q_{t+1}\right) \\ & \leq \sum_{i, j=1}^{n} W_{i j}\left\|q_{t}^{i}-q_{t}^{j}\right\|_{2}+f\left(Q_{t}\right) \end{aligned} \tag{20}$$

因此，算法2在每次迭代$t$中单调地降低问题$(16)$的目标，收敛时$Q_t$和$L_t$满足$(17)$式。由于问题$(16)$是一个凸优化问题，满足式$(17)$表明$Q_t$是问题$(16)$的全局最优解。因此，算法2收敛到问题$(16)$的全局最优。定理2得证。

4 思考

1. 本文模型简单来说就是在Normalized Cut谱聚类的基础上，将$\ell_2$范数约束项的平方等价为了一个$\ell_1$范数，目的是为了构造出一个与$Q$相关的$\widetilde{W}$，从而联系了$Q$和$L$并使得二者交替得以更新。相较于固定$L$的原始Normalized Cut算法来说，$L$的更新无疑带来了算法的提升。说穿了感觉就像是一个优化的小trick造就了一篇顶会。

2. 从直观层面谈一谈聚类算法：（TODO）

   • $K$-means。其一般采用欧氏距离所以只能局限于球形簇。距离度量的不确定性是算是聚类算法的通病。我们需要通过多次尝试，或者精细地分析所研究数据的特点来确定选取何种距离。$K$-means最大的问题是初始化过程对结果的影响非常大，对此有$K$-means++和二分$K$-means改进了初始化过程。而对噪点和异常值十分敏感的问题，出现了抛弃均值而转投中值怀抱的尝试（$K$-mediods）。

   • DESCAN。

   • 分层聚类。

   • 谱聚类。主要的两个问题，

   • 流形聚类。

   • 子空间聚类。