支持向量机教材ppt课件.ppt

支持向量机北京10月机器学习班邹博2014年11月9日1为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能谱聚类历史遗留问题o最小化fLf，为什么等价于最小特征值和特征向量？o其不满足f1的条件，为什么？o特征向量v里的元素是连续的任意实数，能否具体点？o求拉普拉斯矩阵的前K个特征值，再对前K个特征值对应的特征向量进行K-means聚类，对特征向量进行K聚类的目的是什么？o最小的系列特征向量对应着图最优的系列划分方法，怎么理解向量划分图？o什么是NP问题？2为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能解答o其不满足f1的条件，为什么？3为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能切割代价与fLf的关系4为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能解答5为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能解答o特征向量v里的元素是连续的任意实数，能否具体点？o求拉普拉斯矩阵的前K个特征值，再对前K个特征值对应的特征向量进行K-means聚类，对特征向量进行K聚类的目的是什么？oL是实对称正定阵，那么，L的特征向量u，是实向量。即：u的每个元素都是实数。n这其实不是我们想要的。如果计算L的次小特征向量v，得到的v中的元素都只能取-1，+1，那么，直接就可以用-1，+1将原始样本聚类成两簇了。（可惜现实中不是这样子）n所以，必须将特征向量v根据是否大于0（或其他定值）分成两部分，进而把原始样本聚类成两簇。n实践中，往往不是只选择次小的特征向量，而是选择前K个特征向量进行K均值聚类。6为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能解答o最小的系列特征向量对应着图最优的系列划分方法，怎么理解向量划分图？n一般翻译成“连通分量”。o什么是NP问题？n有些问题，目前人们从未找到过多项式级的时间复杂度，我们把这种问题，叫做NP问题。7为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能复习：对偶问题o一般优化问题的Lagrange乘子法oLagrange函数n对固定的x，Lagrange函数L(x,v)为关于和v的仿射函数8为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能复习：Lagrange对偶函数(dualfunction)oLagrange对偶函数o若没有下确界，定义：o根据定义，显然有：对0，v，若原优化问题有最优值p*，则o进一步：Lagrange对偶函数为凹函数。9为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能另一种表述o原始问题o引入拉格朗日乘子：o原始问题：o有如下结论：10为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能主要内容和目标o理解支持向量机SVM的原理和目标o掌握支持向量机的计算过程和算法步骤o对线性不可分的数据，理解软间隔最大化的含义o了解核函数的思想o了解SMO算法的过程11为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能线性分类问题12为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能输入数据o假设给定一个特征空间上的训练数据集T=(x1,y1),(x2,y2)(xN,yN)，其中，xiRn，yi+1,-1，i=1,2,N。xi为第i个特征向量，也称为实例，yi为xi的类标记；当yi=+1时，称xi为正例；当yi=-1时，称xi为负例。(xi,yi)称为样本点。13为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能各种概念o线性可分支持向量机n硬间隔最大化hardmarginmaximizationn硬间隔支持向量机o线性支持向量机n软间隔最大化softmarginmaximizationn软间隔支持向量机o非线性支持向量机n核函数kernelfunction14为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能线性可分支持向量机o给定线性可分训练数据集，通过间隔最大化或等价的求解相应的凸二次规划问题学习得到的分离超平面为wx+b=0，相应的分类决策函数f(x)=sign(wx+b)该决策函数称为线性可分支持向量机。15为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能二维平面上线性分类问题16为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能线性可分支持向量机17为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能函数间隔和几何间隔o给定的训练数据集T和超平面(w,b)，定义超平面(w,b)关于样本点(xi,yi)的函数间隔为：o平面法向单位化的函数间隔，即几何间隔18为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能最大间隔分离超平面19为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能最大间隔分离超平面20为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能最大间隔分离超平面21为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能最大间隔分离超平面22为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能拉格朗日乘子法o原问题是极小极大问题o原始问题的对偶问题，是极大极小问题23为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能拉格朗日乘子法o将拉格朗日函数L(w,b,)分别对w，b求偏导并令其为0：24为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能拉格朗日乘子法o将上式带入拉格朗日函数L(w,b,)中，得到：25为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能继续求minw,bL(w,b,)对的极大26为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能整理目标函数：添加负号27为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能线性可分支持向量机学习算法o构造并求解约束最优化问题o求得最优解*28为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能线性可分支持向量机学习算法o计算o求得分离超平面o分类决策函数29为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能举例o给定3个数据点：正例点x1=(3,3)T，x2=(4,3)T，负例点x3=(1,1)T，求线性可分支持向量机。30为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能目标31为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能将约束带入目标函数，化简计算o将o带入目标函数，得到关于12的函数：o对12求偏导并令其为0，易知s(1,2)在点(1.5,-1)处取极值。而改点不满足条件20，所以，最小值在边界上达到。o当1=0时，最小值s(0,2/13)=-2/13o当2=0时，最小值s(1/4,0)=-1/4o于是，s(1,2)在1=1/4，2=0时达到最小，此时，3=1+2=1/432为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能分离超平面o1=3=1/4对应的点x1,x3是支持向量。o带入公式：o得到w1=w2=0.5，b=-2o因此，分离超平面为o分离决策函数为33为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能线性支持向量机o若数据线性不可分，则增加松弛因子i0，使函数间隔加上松弛变量大于等于1。这样，约束条件变成o目标函数：34为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能线性SVM的目标函数35为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能拉格朗日函数o拉格朗日函数o对w,b,求偏导36为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能带入目标函数o将三式带入L中，得到o对上式求关于的极大，得到：37为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能最终的目标函数o整理，得到对偶问题：38为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能线性支持向量机学习算法o构造并求解约束最优化问题o求得最优解*39为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能线性支持向量机学习算法o计算n注意：计算b*时，需要满足0jCo求得分离超平面o分类决策函数40为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能核函数o可以使用核函数，将输入空间映射到特征空间，从而，使得原本线性不可分的样本可以在特征空间可分。o在实际应用中，往往依赖先验领域知识才能选择有效的核函数o多项式核函数o高斯核函数o字符串核函数n如：两个字符串的最长公共子序列LCS(X,Y)41为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能核函数影射42为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能SMOo序列最小最优化nSequentialMinimalOptimizationo有多个拉格朗日乘子o每次只选择其中两个乘子做优化，其他因子认为是常数。n关于这两个变量的解应该更接近原始二次规划问题的解。43为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能SMOo考察目标函数，假设1和2是变量，其他是定值：44为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能二变量优化问题45为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能SMO的迭代公式o迭代公式：46为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能SMO算法o1.取初值(0)=0，令k=0o2.选择优化变量1(k)，2(k)，解析求解两个变量的优化问题，求得最优解1(k+1)，2(k+1)，更新为(k+1)o3.若在精度范围内满足退出条件(下一页)，则转4；否则，k+，转2o4.取=(k+1)47为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能退出条件48为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能参考文献o统计学习方法，李航著，清华大学出版社，2012年ohttp:/ 感谢大家！恳请大家批评指正！50