sanov の定理の証明

sanov の定理は大偏差原理の一種であり、統計的推論におけるKLダイバージェンスの最小化 (= 尤度の最大化) の意味を理解するのに必須の定理です。本記事では sanov の定理を証明します。概ね [TC] に沿って証明しますが、一部補完、順序の変更を行なっています。

必要に応じて以下の記事を引用します。都度リンクを貼りますが、ひと通り軽く目を通した方が、本記事の内容を理解しやすいと思います。

sanov の定理の主張

この節では sanov の定理の主張について述べます。sanov の定理は可分完備距離空間 (ポーランド空間) $(S, d)$ に値をとる独立同分布な確率変数族に関する大偏差原理です。まず、sanov の定理の主張に現れる確率測度の族と rate function を定義し、その後定理の主張を述べます。

$\mathcal{P}(S)$ を $S$ 上の Borel 確率測度全体とします。$d_P$ を $\mathcal{P}(S)$ の Prokhorov 距離とし、$\mathcal{P}(S)$ には $d_P$ による位相が入っているものとします。弱収束と $d_P$ による収束は一致します。

確率測度の族

$N \in \mathbb{N}$ に対して $L_N: S^N \to \mathcal{P}(S)$ を

$$L_N: S^N \ni x = (x_1, \dots, x_n) \mapsto \frac{1}{N} \sum_{i = 1}^N \delta_{x_i} \in \mathcal{P}(S)$$

と定めると、これは可測になります。実際、ディラック測度をとる写像 $\iota: S \to \mathcal{P}(S)$ は埋め込み (証明はこちら) なので、$\iota^N: S^N \to \mathcal{P}(S)^N$ は連続です。また、写像

$$m: \mathcal{P}(S)^N \ni \eta = (\eta_1, \dots, \eta_N) \mapsto \frac{1}{N} \sum_{i=1}^N \eta_i \in \mathcal{P}(S)$$

は、$\mathcal{P}(S)^N$ の点列 $\{\eta^\alpha\}_{\alpha=1}^{\infty}$ が $\eta$ に収束すれば各成分 $\{\eta^\alpha_i\}_{\alpha=1}^{\infty}$ は $\eta_i$ に弱収束するので、$S$ 上の任意の有界連続関数 $f$ に対して

\begin{align} \lim_{\alpha \to \infty} \int_{S} f d \left(\frac{1}{N} \sum_{i = 1}^N \eta^{\alpha}_i \right) &= \lim_{\alpha \to \infty} \frac{1}{N} \sum_{i = 1}^N \int_{S} f d\eta^{\alpha}_i \\ &= \frac{1}{N} \sum_{i = 1}^N \int_{S} f d\eta_i \\ &= \int_{S} f d \left(\frac{1}{N} \sum_{i = 1}^N \eta_i \right) \end{align}

を満たし、$\{m(\eta^\alpha)\}_{\alpha=1}^{\infty}$ は $m(\eta)$ に弱収束します。よって $m$ は連続です。$L_N = m \circ \iota^N$ なので $L_N$ は連続、特に可測になります。

$\mu \in \mathcal{P}(S)$ の $N$ 個の直積測度を $\mu^{\otimes N} \in \mathcal{P}(S^N)$ とおき、

$$Q_N = (L_N)_* (\mu^{\otimes N})$$

とおくと、$Q_N \in \mathcal{P}(\mathcal{P}(S))$ になります。$\{Q_N\}_{N=1}^{\infty}$ が sanov の定理に現れる確率変数の族になります。

$Q_N$ について補足します。$\{Y_1, Y_2, \dots\}$ を $S$ 値の独立同分布な確率変数列とし、その分布が $\mu \in \mathcal{P}(S)$ であるとします。このとき、$Y_i$ の定義域を $\Omega_i$ とおいて $\delta_{Y_i}$ を以下の写像の合成

$$\Omega_i \xrightarrow{Y_i} S \xrightarrow{\iota} \mathcal{P}(S)$$

とし、$Q^{\prime}_N$ を $(\delta_{Y_1} + \cdots + \delta_{Y_N}) / N$ の分布おくと、$Q_N$ と $Q^{\prime}_N$ は一致します。実際、任意の Borel 集合 $A \subset \mathcal{P}(S)$ に対して

\begin{align} Q^{\prime}_N(A) &= \mu^{\otimes N}(\{x \in S^N \mid \frac{\delta_{x_1} + \cdots + \delta_{x_N}}{N} \in A\}) \\ &= \mu^{\otimes N}(\{x \in S^N \mid L_N(x) \in A\}) \\ &= \mu^{\otimes N}(L_N^{-1}(A)\}) \\ &= (L_N)_*(\mu^{\otimes N})(A) \\ &= Q_N(A) \\ \end{align}

となります。

後で示しますが、$N \to \infty$ で

$$Q_N \to \delta_{\mu} \quad (弱収束)$$

が成り立ちます。

KL ダイバージェンス

$\mu, \nu \in \mathcal{P}(S)$ とし、$\nu$ が $\mu$ に関して絶対連続であること $\nu \ll \mu$ と表します。また、$\nu \ll \mu$ のとき、ラドン・ニコディム微分を $\frac{d \nu}{d \mu}$ と表します。

$\mu, \nu \in \mathcal{P}(S)$ に対し、$D_{KL}(\nu || \mu)$ を

\begin{align} D_{KL}(\nu || \mu) = \begin{cases} \displaystyle \int_{S} \frac{d \nu}{d \mu} \log \left(\frac{d \nu}{d \mu}\right) d \mu & (\nu \ll \mu, \ \log (\frac{d \nu}{d \mu}) \in L^1(S, \nu)) \\ \infty & (\textrm{それ以外}) \end{cases} \end{align}

と定め、KL ダイバージェンス (またはカルバック・ライブラーダイバージェンス、相対エントロピー) といいます ([TC] では $D_{KL}(\nu || \mu) = H(\nu | \mu)$ と表しています)。補足すると、$\nu \ll \mu$ のとき

$$\int_{S} \frac{d \nu}{d \mu} \log \left(\frac{d \nu}{d \mu}\right) d \mu = \int_{S} \log \left(\frac{d \nu}{d \mu}\right) d \nu$$

が成り立ちます。よって $\log (\frac{d \nu}{d \mu}) \in L^1(S, \nu)$ ならば $D_{KL}(\nu || \mu)$ の値が有限になります。

後で示しますが、$\mu \in \mathcal{P}(S)$ を固定したとき、

$$D_{KL}(\cdot || \mu): \mathcal{P}(S) \to \mathbb{R} \cup \{+ \infty\}$$

は下半連続かつ凸であり、$D_{KL}(\cdot || \mu) \geq 0$ を満たします。

以上で sanov の定理の主張を述べる準備ができました。

sanov の定理の主張

sanov の定理の主張は以下の通りです。

定理. sanov の定理

$S$ をポーランド空間, $\mu$ をその上の Borel 確率測度とし, $D_{KL}(\cdot || \mu)$ を KL ダイバージェンスとする. このとき, $Q_N = (L_N)_* (\mu^{\otimes N})$ とおくと, $\{Q_N\}_{N = 1}^{\infty}$ は $D_{KL}(\cdot || \mu)$ を凸な good rate function として大偏差原理を満たす. $\Box$

以下で、これを示します。

証明の流れ

sanov の証明の流れは概ね以下のようになります。

