統計力学を用いた情報通信技術入門ーレプリカ法による性能

確率モデルを用いた
情報通信技術入門
ー誤り訂正符号を中心にー
東京工業大学大学院
知能システム科学専攻
樺島祥介
概要




誤り訂正符号とは
低密度パリティ検査符号
レプリカ法による性能評価
平均場近似による復号
誤り訂正符号とは

情報通信において、冗長な情報表現によ
り送信誤りを訂正する符号化技術
原情報
0010
復号
0010101
符号化
誤り訂正
0010101
符号語
送信
0110101
パリティ検査(I)

例）(7,4)ハミング符号の仕組み
原情報：x=(x0 x1 x2 x3)
x5
パリティビット：x4=x0+x2+x3
x5=x0+x1+x3
x6=x0+x1+x2
符号語：y=(x0 x1 x2 x3 x4 x5 x6)
x1
x6
x0
x2
x3
x4
符号の構成規則
パリティ検査(II)

z1=1
パリティ検査
z0=x0+x2+x3+x4
z1=x0+x1+x3+x5
z2=x0+x1+x2+x6
0
z2=1
誤りなし → (z0 z1 z2)=(0 0 0)
誤り検出 ← (z0 z1 z2)=(0 0 0)
1
1
0
1
(z0 z1 z2)=(0 0 1)～(1 1 1)の7通りが
7通りの1ビット誤りに対応
1ビット誤り訂正可能
0
1
z0=0
線形写像と符号化/復号

符号化は線形写像  復号は線形方程式
y= 1000 x=GTx
0100
0010
0001
1011
1101
1110
GT
z= 1011100 (y+n)=H(y+n)
1101010
=H n
1110001
H
ノイズを取り出す
＃重要な性質
HGT=0
低密度パリティ検査符号(I)


(7,4)ハミング符号を一般化
 N ビットの符号語を K ビットから作る
