为何要压缩目标函数?
假设大量观测各有 个特征,把特征行放进 ,响应放进 。我们希望找出使 最小的向量 。当 远大于 ,全部数据可能放不进内存,一个 矩阵却可以。理想的摘要让我们只读每行一次,仍能重现相同的最小二乘问题。本节用 QR 建立此摘要,补充前面的单变量直线拟合流程。
正交分解
先假设 。我们需要的摘要由它必须满足的性质来定义,而不是由计算方法来定义。
定义 4.2.1
(薄 QR 分解与最小二乘摘要)
设 ,,且 。
- 薄 QR 分解把 写成 ,其中 的列标准正交(), 为上三角矩阵。即使 秩亏,这个分解仍然存在,但此时 奇异。
- 的最小二乘摘要是三元组 ,其中 为上三角矩阵、、,使得对每个 都有 。
下面的引理说明薄 QR 分解直接给出一份摘要。
引理 4.2.2
(残差的正交分拆)
设 为薄 QR 分解,并令 、。则对每个 ,
证明
(交叉项消失)
写成
因为 且 ,有 ,所以残差 与 的每一列正交,而 位于这些列张成的空间中。无论 取什么,两项都互相正交,由勾股定理得 。最后,对每个 有 ,于是第一项等于 。
这比只保留最小化解更强:整个目标函数及其最小值都得以保留。精确运算下 ;在浮点运算中,若残差很小,这个相减可能损失精度。对 施加相同的正交变换并累加被舍弃分量的平方,可以避免依赖这个相减,但仍有舍入误差。
若 列满秩, 可逆,唯一的最小化解满足 ;应使用三角回代,而不是计算显式逆矩阵。最小损失为 。若秩亏,式 (1) 仍成立,但 可能无解或有无穷多个解。一般而言应先最小化 ,再加上 得到最小损失; 本身不一定是最小损失。秩揭示 QR 或 SVD 可以识别数值秩,并给出指定的解(例如最小范数解);普通的无主元回代不会自动做到这一点。
常见错误
(对奇异三角因子进行回代)
若两个特征列相同,则每个薄 QR 的因子都形如 ,因为 的第二列已经落在第一列张成的空间中。回代时会遇到方程 : 时无解, 时有无穷多解。除以零主元,或者除以舍入产生的极小主元,得到的系数向量没有意义。把 当作有唯一解之前,应先检查秩,或改用秩揭示方法。
分块算法与不变量
读入至少有 行的第一块 和响应 ,计算薄 QR:,设 、。之后维护摘要 。对每一个后续块 ,分解叠合矩阵并变换叠合响应:
用新摘要取代旧摘要。即使叠合矩阵秩亏, 仍有 个标准正交列。实际的 Householder 实现可以把反射变换直接作用于响应,无须构造完整的 。
命题 4.2.3
(保留目标函数的流式不变量)
处理若干块后,设 是这些块拼接所得的矩阵和向量。精确运算下,摘要对每个 满足
证明
(对已处理的块作归纳)
第一块由引理式 (1) 满足此式。设加入另一块 之前此式成立。叠合向量的平方范数等于各部分平方范数之和,所以对每个
对叠合矩阵和叠合响应 应用式 (1):最后的平方范数等于 。再加上 ,恰好得到上面规定的 。由归纳法得证。
这个归纳很短,但两个等号各自用到不同的假设。
证明透视
假设在归纳中何处出现
第一个等号只是把行叠起来:新块只附加一次,旧数据则由归纳假设代替。这种代替之所以合法,是因为归纳假设对每个 成立,即作为函数相等,而不只是在最小化解处相等。若摘要只保留旧的最小化解,就无法与新块合并,因为两个损失之和的最小化解并不由各自的最小化解决定。第二个等号是对叠合矩阵应用引理;旧的 已有 行,所以叠合矩阵至少有 行。引理只需要标准正交的列,不需要满秩,因此允许秩亏的块。论证之所以能闭合,是因为新常数等于旧常数加上这一步舍弃的能量。会破坏结论的是数据而不是代数:同一块读入两次,会把它的平方残差加两次,从而改变目标函数。
同一恒等式也支持树状归约:对互不重叠、各有至少 行的块分别求摘要,叠合两份摘要的 与 ,再做 QR,最后把两个 和新舍弃的能量相加。树状归约和顺序归约得到的 或 的符号可以不同,但在精确运算下目标函数相同。浮点结果则可能随归约次序改变。
概念视角代数
摘要就是增广矩阵的三角因子
把 附加为新的一列。当 时,增广矩阵的一个薄 QR 分解是
因此 正是它的 三角因子 ,而 是最后一个对角元的平方。等价地,这个因子满足 ,把算例中验证的三个恒等式合而为一。流式更新摘要,就是逐个行块地更新 的 QR 因子。
算例
例题 4.2.4
(三个观测、两个特征)
取三行 、、,响应分别为 。前两行给出 、、。加入第三行后,其中一个有效摘要是
可以独立检查 ,以及 ;另有 。展开两边即可由这三个等式确立式 (1)。回代得 。三个残差 为 ,因此损失是 ,与 相同。
同一更新规则也能合并分别计算的两份摘要,这正是树状归约所需要的。
例题 4.2.5
(合并两份标量摘要)
两个互不重叠的块的摘要为 和 。把它们叠合:矩阵为 ,响应为 。其薄 QR 有 、,所以 。新舍弃的能量为 ,合并后的常数为 。合并摘要是 。
直接验证:总目标是 ,正好等于 。最小化解是 ,最小值为 。第二块的 必须保留。
最后一例是叠合矩阵秩亏的退化情形。
例题 4.2.6
(秩亏的块)
令 、。第一列的范数为 ,故 ;第二列与第一列相同,薄 QR 可以用 补全 ,并取
式 (1) 变为 ,所以所有满足 的解都是最优的,最小值为零。回代停在 , 可以任取。令 ,平方范数 唯一地在最小范数解 处取最小值。
成本、条件数与反例
每块有 行时,对 的稠密叠合矩阵做 Householder QR 需要 次算术运算。存储叠合矩阵与响应需要 个数,摘要另需 ;当 ,对全部 行做稠密 QR 为 。若有 块,顺序叠合分解的总算术上界为 ,其中包括重复处理 行摘要的成本。这些是算术和工作存储模型,并不保证实际运行时间:输入带宽、通信、实现和稀疏性都会影响成本。块大小影响额外开销,稀疏矩阵分解后也不一定仍然稀疏。
另一种紧凑归约方法是构造 和 ;但当 列满秩时,谱条件数满足 ,因为 的特征值是 的奇异值的平方。大的条件数再平方,可能放大敏感度和舍入的影响。QR 避免显式构造法方程矩阵,却不能消除原问题本身的敏感度。这里的精确恒等式也不保证每种实现都有指定的数值误差。
反例模式
缺少残差常数的摘要
断言:只用 就足以报告最小二乘拟合。令 、。则 、、,而 。丢弃 仍得到正确的最小化解 ,因为此处 ;但它报告的最小损失为零,而残差 给出的损失是 。合并之后错误依然存在:每次舍弃的常数都丢失了。修正后的说法是:摘要必须是定义中的三元组 。
拟合得好也不能证明系数准确。
常见错误
(把小残差当作系数准确)
取 、,其中 很小。精确解是 ,但向量 的残差为 ,损失只有 。因此当特征近乎线性相关时,极小的损失可以与误差达 的量级的系数同时出现。系数是否准确应由条件数判断,不能只看残差。
练习与完整解答
快速检查
(对 、,求 、、 和最小化解。)
这是两行的单个块:计算一个薄 QR 分解。
解答 · 答案
取 ,得 、、。所以 ,最小损失为 ;确实, 时残差为 。
快速检查
(处理新块时,维护的常数 会不会减小?)
看 的更新规则。
解答 · 答案
不会。更新式为 ,平方范数非负,所以 。若计算值减小,说明有舍入问题或记账错误,例如用新值覆盖 而不是加到 上。
快速检查
(列满秩矩阵 的最大与最小奇异值分别为 和 。求 和 。)
利用 的奇异值与 的特征值之间的关系。
解答 · 答案
。 的最大和最小特征值为 和 ,故 。这一比较在没有误差分析和数据的情况下,并不断言实际误差。