SVM 机器学习课件.ppt

线性分类器 从最一般的定义上说，一个求最小值的问题就是一个优化问题（也叫规划），它同样由两部分组成，目标函数和约束条件，可以用下面的式子表示： 　　 　　 约束条件用函数c来表示，就是constrain的意思。一共有p+q个约束条件，其中p个是不等式约束，q个等式约束。 精品 线性分类器 这个式子中的x是自变量，但不限定它的维数必须为1（视乎你解决的问题空间维数）。要求f(x)在哪一点上取得最小值，但不是在整个空间里找，而是在约束条件所划定的可行域里找。注意可行域中的每一个点都要求满足所有p+q个条件，同时可行域边界上的点有一个额外好的特性，它们可以使不等式约束取得等号！而边界内的点不行。 精品 线性分类器 这对一般的优化问题可能提供不了什么帮助，但对 SVM来说，边界上的点有其特殊意义，实际上是它们唯一决定了分类超平面，这些点（就是以前的图中恰好落在H1和H2上的点，在文本分类问题中，每一个点代表一个文档，因而这个点本身也是一个向量）就被称为支持向量。 精品 线性分类器 回头再看线性分类器问题的描述： 　　 在这个问题中，自变量就是w，目标函数是w的二次函数，所有的约束条件都是w的线性函数（不要把xi当成变量，它代表样本，是已知的），这种规划问题也叫做二次规划（Quadratic Programming，QP）。而且，由于它的可行域是一个凸集，因此它是一个凸二次规划。凸二次规划的优点在于它有全局最优解。 精品 线性分类器 我们想求得这样一个线性函数（在n维空间中的线性函数）： g(x)=wx+b 求g(x)的过程就是求w（一个n维向量）和b（一个实数）两个参数的过程（但实际上只需要求w，求得以后找某些样本点代入就可以求得b）。因此在求g(x)的时候，w才是变量。 精品 Support Vector Machine支持向量机 精品 内容 SVM简介 线性分类器 核函数 松弛变量 LIBSVM介绍 实验 精品 SVM简介 支持向量机(Support Vector Machine)是Cortes和Vapnik于1995年首先提出的，它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。 精品 SVM简介 支持向量机方法是建立在统计学习理论的VC 维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度，Accuracy）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷，以期获得最好的推广能力（或称泛化能力）。 精品 SVM简介 VC维：所谓VC维是对函数类的一种度量，可以简单的理解为问题的复杂程度，VC维越高，一个问题就越复杂。正是因为SVM关注的是VC维，后面我们可以看到，SVM解决问题的时候，和样本的维数是无关的（甚至样本是上万维的都可以，这使得SVM很适合用来解决像文本分类这样的问题，当然，有这样的能力也因为引入了核函数）。 精品 SVM简介 结构风险最小原理：就是追求“经验风险”与“置信风险”的和最小 。 精品 SVM简介 风险：机器学习本质上就是一种对问题真实模型的逼近（我们选择一个我们认为比较好的近似模型，这个近似模型就叫做一个假设），但毫无疑问，真实模型一定是不知道的。既然真实模型不知道，那么我们选择的假设与问题真实解之间究竟有多大差距，我们就没法得知。这个与问题真实解之间的误差，就叫做风险（更严格的说，误差的累积叫做风险）。 精品 SVM简介 经验风险Remp(w) ：我们选择了一个假设之后（更直观点说，我们得到了一个分类器以后），真实误差无从得知，但我们可以用某些可以掌握的量来逼近它。最直观的想法就是使用分类器在样本数据上的分类的结果与真实结果（因为样本是已经标注过的数据，是准确的数据）之间的差值来表示。这个差值叫做经验风险Remp(w) 。 精品 SVM简介 以前的一些机器学习方法把经验风险最小化作为努力的目标，但后来发现很多分类函数能够在样本集上轻易达到100%的正确率，在真实分类时却不好（即所谓的推广能力差，或泛化能力差）。此时的情况是因为选择了一个足够复杂的分类函数（它的VC维很高），能够精确的记住每一个样本，但对样本之外的数据一律分类错误。因为经验风险最小化原则适用的大前提是经验风险要确实能够逼近真实风险才行。但实际上不太可能，经验风险最小化原则只在这占很小比例的样本上做到没有误差，不能保证在更大比例的真实文本上也没有误差。 精品 SVM