简述

在统计学中,线性回归(Linear Regression)是利用称为线性回归方程的最小平方函数对一个或多个自变量和因变量之间关系进行建模的一种回归分析。这种函数是一个或多个称为回归系数的模型参数的线性组合。
机器学习中,我们通过线性回归得到的模型对其它的输入值预测出相对应的输出值。上述的模型我们称它为 假设,函数表达为 h(x):XYh(x):\mathcal{X}\mapsto\mathcal{Y}

基本过程

现在,我们有 mm 个样本 x\boldsymbol{x},对于每一个样本 x(i)\boldsymbol{x}^{(i)} ,一共有 nn 个特征值,为 xj(i)\boldsymbol{x}^{(i)}_{j} 。有 nn 个系数(模型参数)θ0θ1θn\theta_0\quad\theta_1\dots\theta_n
则我们的预测函数为:

hθ(x)=θ0+θ1x1+θ2x2++θnxnh_{\theta}(x) = \theta_0 +\theta_1 x_1+\theta_2 x_2 +\dots+\theta_n x_n

为了简单化函数的表示,我们规定 x0=1x_0 = 1,因此函数中的的参数 θ0\theta_0 就是参数 bais\mathcal{bais}

上面提到的bais\mathcal{bais},它的的作用会在以后的笔记中详细解释。
在计算机中,为了简便计算,我们将数据向量化(vectorize):

h(x)=i=0nθixi=θTx,θRn+1,xRn+1h(\boldsymbol{x}) = \sum^{n}_{i=0} \theta_i x_i = \boldsymbol{\theta}^{\mathit{T}} \boldsymbol{x},\quad \boldsymbol{\theta} \in \mathbb{R}^{n+1}, \boldsymbol{x} \in \mathbb{R}^{n+1}

在周志华的《机器学习》一书中,则将hθ(x)h_{\theta}(\boldsymbol{x}),表示为:

f(x)=wTx+b,wRn,xRn,f(\boldsymbol{x})=\boldsymbol{w}^T\boldsymbol{x}+b,\quad \boldsymbol{w}\in \mathbb{R}^n,\boldsymbol{x}\in \mathbb{R}^n,

其实两个函数是一样的,因为有θ0=b\theta_0 = b。但是在计算机中,第一种向量表示比较方便储存数据,我的笔记也就这么记了。

为了使估计值y^\hat{y}接近于yy,我们定义cost function :

J(θ)=12mm_i=1(h_θ(x(i))y(i))2\mathit{J}(\theta) = \frac{1}{2m}\sum ^{m}\_{i = 1}(h\_{\theta}(x^{(i)})-y^{(i)})^2

有了cost function,我们的目标就是:

θ=arg minJθ(x) \boldsymbol{\theta} = \mathop{\argmin} \limits_{\mathit{J}} {\theta (x)}

求解 θ\theta 的方法

基于均方误差最小化来进行模型求解的方法称为“最小二乘法”。——周志华《机器学习》

上述的 cost function 就是基于了均方误差。最小二乘法就是试图找到一条“线”,使所有样本到直线的欧式距离之和最小。

求解 θ\boldsymbol{\theta} 的方法有两个,一个是梯度下降(gradient descent),一个是通过求导得出极值。

梯度下降(gradient descent)

首先,梯度下降是通过不断更新 θ\theta 的值,而找到最优的情况。对于一个凸函数来说,是让当前的 $\theta $ 往函数下降最快的方向进行移动,以此更新 $\theta $ ,而更新的量,就是函数的导数了。所以,对于某一特征系数有更新公式:

θj:=θjα1mθjJ(θ)\theta_j := \theta_j-\alpha \cdot \frac{1}{m} \cdot \frac{\partial}{\partial\theta_j}\mathit{J}(\theta)

我们从一个样本来看梯度下降,首先对 J(θ)\mathit{J}(\theta)θ\theta 的偏导:

θjJ(θ)=θj12(hθ(x)y)2=212(hθ(x)y)θj(hθ(x)y)=(hθ(x)y)θj(i=0nθixiy)=(hθ(x)y)xj\begin{aligned} \frac{\partial}{\partial\theta_j}\mathit{J}(\theta) &= \frac{\partial}{\partial\theta_j}\frac{1}{2}(h_{\theta}(x)-y)^2\\\\ &=2\cdot\frac{1}{2}(h_{\theta}(x)-y)\cdot \frac{\partial}{\partial\theta_j}(h_{\theta}(x)-y)\\\\ &=(h_{\theta}(x)-y)\cdot \frac{\partial}{\partial\theta_j}(\sum^n_{i=0}\theta_ix_i-y)\\\\ &=(h_{\theta}(x)-y)x_j \end{aligned}

于是,更新公式可写为:

θj:=θjα(hθ(x)y)xj:=θj+α(yhθ(x))xj\begin{aligned} \theta_j &:= \theta_j-\alpha \cdot(h_{\theta}(x)-y)x_j\\\\ &:=\theta_j +\alpha \cdot(y-h_{\theta}(x))x_j \end{aligned}

对于一个训练集,我们就得到:

Repeat until convergence{θj:=θj+α1mm_i=1(y(i)hθ(x(i)))x(i)_j}\begin{aligned} &\text{Repeat until convergence}\{\\ & \quad \quad \theta_j := \theta_j +\alpha \cdot \frac{1}{m} \cdot \sum^{m}\_{i=1}(y^{(i)}-h_{\theta}(x^{(i)}))x^{(i)}\_j\\ &\} \end{aligned}

求导

The "Normal Equation" is a method of finding the optimum theta without iteration.

首先,我们定义一下 XXXX 是一个 m×nm \times n 的矩阵,事实上,考虑截距(θ0\theta_0),矩阵应该为 m×(n+1)m \times (n+1)

我们有:

X=[(x(1))T(x(2))T(x(m))T]X = \left[ \begin{matrix} -(x^{(1)})^T-\\\\ -(x^{(2)})^T- \\\\ \vdots\\\\ -(x^{(m)})^T- \end{matrix} \right]

然后有 y\boldsymbol{y}

y=[y(1)y(2)y(m)],yRm\boldsymbol{y} = \left[ \begin{matrix} y^{(1)}\\\\ y^{(2)}\\\\ \vdots\\\\ y^{(m}) \end{matrix} \right],\boldsymbol{y} \in \mathbb{R}^m

于是有:

J(θ)=12(Xθy)T(Xθy)J(\boldsymbol{\theta}) = \frac{1}{2}(X\boldsymbol{\theta}-\boldsymbol{y})^T(X\boldsymbol{\theta}-\boldsymbol{y})

因此,对 J(θ)\mathit{J}(\theta)θ\theta 的偏导:

θJ(θ)=θ12(Xθy)T(Xθy)=12θ(θTXTXθθTXTyyTXθ+yTy)=12θtr(θTXTXθθTXTyyTXθ+yTy)=12θ(trθTXTXθ2tryTXθ)=12(XTXθ+XTXθ2XTy)=XTXθXTy\begin{aligned} \nabla_{\theta} J(\boldsymbol{\theta}) &= \nabla_{\theta} \frac{1}{2}(X\boldsymbol{\theta}-\boldsymbol{y})^T(X\boldsymbol{\theta}-\boldsymbol{y})\\\\ & = \frac{1}{2}\nabla_{\theta} (\boldsymbol{\theta}^TX^TX\boldsymbol{\theta}-\boldsymbol{\theta}^TX^T\boldsymbol{y}-\boldsymbol{y}^TX\boldsymbol{\theta}+\boldsymbol{y}^T\boldsymbol{y})\\\\ & =\frac{1}{2}\nabla_{\theta} tr (\boldsymbol{\theta}^TX^TX\boldsymbol{\theta}-\boldsymbol{\theta}^TX^T\boldsymbol{y}-\boldsymbol{y}^TX\boldsymbol{\theta}+\boldsymbol{y}^T\boldsymbol{y})\\\\ & = \frac{1}{2}\nabla_{\theta}(tr \boldsymbol{\theta}^TX^TX\boldsymbol{\theta} - 2 tr \boldsymbol{y}^TX\boldsymbol{\theta})\\\\ &=\frac{1}{2} (X^TX\boldsymbol{\theta}+X^TX\boldsymbol{\theta}-2X^T\boldsymbol{y})\\\\ &=X^TX\boldsymbol{\theta}-X^T\boldsymbol{y} \end{aligned}

当对 θ\theta 的偏导为 00 时,可得极值,得:

XTXθ=XTyX^TX\boldsymbol{\theta} = X^T\boldsymbol{y}

得到最优 θ\theta 解 :

θ=(XTX)1XTy\boldsymbol{\theta} = (X^TX)^{-1}X^T\boldsymbol{y}

概率解释(Probabilistic Interpretation)

简单说明

在对数据进行概率假设的基础上,最小二乘回归得到的 θ\theta 和最大似然法估计的 θ\theta 是一致的。所以这是一系列的假设,其前提是认为最小二乘回归(least-squares regression)能够被判定为一种非常自然的方法,这种方法正好就进行了最大似然估计(maximum likelihood estimation)。

证明

首先假设目标变量与输入变量存在以下等量关系:

y(i)=θTx+ε(i)\boldsymbol{y}^{(i)} = \boldsymbol{\theta}^T\boldsymbol{x}+ \boldsymbol{\varepsilon}^{(i)}

上式的 ε(i)\boldsymbol{\varepsilon}^{(i)} 是误差项,用于存放由于建模所忽略的变量导致的效果 (比如可能某些特征对于房价的影响很明显,但我们做回归的时候忽略掉了)或者随机的噪音信息(random noise)。进一步假设 ε(i)\boldsymbol{\varepsilon}^{(i)} 是独立同分布的 (IID ,independently and identically distributed) ,服从高斯分布(Gaussian distribution),其平均值为 00,方差(variance)为 σ2\sigma^2。这样就可以把这个假设写成 ε(i)N(0,σ2)\boldsymbol{\varepsilon}^{(i)} \sim \mathcal{N}(0,\sigma^2)。然后 ε(i)\boldsymbol{\varepsilon}^{(i)} 的密度函数就是:

