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

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

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

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

パリティ検査(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ビット誤り訂正可能

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

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

低密度パリティ検査符号(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

復号問題とベイズ統計 ノイズ ｎ は確率的 ベイズ統計 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)：事後分布での期待値

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

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

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

ゲージ変換 = (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

レプリカ法 [δ(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 物理学独特の接近法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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