連載講座11111111111111111111111111111111111111111111111111111111111111111111111111111111.
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

ニューラノレネットの基礎数理 (3)上坂吉則
11111111111111111111111111111111111111""
"
111""
1
111111111"
1
11111111111111111111111111111111111111111"
11111"
11"
111111"1111111111111111""""""
111"""
"
1
1111"
1
1111"
1
1111111111"
1
1111111111111111111111111
1115. ポルツマンマシン"'1ニtz債が O か 1 をとる n 個の入力.xh … ， X免に対して出力IfJカ

y=O , ly が確率:

(弘1)

P(y==I)=a{¥竺ー)=一一一
1 一一一一T;‑l+exp(‑uIT)X.

で l を出し，また確率:

P(y=<1)P( 円 )==I-P( ド1)吋(一手)(5 , 2)で 0 を出す':::'.::1.，-口ンモデんを考える(図 5.1).

ここに

u=:wo+ 叩 l X l+ ぃ・ +W旬Zπ(5 , 3)は入力 .x =(Xh "'，.x n ) と重み加$としきい値(の符号を反転したもの)加。から定まるニューロンの内部電位であり ，uTlt 個々のニューロンには依存しない温度と呼関 S. 1 デジタル型静的確率論的ニューロンモばれる正の定数(実数)である.発火確率を u の関数とデルと発火確率の温度 T への依存の様子

みると，それが大きいほど出力として 1 ÌJ< 出やすく，小さいほど O が出やすい.このような情報処理素子をニューロン h を選ぶ.

3
" 内部電位向 =Uk(XI ， … ， x，，) を求める.

ー日ンのデジダル的静的確率論的モデルという.

4" 確率 σ (ukIT) でこのニューロンの出力として l

このようなニ.".~ロン素子を，前節のように，相互に結合したフイ}ドパック型の回路を考える(図 4.2).のとき，各ユユーロンの出力が引ならばこを出す(確率 1 ー σ (Uk/ T ) で出力として 0 を出す).
デk 番目のユユーロンの内部電{立は(5.
4)

Uk'==U~(X)=U，危 (.xt."'，.x，，)=akI X l+ ・・・十 ak九x，， +b kで与えられることになる、ここに dυ は i 番目の ι ュ一
日ンと j 番目のニ品}ロンとの結合係数であり ， bd 主 i番目のニ品ーロンのしきい値である.しかし，このような回路を考えても，上のニューロンモデルには時間特性うすると各':::'.;:L---ロンの内部電位が式 (5.3) によって決まる.にういてだけ出力を確率的に定めるのである.このような確率的な動作を繰り返す機械をボルツマンマシンという.

