AI 数学课程 · 第 47 课,共 180

Gram–Schmidt 构造正交方向

手算并用 NumPy 执行 Gram–Schmidt,把残差大小作为重叠诊断,并识别顺序与浮点数不稳定性。

分享这篇文章

两个特征方向看起来可能不同,却携带几乎相同的信息。分别归一化只能修正长度,不能消除重叠。Gram–Schmidt 会移除每个新向量中已经由较早方向解释的部分,然后把剩余部分归一化。这个剩余部分的长度是一个有用的诊断:零表示相关,极小的值则警告新方向几乎冗余,或在数值上很脆弱。

学完本课后,你将能够对两个或三个向量执行 Gram–Schmidt,验证输出是否正交规范,并把残差大小解读为与尺度有关的重叠信号。你还会知道,输入顺序和所选浮点容差为什么会影响结果。

**学习成果:**对两个或三个向量执行 Gram–Schmidt,并识别不稳定性。

第 046 课:正交规范基简化坐标说明了:当方向构成正交规范基时,内积为什么能够直接读出坐标。本课解释如何从线性无关的向量列表构造这些方向。官方的 Mathematics for Machine Learning 一书将这一思想放在第 3.5 节。本文的向量演算、视觉呈现、NumPy 实现、AI 连接和评估题均为原创。

每个新方向只保留尚未解释的部分

设 a1,…,aka_1,\ldots,a_k 是 Rd\mathbb{R}^d 中的向量。输入向量不必彼此垂直,也不必是单位长度。只要每个新输入在移除较早方向后仍贡献一个非零方向,Gram–Schmidt 就能在相同的张成空间中构造单位向量 q1,…,qkq_1,\ldots,q_k。

第一个向量没有需要减去的部分。对于后续向量,可以用它与每个较早单位方向的内积,测量它沿该方向的分量。由于每个 qjq_j 都是单位长度,⟨qj,ai⟩qj\langle q_j,a_i\rangle q_j 正好是 aia_i 在该方向上的投影。

残差这个词非常重要。残差并不只是归一化后就可以丢弃的中间向量。它的范数 ∥ri∥2\lVert r_i\rVert_2 是 aia_i 到较早方向张成空间的距离。较大的残差表示,相对于当前顺序,输入贡献了相当大的新分量;较小的残差表示输入接近较早的张成空间;零残差则根本无法归一化。

这个构造是顺序式的,因此顺序是计算的一部分。如果输入线性无关,那么在精确算术中,不同顺序仍描述相同的张成空间,但每一步产生的方向、符号和残差大小可能不同。当残差接近精度下限或噪声下限时,这一点就很重要。

一次处理一个投影的三向量计算

使用 R3\mathbb{R}^3 中的三个向量:

a1=[110],a2=[101],a3=[011].a_1=\begin{bmatrix}1\\1\\0\end{bmatrix}, \qquad a_2=\begin{bmatrix}1\\0\\1\end{bmatrix}, \qquad a_3=\begin{bmatrix}0\\1\\1\end{bmatrix}.

这里的坐标没有具体物理单位;它们是一个玩具特征方向的三个分量。数字保持较小,可以清楚地看见投影和归一化过程。

下面的视觉呈现把这个顺序变成由读者控制的逐步浏览。每个面板展示一个阶段的输入、移除的总投影、残差和单位方向。表格不是装饰性的重复:它是服务器端渲染的数值回退方案,为键盘用户和辅助技术用户保留完整的比较内容。

跟随残差走过 Gram–Schmidt

可以使用按钮或选择菜单。选中的阶段会被播报,下面的表格无需交互即可使用。

1 / 3:从 a₁ 开始
跟随残差走过 Gram–Schmidt从 a₁ 开始。四个面板分别显示 输入 aᵢ、移除的投影、残差 rᵢ 和 单位方向 qᵢ;每个向量也在下面的表格中以精确形式写出。输入 aᵢx₁x₂x₃(1, 1, 0)移除的投影x₁x₂x₃(0, 0, 0)残差 rᵢx₁x₂x₃(1, 1, 0)单位方向 qᵢx₁x₂x₃(0.71, 0.71, 0)
输入向量
(1, 1, 0)
移除的投影
(0, 0, 0)
归一化前的残差
(1, 1, 0)
归一化方向
(0.71, 0.71, 0)
所有 Gram–Schmidt 阶段及其三维向量。
阶段输入 aᵢ移除的投影残差 rᵢ单位方向 qᵢ
从 a₁ 开始(1, 1, 0)(0, 0, 0)(1, 1, 0)(0.71, 0.71, 0)
从 a₂ 中移除 q₁(1, 0, 1)(0.5, 0.5, 0)(0.5, −0.5, 1)(0.41, −0.41, 0.82)
从 a₃ 中移除 q₁ 和 q₂(0, 1, 1)(0.67, 0.33, 0.33)(−0.67, 0.67, 0.67)(−0.58, 0.58, 0.58)

