2025-11-16T23:37:13.075377

The Algorithmic Regulator

Ruffini
The regulator theorem states that, under certain conditions, any optimal controller must embody a model of the system it regulates, grounding the idea that controllers embed, explicitly or implicitly, internal models of the controlled. This principle underpins neuroscience and predictive brain theories like the Free-Energy Principle or Kolmogorov/Algorithmic Agent theory. However, the theorem is only proven in limited settings. Here, we treat the deterministic, closed, coupled world-regulator system $(W,R)$ as a single self-delimiting program $p$ via a constant-size wrapper that produces the world output string~$x$ fed to the regulator. We analyze regulation from the viewpoint of the algorithmic complexity of the output, $K(x)$. We define $R$ to be a \emph{good algorithmic regulator} if it \emph{reduces} the algorithmic complexity of the readout relative to a null (unregulated) baseline $\varnothing$, i.e., \[ Δ= K\big(O_{W,\varnothing}\big) - K\big(O_{W,R}\big) > 0. \] We then prove that the larger $Δ$ is, the more world-regulator pairs with high mutual algorithmic information are favored. More precisely, a complexity gap $Δ> 0$ yields \[ \Pr\big((W,R)\mid x\big) \le C\,2^{\,M(W{:}R)}\,2^{-Δ}, \] making low $M(W{:}R)$ exponentially unlikely as $Δ$ grows. This is an AIT version of the idea that ``the regulator contains a model of the world.'' The framework is distribution-free, applies to individual sequences, and complements the Internal Model Principle. Beyond this necessity claim, the same coding-theorem calculus singles out a \emph{canonical scalar objective} and implicates a \emph{planner}. On the realized episode, a regulator behaves \emph{as if} it minimized the conditional description length of the readout.
academic

알고리즘 규제자

기본 정보

  • 논문 ID: 2510.10300
  • 제목: The Algorithmic Regulator
  • 저자: Giulio Ruffini
  • 분류: cs.CC cs.AI cs.IT cs.SY eess.SY math.IT q-bio.NC
  • 발표 시간: 2025년 10월 14일 (arXiv 사전인쇄본)
  • 논문 링크: https://arxiv.org/abs/2510.10300

초록

본 논문은 알고리즘 정보 이론(AIT)을 기반으로 고전적인 규제자 정리를 재검토합니다. 이 정리는 특정 조건 하에서 모든 최적 제어기가 자신이 규제하는 시스템의 모델을 포함해야 한다고 주장합니다. 저자는 결정론적 세계-규제자 결합 시스템 (W,R)(W,R)을 단일의 자기-제한 프로그램으로 간주하고, 출력의 알고리즘 복잡도 K(x)K(x) 관점에서 규제를 분석합니다. "좋은 알고리즘 규제자"를 규제 없는 기준선과 비교하여 출력 알고리즘 복잡도를 감소시키는 규제자로 정의합니다. 즉, Δ=K(OW,∅)−K(OW,R)>0\Delta = K(O_{W,\varnothing}) - K(O_{W,R}) > 0입니다. 논문은 복잡도 차이 Δ\Delta가 클수록 높은 상호 알고리즘 정보를 가진 세계-규제자 쌍이 선호되며, 낮은 M(W:R)M(W:R)이 Δ\Delta의 증가에 따라 지수적으로 불가능해짐을 증명합니다.

연구 배경 및 동기

문제 배경

  1. 고전적 규제자 정리의 한계: Conant와 Ashby(1970)가 제시한 좋은 규제자 정리(GRT)는 "모든 좋은 규제자는 시스템의 모델이어야 한다"고 주장하지만, "모델"과 "좋은"의 정의가 너무 광범위하고 증명이 충분히 엄격하지 않습니다.
  2. 내부 모델 원리의 제한: 현대 제어 이론의 내부 모델 원리(IMP)는 엄격하지만 주로 선형 시불변(LTI) 시스템에 적용되며, 비선형 시스템으로의 확장에는 추가적인 구조적 가정이 필요합니다.
  3. 신경과학 이론의 필요성: 자유 에너지 원리와 Kolmogorov/알고리즘 에이전트 이론 등의 예측 뇌 이론은 "에이전트는 세계 모델을 포함해야 한다"는 관점을 뒷받침하기 위한 더 보편적인 이론적 기초가 필요합니다.

연구 동기

저자의 목표는:

  • 분포 무관하고 개별 수열에 적용 가능한 규제 이론 제공
  • 선형 가정 및 확률 모델의 제한 극복
  • 알고리즘 정보 이론 프레임워크 하에서의 규제자 정리 수립
  • 신경과학 및 인지과학에 더 엄격한 이론적 기초 제공

핵심 기여

  1. 알고리즘 규제자 프레임워크 제시: 알고리즘 정보 이론을 기반으로 규제자의 "좋고 나쁨"의 기준을 재정의하며, 출력의 압축 가능성을 평가 기준으로 사용합니다.
  2. 세 가지 주요 정리 수립:
    • 사후 형식 정리: 관측된 출력 x가 주어진 프로그램의 사후 분포
    • 대조 규제자 정리: 복잡도 차이와 상호 알고리즘 정보의 지수 관계 증명
    • 목표 함수 추론 정리: 규범적 스칼라 목표 함수 식별
  3. 분포 무관 이론 제공: 확률 분포 가정에 의존하지 않으며, 단일 실현 수열에 적용 가능합니다.
  4. 내부 모델 원리 보완: 정보 이론 수준에서 IMP의 구조적 필요 조건을 보완합니다.

