Minimum description length

rdf:langString 最小描述長度

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