本記事は情報理論の徹底解説シリーズに含まれます。
初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。
はじめに
通信路容量は，情報理論では避けては通れない重要なトピックです。線形代数の学部レベルのゴールが行列の$n$乗とするなら，情報理論の学部レベルのゴールは通信路容量を求めることでしょう。通信路容量はそれだけ様々な要素が詰まった重要なトピックです。本稿では，そんな通信路容量の求め方を通信路の種類別にまとめていきます。
通信路の分類
まずは，通信路を分類していきます。
- 雑音のない通信路
- 確定的通信路
- 一様な通信路
- 二元対称通信路
- 一般の通信路
雑音のない通信路
雑音のない通信路とは，$b_k\rightarrow a_j$が1通りしかないような通信路です。つまり，$p(a_j|b_k)$が$0$か$1$となります。具体的には，以下のような通信路行列$T$をイメージしてもらえればと思います。
T&=
\begin{bmatrix}
0.6 & 0 & 0.4 & 0 & 0 \\
0 & 0.5 & 0 & 0.3 & 0.2
\end{bmatrix}
\end{align}
確定的通信路
確定的通信路とは，$a_j\rightarrow b_k$が1通りしかないような通信路です。$p(b_k|a_j)$が$0$か$1$になるような通信路です。具体的には，以下のような通信路行列$T$をイメージしてもらえればと思います。
T&=
\begin{bmatrix}
1 & 0 \\
0 & 1 \\
1 & 0 \\
0 & 1 \\
0 & 1
\end{bmatrix}
\end{align}
一様な通信路（$2$元対称消失通信路）
一様な通信路（$2$元対称消失通信路）とは，通信路行列の各行が，全て要素を入れ替えただけの関係になっているような通信路を指します。具体的には，以下のような通信路行列$T$をイメージしてもらえればと思います。
T&=
\begin{bmatrix}
1-p-q & q & p \\
p & q & 1-p-q
\end{bmatrix}
\end{align}
二元対称通信路
二元対称通信路は，頻出の通信路です。以下の通信路行列$T$で表されます。
T&=
\begin{bmatrix}
1-p & p \\
p & 1-p
\end{bmatrix}
\end{align}
結論
これらの通信路について，それぞれ以下のように通信路が求められます。
- 雑音のない通信路
-
\begin{align}
\max \left\{ H(A) \right\}
\end{align} - 確定的通信路
-
\begin{align}
\max \left\{ H(B) \right\}
\end{align} - 一様通信路（$2$元対称消失通信路）
-
\begin{align}
\max\left\{H(B)\right\} + \sum_{k=1}^K p(b_k|a_j)\log p(b_k|a_j)
\end{align} - 二元対称通信路
-
\begin{align}
1-\calH(p)
\end{align} - 一般の通信路
-
\begin{align}
\log \sum_{k=1}^{K}2^{x_{k}}
\end{align}
ただし，上の表で利用した記号は以下のとおりです。
| 記号 | 内容 |
|---|---|
| $A$ | 入力記号 |
| $B$ | 出力記号 |
| $K$ | 出力記号数 |
| $\calH$ | エントロピー関数 |
| $x_{k}$ | $x_{k}=\sum_{j=1}^{J}p(a_j|b_k)\log p(b_k|a_j)$ |
以下では，通信路の種類別に通信路容量の求め方を確認していきます。
証明
雑音のない通信路
$p(a_j|b_k)=0,1$ということから，エントロピー$H(A|B)$が$0$となることが分かります。したがって，通信路容量$C$は以下のように求められます。
C &= \max \left\{ I(A;B) \right\}\\[0.7em]
&= \max \left\{ H(A) - H(A|B) \right\}\\[0.7em]
&= \max\left\{H(A) \right\}
\end{align}
確定的通信路
$p(b_k|a_j)=0,1$ということから，エントロピー$H(B|A)$が$0$となることが分かります。したがって，通信路容量$C$は以下のように求められます。
C &= \max \left\{ I(A;B) \right\}\\[0.7em]
&= \max \left\{ H(B) - H(B|A) \right\}\\[0.7em]
&= \max\left\{H(B) \right\}
\end{align}
一様な通信路（$2$元対称消失通信路）
一様な通信路（$2$元対称消失通信路）では，以下のようにすれば$H(B|A)$を「一行だけについて注目すればよい」ことが分かります。感覚的には，全ての行が同じ要素で構成されているため，$p(a_j)$が足し合わされて$1$になるイメージです。
C &= \max \left\{ I(A;B) \right \} \\[0.7em]
&= \max \left\{ H(B) - H(B|A) \right\}\\[0.7em]
&= \max\left\{ H(B) + \sum_{j=1}^{J}p(a_j) \sum_{k=1}^K p(b_k|a_j)\log p(b_k|a_j) \right\}\\[0.7em]
&= \max \left\{ H(B) + \sum_{k=1}^K p(b_k|a_j)\log p(b_k|a_j)\right\}\\[0.7em]
&= \max \left\{ H(B) \right\} + \sum_{k=1}^K p(b_k|a_j)\log p(b_k|a_j)
\end{align}
ただし，各$j$について$p(b_k|a_j)$は同じで$\sum_{j=1}^{J} p(a_j)=1$であることを利用しました。
二元対称通信路
定義通り素直に計算するだけです。$p(a_{1}){=}\omega$とおき，$I(A;B){=}H(A){-}H(A|B)$を考えます。$H(A)$については
H(A) &= \omega\log \frac{1}{\omega} + (1-\omega)\log \frac{1}{1-\omega}
= \calH (\omega)
\end{align}
となります。$H(A|B)$については$H(A|B){=}H(A,B){-}H(B)$を利用します。$H(A,B)$については
H(A,B)
&= p(a_1,b_1)\log \frac{1}{p(a_1, b_1)} + p(a_1, b_2)\log \frac{1}{p(a_1, b_2)}\notag \\[0.7em]
&\quad\quad + p(a_2,b_1)\log\frac{1}{p(a_2, b_1)} + p(a_2, b_2)\log\frac{1}{p(a_2, b_2)}\\[0.7em]
&= \omega(1-p) \log \frac{1}{\omega(1-p)} + \omega p \log\frac{1}{\omega p}\notag \\[0.7em]
&\quad + (1-\omega)p \log\frac{1}{(1-\omega)p} + (1-\omega)(1-p) \log\frac{1}{(1-\omega)(1-p)}\\[0.7em]
&= \calH(\omega)+\calH(p)
\end{align}
となります。$H(B)$については，
p(b_1) &= p(a_1)p(b_1|a_1) + p(a_2)p(b_1|a_2)
= \omega(1-p) + (1-\omega)p
\end{align}
より，
H(B) &= p(b_1)\log \frac{1}{p(b_1)} + p(b_2)\log \frac{1}{p(b_2)}
= \calH\left(\omega(1-p) + (1-\omega)p\right)
\end{align}
となります。これらより，$H(A|B)$は以下のようになります。
H(A|B)&=H(A,B) - H(B)
= \calH(\omega)+\calH(p)-\calH\left(\omega(1-p) + (1-\omega)p\right)
\end{align}
したがって，通信路容量は以下で表されます。
C &= \max\{ I(A;B) \}
= \max \{ H(A) - H(A|B) \}\\[0.7em]
&= \max\{ \calH(\omega)-\calH(\omega)-\calH(p)+\calH\left(\omega(1-p) + (1-\omega)p\right) \}\\[0.7em]
&= \max\{\calH\left(\omega(1-p) + (1-\omega)p\right)\}-\calH(p)
\end{align}
ここで，$\calH(x)$は$x{=}1/2$で最大値$1$を取ることから，
\omega(1-p) + (1-\omega)p
= \omega+(1-2\omega)p = \frac{1}{2} = \frac{1}{2}+0\cdot p
\end{align}
の恒等式，すなわち
\omega+(1-2\omega)p = \frac{1}{2}+0\cdot p
\end{align}
を考えると，$\omega{=}1/2$が得られます。したがって，
C
&= \max\{\calH\left(\omega(1-p) + (1-\omega)p\right)\}-\calH(p)
= \calH\left(\frac{1}{2}\right)-\calH(p)
= 1-\calH(p)
\end{align}
が得られます。
一般の通信路
一般の通信路の通信路容量ですが，まず求め方を日本語で説明してみます。
$I(A;B)$を$p(b_k)$のみで表して$\sum_k p(b_k)=1$の条件下での最大値を求める
この方針のもと，相互情報量$I(A;B)$の最大値を求めていきます。条件付き最大最小問題なので，ラグランジュの未定乗数法を利用します。ラグランジュ関数を$L$とおくと，以下のように表すことができます。
L &= I(A;B) + \lambda \left( \sum_k p(b_k)-1 \right)
\end{align}
まずは，$I(A;B)$を$p(b_k)$のみで表してみましょう。
I(A;B) &= H(B) - H(B|A)\\
&= \sum_{k=1}^K p(b_k)\log \frac{1}{p(b_k)} + \sum_{j=1}^{J}p(a_j) \sum_{k=1}^K p(b_k|a_j)\log p(b_k|a_j)\\[0.7em]
&= \sum_{k=1}^K p(b_k)\log \frac{1}{p(b_k)} + \sum_{j=1}^{J}\sum_{k=1}^K p(a_j)p(b_k|a_j)\log p(b_k|a_j)\\[0.7em]
&= \sum_{k=1}^K p(b_k)\log \frac{1}{p(b_k)} + \sum_{j=1}^{J}\sum_{k=1}^K p(b_k)p(a_j|b_k)\log p(b_k|a_j)\\[0.7em]
&= \sum_{k=1}^K p(b_k)\log \frac{1}{p(b_k)} + \sum_{k=1}^K p(b_k)\sum_{j=1}^{J}p(a_j|b_k)\log p(b_k|a_j)\label{置換前}\\[0.7em]
&= \sum_{k=1}^K p(b_k)\log \frac{1}{p(b_k)} + \sum_{k=1}^{K} p(b_k) x_{k}\label{相互情報量}
\end{align}
ただし，簡単のため$x_{k}=\sum_{j=1}^{J}p(a_j|b_k)\log p(b_k|a_j)$とおきました。この相互情報量を，ラグランジュ関数に代入します。
L &= \sum_{k=1}^K p(b_k)\log \frac{1}{p(b_k)} + \sum_{k=1}^{K} p(b_k) x_{k} + \lambda \left( \sum_k p(b_k)-1 \right)\label{ラグランジュ関数}
\end{align}
$b_{k}$に関する最大最小問題を解くため，$L$の$p(b_{k})$に関する導関数を$0$とおきます。
\frac{\partial L}{\partial p(b_k)}
&= -\frac{\partial }{\partial p(b_k)}\left\{\sum_{k=1}^K p(b_k)\log p(b_k)\right\}+ \frac{\partial }{\partial p(b_k)}\left\{\sum_{k=1}^{K} p(b_k) x_{k}\right\}\notag\\[0.7em]
&\quad\quad\quad\quad+\frac{\partial }{\partial p(b_k)}\left\{\lambda \left( \sum_{k=1}^{K} p(b_k)-1 \right)\right\}\\[0.7em]
&= -\log p(b_k) - \frac{1}{\log_{e}2} + x_{k} + \lambda\\[0.7em]
&= -\log p(b_k) - \log e + x_{k} + \lambda
= 0
\label{lag_func}
\end{align}
ただし，$\log$の底は$2$であるため，
\frac{\partial }{\partial p(b_k)}\log p(b_k) &= \frac{1}{\log_{e}2} = \log e
\end{align}
であることに注意してください。ここで，機械学習でもよく用いるアイディアなのですが，両辺に$p(b_k)$をかけます。
-p(b_k) \log p(b_k) - p(b_k)\log e + p(b_k)x_{j} + p(b_k)\lambda &= 0
\end{align}
両辺の$k$についての和をとります。
-\sum_{k=1}^Kp(b_k) \log p(b_k) - \log e \sum_{k=1}^K p(b_k) + \sum_{k=1}^Kp(b_k)x_k + \lambda\sum_{k=1}^Kp(b_k)&=0
\end{align}
$\sum_{k=1}^{K}p(b_k)=1$に注意して両辺を整理します。
\sum_{k=1}^Kp(b_k)\frac{1}{\log p(b_k)} \sum_{k=1}^Kp(b_k) x_k - \log e + \lambda &=0
\label{lag_cap}
\end{align}
ここで，相互情報量の式($\ref{相互情報量}$)を今一度確認してみます。よくよく見てみると，式(\ref{lag_cap})の中に$I(A;B)$が入っていることが分かります。今回は$I(A;B)$が最大になるときを考えていますので，$I(A;B)=C$となることに注意すると，式(\ref{lag_cap})は以下のように表されます。
\lambda &= -C + \log e
\label{lam_cap}
\end{align}
式(\ref{lam_cap})を式(\ref{lag_func})に代入して整理します。
p(b_k) &= 2^{x_k - C}
\end{align}
両辺の$k$についての和をとります。
\sum_{k=1}^K p(b_k) &= \sum_{k=1}^K 2^{x_k - C}
\end{align}
$\sum_{k=1}^K p(b_k)=1$に注意して整理すると，一般の通信路容量の式が導出されます。
C &= \log \sum_{k=1}^K 2^{x_k}\label{解}
\end{align}
補足1
一般の通信路の通信路容量を求めるために，ラグランジュの未定乗数法を用いて最大最小問題の解を求めました。目的関数($\ref{ラグランジュ関数}$)の解($\ref{解}$)が存在するためには，$x_{k}$が存在する必要があります。改めて$x_{k}$の定義を見直してみましょう。式($\ref{置換前}$)から式($\ref{相互情報量}$)の変形に際し，以下のような置換を行いました。
-\sum_{k=1}^{K}p(b_{k})x_{k} &= H(B|A)
\end{align}
以下では$x_{k}$が存在するための条件を考えます。$a_{j}$に関する条件も考慮するため，両辺を$a_{j}$で周辺化します。
-\sum_{j=1}^{J}\sum_{k=1}^{K}p(a_{j},b_{k})x_{k} &= H(B|A)
\end{align}
さらに変形を続けます。
-\sum_{j=1}^{J}p(a_{j})\sum_{k=1}^{K}p(b_{k}|a_{j})x_{k} &= -\sum_{j=1}^{J}p(a_{j})\sum_{k=1}^{K}p(b_{k}|a_{j})\log p(b_{k}|a_{j})
\end{align}
両辺を比較すると，各$j$について以下が成り立たなければなりません。
\sum_{k=1}^{K}p(b_{k}|a_{j})x_{k} &= \sum_{k=1}^{K}p(b_{k}|a_{j})\log p(b_{k}|a_{j})\label{散布度連立方程式}
\end{align}
これは$K$個の変数$x_{1},\ldots,x_{K}$に対する$J$個の方程式になります。$x_{1},\ldots,x_{K}$が一意な解をもつならば，変数の数と方程式の数は等しくなければなりません。すなわち，$K=J$となります。したがって，通信路行列が正方行列のときに限り，一般の通信路の通信路容量は解($\ref{解}$)を持つことが分かります。
方程式($\ref{散布度連立方程式}$)のことを散布度連立方程式とよびます。
補足2
解($\ref{解}$)の具体例を考えましょう。以下の通信路$P$の通信路容量$C$を求めてみます。
P &=
\begin{bmatrix}
1-p&p\\
q&1-q
\end{bmatrix}
\end{align}
散布度連立方程式($\ref{散布度連立方程式}$)は以下のようになります。
\begin{cases}
\displaystyle (1-p)x_{1}+px_{2} &= (1-p)\log(1-p)+p\log p = -\calH(p)\\[0.7em]
\displaystyle qx_{1}+(1-q)x_{2} &= q\log q+(1-q)\log(1-q) = -\calH(q)
\end{cases}
\end{align}
これを解くと，以下が得られます。
x_{1} &= \frac{p\calH(q)-(1-q)\calH(p)}{1-p-q} \\[0.7em]
x_{2} &= \frac{q\calH(p)-(1-p)\calH(q)}{1-p-q}
\end{align}
したがって，求める通信路容量$C$は以下のようになります。
C &= \log\left( 2^{p\calH(q)-(1-q)\calH(p)/(1-p-q)}+2^{q\calH(p)-(1-p)\calH(q)/(1-p-q)} \right)
\end{align}
おわりに
通信路容量の計算は少し複雑になって大変ですが，必ず一度は手を動かしてみましょう。冒頭でもお伝えした通り，通信路容量は学部レベルの情報理論でラスボス的存在ですから，本記事の内容をマスターすることを直近の目標にしてみるとよいかもしれません。
コメント
コメント一覧 （4件）
一般の通信路についてですが、(40)から(41)への式変形の部分はH(B|A)の部分のa_jとb_kが逆ではないですか？
nanana 様
ご指摘誠にありがとうございます。
一般の通信路に関して，本文を全面的に修正致しました。
ご確認いただけますと幸いです。
一般の通信路についてですが、(44)から(45)の変形は間違っていませんか？
また、(46)から(47)の導出の計算方法を教えていただければ大変助かります。
Donkey様
ご質問誠にありがとうございます。
>(44)から(45)の変形は間違っていませんか？
おっしゃる通り間違えておりました。修正致しました。
>(46)から(47)の導出の計算方法を教えていただければ大変助かります。
本文を追記しました。一部誤植がありましたので，お手隙の際に再度ご確認お願いできますでしょうか。