本文源自微信公众号【Python编程和深度学习】原文链接：[机器学习系列（五）支持向量机（SVM）](https://mp.weixin.qq.com/s?__biz=MzUxNTY1MjMxNQ==&mid=2247484512&idx=1&sn=b76a844c41ede0f9e380245e8522eee1&chksm=f9b22bd4cec5a2c2fbc2923d0c84ad679fadd531d1355785eb1aa98f3bb71037eb2bea68e0d2&token=826655880&lang=zh_CN#rd)，欢迎扫码关注鸭！  支持向量机（SVM）是一种有监督的机器学习算法，主要用于分类任务， 给定训练样本集D = （（x1,y1）,(x2,y2),…,(xn,yn)）,yi的取值为{-1，1}，当yi为1时就是正类，为-1时就是负类，线性分类器基于训练样本D在二维空间中找到一个超平面来对样本进行分类。 # 目录 [一、线性可分问题](#1)<br> [1.1、最大间隔超平面](#1.1)<br> [1.2、SVM最优化问题](#1.2)<br> [1.3、拉格朗日目标函数](#1.3)<br> [1.4、KKT条件](#1.4)<br> [1.5、序列最小优化算法（SMO](#1.5)<br> <div id="1"></div> ##一、数据类型 D0和D1是n维欧氏空间中的两个点集。如果存在n维向量*w*和实数b，使得所有属于D0的点xi都有$w x_{i}+b>0$，而对于所有属于 D1的点 xj则有$w x_{j}+b<0$，则我们称D0和D1线性可分。在二维空间中就是一条直线把两类点完全分开。 <div id="1.1"></div> ### 1.1 最大间隔超平面 我们将特征空间扩展到高维空间，就需要一个超平面来将两种数据进行分开，这样的超平面往往很多，我们需要选择最佳的分类超平面，使得超平面两侧最近的样本到超平面的距离最大，称为最大间隔超平面，距离超平面最近的点称为支持向量。图中红实圈和红空圈都是支持向量，中间的实线为最佳超平面。  <div id="1.2"></div> ### 1.2 SVM最优化问题 这里间隔超平面用下面式子代表： $$ w^{T} x+b=0 $$ 在二维空间中，点到直线的标准距离公式为： $$ \frac{|A x+B y+C|}{\sqrt{A^{2}+B^{2}}} $$ 在n维空间中点x到间隔超平面的距离为： $$ \frac{\left|w^{T} x+b\right|}{\|w\|} $$ 其中$\|w\|=\sqrt{w_{1}^{2}+\ldots w_{n}^{2}}$，我们假设支持向量到最佳超平面的距离为d，那么可以知道其他点到最佳超平面的距离都大于d，则有 $$ \left\{\begin{array}{l} \frac{w^{T} x+b}{\|w\|} \geq d \quad y=1 \\ \frac{w^{T} x+b}{\|w\|} \leq-d \quad y=-1 \end{array}\right. $$ 变换为 $$ \left\{\begin{array}{l} \frac{w^{T} x+b}{\|w\| d} \geq 1 \quad y=1 \\ \frac{w^{T} x+b}{\|w\| d} \leq-1 \quad y=-1 \end{array}\right. $$ 由于$\|w\| d$是正数，为了方便计算给它置1， $$ \left\{\begin{array}{l} w^{T} x+b \geq 1 \quad y=1 \\ w^{T} x+b \leq-1 \quad y=-1 \end{array}\right. $$ 简写为： $$ y\left(w^{T} x+b\right) \geq 1 $$ 前面介绍过支持向量到超平面的距离为 $$ d=\frac{\left|w^{T} x+b\right|}{\|w\|} $$ 替换为 $$ d=\frac{y\left|w^{T} x+b\right|}{\|w\|} $$ 我们定margin为2个d，则目标变为最大化两侧支持向量到最佳超平面的距离， $$ \max 2 * \frac{y\left(w^{T} x+b\right)}{\|w\|} $$ 由于支持向量到最大超平面的距离为1，因此 $$ \max \frac2{\|w\|} $$ 将求最大变为求最小 $$ \min \frac{1}{2}\|w\| $$ 这样，最终的支持向量机最优化问题为： $$ \left\{\begin{array}{l} \min \frac{1}{2}\|w\|\\ \begin{array}{ll}\text { s. t. } \quad y_{i} & \left(w^{T} x_{i}+b\right) \geq 1\end{array} \end{array}\right. $$ <div id="1.3"></div> ### 1.3 拉格朗日目标函数 这是一个含有不等式约束的凸二次规划问题，可以对其使用拉格朗日乘子法得到其对偶问题（dual problem）。 将有约束的原始目标函数转换为无约束的拉格朗日目标函数， $$ L(\boldsymbol{w}, b, \boldsymbol{\alpha})=\frac{1}{2}\|\boldsymbol{w}\|^{2}-\sum_{i=1}^{N} \alpha_{i}\left(y_{i}\left(\boldsymbol{w} \cdot \boldsymbol{x}_{i}+b\right)-1\right) $$ 其中，alpha为拉格朗日乘子，且大于等于0，得到 $$ \theta(\boldsymbol{w})=\max _{\alpha_{i} \geq 0} L(\boldsymbol{w}, b, \boldsymbol{\alpha}) $$ 当样本点不满足约束条件时，即在可行解区域外： $$ y_{i}\left(\boldsymbol{w} \cdot \boldsymbol{x}_{i}+b\right)<1 $$ 此时，将 alpha设置为无穷大，则$\theta(\boldsymbol{w})$也为无穷大。 当满本点满足约束条件时，即在可行解区域内： $$ y_{i}\left(\boldsymbol{w} \cdot \boldsymbol{x}_{i}+b\right)\geq 1 $$ 此时，$\theta(\boldsymbol{w})$为原函数本身。于是，将两种情况合并起来就可以得到我们新的目标函数 $$ \theta(\boldsymbol{w})=\left\{\begin{array}{ll} \frac{1}{2}\|\boldsymbol{w}\|^{2}, \boldsymbol{x} \in \text { 可行区域 } \\ +\infty & , \boldsymbol{x} \in \text { 不可行区域 } \end{array}\right. $$ 于是原约束问题就等价于 $$ \min _{\boldsymbol{w}, b} \theta(\boldsymbol{w})=\min _{\boldsymbol{w}, b} \max _{\alpha_{i} \geq 0} L(\boldsymbol{w}, b, \boldsymbol{\alpha})=p^{*} $$ 该式先求最大值，再求最小值，使用拉格朗日函数对偶性，将最小和最大的位置交换一下，这样就变成了 $$ \max _{\alpha_{i} \geq 0} \min _{\boldsymbol{w}, b} L(\boldsymbol{w}, b, \boldsymbol{\alpha})=d^{*} $$ <div id="1.4"></div> ### 1.4 KKT条件 要有需要满足两个条件: 1）优化问题是凸优化问题 2）满足KKT条件 本问题明显是凸优化问题，KKT条件是 $$ \left\{\begin{array}{l} \alpha_{i} \geq 0 \\ y_{i}\left(\boldsymbol{w}_{i} \cdot \boldsymbol{x}_{i}+b\right)-1 \geq 0 \\ \alpha_{i}\left(y_{i}\left(\boldsymbol{w}_{i} \cdot \boldsymbol{x}_{i}+b\right)-1\right)=0 \end{array}\right. $$ 为了得到求解对偶问题的具体形式，令$L(\boldsymbol{w}, b, \boldsymbol{\alpha})$对 w 和 b的偏导为0，可得 $$ \boldsymbol{w}=\sum_{i=1}^{N} \alpha_{i} y_{i} \boldsymbol{x}_{i} $$ $$ \sum_{i=1}^{N} \alpha_{i} y_{i}=0 $$ 将以上两个等式带入拉格朗日目标函数，消去 w和 b， 得 $$ \begin{array}{l} L(\boldsymbol{w}, b, \boldsymbol{\alpha})=\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}\left(\boldsymbol{x}_{i} \cdot \boldsymbol{x}_{j}\right)-\sum_{i=1}^{N} \alpha_{i} y_{i}\left(\left(\sum_{j=1}^{N} \alpha_{j} y_{j} \boldsymbol{x}_{j}\right) \cdot \boldsymbol{x}_{i}+b\right)+\sum_{i=1}^{N} \alpha_{i} \\ =-\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}\left(\boldsymbol{x}_{i} \cdot \boldsymbol{x}_{j}\right)+\sum_{i=1}^{N} \alpha_{i} \end{array} $$ 即 $$ \min _{w, b} L(\boldsymbol{w}, b, \boldsymbol{\alpha})=-\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}\left(\boldsymbol{x}_{i} \cdot \boldsymbol{x}_{j}\right)+\sum_{i=1}^{N} \alpha_{i} $$ 求$\min _{\boldsymbol{w}, b} L(\boldsymbol{w}, b, \boldsymbol{\alpha})$对alpha的极大，是对偶问题 $$ \begin{array}{l} \max _{\alpha}-\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}\left(\boldsymbol{x}_{i} \cdot \boldsymbol{x}_{j}\right)+\sum_{i=1}^{N} \alpha_{i} \\ \text { s.t. } \quad \sum_{i=1}^{N} \alpha_{i} y_{i}=0 \\ \quad \alpha_{i} \geq 0, i=1,2, \ldots, N \end{array} $$ 为了计算方便给式子取负号，转换为求解极小， $$ \begin{array}{l} \min _{\alpha} \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}\left(\boldsymbol{x}_{i} \cdot \boldsymbol{x}_{j}\right)-\sum_{i=1}^{N} \alpha_{i} \\ \text {s.t.} \quad \sum_{i=1}^{N} \alpha_{i} y_{i}=0 \\ \alpha_{i} \geq 0, i=1,2, \ldots, N \end{array} $$ <div id="1.5"></div> ### 1.5 序列最小优化算法（SMO） 到现在我们的优化问题需要更高效的优化算法，序列最小优化算法（SMO），我们通过这个优化算法能得到 alpha，再根据 alpha，我们就可以求解出 w和 b ，进而求得我们最初的目的：找到超平面，即”决策平面”。 根据前面的推导，还有下面两个式子成立 $$ \begin{array}{l} \boldsymbol{w}=\sum_{i=1}^{N} \alpha_{i} y_{i} \boldsymbol{x}_{i} \\ \sum_{i=1}^{N} \alpha_{i} y_{i}=0 \end{array} $$ 由此可知在 alpha中，至少存在一个$\alpha_{j}^{*}>0$（反证法可以证明，若全为0，则 w=0，矛盾），对此 j有  得到  大部分的训练样本都不需要保留，最终模型仅与支持向量有关。