( 前半 ) 目次 1. 辞書学習の導入と先行研究の紹介. 辞書学習の応用事例 3. 辞書学習のサンプル複雑度とは ( 後半 ) 4. 既存の辞書学習のアルゴリズム 5.Bayes 推定を用いた辞書学習のアルゴリズム /53

Size: px

Start display at page:

Download "( 前半 ) 目次 1. 辞書学習の導入と先行研究の紹介. 辞書学習の応用事例 3. 辞書学習のサンプル複雑度とは ( 後半 ) 4. 既存の辞書学習のアルゴリズム 5.Bayes 推定を用いた辞書学習のアルゴリズム /53"

ありさこうだ
5 years ago
Views:

1 スパース表現を探す - 辞書学習におけるサンプル複雑度とアルゴリズム - 坂田綾香 A, 樺島祥介 B A 統計数理研究所, B 東京工業大学 1/53

2 ( 前半 ) 目次 1. 辞書学習の導入と先行研究の紹介. 辞書学習の応用事例 3. 辞書学習のサンプル複雑度とは ( 後半 ) 4. 既存の辞書学習のアルゴリズム 5.Bayes 推定を用いた辞書学習のアルゴリズム /53

3 ( 前半 ) 目次 1. 辞書学習の導入と先行研究の紹介. 辞書学習の応用事例 3. 辞書学習のサンプル複雑度とは ( 後半 ) 4. 既存の辞書学習のアルゴリズム 5.Bayes 推定を用いた辞書学習のアルゴリズム 3/53

4 辞書とはスパース表現のための基底データ次元 M 3 での例 y 3 辞書 (N 5 本 ) y データサンプル ( 全部で P 個 ) y y 1 全ての基底は使わないスパース表現 4/53

5 行列表記 M 次元 P 個のデータ M 次元 N 個の基底 ( 辞書 ) P 個のデータごとのスパース表現 P N P M Y 1 Y Y P M 1 3 N N ゼロ成分 1 P データ次元 < 辞書コラムの数のときを過完備辞書と呼ぶ 5/53

6 過完備辞書を用いる目的特徴を抽出するデータが持つ傾向を辞書として表現するノイズ耐性を得るゼロ成分が存在していることでもとの信号とノイズを分離することが容易になる圧縮表現を得る冗長な成分をゼロ成分と見なすことで圧縮された表現が得られる 6/53

7 M 次元 P 個のデータ P 辞書学習 M 次元 N 個の基底 ( 辞書 ) N P 個のデータごとのスパース表現 P M Y 1 Y Y P M 1 3 N N ゼロ成分 1 P データ Y から辞書とスパース表現を学習することを辞書学習と呼ぶ 7/53

8 辞書学習は行列分解の一種 8/53

9 行列分解問題データを行列の積として近似する問題の総称 Y ~ A 表現基底個別の問題ごとに行列の性質を仮定する主成分分析 (PCA) A のコラムは互いに直交する非負因子行列分解 (NMF) A, の要素が非ゼロ辞書学習 (L) がスパース A の空間での座標 9/53

10 スパース基底に関する研究年代 : フーリエ基底による信号処理 1965 FFT M M M M Y n 1 M-1 exp( iny), x T y 1/53

11 スパース基底に関する研究年代 : フーリエ基底による信号処理 1965 FFT フーリエ基底を用いた圧縮 (under coplete 基底 ) K M ~ M K (K < M) Y K n exp( iny), x T y 11/53

12 スパース基底に関する研究. 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

13 スパース基底に関する研究. 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

14 スパース基底に関する研究 3. 過完備基底の提案 Sioncelli et al. (199) 基底の直交性を破り冗長にする Wavelet 変換の並進回転不変性の欠如を補う目的 Nason and Silveran (1995) Stationary Wavelet Transfor 14/53

15 スパース基底に関する研究 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

16 5. 辞書の学習スパース基底に関する研究 Olshausen and Field (1997) 視覚野における情報表現の疎性についてエッジやラインなどの少数の基本的性質が画像の本質である視覚野において少数の性質を抽出するコーディングが行われていると考えられる基底行列の線形和として高次元の情報を表す方法を提案ただし和の数は少ないとする ( スパース性 ) 最尤推定に基づく学習を通して入力データから基底を学習 16/53

