Memory Networks

1. Introduction

오늘날 대부분의 모델들은 장기 기억요소(Long-term memory component)를 전혀 사용하지 못하고 있다. QA task를 생각해 보자면, RNN을 사용해 구현하는 경우, 일련의 사실이나 이야기를 들은 후, 하나의 hidden vector로 표현한다. 이러한 저장은 일반적으로 너무 작고, 과거의 사실들을 정확하게 기억한만큼 충분하지 못하다.

본 모델에서는 이러한 문제를 해결하기 위해 메모리 네트워크 라는 새로운 모델 구조를 제안한다. 핵심 아이디어는 추론을 위해 ML의 학습전략을 메모리 요소와 결합하는 것이다.

2. Memory networks

2.1 구성요소

$m$ : memory

I : (input feature map) 입력된 input을 feature representation으로 변환

$x$ → $I(x)$

G : (generalization) 메모리를 업데이트(왜 generalization이냐? → 향후 과정에서 메모리를 압축하고, 일반화하는 과정이 있기 때문)

$m_i=G(m_i,I(x),m), ∀i.$

O : (output feature map) 새 입력과 기존의 메모리들을 통해 feature representation space 상에서의 출력 생성

$o = O(I(x),m)$

R : (response) 출력을 원하는 형식으로 변환.

$r=R(o)$

train 단계에서는 I~R 을 거치며 메모리 업데이트, test 단계에서는 I~R을 거치는것은 같으나 파라미터를 고정 하는 방식으로 진행,

메모리 네트워크는 General 한 모델로, 원하는 사용 용도에 따라 I,G,O,R에 다양한 모델을 적용할 수 있다.

I component

I 단계에서는 텍스트 입력에 대한 pre-processing 과정을 진행한다. input을 feature representation으로 변환하는 과저이 링러난다.

G component

메모리를 저장하는 방식에 따라 다양한 구현을 시도해 볼 수 있을 것이다. 가장 단순하게는 모든 입력을 메모리에 순차적으로 저장하는 것이지만, 해당 논문에서는 hash function과 같은 방법들을 통해 많은 데이터에서 효율적으로 원하는 메모리에 접근하는 과정을 설계했다.

메모리가 가득 찼을때 forgetting 과정또한 필요할 수 있음을 언급했지만, 저자들은 이에대해 구현까지는 진행하지 않았다.

O,R components

O 에서는 일반적으로 메모리에서 응답을 읽어내고, 추론하는 과정을 진행한다. R 에서는 이렇게 얻은 feature vector representation으로 부터 최종적인 결과물을 생성하게 된다.

해당 논문에서 중점으로 살펴본 QA task의 경우는 O에서 관련된 메모리들(relevant memories)을 찾고, R에서는 결과로 내어줄 실제 문장(혹은 단어)를 생성한다.

3 A MemNN IMPLEMENTATION FOR TEXT

저자들은 메모리 네트워크의 구현 중 component들이 neural network인 것을 Memory neural network(memNN) 이라 이름붙이고, 입출력으로 텍스트를 가지는 qa task에 대해 구현했다.

3.1 Basic model(for qa)

해당 모델에서 I 모듈은 입력 텍스트(사실을 담은 기술 또는 시스템에게 물어볼 문장)를 받는다.

텍스트는 original form으로 memory에 저장된다. 즉 G 모듈은 새로운 데이터를 저장하는데에만 쓰이고 기존 데이터는 업데이트 되지 않는다.

추론은 O,R 모듈에서 진행된다.

O 모듈은 given query x 로 부터 k 개의 supporting 메모리를 찾는다. (해당 구현에서 k=2로 설정되었다.)

k=1 일때 highest vector o_1은 다음과 같이 찾아진다.($s_O$는 $x$ 와 $m_i$ 간의 scoring function)

$$o_{1}=O_{1}(x, \mathbf{m})=\underset{i=1, \ldots, N}{\arg \max } s_{O}\left(x, \mathbf{m}_{i}\right)$$

k=2 일때 o_1과 x로 부터 O_2를 찾는다.

$$o_{2}=O_{2}(x, \mathbf{m})=\underset{i=1, \ldots, N}{\arg \max } s_{O}\left(\left[x, \mathbf{m}_{o_{1}}\right], \mathbf{m}_{i}\right)$$

