最小二乘問題詳解7：正則化最小二乘

本文系統闡述了正則化最小二乘（嶺估計）的動機、理論推導、求解方法與數值實例，揭示其通過L2懲罰項改善病態問題和過擬合的機制。

1. 引言

在之前的文章《最小二乘問題詳解4：非線性最小二乘》、《最小二乘問題詳解5：非線性最小二乘求解實例》和《最小二乘問題詳解6：梯度下降法》中分別介紹了使用Gauss-Newton方法（簡稱GN方法）和梯度下降法求解最小二乘問題之后，讓我們插入另一個基礎知識：正則化最小二乘（Regularized Least Squares），也就是大家常說的嶺估計（Ridge Estimator），因為接下來要介紹的 Levenberg-Marquardt方法會用到這個思想。

本文討論的嶺估計在機器學習中也常稱為嶺回歸（Ridge Regression）

2. 問題

復習《最小二乘問題詳解2：線性最小二乘求解》中討論的標準線性最小二乘問題：

\[\min_{\theta} \|A\theta - b\|^2 \]

其解為正規方程 $A^T A \theta = A^T b$的解。當$A$列滿秩時，解唯一且為：

\[\theta^* = (A^T A)^{-1} A^T b \]

然而，在實際應用中，直接使用這個解可能會遇到一些問題。

矩陣病態（Ill-conditioning）：
- 矩陣 $A^T A$ 的條件數可能非常大。
- 這意味著即使數據 $b$ 中有微小的擾動，也會導致解 $\theta^*$ 發生劇烈變化，數值不穩定。
- 條件數大的一個常見原因是特征之間高度相關（多重共線性），此時 $A^T A$ 接近奇異，逆矩陣難以精確計算。
過擬合（Overfitting）：
- 當模型參數過多或特征維度很高時，標準最小二乘傾向于擬合訓練數據中的噪聲，導致泛化能力差。
- 解 $\theta^*$ 的模長（范數）可能非常大，表示模型對某些特征賦予了不合理的高權重。
秩虧（Rank Deficiency）：
- 若 $A$ 不是列滿秩（即 $\text{rank}(A) < n$），則 $A^T A$ 是奇異的，無法求逆，正規方程有無窮多解。

矩陣的病態問題詳見6.1節。

為了解決這些問題，我們引入正則化（Regularization）——通過在目標函數中加入一個額外的懲罰項，來“約束”解的行為，使其更穩定、更平滑，并避免過擬合。其實，正則化是一個通用的數學和機器學習思想：在優化問題中，通過向目標函數添加一個額外的“懲罰項”（penalty term），來引導解具有某種期望的性質，比如平滑性、稀疏性、小范數、結構簡單等，從而提高模型的穩定性、泛化能力或可解釋性。

3. 定義

最常用的正則化方法之一是Tikhonov 正則化，其核心思想是在原始的殘差平方和基礎上，加上一個關于參數$\theta$的L2范數平方的懲罰項：

\[\boxed{ \min_{\theta} \left( \|A\theta - b\|^2 + \lambda \|\theta\|^2 \right) } \]

其中：

$\|A\theta - b\|^2$是數據擬合項（data fidelity term），衡量模型對數據的擬合程度。
$\|\theta\|^2 = \theta^T \theta$是正則化項（regularization term），也叫 Tikhonov 項，它懲罰較大的參數值。
$\lambda > 0$是正則化參數（regularization parameter），控制正則化的強度：
- $\lambda \to 0$：正則化作用消失，退化為標準最小二乘。
- $\lambda \to \infty$：正則化主導，迫使 $\theta \to 0$，模型趨于常數零。

直觀理解就是：通過加入正則項，不僅要保證預測誤差小，還要保證模型參數不要太大。這相當于在“擬合數據”和“保持模型簡單”之間做權衡。

4. 求解

將目標函數展開：

\[f(\theta) = (A\theta - b)^T (A\theta - b) + \lambda \theta^T \theta = \theta^T A^T A \theta - 2 b^T A \theta + b^T b + \lambda \theta^T \theta \]

對$\theta$求梯度并令其為零：

\[\nabla_\theta f(\theta) = 2 A^T A \theta - 2 A^T b + 2 \lambda \theta = 0 \]

整理得：

\[(A^T A + \lambda I) \theta = A^T b \]

這就是嶺估計的正規方程。

