正則化與線性分類｜機器學習筆記

本章內容

3.1收縮懲罰
3.2脊迴歸
3.3套索迴歸
3.4子集選擇與 L0
3.5邏輯斯迴歸
3.6線性判別分析
3.7參考資料

第 2 章的子集選擇是在「放或不放」之間做離散的決定。當變數很多、彼此相關，甚至比樣本還多時，這種做法不是運算量爆炸，就是結果很不穩定。收縮方法（shrinkage methods）換了一個角度：保留所有變數，但對係數的大小加上懲罰，讓模型自己決定每個係數該縮多少。

這一章的前半部從一個統一的懲罰目標函數出發，依 $p = 2, 1, 0$ 依序介紹脊迴歸、Lasso 與子集選擇；後半部轉向分類問題，比較兩種最基本的線性分類器：判別式的邏輯斯迴歸，與生成式的線性判別分析。

3.1收縮懲罰Shrinkage Penalty

收縮方法在最小平方的目標上加一項係數大小的懲罰：

\min_{\mathbf{w}} \; \lVert \mathbf{y} - \mathbf{X}\mathbf{w} \rVert_2^2 + \lambda \lVert \mathbf{w} \rVert_p^p

其中 $\lVert \mathbf{w} \rVert_p^p = \sum_j |w_j|^p$ 。 $p = 2$ 是脊迴歸， $p = 1$ 是 Lasso； $p = 0$ 則約定為非零係數的個數 $\lVert \mathbf{w} \rVert_0$ ，對應子集選擇。截距通常不納入懲罰，否則模型的預測會受 $y$ 的平移影響。

這個目標也可以等價地寫成限制式的形式：在 $\lVert \mathbf{w} \rVert_p^p \le t$ 的條件下最小化 RSS。每個 $\lambda$ 都對應某個預算 $t$ ， $\lambda$ 越大，預算越小。

為什麼要懲罰大的係數

係數很大時，輸入的微小變動（包括雜訊）就會被放大成輸出的大幅變動，模型對訓練資料的細節非常敏感，也就是變異很高。懲罰項把係數往 0 拉，換來較穩定的估計。

調整參數 $\lambda \ge 0$ 控制模型複雜度：

$\lambda = 0$ ：沒有懲罰，等同普通最小平方法。
$\lambda$ 增加：收縮效果增強，模型越來越簡單。
$\lambda \to \infty$ ：所有係數被壓到 0，只剩截距。

	Ridge（ $p=2$ ）	Lasso（ $p=1$ ）	子集選擇（ $p=0$ ）
係數收縮	有	有	無
變數選擇	無	有	有
凸最佳化	是（嚴格凸）	是	否
尺度不變	否	否	是

3.2脊迴歸Ridge Regression

取 $p = 2$ ，目標函數可微，對 $\mathbf{w}$ 求導並令其為 0，得到封閉解：

\hat{\mathbf{w}}_{\text{ridge}} = (\mathbf{X}^\top \mathbf{X} + \lambda \mathbf{I})^{-1} \mathbf{X}^\top \mathbf{y}

$\mathbf{X}^\top \mathbf{X}$ 是半正定矩陣，加上 $\lambda \mathbf{I}$ （ $\lambda > 0$ ）之後一定正定、一定可逆。因此脊迴歸在變數高度共線，甚至 $p > n$ 時，仍然有唯一解。處理共線（非正交）的設計矩陣，正是 Hoerl 與 Kennard 最初提出它的動機。

從 SVD 看收縮

若將中心化後的 $\mathbf{X}$ 做奇異值分解 $\mathbf{X} = \mathbf{U}\mathbf{D}\mathbf{V}^\top$ （見第 4 章），脊迴歸的配適值可以寫成

\mathbf{X}\hat{\mathbf{w}}_{\text{ridge}} = \sum_{j} \mathbf{u}_j \, \frac{d_j^2}{d_j^2 + \lambda} \, \mathbf{u}_j^\top \mathbf{y}

普通最小平方法對應收縮因子全為 1。脊迴歸則對每個主成分方向乘上 $d_j^2 / (d_j^2 + \lambda)$ ：奇異值 $d_j$ 越小、也就是資料在該方向變異越小，收縮得越多。共線性造成的不穩定，恰好集中在這些變異很小的方向上。

