PACベイズの基礎についてまとめる

この記事は古川研究室Advent_calendar 11日目の記事です。

#はじめに

最近PACベイズを使った研究に関心があるのですが，PACベイズについてまとまった日本語の資料があまりないように感じましたので基本的な考え方についてまとめたいと思います．英語の資料としてはBenjamin Guedjさんの論文¹がよくまとまっているので，詳細を知りたい方はぜひそちらを参考にしてください．また，私自身まだモヤモヤしながら書いたものなのであまり鵜呑みにせずに読んでいただけると助かります．

#PACベイズとは

PACベイズについて話す前にまず教師あり学習の枠組みを考えます．つまり，$N$個の入力と出力のペア$S=\{(x_n, y_n)\}^N_{n=1}$が与えられた時に入出力関係$f: \mathbf{x} \mapsto y$を推定する問題を考えます．$h$，$\mathbf{x}$，$y$についての損失関数を$l(h(x),y)$とすると訓練誤差最小化では以下の目的関数$L_S(f)$を最小にするように予測器$h$を推定することを考えます．

L_S(f) := \frac{1}{N}\sum^N_{n=1}l(h(x_n),y_n)

ここで損失関数としては回帰の問題なら二乗損失$l(h(x),y)=(y-h(x))^2$が用いられたり，二値分類ならロジスティック損失$l(h(x),y)=\log(1+\exp(−yh(x)))$などが用いられます．これによって，観測したデータに最も当てはまる予測器を見つけることができます．一方で教師あり学習の本来の目的は将来現れるデータを予測することです．つまり，データセット$S$がある分布$\mathcal{D}$にしたがって生成されたと仮定すると，以下の汎化誤差を最小にする予測器$h$を推定することが本来の目的です．

L(f) := E_{\mathcal{D}}[l(h(x),y)]

しかし，有限のデータセット$S$しか観測することができないため$L(h)$を直接最小化することはできません．そのため，データセット$S$から$L(h)$を最小化する方法や理論的に$L(h)$を評価する方法が研究されており，その中の一つにProbably Approximately Correct (PAC) 学習というものがあります．訓練誤差最小の予測器を$h_S$とするとPAC学習では$h_S$の汎化誤差が$\epsilon$以下である確率が$1-\delta$以上であることを保証することを考えます．これを数式で書くと以下のようになります．

Pr\left( L(h_S) \leq \epsilon \right) \geq 1-\delta

あるいは汎化誤差を最小にする予測器を$h^\ast$とし，訓練誤差を最小にする予測器を$h_S$とすると$|L(h_S)-L(h^\ast)|$が$\epsilon$以下である確率が$1-\delta$以上であることを保証することを考える場合もあります．つまり，

Pr\left( |L(h_S)-L(h^\ast)| \leq \epsilon \right) \geq 1-\delta

です．ここで$\epsilon$は$\delta$やデータセット$S$によって決まる変数です．例えば，クラス分類の問題を考え，汎化誤差の範囲を$0<L(h)<1$とします．また，仮定している$h$の集合を$\mathcal{H}$とし，$\mathcal{H}$は有限集合でその要素数を$|\mathcal{H}|$とします．この時，以下の不等式が成り立ちます²．

Pr\left( |L(h_S)-L(h^\ast)| \leq \epsilon \right) \geq 1-2|\mathcal{H}|\exp(-2N\epsilon^2) \tag{1}

この不等式から様々なことを読み取ることができます．例えば，データ数$N$に対して

N\geq \frac{\log\left(\frac{2|\mathcal{H}|}{\delta}\right)}{2\epsilon^2}

が成り立てば，$|L(h_S)-L(h^\ast)|$が$\epsilon$以下である確率が$1-\delta$以上になることが保証できます．つまり，サンプル数をどのくらい増やすとトレーニング誤差と汎化誤差の差を小さくできるかを見積もれるようになります．また，$|\mathcal{H}|$が大きいほどトレーニング誤差と汎化誤差の差を保証するのに必要なサンプル数が増えることもこの式からわかります．実際には$\mathcal{H}$が無限集合になる場合がほとんどなためより難しい問題を考える必要がありますがその場合はVC次元などを用いることで同じように評価することが可能です．

さて，いよいよ本題のPACベイズについて話をします．ここまでは予測器の推定は点推定をする状況を考えていましたが，以降では予測器を分布推定することを考えます．具体的にはデータセット$S$が観測された時に以下のように推定される事後分布$q(h|S)$がよく用いられます．

q(h|S) = \frac{1}{Z}e^{-\lambda L_S(h)}p(h)

ここで$Z$は総和を$1$にするための規格化定数です．この式を使うことのお気持ちや通常のベイズ推定との違いはまた後ほどまとめますので，ここではこういうものを使うと思ってください．この時$q(h|S)$の汎化誤差を評価することを考えたいのですが，$q(h|S)$は分布のため$q(h|S)$の汎化誤差の評価方法は平均値，メジアン，MAP解などいくつか考えられます．ここでは以下のような訓練誤差や汎化誤差の事後分布$q(h|S)$に関する期待値を考えます．

L_S(q) := E_{q(h|S)}[L_S(h)] \\
L(q) := E_{q(h|S)}[L(h)]

この時以下のように$L(q)$の上界を確率的に保証する不等式を求めることがPACベイズの目的になります．

Pr\left( L(q) \leq \epsilon \right) \geq 1-\delta \tag{2}

このような不等式を求めることはいくつかの利点がありますが，1番の利点は$Pr(\cdot)$内の右辺はトレーニングデータのみから計算が可能なため，テストデータを用いずに汎化誤差を評価できるようになることです．これは特に教師情報を得るためのアノテーションコストが高く，十分な数のデータセットが得られない場合に特に有効な方法になります．以下では(2)式のような不等式を導出するためのコアになる考え方について説明していきます．

