# 14 -- Regularization
上節課我們介紹了過擬合發生的原因:excessive power, stochastic/deterministic noise 和limited data。并介紹了解決overfitting的簡單方法。本節課,我們將介紹解決overfitting的另一種非常重要的方法:Regularization規則化。
### **一、Regularized Hypothesis Set**
先來看一個典型的overfitting的例子:

如圖所示,在數據量不夠大的情況下,如果我們使用一個高階多項式(圖中紅色曲線所示),例如10階,對目標函數(藍色曲線)進行擬合。擬合曲線波動很大,雖然很小,但是很大,也就造成了過擬合現象。
那么如何對過擬合現象進行修正,使hypothesis更接近于target function呢?一種方法就是regularized fit。

這種方法得到的紅色fit曲線,要比overfit的紅色曲線平滑很多,更接近與目標函數,它的階數要更低一些。那么問題就變成了我們要把高階(10階)的hypothesis sets轉換為低階(2階)的hypothesis sets。通過下圖我們發現,不同階數的hypothesis存在如下包含關系:

我們發現10階多項式hypothesis sets里包含了2階多項式hypothesis sets的所有項,那么在中加入一些限定條件,使它近似為即可。這種函數近似曾被稱之為不適定問題(ill-posed problem)。
如何從10階轉換為2階呢?首先,可表示為:
而可表示為:
所以,如果限定條件是,那么就有。也就是說,對于高階的hypothesis,為了防止過擬合,我們可以將其高階部分的權重w限制為0,這樣,就相當于從高階的形式轉換為低階,fit波形更加平滑,不容易發生過擬合。

那有一個問題,令高階權重w為0,為什么不直接使用呢?這樣做的目的是拓展我們的視野,為即將討論的問題做準備。剛剛我們討論的限制是高階部分的權重w限制為0,這是比較苛刻的一種限制。下面,我們把這個限制條件變得更寬松一點,即令任意8個權重w為0,并不非要限定,這個Looser Constraint可以寫成:
也就只是限定了w不為0的個數,并不限定必須是高階的w。這種hypothesis記為,稱為sparse hypothesis set,它與和的關系為:

Looser Constraint對應的hypothesis應該更好解一些,但事實是sparse hypothesis set 被證明也是NP-hard,求解非常困難。所以,還要轉換為另一種易于求解的限定條件。
那么,我們尋找一種更容易求解的寬松的限定條件Softer Constraint,即:
其中,C是常數,也就是說,所有的權重w的平方和的大小不超過C,我們把這種hypothesis sets記為。
與的關系是,它們之間有重疊,有交集的部分,但是沒有完全包含的關系,也不一定相等。對應,C值越大,限定的范圍越大,即越寬松:
當C無限大的時候,即限定條件非常寬松,相當于沒有加上任何限制,就與沒有什么兩樣。稱為regularized hypothesis set,這種形式的限定條件是可以進行求解的,我們把求解的滿足限定條件的權重w記為。接下來就要探討如何求解。
### **二、Weight Decay Regularization**
現在,針對H(c),即加上限定條件,我們的問題變成:

我們的目的是計算的最小值,限定條件是。這個限定條件從幾何角度上的意思是,權重w被限定在半徑為的圓內,而球外的w都不符合要求,即便它是靠近梯度為零的w。

下面用一張圖來解釋在限定條件下,最小化的過程:

