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

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

備忘

序列 = 軌跡 = 物理ODE模擬
序列最佳化 = motion planning
函數是 KL distance
算法從 Kalman filter ---> LSTM ---> MDP

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

狀態(因)   x₁ x₂ x₃ ...            未知 (一條數列,線性遞迴關係)
函數(指標) H₁ H₂ H₃ ...            已知 (數列每一項皆有一個函數)
觀察(果)   y₁=H₁(x₁) y₂=H₂(x₂) ... 已知 (數列每一項皆有一個輸出)

狀態是自遞迴的LTI filter   xₙ = a₁xₙ₋₁ + a₂xₙ₋₂ + ... + aₚxₙ₋ₚ
                           xₙ = A(xₙ₋₁, xₙ₋₂, ..., xₙ₋ₚ)
狀態可以添加雜訊           xₙ = a₁xₙ₋₁ + a₂xₙ₋₂ + ... + aₚxₙ₋ₚ + q
函數通常是同一個           H₁ = H₂ = H₃
函數可以推廣成LTI filter   yₙ = hₙ₁xₙ₋₁ + hₙ₂xₙ₋₂ + ... + hₙₚxₙ₋ᵣ
                           yₙ = Hₙ(xn, xₙ₋₁, xₙ₋₂, ..., xₙ₋ᵣ)

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

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

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