社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,INFORMATION AND COMMUNICATION ENGINEERS

信学技報
TECHNICAL REPORT OF IEICE.

ローカルブリッジを持つスモールワールドホップフィールド
ネットワークによる連想記憶
志摩 知哉†

生田 智敬†

上手洋子†

西尾 芳文†† 徳島大学工学部〒 770-8506 徳島県徳島市南常三島町 2-1
E-mail: †{s-tomoya,ikuta,uwate,nishio}@ee.tokushima-u.ac.jp
あらまし 人工ニューラルネットワークの 1 つにホップフィールドネットワーク（Hopfield Neural Network：HNN）がある．このネットワークは一般的に，自己結合を持たない相互結合型，つまり結合が密なネットワークとして知られている．しかし，ネットワークを実装する上では結合が密なため高いコストが生じてしまう．一方，Boland らが開発したスモールワールドホップフィールドニューラルネットワーク（Small World HNN：SWHNN）は，社会ネットワー
クに見られるスモールワールド現象を HNN に応用したもので，結合が疎なネットワークである．しかし，結合が疎であるため，例えば連想記憶の場合，記憶容量が減少してしまうなどの問題が生じる．本研究では，この連想記憶の問題を解決するために，新たな社会ネットワークの現象の 1 つであるローカルブリッジの特性を持つスモールワール
ドホップフィールドニューラルネットワーク（SWHNN with Local Bridge：SWHNN-LB）を提案し，性能を調査した．
キーワード ホップフィールドニューラルネットワーク，連想記憶，社会ネットワーク，スモールワールドネットワー
ク，ローカルブリッジ

Tomoya SHIMA† , Chihiro IKUTA† , Yoko UWATE† , and Yoshifumi NISHIO†† Dept. of Electrical and Electronic Engineering, Tokushima University,
2-1 Minamijosanjima, Tokushima, 770-8506 Japan
E-mail: †{s-tomoya,ikuta,uwate,nishio}@ee.tokushima-u.ac.jp
Abstract The Hopfield Neural Network (HNN) is one of artificial neural networks. Every neurons in the HNN is connectedto each other neuron in the network with no self-connection. Namely, the HNN has full connectivity. On the other hand, few
years ago, Boland et al propsed the Small World Hopfield Neural Network (SWHNN) which has sparse connectivity. The
SWHNN is combined small world phenomenon in social network with the HNN. However the storage ability of the SWHNN
decreases for associative memory because the SWHNN has sparse connectivity. In this study, we propose the SWHNN withcharacteristic of Local Bridge (SWHNN-LB) using a phenomenon in the social network, which is “local bridge”. And we
explore performance of the SWHNN-LB using the associative memory.
Key words Hopfield Neural Network, Associative Memory, Social Network, Small World Network, Local Bridge

1. ま え が きワーク（Small World HNN：SWHNN） [2] は，社会ネットワー
ク（友人，親類，取引，ウェブリンク，疾病の伝染（疫学），航多くの研究者が今日まで人工ニューラルネットワークについ空路といった 1 つ以上の関係により結びつけられた社会的な構て研究を行ってきた．ホップフィールドニューラルネットワーク

造ネットワーク）に見られるスモールワールド現象 [4] を HNN（Hopfield Neural Network:HNN）はそのうちの 1 つであり [1]，に応用した疎な結合を持つネットワークで，効果的な連想記憶

本研究では HNN のアプリケーションの 1 つである連想記憶にを行うことを示した．これはスモールワールドネットワークのついて研究を行う．このネットワークは一般的に，自己結合を1：クラスタリング性が高い・2：平均経路長が短い，という 2 つ持たない相互結合型，つまり結合が密なネットワークとしての特性によってもたらされ [3]，この 2 つの特性によりスモール知られている．しかし，ネットワークを実装する上では結合がワールドネットワークは疎な結合でありながら，高効率の情報密な場合，高いコストが生じてしまう．数年前，Boland らが伝達を行うことができる．ここで 1 つ目の特性は，レギュラー開発したスモールワールドホップフィールドニューラルネットネットワークの導入によってもたらされ，2 つ目の特性は，レ—1—

