提案アルゴリズムの計算時間に関するシミュレーション

7.3.2 結果と考察

表7.3: 平均場近似と提案アルゴリズムの精度比較 グラフG_aのサイズ クラスターの個数Z 各クラスターの列数 D(q^G_ˆ^b

θ ∥P_θ^Ga) D(q^Gc

h ∥P_θ^Ga) 2 M_i = 3 (i= 1,2) 1.6×10⁻³

3×6 3 Mi= 2 (i= 1,2,3) 1.4×10⁻² 5.9×10⁻²

6 Mi = 1 (1≤i≤6) 2.3×10⁻² 2 M_i = 4 (i= 1,2) 6.0×10⁻³

3×8 4 Mi = 2 (i= 1,2,3,4) 1.7×10⁻² 1.0×10⁻¹ 8 Mi = 1 (1≤i≤6) 6.9×10⁻²

2 Mi = 5 (i= 1,2) 1.0×10⁻²

3×10 5 Mi = 2 (1≤i≤5) 2.2×10⁻² 9.2×10⁻²

10 Mi = 1 (1≤i≤10) 5.4×10⁻²

表7.3は，格子模型G_aのサイズ，クラスター型模型G_bに含まれるクラスターの個数，

各クラスターの列数をそれぞれ変化させた時に，提案アルゴリズムにより導出される近似 分布q^G_ˆ^b

θ ∈ M(G_b) と平均場近似により導出される近似分布q^Gc

h ∈ M(G_c) の精度をまと めた表である．すべてのパターンにおいて，提案アルゴリズムにより導出される近似分布 q^G_ˆ^b

θ ∈ M(Gb) は，従来の平均場近似により導出される近似分布q_h^Gc ∈ M(Gc) よりも近似 精度が上であるという結果となった．また，格子模型Gaのサイズを固定し，クラスターの 個数Zを増加させた場合，近似分布q^G_ˆ^b

θ ∈ M(G_b) の精度は徐々に落ちていることが確認で きる．これは，クラスターの個数が増加していくにつれて，分布族M(G_b)の範囲が狭まっ ていくことに起因している．

7.4 提案アルゴリズムの計算時間に関するシミュレーション

7.4.1 シミュレーション内容

各クラスターの列数と行数，クラスター型模型に含まれるクラスターの個数をそれぞれ増 やしていく場合に，提案アルゴリズムの計算時間がどのように増加していくのかについて，

計算機によるシミュレーションで確認をした．

第 7章 数値実験

7.4.2 結果と考察

表7.4: 各クラスターの列数の増加に伴う計算時間の変化

クラスターの個数Z 各クラスターの行数 各クラスターの列数 計算時間[ミリ秒]

2 3 M_i = 4 (i= 1,2) 7

2 3 M_i = 5 (i= 1,2) 29

2 3 Mi = 6 (i= 1,2) 132

2 3 Mi = 7 (i= 1,2) 402

2 3 M_i = 8 (i= 1,2) 1.8×10³

2 3 M_i = 9 (i= 1,2) 7.6×10³

2 3 Mi= 10 (i= 1,2) 3.2×10⁴

2 3 Mi= 11 (i= 1,2) 1.1×10⁵

2 3 M_i= 12 (i= 1,2) 5.8×10⁵

2 3 M_i= 13 (i= 1,2) 1.9×10⁶

2 3 Mi= 14 (i= 1,2) 1.0×10⁷

4 6 8 10 12 14

0.0 0.2 0.4 0.6 0.8 1.0

[]

×

図 7.7: 列数の増加に伴う計算時間の変化

表7.4は，クラスターの個数，各クラスターの行数に関しては固定し，各クラスターの列 数を1ずつ増やした場合の提案アルゴリズムの計算時間の増加具合を表したものである．図 7.7は横軸を各クラスターの列数M_i，縦軸を提案アルゴリズムの計算時間[ミリ秒]とした 時のグラフを表している．図7.7を見ると，アルゴリズムの計算時間は，各クラスターの列 数の増加に関して指数関数的に増加していることが分かる．このように計算時間が一気に増 加してしまう原因としては，提案アルゴリズムのstep.2におけるビリーフプロパゲーション の計算部分が挙げられる．

