模式识别中支持向量机方法研究.doc

模式识别中支持向量机方法研究摘要：模式识别的目的是将对象进行分类，被分类的对象因应用邻域的不同而不同，一般统称为“模式”，而“模式识别”也被称为“模式分类”。一般的模式识别系统可以分为传感器、分割、特征提取、分类器及后处理等部分，其中实现对“模式”进行分类的部分为分类器，系统中分类器的作用是根据特征提取器得到的特征向量来给对象或者模式赋一个类别标号。本课程论文重点介绍支持向量机（Support Vector Machine，SVM）分类器的原理及应用。关键词：模式识别支持向量机（SVM）0. 引言Vapnik1等人早在20世纪60年代就开始研究有限样本情况下的机器学习问题，由于当时这些研究尚不十分完善，在解决模式识别问题中往往趋于保守，且数学上比较难处理，而直到90年代以前并没有提出能够将其理论付诸实现的较好方法。加上当时正处在其他学习方法飞速发展的时期，因此这些研究一直没有得到充分的重视。直到90年代中，有限样本情况下的机器学习理论研究逐渐成熟起来，形成了一个较完善的理论体系统计学习理论。而同时，神经网络等较新兴的机器学习方法的研究则遇到了一些重要的困难，例如如何确定网络结构问题、过学习和欠学习问题、局部极小点问题等。在这种情况下，试图从更本质上研究机器学习问题的统计学习理论逐步得到重视。1992年1995年，在统计学习理论的基础上发展出了支持向量机学习方法。1. 统计学习理论的核心内容机器学习的目的是根据给定的已知训练样本估计输入输出之间关系，并对新输入的未知输出做出尽可能准确的判断。机器学习问题可以形式化地表示为：已知变量与输入之间存在一定的未知依赖关系，即存在一个未知的联合概率，机器学习就是根据个独立同分布观测样本，在一组函数中求一个最优的函数，使预测的期望风险最小， 的定义如式。 其中，称作预测函数集，为函数的广义参数，故可以表示任何函数集； 为由于用对进行预测而造成的损失。在实际的机器学习问题中，只能利用已知样本的信息，因此期望风险无法直接计算和最小化。根据概率论中大数定律定理的思想，人们自然想到用算术平均代替上式的数学期望，于是定义了：由于是用已知的训练样本（即经验数据）定义的，因此称作经验风险。用对参数求经验风险的最小值代替求期望风险的最小值，就是所谓的经验风险最小化原则。在样本数较多的情况下，可以用经验风险最小化的最优值来估计实际的最优值，但是当样本数较少时，这个估计是不准确的。统计学习理论提供了一种在小样本情况下，使极小化的同时，控制VC维（模型复杂性）的方法，即对于给定的有限样本，选择最佳模型复杂性的方法。首先把函数集分解为一个函数子集序列，使其具有一种嵌套结构，即：其中为函数集的子集（元素），其VC维为有限的，在此结构中嵌套子集按其复杂性，即VC维的大小顺序排列，有：这样，在同一个子集中，置信范围是相同的。在每个子集中寻找最小经验风险，通常它随着子集复杂度的增加而减小。选择最小经验风险与置信范围之和最小的子集，就可以达到期望风险的最小，这个子集中使经验风险最小的函数就是要求的最优函数。这种思想称作结构风险最小化原则。结构风险最小化的示意图如图1所示。图1 结构风险最小化示意图2SVM使用的算法是找出一种特殊的函数集，其结构中每一个子集的经验风险都等于0或一个非常小的数，然后求出使置信区间为最小的一个子集，则该子集的实际期望风险为极小。2. SVM原理考虑线性可分的情况，给定有个样本的训练集合，其中，第个输入数据对应第个输出数据是类标。定义判别函数：这个判别函数是维矢量空间中的一个超平面，也称作分界面，其中是矢量的内积。以图2中的二维情况为例，有许多个判别函数可以将图中的两类样本分割开来，但只有一个超平面可以将两类样本中离超平面最近的样本点距离超平面距离之和最大，这个超平面就是最优超平面，如图2中绿色的粗线条。图2 超平面示意图为了寻找最优超平面，应该从超平面的定义式开始考虑。首先要使超平面能将和的两类样本正确区分，就必须选择适当的，使样本满足下列条件：可以改写为：任意一个样本点到分界面的距离为：若存在一个，对任意样本都有：则称为判别函数的余量，它表示样本点与分界面之间的最小距离。当余量达到最大值时，该分界面就是最优超平面。从上式可以看出，余量越大即表示越小，因此求最优分界面的问题可以表述为下列二次优化问题:对于给定的训练样本及类标，求使下列二次泛函取极小值的。约束条件：对于这样一个二次规划问题，通常转换成与其对应的Lagrange对偶问题来求解，该对偶问题可以用标准的二次规划方法求解。设对偶问题的解为，最优分界面的参数有：由上式可以看出，仅当即约束条件取等号时，才能取非零的数值，所对应输入矢量称为支持向量。如图3所示。因此最优界面参数中的求和只需对支持向量进行：其中为支持向量个数，通常，公式（3.24）表明，最优分界面的权重参数向量可以表示为支持向量的线性组合。最优分界面的另外一个参数可由：图3 支持向量示意图其中，分别属于，类。分界面方程也可以完全由支持向量确定：3. SVM的应用1）分类在大多数监督学习分类过程中，训练数据包括特征及所属类别标号，例如遥感图像分类、文本自动识别、人脸检测等系统中都可以使用SVM来进行分类。训练数据中每个样本，其中为样本数据的特征，为对应的标号，SVM算法根据输入的学习样本找出支持向量集，并由支持向量集得到最大间隔的分类超平面；当用于预测新数据时，SVM根据新样本的特征与分类超平面的相对位置来判断预测数据所属类别。同样，SVM可以扩展为多类的分类器。一般的实现方法是将分类问题层次化，即将多类问题转换为二分类问题。首先将多类分为两大类，然在依次循环在这两个大类中再二分，直至局部问题变为二分类问题。2）相似度测量及相关反馈3检索中，当用户一开始提供的查询信息不够准确致使最后的检索结果不能令用户满意时，这就需要通过调整输入的查询信息来改善最后的检索结果，调整查询信息的过程就是优化查询的过程。相关反馈技术就是代替用户来优化查询，用户只需要查看查询结果并给出它们与用户信息需求是否相关或者相关程度的判断，系统根据用户反馈信息来构造更好的查询表达或者修改检索策略中的参数以更好地把握用户的信息需求。这里的相关度既可以是多个级别(多级的相关尺度)，也可以是简单的“是”与“否”，也就是要么为正例要么为反例。为了用户的方便,同时尽可能丰富地表示反馈信息，本文中采用了“是”、“否”和“无关”三种相关尺度，其中“是”、“否”分别表示正例、反例，“无关”则表示不确定是否相关。分析SVM的学习方法，由于检索的用户提供的相关反馈信息只有“对”、“错”，区分“对”、“错”过程可以看作模式识别中的二分类问题，因此也可以将SVM算法用于相关反馈的学习和检索过程。SVM方法由于不仅考虑了对渐近性能的要求，而且能够根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折中，从而获得最好的推广能力。每次反馈时用户标记样本仅限于检索结果的输出样本中，而这些样本都是在特征空间中距离查询样本较近的样本，也非常适合于构造SVM分类面，因为只有离分类面较近的支持向量对SVM最优分类面的形成有影响，距离分类间隔面很远的样本则没有影响的。因此，虽然用户标记和反馈的样本有限，但却能够提供将相关和不相关样本在特征空间中分开所需的信息。在实际检索系统中，将检索结果中由用户标记出正负例样本作为有类别标号的训练样本交由SVM进行学习，构造出适合表示用户查询意图的最优分类面，然后用该分类面对样本库中的所有样本进行分类，对于分为“正类”的样本，求出每个样本相对于分类面的距离，离分类面越远的样本就与查询样本越相似，按此距离从大到小排序并返回结果。参考文献1 B.Boser,I.Guyon,V.N.Vapnik.A training algorithm for optimal margin classifiers. Fifth Annual Workshop on Computational Learning Theory.Pit