17 スパース基底に関する研究 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

18 スパース基底に関する研究 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

19 ( 前半 ) 目次 1. 辞書学習の導入と先行研究の紹介. 辞書学習の応用事例 3. 辞書学習のサンプル複雑度とは ( 後半 ) 4. 既存の辞書学習のアルゴリズム 5.Bayes 推定を用いた辞書学習のアルゴリズム 19/53

20 過完備辞書による画像のスパース表現 [Elad (1)] スパース表現データ集合 ictionary ~ 個のパッチゼロ成分 4 つの ictionary 成分の重ね合わせとして全パッチを表現 /53

21 辞書学習によるノイズ除去 [Elad and Aharon (6)] in λ Y Z,, Z + ij µ ij x ij + Z ノイズを含む画像スパース制約ノイズ除去された画像辞書元画像ノイズあり画像 1/53

22 辞書学習によるノイズ除去 [Elad and Aharon (6)] σ ノイズあり画像辞書学習 CT ノイズ除去画像ノイズの強さ /53

23 ( 前半 ) 目次 1. 辞書学習の導入と先行研究の紹介. 辞書学習の応用事例 3. 辞書学習のサンプル複雑度とは ( 後半 ) 4. 既存の辞書学習のアルゴリズム 5.Bayes 推定を用いた辞書学習のアルゴリズム 3/53

24 Overcoplete dictionary によるスパース表現 [Elad (1)] スパース表現データ集合 ictionary ~ 個のパッチゼロ成分どのくらいサンプルがあれば dictionary を決定可能? 4/53

25 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

26 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

27 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

28 研究動機統計力学的アプローチから P c を見積もる特に大自由度極限 ( 熱力学的極限 )N,M, P における L の典型的な振る舞いを調べる Aharon らの planted solution シナリオを採用し,saple coplexity の典型な値を評価する. 8/53

29 制約付き二乗誤差最小化による辞書学習 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

30 Planted solution scenario 訓練データ P Y P 学習 N Y P N P > P c のとき, となる 3/53

