在机器学习中，回归和分类是两种常见的问题，回归预测的是连续型数据，分类预测的是离散型数据

线性回归

线性回归模型

线性回归是利用线性回归方程对一个或多个自变量与因变量进行建模的回归分析，预测结果是一个或多个自变量的线性组合

• 一元线性回归：只有一个自变量
• 多元线性回归：有多个自变量

输入数据集：

\[D={ (\pmb{x}^{(1)},y^{(1)}),(\pmb{x}^{(2)},y^{(2)}),...,(\pmb{x}^{(m)},y^{(m)}) } \]

其中m表示输入数据集的大小，x⁽ⁱ⁾表示一组输入数据：

\[\pmb{x}^{(i)}=(x_1^{(i)},x_2^{(i)},...,x_n^{(i)}) \]

线性回归模型：

\[f_\theta(\pmb{x})=\theta_0+\theta_1x_1+\theta_2x_2+...+\theta_nx_n=\sum_{i=0}^n\theta_ix_i=\pmb{\theta^T}\pmb{x} \]

其中引入x₀=1作为偏置项

线性回归的目标就是对于每组输入数据x⁽ⁱ⁾，使得预测值f_θ(x⁽ⁱ⁾)尽可能接近真实值y⁽ⁱ⁾，甚至相等
因此定义损失函数：

\[J(\pmb{\theta})=\frac{1}{2m}\sum_{i=1}^m [f_\theta(\pmb{x}^{(i)})-y^{(i)}]^2 \]

也可以视作数据集的均方误差(MSE)，而要让误差最小：

\[\pmb{\theta}=argmin_{\theta}J(\pmb{\theta}) \]

为了找到合适的θ使得J(θ)取得最小值，可以使用梯度下降算法进行迭代，θ的初始值是随机生成的，通过反复调整θ使J(θ)收敛：

\[\theta_j=\theta_j-\alpha\frac{\partial}{\partial{\theta_j}}J(\pmb{\theta}) \]

其中α为学习率，表示每次迭代过程中θ的更新速度
而偏导数计算如下：

\[ \frac{\partial}{\partial{\theta_j}}J(\pmb{\theta})=\frac{\partial}{\partial{\theta_j}}\frac{1}{2m}\sum_{i=1}^m [f_\theta(\pmb{x}^{(i)})-y^{(i)}]^2 =2*\frac{1}{2m}\sum_{i=1}^m (f_\theta(\pmb{x}^{(i)})-y^{(i)})*\frac{\partial}{\partial{\theta_j}}(f_\theta(\pmb{x}^{(i)})-y^{(i)}) =\frac{1}{m}\sum_{i=1}^m (f_\theta(\pmb{x}^{(i)})-y^{(i)})x_j^{(i)} \]

对于单个训练样本而言，m=1，则参数θ的更新公式为：

\[\theta_j=\theta_j+\alpha(y-f_\theta(\pmb{x}))x_j \]

梯度下降算法

梯度下降算法是一种迭代更新算法，主要分为3种：

• 批量梯度下降算法
• 随机梯度下降算法
• 小批量梯度下降算法

批量梯度下降算法(Batch Gradient Descent，BGD)

每次迭代遍历数据集时，保存每组训练数据对应的梯度增量，遍历结束后，计算数据集的梯度增量之和，最后调整所有模型参数：

Repeat until convergence{
w_j=w_j-α∑_{i=1}^m Δw_j⁽ⁱ⁾ (for every j)
}

其中m为训练数据集规模，α为学习率，w为带优化的参数，Δw为参数w的梯度增量

BGD算法每次迭代调整一次模型参数，阻碍了迭代训练，同时每次迭代需要保存每组数据对应的梯度增量，当训练数据规模较大时，会带来很大的空间开销

随机梯度下降算法(Stochastic Gradient Descent，SGD)

BGD算法虽然收敛于全局最优解，但是收敛速度缓慢，因此适用性不强，SGD算法可以作为BGD算法的替代，其伪代码如下所示：

Loop{
for i=1 to m{
w_j=w_j-αΔw_j⁽ⁱ⁾ (for every j)
}
}

SGD算法在一次迭代训练中，依次遍历数据集中的每组数据，利用每组数据对应的梯度增量来调整模型参数，即对于一个含有m组数据的数据集，在每次迭代训练中，必须调整模型参数m次
SGD属于贪心算法，每次迭代只用一组数据进行参数调整，而一组数据的梯度不能代表整体数据集的梯度方向，因而不可能都沿着全局最优解方向，故而可能会陷入局部最优解

小批量梯度下降算法(Mini Batch Gradient Descent，MBGD)

MBGD算法是BGD算法和SGD算法两者的折中，MBGD算法的伪代码如下所示：

m=Data Size
n=Mini Batch Size
Repeat until convergence{
for i=1 to m/n:
w_j=w_j-α/n∑_{k=1}^n Δw_j^(k) (for every j)
}

MBGD算法首先将训练数据集随机打乱，并划分为若干均等小样本，然后每次迭代遍历每个小样本，计算小批量样本的梯度增量的平均值，并根据计算的平均值调整参数，在小批量样本规模足够大时，小批量样本梯度的平均值在误差允许范围内近似等于全体训练样本梯度增量的平均值
MBGD算法相比于BGD算法加快了收敛速度，相比于SGD算法降低了迭代训练中陷入局部最优解的风险

在线性回归中使用梯度下降算法

正则方程

输入数据集定义为：

\[\pmb{X}=(\pmb{x}^{(1)},\pmb{x}^{(2)},...\pmb{x}^{(m)})^T \]

\[\pmb{Y}=(y^{(1)},y^{(2)},...y^{(m)})^T \]

\[\pmb{\theta}=(\theta_0,\theta_1,...,\theta_n)^T \]

输入数据集的预测值：

\[f(\pmb{X})=\pmb{X}\pmb{\theta} \]

损失函数：

\[J(\pmb{\theta})=\frac{1}{2m}\sum_{i=1}^m [f_\theta(\pmb{x}^{(i)})-y^{(i)}]^2=\frac{1}{2m}(\pmb{X}\pmb{\theta}-\pmb{Y})^T(\pmb{X}\pmb{\theta}-\pmb{Y}) \]

对上式求导：

当求导后的结果等于0时：

\[\pmb{X}^T\pmb{X}\pmb{\theta}=\pmb{X}^T\pmb{Y} \]

上式称为正则方程，化简可得：

\[\pmb{\theta}=(\pmb{X}^T\pmb{X})^{-1}\pmb{X}^T\pmb{Y} \]

可见梯度下降算法需要反复迭代才能得出参数θ，正则方程只需要进行简单的矩阵运算就能得到参数θ，但是相比于梯度下降算法的时间复杂度O(kn²)，正则方程的时间复杂度是O(n³)，因此适用于小数据集
同时要使用正则方程必须满足X^TX可逆，即X^TX是满秩矩阵，在实际编程过程中，通常在计算(X^TX)^-1前先将X^TX加上一个较小的可逆矩阵，如0.001E

局部加权线性回归