算法概率

在算法信息理論中，算法概率，也被稱為所羅門諾夫概率，是一種為給定觀察分配先驗概率的數學方法。它是由RaySolomonoff在20世紀60年代發明的。它被用于歸納推理理論和算法的分析中。在他的歸納推理的一般理論中，所羅門諾夫將該方法與貝葉斯規則一起使用，以獲得對算法未來輸出的預測概率。在所使用的數學形式中，觀察結果具有有限二進制字符串的形式，被視為圖靈機的輸出，而通用先驗是由程序（即通用圖靈機的輸入）的概率分布計算出的有限二進制字符串集合的概率分布。在圖靈可計算性的意義上，該先驗是普遍的，也就是說，沒有一個字符串的概率為零。它是不可計算的，但它可以被近似計算。

算法概率的概述

算法概率是所羅門諾夫的歸納推理理論的主要成分，即基于觀察的預測理論；發明它的目的是將其用于機器學習；給定一個符號序列，接下來會是哪一個？所羅門諾夫的理論提供了一個在某種意義上是最優的答案，盡管它是不可計算的。與卡爾-波普爾的非正式歸納推理理論不同，所羅門諾夫的理論在數學上是嚴謹的。所羅門諾夫的算法概率的四個主要靈感是。奧卡姆剃刀、伊壁鳩魯的多重解釋原則、現代計算理論（例如使用通用圖靈機）和貝葉斯的預測規則。奧卡姆剃刀和伊壁鳩魯原則本質上是對普遍先驗的兩種不同的非數學近似。奧卡姆剃刀：在與觀察到的現象相一致的理論中，應該選擇最簡單的理論。伊壁鳩魯的多重解釋原則：如果有一個以上的理論與觀察結果相一致，就保留所有這些理論。普遍先驗的核心是計算機的抽象模型，如通用圖靈機。任何抽象計算機都可以，只要它是圖靈完備的，也就是說，每個可計算的函數至少有一個程序可以在抽象計算機上計算其應用。抽象計算機被用來賦予簡單解釋這一短語的精確含義。在所使用的形式主義中，解釋或現象的理論，是在抽象計算機上運行時產生觀察字符串的計算機程序。每個計算機程序都被分配了一個與它的長度相對應的權重。普遍概率分布是隨機輸入的所有可能的輸出串上的概率分布，為每個有限的輸出前綴q分配計算以q開始的東西的程序的概率之和。一個復雜的解釋是一個長的計算機程序。簡單的解釋更有可能，所以一個高概率的觀察串是由一個短的計算機程序產生的，也可能是由大量稍長的計算機程序產生的。低概率的觀察串是一個只能由長的計算機程序產生的觀察串。算法概率與Kolmogorov復雜性的概念密切相關。科爾莫戈羅夫引入復雜性的動機是信息論和隨機性中的問題，而所羅門諾夫引入算法復雜性的原因則不同：歸納推理。

所羅門諾夫發明了一個可以替代貝葉斯規則中每個實際先驗概率的單一通用先驗概率，并將科爾莫戈羅夫復雜性作為一個副產品。它預測了該觀察最可能的延續，并提供了這種延續的可能性的衡量標準。Solomonoff的可列舉措施在某種強大的意義上是普遍的，但計算時間可能是無限的。處理這個問題的一種方法是列昂尼德-列文的搜索算法的變種，它限制了計算可能程序的成功率的時間，較短的程序會得到更多的時間。當運行的時間越來越長時，它將產生一連串的近似值，這些近似值將收斂于普遍的概率分布。處理這個問題的其他方法包括通過包括訓練序列來限制搜索空間。Solomonoff證明這種分布在一個常數范圍內是機器不變的（稱為不變性定理）