為何要壓縮目標函數?
假設大量觀測各有 個特徵,把特徵行放進 ,回應放進 。我們希望找出使 最小的向量 。當 遠大於 ,全部數據可能放不進記憶體,一個 矩陣卻可以。理想的摘要讓我們只讀每行一次,仍能重現相同的最小二乘問題。本節用 QR 建立此摘要,補充前面的單變量直線擬合流程。
正交分解
先假設 。我們需要的摘要由它必須滿足的性質來定義,而不是由計算方法來定義。
定義 4.2.1
(薄 QR 分解與最小二乘摘要)
設 ,,且 。
- 薄 QR 分解把 寫為 ,其中 的列標準正交(), 為上三角矩陣。即使 秩不足,此分解仍存在,但此時 奇異。
- 的最小二乘摘要是三元組 ,其中 為上三角矩陣、、,使得對每個 都有 。
下面的引理說明薄 QR 分解直接給出一份摘要。
引理 4.2.2
(殘差的正交分拆)
設 為薄 QR 分解,並令 、。則對每個 ,
證明
(交叉項消失)
寫成
因 且 ,有 ,所以殘差 垂直於 的每一列,而 位於這些列的生成空間。不論 為何,兩項都互相正交,由畢氏定理(Pythagoras)得 。最後,對每個 有 ,於是第一項等於 。
這比只保留最小化解更強:整個目標函數及其最小值都得以保留。精確運算下 ;浮點運算中,若殘差很小,此相減可能損失精度。對 施加相同的正交變換並累加被捨棄分量的平方,可避免依賴這個相減,但仍有捨入誤差。
若 滿列秩, 可逆,唯一的最小化解滿足 ;應用三角回代,而非計算顯式逆矩陣。最小損失為 。若秩不足,式 (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 分解。
解答 · 答案
取 ,得 、、。所以 ,最小損失為 ;確實, 時殘差為 。
快速檢查
(處理新塊時,維持的常數 會否減少?)
看 的更新規則。
解答 · 答案
不會。更新式為 ,平方範數非負,所以 。若計算值減少,表示有捨入問題或記賬錯誤,例如用新值覆蓋 而不是加到 上。
快速檢查
(滿列秩矩陣 的最大與最小奇異值分別為 和 。求 和 。)
利用 的奇異值與 的特徵值之間的關係。
解答 · 答案
。 的最大和最小特徵值為 和 ,故 。這項比較並未在沒有誤差分析及數據下斷言實際誤差。