A tutorial introduction to the minimum description length principle

https://arxiv.org/abs/1603.05027 Recurrent Neural Network Regularization - https://arxiv.org/abs/1409.2329 Deep Speech 2: End-to-End Speech Recognition in English and Mandarin - https://arxiv.org/abs/1512.02595 Order Matters: Sequence to Sequence for Sets - https://arxiv.org/abs/1511.06391 Neural Machine Translation by Jointly Learning to Align and Translate - https://arxiv.org/abs/1409.0473 Pointer Networks - https://arxiv.org/abs/1506.03134 Attention Is All You Need - https://arxiv.org/abs/1706.03762 The Annotated Transformer - https://nlp.seas.harvard.edu/annotated-transformer/ Neural Turing Machines - https://arxiv.org/abs/1410.5401 A Simple Neural Network Module for Relational Reasoning - https://arxiv.org/abs/1706.01427 Relational Recurrent Neural Networks - https://arxiv.org/abs/1806.01822 Neural Message Passing for Quantum Chemistry - https://arxiv.org/abs/1704.01212 Scaling Laws for Neural Language Models - https://arxiv.org/abs/2001.08361 GPipe: Efficient Training of Giant Neural Networks using Pipeline Parallelism - https://arxiv.org/abs/1811.06965 Keeping Neural Networks Simple by Minimizing the Description Length of the Weights - https://www.cs.toronto.edu/~hinton/absps/colt93.pdf A Tutorial Introduction to the Minimum Description Length Principle - https://arxiv.org/abs/math/0406077 The First Law of Complexodynamics - https://scottaaronson.blog/?p=762 Quantifying the Rise and Fall of Complexity in Closed Systems: The Coffee Automaton - https://arxiv.org/abs/1405.6903 Kolmogorov Complexity - https://onlinelibrary.wiley.com/doi/book/10.1002/047174882X Variational Lossy Autoencoder - https://arxiv.org/abs/1611.02731 Machine Super Intelligence - https://www.vetta.org/documents/Machine_Super_Intelligence.p...

of the data, counting the size of the model itself. This is similar to the technique used in this blog post (argmin code length across class-conditioned compressors) except for counting the model size. Basically you can train a compressor per class and then choose the class compressor which best compresses the test data. It is a maximum likelihood argument because of Shannon's source coding theorem: a code length L corresponds to a probability 2^-L. The second way is the Normalized Compression Distance (NCD) [1], which uses code lengths to calculate information-theoretic distances which can then be plugged into distance-based algorithms like kNN. MDL interprets compressed lengths as likelihoods, while NCD interprets them for distance calculations. The theoretical foundation is Kolmogorov complexity which is the ideal (& uncomputable) lossless compressor, used to define information distance, an "ideal" distance metric based on algorithmic similarity. Data compression is not in principle restricted to syntactic similarity. As others have mentioned, the new wave of neural compressors (e.g. NNCP [2], CMIX [3], leading the large text compression benchmark [4]) outperform their traditional counterparts (e.g. gzip) because of the ability of neural networks to learn complex semantic patterns. Their improved ability to predict the next token means improved lossless compression. This has also been shown to be the case with pre-trained LLMs [5]. I think it's neat that improving compression improves machine learning, and improving machine learning improves compression! Looking forward to hearing other thoughts. [0] https://arxiv.org/abs/math/0406077 [1] https://arxiv.org/abs/cs/0111054 [2] https://bellard.org/nncp/nncp_v2.pdf [3] https://www.byronknoll.com/cmix.html [4] https://www.mattmahoney.net/dc/text.html [5] https://arxiv.org/abs/2309.10668