この機械の各時刻における様子は各ニューロンの発火の状況によって記述することができるから ， .x==(x"... ,Z拘)を状態と呼び，すべての状態の集合を S で表わすこにする:01
i=l ，… ， n に対して引に初期値を設定する.

20n 個の二品}ロンの中から一様分布で l つのユユとにする.なお，以下の議論では回路の結合係数に関して(ラ.ラかみさか

このとき n 個のニューロンの中から確率 l/nでランダムに 1 つのニ品ーロンを選び，このニューロンが規定されてし、ないから，このままではこの回路は動きょうがない.そこで回路の動作を次のように定めること

2" へゆく.

つまり，最初各 ζ 品ーロンの出力を任意に定める.そよしのり

東京理科大学理工学部

宇 278 野間市山崎 2641

408(30)a;;=O ，

乎 j:今 a ， j= α jtを仮定しておくことにする.

ボルツマンマシン Ll:，
© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.とでみたように，その状態を確オベレーシ酒ンズ・リサーチ

率的に変えてし、く機械である.そこで時刻 t での状態をを z 行 g 列の成分とする行列 A を受理行列という.

表わす確率変数(ベクトル)を，習慣にしたがって大文字を使って ，X(t) と表わすことにすると，

ボルツマン

マシンは 1 つの確率過程:(5.
6)

この 2 つの確率，すなわち，摂動確率と受理確率を用いると時刻 t で状態が z であるとき時刻 t+1 で状態が却に移る確率:

X(O) ， X (1)， … ， X(t) ， ・(5.
12)と同一視できる.この過程は実は以下に述べるような状

l主態推移確率行列 G T を持つ有限マルコフ連鎖であることがわかっている [4 ]. 以下でそのことを簡単に見ておG T (x , y)=P(X(t+1)=y/X(t)=x)GT(x , y)=

(5.
13)

こう.

反転した(つまりx(k)=(Xh…, Xk-h 1- x k, xk+h. ・ '， Xn )で表わすことにする.
0

このとき，上のアルゴリズムのは z を摂動し，次に移る状態の候補として x(k) を確率分布:(5.
8)で与えられることがわかる.そして，この確率は明らか

o ならば 1 にならば O にした)状態を2

x ヲéy のとき;

(1- 1::.件 ω P(x ， z)AT(x ， z) ， x=y のとき

いま，状態 X=(XJ，"'， X n ) に対してその第 k 成分を(5.
7)

rP(x , y)AT(x , y) ,(l/n ， ヨ k: y=x(k) であるとき;

P(x , y)=llO ,その他のときにしたがって，確率 P(x ， x(k)) で選定したということができる.この P(x ， y) を摂動確率といい，これを z 行H 列の成分とする行列 P を摂動行列と呼んでいる.
ポルツマンマシンのメカニズムの第 2 の部分は選んだニューロンの発火を試み，その結果によって状態の第 h(5.
14)

VX, yES:O~三 GT(x， y):豆 1 ，(5.
15)

Vx ε S; 1:G T (x , y)=1lIeSを満たしているので，ボルツマンマシンの状態の列はGT(x ， y) を z 行軍列の成分とする状態推移確率行列 G Tにしたがうマルコフ連鎖であることがわかるわけである.

ここで，このマルコフ連鎖にしたがう状態の確率分布がどのような分布に近づいていくかを考えてみる.そのためにエネルギー E から定まるギブス分布あるいはボルツマン分布と呼ばれる確率分布:

(5.
16)

qT(x)=す exp(-+E(x))( 目的

成分 X l;を決めることである(上のアルゴリズムの 40 をを導入する.ここに Z は式 (5.16) の z に関する和を!

参照).とするための規格化定数であるが，統計物理学においてこれを次に推移する状態の候補という観点から考えると，その候補をほんとうに受け入れるかどうかを決めるということになる.つまり，現在 z とし、ぅ状態にあって，選んだ候補が x(k) であったとすると，その候補が受け入れられるのは Xk=O のときはニューロン h が発火するときであり，また ， xk=1 のときはニューロンh が発火しないときである.したがって，ニューロンモデルの発火確率の式 (5.1) ，(5.2) に注意すれば，確率分配関数と呼ばれるものに相当している.
このとき，ギプス分布とギプス行列の間に次のようないちじるしい関係(詳細釣合条件い

(5.
17)

VX, YES: qT(X)GT(x， 宮) =qT(y)GT(y , x)が成り立つことが簡単な計算からわかり，これを用いると，さらに(5.(8)

VT :qTGT=qT

σ( ー ( 2X k ー I) Uk (x)/T) で状態 x(k) を受け入れるとを示すことができる.ここに qT は qT( 討を第 z 成分と考えてよいことになる.

する確率(行)ベクトル(状態の確率分布)である.

ここで状態 z から定まる量:(5.
9)

式 (5.18) は状態の確率分布がギプス分布であるとき

nnE(Z)=-LE1atjZ戸J-zb内には，状態推移確率行列 G T によって状態確率分布が変化しないということを意味している.このような状態確を考え，これをエネルギーと呼ぶことにする.そうすると状態 z が x(k) に変わったときのエネルギーの差は

(5.
10)

E(x(k))-E(x)=(2x" 一 I)Uk (x)と表わされるので，状態 E を受け入れる上の確率は

(5.
11)

‑")

( E(x(k))‑E(x)¥AT(x ， y)= σ ， --"'Tと書くことができる.この確率を受理確率といい，これ1991 年 8 月号

率分布をこのマルコフ連鎖の平衡分布と呼んでいる.
ところで，上の推移行列 G T をよく調べてみると 2 つの重要な性質を持っていることがわかる.すなわち，その 1 つは(5.
19) Vx , yES ，ヨ S; Gも (x， y)>Oが成り立つことで，このとき G T は既約であるという.

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(31)409ここに G}(x， y) は行列 G T の s 個の積の z 行 g 列の成分である.時刻 O での状態確率分布を p(O) とすると
きs 時刻後の状態確率分布 p(s) は P(s)=p(O)G} で与えられるから，マルコフ連鎖が既約で・あるとはどんな状態から出発しでも十分の時間の経過の後には任意の状態に推移できる可能性をもっているということに他ならない.

li
mli
mrG'!
p=qo(5.
25)

T吋 Om→∞が成り立つことになる.

最適分布 qo はエネルギーを最小にするような状態が確率 1 で発生することを意味している.したがって，十分低い温度 T を設定し，ボルツマンマシンを駆動すると，状態分布はやがてはギプス分布に近づき，それはほとんど最適分布に等しいから，エネルギーの最小値を与状態推移確率行列のもう 1 つの性質は

(5.
20)

VXES: {sIG}(x， x)>O} の最大公約数 =1が成り立つことであり，このとき G T は非周期的であるという.つまり，任意の状態に関して自分自身に戻るのえる状態が高い確率で発生することになる.つまり，離散値をとる変数の関数(エネルギー)の最小値を求めることができるわけである.これが確率的探索機械としてのボルツマンマシンの基本的なからくりである.に要する推移の回数の最大公約数が l であるということ

6. 確率論的最小値探索機械である.

きて，状態推移確率行列が既約でしかも非周期的であると，唯一つの平衡分布が存在して，どんな初期分布から出発しても状態分布はやがてはこの平衡分布に収束することがマルコフ連鎖の理論でよく知られている.つまり

r を任意の状態確率分布とするとき

(
5.
21)

limrG~=qT

いま，ボルツマンマシンのアルゴリズムを摂動確率と受理確率を用いて書き改めると次のようになる.
01x に初期状態を設定する.

20

確率分布 P(x ， y) にしたがって状態 U を選ぶ.

30 受理確率 AT(x， y) を求める.

40 確率 AT(x ， y) で状態を z から百に更新する(確m→∞が成り立つ.したがって，すてtこ見たように，ギプス分布が平衡分布であったわけであるが，実はこれが唯一の平衡分布であり，ポルツマンマシンを動かしていくと，最初の状態が何であれ，やがては状態分布は式 (5.16)

率 1-A T (x ， y) で状態を変えな L 、).

50 20へゆく.

ここで，式 (5.11) の受理確率をギブス分布を用いて表わすとのギプス分布に必ず近づいていくということになる.これがボルツマンマシンの最も重要な確率的性質である.
ここで平衡分布であるギプス分布の形が温度 T によってどのように変わるかを調べてみよう.そのためにエネ(6.
1)

AT(x , y)=q T( 智 )/qT(X)

1+qT(y)/qT(X)と書くことができる.

一方，ニューラルネットのことを忘れて，s を一般のルギー E の最小値 Emln を与える S の要素の集合を状態集合(数学的には単に有限集合であればよ L 、)と(5.
22)し，So={xIE(x)=Emln}と表わすことにし，これを用いて状態の確率分布:

(5.
23)

r 1/ ISol ， xES o のとき;

qo(x)=llO,を考える.

x$S。のときここに IAI は集合 A の要素の数を表わす.

E をその上で定義された実数値関数と考えてみると，上のアルゴリズムはシミュレーテ 4 ・y ドアニーリン

グと呼ばれる確率論的探索機械とほぼ同じものになっているのである [1 ， 4J. 違うところは 2 つある.
その l つは摂動確率 P(x， y) を z 行 y ;lJ の成分とする

この確率分布をエネルギー E の最漣分布と呼ぶことにす行列 P( これを摂動行列という)が L 、わゆる確率行列でる.

あって，次の条件:

そうすると温度 T を O に近づけることによって，ギプ(6.
2)

VXES:P(x , x)=O ,ス分布は最適分布を限りなく十分に近似できるという性(6.
3)

VX， 世 ε S: P(x ， 百 )=P(y ， x) ，質をもっていることが簡単な計算から確かめられる.つ(6.
4)

Vx , yES，ヨ s: P8(X, y)>0まり，(5.
24)を満たしているならばどんなものでもよいという点であlimqT=qoる.ここに ， P'(x， y) は行列 P の s 個の積の (x， y) 成T吟O分である.

が成り立つ.

したがって，この式と式 (5.2 1)を合わせると，結局410 (32)

違いの他の 1 つは受理確率が© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オベレーションズ・リサーチ

(6.
5)

(qT(Y)¥

AT(x , y)=g('.1' 一一 i¥qT(X)J要とするが，その筋道は次のように要約することができの形で与えられればよいということである.ここに g は区間 (0，∞)から区間 (O， IJ への単調増加な関数で(6.
6)る.

いま，温度 T を時刻 t に対して

(6.
10) O(t)=一一全一一VUE( い) :仰 )=Ug(~)

ln(t+2)を満たすものである[ 4J. 。の例としては式 (6.1) のボルツマンマシンの場合，すなわち，

t=0， 1 ， 2， …と制御することにする.ここに A はエネルギー E と摂動行列から定まるある定数である.

このとき受理確率 AT(x， y) とギプス行列の成分 GT(x， 引は!時間 t に依存(6 , 7)g(U)= ー竺ーするので，それぞれを A(x， y; t) および G(x， y; t)l+uと書くことにする.そうすると，上のシミュレーティッ

や

(6.
8)

ドアニーリングのアルゴリズムは次のように書き改めらg(u)=min{l , u}れる.

が知られているが，これらは01rγ-11 ノ γ(6.
9)gr(u)= 卜二一lr

x に初期状態を設定する.

20 時刻 t を O にセットする.

Ll+u Jにおいて，それぞれ r=1 あるいは r→∞とした場合に含まれる.特に式 (6.8) の g を用いた場合のアルゴリ
ズムはメトロポリス法として知られている.
以上述べたことから，ポルツマンマシンはシミュレーティッドアニーリングの特殊なタイプであることがわかる“アニーリング"とは物質を高温から低温へとゆっ
くりと“焼きなまじ'て L ぺ物理現象のことをいう.このとき，物質の内部エネルギーが最小の準位になることが知られている.そして温度 T においてエネルギー準位が E(x) である状態 z が生起する確率が式 (5.16) のギプス分布で与えられると L 、うわけである.
ところで，式 (5.24) によれば，温度 T を小さ〈設定するほど，状態分布は最適分布 qo に近づき，したがっ30 磯率分布 P(x， y) にしたがって状態 E を選ぶ.

40 温度 T を O(t) に設定する.

50 受理確率 A(x， y; t) を求める.

60 確率 A(x， y;t) で状態を z から g に更新する(確率 l-A(x， y; t) で状態を変えな L 、).
070
時刻 t を 1 だけ増し ， 3 へゆく.

このとき，時刻 t での状態の確率分布 ρ (t) は(6.
11)p(t)=P(O)G(O)G(I) …G(t)と麦わされる.この ρ (t) が t→∞で最適分布 qo に収束してくれれば，すなわち，(6.
12) limp(t)=qoが成り立つならば，時聞に関して非一様なアニーリングによって関数 E の最小値を確率 1 で求めることができるて，大きい確率で最小値を求めることができるはずであことになる.そしてこの収束性は一様でないマルコフ連る.しかし，このとき状態推移に関してやっかし、な問題鎖の理論を使い，やや長い議論ののちに保証されることが生じてくる.つまり，状態が目的関数の極小点に到達になるのである [2 ，すると，そこから抜け出すことがきわめて困難になり，

3, 4
J.

こうして得られた結果は，式 (6.10) の温度制御にしなかなか最小点に到達できない.こういうときには一度たがうならば，どんな状態から出発してもボルツ 7 ンマ

温度 T を大きくすれば極小点から飛び出すことができそシンを含むアニーリングの手法によって必ずエネルギーうである.このように，状態推移を重ねて L 、く過程で温の最小値を探索できることを意味している.しかし，そ度 T をゆっくりと下げて L ぺ方がより確実に最小点に到うはし、っても最小値が得られる確率が時刻 t に関してど達できそうに考えられる.

れくらいの早さで Uこ近づくかが問題である.つまり，しかし，こうするとギプス行列 G T はもはや時間に関収束の速度である.これに関しては実験的にいろいろ考して一定ではなくなり，したがって，これまでの議論は察されているが，明確な結論は現在のところ得られてい通用しなくなる.つまり，状態推移確率行列が時間に依ない模様である[5].

存するタイプのマルコフ連鎖(これを(時間的に)一様でないマルコフ連鎖という)を扱わなければならない.

7.

おわりに探索の過程で温度をしだいに下げて L ぺ場合，つまり，多くのニューラルネットの中から典型的なマシンを 3

一様でないアニーリソグを議論するには多くの準備を必つ選んでその数理的からくりを紹介した.学習認識機械

1991 年 8 月号

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(33)411は基本的には関数補聞の問題であるが，汎化性まで考慮に入れるとさまざまな課題をはらんでおり，統計的推定

参芳文献やトポロジ}や組合せ理論が援用されることになる・決定論的探索機械では微分方程式の安定点に関する議論が[1J Aarts , E. andKorst , J.:
Simulateda
nneal‑ing and Boltzmann machines:A stochastic

中心的役割を演じる.また，シミュレーティッドアニー

approach to combinatorial optimization andリングは本質的には有限マルコフ連鎖の理論に負うとこ

neural computing , Wiley , 1988.

ろが大きい.

. and Geman , D.:Stochastic re・[2J Geman , S

大部分は大学初年級の線形代数・微分積分・確率統計

laxation , Gibbs distributions , and the Bayeｭ

でこと足りるとはし、ぇ，少しきちんと理解しようとする

sianrestorationof images , IEEE Trans. onと，数値解析や微分方程式の定性的理論やマルコフ連鎖

Pattern Analysis and M achine Intelligence ,の入り口程度は理解しておく必要がある.ましてや新しいを展開を試みようとすると，ときには予想もしない数学が必要になることもあるかも知れない.
この傾向は，ニューラルネットのような，幹線道路が敷かれていない新興分野の特徴であると同時に悩みでもある.これに対処するには，専門にとらわれない自由なPAMI-6 , 6 (1984) , 721‑741.
[3J Mitra , D. , Romeo , F. and SangiovanniｭVincentelli , A.:Convergenceandfinite‑time
behavioro
fsimulatedannealing , Adv. Appl.

Prob. , 18 (1986) , 7
47‑771.
[4J 上坂，塚田:シミュレーティッドアニーリングの発想と時聞を掛けて培われた底力に頼るしかないようにための受理関数の族について，電子情報通信学会技思われる.そのような資質をもった優れた理論研究者が術報告，多く輩出して，この世界に新風を吹き込んでくれることを期待しつつ，この連載の筆をおくこととする.

NC89‑
66 (1990) , 31‑
36.

[5J 上坂:シミュレーティッドアニーリングの摂動近傍と収束速度について，
告，

電子情報通信学会技術報,

AI90-37 , PRU90‑31 (1990) , 2 -29.

木学教
募集人員経営情報学部専任講師まだは田教授… 2 名

〈勤務先〉

担当科目

プログラミシグ/情報システム設計/〒259-11

専門分野

計算機ソフトウエ戸、情報システム

シミュレーション(情報システム開発の実務経験のあることが望ましい〉

着任時期

1992年4 月 1 日

神奈川県伊勢原市上粕屋1573

産能大学(目憧醐産
経営情報学部

応募資格大学院博士課程修了者
ま疋はこれに準ずる研究歴を有する者。

通勤圏に唐住できる者、年齢40歳位まで。
提出書類履歴書、教育研究業績一覧、〈書類送伺先・問合せ先〉

1 干141 東京都田川区大崎 5-6-2

主要論文別刷
応募締切

随時(適任者ガ決定次第締切ります。〉※応募書類は返却いだしませんのでご了承下さい。

412(34)

TE
L.
03‑
5487‑
8855|学校法人産能大学人事2課OR係© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オベレーションズ・リサーチ