動機
大型矩陣運算常把大量時間花在讀取數據行及累加外積。隨機近似問:能否只抽取較少貢獻,仍以足夠精度回答指定問題?目標不是讓隨機性看來先進,而是用明確誤差交換較少算術或通訊,同時把建立抽樣分佈的成本算進去。
草圖可以承諾不同事情:均方意義下近似一個矩陣乘積、高概率保留一個預先固定向量的長度,或同時保留整個子空間。這些量詞不同。對抽樣前固定的向量成立,不代表對看過草圖後由優化器選出的向量也成立。用抽樣 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
(在抽樣求解的擾動界中,取 。計算係數誤差上界,並說明 的作用。)
核心
解答 · 答案
分子為 ,分母為 ,所以界為 。嚴格小於一使最小特徵值下界為正;到一時已容許奇異,不能再由此推得有限逆範數。