JPS60222968A - 高速連想記憶装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔発明の利用分野〕 本発明は複数の要素からなる記憶項目を多数記憶して、
検索キーによシ想起する記憶装置に係ゎシ、特に検索キ
ーにあいまい性が含まれる場合の検索に好適な連想記憶
装置に関する。

〔発明の背景〕

人間の情報処理ではあいまいな言葉や部分的情報を手が
かルにして、関連する情報をすばやく想起している。こ
の機能は連想記憶と呼ばれている。

この連想記憶をモデル化したものに相関行列型の連想記
憶モデルがある（連想記憶＋　Ｋｏ）１０ｎｅｒ　、す
イエンス社、昭和５５年１０月ン。

このモデルでは、ベクトルとして表わされるデータｙｒ
　”’　（Ｙ　ＩＩ　Ｉ　Ｙ　１２’　＋…、ｙＩＮ）
′をＬヶ記憶している状態Ｍを次のように相関行列で表
わす。

Ｍ−Ｙ＋　Ｖｔ　＋Ｖ２　Ｖ２　＋・・・＋　ｙＬ　ｙ
Ｌ　−（１）ただし、「′」はベクトルもしくは行列の
転置を表わす。記憶Ｍが与えられているとき、想起人力
Ｘ”　（Ｘ＋　、Ｎ２　、　・・・、ＸＮ　）が与えら
れると、想起出力Ｙは次式で与えられる。

もし入力Ｘがｙ２以外の記憶デ〜りと直交しているなら
ば、（２）式の第２項は零になるので出力はｙｒに比例
したものになり、その比例係数は（ｙ、ｘ）で与えられ
る。

入力Ｘはｙ、に正確に等しくなくても良い。Ｘとしてｙ
７の部分を入力することによｌ／、全体を想起すること
もできる。

しかしながらこの方式ては行列Ｍの要素の数は、Ｎ２　
（Ｎはベクトルの要素数）ケ必要である。行列Ｍの対称
性を考慮してもＮ２／２ケ必要である。

例えば記憶ｌ−夕として、画素数が１０’７２ケ程度の
比較的小さい画像データを考えると、これを記憶する相
関行列の要素数は１０Ｂ／４も必要となり、実用上の大
きな障害となる。

この方式のもう１つの問題点は、（２）式の想起におい
て人力Ｘがｙ、以外と直交していることを仮定している
ことに係わる。通常のデータでは、このような直交性が
成シ立たない場合があるので、直交化の手法を前処理と
して導入する必要がある。

引例１には、画像ｌ−夕を記憶する場合に関しデータＶ
ｌに対しラプラシアン演算ｖ２を行うことによって直交
性が向上することを示している。その結果を記憶項目と
してα）式を演算すれば（功弐による想起の後、Ｙに対
しラグラジアン演算の逆変換することによって想起が可
能となる。しかしながらこの逆変換には、収束計算が必
要となり、その処理時間と処理に要するメモリの容量は
膨大なものとなシ、実用上問題が多い。

〔発明の目的〕

本発明の目的はかかる従来の連想記憶方式の欠点に鑑み
、メモリ効率が良く、高速の記憶と想起が可能な連想記
憶装置を提供することにある。

〔発明の概要〕

本発明では各記憶項目の要素間の高次変化分をめ、この
変化分を表わすベクトルを複数のグループに分け、各グ
ループの自己相関と相互相関を記憶し、想起出力に２次
微分の逆変換を施すことにより高速の記憶・想起とメモ
リ効率の向上を実現する。

〔発明の実施例〕

本発明の具体的実施例を説明する前に、本発明の基本的
原理を説明する。本発明ではベクトルデータ３／ｌを次
のようＶＣｐ個の部分ベクトルに分割するＯ ＩＶ　Ｉ　＝　（Ｖ　ｔ（１）’　Ｖ　ｔ（２）′・・
・ｙＸ（ｐ）’）’　・・・（３）Ｉ＝１，２．・・・ ただし ’ｉｔ　（Ｊ）−□’ＩＩＡ　Ｙ！＋ｔやｈ・・・Ｙ　
Ｋ、ｉ）’　・・・（４）ｔ　＝　−（ｊ　−１）＋１ 本発明では、（１）の相関行列のかわシに次の行列（以
下では部分相関行列と呼ぶ）Ｍｐを記憶モデ・・・・・
・・・・・・・・・・（５）ここで なお、一般にＹ　＋５　＝　Ｙ’ｔ　＋が成シ立つので
、実際にはＹ　目（ム＝１〜ｐ）　Ｙｔ＊＋＊凰（ｉ＝
１〜ｐ−１）だけを記憶すれば良い。

