確率伝搬法と量子系の平均場理論田中和之

(1)

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

18

年度研究成果発表会

確率伝搬法と量子系の平均場理論

田中和之

¹

東北大学大学院情報科学研究科応用情報科学専攻宮城県仙台市青葉区荒巻字青葉

6-3-09

1 ^はじめに

確率モデルを用いた情報処理は画像処理, 誤り訂正符号,移動体通信から確率推論まで様々に拡がりつつあり, 確率的情報処理として定着しつつある

[1, 2, 3, 4, 5].

近年,この確率的情報処理に統計力学がアルゴリズム化とその性能の解析を中心に大きな役割を果たし,情報統計力学として急速な深化を始めつつある

[6, 7, 8].

情報統計力学における展開のブランチの一つとして確率伝搬法を用いた近似アルゴリズムがあげられる.

確率伝搬法は人工知能における確率推論アルゴリズムのひとつとして提案されたものである

[9].

その後,誤り訂正符号における高性能の復号方式である

Turbo

符号,低密度パリティ検査符号等とのアルゴリズムとしての構造の等価性から注目を浴びることとなる

[10].

そして統計力学における平均場理論との数理構造の類似性が指摘されるにいたり,情報工学,統計力学,統計科学,数理工学等の各分野の研究者を巻き込んで新たなる確率的情報処理の近似アルゴリズムの提案に向けて動き出しつつある

[11, 12, 13].

平均場理論のひとつとして材料物性科学において長い歴史をもつもののひとつにクラスター変分法がある

[14, 15, 16].

確率伝搬法がこのクラスター変分法を用いることで一般化された確率伝搬法へと拡張されることが指摘されたことは特に大きな発展ということができる

[12, 13, 17].

情報統計力学の次なる目標の一つは量子力学的概念を確率的情報処理に本質的意味において導入することである

[20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30].

確率的情報処理への統計力学的アプローチの本質はたくさんの構成要素が関連しながら集まることで生み出される数理構造の本質を理解し,如何にうまく取り扱うかにある. 量子力学的概念を確率的情報処理に持ち込む以上,量子力学的状態を伴うたくさんの基本構成要素の間に相互作用を伴う物理モデル,すなわち量子力学的に拡張された相関を伴う確率モデルに対する計算アルゴリズムの提案が避けては通れない課題のひとつとなる. そこで,まず考えたい研究テーマのひとつに,確率的情報処理において大きな成功をおさめた確率伝搬法がはたして量子力学的に拡張された確率的情報処理にどの程度の範囲で転用できるのかがある.

既に述べたとおり確率伝搬法は平均場理論, 特にクラスター変分法と数理的構造において深い関係があ

る

[12, 13, 17].

統計力学において

20

世紀半ばからこの平均場理論とクラスター変分法は多くの量子力学的

概念に基づいて構成された物理モデルに対して用いられている

[18].

確率的情報処理に量子力学的概念を持ち込むことにより構成された物理モデルに対して,平均場理論やクラスター変分法を応用することは, これまでの情報統計力学の成功を考えるとごく自然なことである. その出発点として,まず従来の確率伝搬法をそのまま適用することの困難さがどこにあるのか? 量子力学を持ち込むことにより,従来の確率伝搬法で行われていた操作のどの部分が安易に行ってはならない操作になるのか? そして量子力学的に拡張された確率モデルに対する平均場理論,クラスター変分法からどのような確率伝搬法のアルゴリズムが定式化されるのか? を確認しておく必要がある.

本稿では統計力学における量子力学的に拡張された確率モデル,すなわち量子系のクラスター変分法の量子系に対する定式化を与え, 従来の確率伝搬法の定式化との比較を与える. 第

2

節では

1

次元鎖としてつながったグラフ上の簡単な量子系の定義を与え, 2次元格子上の確率モデルに写像されることを示すことで, 一見, 確率モデルの量子力学的拡張が従来の確率伝搬法を単純に適用できるわけではないことを説明する.

第

3

節では量子系に対するクラスター変分法について説明する. 第

4

節では量子系に対するクラスター変分法が量子力学的拡張が行われていない確率モデル

(統計力学でいうところの古典系)

に対してどのような形で従来の確率伝搬法に帰着されるかについて,その導出の詳細を与える. 第

5

節はまとめである.

2 1 ^{次元量子系と} Suzuki-Trotter ^公式

本節では

1

次元鎖上に配置された少数の頂点からなるグラフ上の量子系の統計量が単純に転送行列法すなわち従来の確率伝搬法を用いて厳密に計算することが困難であるかについて説明する.

