公式の証明はありません(参考文献の1つ目に詳しいのでそちらをご参照ください)。何か問題点がありましたらご指摘いただけますと幸いです。
カルマンフィルタ(のフィルタ操作) | ガウス過程回帰 | |
---|---|---|
知りたいこと | 直接観測できない「状態」が、いまどう分布しているか知りたい。 | 空間内の「目標変数」が、それをまだ観測していないある点でどう分布しているか知りたい。 |
知っていること |
|
|
やること | を計算する(多変量正規分布の積の平方完成)。 → Sherman-Morrison-Woodbury 公式を使用。 |
を のみの関数にする(多変量正規分布で一部変数を固定する形の平方完成)。 → Schur 補行列を使用。 |
補足 | 結局いまの状態の分布は、いまの観測を知らない下でその状態である確率と、その状態からいまの観測が得られる確率の積に比例する。 | 未知の点における目標変数の分布は、すでに知っている点とのカーネル関数にしばられている(目標変数 は であり、 であり、という仮定をおいている。そのため、何も知らない下で、 は行列の各成分が となる共分散行列をもつ多変量正規分布にしたがう)。 |
互いに相手っぽく解くには | を のみの関数にする(同時分布を出すのは面倒。もっとも、普通に解くのも面倒)。 | を計算する(原理上はこうだがやっていないからわからない。というか は結局 において を固定することになりそうなので、最初から の方を固定しろという話にはなる)。 |
結論 | 素直に解いた方がいいと思います。 |
- Schur 補行列とは、「ある行列に対して、その行列の逆行列の左上(または右下)のブロックをとって、その逆行列を取ったもの」。「ある行列に対して、その行列の逆行列の左上(または右下)のブロックをとって、その逆行列を取ったものがほしい」というときにつかう。どういうときにそうなるかというと、「多変量正規分布にしたがう確率ベクトルのうち一部の変数たちを固定して、その条件下で残りの変数たちがしたがう多変量正規分布の分散共分散行列を知りたい」というとき。
- Sherman-Morrison-Woodbury の公式とは、適当なサイズの4つの行列に対して成り立つ恒等式であって、どんなときに役立つかというと、行列の逐次更新式の形が「時刻 の行列の逆行列に他の行列を足してから逆行列をとったもの」のようになっているときに、この公式で書き換えた方が計算量的に有利になることがある(逆行列側で更新しろという形だが、諸事情で逆行列側だけでは手順が進められないとき)。別に Sherman-Morrison-Woodbury の公式がないと死ぬわけではない。ただ計算量というのは馬鹿にできないので、やっぱりないと死ぬかもしれない。Schur 補行列との関係は、この公式自体が Schur 補行列による逆行列のブロック表示からきれいに導かれるのと、だから逐次更新したい行列が Schur 補行列の逆行列型になっていたらこの恒等式で書き換えできる。書き換えるとやはり Schur 補行列の形をしている。
- カルマンフィルタでは、状態ベクトルの分布を、時刻ごとに得られる観測ベクトルにしたがって更新していくが、このうちフィルタ操作(一期先予測分布からフィルタ分布への更新)では、フィルタ後分散共分散行列が Schur 補行列の逆行列型になる。なので、Sherman-Morrison-Woodbury の公式で書き換えて計算量を減らすことが多い(状態ベクトルの次元数よりも、観測ベクトルの次元数の方が小さいときにはこれが有効で、実際カルマンフィルタの適用場面ではそのようなシチュエーションが多い)。フィルタ操作に Schur 補行列をつかうわけではない。
- ただし、カルマンフィルタにおいて、状態ベクトルと観測ベクトルを連結したベクトルを考えれば、フィルタ操作を「多変量正規分布を一部の変数で条件付けたい」ととらえることはできる。このようにとらえるなら、フィルタ操作に Schur 補行列をつかうことになる。あまりこうとらえないとは思う。このやり方で解くとフィルタ後分散共分散行列が直接 Schur 補行列型になる(つまり、逆行列の形で出てくるのではなく、直接 Sherman-Morrison-Woodbury の公式で書き換えた後の形が出てくる)。
- ガウス過程回帰(PRML下巻 6.4.2 節の)では、目標変数 が観測された下で のしたがう分布を知りたいが、これは のしたがう事前分布のうち を固定することで達成される。つまり Schur 補行列をつかう。
え? あ、うん。「そっか、成り立つんだ」って感じなんだけど。なんかうれしいのそれ? あと公式の名前なっが!
の逆行列が知りたいときに有用です。右辺 の方を求めればよいということなので。
ごめん、いうほど「 の逆行列が知りたいなー」ってなる? なったとして「右辺の方を求めればいいんだよかったー」ってなる?
例えばカルマンフィルタの問題設定(システム・観測は線形、システムノイズ・観測ノイズ・状態の事前分布はガウシアン)の下では、時刻 におけるフィルタ分布はベイズの定理より以下のようにかけます(各文字の意味は別の記事を参照してください)。
ここで とおいた部分の、 に依存する項( のしたがう分布を知りたいので)は以下のようになります。これは の二次形式になので、フィルタ分布もガウシアンであり、2次の項 にあらわれる こそが求めたいフィルタ後分散共分散行列 の逆行列に他なりません。上式は の形に平方完成できますから(係数比較より となります。 に依存しない定数項の足し引きは の分布の形を変えません)。「 の逆行列が知りたい(それが求めたい分散共分散行列 だから)」となったわけです。そしてそれは Sherman-Morrison-Woodbury の公式より です。これより、以下の有名なカルマンフィルタのフィルタ分布(の分散共分散行列と平均ベクトル)が導かれます。これらは とおくともう少しすっきりかけますね。何も逆行列補題を適用せずとも分散共分散行列と平均ベクトルを逐次式としてかくことはできます。ただ、逆行列補題を適用しない場合、毎回のフィルタリングで という逆行列を求めなければなりません。この行列は縦幅も横幅も状態変数の次元数ですが、状態の次元が大きいと大きな行列になりえます。他方、逆行列補題を適用すると で、このインバースの中に入っている行列のサイズは縦幅も横幅も観測変数の次元数です(カルマンフィルタの状況では の逆行列が既に求まっているので逆行列を求める必要があるのはこのインバースの中身だけになるわけです)。一般にカルマンフィルタの適用場面では「状態変数の次元数 >> 観測変数の次元数」となることが多いので逆行列補題を適用した方が計算コストが小さくなるんです。状態変数の分散共分散を更新したいだけであれば分散共分散行列の逆行列(精度行列)の方を更新していけば逆行列をとる操作を回避することができそうですが、平均ベクトルの更新では平方完成をするために「精度行列の逆行列」が出てきてしまうので。え? あー確かに、全体で の大きさの行列になるな。それが?
もう数式打つの疲れてるなこれ。それで が多変量正規分布にしたがったら何なの?
モーメント母関数の計算から、 のしたがう多変量正規分布は以下になることがわかります。
- 元々 の分散共分散行列が であったはずなのになぜ にならないのか疑問に思う方もいるかもしれません。 は を知らない下での の分散共分散行列です。 を知ってしまうと分散共分散行列は変わってきます。斜めに傾いた(独立でない)2変量正規分布を思い浮かべて、それの横軸を 、縦軸を と考えてみてください(この記事のグラフの真ん中のようなイメージです)。もし について何も知らないなら、 の分布はこの2変量正規分布を 方向に積分することになります(先ほどの記事の Histgram of x)。しかし、ある を手に入れてしまった場合は、その値に引いた水平線で2変量正規分布を切った断面になります。グラフの上の方の値なのか、下の方の値なのかで の広がりは異なりますよね。 を観測したもとでの の分布を得るには、「2変量正規分布からの切り出し」が必要なんです。
- 後で気付いたんですが、PRML 下巻20ページの図 6.7 に の分布を で固定したときの の分布を示すイラストがありますね。
確かに逆行列だから単純に左上のブロックを取るわけにはいかないな。って、あれ? を観測した下での の分布って、それフィルタ後分布じゃん。じゃあフィルタ後分散共分散行列はさっき上で求めたこれだろ?
さすがにばれてしまいましたか。その を の部分行列 に関するシューア補行列(Schur complement matrix)といいます。 でかくと ですね。
へ? シュ、シューア補行列? 何それ? 確かに の式と を見比べると になってるけど。
シューア補行列とは「ある行列に対して、その行列の逆行列の左上のブロックをとって、その逆行列を取ったもの」ですよ(あるいは右下のブロックでもよく、その場合は に関するシューア補行列 となる)。上の多変量正規分布からの切り出しは、「一部の変数を固定した残りの変数のみの分散共分散行列を知りたいので、もとの分散共分散行列の逆行列をとって、その左上のブロックをとって、それの逆行列をとって分散共分散行列に戻したい」ということなので、これはシューア補行列そのものです。ちなみにシューア補行列を用いた逆行列のブロック表示からの Sherman-Morrison-Woodbury の公式の証明が参考文献にあるので参照してください。
ふーん? でもさっきカルマンフィルタを解いたときにシューア補行列なんて出てきた? 出てきたのは Sherman-Morrison-Woodbury の公式じゃなかった?
そうなんですよね。こちらの解き方ではシューア補行列は出てきますが Sherman-Morrison-Woodbury の公式は出てきません。プロデューサーさんは Sherman-Morrison-Woodbury の公式は、カルマンフィルタの場合に限らず「多変量式分布の一部の変数を固定する場合」に適用できるのではないかと考えて、カルマンフィルタをそのようにとらえたかったようなんですが、そもそもこうやって解く場合は逆行列が出てこなかったんですよね。
駄目じゃん!
じゃあ、代わりに出てきたシューア補行列っていうのは?