방법론 상세 설명

작업 정의

결정론적 결합 세계-규제자 시스템 (W,R)(W,R)을 연구합니다. 여기서:

  • WW: 세계 프로그램(3-테이프 튜링 기계)
  • RR: 규제자 프로그램(3-테이프 튜링 기계)
  • NN: 고정 시간 범위
  • x=OW,R(N)x = O^{(N)}_{W,R}: 규제자 활성화 시 세계 출력
  • y=OW,∅(N)y = O^{(N)}_{W,\varnothing}: 규제자 비활성화 시 세계 출력

핵심 정의

알고리즘 "내부 모델" 정의

고정 범위 NN에서, M(W:R)>0M(W:R) > 0(동치: K(W∣R)<K(W)K(W|R) < K(W))이면 RR은 알고리즘 의미에서 WW의 내부 모델을 포함한다고 합니다.

좋은 알고리즘 규제자 정의

복잡도 차이를 다음과 같이 정의합니다: Δ:=K(OW,∅(N))−K(OW,R(N))\Delta := K(O^{(N)}_{W,\varnothing}) - K(O^{(N)}_{W,R})

Δ>0\Delta > 0이면 RR을 범위 NN에서 WW의 좋은 알고리즘 규제자라고 합니다.

주요 정리

정리 3.1: 프로그램 사후 형식

P((W,R)∣x)∈[1c~2,1c~1]⋅2K(x)−K(W,R)<1c~2M(W:R)P((W,R)|x) \in \left[\frac{1}{\tilde{c}_2}, \frac{1}{\tilde{c}_1}\right] \cdot 2^{K(x)-K(W,R)} < \frac{1}{\tilde{c}} 2^{M(W:R)}

정리 3.2: 확률 규제자 정리

Δ:=K(OW,∅(N))−K(OW,R(N))\Delta := K(O^{(N)}_{W,\varnothing}) - K(O^{(N)}_{W,R})일 때, 상수 C>0C > 0이 존재하여: P((W,R)∣OW,R(N),EbR)≤C⋅2M(W:R)2−ΔP((W,R)|O^{(N)}_{W,R}, E^R_b) \leq C \cdot 2^{M(W:R)} 2^{-\Delta}

이는 M(W:R)M(W:R)이 Δ\Delta의 1비트 감소할 때마다 사후 지지도가 약 2−12^{-1}의 인수만큼 손실됨을 의미합니다.

정리 3.3: 목표 함수 추론

보편적 사전 측도 하에서: log⁡2m(OW,R(N))m(OW,∅(N))=K(OW,∅(N))−K(OW,R(N))±O(1)\log_2 \frac{m(O^{(N)}_{W,R})}{m(O^{(N)}_{W,\varnothing})} = K(O^{(N)}_{W,\varnothing}) - K(O^{(N)}_{W,R}) \pm O(1)

즉, 실현된 에피소드에서 규제자는 K(OW,R(N))K(O^{(N)}_{W,R})을 최소화하는 것처럼 작동합니다.

기술적 혁신점

  1. 압축 관점의 규제: 규제를 출력을 더 압축 가능하게 만드는 과정으로 정의하여 제어 이론과 정보 이론을 연결합니다.
  2. 대조 분석: 규제 활성화/비활성화 시 복잡도 차이를 비교하여 규제 효과를 평가합니다.
  3. 보편적 사전: Solomonoff-Levin 보편 분포를 활용하여 분포 무관 분석 프레임워크를 제공합니다.
  4. 3-테이프 튜링 기계 모델: 표준 계산 모델을 사용하여 결과의 보편성을 보장합니다.

이론적 분석

내부 모델 원리와의 관계

논문은 AIT 프레임워크와 IMP의 차이를 상세히 비교합니다:

측면IMPAIT 프레임워크
가정LTI 시스템, 구조적 가정아키텍처 무관, 결정론적 결합
"모델" 정의동적 복사본알고리즘 의존성 M(W:R)>0M(W:R) > 0
필요성구조적정보 이론적
적용 범위고전적 규제단일 에피소드, 분포 무관

실용적 추정

Kolmogorov 복잡도는 계산 불가능하므로 실제로는 다음을 사용합니다:

  • Lempel-Ziv 압축기: K(⋅)K(\cdot)의 상한 추정값
  • 블록 분해 방법(BDM): 소규모 블록의 복잡도 테이블 조회
  • 신경망 압축기: 변분 자동 인코더 등 기반

가정용 온도 조절기 예시

논문은 온도 조절기를 예로 들어 프레임워크 적용을 설명합니다:

  • 세계 WW: 실내 열역학 + 외부 방해
  • 규제자 RR: 온도 조절기 로직
  • 출력 xx: 실내 온도 또는 오류 신호
  • 좋은 규제자: 온도를 규칙적인 데드존 패턴 내에 유지하여 규제 없는 경우보다 더 압축 가능하게 만듭니다.