1

e-mail address: [email protected], webpage URL: http://www.smapip.is.tohoku.ac.jp/˜kazu/

(2)

確率変数

x 1 , x 2 , x 3 , x 4

を考え,それぞれが

0, 1

の

2

x

1

=0,1

W 12 ( x 1 , x 2 ) (3)

と導入すると, たとえば周辺確率分布

(Marginal Probability Distribution) P (x ₂ ), P (x ₁ , x ₂ ), P (x ₁ , x ₂ )

などは次のように表される.

P(x 2 ) =

x

1

=0,1

x

3

=0,1

P(x 1 , x 2 , x 3 ) = M 3→2 (x 2 )M 3→2 (x 2 )

x

1

=0,1

x

2

=0,1

M 3→2 (x 2 )M 3→2 (x 2 ) (4)

P (x ₁ , x ₂ ) =

x

3

=0,1

P (x ₁ , x ₂ , x ₃ ) = W ₁₂ (x ₁ , x ₂ )M _3→2 (x ₂ )

x

1

=0,1

x

2

=0,1

W ₁₂ (x ₁ , x ₂ )M _3→2 (x ₂ ) (5)

この計算を更に多くの頂点からなる木構造をもつグラフ表現により与えられる結合確率分布に適用してゆくものが確率伝搬法であり,更にループを伴うグラフ構造により与えられる結合確率分布にも近似アルゴリズムとして拡張されている. その基礎は式

(2)

のような等式が成り立つことにある.

次に式

(1)

の結合確率分布を量子系に拡張することを考えてみよう. たとえば

x i = 0 (i = 1, 2, 3)

を

x i = 0| ≡

1 0

, x i = 1 (i = 1, 2, 3)

を

x i = 1| ≡ 0

1

というベクトル表現に形式的に置き換える. 同時に

(x ₁ , x ₂ ), (x ₂ , x ₃ ), (x ₁ , x ₂ , x ₃ )

という状態は

|x ₁ ⊗|x ₂ , |x ₂ ⊗|x ₃ , |x ₁ ⊗|x ₂ ⊗|x ₃

という表現へとそれぞれ書き換えられる.

これらのベクトル表現とその直積操作を用いると次の

2 ³ ×2 ³

の行列

P

が定義される.

P =

x

1

=0,1

x

2

=0,1

x

3

=0,1

w ₁₂ (x ₁ , x ₂ )w ₂₃ (x ₂ , x ₃ )(|x ₁ ⊗|x ₂ ⊗|x ₃ )(x ₁ |⊗x ₂ |⊗x ₃ |)

tr

x

1

=0,1

x

2

=0,1

x

3

=0,1

w 12 (x 1 , x 2 )w 23 (x 2 , x 3 )(|x 1 ⊗|x 2 ⊗|x 3 )(x 1 |⊗x 2 |⊗x 3 |) (6)

この行列

P

は非対角成分がすべて

0

であり,対角成分と

P (x 1 , x 2 , x 3 )

が次の関係式で対応している.

P ( x 1 , x 2 , x 3 ) =

x 1 |⊗x 2 |⊗x 3 | P

|x 1 ⊗|x 2 ⊗|x 3

(7)

更に行列

A

に対する指数関数を

exp(A) ≡ ^+∞

n=1

1 n! A ⁿ (8)

と定義して導入すると式

(6)

の行列表現は次のように書き換えられる.

P = exp

− E tr exp

|z ₁ ⊗|z ₂ ⊗|z ₃

z ₁ |⊗z ₂ |⊗z ₃ | (11)

=0,1

− ln w 23 ( z 2 , z 3 )

列の行列

H

を考える.

H ≡ H 12 + H 23 (13)

=0,1

z

3

=0,1

z

₁

=0,1

z

₂

=0,1

z

₃

=0,1

u ₂₃ (z ₂ , z ₃ , z ₂ , z ₃ )δ _z

₁

_,z

₁

|z ₁ ⊗|z ₂ ⊗|z ₃

z ₁ |⊗z ₂ |⊗z ₃ | (15)

この行列

H

から

2 ³

行

2 ³

列の行列

Q

を次のように定義する.

Q = exp(−H)

tr exp(−H) (16)

式

(13)-(16)

で定義される行列

Q

は量子統計力学では密度行列

(Dencity Matrix)

と呼ばれる. 一般に

密度行列により表される量子力学に基づく体系を総称して量子系と本稿では呼ぶことにする.

