人工智能基礎:問題解決和自動推理

 

目錄

 

 

 

 

第1章核心人工智能： 問題解決和

自動推理

1．1早期的里程碑

 

1．1．1數字運算的極限

 

1．1．2AI的誕生

 

1．1．3早期策略： 搜索

算法

 

1．1．4早期的智慧： 電腦

需要知識

 

1．1．5編程語言

 

1．1．6教科書： 許多不同的

主題

 

1．1．721世紀的展望

 

1．2問題解決

 

1．2．1典型問題

 

1．2．2經典搜索方法

 

1．2．3規劃

 

1．2．4遺傳算法

 

1．2．5群體智能算法

 

1．2．6涌現特性和人工

生命

 

1．3自動推理

 

1．3．1斑馬問題

 

1．3．2電腦能解決斑馬

問題嗎

 

1．3．3家庭關系

 

1．3．4知識表示

 

1．3．5自動推理

 

1．3．6不那麽明確的

概念

 

1．3．7不完美的知識

 

1．3．8不確定性處理

 

1．3．9專家系統

 

1．4本書結構與方法

 

第2章盲搜

 

2．1動機和術語

 

2．1．1簡單謎題

 

2．1．2搜索樹

 

2．1．3搜索操作符

 

2．1．4人工智能中的

盲搜

 

2．1．5滑方塊

 

2．1．6傳教士和食人族

 

2．1．7程序員的視角

 

2．2深度優先搜索和廣度優先

搜索

 

2．2．1搜索樹舉例

 

2．2．2深度優先搜索: 

原理

 

2．2．3深度優先搜索

算法

 

2．2．4數值舉例

 

2．2．5廣度優先搜索： 

原理

 

2．2．6廣度優先搜索

算法

 

 

2．2．7數值舉例

 

2．3實際考慮

 

2．3．1通用搜索模型

 

2．3．2最終狀態的確切形式

可能是未知的

 

2．3．3最終狀態的未知形式： 

舉例

 

2．3．4驗證狀態是否為最終狀

態可能代價高昂

 

2．3．5目標1——問題的解看

上去怎樣

 

2．3．6目標2——什麽途徑可

以得到問題的解

 

2．3．7停止條件

 

2．3．8檢查Lseen可能代價

高昂

 

2．3．9搜索有序列表

 

2．3．10哈希函數

 

2．4搜索性能方面

 

2．4．1代價計量

 

2．4．2分支因子

 

2．4．3搜索深度

 

2．4．4BFS的內存開銷

 

2．4．5DFS的內存開銷

 

2．4．6兩種算法的計算

代價

 

2．4．7兩者哪個成本

更低

 

2．4．8尋找比爾的家

 

2．4．9具有多個最終狀態的

場景

 

2．5迭代深化(和擴展)

 

2．5．1ID算法

 

2．5．2為什麽該技術

有效

 

2．5．3數值舉例

 

2．5．4哪些因素決定了搜索

成本

 

2．5．5迭代深化是否

浪費

 

2．5．6ID與基本算法的

比較

 

2．5．7註意事項

 

2．5．8備選方案： 迭代

擴展

 

2．6熟能生巧

 

2．7結語

 

第3章啟發式搜索和退火

 

3．1爬山算法和最佳優先搜索

 

3．1．1評價函數

 

3．1．2數值舉例： 滑

方塊

 

3．1．3復雜的評價函數

 

3．1．4最大化或最小化

 

3．1．5爬山算法

 

3．1．6最佳優先搜索

 

3．1．7實現最佳優先搜索的

兩種方法

 

3．1．8兩種方法的比較

 

3．1．9人類的搜索方式

 

3．2評價函數的實踐方面

 

3．2．1狀態值的時間

惡化

 

3．2．2多個狀態可以有

相同的值

 

3．2．3前瞻性評價策略

 

3．2．4集束搜索

 

3．2．5N在集束搜索中的

作用

 

3．2．6數值舉例

 

3．2．7昂貴的評價

 

3．3A*和IDA*

 

3．3．1動機

 

3．3．2代價函數

 

3．3．3A*算法

 

3．3．4數值舉例

 

