🤖 machine learning

CayleyPy RL: Pathfinding and Reinforcement Learning on Cayley Graphs

본 논문은 대규모 케일리 그래프에서의 경로 찾기를 효율적으로 해결하기 위해 강화 학습과 확산 거리 방법을 결합한 CayleyPy 프로젝트를 제시하며, GAP 와 같은 기존 도구를 성공적으로 극복하고 대칭군의 지름에 관한 OEIS-A186783 추론에 대한 강력한 증거를 제시함과 동시에 새로운 이론적 경계를 확립하고 Kaggle 챌린지를 통한 커뮤니티 참여를 독려합니다.

원저자: A. Chervov, M. Obozov, A. Soibelman, S. Lytkin, I. Kiselev, S. Fironov, A. Lukyanenko, A. Dolgorukova, A. Ogurtsov, F. Petrov, S. Krymskii, M. Evseev, L. Grunvald, D. Gorodkov, G. Antiufeev, G. Verbii

게시일 2026-05-19

📖 5 분 읽기🧠 심층 분석

CC BY 4.0

원저자: A. Chervov, M. Obozov, A. Soibelman, S. Lytkin, I. Kiselev, S. Fironov, A. Lukyanenko, A. Dolgorukova, A. Ogurtsov, F. Petrov, S. Krymskii, M. Evseev, L. Grunvald, D. Gorodkov, G. Antiufeev, G. Verbii, V. Zamkovoy, L. Cheldieva, I. Koltsov, A. Sychev, A. Eliseev, S. Nikolenko, N. Narynbaev, R. Turtayev, N. Rokotyan, S. Kovalev, A. Rozanov, V. Nelin, S. Ermilov, L. Shishina, D. Mamayeva, A. Korolkova, K. Khoruzhii, A. Romanov

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

다음은 "CayleyPy RL: Cayley 그래프 위의 경로 탐색과 강화 학습"이라는 논문에 대한 설명을 쉬운 언어와 창의적인 비유로 번역한 것입니다.

큰 그림: 거울 미로에서 가장 짧은 집으로 가는 길 찾기

거대하고 끝없는 미로 속에 있다고 상상해 보세요. 하지만 이 미로는 벽으로 만들어진 일반적인 미로가 아니라 규칙으로 만들어진 미로입니다. 한 걸음을 뗄 때마다 특정 규칙을 따라 위치가 바뀝니다. 수학적으로 이를 Cayley 그래프라고 부릅니다.

이 논문의 목표는 미로의 특정 유형인 LRX 미로를 푸는 것입니다. 이 미로는 카드 덱을 섞는 규칙 (또는 숫자의 순열) 을 기반으로 만들어집니다.

규칙 L: 모든 것을 한 칸 왼쪽으로 이동시킵니다.
규칙 R: 모든 것을 한 칸 오른쪽으로 이동시킵니다.
규칙 X: 처음 두 개의 항목을 서로 바꿉니다.

과제는 다음과 같습니다: 카드를 엉망으로 섞은 상태에서 시작할 때, 카드를 완벽한 순서로 되돌리기 위해 필요한 가장 짧은 왼쪽, 오른쪽, 그리고 교환 (Swap) 이동의 순서는 무엇일까요?

문제: 미로가 인간 (과 구형 컴퓨터) 에게는 너무 큽니다

카드 덱이 작다면, 인간이나 GAP라는 유명한 수학 소프트웨어와 같은 표준 컴퓨터 프로그램이 해결책을 찾아낼 수 있습니다. 하지만 카드의 개수 ( $n$ ) 가 늘어날수록 가능한 배열의 수가 폭발적으로 증가합니다.

$n=20$ 인 경우, 미로는 거대합니다.
$n=100$ 인 경우, 미로는 너무 커서 우주에 있는 원자 수보다 더 많은 경로가 존재합니다.

구형 컴퓨터 프로그램들은 막힙니다. 그들은 모든 단일 경로를 매핑하려고 시도하다가 메모리가 부족해지고 포기해 버립니다. 저자들은 **인공지능 (AI)**이 모든 인치를 매핑하지 않고도 이러한 거대한 미로를 통과할 길을 찾을 수 있는 현명한 탐험가 역할을 할 수 있는지 확인하고 싶어 했습니다.

