More is different

科研費特定領域研究「情報統計力学の深化と展開」平成

18

年度研究成果発表会

センサーネットワークでも「 More is different ^」

村山立人，デイビス・ピーター ¹

日本電信電話株式会社

NTT

コミュニケーション科学基礎研究所

1 ^はじめに

いま，データセンターがある系列

{X(t)} ^∞ t=1

に興味を持っているが，これを直接には計測できないもの とする．そこで，データセンターは

L

個のセンサーを周囲に配置したとしよう．各センサーはノイズのあ る環境で計測した系列

{Y i (t)} ^∞ t=1

をそれぞれ独立にデータ圧縮して通報する．つまり，各センサーは互い に通信することができず，したがって，事前にデータセンターに通報する内容についていっさい協調できな い．データセンターは，L個の通報を通信回線を利用して回収し，元の系列

{X(t)} ^∞ t=1

をできるだけ正確 に復元したいと考えている．しかし，通報作成時の合計圧縮率

R

は厳密に制限されている．これは，デー タセンターが一定の回線速度でしか通報を回収しないことを意味する．このような推定機構を伴った分散 符号化の数理モデルは

Berger-Zhang-Viswanathan

によって定式化され

[1]，情報理論の立場からセンサー

ネットワークの理論的枠組みを提供していると解釈されている．

彼らの仕事によって，大規模観測系におけるいくつかの興味深い性質が明らかにされた．もしセンサー 集団が情報共有できるなら，センサー数

L

が無限の極限において，独立に発生している計測ノイズを完全 に除去することが可能となる．したがって，D(·)を情報源

X

の歪み・レート関数 （レート・歪み関数の 逆関数）として，データセンターは任意の忠実度で「歪み」D(R)を達成することが保障されている．逆 に，それが不可能なら，有限の合計圧縮率

R

で歪み

D

を無限に小さくすることはできない．たとえ，無限 個のセンサーが利用可能であったとしても，その不可能性が証明できるのである

[1]．上記の結果は，系列 {X(t)} ^∞ t=1

が離散的である情報源の分析によるが，それを連続的なモデルに拡張したとしても，同様な結果 が得られることが知られている

[2]．しかし，システムへの実装を想定した符号化方式の開発は発展途上で

あり，特に有限の

R

ではその解析的な議論すら難しいのが現実である．

そこで著者らは，各センサーからの通報が独立に復号されることを制約条件としたシステムの構築を提 唱している

[3]．なぜなら，この立場によって，本来は融合している符号化と推定の機構が分離できて問題

が簡単になるためである．実際，符号化における最適性の議論は単一情報源モデルに帰着し，「沢山あるこ と」による多体効果は平均操作的な推定の機構に集約されてしまう．本稿では，対象とするシステムのモ デルを明確にした後，情報理論によるレート・歪み関数を基本的ツールとした非構成的な議論を展開する．

そして，センサーが「沢山あること」のメリットを評価するために，相対ビット誤り率という概念を導入す る．次に，不可逆圧縮の実践的方法として代表的なベクトル量子化の効果を厳密に分析し，その一般化とし て「パリティ量子化」を提唱する

[4]．注目すべきは，単純な量子化の機構を多体問題に一般化したことに

よってシステムの情報利得が劇的に改善される事実である．また，その漸近的挙動が統計力学のレプリカ法 によって評価できるのも興味深い

[5]．本稿の議論では，分析技術としての情報統計力学の信頼性を確認で

きるだけでなく，その独自の「視点」がシステム設計にもたらす利点も示されていると考えられる．

2 システムモデル

データ系列

{X(t)} ∈ X

に共通の確率分布を

P (x)

とする．また，

Y

を計測系列

{Y i (t)}

に共通のアルファ ベットとし，X × Y上で定義される確率行列を

W (y|x)

とする（i

= 1, · · · , L，t ≥ 1）．まず，無記憶情報

1

E-mail: {murayama,davis}@cslab.kecl.ntt.co.jp

源

{X(t)} ^∞ t=1

に対し，同時確率分布を次のように仮定する．

Pr[x, y 1 , · · · , y L ] = P (x) L i=1

W (y i |x) .

ここで，確率変数

Y i (t)

は

X(t)

