- AI發展:1980~1990
- 難以開發出解決general問題的AI => 轉往解決"專業問題"
- 專家系統:以專業知識為基礎
- 規則庫+專業領域的本體(ontology)or劇本(script)
- 劇本:例如點餐:先點、確認、付錢、統編
- 類似某一種固定的流程
- 專家系統:以專業知識為基礎
- 工業應用(而非國防
- scheduling(排程),例如何時去見哪個客戶
- planing(規劃)
- 神經網路:machine learning
- 符號(symbolic):例如紅黃綠燈,類似nomial attribute
- 數字((numeric)
- 結合市場:仍以問題解決為主,而非與人相處等等
- 例如智慧(傻瓜)家電、自動車等等
- 基本演算法+經驗法則
- 分散式智慧、群集智慧:尋找閒置的電腦/裝置來執行計算(例如尋找外星人
- 難以開發出解決general問題的AI => 轉往解決"專業問題"
- 2000~2010
- 網路時代的AI
- 以網路、智慧手機為基礎
- 強調服務而非生產:照護機器人、聊天機器人
- 設計考量與生產機器人大不同,要考慮人類行為
- 強調對使用者了解:以使用者為基礎建模、個人化推薦等等
- 多人世界:不能把互動對象當作問題(不再是problem-solving)
- 需要更精緻的心智模型
- 網路時代的AI
- 看問題的觀點:推薦系統
- 觀點一:
- 根據產品屬性、個別使用者偏好
- 蒐集使用者資料與分析(但要注意個資問題)
- 根據特定使用者作推薦
- 例如搜尋系統就是一種推薦系統
- 搜尋系統事實上已經是先蒐尋找內容
- 根據使用者關鍵字與偏好決定從資料庫中找出哪些內容
- 觀點二:
- 同好 (對於多項產品評分一致的一群人)
- 根據同好所選的東西來推薦(同好滿意但你未使用過的產品)
- 例如:看過這本書的人還看過了xxx書/電影
- 現今常使用cookie來追蹤使用者行為
- amazon為何不會要求使用者評分其書本來建立同好清單?
- 利用購買行為(買了甚麼書),來建立同好清單
- 買了xxx書的人還買了xxx
- 事實上那個"人"可能不是真的某一個人
- 利用購買行為(買了甚麼書),來建立同好清單
- 社群中的推薦系統
- 外掛?!由玩家推薦的idea?下一版本變成內掛?
- 觀點一:
- 看問題的觀點:媒合系統
- 雙向挑選::職業、婚姻仲介
- 媒合就是雙向推薦?(公司選你,你選公司)、(她挑你,你挑她)
- 觀點一:如何在媒合系統勝出?(對方:你想要申請/追求的對象)
- level 1:呈現自己最好的,期待對方欣賞 (並沒有考慮到對方想法與競爭對手)
- level 2:猜測對方好惡,包裝自己
- level 3:猜測、了解競爭對手,提升自己排名好被優先推薦
- SEO:search engine optimization
- 外面想要衝高自己產品在搜尋引擎上的排行
- 搜尋引擎公司極力反制SEO
- 觀點二:如何在電視媒合節目勝出?
- 勝利條件:你挑她,她挑你
- 前提:你會知道上一輪誰挑了你
- 如果有人挑你,但是你沒挑她,那下一輪要不要再挑她?
- 如果你挑了某人,但是她沒挑你,那下一輪要不要再挑同一人?
- 在多回合賽局中,各回合要採取甚麼?
- 猜測對方會怎麼做?我該怎麼調整?
- 如果對方是台下家人的指示,那你該如何調整?
- 在電視平台上,你的對象是誰?
- 目標不是跟到場的配對,而是想與廣大的觀眾宣傳?
- 分類:動詞+副詞
- 動詞:
- 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
- 根據輸入來產生輸出
- 內部會有許多不同的規則等等
- 比較"不像人"
- Rational behavior:做對的事情(比較像人)
- 例子:遊戲(數獨、小精靈)
- 對題目難易的感受像人一樣
- 可以區別出是某人或大眾的觀感
- 可以出題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
- Agent:能夠觀察接收外界資訊並做出行動
- agent = architecture + program
- 例如:吸塵器
- percepts (觀察):位置、內容(是否有髒汙)
- Actions (行動):移動、吸取灰塵
- do the right thing
- 觀察到甚麼,然後從他能做的事情中做些甚麼
- AI的低標
- 能夠進行action來獲得/修改未來能夠觀察到的東西
- 例如機器人移動自己的位置、蒐集新的資訊
- autonomous:agent能夠利用自己的經驗來做出行動
- 自己能夠學習,然後應用之
- AI的基本幾個指標
- Performance measure
- 例如自動車的安全性、速度、合法、舒適
- Environment
- AI適用的情況
- 例如自動車行駛時的路況、交通壅塞程度
- Actuator
- 執行動作的裝置
- 例如自動車的方向盤、加速器、煞車
- Sensor
- 例如自動車的攝影機、感應器等等
- 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花太多時間決策
- 環境不改變,但是隨著時間過去,agent的performace score會降低
- 靜態:在做決策的時候,環境是固定的
- 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來找花生
- 獸人群過橋,智慧在橋上,指揮哪些獸人過橋,而非每一個獸人自己都有複雜AI
- 大量規則形成規則庫,使用於大多數的專家系統
- 衍生問題:規則激發的順序(order)、優先權?
- 整合機制:平行激發規則,例如模糊系統
- 有層次性的規則(規則調整另一個規則)
- 規則自動學習
- 可以"記憶"
- Agent處於某一個狀態
- 因應外界狀況改變狀態並做出行動
- 掌握"動態":動者恆動,並非許多靜態的連續
- 處理持續的行動、預設的行動
- 例如騎車 (沒有特別停車,就是在移動中)
- 把行動附屬於狀態,不用特定條件觸發
- 狀態加上情緒 => 更像人
- 例如:狀態 = 衝刺,情緒 = 吶喊
- 透過觀察
- 把狀態轉為規則的條件之一 (if 在狀態A, then ...)
- 定義每個狀態要怎麼觀察?(用甚麼外部指標來定義當前的狀態?)
- 眼光從外而內,內建的自我覺察
- 透過記憶
- 比較簡單,但需要注意更新
- 定點守衛、固定路線範圍巡邏、表現出差異行為(是否主動、逃跑、求援)、
集體行動與協調(隊伍間、隊伍中的協調)、合作與分工(圍毆、補血)、探索地圖
- 以自然或有機的方式來移動一群生物
- 在三條簡單的規則中取得平衡:保持間距、同向、靠攏
- 容易描述(設計者的構想)
- 容易實作(技術成熟,使用的計算資源少)
- 容易預測(沒有複雜的行為鏈鎖反應)
- 容易改進(邏輯清楚)
- 容易擴充(增加狀態、連結、行動)
- 把資訊存在stack上
- 能夠騎車不摔下來?Yes
- 能夠達到目的地? Maybe Not
- 記錄了世界的樣貌與變化(世界的模型)、對自己行動的影響
- 世界模型(world model)的形式
- 規則庫(我是甚麼樣,就假設別人也是這樣)
- 世界由「別人」構成,把「別人」想成「自己」
- 假想:如果是我,我會怎麼做?
- 缺點:過於麻煩(例如小怪太多,可能會有太多規則)
- FSM:將世界簡化的模型
- 假設世界就處於某幾個狀態
- 黑盒子
- 不知道世界怎麼運作
- 只知道:給予某input,就會有某output
- 把「別人」當作「別人」
- 怎麼樣對不同的世界建模?(modeling) -> 神經網路、決策樹等等
- 規則庫(我是甚麼樣,就假設別人也是這樣)
- 如同作業:pacman,如何寫程式操作pacman,而非操作ghost?
- 以目標為基礎的能動者
- 採取行動後,對世界的影響?是否更接近目標?
- 例如:守衛小怪
- 我的目標是甚麼?我該做甚麼來達成目標?
- 目標:不想被發現-->假裝睡著,玩家會怎麼做?
- 在何種條件下才能行動?
- 現在裝睡會不會太晚?
- 目標架構、行動選項
- 玩家建模(player modeling)
- 從對方的角度來看這件事(我知道你知道我知道)
- 玩家是否會相信我在裝睡?
- 我的目標是甚麼?我該做甚麼來達成目標?
- 最「簡單」的目標:活下去、活得好
- 活下去:個體的學習適應 vs 全體的演化適存? --> 誰值得活下去?
- 活得好:自訂目標,展現agent的能動性
- 根據甚麼來自訂目標?活得好 = 快樂 or 有意義 or 其他?
- 以效用為基礎的能動者
- 例如:達成目標後我會有多高興?
- "效用"的指標:例如『快樂』
- 效用的量度:效益、成本
- 個性:有沒有建立自己的個性?
- 是否有自己的思考風格?
- 對於大家共同的目標,有沒有自己不同的選擇方法?
- 君主(目標清楚單一不聽建議)、寡頭(有多個固定目標,權重相同)、 階層(目標之間有輕重緩急,並知道目標之間的關係)、無政府(目標不明確)
- 自知:有沒有自知之明?在別人眼中的自己是甚麼?
- 脈絡:會在甚麼樣的情況做甚麼樣的事情
- 時間:
- 個性:有沒有建立自己的個性?
- 直接反射:整合所有滿足條件的規則,並展開相對應的行動
- 控制
- 前向鏈結:行動知道會發生甚麼?=>會考慮當前行動的後果
- 預測
- 後向鏈結:我要採取這個行動前,需要完成哪些前置條件?
- 規劃
- 是否要很精確無誤?
- 或者是在當前來說是夠用的就好?
- 監督式學習:有答案的學習
- 專家提供答案、知識
- 會告訴你:應該要怎麼做
- 範例:有小精靈大師告訴你要怎麼玩
- 非監督式學習:沒有答案,因此需要自己找出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:學習『如何學習』
- 不同的情況、主題,有不同的學習方式
- 不同的agent等級,可以比擬為有不同的目標
- Simgle reflex:Survival,以生存為目標,藉由修改rule的方式學習
- Model-based:Attention,會注意外界的改變,藉由修改world model來學習
- Goal-based:Direction,有個明確的方向
- Utility-based:Purpose,有一個明確的目的
-
用搜尋解決問題
- 找出一個『解』
- 找出一條通往解的的路徑
- 主要挑戰:如何將問題用搜尋的概念呈現?
-
範例:尋路
- 計程車司機如何規劃路徑?
- 空車時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
- 無法知道自己狀態
- 探索問題:連之後會碰到甚麼樣的問題與狀態都不知道,需要自己定義狀態
- deterministic,fully observable:能看到地圖的全貌
-
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
- 前一章的Iterative deepening search演算法中,時間中有b^d項
- b:branch、d:搜尋深度
- 設法降低b^d的成長度
- 對於branch來說,對人類比較難
- 對於depth來說,對機器比較難
- 定義:evaluation function f(n)
- 評估每一個node有多好? => desirability
- 不像之前BFS或DFS的出入順序固定,而是每次有新的node就重新用f(n)排序
- 令f(n) = h(n):heuristic function
- 從當前地點n到goal的cost(例如距離)預估量
- 例如:看直線距離
- 顧前不顧後
- 將看起來最近的node做expand
- 非complete:可能會進入loop
- 非optimal
- 複雜度:b^m,如果h(n)設置的夠好,b就可以小
- 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
- Dominance
- 執行action時不要考慮那麼多限制
- 只希望達到目標,是不是最佳不重要
- 只關心current state,並且嘗試改進之
- 類神經網路也是local search
- 缺點:找到的解可能只是local maxima
- 例如Hill-climbing search
- 往好的地方去
- 覺得哪裡好就往哪裡去
- 問題:會碰到local optimal (不知道這個好是多好?)
- 允許有"錯的move":cost反而變高的move
- 利用此move來降低進入local minima的機會
- 但是這種move的出現頻率應該越來越ˋ低
- 距離搜尋的起點越近,就有越高的機率往不好的地方走
- 系統參數T:溫度
- 一開始很高
- 逐漸降低
- T越高,往壞的機率走越高
- 不同處:一開始不只一個起點,而是有k個起點
- 一開始隨機產生k個點
- 每一次迴圈中從每一個當前k個點中各自跑出自己的successor,然後再從所有successor中找出k個最好的
- 一開始由k個起始狀態 (可以是隨機產生或其他方式)
- 下一代由這一代交換部分資訊或者是突變等等
- 兩個parent state會合併產生下一個state
- child可能不一定各從parent繼承一半,有可能是偏向比較好的那一個parent
- 每一個parent可能不只被拿來繁衍一次(比較好的繁衍多次),也可能有parent完全無法被挑來繁衍
- Evaluation function (fitness function)
- 用來決定新狀態的好壞
- 要找一個方式把當前狀態用類似基因的方法編碼
- 可應用於藝術設計、蛋白質結構解析等等
- 從單人的世界進入多人的世界:有對手出現
- 甚麼時機使用local search?(從手邊已有的解答,看看怎麼走比較好)
- 環境需要有local方向性的指引(往哪走比較好?)
- 不一定需要global:就像你不必知道南寮在哪,但知道要往北走。到那邊在找新線索
- 問題:注意不要進入local optimal
- A*需要有global的資訊
- 因為heuristic需要知道往後大概的cost如何,如果完全不知道往後狀況就沒辦法有好的heuristic
- local search的環境假設:解的旁邊一定也不錯
- 很少出現大海撈針的狀況
- 環境需要有local方向性的指引(往哪走比較好?)
- 平行的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?
- 環境是固定,因此一切的變數由對手決定(因此建立"對手"的model)
- 如果把對手想為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
- algorithm
- 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來滿足觀察
- 如果蒐集到很多對手下的棋局,又能學到學到甚麼?
- 假設拿到了(高手)對手的eval function,此時該怎麼做?
- 假設對手是我,運算速度相同,使用相同Eval function
- 另一種思考角度
- 對手怎麼看我?
- 比我怎樣看人重要!
- 旁觀者怎麼看我?
- 我希望別人怎麼看我?
- Agent的自我覺察(self-awareness)
- 別人怎麼看我?
- 別人對我的期待是甚麼?
- 以上兩者之間有沒有落差?
- 對手怎麼看我?
- 西洋棋 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:下次對象可能固定也可能是隨機
- 一大堆agent的集合,如同一個很大的網格,每一個格子都是一個agent
- 那許(Nash)均衡點
- 雙人以上non-cooperative game的解
- 每個人都知道其他人的均衡點策略
- 沒有任何人只靠修改自己的策略來得到好處(必須要其他人也跟著改)
- 決策時必須考慮其他agent的決策
- 策略互動模型的基礎
- 例如:
- 海灘上的兩家冰店,均衡點為兩個人都開在正中央
- Prisoner's Dilemma:scoundrel (囚犯困局其實就是Nash均衡點的一個例子)
- 軍備競賽(知道競爭沒意義,但又怕輸),均衡點為繼續造武器
- 戰爭撤兵(都知道打下去沒意義,但又不肯先撤兵怕吃虧),均衡點為繼續不撤兵
- Coordination game
- 狩獵:兩個獵人,可以自行打兔子,但是打鹿必須要兩人合作才有辦法成功
- 每個獵人可以繼續自己打兔子,或者是前往打鹿(但一個人會失敗,甚麼都沒拿到)
- 但如果剛好另一個人也去打鹿,則收穫都很大
- 均衡點:兩個人都在打兔子,因為都怕對方沒去打鹿,自己卻沒獵到兔子
- 每個獵人可以繼續自己打兔子,或者是前往打鹿(但一個人會失敗,甚麼都沒拿到)
- 狩獵:兩個獵人,可以自行打兔子,但是打鹿必須要兩人合作才有辦法成功
- 如何跳出不佳的Nash均衡點?
- 眼光放遠,計算長期利益:iterative model
- 保持耐心,多做試探:memory model(記憶更多過往的例子,推測對方,而不是謹記住上一次的結果)
- 多方面探索可能的合作對象:parallel & distributed model(例如基因演算法,在不同的起始點發展不同的策略)
- 雙人以上non-cooperative game的解
- 觀察
- 多人世界中,不一定要把別人想成自己:無論對手或隊友,都可以個別建立模型
- 多人世界中,經由互動產生的複雜系統:不斷發展的動態平衡,需要持續學習來因應
- 過去可用的策略,現在不一定可行
- 跳出過去的Nash均衡點:需要有動態的流動(才有辦法產生更多的變化)
- 策略代理人(strategic agents)為一個系統:
- 不只是一個**"方法"**
- 具有整體結構和參數
- 從系統觀點來看學習
- 分化與分工
- 分工的目的:形成更大的組織單位(或building block)
- 過程中的資源引導
- 一開始是競爭而不是合作,但到最後可能發展出一個平衡(甚至是合作)的情境
- 獵人與獵物
- 學習:結構優先,參數其次
- 結構影響遠大於參數
- 獵食者與獵物的共同進化 (類似軍備競賽,兩邊互相進化)
- 獵食者:獵豹、矛、處理Data的Program
- 獵物:羚羊、盾、Data
- 結盟
- 從軍備競賽升級為攻防同盟
- 盟約的締結需要雙方同步?
- 囚犯困局:誰先讓步?
- 單方面釋出善意就足夠?
- 尤其沒有直接利害的時候
- 例如蚱蜢先爬到蛇背上求保護,幫他抓癢。他知道蛇不會立即吃他(沒有直接利害),故先釋出善意
- 偏好結盟的基因:天生會想結盟
- 小精靈的學習
- 如何學會躲鬼?
- 如何學會吃豆子?資源引導
- 如何學會利用大力丸
- 鬼的學習?
- 多人世界中的結盟?多鬼?多精靈?
- 你的行動會造成別人條件的改變
- 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
-
重點:
- knowledge-based agent
- 學習
- Propositional (boolean) logic
- inference rules
- knowledge-based agent
-
knowledge base(KB) = set of sentencecs in a formal language
- Declarative apporach:看到事實,就告知自己的KB
- 你的knowledge base需要知道甚麼,就把看到的告訴他(tell)
- tell之後,詢問自己(ask):現在該做甚麼?
- KB會推理出答案
- 以knowledge level的角度來看:他有多聰明?不管實作細節
- Declarative apporach:看到事實,就告知自己的KB
-
KB agent
- 需要表達出state、action
- 觀察外界
- tell KB有關新的知識
- ask KB要做甚麼,KB給予action
- 執行action後再tell KB
-
不只是從"已經看的到的事實"去推論,也可以從"本來該存在而現在卻看不到的"去推論發生甚麼事情了
- wumpus小鬼例子:為何在這一個房間無法聞到小鬼的味道?可以推論出小鬼的位置的可能性?
- 例如:進入麵包店,為何沒有聞到麵包香?推論出麵包可能是假的(用蠟做的)!!
- 要能夠做這類判斷,心中一定要有個model:要知道甚麼時候缺甚麼,可能會來自甚麼原因(例如麵包店中沒有香味,可能是因為麵包是假的)
- 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
- M(alpha) = (1,2)是安全,(2,2)或(1,3)分別是XX,XO,OX,OO:共四種可能(O = 有陷阱)
- 換句話說,【(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)
- 類似:反證法基於我們假設是錯的確發現矛盾或不滿足,進而推斷出原本的是正確的
- 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中哪些事實有關
- 將所有滿足KB當前內容的rule找出來,然後把他加入KB,直到想要的答案找出來
- Backward Chaining
- 由問題往回推,然後遞迴去證明
- 問題是Q,已知P=>Q,則問題變成把P證出來。若有多條X=>Q,則每一個X都要試試看
- goal-driven:由目標驅動的
- 較適合解決問題
- 複雜度較低
- 有不同演算法,有complete版本,也有因為求快而不complete的
- Summary
- Logical Agent將inference應用到KB上,來得到新資訊與做決定
- inference:從某一個sentence推出另一個
- 上一章的Propositional Logic為Zero-Order Logic
- 好處:Declarative
- 允許部分資料是negated等等
- 可做運算
- context-independent
- 不像自然語言,不同內容的symbol,則意義不同
- 壞處:表達性非常有限
- 好處:Declarative
- 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且都很聰明
- 例如:For all: x At(x,NCTU) and Smart(x)
- For All
- 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)]
- term1 = term2
- 與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:由原因推出結果
- 例如:如果此房間有陷阱,就可以推論出鄰近房間會吹到風
- Diagnostic rule:由結果推出原因
- Knowledge engineering in FOL
- 找出要達成的task
- 例如1bit 加法器:當前電路是否正常運作?
- 將相關的資訊、知識找出來
- 有AND、OR、NOT、XOR等logic gate
- 不相關的範例:gate的大小、形狀、價格、顏色等等
- 決定有那些predicate、function、constants
- Type(X1) = XOR
- Type:用來表達某一個gate的類別
- Type(X1) = XOR
- 用邏輯的形式表達該domain一般的知識
- 例如:
- 1 != 0
- 高電位與低電位是兩件不同的事情
- ForAll t:Signal(t) = 1 OR Signal(t) = 0
- 所有的信號不是高電位就是低電位
- 1 != 0
- 例如:
- 將某一個問題用剛剛的那些syntax表達出來
- 用Type與Connected來表達線路連接
- 將這個問題作為query丟進去inference procedure
- 若無結果,可能是表達錯誤或者是不完整
- 對KB進行debug
- 找出要達成的task
-
降級處理:把FOL轉換成Zero-order:單純且沒效率
- Universal instantiation(UI)
- ForAll x:King(x) AND Greedy(x) => Evil(x)
- 將所有的x可能性全部帶進去,例如:John、Father(John)...
- ForAll x:King(x) AND Greedy(x) => Evil(x)
- Existential instantiation(EI)
- 找一個KB中沒有出現的symbol,將變數代換程該symbol
- Exist x:Crown(x) AND OnHead(x,John)
- 把x用新常數symbol C1帶入,C1為某一個王冠
- 代表John帶了某一頂王冠,目前還不知道,暫且稱為C1
- 造成的問題:變數可能性無限多,代不完
- semidecidable
- 若這件事情為真,就一定可以找到一個方法/演算法證明其為真
- 反之若為假,則不一定找的到(不是有限的結束時間)
- Universal instantiation(UI)
-
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}等代換沒太大意義的常數
- Unify(a,b) = c,若ac = bc
-
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移除
- 要把Exist轉換為function
- Search與Planning的差異?
- Search:效率差
- 買某個東西,去商店街所有店鋪搜尋
- Planning:
- 在買某個東西之前,先想想如何得到這個東西,在去找
- Goal-Based Agent
- Search:效率差
- 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