【徹底解説】通信路容量の求め方マスター講座

URLをコピーする
URLをコピーしました!
zuka

こんにちは。
zuka(@beginaid)です。

本記事では,通信路容量の求め方を網羅的にまとめていきます。通信路容量は,情報理論では避けては通れない重要なトピックです。線形代数の学部レベルのゴールが行列の$n$乗とするなら,情報理論の学部レベルのゴールは通信路容量を求めることでしょう。通信路容量はそれだけ様々な要素が詰まった重要なトピックです。そんな通信路容量の求め方を通信路の種類別にまとめていきます。

本記事では初学者の分かりやすさを優先するため,多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。

目次

通信路の分類

まずは,通信路を分類していきます。

  • 雑音のない通信路
  • 確定的通信路
  • 一様な通信路
  • 二元対称通信路
  • 一般の通信路

雑音のない通信路

雑音のない通信路とは,$b_k\rightarrow a_j$が1通りしかないような通信路です。つまり,$p(a_j|b_k)$が$0$か$1$となります。具体的には,以下のような通信路行列$T$をイメージしてもらえればと思います。

\begin{align}
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$をイメージしてもらえればと思います。

\begin{align}
T&=
\begin{bmatrix}
1 & 0 \\
0 & 1 \\
1 & 0 \\
0 & 1 \\
0 & 1 \\
\end{bmatrix}
\end{align}

一様な通信路

一様な通信路とは,通信路行列の各行が,全て要素を入れ替えただけの関係になっているような通信路を指します。具体的には,以下のような通信路行列$T$をイメージしてもらえればと思います。

\begin{align}
T&=
\begin{bmatrix}
1-p-q & q & p \\
p & q & 1-p-q \\
\end{bmatrix}
\end{align}

二元対称通信路

二元対称通信路は,頻出の通信路です。以下の通信路行列$T$で表されます。

\begin{align}
T&=
\begin{bmatrix}
p & q \\
q & p \\
\end{bmatrix}
\end{align}

結論

これらの通信路について,それぞれ以下のように通信路が求められます。

雑音のない通信路

\begin{align}
\max \left\{ H(A) \right\}
\end{align}

確定的通信路

\begin{align}
\max \left\{ H(B) \right\}
\end{align}

一様通信路

\begin{align}
\max\left\{H(B)\right\} – \sum_{k=1}^K p(b_k|a_j)\log\frac{1}{p(b_k|a_j)}
\end{align}

二元対称通信路

\begin{align}
\max\left[\calH\left\{\omega(1-p-q)+q\right\} – \omega \calH (p) – (1-\omega)\calH (q)\right]
\end{align}

一般の通信路

\begin{align}
\log \sum_{k=1}^{K}2^{x_k}
\end{align}

ただし,上の表で利用した記号は以下のとおりです。

記号内容
$A$入力記号
$B$出力記号
$K$出力記号数
$\calH$エントロピー関数
$x_k$$\sum_{j=1}^{J}p(a_j|b_k)\log p(a_j|b_k)$
記号一覧

以下では,通信路の種類別に通信路容量の求め方を確認していきます。

証明

雑音のない通信路

$p(a_j|b_k)=0,1$ということから,エントロピー$H(A|B)$が$0$となることが分かります。したがって,通信路容量$C$は以下のように求められます。

\begin{align}
C &= \max \left\{ I(A;B) \right\}\\
&= \max \left\{ H(A) – H(A|B) \right\}\\
&= \max\left\{H(A) \right\}
\end{align}

確定的通信路

$p(b_k|a_j)=0,1$ということから,エントロピー$H(B|A)$が$0$となることが分かります。したがって,通信路容量$C$は以下のように求められます。

\begin{align}
C &= \max \left\{ I(A;B) \right\}\\
&= \max \left\{ H(B) – H(B|A) \right\}\\
&= \max\left\{H(B) \right\}
\end{align}

