알고리즘 확률

알고리즘 정보 이론에서, 솔로몬오프 확률이라고도 알려진 알고리즘 확률은 주어진 관찰에 사전 확률을 할당하는 수학적인 방법이다. 그것은 1960년대에 레이 솔로몬오프에 의해 발명되었다.^[1] 귀납 추론 이론과 알고리즘 분석을 사용한다. 솔로몬노프는 그의 일반 귀납 추론 이론에서 이 공식에^[which?] 의해^{[clarification needed]} 얻은 선행, 즉^{[example needed][further explanation needed]} 예측을 위한 베이지스의 법칙을 사용한다.^[2]

사용되는 수학적 형식주의에서 관측치는 유한 이항 문자열의 형태를 가지며, 보편적 선행은 유한 이항 문자열^{[citation needed]} 집합에 대한 확률분포다. 이전은 Turing-computability 의미에서 보편적이다. 즉, 어떤 문자열도 0 확률을 가지고 있지 않다. 계산은 불가능하지만 대략적으로 추정할 수 있다.^[3]

개요

알고리즘적 확률은 다음과 같은 질문을 다룬다:^{[citation needed]} 우리가 이해하고 싶은 어떤 현상에 대한 데이터의 본문을 감안할 때, 가능한 모든 가설들 중에서 그것이 어떻게 발생했는지에 대한 가장 개연성이 높은 가설을 어떻게 선택할 수 있는가, 그리고 어떻게 다른 가설을 평가할 수 있는가? 우리는 어떻게 미래의 데이터를 예측할 수 있으며 어떻게 그 예측이 올바른 예측일 가능성을 측정할 수 있는가?

솔로몬노프의 알고리즘 확률에 대한 4가지 주요 영감을 다음과 같이 표현했다. 오캄의 면도기, 에피쿠로스의 복수 설명 원리, 현대 컴퓨팅 이론(예: 범용 튜링 기계의 사용), 베이즈의 예측 규칙.^[4]

오캄의 면도기와 에피쿠로스의 원리는 본질적으로 보편 이전의 서로 다른 두 가지 비수학적 근사치들이다.^{[citation needed]}

• 오캄의 면도기: 관찰된 현상과 일치하는 이론 중에서 가장 단순한 이론을 선택해야 한다.^[5]

• 에피쿠로스의 다중 설명 원리: 둘 이상의 이론이 관찰과 일치한다면, 그러한 모든 이론을 유지하라.^[6]

유니버설 선행의 중심에는 유니버설 튜링 기계와 같은 컴퓨터의 추상적인 모델이 있다.^[7] 튜링-완전인 한, 즉 모든 유한 이진 문자열은 추상적인 컴퓨터에서 그것을 계산할 적어도 하나의 프로그램을 가지고 있다.

추상 컴퓨터는 "단순한 설명"^{[citation needed]}이라는 문구에 정확한 의미를 부여하기 위해 사용된다. 사용되는 형식주의에서 설명이나 현상 이론은 추상적인 컴퓨터에서 실행될 때 관찰 문자열을 생성하는 컴퓨터 프로그램이다.^{[citation needed]} 간단한 설명은 짧은 컴퓨터 프로그램이다. 복잡한 설명은 긴 컴퓨터 프로그램이다.^{[citation needed]} 간단한 설명이 더 가능성이 높기 때문에 높은 확률의 관찰 문자열은 짧은 컴퓨터 프로그램 또는 약간 긴 많은 수의 컴퓨터 프로그램에 의해 생성된다. 낮은 확률의 관찰 문자열은 긴 컴퓨터 프로그램에^{[citation needed]} 의해서만 생성될 수 있는 문자열이다.

이러한 아이디어는 특정^{[example needed]} 관측치에 대한 사전 확률 분포를 구성하는 데 사용되는 확률과 구체화할 수 있다.^{[citation needed]} 솔로몬노프가 이것을 선행으로 발명한 주된 이유는 실제 선행자를 알 수 없을 때 베이지스의 지배에서 사용될 수 있기 때문에 불확실성 하에서의 예측이 가능하기 때문이다.^{[citation needed]} 그것은 관찰의 가장 가능성이 높은 연속성을 예측하고, 이 연속성이 얼마나 지속될 것인지에 대한 측정치를 제공한다.^{[citation needed]}

