回归问题初步之线性回归

回归的线性模型

如图1所示,机器学习根据数据是否带标签分为:有监督学习(supervised learning)、无监督学习(unsupervised learning)、半监督学习/强化学习(seimi-supervised learning)。所谓有监督学习,即训练样本中包含输入矢量$\boldsymbol{x}$以及其对应的目标矢量$t$。进一步地,有监督学习主要完成回归和分类两大任务。
Re1

  • 回归(regression):回归问题的目标,是在给定输入$\boldsymbol{x}$,预测一个或者多个连续目标(target)变量$t$的值。多项式曲线拟合就是一个经典的回归问题。
  • 分类(classification):分类的目标是将输入变量$\boldsymbol{x}$划分到$K$个离散的类别$\left\{\mathcal{C}_k\right\}_{k=1}^K$中的某一类。

给定数据集$\mathcal{D}=\left\{(\boldsymbol{x}_1,t_1),\cdots,(\boldsymbol{x}_n,t_n)\right\}$,我们的目标是预测对于给定新的$\boldsymbol{x}$所定义的$t$值。为此,我们首先要建立模型。直观的方法是,基于训练数据集$\mathcal{D}$,建立函数$y(\boldsymbol{x},\boldsymbol{w})$,对给定新值$\boldsymbol{x}$,预测其对应的目标$t$。广义上,从概率的角度,我们是对概率$p(t|\boldsymbol{x})$进行建模,因为它表达了对于任意新的输入$\boldsymbol{x}$,其所对应的$t$的可能性。这种方法等同于最小化一个恰当的损失函数的期望值,如若选择均方误差函数,则$t$的估计值,由条件概率$p(t|\boldsymbol{x},\boldsymbol{t})$的均值给出。注意,这里$\boldsymbol{t}$是训练集中的目标变量,$t$为新值$\boldsymbol{x}$所对应的目标。

一元线性回归

线性回归模型是回归问题中的一个相对简单的特例。线性回归假设模型的输出和输入是线性关系
\begin{align}
y(\boldsymbol{x}_i,\boldsymbol{w})=\boldsymbol{w}^T\boldsymbol{x}_i+b
\end{align}
为了方便推导,我们假设$\boldsymbol{x}$的数据维度$d=1$。因此,对应的线性回归模型为
\begin{align}
f(x_i,w)=wx_i+b
\end{align}
我们的目标是让$f(x_i)$去近似$t_i$。我们选择使得均方误差最小的参数作为模型的参数
\begin{align}
(w,b)^{\ast}
&=\underset{(w,b)}{\arg \min} \frac{1}{n}\sum_{i=1}^n\left(f(x_i)-t_i\right)^2\\
&=\underset{(w,b)}{\arg \min} \sum_{i=1}^n\left(f(x_i)-t_i\right)^2
\end{align}
由于$y(x_i,w)$是$x_i$的线性函数,因此该问题是个凸问题,我们利用导数工具进行求解。定义误差函数$J=\sum_{i=1}^n\left(y(x_i,w)-t_i\right)^2$,我们首先求$J$对$b$的偏导数,并令偏导数为$0$
\begin{align}
\frac{\partial J}{\partial b}=0 \quad \Rightarrow \ b=\frac{1}{n}\sum_{i=1}^n(t_i-wx_i)=\overline{t}-w\overline{x}
\end{align}
其中$\overline{t}\overset{\triangle}{=}\frac{1}{n}\sum_{i=1}^nt_i$,$\overset{\triangle}{=}\frac{1}{n}\sum_{i=1}^nx_i$。从此处,我们可以看出,偏置$b$补偿了目标的平均值与输入的加权和之间的差

