ORDER MATTERS: SEQUENCE TO SEQUENCE FOR SETS

논문: ORDER MATTERS: SEQUEN CE TO SEQUENCE FOR SETS

 

 

Oriol Vinyals, SAmy Bengio, Manjunath Kudlur

---

 

1. 입/출력 데이터의 순서가 모델을 학습할 때 중요한 역할

2. 입력 집합을 처리하는 seq2seq framework 확장

3. propose loss: searching over possible orders during training 훈련 중 가능한 순서 탐색

---

1. [Order matters] No natural order is known among input | output objects -> still be one that yields better performace

입/출력 간의 순서가 없을 때에도 성능 개선할 수 있는 순서가 존재한다

 

2. 모델 내에서 집합을 입/출력으로 고려하는 두가지 방법 제안 > 다양한 artificial & real datasets 어떻게 수행되는지 평가

---

RELATED WORK

 

seq2seq 모델 이후 _ 시퀀로부터 매핑하는 여러 프로그램 제안

 

❍ 이미지 캡션 생성: imgae > text

❍ 구문 분석: 문장 > 구문 분석 트리

❍ 계산: 문제 설명 > 솔루션 | point set > traveling salesman problem

 

+ external memories > reading (attention) mechanism to read memory

- RNNSearch

- Memory Networks

- Neural Turing Machines

- RL-TNM (paper): Reinforcement learning neural turing machines

 

> Chain Rule: serialize output random variables

> LSTM: long-term correlation

> RNN(encode sentences recursively as trees)과 같이 structured input을 가정 X

---

NEURAL NETWORKS FOR SEQUENCES AND SETS

 

seq2seq paradigm: 입력 X와 출력 Y를 모두 시퀀스로 나타내 (입/출력은 다른 길이일 수 있다)

조건부 확률로 모델링 > chain rule to decompose

 

Encoder: 입력을 순차적으로 읽기 위해 인코더 RNN 구현 (h(s): state of the encoder at time s)

Decoder RNN: 한번에 하나의 출력:

chain rule의 사용으로 이러한 접근 방식 > 가정 없이 구현 가능

 

입력 X | 출력 Y가 시퀀스에 해당하는 경우: RNN으로 순차적으로 읽는 것이 합리적 >>> 입력이 시퀀스가 아닌 경우??

Ex_ 입력이 정렬되지 않은 원소들의 집합 ?? 

 

❍ 시퀀스는 집합으로 표현 가능 _ (집합 = 순서가 없다)

ex) 시퀀스 내의 각 요소를 index와 결합한 tuple 형태로 

"I like cats" > { (I, 1), (like, 2), (cats, 3) } 형태의 튜플로 변환 가능

 

이런 식의 표현이 시퀀스라도 다른 순서로 입/출력 하는게 더 beneficial 하다고 주장 가능

ex) divide-and-conquer strategy: finds the median element first

> solution: 증가하거나 감소하는 순서로 출력하지 않을 수 O

 

그래서,,

❍ seq2seq을 확장해 입/출력 집합을 다루는 방법

❍ seq2seq 적용된 작업에서 순서의 중요성 > 기존 모델에 대한 확장 & 실험 결과

---

4. INPUT SETS

 

입력 집합을 다루는 방법!!

그 전에, 입력이 집합 = 순서가 중요하지 않아, 두 원소 x(i), x(j)를 바꾸어도  입력 인코딩 결과가 바뀌면 안된다.

이거를 만족할 수 있는 방법이 === bag-of-words

단어의 등장 횟수, 단어 임베딩 , 유사한 임베딩 함수를 합쳐서 표현하는 방법으로 → 자연스럽게 permutation invariant 성질을 가진다.

 

단어의 등장 횟수 계산 > 벡터 표현 > 등장 횟수만 고려한 표현

== 문장에서 단어들의 순서가 중요하지 않은 경우, 문장의 주제/주요 키워드 파악하는데 사용 가능

텍스트 = BAG

각 단어는 고정된 차원의 벡터 공간 내의 특정 위치에 매핑 > 해당 단어의 특성/의미 나타낸다.

 

++_ 언어=sequential 성질을 가진 domain:

복잡한 RNN 을 사용해서 순서를 계산에 포함할 수 있어

 

