한국어 초록
이 논문은 대칭 군(symmetry group) 설정에서 고전 코딩 정리(Coding Theorem)의 직접적인 유사물을 확립한다. 우리는 이진 문자열 집합 위의 계산 가능한 쌍사(bijection)를 대칭(symmetry)이라 부르고, 문자열의 대칭 사전확률(symmetry prior)을 주어진 군에서 무작위로 선택된 대칭이 그 문자열을 유일한 고정점(unique fixed point)으로 갖는 확률로 정의한다. 우리는 고정점-수축 가능(fix-retractable)한 대칭 군, 즉 모든 문자열에 대해 격리 대칭(isolating symmetry)을 선택하는 계산 가능한 단면(section)을 허용하는 군에 대해, 대칭 사전확률이 보편적 하반계산가능 준측도(universal lower semi-computable semi-measure)임을 보인다. 이 경우 기하학적 코딩 정리(Geometric Coding Theorem)가 성립한다. 우리는 또한 G의 부분군과 이진 문자열 부분집합 사이의 갈루아(Galois) 연결을 발전시켜 닫힌 점(closed points)과 극대 닫힌 부분군(maximal closed subgroups)을 특성화하고, 밀집 부분군(dense subgroups)의 결합 반 격格(join-semilattice)를 탐구한다. 우리의 결과는 알고리즘 정보 이론(algorithmic information theory)과 군론(group theory)을 통합하고 대칭 유도 복잡도 측도(symmetry-induced complexity measures)를 연구하기 위한 틀을 제공한다. 이 논문은 계산 알고리즘 통계(Computational Algorithmic Statistics, CAS) 시리즈의 첫 번째 편이다.
원문 초록
This paper establishes a direct analogue of the classical Coding Theorem in the setting of symmetry groups. We consider computable bijections on the set of binary strings, called symmetries and define the symmetry prior of a string as the probability that a randomly chosen symmetry from a given group has the string as its unique fixed point. We show that for any fix-retractable symmetry group, a group admitting a computable section that selects an isolating symmetry for every string, the symmetry prior is a universal lower semi-computable semi-measure. In this case, the Geometric Coding Theorem holds. We also develop a Galois connection between subgroups of G and subsets of binary strings, characterizing closed points and maximal closed subgroups, and explore the join-semilattice of dense subgroups. Our results unify algorithmic information theory with group theory and provide a framework for studying symmetry-induced complexity measures. This paper is the first in a series on Computational Algorithmic Statistics (CAS).
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2607.13796v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
그래프 신경망을 이용한 Cayley 그래프로부터 대수적 성질을 학습하기 위한 일반 프레임워크
A General Framework for Learning Algebraic Properties from Cayley Graphs using Graph Neural Networks
본 연구에서는 Cayley 그래프 표현으로부터 유한군의 대수적 성질을 학습하기 위한 일반적인 그래프 신경망(GNN) 프레임워크를 제안한다. 이 프레임워크는 공통 그래프 구성 절차, 특징 표현, 학습 방법론, GNN 아키텍처로 구성된 통합 계산 파이프라인을 제공하며, 분류 과제 간에는 목표 레이블링 함수만 달라진다. 제안된 접근법의 일반성을 입증하기 위해, 아벨성(abelianity), 멱零성(nilpotency), 가해성(solvability)의 세 가지 대표적인 대수적 성질을 고려한다. 여러 고전적 군족에서 추출한 176개 유한군으로 구성된 벤치마크에 대해 실험을 수행했으며, 각 분류 과제에 모든 군이 포함되었다. 클래스 불균형을 해결하기 위해, 학습 중 적절한 경우 클래스 가중 교차 엔트로피 손실을 사용했다. 또한 PSL(2,q) 군족은 테스트 전용으로 예약하여, 프레임워크가 이전에 보지 못한 군족으로 일반화하는 능력을 평가할 수 있게 했다. 최고 성능 모델은 아벨성, 멱零성, 가해성에 대해 각각 테스트 균형 정확도 1.000, 0.856, 0.875를 달성했다. 모든 과제에 동일한 계산 프레임워크를 사용했음에도, 서로 다른 대수적 성질에 대해 최적인 GNN 아키텍처가 달랐으며, 이는 어떤 성질을 학습하는 데 필요한 표현 복잡도가 그 성질의 기저 대수 구조에 따라 달라짐을 시사한다. 이 결과는 GNN이 Cayley 그래프 표현으로부터 여러 대수적 성질을 직접 효과적으로 학습할 수 있으며, 보지 못한 군족에 대해서도 강한 일반화를 보임을 보여준다. 더 넓게 보면, 제안된 프레임워크는 그래프 기반 머신러닝을 이용해 유한군의 대수적 성질을 연구하기 위한 계산 방법론을 확립한다.
Learning Subgroup Relations Using Siamese Graph Neural Networks
중첩 및 계층적 반복으로부터의 텍스트 거리: 압축 기반 관점
Text Distance from Nested and Hierarchical Repetitions: A Compression-Based Perspective
우리는 알고리즘 정보 이론(AIT)에 기반한 구조적 시퀀스 분석을 위한 새로운 방법을 제시한다. 핵심은 Ladderpath 접근법으로, 언어 시퀀스 내 반복되는 하위 구조들 사이의 중첩 및 계층적 관계를 추출한다. 이는 최소 생성 프로그램을 통해 데이터를 기술하는 AIT 원리의 구체적 구현이다. 이러한 구조를 기반으로 세 가지 거리 측도를 정의한다: 정규화 압축 거리(NCD)와 Ladderpath 표현에서 직접 도출된 두 가지 대안적 거리이다. $k$-최근접 이웃 분류기와 결합하여, 이 거리들은 분포 내(in-distribution), 분포 외(OOD), 퓨샷(few-shot) 텍스트 분류 태스크 전반에 걸쳐 강력하고 일관된 성능을 달성한다. 특히, 세 가지 방법 모두 OOD 및 저자원(low-resource) 환경에서 gzip 기반 NCD와 BERT를 능가한다. 이 결과는 Ladderpath가 포착하는 구조적 표현이 시퀀스의 본질적 속성을 보존하며, 텍스트 모델링을 위한 경량화되고 해석 가능한 학습 불필요(training-free) 대안을 제공함을 보여준다. 본 연구는 구조적이고 도메인 불가지론적인 시퀀스 이해를 위한 AIT 기반 접근법의 잠재력을 부각한다.
유한군의 가역성 예측을 위한 그래프 신경망
Graph Neural Networks for Predicting Solvability of Finite Groups
우리는 가역성에 따른 유한군 분류를 위한 그래프 신경망(GNN) 프레임워크를 제시한다. 케일리 그래프(CG)를 포함한 유한군과 연관된 그래프 표현을 사용하여, 제안된 모델은 구조적 그래프 정보만으로 가역군과 비가역군을 구별하도록 학습된다. 이 프레임워크는 군론에서 나타나는 대수적 성질을 GNN이 어느 정도까지 학습할 수 있는지 조사하기 위해, 학습 데이터셋 밖의 군들에 대해 평가된다. 더 넓게 보면, 본 연구는 대수적 구조와 유한군의 그래프 기반 기하학적 표현 사이의 관계를 탐구한다. 본 연구는 GNN이 그래프 기반 표현으로부터 유한군의 대수적 성질을 학습할 수 있는지에 대한 개념 증명(proof-of-concept) 조사를 목적으로 한다.
반복되는 패턴의 계층적 재사용을 통한 언어 복잡도 측정
Measuring language complexity from hierarchical reuse of recurring patterns
우리는 알고리즘 정보 이론에 기반한 언어 복잡도 측정치로서 ladderpath 지수를 소개합니다. 이는 반복되는 하위 구조의 계층적 재사용을 통해 시퀀스를 재구성하는 데 필요한 최소 단계를 계산하며, 콜모고로프 복잡도(Kolmogorov complexity)와 관련되지만 구별되는 정확히 계산 가능하면서도 제한된 형태의 알고리즘 압축 가능성을 포착합니다. 우리는 Parallel Universal Dependencies 데이터셋의 21개 병렬 말뭉치에 ladderpath 접근법을 적용합니다. Ladderpath 지수는 언어 간에 거의 불변이며, 말뭉치 길이보다 훨씬 적게 변동합니다. 이는 모든 말뭉치가 통합된 이진 표현으로 매핑될 때 더욱 뚜렷해지며, 표현 독립적 관점에서 등가 복잡도 가설(equi-complexity hypothesis)을 뒷받침하는 증거가 됩니다. 또한 문자 집합 크기와 말뭉치 길이 사이, 그리고 어휘 수준과 말뭉치 수준의 재구성 복잡도 사이의 상충 관계(trade-off)를 관찰했는데, 이는 총 복잡도가 보존되어 언어적 수준 전반에 걸쳐 재분배된다는 상충 가설을 지지합니다. Ladderpath 접근법이 어떠한 언어적 입력 없이 식별한 재사용 가능한 하위 구조는 자연 어휘에서 확인된 단어 및 형태소적 구성 요소와 일치합니다. Ladderpath 접근법이 포착한 계층적 재사용은 인지 과학에서 제안된 청킹 메커니즘(chunking mechanisms)과 유사한데, 이는 인간의 인지 시스템이 공유된 메모리 및 처리 제약 조건 하에서 언어적 입력을 중첩된 재사용 가능한 단위로 압축하는 방식입니다. 인지적 청킹과 ladderpath 접근법 사이의 이러한 연결은 등가 복잡도 및 상충 가설에 대한 새로운 해석을 제공하며, 이 두 가설이 모든 인간 언어의 언어 처리를 기반으로 하는 공유된 인지 아키텍처에 뿌리를 두고 있음을 보여줍니다.
장기 비아벨 상태 추적을 위한 보류 전이-쌍 반증자
A Held-Out Transition-Pair Falsifier for Long-Horizon Non-Abelian State Tracking
상태 추적(state tracking)은 시퀀스 모델의 뚜렷한 한계를 드러낸다. 관련 신호는 종종 관측된 토큰의 요약이 아니라, 비가환(non-commutative) 변환을 통해 진화하는 순서 있는 잠재 상태이다. 유한 비아벨(non-Abelian) 군 추적을 위한 보류 전이-쌍(hold-out transition-pair) 반증자를 제안한다. 이 프로토콜은 학습 중 선택된 순서 있는 생성자(generator) 쌍을 금지하고, 평가에서 동일한 국소 패턴을 요구하여 하나의 직접적인 국소 전이 암기 경로를 차단한다. 통제된 $S_3 \times S_3$ 벤치마크에서, 길이 8 시퀀스만으로 학습된 투영 순환 상태 모델은 5개 시드에 걸쳐 최대 1,048,576 토큰까지의 평가 수평(horizon)에서 오류 없는 최종 상태 예측(수평당 완벽한 250/250)을 생성한다. 동일 프로토콜 하에서 bag, GRU, 단일 구성의 구조화된 상태-공간 모델(structured state-space model)을 포함한 매칭된 네이티브 readout 기준선은 바닥(floor) 수준 근처에 머문다. 투영-매칭된 GRU, 구조화된 SSM, 그리고 유사한 유한군 프로토타입 readout을 갖춘 bag 기준선도 동일 분할에서 우연(chance) 수준 근처에 머문다. 메커니즘 진단은 강한(hard) 투영이 낮은 준동형(homomorphism) 오류, 낮은 상태 일관성 drift, 그리고 자명하지 않은(non-trivial) 교환자(commutator) 분리와 일치하는 반면, 완화된(softened) 투영은 최종 상태 정확도를 붕괴시킴을 보여준다. 클린 분할 감사는 학습과 평가 파티션 간 축약 단어(reduced-word)의 문자 그대로 중복이 0이고 구조적 템플릿 중복도 0임을 검증한다. 이 증거는 일반적인 아키텍처 순위가 아니라 이 통제된 유한군 반증자에 한정된다. 그 범위 안에서, 명시적 투영 비가환 상태 합성은 장기 잠재 상태 추적을 위한 유용한 귀납적 바이어스로 작용한다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.