2023-02-16

Exponential Stochastic Inequality

確率

ほとんどのPACベイズ解析は、その証明の根幹にDonsker-Varadhan's variational formulaというものを用いる

任意の確率分布 $\pi$ と可測関数*1 $h:\Theta \to \mathbb{R}$ に対して以下が成り立つ:
$\displaystyle \log \mathbb{E}_{\theta \sim \pi} \left[e^{h(\theta)}\right] = \sup_{\rho \in \mathcal{P}(\Theta)} \left[\mathbb{E}_{\theta \sim \rho}[h(\theta)] - \operatorname{KL}(\rho \| \pi) \right]$
ただし、 $\mathcal{P}(\Theta)$ は $\Theta$ 上の確率分布全ての集合を表す

よって特に、上式の両辺を指数の肩に乗せることで

$\displaystyle \mathbb{E}_{\theta \sim \pi} \left[e^{h(\theta)}\right] = e^{\sup_{\rho \in \mathcal{P}(\Theta)} \left[\mathbb{E}_{\theta \sim \rho}[h(\theta)] - \operatorname{KL}(\rho \| \pi) \right] }$

が得られる

この補題はPACベイズ解析で次のような使われ方をする;
例えばデータを生成する未知の分布 $\mathcal{D}$ 、区間 $[0,1]$ に値をとる損失関数 $\ell$ 、仮説集合 $\mathcal{F} = \{f_\theta\}_{\theta \in \Theta}$ からなる学習問題 $(\mathcal{D}, \ell, \mathcal{F})$ を考え、今 $n$ 個の訓練データ $Z = (Z_1,\dots,Z_n) \sim \mathcal{D}^n$ を観測したとする
この時、Donsker-Varadhan's variational formulaにおける可測関数 $h$ として次のようなものを考えてみる:

$\displaystyle h(\theta) := \eta \left(\mathbb{E}_{z \sim \mathcal{D}} \left[ \ell(f_\theta;z) \right] - \frac{1}{n}\sum_{i=1}^n \ell(f_\theta; Z_i) \right)$

これはすなわち、リスクと経験誤差の差に逆温度 $\eta > 0$ をかけたものである

すると、 $h(\theta)$ は $n$ 個の独立同分布な確率変数の和になっているので、Hoeffdig's lemmaより

$\displaystyle \mathbb{E}_{Z \sim \mathcal{D}^n}\left[e^{h(\theta)}\right] = \mathbb{E}_{Z \sim \mathcal{D}^n}\left[e^{\eta \left(\mathbb{E}_{z \sim \mathcal{D}} \left[ \ell(f_\theta;z) \right] - \frac{1}{n}\sum_{i=1}^n \ell(f_\theta; Z_i) \right)}\right] \leq e^{\eta^2/8n}$

であることがわかるが、これを先ほどの(指数の肩に乗せた)Donsker-Varadhan's variational formulaと組み合わせることで

$\displaystyle \begin{align*} \mathbb{E}_{Z \sim \mathcal{D}^n}\left[ e^{\sup_{\rho \in \mathcal{P}(\Theta)} \left[\mathbb{E}_{\theta \sim \rho}[h(\theta)] - \operatorname{KL}(\rho \| \pi) \right] } \right] &= \mathbb{E}_{Z \sim \mathcal{D}^n}\mathbb{E}_{\theta \sim \pi} \left[e^{h(\theta)}\right] \\ &= \mathbb{E}_{\theta \sim \pi} \mathbb{E}_{Z \sim \mathcal{D}^n} \left[e^{h(\theta)}\right] \\ &\leq e^{\eta^2/8n} \end{align*}$

が得られ、分布 $\rho \in \mathcal{P}(\Theta)$ による平均リスクと平均経験誤差を

$\displaystyle \begin{align*} L(\rho;\mathcal{D}) &:= \mathbb{E}_{z \sim \mathcal{D}}\mathbb{E}_{\theta \sim \rho}[\ell(f_\theta;z)] \\ L(\rho; Z) &:= \frac{1}{n}\sum_{i=1}^n \mathbb{E}_{\theta \sim \rho}[\ell(f_\theta; Z_i) ] \end{align*}$

と表記することにすれば、上式は

$\displaystyle \begin{align*} \mathbb{E}_{Z \sim \mathcal{D}^n}\left[ e^{\eta \sup_{\rho \in \mathcal{P}(\Theta)} \left[ L(\rho;\mathcal{D}) - L(\rho;Z) - \frac{\operatorname{KL}(\rho \| \pi)}{\eta} - \frac{\eta}{8n} \right] } \right] \leq 1 \end{align*}$

と書き換えられることがわかる

モーメント母関数を評価できると何が嬉しいだろうか？
例えばMarkov's inequalityを利用すると、任意の $\delta > 0$ に対して

