Set-to-Sequence Methods in Machine Learning:a Review

리뷰 논문: Set-to-Sequence Methods in Machine Learning: a Review

 

---

집합 -> sequence 출력에서 의 기계학습

-응용) 언어 모델링, meta-learning to multi agent atrategy games, power grid optimization

 

1. Introduction

 

1.1 What is Set-to-Sequence?

 

-input = 순서가 없는 원소들의 모음 (Set)

-output = 순서가 있는 Sequence

 

Problem

- 조합 최적화

Combinatorial Optimization: 유한 탐색 공간에서 최적해 찾기

- Traveling Salesman

- Jop ship scheduling

- Knapsack Problem

대부분 NP-Hard Problem

 

- TSP

여행 거리의 총합이 최소가 되도록 전체 노드이 순회 순서 결정하기

n개 노드에 대한 모든 순열 탐색 -> 적절한 heuristic 사용해 탐색 공간을 줄이는 방식으로 효율 높인다

 

딥러닝을 사용해 TSP 문제의 학습이 가능함을 보임 (Pointer network)

=> 임의 개수의 노드에 대해 동작할 수 있다는 것이 특징

=> 상대적으로 적은 노드의 TSP  학습 후, 더 많은 노드의 TSP 에 대해 동작하도록

- 구조 예측

=> 집합 인코딩, 순열 학습

 

이미지/저연어 문장(구조화된 데이터)과 달리 <-> 집합 = 내부 구조/순서 없다

=> 의미있는 순열 불변 표현을 얻는 것이 중요 (meaningful permutation invariant representations)

=> 집합 요소의 순서와 무관한, 집합의 핵심 특성이나 특징

 

 

1.2 Why Does Set-to-Sequence Matter?

 

계산적으로 다루기 어려운 문제에 대한 approximate solution 제공 가능

ex

_Travelling Salesman Problem

_tackling prominent NLP challenges such as sentence ordering

_text summarization

_multiagent reinforcement learning

_the agent employed by the AlphaStar model

 

 

✎ 

Section 2

필요한 배경 개념과 관련 연구 소개

표기법에 대한 구체적인 설명

 

Section 3

집합 인코딩 방버의 개요 제시

수학적 변환의 세부 사항

 

 Section 4

인코딩된 집합 표현을 사용해 복잡한 순열 출력하는 방법 조사

 

Section 5

현재 한계와 추가 연구 방향

 

Section 6

요약

---

3.2 Pointer Network

 

수정된 어텐션 메커니즘을 포함한 인코더-디코더 구조

learning a target reordering of input elements

 

- 다양한 입력 크기의 조합 최적화 문제를 해결하기 위해 설계

- 잘 일반화되는 것으로 알려짐

 

- content-based attention 메커니즘의 수정 포함

- 모델의 출력을 입력 시퀀스 요소를 가리키는 포인터로 취급

<= 모델이 입력 순열을 출력할 수 있는 방법 중 하나..

 

 

3.2.1 Pointer Networks Limitations

 

1. 입력을 집합을 처리하지 않고 순차적인 순환 신경망을 통해 처리해

- 인코딩된 집합의 순열 불변 표현을 얻지 못한다 > 동일한 집합이 서로 다른 순서로 표현될 수 있어

- 모델이 서로 다른 출력을 예측할 수 있는 상황 발생

= 최적의 순서를 반환하는 것은 보장되지 X

 

2. 모델이 입력 집합이나 시퀀스의 잘못된 재정렬 출력 가능

- 추론 중에 beam search나 점진적으로 마스킹하는 방법으로 완화 가능

 

 

3.2.2 Pointer Networks Details

 

 

포인터 네트워크는 RNN encoder와 수정된 어텐션 메커니즘을 가진 RNN decoder 로 구성

모델은 각 디커도 단계 j 에서 content 기반 어텐션 벡터 aj 를 얻는다

이 벡터는 각 입력 요소 xi 가 해당 단계에서 가리키는 올바른 요소로서의 조건부 확률 <= 이전 모든 단계와 전체 입력 시퀀스에 의존

 

각 요소 xi는 정확히 한 번 가리켜야 한다.

=> 음이 아닌 정수 포인터로 이루어진 출력 시퀀스 yi 가 유효한 순열 π를 나타내도록

 

dj는 j 번째 출력 요소에서의 디코더 은닉 상태,

ei는 i 번째 입력 요소에서의 인코더 은닉 상태

 

W1, W2, v는 학습 가능한 tensor

zj는 입력 x의 길이와 동일, 입력 요소의 사전에 대한 출력 분포

 

 

3.2.3 Pointer Networks Applications

 

- 조합 최적화 문제에 대해 테스트 결과

문제 규모에 따라 제한적이지만 근사 솔루션 학습 가능

 

 

 

 

 

---

💬 글을 날림으로 읽지 말고 이해하자..