Pointer Networks

 

논문:  Vinyals, Oriol, Meire Fortunato, and Navdeep Jaitly. "Pointer networks." Advances in neural information processing systems. 2015.

---

Abstract

조합 최적화 문제를 딥러닝을 활용해 해결하기 위한 모델 제안 => Pointer Networks

 

? 조합 최적화 문제: 입력으로 주어진 요소 중 최적의 조합 찾기, ex) 최단 경로 문제

입력 길이에 의존하기 때문에, 가변적 입력 길이 문제에 대해 기존 모델로 좋은 성능을 얻기 어려워

: seq2seq 과 neural turing machine 접근법으로는 문제를 해결하기 어려움

 

* seq2seq: 고정된 입력에 대해 문제를 해결할 수 있어

* attention 메커니즘: 각 디코더 단계에서 인코더의 hidden state -> context vector로 혼합

* ptr-net: 어텐션을 포인터로 사용해 입력 시퀀스의 구성원을 출력으로 선택

 

 

논문에서 소개하는 조합 최적화 문제 3가지 planar convex hulls | computing Delaunay triangulations | planar Traveling Salesman Problem

=> ptr-nets 으로 approximate solution을 학습 가능

---

1. Introduction

RNN: 입력과 출력이 고정된 프레임 속도로 사용 가능한 설정에 제한,

-> 하나의 RNN 사용해 입력 시퀀스 임베딩으로 매핑하고, 다른 RNN 사용해 임베딩을 출력 시퀀스로 매핑해 제한 제거

-> context-based attention 메커니즘 사용해 입력으로부터 문맥 정보를 디코더에 전달해 보강

순환 신경망 (Recurrent Neural Network, RNN)

- 시퀀스 데이터를 처리하는 데 특화, 자연어 처리, 음성 인식, 시계열 예측 문제에 사용 

ex_ 번역기:

- input = 번역하고자 하는 단어 시퀀스인 문장

- output = 번역된 문장 (단어 시퀀스)

 

- 동일한 가중치와 bias를 공유하면서 반복되는 구조, 길이가 긴 시퀀스에 대해서 일정한 크기의 파라미터만 사용하여 학습 가능

- Long-term dependency problem, 입력과 출력 사이의 거리가 멀어질수록 정보를 기억하지 못해 

=> LSTM과 GRU 같은 RNN 의 변형 개발: 기본 구조에 GATE 메커니즘 추가

 

 

• 간단하고 효과적인 새로운 구조 제안, 가변적인 길이에서 발생하는 문제를 해결하기 위해 sofmax 분포를 포인터로 사용

•  기하학과 관련된 3가지 알고리즘 문제에 적용해, 학습된 모델이 훈련 문제보다  테스트 문제에 대해 일반화된다는 것을 보여줌.

• 50 이하의 크기에서 TSP 문제에 대한 근사적인 해답 제공, 계산적으로 다루기 힘든 문제에 대해 데이터 기반 접근법으로 대략적인 솔루션 학습할 수 있음 보여줌.

---

2. Models

 

2-1 Sequence-to-Sequence

 

주어진 훈련쌍에 대해 모델은 조건부 확률 계산, 매개 변수 θ를 가진 모델을 사용해 확률 체인 룰의 항목 추정

P = 길이 n의 시퀀스

C = 1 .. n 까지의 인덱스 포함하는 길이 m(P)의 시퀀스

모델의 매개변수는 훈련 세트의 조건부 확률 최대화 하는 방식으로 학습.

 

 

LSTM 사용하여 조건부확률 모델링. RNN은 각 시간 단계 i 에서 Pi 를 입력으로 받아, 입력 시퀀스 끝까지 진행. (특수 심벌 ⇒ 입력)

네트워크는 generation mode로 전환되어 특수 심벌 ⇐를 만날 때까지 작동한다.

(통계적 독립성 가정 X, 2개의 RNN -> encoder, decoder)

 

