面壁者系列：線性回歸

02-25

回歸的目的是預測數值型數據的目標值。儘可能使預測的值去擬合真實值。線性回歸，則是預測值和features是線性關係。

線性回歸演算法特點

優點：結果易於理解，計算上不複雜。缺點：對非線性的數據擬合不好。適用於數據類型：數值型和標稱型數據。

Hypothesis Function

$h( heta)= heta^Tx$

$heta$ 是回歸係數（coefficient），x是每個數據點。

Cost Function

$frac{1}{2m}sum_i^m (y^{(i)}- heta^T x^{(i)})^2$

$y^{(i)}$ 是第i個真實值， $x^{(i)}$ 是第i個樣本數據點。

可以用梯度下降法來得出最優解：

$ext{repeat until convergence：}{ \ heta_j := heta_j - frac{alpha}{m}sum_i^m( heta^Tx^{(i)}-y^{(i)}) x^{(i)}_j ext{ for j:= 0...n} \ }$

每次循環都要遍歷每個樣本數據點。

向量化表示為：

$heta := heta - frac{a}{m} X^T(X heta-vec{y})$

$X$ 為 $m imes (n+1)$ 矩陣, n features 額外的1為了 $w_0$ 等於residue, m data points。 $vec{y}$ 與之對應的y $m imes 1$ 真實值向量。 $alpha$ 為步長（用來加快或減慢收斂速度）。

梯度下降法建議進行 特徵歸一化(feature scaling)。這樣會使收斂更快。

或者用正規方程求解：

$heta = (X^TX)^{-1}X^Ty$

正規方程不需要特徵歸一化。

以下是梯度下降法和正規方程的比較:

梯度下降法：

可以選定步長 $alpha$

得出的係數為真實值的近似值

$o(kn^2)$

需要循環多次

樣本數量大的時候也ok

正規方程：

無需選定步長

得出的係數為真實值

無需循環

$o(n^3)$ 因為需要計算逆矩陣

樣本數量特別大的時候會很慢（n>10000）

Local weighted linear regression (LWLR) 局部加權線性回歸

線性回歸的一個問題是線性回歸傾向於欠擬合數據。很多方法通過增加bias可以減少 mean squared error 均方誤差。 局部加權線性回歸就是其中一種方法。對於測試的數據點附近的樣本點給以權重，然後與線性回歸類似，在這個子集上基於最小均方誤差來進行普通的回歸。與KNN類似，這種類型的回歸每次迭代都需要使用整個數據集來計算。

$sum_i^m w^{(i)} (y^{(i)}- heta^Tx^{(i)}) \ ext{ where } w^{(i)} = exp(frac{(x^{(i)}-x)^2}{-2k^2})$

LWLR 使用「核」（與支持向量機中的核類似）來對附近的點賦予更高的權重。核的類型可以自由選擇，最常用的核就是高斯核，高斯核對應的權重如下:

$w_i = exp(frac{(x^{(i)}-x)^2}{-2k^2})$

當點 $x$ 與 $x^{(i)}$ 越近， $w^{(i)}$ 將會越大，越接近於1。越遠，越接近與0。上述公式中包含一個需要用戶指定的參數 $k$ ，它決定了對附近的點賦予多大的權重，這也是使用 LWLR 時唯一需要考慮的參數。

需要的注意的是這個權重公式雖然叫高斯核，但是 $w^{(i)}$ 跟高斯沒有任何關係。實際上 $w^{(i)}$ 不是隨機變數，或者正態分布，其他之類的。 $k$ 是當 $x^{(i)}$ 遠離 $x$ 的時候，控制權重下降多快的程度。 $k$ 叫做 帶寬（bandwidth）參數。

該演算法解出回歸係數 $heta$ 的形式如下:

$heta = (X^TWX)^{-1}X^TWvec{y}$

其中 $X$ 為 $m imes n$ 矩陣， $W$ 是一個對角矩陣，用來給每個數據點賦予權重, 它的對角為 $w^{(i)} ext{for i=1...n}$ ,其他為0。

如何理解LWLR呢？

