IBIS2022チュートリアル 統計的学習理論入門

Transcript

1. 汎化誤差解析から始める 統計的学習理論⼊⾨ 宮⼝航平（IBM東京基礎研究所） IBIS2022 チュートリアル 2022/11/23
2. 本チュートリアルのねらい 理論の学び始めにありがち（︖）な悩み • トピック・分量が多すぎて全体像が掴めない • 具体的にどう使うのかピンとこない • 理論と現実は違うのでは︖ Ø 統計的学習理論/汎化誤差解析について学び始めに知っておくとよいと（個⼈的に）思うことを紹介 0. （なぜ学ぶと良いのか︖） 1. どのような枠組みで成り⽴っているのか︖ 2. どのように使えるのか︖ 3. どのような拡張が⾏われつつあるのか︖ 3
3. 機械学習を問題解決の⼿段として捉える Ø まずスコープを理解することが重要︓どんな条件下で何が出来る/出来ない技術なのか︖ Ø 学習理論は機械学習のスコープについてわかっていることの集積 なぜ学習理論を学ぶとよい（と思う）のか 4 できること できないこと 出来ると わかっている 例）汎化誤差上界 • ERM推定量の上界 • 平滑化推定量の上界 • Boosting推定量の上界 … 出来ないと わかっている 例）汎化誤差下界 • No-free-lunch 定理 • ミニマックス下界 … 未知の領域 （研究の前線） 機械学習のすべてのフェーズ（基礎/応⽤研究・実践）で重要
4. アジェンダ 統計的学習理論/汎化誤差解析は… 1. どのような枠組みで成り⽴っているのか︖ 2. どのように使えるのか︖ 3. どのような拡張が⾏われつつあるのか︖ 5
5. Part 1: 統計的学習理論/汎化誤差解析の基本的な考え⽅ 6
6. 統計的学習理論 • 「有限個のサンプルから背後の分布について推定する（仮説を得る）⾏為」を調べたい（統計成分） • 特に予測・⽣成などなんらかのタスクに対する最適解についての推定に興味がある（学習成分） 7 分布 ! 仮説 "! サンプル #! = #" "#$ ! • 予測器 • ⽣成器 • … 仮説の良さ
7. 汎化誤差解析 最も単純な設定を考える • サンプルは i.i.d. • 仮説の良さは「期待リスク」で定量化︓ 8 ! " ≔ $ !∼# ℓ ", ' 損失関数 • 予測 → ⼆乗誤差 ℓ ", ' = ( − " * % • ⽣成 → 対数尤度 ℓ ", ' = − ln ! ' " 分布 ! 仮説 "! サンプル #! ∼ !! 期待リスク . "
8. 汎化誤差解析のゴール (1/3) 9 考えうる範囲内で (ほぼ) 最もよい仮説を得たい︓ 仮説空間 ℱ&'' (考えうる全ての仮説の集合) 未知分布 ! サンプル #! 推定量 $! 最適 $ ∗∗ (期待リスク最⼩) Q. どんな推定量なら汎化 (汎化誤差→0) するか︖その速さは︖ 抑えたい量(汎化誤差) . "! − . "∗∗
9. 汎化誤差解析のゴール (2/3) 10 とはいえ考えうる全ての仮説を探索するのは荷が重いし，多くの場合無意味︓ 「ある程度 ℱ#$$ が⼤きければ，全ての !∗∗ に対して平等に汎化する推定量は存在しない 」 （no-free-lunch定理） Ø 推定量 " " の範囲を適当な 仮説集合 & に限定 Ø このとき汎化誤差は２つに分解される （“近似-推定誤差分解”） 出⼒ "! 最適 "∗∗ 仮説集合 ℱ 近似誤差 推定誤差 モデル内最適 !∗
10. 汎化誤差解析のゴール (3/3) 式で書くと︓ Ø ⼆つの誤差が共に⼩さくないと汎化しないのでどちらも重要．ただし︓ • 推定量 " " に依存するのは推定誤差だけなので推定誤差単体の評価にも意味がある • 近似誤差を含む評価には別途 "∗∗ に関する仮定が必要 (no-free-lunch定理) 11 本チュートリアルでは近似誤差は無視できると仮定 → 推定誤差を⼩さくする推定量とは︖ ! " ' − ! "∗∗ = ! " ' − ! "∗ + ! "∗ − ! "∗∗ 近似誤差 (≥ 0) 推定誤差 (≥ 0) 汎化誤差 モデル内最適
11. ⾃然な推定量︓経験リスク最⼩化 (ERM) 推定量 期待リスク # " を最⼩化したいが，# " は未知 → 代わりにそのサンプル近似として経験リスクを最⼩化︓ • シンプルかつ応⽤上も成功している推定量のクラス • 正則化付きERM (RERM) などの拡張もERMの延⻑線上で扱える 12 ERMの推定誤差 . "! − . "∗ を調べたい " ' ≔ argmin )∈ℱ ! ' " 経験リスク︓ "3 ! ≔ 1 % & 456 3 ℓ !, )4
12. ERM !! 最適 !∗ # $∗ # $" 解析の鍵 扱いにくい argmin を消去する︓ Ø 実はタイト（定数倍を除き追加の仮定なしには改善不可能） 13 Δ" $" 推定誤差のかわりに⼀様収束誤差を評価すれば良さそう ! " ' − ! "∗ ≤ 2 sup )∈ℱ Δ ' " ERMの推定誤差 .! の⼀様収束誤差 Δ! $ ≔ - $ − -! $ 期待リスク 経験リスク ⼀様収束誤差 −Δ" $∗ #" $" − #" $∗ ≤ 0
13. ここまでのまとめ 基本的な前提を導⼊した • 解析の枠組み︓仮説集合と誤差分解 • ⾃然な推定量︓経験リスク最⼩化 (ERM) • 解析の鍵︓⼀様収束誤差 Ø 次︓⼀様収束誤差を評価するための素朴な⽅法 14 ⼀様収束誤差 推定誤差 ERMの汎化誤差 近似誤差 これを抑えたい
14. 基本⽅針 ⼀様収束誤差の評価 → 確率過程の最⼤値の評価 Ø 確率過程論の⻑い歴史 (1940年代~) の中でさまざまな道具が作られてきた Ø まずはもっとも素朴な状況からはじめて，段階的に拡張してみる 15 仮説 ! Δ! $ sup %∈ℱ Δ! $
15. 最も素朴な場合︓有限仮説集合 (1/3) 独⽴とは限らない $ = & 個の確率変数の max の評価に相当︓ Ø 率直な⽅法︓個々の確率変数は中⼼極限定理に従うので 2( 3)*/, → それらの max も 7) 8*$/% 16 sup )∈ℱ Δ ' " = max 45657 Δ ' "6 Δ3 !9 = 1 % & 456 3 ℓ !9, )4 − " !9 = -: %;6/= これだと > に関する依存性がわからない ! （後々 > → ∞ としたいので困る） !# !$ !%
16. 最も素朴な場合︓有限仮説集合 (2/3) ' に関する依存性を調べたい場合は個々の確率変数の裾の軽さが重要︓ Ø 例）損失関数が (-有界ならば Δ" " は *)/,-劣ガウスなので 17 裾の性質 （独⽴とは限らない）> 個の max の⼤きさ A%-劣ガウス 2( 8 ln ; B, C -劣ガンマ 2( < ln ; + > ln ; max 6D9DE Δ3 !9 = max 6D9DE ±Δ3 !9 = -: 2 ln 5 % 2# 個の max 基本はこっち 「速い」レートを出すときに使う !# !$ !%
17. 最も素朴な場合︓有限仮説集合 (3/3) 結局，適当な条件のもとで Ø 仮説集合が有限なら基本的にサンプル数と log(仮説数) のバランスで⼀様収束誤差を抑えられる Ø より⼀般に裾の軽さを⽰すには集中不等式 (Hoeffding, Bernstein, Azuma, …) を使う 18 sup )∈ℱ Δ ' " = 8 ? ln ℱ ; !# !$ !%
18. 拡張︓距離構造の⼊った⼀般の仮説集合 簡単のため損失関数がリプシッツ連続になるような 距離が⼊っていると仮定︓ → 有限個の代表点で近似してみる︓ 例）--次元有界集合は . /*+ 点 で近似可能︓ 19 ⋯ ⋯ ⋯ 半径 $ 仮説集合 ℱ F-カバリング ̈ ℱ F sup H∈ℱ Δ3 ! = -: JK L,- 3 + - : カバリング上の⼀様収束誤差 近似誤差 . ← 0 1#$/& = -: M JK 3 3 ℓ $, C − ℓ $- , C ≤ $ − $- 収束速度にこだわらなければこれだけでも実⽤的 （1-ステップ離散化と呼ばれる）
19. Part 1 まとめ 汎化誤差解析の基本的な考え⽅ • 問い︓⼀様収束の条件・速さとは︖ • ⽅法︓確率過程の理論 • 素朴な答え︓サンプル数と log(仮説数) のバランスで決まる • 必要なら離散化してから仮説をカウントする Ø Part 2 では実践的な汎化誤差解析の使われ⽅を紹介 20 ⼀様収束誤差 1-ステップ離散化 推定誤差 ERMの汎化誤差 近似誤差 抑えたい
20. Part 2: 実践的な汎化誤差解析の道具 21
21. 1-ステップ離散化の問題点 1. 誤差評価が⽢い • 0-次元パラメトリックモデルの場合︓ 2( . $/ ! ! • 収束レートの最適性を⽰す時などに不都合 2. 取り回しがよくない • 仮説集合や損失関数ごとに /-カバリングや / の調整を考え直すのは⾯倒 22 実は不要
22. なぜ誤差評価が⽢いのか 仮説空間の連続性をフルに使えていない → 異なる解像度を組合わせて段階的に近似 23 F = 1/2 F = 1 F = 1/8 F = 1/4 代表点の親⼦関係で近さの情報を捉えられる ⋯ ⋯ ⋯ 代表点同⼠の近さの情報を無視していた $-カバリング ̈ ℱ $
23. より洗練された⽅法 (1/2) 近似誤差を⼀段ごとに評価する︓ 24 = -: :6 JK ̈ ℱ L2 3 F$ -カバリング (親) E $ $ F% -カバリング (子) ≤ sup H∈ ̈ ℱ L2 Δ3 ! − Δ3 < ! ($# /()-劣ガウス確率変数 有限集合上の 確率過程の最⼤値 = sup H∈ ̈ ℱ L2 Δ3 ! − sup H∈ ̈ ℱ L3 Δ3 ! (近似誤差) = sup H∈ ̈ ℱ L2 Δ3 ! − sup H∈ ̈ ℱ L2 Δ3 < ! F% が⼩さい時は F$ も⼩さいので 解像度を細かくした時の log (仮説数) の爆発の寄与を減衰 できている
24. より洗練された⽅法 (2/2) 全ての解像度 /4 ≔ 2*4 に対して再帰的に近似を連鎖させると， Ø サンプル数と log(仮説数) の重み付き平均 のバランスが⼤事（重み ∝ 解像度） Ø チェイニング [Dudley 1967] と呼ばれる基礎テクニック 25 sup H∈ℱ Δ3 ! = -: & R5S T 2;R ln ̈ ℱ 2;R % □
25. 1-ステップ離散化との⽐較 例）ℱ が 0-次元有界集合のとき︓ ̈ ℱ G = 2 G). だったので， ただし基本的な気持ちは同じ︓ 1. “うまく” 配置された代表点の数で仮説集合の⼤きさを測る（↑の例では 次元 - ） 2. 仮説集合の⼤きさとサンプル数のバランスが⼀様収束誤差の評価につながる 26 sup H∈ℱ Δ3 ! = -: & R56 U 2;R ln 2;R ;M % = -: @ % 追加の仮定なしに ln 8 が取れた
26. 取り回しの良い⽅法 • 問題設定ごとにうまい点の配置を考え直して仮説集合の⼤きさを計算するのは⼿間 • 再利⽤可能性を⾼めたい．ただしタイトさを犠牲にせずに… Ø 様々な「仮説集合の⼤きさの尺度」が開発されてきた︓ • ここまで解説してきた点の配置を利⽤する尺度はメトリックエントロピーと呼ばれる • 他にも VC次元，ラデマッハ複雑度などいろいろある 27 今回は取り回しの良い尺度のひとつとしてラデマッハ複雑度を取り上げる
27. ラデマッハ複雑度 関数集合の⼤きさを測る尺度︓ • 「ランダムラベル 45 を割り振られた各データ 55 にフィットして，どれぐらい sup を⼤きくできるか」 • 6 が⼤きいほどそのラデマッハ複雑度も⼤きくなる 28 ℜ ' > ≔ $ sup I∈J 1 ; @ KL4 ' A K B ' K ラデマッハ確率変数 A" ∼ Uniform ±1 関数 ' ↦ ^ ' ∈ ℝ の集合
28. ラデマッハ複雑度の性質 1. 等価性︓損失関数が有界ならば， 2. 合成則 • ミンコフスキー和︓ • 関数合成︓ • … Ø ⼀様収束誤差を過不⾜なくかつシステマティックに評価可能 Ø 汎化誤差解析でもっとも広く使われる道具のひとつ 29 1 2 sup )∈ℱ Δ ' " − 8 ? 1 ; ≤ ℜ ' ℓ ℱ ≤ 2 sup )∈ℱ Δ ' " + 8 ? 1 ; 部分適⽤された損失関数 ℓ ",⋅ , " ∈ ℱ の集合 ℜ3 B6 + B= = ℜ3 B6 + ℜ3 B6 ℜ3 C ∘ B ≤ Lip C ⋅ ℜ3 B
29. 使⽤例 教師あり学習 ℓ ", 9 ≔ : " ; , < の場合︓ • : = <, < が有界かつ第⼀引数に対してG-リプシッツ連続ならば， • さらに仮説集合 ℱ を規格化された再⽣核ヒルベルト空間 (RKHS) の有界部分集合とすると， 30 sup )∈ℱ Δ ' " ≤ 2ℜ ' C ∘ ℱ + 8 ? 4 ' ≤ 2Eℜ ' ℱ + 8 ? 4 ' 等価性 合成則 (関数合成) ℜ ' ℱ ≤ ℜ ' ℬ 6 G ≤ G ; RKHSノルム ) 以下の集合 単調性 既知の結果 適当な仮定のもと • ヒンジロス • ロジスティックロス • ⼆乗ロス • … • 線形予測器 • カーネル法 • NNの極限 (NTK)
30. 発展︓実質的な仮説集合の⼤きさを測る 仮説集合の中に冗⻑な領域があるかもしれない︓ → 局所ラデマッハ複雑度で 仮説集合の「使われる」領域の⼤きさのみを測る → 条件が揃えば収束速度の加速が可能︓ • 損失関数が強凸（⼆乗誤差回帰） • 低ノイズ条件（分離可能な分類） 31 最適仮説 !∗ 推定量 !! 仮説集合 ℱ 実質的な仮説集合 ℱ∗ ある程度学習が進んでいれば 最適仮説から遠い仮説は ほとんど使われないのでは︖ ℜ3 Jab B; I ≔ J sup c∈d c De 1 % & 456 3 K4L )4 仮説集合を⼯夫した上で ⼀様収束の議論に帰着
31. Part 2 まとめ ⼀様収束誤差の評価のための実践的な⽅法（の⼀部）を紹介した • 基本テクニック︓チェイニング • 便利な尺度︓ラデマッハ複雑度 32 ⼀様収束誤差 ラデマッハ複雑度 チェイニング 推定誤差 (合成則) 汎化誤差 近似誤差 抑えたい
32. Part 1-2 のおさらい 33 Q. サンプルから背後の分布に関する「よい」仮説を得るには︖ A. 損失関数 ℓ と仮説集合 & を⽤意してERMを実⾏するとよい → 「仮説集合の⼤きさ M ≪ サンプル数 ? 」ならば汎化︓ ! " ' ≤ min )∈ℱ ! " + 8 ? H ; さまざまな尺度︓ • メトリックエントロピー (離散化) • メトリックエントロピー (チェイニング) • ラデマッハ複雑度 • …
33. Part 3: 「ERM＋⼀様収束」を超えた汎化誤差解析 34
34. 紹介する話 「ERM + ⼀様収束」では説明がつかない現象たち︓ 1. あえてノイズを加えるとうまくいく現象（ERMでない） 2. あえて過剰適合させるとうまくいく現象（⼀様収束しない） 35
35. ノイズを利⽤する推定量 応⽤上あえてノイズを加える操作が⾏われ，それがうまく働く場合がある • 確率的勾配降下法 (SGD) vs 勾配降下法 (GD) • NNの初期化・ドロップアウト • バギング … Ø 最終的な推定量 " " にもノイズが乗るはずだが，そのご利益とは…︖ 36 仮説集合 推定量の分布
36. PAC-Bayes 不等式 任意の “事前分布” @ と “事後分布” A" に対して， Ø 事後分布の期待リスクは 経験リスク＋事前分布に対する(擬)距離 で抑えられる Ø 「ノイズを加える≒事前分布に近づく」なのでERMにノイズを加えることの根拠を与える 37 仮説 事後分布 *! 事前分布 + ! "! ≤ !! "! + % &" #$ %B‖' ! 期待値の略記
37. PAC-Bayes 解析のアイデア ⽬標︓⾮⾃明な関数-引数相関の評価 ⽅法１︓⼀様収束誤差による解析 引数に関して最悪ケースを評価︓ Ø ノイズの効果が消えてしまう! ⽅法２︓PAC-Bayes解析 Ø 関数と引数を分離して個別に評価 38 " M3 ≤ "3 M3 + (ノイズの効果) Δ3 M3 ≤ (ノイズの効果) 関数と引数が共に ⾮⾃明な形でサンプル依存 Δ3 M3 ≤ sup H∈ℱ Δ3 !
38. 導出（スケッチ） 1. Change-of-measure 不等式 [Donsker,Varadhan 75] で関数と引数を分離︓ 2. 集中不等式を使って関数側を上から評価︓ 例）損失関数が有界ならば fΔ! " は 7 f%/8 -劣ガウス なので， Ø ノイズの効果を残したまま評価できた︓ 39 Δ3 M3 ≤ 1 N KL M3‖< + 1 N ln J H∼h Qij6 H 1 N ln J H∼h Qij6 H = -: N % □ Δ3 M3 ≤ 1 N KL M3‖< + -: N % 最後にハイパーパラメタ , を 調整すれば完成︕
39. PAC-Bayes不等式︓まとめ 確率的なアルゴリズムにおけるノイズの役割を (少なくとも⼀部は) 説明可能 特徴１︓関数引数分離 + 個別評価 を原則とする⾼い拡張性 • 関数引数分離 → 任意の凸共役ペア︓ Δ" , A" ≤ ℎ Δ" + ℎ∗ A" • 個別評価 → ℎ Δ" が評価できる任意の集中不等式（⾮有界なロス，⾮i.i.d.なデータ，etc.） 特徴２︓（オーダーではなく）数値の上で⽐較的タイトな上界が得られることが多い • 直観的には証明全体で不等式評価が２回と少ないため • PAC-Bayes不等式を直接最⼩化するアルゴリズムの研究も盛ん [Guedj 19 (Sec.5)] 40
40. 紹介する話 「ERM + ⼀様収束」では説明がつかない現象たち︓ 1. あえてノイズを加えるとうまくいく現象（ERMでない） 2. あえて過剰適合させるとうまくいく現象（⼀様収束しない） 41
41. Overparameterized な推定量 • 深層学習などでは「⼤きなモデルほど性能がよい」という経験知がある • 象徴的な現象︓⼆重降下 (double descent) [Belkin+19a, Nakkiran+20] 42 [Belkin+19a] 従来の「k ≪ 8」型の理論では説明できない ⼤きければ⼤きいほど良い
42. 何が問題か︖（汎化誤差解析の視点） 経験リスクが0 (完全フィット) となり，期待リスクとの間に縮めようがない差が⽣じている︓ Ø つまり深層学習は⼀様収束しないのに汎化性能◦ Ø （⼀⽅，従来の推定量は⼀様収束するのに汎化性能△） 43 従来理論では説明できない “無害な過適合 (benign overfitting, BO)” が存在 （深層学習成功の鍵かもしれない） 完全フィットする推定量 期待リスク 経験リスク 機械学習タスクの ノイズレベル 従来の推定量
43. 理論的理解に向けての試み Q. どんな設定ならBOが可能なのか︖ A. 標準的な回帰/分類問題ならいつでも可能 → 直観的な仕組み︓ Q. 深層学習 (DNN+SGD) でのBOの仕組みとは︖ A. 徐々に理解が進みつつある • 線形モデル+GD (回帰,分類) • 2-layer NN+GD (分類) … 44 [Belkin21] # -, -& = - − -& '( による カーネル平滑化推定量 → 弱い条件下で常にBOを達成 " ' = " ' ∘ + " ' ⋏ 真の仮説 !∗ に近づく 滑らかな成分 ノイズに引きずられるが 期待リスクの意味で無害な 尖った成分 [Belkin+18,19b] ⽂献多数 , 例えば [Frei+22] から辿れる
44. まとめ 1. 基本的に⼀様収束誤差を抑えることに関⼼がある 2. そのためのツールとしてチェイニング・ラデマッハ複雑度が便利 3. 基本の枠組みを超えた現象のための研究も盛ん︓ • ノイズ → PAC-Bayes 理論 • 過剰適合 → Benign overfitting の理論 • … 45 ⼀様収束誤差 ラデマッハ複雑度 チェイニング 推定誤差 汎化誤差 近似誤差 PAC-Bayes Benign overfitting
45. 参考⽂献 (全体) Part 1-2 : • ⾦森敬⽂. (2015). 統計的学習理論. 講談社. • Shalev-Shwartz, S., & Ben-David, S. (2014). Understanding machine learning: From theory to algorithms. Cambridge university press. • Wainwright, M. J. (2019). High-dimensional statistics: A non-asymptotic viewpoint (Vol. 48). Cambridge University Press. Part 3 - PAC-Bayes不等式︓ • Laviolette, F. (2017, December). A tutorial on PAC-Bayesian theory. In Talk at the NIPS 2017 Workshop. (スライド) • Guedj, B. (2019). A primer on PAC-Bayesian learning. arXiv preprint arXiv:1901.05353. Part 3 - Benign overfitting︓ • Bartlett, P. L., Montanari, A., & Rakhlin, A. (2021). Deep learning: a statistical viewpoint. Acta numerica, 30, 87-201. • Belkin, M. (2021). Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation. Acta Numerica, 30, 203-248. 46
46. 参考⽂献 (個別) • Dudley, R. M. (1967). The sizes of compact subsets of Hilbert space and continuity of Gaussian processes. Journal of Functional Analysis, 1(3), 290-330. • Frei, S., Chatterji, N. S., & Bartlett, P. (2022, June). Benign overfitting without linearity: Neural network classifiers trained by gradient descent for noisy linear data. In Conference on Learning Theory (pp. 2668-2703). PMLR. • Nakkiran, P., Kaplun, G., Bansal, Y., Yang, T., Barak, B., & Sutskever, I. (2021). Deep double descent: Where bigger models and more data hurt. Journal of Statistical Mechanics: Theory and Experiment, 2021(12), 124003. 47 • Belkin, M., Hsu, D. J., & Mitra, P. (2018). Overfitting or perfect fitting? risk bounds for classification and regression rules that interpolate. Advances in neural information processing systems, 31. • Belkin, M., Hsu, D., Ma, S., & Mandal, S. (2019a). Reconciling modern machine-learning practice and the classical bias–variance trade-off. Proceedings of the National Academy of Sciences, 116(32), 15849-15854. • Belkin, M., Rakhlin, A., & Tsybakov, A. B. (2019b). Does data interpolation contradict statistical optimality?. In The 22nd International Conference on Artificial Intelligence and Statistics (pp. 1611-1619). PMLR. • Donsker, M. D., & Varadhan, S. S. (1983). Asymptotic evaluation of certain Markov process expectations for large time. IV. Communications on Pure and Applied Mathematics, 36(2), 183-212.
47. 定数倍をのぞきタイト︖ 以下を満たすような問題が作れてしまう︓ イメージ︓ 49 J " !3 − " !∗ ≥ SJ sup H∈ℱ Δ3 ! 最適 "∗ ERM "! 期待リスク . "
48. 期待値に対する凸共役なペアの作例 1. 期待値 = 内積と捉える︓ 2. 凸共役な関数のペアをとりだす︓ PQ ≤ ℎ P + ℎ ∗ Q 3. 積分の中⾝に適⽤する︓ 50 Δ ' I ' = J Δ ' " ⋅ dI ' dM " dM " Δ ' I ' ≤ Jℎ Δ ' " dM " + J ℎ∗ dI ' dM " dM "