Pointer Networks " target="_blank" title="Pointer Networks" rel="noopener" data-mce-href="http:// Pointer Networks ">http:// Pointer Networks
Pointer Networks
We introduce a new neural architecture to learn the conditional probability of an output sequence with elements that are discrete tokens corresponding to positions in an input sequence. Such problems cannot be trivially addressed by existent approaches suc
arxiv.org
Abstract
이 논문에서는 입력 시퀀스의 위치에 해당하는 이산 토큰들로 구성된 출력 시퀀스의 조건부 확률을 학습하는 새로운 신경 구조를 소개한다. Sequence to Sequence나 뉴럴 튜닝 머신으로는 출력단계에서 클래스의 수가 입력의 크기에 따라 달라지는 문제를 해결할 수 없다. 가변 크기 시퀀스 정렬 및 다양한 조합 최적화 문제들이 경우에 속한다.
이 논문에서 소개하는 포인터 네트(Ptr-Net)는 인코더의 숨겨진 단위들을 디코더 단계마다 콘텍스트 벡터로 혼합하는 데 주의를 사용하는 대신, 출력으로 입력 시퀀스의 멤버를 선택하기 위한 포인터로 주의를 사용하여 위의 문제를 해결한다.
Ptr-Net이 평면 볼록 껍질 찾기, 델로네 삼각 분할 계산, 평면 여행 판매원 문제 등의 도전적인 기하학적 문제에 대한 근사 해결책을 학습하는 데 사용될 수 있음을 보이고자 한다.
1. Introduction
RNN(순환 신경망)은 구조 상 입력과 출력이 고정된 프레임 속도에서만 사용 가능하게 제한되어 있었다. 최근에 도입된 Sequence to Sequence 방식은 하나의 RNN을 사용하여 입력 시퀀스를 임베딩으로 매핑하고 다른 하나(또는 같은) RNN을 사용하여 임베딩을 출력 시퀀스로 매핑함으로써 이러한 제약을 제거했지만, 그림에서 보이는 바와 같이 출력 사전의 크기를 미리 고정해야 한다는 한계가 있다. 이러한 제약 때문에 입력 시퀀스의 길이에 따라 출력 사전의 크기가 달라지는 조합 문제에 이 프레임워크를 직접 적용할 수 없다.
이러한 제한을 해결하기 위해 주의 메커니즘을 재목적화하여 입력 요소들을 가리키는 포인터를 생성하고, 이 구조를 포인터 네트워크(Ptr-Net)라고 부른다.
※ Pointer Network의 특징
- 간단하면서도 효과적: Softmax 함수의 확률분포를 포인터로 사용
- 훈련 문제보다 더 많은 점을 가진 테스트 문제에 일반화됨
- 소규모(n ≤ 50) 여행 판매원 문제(TSP) 근사 해결기: 순수하게 데이터 기반 접근 방식이 계산상으로 불가능한 문제들에 대한 근사 해결책을 학습
2. Models
2.1. Sequence to Sequence
주어진 훈련 쌍 $(P, C^{P})$에 대해, Sequence to Sequence 모델은 조건부 확률 $p(C^{P}|P;\theta)$를 계산한다. 이는 확률의 연쇄 법칙을 추정하기 위해 사용되는 매개 변수화된 모델 RNN을 통해 계산됨
$$p(C^{P}|P;\theta) = \prod_{i=1}^{m(P)} p_{\theta}(C_{i}|C_{1}, C_{2},...C_{n-1}, P;\theta )$$
여기서 $P = {\left\{P_{1}, P_{2},..., P_{n} \right\}}$ 는 n개의 시퀀스 벡터이고, $C^{P} = {\left\{C_{1}, C_{2},..., C_{m_{(P)}} \right\}}$ 는 m(P) 개의 시퀀스 지수이다.
모델의 파라미터는 훈련 셋의 조건부 확률을 최대화시킴으로써 학습된다.
$$\theta^{*} = argmax_{(\theta)} \sum_{P, C^{P}}^{}log(p(C^{P}|P;\theta))$$
2.2. Content Based Input Attention
기본 Sequence to Sequence 모델은 입력 시퀀스 P의 끝에 있는 인식 RNN의 고정된 차원 상태를 사용하여 전체 출력 시퀀스 $C^{P}$를 생성함. 이는 생성 모델로 흐를 수 있는 정보량과 계산량에 제약을 가함. Attention 모델은 인코더 및 디코더 RNN에 인코더 RNN 상태의 전체 시퀀스에 대한 Attention 메커니즘을 사용하는 추가적인 신경망으로 문제 완화.
인코더 hidden states: $(e_{1}, e_{2},..., e_{n})$
디코더 hidden states: $(d_{1}, d_{2},..., d_{n})$
매 시점 Attention Vector 계산법:
$u_{j}^{i} = v^{T}tanh(W_{1}e_{j} + W_{2}d_{i})$ $ j \in (1,2,...,n)$
$a_{j}^{i} = softmax(u_{j}^{i})$ $ j \in (1,2,...,n)$
$d_{i}^{'} = \sum_{j=1}^{n}a_{j}^{i}e_{j}$
Softmax 함수는 벡터 $u$를 정규화시키는 역할을 한다. 이때, 정규화된 $u$ 벡터는 'Attention Mask"로 작용한다.
$v$, $W_{1}$, $W_{2}$는 모델의 학습 파라미터이다. 모든 실험에서 인코더와 디코더가 동일한 은닉층 차원을 가지므로 $v$는 벡터이고, $W_{1}$, $W_{2}$는 정사각형 행렬이다. 마지막으로 $d_{i}$ 와 $d_{i}^{'}$ 는 연결된 상태로 예측을 수행하고 재귀 모델의 다음 시간 단계로 전달하는 데 사용되는 은닉 상태로 활용된다.
이 모델은 2.1의 모델보다 확실히 나은 결과를 보이지만 여전히 출력 크기가 입력 크기에 구애받는 문제들에 대해서는 적용이 힘들다.
2.3. Pointer Network
앞선 문제들을 해결하기 위해, $p(C_{i}|C_{1}, C_{2}, ..., C_{i-1}, P)$를 $u_{j}^{i} = v^{T}tanh(W_{1}e_{j} + W_{2}d_{i})$ 식을 이용해 해결한다.
$$p(C_{i}|C_{1}, C_{2}, ..., C_{i-1}, P) = softmax(u^{i})$$
다만, 여기서는 인코더 상태 $e_{j}$를 혼합하여 디코더에 추가 정보를 전파하는 대신, $u_{j}^{i}$를 입력 요소들을 가리키는 포인터로 사용.
3. Solving Problems
Inputs: 평면 위의 점 $P = {\left\{P_{1}, P_{2},..., P_{n} \right\}}$, $P_{j} = (x_{j}, y_{j})$
Outputs: 시퀀스 $C^{P} = {\left\{C_{1}, C_{2},..., C_{m_{(P)}} \right\}}$
3.1. Convex Hull: 점들을 모두 포함하는 가장 작은 볼록 다각형
- $P_{j}$ : [0,1] x [0,1]의 범위에서 균등히 분포된 벡터들
- $C_{i}$ : 시퀀스 P 내의 특정 위치를 가리키는 인덱스
Input $P = {\left\{P_{1}, P_{2},..., P_{10} \right\}}$
Output $C^{P} = ( →, 2, 4, 3, 5, 6, 7, 2, ← )$ = Convex Hull
3.2. Delaunay Triangulation: 각 삼각형의 내접원에 다른 모든 점들이 포함되지 않음
- $P_{j}$ : [0,1] x [0,1]의 범위에서 균등히 분포된 벡터들
- $C_{i}$ : 시퀀스 P 내의 특정 위치를 가리키는 인덱스
Input $P = {\left\{P_{1}, P_{2},..., P_{5} \right\}}$
Output $C^{P} = ( →, (1, 2, 4), (1, 4, 5), (1, 3, 5), (1, 2, 3), ← )$ = Deluanay Triangulation
3.3. Travelling Salesman Problem: 모든 지점을 한 번씩 방문하고 출발점으로 돌아오는 최단경로
4. Empirical Results
모든 데이터셋에 대해 동일한 단층 LSTM 모델 사용:
(hidden size = 256 or 512, stochastic learning rate = 1.0, batch = 128)
4.1. Convex Hull
실험에서는 정확도와 실제 볼록 껍질이 포함하는 영역을 덮는 정도(accuracy and area covered)라는 두 가지 척도를 보고. 정확도를 계산하기 위해, 같은 다각형을 나타내는 두 출력 시퀀스 C1과 C2를 동일한 것으로 간주함
결과: Ptr-Net으로 달성한 영역 커버리지는 거의 100%에 가깝다. 실수한 부분은 보통 일렬로 나열된 점들에 대해서 나타남.
- LSTM은 인 경우에 매우 낮은 정확도(1.9%)를 보이며, 영역 커버리지에서 실패(Fail).
- Attention 메커니즘을 추가한 LSTM은 정확도가 38.9%로 향상되었고, 영역 커버리지는 99.7% 달성
- Ptr-Net는 인 경우에 72.6%의 정확도와 99.9%의 영역 커버리지를 달성하여 가장 뛰어난 성능
표 하단의 결과는 훈련 범주( n = 5~50)를 벗어난 부분에 대해서도 어느 정도의 성능을 발휘할 수 있음이 보인다.
4.2. Delaunay Triangulation
4.1. 의 경우에서 점들을 삼각형으로 연결하는 작업을 수행. 결과는 비슷한 결과 도출
4.3. Travelling Salesman Problem
- 와 에서는 최적 값에 근접하거나 일치한다.
- 에서 A1 알고리즘 데이터로 훈련한 경우와 A3 알고리즘 데이터로 훈련한 경우 모두 Ptr-Net이 해당 알고리즘보다 낫다.
- 부터 까지 훈련된 데이터로는 와 에서 좋은 성능을 보이지만, 과 에서는 성능이 저하된다. 에서는 특히 성능이 저하되어 7.66의 값을 보이고 있으나, 이는 여전히 우연히 얻을 수 있는 결과보다는 좋은 수치다.
이 결과들은 Ptr-Net이 특정 범위 내에서는 TSP 문제에 대해 매우 효과적으로 일반화할 수 있음을 보여주지만, 더 복잡한 문제나 더 큰 규모의 문제에 대해서는 일반화하는 데 한계가 있음을 나타냄
5. Conclusions
이 논문에서는 Ptr-Net이라는 새로운 아키텍처를 소개하며, 이는 주어진 시퀀스 P에 대해 이산 토큰의 시퀀스 $C^{P}$의 조건부 확률을 학습한다. 여기서 $C^{P}$는 P 내 위치에 해당하는 토큰들로 구성된다. Ptr-Net은 가변 크기의 입력에 대해 작동하며 세 가지 다른 조합 최적화 문제에 대한 해결책을 학습하는 데 사용될 수 있음을 보여준다.
기존 방법들, 예를 들어 RNNSearch, 메모리 네트워크, 뉴럴 튜링 머신들도 입력 처리에 주의 메커니즘을 사용했지만, 가변 출력 사전에 발생하는 문제를 직접 해결하지는 못했다. 이 논문에서는 주의 메커니즘이 출력에 적용될 수 있음을 보여준다.
Q. 위의 조합 최적화 문제들은 정적인 환경들에 관해 다룬다. 그러나 우리의 환경은 동적으로 시간에 따라 변하는 환경인데 배달 경로 최적화 문제에서 환경이 동적으로 변할 때 (예: 교통 상황 변화, 긴급 배달 명령 추가 등) Pointer Network가 어떻게 적응할 수 있나?