2023人工智能機器學習算法

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