1 引言

人類在對客觀世界的問題進(jìn)行判斷時(shí)，往往都會(huì)根據(jù)過去的經(jīng)驗(yàn)來指導(dǎo)自己。例如，為什么看到微濕的路面、感到和風(fēng)、看到晚霞，就認(rèn)為明天是好天了呢？這是因?yàn)樵谖覀兊纳罱?jīng)驗(yàn)中已經(jīng)見過了很多類似的情況，頭一天觀察到上述的特征后，第二天天氣通常會(huì)很好，為什么色澤青綠、根蒂蜷縮、敲聲濁響，就能判斷出是正熟的好瓜？因?yàn)槲覀兂赃^、看到過很多西瓜，所以基于色澤、根蒂、敲聲這幾個(gè)特征我們就可以做出相當(dāng)好的判斷。可以看出，我們能做出有效的判斷，是因?yàn)槲覀円呀?jīng)累計(jì)了許多經(jīng)驗(yàn)，而通過對經(jīng)驗(yàn)的利用，就能對新的情況作出有效的決策。

那么上面對經(jīng)驗(yàn)的利用是靠我們?nèi)祟愖陨硗瓿傻模?jì)算機(jī)能幫忙嗎？

機(jī)器學(xué)習(xí)正是這門學(xué)科，它致力于研究如何通過計(jì)算的手段，利用經(jīng)驗(yàn)來改善系統(tǒng)自身的性能。在計(jì)算機(jī)系統(tǒng)中，”經(jīng)驗(yàn)“通常以”數(shù)據(jù)“的形式存在，因此，機(jī)器學(xué)習(xí)所研究的主要內(nèi)容，是關(guān)于在計(jì)算機(jī)上從數(shù)據(jù)中產(chǎn)生”模型“（model）的算法，即“學(xué)習(xí)算法”（learning algorithm）。有了學(xué)習(xí)算法，我們把經(jīng)驗(yàn)數(shù)據(jù)提供給它，它就能基于這些數(shù)據(jù)產(chǎn)生模型；在面對新的情況時(shí)（例如看到一個(gè)沒有剖開的西瓜），模型會(huì)給我們提供相應(yīng)的判斷（例如好瓜）。如果說計(jì)算機(jī)科學(xué)是研究關(guān)于“算法”的學(xué)問，那么類似的，可以說機(jī)器學(xué)習(xí)是研究關(guān)于“學(xué)習(xí)算法”的學(xué)問。

2 模型評(píng)估與選擇

2.1 經(jīng)驗(yàn)誤差與過擬合

通常我們把分類錯(cuò)誤的樣本占樣本總數(shù)的比例成為“錯(cuò)誤率” (error rate)，即如果在 個(gè)樣本中有 個(gè)樣本分類錯(cuò)誤，則錯(cuò)誤率 ；相應(yīng)的， 稱為“精度” (accuracy)，即 “精度=1-錯(cuò)誤率”。更一般的，我們把學(xué)習(xí)期的實(shí)際預(yù)測輸出與樣本的真實(shí)輸出之間的差異成為“誤差” (error)，學(xué)習(xí)器在訓(xùn)練集上的誤差稱為“訓(xùn)練誤差” (training error) 或“經(jīng)驗(yàn)誤差” (empirical error)，在新樣本上的誤差稱為“泛化誤差” (generalization error)。顯然，我們希望得到泛化誤差最小的學(xué)習(xí)器。然而，我們事先并不知道新樣本是什么樣，實(shí)際能做的是努力使經(jīng)驗(yàn)誤差最小化。在很多情況下，我們可以學(xué)得一個(gè)經(jīng)驗(yàn)誤差很小、在訓(xùn)練集上表現(xiàn)很好的學(xué)習(xí)器，例如甚至對所有訓(xùn)練樣本都分類正確，即分類錯(cuò)誤率為零，分類精度為100%，但這是不是我們想要的學(xué)習(xí)器呢？遺憾的是，這樣的學(xué)習(xí)器在多數(shù)情況下都不好。

