Introduction
시퀀스를 고려하여 처리해야 하는 문제들에서는 주로 RNN을 이용합니다. (2015년 기준?) 하지만 흔히 사용하는 seq와 같은 문제에서는 출력으로 내보내는 클래스들(output dictionary)을 사전에 미리 정의해야 한다는 문제점이 있습니다. 즉 기정의된 셋의 출력만이 가능하기 때문에, 입력에 따라 유연하게 대처하는 것이 불가능합니다.
이 문제점을 해결하기 위해 논문에서는 출력 사전의 크기가 입력의 크기와 관련있는 형태의 네트워크(Ptr-Nets)를 제안합니다. Ptr-Nets에서는 가변 크기 출력을 나타내기 위해 attention 계산 과정에서의 softmax 확률 분포를 입력 중에서 해당 시퀀스의 정답을 가리키는 'pointer'로 사용합니다.
Pointer Network
Sequence-to-Sequence Model
Sequence-to-sequence 모델은 말 그대로 입력 시퀀스에 대해서 정답 시퀀스를 예측하여 출력하는 모델입니다. P는 입력 벡터들의 집합, C^P는 출력 시퀀스이고, 데이터는 (P, C^P)의 쌍으로 이루어집니다.
특정 시점의 시퀀스는 이전 단계까지의 시퀀스에 의존하기 때문에, m(P)를 입력 집합의 인덱스 수, 출력 시퀀스를 C^P = {C1, C2, ..., C_m(P)}라고 할 때 전체 시퀀스에 대한 확률은 다음과 같이 표현할 수 있습니다.
위의 문제를 풀기 위한 모델 학습은 기본적으로 다음의 문제를 푸는 것과 동일합니다.
이를 실질적으로 구현하기 위해서 모델은 LSTM을 사용했습니다. RNN은 각 타임스텝 i에서 P_i를 입력받아서 전체 입력 시퀀스가 모두 입력된 후에는 디코딩의 시작을 알리는 토큰 (여기서는 ⇒)을 만나면 출력값 생성을 시작합니다. seq2seq 모델에서 출력값은 고정되어 있고 입력 값들의 사이즈와 동일하며, 입력 값의 사이즈 n이 바뀔 때마다 네크워크를 새롭게 학습해야 합니다.
Content Based Input Attention
바닐라 sequence-to-sequence 모델에서는 순차적으로 입력 값들을 모두 인코딩 한 뒤에 순차적으로 결과를 출력하기 때문에, 입력 값들이 모두 인코딩된 시점에서는 입력 값에 대한 정보를 더 이상 가지고 있지 않게 되며 디코더로는 제한된 정보의 양만이 들어가게 됩니다. Attention model에서는 인코더와 디코더에 추가적으로 네트워크를 부착하여, 인코더 RNN state의 전체 시퀀스에 대해 attention을 만들어 냄으로써 이를 해결했습니다.
e와 d는 각각 encoder, decoder hidden state이며, softmax의 결과는 input에 대한 attention mask가 됩니다. 이 attention mask와 encoder hidden state를 곱해서 만들어진 d'_i를 원래의 decoder hidden state에 concatenate해서 다음 스텝으로 전파하거나, 출력 값을 디코드할 때 사용하게 됩니다.
Ptr-Net
위의 방법은 여전히 기 정의된 output dictionary 위에서 디코더가 작동한다는 한계를 갖게 됩니다. 이 점을 개선하기 위해서 Pointer Network에서는 softmax로 입력에 대한 attention을 만들어 내는 것이 아니라, 바로 입력 값을 내보내도록 학습합니다.
즉, encoder hidden state를 간접적으로 decoder hidden state에 반영하는 것이 아니라, 직접적으로 encoder hidden state로부터 입력 값 중 어떤 하나를 가리키는 'pointer'를 생성해냅니다. 이렇게 배꾸면, 출력 값들이 입력 값들과 정확히 맵핑되는 시퀀스를 내보내는 것이 가능하며, 아래 예시로 들 task들에 적합한 형태의 문제가 됩니다.
그림으로 seq2seq와 Ptr-Net을 비교하면 다음과 같습니다.
Experiment
입력에 따라 가변 길이 출력을 갖는 세 가지 문제들에 대해 실험을 진행했습니다. 세 가지 문제 모두에서 네트워크의 구조와 하이퍼파라미터는 고정하였으며, LSTM 단일 레이어를 사용했습니다.
Convex Hull
이 문제는 평면에 존재하는 유한한 갯수의 점들을 모두 포함하는 가장 작은 convex hull을 찾는 문제로, 일반적으로 유일해가 있는 것으로 알려져 있으며 exact solution이 존재합니다. n개의 점 집합에 대하여 O(n log n)의 복잡도를 갖습니다.
출력값 C는 convex hull을 이루는 순서대로 나열된 점의 인덱스이며, 인덱스의 순서는 가장 낮은 값의 인덱스부터 시작하여 반시계방향으로 진행합니다.
이 문제의 경우에는 metric으로 정확도와 면적비의 두 가지를 사용했습니다. 면적비는 polygon이 simple polygon이기만 하다면 무조건 gt convex hull보다는 작은 면적을 갖게 됩니다. 면적은 결과 polygon이 simple polygon일 때만 계산하고, 전체 중 1% 이상에서 simple polygon을 생성해내지 못한 경우에는 FAIL로 판정했습니다.
위의 결과를 보면 Ptr-Net을 이용해서 구한 면적이 거의 100%에 근접한 것을 확인할 수 있습니다. 낮은 정확도로 실패한 경우에도 면적을 보면 convex hull과 가까웠으며,시각적으로 확인하면 점들이 일직선으로 정렬되어있어 혼동한 경우가 대부분이었다고 합니다.
Delaunay Triangulation
Delaunay 삼각분할은 평면 위 점들에 대해, 외접원이 점을 내포하지 않도록 하는 삼각형들로 공간을 분할하는 문제입니다. n개의 점에 대해 O(n log n)의 복잡도를 갖습니다. 출력값은 삼각형을 이루는 세 개의 점 인덱스 리스트들의 집합입니다.
여기서는 인덱스들이 모두 permutation이 가능하기 때문에(set의 set), 일반성을 잃지 않고 인덱스 숫자의 사전순서대로 나열했습니다. 이렇게 순서를 지정해주는 것 자체는 임의로 규칙을 만든 것에 불가능하지만, 실제로 이 순서를 넣지 않으면 학습 과정에서의 모호성때문에 잘 학습이 되지 않는다고 합니다.
Delaunay 삼각분할 문제에서는 1) 전체 분할의 정확도와 2) 각 분할에서 정확하게 예측한 삼각형들의 면적 대비 gt 삼각형의 면적 비율 커버리지를 지표로 사용했습니다. n=5일 때 정확도 80.7%, 커버리지 93.0%, n=10일 때는 정확도 22.6%, 커버리지 81.3%였으나, n=50에서는 제대로 된 삼각분할이 나오지 않았으며, 커버리지는 52.8%였습니다.
Travelling Salesman Problem
평면 위 점들을 모두 한번씩만 거쳐 원점으로 되돌아오되, 이 경로를 최소화하는 문제입니다. 모든 점들이 평면상에 존재하며, 이동 경로는 양방향으로 길이가 동일한 Planar symmetric TSP 문제를 학습하였습니다.
이 문제에서는 Ptr-Nets의 복잡도가 원래 문제의 복잡도보다 현저히 낮기 때문에, 데이터만으로 완벽하게 학습은 어렵습니다. 큰 n에 대해서는 어느정도 근사값을 찾을 수 있는 효율적인 알고리즘들이 존재하기 때문에, 이를 비교 대상으로 삼았습니다. (A1, A2, A3) 아래 표의 결과값은 결과 경로의 총 이동 거리입니다. 앞의 문제들과 달리 여기서는 유효한 경로를 찾기 위해 beam search를 이용하였는데, n>20인 경우에서는 10% 이상의 유효하지 않은 경로를 만들어냈다고 합니다.
먼저 아래 표에서 첫번째 그룹은 n의 갯수를 고정시켜서 학습한 경우입니다. n=50의 경우에는 해의 계산이 불가능하므로 A1과 A3을 사용한 것을 각각 gt로 하여 학습하였는데, 흥미롭게도 더 최적에서 먼 A1을 이용해서 학습했을때 Ptr-Net의 결과가 더 좋았습니다.
두번째 그룹은 n의 길이를 바꿔가면서 학습한 것인데, n=25까지는 거의 최적에 준하는 해를 찾을 수 있었습니다. 하지만 거의 완벽하게 일반화가 가능했던 convex hull 문제와 다르게, n=40 이상의 경우들에서는 (그래도 대충 때려 맞춘 경로보다는 훨씬 낫지만) 준최적 해에 비해 급격히 증가합니다. 이는 아까 언급한대로 일반적으로 TSP를 해결하기 위해 사용하는 알고리즘들에 비해 Ptr-Net의 복잡도가 낮기 때문인 것으로 판단됩니다.
Conclusions
이 글에서는 입력에 대해서 입력 값들과 관계된 어떤 시퀀스를 출력할 수 있는 모델인 Ptr-Net에 대해서 알아보았습니다. 이 모델을 이용하면 입력, 출력 값들을 가변적으로 유지할 수 있으며, (어느 정도는) 입력 값의 갯수가 변하더라도 새로 모델을 학습하지 않아도 된다는 장점을 갖습니다. 이 모델을 기본적인 최적화 문제에 적용했을 때, 어느 정도 해결 가능성이 확인된 것 같습니다.
다만 문제의 결과를 보면, 최적화에 실패한 것이 아니라 기본적으로 문제의 constraint 자체를 준수하지 못한 invalid solution이 상당히 출력된다는 것이 아쉽습니다. 이를 보면 (네트워크 구조의 한계일 수도 있지만) 문제의 조건을 학습하는 것이 아니라 답처럼 보이는 무언가를 출력하는 것에 가까워 보입니다.
또, 입력 값들로만 된 시퀀스를 답으로 갖는 문제를 푼다는건 이미 문제의 가정부터 상당히 제한적일 수 있습니다. 대신 (m4c에서 제안하듯이) 어떤 fixed-size dictionary를 별도로 정의하고, 여기에 입력들도 정답 스페이스에 유연하게 추가할 수 있는 형태의 네트워크를 만들면 활용 가치가 높지 않을까 싶습니다.
Share article