第1章　搜尋

引言

　　搜尋是人工智慧的一個關鍵領域。人工智慧所面臨的許多問題都非常複雜，往往無法一步完成，而是需要透過一組動作（action）序列來達到目標（goal）。這個尋找達到目標的動作序列求解過程，就稱為搜尋。解決搜尋問題的方法稱為搜尋策略，其主要任務是確定選取動作的方式和順序。

　　現實中許多規劃問題都可以描述成搜尋問題，且都已得到很好的解決。如圖1.1所示，自動駕駛或導航系統中的路徑規劃以及使機器人完成抓取任務的運動規劃，就是典型的搜尋問題。許多智力遊戲的求解，比如尋找魔術方塊的復原方法，本質也是搜尋問題。還有，擊敗前國際西洋棋冠軍卡斯帕洛夫的深藍程式，以及擊敗世界圍棋冠軍李世石的GoogleDeep Mind AlphaGo，它們的核心也都是搜尋算法。

　　本章將介紹2大類搜尋算法：單智慧型（single–agent）搜尋和多智慧型（multi–agent）對抗搜尋（adversarial search）。

　　單智慧型搜尋針對在單個智慧型環境中的決策問題。即使有其他智慧主體存在，這類搜尋也只是簡單地把它們的行為視為環境的一部分。前面例子中的自動駕駛與導航路徑規劃、機器人抓取規劃，均為單智慧型搜尋。單智慧型的搜尋策略有兩種基本方式。一種是盲目搜尋，也稱為無訊息搜尋策略，即不考慮除問題定義本身之外的知識，根據事先確定好的某種固定排序，依次調用動作，以探求最優的動作序列。另一種是啟發式搜尋，或稱為有訊息引導的搜尋策略，即考慮具體問題的可用知識，有目的地動態確定排序的規則，優先搜尋最可能的動作，從而加快搜尋速度。

　　多智慧型對抗搜尋主要針對存在多個智慧主體競爭的環境。此時，每一個智慧主體都需要考慮其他智慧主體的決策帶來的影響，因而導致了博奕問題和對抗搜尋的產生。對抗搜尋算法在每一步中，尋找在對手最優選擇下使己方收益最大化的步驟，並不斷疊代，直到最終找到雙方策略的均衡點。在均衡點，雙方都無法透過改變自己的策略來提高收益。在對抗搜尋中，可以透過剪枝來避免搜尋必然不優的策略，從而提高效率。

　　在本章，先介紹單智慧型搜尋問題的定義，然後詳細介紹盲目搜尋和啟發式搜尋兩種主要的方法；隨後，將介紹多智慧型對抗搜尋。為方便讀者理解，我們會穿插介紹一些必要的數據結構知識及例子。

1.1 搜尋問題的定義

　　一個搜尋問題可以由六個組成部分〔S，s0，A，T，c，G〕來形式化描述：

　　·　S：狀態空間（state space），是所有可能的狀態集合，而狀態（state）表示問題中考慮系統所處的狀態；

　　·　s0：初始狀態（initial state），描述系統的起始狀態；

　　·　A：行動空間（action space），對每個狀態s，A（s）描述在該狀態下可用的行動集合；

　　·　T（s，a）：轉移函數（transition function），在狀態s下執行行動a後達到的狀態；

　　·　c（s，a，s'）：損耗函數（cost function），在狀態s下執行行動a後達到的狀態s'的損耗；

　　·　G（s）：目標測試函數（goal test），判斷給定的狀態s是否為目標狀態。值得注意的是，對某些問題，目標狀態s是一個集合，而不是單個狀態。搜尋在系統到達其中一個目標狀態後結束。

　　將系統從初始狀態帶到目標狀態的一系列動作稱為一個解。解的好壞由路徑上的總損耗來度量，其中取得最小總損耗的解稱為最優解。在本章中，假定轉移函數為確定性的，即在一個狀態下，執行某個動作之後，會確定性地到達另一個狀態，不存在隨機性。對於存在隨機性的複雜問題，需要將問題建模成一個馬可夫決策過程（Markov decision process），相關內容會在第8章進行介紹。

　　接下來，我們舉兩個例子。

　　第一個例子是圖1.2中展示的一個常見的8數字推盤遊戲。在一個3×3的木板上，有編號為1～8的圖塊和一個空白區域，與空白區域相鄰的圖塊可以被推入空白區域。我們的目標是從初始布局（左），透過移動圖塊達到指定的目標布局（右）。對於這個遊戲，我們難以利用現有的訊息直接計算出問題的解，而必須透過搜尋，逐步找到能夠達成目標的路徑。在這個問題裡，每個解均為一系列的數字移動動作。

