上节整整讨论了两遍（周、李老师），就是为了引出SVM是怎么来的？要解决的问题是什么？如何数学化表达？得到下面的数学问题：
这就是SVM的基本型。该问题也称为原始问题。
对该问题应用拉格朗日乘子法，通过将原始问题转化为求解对偶问题（dual problem）来得到最优解。即可得到线性可分SVM的对偶问题。
为何要引入对偶问题？其优点在于：
对偶问题更易求解：只需要求解乘子 α 。对偶问题的形式中：可自然引入核函数，从而推广到非线性问题。引入拉格朗日乘子 αi≥0,i=1,2,...,N 。即每个样本向量均对应一个乘子。然后定义拉格朗日函数：
L(w,b,α)=12||w||2−∑i=1Nαiyi(w⋅xi+b)+∑i=1Nαiα=(α1,α2,...,αN)T
由拉格朗日对偶性，原始问题的对偶问题是极大极小问题：
maxαminw,bL(w,b,α)
（1）求解 minw,bL(w,b,α)
将 L 分别对w,b求导，令其为0，则有
▽wL=w−∑i=1Nαiyixi=0▽bL=∑i=1Nαiyi=0
则有：
w=∑i=1Nαiyixi∑i=1Nαiyi=0
将其代入 L(w,b,α) 中，可得：
minw,bL(w,b,α)=−12∑i=1N∑j=1Nαiαjyiyj(xi⋅xj)+∑i=1Nαi
（2）求解 minw,bL(w,b,α) 对 α 的极大，即为对偶问题：
maxα(−12∑i=1N∑j=1Nαiαjyiyj(xi⋅xj)+∑i=1Nαi)s.t.∑i=1Nαiyi=0αi≥0,i=1,2,...,N
我们一般喜欢求最小化问题。将其再转化为等价的对偶最优化问题：
minα(12∑i=1N∑j=1Nαiαjyiyj(xi⋅xj)−∑i=1Nαi)s.t.∑i=1Nαiyi=0αi≥0,i=1,2,...,N
这便是线性可分SVM的对偶问题。
对于对偶问题：
minα(12∑i=1N∑j=1Nαiαjyiyj(xi⋅xj)−∑i=1Nαi)s.t.∑i=1Nαiyi=0αi≥0,i=1,2,...,N
存在 w∗,α∗,β∗ ，使得 w∗ 是原始问题的解，使得 α∗,β∗ 是对偶问题的解。这意味着：求解原始问题，现在转化为求解对偶问题。
对于线性可分数据集，假设对偶最优化问题对 α 的解是 α∗=(α∗1,α∗2,...,α∗N)T 。存在下标 j ，使得α∗j>0，并可按照下式计算出 w∗,b∗ ：
w∗=∑i=1Nα∗iyixib∗=yj−∑i=1Nα∗iyixi⋅xj
则分类超平面为（w,b）。此式表明：
分类超平面仅依赖于输入x和训练样本输入的内积。求解w时，仅那些大于0的乘子起作用，即对应着支撑向量。求解b时，任选一个支撑向量样本均可，因所有支撑向量到超平面距离相同。支撑向量一定在边界上。由KKT互补条件可知 α∗(yi(w∗xi+b∗)−1)=0 ，既然乘子大于0，则 yi(w∗xi+b∗)=1 。与前面支撑向量的定义一致。算法：线性可分SVM的对偶学习算法
（1）构造并求解约束最优化的对偶函数，求解拉格朗日乘子。（2）从大于0的乘子，计算原始问题的解（w,b）。（3）求解分离超平面（w,b）=0和决策函数sign(w,b)。为上一节的例题：
已知 x1=(3,3),x2=(4,3),x3=(1,1),y1=y2=+1,y3=−1 ，求最大间隔分离超平面。（因x为2维，则w为2维）
解：
（1）写出对偶问题
minα(12∑i=1N∑j=1Nαiαjyiyj(xi⋅xj)−∑i=1Nαi)=12(18α21+42α1α2−12α1α3−14α2α3+25α22+2α23)−(α1+α2+α3)s.t.∑i=1Nαiyi=0则α1+α2−α3=0αi≥0,i=1,2,3
求解该最优化问题。将 α1+α2=α3 代入目标函数并记为：
minS(α1,α2)=4α21+132α22+10α2α3−2α1−2α2
对 α1,α2 求偏导，令其为0，则有 α1=32,α2=−1 ，不符合乘子大于0的要求。考虑S为凸函数，在某个范围内，要么有极值；没有极值时，则关注边界值。
当 α1=0,α2=213 时， S=−213 当 α2=0,α1=14 时， S=−14
则 α1=14,α2=0,α3=14 。
则其对应的 x1, x3 为支撑向量。
（2）求解原始问题的解。
w=∑i=1Nα∗iyixi=14⋅1⋅(3,3)T+14⋅−1⋅(1,1)T=(12,12)T
采用两个支撑向量，计算得到的 b 均为2。
（3）分离超平面和分离决策函数
分离超平面为 12x(1)+12x(2)−2=0 分类决策函数为 f(x)=sign[12x(1)+12x(2)−2]
over。
对线性可分数据集，该方法非常完美。有理论支撑，有实际可操作的凸优化解法。
但是现实中，线性可分数据集很难找到，有噪声和特异点的存在，使得不能线性可分。于是需要把这个方法推广到一般上来。即下一节《线性SVM》。
