统计学习理论与svm支持向量机(编辑修改稿)

统计学习理论与svm支持向量机(编辑修改稿)内容摘要：

VC维 ：对于一个指示函数（即只有 0和 1两种取值的函数）集，如果存在 h个样本能够被函数集里的函数按照所有可能的 2h种形式分开，则称函数集能够把 h个样本打散，函数集的 VC维就是能够打散的最大样本数目。  如果对任意的样本数，总有函数能打散它们，则函数集的 VC维就是无穷大。 VC维（续）  一般而言 ,VC维越大 , 学习能力就越强 ,但学习机器也越复杂。  目前还没有通用的关于计算任意函数集的VC维的理论 ,只有对一些特殊函数集的 VC维可以准确知道。  N维实数空间中线性分类器和线性实函数的VC维是 n+1。  Sin(ax)的 VC维为无穷大。  …… VC维（续） Open problem: 对于给定的学习函数集 ,如何用理论或实验的方法计算其 VC维是当前统计学习理论研究中有待解决的一个难点问题。 三个里程碑定理 ()( ) ( V C ) l im 0()l im 0()l im 0xannxxHnnHnnGnn收 敛 的 充 分 必 要 条 件 熵快 收 敛 速 度 的 充 分 条 件 与 概 率 测 度 无 关 的 快 收 敛 充 要 条 件推广性的界  SLT系统地研究了经验风险和实际风险之间的关系 ,也即推广性的界。  根据 SLT中关于函数集推广性界的理论 ,对于指示函数集中所有的函数 ,经验风险 和实际风险 之间至少以概率 满足如下关系 : 其中， h是函数集的 VC维 ,n是样本数。 ()empRw()Rw 1 ( l n ( 2 / ) 1 ) l n ( / 4 )( ) ( )e m ph n hRRn 推广性的界（续 1）  学习机器的实际风险由两部分组成 :  训练样本的经验风险  置信范围 (同置信水平 有关 ,而且同学习机器的 VC维和训练样本数有关。  在训练样本有限的情况下 ,学习机器的 VC维越高 ,则置信范围就越大 ,导致实际风险与经验风险之间可能的差就越大。 ( l n ( 2 / ) 1 ) l n ( / 4 )( ) ( )e m ph n hRRn ( ) ( ) ( )e m p nRR h  1 推广性的界（续 2）  在设计分类器时 , 不但要使经验风险最小化 ,还要使 VC维尽量小 ,从而缩小置信范围 ,使期望风险最小。  寻找反映学习机器的能力的更好参数，从而得到更好的界是 SLT今后的重要研究方向之一。 结构风险最小化  传统机器学习方法中普遍采用的经验风险最小化原则在样本数目有限时是不合理的 ,因此，需要同时最小化经验风险和置信范围。  统计学习理论提出了一种新的策略 ,即把函数集构造为一个函数子集序列 ,使各个子集按照 VC维的大小排列。 在每个子集中寻找最小经验风险 ,在子集间折衷考虑经验风险和置信范围 ,取得实际风险的最小。 这种思想称作 结构风险最小化 (Structural Risk Minimization)， 即 SRM准则。 结构风险最小化（续 1） 结构风险最小化（续 2）  实现 SRM原则的两种思路 在每个子集中求最小经验风险 ,然后选择使最小经验风险和置信范围之和最小的子集。 设计函数集的某种结构使每个子集中都能取得最小的经验风险 ,然后只需选择适当的子集使置信范围最小 ,则这个子集中使经验风险最小的函数就是最优函数。 支持向量机方法实际上就是这种思路的实现。 支持向量机概述 支持向量机概述 支持向量机理论 支持向量机 核函数 支持向量机实现 支持向量机概述  1963年， Vapnik在解决模式识别问题时提出了支持向量方法 ,这种方法从训练集中选择一组特征子集 ,使得对特征子集的划分等价于对整个数据集的划分 ,这组特征子集就被称为支持向量 (SV)。  1971年， Kimeldorf提出使用线性不等约束重新构造 SV的核空间 ,解决了一部分线性不可分问题。  1990年， Grace,Boser和 Vapnik等人开始对 SVM进行研究。  1995年， Vapnik正式提出统计学习理论。 支持向量机理论  SVM从线性可分情况下的最优分类面发展而来。  最优分类面就是要求分类线不但能将两类正确分开 (训练错误率为 0),且使分类间隔最大。  SVM考虑寻找一个满足分类要求的超平面 ,并且使训练集中的点距离分类面尽可能的远 ,也就是寻找一个分类面使它两侧的空白区域 (margin)最大。  过两类样本中离分类面最近的点且平行于最优分类面的超平面上 H1,H2的训练样本就叫做支持向量。 支持向量机理论（续 1） 广义最优分类面 广义最优分类面（续 1）  假定训练数据。