如上圖所示,假設在空間中的一點w,根據梯度下降算法,w會朝著的方向移動(圖中藍色箭頭指示的方向),在沒有限定條件的情況下,w最終會取得最小值,即“谷底”的位置。現在,加上限定條件,即w被限定在半徑為的圓內,w距離原點的距離不能超過圓的半徑,球如圖中紅色圓圈所示。那么,這種情況下,w不能到達的位置,最大只能位于圓上,沿著圓的切線方向移動(圖中綠色箭頭指示的方向)。與綠色向量垂直的向量(圖中紅色箭頭指示的方向)是圓切線的法向量,即w的方向,w不能靠近紅色箭頭方向移動。那么隨著迭代優化過程,只要與w點切線方向不垂直,那么根據向量知識,一定在w點切線方向上有不為零的分量,即w點會繼續移動。只有當與綠色切線垂直,即與紅色法向量平行的時候,在切線方向上沒有不為零的分量了,也就表示這時w達到了最優解的位置。
有了這個平行的概念,我們就得到了獲得最優解需要滿足的性質:
上面公式中的稱為Lagrange multiplier,是用來解有條件的最佳化問題常用的數學工具,是方便后面公式推導。那么我們的目標就變成了求解滿足上面公式的。
之前我們推導過,線性回歸的的表達式為:
計算梯度,并代入到平行條件中,得到:
這是一個線性方程式,直接得到為:
上式中包含了求逆矩陣的過程,因為是半正定矩陣,如果大于零,那么一定是正定矩陣,即一定可逆。另外提一下,統計學上把這叫做ridge regression,可以看成是linear regression的進階版。
如果對于更一般的情況,例如邏輯回歸問題中,不是線性的,那么將其代入平行條件中得到的就不是一個線性方程式,不易求解。下面我們從另一個角度來看一下平行等式:
已知是對的導數,而也可以看成是的導數。那么平行等式左邊可以看成一個函數的導數,導數為零,即求該函數的最小值。也就是說,問題轉換為最小化該函數:
該函數中第二項就是限定條件regularizer,也稱為weight-decay regularization。我們把這個函數稱為Augmented Error,即。
如果不為零,對應于加上了限定條件,若等于零,則對應于沒有任何限定條件,問題轉換成之前的最小化。
下面給出一個曲線擬合的例子,取不同的值時,得到的曲線也不相同:

從圖中可以看出,當時,發生了過擬合;當時,擬合的效果很好;當和時,發生了欠擬合。我們可以把看成是一種penality,即對hypothesis復雜度的懲罰,越大,w就越小,對應于C值越小,即這種懲罰越大,擬合曲線就會越平滑,高階項就會削弱,容易發生欠擬合。一般取比較小的值就能達到良好的擬合效果,過大過小都有問題,但究竟取什么值,要根據具體訓練數據和模型進行分析與調試。