관련 연구

고전적 규제 이론

  1. Conant-Ashby GRT (1970): 획기적 연구이나 정의가 모호함
  2. Francis-Wonham IMP (1975-76): 선형 시스템의 엄격한 결과
  3. 비선형 출력 규제: 추가적인 가해성 및 안정성 조건 필요

알고리즘 정보 이론

  1. Solomonoff 귀납법: 보편적 사전 및 부호화 정리
  2. Kolmogorov 복잡도: 개별 수열의 복잡성 측정
  3. 최소 기술 길이: 모델 선택 및 압축의 연결

신경과학 이론

  1. 자유 에너지 원리: 생물 에이전트가 변분 자유 에너지 최소화
  2. 예측 부호화: 뇌를 예측 기계로 간주
  3. 알고리즘 에이전트 이론: 압축 모델 기반 의식 이론

결론 및 논의

주요 결론

  1. 알고리즘 필요성: 지속적인 복잡도 이점 Δ>0\Delta > 0은 낮은 M(W:R)M(W:R)을 지수적으로 불가능하게 만듭니다.
  2. 규범적 목표: 부호화 정리는 규범적 스칼라 목표 함수를 계산으로 식별합니다.
  3. 에이전트 해석: 규제자는 기술 길이 최소화를 수행하는 것처럼 작동합니다.

한계

  1. 계산 불가능성: Kolmogorov 복잡도는 계산 불가능하여 근사가 필요합니다.
  2. 단일 에피소드 제한: 결과는 개별 실현을 기반으로 하며 여러 관측으로 신뢰도 향상이 필요할 수 있습니다.
  3. 진단 요구사항: 대조가 효과적이려면 적절한 읽기 신호 선택이 필요합니다.
  4. 상수 인수: 기계 관련 상수가 실제로는 상당할 수 있습니다.

향후 방향

  1. 다중 에피소드 확장: 여러 에피소드에 걸친 누적 증거 연구
  2. 근사 알고리즘: Kolmogorov 복잡도 추정 방법 개선
  3. 실험적 검증: 실제 제어 시스템에서 프레임워크 테스트
  4. 신경과학 응용: 뇌 기능 연구에 이론 적용

심층 평가

장점

  1. 이론적 엄격성: 고전적 규제자 정리의 엄격한 알고리즘 정보 이론 버전 제공
  2. 보편적 적용성: 선형 또는 확률 가정에 의존하지 않으며 더 넓은 범위에 적용 가능
  3. 깊은 통찰: 규제와 압축을 연결하여 새로운 이론적 관점 제공
  4. 학제간 가치: 신경과학 및 인지과학에 이론적 기초 제공

부족한 점

  1. 실용성 도전: Kolmogorov 복잡도의 계산 불가능성이 직접 적용을 제한합니다.
  2. 경험적 검증 부족: 대규모 실제 시스템의 검증이 부족합니다.
  3. 상수 의존성: 결과의 상수 인수가 실제 적용 효과에 영향을 미칠 수 있습니다.
  4. 단일 관점: 주로 정보 이론 관점에 초점을 맞추어 다른 중요 요소를 간과할 수 있습니다.

영향력

  1. 이론적 기여: 제어 이론에 새로운 정보 이론적 기초 제공
  2. 학제간 교량: 제어 이론, 정보 이론, 신경과학 연결
  3. 방법론 혁신: AIT의 시스템 이론 적용 가능성 시연
  4. 향후 연구: 관련 분야의 후속 연구를 위한 기초 마련

적용 시나리오

  1. 이론적 분석: 규제 시스템의 이론적 분석 및 이해에 적합
  2. 시스템 진단: 제어 시스템이 적절한 세계 모델을 포함하는지 평가
  3. 신경과학 연구: 뇌의 예측 기능 연구를 위한 정량적 프레임워크 제공
  4. 인공지능: 세계 모델을 가진 지능형 시스템 설계에 지침 제공

참고문헌

논문은 65개의 중요 문헌을 인용하며, 주요 내용은:

  1. Conant & Ashby (1970): "Every good regulator of a system must be a model of that system"
  2. Francis & Wonham (1975, 1976): 내부 모델 원리의 원본 연구
  3. Li & Vitányi (2019): Kolmogorov 복잡도의 권위 있는 교과서
  4. Solomonoff (1964): 알고리즘 확률 이론의 기초 연구
  5. Grünwald (2007): 최소 기술 길이 원리
  6. Friston: 자유 에너지 원리 관련 연구
  7. Ruffini: 저자의 알고리즘 에이전트 이론 선행 연구

종합 평가: 이는 이론적으로 매우 엄격하고 심오한 논문으로, 알고리즘 정보 이론을 제어 이론에 성공적으로 도입하여 고전적 규제자 정리에 새로운 관점을 제공합니다. 실용성 측면에서 도전 과제가 있지만, 이론적 기여와 학제간 가치로 인해 관련 분야의 중요한 연구가 됩니다.