솔로몬프의 귀납 추론

이 글에는 여러 가지 문제가 있다. 이 문제를 개선하거나 대화 페이지에서 토의하십시오. (이러한 템플릿 메시지를 제거하는 방법 및 시기 알아보기) 이 글은 독자들에게 혼란스럽거나 불명확할 수 있다. 특히 이 글의 큰 표지는 전문용어와 (무소요!) 막연한 일반화로 채워져 있다. 기사에 대해 명확하게 설명할 수 있도록 도와주십시오. 토크 페이지에서 이에 대한 논의가 있을 수 있다. (2017년 6월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기) 이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "Solomonoff의 귀납 추론 이론" – 뉴스 · 신문 · 책 · 학자 · JSTOR (2017년 6월) (이 템플릿 메시지를 제거하는 방법과 시기 학습) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

솔로몬노프의 귀납 추론 이론은 만약 우주가 알고리즘에 의해 생성된다면, 데이터 집합으로 부호화된 그 우주의 관찰은 그 데이터 집합의 가장 작은 실행 가능한 아카이브에 의해 가장 잘 예측된다는 수학적 증거다. 유도를 위한 오캄의 면도기의^{[1][2][3][4][5]} 이러한 공식화는 확률 이론과 이론 컴퓨터 과학에 기초하여 레이 솔로몬오프에 의해 도입되었다.^[6][7][8] 본질적으로 솔로몬노프의 유도는 일련의 관측된 데이터를 주어진 계산 가능한 이론의 후확률을 도출한다. 이 후방 확률은 베이즈 규칙과 일부 보편적 선행, 즉 계산 가능한 이론에 긍정적인 확률을 할당하는 선행에서 도출된다.

기원

철학적

이 이론은 철학적 토대를 바탕으로 하며, 1960년경 레이 솔로몬노프에 의해 창시되었다.^[9] 오캄의 면도기와^{[1][2][3][4][5]} 복수 설명의 원리를 수학적으로 공식화한 것이다.^[10] 이전의 관측을 완벽하게 설명하는 계산 가능한 모든 이론은 다음 관측의 확률을 계산하는 데 사용되며, 더 짧은 계산 가능한 이론에 가중치가 부여된다. 마커스 허터의 보편적인 인공지능은 어떤 행동의 기대 가치를 계산하기 위해 이것을 기반으로 한다.

원리

