preprint
日本神経回路学会誌

解Vol. 13, No. 1（2006），19–27

説

ニューラルネットワーク理論と符号
三 村

和 史

広島市立大学情報科学部∗

Theory of Neural Networks and Coding
Kazushi Mimura
Faculty of Information Sciences, Hiroshima City University∗
概要
ニューラルネットワークの解析に適用されている統計力学的な手法は，確率モデルで記述できる課題に対して性能評価だけにとどまらず実用的なアルゴリズム開発へも役立っている．本稿では，ニューラルネットワークの解析が，情報処理の課題へどのように適用されているかについて有歪圧縮を例として解説する．

1. は じ め に
ニューラルネットワークのひとつである Hopﬁeld モデル1) の解析に適用されて以来，統計力学的な解析手法
はパーセプトロンの容量評価2, 3) や学習理論4) など様々な情報処理の問題に適用されている．特に通信路符号化の分野で，Sourlas 符号をはじめとして LDPC 符号など性能評価にとどまらず，効率的な復号化アルゴリズ
ムも開発されるなど活発に研究が進められている5–11) ．
情報源符号化12) においても有歪圧縮などの研究がなされ，Shannon が示した理論的な性能限界を達成する有歪圧縮法がいくつか発見された13–15) ．有歪圧縮では，理論的な性能評価が先行して実用的なアルゴリズムの開発が遅れていたが，最近になって高速な符号化アルゴリズムが発見され話題をよんでいる16) ．

∈ J M を長さ N の圧縮符号  = F( ) ∈ X N に変換する．復号器 G は圧縮符号  = t (ξ1 , · · · , ξN ) を用いて，再び長さ M の復元情報 ˆ = G( ) ∈ JˆM に戻す．この場合，圧縮率は R = N/M であり，情報圧
縮ではいつも N < M なので R < 1 となっている．
圧縮率は符号化レート（または単にレート）とも呼ばれる．
歪測度は，原情報アルファベット J と復元情報アルファベット Jˆ の組から非負実数への写像 d : J × Jˆ →[0, ∞) である．多くの場合，原情報のアルファベット

J は復元情報のアルファベット Jˆ と同じである．以降，J = Jˆ ≡ {−1, 1} とし歪測度は，d(Jµ , Jˆµ ) =0,1,Jµ = JˆµJµ = Jˆµ(1)

本稿では，具体的な例として有歪圧縮を具体的な例
として取り上げ，ニューラルネットワークの解析に用いられている統計力学的手法がどのように情報通信のの Hamming 距離とした場合について考える．通常，
情報は 0,1 の 2 値で表現されることが統計力学的な解
析に便利なように，より対称性の高い −1, 1 の表現を分野に適用されているかについて解説する．

利用することが多い．このようにおいても，一般性を失うことはない．この Hamming 距離では，期待値がˆ = P [J = J]
ˆ とビット誤り率となっている．
E[d(J, J)]

2. 情 報 源 符 号 化
まず，レート歪理論を簡単に紹介しよう．有限な原情報アルファベット J をもつ無記憶情報源を考える．この情報源からの長さ M の系列 = t (J 1 , · · · , J M ) ∈J M について考える．符号器 F は長さ M の原情報
∗ 〒 731-3194 広島県広島市安佐南区大塚東 3-4-1

ここで，E ，P はそれぞれ期待値と確率を表す．2 つの系列 = (J µ ), ˆ = (Jˆµ ) ∈ J M について，d( , ˆ ) =M1d(J µ , Jˆµ )
M µ=1

(2)

20

