KnoNの学び部屋

大学に8年在籍した後無事に就職した会社員が何かやるところ。

通信の数学的理論 その2(前編)(追記あり)

数式部分が穴あきのままだけど、時間がかかりそうなのでとりあえずこのまま公開。 

→7/24追記しました。

 

引き続き

通信の数学的理論 (ちくま学芸文庫)クロード・シャノン、2009)

Ⅰ 離散的無雑音システム

をやります。

 

通信の数学的理論 (ちくま学芸文庫)

通信の数学的理論 (ちくま学芸文庫)

 

Ⅰ 離散的無雑音システム

 まずは通信の最も簡単な状況として「発信される情報が離散的」「雑音が存在しない」設定を考える。

 

通信路容量の定義

 一般に、離散的通信路とは「基本的な記号{ \displaystyle S_1,S_2,……,S_n}の有限集合からの選択によって得られた系列を、あるところから別のところに伝えられるシステム」を意味する。各記号{ \displaystyle S_i}は、時間にして{ \displaystyle t_i}秒の持続時間を持つ。

→このとき通信路が伝達できる情報の容量をどのようにして測るか、ということが問題となる。

 

 記号の長さが異なり、伝送が許される系列に対して制約がある場合、離散的通信路の容量Cにたいして次のような定義を行う。

{ \displaystyle  C = \lim_{T \to \infty} \frac{\log N(T)}{T} }

ただしN(T):持続時間Tをもつ許容系列の数

 

 これは定数Aと特性方程式

{ \displaystyle X^{-t_1}+X^{-t_2}+……+X^{-t_n} = 1}

の最大の実数解X0を用いて、漸近的に{ \displaystyle AX^t_0}とかける*1

 したがって

{ \displaystyle C = \lim_{T \to \infty} \frac{\log AX^t_0}{T} = \log X_0 }

が成り立つ。

 

 許容系列に対して課される可能性のある極めて一般的な種類の制約は、次のようなものである。

  • いくつかの可能な状態{ \displaystyle a_1,a_2,……,a_m}にのそれぞれに対し、集合{{ \displaystyle S_1,S_2,……,S_n}}に属する一部の記号のみが伝送できるとする。
  • これらの記号の中から一つが送信されたとき、元の状態と伝送された特定の記号の両方に依存して、状態は新しい状態に遷移する

 この状態は(図2)のような線図で表すことが出来る。

 

定理1:

 状態iにおいて送信可能であり、送信によって状態がjに遷移するs番目の記号の持続時間を{ \displaystyle b^{(s)}_{ij}}で表す。

 このとき、通信路の容量Cはlog Wに等しい。

{ \displaystyle  C = log W }

 ただしWは次の行列式の最大の実数解である。

{ \displaystyle \left| \sum_{}^{s} W^{-b^{(s)}_{ij}} - \delta_ij \right| = 0 }

 また{ \displaystyle \delta_{ij} }はi=jのときにかぎり1であり、その他の場合は0である。

 

情報源の統計的性質:マルコフ過程

 適切な符号化を用いて通信路に要求される容量を減らすには、情報源に関する統計的な知識を把握する必要がある。

→例えば電信において伝送されるメッセージは文字の系列からなっているが、その系列は完全にランダムではない。英語の統計的な構造を持つ文字の系列ならば、文字Eの頻度は文字Qに比べ大きく、文字列THは文字列XPより頻繁に出現する。

 

 離散的情報源は確率過程、それもマルコフ過程によって表現されると考えられる。

 また逆に、有限の集合から選ばれた記号の離散系列を生み出すいかなる確率過程もまた離散的情報源とみなしてよい。*2

→この状況は(図2)のような線図によって表現できる。

 

 マルコフ過程の中で、「エルゴード過程」と呼ばれるものは通信理論において特別な性質を有する。

→エルゴード過程においては、確率過程から得られる全ての系列が同一の統計的性質を有している。

統計的均質性を持つ。

 

 線図が次の二つの性質の持つならば、それに対応する過程はエルゴード的である。

  1. 線図は独立した二つの部分からなる、のではない。
  2. 線図における全ての閉路の長さの最大公約数が1である。
    (閉路長=矢印が全て同じ方向を向き、線が一続きになって閉じている部分(閉路)を構成する線の数)

 

