スパースモデリング

スパースモデリング英語: Sparse modeling、スパース sparse とは「すかすか」、「少ない」を意味する)または疎性モデリングとは、少ない情報から全体像を復元しようとする科学的モデリング手法である[1]。これは、スパース表現あるいはスパース近似という、連立一次方程式スパース解を扱う理論に基づいている。スパースモデリング技術は、スパース解を見つけて応用するもので、画像処理信号処理機械学習医用画像処理などで広く利用されている。

概要編集

圧縮センシングの一技法で膨大なビッグデータを解析して大量のデータに埋もれて見えにくくなってしまう有為な情報を抽出したり、法則性を導き出したり、断片的なデータを補完して実状に忠実に再現する[2]地球科学MRI天文学を含む多くの分野で高分解能化に使用される[3][4][5][6]

医用画像に関しての応用は、2002年頃に筑波大学の工藤博幸らのグループによる先駆的研究があり、2007年のカリフォルニア大学バークレー校准教授のMichael Lustigらのグループによる研究を契機として急速に広がった[3]

用途編集

スパースモデリングは、スパース表現(sparse representation)の考え方やアルゴリズムを用いて、信号処理画像処理機械学習医用画像処理配列処理英語版データマイニングなど、さまざまな分野で広く使用されている。

代表的な用途を次に示す。

このように、スパース性に着想を得たモデルの使用は、幅広い用途で最先端の結果をもたらした[9][10][11]。最近の研究では、スパース表現モデリングと深層学習の間には密接な関係があることが示唆されている[12]

スパース表現編集

上述した用途の多くでは、関心がある未知の信号は、特定の「辞書」から得たいくつかの基本要素(「アトム」という)のスパースな(疎な)組み合わせとしてモデル化され、これが問題の正則化として用いられている。これらの問題では通常、所与のデータにモデルを最もよく一致させるために辞書   を適合させることを目的とするスパース辞書学習英語版スパースコーディングともいう)のメカニズムが伴う。

スパース分解編集

ノイズのない観測編集

線型方程式系   を考える。ここで、 劣決定英語版   行列   であり、  である。ここで、行列  (通常、最大階数と仮定される)は「辞書」と呼ばれ、  は関心のある信号である。基本的なスパース表現問題は、  を満たす最もスパースな表現   を求めることと定義される。  の列決定性により、この線形システムは一般的に無限に多くの可能な解が認められ、これらの中から非ゼロの数が最も少ないものを探す。形式的に言えば、

 

を解く。ここで    半ノルムで、  の非ゼロ成分の数を数える。この問題は、組合せ最適化におけるNP完全な部分集合選択問題への還元を伴うNP困難であることが知られている。

  のスパース性とは、その中で少数の成分( )だけが非ゼロであることを意味する。このようなスパース分解(sparse decomposition)を行う潜在的な動機は、   のできるだけ少ない列(アトムとも呼ばれる)の線形結合として、可能な限り単純に説明したいという欲求にある。このように、信号   は、  から取り出したいくつかの基本要素(アトム)から構成される分子と見なすことができる。

