《人工智慧--chap1》由会员分享，可在线阅读，更多相关《人工智慧--chap1（33页珍藏版）》请在金锄头文库上搜索。
1、1第一章 人工智慧導論 Introduction 高 宗 萬 北台灣科學技術學院 電 子 工 程 系2第1章 緒 論本章所學內容n1.0 演算法n1.1 什麼是人工智慧 n1.2 人工智慧的基礎 n1.3 人工智慧的歷史 n1.4 當前發展水平 n1.5 小 結 31.0 演算法 algorithmsn1984年時代雜誌： 只要把恰當的軟體放進電腦裡，它就會做 任何你想叫它做的事。機器本身的性能也 許有一定的極限，但是能用軟體做的事卻 沒有極限。n說出你的看法或評論？n你了解電腦天生的弱點？41.0 演算法問題及其解答與演算法問題 解決問題的一個演算法所有合格輸入的集合把想要的輸出 變成輸入的
2、函數任何合格的輸入想要的輸出演算法51.0 演算法 algorithmsn演算法問題：n決策(判定)問題(decision problem): Yes or Non最佳解(計算)問題(optimal solution problem)n演算法複雜度：n上限 Big “O” : f(n) = O(g(n) iff there exist positive constants c and n0 such that f(n) cg(n) for all n, n n0. n下限 Omega : f(n) = (g(n) iff there exist positive constants c and
3、 n0 such that f(n) cg(n) for all n, n n0.n上下限 Theta : f(n) = (g(n) iff there exist positive constants c1, c2 and n0 such that c1g(n) f(n) c2g(n) for all n, n n0.6常見演算法複雜度：O(1)、O(log n)、O(n)、 O(nlog n)、O(n2)、O(n3)、O(2 n) 、O(n !) 、O(n n)n1年有31.536百萬秒。函數 n10 5010030010005n50 25050015005000n*log n33 282
4、66524699966n210025001000090000百萬n3100012500百萬8位數字10位數字2 n 102416位數字31位數字91位數字302位數字n!7位數字65位數字161位數字623位數字極限大n n11位數字85位數字201位數字744位數字極限大7演算法分類n合理演算法:複雜度上限為多項式函數 Pf(n)=amnm + am-1nm-1 + + a1n + a0ex: O(1)、O(log n)、O(n)、O(nlog n)、O(n2)、O(n3)n不合理演算法:複雜度下限為超多項式函數or 指數函數 NPex: O(2 n) 、O(n!) 、O(n n)8演算法問
5、題的領域不可判定的 不可計算的可判定的可計算的高度不可計算的不可計算的難算的NP (AI領域) 好算的P 9不可計算的問題鋪地磚問題(tiling problem)n輸入：一組有限數目的地磚樣式T，地磚樣式 按一定順序指定好四個區域的顏色。n問題：對於任何有限的長方形面積，是否能只 用T中樣式的地磚，在滿足相鄰地磚的相接邊 顏色相同的條件下加以鋪滿?n答案：永遠沒有解決鋪地磚問題的演算法。n類似問題：骨牌問題(domino problem) (限制 在上半平面)、停機問題(halting problem)。10停機問題(halting problem)程式或算法A是否可能的輸入XA在X上會停嗎
6、?1. if (x!=1) 1.1 if (x%2=0) x “Can machines behave intelligently?” nTuring猜想2000年機器有30%的機會欺騙人5分鐘。n要通過Turing測試需要電腦有下列能力:了解自然語言 ,知識表示,自動推理,機器學習,電腦視覺,機器人技術。n此六大領域為近50年來AI的大部分研究內容。171.2 人工智慧的基礎1. AI雖然承襲了許多從其他領域來的想法、觀點和技巧 。從近兩千年的哲學傳統思想，理解和學習的理論已 經顯露，伴隨著心靈是由物理系統的動作所構成的這 樣的觀點。2. 從哲學，有邏輯、機率論、決策及計算的正規定理。3.
7、從心裡學，有了觀察人類心靈的工具，以及闡述所發 展的原理的科學語言。4. 從語言學，有了語言結構和意義的定理。5. 最後，從計算機科學，有了工具將AI真正實現。 18人工智慧的基楚(續)n哲學(西元前428年至今): 歐洲哲學傳統思想是由一系列對柏拉 圖的註腳所組成是它最不會引起爭議的特性描述。n數學(西元800年-至今): 哲學家為AI許多重要的概念打下基礎 ，使這些概念進入正規科學在三個領域需要數學層次的公式化 ：計算、邏輯以及機率。n經濟學(1776年-至今): 決策理論、賽局理論、作業研究、馬可 夫決策過程等領域智慧可提供經濟學中獲得最大收益之複雜決 策問題。n神經科學(1861-至今
8、): 研究大腦是如何處理資訊?，大腦是由 神經細胞(神經元)組成，簡單細胞的集合能夠導致思維、行動和 意識。 類神經網路可以提供學習、認知、計算等AI問題。19人工智慧的基楚(續)n心理學(1879-至今) : 假如生命體帶有一種本身可能行動 的模型在頭腦中，就能夠嘗試各種不同可能性，找出何者為 最佳結論，並且在各方面以更完整，更安全，並且更合適的 行為去面對緊急狀況。(Craik,1943)n電腦工程(1940-至今): 人工智慧的成功需要兩件事情：智 慧和人工。電腦毫無疑問的已經被大家公認為最有可能表現 智慧的人工方式。n控制理論(1948-至今): 人工製品要在自己的控制下運作。n語言學
9、（1957-至今）: 1957年 B. F. Skinner發表了語言 行為一書。書中全面且詳細的討論了重要的行為學家對語 言學習的看法。 201.2 人工智慧的基礎1. 研究範疇n做遊戲n證明定理n解決一般的問題( General Problem Solver )n知覺：視覺、語音n了解自然語言n專家系統：符號數學( Symbolic mathematics )、醫學診斷、化學分析、工程設計 21討論問題n我們對“智慧”一辭的假設是什麼?n有助於解決 A I 問題的技術有那些?n我們想仿效人類的智慧到何種程度?n如何才能知道我們已經寫了一個“ 有智慧”的程式?221. 什麼是AI技術n知識(
10、knowledge)的使用：提供一種解決複雜問 題的方式，這種方式利用了相關事物的結構。n抽象：提供一種方法，將重要的特性與不重要的特 性分離開來，以利處理。n搜尋：以非直接的方式解決問題。n智慧(intelligence) 與知識(knowledge)之差異n資訊(information) 與資料(data)之差異nAI運用知識的方法：可以一般化、可以被人所了 解、必須能夠易於修改 、不必具備完整性與精確 性 、減少知識量的運用。232. 如何評估“有智慧”的程式?n程式的複雜性n一般化的程度n智慧的清晰程度n程式的延展性24井字遊戲(Tic-Tac-Toc)程式1n資料結構:n棋盤:以一個
11、九維向量來表示棋盤,0表空白,1表X,2表O。n移動表:一個19,683維的向量(39);ex:0:(0,0,0,0,0,0,0,0,0)-(0,0,0,0,1,0,0,0,0)1:(0,0,0,0,0,0,0,0,1)-(0,0,0,0,2,0,0,0,1)2:(0,0,0,0,0,0,0,0,2)-(0,0,0,0,1,0,0,0,2) 。123 456 78925井字遊戲(Tic-Tac-Toc)程式1n演算法: 1.將表示棋盤向量看成3進位數字,轉換成10進位數字 ,作為索引。 2.依步驟1之索引至移動表取出存在該位置的向量。 3.依步驟2取出的向量即為遊戲之次手。n評論:n程式簡單省
12、時,移動表佔太大空間,建立費時及輸入 易錯,不具擴充性,不是有智慧的程式。26井字遊戲(Tic-Tac-Toc)程式2n資料結構:n棋盤位置:包括一個表示棋盤的九維向量,一 個下棋的移動表以及評估棋盤位置贏的可能 性的函數值。0.5-X27井字遊戲(Tic-Tac-Toc)程式2n演算法: 1.看看下了這個位置後會不會贏,若會,則給這個位置很高 的分數,使其變成最佳位置。 2.若不能贏,則考慮對手下一步可能下的位置,看看其中那 一個對我們最為不利(不斷地重複此一程序) ,假設對手 會選擇下那個對我們最為不利的位置(當然是對手最有利 的)。不管這個最不利的分數是多少,將它傳回去,變化我 們在考慮
13、的那個節點的分數。 3.分數最高的節點是最佳的選擇即為遊戲之次手。n評論:n程式費時,因為在做每一選擇之前,必須搜尋遊戲樹,具擴 充性,程式修改成其他遊戲也能用,只是加入其他遊戲的 知識和玩法即可,是有智慧的程式。281.3 人工智慧的歷史n人工智慧的孕育期(1943-1956)n早期的熱忱，偉大的前景(1952-1969)n一些實際存在的事實(1966-1974)n知識基礎的系統：能力的關鍵?(1969-1979)nAI成為工業(1980-1988)n類神經網路的重新出發(1986-至今)n最近的事件(1987-至今)n現在的發展狀況291.3 人工智慧的歷史nWarren McCulloh
14、 and Walter Pitts(1943):人工類神經元模型nDonald Hebb(1949):調整類神經元連結強度更新規則，類神經網 路學習方法nClaude Shannon(1950) and Alan Turing(1953):下棋程式nMarvin Minsky and Dean Edmonds(1951):類神經網路電腦 SNARCnJohn McCarthy(1958):人工智慧高階程式語言LISTnBernie and Widrow(1960-2):改進Hebb網路學習方法nFrank Rosenblatt(1962):改進Hebb網路學習方法perceptrons301.
15、3 人工智慧的歷史nPartrick Winston(1970):學習理論nTerry Winograd(1972):了解自然語言程式nMcDermott(1982):第一個成功的商業化專家系統 (Digital儀器公司)nBerkiner(1989):第一個擊敗人類西洋棋大師Arnold Denker的電腦程式nPomerleau(1993):自動駕車系統nIBM(1996-7):IBM Chess Machine (DEEP BLUE) Beats Humanitys Champ (Garry Kasparov ) 3.5 : 2.5 ()311.4 現在的發展狀況n自主規劃和排程: NA
16、SA(Josson et al., 2000)n賽局: IBM Chess Machine (DEEP BLUE) Beats Humanitys Champ (Garry Kasparov ) 3.5 : 2.5 () (1996-7)n自主控制: ALVINN電腦視覺系統被訓練來駕駛汽車n診斷: 淋巴結病理學與專家系統(Hecherman 1991)n後勤規劃: DART(Cross and Walker, 1994),美軍用於波斯灣 戰爭n機器人技術: 手術中使用機器人助手HipNav(DiGioia et al., 1996)n語言理解和問題求解: PROVERB(Littman et al., 1999)321.5 摘要n人工智慧是研究讓電腦能做人類做得比電腦好的工 作。n