に対して独立であり，条件つき確率

W [y i (t)|x(t)]

の値はすべての

i

と

t

に 関して同一である．さらに本稿では，この問題をもっとも単純な

2

値系列で議論していく．つまり，データ 系列

{X(t)}

と，それを一定のノイズレベルで計測した系列

{Y i (t)}

はすべて

2

値系列であると仮定される．

したがって，確率行列は次のようにパラメータ化できる．

W (y|x) =

⎧ ⎨

⎩

1 − p (y = x) p (y = x)

.

ここで，p

∈ [0, 1]

は計測におけるノイズのレベルを意味し，アルファベットは

X = Y

と選択されている．

さらに，簡単のため，P

(x) = 1/2

がいつも成立すると仮定しよう．これは，全く冗長性のないランダムな 情報源を計測していることに対応する．

x −→ w sensor

−→ y _i

図

1:

計測のモデル：各センサーは，情報源を独立に計測する．

符号化の段階では，センサー

i

が計測系列

{y i (t)} ^∞ t=1

から長さ

n

のブロック

y i = [y i (1), · · · , y i (n)] ^T

を 切り取り，Z上で定義された長さ

m

のブロック

z i = [z i (1), · · · , z i (m)] ^T

にブロックごと符号化する．以後，

ブール代数の表記にならい，

X = {0, 1}

，したがって

Y = Z = {0, 1}

とする．いま，ˆ

y i

をこのブロックの 復号系列で，圧縮系列の長さ

m(< n)

が既与だとする．本稿では，ハミング距離

d H (·, ·)

を歪み測度として 採用し，各エージェントは独立にレート・歪み関数を達成できると仮定する．

y _i −→ f encoder

−→ z i −→ g decoder

−→ ˆ y _i

図

2:

符号化と復号：各センサーの計測値は独立に符号化され，符号語は受信したデータセンターによって 復号される．

復号・推定の段階では，データセンターは

L

個の符号語の系列

z 1 , · · · , z L

を回収することになる．符号 語の長さはすべて

m

なので，合計の伝送率は

R = L × m/n

となる．そのため，この枠組みでは，データ センターは同一程度の歪みを持つ復号系列

y ˆ 1 , · · · , ˆ y L

を提供する交換可能なセンサーを配置していること になる．最後に，推定系列

x ˆ = [ˆ x(1), · · · , x(n)] ˆ ^T

の第

t

番目のビットは復号系列の対応する

L

個のビット の多数決によって計算される

[6]：

ˆ x(t) =

⎧ ⎨

⎩

0 (ˆ y 1 (t) + · · · + ˆ y L (t) ≤ L/2)

1 (ˆ y 1 (t) + · · · + ˆ y L (t) > L/2) . (1)

よって，システム全体の性能は多数決

(1)

によるビット誤り率の期待値

P e = Pr[x = ˆ x]

によって定義する のが自然である．本稿では，分散化のレベルをシステムが持つ自由度と解釈して，次の

2

つの「戦略」を 考える．

1.

無限個のセンサーで系列を無限に圧縮する：L

→ ∞

2. R

個のセンサーで系列を圧縮しない：L

= R

前者の戦略では各センサーに配分される伝送率はゼロに収束し，後者の戦略では符号化を行わないで通信 をすることになる．しかし，一般には，どちらの戦略がある特定の系列の推定に適しているのかを決定する のは難しい．つまり，どちらの戦略がより小さいビット誤り率の期待値

P e

を与えるのかが自明ではないの である．実際，レート・歪み符号を用いることによって，データセンターはより多くの数のセンサーを利 用することが可能になる．しかし，同時に各センサーが提供する復号系列の歪みはより大きくなるだろう．

最適な分散化レベルの選択は，計測におけるノイズレベル

p

と通信における合計伝送率

R

に依存して決定 されるはずである．

{ˆ y _i } ^L i=1 −→ r estimator

−→ x ˆ

図

3:

推定：計測された系列は，多数の復号系列を利用して推定される．

3 ^{レート・歪み関数}

本章では，情報理論による非構成的なシステムの評価を行う．この議論では，計算的複雑さが高い最良符 号が利用できることを前提にしているので，計算科学的な視点が欠如していることに注意して欲しい．ま ず最初に，レート・歪み理論の基本定理を説明する

