第七章机器学习课件

12023/10/23机器学习要介绍的内容机器学习概述统计学习理论的方法基于符号的方法连接主义的方法遗传与进化的方法第七章机器学习22023/10/23机器学习的定义机器学习还没有统一的定义机器学习的一种定义:机器学习是一门研究机器获取新知识和新技能,并识别现有知识的学问。

另一种机器学习定义：如果一个计算机程序针对某类任务T的用P衡量的性能根据经验E来自我完善。那么我们称这个计算机程序在从经验E中学习，针对某类任务T，它的性能用P来衡量任何智能系统必须具备学习的能力学习是使得智能主体在与环境交互的过程中改变自己.

第七章机器学习

7.1概述32023/10/23机器学习研究的几种观点统计学习理论--基于统计理论进行的推断、预测等学习方法。符号主义采用符号来表示问题域中的实体极其关系,通过对符号语言表示的规则进行搜索，试图用这些符号来推出新的、有效的并且也用这些符号表达的一般规则。连接主义受生物神经网络系统的启发，把知识表示为由小的个体处理单元组成的网络的激活或者抑制状态模式。学习是通过训练数据来修改网络结构和连接权值来实现。遗传和进化观点，在开始时有一组问题的后选解，根据他们解决问题的能力来进化，适者生存，并相互交叉产生下一代解，这样，解不断的增强就像达尔文描述的生物世界一样第七章机器学习

7.1概述42023/10/23机器学习问题的表示系统s是要研究的对象，给定输入x，得到输出yLM是所求的学习机，预测输出y’机器学习目的根据给定的已知训练样本，求取对系统输入／输出之间依赖关系的估计，使它能够对未知输出作出尽可能准确的预测。第七章机器学习

7.1概述输入x系统（s）背景知识输出y学习机（LM）预测输出y’图机器学习问题的基本模型52023/10/23机器学习问题的形式化表示已知变量y与输入x之间存在一定的未知依赖关系，即存在一个未知的联合概率F(x,y)，机器学习根据n个独立同分布观测样本(x1,y1),…(xn,yn)，在一组函数{f(x,w)}中求一个最优的函数f(x,w0)对依赖关系进行估计，使预测的期望风险最小第七章机器学习

7.1概述其中，{f(x,w)}为预测函数集，L()为损失函数预测函数又称为学习函数或学习模型62023/10/23机器学习中的三类基本问题模式识别函数逼近概率密度第七章机器学习

7.1概述输入x系统（s）背景知识输出y学习机（LM）预测输出y’72023/10/23模式识别问题的损失函数模式识别问题，其实是个分类问题多模式识别问题可以分解成若干个两模式识别问题预测函数可只考虑二值函数y是只取0，1损失函数可定义为：第七章机器学习

7.1概述82023/10/23函数逼近问题的损失函数y是连续变量，是x的函数f(x,w)是实函数损失函数可定义为第七章机器学习

7.1概述92023/10/23概率密度估计问题的损失函数学习的目的是根据训练样本确定x的概率分布。将密度函数记为p(x,w)，损失函数可以定义为：第七章机器学习

7.1概述102023/10/23经验风险期望风险是预测函数在整个样本空间上出错率的数学期望期望风险必须依赖于联合概率的信息联合概率未知，因此期望风险实际上不可求传统的学习方法采用了经验风险来近似期望风险定义经验风险第七章机器学习

7.1概述112023/10/23经验风险最小化经验风险为训练样本集上的平均错误率设计学习函数使经验风险最小化。经验风险最小化与期望风险最小化的等价前提是样本数据足够多只有在样本数趋于无穷大时，其性能才有理论上的保证。但在小样本的情况下，期望风险最小化到经验风险最小化并没有可靠的理论依据，只是直观上合理的想当然做法。在实际应用中，一般难以取得理想的效果。第七章机器学习

7.1概述122023/10/23推广能力（泛化能力）学习机器对未来输出进行正确预测的能力称为推广能力（或泛化能力）。在某些情况下，当训练误差过小反而会导致推广能力的下降这就是过学习问题。出现过学习现象的原因：一是因为学习样本不充分；二是学习机器设计不合理。这两个问题是互相关联的。第七章机器学习

7.1概述132023/10/23预测问题举例

