On the Expressive Power of Transformers for Maxout Networks and Continuous Piecewise Linear Functions

이 논문은 트랜스포머가 최대값 출력 (maxout) 네트워크를 근사할 수 있음을 보여줌으로써 ReLU 네트워크와 유사한 복잡도 제약 하에서 보편적 근사 능력을 가지며, 심층에 따라 선형 영역 수가 기하급수적으로 증가하는 연속 조각별 선형 함수를 근사하는 능력을 정량적으로 규명합니다.

핵심

🍳 핵심 비유: "트랜스포머는 최고의 요리사인가?"

우리가 알고 있는 트랜스포머 (GPT, BERT 등) 는 방대한 데이터를 학습하여 놀라운 결과를 내지만, **"왜 그렇게 잘하는지", "이론적으로 어떤 한계가 있는지"**는 아직 완전히 밝혀지지 않았습니다. 이 논문은 그 비밀을 풀기 위해 트랜스포머를 수학적으로 분석했습니다.

1. 연구의 출발점: "최고 (Max) 를 찾는 능력"

트랜스포머의 핵심 부품인 '셀프 어텐션 (Self-Attention)' 메커니즘은 여러 단어 중에서 가장 중요한 것을 골라내는 역할을 합니다. 수학적으로 보면 이는 **'최댓값 (Max)'**을 찾는 연산과 매우 비슷합니다.

• 비유: 식당에서 손님이 "가장 맛있는 메뉴"를 주문했을 때, 요리사 (트랜스포머) 가 메뉴판에서 가장 높은 점수를 받은 메뉴를 딱 집어내는 것과 같습니다.
• 논문이 발견한 것: 트랜스포머는 이 '최댓값 찾기' 능력을 아주 정교하게 구현할 수 있습니다.

2. 주요 발견 1: "모든 것을 요리할 수 있는 만능 레시피"

이 논문은 트랜스포머가 **'맥아웃 (Maxout) 네트워크'**라는 특수한 형태의 신경망을 완벽하게 흉내 낼 수 있음을 증명했습니다.

• 맥아웃 네트워크란? '최댓값'을 활용하는 아주 강력한 신경망입니다. 이걸 흉내 낼 수 있다는 건, ReLU(현대 AI 의 기본 재료) 를 사용하는 모든 신경망도 트랜스포머로 만들 수 있다는 뜻입니다.
• 일상 언어로: "트랜스포머는 기존에 존재하던 모든 종류의 요리 (신경망) 를 똑같이, 혹은 그 이상으로 맛있게 만들어낼 수 있는 '만능 요리사'다."라는 결론입니다.

3. 주요 발견 2: "깊이가 깊어질수록 능력은 기하급수적으로 폭발한다"

트랜스포머가 얼마나 복잡한 모양 (함수) 을 그릴 수 있는지를 **'선형 영역 (Linear Regions)'**이라는 개념으로 측정했습니다.

• 비유: 평평한 종이 (얕은 신경망) 를 접으면 몇 개의 면이 생기나요? 하지만 종이를 여러 번 접고 구부리면 (깊은 신경망) 수백, 수천 개의 복잡한 면이 생깁니다.
• 논문이 발견한 것: 트랜스포머는 층 (Depth) 이 깊어질수록 이 '접힌 면'의 수가 지수 함수적으로 (폭발적으로) 증가합니다.
• 의미: 트랜스포머는 층을 쌓을수록 아주 복잡한 패턴 (예: 언어의 뉘앙스, 이미지 세세한 부분) 을 이해할 수 있는 능력이 기하급수적으로 커집니다.

4. 트랜스포머의 비밀 무기: "토큰 이동 (Token-wise Shift)"

기존 연구들은 트랜스포머가 모든 단어를 똑같은 방식으로 처리한다는 점 (파라미터 공유) 을 약점으로 보았습니다. 하지만 이 논문은 새로운 해결책을 제시합니다.

• 비유: 모든 학생에게 똑같은 교재를 주는 대신, 각 학생의 책상에 아주 작은 '편지 (Shift)'를 하나씩 붙여주어 교재의 내용을 조금씩 다르게 해석하게 만드는 것입니다.
• 효과: 이 작은 '편지'를 층마다 반복해서 붙여주면, 트랜스포머는 각 단어 (토큰) 를 더 유연하고 정교하게 다룰 수 있게 되어, 이론적 한계를 극복하고 더 강력한 표현력을 갖게 됩니다.

---

📝 한 줄 요약