日本神経回路学会誌と歪測度を拡張して，原情報と復元情報の平均歪をˆ )] と定義する．ここで，符号化レート
D = E[d( , （圧縮率）と許容歪の組 (R, D) が到達可能であるとは，
圧縮符号長 N が十分に大きい極限で平均歪が許容歪ˆ )] ≤ D を満たすよう以下となる，すなわち E[d( , 
な符号器と復号器の組 (F, G) が存在することをいう．
到達可能なレート歪対 (R, D) の集合を到達可能域という．レート歪関数 R(D) とは，与えられた許容歪 Dに対して，レート歪対 (R, D) の到達可能域の R の下限を与える関数のことである．
一般に，具体的に与えられた個々の情報源や歪測度に対して，レート歪関数を解析的に求めることは困難である．以降，簡単のため原情報アルファベットはP [J µ = 0] = P [J µ = 1] = 1/2 とビットの偏りがない場合について考えよう．このような偏りがない 2 元
定常無記憶情報源で，歪測度に Hamming 距離を用いる場合に関しては，R(D) = 1 − h2 (D)(3)

Vol. 13, No. 1（2006）

reproduced
sequencecodeword

J

ξ

J
XN

sourcesequence

J M, J M

Fig. 2 ランダム符号化の模式図．すべての圧縮符号（□印）に対してランダムに復元情報（○印）を予め決めておく．符号化は，原情報（×印）との歪が最も小さい復元情報を探して，その最適な復元情報に対応する圧縮符号を選ぶ．

3. ランダム符号化法と 解 析 的 に レ ー ト 歪 関 数 が 与 え ら れ る ．こ こ で ，h2 (x) = −x log2 x − (1 − x) log2 (1 − x) である．これランダム符号化法は，Shannon が通信路符号化定理の証明に用いた誤り訂正符号であるが，有歪圧縮に対は，Shannon 限界と呼ばれる．一方，符号器と復号器の組 (F, G) を指定したうえで，与えられた許容歪 Dに対して (R, D) の到達可能域の R の下限を与える関しても同様の考え方が適用できる．

数はレート歪特性と呼ばれる．符号器と復号器 (F, G)の性能の良さはレート歪特性が Shannon 限界にどれくらい近いかで判断される．さらに，実用的な観点では更に符号化や復号化に必要な計算量が，符号長の多項式程度であることが重要である．
情報圧縮の模式図を図 1 に示す．有歪圧縮では，復号器 G を先に構成しておくのが一般的である．このとき符号器 F は，復号したときに最も歪が小さくなる
ような圧縮符号を探せばよいので単に，F( ) = argmin d( , G()),

∈X N

(4)

とすればよい．

JF
encoderξGJ

decoderFig. 1 情報圧縮の模式図. 符号長 M の原情報  を
符号器 F によって，符号長 N (< M ) の圧縮
符号  へ符号化する．復号器 G は圧縮符号 ˆ に戻す．
から元の符号長 M の復元情報 

復号化： 圧縮符号の長さを N ビットとする．復号
器は，この 2N 通りある圧縮符号それぞれに対応する M ビットの復元情報を予めランダムに決めておいて，この対応関係を保存しておく．復号は，単にこの対応関係を参照することによって行う．
符号化： 一方，符号器は復号器に保存されている対応関係にある復元情報の中から，原情報と最も歪が小さくなるものを探す．その最良の復元情報に対応する圧縮符号を出力する．
この様子を図 2 に示す．このランダム符号化法のレート歪特性は，Shannon 限界を達成できるが，残念ながら復号器で 2N 個の対応関係を保存しておく必要がある上に，符号器でも 2N 回の比較が必要であるため，現実的な符号化法とはいえない．
保坂は，パーセプトロンの容量計算と同様にレプリカ法によってもレート歪関数が導出できることを示した17) ．解析結果は，復号したとき歪が最小となる圧縮符号が複数あることが示唆する．圧縮符号と復元情報の対応関係をランダムに決めているので，これは圧縮符号がばらばらに存在してその平均は 0 になることに21

三村和史：ニューラルネットワーク理論と符号µ対応すると考えられる．このため，圧縮符号の平均が0 となることが，Shannon 限界を達成するために必要であると予想される．

x1

s1

µ

x2

Kabashima は，最も単純な学習機械のひとつであるパーセプトロンが通信に利用できることを指摘した．
さらに，Hosaka らはこの考えを応用して有歪圧縮法を提案し，レート歪特性が Shannon 限界を達成する
ことを示した13) ．まず，パーセプトロンを簡単に紹介
して，それがどのように通信に利用できるかについて説明しよう．
4.1 パーセプトロンµ

プトロンは，特にイジングパーセプトロンと呼ばれている．パーセプトロンは，N 次元の入力ベクトル
Ü = t (x1 , · · · , xN ) ∈ N と結合荷重ベクトル × の内
積 × · Ü によって，

Êy = f (× · Ü)

(5)を出力する．この関数 f を出力関数という．ここで，閾値は入力ベクトル Ü の要素うちのひとつを 1 とおくと導入できるので省略した．例えば，xN = 1 とお
くと sN が閾値の役割をはたす．
いま，M 個の入出力例 {(Ü1 , J 1 ), · · · , (ÜM , J M )}について考えよう．パーセプトロンの学習とは，すべての入出力例について，

J µ = f (× · Üµ )(6)を満たす結合荷重 × を求めることである．以降，情報通信を考えるので，× ∈ X ≡ {−1, 1}, J µ ∈ J ≡{−1, 1}, f :Ê→ J = {−1, 1} というように，2 値の場合に限定して考えることにする．
4.2 パーセプトロンの容量

では，入出力例を正しく再現できる例題数 M はどれくらいであろうか．素子数に応じて正しく再現できる例題数には上限がある．この上限を素子数 N で割ったものをパーセプトロンの容量という．
容量は，与えられた入出力例を全て正しく再現でき
る結合荷重ベクトル × の数を求めることで評価できる．
1

1

先ほどの M 個の入出力例 {(Ü , J ), · · · , (Ü , J
M

M

)}

µ

