⽀持向量机（SVM）原理详解
SVM简介
  ⽀持向量机（support vector machines, SVM）是⼀种⼆分类模型，它的基本模型是定义在特征空间上的间隔最⼤的线性分类器，间隔最⼤使它有别于感知机；SVM还包括核技巧，这使它成为实质上的⾮线性分类器。SVM的的学习策略就是间隔最⼤化，可形式化为⼀个求解凸⼆次规划的问题，也等价于正则化的合页损失函数的最⼩化问题。SVM的的学习算法就是求解凸⼆次规划的最优化算法。
⼀、⽀持向量与超平⾯
在了解svm算法之前，我们⾸先需要了解⼀下线性分类器这个概念。⽐如给定⼀系列的数据样本，每个样本都有对应的⼀个标签。为了使得描述更加直观，我们采⽤⼆维平⾯进⾏解释，⾼维空间原理也是⼀样。举个简单⼦：如下图所⽰是⼀个⼆维平⾯，平⾯上有两类不同的数据，分别⽤圆圈和⽅块表⽰。我们可以很简单地到⼀条直线使得两类数据正好能够完全分开。但是能将据点完全划开直线不⽌⼀条，那么在如此众多的直线中我们应该选择哪⼀条呢？从直观感觉上看图中的⼏条直线，是不是要更好⼀些呢？是的，我们就是希望寻到这样的直线，使得距离这条直线最近的点到这条直线的距离最短。这读起来有些拗⼝，我们从如下右图直观来解释这⼀句话就是要求的两条外⾯的线之间的间隔最⼤。这是可以理解的，因为假如数据样本是随机出现的，那么这样分割之后数据点落⼊到其类别⼀侧的概率越⾼那么最终预测的准
确率也会越⾼。在⾼维空间中这样的直线称之为超平⾯，因为当维数⼤于三的时候我们已经⽆法想象出这个平⾯的具体样⼦。那些距离这个超平⾯最近的点就是所谓⽀持向量，实际上如果确定了⽀持向量也就确定了这个超平⾯，到这些⽀持向量之后其他样本就不会起作⽤了。
⼆、SVM算法原理
  2.1 点到超平⾯的距离公式
既然这样的直线是存在的，那么我们怎样寻出这样的直线呢？与⼆维空间类似，超平⾯的⽅程也可以写成⼀下形式：
（1）
  有了超平⾯的表达式之后之后，我们就可以计算样本点到平⾯的距离了。假设为样本的中的⼀个点，其中表⽰为第个特征变量。那么该点到超平⾯的距离就可以⽤如下公式进⾏计算：
（2）
  其中||W||为超平⾯的范数，常数b类似于直线⽅程中的截距。
  上⾯的公式可以利⽤解析⼏何或⾼中平⾯⼏何知识进⾏推导，这⾥不做进⼀步解释。
  2.2 最⼤间隔的优化模型
现在我们已经知道了如何去求数据点到超平⾯的距离，在超平⾯确定的情况下，我们就能够出所有⽀
持向量，然后计算出间隔margin。每⼀个超平⾯都对应着⼀个margin，我们的⽬标就是出所有margin中最⼤的那个值对应的超平⾯。因此⽤数学语⾔描述就是确定w、b使得margin最⼤。这是⼀个优化问题其⽬标函数可以写成：
（3）
  其中表⽰数据点的标签，且其为-1或1。距离⽤计算，这是就能体会出-1和1的好处了。如果数据点在平⾯的正⽅向(即+1类)那么是⼀个正数，⽽当数据点在平⾯的负⽅向时(即-1类)，依然是⼀个正数，这样就能够保证始终⼤于零了。注意到当w和b等⽐例放⼤时，d的结果是不会改变的。因此我们可以令所有⽀持向量的u为1，⽽其他点的u⼤1这是可以办通过调节w和b求到的。因此上⾯的问题可以简化为：
（4）
  为了后⾯计算的⽅便，我们将⽬标函数等价替换为：
