조합 최적화 분야에 대해 서베이하기 전에는 RNN 특히 주변에서 많이 이야기하는 LSTM 등의 알고리즘은 자연어 처리에서만 사용되는 줄 알았는데 TSP 등 최적화 문제에도 사용될 수 있다는 점이 매우 신선했다.
그리고 최적화 논문을 읽으면서 느낀 것이지만 항상 언급되는 성능 지표 중 하나는 계산 시간이라는 것이다. NP-hard 문제이기 때문에 당연한 이야기지만 또 다른 성능 지표가 없는지에 대해 궁금증이 생겼다. 조합 최적화 문제에서 VRP 문제로 예를 들면, 에너지 소비와 주행 시간 등은 거리에 비례하는 것이라 성능으로 크게 의미가 없을 것 같은데.. 어떠한 성능 지표가 있을지 찾아 봐야겠다.
해당 논문의 구조는 Abstract - Introduction - Model -Motivation and Datasets Structure -Empirical Results - Conclusions으로 구성되어 있다. 서론에서는 전반적인 내용을 다루고 Model에서는 Seq2seq 모델, Attention 모델, Ptr-net으로 구성되어 있으며 각각의 모델의 한계점이 있어 이를 개선하기 위해 Ptr-net을 제안하게 되었다고 언급되어 있다. 이후 두 개의 챕터에서는 조합 최적화 문제 중 세 가지를 선정하여 Optimal한 해를 찾는 방법과 Ptr-net을 적용한 방법의 결과에 대해 비교를 하고 있다. 아무래도 최적해를 찾는 솔버들은 정확한 해를 찾는다는 장점이 있는 반면 계산 시간이 길다는 단점이 있다. 해당 논문에서 제안한 방법은 근사 해를 찾지만 계산 시간을 단축시킬 수 있다는 장점이 있다.
키워드: RNN, Sequence-to-Sequence Model, Pointer networks
인용: Vinyals, O., Fortunato, M., Jaitly, N., 2015. Pointer networks. In: Proceedings of the 28th International Conference on Neural Information Processing Systems. In: NeurIPS, Vol. 2, (ISSN: 10495258) pp. 2692–2700.
O. Vinyals, M. Fortunato, and N. Jaitly, “Pointer networks,” in Proc. Adv. Neural Inf. Process. Syst., Montreal, QC, Canada, Dec. 2015, pp. 2692–2700.
1. Introduction
* 순환 신경망(RNN)의 한계
- RNN은 시퀀스에 대한 함수를 학습하는데 사용됨. 그러나 기존의 RNN 아키텍처는 입력과 출력이 고정된 속도로 제공되는 상황에서만 사용 가능하였음
- 고정된 속도로 제공된다는 의미는 입력 및 출력이 일정한 타이밍에 따라 주어진다는 것을 의미함
- 기존 RNN은 입력 및 출력이 일정한 시간 간격으로 제공되는 경우에만 잘 동작하며, 시간 간격이 일정하지 않거나 유동적인 경우에는 성능 문제가 발생되었음 (즉, 입력 시퀀스나 출력 시퀀스의 길이가 일정하게 유지되어야 함)
이러한 의미가 헷갈렸는데, 결국 해당 논문에서 언급하는 RNN의 한계점은 '장기 의존성 모델링의 어려움'을 의미하는 것이었다. 즉, RNN은 순차적인 데이터를 처리하는데 강점이 있지만 장기 의존성을 모델링하는 데 어려움이 있다. 이는 모델이 현재 시퀀스의 맨 마지막 출력만을 고려하면서 이전 시퀀스의 정보를 잊어버릴 수 있기 때문이다.
* 시퀀스-투-시퀀스(Seq2Seq) 패러다임
- 앞서 설명한 RNN 기본 구조에 대한 제약을 제거함
- 이 패러다임은 하나의 RNN을 사용하여 입력 시퀀스를 임베딩으로 매핑하고, 또 다른 RNN(또는 동일한 RNN)을 사용하여 임베딩을 출력 시퀀스로 매핑함
- 따라서, 다양한 도메인에 적용하는 것이 가능해졌음
* 제안된 Ptr-Net 모델 특징
- Seq2seq 모델의 한계 극복: 기존 Seq2seq 모델은 여전히 출력 사전의 크기가 사전에 고정되어 있어야 한다는 문제점이 있었음. 따라서 입력 시퀀스의 길이에 따라 출력 사전 크기가 달라지는 조합 최적화 문제에는 적용할 수 없었음
- 해당 논문에서는 Attention 메커니즘을 재활용하여 입력 요소에 대한 포인터를 생성하는 방식으로 이러한 문제를 해결함
(a) Sequence-to-Sequence
- 파란색 부분: 입력 시퀀스를 인코더 RNN을 통해 고정된 차원의 벡터로 변환
- 보라색 부분: 위의 벡터를 디코더 RNN에 입력하여 출력 시퀀스를 생성함. 이때 출력 차원은 문제의 차원에 의해 고정됨
다른 자료를 찾아보았을 때에도 Seq2Seq 모델은 유사한 구조를 보인다!
(b) Ptr-Net
- 파란색 부분: 입력 시퀀스를 인코딩 RNN이 벡터로 변환
- 보라색 부분: 위의 벡터를 생성 네트워크(어텐션 모델)에 입력함. 각 단계에서 입력에 대한 콘텐츠 기반 어텐션 메커니즘을 조절하는 벡터를 생성함. 어텐션 메커니즘의 출력은 입력의 길이와 동일한 사전 크기의 소프트맥스 분포임
논문에 제시된 그림이 잘 이해되지 않아 다른 아케텍처를 가져왔다. 이 그림을 보면 보다 직관적인 이해가 가능하니 참고하자!
[정리]
| RNN 알고리즘의 한계 | 장기 의존성 모델링의 어려움 - 모델이 현재 시퀀스의 맨 마지막 출력만을 고려하면서 이전 시퀀스의 정보를 잊어버릴 수 있기 때문임 - 특히, 긴 시퀀스에서 발생하는 문제로, 이러한 한계로 인해 먼 거리에 있는 요소들 간의 관계를 적절하게 학습하기 어려울 수 있음 |
| Seq2seq 모델의 한계 | 출력 딕셔너리의 크기를 사전에 고정해야 하는 문제가 존재 - 입력 시퀀스를 고정된 길이의 벡터로 인코딩하고, 이를 기반으로 출력 시퀀스를 디코딩하는 구조를 가짐 - 출력 딕셔너리의 크기가 입력 시퀀스의 길이에 따라 달라지는 조합 최적화 문제에 적용하기 어려움 |
| Ptrnet 정의 | Seq2seq 한계 극복하기 위한 아키텍처 - 입력 요소에 대한 포인터를 생성하여 가변 길이 딕셔너리를 처리할 수 있는 방법 제안 |
[논문 요약]
- Pointer Net 아키텍처 제안: 해당 모델은 '포인터'로 활용하기 위해 소프트맥스 확률 분포를 사용하여 가변 길이 사전을 표현하는 문제를 해결함
- 해당 알고리즘을 사용하여 3가지 문제에 대해 해결함으로써 많은 포인트를 갖는 테스트 문제에 대해 일반화되는 것을 보여줌
(여기서 사용된 조합 최적화 문제는 Planar convex hull, Delaunay triangullations, Traveling Salesman Problem임)
- Pointer Net 모델은 소규모(n ≤ 50) TSP 근사 해법을 학습함. 결과를 보면 기존의 알고리즘보다 계산 시간 측면에서 이점이 있음을 파악 가능
2. Models
2.1. Sequence-to-Sequence Model
- 시퀀스 모델은 인코더 RNN과 디코더 RNN 두 개의 순환 신경망을 사용함
- 인코더 RNN: 입력 시퀀스를 처리하고 컨텍스트 벡터(Context vector)라는 고정 길이 벡터 표현을 생성함
- 디코더 RNN: 컨텍스트 벡터를 입력으로 받아 출력 시퀀스를 생성함
- 앞서 요약한 것처럼, 이 모델은 입력과 출력이 고정된 프레임 속도로 가능해야 한다는 한계가 존재함
* 식(1): 확률 연쇄 법칙을 적용하여 분해 (주어진 입력 시퀀스 P에 대한 출력 시퀀스 Cp의 조건부 확률 계산)
- 훈련쌍 (P, Cp)이 주어지면, Seq2Seq 모델은 확률 연쇄 법칙을 추정하기 위해 파라미터가 있는 RNN을 사용하여 조건부 확률 P(Cp | P ; θ)를 계산함
- 각 인덱스는 1부터 n까지의 정수이며, 출력 시퀀스의 길이 m(P)는 일반적으로 입력 시퀀스 P의 함수임 (입력 시퀀스의 길이에 따라 출력 시퀀스의 길이가 달라질 수 있음)
- 각 출력 토큰 Ci의 확률을 이전의 출력 토큰들과 입력 시퀀스에 의존하도록 모델링함
* 식(2): 학습 데이터에 대해 로그 값을 최대화하는 θ 찾는 식
- RNN 모델의 파라미터는 데이터셋에 대한 조건부 확률을 최대화함으로써 학습됨
- 식 (1)을 이용하여 주어진 학습 데이터에 대해 모델의 파라미터 θ를 학습함
- P(C P |P; θ)는 입력 시퀀스 P에 대해 출력 시퀀스 Cp를 생성할 모델의 확률을 의미함
- 즉, 출력 시퀀스의 첫 번째 요소부터 마지막 요소까지 순차적으로 생성할 확률임
- 이 확률을 최대화하는 θ를 찾는 것이 목표임
- 이를 위해, 모든 학습 데이터에 대해 로그 확률의 합을 최대화하는 θ를 찾음
- 로그를 취해주는 이유는 확률의 곱을 덧셈으로 바꾸어 계산을 용이하게 하기 위함
2.2. Content Based Input Attention
- 일반적인 Seq2seq 모델은 입력 시퀀스 P를 처리할 때, 해당 시퀀스의 끝에서부터 나온 인코더 RNN의 고정 차원 상태를 사용하여 전체적인 출력 시퀀스 Cp를 생성하였음
이 부분에 대해 추가적인 설명을 하자면 입력 시퀀스 끝에서 나온 고정 차원 상태는 Seq2seq 모델의 컨텍스트 벡터 즉, 맥락 벡터이다. 이렇게 하나의 고정된 길이의 벡터를 사용하게 된다면 입력 시퀀스의 길이가 길어졌을 때 하나의 벡터로 모든 정보를 표현하는 것이 어렵다는 의미이다.
(인코더와 디코더 모델은 모든 state의 정보를 사용하지 않고 단순히 마지막에 나오는 state를 통해 디코딩 됨. 내용이 이해가지 않는다면 https://www.youtube.com/watch?v=WsQLdu2JMgI 를 보는 것을 추천한다.)
- 이러한 문제를 해결하기 위해 인코더 및 디코더 RNN에 어텐션 메커니즘을 추가함
* 식 (3): Content Based Input Attention 식
- u: 인코더의 은닉 상태와 디코더의 은닉 상태를 비교하여 u를 만듬
- a: u를 softmax 하여 어텐션 가중치를 도출함
- d: 어텐션 가중치와 인코더 헤딩을 곱하고 더해줌 (하나의 인코더의 컨텍스트 벡터를 만듬)
- d를 디코더와 결합하여 분류함
- 각 출력에 대해 n개의 연산을 수행해야 하므로, 추론 시 계산 복잡도는 O(n^2)이 됨
- 이 모델은 convex hull 문제에 적용하였을 때 Seq2seq 모델보다 성능이 훨씬 우수하지만, 입력에 따라 출력 크기가 달라지는 상황에서는 적용할 수 없음 (조합 최적화 문제에 적용 불가)
2.3. Ptr-Net
- 해당 알고리즘은 입력 시퀀스 수에 따라 출력 사전 크기가 달라지는 조합 최적화 문제를 해결할 수 있음
- 출력 사전에 대한 softmax 분포를 사용하여 식 (1)을 계산함. 이에 따라 출력 사전 크기가 입력 시퀀스의 길이와 동일한 경우에는 사용할 수 없게 됨
* 어텐션 메커니즘 적용하여 제안한 Ptr-Net 식
- Content Based Input Attention 식과 비교하면 u와 softmax 적용하는 것까지 동일함
- d를 구하는 과정이 없음: 기존 어텐션 메커니즘은 인코더의 상태 ej를 디코더에 전달하여 입력의 다양한 부분에 대한 정보를 함께 고려하도록 설계되었음. 하지만 Ptr-net에서는 u를 활용하여 입력 요소에 직접적으로 '포인팅'하면서 해당 위치의 정보를 가져오게 됨
- 어텐션 가중치를 구한 후 가장 큰 값인 값을 그대로 카피해서 디코더에 가져옴
- 해당 알고리즘은 출력이 이산적이며 입력과 대응되는 문제를 대상으로 함
- 예를 들어, RNN을 사용하여 직접 대상 지점의 좌표를 출력할 수 있음
3. Motivation and Datasets Structure
3.1. Convex Hull
- Task : (x1, y1), ..., (x2, y2)와 같이 n개의 좌표값이 주어져 있을 때, convex hull을 형성하는 좌표값을 출력으로 내보내기
- 즉, P1, P2,..., P10와 같은 연결선 없는 좌표값이 인코더의 input이고, 디코더의 output이 P2, P4, P3,... 와 같이 convex hull을 생성할 수 있는 좌표가 되는 것임
- convex hull: 주어진 포인트들을 다 포함하는 가장 작은 convex set을 의미함
- convex set: 임의의 두 점을 잡았을 때 선 안에 있는 모든 점이 convex set에 들어가야 함
- 해당 문제의 정확한 솔루션을 찾는 방법이 존재하며 O(n log n) 복잡도를 가짐 (n은 좌표의 개수)
- P: 입력 값으로 P1~P10의 좌표
- C: 출력 값으로 P2에서 시작하여 convex hull을 구성한 후 P2 지점에서 마무리 됨
3.2. Delaunay Triangulation
- Delaunay 삼각화: 모든 삼각형의 원외접원이 비어있는 삼각화 문제
fig로 미루어 보았을 때 해당 논문에서 언급되는 조합 최적화 문제는 모두 유사한 구조를 가지고 있는 것 같다. 필요한 부분만 읽기 위해 해당 섹션은 간단히 정의만 하고 넘어가겠다.
3.3. Travelling Salesman Problem (TSP)
- Task: (x1, y1), ..., (x2, y2)와 같이 좌표값이 주어져 있을 때, 가장 최단 경로로 모든 좌표값을 방문하기 위한 순서를 출력으로 내보내기 (주어진 도시 목록에서 각 도시를 정확히 한 번 방문하고 시작 지점으로 돌아가는 최단 경로 찾기)
- P는 도시를 나타내는 카테시안 좌표임
* 카테시안 좌표: 평면 상의 점을 나타내는 좌표 체계로 일반적으로 (x, y)로 표시됨
- Cp는 1~n까지의 정수 순열로 최적 경로(투어)를 나타냄 (n의 범위는 최대 20까지로 설정)
- 정확한 최적 해를 생성하기 위해 Held-Karp 알고리즘을 사용함. 해당 알고리즘의 복잡도는 O(2^n*n^2)임. 따라서 n이 커질수록 복잡도가 높아지기 때문에 n이 작은 수준에서만 해당 알고리즘을 사용함 (표 2 참고)
- Ptr-net과 비교하기 위해 근사 해를 찾는 A1, A2, A3 알고리즘이 사용됨. A1 및 A2는 O(n^2) 복잡도를 가지며 A3는 O(n^3)의 복잡도를 가짐 (표 2 참고)
4. Empirical Results
4.1. Architecture and Hyperparameters
[실험 환경]
- 해당 실험에서는 Ptr-net 알고리즘에 대해 다양한 구조나 하이퍼파라미터 튜닝을 수행하지 않고, 모든 실험과 데이터 집합에 대하 거의 동일한 모델 구조를 사용함 (동일 하이퍼파라미터 사용)
- 단일 레이어 LSTM 사용, 은닛 유닛(은닉 상태)는 256 또는 512로 설정
- 가중치는 -0.08~0.08 사이의 균힐하게 랜덤 초기화 적용되었으며 L2 그래디언트 클리핑 2.0으로 설정함
- 100만 개의 학습 쌍을 생성하였고, 일부 간단한 작업의 경우 과적합 관찰됨
- 학습은 10~20 에폭에서 수렴됨
4.4. Travelling Salesman Problem
[실험 결과]
- 모델이 학습 데이터에서만 잘 수행되고 실제 문제에는 일반화되지 않을 가능성이 있어 3.3 색션에서 논의한 것처럼 상대적으로 작은 n값에 대한 정확한 해를 찾는 알고리즘과 근사해를 찾는 A1, A2, A3 알고리즘 그리고 Ptr-net에 대해 투어의 길이를 비교함
- n값이 20을 초과하는 경우, 빔 서치 절차를 적용하지 않을 때 Ptr-net 모델이 유효하지 않은 투어를 출력할 가능성이 있음
- 즉, n값이 증가함에 따라 실패율이 증가함 (n=30일 때, 실패율 35% 증가, n=40일 때, 실패율 98% 증가)
- 따라서 빔 서치 절차를 사용하여야 함
빔 서치 절차는 가능한 해의 공간을 효율적으로 탐색하는 알고리즘 중 하나로 특정 문제에서 여러 가지 해를 생성하는 경우 사용됨.. 이 부분은 더 찾아봐야겠다. 결론적으로 도시의 수 즉, 노드의 수가 증가할 수록 실패 확률이 높아져서 추가적인 절차가 필요한 것으로 보여진다.
[요약]
- Ground Truth(실제 정답지): 모든 조합을 모두 고려한 가장 optimal한 경우
- Predictions(뉴럴 네트워크): 학습 시켜 내보낸 결과과 실제 optimal과 매우 유사함 (길이가 약간 늘어나긴 했지만 잘 학습되고 있음. 500-1000개 정도 도시까지는 잘 학습됨)
- 이러한 문제를 뉴럴 네트워크를 통해 해결한다면 Time complex가 줄어든다는 장점이 존재함
Convex hull, Delaunay triangulation은 생략
5. Conclusions
* 결론
- Ptr-Net 아키택처 소개
- 이 아키택처는 하나의 시퀀스 P가 주어졌을 때 다른 시퀀스의 Cp의 조건부 확률을 학습할 수 있음
- Cp는 P의 위치에 해당하는 이산 토큰 시퀀스임 (즉, 포인터를 생성)
- 해당 논문에서는 3가지 조합 최적화 문제에 대한 해결책을 학습하는데 사용될 수 있음을 보여줌
- 입력의 크기가 가변적인 경우에 동작하며, 이는 RNN 및 어텐션 기본 모델이 직접 수행할 수 없음 (개선)
* 향후 연구
- 다른 조합 최적화 문제에 Pointer Netwok 알고리즘 적용
[참고]
- 14-01 시퀀스-투-시퀀스(Sequence-to-Sequence, seq2seq): https://wikidocs.net/24996
- [seq2seq] 어텐션이 포함된 seq2seq 모델: https://pasus.tistory.com/291
- [PtrNet] Pointer Net 구조: https://pasus.tistory.com/292
- [딥러닝 기계 번역] 시퀀스 투 시퀀스 + 어텐션 모델: https://www.youtube.com/watch?v=WsQLdu2JMgI
- 자연어 처리(2021f) Lecture 10-1 Pointer Network: https://www.youtube.com/watch?v=isV0jI9q1Uk