特性

適合許多小而非零的係數：脊迴歸會把所有係數一起縮小，但不會讓任何係數恰好等於 0。當真實模型中有很多變數各自貢獻一點效果時，它通常比 Lasso 表現好。
有偏但穩定：在有限樣本下，估計量是有偏的；在 $p$ 固定、 $\lambda$ 不隨 $n$ 增加的情況下，懲罰的相對影響隨樣本增加而消失，估計量仍具一致性。
貝氏解讀：脊迴歸的解等於在係數上放常態先驗 $\mathbf{w} \sim N(\mathbf{0}, \tau^2 \mathbf{I})$ 時的最大後驗估計（MAP）。

3.3套索迴歸Lasso

取 $p = 1$ ：

\min_{\mathbf{w}} \; \lVert \mathbf{y} - \mathbf{X}\mathbf{w} \rVert_2^2 + \lambda \lVert \mathbf{w} \rVert_1

絕對值在 0 點不可微，Lasso 一般沒有封閉解，常用座標下降法（coordinate descent）或最小角迴歸（LARS）求解。它最重要的特性是稀疏性：當 $\lambda$ 夠大，部分係數會被精確地壓成 0，因此 Lasso 同時完成了收縮與變數選擇。

幾何直觀

用限制式的形式來看：RSS 的等高線是以最小平方解為中心的橢圓，限制區域則是 $\lVert \mathbf{w} \rVert_p^p \le t$ 。

L2 限制區域是圓（高維時是球），邊界平滑，橢圓碰到它的位置一般不會落在座標軸上，所以係數不會恰好為 0。
L1 限制區域是菱形（高維時是帶有尖角的多面體），尖角都在座標軸上。橢圓往外擴張時，很容易先碰到角落，對應的解就有部分座標為 0。

正交設計下的對照

當 $\mathbf{X}^\top \mathbf{X} = \mathbf{I}$ 時，三種懲罰都有簡單的封閉解。設 $z_j$ 為第 $j$ 個最小平方係數：

方法	估計值	作用
Ridge	$z_j / (1 + \lambda)$	等比例縮小
Lasso	$\operatorname{sign}(z_j)\,(\lvert z_j \rvert - \lambda/2)_+$	軟門檻：先平移，小的直接歸零
子集選擇	$z_j \cdot \mathbf{1}(\lvert z_j \rvert > \sqrt{\lambda})$	硬門檻：保留或刪除，不收縮

這張表把三種方法的差別說得很清楚：Ridge 只縮不刪，子集選擇只刪不縮，Lasso 兩者兼具。

特性與限制

凸最佳化：目標函數是凸的，任何局部最小值都是全域最小值，但不一定嚴格凸； $p > n$ 時解可能不唯一，且最多只會選出 $n$ 個變數。
相關變數群：一群高度相關的變數中，Lasso 傾向任意挑一個、其餘歸零。若希望整群一起保留，可以改用結合 L1 與 L2 懲罰的彈性網路（elastic net）。
選擇一致性有條件：Lasso 在樣本數增加時能否選中真正的變數集合，取決於變數之間的相關結構（irrepresentable condition），並非無條件成立。
貝氏解讀：等於在係數上放拉普拉斯先驗時的 MAP 估計。

實務上，用管線（pipeline）把標準化與模型綁在一起，可以避免忘記轉換測試資料：

import numpy as np
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.linear_model import RidgeCV, LassoCV

ridge = make_pipeline(StandardScaler(), RidgeCV(alphas=np.logspace(-3, 3, 50)))
lasso = make_pipeline(StandardScaler(), LassoCV(cv=5))
lasso.fit(X_train, y_train)
coef = lasso[-1].coef_        # 被壓成 0 的就是被剔除的變數

3.4子集選擇與 L0Subset Selection and L0

$p = 0$ 時，懲罰項是 $\lambda$ 乘上非零係數的個數。這等於說「每多用一個變數要付出固定成本 $\lambda$ 」，被選入的變數則完全不收縮，直接使用最小平方估計值。也就是選擇能力強，但沒有收縮。

