🤖 machine learning

Learning the symmetric group: large from small

본 논문은 특정 전치 전략을 사용하여 더 작은 대칭군 (예: $S_{10}$ ) 의 순열 예측에 훈련된 트랜스포머 모델이 데이터 생성 및 해석 가능성의 과제를 극복하기 위해 항등 증강 및 분할 윈도우와 같은 기법을 활용하여 훨씬 더 큰 군 (예: $S_{25}$ ) 으로 거의 완벽한 정확도로 일반화할 수 있는 확장 가능한 기계 학습 방법을 제안한다.

원저자: Max Petschack, Alexandr Garbali, Jan de Gier

게시일 2026-05-08

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Max Petschack, Alexandr Garbali, Jan de Gier

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

"Learning the symmetric group: large from small"이라는 논문에 대한 설명을 쉬운 언어와 비유를 사용하여 제시합니다.

핵심 아이디어: 작은 연습 세트로 거대한 퍼즐을 푸는 법을 학생에게 가르치기

25 조각 (심지어는 100 조각) 의 거대하고 복잡한 퍼즐을 푸는 법을 학생에게 가르치고 싶다고 상상해 보세요. 보통은 학생에게 그와 같은 크기의 연습 퍼즐을 주겠지만, 만약 10 조각짜리 연습 퍼즐만 준다면 어떨까요?

이 논문은 다음과 같은 질문을 던집니다: 컴퓨터 (특히 '트랜스포머'라고 불리는 AI) 가 작은 버전의 퍼즐만 연습함으로써 거대한 퍼즐의 규칙을 배운 뒤, 거대한 퍼즐을 한 번도 보지 않은 채 성공적으로 풀 수 있을까요?

이 연구에 따르면 그 답은 그렇습니다. AI 는 거대한 수학적 시스템의 작은 부분집합으로 훈련하여 그 시스템의 논리를 배웠고, 그 지식을 일반화하여 훨씬 크고 복잡한 시스템을 거의 완벽하게 처리했습니다.

우리 이야기의 등장인물들

대칭군 ( $S_n$ ): 이를 '카드 덱을 섞는 거대한 게임'으로 생각하세요.
- $n$ 장의 카드 (1 번부터 $n$ 번까지 번호가 매겨짐) 가 있다면, '순열'은 단순히 그 카드들의 특정 순서입니다.
- '대칭군'은 그 덱을 섞을 수 있는 모든 가능한 방법의 집합입니다.
- 목표는 카드를 어떻게 섞을지 알려주는 지시 목록 ('단어') 을 보고 덱의 최종 순서를 예측하는 것입니다.
지시사항 (전치):
- 일반 전치: 덱의 어떤 두 장의 카드를 골라 서로 바꾸는 것을 상상해 보세요. 이는 어떤 두 항목이든 즉시 바꿀 수 있는 '마법 지팡이'를 가진 것과 같습니다.
- 인접 전치: 오직 서로 바로 옆에 있는 카드들만 바꿀 수 있다고 상상해 보세요. 이는 훨씬 더 어렵습니다. 1 번 카드와 10 번 카드를 바꾸려면, 하나씩 서로 지나가도록 섞어야 합니다. 이는 훨씬 더 길고 복잡한 지시 목록을 만들어냅니다.
AI (트랜스포머): 이는 텍스트를 읽고 패턴을 이해하는 것으로 알려진 기계 학습 모델의 한 유형입니다. 여기서는 문장을 읽는 대신 수학적 지시 목록을 읽습니다.

실험: 두 가지 다른 도전 과제

연구자들은 AI 가 작은 것에서 큰 것으로 '확장'할 수 있는지 확인하기 위해 두 가지 주요 실험을 수행했습니다.

도전 과제 1: '마법 지팡이' (일반 전치)