추론 단계에서 시퀀스 P에 대해 학습된 θ 사용하여 확률이 가장 높은 시퀀스 Cp선택

beam search 사용해 beam 크기에 따라 최상의 시퀀스 찾아

(beam search: 일정 개수의 후보 시퀀스 유지하고, 각 시퀀스의 확률 계산해 우수한 후보 선택)

 

seq2seq 모델에서 모든 Ci 에 대한 출력 사전 크기는 n 으로 고정(입력에서 선택된다)

=> 각 n 에 대해 별도의 모델 훈련

=> 입력 시퀀스 길이에 따라 출력 사전의 크기가 달라지는 문제 해결 학습 불가능!!

 

출력 수가 O(n)인 경우, 모델 계산복잡도 = O(n)

Convex hull 문제 복잡도 = O(n log n)

Attention mechanism 은 해당 모델에 더 많은 계산 용량 추가해, 성능 향상시키는 데 도움이 되는 추가적인 계산 능력 제공

 

 

2-2 Content Based Input Attention

 

기본 seq2seq 모델은 입력 p 의 끝에서 RNN의 고정 차원 상태를 사용해 전체 시퀀스를 생성해 생성 모델로 흐르는 정보와 계산양이 제한됨.

Attention 모델은 인코더, 디코더에 추가적인 신경망 도입해 전체 인코더 상태 시퀀스에 대해 어텐션 메커니즘 적용

 

인코더, 디코더의 hidden state 를 (e1, ... , en) , (d1, ... , dn)이라고 정의 했을 때

LSTM RNN 에 대해서 출력 게이트가 셀 활성화와 요소별로 곱해진 후의 상태 사용

 

각 출력 시점 i 에서 어텐션 벡터 계산 방법:

- softmax: 벡터를 입력에 대한 어텐션 마스크로 정규화

- v, W1, W2: 학습 가능한 매개변수

- d_: 재귀 모델의 다음 시점에 전달되는 hidden state

 

각 출력마다 n개의 연산을 수행하므로, 추론 시 계산 복잡도 = O(n^2)

 

- Convex hull 문제에서 seq2seq 모델보다 우수한 성능보이지만

=> 출력 크기가 입력에 따라 달라지는 문제에 적용할 수 없다!

 

 

 

2-3 Ptr-Net

 

- seq2seq: 

파란색(RNN): 입력 시퀀스 처리해 code vector 생성,

code vector 사용해 probabiltity chain rule과 다른 RNN 통해 출력 시퀀스(보라색) 생성

(출력의 차원은 문제 차원과 동일하며 훈련/추론 중에 고정된다.)

 

- Ptr-Net:

인코딩은 시퀀스를 파란색(code)로 변환하고, 이 코드를 generating network(보라색)에 전달한다.

generating network는 입력에 대한 content-based attention 메커니즘을 조절하는 벡터 생성

어텐션 메커니즘의 출력은 입력 길이와 동일한 크기의 Softmax distribution

 

입력 시퀀스 길이에 따라 출력 크기가 달라지는 조합 문제에 직접 적용할 수 없어

-> 어텐션 메커니즘 재활용 => 입력에 대한 포인터 생성  (data driven 방식으로 근사적인 해결책 생성)

 

 

 

- softmax: 벡터 u를 입력에 대한 출력 분포로 정규화

- v, W1, W2:  출력 모델의 학습 가능한 매개변수

 

=> encoder state(e_i) 를 혼합하여 디코더로 전달하는 대신 입력 요소를 가리키는 포인터로 사용한다.

=> C(i-1)에 대해 조건을 걸기 위해 해당하는 Pc(i-1) 을 입력으로 복사한다.

 

** 출력이 이산값이며 입력 위치에 해당하는 문제를 대상으로 한다.

RNN 사용하여 대상 점의 좌표를 직접 출력하는 방식으로 학습 가능.

** 추론 시 출력이 입력과 정확히 대응되어야 한다는 제약을 지키지 못해, 제약이 없으면 예측은 긴 시퀀스에서 흐릿해질 수 있다

