Kalman Filter, Kalman Smoother, and Expectation Maximization

by allenlu2007

 

前文提到 Kalman filter 的好處 (i) 探索 data 的內在結構 (state equation and noise covariance matrix), 以及 (ii) 發展出 recursive equation 來 estimate 內在的結構 (state or sometimes noise).

實際上遇到的困難是 (a) 這樣的 state equation 是否存在? (b) 如果存在如何找到正確的 model 參數? and (c) 如果 model or 參數不準確,Kalman filter estimate 的結果是否 robust?

(a) State equation 是否存在

有兩種解釋: (i) state equation bases on physics  如力學、電子學、etc. (ii) dynamic system 的線性近似。

(b) 如何找到 model 的參數

(i) 由 equation 推導出. (ii) 是由 training 出來的。如果是 (ii) 一般不會差太多。

(c) 如果 model or 參數不準確,Kalman filter estimate 的結果是否 robust?

Again, 可能要用 training 方式來找 Kalman filter 的 Q, R, A, C.  避免 Kalman filter output 和現實差太多。



Kalman filter Training (parameter estimation) 的方式可以用 EM algorithm 或其他 system identification algorithm (ARMA, .. etc.)

Kalman filter is typically used for on-line state estimation and a minimum-variance smoother may be employed for off-line or batch state estimation. However, these minimum-variance solutions require estimates of the state-space model parameters. EM algorithms can be used for solving joint state and parameter estimation problems.

1. 似乎是 Kalman smoother 才可以。Kalman filter 不能?  是因為必須 batch mode?


Step 0: Kalman filter and Kalman smoother 的差異如下:

(a) Kalman filter 主要是”當下”的最佳 estimation.  依照 Markov state 的定義,只要有前一 state 的 pdf/information (mean and covariance matrix; mean 是 x_hat; covariance matrix 是 P), 就可以 ignore 更早的 information.  

(b) Kalman smoother 則是用未來的 observed data 來回推最佳的 estimation.  By the same token, 似乎只要”下一個” sample 就足夠。實則不然,因為需要的是下一 state 的 pdf/information, 並非只是 observed data.  下一 state 的 pdf/information 可以被 estimate 更精確如果知道下下 sample (because they are correlated), 依此類推。當然也可以只看下一個 (或下幾個) sample 來做 Kalman smoother, 稱為 fixed-length or fixed-interval smoothing.  只是所得到的 variance reduction 不是最佳。實務上很少在 real time application 用 Kalman smoother, 主要是 complexity 以及額外的 latency for smoothing.

NewImage

Step 1: Kalman smoother State Estimation:

因此完整的 Kalman smoother 需要所有的 data 來做 post-processing (Viterbi 例外?)

 

NewImage

對 Kalman filter 來說,xt 是一個 Gaussian random variable.  Mean 是 x_hat; covariance matrix 是 P.  P 在 prediction 時增加 (if Q>0),在 update 時減小。

Kalman smoother 多了 backward pass 可以給更好的 estimation, covariance matrix 應該要減小.  此時並非 real time.  理論上 Pt|T < Pt|t (how to prove?)

Find an example to show the difference of Kalman filter and Kalman smoother!

 

 

Step 3: EM algorithm of State Estimation

綜上所述 Kalman smoother 的 state estimation (mean and covariance) 優於 Kalman filter.  Trade-off 是 complexity and latency.  對於 real-time applications 如 tracking, navigation, etc., Kalman filter 比較適合。但若是一些非 real-time 的影像或聲音處理,Kalman smoother 可以多得到一些 performance.  

Kalman smoother 其實還有一個重要的應用,就是配合 EM algorithm, 用來 estimate A, C, Q, R (當然同時 estimate state 的 mean and covariance)! Magic!

因為在實務上,Q and R 大多非 prior information (如何事先知道 state noise and measurement noise 的大小?) 因此可以靠 training (with or without prior state information).  更進一步,有時 A and C 也是 unknown, 也需要由 training 而來。

結合 EM algorithm 和 Kalman smoother 可以做為 training (without prior state information!!) 而得到 A, C, Q, R 的 estimation.  再 performance real-time Kalman filter.   

EM 的 E-step 就是 Kalman smoother.  M-step 就是 update A, C, Q, R based on ML estimation.  EM algorithm 需要解決兩個問題: (i) 如何決定 A, C, Q, R 的 initial guess.  (ii) 如何避免 local minimum.

NewImage


Example: 


 

 

 

 

Advertisements