3．3．5A*的兩個版本

 

3．3．6更復雜的代價

函數

 

3．3．7跳躍式技術

 

3．3．8IDA*

 

3．4模擬退火

 

3．4．1生長無缺陷晶體

 

3．4．2正式視圖

 

3．4．3AI視角

 

3．4．4簡化視角下的模擬

退火

 

3．4．5狀態值的影響

 

3．4．6溫度影響

 

3．4．7冷卻

 

3．4．8初始溫度

 

3．5背景知識的作用

 

3．5．1AI搜索解決的幻方

問題

 

3．5．2數學家解決幻方

問題

 

3．5．3課程： 背景知識的

好處

 

3．5．4數獨中的分支

因子

 

3．5．5斑馬謎題

 

3．6連續域

 

3．6．1連續域舉例

 

3．6．2離散化

 

3．6．3梯度上升與神經

網絡

 

3．6．4群體智能算法

 

3．7熟能生巧

 

3．8結語

 

第4章對抗搜索

 

4．1典型問題

 

4．1．1簡單游戲舉例

 

4．1．2其他游戲

 

4．1．3更普遍的觀點

 

4．1．4與經典搜索的

區別

 

4．2基準極小極大算法

 

4．2．1最大化者和最小

化者

 

4．2．2游戲樹

 

4．2．3父母自孩子遺傳

 

4．2．4極小極大算法

原理

 

4．2．5數值舉例

 

4．2．6回傳值

 

4．3啟發式極小極大算法

 

4．3．1游戲樹過於龐大

 

4．3．2深度必須受到

限制

 

4．3．3對抗搜索中的評價

函數

 

4．3．4評價函數從何

而來

 

4．3．5啟發式極小極大

算法原理

 

4．3．6影響游戲玩得好壞

的因素

 

4．3．7靈活的評價深度

 

4．3．8計算代價可能很

昂貴

 

4．3．9成功案例

 

4．4AlphaBeta剪枝

 

4．4．1常規情況

 

4．4．2多餘的評價

 

4．4．3另一個例子

 

4．4．4關於剪枝算法

 

4．4．5關於AlphaBeta

剪枝

 

4．4．6反向方法

 

4．5額外的游戲編程技巧

 

4．5．1啟發式的算法控制

搜索深度

 

4．5．2望向視野外

 

4．5．3開局庫

 

4．5．4殘局查找表

 

4．5．5人類模式識別

技能

 

4．5．6人類的“剪枝”

方式

 

4．5．7游戲中的模式

識別

 

4．6熟能生巧

 

4．7結語

 

第5章規劃

 

5．1玩具積木

 

5．1．1移動積木

 

5．1．2描述符

 

5．1．3狀態描述示例

 

5．1．4註釋

 

5．2可用操作

 

5．2．1玩具場景的操作

 

5．2．2前提條件列表

 

5．2．3添加列表

 

5．2．4刪除列表

 

5．2．5定義move(x,y,z)

 

5．2．6通用操作的實

例化

 

5．2．7有多少個實例

 

5．2．8執行操作

 

5．2．9示例

 

5．3使用STRIPS進行規劃

 

5．3．1目標集

 

5．3．2一般理念

 

5．3．3具體實例

 

5．3．4如何確定行動

 

5．3．5倒數第二個狀態是

什麽樣的

 

5．3．6STRIPS的偽

代碼

 

5．4數值舉例

 

5．4．1應該考慮哪些

操作

 

5．4．2檢查列表

 

5．4．3註意事項

 

5．4．4描述前一個狀態

 

5．4．5迭代過程

 

5．5人工智能規劃的高級應用

 

5．5．1旅行推銷員問題

 

5．5．2包裹投遞和數據包

路由

 

5．5．3救護車路由

 

5．5．4背包問題

 

5．5．5工作車間調度

 

5．5．6註意事項

 

5．5．7重要評論

 

5．6熟能生巧

 

5．7結語

 

第6章遺傳算法

 

6．1一般模式

 

6．1．1不完全復制，適者

生存

 

6．1．2GA應用中的

個體

 

6．1．3基本循環

 

6．1．4人口

 

6．1．5適者生存

 

