人工智能（第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　強(qiáng)人工智能與弱人工智能　9
1.3　啟發(fā)法　11
1.3.1　長方體的對角線：解決一個(gè)相對簡單但相關(guān)的
問題　11
1.3.2　水壺問題：向后倒推　12
1.4　識別適用人工智能來求解的問題　13
1.5　應(yīng)用和方法　15
1.5.1　搜索算法和拼圖　16
1.5.2　二人博弈　18
1.5.3　自動(dòng)推理　18
1.5.4　產(chǎn)生式規(guī)則和專家系統(tǒng)　19
1.5.5　細(xì)胞自動(dòng)機(jī)　20
1.5.6　神經(jīng)計(jì)算　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)計(jì)算　31
1.7.4　進(jìn)化計(jì)算　31
1.7.5　自然語言處理　32
1.7.6　生物信息學(xué)　34
1.8　新千年人工智能的發(fā)展　34
1.9　本章小結(jié)　36
第二部分　基礎(chǔ)知識
第　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　盲目搜索算法的實(shí)現(xiàn)和比較　63
2.4.1　實(shí)現(xiàn)深度優(yōu)先搜索　63
2.4.2　實(shí)現(xiàn)廣度優(yōu)先搜索　65
2.4.3　問題求解性能的測量指標(biāo)　65
2.4.4　DFS和BFS的比較　66
2.5　本章小結(jié)　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　搜索算法的其他指標(biāo)　89
3.6　知情搜索（第二部分）——找到最佳解　90
3.6.1　分支定界法　90
3.6.2　使用低估值的分支定界法　95
3.6.3　采用動(dòng)態(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　本章小結(jié)　104
第4章　博弈中的搜索　109
4.0　引言　109
4.1　博弈樹和極小化極大評估　110
4.1.1　啟發(fā)式評估　112
4.1.2　博弈樹的極小化極大評估　112
4.2　具有α-剪枝的極小化極大算法　115
4.3　極小化極大算法的變體和改進(jìn)　120
4.3.1　負(fù)極大值算法　120
4.3.2　漸進(jìn)深化法　122
4.3.3　啟發(fā)式續(xù)篇和地平線效應(yīng)　122
4.4　概率游戲和預(yù)期極小化極大值算法　123
4.5　博弈理論　125
迭代的囚徒困境　126
4.6　本章小結(jié)　127
第5章　人工智能中的邏輯　133
5.0　引言　133
5.1　邏輯和表示　134
5.2　命題邏輯　135
5.2.1　命題邏輯—基礎(chǔ)　136
5.2.2　命題邏輯中的論證　140
5.2.3　證明命題邏輯論證有效的第二種方法　141
5.3　謂詞邏輯——簡要介紹　143
5.3.1　謂詞邏輯中的合一　144
5.3.2　謂詞邏輯中的反演　146
5.3.3　將謂詞表達(dá)式轉(zhuǎn)換為子句形式　148
5.4　其他一些邏輯　151
5.4.1　二階邏輯　151
5.4.2　非單調(diào)邏輯　152
5.4.3　模糊邏輯　152
5.4.4　模態(tài)邏輯　153
5.5　本章小結(jié)　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　面向?qū)ο蟆?72
6.7　框架法　173
6.8　腳本和概念依賴系統(tǒng)　176
6.9　語義網(wǎng)絡(luò)　179
6.10　關(guān)聯(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　當(dāng)代智能體　189
6.12.3　語義網(wǎng)　191
6.12.4　IBM眼中的未來世界　191
6.12.5　作者的觀點(diǎn)　192
6.13　本章小結(jié)　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)和推導(dǎo)方法　208
7.4.1　沖突消解　211
7.4.2　正向鏈接　213
7.4.3　反向鏈接　214
7.5　產(chǎn)生式系統(tǒng)和細(xì)胞自動(dòng)機(jī)　219
7.6　隨機(jī)過程與馬爾可夫鏈　221
7.7　本章小結(jié)　222
第三部分　基于知識的系統(tǒng)
第8章　人工智能中的不確定性　228
8.0　引言　228
8.1　模糊集　229
8.2　模糊邏輯　231
8.3　模糊推理　232
8.4　概率理論和不確定性　235
8.5　本章小結(jié)　239
第9章　專家系統(tǒng)　242
9.0　引言　242
9.1　背景　242
9.2　專家系統(tǒng)的特點(diǎn)　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　守護(hù)規(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　振動(dòng)故障診斷的專家系統(tǒng)　270
9.8.3　自動(dòng)牙科識別　270
9.8.4　更多采用案例推理的專家系統(tǒng)　271
9.9　本章小結(jié)　271
第　10章機(jī)器學(xué)習(xí)第一部分　277
10.0　引言　277
10.1　機(jī)器學(xué)習(xí)：簡要概述　277
10.2　機(jī)器學(xué)習(xí)系統(tǒng)中反饋的作用　279
10.3　歸納學(xué)習(xí)　280
10.4　利用決策樹進(jìn)行學(xué)習(xí)　282
10.5　適用于決策樹的問題　283
10.6　熵　284
10.7　使用ID3構(gòu)建決策樹　285
10.8　其余問題　287
10.9　本章小結(jié)　288
第　11章機(jī)器學(xué)習(xí)第二部分：神經(jīng)網(wǎng)絡(luò)　291
11.0　引言　291
11.1　人工神經(jīng)網(wǎng)絡(luò)的研究　292
11.2　麥卡洛克-皮茨網(wǎng)絡(luò)　294
11.3　感知器學(xué)習(xí)規(guī)則　295
11.4　增量規(guī)則　303
11.5　反向傳播　308
11.6　實(shí)現(xiàn)關(guān)注點(diǎn)　313
11.6.1　模式分析　316
11.6.2　訓(xùn)練方法　317
11.7　離散型霍普菲爾德網(wǎng)絡(luò)　318
11.8　應(yīng)用領(lǐng)域　323
11.9　本章小結(jié)　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　本章小結(jié)　359
第四部分　高級專題
第　13章自然語言處理　368
13.0　引言　368
13.1　概述：語言的問題和可能性　368
13.2　自然語言處理的歷史　371
13.2.1　基礎(chǔ)期（20世紀(jì)40年代和50年代）　371
13.2.2　符號與隨機(jī)方法（1957—1970）　372
13.2.3　４種范式（1970—1983）　372
13.2.4　經(jīng)驗(yàn)主義和有限狀態(tài)模型（1983—1993）　373
13.2.5　大融合（1994—1999）　373
13.2.6　機(jī)器學(xué)習(xí)的興起（2000—2008）　374
13.3　句法和形式語法　374
13.3.1　語法類型　374
13.3.2　句法解析：CYK算法　379
13.4　語義分析和擴(kuò)展語法　380
13.4.1　轉(zhuǎn)換語法　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)計(jì)方法　387
13.5.1　統(tǒng)計(jì)解析　387
13.5.2　機(jī)器翻譯（回顧）和IBM的Candide系統(tǒng)　388
13.5.3　詞義消歧　389
13.6　統(tǒng)計(jì)NLP的概率模型　390
13.6.1　隱馬爾可夫模型　390
13.6.2　維特比算法　391
13.7　統(tǒng)計(jì)NLP語言數(shù)據(jù)集　392
13.7.1　賓夕法尼亞州樹庫項(xiàng)目　392
13.7.2　WordNet　394
13.7.3　NLP中的隱喻模型　394
13.8　應(yīng)用：信息提取和問答系統(tǒng)　396
13.8.1　問答系統(tǒng)　396
13.8.2　信息提取　401
13.9　現(xiàn)在和未來的研究（基于CHARNIAK的工作）　401
13.10　語音理解　402
13.11　語音理解技術(shù)的應(yīng)用　405
13.12　本章小結(jié)　410
第　14章自動(dòng)規(guī)劃　417
14.0　引言　417
14.1　規(guī)劃問題　418
14.1.1　規(guī)劃術(shù)語　418
14.1.2　規(guī)劃應(yīng)用示例　419
14.2　一段簡短的歷史和一個(gè)著名的問題　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　學(xué)習(xí)系統(tǒng)的規(guī)劃方法　441
14.5.5　SCIBox自動(dòng)規(guī)劃器　442
14.6　本章小結(jié)　444
第五部分　現(xiàn)在和未來
第　15章機(jī)器人技術(shù)　452
15.0　引言　452
15.1　歷史：服務(wù)人類、仿效人類、增強(qiáng)人類和替代人類　455
15.1.1　早期機(jī)械機(jī)器人　455
15.1.2　電影與文學(xué)中的機(jī)器人　458
15.1.3　20世紀(jì)早期的機(jī)器人　458
15.2　技術(shù)問題　464
15.2.1　機(jī)器人的組件　464
15.2.2　運(yùn)動(dòng)　467
15.2.3　點(diǎn)機(jī)器人的路徑規(guī)劃　468
15.2.4　移動(dòng)機(jī)器人運(yùn)動(dòng)學(xué)　469
15.3　應(yīng)用：21世紀(jì)的機(jī)器人　471
15.4　本章小結(jié)　479
第　16章高級計(jì)算機(jī)博弈　482
16.0　引言　482
16.1　跳棋：從塞繆爾到舍弗爾　483
16.1.1　在跳棋博弈中用于機(jī)器學(xué)習(xí)的啟發(fā)式方法　486
16.1.2　填鴨式學(xué)習(xí)與概括　488
16.1.3　簽名表評估和棋譜學(xué)習(xí)　489
16.1.4　含有奇諾克程序的世界跳棋錦標(biāo)賽　490
16.1.5　徹底解決跳棋游戲　491
16.2　國際象棋：人工智能的“果蠅”　494
16.2.1　計(jì)算機(jī)國際象棋的歷史背景　495
16.2.2　編程方法　496
16.2.3　超越地平線效應(yīng)　505
16.2.4　DeepThought和DeepBlue與特級大師的比賽（1988—1995年）　505
16.3　計(jì)算機(jī)國際象棋對人工智能的貢獻(xiàn)　507
16.3.1　在機(jī)器中的搜索　507
16.3.2　在搜索方面，人與機(jī)器的對比　508
16.3.3　啟發(fā)式、知識和問題求解　509
16.3.4　蠻力：知識vs.搜索；表現(xiàn)vs.能力　510
16.3.5　殘局?jǐn)?shù)據(jù)庫和并行計(jì)算　511
16.3.6　本書第一作者的貢獻(xiàn)　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　本章小結(jié)　523
第　17章大事記　532
17.0　引言　532
17.1　提綱挈領(lǐng)——概述　532
17.2　普羅米修斯歸來　534
17.3　提綱挈領(lǐng)——介紹人工智能的成果　535
17.4　IBM的沃森-危險(xiǎn)邊緣挑戰(zhàn)賽　539
17.5　21世紀(jì)的人工智能　543
17.6　本章小結(jié)　545
附錄A　CLIPS示例：專家系統(tǒng)外殼　548
附錄B　用于隱馬爾可夫鏈的維特比算法的實(shí)現(xiàn)（由HarunIftikhar提供）　552
附錄C　對計(jì)算機(jī)國際象棋的貢獻(xiàn)：令人驚嘆的WalterShawnBrowne　555
附錄D　應(yīng)用程序和數(shù)據(jù)　559
附錄E　部分練習(xí)的答案　560