x )

sN

xN

Fig. 3 パーセプトロン．結合荷重ベクトル × を調整することによって，入出力関係を学習する．
について考えよう．これらは確率変数であるとする．
まず最初に，さらにこれらのうち µ 番目の入出力例(Üµ , J µ ) ひとつだけに限定して考えよう．いま，

パーセプトロンとは，図 3 のようなニューラルネッ
トワークの基本素子である．パーセプトロンは，結合荷重を適切に変更することにより与えられた入出力関係を学習するモデルとなっている．N 次元の結合
荷重を × = t (s1 , · · · , sN ) ∈ X N とする．結合荷重を X = {−1, 1} のように 2 値に限定したパーセ

f( s

s2

4. パーセプトロンと通信

Θ(x) =

1,0,

x > 0,
otherwise,(7)という階段関数を用いると，Θ[J µ f (× · Üµ )] は，入出力関係が正しく (Üµ , J µ ) となるときに 1 となり，間違ってしまうときに 0 になる関数であることがわかる．
これより，ある結合荷重ベクトル × を持つパーセプト
ロンが入出力例を全て正しく再現するときは，M1Θ[J µ f (× · Üµ )] = 1,
M µ=1

(8)

が成り立つことになる．素子数が N のイジングパー
セプトロンでは，結合荷重ベクトル × ∈ {−1, 1}N は
2N 通りが考えられる．この 2N 通りの結合荷重ベク
トルのうち，(8) 式の値が 1 になる結合荷重ベクトル
の数は，

NG =



δ

×∈{−1,1}N

1 
M

M µ=1



Θ[J µ f (× · Üµ )] − 1 ,(9)と評価できる．この数は Gardner 体積と呼ばれている．ここで， δ はデルタ関数である．結合荷重ベクトルの要素当たりのエントロピー SG は対数をとって，

SG =1< ln NG >Â ,Ü ,N

(10)と求めることができる．ここで，個々の入出力例の実現値に依存しない議論とするために，それらに関する平均 < >Â ,Ü をとっている．組合せ論的な議論から，
例題数を M = αN と一定に保っておく．容量は，エントロピーが 0 になるような最小の比 α で求められることになる．このエントロピーは次の恒等式，∂Z nn→0 ∂nln Z = lim

(11)

22

日本神経回路学会誌を使って対数関数の期待値計算をべきの期待値計算に置き換えることで計算できる．この恒等式を使った計算方法はレプリカ法と呼ばれている．自然数の n に対して，n → 0 の極限をとることの数学的な正当性は示されていないとはいうものの，これまでなされてきたレプリカ法による結果は実験を実によく説明できている．

Vol. 13, No. 1（2006）

クトル × ∈ X N を決められる訳ではない．パーセプト
ロンを用いた通信では，パーセプトロンの容量を超えないようにするためや，誤り訂正の能力を決めるために，素子数 N の調節が必要である．
4.4 パーセプトロンを用いた情報圧縮
パーセプトロンを用いた情報通信で，容量のことを気にせずに任意にパーセプトロンの素子数 N を小さ

解析では鞍点法を適用するために，素子数と例題数を比 α を一定に保っておいて N, M → ∞ としてエントロピー SG を計算する．出力関数が f (x) = sgn(x)くするとどうなるであろうか．N < M となるように
N を選べば，データ圧縮と同じである．比 R = N/Mと符号関数のとき SG = 0 となる最小の α を求めると，単調イジングパーセプトロンの容量 αc = 0.83 が得られる3) ．

出力関係を正しく学習できないかもしれないので，できるだけ多くの入出力関係を再現するように結合荷重ベクトルを決めるようにする．このため，データは復4.3 パーセプトロンを用いた情報通信
では，次にどのようにパーセプトロンを通信に利用するかについて説明する．いま，M ビットの情報

Â = t (J 1 , · · · , J M ) ∈ {−1, 1}M の通信方法について考えよう．情報通信にはノイズがつきものなので，その対策として送信側では誤りを訂正するために何らかのを圧縮率（符号化レート）と呼ぶ．ただし，すべての入号しても元通りになるとは限らない．このような不可逆な圧縮を有歪圧縮という．パーセプトロンを用いた
有歪圧縮は，次のようにするとよい．
符号化：

1. M 個の入力ベクトル Ü1 , · · · , ÜM ∈ÊN をランダムに生成する．

符号化を施して情報を冗長にしておくことが多い．この符号化に，パーセプトロンを利用する．まず，送信側と受信側の両方で，素子数が N 個のパーセプトロ

2. できるだけ入出力関係が (Ü1 , J 1 ), · · · , (ÜM , J M )となるような結合荷重ベクトル × ∈ X N を見つンと，同じ乱数生成用の関数を予め用意しておく．その上で次のようにする．

3. 結合荷重ベクトル × ∈ {−1, 1}N と入力ベクト