6．1．6有多少代

 

6．1．7停止標準

 

6．2不完全復制與生存

 

6．2．1交配

 

6．2．2重組

 

6．2．3變異

 

6．2．4實施生存博弈

 

6．2．5利用生存機制進行

交配

 

6．2．6評論生存游戲

 

6．2．7屬於父母兩邊的

孩子

 

6．2．8GA的簡單任務

 

6．2．9探索與父母的

距離

 

6．2．10重組與變異

 

6．2．11算法為何有效

 

6．3其他GA操作符

 

6．3．1兩點交叉

 

6．3．2隨機位交換

 

6．3．3反轉

 

6．3．4程序員控製程序的

方法

 

6．4潛在問題

 

6．4．1退化種群

 

6．4．2無害退化與過早

退化

 

6．4．3識別退化狀態

 

6．4．4擺脫退化狀態

 

6．4．5設計不當的適應度

函數

 

6．4．6不能反映遺傳算法目

標的適應度函數

 

6．5高級變體

 

6．5．1數字染色體

 

6．5．2樹結構形式的染

色體

 

6．5．3多人群和多目標

 

6．5．4拉馬克方法

 

6．6GA和背包問題

 

6．6．1背包規則(修

訂版)

 

6．6．2用二進制字符串對

問題進行編碼

 

6．6．3運行程序

 

6．6．4GA是否能找到最佳

解決方案

 

6．6．5觀察： 隱含並

行性

 

6．6．6用數字字符串編碼

包內容

 

6．6．7數字字符串中的

變異和重組

 

6．6．8小結

 

6．7GA和囚徒困境

 

6．7．1要保密還是選擇告發/

告密

 

6．7．2實際觀察

 

6．7．3重復事件的策略

 

6．7．4在染色體中編碼

策略

 

6．7．5早期回合

 

6．7．6錦標賽方法

 

6．7．7實驗表現

 

6．7．8小結

 

6．8熟能生巧

 

6．9結語

 

第7章人工生命

 

7．1涌現特性

 

7．1．1從原子到蛋白質

 

7．1．2從分子到社會

 

7．1．3從字母到詩歌

 

7．1．4通往人工生命

之路

 

7．2L系統

 

7．2．1原始的L系統

規則

 

7．2．2另一個例子： 康托爾

集合

 

7．2．3啟示

 

7．3細胞自動機

 

7．3．1簡單示例

 

7．3．2變化

 

7．3．3增加另一個維度

 

7．4康威的生命游戲

 

7．4．1棋盤及其單元格

 

7．4．2規則

 

7．4．3更有趣的例子

 

7．4．4典型行為

 

7．4．5小結

 

7．5熟能生巧

 

7．6結語

 

第8章涌現特性和群體智能

 

8．1蟻群優化

 

8．1．1瑣碎的表述

 

8．1．2蟻群選擇

 

8．1．3信息素路徑

 

8．1．4選擇路徑

 

8．1．5揮發與添加

 

8．1．6程序員的視角

 

8．1．7選擇具體路徑的

概率

 

8．1．8路徑選擇機制

 

8．1．9添加信息素

 

8．1．10信息素揮發

 

8．1．11非穩態任務

 

8．2ACO算法解決推銷員

問題

 

8．2．1螞蟻與智能體

 

8．2．2ACO對TSP的

看法

 

8．2．3初始化

 

8．2．4建立概率決策

 

8．2．5數值舉例

 

8．2．6一隻螞蟻會釋放多少

信息素

 

8．2．7各路線上的螞蟻

數量

 

8．2．8在每條邊上添加信

息素

 

8．2．9更新數值

 

8．2．10完整的概率

公式

 

8．2．11ACO處理推銷員問題

(TSP)的概述

 

8．2．12結束語

 

8．2．13主要限制

 

8．3粒子群優化算法

 

8．3．1是粒子還是鳥

 

8．3．2尋找多元函數的最

大值

 

8．3．3專業術語

 

8．3．43個假設

 

8．3．5智能體的目標

 

8．3．6更新速度和位置： 

簡單公式

 

8．3．7速度更新的全尺寸

版本

 

8．3．8c1和c2的值應該是

