SVM

SVM：Support Vector Machine
中文名：支持向量机

学习模型
有监督学习：需要事先对数据打上分类标签，这样机器就知道数据属于哪一类。
无监督学习：数据没有打上分类标签，有可能因为不具备先验知识，或打标签的成本很高，需要机器代替我们部分完成改工作，比如将数据进行聚类，方便后人工对每个类进行分析。
SVM 是有监督的学习模型：可以进行模式识别、分类以及回归分析。
SVM工作原理
示例： 桌面上有两种颜色混乱的小球，我们将这两种小球来区分开，我们猛拍桌子小球会腾起，在腾空的那一刹那，会出现一个水平切面，将两种颜色的球分开来。
原因： 二维平面无法找出一条直线来区分小球颜色，但是在三位空间。我们可以找到一个平面来区分小球颜色，该平面我们叫做超平面。
SVM计算过程： 就是帮我们找到一个超平面的过程，该超平面就是 SVM分类器。
分类间隔
我们在示例中，会找到一个决策面来将小球颜色分离，在保证决策面C不变，且分类不产生错误的情况下，我们可以移动决策面，来产生两个极限位置：决策面A和决策面B，分界线C就是最优决策面，极限位置到最优决策面的距离就是 分类间隔 。
我们可以转动最优决策面，会发现存在多个最优决策面，它们都能把数据集正确分开，这些最优决策面的分类间隔可能是不同的，拥有最大间隔的决策面就是 SVM 需要的最优解。
点到超平面距离公式
决策面在一维空间就是一个点、二维空间就是一条直线、三维空间就是一个平面，当空间维度更多，这个线性函数名称叫做 “超平面”：$g(x) = w^Tx + b$，其中$w,x\in R^n$
w、x是n维空间里的向量，其中x是函数变量，w是法向量。法向量指的是垂直于平面直线所表示的向量，决定超平面的方向。
SVM就是帮我们找到一个超平面 ，这个超平面能将不同样本划分，使得样本集中的点到这个分类超平面的最小距离(分类间隔)最大化，在这个过程中 支持向量 就是离 分类超平面 最近的样本点，如果确定了支持向量也就确定了这个超平面，所以支持向量决定了分类间隔是多少，在最大间隔以外的样本点，对分类都没有意义。
SVM就是求解 最大分类间隔的过程，我们还要对分类间隔大小进行定义。
定义某类样本集到超平面的距离就是这个样本集合内的样本到超平面的最短距离，用di代表点xi到超平面wxi+b=0的欧氏距离。因此我们求di最小值，计算公式$d_i = \frac{|wx_i + b|}{||w||}$，其中$||w||$为超平面的范数，di可以用解析几何知识进行推导。
最大间隔优化模型
目标： 找出所有分类间隔中最大的那个值对应的超平面。
硬间隔、软间隔和非线性SVM

数据线性可分：模型称为硬间隔支持向量机

硬间隔：完全分类准确，不存在分类错误的情况
软间隔：允许一定量的样本分类错误


非线性数据：模型称为非线性支持向量机

非线性数据集合： 两种颜色的小球，呈现大小圆环的形状。
非线性数据集合，不论多高级的分类器，只要映射函数是线性的，就没办法处理，SVM也处理不了。
核函数： 可以将样本从原始空间映射到一个更高的特质空间中，使得样本在新空间中线性可分，我们就以可以使用原来的推到进行计算，所有推到都是在新空间，而不是在原来的空间中进行。
在非线性SVM中，核函数的选择就是影响SVM最大的变量，下面是常用的核函数

线性核
多项式核
高斯核
拉普拉斯核
sigmoid核

这些函数的区别在于映射方式的不同，通过核函数就能把样本空间投射到新的高维空间中。
结果： 软间隔和核函数的提出，都是为了方便对超平面公式中的w和b进行求解，得到最大分类间隔的超平面。
SVM解决多分类问题
SVM本身就是一个二值分类器，最初是为二分类问题设计的，就是回答Yes/No，但是实际解决的问题，可能是多分类情况，比如：文本进行分类、图像进行识别。
多分类情况，可以将多个二分类器组合起来形成一个多分类器，常见方法有一对多法、一对一法两种。
一对多法
我们将物体分为A、B、C、D四种分类，先把其中的一类作为分类1，其他类归为分类2，我们来构造4种SVM，分为以下情况：

样本A作为正集，B、C、D作为负集
样本B作为正集，A、C、D作为负集
样本C作为正集，A、B、D作为负集
样本D作为正集，A、B、C作为负集

优点： 针对K个分类，需要训练K个分类器，分类速度较快
缺点： 训练速度慢，每个分类器需要对全部样本进行训练，而且负样本数量远大于正样本数量，会造成样本不对称情况，而且增加新的非累，需要重新对分类器进行构造。
一对一法
任意两类样本之间构造一个SVM，这样针对K类的样本，就会有$C(k,2)$类分类器，训练的时候更加灵活。
我们划分A、B、C三个类，可以构造3个分类器：

分类器：A、B
分类器：A、C
分类器：B、C

当对一个未知样本进行分类，每一个分类器有一个分类器结果，为1票，最终得票最多的类就是整个未知样本的类别。
优点： 新增一类，不需要重新训练所有的SVM，只需要训练和新增这一类样本的分类器，在训练单个SVM模型的时候，训练速度很快。
缺点： 分类器的个数与K的平方成正比，当K较大时，训练和测试的时间会比较慢。

SVM 的推导、特点、优缺点、多分类问题及应用

作者：keepreder

SVM有如下主要几个特点：
(1)  非线性映射是SVM方法的理论基础,SVM利用内积核函数代替向高维空间的非线性映射；
(2)  对特征空间划分的最优超平面是SVM的目标,最大化分类边际的思想是SVM方法的核心；
(3)  支持向量是SVM的训练结果,在SVM分类决策中起决定作用的是支持向量。
(4)  SVM 是一种有坚实理论基础的新颖的小样本学习方法。它基本上不涉及概率测度及大数定律等,因此不同于现有的统计方法。从本质上看,它避开了从归纳到演绎的传统过程,实现了高效的从训练样本到预报样本的“转导推理”,大大简化了通常的分类和回归等问题。
(5)  SVM 的最终决策函数只由少数的支持向量所确定,计算的复杂性取决于支持向量的数目,而不是样本空间的维数,这在某种意义上避免了“维数灾难”。
(6)  少数支持向量决定了最终结果,这不但可以帮助我们抓住关键样本、“剔除”大量冗余样本,而且注定了该方法不但算法简单,而且具有较好的“鲁棒”性。这种“鲁棒”性主要体现在:
    ①增、删非支持向量样本对模型没有影响;

    ②支持向量样本集具有一定的鲁棒性;

    ③有些成功的应用中,SVM 方法对核的选取不敏感