绿色曲线：y=sin(2πx)蓝点：有随机噪声的样本目标：曲线拟合，以便对新的输入值x’，预测输出y’第七章机器学习

7.1概述142023/10/23多项式曲线拟合（回归）第七章机器学习

7.1概述学习，首先要选择一种模型形式这里，我们选择多项式曲线由于多项式对于未知参数是线性的这种模型称为线性模型152023/10/23确定参数w第七章机器学习

7.1概述如何训练模型（确定w）因为是线性模型风险函数选择误差平方和我们要确定w，使风险最小162023/10/23

多项式次数M的选择thebestfittothefunction第七章机器学习

7.1概述欠拟合：对数据拟合差表示性差过拟合：对训练数据精确拟合，对函数表示差172023/10/23测试数据进行评价均方根(RMS)误差(风险):N:标准化平方根:在同一尺度下度量ERMS

第七章机器学习

7.1概述从图中看出：泛化性依赖M选择：M=3-9过拟合：对训练数据精确拟合，对函数表示差在M=9，为什么会震荡？182023/10/23多项式系数

第七章机器学习

7.1概述用不同次数下的w，考察欠拟合与过拟合问题随着M的增加，为了拟合随机噪音，w在变大192023/10/23数据集规模产生的影响

数据集越大，拟合数据的模型就越灵活第七章机器学习

7.1概述202023/10/23预测函数复杂性与泛化能力

从前例可以看出：“最优拟合函数”不一定能正确代表原来的函数模型。原因是：用一个复杂的模型去拟合有限的样本，结果就会丧失推广能力。有限样本下学习机器的复杂性与推广性之间的矛盾。

有时，已知问题是某个比较复杂的模型：

由于训练样本有限，如用复杂预测函数去学习效果通常不如用相对简单的预测函数。第七章机器学习

7.1概述212023/10/23统计学习理论的主要内容统计学习理论被认为是目前针对小样本统计估计和预测学习的最佳理论。它从理论上较系统地研究了：经验风险最小化规则成立的条件、有限样本下经验风险与期望风险的关系如何利用这些理论找到新的学习原则和方法其主要内容包括如下四个方面：①经验风险最小化原则下统计学习一致性的条件；②在这些条件下关于统计学习方法推广性的界的结论；③在这些界的基础上建立的小样本归纳推理原则；④实现这些新的原则的实际方法。第七章机器学习

7.1概述222023/10/23学习过程一致性学习一致性的结论是统计学习理论的基础一致性条件，保证在经验风险最小化原则下得到的最优方法当样本无穷大时趋近于使期望风险最小的最优结果。学习过程的一致性：(x1,y1)…，(xn.yn)是n个独立同分布样本f(x,w*)最优预测函数Min(Remp(w))=Remp(w*|n)是经验风险最小值R(w*|n)为相应的真实风险值（期望风险值）R

(w0)=inf(R(w))为实际的最小真实风险值（期望风险值）如果：Remp(w*|n)→R

(w0)，R(w*|n)→R

(w0)第七章机器学习

7.1概述232023/10/23学习过程一致性的条件非平凡一致性:如果预测函数集中每个函数都满足一致性学习理论关键定理：对于有界的损失函数，经验风险最小化学习一致的充分必要条件是经验风险在如下意义上一致地收敛于真实风险其中，P表示概率，Remp(w)、R

(w)分别表示在n个样本下的经验风险和真实风险。第七章机器学习

7.1概述242023/10/23定义指标，衡量函数集性能学习理论关键定理没有给出什么样的学习方法能够满足这些条件为了研究函数集在经验风险最小化原则下的学习一致性问题和一致性收敛的速度定义一些指标：指示函数集的熵（VC熵）和生长函数退火的VC熵VC维第七章机器学习

7.1概述252023/10/23指示函数集的熵和生长函数指示函数集：{f(x,w)}样本集：Zn={zi=(xi,yi)i=1,…n}函数集中的函数能对这组样本实现的不同种分类数目：N(Zn)随机熵：H(Zn)=In(N(Zn))(函数集在这组样本上的)指示函数集的熵（VC熵）：H(n)=E(In(N(Zn)))(与样本无关)由于VC熵与样本的分布有关生长函数：G(n)=In(max(N(Zn)))第七章机器学习

