Document

レプリカ法における解析接続と
誤り指数評価
東京工業大学大学院
知能システム科学専攻
樺島祥介
(共同研究者：中村一尊，J. van Mourik)
4/12/2002
@ SMAPIP2002
Tokyo Institute of Technology
1
背景と目的

背景



統計力学の計算技法を情報科学に応用した
研究が一定の成果を挙げている
ただし，「厳密でない」ために信用されないこと
も多い
目的


怪しそうな問題点を整理する
情報科学と関係付ける→誤り指数評価
4/12/2002
@ SMAPIP2002
＃伊庭（1989）
Tokyo Institute of Technology
2
概要




低密度パリティ検査符号
典型集合復号の誤り指数
レプリカ法による評価と解析接続
まとめと展望
4/12/2002
@ SMAPIP2002
Tokyo Institute of Technology
3
誤り訂正符号

ノイズによる送信誤り
1 p
0
p
p
1

誤り訂正符号

1 p
0
1
情報表現を冗長にすることで誤りを訂正でき
る仕組みを与える
4/12/2002
@ SMAPIP2002
Tokyo Institute of Technology
4
低密度パリティ検査符号(I)


Gallager (1962)
ランダムな疎パリティ行列に基づく符号
k
N  K  0 1 0 0  1 0


1 0 0 1  0 0 
H 
       


 0 0 1 0  1 0


j
N
4/12/2002
@ SMAPIP2002
Tokyo Institute of Technology
5
低密度パリティ検査符号(II)

生成行列GT ：K
N
N K
H
ビット→N ビット
K
G
T

K
0
符号化率
K
R
N
N K
N
4/12/2002
@ SMAPIP2002
Tokyo Institute of Technology
6
低密度パリティ検査符号(III)


符号化 x  G m (mod2)
送受信
T
y  x  n  G m  n (mod2)
T

復号(I):誤りの推定
z  Hy  HG m  Hn  Hn (mod2)
T

復号(II):メッセージの復元
G m  y  n (mod2)
T
4/12/2002
@ SMAPIP2002
Tokyo Institute of Technology
7
復号問題

復号の本質はパリティ検査方程式
Hn  z (mod2)

目的に応じて様々な解法がある



最良性：最尤復号，周辺尤度最大化
実用性：信念伝播法，RandomSearch
解析の容易さ：典型集合復号
4/12/2002
@ SMAPIP2002
Tokyo Institute of Technology
8
典型集合

大数の法則：符号長が長いときほとんど全
てのノイズベクトル n に対して
 
1 N

nl  p  O N , 0    1/2

N l 1

この式を満たすノイズベクトルを典型（的）
系列，その集合を典型（的）集合という
4/12/2002
@ SMAPIP2002
Tokyo Institute of Technology
9
典型集合復号


典型集合からパリティ検査方程式を満
たすベクトルをランダムに１つ選ぶ
２つの誤りの可能性
I. 真のノイズが典型系列でない
II. 真のノイズが典型系列であり，かつ複数の
典型系列がパリティ検査方程式を満たす

大数の法則から，タイプI.の誤り確率は
符号長とともにゼロに漸近
4/12/2002
@ SMAPIP2002
Tokyo Institute of Technology
10
符号のアンサンブル


ランダムに構成した低密度パリティ検査符
号には極端に性能の悪い符号が符号長の
負冪程度含まれている
以下では，典型的な符号性能を評価する
ためにそれらを除いたアンサンブル
(expurgated ensemble)を考察する
4/12/2002
@ SMAPIP2002
Tokyo Institute of Technology
11
インジケータと誤り確率

タイプII.の誤りに関するインジケータ
1, タイプ II.の誤りが生じた場合
 II n , H  
0, そうでない場合


0

タイプII.の誤り確率
N



0
0
PII H    II n , H    nl  Np 
 l 1



4/12/2002
@ SMAPIP2002

Tokyo Institute of Technology
12
インジケータのレプリカ表現

パリティ検査を満たす典型系列の数
N


0
0
 n , H   Hn  Hn    nl  Np 
 l 1

n n 0






レプリカ表現


 II n 0 , H  lim   n 0 , H
4/12/2002
@ SMAPIP2002
 0

 1
  0
1
0
1
Tokyo Institute of Technology
2

13
平均誤り確率の誤り指数

誤り確率のアンサンブル平均
  0
 N 0

PII  lim  n , H    nl  Np 
  0
 l 1


 lim exp N  ; R, p   exp NE R, p 


  0