해결책: AI 에게 길을 "추측"하도록 가르치기

저자들은 CayleyPy RL이라는 시스템을 구축했습니다. 이를 미로를 항해하도록 훈련시키는 로봇이라고 생각하세요. 그들은 **강화 학습 (Reinforcement Learning, RL)**이라는 방법을 사용했습니다.

다음은 간단한 비유를 사용하여 로봇을 훈련시킨 방법입니다:

1. "워밍업" (확산 거리)
유리잔에 물 한 방울을 떨어뜨린다고 상상해 보세요. 잉크는 무작위로 퍼져 나갑니다. 특정 지점이 중심으로부터 얼마나 멀리 떨어져 있는지 알고 싶다면, 잉크가 그곳에 도달하는 데 걸리는 시간을 보면 됩니다.

AI 는 먼저 수백만 개의 "무작위 보행" (잉크가 퍼지는 것과 같은) 을 관찰하며 학습했습니다. AI 는 가장 짧은 경로를 알지는 못했지만, 거리에 대한 "느낌"을 배웠습니다. "내가 여기에 있다면, 보통 집으로 가려면 무작위 이동이 약 50 회 정도 걸릴 것 같다"는 것을 알게 된 것입니다.
이는 AI 에게 대략적인 지도를 제공했지만, 완벽하지는 않았습니다.

2. "스마트 훈련" (강화 학습)
다음으로, 그들은 AI 에게 더 똑똑해지도록 가르쳤습니다. 무작위 보행에 기반한 추측만 하는 대신, Deep Q-Learning이라는 기법을 사용했습니다.

AI 가 매 이동마다 "페널티"를 받는 게임을 한다고 상상해 보세요. AI 는 가장 적은 페널티로 결승선에 도달하고 싶어 합니다.
AI 는 다양한 이동을 시도하고, 어떤 이동이 더 가까이 가게 하는지 확인하며, 더 나은 추측을 할 수 있도록 뇌 (신경망) 를 조정했습니다.
혁신: 그들은 "잉크 퍼짐" 직관과 "게임 플레이" 논리를 결합했습니다. 이는 일반적으로 더 간단한 알고리즘을 가두는 데드엔드 (국소 최소값) 에 빠지는 것을 AI 가 피하도록 도왔습니다.

3. "빔 탐색" (탐험가 팀)
이 부분이 가장 중요합니다. 한 명의 탐험가를 미로에 보내는다고 상상해 보세요. 그들이 잘못된 방향으로 가면 당신은 패배합니다.

대신, 저자들은 팀 (빔) 을 보냈습니다.
모든 분기점에서 팀은 갈라집니다. 그들은 가장 유망한 상위 10,000 개의 경로를 유지하고 나쁜 경로는 버립니다.
거대한 팀 (경우에 따라 수백만 개의 경로) 을 유지함으로써, 대부분의 탐험가가 길을 잃더라도 그중 적어도 한 명은 완벽한 가장 짧은 경로를 찾을 수 있도록 보장합니다.

"마법 트릭" (X-트릭)

저자들은 재미있는 작은 단축키를 발견했습니다. 코드에 논리 한 줄을 추가했습니다:

만약 처음 두 카드가 이미 올바른 순서라면, 교환하지 마십시오.

이는 인간에게는 명백해 보이지만, 컴퓨터에게는 게임 체인저였습니다. X-트릭이라고 부른 이 작은 규칙 덕분에 그들의 AI 는 100 장의 카드 ( $n=100$ ) 가 포함된 미로를 풀 수 있게 되었습니다.

트릭 없이: AI 는 약 40 장의 카드만 처리할 수 있었습니다.
트릭과 함께: 100 장 이상의 카드를 처리했으며, 약 20 장의 카드에서 충돌했던 구형 컴퓨터 소프트웨어 (GAP) 를 능가했습니다.