多少

 

8．3．9PSO 算法的總體

流程

 

8．3．10可能的並發

問題

 

8．3．11本地極端行為的危

險性

 

8．3．12多個群體

 

8．4人工蜂群算法

 

8．4．1原始靈感

 

8．4．2這個比喻對人工智能

的貢獻

 

8．4．3任務

 

8．4．4第一步

 

8．4．5如何選擇有前途的

目標

 

8．4．6跟隨蜜蜂

 

8．4．7更新最佳位置

 

8．4．8支援蜜蜂

 

8．4．9參數

 

8．4．10算法

 

8．5熟能生巧

 

8．6結語

 

第9章自動推理的要素

 

9．1事實與查詢

 

9．1．1事實列表

 

9．1．2回答用戶的查詢

 

9．1．3帶變量的查詢

 

9．1．4多個變量

 

9．1．5復合查詢

 

9．1．6練習

 

9．1．7將變量與具體值

綁定

 

9．1．8如何處理復合

查詢

 

9．1．9謂詞排序

 

9．1．10查詢回答和

搜索

 

9．1．11嵌套論證

 

9．2規則和基於知識的系統

 

9．2．1簡單規則

 

9．2．2較長的規則

 

9．2．3規則的形式觀

 

9．2．4封閉世界假設

 

9．2．5基於知識的系統

 

9．3使用規則進行簡單推理

 

9．3．1回答查詢

 

9．3．2基礎知識之外

 

9．3．3由多條規則定義的

概念

 

9．3．4斷分正則表達式

 

9．3．5遞歸概念定義

 

9．3．6評估遞歸概念

 

9．3．7關於遞歸的評論

 

9．3．8小結

 

9．4熟能生巧

 

9．5結語

 

第10章邏輯與推理（簡化版）

 

10．1蘊涵、推理、定理證明

 

10．1．1蘊涵

 

10．1．2推理過程

 

10．1．3最簡形式的肯定

前項式

 

10．1．4示例

 

10．1．5其他推理

機制

 

10．1．6推理過程的可

靠性

 

10．1．7推理過程的完

備性

 

10．1．8定理證明

 

10．1．9半可判定性

 

10．2基於肯定前項式的

推理

 

10．2．1肯定前項式的

一般形式

 

10．2．2霍恩子句

 

10．2．3事件的真實性與

虛假性

 

10．2．4具體示例

 

10．2．5實際考慮

 

10．2．6霍恩子句知識庫中

的推理

 

10．3運用歸結原則進行

推理

 

10．3．1標準形式

 

10．3．2歸結原則

 

10．3．3理論的優勢

 

10．3．4具體舉例1

 

10．3．5實際考慮

 

10．3．6計算成本

 

10．3．7反向鏈

 

10．3．8具體舉例2

 

10．3．9歸結作為

搜索

 

10．4運用標準形式表達

知識

 

10．4．1標準形式(修

改版)

 

10．4．2轉換為標準

形式

 

10．4．3具體舉例

 

10．5熟能生巧

 

10．6結語

 

第11章使用變量的邏輯和推理

 

11．1規則和量詞

 

11．1．1對象和函數

 

11．1．2關系

 

11．1．3常量和變量

 

11．1．4參數順序

 

11．1．5原子和表

達式

 

11．1．6自動推理中的邏輯

表達式

 

11．1．7全稱量詞

 

11．1．8存在量詞

 

11．1．9量詞的順序

 

11．1．10其他示例

 

11．2刪除量詞

 

11．2．1刪除一些存在

量詞

 

11．2．2存在量化

向量

 

11．2．3經常被忽視的

案例

 

11．2．4斯科勒姆化

 

11．2．5刪除剩餘的存在

量詞

 

11．2．6消失的

後果

 

11．3綁定、統一和推理

 

11．3．1綁定變量

 

11．3．2綁定列表

 

11．3．3嵌套關系的

綁定

 

11．3．4統一

 

11．3．5使用變量的肯定

前項式和歸結

原則

 

11．4實用推理程序

 

11．4．1具體示例

 

11．4．2多個解決

方案

 

11．4．3綁定數量

 

11．4．4從左邊開始

 

