零 前言：Logistic回归与SVM的来源
logistic回归的预测函数如下
对于一组输入数据，只需比较将其输入进hθ中的函数值，若大于0.5，就是y=1的类，否则就是y=0的类。其实其实质上也是比较
与0的大小，若其大于0，则判为y=1，反之判为y=0。当
或
判别正确的概率较大。对于如下图：
其中两个坐标轴为两个特征，直线为
，X与⚪代表样本点。对于A，B我们基本可以确定其就属于X类，但对于C却不是十分确定。我们现在改进算法，即关心这些靠近中心线的点，让它们尽量远离中心线（超平面），用那些较远点靠近超平面来换取较近点远离超平面。这是一种局部最优的算法，而不是全局最优。这就是SVM的基本思想。
一 正式定义
SVM的预测函数如下：
若令z=
，那么g的值为
这就是SVM在二分问题的预测函数，接下来我们的任务是。给出优化目标，据此求出最优化的参数w与b
二 函数间隔（Functional Margin）与几何间隔（Geometric Margin）
首先讨论函数间隔。对于训练样本
，定义函数间隔如下
可知，当y(i)=1时，
，反之同理，所以γ(i)的值就是
。因此，函数间隔γ(i)表示了我们认为特征是正例还是反例的确信度。
继续考虑w和b。若同比例改变w和b，比如在
前乘一个系数2，那么函数间隔都会增加到2倍，但是对最后求出的超平面没有影响，因为超平面的方程形式是
，故同比例改变w和b是没有影响的。
现在定义全局函数间隔如下
此就是SVM的思想体现，即前面所提到的，考虑那些靠近超平面的点。
然后讨论几何间隔，对于下图（图例中的两个轴仍为两个特征）
为样本点A到超平面的距离。如何求得距离呢？可知BA向量的单位方向矢量为k=
，因为A点为训练样本，所以A的坐标为
，又直线BA过A，且斜率为k，那么可得B点的特征轴坐标x=
，又B在超平面上满足
，带入得
整理得γ(i)为
修改上式，我们给出几何间隔的表达式如下
可知当||w||=1时，几何间隔的值与函数间隔相同。
全局几何间隔为
三 优化问题的提出
根据SVM的思想，需要让最靠近超平面的点远离，即优化目标为最大化全局几何间隔，如下
其中利用了
。
可以得知若不给出
的确切数值，w与b的确切数值也无法求出，只是得到w和b的比值。虽然w和b的比值即可确定超平面，但对于优化问题，需要求出w和b的具体数值才能带入优化软件等的求解。所以这里不妨设
=1。
此时，优化目标变为max
，注意到其等价于min
，那么给出如下优化问题
这就是典型的二次规划问题（Quadratic Programming QP），带入优化软件可解，下面一节给出
四 拉格朗日对偶（Lagrange duality）
对于优化问题的Lagrange对偶函数，即
注：L为Lagrange函数；inf即下界，也可写作min
当此对偶问题的最优对偶间隙为0时，那么强对偶性成立，对原问题的max和此问题的max结果是相同的。强对偶性成立的条件（除了凸性条件以外，即必须要求约束与原问题都是凸的）称之为约束准则。其中一个简单的约束准则是Slater条件，即对于其不等式约束，若在定义域存在一点x，使得
则称原问题Slater条件可行，那么原问题可转化为等价的Lagrange对偶问题L:
max g(λ,v)也可以写作 max min L(x,λ,v)，求解原问题等价于求解此对偶问题。
详见Convex Optimization (by Boyd&Vandenberghe)第5章
这里先给出Andrew Ng课程中关于Lagrange对偶的表达式
原优化问题为
Lagrange函数为
KKT条件为
满足KKT条件的点即是原问题与对偶问题的最优解。
其中(5)式称为KKT对偶互补性（ KKT dual complementarity ）条件。也就是说，对于gi(w)<0则αi=0，gi(w)=0则αi>0，且这两个结论的逆命题也成立。
五 最优间隔分类器（optimal margin classifier）
现将“三”中提出的优化问题，即
中的不等式约束，改写成标准的Lagrange对偶问题中的原问题的约束形式，即
可知，对于函数间隔为1的点（离超平面最近的点），其αi>0，而其它点的gi(w)<0，αi=0。
如下图
其中在虚线上的点都是其函数间隔为1的点，它们称为支持向量。
易知原问题满足Slater条件，构造Lagrange函数如下
我们知道，求解原目标，等价于求解max min L(w,b,α)，首先求解min L(w,b,α)。对于固定αi的L(w,b,α)，其最小值只与w和b有关，分别对它们求偏导数，对w有
即有
(*)
对b有
(**)
将(*)带入L(w,b,α)中，经化简得到（化简步骤省略）
由(**)，上式化为
所以，max min L(w,b,α)变为等价问题
此优化问题中，消去了w与b，只与αi有关。对此类优化问题的求解，将由后面节的SMO算法给出。
求出最优化的αi后，可由式(*)求出w。考虑到超平面两侧的最近点的函数间隔均为1，那么据此可求出b为
最后，重新将w用式(*)表示，那么SVM判别函数的表达式又写为
注意到，只有对于支持向量才会αi>0，其它点αi=0，故并没有非常大的计算量，即输入数据x不需与每个样本点做内积。