7.1概述262023/10/23退火的VC熵定义为：Hann(n)=In(E(N(Zn)))∵Jensen不等式∑aiInxi≤In(∑aixi)∴H(n)≤Hann(n)≤G(n)≤nIn2第七章机器学习

7.1概述272023/10/23学习过程一致收敛的充分必要条件函数集学习过程一致收敛的充分必要条件是对任意的样本分布，都有limG(n)/n=0这时学习过程收敛速度一定是快的函数集学习收敛速度快的充分必要条件是limHann(n)/n=0第七章机器学习

7.1概述282023/10/23生长函数的性质所有函数集的生长函数或者：G(n)=nIn2或者G(n)≤hIn(n/h+1)n>h其中，h是一个整数可以看出，生长函数要么是线性的，要么以参数为h的对数函数为上界。第七章机器学习

7.1概述G(n)nIn2nhhIn(n/h+1)292023/10/23VC维函数集能够把样本集打散：函数集中的函数有2h种形式把h个样本的样本集分为两类，指示函数集的VC维：函数集能够打散的最大样本集的h如果指示函数集的生长函数是线性的，其VC维为无穷大如果生长函数以参数为h的对数函数为上界，则函数集的VC维是hVC维是对由学习机器实现的分类函数族的容量或表示能力的测度。第七章机器学习

7.1概述302023/10/23VC维与学习过程一致性经验风险最小化学习过程一致的充分必要条件是函数集的VC维有限，且这时收敛速度是快的。第七章机器学习

7.1概述312023/10/23推广性的界对于两类分类问题，对指示函数集中的所有函数，经验风险和实际风险之间至少以概率1-η满足：第七章机器学习

7.1概述Φ称为置信范围，或VC信任置信范围既受置信概率概率1-η的影响，也受VC维和样本数目的影响当n/h较小时，置信范围较大，用经验风险近似真实风险就有较大的误差当n/h较大，则置信范围就会很小，经验风险最小化的最优解就接近实际的最优解。322023/10/23对推广性界的说明推广性的界是对于最坏情况的结论给出的界在很多情况下是松弛的，尤其当VC维比较高时更是如此。

VC维无穷大时这个界就不再成立这种界往往只在对同一类学习函数进行比较时是有效的，用于指导从函数集中选择最优的函数在不同函数集之间比较却不一定成立。第七章机器学习

7.1概述332023/10/23函数子集序列（子集结构）经验风险最小化原则在样本数目有限时不合理：需要同时最小化经验风险和置信范围。考虑分解函数集S={f(x,w)}为一个函数子集序列（或叫子集结构）:

S1

S2

…

Sn

…

S:使各个子集能够按照置信范围φ的大小排列，也就是按VC维的大小排列，即：

h1≤h2≤…≤hn≤…≤hS同一个子集中置信范围就相同第七章机器学习

7.1概述342023/10/23结构风险最小化原则SRM在每一个子集中寻找最小经验风险通常它随着子集复杂度的增加而减小选择最小经验风险与置信范围之和最小的子集，就可以达到期望风险的最小，这个子集中使经验风险最小的函数就是要求的最优函数。第七章机器学习

7.1概述352023/10/23SnS*经验风险置信范围真实风险的界h1h*hnhS1S*Sn结构风险最小化图示风险第七章机器学习

7.1概述欠学习过学习362023/10/23合理的函数子集结构应满足两个基本条件：一是每个子集的VC维是有限的且满足h1≤h2≤…≤hn≤…≤hS二是每个子集中的函数对应的损失函数或者是有界的非负函数，或者对一定的参数对（p,τk）满足如下关系第七章机器学习

7.1概述Q(z,α)为损失函数372023/10/23结构风险最小化原则下，分类器的设计过程设计过程包括以下两方面任务：选择一个适当的函数子集，使之对问题来说有最优的分类能力；从这个子集中选择一个判别函数，使经验风险最小。第一步相当于模型选择，而第二步则相当于在确定了函数形式后的参数估计。第七章机器学习

7.1概述382023/10/23寻找具体使用结构风险最小化原则的方法结构风险最小化原则比经验风险最小化原则更科学最终目的是在经验风险和置信范围之间进行折中实际上实施这一原则并不容易如果能够找到一种子集划分方法，使得不必逐一计算就可以知道每个子集中所可能取得的最小经验风险，则两步任务就可以分开进行：先选择使置信范围最小的子集，然后在其中选择最优函数。结构风险最小化的一般原则可以用不同的方法实现支持向量机是其中最成功的一个通过固定经验风险而最小化置信范围实现的。第七章机器学习

