本文是关于周志华老师编写的机器学习书籍『西瓜书』的第六章支持向量机.
主要的内容有: 支持向量机的模型理解、支持向量、硬间隔与软间隔、在不等式约束下使用拉格朗日乘子法转化为对偶问题、KKT条件、支持向量回归等.
6.1 间隔与支持向量
面对二分类问题, 最基本的想法是基于训练集, 在样本空间中找到一个合适的划分超平面, 从而将样本划分为两类. 但是划分超平面有很多, 选择最合适的超平面就是我们接下来要解决的问题了.
所谓『最合适』就是指: 不仅在训练集中表现良好, 更要在新的测试集中表现良好, 即泛化性能最好. 那么最直观的就行找到「正中间」的那个超平面.
首先使用线性方程来描述一下超平面:
\[ \boldsymbol{w}^T\boldsymbol{x} + b = 0 \tag{1} \]
其中\(\boldsymbol{w}\)为法向量, 决定平面的方向, \(d\)是位移项, 决定偏移原点的距离.
若样本点在超平面上侧, 即\(\boldsymbol{w}^T\boldsymbol{x} + b > 0\), 那么\(x_i\)为正样本, 记为\(y_i=1\), 反之为负样本, 记为\(y_i=-1\).
若超平面能够正确分类, 那么使用一个sign函数将会得到模型:
\[ y = sign(\boldsymbol{w}^T\boldsymbol{x}_i + b) = \begin{cases} +1, \quad \boldsymbol{w}^T\boldsymbol{x}_i + b \geq +1; \\ -1, \quad \boldsymbol{w}^T\boldsymbol{x}_i + b \leq -1; \tag{2} \end{cases} \]
后面的\(\pm1\)是\((\boldsymbol{w}, b)\)变换过的, 因为任意\(\boldsymbol{w}^T\boldsymbol{x}_i + b \geq c\)可以变化为\(\frac{1}{c}\boldsymbol{w}^T\boldsymbol{x}_i + \frac{b}{c} \geq 1\). 此处的变换仅仅是「常规操作」, 也可以取其他值, 主要目的是使得后续的最优化问题有约束可解. 其中\(c\)即为下面所说的「最近距离」.
注意到公式\((2)\)中的等号, 当且仅当某些样本点距离超平面最近时取得, 称为『支持向量』(support vector)!. 那么, 两侧异类样本点距离超平面的最近距离相同时, 是不是就是最合适的划分呀!
接下来计算样本\(\boldsymbol{x}\)距离超平面的距离计算为:
\[ \gamma = \frac{y_i(\boldsymbol{w}^T\boldsymbol{x} + b)}{\|\boldsymbol{w}\|} \tag{3} \]
那么左右两侧最近的「异类点」到达超平面的距离之和为:
\[ \gamma = \frac{2}{\|\boldsymbol{w}\|} \tag{4} \]
这距离之和就称为『间隔』(margin) !
那么我们的问题就是去寻找最大的间隔\(\frac{2}{\|\boldsymbol{w}\|}\), 使得泛化误差最小, 也等价于寻找最小的\(\|\boldsymbol{w}\|^2\), 问题就转化为:
\[ \begin{aligned} \min_{(\boldsymbol{w}, b)} &\quad{\frac{1}{2}\|\boldsymbol{w}\|^2} \\ s.t &\quad 1-y_i(\boldsymbol{w}^T\boldsymbol{x} + b) \leq 0, \quad i = 1,2,\dots, m. \tag{5} \end{aligned} \]
凸优化的问题一般将优化函数转化为最小值, 约束条件转化为小于等于的形式.
6.2 对偶问题
以上的问题我们可以使用拉格朗日乘子法得到『对偶问题』的拉格朗日函数:
\[ L(\boldsymbol{w}, b, \boldsymbol{\alpha}) = \frac{1}{2}\|\boldsymbol{w}\|^2 + \sum^m_{i=1}\alpha_i{(1-y_i(\boldsymbol{w}^T\boldsymbol{x}_i + b))} \tag{6} \]
并对上式对\(\boldsymbol{w}\)和\(b\)求偏导为\(0\)可得:
\[ \begin{aligned} \boldsymbol{w} &= \sum^m_{i=1}{\alpha_i y_i\boldsymbol{x}_i} \\ 0 &= \sum^m_{i=1}{\alpha_i y_i} \end{aligned} \tag{7} \]
将求得的结果带入拉格朗日函数中, 就可以得到对偶问题:
\[ \begin{aligned} \max_{\boldsymbol{\alpha}} &\quad {\sum^m_{i=1}{\alpha_i}-\frac{1}{2}\sum^m_{i=1}{\sum^m_{j=1}{\alpha_i \alpha_j y_i y_j\boldsymbol{x}_i^T\boldsymbol{x}_j}}} \\ s.t. &\quad\sum^m_{i=1}{\alpha_i y_i} = 0 \end{aligned} \tag{8} \]
那么模型就转化为求解\(\boldsymbol{\alpha}\), 而\(\boldsymbol{\alpha}\)是拉格朗日乘子, 与不等式约束条件个数有关, 即与样本个数成正比. 而我们原本的模型是求出\(\boldsymbol{w}\), 其实也是可以直接优化的, 但是\(\boldsymbol{w}\)表示模型的特征, 所以原模型与样本的特征数成正比.
所以当我们遇到样本数较少, 而特征数较多的情况下可以选择使用对偶问题进行求解. 所以支持向量机在小样本中使用效果相对较好.
KKT条件
在上述的过程中, 我们使用了拉格朗日乘子法, 但是在这里我介绍过, 拉格朗日乘子法是针对等式约束的, 如果是不等式约束, 则需要满足KKT条件, 这里是:
\[ \begin{cases} \alpha_i \geq 0; \\ 1-y_i(\boldsymbol{w}^T\boldsymbol{x}_i + b) \leq 0; \\ \alpha_i(1-y_i(\boldsymbol{w}^T\boldsymbol{x}_i + b)) = 0. \end{cases} \]
⚠在这里可以发现很重要的结论:
- 由第三个条件可以推出, 要么\(\alpha_i = 0\), 要么\(y_if(\boldsymbol{x}_i) = 1\)!
- 若\(\alpha_i = 0\), 那么该样本点不对模型产生影响;
- 若\(y_if(\boldsymbol{x}_i) = 1\), 也就是等式约束, 那么该样本点在最大间隔边界上!, 此处的样本就是支持向量!
也就是说, 我们的模型仅仅与支持向量有关, 这也是为什么叫做支持向量机的原因.
SMO算法
- todo 至于求解的SMO算法以及核函数/核方法之类的后续再补.
6.3 核函数
- todo
6.4 软间隔
在上述的内容中, 我们要求样本严格可分, 来得到一个『间隔』使得样本分开, 这个间隔称为"硬间隔"(hard margin). 但是在实际的情况中, 有很多样本并不是严格线性可分, 可能存在部分(少量)的『出错点』.
所以我们需要寻找一个允许存在误差的间隔, 称之为"软间隔"(soft margin). 当然, 存在的误差要尽可能的少, 所以我们在优化目标上增加『损失函数』, 使得不满足约束的, 赋予一定损失, 满足约束的没有损失:
\[ \min_{(\boldsymbol{w}, b)} {\frac{1}{2}\|\boldsymbol{w}\|^2} + C\sum^m_{i=1}\ell_{0/1}(y_i(\boldsymbol{w}^T\boldsymbol{x}_i + b)-1) \tag{9} \]
其中\(C\)是一个常数, 若定义\(C\)很大, 则对损失要求严格, 反之则越宽松. \(\ell_{0/1}\)则代表『0/1损失函数』, 但是非凸, 非连续, 数学性质不好, 所以常使用『hinge(合页)损失』.
那么损失函数变成
\[ \min_{(\boldsymbol{w}, b)} {\frac{1}{2}\|\boldsymbol{w}\|^2} + C\sum^m_{i=1}{\max{(0, 1-y_i(\boldsymbol{w}^T\boldsymbol{x}_i + b))}} \tag{10} \]
还有常见的指数损失和对率损失等.
引入松弛变量(slack variable)\(\xi_i\), 那么可以重写为
\[ \begin{aligned} \min_{(\boldsymbol{w}, b)} &\quad{\frac{1}{2}\|\boldsymbol{w}\|^2} + C\sum^m_{i=1}{\xi_i} \\ s.t. &\quad 1-y_i(\boldsymbol{w}^T\boldsymbol{x} + b) \leq \xi_i \\ &\quad \xi_i \geq 0, i = 1,2,\dots, m. \tag{11} \end{aligned} \]
这就是常见的软间隔支持向量机.
故意化简为上述形式, 那么就可以和普通支持向量机一样使用拉格朗日函数化为对偶问题再进行求解.
6.5 支持向量回归
之前提到过的线性回归模型, 是学习得到一条线\(f(x)\), 而将支持向量运用于回归的问题上, 是学习得到一条「间隔带」\(f(x)\pm\epsilon\).
为了类似支持向量的分类模型, 写出如下形式:
\[ \min_{(\boldsymbol{w}, b)} {\frac{1}{2}\|\boldsymbol{w}\|^2} + C\sum^m_{i=1}\ell_{\epsilon}(f(\boldsymbol{x}_i)-y_i) \tag{12} \]
其中\(C\)为正则化尝试, \(\ell_{\epsilon}\)是\(\epsilon\)-不敏感损失函数
\[ \ell_{\epsilon}(z) = \begin{cases} 0, &if |z| \leq \epsilon; \\ |z| - \epsilon, & otherwise. \end{cases} \]
模仿软间隔支持向量机的形式, 再引入松弛变量\(\xi_i\)和\(\hat{\xi}_i\), 两个松弛变量的原因是正负两侧的松弛程度可以不一样, 从而重写为:
\[ \begin{aligned} \min_{(\boldsymbol{w}, b, \xi_i, \hat{\xi}_i)} &\quad{\frac{1}{2}\|\boldsymbol{w}\|^2} + C\sum^m_{i=1}{(\xi_i + \hat{\xi}_i)} \\ s.t. &\quad f(\boldsymbol{x}_i) - y_i \leq \xi_i + \epsilon \\ &\quad y_i - f(\boldsymbol{x}_i) \leq \hat{\xi}_i + \epsilon \\ &\quad \xi_i \geq 0, \hat{\xi_i} \geq 0, i = 1,2,\dots, m. \tag{11} \end{aligned} \]
又是类似的优化形式, 同样使用拉格朗日函数转化后求解.
6.6 核方法
- todo
个人收获
首先这一章对我来说是比较困难的, 主要是有些地方懵懵懂懂, 需要花一定的时间来消化.
- 这次对拉格朗日函数有了更进一步的理解!, 终于明白为什么之前说拉格朗日乘子法只能用于等式约束, 而这里可以用于不等式约束, 原来是KKT条件的作用.
- 之前两次都是看到KKT条件然后放弃, 因为不理解这几个条件是干什么的, 这次终于明白了, 是增加约束, 使得不等式项消失, 而保留等式, 从而满足拉格朗日乘子法的使用条件, 也是因此获得支持向量.
- 软间隔这次也明白了, 是为了容错, 从而增加了松弛变量, 变化为相同形式求解.
- 关于支持向量回归这里, 我倒是感觉意义不大(不是), 所以没有太深入理解.
- 在拉格朗日乘子法这里还有一个对偶函数, 听的有些懵懵的, 后续再进一步整理这个理论.