由于$\lambda > 0$，矩陣$A^T A$是半正定的，而$\lambda I$是正定的，因此$A^T A + \lambda I$是嚴格正定的，從而總是可逆的，無論$A$是否列滿秩！于是，嶺估計的閉式解為：

\[\boxed{ \theta^*_{\text{ridge}} = (A^T A + \lambda I)^{-1} A^T b } \]

可見，嶺估計只是在$A^T A$的對角線上加了一個小量$\lambda$，這相當于“抬升”了所有特征值，使得原本接近零的特征值變得遠離零，從而顯著改善了矩陣的條件數，提高了數值穩定性。

關于正定矩陣的問題詳見6.2節。

從幾何角度看，標準最小二乘是尋找使 $A\theta$ 投影最接近 $b$ 的點；而嶺估計則在此基礎上“收縮”參數空間，使 $\theta$ 向零靠近。這可以理解為給 $\theta$ 的空間加上一個“彈簧”，防止參數跑得太遠。

5. 分解

雖然有了閉式解，但在實際數值計算中，仍然不推薦直接計算$(A^T A + \lambda I)^{-1}$，因為$A^T A$可能病態，顯式構造$A^T A$會損失精度。

5.1 QR分解

將正則化最小二乘問題轉化為一個更大的最小二乘問題：

\[\min_{\theta} \left\| \begin{bmatrix} A \\ \sqrt{\lambda} I \end{bmatrix} \theta - \begin{bmatrix} b \\ 0 \end{bmatrix} \right\|^2= \|A\theta - b\|^2 + \lambda \|\theta\|^2 \]

這是一個標準的最小二乘問題，可以用 QR 分解高效求解。

令：

\[\tilde{A} = \begin{bmatrix} A \\ \sqrt{\lambda} I \end{bmatrix},\quad \tilde = \begin{bmatrix} b \\ 0 \end{bmatrix} \]

對$\tilde{A}$做QR分解：$\tilde{A} = \tilde{Q} \tilde{R}$

則解為：

\[\theta^*_{\text{ridge}} = \tilde{R}^{-1} \tilde{Q}_1^T b \]

其中$\tilde{Q}_1$ 是 $\tilde{Q}$的前 $m$ 行（對應 $A$ 部分）。

5.2 SVD分解

設 $A = U \Sigma V^T$ 是 $A$ 的 SVD。

代入嶺估計的閉式解：

\[\theta^*_{\text{ridge}} = (V \Sigma^T U^T U \Sigma V^T + \lambda I)^{-1} V \Sigma^T U^T b = (V (\Sigma^T \Sigma + \lambda I) V^T)^{-1} V \Sigma^T U^T b \]

利用 $V^T V = I$，得：

\[\theta^*_{\text{ridge}} = V (\Sigma^T \Sigma + \lambda I)^{-1} V^T V \Sigma^T U^T b = V (\Sigma^T \Sigma + \lambda I)^{-1} \Sigma^T U^T b \]

記 $\Sigma^T \Sigma = \text{diag}(\sigma_1^2, \dots, \sigma_n^2)$，則：

\[\theta^*_{\text{ridge}} = V \begin{bmatrix} \frac{\sigma_1}{\sigma_1^2 + \lambda} & & \\ & \ddots & \\ & & \frac{\sigma_n}{\sigma_n^2 + \lambda} \end{bmatrix} U^T b \]

即：

\[\boxed{ \theta^*_{\text{ridge}} = \sum_{i=1}^r \frac{\sigma_i}{\sigma_i^2 + \lambda} (u_i^T b) v_i } \]

對比標準最小二乘解（SVD 形式）：

\[\theta^* = \sum_{i=1}^r \frac{1}{\sigma_i} (u_i^T b) v_i \]

可見，嶺估計通過因子 $\frac{\sigma_i}{\sigma_i^2 + \lambda}$ 對小奇異值方向進行了壓制。當 $\sigma_i \to 0$ 時，標準解會爆炸（$1/\sigma_i \to \infty$），但嶺估計中該項趨于 0，從而避免了對噪聲方向的過度放大。

6. 補充

有一些《線性代數》、《矩陣論》相關的知識筆者也忘記了，這里就總結一下。如果有的讀者很熟悉，可以直接略過。

6.1 病態矩陣

