1、人工智能原理,(符號計算科學),Principles of Artificial Intelligence,第一章：概述,Chapter 01 Introduction,01 什么是人工智能？,Section 01 What is AI?,01 什么是人工智能？,人工智能： Artificial Intelligence (AI),Artificial Intelligence,Artificial (adj.) 人造的, 假的, 非原產(chǎn)地的。,1.1 關于智能的概念：,1.1 關于智能的概念： 智能涉及什么？,James Albus： “我相信，對智能的理解涉及理解知識怎樣獲取、表達和存儲，

2、智能行為怎樣生成，靈感、情感和直覺怎樣發(fā)展并產(chǎn)生作用，來自感官的信號怎樣轉(zhuǎn)換成符號，而符號又怎樣操作以表現(xiàn)邏輯并推理過去策劃未來，智能的機制怎樣產(chǎn)生幻想、信念、愿望、恐懼和夢，甚至善良和愛?！?01 什么是人工智能？,01 什么是人工智能？,1.1 關于智能的概念： 理解智能意味著什么？,James Albus： “我相信，在一個基本的水平上理解這些功能將是與原子核物理、相對論和分子遺傳學相提并論的科學成就?！?01 什么是人工智能？,1.2 人工智能的派別 符號計算與神經(jīng)計算,無論是符號計算學派，還是神經(jīng)計算學派，其研究的出發(fā)點都是使機器表現(xiàn)出類似生物智能行為的行為。,01 什么是人工智能？

3、,1.2 人工智能的派別 關于符號計算科學,符號主義最直接的證據(jù)是：人的邏輯思維過程是基于語言符號的。因此，符號計算科學為模擬人的大腦的邏輯思維過程提供了良好的途徑。,實現(xiàn)符號計算的機器是符號計算機。,01 什么是人工智能？,1.2 人工智能的派別 關于神經(jīng)計算科學,神經(jīng)計算反映了科學界對生物智能微觀特征的認識和理解，這種認識和理解對基于神經(jīng)信息的生物智能（包括知覺、記憶、靈感、情感、想象、概念形成、判斷、推理、學習等）的模擬有普遍的意義。,實現(xiàn)神經(jīng)計算的機器是神經(jīng)計算機。,本課程中所講述的 “人工智能” 僅限于 “符號計算科學”。這也是傳統(tǒng)意義上 Artificial Intelligenc

4、e 所具有的內(nèi)涵。,01 什么是人工智能？,1.3 課程對 AI 概念的限定 僅僅意味著符號計算,01 什么是人工智能？,1.3 科學界的人工智能觀 Winston 的 AI 觀,Winston 說： “實際上，下一個一般性的定義似乎是不可能的，因為智能似乎是一個包含著許多的信息處理和信息表達技能的混合體?！?01 什么是人工智能？,1.3 科學界的人工智能觀 Graham 的 AI 觀,Graham 說： “人工智能是計算機科學的一個分支，他用計算機程序來做某些事情，這些事情如果讓人來做的話，就需要智能。”,“至于說，能不能把做這些事情的計算機叫做有智能的，那就由你了。”,01 什么是人工智

5、能？,1.3 科學界的人工智能觀 傅京孫的 AI 觀,傅京孫在上世紀 70 年代初期曾說： “人工智能是一門新興的邊緣學科，其核心是符號模型和符號運算。 ”,01 什么是人工智能？,1.3 科學界的人工智能觀 Nilsson 的 AI 觀,Nilsson 說：“概括地講，人工智能是關于以人工制品的形式存在的智能行為的科學?！?“智能行為依次涉及感知、推理、學習、交流、以及在復雜環(huán)境中進行決策?！?“人工智能的長遠目標之一就是開發(fā)具有能與人一樣出色，甚至比人更為出色地做這些事情的機器。人工智能的另一個目標是理解這種行為，無論這種行為是表現(xiàn)在機器內(nèi)，還是表現(xiàn)在人或其它生物內(nèi)?！?“人工智能既有工程

6、的目標，又有科學的目標?！?01 什么是人工智能？,1.3 注解人工智能 AI 是邊緣科學,注：傳統(tǒng)上，人工智能歸屬計算機科學的范疇。,01 什么是人工智能？,1.3 注解人工智能 AI 的基本目標,人工智能的基本目標在于： 使機器具有類似生物的智能 使機器表現(xiàn)出類似生物的智能行為 使機器思維,按照 Nilsson 的觀點，人工智能包含兩類不同性質(zhì)的目標，即科學目標和工程目標。 (1) 科學目標：理解智能 (2) 工程目標：實現(xiàn)智能,01 什么是人工智能？,1.3 思考與練習,1-1 什么是人工智能？,1-2符號計算學派和神經(jīng)計算學派關于人工智能的基本觀點是什么？,1-3以你的觀點，人工智能研

7、究中，符號計算學和神經(jīng)計算學各具有哪些合理性或不合理性？,1-4作為一門科學，人工智能屬于什么學科？,1-5按照 Nilsson 的觀點，人工智能的科學目標是什么？工程目標又是什么？,1-6人工智能的基本目標是什么？研究的基本內(nèi)容是什么？,1-7符號運算意義下，人工智能的基本目標和研究的基本內(nèi)容是什么？,02 為什么研究 AI？,Section 02 Why AI?,02 為什么研究 AI？,2.1 算法與計算機程序 算法與運行時間,計算機是通過執(zhí)行計算機程序來進行工作的，計算機程序是算法的計算機語言形式，算法是問題求解方法的形式化描述或問題求解的步驟。,問題的求解需要算法，執(zhí)行一個算法或計算

8、機程序需要一定的時間。顯然，算法運行所需的時間與問題的大小有關。,02 為什么研究 AI？,2.2 經(jīng)典算法 定義,算法定義：一個有窮規(guī)則集合稱為一個算法，如果該集合中的規(guī)則規(guī)定了一個解決某一特定類型問題的運算序列，并具有如下特征：,(1) 有窮性：算法必定在執(zhí)行有窮步之后結(jié)束,(2) 確定性：算法的每一個步驟必須是確切定義的,(3) 輸入：算法有 0 個以上的輸入,(4) 輸出：算法有 1 個以上的輸出,(5) 能行性：算法中所有有待實現(xiàn)的運算都是相當基本的，即，它們原則上都是能夠精確地執(zhí)行的，人用筆和紙進行有限次運算可完成的。,1. 已經(jīng)證明，有相當多的同類問題，不存在任何算法可以解答其中

9、任何一個問題。,2. 即使有一種算法能解決某一類別中的所有問題，可是這個算法只對其中一些很小的問題才有實際意義；而對于其中一些較大的實際問題卻仍然無能為力。,02 為什么研究 AI？,2.2 經(jīng)典算法 存在的困難,所謂多項式時間運行算法，即運行時間 t 與問題大小 n 的多項式 nc (c=1,2,) 成正比的算法。,02 為什么研究 AI？,2.2 經(jīng)典算法 多項式時間運行算法,多項式時間運行算法被認為是： 可以實際運行的算法,所謂指數(shù)時間運行算法，即運行時間 t 與問題大小 n 的指數(shù) 2n, n!, nn 成正比的算法。,02 為什么研究 AI？,2.2 經(jīng)典算法 指數(shù)時間運行算法,指數(shù)

10、時間運行算法被認為是： 不可以實際運行的算法,02 為什么研究 AI？,2.2 經(jīng)典算法 TSP 問題,旅行推銷員問題 (Traveling Salesman Problem, TSP)：設有 n 個城市 Ci ( i = 1,2,n )，一推銷員由城市 C1 出發(fā)，必須經(jīng)過且只許經(jīng)過每個城市一次，最后返回城市 C1。求路徑最短的旅行路線。,可能的路徑數(shù)？,例：n 5 Ci 為第 i 個城市 dij 為 Ci 和 Cj 間的距離,(n1)!,02 為什么研究 AI？,2.2 經(jīng)典算法 梵塔問題,梵塔問題 (Tower-of-Hanoi Puzzle)： 設有 3 根柱子和 n 個不同直徑的圓盤

11、 Di ( i = 1,2,n )，圓盤由大到小穿在柱子 1 上。要求將圓盤移至柱子 2，并由大到小地疊放。移動圓盤時，每次只能移動 1 個，且大圓盤不能疊放在小圓盤上。,例：n 3 可能的操作次數(shù)： 2317,2n1,02 為什么研究 AI？,2.2 經(jīng)典算法 梵塔問題,梵塔問題操作次數(shù)：2n1 (n1),證明：(數(shù)學歸納法),Basis Step: n=1時，需操作1次，即：,2n1= 211=1,Inductive Step: 設 n=k 時結(jié)論成立，則 n=k+1 時，操作次數(shù)為：,(證畢),一個標準的梵塔問題是一個有 n=64 個圓盤的梵塔問題，需要對圓盤進行操作的次數(shù)為：,由人來移

12、動圓盤，假設每次操作需要 1 秒的時間，那么，此問題的求解需要多少時間呢？,02 為什么研究 AI？,2.2 經(jīng)典算法 梵塔問題,由計算機來移動圓盤，假設每次操作對應計算機的 1 次計算，那么，對于一個速度為每秒 1 千億次的計算機，求解 64 個圓盤的梵塔問題解需要多少時間呢？,02 為什么研究 AI？,2.2 經(jīng)典算法 梵塔問題,02 為什么研究 AI？,2.2 經(jīng)典算法 運行時間對照表,人類每天都會遇到許多復雜問題。對經(jīng)典算法而言，這些問題大多極其復雜，特別是一些控制、管理與決策問題。然而，人類能很好地，有效地處理和解決這些問題。,數(shù)學家認為，在人類處理的復雜問題中，某些類的問題甚至不存

13、在任何一種經(jīng)典算法能求解此類問題；而另一些類的問題，即使存在某種經(jīng)典算法能求解此類問題，這種算法也是以指數(shù)時間運行的算法，是無法實際運行的。,02 為什么研究 AI？,2.3 智能算法 人類球解復雜問題的能力,1. 經(jīng)典算法需保證對某一類問題的有效性；而人類的方法只需面向合理的或?qū)嶋H的問題，并且，特殊問題，特殊對待。,2. 經(jīng)典算法需保證對某一類問題的正確性；而人類容許某一方法對某一特殊問題的失敗，嘗試各種方法是人類問題求解方法的一部分。,3. 經(jīng)典算法需保證對某一類問題的最優(yōu)性；而人類并不追求最佳解答，只求可行解答。,02 為什么研究 AI？,2.3 智能算法 與經(jīng)典算法的區(qū)別,與經(jīng)典算法相

14、比，人類在求解實際問題方面，遠遠勝過采用經(jīng)典算法的計算機。 因此，將人類解決問題的方法移植到計算機，研究用于計算機的人工智能算法，是一個很好的想法。,02 為什么研究 AI？,2.3 智能算法 模擬人類問題球解策略,1. 搜索：象人類那樣嘗試錯誤,2. 啟發(fā)式搜索：盲目搜索會造成“組合爆炸”，從而導致算法以指數(shù)時間運行。象人類那樣利用經(jīng)驗一類的啟發(fā)性知識進行搜索，能有效避免“組合爆炸”。,3. 問題規(guī)約：象人類那樣將復雜問題化解為一些簡單的子問題，然后分別予以解決，可謂“集中優(yōu)勢兵力，各個擊破”。,4. 規(guī)劃：象人類那樣將制定一個解決復雜問題的計劃和步驟，并依計劃確定各步驟的方案。,02 為什

15、么研究 AI？,2.3 智能算法 特征,1-9人工智能的算法與經(jīng)典算法的根本差異是什么？,1-8為什么說指數(shù)時間運行算法是無法實際運行的的算法？,1-10依你的觀點，機器需要智能嗎？,02 為什么研究 AI？,2.4 思考與練習,03 機器能表現(xiàn)智能嗎？,Section 03 Can Machines be Intelligent?,03 機器能表現(xiàn)智能嗎？,3.1 Simon 和 Newell 杜撰的概念 物理符號系統(tǒng),物理符號系統(tǒng) (Physical Symbol Systems, PSS),Simon 和 Newell 試圖通過對物理符號系統(tǒng) (Physical Symbol Syste

16、ms, PSS)與智能行為關系的研究，闡明計算機表現(xiàn)智慧的可能性或計算機思維的可能性。,03 機器能表現(xiàn)智能嗎？,3.2 物理符號系統(tǒng) 相關概念,03 機器能表現(xiàn)智能嗎？,3.2 物理符號系統(tǒng) 定義,如果一個物理系統(tǒng)具有如下功能，它就是一個物理符號系統(tǒng)：,(1) 輸入符號；,(2) 輸出符號；,(3) 存儲符號；,(4) 復制符號；,(5) 條件轉(zhuǎn)移；,(6) 建立符號結(jié)構：發(fā)現(xiàn)符號關系，形成符號結(jié)構。,03 機器能表現(xiàn)智能嗎？,3.2 物理符號系統(tǒng) 體系結(jié)構,03 機器能表現(xiàn)智能嗎？,3.2 物理符號系統(tǒng) 注釋,物理符號系統(tǒng)是一種信息處理系統(tǒng)，計算機是物理符號系統(tǒng)，人的神經(jīng)系統(tǒng)也是物理符號系

17、統(tǒng)。,物理符號系統(tǒng)意味著所研究的系統(tǒng)是物質(zhì)的,物理符號系統(tǒng)的基本任務或基本功能就是辨認相同的符號，區(qū)別不同的符號。,符號可以是形象的，也可以是抽象的；即可以是文字、圖象，又可以是計算機中的電子運動模式， 或生物神經(jīng)系統(tǒng)中的生物信號模式。,03 機器能表現(xiàn)智能嗎？,3.3 物理符號系統(tǒng)假設 AI 的公理,物理符號系統(tǒng)假設 (PSS 假設，Simon 和 Newell)： 物理系統(tǒng)表現(xiàn)智能行為的充分必要條件是，它是一個物理符號系統(tǒng)。,說明：,(1)必要性意味著：只有物理符號系統(tǒng)能表現(xiàn)智能行為；,(2)充分性意味著：物理符號系統(tǒng)一定能表現(xiàn)智能行為。,03 機器能表現(xiàn)智能嗎？,3.3 物理符號系統(tǒng)假設

18、 推理,推論一：因為人是有智能的，所以，人是一個物理符號系統(tǒng)。,推論二：因為計算機是一個物理符號系統(tǒng)，所以，計算機能表現(xiàn)智能。,推論三：因為人是一個物理符號系統(tǒng)，計算機也是一個物理符號系統(tǒng)，所以，我們能用計算機來模擬人的智能行為。,03 機器能表現(xiàn)智能嗎？,3.3 物理符號系統(tǒng)假設 意義,PSS 假設 (試圖) 使人們相信： 計算機模擬智能是可行的,PSS 假設 (試圖) 建立： 人工智能科學的理論基礎,03 機器能表現(xiàn)智能嗎？,3.3 練習與思考,1-12人是物理符號系統(tǒng)嗎？為什么？,1-13計算機是物理符號系統(tǒng)嗎？為什么？,1-11描述概念：模式、符號、符號系統(tǒng)、物理系統(tǒng)、物理符號系統(tǒng)。指

19、出物理符號系統(tǒng)的基本任務。,1-14依你的觀點，計算機能思維嗎？,1-15物理符號系統(tǒng)假設的內(nèi)容是什么？Simon 和 Newell 提出 PSS 假設的目的是什么？,04 怎樣測試機器智能？,Section 04 How to Test Machine Intelligence,04 怎樣測試機器智能？,4.1 AI 的三個相關問題之一 可操作性問題,人工智能 (Artificial Intelligence) 需要回答的三個相關問題是：,(1) 必要性問題：為什么研究 AI？,(2) 可能性問題：機器能表現(xiàn)智能嗎？,(3) 可操作性問題：怎么知道機器是有智能的？,PSS 假設僅僅意味著機器

20、能模擬智能，并不意味著我們能判定一個具體的機器是否具有智能。 評測機器智能是一個關于可操作性的問題。,04 怎樣測試機器智能？,4.2 Turing 測試 關于 AI 可操作性的理念,1950 年，計算機科學的創(chuàng)始人之一，圖靈 (Turing) 提出了著名的圖靈測試 (Turing test)。,圖靈并不打算證明計算機能模擬智能，但他提供了一種方法，一種測試或評價計算機是否具有智能的方法。,如果說圖靈測試是一種方法，不如說是一種思想，一種關于 AI 可操作性的理念。,04 怎樣測試機器智能？,4.2 Turing 測試 比較機器與人的智能,詢問者 (a human),被詢問者1 (a huma

21、n),被詢問者2 (a computer),通訊界面,04 怎樣測試機器智能？,4.2 Turing 測試 基本思想及意義,圖靈測試的基本思想： 對于一項需要智能才能完成的任務，如果機器的表現(xiàn)與人的表現(xiàn)一樣出色，則機器具有智能。,圖靈測試的重要意義： 圖靈測試意味著，AI 是具有可操作性的，機器或計算機的智能是可以測試和評價的。,04 怎樣測試機器智能？,4.3 練習與思考,1-16給出“機器”的定義，并回答問題：“人是機器嗎？”,1-17設想你是圖靈測試中的詢問者，你會向被測試的人和機器提出什么樣的問題？ (至少列出三個問題),05 AI 能做什么？,Section 05 What AI C

22、an be Used for?,05 AI 能做什么？,5.1 Winston 的預測 幻想與現(xiàn)實,1977 年，Winston 在其所著的人工智能一書中說：“不難想象計算機在未來世界中的應用，以今天的標準來看，很象科學幻想。 這里舉出一些例子：,在農(nóng)業(yè)中：計算機將控制病蟲害，進行剪枝，并有選擇地收割套種的莊稼。,在采礦業(yè)中：計算機將在對人來說過于危險的條件下作業(yè)，在海底發(fā)掘錳。,05 AI 能做什么？,5.1 Winston 的預測 幻想與現(xiàn)實,在學校中：計算機把學生的問題視為要找的錯誤，它將向?qū)W生提供計算機化的超級書籍，在微處理機上顯示出軌道上運行的行星的軌跡和演奏樂譜。,在制造業(yè)中：計算

23、機將進行裝配，并檢查工作。,在醫(yī)院中：計算機將幫助診斷，監(jiān)護病人，處理治療和管理床位。,05 AI 能做什么？,5.1 Winston 的預測 幻想與現(xiàn)實,在辦公室中：計算機將編制有關人員和團體的各種表格，把問題交給適當?shù)娜?，做新聞摘要，推敲文件草案，改正拼寫和文法錯誤?！?在家庭中：計算機將考慮烹調(diào)和采購，清理地板和草地，擔負洗衣和處理生活費用等?！?給出上述例子之后，Winston 說：“當然，現(xiàn)在這些事情都是不可能的，但人工智能有助于使它們成為可能?！?05 AI 能做什么？,5.1 Winston 的預測 幻想與現(xiàn)實,Winston 七十年代談論的“科學幻想”，今天幾乎都已成為現(xiàn)實。

24、當然，這里有的事情不需要人工智能，而有的事情的確是借助于人工智能才得以實現(xiàn)或更好地實現(xiàn)，如：制造業(yè)中的 CIMS 系統(tǒng)，辦公自動化中的寫作自動化，計算機輔助教學 (CAI) 系統(tǒng)，醫(yī)療專家系統(tǒng)和智能信息系統(tǒng)等。,Winston 描述的七十年代的情形與今天的情形對照，從一個側(cè)面反映了人工智能的發(fā)展和進步，同時，也反映了計算機在表現(xiàn)人類智慧方面所具有的潛在能力。,05 AI 能做什么？,5.1 Winston 的預測 幻想與現(xiàn)實,05 AI 能做什么？,5.2 AI 能做的遠比 Winston 想象的要多 AI 的應用或相關領域,1. 定理機器證明與自動推理,2. 自然語言處理,3. 模式識別,4

25、. 自動程序設計,5. 計算機輔助教學,6. 機器視覺,7. 機器學習,8. 機器人學與機器人技術,05 AI 能做什么？,5.3 練習和思考,06 AI 歷史與現(xiàn)狀,Section 06 The Development History of AI,06 AI 的歷史與現(xiàn)狀,6.1 AI 的誕生 Dartmouth 會議,Artificial Intelligence一詞第一次出現(xiàn)，是在 1956 年達特茅斯夏季會議上。,關于 1956 年達特茅斯夏季會議：,會議發(fā)起人：McCarthy, Minsky, Lochester, Shannon 會議應邀者：More, Samuel, Newel

26、l, Simon, 等 會議地點：美國 Dartmouth 大學 會議性質(zhì)：學術研討會 研討內(nèi)容：關于用機器模擬人類智能的問題 會期：兩個月,06 AI 的歷史與現(xiàn)狀,6.1 AI 的誕生 Dartmouth 會議,人類有關“用機器模擬人類智能”的思想可以追溯到很遠，甚至可以追溯到公元前四世紀的亞里士多德時代。然而，作為一門學科，可以說，人工智能誕生于 1956 Dartmouth 夏季會議。,從達特茅斯會議算起，人工智能已走過了半個世紀的歷程。,06 AI 的歷史與現(xiàn)狀,6.1 AI 的誕生 Dartmouth 會議,在 1956 Dartmouth 會議上，Artificial Intel

27、ligence 戰(zhàn)勝了諸多可選名稱后成為“用機器模擬人類智能”這一主題的第一主題詞。,06 AI 的歷史與現(xiàn)狀,6.2 科學界對 AI 的熱情 Simon 的預測,科學界對于人工智能寄予了極高的熱情和希望。 早在人工智能誕生之時，人工智能的創(chuàng)始人之一 Simon 就對人工智能作了極為樂觀的估計，他預言：十年之內(nèi)，人工智能系統(tǒng)將戰(zhàn)勝世界象棋冠軍。,人工智能的誕生，猶如新大陸被發(fā)現(xiàn)，無數(shù)的科技工作者象淘金者涌入新大陸一般，加入到人工智能的研究領域，希望能在人工智能這片科學的處女地上找到“黃金”。,06 AI 的歷史與現(xiàn)狀,6.2 科學界對 AI 的熱情 Simon 的預測,1957 年，Simon

28、 預計在十年之內(nèi)將有 4 件事情在人工智能領域內(nèi)發(fā)生：,(1) 計算機將創(chuàng)造出具有美學價值的音樂作品；,(2) 大多數(shù)心理學定理將具有計算機程序形式；,(3) 計算機將證明具有重大意義的數(shù)學定理；,(4) 計算機將成為國際象棋世界冠軍。,06 AI 的歷史與現(xiàn)狀,6.3 AI 的四個發(fā)展階段 19562000,(1) 五十年代：神經(jīng)網(wǎng)絡時代,(2) 六十年代：弱方法時代,(3) 七十年代：知識工程時代,(4) 八十和九十年代：知識工業(yè)時代,1948 年，Nober Wiener 發(fā)表了控制論 (動物與機器中的控制和通訊),Wiener 將機器與生物的控制和通訊機制進行類比，抽象出共同特征，形成

29、控制論這么獨立的新學科。,Wiener 指出：“就其控制行為而言，所有的人工系統(tǒng)都模仿生物系統(tǒng)，但沒有任何一種生物系統(tǒng)模仿人工系統(tǒng)?！?06 AI 的歷史與現(xiàn)狀,6.3 AI 的四個發(fā)展階段 神經(jīng)網(wǎng)絡時代,Nober Wiener 的控制論的概念跨越了許多領域，因而也影響了許多領域。,控制論把生物神經(jīng)系統(tǒng)的工作原理與信息處理、控制理論、邏輯學和計算聯(lián)系在一起。,控制論的思想極大地影響了許多早期人工智能學者，并成為人工智能強勁的引潮力和人工智能誕生的原動力。,06 AI 的歷史與現(xiàn)狀,6.3 AI 的四個發(fā)展階段 神經(jīng)網(wǎng)絡時代,06 AI 的歷史與現(xiàn)狀,6.3 AI 的四個發(fā)展階段 神經(jīng)網(wǎng)絡時代

30、,Wiener 的思想及其控制論引發(fā)了科學界對生物控制機能、生物通訊機能、生物信息處理機能和生物智能進行模擬的科學研究熱情。,特別是 Wiener 關于生物神經(jīng)系統(tǒng)及其信息處理機制的觀點，引起了人們對生物神經(jīng)系統(tǒng)進行仿真研究的興趣。,Wiener 在其控制論中指出： “能夠做計算系統(tǒng)所做工作的人和動物的神經(jīng)系統(tǒng)，它們的工作單元動作起來就象繼電器。這個事實值得我們注意，這些工作單元就是所謂的神經(jīng)元或神經(jīng)細胞?！?06 AI 的歷史與現(xiàn)狀,6.3 AI 的四個發(fā)展階段 神經(jīng)網(wǎng)絡時代,在這一思想的影響下，五十年代興起了基于開關網(wǎng)的神經(jīng)系統(tǒng)模擬研究，其中較為成功和較有影響的是對青蛙視神經(jīng)的模擬。 Ro

31、senblatt 的感知器 (Perceptron) 等人工神經(jīng)網(wǎng)絡的研究也是這一時期基于 Wiener 思想的產(chǎn)物。”,一方面，常規(guī)計算方法所處理的問題為結(jié)構化問題 (Structured Problem)，而且是充分結(jié)構化問題 (Well-Structured Problem)。對于弱結(jié)構化問題 (Ill-Structured Problem) 和非結(jié)構化問題 (Non-Structured Problem)，常規(guī)算法常常是無能為力的。,另一方面，人每天都會面臨許多的弱結(jié)構化甚至非結(jié)構化問題，并且，人，特別是一個訓練有素的人，能很好的求解這些問題。,06 AI 的歷史與現(xiàn)狀,6.3 AI

32、的四個發(fā)展階段 弱方法時代,對于弱結(jié)構化問題，由于知識的不完備性，人只能運用試驗、試探和搜索的方法，在巨大的問題空間中，運用非完備的知識、經(jīng)驗和啟發(fā)性的知識，尋求可行的問題求解途徑，做計劃、設計和決策，獲取問題的可行解，而非最優(yōu)解。,Simon 和 Newell 視人工智能的任務為弱結(jié)構化問題求解。基于 PSS 假設，Simon 和 Newell 用計算機程序模擬人對弱結(jié)構化問題的求解搜索方法。,06 AI 的歷史與現(xiàn)狀,6.3 AI 的四個發(fā)展階段 弱方法時代,06 AI 的歷史與現(xiàn)狀,6.3 AI 的四個發(fā)展階段 弱方法時代,用計算機程序模擬人對弱結(jié)構化問題的求解方法，是 Simon 和

33、Newell 的基本思想。,六十年代，在這一思想的指導下，科學家們對各種求解智力難題的計算機程序進行了研究。,06 AI 的歷史與現(xiàn)狀,6.3 AI 的四個發(fā)展階段 弱方法時代,六十年代，科學家基于弱方法對計算機人工智能程序進行了諸多研究，其中，最有影響的是 Newell, Shaw 和 Simon 1958，Newell 和 Simon 1963 研究的通用問題求解器 (General Problem Solver, GPS)。這種 GPS 曾被用于如下一些簡單的智力求解問題：,Symbolic integration slagle 1963 Analogy puzzles Evans 19

34、68 Algebra word problems Bobrow 1968,06 AI 的歷史與現(xiàn)狀,6.3 AI 的四個發(fā)展階段 弱方法時代,Simon 和 Newell 的“弱方法”強調(diào)問題求解方法的重要性，注重對人腦思維過程的模擬和仿真，卻忽視了對知識的研究。,06 AI 的歷史與現(xiàn)狀,6.3 AI 的四個發(fā)展階段 知識工程時代,人求解問題的過程，是一個基于知識，應用知識的過程。,一個知識貧乏的大腦，不可能有多少智能，這就是“弱方法”為什么只能用于一些簡單和游戲性質(zhì)的的智力求解問題的原因。,七十年代，鑒于“弱方法”存在的問題，人工智能研究領域出現(xiàn)了知識工程 (Knowledge Engin

35、eering) 學派。,知識工程學派認為：沒有知識，就沒有智能；要使計算機表現(xiàn)出智能，必須給予 它知識。,06 AI 的歷史與現(xiàn)狀,6.3 AI 的四個發(fā)展階段 知識工程時代,使人工智能由弱方法的研究轉(zhuǎn)向知識工程研究的是 DENDRAL 項目。這項研究工作是 Feigenbaum 1965 年到斯坦福大學后不久開始的。,DENDRAL 研究項目：,項目負責人：Feigenbaum,項目合作者：利德伯格，杰拉西,(基于弱方法) 編寫計算機推理程序，一個可以從化學數(shù)據(jù)推斷分子假說的智能系統(tǒng)。,項目研究目標：,項目起始時間：1965 年,06 AI 的歷史與現(xiàn)狀,6.3 AI 的四個發(fā)展階段 知識工

36、程時代,DENDRAL 面臨的困難：,物理化學知識貧乏的 DENDRAL難以實現(xiàn)其從化學數(shù)據(jù)推斷分子假說的目標。,很難想象，不具有豐富的醫(yī)學知識，無論是人還是機器，能治病救人。同樣的道理，DENDRAL 需要豐富的物理化學知識。,DENDRAL 面臨的困難引起了 Feigenbaum 等人對人工智能研究的思考，并由此產(chǎn)生了知識工程的思想和知識工程學派。,06 AI 的歷史與現(xiàn)狀,6.3 AI 的四個發(fā)展階段 知識工程時代,06 AI 的歷史與現(xiàn)狀,6.3 AI 的四個發(fā)展階段 知識工程時代,在“知識就是力量”這一思想的指導下，以美國科學家 Feigenbaum 為首，開展了對基于知識的計算機系

37、統(tǒng)的研究，建造了若干在一定專業(yè)領域內(nèi)具有專家水平和實用價值的專家系統(tǒng)。,06 AI 的歷史與現(xiàn)狀,6.3 AI 的四個發(fā)展階段 知識工程時代,知識工程的目標是建造基于知識的系統(tǒng)，或稱知識基系統(tǒng) (Knowledge-Based Systems)，其最具有代表性的產(chǎn)物是：,專家系統(tǒng) (Expert Systems, ES),從某種意義上說，知識工程就是建造專家系統(tǒng)的工程。,06 AI 的歷史與現(xiàn)狀,6.3 AI 的四個發(fā)展階段 知識工程時代,06 AI 的歷史與現(xiàn)狀,6.3 AI 的四個發(fā)展階段 知識工程時代,06 AI 的歷史與現(xiàn)狀,6.3 AI 的四個發(fā)展階段 知識工程時代,知識工程使人工智

38、能有了成就感。,七十年代，知識工程使人工智能的研究達到了一個高潮。正如我國人工智能專家張鈸所說：“專家系統(tǒng)的問世，使智能在實驗室中擺弄游戲程序的 AI，一夜之間成為解決實際問題的能手。”,作為知識工程的代表，專家系統(tǒng)已成為人工智能的研究熱點之一。七十年代的專家系統(tǒng)研究熱潮至今仍在延續(xù)。,專家系統(tǒng)的成就使人們看到了知識工程的前景。專家系統(tǒng)解決實際問題的能力展現(xiàn)了智能系統(tǒng)的商用價值，由此，智能產(chǎn)業(yè)在八十年代初期開始形成。,僅管全球的智能產(chǎn)業(yè)在 1981 年只有 1 億美元，但人們對信息領域發(fā)展的預測仍然樂觀地認為，二十一世紀初，全球的智能產(chǎn)業(yè)將超過 2500 億美元。,06 AI 的歷史與現(xiàn)狀,6

39、.3 AI 的四個發(fā)展階段 知識工業(yè)時代,面對人工智能大好的發(fā)展形式，Machlup 等人在知識工程概念的基礎上，提出了一個更具感召力的概念： “知識工業(yè)” (Knowledge Industry),06 AI 的歷史與現(xiàn)狀,6.3 AI 的四個發(fā)展階段 知識工業(yè)時代,八十年代初，智能產(chǎn)業(yè)光明的前景，以及智能科學作為尖端科學所具有的戰(zhàn)略意義，促使各國政府紛紛將知識工程納入其經(jīng)濟計劃。如：,美國的 SDI 計劃 英國的 ALVEY 計劃 法國的 UNIKA 計劃 歐共體的 ESPRIT 計劃,06 AI 的歷史與現(xiàn)狀,6.3 AI 的四個發(fā)展階段 知識工業(yè)時代,中國九十年代中期開展的計算機輔助制

40、造系統(tǒng) (Computer Industry Manufacture Systems, CIMS) 研究計劃，即 CIMS 研究計劃就是“知識工業(yè)”的產(chǎn)物。,知識工業(yè)在中國的產(chǎn)物,06 AI 的歷史與現(xiàn)狀,6.3 AI 的四個發(fā)展階段 知識工業(yè)時代,1981 年 10 月，日本政府向全世界宣布了它的第五代機計算機計劃：十年內(nèi)研制出第五代計算機，即人工智能計算機，具有與人類同樣的，甚至超過人類的思維能力的超級計算機。,日本的第五代計算機計劃,06 AI 的歷史與現(xiàn)狀,6.3 AI 的四個發(fā)展階段 知識工業(yè)時代,(40-50s) 電子管的,第一代電子計算機：,(60-70s) 晶體管的,第二代電子

41、計算機：,(70-80s) 集成電路的,第三代電子計算機：,(80-90s) 超大規(guī)模集成電路的,第四代電子計算機：,第一代至第四代電子計算機都是馮 諾依曼 (Von Neumman) 型計算機。,回顧計算機的發(fā)展,06 AI 的歷史與現(xiàn)狀,6.3 AI 的四個發(fā)展階段 知識工業(yè)時代,關于 Von Neumann 型計算機,06 AI 的歷史與現(xiàn)狀,6.3 AI 的四個發(fā)展階段 知識工業(yè)時代,馮諾依曼型計算機的體系結(jié)構,馮 諾依曼型計算機以串性方式運行。,Feigenbaum 筆下的第五代計算機,06 AI 的歷史與現(xiàn)狀,6.3 AI 的四個發(fā)展階段 知識工業(yè)時代,Feigenbaum 筆下的

42、第五代計算機,06 AI 的歷史與現(xiàn)狀,6.3 AI 的四個發(fā)展階段 知識工業(yè)時代,Feigenbaum 筆下的第五代計算機,06 AI 的歷史與現(xiàn)狀,6.3 AI 的四個發(fā)展階段 知識工業(yè)時代,Feigenbaum 筆下的第五代計算機,06 AI 的歷史與現(xiàn)狀,6.3 AI 的四個發(fā)展階段 知識工業(yè)時代,人工智能的研究并不象人們一開始所期望的那樣一帆風順，成果輝煌。,七十年代：專家系統(tǒng)受到了懷疑和批評,人工智能學者對科學界的許諾，大多未能實現(xiàn)。,六十年代：游戲性質(zhì)的弱方法沒有大的作為,八十年代：日本人雄心勃勃的第五代計算機計劃以徹底地失敗而告終,五十年代：神經(jīng)網(wǎng)絡隨 Perceptron 被

43、否定,06 AI 的歷史與現(xiàn)狀,6.4 AI 面臨的困難 AI 前面的路還很長,06 AI 的歷史與現(xiàn)狀,6.5 練習與思考,1-12為什么說 Wiener 的控制論思想是人工智能誕生的原動力？,1-11 Simon 和 Newell 的“弱方法”是什么？其“弱”的含義是什么？,1-13從第一部電子計算機誕生至今，電子計算機經(jīng)歷了多少代？它們的特征是什么？第五代計算機與前四代有什么本質(zhì)上的不同？,1-14Von Neumann 機具有什么樣的基本結(jié)構？,07 AI 與計算機的成就,Section 07 The Achievements of AI & the Computer,07 AI 與計

44、算機的成就,7.1 AI 與計算機成就之一 計算機證明四色定理,1852年，畢業(yè)于倫敦大學的弗南西斯在一家科研單位負責地圖著色的工作。,弗南西斯發(fā)現(xiàn)了一種有趣的現(xiàn)象：,“似乎，每一幅地圖都可以用四種顏色進行著色，使得有共同邊界的國家都被著上不同的顏色?！?07 AI 與計算機的成就,7.1 AI 與計算機成就之一 計算機證明四色定理,這個現(xiàn)象能不能從數(shù)學上加以證明呢？弗南西斯和他在大學讀書的弟弟決心試一試。,兄弟二人為證明這一問題而使用的稿紙已經(jīng)堆成了山，可是研究工作沒有進展。,于是，弗南西斯的弟弟就這一問題請教自己的老師，著名數(shù)學家摩爾根。,07 AI 與計算機的成就,7.1 AI 與計算機

45、成就之一 計算機證明四色定理,摩爾根找不到解決這一問題的途徑，于是又寫信，向自己的好友，著名數(shù)學家密爾頓請教。,密爾頓也未能找到解決這一問題的途徑。,1872年，著名數(shù)學家凱利正式向倫敦數(shù)學學會提出了這個問題，于是四色猜想便成了世界數(shù)學界關注的問題。,07 AI 與計算機的成就,7.1 AI 與計算機成就之一 計算機證明四色定理,一開始，四色問題并為引起人們足夠的重視。數(shù)學家們低估了它的難度。,德國數(shù)論專家閔可夫斯基上拓撲課時說，四色問題之所以一直沒有獲得解決，那僅僅是由于沒有第一流的數(shù)學家來解決它。,他拿起粉筆，竟要當場給學生進行推導，結(jié)果沒有成功。,07 AI 與計算機的成就,7.1 AI

46、 與計算機成就之一 計算機證明四色定理,下一節(jié)課閔可夫斯基繼續(xù)嘗試，還是沒有成功。幾個星期過去了，閔可夫斯基仍無進展。,有一天，閔可夫斯基剛跨進教室，雷聲大作。他馬上對學生說：“上天責我自大，我也無法解決四色問題?！?一百多年來，四色猜想困擾著數(shù)學家們，沒有人能證明它，也沒有人推翻它。,07 AI 與計算機的成就,7.1 AI 與計算機成就之一 計算機證明四色定理,無數(shù)的數(shù)學家投身于四色猜想的證明。,許多人聲稱自己證明了四色猜想。然而，最后都被證明是錯誤的。,1890年，赫伍德證明了五色定理。然而，四色猜想仍然只能是四色猜想。,07 AI 與計算機的成就,7.1 AI 與計算機成就之一 計算機

47、證明四色定理,四色猜想問題刺激了大量的數(shù)學研究，促進了圖論和拓撲學等相關學科的發(fā)展，并獲得了許多的應用。,1976 年 9 月，美國數(shù)學會通報(v.82 n.3) 宣布四色定理被證明。,四色問題是怎么解決的呢？,07 AI 與計算機的成就,7.1 AI 與計算機成就之一 計算機證明四色定理,1976 年 7 月，美國的 Appel 等人用三臺大型計算機，耗時 1200 CPU 時間，進行了 100 億次邏輯判斷，證明了四色定理。,四色猜想成為四色定理。,美國當?shù)氐泥]局在當天發(fā)出的所有郵件上都加蓋了“四色足夠”的特制郵戳，以慶祝這一難題獲得解決。,07 AI 與計算機的成就,7.2 AI 與計算

48、機成就之二 “深藍”戰(zhàn)勝 Kaspanov,讓機器學會下國際象棋并戰(zhàn)勝人類國際象棋冠軍，是人工智能學者從人工智能誕生的那一天起就產(chǎn)生了的夢想。,八十年代，我國女子國際象棋大師劉適蘭在國際比賽中曾被一計算機系統(tǒng)擊敗。,1994年8月，以前保持了四屆的國際象棋冠軍 Kasparov 被一帶有 Genius-2 計算機擊敗。,盡管這些人機大戰(zhàn)是非正式的，但機器潛在的智能已初露端倪。,07 AI 與計算機的成就,7.2 AI 與計算機成就之二 “深藍”戰(zhàn)勝 Kaspanov,1996 年，就在 Kasparov 與 Deep Blue 對陣之前，代表人類國際象棋最高水平的 Kasparov 表示：“絕

49、不能讓計算機獲勝。為了捍衛(wèi)人類的尊嚴，我一定要戰(zhàn)勝深藍。”,“這話過于傲慢。他是向科學挑戰(zhàn)，最終是要失敗的?！?宋健控制論和系統(tǒng)科學與中國的緣分(1997.4),07 AI 與計算機的成就,7.2 AI 與計算機成就之二 “深藍”戰(zhàn)勝 Kaspanov,向科學挑戰(zhàn)是要失敗的,在 Simon 的預測做出整整 40 年之后，人工智能學者最富盛名的夢想，即讓機器戰(zhàn)勝國際象棋世界冠軍的夢想終于成為現(xiàn)實。,1997 年 5 月 3 日11 日，計算機與人類第二次正式比賽在美國舉行。美國 IBM 公司制造的超級計算機“更深藍 (Deeper Blue)”國際象棋世界冠軍俄羅斯的卡斯帕羅夫 (Kasparo

50、v) 對陣，結(jié)果，Deeper Blue 以 6 戰(zhàn) 2 勝 3 和 1 負的戰(zhàn)績戰(zhàn)勝 Kasparov。,07 AI 與計算機的成就,7.2 AI 與計算機成就之二 “深藍”戰(zhàn)勝 Kaspanov,Deep Blue 是 IBM 耗資上千萬美元，耗時 8 年建造起來的世界上最強大的會下國際下棋的計算機。本質(zhì)上，Deep Blue 是一個大規(guī)模并行的基于 RS/6000 超級處理器的計算機系統(tǒng)。,07 AI 與計算機的成就,7.2 AI 與計算機成就之二 “深藍”戰(zhàn)勝 Kaspanov,07 AI 與計算機的成就,7.2 AI 與計算機成就之二 “深藍”戰(zhàn)勝 Kaspanov,深藍的核心：IB

51、M RS/6000 SP 超級處理器, 高度并行的結(jié)構使 SP 三分鐘內(nèi)可計算上千億步棋,Chess Processor,每一個 CP 每秒可分析和評估兩三千個棋譜位置圖。,節(jié)點：由 8個 CP 構成,32 個節(jié)點(共256 個CP)形成 RS/6000 SP，三分鐘內(nèi)可計算上千億步棋。,07 AI 與計算機的成就,7.2 AI 與計算機成就之二 “深藍”戰(zhàn)勝 Kaspanov,項目負責人：譚崇仁 (Chung-Jen Tan),始作蛹者：許封雄 (Feng-Hsiung Hsu ),07 AI 與計算機的成就,7.2 AI 與計算機成就之二 “深藍”戰(zhàn)勝 Kaspanov,“深藍”的始作蛹者

52、許封雄,1985年，美國 Carnegie Mellon 大學一個名叫許封雄華裔博士研究生開始研究和開發(fā)一種可進行國際象棋博弈的機器，取名為“Chiptest”。,07 AI 與計算機的成就,7.2 AI 與計算機成就之二 “深藍”戰(zhàn)勝 Kaspanov,“深藍”的始作蛹者許封雄,1988年，Chiptest成為第一個國際象棋大師級計算機，為此，許封雄贏得了 Fredkin Intermediate Prize。,1989年，許封雄以他的“Chiptest”工作，獲得計算機科學博士學位，其博士學位論文主要包含兩部份內(nèi)容：(1) 國際象棋機器結(jié)構設計，(2) 并行 alpha-beta 搜索算法研究。,1989 年，許封雄進入 IBM 公司，繼續(xù)他的國際象棋博弈計算機的研究工作，并將 Chiptest 更名為 Deep Blue。經(jīng)過 12 年的努力，經(jīng)歷幾百次的失敗之后，Chiptest 最終成長為最強大的國際象棋博弈計算機 Deep Blue。,07 AI 與計算機的成就,7.2 AI 與計算機成就之二 “深藍”戰(zhàn)勝 Kaspanov,“深藍”的始作蛹者許封雄,07 AI 與計算機的成就,7.2 AI 與計算機成就之二 “深藍”戰(zhàn)勝 Ka