因為只計算「有幾個非零係數」，改變變數的單位不影響懲罰，所以 L0 懲罰具尺度不變性。代價是目標函數不連續、非凸，一般情況下求精確解是 NP-hard 的組合最佳化問題。

第 2 章的 $C_p$ 、AIC、BIC 其實都是 L0 懲罰的特例：取 $\lambda = 2\hat\sigma^2$ 對應 $C_p$ 與 AIC，取 $\lambda = \log(n)\,\hat\sigma^2$ 對應 BIC。

搜尋策略

既然無法有效率地求出精確解，就需要不同的搜尋策略：

策略	每一步做什麼	特點
最佳子集（all subset）	窮舉所有 $2^p$ 種組合	全域最佳，但只適用於小 $p$
逐步（stepwise）	評估所有候選變數，加入（或刪除）最好的一個	每步重新配適全部係數，運算量大
串流式（streamwise）	每個變數依序只考慮一次，夠好就加入	順序會影響結果，適合極大或動態產生的特徵集合
分段式（stagewise）	將殘差對一個變數迴歸，只更新該係數	先前係數凍結，每步很快

逐步選擇的候選集合不一定只有原始變數，也可以包含交叉乘積項（交互作用）與高次項。這讓模型更有彈性，但候選數量急遽增加，運算成本與過擬合風險也隨之上升。

串流式選擇適合特徵多到無法一次全部評估，或特徵是邊計算邊產生的情境。每個特徵出現時只決定一次「要不要加入」，之後不再回頭考慮。

前向分段迴歸（forward stagewise regression）每一步找出與目前殘差最相關的變數，把殘差對它做簡單迴歸，並把結果加到該變數的係數上；其他係數維持不變，不重新配適。每一步的計算比逐步選擇便宜很多，但往往需要更多步才能收斂。若每次只前進一個很小的步長，得到的係數路徑與 Lasso 十分接近。這種「每次針對殘差做一點小修正，再累加起來」的做法，正是提升法（boosting）的核心精神：前向分段迴歸可以視為以單一變數線性模型為基底學習器的 L2 boosting（見第 5 章）。

以 MDL 選擇 $\lambda$

除了交叉驗證，也可以用資訊理論來決定 $\lambda$ 。最小描述長度（Minimum Description Length, MDL）原則把學習看成資料壓縮：設資料 $D = \{(x_1, y_1), \ldots, (x_n, y_n)\}$ ，最好的假設是讓「描述假設」加上「在該假設下描述資料」的總位元數最短，

L(D) = \min_{H \in \mathcal{H}} \big[ L(H) + L(D \mid H) \big]

複雜的模型需要較多位元描述自己（ $L(H)$ 大），但能把資料描述得更精簡（ $L(D \mid H)$ 小）；簡單的模型則相反。這個取捨自然地抵抗過擬合。在常見的編碼方式下，每個非零係數大約要花 $\tfrac{1}{2}\log n$ 位元，相當於 BIC 的懲罰；若還要編碼「選的是 $p$ 個特徵中的哪一個」，每個變數再多約 $\log p$ 位元，因此特徵越多，加入變數的門檻越高。

3.5邏輯斯迴歸Logistic Regression

轉到二元分類問題。令標籤 $y \in \{-1, +1\}$ ，邏輯斯迴歸假設

P(y \mid \mathbf{x}, \mathbf{w}) = \sigma(y\,\mathbf{w}^\top \mathbf{x}) = \frac{1}{1 + e^{-y\,\mathbf{w}^\top \mathbf{x}}}

這裡把截距併入 $\mathbf{w}$ （令 $\mathbf{x}$ 的第一個分量為 1）。給定 $n$ 筆獨立資料，對數概似函數是各筆對數機率的總和：

\ell(\mathbf{w}) = \log \prod_{i=1}^{n} \sigma(y_i \mathbf{w}^\top \mathbf{x}_i) = \sum_{i=1}^{n} \log \sigma(y_i \mathbf{w}^\top \mathbf{x}_i) = -\sum_{i=1}^{n} \log\!\left(1 + e^{-y_i \mathbf{w}^\top \mathbf{x}_i}\right)