rate funciton を構成し、弱い意味での大偏差原理を満たすことを示す。
$\{Q_{N}\}_{N =1}^{\infty}$ が exponentially tight であることを示す。
ルジャンドル変換を用いて rate funciton が KL ダイバージェンスと一致することを示す。

1, 2 によって $\{Q_{N}\}_{N =1}^{\infty}$ が大偏差原理を満たすことが示され、rate function が good であることが示されます (証明はこちら)。

ルジャンドル変換を用いるには $\mathcal{P}(S)$ を凸閉部分集合として含む $\mathbb{R}$ 上の局所凸空間が必要になります。その役割は符号付有限 Borel 測度全体 $\mathcal{M}_{\mathbb{R}}(S)$ が担います。

弱い意味での大偏差原理の成立

$\mu \in \mathcal{P}(S)$, $r > 0$ に対して、$\mu$ を中心とする半径 $r$ の開球を $B_r(\mu)$ とおき、開球全体の集合を $\mathcal{B}$ とおきます。任意の $B \in \mathcal{B}$ に対して

$$\mathcal{L}(B) = -\lim_{N \to \infty} \frac{1}{N} \log Q_N(B)$$

が存在するとき、

$$I(\mu) = \sup_{\mu \in B, B \in \mathcal{B}} \mathcal{L}(B)$$

とおくと、$I$ は rate function であり、$\{Q_{N}\}_{N = 1}^{\infty}$ は $I$ を rate function として弱い意味での大偏差原理を満たすのでした (証明はこちら)。

この節では $\mathcal{L}(B)$ が存在すること、$I$ が凸関数であることを証明します。$I$ が凸関数であることは、後にルジャンドル変換を用いるときに必要です。

開球に対する $Q_{N}$ の漸近挙動

まずは $Q_{N}$ の挙動を確認しましょう。任意の $B \in \mathcal{B}$ に対して以下が成立します。

$Q_N(B) Q_M(B) \leq Q_{N+M}(B)$
すべての $N$ に対して $Q_N(B) = 0$ であるか、またはある $N_0$ があって $N \geq N_0$ であれば $Q_N(B) > 0$

まずは (1) を証明します。$M, N \in \mathbb{N}$ とし、$L_{M + N}^{M + 1}: S^{M + N} \to \mathcal{P}(S)$ を

$$L_{M + N}^{M + 1}(x_1, \dots,x_M, x_{M+1}, \dots, x_{M+N}) = \sum_{i = M + 1}^{M + N} \delta_{x_i}$$

とおきます。このとき、$x \in S^{M + N}$ に対して $L_M(x) \in B$ かつ $L_{M + N}^{M+1}(x) \in B$ ならば、$B$ が凸であることから

$$L_{M+N}(x) = \frac{M}{M+N}L_{M}(x) + \frac{N}{M + N}L_{M + N}^{M+1}(x) \in B$$

なので、

\begin{align} Q_M(B)Q_N(B) &= \mu^{\otimes M}(L_M^{-1}(B))\ \mu^{\otimes N}(L_N^{-1}(B)) \\ &= \mu^{\otimes M}(\{x \in S^{M} \mid L_M(x) \in B\})\ \mu^{\otimes N}(\{x \in S^{N} \mid L_N(x) \in B\}) \\ &= \mu^{\otimes (M + N)}(\{x \in S^{M + N} \mid L_M(x) \in B, L_{M + N}^{M+1}(x) \in B\})\\ & \leq \mu^{\otimes (M + N)}(\{x \in S^{M + N} \mid L_{M + N}(x) \in B\})\\ &= Q_{M+N}(B) \end{align}

が成り立ちます。

次に (2) を示します。$M \in \mathbb{N}$ を 1 つ固定します。$Q_M(B) > 0$ とすると、$Q_M$ はポーランド空間 $\mathcal{P}(S)$ 上の Borel 確率測度なので正則であり (証明はこちら)、コンパクト集合 $K \subset B$ で $Q_M(K) > 0$ を満たすものが存在します。ここで

$$d_P(K, \mathcal{P}(S) \setminus B) = \delta^{\prime}$$

とおくと、$K$ は閉集合なので $\delta^{\prime} > 0$ であり、$K \subset B^{\prime} \subset B$ を満たす $B^{\prime} \in \mathcal{B}$ が存在します ($B = B_r(\nu)$ としたとき、$B^{\prime} = B_{r -\delta^{\prime} / 2}(\nu)$ とすれば良い)。$K$ の閉凸包は、$B^{\prime}$ が凸であることから

$$\overline{\mathrm{Conv}(K)} \subset \overline{B^{\prime}} \subset B$$

となり、$\overline{\mathrm{Conv}(K)}$ はコンパクトなので (証明はこちら)、$K$ はあらかじめ凸集合として問題ありません。

ここで、任意の $\nu_1, \nu_2 \in \mathcal{P}(S)$ に対して

$$2d_P(\nu_1, \nu_2) < ||\nu_1 -\nu_2||_{var}$$

が成り立つので (証明はこちら)、

$$0 < 2\delta < d_P(K, \mathcal{P}(S) \setminus B)$$

を満たすように $\delta$ をとると、任意の $\nu \in K$ に対して

\begin{align} B & \supset \{\eta \in \mathcal{P}(S) \mid d_P(\eta, \nu) < \delta\} \\ & \supset \{\eta \in \mathcal{P}(S) \mid ||\eta -\nu||_{var} < 2\delta\} \end{align}

が成り立ちます。このとき $N \in \mathbb{N}$ を $N > M / \delta$ となるように取り、

$$N = Ms + r, \quad (0 \leq r \leq M -1)$$

とおくと、任意の $x \in S$ に対して

$$L_N(x) = \frac{Ms}{N}L_{Ms}(x) + \frac{r}{N} L_{N}^{Ms + 1}(x)$$

であり、

\begin{align} Q_N(B) &= \mu^{\otimes N}(L_N^{-1}(B)) \\ &= \mu^{\otimes N}(\{x \in S^N \mid L_N(x) \in B\}) \\ & \geq \mu^{\otimes N}(\{x \in S^N \mid L_{Ms}(x) \in K, \\ & \qquad \qquad \quad ||L_{Ms}(x) -L_N(x)||_{var} < 2\delta\}) \\ & = \mu^{\otimes N}(\{x \in S^N \mid L_{Ms}(x) \in K, \\ & \qquad \qquad \quad ||\frac{r}{N}L_{Ms}(x) -\frac{r}{N}L_{N}^{Ms + 1}(x)||_{var} < 2\delta\}) \\ & \geq \mu^{\otimes Ms}(\{x \in S^N \mid L_{Ms}(x) \in K, \ \frac{r}{N}||L_{Ms}(x)||_{var} < \delta\}) \\ & \qquad \times \mu^{\otimes r}(\{x \in S^N \mid L_{Ms}(x) \in K, \frac{r}{N}||L_{r}(x)||_{var} < \delta\}) \\ & = \mu^{\otimes Ms}(\{x \in S^N \mid L_{Ms}(x) \in K \}) \\ & \geq \mu^{\otimes M}(\{x \in S^N \mid L_{M}(x) \in K \})^s \\ & > 0 \end{align}

となります。途中で確率測度 $\nu$ に対して $||\nu||_{var} = 1$ であることを用いました。よって $N_0 > M / \delta$ を一つとれば、$N > N_0$ のとき $Q_N(B) > 0$ となります。

