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]

このように、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*}$
が成り立つ