1.什么是支持向量机（SVM）

　　所谓支持向量机，顾名思义，分为两部分了解：一，什么是支持向量（简单来说，就是支持或支撑平面上把两类类别划分开来的超平面的向量点）；二，这里的“机（machine，机器）”便是一个算法。在机器学习领域，常把一些算法看做是一个机器，如分类机，而支持向量机本身便是一种监督式学习的方法，它广泛的应用于统计分类以及回归分析中。

　　支持向量机是90年代中期发展起来的基于统计学习理论的一种机器学习方法，通过寻求结构化风险最小来提高学习机泛华能力，实现经验风险和置信范围的最小化，从而达到在统计样本量较少的情况下，亦能获得良好统计规律的目的。

2.线性分类

　　2.1：分类标准

　　　　这里我们考虑的是两类分类问题，数据点用x来表示，这是一个n维向量，wT上标中的“T”代表转置，而类别用y来表示，可以取1或者-1，分别代表两个不同的类。一个线性分类器就是要在n维的数据空间中找到一个超平面，其方程可以表示为： f(x)=w‘ * x +b=0 ;　　//想追究 y为何要表示为1或者-1，可以查询 logistic 函数

　　　　PS：当然，有些时候，或者说大部分时候数据并不是线性可分的，这个时候满足这样条件的超平面就根本不存在

　　　　PS：更进一步，我们在进行分类的时候，将数据点x带入f(x)中，如果得到的结果小于0，则赋予其类别-1，如果大于0则赋予类别1.如果f(x)=0，则很难办了，分到哪一类都不是。

　　2.2：函数间隔与几何间隔

　　　　一般而言，一个点距离超平面的远近可以表示为分裂预测的确信或准确程度。　　　　

　　　　Ÿ=y(w‘ *x +b)=y*f(x) ;

　　接着，我们定义超平面(w,b)关于训练数据集T的函数间隔为超平面(w,b)关于T中所有样本点(xi,yi)的函数间隔最小值，其中x是特征，y是结果标签，i表示第i个样本，有Ÿ=min Ÿi , i=1,2,...,n

然而于此同时，问题就出来了。上述定义的函数间隔虽然可以表示分类预测的正确性和确信度，但在选择分类超平面时，只有函数间隔还远远不够，因为如果成比例的改变w和b，如将他们改变为2w和2b，虽然此时超平面没有改变，但是函数间隔的值y*f(x)却变成了原来的4倍。其实我们可以对法向量w加些约束条件，使其表面上看起来规范化。

　　2.2：点到超平面的距离定义：几何间隔

　　　　对于一个点x,令其垂直投影到超平面上对应的为x0，由于w是垂直超平面的一个向量，y为样本x到分类间隔的距离，我们有x=x0 + y*(w/|w|) 

　　　　又由于x0是超平面上的点，满足f(x0)=0，带入超平面的方程即可算出  y=(w‘ * x +b)/|w|=f(x)/|w| ；不过这里的y是带符号的，我们需要的只是他的绝对值，因此类似地，也乘上对应的类别y即可，因此实际上我们定义几何间隔为  Ÿ=yY=Ÿ/|w|=|Y|/|w|  ;  //注意：类别y的取值为1或-1

　　　　此公式与曾经学的点到平面的公式一致。

　　2.3：最大间隔分类器

　　　　于此，我们已经很明显的看出，函数间隔和几何间隔相差一个|w|的缩放因子按照我们的分析，对一个数据点进行分类，当它的分隔越大的时候，分类正确的把握越大。对于一个包含n个点的数据集，我们可以很自然地定义它的间隔为所有这n个点的间隔中最小的那个。于是，为了使得分类的把握尽量大，我们希望所选择的超平面能够最大化这个间隔值。

　　　　这样一来，我们的目标就可以定义为： max Ÿ 

　　　　当然，还需要满足一些条件，根据间隔的定义，我们有 yi (w‘ * xi +b)=Ÿi >=Ÿ ,i=1,2,...,n

　　　　其中Ÿ=Ÿ *|w| ，处于方便推荐和优化的目的，我们可以令Ÿ=1，此时目标转化为 max 1/|w|  s.t.  yi * (w‘ * xi +b) >=1 ,i=1,2,...,n