事實上,這種regularization不僅可以用在多項式的hypothesis中,還可以應用在logistic regression等其他hypothesis中,都可以達到防止過擬合的效果。
我們目前討論的多項式是形如的形式,若x的范圍限定在[-1,1]之間,那么可能導致相對于低階的值要小得多,則其對于的w非常大,相當于要給高階項設置很大的懲罰。為了避免出現這種數據大小差別很大的情況,可以使用Legendre Polynomials代替這種形式,Legendre Polynomials各項之間是正交的,用它進行多項式擬合的效果更好。關于Legendre Polynomials的概念這里不詳細介紹,有興趣的童鞋可以看一下[維基百科](https://en.wikipedia.org/wiki/Legendre_polynomials)。
### **三、Regularization and VC Theory**
下面我們研究一下Regularization與VC理論之間的關系。Augmented Error表達式如下:
VC Bound表示為:
其中表示的是單個hypothesis的復雜度,記為;而表示整個hypothesis set的復雜度。根據Augmented Error和VC Bound的表達式,包含于之內,所以,比更接近于,即更好地代表,與之間的誤差更小。

根據VC Dimension理論,整個hypothesis set的,這是因為所有的w都考慮了,沒有任何限制條件。而引入限定條件的,即有效的VC dimension。也就是說,比較大,因為它代表了整個hypothesis set,但是比較小,因為由于regularized的影響,限定了w只取一小部分。其中A表示regularized算法。當時,有:
這些與實際情況是相符的,比如對多項式擬合模型,當時,所有的w都給予考慮,相應的很大,容易發生過擬合。當且越來越大時,很多w將被舍棄,減小,擬合曲線越來越平滑,容易發生欠擬合。
### **四、General Regularizers**
那么通用的Regularizers,即,應該選擇什么樣的形式呢?一般地,我們會朝著目標函數的方向進行選取。有三種方式:
* **target-dependent**
* **plausible**
* **friendly**

其實這三種方法跟之前error measure類似,其也有三種方法:
* **user-dependent**
* **plausible**
* **friendly**
regularizer與error measure是機器學習模型設計中的重要步驟。

接下來,介紹兩種Regularizer:L2和L1。L2 Regularizer一般比較通用,其形式如下:
這種形式的regularizer計算的是w的平方和,是凸函數,比較平滑,易于微分,容易進行最優化計算。
L1 Regularizer的表達式如下:
L1計算的不是w的平方和,而是絕對值和,即長度和,也是凸函數。已知圍成的是圓形,而圍成的是正方形,那么在正方形的四個頂點處,是不可微分的(不像圓形,處處可微分)。根據之前介紹的平行等式推導過程,對應這種正方形,它的解大都位于四個頂點處(不太理解,歡迎補充賜教),因為正方形邊界處的w絕對值都不為零,若不與其平行,那么w就會向頂點處移動,頂點處的許多w分量為零,所以,L1 Regularizer的解是稀疏的,稱為sparsity。優點是計算速度快。

下面來看一下如何取值,首先,若stochastic noise不同,那么一般情況下,取值有如下特點:

從圖中可以看出,stochastic noise越大,越大。
另一種情況,不同的deterministic noise,取值有如下特點:

從圖中可以看出,deterministic noise越大,越大。
以上兩種noise的情況下,都是noise越大,相應的也就越大。這也很好理解,如果在開車的情況下,路況也不好,即noise越多,那么就越會踩剎車,這里踩剎車指的就是regularization。但是大多數情況下,noise是不可知的,這種情況下如何選擇?這部分內容,我們下節課將會討論。
### **五、總結**
本節課主要介紹了Regularization。首先,原來的hypothesis set加上一些限制條件,就成了Regularized Hypothesis Set。加上限制條件之后,我們就可以把問題轉化為最小化問題,即把w的平方加進去。這種過程,實際上回降低VC Dimension。最后,介紹regularization是通用的機器學習工具,設計方法通常包括target-dependent,plausible,friendly等等。下節課將介紹如何選取合適的來建立最佳擬合模型。
**_注明:_**
文章中所有的圖片均來自臺灣大學林軒田《機器學習基石》課程
- 臺灣大學林軒田機器學習筆記
- 機器學習基石
- 1 -- The Learning Problem
- 2 -- Learning to Answer Yes/No
- 3 -- Types of Learning
- 4 -- Feasibility of Learning
- 5 -- Training versus Testing
- 6 -- Theory of Generalization
- 7 -- The VC Dimension
- 8 -- Noise and Error
- 9 -- Linear Regression
- 10 -- Logistic Regression
- 11 -- Linear Models for Classification
- 12 -- Nonlinear Transformation
- 13 -- Hazard of Overfitting
- 14 -- Regularization
- 15 -- Validation
- 16 -- Three Learning Principles
- 機器學習技法
- 1 -- Linear Support Vector Machine
- 2 -- Dual Support Vector Machine
- 3 -- Kernel Support Vector Machine
- 4 -- Soft-Margin Support Vector Machine
- 5 -- Kernel Logistic Regression
- 6 -- Support Vector Regression
- 7 -- Blending and Bagging
- 8 -- Adaptive Boosting
- 9 -- Decision Tree
- 10 -- Random Forest
- 11 -- Gradient Boosted Decision Tree
- 12 -- Neural Network
- 13 -- Deep Learning
- 14 -- Radial Basis Function Network
- 15 -- Matrix Factorization
- 16(完結) -- Finale