기술 요약: 자기회귀 트랜스포머가 계산하는 확률 분포

문제 제기

트랜스포머의 표현력에 관한 기존 이론적 연구는 주로 트랜스포머를 언어 인식기(분류기)로 간주하며, 여기서 입력은 완전한 문자열이고 출력은 이진 분류(수용/거부)입니다. 그러나 트랜스포머의 주요 실용적 응용은 언어 모델(자기회귀기)로서, 접두사를 기반으로 다음 심볼에 대한 확률 분포를 예측하여 토큰 단위로 문자열을 생성하는 것입니다.

본 논문은 근본적인 격차를 다룹니다: 인식 설정에서의 트랜스포머 표현력에 관한 이론적 결과 중 어떤 것이 언어 모델링 설정으로 확장되는지는 불분명합니다. 구체적으로 저자들은 부울 분류기로서의 트랜스포머에 대해 확립된 동치 클래스 (예: 선형 시계 논리 (LTL) 또는 카운터 프리 오토마타와의 동치) 가 트랜스포머가 실수 가중치 또는 부울 자기회귀기로 사용될 때 유지되는지 여부를 조사합니다.

방법론

저자들은 두 가지 가중치 영역에 걸쳐 분류기와 자기회귀기로서의 트랜스포머를 비교하기 위한 형식적 프레임워크를 개발합니다:

1. 부울 반환 ($\mathbb{B}$): 가중치는 $\{0, 1\}$(거짓/참) 입니다.
2. 실수 반환 ($\mathbb{R}_{\geq 0}$): 가중치는 음이 아닌 실수 (확률) 입니다.

저자들은 문자열 접두사를 상태 시퀀스로 매핑하는 상태 인코더를 정의합니다. 여기서 $i$ 위치의 상태는 접두사 $w_{\leq i}$에만 의존합니다. 이 추상화를 사용하여 네 가지 특정 구성을 분석합니다:

• 부울 분류기: 전체 문자열을 부울 값으로 매핑합니다.
• 부울 자기회귀기: 접두사를 다음 토큰에 대한 분포로 매핑합니다 (부울 가중치).
• 실수 분류기: 전체 문자열을 실수 가중치로 매핑합니다.
• 실수 자기회귀기: 접두사를 다음 토큰에 대한 확률 분포로 매핑합니다.

이 연구는 고정 정밀도의 **유니크 하드 어텐션 트랜스포머 (UHATs)**와 **소프트맥스 어텐션 트랜스포머 (SMATs)**에 초점을 맞춥니다. 이들은 다음과 비교됩니다:

• 선형 시계 논리 (LTL) 및 그 파편 (예: $TL[P]$, $TL[H]$).
• 카운터 프리 결정적 유한 오토마타 (cfDFAs) 및 카운터 프리 비결정적 유한 오토마타 (cfNFAs).

핵심 방법론은 분류기 모드와 자기회귀 모드 모두에서 한 형식주의가 다른 것을 시뮬레이션할 수 있는지 여부를 결정하기 위해 이들 형식주의 간에 축소 (reductions) 를 구성하는 것입니다.

주요 기여 및 결과

1. 부울 분류기 vs. 자기회귀기의 동치

• 전체 LTL: 부울 반환에서 LTL 분류기와 LTL 자기회귀기는 동치입니다. 논리에 "어제"($Y$) 및 "역사적으로"($H$) 연산자가 포함된다면, 부울 자기회귀기로 작용하는 트랜스포머는 분류기로 작용하는 것과 동일한 언어를 정의할 수 있습니다.
• 변환의 복잡성: 동치이지만, 자기회귀기를 분류기로 변환하는 것 (특히 $Y$ 연산자를 제거하는 것) 은 공식 크기에서 지수적 팽창을 필요로 할 수 있습니다. 본 논문은 특정 파편에 대해 다항 시간 동치 변환을 구성하는 것은 $P = PSPACE$또는$P = NP$가 아닌 한 불가능함을 증명합니다.

2. 제한된 파편에서의 발산 (부울)

시계 연산자 집합을 제한할 때 (예: $Y$ 없이 $TL[H]$또는$TL[P]$로 제한), 자기회귀기는 분류기보다 엄격하게 더 표현력이 풍부해집니다.

