강한 모델로서의 궤도: 대칭성 하의 콜모고로프 구조 함수
Orbits as Strong Models: Kolmogorov Structure Function under Symmetry
한국어 초록
알고리즘 통계학에서 강한 모델은 본질적으로 $\{0,1\}^n$의 단순한 분할의 셀이다. 본 연구는 대칭성에서 유래하는 분할, 즉 문자열에 작용하는 군의 궤도 분할과 그로부터 유도되는 구조 함수 $h^G_x$를 연구한다. 집합이 이러한 분할의 셀인 것은 그 집합의 집합별 안정자군이 그 위에 추이적으로 작용할 때 그리고 그때에 한하므로, $h^G_x$는 $G$-동차 집합으로 제한된 콜모고로프 구조 함수이다. 전체 대칭군의 경우 이는 모든 모델과 정확히 강한 모델들을 복원한다. $GL(n,2)$의 경우 셀은 선형 동차 집합이며, $h^{GL}_x$는 $C(x)-\alpha$와 $n-\alpha$ 사이의 띠에 놓이고 양쪽 경계가 모두 달성되며, 일부 확률적 정규 문자열은 선형 대칭성에는 보이지 않는 단순한 구조를 가진다. 각 순열군을 배치를 갖는 번사이드 환 유형으로 기술함으로써, 탐색할 수 있을 만큼 작은 대칭성 가설 공간은 단순한 구조를 놓칠 만큼 작다는 것을 보인다. 마지막으로 궤도 모델 탐색을 부분군 격자 위의 가치 추정으로 정식화하며, 계산 가능한 한계, 검증된 학습 목표, 그리고 몬테카를로 트리 탐색의 격자 버전을 제시한다.
원문 초록
Strong models in algorithmic statistics are essentially the cells of simple partitions of $\{0,1\}^n$. We study the partitions that come from symmetry, the orbit partitions of groups acting on strings, and the structure function $h^G_x$ they induce. A set is a cell of such a partition exactly when its setwise stabiliser acts transitively on it, so $h^G_x$ is Kolmogorov's structure function restricted to $G$-homogeneous sets. For the full symmetric group this recovers all models and exactly the strong ones. For $GL(n,2)$ the cells are the linearly homogeneous sets, $h^{GL}_x$ lies in a band between $C(x)-\alpha$ and $n-\alpha$ with both edges attained, and some stochastic normal strings have simple structure that is invisible to linear symmetry. Writing each permutation group as a Burnside-ring type with a placement, we show that any space of symmetry hypotheses small enough to search is small enough to miss simple structure. Finally we cast the search for orbit models as value estimation on subgroup lattices, with computable bounds, certified training targets and a lattice version of Monte Carlo tree search.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2609.40290v3제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.