Created 2021.03.22 by Cong Yu; Last modified: 2024.06.22-v4.3.2
Contact: windmillyucong@163.com
Copyleft! 2024 Cong Yu. Some rights reserved.
1 最小二乘
1.1 问题定义
^a36672
- 目标函数具有特殊形式，是若干项的平方和。
Definition 1.1. Least Squares Problem
\[\begin{align} & \textrm{Given }F：\mathbb{R} ^{n} \mapsto \mathbb{R} \\ & \textrm{Find } \mathbf{x}^+ = \text {argmin}_\mathbf{x} F(\mathbf x) \end{align}\]其中 $F$ 具有形式：
\(F(\mathbf x)= \frac{1}{2}\sum_{i=1}^{m} ( f_{i}( \mathbf{x} ) )^2\) 其中 $f_i(\mathbf{x})$ 具有形式：
\[f_i(\mathbf{x}) = h(\mathbf x,t_i)-y_i\]$h (\mathbf x,t)$ 即预测方程 hypothesis_func，被拟合的函数。
$t$即数据集中的输入，$y$ 即数据集中的拟合目标label。$f$即残差。m即样本数。n即输入数据$t$的维度。
优化目标是 $h(\mathbf x,t)$ 中的参数 $\mathbf x$ 。
1.2 最小二乘优化问题的解法
^25e8d9
最小二乘问题是 凸优化问题 的一个特例。对于这个特例，从凸优化问题的解法，还可以引申出很多更精细更高效的方法。
- 解析解法：解析解法依旧如 凸优化问题。
- 优化解法：优化解法除去 2022-01-03-凸优化 中介绍的梯度下降法、牛顿法等，还可以从凸优化问题的解法引申出很多更精细更高效的方法，如下文所述。
1.2.1 批量梯度下降法
由于此问题由很多项组合而成，所以上面的公式中，我们可以对求和符号可以做进一步深究，由此衍生出各种批量的梯度下降算法：
refitem: https://arxiv.org/pdf/1609.04747
全量梯度下降法 FGD
即2022-01-03-凸优化 中介绍的普通的梯度下降方法，每次迭代时，都选择数据集中所有的数据一起计算cost，即从i=1累加到i=m。 $\sum_{i=1}^{m}$。
\[F_{\theta}(\mathbf x)= \frac{1}{2}\sum_{i=1}^{m} ( f_{\theta}( \mathbf{x}_i ) )^2\] \[\theta := \theta -\eta J(\theta; f_{(1:m)})\]随机梯度下降法 SGD
Stochastic gradient descent，每次迭代都只使用其中的一个数据求cost，然后将误差反向传播到所有的自变量参数，然后选择下一个训练数据重复上述步骤。
\(F_{\theta}(\mathbf x)= \frac{1}{2}( f_{\theta}( \mathbf{x}_i ) )^2\) \(\theta := \theta -\eta J(\theta; f_{i})\)
迭代开始前打乱所有样本，每次迭代都只使用一个样本，下一次迭代使用下一个样本。
批量梯度下降法 Mini-batch GD
每次迭代都只使用数据集中的一部分数据，$F$为第j次迭代所用的数据表达出的cost_function，batch的大小为s个数据。
\(F_{\theta}(\mathbf x)= \frac{1}{2}\sum_{i=js}^{(j+1)s} ( f_{\theta}( \mathbf{x}_i ) )^2\) \(\theta := \theta -\eta J(\theta; f_{(js:(j+1)s)})\)
通常会先将数据集打乱顺序。每次迭代都只选择其中的一部分数据(一个batch)进行拟合，求cost，将误差反向传播到所有自变量参数，然后选择下一个batch里的数据进行下一次迭代，重复上述步骤。
也是非常常用的训练方式。
1.2.2 高斯牛顿法
思路：
牛顿法中迭代公式为：
\[\mathbf x:= \mathbf x-\eta H^{-1}J^T\]需要求解$F$的一阶和二级导，但是注意到，在最小二乘优化中，$F$有形式
\[F(\mathbf x)=\frac 12 {f(\mathbf x)}^T {f(\mathbf x)}= \frac{1}{2}\sum_{i=1}^{m} ( f_{i}( \mathbf{x} ) )^2\]因此有一阶导
\[J_F = \frac{\partial F}{\partial \mathbf x} = \sum_i f_i \frac{\partial f_i}{\partial \mathbf x} = J_f^T f\]有二阶导
\[H_F = \frac{\partial^2 F}{\partial \mathbf x^2} = J_f^T J_f + \sum_i f_i \frac{\partial^2 f_i}{\partial \mathbf x^2}\]如果我们考虑只将$\mathbf{f(x)}$一阶泰勒展开$f(\mathbf x + \Delta \mathbf x) = f(\mathbf x) + J_f(\mathbf x) \Delta \mathbf x + o(|\Delta \mathbf x|^2)$，则可忽略上式的第二项，因此
\[H_F \approx J_f^T J_f\]于是我们只需要求$J_f$ 就可以替代$J_F$和$H_F$，求解速度加快！
然后再用这个替代品$J_F$和$H_F$ 使用牛顿法即可。
最终的迭代公式：
\[\mathbf x := \mathbf x - \eta H_F^{-1} J_F^T\]其中
\[\begin{align} &J_F = J_f^T f \\ &H_F \approx J_f^T J_f \end{align}\]1.2.3 列文伯格-马夸尔特法
思路：可以简单理解为 带阻尼的 高斯-牛顿方法
\[\mathbf x:= \mathbf x - \eta (H + \mu I) ^ {-1} J ^T\]
1.2.4 狗腿法
狗腿法（Dogleg Method）是一种结合了最速下降法和高斯-牛顿法的优化算法。它的基本思想是：
- 计算最速下降方向和高斯-牛顿方向
- 根据信赖域半径，在这两个方向之间选择一个折衷的更新方向
- 如果高斯-牛顿步长在信赖域内，直接使用高斯-牛顿步长
- 否则，在信赖域边界上选择一个点，使得该点与当前点的连线与最速下降方向和高斯-牛顿方向形成一个”狗腿”形状
算法步骤：
- 计算最速下降方向：$p_{sd} = -J^Tf$
- 计算高斯-牛顿方向：$p_{gn} = -(J^TJ)^{-1}J^Tf$
- 如果$|p_{gn}| \leq \Delta$（信赖域半径），则使用$p_{gn}$
- 否则，计算$\alpha$使得$|p_{sd} + \alpha(p_{gn} - p_{sd})| = \Delta$，使用这个点作为更新方向
更多的小技巧：
- 信赖域半径的自适应调整：
- 如果当前步长导致目标函数值下降，增加信赖域半径
- 如果当前步长导致目标函数值上升，减小信赖域半径
- 预处理技术：
- 使用预处理矩阵来改善问题的条件数
- 常用的预处理方法包括对角缩放、不完全Cholesky分解等
- 终止条件：
- 梯度范数小于阈值
- 函数值变化小于阈值
- 达到最大迭代次数
2 非线性最小二乘问题
2.1 问题定义
同 最小二乘问题定义，但补充条件：要求 $h(\mathbf x,t)$ 是非线性函数。
2.2 解决方法
- 采用上文 最小二乘问题的解法
- 对于一些特殊的，可以使用换元法如何将它线性化，然后采用下文线性最小二乘的方法求解
3 线性最小二乘问题 aka 线性回归
3.1 问题定义
\[\begin{align} & \textrm{Given }F：\mathbb{R} ^{n} \mapsto \mathbb{R} \\ & \textrm{Find } \mathbf{x}^+ = \text {argmin}_\mathbf{x} F(\mathbf x) \end{align}\]其中 $F$ 具有形式：
\[F(\mathbf x)= \frac{1}{2m}\sum_{i=1}^{m} ( f_{i}( \mathbf{x} ) )^2 \equiv \text{RSS}\]该形式即均方差，RSS
其中 $f_i(\mathbf{x})$ 具有形式：
\[f_i(\mathbf{x}) = h(\mathbf x,t_i)-y_i = t_i \mathbf x - y_i\]- $h (\mathbf x,t_i)$ 即预测方程 hypothesis_func，被拟合的函数，且是线性函数。表示在参数$\mathbf x$下输入$t_i$的都得结果。
- $y$ 即拟合的label。
- 优化目标即 $h(\mathbf x,t_i)$ 中的参数 $\mathbf x$ 。
事实上，只要目标函数$F(\mathbf x)$是二次函数，基本都是线性最小二乘问题。
- $A$: m个样本,n个特征维度
- $\mathbf x$: n个特征维度,1维，优化参数
- $y$: m个样本,1维
注：本篇的着眼点在最小二乘相关内容，线性回归为什么使用RSS误差形式，从而能构造成线性最小二乘问题？以及f(x) 为什么是h与y的减法的形式？这些与线性回归相关的细节，可以查看另一篇 2022-01-06-广义线性模型 中的相关内容。
定义符号统一
事实上，在这一节，我们需要更换一下符号，将问题表达成更通用的表达，使用更惯用的符号，使用$\theta$表示被优化的目标参数$\mathbf x$，使用$x$表达样本输入$t$
于是更常见地，我们将问题定义为
\[\begin{align} & \textrm{Given }F：\mathbb{R} ^{n} \mapsto \mathbb{R} \\ & \textrm{Find } \theta^+ = \text {argmin}_\theta F(\mathbf \theta) \end{align}\]其中 $F$ 具有形式：
\[F(\theta)= \frac{1}{2m}\sum_{i=1}^{m} ( f_{i}( \theta, x_i) )^2 \equiv \text{RSS}\]该形式即均方差，RSS
其中 $f_i(\theta,x_i)$ 具有形式：
\[f_i(\theta, x_i) = h(\theta, x_i)-y_i = x_i \theta - y_i\]- $h (\theta,x_i)$ 即预测方程 hypothesis_func，被拟合的函数，且是线性函数。表示在参数$\theta$下输入$x_i$可获得的结果。
- $y$ 即拟合的label。
- 优化目标即 $h(\theta,x_i)$ 中的参数 $\theta$ 。
写作矩阵形式：
\[F(\theta) = \frac 1 {2m} \| X \theta - y\|^2\]- $X$: mxn，m个样本,n个特征维度，被拟合的样本
- $y$: mx1，m个样本,1维，被拟合的样本的label
- $x_i$: 1xn，1行n个特征维度，第i个样本
- $y_i$: 1x1，第i个样本的label
- $\theta$: nx1，n个特征维度,1维，待求解参数
3.2 求解方法
除去上文 最小二乘求解方法中的方法 之外，针对此问题的特殊形式，可以有解析法。
3.2.1 解析解
线性最小二乘问题可以直接求得解析解：
$\theta^+ = (X^T X)^{-1} X^T y$
推导
\[\begin{align} F(\theta) =& \frac{1}{2}\sum_{i=1}^{m} ( f_i(\theta, x_i ) )^2 = \frac 1 2 \| X \theta - y \| ^ 2 \\ =& \frac 1 2 (X\theta - y) ^ T (X \theta -y) \\ =& \frac 1 2 (y^Ty - \theta^TX^Ty -y^TX\theta + \theta^TX^T X \theta )\\ \end{align}\]求导 \(J_F = \frac {\partial F} {\partial \theta} = X^TX\theta - X^T y\)
令其等于0，得
\[X^TX \theta = X^T y\]当 $X^T X$ 可逆时，得
\[\theta^+ = (X^T X)^{-1} X^T y\]补充一些矩阵运算公式：The Matrix Cookbook http://matrixcookbook.com
$A$ is a constant.
\[\begin{align} \\ \partial A &= 0 \\ \partial(X+Y) &= \partial X + \partial Y \\ \partial(XY) &= (\partial X) Y + X (\partial Y) \\ \partial(X^{-1}) &= - X^{-1}(\partial X) X^{-1} \\ \partial X^T &= (\partial X)^T \\ \frac {\partial X^TA}{\partial X} &= \frac {\partial A^TX}{\partial X} = A \\ \frac {\partial A X}{\partial X} &= A^T \\ \frac {\partial a^T X b}{\partial X} &= ab^T \\ \frac {\partial a^T X^T b}{\partial X} &= ba^T \\ \frac {\partial X^T A X}{\partial X} &= (A+A^T)X \end{align}\]可行性分析
解析方法求解线性最小二乘问题的复杂度分析：
- 计算$X^TX$：$O(mn^2)$
- 计算$(X^TX)^{-1}$：$O(n^3)$
- 计算$X^Ty$：$O(mn)$
- 最终矩阵乘法：$O(n^2)$
总复杂度：$O(mn^2 + n^3)$
问题规模对求解消耗的影响：
- 当$m \gg n$时，主要复杂度来自$O(mn^2)$
- 当$n$较大时，主要复杂度来自$O(n^3)$
- 对于大规模问题，建议使用迭代方法（如共轭梯度法）而不是直接求解
4 岭回归
- 岭回归（Ridge Regression），也称为L2正则化线性回归。
- 用于解决多重共线性问题，防止过拟合。
- 在损失函数中加入系数的平方和来约束回归的参数。
解析解
\[\theta ^+ = (X^TX + \lambda I)^{-1}X^Ty\]5 Lasso回归
- 使用L1正则化
- 可以将一些系数收缩为零，达到特征选择的目的
6 加权最小二乘问题
6.1 问题定义
加权最小二乘，每个样本都以某种形式计算出一个权重，表征该样本对最终结果的影响程度。加权最小二乘问题可以很容易转化为标准的最小二乘问题进行求解。
\[F_\theta(\mathbf x)= \frac{1}{2}\sum_{i=1}^{m} \omega_i (f_\theta(\mathbf x_i))^2\]6.2 求解
6.2.1 解析解
$\theta^+ = (X^TWX)^{-1}X^TWy$
推导
\[\begin{align} F_{\theta}(\mathbf x) =& \frac{1}{2}\sum_{i=1}^{m} \omega_i ( f_{\theta}( \mathbf{x}_i ) )^2 \\ =& \frac 1 2 (X\theta - y) ^ T W (X \theta -y) \\ \end{align}\]其中 \(W = \begin{bmatrix} \omega_1 & 0 & \cdots & 0 \\ 0 & \omega_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \omega_m \end{bmatrix}\)
有
\[J_\theta = \frac {\partial F} {\partial \theta} = X^TWX\theta - X^TW y\]令其等于0，得
\[X^TWX \theta = X^TW y\]当 $X^T W X$ 可逆时，得
\[\theta^+ = (X^TW X)^{-1} X^T Wy\]loss kernel
损失核（Loss Kernel）是用于处理异常值和非高斯噪声的鲁棒损失函数。常用的损失核包括：
-
Huber损失： \(\rho(r) = \begin{cases} \frac{1}{2}r^2 & |r| \leq \delta \\ \delta|r| - \frac{1}{2}\delta^2 & |r| > \delta \end{cases}\)
-
Cauchy损失： \(\rho(r) = \frac{c^2}{2}\log(1 + (\frac{r}{c})^2)\)
-
Tukey损失： \(\rho(r) = \begin{cases} \frac{c^2}{6}[1 - (1 - (\frac{r}{c})^2)^3] & |r| \leq c \\ \frac{c^2}{6} & |r| > c \end{cases}\)
-
Geman-McClure损失： \(\rho(r) = \frac{r^2}{2(1 + r^2)}\)
这些损失核的共同特点：
- 对异常值不敏感
- 在原点附近近似于二次函数
- 在远离原点处增长较慢
- 可以通过调整参数来控制对异常值的敏感程度
