###### tags: `AI/ML`
# 人工智慧導論(修課筆記) (I)
## CH1 Introduction
AI定義(不同類別):<br>
a. 思考面:
>1. AI需要以人類方式思考
>2. 需要以一定方式思考，解決問題即可算是AI
b. 行為面:
>1. 活動行為需要像是人類
>2. 只要能夠實際解決問題(不論移動方式)
-------------------------------------------
## CH2 Intelligent Agents
* Agents -> 任何可以藉由sensor感知環境，並且藉由actuators互動的原件
* Rational agent -> 在所有可能性中，選擇最佳解的主體，由於在rational agent的觀點上並非全知觀點，因此我們期望rational agent有學習的能力，從現有資料中學習以選擇最佳解
* agent = architecture + program
> simple reflex agents <br>
> 
> * 單純以現有環境資料作為決策的依據
>Model-based reflex agent<br>
>
>* work in a partially observable environment, and track the situation.
>* 兩個在models-based reflex agent中重要的部分:<br>
>1.Model: It is knowledge about "how things happen in the world," so it is called a Model-based agent.<br>
2.Internal State: It is a representation of the current state based on percept history.
>Goal-based agents<br>
>
>* The knowledge of the current state environment is not always sufficient to decide for an agent to what to do.
>需要有最終目標，而非給予規則，由目標選擇達到目標的作法
>Utility-based Reflex Agents<br>
>
>* 類似Goal-based agents
>* 作法並非單純達到目標，而是能夠最佳的達到目標
>* 會將每個狀態轉換成數值，以觀看達到目標的效能
>Learning Agents<br>
><br>
>能藉由過往經驗學習<br>
>A learning agent has mainly four conceptual components, which are:<br>
>1. Learning element: It is responsible for making improvements by learning from environment<br>
>2. Critic: Learning element takes feedback from critic which describes that how well the agent is doing with respect to a fixed performance standard.<br>
>3. Performance element: It is responsible for selecting external action<br>
>4. Problem generator: This component is responsible for suggesting actions that will lead to new and informative experiences.
-------------------------------------------
## CH3/CH4 Solving Problems by Searching
* Introduction of Problem-solving agent(one kind of goal-based agent)
  A problem can gradually defined by five part
1. Initial state (最初始的狀態)
2. posible action (可能採取動作)
3. description of each action does(transition model -闡述這個action的執行，例如result(initial state,action)= next state )
4. goal test/goal state(目標狀態)
後續以下圖問題作為範例:
<img src='https://i.imgur.com/UMAkwOB.png' width ='600'><br>
Searching Alogorithms
-> searching tree
<img src='https://i.imgur.com/Dqoj66c.png' width ='600'><br>
在樹上的節點N，包含四個結構分別如下:
1. n.state - 當節點的狀態
2. n.parent - n節點的上一層節點狀態
3. n.action - parent 執行甚麼動作達current node
4. n.Path-Cost - denoted by g(n)，path cost between the initial state and current(初始到現在節點的損失)
**Uninformed Search Strategies**
- 策略沒有關於問題定義的額外資訊，因此使用目標導向。
### Beadth-first search(BFS)
 同層節點完全展開，在確定該層節點沒有目標解，才會進入到下一層的節點<br>
> 在假設每層上有b個節點時，展開到第d層所需展開節點數量為
sum(b^n^(n:1->d))，由此可見其時間與空間複雜度為O(b^d^)
### Uniform-cost search
 由最小損失路徑(
min(g(n))為目標，逐次展開節點<br>
> 假設C'為最佳損失(最小)，且每個步驟損失最少為e，則此方法的時間與空間複雜度為O(b^1+(C'/e)^)
### Depth-first search(DFS)
 先鎖定單個節點，並且將其朝向單一方向展開至最深層，若沒有找到目標解，再逐層往回回推<br>
<img src='https://i.imgur.com/LWL26bx.png' width ='600'><br>
> 其時間複雜度為O(b^m^)，當中m為最深深度，因此m可能相較於BFS當中的d要大很多，空間複雜度為O(bm)，因此在設計上可藉由指定深度減少空間以及時間複雜度。
### Iterative deepening DFS
 每次疊代增加深度，但當次疊代的找尋方法同DFS，這樣的好處是，當深度為m，但解答在n層就出現時(n<m)，則可在第n次疊代就藉由DFS的方式找到，而不需要直接搜尋到第m層，能夠有效減少複雜度<br>
