线性回归

给定数据集 $\{ ({x_1},{y_1}),({x_2},{y_2}), \cdots ,({x_m},{y_m})\}$ ，其中 $x_i=(x_{i1};x_{i2};\cdots;x_{id})$ , $y_i\in R.$ 线性回归试(linear regression)图学得一个线性模型以尽可能的准确的预测实值输出标记。

这里x(i)表示数据集中第i个样本，该样本总共有d个特征。

1.单变量线性回归

由于是单变量，输入的样本特征只有一个，此时我们忽略关于样本特征的下表，即 $D = \{ ({x_i},{y_i})\} _{i = 1}^m$ ，其中 ${x_i} \in R$ 。对于离散属性，若特征值间存在“序”(order)关系，可通过连续化将其转化为连续值。
线性回归试图学得
$f({x_i}) = w{x_i} + b,使得f({x_i}) \simeq {y_i}$
确定w与b的值，关键在于如何衡量 $f (x)$ 与 $y$ 之间的差异，而均方误差则是回归任务中最常用的性能度量，因此需要让均方误差最小化，即 $w$ 与 $b$ 的解 ${w^*}与{b^*}$ 为
$({w^*},{b^*}) = \mathop {\arg \min }\limits_{(w,b)} \sum\limits_{i = 1}^m {{{(f({x_i}) - {y_i})}^2}}$
$({w^*},{b^*}) = \mathop {\arg \min }\limits_{(w,b)} \sum\limits_{i = 1}^m {{{({y_i} - w{x_i} - b)}^2}}$

均方误差的几何意义对应于欧几里得距离即“欧氏距离”，而基于均方误差最小化来进行模型求解的方法则是“最小二乘法”，“最小二乘法”实质上就是找到一条直线，使所有样本数据到该直线的欧式距离之和最小，即误差最小。
求解 $w$ 与 $b$ 是使代价函数 $=\frac{1}{2} \sum\limits_{i = 1}^m {{{({y_i} - w{x_i} - b)}^2}}$ 最小化的过程， ${J{(w,b)}}$ 是关于 $w$ 和 $b$ 的凸函数，当它关于 $w$ 和 $b$ 的导数均为0时，得到 $w$ 和 $b$ 的最优解。得到
$\frac{{\partial {J{(w,b)}}}}{{\partial w}} = w\sum\limits_{i = 1}^m {{x_i}^2 - } \sum\limits_{i = 1}^m {({y_i} - b){x_i}}$
$\frac{{\partial {J{(w,b)}}}}{{\partial b}} = \sum\limits_{i = 1}^m b - \sum\limits_{i = 1}^m {{y_i} + \sum\limits_{i = 1}^m {w{x_i}} }= mb - \sum\limits_{i = 1}^m {({y_i} - w{x_i}} )$
然后令 $\frac{{\partial {J{(w,b)}}}}{{\partial w}}$ 和 $\frac{{\partial {J{(w,b)}}}}{{\partial b}}$ 等于0可以得到 $w$ 和 $b$ 最优解
$\frac{{\sum\limits_{i = 1}^m {{y_i}({x_i} - \overline x )} }}{{\sum\limits_{i = 1}^m {x_i^2} - \frac{1}{m}{{(\sum\limits_{i = 1}^m {{x_i}} )}^2}}}(注：\overline x = \frac{1}{m}\sum\limits_{i = 1}^m {{x_i}} )$
$\frac{1}{m}\sum\limits_{i = 1}^m {({y_i} - w{x_i})}$

2.推广到一般情形——多元线性回归

例如文章开头的线性回归描述，数据集 $\{ ({x_1},{y_1}),({x_2},{y_2}), \cdots ,({x_m},{y_m})\}$ ，其中 $x_i=(x_{i1};x_{i2};\cdots;x_{id})$ , $y_i\in R.$ ，样本由 $d$ 个特征，此时我们试图学得
$f({x_i}) = w{x_i} + b,使得f({x_i}) \simeq {y_i}$
这称为“多元线性回归”。
同样可以利用最小二乘法来对 $w$ 和 $b$ 进行估计，为方便运算，令 $\hat w = (w;b)$ ， $\hat w$ 是 $(d+1)\times1$ 的矩阵，则数据集 $D$ 可以表示为一个 $\times (d + 1)$ 的矩阵 $X$ ，每一行代表每一个样本，每列的 $d$ 个元素代表 $d$ 个特征，最后一列全为1，即
$\begin{pmatrix} {{x_{11}}} & {{x_{12}}} & \cdots & {{x_{1d}}} & 1 \\ {{x_{21}}} & {{x_{22}}} & \cdots & {{x_{2d}}} & 1 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ {{x_{m1}}} & {{x_{m2}}} & \cdots & {{x_{md}}} & 1 \\ \end{pmatrix} = \begin{pmatrix} {x_1^T} & 1 \\ {x_2^T} & 1 \\ \vdots & \vdots \\ {x_m^T} & 1 \\ \end{pmatrix}$
则 $({y_1};{y_2}; \cdots ;{y_m})$
同样求 $\hat w$ 的解 ${\hat w^*}$ 可表示为
${\hat w^*} = \mathop {\arg \min }\limits_{\hat w} {(y - X\hat w)^T}(y - X\hat w)$
令 $J(\hat w) = {(y - X\hat w)^T}(y - X\hat w)$ ，然后对 $\hat w$ 求导得：
$\frac{{\partial J(\hat w)}}{{\partial \hat w}} = 2{X^T}(X\hat w - y)$

