2015年9月13日日曜日

Iteratively Reweighted Least Squares　についてサクッと。

Iteratively Reweighted Least Squares(IRLS)ってたまに出てくるけど、何か分かってなかった.

Least Squares

LSでは線形モデル、
\bf{y} = \bf{\beta}^T \bf{x} + \bf{\epsilon}
というモデルを考えたときにデータとモデルの2乗和誤差を最小にするように\bf{\beta}を決定する。このとき誤差\bf{\epsilon}を1つの定数で書ける(データのばらつきが次元で同じ)ときは擬似逆行列を使って係数\bf{w}を決定することができる。導出はないけど、微分が0になるようにbf{\beta}を決定すれば
\bf{\beta}^{*}= (X^TX)^{-1}X^T \bf{y}

Weighted Least Squares

先程はデータの次元でばらつきが同じとしたけど、次元間の分散が違うことだってある。そんな場合にWLSをつかう。調べた感じWikipediaが一番分かりやすい。
https://en.wikipedia.org/wiki/Linear_least_squares_(mathematics)#Weighted_linear_least_squares
この場合、
\bf{\beta}^* = (X^TWX)^{-1} X^TWy
となる。ただしWは対角成分に分散の逆数を並べた行列。例えば、あるデータ次元についてはほぼ確定的なら始めから分散は小さくできるので、それを反映させることができる。式を見ると、データを標準偏差で割っているのと同じになっているので、データが事前にある場合は標準化(standardization)しとけば同じことになりそうだ。

Iteratively Reweighted Least Squares(IRLS)

上の2つは一発で最適な係数\bf{\beta}^*を求めることができた。これは2乗和誤差が\bf{\beta}の2次で書けるからだ。IRLSでは、2次でない場合でも2次で近似しながら重みWを更新して、最適な係数\bf{\beta}を求めてくれる。これまたWikipediaがわかりやすかった。
https://en.wikipedia.org/wiki/Iteratively_reweighted_least_squares
Lpノルムを最小化したいときは、
\bf{\beta}^{(t+1)} = (X^TW^{(t)}X)^{-1} X^TW^{(t)}y
W^{(t)}は対角行列。W^{(0)}=\bf{1}と初期化しておき、対角成分の各要素は以下のように更新していく。
w_i^{(t)} = | \bf{y}_i - X_i \beta^{(t)}|^{p-2}
IRLSはスパースな係数を選択するためにL1最適化を使う場合に用いられたりするようだ。
コンピュータビジョン最先端ガイド6巻の3章に少しだけIRLSの記述がある。
Scikit-learnなどではOMPが実装されているみたいだが。

​
ラベル: 時刻:

0 件のコメント:

コメントを投稿

登録: コメントの投稿 (Atom)