エントロピーに対するタスク分析

 情報源をマルコフ過程として表現したとき、どのようにすれば「情報源からどのくらいの生成速度(レート)で情報が生成されたか」を測る量を定義できるだろうか。

 

 生起確率{ \displaystyle p_1,p_2,……,p_n}を有する可能な事象の集合に対し、その「選択性」を測る尺度として{ \displaystyle H(p_1,p_2,……,p_n) }があるとかんがえる。

 このHに求められる性質は次のようなものである(=尺度Hにたいするタスク分析)。

  1. Hは{ \displaystyle p_i}について連続でなければならない。
  2. もし全ての{ \displaystyle p_i}が等しく{ \displaystyle p_i=\frac{1}{n}}であるならば、Hはnに関する単調増加関数である。
  3. もし選択が二つの連続した選択に分けられたならば、元のHは個別のHの値の加重和にならなければならない。

 

定理2:

 上記3つの過程を満足するただ一つのHは次の形式である。

{ \displaystyle H = -K\sum_{i=1}^{n}p_i\log p_i}

(ただしKは正の定数)

 これは統計力学の中で定義されるエントロピーと同じ形をしている。

 

 このように定義される量Hは、選択や情報の合理的な尺度であることを自ら立証するいくつかの興味深い性質を有している。

  1. 実現値が確定しているときに限り、Hはゼロになる。
    →起こることがわかっているときH=0で最小となる。
  2. 与えられたnに対し全ての{ \displaystyle p_i}が等しく{ \displaystyle \frac{1}{n}}のとき(もっとも不確かなとき)、Hは最大値{ \displaystyle log n}をとる。
  3. 同時事象の不確かさは、個別の事象の不確かさの和に等しいか、それより小さい。
    → { \displaystyle H(x,y) \leq H(x) + H(y) }
  4. 確率{ \displaystyle p_1,p_2,……,p_n}の均等化に向けた、どのような確率の変更もHを増加させる。
    →不確かさが増すほどHは大きくなる。
  5. 独立ではない同時事象x,yの不確かさは、xの不確かさに、xがわかっている時のyの不確かさ(条件付きエントロピー)を加えたものである。
    → { \displaystyle H(x,y) = H(x)+H_x(y) }
  6. yの不確かさは、xの知識によって増えることはない。
    → 3.と5.の式より
      { \displaystyle H(x)+H(y) \geq H(x,y)=H(x)+H_x(y)}
     →{ \displaystyle H(y) \geq H_x(y)}

 

 

【今回の三行まとめ】

  • 離散的無雑音通信路における通信路の容量は[定理1]によって求められる。
  • 離散的情報源はマルコフ過程(特にエルゴード過程)によって表される。適切な符号化によって通信の効率を向上させるために、情報源の統計的性質を把握しなければならない。
  • 「情報の生成速度を測る量」として情報のエントロピーHを定義できる([定理2])。これは尺度Hに対するタスク分析から求められるとともに、尺度とするにふさわしい性質を有している。

【今回の宿題】

  • 「離散的通信路の容量C」をあっさり定義しているが、そこにいたる過程はどうなっているのか。
  • 「生成速度」を測る量が「選択性」を測る量に、いつのまにか変わってしまっている気がする。この二つはどのように結びつけられているのか。
  • 数式を表記するために多少のTexの勉強を。

 

……丁寧に、丁寧に読めば前回よりはわかりやすかった。ちゃんと数式の変形を納得しながら追えば。ここでは面倒なので書いてないけど。

 もう少し数学的な素養があればより理解しやすいとおもうが、今のところはなんとかなっている。

 「エントロピー」をどのように求めたかがはっきりしてすっきりした。

 数式の表記についてはなんとか対応を考えないと。これまでのようなごまかしではちょっときつい。

 

それでは

 

KnoN(120min)

 

*1:そうらしい。数学的な証明は(めんどくさいので)省略する。

*2:テキストではこの部分について丁寧な実例解説がなされているが、本稿では割愛する。

ついでにいうと、英語におけるアルファベットの統計的な出現確率についてシャノンは「適当な本をランダムに開き、そのページの1文字目を選ぶ。別のページを開き、その文字が出るまで読み進める。その次の文字を記録する」という方法をとっている。

いい加減なように見えて、結構精度が高い近似が得られているのかもしれない