;而损失函数(loss function),比如此前我们对于二分类问题使用的0-1误差,是从

(定义3.1:经验拉德马赫尔复杂度):G是函数族,其成员函数是从\mathcal{Z}到[a,b]的映射;S=(z_1,\cdots,z_m)是来自\mathcal{Z}空间的容量为m的样本集合。G在S上的经验拉德马赫尔复杂度定义为:

(定义3.2:平均拉德马赫尔复杂度):\mathcal{D}是\mathcal{Z}空间的分布(样本集就是按此分布i.i.d.得到的);对任何整数m \ge 1,G的平均拉德马赫尔复杂度是经验拉德马赫尔复杂度关于随机样本集S的期望:

平均拉德马赫尔复杂度移除了对特定样本集的依赖,更加平均地度量了一个函数族的复杂程度(但仍于分布有关)。

令G为一个函数族,其成员函数是从\mathcal{Z}到[0,1]的映射。对于任何\delta 0,G中的每一个成员g,都有至少1-\delta的概率使得下式成立(S是容量为m的i.i.d.样本集):

上述泛化边界为二元分类问题的可学习性提供了保证。注意,第二个边界是数据依赖的(data-dependent):经验拉德马赫尔复杂度是特定样本集合的函数,我们需要将其计算出来。我们可以把经验拉德马赫尔复杂度的计算公式进行稍微变形:

对于固定的\sigma,期望括号里的求解下确界,其实就是在做经验误差最小化(empirical risk minimization)。我们知道,这对于一些\mathcal{H}是比较困难的。

下面,我们将看到,经验拉德马赫尔复杂度将被所谓的“增长函数(growth function)”限制住。

例如,对于二分类问题,假设我们的假说集合是所有直线,+1},{-1,-1},{+1,-1},{-1,+1}

基于增长函数的泛化边界要比拉德马赫尔边界好算一点,但是我们在此过程中用了“放大”的不等关系,使得边界不再依赖于数据和分布(利,普适性更强),但也使得边界变得更“松”(弊)。

此外,当m变大时,计算增长函数的值也是一件不容易的事情。自然而然地,我们会想:能不能再牺牲一点边界的“tightness”,扩展到一个更加好算的边界?——引出VC维。

来衡量一个假说集合的复杂度。这样做的缺点是,对于具有无限个假说的假说集合,我们得到了两个不符合直觉的结论:①它们的复杂度都是无穷大——但沿轴矩形的学习问题告诉我们,具有无限个假说的假说集合,也是可学习的;②它们的复杂度都相等——但我们一定承认,线性假说集合的复杂度,肯定没有100次多项式假说集合的复杂度高。因此,我们自然而然地需要新的方法来度量一个假说集合的复杂度,而不是简单地用假说集合的大小。

之后,我们希望移除边界对数据和分布的依赖,因此提出用增长函数来描述假说集合的复杂度。通过Massarts引理,我们在拉德马赫尔泛化边界的基础上,放松边界,得到基于增长函数的泛化边界。

最后,我们希望简化复杂度的计算,因为增长函数不是那么容易算出来的。于是,我们提出了VC维的概念。VC维也是描述假说集合复杂度的方法。通过Sauers引理,我们在增长函数泛化边界的基础上,再一次放松边界,得到了易于计算的VC泛化边界。

综上,无论使用哪一种泛化边界,给我们的启示是:尽可能选择简单的假说集合。否则,假说集合的复杂度上去后,泛化误差的上界变大,学习的效果便不能得到保证——也就是容易发生过拟合。这时就必须要用大量的数据来对冲掉这种负面影响,否则只能接受过拟合的结果。

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注