　　對於這個8數字推盤問題，可以給出它的形式化描述：

　　·　狀態空間：所有數字擺放的布局；

　　·　初始狀態：左側圖的布局；

　　·　行動空間：將空格相鄰的數字之一移動到空格處；

　　·　轉移函數：給定上一布局和動作，轉移函數返回當前數字布局；

　　·　損耗函數：該問題中，每移動一次數字產生一單位的損耗；

　　·　目標測試函數：判斷當前數字布局是否與圖右側布局一致。

　　第二個例子是圖1.3中的地圖路徑搜尋問題。在這個問題裡，可以沿著圖中標出的邊從一個城市移動到另一個城市，邊上的數字顯示了對應2座城市之間的距離。我們的目標是找到從烏魯木齊（A）到臺北（T）距離最短的一條路徑。該問題的形式化描述為：

　　·　狀態空間：地圖中的城市；

　　·　初始狀態：本問題中，我們假設智慧主體從烏魯木齊出發，故初始城市為烏魯木齊（A）；

　　·　行動空間：所有移動到相鄰城市的動作集合，即圖中的鄰邊；

　　·　轉移函數：給定狀態（城市）和動作（邊），轉移函數返回下一個到達的狀態（城市）；

　　·　損耗函數：該問題中，每個動作的成本可以設定為從當前城市到達另一城市的距離；

　　·　目標測試函數：判斷當前城市是不是目標城市，在本問題中為臺北（T）。

第4章　決策樹、梯度提升和隨機森林

引言

　　在本章裡，我們將學習決策樹與相關的集成學習算法。與其他監督式學習方法類似，決策樹的訓練也是基於給定的訓練數據，學習出一個從數據到標籤的映射。決策樹表示的映射僅由一系列簡單的判斷規則組成，與人類做決策的過程類似。因此非常易於理解，具有很強的可解釋性。但相比神經網路等複雜模型，單個決策樹的擬合能力非常有限。因此在實際應用時，通常訓練許多個決策樹，然後綜合它們的預測結果，這樣綜合多個簡單模型的方式稱為集成學習。如果將單個模型看成一個專家，那麼集成學習可以理解為由許多專家組成的智囊團。基於決策樹的集成學習是目前除了深度學習之外最主要的監督式學習方法之一，在數據科學比賽（例如Kaggle競賽(1)）和工業界中都有廣泛的應用。因此，決策樹以及相關的集成學習方法，無疑是機器學習領域的必備技能之一。

　　以下，首先介紹決策樹與它的訓練算法。然後將介紹2種常見的、基於決策樹的集成學習算法：隨機森林和梯度提升。

4.1　決策樹

4.1.1　例子

　　為了理解決策樹的結構，我們先舉一個簡單的例子。假設需要根據表4.1的數據集設計一個電子郵件分類系統，用以區分垃圾郵件和正常郵件。一個直觀的做法是制定一些簡單的規則。例如，先判斷郵件是否來自陌生的信箱。如果該郵件來自常用的聯絡人，就可以基本上排除是垃圾郵件的可能。其次，垃圾郵件往往包含詐騙訊息，因此會經常出現「賺錢」、「轉帳」等字眼。基於這兩點，可以制定出如圖4.1所示的郵件分類規則。

4.1.2　決策樹的定義

　　圖4.1中，整個分類流程構成了一種樹狀結構。其中最上方的灰色方框是樹的根部，稱為根節點。每個箭頭是樹的一個分支，每個方框都是樹的節點。灰色的方框帶有分支，稱為中間節點，每個中間節點代表一個判斷條件。根據中間節點判斷結果的不同，從中間節點出發的箭頭，會指向不同的子節點；這個中間節點稱為這些子節點的父節點。橘色的方框不再生出分支，稱為葉子節點。從根節點到每個葉子節點都會經過一條路徑，每個葉子節點紀錄決策樹對符合路徑上所有判斷條件的數據的預測情況。例如圖4.1中，從最高的灰色根節點出發，到左下角的橘色葉子節點，會經過「是否來自陌生信箱」與「是否包含『轉帳』」2個判斷條件。如果有一封郵件這2個條件均成立，它將被分類為垃圾郵件。

　　透過上面的例子，我們對決策樹的主要組成有了直觀的了解。以下是決策樹的正式定義。

