seq2seq · 어텐션 · 조합 최적화

Pointer Networks — 어텐션으로 입력을 가리키기

점 10개의 볼록 껍질을 구하라고 하면 답은 “2번, 4번, 3번, 5번…” 같은 입력의 번호입니다. 그런데 seq2seq의 출력층은 칸 수가 학습할 때 정해져서, 점이 11개가 되면 “11번”이라고 말할 칸이 없습니다. Pointer Network(Vinyals·Fortunato·Jaitly, NeurIPS 2015)는 이 문제를 어텐션 한 줄을 바꿔서 풉니다. 어텐션 가중치로 인코더 상태를 섞지 않고, 그 가중치 분포를 그대로 출력으로 쓰는 것입니다.

0. 먼저: 논문이 푼 세 문제

이 페이지의 예제는 대부분 볼록 껍질(convex hull)입니다. 평면에 흩어진 점들을 모두 감싸는 가장 작은 볼록 다각형이고, 출력은 그 꼭짓점의 번호를 둘레를 따라 적은 것입니다. 논문은 여기에 들로네 삼각분할과 외판원 문제(TSP)를 더해 세 문제를 풀었습니다. 셋 다 답이 “입력 중 몇 번째 점”의 나열입니다.

보충 페이지Pointer Networks가 푼 세 문제 →볼록 껍질 · 들로네 삼각분할 · 외판원 문제를 같은 점 7개로 그림과 함께 설명합니다. 각 문제의 출력 표기 규칙(예: ⇒ 3 → 6 → 4 → 5 → 3 ⇐), 정답 데이터를 만든 방법, 평가 지표를 정리했습니다. 세 문제가 처음이라면 먼저 읽고 오세요.

세 문제 중 볼록 껍질이 첫 과제로 쓰인 이유는 답의 생김새에 있습니다.

답에 새로운 값이 하나도 없습니다. 출력은 모두 “입력 중 몇 번째 점”입니다.
나올 수 있는 번호의 범위가 입력 개수에 따라 바뀝니다. 점이 7개면 1~7번, 50개면 1~50번이 답에 나올 수 있습니다.
정답을 쉽게 만들 수 있습니다. 정확한 알고리즘이 이미 있어서($O(n\log n)$) 학습용 정답을 얼마든지 만들 수 있습니다. 그래서 신경망이 규칙을 데이터만 보고 배울 수 있는지 시험하기 좋습니다.

두 번째 특징 때문에 평범한 seq2seq는 곤란해집니다. 다음 절에서 바로 확인해 봅니다.

1. 출력할 칸이 미리 정해져 있다

seq2seq 디코더는 스텝마다 출력층 $W_o$로 점수를 만들고 softmax를 씌웁니다. 번역이라면 출력 사전은 단어 3만~5만 개쯤이고, 학습이 끝나면 바뀌지 않습니다.

$$p(C_i\mid C_1,\dots,C_{i-1},\mathcal P)=\operatorname{softmax}(W_o\,d_i),\qquad W_o\in\mathbb R^{K\times h}$$ K는 출력 사전의 크기입니다. 행렬 모양에 박혀 있어서 모델을 다시 만들지 않으면 바꿀 수 없습니다.

볼록 껍질 문제로 seq2seq를 학습시키면 출력 사전은 “1번 점”부터 “n번 점”까지에 시작·끝 기호가 붙은 것이 됩니다. 논문도 이 점을 짚습니다. 출력 사전 크기가 n으로 고정되니 n마다 모델을 따로 학습해야 한다는 것입니다. 아래에서 점 개수를 바꿔 보세요. 왼쪽 모델은 점 5개로 학습한 seq2seq입니다.

데모 1 · 점이 6개가 되면 seq2seq는 ‘6번’을 말할 수 없다

초록 선이 볼록 껍질입니다. 정답 순서는 논문처럼 껍질 위에서 번호가 가장 작은 점부터 반시계 방향으로 적고, 끝에 시작점을 한 번 더 적어 닫습니다.

입력 점 개수 n 7

정답 출력 순서

seq2seq (n = 5로 학습) — 출력층의 칸

