Chapter 7. Content-Addressable Memory

Presentation on theme: "Chapter 7. Content-Addressable Memory"— Presentation transcript:

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

2 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

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

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

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

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

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

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

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

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

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

12 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

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

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

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

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

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

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

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

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

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

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

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

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

25 7.3.3 Implementation of Kanerva Memories
Heteroassociative性

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

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