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

スパース表現を探す

－辞書学習におけるサンプル複雑度と

アルゴリズム－

坂田綾香A_, 樺島祥介B

目次

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

目次

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

「辞書」とは

スパース表現のための“基底”

y₂ y₃ y 辞書 (N = 5本) y₁ データ次元 M = 3での例 データサンプル (全部でP個)

行列表記

＝

M P N ゼロ成分

D

D₁ D₂ D₃ D_N …

Y

Y₁ … Y_P

X

X₁ … X_P M _N P M 次元、 P 個のデータ M 次元、 N 個の基底(辞書) P 個のデータごとの スパース表現 データ次元 _< 辞書コラムの数 のとき、 Dを過完備辞書と呼ぶ。

過完備辞書を用いる目的

特徴を抽出する データが持つ傾向を辞書として表現する。 ノイズ耐性を得る ゼロ成分が存在していることで、 もとの信号とノイズを分離することが容易になる。 圧縮表現を得る 冗長な成分をゼロ成分と見なすことで

辞書学習

＝

M P N ゼロ成分

D

D₁ D₂ D₃ … D_N

Y

Y₁ … Y_P

X

X₁ … X_P M N P M 次元、 P 個のデータ M 次元、 N 個の基底(辞書) P 個のデータごとの スパース表現 データYから 辞書Dとスパース表現Xを学習することを 辞書学習と呼ぶ。

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

https://sites.google.com/site/igorcarron2/matrixfactorizations

行列分解問題

データを行列の積として近似する問題の総称 個別の問題ごとに、行列の性質を仮定する。 – 主成分分析(PCA) … Aのコラムは互いに直交する – 非負因子行列分解(NMF) … A, Xの要素が非ゼロ – 辞書学習(DL)…Xがスパース

～

Y

A

X

表現基底 Aの空間での座標

スパース基底に関する研究

1. 1960年代：フーリエ基底による信号処理 – 1965 FFT

＝

M M

D

D₀ D₁ … D_M-1 Y _X M M

y

D

x

y

D

=

exp(

in

),

=

T

スパース基底に関する研究

1. 1960年代：フーリエ基底による信号処理 – 1965 FFT

～

M K

D

D₀ … D_K Y X M K

y

D

x

y

D

_n

=

exp(

in

),

=

T フーリエ基底を用いた圧縮 (under complete基底) (K < M)

スパース基底に関する研究

2. 1970, 1980年代：主成分分析(PCA)

＝

M P M

D

Y

M

_X

M P

( )

a

Y

a

a

D

a a a a

Σ

=

=

= = =

∑

T 1 : 1 2 T 1 : 1 ₂ 2 2 2

max

arg

max

arg

P l l 主成分： Y YT = Σ ※ 第k成分： ＝ Σの第1固有ベクトル

=

k

D

Σの第k固有ベクトル

スパース基底に関する研究

2. 1970, 1980年代：主成分分析(PCA)

～

M P R

D

D₁ … D_R

Y

Y₁ … Y_P

X

X₁ … X_P M R P

( )

a

Y

a

a

D

a a a a

Σ

=

=

= = =

∑

T 1 : 1 2 T 1 : 1 ₂ 2 2 2

max

arg

max

arg

P l l 主成分： Y YT = Σ ※ 第k成分： ＝ Σの第1固有ベクトル

=

k

D

Σの第k固有ベクトル

スパース基底に関する研究

3. 過完備基底の提案

Simoncelli et al. (1992)

基底の直交性を破り、冗長にする

Wavelet変換の並進・回転不変性の欠如を補う目的

Nason and Silverman (1995)

スパース基底に関する研究

4. 「変換」から「基底選択」へ – 変換によるスパース表現ではなく、 固定された辞書の選択によりスパース表現を得る Chen et al. (1994) 基底選択問題をL1最小化として定式化 L1最小化に対してBasis Pursuitアルゴリズムを提案

Dx

y

x

,

subject

to

=

min

1

＝

M N

D

D₁ D₁ … D_N Y _X N

スパース基底に関する研究

5. 辞書の学習

Olshausen and Field (1997)

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

スパース基底に関する研究

Olshausen-Fieldの問題設定 画像I(x)を として表す基底_{φ_i(x)}、スパースベクトル_{ai}を知りたい 方法 として

∑

=

i i i i

a

I

(

x

)

φ

(

x

)

∑

∑

∑