#PACベイズの基本的な考え方

PACベイズの不等式において以下の補題が重要になってきます．

Donsker-valadanのchange of measure
任意の可測関数$\phi(h)$³と任意の確率分布$q(h)$,$p(h)$に対して以下が成り立つ．

E_{q(h)}[\phi(h)]\leq D_{\rm KL}[q(h)||p(h)] + \log(E_{p(h)}[e^{\phi(h)}])

ここで$D_{\rm KL}[q(h)||p(h)]:=E_{q(h)}[\log(q(h)/p(h))]$である．

証明
証明は少し式変形した後にイェンセンの不等式を使うだけです．簡単にまとめると以下の手順で証明ができます．

\begin{align}
E_{q(h)}[\phi(h)] &= E_{q(h)}\left[\log\exp\phi(h)\right] \\
&= E_{q(h)}\left[\log\left\{\exp\phi(h) \left(\frac{p(h)}{q(h)}\right)\left(\frac{q(h)}{p(h)}\right)\right\}\right] \\
&= E_{q(h)}\left[\log\left(\frac{q(h)}{p(h)}\right)\right]+E_{q(h)}\left[\log\left\{\exp\phi(h) \left(\frac{p(h)}{q(h)}\right)\right\}\right] \\
&\leq D_{\rm KL}[q(h)||p(h)]+\log E_{p(h)}[\exp\phi(h)]
\end{align}

この不等式の重要な部分は$q(h)$についての期待値から$p(h)$についての期待値へ変換していることにあります．実際，$\phi(h):=L(h)-L_S(h)$とすると任意の$\lambda>0$に対して以下が成り立ちます．

E_{q(h|S)}[\phi(h)] \leq \frac{1}{\lambda}D_{\rm KL}[q(h|S)||p(h)] + \frac{1}{\lambda}\log(E_{p(h)}[e^{\lambda \phi(h)}]) \tag{3}

この時，事後分布$q(h|S)$は左辺の第一項のみに現れ，第二項は$q(h|S)$とは無関係に決まる項になります．また，データセット$S$が真の分布$D$から独立に生成されたと仮定した時$E_{\mathcal{D}}[L_S(h)]=L(h)$となることに注意すると$\phi(h)$は$L_S(h)$の期待値からの偏差を表しているので，第二項をHoeffdingの不等式などの集中不等式を用いて評価することで様々なバウンドを考えることができます．また集中不等式を使うために多くの場合で損失関数$l$が有界であると仮定します．つまり$-\infty<a<l<b<\infty$となる$a,b$が存在することを仮定するということです．クラス分類の場合は$a=0,b=1$とすることで一般に成り立つことが保証できますが，回帰の場合は損失関数が有界であることを保証できないため$a,b$はデータに応じて決める必要が出てくるため注意が必要です．

#具体的なPACベイズバウンド

最後にこれまでに実際に提案されてきたバウンドをいくつか紹介したいと思います．

以下の3つのバウンドはクラス分類に対して使えます．

McAllester's bound⁴

\mathop{Pr}_{S \sim D}\left(\forall{q}: L(q) \leq L_S(q) + \sqrt{\frac{D_{\rm KL}[q||p] + \log(N/\delta)}{2N-1}} \right)\geq 1-\delta

Langford and Seeger Bound⁵

\mathop{Pr}_{S \sim D}\left(\forall{q}: kl(L(q),L_S(q)) \leq \sqrt{\frac{D_{\rm KL}[q||p] + \log(2\sqrt{N}/\delta)}{2N}} \right)\geq 1-\delta

Catoni's bound⁶

\mathop{Pr}_{S \sim D}\left(\forall{q}: L(q)\leq \frac{1}{1-e^{-C}}\left[1-\exp\left(-C \cdot L_S(q)+\frac{1}{N} \left(D_{\rm KL}[q||p]-\log{\delta}\right)\right)\right]\right)\geq 1-\delta,

以下のバウンドは回帰にも使えます．

Alquier's bound⁷

\mathop{Pr}_{S \sim D}\left(\forall{q}: L(q)\leq L_S(q)+\frac{1}{N} \left(D_{\rm KL}[q||p]-\log{\delta}\right)+\frac{1}{2}(b-a)^2\right)\geq 1-\delta,

他にも非独立なデータに対するバウンドやヘビーテールなデータに対するバウンド，メタ学習に対するバウンドなど様々なバウンドが提案されています．詳細はBenjamin Guedjさんの論文を読んでいただけると助かります．

#おわりに

簡単にですがPACベイズの基礎的な話についてまとめてみました．また，書き足りないところもあるのでそのうち更新しようと思いますので，おかしいところやわからないところなどあれば連絡していただけると幸いです．

1. Benjamin Guedj, A Primer on PAC-Bayesian Learning. ArXiv:1901.05353, 2019. ↩

2. Shai Shalev-Shwartz and Shai Ben-David, Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014 ↩

3. 可測関数$\phi(h)$は$h$が確率変数なら$\phi(h)$も確率変数になることを保証するためのものです． ↩

4. David A. McAllester, PAC-Bayesian Stochastic Model Selection, Machine Learning, 51, 5–21, 2003 ↩

5. Matthias Seeger, PAC-Bayesian Generalisation Error Bounds for Gaussian Process Classification, Journal of Machine Learning Research 3, 233–269, 2002. ↩

6. Olivier Catoni, Pac-Bayesian Supervised Classification: The Thermodynamics of Statistical Learning, ArXiv:0712.0248, 2007. ↩

7. Pierre Alquier, James Ridgway, Nicolas Chopin, On the properties of variational approximations of Gibbs posteriors, arXiv:1506.04091, 2015. ↩