統計的学習理論２

PAC-Bayes

Foundation
Author

司馬 博文

Published

3/02/2024

Modified

3/06/2024

概要
PAC-Bayes は現実的に有用な鋭い PAC bound を得る新たな技術である．最適化の問題に帰着する点が研究を盛り上げている．Vapnik-Chervonenkis 理論の一般化であり，推定量上の確率分布を返すようなより一般的なアルゴリズムに対しても適用できる．

1 PAC-Bayes

通常の機械学習の枠組みでは，仮説集合 \(\mathcal{H}\subset\mathcal{L}(\mathcal{X};\mathcal{Y})\) を固定し，この中で最適な推定量 \(\overline{h}\in\mathcal{H}\) を探すことに集中する．

一方で，PAC-Bayes では，仮説集合 \(\mathcal{H}\) 上の確率分布を学習し，最終的に投票 (vote) などの確率的な操作によって決めることを考え，これにも対応する理論を構築する．1

これは (Shawe-Taylor and Williamson, 1997) によって創始され， (McAllester, 1999) によって最初の定理が示された．(Seeger, 2002), (Catoni, 2007) も金字塔であり，後者は情報統計力学との関連を推し進めている．

1.1 枠組み

データにより決まる確率測度 \[ \widehat{\rho}:(\mathcal{X}\times\mathcal{Y})^n\to\mathcal{P}(\mathcal{H}) \] を考え，推定量をランダムに \(\widetilde{h}\sim\widehat{\rho}\) とサンプリングする．これを ランダム推定量 (randomized estimator) という．

例えば \(\mathcal{Y}=2\) においては，Gibbs 判別器と呼ばれる．2

また，最終的な推定量を積分により \[ h_{\widehat{\rho}}:=(\widehat{\rho}|h) \] と決定しても良い．これを 集合推定量 (aggregated predictor) という．

これらの

  • 経験バウンド (empirical bound)：\(R(\widehat{h})-\widehat{R}_n(h^*)\)
  • 超過リスクバウンド (excess risk / oracle PAC bound)：\(R(h_{\widehat{\rho}})-R(h^*)\)

を調べるのが PAC-Bayes である．

1.2 KL-乖離度

すると，\(\log M\) の項に KL-乖離度が現れる．

Tip

定義 1 (Kullback-Leibler divergence) \(\mu,\nu\in\mathcal{P}(\mathcal{H})\) の Kullback-Leibler 乖離度 とは， \[ \operatorname{KL}(\mu|\nu):=\begin{cases} \int_\mathcal{H}\log\left(\frac{d \mu}{d \nu}(\theta)\right)\mu(d\theta)&\mu\ll\nu,\\ \infty&\mathrm{otherwise}. \end{cases} \] をいう．

1.3 McAllester バウンド

1.3.1 応用

SGD で訓練されたニューラルネットワークに対しても適用されている (Clerico et al., 2023)．

PAC-Bayes による汎化バウンド (Dziugaite and Roy, 2017)

事後分布からサンプリングをすることで鋭い評価を得ている (Ujváry et al., 2023)．

References

Alquier, P. (2024). User-friendly introduction to PAC-bayes bounds. Foundations and Trends in Machine Learning, 17(2), 174–303.
Catoni, O. (2007). PAC-bayesian supervised classification: The thermodynamics of statistical learning,Vol. 56. Institute of Mathematical Statistics.
Clerico, E., Farghly, T., Deligiannidis, G., Guedj, B., and Doucet, A. (2023). Generalisation under gradient descent via deterministic PAC-bayes.
Dziugaite, G. K., and Roy, D. M. (2017). Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data.
McAllester, D. A. (1999). Some PAC-bayesian theorems. Machine Learning, 37, 355–363.
Schölkopf, B., and Smola, A. J. (2002). Learning with kernels: Support vector machines, regularization, optimization, and beyond. MIT Press.
Seeger, M. (2002). PAC-bayesian generalisation error bounds for gaussian process classification. Journal of Machine Learning Research, 3, 233–269.
Shawe-Taylor, J., and Williamson, R. C. (1997). A PAC analysis of a bayesian estimator. In Proceedings of the tenth annual conference on computational learning theory, pages 2–9.
Ujváry, S., Flamich, G., Fortuin, V., and Hernández-Lobato, J. M. (2023). Estimating optimal PAC-bayes bounds with hamiltonian monte carlo. In NeurIPS 2023 workshop on mathematics of modern machine learning.

Footnotes

  1. (Alquier, 2024) Introduction より．↩︎

  2. (Schölkopf and Smola, 2002, p. 381) 定義12.23．↩︎