훈련: AI 는 10 장의 카드를 섞는 것만 훈련받았습니다. 10 장의 덱에서 어떤 두 장의 카드를 바꾸든 지시사항을 따르는 법을 배웠습니다.
테스트: 그런 다음 연구자들은 AI 에게 25 장의 카드를 섞는 문제를 풀도록 요청했습니다.
결과: AI 는 거의 100% 의 정확도로 맞췄습니다. AI 는 단순히 10 장 카드의 규칙을 외운 것이 아니라, '바꾸기'의 근본적인 논리를 파악하여 한 번도 보지 못한 훨씬 더 큰 덱에 적용했습니다.

도전 과제 2: '이웃 바꾸기' (인접 전치)

훈련: 이는 더 어려웠습니다. AI 는 오직 이웃끼리만 바꿀 수 있는 10 장 카드 덱으로 훈련받았습니다.
문제점: 이웃끼리만 바꾸면 지시사항이 매우 길어집니다. 첫 번째 카드와 마지막 카드를 단순히 바꾸는 것만으로도 많은 단계가 필요합니다.
기교 (분할 윈도우): 연구자들은 AI 가 게으름을 피우고 있다는 것을 깨달았습니다. AI 는 단순히 보고 있는 카드들의 특정 '윈도우'를 외우고 있었습니다. 이를 해결하기 위해 '분할 윈도우' 방법을 사용했습니다. 긴 지시 목록을 조각으로 나누고 그 조각들을 섞어서 AI 가 위치에 의존하지 못하도록 했습니다. AI 는 실제 바꾸기의 논리를 배워야만 했습니다.
테스트: 연구자들은 AI 를 16 장의 카드 덱으로 테스트했습니다.
결과: 다시 한번 AI 는 거의 100% 의 정확도를 달성했습니다.

어떻게 작동하게 했을까요? (비밀 레시피)

연구자들은 **'정체성 증강 (Identity Augmentation)'**이라는 교묘한 트릭을 사용했습니다.

요리책을 쓰는데, 모든 요리법이 정확히 50 단계로 구성되어야 한다고 가정해 보세요. 어떤 요리법은 본래 짧습니다 (5 단계뿐). 책에 맞추려면 50 단계에 도달할 때까지 '아무것도 하지 않기' (예: '5 초 동안 가만히 서 있기') 와 같은 '더미 단계'를 추가해야 합니다.

AI 는 이러한 '아무것도 하지 않기' 단계가 결과를 바꾸지 않는다는 것을 배워야 했습니다. 짧은 지시사항에 이러한 '정체성' 단계로 패딩을 줌으로써, AI 는 노이즈를 무시하고 실제 수학에 집중하는 법을 배웠습니다.

AI 는 실제로 무엇을 배웠을까요?

연구자들은 AI 의 '뇌' (내부 데이터 표현) 를 들여다보며 그것이 무엇을 하고 있는지 확인했습니다.

관계 학습: AI 는 A 와 B 를 바꾸는 것이 B 와 A 를 바꾸는 것과 같다는 것을 깨달았습니다.
구조 학습: 바꾸기의 순서가 중요하다는 것을 파악했지만, 순서가 중요하지 않은 경우의 규칙도 배웠습니다.
부정직하지 않음: AI 는 단순히 정답을 외운 것이 아니었습니다. 테스트 질문이 훈련 질문과 달랐기 때문에, AI 는 섞기 작동 방식의 '알고리즘'을 배워야만 했습니다.

결론

이 논문은 AI 모델이 작은 예시에서 복잡한 수학적 규칙을 배워 동일한 문제의 훨씬 더 크고 복잡한 버전에 적용할 수 있음을 증명합니다.

비유: 작은 연습 보드를 사용하여 아이에게 신발 끈 묶는 법을 가르친 뒤, 거대한 부츠를 건네주는 것과 같습니다. 아이는 매듭의 논리를 배웠기 때문에 거대한 부츠도 완벽하게 묶을 수 있습니다.
한계: 저자들은 이것이 '대칭군' (카드 섞기) 에 대해서는 훌륭하게 작동하지만, 다른 수학적 군들은 더 엉망이고 배우기 어려울 수 있다고 지적합니다. 그러나 이 성공은 AI 가 결국 현재 컴퓨터에게 매우 어려운 '언노트 문제 (매듭 풀기)'와 같은 다른 어려운 수학 문제 해결에 도움을 줄 수 있음을 시사합니다.