将$b$代入误差函数$J$,求$J$对$w$的偏导
\begin{align}
\frac{\partial J}{\partial w}
&=2w\sum_{i=1}^nx_i^2-2\sum_{i=1}^n(t_i-b)x_i\\
&=2w\sum_{i=1}^nx_i^2-2\sum_{i=1}^n(t_i-\overline{t})x_i-2w\overline{x}^2
\end{align}
令偏导为$0$,得
\begin{align}
w=\frac{\sum_{i=1}^nx_i(t_i-\overline{t})}{\sum_{i=1}^nx_i^2-\overline{x}^2}
\end{align}

多元线性回归

设置输入和输出呈线性关系,给定数据集合$\mathcal{D}=\left\{(\boldsymbol{x}_1,t_1),(\boldsymbol{x}_n,t_n)\right\}$,若假设样本中$\boldsymbol{x}$的维度$d>1$,这就是多元线性回归。为了简化计算步骤,这里我们设置$b=0$,即$y(\boldsymbol{x}_i,\boldsymbol{w})=\boldsymbol{w}^T\boldsymbol{x}_i$。因此,我们有
\begin{align}
\boldsymbol{y}=\boldsymbol{X}^T\boldsymbol{w}
\end{align}
其中$\boldsymbol{y}=[y(\boldsymbol{x}_1,\boldsymbol{w}),\cdots,y(\boldsymbol{x}_n,\boldsymbol{w})]^T$,$\boldsymbol{X}=[\boldsymbol{x}_1,\cdots,\boldsymbol{x}_n]$。定义误差函数$J$
\begin{align}
J=||\boldsymbol{t}-\boldsymbol{X}^T\boldsymbol{w}||^2
\end{align}
求$J$对$\boldsymbol{w}$的导数,并令偏导为零,得到
\begin{align}
\frac{\partial J}{\partial \boldsymbol{w} }=0 \quad \Rightarrow \boldsymbol{w}=(\boldsymbol{X}\boldsymbol{X}^T)^{-1}\boldsymbol{Xt}
\end{align}

线性基函数模型

上述的例子之中,我们假设输入$\boldsymbol{x}$与输出$f(\boldsymbol{x})$是线性关系,这给模型带来了很大的局限性。为此,我们设定,输出$y(\boldsymbol{x},\boldsymbol{w})$与输入的函数$\phi(\boldsymbol{x})$呈线性关系。(:对于为什么引入基函数,这一点,可以从分类问题类比过来,在样本的原始空间中,样本线性不可分,引入基函数,将样本空间映射到更高维的特征空间,达到线性可分的目的。对应的,就是样本的线性拟合,效果不好。)
\begin{align}
y(\boldsymbol{x},\boldsymbol{w})=\sum\limits_{i=1}^nw_j\phi_j(\boldsymbol{x})+b
\end{align}
其中$\phi_i(\boldsymbol{x})$称为基函数(basis function),$b$称偏置参数。基函数的选择有很多种,如

  • 高斯基函数
    \begin{align}
    \phi_j(x)=\exp \left[-\frac{(x-\mu_j)^2}{2s^2}\right]
    \end{align}
  • Sigmoid函数
    \begin{align}
    \phi_j(x)&=\sigma\left(\frac{x-\mu_j}{s}\right)\\
    \sigma(a)&=\frac{1}{1+\exp(-a)}
    \end{align}
  • 傅里叶函数、小波基函数,等。

最小二乘与最大似然

前面说到,设置输出与基函数呈线性关系,通过最小化均方误差函数,可以得到模型。这里我们从最大似然的角度出发,通过高斯噪声的假设,对概率密度$p(t|\boldsymbol{x})$进行建模,同样能够得到相同解。这里我们假设模型输出$y(\boldsymbol{x},\boldsymbol{w})$与目标$t$的差值服从高斯分布。
\begin{align}
t=y(\boldsymbol{x},\boldsymbol{w})+\epsilon
\end{align}
其中$\epsilon\sim \mathcal{N}(\epsilon|0,\beta^{-1})$,因此给模型的似然函数为
\begin{align}
p(t|\boldsymbol{x},\boldsymbol{w},\beta)=\mathcal{N}\left(t|y(\boldsymbol{x},\boldsymbol{w}),\beta^{-1}\right)
\end{align}
对于给定一个新值$\boldsymbol{x}$,目标预测,由条件均值$y(\boldsymbol{x},\boldsymbol{w})$给出,即$\mathbb{E}[t|\boldsymbol{x}]=\int tp(t|\boldsymbol{x})\text{d}t=y(\boldsymbol{x},\boldsymbol{w})$。这个例子中$t$的分布是单峰的,实际中,$t$的条件分布,可以由多个高斯的线性加权和表示(近似),即混合高斯。