_ +      − = i i i i i i S a a I a I E i ) ( ) ( ) ( ) | , ( 2 λ φ φ x x x

)

|

,

(

min

min

arg

*

φ

φ

φ a

E

I

a

=

Ｉ 平均 スパース正則化

スパース基底に関する研究

6. 辞書学習に対するアルゴリズムの開発

Method of Optimal Direction (Engan et al. 1999) K – SVD (Aharon et al. 2006)

7. 辞書学習に対するサンプル複雑度の解析

Ahron et al. (2006)

目次

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

過完備辞書による画像のスパース表現

データ集合 _Dictionary 2.5×105 _{個のパッチ} [Elad (2010)]

～

ゼロ成分 スパース表現

辞書学習によるノイズ除去

[Elad and Aharon (2006)]













−

+

+

−

∑

2 2 0 2 2 , ,

min

Y

Z

DX

Z

X D Z ij ij ij

x

µ

λ

ノイズを含む 画像 _{ノイズ除去された} 画像 スパース制約 辞書 元画像 ノイズあり 画像

辞書学習によるノイズ除去

[Elad and Aharon (2006)]

ノイズの強さ 辞書学習 DCT ノイズあり 画像 ノイズ除去 画像 σ = 20

目次

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

Overcomplete dictionary

によるスパース表現

データ集合 _Dictionary 2.5×105 _{個のパッチ} [Elad (2010)]

～

ゼロ成分 スパース表現 どのくらいサンプルがあれば、dictionaryを決定可能？

1．Support/Spark condition: ||X0 i||0 = k < σ(D0)/2 σ(D0_{) (spark)…最小の線形従属なコラムの数} (D0_∈RM×N _{がランダム行列のとき、}σ_(D0_{) = M+1).} 2．Richness condition： 同じD0_{コラムの組み合わせ(} NCk通り)を持つ、k+1個のサンプルが 存在すること。(したがって, P > (k+1)_NC_k) 3．Non-degeneracy condition： 同じD0コラムの組み合わせを持つ_k+1サンプルのランクは _k. 異なるD0コラムの組み合わせを持つ_k+1サンプルのランクは_k+1.

1．Support/Spark condition: ||X0 i||0 = k < σ(D0)/2 σ(D0_{) (spark)…最小の線形従属なコラムの数} (D0_∈RM×N _{がランダム行列のとき、}σ_(D0_{) = M+1).} 2．Richness condition： 同じD0_{コラムの組み合わせ(} NCk通り)を持つ、k+1個のサンプルが 存在すること。(したがって, P > (k+1)_NC_k) 3．Non-degeneracy condition： 同じD0コラムの組み合わせを持つ_k+1サンプルのランクは _k. 異なるD0コラムの組み合わせを持つ_k+1サンプルのランクは_k+1.

Dictionary

同定のための条件

[Aharon et. al. (2006)] Aharon et al. (2006)は – 諸条件を満たしたうえで、P > P_c～exp(O(N))ならば、 Dictionaryを一意に同定できることが数学的に証明可。 → P > P_c ～exp(O(N))は十分条件。 実際は P_c～2N(k+1)～O(N2₎で十分なのでは、 と考察しているが、数学的証明は難しい。

(後に[Vainsencher et. al.(2011)]により証明される。)

一方で、_MN+NP

ρ

個の未知変数に対して 既知のデータ数はMP。

研究動機

• 統計力学的アプローチからP_c を見積もる。

• 特に大自由度極限(熱力学的極限)N,M, P → ∞ における DL の典型的な振る舞いを調べる。

• Aharon らのplanted solution シナリオを採用し，sample

制約付き二乗誤差最小化による辞書学習

＝

M P N ゼロ成分

D

D₁ D₂ D₃ D_N …

Y

Y₁ … Y_P

X

X₁ … X_P M _N P M 次元、 P 個のデータ M 次元、 N 個の基底(辞書) P 個のデータごとの スパース表現

θ

NP

MN

=

=

−

2 2 ₀ ,

,

subject

to

,

min

Y

DX

D

X

X D 辞書を規格化 Xの非ゼロ成分数

Planted solution scenario

P > P_c のとき、 D = D0, X = X0 となる。 学習

Y

D

_X

P

0

D

X

0

P

P

訓練データ Y = D0_X0 N N

制約付き二乗誤差最小化による辞書学習

• 事後分布 β→∞ で||D0_X0_－DX||2 _{の最小化が実現する。} • 求めたいもの DとD0の類似度、 _Xと_X0の類似度の平均値 D、Xの分散 ||DX – D0_X0_||2の平均値

)

(

)

(

)

,

(

2

exp

)

,

|

,

(

0 2 0 0 2 0 0 0 0

θ

δ

δ

β

β β

NP

NM

Z

N

P

−

−

×













₋

₋

=

X

D

X

D

X

D

DX

X

D

X

D

DL

の

P

依存性を評価する

① DとD0_{, X}と_X0の平均二乗誤差 ₍一成分当たり₎

[

]

[

]

[ ]

X X X

Q

m

NP

NP

NP

+

−

≡

+

⋅

−

=

−

=

2

1

2

1

MSE

0 2 0 0 0 2 0

ρ

ρ

X

X

X

X

X

[

]

2

1

1

[

]

2

(

1

)

1

MSE

0 0 0 2 0 D D

m

MN

MN





≡

−









⋅

−

=

−

=

D

D

D

D

P₀(D0_,X0_)による D₀, X₀平均 P(D,X|D0_,X0_)による D, X平均

DL

の

P

依存性を評価する

② DとXの分散 (一成分当たり)

[ ]

[ ]

(

)

∑

−

=

il il il X

X

X

NP

0 2 0 2

β

χ

[ ]

[ ]

(

)

[ ]

















−

=

−

=

∑

∑

i i i i i D

D

MN

D

D

MN

_, 0 2 , 0 2 0 2

1

1

µ µ µ µ µ

β

β

χ

DL

の

P

依存性を評価する

③ エネルギー密度 (一成分当たり) –

χ

χ







+

+

+

−

+

















+

+

−

−

−

























₊

+

−

−

−

=

Ω Ω

)

1

(

2

)

2

(

)

,

ˆ

;

(

ˆ

2

ˆ

ˆ

ˆ

2

ˆ

ˆ

ˆ

2

ˆ

ˆ

extr

2 ˆ , X D X X D X h X X X X X X X D D D D D D D D

Q

m

m

Q

Q

h

m

m

Q

Q

Q

m

m

m

Q

f

χ

χ

ρ

αγ

λ

φ

λθ

χ

χ

γ

χ

χ

χ

α

} , ˆ , ˆ , ˆ , ˆ , ˆ , ˆ { ˆ }, , , , , {m_D χ_D Q_X m_X χ_X Ω= Q_D m_D χ_D Q_X m_X χ_X λ = Ω M/N P/N

DL

の

P

依存性を評価する：まとめ

平均二乗誤差と分散 エネルギー

)

ˆ

,

(

extr

arg

*

=

Ω

Ω

Ω

Ω

f

} , , , , {m_D

χ

_D Q_X m_X

χ

_X MSE_D, MSE_X,

χ

D,

χ

X 0 2 0 0 * *

1

)

ˆ

,

(

Ω

Ω

=

_



DX

−

D

X

_



MP

f

5変数の連立方程式を解き、 Ω∗_{を求めればよい。 → 複数個の解が存在する。}

解の分類

解① 解② • m_D = 1 • m_X =

ρ

• Q_X =

ρ

• m_D = 0 • m_X = 0 • Q_x ∈ R₊ ・

χ

_D = ∞,

χ

_X = ∞ f = 0 f = 0 ・

χ

_D = ∞,

χ

_X = ∞ f = 0 f ≠ 0 ・

χ

_D < ∞,

χ

_X < ∞ ・

χ

_D < ∞,

χ

_X < ∞

解の分類

解①：成功解(S) 解②:失敗解(F) • MSE_D = 0 • MSE_X = 0 ・

χ

_D = ∞,

χ

_X = ∞ ・

χ

_D < ∞,

χ

_X < ∞ f = 0 f = 0 ・

χ

_D = ∞,

χ

_X = ∞ f = 0 f ≠ 0 ・

χ

_D < ∞,

χ

_X < ∞ • MSE_D > 0 • MSE_X > 0

解の分類

解①：成功解(S) 解②:失敗解(F) ・

χ

_D = ∞,

χ

_X = ∞ ・

χ

_D < ∞,

χ

_X < ∞ f = 0 f = 0 ・

χ

_D = ∞,

χ

_X = ∞ f = 0 f ≠ 0 この解が唯一の安定解として 存在するとき、学習成功。 ・

χ

_D < ∞,

χ

_X < ∞ • MSE_D = 0 • MSE_X = 0 • MSE_D > 0 • MSE_X > 0

解の分類

解①：成功解(S) 解②:失敗解(F) ・

χ

_D = ∞,

χ

_X = ∞ ・

χ

_D < ∞,

χ

_X < ∞ f = 0 f = 0 ・

χ

_D = ∞,

χ

_X = ∞ f = 0 f ≠ 0 この解が唯一の安定解として 存在するとき、学習成功。 ・

χ

_D < ∞,

χ

_X < ∞ この解が存在するとき、 D0_X0 _{= DXを満たすD≠D}0_,X≠X0_{がたくさん存在。} 2 . D L の 統 計 力 学 • MSE_D = 0 • MSE_X = 0 • MSE_D > 0 • MSE_X > 0

① 成功解の

γ

依存性

・

χ

_D = ∞,

χ

_X = ∞ ・

χ

_D < ∞,

χ

_X < ∞ f = 0 f = 0 …1 <

γ

<

γ

_Sで存在 …

α

>

θ

_effS₍

θ

_,

ρ

_),

γ

S <

γ

で存在













−

−

+

=

>

2

exp

2

)