想起人力Ｘが与えられたときにはＸと記憶行列１■、と
の乗算をおこなう。ここでは入力Ｘとして、ある記憶項
目ｙ２の部分ベクトルｙ　、　（ｑ）を与えた場合の想
起を例にとって説明する。

Ｙ＝Ｍ、ｘ　・・・曲間（７） −Ｍ、（０・・・・・・Ｏｙ、（ｑ）’ｏ・・・・・・
０）′　・・・（７１）・・・・・・・・・・・・（８
） 各記憶項目間で対応する部分ベクトルが直交していると
すると、すなわち （ｉ＝１．２．・・・ｔｐ） とすると（８）式の第１項の係数１ｙ、（ｑ）１２は１
になり、第２項は零になる。従って部分ベクトルｙ　、
　（ｑ）から、その両隣りのｙｒ　（ｑ−１）、ｙｒ　
（Ｑ＋１）が想起される。

この想起出力を入力として想起を繰返すことによって有
限回の後には記憶項目ｙｒ全全体想起できる。もし入力
Ｘが始めから記憶項目ｙ、の情報をよシ多く含んでいれ
ば、この繰返しの回数は少なくてすむ。

ここでは部分ベクトルが直交するという仮定のもとに説
明をおこなったが、この仮定はどのような場合でも成立
するわけではない。例えば画像情報を各画素の階調デー
タからなるベクトルとして表わした場合を考えよう。各
画像を表わすベクトルＶｔ　ｌ　Ｖ２１・・・をそれぞ
れ部分ベクトルに分割しても（９）式は必ずしも成シ立
たない。我々は多くの実験から、このような場合には、
ベクトルの２次微分をとる手法が有効であるとの知見を
得た。

すなわち、記憶項目ｙｌが（ｙｌｌ　＋　ＹＩＮ　＋・
・・）’ｔ＊）’と表わされるとき、その２次微分を次
式で計算する。

Ｍｌ　−”（）’ｕ　Ｙｒｚ　””／嵩Ｊ’　−（□０
）ただし ・・・・・・・・・・・・（１１） この２次微分によシ部分ベクトルの表わす画像の微細構
造が抽出できる。（３）式では入力情報ｙ１を部分ベク
トルに分割したが、そのかわυにこのｙＩ２ゝを部分ベ
クトルに分割する。すなわち、ｙｒ　＝（ｙ　夏（１）
　’ｙ　Ｉ（ｐ）　”　ン′　（３勺＋２１　’　、、
。

従って（６）式では、２次微分部分ベクトルの相関をめ
る。すなわち 想起人力ｘ−（ｘｌ、Ｘ２　・・・、Ｘ％）に対しても
同じように先ず要素間の２次微分×（２）をめ、それを
複数の部分ベクトルに分割する。

Ｘ（２１＝（Ｘ（１）’＋２）Ｘ（２）’＋２）　）（
（ｐｊ（２）、）′・・・（１２）ここで、ｘ（Ｊ　）
′”　（ｘ）２１　ｘ”ｔ　、、、　ＸＦ’　）　’　
・（＋３）ｔ＝　−（ｊ　−１）＋１　・・・（１４）
・・・・・・・・・（１６） このＸ　を（７）式のＸの所に代入することにょシ得ら
れる出力をＹ″）とすると、Ｙ　は次のように表わされ
る。

・・・・・・・・・・・・（１７） 次に、ｙ　”＝：　（ｙ　、＋２１・・・ｙＮ（２１）
’の逆変換を次式によっておこなう。

Ｙ−（ｙＩ　・・・）’Ｎ）’　・・・（１９）ここで ・・・・・・・・・・・・（２０） ・・・・・・・・・・・・（２１） ・・・・・・・・・・・・（２２） 以下、本発明の実施例を第１図を用いて説明する。第１
図において１は記憶部、２は想起部、１０１は微分演算
部、１０２は部分ベクトル演算部、１０３は相関演算部
、１０４は記憶行列演算部、１０５はメモリ、２０１は
微分演算部、２０２は部分ベクトル演算部、２０３は想
起演算部、２０４は逆変換演算部を示している。