もし $Q_N(B) > 0$ を満たす $N \in \mathbb{N}$ が存在しなければ、任意の $N$ に対して $Q_N(B) = 0$ となります。これで示したいことが示されました。

$\mathcal{L}(B)$ の存在

$B \in \mathcal{B}$ に対して

$$f: \mathbb{N} \ni N \mapsto -\log Q_N(B) \in [0, \infty]$$

とおくと、$f$ は劣加法的、つまり

$$f(N + M) \leq f(N) + f(M)$$

を満たし、かつ任意の $N \in \mathbb{N}$ に対して $f(N) = \infty$ であるか、ある $N_0$ が存在して任意の $N > N_0$ に対し $f(N) < \infty$ であるかのどちらかが成り立ちます。

$$\frac{f(N)}{N} = -\frac{1}{N}\log Q_N(B)$$

なので、$f(N) / N$ が極限をもてば、それは $\mathcal{L}(B)$ に一致します。そこで $f(N) / N$ の極限が存在することを示します。

もし任意の $N$ に対して $f(N) = \infty$ であれば、$N \to \infty$ で $f(N) / N \to \infty$ となります。よって極限が存在します。

$N > N_0$ のときに $f(N) < \infty$ であるとします。$N_0$ 以下を切り捨てることで、常に $f(N) < \infty$ として良いです。ここで

$$a = \inf_{N \in \mathbb{N}} \frac{f(N)}{N}$$

とおき、これが極限と一致することを示します。

まず定義から、

$$\liminf_{n \to \infty} \frac{f(N)}{N} \geq a$$

が成り立ちます。よって、

$$\limsup_{n \to \infty} \frac{f(N)}{N} \leq a$$

が成り立つことを示せば良いです。もし成り立たないとすると、$\varepsilon > 0$ と部分列 $\{N_k\}_{k}$ が存在して任意の $k \geq 1$ に対して

$$\frac{f(N_k)}{N_k} > a + \varepsilon$$

が成り立ちます。ここで $a$ の定義から

$$\frac{f(m)}{m} < a + \varepsilon / 2$$

を満たす $m \in \mathbb{N}$ が存在します。$\{N_k\}_{k}$ をそれぞれ $m$ で割った余りを考えると、同じ余りを持つものが無限個存在します。部分列を置き換えて、$\{N_k\}_{k}$ をそれぞれ $m$ で割った余りは同じとします。ここで、$s \in \mathbb{N}$ に対して

\begin{align} \frac{f(N_1 + sm)}{N_1 + sm} &\leq \frac{f(N_1)}{N_1 + sm} + \frac{f(sm)}{N_1 + sm} \\ & \leq \frac{f(N_1)}{N_1 + sm} + \frac{sf(m)}{N_1 + sm} \\ & \leq \frac{f(N_1)}{N_1 + sm} + \frac{sf(m)}{sm} \\ & \leq \frac{f(N_1)}{N_1 + sm} + a + \frac{\varepsilon}{2} \\ & \overset{s \to \infty}{\to} a + \frac{\varepsilon}{2} \end{align}

が成り立つので十分大きな $k$ に対して

$$\frac{f(N_k)}{N_k} \leq a + \frac{\varepsilon}{2}$$

が成り立ち、部分列の取り方に矛盾します。よって極限

$$\lim_{n \to \infty} \frac{f(N)}{N}$$

は存在します。

rate function の構成と凸性

$\nu \in \mathcal{P}(S)$ に対して

$$I(\nu) = \sup_{\nu \in B, B \in \mathcal{B}} \mathcal{L}(B)$$

とおくと、$I$ は rate function であり、$\{Q_N\}_{N=1}^{\infty}$ は rate function を $I$ として弱い意味での大偏差原理を満たすのでした (証明はこちら)。$B_1 \subset B_2$ のとき、任意の $N$ に対して $Q_N(B_1) \leq Q_N(B_2)$なので、

$$\mathcal{L}(B_1) = -\lim_{N \to \infty} \frac{1}{N} \log Q_N(B_1) \geq -\lim_{N \to \infty} \frac{1}{N} \log Q_N(B_2) = \mathcal{L}(B_2)$$

となります。$\nu$ を含む任意の開球 $B \in \mathcal{B}$ に対し、$r$ を十分小さくとれば $B_r(\nu) \subset \mathcal{B}$ となるので、

$$\sup_{\nu \in B, B \in \mathcal{B}} \mathcal{L}(B) = \lim_{r \to 0}\mathcal{L}(B_r(\nu))$$

となります。

$I$ が凸関数であることを示しましょう。$\nu_0, \nu_1 \in \mathcal{P}(S)$、$0 < t < 1$ とし、

$$\nu_t = t \nu_1 +(1 -t)\nu_0$$

とおきます。また $r > 0$ とし、$0 \leq t \leq 1$ に対して

$$t B_r(\nu_1) + (1 -t) B_r(\nu_0) = \{t \nu^{\prime}_1 + (1 -t)\nu^{\prime}_0 \mid \nu^{\prime}_1 \in B_r(\nu_1), \nu^{\prime}_0 \in B_r(\nu_0) \}$$

とおきます。このとき、Prokhorov 距離の性質から任意の $\nu_t^{\prime} \in B_r(\nu_t)$ に対して

$$d_P(\nu^{\prime}_t, \nu_t) < r$$

が成り立つので (証明はこちら)、

$$t B_r(\nu_1) + (1 -t) B_r(\nu_0) \subset B_r(\nu_t)$$

が成り立ちます。このとき、

\begin{align} \mathcal{L}(B_r(\nu_{\frac{1}{2}})) &= -\lim_{N \to \infty} \frac{1}{2N} \log Q_{2N}(B_r(\nu_{\frac{1}{2}})) \\ &= -\lim_{N \to \infty} \frac{1}{2N} \log \mu^{\otimes 2N}(\{x \in S^{2N} \mid L_{2N}(x) \in B_r(\nu_{\frac{1}{2}}) \}) \\ &\leq -\lim_{N \to \infty} \frac{1}{2N} \log \mu^{\otimes 2N}(\{x \in S^{2N} \mid \\ & \qquad \qquad \qquad L_{N}(x) \in B_r(\nu_1), L_{2N}^{N+1}(x) \in B_r(\nu_0) \}) \\ & = -\lim_{N \to \infty} \frac{1}{2N} \log \left( \mu^{\otimes N}(\{x \in S^{N} \mid L_{N}(x) \in B_r(\nu_1) \}) \right. \\ & \qquad \qquad \qquad \left. \times \mu^{\otimes N}(\{x \in S^{N} \mid L_{2N}^{N+1}(x) \in B_r(\nu_0) \}) \right) \\ &= -\lim_{N \to \infty} \frac{1}{2} \left(\frac{1}{N}\log Q_N(B_r(\nu_1)) + \frac{1}{N}\log Q_N(B_r(\nu_0)) \right)\\ &= \frac{1}{2} \mathcal{L}(B_r(\nu_1)) +\frac{1}{2} \mathcal{L}(B_r(\nu_0)) \end{align}

が成り立つので、$r \to \infty$ とすると

$$I(\nu_{\frac{1}{2}}) \leq \frac{1}{2} I(\nu_1) +\frac{1}{2} I(\nu_0)$$

