Databases Reference
In-Depth Information
10
9
8
7
6
5
4
3
2
1
1
2
3
F I GU R E 2 . 7
An illustration of the minimum description length (MDL) principle.
satisfying theoretically than the notion of entropy when compressing sequences, in practice it
is not yet as helpful. However, given the active interest in these ideas it is quite possible that
they will result in more practical applications.
2.6 Minimum Description Length Principle
One of the more practical offshoots of Kolmogorov complexity is the minimum description
length (MDL) principle. The first discoverer of Kolmogorov complexity, Ray Solomonoff,
viewed the concept of a program that would generate a sequence as a way of modeling the
data. Independent from Solomonoff but inspired nonetheless by the ideas of Kolmogorov
complexity, Jorma Risannen in 1978 [
10
] developed the modeling approach commonly known
as MDL.
Let
M
j
be a model from a set of models
that attempt to characterize the structure in a
sequence
x
.Let
D
M
j
be the number of bits required to describe the model
M
j
. For example,
if the set of models
M
can be represented by a (possibly variable) number of coefficients,
then the description of
M
j
would include the number of coefficients and the value of each
coefficient. Let
R
M
j
(
M
be the number of bits required to represent
x
with respect to the model
M
j
. The minimum description length would be given by
x
)