[7]．この定理は情報源符号化定理（Shannon

の第一定 理），通信路符号化定理（Shannonの第二定理）に次ぐ第三の

Shannon

の定理であり，それは不可逆圧縮に おける限界記述長を与える．いま，ビット誤り率

D

を許してデータを圧縮するとしよう．このとき，デー タの圧縮率が

r(D)

より大きい限り，ビット誤り率が

D

より大きくならない符号化の方法が存在するとし よう．この限界の圧縮率

r(D)

を歪み

D

の関数とみなし，レート・歪み関数と呼ぶ．特に，単純な情報源 のクラスでは，簡単に

r(D)

が構成できる．仮に，nビットのデータ

y i = [y i (1), · · · , y i (n)] ^T

が

m

ビット の符号語

z i = [z i (1), · · · , z i (m)] ^T

に圧縮され，それが復号されて系列

y ˆ i = [ˆ y i (1), · · · , y ˆ i (n)] ^T

を得たとし よう．簡単のため，元のデータ系列が全くのランダム系列であり，冗長性を利用した圧縮が不可能な場合を 考えることにする（一般化は容易である）．すると，圧縮率を

r = m/n

で定義して，復元におけるビット 誤り率をハミング距離で測ることにすると，上述のレート・歪み関数は

r(D) =

⎧ ⎨

⎩

1 − h(D) (0 ≤ D ≤ 1/2)

0 (otherwise) , (2)

と求まる．ただし，h(·)は

2

値エントロピー関数であり，次のように定義した．

h(D) = −D log ₂ D − (1 − D) log ₂ (1 − D) .

今後，センサー数が限りなく大きくなる極限を想定し，レート・歪み関数

r(D)

の

(D, r) = (1/2, 0)

近傍に ついて議論していこう．すると，関数

(2)

の連続性により，D

∈ [0, 1/2)

においてテイラー展開できて

r(D) = 1 − h(D)

= 2 ln 2

1 2 − D

2

+ O 1

2 − D 2

となる．ただし，ランダウの記号

O(·)

はその引数より高次の無限小を意味する

[8]．ここで，関係式 R/L = m/n

を考慮すれば，センサー数

L

と歪み

D

の間には漸近的に

R L ≈ 2

ln 2 1

2 − D 2

. (3)

が成立する．一方，各センサーが独立に計測系列の符号化を行うと仮定すると，歪みに由来するビット誤り

は

Bernoulli

試行でモデル化できる

[9]．そのため，復号系列 y ˆ i

のビット誤り率は次のように求まる．

e = Pr[x(t) = ˆ y i (t)] = p(1 − D) + (1 − p)D .

よって，推定系列

x ˆ

のビット誤り率の期待値は累積二項分布

[10]

P BER (e, L) = Pr[x(t) = ˆ x(t)]

=

⎧ ⎨

⎩

B( ^L− ₂ ¹ : e, L) (L is odd) B( ^L ₂ − 1 : e, L) + ¹ ₂ b( ^L ₂ : e, L) (L is even)

で記述できる．ただし，簡単のため

B(L : e, L) =

L

l=0

b(l : e, L) , b(l : L, q) = L

l

(1 − e) ^l e ^L−l

と略記した．ここで，整数

l

は

ˆ y(t)

における反転していない要素の合計を表し，特に項

(1/2)b(L/2 : e, L)

は（ちょうど）l

= L/2

となったときのランダムな推量を意味する．もちろん，記号

_L

l

は

L

個から

l

個を 選ぶ組み合わせの総数である．では，センサーの数

L

が十分に大きいとしよう．すると，累積二項分布は

P BER (e, L) ≈ B L

2 : e, L

=

L/2

l=0

L l

(1 − e) ^l e ^L−l ,

と近似できる．さらに，統計学における基本的定理によると，二項分布と正規分布には

P e (p, R) = lim

L→∞ P BER (e, L)

= L/2

0

du N(L(1 − e), Le(1 − e))

(4)

という関係式が成立する．ただし，N(X, Y

)

は平均

X

で分散

Y

の正規分布を表している

[10]．積分 (4)

を 標準正規分布の形式にするには，測度を

r = (u − L(1 − e))/

