Minimum message length


Minimum message length

Minimum message length (MML) is a formal information theory restatement of Occam's Razor: even when models are not equal in goodness of fit accuracy to the observed data, the one generating the shortest overall message is more likely to be correct (where the message consists of a statement of the model, followed by a statement of data encoded concisely using that model). MML was invented by Chris Wallace, first appearing in the seminal (Wallace and Boulton, 1968).

MML is intended not just as a theoretical construct, but as a technique that may be deployed in practice. It differs from the related concept of Kolmogorov complexity in that it does not require use of a Turing-complete language to model data. The relation between Strict MML (SMML) and Kolmogorov complexity is outlined in Wallace and Dowe (1999a). Further, a variety of mathematical approximations to "Strict" MML can be used — see, e.g., Chapters 4 and 5 of Wallace (posthumous) 2005.

Contents

Definition

Shannon's A Mathematical Theory of Communication (1949) states that in an optimal code, the message length (in binary) of an event E, \operatorname{length}(E), where E has probability P(E), is given by \operatorname{length}(E) = -\log_2(P(E)).

Bayes's theorem states that the probability of a hypothesis (H) given evidence (E) is proportional to P(E | H)P(H), which is just P(H \and E). We want the model (hypothesis) with the highest such probability. Therefore, we want the model which generates the shortest (two-part) encoding of the data. Since \operatorname{length}(H \and E) = -\log_2(P(H \and E)), the most probable model will have the shortest such message. The message breaks into two parts: -\log_2(P(H \and E)) = -\log_2(P(H)) + -\log_2(P(E|H)). The first is the length of the model, and the second is the length of the data, given the model.

MML naturally and precisely trades model complexity for goodness of fit. A more complicated model takes longer to state (longer first part) but probably fits the data better (shorter second part). So, an MML metric won't choose a complicated model unless that model pays for itself.

Continuous-valued parameters

One reason why a model might be longer would be simply because its various parameters are stated to greater precision, thus requiring transmission of more digits. Much of the power of MML derives from its handling of how accurately to state parameters in a model, and a variety of approximations that make this feasible in practice. This allows it to usefully compare, say, a model with many parameters imprecisely stated against a model with fewer parameters more accurately stated.

Key features of MML

  • MML can be used to compare models of different structure. For example, its earliest application was in finding mixture models with the optimal number of classes. Adding extra classes to a mixture model will always allow the data to be fitted to greater accuracy, but according to MML this must be weighed against the extra bits required to encode the parameters defining those classes.
  • MML is a method of Bayesian model comparison. It gives every model a score.
  • MML is scale-invariant and statistically invariant. Unlike many Bayesian selection methods, MML doesn't care if you change from measuring length to volume or from Cartesian co-ordinates to polar co-ordinates.
  • MML is statistically consistent. For problems like the Neyman-Scott (1948) problem or factor analysis where the amount of data per parameter is bounded above, MML can estimate all parameters with statistical consistency.
  • MML accounts for the precision of measurement. It uses the Fisher information (in the Wallace-Freeman 1987 approximation, or other hyper-volumes in other approximations) to optimally discretize continuous parameters. Therefore the posterior is always a probability, not a probability density.
  • MML has been in use since 1968. MML coding schemes have been developed for several distributions, and many kinds of machine learners including unsupervised classification, decision trees and graphs, DNA sequences, Bayesian networks, neural networks (one-layer only so far), image compression, image and function segmentation, etc.

See also

External links

Models for machine learning and data mining in functional programming, J. Functional Programming, 15(1), pp15-32, Jan. 2005 (MML, FP, and Haskell code).

[See also Comley and Dowe (2003), .pdf. Comley & Dowe (2003, 2005) are the first two papers on MML Bayesian nets using both discrete and continuous valued parameters.]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Minimum description length — The minimum description length (MDL) principle is a formalization of Occam s Razor in which the best hypothesis for a given set of data is the one that leads to the best compression of the data. MDL was introduced by Jorma Rissanen in 1978. It is …   Wikipedia

  • Message switching — In telecommunications, message switching was the precursor of packet switching, where messages were routed in their entirety, one hop at a time. It was first introduced by Leonard Kleinrock in 1961. Message switching systems are nowadays mostly… …   Wikipedia

  • Occam's razor — For the aerial theatre company, see Ockham s Razor Theatre Company. It is possible to describe the other planets in the solar system as revolving around the Earth, but that explanation is unnecessarily complex compared to the modern consensus… …   Wikipedia

  • Kolmogorov complexity — In algorithmic information theory (a subfield of computer science), the Kolmogorov complexity of an object, such as a piece of text, is a measure of the computational resources needed to specify the object. It is named after Soviet Russian… …   Wikipedia

  • Mixture model — See also: Mixture distribution In statistics, a mixture model is a probabilistic model for representing the presence of sub populations within an overall population, without requiring that an observed data set should identify the sub population… …   Wikipedia

  • Chris Wallace (computer scientist) — Professor Christopher Stewart Wallace (26 October 1933 7 August 2004) was an Australian computer scientist (and physicist, who also contributed to a variety of other areas) notable for having devised: The minimum message length principle (Wallace …   Wikipedia

  • Nat (information) — Fundamental units of information bit (binary) nat (base e) ban (decimal) qubit (quantum) This box: view · …   Wikipedia

  • Bayesian network — A Bayesian network, Bayes network, belief network or directed acyclic graphical model is a probabilistic graphical model that represents a set of random variables and their conditional dependencies via a directed acyclic graph (DAG). For example …   Wikipedia

  • Алгоритмическая теория информации — Алгоритмическая теория информации  это область информатики, которая пытается уловить суть сложности, используя инструменты из теоретической информатики. Главная идея  это определить сложность (или описательную сложность, колмогоровскую… …   Википедия

  • Байесовская сеть доверия — Байесовская сеть (или Байесовская сеть доверия) это вероятностная модель, представляющая собой множество переменных и их вероятностных зависимостей. Например, байесовская сеть может быть использована для вычисления вероятности того, чем болен… …   Википедия