Pattern Selection via Minimum Description Length

25 concepts21 papers1 proposal

In data mining and unsupervised learning, we frequently encounter a phenomenon known as the pattern explosion. Whether searching for frequent itemsets in transactional databases, recurring episodes in event sequences, or salient $n$-grams in text corpora, standard algorithms routinely output millions of candidate patterns. Most of these candidates are redundant, overlapping variations of the same underlying signals, or simply random noise.

Traditionally, researchers have controlled this explosion by setting manual thresholds, such as minimum support or frequency. However, tuning these thresholds is a guessing game: set them too high, and you miss rare but vital insights; set them too low, and you drown in redundant results.

To solve this problem, a powerful research direction frames pattern discovery not as a search for everything that occurs frequently, but as a data compression task. Guided by the Minimum Description Length (MDL) principle, this approach provides a parameter-free, mathematically rigorous framework for selecting a compact, non-redundant set of patterns that best summarizes a dataset.


The Core Mechanism: Compression as a Metric

The foundational intuition behind this paradigm is simple: the best set of patterns is the one that compresses the data best.

To operationalize this idea, the MDL principle utilizes a two-part code. Suppose we have a dataset $D$ and we want to find the optimal model (or dictionary of patterns) $M$. We measure the quality of $M$ by calculating the total description length $L(M, D)$ in bits:

$$L(M, D) = L(M) + L(D \mid M)$$

Where:

  • $L(M)$ is the cost of describing the model itself (e.g., the number of bits needed to store the definitions of the patterns in our dictionary).
  • $L(D \mid M)$ is the cost of encoding the data given that model (e.g., the number of bits needed to reconstruct the dataset by replacing raw data points with short pointers to our pattern dictionary).

This objective function acts as a natural regularizer. If a pattern is highly frequent and complex, adding it to the dictionary increases $L(M)$ slightly, but drastically reduces $L(D \mid M)$ because it replaces many raw occurrences with compact pointers. Conversely, if a candidate pattern is redundant—meaning it is a minor variation of a pattern we already know—adding it to the dictionary will increase $L(M)$ without offering any additional savings in $L(D \mid M)$. The MDL principle will therefore reject it.


From Itemsets to Sequences: Broad Applicability

This compression-based framework is highly versatile and generalizes across a wide array of data modalities.

Transactional and Tabular Data

In the context of itemset mining, Jilles Vreeken et al. introduced the KRIMP framework in Krimp: mining itemsets that compress. KRIMP demonstrates that minimizing description length can distill millions of frequent itemsets down to a few hundred highly characteristic ones. To capture even more complex interactions, Nikolaj Tatti et al. developed an approach in Finding Good Itemsets by Packing Data that treats the presence and absence of items symmetrically, using decision trees as an encoding mechanism to find deep structural dependencies without requiring user-defined frequency thresholds.

Sequential and Temporal Data

When dealing with event sequences, patterns unfold over time, introducing temporal variations and noise. In The long and the short of it: summarising event sequences with serial episodes, Jilles Vreeken et al. introduced the SQS framework, which uses MDL to identify non-redundant serial episodes that summarize event streams. To accommodate real-world variations where events might overlap or interleave, Apratim Bhattacharyya et al. proposed SQUISH in Efficiently Summarising Event Sequences with Rich Interleaving Patterns, allowing for more flexible, semantically rich sequence compression. More recently, Aleena Siji et al. extended this paradigm to conditional rule mining in Seqret: Mining Rule Sets from Event Sequences, compressing long event sequences into succinct "if-then" rule sets.

Text and Feature Selection

The same compression principles apply directly to feature selection in natural language processing and text deduplication. In Compressive Feature Learning, Hristo S. Paskov et al. framed document feature selection as a dictionary-based lossless compression task, reducing massive $n$-gram feature spaces by two orders of magnitude while maintaining or improving classification accuracy. Similarly, Jyotsna G. Singh et al. developed DUPEX in Simplify Your Law: Using Information Theory to Deduplicate Legal Documents, using MDL to automatically identify and extract the most redundant phrases in massive legal corpora like the United States Code without relying on arbitrary length or frequency thresholds.


Structuring Complex and Multi-Dimensional Truths

Beyond flat lists of itemsets or sequences, MDL serves as a powerful lens for discovering multi-dimensional, structured relationships within data.

Subspace Clustering and Tile Trees

In The blind men and the elephant and When Pattern Met Subspace Cluster, Jilles Vreeken et al. argued that pattern mining and subspace clustering are fundamentally two sides of the same coin: both seek to find informative "tiles" or dense regions of data. To capture hierarchical relationships among these tiles, the authors developed Stijl in Discovering Descriptive Tile Trees - By Mining Optimal Geometric Subtiles, which builds nested trees of geometric regions to summarize binary datasets without manual density thresholds.

Advanced Structural Variations

The flexibility of MDL allows it to adapt to highly specialized data structures:


Overcoming the Computational Bottleneck

If compression-based model selection is so effective, why isn't it used everywhere? The primary challenge is computational. Finding the absolute global minimum description length requires evaluating an exponential combination of candidate patterns, a problem that is fundamentally NP-hard.

To make this paradigm practical for large-scale datasets, researchers rely on two primary algorithmic strategies:

Instead of scanning the entire database repeatedly to evaluate how a new pattern affects compression, algorithms use clever data structures to track pattern overlaps. For instance, Sibylle Hess et al. introduced the SH-tree in SHrimp: Descriptive Patterns in a Tree. By capturing the dependencies between overlapping patterns directly within a tree structure, SHrimp avoids exhaustive database scans, drastically accelerating the greedy MDL selection process on large, dense datasets.

2. Mathematical Relaxations

Another strategy shifts the problem from discrete combinatorial optimization to continuous optimization. In Data Representation and Compression Using Linear-Programming Approximations Hristo Paskov, Hristo S. Paskov et al. demonstrated that lossless compression tasks can be relaxed and solved efficiently using linear programming. This approach allows the core insights of MDL-based feature selection to scale to massive biological and textual datasets, successfully isolating salient signals from background noise at scale.

Key Foundational Work

A Graphical Model for Content Based Image Suggestion and Feature Selection (2007) — contributed 1 concept elements to this direction.
Discovering Patterns to Extract Protein-Protein Interactions from Full Biomedical Texts (2004) — contributed 1 concept elements to this direction.
PROTERAN: animated terrain evolution for visual analysis of patterns in protein folding trajectory (2007) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_compression_based_model_selection_088fa738,
  title = {compression-based model selection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/compression-based-model-selection/rdr_088fa738d1c34e08a5e12919c6c728e4},
  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_compression_based_model_selection_088fa738_v1,
  title = {compression-based model selection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/compression-based-model-selection/rdr_088fa738d1c34e08a5e12919c6c728e4/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake