[Paper Review] Pointer Networks

#paper-review #deep-learning #attention #combinatorial-optimization #pointer-network

논문 링크: Pointer Networks

논문 정보

항목	내용
Venue	NeurIPS
출판 시점	2015년
저자	Oriol Vinyals, Meire Fortunato, Navdeep Jaitly
주제	Attention, combinatorial optimization

핵심 아이디어

Pointer Network는 attention을 output vocabulary 위의 확률분포가 아니라 input element 위의 pointer로 사용한다. 즉 출력은 단어 사전의 token이 아니라, 입력 sequence의 index이다.

Pointer Network는 출력 공간이 입력 길이에 따라 달라지는 문제를 attention pointer로 처리한다.

예를 들어 Traveling Salesman Problem에서는 입력이 점들의 집합이고, 출력은 방문해야 할 점들의 순서이다. 일반 seq2seq는 고정 vocabulary를 가정하지만, Pointer Network는 입력 위치를 직접 가리키므로 variable-size combinatorial problem에 맞는다.

왜 중요한가

이 논문은 attention을 "어디를 참고할지"뿐 아니라 "무엇을 출력할지" 결정하는 mechanism으로 확장했다. 이후 routing, graph, program synthesis, extractive summarization 계열 문제와 연결된다.

수식으로 보는 핵심

Pointer Network는 decoder step $i$ 에서 입력 위치 $j$ 를 가리키는 확률을 출력한다. Encoder hidden state를 $e_j$ , decoder state를 $d_i$ 라고 하면 pointer score는 다음처럼 계산된다.

u_j^i = v^\top \tanh(W_1 e_j + W_2 d_i)

그 다음 입력 위치 전체에 대해 softmax를 취한다.

p(C_i = j \mid C_1, \dots, C_{i-1}, P) = \frac{\exp(u_j^i)}{\sum_{k=1}^{n}\exp(u_k^i)}

여기서 $n$ 은 입력 길이다. 따라서 output vocabulary 크기는 고정된 단어장 크기가 아니라 입력 길이 $n$ 에 따라 변한다.

Pointer Network의 핵심 수식은 attention softmax를 context 생성용 가중치가 아니라 입력 index에 대한 출력 확률로 해석한다는 점이다.

TSP라면 $C_i$ 는 $i$ 번째로 방문할 point index다. Convex hull이라면 $C_i$ 는 hull 위의 다음 point index다. 즉 이 모델은 값을 새로 생성하지 않고, 입력 원소를 순서대로 선택한다.

문제 설정

일반적인 sequence-to-sequence model은 고정된 vocabulary 위에서 token을 선택한다. 하지만 convex hull, Delaunay triangulation, TSP처럼 출력이 입력 원소의 순서나 subset인 문제에서는 vocabulary가 입력마다 달라진다. 입력 점이 10개면 출력 후보가 10개이고, 입력 점이 100개면 출력 후보가 100개다.

Pointer로서의 Attention

Pointer Network는 decoder attention distribution을 그대로 출력 분포로 사용한다. 즉 attention이 source representation을 요약하는 데 쓰이는 것이 아니라, source index 중 하나를 선택하는 확률이 된다.

Pointer Network에서 attention은 context를 읽는 장치이면서 동시에 입력 위치를 출력하는 classifier다.

Combinatorial Problem과의 연결

TSP에서는 입력 점들을 어떤 순서로 방문할지 정해야 한다. Pointer Network는 매 step마다 아직 선택할 수 있는 입력 점 중 하나를 가리키는 방식으로 tour를 만든다. 이 구조는 출력 차원이 입력 크기에 맞춰 자연스럽게 변하기 때문에, fixed vocabulary decoder보다 combinatorial structure에 잘 맞는다.

Generalization 관점

중요한 질문은 작은 크기에서 학습한 모델이 더 큰 입력에도 일반화되는가이다. Pointer Network는 구조적으로 variable length를 처리할 수 있지만, combinatorial optimization의 난이도 자체가 사라지는 것은 아니다. 입력 크기가 커지면 search space가 폭발하고, neural decoder가 항상 좋은 해를 보장하지도 않는다.

한계

Pointer Network는 attention을 출력으로 쓰는 강력한 아이디어를 제시했지만, 제약 조건을 완벽히 만족하는 해를 항상 만들지는 않는다. 또 TSP 같은 문제에서는 classical solver와 비교했을 때 optimality guarantee가 부족하다. 그래서 이후 연구는 reinforcement learning, beam search, graph neural network, constraint-aware decoding과 결합하는 방향으로 발전했다.

읽을 포인트

attention distribution을 pointer distribution으로 해석하는 방식
convex hull, Delaunay triangulation, TSP task 구성
input length가 달라질 때의 generalization
neural combinatorial optimization의 초기 흐름

정리

이 논문은 attention의 의미를 확장했다. Attention은 단순히 encoder state를 읽는 도구가 아니라, 입력 원소 자체를 선택하는 pointer가 될 수 있다. 입력에 따라 출력 공간이 달라지는 문제를 neural network로 다룰 때 기본적으로 떠올려야 할 구조다.