❍  bag-of-words > Reduction operation = inefficient

각 요소를 독립적으로 다루고, 순서/상호작용을 고려하지 않아

> 집합 내 요소의 길이에 따른 변화 반영 못해

fixed dimentional embedding

ex_

10개의 단어로 구성된 문서 > 100 차원의 임베딩

같은 방식으로 구성된 다른 문서 > 100개의 단어로 이루어져 있다면? > 똑같이 100 차원의 임베딩

> 데이터 길이와 상관 없이 항상 일정한 차원의 벡터 생성해 > 데이터의 다양한 특성 표현 못해

 

ex_

이미지 내의 object detection > object = 고정된 차원의 벡터로 표현

고양이 = 100 차원 벡터

개 = 100 차원 벡터

> object 종류와 상관 없이 모든 물체를 동일한 크기의 벡터로 표현 > 비효율

 

 

4.1 INPUT ORDER MATTERS

입력 순서가 시퀀스 입력으로 받는 seq2seq 모델 성능에 주는 영향에 대해 알아보자^^

 

In principle, RNN과 같은 인코더는 입력 시퀀스에서 복잡한 특성 인코딩 할 수 있는 universal approximators (n-grams of any order)

> order not matter 

[RNN] 내부 구조: 시퀀스 각 요소를 한번에 하나씩 처리해 업데이트

이전 시점의 정보 > 현재 시점에 영향 == long-term dependency 학습하는데 유리하다

입력 시퀀스 순서대로 내부 상태 갱신하는 과정 > 각 요소의 순서가 반영되 > 시퀀스 순서가 중요한 정보 처리 가능

입력 순서를 바꿔도 최종적으로 동일한 정보가 담기게 되므로 순서는 중요하지 않다.

[n-gram] 연속된 n 개의 요소(단위)

ex_ "Hello, how are you?" 2-gram ⇨ (Hello, how) (how are) (are you?)

> 주로 자연어 처리 텍스트 패턴 분석 | 모델링에 사용

> 언어 모델링: 이전 (n-1)개의 단어를 기반으로 다음 단어를 예측하는 데 사용 > 문장 | 텍스트 데이터의 확률 구조 모델링

 

근데 왜 순서가 중요하냐..?? non-convex optimization and more suitable prior.

> 모델 최적화 과정에서 함수의 형태가 복잡하고 non-convex 특성 때문에 최적화 어렵고

> 적절한 prior 활용해 모델을 조정하면 더 나은 결과를 얻을 수 ㅇㅇ

 

====== 이걸 보여주기 위해 실험을 해볼게 =====

➀ 기계 번역: 시퀀스의 순서 변경

source language(English) > mapping function: Encode > mapping function:Decode > target language(French)

╚ 영어 문장의 순서를 바꾸면 성능 향상(Seq2Seq): 기계 번역을 위한 end-to-end(하나의 단일 시스템으로 처리) 모델

    ╚ 전통적인 기계번역: 입력 문장 구문 분석 > 구조 추출 > 번역 수행

 

➁ 문장 구성 분석

영어 문장을 구문 분석 트리로 매핑하는 과정 > 문장을 반대로 뒤집으면 F1 score 증가하는 결과 얻어

 

➂ Convex hull 계산

각도에 따라 점들을 정렬 > 작업이 간단해져: O(n log n) > O(n)

학습 잘되고 빠른 결과 얻을 수 있음

=====그러니까 순서가 중요해=====

 

 

=====순서 정하기=====

1. 입력 시퀀스, 집합과 독립적인 순서(= 일정한 순서) 사용를 정의 (ex_ 번역 작업에서 문장을 반대로 뒤집어)

2. 입력에 따라 결졍되는 순서 정의 (ex_ convex hull 문제에서 점들을 정렬해)

====================

 

model << memory + computation

집합의 크기에 따라 증가하는 메모리 + 순서 불변성을 유지하는 특성

 

 

4.2 ATTENTION MECHANISMS

주소 지정 메커니즘을 가진메모리를 결합한 모델 > "content" based attention.

[Content based] 메모리 | 정보로부터 필요한 정보 선택적 추출, 입력 데이터의 content를 기준으로 어떤 정보를 선택할지

(데이터의 순서나 위치와는 독립적)

