经验风险最小化与结构风险最小化浅析_经验风险最小化公式推导过程

最近在学习支持向量机，对经验风险最小化与结构风险最小化不是很了解，仔细研究后发现原来真的很简单。首先要了解一下几个概念。

置信风险： 分类器对 未知样本进行分类，得到的误差。

经验风险： 训练好的分类器，对训练样本重新分类得到的误差。即样本误差

结构风险：置信风险 + 经验风险

泛化误差界的公式为：

R(w)≤Remp(w)+ϕ(h/n)R(w)≤Remp(w)+ϕ(h/n) 
公式中R(w)就是真实风险，Remp(w)就是经验风险，Ф(n/h)就是置信风险。统计学习的目标从经验风险最小化变为了寻求经验风险与置信风险的和最小，即结构风险最小。

VC置信范围(VC confidence)：学习机器的VC维及训练样本数有关。 VC维反映了函数集的学习能力，VC维越大则学习机器越复杂(容量越大)

VC维：将N个点进行分类，如分成两类，那么可以有2^N种分法，即可以理解成有2^N个学习问题。若存在一个假设H，能准确无误地将2^N种问题进行分类。那么这些点的数量N，就是H的VC维。

结构风险最小化(SRM)的基本思想

      所谓的结构风险最小化就是在保证分类精度（经验风险）的同时，降低学习机器的 VC 维，可以使学习机器在整个样本集上的期望风险得到控制。

        传统机器学习方法中普遍采用的经验风险最小化原则在样本数目有限时是不合理的,因此，需要同时最小化经验风险和置信范围。

机器学习过程不但要使经验风险最小，还要使VC维尽量小以缩小置信范围，才能取得较小的实际风险，即对未来样本有较好的推广性。

统计学习理论提出了一种新的策略,即把函数集构造为一个函数子集序列,使各个子集按照VC维的大小排列;在每个子集中寻找最小经验风险,在子集间折衷考虑经验风险和置信范围,取得实际风险的最小。这种思想称作结构风险最小化(Structural Risk Minimization)，即SRM准则。

置信风险的影响因素

置信风险的影响因素与两个量有关，一是样本数量，显然给定的样本数量越大，我们的学习结果越有可能正确，此时置信风险越小；二是分类函数的VC维，显然VC维越大，推广能力越差，置信风险会变大。。训练样本数目，即样本越多，置信风险就可以比较小；VC维越大，问题的解的种类就越多，推广能力就越差，置信风险也就越大。因此，增加样本数，降低VC维，才能降低置信风险。而一般的分类函数，需要提高VC维，即样本的特征数据量，来降低经验风险，如多项式分类函数。如此就会导致置信风险变高，结构风险也相应变高。过度学习即overfit，就是置信风险变高的缘故。
        结构风险最小化SRM(structured risk minimize)就是同时考虑经验风险与结构风险。在小样本情况下，取得比较好的分类效果。保证分类精度（经验风险）的同时，降低学习机器的 VC 维，可以使学习机器在整个样本集上的期望风险得到控制，这应该就是SRM的原则。
当训练样本给定时，分类间隔越大，则对应的分类超平面集合的 VC 维就越小。（分类间隔的要求，对VC维的影响）
根据结构风险最小化原则，前者是保证经验风险（经验风险和期望风险依赖于学习机器函数族的选择）最小，而后者使分类间隔最大，导致 VC 维最小，实际上就是使推广性的界中的置信范围最小，从而达到使真实风险最小。
        训练样本在线性可分的情况下，全部样本能被正确地分类（咦这个不就是传说中的yi*(w*xi+b)）>=1的条件吗），即经验风险Remp 为 0 的前提下，通过对分类间隔最大化（咦，这个就是Φ（w）＝(1/2)*w*w嘛），使分类器获得最好的推广性能。在有限训练样本下，学习机器的VC维越高则置信范围越大,真实风险与经验风险之间可能的差别越大.这就是为什么会出现过学习现象的原因。

      在结构风险最小化原则下，一个分类器的设计过程包含以下两方面的任务：

（1）选择一个适当的函数子集，使它对问题来说具有最优的分类能力；

（2）从这个函数子集中选择一个判别函数，使得经验风险最小；

支持向量机是一个比较好的实现了有序风险最小化思想的方法。