5. マクロ・モデルの例 -- 確率過程にもとづくモデル

この章では，第 3 章でしめした 2 つの提案を具体化するために必要なマクロ・モデルの例 について説明する．5.1 節では，このマクロ・モデルの説明に必要な大域秩序度という量 を定義し，それを例題について実際に観測した結果をしめす．そして，5.2 節でマルコフ 連鎖にもとづくマクロ・モデルを説明する．ただし，このモデルは未完成である．

5.1 大域秩序度の定義とその観測値

局所秩序度の作業記憶全体にわたる和を大域秩序度という [*1]．グラフ彩色問題のばあいは， 頂点すなわち vertex 型のデータの局所秩序度が 0 なので，すべての辺すなわち edge 型の データの局所秩序度の和が大域秩序度となる．したがって，辺の総数を N とすると，大 域秩序度 O の値の範囲は 0 ≦ O ≦ N となる．大域秩序度が最小値 0 をとるのはすべての頂 点が同一色のばあいであり，最大値 N をとるのは解がえられた状態である．米国地図の 彩色においては，辺数が 106 なので O の最大値は 106 である．

SOOC-92 による米国地図の彩色のひとつの実行過程において，大域秩序度の値を反応が おこるごとに実測した結果を図 10 にしめす．初期状態においてはすべての頂点に同一の 色をあたえている．この図から，つぎの 2 つのことがわかる．

第 1 に，CCM にもとづくグラフ彩色においては大域秩序度が単調に増加しないことが容 易にわかる．これは，4.2 節でもふれたように，反応によってある頂点が隣接頂点とこと なる色にぬりわけられても，その頂点の他の複数の隣接頂点とおなじ色にぬられることが あり，このようなばあいには大域秩序度が減少するからである．キャスタのなかには，こ のように局所秩序度の増加がばあいによって大域秩序度の減少をひきおこす競合型のキャ スタと，局所秩序度が増加するときには大域秩序度が減少することがない協調型のキャス タとがある．金田 [Kan 92] でしめした N クウィーン問題のキャスタも競合型である．

第 2 の点は第 1 の点ほどあきらかではないが，図 10 をみると大域秩序度の変化はランダムにみえるから，確率過程とみなせるであろう [*2]．しかも，この確率過程は実行開始からし ばらくは非定常性がつよく，その後定常にちかくなっていることがよみとれる．図 10 の ばあいには反応回数が 100 回くらいまでは非定常性がつよいようにみえる．ただし，反応 回数が 100 回をこえても反応により解に到達するばあいとそうでないばあいとが存在する から，真の定常状態に達してはいない．真の定常状態は解に到達した状態である．したが って，CCM にもとづく計算過程においては，つぎのような 3 つの状態がこの順にあらわ れるという仮説をたてることができる．

1. 強非定常状態 : 反応ごとに確率分布が変化する状態．
2. 準定常状態 : 反応ごとに解状態すなわち大域秩序度が最大の状態の確率が増加するが，それ以外の状態 のわりあい (条件つき確率) は変化しない状態．
3. 停止状態 (定常状態) : 大域秩序度が最大の状態の確率が 1 である状態．ランダム戦略を使用しているばあいには 有限時間でこの状態が実現されることはない (すなわち計算時間に上限はない)．したがっ て，この状態は t → ∞ の極限として存在する．

図 10　グラフ彩色における大域秩序度の実測値例

5.2 マルコフ連鎖にもとづくマクロ・モデル [*3]

CCM の計算における大域秩序度の時系列をマルコフ連鎖とみるマクロ・モデルを構成し た．このモデルは，大域秩序度の時系列を観測してそれをなんらかのかたちで反応の制御 にいかすことをめざしている．以下このモデルについて説明するが，まずやや一般的な説 明からはじめる．

