「スパースモデリング」の版間の差分
削除された内容 追加された内容
m →文献 |
4th protocol (会話 | 投稿記録) 編集の要約なし タグ: Refタグつき記述の除去 2017年版ソースエディター |
||
| (他の1人の利用者による、間の2版が非表示) | |||
1行目:
'''スパースモデリング'''（{{lang-en|Sparse modeling}}、スパース [[wikt:sparse|sparse]] とは「すかすか」、「少ない」を意味する）または'''疎性モデリング'''とは、少ない情報から全体像を
== 概要 ==
[[圧縮センシング]]の一技法で膨大な[[ビッグデータ]]を解析して大量のデータに埋もれて見えにくくなってしまう有為な情報を抽出したり、法則性を導き出したり、断片的なデータを補完して実状に忠実に再現する<ref>{{Cite web|url=http://sparse-modeling.jp/program/B01-3.html|title=物理モデリングとスパースモデリングの融合による自然法則の抽出|accessdate=2016-9-19|author=福島孝治、大森敏明、藤堂眞治|publisher=}}</ref>。[[地球科学]]、[[MRI]]や[[天文学]]を含む多くの分野で高[[分解能]]化に使用される<ref name="zdnet">{{Cite web|url=http://japan.zdnet.com/article/35074052/4/|title=スカスカのデータから知見を見出す救世主？--「スパースモデリング」とは何か - (page 4)|accessdate=2016-9-19|author=大関真之|publisher=ASAHI INTERACTIVE, Inc.}}</ref><ref>{{Cite web|url=http://sparse-modeling.jp/program/A02-1.html|title=スパースモデリングに基づくデータ駆動解析による地球プロセスモデルの構築|accessdate=2016-9-19|author=駒井武、岡本敦、桑谷立、土屋範芳|publisher=}}</ref><ref>{{Cite web|url=http://sparse-modeling.jp/program/B01-1.html|title=圧縮センシングにもとづくスパースモデリングへのアプローチ|accessdate=2016-9-19|author=田中利幸、池田思朗、大関真之|publisher=}}</ref><ref>{{Cite web|url=http://sparse-modeling.jp/program/A02-3.html|title=スパースモデリングを用いた超巨大ブラックホールの直接撮像|accessdate=2016-9-19|author=本間希樹、植村誠、加藤太一、野上大作|publisher=}}</ref>。
[[医用画像]]に関しての応用は、2002年頃に[[筑波大学]]の工藤博幸らのグループによる先駆的研究があり、2007年の[[カリフォルニア大学バークレー校]]准教授のMichael Lustigらのグループによる研究を契機として急速に広がった<ref name="zdnet" />。
== 用途 ==
スパースモデリングは、スパース表現（sparse representation）の考え方やアルゴリズムを用いて、[[信号処理]]、[[画像処理]]、[[機械学習]]、[[医用画像処理]]、{{仮リンク|配列処理|en|Array processing}}、[[データマイニング]]など、さまざまな分野で広く使用されている。
代表的な用途を次に示す。
* [[医用画像]] - [[MRI]]や[[X線CT]]での解像度の向上<ref>{{Cite web|url=http://sparse-modeling.jp/program/A01-1.html|title=スパースモデリングを用いた新しい医用MRI画像の創生|accessdate=2016-9-19|publisher=}}</ref>
* [[地球科学]] - 地下構造の推定
* [[天文学]] - 解像度の向上
* [[生命科学]] - [[核磁気共鳴分光法]]での計測、データ解析、立体構造計算の高速・高精度化<ref>{{Cite web|url=http://sparse-modeling.jp/program/A01-2.html|title=スパースモデリングによるNMR計測・解析の高速高精度化|accessdate=2016-9-19|author=木川隆則、池谷鉄兵、葛西卓磨|publisher=}}</ref>
このように、スパース性に着想を得たモデルの使用は、幅広い用途で最先端の結果をもたらした<ref name="survey1">{{cite journal|author=Baraniuk, R.G. Candes, E. Elad, M. and Ma, Y.|year=2010|title=Applications of sparse representation and compressive sensing|journal=Proceedings of the IEEE|volume=98|number=6|pages=906–909|doi=10.1109/JPROC.2010.2047424}}</ref><ref name="survey2">{{cite journal|author=Elad, M. Figueiredo, M.A.T., and Ma, Y.|year=2010|title=On the role of sparse and redundant representations in image processing|url=https://pdfs.semanticscholar.org/5393/46f7f35f83875d9e86851010ee35d1a47e69.pdf|journal=Proceedings of the IEEE|volume=98|number=6|pages=972–982|doi=10.1109/JPROC.2009.2037655|archiveurl=https://web.archive.org/web/20180117070225/https://pdfs.semanticscholar.org/5393/46f7f35f83875d9e86851010ee35d1a47e69.pdf|url-status=dead|archivedate=2018-01-17|citeseerx=10.1.1.160.465|s2cid=10992685}}</ref><ref name="survey3">{{cite journal|author=Plumbley, M.D. Blumensath, T. Daudet, L. Gribonval, R. and Davies, M.E.|year=2010|title=Sparse representations in audio and music: From coding to source separation|journal=Proceedings of the IEEE|volume=98|number=6|pages=995–1005|doi=10.1109/JPROC.2009.2030345|citeseerx=10.1.1.160.1607|s2cid=4461063}}</ref>。最近の研究では、スパース表現モデリングと[[深層学習]]の間には密接な関係があることが示唆されている<ref name="deeplearning">{{cite journal|author=Papyan, V. Romano, Y. and Elad, M.|year=2017|title=Convolutional Neural Networks Analyzed via Convolutional Sparse Coding|url=http://jmlr.org/papers/volume18/16-505/16-505.pdf|journal=Journal of Machine Learning Research|volume=18|number=83|pages=1–52|arxiv=1607.08194|bibcode=2016arXiv160708194P}}</ref>。
==
上述した用途の多くでは、関心がある未知の信号は、特定の「辞書」から得たいくつかの基本要素（「アトム」という）のスパースな（疎な）組み合わせとしてモデル化され、これが問題の[[正則化]]として用いられている。これらの問題では通常、所与のデータにモデルを最もよく一致させるために辞書 <math>D</math> を適合させることを目的とする{{仮リンク|スパース辞書学習|en|Sparse dictionary learning}}（[[スパースコーディング]]ともいう）のメカニズムが伴う。
=== スパース分解 ===
==== ノイズのない観測 ====
[[線型方程式系]] <math>x = D\alpha</math> を考える。ここで、<math>D</math> は{{仮リンク|劣決定系|en|Underdetermined system|label=劣決定}} <math>m\times p</math> [[行列 (数学)|行列]] <math>(m < p)</math> であり、<math>x \in \mathbb{R}^m,\alpha \in \mathbb{R}^p</math> である。ここで、行列 <math>D</math>（通常、[[行列の階数|最大階数]]と仮定される）は「辞書」と呼ばれ、<math>x</math> は関心のある信号である。基本的なスパース表現問題は、<math>x = D\alpha</math> を満たす最もスパースな表現 <math>\alpha</math> を求めることと定義される。<math>D</math> の列決定性により、この線形システムは一般的に無限に多くの可能な解が認められ、これらの中から非ゼロの数が最も少ないものを探す。形式的に言えば、
:<math>
\min_{\alpha \in \mathbb{R}^p} \|\alpha\|_0 \text{ subject to } x = D\alpha
</math>
を解く。ここで <math>\|\alpha\|_0 = \#\{ i : \alpha_i \neq 0, \, i=1,\ldots,p \}</math> は <math>\ell_0</math> [[半ノルム]]で、<math>\alpha</math> の非ゼロ成分の数を数える。この問題は、[[組合せ最適化]]における[[NP完全問題|NP完全]]な部分集合選択問題への還元を伴う[[NP困難]]であることが知られている。
<math>\alpha</math> のスパース性とは、その中で少数の成分（<math>k \ll m < p</math>）だけが非ゼロであることを意味する。このような'''スパース分解'''（sparse decomposition）を行う潜在的な動機は、<math>x</math> を <math>D</math> のできるだけ少ない列（[[原子|アトム]]とも呼ばれる）の線形結合として、可能な限り単純に説明したいという欲求にある。このように、信号 <math>x</math> は、<math>D</math> から取り出したいくつかの基本要素（アトム）から構成される[[分子]]と見なすことができる。
上記の問題は確かにNP困難であるが、近似アルゴリズムを用いてその解を見つけることができる。そのような選択肢の一つは、<math>\ell_0</math> の代わりに <math>\ell_1</math>ノルムを用いて問題を[[凸最適化|凸緩和]]{{Enlink|Relaxation (approximation)|英語版|en}}することで得られる。ここで、<math>\|\alpha\|_1</math> は <math>\alpha</math> 内の要素の絶対値を単純に合計したものである。これは{{仮リンク|基底追跡|en|Basis pursuit}}（basis pursuit、BP）アルゴリズムとして知られており、任意の[[線型計画法]]ソルバーを用いて処理することができる。もう一つの近似法は、{{仮リンク|マッチング追跡|en|Matching pursuit}}（matching pursuit、MP）のような[[貪欲法]]で、非ゼロの位置を一度に一つずつ見つけてゆくものである。
驚くべきことに、<math>D</math> に関する穏やかな条件（{{仮リンク|Spark (数学)|en|Spark (mathematics)}}、{{仮リンク|相互コヒーレンス (線形代数)|en|Mutual coherence (linear algebra)|label=相互コヒーレンス}}または{{仮リンク|制限付等長性|en|Restricted isometry property}}）と、解のスパース性のレベル <math>k</math> の下で、スパース表現問題は一意の解を持つことが示され、BPとMPはそれを完全に見つけることが保証されている<ref name="donohoelad2003">{{cite journal
| author = Donoho, D.L. and Elad, M.
| year = 2003
| title = Optimally sparse representation in general (nonorthogonal) dictionaries via L1 minimization
| journal = Proceedings of the National Academy of Sciences
| volume = 100
| issue = 5
| pages = 2197–2202
| url = https://www.cs.technion.ac.il/~elad/publications/journals/2003/15_New_Sparseness_IT.pdf
| doi = 10.1073/pnas.0437847100
| pmid = 16576749
| pmc = 153464
| bibcode = 2003PNAS..100.2197D
| doi-access = free
}}</ref><ref name="Tropp2004">{{cite journal
| author = Tropp, J.A.
| year = 2004
| title = Greed is good: Algorithmic results for sparse approximation
| journal = IEEE Transactions on Information Theory
| volume = 50
| number = 10
| pages = 2231–2242
| url = https://authors.library.caltech.edu/9035/1/TROieeetit04a.pdf
| doi = 10.1109/TIT.2004.834793
| citeseerx = 10.1.1.321.1443
| s2cid = 675692
}}</ref><ref name="donoho2006most">{{cite journal
| author = Donoho, D.L.
| year = 2006
| title = For most large underdetermined systems of linear equations the minimal l1-norm solution is also the sparsest solution
| journal = Communications on Pure and Applied Mathematics
| volume = 56
| number = 6
| pages = 797–829
| url = http://www-stat.stanford.edu/~donoho/Reports/2004/l1l0approx.pdf
| doi = 10.1002/cpa.20132
}}</ref>。
==== ノイズの多い観測 ====
多くの場合、観測された信号 <math>x</math> はノイズを含んでいる。等式制約を緩和し、データフィッティング項に [[:en:L2 norm#Euclidean norm|<math>\ell_2</math>]]ノルムを課すことで、スパース分解問題は、
:<math>
\min_{\alpha \in \mathbb{R}^p} \|\alpha\|_0 \text{ subject to } \|x - D\alpha \|_2^2 \le \epsilon^2
</math>
あるいはラグランジュ形式で、
:<math>
\min_{\alpha \in \mathbb{R}^p} \lambda \|\alpha\|_0 + \frac{1}{2}\|x - D\alpha \|_2^2
</math>
となる。ここで、<math>\lambda</math> は <math>\epsilon</math> を置換する。
ノイズのない場合と同様に、これらの2つの問題は一般にNP困難であるが、追跡アルゴリズムを用いて近似することができる。より具体的には、<math>\ell_0</math> を <math>\ell_1</math>ノルムに変更すると、
:<math>
\min_{\alpha \in \mathbb{R}^p} \lambda \|\alpha\|_1 + \frac{1}{2} \|x - D\alpha \|_2^2
</math>
が得られ、これは{{仮リンク|基底追跡ノイズ除去|en|Basis pursuit denoising}}として知られている。同様に、{{仮リンク|マッチング追跡|en|Matching pursuit}}も上記問題の解を近似するために使用することができ、誤差しきい値に達するまで、非ゼロの位置を1つずつ見つけていく。ここでも、BPとMPは、<math>D</math> の特性と解 <math>k</math> の[[濃度 (数学)|カーディナリティ]]に応じて、ほぼ最適な解を導くことが理論的に保証されている<ref name="Elad2010">{{cite book
| author = Elad, M.
| year = 2010
| publisher = Springer
| title = Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing
| doi = 10.1007/978-1-4419-7011-4
| isbn = 978-1441970107
| citeseerx = 10.1.1.331.8963
}}</ref><ref name="DonohoEladTem2006">{{cite journal
| author = Donoho, D.L., Elad, M. and Templyakov, V.
| year = 2006
| title = Stable recovery of sparse overcomplete representations in the presence of noise
| journal = IEEE Transactions on Information Theory
| volume = 52
| number = 1
| pages = 6–18
| url = https://www.cs.technion.ac.il/~elad/publications/journals/2004/23_Stability_IEEE_TIT.pdf
| doi = 10.1109/TIT.2005.860430
| citeseerx = 10.1.1.125.5610
| s2cid = 14813938
}}</ref><ref name="Tropp2006">{{cite journal
| author = Tropp, J.A.
| year = 2006
| title = Just relax: Convex programming methods for identifying sparse signals in noise
| journal = IEEE Transactions on Information Theory
| volume = 52
| number = 3
| pages = 1030–1051
| url = https://authors.library.caltech.edu/9040/1/TROieeetit06.pdf
| doi = 10.1109/TIT.2005.864420
| citeseerx = 10.1.1.184.2957
| s2cid = 6496872
}}</ref>。
もう一つの興味深い理論的結果は、<math>D</math> が[[ユニタリ行列]]である場合に言及され、この仮定の下では、上述の問題（<math>\ell_0</math> または <math>\ell_1</math> を持つ）は、非線形縮退の形で閉形式解を認める<ref name="Elad2010" />。
=== バリエーション ===
基本的なスパース近似問題にはいくつかのバリエーションがある。
'''構造化スパース'''： この問題の元のバージョンでは、辞書に含まれる任意のアトムを選択することができる。構造化（ブロック）スパースモデルでは、個々のアトムを選択する代わりに、アトムのグループを選択する。これらのグループは、互いに重複していたり、大きさが異なる場合がある。その目的は、このブロック構造を強制しながら、スパースになるように <math>x</math> を表現することである<ref>{{cite journal
| author = Eldar, Y.C, Kuppinger, P. and Bolcskei, H.
| year = 2009
| title = Block-sparse signals: Uncertainty relations and efficient recovery
| journal = IEEE Transactions on Signal Processing
| volume = 58
| issue = 6
| pages = 3042–3054
| doi = 10.1109/TSP.2010.2044837
| arxiv = 0906.3173
| bibcode = 2010ITSP...58.3042E
| s2cid = 335122
}}</ref>。
'''協調的（共同）スパースコーディング'''： この問題の元のバージョンは、単一の信号 <math>x</math> に対して定義されている。協調的（共同）スパースコーディングモデルでは、信号の集合が利用可能であり、それぞれが <math>D</math> からの（ほぼ）同じアトムのセットから生成すると考えられている。この場合、追求タスクの目的は、データを最もよく表す一連のスパース表現を、それらが同じ（または近くの）サポートを共有するように強制しながら再現することである<ref>{{cite journal
| author = Tropp, J.A., Gilbert, A.C. and Strauss, M.J.
| year = 2006
| title = Algorithms for simultaneous sparse approximation. Part I: Greedy pursuit
| journal = Signal Processing
| volume = 86
| issue = 3
| pages = 572–588
| doi = 10.1016/j.sigpro.2005.05.030
}}</ref>。
'''その他の構造'''： より広義には、スパース近似問題は、<math>\alpha</math> の非ゼロ位置のパターンに特定の望ましい構造を強制しながら計算<!-- cast -->することができる。広く研究されている興味深い2つの事例は、ツリーベースの構造と、より一般的にはボルツマン分布サポートである<ref>{{cite journal
| author = Peleg, T. Eldar, Y.C. and Elad, M.
| year = 2012
| title = Exploiting Statistical Dependencies in Sparse Representations for Signal Recovery
| journal = IEEE Transactions on Signal Processing
| volume = 60
| issue = 5
| pages = 2286–2303
| doi = 10.1109/TSP.2012.2188520
| arxiv = 1010.5734| bibcode = 2012ITSP...60.2286P
| s2cid = 3179803
}}</ref>。
=== アルゴリズム ===
上述のように、スパース表現問題
: <math>
\min_{\alpha \in \mathbb{R}^p} \|\alpha\|_0 \text{ subject to } \|x - D\alpha \|_2^2 \le \epsilon^2.
</math>
を解くために開発されたさまざまな近似（'''追跡'''（pursuit）ともいう）アルゴリズムがある。
これらの主な手法のいくつかを以下に示す。
* {{仮リンク|マッチング追跡|en|Matching pursuit}}は、上記の問題を近似的に解くための貪欲反復アルゴリズムである。これは、<math>\alpha</math> 内の非ゼロの位置を一度に1つずつ徐々に見つけてゆく方法である。基本的な考え方は、各ステップで、現在の残余（<math>x</math> に初期化）と最も相関のある <math>D</math> の列（アトム）を見つけ、新しいアトムとその係数を考慮に入れて残余を更新することである。マッチング追跡では、同じアトムが複数回選択される場合がある。
* 直交マッチング追跡は、マッチング追跡と非常によく似ているて、大きな違いが一つある。アルゴリズムの各ステップで、すべての非ゼロ係数が[[最小二乗法]]によって更新される。その結果、残余はすでに選択されたアトムと直交しているため、1つのアトムを複数回選択することはできない。
* 段階的貪欲法： 上記のアルゴリズムに改良を加えたバージョンが、貪欲に動作するアルゴリズムで、2つの重要な機能が追加されている。(i) 一度に非ゼロのグループを追加する機能（ラウンドごとに1つの非ゼロではなく）と、(ii) 各ラウンドでいくつかのアトムをサポートから刈り込むプルーニングステップを含める。このアプローチの代表的なものに、部分空間追跡アルゴリズムとCoSaMPがある<ref>{{cite journal
| author = Needell, D. and Tropp, J.A.
| year = 2009
| title = CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
| journal = Applied and Computational Harmonic Analysis
| volume = 26
| issue = 3
| pages = 301–321
| doi = 10.1016/j.acha.2008.07.002
| arxiv = 0803.2392
}}</ref>。
* {{仮リンク|基底追跡|en|Basis pursuit}}法は、<math>\ell_0</math> を <math>\ell_1</math>ノルムに置き換えることで、問題の凸緩和版を解く。これは新しい目的を定義するだけであり、望ましい解を得るためにどのようなアルゴリズムを使用するかという問題は残されていることに注意すること。このようなアルゴリズムとして一般的に考えられているのは、{{仮リンク|反復再重み付け最小二乗|en|Iteratively reweighted least squares|label=IRLS}}、{{仮リンク|最小角回帰|en|Least-angle regression|label=LARS}}、および反復ソフトシュリンク法である<ref>{{cite journal
| author = Zibulevsky, M. and Elad, M.
| year = 2010
| title = L1-L2 optimization in signal and image processing
| journal = IEEE Signal Processing Magazine
| volume = 27
| issue = 3
| pages = 76–88
| url = https://www.cs.technion.ac.il/~elad/publications/journals/2010/L1L2_IEEE_SPM_2010.pdf
| doi = 10.1109/MSP.2010.936023
| bibcode = 2010ISPM...27...76Z
| s2cid = 2783691
}}</ref>。
* スパース分解問題を解く方法としては、他にも、ホモトピー法、{{仮リンク|座標降下法|en|Coordinate descent}}、反復ハードしきい値法、上述の反復ソフトシュリンク法に関連する一次{{仮リンク|近接勾配法|en|Proximal gradient method}}、ダンツィヒ・セレクタ（Dantzig selector）がある。
== 脚注 ==
{{Reflist|2}}
==
* [[圧縮センシング]]
* {{仮リンク|スパース辞書学習|en|Sparse dictionary learning}}
* {{仮リンク|K-SVD|en|K-SVD}}
* [[ラッソ回帰]]
* [[正則化]] および [[逆問題]]
== 参考 ==
{{参照方法|date=2018年1月}}
* 岡田真人, 「[http://id.nii.ac.jp/1001/00096877/ ハイパフォマンスコンピューティングとスパースモデリング]」『ハイパフォーマンスコンピューティングと計算科学シンポジウム論文集』 2014巻 2013年 p.23-24。
* 永田賢二, 田仲顕至, 「[
* 新部祐輔、吳湘筠, 渡辺一帆 ほか, 「[http://id.nii.ac.jp/1001/00106284/ スパースモデリングを目的とした平行座標系表示の拡張]」『情報処理学会第』 76 回全国大会 3 (2014)、頁8。
* 池田思朗, 「[
* Irina Rish、Genady Grabarnik："Sparse Modeling: Theory, Algorithms, and Applications"、CRC Press、ISBN 978-1439828694 (2014年11月17日)。
* 岡田真人, [
* 大関真之, 「[http://www-adsys.sys.i.kyoto-u.ac.jp/mohzeki/Presentation/lectureslide20150904-1.pdf 今日からできる スパースモデリング]」 京都大学大学院
* 池田思朗, 本間希樹, 植村誠, 「[
* 田中利幸, 「圧縮センシング (特集 スパースモデリングの発展: 原理から応用まで)--(全体概要と基本理論)」『電子情報通信学会誌』 99.5 (2016)、p.381-385, {{naid|40020842497}}。
* {{Cite book
* 永原正章：「スパースモデリング- 基礎から動的システムへの応用」、コロナ社、ISBN 978-4339032222（2017年10月6日）。
* 日高昇治：「スパースモデリングって何だ？データ構造を解き明かす先端技法」、カットシステム、ISBN 978-4877834265 (2017年10月25日)。
* [http://www.jam-house.co.jp/sparse_modeling/ Irina Rish, Genady Ya. Grabarnik:「スパースモデリング 理論、アルゴリズム、応用」]、ジャムハウス、{{ISBN2|
== 外部リンク ==
* {{Kotobank}}
{{Numerical linear algebra}}
{{DEFAULTSORT:すはあすもてりんく}}
[[Category:数値線形代数]]
[[Category:科学モデリング]]
[[Category:科学哲学の概念]]
| |||