人工智能 支持向量机

支持向量机1、线性可分情况下的支持向量机1）支持向量机的定义：支持向量机是一个特殊的线性分类器，其分类面满足（1）分类面与两类样本间的距离相等。（2）分类面与两类样本间的距离最大。支持向量（supportvector）的定义：见图0()Tgxwxw()0gx2）线性鉴别函数与分类面的对应关系线性鉴别函数与分类面不是一一对应的。每一个分类面有无穷多个鉴别函数与其相对应。0()Tgxwxw0()0Tgxwxw0()Tagxawxaw0()0Tagxawxaw3）支持向量机设计的目的，本质上是寻求一个距离最大化的等距离分类面。对于任意一个等距离的分类面，必然有无穷多个线性鉴别函数与其对应。在这些鉴别函数中，必然存在一个线性鉴别函数满足|g(x0)|=1,其中为“支持向量”。对于任意一个给定的等距离分类面，仅需考虑这样的鉴别函数。此时分类面距两类样本的间距为000()1Twxwgxz()gx0x()gx该鉴别函数满足如下性质：（1）对“支持向量”：（2）对“非支持向量”：（3）两类样本间的间隔（Margin）:()gx12()1()1gxxgxx如果如果xx12()1()1gxxgxx如果如果1124）支持向量机的数学描述：寻求一个鉴别函数，满足如下条件：（1）取得最大值。（2）该问题等价于求解如下约束条件下的优化问题：minimize:……优化问题1subjectto:2w0()Tgxwxw12()1()1gxxgxx如果如果21()2Jww0()1,1,...,TiiywxwiN5）约束条件下优化问题的求解（1）拉格朗日函数的定义：0011(,,)()12NTTiiiiL1(,...,),0Ni为拉格朗日因子（2）优化问题1的最优解满足如下条件：存在拉格朗日因子，使得满足：**0(,)ww***0(,,)ww***0(,,)0L0011(,,)()12NTTiiiiL***00(,,)0L*0,1,...,iiN***0()10,1,...,TiiiywxwiN**1Niiiiwyx*10Niiiy*（3）优化问题1的对偶问题：maximize:subjectto:该问题等价于：…问题2subjectto:0(,,)Lww1Niiiiwyx10Niiiy0,1,...,iiN1111max2NNNTiijijijiijyyxx10Niiiy0,1,...,iiN（4）最优的求解根据约束条件下的优化问题的求解方法求解问题2，得到。根据下式求解：根据KKT条件求解：支持向量的定义：每一个都对应于一个，如果，则称为支持向量。给定训练样本集，最优的完全由支持向量决定。0(,)1Niiiiwyx0w0()10,0Tiiiiywxwixi0iix0(,)ww2、非线性可分情况下的支持向量机（1）样本集非线性可分条件下的问题描述：在非线性可分条件下，不存在一个满足：但是，存在满足如下条件：对于任意的，存在使得：0(,)ww010211TiiiTiiiwxwxwxwx如果如果010211TiiTiiwxwxwxwx如果如果0(,)wwix0i因此，可以提出一个如下的优化问题：minimize:……问题3subjectto:211()2NiiJwwC0()1,1,...,TiiiywxwiN0,1,...,iiN（2）最优解的性质拉格朗日函数的定义：0(,,)ww010111(,,,,)2()1NTiiNNTiiiiiiiiL0(,,,,)ww存在拉格朗日因子及，使得满足下式KKT条件：最优解满足如下条件：0Lw1Niiiiwyx00Lw10Niiiy0iL0,1,...,iiCiN0()10,0,1,...,TiiiiiiywxwiN0,0,1,...,iiiN0(,,)ww（3）问题3的对偶问题：maximize：subjectto：该问题等价于：…问题4subjectto:0(,,,,)Lww1Niiiiwyx10Niiiy0,1,...,iiCiN0,0,1,...,iiiN1111max2NNNTiijijijiijyyxx10Niiiy0,1,...,iCiN（4）最优的求解根据约束条件下的优化问题的求解方法求解问题4，得到。根据下式求解：根据KKT条件求解：0(,)wwiw1Niiiiwyx0w0()10,0Tiiiiiiywxw0,0iiiCC0()10Tiiywxw