R에서 받을 final output $o = [x,m_{o_1},m_{o_2}]$ ( barket is list)

R에서는 real text response $r$을 만들어야 한다. 가장 간단하게는 입력된 input 중 하나를 출력하면 되겠지만, 진정한 문장 생성을 위해 이번 구현에서는 RNN 모델을 사용하였다.

후의 실험에서는 text응답을 단일단어로 제한하는 접근에 대해서도 논의 할 것이다.

$$r=\operatorname{argmax}_{w \in W} s_{R}\left(\left[x, \mathbf{m}_{o_{1}}, \mathbf{m}_{o_{2}}\right], w\right)$$

$W$는 set of words in the dictionary, $S_R$은 score function

experiment 1

위 구현에서 scoring function $s_O, s_R$은 embedding 에서 비슷한 표현을 뽑는데, 같은 form을 사용했다.

$$s(x, y)=\Phi_{x}(x)^{\top} U^{\top} U \Phi_{y}(y)$$

U는 n*D matrix, D : num of features, n : embedding dim

$Φx , Φy$는 x,y를 D-dim feature space에 mapping 하는 함수

가장 간단한 feature space는 bag of word 표현이며, 해당 논문에서는 $D=3|W|$로 설정하였다.

즉, dictionary 내 단어들은 세가지 표현을 가진다. one for Φy(.) and two for Φx(.)

논문에서는 o,r의 scoring을 위해 같은 D를 사용했으며, 각각 다른 weight matrix $U_o, U_R$을 사용했다.

Training

training 은 fully supervised로 이뤄졌다. 즉 이상적인 input ,response, supporting sentence(O의 결과) 가 정해져 있음.(test set 에선 input만) =

training 에서는 margin ranking loss 와 SGD 가 사용되었다.

$x$와 그에 대한 true response $r$, supporting sentence $m_{o1},m_{o2}$를 알고 있을때 Loss func은 다음과 같다.

$$\begin{gathered}\sum_{\bar{f} \neq \mathbf{m}_{o_{1}}} \max \left(0, \gamma-s_{O}\left(x, \mathbf{m}_{o_{1}}\right)+s_{O}(x, \bar{f})\right)+ \\\left.\left.\sum_{\bar{f}^{\prime} \neq \mathbf{m}_{o_{2}}} \max \left(0, \gamma-s_{O}\left(\left[x, \mathbf{m}_{o_{1}}\right], \mathbf{m}_{o_{2}}\right]\right)+s_{O}\left(\left[x, \mathbf{m}_{o_{1}}\right], \bar{f}^{\prime}\right]\right)\right)+ \\\left.\sum_{\bar{r} \neq r} \max \left(0, \gamma-s_{R}\left(\left[x, \mathbf{m}_{o_{1}}, \mathbf{m}_{o_{2}}\right], r\right)+s_{R}\left(\left[x, \mathbf{m}_{o_{1}}, \mathbf{m}_{o_{2}}\right], \bar{r}\right]\right)\right)\end{gathered}$$

$\bar{f},\bar{{f}^\prime},\bar{r}$은 올바른 레이블이 아닌 것들의 집합, $\gamma$는 margin, 즉, 실제답과의 차이가 각각 모두γγ 이상 만큼 나는것을 목표로 한다.

맨 윗줄을 살펴보자면, $m_o1$이 true label 일때, f_bar 가 known label 이 아닌것들에 대해 summation gamma - true + 다른거 와 0중에 큰걸 더해서 이를 minimize 한다.

https://lsjsj92.tistory.com/391

R에서 RNN을 사용하는경우에는 last term을 log likelihood 로 바꿔 사용한다.

3.2 WORD SEQUENCES AS INPUT

Input이 문장수준으로 끊어지는게 아니라 단어 수준으로 끊어지는 경우가 있다. 단어가 쭉 이어져서 도착하고 statement 와 question으로 나뉘지 않았다면, 이를 나눌 방법을 생각해야 한다.