密度行列

Q

は非対角項が非零の値を持つことがあるため

tr exp

− H ₁₂ − H ₂₃

= tr exp

− H ₁₂ exp

− H ₂₃

(17)

のような等式はもはや一般には成り立たなくなる. 指数関数の定義を用いると

exp

− H ₁₂ − H ₂₃

= exp

− H ₁₂ exp

− H ₂₃ +

H ₂₃ H ₁₂ − H ₁₂ H ₂₃

+ · · · (18)

という形に

O(1)

の補正項が残ってしまう. そこで通常は

Suzuki-Trotter

公式

(Suzuki-Trotter Formula)

と呼ばれる次の公式が用いられる

[19, 31].

exp − 1

n H ₁₂ − 1

n H ₂₃ _n

= exp − 1

n H ₁₂ exp

− 1

n H ₂₃ _n

+ O(n ⁻¹ ) (n→ + ∞) (19)

この公式を用いると, 例えば式

(16)

の分母

tr exp(−H)

は次のように書き換えられる.

tr exp(−H) = lim

n→+∞ tr exp − 1

n H ₁₂ exp

− 1

n H ₂₃ _n

= lim

n→+∞

{a

i,j

|i=1,2, j=1,2,···,n}

a 1,1 | exp( − 1

n H 12 ) |a 2,1 a 2,1 | exp( − 1

n H 23 ) |a 1,2

× a _1,2 |exp(− 1

n H ₁₂ )|a _2,2 a _2,2 |exp(− 1

n H ₂₃ )|a _1,3

×· · ·

× a _1,n |exp(− 1

n H ₂₃ )|a _2,n a _2,n |exp(− 1

n H ₂₃ )|a _1,1 (20)

式

(20)

は実は次の量に対応づけられる.

tr exp( −H ) = lim

n→+∞

{x

i,j

|i=1,2, j=1,2,···,n}

n j=1 y=0,1

v 12 ( x 1,j , x 2,j , x 1,j+1 , y ) v 23 ( y, x 3,j , x 2,j+1 , x 3,j+1 )

(21)

(4)

v 12 ( ξ 1 , ξ 2 , η 1 , η 2 ) ≡

ξ 1 |⊗ξ 2 | exp( − 1

n H 12 )

|η 1 ⊗|η 2

(22) v ₂₃ (ξ ₂ , ξ ₃ , η ₂ , η ₃ ) ≡

ξ ₂ |⊗ξ ₃ | exp(− 1

n H ₃₄ )

|η ₂ ⊗|η ₃

(23)

この場合

2 ³

行

2 ³

列の行列

exp(− _n ¹ H ₂₃ )

I⊗exp(− _n ¹ H ₂₃ )

を対角化することになる. しかし,これが計算できるのであればそもそも行列

exp(−H ₂₃ − H ₂₃ )

の対角化ができることになり,計算量的には何ら代わらないことになる.

一方,式

(21)

における量子系と古典系の対応関係をみると,式

(16)

の量子系の統計量の計算は,等式

(16)

から確率変数

x = {x _1,1 , x _2,1 , x _3,1 , x _1,2 , x _2,2 , x _3,2 , · · ·, x _1,n , x _2,n , x _3,n }

に対する結合確率分布

Q(x) =

n j=1 y=0,1

v 12 (x 1,j , x 2,j , x 1,j+1 , y)v 23 (y, x 3,j , x 2,j+1 , x 3,j+1 )

{x

i,j

|i=1,2, j=1,2,···,n}

n j=1 y=0,1

v 12 (x 1,j , x 2,j , x 1,j+1 , y)v 23 (y, x 3,j , x 2,j+1 , x 3,j+1 ) (24)

の分母が

tr exp( −H )

に関係づけられることがわかる. しかしながら, 式

(24)

で与えられる確率モデルに

対して一般化された確率伝搬法のアルゴリズムを書き下してみるとメッセージが

3

変数の関数になり,メッセージ更新規則の

1

回の計算量は

2 ³

通りの状態の和を含むこととなる. つまり計算量的にはもともとの量子系を計算するのと手間が変わらないことになる.

本節では

3

個の確率変数

x ₁ , x ₂ , x ₃

からなる結合確率分布

P (x ₁ , x ₂ , x ₃ )

から出発し,それを量子系の密度行列

Q

に拡張した場合を例にあげ,何故,古典系に対する確率伝搬法