不是嘗試去擬合單條回歸線，而是去擬合很多線性回歸模型。最後產生的光滑曲線是所有線性回歸模型的產物。
顯而易見的是我們不能一直用同一個線性模型來擬合。相反，對於每個需要擬合線性模型，我們選擇一個測試點（需要預測的data point）x來擬合一個局部線性模型。
我們找的的x附近的點們來擬合我們的局部線性模型。這就是為什麼在有些地方這種演算法叫做最近鄰演算法。

比如你有100個單維度的測試的點（即只有一個特徵），從1到100: [1,2,3 ... 98, 99, 100]。那麼這個演算法就為1,2,3...,98,99,100 每個點擬合一個線性模型。那麼你就會有100個線性模型。

我想擬合 x=50 這個點，那麼 [48,49,50,51,52]這幾個點的權重較高，[45,46,47,53,54,55]的權重就較低。如果想擬合 x=95這個點，那麼相比於其他的點，[93,94,95,96,97]的權重較高。

正則化

正則化是為了防止模型過擬合。比如，有時候特徵比樣本數據多的時候（n>m）, 正規方程是求不了解（無法求逆）。我們可以手動減少特徵，也可以將目標函數正則化即在目標函數中加入 正則項或叫懲罰項 來解決過擬合問題。

$frac{1}{2m}sum_i^m (y^{(i)}- heta^T x^{(i)})^2 + lambda sum_{j=1}^n heta_j^2$

回歸則變成了 ridge regression 嶺回歸。在這種情況下，回歸係數的計算公式將變成：

$heta = (X^TX+lambda L)^{-1}X^Ty \ ext{where L = } egin{bmatrix} 0& & & \ &1 & & \ & & ddots & \ & & & 1 end{bmatrix}$

這裡 $X$ 為 $m imes (n+1)$ 矩陣, n features 額外的1為了 $w_0$ 等於residue, m data points。 $y$ 與之對應的y $m imes 1$ 真實值向量。

嶺回歸最先用來處理特徵數多於樣本數的情況，現在也用於在估計中加入偏差，從而得到更好的估計。這裡通過引入 λ 來限制了所有 $heta$ 平方和，通過引入該懲罰項，能夠減少不重要的參數的影響，這個技術在統計學中也叫作 縮減(shrinkage) 。

如果懲罰項為 $lambda sum_{j=1}^n heta_j$ ，那麼這種正則化叫Lasso 法。這種方法可以是演算法叫一些不重要或者微乎其微的特徵的係數縮減到0。這種方法可以自由選擇特徵。

前向逐步回歸演算法（forward stagewise regression）可以得到與 Lasso 差不多的效果，但更加簡單。它屬於一種貪心演算法，即每一步都儘可能減少誤差。一開始，所有權重都設置為 0，然後每一步所做的決策是對某個權重增加或減少一個很小的值。

偽代碼如下:

數據標準化，使其分布滿足 0 均值和單位方差在每輪迭代過程中: 設置當前最小誤差 lowestError 為正無窮對每個特徵: 增大或縮小: 改變一個係數得到一個新的 w (回歸係數) 計算新 w 下的誤差如果誤差 Error 小於當前最小誤差 lowestError: 設置 Wbest 等於當前的 W 將 W 設置為新的 Wbest

逐步線性回歸演算法的主要優點在於它可以幫助人們理解現有的模型並作出改進。當構建了一個模型後，可以運行該演算法找出重要的特徵，這樣就有可能及時停止對那些不重要特徵的收集。最後，如果用於測試，該演算法每100次迭代後就可以構建出一個模型，可以使用類似於10折交叉驗證的方法比較這些模型，最終選擇使誤差最小的模型。

Bias and Variance Tradeoff 權衡偏差和方差

一般認為，誤差由三個部分組成: 偏差、測量誤差和隨機雜訊。任何時候，一旦發現模型和測量值之間存在差異，就說出現了誤差。當考慮模型中的「雜訊」或者說誤差時，必須考慮其來源。你可能會對複雜的過程進行簡化，這將導致在模型和測量值之間出現「雜訊」或誤差，若無法理解數據的真實生成過程，也會導致差異的產生。另外，測量過程本身也可能產生「雜訊」或者問題。

Tips

在使用梯度下降法的時候，或者使用Lasso或者ridge，建議使特徵歸一化。