ここでは入力データとして、第２図に示した６４Ｘ６４
の画素から構成される画像を対象に説明をおこなう。各
画素は２５６階調の明るさによって表わされ、その明る
さによってＯから２５５までの値をもつ。

ここでは、入力データとして画像をと９あげ、説明をお
こなう。通常の画像処理と同様に画像をカメラもしくは
専用スキャナーで読みとり、その出力を本発明の記憶部
１に入力する。この入力が６４Ｘ６４画素で構成され、
各画素はＯから２５５までの明るさのいずれかの値をも
つ場合を考える。

第２図は、この入力データの１例（ＣＲ，Ｔ上に表示し
たもの）である。

微分演算部１０１は、画像に対応する入力データＶｌが
与えられると、（１０）　、　（１１）式により、２次
微分部分ベクトルｙ、　（２）を計算する。

部分ベクトル演算部１０１は、微分演算部１０１から２
次微分ベクトルｙｔ　を与えられると、これを部分画像
に分割する。ここでは第３図のように２次微分した画像
を１６ケの部分に分割するものとする。このときｙＸ（
２）は次のように表わされる。

Ｖ　１”　−’　（Ｖ　１”（１）’・・・ｙＩ”　（
１６）　’　）　’　・・・（２４）ここで、Ｖ！”（
Ｑ）は第９部分にある全ての画素の２次微分値を構成要
素とする部分ベクトルを表わす。

相関演算部１０３は、この２次微分部分ベクトルｙ　＊
（ｊ戸（ｊ＝ｘ　〜１６　）を入力し、次の相関行列を
計算する。

・・・・・・・・・・・・（２５） Ｙｌｌ、を自己相関行列、ＹＱ＋Ｑ’ｈｌを相互相関行
列と呼ぶ。

記憶行列演算部１０４は、これらの相関行列を入力する
とともに、メモリ１０５から自己相関行列和Ｙ　ｑ　＋
　ｑ　（Ｑ　＝　１〜１６）、相互相関行列和Ｙｑ、、
。１（ｑ＝１〜１５）をとシ出し、それらを次式によっ
て更新する。

・・・・・・・・・・・・（２６） 上式かられかるようにＹ、、、Ｙ、、、。ｌはそれまで
に入力された多数の画像の自己相関行列の和と相互相関
行列の和を表わしている。すなわち、（５）。

（６）式に対応する記憶モデルを１つの画像入力毎に更
新する方法を示している。

記憶行列演算部１０４は、この結果をメモリ１０５へ格
納する。このように記憶部ｌは、新しく記憶入力が与え
られるたびに、相関行列和を更新していくことによシ、
多数の画像情報を記憶することができる。

次に、この記憶情報を検索するために、入力Ｘが想起部
２に与えられたとする。

微分演算部２０１は、この入力ベクトルＸを入力し、次
式によシ２２次微ベクトル×（２）（ｊ＝１〜１６）を
める。

ｘ　＝　（ｘ　ｆ”　Ｘ　２”　−Ｘ　Ｎ”　）’（２
） ただし ・・・・・・・・・・・・（２７） 部分ベクトル演算部２０２はこの２次微分ベクトルｘ０
を取り込んで、これを１６ケの部分ベクトルに分割する
。すなわち、 ｘ”−（ｘ（ｉ声”ｘ（２）”’−ｘ　（１６）””）
’　・（２８）（２） 想起演算部２０２は、ｘ（１）、　・　Ｘ（１６戸を入
力すると同時に、メモリからＹ、、（ｑ＝１〜１６）と
Ｙｌｌ、や＋（Ｑ＝１〜１５）をとシ出し、（１８）式
の演算をおこなう。この結果得られる想起出力Ｙ　（２
ゝ＝（ｙ（１）　Ｙ（ｘ６戸′）′を、想起演算部２０
２の＋２１’、、。

入力とみなし、想起演算を繰返す。すなわちこのｙ（１
）　、・・・ｙ　（１ゲ２）を（１８）式のｘ　（ｔ）
　”ゝ、・・・、Ｘ（１６戸（２） に代入し、新しいｙ（１）　Ｌ２）、・・・Ｖ　（１６
）”’ｔ−決定する。