(すなわち統計力学で言うところ

の転送行列法)をそのまま量子系に適用することが困難である理由を説明した. この状況は木構造をもつグラフ表現上で与えられた量子系一般に言えることなのである.

3 量子系のクラスター変分法

N

個の頂点

1 , 2 , · · ·, N

を考え,そのうちいくつかの頂点間が線分により結ばれているグラフを考える.

線分により結ばれた頂点対を隣接頂点対と呼ぶことにする. 頂点

i

と頂点

j

が線分により結ばれるとき,その隣接頂点対を

ij

という記号により表すことにする. すべての頂点からなる集合を

Ω = {1, 2, · · ·, N},

すべての隣接頂点対からなる集合を

B

によりそれぞれ表す. 各頂点

i

には

|0 ≡

1 0

と

|1 ≡ 0

1

という

2

つのベクトル表現により与えられた状態のいずれかをとるものとする. この状態をもとに

2 ^N

行

2 ^N

列の行列

H

を以下のように導入する.

H ≡

ij∈B

H ij (25)

H _ij ≡

z

k=1

δ _i,k + δ _j,k + (1 − δ _i,k − δ _j,k )δ _z

_k

_,z

_k

×

|z 1 ⊗|z 2 ⊗· · ·⊗|z N

z ₁ |⊗z ₂ |⊗· · ·⊗z _N |

(26)

行列

H

から

2 ^N

行

2 ^N

列の試行行列

R

に対する量

F [R] = trR

H + lnR

(27)

を導入すると

arg max R

F[R] trR = 1

= Q (28)

Q ≡ exp( −H )

tr exp(−H) (29)

(5)

という等式が得られる. 量子統計力学において

H

はハミルトニアン,

Q

は密度行列,

F [ Q ] = − ln

tr exp( −H )

は自由エネルギーに対応するものである.

密度行列

Q

に対する縮約密度行列

(Reduced Density Matrix) Q _i ≡ tr _\i Q , Q _ij ≡ tr _\ij Q

を以下のように導入する.

x i |Q _i |y i = x i |tr _\i Q|y i

≡

z

1

=0,1

z

2

=0,1

· · ·

z

N

=0,1

z

|z ₁ ⊗|z ₂ ⊗· · ·⊗|z _N

(30) x _i |⊗x _j |

Q _ij

|y _i ⊗|y _j

=

x _i |⊗x _j | tr _\ij Q

|y _i ⊗|y _j

≡

z

1

=0,1

z

2

=0,1

· · ·

z

N

=0,1

z

|z ₁ ⊗|z ₂ ⊗· · ·⊗|z _N

(31)

これらの縮約密度行列を与えられた

Q

から厳密に計算するためには

z

i

=0,1

z

j

=0,1

u ij (z i , z j , z _i , z _j )

|z i ⊗|z j

z i |⊗z j |

(32)

この表現と式

(31)

および式

(30)

を用いると式

(27)

の

F[Q]

は

F[Q] =

ij∈B

trQ _ij H _ij + trQlnQ (33)

と書き換えられる.

式

(33)

の右辺の第

2

項の

S[Q] ≡ −trQlnQ

は量子統計力学におけるエントロピーに対応するが,クラスター変分法ではこれを式

(31)

および式

(30)

の

Q _i , Q _ij

を用いて次のように近似される.

S[Q] ≡ −trQlnQ −

i∈Ω

trQ _i lnQ _i −

ij∈B

trQ _ij lnQ _ij − trQ _i lnQ _i − trQ _j lnQ _j

(34)

すなわち,式

(33)

の

F[Q]

の近似量として次の式で定義される

F Bethe

{Q _i , Q _ij }

を考える.

F Bethe

{Q _i , Q _ij }

≡

ij∈B

trQ _ij H ij +

i∈Ω

trQ _i lnQ _i +

ij∈B

trQ _ij lnQ _ij − trQ _i lnQ _i − trQ _j lnQ _j (35)

式

(31)

および式

(30)

の

Q _i , Q _ij

は以下の等式が成り立つことが要請される.

Q _i = tr _\i Q _ij , Q _j = tr _\j Q _ij , trQ _ij = 1, trQ _i = 1 (36)

ここで記号

tr _\i Q _ij

z _i |⊗z _j | Q _ij

|z _i ⊗|z _j

(37)

x j | tr _\j Q _ij |y j ≡

z

i

=0,1

z

j

=0,1

z

_i

=0,1

z

_j

=0,1

δ z

i

,z

_i

δ z

j

,x

j

δ z

_j

,y

j

