1 知的ロボティクス 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.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 2 7.1 INTRODUCTION CAM(Content-Addressble Memory) データの情報の一部から関連した情報を連想して探す Hopfield memories (Autoassociative) Kanerva memories (Heteroassociative) 3 7.1 INTRODUCTION 4 抽象化されたneuron(unit)がmemory bitを表現 Unitは-1 or 1の離散状態を取る Weightは0~1の実数 xj wij N xi xi (t 1) wij x j (t ) j 1 1 g ( x) 1 x0 otherwise. N xi (t 1) g wij x j (t ) j 1 7.2 HOPFIELD MEMORIES 5 Autoassociative memories Weightを wij wjiのように対称になるように制限すること でweightの決定が比較的容易 2層型ネットワーク ある時刻の出力は次の状態の入力になる Attractors(安定した平衡点)だけが存在する X h W X 7.2 HOPFIELD MEMORIES Hebbian Rule p x , p 1,, Q に適したweightを決定する Q個のパターン Q wij x x p 1 p p i j Q W x (x ) p p T p 1 Weightのupdate rule new ij w n 1 old 1 new new wij xi x j n n 6 7.2.1 Stability Weightの対称性から状態ベクトルはhypercube(n次元 の立方体)の頂点の状態のみを取る 7 7.2.1 Stability 8 p x Hopfield memoriesがある状態ベクトル で安定 N p p xi g wij x j g (hip ) j 1 x p g (Wx p ) N Q hip x iq x jq xi p Nx ip x iq x jq x jp j 1 q 1 j q p Nx x p i q p q i x x Nx q j p j p i j x p x q x jp x jq 0 j パターンの各成分が1 or-1に等確率で分布・独立であ る場合noise成分の分散は独立項の分散の和 2 (Q 1) N QN ∵Q 1 7.2.1 Stability 9 2 , QN の二項分布 Noise成分の分散は Bit error rateはNから∞までの積分で求められる パターン数が増えるとBit error rateは増加 Unit数が減るとBit error rateは低下 N Q 1.4 Q N 7.2.1 Stability 平均と標準偏差の比 N QN N Q は SNR(Signal to Noise Ratio)とみなせる Bit errorの起きる確率 ( ) ( N Q ) N=1000, Q=100の場合 ( N Q ) ( 1000100) ( 10) CAMの記憶容量は非常に小さい 0.138 N 10 7.2.2 Lyapunov Stability 11 Lyapunov関数V(x)を用いてシステムの安定性を調べる V(x)が単調減少する場合CAMは常にlocal minimaになる V(x)をシステムのエネルギーとみなせる 1 V wij xi x j C wij xi x j xi xi 1 2 i j i j V V ( xi) V ( xi ) 0 xi xi V 0 xi xi V wij xix j wij xi x j i j i j 2 wij xi x j 2 xi wij xi 2wii 0 i j j 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 12 Exmaple: CAM for a Small Phone Book Memoryパターンに近い状態で始まった場合 Vは単調減少 格納パターンに十分近づく CAM state Time Energy 0.0 0.2 0.4 0.6 0.0 -0.0784 -0.8426 -0.8451 john s john sdewirubneoimv 8109 john sdewirtbnenimv 8129 john sdewirtbnenimv 8129 0.8 1.0 1.2 -0.8581 -0.9099 -0.9824 john sdewirt nenkmv john sdewart denker john stewart denker 8128 8128 8128 13 Exmaple: CAM for a Small Phone Book Memoryパターンから遠い状態で始まった場合 Vは単調減少するがattractorは偽のlocal minimaになる Time Energy CAM state 0.0 0.2 0.4 0.6 0.8 1.0 1.2 1.4 1.6 0.0 -0.00244 -0.6280 -0.6904 -0.6904 -0.7595 -0.7709 -0.8276 -0.8282 garbage garbagee lafj naabd garbaged derjd naabd garbaged derjd nadbd gasbafed derjd nadbd gasbafed derjd naabd fasjebad derjd naabd fasjebad derjd naabd fasjeb d derjd naabd 5173 7173 7173 7173 7173 7173 7173 7173 14 7.3 KANERVAMEMORIES Heteroassociative Q個のメモリ(n bit/memory)がアドレス空間( Q 2n ) に無相関に分布 M個のペア(x, y), x・・・アドレス, y ・・・データ ベクトルを格納するためにはxのHamming距離Dの全ベクト ルdにyを加える ベクトルを修正するためにはdの総和を閾値処理する yi g di 15 7.3 KANERVAMEMORIES 単一のベクトルのみを処理する場合は正確にベクトル を修正できる 一般的には複数のベクトルを扱う必要がある 総和をとることで影響が出る可能性がある データの各成分が±1の範囲でランダムに分布すると 仮定 他のベクトルの要素は打ち消しあう 入力ベクトルが主な成分を占める 16 7.3 KANERVAMEMORIES Conventional computer memory 密なアドレス空間(ex. 20 bit)を持ち全てのアドレス( 2 20)を 使用 17 7.3 KANERVAMEMORIES 疎なアドレス空間(ex. 1000 bit)を持つ 21000 ものアドレスを確保することは物理的に不可能 18 7.3.1 Implementation 19 M×N(M << アドレスス空間)のアドレス行列AとM×N データ行列C xから距離D内のベクトルをセレクトベクトルsを用いて表す 1 D ( x) 0 s D (Ax ) xD otherwise. 実際に使用するベクトルの割合をpとすると使用されるベクト ル数はpMになる Q C s k 1 k y k T 7.3.1 Implementation ベクトルを格納することでデータを得られる h sT C y g (h) 20 1 g i ( x) 1 xi 0 otherwise. Kanerva memoriesは3層ネットワークで表現できる Y h C d A X 7.3.2 Performance of Kanerva Memories s a D ( Ax a ) aT h s C s a s y Q a ak k T y (s s ) s a a a k 1 第一項の期待値・・・ s s y Q a 21 a k k T k 1, k a pMy a p 1 ベクトルをランダムに選んだ場合のnoise成分 kT Lk s s k Q a a a k kT k var yi ( s s ) yi s s k 1, k a Q k k k var(La ) var yi s s var(La ) (Q 1) var(y1 L1 ) k 1,k a 7.3.2 Performance of Kanerva Memories var(La ) (Q 1) var(y1L1 ) 第1項の期待値・・・pM 第2項の期待値・・・pM E y L E y1L1 var(L1 ) E( L1 )2 2 2 1 1 2 合計確率はポアソン分布でモデル化可能 x pM p( L) pM e L! , pM 2 2 pM (Q 1)p 2 M ( p 2 M ) 2 pM 1 pQ(1 p 2 M ) Q 1 22 7.3.2 Performance of Kanerva Memories 合計の各要素が独立であると仮定した場合正規分布 で近似できる Error rate・・・ ( ) Example of a Kanerva Memory Q=100,p=0.1,M=10,000 100 100 (1 1(1 1)) 10 3 ( ) (5.77) 23 7.3.3 Implementation of Kanerva Memories Content-addressable性 16×16 = 256次元のベクトル 24 7.3.3 Implementation of Kanerva Memories Heteroassociative性 25 7.4 RADIAL BASIS FUNCTIONS Kanerva memoriesではアドレス空間を大きく取ることで error rateを下げることが可能 データがアドレスの関数として表現可能 内挿によって関数近似を行う Radial basis functionsを使用 h( x) g( x xi ) h( x) ( x xi ) 2 2 i2 f ( x) ci hi ( xi ) i 26 7.5 KALMAN FILTERING Kanerva memoriesの拡張 Noiseの影響を抑える コストを最小化する E (W,x ) W x E x 2 x I Wx 2 2 k1 x k 2W T ( I Wx ) μ x xv xˆ k1 x k2W T ( I Wx) PR1 ( x xˆ ) P・・・( x xˆ )の共分散行列 27
© Copyright 2024 ExpyDoc