ギュラーネットワークのパスよりも少し長い「ショートカット」し機能が働いており，この局所的なブリッジのことをローカルと呼ばれるパスの導入によってもたらされる．しかし SWHNNブリッジと呼ぶ．社会ネットワークの中で，ローカルブリッジは疎な結合であることから，記憶容量の低下の問題が生じてしは情報伝達をする上で，とても重要な役割を持っている．なぜまう．私達は，スモールワールド現象のように実際の社会ネッなら，ローカルブリッジはある 2 点間を結ぶより短い経路を，トワークの情報伝達において，重要な役割をしている現象を応より多く作ることができるからである．このことから，ネット用すれば，記憶容量の低下の問題が解決できるのではないかとワーク内で最短経路と 2 番目に短い経路の差が大きければ大考えた．そこで今回の研究では，社会ネットワークに見られるきいほど，情報伝達の観点において，そのローカルブリッジが現象の 1 つとして「ローカルブリッジ」 [5] を用い，SWHNNネットワークに与える影響が大きくなる．これらのローカルブのショートカットに応用して研究を行った．

リッジの特性は，スモールワールドネットワークで平均経路長まずローカルブリッジを説明する前に，「ブリッジ」についてを短くする役割を持つショートカットと類似していると私達は説明する必要がある．ブリッジとは，ネットワーク中の２点間考えた．そして，ショートカットがもしローカルブリッジと同を結ぶ唯一の経路となるような線のことである．このブリッジじ特性を持っているのであれば，それぞれのショートカットにを簡潔に表したものを下の図 1 に示す．ここで，A-B 間のブよってネットワークに与える影響が変化してくる．

リッジは A の接触相手のうちの 1 人から B の接触相手のなかそ こ で 本 研 究 で は ，ロ ー カ ル ブ リッジ を も つ SWHNNの 1 人に情報や影響力が伝わる唯一の経路を提供しており，こ（SWHNN with Local Bridge: SWHNN-LB）を提案し，ローカのことを「橋渡し機能」と呼ぶ．

ルブリッジがネットワークに与える影響を調査する．提案手法では，ローカルブリッジの考え方を元に，SWHNN のショー
トカットそれぞれに「重要度」という値を定義し，この「重要度」に従ってショートカットの結合荷重のパラメータを調整することで「重要度」の違うショートカットがネットワークにどのような影響を及ぼすかを調査する．比較の対象として，今回は従来の SWHNN の他に，スケールフリーホップフィールドニューラルネットワーク（Scale Free HNN: SFHNN） [7] を用いた．ここで，本研究のスケールフリーは Barabasi and Albert(BA) model [6] を使用する．
図1

Example of the bridge.

図 1 のように小さいネットワークの場合はブリッジが発生する

2. スモールワールドホップフィールドニューラ
ルネットワーク

が，大きなネットワークにおいて特定の経路が 2 点間の唯一の本研究では，私達はスモールワールドネットワークの一次元経路であるということは，稀にしか起こらない．しかし，局所リングモデルを用いる．一次元リングモデルを作成するにあた的には橋渡し機能が働くことがある．その現象を図 2 に示す．

り，まず n 個のノードを持ち，各ノードが隣り合う k（以降この k を次数と呼ぶ．
）個のノードと結合しているレギュラーネットワークを用意する．ここで，k は n に比べ非常に小さい値でなければならない．次にネットワーク上の各ノードを p の確率で，別のノードにランダムにつなぎかえる．これらレギュラーネットワークと一次元リングモデルを表したものを図 3 に示す．
作成した一次元リングモデルがスモールワールドの特性を持っていることを示す指標として，平均経路長 L とクラスタリン
グ係数 C を用いる．ここで，L はネットワーク内のある全てのノード間の経路数の平均，C はあるーつのノードに着目したとき，そのリンク先のノード間にもリンクがある比率のことであ

