System(Under Construction!)

System

「系統」。輸入、輸出、函數所組成的機制。輸入、輸出是多道訊號。

http://www.egr.msu.edu/classes/me851/jchoi/lecture/
http://www.princeton.edu/~stengel/MAE546Seminars.html

http://www.gaussianwaves.com/2014/05/22/

moving average model就是正常的LTI Filter。autoregressive model可以想成LTI Filter的反運算,也是LTI Filter。

乘法摺積對偶性。實際計算採用Fourier Transform。闡述理論則採用Laplace Transform,迎合訊號從零開始。

System Identification

找到適當的函數類型,盡量符合輸入與輸出。

System Realization(Under Construction!)

System Realization

找到函數,盡量符合輸入與輸出。

System Estimation(Under Construction!)

System Estimation

找到函數與輸入,盡量符合輸出。

已知輸出(果),未知輸入(因),尋找最有可能的因。

函數(業)已知是Kalman Filter,未知是Hidden Markov Model。

大家習慣想成是Signal Estimation的進階版本。

System Estimation: Kalman Filter(Under Construction!)

Linear Prediction

預測數列發展。

Kalman Filter

精髓:果的誤差,經過反濾波器,用以修正因。

http://www.cs.unc.edu/~welch/media/pdf/kalman_intro.pdf

狀態(因)   x1 x2 x3 ...            未知 (一條數列,線性遞迴關係)
函數(指標) H1 H2 H3 ...            已知 (數列每一項皆有一個函數)
觀察(果)   y1=H1(x1) y2=H2(x2) ... 已知 (數列每一項皆有一個輸出)

狀態是自遞迴的LTI filter   xn = a1*xn-1 + a2*xn-2 + ... + ap*xn-p
                           xn = A(xn-1, xn-2, ..., xn-p)
狀態可以添加雜訊           xn = a1*xn-1 + a2*xn-2 + ... + ap*xn-p + q
函數通常是同一個           H1 = H2 = H3
函數可以推廣成LTI filter   yn = hn1*xn-1 + hn2*xn-2 + ... + hnp*xn-r
                           yn = Hn(xn, xn-1, xn-2, ..., xn-r)

從 x1 開始一個一個算到 xk,現在要算 xk 是多少:
1. 利用遞迴式計算 xk' = A(xk-1) (此處僅以一階為例。自行初始化 x1 為零。)
   這很直覺吧。
2. 順手求出 yk' = Hk(xk')。
  通常 yk' 不等於正版 yk。這表示我們算的 xk' 不夠準,需要修正。
3. 求出 Hk 的反濾波器 Hk。又稱Kalman gain Kk。
   xk = xk' + Hk(yk - Hk(xk'))。
   yk的誤差,套用反濾波器,變成xk的誤差。原本的xk'加上誤差,答案就對了。
3.1. 為了計算反濾波器,需要 xk 的誤差的平方 pk。 (誤差的autocorrelation)
     利用遞迴式推導出 pk' = A2(pk-1) (自行初始化 p1 為零)
     這個式子的原理,大致上符合 Var[X*a] = Var[X] * a^2。
3.2. 以 pk' Hk 求出 Hk。
4. 修正好 xk 之後,不忘修正 pk = pk' - Hk(Hk(pk'))

為什麼要大費周章,將觀察值的誤差通過反濾波器,而不是直截了當,將觀察值通過反濾波器?我也不清楚。可能是因為添加了雜訊,不得不這樣處理。

System Estimation: Hidden Markov Model(Under Construction!)

Markov Chain

預測數列發展。

Hidden Markov Model

詳見本站文件「Hidden Markov Model」。

一個函數,輸入和輸出都是數列。現在只知道大量的輸出數列(果),完全不清楚函數(業)和輸入數列(因)。

現在假設此函數是一個Hidden Markov Model(即是假設輸入數列是Markov Chain),假設狀態數量為N、機率均等。

針對一個已知的輸出數列,我們調整函數,讓該輸出數列的出現機率最大,同時求出機率多寡。(理論上應該要同時考慮所有輸出數列,讓整體的機率最大;但是這樣時間複雜度太高是指數時間,只好一次處理一個。)

針對一個新的輸出數列,我們找到可能性最高的輸入數列,同時求出機率多寡。

用於Classification

用來分類數列,數列前後項關係密切。

每一種類別,各自建立一個HMM。針對一個新的輸出數列,以機率多寡來判斷其分類。

Conditional Random Field

有向圖改成無向圖。

http://www.zhihu.com/question/35866596

Policy Evaluation

靜態改成動態。

http://www.cs.berkeley.edu/~pabbeel/cs287-fa12/slides/mdps-exact-methods.pdf