Pattern Discovery through the Minimum Description Length Principle

This direction is split into other directions: compression-based model selection. Its last version stays readable and citable here.

Version 1 of 188 papers116 conceptsfrozen 2026-10-04

In data mining, we often face a "pattern explosion." If you ask a traditional algorithm to find frequent itemsets or sequential rules in a large database, it might return millions of results. Most of these are redundant—slight variations of the same underlying phenomenon. To find the "essence" of the data, researchers have turned to a concept from information theory: the Minimum Description Length (MDL) principle.

The core intuition is that learning is compression. If we can find a small set of patterns that allows us to compress a dataset into its shortest possible representation, those patterns must capture the most important structural regularities of the data.

The Problem of Redundancy and Noise

Traditional pattern mining relies on user-defined thresholds, such as "minimum support" (how often a pattern appears). However, as Matthijs van Leeuwen, Jilles Vreeken, and Arno Siebes argue in Compression Picks Item Sets That Matter, these thresholds are arbitrary and often lead to an overwhelming number of redundant results.

Furthermore, in noisy environments like time series, traditional methods often find "spurious" rules—patterns that appear frequent just by chance. Mohammad Shokoohi-Yekta and Eamonn J. Keogh demonstrated in Discovery of Meaningful Rules in Time Series that framing rule discovery as a compression problem prevents the identification of these coincidental patterns. If a rule doesn't help compress the data, MDL rejects it as noise.

How MDL Works: The Two-Part Code

The MDL principle, as explored by Yoichiro Nakakuki and Edwin P. D. Pednault, selects the "best" model by minimizing the total description length $L(M) + L(D|M)$:

  1. $L(M)$: The number of bits needed to describe the model (the patterns or rules).
  2. $L(D|M)$: The number of bits needed to describe the data, given that we know the model.

This creates a natural "Goldilocks" balance. A model that is too simple (few patterns) will be easy to describe ($L(M)$ is small) but will do a poor job of compressing the data ($L(D|M)$ is large). A model that is too complex (too many patterns) will describe the data perfectly ($L(D|M)$ is small) but will be massive and overfit ($L(M)$ is large). The optimal model—the one that truly understands the data—is the one that minimizes the sum of both.

Distilling the Essence of Data

By treating pattern discovery as a compression task, researchers can extract highly representative summaries across various domains:

  • Sequential Data: Jilles Vreeken and Nikolaj Tatti developed SQS to identify a small, non-redundant set of "serial episodes" that summarize event sequences, effectively "squeezing" the information into its most informative parts (The long and the short of it).
  • Model Debugging: In Label-Descriptive Patterns and their Application to Characterizing Classification Errors, Michael A. Hedderich and colleagues use MDL to find a succinct set of patterns that explain why a deep learning model fails, providing a global "fingerprint" of model errors rather than thousands of disconnected local explanations.
  • Constraint Discovery: Boris Wiegand and Jilles Vreeken showed that MDL can even discover the underlying "rules" or constraints of a system (like scheduling logic) using only positive examples, because the true rules are the most efficient way to restrict the space of possible observations (What Are the Rules?).

Why It Works: Automatic Regularization

The beauty of the MDL approach is that it is often parameter-free. In Automatic Segmentation of Data Sequences, Liangzhe Chen and B. Aditya Prakash demonstrate that MDL can find the ideal number of segments in a sequence without the user needing to specify how many segments to look for.

Because every new pattern added to the model "costs" bits, the algorithm only includes a pattern if the "savings" it provides in compressing the data outweigh its own description cost. This acts as a built-in Occam’s Razor, naturally penalizing complexity and ensuring that the resulting pattern set is diverse, non-redundant, and statistically robust. As Alexander Botta noted in Regularity and Structure, a concept is only "real" within a dataset if it pays for itself through compression.

Papers in this version

Showing 60 of 88 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_pattern_discovery_through_the_minimum_de_507d4e2e,
  title = {Pattern Discovery through the Minimum Description Length Principle},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/pattern-discovery-through-the-minimum-description-length-principle/rdr_507d4e2e465f4d2e8dbf319996b7a3db},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_pattern_discovery_through_the_minimum_de_507d4e2e_v1,
  title = {Pattern Discovery through the Minimum Description Length Principle},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/pattern-discovery-through-the-minimum-description-length-principle/rdr_507d4e2e465f4d2e8dbf319996b7a3db/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}