人工智能（第2版）

第一部分引言
第　1章人工智能概述　2
1.0　引言　2
1.0.1　人工智能的定義　3
1.0.2　思維是什么？智能是什么？　3
1.1　圖靈測(cè)試　5
1.1.1　圖靈測(cè)試的定義　6
1.1.2　圖靈測(cè)試的爭(zhēng)議和批評(píng)　8
1.2　強(qiáng)人工智能與弱人工智能　9
1.3　啟發(fā)法　11
1.3.1　長(zhǎng)方體的對(duì)角線：解決一個(gè)相對(duì)簡(jiǎn)單但相關(guān)的
問(wèn)題　11
1.3.2　水壺問(wèn)題：向后倒推　12
1.4　識(shí)別適用人工智能來(lái)求解的問(wèn)題　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ī)則和專(zhuān)家系統(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　知識(shí)表示　23
1.5.9　不確定性推理　24
1.6　人工智能的早期歷史　25
1.7　人工智能的近期歷史到現(xiàn)在　29
1.7.1　博弈　29
1.7.2　專(zhuān)家系統(tǒng)　30
1.7.3　神經(jīng)計(jì)算　31
1.7.4　進(jìn)化計(jì)算　31
1.7.5　自然語(yǔ)言處理　32
1.7.6　生物信息學(xué)　34
1.8　新千年人工智能的發(fā)展　34
1.9　本章小結(jié)　36
第二部分　基礎(chǔ)知識(shí)
第　2章盲目搜索　46
2.0　簡(jiǎn)介：智能系統(tǒng)中的搜索　46
2.1　狀態(tài)空間圖　47
2.2　生成與測(cè)試范式　49
2.2.1　回溯　50
2.2.2　貪婪算法　54
2.2.3　旅行銷(xiāo)售員問(wèn)題　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　問(wèn)題求解性能的測(cè)量指標(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　知情搜索（第三部分）—高級(jí)搜索算法　100
3.7.1　約束滿足搜索　100
3.7.2　與或樹(shù)　101
3.7.3　雙向搜索　102
3.8　本章小結(jié)　104
第4章　博弈中的搜索　109
4.0　引言　109
4.1　博弈樹(shù)和極小化極大評(píng)估　110
4.1.1　啟發(fā)式評(píng)估　112
4.1.2　博弈樹(shù)的極小化極大評(píng)估　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　謂詞邏輯——簡(jiǎn)要介紹　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章　知識(shí)表示　160
6.0　引言　160
6.1　圖形草圖和人類(lèi)視窗　163
6.2　圖和哥尼斯堡橋問(wèn)題　166
6.3　搜索樹(shù)　167
6.4　表示方法的選擇　169
6.5　產(chǎn)生式系統(tǒng)　172
6.6　面向?qū)ο蟆?72
6.7　框架法　173
6.8　腳本和概念依賴(lài)系統(tǒng)　176
6.9　語(yǔ)義網(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　語(yǔ)義網(wǎng)　191
6.12.4　IBM眼中的未來(lái)世界　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ī)過(guò)程與馬爾可夫鏈　221
7.7　本章小結(jié)　222
第三部分　基于知識(shí)的系統(tǒng)
第8章　人工智能中的不確定性　228
8.0　引言　228
8.1　模糊集　229
8.2　模糊邏輯　231
8.3　模糊推理　232
8.4　概率理論和不確定性　235
8.5　本章小結(jié)　239
第9章　專(zhuān)家系統(tǒng)　242
9.0　引言　242
9.1　背景　242
9.2　專(zhuān)家系統(tǒng)的特點(diǎn)　249
9.3　知識(shí)工程　250
9.4　知識(shí)獲取　252
9.5　經(jīng)典的專(zhuān)家系統(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　模糊知識(shí)和貝葉斯規(guī)則　261
9.6　提高效率的方法　262
9.6.1　守護(hù)規(guī)則　262
9.6.2　Rete算法　263
9.7　基于案例的推理　264
9.8　更多最新的專(zhuān)家系統(tǒng)　269
9.8.1　改善就業(yè)匹配系統(tǒng)　269
9.8.2　振動(dòng)故障診斷的專(zhuān)家系統(tǒng)　270
9.8.3　自動(dòng)牙科識(shí)別　270
9.8.4　更多采用案例推理的專(zhuān)家系統(tǒng)　271
9.9　本章小結(jié)　271
第　10章機(jī)器學(xué)習(xí)第一部分　277
10.0　引言　277
10.1　機(jī)器學(xué)習(xí)：簡(jiǎn)要概述　277
10.2　機(jī)器學(xué)習(xí)系統(tǒng)中反饋的作用　279
10.3　歸納學(xué)習(xí)　280
10.4　利用決策樹(shù)進(jìn)行學(xué)習(xí)　282
10.5　適用于決策樹(shù)的問(wèn)題　283
10.6　熵　284
10.7　使用ID3構(gòu)建決策樹(shù)　285
10.8　其余問(wèn)題　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
第四部分　高級(jí)專(zhuān)題
第　13章自然語(yǔ)言處理　368
13.0　引言　368
13.1　概述：語(yǔ)言的問(wèn)題和可能性　368
13.2　自然語(yǔ)言處理的歷史　371
13.2.1　基礎(chǔ)期（20世紀(jì)40年代和50年代）　371
13.2.2　符號(hào)與隨機(jī)方法（1957—1970）　372
13.2.3?。捶N范式（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　句法和形式語(yǔ)法　374
13.3.1　語(yǔ)法類(lèi)型　374
13.3.2　句法解析：CYK算法　379
13.4　語(yǔ)義分析和擴(kuò)展語(yǔ)法　380
13.4.1　轉(zhuǎn)換語(yǔ)法　381
13.4.2　系統(tǒng)語(yǔ)法　381
13.4.3　格語(yǔ)法　382
13.4.4　語(yǔ)義語(yǔ)法　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語(yǔ)言數(shù)據(jù)集　392
13.7.1　賓夕法尼亞州樹(shù)庫(kù)項(xiàng)目　392
13.7.2　WordNet　394
13.7.3　NLP中的隱喻模型　394
13.8　應(yīng)用：信息提取和問(wèn)答系統(tǒng)　396
13.8.1　問(wèn)答系統(tǒng)　396
13.8.2　信息提取　401
13.9　現(xiàn)在和未來(lái)的研究（基于CHARNIAK的工作）　401
13.10　語(yǔ)音理解　402
13.11　語(yǔ)音理解技術(shù)的應(yīng)用　405
13.12　本章小結(jié)　410
第　14章自動(dòng)規(guī)劃　417
14.0　引言　417
14.1　規(guī)劃問(wèn)題　418
14.1.1　規(guī)劃術(shù)語(yǔ)　418
14.1.2　規(guī)劃應(yīng)用示例　419
14.2　一段簡(jiǎn)短的歷史和一個(gè)著名的問(wèn)題　424
14.3　規(guī)劃方法　426
14.3.1　規(guī)劃即搜索　426
14.3.2　部分有序規(guī)劃　430
14.3.3　分級(jí)規(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)在和未來(lái)
第　15章機(jī)器人技術(shù)　452
15.0　引言　452
15.1　歷史：服務(wù)人類(lèi)、仿效人類(lèi)、增強(qiáng)人類(lèi)和替代人類(lèi)　455
15.1.1　早期機(jī)械機(jī)器人　455
15.1.2　電影與文學(xué)中的機(jī)器人　458
15.1.3　20世紀(jì)早期的機(jī)器人　458
15.2　技術(shù)問(wèn)題　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ì)算機(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　簽名表評(píng)估和棋譜學(xué)習(xí)　489
16.1.4　含有奇諾克程序的世界跳棋錦標(biāo)賽　490
16.1.5　徹底解決跳棋游戲　491
16.2　國(guó)際象棋：人工智能的“果蠅”　494
16.2.1　計(jì)算機(jī)國(guó)際象棋的歷史背景　495
16.2.2　編程方法　496
16.2.3　超越地平線效應(yīng)　505
16.2.4　DeepThought和DeepBlue與特級(jí)大師的比賽（1988—1995年）　505
16.3　計(jì)算機(jī)國(guó)際象棋對(duì)人工智能的貢獻(xiàn)　507
16.3.1　在機(jī)器中的搜索　507
16.3.2　在搜索方面，人與機(jī)器的對(duì)比　508
16.3.3　啟發(fā)式、知識(shí)和問(wèn)題求解　509
16.3.4　蠻力：知識(shí)vs.搜索；表現(xiàn)vs.能力　510
16.3.5　殘局?jǐn)?shù)據(jù)庫(kù)和并行計(jì)算　511
16.3.6　本書(shū)第一作者的貢獻(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　普羅米修斯歸來(lái)　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示例：專(zhuān)家系統(tǒng)外殼　548
附錄B　用于隱馬爾可夫鏈的維特比算法的實(shí)現(xiàn)（由HarunIftikhar提供）　552
附錄C　對(duì)計(jì)算機(jī)國(guó)際象棋的貢獻(xiàn)：令人驚嘆的WalterShawnBrowne　555
附錄D　應(yīng)用程序和數(shù)據(jù)　559
附錄E　部分練習(xí)的答案　560