lctseng/NCTUCS-103-2-AI-Note.md

## NCTUCS-103-2-AI-Note.md

      
    Raw
  

              NCTUCS-103-2-AI-Note.md
            
          
    AI 課本第二章以前


AI發展：1980~1990

難以開發出解決general問題的AI => 轉往解決"專業問題"

專家系統：以專業知識為基礎

規則庫+專業領域的本體(ontology)or劇本(script)
劇本：例如點餐：先點、確認、付錢、統編

類似某一種固定的流程


工業應用(而非國防

scheduling(排程)，例如何時去見哪個客戶
planing(規劃)


神經網路：machine learning

符號(symbolic)：例如紅黃綠燈，類似nomial attribute
數字((numeric)


結合市場：仍以問題解決為主，而非與人相處等等

例如智慧(傻瓜)家電、自動車等等


基本演算法+經驗法則
分散式智慧、群集智慧：尋找閒置的電腦/裝置來執行計算(例如尋找外星人


2000~2010

網路時代的AI

以網路、智慧手機為基礎


強調服務而非生產：照護機器人、聊天機器人

設計考量與生產機器人大不同，要考慮人類行為


強調對使用者了解：以使用者為基礎建模、個人化推薦等等
多人世界：不能把互動對象當作問題(不再是problem-solving)

需要更精緻的心智模型


看問題的觀點：推薦系統

觀點一：

根據產品屬性、個別使用者偏好
蒐集使用者資料與分析(但要注意個資問題)
根據特定使用者作推薦


例如搜尋系統就是一種推薦系統

搜尋系統事實上已經是先蒐尋找內容
根據使用者關鍵字與偏好決定從資料庫中找出哪些內容


觀點二：

同好 (對於多項產品評分一致的一群人)
根據同好所選的東西來推薦(同好滿意但你未使用過的產品)
例如：看過這本書的人還看過了xxx書/電影


現今常使用cookie來追蹤使用者行為
amazon為何不會要求使用者評分其書本來建立同好清單？

利用購買行為(買了甚麼書)，來建立同好清單

買了xxx書的人還買了xxx
事實上那個"人"可能不是真的某一個人


社群中的推薦系統

外掛？！由玩家推薦的idea？下一版本變成內掛？


看問題的觀點：媒合系統

雙向挑選：：職業、婚姻仲介
媒合就是雙向推薦？(公司選你，你選公司)、(她挑你，你挑她)
觀點一：如何在媒合系統勝出？(對方：你想要申請/追求的對象)

level 1：呈現自己最好的，期待對方欣賞 (並沒有考慮到對方想法與競爭對手)
level 2：猜測對方好惡，包裝自己
level 3：猜測、了解競爭對手，提升自己排名好被優先推薦

SEO：search engine optimization
外面想要衝高自己產品在搜尋引擎上的排行
搜尋引擎公司極力反制SEO


觀點二：如何在電視媒合節目勝出？

勝利條件：你挑她，她挑你
前提：你會知道上一輪誰挑了你
如果有人挑你，但是你沒挑她，那下一輪要不要再挑她？
如果你挑了某人，但是她沒挑你，那下一輪要不要再挑同一人？


在多回合賽局中，各回合要採取甚麼？
猜測對方會怎麼做？我該怎麼調整？

如果對方是台下家人的指示，那你該如何調整？


在電視平台上，你的對象是誰？

目標不是跟到場的配對，而是想與廣大的觀眾宣傳？


What's AI？


分類：動詞+副詞
動詞：

Thinking：思考模式
Acting：行動模式


副詞：

rationally：理性的，例如給予某種刺激與規則，下次會不會因上次結果而改變？
humanly：人性的，類似於人類行為/思考


Acting humanly：Tuning test

如何做出行動像人？
tuning test：

屏幕左：詢問者
屏幕右：電腦AI系統或者是人
詢問者詢問各種問題，如果詢問者無法區別出屏幕右邊是誰，該機器就通過tuning test


Tuning：預測在2000年之前一台機器可以唬一個普通人長達五分鐘
AI的主要成分：

知識(學習與儲存)、推理、語言了解、學習


Thinking humanly：cognitive moding：認知模型

如何像人一般思考？
Top-Down：以人類行為的方式來做
Bottom-up：從神經元模擬的方式


腦科學與AI仍然是獨立的領域
Thinking rationally

哲學、公孫子(白馬非馬)
邏輯發展
接近演算法
問題：思考的目的是甚麼？


Acting rationally

Rational behavior：做對的事情(比較像人)

而非只是把事情做對(很像機器)


對的事情：能夠取得最大利益、最大回報
但事實上不一定牽涉思考？

人類的反射動作(眨眼)，對人體是"對的事情"，但是沒有牽涉思考


Rational Agent

根據輸入來產生輸出
內部會有許多不同的規則等等
比較"不像人"


甚麼是"像人"


例子：遊戲(數獨、小精靈)
對題目難易的感受像人一樣

可以區別出是某人或大眾的觀感
可以出題or挑題去符合當前難度


解題程序和人一樣
像人的數獨AI

對於不同難度的解題時間和人相似：acting humanly
程式中的解題策略層次、順序與人相似：thinking humanly
甚麼是人？

一般人(generic)：例如統計學上，一般大眾的平均智慧程度(例如眾數或平均數等等)
典型人(typical)
特定人(specific)：例如針對向某一個特定的使用者服務設計的的AI


課本


當前技術

下棋、自動車、填字遊戲(crossword puzzle)、planning、scheduling
Turing test的缺陷

文化限制：換一個文化背景知識，一切都就不同了


哪一種AI的種類？

行為上 vs 認知上
是否有自我意識


不同AI的目標

Acting humanly：Turing test
Thinking humanly：cognitive
Thinking rationally：Logic
Acting rationally：Rational agents

能夠感知世界並行動
有限理性：人不可能有100%的理性 => 跟著感覺走

例如就期望值的理性面上來看，買樂透是虧的


最重要：必須要能夠處理世界給的回饋


ELIZA：心理諮商師的AI

Intelillgent Agent


Agent：能夠觀察接收外界資訊並做出行動

agent = architecture + program


例如：吸塵器

percepts (觀察)：位置、內容(是否有髒汙)
Actions (行動)：移動、吸取灰塵


Rational Agent


do the right thing

觀察到甚麼，然後從他能做的事情中做些甚麼


AI的低標
能夠進行action來獲得/修改未來能夠觀察到的東西

例如機器人移動自己的位置、蒐集新的資訊


autonomous：agent能夠利用自己的經驗來做出行動

自己能夠學習，然後應用之


PEAS


AI的基本幾個指標
Performance measure

例如自動車的安全性、速度、合法、舒適


Environment

AI適用的情況
例如自動車行駛時的路況、交通壅塞程度


Actuator

執行動作的裝置
例如自動車的方向盤、加速器、煞車


Sensor

例如自動車的攝影機、感應器等等


Environment type


Fully observable <-> partially observable

執行的環境是否能夠讓AI自己全盤了解(自己想要的資訊，自己都有辦法得到)
Fully範例：工廠內的自動機器人
Partially範例：AI與他人玩牌，AI並無法得知對方有甚麼牌


Deterministic <-> Stochastic(不確定的、有風險的)

環境的下一個狀態完全由自己當前的行為來決定
Deterministic範例：下某一步棋之後形成的下一個棋盤的狀態是確定的
Stochastic範例：哈利波特裡面的西洋棋，你要他走某一步，最後要不要走是他決定的
玩家不能100%決定棋子的行為
介於兩者之間：Strategic

環境是Deterministic，但不確定的是其他的agent
股票市場操作


Episodic <-> Sequential

單元劇vs連續劇
agent的經驗可以切割為許多"episodes，單元"
每一個單元包含了agent的觀察與"一個"最終決定的動作


Static <-> Dynamic

靜態：在做決策的時候，環境是固定的

例如下棋的時候沒有時間限制


動態：例如小精靈遊戲，隨著時間過去，環境(鬼的位置)會改變
semidynamic：半動態

環境不改變，但是隨著時間過去，agent的performace score會降低

不希望agent花太多時間決策


Discrete <-> Continuous

要做的事情是整數式、離散式，例如把棋子往前走一步or兩步，沒有0.5步
連續式：例如車子要往前走多遠，距離是連續的


Single Agent <-> Multi-agent

環境中到底有多少agent在行動


以上這些environment type會根據不同應用而變，並影響agent的設計
例如：

下棋沒有時間限制：static
下棋有時間限制：semi


真實世界通常的情況(最複雜)

partially、stochasic、sequantial、dynamic、continuous、multi-agent


Rational Agent

行為就像一個function，把輸入觀察變成輸出行為


Table-lookup agent

根據某種輸入查出表格中的答案
就像背九九乘法表，而非不斷做加法
缺點：

表格大，需要很多心力來建置表格
沒有autonomy(看不出自主性，沒有學習與應用能力)

即使有學習，也要花很多時間來學出一個良好的表格


Agent Type

AI層級((從簡單到複雜)
Simple Reflex

單純反射式agent
很像反射動作，收到資訊A，就做動作B
環境資訊->被sensor接收->判斷外界環境是甚麼->根據知識與狀況，當前該做甚麼事？->Action
沒有考慮Sensor或Actuator是否失真或失準
外界環境的資訊如何被感知？

需要轉換為內部能夠和action-condition的條件相匹配的
例如把紅綠藍三個顏色的光波長轉換成內部判斷用的RGB三個symbol
需要試想人的感覺(人看到這個東西，會產生甚麼想法？)

需要能夠篩選、壓縮接收到的訊息


Model-Base

內部擁有"世界模型"(environment model)
世界處於甚麼狀態？比起simple reflex，會多考慮世界當前處於甚麼狀況？

利用外界資訊綜合判斷
相對於Simple只會看外界的刺激來決定行為


環境資訊被sensor接收->經過多次觀察，推論出世界模型->利用模型與觀察的資訊做出行為


Goal-base

AI有自己的目標
多考慮：當我做了某一個行為之後，會發生甚麼事？
是否對自己想達成的目標有幫助？


Utility

AI有自己想做的事情
我做了某一件事情之後，我有多快樂？值不值得我去做這件事？
更加像人


Learning Agent

上述提到的都是learning element(agent的一部分)
Critic:給予一個要求的標準(例如如何精準地打到球心？)
但有時並不是精確得知該做甚麼

例如落後20分，該修正的是？換球員or換戰術？
Critic的重點就是要能夠找出一個明確的方向


Problem Generator

如何產生問題、製造狀況問自己，看自己能不能解決
難處：需要知道自己哪裡不好，來設計問題


小怪、殭屍的觀點


Fully Observable!

對於他想知道的(前面有沒有路?)，他都可以知道
非主動怪，他不會想知道玩家是不是躲在柱子後面
當然此立論建立在小怪的AI沒那麼聰明，沒想到要找出玩家


Episodic

殭屍不會顧慮到剛才發生甚麼事了
不會有殭屍剛吃飽(過去的事件)現在不想吃(影響到現在的行為)


AI inside out


智慧不一定擺在動作主體上

鴿子吃花生，智慧在花生上，指揮鴿子來吃，而非鴿子自己用AI來找花生
獸人群過橋，智慧在橋上，指揮哪些獸人過橋，而非每一個獸人自己都有複雜AI


規則組織與運作


大量規則形成規則庫，使用於大多數的專家系統

衍生問題：規則激發的順序(order)、優先權？


整合機制：平行激發規則，例如模糊系統
有層次性的規則(規則調整另一個規則)
規則自動學習

有限狀態機


可以"記憶"
Agent處於某一個狀態
因應外界狀況改變狀態並做出行動

使用"狀態"的優勢


掌握"動態"：動者恆動，並非許多靜態的連續
處理持續的行動、預設的行動

例如騎車 (沒有特別停車，就是在移動中)


把行動附屬於狀態，不用特定條件觸發
狀態加上情緒 => 更像人

例如：狀態 = 衝刺，情緒 = 吶喊


如何知道自己目前處於甚麼狀態？


透過觀察

把狀態轉為規則的條件之一 (if 在狀態A, then ...)
定義每個狀態要怎麼觀察？(用甚麼外部指標來定義當前的狀態？)
眼光從外而內，內建的自我覺察


透過記憶

比較簡單，但需要注意更新


哪些是FSM-represented reflex agent能做的事情？

- 定點守衛、固定路線範圍巡邏、表現出差異行為(是否主動、逃跑、求援)、
  集體行動與協調(隊伍間、隊伍中的協調)、合作與分工(圍毆、補血)、探索地圖

成群結隊(flocking)

- 以自然或有機的方式來移動一群生物
- 在三條簡單的規則中取得平衡：保持間距、同向、靠攏

FSM-represented reflex agent的優點

- 容易描述(設計者的構想)
- 容易實作(技術成熟，使用的計算資源少)
- 容易預測(沒有複雜的行為鏈鎖反應)
- 容易改進(邏輯清楚)
- 容易擴充(增加狀態、連結、行動)

在FSM上增加記憶能力：使用Push-down automata

- 把資訊存在stack上

簡單的反射動作能做甚麼？不能做甚麼？


能夠騎車不摔下來？Yes
能夠達到目的地？ Maybe Not

Model-based reflex agents


記錄了世界的樣貌與變化(世界的模型)、對自己行動的影響
世界模型(world model)的形式

規則庫(我是甚麼樣，就假設別人也是這樣)

世界由「別人」構成，把「別人」想成「自己」
假想：如果是我，我會怎麼做？
缺點：過於麻煩(例如小怪太多，可能會有太多規則)


FSM：將世界簡化的模型

假設世界就處於某幾個狀態


黑盒子

不知道世界怎麼運作
只知道：給予某input，就會有某output
把「別人」當作「別人」
怎麼樣對不同的世界建模？(modeling) -> 神經網路、決策樹等等


環境類型：從玩家的觀點


如同作業：pacman，如何寫程式操作pacman，而非操作ghost？

Goal-based agents


以目標為基礎的能動者
採取行動後，對世界的影響？是否更接近目標？
例如：守衛小怪

我的目標是甚麼？我該做甚麼來達成目標？

目標：不想被發現-->假裝睡著，玩家會怎麼做？


在何種條件下才能行動？

現在裝睡會不會太晚？


目標架構、行動選項
玩家建模(player modeling)

從對方的角度來看這件事(我知道你知道我知道)
玩家是否會相信我在裝睡？


最「簡單」的目標：活下去、活得好

活下去：個體的學習適應 vs 全體的演化適存？ --> 誰值得活下去？
活得好：自訂目標，展現agent的能動性

根據甚麼來自訂目標？活得好 = 快樂 or 有意義 or 其他？


Utility-based agents


以效用為基礎的能動者
例如：達成目標後我會有多高興？
"效用"的指標：例如『快樂』
效用的量度：效益、成本

個性：有沒有建立自己的個性？

是否有自己的思考風格？
對於大家共同的目標，有沒有自己不同的選擇方法？
君主(目標清楚單一不聽建議)、寡頭(有多個固定目標，權重相同)、
階層(目標之間有輕重緩急，並知道目標之間的關係)、無政府(目標不明確)


自知：有沒有自知之明？在別人眼中的自己是甚麼？
脈絡：會在甚麼樣的情況做甚麼樣的事情
時間：


條件:行動規則的用法


直接反射：整合所有滿足條件的規則，並展開相對應的行動

控制


前向鏈結：行動知道會發生甚麼？=>會考慮當前行動的後果

預測


後向鏈結：我要採取這個行動前，需要完成哪些前置條件？

規劃


對環境的研判


是否要很精確無誤？
或者是在當前來說是夠用的就好？

Learning agnets


監督式學習：有答案的學習

專家提供答案、知識
會告訴你：應該要怎麼做
範例：有小精靈大師告訴你要怎麼玩


非監督式學習：沒有答案，因此需要自己找出pattern

data mining、knowledge-discovery
紀錄每一次行動的結果，自己整理出規則
範例：出現新的道具在小精靈中，但是沒人告訴你那是甚麼


強化式學習 - Reinforced learning

行動之後，會有reinforcement(feedback)，可能是reward(獎賞)或penalty(處罰)
藉由行動之後的feedback調整下次的行動


Fill-scale learning agents

難度最高
如何挑自己的毛病？(critcize oneself)
能自我意識自己的狀態(self-awareness)
如何找問題給自己學習？(problem generate)
learning about learning：學習『如何學習』

不同的情況、主題，有不同的學習方式


Agents,Purpose, Learning


不同的agent等級，可以比擬為有不同的目標
Simgle reflex：Survival，以生存為目標，藉由修改rule的方式學習
Model-based：Attention，會注意外界的改變，藉由修改world model來學習
Goal-based：Direction，有個明確的方向
Utility-based：Purpose，有一個明確的目的


第三章：Solving problem by searching


用搜尋解決問題

找出一個『解』
找出一條通往解的的路徑
主要挑戰：如何將問題用搜尋的概念呈現？


範例：尋路

計程車司機如何規劃路徑？

空車時or有乘客時該怎麼走？
algorithm 還是 rule？

algorithm：事先算好怎麼走
rule：例如先固定上高速公路，到時候再看情況


Google map如何推薦路徑？
在語言不通的國外城市如何找到飯店？
登山迷路找路下山？(往下走不一定是答案？)


Problem-solving agents

把想達到的目標轉換為狀態
如果還沒有決定要走的路徑：

利用當前的狀態與目標的狀態轉化為problem
利用search找出想要走的路徑


執行路徑中的第一步，執行後將之從路徑中移除(當作走過了
重複執行步驟


在Search中，要把問題轉換為states與actions

states：視為路徑上的每一個node
actions：從某一個node移動到另一個node


但某些找路問題中，可能只有partial local infomation

只知當前node往周圍的情況，但無法知道更往外的情況


問題的種類

deterministic,fully observable：能看到地圖的全貌

agent知道自己的位置在哪
single-state problem


Non-observable, sensorless problem (conformant problem)：

agent可能不知道自己的位置在哪
例如被蒙著眼睛載著走
需要保持狀態的一致性(腦中要一直猜測自己的狀態/位置)


Nondeterministic/partially observable

需要隨機應變
可能路徑上突然不能走？或者是碰到鬼？
當發現狀況改變時，需要重新計算


Unknown state space

無法知道自己狀態
探索問題：連之後會碰到甚麼樣的問題與狀態都不知道，需要自己定義狀態


tree search problem

node上可以記載當前state、parent、action等等


比較演算法的方向：

完整性 (complete，在答案存在的情況下，是不是總是能找出？
時間複雜度
空間複雜度
最佳度(optimal，找出的答案是不是都是最佳的？


搜尋策略重點：

甚麼時機，使用甚麼策略？
if時機 then 策略


uninformed search strategies

BFS、DFS
只有在問題定義的時候的資訊可以取得
Uniform-cost search

BFS變形，但是每一個node的cost不同
優先搜尋cost比較低的node


Depth-limited search

DFS變形，但是限制最大深度


Iterative deepening search

從深度限制1開始，搜尋完之後增加深度
每次搜尋時，都會把該深度限制的所有可能探索完
最大特色：可以達到complete與optimal
繼承了BFS的complete/optimal與DFS的space


第四章：Informed search algorithm


前一章的Iterative deepening search演算法中，時間中有b^d項

b：branch、d：搜尋深度


設法降低b^d的成長度
對於branch來說，對人類比較難
對於depth來說，對機器比較難

Best-first search


定義：evaluation function f(n)

評估每一個node有多好？ => desirability
不像之前BFS或DFS的出入順序固定，而是每次有新的node就重新用f(n)排序


Greedy best-first search


令f(n) = h(n)：heuristic function

從當前地點n到goal的cost(例如距離)預估量
例如：看直線距離
顧前不顧後
將看起來最近的node做expand


非complete：可能會進入loop
非optimal
複雜度：b^m，如果h(n)設置的夠好，b就可以小

A* search


idea：避免某一條已經走很久的路(cost已經太大)
增加另一項：g(n)，其中g(n)是從起點走到現在的cost，不是估計值而是一個知道的值
f(n) = g(n) + h(n)

f(n)的意義：從起點經過n之後走到終點的估計cost


Admissible heuristics

被稱為Admissible heuristics的h(n)：絕對不會高估的h(n)
算出來的h(n) <= h*(n)，其中h*(n)為實際上真正從n到目標的cost


consistent heuristics

A->B->C 的heuristics不會小於A->C的heuristic


A*的最佳性

等高線的概念
對於越有可能的方向，越向該方向展開
步伐的大小：與目標的距離不同，搜尋步伐也不同

例如：要走到大霸尖山山頂，不用每一公尺就檢查是否到目標&搜尋


時間仍是指數，且也會將所有node放在記憶體。但若f取得夠好，其b的值(branch程度)很小
尋找好的heuristic

Dominance

若有兩個admissible的heuristic：h1、h2
若對於所有n來說，h2(n) >= h1(n)，則稱h2 dominate h1
此時h2是比較適合的搜尋用heuristic


Relaxed Problems


執行action時不要考慮那麼多限制

Local search algorithm


只希望達到目標，是不是最佳不重要
只關心current state，並且嘗試改進之
類神經網路也是local search
缺點：找到的解可能只是local maxima
例如Hill-climbing search

往好的地方去
覺得哪裡好就往哪裡去
問題：會碰到local optimal (不知道這個好是多好?)


Simulated annealing search (模擬退火法)


允許有"錯的move"：cost反而變高的move
利用此move來降低進入local minima的機會
但是這種move的出現頻率應該越來越ˋ低
距離搜尋的起點越近，就有越高的機率往不好的地方走
系統參數T：溫度

一開始很高
逐漸降低
T越高，往壞的機率走越高


Local beam search


不同處：一開始不只一個起點，而是有k個起點
一開始隨機產生k個點
每一次迴圈中從每一個當前k個點中各自跑出自己的successor，然後再從所有successor中找出k個最好的

基因演算法


一開始由k個起始狀態 (可以是隨機產生或其他方式)
下一代由這一代交換部分資訊或者是突變等等

兩個parent state會合併產生下一個state
child可能不一定各從parent繼承一半，有可能是偏向比較好的那一個parent
每一個parent可能不只被拿來繁衍一次(比較好的繁衍多次)，也可能有parent完全無法被挑來繁衍


Evaluation function (fitness function)

用來決定新狀態的好壞


要找一個方式把當前狀態用類似基因的方法編碼
可應用於藝術設計、蛋白質結構解析等等


第五章：Adversarial Search (搗蛋鬼搜尋)


從單人的世界進入多人的世界：有對手出現
甚麼時機使用local search？(從手邊已有的解答，看看怎麼走比較好)

環境需要有local方向性的指引(往哪走比較好？)

不一定需要global：就像你不必知道南寮在哪，但知道要往北走。到那邊在找新線索
問題：注意不要進入local optimal
A*需要有global的資訊

因為heuristic需要知道往後大概的cost如何，如果完全不知道往後狀況就沒辦法有好的heuristic


local search的環境假設：解的旁邊一定也不錯

很少出現大海撈針的狀況


平行的local search

假設：解不只一個，很多地方都有or只有一個解，但是存在很多地方
同時在多個地方進行搜尋

Local beam search
Evolutionary strategy

只使用突變的基因演算法，沒有基因cross over


其他問題：如何彙整資訊、平行效能(讓大家做的速度差不多)
如何處理太快收斂？不要太快匯總(例如beam search，先在local先多搜幾輪，之後再把全部拿來排名)
Generic algorithm的假設

解有很多or存在很多地方：平行搜尋
解是一個系統，其中存在子系統、module等building block(例如生物有很多building block組成)

使用crossover來搜尋、維護、交換這些building block


從單人到多人世界的AI

過去的方法：把其他人當作是環境的一部分(因此環境是stochastic)
問題簡化：大部分情況下環境是不會變的

應假設是strategic環境
解就是一套策略


策略的形式：演算法或者是heuristic或者是兩者的結合

演算法是可以證明永遠正確，而heuristic只是推斷


把遊戲當作一個搜尋問題

無法預測的對手(例如西洋棋)：可能需要對每個對手可能的行動作出相對應的動作
時間限制：如果在一定時間內沒辦法找到目標或最佳解，至少找出比較好的解


根據對手(opponent)的一些思考(賽局理論)

零和賽局：競爭(損失與獲利加起來是零) vs 非零和賽局：合作
雙人賽局、多人賽局
輪流賽局(turn-based)與即時賽局(real-time)


過去的search agent僅為simple reflex agent
Model-based reflex model

例如雙人賽局：下棋
Strategic environment：對手代表了世界

環境是固定，因此一切的變數由對手決定(因此建立"對手"的model)

給對手甚麼輸入，他會有甚麼輸出？
例如如果知道對手是貪小便宜的，就放誘餌


至於要把對手想像成哪樣的agent？

Simple reflex？model-based？goal-based？utility-based？


如果把對手想為simple reflex agent

如何建立對手的行動模型？

例如找出對手的if-then-else規則庫


如何蒐集對手的行動資訊？
假設為此種模式通常是最好做的


把別人當作別人：替別人建立模型
把別人當作自己：把自己的模型套在別人身上
把自己當作別人
把自己當作自己：有自我意識
如果把對手想像成自己

通常是最常用的
如果是我，我會怎麼做？設身處地，推己及人？


Minimax search

雙人賽局裡的A-star
要下某一步時，往後看下兩步(自己與對手)

由於對手不配合，對手基本上會選擇對手自己損失最小的
由於自己下完之後，會換對手下，此時對手會在他下的時候找損失最小的下
因此自己要下這一步的時候，要找出某一步使得下一步換對手的時候，他找到的損失相對較大

而不是一廂情願找出永遠的最佳解(因為對手不會配合)


需要有一個判斷局勢好壞的方法(量測對手的損失程度)


n-ply game：考慮之後n步
Resource limit：計算速度問題

大多數遊戲可能性太多(例如西洋棋)，因此要real-time時，通常找出來的結果都不是最完美的
沒辦法展開那麼多的search tree
cutoff-test

限制展開的深度(例如使用quiescence search)


evaluation function

評估各種情況下的好壞(estimated desirability of position)
Eval(s) = w1f1(s) + w2f2(s) + .... + wnfn(s)

s：某一種狀況
fn：feature function：對於現在某一件事實的評估狀態

以西洋棋為例：fn = 我方的皇后數量 - 敵方的皇后數量


wn：對於某一個feature的評估權重

如果權重值可以由學習而來更好，而非事先指定


例如：黑白棋

下了之後，往後還有多少步可走？
穩定性：是不是很容易被翻盤？
每一個特定位置的重要性？例如角落不會被翻盤


我的目標是甚麼？

對手是誰？

高手：想贏？有進步就好？
上司：故意小輸
買遊戲的玩家：勢均力敵、小贏對方


其他目標？


Complete：是(如果tree是有限的)
Optimal：是(如果對手也是Optimal的)
時間複雜度：O(b^m)
空間複雜度：O(bm)，depth-first exploration
由於時間複雜度太高：使用alpha-beta pruning

展開第一個subtree時，發現最終可以得到的利益是3 (對手根據最小損失原則得來的數字)
展開第二個subtree時，發現出現某一個利益是2，就不必展開其他node了()
依此類推，降低需要展開的node數
不會影響最終結果
根據不同的pruning ordering，效能不同
最好的情況下(最好的ordering)，時間複雜度為O(b^(m/2))
alpha：到目前為止最好的值
beta：到目前為止最差的值


Algorithm with heuristic

algorithm

Minimax search
alpha-beta pruning


heuristic

Evaluation function
好的pruning ordering
cut-off depth


Evaluation function 與 Learning

找出更好的weight combination
找出其他更重要的feature
回顧：learning agent：就像聘請一個教練，告訴你怎麼打(performace element)
何時學習？

比賽前：在與下一個對手開始比賽前
比賽的第一個部分(例如七戰四勝，打第一場之後就學習)
比賽中(半場休息、攻守互換間隔等等)


Minimax search & alpha-beta pruning：重點與假設

假設對手是我，運算速度相同，使用相同Eval function

對手比我弱時，有需要如此假設嗎？
對手比我強時，這樣假設有用嗎？


如何突破障礙？超越棋局，進入真實世界
思考：情報、分析、學習

假設拿到了(高手)對手的eval function，此時該怎麼做？

除了模仿，還能學到甚麼？


假設對手的eval function的形式(例如linear weighted sum)與自己相同，且又可以觀察到對手的棋步，能夠把對手的eval function建構出來嗎？

和自己的function比較，然後呢？
如果想要模仿：試圖調整自己的weight來滿足觀察


如果蒐集到很多對手下的棋局，又能學到學到甚麼？


另一種思考角度

對手怎麼看我？

比我怎樣看人重要！
旁觀者怎麼看我？
我希望別人怎麼看我？


Agent的自我覺察(self-awareness)

別人怎麼看我？
別人對我的期待是甚麼？

以上兩者之間有沒有落差？


Cooperative agent


西洋棋 vs 多人世界

西洋棋：簡單的明確的規則、有足夠時間可以深思、單一對手、目標明確(打敗對手獲得勝利)
多人世界：規則複雜模糊且多變、需要即時反應與預測能力(建構預測模型)、多人(對手、盟友、中立)、以效益(utility)為考量(合作、競爭、中立)


競爭與合作

競爭：通常需要分析對手策略
合作：不一定需要知道結盟者的細部執行策略

只需要相信對方，相信對方會解決問題
除非需要分工的合作，才需要知道隊友的執行細節
分工及分工前需要的功能分化，如何自動完成？


合作行為是如何產生的？

不需以利他或其他道德規訓為基礎
基於理性的計算也能產生因合作而互惠的結果
探討合作行為的賽局：囚犯困局

兩個嫌犯被抓了，隔離審訊
A出賣，B合作：A自由，B關五年
AB皆合作：都關兩年
AB皆互相出賣：都關四年
平均應該關少於2.5年，才有賺


邀請共事

正式：簽訂合約

要履約(C)還是毀約(D)？
_ 非正式：日常人際互動
拍賣場中的競標信號
社會行動


Axelrod的IPD實驗

IPD：iterative prisoner's dilemma：囚犯困局
假設：未來很重要(未來還會再跟這個人合作 )
TIT FOR TAT策略

只記住上一次的行為
對手怎麼做，我這次就怎麼做


Strategy：一群condition-action rule的集合
Strategy Table：涵蓋各種condition的組合
strategy之間的互動：

平衡(equilibrium)、變化(dynamic)、過去沒遇過這次突然出來的行為(emergent behavior)


PAVLOV 策略

Win-stay, lose-shift
CC->C：你我都合作，我們就合作
CD->D：我合作你背叛，我下次就背叛
DC->C：我背叛你卻合作，我得利所以我還是背叛
DD->C：都背叛沒好處，試圖合作


TFT在演化上並不穩定：會大起大落
TFT如果在過程中發生反常，就可能常常黑吃黑
PAVLOV：可以修正偶爾發生的錯誤(偶爾發生異常不會一直持續)
PAVLOV：如果和自己打(對手使用和自己相似的策略)，大部分的情況都會採取合作
Agents in a Map

一大堆agent的集合，如同一個很大的網格，每一個格子都是一個agent

最基本的情況：每個格子只會與周圍agent互動
較複雜的情況：存在hpyer link

agent的互動範圍不限於鄰居，例如internet造就了agent(人們)可以不只和現實身邊的人互動


Spatial IPD

聚落、族群分化，分散式演化


不同的社會網路

Regular Network：下次合作的對象固定
Random Network：合作對象隨機
Small-work：下次對象可能固定也可能是隨機


那許(Nash)均衡點

雙人以上non-cooperative game的解

每個人都知道其他人的均衡點策略
沒有任何人只靠修改自己的策略來得到好處(必須要其他人也跟著改)


決策時必須考慮其他agent的決策
策略互動模型的基礎
例如：

海灘上的兩家冰店，均衡點為兩個人都開在正中央
Prisoner's Dilemma:scoundrel (囚犯困局其實就是Nash均衡點的一個例子)

軍備競賽(知道競爭沒意義，但又怕輸)，均衡點為繼續造武器
戰爭撤兵(都知道打下去沒意義，但又不肯先撤兵怕吃虧)，均衡點為繼續不撤兵


Coordination game

狩獵：兩個獵人，可以自行打兔子，但是打鹿必須要兩人合作才有辦法成功

每個獵人可以繼續自己打兔子，或者是前往打鹿(但一個人會失敗，甚麼都沒拿到)

但如果剛好另一個人也去打鹿，則收穫都很大


均衡點：兩個人都在打兔子，因為都怕對方沒去打鹿，自己卻沒獵到兔子


如何跳出不佳的Nash均衡點？

眼光放遠，計算長期利益：iterative model
保持耐心，多做試探：memory model(記憶更多過往的例子，推測對方，而不是謹記住上一次的結果)
多方面探索可能的合作對象：parallel & distributed model(例如基因演算法，在不同的起始點發展不同的策略)


觀察

多人世界中，不一定要把別人想成自己：無論對手或隊友，都可以個別建立模型
多人世界中，經由互動產生的複雜系統：不斷發展的動態平衡，需要持續學習來因應

過去可用的策略，現在不一定可行
跳出過去的Nash均衡點：需要有動態的流動(才有辦法產生更多的變化)


策略代理人(strategic agents)為一個系統：

不只是一個**"方法"**
具有整體結構和參數
從系統觀點來看學習


分化與分工

分工的目的：形成更大的組織單位(或building block)
過程中的資源引導

一開始是競爭而不是合作，但到最後可能發展出一個平衡(甚至是合作)的情境
獵人與獵物


學習：結構優先，參數其次

結構影響遠大於參數


獵食者與獵物的共同進化 (類似軍備競賽，兩邊互相進化)

獵食者：獵豹、矛、處理Data的Program
獵物：羚羊、盾、Data


結盟

從軍備競賽升級為攻防同盟
盟約的締結需要雙方同步？

囚犯困局：誰先讓步？


單方面釋出善意就足夠？

尤其沒有直接利害的時候
例如蚱蜢先爬到蛇背上求保護，幫他抓癢。他知道蛇不會立即吃他(沒有直接利害)，故先釋出善意
偏好結盟的基因：天生會想結盟


小精靈的學習

如何學會躲鬼？
如何學會吃豆子？資源引導
如何學會利用大力丸
鬼的學習？
多人世界中的結盟？多鬼？多精靈？


補充：Rulebase


你的行動會造成別人條件的改變
rules of reaction：在某些條件下，就做某事：condition-action
rules of inference：如果發生/觀察到某事，就可以得知某些事情：premises(前提)-conclusion(結論)
Chaining of rules

前後串聯的rule：滿足某一rule，觸發另一組rule
用於logic reasoning(邏輯推理)
用於Task planning


Locality & Continuity

位置差不多，則情況與結果也不會差太多


Reasoning types & learning

淺思：有效率

Shallow reasoning
需要依賴過去建立的model來反應
遇到問題時的即時反應


深思

Deep reasoning
例如下棋
邏輯推導與規劃
強調推理過程中的健全


大部分情況都是用淺思判斷大概的問題與情況


Classification & Control

Correct：rule會做出正確的action
Complete：rule對每一個data entry都會反映
Consistent：multiple responding rule不會產生出衝突的action (不同病人來，五的醫生答案不同)
Concise：不會有redundant rule


第七章：Logical Agents


重點：

knowledge-based agent

學習


Propositional (boolean) logic
inference rules


knowledge base(KB) = set of sentencecs in a formal language

Declarative apporach：看到事實，就告知自己的KB

你的knowledge base需要知道甚麼，就把看到的告訴他(tell)


tell之後，詢問自己(ask)：現在該做甚麼？

KB會推理出答案


以knowledge level的角度來看：他有多聰明？不管實作細節


KB agent

需要表達出state、action
觀察外界
tell KB有關新的知識
ask KB要做甚麼，KB給予action
執行action後再tell KB


不只是從"已經看的到的事實"去推論，也可以從"本來該存在而現在卻看不到的"去推論發生甚麼事情了

wumpus小鬼例子：為何在這一個房間無法聞到小鬼的味道？可以推論出小鬼的位置的可能性？
例如：進入麵包店，為何沒有聞到麵包香？推論出麵包可能是假的(用蠟做的)!!
要能夠做這類判斷，心中一定要有個model：要知道甚麼時候缺甚麼，可能會來自甚麼原因(例如麵包店中沒有香味，可能是因為麵包是假的)


Logic


logic：有自己的syntax與semantics

syntax：描述了某一個sentence長甚麼樣子
semantics：描述了某一個sentence代表甚麼意思


entailment

代表某種事情是follow另一件事情
KB |= alpha
KB entails sentence alpha
alpha是跟在KB之後
滿足：若KB是正確的，則產生出來的alpha也是正確的
M(alpha) 包含了 M(KB)

M(x)：a model of x：亦即滿足條件x的所有可能性


舉例

wumpus world：假設只有陷阱
(1,1)沒事，(2,1)有吹到風
此時的KB = 已知的wumpus-world rule與觀察到的現象
可以推論出：(1,2)一定沒陷阱，(2,2)或(1,3)至少有一個陷阱
此時：

M(alpha) = (1,2)是安全，(2,2)或(1,3)分別是XX,XO,OX,OO：共四種可能(O = 有陷阱)

alpha = 猜測(1,2)是安全的(但並不知道是否有風或其他資訊，alpha就是一個猜測出來的事實)


M(KB) = (1,2)一定沒陷阱，(2,2)或(1,3)至少有一個陷阱(XO,OX,OO)，共三種可能

對KB來說，他知道(2,2)或(1,3)至少有一個陷阱，因為他在(1,2)吹到風了


由於M(alpha)包含了M(KB)，因此KB |= alpha


換句話說，【(1,2)是安全的】這一個事實，在滿足了KB中的條件【(1,1)啥事也沒發生】就肯定滿足了


Computer Science中，必須要在有限的時間內找到解

KB |-i alpha：sentence alpha可以利用procedure i套用在KB中得來
Soundness：健全性，procedure i為sound，當KB |-i alpha 是true時，KB |= alpha也是true

醫生看病，他如果說得出來你有病則一定會對(不會說錯)。但他也可能你有病但他找不到而都沒說。
換句話說KB |= alpha可能真的成立，但是procedure i找不出來


Completeness：完整性，procedure i為Completeness，若KB |= alpha為true時，則KB |-i alpha也是true

醫生看病，如果你有病他一定說得出來，只是說出來的不一定對。


最基本的一種方法：窮舉：列出所有symbol的true/false組合(例如找出wumpus中每個格子是不是鬼/陷阱的true/false組合)

為sound and complete
但時機複雜度是exponential，效率太差


equivalence：a ≡ b iff a|=b且b|=a
satisfiable：存在某些model中會滿足，例如 A or B，在許多A、B的組合中，總會有幾個是成立的(例如A：大於5，B：大於3，輸入 = 4)
unsatisfiable：不管A做甚麼解釋，都不可能滿足。例如：A且not A
KB |= a

iff (KB且not a) 為unsatisfiable，即KB成立但a不成立這件事情永遠不可能滿足，即若KB滿足，其產生的a也必定滿足(找不到不滿足的a)

類似：反證法基於我們假設是錯的確發現矛盾或不滿足，進而推斷出原本的是正確的


Conjunctive Normal Form (CNF)：一堆or項進行and

例如(A or ~B or C) and (C or not D)
wumpus world：P13有陷阱 or P22有陷阱
Conversion to CNF 可能會考?

把某些事實轉換為CNF
例如：題目B(1,1) <=> P(1,2) or P(2,1)

B(1,1)吹到風，代表P(1,2) or P(2,1)至少其中一個地方有陷阱，反之亦然


轉換為CNF的方法

將 a <=> b 轉換為 (a => b) and (b => a)
將 a => b轉換為 ~a or b

要嘛a是錯的，若不是(代表a是對的)，則b也要對才行


deMorgan Raw (把not推進去，and/or互換)
分配律(AND over OR)

C and (( A and B ) or A )
轉換為：(A and B and C) or (A and C)


Horn Form

KB = 一堆Horn clauses的and集合
Horn clause(子句)

terminal：任何一個符號
(一堆symbol進行AND ) => 另一個symbol


Forward chaining：左邊推到右邊
Backward chaining：右邊推到左邊


Forward Chaining

將所有滿足KB當前內容的rule找出來，然後把他加入KB，直到想要的答案找出來

已知A成立，則把所有A=>BC的B和C當作是成立，繼續往下找


可能會推論出redundancy的結論(可能會出現對答案沒有幫助的結論)
Sound & Complete
data-driven：由資料驅動的
要加快流程，可以只在新資料進來時才進行推導

稱為matching，尋找新事實與KB中哪些事實有關


Backward Chaining

由問題往回推，然後遞迴去證明
問題是Q，已知P=>Q，則問題變成把P證出來。若有多條X=>Q，則每一個X都要試試看
goal-driven：由目標驅動的
較適合解決問題
複雜度較低
有不同演算法，有complete版本，也有因為求快而不complete的


Summary

Logical Agent將inference應用到KB上，來得到新資訊與做決定
inference：從某一個sentence推出另一個


第八章：一階邏輯 (First-Order Logic，FOL)


上一章的Propositional Logic為Zero-Order Logic

好處：Declarative

允許部分資料是negated等等
可做運算
context-independent

不像自然語言，不同內容的symbol，則意義不同


壞處：表達性非常有限


FOL

Zero-order：只有表達一堆事實
FOL包含了

Object：物件本身(人、房子、數字)
Relation：形容詞，比較詞
function：某人的朋友、比你還要大於一的數字


FOL的Syntax

Constants：常數(事實)
Predicates：描述relation，例如：Brother、>、<
Function：特殊的Predicate，Sqrt()、LeftLegOf()，答案只能有一個

能夠轉成function就不要用predicate表示


Variable：變數，x,y,a,b,...
Connectives：not、and、or、=>、<=>
Equality：相等，代表等號兩邊是同一個object：=

過去提到的"全等"：左右兩邊的邏輯值完全相同


Quantifier：For all、Exist


Atomic sentence = predicate(term1,term2,...) 或 term1 = term2

Term = function(term1,term2,...)或constant或variable


Complex sentence：將amotic sentence用connectives連接起來(and、or、not、=>等等)
Universal Quantification

For All

例如：

Everyone at NCTU is smart
For all: x At(x,NCTU)=> Smart(x)


對於所有變數的可能性，將之帶進去之後and起來
通常for all最主要的connective是=>，而不是and

例如：For all: x At(x,NCTU) and Smart(x)

世界上所有人都在NCTU且都很聰明


Existential Quantification

Exist
以and為main connective

而不是使用 =>
Exist: x At(x,NCTU)=> Smart(x)

如果前者不成立，此句子就成立！
意思是只要x不在NCTU，這句話也成立


Quantifier的特性

A: for all ; E: exist
AxAy = AyAx
ExEy = EyEx
ExAy Love(x,y)：存在一個博愛者愛大家
EyAx Love(x,y)：存在一個人都被大家愛(人人愛)
對偶性

A與E可以互相用對方表達，類似負負得正
每個人都喜歡冰淇淋 = 不存在不喜歡冰淇淋的人

ForAll x:like ice = not Exist x:not like


存在某個人喜歡花椰菜 = 不是所有人都不喜歡花椰菜

Exist x:like brcocoli = not ForAll x:not like brocoli


Equality

term1 = term2

代表兩個東西是同一個東西，但名稱不一樣。例如同一人有許多綽號
而不是之前提到的"全等"，全等是指truth value相同


例如：手足(sibling)的定義

要有共同的雙親(mother和father)，且xy、mf都不是同一個人
ForAll x,y:Sibling(x,y) <=> [not (x=y) AND Exist m,f:not (m=f) AND Parent(m,x) AND Parent(f,x) and Parent(m,y) and Parent(f,y)]


與FOL KB互動

假設在wumpus-world
假設只能觀察到味道、風、金光
例如：在t=5時發現到味道以及風

Tell(KB,[有味道,有風,沒金光],5)
Ask(KB,Exist a:BestAction(a,5))
亦即：告訴KB目前已經觀察到的事實，問KB是否存在一個action a，這個action是在t=5時最佳的action
KB的Answer: Yes,{a/Shoot}代表存在答案，答案是action = shoot


目標：把所有的變數都變成常數

例如把未知的action變數a變成動作常數Shoot


代換 (substitution)

S = Smarter(x,y)
substitution "sigma" = {x/Alice,y/Bob}：把x換成Alice，y換成Bob
將sigma帶入S，取得答案
Ask(KB,S)，希望得到所有的sigma，使得KB|=sigma

例如問"Smarter"，希望KB告訴他所有滿足Smarter的所有代換方式


推論隱藏的properties

Diagnostic rule：由結果推出原因

例如：如果吹到風，就可以推論出鄰近房間有陷阱


Causao rule：由原因推出結果

例如：如果此房間有陷阱，就可以推論出鄰近房間會吹到風


Knowledge engineering in FOL

找出要達成的task

例如1bit 加法器：當前電路是否正常運作？


將相關的資訊、知識找出來

有AND、OR、NOT、XOR等logic gate
不相關的範例：gate的大小、形狀、價格、顏色等等


決定有那些predicate、function、constants

Type(X1) = XOR

Type：用來表達某一個gate的類別


用邏輯的形式表達該domain一般的知識

例如：

1 != 0

高電位與低電位是兩件不同的事情


ForAll t:Signal(t) = 1 OR Signal(t) = 0

所有的信號不是高電位就是低電位


將某一個問題用剛剛的那些syntax表達出來

用Type與Connected來表達線路連接


將這個問題作為query丟進去inference procedure

若無結果，可能是表達錯誤或者是不完整


對KB進行debug


第九章：inference in FOL


降級處理：把FOL轉換成Zero-order：單純且沒效率

Universal instantiation(UI)

ForAll x:King(x) AND Greedy(x) => Evil(x)

將所有的x可能性全部帶進去，例如：John、Father(John)...


Existential instantiation(EI)

找一個KB中沒有出現的symbol，將變數代換程該symbol
Exist x:Crown(x) AND OnHead(x,John)

把x用新常數symbol C1帶入，C1為某一個王冠
代表John帶了某一頂王冠，目前還不知道，暫且稱為C1


造成的問題：變數可能性無限多，代不完
semidecidable

若這件事情為真，就一定可以找到一個方法/演算法證明其為真
反之若為假，則不一定找的到(不是有限的結束時間)


Unification

Unify(a,b) = c，若ac = bc

利用甚麼樣的substitution可以讓a和b變得一樣
例如：

a = Knows(John,x)
b = Knows(John,Jane)
則可以使用substitution {x/Jane}把a、b變得一樣


存在不只一種substitution，也可能不存在任何一種


盡量取更general的unify

例如：Knows(Alice,x)與Knows(Alice,y)
較好的：{x/y}，而不是{x/Bob,y/Candy}等代換沒太大意義的常數


Conversion to CNF (要會(?))

要把Exist轉換為function

Skolemize很重要
reference:http://www.cs.toronto.edu/~sheila/384/w11/Lectures/csc384w11-KR-tutorial.pdf

看前半段


刪掉exist後，只剩下for all，將所有for all移除


第十章：規劃(Classical Planning)


Search與Planning的差異？

Search：效率差

買某個東西，去商店街所有店鋪搜尋


Planning：

在買某個東西之前，先想想如何得到這個東西，在去找
Goal-Based Agent


Partially ordered plans

start step：起始狀態
finish step：目標狀態
causal links：因果關係，前一個步驟產生的結果到下一個步驟所需的條件
temporal ordering：調換steps之間的順序


範例：更換輪胎

開始狀態：輪胎1壞掉，有備胎但未打氣
結束狀態：所有輪子x都在輪軸上，且有打氣
可進行的動作：從輪軸上移除x、把x放到輪軸上、把x充氣
設法建立link從開始連到結束


衝突

有些action的precondition有規定，如果先完成其他的action使得該precondition無法達成，就不能做那一個\


期末考範圍

Chapter 5,7,8,9,10
期末考題庫(美版課本題號)

5: 1, 2, 4, 6, 7, 12, 16, 19, 20, 21
7: 4, 5, 6, 7, 10, 20, 21, 26
8: 6, 10, 18 , 19 ,  20 , 24
9: 1, 3, 4, 6, 7, 9
10: 1,  2,  3,  4,  6, 9, 14, 16