人工智能（第2版）

第一部分引言
第　1章人工智能概述　2
1.0　引言　2
1.0.1　人工智能的定義　3
1.0.2　思維是什么？智能是什么？　3
1.1　圖靈測試　5
1.1.1　圖靈測試的定義　6
1.1.2　圖靈測試的爭議和批評　8
1.2　強人工智能與弱人工智能　9
1.3　啟發(fā)法　11
1.3.1　長方體的對角線：解決一個相對簡單但相關的
問題　11
1.3.2　水壺問題：向后倒推　12
1.4　識別適用人工智能來求解的問題　13
1.5　應用和方法　15
1.5.1　搜索算法和拼圖　16
1.5.2　二人博弈　18
1.5.3　自動推理　18
1.5.4　產(chǎn)生式規(guī)則和專家系統(tǒng)　19
1.5.5　細胞自動機　20
1.5.6　神經(jīng)計算　21
1.5.7　遺傳算法　23
1.5.8　知識表示　23
1.5.9　不確定性推理　24
1.6　人工智能的早期歷史　25
1.7　人工智能的近期歷史到現(xiàn)在　29
1.7.1　博弈　29
1.7.2　專家系統(tǒng)　30
1.7.3　神經(jīng)計算　31
1.7.4　進化計算　31
1.7.5　自然語言處理　32
1.7.6　生物信息學　34
1.8　新千年人工智能的發(fā)展　34
1.9　本章小結　36
第二部分　基礎知識
第　2章盲目搜索　46
2.0　簡介：智能系統(tǒng)中的搜索　46
2.1　狀態(tài)空間圖　47
2.2　生成與測試范式　49
2.2.1　回溯　50
2.2.2　貪婪算法　54
2.2.3　旅行銷售員問題　56
2.3　盲目搜索算法　58
2.3.1　深度優(yōu)先搜索　58
2.3.2　廣度優(yōu)先搜索　60
2.4　盲目搜索算法的實現(xiàn)和比較　63
2.4.1　實現(xiàn)深度優(yōu)先搜索　63
2.4.2　實現(xiàn)廣度優(yōu)先搜索　65
2.4.3　問題求解性能的測量指標　65
2.4.4　DFS和BFS的比較　66
2.5　本章小結　68
第3章　知情搜索　74
3.0　引言　74
3.1　啟發(fā)法　76
3.2　知情搜索（第一部分）——找到任何解　81
3.2.1　爬山法　81
3.2.2　最陡爬坡法　82
3.3　最佳優(yōu)先搜索　84
3.4　集束搜索　87
3.5　搜索算法的其他指標　89
3.6　知情搜索（第二部分）——找到最佳解　90
3.6.1　分支定界法　90
3.6.2　使用低估值的分支定界法　95
3.6.3　采用動態(tài)規(guī)劃的分支定界法　98
3.6.4　A*搜索　99
3.7　知情搜索（第三部分）—高級搜索算法　100
3.7.1　約束滿足搜索　100
3.7.2　與或樹　101
3.7.3　雙向搜索　102
3.8　本章小結　104
第4章　博弈中的搜索　109
4.0　引言　109
4.1　博弈樹和極小化極大評估　110
4.1.1　啟發(fā)式評估　112
4.1.2　博弈樹的極小化極大評估　112
4.2　具有α-剪枝的極小化極大算法　115
4.3　極小化極大算法的變體和改進　120
4.3.1　負極大值算法　120
4.3.2　漸進深化法　122
4.3.3　啟發(fā)式續(xù)篇和地平線效應　122
4.4　概率游戲和預期極小化極大值算法　123
4.5　博弈理論　125
迭代的囚徒困境　126
4.6　本章小結　127
第5章　人工智能中的邏輯　133
5.0　引言　133
5.1　邏輯和表示　134
5.2　命題邏輯　135
5.2.1　命題邏輯—基礎　136
5.2.2　命題邏輯中的論證　140
5.2.3　證明命題邏輯論證有效的第二種方法　141
5.3　謂詞邏輯——簡要介紹　143
5.3.1　謂詞邏輯中的合一　144
5.3.2　謂詞邏輯中的反演　146
5.3.3　將謂詞表達式轉換為子句形式　148
5.4　其他一些邏輯　151
5.4.1　二階邏輯　151
5.4.2　非單調邏輯　152
5.4.3　模糊邏輯　152
5.4.4　模態(tài)邏輯　153
5.5　本章小結　153
第6章　知識表示　160
6.0　引言　160
6.1　圖形草圖和人類視窗　163
6.2　圖和哥尼斯堡橋問題　166
6.3　搜索樹　167
6.4　表示方法的選擇　169
6.5　產(chǎn)生式系統(tǒng)　172
6.6　面向對象　172
6.7　框架法　173
6.8　腳本和概念依賴系統(tǒng)　176
6.9　語義網(wǎng)絡　179
6.10　關聯(lián)　181
6.11　新近的方法　182
6.11.1　概念地圖　182
6.11.2　概念圖　184
6.11.3　Baecker的工作　184
6.12　智能體：智能或其他　185
6.12.1　智能體的一些歷史　188
6.12.2　當代智能體　189
6.12.3　語義網(wǎng)　191
6.12.4　IBM眼中的未來世界　191
6.12.5　作者的觀點　192
6.13　本章小結　192
第7章　產(chǎn)生式系統(tǒng)　199
7.0　引言　199
7.1　背景　199
7.2　基本示例　202
7.3　CARBUYER系統(tǒng)　204
7.4　產(chǎn)生式系統(tǒng)和推導方法　208
7.4.1　沖突消解　211
7.4.2　正向鏈接　213
7.4.3　反向鏈接　214
7.5　產(chǎn)生式系統(tǒng)和細胞自動機　219
7.6　隨機過程與馬爾可夫鏈　221
7.7　本章小結　222
第三部分　基于知識的系統(tǒng)
第8章　人工智能中的不確定性　228
8.0　引言　228
8.1　模糊集　229
8.2　模糊邏輯　231
8.3　模糊推理　232
8.4　概率理論和不確定性　235
8.5　本章小結　239
第9章　專家系統(tǒng)　242
9.0　引言　242
9.1　背景　242
9.2　專家系統(tǒng)的特點　249
9.3　知識工程　250
9.4　知識獲取　252
9.5　經(jīng)典的專家系統(tǒng)　254
9.5.1　DENDRAL　254
9.5.2　MYCIN　255
9.5.3　EMYCIN　258
9.5.4　PROSPECTOR　259
9.5.5　模糊知識和貝葉斯規(guī)則　261
9.6　提高效率的方法　262
9.6.1　守護規(guī)則　262
9.6.2　Rete算法　263
9.7　基于案例的推理　264
9.8　更多最新的專家系統(tǒng)　269
9.8.1　改善就業(yè)匹配系統(tǒng)　269
9.8.2　振動故障診斷的專家系統(tǒng)　270
9.8.3　自動牙科識別　270
9.8.4　更多采用案例推理的專家系統(tǒng)　271
9.9　本章小結　271
第　10章機器學習第一部分　277
10.0　引言　277
10.1　機器學習：簡要概述　277
10.2　機器學習系統(tǒng)中反饋的作用　279
10.3　歸納學習　280
10.4　利用決策樹進行學習　282
10.5　適用于決策樹的問題　283
10.6　熵　284
10.7　使用ID3構建決策樹　285
10.8　其余問題　287
10.9　本章小結　288
第　11章機器學習第二部分：神經(jīng)網(wǎng)絡　291
11.0　引言　291
11.1　人工神經(jīng)網(wǎng)絡的研究　292
11.2　麥卡洛克-皮茨網(wǎng)絡　294
11.3　感知器學習規(guī)則　295
11.4　增量規(guī)則　303
11.5　反向傳播　308
11.6　實現(xiàn)關注點　313
11.6.1　模式分析　316
11.6.2　訓練方法　317
11.7　離散型霍普菲爾德網(wǎng)絡　318
11.8　應用領域　323
11.9　本章小結　330
第　12章受到自然啟發(fā)的搜索　337
12.0　引言　337
12.1　模擬退火　338
12.2　遺傳算法　341
12.3　遺傳規(guī)劃　349
12.4　禁忌搜索　353
12.5　螞蟻聚居地優(yōu)化　356
12.6　本章小結　359
第四部分　高級專題
第　13章自然語言處理　368
13.0　引言　368
13.1　概述：語言的問題和可能性　368
13.2　自然語言處理的歷史　371
13.2.1　基礎期（20世紀40年代和50年代）　371
13.2.2　符號與隨機方法（1957—1970）　372
13.2.3　４種范式（1970—1983）　372
13.2.4　經(jīng)驗主義和有限狀態(tài)模型（1983—1993）　373
13.2.5　大融合（1994—1999）　373
13.2.6　機器學習的興起（2000—2008）　374
13.3　句法和形式語法　374
13.3.1　語法類型　374
13.3.2　句法解析：CYK算法　379
13.4　語義分析和擴展語法　380
13.4.1　轉換語法　381
13.4.2　系統(tǒng)語法　381
13.4.3　格語法　382
13.4.4　語義語法　383
13.4.5　Schank系統(tǒng)　383
13.5　NLP中的統(tǒng)計方法　387
13.5.1　統(tǒng)計解析　387
13.5.2　機器翻譯（回顧）和IBM的Candide系統(tǒng)　388
13.5.3　詞義消歧　389
13.6　統(tǒng)計NLP的概率模型　390
13.6.1　隱馬爾可夫模型　390
13.6.2　維特比算法　391
13.7　統(tǒng)計NLP語言數(shù)據(jù)集　392
13.7.1　賓夕法尼亞州樹庫項目　392
13.7.2　WordNet　394
13.7.3　NLP中的隱喻模型　394
13.8　應用：信息提取和問答系統(tǒng)　396
13.8.1　問答系統(tǒng)　396
13.8.2　信息提取　401
13.9　現(xiàn)在和未來的研究（基于CHARNIAK的工作）　401
13.10　語音理解　402
13.11　語音理解技術的應用　405
13.12　本章小結　410
第　14章自動規(guī)劃　417
14.0　引言　417
14.1　規(guī)劃問題　418
14.1.1　規(guī)劃術語　418
14.1.2　規(guī)劃應用示例　419
14.2　一段簡短的歷史和一個著名的問題　424
14.3　規(guī)劃方法　426
14.3.1　規(guī)劃即搜索　426
14.3.2　部分有序規(guī)劃　430
14.3.3　分級規(guī)劃　432
14.3.4　基于案例的規(guī)劃　433
14.3.5　規(guī)劃方法集錦　434
14.4　早期規(guī)劃系統(tǒng)　435
14.4.1　STRIPS　435
14.4.2　NOAH　436
14.4.3　NONLIN　436
14.5　更多現(xiàn)代規(guī)劃系統(tǒng)　437
14.5.1　O-PLAN　438
14.5.2　Graphplan　439
14.5.3　規(guī)劃系統(tǒng)集錦　441
14.5.4　學習系統(tǒng)的規(guī)劃方法　441
14.5.5　SCIBox自動規(guī)劃器　442
14.6　本章小結　444
第五部分　現(xiàn)在和未來
第　15章機器人技術　452
15.0　引言　452
15.1　歷史：服務人類、仿效人類、增強人類和替代人類　455
15.1.1　早期機械機器人　455
15.1.2　電影與文學中的機器人　458
15.1.3　20世紀早期的機器人　458
15.2　技術問題　464
15.2.1　機器人的組件　464
15.2.2　運動　467
15.2.3　點機器人的路徑規(guī)劃　468
15.2.4　移動機器人運動學　469
15.3　應用：21世紀的機器人　471
15.4　本章小結　479
第　16章高級計算機博弈　482
16.0　引言　482
16.1　跳棋：從塞繆爾到舍弗爾　483
16.1.1　在跳棋博弈中用于機器學習的啟發(fā)式方法　486
16.1.2　填鴨式學習與概括　488
16.1.3　簽名表評估和棋譜學習　489
16.1.4　含有奇諾克程序的世界跳棋錦標賽　490
16.1.5　徹底解決跳棋游戲　491
16.2　國際象棋：人工智能的“果蠅”　494
16.2.1　計算機國際象棋的歷史背景　495
16.2.2　編程方法　496
16.2.3　超越地平線效應　505
16.2.4　DeepThought和DeepBlue與特級大師的比賽（1988—1995年）　505
16.3　計算機國際象棋對人工智能的貢獻　507
16.3.1　在機器中的搜索　507
16.3.2　在搜索方面，人與機器的對比　508
16.3.3　啟發(fā)式、知識和問題求解　509
16.3.4　蠻力：知識vs.搜索；表現(xiàn)vs.能力　510
16.3.5　殘局數(shù)據(jù)庫和并行計算　511
16.3.6　本書第一作者的貢獻　514
16.4　其他博弈　514
16.4.1　奧賽羅　515
16.4.2　西洋雙陸棋　516
16.4.3　橋牌　518
16.4.4　撲克　519
16.5　圍棋：人工智能的“新果蠅”？　520
16.6　本章小結　523
第　17章大事記　532
17.0　引言　532
17.1　提綱挈領——概述　532
17.2　普羅米修斯歸來　534
17.3　提綱挈領——介紹人工智能的成果　535
17.4　IBM的沃森-危險邊緣挑戰(zhàn)賽　539
17.5　21世紀的人工智能　543
17.6　本章小結　545
附錄A　CLIPS示例：專家系統(tǒng)外殼　548
附錄B　用于隱馬爾可夫鏈的維特比算法的實現(xiàn)（由HarunIftikhar提供）　552
附錄C　對計算機國際象棋的貢獻：令人驚嘆的WalterShawnBrowne　555
附錄D　應用程序和數(shù)據(jù)　559
附錄E　部分練習的答案　560