11．4．5加速推理

過程

 

11．4．6先行的策略

 

11．4．7回跳

 

11．5熟能生巧

 

11．6結語

 

第12章表示知識的不同方式

 

12．1框架和語義網絡

 

12．1．1框架的具體

例子

 

12．1．2繼承值

 

12．1．3規則的例外

 

12．1．4語義網絡

 

12．2基於框架的知識推理

 

12．2．1查找實例

的類

 

12．2．2找到一個變量

的值

 

12．2．3語義網絡中的

推理

 

12．2．4框架中推理的計算

成本

 

12．3框架和SN中的N元

關系

 

12．3．1二元關系與

框架

 

12．3．2基於二元關系的

框架推理

 

12．3．3將二元關系轉換為

規則

 

12．3．4促進二元關系推理

的規則

 

12．3．5N元關系帶來的

困難

 

12．4熟能生巧

 

12．5結語

 

第13章自動推理道路上的障礙

 

13．1隱性假設

 

13．1．1框架問題

 

13．1．2隱性假設

 

13．2非單調性

 

13．2．1推理的單

調性

 

13．2．2母雞會飛嗎

 

13．2．3它們不會

飛嗎

 

13．2．4一般情況

 

13．2．5異常情況

 

13．2．6選擇哪個

版本

 

13．2．7理論、假設和

擴展

 

13．2．8多個擴展

 

13．2．9多值邏輯

 

13．2．10框架和語義

網絡

 

13．3Mycin的不確定性

因素

 

13．3．1不確定性

處理

 

13．3．2Mycin的確定性

因素

 

13．3．3一組事實和規則

的真相

 

13．3．4否定的確

定性

 

13．3．5數值舉例1

 

13．3．6確定性因素和肯定

前項式

 

13．3．7數值舉例2

 

13．3．8結合證據

 

13．3．9直觀的解釋

 

13．3．10數值舉例3

 

13．3．11數值舉例4

 

13．3．12兩種以上的

選擇

 

13．3．13理論基礎

 

13．4熟能生巧

 

13．5結語

 

第14章概率推理

 

14．1概率論(修改版)

 

14．1．1概率信息

來源

 

14．1．2單位間隔

 

14．1．3聯合概率

 

14．1．4數值舉例

 

14．1．5條件概率

 

14．1．6更一般的

公式

 

14．1．7罕見事件： m

估計

 

14．1．8通過m來量化

信心

 

14．1．9數值舉例

 

14．2概率與推理

 

14．2．1家庭關系領域的

例子

 

14．2．2規則和條件

概率

 

14．2．3依賴事件和獨立

事件

 

14．2．4貝葉斯公式

 

14．2．5貝葉斯公式和概率

推理

 

14．2．6選擇最有可能的

假設

 

14．3信念網絡

 

14．3．1信念網絡

概述

 

14．3．2數值舉例

 

14．3．3具體情況的

概率

 

14．3．4結論的概率

 

14．3．5B是真的嗎

 

14．4處理更現實的領域

 

14．4．1更大的信念

網絡

 

14．4．2看不見的原因和

漏洞節點

 

14．4．3需要太多的

概率

 

14．4．4樸素貝葉斯

 

14．4．5樸素貝葉斯假設是

否有害

 

14．4．6否定概率

(提醒)

 

14．4．7P(X|A1∨A2∨…

∨An)的概率是

多少

 

14．4．8具體事件的

概率

 

14．4．9數值舉例

 

14．4．10這些概率從哪

里來

 

14．5DempsterShafer理論： 

使用權重代替概率

 

14．5．1動機

 

14．5．2權重而非

概率

 

14．5．3辨識框架

 

14．5．4單例和組合

實例

 

14．6從權重到信念和可信度

 

14．6．1基本信念

分配

 

14．6．2任何BBA的基本

特性

 

14．6．3相信某個

命題

 

14．6．4命題的可

信度

 

14．6．5不確定性由兩個

值量化

 

14．6．6數值舉例

 

14．7DST證據組合規則

 

14．7．1多個權重轉移的

源頭

 

14．7．2沖突的級別

 

14．7．3組合法則

 