<img src='https://i.imgur.com/YQDJzPe.png' width ='600'><br>
>雖然疊代會產生一定的計算量，但與直接利用DFS找尋到m層來說，以疊代的方式找尋到n層還是可以有效減少複雜度，主要是因為在時間複雜度上是以次方方式增長
### bidirection search
 只有兩種選擇方案的搜尋方式，因此並非每種狀況皆可使用。
**Informed (Heuristic) Search Strategies**<br>
 可得知距離初始狀態距離，並且藉由啟發函數推算距離目標距離，並依造評估函數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.
### Greedy best-first search
 展開最接近目標的節點，單純使用heuristic作為預估。<br>
<img src='https://i.imgur.com/EUgLafG.png' width ='600'><br>
<img src='https://i.imgur.com/XUQpSme.png' width ='600'><br>
然而，此方法未必是最佳解。
### A^*^ search
 利用到達現節點的損失函數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')間有關係式:<br>
* <img src='https://i.imgur.com/PeAQGlG.png' style ='width:200px;margin-left:150px'><br>上式當中，c代表由n採取狀態到n'中損失的距離，此式等同於三角不等式(可用向量思考)。
A^*^ search 總範例如下:
<img src='https://i.imgur.com/5F02BLf.png' width ='600'>
<img src='https://i.imgur.com/3RYV7W9.png' width ='600'>
-------------------------------------------
## CH4 Search in Complex Environments
### Local Search
<img src='https://i.imgur.com/AkQvjP3.png' width ='600'>
### Hill Climbing Search
 一種演算法，會重複迴圈並且每圈迴圈不斷增加值(與鄰居點比較，每次接往比現值高的方向前進)，直到找到頂點，然而此種每次接往較高點前進的方法約只能解決14%問題(達到全域最大值)，但若每次前進並非要求增加，而是允許朝同值方向前進，則可能由14%增加至94%。
Hill Climbing Search 又可分為下列幾種:
* Stochastic hill climbing(鄰近點選較優點，該點未必為最佳點)
* First-choice hill climbing (選擇最接近現點的較佳解，該點未必為最佳點)
* Random-restart hill climbing
### Simulated Annealing
 允許出現選擇較差點的選項，但每次選擇較差點的機率會隨疊代下降(T)，而當delta(E)>0，則為較佳解，一定前進，若<0，則為較差解，每次疊代有e^delta(E)/T^的機率選擇。
>每次疊代，溫度(T)會下降，因為不希望再多次疊帶後，還有相同的機率，取到較差的結果點
### Local Beam Search
 每次展開K個點，並且在該K個點內搜尋目標點，若沒有目標點，則會從從中選擇K個最佳選擇器，並依此重複展開K個點
<img src = 'https://i.imgur.com/LEWecBE.png' width ="350">
### Genetic Algorithms
 初始時有N個序列，在依造正確率作排序，於排序後兩兩序列為一組，切分序列並做交互替換(crossover)，產生新的序列，並且依照突變率隨機改變序列內容，以此作為下一次預測模型。
>大原則隨機切分，但是在不同領域跟應用上，可能可以在crossover上給定限制<br>
-------------------------------------------
## ch12 Quantifying Uncertainty
 在描述問題上，若是由果導因可能會需要列出無限種可能性，例如:
>Toothache =>Cavity V GumProblem...
 因此可嘗試由因導果的方式描述問題，例如:
>Cavity => Toothache
 然而在上述的例子內，也並非完全正確，因為未必所有蛀牙皆會造成牙痛的情形，因此由機率表示未失為一個好方法。
 決策理論 = 機率理論+效用理論，在決策理論的核心概念為，**只有當選擇的行為擁有最高的預測效用，且平均超過所有行動的可能結果，才視為agent為合理的**，此原則稱為最大預測效用(MSE => maximum expected utility)
