確率モデルを用いた 情報通信技術入門 ー誤り訂正符号を中心にー

Presentation on theme: "確率モデルを用いた 情報通信技術入門 ー誤り訂正符号を中心にー"— Presentation transcript:

1 確率モデルを用いた 情報通信技術入門 ー誤り訂正符号を中心にー
東京工業大学大学院 知能システム科学専攻 樺島祥介

2 概要 誤り訂正符号とは 低密度パリティ検査符号 レプリカ法による性能評価 平均場近似による復号

3 誤り訂正符号とは 情報通信において、冗長な情報表現により送信誤りを訂正する符号化技術 原情報 0010 0010101 0010101
復号 0010 符号化 誤り訂正 符号語 送信

4 パリティ検査(I) 例）(7,4)ハミング符号の仕組み 原情報：x=(x0 x1 x2 x3) x5 パリティビット：x4=x0+x2+x3
符号語：y=(x0 x1 x2 x3 x4 x5 x6) 符号の構成規則

5 パリティ検査(II) 1ビット誤り訂正可能 パリティ検査 z1=1 z0=x0+x2+x3+x4 z1=x0+x1+x3+x5
z0=x0+x2+x3+x4 z1=x0+x1+x3+x5 z2=x0+x1+x2+x6 z2=1 1 1 1 1 誤りなし　 →　(z0 z1 z2)=(0 0 0) 誤り検出　←　(z0 z1 z2)=(0 0 0) z0=0 (z0 z1 z2)=(0 0 1)～(1 1 1)の7通りが 7通りの1ビット誤りに対応 1ビット誤り訂正可能

6 線形写像と符号化/復号 H GT ＃重要な性質 HGT=0 符号化は線形写像 復号は線形方程式
　復号は線形方程式 y= 1000 x=GTx 0100 0010 0001 1011 1101 1110 z= (y+n)=H(y+n) =H n H ノイズを取り出す ＃重要な性質 GT HGT=0

7 低密度パリティ検査符号(I) 現時点での最良 符号の一つ！ (7,4)ハミング符号を一般化 N ビットの符号語を K ビットから作る
ただし、パリティ検査行列 H をランダムに生成 k 現時点での最良 符号の一つ！ H= … 0 0 1 … 1 0 0 … 0 0 0 …………………… … 0 1 0 j N-K N

8 低密度パリティ検査符号(II) K×N 生成行列 GT s.t. HGT=0 符号化： y=GTx 送信（誤り発生）： y+n=GTx+n
パリティ検査： z=H(y+n)=H(GTx+n)=Hn 復号(I)： z=Hn 　→　n どう解くか？ 復号(II)： y=GTx　→　x

9 復号問題とベイズ統計 ノイズ ｎ は確率的 ベイズ統計 P(n|z) ＝ P(z|n)P(n) = δ(z=Hn)P(n)
ノイズビット毎の最適推定 P(z) Σδ(z=Hn)P(n) 1, if <ni> > 1/2 0, otherwise ni= <ni>=Σni P(n|z)：事後分布での期待値

10 性能評価問題 [Pe]H =(1/N)Σ[δ(ni=ni)]n,H 性能評価指標 自然な疑問： ノイズ推定の平均ビット誤り率
低密度パリティ検査符号はどの程度の誤り訂正能力を備えるか？ 符号の能力はパラメータ(k,j)にどのように依存するか？ ＃とりあえず計算コストは考えないことにする 性能評価指標 ノイズ推定の平均ビット誤り率 [Pe]H =(1/N)Σ[δ(ni=ni)]n,H

11 伝統的符号理論の接近法 大自由度性（通常、N，Kは数千～）、離散性のため直接評価困難
評価の容易な間接的指標（確率の上界、最小符号語間距離等）に帰着 厳密ではあるが、あくまでも上界評価 痒いところに手が届かない 議論の展開が難解

12 統計力学による接近法 磁石の模型との類似性、大自由度性を利用した直接的評価 痒いところに手が届く 議論の展開が素直 厳密性はこれからの課題

13 ゲージ変換 = (1/N) Σ∫dx [δ(x-<ni>)]n,H [Pe]H =(1/N)Σ[δ(ni=1)]n,H
シンドロームは常にz=0 推定値niの0,1が誤りのインジケータ [Pe]H =(1/N)Σ[δ(ni=1)]n,H = (1/N) Σ∫dx [δ(x-<ni>)]n,H 1/2

