機器學習讀書筆記系列之正則化與模型選擇

2019 年 11 月 30 日
筆記

機器學習讀書筆記之正則化與模型選擇

整理者：艾奇

原作者：張威，Wei's Homepage

鏈接：https://wei2624.github.io/MachineLearning/

正則化與模型選擇在選擇模型時，如果我們在一個模型中有個參數，那麼問題就是這個參數應該是什麼值？哪些值可以給出最佳偏差-方差權衡呢。其中，我們從有限集合的模型中來選取最佳模型。在集合中，我們有不同的模型，或者不同的參數。

1. 交叉驗證(Cross Validation)

想像一下，給定數據集與一系列的模型，我們很容易想到通過以下方式來選擇模型：

從集合訓練每個模型，並得到相應的假設
選取最小訓練誤差的模型

這個想法不能達到目的因為當我們選擇的多項數階數越高時，模型會更好的擬合訓練數據集。然而，這個模型將會在新的數據集中有很高的統一化誤差，也就是高方差。

在這個情況中，保留交叉驗證(hold-out cross validation)將會做得更好：

以70%和30%的比例將隨機分成訓練數據集和驗證數據集
在在中訓練每一個以學習假設
選擇擁有最小經驗誤差(empirical error)的模型，我們將它標記為 ε

通過以上幾步，我們試圖通過測試模型在驗證集上的表現以估計真實統一化誤差。在第3步中，在選擇最優模型後，我們可以用整個數據集來重複訓練模型來得到最佳假設模型。然而，即使我們可以這樣做，我們仍然選擇的是基於70%數據集來訓練模型。當數據少的時候這是很糟糕的。

因此，我們引出K折交叉驗證(K-fold cross validation)：

隨機將分成個分離的子集，每個子集有m/k個樣本，記為
對於每個模型，我們排除一個子集並標記為，然後我們用其餘的樣本訓練模型以得到。我們在上測試模型，並且得到。我們這樣遍歷每一個。最後，我們獲取統一化誤差除以的平均。
我們選擇有最小平均統一誤差的模型

通常我們取k為10。雖然這樣計算上很複雜，但是它會給我們很好的結果。如果數據很少，我們也可能設。在這種情況下，我們每一次除去一個樣本，這種方法叫除一交叉驗證(leave-one-out cross validation)。

2. 特徵選擇(Feature Selection)

如果我們有n個特徵，m個樣本，其中 (VC 維度is O(n)),我們可能會過度擬合。在這種情況下，你想選擇最重要的特徵來訓練。在暴力演算法中，我們會有用2n 個特徵組合，我們會有2n 個可能的模型，這處理起來會很費力。因此我們可以選擇用向前搜索演算法(forward search algorithm):

我們初始化為F=∅
重複：(a)for i=1,…,n 如果, 讓並且使用交叉驗證演算法來估計。(b)設置F作為(a)中的最佳特徵子集。
從以上選擇最佳特徵子集。

你可以通過設置目標特徵數量來終止循環。相反地，在特徵選擇中我們也可以使用向後搜索演算法(backward search)，這於去除演算法類似。然而，因為這兩種演算法的時間複雜度都是，它們訓練起來都會比較慢。

然而，我們也可以使用過濾特徵選擇(filter feature selection)。它的概念是對於標籤y，我們會根據每一個特徵提供了多少資訊來給它打分，然後挑選出最佳者。一個容易想到的方法是根據每個xi和標籤y的相關性打分。實際中，我們將分數設為相互資訊(mutual information):

其中我們假設每個特徵和標籤都是二元值，並且求和覆蓋整個變數域。每一個可能性都會從訓練數據集中計算。為了進一步理解，我們知道：

其中KL是相對熵(Kullback-Leibler divergence)。它計算了豎線兩邊變數分布的差異。如果和 y 是獨立的，那麼 KL 是0。這代表著特徵和標籤直接沒有任何關係。然而如果MI很高，那麼這個特徵和標籤有強相關性。

3. 貝葉斯統計與正則化(Bayesian Statistics and regularization)

在前面一章我們討論了最大似然法(maximum likelihood (ML) algorithm) 是如何訓練模型參數的：

在這種情況下，我們視θ 為未知參數，它已經存在但是未知。我們的任務是找到未知參數並計算它的值。同時θ也是隨機的，因此我們設置一個先驗值，稱它為先驗分布(prior distribution)。基於先驗分布，我們可以用S數據集來計算後驗分布：

使用後驗分布來預測推斷，我們有：

現在，我們可以計算條件期望值y。然而計算後驗值的完全解是很難的，因為分母中的積分很難得到完全解。因此，我們用另一種方式來計算，我們找到一個後驗值的點估計，在這個點上我們獲得後驗值的最佳 θ。最大後驗MAP(maximum a posteriori) 可以用以下方法計算：

通常來講，先驗分布有0均值，單位方差。這會使MAP 比ML 更不容易過度擬合。