7.4提案アルゴリズムの計算時間に関するシミュレーション

図 7.8: クラスターから一次元鎖への変形

図7.8は，クラスター型模型に含まれるクラスターGiから一次元鎖Gi^′ への変形を表して いる．ビリーフプロパゲーションでは，一次元鎖Gi^′ の各頂点に関する周辺分布(6.6)を導 出している．また，この周辺分布(6.6)を計算するために必要な項は，(6.9), (6.10)式により 導出される．クラスターG_iの列数が増加するにつれて，一次元鎖G_i′に含まれる各頂点の 取りうる状態数は指数的に増加する．このとき，(6.9), (6.10)式の計算時間も指数的に増大 してしまう．このことから，図7.7のような結果が得られたと考えられる．

表7.5: 各クラスターの行数の増加に伴う計算時間の変化

クラスターの個数Z 各クラスターの行数 各クラスターの列数 計算時間[ミリ秒]

2 10 M_i = 4 (i= 1,2) 27

2 20 Mi = 4 (i= 1,2) 69

2 30 Mi = 4 (i= 1,2) 90

2 40 M_i = 4 (i= 1,2) 112

2 50 M_i = 4 (i= 1,2) 141

2 60 Mi = 4 (i= 1,2) 168

2 70 Mi = 4 (i= 1,2) 197

2 80 M_i = 4 (i= 1,2) 236

2 90 M_i = 4 (i= 1,2) 273

2 100 Mi = 4 (i= 1,2) 287

第 7章 数値実験

10 20 30 40 50 60 70 80 90 100 50

100 150 200 250 300

[]

図 7.9: 行数の増加に伴う計算時間の変化

表7.5はクラスターの個数，各クラスターの列数に関しては固定し，各クラスターの行数 を10ずつ増やした時の提案アルゴリズムの計算時間の増加具合を表したものである．図7.9 は横軸を各クラスターの行数，縦軸を提案アルゴリズムの計算時間[ミリ秒]とした場合のグ ラフである．図7.9を見ると，アルゴリズムの計算時間は，各クラスターの行数に関して線 形関数的に増加していることが分かる．表7.4と比較して，表7.5ではクラスター型模型の サイズ（素子数）がかなり大きいものをシミュレーションの対象としている．しかし，アル ゴリズムの計算時間は表7.4と比べて，かなり少ない時間で済んでおり，計算機側での演算 の限界（オーバーフロー）などが生じない限り，行数をさらに大きくとっても現実的な時間 でアルゴリズムが終了すると考えられる．

表7.6: クラスター数の増加に伴う計算時間の変化

クラスターの個数Z 各クラスターの行数 各クラスターの列数 計算時間[ミリ秒]

10 10 Mi= 2 (1≤i≤10) 7

20 10 M_i= 2 (1≤i≤20) 16

30 10 M_i= 2 (1≤i≤30) 24

40 10 Mi= 2 (1≤i≤40) 35

50 10 Mi= 2 (1≤i≤50) 51

60 10 M_i= 2 (1≤i≤60) 64

70 10 M_i= 2 (1≤i≤70) 68

80 10 Mi= 2 (1≤i≤80) 84

90 10 Mi= 2 (1≤i≤90) 89

100 10 M_i = 2 (1≤i≤100) 94

7.4提案アルゴリズムの計算時間に関するシミュレーション

0 10 20 30 40 50 60 70 80 90 100 20

40 60 80

[]

図 7.10: クラスター数の増加に伴う計算時間を表したグラフ

表7.6は各クラスターの行数・列数に関しては固定し，クラスターの個数を10ずつ増や した時の提案アルゴリズムの計算時間の増加具合を表したものである．図7.10は横軸をク ラスターの個数，縦軸を提案アルゴリズムの計算時間[ミリ秒]とした場合のグラフである．

図7.10を見ると，提案アルゴリズムの計算時間は，クラスターの個数に関して線形関数的 に増加していることがわかる．従って，元のボルツマンマシンのサイズが非常に大きい場合 に，クラスターの個数が非常に多いクラスター型模型を用いて提案アルゴリズムを実行する ことで，近似分布を現実的な計算時間で導出することが可能となる．