Nyströmformer: 효율적 근사

Transformer의 핵심인 self-attention 메커니즘은 입력 시퀀스 길이($n$)의 제곱에 비례하는 $O(n^2)$의 시간 및 메모리 복잡도를 가져, 긴 시퀀스 처리 시 막대한 비용이 발생한다.

Nyströmformer는 행렬 근사 기법인 Nyström method를 활용해 이를 $O(n)$ 복잡도로 근사한다. 이 방법은 전체 행렬을 계산하는 대신 일부 행과 열을 샘플링하여 행렬을 근사하는 원리를 이용한다.

주요 특징은 다음과 같다:

• Landmark 샘플링: softmax 행렬에 직접 Nyström 방법을 적용하기 어려운 문제를 해결하기 위해, Query와 Key에서 **landmark(Nyström points)**를 샘플링한다.
• Segment Means: Landmark는 시퀀스를 여러 세그먼트로 나누고 각 세그먼트의 평균을 구하는 방식으로 생성된다.
• 성능 유지: 적은 수의 landmark만으로도 긴 시퀀스에서 표준 self-attention 및 기존의 효율적인 attention 메커니즘과 대등한 성능을 보여준다.