Minimum message length
|
|
Minimum message length (MML) is a formal information theory restatement of Occam's Razor: even when models are not equal in accuracy, 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.
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 allow use of a Turing-complete language to model data. Further, a variety of mathematical approximations to "Strict" MML can be used.
| Contents |
Definition
From Shannon's Mathematical Theory of Communication (1949) we know that in an optimal code, the message length of an event <math>E<math>, <math>Length(E)<math>, where <math>E<math> has probability <math>P(E)<math>, is given by <math>Length(E) = -\log_2(P(E))<math>.
From Bayes' theorem we know that the probability of a hypothesis (<math>H<math>) given evidence (<math>E<math>) is proportional to <math>P(E|H) P(H)<math>, which is just <math>P(H \and E)<math>. We want the model with the highest such probability. Therefore, we want the model which generates the shortest description of the data! Since <math>Length(H \and E) = -log_2(P(H \and E))<math>, the most probable model will have the shortest such message. The message breaks into two parts: <math>-log_2(P(H \and E)) = -log_2(P(H)) + -log_2(P(E|H))<math>. The first is the length of the model, and the second is the length of the data, given the model.
So what? 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. Unlike many Bayesian selection methods, MML doesn't care if you change from measuring length to volume.
- 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
- Minimum description length -- a would-be non-Bayesian alternative
- Kolmogorov complexity -- absolute complexity; MML is typically a computable approximation (see Wallace and Dowe (1999) (http://www3.oup.co.uk/computer_journal/hdb/Volume_42/Issue_04/pdf/420270.pdf) below for elaboration)
- Algorithmic information theory
External links
- Minimum Message Length (MML) (http://www.csse.monash.edu.au/~lloyd/tildeMML/), Lloyd Allison's moderately thorough MML introduction
- History of MML (http://www.csse.monash.edu.au/~lloyd/tildeMML/20031120e/),Chris Wallace (http://www.csse.monash.edu.au/~dld/CSWallacePublications/)'s last MML talk
- Searchable database of some of Chris Wallace's publications (http://www.csse.monash.edu.au/~lloyd/tildeImages/People/Wallace/)
- Minimum Message Length and Kolmogorov Complexity (http://www3.oup.co.uk/computer_journal/hdb/Volume_42/Issue_04/pdf/420270.pdf) (by C.S. Wallace (http://www.csse.monash.edu.au/~dld/CSWallacePublications/) and D.L. Dowe (http://www.csse.monash.edu.au/~dld), Computer Journal, Vol. 42, No. 4, 1999).
- Message Length as an Effective Ockham's Razor in Decision Tree Induction (http://www.ai.mit.edu/conferences/aistats2001/files/needham122.ps), by S. Needham and D. Dowe (http://www.csse.monash.edu.au/~dld), Proc. 8th International Workshop on AI and Statistics (http://www.ai.mit.edu/conferences/aistats2001) (2001), pp253-260 (http://www.csse.monash.edu.au/~dld/Publications/2001/Needham+Dowe2001.ref). (Shows how Ockham's razor (http://www.csse.monash.edu.au/~dld/Ockham.html) works fine when interpreted as MML (http://www.csse.monash.edu.au/~dld/MML.html).)
- P. Grunwald, M. A. Pitt and I. J. Myung (ed.),
Advances in Minimum Description Length: Theory and Applications (http://mitpress.mit.edu/catalog/item/default.asp?sid=4C100C6F-2255-40FF-A2ED-02FC49FEBE7C&ttype=2&tid=10478), M.I.T. Press (MIT Press), April 2005, ISBN (http://mitpress.mit.edu/catalog/item/default.asp?sid=4C100C6F-2255-40FF-A2ED-02FC49FEBE7C&ttype=2&tid=10478) 0-262-07262-9 (http://mitpress.mit.edu/catalog/item/default.asp?sid=4C100C6F-2255-40FF-A2ED-02FC49FEBE7C&ttype=2&tid=10478); and Chapter 11: J.W.Comley and D.L. Dowe (http://www.csse.monash.edu.au/~dld), Minimum Message Length, MDL and Generalised Bayesian Networks with Asymmetric Languages.
- MML researchers and links (http://www.csse.monash.edu.au/~dld/MML.html)
- MITECS (http://ai.ato.ms/MITECS/Entry/wallace): Chris Wallace (http://www.csse.monash.edu.au/~dld/CSWallacePublications/) wrote an entry on MML for MITECS. (Requires account)
- mikko.ps (http://www.cs.helsinki.fi/u/floreen/sem/mikko.ps): Short introductory slides by Mikko Koivisto in Helsinki]