156 lines
8.1 KiB
Markdown
156 lines
8.1 KiB
Markdown
---
|
||
title: 3 第三章 回归的线性方法
|
||
draft: false
|
||
tags:
|
||
- ESL
|
||
---
|
||
|
||
## [逻辑架构图]
|
||
|
||
线性回归知识体系的演进逻辑遵循“从无约束到有约束，从离散选择到连续收缩”的路径：
|
||
|
||
1. **基石：全局最小二乘 (OLS)** —— 追求无偏性，但在病态矩阵（高相关性/稀疏）下方差爆炸。
|
||
|
||
2. **离散优化：子集选择 (Subset Selection)** —— 通过“硬开关”控制特征，提升可解释性，但由于离散性导致预测不稳定。
|
||
|
||
3. **连续正则化：收缩方法 (Ridge/Lasso)** —— 引入几何约束（$\ell_1 / \ell_2$），通过牺牲微小偏差换取方差的大幅下降。
|
||
|
||
4. **算法路径：LAR & 坐标下降** —— 解决收缩方法的计算效率问题，揭示回归系数演化的动态过程。
|
||
|
||
5. **空间重构：派生输入 (PCA/PLS)** —— 不再直接筛选特征，而是将特征投影到新的正交基向量空间。
|
||
|
||
|
||
---
|
||
|
||
## [深度整理正文]
|
||
|
||
### A. 全局最小二乘法 (OLS) 与 Gauss-Markov 定理
|
||
|
||
- **原本内容**：$y = wx$ 中 $w$ 是参数，矩阵是为了批处理。Gauss-Markov 定理说明 OLS 在无偏线性估计中 MSE 最小。
|
||
|
||
- **深度整理**：
|
||
|
||
- 线性模型形式：$f(X) = \beta_0 + \sum_{j=1}^p X_j \beta_j$。
|
||
|
||
- **{扩充部分}**：
|
||
|
||
> 在底层实现中，OLS 的解析解为 $\hat{\beta} = (\mathbf{X}^T \mathbf{X})^{-1} \mathbf{X}^T \mathbf{y}$。从系统角度看，计算 $(\mathbf{X}^T \mathbf{X})^{-1}$ 的复杂度为 $O(p^3 + Np^2)$。当特征数 $p$ 很大时，矩阵往往是**病态的 (Ill-conditioned)**。
|
||
>
|
||
> **SVD 分解视角**：$\mathbf{X} = \mathbf{U}\mathbf{D}\mathbf{V}^T$。OLS 的预测向量 $\hat{\mathbf{y}} = \mathbf{U}\mathbf{U}^T \mathbf{y}$。如果 $\mathbf{X}$ 的奇异值 $d_j$ 极小（对应输入空间中方差极小的方向），$(\mathbf{X}^T \mathbf{X})^{-1}$ 会导致噪声被剧烈放大，这就是为什么 OLS 在“低信噪比”下表现极差。
|
||
>
|
||
> **Gauss-Markov 定理的局限性**：虽然它是 BLUE（最优线性无偏估计），但它仅局限在“无偏”范畴。在工程实践中，我们宁愿要一个“有偏”但“方差极低”的估计（即放弃无偏性，换取更小的总 MSE）。
|
||
|
||
|
||
### B. 为什么需要控制参数：精确性与可解释性
|
||
|
||
- **原本内容**：最小二乘偏差小方差大。收缩和子集选择能提高精确性和可解释性。
|
||
|
||
- **深度整理**：
|
||
|
||
- 精确性 (Accuracy)：牺牲偏差减小方差。
|
||
|
||
- 可解释性 (Interpretability)：减少变量，保留 big picture。
|
||
|
||
- **{扩充部分}**：
|
||
|
||
> **偏差-方差分解 (Bias-Variance Decomposition)**：$MSE = \text{Bias}^2 + \text{Var} + \sigma^2$。OLS 将 $\text{Bias}$ 降为 0，但在 $p > N$ 或特征强相关时，$\text{Var}$ 会趋于无穷。
|
||
>
|
||
> **模型复杂度与过拟合**：从信息论角度看，过多的参数增加了模型的**VC维 (Vapnik-Chervonenkis dimension)**，使其能够“记住”训练集中的随机噪声（High-frequency noise），而收缩方法本质上是**低通滤波器 (Low-pass filter)**。
|
||
|
||
|
||
### C. 子集选择 (Subset Selection)
|
||
|
||
- **原本内容**：最优子集选择 ($2^n$ 组合)、向前逐步、向后逐步。
|
||
|
||
- **深度整理**：
|
||
|
||
- 最优子集：搜索空间巨大，属于 NP-hard 问题。
|
||
|
||
- 逐步回归：贪心算法，向前加相关性最大的，向后减贡献最小的。
|
||
|
||
- **{扩充部分}**：
|
||
|
||
> **计算开销与缓存局部性**：向前逐步选择在每一步都要更新 QR 分解。从系统层面看，这涉及大量的矩阵-向量乘法。
|
||
>
|
||
> **Leaps and Bounds 过程**：在进行最优子集搜索时，可以使用分支定界法（Branch and Bound）来剪枝，避免遍历完整的 $2^p$ 空间。
|
||
|
||
|
||
### D. 收缩方法：岭回归 (Ridge) 与 Lasso
|
||
|
||
- **原本内容**：Ridge 用 $\Sigma \beta_j^2$，控制收缩的是 $\lambda$；Lasso 用 $\Sigma |\beta_j|$。Lasso 能产生稀疏解。
|
||
|
||
- **深度整理**：
|
||
|
||
- 岭回归：$\hat{\beta}^{\text{ridge}} = (\mathbf{X}^T \mathbf{X} + \lambda \mathbf{I})^{-1} \mathbf{X}^T \mathbf{y}$。
|
||
|
||
- Lasso：约束区域是菱形，最优解易落在角点（参数为 0）。
|
||
|
||
- **{扩充部分}**：
|
||
|
||
> **岭回归的数值稳定性**：在底层，$\mathbf{X}^T \mathbf{X}$ 加上 $\lambda \mathbf{I}$ 实际上是在矩阵对角线上加了一个“扰动”。这使得原本不可逆（奇异）的矩阵变得正定可逆，大大增强了数值解的稳定性，防止了 CPU 浮点运算溢出。
|
||
>
|
||
> **岭回归的 SVD 解释**：其缩放因子为 $\frac{d_j^2}{d_j^2 + \lambda}$。对于奇异值 $d_j$ 较小的方向（即噪声方向），该因子会显著减小系数，起到**权重衰减 (Weight Decay)** 的作用。
|
||
>
|
||
> **Lasso 的非解析性**：与 Ridge 不同，Lasso 没有解析解（因为 $\ell_1$ 范数在 0 点不可微）。在实际工程中，常用**坐标下降法 (Coordinate Descent)**。这是一种 Cache-friendly 的算法，通过不断迭代单个 $\beta_j$ 来逼近全局最优。
|
||
|
||
|
||
### E. 最小角回归 (LAR) 与路径算法
|
||
|
||
- **原本内容**：LAR 选一个方向与已选变量夹角相同，保持同等相关，逐步逼近。
|
||
|
||
- **深度整理**：
|
||
|
||
- 核心逻辑：LAR 提供了一条从 0 到 OLS 解的连续路径。
|
||
|
||
- **{扩充部分}**：
|
||
|
||
> **算法逻辑流**：
|
||
>
|
||
> 1. 初始化 $\beta = 0$，残差 $r = y$。
|
||
>
|
||
> 2. 找到与 $r$ 相关性最大的特征 $x_j$。
|
||
>
|
||
> 3. 沿 $x_j$ 方向移动，直到另一个特征 $x_k$ 与 $r$ 的相关性与 $x_j$ 相等。
|
||
>
|
||
> 4. 沿着这两个特征的**角平分线 (Equiangular direction)** 继续移动。
|
||
>
|
||
>
|
||
> **与 Lasso 的等价性**：LAR 的修改版可以完全计算 Lasso 的所有 $\lambda$ 轨迹。其计算代价仅相当于一次全量的 OLS 分解 ($O(Np^2)$)，极其高效。
|
||
|
||
|
||
### F. 派生输入：PCA 与 PLS
|
||
|
||
- **原本内容**：通过线性/非线性变换构造新特征。偏最小二乘 (PLS) 在低维子空间寻找最大解释能力。
|
||
|
||
- **深度整理**：
|
||
|
||
- 主成分回归 (PCR)：先做 PCA，选前 $k$ 个主成分做回归。
|
||
|
||
- 偏最小二乘 (PLS)：在降维时考虑了 $y$ 的信息。
|
||
|
||
- **{扩充部分}**：
|
||
|
||
> **无监督 vs 有监督**：PCA 只看 $\mathbf{X}$ 的协方差结构（无监督），可能丢弃掉方差虽小但对 $y$ 预测至关重要的信号。而 PLS 是有监督的，它构造的方向 $z_m = \sum \phi_{mj} x_j$ 是为了最大化 $\text{Var}(\mathbf{X}\phi) \cdot \text{Corr}^2(y, \mathbf{X}\phi)$。
|
||
>
|
||
> **计算权衡**：虽然 PLS 听起来更好，但在实际高维度数据中，PLS 往往比经过交叉验证的 PCR 更容易过拟合。
|
||
|
||
|
||
---
|
||
|
||
## [边界知识联动]
|
||
|
||
1. **CPU 缓存与 BLAS 库**：
|
||
|
||
在线性回归的矩阵乘法中，数据在内存中通常以行优先 (Row-major) 存储。为了实现高效的 $\mathbf{X}^T \mathbf{X}$，底层的 BLAS (Basic Linear Algebra Subprograms) 会使用**分块 (Blocking)** 策略，以最大化 L1/L2 Cache 的命中率。这对于处理 ESL 中提到的大规模数据集至关重要。
|
||
|
||
2. **虚拟内存与稀疏矩阵**：
|
||
|
||
当 $p$ 极高（如文本处理）且使用 Lasso 产生稀疏系数时，系统层面可以采用**稀疏格式 (如 CSR/CSC)** 存储。这不仅节省了内存空间，还避免了大量的 0 值乘法运算，从而绕过了 TLB Miss 和内存带宽瓶颈。
|
||
|
||
3. **多线程与 SIMD 指令集**：
|
||
|
||
现代线性回归库（如 Scikit-learn 的底层）会利用 **AVX-512** 指令集进行向量化加速。在计算残差平方和或梯度下降更新权重时，单条指令可以并行处理 8 或 16 个浮点数。
|
||
|
||
4. **Dropout 的系统模拟**：
|
||
|
||
虽然 ESL 主讲确定性正则化，但 Dropout 实际上在训练阶段通过随机掩码（Masking）模拟了子集选择的过程。在底层实现上，这涉及到快速伪随机数生成器（PRNG）与位运算。 |