Artificial Intelligence

利用電腦做符號推理、圖形識別、學習其他形式的推理
依賴啟發式搜尋作為人工智能解決問題的技術，使用不精確、缺失、或定義不清的訊息來解決問題

答案既不精確，也不見得是最佳答案，只使用特定領域的知識，使用 meta-level 層面的知識，對解決問題的策略進行更複雜的控制，處理語言問題和句法形式問題，推理情境的重要定性特徵

Knowledge Representation

Intelligent activities:
- 使用 symbol patterns 來表示問題領域的顯著層面
- 針對這些 patterns 進行運算，以生成潛在的問題解決方案
- 從這些可能性中搜索並選擇解決方案
從訓練中歸納

Production Rules

IF: (Condition-1 and Condition-2 and Condition-3)
THEN: Take action-4
聲明性規則(Declarative rules, domain knowledge)): 說明了有關問題的事實和關係
- ex: 如果通貨膨脹，則黃金下跌
程序規則(Procedural rules, inference, meta knowledge)): 對如何解決問題提出建議
- ex: 如果系統中沒有需要的資料，就向客戶索取

Strategies for State Space Search

Data-driven

forward chaining
問題解決者會從給定的問題事實和凱便狀態的規則開始
Data-driven Search
初始問題陳述中給出了全部或大部分數據
很難形成目標或假設

Goal-driven

backward chaining
以目標為中心，找到能實現目標的規則，並 chain backward 所有連續的規則和子目標，直到得出問題的既定事實
Goal-driven Search
- 問題陳述中給出了目標或假設、很容易制定
- 問題數據不是給定的，必須由由問題解決者獲取

Rule-based expert systems

Rule 可以表示 relation、heuristics、...

production rule 儲存在 long-term memory
problem-specific information、facts 儲存在 short-term memory

structure of a rule-based expert system

Knowledge base 儲存 rule，具有 IF 條件、THEN 行動結構，當規則被觸發，就執行動作
Database 儲存 fact，當與 Knowledge base 中儲存的 IF 條件匹配時會觸發動作
Inference engine 負責推理，從而得出 expert system 的解決方案，負責將 Knowledge base 中的 rule 和 Database 中的 fact 聯繫起來
Explanation facilities 讓用戶可以對 expert system 提出詢問，從而使 expert system 進行分析
User interface 讓用戶可以有對 expert system 進行溝通的介面

system

expert system 最重要的特徵是「高質量的性能」和「解決問題的速度」

expert system 採用符號推理來解決問題，符號用來表示不同類型的 knowledge、fact、rule

Forward chaining and backward chaining

如果 expert system 需要收集訊息，並從中推理出可以推斷的訊息，就使用 forward chaining
如果需要從假設的解決方法開始，試著找事實來證明他，就使用 backward chaining

Fowrward chaining

Fowrward chaining 是 data-driven 推理，從已知數據開始，根據這些數據向前推理，每次只執行最頂層的 rule，觸發時，rule 會在 database 增加新的 fact
任何 rule 都只能執行一次，當沒有其他 rule 可以觸發時，match-fire (匹配-觸發) 循環就會停止
但是在 forward 的過程中，會執行許多 rule 與目標無關，所以如果目標只是推測一個特定的 fact，就不能用 forward chaining

Backward chaining

Backward chaining 是 goal-driven 推理，在 backward chaining 中 expert system 有目標和試圖找到證據證明目標的推理引擎，
一開始會先搜尋整個 knowledge base 已找到可能解決方案的 rule，這些 rule 需有 goal 在他們的 THEN(action) apart
如果有這樣的 rule，且其 IF 與 database 中的 data 匹配，rule 就會被觸發，goal 就會被證明

conflict resolution

解衝突的方法

啟動優先級最高的 rule
啟動最 specific 的 rule，又稱為 longest matching strategy
啟動使用了最近輸入的資料的 rule，這種方法依賴 time tag

Advantage of rule based expert system

Natural knowledge representation，expert system 可以用表達方式來解釋解決問題的過程： “在這樣那樣的情況下，我會這樣做”
- 這些表達式可以表示為 IF-THEN
將 knowledge 與其處理方式分離，讓它在使用相同 expert system 下還可以同時開發不同應用
處理不完整和不確定的 knowledge

Disadvantage of rule based expert system

rule 之間關係不透明
搜尋策略效率很差，在越大的 expert system 中搜尋

Blackboard framework

KS: Knowledge Source

將 knowledge 切割成多個 module，為每個 module 提供獨立的推理引擎
把解決問題狀態的資料儲存在 global database, blackboard
knowledge 會對 blackboard 產生變化，並根據變化，逐步找到解決問題的方案
knowledge 之間的交流與整合透過 blackboard 進行

Blackboard 是一個 central global database 用於獨立的非同步 knowledge 進行溝通

Jigsaw Puzzle Problem

小組之間無需直接交流。
每個人都是自我行動的，不存在事先建立的順序
解決方法是漸進式的（每次一塊、一次一個），並隨機應變（有機會時增加一個部分）
需要一個 monitor，它可以看到小組的情況，並可可以選擇一個人走上黑板的順序

Model-Based Reasoning

一個 knowledge-based reasoner，用於分析建立規範在物理模型系統
MBR 會對我們想要了解或修復的功能創建軟體模擬
彌補了基於啟發式方法的侷限性

Advantages and Disadvantages of MBR