给定数据集$\left\{(\boldsymbol{x}_1,t_1),\cdots,(\boldsymbol{x}_N,t_N)\right\}$,设置模型输入与输出关系为$y(\boldsymbol{x},\boldsymbol{w})=\boldsymbol{w}^T\boldsymbol{\phi}(\boldsymbol{x})$,进一步假设$t$与$y(\boldsymbol{x},\boldsymbol{w})$之间存在一个高斯误差项$\epsilon\sim \mathcal{N}(\epsilon|0,\beta^{-1})$。记$\boldsymbol{t}\overset{\triangle}{=}[t_1,\cdots,t_N]^{T}$,$\boldsymbol{X}\overset{\triangle}{=}[\boldsymbol{x}_1,\cdots,\boldsymbol{x}_N]$,则有
\begin{align}
p(\boldsymbol{t}|\boldsymbol{X},\boldsymbol{w},\beta)=\prod\limits_{n=1}^N\mathcal{N}(t_n|\boldsymbol{w}^T\boldsymbol{\phi}(\boldsymbol{x}_n),\beta^{-1})
\end{align}
我们对似然函数取对数,有
\begin{align}
\ln p(\boldsymbol{t}|\boldsymbol{X},\boldsymbol{w},\beta)
&=\sum_{n=1}^N\ln \mathcal{N}(t_n|\boldsymbol{w}^T\boldsymbol{\phi}(\boldsymbol{x}_n),\beta^{-1})\\
&=\frac{N}{2}\ln \beta-\frac{N}{2}\ln (2\pi)-\beta \left(\frac{1}{2}\sum_{n=1}^N(t_n-\boldsymbol{w}^T\boldsymbol{\phi}(\boldsymbol{x}_n))^2\right)\\
&=\frac{N}{2}\ln \beta-\frac{N}{2}\ln (2\pi)-\beta E_D(\boldsymbol{w})
\end{align}
其中$E_D(\boldsymbol{w})\overset{\triangle}{=}\frac{1}{2}\sum_{n=1}^N(t_n-\boldsymbol{w}^T\boldsymbol{\phi}(\boldsymbol{x}_n))^2$。

若假设$\beta$与$\boldsymbol{w}$无关,求对数似然关于$\boldsymbol{w}$的梯度
\begin{align}
\nabla \ln p(\boldsymbol{t}|\boldsymbol{w},\beta)=\beta \sum_{n=1}^N (t_n-\boldsymbol{w}^T\boldsymbol{\phi}(\boldsymbol{w}))\boldsymbol{\phi}(\boldsymbol{x}_n)^T
\end{align}
令梯度为0,得到
\begin{align}
\boldsymbol{w}_{\text{ML} }=\left(\sum_{n=1}^N\boldsymbol{\phi}(\boldsymbol{x}_n)\boldsymbol{\phi}(\boldsymbol{x}_n)^T\right)^{-1}\left(\sum_{n=1}^N\boldsymbol{\phi}(\boldsymbol{x}_n)t_n\right)
\end{align}
定义
\begin{align}
\boldsymbol{\Phi}=\left(
\begin{matrix}
\phi_0(\boldsymbol{x}_1) &\cdots &\phi_{M-1}(\boldsymbol{x}_1)\\
\vdots &\ddots &\vdots\\
\phi_0(\boldsymbol{x}_N) &\cdots &\phi_{M-1}(\boldsymbol{x}_N)
\end{matrix}
\right)
\end{align}
因此
\begin{align}
\boldsymbol{w}_{\text{ML} }=\left(\mathbf{\Phi}^T\mathbf{\Phi}\right)^{-1}\mathbf{\Phi}^T\boldsymbol{t}
\end{align}
很明显,这是最小二乘解(least square, LS)。

