Algebraic Geometry of Learning Machines

Presentation on theme: "Algebraic Geometry of Learning Machines"— Presentation transcript:

1 Algebraic Geometry of Learning Machines
学習理論と代数幾何 東京工業大学 渡辺澄夫 2019/2/16 Algebraic Geometry of Learning Machines

2 Algebraic Geometry of Learning Machines
1. Introduction 学習理論とは … X1, X2, …, Xn q(x) ? q(x) 学習者 2019/2/16 Algebraic Geometry of Learning Machines

3 Algebraic Geometry of Learning Machines
1. Introduction 真の分布　と　学習モデル 学習者 x: 見える si sj wij y: 隠れ部分 p(x|w) 真の分布 例 推測 si p(x|w*) wij* sj y: 隠れ部分 x: 見える w → p( |w) が1対1でない ・・・特定不能 2019/2/16 Algebraic Geometry of Learning Machines

4 Algebraic Geometry of Learning Machines
1. Introduction 事後分布と特異点 p(x|w*) p(x|w) D(w*||w) = ∫p(x|w*) log dx カルバック情報量 W D(w*||w) =0 : 解析的集合 特異点 事後分布も最尤推定量の分布も正規分布には漸近しません。 2019/2/16 Algebraic Geometry of Learning Machines

5 Algebraic Geometry of Learning Machines
1. Introduction 特異モデルの性質 W/～ W=Rd:　パラメータ全体の集合 同値関係　 w1～w2⇔「p(x|w1)= p(x|w2) (∀x)」 W/～　は特異点を持つ集合 2019/2/16 Algebraic Geometry of Learning Machines

6 Algebraic Geometry of Learning Machines
1. Introduction 統計的正則モデルと特異モデル 特異モデル 　　隠れマルコフモデル 　　神経回路網 混合正規分布 　　ベイズネットワーク 縮小ランク回帰 　　ボルツマンマシン 正則モデル 　　正規分布 　　指数分布 　　多項式回帰 隠れた部分がある学習モデルは特異モデルになる 2019/2/16 Algebraic Geometry of Learning Machines

7 Algebraic Geometry of Learning Machines
1. Introduction なぜ特異モデルが必要か １．データから構造を取り出したい ２．潜在（隠れ）変数を使いたい ３．未知の分布を効率よく近似したい 2019/2/16 Algebraic Geometry of Learning Machines

8 Algebraic Geometry of Learning Machines
2. Main Result 記号 確率変数 X　　　分布 q(x)=p(x|w*) Dn = { X1, X2, …, Xn } 独立 モデル p(x|w) , 事前 φ(w) f(x,w) = log q(x) – log p(x|w) K(w) ＝ EX[ f(X,w) ] カルバック情報量 2019/2/16 Algebraic Geometry of Learning Machines

9 Algebraic Geometry of Learning Machines
2. Main Result 条件 (1) W∋w → f( ,w)∈ L2(q) ： 解析関数 L2(q) ={g ;∫|g(x)|2q(x)dx <∞} (2) φ(w) ＝ a0(w) (a1(w)>0,…, aL(w)>0) (それ以外) C1関数 解析関数 コンパクト サポート 2019/2/16 Algebraic Geometry of Learning Machines

10 Algebraic Geometry of Learning Machines
2. Main Result ベイズ統計 n i=1 Hn(w) = ∑ f(xi,w) 対数尤度比 事後分布 e －Hn(w) φ(w) dw １ Z (Dn) p(w|Dn) dw = p(x|Dn) = ∫p(x|w) p(w|Dn) dw 予測分布 2019/2/16 Algebraic Geometry of Learning Machines

11 Algebraic Geometry of Learning Machines
2. Main Result 周辺尤度と汎化誤差 Z (Dn)　= ∫e －Hn(w) φ(w) dw 周辺尤度 平均対数周辺尤度 F(n) = E[ - log Z(Dn) ] ∫q(x) log dx q(x) p(x|Dn) 汎化誤差 G(n) = E[ ] G(n) =　F(n+1) – F(n) 2019/2/16 Algebraic Geometry of Learning Machines

12 Algebraic Geometry of Learning Machines
2. Main Result 主定理 -λ (-λ): ζ(z) の一番大きな極、ｍ：位数 Re(z) Im(z) ζ(z) = ∫K(w)zφ(w) dw ゼータ関数 Re(z)>0 では正則関数 有理型関数として全複素平面に解析接続できる Z(Dn) nλ (log n) m-1 Z* 法則 収束 n → ∞ Cf．E[Z*] ＝ ∞ 2019/2/16 Algebraic Geometry of Learning Machines

13 Algebraic Geometry of Learning Machines
2. Main Result 系：対数周辺尤度 確率的複雑さ n i=1 - log ∫Π p(Xi|w) φ(w) dw モデルの 複雑さ = - Σ log q(Xi) + λlog n – (m-1)loglog n - log Z* n i=1 E[ log Z* ] < ∞ n ±n½ log n loglog n 定数 2019/2/16 Algebraic Geometry of Learning Machines