Ptr-Net — 출력 칸 = 지금 들어온 입력

seq2seq가 낼 수 없는 정답 토큰0

Ptr-Net 출력 분포의 칸 수8

점이 3~5개일 때도 seq2seq가 멀쩡한 것은 아닙니다. 칸이 남을 뿐, 학습 때와 길이가 다르면 인코더가 보던 입력 분포가 달라집니다. 점이 6개를 넘으면 답에 6 이상의 번호가 들어가는 순간 그 토큰은 아예 낼 수 없습니다. 빨간 점선 칸이 그런 토큰입니다.

2. 정답이 ‘입력의 번호’인 문제들

논문은 평면 위의 점 집합 $\mathcal P=\{P_1,\dots,P_n\}$을 받아 번호열 $\mathcal C^{\mathcal P}=\{C_1,\dots,C_{m(\mathcal P)}\}$을 내는 문제 세 개를 풉니다. 점은 모두 $[0,1]\times[0,1]$에서 고르게 뽑았습니다.

볼록 껍질 — 모든 점을 감싸는 가장 작은 볼록 다각형의 꼭짓점. 정확한 알고리즘은 $O(n\log n)$입니다.
들로네 삼각분할 — 어떤 삼각형의 외접원 안에도 다른 점이 없는 삼각분할. 출력은 번호 세 개짜리 묶음의 나열입니다. 예: $\{\Rightarrow,(1,2,4),(1,4,5),(1,3,5),(1,2,3),\Leftarrow\}$
외판원 문제(TSP) — 모든 도시를 한 번씩 들르고 돌아오는 가장 짧은 경로. NP-hard입니다. 학습용 정답은 $O(2^n n^2)$인 Held-Karp 동적 계획법으로 n = 20까지 만들었습니다.

세 문제를 그림으로 자세히 보려면 보충 페이지를 참고하세요. 셋 다 출력에 새로운 값이 하나도 없습니다. 답은 늘 입력 중 무엇을 어떤 순서로 고르느냐입니다. 아래 데모는 같은 점 집합에 볼록 껍질과 TSP를 실제로 풀어서 출력 번호열을 보여 줍니다. TSP 최적해는 논문처럼 Held-Karp로 구합니다.

데모 2 · 같은 입력, 다른 번호열

빈 곳을 누르면 점이 추가되고(최대 12개), 점을 끌면 옮겨집니다. 출력 번호열은 점을 움직일 때마다 다시 계산됩니다.

출력 번호열

출력을 한 줄로 쓰는 방법이 여러 가지면 학습이 흔들립니다. 그래서 논문은 표기를 하나로 정했습니다. 볼록 껍질은 “번호가 가장 작은 점부터 반시계 방향, 끝에 시작점을 한 번 더”, TSP는 “항상 1번 도시에서 출발”, 들로네는 “삼각형을 내심 좌표의 사전순으로, 각 삼각형 안의 번호는 오름차순으로” 적습니다. 들로네 쪽은 이렇게 순서를 정하지 않았을 때 결과가 나빴다고 적혀 있습니다.

3. 어텐션을 섞지 말고 가리키게

저자들은 처음에 볼록 껍질을 평범한 LSTM seq2seq로 풀었습니다. 그러자 껍질 위의 점이 입력 뒤쪽에 늦게 나올수록 정확도가 떨어졌습니다. 그래서 디코더가 입력 전체를 언제든 볼 수 있게 Bahdanau 어텐션을 붙였고, 성능이 크게 올랐습니다. 이때 어텐션이 어디를 보는지 들여다봤더니 입력 쪽의 정답 점을 ‘가리키고’ 있었다고 합니다. Ptr-Net은 여기서 나왔습니다.

인코더 상태를 $e_1,\dots,e_n$, 디코더 상태를 $d_i$라고 할 때, 논문 식 (3)의 어텐션은 이렇습니다.

$$u^i_j=v^\top\tanh(W_1e_j+W_2d_i),\qquad a^i_j=\operatorname{softmax}(u^i)_j,\qquad d'_i=\sum_{j=1}^n a^i_j\,e_j$$ 어텐션: 점수 → 분포 → 가중 평균 $d'_i$. $d'_i$를 $d_i$에 이어 붙여 고정 크기 출력층으로 예측합니다.