z i |⊗z j | Q _ij

|z _i ⊗|z _j

(38)

(6)

クラスター変分法では式

(36)

を拘束条件として式

(35)

の

F Bethe

{Q _i , Q _ij }

を最小化するように決定された

Q _i , Q _ij

を式

(31)

および式

(30)

の

Q _i , Q _ij

に対する近似として計算される.

{ Q _i , Q _ij } = arg min

{ Q

i

, Q

ij

}

F Bethe

{Q _i , Q _ij } Q _i = tr _\j Q _ij , Q _j = tr _\i Q _ij , trQ _ij = 1, trQ _i = 1 (i∈Ω, ij∈B)

(39)

式

(36)

の拘束条件に対してラグランジュの未定乗数

L ij,i , L ij,j , λ ij , λ i

を次のように導入する.

L Bethe

{Q _i , Q _ij }

≡

ij∈B

trQ _ij H ij +

i∈Ω

trQ _i lnQ _i +

ij∈B

trQ _ij lnQ _ij − trQ _i lnQ _i − trQ _j lnQ _j

+

ij∈B

tr L ij,i

Q _i − tr _\i Q _ij

+ tr L ij,j

Q _j − tr _\j Q _ij

+

i∈Ω

λ i

tr Q _i − 1

+

ij∈B

λ ij

tr Q _ij − 1

(40)

式

(40)

の極値条件を求めることにより

Q _i

と

Q _ij

は次のように与えられる.

および式

(42)

の

{L ij,i , L ij,j |ij∈B}

に対して

L ij,i =

k∈c

i

\{j}

C k→i , L ij,i =

k∈c

i

\{j}

C k→i (43)

という形で

{C _i→j , C _j→i |ij∈B}

への変数変換を考える. これにより式

(41)

および式

(42)

は次のような表式に書き換えられる.

Q _i =

exp

k∈c

i

C k→i

tr exp

k∈c

i

C _k→i ( i∈ Ω) (44)

Q _ij = exp

− H ij +

k∈c

i

\{j}

C k→i ⊗I +

k∈c

j

\{i}

I⊗C k→j

tr exp

− H ij +

k∈c

i

\{j}

C k→i ⊗I +

k∈c

j

\{i}

I⊗C k→j

( ij ∈B ) (45)

最後に式

(42)

と式

(45)

を式

(36)

の第

1

式および第

2

式に代入することにより

I⊗C k→j

( ij∈B ) (46)

(7)

exp

k∈c

j

C k→j

tr exp

k∈c

j

C _k→j =

tr _\i exp

− H ij +

k∈c

i

\{j}

C k→i ⊗I +

k∈c

j

\{i}

I⊗C k→j

tr exp

− H _ij +

k∈c

i

\{j}

C _k→i ⊗I +

k∈c

j

\{i}

I⊗C _k→j (ij∈B) (47)

2

行

2

列の行列

{C i→j , C j→i |ij ∈B}

は量子系における有効場

(Eﬀective Field)

と呼ばれる量である.

4 確率伝搬法と量子系のクラスター変分法

本節では量子系におけるクラスター変分法が従来の確率モデル

(グラフィカルモデル)

に対してどのようにして確率伝搬法に帰着されるかについて概説する. 従来の確率モデルは一般に量子系の特別の場合として与えられることができる. すなわち, 従来の確率伝搬法は量子系に対するクラスター変分法の特別な場合として与えられる.

式

(26)

の

u _ij (z _i , z _j , z _i , z _j )

を

u ij (z i , z j , z _i , z _j ) ≡ −δ _z

_i

_,z

_i

δ _z

_j

_,z

_j

lnw(z i , z j ) (48)

により定義すると式

(25)-(26)

で定義される

2 ^N

行

2 ^N

列の行列

H

の非対角成分はすべて

0

となってしまう. すなわち式

(29)

の

Q

も非対角成分はすべて

0

となってしまう. 行列

H

と行列

Q

の対角成分は

x 1 |⊗x 2 |⊗· · ·⊗x N | Q

|x 1 ⊗|x 2 ⊗· · ·⊗|x N

= ^ij∈B

w _ij (x _i , x _j )

z

1

=0,1

z

2

=0,1

· · ·

z

N

=0,1 ij∈B

w ij (z i , z j ) (49)

により与えられる. すなわち,この場合には密度行列

Q

が頂点集合

Ω

と隣接頂点対

B

により定義されたグラフ上で確率変数

{x ₁ , x ₂ , · · ·, x _N }

