最小描述長度 最小描述長度原則是將奧卡姆剃刀形式化後的一種結果其想法是在給予假說的集合的情況下能產生最多資料壓縮效果的那個假說是最好的它是在年由Jorma Rissanen英语Jorma Rissanen所引入的在資訊理論和計算機學習理論中最小描述長度原則是個重要觀念 任一資料集都可以由一有限譬如說二進位制的字母集內符號所成的字串來表示最小描述長度原則背後的基本想法是在任一給定的資料集內的任何規律性都可用來壓縮亦即在描述資料時與逐字逐句來描述資料的方式相比能使用比所需還少的符號Grünwald 見底下的鏈結既然我們希望選取到的假說能抓到資料中最多的規律於是我們則尋找壓縮效果最佳的假說 若要如此我們首先要決定一個用來壓縮資料的程式代碼最一般的方式是選一個具有圖靈完全特性的計算機程式語言我們接著以這個語言撰寫一個會輸出某筆資料的電腦程式於是這個程式則能代表此筆資料而能輸出此資料而又最短的程式其長度被稱為此項資料的柯氏複雜性這是Ray Solomonoff英语Ray Solomonoff的核心概念一個將歸納推論理想化後的理論 然而其想法在數學上並不提供一個實際的推論方法最重要的理由如下 柯氏複雜度在計算理論中是不可計算的不存在一個電腦程式能在給予任意序列的資料情況下輸出最短而又可以產生此筆資料的程式即使我們偶遇一個最短的程式一般情況下也無法確知它是最短的 柯氏複雜度與使用什麼電腦語言來描述程式有關使用什麼語言是可任意選擇的但一些額外的常數項會影響複雜度基於這個理由柯氏複雜度理論中傾向不理會常數項但實務上通常只有資料中的很小一部分總量是可得的如此則常數通常可以對於推論結果有很大的影響好的結果不能保證能適用於有限的資料 而最小描述長度原則則藉由以下方式來試圖補救上述問題 限制所能使用代碼的集合使得對於所允許的代碼而言尋找某筆資料最短的碼長變成可行可計算的 選擇一種代碼使得不論手上有什麼樣的資料此代碼在都是相當有效率的這點是有些獨特的exclusive這方面則有許多研究在進行中 比起程式在最小描述長度理論的領域中比較常用的是侯選假說模型或代碼允許使用的代碼集合則被稱為模型類別有些作者則模型類別指為模型這會令人混淆於是代碼描述及借助於這代碼的資料描述的加總是最小的那個代碼會被選取 最小描述長度的一個重要特性是它提供了一個避免過適現象的保護裝置這是因為它在假說複雜度和已知假說下的資料複雜度之間做了取捨要理解為什麼這是對的可以考慮以下的例子假設你拋擲一個銅板一千次且你觀察到了正反面的個數我們考慮兩種模式類別第一種是對每個結果以表正面及表反面的方式來編碼這代碼所代表的假說即為這銅板是公平根據這個編碼方式所得的代碼長度總是位元對於一個有偏向的銅板第二個模型類別則是所有有效率的代碼其代表的假說即為這個銅板是不公正的譬如我們觀察到個正面和個反面於是根據第二個模型中最佳碼的所求得的碼長應少於一千位元因為這理由一個天真的統計方法可能提出第二個假說應是對資料較好的解釋然而在一個最小描述長度策略中我們必須基於假說建造一個 單一碼我們不能只是用最好的那一個一個簡單的方式是使用兩部分的代碼我們先指定模型中哪一個假說擁有最佳的表現然後指定使用這個代碼的資料我們須要不少位元去指定哪一個代碼要使用所以基於第二個模型的總碼長將大於一千位元所以如果你服從最小描述長度策略其結論將是即使第二個模型類別的最佳資料可以更適應資料仍然沒有足夠的證據可以支持銅板是偏向的假說 最小描述長度核心是代碼長度函數和機率分佈之間的一對一且映成牽涉到的引理為克拉夫特不等式 對於任意機率分佈 P displaystyle P 去建造一代碼 C displaystyle C 其長度為 C  x  displaystyle Cx 等於  l o g  P  x  displaystyle logPx 是可行的這代碼最小化預期的碼長反過來說給予一個編碼 C displaystyle C 則可以建造一個機率分佈 P displaystyle P 保持同樣的結果在這裡忽略rounding issues換句話說搜尋一有效代碼被化簡化搜尋一個好的機率分佈反過來說亦如是