요약하자면: AI 는 작은 덱으로 연습함으로써 마스터 섞기꾼이 되는 법을 배웠으며, 올바른 훈련을 통해 기계가 순수 수학에서 '작은 것'에서 '큰 것'으로 일반화할 수 있음을 증명했습니다.

기술 요약: 대칭군 학습: 작음으로부터의 큼

문제 정의
본 논문은 트랜스포머 기반 신경망이 오직 더 작은 부분군 $S_m$ ( $m < n$ ) 에만 훈련된 후, 군 관계를 하드코딩하지 않고 더 큰 군의 치환을 예측하도록 일반화할 수 있는지, 즉 대칭군 $S_n$ 의 구조를 학습할 수 있는지 조사한다. 구체적인 작업은 전치 (transpositions) 의 곱으로 표현된 $w \in S_n$ 을 입력받아 집합 $\{1, \dots, n\}$ 의 결과 치환을 예측하는 것이다. 저자들은 이 문제에 대한 두 가지 다른 형식을 다룬다:

일반 전치: 임의의 전치 $s_{i,j}$ 를 사용하여 인수분해된 단어.
인접 전치: 기본 인접 전치 $s_i = s_{i,i+1}$ 만 사용하여 인수분해된 단어.

주요 과제는 가변적인 단어 길이를 처리하는 것이다. 저자들은 축소된 단어 길이가 0 (항등원) 에서 $n-1$ (일반 경우) 또는 $n(n-1)/2$ (인접 경우) 까지 다양하다고 지적한다. 이를 관리하기 위해 모델은 항등 전치로 보강된 고정 길이의 비축약 단어에 대해 훈련된다.

방법론
저자들은 치환 토큰을 하나씩 예측하는 자기회귀 트랜스포머 아키텍처 (그림 1) 를 사용한다. 입력은 전치 시퀀스와 부분적으로 예측된 치환을 포함하는 "컨텍스트 윈도우"로 구성된다.

데이터 생성 및 증강:
- 항등 증강: 가변 길이를 처리하기 위해, 단어는 군 관계 하에서 항등으로 작용하는 전치로 최대 길이 $N$ 까지 패딩된다. 모델은 패딩을 무시하기 위해 이러한 관계를 암묵적으로 학습해야 한다.
- 부분군 훈련: 모델은 $S_m$ (구체적으로 $m=10$ ) 에서 생성된 데이터로 훈련되지만 $S_n$ ( $일반적인 경우$ n=25 $, 인접 경우$ n=16$) 에서 테스트된다.
- 재레이블링 전략: $S_m$ $S_{m}$ 만 포함하는 $S_n$ $S_{n}$ 에 대한 훈련 데이터를 생성하기 위해, 저자들은 $S_m$ $S_{m}$ 의 단어를 무작위 치환 $\sigma \in S_n$ $σ \in S_{n}$ 을 통해 $S_n$ $S_{n}$ 으로 매핑한다.
  - 일반 전치의 경우, $\{1, \dots, m\}$ 인덱스를 $\{1, \dots, n\}$ 의 무작위 부분집합으로 단순하게 무작위 재레이블링하는 방식을 사용한다.
  - 인접 전치의 경우, naive 한 "윈도우" 방법 ( $s_1, \dots, s_{m-1}$ 을 연속된 블록 $s_{k+1}, \dots$ 로 재레이블링) 은 모델이 군 구조가 아닌 윈도우 위치를 식별하도록 학습했기 때문에 실패했다. 이를 극복하기 위해 저자들은 분할 윈도우 방법을 도입했다. 이는 $m$ 을 합성 (예: $12 = 3+6+3$ ) 으로 분해하고, $S_n$ 내에서 길이가 다양한 여러 개의 비연속 윈도우를 생성한 후, 입력 토큰을 무작위 오프셋과 함께 이러한 윈도우에 매핑하는 것이다. 이는 모델이 전역적 위치 단서가 아닌 국소적 군 관계를 학습하도록 강제한다.