が成り立ちます。これから、任意の $m \in \mathbb{N}$ と任意の整数 $0 \leq i \leq 2^m$ に対して

$$I(\nu_{\frac{i}{2^m}}) \leq \frac{i}{2^m} I(\nu_1) +\frac{2^m -i}{2^m} I(\nu_0)$$

が成り立つことがわかります。実際 $m -1$ までは正しいとすると、$i \leq 2^{m -1}$ のとき

\begin{align} I(\nu_{\frac{i}{2^m}}) &= I\left(\frac{i}{2^m}\nu_1 + \frac{2^m -i}{2^m}\nu_0 \right) \\ &= I \left(\frac{1}{2}(\frac{i}{2^{m-1}}\nu_1 + \frac{2^{m-1} -i}{2^{m -1}}\nu_0) +\frac{2^{m-1}}{2^m}\nu_0 \right) \\ & \leq \frac{1}{2}I \left(\frac{i}{2^{m-1}}\nu_1 + \frac{2^{m-1} -i}{2^{m-1}}\nu_0 \right) +\frac{1}{2}I(\nu_0) \\ & \leq \frac{i}{2^m}I(\nu_1) + \frac{2^{m-1} -i}{2^{m}}\nu_0 +\frac{1}{2}I(\nu_0)\\ &= \frac{i}{2^m}I(\nu_1) + \frac{2^{m} -i}{2^{m}}I(\nu_0) \end{align}

が成り立ちます。$i > 2^{m -1}$ のときも同様です。

一般の $t$ に対して不等式を示しましょう。$I(\nu_t) = \infty$ とすると、$I$ は下半連続なので、任意の $N > 0$ に対して $\delta> 0$ が存在して、$|t^{\prime} -t| < \delta$ ならば

$$I(\nu_{t^{\prime}}) \geq N$$

が成り立ちます。このとき、$t^{\prime} = i / 2^m$ ならば

\begin{align} I(\nu_{t^{\prime}}) & \leq t^{\prime} I(\nu_1) +(1 -t^{\prime}) I(\nu_0) \\ & \leq t I(\nu_1) +(1 -t) I(\nu_0) + \delta (I(\nu_1) + I(\nu_0)) \end{align}

となりますが、任意の $N$ に対して上記の不等式が成り立つには、$I(\nu_1) = \infty$ または $I(\nu_0) = \infty$ が成り立つ必要があります。よって

$$I(\nu_{t}) \leq t^{\prime} I(\nu_1) +(1 -t) I(\nu_0)$$

が成り立ちます。

$I(\nu_t) < \infty$ とすると、$I$ は下半連続なので、任意の $\varepsilon > 0$ に対して、ある $\delta > 0$ が存在して、$|t^{\prime} -t| < \delta$ ならば

$$I(\nu_{t^{\prime}}) \geq I(\nu_t) -\varepsilon$$

を満たします。$t^{\prime} = i / 2^m$ とおくと、

\begin{align} I(\nu_t) -\varepsilon & \leq I(\nu_{t^{\prime}}) \\ & \leq \frac{i}{2^m}I(\nu_1) + \frac{2^{m} -i}{2^{m}}I(\nu_0) \\ & \leq tI(\nu_1) + (1 -t)I(\nu_0) + \delta(I(\nu_1) + I(\nu_1)) \end{align}

となります。

$$\delta < \frac{\varepsilon}{I(\nu_1) + I(\nu_1)}$$

を満たすように $\delta$ をとれば、$\varepsilon$ が任意であることから

$$I(\nu_t) \leq t I(\nu_1) + (1 -t)I(\nu_0)$$

が成り立ちます。よって $I$ は凸関数です。

以上で $\{Q_N\}_{N =1}^{\infty}$ は $I$ を rate function として弱い意味での大偏差原理を満たし、$I$ が凸関数であることが示されました。

$\{Q_N\}_{N =1}^{\infty}$ が exponentially tight であれば、$I$ が good rate function で、$\{Q_N\}_{N =1}^{\infty}$ が (普通の意味での) 大偏差原理を満たすことがわかります。

exponentially tight であること

$\{Q_N\}_{N=1}^{\infty}$ がexponentially tight であることを示します。そのためには、任意の $L > 0$ に対してコンパクト集合 $C_L \subset \mathcal{P}(S)$ が存在して、

$$\limsup_{N \to \infty} \frac{1}{N} \log Q_N(C_L^c) \leq -L$$

を満たすことを示せば良いです。

$f \in C_{b, \mathbb{R}}(S)$ に対して

$$\hat{f}: \mathcal{P}(S) \ni \nu \mapsto \int_S f d \nu \in \mathbb{R}$$

と定めます。$Q_N = (L_N)_* \mu^{\otimes N}$ なので、任意の $f \in C_{b, \mathbb{R}}(S)$ に対して

\begin{align} \int_{\mathcal{P}(S)} e^{N \langle \hat{f}, \nu \rangle} d Q_N(\nu) &= \int_{S^n} e^{N \langle \hat{f}, L_N(x)\rangle} d\mu^{\otimes N}(x) \\ &= \int_{S^n} e^{\sum_{i=1}^N f(x_i)} d\mu^{\otimes N}(x) \\ &= \left(\int_S e^{f(x)} d\mu(x) \right)^N \end{align}

が成り立ちます。このとき、任意の $T > 0$ と任意の $\delta > 0$ に対して

$$\frac{e^{TN \langle \hat{f}, \nu \rangle}}{e^{TN \delta}} > 0 \quad (\nu \in \mathcal{P}(S))$$

であり、

$$\{\nu \in \mathcal{P}(S) \mid \langle \hat{f}, \nu \rangle \geq \delta\}$$

においては $1$ 以上なので、

\begin{align} & Q_{N}(\{\nu \in \mathcal{P}(S) \mid \langle \hat{f}, \nu \rangle \geq \delta\}) \\ \leq \ & e^{-TN\delta} \int_{\mathcal{P}(S)} e^{TN \langle \hat{f}, \nu \rangle} dQ_N(\nu) \\ = \ & e^{-TN\delta} \left(\int_S e^{T f(x)} d\mu(x) \right)^N \end{align}

となります。ここで $\{f_n\}_{n=1}^{\infty}$ を $C_{b, \mathbb{R}}(S)$ の一様有界な関数列で、$\mu – \mathrm{a.e.}$ ($\mu$ についてほとんど至る所) で $0$ に各点収束するものとします。このときルベーグの収束定理から

$$\lim_{n \to \infty} \int_S e^{T f_n(x)} d\mu(x) = \int_S \lim_{n \to \infty} e^{T f_n(x)} d\mu(x) = 1$$

なので、$k \in \mathbb{N}$ に対して $\delta = 1 / k$, $T = k(k+1 + \log2)$ とし、$n_k \in \mathbb{N}$ を

$$\int_S e^{T f_{n_k}(x)} d\mu(x) < 2$$

を満たすようにとると、任意の $N$ に対して

\begin{align} & Q_{N}({\nu \in \mathcal{P}(S) \mid \langle \hat{f}_{n_k}, \nu \rangle \geq \frac{1}{k}}) \\ \leq \ & e^{-(k+1+\log2)N} \left(\int_S e^{T f_{n_k}(x)} d\mu(x) \right)^N \\ \leq \ & e^{-(k+1)N} \end{align}

が成り立ちます。

