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