はじめに
今回は「スパースモデリング」本に関して、レビューを書きたいと思います。
スパースモデリングを体系的に説明している本は多くなく、
純粋な邦書はこれを含めて数冊程度になります。
また、一般的なスパースモデリングだけでなく、
動的システムへの応用が書かれているのは本書だけだと思います。
この本が難しいと感じられる方は、「入門 パターン認識と機械学習」の
5.1節の主成分分析と、10.1節のリッジ回帰の部分を読むとよいと思います。
本書「スパースモデリング」と関連の深い部分であり、理解の手助けになると思います。
この本は、いわゆるPRML本の要点を整理してまとめたようなもので、
機械学習をはじめる方におすすめしています。
データの近似表現とスパースモデリング
まずは、スパースモデリングの背景について簡単に説明しようと思います。
$d$個のベクトル$x_i$でデータ$y$を表現できると仮定します。
ここで、$w_i$はそのベクトルの大きさを調整する重みとします。
$$
y = w_{1}x_{1} + w_{2}x_{2} + \cdots + w_{d}x_{d}
$$
このときにもし、同じ方向を示す、線形従属なベクトルが含まれているとすると、
$d$個のベクトルより少ない、$z$個のベクトルでデータを表現することができます。
$$
y = w_{1}x_{1} + w_{2}x_{2} + \cdots + w_{z}x_{z}
$$
しかしながら、線形従属を満たすベクトルが存在するという仮定は一般に成り立たないため、
近い方向を示すベクトルが複数あれば、その中から一つ選ぶことを考えます。
そうやって選択したベクトルでデータを表現することにより、データを圧縮できます。
$$
y \approx w_{1}x_{1} + w_{2}x_{2} + \cdots + w_{z}x_{z}
$$
$$
x_i = (x_{i1},x_{i2},\cdots,x_{im})^T
$$
このときに、できるだけ元のデータを正しく表現することができ、
ベクトルの要素$x_{ij}$ができるだけ小さいようなベクトルを選ぶというのが、
スパースモデリングの基本的な考え方になります。
スパースモデリングのメリット
上記のように、ベクトルでデータを近似することには、様々な分野で有益です。
本書の一部を抜粋します。
- データを圧縮できることにより、帯域の狭いネットワークで通信が可能になる
- ノイズに対して過剰適合するような学習を回避することができ、精度を向上できる
- 最小の燃料で、動的システムを目的地まで輸送する制御方法を得ることができる
総評
本書の書評を述べたいと思います。
まず、この本は数学に関して高度な知識がなくても読めるように、
数式の定義に関して丁寧な説明を行っています。
定義の意味を理解できるように数式を噛み砕いて、なぜそのような定義を行ったか説明しています。
また、要点で演習問題が用意されてあり、その解答を付録に載せてあります。
疑問に思うようなところを重点的に絞ってあるため、演習問題で疑問が解消できます。
スパースモデリングの説明に関しては、どういった問題を解こうとしているのか、
愚直に解こうとした際に、どういった問題が生じるのかを例題を交えて説明しています。
スパースモデリングは、厳密解を求めることをやめて、それに近い解を見つける手法です。
そのため、どのような考え方で近似しようとしているかの考え方を押さえること重要で、
そのような点に関して、背景を丁寧に説明してあります。
本書では、スパースモデリングを動的システムに応用する話が書いてあります。
制御分野の基礎知識がなければ読み解くことが難しいのですが、
自分のような他分野の人でも読めるように、基礎知識をまとめてあります。
そして、実際にスパースモデリングを試すことができるソースコードが掲載されています。
本書ではCVXという凸最適化のためのMatlab用のライブラリを用いた解き方が載ってあります。
PythonにもCVXPYという同様のOSSが存在しており、
本書のソースコードを書き直すことで、簡単に実験ができます。
まとめると、必要な基礎知識を押さえたうえで、
スパースモデリングとはなにかについての概念の説明が丁寧に述べられており、
例題を用いた計算機上の実験で仕組みを理解できるようになっています。
加えて、制御系へのスパースモデリングの応用について詳しく説明されてあり、
スパースモデリングに関心を持っている方にはよい書籍だと思います。
公式サイトに、目次が書かれていますので内容を眺めてみて下さい。
「スパースモデリング - 基礎から動的システムへの応用 -（コロナ社）」
各章のレビュー
以降、各章のポイントを書評を交えながら述べようと思います。
一部、厳密さを欠いた説明になっていますが、分かりやすさを重視して書いています。
曲線フィッティングで学ぶスパースモデリング
ここでは、複数の入力と出力の組$(x, y)$が与えられていて、
それを満たすように、多項式で表される曲線をフィッテイングすることを考えます。
その際に直接、逆行列をかけて求める方法が考えられます。
$$
w^* = X^{-1}y
$$
この方法は簡単ですが、データにノイズが含まれる場合は、
過剰にデータに適合しようとして、過学習を起こしてしまいます。
そこで、全ての点を必ず通るという制約を外した、最小二乗法を用いることで、
この問題を起きにくくすることができます。
その際に、正則化項を加えることでより効果が大きくなります。
$$
\arg \min_{w} \ \frac{1}{2} {\parallel}y-wX{\parallel}\ +\ {\parallel}w{\parallel}^{2}_{2}
$$
例として、以下のような高次の多項式で表された曲線を考えます。
$$
\begin{align}
y&=w_{1}x + w_{80} x^{80}\
&= x-x^{80}
\end{align}
$$
このような多くの次数で0となる曲線に上記の手法を用いても、
多くの次数の重み$w_m$で、非零の値を取ります。
そこで、$l^1$ノルムを正則化項として付け加えて最小化する手法があり、
これをLasso（Least Absolute Shrinkage and Selection Operator）と呼びます。
上記のような問題に対しても、Lassoを用いることでスパースな解$w^*$を求めることができます。
$$
\arg \min_{w} \ \frac{1}{2} {\parallel}y-wX{\parallel} +\ {\parallel}w{\parallel}^{2}_{1}
$$
これらはPythonおよび、Matlabの凸最適化のライブラリを使って簡単に試すことができます。
PythonのOSSであるCVXPYのページに分かりやすいコードが載っているので参考にして下さい。
レビュー
この章では、曲線フィッテング問題を用いて、スパースモデリングがなぜ必要なのかを説明しています。
簡単な例で一般的な手法を用いるとどういうことが起きるかが述べてあり、
最適化問題としてどう解くべきかについて述べてあります。
また、Matlabのソースコードが載っており、実際に試すことができます。
凸最適化アルゴリズム
${l}^1$ノルム最小化問題は凸最適化問題であり、求めた解は大域最適解と一致します。
しかしながら、$l^1$ノルムのような関数は微分が不可能なため、勾配法が適用できません。
そこで、近接作用素というものを用いて、同様のことができないかを考えます。
近接作用素とは、微分ができない関数に関して勾配のようなものを計算するもので、
目的関数$f(x)$と、ある点$v$からの距離を示す関数の和を最小化する作用素です。
$$
prox_{f}(v)=\arg \min_x(f(x)+\frac{1}{2\gamma}{\parallel}x-v{\parallel}^2_2)
$$
適当な初期値から近接作用素を適用し続けることで最適解を得ることができます。
これを近接アルゴリズム、あるいは近接勾配法と呼びます。
$$
x_{k+1}=prox_f(x_k)
$$
ここで、目的関数に二つの関数$f_1(x)$と$f_2(x)$が含まれる場合を考えます。
この場合、近接作用素を直接用いることができないため、近接分離法という手法を用います。
例えば、$l^1$ノルム最小化問題であれば、
$l^1$ノルム関数$f_1(x)$と、制約を示す指示関数$f_2(x)$の和となっています。
このそれぞれに対して近接作用素を適用し、繰り返し最適化を行います。
これを特に、ダグラス・ラシュフォードアルゴリズムと呼びます。
しかしながら、関数が複雑で近接作用素を適用するのが難しい場合、近接勾配法が使えません。
その際に、用いられるのがADMM（Alternating Direction Method of Multipliers）です。
これは、目的変数、補助変数、ラグランジュ乗数に対して、２つを固定して、
残り１つを最適化することを交互に繰り返す手法となっています。
レビュー
この章では、勾配法が用いることができない関数に対する最適化について説明をしています。
まずは、要となる近接作用素の定義とその効果を説明し、具体的な関数に適用して挙動を示しています。
そして、これを用いて$l^1$ノルム最小化問題を解く方法が、関数の微分可能性で分けられてあり、
どのような場合に、どの手法を用いればよいかが整理されています。
貪欲アルゴリズム
$l^1$ノルム最小化問題は凸最適化のため、近接作用素の計算ができれば簡単に解けますが、
$l^0$ノルム最小化問題は凸最適化ではないため、組合せ計算が必要で計算量が増大します。
そこで、貪欲法を用いて上記の問題を解く方法について述べてあります。
まずは、データを表現するベクトルの中に、${\parallel}w{\parallel}_0＝1$となる解が存在する場合を考えます。
そうすると、そのベクトルだけでデータを表現することができるため、残差が$0$になります。
この場合、ベクトル数分の評価で、データを表現するベクトルを見つけることができます。
$$
r_i={\parallel}y-wx_{i}{\parallel}=0
$$
しかし、${\parallel}w{\parallel}_0＝2$となると、全部で$d$個あるベクトルから2個のベクトルを選ぶことになり、
組合せ問題となるため、この数が大きいと一般的に有限時間で計算が終わりません。
そこで、貪欲法と呼ばれる手法を用いることで、この問題を解決します。
まずは、マッチング追跡（MP）と呼ばれる手法を述べています。
これはまず、残差$r_i$が小さくなるベクトルを１つ選びます。
次に、そのベクトルでデータを表現した際の残差を計算して、
それを小さくする基底を選びます。
上記の手順を繰り返すことで、目的のベクトルを得る手法です。
しかし、これだと残差$r_i$を小さくするベクトルとして同じものを選ぶ可能性があります。
そこで、既に選ばれたベクトルでデータを表現し直して、
それらの基底では表現できないような、直交する基底を選ぶように改良したのが、
直交マッチング追跡（OMP）というアルゴリズムです。
これは、ベクトルが追加される度に最小二乗法を適用し、
得られた解によって表現されるデータの残差の評価を行います。
そのため、逆行列計算を含み、マッチング追跡と比較すると遅くなります。
このような方法以外に、閾値アルゴリズムという手法があります。
これは、$l^0$ノルム最小化問題に先の近接作用素を適用し、近接勾配法に持ち込むものです。
この手法を、IHT（Iterative Hard Thresholding）と呼びます。
$l^0$ノルムの近接作用素はハード閾値作用素となり、ある閾値以下のl0ノルムの要素を0とする効果を持ちます。
その他に、圧縮サンプリングマッチング追跡（CoSaMP）という、
直交マッチング追跡と組み合わせた手法が紹介されています。
レビュー
ここでは、解くことが難しいとされている$l^0$ノルム最小化問題を解く方法を述べています。
まずは、残差を小さくするという基本的な方法で解くことができないか試し、
その際に問題点となっている部分をどう改良するか述べています。
そして、Matlabのコードで$l^0$ノルム最小化問題を実際に試すことができます。
動的システムと最適制御
スパースモデリングを動的システムに応用することを考えます。
動的システムとは、状態を$x(t)$、制御入力を$u(t)$としたときに、
その微分方程式で表された対象のことを指します。
対象は、自動車や航空機など多岐にわたります。
$$
\dot{x} = Ax(t)+bu(t)
$$
ここでは、この対象が目的地に着くように制御入力$u(t)$を求めることを考えます。
ただし、上記で述べた対象は機械であり、無限の制御入力を発信することはできません。
そこで、制御入力の絶対値は1以下になるように制御するものとします。
$$
{\mid}u(t){\mid}\ {\leq}\ 1
$$
このときに、最短で対象を目的地に移動させる最適制御問題を考えます。
そうすると、入力を制約とする、目的関数の最小化問題として定義できます。
この最適制御解$u(t)^*$は、ポントリャーギンの最小原理を満たすことが知られており、
ハミルトンの正準方程式を満たすという条件より、解を求めることができます。
例として、ロケットの最短制御問題の解法を示しており、その解がバン・バン制御と呼ばれる、
-1から１の切り替えと、1から-1の切り替えで制御できることが示されています。
レビュー
ここでは、スパースモデリングを動的システムに応用することを考え、
動的システムの基礎について説明がされています。
制御について詳しく知らない人でも理解できるように、
具体的な例題を使って、最適制御解を導く方法が示されています。
動的スパースモデリング
動的システムの最適制御解を求める際に、スパースモデリングの概念を導入する方法について述べてあります。
そのために、まず初めに関数に対する$L^p$ノルムの定義を行っています。$l^p$ノルムとは異なるので注意してください。
$$
{\parallel}u_p{\parallel}\ =\ (
\begin{eqnarray}
\int_{0}^{T}{\mid}u(t){\mid}^{p}dt
\end{eqnarray}
)^{\frac{1}{p}}
$$
- $L^0$ノルム：関数$u(t)$が非零である区間の長さ
- $L^1$ノルム：時間軸と関数$u(t)$で挟まれた領域の面積
- $L^2$ノルム：関数$u(t)$自身の内積に対する時間積分の値
$L^0$ノルムを最小化することは、関数が零を取る区間を大きくすることになり、
スパースな制御入力$u(t)$を求めていることになります。
制御では物理的な装置を使って信号を発生させているため、
スパースな信号を用いることは、燃料消費を抑えることに繋がります。
例えば、ハイブリッドカーでは低速時にエンジンを切っています。
ここでは、$L^0$ノルムが非凸性であることから、代わりに$L^1$ノルムに着目して、
その制御入力$u(t)$をスパースにしつつ、対象を目的地にたどり着かせる$L^1$最適制御問題を考えます。
ポントリャーギンの最小原理を用いて最適制御解を求めると不感帯関数$dez(w)$となります。
このとき、$A$が正則であれば、最適制御解はほとんどの時間で0もしくは${\pm}$1の値だけをとります。
このような制御をバン・オフ・バン制御と呼びます。
これを更に、離散値に拡張する方法について述べています。
dez(w) = \left\{
\begin{array}{ll}
-1 & (w \lt -1) \\
0 & (-1 \lt w \lt 1) \\
1 & (1 \lt w)
\end{array}
\right.
これらの最適制御問題は書き換えを行うことで、
今までのスパースモデリングと同様の式で表現できることが分かります。
それぞれの、最適制御問題には対応する名前がついています。
- $L^0$ノルム最小化：スパース最適制御問題
- $L^1$ノルム最小化：最小燃料制御問題
- $L^2$ノルム最小化：最小エネルギー制御問題
レビュー
ここでは、スパースモデリングの概念をどのように動的システムに拡張するか述べてあり、
関数に対するノルムを定義し、それらを最小化する最適制御問題を定義しています。
これにより、動的システムに対してスパースモデリングがいかに有効かを示しています。
また、実際に簡単なロケットの例題で、最適制御解がスパースになることが分かります。
動的スパースモデリングのための数値最適化
ここまでの動的システムは、状態方程式で簡潔に表現できるものを対象としていました。
しかしながら、複雑な動的システムに対して、最適制御解を得るのは簡単ではありません。
この問題に対処するために、近似を行って数値最適化を適用できるようにします。
具体的には、時間に対する離散化と、制御入力$u(t)$に対する量子化を行います。
これにより、状態程式を差分方程式で表すことができます。
これにより、$L^1$最適制御問題を、$l^1$最適化問題に近似でき、
これまで使ってきたADMMなどのアルゴリズムを適用することができます。
レビュー
ここでは、複雑な動的システムに対して近似を行って、
今までのスパースモデリングの手法を適用できる形に変形する方法が示されています。
これにより、動的であるかに関係なく、CVXやCVXPYなどを用いて、
最適制御解を得ることができます。
Matlabのコードが掲載されてあり、実験で確かめることができます。
おわりに
「スパースモデリング」本に関してレビューを行い、そのポイントを説明しました。
ここ最近、機械学習の分野では深層学習が注目を集めています。
特に画像認識の分野では大きな成果を上げ、次々に既存のスコアを塗り替えていっています。
そこでは、明示的に人が特徴量を設計しなくても良いことが利点として挙がっています。
深層学習は端的に言うと、高次元写像によって複雑な特徴量の学習を行っています。
その高次元写像は、パラメータを持つ合成関数を何度も作用させることで実現しています。
各層の関数を$f_l(x)$と表すとすると、分類の機能を持つ最後の全結合層$f_L$以外は、
特徴量を抽出する機能を持った層になっています。
$$
y=f_{L}(f_{L-1}(\cdots(f_{1}(x))))
$$
つまり、深層学習は高次元写像を用いた「特徴抽出器」を実現していることになります。
一方で、スパースモデリングは「特徴選択器」の機能を実現していることになります。
スパースモデリングは特徴ベクトルを組み合わせることで、データを表現しようとしており、
それをどう選ぶかについて、スパース性の指標を用いています。
動的システムに、機械学習の機能を持たせようとしたとき、
リアルタイム性やメモリサイズを考えることが必要になります。
そうすると、学習した特徴量をよりコンパクトに表現することが重要になってきます。
そのため、「特徴抽出器」と「特徴選択器」の双方を考慮して、
機械学習システムを構築することが必須になります。
例えば、深層学習を使って抽出した特徴をよりシンプルにして、
他のモデルを学習させるときなど、スパースモデリングの概念が必要になってきます。
スパース正則化はもちろん、動的な特徴量の選択など、
スパースモデリングが応用できる範囲は広いと考えます。
このような背景のもと、スパースモデリングの知識を深めたいと考える方は読んでみて下さい。