Pointer Networks · 보충 자료
Pointer Networks 논문(Vinyals·Fortunato·Jaitly, 2015)은 볼록 껍질, 들로네 삼각분할, 외판원 문제를 실험 과제로 썼습니다. 셋 다 평면 위의 점들을 받아서 입력 점들의 번호를 출력하는 문제입니다. 이 페이지는 같은 점 7개를 놓고 각 문제의 답이 어떻게 생겼는지 차례로 봅니다.
입력은 세 문제 모두 같습니다. 평면 위의 점 \(n\)개 \(\mathcal P=\{P_1,\dots,P_n\}\)이고, 각 점은 좌표 \((x,y)\) 두 숫자입니다. 논문은 점을 모두 \([0,1]\times[0,1]\) 정사각형에서 고르게 뽑았습니다.
출력도 생김새가 같습니다. 새 값을 만들어 내지 않고, 입력 중 몇 번째 점인지를 골라 늘어놓습니다. 그래서 출력에 나올 수 있는 번호는 1부터 \(n\)까지이고, 이 범위는 입력이 들어올 때마다 달라집니다. 출력 사전이 고정된 seq2seq로는 이런 문제를 풀기 어렵고, Pointer Network는 이 점을 해결하려고 나왔습니다.
아래 그림의 점 7개를 이 페이지 전체에서 씁니다. 본문 4절의 데모도 같은 배치입니다.
번호는 입력 순서일 뿐, 위치와는 상관이 없습니다.
볼록 껍질(convex hull)은 평면에 흩어진 점들을 모두 감싸는 가장 작은 볼록 다각형입니다.
판자에 못을 여러 개 박고, 크게 늘린 고무줄을 바깥에 걸었다가 놓는다고 생각해 보세요. 고무줄은 줄어들다가 가장 바깥쪽 못들에 걸려 멈춥니다. 그때 고무줄이 만든 모양이 볼록 껍질입니다.
초록 선이 고무줄(볼록 껍질)입니다. 진한 초록 점이 꼭짓점이고, 회색 점은 껍질 안쪽에 있어 결과에 영향을 주지 않습니다. 주황 숫자는 출력 순서입니다(⑤는 다각형을 닫으려고 P3을 한 번 더 가리키는 것).
출력은 껍질 꼭짓점의 번호를 둘레를 따라 적은 것입니다. 같은 껍질이라도 어느 점에서 시작해 어느 방향으로 도느냐에 따라 여러 가지로 적을 수 있어서, 논문은 “껍질 위에서 번호가 가장 작은 점부터 반시계 방향”으로 적고, 마지막에 시작점을 한 번 더 적어 다각형을 닫기로 정했습니다(논문 그림 2(a)).
⇒ 3 → 6 → 4 → 5 → 3 ⇐
⇒와 ⇐는 시작과 끝을 알리는 기호입니다. 입력은 7개인데 꼭짓점은 4개이고, 끝에 시작점 3을 한 번 더 적습니다. 출력 길이는 점이 어떻게 놓였느냐에 따라 매번 달라집니다.
볼록 껍질은 \(O(n\log n)\)에 정확히 구하는 알고리즘이 오래전부터 있습니다(Graham 스캔 등). 학습용 정답을 얼마든지 만들 수 있으니, 신경망이 규칙을 데이터만 보고 배울 수 있는지 시험하기 좋은 과제입니다. 논문이 첫 과제로 고른 것도 이 때문입니다.
평가 지표는 두 가지입니다.
Ptr-Net은 길이 5~50을 섞어 학습한 모델 하나로 n = 50에서 정확도 69.6%, 학습 때 본 적 없는 n = 500에서도 면적 커버 99.2%를 냈습니다. 자세한 표는 본문 7절에 있습니다.
삼각분할(triangulation)은 점들을 선분으로 이어 볼록 껍질 안쪽을 삼각형으로 빈틈없이 나누는 것입니다. 선분끼리는 교차하지 않고, 모든 점이 어떤 삼각형의 꼭짓점이 됩니다. 같은 점 집합을 삼각형으로 나누는 방법은 많은데, 그중 들로네 삼각분할(Delaunay triangulation)은 다음 조건을 만족하는 하나입니다.
어떤 삼각형의 세 꼭짓점을 지나는 원(외접원)을 그려도, 그 원 안쪽에 다른 점이 하나도 없다.
이 조건을 만족하면 삼각형들이 되도록 정삼각형에 가까워집니다. 가능한 삼각분할 중에서 가장 작은 각이 가장 크다는 성질이 알려져 있습니다. 바늘처럼 가는 삼각형을 피하고 싶은 곳, 예를 들어 유한요소 해석용 메시나 지형 모델링에 많이 쓰입니다. 점들이 특수하게(네 점이 한 원 위에) 놓이지 않는 한 들로네 삼각분할은 하나로 정해집니다.
삼각형 8개로 나뉩니다. 점선 원은 삼각형 (1, 2, 5)의 외접원이고, 원 안에 다른 점이 없습니다. 바깥 테두리는 그림 1의 볼록 껍질과 같습니다.
출력은 삼각형의 나열이고, 삼각형 하나는 꼭짓점 번호 세 개짜리 묶음입니다. 그런데 삼각형들은 원래 순서가 없는 집합이라, 한 줄로 적으려면 순서를 정해 줘야 합니다. 논문은 삼각형을 내심 좌표의 사전순(x 좌표가 작은 것부터, 같으면 y 좌표순)으로 늘어놓고, 각 삼각형 안의 번호는 오름차순으로 적었습니다. 이렇게 순서를 정하지 않았을 때는 결과가 나빴다고 적혀 있습니다.
⇒ (4,6,7) (1,4,7) (1,6,7) (1,4,5) (1,2,6) (1,2,5) (2,3,5) (2,3,6) ⇐
번호 24개가 나옵니다. 볼록 껍질과 달리 모든 점이 한 번 이상 나오고, P1처럼 여러 삼각형이 공유하는 점은 여러 번 나옵니다. 삼각형 개수는 점 \(n\)개, 껍질 꼭짓점 \(h\)개일 때 항상 \(2n-2-h\)개입니다(여기서는 \(14-2-4=8\)).
디코더 입장에서 보면 이 문제는 볼록 껍질보다 훨씬 깁니다. 점 \(n\)개면 출력 번호가 대략 \(6n\)개 나옵니다. 번호 하나만 틀려도 삼각형이 어긋나므로 완전히 맞히기가 어렵습니다.
들로네 삼각분할도 \(O(n\log n)\) 정확 알고리즘이 있어서 정답을 쉽게 만들 수 있습니다. 평가 지표는 정확도(삼각형 집합이 정답과 완전히 같은 비율)와 삼각형 커버(정답 삼각형 중 출력에 들어 있는 비율)입니다.
| n | 정확도 | 삼각형 커버 |
|---|---|---|
| 5 | 80.7% | 93.0% |
| 10 | 22.6% | 81.3% |
| 50 | — | 52.8% |
n = 50에서는 완전히 맞힌 경우가 없었습니다. 그래도 정답 삼각형의 절반 이상은 맞혔습니다. 출력에 순서를 정해 주는 문제는 같은 저자들의 후속 논문 Order Matters(Vinyals·Bengio·Kudlur, 2016)에서 더 자세히 다룹니다.
외판원 문제(Travelling Salesman Problem)는 도시 \(n\)개를 모두 한 번씩 들르고 출발한 도시로 돌아오는 가장 짧은 경로를 찾는 문제입니다. 논문은 평면 위의 점을 도시로 보고, 두 도시 사이 거리를 직선거리로 쓰는 경우(평면 대칭 유클리드 TSP)를 풉니다.
앞의 두 문제와 가장 다른 점은 어렵다는 것입니다. TSP는 NP-hard라서, 점이 많아지면 최적해를 빠르게 구하는 알고리즘이 알려져 있지 않습니다. 점 7개만 해도 출발점을 고정하고 방향을 무시하면 서로 다른 경로가 \(6!/2=360\)가지이고, 점 20개면 \(6\times10^{16}\)가지가 넘습니다.
왼쪽은 360가지를 모두 따져서 찾은 최적 경로, 오른쪽은 “아직 안 간 도시 중 가장 가까운 곳으로” 가는 최근접 이웃 탐욕법으로 P1에서 출발한 경로입니다. 주황 숫자는 방문 순서입니다. 길이는 그림 좌표 기준입니다.
최적 경로 · 길이 611
최근접 이웃 탐욕법 · 길이 713
탐욕법은 처음 몇 걸음은 짧게 가지만, 마지막에 남은 먼 도시 P3·P4를 차례로 들렀다가 P1로 돌아오느라 긴 선을 그립니다. P3→P4 선은 P2→P5 선과 교차하기도 합니다. 최적 경로는 이렇게 꼬이는 곳이 없습니다(교차하는 두 선을 풀어 바꾸면 항상 더 짧아지기 때문). 결과적으로 최적 경로보다 17% 깁니다. 매 순간 좋아 보이는 선택이 전체로는 나쁠 수 있다는 것, 그래서 TSP가 어렵다는 것을 보여 주는 예입니다.
경로는 원을 이루므로 어느 도시에서 시작해도 같은 경로입니다. 논문은 표기를 하나로 정하려고 항상 1번 도시에서 출발하도록 적었습니다. 출력은 방문 순서대로 적은 번호열입니다.
⇒ 1 → 4 → 7 → 6 → 2 → 3 → 5 ⇐
볼록 껍질과 달리 출력 길이가 늘 \(n\)으로 정해져 있고, 모든 번호가 정확히 한 번씩 나와야 합니다. 같은 도시를 두 번 고르거나 하나라도 빼먹으면 유효한 경로가 아닙니다. 거꾸로 1 → 5 → 3 → 2 → 6 → 7 → 4로 돌아도 길이는 같습니다.
“모든 번호를 정확히 한 번씩”이라는 조건 때문에 논문은 TSP에서만 빔 서치가 유효한 경로만 고려하도록 제한했습니다. 제한하지 않으면 n > 20에서 10% 이상의 경우 유효한 경로가 하나도 나오지 않았다고 합니다. 이 이야기는 본문 4절과 6절에 이어집니다.
최적해를 정답으로 쓰려면 최적해를 구할 수 있어야 합니다. 논문은 \(O(2^n n^2)\)인 Held-Karp 동적 계획법으로 n = 20까지 정확한 정답을 만들었습니다. 그보다 큰 n은 최적해를 구할 수 없어서, 근사 알고리즘의 출력을 정답 대신 썼습니다. A1·A2는 \(O(n^2)\) 근사 알고리즘이고, A3는 최적의 1.5배 이내를 보장하는 \(O(n^3)\) Christofides 알고리즘입니다.
평가 지표는 출력 경로의 평균 길이이고 짧을수록 좋습니다. 이렇게 하면 정답을 흉내 내는 데 그치지 않고 정답보다 나은 답을 낼 수도 있습니다. 실제로 가장 나쁜 근사 알고리즘 A1의 출력으로 학습한 n = 50 모델이 A1보다 짧은 경로(6.42 대 6.46)를 냈습니다. 반면 5~20으로 학습한 모델은 n = 40부터 크게 무너졌습니다. 자세한 표는 본문 7절에 있습니다.
| 볼록 껍질 | 들로네 삼각분할 | 외판원 문제 | |
|---|---|---|---|
| 답 | 바깥쪽 점들로 만든 다각형 | 외접원이 빈 삼각형들 | 모든 도시를 도는 최단 경로 |
| 출력 단위 | 번호 1개 | 번호 3개 묶음 | 번호 1개 |
| 출력 길이 | 배치마다 다름 (꼭짓점 수 + 1) | \(3(2n-2-h)\) | 항상 \(n\) |
| 각 점이 나오는 횟수 | 0번 또는 1번 (시작점만 2번) | 1번 이상 | 정확히 1번 |
| 논문의 표기 규칙 | 번호가 가장 작은 점부터 반시계 방향, 시작점으로 닫기 | 내심 좌표 사전순, 삼각형 안은 오름차순 | 1번 도시에서 출발 |
| 정답 구하기 | \(O(n\log n)\) 정확 | \(O(n\log n)\) 정확 | NP-hard. n ≤ 20은 Held-Karp \(O(2^n n^2)\), 그 위는 근사 |
| 평가 지표 | 정확도, 면적 커버 | 정확도, 삼각형 커버 | 평균 경로 길이 |
| 디코딩 제한 | 없음 | 없음 | 빔 서치를 유효한 경로로 제한 |
세 문제는 난이도도, 출력 모양도 다르지만 논문은 같은 모델과 같은 하이퍼파라미터로 셋을 모두 풀었습니다. 문제마다 달라진 것은 학습 데이터뿐입니다. 출력이 “입력 중 무엇을 어떤 순서로 고르느냐”라는 공통점만 있으면 포인터 하나로 충분하다는 것이 이 논문이 보여 준 내용입니다.
다음으로본문 1절 · 출력할 칸이 미리 정해져 있다 →