首页 > 代码库 > 结构化风险最小、VC维到SVM的理解

结构化风险最小、VC维到SVM的理解

支持向量机方法是建立在统计学习理论的VC 维理论和结构风险最小原理基础上。

置信风险: 分类器对 未知样本进行分类,得到的误差。
经验风险: 训练好的分类器,对训练样本重新分类得到的误差。即样本误差
结构风险:置信风险 + 经验风险
结构风险最小化就是为了防止过拟合而提出来的策略,贝叶斯估计中最大后验概率估计就是结构风险最小化的一个例子。当模型的条件概率分布、损失函数是对数损失函数、模型复杂度由模型先验概率表示时,结构风险最小化等价于最大后验概率估计。监督学习问题变成经验风险或结构风险函数的最优化问题,这时经验风险或结构风险函数是最优化的目标函数。

SVM在小样本训练集上能够得到比其它算法好很多的结果。支持向量机之所以成为目前最常用,效果最好的分类器之一,在于其优秀的泛化能力,这是是因为其本身的优化目标是结构化风险最小,而不是经验风险最小,因此,通过margin的概念,得到对数据分布的结构化描述,因此减低了对数据规模和数据分布的要求。SVM也并不是在任何场景都比其他算法好,对于每种应用,最好尝试多种算法,然后评估结果。如SVM在邮件分类上,还不如逻辑回归、KNN、bayes的效果好。

VC维:将N个点进行分类,如分成两类,那么可以有2^N种分法,即可以理解成有2^N个学习问题。若存在一个假设H,能准确无误地将2^N种问题进行分类。那么这些点的数量N,就是H的VC维。 这个定义真生硬,只能先记住。一个实例就平面上3个点的线性划分的VC维是3. 而平面上 VC维不是4,是因为不存在4个样本点,能被划分成2^4 = 16种划分法,因为对角的两对点不能被线性划分为两类。更一般地,在r 维空间中,线性决策面的VC维为r+1。
置信风险的影响因素有: 训练样本数目和分类函数的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嘛),使分类器获得最好的推广性能。

对于线性不可分的状况,可以允许错分。即对于离群点降低分类间隔。将距离原来的分类面越远,离群就越严重,这个距离,可以用一个值--松弛变量来表示,只有离群点才有松弛变量。当然,要对这个值加以限制,即在最小化函数里,加入一个惩罚项,里面还有一个可以人为设定的惩罚项C。当C无限的大,那么就退化为硬间隔问题,不允许有离群点,问题可能无解。若C=0,无视离群点。有时C值需要多次尝试,获取一个较好的值。 




结构化风险最小、VC维到SVM的理解