の確率分布

P(x 1 , x 2 , · · ·, x N ) = ^ij∈B

w ij ( x i , x j )

z

1

=0,1

z

2

=0,1

· · ·

z

N

=0,1 ij∈B

w ij (z i , z j ) (50)

により与えられた確率モデル

(グラフィカルモデル)

に帰着されることを意味している.

x 1 |⊗x 2 |⊗· · ·⊗x N | Q

|x 1 ⊗|x 2 ⊗· · ·⊗|x N

= P ( x 1 , x 2 , · · ·, x N ) (51)

縮約密度行列

Q _i ≡ tr _\i Q, Q _ij ≡ tr _\ij Q

もその定義である式

(30)

および式

(31)

からやはり非対角成分はすべて

0

である. 縮約密度行列の対角成分

x i |Q _i |x i

および

x i |⊗x i |

Q _ij |x i ⊗|x j

は式

(50)

の確率分布

P (x 1 , x 2 , · · ·, x N )

の周辺確率分布

P _i (x _i ) ≡

z

1

=0,1

z

2

=0,1

· · ·

z

N

=0,1

δ _x

_i

j

P (z 1 , z 2 , · · ·, z N ) (53)

にそれぞれ等しくなる.

x i |Q _i |x i = P i (x i ) (54) x _i |⊗x _i |

j

\{i}

M k→j (x j )

z

i

=0,1

z

j

=0,1 k∈c

i

\{j}

M k→i ( z i )

w ij ( z i , z j )

k∈c

j

\{i}

M k→j ( z j )

(ij∈B) (60)

M _j→i (x _i )

z

i

=0,1

k∈c

i

M _k→i (z _i ) =

z

j

=0,1

w i,j ( x i , z j )

k∈c

j

\{i}

M k→j ( z j )

z

i

=0,1

z

j

=0,1 k∈c

i

\{j}

M k→i (z i )

w ij (z i , z j )

k∈c

j

\{i}

M k→j (z j )

(ij∈B) (61)

M _i→j (x _j )

z

j

=0,1

k∈c

=0,1

z

j

=0,1 k∈c

i

\{j}

M _k→i (z _i )

w _ij (z _i , z _j )

k∈c

j

\{i}

M _k→j (z _j )

(ij ∈B) (62)

更に

{μ i→j (x j ), μ j→i (x i )|ij ∈B}

を

μ _i→j (x _i ) ≡ M _i→j (x _j )

z

j

=0,1

M _i→j (z _j ) , μ _j→j (x _j ) ≡ M _j→i (x _i )

z

i

=0,1

M _j→i (z _i ) (63)

により導入すると,式

(59)-(62)

は以下の様な表式に帰着される.

Q i ( x i ) =

k∈c

i

μ k→i (x i )

z

i

=0,1

k∈c

i

μ k→i (z i )

( i∈ Ω) (64)

Q _ij (x _i , x _j ) = ^k∈c

ⁱ

^\{j}

μ _k→i (x _i )

w _ij (x _i , x _j )

k∈c

j

\{i}

μ _k→j (x _j )

z

i

=0,1

z

j

=0,1 k∈c

i

\{j}

μ k→i ( z i )

w ij ( z i , z j )

k∈c

j

\{i}

μ k→j ( z j )

(ij ∈B) (65)

μ j→i ( x i ) =

z

j

=0,1

w i,j (x i , z j )

k∈c

j

\{i}

μ k→j (z j )

z

と

Q ij (x i , x j )

は式

(50)

の確率分布

P(x 1 , x 2 , · · ·, x N )

の周辺確率分布

P i ( x i )

および

P ij ( x i , x j )

に対する確率伝搬法による近似値

(グラフが 1

次元鎖または木である場合は厳密解)になる.

5 ^まとめ

本稿では統計力学における量子力学的に拡張された確率モデル,すなわち量子系が古典系と比べてどのように難しくなるかを説明し,更にクラスター変分法の量子系に対する定式化を与えた. 更に,量子力学的拡張が行われる前の確率モデル

(いわゆる古典系)

に対して, この量子系に対するクラスター変分法からどのようにして従来の確率伝搬法が導かれるかの導出の詳細も説明した.

今後はこれらのクラスター変分法の量子系を視野に入れた定式化を具体的な確率的情報処理の個別の問題へと適用する試みが進められてゆくことが想定される. そのなかで個別の問題に内在する難しさに応じて具体的な量子情報統計力学としての近似アルゴリズムとして作り込まれることにより,クラスター変分法が更に洗練されたものとして深化して行くことが期待される.

