线性回归¶

线性回归（linear regression）是应用最为广泛的回归模型，但其基本思想与形式早已超出了单纯的回归场景。因为其推导形式比较简单、经典，就拿来记录一下，顺带结合相关的优化学习与正则技巧一起了

分类¶

监督学习方法
非概率模型
参数化模型

基本形式¶

假设样本写作增广后的列向量，即

\[ \mathbf{x} = [1,x^{(1)},x^{(2)},···,x^{(p)}]^\mathrm{T} \]

即第一个对应参数的偏置项，剩下的即是样本的特征项，线性回归的模型相当简洁

\[ y = \theta_0+\theta_1x^{(1)}+\theta_2x^{(2)}+···\theta_px^{(p)} \]

即

\[ y = \mathbf{x}^\mathrm{T}\boldsymbol{\theta} \]

将整个样本写作矩阵形式，有

\[ \begin{aligned} \mathbf{X} &= [\mathbf{x_1},\mathbf{x_2},···,\mathbf{x_n}]^\mathrm{T}\\ \mathbf{y} &= [y_1,y_2,···,y_n]^\mathrm{T}\\ \boldsymbol{\theta} &= [\theta_0,\theta_1,···,\theta_p]^\mathrm{T} \end{aligned} \]

则

\[ \mathbf{y} = f(\mathbf{X};\boldsymbol{\theta}) = \mathbf{X}\boldsymbol{\theta} \]

损失策略¶

采取 SSE（sum of squared error），就是常见的平方损失，该函数是凸函数，这一优秀的性质是正规方程求最优解的基础

\[ \begin{aligned} J(\boldsymbol{\theta}) &= \frac{1}{2}\sum_{i=1}^{n}(\hat{y_i}-y_i)^2\\ % &= \frac{1}{2}\sum_{i=1}^{n}(\mathbf{x}_i^\mathrm{T}\boldsymbol{\theta}-y_i)^2\\ &= \frac{1}{2}(\hat{\mathbf{y}}-\mathbf{y})^\mathrm{T}(\hat{\mathbf{y}}-\mathbf{y})\\ &= \frac{1}{2}(\mathbf{X}\boldsymbol{\theta}-\mathbf{y})^\mathrm{T}(\mathbf{X}\boldsymbol{\theta}-\mathbf{y})\\ &= \frac{1}{2}(\boldsymbol{\theta}^\mathrm{T}\mathbf{X}^\mathrm{T}\mathbf{X}\boldsymbol{\theta}-\mathbf{y}^\mathrm{T}\mathbf{X}\boldsymbol{\theta}-\boldsymbol{\theta}^\mathrm{T}\mathbf{X}^\mathrm{T}\mathbf{y}+\mathbf{y}^\mathrm{T}\mathbf{y}) \end{aligned} \]

优化学习¶

正规方程直接求解¶

为了得到学习的参数 \(\boldsymbol{\theta}\) ，我们首先可以直接求解

\[ \boldsymbol{\theta}^*=\mathop{\arg\min}\limits_{\theta}J(\boldsymbol{\theta}) \]

即求损失函数 \(J(\boldsymbol{\theta})\) 的最小值点，先对其求一阶导

\[ \begin{aligned} \nabla_{\boldsymbol{\theta}}J(\boldsymbol{\theta}) &= \frac{\partial J(\boldsymbol{\theta})}{\partial\boldsymbol{\theta}}\\ &= \frac{1}{2}(2\mathbf{X}^\mathrm{T}\mathbf{X}\boldsymbol{\theta}-2\mathbf{X}^\mathrm{T}\mathbf{y})\\ &= \mathbf{X}^\mathrm{T}\mathbf{X}\boldsymbol{\theta}-\mathbf{X}^\mathrm{T}\mathbf{y} \end{aligned} \]

再有二阶导

\[ \frac{\partial\nabla_{\boldsymbol{\theta}}J(\boldsymbol{\theta})}{\partial\boldsymbol{\theta}} = \mathbf{X}^\mathrm{T}\mathbf{X} \]

关于\(\mathbf{X}^\mathrm{T}\mathbf{X}\)