　　定義［決策樹］：一個樹結構的每個中間節點對數據的某一個特徵進行判斷，根據判斷結果的不同，指向相應的子節點。而且，該樹結構的每個葉子節點，對符合所有根節點到該葉子節點路徑上判斷條件的數據給出一個預測值。這樣的樹結構稱為決策樹。

　　根據特徵類型的不同，決策樹採用不同形式的分支。在圖4.1的例子中，判斷條件僅涉及表4.1中的2個變量，且2個變量均只有「是」和「否」2種取值。對於數值類型的變量x（例如總字數與生僻字比例等），決策樹可使用該變量是否超過一個閾值（x≤t）作為判斷條件，例如總字數是否超過500；而對於具有更多取值的離散型變量，可以使用該變量是否屬於值域的某一子集（如x∈S）作為判斷條件；或者對每種取值都生成一個單獨的分支。

　　針對不同的問題，決策樹的葉子節點需要輸出不同的預測。對於迴歸問題，葉子節點的預測值是一個實數；而對於分類問題，則是一個類別。前者稱為迴歸樹，後者稱為分類樹。在前面垃圾郵件分類問題中，採用的是分類樹。以下看一個迴歸樹的例子。

　　假設你是某手機品牌的粉絲，希望對一款即將發布的新機型價格進行預測，且已知當前市面上各種不同配置手機的價格如表4.2所示。

　　對這個問題，可以採用以下的定價規則進行決策樹的構建：如果內存超過8 GB，則預測價格為5,200元；否則將根據螢幕的材質進行進一步預測。根據這些規則，得到了圖4.2所示的3葉子決策樹。由於規則簡單，決策樹只能得到非常粗糙的結果。如果希望得到更精確的價格預測，則需要使用更複雜的決策樹，或透過後面介紹的集成學習方法，綜合多個決策樹的結果。

　　整體來說，決策樹將輸入的數據X所在的空間，分割成多個不同的子空間；然後為每個子空間（對應一個葉子節點）賦予一個預測值，即決策樹表示一個分段常數函數。圖4.3是一個連續特徵空間上決策樹的例子。在這個例子裡，數據集有2個數值類型的特徵x1和x2，而圖4.3（a）中的決策樹相當於把數據所在的平面分割成4個小塊（見圖4.3（b）），並賦予每個小塊一個常數的預測值。如果把決策樹視為x1，x2的二元函數f，那麼可以在三維空間中畫出y＝f（x1，x2）的圖像，如圖4.3（c）所示。

　　以下將詳細介紹決策樹的訓練。

4.1.3　決策樹的訓練

　　透過前面的2個例子可以看出，決策樹主要由2部分組成：葉子節點的預測值、決策樹的結構，包括中間節點的判斷條件。決策樹的訓練，就是找出一個理想的決策樹結構，並對每片葉子賦予合適的預測值。

　　決策樹的訓練可以總結為如下由根到葉子構造的過程：最初，只有一個根節點，節點對應所有訓練數據；然後，選擇一個特徵，設置一個判斷條件（也稱為分割條件）；接下來，依據該判斷條件構造根的2個葉子，使每個葉子對應一部分數據；重複這個葉子節點的構造步驟，直到達一定的終止條件為止。

　　以下將詳細討論如何選取葉子的預測值以及如何分割葉子節點。這是決策樹構建的核心所在。

第1章　搜尋

引言

　　搜尋是人工智慧的一個關鍵領域。人工智慧所面臨的許多問題都非常複雜，往往無法一步完成，而是需要透過一組動作（action）序列來達到目標（goal）。這個尋找達到目標的動作序列求解過程，就稱為搜尋。解決搜尋問題的方法稱為搜尋策略，其主要任務是確定選取動作的方式和順序。

　　現實中許多規劃問題都可以描述成搜尋問題，且都已得到很好的解決。如圖1.1所示，自動駕駛或導航系統中的路徑規劃以及使機器人完成抓取任務的運動規劃，就是典型的搜尋問題。許多智力遊戲的求解，比如尋找魔術方塊的復原方法，...

前言

　　縱觀科學的發展史，人工智慧可以說是人類長期以來一直不停追求，力求理解與掌握的一個領域。從2,000多年前的亞里斯多德開始，到後來的科學巨擘圖靈（Alan Turing，電腦科學之父）與夏農（Claude Shannon，資訊理論的創始人），他們無一不為人類的智慧及後來的人工智慧著迷，並不倦地探索。科學家們希望能以科學的方法理解智慧的本質，並製造出智慧的機器，實現像人腦一樣的學習、理解與決策。

