AI 筆記9 - Un-informed Search: Uniform cost search

UCS: BFS的變形

這個cost我們之前都沒有考慮過，如果path cost不是1的話，對BFS來說，不能保證optimality，因為search tree中最淺的solution不見得是optimal的。

BFS的搜尋是以深度當作layer，而UCS的則是以cost function g當作layer：

改寫expand function

先定義expand: 意思就是從fringe中拿出下一個要explore的node。

當cost不再是1的時候，我們改成以least cost children來優先從fringe中拿出來explore。

注意我們除了用min-heap之外，我們也要update heap中的unexplored node cost，因為我們可能找到cost of path to root更少的path。

Performance

complete: Yes! 如果solution是finite cost 。UCS保證會找到solution。

time: 這比較難分析了，因為他search layer是by cost不是by depth，但是我們的search space仍然用search tree model，所以還是要給一個近似深度的函數。我們假設optimal solution的path cost to root = C*，而每個state - state action cost至少是e，則可以定義出一個“effective depth”＝ C* / e，至少要搜尋這麼多的layer，這相當於d factor in BFS ，所以time complexity:

space: 和time complexity一樣。

optimal: YES，因為這就是UCS彌補BFS的目的。



這是一個complete & optimal search algorithm!

範例

我們要找以下graph S->G的最短路徑。

1. explore and expand S

2. explore C，因為cost最少：

3. explore A

4. explore E，注意我們update B的cost成 5，因為經由explore E我們發現一條cost更少的路徑從S到B (S -> C -> E -> B)，這就是演算法中所謂decreaseKey的意義：

5. explore B:

6. explore D:

7. explore F:

8. reach Goal

AI 筆記8 - Un-informed Search: Depth limited search & Iterative Deepening

Depth limited search

DFS可能會在某個subtree極端深入，但是最後是fail node。我們要限制factor m，可以定義一個最大搜尋深度限制factor L。這通常在我們對problem有domain knowledge的時候（那不能放入un-informed search吧？！）。

Iterative Deepening: 

這其實是DFS的變形，但卻有深度限制控制：

我們照常做DFS，但是每個iteration只停在搜尋深度限制L。
下一個iteration我們會放寬factor L，直到我們找到最淺層的solution，由於深度被控制，每個iteration疊加起來看起來有點像是BFS。見以下範例：

Optimal if path costs are positively identical: 因為每個depth的subtree一定會整個search完，不會是像default DFS一樣在哪一個branch找到goal node就放棄了其他的sibling brach。

AI 筆記7 - Un-informed Search: DFS

DFS(先找最深的node)

演算法跟BFS不一樣只在使用了LIFO stack而非queue。

DFS Performance

complete: 如果不revisit explored node的話，search space是有限的，就會保證我們一定找到solution。

time:  同樣我們定義effort為“expanded nodes數目”。

這邊用m這個參數表示“可能抵達的最大深度”，因為DFS遇到fail node才會backrack，所以可能已經抵達很深的depth = m才backtrack，最後在某個較淺的subtree depth = d找到solution，不過不懂為什麼是以下的式子：

所以當m >> d的時候，那就是一個很糟的problem instㄝance。
但是當 m ~= d的時候，DFS可能會比BFS先找到solution，因為DFS會比BFS expand較少的node。

space: O(bm)。這是一個linear space complexity （只跟m有關）。因為我們只需要儲存目前可以供backtrack的路徑上的nodes即可，所以每個level需要把b個nodes放入fringe，但同時最多只需要放入b*m個。

optimal: NO! 庭院深深深幾許啊！


DFS的linear space complexity遠勝 BFS！

AI 筆記6 - Un-informed Search: BFS

定義

對於problem沒有domain knowledge的search方法。
可能有以下幾種search strategy（也就是explore node的順序）：

不過先定義什麼叫explored:
1. goal-test
2. expand children nodes into fringe

BFS (先expand深度最淺者）

下圖中灰色代表放入fringe, 黃色代表被explored，黑色代表此subtree fails（不會再被expand)。

演算法如下：

可以看到其實跟general search的演算法幾乎一樣，差別只在於BFS單純用FIFO queue就可以達成。

分析BFS performance

