相対エントロピーから情報と物理を組み立てる 第1部 第8章 §1.8.2 ★★★ 経験分布が集合 E E E E E E D ( p ∥ q ) D(p\|q) D ( p ∥ q )
型の集合へ広げる
前節は型を1つに決めた。実際に問いたいのは「表の割合が 0.7 0.7 0.7 E E E E E E ( n + 1 ) ∣ X ∣ (n+1)^{\lvert \mathcal X\rvert } ( n + 1 ) ∣ X ∣ E E E
定理 1.8.3（Sanov の定理 ★★★）
E E E X \mathcal X X X 1 , … , X n X_1,\dots,X_n X 1 , … , X n q q q
q n ( p X n ∈ E ) ≤ ( n + 1 ) ∣ X ∣ e − n D ( p ∗ ∥ q ) , D ( p ∗ ∥ q ) = inf p ∈ E D ( p ∥ q ) (1.8.6) q^n\bigl(p_{X^n}\in E\bigr)\le(n+1)^{\lvert \mathcal X\rvert }\,\mathrm{e}^{-nD(p^*\|q)},\qquad D(p^*\|q)=\inf_{p\in E}D(p\|q)\tag{1.8.6} q n ( p X n ∈ E ) ≤ ( n + 1 ) ∣ X ∣ e − n D ( p ∗ ∥ q ) , D ( p ∗ ∥ q ) = p ∈ E inf D ( p ∥ q ) ( 1.8.6 )
が成り立つ。さらに E E E
lim n → ∞ 1 n ln q n ( p X n ∈ E ) = − min p ∈ E D ( p ∥ q ) . (1.8.7) \lim_{n\to\infty}\frac1n\ln q^n\bigl(p_{X^n}\in E\bigr)=-\min_{p\in E}D(p\|q).\tag{1.8.7} n → ∞ lim n 1 ln q n ( p X n ∈ E ) = − p ∈ E min D ( p ∥ q ) . ( 1.8.7 )
証明 上界：q n ( p X n ∈ E ) = ∑ p ∈ E ∩ P n q n ( T n ( p ) ) ≤ ∑ p ∈ E ∩ P n e − n D ( p ∥ q ) q^n(p_{X^n}\in E)=\sum_{p\in E\cap\mathcal P_n}q^n(T_n(p))\le\sum_{p\in E\cap\mathcal P_n}\mathrm{e}^{-nD(p\|q)} q n ( p X n ∈ E ) = ∑ p ∈ E ∩ P n q n ( T n ( p )) ≤ ∑ p ∈ E ∩ P n e − n D ( p ∥ q ) e − n D ( p ∗ ∥ q ) \mathrm{e}^{-nD(p^*\|q)} e − n D ( p ∗ ∥ q ) (1.8.2) で ( n + 1 ) ∣ X ∣ (n+1)^{\lvert \mathcal X\rvert } ( n + 1 ) ∣ X ∣
下界：E E E p p p P n \mathcal P_n P n 1 / n 1/n 1/ n n n n p p p E E E p n ∈ P n p_n\in\mathcal P_n p n ∈ P n p n → p p_n\to p p n → p (1.8.5) から q n ( p X n ∈ E ) ≥ q n ( T n ( p n ) ) ≥ ( n + 1 ) − ∣ X ∣ e − n D ( p n ∥ q ) q^n(p_{X^n}\in E)\ge q^n(T_n(p_n))\ge(n+1)^{-\lvert \mathcal X\rvert }\mathrm{e}^{-nD(p_n\|q)} q n ( p X n ∈ E ) ≥ q n ( T n ( p n )) ≥ ( n + 1 ) − ∣ X ∣ e − n D ( p n ∥ q ) D ( ⋅ ∥ q ) D(\cdot\|q) D ( ⋅ ∥ q ) lim inf 1 n ln q n ( p X n ∈ E ) ≥ − D ( p ∥ q ) \liminf\frac1n\ln q^n(p_{X^n}\in E)\ge-D(p\|q) lim inf n 1 ln q n ( p X n ∈ E ) ≥ − D ( p ∥ q ) E E E p p p E E E − min p ∈ E D ( p ∥ q ) -\min_{p\in E}D(p\|q) − min p ∈ E D ( p ∥ q ) (1.8.7) を得る。
この定理の名前は I. N. Sanov に由来する1 1 I. N. Sanov (1957), Mat. Sbornik 42 (84), 11–44。e − n D \mathrm{e}^{-nD} e − n D
Sanov の定理の読み方
めったに起きないことが起きるとき、それは「最もありそうな起こり方」1つでほぼ起きる。その起こり方は、E E E q q q D D D p ∗ p^* p ∗ e − n D ( p ∗ ∥ q ) \mathrm{e}^{-nD(p^*\|q)} e − n D ( p ∗ ∥ q ) p ∗ p^* p ∗ p ∗ p^* p ∗ 1.8.4 節で示す）。
I 射影
E E E D ( p ∥ q ) D(p\|q) D ( p ∥ q ) p p p 第1部第3章 ）なので、最小を与える p ∗ p^* p ∗ q q q E E E I 射影 （information projection）と呼ぶ。名前は、ユークリッド空間で点から凸集合へ最短距離の点をとる射影に対応させたものである。射影との対応は名前だけでなく、次の不等式も成り立つ。
命題 1.8.4（Pythagoras の不等式 ★★）
E E E p ∗ p^* p ∗ q q q E E E D ( p ∗ ∥ q ) < ∞ D(p^*\|q)<\infty D ( p ∗ ∥ q ) < ∞ p ∈ E p\in E p ∈ E
D ( p ∥ q ) ≥ D ( p ∥ p ∗ ) + D ( p ∗ ∥ q ) . (1.8.8) D(p\|q)\ge D(p\|p^*)+D(p^*\|q).\tag{1.8.8} D ( p ∥ q ) ≥ D ( p ∥ p ∗ ) + D ( p ∗ ∥ q ) . ( 1.8.8 )
証明 p t = ( 1 − t ) p ∗ + t p ∈ E p_t=(1-t)p^*+tp\in E p t = ( 1 − t ) p ∗ + tp ∈ E 0 ≤ t ≤ 1 0\le t\le1 0 ≤ t ≤ 1 p ∗ p^* p ∗ d d t D ( p t ∥ q ) ∣ t = 0 + ≥ 0 \frac{\mathrm{d} }{\mathrm{d} t}D(p_t\|q)\big|_{t=0^+}\ge0 d t d D ( p t ∥ q ) t = 0 + ≥ 0 d d t D ( p t ∥ q ) = ∑ x ( p ( x ) − p ∗ ( x ) ) ( ln p t ( x ) q ( x ) + 1 ) \frac{\mathrm{d} }{\mathrm{d} t}D(p_t\|q)=\sum_x(p(x)-p^*(x))\bigl(\ln\frac{p_t(x)}{q(x)}+1\bigr) d t d D ( p t ∥ q ) = ∑ x ( p ( x ) − p ∗ ( x )) ( ln q ( x ) p t ( x ) + 1 ) ∑ x ( p − p ∗ ) = 0 \sum_x(p-p^*)=0 ∑ x ( p − p ∗ ) = 0 t = 0 t=0 t = 0 ∑ x ( p ( x ) − p ∗ ( x ) ) ln p ∗ ( x ) q ( x ) ≥ 0 \sum_x(p(x)-p^*(x))\ln\frac{p^*(x)}{q(x)}\ge0 ∑ x ( p ( x ) − p ∗ ( x )) ln q ( x ) p ∗ ( x ) ≥ 0 ∑ x p ( x ) ln p ∗ ( x ) q ( x ) ≥ D ( p ∗ ∥ q ) \sum_xp(x)\ln\frac{p^*(x)}{q(x)}\ge D(p^*\|q) ∑ x p ( x ) ln q ( x ) p ∗ ( x ) ≥ D ( p ∗ ∥ q ) D ( p ∥ q ) − D ( p ∥ p ∗ ) = ∑ x p ( x ) ln p ∗ ( x ) q ( x ) D(p\|q)-D(p\|p^*)=\sum_xp(x)\ln\frac{p^*(x)}{q(x)} D ( p ∥ q ) − D ( p ∥ p ∗ ) = ∑ x p ( x ) ln q ( x ) p ∗ ( x ) (1.8.8) が従う。
不等式 (1.8.8) は、q q q E E E p p p D D D q q q p ∗ p^* p ∗ p ∗ p^* p ∗ p p p E E E 1.8.3 節の線形の集合（平均を決めた集合）のときは等号が成り立つ。
例題 1.8.2 表の割合が0.7以上になる確率 ★★
オリジナル 公平な硬貨を n n n 0.7 0.7 0.7 P n P_n P n
Sanov の定理から lim n → ∞ − 1 n ln P n \lim_{n\to\infty}-\frac1n\ln P_n lim n → ∞ − n 1 ln P n
n = 100 n=100 n = 100 n = 1000 n=1000 n = 1000 P n P_n P n P 100 = 3.93 × 10 − 5 P_{100}=3.93\times10^{-5} P 100 = 3.93 × 1 0 − 5 P 1000 = 8.83 × 10 − 38 P_{1000}=8.83\times10^{-38} P 1000 = 8.83 × 1 0 − 38 − 1 n ln P n -\frac1n\ln P_n − n 1 ln P n
解答 (1) E = { p : p ( 表 ) ≥ 0.7 } E=\{p:p(\text{表})\ge0.7\} E = { p : p ( 表 ) ≥ 0.7 } q = ( 0.5 , 0.5 ) q=(0.5,0.5) q = ( 0.5 , 0.5 ) E E E D ( p ∥ q ) = ln 2 − h b ( p ( 表 ) ) D(p\|q)=\ln2-h_{\mathrm b}(p(\text{表})) D ( p ∥ q ) = ln 2 − h b ( p ( 表 )) p ( 表 ) > 0.5 p(\text{表})>0.5 p ( 表 ) > 0.5 E E E p ∗ = ( 0.7 , 0.3 ) p^*=(0.7,0.3) p ∗ = ( 0.7 , 0.3 ) lim − 1 n ln P n = D ( p ∗ ∥ q ) = 0.0823 \lim-\frac1n\ln P_n=D(p^*\|q)=0.0823 lim − n 1 ln P n = D ( p ∗ ∥ q ) = 0.0823 0.8 0.8 0.8 0.9 0.9 0.9 E E E P n P_n P n
(2) − 1 100 ln ( 3.93 × 10 − 5 ) = 0.101 -\frac1{100}\ln(3.93\times10^{-5})=0.101 − 100 1 ln ( 3.93 × 1 0 − 5 ) = 0.101 − 1 1000 ln ( 8.83 × 10 − 38 ) = 0.0853 -\frac1{1000}\ln(8.83\times10^{-38})=0.0853 − 1000 1 ln ( 8.83 × 1 0 − 38 ) = 0.0853 0.0823 0.0823 0.0823 n n n ( n + 1 ) ∣ X ∣ (n+1)^{\lvert \mathcal X\rvert } ( n + 1 ) ∣ X ∣ O ( ln n / n ) \mathcal{O}(\ln n/n) O ( ln n / n )
例題 1.8.3 3つの記号での I 射影 ★
オリジナル X = { a , b , c } \mathcal X=\{a,b,c\} X = { a , b , c } q = ( 1 3 , 1 3 , 1 3 ) q=(\tfrac13,\tfrac13,\tfrac13) q = ( 3 1 , 3 1 , 3 1 ) E = { p : p ( a ) ≥ 1 2 } E=\{p:p(a)\ge\tfrac12\} E = { p : p ( a ) ≥ 2 1 } q q q E E E p ∗ p^* p ∗ D ( p ∗ ∥ q ) D(p^*\|q) D ( p ∗ ∥ q )
解答 q ∉ E q\notin E q ∈ / E p ( a ) = 1 2 p(a)=\tfrac12 p ( a ) = 2 1 1 2 \tfrac12 2 1 b b b c c c s s s 1 2 − s \tfrac12-s 2 1 − s D = 1 2 ln 3 2 + s ln ( 3 s ) + ( 1 2 − s ) ln ( 3 ( 1 2 − s ) ) D=\tfrac12\ln\tfrac32+s\ln(3s)+(\tfrac12-s)\ln(3(\tfrac12-s)) D = 2 1 ln 2 3 + s ln ( 3 s ) + ( 2 1 − s ) ln ( 3 ( 2 1 − s )) s s s 0 0 0 ln s = ln ( 1 2 − s ) \ln s=\ln(\tfrac12-s) ln s = ln ( 2 1 − s ) s = 1 4 s=\tfrac14 s = 4 1 p ∗ = ( 1 2 , 1 4 , 1 4 ) p^*=(\tfrac12,\tfrac14,\tfrac14) p ∗ = ( 2 1 , 4 1 , 4 1 ) D ( p ∗ ∥ q ) = 1 2 ln 3 2 + 1 2 ln 3 4 = 0.0589 D(p^*\|q)=\tfrac12\ln\tfrac32+\tfrac12\ln\tfrac34=0.0589 D ( p ∗ ∥ q ) = 2 1 ln 2 3 + 2 1 ln 4 3 = 0.0589 b b b c c c q q q 1 : 1 1:1 1 : 1 1.8.3 節の指数型の傾きの特別な場合（f f f a a a
1 I. N. Sanov (1957), Mat. Sbornik 42 (84), 11–44。
AI（Claude）が書いた教材を、木下が勉強しながら公開しています。式と数値は検算していますが、誤りが残っているかもしれません。誤りのご指摘・削除のご依頼をいただければ直します。 連絡先：support@tecktom.com
