劉應興的部落格

最小絕對離差迴歸 (Least Absolute Deviation regression) 是取代最小平方準則，而代之以看 Yi 與 Yi' = Xi'b 之絕對離差和之最小化的線性迴歸模型配適 (fitting) 方法。前曾談過垂直距離迴歸法，但那看的其實是垂直距離平方和，而非垂直距離之和。而此處談的也不是 Yi 至迴歸線或面的垂直距離，而是 Yi 與 Yi' 之間差距的絕對值加總；最小平方法是前項差距的平方和。

以數學式來表示，我們要

minimize Σ |Yi - Xi'β|

一般解法是把上列問題化為線性規劃問題：令 Ui = |Yi - Xi'V|，則原問題可以寫成

Minimize Σ Ui
Subject to: Yi - Xi'β = Ui or -Ui
            Ui ≧ 0
                   i = 1, ..., n

上列問題限制式 Yi - Xi'β = Ui or -Ui 表明 (U, β)是要在兩個超平面之一，下列問題則將限制條件放寬：

Minimize Σ Ui
Subject to: 
  Yi - Xi'β ≦ Ui
  Xi'β - Yi ≦ Ui
            Ui ≧ 0
                   i = 1, ..., n

n除了沒有限制 β 的元素非負以外，這完全是一個標準的線性規劃 (linear programming) 問題。由於線性規劃問題的可行解 (feasible solution) 範圍是由一堆超平面所圍成的凸形區域，最適解必在邊界，也就自然是

Yi - Xi'β = Ui or -Ui

之一。因此，雖然似乎放寬了限制條件，最後仍歸於原條件。

線性規劃的演算法在有限個 simplex 頂點之間更換，以找尋使目標函數極小化的 (U, β) 解。其中 β 是我們要的迴歸係數（估計），U 則是殘差或離差。但它有 2n 個限制式，n + k 個待解變數（k 是 β 的元素個數，等於線性迴歸模型解釋項數加 1），另加 2n 個鬆弛變數 (slack variables)，運算也是不輕鬆，電腦計算（不可能人工計算）需要龐大的記憶體。不過電腦容量愈來愈大，運算能力愈來愈強，更有現成解線性規劃問題的程式，這是近三十年來 LAD 迴歸法受到重視的一項重要原因。

事實上可以很簡單的用疊代法來逐步逼近 β 的 LAD 解。首先，若有一堆資料 Di, i = 1, ..., n，則使 Σ |Di -b| 最小化的 b 值是資料 Di 的中位數 (median)；若是要極小化加權離差和，

minimize Σ Wi |Di - b|

則 b 應取諸 Di 的加權中位數，意即 Di 依大小順序排後，找 Wi 累積值從小於或等於1/2 總權值，至不小於1/2 所在的 Di 值。現在假設迴歸模型如下：

Yi = β0 + β1*Xi1 + ... + βp*Xip + Ei

配適方法是尋找 β0, β1, ..., βp 使

minimize Σ |Yi - β0 - β1 Xi1 - ...- βp Xip|

其計算程序如下：

令 Xi0 = 1, i = 1,...,n.
(0) 設定 β0, β1, ..., βp 初值；
　　設定疊代完成條件及檢查方式
(1) 設 j = 0
(2) 計算
      Di = (Yi - Σ_{k≠j} βk Xik)/Xij
      Wi = |Xij|, W0 = ΣWi
(3) 將 (Di,Wi) 依 Di 數值大小排序。
(4) 累計前項排序後之 Wi, 至累計值從小於或等於 W0/2 至不小於 W0/2，由此得到諸 Di 之加權中位數。
(5) If j.EQ.p then
       檢查是否需要下一輪疊代
    Else
       set j = j + 1
       回 (2)
(6) 如需下一輪疊代，則
　　　更新疊代檢查方式，回 (1)。

每輪疊代是更新所有 β 參數估計值；而每更新一個參數的值，都是讓絕對離差和更小：

Σ_i |Xij| |Yi - Σ_k βk Xik|/|Xij| = Σ_i  |Yi - Σ_k βk Xik|

隨著 βj 更新而變小或頂多不變，因此這程序必然收斂。檢查是否需再下一輪疊代可由比較上列絕對離差和在完成一輪疊代中是否已無明顯改進，或檢查一輪疊代對諸 βj 的改變是否足夠微小，也可控制最大疊代次數。此法的缺點是：除 Di 的計算外，加權中位數的尋找需做 Di 的排序，最快速的排序也需要 O(n ㏒ n) 的時間，而這些計算是每更新一個 βj 參數值都需要做的；如果加上無法保證快速收斂，則其計算量之龐大可能令人難以接受。