관측치(및 그 확장)의 보편적 확률은 비교할 수 없지만, 컴퓨터 알고리즘이 있는데, 이 알고리즘은 더 길고 긴 시간 동안 실행될 때 보편적 확률 분포에 수렴되는 일련의 근사치를 생성한다.^{[citation needed]}

솔로몬노프는 이 분포가 일정한 요인(불변도 정리라고 함)^[9] 내에서 기계적으로 불변함을 증명했다.

솔로몬노프는 1960년경 관련 침입 정리와 함께 알고리즘 확률의 개념을 발명하여 그것에 관한 보고서를 발표하였다:^[10] "귀납적 추론의 일반 이론에 관한 예비 보고서"^[11] 그는 1964년 "귀납 추론의 형식 이론", 제1부^[12], 제2부로 이러한 사상을 보다 완전하게 명확히 했다.^[13]

추가토론

솔로모노프는 임의로 생성된 입력 프로그램을 가진 보편적인 컴퓨터를 묘사했다. 그 프로그램은 아마도 무한한 출력을 산출한다. 범용 확률 분포는 임의 입력을 가진 모든 가능한 출력 문자열의 확률 분포다.^[14]

주어진 유한 출력 접두사 q의 알고리즘 확률은 q로 시작하는 것을 계산하는 프로그램의 확률을 합한 것이다. 짧은 프로그램을 가진 어떤 긴 개체는 높은 확률을 가진다.

알고리즘적 확률은 솔로몬노프의 귀납적 추론, 관찰에 기초한 예측 이론의 주성분이다. 기계 학습에 그것을 사용하려는 목적으로 발명되었다. 일련의 기호를 주어 다음으로는 어떤 것이 올 것인가? 솔로몬노프의 이론은, 비록 그 답은 무엇에 비길 수 없지만, 어떤 의미에서는 최적의 답을 제공한다. 예를 들어 칼 포퍼의 비공식 귀납 추론 이론과는 달리 솔로몬프의 이론은 수학적으로 엄격하다.^{[clarification needed]}

알고리즘 확률은 Kolmogorov 복잡성의 개념과 밀접하게 관련되어 있다. 콜모고로프의 복잡성에 대한 도입은 정보 이론과 무작위성의 문제들에 의해 동기부여된 반면 솔로몬노프는 다른 이유인 귀납적 추론을 위해 알고리즘적 복잡성을 도입했다. 베이스의 통치에서 각각의 실제 사전 확률을 대체할 수 있는 하나의 보편적 사전 확률은 솔로몬노프가 Kolmogorov 복잡성을 곁들여 발명했다.^[15]

솔로몬프의 헤아릴 수 없는 척도는 어떤 강력한 의미에서는 보편적이지만 계산 시간은 무한할 수 있다. 이 문제에 대처하는 한 가지 방법은 레오니드 레빈의 검색 알고리즘의 변형인데,^[16] 가능한 프로그램의 성공을 계산하는 데 드는 시간을 제한하고, 더 짧은 프로그램에는 더 많은 시간이 주어진다. 검색 공간을 제한하는 다른 방법으로는 훈련 순서가 있다.

주요인

• 레이 솔로모노프
• 안드레이 콜모고로프
• 레오니드 레빈

참고 항목

• 솔로몬프의 귀납 추론
• 알고리즘 정보 이론
• 베이시안 추론
• 귀납적 추론
• 귀납 확률
• 콜모고로프 복잡성
• 유니버설 튜링 기계
• 정보 기반 복잡성

참조

원천

• Li, M. 및 Vitany, P., Kolmogorov 복잡성과 그 적용에 대한 소개, 제3판, Springer Science and Business Media, N.Y., 2008., Springer Science and Business Media, 3판

추가 읽기

• Rathmanner, S, Hutter, M, Entropy 2011, 13, 1076-1136의 "유니버설 유도의 철학적 고찰": 솔로몬노프의 귀납적 추론 이론에 대한 매우 명확한 철학적, 수학적 분석.

외부 링크

• Scholarpedia에서의 알고리즘 확률
• 솔로몬오프 출판물