---

3. Motivation and DataSet Structures

 

3.1 Convex Hull

 

훈련 데이터 입력은 n개의 요소를 가진 평면상의 점 집합(P)

Pj = 볼록 껍질, Delaunay triangulation, Travelling Salesman 문제 해를 찾기 위해 사용되는 점의 직교 좌표

모든 경우에 대해 [0, 1] x [1, 0] 범위 균일한 분포에서 샘플링한다

출력 Cp 는 점 집합 P에 대한 솔루션 나타내는 시퀀스

 

input/output pair (P, C P ) for the convex hull and the Delaunay problems.

 

 

3.2 Delaunay Triangulation

 

평면상의 점 집합 P에 대한 Delaunay 삼각 분할: 모든 삼각형 내부에 P의 어떤 점도 포함되지 않는 삼각분할

 O(n log n) solution 제공

 

Cp 시퀀스의 어떤 순열도 P에 대한 동일한 삼각분할을 나타낸다.

& 3개의 정수로 이루어진 삼각형 표현 Ci 도 순열이 될 수 있음

 

=> 손실 감소시키지 않기 위해 훈련 시 볼록껍질에 대해, 삼각형 Ci를 중심 좌표에 따라 정렬하고 증가하는 삼각형 표현을 선택한다.

(순서를 적용하지 않은 경우, 학습된 모델의 성능 좋지 않아)

 

 

3.3 Travelling Salesman Problem (TSP)

 

외판원 문제: 마이크로칩 설계, DNA 시퀀싱에 사용되는 알고리즘 >> 평면 대칭 TSP 에 초점

주어진 도시 목록에서 각 도시를 정확히 한 번씩 방문, 시작점으로 돌아가는 가장 짧은 경로 찾기 => NP-Hard 문제

(두 도시 간의 거리는 반대 방향에서도 동일하다 가정)

 

Convex hull 과 유사한 형식,

P: 도시를 나타내는 직교 좌표, [0, 1] x [1, 0] 사각형에서 무작위로 선택

Cp: 최적 경로, 1 ~ n 까지의 정수 순열

 

정확한 데이터를 생성하기 위해 Held-Karp 알고리즘 구현

: O(2^n * n^2) 복잡도로 최적해를 찾는다.

 

---

4. Empirical Results

 

4.1 Architecture and Hyperparameters

 

모든 실험/dataset 에서 거의 동일한 아키텍처 사용 (동일한 하이퍼 파라미터 적용 하는 것이 논문 메시지 강화)

256 or 512 개의 hidden unit 이 있는 단일 레이어 LSTM 사용

 

- learning rate = 1.0

- batch size = 128

- random uniform weight = -0.08 ~ 0.08

- L2 gradient clipping = 2.0

 

Generated 1M training example pairs (task 가 단순한 경우 overfitting 발생)

10 to 20 epoch 이후 Training converged

 

---

4.2 Convex Hull

 

- 정확도 (accuracy) : 최적  convex hull 과 완전히 일치한 정답을 내놓은 경우

- area convered of the true convex hull : 최적  convex hull 과 겹치는 영역의 비율

- FAIL:  제대로된 polygon을 만들어 내지 못하는 경우

 

Comparison between LSTM, LSTM with attention, and Ptr-Net model on the convex hull problem.

<결과 해석>

- Ptr-Net으로 달성한 AREA는 100% 에 가깝다.

- n = 500:  convex hull 에서 해결해야 하는 common source of errors, 추론 중 인코더 입력 순서가 성능에 영향을 미친다

=> convex hull의 점들이 입력 시퀀스에서 늦게 나타나면 때 정확도가 낮아진다. 왜??

=> 아마 네트워크가 최신 점들이 나타날 때까지 계산한 convex hull을 "update"하기 충분한 처리 단계가 없어

=> 2.2 절에서 어텐션 메커니즘 사용해 디코더가 언제든지 전체 입력을 확인 할 수 있도록! 성능 향상 O