Ptr-Net은 마지막 단계를 지웁니다.

$$u^i_j=v^\top\tanh(W_1e_j+W_2d_i),\qquad p(C_i\mid C_1,\dots,C_{i-1},\mathcal P)=\operatorname{softmax}(u^i)$$ Ptr-Net: 점수 → 분포 → 끝. 분포의 길이가 n이므로 출력 사전도 저절로 n칸이 됩니다. 다음 스텝 디코더 입력으로는 방금 고른 점의 좌표 $P_{C_{i-1}}$를 그대로 넣습니다.

파라미터 $v, W_1, W_2$의 크기는 은닉 차원만으로 정해지고 n과 상관이 없습니다. 같은 가중치가 점 5개에도, 500개에도 그대로 쓰입니다. 끝 기호 $\Leftarrow$는 논문 그림 1(b)처럼 인코더 맨 앞에 특별한 자리를 하나 두고, 끝내고 싶을 때 그 자리를 가리키게 해서 처리합니다.

데모 3 · 섞으면 입력 사이 어딘가, 가리키면 입력 중 하나

2차원 인코더 상태 e₁~e₅와 디코더 상태 d(파란 화살표)입니다. 화살표 끝을 끌어 보세요. 그림을 단순하게 하려고 점수는 내적 $u_j=e_j\cdot d$로 계산합니다(논문은 위의 덧셈형 점수를 씁니다). d가 길수록 분포가 뾰족해집니다.

어텐션 출력 d′—

포인터 출력—

핵심

어텐션의 결과 d′는 e들의 볼록 결합이라 늘 e들이 만드는 다각형 안쪽에 있고, 분포가 아주 뾰족하지 않으면 어느 입력과도 같지 않습니다. 포인터는 그 분포에서 칸 하나를 고를 뿐이라 결과가 반드시 입력 중 하나입니다. 논문은 좌표를 직접 회귀하게 하는 방법도 언급하면서, 그러면 출력이 입력에 정확히 대응한다는 보장이 없어 긴 시퀀스에서 예측이 흐려진다고 지적합니다.

4. 한 스텝씩 따라가기: 포인터는 다음 점을 이렇게 고른다

Ptr-Net의 디코딩은 언어 모델이 문장을 만드는 방식과 똑같습니다. 매 스텝 다음에 올 것 하나를 고르고, 방금 고른 것을 다음 스텝의 입력으로 넣고, 끝 기호를 고르면 멈춥니다. 다른 점은 고르는 후보뿐입니다.

	자연어 생성	Pointer Network
매 스텝 하는 일	다음 토큰 하나 고르기	다음 점 하나 고르기
다음 스텝 입력	방금 고른 토큰	방금 고른 점의 좌표
끝내는 방법	`<EOS>` 토큰 선택	끝 기호 ⇐ 자리 선택
고르는 후보	고정된 단어 사전	이번에 들어온 입력의 점들

한 스텝 안에서 일어나는 계산을 적으면 이렇습니다. 무엇이 한 번만 계산되고 무엇이 매번 바뀌는지가 핵심입니다.

$$\underbrace{e_1,\dots,e_n}_{\text{인코더가 한 번만 계산}}\qquad d_i=\mathrm{LSTM}\big(d_{i-1},\;\underbrace{P_{C_{i-1}}}_{\text{직전에 고른 점}}\big)\qquad u^i_j=v^\top\tanh(W_1e_j+W_2d_i)\qquad p=\operatorname{softmax}(u^i)$$ 후보 점들의 벡터 $e_j$는 처음에 만들어진 뒤 끝까지 그대로입니다. 매 스텝 바뀌는 것은 질의(query) 역할을 하는 디코더 상태 $d_i$ 하나뿐입니다. 그래서 “직전에 무엇을 골랐느냐에 따라 다음 선택이 달라지는” 효과는 전부 $d_i$를 통해 들어옵니다. 학습할 때는 모델이 실제로 고른 점 대신 정답의 직전 점을 넣습니다(교사 강요).