ここで $X$ はポーランド空間なので、$S$ 上のコンパクト集合の上昇列 $K_n$ で、$\mu(K_n) \to 1$ を満たすものがとれます。それに対し閉集合 $F_n \subset K_n^c$ で

$$\mu(K_n^c \setminus F_n) < \frac{1}{n}$$

を満たすものをとり、有界連続関数 $f_n$ を

$$0 \leq f_n(x) \leq 1 \ \ (x \in S), \quad f_n|_{K_n} = 0, \quad f_n|_{F_n} = 1$$

を満たすように取ります。$K_n$ の取り方から、$f_n$ は $\mu – \mathrm{a.e.}$ で $0$ に収束します。このとき、$\{f_n\}_{n=1}^{\infty}$ の部分列 $\{f_{n_k}\}_{k=1}^{\infty}$ をとると、

\begin{align} & Q_N \left( \left\{ \nu \in \mathcal{P}(S) \mid \nu(K_{n_k}^c) \geq \frac{2}{k} \right\} \right) \\ \leq \ & Q_N \left( \left\{ \nu \in \mathcal{P}(S) \mid \nu(F_{n_k}) \geq \frac{2}{k} -\frac{1}{n_k} \right\} \right) \\ \leq \ & Q_N \left( \left\{ \nu \in \mathcal{P}(S) \mid \hat{f}_{n_k}(\mu) \geq \frac{1}{k} \right\} \right) \\ \leq \ & e^{-(k+1)N} \end{align}

が成り立ちます。ここで、$L > 0$ に対して

$$C_L = \bigcap_{k \geq L} \left\{\nu \in \mathcal{P}(S) \mid \nu(K_{n_k}) \geq 1 -\frac{2}{k}\right\}$$

とおくと、

\begin{align} Q_N(C_L^c) &= Q_N\left(\bigcup_{k \geq L} \left\{\nu \in \mathcal{P}(S) \mid \nu(K_{n_k}^c) \geq \frac{2}{k} \right\}\right) \\ & \leq \sum_{k \geq L} e^{-(k+1)N} \\ & \leq e^{-LN} \end{align}

が成り立ちます。このとき

$$\frac{1}{N} \log Q_N(C_L^c) \leq -L$$

なので、$C_L$ がコンパクトであれば $\{Q_N\}_{N=1}^{\infty}$ は exponentially tight になります。

$S$ はポーランド空間なので、$C_L$ がコンパクトであるためには、タイトかつ閉であれば良いです。任意の $\varepsilon > 0$ に対して $k > \max\{1 / 2\varepsilon , L\}$ ととることで、任意の $\nu \in C_L$ に対して

$$\nu(K_{n_k}) > 1 -\varepsilon$$

が成り立つので $C_L$ はタイトです。$C_L$ が閉集合であるためには、

$$\left\{\nu \in \mathcal{P}(S) \mid \nu(K_{n_k}^c) \geq \frac{2}{k}\right\}$$

が閉集合であれば良いですが、$C_{b, \mathbb{R}}(S)$ の減少列 $g_m$ で $1_{K_{n_k}}$ に各点収束するものをとると、

\begin{align} & \left\{\nu \in \mathcal{P}(S) \mid \nu(K_{n_k}^c) \geq \frac{2}{k}\right\} \\ = \ & \bigcap_{m = 1}^{\infty}\left\{\nu \in \mathcal{P}(S) \mid \hat{g}_m(\nu) \geq \frac{2}{k}\right\} \\ = \ & \bigcap_{m = 1}^{\infty}\hat{g}_m^{-1}([\frac{2}{k}, \infty)) \\ \end{align}

となるので、$\hat{g}_m$ が連続であることから左辺が閉集合であることがわかり、$C_L$ が閉集合であることもわかります。

以上で $\{Q_N\}_{N=1}^{\infty}$ が exponentially tight であることがわかりました。

ルジャンドル変換と KL ダイバージェンス

ルジャンドル変換を用いて rate function を計算し、それが KL ダイバージェンスに一致することを示します。

rate function とルジャンドル変換

ルジャンドル変換を用いるための条件を満たすこと確認しましょう。以下の 5 つを満たす必要があります (詳しくはこちら)。

$\mathcal{P}(S)$ を含む $\mathbb{R}$ 上の局所凸空間 $X$ が存在する。
$\mathcal{P}(S) \subset \mathbb{R}$ は閉凸部分集合。
$\{Q_N\}_{N = 1}^{\infty}$ は $I$ を good rate function として大偏差原理を満たす。
$I$ は凸関数である。
任意の $\lambda \in X^*$ に対して $\lambda: E \to \mathbb{R}$ は有界。

これまで示してきたことから、3, 4 が成り立ちます。また、$\mathcal{M}_{\mathbb{R}}(S)$ を $S$ 上の符号付有限 Borel 測度全体とします。このとき、

$\mathcal{M}_{\mathbb{R}}(S)$ は $\mathbb{R}$ 上の局所凸空間 (詳しくはこちら)
$\mathcal{P}(S) \subset \mathcal{M}_{\mathbb{R}}(S)$ は閉凸部分集合 (詳しくはこちら)

が成り立ちます。よって任意の $\lambda \in \mathcal{M}_{\mathbb{R}}(S)^*$ に対して、$E$ への制限が有界であることがわかれば、ルジャンドル変換を適用できます。

$\mathcal{M}_{\mathbb{R}}(S)^* \simeq C_{b, \mathbb{R}}(S)$ なので (証明はこちら)、$\lambda = \hat{f}$ を満たす $f \in C_{b, \mathbb{R}}(S)$ が存在します。このとき、任意の $\nu \in \mathcal{P}(S)$ に対して

$$|\hat{f}(\nu)| = \left| \int_S f d \nu \right| \leq \max_{x \in S}|f(x)|$$

となるので、$\hat{f}$ は $\mathcal{P}(S)$ 上で有界です。

任意の $f \in C_{b, \mathbb{R}}(S)$ に対して

\begin{align} \frac{1}{N} \log \int_{\mathcal{P}(S)} e^{N \langle \hat{f}, \nu \rangle} d Q_N(\nu) = \log \int_S e^{f(x)} d\mu(x)\end{align}

なので、左辺の $N \to \infty$ 極限は存在します (そもそも $N$ によらない)。そこで、

$$\Lambda(f) =\log \int_S e^{f(x)} d\mu(x) $$

とおきます (キュムラント母関数に似ています)。$\nu \in \mathcal{P}(S)$ に対して

$$\Lambda^*(\nu) = \sup_{f \in C_{b, \mathbb{R}}(S)} \{\langle \hat{f}, \nu \rangle -\Lambda(f)\}$$

とおくと、$\{Q_N\}_{N=1}^{\infty}$ は $I$ を good rate function として大偏差原理を満たすので、$\Lambda^* = I$ が成り立ちます。

KL ダイバージェンスと $\Lambda^*$ が一致することを示せば、sanov の証明が完了しますが、その前に補題をいくつか証明します。

KL ダイバージェンスの近似

KL ダイバージェンスの定義において、もし

$$\mu(\{x \in S \mid \frac{d \nu}{d \mu}(x) = 0\}) > 0$$

を満たすと積分の中身の $\log (\frac{d \nu}{d \mu})$ の扱いがややこしくなるので、$D_{KL}(\nu || \mu) < \infty$ のときに、$\nu$ に弱収束する $\mathcal{P}(S)$ の列 $\{\nu_n\}_{n=1}^{\infty}$ で、