$\displaystyle \begin{align*} &\mathbb{P}_{Z \sim \mathcal{D}^n} \left[ \eta \sup_{\rho \in \mathcal{P}(\Theta)} \left[ L(\rho;\mathcal{D}) - L(\rho;Z) - \frac{\operatorname{KL}(\rho \| \pi)}{\eta} - \frac{\eta}{8n} \right] > \delta \right] \\ &=\mathbb{P}_{Z \sim \mathcal{D}^n} \left[ e^{\eta \sup_{\rho \in \mathcal{P}(\Theta)} \left[ L(\rho;\mathcal{D}) - L(\rho;Z) - \frac{\operatorname{KL}(\rho \| \pi)}{\eta} - \frac{\eta}{8n} \right] } > e^\delta \right] \\ &\leq e^{-\delta} \cdot \mathbb{E}_{Z \sim \mathcal{D}^n}\left[ e^{\eta \sup_{\rho \in \mathcal{P}(\Theta)} \left[ L(\rho;\mathcal{D}) - L(\rho;Z) - \frac{\operatorname{KL}(\rho \| \pi)}{\eta} - \frac{\eta}{8n} \right] } \right] = e^{-\delta} \end{align*}$

が成り立つので、 $\epsilon := e^{-\delta}$ とおけば、上式は $1-\epsilon$ 以上の確率で

$\displaystyle \begin{align*} \forall \rho \in \mathcal{P}(\Theta).\quad L(\rho;\mathcal{D}) \leq L(\rho;Z) + \frac{\eta}{8n} + \frac{\operatorname{KL}(\rho \| \pi) + \log(1/\epsilon)}{\eta} \end{align*}$

と、標準的なPACベイズによる汎化誤差解析が得られる[1]

Exponential Stochastic Inequality

このように、PACベイズ解析ではモーメント母関数の評価が主な作業であり、まともに数式を書いていこうとすると毎回指数の肩に式を乗せる羽目になるので割と煩雑になりやすい

そこで、近年のPACベイズ解析ではExponential Stochastic Inequality (ESI*2 )という書式が使われることがある

任意の $\eta > 0$ と確率変数 $X,Y$ に対して
$\displaystyle \begin{align*} X \unlhd_{\eta} Y \overset{\mathrm{def}}{\Longleftrightarrow} \mathbb{E}\left[e^{\eta (X-Y) }\right] \leq 1 \end{align*}$
特に、上式右辺の期待値が確率変数 $U$ についてのものであることを強調したい時は $X \unlhd_{\eta}^U Y$ と書く

ESIを用いることで、大抵のPACベイズ解析の流れは次のようにパッケージ化できる:

ある $\eta > 0$ について、 $\{ Y_\theta \}_{\theta \in \Theta}$ を $\forall \theta.\, Y_\theta \unlhd_\eta 0$ を満たす確率変数の族とするとき、任意の事前分布 $\pi \in \mathcal{P}(\Theta)$ と事後分布 $\rho: \bigcup_{i=1}^n \mathcal{Z}^i \to \mathcal{P}(\Theta)$ に対して
$\displaystyle \begin{align*} \mathbb{E}_{\theta \sim \rho(Z)} [Y_\theta] \unlhd_{\eta} \frac{\operatorname{KL}(\rho \| \pi)}{\eta} \end{align*}$
が成り立つ

ESIの主要な性質に関しては、例えば[2]が参考になる

最近ブログで数式を書くことが増えてきてはてなブログで記事を書くのが少し大変なので、GitHub Pagesとかに引っ越そうかな〜とか考え始めてる
ブログ形式で数式を書く一番良い方法はなんなんだろか

参考文献

[1] Olivier Catoni. A PAC-Bayesian approach to adaptive classification. 2004.
[2] Mhammedi et al. PAC-Bayes Un-Expected Bernstein Inequality. 2019.

*1:正直文献によって補題の主張が微妙に異なっていて、可測関数全般に対して成り立つのか良くわかっていない、少なくとも有界であれば成り立つ

*2:イージーと読む

2023-01-30

1月終わり

雑記

youtu.be

<a href="https://yoyaku.bandcamp.com/album/jinger002">JINGER002 by Jinger aka Traumer</a>

気がついたら今年の12分の1が終わろうとしてるの怖すぎる

なんとか修論発表も終わって、今が一番暇な時期かもしれない

