簡單回顧一下 線性回歸 。我們使用了如下變量：\(x\)—輸入變量/特征；\(y\)—目標變量；\((x,y)\)—單個訓練樣本；\(m\)—訓練集中的樣本數目；\(n\)—特征維度；\((x^{(i)},y^{(i)})\)—第\(i\)個訓練樣本。在接下來的內容中，仍沿用這些標識。我們給定的模型假設為：

\begin{equation}h_{\theta}(x)=\theta_0+\theta_1x_1+\cdots+\theta_nx_n=\sum_{i=1}^n\theta_ix_i=\theta^Tx\end{equation}

代價函數定義如下：

\begin{equation}J(\theta)=\frac{1}{2}\sum_{i=0}^m(h_{\theta}(x^{(i)})-y^{(i)})^2\end{equation}

在線性回歸問題中，特征的選擇會直接影響到模型的性能。如下圖所示，僅使用一個特征\(x\)時，很多樣本點都沒落到直線上，模型的擬合程度不怎么好；如果我們增加一個特征\(x^2\)，擬合效果好很多；如果用5階多項式來擬合，可以保證圖中的6個樣本點全部落在曲線上。這種現象不禁讓我們想，是不是使用的特征越多越好？答案是否定的。左圖存在的問題稱之為 欠擬合(underfitting) ，該模型過于簡單，不足以捕捉數據的諸多結構信息；右圖存在的問題稱之為 過擬合(overfitting) ，模型設計得過于復雜，雖能完美擬合訓練集集上的數據信息，卻不能揭示更一般化的規律。

下面介紹線性回歸的一種改進算法——局部加權回歸(Locally Weighted Regression,LWR)。局部加權回歸是一種 非參數(non-parametric) 型學習算法 ，能在一定程度上將我們從特征選擇的困境中拉出來一點。 參數型學習算法 事先假設數據來自某種模型，然后推斷模型參數。這類學習算法通常都有固定數目的參數，一旦學習到參數后，模型也就建立起來了，接下來就能扔掉訓練數據并利用該模型獨立完成任務。如果事先的假設與實際情況比較接近，模型可以給出比較準確的估計；否則，估計到的參數會有很強的誤導性。 非參數型學習算法 不會事先指定模型，其參數由訓練數據決定。這里的非參數不是說完全沒有參數，而是指參數數目不是固定的，并且會隨訓練集規模的增加而增多。此外，我們必須保留整個訓練集，以便后續進行完成后續的任務。

結合上圖來闡述局部加權回歸的主要思想。綠色的樣本點(采樣自拋物線)為訓練集中的數據。利用線性回歸擬合該訓練集，最終得到紅線表示的線性模型，很顯然該模型在訓練集上的擬合程度相當差，對特定查詢點(Query Point)給出的估計與實際情況相差甚遠。局部加權回歸則重點考慮查詢點附加的樣本點(如紅色圓形劃定的樣本集合)，然后在這個樣本子集合上執行加權線性回歸，得到紫色直線所示的模型。該模型在估計查詢點附近的樣本時準確度還是很高的。權值是由樣本點與查詢點間的相似度(在幾何空間可用距離度量)決定，越相似的權值越大，差異越大的權值幾乎為0(相當于忽略這些樣本)。

權值函數有很多種，只要滿足兩個基本條件即可：1)相似樣本間權值較大；2)相似度非常小的樣本間權值近似為0。最常用權值函數如下：

\begin{equation}w^{(i)}=\exp\left(-\frac{\|x^{(i)}-x\|^2}{2\tau^2}\right)\end{equation}

\(\|x^{(i)}-x\|^2\)為第\(i\)個樣本\(x^{(i)}\)和查詢點\(x\)之間的歐式距離。顯然，當\(\|x^{(i)}-x\|^2\)很小時，\(w^{(i)}\approx 1\)；當\(\|x^{(i)}-x\|^2\)很大時，\(w^{(i)}\approx 0\)。參數\(\tau\)稱為帶寬參數(Bandwidth Parameter)，控制權值隨距離變量的速度。如下圖所示，\(\tau\)越小，權值變化越平緩；\(\tau\)越大權值變化越快。

加權線性回歸的目標函數形式如下：

\begin{equation}J(\theta)=\frac{1}{2}\sum_{i=1}^mw^{(i)}(h_{\theta}(x^{(i)})-y^{(i)})^2\end{equation}

單個樣本\((x^{(j)},y^{(j)})\)情況下的梯度下降問題與線性回歸基本相似：

\begin{equation}\frac{\partial}{\partial\theta_j}J(\theta)=w^{(j)}(h_{\theta}(x^{(j)})-y^{(j)})\cdot x_i\end{equation}

參數迭代更新方式基本不變：

\begin{equation}\theta_i=\theta_i-\alpha\sum_{j=1}^mw^{(j)}(h_{\theta}(x^{(j)})-y^{(j)})x_i^{(j)}\end{equation}

一般而言，局部加權回歸效果會比線性回歸好很多。在訓練集很大的情況下，該方法的效率就很低了。因為對應后續的每個查詢點，其與訓練樣本之間的權重都不同。我們首先要計算訓練集中所有樣本點與查詢點直接的權值，然后執行線性擬合過程，并確定適用于該查詢點的參數\(\theta\)，最后在該查詢點處進行估計。

其實，線性回歸可視為局部線性回歸的一個特例。在線性回歸中，所有訓練樣本的權值都為1，地位平等。因為所有訓練樣本同等重要，針對不同的查詢點 就沒必要重新計算每個訓練樣本的權值。 雖然模型的性能不如局部線性回歸，但是后期我們只需用學習到的參數建立的模型就可以對新樣本進行估計，不用每次估計都要耗費大量資源在整個訓練集上重新擬合一遍。有得必有失，在這里也體現得淋漓盡致！

以下是實驗的截圖， 實驗代碼在這里下載 。 左圖為局部權值回歸，右圖為線性回歸。綠色曲線由采樣自拋物線的樣本點組成，藍色直線為查詢點對應的位置，紅色直線為學習到的模型。圖中的黑色紅線是我手動添加的，便于進行對比。從圖中可以看出，針對查詢點，局部線性回歸的誤差明顯要小于線性回歸。

Locally Weighted Regression