图半监督学习

【概述】

给定一个数据集，可以将其映射为一个图，数据集中的每个样本对应于图中的一个结点，若两个样本间具有较高的相似度，则对应结点间存在一条边，边的强度正比于样本间的相似度

若将有标记的样本所对应的结点视为染色，未标记的样本所对应的结点视为尚未染色，则半监督学习就对应于颜色在图上扩散或传播的过程，由于一个图对应了一个矩阵，这就使得能够基于矩阵运算来进行半监督学习算法的推导和分析

图半监督学习方法在概念上相当清晰，且易于通过对所涉矩阵运算的分析来探索算法性质，但这类算法在存储开销上较大，难以直接处理大规模数据

此外，由于构图过程仅能考虑训练样本集，难以判知新样本在图中的位置，因此在接收到新样本时，通常将其加入原数据集对图进行重构并重新进行标记传播，或是引入额外的预测机制，另外训练一个学习器来对新样本进行预测

【二分类问题的标记传播方法】

标记传播方法（Label Propagation）是较为常用的图半监督学习方法，常用于二分类和多分类问题，对于二分类问题来说，对于给定有标记样本集 $D_l=\{(\mathbf{x}_1,y_1),(\mathbf{x}_2,y_2),\cdots,(\mathbf{x}_l,y_l)\}$ 和未标记样本集 $D_u=\{\mathbf{x}_{l+1},\mathbf{x}_{l+2},\cdots,\mathbf{x}_{l+u}\}$，其中 $l$ 和 $u$ 满足 $l\ll u,l+u=n$，标记 $y_i\in \{-1,1\}$

基于 $D_l\cup D_u$ 建立一个图 $G=(V,E)$，其中结点集 $V=\{\mathbf{x}_1,\mathbf{x}_2,\cdots,\mathbf{x}_l,\mathbf{x}_{l+1},\cdots,\mathbf{x}_{l+u}\}$，边集 $E$ 可表示为一个亲和矩阵（Affinity Matrix），其中的元素常基于高斯函数定义为：

