YSYSIMONCODE. ART. SCIENCE. VISION.

回归和线性系统 Regression and linear system

从过定系统、欠定系统和范数约束理解线性系统中的回归方法。

Aug 18, 2024约 7 分钟Machine Learningysysimon
Machine LearningRegressionLinear SystemsLASSORidge Regression

我们已经知道，曲线拟合会产生 优化问题 optimization problem，在许多情况下，优化可以从数学上理解为求解线性方程组 Ax=b\mathbf{A}\mathbf{x} = \mathbf{b}，在许多现代数据科学问题中，这个线性系统常常是 过定 over-determined 或 欠定 under-determined 的

过定 over-determined 系统的约束 (方程数量) 比未知数更多，而 欠定 under-determined 的约束 (方程数量) 比未知数要少

所以在系统过定的情况下，将不存在任何解能满足系统，必须找到最优的近似解来最小化给定的误差

而在系统欠定时，将存在无穷多解，必须对解做出一些约束以最终选择一个满足该约束的解来作为系统的最终解

范数的选择对于寻找最优解有着深远影响，例如最常用的 ℓ2\ell_2 和 ℓ1\ell_1 范数，对于优化过定和欠定系统也是一样

线性系统 Ax=b\mathbf{A}\mathbf{x}=\mathbf{b} 可以被认为是回归问题 Y=f(X,β)\mathbf{Y}=f(\mathbf{X,\beta}) 的受限特例，解 x\mathbf{x} 包含了表征输入数据 A\mathbf{A} 和结果数据 b\mathbf{b} 之间关系的 负载 loadings 或称 杠杆分数 leverage scores，求解这种系统的一个方法是使用以前介绍过的 Moore–Penrose 伪逆 A†\mathbf{A}^\dagger

x=A†b\mathbf{x} = \mathbf{A}^\dagger \mathbf{b}

然而这种伪逆方法具有限制性，它相当于使用 ℓ2\ell_2-范数进行最小二乘优化，在很多时候，我们需要更多的灵活性，例如使用ℓ2\ell_2 和 ℓ1\ell_1 范数进行不同的优化

过定系统 Over-determined Systems

我们已经知道，若 Ax=b\mathbf{A}\mathbf{x} = \mathbf{b} 是一个过定系统，则一般系统无解，随之而来的优化问题包括最小化“最优解”的误差

[]A输入[]x负载  =  []b结果\begin{align*} \overset{\text{输入}}{ \overset{\mathbf{A}}{ \begin{bmatrix} \hspace{1.8cm} \\[3.8cm] \end{bmatrix} } } \end{align*} \begin{align*} \overset{\text{负载}}{ \overset{\mathbf{x}}{ \begin{bmatrix} \hspace{1.7cm} \\[1cm] \end{bmatrix} } } \\[3.2cm] \end{align*} \ \ \begin{align*} = \\[2.28cm] \end{align*} \ \ \begin{align*} \overset{\text{结果}}{ \overset{\mathbf{b}}{ \begin{bmatrix} \hspace{1.8cm} \\[3.8cm] \end{bmatrix} } } \end{align*}

要想最小化“最优解”的误差，最常见的方法是使用 ℓ2\ell_2-范数构造最小二乘误差，并对该误差执行最小化优化，这可以表示为

x^=argmin⁡x∥Ax−b∥2\mathbf{\hat{x}} = \operatorname*{argmin}_{\mathbf{x}} \|\mathbf{A}\mathbf{x} - \mathbf{b} \|_2

但是这并没有对 x\mathbf{x} 作出任何约束，为了在最小化误差的同时对解 x\mathbf{x} 施加约束，可以将公式修改为

x^=argmin⁡x∥Ax−b∥2+λ1∥x∥1+λ2∥x∥2\mathbf{\hat{x}} = \operatorname*{argmin}_{\mathbf{x}} \|\mathbf{A}\mathbf{x} - \mathbf{b} \|_2 + \lambda_1 \|\mathbf{x}\|_1 + \lambda_2 \|\mathbf{x}\|_2

