半监督支持向量机
预备知识
什么是半监督学习
- 有标记样本集合 \(\mathbb{D}_l = \{ (\vec{x}_1), y_1), \cdots, (\vec{x}_l, y_l) \}\)
- 未标记样本集合 \(\mathbb{D}_u = \{ (\vec{x}_{l + 1}), y_{l + 1}), \cdots, (\vec{x}_{l+u}, y_{l+u}) \}\)
- 其中 \(l << u\)
学习器自动地利用未标记的 \(\mathbb{D}_u\) 来提升学习性能,
这就是半监督学习(semi-supervised learning).
半监督学习假设
虽然未标记样本集合 \(\mathbb{D}_u\) 未包含标记数据, 但如果假设 \(\mathbb{D}_u\) 与 \(\mathbb{D}_l\) 从同样数据源独立同分布采样而来, 则 \(\mathbb{D}_u\) 所包含的数据分布有利于模型建立(参见
[1], 通过实验证明了如何利用无类标签的 样例帮助减轻休斯现象, 但若假设不成立, 则会降低模型效果).
从半监督学习最基本假设引申的 \(\mathbb{D}_u\) 与 \(\mathbb{D}_l\)
样本分布假设主要有三种[2]:
- 平滑假设(
Smoothness Assumption): 位于稠密数据区域的两个距离很近的样例的类标签相似(参见[3], 判定方法基于样本间是否存在高密度边). - 聚类假设(
Cluster Assumption): 两个样例位于同一聚类簇时,它们在很大的概率下有相同的类标签. 这个假设的等价定义为低密度分离假设. - 流形假设(
Manifold Assumption): 将高维数据嵌入到低维流形中, 当两个样例位于低维流形中的一个小局部邻域内时,它们具有相似的类标签.
流形假设可以看作是聚类假设的推广, 但流形假设对于输出值没有限制,因此比聚类假设的适用程度更广,可用于多类型的学习任务.
无论聚类假设还是流形假设,本质都假设是: 相似的样本有相似的输出.
半监督学习分类
- 归纳(
pure)半监督学习(Inductive semi-supervised Learning): 假定训练数据中的未标记样本并非仅为待预测的数据, 希望学得模型能适用于训练过程中未观察到的数据. - 直推学习(
Transductive Learning): 假定学习过程中所考虑的未标记样本恰是待预测数据, 学习的目的就是在这些未标记样本上获得最优泛化性能m仅试图对学习过程中观察到的未标记数据进行预测. 限定限制形式为Graph Learning.
支持向量机
支持向量机算法(support vector machine)是由弗拉基米尔·万普尼克和亚历克塞·泽范兰杰斯于1963年发明的.
学习资料见机器学习-白板推导系列-支持向量机
线性可分支持向量机
点 \((x_0, y_0)\) 到直线 \(Ax + By + C = 0\) 的距离为:
\[d = |\frac{A x_0 + B y_0 + C}{\sqrt{A^2 + B^2}}|\]
- 分离类别的超平面: \(w \cdot x + b = 0\)
- 点到超平面的距离: \(|w \cdot x + b|\)
- 分类正确度和确信度: \(y(w \cdot x +
b)\)
- 正确度: 基于点到直线位置关系(正类应当同时在直线的上方或下方)
- 确信度: 点与决策平面距离越远代表该分类的确信程度越高
- 函数间隔: \(\hat{\gamma}_i = y_i(w \cdot x_i + b)\)
- 几何间隔: \(\gamma_i = y_i(\frac{w}{||w||} \cdot x_i + \frac{b}{||w||})=\frac{\hat{\gamma}_i}{||w||}\)
若 \(w,b\) 成比例地改变(即超平面不变), 函数间隔也会按此比例改变, 几何间隔不变.
求解几何间隔最大的超平面
\[ \begin{matrix} \max_{w,b} & \gamma \\ s.t. & y(\frac{w}{\Vert w \Vert}\cdot x_i+\frac{b}{\Vert w \Vert}) \geq \gamma \end{matrix} \]
换成函数间隔
\[ \begin{matrix} \max_{w,b} & \frac{\hat\gamma}{\Vert w \Vert} \\ s.t. & y(\frac{w}{\Vert w\Vert}\cdot x_i+\frac{b}{\Vert w \Vert})\geq\frac{\hat\gamma}{\Vert w \Vert} \\ \longrightarrow & y(w \cdot x_i+b)\geq\hat\gamma \end{matrix} \]
函数间隔的取值不影响最优化问题的解, 因此取\(\hat{\gamma} = 1\)
\[ \begin{matrix} \max_{w,b} & \frac{1}{\Vert w \Vert}\\ s.t. & y(w\cdot x_i+b)\geq 1 \end{matrix} \]
等价形式(线性可分最终形式)
\[ \begin{matrix} \min_{w,b} & \frac{1}{2}{\Vert w\Vert}^2\\ s.t. & y(w\cdot x_i+b)-1\geq 0 \end{matrix} \]
若存在线性不可分的数据, 此时需要引入软间隔 \(\zeta_i\) (线性不可分最终形式)
\[ \begin{matrix} \min_{w,b} & \frac{1}{2}{\Vert w \Vert}^2 + C \sum_{i = 1}^N \zeta_i \\ s.t. & y(w\cdot x_i+b) \geq 1 - \zeta_i, \zeta_i \geq 0 \end{matrix} \]
这里 \(C\) 表示对误分类距离的惩罚系数
SVM 实际的损失函数等价于 合页损失函数(hinge loss) 与 L2
范数损失的和, 推导见[5]
\[ \sum_{i}^N \max( 1 - y_i(w \cdot x_i + b), 0) + \lambda \Vert w \Vert^2 \]
半监督支持向量机
半监督支持向量机
Semi-Supervised Support Vector Machine:S3VM是支持向量机在半监督学习上的推广. 基本假设是: 低密度分隔low-density separation.
\[ \begin{matrix} \min_{w,b} & \sum_{i = 1}^l \max( 1 - y_i(w \cdot x_i + b), 0) + \lambda_1 \Vert w \Vert^2 + \lambda_2 \sum_{i = l + 1}^{l+u} \max( 1 - y_i(w \cdot x_i + b), 0) \\ s.t. & \frac{1}{u}\sum_{j=l+1}^{l+u}{f(\mathbf+x_{j})}=\frac{1}{l}\sum_{i=1}^{l}{f(\mathbf+y_{i})} \end{matrix} \]
约束的引用在于逆转无标注样本可能的归属于同一类别的问题, 因此限制预测值中各个类的比例. 由于约束中存在类别约束, 导致整体目标函数是非凸的, 从而难以求解.
TSVM
半监督支持向量机中最著名的是
TSVM:Transductive Support Vector Machine.与标准
SVM 一样,TSVM
也是针对二分类问题的学习方法.
主要思想:
TSVM试图考虑对未标记样本进行各种可能的标记指派类别假设, 基于类别假设选取最优的超平面.
\[ \begin{matrix} \min_{w,b} & \frac{1}{2}{\Vert w \Vert}^2 + C_l \sum_{i = 1}^l \zeta_i + C_l \sum_{i = l + 1}^{l + u} \zeta_i \\ s.t. & \begin{cases} y_i(w\cdot x_i+b) \geq 1 - \zeta_i \\ \zeta_i \geq 0 \end{cases} \end{matrix} \]
- \(C_l, C_u\) 是由用户指定的用于平衡模型复杂度、有标记样本、未标记样本重要程度的折中参数.
TSVM 尝试未标记样本的各种标记指派是一个穷举过程,仅当未标记样本很少时才有可能直接求解.
S4VM
\[ \begin{matrix} \min_{w,b} & \sum_{t = 1}^T (\frac{1}{2}{\Vert w \Vert}^2 + C_l \sum_{i = 1}^l \zeta_i + C_l \sum_{i = l + 1}^{l + u} \zeta_i) + M \sum_{1 \leq t \ne \tilde{t} \leq T} I(\frac{\hat{y}^{'}_t \hat{y}_{\bar{t}}}{u} \geq 1 - \epsilon) \\ s.t. & \begin{cases} y_i(w\cdot x_i+b) \geq 1 - \zeta_i \\ \zeta_i \geq 0 \end{cases} \end{matrix} \]
注: 正则项用来保证不同超平面之间具有一定的差异性,如果两个超平面差异性越大,则预测相同的数目越小,则函数值越小,M为惩罚系数,M越大,则要求超平面的差异性越大.
半监督支持向量机在风控上的应用
支持向量数据描述(SVDD:Support Vector Domain Description)与1999年发表.
常用于异常值(奇异值)检测和极度不平衡数据的分类问题.
主要思想: 针对同一类有标记样本特性构建一个球面作为决策边界,判断剩下无标记样本属性,球内判定正样本,球外判定负样本.
- 异常值检测: 训练数据中含有离群点, 希望通过算法找到训练数据最集中的区域, 忽略偏差观测值.
- 奇异值检测: 训练数据中没有离群点, 目标使用训练好的模型去检测一个新的观测值是否有异常.该情况下, 离群点也成为奇异点.
\[ \begin{matrix} L(R, \vec{o}, \vec{\zeta}) = R^2 + C \sum_{i = 1}^N \zeta_i \\ s.t. \Vert \vec{x}_i - \vec{o} \Vert^2_2 \leq R^2 + \zeta_i \\ \zeta_i \geq 0 \\ i = 1, 2, \cdots, N \end{matrix} \]
其中 \(C > 0\) 为惩罚系数:
- 若 \(C\) 较大, 则不能容忍那些球面之外的点, 因此球面会较大.
- 若 \(C\) 较小, 则给予球面之外的点较大的弹性, 因此球面会较小.
参考资料
Shahshahani B M , Landgrebe D A . The effect of unlabeled samples in reducing the small sample size problem and mitigating the Hughes phenomenon[J]. IEEE Transactions on Geoscience and Remote Sensing, 1994, 32(5):P.1087-1095.- 百度百科-半监督学习
- 李宏毅机器学习-半监督学习章节
- 机器学习-白板推导系列-支持向量机
- 合页损失函数
- Towards Making Unlabeled Data Never Hurt