最大化 $\ell(\mathbf{w})$ 等同於最小化邏輯斯損失（logistic loss），也就是二元交叉熵（見第 6 章）。這是凸問題，但沒有封閉解，通常以牛頓法（即迭代再加權最小平方法，IRLS）或梯度下降求解。

對數勝算是線性的

由上式可得

\log \frac{P(y = +1 \mid \mathbf{x})}{P(y = -1 \mid \mathbf{x})} = \mathbf{w}^\top \mathbf{x}

也就是說，邏輯斯迴歸假設對數勝算（log-odds）是 $\mathbf{x}$ 的線性函數。係數的解讀因此是： $x_j$ 增加一單位，勝算乘上 $e^{w_j}$ 。

線性決策邊界

以 0.5 為門檻分類時，決策邊界是兩類機率相等的地方：

P(y = +1 \mid \mathbf{x}, \mathbf{w}) = P(y = -1 \mid \mathbf{x}, \mathbf{w}) = 0.5 \;\Longleftrightarrow\; \mathbf{w}^\top \mathbf{x} = 0

這是一個超平面，而 $\mathbf{w}$ 是它的法向量：對邊界上任意兩點 $\mathbf{x}_a, \mathbf{x}_b$ ，都有 $\mathbf{w}^\top (\mathbf{x}_a - \mathbf{x}_b) = 0$ ，所以 $\mathbf{w}$ 與邊界上的每個方向正交。一個點離邊界越遠， $|\mathbf{w}^\top \mathbf{x}|$ 越大，模型對它的預測越有把握。

從生成模型的角度也能看出邊界為何是線性的。以 $Y \in \{0, 1\}$ 表示類別，由貝氏定理，

P(Y = 1 \mid \mathbf{x}) = \frac{1}{1 + \exp\!\left( -\log \dfrac{P(Y=1)\,P(\mathbf{x} \mid Y=1)}{P(Y=0)\,P(\mathbf{x} \mid Y=0)} \right)}

只要指數中的對數比值是 $\mathbf{x}$ 的線性函數，後驗機率就具有邏輯斯形式、邊界就是超平面。下一節的 LDA 正是一個滿足這個條件的生成模型。

完全可分的資料

常見誤區Common pitfall

若訓練資料線性完全可分，也就是存在 $\mathbf{w}$ 使所有 $y_i \mathbf{w}^\top \mathbf{x}_i > 0$ ，那麼把 $\mathbf{w}$ 乘上越來越大的常數，每一筆的預測機率都趨近 1，概似函數持續上升卻永遠達不到最大值。MLE 不存在， $\lVert \mathbf{w} \rVert$ 會發散，軟體通常會提示預測機率在數值上等於 0 或 1。

解法是加入正則化。L2 正則化等於在係數上放常態先驗 $\mathbf{w} \sim N(\mathbf{0}, \tau^2 \mathbf{I})$ 後求最大後驗估計（MAP）：最大化 $\ell(\mathbf{w}) - \lVert \mathbf{w} \rVert_2^2 / (2\tau^2)$ 。懲罰項讓目標函數有唯一的有限最大值。

此外，MLE 的漸近性質（近似常態、標準誤可信）需要樣本數遠大於參數個數（ $n \gg p$ ）。當 $p$ 與 $n$ 相近時，即使資料不完全可分，估計也會很不穩定，同樣應該加上正則化。

3.6線性判別分析Linear Discriminant Analysis

邏輯斯迴歸直接為 $P(Y \mid \mathbf{x})$ 建模，屬於判別式模型（discriminative model）。線性判別分析（Linear Discriminant Analysis, LDA）則是生成式模型（generative model）：先為每一類的資料分布 $P(\mathbf{x} \mid Y = k)$ 建模，再用貝氏定理得到後驗機率。

模型假設

LDA 假設在給定類別 $k$ 之下， $\mathbf{x}$ 服從多變量常態分布，而且所有類別共用同一個共變異數矩陣：

\mathbf{x} \mid Y = k \;\sim\; N(\boldsymbol\mu_k, \boldsymbol\Sigma), \qquad P(Y = k) = \pi_k

代入貝氏定理、取對數並刪去與類別無關的項，得到每一類的判別函數：