14 Algebraic Geometry of Learning Machines
2. Main Result 系：汎化誤差 G(n) = λ/ n + o(λ/n) 汎化誤差 真の分布 から 学習結果 までの距離 学習例数 2019/2/16 Algebraic Geometry of Learning Machines

15 Algebraic Geometry of Learning Machines
3. Proof 対数尤度比のふるまい 対数尤度比 カルバック情報量 Hn(w) = n K (w) + {nK(w)}1/2 σn(w) σn(w) = Σ 1 n i=1 f（Xi,w) - K(w) K(w)1/2 → σ(w) ? K(w)=0の特異点上で ill-defined 各 w 毎に正規分布に収束 2019/2/16 Algebraic Geometry of Learning Machines

16 Algebraic Geometry of Learning Machines
3. Proof 特異点の問題 Z (Dn)　= ∫ dwφ(w) e －Hn(w) = ∫φ(w) dw ∫dtδ(t-K(w)) e －nt －(nt)½σn(w) = ∫φ(w) dw ∫ δ( K(w)) e －t －t½σn(w) dt n t ② ill-defined ① δ(K(w)) は定義されない 2019/2/16 Algebraic Geometry of Learning Machines

17 Algebraic Geometry of Learning Machines
3. Proof 特異点解消定理 広中(1964) Atiyah(1970) A(g(u))= u1s1 u2s2 ・・・ udsd A(w) 実解析関数 g U locally U0 正規交差点 実多様体 W W0 プロパーな 実解析関数 φ(w) φ(g(u)) |g’(u)| 2019/2/16 Algebraic Geometry of Learning Machines

18 Algebraic Geometry of Learning Machines
3. Proof 周辺尤度の分解 L j=1 A(w)≡K(w) Π aj(w) U に特異点解消定理を適用 U0 Z (Dn)　= Σ∫ du ψ(u) e －Hn(u) Uα Uα＝[0,a]d = Σ ∫ψ (u) du ∫ δ( K(u)) e －t －t½σn(u) dt n t Uα 2019/2/16 Algebraic Geometry of Learning Machines

19 Algebraic Geometry of Learning Machines
3. Proof 座標 u の分離 u = (ua,ub) K1(ua) = u12s1 u22s2 ・・・ um2sm K(u) = K1(ua) K2(ub) K2(ub) = um+12sm+1 ・・・ ud2sd ψ(u) = c(u)ψ1(ua)ψ2(ub) ψ1(ua) = u1k1 u2k2 ・・・ umkm ψ2(ub) = um+1km+1 ・・・ udkd s.t. k1+1 2s1 k2+1 2s2 = =・・・= km+1 2sm < km+1+1 2sm+1 ζ(z) の極 =λ 2019/2/16 Algebraic Geometry of Learning Machines

20 Algebraic Geometry of Learning Machines
3. Proof δ(t-K(u)) の性質 任意のC1関数 S(u) (u∈[0,a]d ) について I(t) = ∫δ(t – K(u))ψ(u) S(u) du I0(t) = c0 tλ-1 (-log t)m-1 ∫K2(uｂ)-λ ψ2(uｂ) S(0, uｂ ) duｂ |I(t)-I0(t)| ≦ tλ-1 (-log t)m-2 ||S|| ||S||={ max |S(u)| + Σmax |∂ｊS(u)| } 補題 2019/2/16 Algebraic Geometry of Learning Machines

21 Algebraic Geometry of Learning Machines
3. Proof L2(q)値解析関数のイデアル 補題 f(x,u) = a(x,u) u1s1 ・・ udsd J j=1 f(x,u) = Σ gj(u) hj(x,u) L2(q)解析 解析関数 L2(q)解析 (hj(u),hk(u))>I K(u) = u12s1 u22s2 ・・・ ud2sd = ∫{f(x,u)+e-f(x,u) -1} q(x) dx 2019/2/16 Algebraic Geometry of Learning Machines

22 Algebraic Geometry of Learning Machines
3. Proof 経験過程の法則収束 n i=1 1 n σn(u) = Σ a（Xi,u) - u1s1 ・・ udsd → σ(u) 正規確率過程 ※経験過程の法則収束 L∞(U)　=　{ f(u) ; ||f(u)||<∞ }　 ||f|| = ess. sup |f(u)| u ∈U σn(u) → σ(u) L∞(U)上の任意の有界連続関数 F について EDn[ F(σn)]→Eσ[F(σ)] 定義 2019/2/16 Algebraic Geometry of Learning Machines