我們實(shí)際希望的，是在新樣本上能表現(xiàn)得很好的學(xué)習(xí)器。為了達(dá)到這個(gè)目的，應(yīng)該從訓(xùn)練樣本中盡可能學(xué)出適用于所有潛在樣本的“普遍規(guī)律”，這樣才能在遇到新樣本時(shí)做出正確的判斷。然而，當(dāng)學(xué)習(xí)器把訓(xùn)練樣本學(xué)得“太好”的時(shí)候，很可能已經(jīng)把訓(xùn)練樣本自身的一些特點(diǎn)當(dāng)做了所有潛在樣本都會(huì)具有的一般性質(zhì)，這樣就會(huì)導(dǎo)致泛化能力下降。這種現(xiàn)象在機(jī)器學(xué)習(xí)中稱為“過擬合” (overfitting)。與“過擬合”相對的是“欠擬合” (underfitting)，這是指對訓(xùn)練樣本的一般性質(zhì)尚未學(xué)好。

有很多因素可能導(dǎo)致過擬合，其中最常見的情況是由于學(xué)習(xí)能力過于強(qiáng)大，以至于把訓(xùn)練樣本所包含的不太一般的特性也都學(xué)習(xí)到了，而欠擬合則通常是由于學(xué)習(xí)能力低下而造成的。欠擬合比較容易克服，例如在決策樹中擴(kuò)展分支、在神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)中增加訓(xùn)練輪數(shù)等，而過擬合則很麻煩。過擬合是機(jī)器學(xué)習(xí)面臨的關(guān)鍵障礙，各類學(xué)習(xí)算法都必然帶有一些針對過擬合的措施；然而必須認(rèn)識(shí)到，過擬合是無法徹底避免的，我們所能做的只是“緩解”，或者說減小其風(fēng)險(xiǎn)。關(guān)于這一點(diǎn)，可大致這樣理解：機(jī)器學(xué)習(xí)面臨的問題通常是 NP 難甚至更難，而有效的學(xué)習(xí)算法必然是在多項(xiàng)式時(shí)間內(nèi)運(yùn)行完成，若克徹底避免過擬合，則通過經(jīng)驗(yàn)誤差最小化就能獲得最優(yōu)解，這就意味著我們構(gòu)造性地證明了 “P = NP”；因此，只要相信?，過擬合就不可避免。

在現(xiàn)實(shí)任務(wù)中，我們往往有很多學(xué)習(xí)算法可供選擇，甚至對同一個(gè)學(xué)習(xí)算法，當(dāng)使用不同的參數(shù)匹配時(shí)，也會(huì)產(chǎn)生不同的模型。那么，我們該選用哪一個(gè)學(xué)習(xí)算法，使用哪一種配置參數(shù)呢？這就是機(jī)器學(xué)習(xí)中的“模型選擇” (model selection)問題。理想的解決方案當(dāng)然是對候選模型的泛化誤差進(jìn)行評(píng)估，然后選擇泛化誤差最小的那個(gè)模型。然而如上面所討論的，我們無法直接獲得泛化誤差，而訓(xùn)練誤差又由于過擬合現(xiàn)象的存在而不適合作為標(biāo)準(zhǔn)，那么，在現(xiàn)實(shí)中如何進(jìn)行模型評(píng)估與選擇呢？

2.2 評(píng)估方法

通常，我們可以通過實(shí)驗(yàn)測試來對學(xué)習(xí)器的泛化誤差進(jìn)行評(píng)估并進(jìn)而做出選擇。為此，需要使用一個(gè)“測試集” (testing set)來測試學(xué)習(xí)器對新樣本的判別能力，然后以測試集上的“測試誤差” (testing error)作為泛化誤差的近似。通常我們假設(shè)測試樣本也是從樣本真實(shí)分布中獨(dú)立同分布采樣而得。但需要注意的是，測試集應(yīng)該盡可能與訓(xùn)練集互斥，即測試樣本盡量不在訓(xùn)練集中出現(xiàn)、未在訓(xùn)練過程中使用過。

測試樣本為什么要盡可能不出現(xiàn)在訓(xùn)練集中呢？為理解這一點(diǎn)，不妨考慮這樣一個(gè)場景：老師出了 10 道題供同學(xué)們練習(xí)，考試時(shí)老師又用同樣的這 10 道題作為試題，這個(gè)考試成績能否有效反應(yīng)出同學(xué)們學(xué)得好不好呢？答案是否定的，可能有的同學(xué)只會(huì)做這 10 道題卻能得高分。回到我們的問題上來，我們希望得到泛化性能很強(qiáng)的模型，好比是希望同學(xué)們對課程學(xué)得很好、獲得了對所學(xué)知識(shí) “舉一反三” 的能力；訓(xùn)練樣本相當(dāng)于給同學(xué)們練習(xí)的習(xí)題，測試過程則是相當(dāng)于考試。顯然，若測試樣本被用作訓(xùn)練了，則得到的將是過于 “樂觀” 的估計(jì)結(jié)果。