注：常用的矩阵求导公式

$\frac{{\partial AB}}{{\partial B}} = {A^T}$ $\frac{{\partial {A^T}B}}{{\partial A}} = B$ $\frac{{\partial {X^T}AX}}{{\partial X}} = 2AX$

当 $\frac{{\partial J(\hat w)}}{{\partial \hat w}}$ 为0可得 $\hat w$ 的最优解，当 ${X^T}X$ 为满秩矩阵或正定矩阵时，可得 ${\hat w^*} = {({X^T}X)^{ - 1}}{X^T}y$
令 $\hat x = ({x_i};1)$ 最终学得的多元线性回归模型为 $f({x_i}) = x_i^T{({X^T}X)^{ - 1}}{X^T}y$

梯度下降算法

1.选择梯度下降算法而不是直接求导等于0的理由

为什么计算损失函数最优值采用梯度下降算法而不是直接求导等于0？
1、 ${X^T}X$ 必须要可逆，也就是 $X$ 必须可逆，但是现实任务中 ${X^T}X$ 往往不是满秩矩阵。例如在许多任务中我们会遇到样本包含大量的特征，其数目甚至超过样本数目，导致 $X$ 的列数多于行数， ${X^T}X$ 显然不是满秩，因此直接求导不可行；
2、假设满足了条件一，那么就需要去求 $X$ 的转置乘以 $X$ 这个整体的逆，线性代数中给出了求逆矩阵的方法，是非常复杂的(对计算机来说就是十分消耗性能的)，数据量小时，还可行，一旦数据量大，计算机求矩阵的逆将会是一项非常艰巨的任务，消耗的性能以及时间巨大，而在机器学习中，数据量少者上千，多者上亿；因此直接求导不可行。
相较而言，梯度下降算法同样能够实现最优化求解，通过多次迭代使得代价函数收敛，并且使用梯度下降的计算成本很低，所以基于以上两个原因，回归中多数采用梯度下降而不是求导等于零。

2.梯度的概念

梯度是微积分中一个很重要的概念
1）在单变量的函数中，梯度其实就是函数的微分，代表着函数在某个给定点的切线的斜率
2）在多变量函数中，梯度是一个向量，向量有方向，梯度的方向就指出了函数在给定点的上升最快的方向

3.场景假设

在这里插入图片描述
想象一下你正站立在山的这一点上，站立在你想象的公园这座红色山上，在梯度下降算法中，我们要做的就是旋转360度，看看我们的周围，并问自己要在某个方向上，用小碎步尽快下山。这些小碎步需要朝什么方向？如果我们站在山坡上的这一点，你看一下周围，你会发现最佳的下山方向，你再看看周围，然后再一次想想，我应该从什么方向迈着小碎步下山？然后你按照自己的判断又迈出一步，重复上面的步骤，从这个新的点，你环顾四周，并决定从什么方向将会最快下山，然后又迈进了一小步，并依此类推，直到你接近局部最低点的位置。

4.学习率

学习率即为每次更新迭代参数的步长，通常我们学习率使用 $\alpha$ 来表示。
如果 $\alpha$ 太小了，即我的学习速率太小，结果就是只能这样像小宝宝一样一点点地挪动，去努力接近最低点，这样就需要很多步才能到达最低点，所以如果太小的话，可能会很慢，因为它会一点点挪动，它会需要很多步才能到达全局最低点。
如果 $\alpha$ 太大，那么梯度下降法可能会越过最低点，甚至可能无法收敛，下一次迭代又移动了一大步，越过一次，又越过一次，一次次越过最低点，直到你发现实际上离最低点越来越远，所以，如果太大，它会导致无法收敛，甚至发散。

5.单变量梯度下降

为方便描述，这里令预测的函数模型为 $f({x_i}) = {\theta _0} + {\theta _1}x$
代价函数为
$J({\theta _0},{\theta _1}) = \frac{1}{{2m}}\sum\limits_{i = 1}^m {{{(f({x^{_(i)}}) - {y^{_(i)}})}^2}}$

注：跟之前的式子比，这里 ${\theta _0}$ = $b$ , ${\theta _1}$ = $w$ .这里的系数 $\frac{1}{{2m}}$ 对结果没有影响。

（1）单变量梯度下降公式

repeat until convergence{
${\theta _j} = {\theta _j} - \alpha \frac{{\partial J({\theta _0},{\theta _1})}}{{\partial {\theta _j}}}$ (for j=0 and j=1)
}
注:需要同步跟新两个变量
${\theta _0} - \alpha \frac{{\partial J({\theta _0},{\theta _1})}}{{\partial {\theta _0}}}$
${\theta _1} - \alpha \frac{{\partial J({\theta _0},{\theta _1})}}{{\partial {\theta _1}}}$
${\theta _0}: = temp0$
${\theta _1}: = temp1$

