요약

Pointer Network는 입력차원에 따른 출력 차원이 조절되는 모델 제안
작은 크기의 Convex Hull, Delaunary Triangulation, TSP 문제에서 출력 차원이 고정된 모델보다 더 좋은 성능을 보임
학습 데이터보다 더 긴 길이의 input에서도 동작

배경 지식

다음의 내용을 알고 있으면 글을 이해하기 편합니다.

조합최적화 (Combinatorial Optimization)
TSP
RNN, seq-to-seq
Attention

배경

조합최적화 문제는 주어진 아이템의 최적 순서를 찾는 문제입니다. 대표적으로 외판원순환문제(TSP), 최소신장트리(MST), 배낭문제 (Knapsack Problem) 등이 조합최적화 문제에 속합니다. 조합최적화는 산업에서 생산 물류 최적화, 운송 경로 최적화, 자원 할당 최적화, 작업 공정 최적화 (Job-shop scheduling) 등의 문제를 해결하는데 사용됩니다. 조합최적화는 NP-Hard 문제로 최근에는 딥러닝으로 해결하려는 연구들이 진행되고 있습니다.

Pointer Network는 input 개수에 따라 output 개수가 정해지는 모델을 제안합니다.
일반적인 조합 최적화 문제는 output 개수(size of output dictionray) 가 input 개수와 같아야 합니다. 즉, 출력이 입력에 의존적입니다. 하지만 기존의 seq-to-seq모델에서 output의 개수는 학습 전에 정해집니다. 따라서 문제의 input 개수가 달라지면 output 개수도 달라져야하고 결과적으로 새로운 모델이 필요하게 됩니다. Pointer Network는 output 개수를 input 개수와 같게 만들어 다양한 크기의 input를 다룰 수 있는 학습및 추론 할수 있는 방법을 제안합니다.

Model

Pointer Network는 기존의 attention을 변형해 score가 아닌 input의 index를 반환하게 합니다. 모델을 통과하면 n개의 input은 대응하는 n개의 index를 출력하게 되어 input과 output의 개수가 일치하게 됩니다.

기존의 Attention은 아래 그림과 같이 동작합니다. (아래 그림은 남규현님의 그림을 참고하였습니다.)
각 input에 대한 attention score를 가중치로 하여 input의 encoding 값을 가중치합하여 다음 decoding 값을 계산합니다.

Pointer Network는 가중치 합을 계산하는 부분을 생략하고 softmax 값을 다음 output의 probability distribution로 취급합니다.
그리고 argmax를 취해 가장 확률이 높은 input 의 index를 출력합니다. 이때 attention layer의 계산복잡도는 $O(N^2)$ 입니다.

Experiment

논문에서는 실험에 사용한 데이터셋을 공개했습니다.
위 데이터셋을 사용해 convex hull, Delaunary traingle, Travelling Salesman Problem 에 적용했습니다. 이 블로그에서는 TSP 에 대한 결과만 소개하겠습니다.

Convex Hull (left), Delaundary Triangle (center), TSP (right)

TSP

TSP 문제에 대해서는 모델의 약간의 변형이 있습니다. 기존에는 argmax로 greedy decoding을 했다면 TSP에서는 beam search를 사용해 성능을 높였습니다. (beam search를 사용하지 않으면 같은 도시를 두번 반복하는 것과 같은 invalid output을 출력한다고 합니다.)
TSP 문제는 기존 approximate 세개(A1, A2, A3) 와 pointer network를 비교했습니다. approximate algorithm들은 각각 $O(N^2), O(N^2), O(N^3)$ 의 계산복잡도를 갖습니다.
TSP문제에서 optimal solution을 구할 때 필요한 계산 복잡도는 $O(2^NN^2)$ 으로 N > 25 일때는 계산이 어려워 표현이 어려워 A1과 A3 알고리즘으로 훈련 데이터셋을 만들었다고 합니다.

실험 결과는 두가지를 확인할 수 있습니다.

A1 알고리즘으로 학습한 Pointer Network가 A1보다 더 좋은 성능을 보였습니다.
(5-20)개의 도시 데이터셋을 학습한 Pointer Network가 30개까지는 괜찮은 성능을 보이고 40개 이상에서는 성능이 떨어집니다.

Conclusion

이 논문은 출력의 크기가 입력 sequence 길이에 따라 달라지는 문제에 대해서 다양한 크기의 input을 다룰 수 있는 모델을 제안했습니다.
Pointer Network는 조합최적화 문제에서 하나의 학습된 모델로 다양한 복잡도의 문제에 적용할 수 있게 해줍니다.
또한 데이터를 생성할 때 사용한 알고리즘보다 학습된 모델이 더 좋은 성능을 보여주는 흥미로운 결과도 보여주었습니다.
하지만 beam search 를 사용하지 않으면 invalid output을 출력한다는 점과 생각보다 scalability가 적다는 점이 아쉬웠습니다.

저작자표시 (새창열림)