【原題】A Few Useful Things to Know About Machine Learning

【譯題】機(jī)器學(xué)習(xí)的那些事

【作者】Pedro Domingos

【譯者】劉知遠(yuǎn)

【說(shuō)明】譯文載于《中國(guó)計(jì)算機(jī)學(xué)會(huì)通訊》 第 8 卷 第 11 期 2012 年 11 月 ，本文譯自Communications of the ACM 2012年第10期的“A Few Useful Things to Know About Machine Learning”一文。

機(jī)器學(xué)習(xí)系統(tǒng)自動(dòng)地從數(shù)據(jù)中學(xué)習(xí)程序。與手工編程相比，這非常吸引人。在過(guò)去的20年中，機(jī)器學(xué)習(xí)已經(jīng)迅速地在計(jì)算機(jī)科學(xué)等領(lǐng)域普及。機(jī)器學(xué)習(xí)被用于網(wǎng)絡(luò)搜索、垃圾郵件過(guò)濾、推薦系統(tǒng)、廣告投放、信用評(píng)價(jià)、欺詐檢測(cè)、股票交易和藥物設(shè)計(jì)等應(yīng)用。

麥肯錫全球研究院（the McKinsey Global Institute）最近一份報(bào)告指出，機(jī)器學(xué)習(xí)（又稱數(shù)據(jù)挖掘或者預(yù)測(cè)分析）將驅(qū)動(dòng)下一輪創(chuàng)新【15】。現(xiàn)在已經(jīng)有幾本優(yōu)秀的機(jī)器學(xué)習(xí)教材書可以供感興趣的研究者和實(shí)踐者使用（例如米切爾（Mitchell）和維滕（Witten）等人的教材【16,24】）。但是，成功使用機(jī)器學(xué)習(xí)所應(yīng)掌握的大量“民間知識(shí)”并沒(méi)有出現(xiàn)在這些教材中。因此，很多機(jī)器學(xué)習(xí)項(xiàng)目浪費(fèi)了大量時(shí)間，甚深入了解所需的“民間知識(shí)”可推進(jìn)機(jī)器學(xué)習(xí)的應(yīng)用。至最終也沒(méi)有得到理想的結(jié)果。其實(shí)這些“民間知識(shí)”非常容易理解。本文的目的就是介紹這些知識(shí)。

機(jī)器學(xué)習(xí)有許多不同的類型，但為了展示方便，本文將主要介紹其中最常用的類型：分類。但是，本文所探討的問(wèn)題適用于所有的機(jī)器學(xué)習(xí)類型。一個(gè)分類器（classifier）是一個(gè)系統(tǒng)，系統(tǒng)輸入是一個(gè)包括若干離散或連續(xù)的特征值（feature values）的向量，系統(tǒng)輸出是一個(gè)離散值，代表分類的類別（class）。例如，一個(gè)垃圾郵件過(guò)濾器會(huì)將郵件信息分類到“是垃圾郵件”和“不是垃圾郵件”兩個(gè)類別中。它的輸入可以是一個(gè)布爾向量 x=(x1,…,xj,…,xd) ，其中如果詞典中的第 j 個(gè)詞出現(xiàn)在該郵件中，則 xj=1，否則 xj=0 。一個(gè)學(xué)習(xí)器將一個(gè)訓(xùn)練集（trainingset）樣例 (xi,yi) 作為輸入，其中xi=(xi,1,…,xi,d) 是觀察到的輸入，yi 是相應(yīng)的輸出，學(xué)習(xí)器的輸出是一個(gè)分類器。對(duì)學(xué)習(xí)器的檢驗(yàn)就是判斷它輸出的分類器是否能夠?qū)?lái)的輸入樣例 xt 輸出正確的 yt（例如，垃圾郵件過(guò)濾器是否能夠?qū)⒂?xùn)練時(shí)沒(méi)有見(jiàn)過(guò)的郵件信息正確分類）。

學(xué)習(xí)=表示 + 評(píng)價(jià)+ 優(yōu)化

假設(shè)有一個(gè)應(yīng)用，你認(rèn)為機(jī)器學(xué)習(xí)有可能在其中發(fā)揮作用。那么，你面臨的第一個(gè)問(wèn)題是各種機(jī)器學(xué)習(xí)算法令人眼花繚亂。應(yīng)挑選使用哪一個(gè)？現(xiàn)在有成千上萬(wàn)的機(jī)器學(xué)習(xí)算法，每年還有成百上千的新算法發(fā)表出來(lái)。免迷失在這么多算法中的關(guān)鍵是，要認(rèn)識(shí)到這些算法都是由三個(gè)部分組成的，分別是：

表示（Representation）　

一個(gè)分類器必須用計(jì)算機(jī)可以處理的某種形式語(yǔ)言來(lái)表示。反過(guò)來(lái)講，為學(xué)習(xí)器選擇一種表示，就意味選擇一個(gè)特定的分類器集合。學(xué)習(xí)器可能學(xué)出的分類器只能在這個(gè)集合中。這個(gè)集合被稱為學(xué)習(xí)器的假設(shè)空間（hypothesis space）。如果某個(gè)分類器不在該空間中，它就不可能被該學(xué)習(xí)器學(xué)到。與此相關(guān)的一個(gè)問(wèn)題是如何表示輸入，即使用哪些特征，本文稍后介紹。

評(píng)價(jià)（Evaluation）

我們需要一個(gè)評(píng)價(jià)函數(shù)（亦稱為目標(biāo)函數(shù)或打分函數(shù)）來(lái)判斷分類器的優(yōu)劣。機(jī)器學(xué)習(xí)算法內(nèi)部使用的評(píng)價(jià)函數(shù)和我們希望分類器進(jìn)行優(yōu)化的外部評(píng)價(jià)函數(shù)有所不同。這是為了便于優(yōu)化，接下來(lái)會(huì)討論。

優(yōu)化（Optimization）

最后，我們需要一個(gè)搜索方法，能夠在假設(shè)空間中找到評(píng)價(jià)函數(shù)得分最高的那個(gè)分類器。優(yōu)化技術(shù)的選擇對(duì)學(xué)習(xí)器效率至關(guān)重要；而當(dāng)評(píng)價(jià)函數(shù)有多個(gè)最優(yōu)結(jié)果時(shí)，優(yōu)化技術(shù)也有助于從中選擇。初學(xué)者通常會(huì)采用現(xiàn)成的優(yōu)化方法，之后再用定制專門的優(yōu)化方法來(lái)替代。表 1 展示了三個(gè)組成部分常見(jiàn)的例子。例如，對(duì)一個(gè)測(cè)試樣例， k-近鄰方法會(huì)尋找它的 k 個(gè)最相似的訓(xùn)練樣例，并將這些樣例中出現(xiàn)最多的類別作為該測(cè)試樣例的類別。超平面方法會(huì)為每一個(gè)類別構(gòu)造一個(gè)特征的線性組合，并將得分最高的組合所對(duì)應(yīng)的類別作為預(yù)測(cè)結(jié)果。決策樹方法會(huì)在樹上的每個(gè)內(nèi)部節(jié)點(diǎn)測(cè)試一個(gè)特征，每個(gè)特征值會(huì)對(duì)應(yīng)一個(gè)分支，而不同的葉子節(jié)點(diǎn)會(huì)對(duì)應(yīng)不同的類別。算法 1 展示了一個(gè)極簡(jiǎn)單的二分類決策樹學(xué)習(xí)器，其中使用了信息增益（informationgain）和貪心搜索（greedysearch）【20】。InfoGain(xj,y ) 表示特征 xj 與類別 y 之間的互信息（mutualinformation）。 MakeNode(x,c0,c1 ) 會(huì)返回一個(gè)測(cè)試特征 x 的節(jié)點(diǎn)，該節(jié)點(diǎn)以 c0 作為 x

= 0 時(shí)的孩子節(jié)點(diǎn)，以 c1 作為 x
= 1 時(shí)的孩子節(jié)點(diǎn)。

當(dāng)然，并不是表 1 中從各列選出元素的相互組合都同樣有意義。例如，離散表示很自然地與組合優(yōu)化相結(jié)合；而連續(xù)表示則與連續(xù)優(yōu)化相結(jié)合。然而，很多學(xué)習(xí)器同時(shí)包含離散和連續(xù)的部分。實(shí)際上，所有可能的組合也都快被實(shí)現(xiàn)過(guò)了。

大部分教科書是以表示為視角組織內(nèi)容的。這通常會(huì)讓人忽略掉一個(gè)事實(shí)，即其他部分也同樣重要。雖然對(duì)如何在每個(gè)部分做出選擇并沒(méi)有簡(jiǎn)單的秘訣，但本文將涉及其中幾個(gè)重要的問(wèn)題。正如我們以后會(huì)看到的那樣，機(jī)器學(xué)習(xí)項(xiàng)目中的某些選擇甚至比學(xué)習(xí)器的選擇更加重要。

泛化（Generalization）很重要

機(jī)器學(xué)習(xí)的基本目標(biāo)是對(duì)訓(xùn)練集合中樣例的泛化。這是因?yàn)?#xff0c;不管我們有多少訓(xùn)練數(shù)據(jù)，在測(cè)試階段這些數(shù)據(jù)都不太可能會(huì)重復(fù)出現(xiàn)。（注意，如果在詞典中有?100000個(gè)詞，前述垃圾郵件過(guò)濾器將會(huì)有種?2¹⁰⁰⁰⁰⁰?種可能的不同輸入）。

在訓(xùn)練集上表現(xiàn)出色其實(shí)很簡(jiǎn)單（只要記住這些訓(xùn)練樣例即可）。機(jī)器學(xué)習(xí)初學(xué)者最常犯的錯(cuò)誤是在訓(xùn)練數(shù)據(jù)上做測(cè)試，從而產(chǎn)生勝利的錯(cuò)覺(jué)。如果這時(shí)將選中的分類器在新數(shù)據(jù)上測(cè)試，它往往還不如隨機(jī)猜測(cè)準(zhǔn)確。因此，如果你雇人來(lái)訓(xùn)練分類器，一定要自己保存一些數(shù)據(jù)，來(lái)測(cè)試他們給你的分類器的性能。相反，如果你被人雇來(lái)訓(xùn)練分類器，一開始就應(yīng)該將一部分?jǐn)?shù)據(jù)取出來(lái)，只用它們來(lái)測(cè)試你選擇的分類器性能，接下來(lái)再在整個(gè)數(shù)據(jù)上學(xué)習(xí)你最終的分類器。

你的分類器可能會(huì)在不知不覺(jué)中受到測(cè)試數(shù)據(jù)的影響，例如你可能會(huì)使用測(cè)試數(shù)據(jù)來(lái)調(diào)節(jié)參數(shù)并做了很多調(diào)節(jié)（機(jī)器學(xué)習(xí)算法有很多參數(shù)，算法成功往往源自對(duì)這些參數(shù)的精細(xì)調(diào)節(jié)，因此這是非常值得關(guān)注的問(wèn)題）。當(dāng)然，保留一部分?jǐn)?shù)據(jù)用于測(cè)試會(huì)減少訓(xùn)練數(shù)據(jù)的數(shù)量。這個(gè)問(wèn)題可以通過(guò)交叉驗(yàn)證（cross – validation）來(lái)解決：將訓(xùn)練數(shù)據(jù)隨機(jī)地等分為若干份（如 10份），其中的每一份均可用作測(cè)試，而剩下的數(shù)據(jù)用作訓(xùn)練，然后將每個(gè)學(xué)習(xí)的分類器在它沒(méi)見(jiàn)過(guò)的樣例上進(jìn)行測(cè)試，將測(cè)試結(jié)果取平均后，就可用來(lái)評(píng)價(jià)不同參數(shù)設(shè)置的性能。

僅有數(shù)據(jù)還不夠

將泛化作為目標(biāo)帶來(lái)的另外一個(gè)重要結(jié)果是，僅有數(shù)據(jù)還不夠，無(wú)論你有多少。考慮要從100萬(wàn)樣例中學(xué)習(xí)一個(gè)包含 100個(gè)變量的布爾函數(shù)。此時(shí)將有2^100??– 10^6?個(gè)樣例的類別是不知道的（注：這里2^100?表示?100個(gè)布爾變量的所有可能情況的個(gè)數(shù)，而10⁶表示已經(jīng)看到的100萬(wàn)樣例，因此有?2¹⁰⁰?-10⁶?個(gè)可能情況是沒(méi)有看到過(guò)的，因此也不知道它們的類別）。你如何確定那些樣例的類別呢？在沒(méi)有更進(jìn)一步信息的情況下，除了拋硬幣隨機(jī)猜之外將束手無(wú)策。哲學(xué)家大衛(wèi) ·休謨（David Hume）在?200多年前首次指出這一問(wèn)題（以某種不同的形式），但直到今天機(jī)器學(xué)習(xí)中的很多錯(cuò)誤仍是由于沒(méi)有意識(shí)到這一問(wèn)題造成的。每個(gè)學(xué)習(xí)器都必須包含一些數(shù)據(jù)之外的知識(shí)或假設(shè)（assumption），才能夠?qū)?shù)據(jù)泛化。這一概念被沃爾伯特（Wolpert）形式化為“沒(méi)有免費(fèi)的午餐”定理。根據(jù)該定理，沒(méi)有學(xué)習(xí)器能夠比在所有可能的布爾函數(shù)中隨機(jī)猜測(cè)的結(jié)果更優(yōu)【25】。

這似乎是一個(gè)非常讓人失望的消息。那我們還能指望能學(xué)到什么東西嗎？幸運(yùn)的是，在真實(shí)世界中，我們要學(xué)習(xí)的函數(shù)并非均勻地來(lái)自所有可能的函數(shù)！實(shí)際上，一些非常泛泛的假設(shè)——比如平滑（smoothness），相似的樣例有相似的類別，有限依賴，或者有限復(fù)雜度——通常足夠起很大作用，這也是機(jī)器學(xué)習(xí)能夠如此成功的重要原因。如同演繹（deduction）一樣，歸納（induction，正是學(xué)習(xí)器所做的） 起到知識(shí)杠桿的作用 —— 它將少量的輸入知識(shí)轉(zhuǎn)化成為大量的輸出知識(shí)。歸納是比演繹強(qiáng)大得多的杠桿，只要求很少的輸入知識(shí)就可以產(chǎn)生有用的結(jié)果，但是它終歸不能在沒(méi)有知識(shí)的情況下工作。而且就像任何杠桿一樣，輸入越多，我們得到的輸出就越多。

從中可以得到的一個(gè)推論是，選擇表示的關(guān)鍵標(biāo)準(zhǔn)之一是，它比較易于表達(dá)什么類型的知識(shí)。例如，如果我們擁有大量關(guān)于在我們的領(lǐng)域是什么造成樣例相似的知識(shí)，基于實(shí)例的方法也許就是合適的選擇。如果我們擁有概率依賴的知識(shí)，圖模型則比較適合。如果我們擁有每個(gè)類別要求的先決條件的知識(shí)，“ If…Then…（如果…那么…）”規(guī)則的表示也許是最好的選擇。在這一點(diǎn)上，最有用的學(xué)習(xí)器是那些并非將假設(shè)固化在其中，而是允許我們用顯式規(guī)定假設(shè)，在大范圍改變假設(shè)，并自動(dòng)將其體現(xiàn)在學(xué)習(xí)中（例如采用一階邏輯 【21】或者語(yǔ)法 【6】）的學(xué)習(xí)器。

說(shuō)到這里，學(xué)習(xí)需要知識(shí)，這并不讓人驚訝。機(jī)器學(xué)習(xí)不是魔術(shù)，它無(wú)法憑空變出東西。它所做的是由少變多。編程就像所有的工程技術(shù)那樣，意味著大量的工作，必須從頭開始建造一切。而機(jī)器學(xué)習(xí)更像是種田，它讓大自然做大部分工作。農(nóng)夫?qū)⒎N子與肥料混合種出莊稼。學(xué)習(xí)器將知識(shí)和數(shù)據(jù)結(jié)合“種出”程序。

過(guò)擬合（Overfitting）有多張面孔

如果我們擁有的知識(shí)和數(shù)據(jù)并不足以學(xué)習(xí)出正確的分類器，將會(huì)怎樣呢？我們就得冒風(fēng)險(xiǎn)構(gòu)建一個(gè)分類器（或者其中一部分），這個(gè)分類器并非建立在現(xiàn)實(shí)基礎(chǔ)上，而是將數(shù)據(jù)隨機(jī)表現(xiàn)加以解讀。這個(gè)問(wèn)題稱為過(guò)擬合，它是機(jī)器學(xué)習(xí)中的棘手問(wèn)題。當(dāng)你的學(xué)習(xí)器輸出的分類器在訓(xùn)練數(shù)據(jù)上準(zhǔn)確率為 100%，而在測(cè)試數(shù)據(jù)上僅有 50% 的時(shí)候（而本來(lái)可以學(xué)到一個(gè)分類器能夠在兩個(gè)數(shù)據(jù)上均達(dá)到 75% 的準(zhǔn)確率），說(shuō)明這個(gè)分類器發(fā)生過(guò)擬合了。

機(jī)器學(xué)習(xí)領(lǐng)域的每個(gè)人都了解過(guò)擬合，但過(guò)擬合會(huì)以多種并不明顯的形式出現(xiàn)。一種理解過(guò)擬合的方式是將泛化誤差（generalization error）分解為偏置（bias）和方差（ variance）【9】。偏置度量了學(xué)習(xí)器傾向于一直學(xué)習(xí)相同錯(cuò)誤的程度。方差則度量了學(xué)習(xí)器傾向于忽略真實(shí)信號(hào)、學(xué)習(xí)隨機(jī)事物的程度。圖 1用朝板子扔飛鏢作為類比進(jìn)行了直觀說(shuō)明。

一個(gè)線性學(xué)習(xí)器有較高的偏置，因?yàn)楫?dāng)兩個(gè)類別的交界不是超平面的時(shí)候，這個(gè)學(xué)習(xí)器就無(wú)法進(jìn)行歸納（摘注：原文 A linear learner has high bias, because when the frontier between two classes is not a hyper-plane the learner is unable
to induce it）。決策樹就不會(huì)有這個(gè)問(wèn)題，因?yàn)樗梢员硎救我獾牟紶柡瘮?shù)，但在另一方面，決策樹會(huì)面臨高方差的問(wèn)題：在同一現(xiàn)象所產(chǎn)生的不同訓(xùn)練數(shù)據(jù)上學(xué)習(xí)的決策樹往往差異巨大，而實(shí)際上它們應(yīng)當(dāng)是相同的。類似道理也適用于優(yōu)化方法的選擇上：與貪心搜索相比，柱搜索的偏置較低，但方差較高，原因是柱搜索會(huì)嘗試搜索更多的假設(shè)。因此，與直覺(jué)相反，一個(gè)學(xué)習(xí)能力更強(qiáng)的學(xué)習(xí)器并不見(jiàn)得比學(xué)習(xí)能力弱的效果更好。

圖 2 示例說(shuō)明了這一點(diǎn)（注：訓(xùn)練樣例含有 64 個(gè)布爾類型特征和 1 個(gè)根據(jù)一個(gè)集合的“如果…那么…”的規(guī)則集合計(jì)算得到的布爾類型的類別。圖中的曲線是對(duì) 100 次運(yùn)行結(jié)果的平均，每次對(duì)應(yīng)不同的隨機(jī)產(chǎn)生的規(guī)則集合。誤差條（error bar）代表兩個(gè)標(biāo)準(zhǔn)方差。具體細(xì)節(jié)請(qǐng)參考論文【10】）。即使真正的分類器是一個(gè)規(guī)則集合，但根據(jù) 1000個(gè)樣例學(xué)習(xí)的樸素貝葉斯學(xué)習(xí)器（摘注：原文 Naive?Bayes）仍比一個(gè)規(guī)則學(xué)習(xí)器的準(zhǔn)確率更高。甚至當(dāng)樸素貝葉斯錯(cuò)誤地假設(shè)分類面是線性的，也依然如此。這種情形在機(jī)器學(xué)習(xí)領(lǐng)域很常見(jiàn)：一個(gè)強(qiáng)錯(cuò)誤假設(shè)比那些弱正確假設(shè)更好，這是因?yàn)楹笳咝枰嗟臄?shù)據(jù)才能避免過(guò)擬合。

交叉驗(yàn)證可以幫助避免過(guò)擬合，例如通過(guò)交叉驗(yàn)證來(lái)選擇決策樹的最佳大小。但這不能徹底解決問(wèn)題，因?yàn)榧偃缥覀兝媒徊骝?yàn)證做太多的參數(shù)選擇，它本身就會(huì)開始過(guò)擬合【17】。

除了交叉驗(yàn)證以外，還有很多方法可以避免過(guò)擬合。最常用的方法是對(duì)評(píng)價(jià)函數(shù)增加一個(gè)正則項(xiàng)（regularization term）。這樣做可以懲罰那些包含更多結(jié)構(gòu)的分類器，偏好更小的分類器，從而降低過(guò)擬合的可能性。另一個(gè)方案是在決定是否增加新的結(jié)構(gòu)時(shí)進(jìn)行諸如卡方測(cè)試（chi-squre）等統(tǒng)計(jì)顯著性檢驗(yàn)（statistical?significance test），用來(lái)決定類別分布是否會(huì)因?yàn)樵黾舆@個(gè)結(jié)構(gòu)而不同。當(dāng)數(shù)據(jù)非常缺乏時(shí)，這些技術(shù)非常有用。然而，你應(yīng)該對(duì)那些宣稱某項(xiàng)技術(shù)“解決”了過(guò)擬合問(wèn)題的說(shuō)法持懷疑態(tài)度。我們會(huì)很容易在避免過(guò)擬合（或者說(shuō)“方差”）時(shí)，造成另外一個(gè)相反的錯(cuò)誤—— 欠擬合（ underfitting，或者說(shuō)“偏置”）。要學(xué)習(xí)一個(gè)完美的分類器來(lái)同時(shí)避免過(guò)擬合和欠擬合，事先又沒(méi)有足夠知識(shí)，這種情形下沒(méi)有任何單一技術(shù)能夠總是表現(xiàn)最好（沒(méi)有免費(fèi)的午餐）。

對(duì)過(guò)擬合的一個(gè)常見(jiàn)誤解是認(rèn)為它是由噪音造成的，例如有些訓(xùn)練樣例的標(biāo)注類別是錯(cuò)誤的。這的確會(huì)加劇過(guò)擬合，因?yàn)榉诸惼鲿?huì)調(diào)整分類面讓那些樣例保持在分類器認(rèn)為正確的一側(cè)。但是即使沒(méi)有噪音依然會(huì)發(fā)生嚴(yán)重的過(guò)擬合。例如，假如我們學(xué)習(xí)一個(gè)布爾類型分類器，它是訓(xùn)練數(shù)據(jù)中所有標(biāo)為“true”的樣例的析取（disjunction）。（換句話說(shuō)，這個(gè)分類器是一個(gè)析取范式（disjunctive normal form）的布爾類型公式，其中每一項(xiàng)是某個(gè)特定訓(xùn)練樣例的所有特征值的合取（conjunction）。）這個(gè)分類器對(duì)所有的訓(xùn)練樣例都分類正確，但對(duì)測(cè)試樣例中的每個(gè)正例都分類錯(cuò)誤，不管訓(xùn)練數(shù)據(jù)是否有噪音。

多重檢驗(yàn)（multiple testing）【13】問(wèn)題與過(guò)擬合密切相關(guān)。標(biāo)準(zhǔn)的統(tǒng)計(jì)檢驗(yàn)中只有一個(gè)假設(shè)被檢驗(yàn)，而現(xiàn)代學(xué)習(xí)器在結(jié)束學(xué)習(xí)前會(huì)輕易地檢驗(yàn)上百萬(wàn)個(gè)假設(shè)。因此，那些看上去很顯著的結(jié)論實(shí)際并不如此。例如，一個(gè)連續(xù)十年跑贏市場(chǎng)的共同基金（mutual fund）看上去很引人注目。但當(dāng)你發(fā)現(xiàn)，如果有1000家基金，每家都有50%的概率在某年跑贏市場(chǎng)，在這種情況下，極有可能會(huì)有一家基金能夠憑僥幸而連續(xù)10次都跑贏市場(chǎng)。這個(gè)問(wèn)題可以通過(guò)在顯著性檢驗(yàn)中將假設(shè)的個(gè)數(shù)考慮進(jìn)去來(lái)解決，但這樣也會(huì)導(dǎo)致欠擬合。更好的途徑是控制錯(cuò)誤接受的非零假設(shè)（non-null hypotheses）的比率，該方法通常被稱為錯(cuò)誤發(fā)現(xiàn)率（false dis-covery rate）方法【3】。

直覺(jué)不適用于高維空間