ける．

ルの生成に使った乱数のタネを送信する．
送信：

1. M 個の入力ベクトル Ü1 , · · · , ÜM ∈ÊN をランダムに生成する．
2. 入出力関係が (Ü1 , J 1 ), · · · , (ÜM , J M ) となる
ように結合荷重ベクトル × ∈ X N を見つける（学習に対応する）．
3. 結合荷重ベクトル × ∈ {−1, 1}N と入力ベクトルの生成に使った乱数のタネを送信する．
受信：

1. 受信した乱数のタネを使って，送信側と同じ M
個の入力ベクトル Ü1 , · · · , ÜM を生成する．
2. 受信した結合荷重ベクトル × を使って，パーセ
プトロンで復号する．
これは乱数のタネを除くと，M ビットの情報 Â を N

ビットの情報 × への変換を表している．
と こ ろ で ，パ ー セ プ ト ロ ン が 正 し く 学 習 で き る
入出力関係の数には上限（パーセプトロンの容量）が あ るの で ，送 信者 は い つ でも 全 て の 入出 力 関 係(Ü1 , J 1 ), · · · , (ÜM , J M ) を満たすように，結合荷重ベ復号化：
1. 受信した乱数のタネを使って，送信側と同じ M
個の入力ベクトル Ü1 , · · · , ÜM を生成する．

2. 受信した結合荷重ベクトル × を使って，パーセ
プトロンで復号する．

通信のときと比べて，符号化の手順 2 を少し変更しているが後は同じである．このように，パーセプトロンの結合荷重ベクトル × が圧縮符号の役割をはたすことがわかる．上記の復号化法を G̃ とおく．この符号化は，(4) 式の符号化と同じである．
レート歪特性は，次のようにして評価できる13) ．まず，許容歪 D を指定する．原情報と復元情報の歪d(Â , G̃(×)) が許容歪 D 以下になるような最小の圧
縮率 R を求めればよい．圧縮符号（結合荷重ベクトル） × の長さを N (= RM ) としたとき，原情報と復元情報の歪がちょうど許容歪と等しくなるような圧縮
符号 × の数 NC (D) を求めてみる．このような圧縮符
号がひとつでも存在すれば，レート歪対 (R, D) は到
達可能である．先程と同様に，圧縮符号数 NC (D) は，

NC (D) =×∈{−1,1}N

23

三村和史：ニューラルネットワーク理論と符号δ D − d(Â , G̃(×)) ,

(12)

x 1µ

s1

と評価できる．圧縮符 号 1 ビット当りのエントロ
ピー SC (D) は対数をとって，SC (D) = N −1 <ln NC (D) >Â ,Ü となる．容量はエントロピーが 0 になるような最小の圧縮率 RC (D) によって，レート歪特性 R = RC (D) を求めることができる．レート歪特性は，圧縮率 R と許容歪 D の関係を表しているので，ある圧縮率 R を与えたときの最小の歪 D を与える特性と読み替えることもできる．
ところで歪を許容しない場合について考えると，この有歪圧縮法は全ての入出力関係を正しく再現する結合荷重ベクトルを探すことになるので，パーセプトロ
ンの容量評価問題と全く同じ問題のはずである．実際，原情報と復元情報の歪が，
M





1
d(Â , G̃(×)) =1 − Θ[J µ f (× · Üµ )] ,
M µ=1

y

x Kµ

sK

Fig. 4 木構造 3 層パーセプトロン．出力素子の出力が中間素子の出力の多数決で決まるものをコ
ミティマシン，積で決まるものをパリティマシ
ンという．

5.1 非単調パーセプトロン復号器
(13)

(14)

となることがわかる．これは，許容歪が D = 0 のときの最小の圧縮率 RC (0) が，用いるパーセプトロンの容量の逆数 1/αc と一致することを示す（逆数になるのは，R の定義を M/N ではなく N/M としたためである）．単調イジングパーセプトロンの容量は αc = 0.83なので，単調イジングパーセプトロンを用いた有歪圧
縮法では許容歪を 0 にしようとすると，最小の圧縮率
は RC (0) = 1/αc  1.2 となり，かえって圧縮符号の方が長くなってしまう．Shannon 限界は (3) 式のレート歪関数より R(0) = 1 < RC (0) となるので，単調イ
ジングパーセプトロンを用いた有歪圧縮法ではレート
歪特性が Shannon 限界を達成できないことは明らかである．

5. 学習機械を用いた有歪圧縮
ここまでの議論では，情報通信や情報圧縮に用いる



Hosaka らは，次のような偶関数の出力関数
f (x) =

で与えられることに注意すると，NC (0) = NG ,

^µ

1,
−1,

