防止過擬合策略——正則化

05-08

本文主要討論常見的L1和L2正則化的定義，並推導正則化公式的來源，最後分析兩種正則的效果。

範數

過擬合是機器學習中一個比較常見的問題，而正則化是解決模型過擬合的一種手段。我們先看一下範數的定義：

Going a bit further, we define $||x||_p$ as a "p-norm". Given $x$ , a vector with $i$ components, a p-norm is defined as:
$|| x ||_p = left(sum_i |x_i|^p ight)^{1/p}$
The simplest norm conceptually is Euclidean distance. This is what we typically think of as distance between two points in space:

$|| x ||_2 = sqrt{left(sum_i x_i^2 ight)} = sqrt{x1^2 + x2^2 + ldots + xi^2}$
Another common norm is taxicab distance, which is the 1-norm:
$|| x ||_1 = sum_i |x_i| = |x_1| + |x_2| + ldots + |x_i|$
Taxicab distance is so-called because it emulates moving between two points as though you are moving through the streets of Manhattan in a taxi cab. Instead of measuring the distance "as the crow flies" it measures the right-angle distance between two points:

正則化（Regularization）是機器學習中一種常用的技術，其主要目的是控制模型複雜度，減小過擬合。最基本的正則化方法是在原目標（代價）函數中添加懲罰項，對複雜度高的模型進行「懲罰」。其數學表達形式為：

$ilde{J}(w;X,y)=J(w;X,y)+alpha Omega (w)$

式中：

$X，y$ 為訓練樣本和相應標籤；
$w$ 為權重係數向量；
$J()$ 為目標函數；
$Omega(w)$ 為懲罰項，即模型「規模」的某種度量；
$alpha$ 控制正則化強弱。

不同的 $Omega$ 函數對權重 $w$ 的最優解有不同的偏好，因此會產生不同的正則化效果，最常用的 $Omega$ 函數有兩種，即 $l_1$ 範數和 $l_2$ 範數，稱為 $l_1$ 正則化和 $l_2$ 正則化：

$l_1: Omega (w) = || w ||_1 = sum_{i=1}^k |w_i|$

$l_2: Omega (w) = || w ||_2 = sum_{i=1}^k w_i^2$

帶有L1正則化的回歸模型通常被稱為Lasso Regression，帶有L2正則化的回歸模型通常被稱為Ridge Regression。

L1正則化和L2正則化主要的區別在於，L1正比於參數的絕對值，而L2正比於參數的平方。這導致了兩種正則化方式會產生不同的效果。

公式來源分析

基於約束條件的最優化

對於模型權重係數 $w$ 求解釋通過最小化目標函數實現的，即求解：

$min_wJ(w;X,y)$

通常情況下，模型複雜度與係數 $w$ 的個數成線性關係：即 $w$ 數量越多，模型越複雜。因此，為了限制模型的複雜度，很自然的想法就是減少係數 $w$ 的個數，即讓 $w$ 向量中一些元素為0或者說限制 $w$ 中非零元素的數量。因此，我們可以在原優化問題中加入一個約束條件：

$min_wJ(w;X,y), s.t. ||w||_0 leq C$

式中， $||cdot||_0$ 範數表示向量中非零元素的個數，但由於該問題是一個NP問題，不易求解，為此我們可以放鬆一下約束條件，為了達到近似效果，我們不嚴格要求某些權重 $w$ 為0，而是要求權重 $w$ 應接近於0，即盡量小。從而可用 $l_1、l_2$ 範數來近似 $l_0$ 範數，即：

$min_wJ(w;X,y), s.t. ||w||_1 leq C$ 或

$min_wJ(w;X,y), s.t. ||w||_2^2 leq C$ （為了後續方便處理，對 $||w||_2$ 進行平方）

利用拉格朗日運算元法，我們可將上述帶約束條件的最優化問題轉換為不帶約束項的優化問題，構建拉格朗日函數：

$minwJ(w;X,y) + alpha^*||w||_1$ 或