그들이 증명했던 것 (수학 부분)

단순히 빠른 솔버를 구축하는 것을 넘어, 그들은 이러한 미로의 수학에 대한 발견을 위해 AI 를 사용했습니다:

"신의 숫자" 추측: 수학에는 $n$ 장의 카드를 섞는 가장 어려운 경우가 정확히 $n(n-1)/2$ 번의 이동이 필요하다는 유명한 추측이 있습니다. AI 는 거대한 숫자에 대해 이를 테스트했고, 이보다 더 어려운 섞임은 단 한 번도 발견하지 못했습니다. 이는 이 공식이 절대적인 한계라는 아이디어를 강력하게 지지합니다.
"가장 긴" 섞임: 그들은 가능한 가장 혼란스러운 단일 섞임 ("가장 긴 원소") 을 식별하고, 이를 이동으로 분해하는 방법을 정확히 증명했습니다.
새로운 경계: 그들은 수학적으로 미로가 특정 크기보다 작을 수 없고 다른 크기보다 클 수 없음을 증명하여 답을 상당히 좁혔습니다.
미로의 모양: 그들은 시작점으로부터의 거리에 따라 존재하는 섞임의 수를 세어보면, 숫자들이 완벽한 종 모양 (정규 분포) 을 따르지 않는다는 것을 발견했습니다. 대신, 그들은 **구벨 분포 (Gumbel distribution)**라고 불리는 기묘하고 비대칭적인 모양을 따릅니다.

결과: AI 대 구형 수호자

이 논문은 새로운 AI 방법을 표준 컴퓨터 대수 시스템인 GAP와 비교합니다:

GAP: 약 20 장의 카드까지 해결 가능합니다. 수 시간에서 수 일이 걸립니다. 찾은 경로들은 종종 길고 비효율적입니다.
CayleyPy RL (AI): 약 100 장의 카드까지 해결 가능합니다. 훨씬 더 빠릅니다. 이론적으로 가능한 가장 짧은 경로에 매우 근접한 경로를 찾습니다.

요약

저자들은 복잡한 수학 문제를 거대한 미로처럼 취급하는 똑똑한 AI 시스템을 만들었습니다. 무작위 추측과 스마트한 학습을 결합하고 거대한 "팀"의 가상 탐험가들을 보내는 방식으로, 그들은 전통적인 컴퓨터로는 너무 큰 미로를 항해할 수 있었습니다. 그들은 또한 이전보다 5 배 더 큰 문제를 해결할 수 있게 해주는 작은 "치트 코드 (X-트릭)"를 발견했으며, 동시에 이러한 미로의 구조에 대한 새로운 수학 사실을 증명했습니다.

그들은 또한 코드와 과제를 Kaggle이라는 플랫폼에 올려놓아, 다른 사람들이 그들의 기록을 깨고 이러한 퍼즐의 더 어려운 버전을 해결하는 데 도움을 줄 수 있도록 초대했습니다.

기술 요약: CayleyPy RL: Cayley 그래프에서의 경로 탐색과 강화 학습

문제 정의
본 논문은 특히 왼쪽 순환 이동 ( $L$ ), 오른쪽 순환 이동 ( $R$ ), 그리고 첫 두 원소의 전치 ( $X$ ) 로 생성된 대칭군 $S_n$ 에 초점을 맞춘, 극도로 큰 유한 Cayley 그래프에서의 경로 탐색 문제를 다룬다. 이 구성은 LRX Cayley 그래프로 알려져 있으며 OEIS 시퀀스 A186783 에 해당한다. 핵심적인 수학적 도전 과제는 군 원소를 생성元の 가장 짧은 곱으로 분해하는 것 (그래프에서 최단 경로 찾기) 이다. 이 문제는 일반적인 유한 Cayley 그래프에 대해 NP-하드 문제이다. GAP 과 같은 고전적인 컴퓨터 대수 시스템은 Schreier-Sims 알고리즘에 의존하는데, 이는 종종 지수적으로 긴 경로를 생성하며 $10^{30}$ 을 초과하는 크기 (대략 $S_n$ 의 경우 $n \approx 20$ ) 의 군을 처리하지 못한다. 저자들은 $10^{70}$ 까지의 크기 (예: $n \approx 40$ 에서 $100$) 를 처리할 수 있으며, 최적 또는 최적에 가까운 경로를 생성할 수 있는 효율적인 인공지능 기반 접근법을 개발하는 것을 목표로 한다.