보충 페이지 그림 1의 점 7개로 실제 순서를 따라가 봅니다. 정답은 ⇒ 3 → 6 → 4 → 5 → 3 ⇐입니다. 후보는 끝 기호 ⇐ 자리까지 8칸입니다. 볼록 껍질은 답의 길이가 입력마다 다르기 때문에, 언제 멈출지도 모델이 골라야 합니다.

데모 4 · 볼록 껍질을 한 스텝씩 디코딩하기

원의 크기와 숫자가 그 스텝에서 각 후보를 가리킬 확률입니다. 주황 선은 지금까지 출력한 순서입니다. 확률은 학습이 잘된 모델이라면 이런 모양이 나온다는 것을 보이려고 정한 예시 값입니다.

마스크 적용 (후속 연구 방식)

스텝1 / 6

디코더 입력⇒

이번 선택P3

지금까지의 출력

P1, P2, P7은 어떻게 빠지는가

스텝을 끝까지 넘겨 보면 P1, P2, P7은 무언가에 의해 지워지는 것이 아니라, 여섯 스텝 내내 후보로 남아 있지만 한 번도 뽑히지 않습니다. 마스크를 켜도 이 점들은 지워지지 않습니다. 마스크는 이미 고른 점만 지우기 때문입니다.

이 점들의 확률이 매번 낮게 나오는 것은 모델이 그렇게 배웠기 때문입니다. 학습 데이터 100만 개의 정답에는 안쪽 점이 한 번도 나오지 않습니다. 그래서 모델은 “다른 점들에 둘러싸인 점에는 낮은 점수를 준다”는 판단을 $W_1, W_2, v$와 인코더 가중치에 새겨 넣습니다. 꼭짓점을 다 돌고 시작점으로 돌아왔다고 판단하면 안쪽 점 대신 ⇐에 높은 점수를 줍니다.

후보	처리 방식
P3, P6, P4, P5	높은 점수로 선택됨. P3은 다각형을 닫으려고 마지막에 한 번 더 선택됨
P1, P2, P7	끝까지 후보로 남지만 학습된 점수가 낮아서 선택되지 않음
⇐	다 돌았다고 판단하면 선택되어 디코딩 종료

그래서 “안쪽 점은 고르지 마라”는 어떤 장치도 보장하지 않습니다. 순전히 모델이 배운 판단이고, 학습이 덜 됐거나 처음 보는 배치가 들어오면 틀릴 수 있습니다. 논문도 틀린 경우가 대부분 점들이 거의 일직선으로 놓인 곳이었다고 적고 있습니다. 안쪽 점인지 가장자리 점인지 애매해지는 배치입니다.

같은 점을 두 번 고르지 않게 하는 두 가지 방법

이미 고른 점을 또 고르지 않게 하는 방법은 두 가지입니다.

디코더 상태가 기억하게 학습시키기 (원 논문의 볼록 껍질·들로네 실험). 논문은 이 두 문제에서 디코더를 제한하지 않았습니다. LSTM 디코더는 P3, P6, P4…를 차례로 입력받으면서 “어디까지 왔는지”를 $d_i$에 쌓아 갑니다. 정답에는 같은 꼭짓점이 (닫는 점을 빼고) 두 번 나오지 않으므로, 모델은 이미 지나온 점에 낮은 점수를 주도록 배웁니다. 하지만 배운 것이라 보장은 없습니다.
마스크로 지우기. 어텐션과 별개로 “이미 고른 점” 장부를 들고 다니면서, 그 칸의 점수 $u_j$를 $-\infty$로 만들어 softmax에서 아예 빼 버립니다. 논문은 TSP에서 빔 서치가 유효한 경로만 보도록 제한했는데, 그러지 않으면 n > 20에서 10% 이상의 경우 도시를 반복하거나 빼먹은 경로만 나왔다고 합니다. 이후 TSP 연구들(Bello 외 2016, Kool 외 2019)은 디코더에서 방문한 도시를 마스크로 지우는 방식을 씁니다.

정리

