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

《线性可分情形下的支持向量机ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性可分情形下的支持向量机(Supportvectormachine,SVM)OutlineMovitationPrimalproblemandanexampleDualproblemandanexampleOptimizationalgorithms-SMODiscussionMovitation函数间隔与几何间隔SVM：通过找出支持向量，获得这样的超平面——最大化与最近样本之间的几何间隔支持向量问题提出线性可分的分类问题：（令黑色的点=-1，白色的点=+1）所以当有一个新的点x需要预测属

2、于哪个分类的时候，我们用sgn(f(x))，就可以预测了，sgn表示符号函数，当f(x)>0的时候，sgn(f(x))=+1,当f(x)<0的时候sgn(f(x))=–1。+1-1我们怎样才能取得一个最优的划分直线f(x)呢？最大化与最近样本之间的间隔！左边的图：改组样本有很多超平面;中间的图：该超平面随能正确划分现有的点，但是好险啊。再来一个点，预测错误的几率很大!右边的图：通过找出支持向量，获得的最大间隔的超明面函数间隔与几何间隔函数间隔的缺点：以相同的倍数变化w和b，超平面未发生改变，函数

3、间隔却发生了变化！最优超平面：最大化间隔的超平面目标函数：目标函数的变换↓函数间隔与几何间隔之间的关系↓令函数间隔为1，唯一化最优的w,b支持向量刚好满足约束条件的即为支持向量——画圈的样本点。黑色的线为最优超平面！其w,b由支持向量确定！虚线为间隔边界！支持向量至最优超平面的几何距离为1/

4、

5、w

6、

7、！目标函数即使得该几何距离最大化！原始形式的算法流程一个例子Dualproblem原问题对偶问题：将w,b表示为样本的线性组合的形式变化为对偶问题的优势1、对偶问题更容易求解2、自然引入核函

8、数，进而推广至非线性分类问题。核函数如何变化为对偶问题？——Lagrangeduality其中原问题原问题的另一种形式→显然有：Lagrangeduality其中原问题（P）对偶问题（D)显然有对偶间隙：p*-d*When对偶间隙为0?对偶间隙为0时，必定有w*,alpha*,beta*满足：w*为原问题的（最优）解，且alpha*,beta*为对偶问题的（最优）解；且满足Karush-Kuhn-Tucker(KKT)条件。Karush-Kuhn-Tucker(KKT)条件注：Moreover

9、,ifsomew*,alpha*,beta*satisfytheKKTconditions,thenitisalsoasolutiontotheprimalanddualproblems.其中第3式被称为对偶互补条件。利用3式可以获得支持向量。SVM的原问题变为对偶问题（maxmin问题）第一步：建立拉格朗日函数第二步：固定w,b，最小化L。令偏导数为0第三步：将两式带回L(w,b,a)得到对偶问题的表达式对偶问题目标函数是alpha的函数，约束条件也只与alpha有关了！KKT条件在SVM上的

10、应用假设已经求得对偶问题的解，利用KKT条件构造w和b支持向量对应于alpha*>0的向量！一个例子对偶问题的求解算法：SMO坐标法扩展知识线性不可分核函数