誤り指数
E R, p   lim   ; R, p 
  0
4/12/2002
@ SMAPIP2002
Tokyo Institute of Technology
14
レプリカ法による評価と
解析接続

誤り指数の評価は難しい



0
 n , H     Hn  Hn    nl  Np  
 l 1

 n n 0



0



N

ただし，が自然数の時だけは

 N a

a
0
  Hn  Hn    nl  Np  
 n ,H 


 l 1

n1 ,n 2 ,,n  n 0 a 1 


0




＃和の展開可能
4/12/2002
@ SMAPIP2002
Tokyo Institute of Technology
15
レプリカ法（予稿を修正）

熱力学的極限：N →∞のとき自然数に対し，
平均評価
 鞍点法，大偏差理論，組み合わせ論，etc
＃実際的にはほぼ鞍点法

解析接続：レプリカ添え字に関し対称性の制約
を課した評価結果は実数に対しても定義可能
＃自然数に対しては複数の対称性が同一結
果を導く
4/12/2002
@ SMAPIP2002
Tokyo Institute of Technology
16
あり得る問題(1)：極限の取替え

評価したいのは
  0
 N 0

PII  lim  n , H    nl  Np 
  0
 l 1




lim lim
N     0

評価できるのは
lim lim
  0 N  

多くの場合ＯＫ

でも，今の場合は証明できていない（とりあえず前へ）
4/12/2002
@ SMAPIP2002
Tokyo Institute of Technology
17
鞍点法


exp[Nf(x)] の複素積分を f’(x)=0 となる
点（鞍点）の値で近似
利点：



簡単
鞍点が単一ならN→∞で厳密
注意すべき点：


場合によっては「極小値」を与える
鞍点が複数ある場合は最大値を選ぶ必要
4/12/2002
@ SMAPIP2002
Tokyo Institute of Technology
18
鞍点法関連で生じ得ること


負のエントロピー（SK，REM）
ヘシアンの反転（SKモデル）
  0

鞍点値の逆転(誤り指数評価)
  0
A
4/12/2002
@ SMAPIP2002
B
A
B
Tokyo Institute of Technology
19
あり得る問題(２)：対称性の不定性

複数の対称性が自然数に対し同一結果
＃ヘシアンの反転，負のエントロピーを解決する
シナリオ
0
4/12/2002
@ SMAPIP2002
1
2
3
Tokyo Institute of Technology

20
あり得る問題(３)：解析接続

未解決の問題
＃ の低い方が鞍点は優位
  
  
1

(a)自然数で優位
4/12/2002
@ SMAPIP2002
どっち？
1

(b)極限を取ったあと優位
Tokyo Institute of Technology
21
誤り指数評価と解析接続


低密度パリティ検査符号の誤り指数評価
は解析接続の問題が露になる
しかも，情報理論ではk,j→∞での正解が
知られている
4/12/2002
@ SMAPIP2002
Tokyo Institute of Technology
22
結果（k,j→∞のとき）


２つの鞍点系列
情報理論の正解に合わせるためには
自然数で優位な系列を選択すべき
  
  
0
1

0
4/12/2002
@ SMAPIP2002
Tokyo Institute of Technology
1

23
結果（k,j→∞のとき）

誤り指数
for R  1  H 2 ( p)
0,
E ( R, p)  
ln 2(1  H 2 ( p)), for R  1  H 2 ( p)
E ( R, p)
 1
Rc   0
0
4/12/2002
@ SMAPIP2002
Tokyo Institute of Technology
R
24
結果(有限のk,j )


２つの鞍点系列（数値的評価）
自然数で優位性が変化する可能性

1付近で優位な系列を選ぶ以外方法はない
4/12/2002
@ SMAPIP2002
Tokyo Institute of Technology
25
結果(有限のk,j )

誤り指数

情報理論の下限と赤い部分で一致
E ( R, p)
 1
0   1
0
4/12/2002
@ SMAPIP2002
Rb
  0
Rc
Tokyo Institute of Technology
R
26
まとめと今後の展望





誤り指数の問題ではレプリカ法の問題点（特に
解析接続）があらわになる
一部厳密解が知られているのでSKモデルより検
討しやすい（と思う）
有限のk,j で情報理論の枠組みから詰める
シミュレーションとの比較
極限取替えの証明（鞍点法を使わない）
4/12/2002
@ SMAPIP2002
Tokyo Institute of Technology
27

Download Report