Markov Chains and Monte Carlo Methods 10日目

Ioana A. Cosma and Ludger Evers, Markov Chains and Monte Carlo Methods
http://users.aims.ac.za/~ioana/notes.pdf
CC-by-nc-sa 2.5
http://creativecommons.org/licenses/by-nc-sa/2.5/za/legalcode

Gibbs samplerが終わったし後は流れで

• Chapter 7. State-space models and the Kalman filter algorithm
  • 7.1 Motivation
  • 7.2 State-space models
    • 7.2.1 Inference problems in SSMs

Chapter 7. State-space models and the Kalman filter algorithm

7.1 Motivation

現実世界では,観測は時間的に離散的な列で行われて,その観測が行われるたびに以前の観測たちから興味有る対象の量($x$)を推測することになる. これをon-line inferenceという. 観測データが$y_1, y_2, ..., y_t, ...$と時刻$t$に沿って与えられて,各時刻で興味有る対象$x_t$を推測することを考える. $x_t$の事前分布$p(x_t)$が$t$によって変化するようなモデルをDynamic Modelという.
Dynamic modelの例には,レーダーによる観測からの飛行機の監視(場所,速度を推測する)やノイズの有る音声データからの発話の認識(発音された単語を推測する) などがある. これらの問題を扱うのに適した方法の一つがSequential Monte Carlo (SMC)である. SMCはiterativeではないMCMCの一種で,$t-1$における$x$の分布をapproximate sampleで表現し,それを$t$における分布の表現で再利用する.

7.2 State-space models

SSMでは,根底となり,観測できないMarkov process(state process) $\{X_t\}$と,観測される過程(observation procss)$\{Y_t\}$からなる.
observation: $y_t = a(x_t, u_t) \sim g(\cdot| x_t, \phi)$
hidden state: $x_t = b(x_{t-1}, v_t) \sim f(\cdot|x_{t-1}, \theta)$
$u,v$はノイズを表す変数で,$\phi, \theta$は既知である. $p(x_1)$が初期状態$x_1$の分布とする. state processは$p(x_t|x_1,...,x_{t-1})=p(x_t|x_{t-1})=f(x_t|x_{t-1},\theta)$だからMarkov chainである. さらに$p(y_t|x_{1:t}, y_{1:t-1})=p(y_t|x_t)=g(y_t|x_t, \phi)$すなわち$y_t$の分布は$x_t$それ以前の観測値と独立である(fig. 7.1).

$x_{1:t}$で$x_1,...,x_t$を表し,$y_{1:t}$も同様である. 簡単のため$\theta$や$\phi$との依存関係の記述を省略して$f(\cdot|x_{t-1}), g(\cdot|x_t)$などと書く.

7.2.1 Inference problems in SSMs

$$\begin{aligned} p(x_{1:t}, y_{1:t}) &= p(x_1)g(y_1|x_1) \prod_{i=2}^t p(x_i,y_i|x_{1:t-1},y_{1:t-1}) \\ &=p(x_1)g(y_1|x_1)\prod_{i=2}^t f(x_i|x_{i-1})g(y_i|x_i) \end{aligned}$$
またBayesの定理から,
$$p(x_{1:t}|y_{1:t}) \propto p(x_{1:t}|y_{1:t-1})g(y_t|x_t) = p(x_{1:t-1}|y_{1:t-1})f(x_t|x_{t-1})g(y_t|x_t)$$
が成立する.
- $p(x_t|y_{1:t})$からのサンプルを取ることをfilgeringという
- $p(x_{1:t}|y_{1:t})$からのサンプルを取ることをsmoothingという
これらについて議論する.

filtering, smoothingはともに$p(x_{1:t}|y_{1:t})$の扱いやすさが問題となる. ほとんどのSSMでは,この分布はnormalizing constantしかわからない.その例外が
- transitionとobservationが離散的である場合(Hidden Markov modelという)には,再帰的なアルゴリズムが使える
- 関数$a, b$が線形であり,ノイズ$u_t, v_t$が正規分布である時(linear Gaussian SSMという),これを解くアルゴリズムをKalman filterという.