방법론
저자들은 확산 거리 (diffusion distances) 기반의 사전 학습 전략과 강화 학습 (RL), 구체적으로 Deep Q-Learning (DQN) 을 결합한 하이브리드 방법론을 제안한다.

강화 학습 프레임워크: 경로 탐색 문제는 상태 $s$ 에서 항등원 $e$ 로 가는 최단 경로를 찾는 문제로 설정된다. 이는 거리 함수 $d(s)$ 가 $d(s) = 1 + \min_{t \in N(s)} d(t)$ 를 만족하는 벨만 방정식을 사용하여 모델링된다. 표준 DQN 은 신경망을 사용하여 이 가치 함수를 근사하도록 적응된다.
확산 거리 사전 학습: "희소 보상" 문제와 표준 DQN 초기화에 내재된 노이즈를 해결하기 위해 저자들은 "워밍업" 단계를 도입한다. 그들은 목표에서 시작하는 무작위 보행 (diffusion) 을 통해 학습 데이터를 생성한다. 신경망은 먼저 이러한 무작위 보행의 단계 수 (확산 거리) 를 예측하도록 훈련된다.
수정된 DQN: 사전 훈련된 네트워크는 수정된 DQN 알고리즘을 사용하여 미세 조정된다. 결정적으로, 벨만 업데이트 목표는 무작위 보행 생성 동안 상태가 처음 방문된 시간 단계 $k$ 에 따라 클리핑된다. 이는 네트워크가 거리를 과대평가하는 것을 방지하고 훈련을 안정화한다.
가이드 빔 탐색: 신경망이 거리를 추정하도록 훈련되면, 빔 탐색 알고리즘을 위한 휴리스틱 함수로 작용한다. 빔 탐색은 각 단계에서 가장 유망한 상태의 고정된 수 ( $W$ ) 를 유지하며, 이웃을 확장하고 네트워크의 예측에 기반하여 상위 $W$ 개를 선택한다. 이는 탐욕적 탐색의 일반적인 실패 모드인 지역 최소값에 갇히는 것을 방지한다.
"X-트릭": LRX 생성자에 대한 특정 휴리스틱 수정이 도입된다. 만약 순열의 첫 두 원소가 이미 정렬되어 있다면, 그들을 교환하는 생성자 $X$ 는 이웃 집합에서 제외된다. 이 단일 줄 수정은 검색 공간을 극적으로 줄이고 혼합 시간을 개선한다.
되돌아가지 않음 (Non-backtracking): 저자들은 거리 추정치의 분산을 줄이고 지역 최소값에서의 정체성을 방지하기 위해 무작위 보행 생성과 빔 탐색 모두에 되돌아가지 않는 제약을 포함시킨다.

주요 기여

