# 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更加常用。
**_注明:_**
文章中所有的圖片均來自臺灣大學林軒田《機器學習基石》課程
- 臺灣大學林軒田機器學習筆記
- 機器學習基石
- 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