[RNN] Pointer Networks

키워드

1. 포인터 메커니즘을 도입하여 입력 시퀀스에서 직접 위치를 선택. TSP와 같은 문제 해결.

2. "Pointer Networks"

3. Pointer Network, pointer, attention

Pointer Network

  RNN(Recurrent Neural Networks)은 시퀀스 형식의 데이터를 통해 함수를 학습하는 데 사용되었다. 초기 모델은 입력과 출력이 고정된 frame rate여야 한다는 단점이 있었고, sequence-to-sequence 구조로 보완되었다. 이후 attention mechanism이 추가되어 입력의 상황 정보를 고려하도록 디코더를 강화하였다.

  이러한 개선에도 불구하고 여전히 출력의 크기가 고정되어 있다는 단점이 존재한다. 출력의 시퀀스 길이가 아닌, 사용 가능한 단어의 집합처럼 출력 자체가 가질 수 있는 후보가 고정되어 있는 것을 의미한다. 이러한 한계로 인해 출력의 크기가 입력 시퀀스의 길이에 따라 달라지는 조합 문제를 구현하는데 한계가 존재한다.

  이에 입력 시퀀스의 각 요소에 대한 “pointer”를 생성하는 방식을 고안하였으며, 이를 Pointer Networks(Ptr-Nets) 라고 한다. Attention mechanism을 활용하여 확률을 구한다는 것은 이전 방식과 동일하지만, 해당 확률을 입력의 각 요소 중 하나를 선택하는 “pointer”로 활용한다는 차이가 존재한다. 이를 통해 출력의 크기를 입력에 따라 가변적으로 조절할 수 있다.

  이러한 구조는 출력이 입력 시퀀스의 개별 토큰(discrete tokens)으로 구성되는 문제에서 활용된다. 이는 입력이 달라지게 되면 출력의 클래스 수가 달라진다는 것을 의미하며, 이를 통해 시퀀스 정렬과 같은 문제와 다양한 조합 최적화 문제에 활용 될 수 있다. 실험으로 사용된 예시는 어려운 기하학적 문제에 대한 솔루션을 다뤘다.

Architecture

  구조 비교를 위해 Baseline이 될 모델부터 시작하고자 한다. 그리고 앞서 말했듯 “출력이 입력 시퀀스의 개별 토큰(discrete tokens)으로 구성되는 문제”에 활용하기 위해, 학습 예제가 시퀀스 길이가 n인 vector로 이루어져 있다고 가정하고자 한다.

  우선 LSTM(Long Short Term Memory)을 base로 사용하였다. 그리고 특수 기호 ⇒는 모델이 입력 시퀀스의 끝에 도달하여 모든 step 𝑖에 대한 𝑃𝑖를 공급하였음을 의미하며, 이후 출력 시퀀스의 끝을 의미하는 특수 기호 ⇐를 만날 때까지 생성 모드로 전환된다.

Seq2Seq

  두 개의 별도 RNN을 사용하며 전자의 RNN을 encoder라고 부르고 후자를 decoder 또는 generative RNN이라 한다. 인코더로 벡터 시퀀스 𝑃𝑗를 인코딩하고 디코더로 출력 기호 𝐶𝑖을 생성하게 되는데, 최적의 시퀀스 𝒞를 찾는 것은 가능한 출력의 조합 수 때문에 계산적으로 비현실적이다. 이에 beam search를 사용하여 최상의 시퀀스를 찾게 된다.

  Seq2Seq 모델에서 출력 크기 𝑛은 고정되며, 이로 인해 추론 시 n과 다른 입력 시퀀스 길이가 들어와도 출력의 크기가 달라지지 않아 최적의 솔루션을 학습할 수 없다. 출력 개수가 𝑂​(𝑛)라고 가정하면 이 모델의 계산 복잡도는 𝑂​(𝑛)이 된다.

Attention

  Seq2Seq 모델은 입력 시퀀스 끝에서 RNN의 state를 사용하여 전체 출력 시퀀스 𝒞를 생성한다. 이는 생성 모델에 전달될 수 있는 정보와 계산의 양을 제한한다. 이를 보완하기 위해 attention mechanism으로 인코더 및 디코더 RNN을 강화하였다.

  다만 여전히 출력 크기는 고정되어 있으며, 각 출력에 대해 𝑛 연산을 수행해야 하므로 추론 시 계산 복잡도는 𝑂​(𝑛^2)이 된다.

Ptr-Net

  Point Network는 출력 크기가 입력 시퀀스의 수에 따라 달라지는 조합 최적화 문제에 적용할 수 있는 attention 모델로 볼 수 있다. 다만 attention mechanism은 softmax 분포를 디코더로 전파하는 반면, Ptr-Net은 디코더로 전파하지 않고 직접적으로 입력 요소를 선택하는 포인터로 사용했다. 즉, softmax는 벡터 𝑢𝑖(길이 𝑛)를 입력 요소에 대한 출력 분포로 normalize 한다. 이를 통해 출력을 입력으로부터 얻을 수 있으며, 구현한 수식은 위와 같다.

728x90

