期望风险最小化、经验风险最小化、结构风险最小化

本文为阅读《关于统计学习理论与支持向量机》论文笔记
水平有限，有错误请指出，谢谢

损失函数

损失函数（loss function）或代价函数（cost function）是将随机事件或其有关随机变量的取值映射为非负实数以表示该随机事件的“风险”或“损失”的函数。损失函数通常作为学习准则与优化问题相联系，即通过最小化损失函数求解和评估模型。

有三类基本的机器学习问题 ,即模式识别、函数逼近和概率密度估计。
对模式识别问题 ,输出 y 是类别标号1,两类情况下 y= { 0, 1}或 { 1, - 1},预测函数称作指示函数 ,损失函数可以定义为：
div
使风险最小就是 Bay es决策中使错误率最小.在函数逼近问题中 , y 是连续变量 (这里假 设为单值函数 ) ,损失函数可定义为:

L ( y , f (x ,w ) ) = (y - f (x , w ) ) ²
即采用最小平方误差准则.而对概率密度估计问题 ,学习的目的是根据训练样本确定 x 的概率密度.记估计的密度函数为 p (x , w ) ，则损失函数可以定义为：
L (p (x ,w ) ) = - logp (x ,w )

期望风险最小化

变量 y与 x 存在一定 的未知依赖关系 ,即遵循某一未知的联合概率 F (x , y ) , (x 和 y 之间的确定性关系可以看 作是其特例 ) ,机器学习问题就是根据 n个独立同分布观测样本

( x 1 , y1 ) , ( x2 , y2 ) ,… , (xn , yn ) ,
在一组函数 {f (x ,w ) }中求一个最优的函数 f (x , w0 )对依赖关系进行估计 ,最小化期望风险
R ( w ) =∫L (y , f ( x , w ) ) dF (x , y )
f (x ,w ) 称作预测函数集，w为函数的广义参数 ，f ( x ,w ) 可以表示任何函数集；L ( y , f ( x ,w ) )为由于用 f ( x , w )对 y进行预测而造成的损失。
期望风险最小化代表的是一种全局风险的最小化，对于全体样本是未可知的，一般情况下，无法解得真实值。

经验风险最小化

由于我们能得到的只有样本的值，期望风险是无法得到的，所以在传统的学习方法中，使用经验风险最小化（ERM）准则，来对期望风险最小化来进行估计。用样本来定义经验风险：

而实际上，即使可以假定当n趋向于无穷大时经验风险式趋近于期望风险式，在很多问题中的样本数目也离无穷大相去甚远。
ERM 准则不成功的一个例子是神经网络的过学习问题。训练 误差小并不总能导致好的预测效果，某些情况下，训练误差过小反而会导致推广能力的下降，即真实风险的增加，这就是过学习问题。
之所以出现过学习现象 ，一是因为样本不充分 ，二是学习机器设计不合理，这两个问题是互相关联的。
有限样本情况下：
1)经验风险最小并不一定意味着期望风险最小。
2)学 习机器的复杂性不但应与所研究的系统有关 ,而且要和有限数目的样本相适应。

结构化风险最小化

引入结构化经验最小化来处理上面经验风险最小化存在的问题。

VC维

为了研究学习过程一致收敛的速度和推广性，统计学习理论定义了一系列有关函数集学习性能的指标 ,其中最重要的是VC维 (Vapnik-Cherv onenkis Dimension)。
模式识别方法中VC维的直观定义是：对一个指示函数集，如果存在h个样本能够被函数集中的函数按所有可能的2h种形式分开，则称函数集能够把h个样本打散；函数集的VC维就是它能打散的最大样本数目h。若对任意数目的样本都有函数能将它们打散，则函数集的VC维是无穷大。
有界实函数的VC维可以通过用一定的阈值将它转化成指示函数来定义。VC维反映了函数集的学习能力，VC维越大则学习机器越复杂 (容量越大) 。目前VC维无法通过计算得出，一些特殊的函数集知道其VC维。比如在n维实数空间中线性分类器和线性实函数的VC维是 n+ 1，f(x ,T)= sin(Tx)的VC维则为无穷大。

推广性的界

统计学习理论系统地研究了对于各种类型的函数集，经验风险和实际风险之间的关系，即推广性的界。关于两类分类问题，结论是：对指示函数集中的所有函数(包括使经验风险最小的函数) ,经验风险Remp(w)和实际风险R(w)之间以至少1- Z的概率满足如下关系。

其中h是函数集的VC维，n是样本数。
这一结论从理论上说明了学习机器的实际风险是由两部分组成的： 一是经验风险 (训练误差) ,另一部分称作置信范围 。
它和学习机器的VC维及训练样本数有关。可以简单地表示为：

R (w ) ≤ Remp (w ) + H(h /n )
它表明，在有限训练样本下，学习机器的VC维越高(复杂性越高)则置信范围越大，导致真实风险与经验风险之间可能的差别越大。这就是为什么会出现过学习现象的原因。
要使机器学习取得较小的实际风险，需要同时使 经验风险最小化和VC维尽量小（置信范围小）。

结构风险最小化

把函数集构造为一个函数子集序列，使各个子集按照VC维的大小 (亦即H的大小)排列；在每个子集中寻找最小经验风险，在子集间折衷考虑经验风险和置信范围，取得实际风险的最小，如图所示。这种思想称作结构风险最小化 ( Structural Risk Minimization)即SRM准则。

实现SRM原则可以有两种思路：
一、在每个子集中求最小经验风险，然后选择使最小经验风险和置信范围之和最小的子集。显然这种方法比较费时，当子集数目很大甚至是无穷时不可行。
二、设计函数集的某种结构使每个子集中都能取得最小的经验风险 (如使训练误差为 0)，然后只需选择选择适当的子集使置信范围最小，则这个子集中使经验风险最小的函数就是最优函数。支持向量机方法实际上就是这种思想的具体实现。