complete: 如果branching factor(最大children node數目）是有限的，search space就是有限的，我們終究可以找到solution。

time: 可以定義成expanded node的數目，假設我們solution在depth = d的時候被expand，則我們總共expand了:

因為depth = 0有1個node (initial node)，depth = 1有b個nodes, depth = 2 有b^2 nodes，這個多項式是O(b^d)。

space: 看起來跟time complexity的需求一樣。

optimal: 意思是我們的演算法找到的goal是否是cost最低的？是的，BFS因為找最淺的node，所以如果每次step cost相同的時候，我們保證找到optimal solution。


BFS 是exponential time/space complexity，只有在某些特定的application才適合使用（solution會在很淺的node被找到）:

AI 筆記5 - Search Space

State Space

可以說是一個要解決的問題的所有可能的狀態(state)的集合。

Search Space

在解決問題的過程中，能抵達任何可能的狀態(state)的抽象路徑（藉由sequence of actions)。通常會用search tree 資料結構來model search space，每個state就是一個node。

每個node會有一個expand function，告訴我們怎麼map一個parent node到所有的children nodes。

search nodes 有三種state:

1. explored: 已經explored的nodes 
2. frontier / fringe: 下一批要被explore的unexplored nodes的queue
3. unexplored

所以一開始所有nodes會是unexplored，然後隨著演算法挑選哪些要加入frontier，然後再從frontier去explore所有的frontier nodes。

Tree Search Algorithm

演算法框架如下，簡單來說就是一個個explore node，但什麼順序explore node 則是獨立的演算法(search strategy)，可以視需要抽換，例如BFS or DFS。

上面這個演算法，以下tree就是上面演算法的視覺化：

如果我們用DFS來選擇exploration的順序：

不過這個馬上面臨一個問題，child node A也能再回到parent node B，如果neighbors(A)有包含B的話，這會形成infinite search space，也就是我們演算法會形成無窮迴圈。

改良：graph search with explored set

不過其實可以一開始就講graph search不就好了.... @@

Search Strategies

就是決定fringe裡面哪一個先被explore的順序的演算法。

這個演算法好壞取決於time/space complexity，有以下三個面向：

(1) maximum branching factor b: 一個node最多有幾個action (to children)

(2) 到solution的深度 d

(3) state space的最大深度 m: 這可能是無限的！

AI 筆記4 - Search Agents & Problem Formulation

Goal-based （Search) agents

goal-based agent透過找到goal的state to state path，解決問題。找尋通往goal的path，可以被formalize成一個search problem。

所有可能的states(不一定能到達goal) 組成一個search space，就像下圖中所有可能抵達中心的路徑：

Search Space

search space有點類似sample space，也就是所有可能的states的集合。以8-queens來說，search space總共有64*63*... * 56種可能的8個queen放置在棋盤的方法（也就是這8個queen組成一個棋盤的screenshot state)。

goal-based agent只要找出其中一個goal state即算是solve the problem。

Solve Search Problem的步驟

1. formulate problem:

• 定義initial state為何？
• 定義所有state space ，就是initial state透過action sequence能夠抵達的其他states
• 定義action space，也就是所有的state能做的actions
• 定義transition model，也就是state A經過某個action map到哪一個state 
• 定義goal test
• 定義path cost

2. formulate goal
3. calculate solution (offline): 先算好在行動，所以基本上有environment overview
4. execute solution

8-queens Problem Formulation 範例

state：0~8個queens 在棋盤上的位置。
state space: 所有state的可能排列組合。
initial state: 這個就是0個queens的state，也就是棋盤是空的。
actions: 在棋盤空格加上一個queen
transition model: action會讓棋盤的state自然的改變
goal test: 8個queen同時在棋盤上，但是沒有任何兩子會處於可以吃掉對方的位子

Routing Problem Formulation範例

懶得打字，上圖比較快！

AI 筆記3 - Agent types

Simple Reflex Agent

中文應該就是簡單反射條件agent，也就是只對“目前的刺激(percepts)做出反應”，而不去管過往的perception歷史。

能夠“只管目前環境刺激”，代表我們對環境全局完全了解，才能選出一個相對應的動作，所以這個agent只能在fully observable 環境運作。

這種agent其實就是依賴一個mapping table (state -> action)，但是當某個sensor壞掉，也就是無法collect完整的state時候，就掛點了。這時可以加入一些randomization，讓壞掉的sensor回報的資料做隨機性的選擇，算是一點點的改良。

Model-based reflex agent

這種agent對世界環境有其猜測，認為環境符合某個model （也包括agent參與後如何改變世界的考量），maintain internal states，所以他可以在partial observable的條件下運作。