图示将数值四舍五入到小数点后两位;课程中的演算保留精确的根式和分数。

选择一个阶段,查看输入、已由较早方向解释的部分、剩余的残差及其归一化方向。表格是图示的完整数值替代方案。

NumPy 复现推导并暴露检查结果

实现可以把方向保存为行向量。对于每个输入,它从原始向量的副本开始,逐个减去投影,测量残差范数,并且只有当该范数超过容差时才进行归一化。numpy.linalg.norm 提供这里使用的欧几里得长度。这种一次减去一个投影的形式通常称为改进 Gram–Schmidt;在精确算术中,它与展示的求和执行相同的减法,而更新顺序会让当前残差保持显式。

import numpy as np


def gram_schmidt(vectors, rtol=1e-12):
    directions = []
    residual_norms = []

    for index, vector in enumerate(vectors, start=1):
        original = np.asarray(vector, dtype=float)
        if original.ndim != 1:
            raise ValueError(f"vector {index} must be one-dimensional")

        residual = original.copy()
        for q in directions:
            coefficient = q @ residual
            residual -= coefficient * q

        residual_norm = np.linalg.norm(residual)
        residual_norms.append(residual_norm)
        scale = max(1.0, np.linalg.norm(original))
        if residual_norm <= rtol * scale:
            raise ValueError(
                f"vector {index} is dependent at rtol={rtol:g}"
            )

        directions.append(residual / residual_norm)

    return np.array(directions), np.array(residual_norms)


A = np.array([
    [1.0, 1.0, 0.0],
    [1.0, 0.0, 1.0],
    [0.0, 1.0, 1.0],
])

Q, residual_norms = gram_schmidt(A)
np.set_printoptions(precision=8, suppress=True)
print(Q)
print(residual_norms)
print(Q @ Q.T)
print(np.allclose(Q @ Q.T, np.eye(3), rtol=1e-12, atol=1e-12))

经过验证的输出是:

[[ 0.70710678  0.70710678  0.        ]
 [ 0.40824829 -0.40824829  0.81649658]
 [-0.57735027  0.57735027  0.57735027]]
[1.41421356 1.22474487 1.15470054]
[[ 1.  0.  0.]
 [ 0.  1.  0.]
 [ 0.  0.  1.]]
True

由于方向被存为行向量,Q @ Q.T 是输出的 Gram 矩阵。单位矩阵说明对角线上是单位长度,其他位置是零交叉内积。如果实现把方向存为列向量,对应的检查就是 Q.T @ Q;必须在写乘法之前确定形状约定。

np.allclose 使用明确的相对和绝对容差比较浮点值,而不是要求小数完全相等。这是对计算结果的测试,并不允许把每个小数都当作零。容差必须与特征数据的尺度和噪声相匹配。

残差大小是有用的重叠警告,而不是判决

考虑一对几乎重复的向量:

a1=(1,1,0),a2=(1,1+10−10,0).a_1=(1,1,0), \qquad a_2=(1,1+10^{-10},0).

移除 q1q_1 分量后,第二个残差近似为

r2≈(−5×10−11, 5×10−11, 0),∥r2∥2≈7.07×10−11.r_2\approx(-5\times10^{-11},\,5\times10^{-11},\,0), \qquad \lVert r_2\rVert_2\approx7.07\times10^{-11}.

对于 rtol=1e-12,以这个输入尺度看残差超过阈值,代码会接受这个很小的新方向。对于 rtol=1e-9,它会被标记为相关。两种设置都没有发现关于特征的普遍真理:前者要求更细的区分,后者则把这种区分视为低于应用有用的分辨率。

完全相关的向量更清楚。如果 a2=2a1a_2=2a_1,减去它的投影会留下 r2=0r_2=0。除以 ∥r2∥2\lVert r_2\rVert_2 就是除以零,因此健壮的实现必须停止、丢弃这个向量,或报告冗余。不能输出 nan 后继续假装存在新方向。

代码中的尺度感知检查使用 ∥ri∥2≤rtol max⁡(1,∥ai∥2)\lVert r_i\rVert_2\le\texttt{rtol}\,\max(1,\lVert a_i\rVert_2) 作为判定规则。在真实特征流水线中,应根据预期测量噪声、特征缩放和下游决策选择阈值,并把选择记录在诊断中。没有尺度的容差很难解释。

顺序会改变基,也会改变稳定性故事