(5）
  这是⼀个凸⼆次规划问题。能直接⽤现成的优化计算包求解，但我们可以有更⾼效的办法。
  2.3 学习的对偶算法
  为了求解线性可分⽀持向量机的最优化问题，将它作为原始最优化问题，应⽤拉格朗⽇对偶性，通过求解对偶问题得到原始问题的最优解，这就是线性可分⽀持向量的对偶算法。这样的优点：
对偶问题往往更容易求解
⾃然引⼊核函数，进⽽推⼴到⾮线性分类问题
改变了问题的复杂度。由求特征向量w转化为求⽐例系数a，在原始问题下，求解的复杂度与样本的维度有关，即w的维度。在对偶问题下，只与样本数量有关。
  ⾸先构建拉格朗⽇函数。为此，对每个不等式约束引进拉格朗⽇乘⼦$a_{i}\geq 0,i=1,2,...,N$，定义拉格朗⽇函数：
L(w,b,a)=1
2‖  （6）
  其中a_{i}> 0。
  根据拉格朗⽇函数对偶性，原始问题的对偶问题是极⼤极⼩问题：
max_{a}min_{w,b}L(w,b,a)（7）
  所以，为了求解问题的解，需要先求求L(w,b,a)对w,b的极⼩，再求对a的极⼤。 
  (1) 求min_{w,b}L(w,b,a)
  将拉格朗⽇函数L(w,b,a)分别对w,b求偏导数令其等于0：
\bigtriangledown _{w}L(w,b,a)=w-\sum_{i=1}^{N}a_{i}y_{i}x_{i}=0  （8）
\bigtriangledown _{b}L(w,b,a)=\sum_{i=1}^{N}a_{i}y_{i}=0  （9）
  得：
w=\sum_{i=1}^{N}a_{i}y_{i}x_{i}（10）
\sum_{i=1}^{N}a_{i}y_{i}=0（11)
  将式(10)代⼊拉格朗⽇函数(6)并利⽤式(11)，即得：
L(w,b,a)=\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}a_{i}a_{j}y_{i}y_{j}(x_{i}x_{j})-\sum_{i=1}^{N}a_{i}\left [ y_{i} \right ((\sum_{j=1}^{N}a_{i}y_{j}x_{j})x_{i}+b)-1]+\sum_{i=1}^{N}a_{i} =-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}a_{i}a_{j}y_{i}y_{j}(x_{i}\cdot
x_{j})+\sum_{i=1}^{N}a_{i}  (12)
  (2) 求max_{w,b}L(w,b,a)对a的极⼤
max_{a} \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}a_{i}a_{j}y_{i}y_{j}(x_{i}\cdot x_{j})+\sum_{i=1}^{N}a_{i}  (13)
  subject to
\sum_{i=1}^{N}a_{i}y_{i}=0
a_{i}\geq 0,i=1,2,...,N
  将上式的⽬标函数由极⼤转换成极⼩，就得到下⾯与之等价的对偶最优化问题：
min_{a} \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}a_{i}a_{j}y_{i}y_{j}(x_{i}\cdot x_{j})+\sum_{i=1}^{N}a_{i}  (14)
  subject to
\sum_{i=1}^{N}a_{i}y_{i}=0
a_{i}\geq 0,i=1,2,...,N
  从对偶问题解出的是原式中的拉格朗⽇乘⼦。注意到原式中有不等式约束，因此上述过程需要满⾜KKT条件，即要求：
