基于特征选择的稀疏学习算法：LASSO回归的原理与坐标下降法（Coordinate Descent）求解过程
字数 3081 2025-12-22 09:33:26

基于特征选择的稀疏学习算法：LASSO回归的原理与坐标下降法（Coordinate Descent）求解过程

题目描述

LASSO（Least Absolute Shrinkage and Selection Operator）回归是一种线性回归的扩展，它在普通最小二乘（OLS）损失函数基础上增加了一个L1范数惩罚项，旨在同时进行参数估计和特征选择。本题目要求详细解释LASSO回归的数学模型、其如何通过引入稀疏性实现特征选择，并重点阐述坐标下降法（Coordinate Descent）这一高效优化算法的具体迭代求解过程。

解题过程

第一步：LASSO回归的数学模型与优化目标

  1. 问题设定：

    • 给定数据集 \(\{ (x_i, y_i) \}_{i=1}^{n}\)，其中 \(x_i \in \mathbb{R}^p\) 为特征向量，\(y_i \in \mathbb{R}\) 为响应变量。
    • 假设线性关系：\(y_i = \beta_0 + \sum_{j=1}^{p} \beta_j x_{ij} + \epsilon_i\)，其中 \(\epsilon_i\) 为噪声。

  2. 目标函数：

    • LASSO回归的优化目标为最小化以下损失函数：

\[ \min_{\beta_0, \beta} \frac{1}{2n} \sum_{i=1}^{n} \left( y_i - \beta_0 - \sum_{j=1}^{p} \beta_j x_{ij} \right)^2 + \lambda \sum_{j=1}^{p} |\beta_j| \]

 - 第一项为均方误差（MSE），衡量模型拟合数据的能力。
 - 第二项为L1正则化项（$ \lambda \sum |\beta_j| $），其中 $ \lambda > 0 $ 是正则化强度参数，控制惩罚力度。
 - L1惩罚的几何特性（菱形约束域）使得最优解中部分系数 $ \beta_j $ 恰好为0，从而实现特征选择。
  1. 稀疏性解释：
    • 当 \(\lambda\) 较大时，惩罚项主导优化过程，迫使某些 \(\beta_j\) 收缩至0，模型仅保留重要特征。
    • 这解决了普通线性回归在高维数据（\(p > n\)）中过拟合的问题，并提升了模型可解释性。
第二步：坐标下降法的基本思想

由于LASSO的目标函数非平滑（L1项在0点不可导），传统梯度下降法不适用。坐标下降法通过以下策略高效求解：

  1. 分而治之：

    • 每次迭代只优化一个坐标（即一个系数 \(\beta_j\)），固定其他所有坐标。
    • 依次循环更新所有坐标，直至收敛。

  2. 优势：

    • 将多元优化分解为一系列一元优化问题，每个子问题有闭式解（或简单迭代解）。
    • 特别适合高维稀疏问题，计算效率高。
第三步：坐标下降法求解LASSO的详细步骤
  1. 预处理：
    • 假设特征已中心化（均值为0），截距项 \(\beta_0\) 可单独估计为 \(\bar{y}\)，后续仅优化 \(\beta\)。
    • 将目标函数重写为：

\[ J(\beta) = \frac{1}{2n} \| y - X\beta \|^2 + \lambda \|\beta\|_1 \]

  1. 单变量子问题推导：
    • 固定 \(\beta_k (k \ne j)\)，优化 \(\beta_j\) 时，目标函数简化为：

\[ J(\beta_j) = \frac{1}{2n} \sum_{i=1}^{n} \left( r_i^{(j)} - x_{ij}\beta_j \right)^2 + \lambda |\beta_j| + \text{常数} \]

 其中 $ r_i^{(j)} = y_i - \sum_{k \ne j} x_{ik}\beta_k $ 是剔除特征 $ j $ 后的残差。
  • 令 \(z_j = \frac{1}{n} \sum_{i=1}^{n} x_{ij} r_i^{(j)}\)，\(\rho_j = \frac{1}{n} \sum_{i=1}^{n} x_{ij}^2\)（通常特征已标准化使得 \(\rho_j = 1\)）。
  • 则关于 \(\beta_j\) 的一维优化问题等价于：

\[ \min_{\beta_j} \frac{1}{2} \rho_j (\beta_j - \frac{z_j}{\rho_j})^2 + \lambda |\beta_j| \]

  1. 软阈值算子（Soft-thresholding）：
    • 上述问题有闭式解，称为软阈值算子：