可是，我們只有一個(gè)包含個(gè)樣例的數(shù)據(jù)集?， 既要訓(xùn)練，又要測試，怎樣才能做到呢？答案是：通過對??進(jìn)行適當(dāng)?shù)奶幚恚瑥闹挟a(chǎn)生出訓(xùn)練集 S?和測試集 T?。下面介紹幾種常見的做法。

2.2.1 留出法

“留出法”(hold-out) 直接將數(shù)據(jù)集D劃分成兩個(gè)互斥的集合，其中一一個(gè)集合作為訓(xùn)練集S另一個(gè)作為測試集T，即。在S上訓(xùn)練出模型后，用T來評(píng)估其測試誤差，作為對泛化誤差的估計(jì)。

以二分類任務(wù)為例，假定D包含1000個(gè)樣本，將其劃分為S包含700個(gè)樣本, T包含300個(gè)樣本，用S進(jìn)行訓(xùn)練后，如果模型在T上有90個(gè)樣本分類錯(cuò)誤，那么其錯(cuò)誤率為90/300X100%,相應(yīng)的,精度為1-30%=70%。

需注意的是，訓(xùn)練/測試集的劃分要盡可能保持?jǐn)?shù)據(jù)分布的一致性，避免因數(shù)據(jù)劃分過程引入額外的偏差而對最終結(jié)果產(chǎn)生影響，例如在分類任務(wù)中至少要保持樣本的類別比例相似。如果從采樣(sampling)的角度來看待數(shù)據(jù)集的劃分過程，則保留類別比例的采樣方式通常稱為 ”分層采樣”(stratified sampling)。例如通過對D進(jìn)行分層采樣而獲得含70%樣本的訓(xùn)練集S和含30% 樣本的測試集S,若D包含500個(gè)正例、500 個(gè)反例，則分層采樣得到的S應(yīng)包含350個(gè)正例、350 個(gè)反例，而T 則包含150個(gè)正例和150個(gè)反例;若S、T中樣本類別比例差別很大，則誤差估計(jì)將由于訓(xùn)練/測試數(shù)據(jù)分布的差異而產(chǎn)生偏差。

另一個(gè)需要注意的問題是，即便在給定的訓(xùn)練測試集的樣本比例后，仍存在多種劃分方式對初始數(shù)據(jù)集 D 進(jìn)行分割。例如在上面的例子中，可泌巴 D 中的樣本排序，然后把前 350 個(gè)正例放到訓(xùn)練集中，也可以把最后 350 個(gè)正例放到訓(xùn)練集中，…… 這些不同的劃分將導(dǎo)致不同的訓(xùn)練測試集，相應(yīng)的，模型評(píng)估的結(jié)果也會(huì)有差別。因此，單次使用留出法得到的估計(jì)結(jié)果往往不夠穩(wěn)定可靠，在使用留出法時(shí)，一般要采用若干次隨機(jī)劃分、重復(fù)進(jìn)行實(shí)驗(yàn)評(píng)估后取平均值作為留出法的評(píng)估結(jié)果。佰收口進(jìn)行 1 00 次隨相蒯分 r 每次產(chǎn)生一個(gè)訓(xùn)練／測試集用于實(shí)驗(yàn)評(píng)估， 100 次后就得到 1 00 個(gè)結(jié)果，而留出法返回的則是這 1 00 個(gè)結(jié)果的平均。

此外，我們希望評(píng)估的是用 D 訓(xùn)練出的模型的性能，但留出法需劃創(chuàng) 11 練／測試集，這就會(huì)導(dǎo)致一個(gè)窘境（ a wkward situation ) ：若令訓(xùn)練集 S 包含絕大多數(shù)樣本，則訓(xùn)練出的模型可能更接近于用 D 訓(xùn)練出的模型，但由于 T 比較小，評(píng)估結(jié)果可能不夠穩(wěn)定準(zhǔn)確；若令測試集 T 多包含一些樣本，則訓(xùn)練集 S 與 D 差別更大了，被評(píng)估的模型與用 D 訓(xùn)練出的模型相比可能有較大的差別，從而降低了評(píng)估結(jié)果的保真性（ fidelity ）。這個(gè)問題沒有完美的解決方案，常見做法是將大約 2 / 3 ~4 / 5 的樣本用于訓(xùn)練，剩余樣本用于測試。

