高效的在線線性回歸
我正在分析一些我想執行普通線性回歸的數據，但是這是不可能的，因為我正在處理具有連續輸入數據流的在線設置（這將很快變得太大而無法存儲）並且需要在消耗它時更新參數估計。即我不能只將它全部加載到內存中並對整個數據集執行線性回歸。
我假設一個簡單的線性多元回歸模型，即
創建線性回歸參數的持續更新估計的最佳算法是什麼和?
理想情況下：
- 我想要一個最每次更新的空間和時間複雜度，其中是自變量的維數（） 和是因變量的維數（）。
- 我希望能夠指定一些參數來確定每個新樣本更新了多少參數，例如 0.000001 意味著下一個樣本將提供參數估計的百萬分之一。這將對遙遠過去的樣本效應產生某種指數衰減。
Maindonald 描述了一種基於Givens 旋轉的順序方法。（Givens 旋轉是兩個向量的正交變換，將其中一個向量中的給定條目歸零。）在上一步中，您已經分解了設計矩陣 $ \mathbf{X} $ 成三角矩陣 $ \mathbf{T} $ 通過正交變換 $ \mathbf{Q} $ 以便 $ \mathbf{Q}\mathbf{X} = (\mathbf{T}, \mathbf{0})' $ . （從三角矩陣中獲取回歸結果既快速又容易。）在與新行相鄰時 $ v $ 以下 $ \mathbf{X} $ , 你有效地擴展 $ (\mathbf{T}, \mathbf{0})' $ 也有一個非零行，比如說 $ t $ . 任務是將該行歸零，同時將條目保持在 $ \mathbf{T} $ 對角線。一系列 Givens 旋轉可以做到這一點：第一行的旋轉 $ \mathbf{T} $ 將第一個元素歸零 $ t $ ; 然後與第二排的旋轉 $ \mathbf{T} $ 將第二個元素歸零，依此類推。效果是預乘 $ \mathbf{Q} $ 通過一系列旋轉，這不會改變其正交性。
當設計矩陣有 $ p+1 $ 列（回歸時就是這種情況 $ p $ 變量加一個常數），所需的旋轉次數不超過 $ p+1 $ 每次旋轉改變兩個 $ p+1 $ -向量。所需的存儲空間 $ \mathbf{T} $ 是 $ O((p+1)^2) $ . 因此該算法的計算成本為 $ O((p+1)^2) $ 在時間和空間上。
類似的方法可以讓您確定刪除行對回歸的影響。Maindonald 給出公式；貝爾斯利、庫赫和威爾士也是如此。因此，如果您正在尋找用於回歸的移動窗口，您可以將窗口的數據保留在循環緩衝區中，與新數據相鄰並在每次更新時刪除舊數據。這會使更新時間加倍並需要額外的 $ O(k (p+1)) $ 存儲寬度的窗口 $ k $ . 看起來 $ 1/k $ 將是影響參數的模擬。
對於指數衰減，我認為（推測性地）您可以將此方法應用於加權最小二乘法，為每個新值賦予大於 1 的權重。不需要維護先前值的緩衝區或刪除任何舊數據。
參考
JH Maindonald，統計計算。 J. Wiley & Sons，1984 年。第 4 章。
DA Belsley、E. Kuh、RE Welsch，回歸診斷：識別有影響的數據和共線性來源。 J.威利父子公司，1980 年。