**驗前機率:該機率與其餘機率無關**<br>
**驗後機率:該機率建構於另一機率之上，因此需先算另一機率才可得出該機率**<br>
### 貝氏定理
<img src = 'https://i.imgur.com/v9nLcMG.png' width = '200'><br>
上式代表，當發生b的情況下同時發生a的機率，因此藉由數學運算可得:
<img src = 'https://i.imgur.com/f7KzGVQ.png' width = '200'><br>
 在機率表示內，細體字的P代表單一情況發生的機率，
粗體字的**P**代表所有情況所形成的機率向量，例如:
> **P**(X|Y) =**P**(X=x~i~|Y=y~i~)<br>
代表列出i,j形成的二維向量，當中包含i,j各種情況的機率
**P**(A,B)代表的是結合A,B兩種情況的所有可能性，稱為joint probability distribution。以下以A為天氣，B為蛀牙，天氣內有四種情況而蛀牙有兩種情況作為舉例:<br>
<img src = 'https://i.imgur.com/frqIS9t.png' width = '450'><br>
則其展開式為:<br>
<img src = 'https://i.imgur.com/bu57r6q.png' width = '400'><br>
>註解:在機率表示式內，如果開頭是大寫則是當中的所有可能，小寫則是確定情況，例如Cavity代表的是有蛀牙以及沒蛀牙兩種情況，cavity代表的是只有蛀牙的情況<br>
聯集表示法:
>P(a ∨ b) = P(a) + P(b) − P(a ∧ b)
正常化法->當今天要計算交集機率時，可以使用兩者的joint probability，並使用正常化得出，而不需要得到母體的機率，例如:<br>
<img src = 'https://i.imgur.com/cc3iEMG.png' width = '500'><br>
上式代表今天已知牙痛，且欲求到牙痛且蛀牙的機率，或牙痛沒蛀牙，則可能性分為:<br>
1.牙痛、蛀牙且被探針偵測 <br>
2.牙痛、蛀牙且沒被探針偵測<br>
3.牙痛、沒蛀牙且被探針偵測 <br>
4.牙痛、沒蛀牙且沒被探針偵測<br>
因此可表示兩個1x2矩陣。
### Bayes' Rule
**P**(a^b) =**P**(a|b)**P**(b)，則由此關係是可得到:<br>
>**P**(b|a) = **P**(a|b)**P**(b)/**P**(a)<br>
此關係式及為Bayes' Rule，若以joint probability角度改寫，則為以下:<br>
><img src = 'https://i.imgur.com/aGTQ8RC.png' width = '200'><br>
>This formula shows that we have some occasion to use more general version conditionalized on some background evidence e.（這條公式由chain rule移項而來)
 Bayes' Rule在一般的情況下看似沒用，但其實在應用上有很大的公用，例如今天得知一疾病與伴隨特定症狀的機率，且有該疾病的發生機率，以及該症狀的單獨發生機率，則可利用Bayes' Rule反推出出現該症狀時罹患疾病的機率。
Bayes' Rule應用如下:
><img src = 'https://i.imgur.com/xQhCfXL.png' width = '400'><br>
>上式中的等號左邊代表找尋牙痛且被探針搜尋到的情況下，有蛀牙以及沒蛀牙的個別機率，等號右邊為利用Bayes' Rule尋找交集部分後，再利用normalized將機率兩者形成互補為1。
--------------------------------
## ch13 Probabilistic Reasoning
### Bayesian network(belief network)
#### Bayesian network基礎介紹
Bayesian network是一個有方向性的圖表，每個節點內包含相對應的機率資訊在內，整體的規範如下:<br>
1. 每個節點對應到一個隨機變數(可為連續或離散)
2. 由帶方向性的連結或是箭頭連結兩節點，若由節點X指向節點Y，則稱節點X為節點Y的父代(parent)
3. 每個節點X~i~會辦隨著一個條件機率**P**(X~i~|Parent(X~i~))，作為量化父節點對於對於當下節點的影響。
<img src = 'https://i.imgur.com/PlcrgUU.png' width = '600'><br>
 由上圖作為解說，從圖中我們可看到，在上一章的牙痛關係中，天氣是從當中完全獨立出來，而蛀牙會與牙痛以及是否被探針偵測到有直接關係，然而牙痛與探針偵測卻並無直接關係。<br>
 後續以新的範例作為解說，現在假設有一個警報器當發生竊盜時會鈴響，而有時若是發生地震時也會造成警報器的觸發，且有兩鄰居John&Mary答應會在響鈴時打電話通知，兩者之中John對於鈴聲的敏感度較高，但偶爾會與電話鈴聲搞混，Mary時常播放大聲的音樂，因此時常錯過警鈴的響鈴，依造上述的敘述，我們可得到Bayesian network如下:<br>
<img src = 'https://i.imgur.com/5sVhmwm.png' width = '600'><br>
 在上圖中，沒有父代的節點層稱為驗前機率(prior probabilities)，同時在上圖中，並沒有標示Mary播放大聲音樂的機率，以及John搞混電話與警鈴的機率，這些機率被包含在從Alarm指向兩者的過程中。<br>
 要展示Basyesian network的結構我們會以conditional probability的形式改寫joint probability，並以此逐項展開，此步驟稱為鏈鎖率(chain rule)，如下:<br>
>用conditioanl probability改寫joint probability<br>
><img src = 'https://i.imgur.com/1vHH6oX.png' width = '400'><br>
>展開joint probability<br>
><img src = 'https://i.imgur.com/Zfe7RM4.png' width = '600'><br>
>*注意joint probability的展開很重要* (上面即為chain rule)
 對於X~i~的父代節點，應該直接影響X~i~，範例如下:<br>
<img src = 'https://i.imgur.com/Ow86ZEe.png' width = '600'><br>
 上式中，由figure14.2中我們可看到，地震與盜竊而響鈴並非影響到Mary有沒有打電話的因素，而是影響到是否響鈴，而John是否打電話也無影響到Mary打電話的意願，在所有之中，真正影響到Mary打電話的因素只有警鈴是否有響，因此真正影響Mary的只有他的父節點Alarm，因此可將機率寫為**P**(MaryCalls|Alarm)<br>
#### Bayesian network 的Compactness 以及 node ordering
 Bayesian network的緊湊性(compactness)是局部結構化的，也就是說在bayesian network內元素(節點)只與相鄰的有關，而不與其他元素有關聯，有時並非單純與父輩有關聯，例如發生地震時，John跟Mary可能會因為考慮到是因為地震的原因，而導致警鈴作響而因此不打電話，但這種關聯性過低，若是將此條件也加入Bayesian network內，可能會導致過於複雜，因此加入的利潤過低。<br>
 若是開始時所繪製的順序錯誤，可能會導致網格過於複雜，例如:<br>
<img src = 'https://i.imgur.com/p4VpkGS.png' width = '600'><br>
#### Markov blanket
 再給定一個節點的父輩、子代、子代的另一個父輩之後，則該節點條件獨立於其他所有節點。<br>
<img src = 'https://i.imgur.com/ege03UK.png' width = '600'><br>
#### Bayesian network的離散化
 若是今天的變數為連續變數，而非離散，則可以使用離散化的方式將連續變數轉為離散變數，舉例而言可使用高斯轉換，而當今天變數同時出現連續與離散時，我們稱該種bayesian network為hybrid Bayesian network，例如下圖的cost為連續變數，而buy為離散。
<img src = 'https://i.imgur.com/03HxEAJ.png' width = '600'><br>
 使用pro-bit/logistic/Gaussian轉換後，可將機率表示為下圖<br>
<img src = 'https://i.imgur.com/x40QNVZ.png' width = '600'><br>
#### Enumration
 設定X為query variable，**E**為evidence variables sets，e為特定的observed event，Y為nonevidence,nonquery variables，則完整的Xset 可表示為:X = {X} ∪ E ∪ Y，當一個典型的查詢要求對於後驗概率分佈表示為**P**(X|e)。<br>
 同樣也可將**P**(X|e)藉由正規化的方式表示為:<br>
<img src = 'https://i.imgur.com/eiX9Y1o.png' width = '350'><br>
 而在後驗機率的觀察變數裡面，其實包含著先驗機率在內，因此需先求先驗機率才可得出最終機率。<br>
 由此我們可下總結如下:<br>
>Therefore, a query can be answered using a Bayesian network by computing sums of products of conditional probabilities from the network.<br>
><img src = 'https://i.imgur.com/Z0adcur.png' width = '400'><br>
><img src = 'https://i.imgur.com/UFIkDt3.png' width = '500'><br>
>上圖展示的是b=True的情況，因此要求b=False的情況則用同邏輯展開。
#### Variable Elimination Algorithm
<img src = 'https://i.imgur.com/cGkw6wp.png' width = '700'><br>
可先將f3、f4、f5歸納成一個2x2的矩陣，這邊以警鈴是否有想做歸納，得出:<br>
<img src = 'https://i.imgur.com/p5awt6Z.png' width = '600'><br>
則原式改寫為:<br>
<img src = 'https://i.imgur.com/nfxaCZK.png' width = '350'><br>
再依造地震是否發生做歸納，得出:<br>
<img src = 'https://i.imgur.com/wj5hLWO.png' width = '350'><br>
則原式最終可改寫為:<br>
<img src = 'https://i.imgur.com/qwjFr7Q.png' width = '250'><br>
 Variable Elimination Alogrithm便是依造此種方式，將式子作化簡，將原本複雜的式子改寫為2x2x2的矩陣。<br>
<img src = 'https://i.imgur.com/QY9xQvI.png' width = '600'><br>
 這邊會用到與積分相同觀念，若是今天的變數與加總無關，則可以先移出summation符號之外，與積分時若是變數與積分像無關，可當成常數移出積分符號相同，且此種方法很吃個人對於數學的歸納還有靈敏度，不同的歸納方式還有順序會造成不同的式子。<br>
#### Direct sampling methods(用來估計貝氏網絡)
後續題目以此較複雜的Bayesian Network做範例:<br>
<img src = 'https://i.imgur.com/5exYzAG.png' width = '800'><br>
##### Prior-sample
邏輯為:利用拓樸排序的方式對每個變數做採樣<br>
<img src = 'https://i.imgur.com/0JVnMGQ.png' width = '600'><br>
<img src = 'https://i.imgur.com/INRbpR0.png' width = '700'><br>
In this case, PRIOR-SAMPLE returns the event [true, false, true, true].<br>
 現在假設有一個依造PRIOR-SAMPLE演算法的機率組S~ps~(x~1~,.....,x~2~)，則此機率組可表示為:<br>
<img src = 'https://i.imgur.com/YwsWsvk.png' width = '300'><br>
>because each sampling step depends only on the parent values.
在此以上面的例子作為延伸，若是要表示這邊的[true, false, true, true]，則可寫為:<br>
<img src = 'https://i.imgur.com/Tnvn6l1.png' width = '450'><br>
 當我們大輛採樣N次後，我們期許我們採樣的機率會與sample的機率也就是S~ps~相同，因此在這個例子上我們期許採樣N次內會有32.4%的samples為[true,false,true,true]的情況。也就是:<br>
<img src = 'https://i.imgur.com/nohP0vc.png' width = '450'><br>
##### Rejection sampling
<img src = 'https://i.imgur.com/JcNgjHO.png' width = '600'><br>
 我的理解->會先依造網路依造事前分配產生樣本(samples)，再從這先樣本中拒絕沒有對應到指定證據的樣本(reject the samples that doesn't match the evidence)<br>
<img src = 'https://i.imgur.com/AA3OYwh.png' width = '700'><br>
#### Markov chain simulation -- Gibbs sampling
<img src = 'https://i.imgur.com/xMXkbiy.png' width = '700'><br>
<img src = 'https://i.imgur.com/uuBJQ4g.png' width = '700'><br>
----------
## CH14 Probabilistic Reasoning over Time
### States and Observation
 若以時間作為切分，則在每個時間點，我們可以 **X~t~** 表示為當下的狀態(是否下雨)，並以 **E~t~** 表示為觀察證據(是否有帶著雨傘)，在已知的觀察時間可寫為 **E~t~** = **e~t~**。
<br>
 在此以觀察是否有帶傘作為觀察變數，而以是否有下雨作為狀態，作為下面的範例。
<br>
#### Transition model
 從狀態0:t預估到狀態t+1的改變機率，稱為transition model，在這邊若使用Markov assumption可簡化成one oredr transtion，也就是狀態t+1僅與狀態t有關，可寫為下式子:<br>
> **P**(X~t+1~|X~0:t~) = **P**(X~t+1~|X~t~)<br>
<img src = 'https://i.imgur.com/Jiwh1Yg.png' width = '700'>
在Markov assumption的情況下，為了簡化假設，因此我們會假設stationary process，也就是在每個狀態間的改變機率都是固定的。
#### Sensor model(Observation model)
 在觀察變數 **E~t~** 的情況下，發生情況的機率會與到t的狀態以及到t-1的觀察變數有關連，在此採用Markov assumption，使當下的觀察狀態僅與當下的狀態有關，如下:<br>
> **P**(E~t~|X~0:t~,E~0:t-1~) = **P**(E~t~|X~t~)
 則結合transtion model 以及 sensor model可得下圖:<br>
><img src = 'https://i.imgur.com/hrh8IOP.png' width = '700'>
>在此下雨的狀態間為transtion model，帶傘與下雨的聯繫為sensor model<br>
 則以joint probability展開所有的帶傘與否以及下雨與否的可能性可表示為:<br>
<img src = 'https://i.imgur.com/BgQoRBv.png' width = '350' style = "margin-left:100px"><br>
### Solving Markov Process models
 為了解決Markov process models的問題，發展出下面幾種預估的方式:<br>
* Filter =>給定1:t的觀察值，要預估第t天的狀態，也就是 **P**(X~t~|e~1:t~)
* Predition =>給定1:t的觀察值，要預估第t+k天的狀態，也就是 **P** (X~t+k~|e~1:t~)
* Smoothing => 給定第1:t的觀察值，要預估第k天的狀態，也就是**P** (X~k~|e~1:t~) (在這邊 0<k<t)
* Most likely explatnion =>給定第1:t的觀察值，預估所有1:t天的狀態，也就是 **P**(X~1:t~|e~1:t~)
* Learning => transiton model以及sensor model會隨著觀察而學習的方法。
### Filter and Predition
 在解決fliter問題時，我們希望我們不用每次計算時都要從頭開始算，也就是如果我們要計算第t+1天的結果時，我們可以利用過往的經驗並給予第t+1天的觀察值，預估出第t+1天的狀態，如下:<br>
<img src = 'https://i.imgur.com/eaOQt2R.png' width = '350' style = "margin-left:100px"><br>
 此種方式稱為recursive estimation，在已知的1:t天的觀察後，加上第t+1的觀察值推估第t+1天狀態的這個過程稱為forward，推導如下:<br>
<img src = 'https://i.imgur.com/zILwIkC.png' width = '650' ><br>
 上面的第二步轉換可理解為:先由第1:t天的觀察值預估到第t+1天的狀態，在藉由這個狀態去計算觀察值的機率，做normalization，就可以得知當天的觀察值加上之後當天情況狀態的機率。<br>
 改寫Prediction Model後為:<br>
<img src = 'https://i.imgur.com/DBtptbn.png' width = '650' ><br>
 在上式prediction models的展開可理解為，先藉由第1:t天的觀察值，預估到第t天的狀態，再利用第transition model從第t天的狀態預估到第t+1天的狀態，而在這邊第1:t預估第t天狀態，又可寫為另一個filter方程式展開，由此成為一個recurisive function，可表示為:<br>
<img src = 'https://i.imgur.com/BOcizQh.png' width = '300' style = "margin-left:100px"><br>
### Smoothing
 同樣再利用smoothing解決問題(估算)時，也希望夠利用到recursive 的方式，可以在增加每次觀察的值的時候，一計算特定時間點的狀態，其推導如下:<br>
<img src = 'https://i.imgur.com/VwYWCrh.png' width = '600'><br>
 上面的第三條式子當中，前向為forward recursive，也就是filter，後項為backward recursive，可以理解為，先用forward找到第X~k~的狀態可能性，再結合後面的觀察值，去修正X~k~的狀態可能性，backward的推導如下:<br>
<img src = 'https://i.imgur.com/CTBtUMt.png' width = '600'><br>
 上面的第一條式子可理解為，先用transition model預估X~k+1~的狀態，再以此為基礎去做機率推導，最終再以joint probability展開，得到backward recursive，可表示為:<br>
<img src = 'https://i.imgur.com/bcZq3pi.png' width = '300' style = "margin-left:100px"><br>
### Most likely sequence
<img src = 'https://i.imgur.com/1wUKtAR.png' width = '600'><br>
 藉由已知的觀察值序列，計算可能的狀態序列<br>
<img src = 'https://i.imgur.com/eGstOwE.png' width = '600'><br>
<img src = 'https://i.imgur.com/m04mLxj.png' width = '600'><br>
### HMM (Hidden Markov Model)
 HMM 是一種時間概率模型，其中過程的狀態為由單離散隨機變量描述。
### Kalman Filters
 前述的狀態皆為離散變數，而當今天狀態取點為連續變數時，則需使用Kalman Filter，在使用Kalman Filter時，影響下一個狀態的因素為現在狀態，以及現在狀態的加速度，在這個地方會做一個重要假設，會先將filter假設為Gaussian distribution，以及transition model為gaussian distribution，則prediction 也為gaussian distribution，因為組成如下:<br>
<img src = 'https://i.imgur.com/2flyjR5.png' width = '350'><br>
則由update組成的在t+1時間點的filter也為gaussian distribution，因為其組成如下:<br>
<img src = 'https://i.imgur.com/6mIvfW9.png' width = '350'><br>
即是如果開始的初始狀態也為gaussian distribution，則後續的filter皆為gaussian distribution，在這邊我們以X作為連續狀態變數，Z作為觀察值，則可構成下列方程式:<br>
<img src = 'https://i.imgur.com/8wuL33G.png' width = '700'><br>
而最終式子可以x~0~作為變數，做配方法，得出X~1~的機率為(x~0~項會因為積分而成為1):<br>
<img src = 'https://i.imgur.com/crQ4l2I.png' width = '180'><br>
其分布圖如下:<br>
<img src = 'https://i.imgur.com/eV7VlJN.png' width = '700'><br>
當中:<br>
<img src = 'https://i.imgur.com/ABPD69S.png' width = '400'><br>
<img src = 'https://i.imgur.com/d672sTI.png' width = '700'><br>
 若今天不是單一維度，而是高維的Kalman filter則會表示為:<br>
<img src = 'https://i.imgur.com/ThZ6cpI.png' width = '800'><br>
 當今天並非線性方程式時候，則須改用extend Kalman filter作為model，範例問題如下:<br>
><p style="margine-right:300px"><img src = 'https://i.imgur.com/5rh7BVZ.png' width = '500'></p>
><p ><a style="margine-left:700px">當今天遇到的題目為迴避問題時，則飛行的預測並非線性的，而是會在迴避物的左右兩側較高</a></p>
### Keeping Track of Many Objects
 在觀察值時，我們如果同時觀察複數個點，只會知道在該座標出現點，但是不知道與前一個點的連結關係，如下:<br>
<img src = 'https://i.imgur.com/x7bWEiF.png' width = '500'><br>
用下式展開所有可能性:<br>
<img src = 'https://i.imgur.com/tTI1t7V.png' width = '500'><br>
 在上式當中，最感到困擾的為最後一項 **P**(e^1^~i~,e^2^~i~|X^A^~i~,X^B^~i~)，因為我們無法得知點與觀察值間的關聯性，因此在理論上需要利用w(t)作為相關係數聯繫，將方程式表示為:<br>
<img src = 'https://i.imgur.com/RKrVlCG.png' width = '500'><br>
但可惜的是我們無法正確的找到相關係數，因此理論上無法建構出一個真的好的模型，因此有個替代方案，以距離作為相關性連結。
-----
## 其餘篇筆記
<a href = 'https://hackmd.io/qdvV8JPVRFyThCyvik2YWg?view'>人工智慧導論(修課筆記) (II) </a>
Google Drive
Gist
Clipboard
Sign in with Wallet