1

(

)

,

(

2 S eff

u

u

π

ρ

θ

ρ

θ

θ

α

)

,

(

)

,

,

(

_S eff

θ

ρ

θ

α

α

ρ

θ

α

γ

γ

−

=

>

_S

∫

+∞ ₋ = − z dz exp( 2) 2

θ

ρ

u は次のように決められる。 • MSE_D = 0 • MSE_X = 0

② 失敗解の

γ

依存性

・

χ

_D = ∞,

χ

_X = ∞ f = 0 f ≠ 0 ・

χ

_D < ∞,

χ

_X < ∞ …0<

γ

<

γ

_Fで存在。 …

α

>

θ

_effF₍

θ

_,

ρ

_),

γ

F <

γ

で存在。













−

+

=

>

2

exp

2

)

(

2 F eff

v

v

π

θ

θ

θ

α

(

)

2 F eff ) , (

θ

α

θ

α

γ

γ

− = > _F a 2 2 exp 2 2

θ

π

 =     −

∫

+∞ v z dz v は次のように決められる。 2 . D L の 統 計 力 学 • MSE_D > 0 • MSE_X > 0

Impossible to learn Learnable by O(N) samples

0.2

0.4

0.6

0.8

1

1

0.8

0.6

0.4

0.2

0

α

α

‐

θ

平面の相図

α = θ F eff

θ

α

=

α

>

θ

_effFでは、₍

α

，

θ

effF から決まる

γ

Fを用いて) P > N

