[数据结构与算法]线性模型——最小二乘法，梯度下降，线性回归，logistic回归

线性模型——最小二乘法，梯度下，线性回归，logistic回归（逻辑回归）

（一）基本形式

• 线性模型： 给定d个属性描述的示例X = (x1;x2;……;xd)（X为列向量），xi是第i个属性上的取值。 线性模型(linear model)试图学得一个通过属性的线性组合进行预测的函数。

$$f(X)=w_1{x}_1+w_2{x}_2+\dots +w_d{x}_d+b$$

向量形式：
$$f(X)=W^{T}X+b$$
其中W = (w1;w2;……;wd)。学习过程就是调整W和b。

• 线性模型的优点：
• 线性模型形式简单，易于建模，却蕴含着机器学习中的一些重要的基本思想。许多功能更为强大的非线性模型(nonlinear model)可在线性模型基础上通过引入层级结或更高维映射而得。
• 线性模型有很好得可解释性(comprehensibility)：因为W直观表达了各属性在预测中得重要性。

（二）线性回归(linear regression)

• 线性回归(linear regression)： 给定数据集D = {(X1,y1),(X2,y2),……,(Xm,ym)},其中Xi = (xi1;xi2;……xid),yi ∈ R，线性回归试图学得一个线性模型以尽可能准确地预测实值输出标记。

• 对于离散属性：
• 若属性值之间存在“序”的关系：可通过连续化将其转化为连续值，如身高地高、矮可转化为{1.0, 0.0}。
• 若属性之间不存在"序“的关系，假定有k个属性值，则通常转换为k维向量，例如西瓜、南瓜、黄瓜可转化为{(0, 0, 1), (0, 1, 0), (1, 0, 0)}。

1.最小二乘法(least square method)

• 最小二乘法(least square method)： 基于均方误差最小化来进行模型求解的方法称为最小二乘法。
• 均方误差具有非常好的几何意义，它对应了常用的欧几里得距离(欧氏距离)。

$$(w^{?},b^{?})=argmin\sum _{i=1}^m(f(x_i)?y_i{)}^2=argmin\sum _{i=1}^m(y_i?w{x}_i?b{)}^2(w^{?},b^{?}表示w，b的解)$$

$$E(w,b)=\sum _{i=1}^m(y_i?w{x}_i?b{)}^2$$

• 参数估计(parameter estimation)： 求解w和b使均方误差最小化的过程，称为对线性回归模型的最小二乘“参数估计”

以上是针对一个属性的样本求解，对于一般情形，样本由d个属性描述，此时我们试图学得
$$f(x_i)1=w^T{x}_i+b,使得f(x_i)?{>}_i$$
这称为多元线性回归（multivariate linear regression）。以下是采用最小二乘法的正则化求解过程：

使用正则方程组必须满足XTX可逆，即为满秩矩阵。但是在实际问题中，数据集的特征数n可能大于数据集规模m，这导致矩阵不可逆。因此，通常在计算(xTx)^-1之前在xTx加上一个较小的可逆矩阵，如0.001E(E为单位矩阵)。

• *有关最小二乘法的概率解释：

注：上述的最小二乘估计解释和下面的梯度下降算法都来自于《机器学习入门基于数学原理的Python实战》戴璞微，潘斌。

2.梯度下降算法

虽然迭代更新的算法有很多种，但是梯度下降算法是最好理解的一种。当前梯度下降算法主要分为三种：

• 批量梯度下降算法(Batch Gradient Descent, BCD)
• 随机梯度下降算法(Stochastic Gradient Descent, SGD)
• 小批量梯度下降算法(Mini Batch Gradient Descent, MBGD)

• 批量梯度下降算法(BCD)
• 算法思想：每次迭代遍历数据集时，保存每组训练数据对应的梯度增量。遍历结束后，计算数据集的梯度增量之和，最后调整所有模型参数。显然，不断迭代优化后，BGD算法能收敛于全局最优解。BGD算法的伪代码如下：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QGDu2hsk-1628868467972)(D:\Program Files\Typora\picture\BGD.png)]

