2023人工智能機(jī)器學(xué)習(xí)算法

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