|x| < k,otherwise,(15)をもつ非単調イジングパーセプトロンを復号器として用いた有歪圧縮を提案して，レプリカ法によってレー
ト歪特性を解析的に評価した13) ．出力関数のパラメー
タ k を最適化すると，レート歪特性は Shannon 限界を達成できること示されている．
レプリカ法による解析では，圧縮符号となりえる符
号の間のオーバーラップ（方向余弦）が求められる．
この量は，Edwards-Anderson (EA) オーダーパラ
メータと呼ばれている．いま，µ 番目の入力パター
ン Üµ に対する非単調イジングパーセプトロンの出力µ(×) ≡ f (× · Üµ ) とすると出力関数 f が偶関数
を GNP
なので，
µ
µ
GNP
(−×) = GNP
(×),

(16)

となっていることがわかる．このため，圧縮符号 × に対して必ず −× という符号も同じ歪を持つ，つまり原点を対称に圧縮符号が存在するので，EA オーダーパ

モデルはパーセプトロンに限定していたが，同じ長さの適当な可変パラメータ × を含む関数 g(Ü; ×) を用いても同じ議論が成り立つ．初めてパーセプトロンを用

ラメータは 0 となる．

いた有歪圧縮法を提案した Hosaka らが用いた非単調
イジングパーセプトロンによる方法のほか13) ，学習の統計力学で詳しく議論されてきた木構造 3 層パーセプ
トロンも有歪圧縮への適用が Mimura らによってなさのような木構造 3 層パーセプトロンへ拡張した有歪圧縮法について性能評価を行なった．3 層パーセプトロ
ンは，各中間素子が全ての入力素子と結合した完全結合 3 層パーセプトロンと，各入力素子がそれぞれひと

れており15) ，これらの結果を簡単に紹介する．

つの中間素子にのみ結合している木構造 3 層パーセプ

5.2 コミティツリー復号器
Mimura らは非単調パーセプトロン復号器を，図 4

24

日本神経回路学会誌

1

呼ばれる中間素子の出力の積によって出力を決める出
力素子を採用した木構造 3 層パーセプトロンを復号器に使ってみよう．µ 番目の入力パターン Üµ に対する

theoretical prediction (K=1)
theoretical prediction (K=3)
theoretical prediction (K)
rate distortion function

0.8

Vol. 13, No. 1（2006）

パリティツリーの出力は，
0.6
R

×) ≡

GPµ T (

0.4



sgn

l=1

0.2
0

K


0

0.1

0.2

0.3

0.4

0.5

D

Fig. 5 コミティマシンを用いた有歪圧縮法のレート歪特性．中間素子数が増えると性能はよくなる
が，中間素子数が無限大の極限でも Shannon
限界は達成できない．

K×l · Üµl ,N(18)である．コミティマシンの場合と同様に，中間素子の出力関数は符号関数 sgn とした．
図 6 にパリティツリーを用いた有歪圧縮法のレート
歪特性を示す．このときももちろん，中間素子数 K = 1のときは単調イジングパーセプトロンを用いた場合と同じである．中間素子数が K ≥ 2 では，レート歪特性はレート歪関数に一致することが解析的に示される．

AT 不安定性を計算すると，中間素子数が K = 2 のときだけレプリカ対称解が不安定な領域がすこしあることがわかる．

トロンがよく解析されている．結合荷重が圧縮符号の役割をはたすので，完全結合 3 層パーセプトロンは結合荷重の数が多くなりすぎるため情報圧縮には適して

中間素子数が K ≥ 2 のとき Shannon 限界を達成
するが，このときも EA オーダパラメータは 0 になっている．パリティツリーの出力は，いない．このため，木構造 3 層パーセプトロンについてのみ考える．
入力素子を N ，中間素子数を K とする．各中間素

GPµ T (−×) = (−1)K GPµ T (×),

子は N/K 個の入力素子と結合し，出力素子は全ての中間素子を結合荷重 1 の一定値で結合している．中間素子の出力の多数決によって出力を決める出力素子を採用した木構造 3 層パーセプトロンをコミティツリー（またはコミティマシン）という．
µ 番目の入力パターン Üµ に対するコミティツリーの出力を，×) ≡ sgn

