Editing Minimum description length (section)

==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 proving|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.