機(jī)器學(xué)習(xí)中緊接過(guò)擬合之后的最大問(wèn)題就是維度災(zāi)難（curse of dimensionality）。這一概念是由貝爾曼（Bellman）在1961年首先提出的，用來(lái)描述以下事實(shí)：許多在低維空間表現(xiàn)很好的算法，當(dāng)輸入是高維度的時(shí)候，就變得計(jì)算不可行（intractable）了。但在機(jī)器學(xué)習(xí)領(lǐng)域，這有更多的意義。隨著樣例維度（即特征數(shù)目）的增長(zhǎng)，正確泛化的難度會(huì)以指數(shù)級(jí)增加，原因是同等規(guī)模的訓(xùn)練集只能覆蓋越來(lái)越少的輸入空間比例。即使對(duì)于中等大小的 100維布爾空間，一個(gè)包含 1 萬(wàn)億樣例的大型數(shù)據(jù)集合也只能覆蓋輸入空間的 10-18 左右(譯注：這里作者指的是輸入為布爾量時(shí)的情形)。這體現(xiàn)了機(jī)器學(xué)習(xí)存在的必要性，也是它的難點(diǎn)所在。

更嚴(yán)格地講，機(jī)器學(xué)習(xí)算法所（顯式或隱式）依賴的基于相似度的推理在高維空間不再有效。現(xiàn)在考慮一個(gè)采用漢明距離（hamming distance）作為相似度度量的最近鄰分類器，并設(shè)定樣例的分類類別是 x1∧x2 。如果沒(méi)有其他特征，這是一個(gè)很容易的問(wèn)題。但是當(dāng)增加 98 個(gè)不相關(guān)的特征 x3,…,x100 的時(shí)候，來(lái)自這些特征的噪音會(huì)淹沒(méi)來(lái)自 x1 和 x2 的信號(hào)，導(dǎo)致所找到的最近鄰相當(dāng)于做出隨機(jī)預(yù)測(cè)。

更多的困擾是，即使所有的100個(gè)特征都是相關(guān)的，最近鄰方法依然會(huì)有問(wèn)題。這是因?yàn)樵诟呔S空間所有的樣例都變得很相似。例如，假設(shè)所有樣例分布在規(guī)則的網(wǎng)格上，現(xiàn)在考慮一個(gè)測(cè)試樣例 xt。如果網(wǎng)格是 d-維的，會(huì)有個(gè) 2d 個(gè) xt 最近鄰樣例與 xt 的距離相等。因此，隨著維數(shù)的增加，越來(lái)越多的樣例會(huì)變成 xt 的最近鄰，以致最后最近鄰的選擇實(shí)際上變成隨機(jī)的（類別選擇也因此變成隨機(jī)的）。

這只是高維空間上更廣泛?jiǎn)栴}的一個(gè)實(shí)例。我們的來(lái)自三維世界的直覺(jué)在高維空間通常并不奏效(摘注：原文our intuitions, which come from a three dimensional world, often do not apply in high-dimensional ones.)。在高維空間，多元高斯分布（multivariate?Gaussian distribution）的大部分質(zhì)量（mass）并不分布在均值附近，而是在逐漸遠(yuǎn)離均值的一層“殼”上；打個(gè)比方，一個(gè)高維的橘子的大部分質(zhì)量不在瓤上，而是在皮上。如果數(shù)量一定的樣例均勻分布在一個(gè)（維數(shù)不斷增加的）高維的超立方體中，那么超出某個(gè)維數(shù)后，大部分樣例與超立方體的某一面的距離要小于與它們最近鄰的距離。如果我們?cè)诔⒎襟w中內(nèi)接一個(gè)超球面，那么超立方體的幾乎所有質(zhì)量都會(huì)分布在超球面之外。這對(duì)機(jī)器學(xué)習(xí)是一個(gè)壞消息，因?yàn)闄C(jī)器學(xué)習(xí)常常用一種類型的形狀來(lái)近似另一種類型的形狀。

在二維或三維空間構(gòu)建分類器很簡(jiǎn)單，我們可以僅通過(guò)肉眼觀察發(fā)現(xiàn)不同類別樣例的分界線（甚至可以說(shuō)，假如人們有在高維空間中觀察的能力，機(jī)器學(xué)習(xí)就沒(méi)有存在的必要了）。但是在高維空間中很難理解正在發(fā)生什么。因此也就很難設(shè)計(jì)一個(gè)好的分類器。人們也許會(huì)天真地認(rèn)為收集更多的特征永遠(yuǎn)不會(huì)有什么壞處，因?yàn)樽顗牡那闆r也不過(guò)是沒(méi)有提供關(guān)于類別的新信息而已。但實(shí)際上這樣做的好處可能要遠(yuǎn)小于維度災(zāi)難帶來(lái)的問(wèn)題。

幸運(yùn)的是，有一個(gè)效應(yīng)可以在一定程度上抵消維度災(zāi)難，那就是所謂的“非均勻性的祝福”（blessing of nonuniformity）。在大多數(shù)應(yīng)用中，樣例在空間中并非均勻分布，而是集中在一個(gè)低維流形（manifold）上面或附近。例如在手寫體數(shù)字識(shí)別任務(wù)中，即使數(shù)字圖片的每個(gè)像素都單獨(dú)作為一個(gè)特征，近鄰方法在該任務(wù)上表現(xiàn)依然良好，這是因?yàn)閿?shù)字圖片的空間要遠(yuǎn)小于整個(gè)可能的空間。學(xué)習(xí)器可以隱式地充分利用這個(gè)有效的更低維空間，也可以顯式地進(jìn)行降維（例如特南鮑姆（Tenenbaum）的工作【22】）。

理論保證（Theoretical Guarantees）與看上去的不一樣

機(jī)器學(xué)習(xí)論文充滿了理論保證。最常見(jiàn)的類型是能保證泛化所需樣例數(shù)目的邊界（bound）。你應(yīng)當(dāng)如何理解這些保證呢？首先，需要注意的是它們是否可行。歸納與演繹相反：在演繹中你可以保證結(jié)論是對(duì)的；在歸納中就難說(shuō)了。這是很多世紀(jì)以來(lái)的普遍共識(shí)。最近幾十年的一個(gè)重要進(jìn)展是我們認(rèn)識(shí)到可以有歸納結(jié)果正確性的保證，特別是如果我們?cè)敢饨邮芨怕时ＷC（摘注：原文One
of the major developments of recent decades has been the realization that in fact we can have guarantees on the results of induction, particularly if we’re willing to settle for probabilistic guarantees.）。

基本論證非常簡(jiǎn)單【5】。如果一個(gè)分類器的真實(shí)錯(cuò)誤率（true error rate）大于 ? ，我們稱該分類器是壞的。那么一個(gè)壞分類器在 n 個(gè)隨機(jī)獨(dú)立訓(xùn)練樣例上都保持正確的概率小于(1??)n 。設(shè) b 是學(xué)習(xí)器的假設(shè)空間 H 中壞分類器的個(gè)數(shù)，其中至少有一個(gè)分類器能保持正確的概率小于 b(1??)n ，即所謂“一致限（union bound）”。假設(shè)學(xué)習(xí)器返回的都是保持正確的分類器，那么這個(gè)分類器是壞的概率小于 |H|(1??)n ，這里我們利用了 b≤|H| 這個(gè)事實(shí)。所以，如果我們希望這個(gè)概率小于 δ的充分條件是使 n>1/?(ln|H|+ln1/δ)≥ln(δ/|H|)/ln(1??) (摘注：原文該公式為 n>ln(δ/|H|)/ln(1??)≥1?(ln|H|+ln1δ) ，修改原文公式的譯注為—— 原文公式有誤，根據(jù)參考文獻(xiàn)【5】應(yīng)為該公式 )。

不幸的是，對(duì)這類保證得十分小心。這是因?yàn)橥ㄟ^(guò)這種方式獲得的邊界往往非常松散（loose）。這種邊界的突出優(yōu)點(diǎn)是所要求的樣例數(shù)目只隨 |H| 和 1/delta呈對(duì)數(shù)增長(zhǎng)。但遺憾的是，大多數(shù)假設(shè)空間是隨著特征數(shù)目呈雙指數(shù)級(jí)增長(zhǎng)的，這就要求我們提供的樣例數(shù)目 d 也隨著呈指數(shù)增長(zhǎng)。例如，考慮包含 d 個(gè)布爾變量的布爾類型函數(shù)空間。如果有 e 個(gè)可能不同的樣例，就會(huì)有 2e 個(gè)可能不同的函數(shù)。因此，由于有 2d 個(gè)可能的樣例，函數(shù)總數(shù)達(dá)到個(gè) 22d 。即使對(duì)“僅僅”為指數(shù)級(jí)的假設(shè)空間，這個(gè)邊界仍然很松，因?yàn)橐恢孪薹浅１Ｊ亍＠?#xff0c;如果有 100 個(gè)布爾特征，假設(shè)空間是層數(shù)最多為 10 的決策樹，為了保證 δ=?=1 ，我們需要 50 萬(wàn)個(gè)樣例。但實(shí)際上，只需要其中的一小部分?jǐn)?shù)據(jù)就足以精確學(xué)習(xí)了。