µ
GCT
(

K



sgn

l=1

K
×l · Üµl
N


,

(17)

と す る ．こ こ で ，Üµ = t (Ü1 , · · · , ÜK ), ×µ =µt
(×µ1 , · · · , ×K ) とし，中間素子の出力関数は符号関数
sgn とした．この場合は，非単調イジングパーセプトロµµ

ンのときのような圧縮符号の対称性はなく，EA オー
ダパラメータも全ての K で 0 にはならない．
図 5 にコミティツリーを用いた有歪圧縮法のレート
歪特性を示す．中間素子数 K = 1 のときは，単調イ
ジングパーセプトロンを用いた場合と同じである．中間素子数を増やすとレート歪特性がよくなることがわ(19)となるので，中間素子数 K が偶数個なら非単調パー
セプトロンの場合と同様な対称性があることがわかる．
奇数個ならこのような対称性は一見なさそうに見える．

しかし，圧縮符号 × = t (×1 , ×2 , ×3 , · · · , ×K ) のうち複数個のブロックの符号を反転させた符号，例えば，t(−×1 , −×2 , ×3 , · · · , ×K ) は × と復号したとき同じ歪となる．このような符号は全部で 2K−1 個あるので，それらの和は 0 となり EA オーダパラメータはやは
り 0 になる．図 7 にこの様子を示す．図 7 (a) は，非単調パーセプトロンを用いたとき，圧縮符号 ×, −× が同じ復元情報を出力することを示す．図 7 (b) のように，単調パーセプトロンではこの対称性はない．図 7(c) の K = 2 パリティツリーのときは (a) と同様である．図 7 (d) は K = 3 パリティツリーのときの様子を示す．(×1 , ×2 , ×3 ), (−×1 , −×2 , ×3 ), (×1 , −×2 , −×3 ),(−×1 , ×2 , −×3 ), という 4 つの符号が同じ復元情報を出力する．

6. LDGM 符 号

5.3 パリティツリー復号器

Murayama らは，パーセプトロンの代わりに LDPC
符号で使うような疎行列を用いた有歪圧縮法を提案した14) ．用いる疎行列 A は，1 が各行に K 個，各列にC 個しかなく，その他の要素は 0 の M × N 行列で

そこで，パリティツリー（またはパリティマシン）とある．復号化を次の線形変換

かるが，中間素子数を K → ∞ の極限でもレート歪関数（Shannon 限界）には達しないことがわかる．

25

三村和史：ニューラルネットワーク理論と符号1の極限をとると，LDGM 符号のレート歪特性は Shannon 限界を達成できることが示されている14) ．また，Shannon 限界を達成するこの極限の場合も EA オーダ
パラメータ（関数）は 0 （デルタ関数）となる．K, Cが有限のときでも，レート歪特性はかなり Shannon 限

theoretical prediction (K = 1)
rate distortion function& theoretical prediction (K >= 2)
AT line (K = 2)

0.8

R

0.6

界に近い14) ．

0.4

7. ア ル ゴ リ ズ ム
0.2
0では，これらの有歪圧縮法において，圧縮符号はどのようにして求めればよいであろうか．パーセプトロ
0

0.1

0.2

0.3

0.4

0.5

D

Fig. 6 パリティマシンを用いた有歪圧縮法のレート歪特性．中間素子数が K ≥ 2 以上で，Shannon
限界を達成する．中間素子数が K = 2 のときだけレプリカ対称解が不安定な領域（レート歪み関数と AT 線で囲まれた細い領域）がある．
−

s

+

O

-s

+

s

ン，3 層パーセプトロン，疎行列を用いた有歪圧縮方法の符号化は，全て (4) 式のように 2N 個ある圧縮符号の候補  から復号情報の歪 d( , G()) が最も小さくなる圧縮符号を探すというものである．これには指数関数的な計算量が必要であり実行が困難なので，実用のためには計算量を減らす工夫が必要となる．
そこで，まず逆温度と呼ばれるパラメータ β を導入して，次の Boltzmann 分布p(| ) ∝ e−βd( ,G()) ,

O

-s

−

(a)

を考えよう．原情報  が与えられたときの圧縮符号が  となる事後確率が，この Boltzmann 分布で与えられると考えるのである．このとき，歪 d( , G̃()) の最小化は，Boltzmann 分布 p(| ) の最大化と等価と

−

(b)
+

(21)

−

なっている．(4) 式の符号化は，
−

+

−

O

+

+

F( ) = argmax p(| ),∈{−1,1}N

O

+

−
+
(c)

と書き直すことができるので，事後確率最大化 (Maximum A Posteriori: MAP) 推定とよばれている．このまま実行しようとすると，MAP 推定の計算量もや−(d)Fig. 7 復元情報の各ビットと圧縮符号の関係．記号 +,− はそれぞれ復元情報のビットが 1, -1 であることを表す．圧縮符号の集合 {−1, 1}N は，互いに直交する法ベクトルをもつ K 枚の超平面で分割される．(a) 非単調パーセプトロン．
(b) 単調パーセプトロン．(c) K = 2 パリティツリー．(d) K = 3 パリティツリー．EA オー
ダパラメータは (b) の場合だけ 0 にならない．
GLDGM () = A

はり指数関数的である．
一方，圧縮符号を探索する範囲を絞るために事後確率 p(| ) の周辺事後確率p(sl | ) =\slp(| ),