\(\mathbf{H} = \mathbf{X}^\mathrm{T}\mathbf{X}\) 总是半正定的（PSD，positive semi-definite），因为对任意非零列向量 \(\mathbf{a}\)，总有

\[ \mathbf{a}^\mathrm{T}\mathbf{H}\mathbf{a} = \mathbf{a}^\mathrm{T}\mathbf{X}^\mathrm{T}\mathbf{X}\mathbf{a} = \Vert\mathbf{X}\mathbf{a}\Vert_2^2 \geq 0 \]

且当 \(\mathbf{X}\) 列满秩时，\(\mathbf{H}\) 为正定的（PD，pisitive definite），故 \(\mathbf{H} = \mathbf{X}^\mathrm{T}\mathbf{X}\) 可逆

回到函数

由 \(J(\boldsymbol{\theta})\) 的二阶导，即 Hessian 矩阵可知，一般情况下，\(\mathbf{X}\) 的行数远大于列数（样本数远多于特征数），这意味着 \(\mathbf{X}\) 是列满秩的，故 \(J(\boldsymbol{\theta})\) 的二阶导正定可逆

进一步我们知道，多元函数 \(J(\boldsymbol{\theta})\) 是凸函数

极值点便是最值点
极值点 \(\nabla_{\boldsymbol{\theta}}J(\boldsymbol{\theta}) = 0\) 是极小值点

故我们可以直接写出 \(\boldsymbol{\theta}^*\) 的解析解

\[ \begin{aligned} \nabla_{\boldsymbol{\theta}}J(\boldsymbol{\theta}) &= \mathbf{X}^\mathrm{T}\mathbf{X}\boldsymbol{\theta}-\mathbf{X}^\mathrm{T}\mathbf{y} = 0\\ \boldsymbol{\theta}^*&= (\mathbf{X}^\mathrm{T}\mathbf{X})^{-1}\mathbf{X}^\mathrm{T}\mathbf{y} \end{aligned} \]

计算开销粗估

\[ \boldsymbol{\theta}^* = (\mathbf{X}^\mathrm{T}\mathbf{X})^{-1}\mathbf{X}^\mathrm{T}\mathbf{y} \]

\(\mathbf{X}^\mathrm{T}\mathbf{X}\)：\(O(p^2n)\)，\(\mathbf{X}^\mathrm{T}\mathbf{y}\)：\(O(p^3)\)，合起来\(O(p^2n+p^3)\)

当 \(n >> p\) 时，前一步乘积开销更大

梯度下降¶

一般的情形

对任意可得到一阶导的函数\(f(\mathbf{x})\)

初始化\(k = 0\)，随机或专门选取起始点\(\mathbf{x}_0\)
当 \(k < k_{max}\) 时，即设定迭代 \(k_{max}\) 次：

\[ \mathbf{x}_{t+1} = \mathbf{x}_t - \alpha \nabla_{\mathbf{x}}f(\mathbf{x}_t) \]

其学习率 \(\alpha\)，起始点 \(\mathbf{x}_0\)（若 \(f(\mathbf{x})\) 为凸则能避免收敛到局部极值）以及优化对象 \(f(\mathbf{x})\) 都会对梯度下降效果有影响

线性回归的情形

之前推导中我们已经有了凸函数 \(J(\boldsymbol{\theta})\) 的一阶导

\[ \begin{aligned} \boldsymbol{\theta}^{t+1} &= \boldsymbol{\theta}^{t} - \alpha \nabla_{\boldsymbol{\theta}}J(\boldsymbol{\theta}^{t})\\ \boldsymbol{\theta}^{t+1} &= \boldsymbol{\theta}^{t} - \alpha (\mathbf{X}^\mathrm{T}\mathbf{X}\boldsymbol{\theta}^{t}-\mathbf{X}^\mathrm{T}\mathbf{y})\\ \boldsymbol{\theta}^{t+1} &= \boldsymbol{\theta}^{t} + \alpha\mathbf{X}^\mathrm{T}(\mathbf{y}-\mathbf{X}\boldsymbol{\theta}^{t}) \end{aligned} \]

这里我们将样本 \(\mathbf{X}\) 写成了整体矩阵的形式，代表我们能一次获取大量数据，也叫做批量梯度下降（BGD，Batch Gradient Descent）