γ

_Fのときにplanted solutionを同定できる。

Impossible to learn Learnable by O(N) samples

0.2

0.4

0.6

0.8

1

1

0.8

0.6

0.4

0.2

0

θ

α

α

‐

θ

平面の相図

α = θ F eff

θ

α

=

α

>

θ

_effFでは、₍

α

，

θ

effF から決まる

γ

Fを用いて) P > N

γ

_Fのときにplanted solutionを同定できる。 ベイズ最適な辞書学習では、 この領域でも学習が可能。

ベイズ最適な学習則

• 平均自乗誤差(MSE)を定義 ， は任意の学習則を用いて_Yから推定した解 <…>は次の同時分布による平均

∑

−

=

i i i D

D

D

MN

_µ µ µ

Y

D ,X ,Y 2 0 0 0

))

(

ˆ

(

1

MSE

∑

−

=

il il il X

X

X

NP

Y

D ,X ,Y 2 0 0 0

))

(

ˆ

(

1

MSE

)

;

(

)

(

)

,

,

(

₀ 0 ₀ 0 0 0 0 0

δ

ρ

X

D

X

D

Y

Y

X

D

P

P

P

=

_



−

_



) ( ˆ Y D Xˆ Y( )

ベイズ最適な学習則

MSE はベイズ最適な学習則により最小化される。 – この学習則による推定値は以下の通り。 – D_i はDのi 番目のコラム – <…> は事後分布P(D,X|Y) = P(D,X,Y)/P(Y)によるD，X平均. • つまり、推定の際にモデルの真の分布が分かっている。 • このとき、レプリカ対称解は安定。[Y. Iba (1999)]

X

Y

X

D

D

Y

D

ˆ

(

)

=

(

=

1

,...,

),

ˆ

ODL

(

)

=

2 ODL

N

i

M

i i i

ベイズ最適な学習則の解析

真の値と推定値の重なり m_D ，m_X を定義する MSE_D = 2(1 – m_D), MSE_X = 2(

ρ

– m_X) となるので m_D = 1, m_X =

ρ

: D0 と X0 の学習に成功。 m_D = 0, m_X = 0 : 学習失敗。 レプリカ法によりm , m のパラメータ依存性を明らかにする。

∑

=

i l i D

D

D

MN

m

µ µ µ D X Y

Y

, , ODL 0 0 0

)

(

ˆ

1

∑

=

il il il X

X

X

NP

m

Y X D

Y

, , ODL 0 0 0

)

(

ˆ

1

• レプリカ法によるm_D ，m_Xの表式 2 2 2 0 0 0 0

)

ˆ

1

(

ˆ

ˆ

)

(

ˆ

1

ˆ

















+

+

Ξ

Ξ

=

+

=

+

∫

X X X X X X X D D D

m

X

m

z

m

X

P

DzdX

m

m

m

m

σ

X D X X D X D X D X

m

m

m

m

m

m

m

m

−

=

−

=

₂

,

ˆ

₂

ˆ

ρσ

γ

ρσ

α

+ + _{Ξ = − + Ξ}         + + + = Ξ _{X X} X X X X X X X X m X m z m m ) 1 ( , ) ˆ 1 ( 2 ) ˆ ˆ ( exp ˆ 1 2 2 0 2 2

σ

ρ

σ

σ

ρ

α

= M / N

γ

= P / N

ベイズ最適な学習則の解析

m

_D

の

γ

依存性

(

α

= 0.5,

ρ

= 0.2)

•

γ

>

γ

_S =

α

/(

α

－

ρ

)で m_D = 1， m_X =

ρ

の解が現れる。 → Sample complexity は P_c = N

γ

_S. •

γ

>

γ

_M で m_D = 1 ，m_X =

ρ

以外の解が消える。 しかし、

γ

は

ρ

→

ρ

₍

α

_{)で発散する。} 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1.5 2 2.5 3 3.5 4 m D γ

γ

_S

γ

F

γ

_M m_D

γ

※ α = 圧縮率、 ρ = 非ゼロ要素の割合

•

α

と

ρ

の差が広がるにつれて

γ

_M は増加し、

ρ

>

ρ

_M(

α

) で発散する。

γ

_M

の

α

_,

ρ

依存性

ρM 0 20 40 60 80 100 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 γM ρ ρM 0 20 40 60 80 100 0 0.1 0.2 0.3 0.4 0.5 0.6 γ ρ

α

= 0.5

α

= 0.7

γ

_M

γ

_M

ρ

ρ

ρ

_M

_ρ

M ※ α = 圧縮率、ρ = 非ゼロ要素の割合

γ

_M

の意味

γ

>

γ

_M

で

m

_D

= 1

が大域的安定解となる。

γ

γ

_S <

γ

<

γ

_M

γ

>

γ

_M m_D = 1 (MSE = 0) m_D = 1 (MSE = 0) 0 < m_D < 1 (MSE > 0)

• (1)+(2): サンプル複雑度は P_c = N

γ

_S,

γ

_S =

α

/(

α

–

ρ

). • (1):

γ

_M が有限(

γ

>

γ

_M ではm_D = 1 が大域的安定解となる)

α

–

ρ

平面上の相図

0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 α ρ (1) (2) (3) Impossible to learn 二乗誤差最小化 による学習での O(N) limit

ρ

_M(

α

)

α

=

ρ

α

ρ

まとめ

辞書学習に対して、ベイズ最適な学習則を用いた場合の サンプル複雑度の解析を行った。 非ゼロ要素の割合

ρ

< 圧縮率

α

のとき、 原理的にはサンプル数 P > P_c =

γ

_sN で辞書学習が達成可。 サンプル複雑度はO(N)である。 先行研究の上界O(N2₎を改善した。 特に

ρ

<

ρ

_M(

α

)の場合、 学習成功状態が大域的な安定解となるため、 多項式時間で解を得られる可能性が示唆された。

Dictionary Learning

のアルゴリズム

Dictionary learningにおける理論限界：P > P_c～O(N)

理論限界を実現するアルゴリズムを構成したい。

必要なこと

既存アルゴリズムの性能評価

Method of Optimal Direction, K – SVD

新しいアルゴリズムの開発、改善