Self-Attentive Associative Memory

2021.09.27 랩미팅 준비 : Self-Attentive Associative Memory (ICML 2020)

 

[Introduction]

지금까지 external memory를 가지는 neural network는 memory를 1개(single)만 사용하였지만 이 논문에서는 2개의 메모리(item memory, relational memory)를 사용하여 represnetation 을 저장할 수 있다.

논문에서 새롭게 제안하는 모델은 SAM(Self-Attentive Associative Memory) operator 이다.

https://arxiv.org/pdf/2002.03519.pdf

[Methods]

1. Outer product attention (OPA)

'Attention is all you need' 의 dot product attention(DPA) 의 extension 버전이다. key-query-value를 똑같이 사용하고 outer porduct(외적)를 사용한다.

https://arxiv.org/pdf/2002.03519.pdf 식(1)

 

위의 식은 DPA로, · 는 dot product (내적)을 의미하고 S는 softmax 를 의미한다.

https://arxiv.org/pdf/2002.03519.pdf 식(2)

다음의 식은 이 논문에서 제안하는 OPA이다. 

⊙ 는 element-wise multiplication, ⊗ 은 outer product이고, F 는 element-wise tanh function을 의미한다.

OPA를 이용하여 item memory로부터 relational representation을 만들 수 있다.

 

DPA A°는 item을, OPA A⊗은 relational representation을 나타낸다.

OPA의 장점은 첫번째, DPA는 제공할 수 없는 higher-order representational capacity이고, 두번째는 contraction operation인 P (A⊗) 을 이용해 저장된 item을 검색할 수 있는 associative memory를 구현할 수 있다는 것이다. (즉, 함수 P를 이용하여 A⊗ 에서 A°를 추출하는 것)

이를 통해 item memorization과 relational binding을 둘다 얻을 수 있다.

https://arxiv.org/pdf/2002.03519.pdf 식(3)

위의 P를 정의하기 위해서 이 논문에서는 DPA의 S(softmax)를 linear transformation으로 가정한다.

 

자세한 증명은 Appendix에서..

 

2. Self-Attentive Associative Memory (SAM)

https://arxiv.org/pdf/2002.03519.pdf

 

SAM은 OPA를 이용해 item memory M로 부터 relational repesentation을 만들어내는 operator이다. M을 weight 와 layer norm을 이용해 query, key, value input로 만든다.

다음 아래의 식에서 SAMθ (M) 를 (query 와 value 사이의) relational represetation이라고 한다. 

https://arxiv.org/pdf/2002.03519.pdf 식(7), (8)

 

Item memory는 여러가지 방법으로 구현될 수 있는데, 이 논문에서는 associative memory를 사용하였다.

일반적인 attention에서 쓰인 dot product는 input matrix 조합에 대해 1개 relation에 대해 1 scalar를 내놓지만, OPA는 query와 value 사이에 대해 bit-level의 행렬을 relation으로 내놓을 수 있다.

 

* Associative memory란?

= 컴퓨터 에서의 Contents Address Memory 라고도 함 기억 장치에 있는 정보에 접근하기 위해 주소를 사용하는게 아니라 기억된 정보의 일부를 이용해 원하는 정보가 기억된 위치를 알아낸 후 그 위치에서 나머지 정보에 접근할 수 있는 장치 보통 컴퓨터의 캐시에서 이런 방법 사용 = 비 폰노이만 구조

이 개념과 헷갈리면 안된다고 한다..

 

EX )

• Hopfield Network(Hopfield) :
  (물리학적 스핀운동에서 착안) 에너지 개념을 신경망에 도입 → 자신을 제외한 모든 unit간에 양방향으로 상호연결된 네트워크, 최적화(optimization)문제에 많이 사용, SOM처럼 weight가 업데이트 되지않고 고정됨
  기억하려는 binary학습패턴을 이용해 가중치 행렬을 만든 후, inference 단계에서 새로운 입력패턴에 대해 학습한 패턴이 나올때 까지 계속 가중치를 곱한다 학습패턴이 나오면 알고리즘 종료? = 즉 입력 패턴에 대한 학습 패턴 연상을 반복한다

Hopfield Network is all you need 살펴보기

Hopfield Network is all you need 살펴보기

[머신러닝] - 홉필드 네트워크(Hopfield Network)

[머신러닝] - 홉필드 네트워크(Hopfield Network)

 

• Correlation Matrix Memory (Kohonen) :
  retrieval 메카니즘으로 recurrent network 사용

 

3. SAM based Two-Memory Model (STM)

2개의 메모리는 Mi item memory와 Mr relationship memory unit으로 이루어져 있고 t time-step input과 t-1 time-step memory를 이용해 output o_t 와 t time-step 의 memory를 생성한다.

 

input 을 x_t 라고 할 때

 

- Mi write

https://arxiv.org/pdf/2002.03519.pdf 식 (9)

f_1과 f_2는 feed forward network 이고 첫 번째 식을 이용해 input을 이용해 associative memory의 row를 write한다. (semantic이라고 할 수 있다.)

https://arxiv.org/pdf/2002.03519.pdf 식 (10)

메모리를 지우기 위해서는 LSTM을 참조하여 Forget gate인 F_t 와 Input gate I_t 를 이용하였다.

 

- Mr read

 relational memory를 이용해 이전 time-step 의 item을 다시 만들 수 있다.

https://arxiv.org/pdf/2002.03519.pdf 식 (11)

다음의 식 처럼 relational memory를 read 한다.

 

- Mi read / Mr write

 

https://arxiv.org/pdf/2002.03519.pdf 식 (12)

item memory 를 읽고 relational memory 를 write하기 위해 SAMθ 함수를 사용한다.

위의 식에서 item memory read 부분은 SAMθ 함수 괄호 안의 부분이다. 이때 사용하는 coefficient 인 알파는 blending hyper-parameter 라고 한다. SAMθ 은 input 으로 위의 relational read 벡터를 함께 사용한다. 이를 이용해 long-term 정보를 Mr에 저장할 수 있다.

 

 

- Mr transfer

Mr의 relational 정보를 Mi에 transfer 하는 단계이다.

https://arxiv.org/pdf/2002.03519.pdf 식 (13)

G_1은 feed-forward net 이고 V_f 는 input을 flatten하는 함수이다.

https://arxiv.org/pdf/2002.03519.pdf 식 (14)

 

[Experiments]

Task

1. Algorithmic synthetic tasks

NTM에서도 실험한 recall, associative recall, priority sort 등의 실험 task.

 

2. Geometric and graph reasoning

relational reasoning을 위해 geometry와 graph에서의 문제인 Traveling salesman Problem, Shortest path, Minimum spanning tree 등 을 실험 

 

3. Reinforcement learning 

Game pong을 이용하여 STM-augmentd agent 실험

 

4. Question Answering 

bAbI dataset 사용한다.

현재  Paper with Code 사이트의  sota 모델