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

统计学习理论与支持向量机机器学习概述Simon对学习的论述：“如果一个系统能够通过执行某个过程改进它的性能，这就是学习。”1983年simon进一步指出：“学习就是系统的适应性，这意味着这些改进使得系统能够更有效的完成同样的工作或者类似的工作。”机器学习就是通过对已知事实的分析总结规律，预测无法直接预测的事实。目的：设计某种方法，通过对已知数据的学习，找到数据内在的相互依赖关系，从而对未知数据进行预测或对其性质进行判断。泛化能力：推广能力，对未知数据进行预测和判断的能力。机器学习问题的一般表示

系统S是研究对象，符合某一未知的联合概率分布F(x,y)。在给定的输入x下得到系统的输出y。在训练过程中，输入与输出组成独立同分布的训练样本(x,y)求出学习机器，在测试过程中，训练后的学习机器对于输入x给出预测y’Assumption:(iid)Hypothesisspace:Lossfunction:Objectivefunction

从一组独立同分布的观测样本出发，通过最小化期望风险R(w)，确定学习机器的广义参数w的过程。经验风险最小化根据概率论中大数定律的思想，用算术平均代替设计学习算法时，用对w求经验风险的最小值代替求期望风险的最小值，实现所谓的经验风险最小化原则。大数定律说明当样本数趋于无穷多时，概率意义下趋于，并不保证在同一点上取最小值。当前提不成立时，能否找到更合理的原则？统计学习理论的简介：统计学习理论研究小样本情况下机器学习理论。始于60年代。1962年，rosenblatt提出了第一个机器学习的模型—感知机，标志人们对学习问题进行研究的真正开始。Vapnic在1974年提出的结构风险最小化原则对统计机器学习具有划时代的意义。统计学习理论用VC维来描述学习机器的性能，并从控制学习机器的性能的角度出发，结合经验风险和训练样本，导出学习机器的泛化上界。学习机器的VC维VC维的直观定义：对一个指示函数集，如果存在h个样本能够被函数集中的函数按所有可能的2种形式分开，函数集的VC维是h目前没有通用的关于任意函数集VC维的计算理论，只有一些特殊函数知道其VC维。n维实数空间中线性分类器和线性实函数的VC维是n+1，而的VC维则为无穷大。h推广性的界统计学习理论从VC维的概念出发，推导出经验风险和实际风险之间关系的重要结论，称作推广性的界。Vapnik证明，下列边界以成立：

h是函数集的VC维，n是样本数，是置信范围。为最小化期望风险，应同时最小化经验风险和假设空间的VC维。结构风险最小化原理把函数集分解为一个函数子集序列，使各个子集按照VC维的大小排列，在每个子集中寻找最小经验风险，在子集间折衷考虑经验风险和置信范围，取得实际风险最小。实现结构风险最小化的两种思路：一是在每个子集中求最小经验风险，然后选择使最小经验风险和置信范围之和最小的子集。显然这种方法比较费时，当子集数目很大甚至是无穷时不可行。二是设计函数集的某种结构使每个子集中都能够取得最小的经验风险（如使训练误差为0），然后选择适当的子集使置信范围最小，则这个子集使经验风险最小的函数便是最优函数。支持向量机简介支持向量机(SVM)是由Vapnik领导的AT＆TBell实验室研究小组在1963年提出。1995年Cortes和Vapnic首先提出比较完善的SVM方法。支持向量机是建立在统计学习理论的VC维理论和结构风险最小化原理基础上的，根据有限样本信息在模型复杂性和学习能力之间寻求最佳折衷，以期获得最好的泛化能力。支持向量机优点针对有限样本情况。算法最终将转化为一个二次型寻优问题，从理论上讲，得到的将是全局最优点，解决了在神经网络中无法避免的局部极值问题。算法将实际问题通过特征映射，映射到高维特征空间，在高维空间中构造线性判别函数来实现原空间中的非线性判别函数。解决了维数灾难问题，其算法复杂度与样本维数无关。边缘的概念及其泛化界统计学习理论中，泛化界是通过VC维得到的，通过控制函数集的VC维，以便获得最好的学习机器泛化性能。引入一种基于边缘的泛化界思想，将边缘的概念引入到学习算法中去。难以计算泛化不等式泛化不等式告诉我们可以通过控制边缘来控制泛化界，从而可以将优化目标定为求取最大边缘分类器，也即所谓的最大边缘算法。直观上看，样本点离分界面越远，边缘越大，泛化性能越好。线性可分情形最大边缘算法假设给定训练样本集：其中服从独立同分布，为样本类别标签。

支持向量机本质上是处理二分类问题的。支持向量机的目的是构造最优超平面，将两类正确分开（错误率为0），且分类边缘最大。分类面方程：归一化：分类边缘：使分类边缘最大等价于使求解：利用Lagrange乘子法转化为对偶优化问题构造Lagrange函数为对应的Lagrange乘子对w,b分别求偏导将和代入Lagrange化简为对偶式：由上式求得最优解其中为一类的任意支持向量，为另一类的任意支持向量。支持向量是在中满足等号的那些向量，也就是落在两侧边界超平面上的向量。支持向量在w的展开式中对应的系数a非零，权向量w是支持向量集合的线性组合，各个支持向量对这个线性组合的贡献就是它们Lagrange系数与y的乘积。分类超平面函数：支持向量方法的优点通过化简为对偶优化形式，变成一个凸二次优化问题，其局部解一定是全局最优解，这是神经网络研究多年没有实现的目标。仅与样本点内积运算有关，不涉及样本点本身计算，为核技巧处理非线性问题奠定了基础。支持向量只占全体样本中很少一部分。线性不可分问题的软边缘算法由于样本中小概率事件和噪声的存在，极个别的样本点就会严重影响分类器泛化性能，即导致对训练样本线性不可分。C.coters和V.Vapnic通过引入松弛变量提出软边缘算法。第一项控制的是泛化能力，第二项是惩罚项，控制分类错误。可看作是训练样本关于（广义）分类超平面的偏差，为线性可分情况。C为预先确定好的正实数，实现算法复杂度与错分样本间的折中。当=1时，称为l1范数C-SVM；当=2时，称为l2范数C-SVM。采用Lagrange乘子法求解，约束条件为线性可分与不可分超平面对比非线性问题与核技巧非线性问题可以通过适当的特征映射变换为另一个空间的线性可分问题，变换空间的维数一般会增加。增加空间的维数会陷入“维数灾难”。××××××××××××××××××x1、x2××××××××z3z1z2核技巧的基本思想我们注意到了在讨论最大边缘和软边缘算法时，其最终的分类判别函数式中只包含待分类样本与训练样本中的内积运算，不涉及样本本身的运算。于是要解决一个特征空间中的最优线性分类问题，只需要知道在原空间中的内积运算，而不需要具体的映射函数，因此可以避免“维数灾难”问题这就是核技巧的基本思想。常用核函数类型：多项式类型:径向基