ˆ ˆ extr

DL の P 依存性を評価する

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

–

χ χ

 

 +

+

+ + −

 





 



 − − + +

−



 



 





 



 − − + +

−

=

Ω Ω

) 1

( 2

) 2

(

) ˆ ,

; ˆ (

2 ˆ ˆ

2 ˆ ˆ ˆ 2 ˆ

ˆ ˆ

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

平均二乗誤差と分散

エネルギー

ˆ ) , (

extr

*

= arg Ω Ω

Ω

Ω

f

} ,

, ,

,

{m_D

χ

_D Q_X m_X

χ

_X

MSE_D, MSE_X,

χ

_D^,

χ

_X

0 0 2

0

*

*

1

ˆ ) ,

(  

  −

= Ω

Ω DX D X

f MP

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 ^{< ∞}

この解が存在するとき、

D⁰X⁰ = DXを満たすD≠D⁰,X≠X⁰がたくさん存在。

. DL2の統計力学

• MSE_D = 0

• MSE_X = 0

• MSE_D > 0

• MSE_X > 0

① 成功解の γ ^依存性

・

χ

_D ^{= ∞,}

χ

_X ^{= ∞}

・

χ

_D ^{< ∞,}

χ

_X ^{< ∞}

f = 0

f = 0

…1 < γ ^<γ_S^で存在

… α ^> θ_eff^S(θ^, ρ^), γ_S ^< γ ^で存在

 



 

 −

− +

=

> 2 exp 2

) 1

( )

, (

2 S

eff

u u ρ π

θ ρ

θ θ

α

) , ) (

, ,

(

_S

eff

θ ρ θ

α ρ α

θ α γ

γ >

_S

= −

+∞

∫

− z = −

dz exp( ² 2)

θ ρ

u は次のように決められる。

• MSE_D = 0

• MSE_X = 0

② 失敗解の γ ^依存性

・

χ

_D ^{= ∞,}

χ

_X ^{= ∞ f = 0}

f ≠ 0

・

χ

_D ^{< ∞,}

χ

_X ^{< ∞}

…0< γ ^< γ_F^で存在。

…α ^> θ_eff^F(θ^, ρ^), γ_F ^< γ ^で存在。







− +

=

> 2 exp 2

) (

2 F

eff

v v

θ π

θ θ

α

(

^effF

)

²

) ,

(

α θ α θ

γ

γ

> = −a

F

2 exp 2

2

2

θ

π

^ ⁼





−

+∞

∫

v

z dz

v は次のように決められる。

. DL2の統計力学

• 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

α

=

α

^>

θ

_eff^Fでは、(

α

^，

θ

_eff^{F から決まる}

γ

_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

α

=

α

^>

θ

_eff^Fでは、(

α

^，

θ

_eff^{F から決まる}

γ

_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

^{X Y} δ ^{Y D X D 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

D X Y D

D ˆ ( ) = ( = 1 ,..., ), ˆ

^ODL

( ) =

2

ODL

M i N

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

m MN

µ µ µ

Y X

Y

D

, , ODL

0

0

)

0

ˆ ( 1

∑

=

il

il il

X

X X

m NP

Y X

Y

D

, , 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

X m 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 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 =

γ

_s^{N で辞書学習が達成可。}

サンプル複雑度はO(N)である。

先行研究の上界O(N²)を改善した。

特に

ρ

^<

ρ

_M⁽

α

^{)の場合、}

学習成功状態が大域的な安定解となるため、

多項式時間で解を得られる可能性が示唆された。

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