p(ε(i))=12πσexp((ε(i))22σ2)p( \boldsymbol{\varepsilon}^{(i)} ) = \frac{1}{\sqrt{2\pi}\sigma}\mathrm{exp}(-\frac{(\varepsilon^{(i)})^2}{2\sigma^2})

这意味着存在下面的等量关系:

p(y(i)x(i);θ)=12πσexp((y(i)θTx(i))22σ2)p(\boldsymbol{y}^{(i)}|\boldsymbol{x}^{(i)};\boldsymbol{\theta }) = \frac{1}{\sqrt{2\pi}\sigma}\mathrm{exp}(-\frac{(y^{(i)}-\boldsymbol{\theta}^T\boldsymbol{x}^{(i)})^2}{2\sigma^2})

上式为,在 θ\theta 取某个固定值的情况下,这个等式表达为,在 x(i)\boldsymbol{x}^{(i)} 的情况下发生 y(i)\boldsymbol{y}^{(i)} 的概率, 通常可以看做是一个 y(i)\boldsymbol{y}^{(i)} 的函数。当我们要把它当做 θ\theta 的函数的时候,就称它为似然函数(likelihood function)在整个数据集下有:

L(θ)=L(θ;X,y)=p(yX;θ)L(\boldsymbol{\theta}) = L(\boldsymbol{\theta};X,\boldsymbol{y}) = p(\boldsymbol{y}|X;\boldsymbol{\theta })

结合之前对 ε(i)\boldsymbol{\varepsilon}^{(i)} 的独立性假设(这里对 y(i)\boldsymbol{y}^{(i)} 以及给定的 x(i)\boldsymbol{x}^{(i)} 也都做同样假设),就可以把上面这个等式改写成下面的形式:

L(θ)=i=1m(y(i)x(i);θ)=i=1m12πσexp((y(i)θTx(i))22σ2)\begin{aligned} L(\boldsymbol{\theta}) &= \prod^m_{i=1}(\boldsymbol{y}^{(i)}|\boldsymbol{x}^{(i)};\boldsymbol{\theta }) \\\\ &= \prod^m_{i=1} \frac{1}{\sqrt{2\pi}\sigma}\mathrm{exp}(-\frac{(y^{(i)}-\boldsymbol{\theta}^T\boldsymbol{x}^{(i)})^2}{2\sigma^2}) \end{aligned}

最大似然法(maximum likelihood)告诉我们要选择能让数据的似然函数尽可能大的 θ\theta 。也就是说,找到 θ\theta 能够让函数 L(θ)L(\boldsymbol{\theta}) 取到最大值。

为了找到 L(θ)L(\boldsymbol{\theta}) 的最大值,我们不能直接使用 L(θ)L(\boldsymbol{\theta}) ,而要使用严格递增的 L(θ)L(\boldsymbol{\theta}) 的函数求最大值。使用对数函数来找对数函数 L(θ)L(\boldsymbol{\theta}) 的最大值是一种方法,而且求导来说就简单了一些:

v=logL(θ)=logi=1m12πσexp((y(i)θTx(i))22σ2)=i=1mlogi=1m12πσexp((y(i)θTx(i))22σ2)=mlog12πσ1σ2i=1m(y(i)θTx(i))2\begin{aligned} v& = \log{L(\boldsymbol{\theta})}\\ &=\log{ \prod^m_{i=1} \frac{1}{\sqrt{2\pi}\sigma}\mathrm{exp}(-\frac{(y^{(i)}-\boldsymbol{\theta}^T\boldsymbol{x}^{(i)})^2}{2\sigma^2})}\\ &=\sum^m_{i=1}\log{ \prod^m_{i=1} \frac{1}{\sqrt{2\pi}\sigma}\mathrm{exp}(-\frac{(y^{(i)}-\boldsymbol{\theta}^T\boldsymbol{x}^{(i)})^2}{2\sigma^2})}\\ &=m\log{ \frac{1}{\sqrt{2\pi}\sigma} -\frac{1}{\sigma^2} \cdot \sum^m_{i=1}(y^{(i)}-\boldsymbol{\theta}^T\boldsymbol{x}^{(i)})^2} \end{aligned}

对于上式 ,由于mlog12πσm\log{\frac{1}{\sqrt{2\pi}\sigma}}1σ2\frac{1}{\sigma^2} 值不变,那么 L(θ)\mathscr{L}(\boldsymbol{\theta}) 取最大,即求下面的式子最小:

12i=1m(y(i)θTx(i))2\frac{1}{2}\sum^m_{i=1}(y^{(i)}-\boldsymbol{\theta}^T\boldsymbol{x}^{(i)})^2

证毕。

多项式回归(Polynomial Regession)

多项式回归可以用来拟合二次、三次、高次模型,通过使用 x2,x\boldsymbol{x}^2,\sqrt{\boldsymbol{x}} 等进行拟合。

这样便将高阶方程模型转换成线性回归模型。这也算是 特征缩放(Features Scaling) 的一种。