このモデルにおいては，反応がおこるごとに変化する作業記憶の状態を確率過程とみる． そのためにまず，初期状態において時刻を 0 とし，反応がおこるたびに時刻が 1 ずつすす むとみなす．そして，時刻 t における作業記憶の状態をあらわす適当なマクロな変数 X(t) を確率変数とみなす． X(t) がとる値として実数値や数値以外のものをかんがえることも できるが，ここでは非負の整数値にかぎられると仮定する．また，X(t) に関してマルコフ性がなりたつことを仮定する [*4]．すなわち，X(t) が i という値をとる確率を p(X(t) = i) (Σ(i=0 to I) p(X(t) = i)) = 1 がなりたつ) とし，p(X(t) = i) (i = 0, 1, ... , I) を要素とするベクトルを p[t] とするとき，p[t] と p[t+1] とのあいだにつぎのような関係がなりたつと仮定する．

p[t+1] = T p[t] .

ここで遷移行列 T は I 行 I 列の行列であり，その値は時刻にはよらないとする．T の固有値を λ0, λ1, ... , λI (λ0 ≧ λ1 ≧ ... ≧ λI ) とすると，λ0 = 1 がなりたつ [Mor 79]．また，T^n はつぎの ように表現することができる [Mor 79]．

T^n = T0 + (λ1)^n T1 + (λ2)^n T2 + ... + (λI)^n TI .

p[t] = Tt p[0] かつ λ2, ... , λI < 1 がなりたつから，t → ∞ とすれば (λ1)^t, ... , (λI)^t → 0 となり，したがって Tt → T0 となる．このような時刻 t における状態が停止状態である．また，λ2, ... , λI は 1 より十分にちいさいが λ1 が 1 に十分にちかいというばあいには，t が十分おおきな値をとるときに Tt ≒ T0 + λ1t T1 がなりたつ．このような時刻 t における状態が準定常状態だとかんがえられる．

このような仮定のもとで X として大域秩序度をとり，SOOC-92 による大域秩序度の実測 値をモデルにあてはめてグラフ彩色問題およびエイト・クウィーン問題のキャスタの実行 における T の値を推定すると，大域秩序度の変化をうまく説明できるモデルがえられた． 紙数がたりないため T の推定法はべつの機会にしめす．これ以下の計算はグラフ彩色問 題についてはまだ部分的にしかおこなっていないため，これ以降はエイト・クウィーン問 題の解析結果をしめす (ただし，これまでにわかっている範囲ではグラフ彩色問題も同様 の性質をしめしている)．この問題のばあい，推定された T からその固有値をもとめると λ1 = 0.986, λ2 = 0.5, λ3 = 0.2, ... となった．これにより上記の条件の成立がたしかめられ， したがって準定常状態の存在がたしかめられたといえる．

このモデルが実測結果とよくあっているということは，つぎのようにしてもたしかめるこ とができる．大域秩序度 (global order degree, GOD) の実測値から p(X(t) = i) の値を直接推 定したものを図 11 にしめし，マルコフ連鎖モデルから推定した p(X(t) = i) の値を図 12 に しめす [*5]．これらを比較すると，時間 (反応回数) のスケールにちがいがあり，また時間が 16 以下の部分すなわち λ2, λ3, ... 以下の固有値に支配されている部分にはちがいがあるが， それ以外はよく一致している．したがって，マルコフ連鎖モデルじたいは適切だが，固有 値の推定誤差がおおきいとかんがえられる [*6]．

図 11　エイト・クウィーン問題の計算過程における実測値から直接推定した大域秩序度 の分布の変化

図 12　マルコフ連鎖モデルから推定したエイト・クウィーン問題の大域秩序度の分布の変化

ところで，上記のモデルにはまだつぎのような問題がある．第 1 に，推定すべきパラメタ がおおすぎる．T のすべての要素を推定する必要があるから，グラフ彩色問題のばあいに は，辺の数を N とすると (N+1)^2 個のパラメタを推定することになる (このなかには実際には推定できないものもあるが)． したがって，パラメタ推定のために多量の測定データ を必要とする．第 2 に，これはもっと重大な問題だが，このような観測によってえられた モデルをどのようにして制御にいかせばよいかは，まだほとんどわかっていない [*7]．自己組織化はおろか， 自己安定化をどのようにあつかえばよいかもわかっていない [*8]．ただ，すくない測定データからモデルのパラメタが 推定できれば，4.2 節でふれたような計算効率の 向上のためにこのモデルをいかすことは可能だろう．これらの問題の解決は今後の課題で ある．

[→ 次章]

脚注