KnoNの学び部屋

落ち着きのない大学院生が専攻に関係ない(むしろそっちのけで)学んだコトを記録しておく場所

通信の数学的理論 その6

どんなに頑張っても午前中は家事で潰れてしまう……。

 

引き続き

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

Ⅴ 連続情報源のレート

をやります。

 

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

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

 

 

Ⅴ 連続情報源のレート

 情報源が離散的である場合、情報を生成する明確な速度(レート)は基礎となる確率過程のエントロピーとして求めることが出来た*1

 しかし連続情報源に関しては状況はより複雑なものになる。

 

忠実度評価関数

 連続に変化する量は、無限個の値を取る=正確な記述のために無限個の2元記号を必要とする、と仮定される。これは現実的には不可能である。

→しかし実際で考慮されるのは、「ある許容範囲内の伝送」についてである。

 つまり「適切な方法で測られた、ある一定の復元の忠実度のみを要求するとき、明確なレート(伝送速度)を連続情報に付与できるか」という点が問題となる。

 

 まず「伝送の忠実度」の一般的な数学的定式化を行わなければならない。

→メッセージx、最終的な出力yに対し、全体的なシステムは確率関数{ \displaystyle P(x,y)}として記述される。

 そしてその忠実度(の尺度)は、2つの仮定をおくことにより次のような数値による評価関数によって表される。

  • 情報源とシステムがエルゴード的である
  • 標本時間Tを延ばすほど、仮の評価としておかれた{ \displaystyle \rho(x,y)}は定数に近づく*2

{ \displaystyle  v(P(x,y)) = \int\int P(x,y)\rho(x,y)dxdy}

 

※関数{ \displaystyle \rho(x,y)}は、xとyの間の「距離」に関する一般的な性質を有している*3

 

 これをまとめると、次のように言うことが出来る。

→「いかなる合理的な評価も、メッセージが得られる持続時間Tを十分長く取れば、メッセージxと復元メッセージyの集合上で、問題となる対{ \displaystyle (x,y)}を得る確率{ \displaystyle P(x,y)}で重みづけられた距離関数の平均として表現される」

 

 評価関数とする尺度は様々だが、次のような例が考えられる。

  1. 平均2乗規範:2値(xとy)の差の2乗をとり、持続時間Tでの平均を求める。
    { \displaystyle  \rho(x,y) = \frac{1}{T}\int_{0}^{T}[x(t) - y(t)]^2dt}
  2. 周波数重み付き平均2乗規範:平均2乗規範の前に、個々の周波数成分に対して重み付けを行う。
  3. 絶対誤り規範:2値の差の絶対値を取り、持続時間Tでの平均を求める。
    { \displaystyle  \rho(x,y) = \frac{1}{T}\int_{0}^{T}|x(t) - y(t)|dt}
  4. 普段の会話などにおける「明瞭さ」などの規範。実験などから経験的に得られる。
  5. 離散的な場合は、誤りの頻度に基づいた評価を暗黙のうちに仮定した特別な場合として取り扱える。

 

忠実度評価に関する情報源のレート

 連続情報源に対して生成される一般的な情報のレートを定義する。

 あるシステム{ \displaystyle P(x,y)}に対し、

  • 忠実度評価関数
    { \displaystyle  v(P(x,y)) = \int\int P(x,y)\rho(x,y)dxdy}
  • 2元記号の流れのレート
    { \displaystyle  R = \int\int P(x,y)\log\frac{P(x,y)}{P(x) P(y)}dxdy}

である。

 このとき、復元の際に定められた品質{ \displaystyle v_1}を有するための情報の生成レート{ \displaystyle R_1}を、品質{ \displaystyle v}{ \displaystyle v_1}に固定して{ \displaystyle P_x(y)}を変化させたときに得られる{ \displaystyle R}の最小値として定義する。

 すなわち、

{ \displaystyle  R_1 = \min\int\int P(x,y)\log\frac{P(x,y)}{P(x) P(y)}dxdy}

と拘束条件

{ \displaystyle  v_1= \int\int P(x,y)\rho(x,y)dxdy}

である。

→要求される忠実度({ \displaystyle v_1}、任意に設定)を満たす、全ての可能な通信システム({ \displaystyle P(x,y)})の中から、その時のレート({ \displaystyle R(P_x(y))})を最小にするものを選ぶ、ということを意味する。

定理21:

 もし情報源が評価{ \displaystyle v_1}でレート{ \displaystyle R_1}を有するならば、その情報源の出力を符号化したのち、{ \displaystyle R_1 \leq C}を満たす容量{ \displaystyle C}を有する通信路を通じて、望むだけ{ \displaystyle v_1}に近い忠実度でその出力を送ることが出来る。

 これは{ \displaystyle R_1 > C}ならば不可能である。

 

 

レートの計算

 情報源のレートを与える一般の最大化問題の解は、ラグランジュの方式などを用いて求めることが出来る。

→しかしこれによって与えられる形式的な解は、個別の場合においては計算することが困難であり、実質的な意味を持たない。

 

 実際のレートの計算はいくつかのとても簡単な場合にしか行われていない。 

→例えば「距離関数{ \displaystyle \rho(x,y)}がxとyの平均2乗誤差(例1)」「メッセージのアンサンブルが白色雑音」ならば、レートを決定することが出来る。

定理22:

 電力{ \displaystyle Q}と帯域{ \displaystyle W_1}とを有する白色雑音情報源の、平均2乗忠実度尺度に関するレートは、次のように与えられる。

{ \displaystyle  R = W_1\log\frac{Q}{N}}

 

 ここで、{ \displaystyle N}は元のメッセージと復元されたメッセージの間の許容平均2乗誤差である。

 

 より一般的には、メッセージの情報源がいかなる場合であれ、平均2乗誤り規範に関するレートを制限する不等式を得ることができる、

定理23:

 帯域 { \displaystyle W_1}を有する任意の情報源に対するレートは、次の不等式に寄って制限される。

{ \displaystyle  W_1\log\frac{Q_1}{N} \leq R \leq W_1\log\frac{Q}{N}}

 

 ここで、{ \displaystyle Q}{ \displaystyle Q_1}はそれぞれ情報源の平均電力とエントロピー電力であり、また{ \displaystyle N}は許容平均2乗誤差を示している。

 

 

【今回の三行まとめ】

  • 連続情報源において「厳密に正確な」伝送を行うことは不可能である。実際上の問題として、ある一定の「復元の忠実度」を持たせた時のレートについて考える。
  • 連続情報源のレートは「品質{ \displaystyle v}{ \displaystyle v_1}に固定して{ \displaystyle P_x(y)}を変化させたときに得られる{ \displaystyle R}の最小値」として定義される。
  • その計算は一般的には現実的ではないが、平均2乗誤り規範に関するレートに対してはそれを評価する不等式を得ることが出来る。

 

【今回の宿題】

  • 伝送の忠実度を数式化する時の仮定の2つ目
  • 評価関数とする尺度のそれぞれ、特に4.について

 

……実は「レート」ってものの感覚がまだよくわかっていなかったり。しかし論述自体は明瞭で分かりやすい内容だった。

 これで本文は終了です。明日は「訳者解説」を追いながら全体のまとめをおこないます。

 

それでは

 

KnoN(90min)

*1:通信の数学的理論 その2(前編)(追記あり) - KnoNの学び部屋

*2:テキスト原文がイマイチ要領を得ない説明なので、これでまとまっているか自信がない。要確認。

*3:しかし厳密には「距離」ではない。本文の脚注参照のこと。