适用于初学者的模式识别核方法与支持向量机简介.ppt

,模式识别核方法,夏 森 1310514,（1）核函数方法简介,核函数发展历史 早在1964年Aizermann等在势函数方法的研究中就将该技术引入到机器学习领域，但是直到1992年Vapnik等利用该技术成功地将线性SVMs推广到非线性SVMs时其潜力才得以充分挖掘。而核函数的理论则更为古老，Mercer定理可以追溯到1909年，再生核希尔伯特空间(ReproducingKernel Hilbert Space, RKHS)研究是在20世纪40年代开始的。,（2）核函数方法原理,根据模式识别理论，低维空间线性不可分的模式通过非线性映射到高维特征空间则可能实现线性可分，但是如果直接采用这种技术在高维空间进行分类或回归，则存在确定非线性映射函数的形式和参数、特征空间维数等问题，而最大的障碍则是在高维特征空间运算时存在的“维数灾难”。采用核函数技术可以有效地解决这样问题。,设x,zX,X属于R（n）空间,非线性函数实现输入间X到特征空间F的映射,其中F属于R（m）,n 其中：为内积,K(x,z)为核函数。从式可以看出，核函数将m维高维空间的内积运算转化为n维低维输入空间的核函数计算，从而巧妙地解决了在高维特征空间中计算的“维数灾难”等问题，从而为在高维特征空间解决复杂的分类或回归问题奠定了理论基础。,（3）核函数特点,核函数方法的广泛应用,与其特点是分不开的： 1）核函数的引入避免了“维数灾难”,大大减小了计算量。而输入空间的维数n对核函数矩阵无影响，因此，核函数方法可以有效处理高维输入。 2）无需知道非线性变换函数的形式和参数. 3）核函数的形式和参数的变化会隐式地改变从输入空间到特征空间的映射，进而对特征空间的性质产生影响，最终改变各种核函数方法的性能。 4）核函数方法可以和不同的算法相结合，形成多种不同的基于核函数技术的方法，且这两部分的设计可以单独进行，并可以为不同的应用选择不同的核函数和算法。,（4）常见核函数,核函数的确定并不困难,满足Mercer定理的函数都可以作为核函数。常用的核函数可分为两类，即内积核函数和平移不变核函数，,（5）核函数方法实施步骤,核函数方法是一种模块化(Modularity)方法，它可分为核函数设计和算法设计两个部分，具体为： 1）收集和整理样本,并进行标准化； 2）选择或构造核函数； 3）用核函数将样本变换成为核函数矩阵,这一步相当于将输入数据通过非线性函数映射到高维特征空间； 4）在特征空间对核函数矩阵实施各种线性算法； 5）得到输入空间中的非线性模型。 显然,将样本数据核化成核函数矩阵是核函数方法中的关键 。注意到核函数矩阵是ll的对称矩阵，其中l为样本数。,（6）核函数在模式识别中的应用,1）新方法。主要用在基于结构风险最小化(Structural Risk Minimization,SRM)的SVM中。 2）传统方法改造。如核主元分析(kernel PCA)、核主元回归(kernel PCR)、核部分最小二乘法(kernel PLS)、核Fisher判别分析(Kernel Fisher Discriminator, KFD)、核独立主元分析(Kernel Independent Component Analysis,KICA)等，这些方法在模式识别等不同领域的应用中都表现了很好的性能。,VC维,VC维：对于一个指示函数（即只有0和1两种取值的函数）集，如果存在h个样本能够被函数集里的函数按照所有可能的2h种形式分开，则称函数集能够把h个样本打散，函数集的VC维就是能够打散的最大样本数目。 如果对任意的样本数，总有函数能打散它们，则函数集的VC维就是无穷大。,一般而言,VC维越大, 学习能力就越强,但学习机器也越复杂。 目前还没有通用的关于计算任意函数集的VC维的理论,只有对一些特殊函数集的VC维可以准确知道。 N维实数空间中线性分类器和线性实函数的VC维是n+1。,学习机器的实际风险由两部分组成: 训练样本的经验风险 置信范围(同置信水平有关,而且同学习机器的VC维和训练样本数有关。 在训练样本有限的情况下,学习机器的VC维越高,则置信范围就越大,导致实际风险与经验风险之间可能的差就越大。 在设计分类器时, 不但要使经验风险最小化,还要使VC维尽量小,从而缩小置信范围,使期望风险最小。,结构风险最小化,传统机器学习方法中普遍采用的经验风险最小化原则在样本数目有限时是不合理的,因此，需要同时最小化经验风险和置信范围。 统计学习理论提出了一种新的策略,即把函数集构造为一个函数子集序列,使各个子集按照VC维的大小排列;在每个子集中寻找最小经验风险,在子集间折衷考虑经验风险和置信范围,取得实际风险的最小。这种思想称作结构风险最小化(Structural Risk Minimization)，即SRM准则。,实现SRM原则的两种思路,在每个子集中求最小经验风险,然后选择使最小经验风险和置信范围之和最小的子集。 设计函数集的某种结构使每个子集中都能取得最小的经验风险,然后只需选择适当的子集使置信范围最小,则这个子集中使经验风险最小的函数就是最优函数。支持向量机方法实际上就是这种思路的实现。,多核学习方法,人们对核方法的关注,得益于支持向量机(Support vector machine,SVM)理论的发展和应用,核函数的采用使得线性的SVM很容易推广到非线性的SVM.其核心在于利用相对简单得多的核函数运算,既避免了特征空间中复杂的内积计算,又避免了特征空间(学习机器)本身的设计。 多核学习方法是当前核机器学习领域的一个新的热点.核方法是解决非线性模式分析问题的一种有效方法,但在一些复杂情形下,由单个核函数构成的核机器并不能满足诸如 ： 数据异构或不规则、样本规模巨大、样本不平坦分布等实际的应用需求,因此将多个核函数进行组合,以获得更好的结果。,SVM,广义最优分类面,假定训练数据 可以被一个超平面分开 我们进行正归化 此时分类间隔等于 使最大间隔最大等价于使 最小,最优分类面问题可以表示成约束优化问题 Minimize Subject to,SVM多类的情况,SVM本质上是两类分类器. 常用的SVM多值分类器，利用线性判别函数设计多类分类器有多种方法。例如 可以把k类问题转化为k个两类问题，其中第i 个问题是用线性判别函数把属于Ci类与不属于Ci类的点分开。 更复杂一点的方法是用k(k-1)/2个线性判别函数，把样本分为k个类别，每个线性判别函数只对其中的两个类别分类。,SVM训练算法,传统的利用标准二次型优化技术解决对偶问题的方法,是SVM训练算法慢及受到训练样本集规模制约的主要原因。 目前已提出了许多解决方法和改进算法,主要是从如何处理大规模样本集的训练问题、提高训练算法收敛速度等方面改进。 主要有：分解方法、修改优化问题法、增量学习法、几何方法等分别讨论。,SVM分类算法,训练好SVM分类器后,得到的支持向量被用来构成决策分类面。对于大规模样本集问题,SVM训练得到的支持向量数目很大,则进行分类决策时的计算代价就是一个值得考虑的问题。 解决方法如：缩减集(Reduced Set) SVM方法，采用缩减集代替支持向量集,缩减集中的向量不是支持向量,数目比支持向量少,但它们在分类决策函数中的形式与支持向量相同。,SVM方法的特点,SVM 的最终决策函数只由少数的支持向量所确定,计算的复杂性取决于支持向量的数目,而不是样本空间的维数