修論発表のついでに博士審査なるものがあったのだけど、自分はまだ博士課程に進学できることが確定してないみたいで、落ち着いて博士課程の研究をできない(弱音を吐くな

博士課程ではグラフニューラルネットワーク周りのことをやろうかなーと思ってるけど、一旦修論終わったし趣味勉でcounterfactual regret minimizationでも実装してみよう

2023-01-19

修論

雑記

昨日、無事修論を提出した

やっと解放されたーーと言いたいところだけど、まだ修論発表が残っている..._(:3」∠)_

今日は実は25歳の誕生日なのだけど、おかげで明日の発表練習に向けてスライドを作る羽目に😭

25歳って、四捨五入したら30やん！もうアラサーじゃないか！！😭

流石にこの年齢になると確実に立派な大人(24歳もそう)なのに、まだ自分はまともに稼ぎもせず実家暮らしと考えると泣いてしまう

そろそろ何か自信を持って言えるものが欲しい...

修論の方も、とりあえず書きはしたけれど、1年弱かけた割に大事なケースが未解決という感じで、なんだかビミョーかもしれない

締め切り当日に細かいところを修正していて思ったけど、目の前に書き終わった修論があるから良いだけで、完成していなかったら去年のように書くのをやめていた気がする

修論発表は博士審査も兼ねていて、修論に関する発表の後に1分で博士課程で何をやるつもりか語って、それらの内容でもって博士課程に入学できるか決まるらしいけれど、こんな発表で大丈夫か...？(画像略

とりあえず修論発表が終わって博士入学が決まったら、修論で扱っていたPAC-Bayes周りのことを記事にしようかなと思う

入学失敗したらスイスの時計専門学校にいこかな

2023-01-02

2023

雑記

明けましておめでとうございます！！

お正月に投稿するの忘れてたけど、まぁ1/5までは正月ってことでね...()

もうすぐ修論の提出締め切りということで、最近はただただ修論を書いてる

1年あったはずなのになぜ、、、

相変わらず修論の成果にはちょっと納得いってないというか、もう少しできる気がする！って感じがするけど、流石に今回はとりあえず形にすることを優先しよう😅

ブログの更新もちょびちょびやってこうと思います！

2022-11-24

Efron-Stein inequality

確率

独立な確率変数 $X_1,\dots,X_n$ による和 $Z = X_1 + \cdots + X_n$ の分散は

$\displaystyle \mathrm{Var}(Z) = \sum_{i=1}^n \mathrm{Var}(X_i)$

という関係が成り立つが、似たような関係式を一般の関数 $Z = f(X_1,\dots,X_n)$ に対して述べたのがEfron-Stein inequalityである

Efron-Stein inequality

独立な確率変数 $X_1,\dots,X_n$ によって定義されるsquare-integrableな関数 $Z = f(X_1,\dots,X_n)$ に対して以下の関係が成り立つ:
$\displaystyle \mathrm{Var}(Z) \leq \sum_{i=1}^n \mathbb{E} \left[ \left( Z - \mathbb{E}^{(i)}Z \right)^2\right]$

ただし、 $\mathbb{E}^{(i)}Z$ は $X^{(i)} = (X_1,\dots,X_{i-1},X_{i+1},\dots,X_n)$ によって条件付けられた $Z$ の期待値、すなわち $X_i$ の確率分布を $\mu_i$ と表した時の
$\displaystyle \mathbb{E}^{(i)}Z = \int_{\mathcal{X}} f(X_1,\dots,X_{i-1},x_i,X_{i+1},\dots,X_n) d\mu_i(x_i)$

$Z = \sum_{I=1}^n X_i$ であるときは $Z - \mathbb{E}^{(i)}Z = X_i - \mathbb{E}X_i$ よりEfron-Stein inequalityの右辺は $\sum_{i=1}^n \mathrm{Var}(X_i)$ となり、冒頭で述べた「和の分散が分散の和」の不等式版が得られる*1

証明の肝は、 $Z - \mathbb{E}Z$ をDoob decompositionによって $L^2$ 空間で直交する確率変数の和で表すというアイディアである

証明

$\mathbb{E}_i Z$ を $(X_1,\dots,X_i)$ によって条件付けた $Z$ の期待値、すなわち

$\displaystyle \mathbb{E}_i Z = \int_{\mathcal{X}^{n-i}} f(X_1,\dots,X_{i},x_{i+1},\dots,x_n) d\mu_{i+1}(x_{i+1})\dots d\mu_n (x_n)$

とし、

$\displaystyle \Delta_i = \mathbb{E}_i Z - \mathbb{E}_{i-1}Z$

と定義すれば*2、いわゆるtelescoping sumにより

$\displaystyle Z - \mathbb{E}Z = \sum_{I=1}^n \Delta_i$

が成り立ち、さらに任意の $j > i$ に対して $\mathbb{E}_i \Delta_j = 0$ より $\mathbb{E}_i [\Delta_j \Delta_i ] = \Delta_i \mathbb{E}_i \Delta_j = 0$ となるが、これは

$\displaystyle \begin{align*} \mathrm{Var}(Z) &= \mathbb{E}\left[\left( \sum_{i=1}^n \Delta_i \right)^2\right] \\ &= \sum_{i=1}^n \mathbb{E}[\Delta_i^2] + 2\sum_{j > i} \mathbb{E}[\Delta_i \Delta_j] \\ &= \sum_{i=1}^n \mathbb{E}[\Delta_i^2] \end{align*}$

を意味する

Fubini's theoremより $\mathbb{E}_i [\mathbb{E}^{(i)}Z] = \mathbb{E}_{i-1} Z$ であることに注目すると $\Delta_i = \mathbb{E}_i [Z - \mathbb{E}^{(i)}Z ]$ と表せ、Jensen's inequalityより