关于最小二乘,更为直观的解释,可以通过图-2表示。基函数$\left\{\boldsymbol{\phi}(\boldsymbol{x}_1),\cdots,\boldsymbol{\phi}(\boldsymbol{x}_n)\right\}$,张成空间$\mathcal{C}$(图中,考虑更为简单的特例,二维平面)。最小二乘的集合解释,就是在基函数所张成的几何空间$\mathcal{C}$上,找到$\boldsymbol{t}$的正交投影$\boldsymbol{y}$,此时所得到的误差$e$最小。
Re2

将$\boldsymbol{w}_{\text{ML} }$代回对数似然函数,求对数似然函数对$\beta$的偏导,并令其为0,得到
\begin{align}
\beta_{\text{ML} }^{-1}=\frac{1}{N}\sum_{n=1}^N\left(t_n-\boldsymbol{w}_{\text{ML} }^T\boldsymbol{\phi}(\boldsymbol{x}_n)\right)^2
\end{align}
因此,我们看到噪声方差的倒数由目标值与回归函数的加权和的残差(residual variance)给出。

正则化最小二乘(Least Square)

为了控制过拟合,我们给误差函数添加正则化项,相应地,目标函数变为
\begin{align}
J=E_D(\boldsymbol{w})+\lambda E_W(\boldsymbol{w})
\end{align}
其中$\lambda$是正则化系数,用于控制数据相对误差$E_D(\boldsymbol{w})$和正则化项$E_W(\boldsymbol{w})$的比例。正则化项的选择,可以是一个简单的权向量$\boldsymbol{w}$的二范数$E_W(\boldsymbol{w})=\frac{1}{2}||\boldsymbol{w}||^2$,若考虑平方和误差
\begin{align}
E_D(\boldsymbol{w})=\frac{1}{2}\sum_{n=1}^N(t_n-\boldsymbol{w}^T\boldsymbol{\phi}(\boldsymbol{x}_n))^2
\end{align}
则,相应的目标向量为
\begin{align}
J=\frac{1}{2}\sum_{n=1}^N(t_n-\boldsymbol{w}^T\boldsymbol{\phi}(\boldsymbol{x}_n))^2+\frac{\lambda}{2}||\boldsymbol{w}||^2
\end{align}
利用导数工具,我们可以到权值$\boldsymbol{w}$的解
\begin{align}
\boldsymbol{w}=(\lambda \mathbf{I}+\mathbf{\Phi}^T\mathbf{\Phi})^{-1}\mathbf{\Phi}^T\boldsymbol{t}
\end{align}
这是线性最小均方误差(linear minimum mean square error, LMMSE)解,这类似于给$\boldsymbol{w}$加了一个高斯先验分布。

更为一般地,考虑正则化项为$p$-范数
\begin{align}
J=E_D(\boldsymbol{w})+\lambda ||\boldsymbol{w}||^p
\end{align}
而,实际中,二范数正则化项应用较多。

贝叶斯线性回归

在讨论使用最大似然方法寻找线性回归模型时,我们已经看到,模型的复杂度由基函数$\phi(\boldsymbol{x})$的数量及其具体形式所决定。最大似然方法本身的缺陷在于,需要大量的样本(渐进最优),并且可能造成过拟合的现象。

  • 过拟合:模型在训练集上可以达到很好的效果(太依赖训练集),但是在测试集上,效果奇差。
  • 欠拟合:模型不够复杂,或者数据训练太少,导致无法预测数据。

这里,我们考虑线性回归的贝叶斯方法,为了简单起见,我们考虑单一目标变量$t$的情形。对于多个变量的推广,可以类比于线性回归的最大似然法。

