Semantic Novelty through Relational Dependencies

16 concepts3 papers1 proposal

When is a piece of information truly "new" or "interesting"?

In classical information theory and data mining, novelty and information gain are typically quantified by reduction in uncertainty—such as shrinking the absolute range of a variable or maximizing the predictive power of a rule. However, these metrics often fail to capture human intuition. A fact can leave the individual probabilities or possible values of a variable completely unchanged, yet fundamentally alter our understanding of how that variable interacts with the rest of the world.

A powerful alternative perspective frames novelty and interestingness not as the restriction of isolated variables, but as the discovery or alteration of conditional dependencies. Under this view, information is meaningful if it breaks default assumptions of independence or introduces new relational constraints between concepts.

The Limits of Absolute Information Gain

To understand why traditional measures fall short, consider a knowledge base containing independent concepts. If we learn a new statement that links these concepts without narrowing their individual scopes, traditional syntactic metrics might flag the statement as uninformative.

In What's New? A Semantic Definition of Novelty, Greiner et al. argue that this narrow focus ignores how relational information constrains a world model. A statement can be highly novel if it establishes a logical dependency between previously unrelated symbols, linking the state of one variable to the state of another.

For example, knowing that an object is red tells us nothing about its weight. If we learn a rule stating that "all red objects in this specific environment are heavy," the absolute range of possible colors (red) and weights (heavy) has not changed. What has changed is the relational structure: the state of the weight variable is now contingent on the color variable. Traditional systems that look only at individual variable entropy miss this constraint entirely.

Evaluating Novelty via Partial Interpretations

How do we formalize this intuition mathematically or logically? The solution proposed by Greiner et al. relies on analyzing partial assignments.

Instead of evaluating a statement's impact on a symbol in isolation, the system evaluates how the statement affects a concept's possible interpretations under various partial assignments to other symbols.

Standard Novelty: Does this fact reduce the absolute range of X?
Semantic Novelty: Given a specific context (Y = y), does this fact reduce the possible meanings of X?

As also explored in related semantic frameworks, a statement provides novel information if it influences the set of possible values for a concept given incomplete information about related concepts. By checking whether a sentence reduces the possible meanings of a symbol when conditioned on specific contexts, the system can detect subtle, indirect constraints that only manifest when combined with background knowledge.

Breaking the Assumption of Independence

This dependency-based framing applies equally well to data mining and probabilistic reasoning. When humans look at data, they naturally operate under a default assumption of independence unless evidence suggests otherwise. We find rules "interesting" precisely when they violate this default assumption.

In A New Approach to Rule Interest Measures, the authors leverage this insight to redefine what makes an association rule valuable. Traditional data mining evaluates a rule like $A \land B \rightarrow C$ based on its predictive power (e.g., how often $C$ occurs when $A$ and $B$ are present). However, if $A$ and $B$ independently cause $C$, their co-occurrence is entirely expected and uninteresting.

To capture true human interest, the approach in [1] directly tests for conditional independence. For a rule $A \land B \rightarrow C$, the method evaluates whether the probability of $A$ and $B$ co-occurring given $C$ deviates from the product of their individual probabilities given $C$:

$$P(A \land B \mid C) \neq P(A \mid C) \cdot P(B \mid C)$$

If the equality holds, $A$ and $B$ are conditionally independent given $C$, meaning the rule provides no new relational insight. If the equality is meaningfully broken, it reveals a non-trivial dependency between the constituent parts of the rule within the context of $C$.

Why This Shift Matters

Shifting the definition of information gain from "value reduction" to "dependency alteration" bridges the gap between algorithmic metrics and human intuition.

  1. Context-Dependent Awareness: Systems can recognize that a fact is highly informative in specific scenarios, even if its global, average impact on a variable appears negligible.
  2. Relational Discovery: Rather than just confirming expected co-occurrences, algorithms can prioritize uncovering the hidden structural links that bind a system together.

By focusing on how new data reshapes the web of dependencies between concepts, AI systems can more effectively mimic human reasoning, filtering out trivial statistical correlations to focus on genuinely novel insights.

Key Foundational Work

A New Approach to Rule Interest Measures (1998) — contributed 8 concept elements to this direction.
What's New? A Semantic Definition of Novelty (1983) — contributed 4 concept elements to this direction.
What's New? A Semantic Definition of Novelty (1983) — contributed 4 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_dependency_based_information_gain_1fa77100,
  title = {dependency-based information gain},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dependency-based-information-gain/rdr_1fa77100ba9149939413ed3a8972ee47},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_dependency_based_information_gain_1fa77100_v1,
  title = {dependency-based information gain},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dependency-based-information-gain/rdr_1fa77100ba9149939413ed3a8972ee47/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake