人工智慧概論.

Presentation on theme: "人工智慧概論."— Presentation transcript:

1 人工智慧概論

2 授課主要大綱 人工智慧 專家系統 類神經網路 模糊理論 資料探勘 (關聯規則、決策樹、群聚分析 ) 時間序列統計 基因演算法 離散數學之樹論
評分標準: 期末專題(100%) 利用人工智慧真正去解決一項問題 例如: 實際利用人工智慧方法解決圖形辯識的問題 或預測的問題

3 教課書 模糊理論應用與實務 儒林書局 應用類神經網路 儒林書局 作者 葉怡成編著 資料探勘 (Data Mining) 旗標書局

4 AI （Artificial Intelligence）是什麼
說到了人工智慧就應該會想到西洋棋程式，在1996年時，IBM研發出一台超級電腦"深藍"，當時就舉辦了一場西洋棋棋王大賽，是由"深藍"出戰當時世界上最頂尖的棋王Gary Kasparov，雖然最後是棋王贏了，但是贏的很驚險，到了1997年五月，"深藍"以1分之差擊敗了Kasparov，，這件事情震驚全世界，甚至有人在害怕電腦已經快取代人類了。其實，真的是非常需要電腦能夠變得很有智慧的，這樣它便能夠幫我們分擔許多的工作。 

5 AI （Artificial Intelligence）是什麼
人類的許多特性中，無疑的，是表現了某種的智慧行為在內。若我們對智慧加以描述，則可以用下述內容表示：判斷、認知（perception）、洞察（insight）、學習（learning）、 瞭解（comprehension）及推論（reasoning）。如果電腦能表現出上述的智慧行為，則是人工智慧追求的目標。

6 1. 導言 電腦最早的設計目的是從事數學運算。 隨著電腦的演進，逐漸發展出擬人化的知識表達及推論技術，讓電腦程式看起來有智慧，此為人工智慧與專家系統的發展過程。 國內學術單位在人工智慧與專家系統的發展歷史中，扮演重要角色，如：蒙恬的手寫輸入系統，指紋辨識系統，電腦象棋系統。

7 1. 導言(續) 透過知識工程的技術，也可有效整合多位專家的知識，建立具備即時反應及解析問題功能的系統。
對於決策支援、自動控制及各類診斷的問題，是十分合適的解決方式。

8 1.1 人工智慧的演進歷史 主要的人工智慧語言及知識表示法：早期的LISP及PROLOG語言、規則式(Rule-based)及框架式(Frame-based)的知識表示法，以及近期的CLIPS語言及物件式(Object-Oriented)的知識表示法等。

9 1.2 人工智慧V.S.專家系統 經典的人工智慧問題，例如各種語言翻譯、語音影像識別等的一般解決方案不容易被定義，但我們相信，縮小問題的領域更能找到有效的解決方法。 如果我們把句子的輸入方式限定為只有名詞、動詞和受詞，便能架構出一套簡單的翻譯系統。

10 1.3 何謂專家系統 專家系統是人工智慧（Artificial Intelligence, AI）的一個分支，應用大量來自人類專家 (expert) 的專業知識來解決問題。 在專家系統中，使用特定用途（special purpose）的知識及規則（rule）來解決問題，這些知識與規則被存放在知識庫（knowledge base）裏，也因此專家系統早期被稱為「知識庫專家系統」（knowledge-based expert system），亦稱為「知識庫系統」（knowledge-based system）

11 1.3 何謂專家系統 專家系統的基本觀念描述如下：

12 1.3 何謂專家系統(續) 有用的知識系統如同一個「智慧型助理」，當灌輸更多的知識給一個智慧型助理時，它的功能將變得更強大，不僅能減輕專家的負擔，並可提高解決問題的效率，因而更接近一個真正的專家。 專家系統以專注於解決某一特定問題領域為目標，此特定問題通常歸納為某一知識領域。

13 1.3 何謂專家系統 不同層面的參與人員對專家系統的看法 參與人員 看法 管理人員 專家系統可提供什麼功用？ 技術人員
1.3 何謂專家系統 不同層面的參與人員對專家系統的看法 參與人員 看法 管理人員 專家系統可提供什麼功用？ 技術人員 怎樣是發展專家系統最佳的方式？ 研究人員 如何擴展專家系統的能力？ 用戶 專家系統幫我解決什麼問題？ 時間及金錢的投資是否值得？ 開發的專家系統是否可靠？

14 1.4 為何使用專家系統 專家系統依用途分成下列幾類： 診斷系統-主要用於醫學及教學。 解釋系統-從觀察的資料中進行分析說明
1.4 為何使用專家系統 專家系統依用途分成下列幾類： 診斷系統-主要用於醫學及教學。 解釋系統-從觀察的資料中進行分析說明 監督系統-用於農業、工程、軍事及線上分析 偵錯系統-程式、電話線路、電路板偵錯 預測系統-財經、地質、氣象、石油市場預測 設計系統-計算機軟、硬體的設計系統

15 1.4 為何使用專家系統 一些開發的實例 實驗中暨使用中的專家系統及工具 領域 系統 說明 研究與開發機構 化學 工業 DENDRAL
1.4 為何使用專家系統 一些開發的實例 實驗中暨使用中的專家系統及工具 領域 系統 說明 研究與開發機構 化學 工業 DENDRAL 解析大型光譜測度儀所生成之資 料，並決定分子結構及其原子成分 HPP，史丹福大學 教育 用 GUIDON 實驗中之智慧型電腦輔函教學 (CAI)系統可針對一系列的技術領 域，提出問題並修正答案，以教 導學生正確的技能。 ITED 智慧型學習評量與診斷系統，可 依學生測驗的結果診斷其學習障 礙，並提供個人化的學習建議 暨南國際大學

16 1.4 為何使用專家系統 專家系統適用於解決以下幾種問題：
1.4 為何使用專家系統 專家系統適用於解決以下幾種問題： (1)對於沒有明確的解決方案的問題，或找不到適合的演算法。例如醫療、決策、股票投資等。 (2)只能靠經驗或憑自覺來解決的非結構性問題。 (3)危險環境下的操作問題。 (4)珍貴的知識得以保留不至於失傳。

17 1.5 發展專家系統的技術 專家系統的知識表示方式很多，目前許多廣受採用是IF THEN規則。
1.5 發展專家系統的技術 專家系統的知識表示方式很多，目前許多廣受採用是IF THEN規則。 早期人工智慧利用精密的推論但不依賴知識的方向發展，但後來專家系統的知識庫取代了耗時甚多的精密推論。 許多專家系統仍不斷在發展，大型系統包含了成千上萬條規則，具完成特定任務的小型系統大致包括數百條規則以上。 一些專家系統更能讓系統從案例中自我學習，這就是規則歸納法(Rule induction)

18 1.5 發展專家系統的技術(續) 典型的知識擷取方式

19 1.6 人工智慧與專家系統的發 展近況 專家系統被廣泛應用和開發的三點原因：
1.6 人工智慧與專家系統的發 展近況 專家系統被廣泛應用和開發的三點原因： (1)希望把專業知識相關的累積經驗保存下來，供作未來在解決相關問題的重要參考依據。 (2)希望解決專業人員缺乏的問題，甚至於希望專家系統能協助或取代部分專業人員的工作。 (3)希望藉助於電腦設備及專家系統，合理地從事需要昂貴知識的工作。

20 1.7 人工智慧與知識管理 企業在面臨挑戰和問題時，積極引入「知識管理」的概念來做好組織中知識的管理。
比爾‧蓋茲在新著「數位神經系統」中，強調企業須將資訊轉成數位型式，並利用網際網路技術，以提昇效率。 一個藉由知識管理系統而不斷學習的企業組織，才能發揮知識的最大功用，創造企業競爭優勢。 現今企業的知識管理活動大多建立在網路和資料庫的基礎上，因此透過『知識工程』的輔助來達到知識整合的目標，已是解決組織內部知識管理問題的一大利器。

21 1.8 決策支援系統 v.s. 專家系統 傳統的決策系統在應用上有以下問題： (1)使用者必須熟悉電腦及系統的使用方法
(2)使用者必須知道如何將問題利用數學模 型進行推演，並解釋獲得的結果 傳統的決策支援系統的架構中，管理人員須同時具備的電腦素養及運用數學模型解決問題的能力，對企業及個人是很困難，因此，決策支援專家系統的概念因應而生

22 解題與搜尋方法 說明決策及求解問題的描述方式，以及如何運用傳統的人工智慧搜尋方法來解決這個類型的問題。
用來解決一般的複雜問題之外，本章所提到的觀念也常被應用在遊戲的解題策略中 。

23 2.1 問題定義 (Problem formulation)
在問始運用電腦解決一個問題之前，首先要能將問題清楚的在電腦中描述。 完整的問題描通常包含大量與問題特性相關的資訊，而與這些資訊相關的知識對於找到解答有很大的幫助。

24 問題與解題狀態的定義 具體的表達方式如下： 初始狀態(initial state)。 可用的運算元(operator)的集合。
「狀態空間」(state space) 「路徑」(path)： 「目標測試」(goal test) 「路徑成本」(path cost)

25 有限狀態機器 此圖稱為「有限狀態機器」（Finite state machine）圖示法，因為這個機器的狀態個數是有限的。
有限狀態機器常用於程式語言編譯器或其他電腦程式中，用來辨識輸入字字串的正確性。 一個狀態空間對於描繪結構不明確的問題仍相當有用 結構不明確的問題是指很多不確定因素的結合，這種不確定性可以用問題空間精確表達。

26 解題狀態的評量 搜尋的效能至少可以用三種方法來評量： (1)它是否能找到答案？ (2)它是否為好的答案？
(3)需要找到解答的時間和空間的搜尋成本是什麼？ 搜尋的總成本即是路徑成本和搜尋成本的總和。

27 狀態的選擇與執行 初始狀態是「在新莊」而目標測試則是「是否在新竹？」運作元則是對應於沿著兩個城市之間的路駕車。

28 解題範例-以智慧盤遊戲為例 (the 8-puzzle problem)
圖是一3 x 3的智慧盤，其中有8個標示數字的方塊，以及一個空格。 與空格相鄰的方塊可以滑動到空格裡。

29 智慧盤遊戲 狀態：狀態描述要能分辨八個方塊個別在九個方格中的位置。為了效率起見，最好也包含空格的位置。 操作：空格向左、右、上、下移動。
目標測試：狀態是否符合圖所示的目標狀態。 路徑成本：每一步成本是1，所以路徑成本就是路徑長度。 智慧盤屬於排列組合系列的問題，這種問題通常是NP-complete，亦即當問題中的方格個數增加時，解決問題需要的時間通常會以指數的次方成長。 其中15個方格的智慧盤問題常在人工智慧中被作為測試新的搜尋演算法的標準問題。

30 搜尋策略 (Searching Strategies)
對搜尋演算法的最簡單的詮釋方式，即是以狀態空間中搜尋樹的建構過程來進行說明。 其中由樹根直接展開的節點，標記為深度是1；由深度是d的節點直接展開的節點，標記為深度是d+1。 圖顯示通用搜尋演算法在建立從新莊到新竹搜尋樹的展開路線。 新莊 基隆 板橋 台北 新店 桃園 (a) 起始狀態 (b) 展開 新莊 (c) 展開　台北

31 通用搜尋演算法 通用搜尋演算法： GENERAL-SEARCH (問題描述, 策略) 傳回 解答 或 宣告失敗 依初始狀態建立起始節點
重複以下的指令 IF 沒有可展開的節點 THEN傳回 宣告失敗 依據傳入的策略決定展開的節點 IF 有任何節點為目標節點then傳回 解答 ELSE 將展開後的節點加入搜尋樹中

32 先寬後深搜尋策略 在這個策略中，根節點會先被展開，然後再展開被根節點展開的所有節點，接著再展開它們的後繼者等。
在寬度優先的搜尋樹中，所有在深度為d的節點皆會比所有在深度為d+1的節點早被展開。

33 先寬後深搜尋策略 寬度優先搜尋法是一個非常系統化的策略，因為它會先考慮所有長度為1的路徑，然後是那些長度為2的路徑…等。
如果有解答，寬度優先搜尋法會很快的發現它； 而如果有多個解答，寬度優先搜尋法將會先發現最小路徑的目標。

34 先深後寬搜尋策略 深度優先搜尋法總是先展開一棵搜尋樹中位於最深一層的節點，只有當遇到末端節點時，才會回溯到上一層，並展開另一個較淺層的節點。

35 先深後寬搜尋策略 深度優先搜尋法的缺點為，它可能會陷在錯誤的路徑中。
因此深度優先搜尋法可能會無法從錯誤的選擇路徑中恢復到靠近搜尋樹頂端的節點 若無適當的控制，深度優先搜尋法將陷在無窮迴圈，即使最終會找到解答路徑，而這些路徑可能比最佳路徑長。

36 最佳解優先搜尋策略 它使用一些估計解答成本的測量方式，並設法朝最低成本的方向進行搜尋。
以井字遊戲為例，若電腦是“ｏ”，對手是“x”，且評估函數定義為： F(x)=同一行及對角線的其他空白個數1 +同一行及對角線的“ｏ”個數2+ Y(X) Y(X)= 0 若該一行及對角線的“x”個數為0 = –1 若該一行及對角線的“x”個數為１ = 2 若該一行及對角線的“x”個數為4

37 假設目前的盤面狀況如下： 一開始全部都是空格 A1 A2 A3 A4 A5 A6 A7 A8 A9

38 若由電腦先下，則 F(A1)=(2+2+2) 1 + (0+0+0)  2 + (0+0+0) = 6 F(A2)=(2+2) 1 + (0+0)  2 + (0+0) = 4 F(A3)=(2+2+2) 1 + (0+0+0)  2 + (0+0+0) = 6 F(A4)=(2+2) 1 + (0+0)  2 + (0+0)  2 = 4 F(A5)=( ) 1 + (0+0+0)  2 + (0+0+0) = 8 F(A6)=(2+2) 1 + (0+0)  2 + (0+0) = 4 F(A7)=(2+2+2) 1 + (0+0+0)  2 + (0+0+0) = 6 F(A8)=(2+2) 1 + (0+0)  2 + (0+0)  2 = 4 F(A9)=(2+2+2) 1 + (0+0+0)  2 + (0+0+0)  2 = 6

39 最佳解優先搜尋策略 因此電腦選擇A5；若對手選擇A1，則盤面狀況如下： X A2 A3 A4 O A6 A7 A8 A9

40 最佳解優先搜尋策略 依同樣的評估函數，可算出 F(A2)=(1+1) 1 + (1+0)  2 + (-1+0) = 3

41 由此可知，A3、A6、A7、A8 及A9都是不錯的選擇，假設電腦選擇A3；若對手選擇A7，則盤面狀況如下：
X A2 O A4 A6 A8 A9

42 最佳解優先搜尋策略 依同樣的評估函數，可算出 F(A2)=(0+1) 1 + (1+1)  2 + (-1+0) = 4

43 因此電腦選擇A4；若對手選擇A6，則盤面狀況如下：
X A2 O A8 A9

44 依同樣的評估函數，可算出 F(A2)=(0+1) 1 + (1+1)  2 + (-1+0) = 4

45 因此電腦選擇A2；若對手選擇A8，則盤面狀況如下：
X O A9 最後電腦選擇A9，雙方以合局結束