1. Query 생성: 입력 데이터 | 메모리에서 검색하려는 정보 나타내는 쿼리 벡터 생성

2. Key: Q, K 간의 유사도 계산 = 어텐션 스코어를 얻는다

3. 어텐션 스코어 확률 분포로 변환 > 어떤 정보를 어느 정도로 선택할 것인지

4. 가중 평균

╚  메모리에서 얻은 벡터가 메모리를 무작위로 섞어도 변경되지 않는 특성

╚ 입력 집합을 처리하는데 중요!!

 

The Read-Process-and-Write model

i = memory vector m(i), 입력 크기와 같음

q(t): qeury vector 메모리에서 r(t)를 읽어

f: m(i), q(t) 에서 single sclar 계산(dot-product)

LSTM: 반복 상태 계산하지만 입력은 받지 X

q(t)*: LSTM이 발전하는 상태, q(t)와 어텐션 출력 결과 r(t)를 연결해 형성

t = processing stpes

m(i) 와 m(i)'를 바꾸더라도 r(t)에는 영향을 미치지 않는다.

 

 

READ, PROCESS, WRITE

논문에서 제안하는 모델의 3가지 구성 요소

❍ Reading block: 입력 요소 x(i)를 신경망 사용해 m(i)로 임베딩, 모든 i에 동일한 신경망 사용

 

❍ Process block: 입/출력 없이 T steps 동안 m(i)에서 계산 수행하는 LSTM, attention mechanism 사용

    ╚ m(i) 반복해서 읽어 상태 업데이트

    ╚ 블록의 마지막, hidden stae q(T)* 는 입력에 대해 permutation invariant 가지는 임베딩

 

❍ Write block: LSTM pointer network(paper)(blog)로 구성

    ╚ 출력을 생성하기 위한 context로 Process block에서 생성한 q*(T)가 주어진다

    ╚ context와 입력 집합의 메모리 벡터 m(i) 사이의 유사도를 계산해 원소 선택

    ╚ [기존] Pointer network = 포인터 자체를 손실 함수에 포함, 메모리 내의 특정 위치를 가리키도록 만들어

    ╚ 포인터 앞에 추가적인 어텐션(glimpse)

 

 

(L) Write block - LSTM pointer (R) Pointer network

➔ 입력 요소 X의 순서에 무관 = 집합으로 처리

출력이 고정된 dictionary가 아닌 입력을 가리키는 포인터이므로 LSTM이 아닌 Pointer Network를 사용

 

 

SORTING EXPERIMENT

seq2seq보다 효율적으로 처리하는지 확인하기 위한 실험 수행

 

❍ 입력 = 0 ~ 1 사이 N개의 부동 소수점

❍ 출력 = 정렬된 순서 (집합을 시퀀스로 정렬)

╚ Read: 각 숫자마다 multilayer perception

╚ Proceess: 읽은 숫자들에 대한 att mechanism

    ┖ 입력과 출력이 없는 LSTM으로 이루어진 T steps

    ┖ 입력 임베딩에 관여, 포인터 네트워크 사용 > 입력 숫자의 적절한 정렬된 순서의 인덱스 생성하기 위한 LSTM

 

❍ LSTM으로 이어진 vanilla seq2seq과 비교

┖ Ptr-Net 사용해 입력 숫자의 인덱스 만들어내는

===> 차이점: 집합 인코딩 방식

┖ LSTM (previous work): 입력을 순차적으로 처리

 

┖ 제안 모델: 입력 데이터 한번에 처리해 순서에 영향을 받지 않는다.

 

1000 training iterations, all models had converged, non overfitted

 

❍ 결과 (N 작업 크기 | P= Process step)

기본 Ptr-net 모델이 처리 단계가 없을 때(P=0) 더 좋은 결과

처리 단계 있으면 > Read-Process-and-Write 모델 성능이 좋아

Writing module with glimpses(attention mechanism prior to "pointing") 사용하는게 둘 다 효과적

 

---

5. OUTPUT SETS

ouptut representation:

확률 변수 집합 Y에 대한 joint probabilites 를 설명하는 chain rule > 조건부 독립과 같은 임의의 제한 내포하지 않는 간단한 decomposition

 

long range corrlation을 다룰 수 있는 모델 존재한다면 어떤 순서든 사전 정보 없이 작동해야 한다.