而且，我們必須留意邊界所包含的意義。例如，邊界并不意味著，假如你的學(xué)習(xí)器返回了一個(gè)在某個(gè)特定訓(xùn)練集上保持正確的假設(shè)，這個(gè)假設(shè)就可能實(shí)現(xiàn)了泛化。邊界的意思是，給定一個(gè)足夠大的訓(xùn)練集，告訴你在很大的概率上你的學(xué)習(xí)器會(huì)返回一個(gè)成功泛化的假設(shè)，還是無(wú)法找到一個(gè)保持正確的假設(shè)。這個(gè)邊界也無(wú)法告訴我們?nèi)绾芜x擇好的假設(shè)空間。它只能告訴我們，如果這個(gè)假設(shè)空間包含真實(shí)分類器，那么學(xué)習(xí)器輸出一個(gè)壞分類器的概率隨著訓(xùn)練數(shù)據(jù)規(guī)模的增長(zhǎng)而降低(摘注：原文 It only tells us that, if the hypothesis?space contains the true classifier, then the probability that the learner outputs a bad classifier decreases with training set size.)。如果我們縮小假設(shè)空間，邊界就會(huì)得到改善，但是空間包含真實(shí)分類器的幾率也降低了（在真實(shí)分類器不在假設(shè)空間中的情況下也會(huì)有邊界，以上討論同樣適用）。

另一類常用理論保證是漸進(jìn)（asymptotic）：給定無(wú)窮數(shù)據(jù)，學(xué)習(xí)器將保證輸出正確的分類器。這個(gè)保證讓人欣慰，但如果只是因?yàn)橛袧u進(jìn)保證而選擇一個(gè)分類器則是非常草率的。在實(shí)踐中，我們很少處于漸進(jìn)狀態(tài)（或稱為漸進(jìn)態(tài)（asymptopia））。而且，由于我們前面探討過(guò)的偏置-方差的權(quán)衡（trade-off），如果對(duì)無(wú)窮數(shù)據(jù)，學(xué)習(xí)器 A 比學(xué)習(xí)器B好，那么在有限數(shù)據(jù)的情況下 B 通常比 A 好。

機(jī)器學(xué)習(xí)中理論保證的主要作用并不是在實(shí)踐中作為決策的標(biāo)準(zhǔn)，而是在算法設(shè)計(jì)中作為理解和驅(qū)動(dòng)的來(lái)源。在這方面，它們作用巨大；實(shí)際上，理論與實(shí)踐的緊密結(jié)合是機(jī)器學(xué)習(xí)在過(guò)去幾年中取得重大進(jìn)展的重要原因。但是使用者需要謹(jǐn)慎：學(xué)習(xí)是一個(gè)復(fù)雜現(xiàn)象，因?yàn)橐粋€(gè)學(xué)習(xí)器既有理論證明又有實(shí)際應(yīng)用，而前者并未成為后者的依據(jù)（摘注：本段原文 The main role of theoretical guarantees in machine learning is not as a criterion for practical decisions,but as a source of understanding and driving force for algorithm design. In this capacity, they are quite useful; indeed, the close interplay of theory and practice is one of the main reasons machine learning has made so much progress over the years. But caveatemptor: learning is a complex phenomenon, and just because a learner has a theoretical justification and works in practice doesn’t mean the former is the reason for the latter. ）。

特征工程（Feature Engineering）是關(guān)鍵

在考慮所有情況之后，有的機(jī)器學(xué)習(xí)項(xiàng)目成功了而有的則失敗了。這是什么原因造成的呢？無(wú)疑最重要的因素是所利用的特征。如果你有很多與類別非常相關(guān)的獨(dú)立特征，學(xué)習(xí)起來(lái)很容易。但另一方面，如果特征與類別的關(guān)系非常復(fù)雜，你就不一定能夠?qū)W到它了。通常原始數(shù)據(jù)不能直接拿來(lái)學(xué)習(xí)，你需要從中構(gòu)建特征。這是機(jī)器學(xué)習(xí)項(xiàng)目的主要工作。這通常也是最有趣的部分，在這里直覺(jué)、創(chuàng)造性和魔法與技術(shù)一樣都很重要。

初學(xué)者往往驚訝于機(jī)器學(xué)習(xí)項(xiàng)目中真正用于機(jī)器學(xué)習(xí)的時(shí)間是如此之少。但假如你考慮到對(duì)數(shù)據(jù)的收集、整合、清理和預(yù)處理是多么費(fèi)時(shí)，以及特征設(shè)計(jì)需要經(jīng)歷多少試驗(yàn)和錯(cuò)誤，就會(huì)理解這個(gè)過(guò)程了。還有，機(jī)器學(xué)習(xí)無(wú)法做到一次性就能完成構(gòu)建數(shù)據(jù)集合和運(yùn)行學(xué)習(xí)器，它是一個(gè)反復(fù)迭代的過(guò)程，包括運(yùn)行學(xué)習(xí)器，分析結(jié)果，修改數(shù)據(jù)和/或?qū)W習(xí)器等，不斷重復(fù)。學(xué)習(xí)往往是這其中最快完成的部分，原因在于我們已經(jīng)非常精通它了！特征工程更加困難，原因是它是領(lǐng)域相關(guān)（domain-specific）的，而學(xué)習(xí)器則很大程度是通用的。不過(guò)，兩者并沒(méi)有明確界限，這也是最有用的學(xué)習(xí)器往往是那些有助于融入領(lǐng)域知識(shí)的學(xué)習(xí)器的原因之一。

當(dāng)然，機(jī)器學(xué)習(xí)的一個(gè)終極目標(biāo)就是將特征工程過(guò)程越來(lái)越多地自動(dòng)化(摘注：原文one of the holy grails of machine learning is to automate more and more of the feature engineering process )。現(xiàn)在經(jīng)常采用的一種方式是先自動(dòng)產(chǎn)生大量的候選特征，然后根據(jù)它們與分類類別的信息增益等方法來(lái)選取最好的特征。但需要牢記在心的是，特征獨(dú)立地看也許與分類無(wú)關(guān)，但組合起來(lái)也許就相關(guān)了。例如，如果分類類別是取 k 個(gè)輸入特征的“XOR（異或）”，那么每個(gè)特征單獨(dú)看都與分類沒(méi)有關(guān)系（如果你想給機(jī)器學(xué)習(xí)找點(diǎn)亂子，就祭出 XOR 來(lái)吧）。但是，運(yùn)行包含大量特征的學(xué)習(xí)器來(lái)尋找有用的特征組合太耗時(shí)，也容易導(dǎo)致過(guò)擬合。因此，歸根到底你仍需責(zé)無(wú)旁貸地介入特征工程的工作。

更多的數(shù)據(jù)勝過(guò)更聰明的算法

假設(shè)你已經(jīng)盡你所能構(gòu)建了最好的特征集合，但分類器的效果仍不夠好，這時(shí)候應(yīng)該怎么辦呢？有兩個(gè)主要選擇：設(shè)計(jì)更好的學(xué)習(xí)算法，或者收集更多數(shù)據(jù)（包括更多的樣例和不致造成維度災(zāi)難的更多可能的原始特征）。機(jī)器學(xué)習(xí)研究者更關(guān)注前者，但從實(shí)用角度來(lái)看，最快捷的方法是收集更多數(shù)據(jù)。作為一條經(jīng)驗(yàn)，有大量數(shù)據(jù)的笨算法要?jiǎng)龠^(guò)數(shù)據(jù)量較少的聰明算法。（畢竟，機(jī)器學(xué)習(xí)就是研究如何讓數(shù)據(jù)發(fā)揮作用的。）

然而這帶來(lái)了另外一個(gè)問(wèn)題：可擴(kuò)展性（scalability）。在絕大多數(shù)計(jì)算機(jī)科學(xué)問(wèn)題中，兩個(gè)主要資源是有限的——時(shí)間和內(nèi)存。而在機(jī)器學(xué)習(xí)中，還有第三個(gè)：訓(xùn)練數(shù)據(jù)（摘注：原文training data ）。其中哪一個(gè)資源會(huì)成為瓶頸是隨著時(shí)間變化而不斷變化的。在20世紀(jì)80年代，瓶頸是數(shù)據(jù)。現(xiàn)在的瓶頸則是時(shí)間。我們有海量數(shù)據(jù)，但沒(méi)有足夠的時(shí)間處理它們，只能棄之不用。這就造成一個(gè)悖論：即使理論上說(shuō)，更多數(shù)據(jù)意味著我們可以學(xué)習(xí)更復(fù)雜的分類器，但在實(shí)踐中由于復(fù)雜分類器需要更多的學(xué)習(xí)時(shí)間，我們只能選用更簡(jiǎn)單的分類器。一個(gè)解決方案是對(duì)復(fù)雜分類器提出快速學(xué)習(xí)算法，在這個(gè)方向上已經(jīng)有了一些引人注目的進(jìn)展（例如赫爾滕（Hulten）和多明戈斯（Domingos）的工作【11】）。

