Blahut–有本アルゴリズム(Blahut–Arimoto algorithm)とは、入出力が有限の無記憶な通信路の容量 $C=\max_pI(X;Y)$ を、入力の分布 $p$ に各入力の出力分布の $D(W(\cdot\mid x)\Vert q_p)$ の指数を掛けて正規化し直す更新の繰り返しで求める反復法で、1972 年に有本卓と R. Blahut が発表した。容量を達成する分布は「すべての入力で $D(W(\cdot\mid x)\Vert q_p)\le I(p)$」で特徴づけられ、反復の各段で計算できる下界と上界が容量を挟み、下界は単調に増えて誤差は $t$ 回で $\log\lvert\mathcal X\rvert/t$ 以下になり、分布は最適な分布に収束する。同じ交互の最適化でレート歪み関数も計算できる。
前提知識: 相互情報量, Kullback–Leibler情報量, Shannonの通信路符号化定理
Blahut–有本アルゴリズム(Blahut–Arimoto algorithm)は、入力と出力が有限集合の無記憶な通信路の容量
$$
C=\max_pI(X;Y)
$$
を数値的に求める反復法である。入力の分布 $p$ を、各入力 $x$ の「出力の分布の、全体の出力の分布からの離れ具合」$D(W(\cdot\mid x)\Vert q_p)$ の指数で重み付けし直す、という掛け算だけの更新を繰り返す。各段で、計算できる下界と上界が容量を挟み、下界は単調に増えて容量に収束し、誤差は反復の回数 $t$ について $\log\lvert\mathcal X\rvert/t$ 以下になる。名は、1972 年に同じ反復を IEEE Transactions on Information Theory で発表した 有本卓(Suguru Arimoto、Ari72)と R. Blahut(Bla72)による(PW25 §5.6、p. 102)。Blahut は同じ考え方でレート歪み関数も計算した。
2元対称通信路のように対称な通信路では容量の式が手で求まる(Shannonの通信路符号化定理 の命題「対称な通信路の容量」)が、一般の通信路では最大化を解く必要がある。この記事では、容量を達成する分布の特徴づけ(Kuhn–Tucker 型の条件)を証明し、アルゴリズムを定義して、単調性・誤差の評価・収束を完全に証明する。最後に、レート歪み関数を計算する Blahut の版を述べる。
以下、$\log$ は自然対数(nat)とする。$\mathcal X,\mathcal Y$ を有限集合、$W(y\mid x)$ を通信路($W(y\mid x)\ge0$、$\sum_yW(y\mid x)=1$)とし、$W_x:=W(\cdot\mid x)$ と書く。$\Delta$ を $\mathcal X$ 上の確率分布の全体とする。$p\in\Delta$ に対し、出力の分布を $q_p(y):=\sum_xp(x)W(y\mid x)$、
$$
D_x(p):=D(W_x\Vert q_p)=\sum_yW(y\mid x)\log\frac{W(y\mid x)}{q_p(y)}\in[0,\infty]
$$
とおき、入力 $X\sim p$ と出力 $Y$ の 相互情報量 を $I(p)$ と書く。$I(p)=\sum_xp(x)D_x(p)$ である($p(x)>0$ なら $q_p(y)\ge p(x)W(y\mid x)$ なので $D_x(p)< \infty$)。$I$ は $\Delta$ 上で連続かつ凹で(相互情報量 の系「入力について凹、通信路について凸」)、$\Delta$ はコンパクトなので最大値 $C$ をとる。最大値をとる $p$ を 最適な入力の分布 という。
$p\in\Delta$ と $\mathcal Y$ 上の確率分布 $r$ について
$$
\sum_xp(x)D(W_x\Vert r)=I(p)+D(q_p\Vert r)
$$
である(両辺は $+\infty$ もとりうる)。
$q_p(y)>0$ かつ $r(y)=0$ となる $y$ があれば、$p(x)W(y\mid x)>0$ となる $x$ があって両辺とも $+\infty$ である。そうでなければ、$p(x)W(y\mid x)>0$ となる組で $\log\frac{W(y\mid x)}{r(y)}=\log\frac{W(y\mid x)}{q_p(y)}+\log\frac{q_p(y)}{r(y)}$ と分け、$p(x)W(y\mid x)$ を掛けて足す。第 1 項の和が $I(p)$、第 2 項の和が $\sum_yq_p(y)\log\frac{q_p(y)}{r(y)}=D(q_p\Vert r)$ である。$\square$
同じ等式は CS04 Lemma 7.1(p. 491)にある。$D(q_p\Vert r)\ge0$ なので、左辺の $r$ についての最小値は $I(p)$ で、$r=q_p$ でとられる。
1. 最適な $p^*$ をとる。lem-ba-identity を $p^*$ と $r=q_p$ に使うと
$$
\max_xD_x(p)\ge\sum_xp^*(x)D(W_x\Vert q_p)=I(p^*)+D(q_{p^*}\Vert q_p)\ge C
$$
である。
2. 十分性。 すべての $x$ で $D_x(p^*)\le I(p^*)$ なら、1 から $C\le\max_xD_x(p^*)\le I(p^*)\le C$ で、$p^*$ は最適である。
必要性。 $p^*$ を最適とし、$x_0\in\mathcal X$ を固定する。$\delta_{x_0}$ を $x_0$ に集中した分布とし、$p_s:=(1-s)p^*+s\delta_{x_0}$、$g(s):=I(p_s)$($0\le s\le1$)とおく。$g$ は凹で、$g(s)\le g(0)$ である。出力の分布は $q_s:=q_{p_s}=(1-s)q^*+sW_{x_0}$($q^*:=q_{p^*}$)で、$H(\cdot)$ を エントロピー として $g(s)=H(q_s)-\sum_xp_s(x)H(W_x)$ と書ける。$0< s< 1$ では、$q^*$ か $W_{x_0}$ が正の $y$ で $q_s(y)>0$ なので $g$ は微分でき、$\sum_y(W(y\mid x_0)-q^*(y))=0$ を使うと
$$
g'(s)=-\sum_y\bigl(W(y\mid x_0)-q^*(y)\bigr)\log q_s(y)-H(W_{x_0})+\sum_xp^*(x)H(W_x)
$$
である。平均値の定理により $g(s)-g(0)=sg'(\sigma)$ となる $\sigma\in(0,s)$ があり、凹関数の導関数は減少するので $g'(s)\le g'(\sigma)\le0$ である。
$s\downarrow0$ とする。$W(y\mid x_0)>0$ かつ $q^*(y)=0$ となる $y$ があれば、その項 $-W(y\mid x_0)\log q_s(y)=-W(y\mid x_0)\log(sW(y\mid x_0))$ は $+\infty$ に発散し、ほかの項は有界なので $g'(s)\to+\infty$ となって $g'\le0$ に反する。よってそのような $y$ はなく、
$$
\lim_{s\downarrow0}g'(s)=-\sum_yW(y\mid x_0)\log q^*(y)-H(W_{x_0})+\Bigl(\sum_yq^*(y)\log q^*(y)+\sum_xp^*(x)H(W_x)\Bigr)=D_{x_0}(p^*)-I(p^*)
$$
である(括弧の中は $-H(q^*)+\sum_xp^*(x)H(W_x)=-I(p^*)$)。これが $0$ 以下なので $D_{x_0}(p^*)\le I(p^*)$ である。
最後に、$\sum_xp^*(x)D_x(p^*)=I(p^*)=C$ で各項が $C$ 以下なので、$p^*(x)>0$ の $x$ では $D_x(p^*)=C$ である。$\square$
2 は CS04 Theorem 7.1(p. 492)の、入力が有限集合の場合である(同書は $\sup_\theta D(P_\theta\Vert Q)\ge I(\nu)$ と等号の条件の形で述べ、同じく片側の微分で示している)。2 の条件は、容量が「出力の分布 $r$ を 1 つ選んで、すべての $W_x$ からの $D(W_x\Vert r)$ の最大を最小にする」問題の値に等しく、最適な $r$ が $q_{p^*}$ であることを意味する。最適な入力の分布は一つとは限らないが、最適な出力の分布は一つである:$p^*,p^{**}$ が最適なら、2 と lem-ba-identity から $C\ge\sum_xp^{**}(x)D(W_x\Vert q_{p^*})=C+D(q_{p^{**}}\Vert q_{p^*})$ で、$q_{p^{**}}=q_{p^*}$ となる。
すべての $x$ で $p_0(x)>0$ となる $p_0\in\Delta$(たとえば一様分布)から始め、$t=0,1,2,\dots$ について
$$
Z_t:=\sum_xp_t(x)e^{D_x(p_t)},\qquad p_{t+1}(x):=\frac{p_t(x)e^{D_x(p_t)}}{Z_t}
$$
と定める。各段で、下界 $\log Z_t$ と上界 $U_t:=\max_xD_x(p_t)$ を計算し、$U_t-\log Z_t$ が許容誤差より小さくなったら止める。
帰納法で、すべての $t,x$ で $p_t(x)>0$ であり、$D_x(p_t)< \infty$ である。$q_t:=q_{p_t}$ とおき、受け取った $y$ から入力を推定する 逆向きの通信路 $\Phi_t(x\mid y):=p_t(x)W(y\mid x)/q_t(y)$($q_t(y)>0$ のとき)を考えると
$$
\sum_yW(y\mid x)\log\Phi_t(x\mid y)=\log p_t(x)+D_x(p_t)
$$
なので、更新は $p_{t+1}(x)\propto\exp\bigl(\sum_yW(y\mid x)\log\Phi_t(x\mid y)\bigr)$ とも書ける。PW25 p. 103 はこの形で、$\Phi$ と $p$ を交互に最適化する反復として導いている。その根拠が次の補題である。
$p\in\Delta$ と、$q_p(y)>0$ となる各 $y$ について $\mathcal X$ 上の確率分布 $\Phi(\cdot\mid y)$ をとる。
$$
J(p,\Phi):=\sum_{x,y}p(x)W(y\mid x)\log\frac{\Phi(x\mid y)}{p(x)}
$$
($p(x)W(y\mid x)=0$ の項は $0$ とする)とおくと $J(p,\Phi)\le I(p)$ で、$\Phi(x\mid y)=p(x)W(y\mid x)/q_p(y)$ のとき等号が成り立つ。
$\Phi_p(x\mid y):=p(x)W(y\mid x)/q_p(y)$ とおくと、$I(p)=\sum_{x,y}p(x)W(y\mid x)\log\frac{\Phi_p(x\mid y)}{p(x)}$ である。差をとると $I(p)-J(p,\Phi)=\sum_yq_p(y)\sum_x\Phi_p(x\mid y)\log\frac{\Phi_p(x\mid y)}{\Phi(x\mid y)}=\sum_yq_p(y)D\bigl(\Phi_p(\cdot\mid y)\Vert\Phi(\cdot\mid y)\bigr)\ge0$ である(右辺が $+\infty$ なら $J=-\infty$ で不等式は自明)。$\square$
def-ba-algorithm の列 $(p_t)$ について、次が成り立つ。
1 の左と右。 $\log$ は凹なので、Jensen の不等式により $\log Z_t=\log\sum_xp_t(x)e^{D_x(p_t)}\ge\sum_xp_t(x)D_x(p_t)=I(p_t)$ である。$C\le U_t$ は thm-ba-kkt の 1 である。
1 の中央。 lem-ba-variational を $p_{t+1}$ と $\Phi_t$ に使う($p_t$ も $p_{t+1}$ もすべての $x$ で正なので、$q_t(y)>0$ と $q_{p_{t+1}}(y)>0$ はどちらも「$W(y\mid x)>0$ となる $x$ がある」ことと同じで、必要な $y$ で $\Phi_t(\cdot\mid y)$ は定まり、$p_{t+1}(x)W(y\mid x)>0$ なら $\Phi_t(x\mid y)>0$ である)。$\sum_yW(y\mid x)\log\Phi_t(x\mid y)=\log p_t(x)+D_x(p_t)$ と、定義から $\log p_{t+1}(x)=\log p_t(x)+D_x(p_t)-\log Z_t$ であることを使うと
$$
J(p_{t+1},\Phi_t)=\sum_xp_{t+1}(x)\bigl(\log p_t(x)+D_x(p_t)-\log p_{t+1}(x)\bigr)=\sum_xp_{t+1}(x)\log Z_t=\log Z_t
$$
となり、$\log Z_t=J(p_{t+1},\Phi_t)\le I(p_{t+1})\le C$ である。
2. $p^*$ を最適とし、$q^*:=q_{p^*}$ とおく。すべての $x$ で $p_t(x)>0$ なので $D(p^*\Vert p_t)< \infty$ である。更新の式の対数をとって $p^*(x)$ を掛けて足すと
$$
D(p^*\Vert p_t)-D(p^*\Vert p_{t+1})=\sum_xp^*(x)\log\frac{p_{t+1}(x)}{p_t(x)}=\sum_xp^*(x)D_x(p_t)-\log Z_t
$$
である。lem-ba-identity を $p^*$ と $r=q_t$ に使うと $\sum_xp^*(x)D_x(p_t)=C+D(q^*\Vert q_t)$ なので、1 と合わせて
$$
D(p^*\Vert p_t)-D(p^*\Vert p_{t+1})=C-\log Z_t+D(q^*\Vert q_t)\ge C-I(p_{t+1})\ge0\qquad(\ast)
$$
を得る。$t=0,\dots,T-1$ について足すと
$$
\sum_{t=1}^T\bigl(C-I(p_t)\bigr)\le D(p^*\Vert p_0)-D(p^*\Vert p_T)\le D(p^*\Vert p_0)
$$
で、1 から $C-I(p_t)$ は $t$ について減少するので、左辺は $T\bigl(C-I(p_T)\bigr)$ 以上である。$p_0$ が一様なら $D(p^*\Vert p_0)=\log\lvert\mathcal X\rvert-H(p^*)\le\log\lvert\mathcal X\rvert$ である。
3. 2 から $I(p_t)\to C$ である。$\Delta$ はコンパクトなので、部分列 $p_{t_k}$ がある $\bar p$ に収束する。$I$ は連続なので $I(\bar p)=C$ で、$\bar p$ は最適である。$(\ast)$ を $p^*=\bar p$ に使うと $D(\bar p\Vert p_t)$ は $t$ について減少する。$\bar p(x)>0$ の $x$ では $p_{t_k}(x)\to\bar p(x)>0$ なので $D(\bar p\Vert p_{t_k})\to0$ で、減少する列なので $D(\bar p\Vert p_t)\to0$ である。$p_t$ の任意の集積点 $p'$ をとる。$p\mapsto D(\bar p\Vert p)$ は各項 $\bar p(x)\log\frac{\bar p(x)}{p(x)}$ が $(-\infty,+\infty]$ に値をとる連続関数なので下半連続で、$D(\bar p\Vert p')\le\liminf D(\bar p\Vert p_t)=0$ となり、Gibbs の不等式の等号条件から $p'=\bar p$ である。集積点がただ 1 つでコンパクトなので $p_t\to\bar p$ である。
最後に $q_t\to q_{\bar p}$ である。thm-ba-kkt の 2 により各 $x$ で $D_x(\bar p)\le C< \infty$ なので、$W(y\mid x)>0$ なら $q_{\bar p}(y)>0$ で、$D_x(p_t)=\sum_{y:W(y\mid x)>0}W(y\mid x)\log\frac{W(y\mid x)}{q_t(y)}$ は $D_x(\bar p)$ に収束する。よって $U_t\to\max_xD_x(\bar p)$ で、これは thm-ba-kkt の 1・2 から $C$ に等しい。$\square$
PW25 p. 103 の式 (5.29) は、1 の外側の不等式 $I(p_t)\le C\le U_t$ を停止の判定に使えることを述べ、両側が $C$ に単調に収束することの証明を文献に譲っている。上の 2 の評価は、各段の増加 $C-\log Z_t$ を、最適な分布までの Kullback–Leibler 情報量の減少で抑える議論による。$U_t$ が単調であることは示していない。
2 の評価は最悪の場合の保証で、具体的な通信路ではずっと速いことが多い(ex-ba-three では誤差は $t$ について指数的に減る)。誤差 $\eta$ を保証するには、一様な $p_0$ から $\lceil\log\lvert\mathcal X\rvert/\eta\rceil$ 回の反復で足りる。1 回の反復は $\lvert\mathcal X\rvert\lvert\mathcal Y\rvert$ に比例する手間で計算できる。
2元対称通信路 $\mathrm{BSC}(\varepsilon)$ で一様な $p_0$ から始めると、$q_0$ も一様で、$D_0(p_0)=D_1(p_0)=\log2-h(\varepsilon)$($h$ は 2 値エントロピー)である。$p_1=p_0$ となり、$I(p_0)=\log Z_0=U_0=\log2-h(\varepsilon)$ で、反復は 0 回で止まる。thm-ba-kkt の 2 の条件がそのまま成り立っている。
$\mathcal X=\mathcal Y=\{0,1\}$ で、$0$ はそのまま届き、$1$ は確率 $\frac12$ で $0$ に変わる通信路を考える:$W_0=(1,0)$、$W_1=(\frac12,\frac12)$。$p=(\frac35,\frac25)$ では $q_p=(\frac45,\frac15)$ で、$D_0(p)=\log\frac54$、$D_1(p)=\frac12\log\frac{1/2}{4/5}+\frac12\log\frac{1/2}{1/5}=\frac12\log\frac{25}{16}=\log\frac54$ なので、thm-ba-kkt の 2 により $p$ は最適で $C=\log\frac54$、すなわち $\log_2\frac54\approx0.321928$ bit である。一様な $p_0$ からの反復は次のとおりである(単位は bit)。
| $t$ | $p_t(1)$ | $I(p_t)$ | $\log Z_t$ | $U_t$ |
|---|---|---|---|---|
| 0 | 0.500000 | 0.311278 | 0.315006 | 0.415037 |
| 1 | 0.464102 | 0.317468 | 0.319074 | 0.380917 |
| 2 | 0.440630 | 0.320112 | 0.320777 | 0.359037 |
| 4 | 0.416073 | 0.321640 | 0.321747 | 0.336494 |
| 8 | 0.402468 | 0.321921 | 0.321924 | 0.324155 |
下界は速く容量に近づくが、上界 $U_t$ の近づき方は遅い。停止の判定 $U_t-\log Z_t$ は保守的である。
$\mathcal X=\{0,1,2\}$、$\mathcal Y=\{0,1\}$、$W_0=(1,0)$、$W_1=(0,1)$、$W_2=(\frac12,\frac12)$ とする。$p^*=(\frac12,\frac12,0)$ で $q^*$ は一様、$D_0(p^*)=D_1(p^*)=\log2$、$D_2(p^*)=0$ なので、$p^*$ は最適で $C=\log2$(1 bit)である。$D_2(p^*)< C$ で、thm-ba-kkt の 2 の等号は台の外では成り立たない。一様な $p_0$ から始めると、$p_t(0)=p_t(1)$ が保たれて $q_t$ はつねに一様なので、$D_0=D_1=\log2$、$D_2=0$ で、$p_{t+1}(2)=\frac{p_t(2)}{2-p_t(2)}$ から $p_t(2)=\frac1{1+2^{t+1}}$、$C-I(p_t)=p_t(2)\log2$ となる。誤差は指数的に減るが、使われない入力の確率は有限回では $0$ にならない。
同じ交互の最適化で、レート歪み理論 の情報レート歪み関数 $R^{(I)}(D)=\min\{I(S;\hat S)\mid E[d(S,\hat S)]\le D\}$ も計算できる。$P$ を有限集合 $\mathcal S$ 上の情報源の分布、$\hat{\mathcal S}$ を有限の再生の集合、$d\ge0$ を歪みの尺度とする。試験の通信路 $Q(\hat s\mid s)$ について、$I(Q)$ を $S\sim P$ と $\hat S$ の相互情報量、$E_Q[d]:=\sum_{s,\hat s}P(s)Q(\hat s\mid s)d(s,\hat s)$ とする。制約付きの最小化の代わりに、$\beta\ge0$ を固定して $I(Q)+\beta E_Q[d]$ を最小にする。
$Q_\beta$ が $I(Q)+\beta E_Q[d]$ を最小にし、$D_\beta:=E_{Q_\beta}[d]$ とすると、$I(Q_\beta)=R^{(I)}(D_\beta)$ である。
$E_Q[d]\le D_\beta$ を満たすどの $Q$ についても、最小性から $I(Q)\ge I(Q_\beta)+\beta(D_\beta-E_Q[d])\ge I(Q_\beta)$ である。$Q_\beta$ 自身は条件を満たすので、$I(Q_\beta)$ が条件のもとでの最小値である。$\square$
$\hat{\mathcal S}$ 上の分布 $r$ と試験の通信路 $Q$ について
$$
G(Q,r):=\sum_sP(s)\Bigl(D\bigl(Q(\cdot\mid s)\Vert r\bigr)+\beta\sum_{\hat s}Q(\hat s\mid s)d(s,\hat s)\Bigr)
$$
とおく。Blahut の反復は、すべての $\hat s$ で正の $r_0$ から始めて
$$
Q_t(\hat s\mid s):=\frac{r_t(\hat s)e^{-\beta d(s,\hat s)}}{\sum_{\hat s'}r_t(\hat s')e^{-\beta d(s,\hat s')}},\qquad r_{t+1}(\hat s):=\sum_sP(s)Q_t(\hat s\mid s)
$$
と定める(PW25 p. 103 の反復で、$d$ を $\beta d$ に替えたもの)。
(1):lem-ba-identity を、入力 $s\sim P$、通信路 $Q$ に使うと $\sum_sP(s)D(Q(\cdot\mid s)\Vert r)=I(Q)+D(r_Q\Vert r)$ である。
(2):$z_s:=\sum_{\hat s}r(\hat s)e^{-\beta d(s,\hat s)}$、$g_s(\hat s):=r(\hat s)e^{-\beta d(s,\hat s)}/z_s$ とおくと、各 $s$ で
$$
D\bigl(Q(\cdot\mid s)\Vert r\bigr)+\beta\sum_{\hat s}Q(\hat s\mid s)d(s,\hat s)=D\bigl(Q(\cdot\mid s)\Vert g_s\bigr)-\log z_s
$$
であり($\log\frac{Q}{r}+\beta d=\log\frac Q{g_s}-\log z_s$)、最小は $Q(\cdot\mid s)=g_s$ でとられる。
(3):反復は $Q_t$ が $r_t$ に対する (2) の最小点、$r_{t+1}$ が $Q_t$ に対する (1) の最小点なので、$G(Q_t,r_{t+1})\ge G(Q_{t+1},r_{t+1})\ge G(Q_{t+1},r_{t+2})$ で、両端が (1) により $I(Q_t)+\beta E_{Q_t}[d]$ と $I(Q_{t+1})+\beta E_{Q_{t+1}}[d]$ に等しい。$\square$
この値が最小値に収束し、上からと下から計算できる評価で挟めることは PW25 p. 103(式 (5.32) との類比)に述べられているが、この記事では証明しない。$\beta$ を動かすと、prop-ba-rd-point により曲線 $R^{(I)}$ 上の点 $(D_\beta,R^{(I)}(D_\beta))$ が得られる。
$\mathcal S=\hat{\mathcal S}=\{0,1\}$、Hamming 歪みとする。公平な硬貨で $\beta=\log4$、一様な $r_0$ から始めると、$Q_0(\hat s\mid s)$ は $\hat s=s$ で $\frac{1}{1+e^{-\beta}}=\frac45$ で、$r_1$ は一様のままなので不動点である。$D_\beta=\frac15$、$I=\log2-h(\frac15)$ で、レート歪み理論 の公平な硬貨の値 $R(D)=\log2-h(D)$ と一致する。$P(1)=0.2$ の偏った硬貨で $\beta=\log9$ とすると、反復は $D_\beta=0.1$、$I=h(0.2)-h(0.1)$ の点に収束する(数値で確認)。これも同記事の Bernoulli 源の式 $h(p)-h(D)$($D\le p$)と合う。
| 外した仮定 | 反例 | 成り立たなくなる結論 |
|---|---|---|
| $p_0$ がすべての入力で正(thm-ba-main) | $\mathrm{BSC}(0.1)$ で $p_0=\delta_0$($0$ に集中) | $q_0=W_0$ で $D_0(p_0)=0$、$p_t=\delta_0$ のまま動かず $I(p_t)=0< C$。3 の収束が成り立たない($U_t=D_1(\delta_0)=0.8\log9>C$ のまま。2 の評価は $D(p^*\Vert p_0)=+\infty$ で何も言わない)($p_t(x)=0$ なら $p_{t+1}(x)=0$ で、台は広がらない) |
| $p^*(x)>0$(thm-ba-kkt の 2 の等号) | ex-ba-three の入力 $2$ | $D_2(p^*)=0< C$ で、$D_x(p^*)=C$ がすべての $x$ では成り立たない |
| 最適な入力の分布が一つ(thm-ba-main の 3 の極限を $p_0$ によらず決めるのに要る) | $W_0=W_1=(1,0)$、$W_2=(0,1)$ | 最適な分布は $p(0)+p(1)=p(2)=\frac12$ のものすべてである。$D_0=D_1$ なので比 $p_t(0)/p_t(1)$ は保たれ、極限は $p_0=(a,b,c)$ で決まる $\bigl(\frac{a}{2(a+b)},\frac{b}{2(a+b)},\frac12\bigr)$ になる。極限が通信路だけで決まるという結論が成り立たない |
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する