알고리즘적 발전: 본 논문은 확산 거리 사전 학습과 수정된 DQN 의 독창적인 결합을 제시한다. 이 접근법은 표준 DQN 의 한계 (희소 보상, 노이즈가 있는 목표) 를 극복하고 고전적 방법들을 능가한다.
성능 벤치마크: 제안된 방법은 사전 지식 없이 $n \approx 44$ 까지의 LRX Cayley 그래프에 대한 경로를 성공적으로 찾으며, "X-트릭"을 활용할 경우 $n \approx 100$ 까지 찾는다. 이는 $n \approx 20$ 으로 제한된 GAP 의 능력을 크게 초과한다. AI 방법은 비교 가능한 $n$ 에 대해 GAP 보다 더 짧은 경로를 생성하고 더 빠르게 실행된다.
수학적 결과 및 가설:
- 지름 가설: 저자들은 LRX Cayley 그래프의 지름이 $n(n-1)/2$ 라는 OEIS-A186783 가설을 강력히 지지한다. 그들은 $n \le 15$ 에 대해서는 브루트 포스 BFS 를 통해, Kaggle 챌린지를 통해 $n$ 이 200 까지인 경우에는 AI 분해를 통해 이를 검증했으며, 제안된 길이보다 짧은 분해는 발견되지 않았다.
- 최장 원소: 그들은 고유한 "최장 원소" $\ell_n = (1, 0, n-1, n-2, \dots, 3, 2)$ 를 식별하고 길이 $n(n-1)/2$ 인 명시적 분해를 제공한다.
- 경계: 본 논문은 구성적 알고리즘을 통해 지름에 대한 하한 $n(n-1)/2 - n/2 - 1$ 과 상한 $n(n-1)/2 + 3n$ 을 증명한다. 경험적 알고리즘은 $n(n-1)/2 + n/2$ 의 더 엄격한 경계를 제안한다.
- 성장 분포: 수치 실험은 큰 $n$ 에 대해 LRX 그래프의 성장 함수가 이웃 전치 그래프에서 관찰된 가우시안 분포와 대조적으로 왼쪽으로 치우친 구벨 (Gumbel) 분포를 따르는 것으로 시사한다.
- 혼합 시간: 표준 무작위 보행의 혼합 시간은 $O(n^3)$ 과 $O(n^3 \log n)$ 사이이지만, 저자들은 "X-트릭"으로 수정된 무작위 보행이 더 빠르게 혼합되어 시간 복잡도가 $O(n^2)$ 일 것이라고 가설을 세운다.
- 스펙트럼: LRX 그래프의 스펙트럼은 균일 분포를 따르는 것으로 보인다.
오픈 소스 및 크라우드소싱: 저자들은 "CayleyPy" 프로젝트를 공개하고 최장 원소 분해 및 최적 알고리즘 찾기를 위한 Kaggle 챌린지를 만들어 AI 및 수학 커뮤니티 간의 협력을 장려하는 크라우드소싱 솔루션을 창출했다.

결과

효율성: $n=20$ 의 경우, GAP 은 길이 217,944 인 경로를 찾는 데 41 분 이상이 소요되는 반면, 확산 거리 방법은 4 분 미만에 길이 190 의 최적 경로를 찾는다.
확장성: "X-트릭"을 사용하면 시스템은 단일 GPU 에서 약 8.5 시간 만에 $n=100$ (그래프 크기 $\approx 10^{157}$ ) 인 인스턴스를 해결하여, 가설 지름 4,950 에 비해 길이 16,632 인 경로를 찾았다.
모델 성능: 다층 퍼셉트론 (MLP) 과 그래디언트 부스팅 (CatBoost/XGBoost) 과 같은 단순한 모델들이 종종 이 특정 작업에서 트랜스포머 및 CNN 과 같은 복잡한 아키텍처보다 우수한 성과를 보였다.
빔 탐색: 경로를 찾는 성공률은 빔 너비에 크게 의존하며, 빔 크기가 증가함에 따라 연구 커뮤니티의 "아이디어 교환"과 유사하게 초선형적인 개선이 나타난다.

의의
본 논문은 특히 AI 를 활용한 계산 실험이 Cayley 그래프에 대한 수학적 연구를 크게 발전시킬 수 있다고 주장한다. 이는 AI 방법이 확장성 (훨씬 더 큰 $n$ 처리) 과 해결책의 품질 (더 짧고 최적에 가까운 경로 찾기) 모두에서 고전적인 컴퓨터 대수 시스템을 "초월"할 수 있음을 보여준다. 이 작업은 이론적 군론과 실용적 AI 간의 간극을 메우며, 엄격한 경계, 성장 및 혼합 시간에 대한 새로운 가설, 그리고 이전에 처리 불가능했던 극도로 큰 상태 공간에서의 경로 탐색 문제를 해결하기 위한 프레임워크를 제공한다. 저자들은 이를 이론 과학의 다른 복잡한 계획 문제에 AI 를 적용하는 단계로 위치시킨다.