动机
大型矩阵运算常把大量时间花在读取数据行及累加外积。随机近似问:能否只抽取较少贡献,仍以足够精度回答指定问题?目标不是让随机性看来先进,而是用明确误差换取较少算术或通信,同时把建立抽样分布的成本算进去。
草图可以承诺不同事情:均方意义下近似一个矩阵乘积、高概率保留一个预先固定向量的长度,或同时保留整个子空间。这些量词不同。对抽样前固定的向量成立,不代表对看过草图后由优化器选出的向量也成立。用抽样 Gram 矩阵求线性系统时,这个差别尤其重要。
本节建立两个有限算法:抽取数据行的外积,以及随机符号投影。证明只需期望、内积及初等不等式,能构成随机数值线性代数的严谨起点。更强的子空间嵌入与最小二乘抽样定理仍须另学。程序是框架中立的 Python;种子使例子可重现,定理则在理想独立抽样下分析。
定义
定义 6.1.1
(重要性抽样矩阵乘积)
设 、,第 行分别为列向量 的转置。因此
选概率 、总和为一,且凡 都有 ;这样的概率称为容许概率。独立有放回抽取 ,定义
零概率项的外积必为零,也永远不会被抽到。Frobenius 范数是各元素平方和的平方根,对应内积把矩阵视为有限维欧氏(Euclidean)向量。尤其 ,因此每行对乘积的贡献大小可以量化。
定义 6.1.2
(随机符号草图)
随机符号草图是矩阵 ,其每个元素独立地取正负 ,各占一半。它把 映到 。
只有 个坐标,但直接稠密计算仍读取全部 个输入,并做 次符号贡献。输出缩小,不等于输入处理必然较便宜;对矩阵的所有列作草图也有相同的成本问题。
数据先固定,然后才作随机选择。期望描述重复抽样的结果。下面的无偏性是精确算术恒等式;有限精度的概率及累加另有数值误差。一次打印结果不必等于期望,固定种子也不是准确度证书。
概念视角代数
两个估计量都是草图化乘积
行抽样同样是乘以一个随机矩阵。令 的第 行为 ,则 的第 行是 ,并且
因此下面两个定理都在度量:从数据看去,随机 矩阵 或 离单位矩阵有多远。对符号草图, 的对角元恰为一,非对角元均值为零,所以 。对抽样,,即在正概率的行上是单位矩阵;容许条件恰好使 。同样的代数也说明 是 的无偏估计,而且无须任何概率。
定理 / 命题
第一个结果关于抽样乘积;第二个关于固定向量在符号草图下的长度。
定理 6.1.3
(无偏乘积与精确均方误差)
行抽样估计量满足
若 ,取 可在容许概率中最小化此误差,值为 。对任何 ,Frobenius 误差至少为 的概率不超过该均方误差除以 。
符号草图的命题需要四阶矩,因为关心的量本身已是平方。
定理 6.1.4
(固定有限向量集的符号草图保证)
对固定 ,
对 个预先固定的非零向量,并集界保证同时相对平方长度误差小于 的失败概率不超过 。此界可能大于一,也可能保守;向量集须与草图的选择独立。
证明思路
证明
(无偏性、方差与最优概率)
令 为一次抽取。只有 的索引会被抽到,所以 ;由于被略去的项外积都为零,这正是 。它的期望 Frobenius 范数平方是 ,即定理中的求和,减去均值范数平方便得方差。矩阵空间也是欧氏空间;独立中心向量的交叉内积期望为零,所以平均 次把方差除以 。
令 。Cauchy–Schwarz 给出 ,而概率与非零 成正比时取等号。对误差平方使用 Markov 不等式,便得尾概率界。这限制的是绝对矩阵误差;若真乘积近乎相消,相对误差仍可能很大。
第二个证明把草图长度化为一行符号。
证明
(一行符号的四阶矩)
对一行未缩放的符号,写 。独立零均值符号给出 。展开四次方,只有每个索引出现偶数次的项留下,故
平方草图长度是 个独立 的平均。从四阶矩减去 得 ,平均后再除以 ,便得精确方差。Chebyshev 给出单向量失败界 ,再把有限集的失败概率相加。不同向量的失败事件无须彼此独立,并集界仍然有效。
证明透视
符号的每个性质在哪里用上
符号证明在三处分别用了三个不同性质。零均值与两两独立消去 的交叉项;无偏性只需要这一点。
方差是唯一非例行的一步,而它其实是计数。项 在四个索引两两配对时为一,否则为零。对固定的 ,多重集 有 种排列,这就是系数六。由于 ,对角项贡献 。若元素是标准高斯(Gauss)变量,对角项会贡献 ,方差变成较大的 ,恰好是定理中的上界。
行彼此独立只用于把方差除以 ;Chebyshev 除方差外不需要别的。并集界不需要向量之间独立,但每个向量的失败概率都是在该向量固定时计算的。第二个例题说明这个假设不能去掉:每个实现的一行草图都把某个列空间方向送到零,所以看过 后才选的方向可以以概率一失败。
例题详解
例题 6.1.5
(可执行的重要性抽样乘积)
取 ,标量行 。乘积为 ,最优概率是三分之一和三分之二。单次贡献不是 就是 ,故 次的均方误差为 ;均匀抽样则是 。以下完整实现也处理全部贡献为零的情况:
import math
import random
import bisect
from itertools import accumulate
def sampled_product(A, B, draws, seed=7):
if draws < 1 or not A or len(A) != len(B):
raise ValueError("invalid sample dimensions")
d, k = len(A[0]), len(B[0])
if any(len(a) != d for a in A) or any(len(b) != k for b in B):
raise ValueError("ragged matrix")
weights = [math.sqrt(sum(x*x for x in a)) *
math.sqrt(sum(y*y for y in b)) for a, b in zip(A, B)]
total = math.fsum(weights)
answer = [[0.0] * k for _ in range(d)]
if total == 0:
return answer
active = [(i, weight) for i, weight in enumerate(weights) if weight > 0]
cdf = list(accumulate(weight / total for i, weight in active))
cdf[-1] = 1.0
rng = random.Random(seed)
for _ in range(draws):
position = bisect.bisect_right(cdf, rng.random())
i = active[position][0]
scale = total / (draws * weights[i])
for j in range(d):
for ell in range(k):
answer[j][ell] += scale * A[i][j] * B[i][ell]
return answer
A = [[1.0, 0.0], [0.0, 2.0]]
B = [[1.0], [1.0]]
estimate = sampled_product(A, B, draws=6)
print(estimate)
所示种子输出 [[1.5], [1.5]]。与真值的差是普通抽样误差,不反驳无偏性。建立概率须先扫描行范数,之后抽到某行还须能读取该行。小例子保存原矩阵;大型文件另需索引、蓄水池设计或其他访问策略,不能省略其成本再宣称加速。
例题 6.1.6
(符号草图可完全漏掉某个向量)
,草图只有一行。符号不同时平方长度为零,相同时为四,各占一半;期望正确地为二,方差则为四。平均 行后方差是 。一次完全抵消与无偏估计可以同时成立。
对两列矩阵 ,若草图有 行,则 必有非零的零空间向量 。若原来两列线性无关, 就是原列空间中真正非零、却被 消去的方向。因此每个一行草图都失去某个列空间方向,但该方向可随草图而变。固定向量保证与全方向一致保证,确实是不同结论。
例题 6.1.7
(无偏矩阵推不出无偏解)
正标量 以相同概率取一或三,故 。固定右端为一,解的期望为 ,但先对矩阵取均值再求解得到 。求逆是非线性的。抽样 Gram 元素无偏,不代表系数无偏,更不代表每次抽样的系统都可逆。
要连接求解器,可先证一个确定性结果。它把抽样 Gram 矩阵的算子范数事件转化为系数误差界。
命题 6.1.8
(抽样正规方程求解的扰动界)
设 正定,最小特征值为 ,,且 。若对称矩阵 满足 ,其中 ,又 ,则 可逆,且 的解满足
证明
(先下界二次型,再相减)
对单位向量 ,。由于 对称,其最小特征值至少为 ,故可逆且 。从 减去 ,得 ,其范数至多为 。乘以 即得上界。
随机乘积定理要变成求解器定理,须控制这些条件同时成立的事件,而不是只算期望。Frobenius 界可以控制不大于它的算子范数,但预算可能保守。
预算必须说明误差尺度
可用输入能量归一化,避免除以近乎零的真乘积。
推论 6.1.9
(以输入能量为尺度的抽取预算)
设 并使用最优概率。对每个 ,
故 次抽取足以把失败概率压到 。
证明
(对行范数用 Cauchy–Schwarz)
Cauchy–Schwarz 给出 ,而因 ,右端为正。最优均方误差为 。取 应用 Markov 不等式,便得上式。
这是与维数无关的外积抽取数,却不是相对于 的误差定理。两个大外积近乎抵消时,输入能量可远大于答案。
每个稠密外积仍需 工作。程序的累积概率数组可用二分查找,每次需 次比较;行范数及数组的准备要读取输入,另存 个概率。直接乘法为 ;只有抽取数远小于行数、且访问成本合理时,才可能节省外积工作。小问题及不利的访问模式足以抵消优势,这些成本计数并非实测速度。
常见错误
常见错误
(漏掉逆概率权重)
把抽到的外积直接平均而不除以 ,估计的是概率加权乘积 ,而不是 。标量贡献为一及三、概率为 及 时,未加权平均的期望是 ,目标却是四。正是除以 ,才使每次抽取都是整个和的无偏估计。
反例模式
非零贡献配上零概率
声称:只要把每个抽到的项除以其概率,任何概率向量都给出无偏估计。取标量贡献一及三,概率 。每次都抽到第一个索引,所以每个估计都是 ,期望为一而非四;第二个贡献永远无法恢复。修正就是定义中的容许条件:凡 都须 。恰为零的贡献可以给零概率,因为期望只略去零项。
与成对行范数乘积 成正比的概率,只对这个 Frobenius 误差准则最优,不能顺便宣称对子空间保留或预测风险也最优。
常见错误
(把输出维数当成输入成本)
稠密符号草图处理一个向量需 ,处理 列需 。它缩小后续数据维数,但对极稀疏输入未必是好的第一步;结构化或稀疏草图须另作构造与证明。算法名称本身不是资源分析。
常见错误
(只报告最好看的种子)
反复试种子再只展示最漂亮的结果,已经改变了报告程序。应记录预算、概率及选择规则。定理包含不方便的抽样结果,不只包含作者想展示的实现。重复实验可研究典型表现,却不能取代已声明的概率空间。
总结
重要性抽样给出无偏乘积、精确方差及指定准则下的最优行概率。随机符号保留固定向量平方长度的期望,并有有限集概率界。求解稳定性、一致子空间保留及输入访问各需额外论证;小型草图的承诺应停在已证明的地方。
练习
练习 6.1.10
(标量贡献为一及三,分别用均匀概率及与贡献成比例的概率作单次逆概率估计,比较两者的方差。)
基础
解答 · 答案
真和为四。均匀抽样返回 或 ,方差为四;比例概率为 ,两种结果除以概率后都为四,故方差为零。这依赖同向正标量的结构;矩阵贡献方向不同时,同一概率规则一般不会给出零方差。
练习 6.1.11
(十个固定非零向量,相对平方长度误差小于 ,失败概率至多 。初等符号界需要多少行?此维数是否锐利?)
基础
解答 · 答案
要求 ,得 。它来自四阶矩与并集界,属充分但可能很松的预算。更强的集中不等式可给出对数级的有限集维数界,但此处没有证明,不能把它当成已得结论。
练习 6.1.12
(为何抽样数等于列数时,有放回行抽样的 Gram 矩阵仍可能奇异?给一个两行的例子。)
核心
解答 · 答案
取 ,抽两次且每行概率都为正。两次都抽到第一行有正概率,所得 Gram 只有第一坐标方向,第二特征值为零;原 Gram 却是单位矩阵。抽样次数不是秩的证书。
练习 6.1.13
(在抽样求解的扰动界中,取 。计算系数误差上界,并说明 的作用。)
核心
解答 · 答案
分子为 ,分母为 ,所以界为 。严格小于一使最小特征值下界为正;等于一时已容许奇异,不能再由此推得有限的逆范数。