机器学习笔记（10）：支持向量机

本文来自之前在Udacity上自学机器学习的系列笔记。这是第10篇，介绍了监督学习中的支持向量机。

支持向量机
支持向量机是一种分类模型，它是在给定的有两个类别的数据集下，寻找一条分割线（称为“超平面”）将数据集正确地分成两类。

比如说下图中的两个类别数据，分别有三条分割线，将数据分隔开来。

image.png

你觉得哪一条直线是最佳分割线呢？这里我们得先定义怎么样才是“最佳”。为此，我们认为，一条最佳分割线除了正确分类数据外，还应该最大化这条分割线到两边最近的数据点所在的平行线的距离。我们把这段距离叫做“Margin”。除了分类正确，还在最大化“Margin”。

支持向量机的模型推导
下图有正样本和负样本两类数据点。我们希望找到中间那条黄色的分隔线，同时它与两类样本的最近邻点所在的平行线距离最大化。

image.png

如图所示，我们把这些点看成是二维坐标下的向量，那么两个向量的点积就是一个向量到另一个向量的投影长度。

假设 $\vec w$ 是垂直于黄线的向量，我们要判断给定的任意一点 $\vec u$ 是正还是负，我们可以根据这个条件来判断，即 $\vec w \centerdot \vec u \geq C$ ，它表示什么意思呢？它的意思是，如果两者的点积大于等于某个值 $C$ ，则判断为正；否则为负。向量的点积有实际的含义，它表示其中一个向量在另外一个向量的投影的长度。所以，大于 $C$ 说明在分隔线之上，为正样本；小于 $C$ 说明在分隔线之下，为负样本。

因此，决策规则表示为
$\vec w \centerdot \vec u + b \geq 0, \quad y=1$ ， $(b=-C)$

假设 $\vec x$ 是正样本，则 $\vec w \centerdot \vec x_+ + b \geq 1$
假设 $\vec x$ 是负样本，则 $\vec w \centerdot \vec x_- + b \leq -1$

设定 $y_i=1$ ，当 $\vec x$ 为正样本时；否则 $y_i=-1$

从而可以得到
$y_i(\vec w \centerdot \vec x_i + b) \geq 1$

决策规则变换为，对于所有训练集 $i$
$y_i(\vec w \centerdot \vec x_i + b) -1 \geq 0$

从而，上图中的“Margin”的宽度就等于
$Margin = (\vec x_+ - \vec x_-) \centerdot \frac{\vec w}{\left \| \vec w \right \|}$

问题就转换为求解 $max \frac{1}{\left \| \vec w \right \|}$ 的问题，也是 $min \frac{1}{2} \left \| \vec w \right \|^2$ 的问题。

综上，这是一个在约束条件下多元函数求极值的问题，可以使用拉格朗日乘数法来解决。
约束条件也就是上面提到的决策规则，对于所有训练集 $i$
$y_i(\vec w \centerdot \vec x_i + b) -1 \geq 0$

构造以下的函数
$L=\frac{1}{2} \left \| \vec w \right \|^2 - \sum \alpha_i [y_i(\vec w \centerdot \vec x_i + b)-1]$

其中， $\alpha \geq 0$ ，函数对 $\vec w$ 求导，可得

$\frac {\partial L}{\partial \vec w} = \vec w - \sum \alpha_i y_i x_i = 0$

所以

$\vec w = \sum \alpha_i y_i x_i$

函数对 $b$ 求导，可得

$\frac {\partial L}{\partial b} = - \sum \alpha_i y_i = 0$
所以
$\sum \alpha_i y_i = 0$

将上式中的 $\vec w$ 和 $b$ 分别带回函数 $L$ 和决策规则，经过推导可以得到
$L=\sum \alpha_i - \frac {1}{2} \sum_i \sum_j \alpha_i \alpha_j y_i y_j \vec x_i \centerdot \vec x_j$

如果 $\sum \alpha_i y_i \vec x_i \centerdot \vec u + b \geq 0$ ，那么 $\vec u$ 为正样本。

到了这一步后，我们已经得到 $L$ 式，根据拉格朗日对偶性，接下来的问题就是求解 $max_\alpha L$ 的问题（完整地，应该就是 $max_\alpha min_{\vec w, b} L(\vec w, b, \alpha)$ 问题）。其中 $\sum \alpha_i y_i = 0$ 是约束条件。该问题可以使用数值分析中的SMO（Sequential Minimal Optimization）算法进行求解。

在得到 $\alpha$ 的值之后，就可以求解 $\vec w$ 和 $b$ 了（求解 $b$ 还需要再推导一番）。

解读
上面得出的 $L$ 式，在实际运用时有个特点，就是大部分的 $\alpha$ 是为0的。它是通过对整体样本判断后得出哪些 $\alpha$ 为0，哪些不为0。这说明在决策时真正有影响力的数据点是靠近决策边界的点，而那些远离决策边界的点，影响不大。

$L$ 式中的 $\alpha_i \alpha_j$ 告诉我们找出所有的点对，弄清楚哪些点是重要的，能够影响决策边界的定义的点对。然后 $y_i y_j$ 则告诉我们，从这些点对的输出的角度出发，它们是如何彼此相关，以及考虑它们之间的相似程度。

另外，从 $L$ 式可以看出，其结果只取决于 $x_i \centerdot x_j$ ，所以对于不能使用一条直线直观地分隔开数据的情况，我们可以构造函数 $\phi(x^Ty)=\phi(x)^T\phi(y)$ 来对数据进行转换，实现线性可分。我们称其为核函数，它表示了数据之间的一种相似性。核函数也是我们将域知识（Domain Knowledge）引入到SVM的机制。

常用的核函数有

$K=(x^Ty+c)^p$
$K=e^{-(\frac {\left \| x - y \right \|^2}{2\sigma^2})}$
$K=tanh(\alpha x^Ty+\theta)$

参考sklearn：
https://scikit-learn.org/stable/modules/svm.html#svm

机器学习笔记（10）：支持向量机

推荐阅读更多精彩内容