0%

从支持向量机到结构化输出预测

支持向量机

边距的表示

即 $SVM$ 的学习过程归结为寻找合适的 $w$ 和 $b$ 使边距 $M$ 最大化

  • 若所有的训练数据都在正确的分类区域,则有 $y_i(\langle w,x_i \rangle+b)≥1 $,其中 $y_i \in \lbrace +1,−1 \rbrace $
  • $ max \frac 2 {\sqrt{\langle w,w \rangle}} \Leftrightarrow min ||w||^2 $

即 $SVM$ 的优化问题可以表示为:

$(\langle w,x_i \rangle+b)$ 应当是一个绝对值大于等于 $1$ 的值,约束条件就意味着所有点均位于正边距和负边距之上或之外

软边距SVM

原问题的对偶问题

推导:

原问题的拉格朗日函数:
$$ L(w, b, \xi, \mu, a) = \frac 1 2 ||w||^2 + C \sum_{i=1}^n \xi_i - \sum_{i=1}^n a_i(y_i(w·x_i+b)-1+\xi_i)-\sum_{i=1}^n\mu_i \xi_i$$

显然:
$$ \frac 1 2 ||w||^2 ≥ L(w, b, \xi, \mu, a) ≥ \mathop{inf} \limits_{w,b} L(w, b, \xi, \mu, a)$$

对偶问题是拉格朗日函数的极大极小问题,首先求 $L(w, b, \xi, \mu, a)$ 对 $w, b, \xi$ 的极小值,由:
$$ \nabla_w L(w, b, \xi, \mu, a) = w - \sum_{i=1}^n a_iy_ix_i = 0 $$$$ \nabla_b L(w, b, \xi, \mu, a) = - \sum_{i=1}^n a_iy_i = 0 $$$$\nabla_{\xi} L(w, b, \xi, \mu, a) = C - a_i - \mu_i = 0 $$
得:
$$ w = \sum_{i=1}^n a_iy_ix_i $$$$ \sum_{i=1}^n a_iy_i = 0 $$$$ C - a_i - \mu_i = 0 $$

原式可化为:
$$ L(w, b, \xi, \mu, a) = \frac 1 2 ||w||^2 + \sum_{i=1}^n \xi_i (C - a_i - \mu_i) - \sum_{i=1}^n a_iy_i(w·x_i+b) + \sum_{i=1}^n a_i $$

代入易得:
$$ L(w, b, \xi, \mu, a) =\sum_{i=1}^n a_i - \frac 1 2 \sum_{i=1}^n\sum_{j=1}^n a_ia_jy_iy_j \langle x_i, x_j\rangle $$

对拉格朗日乘子有以下约束:
$$ \sum_{i=1}^n a_iy_i = 0 $$$$ C ≥ a_i ≥ 0 $$

求解对偶问题

据此学习到的分类函数为

损失函数

损失函数的定义

SVM的损失函数

结构化输出预测

结构化输出问题描述

其简单做法就是将简化为更加细粒度的分类问题,即多个分类问题:

结构化输出预测模型


结构化感知机

结构化SVM

基本思路

具体实现

注:负例并不会出现在正边距及其方向上,因为要保证正确样本的得分值比错误样本的得分值高。

转化成差值后的形式,类似于 $RankingSVM$

对于上图,正确样本的误差为 $0$,其位置应该位于分类面上,即垂直于 $w$ 的过原点的直线,这也就是与原图相比转换成差值后增加了坐标轴的原因。

软边距及变边距SVM-Struct

和软边距$SVM$、变边距$SVM$和 $SVM$ 的区别一样,只是对边距表示的调整。

软边距 SVM-Struct

变边距 SVM-Struct

参考文献:
[1] 徐君,《网络数据挖掘》,中国科学院大学2017年秋季研究生课程
[2] 卜东波,《计算机算法设计与分析》,中国科学院大学2017年秋季研究生课程
[3] 李航,《统计学习方法》,清华大学出版社