




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第八章
高级人工智能1/30/2021Chap8
SVM
Zhongzhi
Shi1史忠植中国科学院计算技术研究所支持向量机Support
Vector
Machines内容提要1/30/2021Chap8
SVM
Zhongzhi
Shi2统计学习方法概述统计学习问题学习过程的泛化能力支持向量机SVM寻优算法应用统计学习方法概述1/30/2021Chap8
SVM
Zhongzhi
Shi3统计方法是从事物的外在数量上的表现去推断该事物可能的规律性。科学规律性的东西一般总是隐藏得比较深,最初总是从其数量表现上通过统计分析看出一些线索,然后提出一定的假说或学说,作进一步深入的理论研究。当理论研究提出一定的结论时,往往还需要在实践中加以验证。就是说,观测一些自然现象或专门安排的实验所得资料,是否与理论相符、在多大的程度上相符、偏离可能是朝哪个方向等等问题,都需要用统计分析的方法处理。统计学习方法概述1/30/2021Chap8
SVM
Zhongzhi
Shi4近百年来,统计学得到极大的发展。我们可用下面的框架粗略地刻划统计学发展的过程:1900-19201920-19401940-1960数据描述统计模型的曙光数理统计时代随机模型假设的挑战松弛结构模型假设1990-1999
建模复杂的数据结构统计学习方法概述1/30/2021Chap8
SVM
Zhongzhi
Shi5从1960年至1980年间,统计学领域出现了一场革命要从观测数据对依赖关系进行估计,只要知道未知依赖关系所属的函数集的某些一般的性质就足够了引导这一革命的是60年代的四项发现: Tikhonov,Ivanov和Philips发现的关于解决不适问题的正则化原则; Parzen,Rosenblatt 和Chentsov发现的非参数统学; Vapnik和Chervonenkis发现的在泛函数空间的大定律,以及它与学习过程的关系; Kolmogorov,Solomonoff 和Chaitin发现的算法复杂性及其与归纳推理的关系。这四项发现也成为人们对学习过程研究的重要基础。统计学习方法概述1/30/2021Chap8
SVM
Zhongzhi
Shi6统计学习方法: 传统方法:统计学在解决机器学习问题中起着基础性的作用。传统的统计学所研究的主要是渐近理论即当样本趋向于无穷多时的统计性质。统计方法主要考虑测试预想的假设和数据模型拟合。它依赖于显式的基本概率模型。模糊集粗糙集支持向量机统计学习方法概述1/30/2021Chap8
SVM
Zhongzhi
Shi7统计方法处理过程可以分为三个阶段:(1)搜集数据:采样、实验设计(2)分析数据:建模、知识发现、可视化(3)进行推理:预测、分类常见的统计方法有:回归分析(多元回归、自回归等)判别分析(贝叶斯判别、费歇尔判别、非参数判别等)聚类分析(系统聚类、动态聚类等)探索性分析(主元分析法、相关分析法等)等。COLT(Computational
Learning
Theory)支持向量机 SVM是一种基于统计学习理论的机器学习方法,它是由Boser,Guyon,Vapnik在COLT-92上首次提出,从此迅速发展起来 VapnikVN.1995.TheNatureofStatisticalLearningTheory.SpringeVerlag,NewYork VapnikVN.1998.StatisticalLearninTheory.Wiley-IntersciencePublicatiJohnWiley&Sons,Inc 目前已经在许多智能信息获取与处理领域都取得了成功的应用。1/30/2021Chap8
SVM
Zhongzhi
Shi8统计学习理论1/30/2021Chap8
SVM
Zhongzhi
Shi9 统计学习理论是小样本统计估计和预测学习的最佳理论。 假设输出变量Y与输入变量X之间存在某种对应的依赖关系,即一未知概率分布P(X,Y),P(X,Y)反映了某种知识。学习问题可以概括为:根据l个独立同分布(independentlydrawnandidenticallydistributed)的观测样本trainset,(x1,y1),(x2,y2),…,(xn,yn)函数估计模型学习样本的函数:
产生器
(G)
generates
observations
x(typically
in
Rn),
independentlydrawn
from
some
fixed
distributionF(x)
训练器Supervisor
(S)
labels
eachinput
x
with
an
output
value
yaccording
to
some
fixed
distributionF(y|x) 学习机Learning Machine (LM) “learnsfromani.i.d.l-sampleof(x,y)-pairsoutputfromGandS,bychoosingafunctionthatbestapproximatesSfromaparameterisedfunctionclassf(x, ),where isintheparameterset关键概念:F(x,y),ani.i.d.l-sampleonF,functionsf(x,)andtheequivalentrepresentationofeachfusingitsindexGSLMxy^y1/30/2021Chap8
SVM
Zhongzhi
Shi10期望风险学习到一个假设H=f(x,w)作为预测函数,其中w是广义参数.它对F(X,Y)的期望风险R(w)是(即统计学习的实际风险):其中,{f(x,w)}称作预测函数集,w为函数的广义参数。{f(x,w)}可以表示任何函数集。L(y,f(x,w为由于用f(x,w)对y进行预测而造成的损失。不同类型的学习问题有不同形式的损失函数。1/30/2021Chap8
SVM
Zhongzhi
Shi11而对train
set上产生的风险Remp(w)被称为经验风险(学习的训练误差):首先Remp(w)和R(w)都是w的函数,传统概率论中的定理只说明了(在一定条件下)当样本趋于无穷多时Remp(w)将在概率意义上趋近于R(w),却没有保证使Remp(w)最小的点也能够使R(w)最小(同步最小)。1/30/2021Chap8
SVM
Zhongzhi
Shi12经验风险根据统计学习理论中关于函数集的推广性的界的结论,对于两类分类问题中的指示函数集f(x,w)的所有函数(当然也包括使经验风险员小的函数),经验风险Remp(w)和实际风险R(w)之间至少以不下于1-η(0≤η≤1)的概率存在这样的关系:经验风险1/30/2021Chap8
SVM
Zhongzhi
Shi13h是函数H=f(x,w)的VC维,l是样本数.1/30/2021Chap8
SVM
Zhongzhi
Shi14VC维(Vapnik-ChervonenkisDimension)。模式识别方法中VC维的直观定义是:对一个指示函数集,如果存在h个样本能够被函数集里的函数按照所有可能的2h种形式分开,则称函数集能够把h个样本打散。函数集的VC维就是它能打散的最大样本数目h。VC维一般的学习方法(如神经网络)是基于Remp(w)最小,满足对已有训练数据的最佳拟和,在理论上可以通过增加算法(如神经网络)的规模使得Remp(w)不断降低以至为0。但是,这样使得算法(神经网络)的复杂度增加,VC维h增加,从而φ(h/l)增大,导致实际风险R(w)增加,这就是学习算法的过拟合(Overfitting).1/30/2021Chap8
SVM
Zhongzhi
Shi15过学习过学习Overfitting
and
underfittiProblem:
how
rich
class
of
classifications
q(x;θ)
to
use.underfitting good
fit
overfittingProblem
of
generalization:
a
small
emprical
risk
Remp
does
noimply
small
true
expected
risk
R.1/30/2021Chap8
SVM
Zhongzhi
Shi16学习理论的四个部分1/30/2021Chap8
SVM
Zhongzhi
Shi17学习过程的一致性理论What
are
(necessary
and
sufficient)
conditions
for
consistency(convergence
of
Remp
to
R)
of
a
learning
process
based
on
the
ERMPrinciple?学习过程收敛速度的非渐近理论How
fast
is
the
rate
of
convergence
of
a
learning
proces控制学习过程的泛化能力理论How
can
one
control
the
rate
of
convergence
(thegeneralization
ability)
of
a
learning
process?构造学习算法的理论How
can
one
construct
algorithms
that
can
control
thegeneralization
ability?结构风险最小化归纳原则(SRM)1/30/2021Chap8
SVM
Zhongzhi
Shi18
ERM
is
intended
for
relatively
largesamples
(large
l/h)Large
l/h
induces
a
smallwhichdecreases
the
the
upper
bound
on
risk
Small
samples?
Small
empirical
riskdoesn’t
guarantee
anything!…we
need
to
minimise
both
terms
of
theRHS
of
the
risk
boundsThe
empirical
risk
of
the
chosenAn
expression
depending
on
the
VC
dimension
of结构风险最小化归纳原则(SRM)1/30/2021Chap8
SVM
Zhongzhi
Shi19
The
Structural
Risk
Minimisation
(SRM)PrincipleLet
S
=
{Q(z,),}.
An
admissiblestructure
S1S2…Sn
…
S:For
each
k,
the
VC
dimension
hk
of
Sk
is
finite
anh1≤h2≤…≤hn≤…≤hS
Every
Sk
is
either
is
non-negative
bounded,
orsatisfies
for
some
(p,
k)Forgivenz1,…,zlandanadmissiblestructureS1 S2…Sn…S,SRMchoosesfunctionQ(z,minimisingRempinSkforwhichtheguaranteedrisk(riskupper-bound)isminimal Thusmanagestheunavoidabletrade-offofqualityofapproximationplexityofapproximationS11/30/2021Chap8
SVM
Zhongzhi
Shi20S2Snhh1The
SRM
Principle
continuedhnh*结构风险最小化归纳原则(SRM)Sn风险界限Bound
on
the
ris置信范围Confidence
intervh*经验风险Empirical
riskhn
hh1S*S1
S*Sn结构风险最小化归纳原则(SRM)1/30/2021Chap8
SVM
Zhongzhi
Shi21支持向量机SVM1/30/2021Chap8
SVM
Zhongzhi
Shi22SVMs
are
learning
systems
thatuse
a
hyperplane
of
linear
functionsin
a
high
dimensional
feature
space
—
Kernel
funct
trained
with
a
learning
algorithm
from
optimizationtheory
—
Lagrange
Implements
a
learning
bias
derived
from
statisticallearning
theory
—
Generalisation
SVM
is
a
classifiderived
from
statistical
learning
theory
by
VapnikChervonenkis线性分类器ayestxff(x,w,b)=sign(w.x-b)denotes
+1denotes
-1How
would
youclassify
this
data?1/30/2021Chap8
SVM
Zhongzhi
Shi23f线性分类器xayestdenotes
+1denotes
-1f(x,w,b)=sign(w.x-b)1/30/2021Chap8
SVM
Zhongzhi
Shi24How
would
youclassify
this
data?f线性分类器xayestdenotes
+1denotes
-1f(x,w,b)=sign(w.x-b)1/30/2021Chap8
SVM
Zhongzhi
Shi25Copyright©2001,2003,AndrewW.MooreHow
would
youclassify
this
data?f线性分类器xayestdenotes
+1denotes
-1f(x,w,b)=sign(w.x-b)1/30/2021Chap8
SVM
Zhongzhi
Shi26Copyright©2001,2003,AndrewW.MooreHow
would
youclassify
this
data?f线性分类器xayestdenotes
+1denotes
-1f(x,w,b)=sign(w.x-b)1/30/2021Chap8
SVM
Zhongzhi
Shi27Copyright©2001,2003,AndrewW.MooreHow
would
youclassify
this
data?最大间隔fxayestdenotes
+1denotes
-1f(x,w,b)=sign(w.x-b)The
maximummargin
linearclassifier
is
thelinear
classifierwith
the
maximummargin.This
is
the
simplekind
of
SVM(Called
an
LSVM)Linear
SVM1/30/2021Chap8
SVM
Zhongzhi
Shi28Copyright©2001,2003,AndrewW.Moore分类超平面Training
set:
(xi,
yi),
i=1,2,…N;
yiHyperplane:
wx+b=0This
is
fully
determined
by
(w,b){+1,-1}1/30/2021Chap8
SVM
Zhongzhi
Shi29最大间隔According
to
a
theoremfrom
Learning
Theory,from
all
possible
lineardecision
functions
the
othat
maximises
the
margiof
the
training
set
willminimise
thegeneralisation
error.1/30/2021Chap8
SVM
Zhongzhi
Shi30最大间隔原则Note1:
decision
functions
(w,b)
and(cw,
cb)
are
the
sameNote2:
but
margins
as
measured
by
theoutputs
of
the
function
x
wx+bare
not
the
same
if
we
take
(cw,
cb)1/30/2021Chap8
SVM
Zhongzhi
Shi31Definition:
geometric
margin:
themargin
given
by
the
canonicaldecision
function,
which
is
whenc=1/||w||Strategy:we
need
to
maximise
thegeometric
margin!
(cf
result
fromlearning
theory)subject
to
the
constraint
thattraining
examples
are
classifiedcorrectlywwx+b=0wx+b>0wx+b<0AccordingtoNote1,wecandemandthefunctionoutputfthenearestpointstobe+1and–1onthetwosidesodecisionfunction.ThisremovesthescalingfreedomDenotinganearestpositiveexamplex+andanearestnegativeexamplex-,thisisComputingthegeometricmargin(thathastobemaximised):Andherearetheconstraints:最大间隔原则1/30/2021Chap8
SVM
Zhongzhi
Shi32wx+b=0wx+b=-1wx+b>1wx+b<1This
is
a
quadraticprogramming
problem
withlinear
inequality
constraiwx+b=1
There
are
well
knownMaximum
margin
–
summing
upGiven
a
linearly
separabletraining
set
(xi,
yi),i=1,2,…N;
yi
{+1,-1}Minimise
||w||2Subject
toprocedures
for
solving
it1/30/2021Chap8
SVM
Zhongzhi
Shi33支持向量The
training
pointsthat
are
nearest
to
theseparating
functionare
called
supportvectors.What
is
the
output
ofour
decision
functionfor
these
points?1/30/2021Chap8
SVM
Zhongzhi
Shi34分类问题的数学表示已知:训练集包含个样本点:说明: 是输入指标向量,或称输入,或称模式,其分量称为特征,或属性,或输入指标;是输出指标,或输出.问题:对一个新的模式 ,推断它所对应的输出 是1还是-1.实质:找到一个把 上的点分成两部分的规则.2维空间上的分类问题) n维空间上的分类问题.1/30/2021Chap8
SVM
Zhongzhi
Shi35根据给定的训练集,寻找上的一个其中,实值函数,用决策函数判断任一模式 对应的 值.可见,分类学习机——构造决策函数的方法(算法),两类分类问题线性分类学习机多类分类问题非线性分类学习机分类学习方法1/30/2021Chap8
SVM
Zhongzhi
Shi36分类学习方法SVM分类问题大致有三种:线性可分问题、近似线性可分问题、线性不可分问题。1/30/2021Chap8
SVM
Zhongzhi
Shi37考虑 上的线性可分的分类问题.这里有许多直线 能将两类点正确分开.如何选取和?简单问题:设法方向 已选定,如何选取 ?解答:选定 平行直线 极端直线和取 和的中间线为分划直线如何选取对应一个?,有极端直线 ,称和 之间的距离为“间隔”.显然应选使“间隔”最大的
。最大间隔法的直观导出1/30/2021Chap8
SVM
Zhongzhi
Shi38数学语言描述调整 ,使得令,则两式可以等价写为与此相应的分划直线表达式:给定适当的法方向1/30/2021Chap8
SVM
Zhongzhi
Shi39后,这两条极端直线可表示为如何计算分划间隔?考虑2维空间中极端直线之间的间隔情况求出两条极端直线的距离:1/30/2021Chap8
SVM
Zhongzhi
Shi40分划直线表达式为“间隔”为的最优化问,从而构造分划。说明:只要我们求得该问题的最优解超平面 ,求出决策函数上述方法对一般 上的分类问题也适用.
极大化“间隔”的思想导致求解下列对变量
和题原始问题1/30/2021Chap8
SVM
Zhongzhi
Shi41Margin
=H1平面:H2平面:…..(2)1/30/2021Chap8
SVM
Zhongzhi
Shi42…..(1)求解原始问题为求解原始问题,根据最优化理论,我们转化为对偶问题来求解对偶问题为原始问题中与每个约束条件对应的Lagrange乘子。这是一个不等式约束条件下的二次函数寻优问题,存在唯一解1/30/2021Chap8
SVM
Zhongzhi
Shi43线性可分问题计算,选择 的一个正分量 ,并据此计算事实上, 的每一个分量都与一个训练点相对应。而分划超平面仅仅依赖于 不为零的训练点,而与对应于 为零的那些训练点无关。称 不为零的这些训练点的输入
为支持向量(SV)构造分划超平面,决策函数根据最优解1/30/2021Chap8
SVM
Zhongzhi
Shi44近似线性可分问题不要求所有训练点都满足约束条件 ,为此对第 个训练点 引入松弛变量(SlackVariable) ,把约束条件放松到 。(即“软化”约束条件体现了训练集被错分的情况,可采用 作为一种度量来描述错划程度。两个目标:1.间隔 尽可能大 2.错划程度 尽可能小显然,当 充分大时,样本点 总可以满足以上约束条件。然而事实上应避免 太大,所以需在目标函数对 进行惩罚1/30/2021Chap8
SVM
Zhongzhi
Shi45因此,引入一个惩罚参数,新的目标函数变为:体现了经验风险,而 则体现了表达能力。所以惩罚参数 实质上是对经验风险和表达能力匹配一个裁决。当 时,近似线性可分SVC的原始问题退化为线性可分SVC的原始问题。近似线性可分问题1/30/2021Chap8
SVM
Zhongzhi
Shi46(广义)线性支持向量分类机算法1.设已知训练集 ,其中2.选择适当的惩罚参数,构造并求解最优化问题,选择 的一个分量,并据此3.计算计算出4.构造分划超平面,决策函数求得1/30/2021Chap8
SVM
Zhongzhi
Shi47非线性分类例子:1/30/2021Chap8
SVM
Zhongzhi
Shi48Non-linear
ClassificationWhat
can
we
do
if
the
boundary
is
nonlinear
?Idea:1/30/2021Chap8
SVM
Zhongzhi
Shi49transform
the
data
vectors
to
aspace
where
the
separator
islinearNon-linear
ClassificationThe
transformation
many
times
is
made
to
an
infinitedimensional
space,
usually
a
function
space.Example:
x
cos(uTx)1/30/2021Chap8
SVM
Zhongzhi
Shi50Non-linear
SVMsTransform
x
(x)
The
linear
algorithm
depends
only
on
xxi,
hencetransformed
algorithm
depends
only
on
(x)
(xi
Use
kernel
function
K(xi,xj)
such
that
K(xi,xj)=(xi)1/30/2021Chap8
SVM
Zhongzhi
Shi51设训练集假定可以用,其中平面上的二次曲线来分划:现考虑把2维空间映射到6维空间的变换上式可将2维空间上二次曲线映射为6维空间上的一个超平面:非线性分类1/30/2021Chap8
SVM
Zhongzhi
Shi52可见,只要利用变换,把所在的2维空间的两类输入点映射到所在的6维空间,然后在这个6维空间中,使用线性学习机求出分划超平面:最后得出原空间中的二次曲线:1/30/2021Chap8
SVM
Zhongzhi
Shi53怎样求6维空间中的分划超平面?(线性支持向量分类机)非线性分类需要求解的最优化问题其中非线性分类1/30/2021Chap8
SVM
Zhongzhi
Shi54在求得最优化问题的解 后,得到分划超平面其中最后得到决策函数或1/30/2021Chap8
SVM
Zhongzhi
Shi55线性分划->非线性分划代价:2维空间内积->6维空间内积非线性分类为此,引进函数有比较(2)和(3),可以发现这是一个重要的等式,提示6维空间中的内积可以通过计算 中2维空间中的内积得到。非线性分类1/30/2021Chap8
SVM
Zhongzhi
Shi56实现非线性分类的思想给定训练集后,决策函数仅依赖于而不需要再考虑非线性变换如果想用其它的非线性分划办法,则可以考虑选择其它形式的函数 ,一旦选定了函数,就可以求解最优化问题1/30得/2021,C而hap决8SV策MZh函ongz数hiShi57决策函数其中实现非线性分类的思想1/30/2021Chap8
SVM
Zhongzhi
Shi58设 是 中的一个子集。称定义在是核函数(正定核或核),如果存在着从空间 的映射上的函数到某一个使得其中表示中的内积核函数(核或正定核)定义1/30/2021Chap8
SVM
Zhongzhi
Shi59目前研究最多的核函数主要有三类:多项式内核得到q阶多项式分类器径向基函数内核RBF每个基函数中心对应一个支持向量,它们及输出权值由算法自动确定Sigmoind内核包含一个隐层的多层感知器,隐层节点数是由算法自动确定1/30/2021Chap8
SVM
Zhongzhi
Shi60核函数的选择多项式内核
The
kind
of
kernel
represents
the
innerproduct
of
two
vector(point)
in
a
featurespace
of
dimension.For
example1/30/2021Chap8
SVM
Zhongzhi
Shi61传统的利用二次型优化技术解决对偶问题时:需要计算存储核函数矩阵。当样本点数较大时,需要很大的存储空间。例如:当样本点超过4000时,存储核函数矩阵就需要多达128兆内存;SVM在二次型寻优过程中要进行大量的矩阵运算,通常寻优算法占用了算法时间的主要部分。■-EdgarOsuna(Cambridge,MA)等人在IEEENNSP’97发表了AnImprovedTrainingAlgorithmforSupportVectorMachines,提出了SVM的分解算法,即将原问题分解为若干个子问题,按照某种迭代策略,通过反复求解子问题,最终使得结果收敛于原问题的最优解。1/30/2021Chap8
SVM
Zhongzhi
Shi62SVM寻优算法根据子问题的划分和迭代策略的不同,大致分为:1.块算法(ChunkingAlgorithm):考虑去掉Lagrange乘子等于零的训练样本不会影响原问题的解,采用一部分样本构成工作样本集进行训练,移除其中的非支持向量,并把训练结果对剩余样本进行检验,将不符合KKT条件的样本与本次结果的支持向量合并成为一个新的工作集。然后重新训练,如此重复获得最优结果。例如:基于这种思路的 算法。SVM寻优算法1/30/2021Chap8
SVM
Zhongzhi
Shi63块算法(ChunkingAlgorithm):SMO使用了块与分解技术,而SMO算法则将分解算法思想推向极致,每次迭代仅优化两个点的最小子集,其威力在于两个数据点的优化问题可以获得解析解,从而不需要将二次规划优化算法作为算法一部分。尽管需要更多的迭代才收敛,但每个迭代需要很少的操作,因此算法在整体上的速度有数量级的提高。另外,算法其他的特征是没有矩阵操作,不需要在内存中存储核矩阵。1/30/2021Chap8
SVM
Zhongzhi
Shi64SVM寻优算法SMO算法每次迭代时,在可行的区域内选择两点,最大化目标函数,从而优化两个点的最小子集。无论何时,当一个乘子被更新时,调整另一个乘子来保证线性约束条件成立,保证解不离开可行区域。每步SMO选择两个参数优化,其他参数固定,可以获得解析解。尽管需要更多的迭代才收敛,但每个迭代需要很少的操作,因此算法在整体上的速度有数量级的提高。另外,算法其他的特征是没有矩阵操作,不需要在内存中存储核矩阵。1/30/2021Chap8
SVM
Zhongzhi
Shi65SVM寻优算法SVM寻优算法1/30/2021Chap8
SVM
Zhongzhi
Shi66类别名称测试样本数错误分类数准确度(%)政治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.87SMO算法核缓存算法SMO算法在每次迭代只选择两个样本向量优化目标函数,不需要核矩阵。虽然没有核矩阵操作,但仍需要计算被选向量和训练集中所有样本向量的核函数,计算次数为2n(n为训练集中的样本数)。如果训练集中的样本选取有误,在噪声比较多的情况下,收敛会很慢,迭代次数很多,则核函数的计算量也是非常可观的,SMO算法的优点就完成失去了。同时,考虑到文本分类的文本向量一般维数比较大,核函数的计算将会非常耗时,尤其在高价多项式核和高斯核等核函数的计算中表现更加明显。1/30/2021Chap8
SVM
Zhongzhi
Shi67SVM寻优算法SMO算法核缓存算法在内存中为SMO算法核函数开辟n行m列的核矩阵空间。其中:n为训练集中的样本数;m是为可调节参数,根据实际的内存大小进行调整,每列存放训练集中某个样本向量与训练集中所有样本向量的核函数计算结果列表。在核矩阵列头生成m个节点的双向循环链表队列,每个节点指向核矩阵的列,通过双向循环链表队列实现核矩阵中的核函数列唤入唤出操作。同时,为了实现样本向量的核函数列的快速查找,为每个训练样本向量设计了快速索引列表,通过索引列表判断该训练样本向量的核函数列是否在核矩阵中,并确定在哪1/一30/2列021
。SVM寻优算法Chap8
SVM
Zhongzhi
Shi
68SVM寻优算法 选择一个训练集,通过调整核缓冲参数的大小,记录不同核缓存大小情况下训练时间,结果如下表:1核缓存大小(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:37/2350/20215624
Chap5862S4V*M5Z6h2o4ngzhiS4h0i7261:12
69通过引入核缓存机制,有效的改进了SMO算法,提高了文本分类的训练速度。在核缓存机制中采用简单的hash查找算法和队列FILO算法,有效提高了核矩阵查找和唤入唤出操作的效率。设置核矩阵列参数,通过调节列参数,可以灵活的根据系统运行情况调整训练的时间和空间开销,避免因系统空间开销过大使系统运行效率下降,反而影响训练速度。1/30/2021Chap8
SVM
Zhongzhi
Shi70SVM寻优算法活动向量集选择算法当训练样本数非常大的时候,如果系统能够提供的核缓冲大小很有限,那么能够同时保存在核缓冲中训练样本的核函数数目在训练样本数中所占比例将非常的小。在训练过程中,训练样本在核缓冲中的核函数命中率将显著下降,导致核缓冲中的核函数被频繁的唤入唤出,而每执行一次唤入唤出操作将引起系统重新计算训练样本的核函数,核缓存的作用被很大程度的削弱了。如果出现这样的情况,要么增加系统的存储空间;要么减少训练样本数,才能提高系统的训练速度。为解决训练样本数多,系统内存空间小的矛盾,本文通过活动向量集选择算法,比较好地解决了这个问题。1/30/2021Chap8
SVM
Zhongzhi
Shi71SVM寻优算法活动向量集选择算法算法的主要思想是:定期检查训练样本集,在收敛前预先确定训练样本集中一些边界上的点(alpha=0,或者alpha=C)是否以后不再被启发式选择,或者不再被判定为最有可能违例,如果存在这样的点,将它们从训练样本集中剔除出去,减少参加训练的样本数。该算法基于如下的认识:经过多次迭代后,如果样本的拉格朗日乘子一直为0该点被当前估计的支持向量集所确定的超平面区分得很开,即使以后支持向量集发生变化,该点也不会是最靠近超平面的点,则可以确定该样本不是支持向量;经过多次迭代后,如果样本的拉格朗日乘子一直为非常大的C常数,即使以后支持向量集发生变化,该点也不会远离超平面,则可以确定该样本是上边界处的支持向量1/30/2021Chap8
SVM
Zhongzhi
Shi72SVM寻优算法活动向量集选择算法这样就可以在SMO算法收敛前,提前将边界上的点从训练样本集中剔除,逐渐缩小参加训练的活动样本集,从而减少SMO算法对核缓存空间的要求,提高训练速度。训练开始前,训练活动集样本初始化为全部训练样本。每经过一定次数的迭代(比如迭代1000次),如果算法还没有收敛,应检查活动集中的向量,检查是否有训练样本可以不参加迭代运算。检查完当前活动向量集中所有样本后,产生了新的活动向量集。如果新的活动向量集的样本数减少一成以上(含一成),则可以收缩当前活动向量集,用新的活动向量集替换当前活动向量集。当活动向量集的样本数减少到一定的程度,对核缓存空间的要求不是很大的时候,继续减少训练样本对训练速度的提高就非常有限了,这时就没有必要再1/3减0/20少21
训练样本了。Chap8
SVM
Zhongzhi
ShiSVM寻优算法73固定工作样本集(Osunaetal.):将工作样本集的大小固定在算法速度可以容忍的限度内,迭代过程选择一种合适的换入换出策略,将剩余样本中的一部分与工作样本集中的样本进行等量交换,即使支持向量的个数超过工作样本集的大小,也不改变工作样本集的规模,而只对支持向量中的一部分进行优化。例如: 算法SVM寻优算法1/30/2021Chap8
SVM
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年广东省惠州市惠城区中考数学二模试卷(含答案)
- 财务会计入门实操指南
- 高等土力学:本构模型
- 2025年android自学视频!一起看看这些大厂面试真题查漏补缺吧分享一点面试小经验
- 2023-2024学年山西省长治市部分学校高二下学期期末考试数学试题(解析版)
- 2025届河南省许昌、平顶山、汝州名校高三二模语文试题(解析版)
- 2025届福建省高三模拟练习联合检测语文试题(解析版)
- 2024届湖南省益阳市七校高三下学期第二次模拟考试语文试题(解析版)
- 2024-2025学年浙江省湖州市高二上学期期末考试语文试题(解析版)
- 2024-2025学年山西省晋城市部分学校高二下学期开学检测语文试题(解析版)
- 2025年入党积极分子培训结业测试题及答案
- 人教版(2024)七年级下册生物期末复习重点知识点提纲
- 2025年中考语文二轮复习:标点符号 专题练习题(含答案解析)
- 跌倒坠床防范试题及答案
- 2024-2025学年人教版(2024)初中英语七年级下册(全册)知识点归纳
- XXX社区居委会、业主委员会和物业管理机构三方联席会议制度
- 三伏贴不良反应应急预案
- 简阳市2024-2025学年五年级数学第二学期期末统考模拟试题含答案
- 2025年广东省佛山市中考英语一模试卷
- 防尘网施工方案
- 垃圾发电行业安全培训
评论
0/150
提交评论