SVM是一种有监督的统计学习方法，能够最小化经验误差和最大化几何边缘，被称为最大间隔分类器，可用于分类和回归分析。

一、基本原理

     SVM是一个机器学习的过程，在高维空间中寻找一个分类超平面，将不同类别的数据样本点分开，使不同类别的点之间的间隔最大，该分类超平面即为最大间隔超平面，对应的分类器称为最大间隔分类器，对于二分类问题，下图可描述SVM的空间特征。 

      假设数据样本为x₁,x₂,...,x_n,分类超平面可表示为：w^Tx-b=0.其中x为分类超平面上的点；w为垂直于分类超平面的向量；b为位移量，用于改善分类超平面的灵活性，超平面不用必须通过原点。

      两个分类超平面之间具有最大间隔，需要知道训练样本中的支撑向量、距离支撑向量最近的平行超平面，这些超平面可表示为：

w^Tx-b=1

w^Tx-b=-1

      其中，w是分类超平面的法向量，长度未定;1和-1只是为了计算方便而取的常量，其他常量只要互为相反数即可。

      如果给定的训练样本是线性可分的，那么就可以找到两个间距最大的平行超平面，并且这两个超平面之间没有任何训练样本，它们之间的距离为2/||w||².所以最小化||w||²，就可以使这两个超平面之间的间隔最大化。

      为了使所有训练样本点在上述两个平行需要超平面间隔区域以外，我们确保所有的训练数据样本点x₁,x₂,...,x_n都满足以下条件之一，即

w^Tx_i-b≥1

w^Tx_i-b≤-1

二、算法改进

      假定问题的目标函数及其约束条件如下：  

max(1/||w||)

                     s.t.  y_i(w^Tx_i+b)≥1  i=1,...,n

     求解1/||w||的最大值，相当于求解（1/2）||w||^{2的最小值，所以上述问题可以等价于如下约束不等式：}  

^{min（1/2）||w||2}

                  s.t.  y_i(w^Tx_i+b)≥1  i=1,...,n

     通过将目标函数转化，求解SVM可以变成一个标准的凸优化问题。因为目标函数是二次的，而约束条件是线性的，所以这是一个凸二次规划问题。虽然这个问题是一个标准的二次规划问题，但同时具有它的特殊结构，通过Langrang对偶变换为对偶变量的优化问题后，可以找到一种更加有效的方法进行求解。

     通过对每个约束条件加一个拉格朗日乘值，即引入拉格朗日乘子，可以通过拉格朗日函数将约束条件融入到目标函数之中。

L（w,b,α）=（1/2）||w||²-∑α_i(y_i(w^Tx_i+b)-1)

     令：θ(w)=max L（w,b,α）（α_i≥0）

     当某个约束条件不满足时，如：y_i(w^Tx_i+b)<1   那么有：θ(w)=∞

     当所有约束条件都满足时，则：θ(w)=（1/2）||w||²   即为最初要最小化的变量。

     在要求约束条件得到满足情况下最小化（1/2）||w||²，实际上等价于最小化θ(w)。因为如果约束条件没有得到满足，θ(w)就会等于无穷大，不会是所要求的最小值，则目标函数变为：

     用p*表示这个问题的最优值，这个问题和最初的问题是等同的。通过把最小和最大的位置对换，可以获得：

     交换后不再等价于原来的问题，这个新问题的最优值用q*来表示，并且q*<p*,因为最大一个值中最小的一个比最小值中最大的要大。第二个问题的最优解q*提供第一个问题的最优解p*的一个下界，在满足某些条件的情况下，这两者相等，可以通过求解第二个问题间接求解第一个问题。

      因此，可以通过先求L对w,b的极小，再求L对α的极大。之所以从最小和最大化的原始问题p*转化为最大和最小化的对偶问题q*，是因为q*是p*的近似解，转化为对偶问题后，求解过程更容易。

      通常情况下，这种变换需要满足KKT条件。通常一个最优化的数学模型能够表示成如下标准形式：

                                                                                                 min f(x)