매 스텝 들어오는 입력(직전에 고른 점)은 질의 $d_i$를 바꾸는 데만 쓰입니다. 어텐션은 그 질의로 모든 후보에 점수를 다시 매길 뿐, 무언가를 “빼는” 연산은 없습니다. 안쪽 점이 빠지는 것은 학습된 낮은 점수 덕분이고, 같은 점을 두 번 고르지 않는 것은 학습된 디코더 상태나 어텐션 바깥의 마스크가 맡습니다.

5. 브라우저에서 학습하는 미니 Ptr-Net

이제 진짜로 학습시켜 봅니다. 과제는 숫자 정렬입니다. 0~1 사이 숫자 n개를 받아 작은 것부터 차례로 가리키면 됩니다. 논문 결론에서 다음 과제로 꼽은 것이 정렬이기도 합니다.

브라우저에서 몇 초 안에 돌리려고 LSTM은 빼고 포인터 부분만 남겼습니다.

$$u^i_j=v^\top\tanh\big(\underbrace{A\,x_j+a_0}_{W_1e_j}+\underbrace{B\,x_{C_{i-1}}+b_0}_{W_2d_i}\big),\qquad p(C_i)=\operatorname{softmax}(u^i)$$ 은닉 차원 16. 인코더는 숫자 하나를 16차원으로 펴는 선형 변환이고, 디코더 상태는 “직전에 가리킨 숫자”만 봅니다(첫 스텝에는 학습되는 시작 벡터 s). 파라미터는 A·a₀·B·b₀·s·v 각 16개, 모두 96개입니다. 학습은 n = 5~10짜리 무작위 수열, 교사 강요(teacher forcing), 교차 엔트로피, Adam(학습률 0.01, 배치 32)으로 합니다.

논문 모델의 디코더는 LSTM이라 지금까지 무엇을 골랐는지 기억합니다. 이 미니 모델은 직전 하나만 보므로, “이미 고른 위치는 다시 고르지 않는다”는 규칙을 마스크로 줄지 말지가 중요해집니다. 마스크를 켜면 이미 가리킨 위치의 점수를 $-\infty$로 만들어 softmax에서 뺍니다.

데모 5 · 정렬을 배우는 포인터

아래 행렬의 행은 디코딩 스텝, 열은 입력 위치(위에 적힌 값이 입력 숫자)입니다. 칸이 진할수록 그 스텝에서 그 위치를 가리킬 확률이 높습니다. 초록 테두리가 정답, 점이 모델이 실제로 고른 위치(틀리면 빨강)입니다. 디코딩은 모델이 스스로 고른 값을 다음 입력으로 넣는 탐욕적 방식입니다.

마스크 (이미 가리킨 위치 제외)

반복0

스텝당 손실—

n = 10 수열 정답률—

시험 수열 길이 n 8

정답 순서 / 모델 출력

학습 전에는 모든 칸이 비슷하게 흐립니다. 몇백 번 반복하면 행렬에 대각선 대신 정렬 순서를 따라가는 지그재그 경로가 진하게 떠오릅니다. 입력 순서는 무작위인데 경로가 하나로 이어지는 이유는, 각 행이 “지금까지 고른 것 다음으로 작은 수”를 가리키기 때문입니다.

6. 같은 가중치로 더 긴 입력 — 그리고 마스크

데모 5의 모델은 길이 5~10 수열만 봤습니다. 그런데 파라미터 96개 중 어느 것도 n에 묶여 있지 않으니, 길이 50짜리 수열에도 그대로 돌릴 수 있습니다. seq2seq라면 출력층이 맞지 않아 실행조차 안 되는 상황입니다. 아래 버튼은 지금 모델을 길이마다 수열 150개로 시험합니다.

데모 6 · 길이별 정답률과 ‘유효하지 않은 출력’

파랑 = 수열 전체를 맞힌 비율, 초록 = 위치별로 맞힌 비율, 빨강 점선 = 같은 위치를 두 번 이상 가리켜 순열이 아니게 된 비율. 회색 띠가 학습 때 본 길이입니다. 다시 평가하면 직전 결과가 옅은 선으로 남습니다.

수열 정답률 위치별 정답률 유효하지 않은 출력

데모 5에서 모델을 학습시킨 뒤 눌러 보세요.

