教程-人工智能第12章講稿

1、第一章 引言 1.1 人工智能研究什么？ 關(guān)于人工智能的 強(qiáng)定義和弱定義強(qiáng)： 可以讓機(jī)器THINKING 、ACTING LIKE HUMAN ； 哲學(xué)、科學(xué)問題，人的心智是如何工作的，能夠建造人工心智嗎？ *AI是探討HUMAN THINKING AND HUMAN ACTIVITIES 中那些尚未算法化的功能行為.。永遠(yuǎn)地 探索下去。*人腦的思維推理過程的機(jī)械化？*大腦的意識是什么？ *計算機(jī)能夠有自覺性和意識嗎？直覺和快速反應(yīng)的原因？ 未自覺意識到推理步，和腦中進(jìn)行了復(fù)雜推理步驟，兩者并不矛盾。弱 ：讓計算機(jī)成為有效的TOOLS FOR SIMULATING AND MODELING H

2、UMAN THINKING AND HUMAN ACTIVITIES； 工程問題 復(fù)雜系統(tǒng)的結(jié)構(gòu)、功能和智能行為: o 結(jié)構(gòu)，（由部分到全體，由元件及互連到系統(tǒng)的 構(gòu)成規(guī)律; 結(jié)構(gòu)互連與 系統(tǒng)功能、系統(tǒng)行為的關(guān)系）； o 功能，（I/O,作用，任務(wù)，目標(biāo)）； o 智能行為，（物理的或信息的運(yùn)動過程）； 輸入、輸出的反應(yīng)序列；1.2 哲學(xué)和科學(xué)中 研究 思維和智能的本質(zhì) 使用 邏輯學(xué)方法、心理學(xué)的方法、非線性動力學(xué)系統(tǒng)的方法、等 多學(xué)科：哲學(xué)，心理學(xué)，腦科學(xué)，邏輯，認(rèn)知科學(xué)，神經(jīng)生理學(xué)，語言學(xué)，計算語言學(xué)，人 工智能，非線性科學(xué)混沌Chaos ）研究 thinking ，thought ，rea

3、soning 思想、思維能力、推理能力,mind心智，意識， intelligence 智力，聰明,intentionality，consciousness 自我意識意識、自我理解是大問題：Chinese Room Problem懂得怎樣做 懂得自己作了什么例子 英翻中房間翻譯和理解 Chinese Room Problem人工建造的復(fù)雜系統(tǒng)是否能夠具有意識，懂得自己在干什么？一個房間內(nèi)，有只懂得英文的一個人，一疊用英文寫的翻譯規(guī)則和符號對照表等書籍，一疊白紙；一個小窗能夠遞進(jìn)遞出薄的紙片；房間進(jìn)行翻譯工作；在外部看，這個房間是正在進(jìn)行中文翻譯工作，但是假定該人不懂中文，書籍和表格等也談不上懂

4、得中文，那么直覺上，我們認(rèn)為這個房間的工作沒有任何談得上具有理解understanding 中文的工作。因此，這例子說明，雖然系統(tǒng)功能上正常運(yùn)行并解決問題，但談不上系統(tǒng)對其問題任務(wù)有任何理解。*Turing Test，圖靈測試的意義Alan Turing 1950提出，假設(shè) 1機(jī)器和人雙方?jīng)]有物理接觸2可以間接交流信息（打字機(jī)）3機(jī)器是否能夠讓人以為人是在和另一個人交流問題？*圖靈認(rèn)為在2000年以前，可能構(gòu)造計算機(jī)和人們交談5分鐘，并有30%的把握可以FOOL人。全面圖靈測試( 再加攝象機(jī)和行動機(jī)器人) 他的支持派的研究成果: *自動邏輯推理 :推理機(jī)械化 ；三段論，演繹邏輯推理,研究邏輯思

5、維規(guī)律；1965年光景，Robinson給出horn子句的refutation 半完全性定理.但表達(dá)不完整知識，推理的時空爆炸性等仍困難 他的反對派。存在計算機(jī)不可能解決的問題：(無法算法化的)圖靈:停機(jī)問題;(存在著計算機(jī)不能通用求解的問題類)LUCAS提出:GODEL不完全定理說明人比計算機(jī)高明，任意的形式化的公理系統(tǒng)(一組公理加一組推理規(guī)則)F都可能構(gòu)造一個GODEL命題 G(F): G(F) 是F中的合法句子, 且如果F是無矛盾的,則 G(F)在F中是真的，且 不能被F所導(dǎo)出; 例系統(tǒng) ：對象A,B,C; 關(guān)系=,; 且遵循傳遞律; 已知X=B; B=C; 問句子F： X =C ？驗證

6、F為真(驗證時相同對象可替換)? 可以導(dǎo)出否?*圖靈測試的意義：研究智能行為使實(shí)驗研究成為可能數(shù)學(xué)家的發(fā)明新形式系統(tǒng)的直覺靈感可能算法化嗎?大腦和機(jī)器的本質(zhì)區(qū)別是什么?是大腦的復(fù)雜物理結(jié)構(gòu)和物理運(yùn)動的系統(tǒng)復(fù)雜性產(chǎn)生思維嗎?大腦的意識是什么？計算機(jī)能夠有自覺性和意識嗎？意識：知道自己的當(dāng)前思維狀態(tài)和行動狀態(tài)；怎樣評判有無意識？會寫作意味著，不僅是寫作本身，而且是知道自己寫了什么； 你無法知道別人的內(nèi)部思維狀態(tài)。 科學(xué)實(shí)驗無法肯定或否定它,空調(diào)器和溫血動物中的溫度調(diào)節(jié)，有沒有思維狀態(tài)？空調(diào)器喜歡氣候涼爽、期望溫度會往下降，一個科學(xué)實(shí)驗的各個階段需要得到有關(guān)直覺和意識的測量數(shù)據(jù),但它“測量”-本身會

7、嚴(yán)重影響 直覺和意識。 知覺、自覺性、意識conscious等，不可分解性： 目前無法把意識分解為其他組成部分：紅、痛、面包香味等分解為更小的部分 思維狀態(tài)mental state它和大腦的物理狀態(tài)之間不是一一對應(yīng)的：在生 理上的新陳代謝、個別細(xì)胞的死亡，不影響知識、技能和感知經(jīng)驗的狀態(tài)大問題：意識和行為的關(guān)系，意識影響行為嗎？ 思辯性問題：碳腦到硅腦的神經(jīng)細(xì)胞置換實(shí)驗。假定科學(xué)發(fā)展到某一天，大腦內(nèi)的生物神經(jīng)元、生物神經(jīng)構(gòu)件已經(jīng)可以被硅等價物所替換，而且可以使大腦整體行為上完全不發(fā)生改變。 試問： 受試者的意識最終會有改變嗎？ 兩種回答：不變，硅腦和碳腦意識完全相同 （計算機(jī)完全可能有意識）

8、變， 硅腦和碳腦的意識不同，那么意識在碳硅替換過程中何時發(fā)生改變？ 何時？突然變化或漸變（！），很大可能是漸變； 那么意識的漸變會影響行為嗎？意識影響行為嗎？可能的回答：是！行為會相應(yīng)變化 基于神經(jīng)生理學(xué)的研究：神經(jīng)元的基本結(jié)構(gòu)和基本功能，對于低級動物到高級動物，結(jié)構(gòu)和功能在進(jìn)化，但沒有大的區(qū)別。低級動物沒有意識，只有自適應(yīng)分辨式adaptive的能力，在進(jìn)化的哪一級出現(xiàn)了意識？1.3 人工的智能 建造人工的智能，使計算機(jī)具有和人相類似的，對事件和環(huán)境的反應(yīng)和行動的 理性反映能力（行為表現(xiàn)）研究方法的特點(diǎn)是 邏輯，數(shù)學(xué)和工程， 研究方法具有工程的特點(diǎn)：難解問題的近似解決算法研究如何用計算機(jī)解決

9、需要人的復(fù)雜智慧才能解決的問題具有合理的思維能力，思維不發(fā)神經(jīng)。已知的知識和給定的目標(biāo)， 具有合理的行動能力。合理性，RATIONAL 雖然可能有時犯錯誤，但可被接受。 人工智能困難：知識的復(fù)雜性; 表達(dá)不完整知識; 推理的時空爆炸性; 學(xué)習(xí); 規(guī)劃; 多主體通信等， 沒有可靠的理論。當(dāng)前人工智能的現(xiàn)狀 重要挑戰(zhàn)問題GRAND CHALLENGE: Knowbots / Infobots Intelligent Help Desks理解你需要什么信息，Natural Language Understanding (NLU)好的翻譯 必須理解內(nèi)容，NL-Generating 說話人是帶感情的 Q

10、ualitative Reasoning量和質(zhì)， Machine Vision空間關(guān)系和時間關(guān)系, Machine Learning,歸納，類比 等等*計算機(jī)打敗國際象棋大師 1996*旅行社的旅游咨詢顧問（online的語言問答，由boston到舊金山，結(jié)果票價節(jié)省 1994）*Voyager探險者號，Marvel實(shí)時專家系統(tǒng)發(fā)現(xiàn)了一個重要問題，提前發(fā)出警告 1992*小汽車以每小時55英里的速度向前，駕駛員坐在旁邊沒有駕駛。 機(jī)器人配有攝象鏡頭、聲納探測儀、激光測距儀1993*城市交通堵塞及事故警報系統(tǒng)，十字路口 及 路段1994*內(nèi)科淋巴系統(tǒng)疾病計算機(jī)專家系統(tǒng)，對著名專家提供了有益幫助。

11、1991 GOFAI:Good Old-Fashion AI （First-order logic ;rule- based system）；Dreyfus教授對GOFAI提出批評：常識、不確定性、學(xué)習(xí)、缺乏機(jī)器人式的situated agent和環(huán)境的交互關(guān)系,等等1.4 Agent agent的 P A G E 四部特征 PAGE: Percept,Action,Goal,Environment*具有sensors感知外界環(huán)境的能力，（能夠獲得一個percept sequence），感知序列*具有對環(huán)境采取行動的能力，（一組可選的行動，包括為了得到進(jìn)一步的信息而采取的行動）*加上 具有成功

12、地達(dá)到目的（goal）之能力 給出了最終的狀態(tài)條件，和達(dá)到目的的行為過程的評價 Performance Measure*已知關(guān)于環(huán)境的一部分知識,Knowledge為什么提出Agent Paradigm？ Agent的定義*例如 打掃房間的吸塵機(jī)器人 行動：step-forward, direction-turn, tube-suck, 謂詞：agent_in(x,y); dirt_in(x,y);agent_facing(d:direction); 函數(shù)：DO(行動)： 狀態(tài) 行動 狀態(tài)*各種不同應(yīng)用環(huán)境，AGENT的特性大不一樣 交通網(wǎng)絡(luò)的交通疏導(dǎo); 因特網(wǎng)信息查詢; 多個機(jī)器人的合作裝配

13、; 空間探測; 空調(diào)自動調(diào)溫；打掃房間的吸塵機(jī)器人； 軟件deamon精靈；*環(huán)境的類型：可能是 隨時間而改變（動態(tài)性），環(huán)境可能是無法精確預(yù)測的（隨機(jī)的），環(huán)境可 能是要求開放的（應(yīng)用環(huán)境本身可以集成于多種、新的環(huán)境中；軟件精靈）；離散的（下棋機(jī)器 人）或者連續(xù)的（ SOCCER ROBOTS 空間爭搶、躲避） *AGENT方法是：Conceptualization Paradigm as well as Implementation Technique for Software applications，方法特點(diǎn)：Agents和所在的環(huán)境的關(guān)系，及時反應(yīng)能力環(huán)境有 隨機(jī)不確定, 或動態(tài)環(huán)境

14、，當(dāng)agent對環(huán)境的感知能力不完備，agent對他自己的行動在環(huán)境上引起的可能差錯、失誤 必須有所準(zhǔn)備，exception handling reactive對環(huán)境能夠自動、主動作出反應(yīng)，對自己的行為和內(nèi)部狀態(tài)有控制力goaldirected帶有實(shí)現(xiàn)規(guī)定目標(biāo)的責(zé)任，和為完成任務(wù)主動采取行動；Communication, 和其他agent的互相配合，通信協(xié)商能力； goaldirected， 和 reactive 兩者配合好 , 難objects vs agents兩者的區(qū)別agent的主動反應(yīng)能力，多個agents的并行多線程能力；是object基礎(chǔ)系統(tǒng)不具備的（除active object

15、）區(qū)別：如何 “請求執(zhí)行” A請求執(zhí)行 一個行動B：action:“Objects do it for free (A調(diào)用它)Agents do it for money（A請B幫忙執(zhí)行）”理論上說，對于AGENT只看評價性能最優(yōu)，（誰打贏了SOCCER GAME？） 而不問blief,desire,intention 并不恰當(dāng).智能不應(yīng)該僅僅是事先嵌入的死板知識，從實(shí)際經(jīng)驗（歷史的感知-行動序列）和環(huán)境的狀態(tài)變化，應(yīng)該能夠適應(yīng)多類不同的環(huán)境, 從環(huán)境中學(xué)習(xí)總結(jié)，改進(jìn)行為.由它過去獲得的全部經(jīng)驗（從經(jīng)驗學(xué)習(xí)）而不是完全基于先驗的經(jīng)驗和知識。B-D-I BELIEF-DESIRE-INTENTI

16、ONDESIRE 渴望，愿望d ； 愿望本身應(yīng)該 持續(xù)時間、持續(xù)性較久 它和GOAL（目標(biāo)）性質(zhì)上有相同處和相異之處 agent希望能夠有朝一日實(shí)現(xiàn) 在AGENT預(yù)期的一些相關(guān)可能環(huán)境狀態(tài)中，都有實(shí)現(xiàn)此目標(biāo)d的可能，持 續(xù)性, 實(shí)現(xiàn)d的辦法并不一定已經(jīng)明確， DESIRE集合中各個di 可以有矛盾不一致；必須經(jīng)過考慮審量 DELIBERATION后， 才可以得出一組互相一致的GOALSIntention 意圖 是 給出的一種性質(zhì)條件， *具有持續(xù)性，在不同的時刻具有 持續(xù)的意圖， * 可滿足性，有可能實(shí)現(xiàn)， 規(guī)定了：該AGENT所向往的各種可 能發(fā)展前途中，int應(yīng)該成立 agent的行動是和

17、滿足int密切相關(guān)的； * 但是，如果agent的知識不夠或者由于環(huán)境的其他干擾， 行動的結(jié)果將無法保證一 定滿足int，可能是不成功的；Belief 信念b, Agent對一組可能世界狀態(tài)的描述，在這可能世界集合中，對 Agent 而言，他相信都具有性質(zhì)b; Agent所具有的信息，是有關(guān)他的環(huán)境 的信息，belief可以用于選擇行動的決策 *對于當(dāng)前世界而言，信念并不保證總是真的，可能被否定或更新 *信念和知識的關(guān)系， 知識是當(dāng)前的事實(shí)證據(jù)所支持的信念；是真的； * Belief(agent, b)Belief(agent, Belief(agent, b) )Agent 的實(shí)現(xiàn)類別* R

18、eactive, Reactive with memory,自動駕駛，空調(diào)（目標(biāo)固定）*Goal-based, 潛艇尋的，目標(biāo)是用戶根據(jù)情況才確定*Utility-based, 多目標(biāo)，評價函數(shù)*Problem-Solving，事先規(guī)劃 第2章目錄 問題求解、啟發(fā)式搜索; 2.1 問題求解; 2.2 通用搜索算法 ; 2.3 啟發(fā)式搜索第二章 問題求解， 啟發(fā)式搜索2.1問題求解AGENT問題求解 = 問題的表達(dá) + 求解的控制狀態(tài)空間 是一種問題的 表達(dá)和分析方法:問題的狀態(tài)空間：從任意一個狀態(tài)出發(fā)，各種任意的操作序列所可以達(dá)到的狀態(tài)集合的全體；問題 = 初態(tài)，目標(biāo), 為達(dá)到目標(biāo)而可以采取的

19、行動集合 以及 COST函數(shù)；問題 = 初始狀態(tài)集合 + 操作集合 + 測試目標(biāo)狀態(tài)的函數(shù) + +對操作序列的評價函數(shù)搜索求解：求出由初態(tài)到目標(biāo)態(tài)的一個操作序列，滿足目標(biāo)狀態(tài)條件*搜索樹隨行動序列而不斷展開;*搜索樹和搜索網(wǎng)絡(luò)（有無 相同結(jié)點(diǎn)）,？有環(huán)的路線 *剛剛出現(xiàn)過的結(jié)點(diǎn)不要再展開 *已經(jīng)出現(xiàn)過的結(jié)點(diǎn)不要展開,查驗困難搜索樹結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)struct node problem-state-type state; /狀態(tài)，其內(nèi)容和具體應(yīng)用有關(guān)node * parent-node; / 指向父結(jié)點(diǎn)的指針int the selected operator;/該分支的行動 操作算子int pat

20、h-depth; /自根到此的深度float path-cost; / 自根到此的費(fèi)用，函數(shù)g 搜索策略的時間空間復(fù)雜性：問題常常出在空間復(fù)雜性 搜索策略的完備和最優(yōu)性：對解的好壞，有評價函數(shù), 找到解, 和 解是否最優(yōu)?是否所有各種問題都可以用狀態(tài)空間問題求解來表達(dá)？有些類型的問題并不自然地具有 “狀態(tài) 行動 新的狀態(tài)”的 描述形式，例如 *？數(shù)學(xué)公式演算，公式化簡 *？口語翻譯Function General_Search ( 問題的初態(tài) ，行動集，目標(biāo)狀態(tài)判定函數(shù)，選擇狀態(tài)的優(yōu)先策略） returns solution /可能無解，解集合為空 /初始時，把 (問題的初態(tài)集合) 作為搜索樹

21、的當(dāng)前葉結(jié)點(diǎn)集合，并 /建立 搜索樹的根結(jié)點(diǎn)；loop DOIF搜索樹已經(jīng)沒有葉結(jié)點(diǎn)，或按照(選擇狀態(tài)的優(yōu)先策略) 全部葉結(jié)點(diǎn)都不符合挑選要求 then return failure在搜索樹上 按照(狀態(tài)選擇優(yōu)先策略)選擇 一個葉結(jié)點(diǎn) IF 所選葉結(jié)點(diǎn)滿足(目標(biāo)狀態(tài)判定函數(shù)) then return solution / 相應(yīng)的解 else使用(行動集)使所選結(jié)點(diǎn)擴(kuò)展形成它的全部可能葉結(jié) 點(diǎn)，放入當(dāng)前葉結(jié)點(diǎn)集合；/當(dāng)前可擴(kuò)展候選結(jié)點(diǎn)集，一般是一個隊列，必須有排序策略 end loop基本搜索方法$廣度優(yōu)先(深度為評價函數(shù))，深度8,分支10:結(jié)點(diǎn)一億個,時間31小時(每個結(jié)點(diǎn)費(fèi)時1 ms),

22、空間11個GBYTE(每個結(jié)點(diǎn)100個字節(jié))$雙向廣度優(yōu)先（由啟始和目標(biāo)終點(diǎn)同時搜索）$深度優(yōu)先$增量式深度優(yōu)先( 深度d, 每一個給定深度d，做深度搜索，但限于= d為止),如果沒有解,則把深度常數(shù)d加一（d+）后再做. 深度d，ITERATIVE DEEPENING SEARCH2.3 Heuristic啟發(fā)式搜索Best-first search的含義：所有的前沿結(jié)點(diǎn)按照一定結(jié)點(diǎn)評價函數(shù)排序，最好的被選出加以擴(kuò)展；一般的搜索算法則只要求能夠從新舊前沿葉結(jié)點(diǎn)中挑出一個,沒有BEST-FIRST要求。 /initial-node函數(shù)（prblm-initial-state）:nodes /c

23、urrent-node當(dāng)前結(jié)點(diǎn) /expand-node函數(shù)（parnt-node,prblm-operators）:nodes /Frontier-node-set 結(jié)點(diǎn)集，所有已經(jīng)被父結(jié)點(diǎn)擴(kuò)展出來， / 但是本身尚未擴(kuò)展的結(jié)點(diǎn),亦即葉結(jié)點(diǎn) /queuing-func(frntier-set,new_nodes): frntier-set nodes; /排序排好new_nodes以及frntier-set; / queuing-func是用于評價結(jié)點(diǎn)是否適宜用于當(dāng)前擴(kuò)展 /要維護(hù)一個前沿結(jié)點(diǎn)集合，對此函數(shù)queuing-func /的性質(zhì)未加限制, Function best-first-search (problem, queuing-func) return solutionfrntier-set = initial-node(prblm-initial-state）;loopif frntier-set is empty then return failure;currnt-node = top(frntier-set);if currnt-node satisfies the prblm goal-test then return currnt-node;frntier-set = queuing-func(frntier-set, exp