Chapter 7. Content-Addressable Memory 知的ロボティクス Chapter 7. Content-Addressable Memory 知的計測クラスタ 聴覚メディア研究室 傳田　遊亀

Chapter 7. 7.1 INTRODUCTION 7.2 HOPFIELD MEMORIES 7.3 KANERVA MEMORIES 7.2.1 Stability 7.2.2 Lyapunov Stability Example: CAM for a Small Phone Book 7.3 KANERVA MEMORIES 7.3.1 Implementation 7.3.2 Performance of Kanerva Memories 7.3.3 Implementation of Kanerva Memories 7.4 RADIAL BASIS FUNCTIONS 7.5 KALMAN FILTERING

7.1 INTRODUCTION CAM（Content-Addressble Memory） データの情報の一部から関連した情報を連想して探す Hopfield memories （Autoassociative） Kanerva memories （Heteroassociative）

7.1 INTRODUCTION 抽象化されたneuron（unit）がmemory bitを表現 Unitは-1 or 1の離散状態を取る Weightは0～1の実数

7.2 HOPFIELD MEMORIES Autoassociative memories Weightを のように対称になるように制限することでweightの決定が比較的容易 2層型ネットワーク ある時刻の出力は次の状態の入力になる Attractors（安定した平衡点）だけが存在する W X h

7.2 HOPFIELD MEMORIES Hebbian Rule Weightのupdate rule Q個のパターン に適したweightを決定する Weightのupdate rule

7.2.1 Stability Weightの対称性から状態ベクトルはhypercube（n次元の立方体）の頂点の状態のみを取る

7.2.1 Stability Hopfield memoriesがある状態ベクトル で安定 パターンの各成分が1 or-1に等確率で分布・独立である場合noise成分の分散は独立項の分散の和

7.2.1 Stability Noise成分の分散は の二項分布 Bit error rateはNから∞までの積分で求められる Unit数が減るとBit error rateは低下

7.2.1 Stability 平均と標準偏差の比 は SNR（Signal to Noise Ratio）とみなせる Bit errorの起きる確率 N=1000, Q=100の場合 CAMの記憶容量は非常に小さい

7.2.2 Lyapunov Stability Lyapunov関数V(x)を用いてシステムの安定性を調べる V(x)が単調減少する場合CAMは常にlocal minimaになる V(x)をシステムのエネルギーとみなせる

Exmaple: CAM for a Small Phone Book 各エントリー25文字の電話帳 1文字/5bit, ±1 で符号化 ex.) a・・・(-1,-1,-1,-1,1)，b・・・(-1,-1,-1,1,-1) 各エントリーは125次元のベクトルで表現 John Stewart Denker 8128 Lawrence David Jackel 7773 Richard Edwin Howard 5952 Wayne P. Hubbard 7707 Brian W. Straughn 3126 John Henry Scofield 8109

Exmaple: CAM for a Small Phone Book Memoryパターンに近い状態で始まった場合 Vは単調減少 格納パターンに十分近づく Time　　　 Energy　　 CAM state 0.0 john s 0.2 -0.0784 john sdewirubneoimv 8109 0.4 -0.8426 john sdewirtbnenimv 8129 0.6 -0.8451 0.8 -0.8581 john sdewirt nenkmv 8128 1.0 -0.9099 john sdewart denker 1.2 -0.9824 john stewart denker

Exmaple: CAM for a Small Phone Book Memoryパターンから遠い状態で始まった場合 Vは単調減少するがattractorは偽のlocal minimaになる Time　　　 Energy　　 CAM state 0.0 garbage 0.2 -0.00244 garbagee lafj naabd 5173 0.4 -0.6280 garbaged derjd naabd 7173 0.6 -0.6904 garbaged derjd nadbd 0.8 gasbafed derjd nadbd 1.0 -0.7595 gasbafed derjd naabd 1.2 -0.7709 fasjebad derjd naabd 1.4 -0.8276 1.6 -0.8282 fasjeb d derjd naabd

7.3 KANERVAMEMORIES Heteroassociative Q個のメモリ（n bit/memory）がアドレス空間（　　　　 ）に無相関に分布 M個のペア(x, y)， x・・・アドレス, y ・・・データ ベクトルを格納するためにはxのHamming距離Dの全ベクトルdにyを加える ベクトルを修正するためにはdの総和を閾値処理する

7.3 KANERVAMEMORIES 単一のベクトルのみを処理する場合は正確にベクトルを修正できる 一般的には複数のベクトルを扱う必要がある 総和をとることで影響が出る可能性がある データの各成分が±1の範囲でランダムに分布すると仮定 他のベクトルの要素は打ち消しあう 入力ベクトルが主な成分を占める

7.3 KANERVAMEMORIES Conventional computer memory 密なアドレス空間（ex. 20 bit）を持ち全てのアドレス（　 ）を使用

7.3 KANERVAMEMORIES 疎なアドレス空間（ex. 1000 bit)を持つ 　　　 ものアドレスを確保することは物理的に不可能

7.3.1 Implementation M×N（M << アドレスス空間）のアドレス行列AとM×Nデータ行列C xから距離D内のベクトルをセレクトベクトルsを用いて表す 実際に使用するベクトルの割合をpとすると使用されるベクトル数はpMになる

7.3.1 Implementation ベクトルを格納することでデータを得られる Kanerva memoriesは3層ネットワークで表現できる A X d C h Y

7.3.2 Performance of Kanerva Memories 第一項の期待値・・・　　　　　　　　　　　　　　　　 ベクトルをランダムに選んだ場合のnoise成分　　　　　　　　　　　　　　　　

7.3.2 Performance of Kanerva Memories 第1項の期待値・・・pM 第2項の期待値・・・pM 合計確率はポアソン分布でモデル化可能

7.3.2 Performance of Kanerva Memories 合計の各要素が独立であると仮定した場合正規分布で近似できる Error rate・・・ Example of a Kanerva Memory Q=100，p=0.1，M=10,000

7.3.3 Implementation of Kanerva Memories Content-addressable性 16×16 = 256次元のベクトル

7.3.3 Implementation of Kanerva Memories Heteroassociative性

7.4 RADIAL BASIS FUNCTIONS Kanerva memoriesではアドレス空間を大きく取ることでerror rateを下げることが可能 データがアドレスの関数として表現可能 内挿によって関数近似を行う Radial basis functionsを使用

7.5 KALMAN FILTERING Kanerva memoriesの拡張 Noiseの影響を抑える コストを最小化する