=> Attention의 초점 = 입력 부분에서 정답을 "pointing" => 2.3절 Ptr-Net inspired ^^

 

 

LSTM 과 Attention LSTM 보다 우수한 성능

-> 가변 길이: 모델을 5~50 까지 다양한 길이로 훈련할 때, 모든 길이에 대해 잘 수행

-> 모델이 훈련 중에 본 적없는 길이에 대해서도 수행, 모델이 단순한 Lookup  이상을 학습한 것을 간접적으로 나타냄

(LSTM, LSTM with Attention dms n != n 인 경우, 새로운 모델 훈련시켜야 사용 가능)

 

 

4.3 Delaunay Triangulation

 

Convex hull 찾기 문제와 연결.. 주어진 점들의 들루네 삼각분할은 convex hull을 삼각형으로 분할

입력 점 집합 P에 대해 output sequence = 하나의 집합 (요소들의 임의의 순열은 동일한 triangulation을 나타낸다)

 

- acuracy

- triangle coverage in percentage(올바르게 예측된 삼각형의 백분율)

 

 

Ptr-Net

( n=5 )의 경우, accuracy = 80.7%, coverage = 93.0%

(n=10)의 경우, accuracy = 22.6%, coverage = 81.3%

(n=50)의 경우, accuracy = ??.?%, coverage = 52.8% [그림 참조]

 

 

4.4 Travelling Salesman Problem (TSP)

 

NP-Hard: planar symmetric travelling salesman problem

순차적인 출력을 가지고 있다.. Ptr-Net이 O(n^2) 알고리즘을 구현하고 있는데, 데이터만으로 유용한 알고리즘 학습할 충분한 용량 가지는지 불분명

 

상대적으로 작은 n 에 대해 정확한 솔루션 생성, 훈련 데이터로 사용하는 것이 가능하다.

더 큰 n에 대해서는 합리적인 근사해를 제공하는 알고리즘 존재..

 

 

convex hull과 delaunay 삼각분할과 달리, 디코더를 제한하여 유효한 경로만 고려하도록 beam search 설정

- 두 개의 도시를 반복하거나 목적지를 무시할 수 있어 (n이 20 초과인 경우 관련 있다, 작은 경우 제한 없어도 실패율 낮아)

표의 첫 번째 그룹: 최적 데이터로 훈련된 Ptr-Net

최악 알고리즘(A1) 데이터 사용하여 훈련시킨 경우, 모델이 해당 알고리즘 모방하는 것 보다 뛰어난 성능 보여

 

 

5-20 개의 도시로 훈려된 최적 데이터로 훈련된 Ptr-Net이 그 이상의 경우에 대해 어떻게 일반화 하는지 보여

n=40 이상인 경우 결과 악화 <-> Convex hull의 경우 10배 정도 일반화 가능한데 기반 알고리즘이 O(n log n)보다 더 복잡하기 때문일 수 O

---

5. Conclusions

 

그래서@@

Ptr-Net 이라는 새로운 아키텍처 소개

-> P와 Cp 두 개의 시퀀스가 주어졌을 때, Cp의 조건부 확률 학습 (Cp 는 P 위치에 해당하는 discrete tokens의 시퀀스)

 

-> 세 가지 조합 최적화 문제의 솔루션 학습 할 수 있음 보임

-> ⭐가변적(variable) 입력에  의존적인 출력 차원 조절, 기존 seq2seq이 수행할 수 없는 작업!!

-> Ptr-Net 이 고정된 입력 크기 문제에서도 기존 모델 능가

 

과거 RNNSearch, Memory Networks, Neural Turing Machines

= 입력 처리하기 위해 attention 메커니즘 사용

= variable ouput dictionaries 문제 처리할 수 없어

 

출력에 attention 메커니즘 적용해 해당 문제를 해결할 수 있음 보였다 

-> 인공적인 가정 없이 신경망을 적용할 수 있다

-> 본 논문에서 RNNSearch 에 적용하였지만 Memory Networks와 Neural Turing Machines에 동일하게 적용 가능

 

