Minimum description length (MDL) is a model selection principle where the shortest description of the data is judged to be the best model. MDL methods learn through a data compression perspective and are sometimes described as mathematical applications of Occam's razor. The MDL principle can be extended to other forms of inductive inference and learning, for example to estimation and sequential prediction, without explicitly identifying a single model of the data. MDL has its origins mostly in information theory and has been further developed within the general fields of statistics, theoretical computer science and machine learning, and more narrowly computational learning theory. Historically, there are different, yet interrelated, usages of the definite noun phrase "the minimum description length principle" that vary in what is meant by description:
Within Jorma Rissanen's theory of learning, a central concept of information theory, models are statistical hypotheses and descriptions are defined as universal codes. Rissanen's 1978 pragmatic first attempt to automatically derive short descriptions, relates to the Bayesian Information Criterion (BIC). Within algorithmic information theory, where the description length of a data sequence is the length of the smallest program that outputs that data set. In this context, it is also known as 'idealized' MDL principle and it is closely related to Solomonoff's theory of inductive inference, which is that the best model of a data set is represented by its shortest self-extracting archive.
Overview Selecting the minimum length description of the available data as the best model observes the principle identified as Occam's razor. Prior to the advent of computer programming, generating such descriptions was the intellectual labor of scientific theorists. It was far less formal than it has become in the computer age. If two scientists had a theoretic disagreement, they rarely could formally apply Occam's razor to choose between their theories. They would have different data sets and possibly different descriptive languages. Nevertheless, science advanced as Occam's razor was an informal guide in deciding which model was best. With the advent of formal languages and computer programming Occam's razor was mathematically defined. Models of a given set of observations, encoded as bits of data, could be created in the form of computer programs that output that data. Occam's razor could then formally select the shortest program, measured in bits of this algorithmic information, as the best model. To avoid confusion, note that there is nothing in the MDL principle that implies the model must be produced by a machine. It can be entirely the product of humans. The MDL principle applies regardless of whether the description to be run on a computer is the product of humans, machines or any combination thereof. The MDL principle requires only that the shortest description, when executed, produce the original data set without error.
Two-Part codes The distinction in computer programs between programs and literal data applies to all formal descriptions and is sometimes referred to as "two parts" of a description. In statistical MDL learning, such a description is frequently called a two-part code.
MDL in machine learning MDL applies in machine learning when algorithms (machines) generate descriptions. Learning occurs when an algorithm generates a shorter description of the same data set. The theoretic minimum description length of a data set, called its Kolmogorov complexity, cannot, however, be computed. That is to say, even if by random chance an algorithm generates the shortest program of all that outputs the data set, an automated theorem prover cannot prove there is no shorter such program. Nevertheless, given two programs that output the dataset, the MDL principle selects the shorter of the two as embodying the best model.
Recent work on algorithmic MDL learning Recent machine MDL learning of algorithmic, as opposed to statistical, data models have received increasing attention with increasing availability of data, computation resources and theoretic advances. Approaches are informed by the burgeoning field of artificial general intelligence. Shortly before his death, Marvin Minsky came out strongly in favor of this line of research, saying:
It seems to me that the most important discovery since Gödel was the discovery by Chaitin, Solomonoff and Kolmogorov of the concept called Algorithmic Probability which is a fundamental new theory of how to make predictions given a collection of experiences and this is a beautiful theory, everybody should learn it, but it’s got one problem, that is, that you cannot actually calculate what this theory predicts because it is too hard, it requires an infinite amount of work. However, it should be possible to make practical approximations to the Chaitin, Kolmogorov, Solomonoff theory that would make better predictions than anything we have today. Everybody should learn all about that and spend the rest of their lives working on it.
Statistical MDL learning Any set of data can be represented by a string of symbols from a finite (say, binary) alphabet.
[The MDL Principle] is based on the following insight: any regularity in a given set of data can be used to compress the data, i.e. to describe it using fewer symbols than needed to describe the data literally. (Grünwald, 2004)
… excerpt ends here. Continue reading the full article.