このような想起処理を有限回繰返す。繰返し回数は、最
大でも１６に設定すれば良い。この繰返しによって最終
的に得られたデータ列をｙＩ　＋　ｙＮ　！・・・、ｙ
Ｎと表わす。

逆変換部２０４は、想起演算部２０４で有限回の繰返し
計算後に得られた結果ｙｌ、ｙ２．・・・、ｙＮを入力
し、（１９）〜（２２）の逆変換演算をおこなう。

この逆変換演算の結果Ｙが我々に必要な想起データであ
る。

本実施例による想起の例を第４図に示す。第４図（ａ）
は第２図の画像の一部分で、これを想起のための入力と
する。第４図（ｂ）は想起の結果を表わしている。第４
図（ｂ）と第２図を比較すると、部分情報（第４図（ａ
））を手がかりに、全体の想起が正しくおこなわれてい
ることがわかる。なお第４図（ｂ）は想起の繰返し演算
が１０回目のときの結果である。

次に本発明を用いた場合の記憶容量削減効果について説
明する。本発明ではＮヶの要素からなる記憶ベクトルを
ｐヶの部分ベクトルに分割し、その自己相関行列、相互
相関行列を記憶する。相互相関行列の要素の数は（Ｎ／
ｐ）２ケ、自己相関性列の要素の数は行列の対象性を考
慮すると２（Ｎ／ｐ）２ケで与えられる。自己相関行列
の数はｐ　：ｒ１相互相関行列の数はｐ−１ケあるので
記憶すべき要素の数Ｅ、は次式で与えられる。

ｐ−２Ｎ２ ｐ”　２ 一方、従来の相関行列型連想記憶では、行列の対称性を
考慮してもＮ２／２ケの要素を記憶する必要がある。

第５図に記憶データの要素の数Ｎと分割数ｐを変えた場
合の記憶要素の数値を示す。Ｎおよびｐが大になる程、
本発明の効果が大きいことが明らかであろう。同時の黒
丸は、前述の実施例の場合の記憶要素の数を示している
。

分割数ｐが大きくなる程、記憶容量は少なくてすむが、
ｐを大きくしすぎると部分ベクトルの要素数が少なくな
り、クロストークが大きくなる。

ｐをどのように選ぶかは、対象とする記憶データの種類
によって異なる。

前述の実施例では自己相関の他に隣り合う部分ベクトル
間の相関を考えたが、もう少し広い範囲の相関を考える
こともできる。例えば（２５）式の相関計算に加えて、
次の相関行列も計算して記憶する方法も考えられる。

Ｙｑ＋ｑ＋ｘ＝ｙｔ（ψ’　Ｙｌ（ｑ＋２）　（ｑ＝１
〜１４）このとき記憶行列では（２６）式の他に次の行
列を計算して記憶する。

ｙｑ＋ｑ＋ｚ←Ｙ＋１１４＋２＋Ｙｑ＋ｑ＋ｚこの分記
憶容量は増加するが、想起過程では１回の想起で広い範
囲のデータが想起されるので繰返し数が少なくてすむ。

次に記憶情報を互いに歯丈化するために従来のラプラシ
アンを用いた場合と、２次微分を用いた　１・場合に関
し、想“起過程の演算量について比較する。

第６図は、演算時間の大部分を占める乗算の数を比較し
たものである。ただし乗算回数の見積シは次式によって
おこなった。

ラグラジアン使用の場合：　２Ｎ２＋Ｎ本図からラプラ
シアン方式に比べ、２次微分方式で画像を１６分割した
場合の方が乗算演算量が１／１０以下になっていること
がわかる。

本発明の実施例によれば、連想記憶に必要なメモリ容量
と計算時間を大幅に低減できる。

以上の実施例では画像の記憶について述べたが多数の要
素からなる記憶項目の記憶想起に対し、本発明を適用で
きることは明らかである。

【図面の簡単な説明】

