统计学习理论导论-7

1XuegongZhangTsinghuaUniversity1支持向量机（SVM）实现的是如下的思想：它通过某种事先选择的非线性映射将输入向量x映射到一个高维特征空间Z，在这个空间中构造最优分类超平面。XuegongZhangTsinghuaUniversity2两个问题：(1)怎样找到一个推广性好的分类超平面？（概念上的问题）特征空间的维数将会很高，将训练数据分开的一个超平面不一定能够很好地推广。(2)怎样在计算上处理在如此高维的空间？（技术上的问题）要在一个200维空间中构造一个4或5阶的多项式，需要构造一个上十亿维的特征空间。如何克服这种“维数灾难”(curseofdimensionality)？XuegongZhangTsinghuaUniversity35.6.2内积的回旋(Convolutionoftheinnerproduct)广义昀优超平面的系数是其中参数,是下列二次优化问题的解：s.t.决策函数：∑==liiiixyw1αiαli,,1L=αmax∑∑==⋅−=ljijijijiliixxyyW1,1)(21)(αααα01=∑=liiiyαliCi,,1,0L=≤≤α−⋅=∑=liiiibxxyxf100)(sign)(α——只涉及对向量的内积运算XuegongZhangTsinghuaUniversity4经过变换z=Φ(x)，在空间Z中的（广义）昀优分类面与上述问题形式完全相同，只是x被替换成z=Φ(x)：∑∑==⋅−=ljijijijiliizzyyW1,1)(21)(αααα−⋅=∑=liiiibzzyxf100)(sign)(α),())(),((),(jijijixxkxxzz→=φφZ空间中的内积可以转化为原X空间中的函数（核函数）因此，变换空间（特征空间）中的昀优分类面实际只需要在原空间中进行求解，并不需要实际实现变换。进一步，变换z=Φ(x)完全可以只是概念性的，只要知道核函数，我们甚至不需要知道对应的变换是什么。XuegongZhangTsinghuaUniversity5构造适当的变换，在变换空间中求最优分类面构造适当的核函数，求由核函数定义的最优分类面找什么样的核函数？——基本要求是它对应于某一个变换空间的内积XuegongZhangTsinghuaUniversity6定理5.3(Mercer)要保证下的对称函数能以正的系数展开成（即描述了在某个特征空间中的一个内积），充分必要条件是，对使得的所有，条件成立。2L),(vuK0ka∑∞==1)()(),(kkkkvuavuKψψ),(vuK∫∞duug)(20≠g∫∫0)()(),(dudvvgugvuK根据Hilbert-Schmidt理论，可以是满足上面的一般条件的任意对称函数[CourantandHilbert,1953]。——Mercer条件2XuegongZhangTsinghuaUniversity7简化条件：XuegongZhangTsinghuaUniversity8于是，构造非线性变换以在新空间中求解（广义）昀优超平面的问题就变为构造适当的核函数的问题。XuegongZhangTsinghuaUniversity9支持向量机决策函数是其中参数是下列二次优化问题的解：s.t.5.6.3构造SV机(ConstructingSVM)利用内积核函数等效地进行非线性变换，在变换空间中构造（广义）昀优超平面，即得到昀优超平面的非线性推广——支持向量机。−=∑bxxKyxfiii支持向量),(sign)(αlii,,1,L=α∑∑−==ljijijijiliixxKyyW,1),(21)(maxααααα01=∑=liiiyαliCi,,1,0L=≤≤αXuegongZhangTsinghuaUniversity10“支持向量网络”——支持向量机的决策可以表示成类似神经网络的形式XuegongZhangTsinghuaUniversity11一种直观解释：模板Æ相似性度量Æ加权投票距离、相关、…核函数XuegongZhangTsinghuaUniversity125.6.4支持向量机的例子（ExamplesofSVM）采用不同的函数作为内积，就得到不同类型的学习机器。目前研究较多的是以下三种类型的学习机器：•多项式学习机器——采用多项式核函数•径向基函数机器——采用高斯核函数•两层神经网络——采用Sigmoid核函数),(ixxK3XuegongZhangTsinghuaUniversity13diixxxxK]1)[(),(+⋅=−+⋅=∑bxxyxfdiii支持向量]1)[(sign),(αα)(dnO多项式学习机器多项式学习机器（（PolynomialSVMPolynomialSVM））要构造阶多项式决策规则，可以用下面的函数作为内积：决策函数形式如下：它是n维输入空间中的d阶多项式的一种因子分解。尽管特征空间的维数很高（n维输入空间中的d阶多项式有个自由参数），求解得到的多项式子集的估计VC维却可以是低的。XuegongZhangTsinghuaUniversity14径向基函数机器径向基函数机器（（RadialBaseFunctionSVMRadialBaseFunctionSVM））传统的径向基函数（RBF）机器采用下面的决策规则集合：其中依赖于两个向量之间的距离。径向基函数（RBF）：对任意固定，函数是一个非负的单调函数；当趋向于无穷大时它趋向于零。这种类型的函数中最常用的是要构造RBF机器的决策规则，需要确定：(1)参数(2)中心的数目N(3)描述各中心的向量(4)参数−−=∑=bxxKaxfNiii1)(sign)(γ)(ixxK−γixx−γ)(ixxK−γixxz−=}exp{)(2iixxxxK−−=−γγγixixiaXuegongZhangTsinghuaUniversity15传统RBF方法中，前三步（确定参数，N和中心向量）是基于启发式知识的，只有第四步（确定上述参数之后求参数）是通过最小化经验风险确定的。γNixi,,1,L=iaSVM:把径向基函数选作SV机中内积的核函数在这种情况下，SV机将构造RBF决策函数集合中的一个函数。−−=22exp)(σii,Kxxxx与传统的RBF方法对比，在SV技术中，所有四种类型的参数都可以通过控制推广能力（控制训练误差和VC维）确定的。理论上如此，实际不尽然XuegongZhangTsinghuaUniversity16两层神经网络（两层神经网络（SVMforTwoSVMforTwo--layerNNlayerNN））通过选择核函数可以定义两层的神经网络，其中是sigmoid函数。注意：sigmoid核,只是对参数的某些值满足Mercer条件。对参数的这些取值，可以构造实现下述规则的SV机：.利用SVM技术，可以自动地找到下列内容：(1)两层机器的构造，即确定隐层单元的数目N（支持向量的数目）；(2)第一层（隐层）神经元（支持向量）的权值向量；(3)第二层的权值向量（值）。])([),(cxxvSxxKii+⋅=)(uS)tanh(cvu+1≤ucv,++⋅=∑=NiiibcxxvSxf1))((sign),(ααiixw=αXuegongZhangTsinghuaUniversity17qii,K]1)[()(+⋅=xxxx−−=22exp)(σii,Kxxxx))(tanh()(cv,Kii+⋅=xxxx核函数选择：多项式核函数：径向基函数（RBF）：Sigmoid函数：－多项式判别函数－RBF网络－包含一个隐层的多层感知器问题：•采用不同的核函数及不同的参数会产生不同的学习机器，如何选择核函数及其参数？XuegongZhangTsinghuaUniversity18理论上，核函数也可以根据理论上，核函数也可以根据SRMSRM原则来选择原则来选择设是一个特征空间，是确定了这个空间中的一个超平面的权值向量。考虑超平面集合的一种结构，其元素包含的函数满足其中R是包含向量的最小超球的半径，是权值的模（我们采用特征空间中对于向量的正规超平面，是训练数据中的元素）。根据定理5.1（现在应用于特征空间），k给出了对函数集的VC维的一种估计。SVM把训练数据没有错误地分开：并且有最小模。换句话说，SVM用估计VC维最小的子集中的函数把训练数据分开。))(,),(()(1xxxNψψL=Ψ),,(1N=kSkwR≤22)(xΨw)(ixzΨ=ixkSliybwxyiii,,2,1},1,1{,1]))([(L=−+=≥−⋅Ψw4XuegongZhangTsinghuaUniversity19回顾在特征空间中，有等式为了控制机器的推广能力（使测试错误概率最小），我们必须构造使得泛函最小的分类超平面。把数据没有错误地分开的超平面以概率有如下的测试错误的界：其中h是超平面集合的VC维。我们用来近似最大间隔超平面的VC维h。要估计这一泛函，只要估计并通过寻找估计即可。∑∑==liilijijijiyyxxKw00020),(αααlwRlwR2020),,(=Φη−1lhlh4ln)12(ln4η−+=E202wRhest=20w)],(2),(),([maxmin)(22axKaaKxxKKRRiiixai−+==2RXuegongZhangTsinghuaUniversity20实际上，核函数目前多人为事先选择实际上，核函数目前多人为事先选择目前报道的SVM应用，多数只报道选定核函数（及其参数）后的结果，选择的过程有的依据经验，有的采用反复试验后确定的办法。有人把核函数选择问题作为一个模型选择（modelselection）的问题专门研究。核函数及其参数的选择是SVM及其他各种核方法的关键之一，是一个重要的未成熟的研究方向。XuegongZhangTsinghuaUniversity21思考题（选作，不算作业）1.综述传统RBF网络中四类参数的确定方法。2.综述传统多层感知器神经网络确定其构造的方法思路。XuegongZhangTsinghuaUniversity22期末大作业建议题目1.平时选作的作业2.自己想出的适当的题目3.针对某一种学习机器（比如较常见的某种神经网络、模式识别方法）研究VC维的理论/实验估计问题。（要求有自己的想法）4.综述（统计学中的）模型选择问题，包括问题的提法、主要理论和方法、应用举例等，并用这些思想和方法探讨解决统计学习理论中的某些未解决问题的途径。5.调研、综述关于核函数及其参数选择的主要工作，就此问题提出自己的思路。XuegongZhangTsinghuaUniversity235.7SVM实验举例图中用黑点和白圈代表两类向量。决策边界是用的多项式型内积构造的。图中的例子不能被没有错误地分开；用叉号标出错分的样本，用套在样本点上的圆圈标出样本中的支持向量。用RBF核函数实现的分类的例子XuegongZhangTsinghuaUniversity24分类器粗错误率％人工表现2.5决策树C4.516.2最好的两层神经网络5.9五层神经网络（LeNet1）5.1在美国邮政服务数据库上解决数字识别问题时的人工表现和各种学习机器的表现5XuegongZhangTsinghuaUniversity25采用三种类型的SV机来构造决策规则：(1)多项式机器，采用回旋函数：(2)径向基函数机器，采用回旋函数：(3)两层神经网络机器，采用回旋函数：处理多类问题：处理多类问题：所有机器都构造十个分类器，每一个把十个数字中的一类与其它类分开。选择分类器输出值昀大的类作为十类的分类。7,,1,256)(),(L=⋅=dxxxxKdii−−=22256)(exp),(σiixxxxK−⋅=cxxbxxKii256)(tanh),(XuegongZhangTsinghu