线性回归与梯度下降

前提

m行数据，n列特征

数学模型

$h_θ(x) = Σ_{j=0}^{n}θ_jX_j$ （ $X_0=1$ ）

目标函数

$J(θ) = \frac12Σ_{i=1}^{m}(h_θ(x^{(i)}) - y^{(i)})^2$

任务

寻找 $θ$ 使 $J(θ)$ 最小

方法

方法一、梯度下降（Gradient Descent，GD）

1.批量梯度下降（Batch Gradient Descent，BGD）

批量梯度下降法是最原始的形式，它是指在每一次迭代时使用所有样本来进行梯度的更新。
梯度下降更新规则：
$\theta_j := \theta_j - \alpha \frac{\partial^{}J(θ)}{\partialθ_j}$ $(0\leqslant j \leqslant n)$
方便起见，假设只有一个样本的情况下(m=1)，将 $J(θ) = \frac12\sum_{i=1}^{m}(h_θ(x^{(i)}) - y^{(i)})^2$ 代入
$\begin{align*} \frac{\partial^{}J(θ)}{\partialθ_j} &= \frac{\partial^{}}{\partialθ_j}\frac12(h_θ(x)-y)^2\\ &= (h_θ(x)-y) * \frac{\partial^{}}{\partialθ_j}(θ_0x_0+θ_1x_1+...+θ_nx_n-y)\\ &= (h_θ(x)-y) * x_j \end{align*}$
再将上式代入梯度下降更新规则：
$\theta_j := \theta_j - \alpha(h_θ(x)-y) * x_j$ （1个样本） $(0\leqslant j \leqslant n)$
映射到m个样本，只需要在相应的地方加上上标i：
$\theta_j := \theta_j - \alpha\sum_{i=1}^{m}(h_θ(x^{(i)})-y^{(i)}) * x_j^{(i)}$ （m个样本） $(0\leqslant j \leqslant n)$

于是得到梯度下降更新伪代码：
repeat{
$\theta_j := \theta_j - \alpha\sum_{i=1}^{m}(h_θ(x^{(i)})-y^{(i)}) * x_j^{(i)}$ $(0\leqslant j \leqslant n)$
}
优点：
（1）一次迭代是对所有样本进行计算，此时利用矩阵进行操作，实现了并行。
（2）由全数据集确定的方向能够更好地代表样本总体，从而更准确地朝向极值所在的方向。当目标函数为凸函数时，BGD一定能够得到全局最优。
缺点：
（1）当样本数目 m 很大时，每迭代一步都需要对所有样本计算，训练过程会很慢。

2.随机梯度下降（Stochastic Gradient Descent，SGD）

随机梯度下降是每次迭代使用一个样本来对参数进行更新。使得训练速度加快。

伪代码形式：
repeat{
for i=1,...,m{
$\theta_j := \theta_j -\alpha (h_{\theta}(x{(i)})-y{(i)})x_j^{(i)}$
(for j =0,1)
}
}

优点：
（1）由于不是在全部训练数据上的损失函数，而是在每轮迭代中，随机优化某一条训练数据上的损失函数，这样每一轮参数的更新速度大大加快。
缺点：
（1）准确度下降。由于即使在目标函数为强凸函数的情况下，SGD仍旧无法做到线性收敛。
（2）可能会收敛到局部最优，由于单个样本并不能代表全体样本的趋势。
（3）不易于并行实现。

3.小批量梯度下降（Mini-Batch Gradient Descent, MBGD）

小批量梯度下降，是对批量梯度下降以及随机梯度下降的一个折中办法。其思想是：每次迭代使用 batch_size 个样本来对参数进行更新。
这里我们假设 batchsize=10 ，样本数 m=1000 。

伪代码形式：
repeat{
for i=1,11,21,31,...,991{
$\theta_j := \theta_j - \alpha \frac{1}{10} \sum_{k=i}{(i+9)}(h_{\theta}(x{(k)})-y{(k)})x_j{(k)}$
(for j =0,1)
}
}

优点：
（1）通过矩阵运算，每次在一个batch上优化神经网络参数并不会比单个数据慢太多。
（2）每次使用一个batch可以大大减小收敛所需要的迭代次数，同时可以使收敛到的结果更加接近梯度下降的效果。
（3）可实现并行化。
缺点：
（1）batch_size的不当选择可能会带来一些问题。

总结

下图显示了三种梯度下降算法的收敛过程：

image.png

目前小批量最为常用，而由于现如今数据量较大，批量梯度下降几乎很少使用。

方法二、正规方程（Normal Equation）

此方法仅适用于线性回归。梯度下降是迭代解法，而正规方程是解析解法，只需一步即可计算得出θ。
公式为：
$θ=(X^TX)^{-1}X^Ty$

推导：
$h_θ(x) = Σ_{j=0}^{n}θ_jX_j（X_0=1）$
$J(θ) = \frac12Σ_{i=1}^{m}(h_θ(x^{(i)}) - y^{(i)})^2$
将x、θ、y都写成向量形式后
$\begin{align*} J(θ) &= \frac12(Xθ-y)^T(Xθ-y)\\ &=\frac12(θ^TX^T-y^T)(Xθ-y)\\ &=\frac12(θ^TX^TXθ-θ^TX^Ty-y^TXθ+y^Ty)\\ \end{align*}$
求一个函数的极值需要对其求导， $J(θ)$ 对 $θ$ 求导得：
$\begin{align*} \frac{\partial^{}J(θ)}{\partialθ_j} &= \frac12(2X^TXθ-2X^Ty)= 0\\ X^TXθ - X^Ty&=0\\ θ &= (X^TX)^{-1}X^Ty\\ \end{align*}$

公式适用条件：
X可逆
若X不可逆，说明特征线性相关，可以观察数据集寻找多余特征并去除。

引用及参考：
[1] https://www.cnblogs.com/lliuye/p/9451903.html
[2] https://www.cnblogs.com/maybe2030/p/5089753.html
[3] https://zhuanlan.zhihu.com/p/37714263
[4] https://zhuanlan.zhihu.com/p/30891055
[5] https://www.zhihu.com/question/40892922/answer/231600231