Locally Weighted Regression

简单回顾一下线性回归。我们使用了如下变量：\(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，地位平等。因为所有训练样本同等重要，针对不同的查询点就没必要重新计算每个训练样本的权值。虽然模型的性能不如局部线性回归，但是后期我们只需用学习到的参数建立的模型就可以对新样本进行估计，不用每次估计都要耗费大量资源在整个训练集上重新拟合一遍。有得必有失，在这里也体现得淋漓尽致！

以下是实验的截图，实验代码在这里下载。左图为局部权值回归，右图为线性回归。绿色曲线由采样自抛物线的样本点组成，蓝色直线为查询点对应的位置，红色直线为学习到的模型。图中的黑色红线是我手动添加的，便于进行对比。从图中可以看出，针对查询点，局部线性回归的误差明显要小于线性回归。