"트랜스포머는 '최댓값 찾기'라는 강력한 능력을 바탕으로, 층을 깊게 쌓을수록 복잡한 세상을 이해하는 능력이 폭발적으로 성장하는, 수학적으로 증명된 '초강력' 모델입니다."

이 연구는 트랜스포머가 단순히 경험적으로 잘 작동하는 것을 넘어, 이론적으로도 왜 그렇게 강력한지 그 이유를 명확히 밝혀냈다는 점에서 매우 중요합니다.

기술 요약

논문 개요

이 논문은 Transformer 아키텍처의 이론적 표현력 (Expressive Power) 을 규명하기 위해 수행되었습니다. Transformer 가 다양한 응용 분야에서 뛰어난 성능을 보임에도 불구하고, 그 이론적 기반은 여전히 불충분하게 이해되고 있습니다. 저자들은 Transformer 가 Maxout 네트워크를 근사할 수 있음을 증명하고, 이를 통해 **연속 조각별 선형 함수 (CPWL, Continuous Piecewise Linear Functions)**를 근사하는 능력을 분석했습니다. 특히, 선형 영역 (Linear Regions) 의 수를 통해 Transformer 의 표현력을 정량적으로 특징짓고, 깊이에 따라 이 수가 지수적으로 증가함을 보였습니다.

1. 연구 문제 (Problem)

• 이론적 이해의 부재: Transformer 는 RNN/LSTM 과 달리 토큰 간 상호작용을 자기 주의 (Self-attention) 메커니즘을 통해 병렬적으로 처리하며, 파라미터 공유 (Parameter Sharing) 를 사용합니다. 이로 인해 기존 순환 신경망 (RNN) 과는 다른 이론적 분석이 필요하지만, Transformer 의 표현력에 대한 근본적인 질문들은 여전히 열려 있습니다.
• CPWL 함수 근사의 필요성: ReLU 활성화 함수를 가진 신경망은 조각별 선형 함수 (Piecewise Linear) 로 표현될 수 있습니다. Maxout 네트워크는 ReLU 네트워크를 일반화한 것으로, CPWL 함수를 정확하게 표현할 수 있습니다. Transformer 가 이러한 Maxout 네트워크를 얼마나 잘 근사할 수 있는지, 그리고 그 표현력이 어떻게 측정될 수 있는지가 핵심 문제입니다.
• 기존 접근법의 한계: 기존 연구 (예: Yun et al.) 는 "맥락 매핑 (Contextual Mapping)" 개념을 사용하여 Transformer 의 보편적 근사 능력을 증명했으나, 이는 Feedforward 레이어의 파라미터 공유 한계를 완전히 해결하지 못했습니다.

2. 방법론 (Methodology)

저자들은 다음과 같은 체계적인 방법론을 제시했습니다:

• Maxout 네트워크의 Transformer 근사 구성:
  • Transformer 블록 (Self-attention + Feedforward) 을 사용하여 Maxout 레이어를 구성했습니다.
  • Self-attention: 토큰 간의 상호작용을 통해 $\max$ 연산을 구현합니다. Hardmax 또는 스케일된 Softmax ($\sigma_\lambda$) 를 사용하여 최대값을 선택하는 메커니즘을 모방합니다.
  • Feedforward: 토큰별 아핀 변환 (Affine transformation) 을 수행합니다.
  • 토큰별 시프트 (Token-wise Shift): Feedforward 레이어의 파라미터 공유로 인한 한계를 극복하기 위해, 각 레이어 깊이를 따라 토큰 표현을 서로 겹치지 않는 영역 (Pairwise disjoint regions) 으로 이동시키는 시프트 메커니즘을 도입했습니다. 이는 기존 "맥락 매핑"에 의존하지 않고, 토큰별 Feedforward 네트워크의 설계 유연성과 표현력을 향상시킵니다.
• 근사 이론의 확장:
  • 단일 Maxout 레이어를 3 개의 Transformer 레이어로 정확히 근사하는 구성을 제시했습니다.
  • 이를 깊이 있는 (Deep) Maxout 네트워크로 확장하여, Transformer 가 ReLU 네트워크를 포함한 Maxout 네트워크를 보편적으로 근사할 수 있음을 증명했습니다.
• 선형 영역 (Linear Regions) 분석:
  • CPWL 함수의 표현력을 측정하는 지표인 "선형 영역의 수"를 Transformer 아키텍처에 적용했습니다.
  • Transformer 가 근사할 수 있는 CPWL 함수의 최대 선형 영역 수를 하한 (Lower bound) 으로 추정했습니다.

