08支持向量机

支持向量机(SUPPORTVECTORMACHINES)超平面的选择•线性可分的情况下分类面有无穷多个•那么不同的分类器选择方法不同yi:1或-1支持向量机0WXb1WXb0WXbSupportVectorOptimalSeparatingHyperplane线性可分情况下，不仅要区分开，而且要使得间隔(Margin)最大。1WXb0WXbMarginH1:H2:小间隔vs.大间隔间隔大，将来的点分队的可能性就大（可证：将来犯错误的概率的上界更小）•如上图的训练样本,在线性可分的情况下,存在多个超平面(Hyperplane)(如:H1,H2….)使得这两类被无误差的完全分开。超平面可以定义为：其中W、Ｘ都是向量，W•Ｘ是内积，b是标量。0WXb超平面定义•如果X是二维的，则超平面是直线，各样本点到直线的距离为（根据解析几何）：•亦可表达为：超平面定义将分类平面平移到某位置，使得分类面离两个类中最近的点的距离相等，则间隔就等于两倍的上述δ；再令分子为1（本来是某个常数，为方便将其置换为1，对我们的求解无影响）则我们的优化目标就是：•最优超平面是指两类的分类间隔(Margin)最大，即每类中“距离超平面最近的样本”到超平面的距离之和最大。距离这个最优超平面最近的样本被称为支持向量(SupportVector)。•优化问题：最优超平面2WMargin=11WXbH1平面：H2平面：2•1WXb[()]10iiyWXb目标函数：约束条件：等于1可视为约定俗成等于1或-1•求解最优超平面就相当于，在下列约束条件下，求目标函数的最小值目标函数:2121)(2[()]10iiyWXb约束条件:最优超平面•对范数平方是为了更方便求解。•针对上述的极值问题，我们可以采用拉格朗日乘子法求极值，这个式子的拉格朗日目标函数：求解原始问题•为求解原始问题，根据最优化理论，我们转化为对偶问题来求解11111minXX2..0,0,1lllijijijjijjliiiiyystyil对偶问题为原始问题中与每个约束条件对应的Lagrange乘子。这是一个不等式约束条件下的二次函数寻优问题，存在唯一解i*目标函数是凸函数，约束条件是线性不等式，则必有唯一解！线性可分问题求解结果需要分类的新点的向量也就是计算相似度非线性可分情况下的处理方法一最优超平面求解非线性可分情况下的处理方法二将不可分的样本映射到高维空间，实现线性可分映射函数找不到？变换到高维空间的支持向量机•采用如下的内积函数(核函数)：qiiXXXXK]1)[(),(22exp),(XiXXiXK))(tanh(),(cXXXXKii核函数就是在高维空间下的内积函数*1*),(sgn)(bXXKyXfiinii分类函数支持向量机小结•SVM训练相对较慢，分类速度一般。但是分类效果较好。•在面对非线性可分情况时，可以引入松弛变量进行处理或者通过空间变换到另一个线性可分空间进行处理。•SVM有很多实现工具，SMO/SVMlight/SVMtorch/LibSVM等等。一个SVM的例子—几何法求解•最大间隔权重向量将和两类中距离最短的那条线段(直线)平行，即与连接点(1,1)和(2,3)的直线平行，这可以得到权重向量(1,2).•最优的分类直线与上述线段垂直并相交与其中点(中垂线)，因此它经过点(1.5,2).•于是，可以求得SVM的决策直线方程为：y=x1+2x2−5.5一个SVM的例子—代数法求解一般过程：使用工具包•SVMlight，libSVM等•构造样本集合•使用工具直接计算出分类器•将待测试样本输入分类器得到结果END(所有课件已发邮箱)[e-mail]密码：本校拼音全部课程结束!课程考核:论文(格式见邮件)第19周(或之前)交