你是理性主義者還是經驗主義者？
理性主義者認為，感官會欺騙人，而邏輯推理是通往知識的唯一可靠的道路。經驗主義者認為所有推理都是不可靠的，知識必須來源於觀察及實驗。法國人是理性主義者，盎格魯–撒克遜人（法國人就這樣稱呼他們）是經驗主義者。評論員、律師、數學家是理性主義者，記者、醫生、科學家是經驗主義者。《女作家與謀殺案》是關於犯罪的電視劇，屬於理性主義，《犯罪現場調查》則屬於經驗主義。在計算機科學領域，理論家和知識工程師屬於理性主義者，黑客和計算機學習者屬於經驗主義者。
理性主義者喜歡在邁出第一步前，就提前規劃好一切。經驗主義者喜歡嘗試新事物，然後看看結果會怎樣。我不知道理性主義和經驗主義是否都有專門的基因，但我看了看自己的計算機科學家同事，經過反覆觀察，發現理性主義者和經驗主義者的個性特點幾乎一樣：有些人以理性主義為核心，而且絕不會改變；其他人則是徹底的經驗主義者，未來也不會改變。這兩方可以彼此進行對話，而且有時候還可以利用彼此的定論，但他們對彼此瞭解僅限這麼多。實際上，每方都會認為對方做什麼並不重要，而且也沒什麼意思。
自從智人的黎明到來，理性主義和經驗主義也許就已經出現。在去狩獵之前，原始人鮑勃會花很長時間坐在洞裡，思考要去哪裡打獵。同時，穴居女人愛麗絲正在外面系統地調查領土。這兩種方法我們都還在使用，保守地說這兩種方法沒有哪個更好。你也許會認為，機器學習就是經驗主義最終勝利的產物，但我們很快會看到，真理總是比我們想的更加微妙。
理性主義與經驗主義是哲學家最熱衷討論的問題。柏拉圖是早期的理性主義者，而亞里士多德是早期的經驗主義者。關於這個問題的辯論，真正開始於啟蒙運動時期，每方有三位偉大的思想家：笛卡兒、斯賓諾莎、萊布尼茨是理性主義的代表，洛克、貝克萊、休謨則是經驗主義的代表。因為相信自己的推理能力，理性主義者編造出宇宙理論（委婉地說），這經不住時間的考驗，但他們也創造了基本的數學知識，比如微積分和解析幾何。經驗主義總體來說更為實際，而且它們隨處可見，從科學方法到美國憲法都有它們的身影。
大衛·休謨是最偉大的經驗主義者，以及有史以來最偉大、以英語為母語的哲學家。諸如亞當·斯密、查爾斯·達爾文之類的思想家都深受其影響。你也可以說他是符號學派的守護神。他1711年生於蘇格蘭，大半輩子都生活在18世紀的愛丁堡（一個思想活躍的繁榮城市）。他雖然性情溫和，卻是一個嚴格的懷疑論者，花了大半輩子來解開他那個時代的難題。為了得出符合邏輯的論斷，休謨借用了洛克開創的經驗主義思想，並提出一個問題，這個問題在所有領域的知識中就像一把達摩克利斯之劍，從最瑣碎的領域到最先進的領域，都是一個時刻存在的問題：在概括我們見過的東西以及沒見過的東西時，怎樣才能做到合理？從某種意義上說，每種學習算法都在嘗試回答這個問題。
休謨的問題也正是我們開啟尋找終極算法之旅的開始。首先，我們會通過日常生活中的例子來解釋這個問題，並通過現在人人皆知的「天下沒有免費的午餐」這個定理來體現這個問題。然後我們會看到符號學者對休謨的回答。這把我們引向機器學習中最重要的問題：不真實存在的過擬合或幻覺模式。我們會看到符號學者如何解決它。機器學習本質上是一種煉金術，在魔法石的輔助下把數據變成知識。對於符號學者來說，魔法石就是知識。在接下來的4章中，我們還會研究其他學派的「煉金術」。
約不約
你有一個很喜歡的朋友，想找她出來約會。如果遭到拒絕，你會很難過，但是如果你想知道她會不會答應，也只能去問她。現在是週五傍晚，你拿著手機坐在那裡考慮要不要給她打電話。你記得上次你問過她，但她拒絕了。但是為什麼上次的前兩次你約她，她都答應了，而這兩次的前一次她卻拒絕了？可能有時候只是她不想出門？也可能她喜歡泡吧而不喜歡吃飯？為了理出頭緒，你先放下了手機，寫下了前幾次的情況（見表3–1）。
表3–1 約會記錄
那麼答案是什麼？答應還是不答應？有沒有什麼模型可以區分肯定和否定？更重要的是，這個模型會如何決定今天的情況？
很明顯，沒有哪個因素可以單獨準確預測出答案：有的週末她喜歡出去約會，而有的週末她卻不想出去；有時她喜歡去泡吧，而有時她又不喜歡……把所有因素綜合起來會怎樣？可能週末她喜歡去泡吧？並不是，第四次約會就排除了這種情況，或者可能她只喜歡天氣暖和的週末晚上出去約會？是的！這個說法符合之前的情況！看了看外面寒冷的天氣，好像今晚不合適。可是等一下！電視不好看的晚上她會不會想去泡吧？好像這也符合前幾次的情況，也就是說今天可以約會！快，快點打給她，不然就遲了。再等等。你怎麼知道這是對的模型？你已經找到兩種情況和之前的情況相符，但這兩次的預測都是否定。細想一下，如果她只想天氣好的時候去泡吧，那怎麼辦？或者她只是在沒什麼電視好看時的週末才會出去？或者……
這時，你灰心地把畫好的表揉成一團，丟到垃圾桶裡。沒有辦法知道她會不會答應！你能做什麼？休謨的靈魂傷心地在你的肩膀上點頭。你沒有任何依據選擇這個而不是另外一個。對於「她會說什麼」這個問題，回答「是」或「否」的可能性都一樣。時鐘嘀嗒作響，最後你準備拋硬幣來決定。
你不是唯一身處窘境的人——我們都是。我們才開始尋找終極算法之旅，似乎就已經遇到無法克服的困難了。有沒有什麼辦法可以從過去的經歷中掌握規律，然後信心滿滿地運用到未來的事情中？如果沒有，那麼機器學習不就是一個沒有希望的事業了嗎？就此而言，所有學科甚至所有人類的知識，不就隨時可能會被推翻嗎？
這種情況不是大數據能解決的問題。你可以像卡薩諾瓦那樣放蕩，有無數個可以約會數幾千次的女人，但你的主數據庫還是不知道這次這個女人會說什麼。即使今天和前幾次她答應約會的情況一樣（都是週末、一樣的約會方式、一樣的天氣、一樣的電視節目），這也並不意味著這次她會答應你出去約會。正如你所知道的那樣，她的回答由一些你不知道或者無法知道的原因決定。也或者她的回答沒有什麼別的原因，只是隨口回答，而你也只是白費力氣地從之前的情況中找規律。
自休謨提出歸納問題，哲學家就已經對此進行辯論，但還沒有人能給出一個滿意的答案。伯特蘭·羅素喜歡用「歸納主義者火雞」這個故事來闡述這個問題。故事的主人公是一隻火雞，它來到農場的第一個早晨，主人在早上9點餵它們，但作為實實在在的歸納法優越論者，它不想過早下結論：主人每天都9點餵它們。首先它在不同情況下觀察了很多天，收集了許多觀察數據。主人連續多天都是9點餵它們，最終它得出結論，認為主人每天早上9點喂火雞，那麼主人一直會在早上9點給它餵食。接下來是平安夜那天的早晨，主人沒有餵它，因為它被宰了。
如果休謨問題僅僅是一個我們可以忽略的哲學小難題，就太好了，但事實並非如此。例如，谷歌的業務就是在你往搜索框輸入一些關鍵字時，猜測你在尋找哪些網頁。過去搜索查詢的人所輸入關鍵字的大量記錄，以及他們點擊的、相應查詢結果頁面的鏈接，都是谷歌的重要資產。如果某個人輸入一組關鍵字，而這些關鍵字卻不在記錄裡面，你該怎麼辦？即便關鍵字在記錄中，你怎麼能肯定當前用戶想要的搜索結果和之前的一樣？
如果我們只是假設未來和昨天一樣，那麼會怎樣呢？這當然是一個有風險的假設（這對歸納主義者火雞就不會奏效）。另外，沒有這樣的假設，所有知識將不復存在，生活也是如此。雖然有很多不確定性，但我們還是寧可活下來。遺憾的是，雖然有那樣的假設，但我們還是尚未走出困境。這個假設還得應付這些「微不足道的」例子：如果我是一名醫生，患者B和患者A有一模一樣的症狀，我假設兩人的診斷結果都一樣。但如果患者B的症狀和其他人都不一樣，我就仍然不知道如何做診斷。這屬於機器學習問題：將某結果推廣到我們沒有見過的事件中。
也許這也不是什麼大問題？有了足夠的數據，大多數事件不就變得「微不足道」了嗎？不是的。我們在前面的章節中瞭解到，為什麼記憶不能當作通用學習算法，我們現在可以用更量化的方式來解釋這個問題。假設你現在有一個數據庫，含有1萬億條記錄，每條記錄有1000個布爾字段（也就是說，每個字段回答一個是或否的問題）。這個數據庫真的好大。你認為有多少種可能的事件？往下讀之前好好猜一猜。每個問題可能的答案有兩個，兩個問題就是2乘以2（是—是、是—否、否—是、否—否），三個問題就是2的三次方（2×2×2=23），如果是1000個問題，就是2的1000次方（21000）。你的數據庫中1萬億條記錄，可能性就是分子是1、分母是無限大的數乘以1%，然後再乘以21000，「分子是1、分母是無限大的數」指的是「小數點前是0，小數點後是286個0，後面跟著1的小數」。結果就是：無論有多少數據——多少兆、多少千兆、多少千兆兆、多少澤或多少堯字節，你基本上什麼也看不到。你要決定的新事件已經存在於數據庫中，而數據庫非常大，這件事發生的概率低到可以忽略，所以如果不進行一般化，對你就不會有任何幫助。
如果這些聽起來有點抽像，那麼假設你是一個郵件服務提供商，要將每封收到的郵件進行分類，分為垃圾郵件或非垃圾郵件。你也許有一個包含1萬億封過去郵件的數據庫，而且每封郵件都已經被分為垃圾郵件或非垃圾郵件，但那樣做並不會讓你省事，因為每封新郵件和之前郵件一模一樣的概率幾乎是0。你沒有選擇，只能以大概的概率來區分垃圾郵件和非垃圾郵件，而根據休謨的觀點，這根本做不到。
「天下沒有免費的午餐」定理
休謨提出爆炸性問題之後的250年，大衛·沃爾珀特（David Wolpert）賦予了這個問題優雅的數學形式。沃爾珀特原來是一名物理學家，後來成為機器學習者。他的研究結果被人們稱為「天下沒有免費的午餐」定理，規定「怎樣才算是好的學習算法」。這個規定要求很低：沒有哪個學習算法可以比得上隨意猜測。好吧，那我們就不用找終極算法，可以回家了：終極算法只是用拋硬幣來做決定的算法。說真的，如果沒有哪個學習算法可以比拋硬幣更管用，那會怎樣？而且如果真的是那樣，為什麼這個世界——從垃圾郵件過濾（隨時都在進行）到自動駕駛汽車——到處都是非常成功的學習算法呢？
「天下沒有免費的午餐」這個定理和帕斯卡爾賭注失敗的原因非常相似。帕斯卡爾的《思想錄》於1669年出版，他在書中提到我們應該相信基督教中的神，因為如果神存在，他就會給我們永生，而如果他不存在，我們的損失也很小。這在當時是非常複雜的論點，但正如狄德羅指出的那樣，伊瑪目也可以同樣的理由讓人們來相信真主安拉的存在。如果你選錯了要信的神，代價就是永世在地獄。總而言之，在考慮各種各樣可能相信的神時，選擇特定的神來信仰，還不如選擇其他的神。因為，有說「這樣做」的神，也會有說「不，那樣做」的神。你也許應該把神忘了，好好享受沒有宗教限制的生活。
用「學習算法」來代替「神」，用「準確的預測」來代替「永生」，你就遵守「天下沒有免費的午餐」這個定理了。選擇你最喜歡的學習算法（在本書中你會看到很多算法）。如果存在學習算法比隨機猜測好用的領域，我（一個喜歡唱反調的人）會構建一個學習算法沒有隨機猜測好用的領域。我要做的就是把所有「未知」例子的標籤翻過來。因為「經過觀察」的標籤表明，你的學習算法絕無可能區分世界和反物質世界。在這兩個世界中的平均表現，學習算法和隨機猜測一樣好用。因此，在所有可能的世界中，把每個世界與其反物質世界配對，你的學習算法的作用就和拋硬幣的作用一樣。
雖然如此，別馬上就對機器學習或終極算法失望。我們不關心所有可能存在的世界，而只關心我們生存的這個世界。如果我們對這個世界有所瞭解，然後把瞭解的知識輸入我們的學習算法，那麼現在和隨機猜測相比，學習算法就可以發揮優勢了。休謨可能會回應說，知識本身必須由歸納得來，因此知識也是有問題的。沒錯，雖然知識是通過進化編入我們的大腦的，但我們不得不冒這個險。我們也可以這樣問，有沒有小部分毋庸置疑、非常基礎的寶貴知識，讓我們可以在其基礎上進行所有歸納（有點像笛卡兒的「我思故我在」，雖然很難明白，如何將這句話輸入學習算法中）。我覺得回答是肯定的，在第九章，我們就會知道那些寶貴的知識是什麼。
同時，「天下沒有免費的午餐」這個實際的結論表明，不靠知識進行學習，這樣的事不存在。只有數字也不夠。從零開始只會讓你一無所獲。機器學習就像知識泵，我們可以用它來從數據中提取大量的知識，但首先我們得先對泵進行預設。
數學家認為機器學習這個問題是一個不適定問題（ill–posed problem）：這個問題沒有唯一解。下面是一個簡單的不適定問題：哪兩個數相加的得數是1000？假設這兩個數都是正數，答案就有500種……1和999，2和998等等。解決不適定問題的唯一辦法就是引入附加假設。如果我告訴你，第二個數是第一個數的三倍，那麼答案就是250和750。
湯姆·米切爾（Tom Mitchell）是典型的符號學者，稱機器學習體現「無偏見學習的無用性」。在日常生活中，「偏見」是一個貶義詞：預設觀念不太好。但在機器學習中，預設觀念是必不可少的；沒有這些觀念，你就無法進行學習。實際上，預設觀念對人類認知來說，也是必不可少的，這些觀念是「直線布入」人腦的。對於它們，我們也覺得是理所當然的。超出那些觀念的偏見才值得質疑。
亞里士多德曾經說過，在知識領域，沒有什麼東西不是首先憑借感覺來形成的。萊布尼茨又加了一句，「除了知識本身」。人類的大腦不是一張白紙，因為它不是一塊石板。石板是被動的，你可以在上面寫東西，但大腦可以主動處理它接收到的東西。記憶就是大腦用來寫東西的石板，而且記憶不是一開始就是空白的。另一方面，計算機在你給它編程之前，就是一張白紙；在用計算機做事之前，這個積極的過程需寫入記憶。我們的目標是找到最簡單的、我們能編寫的程序，這樣寫好的程序就可以無限制地通過閱讀數據來自行編程，直到該程序掌握所有能掌握的知識。
機器學習不可避免地含有投機的因素。在《警探哈里》（第一集）中，克林特·伊斯特伍德追逐一名銀行搶劫犯，同時不斷向他開槍。最後，搶劫犯躺在一把裝有子彈的槍旁邊，不確定要不要把它拿起來。哈里開了6槍還是只開了5槍？哈里同情地說（可以這麼說）：「你得問自己一個問題：『我足夠走運嗎？』你真的走運嗎，小子？」這也是機器學習算法每天運作時必須問自己的問題：「今天我幸運嗎？」就像進化的過程一樣，機器學習不是時時刻刻都知道自己是否可以準確無誤地運行。實際上，誤差是常有的事，並不意外。但沒關係，因為我們放棄誤差的部分，主要靠沒有誤差的部分，而計算結果才是最重要的。我們一旦掌握新的知識，基於前面的步驟，就可以得出更多的知識。唯一的問題就是，從哪裡開始。
對知識泵進行預設
在《自然哲學的數學原理》一書及三大運動定律中，牛頓闡述了推理的四條法則。雖然這些法則沒有那些物理定律那麼著名，但可以說很重要。其中第三條是關鍵法則，我們可以這樣表述：
我們見過的所有真實的東西，在宇宙中也是真實的。
可以毫不誇張地說，這句聽起來無傷大雅的話就是牛頓革命以及現代科學的核心。開普勒定律適用於6個實體：那個年代太陽系中已知的6顆行星。牛頓定律適用於宇宙中的每一個微粒。這兩個定律之間的共性如此之大，讓人感到吃驚，而這也是牛頓法則的直接結果。這個法則本身就是擁有非凡動力的知識泵。沒有這個法則，也就沒有什麼自然法則，有的也只是永遠無法完整的、小規律的集合體。
牛頓法則是機器學習的第一個不成文規則。我們歸納自己能力範圍內、應用最廣泛的規則，只有在數據的迫使下，才縮小規則的應用範圍。乍一看，這看起來可能過於自信甚至近乎荒謬，但這種做法已經為科學服務了300餘年。當然也可以想像出一個變化無常的宇宙，在那裡牛頓法則不起作用，但那並不是我們的宇宙。
然而，牛頓法則僅僅是第一步。還得弄明白我們見到的哪些是真實的——如何從原始數據中找出規律。標準的解決方法就是假設我們知道真理的形式，而算法的任務就是把這個形式具體化。例如，在之前提到的約會問題中，你可以假設你朋友的回復由單個因素來決定。在這種情況下，算法就只包括看看每個已知的因素（時間、約會方式、天氣、晚間電視節目），確定該因素是否每次都能準確預測她的回答。可問題就在於，每個因素都無法預測她的回答！你打賭了，然後輸了。所以你把假設放寬了一點。如果你朋友的回答是由兩個因素一起決定的呢？總共四個因素，每個因素有兩種可能的值，那麼總共有24種可能（總共有6對因素組合，即12乘以因素的兩種可能）。數字太多，我們遇到尷尬：兩個因素的四種組合準確預測了結果！接下來怎麼辦？如果你覺得運氣還行，可以選其中的一種，然後祈禱最好的結果。但更明智的選擇是採取民主的做法：對每個選項進行選擇，然後選最後贏的預測。
如果所有兩個因素組合的預測都失敗了，你可以嘗試任意個數因素的組合，機器學習者和心理學家稱之為「合取概念」（conjunctive concept）。字典對詞的定義就屬於合取概念：椅子是有靠背、若干條腿的坐具。把任意一個描述去掉，就不再是椅子。托爾斯泰在寫《安娜·卡列尼娜》的開篇時，出現在他腦海裡的就是合取概念：「所有幸福的家庭都是相似的，每個不幸的家庭各有各的不幸。」對於個人來說，也是這樣的。為了感到幸福，你需要健康、愛、朋友、錢、你喜歡的工作等。把這些東西的任意一個拿走，痛苦也會隨之而來。
在機器學習中，概念性的例子成為正面例子，而與概念例子相反的則是負面例子。如果你在嘗試通過圖片來認出貓，那麼貓的圖片就是正面例子，而狗的圖片則是負面例子。如果你對世界文學中描述的家庭進行匯總，並編成數據庫，那麼卡列尼娜一家就是幸福家庭的負面例子，而且正面例子寥寥無幾。
首先做有條件的假設，如果這樣無法解釋數據，再放鬆假設的條件，這就是典型的機器學習。這個過程通常由算法自行進行，不需要你的幫助。首先，算法會嘗試所有單一因素，然後嘗試所有兩個因素的組合，之後就是所有三個因素的組合等。但現在我們遇到一個問題：合取概念太多，沒有足夠的時間對其逐個嘗試。
約會的例子有點欺騙性，因為它太小（4個變量，4個例子）。但假設你提供在線約會服務，你就需要知道要對哪些人進行配對。如果你的每個會員都填寫了一份問卷，問卷包含50個「是或否」的問題，這樣就有100種特點，這100種特點涵蓋了每對可能配對成功的情侶的特點，每對情侶中的一方都有50個特點。這些情侶出去約會之後，會匯報結果，在此基礎上，你能找到「佳偶」這個定義的合取概念嗎？總共有3100種可能的定義（每個問題有三種選擇，分別為「是」、「否」、「與該品質無關」）。即使由世界上最快速的計算機來做這項工作，這些情侶也會老得去世了（你的公司也破產了）。等你計算出來，除非你走運，可以找出很短的一條關於「佳偶」的定義。規則太多，而時間太少，我們得做點更精明的事。
這裡有一種方法：暫且假設每個配對都合適，然後排除所有不含有某品質的搭配，對每種品質重複同樣的做法，然後選擇那個排除了最多不當搭配和最少適當搭配的選項。現在你的定義看起來就像「只有他開朗，這對才合適」。現在反過來試著把其他品質加進去，然後選擇那個排除了剩下最多的不當搭配和剩下最少的適當搭配的選項。現在的定義可能是「只有他和她都開朗，這對才合適」。然後試著往那兩個特點裡加入第三個品質，以此類推。一旦排除了所有不合適的搭配，你就成功了：就有了這個概念的定義，這個概念排除了所有的正面例子和所有的負面例子。例如，「每對中的兩個人都開朗，這對才合適，他愛狗，而她不愛貓」。現在你可以丟掉所有數據，然後只把這個定義留下，因為這個定義概括了所有和你的目標相關的東西。這個算法保證能在合理的時間內完成運算，而這也是我們在本書中見過的第一個真實的學習算法。
如何征服世界
雖然合取概念的用途有很多，但並不能讓你走很遠。正如魯德亞德·吉卜林說的那樣，問題在於「編部落歌謠的方法有很多種，而每種方法都是正確的」。真正的概念是分離的。椅子可能有四條腿或三條腿，而有些則一條也沒有。你可以以無數種方法來贏一盤棋。包含「偉哥」這個詞的郵件有可能是垃圾郵件，但包含「免費」一詞的郵件也有可能是垃圾郵件。此外，所有規則都會有例外。所有的鳥都會飛，除了企鵝、鴕鳥、食火雞或者幾維鳥（或斷了翅膀的鳥，或被鎖在籠子裡的鳥）。
我們要做的就是學習經過一系列規則定義的概念，而不僅僅是單個規則，例如：
如果你喜歡《星球大戰》第四至六部，那麼你會喜歡《阿凡達》。
如果你喜歡《星際迷航：下一代》以及《泰坦尼克號》，那麼你會喜歡《阿凡達》。
如果你參加塞拉俱樂部，並閱讀科幻書籍，那麼你會喜歡《阿凡達》。
或者：
如果你的信用卡昨天在中國、加拿大以及尼日利亞被刷，那麼它被盜了。
如果某工作日晚上11點，你的信用卡被刷，那麼它被盜了。
如果你的信用卡被用來購買一美元的汽油，那麼它被盜了。
如果你對最後一條規則有疑問，解釋如下：過去信用卡竊賊通常會用偷到的卡購買一美元的汽油，來看看在數據挖掘器識破其陰謀前，信用卡是否完好。
我們可以像學習這條規則那樣來同時學習多套規則，利用我們之前見過的算法來學習合取概念。我們學習每個規則之後，會排除該規則包含的正面例子，因此下一個規則會盡可能多地包含剩下的正面例子，以此類推，直到所有的例子都被包含在內。這是一個「分而治之」的例子，也是科學家的戰術手冊中最古老的策略。為了找到單個規則，我們也可以對算法進行改良，方法就是保留某數n的假設，不止一個數，然後在每個步驟中將這些數以所有可能的方法延伸開來，最後保留n的最佳結果。
通過該方法發現規則的創意來自理夏德·米哈爾斯基（Ryszard Michalski），他是波蘭的一位計算機科學家。米哈爾斯基的故鄉——卡爾魯茲之前曾屬於波蘭、俄羅斯、德國以及烏克蘭，這讓米哈爾斯基比多數人更能理解合取概念。1970年移民美國之後，他和湯姆·米切爾、傑米·卡博內爾一起創立了機器學習的符號學派。他個性傲慢，如果你在一場機器學習會議中做報告，那麼很有可能他會舉手指出你只是重新發現了他之前的舊觀點。
零售商喜歡一套套的規則，因為他們要決定該囤什麼貨。通常，他們會用比「分而治之」更為徹底的方法，也就是尋找所有能夠準確預測每個購買項的規則。沃爾瑪在該領域屬先驅，他們早期的發現之一就是，如果你買了紙尿片，那麼很有可能會買啤酒。為什麼？對此進行解釋的說法之一就是，媽媽讓爸爸去超市買紙尿片，出於情感補償，爸爸買了一箱啤酒。知道這一點，超市現在會把啤酒放在紙尿片旁邊，這樣啤酒就會賣得更好。不找規律，這樣的事就不會在沃爾瑪發生。「啤酒和紙尿片」的規則已經在數據挖掘領域取得傳奇式的地位（雖然會有人說，所謂的傳奇和城市多樣化有關）。不管怎樣，這和米哈爾斯基想像的數字電路設計問題還差得很遠。20世紀60年代，他開始考慮規則歸納問題。如果你發明了新的學習算法，你甚至無法想像這個算法能應用的所有地方。
我第一次直接體驗規則學習，是在申請信用卡的時候。那時我剛來到美國，開始接受研究生教育，銀行給我寄了一封信，說「很遺憾，您居住在該地址的時間還不足夠長，所以無歷史信用記錄，你的申請被拒絕了」。就在那時，我知道在機器學習領域有待研究的東西還很多。
在無知與幻覺之間
規則集在很大程度上比合取概念要有力得多。實際上，規則的力量如此之大，大到你可以用規則來代表任何概念，要找到原因則很難。如果你給我某個概念的完整例子，我只能將每個例子變成一個規則。這個規則規定了每個例子的所有屬性，而這些規則的集合就是該概念的定義。回到之前關於約會的例子，其中的一個規則是：現在是週末晚上，天氣暖和，沒有好看的電視節目，你提議去泡吧，她會說「沒問題」。表3–1只包含了幾個例子，但其實它有16種（2×2×2×2）可能，每個可能都會有「約」或者「不約」的結果，將每個正面例子以這樣的方法變成規則，我們就成功了。
規則集的力量是一把雙刃劍。從正面看，你知道自己總能找到和數據完美匹配的規則。但你還沒來得及開始覺得走運，就意識到自己很有可能會找到一個毫無意義的規則。記住「天下沒有免費的午餐」：沒有知識，你就無法進行學習。假設某概念能通過規則集來定義，相當於什麼也沒有假設。
無用規則集的一個例子就是，只包含了你看到的正面例子，除此之外，沒有其他的例子。這個規則集看起來100%準確，但那只是假象：它會預測每個新例子都是負面例子，然後把每個正面例子弄錯。如果正面例子總體上比負面例子多，這種做法的效果會比拋硬幣更糟糕。想像一下，郵件過濾器僅因為某封郵件和之前垃圾郵件一模一樣就將其過濾，這樣會有什麼後果？對分類好的數據進行學習很容易，這樣的數據看起來也很棒，但還不如沒有垃圾郵件過濾器。很遺憾，我們「分而治之」的算法有可能就像那樣對規則集進行簡單的學習。
在《博聞強識的富內斯》的故事中，豪爾赫·路易斯·博爾赫斯講述了和一位擁有完美記憶力的少年相遇的故事。擁有完美記憶力看起來非常幸運，但其實這是一個可怕的詛咒。富內斯能記住過去任意時刻天空中雲朵的形狀，但他沒有辦法理解，下午15:14看到的狗的側面和下午15:15看到的狗的正面，都是同一條狗。每次他在鏡子中看到自己的臉，都會感到驚訝不已。富內斯無法進行概括：對他來說，兩個事物，只有每個細節看起來都一致，才能說它們是一樣的。自由的規則算法和富內斯一樣，發揮不了作用。學習就意味著將細節遺忘，只記住重要部分。計算機就是最大的白癡專家：它們可以毫無差錯地將所有東西記住，但那不是我們想讓它們做的。
問題不限於記憶大量例子。每當算法在數據中找到現實世界中不存在的模型時，我們說它與數據過於擬合。過擬合問題是機器學習中的中心問題。在所有主題中，關於過擬合問題的論文最多。每個強大的學習算法，無論是符號學算法、聯結學算法，或者其他別的學習算法，都不得不擔憂幻覺模式這個問題。避免幻覺模式唯一安全的方法，就是嚴格限制算法學習的內容，例如要求學習內容是一個簡短的合取概念。很遺憾，這種做法就像把孩子和洗澡水一起倒掉一樣，會讓學習算法無法看到多數真實的模型，這些模型在數據中是可見的。因此，好的學習算法永遠在無知與幻覺的夾縫中行走。
人類對過擬合也沒有免疫。你甚至可以說，過擬合是我們的萬惡之源。想想一個白人小女孩，在商場看到拉美裔嬰兒時脫口而出「看，媽媽，那是小女傭」（真實例子）。小女孩並非生來就是偏執狂。那是因為在她短暫的人生閱歷裡，她對見過的僅僅幾個拉美裔女傭進行了籠統的概括。這個世界有許多從事其他職業的拉美裔，但她還沒有見過他們。我們的信仰建立在自己的經歷之上，這會讓我們對世界的理解不完整，而且也容易過早得出錯誤的結論。即便你很聰明，學識淵博，也無法免受過擬合的影響。亞里士多德說要使一個物體不斷運動，需要對其施加一個力，就犯了過擬合的錯誤。伽利略的天才之處在於，無須到外太空親眼見證，他憑直覺就知道，不受外力影響的物體會一直保持運動。
但學習算法特別容易過擬合，因為它們擁有從數據中發現模型、近乎無限制的能力。人類發現一個模型所用的時間，計算機可以找到數百萬個。在機器學習中，計算機最大的優勢（處理大量數據以及不知疲倦不斷重複同樣步驟的能力）也是它的劣質所在。如果你做的研究夠多，然後能有所發現，也很不錯。《聖經密碼》（1998年的暢銷書）聲稱如果你以固定間距跳過某些字母，然後把點中的字母拼起來，就會發現《聖經》對未來的預言。遺憾的是，保證你能從任何足夠長的文本中找到「預言」，有很多方法。懷疑論者會說，他們在《白鯨記》和最高法院的裁決中找到了預言，除此之外，還提到羅斯威爾，以及《聖經·創世紀》中的不明飛行物。約翰·馮·諾依曼（計算機科學的奠基之父之一）曾說過一句眾所周知的話：「用4個參數，我能擬合一頭大象；用5個參數，我可以讓它的鼻子扭動起來。」當今我們通常會學習擁有數百萬參數的模型，這些參數足以讓世界上的每頭大象都扭動鼻子。甚至曾有人說過，數據挖掘意味著「折磨數據，直到數據妥協」。
過擬合問題因為嘈雜的聲音被嚴重誇大。在機器學習中，這些噪聲僅僅意味著數據中的誤差，或者你無法預測的偶然事件。比如你的朋友在電視不好看的時候，真的想去泡吧，但你記錯第三次約會的情況，並寫著那天晚上的電視好看。如果你現在努力找出一套規則，為那天晚上破個例，這樣你可能最終會得到一個糟糕的答案，比忽略那個晚上得出的結果還糟。或者比如你的朋友前一晚剛出去喝醉了，所以今晚想休息，但如果是平時，她會答應出去約會。除非你知道她宿醉了，為了得出本例子的正確結果而掌握一套規則，其實會適得其反：你最好將第三次約會情況「錯誤分類」，以得出否定回答。這種情況更糟：誤差或偶然事件會讓你無法找出整套規律。仔細看，你會發現第二次約會和第三次約會其實難以區別：它們都有相同的屬性。如果你的朋友答應第二次邀請，而拒絕第三次邀請，那麼就沒有什麼規則能讓這兩次預測都準確。
當你有過多假設，而沒有足夠的數據將這些假設區分開來時，過擬合問題就發生了。壞消息是，即便對最簡單的合取概念算法來說，假設的數量也會隨著屬性的增多而呈指數級增長。指數級增長是一件恐怖的事。大腸桿菌每15分鐘就能大致分裂成兩個細菌，只要有足夠的營養，它可以在大約一天時間內，生長出大量細菌，和地球一樣大。當算法需要做的事情和輸入的數據一樣呈指數級增長時，計算機科學家就將這個現象稱為組合爆炸，然後會四處奔走尋求保護。在機器學習中，一個概念可能實例的數量，是其屬性數量的指數函數：如果屬性是布爾值，每種新的屬性可能會是實例數量的兩倍，方法就是引用之前的每個實例，然後為了那個新屬性，對該實例以「是」或「非」來進行擴展。反過來，可能概念的數量是可能實例數量的指數函數：既然每個概念都把實例分成正面或者負面，加入一個實例，可能的概念就會翻倍。因此，概念的數量就是屬性數量的指數函數的一個指數函數！換句話說，機器學習就是組合爆炸的組合爆炸。也許我們該放棄，不要把時間浪費在這樣沒有希望的問題上。
幸運的是，在學習過程中，會發生一些事，把其中一個指數消除，只剩下一個「普通的」單一指數難解型問題。假設你有一個袋子，裝滿概念的定義，每個定義寫在一張紙上，你隨機取出紙片，然後看看這個概念和數據的匹配程度。和連續拋1000次硬幣都是正面朝上的概率相比，一個不恰當的定義更沒有可能讓你的數據中所有1000個例子都準確無誤。「一把椅子有四條腿，而且是紅色的，或者有椅面但沒有椅腿」可能會和某些例子匹配，但並不是和你看到的所有椅子都匹配，也可能會和其他一些事物相匹配，但並不是和所有其他事物都匹配。因此，如果一個隨機定義準確匹配了1000個例子，那麼這個概念不太有可能是錯誤的定義，或者至少它和正確的定義非常接近。而且如果一個定義和100萬個例子相匹配，那麼實際上它就是正確的定義。其他的定義怎麼能使那麼多例子準確無誤？
當然，真正的學習算法不會只是從袋子裡隨機去除一個定義。這個算法會嘗試所有定義，而且這些定義也不是隨機選擇的。算法嘗試的定義越多，越有可能偶然得到能夠和所有例子匹配的定義。如果你每組拋1000次硬幣，然後重複100萬組，實際上至少會有一組出現1000次硬幣都是正面朝上的情況，而100萬也僅僅是假設的一個小數目。例如，如果例子只有13個屬性，那大概就是可能的合取概念的數目（注意你不需要明確地嘗試一個又一個概念，如果你找到的最好的那個概念利用了合取概念學習算法，並且和所有的例子匹配，效果也是一樣的）。
總結：學習就是你擁有的數據的數量和你所做假設數量之間的較量。更多的數據會呈指數級地減少能夠成立的假設數量，但如果一開始就做很多假設，最後你可能還會留下一些無法成立的假設。一般來說，如果學習算法只做了一個指數數量的假設（例如，所有可能的合取概念），那麼該數據的指數報酬會將其取消，你毫無影響，只要你有許多例子，且屬性不太多。另外，如果算法做了一個雙指數的假設（例如，所有可能的規則集），那麼數據只會取消其中的一個指數，而且你仍會處於麻煩之中。你甚至可以提前弄明白自己需要多少例子，這是為了保證算法選擇的假設和準確的那個非常接近，只要它對所有數據都擬合。換句話說，是為了假設能夠盡可能準確。哈佛大學的萊斯利·瓦利安特獲得了圖靈獎（計算機科學領域的諾貝爾獎），因為他發明了這種分析方法，他在自己的書中將這種方法取名為「可能近似正確」（probably approximately correct），非常恰當。
你能信任的準確度
在實踐中，瓦利安特式的分析方法往往非常被動，而且需要的數據比你擁有的還要多。那麼你怎麼決定，是否要相信學習算法告訴你的東西呢？這個很簡單：在利用學習算法過去看不到的數據對其進行證實之前，你不要相信任何東西。如果學習算法假設的模型對新數據來說也適用，你就可以很有信心地說那些模型是正確的，否則你知道學習算法過擬合了。這僅僅是應用於機器學習中的科學方法：對一個新理論來說，這不足以用來解釋過去的證據，因為捏造一個能做到這些的理論非常容易。理論還必須做出新的預測，而且只有這些預測經過實驗驗證後，你才接受它們（即使那樣，也只是暫時的，因為未來的證據會對其進行證偽）。
愛因斯坦的廣義相對論也只是在亞瑟·愛丁頓對其證實之後才廣泛被人們接受。愛丁頓以經驗為主，證實廣義相對論的預測是對的，預測表明太陽使來自遙遠星球的光線變彎了。但是你也不必等待新數據的到來，以決定能否信任學習算法。你可以利用自己擁有的數據，將其分成一個訓練集和一個測試集，然後前者交給學習算法，把後者隱藏起來不讓學習算法發現，用來驗證其準確度。留存數據的準確度就是機器學習中的「黃金標準」。你可以寫一篇關於你發明的偉大的新型學習算法的文章，但如果你的算法的留存數據不如之前的算法的留存數據準確，那麼這篇文章也沒有什麼出版價值。
此前不可見數據的準確度測試確實是一個相當嚴格的考驗，實際上，科學的很多方面都因此沒有經得住考驗。這並不意味著科學就沒有用了，因為科學不僅僅是用來預測的，還能用來解釋和理解。但是最後，你的模型如果無法對新的數據做出準確預測，就無法保證自己真的理解或者解釋了隱藏在背後的現象。對於機器學習來說，對不可見數據的測試是必不可少的，因為這是判斷學習算法是否過擬合的唯一方法。
即使測試集準確度也會出問題。據說，在早期軍事應用中，一種簡單的學習算法探測到坦克的訓練集和測試集的準確度都為100%，兩個集都由100張圖片組成。驚訝？還是懷疑？結果是這樣的——所有有坦克的圖片都比沒有坦克的圖片亮，所以學習算法就都挑了較亮的圖片。目前我們有更大的數據集，但並不意味數據收集的質量會更好，所以得當心。在機器學習從新生領域成長為成熟領域的過程中，務實的經驗評價會起到重要的作用。追溯至20世紀80年代，每個學派的研究人員很多時候都相信自己華而不實的理論，假裝自己的研究範式從根本上說是更好的，所以與其他學派的交流也很少。雷·穆尼、裘德·沙弗裡克等符號學者開始系統地對不同算法的相同數據集進行比較，令人驚訝的是，真正的贏家還沒有出現。如今競爭在繼續，但「異花授粉」的情況也很多。利用加州大學歐文分校的機器學習小組維護的普通實驗框架和大型數據集存儲庫，我們會取得重大進步。而且正如我們看到的，創造通用學習算法的最大希望在於綜合不同研究範式的觀點。
當然，知道你何時過擬合這一點還不足夠，我們需要第一時間避免過擬合。這就意味著不再對數據進行完全擬合，即便我們能做到。有一個方法就是運用統計顯著性檢驗來確保我們看到的模型真實可靠。例如，擁有300個正面例子、100個反面例子的規則，和擁有3個正面例子、1個負面例子的規則一樣，它們訓練數據的準確率都達到75%，但第一個規則幾乎可以肯定比拋硬幣好用，而第二個則不然，因為拋4次硬幣，可以很容易得出3次正面朝上。在構建規則時，如果某一時刻無法找到能提高該規則準確度的條件，那麼我們只能停下，即便它還包括一些負面例子。這樣做會降低規則的訓練集準確度，也可能讓它變成一個更能準確概括的規則，這是我們關心的。
雖然如此，我們還沒有大功告成。如果我嘗試了一條規則，400個例子中的準確率是75%，可能會相信這個規則。但如果我嘗試了100萬條規則，其中最佳的規則中，400個例子中的準確率是75%，可能就不會相信這個規則，因為這很有可能是偶然發生的。這也是你在挑共同基金時遇到的問題。Clairvoyant基金連續10年獲得高於市場平均水平的收益。哇！這個基金的經理一定是個天才，不是嗎？如果你有1000種基金可以選擇，很有可能你選的那個會比Clairvoyant基金的收益還要高，即使那些基金都由玩飛鏢的猴子秘密經營。科學文獻也被這個問題困擾著。顯著性檢驗是決定一項研究結果是否值得出版的「黃金標準」，但如果幾個組找一個結果，而只有一個組找到了，那麼很有可能它並沒有找到。雖然你閱讀他們看起來很可靠的文章，但是絕不會猜到那樣的結果。有一個解決方法：出版有肯定結果的文章，同時發表有否定結果的文章，那樣你就會知道所有嘗試失敗的例子，但這種做法沒有流行起來。在機器學習中，我們可以把自己嘗試了多少條規則記錄下來，然後相應地調整顯著性檢驗，不過那樣做，這些檢驗可能會把可靠的規則連同不可靠的一起丟棄。更好的方法就是認識到有些錯誤的假設會不可避免成立，但要控制它們的數量，方法就是否定低顯著性的假設，然後對剩下的假設做進一步的數據檢測。
另外一個流行的方法就是選擇更加簡單的假設。「分而治之」算法會含蓄地選擇更簡單的規則，因為它在一出現只有正面例子的情況時，就會停止添加條件；在一出現包含所有正面例子的情況時，就會停止添加規則。但為了和過擬合做鬥爭，我們要對更簡單的規則有更強的偏好，這樣就能在所有負面例子被包含之前，就停止添加條件。例如，我們可以稍微降低規則的準確度，來縮短規則的長度，然後把這種做法當作一個測評指標。
對較簡單假設的偏好就是眾人皆知的奧卡姆剃刀原理（Ocam』s razor），但在機器學習背景下，這有點誤導性。「如無必要，勿增實體」，因為剃刀常常會被替換，僅意味著挑選能夠擬合數據的最簡原理。奧卡姆可能對這樣的想法感到迷惑，也就是我們會偏向那些不那麼能完整解釋論據的理論，因為這個理論的概括性更好。簡單的理論更受歡迎，因為它們對於我們來說，花費的認知成本更低；對於我們的算法來說，花費的計算成本更低，這不是因為我們想讓這些理論更準確。相反，即使是我們最複雜的模型，也往往是在事實過分簡化之後得到的。甚至在那些能夠完美擬合數據的理論中，我們由「天下沒有免費的午餐」這個定理，知道沒有什麼能夠保證最簡單的理論最擅長概括，而實際上，有些最佳的學習算法，比如推進和支持向量機，能瞭解那些看起來過於複雜的模型（在第七章和第九章中我們會瞭解它們為什麼有這樣的功能）。
如果你的學習算法檢測集準確度不盡如人意，你就得診斷問題在哪裡。是因為無知，還是因為幻想？在機器學習中，這些的專業叫法為「偏差」和「方差」。某座鐘如果總是慢一個小時，那麼它的偏差會很高，但方差會很低。但如果這座鐘走得時快時慢，最後平均下來准點了，那麼它的方差會很高，但偏差會很低。假設你和一些朋友在酒吧喝酒、玩飛鏢。他們不知道你已經練了多年飛鏢，所以非常熟練。你的所有飛鏢都打到靶心，你的偏差和方差都很低，效果圖3–1c所示。
圖3–1
你的朋友本也玩得很好，但他喝得有點多。他的鏢射完了，他大聲說，平均下來是他射中了靶心（也許他本該是一位統計學家）。這是低偏差、高方差的例子，如圖3–1d所示。本的女朋友艾希莉射得很穩，但射的時候過於偏向右上角。她的方差低，但偏差高（見圖3–1a）。科迪，從外地來，從來沒有玩過飛鏢，射的鏢都位於中心上方，偏離中心，他的偏差和方差都高（見圖3–1b）。
你可以估算一種學習算法的偏差和方差，方法就是在掌握訓練集的隨機變量之後，對算法的預測進行對比。如果算法一直出錯，那麼問題就出在偏差上，而你需要一個更為靈活的學習算法（或者只和原來的不一樣即可）。如果出現的錯誤無模式可循，問題就出在方差上，而你要麼嘗試一種不那麼靈活的學習算法，要麼獲取更多的數據。大多數學習算法都有一個「把手」，通過旋轉「把手」，你可以調節這些算法的靈活度，例如，顯著性檢驗的界限值，或者對於模型規模的懲罰方式。扭動「把手」是你嘗試的第一個方法。
歸納是逆向的演繹
更深層的問題是，多數學習算法開始時掌握的東西很少，即使轉再多「把手」，也沒法讓這些算法到達終點。沒有成年人大腦中所儲存知識的指導，這些算法很容易誤入歧途。雖然多數學習算法會誤入歧途，但只是假設你明白真理的形式（例如，那是一小組規則），還不足以達到令人震驚的程度。嚴格的經驗主義者會說，開始時知之甚少，這是所有新生兒都有的特點，因為這個特點深深存在於其大腦結構中，而孩子確實會比成人更容易犯過擬合的錯誤，但我們想學得比孩子快（18年是很長的一段時間，而且還沒把大學教育時間計算在內）。主算法應該能以大量的知識作為啟動（無論這些知識由人類來提供，還是之前已經掌握），然後在對數據做出新概括時，用到這些知識。這就是科學家做的工作，這相當於從零開始做。「分而治之」原則的歸納算法做不到這一點，但還有別的掌握規則的方法能做到。
問題的關鍵在於認識到，歸納僅僅是逆向演繹，就和減法是加法的逆運算，或者積分是微分的逆運算一樣。這個觀點由威廉姆·斯坦利·傑文斯於19世紀末首次提出。史蒂夫·馬格爾頓和雷·邦坦（一個英國—澳大利亞研究組）在此基礎上於1988年設計出第一個實用算法。在數學這個學科中，通過已知條件進行運算，得出其逆向結果的方法已經有一段傳奇的歷史。把這種方法運用到加法當中就有了整數，因為如果沒有負數，加法就不可逆了（3-4=-1）。同樣，將其用到乘法中就有了有理數，而將其運用到平方運算中就有了複數。讓我們來看看能否將這種方法運用到演繹中。演繹推理的一個典型例子就是：
蘇格拉底是人類。
所有人類都會死。
所以……
第一個句子是關於蘇格拉底的事實，第二個是關於人類的一般規則。接下來的推理是怎樣的？蘇格拉底當然也會死，這是將一般規則用到蘇格拉底身上得出的。相反，我們在歸納推理中會以最初事實和衍生事實作為開始，然後找一個規則，讓我們由前者推出後者：
蘇格拉底是人類。
……
所以蘇格拉底也會死。
有這樣一個規則：如果蘇格拉底是人類，那麼他就會死。這句話完成了推理，但並不是很有用，因為這是專門針對蘇格拉底的規則。但現在我們應用牛頓定律，然後將該定律推廣到所有實體當中：如果某實體是人類，那麼它就會死。或者更簡潔些：所有人類都會死。當然，僅通過蘇格拉底就歸納出該規則過於草率，但對於其他人類，我們知道相似的事實：
柏拉圖是人類，他會死。
亞里士多德是人類，他會死。
以此類推……
對於每個事實，我們構建這樣的規則，讓我們由第一個事實推出第二個事實，然後通過牛頓定律將其推廣。當同一條通用規則一次又一次被歸納出來時，我們有信心說那條規則說的是真的。
到目前為止，我們還沒有做任何「分而治之」算法無法做到的事。可是，如果我們不知道蘇格拉底、柏拉圖、亞里士多德是人類，只知道他們是哲學家，那會怎樣？我們仍會得出結論，說他們也會死，因為之前我們就歸納過或者別人告訴過我們，所有人都會死。這也是一種有效推廣（至少在我們解決人工智能問題，而機器人開始從事哲學研究之前是），而且這也在我們的推理中「填補了漏洞」：
蘇格拉底是哲學家。
所有哲學家都是人。
所有人都會死。
所以蘇格拉底會死。
我們也可以單純從其他規則中歸納另一些規則。如果我們知道所有哲學家都是人，而且會死，我們就可以歸納出所有人都會死（我們不會歸納出所有會死的都是人類，因為我們知道其他會死的動物，例如貓和狗。另一方面，科學家、藝術家等也是人類，也會死，因此這條規則得到加強）。通常，我們以越多的規則和事實作為開頭，也就有越多的機會運用「逆向演繹」歸納新的規則。我們歸納的規則越多，我們能歸納的規則也就越多。這是知識創造的良性循環，只受過擬合風險和計算成本的限制。可是在這裡，我們也有初始知識的協助：如果我們有很多小的而不是大的漏洞要修補，歸納的步驟就不會有那麼大的風險，所以過擬合的可能性也會降低（例如，給定相同數量的例子，「所有哲學家都是人類」這個歸納，就比「所有人都會死」這個歸納風險要小）。
逆運算往往比較困難，因為逆運算的結果不止一個。例如，一個整數有兩個平方根：一個正數，一個負數〔22=（–2）2=4〕。最為人所知的是，對一個函數的導數積分，只會將函數恢復為一個常數。函數的導數告訴我們該函數在每個點上下浮動的幅度。把所有幅度值加起來會重新得到函數，除非我們不知道它從哪裡開始變化。我們可以在不改變導數的情況下，上下「滑動」積分過的函數。為了簡便，我們可以假設附加常量為0，來「取締」函數。逆向演繹存在類似的問題，而牛頓定律就是一個解決方法。例如，我們由「所有希臘的哲學家都是人類」和「所有希臘哲學家都會死」可以歸納出「所有人類都會死」，或只能歸納出「所有希臘人都會死」。可是為什麼僅滿足於最保守的歸納？其實我們可以認為所有人都會死，直到遇到例外（據雷·庫茲韋爾說，這個意外很快就會出現）。
同時，逆向演繹的另外一個重要的應用，就是預測新研製的藥物是否有不良的副作用。動物測試及臨床試驗的失敗，成為研製新藥物需要花費多年、數十億美元的主要原因。通過歸納已知有毒分子的結構，我們可以得出規律，迅速清除明顯的有毒化合物，大大提高剩餘化合物的臨床試驗成功率。
掌握治癒癌症的方法
更廣泛地說，逆向演繹是在生物學中發現新知識的重要方法，這也是治癒癌症要邁出的第一步。根據中心法則的觀點，在活細胞中進行的任何活動都最終由細胞的基因控制，通過發起蛋白質的合成來完成。一個細胞就像一台微型計算機，而DNA就是計算機運行的程序：改變DNA，皮膚細胞就會變成神經元細胞，或者小鼠細胞會變成人類細胞。在計算機的程序中，所有的故障都是由程序員引起的。但在細胞中，故障可自行產生，比如當輻射或者細胞複製誤差將某基因變成另外一個基因時，當基因偶然被複製兩次時……很多時候，變異會導致細胞悄無聲息地死去，但有時候細胞開始生長，然後不可控制地分裂，這樣癌細胞就產生了。
治癒癌症意味著在不破壞完好細胞的情況下，阻止受損細胞的繁殖。這就需要知道完好細胞和受損細胞的區別在哪裡，特別是它們染色體組的區別在哪裡，因為其他所有的一切都依此進行。幸運的是，基因測序變得越來越普遍、越來越實惠。利用基因測序，我們可以預測哪種藥對哪種癌基因起作用。這和傳統的化學療法不一樣，化學療法對所有細胞的影響都一樣。掌握哪種藥物對哪種變異有效，這需要關於患者的數據庫、他們的癌基因、服用過的藥物以及藥效。最簡單的規則對基因與藥物之間一對一的對應關係進行編碼，例如，如果出現BCR–ABL基因，那麼服用格列衛這種藥物（BCR–ABL引發一種白血病，而格列衛在10個患者中能治癒9個患者）。一旦癌基因排序和治療結果核對達到標準管理，更多這樣的規則會被發現。
然而，這僅僅是一個開始。大多數癌症都會涉及各種混合的變異，或者只有靠某些藥物才能治癒，而這些藥物尚未被研發出來。下一步就是以更為複雜的條件來掌握規則，這涉及癌基因組、患者的基因組、病史、藥物的已知副作用等。但最終我們需要的，就是完整細胞運轉的模型，這讓我們在計算機上對特殊病人變異的影響、不同藥物組合的效果進行模仿，無論是真實存在的，還是猜想出來的，都進行模仿。我們構建此類模型的主要信息，主要源於DNA測序儀、基因表達微陣列以及生物學文獻。將這些結合起來，人們就會看到逆向演繹的作用。
亞當（我們在第一章中提到過的機器人科學家）就是一個例子。亞當的目標是弄明白酵母粉如何起作用。機器人以酵母遺傳學、新陳代謝的基本知識，以及一批酵母細胞的基因表達數據作為開端，運用逆向演繹來假設哪種基因會通過哪種蛋白質來表達，然後設計微陣列實驗來對其進行檢測，接著修正假設，最後重複以上步驟。是否每個基因都會表達出來，這取決於其他基因，以及所處的環境條件，由此產生的網絡交互可表達為一個規則集，例如：
如果溫度高，那麼基因A就會表達出來。
如果基因A表達出來，而基因B沒表達出來，則基因C表達出來。
如果基因C表達出來，那麼基因D不會表達出來。
如果我們知道的是第一條和第三條規則，不知道第二條，但我們有微陣列數據，數據顯示在高溫條件下，基因B和基因D無法表達，那麼我們就可以通過逆向演繹來歸納出第二條規則。一旦我們有了這條規則，而且也許利用微陣列實驗證實了這條規則，那麼我們就能用它作為進一步歸納推理的基礎。同理，我們也可以將化學反應的順序拼湊起來，因為蛋白質就是按照這些順序發揮作用的。
即便如此，僅僅知道哪些基因調節哪些基因，以及蛋白質如何組織化學反應中的細胞網絡還不夠。我們還需要知道，每種分子產生的量有多少。DNA微陣列和其他實驗能夠提供這種數量方面的信息，但逆向演繹，以其「非有即無」的邏輯特點，並不是很擅長處理這方面的事情。因此我們要用到聯結學派的方法，這會在下一章談到。
20問遊戲
逆向演繹的另外一個局限性就在於，它涉及很密集的計算，因此很難擴展到海量數據集中。因為這些原因，符號學家選擇的算法是決策樹歸納。決策樹可以當作此類問題的答案：如果有多個概念的規則對應一個實例，那怎麼辦？那麼我們怎麼知道實例對應哪個概念呢？如果看到一個部分封閉的物體，它有一個平面、四條腿，那麼我們怎麼知道它是一張桌子，還是一把椅子呢？有一個方法，就是對規則進行排序，例如以準確率遞減的順序來排列，然後選擇符合描述的第一條規則。另一個方法，就是讓規則自己選擇。決策樹通常會保證，每個實例會準確對應一條規則。也就是說，在一次及以上的屬性測試中，如果每對規則存在區別，這樣的規則集將被組織成一棵決策樹。例如，看看以下這些規則：
如果你支持削減稅收，反對墮胎，那麼你屬於共和黨。
如果你反對削減稅收，那麼你屬於民主黨。
如果你支持削減稅收，提倡墮胎合法，反對槍械管制，那麼你屬於獨立人士。
如果你支持削減稅收，提倡墮胎合法，支持槍械管制，那麼你屬於民主黨。
這些可以組成一些決策樹，如圖3–2所示。
圖3–2
決策樹的原理就像玩一個有實例的20問遊戲。從「根部」開始，每個節點都會問每個屬性的值，然後根據答案，我們沿著這個或另外一個分支繼續下去。當到達「樹葉」部分時，我們讀取預測的概念。從「根部」到「樹葉」的每條路線都對應一個規則。這讓人想起那些煩人的電話語音提示菜單，如果你撥打客戶服務電話，就得通過這些菜單，這些菜單與決策樹相似並非偶然——電話語音提示菜單就是一棵決策樹。電話線另一頭的計算機在和你玩20問遊戲，目的是弄明白你想要做什麼，每個選項就是一個問題。
根據以上決策樹，你要麼是共和黨人，要麼是民主黨人，要麼是獨立人士。你無法選擇其中的兩種或三種，或者一個都不選。擁有這個屬性的概念組被稱為類集，而預測類集的算法稱為分類器。單個概念隱含兩類定義：概念本身及其反面（例如，垃圾郵件和非垃圾郵件）。分類器是機器學習最為普遍的方式。
利用「分而治之」算法的一個變體，我們就可以掌握決策樹了。首先，我們選一個屬性，在決策樹的「根部」進行測試。然後我們關注每個分支上的例子，為那些例子選擇下一個測試（例如，我們看看支持削減稅收的人是否反對墮胎或者支持墮胎合法）。我們在歸納推理出的每個新節點上重複這個步驟，一直到分支上的所有例子都有同一個類別，此時我們就可以用該類別來命名該分支了。
有一個突出的問題，那就是如何挑選最佳屬性以便在節點處進行測試。準確度（準確預測例子的數量）並不能起到很好的作用，因為我們不是在嘗試預測某個特殊類別，而是在嘗試慢慢分離每個類別，直到每個分支都變得「純粹」。這使人想起信息論中熵的概念。一組對象的熵，就是用來衡量混亂度的單位。如果150人的組裡面有50個共和黨人、50個民主黨人、50個獨立人士，那麼這個組的政治熵會達到最大。另一方面，如果這個組全部是共和黨人，那麼熵就變成零（這就是黨派聯合的目的）。所以為了學習一棵好的決策樹的優點，我們在每個節點選擇這樣的屬性：在其所有分支中，產生的熵在平均值上屬性最低，取決於每個分支上有多少例子。
和規則學習一樣，我們不想歸納出一棵樹，可以準確地預測所有訓練例子的類別，因為這樣的樹很有可能會過擬合。和之前一樣，為了防止這樣的事情發生，我們可以利用顯著性檢驗或針對樹的大小設立懲罰制度。
如果屬性離散，屬性的每個值都有一個分支，這沒關係，但如果是數值屬性該怎麼辦？如果連續變量的每個值都有一個分支，決策樹將變得無限寬。一個簡單的方法就是通過熵來選擇幾個臨界值，然後使這些臨界值起作用。例如，患者的體溫是高於還是低於100華氏度？這個體溫數和其他症狀一起，也許是所有醫生都要知道的，通過體溫可以斷定患者是否感染疾病。
決策樹可應用在許多不同的領域。在機器學習領域，決策樹源於心理學方面的知識。厄爾·亨特及其同事於20世紀60年代利用了決策樹，目的是為了模擬人類如何掌握新的概念。另外，亨特其中的一個研究生羅斯·昆蘭後來嘗試把決策樹用於象棋中。他最初的目的是為了從棋盤佔位預測王車大戰騎士的後果。據調查，決策樹已經由一開始這些微不足道的用途，發展成為機器學習算法中應用最為廣泛的方法。要知道原因並不困難：決策樹易於理解，可以快速掌握，而且通常無須太多調整就可以做到準確無誤。昆蘭是符號學派中最卓越的研究者。作為一個沉穩、務實的澳大利亞人，因為對決策樹年復一年不斷地改進，並寫了和決策樹有關、邏輯清晰的論文，使決策樹成為分類活動中的「黃金標準」。
無論你想預測什麼，人們利用決策樹來預測的可能性會很大。微軟的Kinect利用決策樹，通過其深度相機的輸出信息，可以弄明白你身體的各個部位在哪裡，然後利用這些部位的動作來控制Xbox遊戲機。在2002年的一場正面交鋒中，決策樹準確預測了3/4的最高法院裁決，而一個專家小組的準確率卻不到60%。數千個決策樹使用者不可能會出錯，你仔細想想，然後畫一棵樹來預測朋友的答覆（如果你想約她出去的話）。如圖3–3所示。
圖3–3
根據這棵樹的結果，今晚她會答應你出去約會。深呼吸，拿起手機，撥通她的電話吧。
符號學派
符號學派的核心理念就是，所有和智力相關的工作都可以歸結為對符號的操縱。數學家在解方程時，會移動符號，然後根據預先定義的規則，用其他符號來代替這些符號。邏輯學家進行推論時也是同樣的道理。根據這個假設，智力是獨立於基質的。符號處理是通過寫在黑板上進行的，還是通過打開或關閉晶體管、放電神經元，或者玩玩積木就能完成的，這些都不重要。如果你能利用萬能圖靈機的力量來進行設置，那麼就能做任何事情。軟件可以和硬件清晰地分離。如果你關注的重點是想弄明白機器是怎樣學習的，你（謝天謝地）不用擔心後者無法在亞馬遜的雲服務上購買個人計算機或者自行車。
符號學機器學習者和許多其他計算機科學家、心理學家、哲學家一樣，都相信符號操縱的力量。心理學家大衛·馬爾稱，每個信息處理系統應該經過三個不同水平的研究：該系統解決所解決問題的基本屬性，用來解決問題的算法和表示方法，以及這些算法和表示方法如何實現。例如，加法可以由一組公理來定義，和加法如何進行無關；數字可以以不同方式進行表達（例如，羅馬數字和阿拉伯數字），還可以用不同算法進行相加；而這些運算可以通過算盤、袖珍計算器，或者效率更低的方式——你的大腦來進行。根據馬爾的水平理論，學習是我們能夠研究的認知能力的典型例子，而且對我們來說受益匪淺。
符號主義機器學習是人工智能知識工程學派的一個分支。20世紀70年代，所謂的基於知識的系統取得卓越成績，而到了80年代，它們迅速傳播，後來卻消失了。它們消失的主要原因是人人逃避的知識習得瓶頸：從專家身上提取知識，然後將其編碼成為規則，這樣做難度太大、太費力、易出故障，會引起很多問題。讓計算機自行學習，比如通過查看過往患者症狀及其相應療效的數據庫，就可以進行疾病診斷，比無數次地找醫生要容易很多。突然之間，諸如理夏德·米哈爾斯基、湯姆·米切爾、羅斯·昆蘭之類的先驅人物，他們的工作有了新的聯繫，而這個領域自此沒有停止發展過（另外一個重要的問題就是基於知識的系統在處理不確定性時會有問題，在第六章會深入探討這個問題）。
因為其起源和指導原則，符號學派和其他學派相比，和人工智能的其他方面關係更為密切。如果計算機科學是一塊大陸，符號主義機器學習和知識工程學會有很長的交界線。知識通過兩個方向進行交易——手動輸入的知識，供學習算法使用；還有歸納得出的知識，用來加入知識庫中，但最終理性主義者和經驗主義者的斷層線會剛好落在這條界線上，想越過這條界線則不容易。
符號主義是通往終極算法的最短路程。它不要求我們弄明白進化論和大腦的工作原理，而且也避免了貝葉斯主義的數學複雜性。規則集合決策樹易於理解，所以我們知道學習算法要做什麼。這樣它可以輕易算出自己做對或做錯什麼，找出故障，得出準確結果。
儘管決策樹很受歡迎，但逆向演繹是尋找主算法更好的出發點。因為逆向演繹具備這樣的關鍵屬性：可以輕易地將知識併入主算法中，而且我們知道休謨問題使這一點變得很有必要。另外，規則集和決策樹相比，表達多數概念的方式要簡潔很多。把一棵決策樹轉變成一個規則集很容易：每條從「根部」到「葉子」的路線是一條規則，而且路線不會崩潰。另外，最壞的情況是，把一個規則集轉化成一棵決策樹，需要把每條規則變成一棵迷你決策樹，然後用規則2決策樹的副本來代替規則1決策樹的每片葉子，用規則3決策樹的副本來代替規則2決策樹每個副本的每片葉子，以此類推，這樣會引起大範圍崩潰。
逆向演繹就像一個超級科學家，系統查看論據，思考可行的歸納法，整理最有利的證據，然後將這些和其他論據一起，進一步提出假設——所有過程都基於計算機的速度。逆向演繹簡潔而美觀，至少符合符號學者的品位。此外，逆向演繹也有一些嚴重的缺點。可行的歸納法數量廣泛，除非我們和最初知識保持親密關係，否則很容易在空間中迷失。逆向演繹容易被噪聲迷惑：我們怎樣才能知道，哪些演繹步驟被漏掉了，如果前提或者結論本身就已出錯？最嚴重的是，真正的概念很少能通過一個規則集來定義。它們不是黑，也不是白，比如垃圾郵件和非垃圾郵件之間有一片很大的灰色區域。要獲取真正的概念，就得權衡並收集有弱點的論據，直到出現清晰的定義。疾病的診斷，涉及把重點放在一些症狀上面，然後放棄那些不完整的論據。還沒有人能只學習一個規則組，就能通過觀看圖片的像素來認出一隻貓，而且可能以後也沒人能做到。
聯結學派對符號學派尤其不滿。根據他們的觀點，你能通過邏輯規則來定義的概念僅僅是冰山一角，其實表面之下還有很多東西是形式推理無法看到的。而同樣的道理，我們腦子裡所想的東西也是潛意識的。你不能僅靠構造一個空洞的機械化科學家，就想讓他把所有有意義的事情完成，你首先得給他點什麼東西，例如一個真正的大腦，能和真實的感覺相連，在真實世界中成長，甚至可能要常常絆他的腳。你怎樣才能構造這樣的大腦呢？通過逆向分析。如果想對一輛車進行逆向分析，你就應看看發動機蓋下面。如果想對大腦進行逆向分析，你就要看看腦殼裡面。