해단 논문에서는 segmemtation function을 정의했다. 해당 함수는 input으로 아직 segmented 되지 않은 단어를 입력으로 받고, 중단점을 찾는다. segmenter 가 실행되고, 문장이 분할되면, 이를 메모리에 쓰고 계속해서 진행한다.

$$\operatorname{seg}(c)=W_{s e g}^{\top} U_{S} \Phi_{\operatorname{seg}}(c)$$

이때 W는 embedding space에서 linear classifier로의 기능을 하는 벡터이고, c는 bag of words 로 표현된 input, seg(c)가 margin $γ$보다 크면 segment로 간주됨. MemNN에서는 fully supervised setting을 가정하기 때문에, segmenter 에도 같은 상황속에 학습이 진행됨.

segmenter 에 대한 training creteria 는 다음과 같이 적용될 수 있다.

F are all known supporting segments in the labeled training set, and F¯ are all other segments in the training set.

3.3 EFFICIENT MEMORY VIA HASHING

vanila 구현에서는 모든 메모리셋을 탐색하게 되는데(그것도 두번이나) 이는 많은 computational cost를 소모, hashing function을 통해 이를 늘렸다.

$I(x)$에서 나온 bucket에 해당하는 메모리만 scoring 함으로서, cost를 절약한다.

해싱은 두가지 방법을 시도했는데

1. word dictionary를 사용한 것

   사전에 있는 단어 수만큼 버킷을 구성, 주어진 문장에 대해 문장 내 단어들에 해당하는 모든 버킷에 해시.

2. word embedding 을 clustering 해서 사용한 것

   embeddign matrix $U_O$를 학습시킨 후 k-means를 통해 word vectors $(U_O)_i$를 클러스터해서 K개의 버켓을 만듦, 그 후 주어진 문장에 주어진 문장에 대해 문장 내 단어들에 해당하는 모든 버킷에 해시.

1 번 방법은 새로들어온 input에 대해 $I(x)$의 단어중 적어도 하나 이상의 단어가 memory 에 있어야 점수를 매길 수 있지만, 2번의 경우 이러한 현상이 완화되고, 유사한 memory 에도 점수가 매겨질 수 있다.

3.4 MODELING WRITE TIME

vanila 구현에서는 각 메모리들이 입력된 시점을 고려하지 않음. 이는 순서를 가지는 질문에 답할때(물건을 여러명이 사용한다던지, 물건의 위치가 여러 단계로 이동된다던지) 중요한 문제임.

가장 간단한 해결책은 memory j 에 기록될때(rewriting이 없다는 전재하에) j를 extra feature로 $Φx ,Φy$에 추가하는 것 이지만, 이는 절대적인 시간값을 저장하게 된다.

QA task에서는 상대적인 시간 관계가 더 중요하기 때문에, 다음과 같은 scoring function을 통한 상대적 시간값을 반영하였다.

$$s_O(x, y)=\Phi_{x}(x)^{\top} U^{\top} U \Phi_{y}(y)$$

$$s_{O_{t}}\left(x, y, y^{\prime}\right)=\Phi_{x}(x)^{\top} U_{O_{t}}^{\top} U_{O_{t}}\left(\Phi_{y}(y)-\Phi_{y}\left(y^{\prime}\right)+\Phi_{t}\left(x, y, y^{\prime}\right)\right)$$

x 가 새로운 입력 일때 $Φ_t(x, y, y′)$ 는 3차원의 binary feature를 가지는데, x-y, x-y’.y-y’ 간의 선후관계에 대한 표현을 가진다.

(정말 모르겠음)

3.5 MODELING PREVIOUSLY UNSEEN WORDS

한번도 나오지 않은 unseen word 에 대해서 이상적인 해결은 language model을 사용하여 주변 단어를 통해 현재 단어를 예측해야 한다.

해당 논문에서는 이러한 아이디어를 $S_O, S_R$을 약간 변경함으로서 도입했는데,

input 단어의 앞, 뒤에 있는 단어를 bag of word로 input feature representation에 포함시킨다. 따라서 feature representation은 3W 에서 5W 로 확장되는데, 이를 잘 학습시키기 위해서 dropout 을 사용했다.

3.6 EXACT MATCHES AND UNSEEN WORDS