• 예시: 언어 $(ab)^*$는 부울 $TL[\emptyset]$ 자기회귀기로 정의 가능하지만, 어떤 $TL[H]$또는$TL[Y]$ 분류기로도 정의할 수 없습니다.
• 함의: 이러한 파편에 해당하는 특정 어텐션 메커니즘을 가진 트랜스포머 (예: 왼쪽 끝 UHAT 또는 고정 정밀도 SMAT) 는 분류기로서는 인식할 수 없는 언어를 자기회귀기로서는 인식할 수 있습니다.

3. 실수 가중치 설정에서의 발산

실수 반환에서 표현력 지형은 크게 변화합니다:

• 분류기 vs. 자기회귀기: 이들은 비교 불가능합니다.
  • 실수 자기회귀기로는 표현 가능하지만 실수 분류기로는 표현 불가능한 가중치 언어가 있습니다 (예: 무한히 많은 서로 다른 가중치를 필요로 하는 $(\frac{1}{2}a)^*$).
  • 실수 분류기로는 표현 가능하지만 실수 자기회귀기로는 표현 불가능한 가중치 언어가 있습니다 (예: 정규화된 확률 분포가 아닌 $(1a)^*$).
• UHATs 와 cfDFAs: 실수 설정에서 자기회귀기로서의 UHAT(및 LTL) 는 카운터 프리 DFA와 동치입니다. 그러나 가중치 카운터 프리 NFA보다 엄격하게 표현력이 떨어집니다.
  • 본 논문은 결정화될 수 없는 (동치인 가중치 DFA 로 변환 불가능한) 카운터 프리 가중치 NFA 를 보여줍니다. 이는 실수 가중치 설정에서의 비결정성이 트랜스포머 (결정적 상태 인코더로 모델링됨) 가 포착할 수 없는 표현력을 추가함을 보여줍니다.

4. 카운팅 연산자의 영향

본 논문은 카운팅 능력을 갖춘 트랜스포머 (예: 어텐션 내부에서 임의 정밀도를 가진 SMAT, $TL[\#]$에 동치) 에 관한 결과를 재검토합니다.

• 이전 연구는 이러한 트랜스포머가 분류기로서 특정 언어를 인식함을 보였습니다.
• 본 논문은 자기회귀기로서 이러한 모델이 약간 더 강력하며, 분류기로서는 인식할 수 없는 언어 (예: $L_{k+2}$, 분류기로는 $L_k$로 제한됨) 를 인식할 수 있음을 보여줍니다. 이는 이전 문헌에서 이론적 인식 한계와 경험적 심볼 예측 성능 사이의 불일치를 설명합니다.

중요성 및 주장

본 논문은 트랜스포머 표현력에 대한 기존 실험을 해석할 수 있는 원칙적인 방법을 제공한다고 주장합니다.

• 검증: 많은 경우 (특히 전체 부울 LTL) 언어 인식 문헌의 결과가 언어 모델로 이전됩니다. 예를 들어, UHAT 이 분류기로서 PARITY 를 인식할 수 없으므로 자기회귀기로서도 이를 인식할 수 없습니다.
• 주의점: 저자들은 인식 결과가 생성에 적용된다고 맹신해서는 안 된다고 강조합니다.
  • 실수 가중치: 부울에서 실수 가중치로의 전환은 부울 사례에서 발견된 동치 (예: DFA 와 NFA 사이) 를 깨뜨립니다.
  • 자기회귀 vs. 분류: 자기회귀는 제한된 논리 파편 (부울) 에서 표현력을 엄격하게 증가시킬 수 있으며, 표현 가능한 가중치 언어의 클래스를 변경합니다 (실수).
• 향후 방향: 저자들은 향후 연구가 이러한 결과를 로그 정밀도 소프트맥스 어텐션, 위치 인코딩, 그리고 실수 가중치 설정에서의 "생각의 사슬 (chain of thought)" 추론으로 확장해야 한다고 제안하며, 현재 자기회귀기의 비표현성을 증명하는 기술은 제한적임을 지적합니다.

요약하자면, 본 논문은 언어 모델로서의 트랜스포머가 인식기로서의 트랜스포머와 많은 이론적 기반을 공유하지만, 자기회귀와 실수 값 확률로의 전환은 비결정성의 힘과 사용 가능한 특정 시계 연산자와 관련하여 계산적 표현력에 미묘하지만 결정적인 차이를 도입함을 확립합니다.