$$\mu(\{x \in S \mid \frac{d \nu_n}{d \mu}(x) \geq \frac{1}{n + 1} \}) = 1$$

かつ

$$\lim_{n \to \infty} D_{KL}(\nu_n || \mu) = D_{KL}(\nu || \mu)$$

を満たすものが存在することを示します。

可測関数 $g: S \to \mathbb{R}$ が $\mu – \mathrm{a.e.}$ で $g \geq 0$ を満たし、かつ

$$\int_S g d \mu = 1$$

を満たすとき、

$$\mu_g: \mathfrak{B}_S \ni A \mapsto \int_A f d \mu$$

は確率測度で、$$\mu_g \ll \mu$$ であることに注意します。

ここで、$g = \frac{d \nu}{d \mu}$ とおいて、$n \geq 1$ に対して

$$g^{\prime}_n(x) = \begin{cases} g(x) & (g(x) > \frac{1}{n}) \\ \frac{1}{n} & (g(x) \leq \frac{1}{n})\end{cases}$$

とします。このとき $\mu – \mathrm{a.e.}$ で $g^{\prime}_n(x) \geq g(x)$ であり、

\begin{align} 1 & \leq \int_S g^{\prime}_n d \mu \\ & = \int_{g^{-1}((\frac{1}{n}, \infty))} g(x) d\mu + \int_{g^{-1}( [0, \frac{1}{n}])} \frac{1}{n} d \mu\\ & \leq 1 + \frac{1}{n} \end{align}

が成り立ちます。ここで

$$g_n(x) = \frac{g^{\prime}_n(x)}{\int_S g^{\prime}_n d \mu }$$

とおくと、

$$g_n(x) \geq \frac{\frac{1}{n}}{1 + \frac{1}{n}} = \frac{1}{n + 1} \quad (\mu – \mathrm{a.e.})$$

となります。$\nu$ が確率測度なので、$g \geq 0$ $\mu – \mathrm{a.e.}$ であることに注意すると、$g_n$ は $g$ に概収束 ($\mu – \mathrm{a.e.}$ で各点収束) します。 $\nu_n = \mu_{g_n}$ とおくと、

$$D_{KL}(\nu_n || \mu) = \int_S g_n(x) \log (g_n(x)) d\mu(x)$$

です。ここで、$x \log x$ は 1 階微分が $\log x +1$ で、2 階微分が $x^{-1}$ なので、$x > 0$ で凸であり、$x = e^{-1}$ で最小値 $-e^{-1}$ を取ります。また、$x \leq 1$ で $x \log x \leq 0$ を満たします。よって

$$h(x) = \begin{cases}g(x) \log(g(x)) & (g(x) > 1) \\ 1 & (g(x) \leq 1)\end{cases}$$

とおくと、$\mu – \mathrm{a.e.}$ で $h(x) \geq 0$ かつ $|g_n(x) \log (g_n(x))| \leq h(x)$ であり、

\begin{align} \int_S h(x) d\mu &= \int_{g^{-1}((1, \infty))} g(x) \log (g (x)) d \mu(x) + \int_{g^{-1}([0, 1])} 1 d \mu \\ &\leq D_{KL}(\nu||\mu) + 1 \\ & < \infty \end{align}

なので、ルベーグの収束定理から

\begin{align} \lim_{n \to \infty} D_{KL}(\nu_n || \mu) &= \lim_{n \to \infty} \int_S g_n(x) \log g_n(x) d\mu \\ &= \int_S g(x) \log g(x) d \mu \\ &= D_{KL}(\nu || \mu) \end{align}

が成り立ちます。

最後に $\nu_n$ が $\nu$ に弱収束することを示します。任意の $f \in C_{b, \mathbb{R}}(S)$ に対して、

$$|f(x) g_n(x)| < ||f||_{\infty} \max\{g(x), 1\}$$

が成り立ち、右辺は可積分なので、ルベーグの収束定理から

\begin{align} \lim_{n \to \infty} \int_S f d \nu_n &= \lim_{n \to \infty}\int_S f g_n d \mu \\ &= \int_S f g d \mu \\ &= \int_S f d \nu \end{align}

が成り立ちます。よって $\nu_n$ は $\nu$ に弱収束します。

$L^1(S, \mu)$ の連続関数による近似

$\varphi \in L^1(S, \mu)$ ($\int_S |\varphi| d\mu < \infty$ を満たす実可測関数) に対して、 $C_{b, \mathbb{R}}(S)$ の列 $\{f_n\}_{n=1}^{\infty}$ で、$\varphi$ に概収束するものが存在することを示します。

証明は 2 段階に分かれます。

$L^1$ 収束する $C_{b, \mathbb{R}}(S)$ の列 $\{f_n\}_{n=1}^{\infty}$ を構成する。
$L^1$ 収束する列 $\{f_n\}_{n=1}^{\infty}$ に対して、概収束する部分列が存在する。

2 は多くの教科書に記載されていると思うので省略します (例えば [K 命題 5.7])。1 も教科書に載っていると思いますが、距離空間において示しているものは少ないかもしれないので、一応証明をします。1, 2 は $L^p$ $(1 \leq p < \infty)$ に対しても成り立ちます。

$A \in \mathfrak{B}_S$ と任意の $\varepsilon > 0$ に対して、

$$F \subset A \subset U, \quad \mu(U \setminus F) < \varepsilon$$

を満たす閉集合 $F$ と開集合 $U$ がとれます。また、連続関数 $f$ で、任意の $x \in S$ で $0 \leq f(x) \leq 1$ かつ $f|_{F} \equiv 1$, $f|_{S \setminus A} \equiv 0$ を満たすものが存在します。よって

$$\int_S |1_A -f| d \mu \leq \mu(U \setminus F) < \varepsilon$$

を満たすため、$1_A$ は連続関数により、$L^1$ の意味でいくらでも近似できます。同様にして単関数も連続関数により、$L^1$ の意味でいくらでも近似できます。

$\varphi \in L^1(S, \mu)$ を非負関数とし、単関数の増大列 $\varphi_n$ で、$\varphi$ に各点収束するものを取ります。$\varepsilon > 0$ を 1 つ固定します。このとき $|\varphi -\varphi_n|$ は減少列で、可積分関数 $\varphi$ により上から抑えられているので、ルベーグの収束定理から

$$\int_S |\varphi -\varphi_k| d \mu < \varepsilon$$

を満たす$k$ が存在します。単関数 $\varphi_k$ に対して

$$\int_S |\varphi_k -f| d \mu < \varepsilon$$

を満たす連続関数が存在するので

が成り立ちます。$\varepsilon > 0$ は任意なので、$\varphi$ は $L^1$ の意味でいくらでも近似できます。$\varphi$ が非負でない場合は、正と負に分けて同様の議論をすれば良いです。

特に $\varphi_k$ に対して

$$\int_S |\varphi_k -f_k| d \mu < \frac{\varepsilon}{k}$$

を満たす $f_k \in C_{b, \mathbb{R}}(S)$ をとれば、$f_k$ は $\varphi$ に $L^1$ 収束します。

$\Lambda^*(\nu) < \infty$ ならば $\nu \ll \mu$ である

まずは、$\Lambda^*(\nu) < \infty$ のときに $\nu$ は $\mu$ に絶対連続であることを示します。定義から、任意の $f \in C_{b, \mathbb{R}}(S)$ に対して