采用更聰明的算法得到的回報(bào)比預(yù)期要少，一部分原因是，機(jī)器學(xué)習(xí)的工作機(jī)制基本上是相同的。這個(gè)論斷也許讓你吃驚，特別是當(dāng)你想到諸如規(guī)則集與神經(jīng)網(wǎng)絡(luò)之間差異巨大的表示方法的時(shí)候。但實(shí)際上，命題規(guī)則的確可以輕易地表示成神經(jīng)網(wǎng)絡(luò)，其他表示之間也有類似的關(guān)系。本質(zhì)上所有的學(xué)習(xí)器都是將臨近的樣例歸類到同一個(gè)類別中；關(guān)鍵的不同之處在于“臨近”的意義。對(duì)于非均勻分布的數(shù)據(jù)，不同的學(xué)習(xí)器可以產(chǎn)生迥乎不同的分類邊界，同時(shí)仍能在關(guān)心的領(lǐng)域（即那些有大量訓(xùn)練樣例、測(cè)試樣例也會(huì)有很大概率出現(xiàn)的領(lǐng)域）保證得到相的預(yù)測(cè)結(jié)果。這也有助于解釋為什么能力強(qiáng)的學(xué)習(xí)器雖然不穩(wěn)定卻仍然很精確。圖 3在二維空間展示了這一點(diǎn)，在高維空間這個(gè)效應(yīng)會(huì)更強(qiáng)。

作為一條規(guī)則，首先嘗試最簡(jiǎn)單的學(xué)習(xí)器總是有好處的（例如應(yīng)該在邏輯斯蒂回歸之前先嘗試樸素貝葉斯，在支持向量機(jī)之前先嘗試近鄰 [ 摘注：原文， na?ve Bayes before logistic?regression, k-nearest neighbor beforesupport vector machines)]）。更復(fù)雜的分類器固然誘人，但它們通常比較難駕馭，原因包括我們需要調(diào)節(jié)更多的參數(shù)才能得到好的結(jié)果，以及它們的內(nèi)部機(jī)制更不透明。

學(xué)習(xí)器可以分為兩大類：一類的表示是大小不變的，比如線性分類器（摘注：原文 linear classifiers）；另一類的表示會(huì)隨著數(shù)據(jù)而增長(zhǎng)，比如決策樹（摘注：原文 decisiontrees）。（后者有時(shí)候會(huì)被稱為非參數(shù)化學(xué)習(xí)器（nonparametric learners），但不幸的是，它們通常需要比參數(shù)化學(xué)習(xí)器學(xué)習(xí)更多的參數(shù)。）數(shù)據(jù)超過(guò)一定數(shù)量后，大小不變的學(xué)習(xí)器就不能再?gòu)闹蝎@益。（注意圖 2 中樸素貝葉斯的準(zhǔn)確率是如何逼近大約 70%的。）而如果有足夠的數(shù)據(jù)，大小可變的學(xué)習(xí)器理論上可以學(xué)習(xí)任何函數(shù)，但實(shí)際上卻無(wú)法做到。這主要是受到算法（例如貪心搜索會(huì)陷入局部最優(yōu)）和計(jì)算復(fù)雜度的限制。而且，由于維度災(zāi)難，再多的數(shù)據(jù)也不會(huì)夠。正是由于這些原因，只要你努力，聰明的算法——那些充分利用已有數(shù)據(jù)和計(jì)算資源的算法——最后總能取得成功。在設(shè)計(jì)學(xué)習(xí)器和學(xué)習(xí)分類器之間并沒(méi)有明顯的界限；因?yàn)槿魏沃R(shí)要么可以被編碼進(jìn)學(xué)習(xí)器，要么可以從數(shù)據(jù)中學(xué)到。所以，機(jī)器學(xué)習(xí)項(xiàng)目通常會(huì)有學(xué)習(xí)器設(shè)計(jì)這一重要部分，機(jī)器學(xué)習(xí)實(shí)踐者應(yīng)當(dāng)在這方面積累一些專門知識(shí)【12】。

終極而言，最大的瓶頸既不是數(shù)據(jù)，也不是 CPU速度，而是人力。在研究論文中，學(xué)習(xí)器一般都在準(zhǔn)確率和計(jì)算復(fù)雜度方面進(jìn)行比較。但更重要的是節(jié)省的人力和得到的知識(shí)，雖然這些更難度量。這使那些產(chǎn)生人類可理解的輸出的學(xué)習(xí)器（比如規(guī)則集合）更為受到青睞。機(jī)器學(xué)習(xí)成果最豐碩的，是那些建立了機(jī)器學(xué)習(xí)的基本條件，能夠便捷地在多個(gè)學(xué)習(xí)器、數(shù)據(jù)來(lái)源和學(xué)習(xí)問(wèn)題上方便有效地開展實(shí)驗(yàn)，并實(shí)現(xiàn)機(jī)器學(xué)習(xí)專家與領(lǐng)域?qū)＜业拿芮泻献鞯慕M織。

要學(xué)習(xí)很多模型，而不僅僅是一個(gè)

在機(jī)器學(xué)習(xí)早期，每個(gè)人都有一個(gè)最喜歡的學(xué)習(xí)器，并由于一些先入為主的原因堅(jiān)信它的優(yōu)越性。人們花費(fèi)大部分精力來(lái)嘗試它的各種變種，從中選擇最好的那個(gè)。后來(lái)，系統(tǒng)的實(shí)驗(yàn)比較表明在不同應(yīng)用上的最佳學(xué)習(xí)器并不相同，因此開始出現(xiàn)包含多種學(xué)習(xí)器的系統(tǒng)。這時(shí)，人們嘗試不同學(xué)習(xí)器的各種變種，仍然只是找出其中表現(xiàn)最好的那個(gè)。后來(lái)研究者注意到，如果不是只選最好的那個(gè)，而是將多個(gè)學(xué)習(xí)器結(jié)合，結(jié)果會(huì)更好——通常是好得多——而這只需要花費(fèi)人們很少的精力。

現(xiàn)在建立模型集成（model ensembles）已經(jīng)實(shí)現(xiàn)標(biāo)準(zhǔn)化【1】。最簡(jiǎn)單的集成技術(shù)是 bagging（裝袋）方法，該方法通過(guò)重采樣（resampling）隨機(jī)產(chǎn)生若干個(gè)不同的訓(xùn)練集，在每個(gè)集合上訓(xùn)練一個(gè)分類器，然后用投票（voting）的方式將結(jié)果合并。該方法比較有效，原因是它在輕度增加偏置的同時(shí)，極大地降低了方差。在boosting（強(qiáng)化提升）方法中，每個(gè)訓(xùn)練樣例都有權(quán)重，權(quán)重會(huì)不斷變化，每次訓(xùn)練新分類器的時(shí)候都集中在那些分類器之前傾向于分錯(cuò)的樣例上。在stacking（堆疊）方法中，每個(gè)單獨(dú)分類器的輸出會(huì)作為更高層分類器的輸入，更高層分類器可以判斷如何更好地合并這些來(lái)自低層的輸出。

此外，還有很多其他技術(shù)，現(xiàn)在的趨勢(shì)是越來(lái)越大型的集成。在Netflix大獎(jiǎng)賽中，來(lái)自世界各地的團(tuán)隊(duì)競(jìng)爭(zhēng)建立最好的視頻推薦系統(tǒng)（http://netflixprize.com）。隨著競(jìng)賽的開展，團(tuán)隊(duì)們開始發(fā)現(xiàn)與其他團(tuán)隊(duì)合并學(xué)習(xí)器會(huì)取得最好的結(jié)果，因此團(tuán)隊(duì)開始合并，越來(lái)越大。競(jìng)賽的第一名和第二名團(tuán)隊(duì)都合并了超過(guò)100個(gè)學(xué)習(xí)器，將這兩者集成后又進(jìn)一步提升了效果。毫無(wú)疑問(wèn)，未來(lái)我們會(huì)看到更大的集成學(xué)習(xí)器。