ただし、パリティ検査行列 H をランダムに生成
k
H= 0 1 0 0 0 … 0 0 1
00001…100
N-K 1 0 1 0 0 … 0 0 0
……………………
00010…010
N
j
現時点での最良
符号の一つ！
低密度パリティ検査符号(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
ni =
0, otherwise
<ni>=Σni P(n|z)：事後分布での期待値
性能評価問題

自然な疑問：
低密度パリティ検査符号はどの程度の誤り訂正能力
を備えるか？
 符号の能力はパラメータ(k,j)にどのように依存する
か？
＃とりあえず計算コストは考えないことにする


性能評価指標

ノイズ推定の平均ビット誤り率
[Pe]H =(1/N)Σ[δ(ni=ni)]n,H
伝統的符号理論の接近法



大自由度性（通常、N，Kは数千～）、離散
性のため直接評価困難
評価の容易な間接的指標（確率の上界、
最小符号語間距離等）に帰着
厳密ではあるが、あくまでも上界評価


痒いところに手が届かない
議論の展開が難解
統計力学による接近法

磁石の模型との類似性、大自由度性を利
用した直接的評価



痒いところに手が届く
議論の展開が素直
厳密性はこれからの課題
ゲージ変換

n の推定値を真値からの相対値で表現


シンドロームは常にz=0
推定値niの0,1が誤りのインジケータ
[Pe]H =(1/N)Σ[δ(ni=1)]n,H
1/2
= (1/N) Σ∫dx [δ(x-<ni>)]n,H
0
レプリカ法

「2重平均」を系統的に評価する方法

予稿参照
[δ(x-<ni>)]n,H
=∫dke-ikxΣ(xp/p!) [<ni>p]n,H

平均場モデル


要素間の入れ換え対称性＋大自由度性
レプリカトリックは平均場モデルなら容易に実行可能
物理学独特の接近法
平均場モデルとしての低密度パ
リティ検査符号
k

入れ換え対称性



H= 0 1 0 0 0 … 0 0 1
00001…100
N-K 1 0 1 0 0 … 0 0 0
……………………
00010…010
個々のＨにはない
平均的にはある
巨視的変数による記述
N
大自由度性

N,K :103～
大数の法則
N:大
N:小
m=(1/N)Σmi
j
性能評価の例

N=104, k=4, j=3
マーカーはノイズの真値
と復号結果との重なりrを
50回の実験に関し平均し
たもの．横軸はノイズの大
きさp．曲線は統計力学に
よる理論値．
復号のコスト


復号に必要な期待値<ni>=Σni P(n|z)の
計算はNP困難
なのになぜ復号できてるの？

統計力学の知見に基づく近似アルゴリズム
統計的情報処理の計算コスト

ベイズ統計による情報処理
見通し良い．性能良い．
 計算量的に実現困難．
例）誤り訂正符号の復号

<ni>=Σni P(n|z)
2N回の和が必要
＃ギブス学習、ベイズ学習、CDMAマルチユーザー復調等も同様
グラフ構造と計算可能性(I)

ただし、相互作用が特殊なグラフで表現さ
れる分布では爆発が生じない
結合無し（自明な例）
 1  mi Si 
PS    

2 
i 1 
N
 1  mi Si 
Si   Si PS    Si 
  mi
2 
S
Si  1 
＃計算コストは１自由度当たりO(1)
グラフ構造と計算可能性（II）

N 1

1次元鎖 exp
Si , Si 1 
PS  

 i 1


Z
以下の量を定義
 k 1

LSk    exp Si , Si 1 
S i k
 i 1

 N 1

RSk    exp Si , Si 1 
S i k
 i k

LSk 
k
RSk 
k
転送行列法
パスは一つ
漸化式
LS    expS , S LS 
RSk 1    expSk 1 , Sk RSk 

k 1
k 1
k
LSk 
k
LS k 1 
Sk
k
Sk


k 1
端から端でO(N)
平均
Sk 
 S LS RS 
S k  1
k
k
k
 LS RS 
S k  1
k
k
＃計算コストは１自由度当たりO(1)
k 1 k
RSk 1  RSk 
グラフ構造と計算可能性（III）




exp  Si , S j 
( ij )Tree


PS  
Z
木
転送行列法は木にも
一般化可能
k
ビリーフプロパゲーション

一般の分布で困難な理由

一般のグラフは分割不可能
k
結合があるため各々
独立に和を取れない
平均場近似

計算困難な分布を計算が容易な分布で近
似する
似させる
計
算
が
容
易
な
分
布
本物の分布
ナイーブ平均場近似
KLダイバージェンスを最小化するように
S 
Qを決める

minKLQ | P 
Q
Q
P
計
算
が
容
易
な
分
布
の
空
間
ベーテ（Bethe）近似

局所的に木構造を仮定して近似



低密度パリティ検査符号の復号アルゴリズム
Loopy Belief Propagation等とも呼ばれる
どんな理屈から導出されるのか？
木構造とKLダイバージェンス（I）

補題：Junction Tree Algorithm
ループがなければ結合確率を高速に以下の
表現に書き直すことが可能


exp  Sl   P Sl 




PS  

ql 1
Z
 P S l 


l
 PSl   PSl  :Reducibility
S j \l
Junction Tree
木構造とKLダイバージェンス
（II）

試験関数を以下のように仮定
 QS 
QS  
 Q S 
l

ql 1
l
l
 ただし

  QSl   QSl 
S

 j\l

KLダイバージェンス
QS 
QSl   Sl   ln QSl 
S QS ln PS   
 S
  ql  1 QSl  ln QSl   ln Z  0

l
l
Sl
木構造とKLダイバージェンス
（III）

KLダイバージェンスを最小化


答えはJTAの解（当たり前）
Reducibility が存在  QS   QS 
l
l
 S


⇒Lagrange未定乗数 
j \l
l Sl   ln rl Sl    ln rˆ l Sl 
 
Q Sl     exp Sl  rl Sl 

l

QSl    l  rˆ l Sl 

 l 

Lagrange未定乗数の決定

未定乗数は以下の方程式から決まる

rl Sl    l  rˆ l S l 

 l \ 
ˆ
ˆ








r
S


exp

S
r
S


l
l

l
l



j
j

j \ l



反復法で解ける
反復アルゴリズムは局所的な情報にしか依存し
ていない！
非木構造への拡張

一般のグラフに対しても以下のコスト関数
F Q   QSl  Sl   ln QSl 
 Sl
  ql  1 QSl  ln QSl 
l

Sl


  QSl   QSl 
S

 j\l

未定乗数の反復アルゴリズム

rl Sl    l  rˆ l S l 

 l \ 
ˆ
rl Sl   ˆ l exp Sl  rj S j 
j \ l

木構造ならKLD
最小化に一致
低密度パリティ検査符号とベー
テ近似


ベーテ近似の復号ななぜうまくいく？
低密度パリティ検査符号はランダムグラフ



ループは存在
ただし、ループの長さはO(ln N) 程度
N→∞でループの影響は無視できる

木構造による近似の妥当性
まとめ

大規模統計モデルに基づく情報処理



物理学における常套手段



性能評価問題
アルゴリズム開発
解析解の求まる(平均場)モデルを構成
解析解を起点に摂動で接近
この接近法はおそらく情報科学でも有効
参考文献


岩波講座物理の世界
学習と情報の平均場理論
樺島祥介著（定価1300円）
岩波講座
統計科学のフロンティア
(現在執筆中)
樺島祥介，上田修功共著

Download Report