【机器学习基础】系列博客为参考周志华老师的《机器学习》一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.图半监督学习
本章节没太理解，在此仅作记录，相关公式的详细推导可参考南瓜书PumpkinBook。
给定一个数据集，我们可将其映射为一个图，数据集中每个样本对应于图中一个结点，若两个样本之间的相似度很高（或相关性很强），则对应的结点之间存在一条边，边的“强度”（strength）正比于样本之间的相似度（或相关性）。我们可将有标记样本所对应的结点想象为染过色，而未标记样本所对应的结点尚未染色。于是，半监督学习就对应于“颜色”在图上扩散或传播的过程。由于一个图对应了一个矩阵，这就使得我们能基于矩阵运算来进行半监督学习算法的推导与分析。
给定$D_l = \{ (\mathbf{x}_1,y_1),(\mathbf{x}_2,y_2),\dots,(\mathbf{x}_l,y_l) \}$和$D_u = \{ \mathbf{x}_{l+1},\mathbf{x}_{l+2},\dots,\mathbf{x}_{l+u} \},l \ll u,l+u=m$。我们先基于$D_l \cup D_u$构建一个图$G=(V,E)$，其中结点集$V = \{ \mathbf{x}_1,…,\mathbf{x}_l,\mathbf{x}_{l+1},…,\mathbf{x}_{l+u} \}$，边集$E$可表示为一个亲和矩阵（affinity matrix），常基于高斯函数定义为：
\[(\mathbf{W})_{ij} = \begin{cases} \exp \left( \frac{-\|\mathbf{x}_i - \mathbf{x}_j\|_2^2}{2\sigma^2} \right), & \text{if } i \neq j; \\ 0, & \text{otherwise}. \end{cases} \tag{1}\]其中$i,j \in \{ 1,2,…,m \}$，$\sigma > 0$是用户指定的高斯函数带宽参数。
假定从图$G = (V,E)$将学得一个实值函数$f:V \to \mathbb{R}$，其对应的分类规则为：$y_i = \text{sign} (f(\mathbf{x}_i)),y_i \in \{-1,+1 \}$。直观上看，相似的样本应具有相似的标记，于是可定义关于$f$的“能量函数”（energy function）：
\[\begin{align*} E(f) &= \frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m (\mathbf{W})_{ij}(f(\mathbf{x}_i)-f(\mathbf{x}_j))^2 \\&= \frac{1}{2} \left( \sum_{i=1}^m d_i f^2 (\mathbf{x}_i) + \sum_{j=1}^m d_j f^2(\mathbf{x}_j) - 2\sum_{i=1}^m \sum_{j=1}^m (\mathbf{W})_{ij} f(\mathbf{x}_i) f(\mathbf{x}_j) \right) \\&= \sum_{i=1}^m d_i f^2(\mathbf{x}_i) - \sum_{i=1}^m \sum_{j=1}^m (\mathbf{W})_{ij} f(\mathbf{x}_i) f(\mathbf{x}_j) \\&= \mathbf{f}^T (\mathbf{D}-\mathbf{W}) \mathbf{f} \end{align*} \tag{2}\]能量函数最小化时即得到最优结果。
其中$\mathbf{f}=(\mathbf{f}_l^T \mathbf{f}_u^T)^T,\mathbf{f}_l = (f(\mathbf{x}_1);f(\mathbf{x}_2);…;f(\mathbf{x}_l)),\mathbf{f}_u = (f(\mathbf{x}_{l+1});f(\mathbf{x}_{l+2});…;f(\mathbf{x}_{l+u}))$分别为函数$f$在有标记样本与未标记样本上的预测结果，$\mathbf{D}=\text{diag}(d_1,d_2,…,d_{l+u})$是一个对角矩阵，其对角元素$d_i = \sum_{j=1}^{l+u}(\mathbf{W})_{ij}$为矩阵$\mathbf{W}$的第$i$行元素之和。
$\mathbf{W}$为对称矩阵，因此$d_i$亦为$\mathbf{W}$第$i$列元素之和。
具有最小能量的函数$f$在有标记样本上满足$f(\mathbf{x}_i)=y_i (i=1,2,…,l)$，在未标记样本上满足$\mathbf{\Delta f} = \mathbf{0}$，其中$\mathbf{\Delta} = \mathbf{D} - \mathbf{W}$为拉普拉斯矩阵（Laplacian matrix）。以第$l$行与第$l$列为界，采用分块矩阵表示方式：
\[\mathbf{W} = \begin{bmatrix} \mathbf{W}_{ll} & \mathbf{W}_{lu} \\ \mathbf{W}_{ul} & \mathbf{W}_{uu} \end{bmatrix}, \mathbf{D} = \begin{bmatrix} \mathbf{D}_{ll} & \mathbf{0}_{lu} \\ \mathbf{0}_{ul} & \mathbf{D}_{uu} \end{bmatrix}\]则式(2)可重写为：
\[\begin{align*} E(f) &= \begin{pmatrix} \mathbf{f}_l^T & \mathbf{f}_u^T \end{pmatrix} \left( \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} \right) \begin{bmatrix} \mathbf{f}_l \\ \mathbf{f}_u \end{bmatrix} \tag{3} \\&= \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 \tag{4} \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 \tag{5}\]令：
\[\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*} \tag{6}\]即$\mathbf{P}_{uu}=\mathbf{D}_{uu}^{-1}\mathbf{W}_{uu},\mathbf{P}_{ul}=\mathbf{D}_{uu}^{-1}\mathbf{W}_{ul}$，则式(5)可重写为：
\[\begin{align*} \mathbf{f}_u &= (\mathbf{D}_{uu}(\mathbf{I}-\mathbf{D}_{uu}^{-1}\mathbf{W}_{uu}))^{-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*} \tag{7}\]于是，将$D_l$上的标记信息作为$\mathbf{f}_l=(y_1;y_2;…;y_l)$代入式(7)，即可利用求得的$\mathbf{f}_u$对未标记样本进行预测。
上面描述的是一个针对二分类问题的标记传播（label propagation）方法，下面来看一个适用于多分类问题的标记传播方法。
假定$y_i \in \mathcal{Y}$，仍基于$D_l \cup D_u$构建一个图$G=(V,E)$，其中结点集$V = \{ \mathbf{x}_1,…,\mathbf{x}_l,…,\mathbf{x}_{l+u} \}$，边集$E$所对应的$\mathbf{W}$仍使用式(1)，对角矩阵$\mathbf{D}=\text{diag}(d_1,d_2,…,d_{l+u})$的对角元素$d_i = \sum_{j=1}^{l+u}(\mathbf{W})_{ij}$。定义一个$(l+u)\times \lvert \mathcal{Y} \rvert$的非负标记矩阵$\mathbf{F}=(\mathbf{F}_1^T,\mathbf{F}_2^T,…,\mathbf{F}_{l+u}^T)^T$，其第$i$行元素$\mathbf{F}_i=((\mathbf{F})_{i1},(\mathbf{F})_{i2},…,(\mathbf{F})_{i\lvert \mathcal{Y} \rvert})$为示例$\mathbf{x}_i$的标记向量，相应的分类规则为：$y_i = \text{argmax}_{1 \leqslant j \leqslant \lvert \mathcal{Y} \rvert}(\mathbf{F})_{ij}$。
对$i=1,2,…,m,j=1,2,…,\lvert \mathcal{Y} \rvert$，将$\mathbf{F}$初始化为：
\[\mathbf{F}(0)=(\mathbf{Y})_{ij} = \begin{cases} 1, & \text{if } (1 \leqslant i \leqslant l) \land (y_i = j); \\ 0, & \text{otherwise}. \end{cases} \tag{8}\]显然，$\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}}=\text{diag}(\frac{1}{\sqrt{d_1}},\frac{1}{\sqrt{d_2}},…,\frac{1}{\sqrt{d_{l+u}}})$，于是有迭代计算式：
\[\mathbf{F}(t+1)=\alpha \mathbf{SF}(t)+(1-\alpha)\mathbf{Y} \tag{9}\]其中$\alpha \in (0,1)$为用户指定的参数，用于对标记传播项$\mathbf{SF}(t)$与初始化项$\mathbf{Y}$的重要性进行折中。基于式(9)迭代至收敛可得：
\[\mathbf{F}^*=\lim _{t \mapsto \infty } \mathbf{F}(t) = (1-\alpha) (\mathbf{I}-\alpha\mathbf{S})^{-1}\mathbf{Y} \tag{10}\]由$\mathbf{F}^*$可获得$D_u$中样本的标记$(\hat{y}_{l+1},\hat{y}_{l+2},…,\hat{y}_{l+u})$。算法描述如图13.5所示。
事实上，图13.5的算法对应于正则化框架：
\[\min_{\mathbf{F}} \frac{1}{2} \left( \sum_{i,j=1}^{l+u} (\mathbf{W})_{ij} \left \| \frac{1}{\sqrt{d_i}}\mathbf{F}_i - \frac{1}{\sqrt{d_j}}\mathbf{F}_j \right \| ^2 \right) + \mu \sum_{i=1}^l \| \mathbf{F}_i - \mathbf{Y}_i \| ^2 \tag{11}\]其中$\mu > 0$为正则化参数。当$\mu = \frac{1-\alpha}{\alpha}$时，式(11)的最优解恰为图13.5算法的迭代收敛解$\mathbf{F}^*$。
式(11)右边第二项是迫使学得结果在有标记样本上的预测与真实标记尽可能相同，而第一项则迫使相近样本具有相似的标记，显然，它与式(2)都是基于半监督学习的基本假设，不同的是式(11)考虑离散的类别标记，而式(2)则是考虑输出连续值。
图半监督学习方法在概念上相当清晰，且易于通过对所涉矩阵运算的分析来探索算法性质。但此类算法的缺陷也相当明显。首先是在存储开销上，若样本数为$O(m)$，则算法中所涉及的矩阵规模为$O(m^2)$，这使得此类算法很难直接处理大规模数据；另一方面，由于构图过程仅能考虑训练样本集，难以判知新样本在图中的位置，因此，在接收到新样本时，或是将其加入原数据集对图进行重构并重新进行标记传播，或是需引入额外的预测机制，例如将$D_l$和经标记传播后得到标记的$D_u$合并作为训练集，另外训练一个学习器例如支持向量机来对新样本进行预测。
