[Paper Review] Set Transformer: A Framework for Attention-based Permutation-Invariant Neural Networks

Title: Set Transformer: A Framework for Attention-based Permutation-Invariant Neural Networks
Authors: Juho Lee, Yoonho Lee, Jungtaek Kim, Adam R. Kosiorek, Seungjin Choi, Yee Whye Teh  

---

0. Abstract 

• 다양한 ML tasks는 set의 순서에 의존하지 않는 *permutation invariant한 특성을 반영하지 못함 
• 기존 모델의 이러한 한계로, Attention-based neural network model인 Set Transformer를 제안함 
• Set Transformer는 input set 내 요소들의 interaction을 반영할 수 있도록 설계됨. 또한 attention mechanisms에 기반하여 encoder-decoder 구조로 이루어짐
• Set Transformer는 sparse Gaussian process literature를 통해 computation time을 절감함

 

1. Introduction

Set-structured data는 set of instances이 input이며, entire set에 대해 한 label이 존재함. 이러한 set-input 형태 데이터를 처리하기 위한 모델은 아래의 두 가지를 만족해야 함

• It should be permutation invariant - 모델의 output은 input set의 순서에 상관 없이 동일해야 함 
• It should be able to process input sets of any size. - input의 shape이 달라도 이를 처리할 수 있어야 함. 대부분의 neural network-based models는 이를 만족하지 못함

Set-structured data를 처리하기 위해 "set pooling methods"라는 것이 제안됨. 하지만, output의 형태가 black-box라는 단점이 존재함. "amortized clustering"도 parametric mapping을 통해 cluster와 set을 매핑하여, set-structured data를 처리하고자 함. 하지만, quantization이 contents of the set을 반영할 수 없었음

따라서, Set Transformer가 제안됨. Set Transformer의 novelty는 아래와 같음

• Self-attention mechanism을 사용해, 모든 element를 input-set으로 처리함. 이는 set 내의 elements 간의 interaction을 반영하여 encoding 할 수 있음 
• computation time을 줄임 
• feature를 aggregate할 때, self-attention mechanism을 사용하여 problem이 multiple outputs를 요구할때에도 사용이 가능함 

 

2. Background 

Pooling Architecture for Sets 

• Problems involving a set of objects have the permutation invariance property: the target value for a given set is the same regardless of the order of objects in the set.
• A simple example of a permutation invariant model → set element에서 추출된 embedding에 대해 pooling을 수행하는 network

• 모든 permutation invariant function은 (1)처럼 표현. pool은 sum operator, ρ, φ는 continuous function
• (1)은 encoder-decoder 파트로 구분 가능
  • encoder(φ): element of a set of n items 
  • decoder(ρ): which aggregates these encoded features and produces output

Attention 

Att(Query, Key, Value). W(Weight, activation function)

• n개의 query vector(set with n elements)
• dot product Q*K(T)는 query의 each pair들끼리 얼마나 유사한지 측정함
• **Attention에 대한 설명은 아래 링크 참조

 

3. Set Transformer 

Set Transformer란?

• sets of data를 처리하기 위한 an attention-based neural network
• Set Transformer는 encoder-decoder architecture 구조임 (각각의 encoder-decoder의 layer가 activation을 생성)
• 또한, fixed pooling operation 대신,  aggregating function pool(·) 이 problem에 맞게 parameterized 될 수 있음 

 

Permutation Equivariant (Induced) Set Attention Blocks

• self-attention → compute interactions among instances during the encoding process 
• multi-head attention mechanism 

Pooling by Multihead Attention

 

Overall Architecture 

 

 

Analysis

Since the blocks used to construct the encoder (i.e., SAB, ISAB) are permutation equivariant, the mapping of the encoder X → Z is permutation equivariant as well. Combined with the fact that the PMA in the decoder is a permutation invariant transformation, we have the following:

• Proposition 1. The Set Transformer is permutation invariant.

Being able to approximate any function is a desirable property, especially for black-box models such as deep neural networks. Building on previous results about the universal approximation of permutation invariant functions, we prove the universality of Set Transformers:

• Proposition 2. The Set Transformer is a universal approximator of permutation invariant function.

 

 

 

---

* Permutation Invariant 개념 (https://jiachoi.tistory.com/15)

[ML] Permutation invariant의 개념

 

** Attention 논문 리뷰(https://jiachoi.tistory.com/4?category=1054535) 

[Paper Review] Transformer: Attention is All you Need

 

*** Paper URL (https://arxiv.org/abs/1810.00825)

Set Transformer: A Framework for Attention-based Permutation-Invariant Neural Networks