LSTM과 같은 모델을 사용하더라도 출력 순서는 여전히 ordering still plays a key role!!

 

왜????

 

 

5.1 OUTPUT ORDER MATTERS

집합 | 시퀀스 Y 원소 배열 순서가 seq2seq 모델 성능에 어떤 영향을 미치는가?

 

 

❍ Y 변수들의 임의 | 임의적이지 않은 순서 고려해 > 조건부 확률 분포 P(Y|X) 모델링

┖ 이론: chain rule 사용하는 경우 = 순서는 중요하지 X

┖ 목표: ordering of elements does indeed have an impact on the performance of the model

 

 

5.1.1 LANGUAGE MODELING

 

❍ Penn Tree Bank

 

┖ standard language modeling benchmark

┖ small dataset

┖ medium sized LSTMs with large amounts of regularization: 단어 시퀀스에 대한 확률 추정

   ┖ [orderings] natrual | reverse | fixed, 3-word reversal > 순서에 대해 다른 모델 훈련

 

❍ Results

 

┖ Natural & Reverse: match 86 perplexity

┖ 3-word reversal: 96 perplexity: 모델이 순서 처리하는데 어려움.. 혼동되는 순서가 선택되면 일부 저하 ㅇㅇ

❍ Perplexity: 언어 모델 평가 지표

모델이 특정 텍스트 데이터셋을 얼마나 잘 예측하는가, 일련의 단어/토큰들이 얼마나 예측 가능한지 측정

낮을수록 모델이 데이터셋의 다음 단어를 잘 예측할 수 있음 나타내

높을수록 모델이 데이터셋을 잘 모델링하지 못하거나 예측하기 어려움 의미

 

5.1.2 PARSING

Consituency parsing = 문장 입력받아 구문 분석 트리 생성

 

encoder LSTM > decoder LSTM > generate a depth first traversal encoding of parse tree && attention

++ Breadth first traversal 사용해 작은 모델 훈련(순서는 입력에 따라 다르다)

깊이 우선 = 89.5% F1 score

너비 우선 = 81.5% F1 score

==== 순서가 중요해^^

 

 

5.1.3 COMBINATIONAL PROBLEMS

tours, triangulations, etc 와 같은 비순차적인 데이터를 다룰 때, large equivalence class of solutions

== 주어진 문제에 대해 서로 다른 해결책이 모두 유효 | 최적일 수 있어

 

ex_ 무작위 숫자 집합 X의 정렬된 입력 인덱스를 출력하는 경우

- 어떤 순서로 출력할지 선택 가능

- 집합으로 처리 가능

== n! 개의 가능한 출력 (perfectly valid)

훈련 set가 이런 순열 중 하나를 무작위로 선택해 생성하면

동일한 입력 X에 대해 n! 개의 출력 구성에 동일한 확률 할당해야해.. 

 

[previous work]: 출력 class를 제한

❍ tour: started from lower index city > counter-clockwise ordring

❍ triangles: sorted in lexicographical order > move left to right

(출력을 제한하지 않으면 수렴 속도 훨씬 느려져)

 

 

5.1.4 GRAPHICAL MODELS

T개의 무작위 변수 집합에 대한 결합 확률 P(y1, ..., yT)

무작위 변수들에 대한 사전 정보가 없는 경우, 결합 확률을 모델링하는 방법 = chain rule 사용

(RNN과 비슷한 방식으로 모델링)

문장의 경우 = 단어의 순서 > 모델 내에서 무작위 변수의 순서를 정하는데 도움

이론상 - Bayes rule: 필요에 따라 모든 조건부 확률 재정렬 가능, order should not matter

=== 어쨌거나 one order is easier to modelr than another

 

 

❍ generated starlike graphical models

head 변수와 그에 따른 조건부 확률 주어저 > 다양한 조건 하에서의 확률 분포 모델링 > 최적의 변수 순서 결정

[Expect] head 변수로 시작하는 것이 더 쉬울 것

- random variable: 10 ~ 50

- training set size: 200 ~ 20000

- randomness

- peaky

 

[결과]

- traning set size = 20000, 어떤 순서로든 학습

- marginal distribution are very peaky: 어떤 순서로든 학습