謝辞

本研究の一部は文部科学省科学研究費補助金

(No.17500134, No.18079002)

の補助を得て行われたものである.

References

[1] B. J. Frey: Graphical Models for Machine Learning and Digital Communication, MIT Press, Cam- bridge, 1998.

[2] M. I. Jordan (eds): Learning in Graphical Models, MIT Press, Cambridge, 1999.

[3] F. V. Jensen: Bayesian Networks and Decision Graphs (Statistics for Engineering and Information Science), Springer-Verlag, 2001.

[4]

渡辺澄夫,萩原克幸,赤穂昭太郎,本村陽一,福水健次,岡田真人,青柳美輝: 「学習システムの理論と実現」, 森北出版, 2005.

[5]

繁桝算男,植野真臣,本村陽一: ベイジアンネットワーク概説,培風館, 2006.

[6]

西森秀稔: 「スピングラス理論と情報統計力学」, 岩波書店, 1999.

[7] H. Nishimori: Statistical Physics of Spin Glasses and Information Processing: An Introduction, Oxford University Press, Oxford, 2001.

[8]

田中和之編著: 臨時別冊・数理科学

SGC

ライブラリ「確率的情報処理と統計力学

—様々なアプローチ

とそのチュートリアル」,サイエンス社，2006.

[9] J. Pearl: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, Morgan Kaufmann, 1988.

[10]

岡育生編: 「小特集/ターボ符号・LDPC符号と繰り返し復号の理論」, 電子情報通信学会誌, vol.88,

no.4, pp.243-265, 2005.

[11] M. Opper and D. Saad (eds): Advanced Mean Field Methods — Theory and Practice —, MIT Press, 2001.

[12]

汪金芳,田栗正章,手塚集,樺島祥介,上田修功: 「統計科学のフロンティア/計算統計

I —確率計算の

新しい手法」,岩波書店, 2003.

(10)

[13]

田中和之著: 確率モデルによる画像処理技術入門, 森北出版, 2006.

[14]

小口武彦: 磁性体の統計理論,裳華房, 1970.

[15]

守田徹: 新しい物性

(石原明,

和達三樹編), 第

2

章フラストレートした磁性体の統計力学, 共立出版,

1990.

[16]

菊池良一,毛利哲雄: クラスター変分法材料物性論への応用,森北出版, 1997.

[17] J. S. Yedidia, W. T. Freeman and Y. Weiss: Constructing free-energy approximations and generalized belief propagation algorithms, IEEE Transactions on Information Theory, vol.51, no.7, pp.2282-2312, 2005.

[18] T. Morita: Cluster variation method of cooperative phenomena and its generalization II. Quantum Statistics, Journal of the Physical Society of Japan, vol.12, no.10, pp.1060-1063, 1957.

[19]

宮下精二: 熱・統計力学,培風館, 1993.

[20] H. Nishimori and Y. Nonomura: Quantum eﬀects in neural networks, Journal of the Physical Society of Japan, vol.65, no.12, pp.3780-3796, 1996.

[21]

田中和之,堀口剛: 画像修復に対する量子統計力学的反復計算法,電子情報通信学会論文誌

(A), vol.J80- A, no.12, pp.2117-2126, 1997; translated in Electronics and Communications in Japan, Part 3:

Fundamental Electronic Science, Vol.83, No.3, pp.84-94, 2000.

[22] T. Kadowaki and H. Nishimori: Quantum annealing in the transverse Ising model, Physical Review E, vol.58, no.5, pp.5355-5363, 1998.

[23]

田中和之: 量子力学的に拡張されたライン場をもつ結合ガウス・マルコフ確率場モデルを用いた画像修復,電子情報通信学会論文誌

(D-II), vol.J84-D-II, no.4, pp.737-743, 2001.

[24] J. Inoue: Application of the quantum spin glass theory to image restoration, Physical Review E, vol.63, no.4, article no.046114, pp.1-10, 2001.

[25] H. Nishimori and P. Sollich: Error counting in a quantum error-correcting code and the ground-state energy of a spin glass, Journal of the Physical Society of Japan, vol.73, no.10, pp.2701-2707, 2004.

[26] K. Takeda and H. Nishimori: Self-dual random-plaquette gauge model and the quantum toric code, Nuclear Physics B, vol.686, no.3, pp.377-396, 2004.

