【Python】l0最適化問題に対するマッチング追跡アルゴリズム(スパースモデリング)

マッチング追跡 機械学習

久しぶりの更新になりますが、今回はスパースモデリングの一種であるl0最適化問題に取り組みます。今回やりたいことは、以下の多項式:

$$y=-2t^{30}+5t+3$$

から得られる観測データ\({\bf t}=(t_i)_{i=1\cdots n},{\bf y}=(y_i)_{i=1\cdots n}\)を元に、上の多項式を復元することになります。要は、

多項式

上のオレンジの点データをもとに、青色の線を復元することが目的になります。今回参考にしたのは以下の書籍です。

スパースモデリング 基礎から動的システムへの応用 [ 永原正章 ]

価格:3,240円
(2019/4/21 10:49時点)
感想(0件)

また、ソースはGitHubにあげています。

https://github.com/Daisuke0209/Basic_analysis/blob/master/190422_matching_pursuit.ipynb

【Python】ライブラリのインポート

まずはライブラリをインポートします。

【Python】マッチング追跡関数の定義

マッチング追跡関数と、直交マッチング追跡関数を定義します。詳細は上で紹介した書籍を見てください。

【Python】マッチング追跡関数(MP)

【Python】直交マッチング追跡関数

【Python】パラメータの設定

31

[-2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 3]

背景にある多項式も定義しています。30次の係数が-2、1次の係数が5、定数項が3の多項式を定義しています。

次数 係数
30 -2
1 5
0 3

その多項式から、\(t=0,0.1,\cdots,1\)までの11点をサンプリングし、その観測データから多項式を復元することをマッチング追跡関数を用いて行います。

【Python】マッチング追跡関数の実行

それではアルゴリズムを実行します。まずはマッチング追跡関数から!

【Python】マッチング追跡関数(MP)

残差=0.0865154541

[-2. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. -0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 0. 0. -0. -0. -1. -1. 2. 4. 3.]

アルゴリズムによって推定された多項式の係数は、

次数 係数
30 -2
9 1
4 -1
3 -1
2 2
1 4
0 3

元の多項式をあまり復元できていません。一方で、この多項式を元にサンプリング点の比較をしてみると、

マッチング追跡オレンジがマッチング追跡によって復元された多項式を元にプロットしたものですが、各サンプリング点では元の多項式の点とほぼ一致しています。つまり、ことなる多項式が復元されてしまいましたが、得られた観測点を通るような多項式は他にもあったため、それをマッチング追跡が答えとして出してしまったということにになります。

次に直交マッチング追跡を実行してみます。

【Python】直交マッチング追跡(OMP)

残差=0.0865154541

[-2. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. -0. 0. 0. 0. -0. 5. 3.]

アルゴリズムによって推定された多項式の係数は、以下のようになりました。

次数 係数
30 -2
1 5
0 3

つまり、もともとの多項式を完全再現することに成功しました。

まとめ

今回はマッチング追跡アルゴリズムを用いて多項式の係数推定を行いました。私自身、このアルゴリズムを用いて他にどういうことができるかまだ理解できていないので、もっとも面白いことが出来たらまた紹介します。

また、機械学習を勉強するための参考書を以下で紹介しています!よかったら見ていってください。

機械学習を勉強するためのオススメ参考書(理論・Python・Webアプリ)
統計・機械学習に関しては授業で習ったところありますが、結構忘れてしまっています(。また、Rの演習の授業はありましたが、Pythonは学生のころには使っていません。機械学習・データサイエンスを勉強するにあたり、私が参考にしている参考書を一挙ご紹介したいと思います。

コメント