- 다른 모든 경우: 최적의 무작위 변수 순서로 학습하는 것이 다른 순서로 학습하는 것보다 더 쉬워

 

=== 결국에 순서가 중요하다22

 

5.2 FINDING OPTIAML ORDEREING WHILE TRAINING

제안하는 모델 = 입력 집합을 다루기 위한 것

- 입력 순서를 바꾸더라도 불변성 유지하는 임베딩 얻을 수 O

- 입력 집합에 대해 수행할 계산 종류 다룰 수 O

 

확률 변수 y1, ..., yn에 대한 joint probability를 구성하는 것은 함수 구조가 알려지지 않은 경우 어려워

RNN을 통해 해결 가능 > chain rule > decompose joint probabilty

 

[drawback] Chain rule

y1, .., yn을 집합으로 다루는 주장 위반 > 확률 변수들을 특정한 순서로 조건부화 한다는 것 의미

= LSTM을 사용한 결합 확률의 매개변수화

= non-convex nature of optimization problem 때문

   ┖ 목적 함수의 지역 최소값이 전역 최소값과 달라

   ┖ 초기 조건에 민감하게 변동 | 기울기가 급격하게 변하는 부분에서 수렴하기 어려움

 

[drawback: proposed solution]   

- 모델이 훈련하는 동안 어떤 순서가 가장 적합한지 결정하도록

- 가장 간단하게 작업을 단순화 하는 순서 π(X)가 존재한다고 가정

- p(Yπ(X)|X), 가능한 순서의 수는 n! (n=출력 길이), 최적의 순서는 사전에 알려지지 X

 

n! 매우 큰 값 > 훈련 동안 근사적인 탐색 시도 > 로그 확률을 최대화, training pair 에 대한 maximize

각 순서에 대한 작업 수행 > 가장 좋은 순서 찾아내 최적 결과 얻어

 

❍ 초기 파라미터 영향 > 무작위 순서 선택 후 머무르는 문제 존재

   ┖ 모델을 균일한 사전 분포로 1000 step 사전 훈련

   ┖ p(Yπ(X)|X)에 비례하는 분포에 따라 π(X) 샘플링 > 순서 선택: 모델 평가 O(n!) -> O(1) 필요

   ┖ 효율적인 샘플링: anceestral sampling(left-to-right) > p(.)을 n! 대신 한번만 평가

 

 

5.2.1 5-GRAM MODELING

 

해결하기 위한 시도 > 언어 모델링 작업의 간소화된 버전

추가적인 context 없이 5-gram 결합 확률 모델링: 입력 X 없음

n! 개의 가능한 순서 중에서 최상의 순서 찾기 > 

 

5-gram (sequence): y1=This, y2=is, y3=a, y4=five, y5=gram

5-gram (set): y1=(This,1), y2=(is,2), y3=(a,3), y4=(five,4), y5=(gram,5) 위치를 단어와 함께 추가하면 Y는 집합이 된다

시퀀스 구조 잃지 않고 임의로 Y shuffle 가능

 

natural order: perplexity 225.2

(5,1,3,4,2) order: perplexity 280 (안좋음)

 

❍  optimization

   ┖ Easy: (1,2,3,4,5) | (5,1,3,4,2) 에서 균일하게 추출된 exmaple

   ┖ Hard: 5! 개의 가능한 순서에 대한 example

 

 

 

6. CONCLUSION

 

LSTM은 가변 길이의 시퀀스 데이터를 효과적으로 표현 가능

- Long term dependencies 처리 능력: gradient vanishing 문제 해결, 모델 성능 향상

- chaing rule 이용해 복잡한 변수 확률 분포를 조건부 확률 곱으로 분해 가능

 

❍  input | output 이 순서가 없는 집합의 경우로 표현되는 경우

LSTM에 입력 가능한 순차적인 linearized 형태로 만들어야 한다.

 

 

❍ order matters to obtain the best performance.

┖ 순서가 없는 입력 데이터의 경우: Read-Process-and-Write architecture 제안

┖ 순서가 없는 출력 데이터의 경우: efficient training algorithm ↞ training | inference 중 가능한 순서 탐색

 

❍ sorting | graphical model | langugae model | parseing 에서 입력 및 출력 집합에 대한 실험 통해 설명