Permutation Invariance, Permutation Equivariance

두 개념은 graph, scene generation task 주제와 관련된 논문을 읽다가 등장한 용어이다.

 

Permutation invariance, permutation equivariance는 입력 벡터(또는 행렬)의 요소의 순서가 바뀔 때 그 결과가 어떻게 바뀌는지에 대한 개념이다.

 

 

Permutation Invariance

 

Permutation invariance란, 입력 벡터 요소의 순서와 상관 없이 같은 출력을 생성하는 특성이다.

이를 graph에 적용해보면, adjacency matrix의 행, 또는 열의 순서가 바뀌어도 output이 변하지 않는 특성을 말한다.

 

\( f(\mathbf{P}\mathbf{A}\mathbf{P}^\top) = f(\mathbf{A}) \)

 

\(\mathbf{A}\)는 adjacency matrix, \(\mathbf{P\)는 행, 열의 순서를 바꾸는 permutation matrix이다.

 

이 특성을 갖는 대표적인 예로는 graph 자체가 있다. graph는 노드의 순서가 바뀌어도 같은 graph이다.

그리고 MLP(Multi Layer Perceptron) 또한 순서에 상관 없이 같은 출력을 생성하는 모델이므로, permutation invariant model으로 생각해볼 수 있다. 이에 반해, CNN(Convolutional Neural Network), RNN(Recurrent Neural Network)는 permutation invariant model이 아니다. (이 모델들은 image나 text에 자주 사용되는데, 입력 픽셀이나 입력 텍스트의 순서를 고려하지 못하면 특징을 학습하기 어려울 것이다.)

 

 

 

 

 

Permutation equivariance

 

ATISS 논문에서는 set generation task에서 transformer의 permutation equivariance property를 사용하여 순서가 없는 set을 처리하고 예측하는 이전 연구를 소개했다. ATISS 모델 또한 transformer의 이러한 특성을 사용하여 partial scene을 다룬다.

 

Permutation equivariance란, 입력 벡터 요소의 순서가 바뀜에 따라 output의 행 또는 열도 바뀌는 특성이다.

Permutation invariance와는 반대되는 개념이라고 생각하면 된다. 그래프에 적용해보면,  adjacency matrix의 행 또는 열의 순서가 바뀌는 대로 output의 행 또는 열도 바뀌는 특성으로 볼 수 있다.

 

\( f(\mathbf{P}\mathbf{A}\mathbf{P}^\top) =  \mathbf{P} f(\mathbf{A}) \)

 

예를 들어, 각 노드의 degree를 나타내는 함수 \(f\)는 노드의 순서가 바뀌게 되면 바뀐 순서 그대로 output 행렬의 순서가 바뀌게 된다.