• m为训练数据集规模、α为学习率、w为待优化参数、Δw为参数w的梯度增量。
• 优缺点：BGD算法虽然收敛于全局最优解，但是收敛速度缓慢，因此适用性不强。

• 随机梯度下降算法(SGD)
• 算法思想：在每次迭代训练中，首先将训练集随机打乱，依次遍历数据集中的每一组数据，利用数据对应的梯度增量来调整模型参数。也就是说，对于一个含有m组数据的数据集，在每次迭代训练中，必须调整模型参数m次。算法伪代码如下：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-szcoUYSc-1628868467975)(D:\Program Files\Typora\picture\SGD.png)]

• 优缺点： 从SGD算法的思想上来看，SGD属于贪心算法。每次迭代训练过程中，SGD算法相比于BGD算法虽然频繁地调整参数，加快了收敛速度，但SGD算法也会存在偏差，每次迭代只用一组数据进行参数调整，而一组数据不能代表整体数据集地梯度方向，因此不可能都沿着全局最优解方向，故而陷入局部最优解。SGD理论上不能收敛到全局最优解，而在全局最优解地附近领域内震荡。

• 小批量梯度下降算法(MBGD)
• 算法思想： 每次迭代训练将数据集随机打乱，并划分为若干均等小样本，每次迭代训练地过程中遍历每个小样本，计算小批量样本地梯度增量平均值，并根据计算的平均值调整参数。算法伪代码如下：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8uFpqHZ2-1628868467977)(D:\Program Files\Typora\picture\MBGD.png)]

• 优缺点：MBGD算法兼顾了BGD和SGD算法的优点，所以MBGD算法相比于BGD算法加快了收敛速度，相比于SGD算法降低了迭代训练中陷入局部最优解的风险。

综合上述的三种算法，当损失函数为均方误差(MSE）时，可以得到一个统一的更新公式：
$$w_j=w_j?\frac{\alpha }{\xi }\sum _{i=1}^{\xi }\Delta w_j$$
公式中ξ为常数，Δw为参数w的梯度增量，m为数据集规模。当ξ=1时，对应的就是SGD；当ξ=m时，对应的就是BGD；当ξ=n(1<n<m)时，对应的就是MBGD。

• 梯度下降算法与最小二乘法（正则方程）的比较：

（三）广义线性模型（generalized linear model）

• 广义线性模型(generalized linear model)：考虑单调可微函数g(·),令

$$y=g^{?1}(w^{t}x+b)$$

这样得到的模型称为"广义线性模型"，其中g(·)称为“联系函数”。

（四）对数几率回归(logistic regression/logit regression)

虽然名称为对数几率回归，但是是用来解决分类问题的。

• 单位阶跃函数(unit-step function)： 若预测值大于零则为正例，小于零则为反例，预测值为临界值则可任意判别。因为单位阶跃函数不可微，因此不能直接用作联系函数构造广义线性模型。
• 对数几率函数(logistic function)：

$$y=\frac{1}{1+e^{?z}}$$

$$\begin{gathered} y=\frac{1}{1+e^{?z}}=>z=ln\frac{y}{1?y} \\ z=w^{T}x+b=>y=\frac{1}{1+e^{?(w^{T}x+b)}} \\ ln\frac{y}{1?y}=w^{T}x+b \end{gathered}$$

• 根据上述几个式子，有几个定义。
• 几率(odds)： 若将视为样本x作为正例的可能性，则1-y时反例的可能性，两者的比值称为几率。几率反映了x作为正例的相对可能性。
• 对数几率(log odds,亦称logit)： 对几率取对数则称为对数几率。

• 先来看看对数几率回归这种分类学习算法的 优点
• 无需事先假设数据分布，这样避免了假设分布不准确所带来的问题。
• 它不仅预测出类别，而是可得到近似概率预测，这对许多需利用概率辅助决策的任务很有用。
• 对数几率是任意阶可导的凸函数，有很好的数学性质，现有的许多数值优化算法都可直接用于求取最优解。