スパース表現を探す - 辞書学習におけるサンプル複雑度と アルゴリズム - 坂田綾香 A, 樺島祥介 B A 統計数理研究所, B 東京工業大学 1/53
( 前半 ) 目次 1. 辞書学習の導入と先行研究の紹介. 辞書学習の応用事例 3. 辞書学習のサンプル複雑度とは ( 後半 ) 4. 既存の辞書学習のアルゴリズム 5.Bayes 推定を用いた辞書学習のアルゴリズム /53
( 前半 ) 目次 1. 辞書学習の導入と先行研究の紹介. 辞書学習の応用事例 3. 辞書学習のサンプル複雑度とは ( 後半 ) 4. 既存の辞書学習のアルゴリズム 5.Bayes 推定を用いた辞書学習のアルゴリズム 3/53
辞書 とは スパース表現のための 基底 データ次元 M 3 での例 y 3 辞書 (N 5 本 ) y データサンプル ( 全部で P 個 ) y y 1 全ての基底は使わない スパース表現 4/53
行列表記 M 次元 P 個のデータ M 次元 N 個の基底 ( 辞書 ) P 個のデータごとのスパース表現 P N P M Y 1 Y Y P M 1 3 N N ゼロ成分 1 P データ次元 < 辞書コラムの数のとき を過完備辞書と呼ぶ 5/53
過完備辞書を用いる目的 特徴を抽出する データが持つ傾向を辞書として表現する ノイズ耐性を得る ゼロ成分が存在していることで もとの信号とノイズを分離することが容易になる 圧縮表現を得る 冗長な成分をゼロ成分と見なすことで圧縮された表現が得られる 6/53
M 次元 P 個のデータ P 辞書学習 M 次元 N 個の基底 ( 辞書 ) N P 個のデータごとのスパース表現 P M Y 1 Y Y P M 1 3 N N ゼロ成分 1 P データ Y から辞書 とスパース表現 を学習することを 辞書学習と呼ぶ 7/53
辞書学習は行列分解の一種 https://sites.google.co/site/igorcarron/atrixfactorizations 8/53
行列分解問題 データを行列の積として近似する問題の総称 Y ~ A 表現基底 個別の問題ごとに 行列の性質を仮定する 主成分分析 (PCA) A のコラムは互いに直交する 非負因子行列分解 (NMF) A, の要素が非ゼロ 辞書学習 (L) がスパース A の空間での座標 9/53
スパース基底に関する研究 1. 196 年代 : フーリエ基底による信号処理 1965 FFT M M M M Y n 1 M-1 exp( iny), x T y 1/53
スパース基底に関する研究 1. 196 年代 : フーリエ基底による信号処理 1965 FFT フーリエ基底を用いた圧縮 (under coplete 基底 ) K M ~ M K (K < M) Y K n exp( iny), x T y 11/53
スパース基底に関する研究. 197, 198 年代 : 主成分分析 (PCA) 主成分 : 第 k 成分 : k arg ax P ( T ) a Y arg ax a Σa 1 a: a Σ の第 1 固有ベクトル T l 1 l 1 a: a 1 Σ の第 k 固有ベクトル Σ Y T Y P M P M Y M M Y 1 Y P 1 M 1 P 1/53
スパース基底に関する研究. 197, 198 年代 : 主成分分析 (PCA) 主成分 : 第 k 成分 : k P arg ax P ( T ) a Y arg ax a Σa 1 a: a Σ の第 1 固有ベクトル T l 1 l 1 a: a 1 Σ の第 k 固有ベクトル PCA に基づく圧縮 (under coplete 基底 ) R P Σ Y T Y M Y ~ M R Y 1 Y P 1 R 1 P 13/53
スパース基底に関する研究 3. 過完備基底の提案 Sioncelli et al. (199) 基底の直交性を破り 冗長にする Wavelet 変換の並進 回転不変性の欠如を補う目的 Nason and Silveran (1995) Stationary Wavelet Transfor 14/53
スパース基底に関する研究 4. 変換 から 基底選択 へ 変換によるスパース表現ではなく 固定された辞書の選択によりスパース表現を得る Chen et al. (1994) 基底選択問題を L1 最小化として定式化 L1 最小化に対して Basis Pursuit アルゴリズムを提案 N in x, subject to y 1 x M N Y 1 1 N 15/53
5. 辞書の学習 スパース基底に関する研究 Olshausen and Field (1997) 視覚野における情報表現の疎性について エッジやラインなどの 少数の基本的性質が画像の本質である 視覚野において 少数の性質を抽出するコーディングが行われていると考えられる 基底行列の線形和として 高次元の情報を表す方法を提案 ただし和の数は少ないとする ( スパース性 ) 最尤推定に基づく学習を通して 入力データから基底を学習 16/53
スパース基底に関する研究 Olshausen-Field の問題設定 画像 I(x) を i I ( x) φ ( x ) として表す基底 {φ i (x)} スパースベクトル {a i } を知りたい a i i i 方法 E( I, a φ) として * φ I( x) aiφi ( xi ) + x i arg in φ i λ in E( I, a φ) a i S( a i ) スパース正則化 I 平均 17/53
スパース基底に関する研究 6. 辞書学習に対するアルゴリズムの開発 Method of Optial irection (Engan et al. 1999) K SV (Aharon et al. 6) 7. 辞書学習に対するサンプル複雑度の解析 Ahron et al. (6) Vainsencher et. al.(11) 18/53
( 前半 ) 目次 1. 辞書学習の導入と先行研究の紹介. 辞書学習の応用事例 3. 辞書学習のサンプル複雑度とは ( 後半 ) 4. 既存の辞書学習のアルゴリズム 5.Bayes 推定を用いた辞書学習のアルゴリズム 19/53
過完備辞書による画像のスパース表現 [Elad (1)] スパース表現 データ集合 ictionary ~.5 1 5 個のパッチ ゼロ成分 4 つの ictionary 成分の重ね合わせとして全パッチを表現 /53
辞書学習によるノイズ除去 [Elad and Aharon (6)] in λ Y Z,, Z + ij µ ij x ij + Z ノイズを含む画像 スパース制約 ノイズ除去された画像 辞書 元画像 ノイズあり画像 1/53
辞書学習によるノイズ除去 [Elad and Aharon (6)] σ ノイズあり画像 辞書学習 CT ノイズ除去画像 ノイズの強さ /53
( 前半 ) 目次 1. 辞書学習の導入と先行研究の紹介. 辞書学習の応用事例 3. 辞書学習のサンプル複雑度とは ( 後半 ) 4. 既存の辞書学習のアルゴリズム 5.Bayes 推定を用いた辞書学習のアルゴリズム 3/53
Overcoplete dictionary によるスパース表現 [Elad (1)] スパース表現 データ集合 ictionary ~.5 1 5 個のパッチ ゼロ成分 どのくらいサンプルがあれば dictionary を決定可能? 4/53
ictionary 同定のための条件 [Aharon et. al. (6)] 1.Support/Spark condition: i k < σ( )/ σ( ) (spark) 最小の線形従属なコラムの数 ( R M N がランダム行列のとき σ( ) M+1)..Richness condition: 同じ コラムの組み合わせ ( N C k 通り ) を持つ k+1 個のサンプルが 存在すること ( したがって, P > (k+1) N C k ) 3.Non-degeneracy condition: 同じ コラムの組み合わせを持つ k+1 サンプルのランクは k. 異なる コラムの組み合わせを持つ k+1 サンプルのランクは k+1. 5/53
ictionary 同定のための条件 [Aharon et. al. (6)] 1.Support/Spark condition: i k < σ( )/ σ( ) (spark) 最小の線形従属なコラムの数 ( R M N がランダム行列のとき σ( ) M+1)..Richness condition: 同じ コラムの組み合わせ ( N C k 通り ) を持つ k+1 個のサンプルが 存在すること ( したがって, P > (k+1) N C k ) 3.Non-degeneracy condition: 同じ コラムの組み合わせを持つ k+1 サンプルのランクは k. 異なる コラムの組み合わせを持つ k+1 サンプルのランクは k+1. 6/53
ictionary 同定のための条件 [Aharon et. al. (6)] Aharon et al. (6) は 諸条件を満たしたうえで P > P c ~exp(o(n)) ならば ictionaryを一意に同定できることが数学的に証明可 P > P c ~exp(o(n)) は十分条件 実際は P c ~N(k+1)~O(N ) で十分なのでは と考察しているが 数学的証明は難しい ( 後に [Vainsencher et. al.(11)] により証明される ) 一方で MN+NPρ 個の未知変数に対して既知のデータ数は MP M~O(N) のとき P~O(N) で良いのでは? 7/53
研究動機 統計力学的アプローチから P c を見積もる 特に大自由度極限 ( 熱力学的極限 )N,M, P における L の典型的な振る舞いを調べる Aharon らの planted solution シナリオを採用し,saple coplexity の典型な値を評価する. 8/53
制約付き二乗誤差最小化による辞書学習 M 次元 P 個のデータ M 次元 N 個の基底 ( 辞書 ) P 個のデータごとのスパース表現 P N P M Y 1 Y Y P M 1 3 N N ゼロ成分 1 P in, Y, subject to MN, NPθ 辞書を規格化 の非ゼロ成分数 9/53
Planted solution scenario 訓練データ P Y P 学習 N Y P N P > P c のとき, となる 3/53
31/53 制約付き二乗誤差最小化による辞書学習 事後分布 β で - の最小化が実現する 求めたいもの と の類似度 と の類似度の平均値 の分散 の平均値 ) ( ) ( ), ( exp ),, ( θ δ δ β β β NP NM Z N P
L の P 依存性を評価する 1 と, と の平均二乗誤差 ( 一成分当たり ) [ ] 1 1 [ ] (1 ) 1 MSE MN MN P(,, ) による, 平均 P (, ) による, 平均 MSE 1 NP ρ [ ] NP 1 NP [ ] [ ] + ρ + Q MSE, MSE なら <>, <> は, に収束 3/53
L の P 依存性を評価する と の分散 ( 一成分当たり ) χ β MN ([ ] [ ] ) [ ] 1 1 µ i µ i β µ, i MN µ, i µ i χ il ([ ] [ ] ) β il il NP 33/53
34/53 L の P 依存性を評価する 3 エネルギー密度 ( 一成分当たり ),, Q, χ, χ は f の停留点として与えられる + + + + + + + + Ω Ω ) (1 ) ( ), ; ( extr, h Q Q Q h Q Q Q Q f χ χ ρ αγ λ φ λθ χ χ γ χ χ χ α },,,,,, { },,,,, { λ χ χ χ χ Q Q Q Ω Ω M/N P/N
L の P 依存性を評価する : まとめ 平均二乗誤差と分散 Ω * arg extr Ω f ( Ω, Ω ) {, χ, Q,, χ } MSE, MSE, χ, χ エネルギー f ( Ω, Ω ) * * 1 MP 5 変数の連立方程式を解き Ω を求めればよい 複数個の解が存在する 35/53
解の分類 解 1 1 ρ Q ρ χ, χ f χ <, χ < f 解 Q x R + χ, χ f χ <, χ < f 36/53
解の分類 解 1: 成功解 (S) MSE MSE χ, χ χ <, χ < f f 解 : 失敗解 (F) MSE > MSE > χ, χ f χ <, χ < f 37/53
解の分類 解 1: 成功解 (S) MSE MSE 解 : 失敗解 (F) χ, χ χ <, χ < この解が唯一の安定解として存在するとき 学習成功 f f MSE > MSE > χ, χ f χ <, χ < f 38/53
解の分類. L の 統計力解 1: 成功解 (S) MSE MSE 学解 : 失敗解 (F) χ, χ χ <, χ < この解が唯一の安定解として存在するとき 学習成功 f f MSE > MSE > χ, χ f χ <, χ < f この解が存在するとき を満たす, がたくさん存在 39/53
1 成功解の γ 依存性 MSE MSE χ, χ f 1 < γ <γ S で存在 χ <, χ < f α > θ effs (θ, ρ), γ S < γ で存在 > S u α θeff ( θ, ρ) θ + (1 ρ) u exp π α γ > γ S ( α, θ, ρ) S α θ ( θ, ρ) u は次のように決められる + u eff exp( z dz π ) θ ρ (1 ρ) 4/53
. L の MSE> MSE > 学 統計力 失敗解の γ 依存性 χ, χ f < γ< γ F で存在 χ <, χ < f α > θ efff (θ, ρ), γ F < γ で存在 > F v α θeff ( θ ) θ + v exp π a γ > γ F ( α, θ ) F α θ v は次のように決められる ( ) + v eff dz exp π z θ 41/53
α θ 平面の相図 α > θefffでは (α θefff から決まるγFを用いて) P > NγFのときにplanted solutionを同定できる α θefff 1.8 α Learnable by O(N) saples αθ.6.4. Ipossible to learn..4 θ.6.8 1 4/53
α θ 平面の相図 α > θefffでは (α θefff から決まるγFを用いて) P > NγFのときにplanted solutionを同定できる α θefff 1.8 α Learnable by O(N) saples αθ.6.4 ベイズ最適な辞書学習では この領域でも学習が可能. Ipossible to learn..4 θ.6.8 1 43/53
44/53 ベイズ最適な学習則 平均自乗誤差 (MSE) を定義, は任意の学習則を用いて Y から推定した解 < > は次の同時分布による平均 i i i MN µ µ µ Y Y,, )) ( ( 1 MSE il il il NP Y Y,, )) ( ( 1 MSE ) ; ( ) ( ),, ( ρ δ Y Y P P N P ) ( Y ) ( Y
ベイズ最適な学習則 MSE はベイズ最適な学習則により最小化される この学習則による推定値は以下の通り OL M i Y OL i ( ) ( i 1,..., N), ( Y) i i は の i 番目のコラム < > は事後分布 P(, Y) P(,,Y)/P(Y) による, 平均. つまり 推定の際にモデルの真の分布が分かっている このとき レプリカ対称解は安定 [Y. Iba (1999)] 45/53
ベイズ最適な学習則の解析 真の値と推定値の重なり, を定義する 1 MN 1 NP µ i il µ i il OL µ l OL il ( Y) ( Y),,, Y, Y MSE (1 ), MSE (ρ ) となるので 1, ρ : と の学習に成功, : 学習失敗 レプリカ法により, のパラメータ依存性を明らかにする 46/53
47/53 レプリカ法による, の表式 ) (1 ) ( 1 + + Ξ Ξ + + z P zd σ, ρσ γ ρσ α + + + Ξ Ξ + + + Ξ z ) (1, ) (1 ) ( exp 1 ρ σ σ σ ρ α M / N γ P / N ベイズ最適な学習則の解析
の γ 依存性 (α.5, ρ.) 1.9.8.7.6.5.4.3..1 γ S γ F 1.5.5 3 3.5 4 γ > γ S α/(α - ρ) で 1, ρ の解が現れる Saple coplexity は P c Nγ S. γ > γ M で 1, ρ 以外の解が消える しかし γ M は ρ ρ M (α) で発散する γ γ γ M α 圧縮率 ρ 非ゼロ要素の割合 48/53
γ M の α, ρ 依存性 α 圧縮率 ρ 非ゼロ要素の割合 1 8 6 γ M 4 γ M α.5 α.7 1 8 6 γ M 4 γ ρ M.5.1.15 ρ..5.3.35 ρ ρ M.1..3 ρ.4.5.6 ρ α と ρ の差が広がるにつれて γ M は増加し ρ > ρ M (α) で発散する 49/53
γ M の意味 γ S < γ < γ M γ > γ M 1 (MSE ) < < 1 (MSE > ) 1 (MSE ) γ > γ M で 1 が大域的安定解となる γ M が有限の時 局所探索アルゴリズムにより学習が可能 5/53
α ρ 平面上の相図 α 1.8.6 α.4. (1) () (3) Ipossible to learn..4 ρ.6.8 1 ρ 二乗誤差最小化による学習での O(N) liit ρ M (α) α ρ (1)+(): サンプル複雑度は P c Nγ S, γ S α/(α ρ). (1): γ M が有限 (γ > γ M では 1 が大域的安定解となる ) 51/53
まとめ 辞書学習に対して ベイズ最適な学習則を用いた場合の サンプル複雑度の解析を行った 非ゼロ要素の割合 ρ < 圧縮率 α のとき 原理的にはサンプル数 P > P c γ s N で辞書学習が達成可 サンプル複雑度は O(N) である 先行研究の上界 O(N ) を改善した 特に ρ < ρ M (α) の場合 学習成功状態が大域的な安定解となるため 多項式時間で解を得られる可能性が示唆された 5/53
ictionary Learning のアルゴリズム ictionary learning における理論限界 :P > P c ~O(N) 理論限界を実現するアルゴリズムを構成したい 必要なこと 既存アルゴリズムの性能評価 Method of Optial irection, K SV 新しいアルゴリズムの開発 改善 Belief propagation 53/53