动机
低秩近似定理描述最优解,却未单凭这个描述告诉我们如何准备观测、计算表示,或处理一个新观测。在特征值计算开始之前,已有三项选择:哪些观测可以决定中心、哪些坐标决定重建损失,以及保留多少个方向。这些都是建模决定。即使特征值计算十分准确,也不能修补不合目的的损失,或从评估数据泄漏进来的信息。
良好重建与稳定方向亦是两回事。当最大的两个方差非常接近时,许多方向的重建表现几乎一样;数据稍有改动,所报告的载荷向量便可能大幅转动,而目标值只改变很少。反过来,迭代计算可以找到精确的特征向量,却找到并非最大的那一个。要负责任地解读输出,我们需要说明最优化问题、有限的收敛论证,以及谱间隙究竟控制什么。
本节处理实有限矩阵。以下结果只涉及观测到的矩阵及指定的扰动。若要把它们变成总体保证,还须另行提出抽样模型及协方差估计误差界;这里没有假设这两项条件已经成立。
定义
定义 21.1.1
(以训练数据为中心的矩阵与重建损失)
设 为训练观测,且 。定义
以 作除数,令 的特征值等于分数的均方值;改用 只会缩放特征值,不改变特征向量。若 各列正交归一,令 。分数矩阵为 ,重建的中心化各行为 ,每个观测的训练重建损失为 。
把 加回每一行,便得到原坐标下的重建观测。对新的列向量观测 ,锁定的训练表示给出分数 及重建 。若改用评估集的均值,便已改变拟合程序。可以利用验证数据选择 或坐标缩放,但整个选择过程必须留在模型选择之内,最终测试观测则必须留在这个过程之外。
定义 21.1.2
(奇异值与两种不同的误差)
把奇异值分解写成 ,其中 ,。把奇异值序列补零至 ,并在需要时把奇异向量补成正交归一基底。对 ,截断矩阵为 。Frobenius 范数是全部矩阵元素平方和的平方根,所以 。谱范数则为
所以,谱近似控制单位输入组合中最大的误差;Frobenius 近似控制总平方误差。两者是不同目标,即使截断奇异值分解同时解出两个问题。
当 ,前列右奇异向量就是 的前列特征向量,特征值为 。当 ,可用零空间内的方向补足基底。两种情况下,保留前列的 维特征子空间都给出 ,但所选奇异值分解的首右奇异向量须张成该选定空间。在重复奇异值处,任意固定的分解未必符合这个配合条件。下方证明部分再次完整证明的 Frobenius 近似结果,因此给出训练损失 。中心化亦保证 ;小样本可以迫使某些特征值为零,却不表示总体在那些方向完全没有变异。
定理与命题
定理 21.1.3
(谱范数下精确的最佳秩界)
对任何实 矩阵 及整数 ,
截断奇异值分解达到谱误差下界。截断位置若有相等的奇异值,可以选择不同的前列子空间。本定理不声称谱范数最小化解唯一;即使有间隙,亦不作这个声称。
定理 21.1.4
(有限的首特征方向扰动界)
设 为实对称 矩阵,,特征值为 ,单位首特征向量为 ,间隙为 。设对称矩阵 满足 。它的首特征向量 除正负号外唯一。以 定义不分正负方向的夹角 ,则
若确实掌握所列的误差界与间隙,定理特别适用于样本协方差矩阵。但定理本身不会只凭数据便提供估计误差界。
定理 21.1.5
(幂次迭代需要初始的首方向分量)
设正半定 满足 。把单位初始向量展开为 ,其中 构成正交归一特征基底,并假设 。定义 。若 为它与 不分正负方向的夹角,则对 ,
在精确算术中,每次乘法之后归一化会产生相同方向。若 ,此命题不保证得到首特征方向。重复的最大特征值不符合严格间隙假设;只把比值代成一,不能为指定的载荷给出严格压缩界。我们把界写于 ,以避免在 时另订零的零次方惯例。
证明与思路
证明
(低秩映射必定漏掉一个前列组合)
当 ,用正交归一的零空间基底把右奇异向量补至 ;由于 ,这是可行的。令 为首 个右奇异向量的张成空间,维数为 。秩不超过 的 不可能在 上单射,所以存在单位 满足 。利用左奇异向量的正交性,
因此每个容许的 都有至少 的谱误差。余项 的奇异值是 ,故其谱范数恰好达到下界,Frobenius 范数平方亦等于所列的和。零奇异值同样包含在论证之内。证明给出最小值与可达性,并没有找出每一个最小化矩阵。
为求完整,这里亦证明 Frobenius 最优性。令 为投影至 行空间的正交投影矩阵。因为 ,互补右投影的正交性给出
在完整正交归一右奇异基底中,对 取 ,并写 。每个 都在 内,总和为 。因此 :把至多 单位质量分配至最大的非负权重,可以令和最大。相减便证明 Frobenius 下界,并由 达到。这个证明不要求满秩,亦清楚分开两种近似目标。
证明透视
先数维数,再取加权平均
真正的想法是维数计算:秩至多为 的矩阵 不可能在 维空间 上是单射,所以 中有单位向量 满足 ,而在 上的误差就是 。左奇异向量的正交性把 变成 的加权平均,按次序它至少是 。秩的假设只在维数计算中用到。这个论证给出最小值,但没有说明哪些矩阵能达到它。
证明
(间隙只让我们在首方向以外作逆运算)
对每个单位 ,都有 。在 处计算 的 Rayleigh 商,得到 。第二特征值至多为 :把 Rayleigh 商限制在 ,此处 ,再用对称矩阵的极小极大刻画便可。因此 ,证明首方向除正负号外唯一。
令 及 。把 投影至 ,得到
在这个子空间上,左边算子的每个特征值至少为 ,故逆算子的范数至多为 。所以 ,就是所需的角度界。要证明投影矩阵等式,必要时先改变 的正负号,再写成 ,其中单位 。在 的张成空间上,两投影之差的迹为零,行列式为 ,故特征值为 ;在正交补空间上则为零。若两方向重合,两投影直接相等。逆算子这一步只需 ;定理较强的半间隙条件还保证扰动后首特征值单一,并使角度界严格小于一。
证明透视
观测到的间隙与统计保证是两项条件
逆算子界使用总体或参照矩阵的间隙 ,以及另有根据的扰动大小 。只有最大的特征值很大并不足够,因为它可能与第二个几乎相等。若 是总体协方差, 是估计,首先须用抽样论证建立 的界,然后这里的代数才把该界转为方向界。一幅看来漂亮的载荷图不能补上缺失的前提。
证明
(先追踪不需要的特征分量,再归一化)
的首系数为 。其余系数的平方和为 。两者的比值证明正切界,亦证明归一化的分母非零。在同一特征基底展开单位 ,得到
因为全部特征值非负,不需要的分量中最大模长就是 。对一般对称矩阵则未必如此:普通幂次迭代追随绝对值最大的特征值,而它可以是负数。协方差矩阵避免了这个问题,却不会避免初始首分量为零或有限精度误差。
完整例子
例题 21.1.6
(逐一拟合、压缩并重建全部观测)
取四个训练观测 、、、。均值为 。中心化各行为 、、、,所以
单位特征向量为 、,特征值分别为八及二。 的奇异值是 及 。保留一个方向,分数为 。把每个分数乘以 ,得到重建中心化各行 。加回训练均值,便得到 。
每个残差的长度平方为二,故总平方重建误差为八,每个观测的误差为二,正好等于 。谱误差则为 ;它既不是 Frobenius 范数平方,也不是每个观测的损失。所保留的方差比例是 ,只描述训练重建,不是分类准确率。
对新观测 ,中心化向量为 ,分数为 ,重建为 ,平方重建误差为二。计算中没有利用评估集重新定中心,也没有重新计算方向。
例题 21.1.7
(执行幂次迭代并解读停止证据)
对同一 ,从 开始。 与 成比例,所以 ,而
一次乘法给出 ,商为 。两次给出 ,商为 。以下只用 Python 标准库的程序执行逐次归一化迭代。程序明确指定四步预算,并没有从输出暗中推论停止准则。
from math import sqrt
z = (1.0, 0.0)
for t in range(5):
Cz = (5*z[0] + 3*z[1], 3*z[0] + 5*z[1])
rayleigh = z[0]*Cz[0] + z[1]*Cz[1]
residual = sqrt(sum((Cz[j] - rayleigh*z[j])**2 for j in range(2)))
print(t, f"{rayleigh:.9f}", f"{residual:.9f}")
if t < 4:
length = sqrt(Cz[0]**2 + Cz[1]**2)
z = (Cz[0]/length, Cz[1]/length)
0 5.000000000 3.000000000
1 7.647058824 1.411764706
2 7.976653696 0.373540856
3 7.998535514 0.093727117
4 7.999908449 0.023437142
残差衡量是否接近某个特征向量。要把它辨认为首特征向量,仍须使用非零的初始首分量及正谱间隙。对大矩阵,可以直接计算 ,不必存储 。直接奇异值分解则避免明确形成协方差矩阵,后者最大与最小非零特征值的比值,是 相应奇异值比值的平方。两种方法都不会消除训练中心化或遵守所选损失的需要。程序使用浮点算术;所印数字与精确量 及 在所列精度一致。一般浮点误差分析与通用特征值求解器,不属这个二维例子的范围。
例题 21.1.8
(间隙把非对角扰动转为角度界)
设 , 的对角元素为零,两个非对角元素都为 。其谱范数为 ,而 。所以定理给出 。直接对角化得到
精确角度符合界,但界不是等式。相反, 加上 后,首方向会由 变成 ,而扰动范数只有 。当 ,任意小的扰动都可造成直角改变,因为参照间隙也同时趋近零。小扰动的严格假设恰好在这里失效。
概念视角结构
子空间稳定性、重建及标签信息回答不同问题
重复的首特征值可以令个别载荷无法唯一辨认,但整个特征空间仍有意义。很小的间隙可以令载荷不稳定,而重建仍然良好。即使一个高方差方向十分稳定,也可以遗失类别信息。例如,两个等先验高斯(Gaussian)类别的均值为 及 ,共同类内协方差为 ,总协方差便是 。最大的主坐标在两类中有完全相同的分布,因此不含标签信息。应分别报告所选秩、训练损失、间隙及评估目标;任何一项都不能取代其余几项。
常见误解
反例模式
零残差也可以对应错误的特征向量
对 ,若从 开始,幂次迭代永远留在 。残差 精确等于零,但 Rayleigh 商只是一而非四。只有小残差并不能证明找到首分量。定理需要非零的初始首系数,而例子违反这个条件。在适当分布下随机起点可以降低此失败风险,但确定性成功的声称仍须交代前提。
常见错误
(中心化与改变单位会改变最优化问题)
对观测 、,未中心化的二阶矩矩阵是 。未中心化秩一拟合保留第一轴,把表示能力花在均值上。中心化协方差是 ,因此中心化主成分保留第二轴,加回均值后可以精确重建两个观测。两个计算都可以数值正确,却解答不同问题。
同样,若中心化协方差为 ,把第一坐标乘以 ,协方差便变成 ,首方向由第一轴转为第二轴。缩放后的欧几里得(Euclidean)重建,会按缩放因子的平方加权原坐标平方误差。因此,在称一个表示最优之前,必须交代单位与损失。用训练数据估计标准化,是合理的另一种度量,并不是原坐标主成分的不变版本。
小结
以训练数据为中心的奇异值分解,给出分数及处理新观测的完整重建规则。截断同时最小化总平方矩阵误差与最坏单位组合误差,但两者报告的数值不同。谱间隙把有根据的矩阵扰动界转为方向稳定性。对正半定矩阵,所证明的界保证:当起点包含非零首分量且 ,迭代按几何速率收敛至首方向。重复的最大特征值不在这个定理的范围,所以此界不会在该情况下选定事先指定的载荷。这些有限结果支持谨慎计算,却不证明预测表现或未知的总体协方差。
练习
快速检查
(在四观测拟合例中,用锁定的秩一表示重建新观测 。计算平方误差,并解释为何不一定要保留它的第二分数。)
先减去训练均值,再计算首分数。
解答 · 答案
中心化观测为 ,首分数为 。重建中心化向量为 ,故重建是 。残差为 ,平方误差为八。被舍弃的第二分数是 ,其平方同样为八。秩一是刻意舍弃这个坐标;这个观测的误差大,不会推翻训练最优性,只表示所选表示对它的重建可能欠佳。若因此改变秩,便是一项新的建模决定,须遵守原定的选择程序。
快速检查
(对幂次迭代例,找出最小非负整数 ,使首方向夹角的正切至多为 。计算该次迭代精确的 Rayleigh 误差。)
精确正切是四分之一的幂。
解答 · 答案
需要 。因为 而 ,最小迭代次数为五。精确 Rayleigh 误差为 ,约为 。这是指定矩阵及起点下的确定性计算,不是普遍的五步规则。若起点更靠近首方向的正交补,初始正切因子便会令所需步数增加。
快速检查
(对称参照协方差的首两个特征值为 及 。另一个论证把协方差扰动的谱范数限制在 以内。求首投影矩阵误差的谱范数界。若只知道扰动界为 ,同一论证能否保证严格小于一的界?)
代入数字之前,先检查定理的严格假设。
解答 · 答案
间隙为二,且 ,故投影矩阵误差至多为 。若只有 ,便不符合严格假设 。形式上代入会得到一,但那只是秩一正交投影之间的平凡上界,没有给出严格的方向控制。事实上, 加上 后,最大的特征值重复为六,此时可以选取与原方向正交的首方向。因此不能保证唯一的扰动后首直线。
快速检查
(设 ,只保留秩一。给出一个截断最优解、两种近似误差,以及另一个谱范数最优解。解释为何这里的 Frobenius 最优秩一矩阵仍然唯一。)
谱目标容许保留的对角元素稍有改动,只要被舍弃的三仍是最大误差。
解答 · 引导解答
截断矩阵为 。谱误差为三,Frobenius 误差平方为 ,Frobenius 误差为 。另一个秩一矩阵 的谱误差仍为 ,故同样谱最优,事实上,每个 在 时都有谱误差三; 的 Frobenius 误差平方是十一。对 Frobenius 秩一近似,严格间隙 迫使上述行空间迹界采用 ,而互补投影界取等号又要求 。这固定系数为五及两条首奇异直线,所以最优矩阵唯一。不过两个单位奇异向量仍可同时反号。谈唯一性时,必须说清楚目标,并区分矩阵与它的分解因子。