logo

线性回归

在大学里,学生每周的学习时间和期末考试成绩有一定的相关性.
我们调查了一些同学每周的学习时间和期末考试成绩,画成如下这幅图,图中每一个点代表一名同学.

image

对于此类问题,如果我们能够找到一个方程来描述数据的分布规律,那么我们就可以根据这个方程来判断某同学的学习成绩了.我们假设有这样的一个线性方程:

h_\theta(x) = \theta_0 + \theta x

由于数据的特征可能很多,比如说影响学习成绩的因素不止有学习时间,还有环境,家庭情况,经济情况等等.所以线性方程会有多个变量:

h_\theta(x) = \theta_0 + \theta_1x_1 + \theta_2x_2 + \theta_3x_3 + ...

第一个参数 \theta_0 相当于 \theta_0x_0 ,并且 x_0 = 1 ,所以有

h(x) = \sum_{i=1}^n \theta_ix_i = \theta^Tx

这里的n为特征数.

数据分析中经常用均方根误差RMSD(root-mean-square deviation)来衡量模型的好坏,其实就是标准差:
RMSD ={\sqrt {\frac {\sum _{t=1}^{n}({\hat {y}}_{t}-y_{t})^{2}}{n}}}

有时候,比如kaggle,会使用对数的RMSD作为评估结果.

我们在训练的过程中一般使用方差来评定模型的好坏:
J(\theta) = \frac{1}{2m} \sum_{i=1}^m (h_\theta(x_i) - y_i)^2

这里的m为训练样本数. J(\theta) 叫做代价函数,代价函数越小方程越优.

正规化方程

为了方便推导把训练样本与标记写成大矩阵的形式,训练样本为:

X = \begin{bmatrix} (x^{(1)})^T\\ (x^{(2)})^T\\ ...\\ (x^{(m)})^T \end{bmatrix}

标记为:
\vec{y} = \begin{bmatrix} y^{(1)}\\ y^{(2)}\\ ...\\ y^{(m)} \end{bmatrix}

根据 h(x) = \theta^Tx 可以得到:

X\theta - \vec{y} = \begin{bmatrix} h_\theta(x^{(1)}) - y^{(1)}\\ h_\theta(x^{(2)}) - y^{(2)}\\ ...\\ h_\theta(x^{(m)}) - y^{(m)} \end{bmatrix}

所以:

J(\theta) = \frac{1}{2m}\sum_{i=1}^m (h_\theta(x_i) - y_i)^2 = \frac{1}{2m}(X\theta - \vec{y})^T(X\theta - \vec{y})

对代价函数求导:

\begin{equation} \begin{split} \Delta_{\theta}J(\theta) &= \Delta_{\theta}\frac{1}{2}(X\theta - \vec{y})^T(X\theta - \vec{y}) \\ &= \frac{1}{2m}\Delta_{\theta}(\theta^T X^TX\theta-\theta^T X^T\vec{y} - \vec{y}^TX\theta + \vec{y}^T\vec{y}) \\ &= \frac{1}{2m}\Delta_{\theta}tr(\theta^T X^TX\theta-\theta^T X^T\vec{y} - \vec{y}^TX\theta + \vec{y}^T\vec{y}) \\ &= \frac{1}{2m}\Delta_{\theta}(tr\theta^T X^TX\theta - 2tr\vec{y}^TX\theta) \\ &= \frac{1}{2m}(X^TX\theta + X^TX\theta - 2X^T\vec{y}) \\ &= \frac{1}{m}(X^TX\theta - X^T\vec{y}) \end{split} \end{equation}

上述求导过程使用了如下公式,而下面公式是由矩阵迹的性质,得到的:
\Delta_{A^T}trABA^TC = B^TA^TC^T + BA^TC

代价函数极值点导数为0,即 \Delta_{\theta}J(\theta) = 0 ,即:

X^TX\theta - X^T\vec{y} = 0 可得

\theta = (X^TX)^{-1}X^T\vec{y}

正规化方程的优缺点

正规化方程真的非常简单,但是正规化方程还是有缺点的.在正则化方程中 (X^TX)^{-1} 的复杂度为 O(n^3) .

当特征数n比较大的时候,比如n为10000的时候X会使一个10000*10000的矩阵,这时计算 (X^TX)^{-1} 的速度回明显变慢.

所以当特征数大于10000的时候我们通常会选择梯度下降.

梯度下降的复杂度为 O(kn^2) 可以解决效率问题.不过相对正规化方程梯度下降要复杂一些:

首先梯度下降需要进行归一化操作,其次需要考虑考虑学习率等参数,再次梯度下降是通过迭代无限逼近极值的,而正规化方程是直接求得准确的极值点.

梯度下降

我们把代价函数画出来,可能是这样的:

image

调整 \theta 来让代价函数最小的过程,相当于图中找最低点的过程.

需要注意的是,由于初始值的不同,我们找到的局部最低点可能是不同的.

image

这很像一个人在一座山峰上,每次只走一小步,那么他如何能以最快的速度下山呢?一定是沿着最陡峭的方向走,这样下山的速度是最快的.

最小化代价函数也是同样的道理,我们需要沿着最陡峭的方向优化,也就是梯度(斜率)最大的方向,而梯度就是函数的导数.

