08-3第八章机器学习-SVM简介

支持向量机简介•我们怎样才能取得一个最优的划分直线f(x)呢？最大距离MaximumMarginal•选择使得间隙最大的函数作为分割平面是由很多道理的，比如说从概率的角度上来说，就是使得置信度最小的点置信度最大（听起来很拗口），从实践的角度来说，这样的效果非常好，等等。最大距离f(x)=wx+b=0wx+b=1wx+b=-1(x,y)MwwyxfM),(1),(wM22max目标函数：wmin等价于：221minw因为单调，并且为了计算方便w：线性不可分的情况核函数如果建立一个二次判别函数：g(x)=(x-a)(x-b)则可以很好的解决上述分类问题。线性不可分的情况•我们可以为分错的点加上一点惩罚，对一个分错的点的惩罚函数就是这个点到其正确位置的距离：主要内容•支持向量机基础理论•基于核函数的机器学习初探支持向量机基础理论主要内容•基本概念•线性可分情况下的支持向量机•线性不可分情况下的支持向量机•近似线性可分情况下的支持向量机•用于多分类的支持向量机基本概念•二分类–及格？不及格？–长？短？–有？没有？–相似？不相似？……根据某一（类）指标（特征）将某一事物或某些事物分到两类中的一类中去阈值（threshold）参照基本概念•二分类–样例：ti表示x的各个指标的权重–给出评价函数f(x)和阈值bf(x)≥b?或f(x)b?f(x)+b≥0?或f(x)+b0?(阈值转化为了-b)y=sgn(f(x)+b)y表示类别标记{1,1}y1234[,,,......]'ntttttx基本概念•二分类–两类问题的分类通常用一个实值函数按照这样的方式操作：当时给输入x赋给正类，否则赋给负类，f称为决策函数。:nfXRR()0fx基本概念•线性分类–前述内容未对函数的形式做任何限制–可以实任意类型的函数：指数、对数、多项式、规则的集合()fx()fx112233()......nnfwtwtwtwtx1()niiifwtxwx123,,,......'nw基本概念•线性分类1sgn()sgn(())niiiywtbfx1()niiifbwtbxwx决策函数线性函数线性分类是的分类方法称为方法或线性分类器基本概念•线性分类-------++++++++++---+bw分类超平面基本概念•线性可分–直观的解释：在特征空间中是否存在一超平面能够将样例正确的分类。–形式化解释：是否存在线性函数能够对样例做出正确的决策。()fx基本概念•线性函数的获得–如果线性可分，我们如何获得该线性函数？1()niiifbwtbxwx人工机器学习线性可分情况下的支持向量机•线性可分–存在线性函数能够对样例做出正确的决策。()fx-------+++++++++---+线性可分情况下的支持向量机•样例对应超平面的函数间隔–定义：样例（xi,yi）对应于超平面的（函数的）间隔是量：()iiybiwx1,1y0i当样本被正确分类时ibiwx线性可分情况下的支持向量机•样本对应超平面的函数间隔–定义：样本中与对应于超平面的（函数的）间隔的最小值。若对w，b进行归一化bdwxww几何间隔线性可分情况下的支持向量机-------+++++++++---+dd线性可分情况下的支持向量机•几何间隔与分类性能的关系–根据结构风险最小的原理22Rd误分类次数R是样本中向量长度最长的值max(x)1,2,3...iRin几何间隔越大误分类次数的上界越小，分类效果越好线性可分情况下的支持向量机•支持向量机算法的目标–寻找与样本几何间隔最大的分类超平面bdwxww几何间隔与分类超平面的法向量的长度成反比通常固定函数间隔为1，即11dwmax()mindw线性可分情况下的支持向量机•支持向量机算法优化目标1dwmax()mindw22111minminmin22niiwww21min2w支持向量机优化目标：线性可分情况下的支持向量机•支持向量机优化问题的约束21min2w0w求导1dw？！？！？！通常固定样本的函数间隔为1，即样本中与对应于超平面的（函数的）间隔的最小值。线性可分情况下的支持向量机•支持向量机优化问题的约束()1iiybiwx121min2w..()101,2,3......istybimiwx线性可分情况下的支持向量机•二次规划问题21min2w.()101,2,3......istybimiwx该二次规划问题是否有解？该解是否能够找到？线性可分情况下的支持向量机•二次规划问题–凸函数定义：对于,如果并且对于任意的有：实值函数称为凸函数，如果不等式关系严格成立，则该函数称为严格凸函数。如果一个二次可导函数的Hessian矩阵（二次项系数矩阵）是半正定的，则该函数是凸的。nRwnRw,u(0,1)((1))()(1)()fffwuwu()fw线性可分情况下的支持向量机•二次规划问题2wuwuf(w)f(u)()()2fwfu()2wuff(x)1111((1))()(1)()2222fwufwfu线性可分情况下的支持向量机•二次规划问题–凸最优化问题：如果一个最优化问题的集合、目标函数和所有的约束都是凸的，则称其为是凸的。21min2w.()101,2,3......istybimiwx局部最优解既是全局最优解线性可分情况下的支持向量机•二次规划问题–计算机求解的方法—迭代法()fxxy1x2x线性可分情况下的支持向量机•最优解满足的条件nR给定一个在域上的最优化问题：min()..()01,2,3,...()=01,2,3,...iifstgikhim定义广义拉格朗日函数为：1(,,)()()()kmiiiiiiLfgh线性可分情况下的支持向量机•最优解满足的条件–Kuhn-Tucher定理：给定一个凸域上的最优化问题：min()..()01,2,3,...()=01,2,3,...iifstgikhim是凸的，一般地，一个点w*是最优点的充要条件是存在*,*满足：线性可分情况下的支持向量机•最优解满足的条件min()..()01,2,3,...()=01,2,3,...iifstgwikhimww(,*,*)0Lww(,*,*)0Lw*(*)0i=1,2,3,....kiigw(*)0i=1,2,3,....kigw0i=1,2,3,....ki线性可分情况下的支持向量机•最优解满足的条件21min2w..()101,2,3......istybimiwx21(,,)()12miiiLwbybiwwx线性可分情况下的支持向量机•最优解满足的条件21(,,)()12miiiLwbybiwwx(,*,*)0Lww(,*,*)0Lw*(*)0i=1,2,3,....kiigw(*)0i=1,2,3,....kigw0i=1,2,3,....kii=1,2,3,..()10..miiybiwx()10i=1,2,3,....miybiwx0i=1,2,3,....mi(,,)0Lwbw(,,)0Lwbb线性可分情况下的支持向量机•对偶问题原问题的拉格朗日对偶问题定义如下：(,)..max0st这里目标函数在最优解的值称为问题的值(,)inf(,,)Lww线性可分情况下的支持向量机•问题求解–使用拉格朗日定理解最优化问题可以使用一个对偶表示替代描述，该对偶问题通常比原问题更容易处理，因为直接处理不等式约束是困难的。对偶问题通过引入又称为对偶变量的拉格朗日乘子来解。对偶方法来源于将对偶变量作为问题的基本未知量的思想。可以通过把拉格朗日函数对于各个原变量的导数致零，并将得到的关系式带入原拉格朗日函数，将原问题转化为对偶问题并去除了原变量的相关性。线性可分情况下的支持向量机•问题求解21min2w.()101,2,3......istybimiwx21(,,)()12miiiLwbybiwwx线性可分情况下的支持向量机•问题求解21(,,)()12miiiLwbybiwwx(,,)Lwbw0miiiiywx(,,)Lwbb0miiiymiiiiywx22222123......nw22222123,,,....'ndd线性可分情况下的支持向量机•问题求解()mmiiiiiiiiyywxx()10i=1,2,3,....miiybiwx分类超平面的法向量是所有样本向量的线性组合！权重主要由决定！ii时()10iybiwxi才有可能不为零！只有边界向量决定分类超平面法向量，此类向量支撑出了分类超平面，支持向量机因此而得名！线性可分情况下的支持向量机•问题求解21(,,)()12miiiLwbybiwwxmiiiiywx0miiiy线性可分情况下的支持向量机•问题求解21(,,)()12miiiLwbybiwwx1111(,,)()12mmmiiiiiiiijiimjiiiiyyyLwbybxxxxmiiiiywx0miiiy,111(,,)()12immijijijijijjmiiiiyLybbywyxxxx,111(,,)()2immiimmmijiiiijijijijjiiiiLwbybyyyyxxxx线性可分情况下的支持向量机•问题求解,111(,,)()2immiimmijijijijijmiijiiiiiyyyxyLwbybxxx,1,11(,,)2mmmijijijijijijiijijiLwbyyxyyxxx,11()2mmiijiijiijjLyyxx线性可分情况下的支持向量机..00miiiisty,11max2mmiijijijiijyyxx•线性可分情况下的SVM优化模型线性可分情况下的支持向量机•线性可分情况下的SVM的决策函数miiiiywx()fbxwx()iiiisvfybxxxxb=yi-wxi线性可分情况下的支持向量机•小结–最大化几何间隔–凸二次规划问题–拉格朗日对偶问题线性不可分情况下的支持向量机•线性不可分情况–不存在线性函数能够对样例做出正确的决策。–如果线性不可分支持向量机求解算法将不能收敛()fx•例abx2012()fxccxcx线性不可分情况下的支持向量机线性不可分情况下的支持向量机•例2012()fxccxcx12231yyyxyx102132acaacac()fxya需要一个函数将当前特征空间中的向量转换到新的特征空间中去线性不可分情况下的支持向量机•SVM的模型和决策函数x设变换函数为：..00miiiisty,11max2()()mmiijijiijijyyxx()()()iiixsvifybxxx线性不可分