(7)  SVM学习问题可以表示为凸优化问题，因此可以利用已知的有效算法发现目标函数的全局最小值。而其他分类方法（如基于规则的分类器和人工神经网络）都采用一种基于贪心学习的策略来搜索假设空间，这种方法一般只能获得局部最优解。
(8)  SVM通过最大化决策边界的边缘来控制模型的能力。尽管如此，用户必须提供其他参数，如使用核函数类型和引入松弛变量等。
(9)  SVM在小样本训练集上能够得到比其它算法好很多的结果。支持向量机之所以成为目前最常用，效果最好的分类器之一，在于其优秀的泛化能力，这是是因为其本身的优化目标是结构化风险最小，而不是经验风险最小，因此，通过margin的概念，得到对数据分布的结构化描述，因此减低了对数据规模和数据分布的要求。SVM也并不是在任何场景都比其他算法好，对于每种应用，最好尝试多种算法，然后评估结果。如SVM在邮件分类上，还不如逻辑回归、KNN、bayes的效果好。
(10)  它基于结构风险最小化原则，这样就避免了过学习问题，泛化能力强。
(11)  它是一个凸优化问题，因此局部最优解一定是全局最优解的优点。
(12)  泛华错误率低，分类速度快，结果易解释
不足之处：
(1) SVM算法对大规模训练样本难以实施

SVM的空间消耗主要是存储训练样本和核矩阵，由于SVM是借助二次规划来求解支持向量，而求解二次规划将涉及m阶矩阵的计算（m为样本的个数），当m数目很大时该矩阵的存储和计算将耗费大量的机器内存和运算时间。针对以上问题的主要改进有有J.Platt的SMO算法、T.Joachims的SVM、C.J.C.Burges等的PCGC、张学工的CSVM以及O.L.Mangasarian等的SOR算法。
    如果数据量很大，SVM的训练时间就会比较长，如垃圾邮件的分类检测，没有使用SVM分类器，而是使用了简单的naive bayes分类器，或者是使用逻辑回归模型分类。

(2) 用SVM解决多分类问题存在困难

经典的支持向量机算法只给出了二类分类的算法，而在数据挖掘的实际应用中，一般要解决多类的分类问题。可以通过多个二类支持向量机的组合来解决。主要有一对多组合模式、一对一组合模式和SVM决策树；再就是通过构造多个分类器的组合来解决。主要原理是克服SVM固有的缺点，结合其他算法的优势，解决多类问题的分类精度。如：与粗集理论结合，形成一种优势互补的多类问题的组合分类器。
(3)对缺失数据敏感，对参数和核函数的选择敏感

支持向量机性能的优劣主要取决于核函数的选取,所以对于一个实际问题而言,如何根据实际的数据模型选择合适的核函数从而构造SVM算法.目前比较成熟的核函数及其参数的选择都是人为的,根据经验来选取的,带有一定的随意性.在不同的问题领域,核函数应当具有不同的形式和参数,所以在选取时候应该将领域知识引入进来,但是目前还没有好的方法来解决核函数的选取问题.
支持向量机的主要应用和研究的热点

目前支持向量机主要应用在模式识别领域中的文本识别,中文分类,人脸识别等;同时也应用到许多的工程技术和信息过滤等方面.
    当前研究的热点主要是对支持向量机中算法的优化,包括解决SVM中二次规划求解问题,对大规模SVM的求解问题,对SVM中QP问题的求解问题等.另外就是如何更好的构造基于SVM的多类分类器,如何提高SVM的归纳能力和分类速度等.如何根据实际问题确定核函数也是一个重要的研究热点.

前言
朋友，你通过各种不同的途经初次接触支持向量机（SVM）的时候，是不是会觉得这个东西耳熟能详，感觉大家都会，却唯独自己很难理解？

每一次你的老板或者同仁让你讲解SVM的时候，你觉得你看过这么多资料，使用过这么多次，讲解应该没有问题，但偏偏在分享的时候结结巴巴，漏洞百出？

每一次机器学习相关的面试在问到支持向量机（SVM）的时候，尽管你觉得你都准备好了，可是一次又一次败下阵来，以至于觉得问那些问题的人（是不是脑子有…）是那么的厉害，每一次都能精准发觉到你的不足和漏洞，让你怀疑你掌握的是假的SVM，然后让你怀疑人生？

那还等什么，快来看看这篇文章吧，原价998，现在只要。。。（不好意思，扯偏了。）
以上可能真的只是我的个人经历（在这里，学渣给各位大佬鞠躬了！），但不管怎么样，我还是要自己写一篇从头到尾的SVM的理解，然后呈现给各位大佬审阅，欢迎您批评指正！
按照以下问题成文：

由线性分类任务开始
为何需要最大化间隔
怎么解决凸二次规划问题
对偶问题的求解
SMO算法
核函数的由来和使用
SVM与LR的异同

SVM由线性分类开始
在这之前，假设读者们对线性分类模型和向量矩阵求导有大概的了解。
给定训练样本集$D={(x_{1},y_{1}),(x_{2},y_{2}),...,(x_{m},y_{m})))}, y_{i}\in \left \{ -1, 1\right \}$, 线性分类器基于训练样本D 在二维空间中找到一个超平面来分开二类样本。当然，这样的超平面有很多。

但我们可以直观感受到，这根红色线代表的超平面抗“扰动”性最好。这个超平面离直线两边的数据的间隔最大，对训练集的数据的局限性或噪声有最大的“容忍”能力。
在这里，这个超平面可以用函数$f(x) = w^{T}x+b$ 表示。 当$f(x)$ 等于0的时候，x便是位于超平面