7.1概述392023/10/237.2线性分类器第七章机器学习

7.2线性分类器402023/10/23线性分类器定义

在二类分类问题中,如果我们的学习函数选择为：第七章机器学习

7.2线性分类器这种学习函数称为线性分类器412023/10/23a考虑对下面情况的分类第七章机器学习

7.2线性分类器422023/10/23采样线性分类，可以这样第七章机器学习

7.2线性分类器432023/10/23采样线性分类，也可以这样Copyright©2001,2003,AndrewW.Moore第七章机器学习

7.2线性分类器442023/10/23采样线性分类，还可以这样Copyright©2001,2003,AndrewW.Moore第七章机器学习

7.2线性分类器452023/10/23分类超平面有训练集：(xi,yi),i=1,2,…N;yi{+1,-1}如果分类函数y=wx+b，能够正确训练集超平面（Hyperplane）:

wx+b=0称为分类超平面第七章机器学习

7.2线性分类器462023/10/23分类间隔样本点(xi,yi),到超平面H的函数间隔：yi(w⋅xi+b)

几何间隔:只需换成归一化函数(w/||w||，b/||w||)分类间隔（样本集到分类超平面的间隔）:样本集中所有点到分类超平面间隔（几何间隔）中的最小值第七章机器学习

7.2线性分类器472023/10/23感知机算法第七章机器学习