(23)を使う方法もある．符号器を F( ) = t (F 1 ( ), · · · , F M ( ))としたとき，周辺事後確率によって圧縮符号を要素ごとに，F µ ( ) = argmax p(sl | )(mod 2),sl ∈{−1,1}(20)で定義する．ただし，符号は全て {0, 1} の 2 値表現とする．符号化は，(4) 式の符号化と同じである．この符号は，LDGM (Low Density Generator Matrix) 符号と呼ばれている．K(22)

N を保ったまま，K, C → ∞=sgn < sl >p(s | ) ,l(24)と求める方法は周辺事後確率最大化 (Maximizer ofPosterior Marginals: MPM) 推定と呼ばれている．ここで，< >p(s | ) は分布 p(sl | ) での期待値を表す．
l26

日本神経回路学会誌

Vol. 13, No. 1（2006）

MPM 推定では，単に p(sl = −1| ) と p(sl = 1| )の 2 つの確率を比較して，p(sl = −1| ) の方が大きければ −1 として，p(sl = 1| ) の方が大きければ 1とするだけで済む．これは，sl の期待値の符号をとる

codewords
ξ
γ>0

ことと同じ操作である．
逆温度は次のように設定する．デルタ関数の積分表
i∞ dβ βxe より，(12) 式の状態数 NC (D)示 δ(x) = −i∞ 2π

γ=0は Boltzmann 分布 exp[−βd( , G̃())] の分配関数の形となっていることがわかる．この逆温度に対応するパラメータ β はレプリカ解析ではオーダパラメータとinitial state
O

して取り出せる．ビリーフプロパゲーションを実行するときに用いる逆温度は，エントロピーが SC (D) = 0となるときのオーダパラメータ β の値を用いればよい．
逆温度を β → ∞ とすると，歪が最小とならない圧縮
符号の事後確率は 0 になるので，MPM 推定の結果はMAP 推定の結果と一致する．

Fig. 8 慣性項を導入したビリーフプロパゲーションのダイナミクス（模式図）．圧縮符号の推定値

MPM 推定では，探索範囲を限定できる代わりに (23)式の周辺事後確率には，2N−1 個の項の和を計算する必要があるので，やはりそのままでは MPM 推定も（□印）の推移を表す．破線は，圧縮符号を復元した情報と原情報の歪の等高線であり，圧縮符号のととろがくぼんでいる．圧縮符号の平指数関数的な計算量が必要になってくることが問題となる．このため，ビリーフプロパゲーションを適用して周辺事後確率の期待値計算を近似的に行なうことで，均は 0 なので，慣性項がない γ = 0 のとき，
圧縮符号の推定値は原点へ移動する（一点鎖線）．慣性項がある γ > 0 のとき，圧縮符号符号化の計算量を減らすことが試みられている16, 18) ．
さらに，デンス系では中心極限定理を適用して，計算量を減らすなどの工夫が必要である．
しかしながら，ここでもまた問題が起こる．例えば，
非単調パーセプトロンを用いた方法では，圧縮符号 と同じ歪となる符号 − が必ず存在するために，周辺事
後確率は必ず p(sl = −1| ) = p(sl = 1| ) = 1/2 となってしまう．このため，期待値は < sl >p(s | ) = 0lとなってしまい，圧縮符号の推定がうまくできない17) ．
他の方法でも，EA オーダパラメータが 0 であれば同じ問題が起こることになる．

7.1 慣性項を導入したビリーフプロパゲーション
この問題を解決するためには，ビリーフプロパゲー
ションの改良が必要であった16) ．ビリーフプロパゲー
ションは，確率分布 p(| ) が，p(| ) =

 φ ( |J µ )
e µ µ
,

(25)

µ

の推定値は，過去の状態と同じ状態を取ろうとするため，ランダムに与えられる初期値に依存してどこか特定の圧縮符号の付近へと移動することができる（実線）．この模式図の圧
縮符号の分布は K = 3 パリティツリーを用いた場合に対応する．

んらかの方法で，特定の圧縮符号の情報だけを増やす必要があるのである．
Murayama は，ビリーフプロパゲーションに慣性項を導入して，LDGM 符号の高速な符号化アルゴリズ
ムの構成に成功した16) ．Murayama の方法は，理論が予測する性能をほぼ実現する符号化アルゴリズムとして注目を集めている．慣性項は，メッセージの更新式
を次のようにすることで導入される．すなわち，

ρtµl =

ρ̂tνl (sl ),ν∈M(l)\µ(26)eφµ (µ |J )

のような形で与えられるとき，高速に各変数 sl の期

待値 ml =
\sl sl p(| ) を反復計算によって近似的に求める方法である．しかし，EA オーダパラメー
タが 0 となる有歪圧縮法では，真の期待値が 0 であると考えられるので，単純にビリーフプロパゲーションとする．反復ステップ t のメッセージを利用して計算を適用しても期待値は 0 が得られるだけであろう．なは，した期待値 mt+1
l

t+1
(sl )
ρ̂t+1
µl (sl ) = q