第１図は本発明の実施例、第２図は記憶入力する２値画
像の例（写真）、第３図は記憶入力画像の分割方法の例
、第４図は想起入力と繰返し想起の例（写真）、第５図
は本発明になる記憶容量の圧縮効果の説明図、第６図は
本発明による高速化の効果の説明図。 １・・・記憶部、２・・・想起部、１０１・・・微分演
算部、１０２・・・部分ベクトル演算部、１０３・・・
相関演算部、１０４・・・記憶行列演算部、１０５・・
・メモリ、２０１・・・微分演算部、２０２・・・部分
ベクトル演算部、２０３・・・想起演算部、２０４・・
・逆変換演算部。 第　１　図 第　乙　し４ 手続補正書（万民） 特許庁長官志賀　学殿 事件の表示 昭和５９年持重１′１願第　７８５１３　−３・発明の
名称 畠速連想記憶装置 補正をする者 事件との関係　特許出願人 名　称（５１１１１株式会（」　口　立　製　イ乍　所
代　理　人 居　館〒Ｉ（Ｘｌｌ東京都千代田区丸の内−丁目５番１
号株式会社　日立製作所内　電話東＋；’、２１２−１
１１Ｈ大代］、）補正の内容 別紙のとおシ １、明細書の図面の簡単な説明を次のとおり訂正する。 「第１図は本発明の実施例を示す図、第２図は記憶入力
画像の分割方法の例を示す図、第３図は本発明に係る記
憶容量の圧縮効果の説明図、第４図は本発明による高速
化の効果の説明図。 ■・・・記憶部、２・・・想起部、１０１・・・微分演
算部、１０２・・・部分ベクトル演算部、１０３・・・
相関演算部、１０４・・・記憶行列演算部、１０５・・
・メモリ、２０１・・・微分演算部、２０２・・・部分
ベクトル演算部、２０３・・・想起演算部、２０４・・
・逆変換演算部。」 及び第客□よ付（１）２お、訂正す、。 以上 茅Ｚ　区 芽３　目 ｏ　ｔｏＪｓｘｔｏＪ１０’ へ・フトＪし学索季ξＮ 茅　４．口 手続補正書（自発） 特許庁長官志賀　学　殿 事件の表示 昭４４１５９年１”Ｉ’ｊ’ｌ願第　７８５１３　号発
明の名称 高速連想記憶装置 補正をする者 事件との関係　特許出願人 名　イｈ（ｆｉｌｎｌ　＋３、入会（１日　立　製　イ
乍　１す１代　月１　人 居　酪〒Ｉ（Ｘ’ｌｌ東京都千代田区丸の内−丁目５番
１号（１）明細書の発明の詳細な説明の欄 補正の内容 別紙のとおり １、明細書の発明の詳細な説明を次のとおり訂正する。 ■第１２頁第５行「第２図に示した」を削除する。 ■同頁第７行「おこなう」を「おこなう（図示せず）」
に訂正する。 ■同頁第１６行ないし第１７行を削除する。 ■第１３頁第３行「第３図」を「第２図ｊに訂正する。 ■第１６頁第９行ないし第１６行を削除する。 ■第１７頁第１３行［第５図）を「第３図ｊに訂正する
。 ■第１８頁第１８行「第６図」を「第４図」に訂正する
。 以上

Claims (1)

1. 【特許請求の範囲】 １、複数の要素からなる記憶項目を多数記憶するデータ
   ベースにおいて、新規に記憶項目が与えられたとき該記
   憶項目の要素間の高次変化分を抽出する微分演算部と、
   該微分演算部によって微分処理した要素を複数のグルー
   プに分割する部分ベクトル演算部と該部分ベクトル演算
   部でめた各グループの自己相関行列と相互相関行列を計
   算する相関演算部と、該相関演算部の出力である自己相
   関および相互相関行列を、それ以前の記憶過程で計算し
   て記憶している自己相関行列の和および相互相関行列の
   和に加えて、新しく記憶する記憶部とからなることを特
   徴とするデータベース用の高速連想記憶装置。 ２、特許請求の範囲第１項においてデータベースに対し
   情報検索用の入力が与えられたとき、検索用入力を構成
   する要素間の高次変化分を抽出する微分演算部と、該微
   分演算部の演算で微分処理した要素を複数グループに分
   割する部分ベクトル演算部と、該部分ベクトル演算部で
   めた各グループを該記憶部に記憶した自己相関行列の和
   および相互相関行列の和に乗する想起演算部と、想起演
   算部の出力に差分演算の逆演算を施して、それを置。