14．7．4數值舉例

 

14．7．5不止兩個來源的

情況

 

14．7．6BBA通常是什麽

樣的

 

14．8熟能生巧

 

14．9結語

 

第15章模糊集

 

15．1現實世界概念的模

糊性

 

15．1．1清晰概念和模糊

概念

 

15．1．2堆的悖論

 

15．1．3視覺示例

 

15．1．4另一個例子

 

15．2模糊集成員資格

 

15．2．1隸屬度

 

15．2．2黑色矩形

 

15．2．3有才華的

學生

 

15．2．4高個子

 

15．2．5溫暖的房間

 

15．2．6μA(x)函數的其他

常見形狀

 

15．2．7μA(x)的值

來源

 

15．3模糊性與其他範式的

比較

 

15．3．1一個清晰事件發生

的概率

 

15．3．2特徵的範圍

 

15．3．3模糊值的

概率

 

15．3．4模糊概率

 

15．4模糊集合運算

 

15．4．1模糊邏輯

 

15．4．2合取

 

15．4．3析取

 

15．4．4否定

 

15．4．5圖形說明

 

15．4．6數值舉例

 

15．4．7復雜表達

 

15．5計算語言變量

 

15．5．1語言變量的

例子

 

15．5．2語言變量的主

觀性

 

15．5．3上下文依賴

 

15．5．4計算模糊對象

數量

 

15．5．5數值舉例

 

15．5．6更高級的

例子

 

15．6模糊推理

 

15．6．1模糊規則

 

15．6．2更加真實的

規則

 

15．6．3用模糊規則

推理

 

15．6．4傳播隸屬度

 

15．6．5模糊控制

 

15．7熟能生巧

 

15．8結語

 

第16章專家系統的優點和缺點

 

16．1早期探索： Mycin

 

16．1．1實現

 

16．1．2預期的應用

範圍

 

16．1．3早期關註

 

16．1．4早期希望

 

16．2後續發展

 

16．2．1另一個醫學

系統

 

16．2．2發展前景

 

16．2．3數以百計的專家

系統

 

16．2．4過高期待的

風險

 

16．2．5懷疑主義

 

16．2．6現狀

 

16．3一些經驗

 

16．3．15分鐘到5小時

規則

 

16．3．2瓶頸： 知識庫

 

16．3．3通信模塊

 

16．3．4優雅降級

 

16．4熟能生巧

 

16．5結語

 

第17章超越核心人工智能

 

17．1電腦視覺

 

17．1．1圖像及其

像素

 

17．1．2去除噪聲

 

17．1．3邊緣檢測

 

17．1．4連接邊緣

 

17．1．5紋理

 

17．1．6顏色

 

17．1．7分割

 

17．1．8場景解釋

 

17．1．9現代方法

 

17．2自然語言處理

 

17．2．1信號處理

 

17．2．2句法分析

(解析)

 

17．2．3語義分析

 

17．2．4歧義

 

17．2．5語言生成

 

17．2．6現代方法： 機器

學習

 

17．3機器學習

 

17．3．1知識獲取： 人工

智能的瓶頸

 

17．3．2從實例中

學習

 

17．3．3規則和決

策樹

 

17．3．4其他方法

 

17．3．5舊機器學習的普遍

理念

 

17．3．6如今的機器

學習

 

17．4智能體技術

 

17．4．1為什麽選擇智

能體

 

17．4．2框架

 

17．5結語

 

第18章哲學思考

 

18．1圖靈測試

 

18．1．1圖靈的基本

方案

 

18．1．2其他應用

 

18．1．3打破圖靈

測試

 

18．2中文房間和其他意見

 

18．2．1Searle的基本

設想

 

18．2．2這個人是否懂

中文

 

18．2．3哲學家的

觀點

 

18．2．4下棋程序帶來的

啟示

 

18．2．5圖靈對神學保留

意見的回應

 

18．2．6弱人工智能與強

人工智能

 

18．3工程師角度

 

18．3．1實踐性

 

18．3．2人們是否應該

擔憂

 

18．3．3增強人類

智慧

 

18．3．4現有人工智能的

局限性

 

18．4結語

 

參考文獻