---

Seminar

* Oriol Vinyals: Google DeepMind 의 수석 과학자, 머신러닝, 딥러닝 및 강화 학습 중점

* Meire Fortunato: Google DeepMinde 의 연구 과학자, 시퀀스 모델링, 탐색, 강화 학습에서 메모리 역할 이해 등 기계학습 주제 작업

* Navdeep Jaitly: Google brain 팀의 연구 과학자, 시퀀스를 위한 새로운 딥 러닝 모델 연구

 

 

일반적인 seq2seq , attention 한계

=> 학습 시 정해진 차원에 대한 출력만 결과로 할 수 있어

=> Ptr-Net을 사용하면 출력 차원이 input set 크기와 같게 만들어 구조적 한계 극복!!

(solution 차원이 input set의 element 갯수와 같은 크기를 가져야 하는 조합 최적화 문제에 가장 필요한 기능)

 

 

1. ⭐가변적(variable) 입력에  의존적인 출력 차원 조절 (새로운 아키텍처 제안: softmax 분포를 포인터로 사용)

2. Convex hull, Delaunay triangluation, TSP 같은 문제들에 적용하여 검증

3. 순수 data driven 방식만으로 NP hard 문제에 대한 대략적 solution 제공 (작은 범위 내에서)

---

Attention 메커니즘을 사용해 순서 정보는 보존하면서 시퀀스 내 특정 위치를 가리킬 수 있는 모델 구축

 

 

학습 모델의 목표 = (P, Cp) 애 대해 조건부 확률 p(Cp | P; θ) 구하기

 

Ptr-Net > attention mechanism 에서 attention value 를 구하기 전 단계; attention distribution 까지만 출력으로

> 최대 값을 input set 의 index 로 하여 출력이 input  요소를 가리키도록 구조 짜여져

 

 

"Pointing"

We inspected what attention was focusing on, and we observed that it was “pointing” at the correct answer on the input side. This inspired us to create the Ptr-Net model described in Section 2.3.

출력 위치 예측하기 위한 가중치 학습 -> 입력 시퀀스 요소에 따라 동적으로 결정, 적절한 위치로 포인팅

 

---

 

seq2seq

RNN을 어떻게 조립했는가에 따라 seq2seq 구조 만들어진다

2개의 RNN 아키텍처(성능 문제로 바닐라 RNN > LSTM 또는 GRU 구성)

* 인코더: 입력 문장의 모든 단어들을 순처적으로 받아 => 마지막에 모든 단어 정보 압축해 하나의 벡터로 만들어 => CONTEXT vector

* 디코더: context vector 받아 번역된 단어를 하나씩 순차적으로 출력,

다음에 올 단어를 예측 -> 예측한 단어를 다음 시점의  RNN 입력으로 넣는 행위 반복

 

 

Embedding

seq2seq 에서 사용되는 단어들은 임베딩 벡터로 변환 후 입력으로 사용

 

모든 단어에 대해 임베딩 과정 거쳐 (embedding layer), 보통 임베딩 켁터는 수백 개의 차원을 가질 수 있어..

 

 

Decoder

 

디코더는 인코더의 마지막 RNN Cell의 hidden state인 context vector를 첫 번째 히든 상태 값으로 사용.

첫 히든 상태 & 현재 t 에서의 입력값<sos>  => 다음에 등장할 단어 예측

 

출력 단어로 나올 수 있는 다양한 단어 중, 선택될 수 있는 모든 단어들로부터 하나의 단어 골라 예측

Softmax: 디코더에서 각 시점의 RNN cell 에서 출력 벡터 => softmax  통해 출력 시퀀스의 각 단어별 확률값 반환 => 출력 단어 결정

 

++

context vector를 디코더 초기 히든 상태로만 사용

디코더가 단어를 예측하는 매 시점마다 하나의 입력으로 사용

attention 메커니즘 통해 현재 context 벡터보다 문맥을 반영할 수 있도록 매 시점마다 하나의 입력으로 사용

 

