PAGEPAGE1010人工智能機(jī)器算法樣例學(xué)習(xí)目錄TOC\o"1-2"\h\u90011學(xué)習(xí)的形式 5293751.1監(jiān)督學(xué)習(xí) 853141.2決策樹(shù)學(xué)習(xí) 1457571.2.1決策樹(shù)的表達(dá)能力 15124581.2.2從樣例中學(xué)習(xí)決策樹(shù) 1583741.2.3選擇測(cè)試屬性 20324611.2.4泛化與過(guò)擬合 23235591.2.5拓展決策樹(shù)的適用范圍 2559621.3模型選擇與模型優(yōu)化 27921.3.1模型選擇 29311061.3.2從錯(cuò)誤率到損失函數(shù) 3187511.3.3正則化 3461991.3.4超參數(shù)調(diào)整 3583551.4學(xué)習(xí)理論 37224711.5線性回歸與分類 43208241.5.1單變量線性回歸 4359171.5.2梯度下降 45164031.5.3多變量線性回歸 48249121.5.4帶有硬閾值的線性分類器 51185411.5.5基于邏輯斯諦回歸的線性分類器 5553811.6非參數(shù)模型 59169311.6.1最近鄰模型 59307311.6.3局部敏感哈希 63319331.6.4非參數(shù)回歸 6484061.6.5支持向量機(jī) 66280761.6.6核技巧 71114511.7集成學(xué)習(xí) 73194661.7.1自助聚合法 74125711.7.2隨機(jī)森林法 75285741.7.3堆疊法 7717621.7.4自適應(yīng)提升法 78135321.7.5梯度提升法 83192061.7.6在線學(xué)習(xí) 84301941.8開(kāi)發(fā)機(jī)器學(xué)習(xí)系統(tǒng) 879971.8.1問(wèn)題形式化 87269071.8.2數(shù)據(jù)收集、評(píng)估和管理 8844591.8.3模型選擇與訓(xùn)練 93283811.8.4信任、可解釋性、可說(shuō)明性 95247571.8.5操作、監(jiān)控和維護(hù) 9730801小結(jié) 100我們用樣例學(xué)習(xí)來(lái)描述智能體通過(guò)不斷學(xué)習(xí)自己以往的經(jīng)驗(yàn)從而改善自己的行為，并對(duì)未來(lái)進(jìn)行預(yù)測(cè)的過(guò)程。如果一個(gè)智能體通過(guò)對(duì)世界進(jìn)行觀測(cè)來(lái)提高它的性能，我們稱其為智能體學(xué)習(xí)（learning）。學(xué)習(xí)可以是簡(jiǎn)單的，例如記錄一個(gè)購(gòu)物清單，也可以是復(fù)雜的，例如愛(ài)因斯坦推斷關(guān)于宇宙的新理論。當(dāng)智能體是一臺(tái)計(jì)算機(jī)時(shí)，我們稱之為機(jī)器學(xué)習(xí)（machinelearning）：一臺(tái)計(jì)算機(jī)觀測(cè)到一些數(shù)據(jù)，基于這些數(shù)據(jù)構(gòu)建一個(gè)模型（model），并將這個(gè)模型作為關(guān)于世界的一個(gè)假設(shè)（hypothesis）以及用于求解問(wèn)題的軟件的一部分。為什么我們希望一臺(tái)機(jī)器進(jìn)行學(xué)習(xí)？為什么不通過(guò)合適的方式編程然后讓它運(yùn)行呢？這里有兩個(gè)主要的原因。其一，程序的設(shè)計(jì)者無(wú)法預(yù)見(jiàn)未來(lái)所有可能發(fā)生的情形。舉例來(lái)說(shuō)，一個(gè)被設(shè)計(jì)用來(lái)導(dǎo)航迷宮的機(jī)器人必須掌握每一個(gè)它可能遇到的新迷宮的布局；一個(gè)用于預(yù)測(cè)股市價(jià)格的程序必須能適應(yīng)各種股票漲跌的情形。其二，有時(shí)候設(shè)計(jì)者并不知道如何設(shè)計(jì)一個(gè)程序來(lái)求解目標(biāo)問(wèn)題。大多數(shù)人都能辨認(rèn)自己家人的面孔，但是他們實(shí)現(xiàn)這一點(diǎn)利用的是潛意識(shí)，所以即使能力再?gòu)?qiáng)的程序員也不知道如何編寫(xiě)計(jì)算機(jī)程序來(lái)完成這項(xiàng)任務(wù)，除非他使用機(jī)器學(xué)習(xí)算法。學(xué)習(xí)的形式一個(gè)智能體程序的各個(gè)組件都可以通過(guò)機(jī)器學(xué)習(xí)進(jìn)行改進(jìn)。改進(jìn)及用于改進(jìn)的技巧取決于下面幾個(gè)因素：哪些組件可以被改進(jìn)；智能體有哪些先驗(yàn)知識(shí)，這將影響模型構(gòu)建；有哪些數(shù)據(jù)，以及關(guān)于這些數(shù)據(jù)的反饋。第2章中描述了一些智能體的設(shè)計(jì)。這些智能體的組件包括：從當(dāng)前狀態(tài)條件到動(dòng)作的直接映射；用于從感知序列推斷世界相關(guān)性質(zhì)的方法；動(dòng)作所導(dǎo)致的結(jié)果的信息；表示狀態(tài)意向的效用信息；表示動(dòng)作意向的動(dòng)作-價(jià)值信息；最希望達(dá)到的狀態(tài)，即目標(biāo)；問(wèn)題生成器、評(píng)判標(biāo)準(zhǔn)和使系統(tǒng)得以改進(jìn)的學(xué)習(xí)元素。這些組件中的任何一個(gè)都可以被學(xué)習(xí)到。我們?cè)O(shè)想一個(gè)可以通過(guò)觀測(cè)人類司機(jī)行為來(lái)學(xué)習(xí)自動(dòng)駕駛的汽車(chē)智能體。每次司機(jī)剎車(chē)時(shí)，這個(gè)智能體可以學(xué)習(xí)到一個(gè)關(guān)于什么時(shí)候該踩剎車(chē)的條件-動(dòng)作規(guī)則（組件1）。通過(guò)觀察大量包含公共汽車(chē)的照相機(jī)圖像，它可以學(xué)習(xí)到如何辨認(rèn)公共汽車(chē)（組件2）。通過(guò)嘗試不同動(dòng)作以及觀測(cè)相應(yīng)的結(jié)果（例如在潮濕的道路上艱難地剎車(chē)），它可以學(xué)習(xí)到動(dòng)作相應(yīng)的結(jié)果（組件3）。接著，如果它收到在旅途中被劇烈顛簸嚇壞了的乘客們的抱怨，它可以學(xué)習(xí)到關(guān)于其總體效用函數(shù)的一個(gè)有效組件（組件4）。機(jī)器學(xué)習(xí)技術(shù)已經(jīng)成為軟件工程的標(biāo)準(zhǔn)組成部分。無(wú)論何時(shí)你想搭建一個(gè)軟件系統(tǒng)，即使你不認(rèn)為它是一個(gè)人工智能主體，這個(gè)系統(tǒng)的組件也可能可以用機(jī)器學(xué)習(xí)的方式加以改進(jìn)。例如，一個(gè)用于分析星系在引力透鏡下的圖像的軟件可以通過(guò)機(jī)器學(xué)習(xí)的模型加速一千萬(wàn)倍（Hezavehetal.,2017）；通過(guò)采用另一種機(jī)器學(xué)習(xí)的模型可以將數(shù)中心冷卻的能耗降低40%（Gao, 2014）。圖靈獎(jiǎng)得主大衛(wèi)·帕特（DavidPatterson）和谷歌AI的掌門(mén)人杰夫·迪安（JeffDean）宣稱，計(jì)算機(jī)體系結(jié)構(gòu)的“黃金時(shí)代”的到來(lái)正歸功于機(jī)器學(xué)習(xí)（Deanetal.,2018）。我們已經(jīng)見(jiàn)過(guò)了一些關(guān)于智能體組件的模型示例：原子模型、因子化模型，以及基于邏輯的關(guān)系模型或基于概率的關(guān)系模型等。人們針對(duì)所有這些模型設(shè)計(jì)了廣泛的學(xué)習(xí)算法。本文中我們假設(shè)不存在關(guān)于這個(gè)智能體的先驗(yàn)知識(shí)（priorknowledge）：它從零開(kāi)始，從數(shù)據(jù)中學(xué)習(xí)。在21.7.2節(jié)中，我們將考慮遷移學(xué)習(xí)（transfer learning），在這種情形下，一個(gè)領(lǐng)域的知識(shí)被遷到一個(gè)新的領(lǐng)域，以更少的數(shù)據(jù)使學(xué)習(xí)過(guò)程進(jìn)行得更快。我們當(dāng)然還要假設(shè)系統(tǒng)的設(shè)計(jì)者選取了合適的模型框架，從而讓學(xué)習(xí)過(guò)程變得更加有效。從一組特定的觀測(cè)結(jié)果得出一個(gè)普遍的規(guī)則，我們稱之為歸納（induction）。例如，我們觀察到，過(guò)去的每一天太陽(yáng)都會(huì)升起，因此我們推斷太陽(yáng)明天也會(huì)升起。這與我們?cè)诘?章中研究的演繹（deduction）不同，因?yàn)闅w納的結(jié)論可能是不正確的，然而在演繹中，只要前提是正確的，演繹的結(jié)論就保證是正確的。本文將集中討論輸入為因子化表示（factoredrepresentation）——屬性值組成的向量——的問(wèn)題。輸入也可以是任意類型的數(shù)據(jù)結(jié)構(gòu)，包括原子表示的數(shù)據(jù)和關(guān)系數(shù)據(jù)等。當(dāng)輸出是一個(gè)有限集合中的某個(gè)值時(shí)（如晴天/陰天/雨天或者正確/錯(cuò)誤），我們稱該學(xué)習(xí)問(wèn)題為分類（classification）。當(dāng)輸出是一個(gè)數(shù)值時(shí)（例如明天的溫度，無(wú)論它是一個(gè)整數(shù)還是其他實(shí)數(shù)），我們稱該學(xué)習(xí)問(wèn)題為回歸（regression）（這個(gè)詞有些晦澀難懂[1]）。一個(gè)更好的名稱是函數(shù)逼近或者數(shù)值預(yù)測(cè)。但在1886年，法國(guó)人弗朗西斯·高爾頓（FrancisGalton）寫(xiě)了一篇關(guān)于這一概念的富有影響力的文章regressiontothemean（例如，高個(gè)子父母）。高爾頓用他所稱的“回歸線”示，之后讀者逐漸把“回歸”一詞與函數(shù)逼近這一統(tǒng)計(jì)技術(shù)聯(lián)系起來(lái)，而不是與回歸于均值的主題聯(lián)系起來(lái)。伴隨輸入有3種類型的反饋（feedback），它們決定了3種類型的學(xué)習(xí)。在監(jiān)督學(xué)習(xí)（supervised learning）中，智能體觀測(cè)到輸入-輸對(duì)，并學(xué)習(xí)從輸入到輸出的一個(gè)函數(shù)映射。舉個(gè)例子來(lái)說(shuō)，輸入是照相機(jī)的圖像，伴隨輸入的輸出就是“公共汽車(chē)”或者“行人”等。諸如此類的輸出，我們稱之為標(biāo)簽（label）。在智能體學(xué)習(xí)到一個(gè)函數(shù)之后，如果給它一個(gè)新的圖像輸入，它將預(yù)測(cè)一個(gè)合適的標(biāo)簽。對(duì)于踩剎車(chē)這一動(dòng)作的學(xué)習(xí)（上述的組件1），其輸入是當(dāng)前的狀態(tài)（車(chē)的速度和行駛方向、道路條件），輸出是開(kāi)始剎車(chē)到停車(chē)所需要行駛的距離。在這種情形下，智能體可以直接從自己的感知中獲得輸出值（在動(dòng)作結(jié)束之后）；環(huán)境就是老師，智能體學(xué)習(xí)的是從當(dāng)前狀態(tài)到剎車(chē)距離的一個(gè)函數(shù)。在無(wú)監(jiān)督學(xué)習(xí)（unsupervisedlearning）中，智能體從沒(méi)有任何顯式反饋的輸入中學(xué)習(xí)模式。最常見(jiàn)的無(wú)監(jiān)督學(xué)習(xí)任務(wù)是聚類（clustering）：通過(guò)輸入樣例來(lái)檢測(cè)潛在的有價(jià)值的聚類簇。例如，我們從互聯(lián)網(wǎng)上可以獲取數(shù)百萬(wàn)個(gè)圖像，一個(gè)計(jì)算機(jī)視覺(jué)系統(tǒng)可以識(shí)別一大類相似的、被人類稱為“貓”的圖像。在強(qiáng)化學(xué)習(xí)（reinforcementlearning）中，智能體從一系列的強(qiáng)化——獎(jiǎng)勵(lì)與懲罰——中進(jìn)行學(xué)習(xí)。舉例來(lái)說(shuō)，在一局國(guó)際象棋比賽結(jié)束時(shí)，智能體會(huì)被告知它贏了（獎(jiǎng)勵(lì)）還是輸了（懲罰）。智能體判斷之前采取的哪個(gè)動(dòng)作該為這一結(jié)果負(fù)責(zé)，并且改變它的動(dòng)作以在未來(lái)得到更多的獎(jiǎng)勵(lì)。監(jiān)督學(xué)習(xí)更正式地說(shuō)，監(jiān)督學(xué)習(xí)的任務(wù)如下。給定一個(gè)訓(xùn)練集（trainingset）含有N個(gè)“輸入-輸出”對(duì)樣例：其中每一對(duì)數(shù)據(jù)都由一個(gè)未知的函數(shù)生成找一個(gè)函數(shù)h來(lái)近似真實(shí)的函數(shù)f。函數(shù)h被稱為關(guān)于世界的假設(shè)（hypothesis）。它取自一個(gè)假設(shè)空間（hypothesis space）H間可能是最高次數(shù)為3的多項(xiàng)式集合、JavaScript函數(shù)的集合，也可能是所有3-SAT布爾邏輯公式的集合。同樣地，我們可以稱h是關(guān)于數(shù)據(jù)的模型，它取自模型類（modelclass）H，也可以說(shuō)它取自函數(shù)類（function class）中的一個(gè)函（function）。我們稱輸出yi為真實(shí)數(shù)據(jù)（groundtruth）——我們希望模型能預(yù)測(cè)的正確答案。那么，如何選擇一個(gè)假設(shè)空間呢？我們可能有一些關(guān)于數(shù)據(jù)生成過(guò)程的先驗(yàn)知識(shí)。如果沒(méi)有的話，可以采用探索性數(shù)據(jù)分析（exploratorydataanalysis）：通過(guò)統(tǒng)計(jì)檢驗(yàn)和可視化方法——直方圖、散點(diǎn)圖、箱形圖——來(lái)探索數(shù)據(jù)以獲得對(duì)數(shù)據(jù)的一些理解，以及洞察哪些假設(shè)空間可能是合適的。或者我們可以直接嘗試多種不同的假設(shè)空間，然后評(píng)估哪個(gè)假設(shè)空間的效果最好。有了假設(shè)空間后，如何從中選擇一個(gè)好的假設(shè)呢？我們希望尋找一個(gè)一致性假設(shè)（consistenthypothesis）：假設(shè)h，對(duì)訓(xùn)練集中的任意一個(gè)xi，都有h(xiyi。如果輸出是連續(xù)值，我們不能期望模型輸出與真實(shí)數(shù)據(jù)精確匹配；相反，我們可以寄希望于尋找一個(gè)最佳擬合函數(shù)（best-fitfunction），使得每一個(gè)h(xi)與yi非常接近（我們將在19.4.2節(jié)中給出正式表述）。衡量一個(gè)假設(shè)的標(biāo)準(zhǔn)不是看它在訓(xùn)練集上的表現(xiàn)，而是取決于它如何處理尚未觀測(cè)到的輸入。我們可以使用一個(gè)測(cè)試集（testset）——第二組樣本數(shù)據(jù)對(duì)(xi,yi)——來(lái)評(píng)估假設(shè)。如果h準(zhǔn)確地預(yù)測(cè)了測(cè)試集的輸出，我們稱h具有很好的泛化（generalize）能力。圖19-1展示了一個(gè)學(xué)習(xí)算法所得到的函數(shù)h依賴于假設(shè)所考慮的假設(shè)空間H和給定的訓(xùn)練集。第一行的4幅圖使用同一個(gè)訓(xùn)練集，訓(xùn)練集中包含13個(gè)(x, y)平面上的數(shù)據(jù)點(diǎn)。第二行的4幅圖使用第二組由13個(gè)數(shù)據(jù)點(diǎn)組成的訓(xùn)練集；兩個(gè)訓(xùn)練集都代表了某個(gè)未知的函數(shù)f (x)。每一展示了不同假設(shè)空間中的最佳擬合假設(shè)h。列1：直線；形的函數(shù)。對(duì)于這些數(shù)據(jù)點(diǎn)，不存在一致性假設(shè)的直線。圖19-1 尋找擬合數(shù)據(jù)的假設(shè)。第一行：在數(shù)據(jù)集1上訓(xùn)練的來(lái)自4個(gè)不同假設(shè)空間的最佳擬函數(shù)的4個(gè)圖像。第二行：同樣的4個(gè)函數(shù)，但是在稍有不同的數(shù)據(jù)集上進(jìn)行訓(xùn)練得到的結(jié)果（數(shù)據(jù)集采樣自相同的函數(shù)f(x)）列2：形的正弦函數(shù)。這個(gè)假設(shè)并不是完全一致的，但是將兩個(gè)數(shù)據(jù)集都擬合得非常好。列3個(gè)數(shù)據(jù)點(diǎn)。這類函數(shù)永遠(yuǎn)是一致的。列4：形如 的12次多項(xiàng)式。這類函數(shù)是一致的：們總是能找到一個(gè)12次多項(xiàng)式來(lái)準(zhǔn)確地?cái)M合13這是一個(gè)好的預(yù)測(cè)。分析假設(shè)空間的一個(gè)方法是分析它們帶來(lái)的偏差（不考慮訓(xùn)練集）和它們產(chǎn)生的方差（從一個(gè)訓(xùn)練集到另一個(gè)訓(xùn)練集）。我們所說(shuō)的偏差（bias）是指（不嚴(yán)格地）在不同的訓(xùn)練集上，假設(shè)所預(yù)測(cè)的值偏離期望值的平均趨勢(shì)。偏差常常是由假設(shè)空間所施加的約束造成的。例如，當(dāng)假設(shè)空間是線性函數(shù)時(shí)會(huì)導(dǎo)致較大的偏差：它只允許函數(shù)圖像是一條直線。如果數(shù)據(jù)中除了直線的整體斜率以外還存在別的模式，線性函數(shù)將無(wú)法表示其他的模式。當(dāng)一個(gè)假設(shè)不能找到數(shù)據(jù)中的模式時(shí)，我們稱它是欠擬合（underfitting）的。但是，分段線性函數(shù)具有較小的偏差，其函數(shù)的形狀是由數(shù)據(jù)決定的。我們所說(shuō)的方差（variance）是指由訓(xùn)練數(shù)據(jù)波動(dòng)而導(dǎo)致假設(shè)的變化量。圖19-1的兩行所使用的數(shù)據(jù)集采樣于同一個(gè)函數(shù)f(x)。兩個(gè)數(shù)據(jù)集略有不同。對(duì)前三列函數(shù)來(lái)說(shuō)，數(shù)據(jù)集的略微不同導(dǎo)致的假設(shè)差別比較小，我們稱之為低方差的。但是第4列中的12次多項(xiàng)式函數(shù)則具有較大方差：可以看到它們?cè)趚軸兩端的表現(xiàn)差別很大。顯然，這兩個(gè)多項(xiàng)式中至少有一個(gè)多項(xiàng)式對(duì)正確的函數(shù)f(x)的擬合效果較差。當(dāng)一個(gè)函數(shù)過(guò)于關(guān)注它用來(lái)訓(xùn)練的特定訓(xùn)練數(shù)據(jù)集，進(jìn)而導(dǎo)致它在沒(méi)有見(jiàn)過(guò)的數(shù)據(jù)上表現(xiàn)較差時(shí)，我們稱該函數(shù)對(duì)數(shù)據(jù)集是過(guò)擬合（overfitting）的。通常這其中存在一個(gè)偏差-方差權(quán)衡（bias-variancetradeoff）：在更復(fù)雜、低偏差的能較好擬合訓(xùn)練集的假設(shè)與更簡(jiǎn)單、低方差的可能泛化得更好的假設(shè)中做出選擇。阿爾伯特·愛(ài)因斯坦（Albert Einstein）曾于1933年說(shuō)過(guò)，“任何理論的終極目標(biāo)都是盡可能讓不可削減的基本元素變得更加簡(jiǎn)單且更少，但也不能放棄對(duì)任何一個(gè)單一經(jīng)驗(yàn)數(shù)據(jù)的充分闡釋”。換句話說(shuō)，愛(ài)因斯坦建議選擇與數(shù)據(jù)相符的最簡(jiǎn)單的假設(shè)。這個(gè)原則可以追溯到14世紀(jì)的英國(guó)哲學(xué)家?jiàn)W卡姆的威廉（William ofOckham[2]），他的原則“如無(wú)必要，勿增實(shí)體”被稱為奧卡姆剃刀原則（Ockham’srazor），因?yàn)樗挥脕?lái)“剔除”含糊的解釋。“Occam”。奧卡姆是英國(guó)一座小鎮(zhèn)的名字，是威廉出生的地方。他在牛津大學(xué)注冊(cè)時(shí)用的名字是“奧卡姆的威廉”，后來(lái)人們習(xí)慣性地把他提出的觀點(diǎn)概括地稱為“奧卡姆剃刀原則”。——編者注定義簡(jiǎn)單性并不容易。顯然，只有兩個(gè)參數(shù)的多項(xiàng)式比有13個(gè)參數(shù)的多項(xiàng)式簡(jiǎn)單。在19.3.4節(jié)中，我們將更加精確具體地表述這種直覺(jué)。然而，在第21章中，我們將會(huì)看到，深度神經(jīng)網(wǎng)絡(luò)模型往往可以泛化得非常好，盡管它們非常復(fù)雜——其中有些網(wǎng)絡(luò)的參數(shù)達(dá)到數(shù)十億個(gè)。所以，僅通過(guò)參數(shù)個(gè)數(shù)本身來(lái)衡量模型的適合程度并不是一個(gè)好方法。因此我們或許應(yīng)該將目標(biāo)定為選擇“合適”而不是“簡(jiǎn)單”的模型類。我們將在19.4.1節(jié)中考慮這個(gè)問(wèn)題。在圖19-1中，我們并不確定哪個(gè)假設(shè)是最佳的。如果我們知道數(shù)據(jù)所表示的內(nèi)容，例如，一個(gè)網(wǎng)站的點(diǎn)擊量每天都在增長(zhǎng)，并且會(huì)根據(jù)一天的時(shí)間周期性變化，那么我們可能會(huì)更傾向于選擇正弦函數(shù)。如果我們知道數(shù)據(jù)不是周期性的并且存在較大的噪聲，那么我們可能傾向于選擇線性函數(shù)。在某些情形下，相比于僅僅判斷一個(gè)假設(shè)是可能還是不可能的，分析者更愿意給出一個(gè)假設(shè)可能發(fā)生的概率。監(jiān)督學(xué)習(xí)可以通過(guò)選擇假設(shè)h*（在數(shù)據(jù)集上h*發(fā)生概率最大）來(lái)實(shí)現(xiàn)：根據(jù)貝葉斯法則，上式等價(jià)于：于是我們可以認(rèn)為，光滑的一次或二次多項(xiàng)式的先驗(yàn)概率P(h)是較高的，而有較大波動(dòng)的12次多項(xiàng)式的先驗(yàn)概率是較低的。當(dāng)數(shù)據(jù)表示我們確實(shí)需要使用一些不尋常的函數(shù)進(jìn)行擬合時(shí)，我們也可以使用這些不尋常的函數(shù)，但我們通過(guò)賦予它們一個(gè)較低的先驗(yàn)概率來(lái)盡可能避免這種情況。為什么我們不將H取為所有計(jì)算機(jī)程序或所有圖靈機(jī)構(gòu)成的類呢？這里存在一個(gè)問(wèn)題，在假設(shè)空間的表達(dá)能力與在該假設(shè)空間中尋找一個(gè)合適的假設(shè)所需的計(jì)算復(fù)雜性之間存在一種權(quán)衡。舉例來(lái)說(shuō)，根據(jù)數(shù)據(jù)擬合一條直線是易于計(jì)算的；然而擬合一個(gè)高次的多項(xiàng)式則較為困難；擬合一個(gè)圖靈機(jī)則是不可判定的。我們傾向于選擇簡(jiǎn)單假設(shè)空間的第二個(gè)原因是，我們可能會(huì)在學(xué)習(xí)完h后使用它，當(dāng)h是一個(gè)線性函數(shù)時(shí)，計(jì)算h(x)是很快的，然而計(jì)算任意的圖靈機(jī)程序甚至不能保證程序終止。基于這些原因，大多數(shù)關(guān)于學(xué)習(xí)的工作都集中在簡(jiǎn)單的表示上。近年來(lái)，人們對(duì)深度學(xué)習(xí)產(chǎn)生了極大的興趣（第21章），它對(duì)函數(shù)的表示并不簡(jiǎn)單，但是h(x)仍然只需使用適當(dāng)?shù)挠布M(jìn)行有限步的計(jì)算就可以得到。我們將看到，表達(dá)能力與復(fù)雜性的權(quán)衡并不簡(jiǎn)單：正如我們?cè)诘?章一階邏輯中所看到的，通常情況下，表達(dá)性語(yǔ)言使簡(jiǎn)單的假設(shè)能夠與數(shù)據(jù)相匹配，而限制語(yǔ)言的表達(dá)能力則意味著任何一致性假設(shè)都必定是復(fù)雜的。問(wèn)題示例：餐廳等待問(wèn)題我們將詳細(xì)描述一個(gè)監(jiān)督學(xué)習(xí)問(wèn)題的例子：決定是否在一家餐廳等待位置的問(wèn)題。這個(gè)問(wèn)題將貫穿整章，用于比較不同的模型類。在這個(gè)問(wèn)題中，輸出y是一個(gè)布爾變量，我們將其稱為是否等待（WillWait）；當(dāng)我們決定在餐廳等待位置時(shí)它的值為真。輸入x是有10個(gè)屬性值的向量，每個(gè)屬性都是離散的值。候補(bǔ)（Alternate）：廳。吧臺(tái)（Bar）：該餐廳是否有舒適的吧臺(tái)用于等待。周五/六（Fri/Sat）：今天是否為周五或周六。饑餓（Hungry）：現(xiàn)在是不是餓了。顧客（Patrons）：目前餐廳有多少顧客（值為None、Some、Full）。價(jià)格（Price）：餐廳的價(jià)格范圍（$、$$,、$$$）。下雨（Raining）：外面是否正在下雨。預(yù)約（Reservation）：我們是否有預(yù)訂。種類（Type）：餐廳種類（French、Italian、Thai或Burger）。（WaitEstimate）：對(duì)等待時(shí)間的估計(jì)（0～10分鐘、10～30分鐘、30～60分鐘或60分鐘）。圖19-2給出了一組12個(gè)樣例，這些樣例取自本書(shū)作者羅素（SR）的切身經(jīng)歷。注意，數(shù)據(jù)量是很少的：輸入屬性的值一共有種可能的組合，但是我們只得到了其中12個(gè)組合的正確輸出，其他9204個(gè)結(jié)果可能為真，也可能為假，我們并不知道。這就是歸納的關(guān)鍵：我們需要通過(guò)僅有的12個(gè)樣例，對(duì)缺失的9204個(gè)輸出值給出最好的猜測(cè)。圖19-2 餐廳等待問(wèn)題領(lǐng)域的樣例決策樹(shù)學(xué)習(xí)決策樹(shù)（decisiontree）表示了這么一類函數(shù)——它將屬性值向量映射到單個(gè)輸出值（即“決策”）。決策樹(shù)通過(guò)執(zhí)行一系列測(cè)試來(lái)實(shí)現(xiàn)其決策，它從根節(jié)點(diǎn)出發(fā)，沿著適當(dāng)?shù)姆种В钡降竭_(dá)葉節(jié)點(diǎn)為止。樹(shù)中的每個(gè)內(nèi)部節(jié)點(diǎn)對(duì)應(yīng)于一個(gè)輸入屬性的測(cè)試，該節(jié)點(diǎn)的分支用該屬性的所有可能值進(jìn)行標(biāo)記，葉節(jié)點(diǎn)指定了函數(shù)要返回的值。通常來(lái)說(shuō)，一個(gè)函數(shù)的輸入與輸出可以是離散的或連續(xù)的，這里我們只考慮輸入為離散值，輸出為真（一個(gè)正樣例）或假（一個(gè)負(fù)樣例）的函數(shù)。我們稱該情形為布爾分類（Booleanclassification）。我們用字母j來(lái)標(biāo)記樣例（xj代表第j個(gè)樣例的輸入向量，yj代表該樣例的輸出），此外xj,i代表第j個(gè)樣例的第i個(gè)屬性。如圖19-3所示，該樹(shù)代表了SR用于餐廳等待問(wèn)題的決策函數(shù)。沿著樹(shù)的分支，我們可以發(fā)現(xiàn)，Patrons=Full與WaitEstimate=0～10的樣例會(huì)被分類為正（即“yes”，我們將在餐廳等待）。圖19-3 決定是否在餐廳等待的決策樹(shù)決策樹(shù)的表達(dá)能力一棵布爾型的決策樹(shù)等價(jià)于如下形式的邏輯語(yǔ)句：其中每個(gè)Pathi是從根節(jié)點(diǎn)到true葉節(jié)點(diǎn)的路徑上的屬性-值測(cè)試形式的合取。因此，完整的表達(dá)式為析取范式的形式，這意味著命題邏輯中的任何函數(shù)都可以表示為決策樹(shù)。際上，許多內(nèi)容為“如何……”的指南手冊(cè)（如，汽車(chē)維修）都會(huì)按決策策樹(shù)來(lái)表示；奇偶性函數(shù)也有這樣的問(wèn)題，當(dāng)且僅當(dāng)偶數(shù)個(gè)輸入為真時(shí)，它的輸出為真。當(dāng)輸入屬性為實(shí)數(shù)值時(shí)，形如的函數(shù)很好表示的，而對(duì)另一些函數(shù)來(lái)說(shuō)卻是不合適的。是否存在一種表示方式使得任何函數(shù)都能被有效地表示？遺憾的是，答案是否定的——函數(shù)的形式過(guò)多，無(wú)法用少量的位來(lái)全部表示。甚至即使僅僅考慮含有n個(gè)屬性值的布爾函數(shù)，真值表也會(huì)有2n行，并且每一行的輸出有真與假兩種情形，因此存在個(gè)不同的函數(shù)。如果性值是20個(gè)，那么就存在個(gè)函數(shù)，所以如果我們把表示限制在百萬(wàn)位內(nèi)，我們就不能表示所有的這些函數(shù)。從樣例中學(xué)習(xí)決策樹(shù)我們希望找到一棵與圖19-2中的樣例保持一致并盡可能小的決策近的樹(shù)。算法采用貪心與分治的策略：我們總是首先測(cè)試子問(wèn)題。我們所說(shuō)的“最重要的屬性”指的是對(duì)一個(gè)樣例的分類結(jié)果能產(chǎn)淺。圖19-4a表明Type是一個(gè)較差的屬性，因?yàn)樗妮敵鲇?種可能，并且每種可能中含有相同數(shù)量的正樣例與負(fù)樣例。另外，在圖19-4b中我們發(fā)現(xiàn)Patrons是一個(gè)相當(dāng)重要的屬性，因?yàn)槿绻渲禐镹one或者Some，那么剩余的樣例將會(huì)有準(zhǔn)確的輸出（分別為No或者Yes）；如果其屬性值為Full，仍將有混合的樣例集。對(duì)于這些遞歸子問(wèn)題，我們需要考慮以下4個(gè)方面。如果剩余的樣例全為正（或全為負(fù)），那么我們已經(jīng)達(dá)成目標(biāo)，可以輸出Yes或No。圖19-4bNone和Some的分支中。對(duì)樣例進(jìn)行分割。圖19-4b中所示的是Hungry屬性被用于分割剩余的樣例。合的樣例，將返回構(gòu)造該節(jié)點(diǎn)的父節(jié)點(diǎn)的樣例集中最常見(jiàn)的輸出值。如果分割后沒(méi)有任何其他的屬性剩余，但是存在正負(fù)兩種樣例，這意味著，這些樣例有完全相同的屬性值組合，但分類不同。這是可能發(fā)生的，或是因?yàn)閿?shù)據(jù)中存在錯(cuò)誤或噪聲（noise），域是非確定性的，再或是因?yàn)槲覀儫o(wú)法觀測(cè)到可以區(qū)分樣例的屬性。此時(shí)的最好的選擇就是返回剩余樣例中最常見(jiàn)的輸出值。圖19-4 通過(guò)測(cè)試屬性來(lái)對(duì)樣例進(jìn)行分割。在每一個(gè)節(jié)點(diǎn)中我們給出剩余樣例的正（綠色方框）負(fù)（紅色方框）情況。（a）根據(jù)Type分割樣例，沒(méi)有為我們分辨正負(fù)帶來(lái)幫助。（b）根分割樣例，很好地區(qū)分了正負(fù)樣例。在根據(jù)Patrons進(jìn)行分類之后，Hungry是相對(duì)較好的第二個(gè)測(cè)試屬性圖195所示為算法。注意，樣例集是算法的一個(gè)輸屬性的測(cè)試、分支上的屬性值和葉節(jié)點(diǎn)上的輸出組成。在19.3.3節(jié)中，我們將給出重要性函數(shù)的細(xì)節(jié)。圖196給出了學(xué)習(xí)算法在樣本訓(xùn)練集上的輸出結(jié)果。該樹(shù)與我們?cè)趫D19-3中給出的原始樹(shù)截然不同。一些讀者可能會(huì)得出這樣的結(jié)論：學(xué)習(xí)算法并沒(méi)有很好地學(xué)習(xí)正確的函數(shù)。事實(shí)上，這是一個(gè)錯(cuò)誤的結(jié)論。學(xué)習(xí)算法著眼于examples，而不是正確的函數(shù)，從現(xiàn)實(shí)來(lái)看，它的假設(shè)（見(jiàn)圖19-6）不僅與所有樣例一能會(huì)非常不同，但它所表示的函數(shù)是相似的。圖19-5 。重要性函數(shù)IMPORTANCE將在19.3.3節(jié)中給出，函數(shù)PLURALITY-VALUE將選擇樣例集中最常見(jiàn)的輸出，并隨機(jī)地?cái)嚅_(kāi)連接圖19-6 根據(jù)12樣例訓(xùn)練集推斷出的決策樹(shù)學(xué)習(xí)算法不需要包含對(duì)Raining與Reservation兩個(gè)屬性的測(cè)試，因?yàn)樗梢栽跊](méi)有這兩個(gè)屬性的情況下對(duì)所有樣例進(jìn)行分類。它還發(fā)現(xiàn)了一個(gè)有趣的、此前未被注意到的模式：SR會(huì)在周末等待泰國(guó)菜（Thai）。在一些沒(méi)有任何樣例被觀測(cè)到的情形中，決策樹(shù)也必然會(huì)犯一些錯(cuò)誤。例如，決策樹(shù)未觀測(cè)到等待時(shí)間為0～10這種情況下，當(dāng)Hungry屬性值為假時(shí)，決策樹(shù)的輸出是No，即不等待，但SR肯定會(huì)選擇等待。如果有更多的訓(xùn)練樣例，決策樹(shù)就可以在學(xué)習(xí)過(guò)程中糾正這個(gè)錯(cuò)誤。我們可以用學(xué)習(xí)曲線（learningcurve）來(lái)評(píng)估學(xué)習(xí)算法的表現(xiàn)，如圖19-7所示。在這個(gè)圖中，有100個(gè)樣例可供學(xué)習(xí)使用，我們將它們隨機(jī)分割為一個(gè)訓(xùn)練集和一個(gè)測(cè)試集。我們使用訓(xùn)練集學(xué)習(xí)假設(shè)h，并用測(cè)試集來(lái)度量其準(zhǔn)確率。我們可以從大小為1個(gè)樣例的訓(xùn)練集開(kāi)始訓(xùn)練與測(cè)試的過(guò)程，每次增加1個(gè)訓(xùn)練樣例，直到訓(xùn)練集包含99個(gè)樣例。對(duì)于每種大小的訓(xùn)練集，我們實(shí)際操作時(shí)重復(fù)隨機(jī)分割訓(xùn)練集和測(cè)試集的過(guò)程20次，并對(duì)這20次試驗(yàn)的結(jié)果取平均值。曲線的結(jié)果表明，隨著訓(xùn)練集大小的增加，準(zhǔn)確率將提高。出于這個(gè)原因，學(xué)習(xí)曲線也被稱為快樂(lè)圖（happygraph）。在這張圖中，準(zhǔn)確率最終達(dá)到了95%，并且從趨勢(shì)上看，如果有更多的數(shù)據(jù)，曲線可能會(huì)繼續(xù)上升。圖19-7 一個(gè)決策樹(shù)的學(xué)習(xí)曲線，數(shù)據(jù)集為從餐廳等待問(wèn)題領(lǐng)域中隨機(jī)產(chǎn)生的100個(gè)樣例。圖每個(gè)點(diǎn)都是20次試驗(yàn)的均值選擇測(cè)試屬性決策樹(shù)學(xué)習(xí)算法會(huì)選擇重要性IMPORTANCE最高的屬性。我們現(xiàn)在將陳述如何使用信息增益這一概念來(lái)度量重要性。信息增益是從熵（entropy）的角度進(jìn)行定義的，而熵是信息論中最基本的量（ShannonandWeaver,1949）。熵是隨機(jī)變量不確定性的度量；信息量越多，熵越小。一個(gè)只有一個(gè)可能值的隨機(jī)變量（如一枚總是正面朝上的硬幣）沒(méi)有不確定性，因此它的熵為0。一枚公平的硬幣在拋擲時(shí)出現(xiàn)正面或反面朝上的概率相同，我們將證明它的熵為“1位”。一個(gè)公平的四面骰子的熵為2位，因?yàn)樗?2種可能性相同的選擇。現(xiàn)在考慮一枚不公平的硬幣，它在99%的情況下都是正面朝上。直覺(jué)告訴我們，這枚硬幣含有的不確定性比公平硬幣要少——如果我們猜測(cè)正面朝上，只會(huì)有1%的情況是錯(cuò)的——所以我們希望它有一個(gè)接近于0，但為正的熵。一般情況下，若一個(gè)隨機(jī)變量V取值為vk的概率為P(vk)，那么它的熵H(V)定義為我們可以驗(yàn)證一枚公平硬幣被拋擲的熵確實(shí)是1位：而一個(gè)四面骰子的熵是2位：對(duì)于99%的情況出現(xiàn)正面的硬幣，有一個(gè)布爾隨機(jī)變量，如果其為真的概率是q，則該變量的熵B(q)定義為因此，。現(xiàn)在我們回過(guò)頭來(lái)看決策樹(shù)的學(xué)習(xí)。如果一個(gè)訓(xùn)練集包含p個(gè)正樣例和n輸出變量的熵為在圖19-2所示的餐廳訓(xùn)練集中，有p = n = 6，因此相應(yīng)的是B(0.5)，或恰好為1位。對(duì)屬性A的測(cè)試結(jié)果會(huì)給我們提供一些信息，從而減少一些整體的熵。我們可以通過(guò)觀察屬性測(cè)試后剩余的熵來(lái)度量這種減少。若一個(gè)具有d個(gè)不同值的屬性A將訓(xùn)練集E劃分為子集E1,…,Ed個(gè)子集Ek含有pk個(gè)正樣例與nk個(gè)負(fù)樣例，那么如果我們沿著該分支前進(jìn)，將需要額外的位的信息來(lái)處理問(wèn)題。從訓(xùn)練集中隨選取一個(gè)樣例，它具有該屬性的第k個(gè)值（即該樣例在Ek中的概率為），因此在測(cè)試屬性A后剩余的熵的期望為通過(guò)測(cè)試屬性A獲得的信息增益（information gain）定義為熵減的期望值：事實(shí)上，an正是我們實(shí)現(xiàn)重要性函數(shù)需要的。回顧圖19-4中所考慮的屬性，有這證實(shí)了我們的直覺(jué)，即Patrons最適合作為優(yōu)先考慮的分割屬性。事實(shí)上，Patrons在所有的屬性中有最大的信息增益，因此將被決策樹(shù)學(xué)習(xí)算法選擇作為樹(shù)的根。泛化與過(guò)擬合19-1中我們看到，一個(gè)高階多項(xiàng)式可以擬合所有數(shù)據(jù)，但它在擬合數(shù)據(jù)數(shù)量的增加，過(guò)擬合的可能性將越來(lái)越大，而隨著訓(xùn)練樣例數(shù)量的增加，過(guò)擬合的可能性會(huì)越來(lái)越小。較大的假設(shè)空間（點(diǎn)的決策樹(shù)或具有更高階數(shù)的多項(xiàng)式空間）力，某些模型類比其他模型類更容易過(guò)擬合。對(duì)決策樹(shù)來(lái)說(shuō)，一種稱為決策樹(shù)剪枝（decisiontreepruning）的技術(shù)可以用于減輕過(guò)擬合。剪枝通過(guò)刪去不明顯相關(guān)的節(jié)點(diǎn)來(lái)實(shí)現(xiàn)。我們從一棵完整的樹(shù)出發(fā)，它由LEARN-DECISION-TREE生成。接著我們研究一個(gè)只有葉節(jié)點(diǎn)作為子節(jié)點(diǎn)的測(cè)試節(jié)點(diǎn)，如果該節(jié)點(diǎn)的測(cè)試效果為不相關(guān)——它只測(cè)試數(shù)據(jù)中的噪聲——那么我們將刪去該測(cè)試節(jié)點(diǎn)，并用它的葉節(jié)點(diǎn)替換它。重復(fù)這個(gè)過(guò)程，考慮每個(gè)只有葉節(jié)點(diǎn)作為子節(jié)點(diǎn)的測(cè)試節(jié)點(diǎn)，直到每個(gè)測(cè)試節(jié)點(diǎn)都被剪枝或按原樣接受。現(xiàn)在的問(wèn)題是如何判斷一個(gè)節(jié)點(diǎn)所測(cè)試的屬性是否是不相關(guān)的屬性。假設(shè)我們目前所考慮的節(jié)點(diǎn)由p個(gè)正樣例和n個(gè)負(fù)樣例組成。如果該節(jié)點(diǎn)測(cè)試的屬性是不相關(guān)的，那么在我們的預(yù)期中，該測(cè)試會(huì)將樣例分割成多個(gè)子集，使得每個(gè)子集的正樣例的比例與整個(gè)集合的比例p/(p n)大致相同，因此信息增益將接近于0。[3]因而，低信息增益是判斷屬性是否不相關(guān)的一個(gè)很好的方法。現(xiàn)在的問(wèn)題是，我們需要多大的增益才能在特定屬性上進(jìn)行分割？這個(gè)增益將恒為正數(shù)，除了所有的比例都完全相同的情形（不太常見(jiàn)）。（19.NNGA。）我們可以用統(tǒng)計(jì)學(xué)中的顯著性檢驗(yàn)（significance test）來(lái)回答這問(wèn)題。該檢驗(yàn)首先假設(shè)不存在基礎(chǔ)的模式［所謂的零假設(shè)（nullhyphothesis）］，然后對(duì)實(shí)際數(shù)據(jù)進(jìn)行分析，并計(jì)算它們偏離零假設(shè)的程度。如果偏離程度在統(tǒng)計(jì)上不太可能發(fā)生（通常我們?nèi)?%或更低的概率作為閾值），那么這在一定程度上證明了數(shù)據(jù)中仍存在顯著的模式。其中概率將根據(jù)隨機(jī)抽樣中偏差量的標(biāo)準(zhǔn)分布計(jì)算得到。無(wú)限大的樣本集而言，信息增益將為0。我們需要計(jì)算的概率是在零假設(shè)下，一個(gè)大小為的樣本集所呈現(xiàn)的與正負(fù)樣例的期望分布的pk和nk與假設(shè)該屬性不相關(guān)情形下的期望數(shù)量和來(lái)衡量這一偏差：下式給出總偏差的一個(gè)簡(jiǎn)潔形式：在零假設(shè)下，將服從 個(gè)自由度的分布（卡方分布）。我可以使用統(tǒng)計(jì)量來(lái)判斷一個(gè)特定的值是接受還是拒絕了零假設(shè)。例如，餐廳的Type屬性有4個(gè)值，因此分布有3個(gè)自由度。在5%的置信水平下，總偏差 或更大的值將拒絕零假設(shè)（在1%的置信水平下，或更大的值將拒絕零假設(shè)）。低于閾值的偏差值會(huì)讓我們接受屬性不相關(guān)這一零假設(shè)，因此樹(shù)的相關(guān)分支應(yīng)該被剪枝。這個(gè)方法被稱為剪枝（pruning）。有了剪枝的技術(shù)，我們?cè)试S樣例中存在噪聲。樣例標(biāo)簽中的錯(cuò)誤（例如，一個(gè)樣例(xNo)被誤標(biāo)為(x,Yes)）會(huì)使預(yù)測(cè)誤差線性地增加，而樣例描述中的錯(cuò)誤（例如，樣例的實(shí)際屬性被誤標(biāo)記）對(duì)誤差具有漸近的影響，隨著樹(shù)收縮在更小的集合上運(yùn)作，這種影響會(huì)變得更糟。當(dāng)數(shù)據(jù)具有較大的噪聲時(shí)，經(jīng)過(guò)剪枝的樹(shù)的性能將明顯優(yōu)于未剪枝的樹(shù)。而且經(jīng)過(guò)剪枝的樹(shù)通常要小得多，因此更容易被理解，調(diào)用也更有效率。最后一個(gè)需要提醒的地方：我們可能會(huì)認(rèn)為剪枝和信息增益看起來(lái)很類似，那么為什么不使用一種被稱為提前停止（earlystopping）的方法將它們合并起來(lái)，即讓決策樹(shù)算法在沒(méi)有好的屬性來(lái)繼續(xù)進(jìn)行分割時(shí)停止生成節(jié)點(diǎn)，而不是平添麻煩地生成完所有不必要的節(jié)點(diǎn)，然后再將它們修剪掉呢？提前停止法的問(wèn)題在于，它在我們找不出任何一個(gè)好的屬性時(shí)即停止了程序，但有一些屬性需要相互組合才會(huì)含有信息并發(fā)揮效果。例如，考慮含有兩個(gè)二值屬性的XOR函數(shù)，如果輸入值的4種組合的樣例數(shù)大致相等，那么這兩個(gè)屬性都不具有顯著的信息，但正確的做法是先基于其中一個(gè)屬性（不論是哪一個(gè)）進(jìn)行分割，然后在下一個(gè)分割階段，我們將得到非常有信息量且效果很好的分割。提前停止法可能會(huì)錯(cuò)過(guò)這一點(diǎn)，但是“先生成后剪枝”的方式可以正確地處理這種情況。拓展決策樹(shù)的適用范圍通過(guò)處理以下復(fù)雜情況，決策樹(shù)可以得到更廣泛的應(yīng)用。缺失數(shù)據(jù)：知的。這些值可能沒(méi)有被記錄，也可能因獲得它們的代價(jià)太大而無(wú)法獲得。這就產(chǎn)生了兩個(gè)問(wèn)題：首先，給定一棵完整的決策樹(shù)，對(duì)于缺少一個(gè)測(cè)試屬性的樣例，應(yīng)該如何將它分類？其次，當(dāng)一些樣例的屬性值未知時(shí)，應(yīng)該如何修改信息增益公式？這些問(wèn)題留于習(xí)題19.MISS。連續(xù)屬性與多值輸入屬性：對(duì)于連續(xù)屬性（如身高、體重或時(shí)間），可能每個(gè)樣例都有不同的屬性值。用信息增益來(lái)衡量屬性將導(dǎo)致這樣的屬性得到理論上最高的信息增益，最終給出一棵以該屬性為根的淺層樹(shù)，其中每個(gè)可能值對(duì)應(yīng)一個(gè)單樣例子樹(shù)。但是當(dāng)我們需要對(duì)一個(gè)新的樣例進(jìn)行分類，且樣例的該屬性值并沒(méi)有被觀測(cè)過(guò)時(shí)，這棵樹(shù)對(duì)我們沒(méi)有幫助。處理連續(xù)值的一個(gè)更好的方法是采用分割點(diǎn)（splitpoint）測(cè)試——一個(gè)關(guān)于屬性值的不等式測(cè)試。例如，在樹(shù)中的一個(gè)給定節(jié)點(diǎn)上，體重160的測(cè)試可能會(huì)提供最多的信息。找到好的分割點(diǎn)的有效方法是：對(duì)于不連續(xù)的或者排序沒(méi)有意義的，但有大量可能值的屬性（例如郵政編碼或者信用卡號(hào)碼），可以使用一種稱為信息增益比（informationgainratio）（見(jiàn)習(xí)題19.GAIN）的度量方法來(lái)避免算法將樹(shù)分割成許多單樣例子樹(shù)。另一個(gè)有效的方法是采用形如A=vk的等式進(jìn)行測(cè)試。例如，測(cè)試郵政編碼=10002，可以在紐約市挑選出這個(gè)郵政編碼下的一大群人，然后將其他所有人歸并到“其他”子樹(shù)中。連續(xù)值輸出屬性：如果要預(yù)測(cè)一個(gè)數(shù)值類型的輸出，那么我們需要的是一棵回歸樹(shù)（regressiontree），而不是一棵分類樹(shù)。回歸樹(shù)在每個(gè)葉節(jié)點(diǎn)上都有一個(gè)關(guān)于數(shù)值屬性子集的線性函數(shù)，而不是一個(gè)單一的輸出值。舉個(gè)例子來(lái)說(shuō)，兩居室公寓的價(jià)格最終可能以一個(gè)關(guān)于占地面積和浴室數(shù)量的線性函數(shù)輸出。學(xué)習(xí)算法必須能夠決定何時(shí)停止對(duì)樹(shù)進(jìn)行分割并開(kāi)始對(duì)屬性應(yīng)用線性回歸（見(jiàn)19.6節(jié)）。CART這個(gè)名字代表分類與回歸樹(shù)（ClassificationAndRegressionTree），用于涵蓋這兩個(gè)類別的樹(shù)。一個(gè)面向?qū)嶋H應(yīng)用的決策樹(shù)學(xué)習(xí)系統(tǒng)必須能夠處理所有這些問(wèn)題。處理連續(xù)值變量尤其重要，因?yàn)槲锢磉^(guò)程和金融過(guò)程所提供的都是數(shù)值數(shù)據(jù)。現(xiàn)實(shí)應(yīng)用中已經(jīng)出現(xiàn)了一些符合這些標(biāo)準(zhǔn)的商業(yè)軟件包，并已用于開(kāi)發(fā)數(shù)千個(gè)部署系統(tǒng)。在工業(yè)和商業(yè)的許多領(lǐng)域中，決策樹(shù)仍是從數(shù)據(jù)集中尋找分類方法的首要方法。決策樹(shù)有很多優(yōu)點(diǎn)：易于理解，可推廣到大型數(shù)據(jù)集，處理離散輸入和連續(xù)輸入及分類和回歸問(wèn)題的多功能性。然而，它們的精確度可能是次優(yōu)的（主要是由貪心搜索導(dǎo)致），并且如果樹(shù)很深，那么在調(diào)用樹(shù)為一個(gè)新的樣例進(jìn)行預(yù)測(cè)時(shí)可能會(huì)有昂貴的運(yùn)行代價(jià)。決策樹(shù)也是不穩(wěn)定的（unstable），因?yàn)閮H添加一個(gè)新的樣例，就可能更改根上的測(cè)試結(jié)果，從而更改整個(gè)樹(shù)。在19.8.2節(jié)中，我們將看到隨機(jī)森林模型（randomforestmodel）可以解決這些問(wèn)題中的一部分。模型選擇與模型優(yōu)化在機(jī)器學(xué)習(xí)中，我們的目標(biāo)是選擇一個(gè)和未來(lái)的樣例最佳擬合的假設(shè)。要做到這一點(diǎn)，我們需要定義“未來(lái)的樣例”和“最佳擬合”。首先，我們假設(shè)未來(lái)的樣例類似于過(guò)去觀測(cè)過(guò)的樣本。我們稱之為平穩(wěn)性（stationary）假設(shè)；若沒(méi)有它，所有的方法都沒(méi)有意義。我們假設(shè)每個(gè)樣例Ej都具有相同的先驗(yàn)概率分布：而且它與之前的樣例是獨(dú)立的：對(duì)于滿足這些等式的樣例，我們稱它們?yōu)楠?dú)立同分布的或i.i.d.。下一步是定義“最佳擬合”。我們說(shuō)最佳擬合是最小化錯(cuò)誤率（errorrate）——對(duì)于樣例(x,y)，的比例——的假設(shè)。（稍后我們將對(duì)此內(nèi)容進(jìn)行推廣，以允許不同的誤差具有不同的代價(jià)，實(shí)際上傾向于信任“幾乎”正確的答案。）我們可以通過(guò)對(duì)一個(gè)假設(shè)進(jìn)行測(cè)試來(lái)估計(jì)其錯(cuò)誤率：在一組稱為測(cè)試集的樣例上評(píng)估它的表現(xiàn)。一個(gè)假設(shè)（或一個(gè)學(xué)生）在測(cè)試前偷看答案屬于作弊行為。為確保這種情況不會(huì)發(fā)生，最簡(jiǎn)單的方法是將我們擁有的樣例分割成兩組：一組為用于訓(xùn)練從而得到假設(shè)的訓(xùn)練集，另一組為用于評(píng)估假設(shè)的測(cè)試集。最終會(huì)得到多個(gè)假設(shè)：我們可能想要比較兩個(gè)完全不同的機(jī)器學(xué)習(xí)模型，或者我們可能想要在同一個(gè)模型中調(diào)整不同的“旋鈕”。例如，在的多項(xiàng)式。我們稱這些“旋鈕”為超參數(shù)（hyperparameter），它們是對(duì)模型類而言的，而不是對(duì)單個(gè)模型。假設(shè)一個(gè)研究者在一組剪枝的超參數(shù)中訓(xùn)練出一個(gè)假設(shè)，并在測(cè)獨(dú)的假設(shè)“偷看”或使用了測(cè)試集的數(shù)據(jù)，但整個(gè)過(guò)程通過(guò)研究者還是泄露了測(cè)試集的信息。避免這種依賴性的方法是將測(cè)試集完全鎖定——直到你完全完成了訓(xùn)練、實(shí)驗(yàn)、超參數(shù)調(diào)整、再訓(xùn)練這一系列過(guò)程。這意味著你需要3個(gè)數(shù)據(jù)集。訓(xùn)練集用于訓(xùn)練備選模型。驗(yàn)證集（validationset）也被稱為開(kāi)發(fā)集（developmentset或devset），用于評(píng)估備選模型并選擇最佳的備選模型。測(cè)試集用于無(wú)偏地估計(jì)最佳模型。如果我們沒(méi)有足夠的數(shù)據(jù)來(lái)構(gòu)成這3個(gè)數(shù)據(jù)集怎么辦？我們可以使用一種稱為k折交叉驗(yàn)證（k-fold 的方法從數(shù)據(jù)中獲得更多子數(shù)據(jù)集。其思想是，每個(gè)樣例都被作為訓(xùn)練數(shù)據(jù)和驗(yàn)證數(shù)據(jù)，從而提供雙重功能，但又不同時(shí)提供。首先，我們將數(shù)據(jù)分割成k個(gè)相等大小的子集，然后進(jìn)行k輪學(xué)習(xí)；在每一輪中，1/k的數(shù)據(jù)被作為驗(yàn)證集，其余的樣例被用于訓(xùn)練。k輪的平均測(cè)試分?jǐn)?shù)相比單個(gè)分?jǐn)?shù)應(yīng)該是一個(gè)更準(zhǔn)確的估計(jì)。常用k值為5或10——足以給出一個(gè)在統(tǒng)計(jì)上較為準(zhǔn)確的估計(jì)值，其代價(jià)是5到10倍的計(jì)算量。最極端的情形是k=n，該情形也被稱為留一交叉驗(yàn)證（leave-one-out 。即使采用了交叉驗(yàn)證的方法，我們?nèi)匀恍枰粋€(gè)單獨(dú)的測(cè)試集。在圖19-1（見(jiàn)19.2節(jié)）中，我們注意到，一個(gè)線性的函數(shù)對(duì)數(shù)據(jù)集是欠擬合的，而高次多項(xiàng)式對(duì)數(shù)據(jù)是過(guò)擬合的。我們可以把找到一個(gè)好的假設(shè)這一目標(biāo)分作兩個(gè)子任務(wù)：模型選擇（model 選擇一個(gè)好的假設(shè)空間；模型優(yōu)化（model 也稱為訓(xùn)練），即在這個(gè)空間中找到最佳假設(shè)。盡管“模型選擇”這一名稱已經(jīng)被廣泛運(yùn)用，但更好的名稱應(yīng)該是“模型類選擇”或“假設(shè)空間”。“模型”一詞在文獻(xiàn)中通常有3種不同層次的含義：寬泛的假設(shè)空間（如“多項(xiàng)式”）、固定超參數(shù)的假設(shè)空間（如“二次多項(xiàng)式”）以及所有參數(shù)固定了的特定假設(shè)（5x2+3x–2）。模型選擇有一部分是定性的和主觀的：基于我們對(duì)問(wèn)題已有的一些了解與認(rèn)識(shí)，我們可能會(huì)選擇多項(xiàng)式函數(shù)而不選擇決策樹(shù)。模型選擇的另一部分是定量的和經(jīng)驗(yàn)性的：在多項(xiàng)式函數(shù)類中，我們可以選擇次數(shù)為2的多項(xiàng)式，因?yàn)檫@個(gè)值在驗(yàn)證數(shù)據(jù)集上表現(xiàn)最好。模型選擇圖19-8描述了一個(gè)簡(jiǎn)單的模型選擇算法。它以一個(gè)學(xué)習(xí)器Learner（例如，它可以是決策樹(shù)學(xué)習(xí)器LEARN-DECISION-TREE）為參數(shù)。Learner選取一個(gè)在圖中名為size的超參數(shù)，對(duì)于決策樹(shù)而言，它可以是樹(shù)中的節(jié)點(diǎn)數(shù)；對(duì)于多項(xiàng)式，它可以是函數(shù)的次數(shù)。模型選擇從的最小值開(kāi)始，得到一個(gè)簡(jiǎn)單的模型（這可能會(huì)導(dǎo)致數(shù)據(jù)欠擬合），之后采用較大的size值，并考慮更復(fù)雜的模型。最后，模型選擇算法將選擇在驗(yàn)證數(shù)據(jù)上平均錯(cuò)誤率最低的模型。圖19-8 選擇驗(yàn)證誤差最小的模型的算法。隨著復(fù)雜性不斷增加，算法建立了多個(gè)模型，并在驗(yàn)證數(shù)據(jù)集上選擇經(jīng)驗(yàn)錯(cuò)誤率err最小的模型。Learner(size,examples)返回一個(gè)假設(shè)，其復(fù)雜性設(shè)置，并根據(jù)樣例集examples進(jìn)行訓(xùn)練。在交叉驗(yàn)證CROSS-VALIDATION中，for循環(huán)的每次迭代都會(huì)選擇一個(gè)不同部分的examples作為驗(yàn)證集，并保留其他樣例作為訓(xùn)練集。然后它返回我們確定了size參數(shù)哪個(gè)值是最佳的，MODEL-SELECTION將返回該參數(shù)下的在所有的訓(xùn)練樣例上訓(xùn)練過(guò)的模型（如學(xué)習(xí)器/假設(shè)），率在圖19-9中，我們看到了在模型選擇中可能發(fā)生的兩種典型的模式。在圖19-9a和圖19-9b中，隨著模型復(fù)雜性的增加，訓(xùn)練集誤差單調(diào)減小（伴隨著輕微的隨機(jī)波動(dòng)）。復(fù)雜性分別由圖19-9a中的決策樹(shù)節(jié)點(diǎn)數(shù)量和圖19-9b中的神經(jīng)網(wǎng)絡(luò)參數(shù)（wi）數(shù)量衡量。對(duì)許多模型類來(lái)說(shuō)，隨著復(fù)雜性的增加，訓(xùn)練集誤差將逐漸達(dá)到0。圖19-9 兩個(gè)不同問(wèn)題上不同復(fù)雜性模型的訓(xùn)練誤差（下方綠線）和驗(yàn)證誤差（上方橙色。模型選擇算法MODEL-SELECTION將選擇驗(yàn)證誤差最小的模型對(duì)應(yīng)的超參數(shù)值。（a）模型類是決策樹(shù)，超參數(shù)是節(jié)點(diǎn)數(shù)量。數(shù)據(jù)來(lái)自餐廳等待問(wèn)題。最佳的超參數(shù)大小為7。（b）模型類是卷積神經(jīng)網(wǎng)絡(luò)（見(jiàn)21.3節(jié)），超參數(shù)是網(wǎng)絡(luò)中常規(guī)參數(shù)的數(shù)量。數(shù)據(jù)是數(shù)字圖像的MNIST數(shù)據(jù)集，任務(wù)是識(shí)別手寫(xiě)數(shù)字的照片。效果最好的超參數(shù)是1000000（注意坐標(biāo)的對(duì)數(shù)刻度）關(guān)于在驗(yàn)證集誤差上的表現(xiàn)，這兩種情況有著顯著的差異。在圖19-9a中，我們看到了一個(gè)U形的驗(yàn)證集誤差曲線：隨著模型復(fù)雜性的增加，誤差在一段時(shí)間內(nèi)會(huì)先降低，但是當(dāng)它到達(dá)一個(gè)臨界點(diǎn)時(shí)，模型開(kāi)始過(guò)擬合，驗(yàn)證誤差逐漸增加。MODEL-SELECTION將選擇U形驗(yàn)證誤差曲線中驗(yàn)證誤差最低的值：在本例中是一個(gè)節(jié)點(diǎn)個(gè)數(shù)為7的樹(shù)。這是最能平衡欠擬合和過(guò)擬合的位置。在圖19-9b中，一開(kāi)始我們觀察到了與圖19-9a中類似的U形曲線，但隨后驗(yàn)證誤差又開(kāi)始減小；驗(yàn)證誤差最低的點(diǎn)是實(shí)驗(yàn)結(jié)果中的最后一點(diǎn)，參數(shù)個(gè)數(shù)為1000000。為什么有些驗(yàn)證誤差曲線形如圖19-9a所示而另一些形如圖19-9b所示呢？根本問(wèn)題在于不同的模型類如何利用其過(guò)強(qiáng)的表達(dá)能力，以及它通常會(huì)達(dá)到這樣的程度：所有的訓(xùn)練樣例都可以在模型中被完美地表達(dá)。例如，給定一個(gè)包含n個(gè)不同樣例的訓(xùn)練集，總有一個(gè)具有n節(jié)點(diǎn)的決策樹(shù)可以表達(dá)所有的樣例。我們稱一個(gè)完全擬合了所有訓(xùn)練數(shù)據(jù)的模型為對(duì)數(shù)據(jù)進(jìn)行了插值（interpolated）。[5]當(dāng)模型的表達(dá)能力接近于插值臨界點(diǎn)時(shí)，模型類已經(jīng)開(kāi)始過(guò)擬合。這似乎是因?yàn)槟Ｐ偷拇蟛糠直磉_(dá)能力都集中在訓(xùn)練樣例上，而剩余的表達(dá)能力以不代表驗(yàn)證數(shù)據(jù)集中的模式的方式隨機(jī)分布。有些模型類永遠(yuǎn)不會(huì)從這種過(guò)擬合的表現(xiàn)中自主地恢復(fù)過(guò)來(lái)，例如圖19-9a中的決策樹(shù)。但是對(duì)于其他模型類，增加模型類的表達(dá)能力意味著有更多的候選函數(shù)，其中一些函數(shù)自然非常適合真實(shí)函數(shù)f(x)中的數(shù)據(jù)模式。表達(dá)能力越強(qiáng)，合適的表示函數(shù)就越多，優(yōu)化方法就越有可能將結(jié)果落在其中一個(gè)之上。一些作者也把這個(gè)現(xiàn)象稱為模型“記住”了數(shù)據(jù)。深度神經(jīng)網(wǎng)絡(luò)（第21章）、核機(jī)器（19.7.5節(jié)）、隨機(jī)森林（19.8.2節(jié)）和增強(qiáng)集成（19.8.4節(jié)）都具有驗(yàn)證誤差隨模型類表達(dá)能力增加而減小的特點(diǎn)，如圖19-9b所示。我們可以用以下不同方式來(lái)擴(kuò)展模型選擇算法：比較不同的模型類，通過(guò)讓模型選擇函數(shù)MODEL-SELECTION使用決策樹(shù)學(xué)習(xí)器DECISION-TREE-LEARNER和多項(xiàng)式學(xué)習(xí)器POLYNOMIAL-LEARNER進(jìn)行比較，觀察哪個(gè)表現(xiàn)更好來(lái)實(shí)現(xiàn)。我們可以允許多個(gè)超參數(shù)的存在，這意味著需要有更復(fù)雜的優(yōu)化算法以確定超參數(shù)，如網(wǎng)格搜索（見(jiàn)19.9.3節(jié)），而不是線性搜索。從錯(cuò)誤率到損失函數(shù)到目前為止，我們一直在試圖降低錯(cuò)誤率。這顯然比最大化錯(cuò)誤率要好，但這樣是不夠的。例如，將電子郵件分類為垃圾郵件或非垃圾郵件的問(wèn)題。把非垃圾郵件歸類為垃圾郵件（這可能導(dǎo)致漏掉一封重要的郵件）比把垃圾郵件歸類為非垃圾郵件（導(dǎo)致自己遭受幾秒鐘的騷擾）糟糕得多。因此，如果一個(gè)分類器所犯的大多數(shù)錯(cuò)誤都是將垃圾郵件分類為非垃圾郵件，那么錯(cuò)誤率為1%的該分類器將比錯(cuò)誤率僅為0.5%但所犯的錯(cuò)誤都是把非垃圾郵件分類為垃圾郵件的分類器要好。我們?cè)诘?6章中看到，決策者應(yīng)該最大化預(yù)期效用，那么學(xué)習(xí)器也應(yīng)該最大化效用。然而，在機(jī)器學(xué)習(xí)中，傳統(tǒng)的做法是將其表述為負(fù)面效用：最小化損失函數(shù)（lossfunction）而不是最大化效用函數(shù)。損失函數(shù)定義為當(dāng)正確的答案為f(x)=y時(shí)，模型預(yù)測(cè)出的效用損失量：這是損失函數(shù)最一般的形式。我們通常使用的是更簡(jiǎn)單的形式，它獨(dú)立于x。在本文的剩余部分中，我們將使用簡(jiǎn)化版本的損失函數(shù)，這意味著我們不能認(rèn)為，將媽媽的來(lái)信錯(cuò)誤分類比將討厭的堂兄的來(lái)信錯(cuò)誤分類更糟糕，但我們可以說(shuō)，將非垃圾郵件歸類為垃圾郵件要比將垃圾郵件歸類為非垃圾郵件糟糕10倍：注意，L(y,y)始終為0；即根據(jù)定義，當(dāng)你正確猜測(cè)時(shí)，我們認(rèn)為沒(méi)有損失。對(duì)于具有離散輸出值的函數(shù)，我們可以為每個(gè)可能的誤分類狀況枚舉出一個(gè)損失值，但輸出值為實(shí)數(shù)時(shí)我們不能列舉出所有可能性。當(dāng)f(x)函數(shù)值為137.035999時(shí)，我們對(duì)預(yù)測(cè)值h(x)=137.036相當(dāng)滿意，但是如何衡量我們對(duì)此的滿意程度呢？一般來(lái)說(shuō)，小的誤差總是比大的誤差好；可以實(shí)現(xiàn)這種想法的兩個(gè)函數(shù)為兩者差的絕對(duì)值（稱為L(zhǎng)1損失）和兩者差的平方（稱為L(zhǎng)2損失；將“2”理解為平方的意思）。對(duì)于離散值輸出，如果我們希望達(dá)到最小化錯(cuò)誤率，那么可以使用L0/1損失函數(shù)，即對(duì)錯(cuò)誤答案損失為1、對(duì)正確答案損失為0的損失函數(shù)：從理論上來(lái)說(shuō)，學(xué)習(xí)智能體通過(guò)選擇最小化目前觀測(cè)到的所有輸入-輸出對(duì)的預(yù)期損失的假設(shè)，來(lái)使其期望效用最大化。為了計(jì)算該期望，我們需要定義樣例的先驗(yàn)概率分布。令為所有可能的輸入輸出樣例的集合。那么假設(shè)h（關(guān)于損失函數(shù)L）的期望泛化損失（generalizationloss）為而最佳假設(shè)h*是使得期望泛化損失最小的假設(shè)：由于在大多數(shù)情況下，先驗(yàn)分布P(x,y)是未知的，學(xué)習(xí)智能體只能在一組大小為N的樣例E上用經(jīng)驗(yàn)損失（empiricalloss）來(lái)估計(jì)泛化損失：估計(jì)最佳假設(shè)即為使得經(jīng)驗(yàn)損失最小的假設(shè)：得到的假設(shè)與真實(shí)函數(shù)f不同，有4種可能的原因：不可實(shí)現(xiàn)性方差、噪聲和計(jì)算復(fù)雜性。第一，如果假設(shè)空間H實(shí)際上包含真實(shí)函數(shù)f，那么稱該學(xué)習(xí)問(wèn)題是可實(shí)現(xiàn)的（realizable）。如果H是線性函數(shù)的集合，而真實(shí)函數(shù)f是一個(gè)二次函數(shù)，那么無(wú)論有多少數(shù)據(jù)可供使用，都無(wú)法找到真實(shí)函數(shù)f。第二，方差意味著我們所使用的學(xué)習(xí)算法通常會(huì)針對(duì)不同的樣例集合返回不同的假設(shè)。如果問(wèn)題是可實(shí)現(xiàn)的，那么方差會(huì)隨著訓(xùn)練樣例數(shù)量的增加而逐漸減小到0。第三，函數(shù)f可能是非確定性的或有噪聲的（noisy）——對(duì)于同一個(gè)輸入值x它可能返回不同的f(x)值。根據(jù)定義，噪聲是無(wú)法被預(yù)測(cè)的（它只能被描述）。第四，當(dāng)假設(shè)空間H是一個(gè)龐大假設(shè)空間中的復(fù)雜函數(shù)時(shí)，系統(tǒng)地搜索所有可能性將是難以計(jì)算的（computationallyintractable）；在這種情況下，搜索可以探索假設(shè)空間的一部分并返回一個(gè)相當(dāng)好的假設(shè)，但并不能總是保證它是最佳的假設(shè)。傳統(tǒng)的統(tǒng)計(jì)學(xué)方法和早期的機(jī)器學(xué)習(xí)主要注重小規(guī)模學(xué)習(xí)（small-scale learning），其中訓(xùn)練樣例的數(shù)量可能從幾十個(gè)到幾千個(gè)不等。時(shí)泛化損失主要來(lái)源于假設(shè)空間中不包含真實(shí)函數(shù)f而導(dǎo)致的近似誤差，以及因?yàn)闆](méi)有足夠訓(xùn)練樣例來(lái)限制方差而導(dǎo)致的估計(jì)誤差。近年來(lái)，人們?cè)絹?lái)越重視大規(guī)模學(xué)習(xí)（large-scalelearning），它們通常有上百萬(wàn)的訓(xùn)練樣例。在這樣的問(wèn)題中，泛化損失可能受到計(jì)算限制的約束，即如果有足夠的數(shù)據(jù)和足夠豐富的模型，我們可以找到一個(gè)非常接近真實(shí)函數(shù)f的假設(shè)h，但是找到它的計(jì)算是復(fù)雜的，所以我們需要采用近似的方法。正則化在19.4.1節(jié)中，我們了解了如何使用交叉驗(yàn)證進(jìn)行模型選擇。模型選擇的另一種方法是尋找一個(gè)假設(shè)，它直接最小化經(jīng)驗(yàn)損失與假設(shè)復(fù)雜性度量的加權(quán)和，我們稱之為總代價(jià)：其中是一個(gè)大于零的超參數(shù)，作為損失和假設(shè)復(fù)雜性度量之間轉(zhuǎn)換比率。如果選擇了一個(gè)較好的，它可以很好地平衡簡(jiǎn)單函數(shù)中能較大的經(jīng)驗(yàn)損失與復(fù)雜函數(shù)中過(guò)擬合的傾向。我們把這個(gè)過(guò)程稱為正則化（regularization），它顯式地懲罰復(fù)雜假設(shè)的復(fù)雜性：我們希望尋找更規(guī)則的函數(shù)。我們現(xiàn)在結(jié)合了兩種度量，即損失函數(shù)（L1或L2）和復(fù)雜性度量，我們稱后者為正則化函數(shù)（regularizationfunction）。正則化函數(shù)的選擇依賴于假設(shè)空間。例如，對(duì)多項(xiàng)式假設(shè)空間來(lái)說(shuō)，系數(shù)平方和是正則化函數(shù)的一個(gè)不錯(cuò)選擇——保持系數(shù)平方和較小將引導(dǎo)我們避開(kāi)圖19-1中劇烈波動(dòng)的12次多項(xiàng)式。我們將在19.6.3節(jié)中給出一個(gè)這種正則化的例子。另一種簡(jiǎn)化模型的方法是減少模型的維數(shù)。例如可以使用一個(gè)稱為特征選擇（featureselection）的過(guò)程來(lái)判斷屬性的相關(guān)性，然后丟棄不相關(guān)的屬性。剪枝就是一種特征選擇的方式。在沒(méi)有轉(zhuǎn)換因子的情況下，經(jīng)驗(yàn)損失和復(fù)雜性將在同一尺度下進(jìn)行度量，實(shí)際上這可能是可行的：它們都可以用計(jì)算機(jī)位來(lái)度量。首先我們將假設(shè)編碼為圖靈機(jī)程序，并計(jì)算其位數(shù)。然后計(jì)算對(duì)數(shù)據(jù)進(jìn)行編碼所需的位數(shù)，其中正確預(yù)測(cè)的樣例的代價(jià)為零位，而錯(cuò)誤預(yù)測(cè)的樣例的代價(jià)取決于預(yù)測(cè)錯(cuò)誤的嚴(yán)重程度。最小描述長(zhǎng)度（minimundescription length，MDL）的假設(shè)為使所需的總位數(shù)最小化的假設(shè)。個(gè)方法在一定情境下可以很好地工作，但是對(duì)于規(guī)模較小的問(wèn)題，程序編碼的選擇——如何最好地將決策樹(shù)編碼為位字符串——將會(huì)影響結(jié)果。在第20章中，我們將為MDL方法提供一個(gè)概率層面的解釋。超參數(shù)調(diào)整在19.4.1節(jié)中，我們描述了如何選擇最佳的超參數(shù)值——通過(guò)對(duì)每數(shù)，且它的可能值不多時(shí)，這是一個(gè)很好的方法。但當(dāng)存在多個(gè)超參數(shù)，或當(dāng)它們具有連續(xù)值時(shí)，選擇好的超參數(shù)值就較為困難。最簡(jiǎn)單的超參數(shù)調(diào)整方法是手動(dòng)調(diào)參（hand-tuning）：根據(jù)個(gè)人以往的經(jīng)驗(yàn)來(lái)猜測(cè)參數(shù)，在該參數(shù)下訓(xùn)練模型，并在驗(yàn)證集上測(cè)試其表現(xiàn)并分析結(jié)果，根據(jù)直覺(jué)得到參數(shù)調(diào)整的結(jié)果。之后重復(fù)此操作，直到獲得滿意的模型表現(xiàn)為止（運(yùn)氣不好的話，你可能會(huì)耗光時(shí)間、計(jì)算預(yù)算或耐心）。如果只有幾個(gè)超參數(shù)，且每個(gè)超參數(shù)都有比較少的可能值，那么一種稱為網(wǎng)格搜索（gridsearch）的更系統(tǒng)化的方法將是適用的：嘗試所有超參數(shù)值的組合，觀察哪個(gè)組合在驗(yàn)證集上表現(xiàn)得最好。不同的組合可以在不同的機(jī)器上并行運(yùn)行，所以如果你有足夠的計(jì)算資源，這種嘗試過(guò)程將不會(huì)太緩慢，盡管在某些情況下，模型選擇一次超參數(shù)并運(yùn)行會(huì)占用很大的計(jì)算資源。我們?cè)诘?章和第4章中提到的搜索策略也可以在此發(fā)揮作用。例如，如果兩個(gè)超參數(shù)彼此獨(dú)立，則可以分別對(duì)它們進(jìn)行優(yōu)化。如果參數(shù)可能值的組合太多，那么考慮從所有可能的超參數(shù)可能值組合的集合中隨機(jī)搜索（randomsearch）采樣，并重復(fù)進(jìn)行足夠多次，只要你愿意花費(fèi)時(shí)間和計(jì)算資源就能找到足夠好的參數(shù)組合。此外，隨機(jī)搜索也適用于處理連續(xù)值的超參數(shù)選擇。在每次訓(xùn)練需要花費(fèi)很長(zhǎng)時(shí)間的情況下，從每次訓(xùn)練中獲取有用的信息將會(huì)對(duì)我們優(yōu)化超參數(shù)有所幫助。貝葉斯優(yōu)化（Bayesianoptimization）也就是說(shuō)把超參數(shù)值x向量作為輸入，把用這些超參數(shù)所建立與訓(xùn)練的模型在驗(yàn)證集上的總損失作為輸出y；之后試圖找到函數(shù)，來(lái)使損失y最小化。每次使用一組超參數(shù)進(jìn)行訓(xùn)練時(shí)，都會(huì)得到一個(gè)新的對(duì)，我們可以用它來(lái)更新對(duì)函數(shù)f的形式的猜測(cè)。超參數(shù)選擇的核心思想是在探索（嘗試新的超參數(shù)值）與利用（選擇與先前得到的結(jié)果較好的超參數(shù)值接近的超參數(shù)值）之間進(jìn)行權(quán)衡。這與我們?cè)诿商乜_樹(shù)搜索（5.4節(jié)）中看到的權(quán)衡類似，實(shí)際上，這里也使用了上置信界的概念來(lái)最大限度地減少遺憾。如果我們假設(shè)函數(shù)f可以用一個(gè)高斯過(guò)程（Gaussian process）來(lái)近似，那么在數(shù)學(xué)上函數(shù)f的更新將表現(xiàn)得非常好。斯努克等人（Snoeketal.,2013）從數(shù)學(xué)對(duì)該方法做出了解釋，并為該方法提供了實(shí)際應(yīng)用層面的指導(dǎo)，結(jié)果表明，該方法的效果勝過(guò)手動(dòng)調(diào)整的超參數(shù)（即便是調(diào)參專家所調(diào)出來(lái)的超參數(shù)）。一種可以代替貝葉斯優(yōu)化的方法是基于群體的訓(xùn)練（population-based 。PBT首先使用隨機(jī)搜索（并行地）訓(xùn)練大量模型，其中每個(gè)模型具有不同的超參數(shù)值。接著訓(xùn)練第二代模型，可以基于上一代中較好的參數(shù)值，通過(guò)對(duì)其使用遺傳算法（4.1.4節(jié)）中的隨機(jī)突變來(lái)選擇新的超參數(shù)值。因此，基于群體的訓(xùn)練既有隨機(jī)搜索的優(yōu)點(diǎn)，即可以并行地執(zhí)行許多次訓(xùn)練，又具有貝葉斯優(yōu)化（或由專業(yè)人士進(jìn)行手動(dòng)調(diào)參）的優(yōu)點(diǎn)，即我們可以從過(guò)去的訓(xùn)練結(jié)果中獲取信息并提供給之后的超參數(shù)選取。學(xué)習(xí)理論我們?nèi)绾未_定我們所學(xué)的假設(shè)能夠很好地預(yù)測(cè)還未被觀測(cè)過(guò)的輸入？也就是說(shuō)，如果我們不知道目標(biāo)函數(shù)f是什么樣子的，該如何確定假設(shè)h是否接近目標(biāo)函數(shù)f？這個(gè)問(wèn)題已經(jīng)存在了好幾個(gè)世紀(jì)，奧卡姆、假設(shè)空間非常復(fù)雜，我們是否可以找到最佳的假設(shè)h，還是只能找到局部最佳的假設(shè)？h應(yīng)該有多大的復(fù)雜性？如何避免過(guò)擬合？我們將在本節(jié)中探討這些問(wèn)題。我們從學(xué)習(xí)需要多少樣例這一問(wèn)題入手。從決策樹(shù)學(xué)習(xí)在餐廳等待問(wèn)題上的學(xué)習(xí)曲線（圖19-7）中可以看出，使用更多訓(xùn)練數(shù)據(jù)有利于提高準(zhǔn)確性。學(xué)習(xí)曲線是有一定效果的，但它僅限于特定問(wèn)題的特定學(xué)習(xí)算法。那么是否有一些更通用的法則來(lái)衡量所需的樣例數(shù)量？諸如此類的問(wèn)題我們統(tǒng)稱為計(jì)算學(xué)習(xí)理論（computational theory），它是人工智能、統(tǒng)計(jì)學(xué)和計(jì)算機(jī)理論等學(xué)科交匯的理論。解決這個(gè)問(wèn)題的基本原理是，在用少量的樣例進(jìn)行訓(xùn)練之后，那些非常不匹配的假設(shè)將有很高的概率被“排除”，因?yàn)樗鼈儗⒆龀鲥e(cuò)誤的預(yù)測(cè)。因此，如果一個(gè)假設(shè)與足夠多的訓(xùn)練樣例相一致，那么它不太可能是嚴(yán)重不匹配的，也就是說(shuō)，它必須是概率近似正確的（probablyapproximatelycorrect，PAC）。任何返回概率近似正確的假設(shè)的學(xué)習(xí)算法都稱為PAC學(xué)習(xí)（PAClearning）算法。我們可以使用這種方法為各種學(xué)習(xí)算法提供性能限界。與所有其他理論一樣，PAC學(xué)習(xí)理論也是公理的邏輯結(jié)果。當(dāng)一個(gè)定理（而不是一個(gè)政客）提供“基礎(chǔ)”以支撐這種聯(lián)系。對(duì)PAC學(xué)習(xí)而言，該“基礎(chǔ)”是由19.4節(jié)中樣例相同的固定分布中得出。（注意，我們可能不知道分布具體是什么樣的，我們只知道它不會(huì)改變。）此外，出于方便考慮，我們將假定真實(shí)函數(shù)f是確定性的，并且是正在考慮的假設(shè)空間H一個(gè)成員。最簡(jiǎn)單的PAC定理是有關(guān)布爾函數(shù)的，對(duì)布爾函數(shù)來(lái)說(shuō)，0/1損失是較合適的損失函數(shù)。在前面的內(nèi)容中我們非正式地給出了假設(shè)h的錯(cuò)誤率的定義，在此給出正式的定義，即從平穩(wěn)分布中得出的樣例的泛化誤差的期望：換句話說(shuō)，error(h)是假設(shè)h對(duì)新樣例進(jìn)行分類產(chǎn)生錯(cuò)誤結(jié)果的概率。該錯(cuò)誤率即為學(xué)習(xí)曲線實(shí)驗(yàn)中所測(cè)量的量。如果一個(gè)假設(shè)滿足，那么我們稱該假設(shè)h是近似正確（approximatelycorrect）球（-ball）內(nèi)。我們將該球外部的假設(shè)空間記為Hbad。對(duì)于一個(gè)“嚴(yán)重錯(cuò)誤”的假設(shè)，我們可以給出它與前N個(gè)樣例都一致的概率的界限。首先，有。因此，它與某個(gè)給定樣一致的概率最多為 。又由于樣例是獨(dú)立的，因此與N個(gè)樣例一致的概率上界為：則“在Hbad中至少含有一個(gè)與該N個(gè)樣例一致的假設(shè)”的概率將有上界，上界為各個(gè)假設(shè)與樣例保持一致的概率的和：其中Hbad為假設(shè)空間H的一個(gè)子集，因此有 。我們希能使這個(gè)事件發(fā)生的概率小于某個(gè)較小的正數(shù)：由于，通過(guò)較大的樣例數(shù)（19-1）后，以至少的概率，返回一個(gè)錯(cuò)誤率至多為的假設(shè)。換言之，它是概率近似正確的。所需的樣例數(shù)量是關(guān)于與的一個(gè)函數(shù)，被稱為學(xué)習(xí)算法的樣本復(fù)雜性（samplecomplexity）。如我們之前所述，如果H是n個(gè)屬性上所有布爾函數(shù)的集合，則。因此，假設(shè)空間的樣本復(fù)雜性增長(zhǎng)速度為2n。因?yàn)樗锌赡艿臉永龜?shù)也是2n，所以這表明在所有布爾函數(shù)類中的PAC學(xué)習(xí)需要觀測(cè)到幾乎所有可能的樣例。換個(gè)角度思考產(chǎn)生這樣結(jié)果的原因：H包含足夠多假設(shè)，它可以區(qū)分以任何方式給定的任何樣例集合。特別地，對(duì)于任何包含N個(gè)樣例的集合，與樣例一致的假設(shè)的集合仍包含數(shù)量相等的預(yù)測(cè)xN+1為正的假設(shè)和預(yù)測(cè)xN+1為負(fù)的假設(shè)。為了獲得對(duì)未觀測(cè)的樣例的真實(shí)泛化狀況，我們似乎需要以某種方式對(duì)假設(shè)空間進(jìn)行限制。但是，如果我們確實(shí)限制了假設(shè)空間H，則可能會(huì)完全排除真實(shí)的假設(shè)。有3種方法可以避免這種困境。第一種方法是利用先驗(yàn)知識(shí)來(lái)解決這個(gè)問(wèn)題。第二種方法是我們?cè)?9.4.3節(jié)中介紹的，它要求算法不只是返回任何一致性假設(shè)，而是優(yōu)先返回一個(gè)簡(jiǎn)單的假設(shè)（就像在決策樹(shù)學(xué)習(xí)中所做的那樣）。如果找到簡(jiǎn)單的一致性假設(shè)是比較容易的，那么其樣本復(fù)雜性結(jié)果通常比僅基于一致性分析所得到的假設(shè)要好一些。接下來(lái)我們要探討的第三種方法注重布爾函數(shù)整個(gè)假設(shè)空間的可學(xué)習(xí)子集。該方法依賴于以下假設(shè)：受限的假設(shè)空間包含與真實(shí)函數(shù)f足夠接近的假設(shè)h；其好處是受限的假設(shè)空間可以更有效地泛化，并且通常更易于搜索。接下來(lái)我們將更詳細(xì)地研究其中一種這樣的受限假設(shè)空間。PAC學(xué)習(xí)示例：學(xué)習(xí)決策列表現(xiàn)在，我們將展示如何將PAC學(xué)習(xí)應(yīng)用于新的假設(shè)空間：決策列表（decisionlist）。決策列表包含一系列測(cè)試，每個(gè)測(cè)試都是一些文字的合取。如果一個(gè)測(cè)試應(yīng)用于一個(gè)樣例描述的結(jié)果是相符的，則決策列表將指定要返回的值。如果測(cè)試不相符，則將繼續(xù)處理列表中的下一個(gè)測(cè)試。決策列表類似于決策樹(shù)，但它的整體結(jié)構(gòu)更簡(jiǎn)單：僅在一個(gè)方向上存在分支。相比之下，它的單個(gè)測(cè)試更為復(fù)雜。圖19-10給出了一個(gè)代表以下假設(shè)的決策列表：圖19-10 餐廳等待問(wèn)題的決策列表如果允許測(cè)試可以是任意大小的，那么決策列表將能表示任何布爾函數(shù)（習(xí)題19.DLEX）。另外，如果我們將每個(gè)測(cè)試的大小限制為最多k個(gè)文字，則學(xué)習(xí)算法將可能從少量樣例中成功泛化。我們采用符號(hào)來(lái)表示最多包含個(gè)合取的決策列表。圖1910中的樣例即為2。容易證明（習(xí)題19.），是的子集，是深度最多為的所有決策樹(shù)的集合。我們用n表示使用n個(gè)布爾屬性的。我們的第一個(gè)任務(wù)是證明是可學(xué)習(xí)的，也就是說(shuō)，中的任何函數(shù)在經(jīng)過(guò)合理數(shù)量的樣例訓(xùn)練后，都可以被準(zhǔn)確地近似。為證明這一點(diǎn)，我們需要計(jì)算所有可能假設(shè)的數(shù)量。我們將使用n個(gè)屬性且最多k個(gè)文字的合取式集合記為Conj(n, k)。由于決策列表是根據(jù)許多測(cè)試構(gòu)的，并且每個(gè)測(cè)試結(jié)果為Yes或No或不在決策列表中，所以最多存在個(gè)不同的用于組成決策列表的測(cè)試。又由于這些測(cè)試可以按任意順序進(jìn)行排列，因此：使用n個(gè)屬性且最多k個(gè)文字的合取式的數(shù)量由下式給出：因此，通過(guò)計(jì)算我們可以得到我們將其代入式（19-1）來(lái)獲得PAC學(xué)習(xí)中k-DL(n)函數(shù)所需的樣例數(shù)，它是關(guān)于n的多項(xiàng)式：因此，對(duì)于較小的k，任何返回一致決策列表的算法都將在合理數(shù)量的樣例中PAC學(xué)習(xí)k-DL函數(shù)。下一個(gè)任務(wù)是找到一種可返回一致決策列表的有效算法。我們使用一種稱為DECISION-LIST-LEARNING的貪心算法，該算法將反復(fù)查找與訓(xùn)練集的某些子集完全一致的測(cè)試。在找到這樣的測(cè)試后，便將其添加到正在構(gòu)建的決策列表中，并刪除相應(yīng)的樣例。然后僅使用剩余的樣例來(lái)構(gòu)造決策列表的剩余部分。之后重復(fù)此過(guò)程，直到?jīng)]有樣例剩余為止。該算法如圖19-11所示。該算法沒(méi)有給出選擇下一個(gè)要添加到?jīng)Q策列表的測(cè)試的方法。盡管之前給出的形式化的結(jié)果也不依賴于選擇方法，但優(yōu)先選擇小的測(cè)試并使它能與盡量多的統(tǒng)一分類樣例匹配是一個(gè)合理的選擇，這樣會(huì)使決策列表整體盡可能緊湊。最簡(jiǎn)單的策略是找到與任意一個(gè)統(tǒng)一分類的子集匹配的最小測(cè)試t，而不考慮子集的大小。結(jié)果如圖19-12所示，可以發(fā)現(xiàn)即便是這種簡(jiǎn)單的方法也能表現(xiàn)得很好。對(duì)于此問(wèn)題，決策樹(shù)的學(xué)習(xí)速度比決策列表要快一些，但對(duì)應(yīng)的波動(dòng)更大。兩種方法的準(zhǔn)確率在經(jīng)過(guò)100次試驗(yàn)后均超過(guò)90%。圖19-11 學(xué)習(xí)決策列表的算法圖19-12 算法用于餐廳等待問(wèn)題的學(xué)習(xí)曲線。LEARN-DECISION-TREE的曲線也在圖中給出，用于比較；決策樹(shù)在這個(gè)特定問(wèn)題上表現(xiàn)得稍好一些線性回歸與分類現(xiàn)在是時(shí)候?qū)⒆⒁饬难芯繘Q策樹(shù)和決策列表轉(zhuǎn)移到另一個(gè)已經(jīng)被使用了數(shù)百年的假設(shè)空間：關(guān)于連續(xù)值輸入的線性函數(shù)（linearfunction）。我們將從最簡(jiǎn)單的情況開(kāi)始討論：使用單變量線性函數(shù)進(jìn)行回歸，它也被稱為“直線擬合”。19.6.3節(jié)將介紹多變量的情形。19.6.4節(jié)和19.6.5節(jié)將介紹如何通過(guò)應(yīng)用硬閾值和軟閾值將線性函數(shù)轉(zhuǎn)換為分類器。單變量線性回歸擁有輸入x和輸出y的單變量線性函數(shù)（直線）的形式是，其中w0和w1為待學(xué)習(xí)的實(shí)值系數(shù)。之所以使用字母w，是因?yàn)槲覀儗⑾禂?shù)視為權(quán)重（weight）。y的值將隨著一項(xiàng)或多項(xiàng)的相對(duì)權(quán)重的改變改變。我們將w定義為向，并定義在此權(quán)重下的線性函數(shù)圖19-13a給出了xy平面上的一個(gè)含有n個(gè)樣例點(diǎn)的訓(xùn)練集，每個(gè)點(diǎn)代表房屋的占地面積和價(jià)格。我們要找到最匹配這些數(shù)據(jù)的線性函數(shù)hw，該任務(wù)被稱為線性回歸（linear regression）。要用數(shù)據(jù)擬合出一條直線，我們實(shí)際上需要做的就是找到對(duì)應(yīng)的權(quán)重值(w0, w1)，使得其經(jīng)損失最小。通常我們（回到高斯[6]）采用平方誤差損失函數(shù)L2，并對(duì)所有訓(xùn)練樣例進(jìn)行求和：高斯證明了，如果yj的觀測(cè)值帶有一個(gè)服從正態(tài)分布的噪聲，那么使用L2損失函數(shù)，并通小化誤差的平方和，我們將得到w1和w0的可能性最大的解。（如果輸出值帶有一個(gè)服從拉普拉斯分布的噪聲，那么L1損失函數(shù)將適用于這個(gè)情形。）我們希望找到特定的。當(dāng)求和達(dá)到最小時(shí)，它關(guān)于參數(shù)w0和w1的偏導(dǎo)數(shù)為0：（19-2）此時(shí)該問(wèn)題有唯一解：（19-3）對(duì)于圖19-13a中的樣例，對(duì)應(yīng)的解為、，擁有權(quán)重的直線已經(jīng)在圖中用虛線表示。許多形式的學(xué)習(xí)都涉及調(diào)整權(quán)重以最大限度地減小損失，因此對(duì)損失函數(shù)在權(quán)重空間（weight 由所有可能權(quán)重值構(gòu)成的空w0和w1定義的權(quán)重空間是一個(gè)二維空間，因此我們可以在三維圖中繪制損失函數(shù)與w0和w1的函數(shù)關(guān)系圖（見(jiàn)圖19-13b）。我們可以發(fā)現(xiàn)損失函數(shù)是凸的（如第4章所定義）；對(duì)于采用L2損失的每個(gè)線性回歸問(wèn)題，這個(gè)結(jié)果都是正確的，凸的性質(zhì)意味著損失函數(shù)沒(méi)有局部極小值。從某種意義上來(lái)說(shuō)，線性回歸模型到這里已經(jīng)完成了；即如果需要線性地?cái)M合數(shù)據(jù)，則直接應(yīng)用公式（19-3）即可。[7]需要注意的是：當(dāng)存在與x無(wú)關(guān)的服從正態(tài)分布的噪聲時(shí)，L2圖19-13 （a）2009年7月在加利福尼亞州伯克利出售的房屋的價(jià)格與建筑面積的數(shù)據(jù)點(diǎn)，以使得平方誤差損失最小的線性函數(shù)假設(shè)：。（b）損失函數(shù)關(guān)于不同的w0和w1值的三維圖。注意，損失函數(shù)是凸的，只存在一個(gè)全局最小值（注：1平方英尺=0.093平方米）梯度下降單變量線性回歸模型有一個(gè)很好的性質(zhì)，即利用最優(yōu)解處的偏導(dǎo)數(shù)為0，我們很容易找到模型的最優(yōu)解。但在其他模型中，情況并非總是如此，因此我們將在這里介紹另一種使損失函數(shù)最小化的方法，該方法不依賴于通過(guò)求解導(dǎo)數(shù)的零點(diǎn)來(lái)求解模型，并且可以應(yīng)用于任何損失函數(shù)，無(wú)論它有多復(fù)雜。如4.2節(jié)中所討論的，我們可以通過(guò)逐步修改參數(shù)來(lái)搜索連續(xù)的權(quán)重空間。在前面我們將此算法稱為爬山算法，但現(xiàn)在我們的目標(biāo)是將損失最小化，而不是將收益最大化，因此我們將使用梯度下降（gradientdescent）一詞。首先選擇權(quán)重空間中的任何一點(diǎn)作為起點(diǎn)——該問(wèn)題中選擇(w0, w1)平面上的一個(gè)點(diǎn)，然后計(jì)算梯度的估計(jì)值，并在最陡峭下坡方向移動(dòng)一小步，重復(fù)這一過(guò)程直到收斂到權(quán)重空間上某一點(diǎn)為止，它將在權(quán)重空間具有（局部）最小的損失。對(duì)應(yīng)的算法如下所示：w←whilenotdoforeachwiinwdo（19-4）其中參數(shù)，我們?cè)?.2節(jié)中稱之為步長(zhǎng)，當(dāng)我們?cè)噲D最小化學(xué)習(xí)問(wèn)題中的損失函數(shù)時(shí)，通常稱之為學(xué)習(xí)率（learningrate）。它可以是一個(gè)固定的常數(shù)，也可以隨著學(xué)習(xí)過(guò)程的進(jìn)行逐漸衰減。對(duì)于單變量回歸問(wèn)題，其損失函數(shù)是二次的，因此偏導(dǎo)數(shù)將是線性的。［你只需要知道運(yùn)算的鏈?zhǔn)椒▌t（chain ，再加上這一事實(shí)。］先，我們?cè)趦H有一個(gè)訓(xùn)練樣例(x,y)的簡(jiǎn)化情形下，推導(dǎo)出偏導(dǎo)數(shù)（率）（19-5）對(duì)于具體的w0和w1：將這兩個(gè)偏導(dǎo)數(shù)代入式（19-4），并將系數(shù)2歸入未定的學(xué)習(xí)率，我們得到權(quán)重的學(xué)習(xí)規(guī)則如下：這些更新規(guī)則具有直觀的意義：如果（即輸出太大），么需要稍微降低w0，如果x是正輸入則減小w1，若是負(fù)輸入則增加w1。前面的式子涵蓋了一個(gè)訓(xùn)練樣例的訓(xùn)練過(guò)程。對(duì)于N個(gè)訓(xùn)練樣例，我們希望最小化每個(gè)樣例各自損失的總和。由于和的導(dǎo)數(shù)即是導(dǎo)數(shù)的和，因此有這些更新法則構(gòu)成了用于單變量線性回歸的批梯度下降（batchgradient descent）學(xué)習(xí)法則（也稱確定性梯度下降）。其損失曲面是凸的，這意味著訓(xùn)練不會(huì)陷入局部極小值，到全局最小值的收斂性可以保證（只要我們不選擇一個(gè)過(guò)大的），但是有可能非常慢：在每一步更新中我們必須對(duì)所有N個(gè)訓(xùn)練樣例進(jìn)行求和，并且可能會(huì)進(jìn)行很多輪更新。如果N的大小超過(guò)處理器的內(nèi)存大小，那么問(wèn)題就更加復(fù)雜了。遍歷了所有訓(xùn)練樣例的一步更新，我們稱之為輪（epoch）。一種速度更快的變種是隨機(jī)梯度下降（stochasticgradientdescent，SGD）：它在每一步中隨機(jī)選擇少量訓(xùn)練樣例，并根據(jù)式（19-5）進(jìn)行更新。SGD的初始版本為在每一步中僅選擇一個(gè)訓(xùn)練樣例，但現(xiàn)在更常見(jiàn)的做法是從N個(gè)樣例中選擇一個(gè)大小為m的小批量。假設(shè)我們有N=000個(gè)樣例，并選擇批量大小為m=100算量減小到原來(lái)的1/100，但是由于估算的平均梯度的標(biāo)準(zhǔn)誤差與樣例數(shù)的平方根成比例，因此標(biāo)準(zhǔn)誤差僅增加10倍。因此，在本例中，雖然小批量SGD要花費(fèi)10倍以上的步驟才能達(dá)到相同的收斂程度，但它仍然比全批量SGD快10倍。根據(jù)CPU或GPU的結(jié)構(gòu)，我們可以選擇合適的m來(lái)利用并行向量運(yùn)算，使得包含m這些條件下，我們會(huì)將m視為針對(duì)各個(gè)學(xué)習(xí)問(wèn)題需要進(jìn)行調(diào)整的超參數(shù)。小批量SGD的收斂性是沒(méi)有嚴(yán)格保證的；因?yàn)樗鼤?huì)在最小值附近波動(dòng)，而不會(huì)穩(wěn)定下來(lái)。在19.6.4節(jié)中我們將看到，一個(gè)逐漸降低學(xué)習(xí)率的序列（如在模擬退火中所用）是如何確保算法收斂的。SGD在在線的情境中可能會(huì)有較大作用，在這種情況下，新數(shù)據(jù)的產(chǎn)生是逐次逐個(gè)的，并且平穩(wěn)性假設(shè)可能不成立。［實(shí)際上，SGD也稱為在線梯度下降（onlinegradientdescent）。］在選擇了一個(gè)較好的學(xué)習(xí)率后，模型就會(huì)逐漸優(yōu)化，并記住它過(guò)去學(xué)到的一些知識(shí)，還可以適應(yīng)蘊(yùn)含在新數(shù)據(jù)中的分布的變化。SGD已經(jīng)被廣泛地應(yīng)用于除線性回歸以外的模型，尤其是神經(jīng)網(wǎng)局最小值的性質(zhì)良好的局部極小值。多變量線性回歸我們可以輕松地將上述方法推廣到多變量線性回歸（multivariablelinear regression）問(wèn)題，在該問(wèn)題中每個(gè)樣例xj是一個(gè)n元向量。[8]我的假設(shè)空間是由形如下式的函數(shù)構(gòu)成的集合：有需要的讀者不妨參考附錄A“多變量回歸”來(lái)表示輸入是多個(gè)值的向量，但是輸出是單個(gè)變量。對(duì)于輸出也是多個(gè)變量的向量的情況，我們將使用術(shù)語(yǔ)“多元回歸”。但是，在其他著作中存在互換使用這兩個(gè)術(shù)語(yǔ)的現(xiàn)象。其中w0項(xiàng)（截距）與其他項(xiàng)截然不同。我們可以通過(guò)引入一個(gè)虛擬輸入屬性xj,0來(lái)解決這個(gè)問(wèn)題，該屬性始終等于1。那么h將用權(quán)重與輸入向量的點(diǎn)積（或等價(jià)的，權(quán)重轉(zhuǎn)置與輸入向量的矩陣內(nèi)積）來(lái)表示：最佳的權(quán)重向量w*為最小化樣例上的平方誤差損失：實(shí)際上，多變量線性回歸并不比我們剛剛介紹的單變量情況復(fù)雜很多。梯度下降將收斂到損失函數(shù)的（唯一）最小值。每個(gè)權(quán)重wi的更新式為（19-6）利用線性代數(shù)和向量的運(yùn)算，還可以解析地求解最小化損失函數(shù)的w。令y為訓(xùn)練樣例的輸出向量，X為數(shù)據(jù)矩陣（