上記の問題は確かにNP困難であるが、近似アルゴリズムを用いてその解を見つけることができる。そのような選択肢の一つは、  の代わりに  ノルムを用いて問題を凸緩和 (en:英語版することで得られる。ここで、   内の要素の絶対値を単純に合計したものである。これは基底追跡英語版(basis pursuit、BP)アルゴリズムとして知られており、任意の線型計画法ソルバーを用いて処理することができる。もう一つの近似法は、マッチング追跡英語版(matching pursuit、MP)のような貪欲法で、非ゼロの位置を一度に一つずつ見つけてゆくものである。

驚くべきことに、  に関する穏やかな条件(Spark (数学)英語版相互コヒーレンス英語版または制限付等長性英語版)と、解のスパース性のレベル   の下で、スパース表現問題は一意の解を持つことが示され、BPとMPはそれを完全に見つけることが保証されている[13][14][15]

ノイズの多い観測編集

多くの場合、観測された信号   はノイズを含んでいる。等式制約を緩和し、データフィッティング項に  ノルムを課すことで、スパース分解問題は、

 

あるいはラグランジュ形式で、

 

となる。ここで、   を置換する。

ノイズのない場合と同様に、これらの2つの問題は一般にNP困難であるが、追跡アルゴリズムを用いて近似することができる。より具体的には、  ノルムに変更すると、

 

が得られ、これは基底追跡ノイズ除去英語版として知られている。同様に、マッチング追跡英語版も上記問題の解を近似するために使用することができ、誤差しきい値に達するまで、非ゼロの位置を1つずつ見つけていく。ここでも、BPとMPは、  の特性と解  カーディナリティに応じて、ほぼ最適な解を導くことが理論的に保証されている[16][17][18]

もう一つの興味深い理論的結果は、 ユニタリ行列である場合に言及され、この仮定の下では、上述の問題(  または   を持つ)は、非線形縮退の形で閉形式解を認める[16]

バリエーション編集

基本的なスパース近似問題にはいくつかのバリエーションがある。

構造化スパース: この問題の元のバージョンでは、辞書に含まれる任意のアトムを選択することができる。構造化(ブロック)スパースモデルでは、個々のアトムを選択する代わりに、アトムのグループを選択する。これらのグループは、互いに重複していたり、大きさが異なる場合がある。その目的は、このブロック構造を強制しながら、スパースになるように   を表現することである[19]

協調的(共同)スパースコーディング: この問題の元のバージョンは、単一の信号   に対して定義されている。協調的(共同)スパースコーディングモデルでは、信号の集合が利用可能であり、それぞれが   からの(ほぼ)同じアトムのセットから生成すると考えられている。この場合、追求タスクの目的は、データを最もよく表す一連のスパース表現を、それらが同じ(または近くの)サポートを共有するように強制しながら再現することである[20]

その他の構造: より広義には、スパース近似問題は、  の非ゼロ位置のパターンに特定の望ましい構造を強制しながら計算することができる。広く研究されている興味深い2つの事例は、ツリーベースの構造と、より一般的にはボルツマン分布サポートである[21]

アルゴリズム編集

上述のように、スパース表現問題

 

を解くために開発されたさまざまな近似(追跡(pursuit)ともいう)アルゴリズムがある。

これらの主な手法のいくつかを以下に示す。

  • マッチング追跡英語版は、上記の問題を近似的に解くための貪欲反復アルゴリズムである。これは、  内の非ゼロの位置を一度に1つずつ徐々に見つけてゆく方法である。基本的な考え方は、各ステップで、現在の残余(  に初期化)と最も相関のある   の列(アトム)を見つけ、新しいアトムとその係数を考慮に入れて残余を更新することである。マッチング追跡では、同じアトムが複数回選択される場合がある。
  • 直交マッチング追跡は、マッチング追跡と非常によく似ているて、大きな違いが一つある。アルゴリズムの各ステップで、すべての非ゼロ係数が最小二乗法によって更新される。その結果、残余はすでに選択されたアトムと直交しているため、1つのアトムを複数回選択することはできない。
  • 段階的貪欲法: 上記のアルゴリズムに改良を加えたバージョンが、貪欲に動作するアルゴリズムで、2つの重要な機能が追加されている。(i) 一度に非ゼロのグループを追加する機能(ラウンドごとに1つの非ゼロではなく)と、(ii) 各ラウンドでいくつかのアトムをサポートから刈り込むプルーニングステップを含める。このアプローチの代表的なものに、部分空間追跡アルゴリズムとCoSaMPがある[22]
  • 基底追跡英語版法は、  ノルムに置き換えることで、問題の凸緩和版を解く。これは新しい目的を定義するだけであり、望ましい解を得るためにどのようなアルゴリズムを使用するかという問題は残されていることに注意すること。このようなアルゴリズムとして一般的に考えられているのは、IRLS英語版LARS英語版、および反復ソフトシュリンク法である[23]
  • スパース分解問題を解く方法としては、他にも、ホモトピー法、座標降下法英語版、反復ハードしきい値法、上述の反復ソフトシュリンク法に関連する一次近接勾配法英語版、ダンツィヒ・セレクタ(Dantzig selector)がある。

脚注編集

  1. ^ 情報科学の名探偵! 魔法の数式 スパースモデリング”. NHK. 2016年9月19日閲覧。
  2. ^ 福島孝治、大森敏明、藤堂眞治. “物理モデリングとスパースモデリングの融合による自然法則の抽出”. 2016年9月19日閲覧。
  3. ^ a b 大関真之. “スカスカのデータから知見を見出す救世主?--「スパースモデリング」とは何か - (page 4)”. ASAHI INTERACTIVE, Inc.. 2016年9月19日閲覧。
  4. ^ 駒井武、岡本敦、桑谷立、土屋範芳. “スパースモデリングに基づくデータ駆動解析による地球プロセスモデルの構築”. 2016年9月19日閲覧。
  5. ^ 田中利幸、池田思朗、大関真之. “圧縮センシングにもとづくスパースモデリングへのアプローチ”. 2016年9月19日閲覧。
  6. ^ 本間希樹、植村誠、加藤太一、野上大作. “スパースモデリングを用いた超巨大ブラックホールの直接撮像”. 2016年9月19日閲覧。
  7. ^ スパースモデリングを用いた新しい医用MRI画像の創生”. 2016年9月19日閲覧。
  8. ^ 木川隆則、池谷鉄兵、葛西卓磨. “スパースモデリングによるNMR計測・解析の高速高精度化”. 2016年9月19日閲覧。
  9. ^ Baraniuk, R.G. Candes, E. Elad, M. and Ma, Y. (2010). “Applications of sparse representation and compressive sensing”. Proceedings of the IEEE 98 (6): 906–909. doi:10.1109/JPROC.2010.2047424. 
  10. ^ Elad, M. Figueiredo, M.A.T., and Ma, Y. (2010). “On the role of sparse and redundant representations in image processing”. Proceedings of the IEEE 98 (6): 972–982. doi:10.1109/JPROC.2009.2037655. オリジナルの2018-01-17時点におけるアーカイブ。. https://web.archive.org/web/20180117070225/https://pdfs.semanticscholar.org/5393/46f7f35f83875d9e86851010ee35d1a47e69.pdf. 
  11. ^ Plumbley, M.D. Blumensath, T. Daudet, L. Gribonval, R. and Davies, M.E. (2010). “Sparse representations in audio and music: From coding to source separation”. Proceedings of the IEEE 98 (6): 995–1005. doi:10.1109/JPROC.2009.2030345. 
  12. ^ Papyan, V. Romano, Y. and Elad, M. (2017). “Convolutional Neural Networks Analyzed via Convolutional Sparse Coding”. Journal of Machine Learning Research 18 (83): 1–52. arXiv:1607.08194. Bibcode2016arXiv160708194P. http://jmlr.org/papers/volume18/16-505/16-505.pdf. 
  13. ^ Donoho, D.L. and Elad, M. (2003). “Optimally sparse representation in general (nonorthogonal) dictionaries via L1 minimization”. Proceedings of the National Academy of Sciences 100 (5): 2197–2202. Bibcode2003PNAS..100.2197D. doi:10.1073/pnas.0437847100. PMC 153464. PMID 16576749. https://www.cs.technion.ac.il/~elad/publications/journals/2003/15_New_Sparseness_IT.pdf. 
  14. ^ Tropp, J.A. (2004). “Greed is good: Algorithmic results for sparse approximation”. IEEE Transactions on Information Theory 50 (10): 2231–2242. doi:10.1109/TIT.2004.834793. https://authors.library.caltech.edu/9035/1/TROieeetit04a.pdf. 
  15. ^ Donoho, D.L. (2006). “For most large underdetermined systems of linear equations the minimal l1-norm solution is also the sparsest solution”. Communications on Pure and Applied Mathematics 56 (6): 797–829. doi:10.1002/cpa.20132. http://www-stat.stanford.edu/~donoho/Reports/2004/l1l0approx.pdf. 
  16. ^ a b Elad, M. (2010). Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing. Springer. doi:10.1007/978-1-4419-7011-4. ISBN 978-1441970107 
  17. ^ Donoho, D.L., Elad, M. and Templyakov, V. (2006). “Stable recovery of sparse overcomplete representations in the presence of noise”. IEEE Transactions on Information Theory 52 (1): 6–18. doi:10.1109/TIT.2005.860430. https://www.cs.technion.ac.il/~elad/publications/journals/2004/23_Stability_IEEE_TIT.pdf. 
  18. ^ Tropp, J.A. (2006). “Just relax: Convex programming methods for identifying sparse signals in noise”. IEEE Transactions on Information Theory 52 (3): 1030–1051. doi:10.1109/TIT.2005.864420. https://authors.library.caltech.edu/9040/1/TROieeetit06.pdf. 
  19. ^ Eldar, Y.C, Kuppinger, P. and Bolcskei, H. (2009). “Block-sparse signals: Uncertainty relations and efficient recovery”. IEEE Transactions on Signal Processing 58 (6): 3042–3054. arXiv:0906.3173. Bibcode2010ITSP...58.3042E. doi:10.1109/TSP.2010.2044837. 
  20. ^ Tropp, J.A., Gilbert, A.C. and Strauss, M.J. (2006). “Algorithms for simultaneous sparse approximation. Part I: Greedy pursuit”. Signal Processing 86 (3): 572–588. doi:10.1016/j.sigpro.2005.05.030. 
  21. ^ Peleg, T. Eldar, Y.C. and Elad, M. (2012). “Exploiting Statistical Dependencies in Sparse Representations for Signal Recovery”. IEEE Transactions on Signal Processing 60 (5): 2286–2303. arXiv:1010.5734. Bibcode2012ITSP...60.2286P. doi:10.1109/TSP.2012.2188520. 
  22. ^ Needell, D. and Tropp, J.A. (2009). “CoSaMP: Iterative signal recovery from incomplete and inaccurate samples”. Applied and Computational Harmonic Analysis 26 (3): 301–321. arXiv:0803.2392. doi:10.1016/j.acha.2008.07.002. 
  23. ^ Zibulevsky, M. and Elad, M. (2010). “L1-L2 optimization in signal and image processing”. IEEE Signal Processing Magazine 27 (3): 76–88. Bibcode2010ISPM...27...76Z. doi:10.1109/MSP.2010.936023. https://www.cs.technion.ac.il/~elad/publications/journals/2010/L1L2_IEEE_SPM_2010.pdf. 

関連項目編集

参考編集

外部リンク編集