2.2.2 交叉驗(yàn)證法

“交叉驗(yàn)證法” (cross validation)先將數(shù)據(jù)集D劃分為k個(gè)大小相似的互斥子集，即

。每個(gè)子集D;都盡可能保持?jǐn)?shù)據(jù)分布的一致性，即從D中通過分層采樣得到。然后，每次用k- 1個(gè)子集的并集作為訓(xùn)練集，余下的那一個(gè)子集作為測試集;這樣就可獲得k組訓(xùn)練測試集，從而可進(jìn)行k次訓(xùn)練和測試，最終返回的是這k個(gè)測試結(jié)果的均值。顯然，交叉驗(yàn)證法評(píng)估結(jié)果的穩(wěn)定性和保真性在很大程度上取決于k:的取值，為強(qiáng)調(diào)這一點(diǎn)，通常把交叉驗(yàn)證法稱為“ k折交叉驗(yàn)證”( k - foldcross validation)。? 最常用的取值是10，此時(shí)稱為10折交叉驗(yàn)證;其他常用的k值有5、20等。

與留出法相似，將數(shù)據(jù)集 D劃分為k:個(gè)子集同樣存在多種劃分方式。為減小因樣本劃分不同而引入的差別， k折交叉驗(yàn)證通常要隨機(jī)使用不同的劃分重復(fù)p次，最終的評(píng)估結(jié)果是這p次k折交叉驗(yàn)證結(jié)果的均值,例如常見的有"10 次10折交叉驗(yàn)證”。

假定數(shù)據(jù)集D中包含 m個(gè)樣本，若令k= m，則得到了交叉驗(yàn)證法的一個(gè)特例:留一法(Leave-One-Out,簡稱LOO)。顯然，留一法不受隨機(jī)樣本劃分方式的影響，因?yàn)閭€(gè)樣本只有唯一的方式劃分為個(gè)子集每個(gè)子集包含一個(gè)樣本; 留一法使用的訓(xùn)練集與初始數(shù)據(jù)集相比只少了一個(gè)樣本，這就使得在絕大多數(shù)情況下，留一法中被實(shí)際評(píng)估的模型與期望評(píng)估的用D訓(xùn)練出的核型很相似。因此，留一法的評(píng)估結(jié)果往往被認(rèn)為比較準(zhǔn)確。然而，留一法也有其缺陷:在數(shù)據(jù)集比較大時(shí)，訓(xùn)練m個(gè)模型的計(jì)算開銷可能是難以忍受的(例如數(shù)據(jù)集包含1百萬個(gè)樣本，則需要訓(xùn)練1百萬個(gè)模型)，而這還是在未考慮算法調(diào)參的情況下。另外，留一法的估計(jì)結(jié)果也未必永遠(yuǎn)比其他評(píng)估方法準(zhǔn)確; “沒有免費(fèi)的午餐” 定理對實(shí)驗(yàn)評(píng)估方法同樣適用。

2.2.3 自助法

我們希望評(píng)估的是用D訓(xùn)練出的模型。但在留出法和交叉驗(yàn)證法中，由于保留了一部分樣本用于測試，因此實(shí)際評(píng)估的模型所使用的訓(xùn)練集比D小，這必然會(huì)引入一些因訓(xùn)練樣本規(guī)模不同而導(dǎo)致的估計(jì)偏差。留一法受訓(xùn)練樣本規(guī)模變化的影響較小，但計(jì)算復(fù)雜度又太高了。有沒有什么辦法可以減少訓(xùn)練樣本規(guī)模不同造成的影響，同時(shí)還能比較高效地進(jìn)行實(shí)驗(yàn)估計(jì)呢?

“自助法”(bootstrapping)是一個(gè)比較好的解決方案，它直接以自助采樣法(bootstrapsampling)為基礎(chǔ)。給定包含m個(gè)樣本的數(shù)據(jù)集D ,我們對它進(jìn)行采樣產(chǎn)生數(shù)據(jù)集D' :每次隨機(jī)從D中挑選一個(gè)樣本，將其拷貝放入D'，然后再將該樣本放回初始數(shù)據(jù)集中，是的該樣本在下次采樣時(shí)仍有可能被采到;這個(gè)過程重復(fù)執(zhí)行m次后，我們就得到了包含m個(gè)樣本的數(shù)據(jù)集,這就是自助采樣的結(jié)果。顯然，D中有一部分樣本會(huì)在D'中多次出現(xiàn)，而另一部分樣本不出現(xiàn)。可以做一個(gè)簡單的估計(jì),樣本在m次采樣中始終不被采到的概率是?,取極限得到:

即通過自助采樣，初始數(shù)據(jù)集D中約有36.8% 的樣本未出現(xiàn)在采樣數(shù)據(jù)集D'中。于是我們可將D'用作訓(xùn)練集, D D' 用作測試集;這樣實(shí)際評(píng)估的模型與期望評(píng)估的模型都使用m個(gè)訓(xùn)練樣本，而我們?nèi)杂袛?shù)據(jù)總量約1/3 的、沒在訓(xùn)練集中出現(xiàn)的樣本用于測試。這樣的測試結(jié)果，亦稱“外包估計(jì)”(out-of-bag estimate)。

自助法在數(shù)據(jù)集較小、難以有效劃分訓(xùn)練/測試集時(shí)很有用;此外， 自助法能從初始數(shù)據(jù)集中產(chǎn)生多個(gè)不同的訓(xùn)練集，這對集成學(xué)習(xí)等方法有很大的好處。然而，自助法產(chǎn)生的數(shù)據(jù)集改變了初始數(shù)據(jù)集的分布，這會(huì)引入估計(jì)偏差。因此，在初始數(shù)據(jù)集足夠時(shí)，留出法和交叉驗(yàn)證法更為常用一些。

2.2.4 調(diào)參與最終模型

大多數(shù)學(xué)習(xí)算法都有些參數(shù) (parameter) 需要設(shè)定，參數(shù)配置不同，學(xué)得模型的性能往往有顯著差別。因此，在進(jìn)行模型評(píng)估與選擇時(shí)，除了要對適用學(xué)習(xí)算法進(jìn)行選擇，還需要對算法參數(shù)進(jìn)行設(shè)定，這就是通常所說的 “參數(shù)調(diào)節(jié)” 或簡稱 “調(diào)參” (parameter tuning)。

這里需要注意一點(diǎn):學(xué)習(xí)算法的很多參數(shù)是在實(shí)數(shù)范圍內(nèi)取值，因此，對每種參數(shù)配置都訓(xùn)練出模型來是不可行的。現(xiàn)實(shí)中常用的做法，是對每個(gè)參數(shù)選定一個(gè)范圍和變化步長， 例如在[0, 0.2]范圍內(nèi)以0.05為步長，則實(shí)際要評(píng)估的候選參數(shù)值有5個(gè)，最終是從這5個(gè)候選值中產(chǎn)生選定值。顯然，這樣選定的參數(shù)值往往不是“最佳” 值，但這是在計(jì)算開銷和性能估計(jì)之間進(jìn)行折中的結(jié)果，通過這個(gè)折中，學(xué)習(xí)過程才變得可行。事實(shí)上，即便在進(jìn)行這樣的折中后，調(diào)參往往仍很困難。可以簡單估算一下: 假定算法有3個(gè)參數(shù)，每個(gè)參數(shù)僅考慮5個(gè)候選值，這樣對每一組訓(xùn)練/測試集就有

給定包含m個(gè)樣本的數(shù)據(jù)集D， 在模型評(píng)估與選擇過程中由于需要留出一部分?jǐn)?shù)據(jù)進(jìn)行評(píng)估測試，事實(shí)上我們只使用了-部分?jǐn)?shù)據(jù)訓(xùn)練模型。因此，在模型選擇完成后，學(xué)習(xí)算法和參數(shù)配置已選定，此時(shí)應(yīng)該用數(shù)據(jù)集D重新訓(xùn)練模型。這個(gè)模型在訓(xùn)練過程中使用了所有m個(gè)樣本，這才是我們最終提交給用戶的模型。

另外，需要注意的是，我們通常把學(xué)得模型在實(shí)際使用中遇到的數(shù)據(jù)稱為測試數(shù)據(jù)，為了加以區(qū)分，模型評(píng)估與選擇中用于評(píng)估測試的數(shù)據(jù)集常稱為 “驗(yàn)證集” (validation set)。例如，在研究對比不同算法的泛化性能時(shí)，我們用測試集上的判斷效果來估計(jì)模型在實(shí)際使用時(shí)的泛化能力，而把訓(xùn)練數(shù)據(jù)另外劃分為訓(xùn)練集和驗(yàn)證集，基于驗(yàn)證集上的性能來進(jìn)行模型選擇和調(diào)參。