事实上对于线性规划问题并没有上面图中那样复杂到有多个局部最低点,我们可以通过证明 J(\theta) 是一个凸函数来证明 J(\theta) 只有一个局部最小值.

因为 J(\theta) 相当于很多平方和,所以写为:
J(\theta) = \Delta^2_1 + \Delta^2_2 +\Delta^2_3 +...

\Delta^2 显然为凸函数,又由于凸函数加凸函数等于凸函数.所以 J(\theta) 为凸函数,所以它的图像应该类似下面这个样子.

image

我们按照梯度的大小对 \theta 进行调整,梯度大的调整的幅度大,梯度小的调整的幅度小,这样代价函数会朝着梯度最大的方向最小化.

\theta_j := \theta_j - \alpha\frac{\partial}{\partial\theta_j}J(\theta)

其中:=的意思是用右边的值更新左边的值,相当于代码中的赋值. \alpha 是学习率,每次学习的幅度,它可以调整学习的快慢.

将 \alpha\frac{\partial}{\partial\theta_j}J(\theta) 展开:

\begin{equation} \begin{split} \frac{\partial}{\partial\theta_j}J(\theta) &= \frac{1}{2}\cdot\frac{\partial}{\partial\theta_j}(h_\theta(x) - y)^2 \\ &= 2\cdot\frac{1}{2}\cdot(h_\theta(x) - y)\frac{\partial}{\partial\theta_j}(h_\theta(x) - y) \\ &= (h_\theta(x) - y)\frac{\partial}{\partial\theta_j}(\sum_{i=1}^n \theta_ix_i - y) \\ &= (h_\theta(x) - y)x_j \end{split} \end{equation}

以上是使用一个训练样本,推广到多个训练样本:
\theta_j := \theta_j - \frac{\alpha}{m}\sum_{i=1}^m(h_\theta(x^{(i)}) - y^{(i)})x_j

这里我们可以使用矩阵相乘一次性计算出所有的 \theta

\theta := \theta - \frac{\alpha}{m} X^{T} (g(X \theta ) - \vec{y})

以上的算法叫做批梯度下降.

随机梯度下降

批梯度下降非常有效,被广泛使用,但数据量比较大的时候,批梯度下降每一次迭代都需要循环所有的训练样本,造成收敛速度缓慢.

为了解决这个问题,我们每次只对j个数据求和,这j个数据是随机选取的

\begin{align*} & Repeat \; \lbrace \\ & \; \theta_j := \theta_j - \alpha(h_\theta(x^{(i)}) - y^{(i)}) x_j^{(i)} \\ & \rbrace \end{align*}

这种方法叫做随机梯度下降.它的速度非常快.

随机梯度下降有可能梯度下降不是每次都朝着梯度最大的方向进行的,但是总体是向着梯度方向.而且有可能会在最低点附近徘徊,而不是在最低点停止.

image

从概率的角度理解迭代

现在我们换一个思路,看看从概率的角度如何理解线性回归的迭代过程.

模型依然是
y = \theta^Tx

假设模型的误差 \varepsilon 服从呈高斯分布,即

p(\varepsilon)={\frac {1}{\sigma {\sqrt {2\pi }}}}\,\exp \left(-{\frac {(\varepsilon)^{2}}{2\sigma ^{2}}}\right)

那么使用模型预测数据正确的概率为:
p(y^{(i)}|x^{(i)};\theta)={\frac {1}{\sigma {\sqrt {2\pi }}}}\,\exp \left(-{\frac {(y^{(i)} -\theta^Tx^{(i)})^{2}}{2\sigma ^{2}}}\right)

根据最大似然法的思想,如果模型足够好,则要使已知的数据的概率足够高,所以:
L(\theta) = \prod_{i=1}^m p(y^{(i)}|x^{(i)};\theta) = \prod_{i=1}^m {\frac {1}{\sigma {\sqrt {2\pi }}}}\,\exp \left(-{\frac {(y^{(i)} -\theta^Tx^{(i)})^{2}}{2\sigma ^{2}}}\right)

为了方便计算,我们对 L(\theta) 取对数,这并不影响结果:

\begin{equation} \begin{split} l(\theta) &= log \; L(\theta) \\ &= log\prod_{i=1}^m {\frac {1}{\sigma {\sqrt {2\pi }}}}\,\exp \left(-{\frac {(y^{(i)} -\theta^Tx^{(i)})^{2}}{2\sigma ^{2}}}\right) \\ &= \sum_{i=1}^m log{\frac {1}{\sigma {\sqrt {2\pi }}}}\,\exp \left(-{\frac {(y^{(i)} -\theta^Tx^{(i)})^{2}}{2\sigma ^{2}}}\right) \\ &= m \; log\frac {1}{\sigma {\sqrt {2\pi }}} - \frac {1}{\sigma^2} \cdot \frac{1}{2} \sum_{i=1}^m (y^{(i)} -\theta^Tx^{(i)})^2 \end{split} \end{equation}

此时我们最大化 l(\theta) 相当于最小化:

\frac{1}{2} \sum_{i=1}^m (y^{(i)} -\theta^Tx^{(i)})^2

这正是我们的代价函数 J(\theta)

编程实现:
https://www.kaggle.com/swimmingwhale/linear-regression

参考:
https://www.coursera.org/learn/machine-learning
http://cs229.stanford.edu/

posted @ 2018-07-09 20:33:21
评论加载中...
发表评论