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

\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}

代價(jià)函數(shù)定義如下：

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

在線性回歸問(wèn)題中，特征的選擇會(huì)直接影響到模型的性能。如下圖所示，僅使用一個(gè)特征\(x\)時(shí)，很多樣本點(diǎn)都沒(méi)落到直線上，模型的擬合程度不怎么好；如果我們?cè)黾右粋€(gè)特征\(x^2\)，擬合效果好很多；如果用5階多項(xiàng)式來(lái)擬合，可以保證圖中的6個(gè)樣本點(diǎn)全部落在曲線上。這種現(xiàn)象不禁讓我們想，是不是使用的特征越多越好？答案是否定的。左圖存在的問(wèn)題稱(chēng)之為 欠擬合(underfitting) ，該模型過(guò)于簡(jiǎn)單，不足以捕捉數(shù)據(jù)的諸多結(jié)構(gòu)信息；右圖存在的問(wèn)題稱(chēng)之為 過(guò)擬合(overfitting) ，模型設(shè)計(jì)得過(guò)于復(fù)雜，雖能完美擬合訓(xùn)練集集上的數(shù)據(jù)信息，卻不能揭示更一般化的規(guī)律。

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

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

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

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

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

加權(quán)線性回歸的目標(biāo)函數(shù)形式如下：

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

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

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

參數(shù)迭代更新方式基本不變：

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

一般而言，局部加權(quán)回歸效果會(huì)比線性回歸好很多。在訓(xùn)練集很大的情況下，該方法的效率就很低了。因?yàn)閷?duì)應(yīng)后續(xù)的每個(gè)查詢點(diǎn)，其與訓(xùn)練樣本之間的權(quán)重都不同。我們首先要計(jì)算訓(xùn)練集中所有樣本點(diǎn)與查詢點(diǎn)直接的權(quán)值，然后執(zhí)行線性擬合過(guò)程，并確定適用于該查詢點(diǎn)的參數(shù)\(\theta\)，最后在該查詢點(diǎn)處進(jìn)行估計(jì)。

其實(shí)，線性回歸可視為局部線性回歸的一個(gè)特例。在線性回歸中，所有訓(xùn)練樣本的權(quán)值都為1，地位平等。因?yàn)樗杏?xùn)練樣本同等重要，針對(duì)不同的查詢點(diǎn) 就沒(méi)必要重新計(jì)算每個(gè)訓(xùn)練樣本的權(quán)值。 雖然模型的性能不如局部線性回歸，但是后期我們只需用學(xué)習(xí)到的參數(shù)建立的模型就可以對(duì)新樣本進(jìn)行估計(jì)，不用每次估計(jì)都要耗費(fèi)大量資源在整個(gè)訓(xùn)練集上重新擬合一遍。有得必有失，在這里也體現(xiàn)得淋漓盡致！

以下是實(shí)驗(yàn)的截圖， 實(shí)驗(yàn)代碼在這里下載 。 左圖為局部權(quán)值回歸，右圖為線性回歸。綠色曲線由采樣自拋物線的樣本點(diǎn)組成，藍(lán)色直線為查詢點(diǎn)對(duì)應(yīng)的位置，紅色直線為學(xué)習(xí)到的模型。圖中的黑色紅線是我手動(dòng)添加的，便于進(jìn)行對(duì)比。從圖中可以看出，針對(duì)查詢點(diǎn)，局部線性回歸的誤差明顯要小于線性回歸。

Locally Weighted Regression