arXiv:2511.23152v5 cs.LG

오컴의 면도날로서의 함수적 압축: 민감도 최소화로부터의 대수적 복잡도

Functional Compression as Occam's Razor: Algebraic Complexity from Sensitivity Minimization

Dongsung Huh, Lior Horesh, Halyun Jeong

제출 2026-11-18

한국어 초록

데이터로부터 이산적 대수 구조를 발견하는 것은 기계학습의 근본적인 과제이다. 본 논문은 연속적 학습 목적함수가 저랭크 표현이 아니라 공유된 대수적 합성을 통해 데이터를 표현하는 함수적 압축을 어떻게 선호하게 할 수 있는지를 묻는다. 군 연산에 대한 선호를 보인 바 있는, 대수적 완성(유한 이항 연산 복원)을 위한 표준적 분해 모형의 전역 최적해를 분석한다. 대수적 복잡도는 정확한 복원 조건 아래에서 파라미터 민감도의 하한(infimum)으로 측정한다. 보편적인 복잡도 하한선을 확립하며, 이를 달성하면 잠재 표현의 기하적 정렬과 유니터리성이 강제된다. 하한선에서는 입력 표현이 대응하는 출력 표현으로 합성되며, 연산표 전반에 걸친 이들의 재사용이 이러한 국소적 항등식을 전파하여 전역적으로 공유되는 대수 구조를 강제한다. 하한선이 달성되지 않으면 양의 간극이 이를 실현 가능한 하한과 분리한다. 소거 가능(cancellative) 연산의 경우 하한선 달성은 모델의 잠재 표현이 단사 준동형사상이 되도록 강제하며, 이는 목표가 군과 아이소토픽(isotopic)임과 동치이다. 이 경우 모든 전역 최소화기는 아이소토피와 유니터리 게이지를 제외하면 기저 군의 유니터리 좌정규 표현과 동치이며, 이로써 Huh(2025)의 핵심 추측을 해결한다. 소거 불가능 연산의 경우 하한선 달성은 정확한 구조적 중복(동일한 행 또는 열)을 강제하며, 직교정규 출력 행렬을 갖는 목표의 행·열 축약 표에 대한 유니터리 분해와 동치이고, 정확한 복원과 양립하는 가장 적은 수의 서로 다른 입력 행렬을 낳는다. 그 결과로 얻어지는 소거 가능 표는 군 아이소토프 표에 임베딩된다. 이 분석은 함수적 압축을 향한 구조적 편향을 드러내는데, 민감도 하한선에서는 잠재 표현의 대수적 합성이 목표 연산을 구현한다.

원문 초록

Discovering discrete algebraic structures from data is a fundamental challenge in machine learning. We ask how continuous learning objectives can favor functional compression---representing data through shared algebraic composition rather than low-rank representations. We analyze the global optima of a canonical factorization model for algebraic completion (recovering finite binary operations) that demonstrated a preference for group operations. We measure algebraic complexity by the infimum of parameter sensitivity under exact reconstruction. We establish a universal complexity floor, whose attainment forces geometric alignment and unitarity of the latent representations. At the floor, input representations compose into the corresponding output representations; their reuse across the operation table propagates these local identities to enforce a globally shared algebraic structure. If the floor is not attained, a positive gap separates it from the feasible infimum. For cancellative operations, floor attainment forces the model's latent representation to be an injective homomorphism, equivalent to the target being isotopic to a group. In this case, every global minimizer is equivalent to the underlying group's unitary left-regular representation, up to isotopy and unitary gauge, resolving the central conjecture of Huh (2025). For non-cancellative operations, floor attainment forces exact structural redundancies (identical rows or columns) and is equivalent to a unitary factorization of the target's row- and column-reduced table with orthonormal output matrices, yielding the fewest distinct input matrices compatible with exact reconstruction. The resulting cancellative table then embeds in a group-isotope table. This analysis reveals a structural bias toward functional compression: at the sensitivity floor, algebraic composition of latent representations implements the target operation.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2511.23152v5제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.