但实际应用时，我们不一定能随时获取大批量的样本信息（例如在线学习）。因此我们考虑改写形式

\[ \begin{aligned} \boldsymbol{\theta}^{t+1} &= \boldsymbol{\theta}^{t} + \alpha\mathbf{X}^\mathrm{T}(\mathbf{y}-\mathbf{X}\boldsymbol{\theta}^{t})\\ \boldsymbol{\theta}^{t+1} &= \boldsymbol{\theta}^{t} + \alpha\sum_{i=1}^{n}(y_i-\mathbf{x}_i^\mathrm{T}\boldsymbol{\theta}^{t})\mathbf{x}_i \end{aligned} \]

极端情况下，对单独 \(\mathbf{x}\)，我们有

\[ \boldsymbol{\theta}^{t+1} = \boldsymbol{\theta}^{t} + \alpha (y-\mathbf{x}^\mathrm{T}\boldsymbol{\theta}^{t})\mathbf{x} \]

于是将 \(\mathbf{X}\) 写成了单个样本 \(\mathbf{x}\) 的形式，代表我们仅凭少量甚至单个数据信息也能进行梯度下降，即随机梯度下降（SGD，Stochastic Gradient Descent）

各自特点

对于 BGD：

对应整个数据集 \(\mathbf{X}\) 形式，存储开销大
一次 Epoch 经过 1 次参数更新

对于 SGD：

对应数据集某一部分 \(\alpha\sum_{i=1}^{B}(y_i-\mathbf{x}_i^\mathrm{T}\boldsymbol{\theta}^{t})\mathbf{x}_i\) 形式（Mini-Batch），存储开销适中
一次 Epoch 经过 \(\frac{n}{B}\) 次参数更新
某些情况只需单一样本 \(\mathbf{x}\)（Single-Sample），存储开销小
一次 Epoch 经过 \(n\) 次参数更新
可以看作非全局优化的 BGD，引入了随机噪声，被认为不容易落入局部极值，在非凸优化中很流行

可以看出 SGD 相对于 BGD 更新频率更高，适用于高度冗余的数据集，但注意观测损失可能要归一化（采用 MSE 而不是 SSE）

优化方法总结¶

正规方程求解：\(\boldsymbol{\theta}^* = (\mathbf{X}^\mathrm{T}\mathbf{X})^{-1}\mathbf{X}^\mathrm{T}\mathbf{y}\)

优点：一步到位，容易实现
缺点：需要求解 \((\mathbf{X}^\mathrm{T}\mathbf{X})^{-1}\)，成本高昂，也不一定有解（例如 \(\mathbf{X}^\mathrm{T}\mathbf{X}\) 是不可逆的）

GD / BGD：\(\boldsymbol{\theta}^{t+1} = \boldsymbol{\theta}^{t} + \alpha\mathbf{X}^\mathrm{T}(\mathbf{y}-\mathbf{X}\boldsymbol{\theta}^{t})\)

优点：容易实现，形式简洁，在 LR 情形下能保证收敛
缺点：大批量，收敛慢

SGD / Mini-SGD：\(\boldsymbol{\theta}^{t+1} = \boldsymbol{\theta}^{t} + \alpha\sum_{i=1}^{B}(y_i-\mathbf{x}_i^\mathrm{T}\boldsymbol{\theta}^{t})\mathbf{x}_i\)

优点：更新频率高，收敛快；不容易落入局部极值
缺点：不能保证全局最优

正则化¶

我们从正规方程求解的视角引入

\[ \boldsymbol{\theta}^* = (\mathbf{X}^\mathrm{T}\mathbf{X})^{-1}\mathbf{X}^\mathrm{T}\mathbf{y} \]

能得到的前提是 \(\mathbf{X}^\mathrm{T}\mathbf{X}\) 可逆，但如果不可逆怎么办？

Ridge Regression | L-2 正则¶

一个很经典的方法是添加正值的对角矩阵

\[ \boldsymbol{\theta}_{ridge}^* = (\mathbf{X}^\mathrm{T}\mathbf{X} + \lambda \mathbf{I})^{-1}\mathbf{X}^\mathrm{T}\mathbf{y} \]