　　在人工智慧的發展史上，有兩個里程碑式的事件最為人們所稱道。一是圖靈在1950年的劃時代論文《電腦機器與智慧》（Computing Machinery and Intelligence）中提出著名的「圖靈測試」：如果一臺機器能與人類透過通訊設備對話，並不被辨別出其機器身分，則稱這臺機器具有智慧。可以說，圖靈測試從計算科學的角度提供了一個智慧的定義。二是1955年，麥卡錫（John McCarthy）、明斯基（Marvin Minsky）、夏農與羅徹斯特（Nathaniel Rochester）共同提交了一份申請書，提出於1956年暑假在美國漢諾瓦小鎮的達特茅斯學院舉行一場研討會，討論透過機器實現智慧所需的科學基礎。在這次會議上，人工智慧的概念正式被提出。

　　在科學家們前赴後繼的努力下，自1956年的達特茅斯會議至今，人工智慧得到了巨大的發展，並在許多領域獲得驚人的成就。比如1997年機器人「深藍（Deep Blue）」擊敗國際西洋棋世界冠軍卡斯帕洛夫；2012年卷積神經網路在ImageNet圖像識別比賽中一舉奪魁；2016年機器人AlphaGo系統擊敗世界圍棋冠軍李世石。除了技術上的突破，人工智慧技術也不斷在實際生活中得到廣泛的應用，包括人臉識別、智慧音響、智慧手機、醫療影像的自動診斷、語音識別、金融科技、機器人、無人駕駛汽車……等。這些日新月異的新技術，無不彰顯了人工智慧技術為人們生活帶來的巨大影響。

　　那麼，所有這些激動人心的突破究竟是如何實現的？它們背後的核心技術與原理又是什麼？我們現在距離真正的人工智慧還有多遠？如何才能持續推進人工智慧的發展？想要回答這些問題，我們必須系統深入地了解人工智慧不同方向的核心原理與前端發展。而中學的人工智慧教育，是人才培養的核心環節。正因為如此，本書希望在中學階段為同學們打下堅實的人工智慧知識基礎，助力同學們在人工智慧領域的學習。有別於大部分市面上的教材，本書希望為同學們系統地介紹人工智慧的核心方向，並學習具體原理。對具體原理的了解與把握，能幫助同學們建立對人工智慧發展的科學理解，更有利於同學們在學習探索中，把握正確的思考方向。

　　為達成這個目標，本書精選並介紹了八個人工智慧的核心方向（即搜尋、機器學習、線性迴歸、決策樹、神經網路、電腦視覺、自然語言處理、強化學習）及其中適合中學階段學習的重點知識，確保在使教學內容易於接受的同時，書中覆蓋的知識點與高等教育中的人工智慧教育一脈相承。

　　本書由姚期智院士主編，黃隆波副主編。全書共分為9章，第0章介紹數學與程式設計基礎，第1章介紹搜尋，第2章介紹機器學習，第3章討論線性迴歸，第4章闡述決策樹、梯度提升和隨機森林，第5章介紹神經網路，第6章分析電腦視覺，第7章介紹自然語言處理，第8章介紹馬可夫決策過程與強化學習。第0章和附錄由馬雄峰、吳文斐編寫，第1章由張崇潔編寫，第2章、第3章和第5章由袁洋編寫，第4章由李建編寫，第6章由高陽編寫，第7章由吳翼編寫，第8章由黃隆波編寫。

　　本書每一章均透過大家熟知的場景為背景，介紹知識點的實際應用，以簡單的例子詳細介紹核心的原理，並以簡潔的文字與數學語言，具體描述原理及擴展。同時，本書的每一章均提供精心設計的練習題。我們希望透過教學與訓練的方式，使同學們獲得對算法的具體經驗，並在練習中加深對基礎理論的理解，做到舉一反三。為方便同學們進行學習，本書同時配套網路資源，提供相關的原始碼及額外的實驗習題，供感興趣的同學進一步學習。本書的推薦使用方式如下：①第0章為數學與程式設計基礎，對此部分比較熟悉的同學，可以選擇跳過，直接進入後面章節。②第1章至第4章為人工智慧入門的基礎章節，這4章之間的連結緊密。因此，建議同時進行學習，學習時間為一個學期。在章節的學習中，建議結合習題與網路資源進行實驗加深理解與鞏固。③第5章至第8章為細分章節，分別介紹人工智慧4個不同方向的基礎知識與原理。在介紹時，可以根據學生興趣與課程時間進行安排。其中較難的部分在授課時可作為選講章節。

