AI定義(不同類別):
a. 思考面:
- AI需要以人類方式思考
- 需要以一定方式思考，解決問題即可算是AI
b. 行為面:
- 活動行為需要像是人類
- 只要能夠實際解決問題(不論移動方式)
- Agents -> 任何可以藉由sensor感知環境，並且藉由actuators互動的原件
- Rational agent -> 在所有可能性中，選擇最佳解的主體，由於在rational agent的觀點上並非全知觀點，因此我們期望rational agent有學習的能力，從現有資料中學習以選擇最佳解
- agent = architecture + program
simple reflex agents
- 單純以現有環境資料作為決策的依據
Model-based reflex agent
- work in a partially observable environment, and track the situation.
- 兩個在models-based reflex agent中重要的部分: 1.Model: It is knowledge about "how things happen in the world," so it is called a Model-based agent. 2.Internal State: It is a representation of the current state based on percept history.
Goal-based agents
- The knowledge of the current state environment is not always sufficient to decide for an agent to what to do. 需要有最終目標，而非給予規則，由目標選擇達到目標的作法
Utility-based Reflex Agents
- 類似Goal-based agents
- 作法並非單純達到目標，而是能夠最佳的達到目標
- 會將每個狀態轉換成數值，以觀看達到目標的效能
Learning Agents
能藉由過往經驗學習 A learning agent has mainly four conceptual components, which are:
1.Learning element: It is responsible for making improvements by learning from environment
2.Critic: Learning element takes feedback from critic which describes that how well the agent is doing with respect to a fixed performance standard.
3.Performance element: It is responsible for selecting external action
4.Problem generator: This component is responsible for suggesting actions that will lead to new and informative experiences.
- Introduction of Problem-solving agent(one kind of goal-based agent)
A problem can gradually defined by five part
- Initial state (最初始的狀態)
- posible action (可能採取動作)
- description of each action does(transition model -闡述這個action的執行，例如result(initial state,action)= next state )
- goal test/goal state(目標狀態)
後續以下圖問題作為範例:
Searching Alogorithms
-> searching tree
在樹上的節點N，包含四個結構分別如下:
- n.state - 當節點的狀態
- n.parent - n節點的上一層節點狀態
- n.action - parent 執行甚麼動作達current node
- n.Path-Cost - denoted by g(n)，path cost between the initial state and current(初始到現在節點的損失)
Uninformed Search Strategies
- 策略沒有關於問題定義的額外資訊，因此使用目標導向。
同層節點完全展開，在確定該層節點沒有目標解，才會進入到下一層的節點
在假設每層上有b個節點時，展開到第d層所需展開節點數量為 sum(b^n^(n:1->d))，由此可見其時間與空間複雜度為O(b^d^)
由最小損失路徑(
min(g(n))為目標，逐次展開節點
假設C'為最佳損失(最小)，且每個步驟損失最少為e，則此方法的時間與空間複雜度為O(b^1+(C'/e)^)
先鎖定單個節點，並且將其朝向單一方向展開至最深層，若沒有找到目標解，再逐層往回回推
其時間複雜度為O(b^m^)，當中m為最深深度，因此m可能相較於BFS當中的d要大很多，空間複雜度為O(bm)，因此在設計上可藉由指定深度減少空間以及時間複雜度。
每次疊代增加深度，但當次疊代的找尋方法同DFS，這樣的好處是，當深度為m，但解答在n層就出現時(n<m)，則可在第n次疊代就藉由DFS的方式找到，而不需要直接搜尋到第m層，能夠有效減少複雜度
雖然疊代會產生一定的計算量，但與直接利用DFS找尋到m層來說，以疊代的方式找尋到n層還是可以有效減少複雜度，主要是因為在時間複雜度上是以次方方式增長
只有兩種選擇方案的搜尋方式，因此並非每種狀況皆可使用。
Informed (Heuristic) Search Strategies 可得知距離初始狀態距離，並且藉由啟發函數推算距離目標距離，並依造評估函數f(n)，決定要展開哪個節點，進而增加效率。
- heuristic function, denoted as h(n)
h(n) = estimated cost of the cheapest path from the state at node n to a goal state.
展開最接近目標的節點，單純使用heuristic作為預估。
然而，此方法未必是最佳解。
利用到達現節點的損失函數g(n)，以及預估到達目標的損失函數h(n)，則f(n)=g(n)+h(n)
當使用A^*^ search要達到最佳解時，須符合兩個情況分別為:admissibility(可受理性) and consistency(一致性)
- admissibility ->要求h(n)必須為admissible heuristic，代表此方程式在預估到達目標的損失時，必須不會高估損失(預估的損失必定小於或等於真實損失)
- consistent(monotonicity) -> 假定現今節點為n，而經過action a 到節點n'後，則h(n)與h(n')間有關係式:
上式當中，c代表由n採取狀態到n'中損失的距離，此式等同於三角不等式(可用向量思考)。 A^*^ search 總範例如下:
允許出現選擇較差點的選項，但每次選擇較差點的機率會隨疊代下降(T)，而當delta(E)>0，則為較佳解，一定前進，若<0，則為較差解，每次疊代有e^delta(E)/T^的機率選擇。
每次疊代，溫度(T)會下降，因為不希望再多次疊帶後，還有相同的機率，取到較差的結果點
每次展開K個點，並且在該K個點內搜尋目標點，若沒有目標點，則會從從中選擇K個最佳選擇器，並依此重複展開K個點
初始時有N個序列，在依造正確率作排序，於排序後兩兩序列為一組，切分序列並做交互替換(crossover)，產生新的序列，並且依照突變率隨機改變序列內容，以此作為下一次預測模型。
大原則隨機切分，但是在不同領域跟應用上，可能可以在crossover上給定限制
在描述問題上，若是由果導因可能會需要列出無限種可能性，例如:
Toothache =>Cavity V GumProblem...
因此可嘗試由因導果的方式描述問題，例如:
Cavity => Toothache
然而在上述的例子內，也並非完全正確，因為未必所有蛀牙皆會造成牙痛的情形，因此由機率表示未失為一個好方法。
決策理論 = 機率理論+效用理論，在決策理論的核心概念為，只有當選擇的行為擁有最高的預測效用，且平均超過所有行動的可能結果，才視為agent為合理的，此原則稱為最大預測效用(MSE => maximum expected utility)
驗前機率:該機率與其餘機率無關
驗後機率:該機率建構於另一機率之上，因此需先算另一機率才可得出該機率
上式代表，當發生b的情況下同時發生a的機率，因此藉由數學運算可得:
在機率表示內，細體字的P代表單一情況發生的機率，
粗體字的P代表所有情況所形成的機率向量，例如:
P(X|Y) =P(X=x
i|Y=yi)
代表列出i,j形成的二維向量，當中包含i,j各種情況的機率
P(A,B)代表的是結合A,B兩種情況的所有可能性，稱為joint probability distribution。以下以A為天氣，B為蛀牙，天氣內有四種情況而蛀牙有兩種情況作為舉例:
則其展開式為:
註解:在機率表示式內，如果開頭是大寫則是當中的所有可能，小寫則是確定情況，例如Cavity代表的是有蛀牙以及沒蛀牙兩種情況，cavity代表的是只有蛀牙的情況
聯集表示法:
P(a ∨ b) = P(a) + P(b) − P(a ∧ b)
正常化法->當今天要計算交集機率時，可以使用兩者的joint probability，並使用正常化得出，而不需要得到母體的機率，例如:
上式代表今天已知牙痛，且欲求到牙痛且蛀牙的機率，或牙痛沒蛀牙，則可能性分為:
1.牙痛、蛀牙且被探針偵測
2.牙痛、蛀牙且沒被探針偵測
3.牙痛、沒蛀牙且被探針偵測
4.牙痛、沒蛀牙且沒被探針偵測
因此可表示兩個1x2矩陣。
P(a|b) =P(a^b)P(b)，則由此關係是可得到:
P(b|a) = P(a^b)P(b)/P(a)
此關係式及為Bayes' Rule，若以joint probability角度改寫，則為以下:
This formula shows that we have some occasion to use more general version conditionalized on some background evidence e.
Bayes' Rule在一般的情況下看似沒用，但其實在應用上有很大的公用，例如今天得知一疾病與伴隨特定症狀的機率，且有該疾病的發生機率，以及該症狀的單獨發生機率，則可利用Bayes' Rule反推出出現該症狀時罹患疾病的機率。
Bayes' Rule應用如下:
上式中的等號左邊代表找尋牙痛且被探針搜尋到的情況下，有蛀牙以及沒蛀牙的個別機率，等號右邊為利用Bayes' Rule尋找交集部分後，再利用normalized將機率兩者形成互補為1。
Bayesian network是一個有方向性的圖表，每個節點內包含相對應的機率資訊在內，整體的規範如下:
- 每個節點對應到一個隨機變數(可為連續或離散)
- 由帶方向性的連結或是箭頭連結兩節點，若由節點X指向節點Y，則稱節點X為節點Y的父代(parent)
- 每個節點X
i會辦隨著一個條件機率P(Xi|Parent(Xi))，作為量化父節點對於對於當下節點的影響。
由上圖作為解說，從圖中我們可看到，在上一章的牙痛關係中，天氣是從當中完全獨立出來，而蛀牙會與牙痛以及是否被探針偵測到有直接關係，然而牙痛與探針偵測卻並無直接關係。
後續以新的範例作為解說，現在假設有一個警報器當發生竊盜時會鈴響，而有時若是發生地震時也會造成警報器的觸發，且有兩鄰居John&Mary答應會在響鈴時打電話通知，兩者之中John對於鈴聲的敏感度較高，但偶爾會與電話鈴聲搞混，Mary時常播放大聲的音樂，因此時常錯過警鈴的響鈴，依造上述的敘述，我們可得到Bayesian network如下:
在上圖中，沒有父代的節點層稱為驗前機率(prior probabilities)，同時在上圖中，並沒有標示Mary播放大聲音樂的機率，以及John搞混電話與警鈴的機率，這些機率被包含在從Alarm指向兩者的過程中。
要展示Basyesian network的結構我們會以conditional probability的形式改寫joint probability，並以此逐項展開，此步驟稱為鏈鎖綠(chain rule)，如下:
用conditioanl probability改寫joint probability
展開joint probability
注意joint probability的展開很重要
對於Xi的父代節點，應該直接影響Xi，範例如下:
上式中，由figure14.2中我們可看到，地震與盜竊而響鈴並非影響到Mary有沒有打電話的因素，而是影響到是否響鈴，而John是否打電話也無影響到Mary打電話的意願，在所有之中，真正影響到Mary打電話的因素只有警鈴是否有響，因此真正影響Mary的只有他的父節點Alarm，因此可將機率寫為P(MaryCalls|Alarm)
Bayesian network的緊湊性(compactness)是局部結構化的，也就是說在bayesian network內元素(節點)只與相鄰的有關，而不與其他元素有關聯，有時並非單純與父輩有關聯，例如發生地震時，John跟Mary可能會因為考慮到是因為地震的原因，而導致警鈴作響而因此不打電話，但這種關聯性過低，若是將此條件也加入Bayesian network內，可能會導致過於複雜，因此加入的利潤過低。
若是開始時所繪製的順序錯誤，可能會導致網格過於複雜，例如:
若是今天的變數為連續變數，而非離散，則可以使用離散化的方式將連續變數轉為離散變數，舉例而言可使用高斯轉換，而當今天變數同時出現連續與離散時，我們稱該種bayesian network為hybrid Bayesian network，例如下圖的cost為連續變數，而buy為離散。
使用pro-bit/logistic/Gaussian轉換後，可將機率表示為下圖
設定X為query variable，E為evidence variables sets，e為特定的observed event，Y為nonevidence,nonquery variables，則完整的Xset 可表示為:X = {X} ∪ E ∪ Y，當一個典型的查詢要求對於後驗概率分佈表示為P(X|e)。
同樣也可將P(X|e)藉由正規化的方式表示為:
由此我們可下總結如下:
Therefore, a query can be answered using a Bayesian network by computing sums of products of conditional probabilities from the network.
上圖展示的是b=True的情況，因此要求b=False的情況則用同邏輯展開。
可先將f3，f4歸納成一個2x2的矩陣，這邊以警鈴是否有想做歸納，得出:
則原式改寫為:
再依造地震是否發生做歸納，得出:
則原式最終可改寫為:
Variable Elimination Alogrithm便是依造此種方式，將式子作化簡，將原本複雜的式子改寫為2x2x2的矩陣。
這邊會用到與積分相同觀念，若是今天的變數與加總無關，則可以先移出summation符號之外，與積分時若是變數與積分像無關，可當成常數移出積分符號相同，且此種方法很吃個人對於數學的歸納還有靈敏度，不同的歸納方式還有順序會造成不同的式子。
後續題目以此較複雜的Bayesian Network做範例:
邏輯為:利用拓樸排序的方式對每個變數做採樣
In this case, PRIOR-SAMPLE returns the event [true, false, true, true].
現在假設有一個依造PRIOR-SAMPLE演算法的機率組Sps(x1,.....,x2)，則此機率組可表示為:
because each sampling step depends only on the parent values.
在此以上面的例子作為延伸，若是要表示這邊的[true, false, true, true]，則可寫為:
當我們大輛採樣N次後，我們期許我們採樣的機率會與sample的機率也就是Sps相同，因此在這個例子上我們期許採樣N次內會有32.4%的samples為[true,false,true,true]的情況。也就是:
我的理解->會先依造網路依造事前分配產生樣本(samples)，再從這先樣本中拒絕沒有對應到指定證據的樣本(reject the samples that doesn't match the evidence)