于是可以看作

\[ \boldsymbol{\theta}_{ridge} = \mathop{\arg\min}\limits_{\theta}(\mathbf{X}\boldsymbol{\theta}-\mathbf{y})^\mathrm{T}(\mathbf{X}\boldsymbol{\theta}-\mathbf{y})+\lambda\boldsymbol{\theta}^\mathrm{T}\boldsymbol{\theta} \]

求解，并求一阶导令为 0 的情形，联系 KKT 条件，可以等价于

\[ \begin{aligned} \boldsymbol{\theta}_{ridge} &= \mathop{\arg\min}\limits_{\theta}(\mathbf{X}\boldsymbol{\theta}-\mathbf{y})^\mathrm{T}(\mathbf{X}\boldsymbol{\theta}-\mathbf{y})\\ s.t. &\quad \boldsymbol{\theta}^\mathrm{T}\boldsymbol{\theta}\leq s^2 \end{aligned} \]

其实就是在 \(\boldsymbol{\theta}^\mathrm{T}\boldsymbol{\theta}\leq s^2\) 的条件下，求原线性回归的解

参数收缩

简化起见，假设 \(\mathbf{X}^\mathrm{T}\mathbf{X} = \mathbf{I}\)

\[ \begin{aligned} \boldsymbol{\theta}^* &= \mathbf{X}^\mathrm{T}\mathbf{y}\\ \boldsymbol{\theta}_{ridge}^* &= \frac{1}{1+\lambda}\mathbf{X}^\mathrm{T}\mathbf{y} \end{aligned} \]

故有 \(\boldsymbol{\theta}_{ridge}^* = \frac{1}{1+\lambda}\boldsymbol{\theta}^*\)，起到参数收缩的作用，当 \(\lambda\) 为 0 时，变为正常线性回归

Lasso Regression | L-1 正则¶

类似 L-2 正则，Lasso 回归只不过将惩罚项由 \(\lambda\boldsymbol{\theta}^\mathrm{T}\boldsymbol{\theta}\) 平方项变为绝对值，也就是 L-1 范数

\[ \begin{aligned} \boldsymbol{\theta}_{lasso} &= \mathop{\arg\min}\limits_{\theta}(\mathbf{X}\boldsymbol{\theta}-\mathbf{y})^\mathrm{T}(\mathbf{X}\boldsymbol{\theta}-\mathbf{y})+\lambda\sum_{i=1}^n\vert\theta_i\vert\\ \boldsymbol{\theta}_{lasso} &= \mathop{\arg\min}\limits_{\theta}(\mathbf{X}\boldsymbol{\theta}-\mathbf{y})^\mathrm{T}(\mathbf{X}\boldsymbol{\theta}-\mathbf{y})\\ s.t. &\quad \sum_{i=1}^n\vert\theta_i\vert\leq s \end{aligned} \]

特征选择

可以看出，当参数值不大时，L-1 正则倾向于将一些不重要的参数置为 0，起到特征选择的作用

Elastic Regression | L-1 & L-2¶

一起用

\[ \begin{aligned} \boldsymbol{\theta}_{elastic} = &\mathop{\arg\min}\limits_{\theta}(\mathbf{X}\boldsymbol{\theta}-\mathbf{y})^\mathrm{T}(\mathbf{X}\boldsymbol{\theta}-\mathbf{y})+\lambda_1\sum_{i=1}^n\vert\theta_i\vert+\lambda_2\boldsymbol{\theta}^\mathrm{T}\boldsymbol{\theta}\\ \boldsymbol{\theta}_{elastic} &= \mathop{\arg\min}\limits_{\theta}(\mathbf{X}\boldsymbol{\theta}-\mathbf{y})^\mathrm{T}(\mathbf{X}\boldsymbol{\theta}-\mathbf{y})\\ s.t. &\quad \sum_{i=1}^n\vert\theta_i\vert\leq s; \quad \boldsymbol{\theta}^\mathrm{T}\boldsymbol{\theta}\leq s^2 \end{aligned} \]

最后更新: 2024-01-09
创建日期: 2024-01-08