　　編寫者對編寫這本教材非常興奮。我們希望透過本書，讓更多的學生了解人工智慧先進方向的核心原理，並從科學的視角觀察與理解尖端科學研究成果。人工智慧是一個基礎非常寬廣的領域，涉及電腦、數學、心理學、神經科學在內的多個學科。因此，本書也僅僅是覆蓋了人工智慧的冰山一角。編寫者希望透過本書，讓同學們對人工智慧的神奇與巨大作用有個初步了解，進而不斷學習相關學科的知識，為今後從事人工智慧的研究，打下良好的基礎。

前言

　　縱觀科學的發展史，人工智慧可以說是人類長期以來一直不停追求，力求理解與掌握的一個領域。從2,000多年前的亞里斯多德開始，到後來的科學巨擘圖靈（Alan Turing，電腦科學之父）與夏農（Claude Shannon，資訊理論的創始人），他們無一不為人類的智慧及後來的人工智慧著迷，並不倦地探索。科學家們希望能以科學的方法理解智慧的本質，並製造出智慧的機器，實現像人腦一樣的學習、理解與決策。

　　在人工智慧的發展史上，有兩個里程碑式的事件最為人們所稱道。一是圖靈在1950年的劃時代論文《電腦機器與智慧》（Computing ...

前言
第0章　數學與程式設計基礎
　　引言
　　0.1　數學基礎
　　0.2　程式設計基礎
　　練習題
　　程式設計
第1章　搜尋
　　引言
　　1.2　搜尋算法基礎
　　1.3　盲目搜尋
　　1.4　啟發式搜尋
　　1.5　對抗搜尋
　　本章總結
　　歷史回顧
　　練習題
　　第2章　機器學習
　　引言
　　2.1　監督式學習的概念
　　2.2　數據集與損失函數
　　2.3　泛化
　　2.4　過度擬合與低度擬合
　　2.5　創建數據集
　　2.6　無監督與半監督式學習
　　本章總結
　　歷史回顧
　　練習題
第3章　線性迴歸
　　引言
　　3.1　線性迴歸
　　3.2　優化方法
　　3.3　二分類問題
　　3.4　多分類問題
　　3.5　脊迴歸
　　3.6　Lasso迴歸
　　本章總結
　　練習題
第4章　決策樹、梯度提升
　　和隨機森林
　　引言
　　4.1　決策樹
　　4.2　隨機森林
　　4.3　梯度提升
　　本章總結
　　歷史回顧
　　參考文獻
　　練習題
第5章　神經網路
　　引言
　　5.1　深度線性網路
　　5.2　非線性神經網路
　　5.3　反向傳播計算導數
　　本章總結
　　歷史回顧
　　練習題
第6章　電腦視覺
　　引言
　　6.1　什麼是電腦視覺
　　6.2　圖像的形成
　　6.3　線性濾波器
　　6.4　邊際檢測
　　6.5　卷積神經網路
　　本章總結
　　歷史回顧
　　參考文獻
　　練習題
第7章　自然語言處理
　　引言
　　7.1　語言模型
　　7.2　字模型與詞模型
　　7.3　向量語義
　　7.4　基於神經網路的自然語言處理
　　本章總結
　　歷史回顧
　　練習題
第8章　馬可夫決策過程與強化學習
　　引言
　　8.1　馬可夫鏈
　　8.2　馬可夫決策過程
　　8.3　強化學習
　　本章總結
　　歷史回顧
　　參考文獻
　　練習題
附錄A　數學基礎
　　A.1　導數
　　A.2　機率
　　A.3　矩陣
附錄B　程式設計基礎
　　B.1　整數類型的運算
　　B.2　變量命名規則
　　B.3　關係表達式和邏輯表達式
　　B.4　函數調用中的傳值和傳引用
　　B.5　複雜類型
　　B.6　一些技巧
　　B.7　程式設計風格

前言
第0章　數學與程式設計基礎
　　引言
　　0.1　數學基礎
　　0.2　程式設計基礎
　　練習題
　　程式設計
第1章　搜尋
　　引言
　　1.2　搜尋算法基礎
　　1.3　盲目搜尋
　　1.4　啟發式搜尋
　　1.5　對抗搜尋
　　本章總結
　　歷史回顧
　　練習題
　　第2章　機器學習
　　引言
　　2.1　監督式學習的概念
　　2.2　數據集與損失函數
　　2.3　泛化
　　2.4　過度擬合與低度擬合
　　2.5　創建數據集
　　2.6　無監督與半監督式學習
　　本章總結
　　歷史回顧
　　練習題...