Posted on

Intro to Artificial Intelligence

課程網址:https://www.udacity.com/course/viewer#!/c-cs271

什麼是Intelligent Agent

人工智能代理(Agent)根據環境的感知器(下圖的Sensors)傳入的資料,經過一連串的映設函數(紅箭頭部份),藉由效應器對環境做影響(下圖Actuators)。在裡面紅色箭頭部份是最重要的課題,這稱為代理控制策略。
螢幕快照 2014-02-18 下午11.05.25
如上圖這樣的一個決策過程會重覆進行很多次,從環境將資訊透過Sensors傳給Agent,經過代理做出決定,然後用Actuators影響環境,這樣的一個周期稱為perception action cycle。

AI應用範疇

  1. 財務金融:應用環境可以在股票市場、債卷市場或期貨市場,感知到一些東西的資訊和相關新聞,決策則是買入和賣出。
  2. 機器人學:這個是研究時間最長的一門ai領域,他的Sensors及Actuators都是與物理環境交互,而更為特殊。
  3. 遊戲:分兩種,一種是與人類對戰,像是象棋對戰,對Agent來說玩家是環境,它必需觀察玩家的動作,目的是戰勝玩家。另一種是遊戲情境模擬,為了要讓遊戲更自然,讓玩家感覺遊戲世界像真實世界般。
  4. 醫藥學:可以用在終身醫療上,輸入過去病史,讓它可以幫助判斷未來可能出現的疾病。
  5. WEB應用:像智能搜索,對語意進行判定,然後幫助找出可能更符合使用者想要的搜尋結果。

術語介紹

  1. 完全可觀察的環境 vs 部份可觀察的環境(partially)
    完全可觀察:例如一些牌類遊戲,當所有牌都已被掀開在桌子上,我們可以看到所有的資訊,可以算出最佳解答。
    部份可觀察:像另一些紙牌遊戲,有些牌是掀開的,有些則是未被掀開的。這時就要去觀察並記憶過去曾有的牌型紀錄,和桌上現有的牌,來推算可能是最有利的出牌方式。越多的歷史紀錄可以幫助Agent去做出更正確的推斷。這個循環稱為馬爾可夫模型(Markov Model),我們會廣泛的討論要如何具有下面的這種結構:
    螢幕快照 2014-02-19 上午1.10.56拷貝
  2. 確定性環境 vs 隨機性環境(stochastic)
    確定性環境:Agent所做的結果會產生的影響是否確定。例如像在象棋遊戲中,移動一個棋子的效果是完全可預見的。
    隨機性環境:像是大富翁的擲骰子遊戲,雖然所做的決定會影響結果,但是我們無法預期骰子會擲出多少,因此無法完全預見所做決策會影響到的效果。
  3. 離散環境 vs 連續環境(continuous)
    離散環境:有有限多個選擇和可能性,例如象棋遊戲。
    環境:可做的行動或可能性是無限的,例如丟飛鏢會有無限種角度的可能性與加速方式
  4. 良性環境 vs 敵對環境(adversarial):環境因素的存在與影響是否剛好與我們所要達成的目標相反?

AI的不確定性

螢幕快照 2014-02-19 上午1.51.16

包括感知器的有限、很多時候會忽略掉某些不重要或無法判別的因素、敵對因素的影響、隨機性環境的不可預測因素、可計算的步數有限性等…。而AI的存在就是在處理並控制不確定性以供做出決策的規則。

定義問題

  1. 初始狀態:一開始的狀態
  2. 動作狀態:若當Agent處於該狀態時會有那幾種可能性(返回一組該狀態可做行動的序列)
  3. 結果狀態:一個狀態和一個動作為輸入,一個新的狀態為輸出
  4. 目標測試函數:是否這個狀態是可達成目標的。
  5. 路徑成本函數:計算從a狀態到b狀態要花的成本

幾個路徑計算方式

螢幕快照 2014-02-19 下午2.20.59
求從上圖的路徑中的A點到B點的最佳路徑的方式有下面這些工具:

  1. Graph Search vs Tree Search
  2. Graph
  3. Tree
  4. BFS
  5. DFS
  6. Best-first Search:在大部份的時後,找到最佳解是最困難的,因此這部份很難實作,有許多文章有在探討相關實作方式。

像上述的這些搜尋方式,是完全不考慮有什麼意外發生的狀態下才有效的。
要使用上面這種路徑搜尋方式,環境必須符合下面幾項條件:
螢幕快照 2014-02-19 下午2.12.33

  1. 搜索域必須是完全可觀察的,換句話說,我們必須具備觀察我們開始的初始狀態的能力
  2. 域必須是可知的,我們必需知道我們可採取的行動的集合
  3. 必須為離散域,可選擇的行動的數量必需是有限的
  4. 域必須是具有確定性的,必須知道採取某一行動所產生的結果
  5. 域必須是靜態的,除了我們自己的行動以外,域中不可以存在任何可以改變它的東西

在AI中以機率去找出最佳解

貝葉斯概率:http://wiki.mbalib.com/zh-tw/%E8%B4%9D%E5%8F%B6%E6%96%AF%E6%A6%82%E7%8E%87
聯合概率分布:http://zh.wikipedia.org/wiki/%E8%81%94%E5%90%88%E5%88%86%E5%B8%83
貝葉斯網絡可以簡潔地表示一個聯合概率分佈狀況,如下圖可表示一個汽車壞掉可能原因的貝葉斯網路圖,我們觀察一些面板數值,然後去推斷可能的原因的發生機率,再去做交叉比對,這樣就可以列出一個概率分布圖。
螢幕快照 2014-02-19 上午3.15.19

機率學相關概念:互補事件獨立性事件(任意兩個變量的聯合概率是兩個機率的乘積)、貝葉斯法則

貝葉斯公式

螢幕快照 2014-02-19 下午7.55.50
P(A|B) = P(B|A) P(A) / P(B)
P(A,B) = P(A|B) P(B)

經過如下的推導
未命名1
可得知P(A,B|C) = P(A|B,C) P(B|C)

這邊有相關的理論說明:條件機率與貝氏定理

範例題目
螢幕快照 2014-02-19 下午5.37.10

是在探討今天若心情很好P(H)可能原因有天氣好P(S)或是被加薪P(R)
假使天氣好P(S)的機率為0.7
被加薪P(R)的機率為0.01

P(H | S,R) = 1 >> 天氣好且被加薪,心情好機率為1
P(H | ^S,R) = 0.9 >> 天氣不好但被加薪,心情好的機率為0.9
P(H | S,^R) = 0.7 >> 天氣好但沒被加薪,心情好的機率為0.7
P(H | ^S,^R) = 0.1 >> 天氣不好又沒被加薪,心情好的機率為0.1

則求出P( R | H,S)  > 也就是求出在心情好且天氣好的狀況下,是被加薪的機率
下面是好心人在討論版所給的詳解方式

According to Bayes formula p(R|H,S) = p(H,S|R)p(R)/p(H,S) = p(H|S,R)p(S|R)p(R)/p(H,S) (1)
In the second equality we used the analog of formula p(H,S) = p(H|S)p(S) but under definite value of R: p(H,S|R) = p(H|S,R)p(S|R).
Further, p(S|R) = p(R|S)p(S)/p(R). Plugging it in the formula (1) and accounting that p(H,S) = p(H|S)p(S) we get the targeted expression:
p(R|H,S) = p(H|R,S)p(R|S)/p(H|S). It’s the strict formula and should be remembered. It’s easy if you note that this formula is the custom Bayes rule p(R|H) = p(H|R)p(R)/p(H) but under definite value of S of all probabilities in the formula.