In traditional data mining, the goal is often to find patterns that meet objective criteria, such as high frequency or statistical significance. However, analysts frequently encounter a "pattern explosion": a search returns thousands of results, most of which are either common sense or redundant variations of a single underlying fact.
A research direction led by researchers like Tijl De Bie, Kai Puolamäki, and Jilles Vreeken shifts the focus from objective metrics to subjective interestingness. The core idea is that a pattern is only interesting if it is surprising relative to what the analyst already knows. By formalizing this "prior knowledge" and updating it iteratively, we can ensure that every step of an analysis provides genuinely new information.
The Background Knowledge Model
To determine if a pattern is surprising, we first need a mathematical representation of the user's current state of knowledge. This is known as the background model.
As Szymon Jaroszewicz and Dan A. Simovici demonstrated in Interestingness of frequent itemsets using Bayesian networks as background knowledge, we can use Bayesian networks to encode what an analyst expects to see. If a new pattern (like a frequent itemset) deviates significantly from the probability distribution predicted by the background model, it is deemed "interesting."
A more flexible approach, championed by Tijl De Bie in Subjective interestingness of subgraph patterns, uses the Maximum Entropy (MaxEnt) principle. The MaxEnt distribution is the most "unbiased" distribution that satisfies the constraints of the user's knowledge (e.g., knowing the average degree of nodes in a graph). Any pattern that is highly improbable under this MaxEnt distribution is, by definition, surprising.
The Iterative Update Loop
The defining characteristic of this research direction is its iterative nature. Once a surprising pattern is discovered and presented to the user, it is no longer "surprising"—it has become part of the user's knowledge.
To prevent the system from rediscovering the same pattern or its trivial consequences, the background model must be updated. This process, described by Sami Hanhijärvi and Heikki Mannila in Tell me something I don't know: randomization strategies for iterative data mining, involves:
- Discovery: Finding a pattern that is surprising relative to the current background model.
- Incorporation: Adding that pattern as a new constraint to the background model.
- Refinement: Updating the model (often using MCMC randomization or I-projections) to reflect this new constraint.
- Repeat: Searching for the next pattern that is surprising relative to the updated model.
This loop effectively "explains away" redundant results. As Bo Kang and colleagues note in Subjectively Interesting Subgroup Discovery on Real-Valued Targets, this mechanism shifts the baseline for future searches, naturally prioritizing novel insights without requiring manual diversity filters.
Applications Across Domains
While the framework originated in frequent itemset and graph mining, its logic is being applied to increasingly diverse fields:
- Scientific Discovery: The DEMUD algorithm, proposed by Kiri Wagstaff in Guiding Scientific Discovery with Explanations Using DEMUD, uses an iterative eigenbasis model to help scientists find rare anomalies in planetary data, ensuring that once a "type" of anomaly is found, the system moves on to find different ones.
- Visual Analytics: Systems like MERCER, developed by Hao Wu and Chris North, use MaxEnt models to guide users through complex relationship chains in text, as seen in Interactive Discovery of Coordinated Relationship Chains with Maximum Entropy Models.
- Large Language Models: The same intuition of "iterative re-evaluation" appears in modern RAG (Retrieval-Augmented Generation) pipelines. Yin Zhu and colleagues' FuRePA framework (Furthest Reasoning with Plan Assessment) and the DeepNote system (DeepNote: Note-Centric Deep Retrieval-Augmented Generation) both use iterative loops to discard redundant or irrelevant information as the model's "knowledge state" evolves during multi-step reasoning.
Why It Works
The power of this approach lies in its ability to automate the "Aha!" moment. By treating the search for patterns as a communication process between the data and the user, researchers have moved from finding statistically significant patterns to finding informative ones. By constantly updating the "null hypothesis" to include everything the user has already seen, the system ensures that the analyst's time is spent only on the data's most stubborn, unexplained mysteries.