図 2 ローカルブリッジの例．

る．L と C の式を以下に示す．
∑1
L=
di j ,N(N − 1)/2 i> j

(1)

図 2 では，A から B までの最短経路は A-B だが，2 番目に短い経路は A-C-D-E-F-G-H-I-J-K-L-B である．最短経路 A-B は

A と B を結ぶ唯一の経路では無いので，厳密にはブリッジとはCi =2Gi.
ki (ki − 1)

(2)言えない．しかし，経路 A-B は他の A と B を結ぶ経路と比べここで G は i と隣接しているノードの中に存在するリンクの数，るとはるかに短い．この場合，経路 A-B によって局所的に橋渡さらに図 3 はスモールワールド特性の L-C 特性を表している．

—2—

トワークに与える影響を調査するためである．結合荷重の調整の方法は，こちらで定義したパラメータ α を掛けてやることで行われる．この重要度の例を以下の図 5 に示す．

図3n = 16, k = 4 の時の一次元リングモデルの例．

10.8
図50.6

ショートカットの重要度決定の例．(n = 16 and k = 4).

0.40.200.0001

4. スケールフリーホップフィールドニューラル
ネットワークCL

本研究ではスケールフリーネットワークとして BA モデルの0.001

0.01

0.1

1

優先的選択手法を用いる．このネットワーク作成の方法は，まpず少ないノード数 m0 を用意し，これらのノードを用いて自己図 4 n = 200, k = 16 の時の L-C 特性．

結合を持たない相互結合ネットワークを作る．次に，m 本のエッジを持った新たな v 個のノードをタイムステップごとに加スモールワールドネットワークの条件は，L ∼ Lrandom and C ≫える．v 個のノードのエッジは，既存のノードを優先的に選択

Crandom なので，図 4 では，0.01 <=p<= 0.1 の時スモールワールするような確率で結合する．以下に優先的選択の式を表す．
∏kj(ki ) = n(1 <(3)= n),=i<Σ k

ドネットワークの特性を持っていると言える．これらの特性は
図 3 で見られるようなレギュラーネットワークの状態のパスよ

j=1 j

りも，少し長いパスの導入によってもたらされる．この少し長ここで，k はノード i の次数を表している．図 6 はスケールフ

いパスのことを「ショートカット」と言う．SWHNN は作成しリーネットワークのネットワーク構造と次数分布図を表していたスモールワールドネットワークに HNN の結合荷重の定義をる．

組み合わせたものである．

3. ローカルブリッジを持つスモールワールドホッ
プフィールドニューラルネットワーク

5. ホップフィールドニューラルネットワークによる連想記憶

社会ネットワークの現象の 1 つであるローカルブリッジを

HNN は J.J. Hopfield [1] が 1982 年に開発した人工ニューラル

SWHNN に応用する．ローカルブリッジの SWHNN への導入

ネットワークの 1 つであり，自己結合を持たない相互結合型の方法は，まず SWHNN のショートカットをローカルブリッジにニューラルネットワークである．以下に従来の HNN による連見立てる．そしてローカルブリッジの考え方を基に，各ショー想記憶の手順を示す．

トカットに「重要度」という値を定義する．この重要度には，[Step1 (HNN)]:HNN が結合荷重を決めることによってパターンショートカットで結ばれている 2 点のノードの 2 番目に短い経を記憶する．結合荷重は以下の式によって求められる．

路数の値を用いる．この重要度を決定する理由は，社会ネット
ワークにおいてのローカルブリッジは，最短経路と 2 番目に短い経路の差が大きければ大きいほどネットワークに与える情報

