逐次最小二乗法(RLS)

更新日時 2021/07/04

逐次最小二乗法(Recursive Least Squares, RLS)について,問題設定から以下の更新式の導出まで解説します。

逐次最小二乗法における更新式

θundefinedn+1=θundefinedn+Pn+1aundefinedn+1(bn+1aundefinedn+1θundefinedn)\overrightarrow{\theta}_{n+1}\\=\overrightarrow{\theta}_{n}+P_{n+1}\overrightarrow{a}_{n+1}(b_{n+1}-\overrightarrow{a}_{n+1}^{\top}\overrightarrow{\theta}_n)

Pn+1=PnPnaundefinedn+1aundefinedn+1Pn1+aundefinedn+1Pnaundefinedn+1P_{n+1}=P_n-\dfrac{P_n\overrightarrow{a}_{n+1}\overrightarrow{a}_{n+1}^{\top}P_n}{1+\overrightarrow{a}_{n+1}^{\top}P_n\overrightarrow{a}_{n+1}}

目次
  • 逐次最小二乗法の問題設定

  • 最小二乗パラメータを計算する2つの方法

  • RLS の更新式の導出

逐次最小二乗法の問題設定

行列 AA と列ベクトル bundefined\overrightarrow{b} が与えられたときに,Aθundefinedbundefined22\|A\overrightarrow{\theta}-\overrightarrow{b}\|_2^2 を最小にする θundefined\overrightarrow{\theta} を求める問題を考えます(最小二乗法)。

この問題の重要性は,以下でも紹介しています。

AA は特徴量の値を並べた行列,bundefined\overrightarrow{b} は正解ラベル,θundefined\overrightarrow{\theta} は推定したい dd 次元のパラメータです。

さらに,ここではデータが1つずつ追加されていく状況を考えます。つまり,

An=(aundefined1,aundefined2,,aundefinedn),bundefinedn=(b1,b2,,bn)A_n=(\overrightarrow{a}_1,\overrightarrow{a}_2,\dots,\overrightarrow{a}_n)^{\top},\overrightarrow{b}_n=(b_1,b_2,\dots,b_n)^{\top}

という nn 個のデータがある場合の最小二乗パラメータ θn\theta_n は分かっている状況で,新しいデータ (aundefinedn+1,bn+1)(\overrightarrow{a}_{n+1},b_{n+1}) を追加した場合のパラメータ θn+1\theta_{n+1} の計算方法を考えます。

最小二乗パラメータを計算する2つの方法

方法1:愚直に計算

n+1n+1 個のデータがある場合の最小二乗パラメータを愚直に直接計算すると,

θundefinedn+1=(An+1An+1)1An+1bundefinedn+1\overrightarrow{\theta}_{n+1}=(A_{n+1}^{\top}A_{n+1})^{-1}A_{n+1}^{\top}\overrightarrow{b}_{n+1}

となります。→最小二乗法の行列表現(単回帰,多変数,多項式)

方法2:逐次最小二乗法(RLS)

一方,1つ前の最適パラメータ θundefinedn\overrightarrow{\theta}_n と新しいデータ (aundefinedn+1,bn+1)(\overrightarrow{a}_{n+1},b_{n+1}) から

θundefinedn+1=θundefinedn+Pn+1aundefinedn+1(bn+1aundefinedn+1θundefinedn)\overrightarrow{\theta}_{n+1}=\overrightarrow{\theta}_{n}+P_{n+1}\overrightarrow{a}_{n+1}(b_{n+1}-\overrightarrow{a}_{n+1}^{\top}\overrightarrow{\theta}_n)

という更新式で θundefinedn+1\overrightarrow{\theta}_{n+1} を計算することもできます。ただし,Pn+1P_{n+1} とは (An+1An+1)1(A_{n+1}^{\top}A_{n+1})^{-1} のことで,この d×dd\times d 行列も

Pn+1=PnPnaundefinedn+1aundefinedn+1Pn1+aundefinedn+1Pnaundefinedn+1P_{n+1}=P_n-\dfrac{P_n\overrightarrow{a}_{n+1}\overrightarrow{a}_{n+1}^{\top}P_n}{1+\overrightarrow{a}_{n+1}^{\top}P_n\overrightarrow{a}_{n+1}}

という別の式を使って更新できます。つまり,θn\theta_n だけでなく PnP_n も覚えておく必要があります。

計算量の比較

方法1は,行列積や逆行列の計算を含むので計算に時間がかかりますが,方法2は O(d2)O(d^2) で計算できます。

このように「毎回1から全部計算し直す」のではなく「1つ前の結果をうまく更新して新しい結果を得る」ことで計算時間や使用メモリ量を削減できることがあります(オンラインアルゴリズム,逐次アルゴリズム)。

RLS の更新式の導出

θundefinedn+1=(An+1An+1)1An+1bundefinedn+1=Pn+1An+1bundefinedn+1\overrightarrow{\theta}_{n+1}=(A_{n+1}^{\top}A_{n+1})^{-1}A_{n+1}^{\top}\overrightarrow{b}_{n+1}\\=P_{n+1}A_{n+1}^{\top}\overrightarrow{b}_{n+1}