7.2线性分类器给定线性可分样集S，学习率η∈R+W0=0,b0=0,k;R=max||xi||;do{k=0;for(i=1;i≤n;i++){if(yi(wk⋅xi+bk)≤0){wk+1=wk+η⋅yi⋅xi;bk+1=bk+η⋅yi⋅R2;k++;}}while(k>0)482023/10/23分类间隔与误分次数的关系

在采样感知机算法时，若分类间隔=δ，R=max||xi||

i=1,...,n，则：第七章机器学习

7.2线性分类器误分次数一定程度上代表分类器的误差分类间隔越大的解，它的误差上界越小。最大化分类间隔成了训练阶段的目标492023/10/23最优分类面要求分类面能将两类正确分开(训练错误率为0),且使分类间隔最大第七章机器学习

7.2线性分类器502023/10/23固定斜率时，最大间隔分类面的导出设过两类中最靠近分类面的点的线分别为：w’⋅x+b’=k1l1w’⋅x+b’=k2l2平行移动分类面，使：K1=

k2=

k令w=w’/k,b=b’/k,则l1,l2变为：w⋅x+b=1

w’⋅x+b=1分类面则为：w⋅x+b=0第七章机器学习

7.2线性分类器wx+b>1wx+b<1wx+b=1wx+b=-1wx+b=0512023/10/23固定斜率时，最大间隔的计算？考虑2维空间中的间隔情况求出两条极端直线的距离，即“间隔”

：第七章机器学习

7.2线性分类器522023/10/23极大化“间隔”的思想导致求解下列对变量和的最优化问题说明：只要我们求得该问题的最优解，从而构造分划超平面，求出决策函数。上述方法对一般上的分类问题也适用.原始问题最优分类面的导出第七章机器学习

7.2线性分类器532023/10/23支持向量最靠近分类面的样本点，称为支持向量

第七章机器学习

7.2线性分类器542023/10/23求解原始问题为求解原始问题，根据最优化理论，我们转化为对偶问题来求解对偶问题

为原始问题中与每个约束条件对应的Lagrange乘子。这是一个不等式约束条件下的二次函数寻优问题，存在唯一解552023/10/23线性可分问题计算，选择的一个正分量,并据此计算事实上，的每一个分量都与一个训练点相对应。而分划超平面仅仅依赖于不为零的训练点，而与对应于为零的那些训练点无关。称不为零的这些训练点的输入为支持向量(SV)构造分划超平面,决策函数根据最优解562023/10/23近似线性可分问题不要求所有训练点都满足约束条件，为此对第个训练点引入松弛变量(SlackVariable),把约束条件放松到。

体现了训练集被错分的情况，可采用作为一种度量来描述错划程度。两个目标：1.间隔尽可能大2.错划程度尽可能小显然，当充分大时，样本点总可以满足以上约束条件。然而事实上应避免太大，所以需在目标函数对进行惩罚（即“软化”约束条件）572023/10/23因此，引入一个惩罚参数，新的目标函数变为:

体现了经验风险，而则体现了表达能力。所以惩罚参数实质上是对经验风险和表达能力匹配一个裁决。当时，近似线性可分SVC的原始问题退化为线性可分SVC的原始问题。近似线性可分问题582023/10/23(广义)线性支持向量分类机算法设已知训练集，其中2.选择适当的惩罚参数，构造并求解最优化问题3.计算，选择的一个分量，并据此计算出4.构造分划超平面,决策函数求得592023/10/23非线性分类例子:602023/10/23Non-linearClassificationWhatcanwedoiftheboundaryisnonlinear?Idea:transformthedatavectorstoaspacewheretheseparatorislinear612023/10/23Non-linearClassificationThetransformationmanytimesismadetoaninfinitedimensionalspace,usuallyafunctionspace.Example:xcos(uTx)622023/10/23Non-linearSVMsTransformx

(x)Thelinearalgorithmdependsonlyonxxi,hencetransformedalgorithmdependsonlyon(x)(xi)UsekernelfunctionK(xi,xj)suchthatK(xi,xj)=(x)(xi)

632023/10/23设训练集，其中假定可以用平面上的二次曲线来分划：现考虑把2维空间映射到6维空间的变换上式可将2维空间上二次曲线映射为6维空间上的一个超平面：非线性分类642023/10/23可见，只要利用变换，把所在的2维空间的两类输入点映射到所在的6维空间，然后在这个6维空间中，使用线性学习机求出分划超平面：最后得出原空间中的二次曲线：怎样求6维空间中的分划超平面？(线性支持向量分类机)非线性分类652023/10/23需要求解的最优化问题其中非线性分类662023/10/23在求得最优化问题的解后，得到分划超平面其中最后得到决策函数或

线性分划－>非线性分划

代价：2维空间内积－>6维空间内积非线性分类672023/10/23为此，引进函数有比较(2)和(3)，可以发现这是一个重要的等式，提示6维空间中的内积可以通过计算中2维空间中的内积得到。非线性分类682023/10/23实现非线性分类的思想给定训练集后，决策函数仅依赖于而不需要再考虑非线性变换如果想用其它的非线性分划办法，则可以考虑选择其它形式的函数，一旦选定了函数，就可以求解最优化问题得，而决策函数692023/10/23决策函数其中实现非线性分类的思想702023/10/23设是中的一个子集。称定义在上的函数是核函数(正定核或核)，如果存在着从到某一个空间的映射使得其中表示中的内积核函数(核或正定核)定义712023/10/23多项式内核径向基函数内核RBFSigmoind内核目前研究最多的核函数主要有三类：得到q阶多项式分类器每个基函数中心对应一个支持向量，它们及输出权值由算法自动确定包含一个隐层的多层感知器，隐层节点数是由算法自动确定核函数的选择722023/10/23多项式内核Thekindofkernelrepresentstheinnerproductoftwovector(point)inafeaturespaceofdimension.Forexample732023/10/23－EdgarOsuna(Cambridge,MA)等人在IEEENNSP’97发表了AnImprovedTrainingAlgorithmforSupportVectorMachines,提出了SVM的分解算法，即将原问题分解为若干个子问题，按照某种迭代策略，通过反复求解子问题，最终使得结果收敛于原问题的最优解。传统的利用二次型优化技术解决对偶问题时：需要计算存储核函数矩阵。当样本点数较大时，需要很大的存储空间。例如：当样本点超过4000时，存储核函数矩阵就需要多达128兆内存；

SVM在二次型寻优过程中要进行大量的矩阵运算，通常寻优算法占用了算法时间的主要部分。SVM寻优算法742023/10/23考虑去掉Lagrange乘子等于零的训练样本不会影响原问题的解，采用一部分样本构成工作样本集进行训练，移除其中的非支持向量，并把训练结果对剩余样本进行检验，将不符合KKT条件的样本与本次结果的支持向量合并成为一个新的工作集。然后重新训练，如此重复获得最优结果。例如：基于这种思路的算法。根据子问题的划分和迭代策略的不同，大致分为：块算法(ChunkingAlgorithm)：SVM寻优算法752023/10/23SMO使用了块与分解技术，而SMO算法则将分解算法思想推向极致，每次迭代仅优化两个点的最小子集，其威力在于两个数据点的优化问题可以获得解析解，从而不需要将二次规划优化算法作为算法一部分。尽管需要更多的迭代才收敛，但每个迭代需要很少的操作，因此算法在整体上的速度有数量级的提高。另外，算法其他的特征是没有矩阵操作，不需要在内存中存储核矩阵。块算法(ChunkingAlgorithm)：SVM寻优算法762023/10/23SMO算法每次迭代时，在可行的区域内选择两点，最大化目标函数，从而优化两个点的最小子集。无论何时，当一个乘子被更新时，调整另一个乘子来保证线性约束条件成立，保证解不离开可行区域。每步SMO选择两个参数优化，其他参数固定，可以获得解析解。尽管需要更多的迭代才收敛，但每个迭代需要很少的操作，因此算法在整体上的速度有数量级的提高。另外，算法其他的特征是没有矩阵操作，不需要在内存中存储核矩阵。SVM寻优算法772023/10/23SVM寻优算法类别名称测试样本数错误分类数准确度（%）政治146497.26军事830100经济137397.81法律32293.75农业106298.11体育90198.89卫生34197.06工业87297.70科技111298.20交通40197.50生活91198.90宗教30100天气24291.67合计9842197.87782023/10/23SMO算法核缓存算法SMO算法在每次迭代只选择两个样本向量优化目标函数，不需要核矩阵。虽然没有核矩阵操作，但仍需要计算被选向量和训练集中所有样本向量的核函数，计算次数为2n（n为训练集中的样本数）。如果训练集中的样本选取有误，在噪声比较多的情况下，收敛会很慢，迭代次数很多，则核函数的计算量也是非常可观的，SMO算法的优点就完成失去了。同时，考虑到文本分类的文本向量一般维数比较大，核函数的计算将会非常耗时，尤其在高价多项式核和高斯核等核函数的计算中表现更加明显。SVM寻优算法792023/10/23SMO算法核缓存算法在内存中为SMO算法核函数开辟n行m列的核矩阵空间。其中：n为训练集中的样本数；m是为可调节参数，根据实际的内存大小进行调整，每列存放训练集中某个样本向量与训练集中所有样本向量的核函数计算结果列表。在核矩阵列头生成m个节点的双向循环链表队列，每个节点指向核矩阵的列，通过双向循环链表队列实现核矩阵中的核函数列唤入唤出操作。同时，为了实现样本向量的核函数列的快速查找，为每个训练样本向量设计了快速索引列表，通过索引列表判断该训练样本向量的核函数列是否在核矩阵中，并确定在哪一列。SVM寻优算法802023/10/23SVM寻优算法选择一个训练集，通过调整核缓冲参数的大小，记录不同核缓存大小情况下训练时间，结果如下表：核缓存大小(Mb)训练样本数核矩阵迭代次数训练时间(M:S)156245624*23407267:061056245624*233407263:502056245624*466407262:413056245624*699407261:564056245624*932407261:295056245624*1165407261:236056245624*1398407261:087056245624*1631407261:058056245624*1864407261:049056245624*2097407261:0710056245624*2330407261:3725056245624*5624407261:12812023/10/23通过引入核缓存机制，有效的改进了SMO算法，提高了文本分类的训练速度。在核缓存机制中采用简单的hash查找算法和队列FILO算法，有效提高了核矩阵查找和唤入唤出操作的效率。设置核矩阵列参数，通过调节列参数，可以灵活的根据系统运行情况调整训练的时间和空间开销，避免因系统空间开销过大使系统运行效率下降，反而影响训练速度。SVM寻优算法822023/10/23活动向量集选择算法

当训练样本数非常大的时候，如果系统能够提供的核缓冲大小很有限，那么能够同时保存在核缓冲中训练样本的核函数数目在训练样本数中所占比例将非常的小。在训练过程中，训练样本在核缓冲中的核函数命中率将显著下降，导致核缓冲中的核函数被频繁的唤入唤出，而每执行一次唤入唤出操作将引起系统重新计算训练样本的核函数，核缓存的作用被很大程度的削弱了。如果出现这样的情况，要么增加系统的存储空间；要么减少训练样本数，才能提高系统的训练速度。为解决训练样本数多，系统内存空间小的矛盾，本文通过活动向量集选择算法，比较好地解决了这个问题。SVM寻优算法832023/10/23活动向量集选择算法

算法的主要思想是：定期检查训练样本集，在收敛前预先确定训练样本集中一些边界上的点（alpha=0，或者alpha=C）是否以后不再被启发式选择，或者不再被判定为最有可能违例，如果存在这样的点，将它们从训练样本集中剔除出去，减少参加训练的样本数。该算法基于如下的认识：经过多次迭代后，如果样本的拉格朗日乘子一直为0，该点被当前估计的支持向量集所确定的超平面区分得很开，即使以后支持向量集发生变化，该点也不会是最靠近超平面的点，则可以确定该样本不是支持向量；经过多次迭代后，如果样本的拉格朗日乘子一直为非常大的C常数，即使以后支持向量集发生变化，该点也不会远离超平面，则可以确定该样本是上边界处的支持向量SVM寻优算法842023/10/23活动向量集选择算法

这样就可以在SMO算法收敛前，提前将边界上的点从训练样本集中剔除，逐渐缩小参加训练的活动样本集，从而减少SMO算法对核缓存空间的要求，提高训练速度。训练开始前，训练活动集样本初始化为全部训练样本。每经过一定次数的迭代（比如迭代1000次），如果算法还没有收敛，应检查活动集中的向量，检查是否有训练样本可以不参加迭代运算。检查完当前活动向量集中所有样本后，产生了新的活动向量集。如果新的活动向量集的样本数减少一成以上（含一成），则可以收缩当前活动向量集，用新的活动向量集替换当前活动向量集。当活动向量集的样本数减少到一定的程度，对核缓存空间的要求不是很大的时候，继续减少训练样本对训练速度的提高就非常有限了，这时就没有必要再减少训练样本了。SVM寻优算法852023/10/23将工作样本集的大小固定在算法速度可以容忍的限度内，迭代过程选择一种合适的换入换出策略，将剩余样本中的一部分与工作样本集中的样本进行等量交换，即使支持向量的个数超过工作样本集的大小，也不改变工作样本集的规模，而只对支持向量中的一部分进行优化。例如:算法2.固定工作样本集(Osunaetal.)：SVM寻优算法862023/10/23SVMapplicationsPatternrecognitionFeatures:wordscountsDNAarrayexpressiondataanalysisFeatures:expr.levelsindiff.conditionsProteinclassificationFeatures:AAcomposition872023/10/23HandwrittenDigitsRecognition882023/10/23ApplyingSVMstoFaceDetectionTheSVMface-detectionsystem1.Rescaletheinputimageseveraltimes2.Cut19x19windowpatternsoutofthescaledimage3.Preprocessthewindowusingmasking,lightcorrectionandhistogramequalization4.ClassifythepatternusingtheSVM5.Iftheclasscorrespondstoaface,drawarectanglearoundthefaceintheoutputimage.892023/10/23ApplyingSVMstoFaceDetectionExperimentalresultsonstaticimagesSetA:313high-quality,samenumberoffacesSetB:23mixedquality,totalof155faces902023/10/23ApplyingSVMstoFaceDetectionExtensiontoareal-timesystemAnexampleoftheskindetectionmoduleimplementedusingSVMsFaceDetectiononthePC-basedColorRealTimeSystem912023/10/23ReferencesVladimirVapnik.TheNatureofStatisticalLearningTheory,Springer,1995AndrewW.Moore.cmsc726:SVMs./~awm/tutorialsC.Burges.Atutorialonsupportvectormachinesforpatternrecognition.DataMiningandKnowledgeDiscovery,2(2):955-974,1998./burges98tutorial.htmlVladimirVapnik.StatisticalLearningTheory.Wiley-Interscience;1998ThorstenJoachims(joachims_01a):AStatisticalLearningModelofTextClassificationforSupportVectorMachinesBenRubinstein.StatisticalLearningTheory.

Dept.ComputerScience&SoftwareEngineering,UniversityofMelbourne;