其中参数 λ1\lambda_1 和 λ2\lambda_2 控制 ℓ1\ell_1-范数 和 ℓ2\ell_2-范数 正则化项 (惩罚项)，这样就对解 x\mathbf{x} 本身施加了约束，而不是仅对误差本身施加约束

欠定系统 Under-determined Systems

对于欠定系统来说，系统将存在无穷多解，我们的目标是额外添加一个或一组约束，使得我们能从无限多可能的解中挑选出一个唯一的解，例如我们在解集里找到那个 ℓ2\ell_2 -范数 最小的解作为我们欠定系统的解

[]A输入[]x负载  =  []b结果\begin{align*} \overset{\text{输入}}{ \overset{\mathbf{A}}{ \begin{bmatrix} \hspace{5cm} \\[1.7cm] \end{bmatrix} } } \\[3cm] \end{align*} \begin{align*} \overset{\text{负载}}{ \overset{\mathbf{x}}{ \begin{bmatrix} \hspace{2cm} \\[3.8cm] \end{bmatrix} } } \end{align*} \ \ \begin{align*} = \\[2.28cm] \end{align*} \ \ \begin{align*} \overset{\text{结果}}{ \overset{\mathbf{b}}{ \begin{bmatrix} \hspace{2cm} \\[1.7cm] \end{bmatrix} } } \\[3cm] \end{align*}

这个优化问题可以写为

min⁡∥x∥psubject toAx=b\min \|\mathbf{x}\|_p \quad \text{subject to} \quad \mathbf{A}\mathbf{x}=\mathbf{b}

其中 pp 是解向量 x\mathbf{x} 的 ℓp\ell_p-范数，为了简单起见，我们只考虑 ℓ1\ell_1 和 ℓ2\ell_2 范数，我们已经根据前面的例子看到，ℓ1\ell_1-范数 会产生稀疏的解

和超定系统一样，可以修改优化问题以处理更一般的欠定矩阵方程，即同时处理 ℓ1\ell_1 和 ℓ2\ell_2 正则化惩罚项

min⁡(λ1∥x∥1+λ2∥x∥2)subject toAx=b\min (\lambda_1\|\mathbf{x}\|_1 + \lambda_2\|\mathbf{x}\|_2) \quad \text{subject to} \quad \mathbf{A}\mathbf{x}=\mathbf{b}

其中 λ1\lambda_1 和 λ2\lambda_2 是 ℓ1\ell_1 和 ℓ2\ell_2 的权重

线性方程的常用回归方法

对于线性方程组 Ax=b\mathbf{A}\mathbf{x}=\mathbf{b}，有以下常用回归方法

  1. 最小二乘回归: 通过 Moore-Penrose 伪逆来解决，而伪逆通常使用 SVD 进行求解，SVD本身有可能涉及 QR 分解
L=∥Ax−b∥2L = \|\mathbf{A}\mathbf{x} - \mathbf{b} \|_2
  1. 矩阵分解: 通过 QR 分解 或 Cholesky 分解 (当系统正定时)
A=QR\mathbf{A} = \mathbf{Q}\mathbf{R}
  1. LASSO Least Absolute Shrinkage and Selection Operator
L=∥Ax−b∥2+λ1∥x∥1L = \|\mathbf{A}\mathbf{x} - \mathbf{b} \|_2 + \lambda_1\|\mathbf{x} \|_1
  1. 岭回归 Ridge regression
L=∥Ax−b∥2+λ2∥x∥2L = \|\mathbf{A}\mathbf{x} - \mathbf{b} \|_2 + \lambda_2\|\mathbf{x} \|_2
  1. 弹性网络 Elastic Net
L=∥Ax−b∥2+λ1∥x∥1+λ2∥x∥2L = \|\mathbf{A}\mathbf{x} - \mathbf{b} \|_2 + \lambda_1\|\mathbf{x} \|_1 + \lambda_2\|\mathbf{x} \|_2
  1. 强稳回归 Robustfit: 通过加权最小二乘法的形式，将离群点的影响降到最低，并通过迭代过程不断调整权重，以求得更加稳健的回归结果

以上大部分方法在稀疏回归里已经详细介绍过