문제 및 결과

  우선 baseline 모델과 Ptr-Net은 결과의 왜곡을 방지하기 위해최적의 하이퍼파라미터가 아닌 동일한 모델 하이퍼파라미터를 사용하였다. 모든 모델은 256개 또는 512개의 hidden unit이 있는 단일 레이어 LSTM을 사용했다.

Convex Hull

  유한한 개수의 점에서 convex hull을 찾는 것은 기하학에서 유명한 문제이며, 일반적으로 솔루션을 찾는 데는 복잡도는 𝑂​(𝑛​log⁡𝑛)이다. 여기서 𝑛는 고려되는 포인트 수이며, 이 문제에서 얻어지는 출력은 1과 𝑛 사이의 인덱스이거나 특수 토큰으로 구성된다.

  정량적인 검증을 위해 “정확도”와 “실제 convex hull이 덮힌 면적” 두 가지 지표를 얻었다. 출력이 단순한 다각형을 나타내는 경우에 대한 영역 범위만 계산하였으며, 단순 다각형을 생성하지 못하면 FAIL로 처리되었다. 이에 따른 결과를 보면, Ptr-Net이 덮힌 면적이 100%에 가까운 것을 알 수 있다. 100%에 도달하지 못한 원인은 너무 많은 포인트(n=500)을 고려하였기 때문이며, Ptr-Net 뿐 아닌 대부분의 알고리즘에서 생기는 일반적인 현상이다.

  그리고 추론 중에 인코더에 제공되는 입력의 순서가 성능에 영향을 미치는 것을 확인하였다. 실제 convex hull의 점이 입력 시퀀스에서 "늦게" 나타나면 정확도가 낮아지는 결과를 보였는데, 이는 convex hull을 계산하기 위해 최근에 입력된 점을 고려하여 “업데이트”할 만큼 충분한 처리 단계가 부족했기 때문이다. 이 문제를 극복하기 위해 attention mechanism을 사용하였고, 항상 전체 입력을 바라보는 특성 덕분에 모델 성능이 향상되었다.

  마지막으로 5에서 50까지의 다양한 길이에서 모델을 학습하면, 단일 모델이 다양한 입력 길이에서 준수한 성능을 보이는 것을 알 수 있다. 더욱 인상적인 점은 모델이 훈련 중에 본 적이 없는 길이까지 추론한다는 것이다. 𝑛=500인 경우에도 결과가 만족스러웠다.

Delaunay Triangulation

  다음 문제는 delaunay triangulation으로, 이는 모든 삼각형의 각 외접원 내부에 아무런 점이 없이 비어 있도록 하는 triangulation 문제다. 𝑂​(𝑛​log⁡𝑛)의 복잡도를 가진 정확한 솔루션이 존재하며, 여기서 𝑛는 점의 수를 의미한다. 이를 위한 출력은 점 집합에서 triangulation(1부터 n 사이의 세 개의 정수) 시퀀스들의 집합이다. 

  이를 위해 “정확도”와 모델이 올바르게 예측한 삼각형의 “백분율” 두 가지 지표로 성능을 평가했다. Ptr-Net 모델을 사용하여 𝑛=5에 대해 80.7%의 정확도와 93.0%라는 준수한 성능을 보였다. n = 10은 22.6%의 정확도와 81.3%의 백분율, 𝑛=50의 경우 정확한 triangulation을 생성하지 못했지만 52.8%의 백분율을 구했다. 위 시각화는 n=50의 결과다.

Traveling Salesman Problem

  TSP는 컴퓨터 과학의 여러 영역에서 활용되며, 마이크로칩 설계 또는 DNA sequencing에 사용되는 중요한 알고리즘이다. 이는 도시 목록이 주어지면 각 도시를 정확히 한 번 방문하고 시작점으로 돌아가는 최단 경로를 구하는 문제다. 여기서 두 도시 사이의 거리는 양방향 모두 동일하다고 가정한다.

  앞선 문제들과 달리 정확한 솔루션을 구하는데 여러 알고리즘을 사용했다. 먼저 Held-Karp 알고리즘(A1)은 𝑂​(2^𝑛*​𝑛^2)의 복잡도로 구할 수 있으나 더 큰 𝑛의 경우 정확한 솔루션을 생성하는 데 비용이 많이 든다. 이에 n=20 까지는 A1을 사용하였고, 이후 근사적인 솔루션을 생성하는 Christofides 알고리즘도 활용 하였으며, 이는 𝑂​(𝑛^2)  복잡도를 가지는 A2, 𝑂​(𝑛^3)의 복잡도를 가지는 A3 로 활용되었다.

  이 문제의 결과는 제안된 투어의 길이를 지표로 활용하였다. 눈에 띄는 부분은 성능이 가장 좋지 않은 A1 알고리즘을 바탕으로 학습하여도, 추론 시에 Ptr-Net이 더 좋은 성능을 보인다는 것이다. 또한 5~20개 도시의 최적 데이터로 훈련된 Ptr-Net은 훈련된 도시 수 보다 많은 n = 25 ~30 수준의 추론에서도 어느 정도 성능을 보였으며, 이는 일반화될 수 있다는 것을 의미한다.

Reference

논문 링크 : https://arxiv.org/abs/1506.03134