Advantages
- 利用功能性和結構性知識來處理各種問題
- 當遇到新問題時，可能會退回到第一原理問題
- 可以提供因果解釋，加深對故障的理解
Disadvantages
- 需要一個 dmain model
- 缺乏對領域的描述性知識，譬如基於規則的方法
- 複雜性高
- 無法預測特殊狀況

Case-Based Reasoning

使用明確的問題數據庫來解決新的問題
解決方法可以收集

Advantages and Disadvantages of CBR

Advantages
- 可以直接從現有得歷史日誌取得案例
- 可以快速推理，用類似案例解決問題
Disadvantages
- 缺乏對案例的深入了解
- 可能誤用案例，導致錯誤
- 龐大的案例庫會導致儲存空間的問題
- 難以獲得案例索引和匹配的標準

Intelligent Agents

Agent Model 須具備那些功能
- 可完成目標任務的技能
  - 訊息檢索、訊息過濾、教學
- 自己必須擁有 Knowledge，在完成任務時所須遵循的規則
  - 要有學習能力
  - 要具備先備知識(例如對環境的知識)
- 溝通技能
  - 對用戶的技能: 互動介面、講解、社交
  - 對其他代理的技能: 集成、通訊、語言

Agent Structures

Agent(代理) = Architecture + Program

Attributes of Intelligent Agents

可以代理代表用戶執行一系列任務
可以與用戶互動
可以於用戶指定的範圍內，無須干預就可以運行(可以自動運行)
可以監控其所處環境
可以影響其所處環境
可以解釋監測到的是見，並做出適當的執行決策

Benefits of Agents

自動化
可執行重複性任務、提高生產力、可客製化、克設定訊息交互、可減少 overload、可提供通知
可學習與用戶互動、可主動提供協助、可提供輔導用戶、可以減少培訓成本

Mobile Agent

協助人們可以在移動時代理網路，提供了移動性和自主性(可自己選擇時間和地點)

Multi-Agent Systems

由多個 agent 組成的可互動的環境，著重在合作找出可解決 global problem
agent 試圖找出可以解決他們自己的 local goals 同時合作解決 global goal 的解答

Fuzzy expert systems

Expert system 在解決問題時依賴常識，當遇到模糊不清(fuzzy)的知識時，使用 fuzzy logic(用於描述 fuzzy 理論的集合)

Fuzzy logic 試圖模擬人類的語感和常識，使智能系統更人性化

Fuzzy logic 使用介於 0 和 1 之間的連續邏輯值，採用的不是黑白兩色，而是色譜，承認事物可以部份為真，部份為假

Fuzzy theory

Fuzzy set of universe 被定義為，又稱為 membership function of set

$µ$
$µ$
$µ$
$µ$

這個集合允許一系列可能的選擇
對於所有 universe 中的任何元素，membership function 等同於 the degree to 任何在集合
這個 degree 是一個介於 0 和 1 的值，表示元素在集合中的 degree of mermbership(also called membership value)

Complement

如果是模糊集，其補集的求法如下：

Mamdani fuzzy inference

輸入變量的模糊化(fuzzification)
- 獲取清晰輸入 x1 和 y1，並根據適當的 fuzzy set 確定這些輸入的 degree
規則評估
- 對輸入進行模糊化處理， $µ µ µ µ$ 並將他們應用於模糊規則的前因，若給定的模糊規則有多個前因，則使用模糊運算符(AND 或 OR) 得到一個代表模糊運算結果的評估結果
- OR fuzzy operation (union): $µ µ µ µ$
- AND fuzzy operation (intersection): $µ µ µ µ$
- 然後可能會進行剪切或縮放
聚合 (aggregation) 規則的輸出
- 聚合 (aggregation) 是統一所有規則輸出的過程，將所有規則剪切或縮放過的 membership functions 合併成一個模糊集
去模糊化(defuzzification)
- 去模糊化後輸出一個數字，最常用的方法是 centroid technique，透過找到一條垂直線將集合切割成兩個相等的質量的點，也就是重心 (COG)，代表模糊集在區間上的重心，算法為:
  $µ µ$

Genetic algorithms

case study

假設需要找出兩個變量的 maximum of 「峰值」

將問題表示出來
編碼，將問題的解轉化為染色體(也就是一組變數的編碼)，例如將染色體的和表示為二進制字串:

選擇群體的大小，例如 6，並隨機生成一組初始種群 (population)，每個解是一條染色體
然後計算每個染色體的適合度 (fitness)，透過將染色體 (16 位元字串) 分割成兩個 8 位字串，
然後將這些字串從二進制轉換成十進制
選擇一些染色體作為父代，用於生成下一代
選擇兩個父代染色體，進行 crossover 操作產生新的染色體，(例如上例為了找到 maximum of 「峰值」，使用 crossover with the probability = 0.7)
對新生成的染色體進行變異 (mutation) 操作，隨機改變某些基因位，(例如上例為了找到 maximum of 「峰值」，使用 mutation = 0.001
將新生成的染色體替換就得種群，形成新一代種群
重複步驟 4 ~ 8，值到滿足終止條件，通常為到達最大 epoch 或 fitness 明顯不再進步

Steps in the GA development

確定問題所在，定義約束條件和最佳標準
將問題區域表示為染色體
定義 fitness function 來評估染色體的性能
構建遺傳因子 (genetic operator)
運行 GA 並調整參數

Reference

許見章老師的人工智慧課程