线性可分情形下的支持向量机.

线性可分情形下的支持向量机(Supportvectormachine,SVM)Outline•Movitation•Primalproblemandanexample•Dualproblemandanexample•Optimizationalgorithms-SMO•DiscussionMovitation•函数间隔与几何间隔•SVM：通过找出支持向量，获得这样的超平面——最大化与最近样本之间的几何间隔–支持向量问题提出•线性可分的分类问题：（令黑色的点=-1，白色的点=+1）•所以当有一个新的点x需要预测属于哪个分类的时候，我们用sgn(f(x))，就可以预测了，sgn表示符号函数，当f(x)0的时候，sgn(f(x))=+1,当f(x)0的时候sgn(f(x))=–1。bxwxfr)(+1-1•我们怎样才能取得一个最优的划分直线f(x)呢？最大化与最近样本之间的间隔！•左边的图：改组样本有很多超平面;•中间的图：该超平面随能正确划分现有的点，但是好险啊。再来一个点，预测错误的几率很大!•右边的图：通过找出支持向量，获得的最大间隔的超明面函数间隔与几何间隔•函数间隔的缺点：以相同的倍数变化w和b，超平面未发生改变，函数间隔却发生了变化！11x1-x2=0x1x2(1,0)：x1-x2=1(0.5,0.5)间隔距离最优超平面：最大化间隔的超平面•目标函数：目标函数的变换↓函数间隔与几何间隔之间的关系↓令函数间隔为1，唯一化最优的w,b支持向量刚好满足约束条件的即为支持向量——画圈的样本点。黑色的线为最优超平面！其w,b由支持向量确定！虚线为间隔边界！支持向量至最优超平面的几何距离为1/||w||！目标函数即使得该几何距离最大化！原始形式的算法流程一个例子Dualproblem•原问题•对偶问题：将w,b表示为样本的线性组合的形式变化为对偶问题的优势•1、对偶问题更容易求解•2、自然引入核函数，进而推广至非线性分类问题。核函数如何变化为对偶问题？——Lagrangeduality•其中•原问题•原问题的另一种形式→•显然有：Lagrangeduality•其中•原问题（P）•对偶问题（D)•显然有•对偶间隙：p*-d*•When对偶间隙为0?•对偶间隙为0时，必定有w*,alpha*,beta*满足：w*为原问题的（最优）解，且alpha*,beta*为对偶问题的（最优）解；且满足Karush-Kuhn-Tucker(KKT)条件。Karush-Kuhn-Tucker(KKT)条件•注：Moreover,ifsomew*,alpha*,beta*satisfytheKKTconditions,thenitisalsoasolutiontotheprimalanddualproblems.•其中第3式被称为对偶互补条件。利用3式可以获得支持向量。SVM的原问题变为对偶问题（maxmin问题）•第一步：建立拉格朗日函数•第二步：固定w,b，最小化L。令偏导数为0•第三步：将两式带回L(w,b,a)得到对偶问题的表达式iiiiiijijjjiiiabyaxwyaxyaxyaabwL,21),,()1)((21),,(2bxwyawabwLiii对偶问题•目标函数是alpha的函数，约束条件也只与alpha有关了！KKT条件在SVM上的应用•假设已经求得对偶问题的解，利用KKT条件构造w和b•支持向量对应于alpha*0的向量！一个例子对偶问题的求解算法：SMO•坐标法扩展知识•线性不可分•核函数