模型集成不應(yīng)與貝葉斯模型平均（bayesian model averaging，BMA）混淆，后者是學(xué)習(xí)的一種理論最優(yōu)化方法【4】。在貝葉斯模型平均方法中，對(duì)新樣例的預(yù)測(cè)是對(duì)假設(shè)空間中的所有分類器的預(yù)測(cè)取平均得到的，每個(gè)分類器會(huì)根據(jù)它解釋訓(xùn)練數(shù)據(jù)的能力和我們對(duì)它的先驗(yàn)信任度而有不同的權(quán)重。雖然模型集成與貝葉斯模型平均方法表面上很相似，它們其實(shí)非常不同。集成方法改變了假設(shè)空間（例如從單獨(dú)的決策樹變成了決策樹的線性組合），而且可以采用多種多樣的形式。貝葉斯模型平均方法只是根據(jù)某個(gè)準(zhǔn)則對(duì)原始空間的假設(shè)賦予不同的權(quán)重。貝葉斯模型平均方法的權(quán)重與bagging或者boosting等集成方法產(chǎn)生的權(quán)重非常不同。后者很平均，而前者波動(dòng)很大，甚至出現(xiàn)某個(gè)權(quán)重最大的分類器占據(jù)統(tǒng)治地位的情況，導(dǎo)致貝葉斯模型平均方法實(shí)際上等同于直接選擇這個(gè)權(quán)重最大的分類器【8】。一個(gè)實(shí)際的后果是，模型集成已經(jīng)成為機(jī)器學(xué)習(xí)工具的重要組成部分，而貝葉斯模型平均方法則少有人問(wèn)津。

簡(jiǎn)單并不意味著準(zhǔn)確

著名的奧坎姆剃刀（occam’s razor）原理稱：若無(wú)必要，勿增實(shí)體（entities should not be multi-plied beyond necessity）。在機(jī)器學(xué)習(xí)中，這經(jīng)常被用來(lái)表示成：對(duì)于有相同訓(xùn)練誤差的兩個(gè)分類器，比較簡(jiǎn)單的那個(gè)更可能有較低的測(cè)試誤差。關(guān)于這個(gè)斷言的證明經(jīng)常出現(xiàn)在文獻(xiàn)中，但實(shí)際上對(duì)此有很多反例，而且“沒(méi)有免費(fèi)的午餐”定理也暗示了這個(gè)斷言并不正確。

我們前面已經(jīng)看到了一個(gè)反例：模型集成。集成模型的泛化誤差會(huì)一直隨著增加新的分類器而改進(jìn)，甚至可以優(yōu)于訓(xùn)練誤差。另一個(gè)反例是支持向量機(jī)，它實(shí)際上可以有無(wú)限個(gè)參數(shù)而不至于過(guò)擬合。而與之相反，函數(shù)可以將軸上任意數(shù)量、任意分類的數(shù)據(jù)點(diǎn)劃分開，即使它只有1個(gè)參數(shù)【23】。因此，與直覺(jué)相反，在模型參數(shù)的數(shù)量和過(guò)擬合之間并無(wú)直接聯(lián)系。

一個(gè)更成熟的認(rèn)識(shí)是將復(fù)雜度等同于假設(shè)空間的大小。這是基于以下事實(shí)：更小的假設(shè)空間允許用更短的代碼表示假設(shè)。那么“理論保證”一節(jié)中的邊界就暗示了，更短的假設(shè)可以泛化得更好。這還可以進(jìn)一步改善為，為有先驗(yàn)偏好的空間中的假設(shè)分配更短的代碼。但如果將此看作是準(zhǔn)確（accuracy）和簡(jiǎn)單（simplicity）之間權(quán)衡的“證明”，那就變成循環(huán)論證了—— 我們將所偏好的假設(shè)設(shè)計(jì)得更加簡(jiǎn)單，而如果結(jié)果是準(zhǔn)確的是因?yàn)槲覀兊钠檬菧?zhǔn)確的，而不是因?yàn)檫@些假設(shè)在我們選擇的表示方法中是“簡(jiǎn)單的”（摘注：該段原文 A more sophisticated?view instead equates complexity with the size of the hypothesis space, on the basis that smaller spaces allow hypotheses to be represented by shorter codes. Bounds like the one in the section on theoretical guarantees above might then be viewed as implying that shorter hypotheses generalize better. This can be further refined by assigning shorter codes to the hypothesis in the space that we have some a priori preference for. But viewing this as “proof” of a tradeoff between accuracy and simplicity is circularreasoning: we made the hypotheses we prefer simpler by design, and if they are accurate it’s because our preferences are accurate, not because the hypotheses are “simple” in the representation we chose.）。

問(wèn)題的復(fù)雜性還來(lái)自這樣一個(gè)因素：幾乎沒(méi)有學(xué)習(xí)器能窮盡搜索整個(gè)假設(shè)空間。一個(gè)在較大的假設(shè)空間搜索較少假設(shè)的學(xué)習(xí)器，比一個(gè)在較小空間中搜索較多假設(shè)的學(xué)習(xí)器更不容易過(guò)擬合（摘注：原文 A learner with a larger hypothesis space that tries fewer hypotheses from it is less likely to over fit than one that tries more hypotheses from a smaller space.）。正如珀?duì)?#xff08;Pearl）【18】指出的，假設(shè)空間的大小只是對(duì)對(duì)確定影響訓(xùn)練誤差和測(cè)試誤差的關(guān)鍵因素有初步的指導(dǎo)意義。

多明戈斯 【7】調(diào)研了機(jī)器學(xué)習(xí)中奧坎姆剃刀原理問(wèn)題的主要論證和論據(jù)。結(jié)論是，應(yīng)當(dāng)先選擇簡(jiǎn)單假設(shè)，這是因?yàn)楹?jiǎn)單本身就是一個(gè)優(yōu)點(diǎn)，而不是因?yàn)樗僭O(shè)的與準(zhǔn)確率有什么聯(lián)系。這也許正是奧坎姆最初想表達(dá)的意思。

可表示并不意味著可學(xué)習(xí)

從本質(zhì)上講，用于大小可變的學(xué)習(xí)器的所有表示都有其形式為“每個(gè)函數(shù)都可以表達(dá)為或以無(wú)限接近的方式近似表達(dá)為××表示”的定理與之伴隨。正因?yàn)槿绱?#xff0c;某種表示方法的擁躉往往會(huì)忽略其他方法。但是，僅僅因?yàn)橐粋€(gè)函數(shù)可以被表示，并不意味著它是可被學(xué)習(xí)的。例如，標(biāo)準(zhǔn)的決策樹學(xué)習(xí)器無(wú)法學(xué)習(xí)出比訓(xùn)練樣例更多的葉子節(jié)點(diǎn)。在連續(xù)空間中，用一個(gè)固定的基元（primitives）族來(lái)表示哪怕很簡(jiǎn)單的函數(shù)，也常常要由無(wú)限多項(xiàng)組成。更進(jìn)一步，如果假設(shè)空間有許多評(píng)價(jià)函數(shù)的局部最優(yōu)點(diǎn)，正如經(jīng)常發(fā)生的那樣，學(xué)習(xí)器可能根本無(wú)法找到這個(gè)真正的函數(shù)，即使它是可表示的。給定有限數(shù)據(jù)、時(shí)間和內(nèi)存，標(biāo)準(zhǔn)學(xué)習(xí)器只能學(xué)到所有可能函數(shù)中很有限的子集。這個(gè)子集會(huì)隨著表示方法的不同而不同。因此，關(guān)鍵問(wèn)題不是“它是否可表示？”（這個(gè)問(wèn)題的答案通常無(wú)關(guān)緊要），而是“它是否可以被學(xué)習(xí)？”這值得我們嘗試不同的學(xué)習(xí)器（或者它們的組合）來(lái)尋找答案。

對(duì)某些函數(shù)來(lái)講，一些表示方法會(huì)比其他方法更加精簡(jiǎn)，從而只需要更少的數(shù)據(jù)來(lái)學(xué)習(xí)那些函數(shù)。很多學(xué)習(xí)器的工作機(jī)制是將簡(jiǎn)單的基函數(shù)（basis function）進(jìn)行線性組合。例如，支持向量機(jī)就形成了集中在某些訓(xùn)練樣例（也就是那些支持向量）上的核（kernels）的組合。如果用這種組合方法來(lái)表示 n 個(gè)比特的奇偶性（parity），將需要 2n 個(gè)基函數(shù)。但如果采用多層表示（也就是說(shuō)在輸入和輸出之間存在多步），奇偶性就可以用一個(gè)線性規(guī)模的分類器表示。探索這種深層表示的學(xué)習(xí)方法是機(jī)器學(xué)習(xí)的主要研究前沿之一 【2】。