Le(1 − e), so dr = du/

Le(1 − e)

と置き 換えればよいことが知られている．その結果，ビット誤り率は

P e (p, R) = lim

L →∞

_−r

_c

− √ L

dr N(0, 1)

と求まる．ただし

r c

は次式を満たす．

r c = L( ¹ ₂ − e)

Le(1 − e) ≈ 2 √

L(1 − 2p) 1

2 − D

. (5)

この関係式は与えられた

L，p，D

の値に対しては常に成立し，符号化の個性は

D

の値に集約される．結 局，分散化利得の理論限界は

(3)

と（5）を連立して

P e (p, R) =

(1 − 2p) √ 2 ln 2R

−∞ dr N(0, 1) (6)

と求まる．ここに，大システム化戦略

L → ∞

におけるビット誤り率が厳密に求まった．次章では，この戦 略の優位性を，符号化の自由度がないシステムと比較することによって検証する．

0 0.1 0.2 0.3 0.4 0.5

−2

−1 0 1 2

p P

(dB) e

( p, R )

(a) Narrow Band

0 0.1 0.2 0.3 0.4 0.5

−150

−100

−50 0 50 100 150

p P

(dB) e

( p, R )

(b) Broadband

R = 1

R = 2 R = 10

R = 100 R = 500 R = 1000

図

4:

レート・歪み関数による分散符号化と独立復号過程による推定操作の性能評価．デシベル

(dB)

単位で 測った参照レベル

P e ⁽⁰⁾ (p, R)

に対する

P e (p, R)

の相対的大きを測った．(a)合計伝送率

R

の小さいナロー バンド回線．R

= 1, 2, 10. (b)

合計伝送率

R

の大きいブロードバンド回線．R

= 100, 500, 1000.

4 ^{相対ビット誤り率}

本章では，有限の合計伝送率

R

が与えられたとき，推定系列の相対的品質がノイズの大きさ

p

にどのよ うに依存するのかを議論しよう．Fig. 4には，デシベル

(dB)

単位で測られた

P e (p, R)

の典型的な挙動を示 している．ただし，ここでは

R

を整数に制限し，参照レベルは次のように設定した．

P _e ⁽⁰⁾ (p, R) =

⎧ ⎨

⎩

_(R− 1)/2 l=0

_R

l

(1 − p) ^l p ^{R − l} (R is odd) R/2 − 1

l=0

_R

l

(1 − p) ^l p ^R−l + ¹ _{2 R}

R/2

(1 − p) ^R/2 p ^R/2 (R is even) (7)

参照レベル

(7)

はセンサー数

L

を合計伝送率

R

に一致させたときの

P e

であり，これはセンサーが系列を全 く圧縮しないシナリオに相当している．このとき，デシベル単位でのビット誤り率の期待値は

P _e ^(dB) (p, R) = 10 log P e (p, R)

P e ⁽⁰⁾ (p, R) , (8)

と定義する．ただし，対数

log

の底は

10

にとった．この単位でビット誤り率を測ることにすると，P

e (p, R)

が参照レベル

P e ⁽⁰⁾ (p, R)

と同じになるときゼロになる．定義

(8)

より，デシベルで測った量は負の値をとる 可能性がある．そのようなときは，測定している分散化レベルでのビット誤り率の期待値が，参照レベルの ものより小さくなっていることを意味している．数値解析によると，合計伝送率

R

が小さいとき（ナロー バンド）は，整数

R

の偶奇性に強く依存したビット誤り率の挙動が観測できる

[Fig. 4 (a)]．ここで，本来

なら実数でも定義されている合計圧縮率を整数に限定しているのは，比較している参照レベルを自然に導 入したいからである．特に，R

= 2

のケースでは，最も小さな閾値の値を持ち，p

c = 0.082

となっている．

この閾値

p c

は，ここを超えると分散化の極限

L → ∞

が参照レベル

L = R

より大きな情報利得をもたらす ことを意味する．しかし，R

= 1

のケースは特別で，このような閾値

p c

が存在していないのは興味深い．

これとは対照的に，合計伝送率

R

が大きいとき（ブロードバンド）は，デシベル単位で測ったビット誤り 率の期待値の差

P e ^(dB) (p, R)

