为什么要选取核矩阵的若干列?
核 Gram 矩阵记录观测特征向量两两之间的内积。有 个观测时,矩阵便有 个元素,即使其中大部分几何结构只需要少数方向就能描述。减少计算的一个方法,是挑选 个观测作为地标,只计算各观测与这些地标的相似度,再用它们重建其余内积。
重建不能只把所选的列直接相乘。这些列相当于以地标向量量度的坐标,而地标未必互相正交,甚至未必线性无关。地标本身的 Gram 矩阵告诉我们如何校正这套坐标。地标线性无关时可用逆矩阵;线性相关时则用伪逆。所得的 Nyström 矩阵有一个很有用的解释:先把每个特征向量正交投影到地标张成的空间,再计算 Gram 矩阵。
本节针对一个固定的有限半正定矩阵,完整证明这个解释。它会准确指出哪些数据被保留、哪些方向被舍去。论证不需要随机地标,也不表示任意选法都准确,更不表示拟合所得的预测函数能在新数据上有良好表现。
矩阵、地标与奇异情况下的逆运算
设 对称且半正定,简记为 PSD;即每个 都满足 。选取互异指标 ,其中 ,并设
所以 包含所选的列,而 是相同指标的行、列相交所得的主子矩阵。 必须来自同一个 PSD 矩阵,这个假设很重要。不能把一个无关的 阶半正定矩阵代入 ,便沿用以下结论。
定义 14.1.1
(半正定伪逆与 Nyström 矩阵)
把 的正特征值部分写成正交特征分解 ,其中 、,而 的对角线包含 个严格正的特征值。定义
伪逆在 上的作用为零。当 ,以上乘积按零矩阵理解,而 有零列。若 可逆,则 。
即使选了 个地标指标,特征矩阵 也只有 列。重复的特征方向不会产生新信息。定义直接给出 半正定,而且秩至多为 。但要证明它与 的差仍半正定,以及所选列能精确重现,还需要进一步论证。
对称矩阵的记号 表示 半正定。这是二次型的大小关系,不是逐元素的不等式。以下以 表示欧氏(Euclidean)算子范数,以 表示迹。
用投影理解整个构造
定理 14.1.2
(地标投影与半正定误差)
对上述有限 PSD 矩阵与地标集合,选任一分解 ,其中 ,并设 。谱定理保证这种分解存在;例如可以取 、。定义
则 是投影到 的正交投影,而且
此外 。等式 成立,当且仅当 的所有行向量转置后均属于地标张成空间 ;等价地,。
实际构造投影,而非直接假定
证明由 的特征向量构造地标张成空间的一组标准正交基,使 显然是投影。
证明
(标准正交地标方向给出投影)
首先, 且 。若 是 对应正特征值 的单位特征向量,定义 。直接相乘可得
这些向量构成 的一组标准正交基。为什么没有漏掉值域中的方向?因为 ,所以 。任一向量 的零特征值分量,经 作用后都变成零。因此正特征值对应的向量已生成整个值域,并且
这个矩阵固定地标张成空间中的向量,并把其正交补中的向量映至零。特别地, 且 。代入 ,便证得 。对每个 ,都有
这样便证明了误差半正定;我们没有假定两个无关 PSD 矩阵的差仍为 PSD。每个地标行向量本来就在投影目标空间内,所以它与任一投影后数据行的内积,等于原来的内积。以矩阵表示,,于是 。
最后, 等价于 。一个方向直接成立;另一方向可取 的迹,所得正是所有残差长度平方之和。因此每个数据特征都在地标张成空间内。地标行空间本来就是数据行空间的子空间,故维数相等就等价于两个空间相同。这两个维数分别为 与 。
证明透视
地标矩阵奇异时,为什么方程仍然相容?
证明只在一处用到半正定假设:分解 ;此后全是 各行的几何。第二个假设是 与 来自同一个矩阵,这使 与 共用因子 。
关键一步是 ,从而 。它用了两次。第一,它说明 的正特征向量已经张成全部地标方向,所以 没有遗漏;第二,它说明 奇异不会造成不相容:若 ,则 ,于是 ,即 。伪逆舍去的组合本来就等于零,从不丢掉某个隐藏的非零所选列。一旦知道 是正交投影,半正定残差与所选列的精确重现都只是一行推论。下面的反例是一个不定矩阵,恰好是 的情形。
奇异 Schur 补与不可省略的假设
把观测重新排序,令地标在前。写成
式子 称为广义 Schur 补。 奇异时,即使已知这个补与 都半正定,仍不足以推出任意对称分块矩阵半正定。
定理 14.1.3
(奇异分块矩阵的准确判据)
实对称矩阵 半正定,当且仅当以下三个条件同时成立:、,以及 。
两个方向都基于同一个二次型计算。
证明
(核向量迫出值域条件,配方完成其余部分)
若 半正定,其主分块 也半正定。对 ,固定任一与下方分块维数相同的向量 ,考虑向量 的二次型。它等于 ,而且对每个实数 都必须非负。因此 。取正交补,并利用 对称,就得到 。
在这个值域条件下,。配方给出:对任意 ,
取 ,便见到 半正定必然要求 Schur 补半正定。反过来,若三个条件成立,配方后的两项都非负。判据因而得证,也解释了 Nyström 残差为什么在非对角分块等于零。
反例模式
伪逆不能修补不定的输入矩阵
取 ,并选第一个指标。此时 、、、。广义 Schur 补等于零,但 是不定矩阵:向量 的二次型等于 。值域条件失效,因为 ,而 。公式产生 ,连所选列也不能重现。原来的 PSD 假设正好排除了这种不相容情况。
地标线性相关时的完整计算
例题 14.1.4
(两个地标,只保留一个方向)
使用四个特征行 、、 与 。它们的 Gram 矩阵为
选前两个观测,则
唯一的正特征值为 ,对应特征向量是 ,所以 。把这一列记作 ,并设 ,便有
把 取为由上述特征行组成的 矩阵,则 :地标保留第一个坐标,舍去第二个。所选列完全准确,但第 项由 变成 。因此,精确重现所选列,比精确重现整个矩阵弱得多。
投影第三个特征时,解 可得 。每个这样的系数向量都重建同一个投影特征 ;伪逆选出欧氏长度最小的系数向量。若把第三个观测也加入地标,便能张成两个坐标方向,令近似完全准确。只增加另一个首个特征的倍数,则不会有这个效果。
没有抽样定理时,仍能验证什么?
令 是 第 行的转置,并设 ,则 。特别地,
元素界来自 Cauchy–Schwarz 不等式。范数界则因 的所有特征值非负,故最大特征值不超过它们的和。这些都是所选有限矩阵的确定性误差凭证。计算对角残差,除了所选列外还需要原矩阵的对角元素,但不必取得所有未选观测之间的两两元素。
例题 14.1.5
(只用所选列计算误差凭证)
回到以 为地标的四点例子,并假设只知道 的对角元及所选列 。第 行有 ,而
所以 。第 行有 ,所以 ;地标行给出 。凭证为 及 。完整计算得 ,其中 、:两个界在这里都达到,因为残差的秩为一。若残差的秩更高,迹界会高估算子范数。
常见错误
(把 PSD 序误读为逐元素不等式)
并不表示 。取特征行 、、,只以第一个作地标。投影到第一个坐标后,另外两行都变成 ,于是 ,而 ,。只有对角残差保证非负;非对角残差元素只由 控制其绝对值。
在精确算术下,增加地标不会令这个 PSD 误差变差。若 的每个指标也出现在地标指标组 ,对应的特征空间就互相包含。把较大的空间分解成较小空间及一个正交补,可知 是正交投影。因此 ,而 。新地标若与原有地标线性相关,空间并无改变,近似也不会改善。
例题 14.1.6
(合法的选法也可以漏掉主要方向)
对 ,只选第二个指标,则 ,算子误差为 。改选第一个指标,误差便是 。两个近似都重现所选列,而且都有 PSD 残差。把 换成更大的数,可令误差比任意大。所以对任意选法,仅知道地标数目并不能保证相对精度。
若 来自真正的 PSD 核 ,同一构造亦能在训练集以外定义核。地标输入是 。设 ,并用
这个核半正定,因为它有特征向量 。在原来的再生核空间中,它等于先把核截面 与 投影到地标截面张成空间,再取内积。同一投影证明显示 在每个有限集合上都是 PSD。不过,这并没有给出整个定义域上的一致小误差界。训练输入的残差很小,仍可能与某个未观测输入的巨大残差同时发生。
数值修改会改变结论
定理使用的是精确伪逆。实际数值计算中,极小的正特征值需要用容许误差作取舍。只保留部分正特征模式,相当于投影到更小的子空间;残差仍然 PSD,但可能失去所选列完全相等的性质。数值容许误差不能被说成精确的代数秩判定。
另一种修改是以 代替 ,其中 。在 下,中间的矩阵变成 。它在正地标方向的特征值为 ,其余特征值为零。因此它介于零与单位矩阵之间,而且只有平凡情况 才是正交投影。正则化近似仍介于零与 之间。若 ,所选的 分块会改变,所以失去所选列的精确重现。对只有一项的矩阵 ,取 ,近似是 ,并非 。这种地标正则化,也与稍后拟合标签时使用的岭惩罚不同。
概念视角结构
三个问题,需要三种不同证据
投影定理问的是近似有没有尊重核的几何结构。残差估计或抽样定理问的是近似对某个指定矩阵有多准确。学习定理问的则是拟合函数在新观测上的表现。半正定性回答第一个问题,不能代答另外两个。Nyström 坐标使用选出的数据地标;固定地标后,得到的是确定性的下方近似 。前一篇的随机特征构造,则在指定特征抽样分布下给出 的逐元素无偏估计;它在 PSD 次序下未必小于 。
练习
快速检查
(设 ,其中 ,只选第二个指标作地标。计算 、、 与 。特征坐标的正负号为什么无关紧要?若所选的 坐标为零,情况有何变化?)
解答 · 答案
此时 ,而 。把这个标量块的正特征值对应的单位特征向量取为 ,便有 ,所以 。把每个特征都乘以 ,不会改变两两内积。若所选坐标为零,则 且 ,近似为零;只有整个向量 都为零时才准确。因此一个秩一矩阵可以用一个有信息的地标恢复,但并非每个地标都可以。
快速检查
(设 、、。准确求出哪些实数 使整个分块矩阵半正定,并以前两个指标作地标,计算 时的 Nyström 残差。)
解答 · 答案
伪逆为 。列 属于 的张成空间,即 ,而且 。因此奇异分块判据给出的条件恰为 。当 时,完整残差为 ,迹与算子范数都等于 。若 ,取 及下方系数 ,二次型便等于负数 。
快速检查
(未选观测的对角残差为 与 ,所有已选观测的残差均为零。求这两个未选观测之间残差元素绝对值的上界,以及 的上界。两个上界能否同时达到?)
解答 · 答案
Cauchy–Schwarz 不等式给出 。迹界给出 。两个界都可由秩一的未选块 达到;它是两个长度分别为 与 、互相共线的残差特征的 Gram 矩阵。另加一个与它们正交的地标特征,即可把它实现为某个 PSD Gram 矩阵的残差。
快速检查
(在 上使用线性核 ,唯一的训练输入兼地标是 。计算训练矩阵误差,以及 处的核对角误差,其中 。这对推断整个定义域上的误差界有什么启示?)
解答 · 答案
训练矩阵及其近似都为 ,所以训练误差为零。地标只记录第一个坐标,因此 。在 处,真实对角为 ,近似对角为零,所以对角误差为 ,在这个无界定义域上可以任意大。若没有进一步的假设控制未观测方向,有限训练集上的精确性不会给出整个定义域上的一致误差界。