参数的先验分布

关于线性回归的贝叶斯方法的讨论,我们首先引入权值矢量的先验概率分布$p(\boldsymbol{w})$。这里,我们假设其先验分布(prior distribution)为
\begin{align}
p(\boldsymbol{w})=\mathcal{N}\left(\boldsymbol{w}|\boldsymbol{0},\alpha^{-1}\mathbf{I}\right)
\end{align}
计算$\boldsymbol{w}$的后验分布(posterior distribution)如下
\begin{align}
p(\boldsymbol{w}|\boldsymbol{t})
&\propto \frac{p(\boldsymbol{t}|\boldsymbol{w})p(\boldsymbol{w})}{p(\boldsymbol{t})}\\
&\propto p(\boldsymbol{t}|\boldsymbol{w})p(\boldsymbol{w})
\end{align}
其中$p(\boldsymbol{t}|\boldsymbol{w})=\mathcal{N}(\boldsymbol{t}|\boldsymbol{\Phi}\boldsymbol{w},\beta^{-1}\mathbf{I})$为模型的似然函数
\begin{align}
\mathcal{N}(\boldsymbol{t}|\boldsymbol{\Phi w},\beta^{-1}\mathbf{I})\propto \mathcal{N}(\boldsymbol{w}|(\mathbf{\Phi}^T\mathbf{\Phi})^{-1}\mathbf{\Phi}^T\boldsymbol{t},(\beta\boldsymbol{\Phi}^T\boldsymbol{\Phi})^{-1})
\end{align}

  • 高斯相乘引理(Guassian product lemma):
    \begin{align}
    \mathcal{N}(\boldsymbol{x}|\boldsymbol{a},\boldsymbol{A})\mathcal{N}(\boldsymbol{x}|\boldsymbol{b},\boldsymbol{B})=\mathcal{N}(\boldsymbol{0}|\boldsymbol{a}-\boldsymbol{b},\boldsymbol{A}+\boldsymbol{B})\mathcal{N}(\boldsymbol{x}|\boldsymbol{c},\boldsymbol{C})
    \end{align}
    其中
    \begin{align}
    \boldsymbol{C}&=\left(\boldsymbol{A}^{-1}+\boldsymbol{B}^{-1}\right)^{-1}\\
    \boldsymbol{c}&=\boldsymbol{C}\cdot\left(\boldsymbol{A}^{-1}\boldsymbol{a}+\boldsymbol{B}^{-1}\boldsymbol{b}\right)
    \end{align}

利用高斯相乘引理,我们有
\begin{align}
p(\boldsymbol{w}|\boldsymbol{t})&=\mathcal{N}\left(\boldsymbol{w}|\boldsymbol{\mu},\boldsymbol{\Sigma}\right)\\
\boldsymbol{\Sigma}&\overset{\triangle}{=}\left(\alpha \mathbf{I}+\eta\boldsymbol{\Phi}^T\boldsymbol{\Phi}\right)^{-1}\\
\boldsymbol{\mu}&\overset{\triangle}{=}\beta\boldsymbol{\Sigma}\mathbf{\Phi}^T\boldsymbol{t}
\end{align}

预测分布