が，定性的には良く似た挙動を示す

[Fig. 4 (b)]．この図を見ていると，R

が

大きくなるにしたがって前述の閾値

p c

が

0.146

という値に漸近している様子がうかがえるが，この値の理 論的導出には成功していない．

本章の結果より，次のことが主張できる．つまり，レート・歪み符号による不可逆圧縮の自由度を各セン サー

a

に与えるとき，それを利用した計測精度の向上が見込めるノイズ領域が存在する．それは，特徴的 な閾値

p c

を超えた高ノイズ領域であり，この区間

[p c , 1/2]

 では「数」の効果が「質」の効果を凌駕して いると解釈できる．逆に，低ノイズ領域

[0, p c ]

では，「質」の効果が「数」の効果を凌駕しているので符号 化による分散化の利得は得にくい．この結果は，計測と通信をうまく制御させることで，システム全体とし て相乗効果が享受できる事実を理論的に示している．

5 ^{ベクトル量子化}

より実践的で複雑なモデルを分析する前に，現存する不可逆圧縮の機構を抽象化した量子化を議論する のが見通しがよい．最も単純な量子化のモデルでは，ある特定の

y µ (a)

を復号するために，1ビットの通報

z l (a)

のみを利用すると仮定する．この符号化の機構は，複数のビットを「ベクトル」として単一のビット に置き換えるとも解釈できるため，ベクトル量子化と呼ばれることがある．

ˆ

y µ (a) = z l(µ) (a) . (9)

ここで，ベクトル量子化の過程

(9)

における入力を指定するために，ポインター

l(µ)

を導入している．注 意すべきは，M ビットの系列がわずか

N ( M )

ビットで表現されているので，写像：µ

→ l = l(µ)

が

1

対

1

ではない上への写像（全射）になることである．便宜上，センサー

a

の計測した情報ビット

y µ (a)

に 対応する通報ビット

z l (a)

を指定するために，集合

M(l) = {µ | µ s.t. l(µ) = l}

を定義しよう．例えば，情 報ビットの

y 1 (1)

と

y 3 (1)

が両方とも通報ビット

z 2 (1)

から計算されるとき，それぞれ

l(1) = 2

と

l(3) = 2

と表記できるので，まとめると

M(2) = {1, 3}

と略記できることになる．

ベクトル量子化の定義から，写像

l(µ)

は上への写像でなければならない．集合論の用語では，写像

l(µ)

が上への写像であるとは，その値

l = l(µ)

で値域

L = {l | l = 1, · · · , N}

に含まれるすべての要素が指定 できることを意味する．つまり，すべての

l ∈ L

について，それに対応した少なくとも

1

つの

µ

が定義域

M = {µ|µ = 1, · · · , M }

に存在して，l

= l(µ)

が満足されることになる

[11].

もし写像

l(µ)

が上への写像 ではないと仮定すると，通報が満たすべき符号化率

R/L

は

m/n

以下となるはずであり，これは明らかに システムが満たすべき要請と矛盾する．ベクトル量子化による

2

値データの不可逆圧縮では，集合

M(l)

に 含まれる指標

µ

を持つすべての情報ビット

y µ (a)

の値は，唯一の通報ビット

z l(µ) (a)

の状態，もちろん

+1

か

−1

のいづれか，によって一意に指定されてしまう．今後，任意の

l

に対応する

µ

の総数は一定であると 仮定する．このように情報ビット

y µ (a)

の集合を等分割することによって，それを復号したビット

y ˆ µ (a)

が 同一の誤り率を持つことが期待できる．結果として，平均的なビット誤り率は次のように求まる．

P e (p, R) =

₋ (1 − 2p) √ R

−∞ dr N(0, 1) . (10)

では，本稿で導入した相対ビット誤り率の表示

(8)

で，式

(10)

の

p

と

R

に対する応答を数値的に評価してみ よう．ただし，デシベルの参照レベルはやはり

P _e ^dB (p, R, R)

とした．すると，平均ビット誤り率

P _e ^dB (p, R)

の典型的挙動は図

5

のように得られる．ナローバンド回線では，レート・歪み関数と似た性能曲線が得ら れるようである．しかし，ブロードバンド回線では，状況はかなり一変してしまう．最適戦略の転移点

