알고리즘 확률(Algorithmic probability)은 솔로모노프의 귀납적 추론 이론(Solomonoff's theory of inductive inference)으로도 알려져 있으며, 가능한 관측 수열에 확률을 할당하기 위한 형식적 체계이다. 이는 보편 튜링 기계(universal Turing machine)가 특정 이진 문자열을 생성할 확률에 대한 수학적 정의를 제공하며, 기계의 프로그램 길이에 기반한다. 이 이론은 1960년대 레이 솔로모노프(Ray Solomonoff)가 도입했고, 이후 레오니드 레빈(Leonid Levin) 등이 개선하여 알고리즘 정보 이론(algorithmic information theory)의 초석을 형성했으며, Artificial intelligence와 같은 분야에 영향을 미쳤다.
핵심 아이디어는 문자열의 확률이 최단 프로그램 길이의 2의 음의 거듭제곱에 비례한다는 것이며, 이 개념은 콜모고로프 복잡도(Kolmogorov complexity)로 알려져 있다. 이는 본질적으로 더 짧은 프로그램이 더 높은 확률을 받으므로 더 단순한 설명을 선호한다. 알고리즘 확률은 일반적인 경우 계산 불가능하지만, 예측 및 패턴 인식의 이론적 이상으로 작용하며, Machine learning 및 Deep learning과 같은 실용적 접근 방식과 자주 대조된다.
역사적 발전
레이 솔로모노프는 1960년 기술 보고서에서 알고리즘 확률을 처음 설명했고, 1964년 "귀납적 추론의 형식 이론(A Formal Theory of Inductive Inference)"이라는 제목의 획기적인 논문을 발표했다. 그의 연구는 모든 가능한 수열에 대한 보편적 사전 확률(universal prior)을 제공함으로써 귀납 문제를 해결하는 것을 목표로 했다. 1970년대에는 레오니드 레빈이 독립적으로 레빈 탐색(Levin's search)과 보편 분포(universal distribution)의 관련 개념을 정의하여 알고리즘 확률을 계산 복잡도 이론과 연결했다. 이후 1980년대와 1990년대에는 밍 리(Ming Li)와 폴 비타니(Paul Vitányi) 같은 연구자들이 이러한 아이디어를 알고리즘 정보 이론의 더 넓은 분야에 통합하여 콜모고로프 복잡도, 알고리즘 확률, 보편 귀납 간의 관계를 공식화한 포괄적인 저서를 출판했다.
형식적 정의
보편 튜링 기계 U에 대해, 이진 문자열 x의 알고리즘 확률은 x를 생성한 후 정지하는 모든 프로그램 p의 확률의 합으로 정의된다. 형식적으로, P_U(x) = Σ_{p: U(p)=x} 2^{-|p|}이며, 여기서 |p|는 프로그램 p의 비트 길이이다. 이 합은 모든 프로그램에 대한 총 확률이 크래프트 부등식(Kraft's inequality)에 의해 제한되므로 수렴한다. 어떤 프로그램도 다른 프로그램의 접두사가 아닌 접두사-자유(prefix-free) 버전은 합이 잘 정의되도록 보장하며 보편 사전 확률로 이어진다. 알고리즘 확률은 부등식 -log P_U(x) ≤ K(x) + O(1)에 의해 콜모고로프 복잡도 K(x)와 관련되며, 이는 낮은 복잡도를 가진 문자열이 높은 확률을 가짐을 의미한다.
오컴의 면도날과의 연결
알고리즘 확률은 더 단순한 설명이 더 정확할 가능성이 높다는 원칙인 오컴의 면도날(Occam's razor)에 대한 엄격한 수학적 정당성을 제공한다. 이 체계에서 단순성은 프로그램 길이로 측정되며, 더 짧은 프로그램은 지수적으로 더 높은 사전 확률이 할당된다. 이는 임의적 선택이 아니라 보편 튜링 기계의 속성과 사전 확률이 계산 가능하고 일관적이어야 한다는 요구에서 비롯된다. 이 이론은 관측된 데이터와 일치하는 모든 가설 중에서 가장 짧은 설명을 가진 가설이 가장 높은 확률을 가진다는 것을 의미하며, 이 원칙은 Machine learning 및 Large language model 훈련의 많은 실용적 알고리즘의 기초가 된다.
귀납적 추론에서의 역할
솔로모노프의 체계는 귀납적 추론을 모든 계산 가능한 가설에 대한 베이즈 업데이트(Bayesian updating)로 공식화한다. 관측된 데이터 수열이 주어지면 각 가설의 사후 확률은 사전 확률(알고리즘 확률)과 우도(likelihood)의 곱에 비례한다. 이는 데이터 생성 과정이 계산 가능하다면 확률 1로 실제 데이터 생성 과정에 수렴하는 보편적 예측 방법을 제공하며, 이 결과는 솔로모노프의 완전성 정리(Solomonoff's completeness theorem)로 알려져 있다. 그러나 이 방법은 무한히 많은 프로그램에 대한 합산을 요구하므로 계산적으로 다루기 어려워 직접 구현할 수 없다. 그럼에도 불구하고 실용적 예측 알고리즘을 평가하기 위한 이론적 기준으로 작용한다.
보편 탐색 및 레빈 탐색과의 관계
알고리즘 확률은 확률 순서대로 프로그램을 탐색하여 문제를 해결하는 방법인 레빈 탐색과 밀접하게 관련된다. 레빈 탐색은 보편 분포를 사용하여 높은 알고리즘 확률을 가진 프로그램을 우선시하며, 짧은 해결책이 있는 문제에 대해 거의 최적의 시간 복잡도를 달성한다. 이 연결은 알고리즘 확률을 계산 복잡도 이론과 연결하며, 보편 사전 확률이 인공 지능 시스템에서 효율적인 탐색을 안내할 수 있음을 보여준다. 이 개념은 Neural network 아키텍처 및 훈련 방법의 설계에 영향을 미쳤지만, Transformer (architecture) 모델과 같은 현대적 접근 방식은 명시적 알고리즘 확률보다 경험적 사전 확률에 의존한다.
인공 지능에서의 응용
알고리즘 확률은 대부분의 현대 AI 시스템에서 직접 사용되지는 않지만, 그 원칙은 이론적 기초를 형성했다. 예를 들어, 알고리즘 확률에서 파생된 최소 설명 길이(MDL) 원칙은 Machine learning의 모델 선택 및 정규화에 적용된다. Deep learning의 베이즈 추론은 종종 단순성을 근사하는 사전 확률을 통합하며, 이는 솔로모노프의 아이디어를 반영한다. Artificial intelligence 안전성 및 해석 가능성 연구는 때때로 더 단순한 모델을 주장하기 위해 알고리즘 확률을 참조한다. OpenAI 및 Google DeepMind 같은 회사는 이론적 작업에서 관련 개념을 탐구했지만, 실용적 구현은 명시적 프로그램 탐색보다 확률적 경사 하강법과 대규모 데이터에 의존한다.
한계 및 비판
알고리즘 확률은 몇 가지 근본적인 한계에 직면한다. 이는 계산 불가능하므로 모든 문자열에 대한 정확한 확률을 계산할 수 있는 알고리즘은 없다. 특정 보편 튜링 기계에 대한 의존성은 절대 확률에 영향을 미치는 가산 상수를 도입하지만, 상대적 순위는 상수까지 기계 독립적이다. 비판자들은 이 체계가 고정된 계산 모델을 가정하며 관찰자나 환경의 복잡성을 고려하지 않는다고 주장한다. 또한 사전 확률은 비계산 가능한 수열에 0의 확률을 할당하므로 계산 가능한 과정에 의해 생성되지 않을 수 있는 실제 데이터에 대한 적용 가능성을 제한한다. 이러한 문제로 인해 일부 연구자들은 실제로 더 다루기 쉬운 확률 과정 모델 및 경험적 베이즈 방법과 같은 대안적 체계를 개발하게 되었다.
현대 연구에 미치는 영향
한계에도 불구하고 알고리즘 확률은 Machine learning 및 인지 과학의 이론적 연구에 계속 영향을 미치고 있다. 이는 보편 귀납, 알고리즘 무작위성, Generative AI의 기초에 대한 연구에 영감을 주었다. MIT CSAIL 및 Stanford AI Lab 같은 기관의 연구자들은 알고리즘 확률과 신경망 일반화 사이의 연결을 연구했다. 이 개념은 또한 인공 일반 지능에 대한 논의에서 나타나며, 보편 학습 에이전트의 구성 요소로 제안된다. Large language model 해석 가능성에 대한 최근 연구는 다음 토큰 예측과 솔로모노프 귀납 사이의 유사점을 도출했지만, 실용적 메커니즘은 상당히 다르다.
같이 보기
- 콜모고로프 복잡도 (관련 개념, 제공된 목록에는 없지만 Machine learning 링크 사용)
- Artificial intelligence
- Deep learning
- Neural network
참고 문헌
- Solomonoff, R. J. (1964). "A Formal Theory of Inductive Inference." Information and Control, 7(1), 1-22.
- Li, M., & Vitányi, P. (2008). "An Introduction to Kolmogorov Complexity and Its Applications." Springer.
- Hutter, M. (2005). "Universal Artificial Intelligence: Sequential Decisions Based on Algorithmic Probability." Springer.