病態矩陣指的是矩陣條件數（Condition Number）很大的矩陣。矩陣病態會導致輸入數據的微小擾動（如 $b$ 或 $A$ 的舍入誤差），線性方程組 $A\theta = b$ 解就會劇烈變化。換句話說，系統對噪聲極度敏感，數值計算中結果不可靠。

對于一個可逆矩陣 $A \in \mathbb{R}^{n \times n}$，其譜條件數（Spectral Condition Number）定義為：

\[\kappa(A) = \frac{\sigma_{\max}(A)}{\sigma_{\min}(A)} \]

其中：
$\sigma_{\max}(A)$ 是 $A$ 的最大奇異值，
$\sigma_{\min}(A)$ 是 $A$ 的最小奇異值。

注意這個定義也適用于非方陣 $A \in \mathbb{R}^{m \times n}$（$m \geq n$），只要 $A$ 列滿秩。條件數 $\kappa(A)$ 的含義如下：

$\kappa(A) \approx 1$ 良態，解非常穩定
$\kappa(A) < 10^2$ 良態
$10^2 \leq \kappa(A) < 10^6$ 中等病態
$\kappa(A) \geq 10^6$ 嚴重病態，浮點計算可能完全失效
$\kappa(A) > 10^{14}$ 雙精度浮點數（約16位有效數字）完全失效

任何實矩陣 $A \in \mathbb{R}^{m \times n}$ 都可以進行奇異值分解（SVD）：

\[A = U \Sigma V^T \]

其中：
$U \in \mathbb{R}^{m \times m}$ 是左奇異向量矩陣（正交），
$V \in \mathbb{R}^{n \times n}$ 是右奇異向量矩陣（正交），
$\Sigma \in \mathbb{R}^{m \times n}$ 是對角矩陣，對角線元素為奇異值(Singular Value) $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r \geq 0$，$r = \min(m,n)$。

奇異值表示矩陣 $A$ 在各個正交方向上的“拉伸”程度。如果 $\sigma_{\min} \to 0$，說明 $A$ 把某個方向“壓扁”了，接近奇異，也就是矩陣病態。

6.2 正定矩陣

設 $A \in \mathbb{R}^{n \times n}$ 是一個實對稱矩陣（即 $A = A^T$），我們有如下定義：

如果對所有非零向量 $x \in \mathbb{R}^n, x \ne 0$，都有：

\[x^T A x > 0 \]

則稱 $A$ 是正定矩陣。

如果對所有非零向量 $x \in \mathbb{R}^n, x \ne 0$，都有：

\[x^T A x \ge 0 \]

則稱 $A$ 是半正定矩陣。

對于實對稱矩陣 $A$，我們可以進行譜分解（特征值分解）：

\[A = Q \Lambda Q^T \]

其中 $Q$ 是正交矩陣（列是特征向量），$\Lambda = \mathrm{diag}(\lambda_1, \dots, \lambda_n)$ 是對角矩陣，對角元素是特征值。

那么：

$A$ 正定 $\Longleftrightarrow$ 所有特征值 $\lambda_i > 0$
$A$ 半正定 $\Longleftrightarrow$ 所有特征值 $\lambda_i \ge 0$

既然正定矩陣的所有特征值都 大于零，那么意味著正定矩陣是滿秩，也就是正定矩陣一定可逆。

回到嶺估計中的 $A^T A + \lambda I$：

$A^T A$ 是半正定的：
- 因為對任意 $x$，有 $x^T A^T A x = \|Ax\|^2 \ge 0$
- 所以它的所有特征值 $\ge 0$
加上 $\lambda I$（其中 $\lambda > 0$）后：
- 新矩陣是 $A^T A + \lambda I$
- 它的特征值變為：原來的每個特征值 $\lambda_i $ 變成 $\lambda_i + \lambda$
- 原來最小可能是 0，現在最小是 $\lambda > 0$
- 所以所有特征值 $> 0$ ? 正定 ? 可逆

因此，$(A^T A + \lambda I)^{-1}$ 總是存在的，無論 $A$ 是否列滿秩。這正是嶺估計的精髓所在：通過加一個小的正數 $\lambda$ 到對角線上，把原本可能奇異（不可逆）的 $A^T A$ “修復”成一個嚴格正定、可逆的矩陣，從而保證了解的唯一性和數值穩定性。

7. 實例

如果線性最小二乘問題的設計矩陣$A$接近線性相關，那么普通方法求得的解不穩定，可以使用嶺估計來給出穩定解。代碼實現如下：