---

Attention Mechanism

 

RNN 기반의 seq2seq 모델 문제

1. 하나의 고정된 크기 벡터에 모든 정보 압축 => 정보 손실

2. RNN: Vanishing gradient 

=> 입력 시퀀스가 길어지면 출력 시퀀스의 정확도 떨어지는 것 보정!

=> Attention

 

* 디코더에서 출력 단어를 예측하는 매 시점마다, 인코더에서 전체 입력 문장을 다시 한 번 참고

=> 해당 시점에서 예측해야 할 단어와 연관이 있는 입력 단어 부분에 더 집중

 

Attention(Q, K, V) = Attention Value

 

주어진 Query 에 대해 모든 Key와의 유사도 구해

구한 유사도를 키와 매핑되어 있는 Value에 반영

유사도가 반영된 Value를 모두 더해 return => attention vlaue

 

Q = Query : t 시점의 디코더 셀에서의 은닉 상태
K = Keys : 모든 시점의 인코더 셀의 은닉 상태들
V = Values : 모든 시점의 인코더 셀의 은닉 상태들

 

 

Dot-Product Attention

 

 

디코더 3rd LSTM cell 에서 출력 단어 예측 시 attention 메커니즘 사용

=> 출력 단어를 예측하기 위해 인코더의 모든 입력 단어 정보를 다시 한번 참고한다

=> 인코더의 softmax 함수 => 입력 단어 각각이 출력 단어를 예측할 때 얼마나 도움이 되는지 정도 수치화

=> 이를 하나의 정보로 담아서 디코더로 전송 => 디코더가 출력 단어를 더 정확하게 예측할 확률이 높아진다

 

 

Attention Score

 

시점 t에서 출력 단어 예측하기 위해 디코더는 t-1 시점의  hidden state와 t-1 의 출력 단어 필요

=> Attention 메커니즘에서는 Attention Value 값 추가

 

 

Attention Score

- 현재 디코더 시점 t에서 단어 예측하기 위해 인코더의 모든  hidden state 각각이 디코더 현 시점  hidden state: st와 얼마나 유사한지 판단한 스코어 값

- dot-product attention에서는 이 값을 구하기 위해 st를 transpose 하고 각  hidden state와 내적을 수행해

 

 

 

softmax -> Attention Distribution

앞에서 구한 e^t에 softmax 적용하여 모든 값을 합하면 1이 되는 확률 분포를 얻는다

 

=> attention distribution

=> 각각의 값은 attention weight 

 

 

Encoder attention weight와 hiddent state 를 가중합 => attention value

준비한 정보 하나로 합치기!

최종 결과 attention value (at)는 인코더의 문맥을 포함하고 있다 -> context vector

<-> seq2seq 인코더의 마지막 hidden state를 context vector 라고 부르는 것과 대조

attention 값을 구하면 이를 st와 결합해 하나의 벡터로 만드는 작업 수행 = vt

vt를 y_hat 예측 연산의 입력으로 사용해 인코더로부터 얻은 정보 활용하여 더 잘 예측할 수 있도록 ==> attention 메커니즘의 핵심!

 

vt를 바로 출력층으로 내보내기 전에 신경망 연산 추가.. 가중치 행렬과 곱한 후 tahn 함수 => 출력층 연산을 위한 st 얻어

(seq2seq과 비교? 출력층 입력이 t 시점의 hiddent state인 st <-> attention에서는 출력층의 입력이 st) 

 

 

 

++ More..

dot-product attention 과 다른 attention 의 차이 = 중간 수식(attention score 함수)

- dot (Luong et al. (2015))

- scaled dot (Vaswani et al. (2017))

- general (Luong et al. (2015))

- concat (Bahdanau et al. (2015))

- location - base (Luong et al. (2015))

 

---

+ 읽을수록 모르겠는데 ^ㅗ^

 

|_ set-to-sequence method in machine learning => Pointer Network 확인