# 15 -- Validation 上節課我們主要講了為了避免overfitting，可以使用regularization方法來解決。在之前的上加上一個regularizer，生成，將其最小化，這樣可以有效減少模型的復雜度，避免過擬合現象的發生。那么，機器學習領域還有許多選擇，如何保證訓練的模型具有良好的泛化能力？本節課將介紹一些概念和方法來解決這個選擇性的問題。 ### **一、Model Selection Problem** 機器學習模型建立的過程中有許多選擇，例如對于簡單的二元分類問題，首先是算法A的選擇，有PLA，pocket，linear regression，logistic regression等等；其次是迭代次數T的選擇，有100，1000,10000等等；之后是學習速率的選擇，有1，0.01,0.0001等等；接著是模型特征轉換的選擇，有linear，quadratic，poly-10，Legendre-poly-10等等；然后是正則化regularizer的選擇，有L2，L1等等；最后是正則化系數的選擇，有0，0.01，1等等。不同的選擇搭配，有不同的機器學習效果。我們的目標就是找到最合適的選擇搭配，得到一個好的矩g，構建最佳的機器學習模型。  假設有M個模型，對應有，即有M個hypothesis set，演算法為，共M個。我們的目標是從這M個hypothesis set中選擇一個模型，通過演算法對樣本集D的訓練，得到一個最好的矩，使其最小。所以，問題的關鍵就是機器學習中如何選擇到最好的矩。 考慮有這樣一種方法，對M個模型分別計算使最小的矩g，再橫向比較，取其中能使最小的模型的矩：  但是足夠小并不能表示模型好，反而可能表示訓練的矩發生了過擬合，泛化能力很差。而且這種“模型選擇+學習訓練”的過程，它的VC Dimension是，模型復雜度增加。總的來說，泛化能力差，用來選擇模型是不好的。 另外一種方法，如果有這樣一個獨立于訓練樣本的測試集，將M個模型在測試集上進行測試，看一下的大小，則選取最小的模型作為最佳模型：  這種測試集驗證的方法，根據finite-bin Hoffding不等式，可以得到： 由上式可以看出，模型個數M越少，測試集數目越大，那么越小，即越接近于。 下面比較一下之前講的兩種方法，第一種方法使用作為判斷基準，使用的數據集就是訓練集D本身；第二種方法使用作為判斷基準，使用的是獨立于訓練集D之外的測試集。前者不僅使用D來訓練不同的，而且又使用D來選擇最好的，那么對未知數據并不一定泛化能力好。舉個例子，這相當于老師用學生做過的練習題再來對學生進行考試，那么即使學生得到高分，也不能說明他的學習能力強。所以最小化的方法并不科學。而后者使用的是獨立于D的測試集，相當于新的考試題能更好地反映學生的真實水平，所以最小化更加理想。  但是，我們拿到的一都是訓練集D，測試集是拿不到的。所以，尋找一種折中的辦法，我們可以使用已有的訓練集D來創造一個驗證集validation set，即從D中劃出一部分作為驗證集。D另外的部分作為訓練模型使用，獨立開來，用來測試各個模型的好壞，最小化，從而選擇最佳的。  ### **二、Validation** 從訓練集D中抽出一部分K個數據作為驗證集，對應的error記為。這樣做的一個前提是保證獨立同分布（iid）于P(x,y)，也就是說的選擇是從D中平均隨機抽樣得到的，這樣能夠把與聯系起來。D中去除后的數據就是供模型選擇的訓練數據，其大小為N-k。從中選擇最好的矩，記為。  假如D共有1000個樣本，那么可以選擇其中900個，剩下的100個作為。使用訓練模型，得到最佳的，使用對進行驗證，得到如下Hoffding不等式： 假設有M種模型hypothesis set，的數量為K，那么從每種模型m中得到一個在上表現最好的矩，再橫向比較，從M個矩中選擇一個最好的作為我們最終得到的模型。  現在由于數量為N的總樣本D的一部分K作為驗證集，那么只有N-k個樣本可供訓練。從中得到最好的，而總樣本D對應的最好的矩為。根據之前的leraning curve很容易知道，訓練樣本越多，得到的模型越準確，其hypothesis越接近target function，即D的比的要小：  所以，我們通常的做法是通過來選擇最好的矩對應的模型，再對整體樣本集D使用該模型進行訓練，最終得到最好的矩。 總結一下，使用驗證集進行模型選擇的整個過程為：先將D分成兩個部分，一個是訓練樣本，一個是驗證集。若有M個模型，那么分別對每個模型在上進行訓練，得到矩，再用對每個進行驗證，選擇表現最好的矩，則該矩對應的模型被選擇。最后使用該模型對整個D進行訓練，得到最終的。下圖展示了整個模型選擇的過程：  不等式關系滿足： 下面我們舉個例子來解釋這種模型選擇的方法的優越性，假設有兩個模型：一個是5階多項式，一個是10階多項式。通過不使用驗證集和使用驗證集兩種方法對模型選擇結果進行比較，分析結果如下：  圖中，橫坐標表示驗證集數量K，縱坐標表示大小。黑色水平線表示沒有驗證集，完全使用進行判斷基準，那么更好一些，但是這種方法的比較大，而且與K無關。黑色虛線表示測試集非常接近實際數據，這是一種理想的情況，其很小，同樣也與K無關，實際中很難得到這條虛線。紅色曲線表示使用驗證集，但是最終選取的矩是，其趨勢是隨著K的增加，它對應的先減小再增大，當K大于一定值的時候，甚至會超過黑色水平線。藍色曲線表示也使用驗證集，最終選取的矩是，其趨勢是隨著K的增加，它對應的先緩慢減小再緩慢增大，且一直位于紅色曲線和黑色直線之下。從此可見，藍色曲線對應的方法最好，符合我們之前討論的使用驗證集進行模型選擇效果最好。 這里提一點，當K大于一定的值時，紅色曲線會超過黑色直線。這是因為隨著K的增大，增大，但可供模型訓練的在減小，那得到的不具有很好的泛化能力，即對應的會增大，甚至當K增大到一定值時，比模型更差。 那么，如何設置驗證集K值的大小呢？根據之前的分析：  當K值很大時，，但是與相差很大；當K值很小是，，但是與可能相差很大。所以有個折中的辦法，通常設置。值得一提的是，劃分驗證集，通常并不會增加整體時間復雜度，反而會減少，因為減少了。 ### **三、Leave-One-Out Cross Validation** 假如考慮一個極端的例子，k=1，也就是說驗證集大小為1，即每次只用一組數據對進行驗證。這樣做的優點是，但是與可能相差很大。為了避免與相差很大，每次從D中取一組作為驗證集，直到所有樣本都作過驗證集，共計算N次，最后對驗證誤差求平均，得到，這種方法稱之為留一法交叉驗證，表達式為： 這樣求平均的目的是為了讓盡可能地接近。 下面用一個例子圖解留一法的過程：  如上圖所示，要對二維平面上的三個點做擬合，上面三個圖表示的是線性模型，下面三個圖表示的是常數模型。對于兩種模型，分別使用留一交叉驗證法來計算，計算過程都是每次將一個點作為驗證集，其他兩個點作為訓練集，最終將得到的驗證誤差求平均值，就得到了和，比較兩個值的大小，取值小對應的模型即為最佳模型。  接下來，我們從理論上分析Leave-One-Out方法的可行性，即是否能保證的矩足夠好？假設有不同的數據集D，它的期望分布記為，則其可以通過推導，等于的平均值。由于N-1近似為N，的平均值也近似等于的平均值。具體推導過程如下：  最終我們得到的結論是的期望值和的期望值是相近的，這代表得到了比較理想的，Leave-One-Out方法是可行的。 舉一個例子，使用兩個特征：Average Intensity和Symmetry加上這兩個特征的非線性變換（例如高階項）來進行手寫數字識別。平面特征分布如下圖所示：  Error與特征數量的關系如下圖所示：  從圖中我們看出，隨著特征數量的增加，不斷減小，先減小再增大，雖然是不斷減小的，但是它與的差距越來越大，發生了過擬合，泛化能力太差。而與的分布基本一致，能較好地反映的變化。所以，我們只要使用Leave-One-Out方法得到使最小的模型，就能保證其足夠小。下圖是分別使用和進行訓練得到的分類曲線：  很明顯可以看出，使用發生了過擬合，而分類效果更好，泛化能力強。 ### **四、V-Fold Cross Validation** 接下來我們看看Leave-One-Out可能的問題是什么。首先，第一個問題是計算量，假設N=1000，那么就需要計算1000次的，再計算其平均值。當N很大的時候，計算量是巨大的，很耗費時間。第二個問題是穩定性，例如對于二分類問題，取值只有0和1兩種，預測本身存在不穩定的因素，那么對所有的計算平均值可能會帶來很大的數值跳動，穩定性不好。所以，這兩個因素決定了Leave-One-Out方法在實際中并不常用。 針對Leave-One-Out的缺點，我們對其作出了改進。Leave-One-Out是將N個數據分成N分，那么改進措施是將N個數據分成V份（例如V=10），計算過程與Leave-One-Out相似。這樣可以減少總的計算量，又能進行交叉驗證，得到最好的矩，這種方法稱為V-折交叉驗證。其實Leave-One-Out就是V-折交叉驗證的一個極端例子。 所以呢，一般的Validation使用V-折交叉驗證來選擇最佳的模型。值得一提的是Validation的數據來源也是樣本集中的，所以并不能保證交叉驗證的效果好，它的模型一定好。只有樣本數據越多，越廣泛，那么Validation的結果越可信，其選擇的模型泛化能力越強。 ### **五、總結** 本節課主要介紹了Validation驗證。先從如何選擇一個好的模型開始切入，例如使用、都是不太好的，最終使用來進行模型選擇。然后詳細介紹了Validation的過程。最后，介紹了Leave-One-Out和V-Fold Cross兩種驗證方法，比較它們各自的優點和缺點，實際情況下，V-Fold Cross更加常用。 **_注明：_** 文章中所有的圖片均來自臺灣大學林軒田《機器學習基石》課程