솔로몬노프의 유도는 순수한 베이시안주의의 계산적 공식화라고 주장되어 왔다.^[8] To understand, recall that Bayesianism derives the posterior probability ${\displaystyle \mathbb {P} [T D]}$ of a theory ${\displaystyle T}$ given data ${\displaystyle D}$ by applying Bayes rule, which yields ${\displaystyle \mathbb{P}[TD]=\mathbb{P}[DT]\mathbb{P}[T]/(\mathbb{P}[DT]\mathbb{P}[T]+\sum _{A\ne T}\mathbb{P}[D}$${\displaystyle \mathbb {P} [T D]=\mathbb {P} [D T]\mathbb {P} [T]/(\mathbb {P} [D T]\mathbb {P} [T]+\sum _{A\neq T}\mathbb {P} [D A]\mathbb {P} [A])}$, where theories ${\displaystyle A}$ are alternatives to theory ${\displaystyle T}$. For this equation to make sense, the quantities ${\disp$$laystyle \mathbb {P} [D T]}$ and ${\displaystyle \mathbb {P} [D A]}$ must be well-defined for all theories ${\displaystyle T}$ and ${\displaystyle A}$. In other words, any theory must define a probability distribution over observable data ${\displaystyle D}$. Solomonoff's induction essentially boils do모든 확률 분포를 계산할 수 있어야 한다.

흥미롭게도, 계산 가능한 확률 분포의 집합은 모든 프로그램 집합의 하위 집합으로, 셀 수 있다. 마찬가지로 솔로몬노프가 고려한 관측 가능한 데이터 집합은 유한했다. 따라서 일반성을 상실하지 않는 한, 관측 가능한 데이터는 유한 비트 문자열이라고 생각할 수 있다. 결과적으로 솔로몬노프의 유도는 이산 확률 분포를 호출하는 것만으로 정의할 수 있다.

솔로몬노프의 유도는 단순히 확률 법칙에 순응함으로써 미래 데이터 $F{\displaystyle }$ ${\displaystyle F$에 대한 확률론적 예측을 할 수 있다. Namely, we have ${\displaystyle \mathbb {P} [F D]=\mathbb {E} _{T}[\mathbb {P} [F T,D]]=\sum _{T}\mathbb {P} [F T,D]\mathbb {P} [T D]}$. This quantity can be interpreted as the average predictions ${\displaystyle \mathbb$${P}$ 과거 데이터 $D{\displaystyle }$ ${\displaystyle D}$이$($가) 부여된 모든 $이론$ T$${\$displaystyle T}$$$중 [F T$,D]}$을(를) 후신신뢰 $P{\displaystyle \mathbb{}}$ ${\displaystyle [TD}$ ${\displaystyle ]}${\$displaystyle \mathb {P} [TD]}$에 의해 가중치가 부여되었다$.$

수학적

"레이저"의 증명은 계수 가능한 집합에 걸쳐 확률 분포의 알려진 수학적 특성에 기초한다. 이러한 속성은 모든 프로그램의 무한 집합이 폄하할 수 없는 집합이기 때문에 관련성이 있다. 모든 프로그램의 확률의 합 S는 (확률의 정의에 따라) 정확히 1과 같아야 하기 때문에 모든 프로그램의 무한 집합을 열거할 때 확률은 대략적으로 감소해야 한다. 그렇지 않으면 S는 한 개보다 절대적으로 클 것이다. 좀 더 정확히 말하면, 모든 $ϵ{\displaystyle }$ ${\displaystyle \epsilon$} >$$ 0에 대해, l보다 긴 모든 프로그램의 확률은 최대 $ϵ{\displaystyle }${\$displaystyle \epsilon$}. 그러나, 매우$$긴 프로그램이 매우 높은 확률을 가지는 것을 배제하지는 않는다.

이 이론의 기본 요소는 알고리즘 확률과 콜모고로프 복잡성의 개념이다. 계산 가능한 시퀀스 x의 어떤 접두사 p의 보편적 사전 확률은 p로 시작하는 것을 계산하는 모든 프로그램(범용 컴퓨터의 경우)의 확률을 합한 것이다. x를 샘플링하는 일부 p와 계산 가능하지만 알려지지 않은 확률 분포를 주어진다면, 보편적 사전과 베이지스의 정리를 사용하여 다음 값을 예측할 수 있다. x의 일부를 최적의 패션으로 아직 보이지 않는 부분들

수학적 보증

솔로몬노프의 완성도

솔로몬노프의 유도의 주목할 만한 성질은 그 완전성이다. 본질적으로 완전성 정리는 솔로몬노프의 유도에 근거한 예측에 의해 이루어지는 예상 누적 오류들이 (stochastic) 데이터 생성 과정의 콜모고로프 복잡성에 의해 상경된다는 것을 보장한다. 오류는 Kullback-Leibler 차이 또는 유도 예측과 (stopchastic) 데이터 생성 프로세스에 의해 할당된 확률 사이의 차이의 제곱을 사용하여 측정할 수 있다.

솔로몬노프의 불손함

불행히도 솔로모노프는 솔로모노프의 유도가 평판이 좋지 않다는 것도 증명했다. 사실, 그는 계산성과 완전성은 상호 배타적이라는 것을 보여주었다: 어떤 완전한 이론도 논박할 수 없는 것이어야 한다. 이것의 증거는 인덕션과 환경 사이의 게임에서 도출된다. 본질적으로 계산 가능한 유도는 계산 가능한 유도의 예측을 부정하는 계산 가능한 환경을 선택함으로써 계산 가능한 환경에 의해 속일 수 있다. 이 사실은 무상급식을 하지 않는 정리의 한 예라고 볼 수 있다.

최신 애플리케이션

인공지능

솔로몬노프의 귀납적 추론은 계산이 불가능하지만, 몇몇 AIXI에서 파생된 알고리즘은 그것을 현대적인 컴퓨터에서 실행시키기 위해 그것을 근사하게 한다. 계산력이 더 많이 주어질수록 그들의 예측은 귀납 추론의 예측에 가깝다(그들의 수학적인 한계는 솔로몬노프의 귀납 추론이다).^[11][12][13]

귀납 추론의 또 다른 방향은 E에 근거한다. 마크 골드의 학습 모델은 1967년부터 한계에 달했고 그 이후 점점 더 많은 학습 모델이 발전했다.^[14] 일반적인 시나리오는 다음과 같다: 계산 가능한 기능의 클래스 S에 따라, 형식(f(0),f(1), ...,f(n)의 입력에 대해 가설을 출력하는 학습자(즉, 재귀적 기능)가 있다(모든 계산 가능한 기능의 허용 가능한 번호 지정에 대해 이전에 합의된 인덱스 e; 인덱스된 함수는 동의가 필요할 수 있다).주어진 f) 값으로 텐트를 치다. 학습자 M은 거의 모든 가설이 동일한 지수 e일 경우 함수 f를 학습한다. M은 함수 f를 생성한다. M은 함수 S를 학습한다. 기본적인 결과는 모든 계산 가능한 함수의 클래스 REC는 학습할 수 없는 반면, 함수의 재귀적으로 열거된 모든 클래스는 학습할 수 있다는 것이다.^{[citation needed]} 많은 관련 모델들이 고려되었고 또한 긍정적인 데이터로부터 재귀적으로 열거할 수 있는 집합의 수업 학습은 1967년 골드 선구자 논문에서 계속 연구된 주제다. 골드 접근법의 광범위한 확장은 슈미두버의 Kolmogorov 복잡성 일반화 이론에 의해 개발되는데,^[15] 이것은 일종의 초복구 알고리즘이다.

튜링 머신

이 절은 출처를 인용하지 않는다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 섹션을 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. (2017년 6월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

세 번째 수학적으로 기반한 귀납 추론 방향은 오토마타 이론과 연산 이론을 이용한다. 이러한 맥락에서 귀납 추론의 과정은 귀납 튜링 기계(Burgin, 2005년)라고 불리는 추상적인 자동화에 의해 수행된다. 귀납 튜링 기계는 현대 컴퓨터와 컴퓨터 네트워크에 더 나은 모델을 제공하고 알고리즘의 정의에서 모든 조건을 충족시키기 때문에 초복구 알고리즘의 중요한 클래스를 형성하는 컴퓨터 과학의 발전의 다음 단계를 나타낸다(Burgin, 2001). 즉, 각 유도 튜링 기계는 초기 상태가 주어졌을 때, 잘 정의된 일련의 연속 상태를 통해 작업을 완료하기 위한 명확한 지시 목록이 진행되어 결국 최종 상태로 종료되는 효과적인 방법의 일종이다. 귀납 튜링 기계와 튜링 기계 사이의 차이점은 튜링 기계가 멈추어야 하는 반면, 어떤 경우에는 귀납 튜링 기계가 멈추지 않고 이것을 할 수 있다는 것이다. 스테판 클레네는 이름 계산 절차나 알고리즘(Kleene 1952:137)에 의해 멈추지 않고 영원히 실행될 수 있는 절차를 불렀다. 클렌은 또한 그러한 알고리즘이 결국 "어떤 물체"를 표시해야 한다고 요구했다(Kleene 1952:137). 유한한 수의 스텝 후에 결과가 나타나기 때문에 이 조건은 유도 튜링 기계에 의해 만족되지만, 유도 튜링 기계는 항상 결과를 어느 단계에서 얻었는지 알려주지 않는다.

간단한 유도 튜링 기계는 다른 계산 모델과 동등하다. 보다 진보된 귀납 튜링 기계는 훨씬 더 강력하다. 부분 재귀 기능, 시행착오 술어, 일반 튜링 머신, 간단한 유도 튜링 머신 등을 제한하는 것이 계산의 등가 모델임을 증명한다(Burgin, 2005). 그러나 간단한 귀납 튜링 기계와 일반 튜링 기계는 물리적 기계에 철저히 바탕을 두고 있는 컴퓨팅 오토마타의 직접 구조를 제공한다. 이와는 대조적으로 시행착오 술어, 재귀함수를 제한하고 부분 재귀함수를 제한하는 것은 기호의 구문 체계를 조작에 대한 형식 규칙을 가지고 있다. 단순 귀납 튜링 기계와 일반 튜링 기계는 튜링 기계가 부분 재귀 기능 및 람다-미적분과 관련이 있기 때문에 부분 재귀 기능 및 시행착오 술어를 제한하는 것과 관련이 있다.

단순한 유도 튜링 기계만이 튜링 기계와 동일한 구조(그러나 출력 모드의 다른 기능 의미론)를 가지고 있다는 점에 유의하십시오. 다른 종류의 귀납 튜링 기계는 구조화된 메모리와 더 강력한 지시로 인해 본질적으로 더 발전된 구조를 가지고 있다. 추론과 학습에 대한 그들의 활용은 더 높은 효율성을 달성할 수 있고 사람들의 학습을 더 잘 반영한다(Burgin and Klinger, 2004).

일부 연구자들은 유도 튜링 기계의 계산을 중단 없는 계산이나 무한 시간 계산과 혼동한다. 첫째, 유도 튜링 기계의 일부 계산이 중단된다. 기존의 튜링 기계의 경우와 같이, 어떤 정지 연산들은 결과를 주는 반면, 다른 것들은 그렇지 않다. 둘째, 유도 튜링 기계의 정지하지 않는 연산은 결과를 제공하는 반면, 다른 연산은 결과를 제공하지 않는다. 유도 튜링 기계의 규칙은 계산(정지 또는 정지하지 않음)이 결과를 제공하는 시기를 결정한다. 즉, 유도 튜링 기계는 때때로 출력을 생성하며 이 출력이 변화를 멈추면 계산의 결과로 간주된다. 일부 논문에서 이 규칙에 대한 설명이 부정확하다는 것을 알 필요가 있다. 예를 들어, 데이비스(2006: 128)는 "정확한 출력이 생산되고 나면 후속 출력이 단순히 이 정확한 결과를 반복할 것"으로 결과를 얻을 때 규칙을 공식화한다. 셋째, 널리 퍼진 오해와 대조적으로 귀납 튜링 기계는 무한정 및 무한정 시간 계산과는 대조적으로 항상 유한한 수 단계(유한 시간) 후에 결과를 준다. 기존의 튜링 기계와 간단한 유도 튜링 기계 사이에는 두 가지 주요한 차이점이 있다. 첫 번째 구분은 단순한 귀납 튜링 기계도 기존의 튜링 기계보다 훨씬 더 많은 일을 할 수 있다는 것이다. 두 번째 구분은 기존의 튜링 기계는 결과를 얻을 때 항상 (정지하거나 최종 상태로 와서) 알려 주는 반면, 어떤 경우에는 간단한 유도 튜링 기계는 결과에 도달하는 것을 알려 주는 반면, 다른 경우에는 (기존 튜링 기계가 무력한 경우에는) 알려주지 않는 것이다. 사람들은 결과가 나오면 컴퓨터 자체가 항상 (정지하거나 다른 수단으로) 알려준다고 착각한다. 이와 대조적으로, 사용자 자신은 많은 경우에 계산된 결과가 필요한 것인지 아니면 계속 계산을 해야 하는지를 결정해야 한다. 실제로 워드프로세서나 스프레드시트와 같은 일상적인 데스크톱 컴퓨터 애플리케이션은 대부분의 시간을 이벤트 루프에서 기다리며, 사용자가 그렇게 하도록 지시할 때까지 종료되지 않는다.

진화 귀납 튜링 기계

유도 추론에 대한 진화적 접근법은 진화 유도 튜링 기계라고 불리는 또 다른 종류의 자동화에 의해 달성된다(Burgin and Eberbach, 2009; 2012). 진화 귀납 튜링 기계는 각각 X[t]세대에 작용하는 귀납 튜링 기계 A[t]의 E = {A[t]; t = 1, 2, 3, ...} 시퀀스로서 A[t]의 알파벳 A[t]로 코딩된다. 추론 조건을 만족하는 '인구' Z를 구축하는 것이 목표다. E의 성분, 즉 레벨 오토마톤이라 불리는 자동 A[t]는 변동 연산자 v와 선택 연산자 s를 적용하여 모집단의 입력 세대 X[i]와 함께 작동하는 1단계 진화 알고리즘을 나타낸다. 1세대 X[0]는 E에 입력으로 제공되며, 1세대 X[1]를 전송 출력으로 생성/생산하는 자동 A[2]에 의해 처리된다. 모든 t = 1, 2, 3, ...에 대해 자동 A[t]는 A[t - 1]로부터 입력으로 X[t - 1]세대를 받은 다음 변동 연산자 v와 선택 연산자 s를 적용하여 X[i + 1]세대를 생성하여 A[t + 1]로 보내 진화를 계속한다.

참고 항목

• 알고리즘 정보 이론
• 베이시안 추론
• 제한 언어 식별
• 귀납적 추론
• 귀납 확률
• 밀의 방법
• 최소 설명 길이
• 최소 메시지 길이
• 철학적 관점은 다음과 같다: 유도의 문제와 유도의 새로운 수수께끼

참조

원천

• Angluin, Dana; Smith, Carl H. (Sep 1983). "Inductive Inference: Theory and Methods". Computing Surveys. 15 (3): 237–269. doi:10.1145/356914.356918. S2CID 3209224.
• Burgin, M. (2005) 초복구 알고리즘, 컴퓨터 과학의 모노그래프, 스프링거. ISBN 0-387-95569-0
• Burgin, M, "기술이 무엇을 할 수 있는지 어떻게 아는가", ACM의 통신, v. 44, 2001, 페이지 82–88.
• Burgin, M.; Eberbach, E, "Universality for Turing Machine, Involidative Turing Machine and Evolutional Algorithm", Uniforma Informaticae, v. 91, no., 2009, 53–77.
• Burgin, M.; Eberbach, "진화 계산의 기초에 관하여: 인공 면역 시스템과 자연 컴퓨팅에 관한 연구 핸드북의 진화적 자동 접근법: Complex Adaptive Technologies(Hongwei Mo, Ed.), IGI Global, Hershey, 2009, 342–360 적용.
• Burgin, M.; Eberbach, E, "진화 오토마타: 표현력과 진화 연산 융합" 컴퓨터 저널, v. 55, No. 9, 2012, 페이지 1023–1029.
• 버긴, M.; 클링거, A. 기계 학습, 이론 컴퓨터 과학의 경험, 세대 및 한계, v. 317, No. 1/3, 2004, 페이지 71–91
• 데이비스, 마틴(2006) "교회-튜링 논문: 합의 및 반대]." Procedures, Computability in European 2006. 컴퓨터 과학 강의 노트, 3988 페이지 125–132.
• Gasarch, W.; Smith, C. H. (1997) "질문에 중점을 둔 귀납 추론에 대한 조사" 복잡성, 논리 및 재귀 이론, 강의 노트(순수 및 응용) 수학, 187, 데커, 뉴욕 페이지 225–260.
• 헤이, 닉 "Universal Semimeasures: 소개," 2007년 2월 오클랜드 대학교 CDMTCS 연구 보고서 시리즈.
• Jain, Sanjay; Osherson, Daniel; Royer, James; Sharma, Arun, Systems that Learning: A Integration to Learning 이론 (제2판), MIT Press, 1999.
• Kleene, Stephen C. (1952), Introduction to Metamathematics (First ed.), Amsterdam: North-Holland.
• Li Ming; Vitany, Paul, Colmogorov 복잡성과 그것의 적용에 대한 소개, 제2판, Springer Verlag, 1997.
• Osherson, Daniel; Stob, Michael; Weinstein, Scott, Systems That Tearn, A Learning, A Learning 이론 소개, MIT Press, 1986.
• Solomonoff, Ray J. (1999). "Two Kinds of Probabilistic Induction" (PDF). The Computer Journal. 42 (4): 256. CiteSeerX 10.1.1.68.8941. doi:10.1093/comjnl/42.4.256.
• Solomonoff, Ray (March 1964). "A Formal Theory of Inductive Inference Part I" (PDF). Information and Control. 7 (1): 1–22. doi:10.1016/S0019-9958(64)90223-2.
• Solomonoff, Ray (June 1964). "A Formal Theory of Inductive Inference Part II" (PDF). Information and Control. 7 (2): 224–254. doi:10.1016/S0019-9958(64)90131-7.

외부 링크

• 알고리즘 확률 – Scholarpedia