一様な通信路

一様な通信路では,以下のようにすれば$H(B|A)$を「一行だけについて注目すればよい」ことが分かります。感覚的には,全ての行が同じ要素で構成されているため,$p(a_j)$が足し合わされて$1$になるイメージです。

\begin{align}
C &= \max \left\{ I(A;B) \right \} \\
&= \max \left\{ H(B) – H(B|A) \right\}\\
&= \max\left\{ H(B) – \sum_{j=1}^{J}p(a_j) \sum_{k=1}^K p(b_k|a_j)\log\frac{1}{p(b_k|a_j)} \right\}\\
&= \max \left\{ H(B) – \sum_{k=1}^K p(b_k|a_j)\log\frac{1}{p(b_k|a_j)}\right\}\\
&(\because \text{各}j\text{について}p(b_k|a_j)\text{は同じで}\sum_{j=1}^J p(a_j)=1)\notag \\
&= \max \left\{ H(B) \right\} – \sum_{k=1}^K p(b_k|a_j)\log\frac{1}{p(b_k|a_j)}
\end{align}

二元対称通信路

定義通り素直に計算するだけです。$p(a_1)=\omega$ときます。$H(A)$は簡単に計算できますので,相互情報量の2通りの変形のうち,$I(A;B)=H(A)-H(A|B)$と変形する方を考えましょう。結局は$H(B)$も計算することになりますが。兎にも角にも,まずは$H(A)$を計算してしまいます。

\begin{align}
H(A) &= \omega\log \frac{1}{\omega} + (1-\omega)\log \frac{1}{1-\omega}\\
&= \calH (\omega)
\end{align}

続いて,$H(A|B)$を計算します。条件付きエントロピーのままでは計算できないため,以下の関係を利用します。

\begin{align}
H(A|B)=H(A,B) – H(B)
\end{align}

さて,$H(A,B)$から求めていきます。

\begin{align}
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 \\
&\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)}\\
&= \omega(1-p) \log \frac{1}{\omega(1-p)} + \omega p \log\frac{1}{\omega p}\notag \\
&\quad + (1-\omega)q \log\frac{1}{(1-\omega)q} + (1-\omega)(1-q) \log\frac{1}{(1-\omega)(1-q)}\\
&= \calH (\omega) + \omega \calH (p) + (1-\omega)\calH (q)
\end{align}

次に,$H(B)$を求めます。

\begin{align}
p(b_1) &= p(a_1)p(b_1|a_1) + p(a_2)p(b_1|a_2)\\
&= \omega (1-p) + (1-\omega)q\\
&= \omega (1-p-q) + q\\
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-q) + q\right)
\end{align}

以上から,$H(A|B)$は以下のようになります。

\begin{align}
H(A|B)&=H(A,B) – H(B)\\
&= \left\{ \calH (\omega) + \omega \calH (p) + (1-\omega)\calH (q)\right\} – \calH \left(\omega (1-p-q) + q\right)\\
&= \calH (\omega) + \omega \calH(p) + (1-\omega)\calH (q) – \calH \left(\omega (1-p-q) + q\right)
\end{align}

したがって,通信路容量は以下のようになります。

\begin{align}
C &= \max \left\{ I(A;B) \right\}\\
&= \max \left\{ H(A) – H(A|B) \right\}\\
&= \left\{ \calH (\omega) \right\} – \left\{ \calH (\omega) + \omega \calH (p) + (1-\omega)\calH(q) – \calH\left(\omega (1-p-q) + q\right) \right\}\\
&= \omega \calH (p) + (1-\omega) \cal{H}(q) – \calH \left(\omega (1-p-q) + q\right)
\end{align}

一般の通信路

一般の通信路の通信路容量ですが,機械学習でよく用いられる式変形を利用します。まず,日本語で説明してみます。

$I(A;B)$を$p(b_k)$のみで表して$\sum_k p(b_k)=1$の条件下での最大値を求める