\left\{\begin{matrix} a_{i}\geq 0\\  y_{i}f(x_{i})-1\geq 0\\  a_{i}(y_{i}f(x_{i})-1)=0 \end{matrix}\right.  (15)
  于是，对于训练数据(x_{i},y_{i})，总有a_{i}=0或y_{i}f(x_{i})=1。若a_{i}=0，则该样本不会出现在上述求和公式中，也就不会对f(x)产⽣任何影响；若a_{i}>0则必有y_{i}f(x_{i})=1，所对应样本点位于最⼤间
隔上，是⼀个⽀撑向量。这⾥显⽰出⽀持向量机的⼀个重要性质：训练完成后，⼤部分的训练样本都不需保留，最终模型仅与⽀持向量相关。
  那么如何求解式(14)不难发现，这是⼀个⼆次规划问题，可使⽤通⽤的⼆次规划算法求解；然⽽，该问题的规模正⽐于训练样本数，这会在实际任务中造成很⼤的开销。为了避开这个障碍，⼈们通过利⽤问题本⾝的特性，提出了很多⾼校的算法，SMO(Sequential Minimal Optimization)是其中⼀个著名的代表。
  2.4 松弛变量
由上⼀节的分析我们知道实际中很多样本数据都不能够⽤⼀个超平⾯把数据完全分开。如果数据集中存在噪点的话，那么在求超平的时候就会出现很⼤问题。从下图中可以看出其中⼀个蓝点偏差太⼤，如果把它作为⽀持向量的话所求出来的margin就会⽐不算⼊它时要⼩得多。更糟糕的情况是如果这个蓝点落在了红点之间那么就不出超平⾯了。
  因此引⼊⼀个松弛变量ξ来允许⼀些数据可以处于分隔⾯错误的⼀侧。这时新的约束条件变为:
（16）
  式中ξi的含义为允许第i个数据点允许偏离的间隔。如果让ξ任意⼤的话，那么任意的超平⾯都是符合条件的了。所以在原有⽬标的基础之上，我们也尽可能的让ξ的总量也尽可能地⼩。所以新的⽬标函数变为：
（17）
（18）
  其中的C是⽤于控制“最⼤化间隔”和“保证⼤部分的点的函数间隔都⼩于1”这两个⽬标的权重。将上述模型完整的写下来就是：
（19）
  新的拉格朗⽇函数变为：
（20）
  接下来将拉格朗⽇函数转化为其对偶函数，⾸先对分别求ξ的偏导，并令其为0，结果如下：
（21）
  代⼊原式化简之后得到和原来⼀样的⽬标函数：
（22）
  但是由于我们得到⽽，因此有所以对偶问题写成：
（23）正则化其实是破坏最优化
  经过添加松弛变量的⽅法，我们现在能够解决数据更加混乱的问题。通过修改参数C，我们可以得到不同的结果⽽C的⼤⼩到底取多少⽐较合适，需要根据实际问题进⾏调节。
  2.5核函数
以上讨论的都是在线性可分情况进⾏讨论的，但是实际问题中给出的数据并不是都是线性可分的，⽐如有些数据可能是如下图样⼦。
  那么这种⾮线性可分的数据是否就不能⽤svm算法来求解呢？答案是否定的。事实上，对于低维平⾯内不可分的数据，放在⼀个⾼维空间中去就有可能变得可分。以⼆维平⾯的数据为例，我们可以通过到⼀个映射将⼆维平⾯的点放到三维平⾯之中。理论上任意的数据样本都能够到⼀个合适的映射使得这些在低维空间不能划分的样本到⾼维空间中之后能够线性可分。我们再来看⼀下之前的⽬标函数：
（24）
  定义⼀个映射使得将所有映射到更⾼维空间之后等价于求解上述问题的对偶问题：
（25）
  这样对于线性不可分的问题就解决了，现在只需要出⼀个合适的映射即可。当特征变量⾮常多的时候在，⾼维空间中计算内积的运算量是⾮常庞⼤的。考虑到我们的⽬的并不是为到这样⼀个映射⽽是为了计算其在⾼维空间的内积，因此如果我们能够到计算⾼维空间下
内积的公式，那么就能够避免这样庞⼤的计算量，我们的问题也就解决了。实际上这就是我们要的核函数，即两个向量在隐式映射后的空间中的内积。下⾯的⼀个简单例⼦可以帮助我们更好地理解核函数。
  通过以上例⼦，我们可以很明显地看到核函数是怎样运作的。上述问题的对偶问题可以写成如下形式：
（26）
  那么怎样的函数才可以作为核函数呢？下⾯的⼀个定理可以帮助我们判断。
  Mercer定理：任何半正定的函数都可以作为核函数。其中所谓半正定函数是指拥有训练集数据集合，我们定义⼀个矩阵的元素，这个矩阵是的矩阵，如果这个矩阵是半正定的，那么就称为半正定函数。
  值得注意的是，上述定理中所给出的条件是充分条件⽽⾮充要条件。因为有些⾮正定函数也可以作为核函数。
  下⾯是⼀些常⽤的核函数：
核函数名称核函数表达式核函数名称核函数表达式
线性核指数核
多项式核拉普拉斯核
⾼斯核Sigmoid核
现在我们已经了解了⼀些⽀持向量机的理论基础，我们通过对偶问题的的转化将最开始求的问题转化为求的对偶问题。只要到所
有的(即出所有⽀持向量)，我们就能够确定。然后就可以通过计算数据点到这个超平⾯的距离从⽽判断出该数据点的类别。
三、SMO 算法
  SMO算法是⽀持向量机学习的⼀种快速算法，其特点是不断地将原⼆次规划问题分解为只有两个变量的⼆次规划⼦问题，并对⼦问题进⾏解析求解，知道所有变量满⾜KKT条件为⽌。这样通过启发式的⽅法得到原⼆次规划问题的最优解。因为⼦问题有解析解，所以每次计算⼦问题都很快，虽然计算⼦问题次数很多，但在总体上还是⾼效的。
参考
《统计学习⽅法（第2版）》李航著
Processing math: 0%

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。