INTRODUCTION:

우리가 접하는 많은 데이타들중에는 그래프 형태로 표현될 수 있는 데이타들이 있습니다. 예를들어 지하철 노선도나 chemical molecule, 혹은 data structure들이 될 수 있겠죠. 그런 데이타들에서 특정 정보를 뽑는다고 할때 (eg. 지하철 노선도에서의 최단거리), 데이타가 그래프화 되어 있다면 정보를 취득하기 훨씬 쉬울 것입니다. 이번에 소개시켜드리는 “Learning Graphical State Transitions” 논문은 ICLR 2017 oral paper에 선정되었으며, unstructured data로부터 그래프를 생성하여 inference하는 네트워크를 학습하는 방식을 제안합니다.

GOALS:

  • Unstructured data로부터 그래프를 생성하고 변형하는 방식을 학습
  • 생성된 그래프로부터 inference하는 방식을 학습

DATASET:

이 논문에서 주로 다룬 데이타셋은 20종류의 text-based question-answering problem으로 이루어진 bAbI 데이타셋입니다.

Screen Shot 2017-05-22 at 7.12.05 PM

각각의 데이타 샘플은 위의 예시처럼 n개의 문장과 m개의 질문으로 이루어져 있고, 이러한 데이타로부터 답을 추론해야합니다. 대부분의 question-answering 시스템들은 위와 같은 인풋을 RNN을 통하여 feature vector representation을 구한 후 답을 도출하게 되는데 저런 인풋을 그래프형식으로 나타낼 수 있다면 (eg. milk, John, garden이 graph vertex들이고 각각이 edge로 이루어져 있는 형태) 답을 얻는 것이 trivial한 작업이 될수도 있습니다.

GRAPH:

먼저 그래프를 정의하겠습니다. 그래프 G = (V, C) 는 vertex 셋 V와 connectivity matrix C로 구성됩니다. V에 속한 vertex v는 annotation vector x_v \in \mathbb{R}^N where\sum^N_{j=1} x_{v,j}=1, hidden state vector h_v \in \mathbb{R}^D, 그리고 strength s_v \in [0,1]로 이루어져 있습니다. x_{v,j}vN개의 vertex type중 j번째 vertex type일 확률을 나타낸다고 볼 수 있고 s_vv가 존재하여할 강도를 나타내는 수라고 생각할 수 있습니다. Connectivity matrix C \in \mathbb{R}^{|V|\times|V|\times Y} where c_{i,j,k} \in [0,1] 는 모든 vertex들의 어떻게 Y개의 type의 edge들로 이루어져있는지 강도를 나타냅니다. 쉬운 이해를 위해 그림과 함께 보겠습니다.

Screen Shot 2017-05-22 at 7.36.29 PM

그래프에서 vertex 1과 2를 보시기 바랍니다. 1은 파란색으로 표현된 첫번째 노드 타입으로, 2는 빨간색으로 표현된 세번째 노드 타입으로 annotation vector에 기록되어있습니다. 1과 2 모두 존재하여야 한다고 strength에 1로 나타내어지고 있고 (이와 반면에 3은 존재할 필요가 없기에 strength가 0으로 나타내어져있습니다), 각각의 상태를 나타내는 hidden state vector를 가지고 있습니다. 1과 2의 커넥션은 source 1로부터 destination 2를 향하는 파란색 타입의 directed edge로 Connectivity matrix에 나타나 있습니다 (이와 반면에 1에서 2로 향하는 빨간색 타입의 edge는 존재할 필요가 없다는 0으로 나타내어져 있습니다).

GRAPH TRANSFORMATION OPERATIONS:

자, 그럼 이제 인풋 데이타로 부터 이런 그래프를 변형 또는 생성하는 operation들을 정의하겠습니다 (인풋 데이타의 vector representation은 잠시 후에 설명하도록 하겠습니다).

1. Aggregation

Screen Shot 2017-05-22 at 8.02.02 PM.png

그래프 G의 representation vector를 뱉어내주는 operation입니다.

Screen Shot 2017-05-23 at 11.59.43 AM.png

ij는 attention과 vertex representation을 만들어내는 1-layer feed-forward neural network들 입니다. 위의 식이 나타내는 것처럼 그래프의 representation은 모든 vertex들을 attention-style mechanism을 통하여 합친 vector입니다.

2. Vertex addition

Screen Shot 2017-05-22 at 7.54.19 PM

Vertex addition은 주어진 input vector a \in \mathbb{R}^{\alpha}와 현재 그래프 G로 부터 새로운 vertex들을 만들어내는 operation입니다. 이 논문에서는 2-layer GRU로 구성되어 미리 정해진 maximum number of vertices까지 recurrent하게 vertex들을 생산해냅니다(필요없는 vertex일경우 s_v=0이 됩니다).

3. Vertex State Update

Screen Shot 2017-05-23 at 1.28.58 PM.png

Screen Shot 2017-05-23 at 1.29.10 PM

주어진 input vector a \in \mathbb{R}^{\alpha}에 기반해 vertex들의 state를 업데이트하는 operation입니다. a를 보고 업데이트될 필요가 있는 vertex들의 hidden state를 적절히 바꿔줍니다.

4. Edge Update

Screen Shot 2017-05-23 at 1.33.01 PM.png

Screen Shot 2017-05-23 at 1.33.15 PM.png

주어진 input vector a \in \mathbb{R}^{\alpha}에 기반해 각각의 vertex 쌍들의 연결을 적절하게 업데이트 시키는 operation입니다. f_{set}f_{reset}은 2-layer feed-forward neural network들로 구성되어있습니다. 이 둘은 각각 [0,1]을 아웃풋하게 되는데, maximum과 minimum일때 케이스만 보자면, 만약 f_{set}f_{reset}이 둘다 0을 아웃풋 한다면 edge가 바뀌지 않을것이고, 둘다 1을 아웃풋 한다면 edge의 state가 toggle될 것 입니다.