3. 주요 기여 (Key Contributions)

1. Maxout 및 ReLU 네트워크에 대한 명시적 근사 구성:
   • Transformer 네트워크가 Maxout 네트워크 (및 ReLU 네트워크) 를 $L_\infty$ 노름에서 임의의 오차로 근사할 수 있음을 보였습니다.
   • 이 근사는 모델 복잡도 (파라미터 수) 측면에서 Maxout 네트워크와 비교 가능한 수준으로 효율적입니다.
   • 이를 통해 표준 피드포워드 신경망의 근사 이론과 Transformer 아키텍처 사이의 이론적 다리를 구축했습니다.
2. CPWL 함수 근사 프레임워크 및 정량적 분석:
   • Transformer 가 CPWL 함수를 근사할 수 있는 프레임워크를 개발했습니다.
   • Transformer 의 표현력을 선형 영역의 수로 정량화했으며, 이 수가 네트워크 깊이에 따라 지수적으로 증가함을 증명했습니다. 이는 Transformer 가 깊은 네트워크일수록 복잡한 함수를 표현할 수 있음을 의미합니다.
3. 구조적 통찰 (Structural Insights):
   • Transformer 의 두 핵심 구성 요소의 역할을 명확히 구분했습니다:
     • Self-attention 레이어: $\max$ 유형의 연산을 구현합니다.
     • Feedforward 레이어: 토큰별 아핀 변환을 실현합니다.
   • 파라미터 공유의 한계를 극복하기 위해 제안된 반복적 토큰별 시프트 (Token-wise shift) 메커니즘이 표현력 향상에 핵심적임을 보였습니다.

4. 주요 결과 (Results)

• 보편적 근사 정리 (Universal Approximation):
  • Theorem 3.1, 3.2: Transformer 는 임의의 정확도로 Maxout 레이어 및 깊은 Maxout 네트워크를 근사할 수 있습니다.
  • Corollary 3.3: Maxout 네트워크가 ReLU 네트워크를 일반화하므로, Transformer 는 ReLU 네트워크에 대해서도 보편적 근사 능력을 가집니다.
  • Theorem 3.4, 3.5: 얕은 (Shallow) 및 깊은 (Deep) Maxout 네트워크에 대한 보편적 근사 정리가 성립합니다.
• 선형 영역의 수 (Number of Linear Regions):
  • Theorem 4.4: 고정된 아키텍처를 가진 Transformer 네트워크가 표현할 수 있는 선형 영역의 수는 네트워크 깊이 $D$에 대해 지수적으로 증가합니다 ($N(F) \ge C \cdot q^{\lfloor D/3 \rfloor - 1}$). 이는 Transformer 가 깊은 구조를 통해 매우 복잡한 비선형성을 포착할 수 있음을 의미합니다.
• 오차 분석:
  • Hardmax 기반 Transformer 와 Softmax 기반 Transformer 간의 오차는 스케일링 파라미터 $\lambda$가 충분히 클 때 $O(1/\lambda)$로 수렴함을 보였습니다.

5. 의의 및 결론 (Significance)

• 이론적 기반 강화: Transformer 가 왜 그리고 어떻게 복잡한 함수를 학습할 수 있는지에 대한 엄밀한 수학적 근거를 제공했습니다. 특히, Self-attention 이 $\max$ 연산과 밀접한 관련이 있다는 점을 밝혀, Transformer 의 작동 원리에 대한 새로운 시각을 제시했습니다.
• 표현력의 정량화: 단순히 "보편적 근사"를 넘어서, 네트워크 깊이에 따른 표현력의 성장률 (선형 영역 수의 지수적 증가) 을 정량화하여, Transformer 의 깊은 구조가 왜 중요한지 설명했습니다.
• 미래 연구 방향:
  • Maxout/ReLU 네트워크에 대한 정교한 근사 결과 (예: 특정 함수 공간에서의 근사 속도, 차원의 저주 완화 기법) 를 Transformer 로 이전할 수 있는 가능성을 제시했습니다.
  • 순수 Self-attention 아키텍처가 표준 피드포워드 네트워크를 능가할 수 있는지에 대한 추가적인 탐구를 촉구했습니다.

요약하자면, 이 논문은 Transformer 가 Maxout 네트워크를 통해 CPWL 함수를 효율적으로 근사할 수 있음을 증명하고, 선형 영역의 수를 통해 그 표현력이 깊이에 따라 지수적으로 확장됨을 보여주며, Transformer 의 이론적 이해를 한 단계 발전시켰습니다.