권장 실험 순서는 이렇습니다.

마스크를 켠 채 학습하고 평가합니다. 길이 50에서도 거의 다 맞힙니다. 마스크가 이미 고른 숫자를 지워 주므로, 모델은 매 스텝 “남은 것 중 가장 작은 수”만 찾으면 됩니다. 이 규칙에는 n이 들어 있지 않습니다.
마스크를 끄고 가중치를 초기화한 뒤 다시 학습하고 평가합니다. 이번에는 “직전 숫자보다 크면서 가장 가까운 수”를 스스로 배워야 합니다. 학습 길이에서도 정답률이 떨어지고, 길이가 길어질수록 같은 숫자를 또 가리키는 출력이 급격히 늘어납니다. 숫자 사이 간격이 약 1/n로 좁아져 구분이 어려워지기 때문입니다.

논문에서도 같은 일이 있었습니다. TSP에서는 빔 서치가 유효한 경로만 고려하도록 제한했는데, 그러지 않으면 모델이 도시를 두 번 들르거나 빼먹었고 n > 20에서는 10% 이상의 경우에 유효한 경로를 하나도 내지 못했다고 합니다. 반면 볼록 껍질과 들로네 실험에서는 디코더를 제한하지 않았습니다. 포인터는 “입력 중 하나”만 보장할 뿐 “각 입력을 한 번씩”까지 보장하지는 않습니다.

7. 논문 실험 결과

모든 실험에서 은닉 유닛 256개 또는 512개짜리 단층 LSTM을 썼고, 학습률 1.0의 SGD, 배치 128, 가중치 초기화 범위 −0.08~0.08, 기울기 L2 클리핑 2.0, 학습 쌍 100만 개였습니다. 저자들은 하이퍼파라미터 탐색을 거의 하지 않고 세 문제에 같은 설정을 썼다고 밝힙니다.

볼록 껍질 (표 1)

방법	학습 n	시험 n	정확도	면적 커버
LSTM seq2seq	50	50	1.9%	FAIL
+ 어텐션	50	50	38.9%	99.7%
Ptr-Net	50	50	72.6%	99.9%
LSTM seq2seq	5	5	87.7%	99.6%
Ptr-Net	5–50	5	92.0%	99.6%
LSTM seq2seq	10	10	29.9%	FAIL
Ptr-Net	5–50	10	87.0%	99.8%
Ptr-Net	5–50	50	69.6%	99.9%
Ptr-Net	5–50	100	50.3%	99.9%
Ptr-Net	5–50	200	22.1%	99.9%
Ptr-Net	5–50	500	1.3%	99.2%

정확도는 다각형이 정답과 완전히 같은 비율이고, 면적 커버는 출력 다각형이 진짜 껍질 넓이의 몇 %를 덮는지입니다(출력이 자기 교차 없는 다각형일 때만 계산하고, 그런 실패가 1%를 넘으면 FAIL). 기준 모델들은 시험할 n으로 따로 학습해야 했지만, Ptr-Net은 길이 5~50을 섞어 학습한 모델 하나로 모든 줄을 채웠습니다. 학습 때 본 적 없는 n = 500에서도 면적은 99.2%를 덮습니다. 틀린 경우는 대부분 점이 일직선에 가깝게 놓인 곳이었다고 합니다.

들로네 삼각분할

n = 5에서 정확도 80.7%·삼각형 커버 93.0%, n = 10에서 22.6%·81.3%였습니다. n = 50에서는 완전히 맞힌 경우가 없었고 삼각형 커버는 52.8%였습니다.

외판원 문제 (표 2, 경로 길이 — 짧을수록 좋음)

n	최적	A1	A2	A3	Ptr-Net
5	2.12	2.18	2.12	2.12	2.12
10	2.87	3.07	2.87	2.87	2.88
50 (A1 데이터로 학습)	N/A	6.46	5.84	5.79	6.42
50 (A3 데이터로 학습)	N/A	6.46	5.84	5.79	6.09
20 (5–20 학습)	3.83	4.24	3.86	3.85	3.88
25 (5–20 학습)	N/A	4.71	4.27	4.24	4.30
30 (5–20 학습)	N/A	5.11	4.63	4.60	4.72
40 (5–20 학습)	N/A	5.82	5.27	5.23	5.91
50 (5–20 학습)	N/A	6.46	5.84	5.79	7.66