5. Propagation

Screen Shot 2017-05-23 at 1.42.52 PM.png

Screen Shot 2017-05-23 at 1.43.18 PM.png

Vertex들 사이의 정보교류를 시키는 operation입니다. f^{fwd}, f^{bwd}는 각각의 edge type마다 정의되어있는 1-layer feed-forward neural network이고 이들은 각 vertex들의 annotation vector와 hidden state를 인풋으로 받아 이웃 vertex들에게 전송해야 하는 정보를 아웃풋해줍니다. 이 정보들은 각 vertex들의 strength와 connectivity strength에 따라 취합이 되고 이웃 vertex들로부터 받은 정보는 GRU와 비슷한 업데이트 공식에 따라 각 노드의 hidden state에 반영됩니다.

ALGORITHM:

위에 설명드린 다섯가지 operation들을 통해 그래프를 만들게 되는데요,  그럼 이제 그래프를 형성하는 알고리즘에 대해 말해보겠습니다. 알고리즘에 소개된 operation의 순서는 풀고자 하는 문제에 따라 달라질 수 있으며 이 포스트에서는 question-answering에 적합한 알고리즘을 소개드리겠습니다.

Screen Shot 2017-05-22 at 7.12.05 PM다시한번 위의 예시를 봅시다. 모델에 K개의 인풋 문장이 들어간다고 할때, 여기서는 1번부터 8번까지의 문장들이 인풋으로 들어갑니다. 처음에 그래프 G는 empty인 상태이고, 각각의 문장은 RNN을 통하여 하나의 input vector a \in \mathbb{R}^{\alpha}로 표현이 되고 K번만큼의 다음 동작을 수행합니다:

  1. Vertex state update with G, a_k
  2. Propagation with G
  3. Aggregation with G -> h^{add}_G
  4. Vertex addition with G, a_k, h^{add}_G
  5. Edge update with G, a_k

위의 반복동작들이 다 실행이 된 후에는 그래프가 만들어져있을 것입니다.

Screen Shot 2017-05-23 at 5.02.28 PM.png

예를들어, 5번째 문장 후에는 위와 같은 그래프가 만들어질 수 있겠죠. 이런 그래프로 부터 question에 대한 답을 추론해야 하는데 question 역시 문장을 embedding한 RNN으로부터 question vector q로 표현됩니다. q를 사용해 다음과 같은 operation으로 답을 추론하게 됩니다:

  1. Vertex state update with G, q
  2. Propagation with G
  3. Aggregation with  G -> h^{answer}_G
  4. return f_{output}(h^{answer}_G)

여기서 f_{output} 또한 neural network (feed-forward or recurrent) 입니다.

WEAKNESSES:

  1. 지금까지 말씀드린 알고리즘을 학습시킬때 매번 그래프를 변형시킬때마다 supervision을 주었는데요, 이 점은 이 논문의 가장 큰 약점이지만 그래프 형식을 만들어내는 end-to-end 방식을 처음 제안한 논문이기 때문에 future work에서는 supervision없이 그래프를 만들어낼 수 있는 테크닉이 나올 수 있을것으로 기대됩니다. Supervision은 새로운 인풋 문장이 들어올 때마다 그래프가 만들어야하는 정답지를 같이 주는식으로 제공되었습니다. 예를 들어 n 번째 문장후 vertex 3과 edge 3->5가 생겨야 한다면 모델이 만들어내는 현재 그래프와 정답지 그래프의 차를 줄여주는 loss를 주고 모델을 학습시킨 것이죠. 그리고 현재 그래프는 정답지 그래프와 교체된 후 다음문장을 보게 됩니다. 이런 supervision은 training시에만 주어지고, testing시에는 모델이 처음부터 끝까지 그래프를 주욱 만들게 됩니다.
  2. Time and space complexity가 높습니다. 예로, operation들에서 strength가 0인, 사실상 존재하지 않아야하는 vertex들도 모두 처리해야 하는점과 connectivity matrix가 모든 vertex간의 관계를 가지고 있어야하는점 등이 있겠는데요, 이런점들도 future work에서 보완되어야 할 부분들입니다.

EXPERIMENTS:

bAbI 데이타셋에 대한 결과를 한번 보겠습니다. 각각의 task에 대해 그에 맞는 모델을 학습시켰습니다.

Screen Shot 2017-05-23 at 5.22.27 PM

맨처음 나온 GGT-NN이 이 논문이 제안하는 방식입니다. 결과를 보면 17번 task를 제외한 모든 문제에서 95%이상의 정확도를 보여주는 것을 알수 있습니다. (supervision을 줘야되는점과 time&space complexity가 높은 점때문에 10,000개에대한 실험은 하지 않은것 같지만) 1,000개의 example만으로 학습시킨 모델들 중에서는 독보적으로 잘 동작하는것을 보여주는데요, supervision을 주었기때문에 좀 불공정하다고 볼 수도 있겠습니다. 위의 표에 명시된 모델중에 supervision을 준 다른 모델은 MemNN인데요, MemNN보다 더 잘 동작하는것을 저자는 강조하고있습니다.

CONCLUSION:

이번 포스트에서는 unstructured data를 그래프 형식으로 표현하고 그래프로부터 답을 추론해내는 “Learning Graphical State Transition”에 대해 알아보았는데요, 아직 보완해야될 점들이 많지만 neural network를 통해 end-to-end로 그래프를 만드는 방법을 학습시키는 첫번째 논문이라는 점에서 future work들이 기대가 됩니다.

Posted by:Seung Wook Kim

Research Scientist at Lunit Inc.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s