\begin{align} \Lambda^*(\nu) \geq \langle \hat{f}, \nu \rangle -\Lambda(f) & = \int_S f d \nu -\log\int_S e^f d \mu \end{align}

となります。$F \subset S$ を閉集合とし、$\mu(F) = 0$ とします。$\{f_n\}_{n=1}^{\infty}$ を $1_F$ に各点収束する $C_{b, \mathbb{R}}(S)$ の減少列とすると、ルベーグの収束定理から

$$\lim_{n \to \infty} \int_S f_n d \nu = \int_S 1_F d \nu = \nu(F)$$

\begin{align} \lim_{n \to \infty} \int_S e^{f_n} d \mu & = \int_S e^{1_F} d \mu\\ & = \int_F e d \mu + \int_{S \setminus F} 1_{S \setminus F} d \mu \\ &= e \mu(F) + \mu(S \setminus F) \\ & = 1 \end{align}

となります。よって任意の $a > 0$ に対して $\{a f_n\}_{n=1}^{\infty}$ の極限をとると、

$$a \nu(F) \leq \Lambda^*(\nu)$$

となり、$\nu(F) \neq 0$ ならば $a$ を十分大きくとることで不等式が成立しなくなるので、$\nu(F) = 0$ となります。

$A \subset \mathfrak{B}_S$ を任意の Borel 可測集合とし、$\mu(A) = 0$ とします。このとき、$S$ は距離空間なので、任意の $n \geq 1$ に対して開集合 $U_n \subset S$ と閉集合 $F_n \subset S$ で、

$$F_n \subset A_n \subset U_n, \quad \nu(U_n \setminus F) < \frac{1}{n}$$

を満たすものが存在します。$F_n \subset A$ なので、$\mu(F_n) = 0$ から $\nu(F_n) = 0$ が従い、よって $\nu(U_n) < 1 / n$ となります。このとき

$$\nu(A) \leq \lim_{n \to \infty} \nu(\bigcap_{i=1}^{n} U_i) \leq \lim_{n \to \infty} \frac{1}{n} = 0$$

となるため、$\nu$ は $\mu$ に絶対連続です。

KL ダイバージェンスと rate function の一致

準備が長くなりましたが、ようやく $\Lambda^*(\nu) = D_{KL}(\nu || \mu)$ の証明に取り掛かります。

$\Lambda^*(\nu) \leq D_{KL}(\nu || \mu)$ であること

任意の $\nu \in \mathcal{P}(S)$ に対して

$$\Lambda^*(\nu) \leq D_{KL}(\nu || \mu)$$

が成り立つことを示します。$D_{KL}(\nu || \mu) = \infty$ ならば不等式は常に成立するので、$D_{KL}(\nu || \mu) < \infty$ であるとします。

まず、$\theta > 0$ が存在して、$\frac{d \nu}{d \mu} \geq \theta$ が成り立つ場合を考えます。このとき、任意の $f \in C_{b, \mathbb{R}}(S)$ に対して

$$\langle \hat{f}, \nu \rangle -D_{KL}(\nu || \mu) = \int_S f -\log \frac{d \nu}{d \mu} d\nu$$

なので、Jensen の不等式から

\begin{align} e^{\langle \hat{f}, \nu \rangle -D_{KL}(\nu||\mu)} & \leq \int_S e^{f -\log \frac{d \nu}{d \mu}} d\nu \\ &= \int_S e^f (\frac{d \nu}{d \mu})^{-1} d \nu \\ &= \int_S e^f d\mu \end{align}

となります。よって

$$\langle \hat{f}, \nu \rangle -\int_S e^f d\mu \leq D_{KL}(\nu || \mu)$$

となり、左辺の $\sup$ をとることで $\Lambda^*(\nu) \leq D_{KL}(\nu || \mu)$ がわかります。

$\frac{d \nu}{d \mu} \geq \theta$ を満たす $\theta > 0$ が存在しない場合は、$\frac{d \nu_n}{d \mu} > \theta_n > 0$ を満たし、$\nu$ に弱収束する列 $\{\nu_n\}_{n=1}^{\infty}$ をとると、

\begin{align} \langle \hat{f}, \nu \rangle -\int_S e^f d\mu &= \lim_{n \to \infty} \langle \hat{f}, \nu_n \rangle -\int_S e^f d\mu \\ &\leq \lim_{n \to \infty} D_{KL}(\nu_n || \mu)\\ &= D_{KL}(\nu || \mu) \end{align}

となります。

$D_{KL}(\nu || \mu) \leq \Lambda^*(\nu)$ であること

任意の $\nu \in \mathcal{P}(S)$ に対して

$$D_{KL}(\nu || \mu) \leq \Lambda^*(\nu)$$

が成り立つことを示します。$\Lambda^*(\nu) = \infty$ ならば不等式は常に成立するので、$\Lambda^*(\nu) < \infty$ であるとします。このとき、上で示したように $\nu \ll \mu$ となります。

$\frac{d \nu}{d \mu} > \theta$ を満たす $\theta > 0$ が存在するとします。$\frac{d \nu}{d \mu}$ が有界の場合は、$C_{b, \mathbb{R}}(S)$ の元で $\log \frac{d \nu}{d \mu}$ を近似することで

\begin{align} \Lambda^*(\nu) & \geq \langle \log \frac{d \nu}{d \mu}, \nu \rangle -\log \int_S e^{\log \frac{d \nu}{d \mu}} d\mu \\ &= \int_S \log \frac{d \nu}{d \mu} d\nu -\log \int_S \frac{d \nu}{d \mu} d\mu \\ &= \int_S \frac{d \nu}{d \nu} \log \frac{d \nu}{d \mu} d\mu \\ &= D_{KL}(\nu || \mu) \end{align}

となります。

$\frac{d \nu}{d \mu}$ が有界でない場合は、

$$g_n(x) = \min \left\{ \frac{d \nu}{d \mu}(x) , n \right\}$$

とおくと $g_n$ は $\frac{d \nu}{d \mu}(x)$ に各点収束し、

$$\Lambda^*(\nu) \geq \int_S \log g_n d\nu -\log \int_S g_n d\mu$$

となりますが、$|g_n(x)| \leq \frac{d \nu}{d \mu}(x)$ 、$\log g_n -\log \theta \geq 0$ が成り立つことに注意すると、Fatou の補題から

\begin{align} & \liminf_{n \to \infty} \left(\int_S \log g_n d\nu -\log \int_S g_n d\mu \right) -\log \theta \\ = \ & \liminf_{n \to \infty} \int_S ( \log g_n -\log \theta) d\nu -\log \lim_{n \to \infty} \int_S g_n d\mu \\ \geq \ & \int_S \liminf_{n \to \infty} (\log g_n -\log \theta) d\nu \\ = \ & \int_S \log \frac{d \mu}{d \nu} d\nu -\log \theta \\ = \ & D_{KL}(\nu || \mu) -\log \theta \end{align}

となるので、

$$\Lambda^*(\nu) \geq D_{KL}(\nu || \mu)$$

が成り立ちます。

$\frac{d \nu}{d \mu} > \theta$ を満たす $\theta > 0$ が存在しない場合は、$\frac{d \nu_n}{d \mu} > \theta_n > 0$ を満たし、$\nu$ に弱収束する列 $\{\nu_n\}_{n=1}^{\infty}$ をとれば良いです。

大数の法則

