支持向量机
由ypyu创建，最终由ypyu 被浏览 29 用户
在本文中，我将介绍机器学习中关于传统机器学习中几乎最为强大的方法——支持向量机。
因为知乎中对于markdown的支持太差了，本文不在知乎直接排版，所以阅读体验不是很好，若想获得更好的阅读体验，请点击下文链接进行阅读。
所有的文章都会在我的博客和我的知乎专栏同步进行更新，欢迎阅读
下面是正文：
概念引入
支持向量机（support vector machine 简称 SVM）是我一直想写但是没写的内容，它的数学推导较为复杂，理论意义没有之前线性回归、决策树那样明显，但却是传统机器学习中几乎最为强大的方法。
支持向量机这个名字听起来较为奇怪，但是他却有深层次的含义，在之后会详细介绍。
如图所示，如果我们要进行一个分类的学习任务，将图中两种类别的样本分开，需要学习一个超平面，结果可能如$H_1,H_2,H_3$所示，如果仅仅以训练集来看三个分类器，他们没有任何差别，都是100%准确率，但从直觉上来看，位于中间的$H_3$似乎是最好的，因为它和任何样本的距离都比较远，其鲁棒性最强。
鲁棒是Robust的音译，也就是健壮和强壮的意思。它是在异常和危险情况下系统生存的关键。比如说，计算机软件在输入错误、磁盘故障、网络过载或有意攻击情况下，能否不死机、不崩溃，就是该软件的鲁棒性。
支持向量机的任务就是找到一个位于正中间的超平面，使之与任何样本之间都有较大间隔，以提高算法鲁棒性，所以又被称为最大间隔分类器。
目标
尽管SVM的概念较为复杂，但是SVM的推导对于其理解还是有重要作用的，下面我们一步一步进行推导。
我们知道，任何空间中的超平面都可以由以下方程代表：$\vec w^T \vec x + b=0$所以一个样本点x（它在样本空间中的坐标由其各个属性决定）距离该超平面的距离为：$r = \frac {|\vec w^T \vec x + b|} {||\vec w||}\\(该公式和高中点到直线公式相同)$对于一般的分类器（非SVM），我们要求在$y=1（标记为正）时，\vec w^T \vec x + b > 0，y=-1时，\vec w^T \vec x + b < 0 $，但是对于SVM，我们有更强的要求，即：$\begin{cases}\vec w^T \vec x + b \ge 1&y=1\\\vec w^T \vec x + b \le -1&y=-1\end{cases}$可以看出，SVM对算法预测的要求比一般的学习器要高，如果我们把上述两个式子看做个超平面，如下图所示，图中的红蓝两条线，SVM的要求就是，使所有的样本都出现在红蓝两条线之外，并且两条线的间隔要尽可能大，这也就是“最大间隔分类器”名称的由来。
图中两条线的间隔为：$d=\frac {2} {||\vec w||}$我们的目标正是最大化该式，max{d}。
数学推导
由上可知，我们的目标是：由上可知，我们的目标是：$max_{w,b} \; d=\frac {2} {||\vec w||}\\st \; y_i(\vec w^T \vec x_i + b) \ge 1\\(将SVM的要求两式合成一式)$实际上等价于最大化w：$min_{w,b} \; \frac 12 {||\vec w||^2}\\st \; y_i(\vec w^T \vec x_i + b) \ge 1\\$$\frac 12$是为了求导方面添加的系数。
如何求解这个模型呢？显然，这是一个凸二次规划问题，可以使用拉格朗日乘子法来解决，添加系数$\alpha$：$L(w,b,a)=\frac 12 ||\vec w||^2 +\sum_{i=1}^{m}\alpha_i(1-y_i(\vec w^T \vec x_i + b))$
接下来使用常规的拉格朗日解法即可，函数L对w,b求偏导，得到：$\vec w = \sum_{i=1}^m \alpha_iy_i\vec x_i\\\sum_{i=1}^m \alpha_iy_i = 0$然后带入原式中，可以将目标问题化为其对偶问题，即：$max_{\alpha} \; \sum_{i=1}^m {\alpha_i}-\frac 12 \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_i \alpha_jy_i y_jx_i^T x_j\\st.\;\alpha_i > 0\;；\sum_{i=1}^m \alpha_iy_i = 0；$观察这个式子可知：
- 该式子中未知变量只有$\alpha$，我们要寻找$\alpha$使式子最大化
- 一旦求出$\alpha$，即可算出$\vec w$和b，模型即得到求解
模型解释（选看）
那么，我们该如何理解这个模型呢，最主要的一个疑问是，为什么模型的名字叫做支持向量机？
为了求解模型：$L(w,b,a)=\frac 12 ||\vec w||^2 +\sum_{i=1}^{m}\alpha_i(1-y_i(\vec w^T \vec x_i + b))$我们使用了拉格朗日乘子法，由于$1-y_i(\vec w^T \vec x_i + b) \le 0$，满足KKT条件，即：$\alpha_i \ge 0\\y_i(\vec w^T \vec x_i + b)-1 \ge 0\\\alpha_i(y_i(\vec w^T \vec x_i + b)-1)=0$观察该方程组可以看到
- 要么$\alpha_i=0$,要么$y_i(\vec w^T \vec x_i + b)-1=0$,两者必须满足其中一个
- 如果$\alpha_i=0$，则该样本点$\vec x_i$没有被使用，即该样本对于构建后的SVM没有作用
- 如果$y_i(\vec w^T \vec x_i + b)-1=0$，即$y_i(\vec w^T \vec x_i + b)=1$，该样本正好处于最大间隔的分类处，而SVM与这些样本有关。
综上可知，所谓的支持向量机，指的就是该模型仅由支持向量决定，即$\alpha_i\ne0$的向量，这些向量被称为支持向量。
SMO算法求解
那么，该如何求得这个对偶问题呢？$max_{\alpha} \; \sum_{i=1}^m {\alpha_i}-\frac 12 \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_i \alpha_jy_i y_jx_i^T x_j\\st.\;\alpha_i > 0\;；\sum_{i=1}^m \alpha_iy_i = 0；由、、、$可以看出这是一个二次规划问题，最好的求解方法是SMO算法。
- 选择一对需要更新的变量$\alpha_i和\alpha_j$
- 固定除了这两个变量外其他所有变量（即看做常量），将问题简化
- 求解简化后的问题，并更新$\alpha_i和\alpha_j$
- 重复1/2/3步骤直到收敛
当我们将$\alpha_i和\alpha_j$固定了之后，问题中的约束被简化为：$\alpha_iyi+\alpha_j y_j=c(c是一个常数)$这是问题被简化为高中学过的二次函数求最值的问题，很容易求解。
在求解得到$\alpha$之后，利用支持向量的关系：$y_i(\vec w^T \vec x_i + b) = 1 （该式子仅对于支持向量成立）$即可求得b，当然也可以用所有支持向量求解的平均值。
至此，朴素形式的SVM求解完成。
核函数优化
SVM的本质，依旧是在空间中找到一个超平面，将样本点分开。那么是否存在找不到这种超平面的情况呢？
如图所示，异或问题的求解在二维平面便找不到可以划分的直线，但是如果选用适当的三维空间，便可以找到一个合适的平面来分开正负样本。
核函数便是这样的思想，将样本从原始的特征空间映射到高维的样本特征空间，来有效划分不同的样本，假设映射函数为h(x)，那么对应的超平面可以表示为：$f(x)=\vec w ^Th(x)+b$将前几节中所有模型中的x换成h(x)，即可得到升维之后的模型。
但是这里出现了一个困难，$x_i^T x_j$变成了$h(x_i)^Th(x_j)$之后，计算可能是很困难的，因为映射后的特征空间是很多维甚至是无穷维。
为了解决该问题，引入核函数：$令\kappa(x_i,x_j)=h(x_i)^Th(x_j)$之后在所有问题中，我们都可以利用核函数来计算$h(x_i)^Th(x_j)$即可。核函数的本质就是高维空间中两个向量的内积。
有很多常用的核函数，例如：
- 线性核：$\kappa(x_i,x_j)=x_i^Tx_j$
- 高斯核：$\kappa(x_i,x_j)=e^{-\frac {||x_i-x_j||^2} {2\sigma^2}}$
- 多项式核：$\kappa(x_i,x_j)=(x_i^Tx_j)^d$
- sigmoid核：$\kappa(x_i,x_j)=tanh(\beta x_i^Tx_j+\theta)$
在真实的机器学习任务中，也可以通过这些核函数的线性组合，直积等来组合成新的核函数。
软间隔支持向量
在之前的SVM中，要求的都是必须满足间隔的约束，但是有可能有一些任务不可能满足所有的样本点，这时，可以适当降低要求，允许部分样本点出错——出现在间隔线内部，只需要给他们一个损失替代函数即可。
如下图所示，列出了常用的四种损失函数，仔细观察可以看出，这些损失函数在在$z\le1$时都会有大量损失，而在$z\ge1$之后，损失迅速下降。
软间隔支持向量和之前的推导很相似，在这里不详细讲述。
一般形式支持向量
实际上，支持向量机可以被表述为更为一般的形式：$min_f\; \Omega（f）+C\sum_{i=1}^m l(f(x_i),yi)$
- $\Omega(f)$为结构风险，用于描述模型的性质，例如$\frac 12 \omega^2$，这里用来显示间隔的大小
- $\sum_{i=1}^m l(f(x_i),yi)$为经验风险，用于描述模型和数据的契合程度，例如软间隔支持向量中的损失函数
- C为正则化常数，用于控制前面两者的比例，防止过拟合和欠拟合。
查看更多
所有的文章都会在我的博客和我的知乎专栏同步进行更新，欢迎阅读
\