\[ \beta_j^* = S_{\lambda/\rho_j}(z_j / \rho_j) = \frac{1}{\rho_j} \cdot \text{sign}(z_j) \cdot \max(|z_j| - \lambda, 0) \]

  • 直观解释：
    • 若 \(|z_j| \le \lambda\)，则 \(\beta_j^* = 0\)（系数被压缩为0）。
    • 若 \(|z_j| > \lambda\)，则 \(\beta_j^* = (z_j - \lambda \cdot \text{sign}(z_j)) / \rho_j\)（系数向0收缩）。
  1. 完整坐标下降算法流程：
    • 初始化：设 \(\beta^{(0)} = 0\)，计算初始残差 \(r = y\)。
    • 迭代更新（第 \(t\) 轮）：
      1. 对 \(j = 1, 2, \dots, p\)：
        • 计算 \(z_j = \frac{1}{n} \sum_{i=1}^{n} x_{ij} r_i + \beta_j^{(t-1)}\)（注意残差中已包含当前 \(\beta_j\) 的贡献）。
        • 更新 \(\beta_j^{(t)} = S_{\lambda}(z_j)\)（假设特征标准化，\(\rho_j = 1\)）。
        • 更新残差：\(r_i \leftarrow r_i + x_{ij} (\beta_j^{(t-1)} - \beta_j^{(t)})\)。
      2. 检查收敛条件（如系数变化量小于阈值 \(\epsilon\) 或目标函数下降不明显）。
    • 输出：稀疏系数向量 \(\beta^*\)。
第四步：算法收敛性与复杂度分析

  1. 收敛性：

    • LASSO目标函数为凸函数（虽不可导），坐标下降法能保证收敛到全局最优解（因每个坐标更新均严格下降）。
    • 实际中通常迭代10-20轮即可达到稳定。

  2. 计算复杂度：

    • 每轮迭代需更新 \(p\) 个系数，每次更新计算 \(z_j\) 代价为 \(O(n)\)。
    • 总体复杂度为 \(O(T \cdot n \cdot p)\)，其中 \(T\) 为迭代轮数。通过维护残差向量，避免了重复计算矩阵乘法，效率远高于直接求解优化问题。

总结

LASSO回归通过L1正则化自动实现特征选择，坐标下降法利用其目标函数的可分特性，将多元优化分解为一系列带软阈值闭式解的一元问题，高效求解稀疏系数。该方法兼具计算效率与模型可解释性，是处理高维数据的核心工具之一。

