統計的学習理論３

構造的リスク最小化

Foundation
Author

司馬 博文

Published

3/03/2024

概要
統計的機械学習には，「汎化」に価値を置く，独特の決定理論的な枠組みが存在する．特に，現状では経験リスク最小化と正則化とを組み合わせた「構造的リスク最小化」が最もよく見られる．この枠組みから，各手法の優越を評価することとなる．

1 正則化と汎化の関係

1.1 非一様性1

PAC 学習 の枠組みは，分布 \(\mathbb{P}\in\mathcal{P}(\mathcal{X}\times\mathcal{Y})\) に依らない一様な評価を要請している．

その結果，分類問題でも，PAC 学習可能であるためには仮設集合 \(\mathcal{H}\) には VC 次元の有限性が必要十分となるのであった（統計的機械学習の基本定理）．

これは多くの場合強すぎる．

そこで，必要な訓練データ数が，分布 \(\mathbb{P}\in\mathcal{P}(\mathcal{X}\times\mathcal{Y})\) に依存することも許すことを考える．この緩めた学習可能性は，\(\mathcal{H}\) が有限 VC 次元集合の有限合併であることに同値になる．

nonuniformly learnable2

定義 1 仮説集合 \(\mathcal{H}\subset\mathcal{L}(\mathcal{X};\mathcal{Y})\) が 非一様に学習可能 であるとは，あるアルゴリズム \(A\) とある \(h\in\mathcal{H}\) に依存しても良い関数 \[ m^{\mathrm{NUL}}:(0,1)^2\times\mathcal{H}\to\mathbb{N} \] が存在して，任意の \(\epsilon,\delta\in(0,1)\) と \(h\in\mathcal{H}\) と \(\mathbb{P}\in\mathcal{P}(\mathcal{X}\times\mathcal{Y})\) について，\(m\ge m^{\mathrm{NUL}}(\epsilon,\delta,h)\) ならば確率 \(1-\delta\) 以上で \[ R(A(S_m))\le R(h)+\epsilon \] を満たすことをいう．

論理的な構造は PAC 学習可能性 と非常に似ているが，確かに真に弱い条件になっている．

Characterization of Nonuniform Learnability3

定理 1 分類問題 \(\mathcal{Y}=2\) を 0-1 損失 \(l=1_{\Delta_\mathcal{Y}^\complement}\) で考えるとする．仮説集合 \(\mathcal{H}\subset\mathcal{L}(\mathcal{X};\mathcal{Y})\) について，次は同値：

  1. \(\mathcal{H}\) は非一様に学習可能である．
  2. \(\mathcal{H}\) は有限 VC 次元集合の可算合併で表せる．

1.2 構造的リスク最小化

PAC バウンド の証明からも判る通り，推定誤差と近似誤差のトレードオフが存在する．

すなわち，仮説の複雑性には代償がある．

そこで，仮説集合 \(\mathcal{H}\) を小さくする代わりに，アルゴリズム \(A:(\mathcal{X}\times\mathcal{Y})^n\to\mathcal{H}\) が探索する範囲を小さいものにし，実質的な仮説空間のサイズを抑えることも考えられる．これを 正則化 という．

実際，深層学習も暗黙的正則化によりよい汎化性能を出していることが徐々に明らかになりつつある．4

すなわち，真に汎化性能を上げたい場合は，経験誤差を最小化するだけでは十分ではなく，経験誤差を小さくしながら，関数が滑らかになるように帰納バイアスを入れる必要がある．

この枠組みを経験リスク最小化の代わりに，構造リスク最小化 といい，(Vapnik and Chervonenkis, 1974) により提案された．

この方向の研究の源流は，(Bousquet and Elisseeff, 2002) らの 安定性 の理論であった．これは「実質的な仮説空間」という考え方を導入することで，機械学習モデルの予測精度理論の精緻化も生んだ．

1.3 枠組み：アルゴリズムに目を向ける

リスクを \[ R(A,S):=\operatorname{E}[l(A(S)(X),YT)] \] 経験リスクと \[ \widehat{R}(A,S_n):=\frac{1}{n}\sum_{i=1}^nl(A(S_n)(x_i),y_i) \] として，アルゴリズム \(A:(\mathcal{X}\times\mathcal{Y})^n\to\mathcal{H}\) の関数とみる．5

この場合，仮説空間 \(\mathcal{H}\) 上の一様な評価は，そもそも目指さない．

1.4 安定性

Tip

定義 2 (安定性6) アルゴリズム \(A:(\mathcal{X}\times\mathcal{Y})^n\to\mathcal{H}\) が，損失関数 \(l\) に関して \(\beta\in(0,1)\)-安定 であるとは，任意の \(S\subset(\mathcal{X}\times\mathcal{Y})^n\) に対して， \[ \begin{align*} &\max_{i\in[n]}\operatorname{E}\biggl[\biggl|l(A(S)(x_i),y_i)\\ &\qquad-l(A(S\setminus\{z_i\})(x_i),y_i)\biggr|\biggr]\le\beta \end{align*} \] が成り立つことをいう．

すなわち，学習データを１つ減らしたときの損失の変化が，ある一定以下であることをいう．

これは感度分析的な考え方であるが，実は正則化により，アルゴリズムは安定的な挙動をするようになり，安定性が汎化誤差の上界を与える！

1.5 主結果

Tip

定理 2 (安定なアルゴリズムに対する汎化バウンド7) \(A\) を \(\beta_1\)-安定で，損失関数 \(l\) は上界 \(M>0\) を持つとする．このとき，\(1-\delta\) の確率で \[ R(A,S)\le\widehat{R}(A,S_n)+2\beta+(4n\beta+M)\sqrt{\frac{\log1/\delta}{2n}}. \]

1.6 アルゴリズムの安定性

一方で，アルゴリズムの安定性を示すことは難しく，通常 admissibility と Bregman divergence を通じて議論されるようである．8

References

Bousquet, O., and Elisseeff, A. (2002). Stability and generalization. Journal of Machine Learning Research, 2, 499–526.
Murphy, K. P. (2022). Probabilistic machine learning: An introduction. MIT Press.
Shalev-Shwartz, S., and Ben-David, S. (2014). Understanding machine learning: From theory to algorithms. Cambridge University Press.
Vapnik, V. N., and Chervonenkis, A. Ya. (1974). Teoriya raspoznavaniya obrazov (theory of pattern recognition). Nauka, Moscow.

Footnotes

  1. (Shalev-Shwartz and Ben-David, 2014, p. 58) 第７章 も参照．↩︎

  2. (Shalev-Shwartz and Ben-David, 2014, p. 59) 定義7.1．↩︎

  3. (Shalev-Shwartz and Ben-David, 2014, p. 59) 定理7.2 など．↩︎

  4. (Murphy, 2022, p. 455) も参照．↩︎

  5. (Bousquet and Elisseeff, 2002, p. 502)．↩︎

  6. (Bousquet and Elisseeff, 2002, p. 503)．↩︎

  7. (Bousquet and Elisseeff, 2002, p. 507) Theorem 12．↩︎

  8. (Bousquet and Elisseeff, 2002) 第５節．↩︎