$min_wJ(w;X,y) + alpha^*||w||2^2$

因此，我們得到了對 $l_1、l_2$ 正則化的第一種理解：

$l_1$ 正則化等價於在原優化目標函數中增加約束條件 $||w||_1 leq C$
$l_2$ 正則化等價於在原優化目標函數中增加約束條件 $||w||_2^2 leq C$

最大後驗概率估計

在最大似然估計中，假設權重 $w$ 是未知的參數，從而求得對數似然函數：

$l(w)=log[P(y|X;w)]=log[prod_iP(y^i|x^i;w)]$

通過假設 $y^i$ 的不同概率分布，即可得到不同的模型，例如若假設 $y^isim N(w^Tx^i, sigma^2)$ 的高斯分布，則有：

$l(w)=log[prod_ifrac{1}{sqrt {2pi}sigma}e^{-frac{(y^i-w^Tx^i)^2}{2sigma^2}}]=-frac{1}{2sigma^2}sum_i(y_i-w^Tx^i)^2+C$

可令 $J(w;X,y) = -l(w)$

在最大後驗概率估計中，則將權重 $w$ 看做隨機變數，也具有某種分布，從而有：

$p(w|X,y)=frac{P(w,X,y)}{P(X,y)}=frac{P(X,y|w)P(w)}{P(X,y)}propto P(y|X,w)P(w)$

對上述取對數有：

$MAP = logP(y|X,w)P(w) = logP(y|X,w)+logP(w)$

可以看到，後驗概率在似然函數的基礎上增加一項 $logP(w)，P(w)$ 的意義是對權重係數 $w$ 的概率分布的先驗假設，在收集到訓練樣本 ${X,y}$ 後，則可根據 $w$ 在 ${X,y}$ 下的後驗概率對 $w$ 進行修改正，從而做出對 $w$ 更好地估計。

若假設 $w_j$ 的先驗分布是均值為0的高斯分布，即 $w_jsim N(0, sigma^2)$ ，則有：

$logP(w) = logprod_jP(w_j)=logprod_j[frac{1}{sqrt{2pi}sigma}e^{-frac{(w_j)^2}{2sigma^2}}]=-frac{1}{2sigma^2}sum_jw_j^2+C$

可以看到，在高斯分布下 $logP(w)$ 的效果等價於在代價函數中增加 $l_2$ 正則項。

若假設 $w_j$ 服從均值為0、參數為 $a$ 的拉普拉斯分布，即：

$P(w_j)=frac{1}{sqrt{2a}}e^{frac{-|w_j|}{a}}$

則有：

$logP(w) = logprod_jfrac{1}{sqrt{2a}}e^{frac{-|w_j|}{a}}=-frac{1}{a}sum_j|wj|+C$

可以看到，在拉普拉斯分布下 $logP(w)$ 的效果等價於在代價函數中增加 $l_1$ 正則化。

因此，我們得到對於 $l_1、l_2$ 正則化的第二種理解：

$l_1$ 正則化可通過假設權重 $w$ 的先驗分布為拉普拉斯分布，由最大後驗概率估計導出；
$l_2$ 正則化可通過假設權重 $w$ 的先驗分布為高斯分布，由最大後驗概率估計導出。

正則化效果理解

直觀理解

有了正則化公式來源分析，我們現在從優化的角度來看一下正則化對目標函數的影響。考慮帶約束條件的優化解釋，對 $l_2$ 正則化為：

$min_w J(w;X,y) s.t. ||w||_2 leq C$

該問題的求解示意圖如下：