#include <Eigen/Dense>
#include <iostream>
#include <random>
#include <vector>

using namespace Eigen;
using namespace std;

int main() {
  // 設置隨機數生成器
  default_random_engine gen;
  normal_distribution<double> noise(0.0, 0.5);  // 噪聲 ~ N(0, 0.5)

  // 數據生成：y = x1 + x2 + 0.1*x3 + noise
  // 但 x3 ≈ x1 + x2 （高度相關，造成病態）
  int n_samples = 20;
  int n_features = 3;
  MatrixXd A(n_samples, n_features);
  VectorXd b(n_samples);

  for (int i = 0; i < n_samples; ++i) {
    double x1 = (double)rand() / RAND_MAX * 10;
    double x2 = (double)rand() / RAND_MAX * 10;
    double x3 = x1 + x2 + (double)rand() / RAND_MAX * 0.1;  // x3 ≈ x1 + x2

    A(i, 0) = x1;
    A(i, 1) = x2;
    A(i, 2) = x3;

    double true_y = 1.0 * x1 + 1.0 * x2 + 0.1 * x3;
    b(i) = true_y + noise(gen);  // 加噪聲
  }

  //使用 SVD 計算條件數
  BDCSVD<MatrixXd> svd(A, ComputeThinU | ComputeThinV);
  cout << "Condition number of A: "
       << svd.singularValues()(0) / svd.singularValues()(2)
       << endl;  // 假設 3 個奇異值

  // 普通最小二乘解：theta = (A^T A)^{-1} A^T b
  VectorXd theta_ols = A.bdcSvd(ComputeThinU | ComputeThinV).solve(b);

  // 嶺回歸解：theta = (A^T A + λI)^{-1} A^T b
  MatrixXd AtA = A.transpose() * A;
  VectorXd Atb = A.transpose() * b;
  double lambda = 0.01;
  MatrixXd ridge_matrix =
      AtA + lambda * MatrixXd::Identity(n_features, n_features);
  VectorXd theta_ridge = ridge_matrix.ldlt().solve(Atb);

  // 輸出結果
  cout << "True weights: [1.0, 1.0, 0.1]" << endl;
  cout << "OLS weights:  " << theta_ols.transpose() << endl;
  cout << "Ridge weights:" << theta_ridge.transpose() << endl;

  return 0;
}

這里可以看到，我們使第三個已知參數向量，可以用第一個已知參數向量和第二個已知參數向量接近線性表示（$x3 ≈ x1 + x2$），那么設計矩陣就接近線性相關，這個設計矩陣就是病態的。分別用普通最小二乘求解和嶺估計來求解，最后結果如下：

Condition number of A: 715.286
True weights: [1.0, 1.0, 0.1]
OLS weights:    2.00569   2.03977 -0.938346
Ridge weights: 1.02399  1.05935 0.038262

理論上來說，使用QR/SVD方法可以一定程度上解決矩陣的病態問題。但是從這個實例結果可以看到，即使使用最穩健的 SVD 方法求解普通最小二乘，參數估計仍嚴重偏離真實值。這是因為問題本身的結構特征高度相關，導致參數不可識別。

相比之下，嶺估計通過引入正則化項$λI$，顯著改善了矩陣的條件數，給出了穩定且接近真實的參數估計。嶺估計通過犧牲一定的精度，提升模型的泛化能力，保證在噪聲存在下仍能穩定預測。嶺估計的另外一個問題是正則化參數$\lambda$不太好進行給定，往往需要一些先驗經驗的輔助才能確定，有機會再進一步進行討論了。

posted @ 2025-10-31 22:07 charlee44 閱讀(69) 評論(0) 收藏舉報

刷新頁面返回頂部

人生海海山山而川

分說，不分說，不由分說！

最小二乘問題詳解7：正則化最小二乘

1. 引言

2. 問題

3. 定義

4. 求解

5. 分解

5.1 QR分解

5.2 SVD分解

6. 補充

6.1 病態矩陣

6.2 正定矩陣

7. 實例

公告

人生海海 山山而川

分說，不分說，不由分說！

最小二乘問題詳解7：正則化最小二乘

1. 引言

2. 問題

3. 定義

4. 求解

5. 分解

5.1 QR分解

5.2 SVD分解

6. 補充

6.1 病態矩陣

6.2 正定矩陣

7. 實例

公告

人生海海山山而川

分說，不分說，不由分說！