p c

の値は，回線容量

R

が大きくなるにしたがって増加している．

6 パリティ量子化

前章で最も単純なベクトル量子化の分析が終わったので，この章ではやや複雑な量子化の機構を提案した い．第一の段階として，ベクトル量子化を自然に拡張した「パリティ量子化」を考えるのが自然である

[4]．

0 0.1 0.2 0.3 0.4 0.5

−0.5

−0.25 0 0.25 0.5

p P

(dB) e

( p, R )

(a) Narrow Band

0.44 0.45 0.46 0.47 0.48 0.49 0.5

−5

−2.5 0 2.5 5

p P

(dB) e

( p, R )

(b) Broadband

R = 1 R = 10

R = 2

R = 500

R = 100 R = 1000

図

5:

ベクトル量子化の相対ビット誤り率

P e ^(dB) (p, R)．デシベル (dB)

単位で測った参照レベル

P e ⁽⁰⁾ (p, R)

に対する

P e (p, R)

の相対的大きを測った．(a)合計伝送率

R

の小さいナローバンド回線．R

= 1, 2, 10．(b)

合計伝送率

R

の大きいブロードバンド回線．R

= 100, 500, 1000．

このモデルでは，1ビットだけの入力が許される写像（9）の制約条件を緩和し，2ビットの入力をも考え るようにする．すると，量子化の過程は多体系に拡張されて

ˆ

y µ (a) = z k(µ) (a) · z l(µ) (a) (11)

と記述される．ここで，2つの指標

k = k(µ), l = l(µ) (k < l)

は情報ビット

y µ (a)

を復元するために利用 する通報ビットの組を指定するポインターである．このとき，写像（11）で記述される量子化の機構を，仮 にパリティ量子化と呼ぶことにしよう．式の上からも明らかなように，パリティ量子化（11）はベクトル量 子化（9）にビット間の相関を導入したことがその特徴である．さらに，情報ビット

y µ (a)

の誤り率が指標

µ

に依存しないと要請する．これは，ある

z l (a)

と式（11）によって関係づけられる

ˆ y µ (a)

の個数が，その 指標

l

に依存しない定数ならば実現できる．今後，この特徴的な定数を

C

と書くことにする．すると，こ の量子化を実行したとき圧縮率は

2/C

となることがわかる．これは，Cビット分の情報が

2

ビット分の通 報から復号されることを意味する．

パリティ量子化（11）によって最適な符号化を実現するためには，ビット間の相関を織り込んで

z l (a)

を 選択しなければならない．このような複雑な量子化の分析は過去にも例がなく，通常の数学的方法では大き な困難が予想される．しかし，統計力学におけるレプリカ法の枠組みを援用することによって，パリティ量 子化の性能限界を直接的に計算することが可能である

[5]．

（レプリカ法の詳細については

[12, 13]

などが詳 しい．）計算は省略するが，この場合の平均ビット誤り率は

P e (p, R) =

₋ (1 − 2p)c

g

√ R

−∞ dr N(0, 1) (12)

と求まる．ただし，簡単のため

c g = 1

√ 2 √

α

2 + 2 ln 2

√ α − √

α 2 − σ ²

√ α

tanh ² x π(x)

.

と略記した．ここで，2つのパラメータ

α，σ

は次の自己コンシステントな方程式（鞍点方程式）によって

0 0.1 0.2 0.3 0.4 0.5

−2

−1 0 1 2

p P

(dB) e

( p, R )

(a) Narrow Band

0 0.1 0.2 0.3 0.4 0.5

−150

−100

−50 0 50 100 150

p P

(dB) e

( p, R )

(b) Broadband

R = 1

R = 2 R = 10

R = 100 R = 500 R = 1000

図

6:

パリティ量子化の相対ビット誤り率

P e ^(dB) (p, R)．デシベル (dB)

単位で測った参照レベル

P e ⁽⁰⁾ (p, R)

に対する

P e (p, R)

の相対的大きを測った．(a)合計伝送率

R

の小さいナローバンド回線．R

= 1, 2, 10．(b)

合計伝送率

R

の大きいブロードバンド回線．R

= 100, 500, 1000．

一意に決定できる．

σ ² = α ˆ x ² π(ˆ ˆ x) ,

