スパースモデリング

スパースモデリング（、スパース sparse とは「すかすか」、「少ない」を意味する）または疎性モデリングとは、少ない情報から全体像を復元しようとする科学的モデリング手法である。これは、スパース表現あるいはスパース近似という、連立一次方程式のスパース解を扱う理論に基づいている。スパースモデリング技術は、スパース解を見つけて応用するもので、画像処理、信号処理、機械学習、医用画像処理などで広く利用されている。
概要.
圧縮センシングの一技法で膨大なビッグデータを解析して大量のデータに埋もれて見えにくくなってしまう有為な情報を抽出したり、法則性を導き出したり、断片的なデータを補完して実状に忠実に再現する。地球科学、MRIや天文学を含む多くの分野で高分解能化に使用される。
医用画像に関しての応用は、2002年頃に筑波大学の工藤博幸らのグループによる先駆的研究があり、2007年のカリフォルニア大学バークレー校准教授のMichael Lustigらのグループによる研究を契機として急速に広がった。
用途.
スパースモデリングは、スパース表現（sparse representation）の考え方やアルゴリズムを用いて、信号処理、画像処理、機械学習、医用画像処理、、データマイニングなど、さまざまな分野で広く使用されている。
代表的な用途を次に示す。
このように、スパース性に着想を得たモデルの使用は、幅広い用途で最先端の結果をもたらした。最近の研究では、スパース表現モデリングと深層学習の間には密接な関係があることが示唆されている。
スパース表現.
上述した用途の多くでは、関心がある未知の信号は、特定の「辞書」から得たいくつかの基本要素（「アトム」という）のスパースな（疎な）組み合わせとしてモデル化され、これが問題の正則化として用いられている。これらの問題では通常、所与のデータにモデルを最もよく一致させるために辞書 formula_1 を適合させることを目的とする（スパースコーディングともいう）のメカニズムが伴う。
スパース分解.
ノイズのない観測.
線型方程式系 formula_2 を考える。ここで、formula_1 は formula_4 行列 formula_5 であり、formula_6 である。ここで、行列 formula_1（通常、最大階数と仮定される）は「辞書」と呼ばれ、formula_8 は関心のある信号である。基本的なスパース表現問題は、formula_2 を満たす最もスパースな表現 formula_10 を求めることと定義される。formula_1 の列決定性により、この線形システムは一般的に無限に多くの可能な解が認められ、これらの中から非ゼロの数が最も少ないものを探す。形式的に言えば、 
を解く。ここで formula_13 は formula_14 半ノルムで、formula_10 の非ゼロ成分の数を数える。この問題は、組合せ最適化におけるNP完全な部分集合選択問題への還元を伴うNP困難であることが知られている。
formula_10 のスパース性とは、その中で少数の成分（formula_17）だけが非ゼロであることを意味する。このようなスパース分解（sparse decomposition）を行う潜在的な動機は、formula_8 を formula_1 のできるだけ少ない列（アトムとも呼ばれる）の線形結合として、可能な限り単純に説明したいという欲求にある。このように、信号 formula_8 は、formula_1 から取り出したいくつかの基本要素（アトム）から構成される分子と見なすことができる。
上記の問題は確かにNP困難であるが、近似アルゴリズムを用いてその解を見つけることができる。そのような選択肢の一つは、formula_14 の代わりに formula_23ノルムを用いて問題を凸緩和することで得られる。ここで、formula_24 は formula_10 内の要素の絶対値を単純に合計したものである。これは（basis pursuit、BP）アルゴリズムとして知られており、任意の線型計画法ソルバーを用いて処理することができる。もう一つの近似法は、（matching pursuit、MP）のような貪欲法で、非ゼロの位置を一度に一つずつ見つけてゆくものである。
驚くべきことに、formula_1 に関する穏やかな条件（、または）と、解のスパース性のレベル formula_27 の下で、スパース表現問題は一意の解を持つことが示され、BPとMPはそれを完全に見つけることが保証されている。
ノイズの多い観測.
多くの場合、観測された信号 formula_8 はノイズを含んでいる。等式制約を緩和し、データフィッティング項に ノルムを課すことで、スパース分解問題は、 
あるいはラグランジュ形式で、
となる。ここで、formula_31 は formula_32 を置換する。
ノイズのない場合と同様に、これらの2つの問題は一般にNP困難であるが、追跡アルゴリズムを用いて近似することができる。より具体的には、formula_14 を formula_23ノルムに変更すると、
が得られ、これはとして知られている。同様に、も上記問題の解を近似するために使用することができ、誤差しきい値に達するまで、非ゼロの位置を1つずつ見つけていく。ここでも、BPとMPは、formula_1 の特性と解 formula_27 のカーディナリティに応じて、ほぼ最適な解を導くことが理論的に保証されている。
もう一つの興味深い理論的結果は、formula_1 がユニタリ行列である場合に言及され、この仮定の下では、上述の問題（formula_14 または formula_23 を持つ）は、非線形縮退の形で閉形式解を認める。
バリエーション.
基本的なスパース近似問題にはいくつかのバリエーションがある。
構造化スパース： この問題の元のバージョンでは、辞書に含まれる任意のアトムを選択することができる。構造化（ブロック）スパースモデルでは、個々のアトムを選択する代わりに、アトムのグループを選択する。これらのグループは、互いに重複していたり、大きさが異なる場合がある。その目的は、このブロック構造を強制しながら、スパースになるように formula_8 を表現することである。
協調的（共同）スパースコーディング： この問題の元のバージョンは、単一の信号 formula_8 に対して定義されている。協調的（共同）スパースコーディングモデルでは、信号の集合が利用可能であり、それぞれが formula_1 からの（ほぼ）同じアトムのセットから生成すると考えられている。この場合、追求タスクの目的は、データを最もよく表す一連のスパース表現を、それらが同じ（または近くの）サポートを共有するように強制しながら再現することである。
その他の構造： より広義には、スパース近似問題は、formula_10 の非ゼロ位置のパターンに特定の望ましい構造を強制しながら計算することができる。広く研究されている興味深い2つの事例は、ツリーベースの構造と、より一般的にはボルツマン分布サポートである。
アルゴリズム.
上述のように、スパース表現問題
を解くために開発されたさまざまな近似（追跡（pursuit）ともいう）アルゴリズムがある。
これらの主な手法のいくつかを以下に示す。