を,

θundefinedn=(AnAn)1Anbundefinedn=PnAnbundefinedn\overrightarrow{\theta}_{n}=(A_{n}^{\top}A_{n})^{-1}A_{n}^{\top}\overrightarrow{b}_{n}=P_nA_{n}^{\top}\overrightarrow{b}_{n}

を使って表すのが目標です。逆行列の補助定理(Woodburyの恒等式)が登場するのが楽しいです。

導出

AbundefinedA^{\top}\overrightarrow{b} の部分を分解すると,

θundefinedn=Pni=1naundefinedibi\overrightarrow{\theta}_n=P_n\displaystyle\sum_{i=1}^n\overrightarrow{a}_ib_i

となる。よって,

i=1naundefinedibi=Pn1θundefinedn\displaystyle\sum_{i=1}^n\overrightarrow{a}_ib_i=P_n^{-1}\overrightarrow{\theta}_n

よって,

θundefinedn+1=Pn+1i=1n+1aundefinedibi=Pn+1(aundefinedn+1bn+1+i=1naundefinedibi)=Pn+1(aundefinedn+1bn+1+Pn1θundefinedn)\overrightarrow{\theta}_{n+1}=P_{n+1}\displaystyle\sum_{i=1}^{n+1}\overrightarrow{a}_ib_i\\ =P_{n+1}(\overrightarrow{a}_{n+1}b_{n+1}+\displaystyle\sum_{i=1}^n\overrightarrow{a}_ib_i)\\ =P_{n+1}(\overrightarrow{a}_{n+1}b_{n+1}+P_n^{-1}\overrightarrow{\theta}_n)

ここで,

Pn+11=An+1An+1=AnAn+aundefinedn+1aundefinedn+1=Pn1+aundefinedn+1aundefinedn+1P_{n+1}^{-1}=A_{n+1}^{\top}A_{n+1}\\ =A_{n}^{\top}A_n+\overrightarrow{a}_{n+1}\overrightarrow{a}_{n+1}^{\top}\\ =P_n^{-1}+\overrightarrow{a}_{n+1}\overrightarrow{a}_{n+1}^{\top}

という関係式(※)を使って上式の Pn1P_n^{-1} を消去すると,

θundefinedn+1=Pn+1{aundefinedn+1bn+1+(Pn+11aundefinedn+1aundefinedn+1)θundefinedn}=θundefinedn+Pn+1aundefinedn+1(bn+1aundefinedn+1θundefinedn)\overrightarrow{\theta}_{n+1}\\= P_{n+1}\{\overrightarrow{a}_{n+1}b_{n+1}+(P_{n+1}^{-1}-\overrightarrow{a}_{n+1}\overrightarrow{a}_{n+1}^{\top})\overrightarrow{\theta}_n\}\\ =\overrightarrow{\theta}_{n}+P_{n+1}\overrightarrow{a}_{n+1}(b_{n+1}-\overrightarrow{a}_{n+1}^{\top}\overrightarrow{\theta}_n)

となり,θ\theta の更新式を得た。

さらに,PnP_n の更新式を得るために,さきほどの関係式(※)に逆行列の補助定理

(A+BDC)1=A1A1B(D1+CA1B)1CA1(A+BDC)^{-1}\\=A^{-1}-A^{-1}B(D^{-1}+CA^{-1}B)^{-1}CA^{-1}

を使うと,

Pn+1=(Pn1+aundefinedn+1aundefinedn+1)1=PnPnaundefinedn+1(1+aundefinedn+1Pnaundefinedn+1)1aundefinedn+1Pn=PnPnaundefinedn+1aundefinedn+1Pn(1+aundefinedn+1Pnaundefinedn+1)P_{n+1}=(P_n^{-1}+\overrightarrow{a}_{n+1}\overrightarrow{a}_{n+1}^{\top})^{-1}\\ =P_n-P_n\overrightarrow{a}_{n+1}(1+\overrightarrow{a}_{n+1}^{\top}P_n\overrightarrow{a}_{n+1})^{-1}\overrightarrow{a}_{n+1}^{\top}P_n\\ =P_n-\dfrac{P_n\overrightarrow{a}_{n+1}\overrightarrow{a}_{n+1}^{\top}P_n}{(1+\overrightarrow{a}_{n+1}^{\top}P_n\overrightarrow{a}_{n+1})}

なお,AAA^{\top}A に逆行列が存在しない場合のことは考えていません。実際,AAA^{\top}A に逆行列が存在するくらい十分なデータがある状態からRLSを開始すればOKです。または,L2正則化(リッジ回帰)をすれば,AAAA+λIA^{\top}A\to A^{\top}A+\lambda I となり,逆行列は必ず存在します。

全然高校数学ではないですが,逆行列の補助定理の応用例をぜひとも紹介したいので書きました。