为什么无限函数族需要新的计数方法
一个连续参数便可代表无穷多个预测函数,例如 ,其中 。上一节对有限清单的并集界不能直接代入 :所得概率界没有用。不过,数值接近的常数预测通常有接近的损失。我们可以先用有限网格近似整个参数族,只在网格点上支付集中不等式的代价,再估计近似误差。
这是一个具体的容量控制方法,依赖有界参数盒以及对损失的一致 Lipschitz 条件。高维时它可能给出很弱的界;不能仅凭参数数目就断言任意神经网络具有同样的泛化保证。
定义与定理
定义 10.2.1
(有界且一致 Lipschitz 的损失族)
设 与新的观测 同分布且相互独立,。对每个 ,其中 、 为正整数,设损失 可测且属于 ,。假设存在确定的 ,使每个 和任意 都满足
定义总体风险 及经验风险 。
上述条件使两个风险函数均为 -Lipschitz,因而连续;盒子内可数稠密子集上的上确界已等于整个盒子上的上确界,所以以下随机上确界可测。
网格网逐个坐标构造。
引理 10.2.2
(参数盒的网格网)
对 令 。所有坐标都属于 的点组成网格 ,共有 个点,而每个 都有网格点 使 。
证明
(坐标等距分割)
把每个坐标区间等分成 段,取全部端点。相邻端点距离 ,整个网格 恰有 点。任意 都有网格邻点 ,满足 。此网格在抽样之前确定。
有了网格网,集中不等式只需在其 个点上付出代价。
定理 10.2.3
(从参数网格得到一致界)
选取 与 ,令 、,并定义
以至少 的概率,同时对所有参数有
若可测的、允许依赖数据的 满足 ,其中 ,则在同一事件上
由于风险在紧盒子上连续,两个下确界实际上都能取到。证明也可先与任意参数比较,再取下确界。概率指的是样本的随机性,而不是在事件建立之后对参数的随机选择。
证明:先覆盖,再选择
证明
(先对网格用并集界,再作 Lipschitz 转移)
对固定网格点,上一节的有界均值集中界给出
对 个点使用并集界,得到至少 的概率下所有网格误差均不超过 。不同网格点的损失使用同一批样本,无须彼此独立。
在这个事件上,对任意参数用三角不等式和两个 Lipschitz 界:
一个 用于移动总体风险,另一个用于移动经验风险。同一个网格事件覆盖所有参数,包括看过数据之后选出的参数。
对任意比较参数 ,依次使用一致界、近似最小化和一致界:
取下确界即得第二个结论。
证明透视
为什么网格必须先固定,每个 Lr 从何而来
论证有严格的次序。网格 在抽样之前选定,所以 是固定数,对 个固定点使用并集界才合法。此后一切都是确定性的:在同一个网格事件上,由 转移到 不涉及任何概率,因此对每个 同时成立,包括依赖数据的 。
转移付出两次 ,理由各不相同。移动总体风险时,对新的 平均 Lipschitz 界;移动经验风险时,则在样本点上使用它。两者都只因该界对每个 成立而成立;两者都与网格相配,因为 Lipschitz 条件与覆盖使用同一个 距离。半径 于是在最后的界中出现两次:在 中以及在 之内,这正是下面要考察的取舍。
它比较的是盒内最佳风险;如果理想预测函数不在这个族内,族内最佳风险与理想风险之差还要作为单独的近似误差加入。
例题:连续的常数预测
例题 10.2.4
(有界区间上的绝对损失)
设 几乎处处成立,考虑所有常数预测 ,损失 属于 。反三角不等式给出 ,故 、。取 、、,则网格有 点,且
因此任一精确经验最小化解,以至少 的概率,其风险不超过最佳常数风险加约 。截断到该区间的样本中位数是这样的解。这个分布无关的界是充分保证,并非说实际超额风险等于该数。
缩小 会降低近似项 ,却增加 和集中项。固定 时取 ,所得界随 趋于零。然而 ,大维度可能使界很弱。利用函数结构或数据分布的更精细覆盖有可能改进结果,但需要另外证明。
例题 10.2.5
(选择网格半径)
保留绝对损失族,、;由于 ,有 。下表列出 、 及四舍五入后的 。
每往下一行,逼近项缩小十倍,而 只通过 增长。界由 改善到 ,之后反而变差:在 ,多出的网格点在 上付出的代价超过在 上节省的。任何 都给出有效的界;选择只影响它包含多少信息。
例题 10.2.6
(边界情形:十维中达到同样精度)
设 、、、,则每个坐标有 个网格值,。要使 ,定理要求 。当 ,此值为 ,所以 已经足够。当 ,,要求变成 。维数只通过 以对数形式出现,但这个对数随 线性增长,充分样本量增大约 倍。
条件与反例
定理的每个假设都排除一种具体的失败。
反例模式
仅有有界损失不能控制不受限制的函数族
断言:若每个损失都在 内,则经验最小化解的总体风险接近最佳风险。设 在 上均匀分布、,允许所有从 到 的可测预测函数,并使用平方损失。对任意有限样本,取函数在样本输入处为零、其他地方为一;其经验风险为零,而总体风险为一。恒零函数的两种风险均为零。所以经验最小化解可能泛化很差;损失有界本身无法控制不受限制的函数族。此例不满足上面的有限维一致 Lipschitz 参数条件。
常见错误
(只在已观测样本上检查 Lipschitz 界)
Lipschitz 常数必须对所有观测值一致成立,不能仅在已观测样本上成立。证明把总体风险 移到网格时,是对新的观测 平均该界;只在 上验证的界,对 在其他位置的取值没有任何结论,而上面反例中的函数恰恰在那些位置不为零。
常见错误
(看过数据之后才选择函数族)
训练误差小本身并不能保证总体误差小。也不能看过同一批数据之后选择函数族,再假装该族事先固定。如果随机函数族由独立的训练数据产生,且同样的确定性界对每个实现都成立,可以先对训练数据条件化。
常见错误
(把界用于无界的平方损失)
没有额外假设或另一种集中工具,保证不涵盖无界平方损失。只限制参数并不足够:若 无界,即使 ,损失 仍然无界,第二题正说明了这一点。
练习
快速检查
(取 、、,求 和 。再令 、、,写出一致误差界的精确值。)
解答 · 答案
,。所求界为 ,其中 。它有效,但大于损失在 时最大可能的误差一,说明正确的界也可能没有实际区分力。
快速检查
(设 、,平方损失 。求适用的 和 ;解释若 无界,为何只限制 不能给出同一个 。)
解答
,故可取 。并且
所以可取 。若 无界,即使 ,平方损失也可任意大;不能以 使用有界损失集中界。
快速检查
(在一致事件上,若族内最佳风险为 、,算法的经验目标距下确界不超过 ,求总体风险上界。若理想风险为 ,分解所得超额风险界。)
解答 · 答案
总体风险至多 。相对理想风险,超额风险界为 :族的近似误差为 ,一致估计贡献 ,优化贡献 。
快速检查
(若 ,定理对族内风险说明什么?此时是否必须支付全部 个网格点的代价?)
解答 · 答案
的逐点条件意味着所有参数在每个 上给出相同损失,所以所有总体风险和经验风险都相同。一个点就覆盖整个族,直接对一个函数应用集中界便可避免多余的 因子;定理使用较大网格仍然正确,只是偏松。