相關(guān)并不意味著因果

相關(guān)不意味著因果，這一點(diǎn)經(jīng)常被提起，好像在這兒已經(jīng)不值得再加贅述了。但是，即使我們討論的這些學(xué)習(xí)器只能學(xué)習(xí)到相關(guān)性，它們的結(jié)果也經(jīng)常被作為因果關(guān)系來(lái)對(duì)待。這樣做錯(cuò)了么？如果是錯(cuò)的，為什么人們還這樣做呢？

更多時(shí)候，人們學(xué)習(xí)預(yù)測(cè)模型的目標(biāo)是作為行動(dòng)指南。如果我們發(fā)現(xiàn)超市里的啤酒和尿布經(jīng)常被一起購(gòu)買，那將啤酒放在尿布旁邊將會(huì)提高銷售量。（這是數(shù)據(jù)挖掘領(lǐng)域的著名例子。）但除非真的做實(shí)驗(yàn)，不然很難發(fā)現(xiàn)這一點(diǎn)。機(jī)器學(xué)習(xí)通常應(yīng)用于觀測(cè)（observational）數(shù)據(jù)，在觀測(cè)數(shù)據(jù)中預(yù)測(cè)變量并不在學(xué)習(xí)器的控制之下，這與實(shí)驗(yàn)（experimental）數(shù)據(jù)相反，后者的預(yù)測(cè)變量在控制范圍內(nèi)。一些學(xué)習(xí)算法其實(shí)有潛力做到從觀測(cè)數(shù)據(jù)發(fā)現(xiàn)因果信息，但它們的可用性比較差 【19】。而另一方面，相關(guān)性是因果關(guān)系的標(biāo)志，我們可以將其作為進(jìn)一步考察的指南（例如試圖理解因果鏈可能是什么樣）。

很多研究者相信因果只是一種為了方便而杜撰的概念。例如，在物理定律中并沒(méi)有因果的概念。因果是否真的存在是一個(gè)深?yuàn)W的哲學(xué)問(wèn)題，現(xiàn)在并沒(méi)有一個(gè)確定的答案。但對(duì)于機(jī)器學(xué)習(xí)有兩個(gè)實(shí)用的要點(diǎn)。首先，無(wú)論我們是否稱它們?yōu)椤耙蚬P(guān)系”，我們都希望能預(yù)測(cè)我們行動(dòng)的效果，而不僅僅是觀測(cè)變量之間的相關(guān)性；其次，如果你能夠獲取到實(shí)驗(yàn)數(shù)據(jù)（例如能夠隨機(jī)分配訪問(wèn)者到一個(gè)網(wǎng)站的不同版本），那么務(wù)必盡量獲取 【14】。

結(jié)論

就像其他任何一個(gè)學(xué)科那樣，機(jī)器學(xué)習(xí)擁有的很多“民間智慧”并不是那么容易就能了解到，但這些知識(shí)對(duì)于成功運(yùn)用機(jī)器學(xué)習(xí)至關(guān)重要。這篇文章總結(jié)了其中最主要的幾條知識(shí)。當(dāng)然這只是對(duì)機(jī)器學(xué)習(xí)的傳統(tǒng)學(xué)習(xí)內(nèi)容的補(bǔ)充。讀者可以參加一個(gè)有完整內(nèi)容的機(jī)器學(xué)習(xí)在線課程，其中融合了正式和非正式的知識(shí)，網(wǎng)站是http://www.cs.washington.edu/homes/pedrod/。此外，在http://videolectures.net/上還有大量寶貴的與機(jī)器學(xué)習(xí)相關(guān)的學(xué)術(shù)報(bào)告。 Weka【24】是一款優(yōu)秀的機(jī)器學(xué)習(xí)開源工具包。

祝大家學(xué)習(xí)快樂(lè)！

參考：

【1】 E. Bauer and R. Kohavi. An empirical comparison of voting classification algorithms: Bagging, boosting and variants.Machine Learning, 36:105–142, 1999.
【2】 Y. Bengio. Learning deep architectures for AI.Foundations and Trends in Machine Learning,2:1–127, 2009.

【3】 Y. Benjamini and Y. Hochberg. Controlling the false discovery rate: A practical and powerful approach to multiple testing.Journal of the Royal Statistical Society, Series B, 57:289–300, 1995.

【4】 J. M. Bernardo and A. F. M. Smith.Bayesian Theory.Wiley, New York, NY, 1994.

【5】 A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K.Warmuth. Occam’s razor. Information Processing Letters, 24:377–380, 1987.
【6】 W. W. Cohen. Grammatically biased learning:Learning logic programs using an explicit antecedent description language. Artificial Intelligence,68:303–366, 1994.

【7】 P. Domingos. 奧卡姆剃刀在知識(shí)發(fā)現(xiàn)中的角色The role of Occam’s razor in knowledge discovery. Data Mining and Knowledge Discovery, 3:409–425, 1999.

【8】 P. Domingos. Bayesian averaging of classifiers and the overfitting problem. In Proceedings of the Seventeenth International Conference on Machine Learning, pages 223–230, Stanford, CA, 2000. Morgan Kaufmann.

【9】 P. Domingos A unified bias-variance decomposition and its applications. In Proceedings of the Seventeenth International Conference on Machine Learning
pages 231–238, Stanford, CA, 2000. Morgan Kaufmann.

【10】 P. Domingos and M. Pazzani On the optimality of the simple Bayesian classifier under zero-one loss. Machine Learning, 29:103–130, 1997.

【11】 G. Hulten and P. Domingos. Mining complex models from arbitrarily large databases in constant time. In Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,pages 525–531, Edmonton, Canada, 2002. ACMPress.

【12】 D. Kibler and P. Langley. 作為一門實(shí)驗(yàn)科學(xué)的機(jī)器學(xué)習(xí)Machine learning as an experimental science. In Proceedings of the Third European Working Session on Learning, London, UK, 1988. Pitman.

【13】 A. J. Klockars and G. Sax. Multiple Comparisons.Sage, Beverly Hills, CA, 1986.

【14】 R. Kohavi, R. Longbotham, D. Sommerfield, and R. Henne. Controlled experiments on the Web: Survey and practical guide. Data Mining and Knowledge Discovery, 18:140–181, 2009.

【15】 Manyika, J., Chui, M., Brown, B.,Bughin, J., Dobbs, R., Roxburgh,C. and A.Byers 大數(shù)據(jù)：創(chuàng)新、競(jìng)爭(zhēng)和生產(chǎn)力的下一個(gè)前沿 Big data: The next frontier for innovation,competition, and productivity.Technical report, McKinsey Global Institute, 2011

【16】 Mitchell, T.M. Machine Learning.McGraw-Hill, NY, 1997

【17】 A. Y. Ng. 阻止交叉驗(yàn)證數(shù)據(jù)的“多擬合”Preventing “overfitting” of cross-validation data. In Proceedings of the Fourteenth International Conference
on Machine Learning pages 245–253, Nashville, TN, 1997. Morgan Kaufmann.

【18】 J. Pearl. 關(guān)于推斷模型之復(fù)雜性和可信性間的聯(lián)系On the connection between the complexity and credibility of inferred models. International Journal of General Systems, 4:255–264, 1978.

【19】 J. Pearl. 因果關(guān)系：模型，推理和推斷Causality: Models, Reasoning, and Inference.Cambridge University Press, Cambridge, UK, 2000.

【20】 J. R. Quinlan. C4.5: Programs for Machine Learning.Morgan Kaufmann, San Mateo, CA, 1993.

【21】 M. Richardson and P. Domingos. 馬爾科夫邏輯網(wǎng)絡(luò) Markov logic networks. Machine Learning, 62:107–136, 2006.

【22】 J. Tenenbaum, V. Silva, and J. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290:2319–2323, 2000.

【23】 V. N. Vapnik. The Nature of Statistical Learning Theory. Springer, New York, NY, 1995.

【24】 Witten, I., Frank, E. and Hall, M Data Mining: Practical Machine Learning Tools and Techniques 3rd Edition. Morgan Kaufmann,San Mateo, CA, 2011

【25】 D. Wolpert. The lack of a priori distinctions between learning algorithms. Neural Computation,8:1341–1390, 1996.

附加：下載?機(jī)器學(xué)習(xí)的那些事.Pdf?

End.

出處：http://www.36dsj.com/archives/22728

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的深度译文：机器学习那些事的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。