\delta_k(\mathbf{x}) = \mathbf{x}^\top \boldsymbol\Sigma^{-1} \boldsymbol\mu_k - \tfrac{1}{2} \boldsymbol\mu_k^\top \boldsymbol\Sigma^{-1} \boldsymbol\mu_k + \log \pi_k

把 $\mathbf{x}$ 分到 $\delta_k(\mathbf{x})$ 最大的類別。因為共變異數相同，展開後 $\mathbf{x}$ 的二次項 $\mathbf{x}^\top \boldsymbol\Sigma^{-1} \mathbf{x}$ 在各類別間互相抵消， $\delta_k$ 是 $\mathbf{x}$ 的線性函數，任兩類之間的決策邊界 $\delta_k(\mathbf{x}) = \delta_l(\mathbf{x})$ 也就是一個超平面。

參數以訓練資料估計： $\hat\pi_k = n_k / n$ ， $\hat{\boldsymbol\mu}_k$ 為第 $k$ 類的樣本平均， $\boldsymbol\Sigma$ 則用合併的組內共變異數

\hat{\boldsymbol\Sigma} = \frac{1}{n - K} \sum_{k=1}^{K} \sum_{i:\, y_i = k} (\mathbf{x}_i - \hat{\boldsymbol\mu}_k)(\mathbf{x}_i - \hat{\boldsymbol\mu}_k)^\top

二次判別分析

若放寬假設，讓每一類有自己的共變異數矩陣 $\boldsymbol\Sigma_k$ ，二次項不再抵消，判別函數變為

\delta_k(\mathbf{x}) = -\tfrac{1}{2}\log\lvert\boldsymbol\Sigma_k\rvert - \tfrac{1}{2}(\mathbf{x} - \boldsymbol\mu_k)^\top \boldsymbol\Sigma_k^{-1} (\mathbf{x} - \boldsymbol\mu_k) + \log \pi_k

決策邊界成為二次曲面，稱為二次判別分析（Quadratic Discriminant Analysis, QDA）。QDA 更有彈性，但共變異數的參數從 $p(p+1)/2$ 個增加為 $K \cdot p(p+1)/2$ 個，需要更多資料才能估計穩定。這又是一次偏誤與變異的取捨。

與邏輯斯迴歸比較

LDA 的對數勝算同樣是 $\mathbf{x}$ 的線性函數，所以它和邏輯斯迴歸的模型形式完全相同，差別只在參數怎麼估計：

	邏輯斯迴歸	LDA	QDA
模型類型	判別式	生成式	生成式
對 $\mathbf{x}$ 的假設	無	各類常態、共變異數相同	各類常態、共變異數各異
決策邊界	線性	線性	二次
適合情境	假設不確定、含類別型特徵	假設大致成立、樣本較少	樣本多、各類形狀不同

LDA 使用了 $\mathbf{x}$ 的完整分布資訊，若常態假設大致成立，它的估計比邏輯斯迴歸更有效率，所需樣本更少；在資料完全可分時也不會出現係數發散的問題，並能自然處理多類別。反之，若資料明顯偏離常態（例如有厚尾、離群值或二元特徵），邏輯斯迴歸因為不依賴這些假設，通常更穩健。

3.7參考資料References

James, Witten, Hastie & Tibshirani, An Introduction to Statistical Learning（ISLR），Springer, 2013，第 4、6 章。
Hastie, Tibshirani & Friedman, The Elements of Statistical Learning（ESL），2nd ed., Springer, 2009，第 3、4 章。
Bishop, Pattern Recognition and Machine Learning, Springer, 2006，第 3、4 章。
Hoerl & Kennard, "Ridge Regression: Biased Estimation for Nonorthogonal Problems", Technometrics, 1970。
Tibshirani, "Regression Shrinkage and Selection via the Lasso", Journal of the Royal Statistical Society: Series B, 1996。
Rissanen, "Modeling by Shortest Data Description", Automatica, 1978。
Zhou, Foster, Stine & Ungar, "Streamwise Feature Selection", Journal of Machine Learning Research, 2006。
Fisher, "The Use of Multiple Measurements in Taxonomic Problems", Annals of Eugenics, 1936。