A1·A2는 $O(n^2)$ 근사 알고리즘, A3는 최적의 1.5배 이내를 보장하는 $O(n^3)$ Christofides 알고리즘입니다. 눈여겨볼 줄이 둘 있습니다.

A1 데이터로 학습한 n = 50: 가장 나쁜 근사 알고리즘 A1의 출력을 정답 삼아 배웠는데, 결과 경로(6.42)가 A1 자신(6.46)보다 짧습니다. 흉내 내던 알고리즘을 넘어선 것입니다.
5–20으로 학습해 더 긴 n에 적용: 25에서는 거의 완벽하고 30도 괜찮지만, 40부터 무너집니다(50에서 7.66). 볼록 껍질이 학습 길이의 10배까지 버틴 것과 대조적인데, 저자들은 TSP를 푸는 알고리즘이 $O(n\log n)$보다 훨씬 복잡하기 때문일 수 있다고 봅니다.

8. 그다음: 복사하는 포인터

“입력을 가리킨다”는 발상은 기하 문제 밖에서 더 오래 쓰였습니다. 요약·질의응답·대화에서 자주 문제가 되는 것은 사전에 없는 단어(OOV)입니다. 사람 이름이나 지명은 원문에 있는데 출력 사전에는 없어서 [UNK]로 나옵니다. 포인터를 쓰면 원문 위치를 가리켜 그 단어를 복사할 수 있습니다.

대표적인 형태가 See·Liu·Manning(ACL 2017)의 pointer-generator입니다. 디코더가 스텝마다 “생성할 확률” $p_{\text{gen}}$을 내고, 사전에서 생성하는 분포와 어텐션으로 복사하는 분포를 섞습니다.

$$P(w)=p_{\text{gen}}\,P_{\text{vocab}}(w)+(1-p_{\text{gen}})\sum_{i:\,w_i=w}a_i$$ 두 번째 항이 Ptr-Net의 포인터입니다. 원문에 같은 단어가 여러 번 나오면 그 위치들의 어텐션이 더해집니다. 사전에 없는 단어는 $P_{\text{vocab}}(w)=0$이라 복사로만 나올 수 있습니다.

데모 7 · 생성할까, 복사할까

요약문의 첫 단어를 고르는 스텝입니다. 원문 “Okonkwo won the Valencia marathon on Sunday”에서 Okonkwo와 Valencia(★)는 사전에 없습니다. 최종 분포의 주황은 원문에서만, 파랑은 사전에서만, 보라는 양쪽에서 확률을 받은 단어입니다. 어텐션과 사전 분포 숫자는 설명을 위해 정한 예시 값입니다.

p_gen (생성 확률) 0.30

원문 어텐션 a_i (복사 분포)

사전 분포 P_vocab (생성 분포)

최종 분포 P(w)

고르는 단어—

같은 계열의 연구를 몇 가지 더 꼽으면 이렇습니다.

CopyNet (Gu 외, ACL 2016) — 생성 모드와 복사 모드의 점수를 한 softmax 안에서 함께 정규화합니다.
Pointer Sentinel (Merity 외, 2016) — 언어 모델에서 최근 문맥의 단어를 가리키는 포인터와 일반 softmax를 섞습니다.
Order Matters (Vinyals·Bengio·Kudlur, ICLR 2016) — 같은 저자가 숫자 정렬 같은 집합 입력 문제에서 입력·출력 순서가 학습에 미치는 영향을 다룹니다.
Neural Combinatorial Optimization with RL (Bello 외, 2016) — Ptr-Net을 지도 학습 대신 강화 학습(경로 길이를 보상으로)으로 학습해, 최적해 정답 없이 TSP를 풉니다.
Attention, Learn to Solve Routing Problems! (Kool 외, ICLR 2019) — 인코더를 Transformer로 바꾸고 디코더는 여전히 입력 노드를 가리키는 구조로 경로 문제를 풉니다.