（2）单变量梯度下降实例

我们假设有一个单变量的函数： $J(\theta ) = {\theta ^2}$
函数的微分： $J'(\theta ) = 2\theta$
初始化，起点可以随意设置，这里设置为为： ${\theta ^0}{\text{ = }}1$
学习率： $\alpha {\text{ = }}0.4$
我们开始进行梯度下降的迭代计算过程:
${\theta ^0}{\text{ = }}1$
$\begin{aligned} {\theta ^1}&= {\theta ^0} - \alpha J'({\theta ^0}) \\ &= 1 - 0.4*2 \\ &= 0.2 \\ \end{aligned}$
$\begin{aligned} {\theta ^2}& ={\theta ^1} - \alpha J'({\theta ^1}) \\ & = 0.2 - 0.4*0.4 \\ & = 0.04 \\ \end{aligned}$
${\theta ^3} = 0.008$
${\theta ^4} = 0.0016$
这个实例显然最优解为0，经过4次迭代，已经非常接近最优解了。
在这里插入图片描述

6.多变量梯度下降

支持多变量的假设 $f$ 表示为 $f({x_i}) = {\theta _0} + {\theta _1}{x_1} + {\theta _2}{x_2} + \cdots + {\theta _n}{x_n}$
这个公式中有个参数和个变量，为了使得公式能够简化一些，引入，则公式转化为： $f({x_i}) = {\theta _0}{x_0} + {\theta _1}{x_1} + {\theta _2}{x_2} + \cdots + {\theta _n}{x_n}$
此时模型中的 $\theta$ 参数是一个 $n + 1$ 维的向量，任何一个训练实例也都是 $n + 1$ 维的向量，特征矩阵 $X$ 的维度是 $m\times(n+1)$ 。因此公式可以简化为： $f({x_i}) = {\theta ^T}X$ .
与单变量线性回归类似，在多变量线性回归中，我们也构建一个代价函数，则这个代价函数是所有建模误差的平方和，即： $J({\theta _0},{\theta _1}, \cdots ,{\theta _n}) = \frac{1}{{2m}}\sum\limits_{i = 1}^m {{{(f({x_i}) - {y_i})}^2}}$

（1）多变量梯度下降公式

Repeat{
$\begin{aligned} {\theta _j} &= {\theta _j} - \alpha \frac{{\partial J({\theta _0},{\theta _1}, \cdots ,{\theta _n})}}{{\partial {\theta _j}}} \\ & = {\theta _j} - \alpha \frac{\partial }{{\partial {\theta _j}}}\frac{1}{{2m}}\sum\limits_{i = 1}^m {{{(f({x^{_(i)}}) - {y^{_(i)}})}^2}} \\ & = {\theta _j} - \alpha \frac{1}{m}\sum\limits_{i = 1}^m {((f({x^{_(i)}}) - {y^{_(i)}})} {x_{_j}^{(i)}}) \\ \end{aligned}$
(simultaneity update ${\theta _j}$ for $j = 0, 1, 2, . . ., n$ )
}

（2）多变量梯度下降实例

我们假设有一个目标函数:
$j({\theta _1},{\theta _2}) = \theta _1^2{\text{ + }}\theta _2^2$
显然这个简单的函数最优解取在(0,0)点，但是这次我们用梯度算法，一步步求出最优解。
我们假设初始的起点为： ${\theta ^0}{\text{ = (1,3)}}$
初始的学习率为： $\alpha = 0.1$
函数的梯度为： $\Delta J({\theta _1},{\theta _2}) = < 2{\theta _1},2{\theta _2} >$
进行多次迭代：
$\begin{aligned} & {\theta ^0}{\text{ = (1,3)}} \\ & {\theta ^1} = {\theta ^0} - \alpha \Delta J({\theta _1},{\theta _2}) = {\text{(1,3)}} - 0.1*(2,6) = (0.8,2.4) \\ & {\theta ^2} = (0.8,2.4) - 0.1*(1.6,4.8) = (0.64,1.92) \\ & {\theta ^3} = (0.5124,1.536) \\ & {\theta ^4} = (0.4096,1.228800000000001) \\ & \vdots \\ & {\theta ^{10}} = (0.1073741824000003,0.32212254720000005) \\ & \vdots \\ & {\theta ^{50}} = (1.141798154164342{e^{ - 05}},3.42539442494306{e^{ - 05}}) \\ \end{aligned}$
显然已经非常接近最优解点
在这里插入图片描述
梯度下降算法与正规方程（直接计算导数等于0）的比较

梯度下降	正规方程
需要选择学习率 $\alpha$	不需要
需要多次迭代	一次运算得出
当特征数量 $n$ 大时也能较好适用	需要计算 ${X^T}X$ 如果特征数量 $n$ 较大则运算代价大，因为矩阵逆的计算时间复杂度为 $O({n^3})$ ，通常来说当 $n$ 小于10000 时还是可以接受的
适用于各种类型的模型	只适用于线性模型，不适合逻辑回归模型等其他模型