机器学习 - 局部加权线性回归

174

(本系列的 Jupyter Notebook 可以到我的码云下载。)

概述

局部加权线性回归(Locally Weighted Linear Regression, LWLR)是一种非参数算法。与k近邻类似,它并没有模型参数,也没有训练过程,而是直接使用整个数据集来做预测。它的核心思想是:在做预测时,更多地参考距离预测样本近的已知样本,而更少地参考距离预测样本远的已知样本。

建模

首先回顾一下线性回归的内容,线性回归中我们引入了如下的损失函数:


\begin{align*} \mathcal{L} = \frac{1}{2} \sum_{i=1}^m (y^{(i)} - \boldsymbol{\theta}^T \mathbf{x}^{(i)})^2 \tag{1} \end{align*}

损失函数是一个加和的式子,每一个式子是单个样本的真实值与预测值的距离:


\begin{align*} \mathcal{L} = \dfrac{1}{2} \left[ \left(y^{(1)} - \boldsymbol{\theta}^T \mathbf{x}^{(1)} \right)^2 + \left(y^{(2)} - \boldsymbol{\theta}^T \mathbf{x}^{(2)} \right)^2 + \cdots + \left(y^{(m)} - \boldsymbol{\theta}^T \mathbf{x}^{(m)} \right)^2 \right] \tag{2} \end{align*}

损失函数的值越小越好,也就是上面相加的每一项越小越好。注意上面的每一项对损失函数而言都是同等重要的。而局部加权线性回归则采用了不同的做法,它将上面的每一项增加了一个权重,从而使它们对损失函数造成不同的影响:


\begin{align*} \mathcal{L} &= \dfrac{1}{2} \left[ w^{(1)} \left(y^{(1)} - \boldsymbol{\theta}^T \mathbf{x}^{(1)} \right)^2 + w^{(2)} \left(y^{(2)} - \boldsymbol{\theta}^T \mathbf{x}^{(2)} \right)^2 + \cdots + w^{(m)} \left(y^{(m)} - \boldsymbol{\theta}^T \mathbf{x}^{(m)} \right)^2 \right] \\ &= \frac{1}{2} \sum_{i=1}^m w^{(i)} \left(y^{(i)} - \boldsymbol{\theta}^T \mathbf{x}^{(i)}\right)^2 \tag{3} \end{align*}

其中的 $w^{(i)}$ 表示每一个样本的权重:


\begin{align*} w^{(i)} = \exp \left( - \dfrac{\left(\mathbf{x}^{(i)} - \mathbf{x}\right)^2}{2k^2} \right) \tag{4} \end{align*}

其中 $k$ 是一个超参数,描述了随着已知样本与预测样本距离的增加,其重要程度减少的速率。现在仅考虑某一特定已知样本和某一特定预测样本,即固定 $\left(\mathbf{x}^{(i)} - \mathbf{x}\right)^2$ 的值,我们来分析 $k$ 的取值对权重 $w^{(i)}$ 的影响:当 $k^2 \to +\infty$ 时 $\dfrac{\left(\mathbf{x}^{(i)} - \mathbf{x}\right)^2}{2k^2} \to 0$,进而 $ w^{(i)} \to 1$,因此 $k$ 越大权重减小的速率越慢;当 $k^2 \to 0^+$ 时 $\dfrac{\left(\mathbf{x}^{(i)} - \mathbf{x}\right)^2}{2k^2} \to +\infty$,进而 $w^{(i)} \to 0$,因此 $k$ 越小权重减小的速率越快。从下图可以看出 $k$ 与权重的关系:

图1 - $k$与权重的关系

继续分析 $(4)$ 式,现在我们固定 $k$ 的值,分析不同已知样本与预测样本的距离对权重 $w^{(i)}$ 的影响:当 $\left(\mathbf{x}^{(i)} - \mathbf{x}\right)^2 \to 0$ 时 $\dfrac{\left(\mathbf{x}^{(i)} - \mathbf{x}\right)^2}{2k^2} \to 0$,进而 $w^{(i)} \to 1$,因此已知样本距离预测样本越近,权重 $w^{(i)}$ 越大;当 $\left(\mathbf{x}^{(i)} - \mathbf{x}\right)^2 \to +\infty$ 时 $\dfrac{\left(\mathbf{x}^{(i)} - \mathbf{x}\right)^2}{2k^2} \to +\infty$,进而 $w^{(i)} \to 0$,因此已知样本距离预测样本越远,权重 $w^{(i)}$ 越小。

求解

为了简化计算,将以 $w^{(i)}$ 为 $ii$ 元的对角矩阵记为 $\mathbf{W}$。则 $(3)$ 式可以转换为矩阵形式:


\begin{align*} \mathcal{L} &= \dfrac{1}{2} \left( \mathbf{y} - \mathbf{X} \boldsymbol{\theta} \right)^T \mathbf{W} \left( \mathbf{y} - \mathbf{X} \boldsymbol{\theta} \right) \tag{5} \end{align*}

整理:


\begin{align*} \mathcal{L} &= \dfrac{1}{2} \left( \mathbf{y} - \mathbf{X} \boldsymbol{\theta} \right)^T \mathbf{W} \left( \mathbf{y} - \mathbf{X} \boldsymbol{\theta} \right) \\ &= \dfrac{1}{2} \left( \mathbf{y}^T \mathbf{W} - \boldsymbol{\theta}^T \mathbf{X}^T \mathbf{W} \right) \left( \mathbf{y} - \mathbf{X} \boldsymbol{\theta} \right) \\ &= \dfrac{1}{2} \left( \mathbf{y}^T \mathbf{W} \mathbf{y} - \mathbf{y}^T \mathbf{W} \mathbf{X} \boldsymbol{\theta} - \boldsymbol{\theta}^T \mathbf{X}^T \mathbf{W} \mathbf{y} + \boldsymbol{\theta}^T \mathbf{X}^T \mathbf{W} \mathbf{X} \boldsymbol{\theta} \right) \\ &= \dfrac{1}{2} \left( \mathbf{y}^T \mathbf{W} \mathbf{y} - 2 \mathbf{y}^T \mathbf{W} \mathbf{X} \boldsymbol{\theta} + \boldsymbol{\theta}^T \mathbf{X}^T \mathbf{W} \mathbf{X} \boldsymbol{\theta} \right) \tag{6} \end{align*}

上面的整理过程中,$\mathbf{y}^T \mathbf{W} \mathbf{X} \boldsymbol{\theta}$ 与 $\boldsymbol{\theta}^T \mathbf{X}^T \mathbf{W} \mathbf{y}$ 可以合并的原因是它们都是标量,而标量的转置就是其本身,另外由于 $\mathbf{W}$ 是对角矩阵,因此 $\mathbf{W}^T = \mathbf{W}$。

为了求得最小值,令上式的导数等于 $\mathbf{0}$(关于矩阵的求导详见线性回归):


\begin{align*} \dfrac{\partial \mathcal{L}}{\partial \boldsymbol{\theta}} &= - \mathbf{X}^T \mathbf{W} \mathbf{y} + \mathbf{X}^T \mathbf{W} \mathbf{X} \boldsymbol{\theta} = \mathbf{0} \tag{7} \end{align*}

解出 $\boldsymbol{\theta}$,得到最优解:


\begin{align*} \widehat{\boldsymbol{\theta}} &= \left( \mathbf{X}^T \mathbf{W} \mathbf{X} \right)^{-1} \mathbf{X}^T \mathbf{W} \mathbf{y} \tag{8} \end{align*}

示例

通过 $(4)$ 式与 $(8)$ 式,我们就可以应用局部线性回归解决实际问题了。

构造数据集

首先构造一些数据:

1
2
3
4
5
6
7
8
9
m = 100

np.random.seed(42)
x_values = 100 * np.random.rand(m,1)
x_values = np.sort(x_values, axis=0)
y = 7 * np.sin(0.12 * x_values) + x_values + 2 * np.random.randn(m, 1)
plt.figure(figsize=(10, 5))
plt.plot(x_values, y, "b.")
plt.show()

构造的数据如下:

图2 - 数据集

预测

局部加权线性回归没有训练步骤,而是直接使用训练集进行预测:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def calculate_theta(x_test, k):
# 构造矩阵 W
W = np.eye(m, m)
for i in range(m):
W[i,i] = np.exp(- np.sum(np.square(X[i] - x_test)) / (2 * k**2))

# 应用局部加权线性回归,求解 theta
theta = np.linalg.inv(X.T.dot(W).dot(X)).dot(X.T).dot(W).dot(y)

return theta

def predict(x_test, k):
theta = calculate_theta(x_test, k)
y_pred = theta[0] + x_test * theta[1]
return y_pred

print(predict(50, 5))

输出如下:

1
[48.041602]

过拟合与欠拟合

根据上面的图1,$k$ 的值越小,随着已知样本与预测样本距离的增加,权重下降的速度越快,因此如果 $k$ 的值过小,就会在短距离内使已知样本的权重接近于 $0$(图1最下面的子图),导致模型更多地纳入了局部噪音而造成过拟合(下图最下面的子图)。 反之,$k$ 的值越大,随着已知样本与预测样本距离的增加,权重下降的速度越慢,因此如果 $k$ 的值过大,就会使所有已知样本的权重都接近于 $1$(图1最上面的子图),这就回到了线性回归的情形,而线性回归往往因为过于简单而造成欠拟合(下图最上面的子图)。因此只有 $k$ 的值适中才能使模型更好的拟合实际规律(图1中间的子图和下图中间的子图)。 以上论述可以通过下面的图形说明:

图3 - 过拟合与欠拟合


局部加权线性回归就讲到这里,感谢阅读!如果有任何疑问或建议,请在留言区留言!

版权声明:本文为原创文章,转载请注明出处。http://cynhard.com/2018/07/13/ML-Locally-Weighted-Linear-Regression/

推荐文章