第七章 類推學派:像什麽就是什麽
終極算法：機器學習和人工智能如何重塑世界 作者：佩德羅·多明戈斯 投票推薦 加入書簽 留言反饋
弗蘭克·阿巴內爾是曆史上最臭名昭著的騙子之一，萊昂納多·迪卡普裏奧曾在斯皮爾伯格的電影《逍遙法外》中飾演阿巴內爾。他偽造價值數百萬美元的支票，冒充律師和大學講師的身份，並以泛美航空飛行員的假身份環遊世界，這些都發生在他21周歲之前。也許他最令人吃驚的“事跡”，就是在20世紀60年代的亞特蘭大成功假扮醫生將近一年之久。行醫應該需要在醫學院學習多年，要有執照、實習期等諸如此類的東西，但阿巴內爾成功避開所有這些細節，而且從未被人發現。
想象一下如何去冒這個險。你偷偷摸摸進入醫生不在的辦公室，不久後有個病人走進來，並把他所有的症狀都告訴了你。現在你得給他診斷，除非你對於藥物一竅不通。你隻有一櫃子的病人資料：他們的症狀、診斷結果、接受過的治療等。你該怎麽辦？最簡單的辦法就是找到和現在這個病人症狀最相似的病人的資料，然後做相同的診斷。如果你對待病人的態度和阿巴內爾一樣有說服力，那麽可能會成功。在醫學之外，同樣的思想也很適用。如果你是一名年輕的總統，麵臨世界危機，就像肯尼迪當年一樣，當時美國的一架間諜機報告，蘇聯的核導彈被部署在古巴，你很有可能因為經驗不足而措手不及。你可以找曆史上與當前情況相似的場景，然後嚐試從這些場景中吸收經驗。參謀長聯席會議敦促對古巴進行襲擊，但肯尼迪那時剛讀過《八月炮火》，這是一本描寫第一次世界大戰的暢銷書，所以他知道那樣做很容易會引發全麵戰爭。所以他選擇了對古巴進行海上封鎖，也許這樣做把世界從核戰爭中拯救出來了。
類比是推動許多曆史上最偉大科學進步的動力。當達爾文閱讀馬爾薩斯的《人口論》時，被經濟和自然界中生存競爭的相似性觸動，所以有了自然選擇理論的誕生。波爾的原子核模型是由將模型看作微型太陽係、將電子看作行星、將原子核看作太陽而產生的。克庫勒也是白天做夢夢見蛇吃自己的尾巴才發現苯分子的環狀結構的。
類比推理有著突出的知識譜係。亞裏士多德在他的相似律中就表達了這一點：如果兩個事物相似，其中的一個想法會觸發另外一個想法。諸如洛克和休謨之類的經驗主義者就追隨這個規律。尼采說，真理是一支由暗喻擬人組成的隊伍。康德也是其中的信奉者。威廉·詹姆斯認為：“這種意義上的一致性是我們思想的支柱。”一些當時的心理學家甚至認為從整體上看，人類認知是分析必不可少的部分。我們依靠它來找到通往新城市的道路，並理解諸如“領悟”“形象高大”之類的表達。那些十幾歲、喜歡說話時在每個句子中加入“像”的人也許喜歡且認為類別是重要的。
考慮到這一點，類比在機器學習中扮演重要角色就不足為奇了。剛開始它進展緩慢，甚至被神經網絡奪走了光芒。它的第一個算法的化身出現在一份寫於1951年、名不見經傳的技術報告中，作者是兩位伯克利的統計學家——伊夫琳·菲克斯和喬·霍奇斯。這篇報告幾十年之後才發表於主流期刊中。但同時，關於菲克斯和霍奇斯的算法的論文也開始出現，後來逐漸增加，直到它成為計算機科學界中受到研究最多的文章之一。最近鄰算法，正如其名，是我們類比學習法之旅的第一站。第二站是支持向量機，這是世紀之交風靡機器學習領域的原理，但最近風頭被深度學習掩蓋。第三站也是最後一站，是成熟的類比推理法，幾十年來是心理學和人工智能的重要組成部分，也是幾十年來機器學習領域的背景主題。
5個學派中，類推學派是最不具有凝聚力的一個學派。不像其他學派有很強的身份意識和共同理想，類推學派則更像研究人員鬆散的集合體，他們的統一依靠的是對於作為學習基礎的、相似性判斷的信任。一些人，比如支持向量機的支持者甚至可能會反對將自己歸入這個範疇。但我認為如果人們能為共同的事業而努力，會受益很多。在機器學習中，相似性是核心思想之一，而類推學派會以各種偽裝的方式來保護它。也許在未來10年，機器學習會被深度類比統治，在某種算法中，與最近鄰法的高效、支持向量機的數學精密性、類比推理的力量和靈活性結合（瞧，我又泄露了自己的一個秘密研究計劃）。 <h2>完美另一半</h2>
最近鄰算法是人類有史以來發明的最簡單、最快速的學習算法。實際上，你甚至可以說，這是人類可以發明的最快速的算法。它可以說什麽也不做，所以花在運行上的時間為零。再沒有比這個更好的了。如果想掌握麵部識別技巧，且有大量標有臉部或非臉部標簽的圖片，你隻需讓算法待在那兒就好。別擔心，高興起來吧。在不知道的情況下，那些圖片已經暗中形成關於“什麽是臉”的模型。假設你是臉書，想在照片上自動識別人臉，人們上傳這些照片，就是用朋友的名字來標記這些照片的前奏。不用做什麽是一件好事，隻要臉書用戶每天上傳超過3億張照片就可以了。將目前為止我們見過的學習算法（可能要排除樸素貝葉斯法這個例外）應用到這些照片上，可能需要一卡車計算機，而貝葉斯算法的智能程度還不足以用來識別臉部。
當然，這是要付出代價的，這個代價在測試時會出現。名叫簡的用戶剛上傳一張新的照片。這是一張臉嗎？最近鄰算法的回答是：在臉書所有標記過的照片庫中，找到那張和這張最相似的照片（它的“最近鄰”）如果那張照片包含一張臉，這張也會有。這足夠簡單，但理想的情況下，你得在不到一秒的時間內瀏覽近幾十億張照片。就像一個不想為考試而學習的懶學生，最近鄰算法此時猝不及防，不得不斷斷續續地運行。不像在現實生活中，你的媽媽會跟你說不要把今天可以做的事留到明天，在機器學習中，拖延真的可以帶來成功。實際上，學習的整個風格（最近鄰算法是其中一種）有時會被人們稱為“懶惰學習算法”，在這種情況下，這個術語並沒有什麽貶義。
懶惰學習算法之所以比它表麵看起來更加智能，是因為雖然它的模型是隱性的，但其實它可以很複雜。考慮到極端的情況下，每個等級我們隻能有一個例子。例如，我們想知道兩個國家的邊界在哪裏，但我們知道的僅僅是其首都的位置。多數學習算法可能會被難住，但最近鄰算法會恰當地猜出，邊界會是一條線，位於兩個城市的中間位置（見圖7–1）。
圖7–1
邊界上的點距離兩個首都的距離都一樣，邊界線左邊的點距離positiville市較近，因此最近鄰算法假定這些點是posistan國的一部分，反之亦然。如果那條線就是準確的邊界，當然是萬幸，但作為一種近似法，很有可能這條線什麽也不是。當我們知道邊界線兩邊都有很多城市時，事情才真正變得有趣起來（見圖7–2）。
圖7–2
最近鄰算法可以暗中形成一條非常複雜的邊界線，雖然它所做的隻是記住每個城市的位置，然後將這些點相應地分給每個國家。我們可以將城市的“城域”看作那些最靠近該城市的點，城域之間的界線在圖中用虛線來表示。現在posistan隻是它的所有城市城域的集合，和negnd一樣。相反，決策樹（舉個例子）也許隻會形成不是南北向就是東西向的邊界，可能更不利於找到真正的邊界。因此，雖然決策樹算法“願望更加強烈”，在學習期間很努力地想弄明白邊界線的位置，但“懶惰的”最近鄰算法實際上最後會勝出。
懶惰學習算法會勝出的原因在於，和構建全局模型（例如，決策樹）相比，隻要每次弄明白指定的點在哪裏會較為簡單。想象一下，利用決策樹來嚐試確定什麽是臉。你可以說，臉有兩隻眼睛、一個鼻子和一張嘴，但什麽是眼睛，而你在一張圖片中怎樣才能找到它呢？如果人的眼睛是閉上的，那又會怎樣呢？準確定義一張臉，細到每個像素，這是十分困難的，在表情、姿態、背景、光線條件各異的情況下尤甚。而最近鄰算法則走捷徑：如果數據庫中與簡上傳的最相似的那張照片是臉部照片，那麽簡的照片也是。要出現這種情況，數據庫就得有一張照片，與新照片足夠相似，因此，數據庫越大越好。對於一個簡單的二維問題，比如猜出兩個國家的邊界，一個小數據庫就足夠了。對於一個很難的問題來說，如識別臉部，因為每個像素的顏色都是變化的一個維度，所以需要巨大的數據庫。目前我們有這些數據庫。但對於渴望學習的算法來說，要從這些數據庫中學習東西可能代價很大，因為這種算法要明確劃分臉部和非臉部的界線。然而，對於最近鄰算法來說，界線隱含在數據點和距離度量中，而唯一要付出的就是查詢時間。
構建局部模型而非全局模型的相同想法可以應用於分類之外的用途。通常科學家們利用線性回歸來預測連續變量，但大多數現象是非線性的。幸運的是，從局部來看，它們是線性的，因為平滑曲線可以局部近似為直線。因此如果你隻用直線來對查詢點附近的點，而不是嚐試對所有的數據都進行擬合，那麽你現在就能擁有一個非常強大的非線性回歸算法。懶惰也會有回報。如果肯尼迪需要一套完整的國際關係理論來決定該如何應對蘇聯在古巴部署的導彈，他可能會遇到麻煩。相反，他從這個危機與第一次世界大戰的爆發之間找到相似點，而這個相似點指引他做了正確的決定。
最近鄰算法可以用來救命，正如史蒂芬·約翰遜在《幽靈地圖》中描述的那樣。1854年，倫敦爆發霍亂，城市部分地區8個人中就有1個人死亡。當時的理論認為，霍亂由“不良氣體”引起，但該理論並沒能阻止霍亂的蔓延，約翰·斯諾（一位質疑該理論的內科醫師）則有更好的主意。他在倫敦地圖上標出所有霍亂病例的位置，然後劃分地圖，每個區域都距離公共水泵最近。有了！幾乎所有死者都位於某個特定水泵的“城域”中，也就是位於蘇活區的布羅德大街上。經推斷井裏的水被汙染了，斯諾說服當地人禁止使用該水泵，流行病就消失了。這段插曲孕育了流行病學，而它還是最近鄰算法取得的第一次成功——流行病學正式出現還是在近一個世紀之後。
有了最近鄰算法，每個數據點就是自己的微型分類器，為所有獲取的查詢例子預測級別。最近鄰算法就像一群螞蟻，在這個隊伍中每隻螞蟻都做得很少，但把力量聚集在一起，它們就可以移動高山。如果一隻螞蟻的負重過大，它可以和周圍的螞蟻共同承擔。本著同樣的精神，在k最近鄰算法（k–nearest–neighbor algorithm）中，測試的例子的分類方法是找到它的k最近鄰，然後讓它們進行投票。如果距離上傳照片最近的圖片是一張臉，但接下來最近的兩張卻不是，第三張最近鄰的照片也還是會認為最新上傳的不是臉。最近鄰算法容易犯過擬合錯誤：如果數據點的等級是錯誤的，它會蔓延到整個城域當中。k最近鄰算法更可靠，因為隻有在多數k近鄰受幹擾時才會出錯。當然，犯錯的代價就是它的圖像會更模糊：邊界的細節因為投票而變得模糊。k值變大時，方差變小，但偏差變大。
利用多個k最近鄰而不僅一個近鄰，這不是事情的結局。直觀來看，與測試例子最接近的例子應該更重要。這讓我們引出加權k最近鄰算法。1994年，明尼蘇達州立大學和麻省理工學院的研究人員建立了一個推薦係統，其構建基礎是他們所謂的“一個看似簡單的想法”：過去人們同意的話，將來他們也還會同意。這個想法直接引出協同過濾係統，所有典型的電子商務網站都有這些係統。假設像網飛一樣，你建立了電影評分的數據庫，用戶對他看過的電影都會給出1~5顆星的評分。你想確認用戶肯恩是否會喜歡《地心引力》，因此你找到那些以往評分與肯恩的評分最相關的用戶。如果他們對《地心引力》評分很高，那麽可能肯恩的評分也會很高，你就可以把這部電影推薦給他。但是，如果對於《地心引力》他們有不同的看法，你就需要一個回退點，在這種情況下就要根據用戶與肯恩關係的密切程度來進行排名。因此，如果李和肯恩的關係比梅格和肯恩的關係密切，那麽相應李的評分也會更有價值。肯恩的預測評價就是與其相關的人的加權平均值，每個人的權值就是他與肯恩關係的係數。
雖然如此，但還是有一個有趣的轉變。假設李和肯恩有非常相似的品位，但李比肯恩脾氣暴躁。當肯恩給5顆星時，李會給3顆星；當肯恩給3顆星時，李會給1顆星，以此類推。我們想用李的評分來預測肯恩的評分，但如果我們直接預測，會總差2顆星。我們要做的就是，在知道李的評分值的基礎上，預測肯恩的排名超過或者低於平均值的量。而現在，既然當李總是比他的平均值高出2顆星時，肯恩也會比他的平均值高出兩顆星，我們的預測就會準確。
順便說一下，你不需要顯性評分來進行協同過濾。如果肯恩在網飛上預訂了一部電影，意味著他可能會喜歡它。這樣“評分”也才有可能被預訂或未被預訂，而兩個用戶如果預訂了很多一樣的電影，那麽他們品位就會相似。即便隻是暗暗點擊某個東西，也會代表你對它感興趣。最近鄰算法和以上提到的都會有效。目前，所有種類的算法都被用於為用戶推薦項目，但加權k最近鄰算法是第一個受到廣泛運用的算法，而且要打敗它仍然很困難。
推薦係統，亦如其名，是大業務：亞馬遜1/3的業務來自它為用戶推薦的商品，網飛3/4的業務也是如此。它與最初的最近鄰算法相差很大，因為它的記憶需求，人們覺得它不夠實用。回到那時，計算機的存儲器是用鐵圈做成的，每個比特一個鐵圈，甚至儲存幾千個例子都很費力。時代改變得多快！雖然如此，不必如此智能，以記住所有你見過的例子，然後搜索這些例子，因為多數例子可能並不相關。如果你回頭看posistan和negnd的地圖，你可能會注意到，如果positiville消失，不會有任何變化。附近城市的城域會擴張至以往被positiville占用的土地，但因為它們都是posistan的城市，與negnd的邊界還是會一樣。真正重要的是橫跨邊界、與對方國家的城市相交的城市，其他所有的城市都可以忽略。因此，使最近鄰算法更加有效的簡單方法，就是刪除所有被它們的近鄰準確分類的例子。這個技巧加上其他技巧可以使最近鄰算法得以應用於一些讓人意外的領域，例如，實時操控機器人的手臂。但不用說，它們仍然不是諸如高頻交易之類事務的第一選擇，因為在這些領域中，計算機會在一秒鍾內買賣股票。在它與神經網絡的競爭中，因為神經網絡可以應用於僅含固定數量的加法、乘法、sigmoids函數的例子中，還可應用於需要為例子的最近鄰搜索龐大數據庫的算法中，因此神經網絡肯定會獲勝。
研究人員最初之所以對最近鄰算法持懷疑態度，是因為它不確定能否找到兩個概念之間的真正邊界。但1967年，湯姆·科韋爾和彼得·哈特證明，在給定足夠數據的情況下，最近鄰算法最糟糕時易於出錯的概率也僅僅是最佳可行分類器的兩倍。舉個例子，如果因為數據中的幹擾因素，有至少1%的測試例子不可避免地被錯誤分類，那麽最近鄰算法保證誤差率最多在2%左右。這是一個重大的啟示。直到那時，所有已知的分類器都假定邊界會有一種非常明確的形式，直線就是典型例子。這是一把雙刃劍：一方麵，它使準確性的證明成為可能，正如在感知器的例子中那樣；另一方麵，這也意味著分類器受到它所能掌握東西的嚴格限製。最近鄰算法是史上第一個能夠利用不限數量的數據來掌握任意複雜概念的算法。沒人能指望它能找到在超空間中、由數百萬個例子形成的邊界，但因為科韋爾和哈特的證明，我們知道，它們可能不會錯得太離譜。據雷·庫茲韋爾的觀點，當我們無法理解計算機在做什麽時，單一性開始產生。依據該標準，說它已經在籌備當中也不稀奇——1951年就已經開始了，當時菲克斯和霍奇斯發明最近鄰算法，這個微小的算法就能做到。 <h2>維數災難</h2>
在這個伊甸園中當然也有一條蛇，它被稱為“維數災難”。雖然它對所有學習算法都會有或多或少的影響，但它對最近鄰算法的危害尤其大。在低維度條件下（比如二維或者三維），最近鄰算法通常能很好地起到作用。隨著維數的上升，事情就會很快陷入崩潰狀態。當今算法要掌握數千甚至數百萬個屬性並不稀奇。對於電子商務網站來說，它要掌握你的喜好，那麽你每點擊一下鼠標就算一種屬性。網頁上的每個詞、圖片上的每個像素也是如此。即使隻有數十或者數百個屬性，最近鄰算法也有可能已陷入困境。第一個問題就是多數屬性是不相關的：關於肯恩你可能知道100萬個事實，但很有可能隻有幾個事實與他得肺癌的風險有關。雖然知道他是否吸煙對於做出該預測很關鍵，但是也可能對知道他是否喜歡看《地心引力》用處不大。舉個例子，符號學派的方法很擅長處理非相關屬性：如果該屬性不含任何關於等級的信息，那麽它就不包含在決策樹或者規則集當中。但讓人感到無望的是，最近鄰算法會受到非相關屬性的迷惑，因為這些屬性都能夠促成例子之間的相似性。有了足夠的相關屬性，不相關維度中的偶然相似性會清除重要維度中有意義的相似性，而最近鄰算法和隨意猜測相比也好不到哪裏。
讓人感到意外的是，有一個更棘手的問題：擁有更多的屬性可能也會有害，即使這些屬性是相關的。你可能會想，終歸信息越多越好。這不是我們這個時代的口號嗎？但隨著維數的上升，用於確定概念邊界的訓練樣本的數量也會呈指數上升。如果有20個布爾屬性，就會有近100萬個可能不一樣的例子。如果有21個布爾屬性，就會有200萬個例子，而邊界也會有相應數量的方式來定義這些屬性。每個額外的屬性都會把學習問題的困難程度加倍，而這也隻是有布爾屬性的情況。如果屬性包含很多信息，添加該屬性帶來的好處可能會多於損失。如果你有的隻是能提供很少信息的屬性，比如郵件中的詞語或者圖片中的像素，那麽你可能會遇到麻煩，即使這些屬性集中在一起組成的信息足以預測你想要的是什麽。
情況會變得更糟糕。最近鄰算法的基礎是找到相似物體，而在高維度情況下，相似性的概念就會無效。超空間就像過渡區域。在三維空間裏的直覺不再適用，怪異離奇的事開始發生。想想一個橘子：一層薄薄的外殼包裹著好吃的果肉。比如橘子90%的半徑是果肉，剩下的10%則是果殼，這意味著橘子73%的體積是果肉（0.93）。現在想象一個超級橘子：90%的半徑還是果肉，但它在100個維度的空間中。那麽果肉的體積已經縮小到超級橘子體積（0.9100）的1/3000。這個超級橘子全都是皮，而並且你絕對無法將其剝開。
另外一個讓人不安的例子就發生在我們的老朋友身上——正態分布，又名鍾形曲線。正態分布認為，數據本質上就落在一個點上（正態分布的平均值），但其周圍也會有模糊的東西（由標準差給出）。對嗎？在超空間中不是這樣的。在高維度正態分布中，你比較有可能得到遠離而不是接近平均值的樣本。超空間中的鍾形曲線看起來更像甜甜圈，而不像鍾。當最近鄰算法走進這個顛倒的世界時，它會變得非常困惑。所有的例子看起來都一樣，同時因為它們距離彼此太遠，無法做出有用的預測。如果你將例子統一地隨意分布在高維度的立方體中，大部分例子會更接近立方體的一個麵，而不是接近它們的最近鄰。在中世紀的地圖中，未涉足領域會被標上“龍”、“海蛇”等其他虛構出的生物，或者隻標上“此處有怪物”的短語。在超空間中，龍無處不在，你的前門也會有。如果嚐試走到你隔壁鄰居家，那你永遠也到不了那裏；你會永遠迷失在陌生的陸地上，在這裏，所有熟悉的東西都消失不見。
決策樹也無法幸免於維數災難。舉個例子，你打算學習的概念是一個球體：球內的點是正的，球外的點是負的。通過放在球體內正合適的最小立方體，決策樹可以估算球體的體積。這不是完美的方法，但也不會太差：隻有立方體的角才會被誤分類。但在高維度空間中，超級立方體幾乎所有的體積都會出現在超球麵外。對於你準確將其標注為正的例子，你會錯誤地將許多負的例子分類為正，這會讓你的準確率驟然下降。
實際上，沒有哪種算法能夠幸免於維數災難。這是機器學習中，繼過擬合之後，第二個最糟糕的問題。“維數災難”這個術語由理查德·貝爾曼在50歲時提出的，他是一位控製論理論家。他觀察到，控製算法在三維空間中可以起到很好的作用，但在高維度空間中則變得效率極低。例如，當你想控製機器人手臂中的每個節點或者化工廠的把手時，這種情況就會出現。但在機器學習中，問題不僅僅在於計算成本——隨著維數上升，變得越來越困難的是學習本身。
然而，並不是所有東西都丟失了。我們能做的第一件事就是擺脫不相關維度。決策樹會自行做好這一點，方法就是計算每種屬性的信息增益，然後隻使用最能提供信息的屬性。對於最近鄰算法來說，我們可以完成類似的事情，方法就是首先丟棄所有那些信息增益低於閾值的屬性，然後隻在簡化的空間中測量相似性。這對於一些應用來說足夠快、足夠好，但不幸的是，這種方法會阻礙許多概念的學習，像xor邏輯那樣：如果當與其他屬性結合時，一個屬性隻描述了有關類別的一些點，而不是關於自己本身，那麽它就會被淘汰。一個代價更大但也更智能的選擇，就是圍繞學習算法來選擇屬性，並進行爬山算法研究，該研究會不斷刪除屬性，隻要不會降低最近鄰算法留存數據的準確度。牛頓也進行過許多次的屬性選擇，當時他確定要預測物體的軌跡，最重要的就是要知道它的質量——不是顏色、氣味、年齡，或者無數其他的屬性。實際上，方程式最重要的東西，就是未在方程式中出現的所有數量：一旦我們知道這些要點是什麽，要弄清楚這些要點如何相互依賴，就變得更加容易了。
要處理弱相關的屬性，一個選擇就是掌握屬性權值。我們不會讓所有維度下相似性的重要性相等，而是“縮減”不那麽相關的屬性。假設訓練例子是房間中的點，那麽高度尺寸對於我們的目標就沒那麽重要了。拋棄這一點會將所有例子投到地板上。調低高度尺寸又更像給屋子加了一層更低的天花板。當計算某點到其他點的距離時，該點的高度仍有價值，但沒有它的水平位置那麽重要。和機器學習中的許多事情一樣，我們可以通過梯度下降來掌握屬性權值。
一間屋子可能會有很高的天花板，但數據點都會在地板附近，就像一層薄薄的灰塵落在地板上。在這種情況下，我們是幸運的：這個問題看起來似乎和三維有關，其實它更接近二維。不必縮減高度，因為自然已經為我們縮減了。這個非一致性往往能夠挽救局麵，通過這一點數據在（超）空間中就可以均勻分布了。例子可能會有1000種屬性，但實際上，它們都“生存”在維度低很多的空間中。這使最近鄰算法有助於識別手寫體數字，例如，每個像素都是一個維度，因此會有很多維度，但在所有可能的圖片中隻有一小部分是數字，所有圖片都一起待在超空間小小的舒適角落裏。但是，數據“生存”的低維度空間可能會反複無常。例如，如果一間房有家具，灰塵就不會落在地板上，而會落在桌麵、椅麵、床罩、古董架上。如果我們能弄明白灰塵覆蓋地板的大致形狀，那麽我們需要的就是地板上每個點的坐標。在第八章中，我們會看到機器學習中會有整個分支致力於（可以這麽說）在超空間的黑暗中摸索，以找到地板的形狀。 <h2>空中蛇災</h2>
直到20世紀90年代，應用範圍最廣的類比學習算法就是最近鄰算法，但後來被來自其他學派更引人注目的“表親”奪去光芒。當時一種新的以相似性為基礎的算法橫空出世了，橫掃之前的所有算法。實際上，你可以說它是自冷戰結束以來的另一個“和平紅利”。它就是支持向量機（support vector machines，svm），是弗拉基米爾·萬普尼克（一位蘇聯頻率論研究者）的創意。萬普尼克的大半生都在莫斯科的控製科學研究所度過，1990年，隨著蘇聯走向解體，他移居美國，在那裏他加入傳說中的貝爾實驗室。雖然在蘇聯，萬普尼克很多時候都滿足於從事理論、紙筆工作，但在貝爾實驗室的氛圍則不一樣。研究人員正在尋找實踐結果，而萬普尼克最終決定將其想法變成算法。在幾年時間內，他和貝爾實驗室的同事已經研發出支持向量機。不久之後，支持向量機就變得無所不在，並創下不同的準確度紀錄。
表麵上看，支持向量機看起來很像加權k最近鄰算法：正類別與負類別之間的邊界由一組例子、其權值加上相似性測度來確定。測試實例會歸入正類別，條件是從平均水平上看，它看起來更像正麵例子而不是負麵例子。平均數會被加權，而支持向量機隻會記住那些用於確定邊界的關鍵例子。如果你回頭看posistan和negnd的例子，一旦我們丟掉那些不在邊界上的城市，剩下的就是這張地圖（見圖7–3）。
這些例子被稱為支持向量，因為它們是“支撐”邊界的向量：移動一個向量，邊界的一段就會滑向其他不同的地方。你也許還會注意到，邊界就是一條鋸齒狀的線，實例的確切位置會決定突然出現的拐角。真實的概念趨向於擁有更加平緩的邊界，這意味著最近鄰算法的估算可能不理想。但有了支持向量機，我們就可以掌握平緩的邊界，看起來更像圖7–4。
圖7–3
圖7–4
為了學習支持向量機，我們需要選擇向量和它們的權值。相似性度量，在支持向量機領地被稱為“核心程序”，通常被歸為先驗性。萬普尼克的一個重要觀點就是，並不是所有將正麵訓練例子從負麵訓練例子分離出來的邊界都是平等的。假設posistan和negnd發生戰爭，它們之間隔著無人區，兩邊都是布雷區。你的任務就是調查無人區，從無人區的這頭走到那頭，不能踩到任何地雷。幸運的是，你有一張地圖，告訴你地雷都埋在哪裏。顯然，你不會走舊路線：你會假設地雷可能在的位置很寬闊。這就是支持向量機所做的事，實例相當於地雷，要掌握的邊界相當於選擇的路線。邊界距離實例最近的地方就是它的安全邊際，支持向量機選擇支持向量和權值，這些向量和權值能夠產生可能的最大邊際。例如，圖7–5中的實線邊界比虛線要好。
圖7–5
虛線邊界能夠較好地將正麵例子和負麵例子分離，但很危險的是，它差點接觸到a處和b處的地雷。這些例子都是支持向量：刪除其中的一個，最大邊際邊界就會移到不同的地方。通常，邊界當然也可能是彎曲的，這使得邊界更加難以想象，但我們可以將邊界想象成爬向無人區的蛇，邊際表示這條蛇可能有多肥。如果很肥的蛇能夠一直蜿蜒爬行而不會被地雷炸得粉碎，那麽支持向量機就可以很好地將正麵例子和負麵例子分離。萬普尼克表明，在這種情況下，我們可以確信，支持向量機不會過擬合。直觀地說，和一條瘦的蛇相比，肥的蛇能夠不觸雷爬行的方法更少。同樣，和低邊際的支持向量機相比，高邊際的就不太可能因為畫了一條過於複雜的邊界而過擬合。
事情的第二部分就是支持向量機如何找到最合適的蛇，剛好夾在正麵雷區和負麵雷區之間。乍一看，通過梯度下降，為每個訓練實例掌握權值可能會成功。我們要做的，就是找到能夠將邊際最大化的權值，而那些最終結果為0權值的例子則被拋棄。不幸的是，這樣做隻會讓權值不受限製地增長，因為從數學的角度講，權值越大，邊際越大。如果距離地雷隻有1英尺，然後你將所有東西的尺寸都擴大一倍，包括你自己，你現在距離雷區有2英尺，但這樣並不會降低你踩到地雷的可能性。相反，我們得在限製範圍內將邊際最大化，該範圍內，權值智能增長到某個固定值。或者，同樣的效果，我們可以在限製範圍內將權值最小化，該範圍內所有例子都會有一個給定的邊際，該邊際有可能是1——確切來說是任意的。這就是通常支持向量機做的事情。
約束優化是在將受限函數最大化或者最小化時遇到的問題。宇宙會最大化熵，而熵遵守能量守恒定律。這類問題在商業和技術領域會經常碰到。例如，我們可能會想把工廠生產的小部件數量最大化，這個部件的數量可由機床的數量、小部件的規格等決定。有了支持向量機，約束優化對機器學習來說也會變得重要。無約束優化正在登上頂峰，而這就是梯度下降（或者，在本例子中為上升）要做的事情。約束優化就是當你停在公路上時，盡可能往高處走。如果公路延伸到頂峰，約束及無約束問題的解決方法就會一樣。即便如此，更多時候，公路彎彎曲曲圍繞著山峰，接著還沒到山頂就繞回來了。你知道自己已經到達公路的最高點，因為在不脫離公路的情況下，你已經無法開到更高的地方。換句話說，也就是到達頂點的路線與公路成直角。如果公路和到達頂點的路線形成斜角，那麽沿著公路開遠些，你總能到達更高點，即使那樣做與直線到達峰頂相比，並不會那麽快。因此，解決約束優化問題的方法，不是沿著坡麵走，而是走與約束麵平行的那部分坡麵（在該例子中為公路），然後當該部分為零時，停下來。
通常，我們得一次性處理許多個約束條件（在支持向量機的情況下，每個條件對應一個例子）。想象一下，你想盡可能地靠近北極，但你不想離開自己的房間。每間房的四麵牆就是一個限製條件，而解決辦法就是要跟著指南針直到你碰到一個角落，這個角落是東北部和西北部兩麵牆的匯合點。我們說這兩堵牆是有效約束條件，因為它們阻止你實現最佳效果，也就是北極。如果你的房間有一堵牆的外部直麵北部，那麽這就是唯一的有效約束條件，而解決方法就在於這堵牆中間的一個點。如果你是聖誕老人，而你的房間已經處在北極上方，而所有的約束條件都無效，那麽你就可以在那兒坐等，仔細考慮玩具的最優分配問題（旅行推銷員更容易將其與聖誕老人比較）。在支持向量機中，有效約束條件就是支持向量，因為它們的邊際已經是經允許達到的最小值，移動邊界會違背一個或多個限製條件。所有其他的例子都不相關，而且它們的權值都是零。
在現實中，我們通常會讓支持向量機違背一些限製條件，這就意味著將一些例子錯誤分類，或者利用更少的邊際，否則它們就會過擬合。如果在正麵區域中間的某個地方有幹擾作用的負麵例子，那麽我們不想讓邊界在正麵區域周圍環繞，目的隻是為了讓例子正確。但支持向量機會因為它弄錯的每個例子而受到懲罰，這樣就會促使它把錯誤例子降到最低。支持向量機就像《沙丘》中的沙蟲：大而強韌，可以在爬過雷區時幸免於幾次但不是很多次爆炸。
四處尋找應用的同時，萬普尼克和他的同事很快偶然發現了手寫體數字識別，他們在貝爾實驗室的聯結學派同事就是研究這個方麵的專家。讓所有人驚訝的是，支持向量機和感知器一樣，在其他領域也能很好地工作，感知器多年來已經被精心設計用於數字識別。這為兩者持續時間長、波及範圍廣的競爭奠定了基礎。支持向量機可以當作感知器的一個概括版，因為當你利用某個特定的相似性度量時，得到的就是類別之間的超平麵邊界（向量之間的點積）。但和多層感知器相比，支持向量機有一個重要優勢：權值有單個最優條件而不是多個局部最優條件，因此可靠地掌握它們變得簡單多了。雖然如此，支持向量機的表現力依舊不比感知器差。支持向量有效地扮演隱藏層的角色，而它們的加權平均值則起到輸出層的作用。例如，一台支持向量機可以輕易表示xor函數，方法就是為4個可能的配置分配一個支持向量，但不較量一下，那些聯結主義學者便不會罷休。1995年，拉裏·傑克爾（貝爾實驗室萬普尼克所在部門的主任）和他賭一頓豐盛的大餐——到2000年，神經網絡就會和支持向量機一樣好理解。他輸了，但作為回報，萬普尼克打賭——到2005年就沒有人會使用神經網絡，後來他也輸了（唯一吃到免費大餐的是燕樂存，他們的見證人）。另外，隨著深度學習的出現，聯結學派已經重新占據優勢。隻要你能掌握它們，含有多層的網絡可以比支持向量機用更加簡潔的方式來表達許多函數，而支持向量機一直以來隻有一層，這一點就使兩者大不相同。
支持向量機早期較大的功績還在於文本分類，後來證明這是一項大實惠，因為網站那時候才人氣漸增。當時，樸素貝葉斯是最先進的文本分類器，但當語言中的每個詞都代表一個維度時，甚至它也開始過擬合了。它需要的隻是一個詞，這個詞會偶然出現在訓練數據中所有與體育相關（舉個例子）的頁麵中，而不是出現在其他頁麵中，而樸素貝葉斯開始出現幻覺，以為隻要包含該詞的頁麵都是體育頁麵。但多虧了邊際最大化，支持向量機即使在很高的維度中也可以抵抗過擬合。
通常，支持向量機選擇的支持向量越少，就能更好地進行概括。任何不是支持向量的訓練例子可能會被正確分類，條件是它顯示為測試實例，因為正麵和負麵例子之間的邊界仍在同樣的地方。因此預測支持向量機的誤差率，最多就是支持向量的那部分例子。隨著維數的上升，這部分也會上升，因此支持向量機無法幸免於維數災難，但它們最能抵抗這個災難。
除了實踐中的功績，支持向量機還完全改變了許多機器學習中的傳統觀點。例如，它揭穿了“模型越簡單就越準確”這個謊言，有時候，這個觀點會被誤以為是奧卡姆剃刀理論。相反，支持向量機可能有無限數量的參數，而且隻要它有足夠大的邊際，就不會過擬合。
然而，支持向量機唯一最讓人吃驚的屬性就是，無論它形成多麽彎曲的邊界，那些邊界也總是直線（或者一般為超平麵）。這並不矛盾，因為直線存在於不同的空間中。假設例子停在（x, y）的平麵上，而正麵和負麵區域之間的邊界是拋物線y=x2。沒有什麽方法能用直線來表示它，但如果我們添加坐標z，意味著現在數據存在於（x, y, z）空間，然後我們設定每個例子的z坐標為它的x坐標的平方，這時邊界就是由y=z定義的斜平麵。實際上，當數據點上升至三維空間時，有些數據點上升的數量正合適，但比其他數據點上升的要多，而急板（presto）在這個新維度中，正麵例子和負麵例子可能會被一個平麵分開。原來，我們可以把支持向量機利用核心程序、支持向量、權值來做的事情，看作將數據映射到更高維數的空間中，並在那個空間找到最大邊際超平麵。對於一些核心程序來說，衍生空間有無限的維數，但支持向量機完全不會因此而受到困擾。超空間可能是過渡區域，但支持向量機已經弄明白如何操縱它。 <h2>爬上梯子</h2>
兩個東西如果在一些方麵意見一致，那麽它們就是相似的。如果它們在一些方麵意見一致，可能在其他方麵也會意見一致，這就是類比的本質。它還表明了類比推理中的兩大子問題：弄明白兩個事物的相似度，確定由它們的相似度還能推導出什麽。到目前為止，我們已經探索了類比“低功耗”的一端，包含諸如最近鄰和支持向量機之類的算法，在這種情況下，這些問題的答案都非常簡單。它們的應用最為廣泛，但隻用一章來介紹類比學習並不完整，因為至少得瀏覽該領域更為強大的部分。
在任何類比學習算法中，最重要的問題就是如何度量相似性。它可以如數據點之間的歐幾裏得距離那麽簡單，也可以和含有多水平子程序的一整套程序那麽複雜，而且這些子程序的最終產出是相似度值。不管怎樣，相似度函數控製的是學習算法如何從已知例子歸納出新的例子。我們將自己對問題域所了解的東西插入學習算法中，這就變成類推學派對於休謨問題的回答。我們可以將類比學習應用到所有種類的物體中，而不僅僅是屬性向量，隻要我們有度量它們之間相似度的方法。例如，我們可以通過兩個分子之間包含相同子結構的數量，來測量兩個分子的相似度。甲烷和甲醇相似，因為它們都有三個碳氫鍵，而不同點僅在於一個氫原子代替了一個羥基（見圖7–6）。
圖7–6
然而，這並不意味著它們之間的化學行為是相似的。甲烷是氣體，而甲醇是酒精。類比推理的第二部分，就是弄明白在已經發現的相似點的基礎上，如何推導出新的東西。這可以很簡單，也可以很複雜。在最近鄰算法或者支持向量機中，這點包括在最近鄰算法或者支持向量類別的基礎上，預測新東西的類別。但在案例推理（類比學習的另外一種類型）中，輸出的可能是由檢索對象組成部分形成的複雜結構。假設你的惠普打印機吐出沒用的東西，你會打電話給求助台。他們之前很有可能已經遇到過很多次你這樣的問題，所以好辦法就是找到那些記錄，然後從這些記錄中找到可能解決你的問題的方法。這不隻是找到與你的問題有許多相似之處的投訴那麽簡單：例如，和你的打印機一起使用的是windows係統，還是mac os x？這可能會引起係統的不同設置，打印機也會變得相關。一旦你找到最相關的例子，解決你的問題所需步驟的順序，可能是不同案例中不同步驟的組合，可能還會針對你的問題進一步微調。
求助台是當今案例推理最受歡迎的應用。多數求助台仍采用人力中介，但正畸診療軟件ipsoft的虛擬求助台員工伊麗莎則與顧客直接對話。伊麗莎配有交互式視頻人物角色，迄今已經為2000多萬的顧客解決問題，這些問題大部分來自一流的美國公司。“來自機器人王國（robotistan）的問候，外包最實惠的新選擇”是近來外包博客對它的評價。而且，正如外包在不斷爬技能這架梯子，類比學習也是如此。第一個以判例為基礎、為指定判決辯論的機器人律師已經誕生。這樣的係統能夠準確預測超過90%經其審核的商業秘密案件。也許在未來的網絡法院中，亞馬遜雲服務上的某處，在開庭期間，機器人律師會推翻機械戰警給你的無人駕駛汽車開出的罰單，當你走到沙灘上時，萊布尼茨將所有辯論簡化為計算的夢想最終會實現。
可以說，站在技能這架梯子更高處的是音樂創作。大衛·科普是加州大學聖克魯斯分校的名譽教授，他設計出一種算法，能夠通過選擇並重組著名作曲家作品中的一些片段，創造出帶有這些作曲家風格的新的音樂。我在幾年前參加過的一個會議上，他演奏了“莫紮特”的三個片段：一段來自真正的莫紮特，一段出自人類作曲家模仿的莫紮特，一段來自他自己的係統。然後他讓聽眾為真正的莫紮特投票。沃爾夫岡勝出了，但計算機打敗了人類模仿者。這是一場人工智能會議，聽眾們感到非常喜悅。在其他項目中則沒有那麽開心了，一位聽眾憤怒地控訴科普，說他毀掉了他的音樂。如果科普是對的，創造性（最深不可測的東西）都可以歸結為類比和重組。你可以通過穀歌搜索“david cope mp3”來自行判斷。
然而，類比學者最棒的技巧在於跨越問題域來進行學習。人類一直在做這件事情，比如一位高管可以從一家媒體公司跳槽到另一家消費品公司，而不用從零開始，因為許多相同的管理技能仍然適用。華爾街雇用很多物理學家，因為物理和金融問題雖然表麵上看區別很大，卻往往包含相似的數學結構。然而，假如我們對目前為止見過的學習算法進行訓練，讓它們預測布朗運動，然後對股市進行預測，那麽這些算法將無法達到預期效果。股票價格和懸浮在液體中的粒子的速度隻是不同的變量，所以學習算法甚至不知道從何開始。但利用構造映射，類比學者可以完成這件事，這是戴德瑞·根特納（西北大學的一位心理學家）發明出的算法。結構映射采用兩種描述方法，發現了它們某些部分和關係的一致對應關係，然後基於這種對應關係，進一步將一個結構中的屬性轉移到另一個結構中。例如，如果是太陽係和原子的結構，我們可以將行星映射為電子，將太陽映射為原子核，並和玻爾一樣得出結論，認為電子圍繞原子核旋轉。當然，真理會更加微妙，而往往我們做出類比之後，又得重新定義它們。但能像這樣從單個例子中學習，當然是通用學習算法的一個關鍵屬性。當我們與一種新的癌症做鬥爭時，這樣的事一直在發生，因為癌症會不斷變異，我們為之前的算法掌握的模型將不再適用。我們也沒有時間從大量病人中收集關於新型癌症的數據，也許隻有一個病人，而他也需要救治。那麽我們最大的希望就是，將新型癌症與已知癌症進行對比，然後努力找到另外一種癌症，它與此種癌症的行為足夠相似，那麽一些相同的療法就會起作用。
有類比無法做到的事嗎？道格拉斯·霍夫斯泰特認為沒有，他是一位認知科學家，還是《哥德爾、艾舍爾、巴赫：集異璧之大成》的作者。霍夫斯泰特看起來有點像格林奇的雙胞胎兄弟，可能是世界上最著名的類比學者了。在《表麵與本質：類比作為思維的燃料和火焰》一書中，霍夫斯泰特和他的合作者伊曼紐爾·桑德爾激烈地爭論，認為所有智能行為都可以歸結為類比。我們學習或者發現的每樣東西，從日常詞語如“媽媽”和“玩耍”的含義，到諸如阿爾伯特·愛因斯坦、埃瓦裏斯特·伽羅瓦這些天才驚人的洞察力，這些都是類比應用於實踐中的結果。當小蒂姆看到婦女像他媽媽照顧他一樣照顧其他孩子時，它概括了“媽媽”的概念來指其他人的媽媽，而不隻他的媽媽。這反過來又是一個跳板，用來理解諸如“母艦”和“大自然”等東西。愛因斯坦的“最快樂思想”（該思想還衍生了廣義相對論），就是重力與加速度之間的類比：如果你是一台升降機，你無法判斷你的重量是因為這個還是那個而產生，因為它們的效果是一樣的。我們在類比的廣闊海洋裏遨遊，我們自己會操縱，但無意間也會被操縱。書中的每頁都會包含類比（比如本節的標題，或者前一節的標題）。《哥德爾、艾舍爾、巴赫》是哥德爾定理、艾舍爾藝術、巴赫音樂的一個延伸類比。如果終極算法不是類比，那麽它肯定就是和類比相似的東西。 <h2>起床啦</h2>
認知科學見證了符號學派與類推學派之間很長一段時間的爭論。符號學派指向他們能夠模仿但類推學派無法模仿的東西；接著類推學派弄明白如何做到這一點，然後想出他們能夠模仿但符號學派無法模仿的東西，這個循環一直重複下去。基於實例的學習——有時人們這樣稱呼它，應該更有利於模仿我們如何記住生活中的特定片段；規則是包含抽象概念（如“工作”“愛”）推理的假定選擇。但我在讀研究生時，覺得這兩者真的隻是連續區間中的點，而我們應該能夠掌握它的所有方麵。實際上，規則就是概括的實例，這種情況下我們已經“忘記”一些屬性，因為它們並不重要。相反，實例則是非常特殊的規則，每種屬性都會有一個條件。在我們的一生中，相似的片段會漸漸被抽象成基於規則的結構，比如“在餐館吃飯”。你知道去餐館會涉及從菜單裏點菜和給小費，而每次你出去吃飯的時候，都會遵守這些“行為準則”，但你可能不記得自己意識到這些準則時的第一家餐廳。
在博士論文中，我設計了一種算法，以這種方式來將基於實例的學習和基於規則的學習結合起來。一條規則不會隻和滿足它所有先決條件的實體匹配，與任何其他規則比，它會與其更加相似的實體匹配。在這個意義上講，它會更接近於滿足它的條件。例如，膽固醇濃度為220毫克/分升的人，會比濃度為200毫克/分升的人更加符合以下規則：如果膽固醇濃度超過240毫克/分升，你會有心髒病發作的風險。rise是我稱呼該算法的名字，通過以每個訓練實例作為開始來學習，然後漸漸概括每個例子，以吸收最近的例子。最終的結果通常是通則的結合，這些通則會在它們之間和多數例子匹配，越來越多的特殊規則用來將例外規則與那些規則匹配，直到到達特定記憶的“長尾”上。rise比當時最好的規則和實例學習算法預測得還要準確，而我的實驗也表明，準確地說，這是因為它結合了兩者的最佳特征。規則可以類推地進行匹配，所以它們不會再那麽脆弱。實例可以選擇空間中不同區域的不同特點，然後比最近鄰算法更能與維數災難相抗衡，而最近鄰算法隻能到處選擇相同的特征。
rise是通往終極算法的一個步驟，因為它將符號與類比學習結合起來了。然而這隻是小小的一步，因為它不具備這兩個範式的全部能力，仍缺少其他三個範式的能力。rise的規則無法以不同的方式連接起來，每個規則隻能直接從其屬性中預測例子的類別。另外，這些規則無法一次討論一個以上的實體；例如，rise無法表達這樣的規則：如果a得了感冒，而b與a有接觸，那麽b也可能會得感冒。在類比這邊，rise僅僅概括了簡單的最近鄰算法，它無法利用結構映射或者某個這樣的策略來進行跨域學習。在完成博士論文時，我找不到能夠為一種算法帶來所有5個範式能力的方法，然後我把這個問題丟在一邊一段時間。但當我把機器學習應用到諸如口碑營銷、數據集成、事例編程、網站個性化等問題中時，我不斷發現，每個這樣的範式隻提供了一部分解決辦法。我相信應該有更好的方法。
至此，我們已完成了對5個學派的介紹，同時集中了他們的觀點、議定它們的界限、探索了這些碎片如何拚湊在一起。我們現在知道的東西比一開始多得多，但還有一些東西沒有找到。在這個謎題的中心有一個很大的漏洞，使人難以看到其模式。問題在於，目前為止，我們見過的所有學習算法，需要一位老師來告訴它們正確答案。它們不會從健康細胞中區分出癌細胞，除非有人將這些細胞標記為“癌細胞”或者“健康細胞”。人類會無師自通，從出生那天開始，就已經這麽做了。正如《指環王》中站在魔多大門的弗羅多那樣，如果無法在這個障礙附近找到出路，那麽我們的長途旅行將毫無意義。有一條路可以穿越壁壘和層層守衛，勝利越來越近。跟我來……
想象一下如何去冒這個險。你偷偷摸摸進入醫生不在的辦公室，不久後有個病人走進來，並把他所有的症狀都告訴了你。現在你得給他診斷，除非你對於藥物一竅不通。你隻有一櫃子的病人資料：他們的症狀、診斷結果、接受過的治療等。你該怎麽辦？最簡單的辦法就是找到和現在這個病人症狀最相似的病人的資料，然後做相同的診斷。如果你對待病人的態度和阿巴內爾一樣有說服力，那麽可能會成功。在醫學之外，同樣的思想也很適用。如果你是一名年輕的總統，麵臨世界危機，就像肯尼迪當年一樣，當時美國的一架間諜機報告，蘇聯的核導彈被部署在古巴，你很有可能因為經驗不足而措手不及。你可以找曆史上與當前情況相似的場景，然後嚐試從這些場景中吸收經驗。參謀長聯席會議敦促對古巴進行襲擊，但肯尼迪那時剛讀過《八月炮火》，這是一本描寫第一次世界大戰的暢銷書，所以他知道那樣做很容易會引發全麵戰爭。所以他選擇了對古巴進行海上封鎖，也許這樣做把世界從核戰爭中拯救出來了。
類比是推動許多曆史上最偉大科學進步的動力。當達爾文閱讀馬爾薩斯的《人口論》時，被經濟和自然界中生存競爭的相似性觸動，所以有了自然選擇理論的誕生。波爾的原子核模型是由將模型看作微型太陽係、將電子看作行星、將原子核看作太陽而產生的。克庫勒也是白天做夢夢見蛇吃自己的尾巴才發現苯分子的環狀結構的。
類比推理有著突出的知識譜係。亞裏士多德在他的相似律中就表達了這一點：如果兩個事物相似，其中的一個想法會觸發另外一個想法。諸如洛克和休謨之類的經驗主義者就追隨這個規律。尼采說，真理是一支由暗喻擬人組成的隊伍。康德也是其中的信奉者。威廉·詹姆斯認為：“這種意義上的一致性是我們思想的支柱。”一些當時的心理學家甚至認為從整體上看，人類認知是分析必不可少的部分。我們依靠它來找到通往新城市的道路，並理解諸如“領悟”“形象高大”之類的表達。那些十幾歲、喜歡說話時在每個句子中加入“像”的人也許喜歡且認為類別是重要的。
考慮到這一點，類比在機器學習中扮演重要角色就不足為奇了。剛開始它進展緩慢，甚至被神經網絡奪走了光芒。它的第一個算法的化身出現在一份寫於1951年、名不見經傳的技術報告中，作者是兩位伯克利的統計學家——伊夫琳·菲克斯和喬·霍奇斯。這篇報告幾十年之後才發表於主流期刊中。但同時，關於菲克斯和霍奇斯的算法的論文也開始出現，後來逐漸增加，直到它成為計算機科學界中受到研究最多的文章之一。最近鄰算法，正如其名，是我們類比學習法之旅的第一站。第二站是支持向量機，這是世紀之交風靡機器學習領域的原理，但最近風頭被深度學習掩蓋。第三站也是最後一站，是成熟的類比推理法，幾十年來是心理學和人工智能的重要組成部分，也是幾十年來機器學習領域的背景主題。
5個學派中，類推學派是最不具有凝聚力的一個學派。不像其他學派有很強的身份意識和共同理想，類推學派則更像研究人員鬆散的集合體，他們的統一依靠的是對於作為學習基礎的、相似性判斷的信任。一些人，比如支持向量機的支持者甚至可能會反對將自己歸入這個範疇。但我認為如果人們能為共同的事業而努力，會受益很多。在機器學習中，相似性是核心思想之一，而類推學派會以各種偽裝的方式來保護它。也許在未來10年，機器學習會被深度類比統治，在某種算法中，與最近鄰法的高效、支持向量機的數學精密性、類比推理的力量和靈活性結合（瞧，我又泄露了自己的一個秘密研究計劃）。 <h2>完美另一半</h2>
最近鄰算法是人類有史以來發明的最簡單、最快速的學習算法。實際上，你甚至可以說，這是人類可以發明的最快速的算法。它可以說什麽也不做，所以花在運行上的時間為零。再沒有比這個更好的了。如果想掌握麵部識別技巧，且有大量標有臉部或非臉部標簽的圖片，你隻需讓算法待在那兒就好。別擔心，高興起來吧。在不知道的情況下，那些圖片已經暗中形成關於“什麽是臉”的模型。假設你是臉書，想在照片上自動識別人臉，人們上傳這些照片，就是用朋友的名字來標記這些照片的前奏。不用做什麽是一件好事，隻要臉書用戶每天上傳超過3億張照片就可以了。將目前為止我們見過的學習算法（可能要排除樸素貝葉斯法這個例外）應用到這些照片上，可能需要一卡車計算機，而貝葉斯算法的智能程度還不足以用來識別臉部。
當然，這是要付出代價的，這個代價在測試時會出現。名叫簡的用戶剛上傳一張新的照片。這是一張臉嗎？最近鄰算法的回答是：在臉書所有標記過的照片庫中，找到那張和這張最相似的照片（它的“最近鄰”）如果那張照片包含一張臉，這張也會有。這足夠簡單，但理想的情況下，你得在不到一秒的時間內瀏覽近幾十億張照片。就像一個不想為考試而學習的懶學生，最近鄰算法此時猝不及防，不得不斷斷續續地運行。不像在現實生活中，你的媽媽會跟你說不要把今天可以做的事留到明天，在機器學習中，拖延真的可以帶來成功。實際上，學習的整個風格（最近鄰算法是其中一種）有時會被人們稱為“懶惰學習算法”，在這種情況下，這個術語並沒有什麽貶義。
懶惰學習算法之所以比它表麵看起來更加智能，是因為雖然它的模型是隱性的，但其實它可以很複雜。考慮到極端的情況下，每個等級我們隻能有一個例子。例如，我們想知道兩個國家的邊界在哪裏，但我們知道的僅僅是其首都的位置。多數學習算法可能會被難住，但最近鄰算法會恰當地猜出，邊界會是一條線，位於兩個城市的中間位置（見圖7–1）。
圖7–1
邊界上的點距離兩個首都的距離都一樣，邊界線左邊的點距離positiville市較近，因此最近鄰算法假定這些點是posistan國的一部分，反之亦然。如果那條線就是準確的邊界，當然是萬幸，但作為一種近似法，很有可能這條線什麽也不是。當我們知道邊界線兩邊都有很多城市時，事情才真正變得有趣起來（見圖7–2）。
圖7–2
最近鄰算法可以暗中形成一條非常複雜的邊界線，雖然它所做的隻是記住每個城市的位置，然後將這些點相應地分給每個國家。我們可以將城市的“城域”看作那些最靠近該城市的點，城域之間的界線在圖中用虛線來表示。現在posistan隻是它的所有城市城域的集合，和negnd一樣。相反，決策樹（舉個例子）也許隻會形成不是南北向就是東西向的邊界，可能更不利於找到真正的邊界。因此，雖然決策樹算法“願望更加強烈”，在學習期間很努力地想弄明白邊界線的位置，但“懶惰的”最近鄰算法實際上最後會勝出。
懶惰學習算法會勝出的原因在於，和構建全局模型（例如，決策樹）相比，隻要每次弄明白指定的點在哪裏會較為簡單。想象一下，利用決策樹來嚐試確定什麽是臉。你可以說，臉有兩隻眼睛、一個鼻子和一張嘴，但什麽是眼睛，而你在一張圖片中怎樣才能找到它呢？如果人的眼睛是閉上的，那又會怎樣呢？準確定義一張臉，細到每個像素，這是十分困難的，在表情、姿態、背景、光線條件各異的情況下尤甚。而最近鄰算法則走捷徑：如果數據庫中與簡上傳的最相似的那張照片是臉部照片，那麽簡的照片也是。要出現這種情況，數據庫就得有一張照片，與新照片足夠相似，因此，數據庫越大越好。對於一個簡單的二維問題，比如猜出兩個國家的邊界，一個小數據庫就足夠了。對於一個很難的問題來說，如識別臉部，因為每個像素的顏色都是變化的一個維度，所以需要巨大的數據庫。目前我們有這些數據庫。但對於渴望學習的算法來說，要從這些數據庫中學習東西可能代價很大，因為這種算法要明確劃分臉部和非臉部的界線。然而，對於最近鄰算法來說，界線隱含在數據點和距離度量中，而唯一要付出的就是查詢時間。
構建局部模型而非全局模型的相同想法可以應用於分類之外的用途。通常科學家們利用線性回歸來預測連續變量，但大多數現象是非線性的。幸運的是，從局部來看，它們是線性的，因為平滑曲線可以局部近似為直線。因此如果你隻用直線來對查詢點附近的點，而不是嚐試對所有的數據都進行擬合，那麽你現在就能擁有一個非常強大的非線性回歸算法。懶惰也會有回報。如果肯尼迪需要一套完整的國際關係理論來決定該如何應對蘇聯在古巴部署的導彈，他可能會遇到麻煩。相反，他從這個危機與第一次世界大戰的爆發之間找到相似點，而這個相似點指引他做了正確的決定。
最近鄰算法可以用來救命，正如史蒂芬·約翰遜在《幽靈地圖》中描述的那樣。1854年，倫敦爆發霍亂，城市部分地區8個人中就有1個人死亡。當時的理論認為，霍亂由“不良氣體”引起，但該理論並沒能阻止霍亂的蔓延，約翰·斯諾（一位質疑該理論的內科醫師）則有更好的主意。他在倫敦地圖上標出所有霍亂病例的位置，然後劃分地圖，每個區域都距離公共水泵最近。有了！幾乎所有死者都位於某個特定水泵的“城域”中，也就是位於蘇活區的布羅德大街上。經推斷井裏的水被汙染了，斯諾說服當地人禁止使用該水泵，流行病就消失了。這段插曲孕育了流行病學，而它還是最近鄰算法取得的第一次成功——流行病學正式出現還是在近一個世紀之後。
有了最近鄰算法，每個數據點就是自己的微型分類器，為所有獲取的查詢例子預測級別。最近鄰算法就像一群螞蟻，在這個隊伍中每隻螞蟻都做得很少，但把力量聚集在一起，它們就可以移動高山。如果一隻螞蟻的負重過大，它可以和周圍的螞蟻共同承擔。本著同樣的精神，在k最近鄰算法（k–nearest–neighbor algorithm）中，測試的例子的分類方法是找到它的k最近鄰，然後讓它們進行投票。如果距離上傳照片最近的圖片是一張臉，但接下來最近的兩張卻不是，第三張最近鄰的照片也還是會認為最新上傳的不是臉。最近鄰算法容易犯過擬合錯誤：如果數據點的等級是錯誤的，它會蔓延到整個城域當中。k最近鄰算法更可靠，因為隻有在多數k近鄰受幹擾時才會出錯。當然，犯錯的代價就是它的圖像會更模糊：邊界的細節因為投票而變得模糊。k值變大時，方差變小，但偏差變大。
利用多個k最近鄰而不僅一個近鄰，這不是事情的結局。直觀來看，與測試例子最接近的例子應該更重要。這讓我們引出加權k最近鄰算法。1994年，明尼蘇達州立大學和麻省理工學院的研究人員建立了一個推薦係統，其構建基礎是他們所謂的“一個看似簡單的想法”：過去人們同意的話，將來他們也還會同意。這個想法直接引出協同過濾係統，所有典型的電子商務網站都有這些係統。假設像網飛一樣，你建立了電影評分的數據庫，用戶對他看過的電影都會給出1~5顆星的評分。你想確認用戶肯恩是否會喜歡《地心引力》，因此你找到那些以往評分與肯恩的評分最相關的用戶。如果他們對《地心引力》評分很高，那麽可能肯恩的評分也會很高，你就可以把這部電影推薦給他。但是，如果對於《地心引力》他們有不同的看法，你就需要一個回退點，在這種情況下就要根據用戶與肯恩關係的密切程度來進行排名。因此，如果李和肯恩的關係比梅格和肯恩的關係密切，那麽相應李的評分也會更有價值。肯恩的預測評價就是與其相關的人的加權平均值，每個人的權值就是他與肯恩關係的係數。
雖然如此，但還是有一個有趣的轉變。假設李和肯恩有非常相似的品位，但李比肯恩脾氣暴躁。當肯恩給5顆星時，李會給3顆星；當肯恩給3顆星時，李會給1顆星，以此類推。我們想用李的評分來預測肯恩的評分，但如果我們直接預測，會總差2顆星。我們要做的就是，在知道李的評分值的基礎上，預測肯恩的排名超過或者低於平均值的量。而現在，既然當李總是比他的平均值高出2顆星時，肯恩也會比他的平均值高出兩顆星，我們的預測就會準確。
順便說一下，你不需要顯性評分來進行協同過濾。如果肯恩在網飛上預訂了一部電影，意味著他可能會喜歡它。這樣“評分”也才有可能被預訂或未被預訂，而兩個用戶如果預訂了很多一樣的電影，那麽他們品位就會相似。即便隻是暗暗點擊某個東西，也會代表你對它感興趣。最近鄰算法和以上提到的都會有效。目前，所有種類的算法都被用於為用戶推薦項目，但加權k最近鄰算法是第一個受到廣泛運用的算法，而且要打敗它仍然很困難。
推薦係統，亦如其名，是大業務：亞馬遜1/3的業務來自它為用戶推薦的商品，網飛3/4的業務也是如此。它與最初的最近鄰算法相差很大，因為它的記憶需求，人們覺得它不夠實用。回到那時，計算機的存儲器是用鐵圈做成的，每個比特一個鐵圈，甚至儲存幾千個例子都很費力。時代改變得多快！雖然如此，不必如此智能，以記住所有你見過的例子，然後搜索這些例子，因為多數例子可能並不相關。如果你回頭看posistan和negnd的地圖，你可能會注意到，如果positiville消失，不會有任何變化。附近城市的城域會擴張至以往被positiville占用的土地，但因為它們都是posistan的城市，與negnd的邊界還是會一樣。真正重要的是橫跨邊界、與對方國家的城市相交的城市，其他所有的城市都可以忽略。因此，使最近鄰算法更加有效的簡單方法，就是刪除所有被它們的近鄰準確分類的例子。這個技巧加上其他技巧可以使最近鄰算法得以應用於一些讓人意外的領域，例如，實時操控機器人的手臂。但不用說，它們仍然不是諸如高頻交易之類事務的第一選擇，因為在這些領域中，計算機會在一秒鍾內買賣股票。在它與神經網絡的競爭中，因為神經網絡可以應用於僅含固定數量的加法、乘法、sigmoids函數的例子中，還可應用於需要為例子的最近鄰搜索龐大數據庫的算法中，因此神經網絡肯定會獲勝。
研究人員最初之所以對最近鄰算法持懷疑態度，是因為它不確定能否找到兩個概念之間的真正邊界。但1967年，湯姆·科韋爾和彼得·哈特證明，在給定足夠數據的情況下，最近鄰算法最糟糕時易於出錯的概率也僅僅是最佳可行分類器的兩倍。舉個例子，如果因為數據中的幹擾因素，有至少1%的測試例子不可避免地被錯誤分類，那麽最近鄰算法保證誤差率最多在2%左右。這是一個重大的啟示。直到那時，所有已知的分類器都假定邊界會有一種非常明確的形式，直線就是典型例子。這是一把雙刃劍：一方麵，它使準確性的證明成為可能，正如在感知器的例子中那樣；另一方麵，這也意味著分類器受到它所能掌握東西的嚴格限製。最近鄰算法是史上第一個能夠利用不限數量的數據來掌握任意複雜概念的算法。沒人能指望它能找到在超空間中、由數百萬個例子形成的邊界，但因為科韋爾和哈特的證明，我們知道，它們可能不會錯得太離譜。據雷·庫茲韋爾的觀點，當我們無法理解計算機在做什麽時，單一性開始產生。依據該標準，說它已經在籌備當中也不稀奇——1951年就已經開始了，當時菲克斯和霍奇斯發明最近鄰算法，這個微小的算法就能做到。 <h2>維數災難</h2>
在這個伊甸園中當然也有一條蛇，它被稱為“維數災難”。雖然它對所有學習算法都會有或多或少的影響，但它對最近鄰算法的危害尤其大。在低維度條件下（比如二維或者三維），最近鄰算法通常能很好地起到作用。隨著維數的上升，事情就會很快陷入崩潰狀態。當今算法要掌握數千甚至數百萬個屬性並不稀奇。對於電子商務網站來說，它要掌握你的喜好，那麽你每點擊一下鼠標就算一種屬性。網頁上的每個詞、圖片上的每個像素也是如此。即使隻有數十或者數百個屬性，最近鄰算法也有可能已陷入困境。第一個問題就是多數屬性是不相關的：關於肯恩你可能知道100萬個事實，但很有可能隻有幾個事實與他得肺癌的風險有關。雖然知道他是否吸煙對於做出該預測很關鍵，但是也可能對知道他是否喜歡看《地心引力》用處不大。舉個例子，符號學派的方法很擅長處理非相關屬性：如果該屬性不含任何關於等級的信息，那麽它就不包含在決策樹或者規則集當中。但讓人感到無望的是，最近鄰算法會受到非相關屬性的迷惑，因為這些屬性都能夠促成例子之間的相似性。有了足夠的相關屬性，不相關維度中的偶然相似性會清除重要維度中有意義的相似性，而最近鄰算法和隨意猜測相比也好不到哪裏。
讓人感到意外的是，有一個更棘手的問題：擁有更多的屬性可能也會有害，即使這些屬性是相關的。你可能會想，終歸信息越多越好。這不是我們這個時代的口號嗎？但隨著維數的上升，用於確定概念邊界的訓練樣本的數量也會呈指數上升。如果有20個布爾屬性，就會有近100萬個可能不一樣的例子。如果有21個布爾屬性，就會有200萬個例子，而邊界也會有相應數量的方式來定義這些屬性。每個額外的屬性都會把學習問題的困難程度加倍，而這也隻是有布爾屬性的情況。如果屬性包含很多信息，添加該屬性帶來的好處可能會多於損失。如果你有的隻是能提供很少信息的屬性，比如郵件中的詞語或者圖片中的像素，那麽你可能會遇到麻煩，即使這些屬性集中在一起組成的信息足以預測你想要的是什麽。
情況會變得更糟糕。最近鄰算法的基礎是找到相似物體，而在高維度情況下，相似性的概念就會無效。超空間就像過渡區域。在三維空間裏的直覺不再適用，怪異離奇的事開始發生。想想一個橘子：一層薄薄的外殼包裹著好吃的果肉。比如橘子90%的半徑是果肉，剩下的10%則是果殼，這意味著橘子73%的體積是果肉（0.93）。現在想象一個超級橘子：90%的半徑還是果肉，但它在100個維度的空間中。那麽果肉的體積已經縮小到超級橘子體積（0.9100）的1/3000。這個超級橘子全都是皮，而並且你絕對無法將其剝開。
另外一個讓人不安的例子就發生在我們的老朋友身上——正態分布，又名鍾形曲線。正態分布認為，數據本質上就落在一個點上（正態分布的平均值），但其周圍也會有模糊的東西（由標準差給出）。對嗎？在超空間中不是這樣的。在高維度正態分布中，你比較有可能得到遠離而不是接近平均值的樣本。超空間中的鍾形曲線看起來更像甜甜圈，而不像鍾。當最近鄰算法走進這個顛倒的世界時，它會變得非常困惑。所有的例子看起來都一樣，同時因為它們距離彼此太遠，無法做出有用的預測。如果你將例子統一地隨意分布在高維度的立方體中，大部分例子會更接近立方體的一個麵，而不是接近它們的最近鄰。在中世紀的地圖中，未涉足領域會被標上“龍”、“海蛇”等其他虛構出的生物，或者隻標上“此處有怪物”的短語。在超空間中，龍無處不在，你的前門也會有。如果嚐試走到你隔壁鄰居家，那你永遠也到不了那裏；你會永遠迷失在陌生的陸地上，在這裏，所有熟悉的東西都消失不見。
決策樹也無法幸免於維數災難。舉個例子，你打算學習的概念是一個球體：球內的點是正的，球外的點是負的。通過放在球體內正合適的最小立方體，決策樹可以估算球體的體積。這不是完美的方法，但也不會太差：隻有立方體的角才會被誤分類。但在高維度空間中，超級立方體幾乎所有的體積都會出現在超球麵外。對於你準確將其標注為正的例子，你會錯誤地將許多負的例子分類為正，這會讓你的準確率驟然下降。
實際上，沒有哪種算法能夠幸免於維數災難。這是機器學習中，繼過擬合之後，第二個最糟糕的問題。“維數災難”這個術語由理查德·貝爾曼在50歲時提出的，他是一位控製論理論家。他觀察到，控製算法在三維空間中可以起到很好的作用，但在高維度空間中則變得效率極低。例如，當你想控製機器人手臂中的每個節點或者化工廠的把手時，這種情況就會出現。但在機器學習中，問題不僅僅在於計算成本——隨著維數上升，變得越來越困難的是學習本身。
然而，並不是所有東西都丟失了。我們能做的第一件事就是擺脫不相關維度。決策樹會自行做好這一點，方法就是計算每種屬性的信息增益，然後隻使用最能提供信息的屬性。對於最近鄰算法來說，我們可以完成類似的事情，方法就是首先丟棄所有那些信息增益低於閾值的屬性，然後隻在簡化的空間中測量相似性。這對於一些應用來說足夠快、足夠好，但不幸的是，這種方法會阻礙許多概念的學習，像xor邏輯那樣：如果當與其他屬性結合時，一個屬性隻描述了有關類別的一些點，而不是關於自己本身，那麽它就會被淘汰。一個代價更大但也更智能的選擇，就是圍繞學習算法來選擇屬性，並進行爬山算法研究，該研究會不斷刪除屬性，隻要不會降低最近鄰算法留存數據的準確度。牛頓也進行過許多次的屬性選擇，當時他確定要預測物體的軌跡，最重要的就是要知道它的質量——不是顏色、氣味、年齡，或者無數其他的屬性。實際上，方程式最重要的東西，就是未在方程式中出現的所有數量：一旦我們知道這些要點是什麽，要弄清楚這些要點如何相互依賴，就變得更加容易了。
要處理弱相關的屬性，一個選擇就是掌握屬性權值。我們不會讓所有維度下相似性的重要性相等，而是“縮減”不那麽相關的屬性。假設訓練例子是房間中的點，那麽高度尺寸對於我們的目標就沒那麽重要了。拋棄這一點會將所有例子投到地板上。調低高度尺寸又更像給屋子加了一層更低的天花板。當計算某點到其他點的距離時，該點的高度仍有價值，但沒有它的水平位置那麽重要。和機器學習中的許多事情一樣，我們可以通過梯度下降來掌握屬性權值。
一間屋子可能會有很高的天花板，但數據點都會在地板附近，就像一層薄薄的灰塵落在地板上。在這種情況下，我們是幸運的：這個問題看起來似乎和三維有關，其實它更接近二維。不必縮減高度，因為自然已經為我們縮減了。這個非一致性往往能夠挽救局麵，通過這一點數據在（超）空間中就可以均勻分布了。例子可能會有1000種屬性，但實際上，它們都“生存”在維度低很多的空間中。這使最近鄰算法有助於識別手寫體數字，例如，每個像素都是一個維度，因此會有很多維度，但在所有可能的圖片中隻有一小部分是數字，所有圖片都一起待在超空間小小的舒適角落裏。但是，數據“生存”的低維度空間可能會反複無常。例如，如果一間房有家具，灰塵就不會落在地板上，而會落在桌麵、椅麵、床罩、古董架上。如果我們能弄明白灰塵覆蓋地板的大致形狀，那麽我們需要的就是地板上每個點的坐標。在第八章中，我們會看到機器學習中會有整個分支致力於（可以這麽說）在超空間的黑暗中摸索，以找到地板的形狀。 <h2>空中蛇災</h2>
直到20世紀90年代，應用範圍最廣的類比學習算法就是最近鄰算法，但後來被來自其他學派更引人注目的“表親”奪去光芒。當時一種新的以相似性為基礎的算法橫空出世了，橫掃之前的所有算法。實際上，你可以說它是自冷戰結束以來的另一個“和平紅利”。它就是支持向量機（support vector machines，svm），是弗拉基米爾·萬普尼克（一位蘇聯頻率論研究者）的創意。萬普尼克的大半生都在莫斯科的控製科學研究所度過，1990年，隨著蘇聯走向解體，他移居美國，在那裏他加入傳說中的貝爾實驗室。雖然在蘇聯，萬普尼克很多時候都滿足於從事理論、紙筆工作，但在貝爾實驗室的氛圍則不一樣。研究人員正在尋找實踐結果，而萬普尼克最終決定將其想法變成算法。在幾年時間內，他和貝爾實驗室的同事已經研發出支持向量機。不久之後，支持向量機就變得無所不在，並創下不同的準確度紀錄。
表麵上看，支持向量機看起來很像加權k最近鄰算法：正類別與負類別之間的邊界由一組例子、其權值加上相似性測度來確定。測試實例會歸入正類別，條件是從平均水平上看，它看起來更像正麵例子而不是負麵例子。平均數會被加權，而支持向量機隻會記住那些用於確定邊界的關鍵例子。如果你回頭看posistan和negnd的例子，一旦我們丟掉那些不在邊界上的城市，剩下的就是這張地圖（見圖7–3）。
這些例子被稱為支持向量，因為它們是“支撐”邊界的向量：移動一個向量，邊界的一段就會滑向其他不同的地方。你也許還會注意到，邊界就是一條鋸齒狀的線，實例的確切位置會決定突然出現的拐角。真實的概念趨向於擁有更加平緩的邊界，這意味著最近鄰算法的估算可能不理想。但有了支持向量機，我們就可以掌握平緩的邊界，看起來更像圖7–4。
圖7–3
圖7–4
為了學習支持向量機，我們需要選擇向量和它們的權值。相似性度量，在支持向量機領地被稱為“核心程序”，通常被歸為先驗性。萬普尼克的一個重要觀點就是，並不是所有將正麵訓練例子從負麵訓練例子分離出來的邊界都是平等的。假設posistan和negnd發生戰爭，它們之間隔著無人區，兩邊都是布雷區。你的任務就是調查無人區，從無人區的這頭走到那頭，不能踩到任何地雷。幸運的是，你有一張地圖，告訴你地雷都埋在哪裏。顯然，你不會走舊路線：你會假設地雷可能在的位置很寬闊。這就是支持向量機所做的事，實例相當於地雷，要掌握的邊界相當於選擇的路線。邊界距離實例最近的地方就是它的安全邊際，支持向量機選擇支持向量和權值，這些向量和權值能夠產生可能的最大邊際。例如，圖7–5中的實線邊界比虛線要好。
圖7–5
虛線邊界能夠較好地將正麵例子和負麵例子分離，但很危險的是，它差點接觸到a處和b處的地雷。這些例子都是支持向量：刪除其中的一個，最大邊際邊界就會移到不同的地方。通常，邊界當然也可能是彎曲的，這使得邊界更加難以想象，但我們可以將邊界想象成爬向無人區的蛇，邊際表示這條蛇可能有多肥。如果很肥的蛇能夠一直蜿蜒爬行而不會被地雷炸得粉碎，那麽支持向量機就可以很好地將正麵例子和負麵例子分離。萬普尼克表明，在這種情況下，我們可以確信，支持向量機不會過擬合。直觀地說，和一條瘦的蛇相比，肥的蛇能夠不觸雷爬行的方法更少。同樣，和低邊際的支持向量機相比，高邊際的就不太可能因為畫了一條過於複雜的邊界而過擬合。
事情的第二部分就是支持向量機如何找到最合適的蛇，剛好夾在正麵雷區和負麵雷區之間。乍一看，通過梯度下降，為每個訓練實例掌握權值可能會成功。我們要做的，就是找到能夠將邊際最大化的權值，而那些最終結果為0權值的例子則被拋棄。不幸的是，這樣做隻會讓權值不受限製地增長，因為從數學的角度講，權值越大，邊際越大。如果距離地雷隻有1英尺，然後你將所有東西的尺寸都擴大一倍，包括你自己，你現在距離雷區有2英尺，但這樣並不會降低你踩到地雷的可能性。相反，我們得在限製範圍內將邊際最大化，該範圍內，權值智能增長到某個固定值。或者，同樣的效果，我們可以在限製範圍內將權值最小化，該範圍內所有例子都會有一個給定的邊際，該邊際有可能是1——確切來說是任意的。這就是通常支持向量機做的事情。
約束優化是在將受限函數最大化或者最小化時遇到的問題。宇宙會最大化熵，而熵遵守能量守恒定律。這類問題在商業和技術領域會經常碰到。例如，我們可能會想把工廠生產的小部件數量最大化，這個部件的數量可由機床的數量、小部件的規格等決定。有了支持向量機，約束優化對機器學習來說也會變得重要。無約束優化正在登上頂峰，而這就是梯度下降（或者，在本例子中為上升）要做的事情。約束優化就是當你停在公路上時，盡可能往高處走。如果公路延伸到頂峰，約束及無約束問題的解決方法就會一樣。即便如此，更多時候，公路彎彎曲曲圍繞著山峰，接著還沒到山頂就繞回來了。你知道自己已經到達公路的最高點，因為在不脫離公路的情況下，你已經無法開到更高的地方。換句話說，也就是到達頂點的路線與公路成直角。如果公路和到達頂點的路線形成斜角，那麽沿著公路開遠些，你總能到達更高點，即使那樣做與直線到達峰頂相比，並不會那麽快。因此，解決約束優化問題的方法，不是沿著坡麵走，而是走與約束麵平行的那部分坡麵（在該例子中為公路），然後當該部分為零時，停下來。
通常，我們得一次性處理許多個約束條件（在支持向量機的情況下，每個條件對應一個例子）。想象一下，你想盡可能地靠近北極，但你不想離開自己的房間。每間房的四麵牆就是一個限製條件，而解決辦法就是要跟著指南針直到你碰到一個角落，這個角落是東北部和西北部兩麵牆的匯合點。我們說這兩堵牆是有效約束條件，因為它們阻止你實現最佳效果，也就是北極。如果你的房間有一堵牆的外部直麵北部，那麽這就是唯一的有效約束條件，而解決方法就在於這堵牆中間的一個點。如果你是聖誕老人，而你的房間已經處在北極上方，而所有的約束條件都無效，那麽你就可以在那兒坐等，仔細考慮玩具的最優分配問題（旅行推銷員更容易將其與聖誕老人比較）。在支持向量機中，有效約束條件就是支持向量，因為它們的邊際已經是經允許達到的最小值，移動邊界會違背一個或多個限製條件。所有其他的例子都不相關，而且它們的權值都是零。
在現實中，我們通常會讓支持向量機違背一些限製條件，這就意味著將一些例子錯誤分類，或者利用更少的邊際，否則它們就會過擬合。如果在正麵區域中間的某個地方有幹擾作用的負麵例子，那麽我們不想讓邊界在正麵區域周圍環繞，目的隻是為了讓例子正確。但支持向量機會因為它弄錯的每個例子而受到懲罰，這樣就會促使它把錯誤例子降到最低。支持向量機就像《沙丘》中的沙蟲：大而強韌，可以在爬過雷區時幸免於幾次但不是很多次爆炸。
四處尋找應用的同時，萬普尼克和他的同事很快偶然發現了手寫體數字識別，他們在貝爾實驗室的聯結學派同事就是研究這個方麵的專家。讓所有人驚訝的是，支持向量機和感知器一樣，在其他領域也能很好地工作，感知器多年來已經被精心設計用於數字識別。這為兩者持續時間長、波及範圍廣的競爭奠定了基礎。支持向量機可以當作感知器的一個概括版，因為當你利用某個特定的相似性度量時，得到的就是類別之間的超平麵邊界（向量之間的點積）。但和多層感知器相比，支持向量機有一個重要優勢：權值有單個最優條件而不是多個局部最優條件，因此可靠地掌握它們變得簡單多了。雖然如此，支持向量機的表現力依舊不比感知器差。支持向量有效地扮演隱藏層的角色，而它們的加權平均值則起到輸出層的作用。例如，一台支持向量機可以輕易表示xor函數，方法就是為4個可能的配置分配一個支持向量，但不較量一下，那些聯結主義學者便不會罷休。1995年，拉裏·傑克爾（貝爾實驗室萬普尼克所在部門的主任）和他賭一頓豐盛的大餐——到2000年，神經網絡就會和支持向量機一樣好理解。他輸了，但作為回報，萬普尼克打賭——到2005年就沒有人會使用神經網絡，後來他也輸了（唯一吃到免費大餐的是燕樂存，他們的見證人）。另外，隨著深度學習的出現，聯結學派已經重新占據優勢。隻要你能掌握它們，含有多層的網絡可以比支持向量機用更加簡潔的方式來表達許多函數，而支持向量機一直以來隻有一層，這一點就使兩者大不相同。
支持向量機早期較大的功績還在於文本分類，後來證明這是一項大實惠，因為網站那時候才人氣漸增。當時，樸素貝葉斯是最先進的文本分類器，但當語言中的每個詞都代表一個維度時，甚至它也開始過擬合了。它需要的隻是一個詞，這個詞會偶然出現在訓練數據中所有與體育相關（舉個例子）的頁麵中，而不是出現在其他頁麵中，而樸素貝葉斯開始出現幻覺，以為隻要包含該詞的頁麵都是體育頁麵。但多虧了邊際最大化，支持向量機即使在很高的維度中也可以抵抗過擬合。
通常，支持向量機選擇的支持向量越少，就能更好地進行概括。任何不是支持向量的訓練例子可能會被正確分類，條件是它顯示為測試實例，因為正麵和負麵例子之間的邊界仍在同樣的地方。因此預測支持向量機的誤差率，最多就是支持向量的那部分例子。隨著維數的上升，這部分也會上升，因此支持向量機無法幸免於維數災難，但它們最能抵抗這個災難。
除了實踐中的功績，支持向量機還完全改變了許多機器學習中的傳統觀點。例如，它揭穿了“模型越簡單就越準確”這個謊言，有時候，這個觀點會被誤以為是奧卡姆剃刀理論。相反，支持向量機可能有無限數量的參數，而且隻要它有足夠大的邊際，就不會過擬合。
然而，支持向量機唯一最讓人吃驚的屬性就是，無論它形成多麽彎曲的邊界，那些邊界也總是直線（或者一般為超平麵）。這並不矛盾，因為直線存在於不同的空間中。假設例子停在（x, y）的平麵上，而正麵和負麵區域之間的邊界是拋物線y=x2。沒有什麽方法能用直線來表示它，但如果我們添加坐標z，意味著現在數據存在於（x, y, z）空間，然後我們設定每個例子的z坐標為它的x坐標的平方，這時邊界就是由y=z定義的斜平麵。實際上，當數據點上升至三維空間時，有些數據點上升的數量正合適，但比其他數據點上升的要多，而急板（presto）在這個新維度中，正麵例子和負麵例子可能會被一個平麵分開。原來，我們可以把支持向量機利用核心程序、支持向量、權值來做的事情，看作將數據映射到更高維數的空間中，並在那個空間找到最大邊際超平麵。對於一些核心程序來說，衍生空間有無限的維數，但支持向量機完全不會因此而受到困擾。超空間可能是過渡區域，但支持向量機已經弄明白如何操縱它。 <h2>爬上梯子</h2>
兩個東西如果在一些方麵意見一致，那麽它們就是相似的。如果它們在一些方麵意見一致，可能在其他方麵也會意見一致，這就是類比的本質。它還表明了類比推理中的兩大子問題：弄明白兩個事物的相似度，確定由它們的相似度還能推導出什麽。到目前為止，我們已經探索了類比“低功耗”的一端，包含諸如最近鄰和支持向量機之類的算法，在這種情況下，這些問題的答案都非常簡單。它們的應用最為廣泛，但隻用一章來介紹類比學習並不完整，因為至少得瀏覽該領域更為強大的部分。
在任何類比學習算法中，最重要的問題就是如何度量相似性。它可以如數據點之間的歐幾裏得距離那麽簡單，也可以和含有多水平子程序的一整套程序那麽複雜，而且這些子程序的最終產出是相似度值。不管怎樣，相似度函數控製的是學習算法如何從已知例子歸納出新的例子。我們將自己對問題域所了解的東西插入學習算法中，這就變成類推學派對於休謨問題的回答。我們可以將類比學習應用到所有種類的物體中，而不僅僅是屬性向量，隻要我們有度量它們之間相似度的方法。例如，我們可以通過兩個分子之間包含相同子結構的數量，來測量兩個分子的相似度。甲烷和甲醇相似，因為它們都有三個碳氫鍵，而不同點僅在於一個氫原子代替了一個羥基（見圖7–6）。
圖7–6
然而，這並不意味著它們之間的化學行為是相似的。甲烷是氣體，而甲醇是酒精。類比推理的第二部分，就是弄明白在已經發現的相似點的基礎上，如何推導出新的東西。這可以很簡單，也可以很複雜。在最近鄰算法或者支持向量機中，這點包括在最近鄰算法或者支持向量類別的基礎上，預測新東西的類別。但在案例推理（類比學習的另外一種類型）中，輸出的可能是由檢索對象組成部分形成的複雜結構。假設你的惠普打印機吐出沒用的東西，你會打電話給求助台。他們之前很有可能已經遇到過很多次你這樣的問題，所以好辦法就是找到那些記錄，然後從這些記錄中找到可能解決你的問題的方法。這不隻是找到與你的問題有許多相似之處的投訴那麽簡單：例如，和你的打印機一起使用的是windows係統，還是mac os x？這可能會引起係統的不同設置，打印機也會變得相關。一旦你找到最相關的例子，解決你的問題所需步驟的順序，可能是不同案例中不同步驟的組合，可能還會針對你的問題進一步微調。
求助台是當今案例推理最受歡迎的應用。多數求助台仍采用人力中介，但正畸診療軟件ipsoft的虛擬求助台員工伊麗莎則與顧客直接對話。伊麗莎配有交互式視頻人物角色，迄今已經為2000多萬的顧客解決問題，這些問題大部分來自一流的美國公司。“來自機器人王國（robotistan）的問候，外包最實惠的新選擇”是近來外包博客對它的評價。而且，正如外包在不斷爬技能這架梯子，類比學習也是如此。第一個以判例為基礎、為指定判決辯論的機器人律師已經誕生。這樣的係統能夠準確預測超過90%經其審核的商業秘密案件。也許在未來的網絡法院中，亞馬遜雲服務上的某處，在開庭期間，機器人律師會推翻機械戰警給你的無人駕駛汽車開出的罰單，當你走到沙灘上時，萊布尼茨將所有辯論簡化為計算的夢想最終會實現。
可以說，站在技能這架梯子更高處的是音樂創作。大衛·科普是加州大學聖克魯斯分校的名譽教授，他設計出一種算法，能夠通過選擇並重組著名作曲家作品中的一些片段，創造出帶有這些作曲家風格的新的音樂。我在幾年前參加過的一個會議上，他演奏了“莫紮特”的三個片段：一段來自真正的莫紮特，一段出自人類作曲家模仿的莫紮特，一段來自他自己的係統。然後他讓聽眾為真正的莫紮特投票。沃爾夫岡勝出了，但計算機打敗了人類模仿者。這是一場人工智能會議，聽眾們感到非常喜悅。在其他項目中則沒有那麽開心了，一位聽眾憤怒地控訴科普，說他毀掉了他的音樂。如果科普是對的，創造性（最深不可測的東西）都可以歸結為類比和重組。你可以通過穀歌搜索“david cope mp3”來自行判斷。
然而，類比學者最棒的技巧在於跨越問題域來進行學習。人類一直在做這件事情，比如一位高管可以從一家媒體公司跳槽到另一家消費品公司，而不用從零開始，因為許多相同的管理技能仍然適用。華爾街雇用很多物理學家，因為物理和金融問題雖然表麵上看區別很大，卻往往包含相似的數學結構。然而，假如我們對目前為止見過的學習算法進行訓練，讓它們預測布朗運動，然後對股市進行預測，那麽這些算法將無法達到預期效果。股票價格和懸浮在液體中的粒子的速度隻是不同的變量，所以學習算法甚至不知道從何開始。但利用構造映射，類比學者可以完成這件事，這是戴德瑞·根特納（西北大學的一位心理學家）發明出的算法。結構映射采用兩種描述方法，發現了它們某些部分和關係的一致對應關係，然後基於這種對應關係，進一步將一個結構中的屬性轉移到另一個結構中。例如，如果是太陽係和原子的結構，我們可以將行星映射為電子，將太陽映射為原子核，並和玻爾一樣得出結論，認為電子圍繞原子核旋轉。當然，真理會更加微妙，而往往我們做出類比之後，又得重新定義它們。但能像這樣從單個例子中學習，當然是通用學習算法的一個關鍵屬性。當我們與一種新的癌症做鬥爭時，這樣的事一直在發生，因為癌症會不斷變異，我們為之前的算法掌握的模型將不再適用。我們也沒有時間從大量病人中收集關於新型癌症的數據，也許隻有一個病人，而他也需要救治。那麽我們最大的希望就是，將新型癌症與已知癌症進行對比，然後努力找到另外一種癌症，它與此種癌症的行為足夠相似，那麽一些相同的療法就會起作用。
有類比無法做到的事嗎？道格拉斯·霍夫斯泰特認為沒有，他是一位認知科學家，還是《哥德爾、艾舍爾、巴赫：集異璧之大成》的作者。霍夫斯泰特看起來有點像格林奇的雙胞胎兄弟，可能是世界上最著名的類比學者了。在《表麵與本質：類比作為思維的燃料和火焰》一書中，霍夫斯泰特和他的合作者伊曼紐爾·桑德爾激烈地爭論，認為所有智能行為都可以歸結為類比。我們學習或者發現的每樣東西，從日常詞語如“媽媽”和“玩耍”的含義，到諸如阿爾伯特·愛因斯坦、埃瓦裏斯特·伽羅瓦這些天才驚人的洞察力，這些都是類比應用於實踐中的結果。當小蒂姆看到婦女像他媽媽照顧他一樣照顧其他孩子時，它概括了“媽媽”的概念來指其他人的媽媽，而不隻他的媽媽。這反過來又是一個跳板，用來理解諸如“母艦”和“大自然”等東西。愛因斯坦的“最快樂思想”（該思想還衍生了廣義相對論），就是重力與加速度之間的類比：如果你是一台升降機，你無法判斷你的重量是因為這個還是那個而產生，因為它們的效果是一樣的。我們在類比的廣闊海洋裏遨遊，我們自己會操縱，但無意間也會被操縱。書中的每頁都會包含類比（比如本節的標題，或者前一節的標題）。《哥德爾、艾舍爾、巴赫》是哥德爾定理、艾舍爾藝術、巴赫音樂的一個延伸類比。如果終極算法不是類比，那麽它肯定就是和類比相似的東西。 <h2>起床啦</h2>
認知科學見證了符號學派與類推學派之間很長一段時間的爭論。符號學派指向他們能夠模仿但類推學派無法模仿的東西；接著類推學派弄明白如何做到這一點，然後想出他們能夠模仿但符號學派無法模仿的東西，這個循環一直重複下去。基於實例的學習——有時人們這樣稱呼它，應該更有利於模仿我們如何記住生活中的特定片段；規則是包含抽象概念（如“工作”“愛”）推理的假定選擇。但我在讀研究生時，覺得這兩者真的隻是連續區間中的點，而我們應該能夠掌握它的所有方麵。實際上，規則就是概括的實例，這種情況下我們已經“忘記”一些屬性，因為它們並不重要。相反，實例則是非常特殊的規則，每種屬性都會有一個條件。在我們的一生中，相似的片段會漸漸被抽象成基於規則的結構，比如“在餐館吃飯”。你知道去餐館會涉及從菜單裏點菜和給小費，而每次你出去吃飯的時候，都會遵守這些“行為準則”，但你可能不記得自己意識到這些準則時的第一家餐廳。
在博士論文中，我設計了一種算法，以這種方式來將基於實例的學習和基於規則的學習結合起來。一條規則不會隻和滿足它所有先決條件的實體匹配，與任何其他規則比，它會與其更加相似的實體匹配。在這個意義上講，它會更接近於滿足它的條件。例如，膽固醇濃度為220毫克/分升的人，會比濃度為200毫克/分升的人更加符合以下規則：如果膽固醇濃度超過240毫克/分升，你會有心髒病發作的風險。rise是我稱呼該算法的名字，通過以每個訓練實例作為開始來學習，然後漸漸概括每個例子，以吸收最近的例子。最終的結果通常是通則的結合，這些通則會在它們之間和多數例子匹配，越來越多的特殊規則用來將例外規則與那些規則匹配，直到到達特定記憶的“長尾”上。rise比當時最好的規則和實例學習算法預測得還要準確，而我的實驗也表明，準確地說，這是因為它結合了兩者的最佳特征。規則可以類推地進行匹配，所以它們不會再那麽脆弱。實例可以選擇空間中不同區域的不同特點，然後比最近鄰算法更能與維數災難相抗衡，而最近鄰算法隻能到處選擇相同的特征。
rise是通往終極算法的一個步驟，因為它將符號與類比學習結合起來了。然而這隻是小小的一步，因為它不具備這兩個範式的全部能力，仍缺少其他三個範式的能力。rise的規則無法以不同的方式連接起來，每個規則隻能直接從其屬性中預測例子的類別。另外，這些規則無法一次討論一個以上的實體；例如，rise無法表達這樣的規則：如果a得了感冒，而b與a有接觸，那麽b也可能會得感冒。在類比這邊，rise僅僅概括了簡單的最近鄰算法，它無法利用結構映射或者某個這樣的策略來進行跨域學習。在完成博士論文時，我找不到能夠為一種算法帶來所有5個範式能力的方法，然後我把這個問題丟在一邊一段時間。但當我把機器學習應用到諸如口碑營銷、數據集成、事例編程、網站個性化等問題中時，我不斷發現，每個這樣的範式隻提供了一部分解決辦法。我相信應該有更好的方法。
至此，我們已完成了對5個學派的介紹，同時集中了他們的觀點、議定它們的界限、探索了這些碎片如何拚湊在一起。我們現在知道的東西比一開始多得多，但還有一些東西沒有找到。在這個謎題的中心有一個很大的漏洞，使人難以看到其模式。問題在於，目前為止，我們見過的所有學習算法，需要一位老師來告訴它們正確答案。它們不會從健康細胞中區分出癌細胞，除非有人將這些細胞標記為“癌細胞”或者“健康細胞”。人類會無師自通，從出生那天開始，就已經這麽做了。正如《指環王》中站在魔多大門的弗羅多那樣，如果無法在這個障礙附近找到出路，那麽我們的長途旅行將毫無意義。有一條路可以穿越壁壘和層層守衛，勝利越來越近。跟我來……