统计学习理论与支持向量机.pptVIP

统计学习理论与支持向量机机器学习概述Simon对学习的论述：“如果一个系统能够通过执行某个过程改进它的性能，这就是学习。”1983年simon进一步指出：“学习就是系统的适应性，这意味着这些改进使得系统能够更有效的完成同样的工作或者类似的工作。”机器学习就是通过对已知事实的分析总结规律，预测无法直接预测的事实。目的：设计某种方法，通过对已知数据的学习，找到数据内在的相互依赖关系，从而对未知数据进行预测或对其性质进行判断。泛化能力：推广能力，对未知数据进行预测和判断的能力。机器学习问题的一般表示Assumption:(iid)Hypothesisspace:Lossfunction:Objectivefunction经验风险最小化根据概率论中大数定律的思想，用算术平均代替设计学习算法时，用对w求经验风险的最小值代替求期望风险的最小值，实现所谓的经验风险最小化原则。大数定律说明当样本数趋于无穷多时，概率意义下趋于，并不保证在同一点上取最小值。当前提不成立时，能否找到更合理的原则？统计学习理论的简介：统计学习理论研究小样本情况下机器学习理论。始于60年代。1962年，rosenblatt提出了第一个机器学习的模型—感知机，标志人们对学习问题进行研究的真正开始。Vapnic在1974年提出的结构风险最小化原则对统计机器学习具有划时代的意义。统计学习理论用VC维来描述学习机器的性能，并从控制学习机器的性能的角度出发，结合经验风险和训练样本，导出学习机器的泛化上界。学习机器的VC维VC维的直观定义：对一个指示函数集，如果存在h个样本能够被函数集中的函数按所有可能的2种形式分开，函数集的VC维是h目前没有通用的关于任意函数集VC维的计算理论，只有一些特殊函数知道其VC维。n维实数空间中线性分类器和线性实函数的VC维是n+1，而的VC维则为无穷大。推广性的界统计学习理论从VC维的概念出发，推导出经验风险和实际风险之间关系的重要结论，称作推广性的界。Vapnik证明，下列边界以成立：h是函数集的VC维，n是样本数，是置信范围。为最小化期望风险，应同时最小化经验风险和假设空间的VC维。结构风险最小化原理把函数集分解为一个函数子集序列，使各个子集按照VC维的大小排列，在每个子集中寻找最小经验风险，在子集间折衷考虑经验风险和置信范围，取得实际风险最小。实现结构风险最小化的两种思路：一是在每个子集中求最小经验风险，然后选择使最小经验风险和置信范围之和最小的子集。显然这种方法比较费时，当子集数目很大甚至是无穷时不可行。二是设计函数集的某种结构使每个子集中都能够取得最小的经验风险（如使训练误差为0），然后选择适当的子集使置信范围最小，则这个子集使经验风险最小的函数便是最优函数。支持向量机简介支持向量机(SVM)是由Vapnik领导的AT＆TBell实验室研究小组在1963年提出。1995年Cortes和Vapnic首先提出比较完善的SVM方法。支持向量机是建立在统计学习理论的VC维理论和结构风险最小化原理基础上的，根据有限样本信息在模型复杂性和学习能力之间寻求最佳折衷，以期获得最好的泛化能力。支持向量机优点针对有限样本情况。算法最终将转化为一个二次型寻优问题，从理论上讲，得到的将是全局最优点，解决了在神经网络中无法避免的局部极值问题。算法将实际问题通过特征映射，映射到高维特征空间，在高维空间中构造线性判别函数来实现原空间中的非线性判别函数。解决了维数灾难问题，其算法复杂度与样本维数无关。边缘的概念及其泛化界统计学习理论中，泛化界是通过VC维得到的，通过控制函数集的VC维，以便获得最好的学习机器泛化性能。引入一种基于边缘的泛化界思想，将边缘的概念引入到学习算法中去。泛化不等式直观上看，样本点离分界面越远，边缘越大，泛化性能越好。线性可分情形最大边缘算法假设给定训练样本集：其中服从独立同分布，为样本类别标签。分类面方程：归一化：分类边缘：使分类边缘最大等价于使求解：利用Lagrange乘子法转化为对偶优化问题构造Lagrange函数为对应的Lagrange乘子对w,b分别求偏导将