机器学习 课件 第4章　采样与非参数贝叶斯方法

支持向量机基于统计学习理论的方法

定义最优超平面，并把寻找最优超平面归结为求解一个凸规划问题支持向量机（supportvectormachine，SVM）基本原理支持向量机能较好地解决小样本、非线性和高维数据、局部极小点等实际问题。H为线性超平面，H1、H2分别为过各类中离超平面最近的样本且平行于超平面

分类间隔（margin）：

|

H1H2

|。最优超平面

：将两类数据正确分开，并且使分类间隔最大。二分类支持向量机（supportvectormachine，SVM）基本原理

能将两类样本正确分开的超平面有无数多个。如何求得

最优超平面

？支持向量机（supportvectormachine，SVM）超平面

线性超平面非线性超平面线性可分情况线性不可分情况线性不可分情况线性最优超平面

线性支持向量机非线性最优超平面非线性支持向量机

支持向量机数据线性可分数据线性不可分核方法基于Mercer

核展开定理，通过用内积函数定义的非线性变换将输入空间映射到高维特征空间（Hilbert空间），在这个高维特征空间中寻找输入变量和输出变量之间的关系。

升维线性化线性可分情况设线性可分的训练样本线性支持向量机

分类超平面：

两类样本：

超平面H1到原点的距离：

超平面H2到原点的距离：分类间隔｜

H1H2｜=

约束的二次规划问题：

构造拉格朗日函数求解H1、H2上的训练样本点称作支持向量（supportvector，SV）线性支持向量机构造Lagrange函数：线性支持向量机满足约束：其中，D是阶对称矩阵，。为原问题中，与每个约束条件式对应的Lagrange乘子

最优分类函数：利用Lagrange优化方法，将其转化为对偶问题，即最大化线性不可分情况引入非负松弛变量约束方程：线性支持向量机

约束的二次规划问题：

构造拉格朗日函数求解

利用Lagrange优化方法，将转化为对偶问题，即最大化线性支持向量机满足约束：其中。KKT（Karush-KuhnTucker）条件：C为大于零的平衡常数TheEnd非线性支持向量机主讲人：李侃基于Mercer

核展开定理，通过用内积函数定义的非线性变换，将输入空间映射到高维特征空间（Hilbert空间），在这个高维空间中寻找输入变量和输出变量之间的关系。非线性支持向量机非线性支持向量机非线性超平面核方法

核函数

已知映射函数，通过内积求得核函数K，不用构造映射函数能否直接判断一个给定的函数是否是核函数K？或者说K满足什么条件才是核函数？核函数正定核的充要条件：设是对称函数，则K（x,z）为正定核函数的充要条件是对任意对应的Gram矩阵是半正定矩阵。Mercer定理可以得到Mercer核，正定核比Mercer更具一般性常用的核函数（1）多项式形式的核函数此时得到的支持向量机是一个d阶多项式分类器。核函数常用的核函数（2）径向基函数形式的核函数此时得到的支持向量机是一种径向基函数分类器。它与传统径向基核函数（RBF）方法的基本区别：每一个核函数的中心对应于一个支持向量，它们以及输出权值是由算法自动确定。核函数常用的核函数（3）Sigmoid函数形式的核函数得到的支持向量机实现的两层的多层感知器神经网络网络的权值、网络的隐层节点数目由算法自动确定。核函数常用的核函数（4）点积形式的核函数此时得到的支持向量机是线性的分类器。核函数常用的核函数判断一个支持向量机分类器性能的关键指标有两个：

学习能力

推广能力核函数常用的核函数学习能力：分类器从训练数据中建立正确的分类模型的能力推广能力：指这个模型对未知数据进行正确预测的能力。推广能力的强弱更能反映分类器性能的好坏，因为设计分类器的目的就是对未知数据进行分类。核函数非线性支持向量机

非线性映射把数据从输入空间映射到高维特征空间在高维特征空间中进行线性分类，映回到原空间后就成了输入空间中的非线性分类为避免高维空间的复杂计算，支持向量机采用核函数代替高维空间非线性支持向量机约束的二次规划问题：

构造拉格朗日函数求解：

优化问题的对偶形式：非线性支持向量机

该优化问题解的特点是大部分将为零，其中不为零的解对应的样本为支持向量

。TheEnd一分类/多分类支持向量机主讲人：李侃优化问题：一分类支持向量机(one-classsupportvectormachine，1-SVM)通过超球体来实现一类分类异常值检测实际上可视为一类分类问题设一个正类样本集为:找到一个以a为中心，以R为半径的包含样本点的最小超球

对偶形式：一分类支持向量机根据KKT条件，对应于样本满足：其中：给定新数据z:若，则z为正常点，否则z为异常点直接法：直接修改目标函数，将多个分类面的参数求解合并到一个最优化问题中，通过求解该最优化问题“一次性”实现多类分类。特点：简单，但计算复杂度较高，实现较困难，只适合小型问题。间接法：主要是通过组合多个二分类器来实现多分类器的构造，如：一对多（one-against-all）和一对一（one-against-one）方法。多分类支持向量机一对多法：训练时依次把某个类别的样本归为一类，其它样本归为另一类，这样k个类别的样本构造了k个SVM。分类时将未知样本分类为具有最大分类函数值的那类。多分类支持向量机优点训练k个分类器，个数较少，其分类速度相对较快缺点训练速度会随着训练样本的数量的增加而急剧减慢；样本不对称：负类样本的数据要远远大于正类样本的数据；

新的类别加入，需要对所有的模型重新训练从“一对多”的方法衍生出基于决策树的分类。解决不对称：引入不同的惩罚因子，对样本点较少的正类采用较大的惩罚因子C。一对一法：在任意两类样本之间设计一个SVM，因此k个类别的样本需要设计k(k-1)/2个SVM。当对一个未知样本进行分类时，得票最多的类别即为该未知样本的类别。多分类支持向量机当类别很多的时候，模型的个数是k(k-1)/2，代价相当大。从“一对一”的方式出发，有向无环图（directedacyclicgraph，DAG）分类方法多分类支持向量机在高维特征空间中对每一类样本求出一个超球体中心，计算待测试样本到每类中心的距离，根据最小距离来判断该点所属的类基于一分类思想的多分类支持向量机方法受到基于一类分类思想的启发训练样本为