在实际应用中,我们通常对新值$\boldsymbol{x}$所对应的$t$感兴趣,这需要我们计算出预测$t$分布,定义
\begin{align}
p(t|\boldsymbol{t},\alpha,\beta)=\int p(t|\boldsymbol{w},\beta)p(\boldsymbol{w}|\boldsymbol{t},\alpha,\beta)\text{d}\boldsymbol{w}
\end{align}
注意,这里$\boldsymbol{t}$是训练集中样本目标,$t$是测试集目标。为计算该分布,我们进行维度扩充,计算
\begin{align}
p(\boldsymbol{t}’|\boldsymbol{t},\alpha,\beta)=\int p(\boldsymbol{t}’|\boldsymbol{w},\beta)p(\boldsymbol{w}|\boldsymbol{t},\alpha,\beta)\text{d}\boldsymbol{w}
\end{align}
其中
\begin{align}
p(\boldsymbol{t}’|\boldsymbol{w},\beta)=\mathcal{N}(\boldsymbol{t}|\boldsymbol{\Phi}\boldsymbol{w},\beta^{-1}\mathbf{I})\propto \mathcal{N}(\boldsymbol{w}|(\mathbf{\Phi}^T\mathbf{\Phi})^{-1}\mathbf{\Phi}^T\boldsymbol{t}’,(\beta\boldsymbol{\Phi}^T\boldsymbol{\Phi})^{-1})
\end{align}
为了简化计算步骤,定义
\begin{align}
\mathbf{H}_1&=(\mathbf{\Phi}^T\mathbf{\Phi})^{-1}\mathbf{\Phi}^T=\mathbf{\Phi}^{\dagger}\\
\mathbf{H}_2&=(\beta\boldsymbol{\Phi}^T\boldsymbol{\Phi})^{-1}
\end{align}
利用高斯相乘引理,有
\begin{align}
p(\boldsymbol{t}’|\boldsymbol{t},\alpha,\beta)
&\propto \mathcal{N}\left(\boldsymbol{H}_1\boldsymbol{t}’|\boldsymbol{\mu},\boldsymbol{H}_2+\boldsymbol{\Sigma}\right)\\
&\propto \mathcal{N}\left(\boldsymbol{t}’|\boldsymbol{\mu}_1,\boldsymbol{\Sigma}_1\right)
\end{align}
其中
\begin{align}
\boldsymbol{\Sigma}_1&=\left(\boldsymbol{H}_1^T(\boldsymbol{H}_2+\boldsymbol{\Sigma})^{-1}\boldsymbol{H}_1\right)^{-1}\\
\boldsymbol{\mu}_1&=\boldsymbol{\Sigma}_1\boldsymbol{H}_1^T(\boldsymbol{H}_2+\boldsymbol{\Sigma})^{-1}\boldsymbol{\mu}
\end{align}
由于这里,我们要求的是$t$的分布,其维度为1,因此,我们重新设置$\boldsymbol{\Phi}=[\boldsymbol{\phi}(\boldsymbol{x}),\cdots,\boldsymbol{\phi}(\boldsymbol{x})]$,计算$t$的均值和方差如下
\begin{align}
\text{方差:}&\frac{1}{N}\text{tr}\left\{\left(\boldsymbol{H}_1^T(\boldsymbol{H}_2+\boldsymbol{\Sigma})^{-1}\boldsymbol{H}_1\right)^{-1}\right\}=\frac{1}{N}\text{tr}\left\{\beta^{-1}\mathbf{I}+\boldsymbol{\Phi}^T\boldsymbol{\Sigma}\boldsymbol{\Phi}\right\}=\beta^{-1}+\boldsymbol{\phi}(\boldsymbol{x})^T\boldsymbol{\Sigma}\boldsymbol{\phi}(\boldsymbol{x})\\
\text{均值:}& \left(\boldsymbol{H}_1^T(\boldsymbol{H}_2+\boldsymbol{\Sigma})^{-1}\boldsymbol{H}_1\right)^{-1}\boldsymbol{H}_1^T(\boldsymbol{H}_1+\boldsymbol{\Sigma})^{-1}\boldsymbol{\mu}=\boldsymbol{\Phi}\boldsymbol{\mu}
\end{align}
因此
\begin{align}
p(t|\boldsymbol{t},\alpha,\beta)=\mathcal{N}(t|\boldsymbol{\phi}(\boldsymbol{x})^T\boldsymbol{\mu},\beta^{-1}+\boldsymbol{\phi}(\boldsymbol{x})^T\boldsymbol{\Sigma}\boldsymbol{\phi}(\boldsymbol{x}))
\end{align}