Gram–Schmidt 是保持张成空间的构造,不是与顺序无关的排序操作。重新排列线性无关的输入,会改变首先构造的方向,因此后续的投影、残差和归一化方向都可能改变。在精确算术中,最终的向量列表仍张成相同子空间,但基向量可能在该子空间内旋转或反号。接近相关时,这种差别更重要:把几乎冗余的向量放得太早,可能让后面的残差看起来很小;先放条件更好的方向,则可能留下更多数值余量。

对于小型教学计算,显式循环很有价值,因为每个投影都能看见。对于更大的矩阵或病态矩阵,应使用经过测试的 QR 分解,例如 numpy.linalg.qr,并检查其秩或重构诊断。这改变的是数值工具,而不是几何目标。

特征方向不等于统计独立的变量

假设矩阵的行是特征方向:它们可能是手工设计的测量模式、学习到的探针,或用于检查模型表示的方向。Gram–Schmidt 可以为它们的张成空间建立正交坐标框架。残差范数告诉实践者,相对于已经处理的行,每一行增加了多少新的线性方向。这可以帮助审查特征,或在下游线性分析之前发现近似重复项。

但它不能证明原始随机变量在统计上独立,也不保证预测更好。正交性是在选定内积下比较固定向量;统计独立性则是关于联合概率分布的陈述。即使协方差为零,也只排除了某一种线性关系。

一个具体的反例是取中心化样本

x=(−2,−1,0,1,2),y=(2,−1,−2,−1,2)=x2−2.x=(-2,-1,0,1,2), \qquad y=(2,-1,-2,-1,2)=x^2-2.

它们的点积为

xTy=(−2)(2)+(−1)(−1)+0(−2)+1(−1)+2(2)=0.x^{\mathsf T}y=(-2)(2)+(-1)(-1)+0(-2)+1(-1)+2(2)=0.

样本列没有线性重叠,但 yy 完全由 xx 通过非线性规则决定。在 AI 报告中,应说方向在所声明的约定下正交,或中心化样本协方差为零。只有当有单独的概率论论证支持时,才使用“独立”这个结论。

因此,Gram–Schmidt 为上一课的正交规范坐标思想提供了一个实用桥梁:移除已解释的部分,测量留下的内容,只在剩余部分有意义时归一化,并报告作出决定时的顺序和容差。下一课将使用相同的残差思想描述与整个子空间正交的方向。

检查你的理解

问题 1

对于输入向量 a₁,…,aᵢ 和已有的单位方向 q₁,…,qᵢ₋₁,写出残差 rᵢ,并解释为什么它的范数有信息量。

显示分步解答

先减去在每个较早方向上的投影:

ri=ai−∑j=1i−1⟨qj,ai⟩qj.r_i=a_i-\sum_{j=1}^{i-1}\langle q_j,a_i\rangle q_j.

因为 qjq_j 是单位长度,系数 ⟨qj,ai⟩\langle q_j,a_i\rangle 测量了沿 qjq_j 的分量。移除所有这些分量后,∥ri∥2\lVert r_i\rVert_2 就是 aia_i 到较早方向张成空间的距离。零值表示没有新的方向留下;小值表示在当前数值尺度下,输入几乎位于该张成空间中。

问题 2

对 a₁=(1, 1) 和 a₂=(1, 0) 执行前两个 Gram–Schmidt 步骤。给出 q₁、从 a₂ 中移除的投影、r₂ 和 q₂。

显示分步解答

第一个范数是

∥a1∥2=12+12=2,q1=[1/21/2].\lVert a_1\rVert_2=\sqrt{1^2+1^2}=\sqrt2, \qquad q_1=\begin{bmatrix}1/\sqrt2\\1/\sqrt2\end{bmatrix}.

a2a_2 的投影系数是

q1Ta2=12.q_1^{\mathsf T}a_2=\frac1{\sqrt2}.

因此投影向量为 (1/2,1/2)(1/2,1/2),并且

r2=[10]−[1/21/2]=[1/2−1/2].r_2=\begin{bmatrix}1\\0\end{bmatrix} -\begin{bmatrix}1/2\\1/2\end{bmatrix} =\begin{bmatrix}1/2\\-1/2\end{bmatrix}.

它的范数为 1/21/\sqrt2,因此归一化得到

q2=[1/2−1/2].q_2=\begin{bmatrix}1/\sqrt2\\-1/\sqrt2\end{bmatrix}.

交叉内积为 q1Tq2=1/2−1/2=0q_1^{\mathsf T}q_2=1/2-1/2=0,这验证了新方向。

问题 3

在本课的三向量示例中,为什么从 a₃ 中移除的总投影等于 (2/3, 1/3, 1/3)?请展示相加前的两个投影向量。

显示分步解答

两个系数是

