Linear Algebra: A Simple Kalman filter (3)

Simple Kalman filter

Kalman filter はこれまでの状態から，次の状態を予測する時に使うことがある．つまり，

x_{new} = x_{old} + f(x_{current}})

のように以前の状態と現在の状態の関数から，新たな状態を予測する．ただ，私はこれに詳しくないのでわかったことだけを述べるに留める．

簡単な Kalman filter では x_{new} を過去の x_i をこれまで述べたような最小二乗法によって可能な限り近い subspace に project して求める手法であるらしい．これに関しては面白い計算がある．これをここで示そう．これは Strang の本で方向性が示されているものを書き下してみたものである．

まずは準備として 1/k を書き換えてみる．

よって，

である．

これまで単なるデータの次の予測値は平均をとるのが，最小二乗法の意味で良いことを示してきた．そこで平均の式を上式を使って書き換えてみる．なぜそうするのかは結果と一緒に説明しよう．

そろそろここで何をしているのかを説明しよう．データが i = 1 から n までとれたとする．しかしこれまでの状態 i = 1 から n-1 までの状態と新しく観測された今の値 x_n だけを使って，つまり，全部のデータを保存しておくのではなく，一つ前と今の状態だけを使って最小二乗法の意味で良い予測をしたい，というのが動機である．状態がかなりある場合，それらを全て覚えておくことは難しいし，次の状態を求める計算が状態を経るにしたがって重くなるのは避けたい．一つ前と今の観測から次を求めたいのである．だから，n と n-1の式にしたのだ．ここで，1/(n-1) Σ_{i=1}^{n-1} x_i が一つ前の状態の平均であることに注意して，これを x_{old} とすると，

なんと，一つ前の状態から次の状態の最小二乗法的な最適な予測ができた．これはすごい．

今回は，最小二乗法を解析学と線形代数の両面から眺めた．これは実は同じであった．そしてその応用の Kalman filter についてちょっと見てみた．

Linear Algebra: A Simple Kalman filter (2)

Linear algebra way

線形代数の方法では一番近い答えは，右辺を左辺の column space にprojection することである．A は column space 内部にしか解を持てないのであるから，b をその空間に投影した結果が最も b に近い．図1に幾何学的な解釈を示しておく．matrix A とb は以下である．


Projection は，ここで A が vector であることを考えると，


微積分の手法と同じ結果になったことに注意すること．つまりこれも平均値である．(Projection になじみが薄い読者は，図1で e が A と直交することに注意すると A^T e=0 より，導くことができるだろう．)


Figure1. Project b to A's column space

私にとって興味あることは，なぜこれらが同じになるかである．二次形式の最小化という calculus の問題と projection という幾何の問題という一見異なるものが同じ結果を導いたのは偶然なのか? もちろん偶然ではない．実はこれらは同じものを求めている．

Projection というのは図1 にみるように b からの最短距離である．距離を求める時，ユークリッド空間では二乗和が出てくる(ピタゴラスの定理)．それを最小化するものである．つまり二次形式の最小化である．計算方法や考え方は違うが，目的は同じであった．

以前も書いたが，私は東野圭吾という作家のファンである．容疑者 X の献身という小説には，異なる手法によってたどりつけない答えがあるということがあり，それに関して数学がたとえとして述べられる．しかし，まったく違う手法でも同じ目的を達しようとすると同じ答えが得られる例がここにある．私は東野圭吾さんの小説においての科学に関する記述は結構良いと思うのだが，これに関しては疑問に思ってしまった．私は，数学で問題を同じように設定した場合，様々な手法が，このように同じ結果にたどりつくことができることに数学の面白さを感じる．いや，実は勉強するにつれて，そういうものが増えてくように感じる．違う考えと思っていたものが，実は更に抽象的な考えから別れてきたものであることに気がつくと驚く．それは山に登ると，地上ではある特定の場所からしか見ることができなかったものが，概観できることに似ている．また，地図を見ることにも似ている．この道，あの道，というふうな風景が実はこの道はこう継がっていたのだ，とわかるようなことが数学の面白さにある．それぞれの道が俯瞰できないと，それは違う所にしか行けないように思うが，まったく継がっていない道というのは，多分ないのではないだろうか．

ここでは，あるベクトルに一番近いベクトルを

- 微積分: 誤差を最小化することで
- 線形代数: 投影することで

求めた．

次回はちょっと Kalman filter の話をしよう．Kalman filter は時々刻々と変化する誤差の入ったデータから，次の未来のデータを可能な限り予測する方法である．基本はこれまでに説明したことと同じであるが，面白い工夫があることを最近知ったので紹介したい．

Linear Algebra: A Simple Kalman filter (1)

Introduction about linear algebra, calculus, and a simple Kalman filter

線形代数と微積分と単純なカルマンフィルタの関係が面白かったのでここにメモを示す．

Problem

単純な観測データ列(x_i)に対して，それぞれが同じ可能性で発生すると考えて最小二乗法を使ってみる．実際，このような簡単な設定ではこれは平均に等しくなる．これは Gilbert Strang の Introduction to Linear Algebra の Chapter4.2 にある．

たとえば，観測データが，[70 80 120]^T の時，それぞれが同じ可能性で発生するならば，

x = 70
x = 80
x = 120

である．これは変な式かもしれない．x が 70 でかつ 80 かつ 120 であるというふうに見えるからだ．ここでは，これらは観測データなので誤差がどこかに入っているために毎回違う値になっているだけで，実は同じものを観測しているというふうに考える．そして観測データから最もそれらしい値を求めようという動機がある．
つまり，

である．残念ながらこのような式を満たす x' はない．しかし，多分測定誤差とかがあるから上手くいかなかったのであろうと考え，もっともありそうな x というのは何かを考える．

Calculus way

まずは微積分の考えを使ってみる．アイデアは観測した結果には誤差があると考え，どんな x であれば誤差が最小になるかということを求めるというものである．これはガウスの最小二乗法の考えである．まずは二乗誤差(E)を計算する．これも Strang の本にある．

E = (x-70)^2 + (x-80)^2 + (x-120)

これは x^2 の式なので，放物線(parabola)である．つまり最小点がどこかに一つある．そのような最小点は微分して傾きが0の点であるから，

となる x をみつけることになる．計算してみると，

よくみるとこれは平均値である．もっともありそうな x は平均というのは私の直感には合うのだが，実はどんな意味でそうなのか，というのはあまり考えたことはなかった．この場合，偏差が比較的小さいのであまり問題にならないが，偏差が大きい場合には直感から外れてしまう．これについては以前 A 6σ Woman という話で書いたことがある．平均は最小二乗法の意味で最適であったのだ．

次は線形代数的な方法を使って最良の x を求めてみよう．