逐次最小二乗法（RLS）

行列 $A$ と列ベクトル $\overrightarrow{b}$ が与えられたときに，$\|A\overrightarrow{\theta}-\overrightarrow{b}\|_2^2$ を最小にする $\overrightarrow{\theta}$ を求める問題を考えます（最小二乗法）。

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

• 最小二乗法（直線）の簡単な説明
• 最小二乗法の行列表現（単回帰，多変数，多項式）

$A$ は特徴量の値を並べた行列，$\overrightarrow{b}$ は正解ラベル，$\overrightarrow{\theta}$ は推定したい $d$ 次元のパラメータです。

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

$A_n=(\overrightarrow{a}_1,\overrightarrow{a}_2,\dots,\overrightarrow{a}_n)^{\top},\overrightarrow{b}_n=(b_1,b_2,\dots,b_n)^{\top}$

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

方法1：愚直に計算

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

$\overrightarrow{\theta}_{n+1}=(A_{n+1}^{\top}A_{n+1})^{-1}A_{n+1}^{\top}\overrightarrow{b}_{n+1}$

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

方法2：逐次最小二乗法（RLS）

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

$\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)$

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

$P_{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}}$

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

計算量の比較

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

このように「毎回1から全部計算し直す」のではなく「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}$

を，

$\overrightarrow{\theta}_{n}=(A_{n}^{\top}A_{n})^{-1}A_{n}^{\top}\overrightarrow{b}_{n}=P_nA_{n}^{\top}\overrightarrow{b}_{n}$

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

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