아키텍처 세부 사항:
- 토큰화: 일반 전치는 정수 $x_k = i_k - 1 + n(j_k - 1)$ 로 매핑된다. 인접 전치는 직접 인덱스 $x_k = i_k$ 로 매핑된다.
- 임베딩: 모델은 학습된 토큰 임베딩과 위치 임베딩을 사용한다. 입력은 표준 트랜스포머 레이어 (멀티헤드 어텐션, 피드포워드, 정규화) 를 거친 후 선형 레이어와 소프트맥스 출력 확률로 처리된다.

주요 결과
실험은 모델이 분포 외 (OOD) 테스트 세트에서 거의 100% 의 정확도를 달성함을 보여준다:

일반 전치: $S_{10}$ 에서 훈련된 모델은 훈련 손실이 0 이고 거의 완벽한 테스트 성능으로 $S_{25}$ 로 일반화되었다 (그림 2).
인접 전치: $S_{10}$ 에서 훈련된 모델은 유사한 높은 성능으로 $S_{16}$ 으로 일반화되었다 (그림 3). 저자들은 인접 경우가 더 긴 단어 길이와 더 엄격한 국소성 제약으로 인해 이론적으로 더 복잡하다고 지적하지만, 분할 윈도우 방법이 일반화를 성공적으로 가능하게 했다고 언급한다.

해석 가능성 관찰
저자들은 학습된 임베딩의 자기유사성 히트맵을 분석했다:

일반 전치: 토큰 임베딩 행렬은 규칙적인 격자 구조를 드러냈으며, 이는 모델이 생성자 간의 고수준 관계 (예: $s_{i,j}$ 는 $s_{i,k}$ 및 $s_{j,i}$ 와 강하게 관련됨) 를 학습했음을 나타낸다. 위치 임베딩은 일반 전치 간에 고유한 순서를 보이지 않았다.
인접 전치: 인접 전치에 대한 위치 임베딩은 처음 $n(n-1)/2$ 행 내에서 놀라운 블록 하위 구조를 보였으나, 저자들은 이것이 모든 군 크기에서 일관되지 않았으며 그 의미가 명확하지 않다고 지적했다.

의의 및 주장
본 논문은 트랜스포머가 작은 훈련 세트에서 군 곱셈의 근본적인 알고리즘 구조를 학습하고, 입력 표현이 변경되더라도 (재레이블링 및 분할을 통해) 훨씬 더 큰 군으로 일반화할 수 있음을 입증한다고 주장한다.

확장성: 이 작업은 더 단순한 구조 ( $S_m$ ) 로 훈련된 모델이 더 크고 복잡한 군 ( $S_n$ ) 에 대한 작업을 해결할 수 있는 확장 가능한 방법을 제안한다.
분포 외 학습: 이는 수학에서 분포 외 학습의 구체적인 사례로, 작은 부분군에서 학습된 특징이 더 큰 군에 적용될 만큼 보편적임을 보여준다.
향후 방향: 저자들은 이 접근법이 유한 생성 군의 단어 문제와 비교 유전체학의 NP-하드 문제에 대한 통찰을 제공할 수 있다고 제안한다. 특히, unknot 문제와의 관련성으로 인해 향후 작업의 대상으로 브레이드 군을 특정하며, 대칭군은 "잘 행동하는" 군이므로 더 이국적인 군이 더 큰 도전을 제시할 것이라고 지적한다.

저자들은 내부 메커니즘에 관해 겸손한 입장을 유지하며, 모델이 일반적인 알고리즘을 발견했는지 아니면 특정 표현을 학습했는지는 "열린 질문"이라고 명시하고, 향후 작업에서 기계적 해석 가능성 분석을 수행할 계획이다.