ch13 半监督学习

未标记样本

在生产活动中，有样本的数目会很少（因为标记很昂贵），从 LLM 的成功来看，在 unlabeled data 上训练模型是很有希望的。这种方法被称为半监督学习。

半监督学习又分为纯半监督学习和直推学习

• 纯半监督学习强调从 unlabeled data 中学习出一个好的模型
• 直推学习强调从 labeled data 中赋予 unlabeled data 一个标签，不强调模型是否存在，不在乎是否有泛化能力

而如果要使用 unlabeled data，需要一些假设

• 对于离散型数据，Cluster assumption：假设数据点在同一个 cluster 中的概率更大
• 对于连续型数据，Manifold assumption：假设数据点在低维流形上，流形上的点更有可能是同一个类别

生成式方法(GMM 再看看)

假设所有的数据都是由同一个潜在的模型生成的

类别标记\(y \in \mathcal{Y}\),其中\(\mathcal{Y} = \{1, 2, \cdots, N\}\)，假设样本由 GMM 生成，每一个类别对应一个高斯混合成份

\[p(x) = \sum_{i=1}^N \alpha_i p(x;\Theta_i) \]

于是令\(f(x)\)为预测标记

\[f(x) = \arg \max_{y \in \mathcal{Y}} p(y|x) = \arg \max_{y \in \mathcal{Y}} \sum_i^{N} p(y,\Theta=i|x) \\ = \arg \max_{y \in \mathcal{Y}} \sum_i^{N} p(y | \Theta=i, x) p(\Theta=i|x) \\ \]

我们可以得知

\[p(\Theta = i| x) = \frac{p(x|\Theta=i)p(\Theta=i)}{p(x)} = \frac{\alpha_i p(x;\Theta=i)}{\sum_{j=1}^N \alpha_j p(x;\Theta=j)} \]

而$p(y | \Theta=i, x) \(，类别标记对应一个混合成分，与\)x$ 无关，所以

\[p(y | \Theta=i, x) = p(y = j| \Theta=i) = 1, \text{if } j = i, 0 \quad \text{otherwise} \]

其中\(p(y = j| \Theta=i)\)表示在混合成分\(i\)中，类别标记为\(j\)的概率，需要标记，而\(p(\Theta=i|x)\)表示在\(x\)的条件下，混合成分为\(i\)的概率，不需要标记

于是我们可以得到极大似然估计

\[LL(D_l \cup D_u) = \sum_{(x, y) \in D_l} \log p(x,y) + \sum_{x \in D_u} \log p(x) \]

半监督 SVM

在无标记数据上，我们希望找到一个超平面，是分隔两类有标记数据的超平面，并尽可能通过低密度的区域，这是考虑了 Clustering Assumption

TSVM 尝试将每一个 unlabeled data 分配到两个类别中，然后求解一个 SVM，使得最终的超平面间隔最大化，unlabeled data 的指派结果即为最终的结果

\[\min_{w,b,\xi} \frac{1}{2} \| w \|^2 + C_l \sum_{i=1}^l \xi_i + C_u \sum_{i=1}^u \xi_i \\ \text{s.t.} \quad y_i(w^T x_i + b) \geq 1 - \xi_i, \quad i = 1, 2, \cdots, l \\ \hat{y_i}(w^T x_i + b) \geq 1 - \xi_i, \quad i = 1, 2, \cdots, u \\ \xi_i \geq 0, \quad i = 1, 2, \cdots, l, u \]

如果使用这样的穷举指派计算，复杂度会很高，因此需要使用另外一种方式，高效计算

利用 labeled data 训练 SVM，并逐步根据 unlabeled data 调整超平面，直到收敛

图半监督学习

给定一个数据集，我们可以将数据点之间的相似度表示为一个图，即相似度矩阵\(W\)，其中\(W_{ij}\)表示数据点\(i\)和\(j\)之间的相似度，直观认为，相似度高的点应该属于同一个类别

我们使用高斯核函数来计算相似度

\[W_{ij} = \begin{cases}\exp \left( - \frac{\| x_i - x_j \|^2}{2 \sigma^2} \right), \quad \text{if } i \neq j \\0, \quad \text{otherwise} \end{cases} \]

二分类标记传播

我们学习的目标是一个函数\(f: V \to \mathbb{R}\)，使得相似的点在\(f\)的值上也相似，定义一个能量函数，使得相似的点在\(f\)的值上也相似

\[E(f) = \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n W_{ij} (f(x_i) - f(x_j))^2 \\ = \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n W_{ij} f(x_i)^2 - 2 W_{ij} f(x_i) f(x_j) + W_{ij}f(x_j)^2 \\ = \frac{1}{2} ( \sum_{i=1}^n d_i f(x_i)^2 + \sum_{j=1}^n d_j f(x_j)^2 - 2 \sum_{i=1}^n \sum_{j=1}^n W_{ij} f(x_i) f(x_j) ) \]

由于\(W\)是对称矩阵，所以\(d_i = d_j\)，于是我们可以得到

\[E(f) = \sum_{i=1}^n d_i f(x_i)^2 - \sum_{i=1}^n \sum_{j=1}^n W_{ij} f(x_i) f(x_j) \\ = f^T (D - W) f \]

其中\(D\)是度矩阵，\(D_{ii} = \sum_{j=1}^n W_{ij}\)，\(f\)是标记函数，\(f_i = f(x_i)\)，\(W\)是相似度矩阵

为了满足能量函数最小化的条件，我们可以得到

\[(D - W) f = 0 \]

其中我们叫做拉普拉斯矩阵\(L = D - W\)，同时要满足在有标记数据上的约束条件\(f_i = y_i, i=1,2,\cdots,l\)

根据这样的假设，我们可以写出

\[E(f) = [f_l^T, f_u^T] ( \begin{bmatrix}D_{ll} & 0_{lu} \\0_{ul} & D_{uu} \end{bmatrix} - \begin{bmatrix}W_{ll} & W_{lu} \\W_{ul} & W_{uu} \end{bmatrix} ) \begin{bmatrix}f_l \\f_u \end{bmatrix} \]

对\(f_u\)求导，可得

\[f_u = (D_{uu} - W_{uu})^{-1} W_{ul} f_l \]

这就是针对二分类问题的一个标记传播算法，我们可以通过代入有标记数据，一次传播得出闭式解

多分类标记传播