wi j ={(p) (p)1 ∑P
p=1 xi x j
P(i , j)0(i = j),(4)

伝達の影響が大きくなるという特性を持っており，本研究でこここで P はパターン数，w は結合荷重，そして x は記憶するパの重要度に基づいてショートカットの結合荷重を調整し，ネッターンを表す．

—3—図 7 記億パターンの例．

分布率(a)

0.40.35
0.30.25
0.20.15
0.10.05
06. 1 200 個のノードのネットワーク
200 個のノードを持ったネットワークの場合，シミュレーショ
ン結果を図 8 に示し，その時のパラメータを表 1 に示す．図 8は k を変化させた時の想起率を表しており，ネットワーク (a)は従来の SWHNN，ネットワーク (e) は SFHNN の結果である．
シミュレーション結果より，SFHNN は SWHNN より高い想起率を示していることがわかる．またネットワーク (b), (c), (d) は0510
次数1520

それぞれ重要度が 2, 3 または 4 のショートカットを調整した

SWHNN-LB の結果である．重要度が 2 または 3 の時，従来の(b)図 6 スケールフリーネットワークの例．(a) スケールフリーネットワーク構造．
(m0 = 3, m = 2 and n = 16). (b) 次数分布．(m0 = 4, m = 3 and n = 200).

SWHNN よりも良い結果を示している．特に重要度 3 の時は全体的に高い想起率を示している．

1れる．すなわちここではネットワークに入力パターンが与えら0.8

想起率[Step2 (HNN)]:ニューロンは新たなパターンによって初期化される．各ニューロンの内部状態は以下の式で決定される．

ui (t) =n∑

wi j (t)x j (t),(5)

(a)
(b)
(c)
(d)
(e)

0.6
0.4
0.2

j=10

ここで u はニューロンの内部状態， x は入力もしくは出力を表

010[Step3 (HNN)]: ニューロンの出力は線形関数により決められる．

3040{ 1,(ui (t) >= 0)−1,(ui (t) < 0).

図8k, p = 0.1 の時の各ネットワークの想起率.．(a) The SWHNN. (b) The
SWHNN-LB（重要度 = 2, α = 3.9）. (c) The SWHNN-LB（重要度 = 3 と以下に出力の決定式を示す．

xi (t + 1) =20kす．

α = 3.1）．(d) The SWHNN-LB （重要度 = 4 と α = 3.1. (e) The SFHNN.

(6)

表1

[Step4 (HNN)]:Step2 から Step3 の処理を繰り返すことによって入力パターンから記億パターンを想起する．

ネットワークパラメータ

Network typeα(a)The SWHNN-

6. シミュレーション結果(b)

The SWHNN-LB（重要度 = 2）

3.9

本研究では，連想記憶に SWHNN，SFHNN，そして SWHNN-(d) The SWHNN-LB（重要度 = 4） 3.1

LB の３つのネットワークを応用する．そして，次数 k を変化(c) The SWHNN-LB（重要度 = 3） 3.1(e)The SFHNN-させた時の各ネットワークの想起率を比較する．今回のシミュ
レーションでは，ノード数を 200 と 300 に設定する．記億パ

重要度 4 の場合は SWHNN-LB の特性は従来の SWHNN と比ターンにはランダムに作った 3 つの 2 値パターン，入力パターべて変化がない．私達は重要度の値が大きければ大きいほど，ンは 3 つのうち 1 つの記億パターンから 25% 離れたものを 1

ネットワークに与える影響は大きく想起率も高くなると予想つ用意した．パターンの例を図 7 に示す．なお今回は各ネットしていた．この想起率が変化しなかった原因を解明するため，ワークをランダムに 100 個作成し，想起した画像の誤差が 1%

SWHNN-LB 中に含まれているショートカットの重要度ごとの以内であれば想起成功とみなす．そしてネットワーク 100 個の比率を調査する．図 9 に SWHNN-LB 中ののショートカットの想起成功の平均を取り，それを想起率として定義する．

比率を示す．

—4—

10.80.8

想起率

比率10.60.40.40.20.20023(a)(b)0.6(c)(d)(e)0410

重要度2030k
図 11

図 9 重要度ごとのショートカットの比率 (k = 14)．

k, p = 0.1 の時の各ネットワークの想起率.．(a) The SWHNN. (b) The
SWHNN-LB（重要度 = 2, α = 3.2）. (c) The SWHNN-LB（重要度 = 3 とα = 2.8）．(d) The SWHNN-LB （重要度 = 4 と α = 3.2. (e) The SFHNN.

表 2 Netwrok parameter

図 8 と 9 より，k が 16 以上の場合，重要度 4 のショートカッNetwork typeトの数が無い，もしくは少なすぎることによってネットワークに影響を与えられていないことがわかる．しかし，k が 14 の場

α(a)The SWHNN-(b)The SWHNN-LB（重要度 = 2）

3.2合，重要度 4 のショートカットがネットワークに影響を与えてお(c) The SWHNN-LB（重要度 = 3） 2.8

り，これらのことから，ショートカットの重要度だけでは無く，(d) The SWHNN-LB（重要度 = 4） 3.2

各ショートカットの重要度がどれだけ含まれているかという比(e)The SFHNN-34率も考慮して，各ネットワークの性能を比較しなければならないことがわかった．そこで，私達は重要度 2，3，4 のショート1

カットの調整する数を統一し，その上でもう一度各ネットワー

0.8

トの重要度が大きいほど，ネットワークのパフォーマンスが向上していることがわかった．

比率

クの性能を比較した．結果の図 10 から，調整するショートカッ

0.6
0.40.200.82
想起率0.6

重要度0.4

T 重要度ごとのショートカットの比率 (k = 14)．

図 120.2234重要度
図 10想起率0

各重要度のショートカット数が 10 の時の SWHNN の性能．

0.60.50.40.30.20.102

図 11 はノードが 300 の場合の結果を示しており，その時の34

重要度

6. 2 300 個のノードのネットワーク
図 13

各重要度のショートカット数が 10 の時の SWHNN の性能．

パラメータを表 2 に示す．ノードが増加した場合，全ての場合で，SWHNN-LB が従来の SWHNN よりも全体的に良い結果を示していることがわかる．これは，重要度 4 のショートカット

7. ま と めの比率が増加したためだと考えられる．

本研究では，社会ネットワークの現象の一つであるローカルブリッジを応用した SWHNN-LB を提案し，連想記憶に応さらに, 重要度 2，3，4 のショートカットの調整する数を統一用した．シミュレーション結果より，従来の SWHNN よりもし，その上でもう一度各ネットワークの特性を比較したとこ

SWHNN-LB の方が良い性能を示した．またショートカットのろ，図 13 より，調整するショートカットの重要度が大きいほど，重要度の値が大きければ大きいほど，ネットワークに与えるネットワークのパフォーマンスが向上していることがわかる．

影響が大きいことがわかった．したがって，実際に社会ネットワークで起こっている現象が，人工ニューラルネットワークに—5—影響を与えることがわかった．
文

献[1] J.J. Hopfield, “Neural Networks and Physical Systems with Emergent Collective Computational Abilities,” Proceedings of the National Academy of Sciences of the United States of America, vol. 79,
pp. 2554-2558, 1982.
[2] J.W. Bohland and A.A. Minai, “Eﬃcient Associative Memory Using
Small-World Architecture,” Neurocomputing, vol. 38-40, pp. 489496, 2001.
[3] D. Watts and S. Strogatz, “Collective Dynamics of small-world’ networks,” Nature, vol. 393, pp. 440-442, 1998.
[4] S. Milgram, “The Small World Problem,” Psychology Today, vol. 2,pp. 60-67, 1967.
[5] S. Mark, “The Strength of Weak Ties”, Amerian Journal of Sociology, vol 78, pp 1360-1380, 1973.
[6] A.L. Barabsi and R. Albert, “Emergence of scaling in random networks,” Science, vol. 286, pp. 509-512, 1999.
[7] D. Stauﬀer, A. Aharony, L. Costa and J. Adler, “Eﬃcient Hopfield
Pattern Recognition on a Scale Free Neural Network,” The European
Physical Journal, no.32, pp. 395-399, 2003.

—6—