Subjective Interestingness for Information Theoretic Pattern Mining

24 concepts23 papers1 proposal

Traditional data mining algorithms rely heavily on objective metrics like frequency, density, or support to identify patterns. However, as datasets grow in size and complexity, these metrics inevitably trigger a "pattern explosion." An analyst searching for insights is often overwhelmed by thousands of results, most of which are either completely obvious (e.g., "customers who buy milk also buy bread") or redundant variations of a single underlying fact.

To solve this problem, a prominent research direction shifts the focus from objective metrics to subjective ones. Instead of evaluating a data pattern in a vacuum, this framework evaluates patterns based on how much new information they provide to a specific human analyst, given what that analyst already knows. By combining information theory with probabilistic modeling, this approach formalizes the human experience of "surprise" and "insight."

Formalizing Prior Knowledge with Maximum Entropy

How do we mathematically model the contents of an analyst's mind? The subjective interestingness framework achieves this by constructing a background probability distribution over the data space. This distribution represents the user's current belief system.

If an analyst knows only a few basic properties of a dataset—such as the row and column sums of a binary matrix, or the degrees of nodes in a network—how should we model their expectations for the rest of the data? As established by Tijl De Bie in Maximum entropy models and subjective interestingness: an application to tiles in binary databases, the Maximum Entropy (MaxEnt) principle provides the mathematically unbiased solution.

The MaxEnt principle constructs a probability distribution that satisfies the user's known constraints while remaining completely uniform (maximizing entropy) over everything else. It assumes absolute ignorance about any structures beyond what the user has explicitly specified. This framework has proven highly versatile, allowing researchers like Jilles Vreeken et al. in Maximum Entropy Models for Iteratively Identifying Subjectively Interesting Structure in Real-Valued Data to extend background models from simple binary matrices to complex, real-valued datasets.

The IC-DL Ratio: Balancing Surprise and Complexity

Once a background model $M$ is established, we can quantify the "interestingness" of any newly discovered pattern. This is achieved by balancing two competing forces: Information Content (IC) and Description Length (DL).

1. Information Content (Surprise)

The Information Content of a pattern is defined as its negative log-probability under the background model:

$$IC(\text{pattern}) = -\log P(\text{pattern} \mid M)$$

If a pattern is highly probable given the analyst's prior knowledge, its probability is close to $1$, and its $IC$ approaches $0$—it tells the user nothing new. Conversely, if a pattern is highly improbable under the background model, its $IC$ is large, signaling a high degree of statistical surprise.

2. Description Length (Cognitive Cost)

Optimizing for surprise alone introduces a major flaw: the algorithm will naturally favor massive, highly intricate, or fragmented structures simply because they are statistically rare. However, a human analyst cannot easily interpret a pattern defined by hundreds of disjointed rules. To account for this, the framework introduces Description Length ($DL$), which measures the complexity required to communicate the pattern's structure or rule to the user.

3. The Final Metric

To identify patterns that offer the highest conceptual payoff for the lowest cognitive effort, the subjective interestingness ($SI$) score is typically formulated as a ratio:

$$SI = \frac{IC}{DL}$$

This ratio represents the information gain per unit of descriptive cost. This exact formulation underpins a wide array of pattern-mining tasks, from finding dense blocks ("tiles") in binary data (Anes Bendimerad et al. in Gibbs Sampling Subjectively Interesting Tiles) to identifying exceptional subgroups in multivariate continuous data (Jefrey Lijffijt et al. in Subjectively Interesting Subgroup Discovery on Real-valued Targets). A closely related strategy is pursued by Matthijs van Leeuwen in Maximal exceptions with minimal descriptions, which leverages the Minimum Description Length (MDL) principle to alternate between maximizing local exceptionality and minimizing description complexity.

Iterative Discovery and the Elimination of Redundancy

If an algorithm surfaces a highly surprising pattern, the next ten patterns it finds should not merely be minor variations of that same insight. The subjective framework elegantly solves this through iterative updating.

[Prior Knowledge Constraints] 
       │
       ▼
[MaxEnt Background Model] ──► [Evaluate Patterns via IC/DL] ──► [Surface Top Pattern]
       ▲                                                               │
       │                                                               │
       └─────────────────── [Update Constraints] ──────────────────────┘

When a pattern is presented to the analyst, the system assumes the analyst immediately absorbs this information. The pattern is converted into a new constraint, and the background MaxEnt model is re-optimized. Because the updated model now accounts for this new structure, the probability of any redundant or overlapping patterns immediately increases. Consequently, their $IC$ drops to near zero, forcing the algorithm to search for genuinely novel insights in the next iteration.

Generalizing to Complex Network Structures

The mathematical elegance of the $IC/DL$ ratio is its ability to generalize seamlessly across diverse data structures, particularly graphs and networks. Instead of mining subgraphs based on raw edge density, authors have used MaxEnt models to find structures that are surprising relative to the network's global topology.

Broader Connections to Cognitive Systems

The core philosophy of this research direction—that interestingness is a function of compression, predictability, and surprise—extends far beyond traditional data mining tables and graphs.

In the domain of artificial curiosity and reinforcement learning, Jürgen Schmidhuber in Simple Algorithmic Principles of Discovery, Subjective Beauty, Selective Attention, Curiosity & Creativity formalizes "interestingness" as the first derivative of data compressibility. In this view, an agent is intrinsically motivated to explore its environment not by random noise, but by actions that actively improve its ability to compress its sensory history.

From a neurocognitive perspective, Geraint A. Wiggins and Joydeep Bhattacharya in Mind the gap: an attempt to bridge computational and neuroscientific approaches to study creativity argue that human creativity is an emergent property of the brain's predictive processing. They suggest that the most valuable outputs for conscious processing hit a cognitive "sweet spot" that maximizes the product of probability and unexpectedness—avoiding both boring predictability and meaningless randomness.

Even in modern text processing, the same principle applies. Anthony Kum Hoe Tung et al. demonstrate in QALinkPlus: Text Enrichment with QA data that text enrichment systems can be significantly improved by moving past simple keyword retrieval to algorithmically rank supplementary information based on its novelty and structural complexity.

By shifting the definition of value from objective frequency to subjective surprise, the information-theoretic framework provides a mathematically rigorous foundation for what it means for information to be genuinely "interesting."

Key Foundational Work

Proposed Interestingness Measure for Characteristic Rules (1996) — contributed 1 concept elements to this direction.
Simple Algorithmic Principles of Discovery, Subjective Beauty, Selective Attention, Curiosity & Creativity (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_subjective_interestingness_metric_12042896,
  title = {subjective interestingness metric},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/subjective-interestingness-metric/rdr_1204289618334375b4ff583acf91768b},
  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_subjective_interestingness_metric_12042896_v1,
  title = {subjective interestingness metric},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/subjective-interestingness-metric/rdr_1204289618334375b4ff583acf91768b/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