上的点，而$f(x)$ 大于0的点对应 y=1 的数据点，$f(x)$ 小于0的点对应y=-1的点。
为什么是$y_{i}\in \left \{ -1, 1\right \}$,换句话说，$y$ 只能是-1，和1吗？不能是$y$ =-100 表示反例，$y$ =2000表示正例，或$y$ =0表示反例，$y$ =300表示正例，或$y$ =5表示反例 $y$ =-7 表示正例吗？当然可以。y 只是一个label ，标注为{-1，+1}不过为了描述方便。
若$y$ =0表示反例，$y$ =300表示正例，只不过分正类的标准变为$(y-150）*f（x)>0$
不妨令：
$\left\{\begin{matrix}w^{T}x_{i}+b \geqslant +1, y_{i} = +1 ;& \\ w^{T}x_{i}+b \leq  -1, y_{i} = -1 & \end{matrix}\right.$
为什么可以这么令呢？我们知道，所谓的支持向量，就是使得上式等号成立，即最靠近两条虚边界线的向量。那么，不难理解当$w^{T}x+b$的值大于+1，或小于-1的时候，就更加支持“样本的分类”了。为什么要这么令呢？还是为了计算方便。接着往下看，你一定能悟到这么令的原因。
我们可以计算得到空间中任意样本点$x$到超平面的距离为：$r = \frac{|w^{T}x+b|}{\left \| w \right \|}$。为什么呢？



如图所示，有：$x = x_{0}+r\frac{w}{\left \| w \right \|}$(简单平面几何)

又有：$w^{T}x_{0}+b = 0$，代入上式，求得：$r = \frac{|w^{T}x+b|}{\left \| w \right \|}$。
因为$y_{i}\in \left \{ -1, 1\right \}$,，两个异类支持向量到超平面的距离之和（也称为“间隔”）可表示为：$r = \frac{2}{\left \| w \right \|}$。

下面我们用严谨的逻辑来重新梳理横线“—”上面的内容：
对于一个分类问题，我们假设$y_{i}\in \left \{ -1, 1\right \}$,同样的，$\left \{ -1, 1\right \}$不过是正类和负类的类标表示。
我们假设
$\left\{\begin{matrix}w^{T}x_{i}+b \geqslant 0, 时，对应y_{i}取正例，表示为y_{i} = +1 ;& \\ w^{T}x_{i}+b \leq  0, 时，对应y_{i}取负例，表示为 y_{i} = -1 ;& \end{matrix}\right.$

如上所述，SVM的目的是最大分类间隔即：

$\max{margin} \\s.t. \ y_i(w^Tx_i+b)\geqslant0 ,for \forall i = 1,...,m$

因为我们前面定义：

$w^{T}x_{i}+b \geqslant 0, 时，对应y_{i}取正$,

$w^{T}x_{i}+b \leq  0, 时，对应y_{i}取负$,

显然有：

$\max{margin} \\s.t. \ y_i(w^Tx_i+b)\geqslant 0 ,for \forall i = 1,...,m$

margin是什么呢？

按照点到直线的距离，每一类样本中的所有样本点到直线的距离为：

$\frac{|w^{T}x_i+b|}{\left \| w \right \|}$

我们的单侧margin应该是每一类样本中，到超平面距离最近的点与超平面的距离。（支持向量到超平面的距离）那么margin 等于2倍的单侧margin。

于是有：

$margin = 2\times _{w,b,x_i}^\textrm{min}\frac{|w^{T}x_i+b|}{\left \| w \right \|},i = 1,...,m$
回到我们之前的假设，我们有$y_i(w^Tx_i+b)\geqslant 0，y_i  与 (w^Tx_i+b) 同号$，我们说有：

$margin = 2\times _{w,b,x_i}^\textrm{min}\frac{|w^{T}x_i+b|}{\left \| w \right \|} = 2\times _{w,b,x_i,y_i}^\textrm{min}\frac{y_i(w^{T}x_i+b)}{\left \| w \right \|},
\\i = 1,...,m$

我们以此来消除分子中的绝对值。
于是SVM的目标变为：

$_{w,b}^\textrm{max}\frac{1}{\left \| w \right \|}2\times _{x_i,y_i}^\textrm{min}{y_i(w^{T}x_i+b)},\\s.t.\\y_i(w^Tx_i+b)\geqslant 0,i = 1,...,m$
单独考察

$\\y_i(w^Tx_i+b)\geqslant 0,i = 1,...,m$

也就是说存在任意a >0 使得 $_{x_i,y_i}^{min}y_i(w^Tx_i+b) = a$
我们令a = 1,来简化运算， 于是得到： $_{x_i,y_i}^{min}y_i(w^Tx_i+b) = 1$

我们完全可以这样令a=1,试想，$y_i$是固定的，假设$y_i$是正例的情况下，$w^Tx_i+b$是一个个大于0的值，这个值是多少，并不重要，只需要其大于0即可。我们令 $_{x_i,y_i}^{min}y_i(w^Tx_i+b) = 1$相当于对$|w|$作了约束。
综上所述：

于是SVM的目标进一步变为：

$_{w,b}^\textrm{max}\frac{2}{\left \| w \right \|},\\s.t.\\y_i(w^Tx_i+b)\geqslant 1,i = 1,...,m$
很显然，我们要找到符合这样一个条件的超平面来分开两类数据：

这个超平面离两类样本都足够远，也就是使得“间隔”最大。即最终确定的参数$w 和 b$,使得$r$最大。
接下来我们继续
$_{w,b}^\textrm{max}\frac{2}{\left \| w \right \|}$

$s.t. y_{i}( w^{T}x_{i}+b)\geq 1，i=1,2,...,m$
等价于
$_{w,b}^\textrm{min}\frac{1}{2}{\left \| w \right \|}^{2}$

$s.t. y_{i}( w^{T}x_{i}+b)\geq 1，i=1,2,...,m$
由此我们得到了SVM的基本型。
##凸优化

我们可以看到，上面的基本型目标函数是二次的，约束条件是线性的，这是一个凸二次规划问题。可以直接用现成的优化计算包求解。但若利用“对偶问题”来求解，会更高效。


啥是凸？什么是凸优化？
凸优化说的是这么一回事情，

$X\subset R^{n}$ 为一凸集，$f:X\rightarrow R$ 为一凸函数，凸优化就是要找出一点$x^{*} \in X,$使得任意$x \in X,$都满足$f(x^{*})\leq f(x)$ .

可以想象成给我一个凸函数，我要去找到最低点。当然凸优化是一个很大很厉害的领域，在这里，我们只需要知晓这个问题是这么一回事。然后，这回事要怎么样求解，就好，有兴趣的朋友可以参考凸优化的概念或者Stephen Boyd & Lieven Vandenberghe 的《Convex Optimization》。


为啥叫二次规划问题呢？


据了解（其实就是知道），目标函数和约束条件都为变量的线性函数，叫做-----线性规划问题。

目标函数为变量的二次函数和约束条件为变量的线性函数，叫做-----二次规划问题。

目标函数和约束条件都为非线性函数，叫做-----非线性规划问题。
对偶问题
对于

$_{w,b}^\textrm{min}\frac{1}{2}{\left \| w \right \|}^{2}$

$s.t. y_{i}( w^{T}x_{i}+b)\geq 1，i=1,2,...,m$

为了后面的描述方便，记这个式子为（1）式。
使用**拉格朗日乘子法**可以得到其“对偶问题”。

这是拉格朗日对偶性，即，通过给每一个约束条件加上一个拉格朗日乘子。然后定义出拉格朗日函数，通过拉格朗日函数将约束条件融合进目标函数中。目的是，只需要通过一个目标函数包含约束条件，便可以清楚解释问题。
比如对（1）式每一个约束（共有m个约束，$y_{i}( w^{T}x_{i}+b)\geq 1$），添加拉格朗日乘子 $\alpha  _{i} \geq 0$,则整个问题的拉格朗日函数可写为：

$L(w,b,\alpha )= \frac{1}{2}\left \|w\right \| ^{2} +\sum _{i=1}^{m}\alpha _{i}(1- y_{i}( w^{T}x_{i}+b))$

为什么使用这样的拉格朗日乘子，又为何这样构建？这实际上是因为我们的目标函数是不等式约束，解这样的二次规划问题，我们选择用KKT条件，而KKT条件需要这样的一个约束$\alpha  _{i} \geq 0$。最终我们便通过KKT条件来产生原问题的对偶问题。

同样的，将上面这个式子记为（2）式。
可以看到，由于$\alpha  _{i} \geq 0$, 这样，但凡有约束条件之一不满足，如$y_{k}( w^{T}x_{k}+b)<  1$），
$L(w,b,\alpha )= \infty$。只有约束条件均满足的时候，
$L(w,b,\alpha )$有最优值，为$L(w,b,\alpha )= \frac{1}{2}\left \|w\right \| ^{2}$
所以优化$\frac{1}{2}\left \|w\right \| ^{2}$ 等价于优化$L(w,b,\alpha )$当然，要满足约束条件$\alpha  _{i} \geq 0$。

我们从逻辑上再来理解下上述内容：

对于一个不等式约束优化问题：

$_x^{min}f(x)
\\s.t.\\m_i(x)\leqslant 0,i=1,...,m$

我们总可以将其转化成拉格朗日形式：

$\iota（x,\lambda ,\eta） = f(x) + \sum_{i=1}^{m}\lambda _im_i$

之后再转化为求如下的约束：

$_x^{min}{_{\lambda,\eta }^{max}}\iota (x,\lambda,\eta)$

我们可以证明转化后的约束包含了原问题。

转化后的约束是一个关于$x$的函数。

进一步的我们可构建其对偶问题：

${_{\lambda,\eta }^{max}}{_x^{min}}\iota (x,\lambda,\eta)$

对偶问题是关于$\lambda,\eta$的函数。

由于是先求最小然后求最大，我们的问题的求解就变得容易。
接下来我们继续

于是，我们的目标函数可以表示为：
$_{w,b}^{min}$$_{_{\alpha\geq 0}}^{max}$$L(w,b,\alpha )$
满足一定条件下，等价于（注意，这个满足一定条件，是指满足KKT条件）
$_{_{\alpha\geq 0}}^{max}$$_{w,b}^{min}$$L(w,b,\alpha )$
后者把最小和最大的位置交换，这样使得运算方便起来。
##KKT条件

什么是KKT条件？其实在这之前，本文有稍微有提到过。在这里正式介绍一下。
KKT条件是一个线性规划问题能有最优解的充分和必要条件。
一般地，一个最优化数学模型可以表示成如下形式：
$minf(x)$

$s.t. h_{i}(x) = 0 , i = 1,2,...,p$

$g_{j}(x) \leq  0 , j = 1,2,...,q$

$x\in X \in R^{n}$
$h(x)$ 是等式约束。

$g(x)$ 是不等式约束。

$p,q$ 表示约束的数量。
而这个最优化数学模型的最优解$x^{*}$须满足的条件，即KKT条件为：

$h_{i}(x^{*}) = 0 , i = 1,2,...,p$,和 $g_{j}(x^{*})  \leq  0 , j = 1,2,...,q$
$\bigtriangledown f(x^{*}) + \sum_{i=1}^{p}\lambda _{i}\bigtriangledown h_{i}(x^{*}) + \sum_{j=1}^{q} \mu _{k}\bigtriangledown g_{k}(x^{*}) = 0$
$\lambda _{i}\neq 0, \mu _{k}\geq 0, \mu _{k}g_{k}(x^{*}) = 0$

于是我们的整个问题转化为


$L(w,b,\alpha)$ 对$w,b$求最小


再对$\alpha$ 求最大。


对于第一步，先令$L(w,b,\alpha )$对$w,b$求偏导为0，可得：

$w=\sum_{i=1}^{m}\alpha_{i}y_{i}x_{i},$
$0=\sum_{i=1}^{m}\alpha_{i}y_{i}.$
将此两个式子带入（2）式消去$w,b$。便得到了（1）式的对偶问题。
$_{\alpha\geq 0 }^{max}\sum_{i=1}^{m}\alpha_{i}-\frac{1}
{2}\sum_{i,j=1}^{m}\alpha_{i}\alpha_{j}y_{i}y_{j}x_{i}^{T}x_{j}$
$s.t. \sum_{i=1}^{m}\alpha_{i}y_{i}.=0,$

$\alpha_{i}\geq 0 , i = 1,2,...,m$
类比来看，我们的目标函数没有$h(x) = 0$ 的等式约束。

于是，上面的过程，需要满足的KKT条件是
$\left\{\begin{matrix}\alpha_{i} \geq 0 ;\\1- y_{i}( w^{T}x_{i}+b) \leq 0;\\ \alpha_{i}(1-y_{i}( w^{T}x_{i}+b))=0.\end{matrix}\right.$
我们看到，对于任意样本，总有$\alpha_{i} = 0$ 或者 $y_{i}( w^{T}x_{i}+b) =1$ .若$\alpha_{i} = 0$ ，则由$w=\sum_{i=1}^{m}\alpha_{i}y_{i}x_{i},$知$w = 0$ , 则此$\alpha_{i}$ 对应的向量不会对 $f(x)$ 的确定有任何影响。而$\alpha_{i} > 0$ 时，必有$y_{i}( w^{T}x_{i}+b) =1$ ，此时$\alpha_{i}$ 对应的向量在最大间隔的边缘上（一开始示意图的虚线上），即是支持向量。这也说明，最终模型的确定，只与支持向量有关。
接下来，怎么求$\alpha$呢？

##序列最小优化算法（SMO算法）
三种支持向量机
我们先来体味一下支持向量机的分类吧。一般支持向量机可以分为三类：线性可分支持向量机（support vector machine in linearly separable case）、线性支持向量机（linear support vector machine ）以及非线性支持向量机（non-linear support vector machine）这三个由简至繁的模型分别解决训练数据的三个不同情况。当训练数据线性可分时，训练一个线性可分支持向量机，也称硬间隔支持向量机，当训练数据近似线性可分时，通过软间隔最大化（什么是软间隔最大化？后面会讲的），训练一个线性支持向量机，当数据线性不可分，我们通过核技巧（核技巧由Boser,Guyon等引入。什么是核技巧？后面会讲到）及软间隔最大化学习非线性支持向量机。
在这里引入一张图片，近距离体会上述三种数据类型。



自此我们也看出来了，上面的所有解法，都是针对于线性可分支持向量机来说的。不过以此为基础，另外两种支持向量机就特别好理解了。

如何判断数据线性可分，推荐参考这篇博文：http://www.atyun.com/14182.html
线性支持向量机
还记得在介绍线性可分svm的时候，我们几乎强给的约束$y_i(w^Tx_i+b)\geqslant 1$ 吗？但当我们面对线性不可分数据时，意味着某些样本点不能满足间隔大于等于1 的约束了。我们可以看下方的示意图，在间隔内部，还存在一些样本点，并不满足约束$y_i(w^Tx_i+b)\geqslant 1$ 。


这时通过引入一个松弛变量 ${\xi}_i\geq0$ 来使得函数间隔加上松弛变量大于等于1。此时，约束条件变为：$y_i(w^Tx_i+b)\geqslant 1-{\xi}_i$

对于所有的样本都加上这样一个松弛变量，目标函数由原来的$\frac{1}{2}{\left \| w \right \|}^{2}$ 变为

$\frac{1}{2}{\left \| w \right \|}^{2} + C\sum_{i=1}^{N}{\xi}_i$

同样的，我们通过求解如下凸二次规划问题：
$_{w,b,{\xi}}^\textrm{min}\frac{1}{2}{\left \| w \right \|}^{2} + C\sum_{i=1}^{N}{\xi}_i$

$s.t.     y_i(w^Tx_i+b)\geqslant 1-{\xi}_i,    i=1,2,....,N\\{\xi}_i\geq0,i=1,2,....,N$

来实现线性支持向量机的学习。我们可以发现，软间隔支持向量机的支持向量$x_i$或在间隔边界上，或在间隔之间，或在分离超平面的误分一侧。
在这里C是一个大于0的超参数，称惩罚参数，

由于要最小化目标函数，仔细推敲不难发现：

C值越小，对误分类的惩罚越小，（在gap内的样本点可能允许多些）。

C值越大，对误分类的惩罚越大。

由于时凸二次规划问题，同样通过求对偶问题来求解。

$（w,b, {\xi}）$的解存在，且可以证明w 的解唯一，b的解在一个区间内。
非线性支持向量机
我们总是希望通过一个非线性变化，将非线性问题转化为线性可分问题来求解。
当输入空间为欧式空间或离散集合、特征空间为希尔伯特空间时，核函数表示将输入从输入空间映射到特征空间得到的特征向量之间的内积。通过核方法可以学习非线性支持向量机，等价于在高维的特征空间中学习线性支持向量机。
通俗点理解就是，当我们的数据在其本身的空间里面没办法做到线性可分的时候，我们把他们以某种方式映射到高维空间，以期实现在高维中间线性可分。这样操作的要点是要选择合适的映射方式，也是就是要选对核函数。
举两个例子：





可以看到，原本在低维不可分的数据，映射到高维之后，就变得线性可分了。

再搬两张图，数据来源:https://www.zhihu.com/question/27210162





好了，解决问题的关键就在于核函数，关于核函数的定义如下：


我们可以这样想（当然理论上不一定对），对于$x_i^Tx_j$我们首先将其看作是两个映射函数在作内积，于是我们将其看作是一个映射至希尔伯特空间的线性核（因为线性核就是这样定义的），我们再将线性核替换成其他的核，实现在希尔伯特空间的变换，完成映射任务。
于是，对于对偶问题中的$x_i^Tx_j$，我们可以将其替换成合适的核函数$k(x_i^Tx_j)$,实现非线性数据的高维线性可分。

一般使用以下几种核函数：


SMO
序列最小最优化算法SMO可以实现SVM的高效学习。

他将凸二次规划的对偶问题不断的分解为子问题并求解，进而达到求解原问题的目的。

参考文章：https://blog.csdn.net/luoshixian099/article/details/51227754
###############################

一些延展:
我们可以在这里从损失函数的角度看一下LR与SVM的异同:
对于LR与SVM的异同我总结如下:
LR的详细介绍:https://blog.csdn.net/b285795298/article/details/88683987
- 相同点:

LR和SVM都是分类算法
LR和SVM都是监督学习算法。
LR和SVM都是判别模型。
如果不考虑核函数，LR和SVM都是线性分类算法，也就是说他们的分类决策面都是线性的。

说明:LR也是可以用核函数的.但LR通常不采用核函数的方法.(计算量太大)

LR和SVM不同点:
1、LR采用log损失，SVM采用合页(hinge)损失。

逻辑回归的损失函数：



支持向量机的目标函数:



​逻辑回归方法基于概率理论，假设样本为1的概率可以用sigmoid函数来表示，然后通过极大似然估计的方法估计出参数的值(基于统计的,其损失函数是人为设定的凸函数) 。支持向量机​基于几何间隔最大化原理，认为存在最大几何间隔的分类面为最优分类面.(有严格的推导)
2、LR对异常值敏感，SVM对异常值不敏感(抗燥能力,SVM要强)(https://www.jianshu.com/p/1a41a1567b87)。支持向量机只考虑局部的边界线附近的点，而逻辑回归考虑全局（远离的点对边界线的确定也起作用，虽然作用会相对小一些）。LR模型找到的那个超平面，是尽量让所有点都远离他，而SVM寻找的那个超平面，是只让最靠近中间分割线的那些点尽量远离，即只用到那些支持向量的样本。
支持向量机改变非支持向量样本并不会引起决策面的变化：

逻辑回归中改变任何样本都会引起决策面的变化：

LR则受所有数据点的影响，如果数据不同类别strongly unbalance，一般需要先对数据做balancing。​（引自http://www.zhihu.com/question/26768865/answer/34078149）
3、计算复杂度不同。对于海量数据，SVM的效率较低，LR效率比较高。 对于两者在feature和样本数量不同的情况下的效率问题,可以参考:https://blog.csdn.net/a244659184/article/details/81122521。该文章说明了:
当样本较少，特征维数较低时，SVM和LR的运行时间均比较短，SVM较短一些。准确率的话，LR明显比SVM要高。当样本稍微增加些时，SVM运行时间开始增长，但是准确率赶超了LR。SVM时间虽长，但在接收范围内。当数据量增长到20000时，特征维数增长到200时，SVM的运行时间剧烈增加，远远超过了LR的运行时间。但是准确率却和LR相差无几。(这其中主要原因是大量非支持向量参与计算,造成SVM的二次规划问题)
4、对非线性问题的处理方式不同，LR主要靠特征构造，必须组合交叉特征，特征离散化。SVM也可以这样，还可以通过kernel(因为只有支持向量参与核计算,计算复杂度不高)。(由于可以利用核函数,。SVM则可以通过对偶求解高效处理。LR则在特征空间维度很高时，表现较差。)
5、SVM的损失函数就自带正则！！！（损失函数中的1/2||w||^2项），这就是为什么SVM是结构风险最小化算法的原因！！！而LR必须另外在损失函数上添加正则项！！！



关于正则化:

给定一个数据集，一旦完成Linear SVM的求解，所有数据点可以被归成两类

1）一类是落在对应分界平面外并被正确分类的点，比如落在正分界左侧的正样本或落在负分界右侧的负样本

2）第二类是落在gap里或被错误分类的点。



假设一个数据集已经被Linear SVM求解，那么往这个数据集里面增加或者删除更多的一类点并不会改变重新求解的Linear SVM平面。这就是它区分与LR的特点，下面我们在看看LR。
值得一提的是求解LR模型过程中，每一个数据点对分类平面都是有影响的，它的影响力远离它到分类平面的距离指数递减。换句话说，LR的解是受数据本身分布影响的。在实际应用中，如果数据维度很高，LR模型都会配合参数的L1 regularization。

关于l1,l2正则化的深入介绍，推荐：https://blog.csdn.net/weixin_41481113/article/details/84304035
要说有什么本质区别，那就是两个模型对数据和参数的敏感程度不同，Linear SVM比较依赖penalty的系数和数据表达空间的测度，而（带正则项的）LR比较依赖对参数做L1 regularization的系数。但是由于他们或多或少都是线性分类器，所以实际上对低维度数据overfitting的能力都比较有限，相比之下对高维度数据，LR的表现会更加稳定，为什么呢？

因为Linear SVM在计算margin有多“宽”的时候是依赖数据表达上的距离测度(可以理解为度量标准,即在什么样的标准上计算gap的大小)的，换句话说如果这个测度不好（badly scaled，这种情况在高维数据尤为显著），所求得的所谓Large margin就没有意义了，这个问题即使换用kernel trick（比如用Gaussian kernel）也无法完全避免。所以使用Linear SVM之前一般都需要先对数据做normalization，(这里的normalization是对数据的归一化,注意区分之前的LR在类别不平衡的时候做的balancing)而求解LR（without regularization）时则不需要或者结果不敏感。

同时会有：feature scaling会使得gradient descent的收敛更好。

如果不归一化，各维特征的跨度差距很大，目标函数就会是“扁”的：


（图中椭圆表示目标函数的等高线，两个坐标轴代表两个特征）

这样feature scaling之后，在进行梯度下降的时候，梯度的方向就会偏离最小值的方向，走很多弯路。

如果归一化了，那么目标函数就“圆”了：

每一步梯度的方向都基本指向最小值，可以大踏步地前进。（引自https://www.zhihu.com/question/37129350）
向您推荐我的其他文章:
支持向量机（SVM）从入门到放弃再到掌握 :https://blog.csdn.net/b285795298/article/details/81977271
逻辑回归(Logistic Regression-LR)从入门到放弃再到掌握 :https://blog.csdn.net/b285795298/article/details/88683987
决策树（decesion Tree）从入门到放弃再到掌握 :https://blog.csdn.net/b285795298/article/details/89086854
随机森林(Random Forest) 从入门到放弃再到掌握:https://blog.csdn.net/b285795298/article/details/89084257
#######################################################
参考博文：

机器学习中的线性代数之矩阵求导 https://blog.csdn.net/u010976453/article/details/54381248

周志华老师的《机器学习》

参考:：https://www.jianshu.com/p/e8dca5613da6

https://www.jianshu.com/p/1a41a1567b87

https://www.cnblogs.com/bentuwuying/p/6616761.html

https://blog.csdn.net/zwqjoy/article/details/82312783

文章目录
1. SVM
1.1 SVM 基本概念
1.2 hard-margin SVM
1.3 SVM 应用实例
2. 核方法
使用核方法的动机
常用的核函数（kernel functions）
核函数举例
相关概念补充
线性可区分和线性不可区分
SVM 可扩展到多分类问题
SVM 算法特性


机器学习的一般框架：

训练集 => 提取特征向量 => 结合一定的算法（分类器：比如决策树、KNN）=>得到结果

1. SVM
支持向量机（support vector machines，SVM）是一种二分类模型，它将实例的特征向量映射为空间中的一些点，SVM 的目的就是想要画出一条线，以 “最好地” 区分这两类点，以至如果以后有了新的点，这条线也能做出很好的分类。SVM 适合中小型数据样本、非线性、高维的分类问题。
SVM 最早是由 Vladimir N. Vapnik 和 Alexey Ya. Chervonenkis 在1963年提出，目前的版本（soft margin）是由 Corinna Cortes 和 Vapnik 在1993年提出，并在1995年发表。深度学习（2012）出现之前，SVM 被认为机器学习中近十几年来最成功，表现最好的算法。
1.1 SVM 基本概念
将实例的特征向量（以二维为例）映射为空间中的一些点，如下图的实心点和空心点，它们属于不同的两类。SVM 的目的就是想要画出一条线，以“最好地”区分这两类点，以至如果以后有了新的点，这条线也能做出很好的分类。



Q1：能够画出多少条线对样本点进行区分？

答：线是有无数条可以画的，区别就在于效果好不好，每条线都可以叫做一个划分超平面。比如上面的绿线就不好，蓝线还凑合，红线看起来就比较好。我们所希望找到的这条效果最好的线就是具有 “最大间隔的划分超平面”。
Q2：为什么要叫作“超平面”呢？

答：因为样本的特征很可能是高维的，此时样本空间的划分就不是一条线了。
Q3：画线的标准是什么？/ 什么才叫这条线的效果好？/ 哪里好？

答：SVM 将会寻找可以区分两个类别并且能使间隔（margin）最大的划分超平面。比较好的划分超平面，样本局部扰动时对它的影响最小、产生的分类结果最鲁棒、对未见示例的泛化能力最强。
Q4：间隔（margin）是什么？

答：对于任意一个超平面，其两侧数据点都距离它有一个最小距离（垂直距离），这两个最小距离的和就是间隔。比如下图中两条虚线构成的带状区域就是 margin，虚线是由距离中央实线最近的两个点所确定出来的（也就是由支持向量决定）。但此时 margin 比较小，如果用第二种方式画，margin 明显变大也更接近我们的目标。



Q5：为什么要让 margin 尽量大？

答：因为大 margin 犯错的几率比较小，也就是更鲁棒啦。
Q6：支持向量是什么？

答：从上图可以看出，虚线上的点到划分超平面的距离都是一样的，实际上只有这几个点共同确定了超平面的位置，因此被称作 “支持向量（support vectors）”，“支持向量机” 也是由此来的。
1.2 hard-margin SVM


划分超平面可以定义为一个线性方程：$w^TX+b=0$，其中：

$w = \{w_1;w_2;...;w_d\}$ 是一个法向量，决定了超平面的方向，$d$ 是特征值的个数
$X$ 为训练样本
$b$ 为位移项，决定了超平面与原点之间的距离

只要确定了法向量 $w$ 和位移 $b$，就可以唯一地确定一个划分超平面。划分超平面和它两侧的边际超平面上任意一点的距离为 $\frac{1}{||w||}$。
利用一些数学推导，公式 $y_i*(w_0+w_1x_1+w_2x_2)\geq1,\ \forall i$ 可变为有限制的凸优化问题(convex quadratic optimization)
利用 Karush-Kuhn-Tucker (KKT)条件和拉格朗日公式，可以推出 MMH 可以被表示为以下“决定边界 (decision boundary)”

$d(X^T)=\sum_{i=1}^ly_i\alpha_iX_iX^T+b_0$

此方程就代表了边际最大化的划分超平面。

$l$ 是支持向量点的个数，因为大部分的点并不是支持向量点，只有个别在边际超平面上的点才是支持向量点。那么我们就只对属于支持向量点的进行求和；
$X_i$ 为支持向量点的特征值；
$y_i$ 是支持向量点$X_i$的类别标记（class label)，比如+1还是-1；
$X^T$ 是要测试的实例，想知道它应该属于哪一类，把它带入该方程
$\alpha _i$ 和 $b_0$ 都是单一数值型参数，由以上提到的最优算法得出，$\alpha _i$ 是拉格朗日乘数。

每当有新的测试样本 $X$，将它带入该方程，看看该方程的值是正还是负，根据符号进行归类。
1.3 SVM 应用实例
看一下 SVM 如何求出一个划分超平面。
我们已经知道了两个支持向量点（1,1）和（2,3），设置权重为 $w = (a,2a)$，那么将这两个支持向量点坐标分别带入公式 $w^Tx+b=\pm1$ 中，可以得到：

$a+2a+w_0=-1,\ \ \ using\ point\ (1,1)$

$2a+6a+w_0=1,\ \ \ using \ point\ (2,3)$

那么未知数就是 $a$ 和 $w_0$，解方程组可得：$a=\frac{2}{5}$，$w_0=-\frac{11}{5}$

带回到权重向量 $w$ 中有：$w=(a,2a)=(\frac{2}{5},\frac{4}{5})$

那么划分超平面为 $x_1+2x_2-5.5=0$

最后可以用点（2,0）验证一下这个划分超平面的分类效果。
由于 SVM 算法本身的实现非常复杂，所以不研究如何实现 SVM，而是采用 sklearn 库来学习 SVM 的应用问题。
# sklearn 库中导入 svm 模块
from sklearn import svm

# 定义三个点和标签
X = [[2, 0], [1, 1], [2,3]]
y = [0, 0, 1]
# 定义分类器，clf 意为 classifier，是分类器的传统命名
clf = svm.SVC(kernel = 'linear')  # .SVC（）就是 SVM 的方程，参数 kernel 为线性核函数
# 训练分类器
clf.fit(X, y)  # 调用分类器的 fit 函数建立模型（即计算出划分超平面，且所有相关属性都保存在了分类器 cls 里）
# 打印分类器 clf 的一系列参数
print(clf)
# 支持向量
print(clf.support_vectors_)
# 属于支持向量的点的 index 
print(clf.support_)
# 在每一个类中有多少个点属于支持向量
print(clf.n_support_) 
# 预测一个新的点
print(clf.predict([[2,0]]))

输出结果：
# 打印分类器 clf 的一系列参数
SVC(C=1.0, cache_size=200, class_weight=None, coef0=0.0,
  decision_function_shape='ovr', degree=3, gamma='auto_deprecated',
  kernel='linear', max_iter=-1, probability=False, random_state=None,
  shrinking=True, tol=0.001, verbose=False)
# 支持向量
[[1. 1.]
 [2. 3.]]
# 属于支持向量的点的 index
[1 2]
# 在每一个类中有多少个点属于支持向量
[1 1]
# 预测一个新的点
[0]

print(__doc__)
# 导入相关的包
import numpy as np
import pylab as pl  # 绘图功能
from sklearn import svm

# 创建 40 个点
np.random.seed(0) # 让每次运行程序生成的随机样本点不变
# 生成训练实例并保证是线性可分的
# np._r表示将矩阵在行方向上进行相连
# random.randn(a,b)表示生成 a 行 b 列的矩阵，且随机数服从标准正态分布
# array(20,2) - [2,2] 相当于给每一行的两个数都减去 2
X = np.r_[np.random.randn(20, 2) - [2, 2], np.random.randn(20, 2) + [2, 2]]
# 两个类别 每类有 20 个点，Y 为 40 行 1 列的列向量
Y = [0] * 20 + [1] * 20

# 建立 svm 模型
clf = svm.SVC(kernel='linear')
clf.fit(X, Y)

# 获得划分超平面
# 划分超平面原方程：w0x0 + w1x1 + b = 0
# 将其转化为点斜式方程，并把 x0 看作 x，x1 看作 y，b 看作 w2
# 点斜式：y = -(w0/w1)x - (w2/w1)
w = clf.coef_[0]  # w 是一个二维数据，coef 就是 w = [w0,w1]
a = -w[0] / w[1]  # 斜率
xx = np.linspace(-5, 5)  # 从 -5 到 5 产生一些连续的值（随机的）
# .intercept[0] 获得 bias，即 b 的值，b / w[1] 是截距
yy = a * xx - (clf.intercept_[0]) / w[1]  # 带入 x 的值，获得直线方程

# 画出和划分超平面平行且经过支持向量的两条线（斜率相同，截距不同）
b = clf.support_vectors_[0] # 取出第一个支持向量点
yy_down = a * xx + (b[1] - a * b[0]) 
b = clf.support_vectors_[-1] # 取出最后一个支持向量点
yy_up = a * xx + (b[1] - a * b[0])

# 查看相关的参数值
print("w: ", w)
print("a: ", a)
print("support_vectors_: ", clf.support_vectors_)
print("clf.coef_: ", clf.coef_)

# 在 scikit-learin 中，coef_ 保存了线性模型中划分超平面的参数向量。形式为(n_classes, n_features)。若 n_classes > 1，则为多分类问题，(1，n_features) 为二分类问题。

# 绘制划分超平面，边际平面和样本点
pl.plot(xx, yy, 'k-')
pl.plot(xx, yy_down, 'k--')
pl.plot(xx, yy_up, 'k--')
# 圈出支持向量
pl.scatter(clf.support_vectors_[:, 0], clf.support_vectors_[:, 1],
           s=80, facecolors='none')
pl.scatter(X[:, 0], X[:, 1], c=Y, cmap=pl.cm.Paired)

pl.axis('tight')
pl.show()

输出结果：
Automatically created module for IPython interactive environment
w:  [0.90230696 0.64821811]
a:  -1.391980476255765
support_vectors_:  [[-1.02126202  0.2408932 ]
 [-0.46722079 -0.53064123]
 [ 0.95144703  0.57998206]]
clf.coef_:  [[0.90230696 0.64821811]]


2. 核方法
使用核方法的动机
在线性 SVM 中转化为最优化问题时求解的公式计算都是以内积(dot product)形式出现的，其中 $\phi(X)$ 是把训练集中的向量点转化到高维的非线性映射函数，因为内积的算法复杂度非常大，所以我们利用核函数来取代计算非线性映射函数的内积。
以下核函数和非线性映射函数的内积等同，但核函数 K 的运算量要远少于求内积。

$K(X_i,X_j)=\phi(X_i)·\phi(X_j)$
常用的核函数（kernel functions）
h 度多项式核函数(polynomial kernel of degree h)：

$K(X_i,X_j)=(X_i,X_j+1)^h$
高斯径向基核函数(Gaussian radial basis function kernel)：

$K(X_i,X_j)=e^{-||X_i-X_j||^2/2\sigma^2}$
S 型核函数(Sigmoid function kernel)：

$K(X_i,X_j)=tanh(kX_i·X_j-\delta)$
如何选择使用哪个 kernel ？

根据先验知识，比如图像分类，通常使用 RBF（高斯径向基核函数），文字不使用 RBF。
尝试不同的 kernel，根据结果准确度而定尝试不同的 kernel，根据结果准确度而定。

核函数举例
假设定义两个向量：$x = (x_1, x_2, x_3)$，$y = (y_1, y_2, y_3)$
定义方程：

$f(x) = (x_1x_1, x_1x_2, x_1x_3, x_2x_1, x_2x_2, x_2x_3, x_3x_1, x_3x_2, x_3x_3)$
核函数：$K(x,y ) = (<x,y>)^2$
假设：$x = (1, 2, 3)$，$y = (4, 5, 6)$
不用核函数，直接求内积：

$f(x) = (1, 2, 3, 2, 4, 6, 3, 6, 9)$

$f(y) = (16, 20, 24, 20, 25, 36, 24, 30, 36)$

$<f(x), f(y)> = 16 + 40 + 72 + 40 + 100+ 180 + 72 + 180 + 324 = 1024$
使用核函数：

$K(x, y) = (4  + 10 + 18 ) ^2 = 32^2 = 1024$
同样的结果，使用 kernel 方法计算容易很多。而这只是 9 维的情况，如果维度更高，那么直接求内积的方法运算复杂度会非常大。
所以使用 kernel 的意义在于：

将向量的维度从低维映射到高维
降低运算复杂度降低运算复杂度

相关概念补充
线性可区分和线性不可区分
能够用一条直线对样本点进行分类的属于线性可区分（linear separable），否则为线性不可区分（linear inseparable)。
以下三个例子，都是线性不可区分的，即无法用一条直线将两类样本点区分开。







而刚才的例子就是线性可区分的。



在线性不可分的情况下，数据集在空间中对应的向量无法被一个超平面区分开，如何处理？
：两个步骤来解决：

利用一个非线性的映射把原数据集中的向量点转化到一个更高维度的空间中（比如下图将二维空间中的点映射到三维空间）
在这个高维度的空间中找一个线性的超平面来根据线性可分的情况处理



比如想要将红点和蓝点变成线性可分的，那么就将映射 $y=x$ 变成映射 $y=x^2$，这样就线性可分了。





视觉化演示：https://www.youtube.com/watch?v=3liCbRZPrZA

如何利用非线性映射将原始数据转化到高维空间中去？
例子：

有一个 3 维输入向量：$X=(x_1,x_2,x_3)$
将其转化到 6 维空间 Z 中去：

$\phi_1(X)=x_1，\phi_2(X)=x_2，\phi_3(X)=x_3，\phi_4(X)=(x_1)^2，\phi_5(X)=x_1x_2，and\ \phi_6(X)=x_1x_3$

新的决策超平面：$d(Z)=WZ+b$，其中 W 和 Z 是向量，这个超平面是线性的。
解出 W 和 b 之后，并且带入回原方程：

$d(Z)=w_1x_1+w_2x_2+w_3x_3+w_4(x_1)^2+w_5x_1x_2+w_6x_1x_3+b=w_1z_1+w_2z_2+w_3z_3+w_4z_4+w_5z_5+w_6z_6+b$
思考问题：

如何选择合理的非线性转化把数据转到高维空间中？
如何解决计算内积时算法复杂度非常高的问题？

：使用核方法（kernel trick)
SVM 可扩展到多分类问题
SVM 扩展可解决多个类别分类问题：

对于每个类，有一个当前类和其他类的二类分类器（one-vs-rest）

将多分类问题转化为 n 个二分类问题，n 就是类别个数。
SVM 算法特性

训练好的模型的算法复杂度是由支持向量的个数决定的，而不是由数据的维度决定的。所以 SVM 不太容易产生 overfitting。
SVM 训练出来的模型完全依赖于支持向量，即使训练集里面所有非支持向量的点都被去除，重复训练过程，结果仍然会得到完全一样的模型。
一个 SVM 如果训练得出的支持向量个数比较少，那么SVM 训练出的模型比较容易被泛化。