[27] S. Suzuki and M. Okada: Residual energies after slow quantum annealing, Journal of the Physical Society of Japan, vol.74, no.6, pp.1649-1652, 2005.

[28]

西森秀稔: 量子情報処理と統計力学

(リレー連載/確率的情報処理と統計力学 ―様々なアプローチとそ

のチュートリアル

10),

数理科学, no.510, pp.77-83, 2005.

[29] S. Morita and H. Nishimori: Convergence theorems for quantum annealing, Journal of Physics A, vol.39, no.45, pp.13903-13920, 2006.

[30] A. Das and B. K. Chakrabarti (eds): Quantum Annealing and Related Optimization Methods, Series: Lecture Notes in Physics, vol. 679, Springer-Heidelberg, 2005.

[31]

大貫義郎,鈴木増雄,柏太郎: 経路積分の方法,岩波書店, 2000.

確率伝搬法と量子系の平均場理論 田中和之

18

確率伝搬法と量子系の平均場理論

1

6-3-09

1 はじめに

[1, 2, 3, 4, 5].

[6, 7, 8].

[9].

Turbo

[10].

[11, 12, 13].

[14, 15, 16].

[12, 13, 17].

[20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30].

[12, 13, 17].

20

[18].

2

1

3

4

(統計力学でいうところの古典系)

5

2 1 次元量子系と Suzuki-Trotter 公式

1

e-mail address: [email protected], webpage URL: http://www.smapip.is.tohoku.ac.jp/˜kazu/

x 1 , x 2 , x 3 , x 4

0, 1

2

(Joint Probability

Destribution)

P (x 1 , x 2 , x 3 ) = w 12 (x 1 , x 2 )w 23 (x 2 , x 3 )

x

=0,1

x

=0,1

x

=0,1

w 12 (x 1 , x 2 )w 23 (x 2 , x 3 ) (1)

x

=0,1

w 12 (x 1 , x 2 )w 23 (x 2 , x 3 ) = w 12 (x 1 , x 2 )

x

=0,1

w 23 (x 2 , x 3 ) (2)

M 3→2 ( x 2 ) ≡

x

=0,1

W 23 ( x 2 , x 3 ) , M 1→2 ( x 2 ) ≡

x

=0,1

W 12 ( x 1 , x 2 ) (3)

(Marginal Probability Distribution) P (x 2 ), P (x 1 , x 2 ), P (x 1 , x 2 )

P(x 2 ) =

x

=0,1

x

=0,1

P(x 1 , x 2 , x 3 ) = M 3→2 (x 2 )M 3→2 (x 2 )

x

=0,1

x

=0,1

M 3→2 (x 2 )M 3→2 (x 2 ) (4)

P (x 1 , x 2 ) =

x

=0,1

P (x 1 , x 2 , x 3 ) = W 12 (x 1 , x 2 )M 3→2 (x 2 )

x

=0,1

x

=0,1

W 12 (x 1 , x 2 )M 3→2 (x 2 ) (5)

(2)

(1)

x i = 0 (i = 1, 2, 3)

x i = 0| ≡

1 0

, x i = 1 (i = 1, 2, 3)

確率伝搬法と量子系の平均場理論田中和之

¹

1 ^はじめに

2 1 ^{次元量子系と} Suzuki-Trotter ^公式

w ₁₂ (x ₁ , x ₂ )w ₂₃ (x ₂ , x ₃ ) (1)

(Marginal Probability Distribution) P (x ₂ ), P (x ₁ , x ₂ ), P (x ₁ , x ₂ )

P (x ₁ , x ₂ ) =

P (x ₁ , x ₂ , x ₃ ) = W ₁₂ (x ₁ , x ₂ )M _3→2 (x ₂ )

W ₁₂ (x ₁ , x ₂ )M _3→2 (x ₂ ) (5)

(x ₁ , x ₂ ), (x ₂ , x ₃ ), (x ₁ , x ₂ , x ₃ )

|x ₁ ⊗|x ₂ , |x ₂ ⊗|x ₃ , |x ₁ ⊗|x ₂ ⊗|x ₃

2 ³ ×2 ³

w ₁₂ (x ₁ , x ₂ )w ₂₃ (x ₂ , x ₃ )(|x ₁ ⊗|x ₂ ⊗|x ₃ )(x ₁ |⊗x ₂ |⊗x ₃ |)

exp(A) ≡ ^+∞

n! A ⁿ (8)

E ≡ E ₁₂ + E ₂₃ (10)

E ₁₂ ≡

− lnw ₁₂ (z ₁ , z ₂ )