为什么有些地标较有信息量?
一个地标保留一个特征方向。如果所有地标都在同一方向上,重复选取它们仍无法恢复另一个方向,即使所选对角元素很大也一样。因此,我们需要一个把各列之间的相关性考虑在内的抽样准则。岭杠杆分数便在指定尺度下衡量每一列:比这尺度小得多的方向权重较低,比它大得多的方向则接近计作一个方向。
本节的保证只针对一个固定、有限的正半定(PSD)Gram 矩阵。我们刻意使用初等方法:以二阶矩计算和 Markov 不等式取代更精细的矩阵集中不等式。所得的地标数目可能很保守,但能清楚展示有效维数、正则化尺度,以及漏掉某些方向的非零概率为什么出现在结论中。
分数和独立抽样
定义 16.1.1
(岭杠杆分数与有效维数)
设 为对称 PSD 矩阵,。定义
称为索引 在尺度 下的岭杠杆分数, 称为有效维数。
若 ,则 。因此 、,而 。所以 :它按所选尺度,以分数计算每个特征向量的贡献,一般不是整数。
概念视角分析
把杠杆分数看作正则化重构代价
令 ,每个分数都是一个小型岭问题的最优值:
令梯度为零得 ;由于各矩阵可交换,代入这个最小点便得最优值 。取 的代价是 ,取 的代价是 ,所以 。若某列的特征向量可以由一个范数小的特征向量组合重现(误差以 计价),该列的分数便小;这正是分数“考虑各列之间相关性”的精确含义。
当 时,。独立地、有放回地抽取 ,其中
重复抽中同一索引仍是有效抽样,但不会增加新方向。设 为抽中过的不同索引所组成的集合,,。近似矩阵是 。等价地,令 ,而 为到所有 对应向量 的张成空间的正交投影;先前的地标投影恒等式给出 ,所以 。
如果 ,则 为零向量。第一个因子可逆,故 ;这列没有特征方向,给它零概率不会遗漏任何方向。若 ,不必抽样,直接设 ;以下残差结论自然成立。
例题 16.1.2
(重复的列分享杠杆)
设 、。特征值为 和 ,对应 的单位特征向量是 ,所以
单独一列 的分数是 。把它重复一次,每个分数降至 ,总和 仍小于一:两列只带一个方向,在此尺度下按分数计算。从上述观点看, 是第一个特征向量的最优重构,代价为 。两个概率都是 ;由于 的秩为一,任何一次抽样都给出 。定理在 、 时要求 ,即 :这个充分抽样数目正确,却没有利用这种精确结构。
常见错误
(按对角元素抽样)
对角元素忽略了相关性。对 和 ,按 成比例抽样使用 ;杠杆分数为 、,给出 。抽五次时,对角抽样漏掉第三个方向的概率是 ,杠杆抽样只有 。
有限样本定理
定理 16.1.3
(初等岭杠杆分数保证)
假设 、、 和 。如果
则上述独立杠杆抽样以至少 的概率满足
这是在尺度 下的绝对谱误差界,并非每个方向相对于 的误差界。
证明分两步:先估计白化向量的样本协方差,再把这个估计转化为 Nyström 残差。
证明
(第一步:白化坐标中的样本协方差)
令 。各矩阵均为 的函数,故可交换;因此
对一次抽样 ,定义 。其分母几乎必然为正,且 。若 ,利用独立性和 的零均值,得到
这里 ,而交叉项因独立而消失。由 ,对 Frobenius 范数的平方使用 Markov 不等式,可知 的概率至少为 。
第二步只用到刚得到的事件,不再涉及其他概率。
证明
(第二步:由方向覆盖得到 Nyström 残差)
在该事件上,取任意与全部抽中 正交的 ,设 。此时 与每个抽中的 正交,所以 。因此
移项得 ,其中 。对任意 ,取 。这个 与地标张成空间正交,且
若 ,所需不等式立即成立;否则除以 再取平方。于是对所有 有 ,即 。结合概率界和所假设的抽样数目,定理得证。
证明透视
白化的作用
概率一步只用到抽样独立,以及 时 ,从而 ;具体选择 则使 恰好等于 ,由 Cauchy–Schwarz 不等式,任何其他选择都会使这个和更大。关键一步在第二步。样本协方差只控制抽中的白化向量所张成的空间,残差却关乎未被覆盖的原始特征方向。对未覆盖的方向 ,改用 检验;正因为白化与反白化互相抵消, 与每个抽中的 正交,于是 在 上为零,而算子范数事件便控制了 。假设 使 可逆,这是坐标变换所需的; 则允许移项。最后的 Cauchy–Schwarz 一步把对未覆盖方向的控制转为 。单纯计算地标个数无法提供这些。
两个方向和具体抽样数目
例题 16.1.4
(对角 Gram 矩阵)
设 、。分数为 和 ,故 ,。抽一次时,选第一个索引的残差为 ;选第二个时为 。后者以 的概率出现,说明为何需要概率形式的保证。
取 、,定理给出的充分抽样数目为 ,故 足够。它保证误差不超过 的概率至少为 。这不是说需要 79 个不同地标:这里只有两个。事实上,误差大于 当且仅当 79 次都选中索引 2,概率为 。本例中的定理虽正确,却非常保守。
反例模式
高概率并非必然
同一对角例子说明:不论有限的 有多大,独立抽样仍可能漏掉主要方向,其概率为 。而 亦不会给出某个 的相对界 :一旦漏掉正的对角方向,该方向的残差恰等于 的该方向。
这对岭预测有什么意义?
固定响应向量 ,比较训练点上的拟合向量
两个矩阵均为 PSD,故各正则化逆矩阵的算子范数不超过 。利用预解式恒等式,
所以在定理的同一事件上,。若 并要求误差不超过 ,取 便足够。比较中两处采用同一个 和上述未归一化约定;若损失函数使用 ,须一致地代入 。结果本身没有说明未见输入、带噪标签或总体泛化的表现。
例题 16.1.5
(漏掉一个方向后比较拟合向量)
回到 、,并假设每次都抽中索引 1,于是 、。对 ,
预解式公式与此一致:。这里 ,恰好是 时定理的水平 ,而上界给出 。它松了约 倍,因为它把在漏掉方向上等于 的 换成范数界 ,而且 并非集中在该方向上。
常见错误
(把分数或有效维数当作误差估计)
分数 决定抽取哪个索引; 控制上述充分抽样数目; 衡量实际得到的有限矩阵误差。它们都不是测试风险的估计。此外,计算精确分数需要完整矩阵的信息,因此这个定理本身不构成快速算法。
练习与解答
快速检查
(设 、。求各分数、有效维数及正的抽样概率。)
对角矩阵有 。
解答 · 答案
分数为 ,。所以 、、。零坐标不会被抽中,亦不带特征方向。
快速检查
(对例中的 和相应概率, 次抽样后 Nyström 近似等于 的精确概率是多少?)
只有两个索引都出现过,近似才精确。
解答 · 答案
两个索引必须都出现。两个互斥的失败事件分别是每次都抽中 1 和每次都抽中 2,因此答案为 。当 时结果为零。
快速检查
(设 且 。证明一次杠杆抽样几乎必然给出 。)
先求 的特征分解。
解答 · 答案
有唯一正特征值 ,而 。分数为正的索引恰好是 的索引。任何这样的一列都张成整个秩一特征空间,因此投影恒等式给出零残差。
快速检查
(如果 而 奇异,上述证明在哪里失效?)
证明中哪个矩阵必须可逆?
解答 · 答案
及其逆不再存在于整个空间上。特别是,用来比较未覆盖特征方向和白化方向的变量替换不再按上述形式有效。或可在 的值域上另作证明,但那不是本定理的证明。