q1Ta3=12,q2Ta3=16.q_1^{\mathsf T}a_3=\frac1{\sqrt2}, \qquad q_2^{\mathsf T}a_3=\frac1{\sqrt6}.

将每个系数乘以其方向:

12q1=[1/21/20],16q2=[1/6−1/61/3].\frac1{\sqrt2}q_1 =\begin{bmatrix}1/2\\1/2\\0\end{bmatrix}, \qquad \frac1{\sqrt6}q_2 =\begin{bmatrix}1/6\\-1/6\\1/3\end{bmatrix}.

逐个坐标相加得到

[1/2+1/61/2−1/60+1/3]=[2/31/31/3].\begin{bmatrix}1/2+1/6\\1/2-1/6\\0+1/3\end{bmatrix} =\begin{bmatrix}2/3\\1/3\\1/3\end{bmatrix}.

这个向量就是 a3a_3 中已经由前两个方向解释的部分;减去它,就得到用来构造 q3q_3 的残差。

问题 4

当一个新输入恰好是较早输入的倍数(例如 a₂=2a₁)时,Gram–Schmidt 实现应该怎么做?

显示分步解答

如果 a2=2a1a_2=2a_1,第一个方向 q1q_1 就张成了 a2a_2。投影为

(q1Ta2)q1=2∥a1∥2q1=2a1=a2,(q_1^{\mathsf T}a_2)q_1=2\lVert a_1\rVert_2q_1=2a_1=a_2,

因此残差是 r2=0r_2=0。它的范数为零,表达式 r2/∥r2∥2r_2/\lVert r_2\rVert_2 没有定义。实现必须报告相关性、丢弃重复项,或采用明确记录的策略;不能归一化零向量,也不能默默保留 nan 值。

问题 5

为什么两个不同的输入顺序会产生不同的 q 向量,即使它们张成相同的子空间?在精确算术中什么保持不变?

显示分步解答

每个新方向都要与之前的方向正交。改变顺序会改变每一步的较早张成空间,因此投影、残差和归一化方向都可能改变。方向还可能反号,而不改变它所表示的一维子空间。

对于线性无关的输入,精确算术仍会保持完整列表的张成空间:每个原始向量都能由输出方向重构,而输出方向位于原始张成空间中。单个基向量和中间残差大小依赖于顺序,所以顺序是数值诊断的一部分。

问题 6

代码把 q 向量存为行。哪个矩阵检查可以验证正交规范性?行与列的混淆会怎样改变检查?

显示分步解答

当向量按行存储时,QQTQ Q^{\mathsf T} 的第 (i,j)(i,j) 个元素就是第 ii 行和第 jj 行的内积。因此正确检查是

QQT≈I.Q Q^{\mathsf T}\approx I.

在 NumPy 中,可以使用 np.allclose(Q @ Q.T, np.eye(Q.shape[0]), atol=...),并声明容差。如果方向按列存储,对应的 Gram 矩阵则是 QTQQ^{\mathsf T}Q。把列存储的检查用于按行存储的数据,可能检查错误的两两关系,甚至得到与目标单位矩阵形状不匹配的结果。

问题 7

一个新特征方向移除较早方向后,残差范数为 0.00000000007。这是否自动意味着该特征没有用?

显示分步解答

不是。这个数值表示,在当前输入尺度和顺序下,新方向相对于较早的张成空间贡献很小。它是否可以忽略,取决于测量噪声、特征单位、下游敏感度和所选容差。

例如,对单位尺度向量,rtol=1e-12 可能接受接近 7×10−117\times10^{-11} 的残差,而 rtol=1e-9 可能把它分类为相关。正确的解读是记录清楚的数值决定——“低于此分辨率”或“在此分辨率下保留”——而不是关于预测价值的普遍结论。

问题 8

为什么特征样本之间中心化后的点积为零,不能证明统计独立?请使用 x=(−2,−1,0,1,2) 和 y=(2,−1,−2,−1,2)。

显示分步解答

先计算线性重叠:

xTy=−4+1+0−1+4=0.x^{\mathsf T}y=-4+1+0-1+4=0.

由于两个样本向量都已中心化,这也表示在通常的等权约定下经验协方差为零。但关系 y=x2−2y=x^2-2 决定了 xx 的每个值对应的 yy。因此二者存在非线性依赖,尽管线性内积为零。

正交性和零协方差描述的是一次线性比较。独立性则要求关于完整联合分布的陈述,因此需要单独的证据。

资料来源

  1. Mathematics for Machine Learning book PDF, Section 3.5
  2. NumPy documentation: numpy.linalg.norm
  3. NumPy documentation: numpy.allclose
  4. NumPy documentation: numpy.linalg.qr