通过求解这个问题，我们就可以找到一个间隔最大的分类器，最大间隔能获得最大稳定性与区分的确信度，从而得到良好的推广能力。

3.从线性可分到线性不可分

　　3.1：从原问题到对偶问题

　　　　虽然前面给出了优化目标，却没给出推导，下面来处理这个问题：max 1/|w|  s.t.  yi (w‘ xi +b)>=1  ,i=1,2,...,n

由于求1/|w| 的最大值相当于求1/2*|w|^2 的最小值，所以上述问题等价于它的对偶问题：min 1/2*|w|^2  s.t.  yi (w‘ * xi +b)>=1 ,i=1,2,...,n

到这个形式以后，就可以很明显地看出来，它是一个凸优化问题(PS:什么是凸优化问题，我看了几篇论文讲这个的，不过具体证明过程还是没怎么看明白，http://www.cqvip.com/read/read.aspx?id=28555264)，或者更具体地说，它是一个二次优化问题——目标函数是二次的，约束条件是线性的。虽然这个问题确实是一个标准的QP问题，但是它也有它的特殊结构，通过Lagrange对偶变换到对偶变量Dual Variable的优化问题之后，可以找到一种更加有效的方法来进行求解，而且通常情况下这种方法比直接使用通用的QP优化包进行优化要高效的多。

　　　　也就是说，除了用解决QP问题的常规方法之外，还可以应用Lagrange对偶性，通过求解对偶问题得到最优解，这就是线性可分条件下支持向量机的对偶算法，这样做的优点在于：一者对偶问题往往更容易求解；二者可以自然的引入核函数，进而推广到非线性分类问题。

　　　　至于上述提到，关于什么是Lagrange对偶性？如果读者学过高等数学，这个过程就是Lagrange乘数法，求条件极值的过程。简单来说，通过给每一个约束条件加上一个Lagrange乘子，即引入Largange对偶变量α,如此我们便可以通过Lagrange函数将约束条件融合到目标函数里去：L(w,b,α)=1/2*|w|^2 - Σ αi (yi ( w‘*xi +b)-1)  ;

　　　　　　　　　　　　　　　　　　　　　　然后我们令      Θ(w)=max L(w,b,α)  ;  ai>0

容易验证，当某个约束条件不满足时，例如yi(w‘ * xi +b)<1 ,那么我们显然有Θ(w)=+∞ 。而当所有约束条件都满足时，则有Θ(w)=1/2*|w|^2 ，亦即我们最初要最小化的量。因此，在要求约束条件得到满足的情况下最小化1/2*|w|^2 ，实际上等价于直接最小化 Θ(w)。具体写出了，我们现在的目标函数变成了： min Θ(w) =min max L(w,b,α)=p* 

这里用p*表示这个问题的最优值，这个问题和我们最初的问题是等价的。不过现在我们来把最小和最大的位置交换一下。

　　　　　　　　　　max  min L(w,b,α)=d* 

当然，交换以后的问题不再等价于原问题，这个新问题的最优值用d*来表示。并且，我们有d*<=p*，这在直观上也不难理解，最大值中最小的一个总也比最小值中最大的一个要大吧！总之，第二个问题的最优值d*在这里提供了一个第一个问题的最优值p*的一个下届，在满足某些条件的情况下，这两者等价，这个时候我们就可以通过第二个问题间接的求解第一个问题。

　　　　上面说到“在满足某些条件的情况下”，这所谓的“满足某些条件”就是要先满足Slater条件，进而就满足KKT条件。

那KKT条件的表现形式是什么呢？ 如果读者学过运筹学的话，就会知道一般的，一个最优化数学模型能够表示成下列标准形式：

　　　　　　　　　　min f(x)

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

　　　　　　　　　　　　　gk(x)<=0 ,k=1,2,...,q

　　　　　　　　　　　　　x€X 

所谓Karush-Kuhn-Tucker最优化条件，就是指上式的最小点x* 必须满足下面的条件：

　　　　1.hj(x*)=0, gk(x*)<=0 , j=1,2,...,p , k=1,2,...,q

　　　　2.∂f(x*)+Σ λj * ∂hj(x*)+Σ uk * ∂gk(x*)=0,  λj≠0 ,uk>=0 , uk*gk(x*)=0

　　3.2:序列最小最优化算法SMO

　　　　关于α的求解过程既是我们常说的SMO算法，这里简要介绍下：

　　　　　　　　max  W(α) = Σ αi  -1/2 * Σ yi*yj*αi*αj *<xi,xj>

　　　　　　　　s.t.  0<=αi<=C, i=1,2,...,n

　　　　　　　　　　 Σ αi * yi=0　,　i=1,2,...,n

　　　　要解决的是在参数α上求W的最大值的问题，至于xi 和 yi 都是已知数。其中C是一个参数，用于控制目标函数中两项 （“寻找间隔最大的超平面”和“保证数据点偏差量最小”）之间的权重

　　3.3：线性不可分的情况

　　　　首先是关于超平面，对于一个数据点x进行分类，实际上式通过把x带入到f(x)=w‘ * x +b算出结果然后根据其正负号来进行类别划分的。而前面的推导中我们得到w=Σ αi*yi*<xi,x>+b，因此分类函数为

　　　　　　　　　　f(x)={Σ αi*yi*xi}‘*x+b=Σ αi*yi*<xi,x> +b

这里的形式的有趣之处在于，对于新点x的预测，只需要计算它与训练数据点的内积即可（<.,.>表示向量内积），这一点至关重要，是之后使用核函数进行非线性推广的前提。此外，所谓“支持向量”也在这里显示出来——事实上，所有非支持向量所对应的系数α都是等于0的，因此对于新点的内积计算实际上只要针对少量的“支持向量”而不是所有的训练数据即可。

4.核函数

　　4.1：特征空间的隐式映射：核函数

　　　　在上面，我们已经了解到了支持向量机处理线性可分的情况，而对于非线性的情况，支持向量机的处理方法是选择一个核函数k(.,.) ,通过将数据映射到高维空间，来解决在原始空间中线性不可分的问题。由于核函数的优良品质，这样的非线性扩展在计算量上并没有比原来复杂多少，这一点是非常难得的。当然，这样归功于核方法——除了支持向量机之外，任何计算表示为数据点的内积的方法，都可以使用核方法进行非线性扩展。

　　　　在线性不可分的情况下，支持向量机通过某种事先选择的非线性映射（核函数）将输入变量映射到一个高维特征空间，在这个空间中构造最优分类超平面。我们使用支持向量机进行数据分类工作的过程首先是同预先选定的一些非线性映射将输入空间映射到高维特征空间。

　　　　在高维特征空间中对训练数据通过超平面进行分类，避免了直接在原输入空间中寻找非线性函数来进行分类。支持向量机的分类函数具有这样的性质：它是一组以支持向量为参数的非线性函数的线性组合，因此分类函数的表达式仅和支持向量的数量有关，而独立于空间的维度，在处理高维输入空间的分类时，这种方法尤其有效。

具体点说：在我们遇到核函数之前，如果用原始的方法，那么在用线性学习器学习一个非线性关系，需要选择一个非线性特征集，并且将数据写成新的表达形式，这等价于应用一个固定的非线性映射，将数据映射到特征空间，在特征空间中使用线性学习器，因此，考虑的假设集是这种类型的函数：f(x)=Σ wi*Φi(x)+b 

　　　　其中Φ：X-->F是从输入空间到某个特征空间的映射，这意味着建立非线性学习器分为两步：

　　　　　　　　1.首先使用一个非线性映射将数据变换到一个特征空间F；

　　　　　　　　2.然后在特征空间使用线性学习器分类。

　　在上文提到过对偶形式，而这个对偶形式就是线性学习器的一个重要性质，这意味着假设可以表达为训练点的线性组合，因此决策规则可以用测试点和训练点的内积来表示：f(x)=Σ ai*yi*<Φ(xi),Φ(x)>+b

如果有一种方式可以在特征空间中直接计算内积<Φ(xi),Φ(x)>,就像在原始输入点的函数中一样，就有可能将两个步骤融合到一起建立一个非线性的学习器，这样直接计算的方法称为核函数方法。

　　这里我们给出一个定义：核是一个函数k,对所有x,z€X,满足k(x,z)=<Φ(xi),Φ(x)>,这里Φ(.)是从原始输入空间X到内积特征空间F的映射。

　　4.2：利用核函数处理非线性数据

　　　　先从简单例子出发，设两个向量x1=(a1,a2)和x2=(b1,b2),而Φ(.)既是五维空间的映射，因此映射过后的内积为：

　　　　　　　　<Φ(x1),Φ(x2)>=a1*b1+a1^2*b1^2+a2*b2+a2^2*b2^2+a1*b1*a2*b2

　　这里我们又注意到 (<Φ(xi),Φ(x)>+1)^2=2*a1*b1+a1^2*b1^2+2*a2*b2+a2^2*b2^2+2*a1*b1*a2*b2+1

　　二者有很多相似的地方，实际上，我们只要把某几个维度线性缩放一下，然后再加上一个常数维度，具体来说，上面这个式之的计算结果实际上和映射

　　　　　　　　Ψ(x1,x2)=(sqrt(2)*x1,x^2,sqrt(2)*x2,x2^2,sqrt(2)*x1,x2,1) ;

　　之后的内积<Φ(x1),Φ(x2)>的结果是相同的，那么区别在什么地方呢？

　　　　　　1.一个是映射到高维空间中，然后再根据内积的公式进行计算；

　　　　　　2.而另一个则是直接在原来的低维空间中进行计算，而不需要显式地写出映射后的结果

　　我们把这里的计算两个向量在隐式映射过后的空间中的内积的函数叫做核函数 Kernel Function ，例如在刚才的例子中，我们的核函数为：k(x1,x2)=(<x1,x2>+1)^2

　　核函数能简化映射空间中的内积运算——刚好“碰巧”的是，在我们的支持向量机里需要计算的地方数据向量总是以内积的形式出现的。则现在我们的分类函数为：

　　　　　　　　f(x)=Σ ai*yi*k(xi,x)+b

　　其中a 由如下的对偶问题求解而得：

　　　　　　　　max Σ ai -1/2*ai*aj*yi*yj*k(xi,xj)

　　　　　　　　s.t.   ai>=0,i=1,2,...,n

　　　　　　　　　　　Σ ai*yi=0　　;   i=1,2,...,n

　　这样一来计算的问题就算解决了，避开了直接在高维空间中进行计算，而结果却是等价的！

　　4.3：几个核函数

　　　　通常人们会从一些常用的核函数中选择：根据问题和数据的不同，选择不同的参数，实际上就是得到了不同的核函数。

　　　　多项式核：k(x1,x2)=(<x1,x2>+R)^d  ;   该空间的维度是[m+d;d],其中m是原始空间的维度。

　　　　高斯核：   k(x1,x2)=exp{-1*|x1-x2|^2/(2*σ^2)}  

　　　　　　　　　　这个核会将原始空间映射为无穷维空间，不过，如果σ选得很大的话，高次特征上的权重实际上衰减的非常快，所以实际上相当于一个低维的子空间，如果σ选得很小，则可以将任意的数据映射为线性可分。

　　　　线性核：    k(x1,x2)=<x1,x2>

　　4.4：使用松弛变量处理离群点的方法

　　　　就是引入松弛变量，使得优化目标变为：

　　　　　　　　min  1/2*|w|^2+C*Σ ζi　　;i=1,2,...,n

　　　　　　　　s.t.  yi*(w‘*xi-b)>=1-ζi  

5.SMO算法

　　咱们首先来定义特征到结果的输出函数为

　　　　　　u=w‘ * x-b

　　这个u与我们之前定义的f(x)=w‘ * x+b 实质是一样的。接着，咱们重新定义咱们原始的优化问题：

　　　　　　min  1/2*|w|^2

　　　　　　s.t.  yi*(w‘ * xi -b)>=1, i=1,2,...,n

类似地，采用Lagrange乘数法可以得到

　　　　　　w=Σ yi*ai*xi

　　　　　　b=w‘ * xk - yk  (对某个ak>0)

 这里的ai还是Lagrange乘数法中引入的系数。引入核函数k(.,.)可以得到

　　　　　　u=Σ ai*yi*k(xi,x) -b　　;i=1,2,...,n

于此同时，和前面类似可以写出

　　　　　　min 1/2*ΣΣ ai*aj*yi*yj*<xi,xj> - Σ ai　　;

　　　　　　s.t.  ai>=0,i=1,2,...,n

　　　　　　Σ ai*yi =0 　　　　i=1,2,...,n

引入松弛变量之后为

　　　　　　min 1/2*|w|^2 +C*Σ ζi

　　　　　　s.t.  yi*(w‘*xi - b)>=1-ζi  ,  i=1,2,...,n

最终的优化目标为

　　　　　　min  1/2*ΣΣ ai*aj*yi*yj*k(xi,xj)  -  Σ ai

　　　　　　s.t.   0<=ai<=C,  i=1,2,...,n

　　　　　　　　　Σ ai*yi=0

根据KKT条件可以得出其中ai取值的意义为：

　　　　　　ai=0         <=> yi*ui>=1　　　　//表明是正常分类，在边界内部，我们知道正确分类的点yi*f(xi)>=0

　　　　　　0<ai<C     <=> yi*ui=1　　　　 //表明了是支持向量，在边界上

　　　　　　ai=C         <=> yi*ui<=1　　    //表明了是在两条边界之间

而最优解需要满足KKT条件，即上述3个条件都得满足，以下几种情况出现将会出现不满足：

　　　　　　yi*ui<=1 但是 ai<C ,则是不满足的，而原本ai=C

　　　　　　yi*ui>=1 但是 ai>0 ,则是不满足的，而原本ai=0

　　　　　　yi*ui =1  但是ai=0 或者 ai=C ,则表明不满足的，而原本应该是0<ai<C

所以要找出不满足KKT条件的这些ai ,并更新这些ai ,但这些ai 又收到另外一个约束：

　　　　　　Σ ai*yi =0　　; i=1,2,...,n

因此，我们通过另一个方法，即同时更新ai 和aj ，要求能满足下式，就能保证和为0的约束。

　　　　　　ai_new*yi+aj_new=ai_old*yi+aj_old*yj=常数

消去ai，可得到一个关于单变量aj的一个凸二次规划问题，不考虑其约束0<=aj<=C，可以得其解为

　　　　　　 aj_new =aj_old+yj*(Ei-Ej)/t

　　　其中：Ei=ui-yi

　　　　　　Ej=uj-yj

　　　　　　t=k(xi,xi)+k(xj,xj)-2*k(xi,xj)

然后考虑约束0<=aj<=C可以得到ai的解析解为

　　　　　　　　　　　　　　  H         ,  ai_new>=H

　　　　　　ai_new_clipped=  ai_new , L<ai_new<H

　　　　　　　　　　　　　　  L          , ai_new <=L

根据yi 和 yj 同号 或异号，可得出两个上、下界分别为

　　　　　　L=max{0,aj-ai}　　yi  != yj

　　　　　　H=max{C,C+aj-ai}

　　　　　　L=max{0,aj+ai-C}   yi=yj

　　　　　　H=max{C,aj-ai}　　 

对于ai,有  ai_new =ai+yi*yj*(aj-aj_new_clipped)

那么如何求得ai 和 aj 呢？对于ai ，可以通过刚刚说的那3中不满足KKT的条件来找；而对于aj，可以通过max|Ei-Ej|求得；而b的更新则是

　　　　　　b1,　　　 0<ai<C

　　　　b=  b2,         0<aj<C

　　　　　　1/2*(b1+b2),   其他

其中，　　b1=b-Ei-yi*(ai-ai_old)*k(xi,xi) - yj*(aj-aj_old)*k(xi,xj)

　　　　   b2=b-Ej-yi*(ai-ai_old)*k(xi,xi) - yj*(aj-aj_old)*k(xj,xj)

每次更新完ai和aj后，都需要再重新计算b，及对应的Ei 和 Ej

最后更新所有ai , y 和 b ，这样模型就出来了，从而即可求出开头提出的分类函数。

支持向量机通俗导论 ——理解SVM的三层境界 总结