統計的学習理論２

A Blog Entry on Bayesian Computation by an Applied Mathematician

$$

$$

1 PAC-Bayes

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

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

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

1.1 枠組み

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

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

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

これらの

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

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

1.2 KL-乖離度

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

Tip

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

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．