この方針のもと,相互情報量$I(A;B)$の最大値を求めていきます。条件付き最大最小問題なので,ラグランジュの未定乗数法を利用します。ラグランジュ関数を$L$とおくと,以下のように表すことができます。

\begin{align}
L &= I(A;B) + \lambda \left( \sum_k p(b_k)-1 \right)
\end{align}

まずは,$I(A;B)$を$p(b_k)$のみで表してみましょう。

\begin{align}
I(A;B) &= H(B) – H(B|A)\\
&= \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 \frac{1}{p(a_j|b_k)}\\
&= \sum_{k=1}^K p(b_k)\log \frac{1}{p(b_k)} – \sum_{k=1}^K p(b_k) x_k
\end{align}

ただし,簡単のため$x_k= \sum_{j=1}^{J}p(a_j|b_k)\log p(a_j|b_k)$とおきました。この相互情報量を,ラグランジュ関数に代入して最大最小問題を解きましょう。

\begin{align}
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)\\
\frac{\partial L}{\partial p(b_k)} &= -\log p(b_k) – \log e + x_k + \lambda\\
&= 0
\label{lag_func}
\end{align}

ここで,機械学習でもよく用いるアイディアなのですが,導関数$=0$の式の両辺に$p(b_k)$をかけます。

\begin{align}
-p(b_k) \log p(b_k) – p(b_k)\log e + p(b_k)x_k + p(b_k)\lambda &= 0
\end{align}

両辺の$k$についての和をとります。

\begin{align}
\sum_{k=1}^K\left\{ -p(b_k) \log p(b_k) – p(b_k)\log e + p(b_k)x_k + p(b_k)\lambda\right\} &= 0\\
-\sum_{k=1}^Kp(b_k) \log p(b_k) – \sum_{k=1}^K p(b_k)\log e + \sum_{k=1}^Kp(b_k)x_k + \sum_{k=1}^Kp(b_k)&=0\\
-\sum_{k=1}^Kp(b_k) \log p(b_k) – \log e + \sum_{k=1}^K x_k + \lambda&=0\quad (\because \sum_{k=1}^Kp(b_k)=1)
\label{lag_cap}
\end{align}

ここで,相互情報量の式を今一度確認してみます。

\begin{align}
I(A;B) = \sum_{k=1}^K p(b_k)\log \frac{1}{p(b_k)} – \sum_{k=1}^K p(b_k) x_k
\end{align}

よくよく見てみると,式(\ref{lag_cap})の中に$I(A;B)$が入っていることが分かります。しかし,今回は$I(A;B)$が最大になるときを考えていますので,$I(A;B)=C$となります。

\begin{align}
C – \log e + \lambda &= 0 \\
\end{align}

したがって,式(\ref{lag_cap})から以下が分かります。

\begin{align}
\lambda &= -C + \log e
\label{lam_cap}
\end{align}

式(\ref{lam_cap})を式(\ref{lag_func})に代入します。

\begin{align}
-\log p(b_k) x_k – C &= 0\\
p(b_k) &= 2^{x_k – C}
\end{align}

両辺の$k$についての和をとります。これで一般の通信路容量の式が導出されました。

\begin{align}
\sum_{k=1}^K p(b_k) &= \sum_{k=1}^K 2^{x_k – C}\\
1 &= 2^{-C}\sum_{k=1}^K2^{x_k}\\
C &= \log \sum_{k=1}^K 2^{x_k}
\end{align}

zuka

お疲れ様!通信路容量の計算は少し複雑になって大変だけど,必ず一度は手を動かしてみるといいよ。冒頭でもお伝えしたとおり,通信路容量は学部レベルの情報理論でラスボス的存在だから,こいつをマスターすることを目標にしてみるといいかも。

シェアはこちらからお願いします!
URLをコピーする
URLをコピーしました!

コメント

コメントする

目次
閉じる