最後に sanov の定理の応用として、 $N \to \infty$ で

$$Q_N \to \delta_{\mu} \quad (弱収束)$$

が成り立つことを示します。おさらいすると、$\{Y_i\}_{i = 1}^{\infty}$ を独立同分布な $S$ 値確率変数とし、$\delta_{Y_i}$ を以下の写像

$$\Omega_i \xrightarrow{Y_i} S \xrightarrow{\iota} \mathcal{P}(S)$$

の合成とすると、$Q_N$ は

$$\frac{\delta_{Y_1} + \cdots + \delta_{Y_N}}{N}$$

の分布と一致するのでした。もし $Q_N \to \delta_{\mu}$ とすると、$f \in C_{b, \mathbb{R}}(S)$ に対して $\hat{f}_*(Q_N)$ は $\hat{f}_*(\mu)$ に弱収束するので (像測度の積分の性質を用いて素直に計算すれば良い)、

\begin{align} \hat{f}(\frac{\delta_{Y_1} + \cdots + \delta_{Y_N}}{N}) &= \frac{f(Y_1) + \cdots + f(Y_N)}{N} \\ & \to \hat{f}(\delta_{\mu}) \\ & = \int_S f d \mu \end{align}

となり、大数の弱法則が成り立ちます。よって

$$Q_N \to \delta_{\mu} \quad (弱収束)$$

は $S$ 値確率変数版の大数の法則といえます。

$D_{KL}$ の正値性

まず準備として、$D_{KL}(\nu || \mu) \geq 0$ かつ $D_{KL}(\nu || \mu) = 0$ ならば $\nu = \mu$ を満たすことを示します。$x \log x$ は凸関数なので、Jensen の不等式から

\begin{align} D_{KL}(\nu || \mu) & = \int_S \frac{d \nu}{d\mu} \log \frac{d \nu}{d\mu} d\mu \\ & \geq (\int_S \frac{d \nu}{d\mu} d \mu) \log (\int_S \frac{d \nu}{d\mu} d \mu)\\ &= 0 \end{align}

となります。また、

$$g(x) = x \log x -x +1$$

は凸関数で $x = 1$ で最小値 $0$をとり、$x \neq 1$ のとき $g(x) > 0$ なので、

$$\mu(\{x \in S \mid \frac{d\nu}{d \mu}(x) \neq 1\}) > 0$$

ならば

$$\int_S \frac{d \nu}{d\mu} \log \frac{d \nu}{d\mu} d\mu > \int_S \frac{d \nu}{d\mu} -1 d\mu = 0 $$

となります。よって $D_{KL}(\nu || \mu) = 0$ ならば $\mu – \mathrm{a.e.}$ で $\frac{d \nu}{d \mu} = 1$ なので、$\nu = \mu$ となります。

$\{Q_N\}_{N=1}^{\infty}$ が $\delta_{\mu}$ に弱収束すること

$\mu \notin F$ を満たす任意の閉集合 $F \subset \mathcal{P}(S)$ に対して、sanov の定理から

$$\limsup_{N \to \infty} \frac{1}{N} \log Q_N(F) \leq -\inf_{\nu \in F} D_{KL}(\nu || \mu) < 0$$

が成り立ちます。よって任意 $\varepsilon > 0$ に対して、$N_0 > 0$ が存在して、$N > N_0$ ならば

$$\frac{1}{N} \log Q_N(F) < -\varepsilon$$

が成り立ちます。このとき

$$Q_N(F) < e^{-\varepsilon N}$$

なので、

$$ \limsup_{N \to \infty} Q_N(F) \geq \limsup_{N \to \infty} e^{-\varepsilon N} = 0$$

が成り立ちます。ここで、$\delta_{\mu}(F) = 0$ なので、

$$ \limsup_{N \to \infty} Q_N(F) \geq \delta_{\mu}(F)$$

が成り立ちます。$\mu \in F$ を満たす開集合に対しても

$$ \liminf_{N \to \infty} Q_N(F) \geq \delta_{\mu}(F) = 1$$

なので、弱収束と同値な条件を満たし (証明はこちら)、$\{Q_N\}_{N=1}^{\infty}$ は $\delta_{\mu}$ に弱収束します。

まとめ

本記事では sanov の定理を証明しました。sanov の定理は統計的推論におけるKLダイバージェンスの最小化 (= 尤度の最大化) の意味を理解するのに必須の定理です。そのあたりの説明は別の記事で行う予定です。

sanov の定理の応用として、大数の法則を示しました。大偏差原理は中心から外れたところでの漸近挙動について述べたものですが、実は中心の漸近挙動についても調べることができます。ただし、証明を見れば分かる通り、大偏差原理の一部しか用いていません。おそらくより弱い条件で示すことができるのでしょう。ちなみにKLダイバージェンスの最小化の意味を述べるときには、中心から外れたところでの漸近挙動が重要になります。

参考文献

[TC] 田村要造, 千代延大造. 大偏差原理

[K] 小谷眞一. 測度と確率

Wikipedia: Subadditivity

[C] Cosma Shalizi. Stochastic Processes [Chapter 30 General Theory of Large Deviations]

[S] J.M. Swart. Large Deviation Theory

sanov の定理の拡張とクラメールの定理

sanov の定理の証明

sanov の定理の主張

確率測度の族

KL ダイバージェンス

sanov の定理の主張

定理. sanov の定理

証明の流れ

弱い意味での大偏差原理の成立

開球に対する $Q_{N}$ の漸近挙動

$\mathcal{L}(B)$ の存在

rate function の構成と凸性

exponentially tight であること

ルジャンドル変換と KL ダイバージェンス

rate function とルジャンドル変換

KL ダイバージェンスの近似

$L^1(S, \mu)$ の連続関数による近似

$\Lambda^*(\nu) < \infty$ ならば $\nu \ll \mu$ である

KL ダイバージェンスと rate function の一致

$\Lambda^*(\nu) \leq D_{KL}(\nu || \mu)$ であること

$D_{KL}(\nu || \mu) \leq \Lambda^*(\nu)$ であること

大数の法則

$D_{KL}$ の正値性

$\{Q_N\}_{N=1}^{\infty}$ が $\delta_{\mu}$ に弱収束すること

まとめ

参考文献

関連記事

最近の投稿

カテゴリー

アーカイブ

目次

sanov の定理の主張

確率測度の族

KL ダイバージェンス

sanov の定理の主張

定理. sanov の定理

証明の流れ

弱い意味での大偏差原理の成立

開球に対する $Q_{N}$ の漸近挙動

$\mathcal{L}(B)$ の存在

rate function の構成と凸性

exponentially tight であること

ルジャンドル変換と KL ダイバージェンス

rate function とルジャンドル変換

KL ダイバージェンスの近似

$L^1(S, \mu)$ の連続関数による近似

$\Lambda^*(\nu) < \infty$ ならば $\nu \ll \mu$ である

KL ダイバージェンスと rate function の一致

$\Lambda^*(\nu) \leq D_{KL}(\nu || \mu)$ であること

$D_{KL}(\nu || \mu) \leq \Lambda^*(\nu)$ であること

大数の法則

$D_{KL}$ の正値性

$\{Q_N\}_{N=1}^{\infty}$ が $\delta_{\mu}$ に弱収束すること

まとめ

参考文献

関連記事

人気の記事

最近の投稿

カテゴリー

アーカイブ

目次