相対エントロピーから情報と物理を組み立てる 第1部 第6章 §1.6.4 ★★ 容量の計算を2つの最大化の交互の繰り返しに分ける。どちらの段も D ≥ 0 D\ge0 D ≥ 0
一般の通信路では条件 (1.6.8) を手で解くことができない。Blahut と Arimoto は同じ年に、容量を数値で求める反復法を独立に発表した1 1 S. Arimoto (1972), IEEE Transactions on Information Theory 18 , 14–20；R. E. Blahut (1972), IEEE Transactions on Information Theory 18 , 460–473.D ≥ 0 D\ge0 D ≥ 0
補助の分布を入れて最大化を2つに分ける
入力 p p p y y y P ( x ∣ y ) = p ( x ) W ( y ∣ x ) / q ( y ) P(x\,|\,y)=p(x)W(y\,|\,x)/q(y) P ( x ∣ y ) = p ( x ) W ( y ∣ x ) / q ( y ) Y \mathcal Y Y X \mathcal X X Φ ( x ∣ y ) \Phi(x\,|\,y) Φ ( x ∣ y )
F ( p , Φ ) = ∑ x , y p ( x ) W ( y ∣ x ) ln Φ ( x ∣ y ) p ( x ) (1.6.16) F(p,\Phi)=\sum_{x,y}p(x)W(y\,|\,x)\ln\frac{\Phi(x\,|\,y)}{p(x)}\tag{1.6.16} F ( p , Φ ) = x , y ∑ p ( x ) W ( y ∣ x ) ln p ( x ) Φ ( x ∣ y ) ( 1.6.16 )
を考える。Φ \Phi Φ P P P P ( x ∣ y ) p ( x ) = W ( y ∣ x ) q ( y ) \frac{P(x|y)}{p(x)}=\frac{W(y|x)}{q(y)} p ( x ) P ( x ∣ y ) = q ( y ) W ( y ∣ x ) F ( p , P ) = I ( p , W ) F(p,P)=I(p,W) F ( p , P ) = I ( p , W )
補題 1.6.13（2つの段はどちらも D ≥ 0 D\ge0 D ≥ 0
(a) p p p F ( p , Φ ) = I ( p , W ) − ∑ y q ( y ) D ( P ( ⋅ ∣ y ) ∥ Φ ( ⋅ ∣ y ) ) F(p,\Phi)=I(p,W)-\sum_yq(y)\,D\bigl(P(\cdot\,|\,y)\,\big\|\,\Phi(\cdot\,|\,y)\bigr) F ( p , Φ ) = I ( p , W ) − ∑ y q ( y ) D ( P ( ⋅ ∣ y ) Φ ( ⋅ ∣ y ) ) max Φ F ( p , Φ ) = I ( p , W ) \max_\Phi F(p,\Phi)=I(p,W) max Φ F ( p , Φ ) = I ( p , W ) Φ = P \Phi=P Φ = P (b) Φ \Phi Φ c ( x ) = ∑ y W ( y ∣ x ) ln Φ ( x ∣ y ) c(x)=\sum_yW(y\,|\,x)\ln\Phi(x\,|\,y) c ( x ) = ∑ y W ( y ∣ x ) ln Φ ( x ∣ y ) Z = ∑ x e c ( x ) Z=\sum_x\mathrm{e}^{c(x)} Z = ∑ x e c ( x ) p ~ ( x ) = e c ( x ) / Z \tilde p(x)=\mathrm{e}^{c(x)}/Z p ~ ( x ) = e c ( x ) / Z F ( p , Φ ) = ln Z − D ( p ∥ p ~ ) F(p,\Phi)=\ln Z-D(p\,\|\,\tilde p) F ( p , Φ ) = ln Z − D ( p ∥ p ~ ) p p p p = p ~ p=\tilde p p = p ~ ln Z \ln Z ln Z
証明 (a) ln Φ p = ln P p − ln P Φ \ln\frac{\Phi}{p}=\ln\frac{P}{p}-\ln\frac{P}{\Phi} ln p Φ = ln p P − ln Φ P I ( p , W ) I(p,W) I ( p , W ) p ( x ) W ( y ∣ x ) = q ( y ) P ( x ∣ y ) p(x)W(y\,|\,x)=q(y)P(x\,|\,y) p ( x ) W ( y ∣ x ) = q ( y ) P ( x ∣ y ) ∑ y q ( y ) ∑ x P ( x ∣ y ) ln P ( x ∣ y ) Φ ( x ∣ y ) \sum_yq(y)\sum_xP(x\,|\,y)\ln\frac{P(x|y)}{\Phi(x|y)} ∑ y q ( y ) ∑ x P ( x ∣ y ) ln Φ ( x ∣ y ) P ( x ∣ y ) F = ∑ x p ( x ) ( c ( x ) − ln p ( x ) ) = ∑ x p ( x ) ( ln Z + ln p ~ ( x ) − ln p ( x ) ) = ln Z − D ( p ∥ p ~ ) F=\sum_xp(x)\bigl(c(x)-\ln p(x)\bigr)=\sum_xp(x)\bigl(\ln Z+\ln\tilde p(x)-\ln p(x)\bigr)=\ln Z-D(p\,\|\,\tilde p) F = ∑ x p ( x ) ( c ( x ) − ln p ( x ) ) = ∑ x p ( x ) ( ln Z + ln p ~ ( x ) − ln p ( x ) ) = ln Z − D ( p ∥ p ~ )
容量は C = max p max Φ F ( p , Φ ) C=\max_p\max_\Phi F(p,\Phi) C = max p max Φ F ( p , Φ ) Φ \Phi Φ p p p p k p_k p k Φ k = P k \Phi_k=P_k Φ k = P k p k p_k p k p k + 1 = p ~ p_{k+1}=\tilde p p k + 1 = p ~ Φ k \Phi_k Φ k c ( x ) c(x) c ( x ) q k = p k W q_k=p_kW q k = p k W c ( x ) = ∑ y W ( y ∣ x ) ln p k ( x ) W ( y ∣ x ) q k ( y ) = ln p k ( x ) + D ( W x ∥ q k ) c(x)=\sum_yW(y\,|\,x)\ln\frac{p_k(x)W(y|x)}{q_k(y)}=\ln p_k(x)+D(W_x\,\|\,q_k) c ( x ) = ∑ y W ( y ∣ x ) ln q k ( y ) p k ( x ) W ( y ∣ x ) = ln p k ( x ) + D ( W x ∥ q k )
定理 1.6.14（Blahut–Arimoto の反復 ★★）
すべての x x x p 0 ( x ) > 0 p_0(x)>0 p 0 ( x ) > 0
p k + 1 ( x ) = p k ( x ) e D ( W x ∥ q k ) ∑ x ′ p k ( x ′ ) e D ( W x ′ ∥ q k ) , q k = p k W (1.6.17) p_{k+1}(x)=\frac{p_k(x)\,\mathrm{e}^{D(W_x\|q_k)}}{\sum_{x'}p_k(x')\,\mathrm{e}^{D(W_{x'}\|q_k)}},\qquad q_k=p_kW\tag{1.6.17} p k + 1 ( x ) = ∑ x ′ p k ( x ′ ) e D ( W x ′ ∥ q k ) p k ( x ) e D ( W x ∥ q k ) , q k = p k W ( 1.6.17 )
を繰り返す。このとき
L k ≔ I ( p k , W ) ≤ C ≤ U k ≔ max x D ( W x ∥ q k ) , (1.6.18) L_k\coloneqq I(p_k,W)\ \le\ C\ \le\ U_k\coloneqq\max_xD(W_x\,\|\,q_k),\tag{1.6.18} L k : = I ( p k , W ) ≤ C ≤ U k : = x max D ( W x ∥ q k ) , ( 1.6.18 )
L k L_k L k k k k L k L_k L k U k U_k U k C C C
証明の一部 式 (1.6.18) の左は容量の定義、右は式 (1.6.10) を r = q k r=q_k r = q k 1.6.13 の2つの段からL k + 1 = I ( p k + 1 , W ) = max Φ F ( p k + 1 , Φ ) ≥ F ( p k + 1 , Φ k ) = max p F ( p , Φ k ) ≥ F ( p k , Φ k ) = I ( p k , W ) = L k L_{k+1}=I(p_{k+1},W)=\max_\Phi F(p_{k+1},\Phi)\ge F(p_{k+1},\Phi_k)=\max_pF(p,\Phi_k)\ge F(p_k,\Phi_k)=I(p_k,W)=L_k L k + 1 = I ( p k + 1 , W ) = max Φ F ( p k + 1 , Φ ) ≥ F ( p k + 1 , Φ k ) = max p F ( p , Φ k ) ≥ F ( p k , Φ k ) = I ( p k , W ) = L k C C C
更新式 (1.6.17) は、条件 (1.6.8) と照らすと意味が分かる。平均の出力 q k q_k q k D ( W x ∥ q k ) D(W_x\,\|\,q_k) D ( W x ∥ q k ) D D D U k U_k U k L k L_k L k U k − L k U_k-L_k U k − L k
図 1.6.3 3入力3出力の通信路 W = ( 0.7 0.2 0.1 0.1 0.8 0.1 0.3 0.3 0.4 ) W=\bigl(\begin{smallmatrix}0.7&0.2&0.1\\0.1&0.8&0.1\\0.3&0.3&0.4\end{smallmatrix}\bigr) W = ( 0.7 0.1 0.3 0.2 0.8 0.3 0.1 0.1 0.4 ) C ≈ 0.3288 C\approx0.3288 C ≈ 0.3288 10 − 10 10^{-10} 1 0 − 10
図 1.6.3 の通信路では、最初の上下の幅は 0.082 0.082 0.082 1.1 × 10 − 3 1.1\times10^{-3} 1.1 × 1 0 − 3 p ∗ ≈ ( 0.424 , 0.470 , 0.106 ) p^*\approx(0.424,\,0.470,\,0.106) p ∗ ≈ ( 0.424 , 0.470 , 0.106 ) ( 0.3 , 0.3 , 0.4 ) (0.3,0.3,0.4) ( 0.3 , 0.3 , 0.4 ) D ( W x ∥ q ∗ ) D(W_x\,\|\,q^*) D ( W x ∥ q ∗ ) C ≈ 0.2279 C\approx0.2279 C ≈ 0.2279
例題 1.6.4 Blahut–Arimoto の1回を手で回す ★★
オリジナル 例題 1.6.2 の Z(1 2 \frac12 2 1 p 0 = ( 1 2 , 1 2 ) p_0=(\frac12,\frac12) p 0 = ( 2 1 , 2 1 ) (1.6.17) を1回当てる。
q 0 q_0 q 0 D ( W 0 ∥ q 0 ) D(W_0\,\|\,q_0) D ( W 0 ∥ q 0 ) D ( W 1 ∥ q 0 ) D(W_1\,\|\,q_0) D ( W 1 ∥ q 0 ) 下界 L 0 L_0 L 0 U 0 U_0 U 0 ln 5 4 ≈ 0.2231 \ln\frac54\approx0.2231 ln 4 5 ≈ 0.2231
更新後の入力 1 1 1 π 1 \pi_1 π 1 L 1 , U 1 L_1,U_1 L 1 , U 1 0.2201 0.2201 0.2201 0.2640 0.2640 0.2640
解答 (1) q 0 = ( 1 2 ⋅ 1 + 1 2 ⋅ 1 2 , 1 2 ⋅ 1 2 ) = ( 3 4 , 1 4 ) q_0=(\frac12\cdot1+\frac12\cdot\frac12,\ \frac12\cdot\frac12)=(\frac34,\frac14) q 0 = ( 2 1 ⋅ 1 + 2 1 ⋅ 2 1 , 2 1 ⋅ 2 1 ) = ( 4 3 , 4 1 ) D ( W 0 ∥ q 0 ) = ln 1 3 / 4 = ln 4 3 ≈ 0.2877 D(W_0\,\|\,q_0)=\ln\frac{1}{3/4}=\ln\frac43\approx0.2877 D ( W 0 ∥ q 0 ) = ln 3/4 1 = ln 3 4 ≈ 0.2877 D ( W 1 ∥ q 0 ) = 1 2 ln 1 / 2 3 / 4 + 1 2 ln 1 / 2 1 / 4 = 1 2 ln 2 3 + 1 2 ln 2 = 1 2 ln 4 3 ≈ 0.1438 D(W_1\,\|\,q_0)=\frac12\ln\frac{1/2}{3/4}+\frac12\ln\frac{1/2}{1/4}=\frac12\ln\frac23+\frac12\ln2=\frac12\ln\frac43\approx0.1438 D ( W 1 ∥ q 0 ) = 2 1 ln 3/4 1/2 + 2 1 ln 1/4 1/2 = 2 1 ln 3 2 + 2 1 ln 2 = 2 1 ln 3 4 ≈ 0.1438
(2) L 0 = 1 2 ( 0.2877 + 0.1438 ) = 3 4 ln 4 3 ≈ 0.2158 L_0=\frac12(0.2877+0.1438)=\frac34\ln\frac43\approx0.2158 L 0 = 2 1 ( 0.2877 + 0.1438 ) = 4 3 ln 3 4 ≈ 0.2158 U 0 = max ( 0.2877 , 0.1438 ) = 0.2877 U_0=\max(0.2877,0.1438)=0.2877 U 0 = max ( 0.2877 , 0.1438 ) = 0.2877 0.2158 ≤ 0.2231 ≤ 0.2877 0.2158\le0.2231\le0.2877 0.2158 ≤ 0.2231 ≤ 0.2877
(3) 更新式から p 1 ∝ ( 1 2 e ln ( 4 / 3 ) , 1 2 e 1 2 ln ( 4 / 3 ) ) = 1 2 ( 4 3 , 4 / 3 ) p_1\propto\bigl(\frac12\mathrm{e}^{\ln(4/3)},\ \frac12\mathrm{e}^{\frac12\ln(4/3)}\bigr)=\frac12\bigl(\frac43,\ \sqrt{4/3}\bigr) p 1 ∝ ( 2 1 e l n ( 4/3 ) , 2 1 e 2 1 l n ( 4/3 ) ) = 2 1 ( 3 4 , 4/3 )
π 1 = 4 / 3 4 / 3 + 4 / 3 ≈ 1.1547 2.4880 ≈ 0.4641. \pi_1=\frac{\sqrt{4/3}}{4/3+\sqrt{4/3}}\approx\frac{1.1547}{2.4880}\approx0.4641 . π 1 = 4/3 + 4/3 4/3 ≈ 2.4880 1.1547 ≈ 0.4641.
入力 1 1 1 q 0 q_0 q 0 D D D 2 5 \frac25 5 2 0.2158 0.2158 0.2158 0.2201 0.2201 0.2201 0.2877 0.2877 0.2877 0.2640 0.2640 0.2640 0.072 0.072 0.072 0.044 0.044 0.044
1 S. Arimoto (1972), IEEE Transactions on Information Theory 18 , 14–20；R. E. Blahut (1972), IEEE Transactions on Information Theory 18 , 460–473.
AI（Claude）が書いた教材を、木下が勉強しながら公開しています。式と数値は検算していますが、誤りが残っているかもしれません。誤りのご指摘・削除のご依頼をいただければ直します。 連絡先：support@tecktom.com
