Statistical Physics and the Fundamentals of Minimum Description Length and Minimum Message Length

The Table of Contents

Abstract

Preface

Introduction

Minimum Message Length

Minimum Description Length

The Grammar of Form

A Compression Engine

A New Paradigm

Conclusion

Summary

Notes

References

About the Author

Introduction

The monograph will address the ‘compressibility’ of a traditional random binary segmental string verses a ‘summing engine’ binary sequential string. The model used for both compression systems are the Minimum Message Length, MML, and the Minimum Description Length, MDL, with the result being a paradigm shift of both the Minimum Message Length and to the Minimum Description Length systems at the fundamental level.

Minimum Message Length, MML, was first developed by C. S. Wallace and D. M. Boulton (1968). The bases of Minimal Message Length is very similar to Minimum Description Length except the Minimum Message Length is a fully subject Bayesian model (Wikipedia, 2011: 1 &4).

Minimum Description Length, MDL, was first developed by J. Rissanen in 1978 (Rissanen, 1978). The bases of the Minimum Description Length is that regularity in a specific set of data can be used to compress the data into a sequence shorter than the original length of the originating sequence.

Minimum Message Length

Minimum Message Length [MML] was the early progenitor of Minimal Description Length [MML] and was first published by Wallace and Boulton in 1968. The primary difference between MML and MDL, the Minimum Description Length, is that the Minimum Message Length is a fully subjective Bayesian model in that it is of a ‘a prior’ distribution (Wikipedia, 2012:5-6).

In the MML model all the parameters are encoded in the first part of a two-part code so all the parameters are learned (Wikipedia, 2012: 5-6).

Minimum Description Length

Minimum Description Length [MDL] was developed in 1978 by Jorma Rissanen as a method by which the “best hypothesis for a given set of data is the one that leads to the best compression of the data” (Wikipedia, 2012. 1). Minimum Description Length has had to bypass two fundamentals of Kolmogorov Complexity in that Kolmogorov Complexity is incomputable and uses ‘what’ computer language is used (Wikipedia, 2012: 2). Minimum Description Length restricts the codes allowable so that it does become computable to find the shortest code length available and that the code being ‘reasonably’ efficient (Wikipedia, 2012: 2).

The Minimum Description Length Principle is as follows:

The best theory minimizes the bit sum of the length of the description of the theory and the length in bits of the data when encode by the help of the theory (Li and Vitany, 1997: 351). Minimum Description Length try’s to balance the regularity and randomness in the data using the best model; the one that uses regularity in the data to compress (Li and Vitanyi, 1997: 351)

[...]