model通常是依賴percerpt history。

Goal-based agent

這種agent把未來考慮進去，所謂未來就是action是否朝向maximize goal的方向前進？

Utility-based agent

goal可能可以通過不同的途徑抵達，所以我們需要找到一個能讓agent最滿足的途徑，透過utility function來評估。

Learning Agent

透過data“學習”，因為program agent是一件困難的事。這是machine learning algorithms。

AI 筆記2 - Rational Agents and Environment

Agent定義

就是簡化人類跟世界的關係，看下圖：

中間問號部分就是decision making。

所以人類也是一個agent，因為人類有sensors可以感受世界，有actuators可以動作，有大腦可以做decision。

吸塵器例子

一個智慧吸塵器是一個agent，有以下的components:
1. percepts: 在哪一個房間，或是房間乾淨程度
2. actions: 往某個方向移動，或是開始吸，或是停止吸
3. agent function: 這算是上面問號盒子的部分，可以是很簡單的mapping table，也可以是很複雜的演算法：

Rational Agent

agent要稱為理性的話，有個嚴格定義：根據percepts證據來最大化其goal。這個原本來自經濟學的概念，把人類都設想爲rational agent，不過事實上不是，才會造成一堆經濟學無法預測的狀況發生，不過這種問題不會出現在comupter agent身上就是。

可以用四個面向來評斷rationality，稱為一個problem的PEAS:

當然最重要的是performance，其他三者都是達成performance的條件。

Environment

agent的環境有很多種描述：

全局知識 vs 部分知識: agent的sensor是否有辦法percept整個environment的參數？

確定性 vs 隨機性: 下一個state是否根據現在state而確定，還是隨機的？後者會用probabilistic model。

static vs dynamic: 環境是否一直在改變

discrete vs continuous: 環境的states和對應的actions能否countably描述？

single agent vs multiple agents

known vs unknown: agent設計者對environment是否有domain knowledge?

舉例如下：

chess是semi static，因為可能有計時，所以環境的“剩餘時間”參數一直在改變。
poker是partially observable，因為你只能看到你手上的牌子

可以看到自駕車是最困難的環境，隨機之外，環境還是變動的，而且還有multiagents @@

Statistics筆記22 - CI範例

題目1

正確解讀CI
注意Confidence Interval 是用來解釋population parameter的possible range，而Confidence level是用來解釋我們對sampling distribution中的samples能夠有多大的機率（信心）涵蓋了真正的population parameter。

所以這題目的CI宣稱如下：我們有95%的信心相信老美平均每個月3.4~4.24天有壞心情。

正確解讀CL

95%的samples會產生能夠包含population parameters的CI。

題目2

這一題其實是要找CI。

不過首先要檢查是否能通過CI的conditional check:

sampling distribution mean = 3.2
sampling distribution SD = 1.74

95% CI z* = 1.96
standard error = 1.74/sqrt(50)

ME = 1.96 * 1.74/sqrt(50) = 0.4823034

所以 95% CI = 3.2 +- ME

Statistics筆記21 - 想要達到margin of error需要多大的sample size?

Margin of error

margin of error 與其他參數的關係：

其中z*是 cutoff value，這是距離mean幾個standard error的倍數
s/sqrt(n) 就是sampling distribution的SD, 也就是standard error

所以要達成某個ME，就是要對這些參數去manipulate。

範例

關鍵字：
90% CI
SD = 18

求使得ME<=4的n?

這題目等於是要縮小margin of error但是不改變90% CI，換句話說就是要增加sample size n，因為ME和sqrt(n)成反比。

首先我們可以知道一個normal distribution 在90% CI的cutoff value z*:

> qnorm((1-0.9)/2)
[1] -1.644854

當然我們取正值 1.644854

所以根據上面公式 1.644854 * 18 / sqrt(n) <= 4
n <= 55.13
所以n必須至少 = 56人

這個一樣把ME = 2帶入：

1.644854 * 18 / sqrt(n) = 2
n = (1.644854 * 18 / 2)^2 = 219.1491
所以n 至少要220人

另一個快速的算法就是，既然 ME和sqrt(n)成反比，所以1/2 ME就必須要有4*n才能維持等式。

所以56*4 = 224，約等於我們精確算出的220人。

這邊我們看到要縮減ME，必須要增加sample size，但這需要花更多的錢！