$$w_{ij} = \left\{\begin{array}{cl} \exp\Big( \frac{-\Vert \mathbf{x}_i-\mathbf{x}_j \Vert_2^2}{2\sigma^2} \Big), & i\neq j \\ 0, & \text{otherwise} \end{array}\right.$$

其中，$i,j\in \{1,2,\cdots,n\}$，$\sigma>0$ 是用户指定的高斯函数带宽参数

假定从图 $G=(V,E)$ 中将要学得一个实值函数 $f:V\rightarrow \mathbb{R}$，其对应的分类规则为：

$$y_i=\text{sign}[f(\mathbf{x}_i)],\quad y_i\in \{-1,1\}$$

直观来看，相似的样本应具有相似的标记，于是可定义关于 $f$ 的能量函数：

$$\begin{align*} E(f) &= \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n w_{ij} \big(f(\mathbf{x}_i)-f(\mathbf{x}_j)\big)^2 \\ &= \frac{1}{2} \Big( \sum_{i=1}^n d_i f^2(\mathbf{x}_i) + \sum_{j=1}^nd_j f^2(\mathbf{x}_j) -2\sum_{i=1}^n\sum_{j=1}^n w_{ij}f(\mathbf{x}_i)f(\mathbf{x}_j) \Big) \\ &= \sum_{i=1}^n d_i f^2(\mathbf{x}_i) - \sum_{i=1}^n\sum_{j=1}^n w_{ij} f(\mathbf{x}_i)f(\mathbf{x}_j) \\ &= \mathbf{f}^T (\mathbf{D}-\mathbf{W})\mathbf{f} \end{align*}$$

其中，$\mathbf{f}=(\mathbf{f}_l^T\mathbf{f}_u^T)^T$，$\mathbf{f}_l=(f(\mathbf{x}_1),f(\mathbf{x}_2),\cdots,f(\mathbf{x}_l))$，$\mathbf{f}_u=(f(\mathbf{x}_{l+1});f(\mathbf{x}_{l+2});\cdots;f(\mathbf{x}_{l+u}))$ 分别为函数 $f$ 在有标记样本和未标记样本上的预测结果，$\mathbf{D}=\text{diag}(d_l,d_2,\cdots,d_{l+u})$ 是度数矩阵，其对角元素 $d_i=\sum\limits_{j=1}^{n} w_{ij}$ 为矩阵 $\mathbf{W}$ 的第 $i$ 行元素和

具有最小能量的函数 $f$ 在有标记样本上满足 $f(\mathbf{x}_i)=y_i,i=1,2,\cdots,l$，在未标记样本上满足 $\Delta \mathbf{f}=\mathbf{0}$，其中 $\Delta = \mathbf{D}-\mathbf{W}$ 为拉普拉斯矩阵

若以第 $l$ 行和第 $l$ 列为界，采用分块矩阵表示方式：

$$\mathbf{W}=\begin{bmatrix} \mathbf{W}_{ll} & \mathbf{W}_{lu} \\ \mathbf{W}_{ul} & \mathbf{W}_{uu} \end{bmatrix},\quad \mathbf{D}=\begin{bmatrix} \mathbf{D}_{ll} & \mathbf{0}_{lu} \\ \mathbf{0}_{ul} & \mathbf{D}_{uu} \end{bmatrix}$$

则上式可重写为：

$$\begin{align*} E(f) &= (\mathbf{f}_l^T\mathbf{f}_u^T) \Bigg( \begin{bmatrix} \mathbf{D}_{ll} & \mathbf{0}_{lu} \\ \mathbf{0}_{ul} & \mathbf{D}_{uu} \end{bmatrix} - \begin{bmatrix} \mathbf{W}_{ll} & \mathbf{W}_{lu} \\ \mathbf{W}_{ul} & \mathbf{W}_{uu} \end{bmatrix} \Bigg) \begin{bmatrix} \mathbf{f}_{l} \\ \mathbf{f}_{u} \end{bmatrix} \\ &= \mathbf{f}_{l}^T (\mathbf{D}_{ll}-\mathbf{W}_{ll})\mathbf{f}_l - 2\mathbf{f}_u^T\mathbf{W}_{ul}\mathbf{f}_l + \mathbf{f}_u^T(\mathbf{D}_{uu}-\mathbf{W}_{uu}) \mathbf{f}_u \end{align*}$$

由 $\frac{\partial E(f)}{\partial \mathbf{f}_u}=\mathbf{0}$ 可得：

$$\mathbf{f}_u = (\mathbf{D}_{uu}-\mathbf{W}_{uu})^{-1} \mathbf{W}_{ul} \mathbf{f}_l$$

令：

$$\begin{align*} \mathbf{P} &= \mathbf{D}^{-1} \mathbf{W} \\ &= \begin{bmatrix} \mathbf{D}_{ll}^{-1} & \mathbf{0}_{lu} \\ \mathbf{0}_{ul} & \mathbf{D}_{uu}^{-1} \end{bmatrix} \begin{bmatrix} \mathbf{W}_{ll} & \mathbf{W}_{lu} \\ \mathbf{W}_{ul} & \mathbf{W}_{uu} \end{bmatrix} \\ &=\begin{bmatrix} \mathbf{D}_{ll}^{-1}\mathbf{W}_{ll} & \mathbf{D}_{ll}^{-1}\mathbf{W}_{lu} \\ \mathbf{D}_{uu}^{-1}\mathbf{W}_{ul} & \mathbf{D}_{uu}^{-1}\mathbf{W}_{uu} \end{bmatrix} \end{align*}$$

即 $\mathbf{P}_{uu}=\mathbf{D}_{uu}^{-1}\mathbf{W}_{uu},\mathbf{P}_{ul}=\mathbf{D}_{uu}^{-1}\mathbf{W}_{ul}$，此时，对于 $\mathbf{f}_u$ 有：

$$\begin{align*} \mathbf{f}_u &= \big( \mathbf{D}_{uu}(\mathbf{I}-\mathbf{D}_{uu}^{-1}\mathbf{W}_{uu}) \big)^{-1}\mathbf{W}_{ul}\mathbf{f}_l \\ &= (\mathbf{I}-\mathbf{D}_{uu}^{-1}\mathbf{W}_{uu})^{-1} \mathbf{D}_{uu}^{-1} \mathbf{W}_{ul} \mathbf{f}_l \\ &= (\mathbf{I}-\mathbf{P}_{uu})^{-1} \mathbf{P}_{ul} \mathbf{f}_l \end{align*}$$

于是，将 $D_l$ 上的标记信息作为 $\mathbf{f}_l=(y_1;y_2;\cdots;y_l)$ 代入上式，即可利用求得 $\mathbf{f}_u$ 的对未标记样本进行预测

【多分类问题的标记传播方法】

标记传播方法（Label Propagation）是较为常用的图半监督学习方法，常用于二分类和多分类问题，对于多分类问题来说，对于给定有标记样本集 $D_l=\{(\mathbf{x}_1,y_1),(\mathbf{x}_2,y_2),\cdots,(\mathbf{x}_l,y_l)\}$ 和未标记样本集 $D_u=\{\mathbf{x}_{l+1},\mathbf{x}_{l+2},\cdots,\mathbf{x}_{l+u}\}$，其中 $l$ 和 $u$ 满足 $l\ll u,l+u=n$，标记 $y_i\in \mathcal{Y}$

仍基于 $D_l\cup D_u$ 建立一个图 $G=(V,E)$，其中结点集 $V=\{\mathbf{x}_1,\mathbf{x}_2,\cdots,\mathbf{x}_l,\mathbf{x}_{l+1},\cdots,\mathbf{x}_{l+u}\}$，边集 $E$ 所对应的亲和矩阵中的元素仍基于高斯函数定义，即：

$$w_{ij} = \left\{\begin{array}{cl} \exp\Big( \frac{-\Vert \mathbf{x}_i-\mathbf{x}_j \Vert_2^2}{2\sigma^2} \Big), & i\neq j \\ 0, & \text{otherwise} \end{array}\right.$$

度数矩阵 $\mathbf{D}=\text{diag}(d_l,d_2,\cdots,d_{l+u})$ 其对角元素 $d_i=\sum\limits_{j=1}^{n} w_{ij}$ 为矩阵 $\mathbf{W}$ 的第 $i$ 行元素和

定义一个 $n\times |\mathcal{Y}|$ 的非负标记矩阵 $\mathbf{F}=(\mathbf{F}_1^{T},\mathbf{F}_2^{T},\cdots,\mathbf{F}_{l+u}^{T})^T$，其第 $i$ 行元素 $\mathbf{F}_i=(\mathbf{F}_{i1},\mathbf{F}_{i2},\cdots,\mathbf{F}_{i|\mathcal{Y}|})$ 为样本 $\mathbf{x}_i$ 的标记向量，相应的分类规则为：

$$y_i=\arg \max_{1\leq j\leq |\mathcal{Y}|} \mathbf{F}_{ij},\quad y_i\in \mathcal{Y}$$

对于 $i=1,2,\cdots,n,j=1,2,\cdots,|\mathcal{Y}|$，将 $\mathbf{F}$ 初始化为：

$$\mathbf{F}(0)=\mathbf{Y}_{ij} = \left\{\begin{array}{cl} 1, & (1\leq i\leq l) \wedge (y_i=j) \\ 0, & \text{otherwise} \end{array}\right.$$

显然，$\mathbf{Y}$ 的前 $l$ 行就是 $l$ 个有标记样本的标记向量

基于 $\mathbf{W}$ 构造一个标记传播矩阵：

$$\mathbf{S} = \mathbf{D}^{-\frac{1}{2}} \mathbf{W} \mathbf{D}^{-\frac{1}{2}}$$

其中，对于 $\mathbf{D}^{-\frac{1}{2}}$，有：

$$\mathbf{D}^{-\frac{1}{2}}=\text{diag}\Big( \frac{1}{\sqrt{d_1}},\frac{1}{\sqrt{d_2}},\cdots,\frac{1}{\sqrt{d_{l+u}}} \Big)$$

于是，有迭代式：

$$\mathbf{F}(t+1) = \alpha \mathbf{S}\mathbf{F}(t) + (1-\alpha) \mathbf{Y}$$

其中，$\alpha\in(0,1)$ 为用户指定的参数，用于对标记传播项 $\mathbf{S}\mathbf{F}(t)$ 与初始化项 $\mathbf{Y}$ 的重要性进行折中

对于上式，迭代至收敛，有：

$$\mathbf{F}^* = \lim_{t\rightarrow \infty} \mathbf{F}(t) = (1-\alpha)(\mathbf{I}-\alpha \mathbf{S})^{-1}\mathbf{Y}$$

由 $\mathbf{F}^*$ 即可得未标记样本集 $D_u$ 中样本的标记 $(\hat{y}_{l+1},\hat{y}_{l+2},\cdots,\hat{y}_{l+u})$