圖中橢圓為原目標函數 $J(w)$ 的一條等高線，圓為半徑 $sqrt{C}$ 的 $l_2$ 範數球。由於約束條件的限制， $w$ 必須位於 $l_2$ 範數球內。考慮邊界上的一點 $w$ ，圖中藍色箭頭為 $J(w)$ 在該處的梯度方向 $riangledown J(w)$ ，紅色箭頭為 $l_2$ 範數球在該處的法線方向。由於 $w$ 不能離開邊界（否則就會違反約束條件），因為在使用梯度下降法更新 $w$ 時，只能朝 $riangledown J(w)$ 在範數球上 $w$ 處的切線方向更新，即圖中的綠色箭頭的方向。如此 $w$ 將沿著邊界移動，當 $riangledown J(w)$ 與範數球上 $w$ 處的切線方向更新，即圖中綠色箭頭的方向。如果 $w$ 將沿著邊界移動，當 $riangledown J(w)$ 與範數球上 $w$ 處的法線平行時，此時， $riangledown J(w)$ 在切線方向的分量為0， $w$ 將無法繼續移動，從而達到最優解 $w^*$ （圖中紅色點所示）。

對於 $l_1$ 正則化：

$min_w J(w;X,y) s.t. ||w||_1 leq C$

同理，其求解示意圖如下所示：

其主要差別在於 $l_1、l_2$ 範數球的形狀差異。由於此時每條邊界上 $w$ 的切線和法線方向保持不變，在圖中 $w$ 一直朝著 $riangledown J(w)$ 的切線方向的分量沿著邊界向左上移動。當 $w$ 跨過頂點到達 $w$ 處時， $riangledown J(w)$ 在切線方向的分量變為右上方，因而 $w$ 將朝右上方移動。最終， $w$ 將穩定在頂點處，達到最優解 $w^*$ ，此時，可以看到 $w_1=0$ ，這也就是採用 $l_1$ 範數會使得 $w$ 產生稀疏性的原因。

以上的分析雖然是基於二維的情況，但不難將其推廣到多維度情況，其主要目的是為了直觀地說明 $l_1、l_2$ 正則化最優解的差異，以及 $l_1$ 範數為什麼會產生稀疏性。

正則化效果分析

稀疏性

從以上的正則化效果理解其實已經可以看出$L1$正則化可以使得答案稀疏的效果，如果那個還不好理解，可以看下面這個例子。

例子

L1正則化和L2正則化哪個能產生稀疏的解呢？答案是L1正則化。假設我們現在要求解模型 $Ax=b$ ，也就是在2維空間上找到一條直線來擬合樣本點。我們需要兩個點才能去固定一條直線，但是，假設我們現在的訓練樣本中只有一個點。那麼我們將得到無窮多個解。假設，該點為(10, 5)，直線為 $y=a*x+b$ ，那麼，該例子可形式化為求解模型： $b = 5 - 10*a$ 的參數。

那麼，當我們加上正則化項後，又該如何求解呢？

假設，我們的正則化的值等於一個常數，它的圖像如下所示：

我們注意到，在紅色直線上，並不是所有點都是稀疏點，而只有在頂點處的點才是稀疏的，因為頂點處的點某些維度為0。現在，我們要做的是就是擴大這個紅色的形狀，讓它慢慢的靠近上圖中藍色的直線直到兩者有公共點。當我們慢慢增大後，我們發現，最有可能成為公共交點的就是紅色形狀的頂點。而從剛才的分析中，我們知道，紅色形狀的頂點是稀疏點，所以，加上L1正則化後，得到的解往往都是稀疏的，而且這些公共點對應的常數$c$也是比較小的。

而，L2正則化沒有這種稀疏性特點。

特徵選擇

L1正則化具有特徵選擇的功能，這是因為L1正則化通常會產生係數的解，假設我們有100個係數，在L1正則化的作用下只有10個係數非0，那麼這就等價於我們從100個特徵中抽出10個重要的特徵。

計算複雜度

在計算效率上，L2優於L1，因為L1正則化通常是不可導的，這導致我們不能用矩陣方式來求解它，而大多數是依賴於近似的方式。

參考

[1]. L1 Norm Regularization and Sparsity Explained for Dummies

[2]. Regularization (mathematics)

[3]. L1 Norms versus L2 Norms

[4]. Hsuan-Tien Lin. Machine Learning Foundations Lecture 14.

[5]. 深入理解L1、L2正則化