SVM

KKT推导

以下是详细步骤：
SVM的目标问题：

应用拉格朗日乘子法得
$l(omega ,b,xi,alpha ,r )=frac{1}{2} omega^{T}omega+Csum_{i=1}^{m}{xi_i} -sum_{i=1}^{m}{alpha_i[y^{(i)}(omega^T x^{(i)}+b)-1+xi_i ]} - sum_{i=1}^{m}{r_ixi_i}$
那么对待优化变量求偏微分
$frac{partial l}{partialomega} =0 Rightarrow w=sum_{i=1}^{m}{alpha_i y^{(i)} x^{(i)} }$ (1)
$frac{partial l}{partial b} =0 Rightarrow sum_{i=1}^{m}{alpha_i y^{(i)} } = 0$ (2)
$frac{partial l}{partialxi_{i}} =0 Rightarrow alpha_{i}=C-r_{i}$ (3)
根据KKT互补条件，
$alpha_i[y^{(i)}(omega^T x^{(i)}+b)-1+xi_i ]=0$ (4)
$r_{i}xi_{i}=0$ (5)
所以，将(3) (4) (5)带入以下式子
当 $alpha_{i}=0 Rightarrow r_{i}=C, xi_{i}=0 Rightarrow y^{(i)}(omega^T x^{(i)}+b) geq 1$ ，几何间距>=1样本的 $xi_{i}=0$
当 $0<alpha_{i}<C Rightarrow r_{i}>0 , xi_{i}=0 Rightarrow y^{(i)}(omega^T x^{(i)}+b)=1-xi_{i} = 1$ ，几何间距为1的样本，也就是支持向量的 $xi_{i}=0$
当 $alpha_{i}=C Rightarrow r_{i}=0, xi_{i}geq 0 Rightarrow y^{(i)}(omega^T x^{(i)}+b)=1-xi_{i}leq 1$ ，只有样本与决策边界的几何间距（geometric margin）小于1时， $xi_{i}>0$ 才成立。而且他们之间的等式关系为 $xi_{i}=1-y^{(i)}(omega^T x^{(i)}+b)$ 。

那么满足KKT条件的，我们说如果一个点满足KKT条件，那么它就不需要调整，一旦不满足，就需要调整。由上可知，不满足KKT条件的也有三种情况：

(1) y i u i \leq 1

------------------------

SVN原理比较复杂，但是思想很简单，一句话概括，就是通过某种核函数，将数据在高维空间里寻找一个最优超平面，能够将两类数据分开。     1.理解什么是对偶问题     ———————————————————— SVM的目的是要找到一个线性分类的最佳超平面 f(x)=xw T +b=0 f(x)=xwT+b=0 。求 w w 和 b b。 首先通过两个分类的最近点，找到f(x) f(x)的约束条件。 有了约束条件，就可以通过拉格朗日乘子法和KKT条件来求解，这时，问题变成了求拉格朗日乘子α i αi 和 b b。 对于异常点的情况，加入松弛变量ξ ξ来处理。 使用SMO来求拉格朗日乘子α i αi和b b。这时，我们会发现有些α i =0 αi=0 ，这些点就可以不用在分类器中考虑了。 惊喜! 不用求w w了，可以使用拉格朗日乘子α i αi和b b作为分类器的参数。 非线性分类的问题：映射到高维度、使用核函数。 ————————————————————     Q: y是否可以是其它非{-1， 1}的值? A: 将y值定义为{-1， 1}是最简化的方案。你的分类可以是cat和dog，只要将cat对应到1, dog对应到-1就可以了。你也可以将y值定义为其它数比如: -2, 2或者2, 3之类的，但是这样就需要修改超平面函数和约束条件，增加了没必要的繁琐，实际上和y值定义为{-1， 1}是等价的。 Q: 如果两组数据里的太近或者太远，是不是可能就找不到xw T +b=1 xwT+b=1  和xw T +b=−1 xwT+b=−1 的这两个点？ A: 不会。假设可以找到x i w T +b=c xiwT+b=c 和 x j w T +b=−c xjwT+b=−c. c>0andc<>1 c>0 andc<>1 。其超平面函数为xw T +b=0 xwT+b=0 . 上面公式左右同时除以c, 则： x i w T /c+b/c=1 xiwT/c+b/c=1 x j w T /c+b/c=−1 xjwT/c+b/c=−1 令: w ′ =w/c w′=w/c b ′ =b/c b′=b/c 有: x i w ′T +b ′ =1 xiw′T+b′=1 x j w ′T +b ′ =−1 xjw′T+b′=−1 可以找到超平面函数: xw T +b ′ =0 xwT+b′=0 因此，总是可以找到y是{-1, 1}的超平面，如果有的话。   ——————————————————————— 输入参数： 参数C C，越大表明影响越严重。C C应该一个大于0值。其实C C也不能太小，太小了就约束α i αi了，比如200。 参数ξ ξ，对所有样本数据起效的松弛变量，比如：0.0001。 具体证明请看： ———————————————————————— 对一个数据点进行分类，当超平面离数据点的“间隔”越大，分类的确信度（confidence）也越大。所以，为了使得分类的确信度尽量高，需要让所选择的超平面能够最大化这个“间隔”值。 ——————————————————— 转换到这种形式以后是不是很像上节说到的KKT条件下的优化问题了，就是这个。但是有一个问题，我们说上节的KKT是在凸函数下使用的，那么这里的目标函数是不是呢？答案是的，想想 W T ∗W ，函数乘出来应该很单一，不能有很多极点，当然也也可以数学证明是的。 ——————————————————— 行文至此，我相信，SVM理解到了一定程度后，是的确能在脑海里从头至尾推导出相关公式的，最初分类函数，最大化分类间隔，max1/||w||，min1/2||w||^2，凸二次规划，拉格朗日函数，转化为对偶问题，SMO算法，都为寻找一个最优解，一个最优分类平面。一步步梳理下来，为什么这样那样，太多东西可以追 ———————————————————  其中     是一个参数，用于控制目标函数中两项（“寻找 margin 最大的超平面”和“保证数据点偏差量最小”）之间的权重。 ——————————————————— 问题： 松弛变量中 ri$求和是怎么来的 ———————————————————  原始问题通过满足KKT条件，已经转化成了对偶问题。而求解这个对偶学习问题，分为3个步骤：首先要让L(w，b，a) 关于 w 和 b 最小化，然后求对的极大，最后利用SMO算法求解对偶问题中的拉格朗日乘子。