基于特征选择的稀疏学习算法：LASSO回归的原理与坐标下降法（Coordinate Descent）求解过程 题目描述 LASSO（Least Absolute Shrinkage and Selection Operator）回归是一种线性回归的扩展，它在普通最小二乘（OLS）损失函数基础上增加了一个L1范数惩罚项，旨在同时进行参数估计和特征选择。本题目要求详细解释LASSO回归的数学模型、其如何通过引入稀疏性实现特征选择，并重点阐述坐标下降法（Coordinate Descent）这一高效优化算法的具体迭代求解过程。 解题过程 第一步：LASSO回归的数学模型与优化目标 问题设定 ： 给定数据集 \( \{ (x_ i, y_ i) \}_ {i=1}^{n} \)，其中 \( x_ i \in \mathbb{R}^p \) 为特征向量，\( y_ i \in \mathbb{R} \) 为响应变量。 假设线性关系：\( y_ i = \beta_ 0 + \sum_ {j=1}^{p} \beta_ j x_ {ij} + \epsilon_ i \)，其中 \( \epsilon_ i \) 为噪声。 目标函数 ： LASSO回归的优化目标为最小化以下损失函数： \[ \min_ {\beta_ 0, \beta} \frac{1}{2n} \sum_ {i=1}^{n} \left( y_ i - \beta_ 0 - \sum_ {j=1}^{p} \beta_ j x_ {ij} \right)^2 + \lambda \sum_ {j=1}^{p} |\beta_ j| \] 第一项为均方误差（MSE），衡量模型拟合数据的能力。 第二项为L1正则化项（\( \lambda \sum |\beta_ j| \)），其中 \( \lambda > 0 \) 是正则化强度参数，控制惩罚力度。 L1惩罚的几何特性（菱形约束域）使得最优解中部分系数 \( \beta_ j \) 恰好为0，从而实现特征选择。 稀疏性解释 ： 当 \( \lambda \) 较大时，惩罚项主导优化过程，迫使某些 \( \beta_ j \) 收缩至0，模型仅保留重要特征。 这解决了普通线性回归在高维数据（\( p > n \)）中过拟合的问题，并提升了模型可解释性。 第二步：坐标下降法的基本思想 由于LASSO的目标函数非平滑（L1项在0点不可导），传统梯度下降法不适用。坐标下降法通过以下策略高效求解： 分而治之 ： 每次迭代只优化一个坐标（即一个系数 \( \beta_ j \)），固定其他所有坐标。 依次循环更新所有坐标，直至收敛。 优势 ： 将多元优化分解为一系列一元优化问题，每个子问题有闭式解（或简单迭代解）。 特别适合高维稀疏问题，计算效率高。 第三步：坐标下降法求解LASSO的详细步骤 预处理 ： 假设特征已中心化（均值为0），截距项 \( \beta_ 0 \) 可单独估计为 \( \bar{y} \)，后续仅优化 \( \beta \)。 将目标函数重写为： \[ J(\beta) = \frac{1}{2n} \| y - X\beta \|^2 + \lambda \|\beta\|_ 1 \] 单变量子问题推导 ： 固定 \( \beta_ k (k \ne j) \)，优化 \( \beta_ j \) 时，目标函数简化为： \[ J(\beta_ j) = \frac{1}{2n} \sum_ {i=1}^{n} \left( r_ i^{(j)} - x_ {ij}\beta_ j \right)^2 + \lambda |\beta_ j| + \text{常数} \] 其中 \( r_ i^{(j)} = y_ i - \sum_ {k \ne j} x_ {ik}\beta_ k \) 是剔除特征 \( j \) 后的残差。 令 \( z_ j = \frac{1}{n} \sum_ {i=1}^{n} x_ {ij} r_ i^{(j)} \)，\( \rho_ j = \frac{1}{n} \sum_ {i=1}^{n} x_ {ij}^2 \)（通常特征已标准化使得 \( \rho_ j = 1 \)）。 则关于 \( \beta_ j \) 的一维优化问题等价于： \[ \min_ {\beta_ j} \frac{1}{2} \rho_ j (\beta_ j - \frac{z_ j}{\rho_ j})^2 + \lambda |\beta_ j| \] 软阈值算子（Soft-thresholding） ： 上述问题有闭式解，称为软阈值算子： \[ \beta_ j^* = S_ {\lambda/\rho_ j}(z_ j / \rho_ j) = \frac{1}{\rho_ j} \cdot \text{sign}(z_ j) \cdot \max(|z_ j| - \lambda, 0) \] 直观解释： 若 \( |z_ j| \le \lambda \)，则 \( \beta_ j^* = 0 \)（系数被压缩为0）。 若 \( |z_ j| > \lambda \)，则 \( \beta_ j^* = (z_ j - \lambda \cdot \text{sign}(z_ j)) / \rho_ j \)（系数向0收缩）。 完整坐标下降算法流程 ： 初始化 ：设 \( \beta^{(0)} = 0 \)，计算初始残差 \( r = y \)。 迭代更新 （第 \( t \) 轮）： 对 \( j = 1, 2, \dots, p \)： 计算 \( z_ j = \frac{1}{n} \sum_ {i=1}^{n} x_ {ij} r_ i + \beta_ j^{(t-1)} \)（注意残差中已包含当前 \( \beta_ j \) 的贡献）。 更新 \( \beta_ j^{(t)} = S_ {\lambda}(z_ j) \)（假设特征标准化，\( \rho_ j = 1 \)）。 更新残差：\( r_ i \leftarrow r_ i + x_ {ij} (\beta_ j^{(t-1)} - \beta_ j^{(t)}) \)。 检查收敛条件（如系数变化量小于阈值 \( \epsilon \) 或目标函数下降不明显）。 输出 ：稀疏系数向量 \( \beta^* \)。 第四步：算法收敛性与复杂度分析 收敛性 ： LASSO目标函数为凸函数（虽不可导），坐标下降法能保证收敛到全局最优解（因每个坐标更新均严格下降）。 实际中通常迭代10-20轮即可达到稳定。 计算复杂度 ： 每轮迭代需更新 \( p \) 个系数，每次更新计算 \( z_ j \) 代价为 \( O(n) \)。 总体复杂度为 \( O(T \cdot n \cdot p) \)，其中 \( T \) 为迭代轮数。通过维护残差向量，避免了重复计算矩阵乘法，效率远高于直接求解优化问题。 总结 LASSO回归通过L1正则化自动实现特征选择，坐标下降法利用其目标函数的可分特性，将多元优化分解为一系列带软阈值闭式解的一元问题，高效求解稀疏系数。该方法兼具计算效率与模型可解释性，是处理高维数据的核心工具之一。