임베딩 모델은 낮은 차원때문에, 정확하게 단어를 일치시킬 수 없다. 해결책은 x,y 쌍에 점수를 매기는 것.

x,y 의 “bag of words” matching score를 n-dimentional embedding space에 더한다.

(이것도 다시한번 봐야할 듯)

4. RELATED WORK

Pass!

5 EXPERIMENTS

5.1 LARGE-SCALE QA

• Dataset
  • from Paralex - Paraphrase-driven learning for open question answering(Fader et al., 2013)
    1. (subject, relation,object) triple 로 구성되는 14M 개 statement 가 존재
    2. ex)(milne, authored , winnie-the-pooh) 및 (sheep, be-afraid-of, wolf)
    3. triple 에서 생성되는 question과 이를 paraphrased 한 35M 개의 question-triple pair로 구성
    4. ex) “Who wrote the Winnie the Pooh books?” and “Who is poohs creator?”

• Baseline
  • Paraphrase-driven learning for open question answering In ACL, pp. 1608–1618, 2013(Fader et al., 2013)
  • Question answering with subgraph embeddings. In Proc. EMNLP, 2014a.(Bordes,et al)

• Metric
  • F1 score

• Result

  

  • (table1)bow feature 를 사용한 MemNN 에서 가장 좋은 성능을 보임
  • (table2) word hash 적용한 경우 speedup 이 1000배 일어났지만, 큰 성능차이, K=1000 인 클러스터 hash 적용한 경우 80배의 성능향상을 보이면서 적은 성능차를 보였음

5.2 SIMULATED WORLD QA

• Dataset simulation
  • simple simulation of 4 characters, 3 objects and 5 rooms– with characters moving around, picking up and dropping objects.
  • 자동화된 문법을 통해 질문과 레이블을 생성
  • 7K statement, 3K question
  • 질의의 Complexity(difficulty)는 Limit 이라는 변수에 의해서 설정되었다.
  • Limit은 질문하고자 하는 entity가 마지막으로 언급된 과거의 시간단계에 제한을 둔다.ex) limit=5 → 과거 1~5 step 에서 무작위로 sentence 선택
  • 이렇게 선택된 senstence 가 인물만을 언급하고 있다면, 인물만에 관한 질문, object 를 언급하고 있다면 object에 관련된 질문을 생성했다.
  • Answer는 simple word 와 간단한 문법으로 만들어진 문장 두가지 종류가 있다.
  • 또한 actor-based question 에 before을 사용하지 않은(더 긴 requirement가 필요)가장 simple 한 버전의 질문또한 준비했다.

• Baseline
  • RNN, LSTM

• Result

  

  • diffuculty 1+easy task 에서는 RNN,LSTM도 잘 작동했지만, difficulty 가 높으면 long memory를 활용하지 못해 성능이 매우 떨어지는 것을 볼 수 있었음
  • actor 나 actor+object task 에서 k=1 이고 time 정보가 없는 경우에는 RNN 계열의 모델에 비해 낮은 성능을 보였다. 이는 RNN, LSTM이 모델 구조상 sequential data를 처리할 수 있기 때문으로 생각됨.
  • time 정보를 사용한 이후에는 극적인 성능향상을 보였으며, k=2 인 경우 훨씬 좋은 성능을 보였다.

5.2.1 QA WITH PREVIOUSLY UNSEEN WORDS

3.5,3.6의 unseen staragy를 적용한 경우의 실험, 해당 실험에서는 Bilbo, Frodo, Sauron, Gollum, Shire 및 Mount-Doom 등의 단어를 dictionary 에 넣지 않은 상태로 실험을 진행했지만, test 단계에서 적절한 정답을 제공했다.

이런 전략을 사용하지 않은 학습에서는 이러한 task들은 완전히 실패했다.

5.3 COMBINING SIMULATED DATA AND LARGE-SCALE QA

5.1 과 5.2에서 각각 두 모델을 largescale QA 와 simulation QA 에 대해 훈련하고, 이를 앙상블하였다. 이에 시스템은 general 한 knolege question 과 simulation 상황에 대한 질문 모두에 대답할 수 있었다. 단 이후 올바른 combining의 방법에 관한건 future work로 남긴다.

Uploaded by N2T