µ \slµρtµj (sj ),j∈L(µ)\l

(27)

27

三村和史：ニューラルネットワーク理論と符号

eφµ (µ |J )µ(28)

めには，その符号化の処理過程などの解析が不可欠である．また，理論限界を達成するための必要条件など
興味深い問題がたくさん残されており，その発展が期となる．圧縮符号の l 番目のビットは，ξl = sgn(mt+1)
lと MPM 推定できる．ここで，L(µ) はクリーク µ に含まれる変数 sl の添え字 l の集合で，M(l) は変数

待されている．
謝 辞 執筆の機会を与えて下さいました山口大学の庄野逸先生をはじめ，本号を分筆されている諸先生方に感謝致します．

mt+1= q t+1 (sl )lµρtµj (sj ),j∈L(µ)\l

sl を含むクリーク µ の添え字 µ の集合である．また，q t+1 (sl ) がヒューリスティックに導入された慣性項であり，q t+1 (sl ) ≡ esl tanh

−1

γmtl

,

(29)

と定義されている．パラメータ 0 ≤ γ ≤ 1 は慣性項の大きさを表し，γ = 0 とすると慣性項のない場合に戻る．
この慣性項は，各反復ステップでの期待値を変化させないように働く．これによって，図 8 の模式図のよ
うに反復式の初期値に依存して，どれか特定の圧縮符
号に関する情報が増えることが期待できる．慣性項の大きさ γ の選び方については，現在のところ理論的指針はない．また，慣性項のないビリーフプロパゲー
ションと同様に反復計算が収束しないこともあることに注意されたい．
Hosaka らは，非単調パーセプトロンの有歪圧縮法の符号化アルゴリズムを慣性項を導入する方法を用いて構成し18) ，この場合も理論的な性能評価に近い符号化に成功しているほか，誤り指数を求めている19) ．
パリティツリーを用いた有歪圧縮法についても，慣性項を導入すると高速な符号化アルゴリズムが構成できることが予測される．パリティツリーの場合は中間素子数 K に応じて，復号したときに最も歪が小さくなる符号が 2K−1 個あることが保障されるので，中間素子数が大きくなるほど反復式がより少ない回数で収束したり，反復解の振動が起こる割合を減らすことができる可能性がある．

8. お わ り に
容量評価問題に関するニューラルネットワーク理論と有歪圧縮の関係について説明した．解析に用いられる統計力学的手法は，既に誤り訂正符号，有歪圧縮，暗号，画像修復といった広範囲な情報処理の課題に対して適用されている．確率モデルで記述できる課題に対して，統計力学的手法には性能評価だけにとどまらず，
情報処理で重要となる処理過程などに適用できる様々な有用な解析手法が用意されている．有歪圧縮の問題についても，よりよい符号化アルゴリズムの開発のた

参

考 文

献

1) Hopﬁeld, J. J. (1982): Proceeding of the National Academy of Sciences, 79, pp. 2554.
2) Gardner, E. (1988): Journal of Physics A:
Mathematical and General, 21, pp. 257.
3) Krauth, W., Mezard, M. (1989): Journal of
Physics France, 37, pp. R1.
4) Watkin, T.L.H., Rau, A., Biehl, M. (1993):
Reviews of Modern Physics, 65, pp. 499.
5) Sourlas, N. (1989): Nature, 339, pp. 693.
6) Nishimori, H., Wong, K. Y. M. (1999): Physical Review E, 60, pp. 132.
7) Kabashima, Y., Saad, D. (1999): Europhysics
Letters, 60, pp. 132.
8) Kabashima, Y., Murayama, T., Saad, D.
(2000): Physical Review Letters, 60, pp. 132.
9) Yoshiyuki, K., Saad, D. (2004): Journal of
Physics A: Mathematical and General, 37, pp.
R1.
10) 樺島祥介 (2004): 数理科学, 11 月号, pp. 48.
11) 樺島祥介 (2002): 物理の世界『学習と情報の平均場理論』, 岩波書店．
12) Murayama, T. (2002): Journal of Physics A:
Mathematical and General, 35, pp. L95.
13) Hosaka, T., Kabashima, Y., Nishimori, H.
(2002): Physical Review E, 66, pp. 066126.
14) Murayama, T., Okada, M. (2003): Journal of
Physics A: Mathematical and General, 36, pp.
11123.
15) Mimura, K., Okada, M. (2005): preprint (eprint arXiv cond-mat/0508598).
16) Murayama, T. (2004): Physical Review E, 69,
pp. 035105.
17) 保坂忠明 (2005): 博士論文，東京工業大学.
18) Hosaka, T., Kabashima Y. (2005): preprint(e-print arXiv cs.IT/0509086).
19) Hosaka, T., Kabashima, Y. (2005): Journalof the Physical Society of Japan, 74, pp. 488.