s.t. h(x)=0, j=1,...,p

                                                                                                 gk(x)≤0, k=1,..,q

                                                                                                 x∈XсRⁿ

      其中，f(x)是需要最小化的函数，h(x)是等式约束，g(x)是不等式约束，p和q分别为等式约束和不等式约束的个数。

      假设XсRⁿ为一个凸集，凸函数，f：X->R为一个凸函数。凸优化就是要找出一个点x*∈X,使得每一点 x∈X满足f(x*)≤f(x).

      KKT条件是一个非线性规划问题，具有最优化解法的充分必要条件。KKT条件就是指上面最优化数学模型的标准形式中的最小点x*必须满足如下条件：

hj(x)=0,j=1,...,p,gk(x)≤0，k=1,...,q

λ_j≠0，μ_k≥0，μ_kg_k(x)=0

       通过观察，这里的问题是满足KKT条件的，因此可以将其转化为求解第二个问题。也就是说，现在原问题通过满足一定条件，已经转化成它的对偶问题。

       而求解这个对偶学习问题，通常可以分为三个步骤：首先要让L（w,b,α）关于w和b最小化，然后求对α的极大，最后利用SMO算法求解对偶因子。

       为求解线性不可分问题，首先需要给出分类超平面的定义。对于数据点x进行分类，实际上式通过把x代入到f(x)=w^Tx+b算出结果，然后根据正负号进行类别划分。

       由前述推导，可以知道：

       因此分类函数可以表述为：f(x)=（∑α_iy_ix_i）^Tx+b=∑α_iy_i<x_i ,x>+b

       通过观察，可以看出对新点x的预测，只需要计算它与训练数据点的内积即可。这一点至关重要，是使用核函数进行非线性推广的基本前提。所有非支撑向量所对应的系数α都等于0，因此对于新点的内积计算，实际上只需要针对少量的支撑向量，而不是所有的训练数据。

       假定数据是线性可分的，即可以找到一个分类超平面将两类数据完全分开。为处理非线性数据，可使用核函数方法对线性SVM进行推广。虽然通过映射φ（·）将原始数据映射到高维空间之后，能够线性分裂的概率大大增加，但是对于某些情况还是很难处理。例如并不是因为数据本身是非线性结构的，而只是因为数据有噪声。对于这种偏离正常位置很远的数据点，称之为野值点。在原来的SVM模型中，野值点的存在有可能造成很大影响，因为超平面本身就是只有少数几个支撑向量组成的。如果这些支撑向量里存在野值点，其影响就很大。

      对于分类平面上的点值为0，边缘上的点值在[0,1/L]之间，其中，L为训练数据集个数，即数据集大小；对于野值点数据和内部的数据值为1/L，则原来的约束条件变为：

y_i(w^Tx_i+b)≥1-ξ_i ，i=1,...,n

      其中，ξ_i≥0称为松弛变量，对应数据点x_i允许偏离的量。如果允许ξ_i任意大的话，那任意的超平面都符合条件了。在原来的目标函数后面加上一项，使得这些ξ_i的加和也要最小，即：

     其中，C是一个参数，控制目标函数中的两项（寻找边界最大的超平面和保证数据点偏差最小）之间的权重。

     ξ_i是需要优化的变量，而C是一个事先确定的常量。因此有：

                                                                                                 s.t.  y_i(w^Tx_i+b)≥1-ξ_i   i=1,...,n

                                                                                                 ξ_i≥0，i=1,...,n

     将约束条件加入到目标函数之中，得到新的拉格朗日函数：

     针对问题的分析方法和前面一样，在转换为另一个问题后，先使L针对w,b和ξ最小化：

     将w代回L并化简，得到和原来一样的目标函数，即：

     由于得到：C-α_i-?_i=0

     又：?_i≥0

     作为拉格朗日乘子的条件，因此有：α_i≤C

     所以整个对偶问题可表示为：

                                                                                          s.t. 0≤α_i≤C, i=1,...,n

                                                                                          ∑α_iy_i=0

      可以看出唯一区别就是现在对偶变量α多了一个上限C。而Kernel化的非线性形式也一样，只要把<xi,xj>换成k(xi,xj)即可，可以获得完整的处理线性和非线性、能够容忍噪声和野值点的支撑向量机。

三、实验

视觉机器学习读书笔记--------SVM方法