23 Algebraic Geometry of Learning Machines
3. Proof 周辺尤度の法則収束 　Σ∫dt c0 tλ-1 (-log t)m-1 ×∫duｂ K2(uｂ)-λ ψ2(uｂ) e －t －t½σ(ub) Uα 証明終 L∞(U)上のσの連続関数 nλ Z (Dn) (log n) m-1 n →∞ 2019/2/16 Algebraic Geometry of Learning Machines

24 Algebraic Geometry of Learning Machines
4. From the Statistical Point of View 統計的推測と特異点 １．特異点を扱うための数理 ２次形式 テーラー展開 中心極限定理 特異点解消定理 イデアル有限生成 経験過程 ２．特異点が統計的推測に及ぼす影響 特異点と真の分布が一致しない場合 最尤法、MAP法 2019/2/16 Algebraic Geometry of Learning Machines

25 Algebraic Geometry of Learning Machines
4. From the Statistical Point of View 学習係数λ det I(w*)＞0, φ(w)>0ならば 　　　λ=d/2 (d: wの次元) (2) det I(w*)=0,φ(w)>0 ならば 　　　λ<< d/2 (３) φ(w): ジェフリーズならば 　　　λ≧ d/2 パラメータ空間 2019/2/16 Algebraic Geometry of Learning Machines

26 Algebraic Geometry of Learning Machines
4. From the Statistical Point of View 具体的なモデルについて ブローアップ　⇒　ζ(z) の極　⇒　λの上限値 　　神経回路網　 （Watanabe,2001) 混合正規分布 (Yamazaki&Watanabe,2002) 　　ベイズネットワーク (Rusakov&Geiger,2002) 縮小ランク回帰 (Watanabe&Watanabe,2002) 2019/2/16 Algebraic Geometry of Learning Machines

27 Algebraic Geometry of Learning Machines
4. From the Statistical Point of View 真の分布がモデルの外？にあるとき n:学習例数 G(n) 小さい モデル 大きな 真の分布 パラメータ空間 2019/2/16 Algebraic Geometry of Learning Machines

28 Algebraic Geometry of Learning Machines
4. From the Statistical Point of View モデルが変化する場所 G(n) ここでは何が起こっているか？ n:学習例数 2019/2/16 Algebraic Geometry of Learning Machines

29 Algebraic Geometry of Learning Machines
4. From the Statistical Point of View 相転移点の解析 エネルギー　対　エントロピー　 関数近似誤差　対　統計的推測誤差 D (特異点|| 真の分布) = c/n モデルの選択・検定 2019/2/16 Algebraic Geometry of Learning Machines

30 Algebraic Geometry of Learning Machines
4. From the Statistical Point of View 具体例 真 b=0 特異点 : {(a,b):a=0 or b=0} Kullback = |a*|2|b*|2/n 真: q(y|x) = 1 2π exp[ (y – 　a* ∑ bｊ* ej(x) )2 ] 2 n N j=1 x ∈RN, y ∈R1 例題 推測 a ∈R1 , b ∈RN N j=1 1 2π 1 2 exp[ (y – a∑ bｊ ej(x) )2 ] 学習者: p(y|x,a,b) = 2019/2/16 Algebraic Geometry of Learning Machines

31 Algebraic Geometry of Learning Machines
4. From the Statistical Point of View 汎化誤差と学習誤差 G(n) ＝ λ/ 2n + o(1/n) , T(n) ＝ μ/ 2n + o(1/n) , ここで λ= 1 + Eg[ (a*2 b*2+a*b*・g)YN(g)/YN-2(g)] μ = λ–2N+ Eg[ (2a* b*・g+2g2) YN(g)/YN-2(g)] YN(g)=∫0π/2 sinN t exp(-|a*b*+g|2 sin2t /2) dt g ～ N次元の標準正規分布 2019/2/16 Algebraic Geometry of Learning Machines

32 Algebraic Geometry of Learning Machines
4. From the Statistical Point of View 漸近展開 |a*| |b*|→∞ のとき λ(a*,b*) = N - (N-1)(N-3) / |a*|2 |b*|2, μ(a*,b*) = - N + (N-1)2 / |a*|2 |b* |2. N　: b の次元 (N-1)(N-3), (N-1)2 : 特異点の指標？ 2019/2/16 Algebraic Geometry of Learning Machines

33 Algebraic Geometry of Learning Machines
4. From the Statistical Point of View 対応する正則モデル 真: q(y|x) = 同じ N j=1 1 2π 1 2 exp[ (y – a∑ bｊ ej(x) )2 ] 学習者: p(y|x,b) = G(n) = N/2n +o(1/n) 真の場所に依存しない T(n) = - N/2n +o(1/n) 2019/2/16 Algebraic Geometry of Learning Machines

34 Algebraic Geometry of Learning Machines
5. Conclusion 結論 (1) 学習理論と特異点 数学的な方法 (2) 統計的推測における特異点の影響 統計学的な意味 2019/2/16 Algebraic Geometry of Learning Machines