14 レプリカ法 [δ(x-<ni>)]n,H =∫dke-ikxΣ(xp/p!) [<ni>p]n,H
「2重平均」を系統的に評価する方法 予稿参照 平均場モデル 要素間の入れ換え対称性＋大自由度性 レプリカトリックは平均場モデルなら容易に実行可能 [δ(x-<ni>)]n,H =∫dke-ikxΣ(xp/p!) [<ni>p]n,H 物理学独特の接近法

15 平均場モデルとしての低密度パリティ検査符号
H= … 0 0 1 … 1 0 0 … 0 0 0 …………………… … 0 1 0 k j N-K N 入れ換え対称性 個々のＨにはない 平均的にはある 大自由度性 N,K :103～ 巨視的変数による記述 N:大 大数の法則 N:小 m=(1/N)Σmi

16 性能評価の例 N=104, k=4, j=3 マーカーはノイズの真値と復号結果との重なりrを50回の実験に関し平均したもの．横軸はノイズの大きさp．曲線は統計力学による理論値．

17 復号のコスト 復号に必要な期待値<ni>=Σni P(n|z)の計算はNP困難 なのになぜ復号できてるの？
統計力学の知見に基づく近似アルゴリズム

18 <ni>=Σni P(n|z)
統計的情報処理の計算コスト ベイズ統計による情報処理 見通し良い．性能良い． 計算量的に実現困難． 例）誤り訂正符号の復号 <ni>=Σni P(n|z) 2N回の和が必要 ＃ギブス学習、ベイズ学習、CDMAマルチユーザー復調等も同様

19 グラフ構造と計算可能性(I) ただし、相互作用が特殊なグラフで表現される分布では爆発が生じない 結合無し（自明な例）
　結合無し（自明な例） ＃計算コストは１自由度当たりO(1)

20 グラフ構造と計算可能性（II） 1次元鎖 　以下の量を定義

21 転送行列法 パスは一つ 漸化式 端から端でO(N) 平均 ＃計算コストは１自由度当たりO(1)

22 グラフ構造と計算可能性（III） 木 転送行列法は木にも 　一般化可能　 ビリーフプロパゲーション

23 一般の分布で困難な理由 一般のグラフは分割不可能 結合があるため各々 独立に和を取れない

24 平均場近似 計算困難な分布を計算が容易な分布で近似する 似させる 計算が容易な分布 本物の分布

25 ナイーブ平均場近似 KLダイバージェンスを最小化するように 　　 を決める 計算が容易な分布の空間

26 ベーテ（Bethe）近似 局所的に木構造を仮定して近似 低密度パリティ検査符号の復号アルゴリズム
Loopy Belief Propagation等とも呼ばれる どんな理屈から導出されるのか？

27 木構造とKLダイバージェンス（I） 補題：Junction Tree Algorithm :Reducibility
ループがなければ結合確率を高速に以下の表現に書き直すことが可能 Junction Tree :Reducibility

28 木構造とKLダイバージェンス（II） 試験関数を以下のように仮定 KLダイバージェンス ただし

29 木構造とKLダイバージェンス（III） KLダイバージェンスを最小化 Reducibility が存在 ⇒Lagrange未定乗数
答えはJTAの解（当たり前） Reducibility が存在 ⇒Lagrange未定乗数

30 Lagrange未定乗数の決定 未定乗数は以下の方程式から決まる 反復法で解ける 反復アルゴリズムは局所的な情報にしか依存していない！

31 非木構造への拡張 一般のグラフに対しても以下のコスト関数 未定乗数の反復アルゴリズム 木構造ならKLD 最小化に一致

32 低密度パリティ検査符号とベーテ近似 ベーテ近似の復号ななぜうまくいく？ 低密度パリティ検査符号はランダムグラフ
ベーテ近似の復号ななぜうまくいく？　 低密度パリティ検査符号はランダムグラフ ループは存在 ただし、ループの長さはO(ln N) 程度 N→∞でループの影響は無視できる 木構造による近似の妥当性

33 まとめ 大規模統計モデルに基づく情報処理 物理学における常套手段 この接近法はおそらく情報科学でも有効 性能評価問題 アルゴリズム開発
解析解の求まる(平均場)モデルを構成 解析解を起点に摂動で接近 この接近法はおそらく情報科学でも有効

34 参考文献 岩波講座 物理の世界 学習と情報の平均場理論 樺島祥介著（定価1300円） 岩波講座 統計科学のフロンティア (現在執筆中)
岩波講座　物理の世界 学習と情報の平均場理論 樺島祥介著（定価1300円） 岩波講座　 統計科学のフロンティア (現在執筆中) 樺島祥介，上田修功共著