− 1 2 + 2

α ln 2 + 1

2 − σ ²

α tanh ² x (1 + 2x csch x sech x)

π(x) = 0 .

ただし，積分の測度は次のように定義する．

· π(x) = _∞

−∞

√ dx

2πσ ² exp

− x ² 2σ ²

( · ) , · π(ˆ ˆ x) =

+1

−1

dˆ x

√ 2πσ ² (1 − ˆ x ² ) ^{− 1} exp

− (tanh ^{− 1} x) ˆ ² 2σ ²

( · ) .

したがって，与えられた

p

と

R

に対して式（12）の応答を数値的に評価するのは難しくない．図

6

では，

有限の

R

に対する相対ビット誤り率

P e ^(dB) (p, R)

の典型的な挙動が示されている．前述のとおり，デシベ ルの参照レベルは

P e (p, R, R)

としている．ナローバンド回線では，図

6(a)

のように最適戦略の転移点は

p c = 0.0921

が最小値となっている．一方，ブロードバンド回線では，最適戦略の転移点は

R

の増加によっ

て

0.165

に収束しているように見える．注目すべきは，どちらの回線幅でもパリティ量子化の性能はベクト

ル量子化のそれをはるかに凌駕し，レート・歪み関数による限界を事実上達成していることである．これ は，ビット間相関による多体効果を量子化の機構に取り入れることで，性能の劇的な改善がもたらされるこ とを示唆している．

7 ^おわりに

本稿では，センサーネットワークにおける

2

種類の「more」（沢山あること）を理論的に扱った．まず，

圧倒的なセンサーの「数」がもたらす情報利得の構造を精密に分析した．その結果，現実的な制約のもとで は，必ずしも「沢山あること」が利得に直結しない事実を発見した．次に，ベクトル量子化とそれを一般化

したパリティ量子化の効果を比較し，システムに多体効果を取り入れることの利得を発見した．この比較 は，情報統計力学の分析技術なしには実現が不可能であり，特にレプリカ法の有用性が示されるいい例だっ たと考えられる．標語的に要約すれば，上記の

2

種類の「more」は確かに「different」な結末を与えたと解 釈できるだろう．

謝辞

本稿を作成するにあたり，議論に加わっていただいた村松純氏に感謝します．

参考文献

[1] T. Berger, Z. Zhang, and H. Viswanathan, “The CEO problem,” IEEE Trans. Inform. Theory, vol. 42, pp. 887–902, May 1996.

[2] Y. Oohama, “The rate-distortion function for the quadratic Gaussian CEO problem,” IEEE Trans.

Inform. Theory, vol. 44, pp. 1057–1070, May 1998.

[3] T. Murayama, “On the asymptotic performance of sparse matrix codes in the CEO problem,” in Proc. 2005 IEEE International Symposium on Information Theory (ISIT’05), Adelaide, Australia, 2005.

[4] T. Murayama and M. Okada, “Rate distortion function in the spin glass state: a toy model,” in Advances in Neural Information Processing Systems 15 (NIPS’02), Vancouver, Canada, Dec. 2002, pp. 423–430.

[5] T. Murayama and P. Davis, “Rate distortion codes in sensor networks: A system-level analysis,”

in Advances in Neural Information Processing Systems 18 (NIPS’05), Vancouver, Canada, Dec. (in press).

[6] D. J. C. MacKay, Information Theory, Inference and Learning Algorithms. Cambridge, UK: Cam- bridge University Press, 2003.

[7] T. M. Cover and J. A. Thomas, Elements of Information Theory. Wiley, 1991.

[8] S. Lang, A First Course in Calculus. Springer-Verlag, 1986.

[9] K. L. Chung, A Course in Probability Theory. Academic Press, 2000.

[10] W. Hays, Statistics (5th Edition). Belmont, CA: Wadsworth Publishing, 1994.

[11] K. Kunen, Set Theory: An Introduction to Independence Proofs. North-Holland, 1984.

[12] M. Mezard, G. Parisi, and M. Virasoro, Spin-Glass Theory and Beyound. World Scientific, 1987.

[13] V. Dotsenko, Introduction to the Replica Theory of Disordered Statistical Systems. Cambridge, UK:

Cambridge University Press, 2001.