31 31/53 制約付き二乗誤差最小化による辞書学習事後分布 β で - の最小化が実現する求めたいものとの類似度との類似度の平均値の分散の平均値 ) ( ) ( ), ( exp ),, ( θ δ δ β β β NP NM Z N P

32 L の P 依存性を評価する 1 と, との平均二乗誤差 ( 一成分当たり ) [ ] 1 1 [ ] (1 ) 1 MSE MN MN P(,, ) による, 平均 P (, ) による, 平均 MSE 1 NP ρ [ ] NP 1 NP [ ] [ ] + ρ + Q MSE, MSE なら <>, <> は, に収束 3/53

33 L の P 依存性を評価するとの分散 ( 一成分当たり ) χ β MN ([ ] [ ] ) [ ] 1 1 µ i µ i β µ, i MN µ, i µ i χ il ([ ] [ ] ) β il il NP 33/53

34 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

35 L の P 依存性を評価する : まとめ平均二乗誤差と分散 Ω * arg extr Ω f ( Ω, Ω ) {, χ, Q,, χ } MSE, MSE, χ, χ エネルギー f ( Ω, Ω ) * * 1 MP 5 変数の連立方程式を解き Ω を求めればよい複数個の解が存在する 35/53

36 解の分類解 1 1 ρ Q ρ χ, χ f χ <, χ < f 解 Q x R + χ, χ f χ <, χ < f 36/53

37 解の分類解 1: 成功解 (S) MSE MSE χ, χ χ <, χ < f f 解 : 失敗解 (F) MSE > MSE > χ, χ f χ <, χ < f 37/53

38 解の分類解 1: 成功解 (S) MSE MSE 解 : 失敗解 (F) χ, χ χ <, χ < この解が唯一の安定解として存在するとき学習成功 f f MSE > MSE > χ, χ f χ <, χ < f 38/53

39 解の分類. L の統計力解 1: 成功解 (S) MSE MSE 学解 : 失敗解 (F) χ, χ χ <, χ < この解が唯一の安定解として存在するとき学習成功 f f MSE > MSE > χ, χ f χ <, χ < f この解が存在するときを満たす, がたくさん存在 39/53

40 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

41 . L の MSE> MSE > 学統計力失敗解の γ 依存性 χ, χ f < γ< γ F で存在 χ <, χ < f α > θ efff (θ, ρ), γ F < γ で存在 > F v α θeff ( θ ) θ + v exp π a γ > γ F ( α, θ ) F α θ v は次のように決められる ( ) + v eff dz exp π z θ 41/53

42 α θ 平面の相図 α > θefffでは (α θefff から決まるγFを用いて) P > NγFのときにplanted solutionを同定できる α θefff 1.8 α Learnable by O(N) saples αθ.6.4. Ipossible to learn..4 θ /53

43 α θ 平面の相図 α > θefffでは (α θefff から決まるγFを用いて) P > NγFのときにplanted solutionを同定できる α θefff 1.8 α Learnable by O(N) saples αθ.6.4 ベイズ最適な辞書学習ではこの領域でも学習が可能. Ipossible to learn..4 θ /53

44 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

45 ベイズ最適な学習則 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

46 ベイズ最適な学習則の解析真の値と推定値の重なり, を定義する 1 MN 1 NP µ i il µ i il OL µ l OL il ( Y) ( Y),,, Y, Y MSE (1 ), MSE (ρ ) となるので 1, ρ : との学習に成功, : 学習失敗レプリカ法により, のパラメータ依存性を明らかにする 46/53

47 47/53 レプリカ法による, の表式 ) (1 ) ( Ξ Ξ + + z P zd σ, ρσ γ ρσ α Ξ Ξ Ξ z ) (1, ) (1 ) ( exp 1 ρ σ σ σ ρ α M / N γ P / N ベイズ最適な学習則の解析

48 の γ 依存性 (α.5, ρ.) γ S γ F γ > γ S α/(α - ρ) で 1, ρ の解が現れる Saple coplexity は P c Nγ S. γ > γ M で 1, ρ 以外の解が消えるしかし γ M は ρ ρ M (α) で発散する γ γ γ M α 圧縮率 ρ 非ゼロ要素の割合 48/53

49 γ M の α, ρ 依存性 α 圧縮率 ρ 非ゼロ要素の割合 γ M 4 γ M α.5 α γ M 4 γ ρ M ρ ρ ρ M.1..3 ρ ρ α と ρ の差が広がるにつれて γ M は増加し ρ > ρ M (α) で発散する 49/53

50 γ M の意味 γ S < γ < γ M γ > γ M 1 (MSE ) < < 1 (MSE > ) 1 (MSE ) γ > γ M で 1 が大域的安定解となる γ M が有限の時局所探索アルゴリズムにより学習が可能 5/53

51 α ρ 平面上の相図 α α.4. (1) () (3) Ipossible to learn..4 ρ ρ 二乗誤差最小化による学習での O(N) liit ρ M (α) α ρ (1)+(): サンプル複雑度は P c Nγ S, γ S α/(α ρ). (1): γ M が有限 (γ > γ M では 1 が大域的安定解となる ) 51/53

52 まとめ辞書学習に対してベイズ最適な学習則を用いた場合のサンプル複雑度の解析を行った非ゼロ要素の割合 ρ < 圧縮率 α のとき原理的にはサンプル数 P > P c γ s N で辞書学習が達成可サンプル複雑度は O(N) である先行研究の上界 O(N ) を改善した特に ρ < ρ M (α) の場合学習成功状態が大域的な安定解となるため多項式時間で解を得られる可能性が示唆された 5/53

53 ictionary Learning のアルゴリズム ictionary learning における理論限界 :P > P c ~O(N) 理論限界を実現するアルゴリズムを構成したい必要なこと既存アルゴリズムの性能評価 Method of Optial irection, K SV 新しいアルゴリズムの開発改善 Belief propagation 53/53

様々なミクロ計量モデル†

様々なミクロ計量モデル† 担当 : 長倉大輔 ( ながくらだいすけ ) この資料は私の講義において使用するために作成した資料です WEB ページ上で公開しており自由に参照して頂いて構いませんただし内容について一応検証してありますがもし間違いがあった場合でもそれによって生じるいかなる損害不利益について責任を負いかねますのでご了承ください間違いは発見次第継続的に直していますがまだ存在する可能性があります 1 カウントデータモデル