3 第三章 回归的线性方法

[逻辑架构图]

线性回归知识体系的演进逻辑遵循“从无约束到有约束，从离散选择到连续收缩”的路径：

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+N{p}^2)$。当特征数 $p$ 很大时，矩阵往往是病态的 (Ill-conditioned)。

    SVD 分解视角：$\mathbf{X}=\mathbf{UD}{\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(N{p}^2)$)，极其高效。

F. 派生输入：PCA 与 PLS

• 原本内容：通过线性/非线性变换构造新特征。偏最小二乘 (PLS) 在低维子空间寻找最大解释能力。

• 深度整理：

  • 主成分回归 (PCR)：先做 PCA，选前 $k$ 个主成分做回归。

  • 偏最小二乘 (PLS)：在降维时考虑了 $y$ 的信息。

• {扩充部分}：

  无监督 vs 有监督：PCA 只看 $\mathbf{X}$ 的协方差结构（无监督），可能丢弃掉方差虽小但对 $y$ 预测至关重要的信号。而 PLS 是有监督的，它构造的方向 $z_m=\sum {\varphi }_{mj}{x}_j$ 是为了最大化 $\text{Var}(\mathbf{X}\varphi )\cdot {\text{Corr}}^2(y,\mathbf{X}\varphi )$。

  计算权衡：虽然 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）与位运算。