What's New? A Semantic Definition of Novelty

TL;DR

This paper tackles the fundamental question of what it means for a piece of information to be "new" in the context of learning. The authors propose a semantic definition of novelty, moving beyond simple syntactic checks, to capture how new facts refine our understanding of concepts and their relationships. This work is crucial for developing more sophisticated AI learning systems that can truly grasp and integrate new knowledge.

What Problem Does This Paper Address?

In artificial intelligence, a core aspect of learning is incorporating new information into an existing knowledge base or "theory." However, despite extensive research in machine learning, there's been a lack of a rigorous definition for what makes a statement "new." This paper aims to fill that gap by providing a semantic definition of novelty, focusing on how a new statement refines our understanding of a specific concept. This is important because simply adding a statement doesn't guarantee it provides genuinely new insight, and a clear definition is needed to build more effective learning agents.

Methods

The authors propose a two-tiered approach to defining novelty:

  1. Newness with Respect to a Theory (N(Th, σ)): This is the foundational definition. A statement σ is considered "new" with respect to a theory Th if it eliminates some possible interpretations of that theory. In essence, it adds constraints that reduce the set of possible "worlds" or scenarios the theory describes. This is a semantic definition, relying on the set of models (interpretations) that satisfy the theory.
  2. Newness with Respect to a Concept (New(Th, s, σ)): This is a more nuanced definition that addresses when a statement provides new information about a specific concept (represented by a symbol 's').
  3. Initial (Syntactic) Idea: A statement is new if it contains the symbol 's' (e.g., "AAB" is new about "A"). This is quickly dismissed as insufficient.
  4. Second (Interpretation Range) Idea (NewFI): A statement is new about 's' if it restricts the set of possible interpretations for 's'. This aligns with information theory's idea of reducing uncertainty.
  5. Third (Partial Interpretations) Idea (NewP): This is the most sophisticated definition. It recognizes that a statement can be new about 's' not only by directly limiting 's's interpretations but also by establishing or increasing 's's dependency on other symbols. This is captured by examining how a statement affects the set of possible assignments to 's' given partial interpretations of other symbols. If any partial interpretation leads to fewer possible values for 's' (without making 's' impossible), the statement is considered new. This is visualized using tableaux, which show the consistency of assignments.

Datasets

Not discussed in the paper. The paper focuses on theoretical definitions and uses propositional logic examples rather than empirical evaluation on datasets.

Key Insights and Ideas

  • Semantics Over Syntax: The paper strongly advocates for a semantic definition of novelty, arguing that understanding the meaning and implications of a statement (its effect on interpretations) is far more powerful than simply checking for the presence of symbols.
  • Novelty as Constraint Reduction: The core idea is that new information constrains possibilities. A statement is new if it rules out some previously valid interpretations of the theory or a concept.
  • Dependency as a Source of Novelty: A key insight is that a statement can be novel by revealing or strengthening dependencies between concepts. Even if a statement doesn't directly limit a concept's possibilities, if it makes that concept's behavior dependent on others (which could lead to future limitations), it's considered new.
  • Partial Interpretations are Key: The most robust definition (NewP) relies on analyzing how statements affect a concept's interpretations under various partial assignments to other symbols. This captures subtle forms of novelty that simpler definitions miss.
  • "Aboutness" is Tied to Novelty: The paper suggests that a statement is "about" a concept if it expresses something new about that concept relative to a theory that doesn't already imply that newness.

Key Results

The paper presents a series of definitions for novelty, culminating in the NewP (Partial Interpretation) definition, which is argued to be the most comprehensive. While no quantitative results are presented (as it's a theoretical paper), the authors demonstrate through examples and counterexamples how their definitions progressively capture more nuanced forms of novelty, particularly the concept of dependency. The NewP definition is shown to subsume the NewFI definition and handles cases where statements are new by establishing dependencies.

Limitations and Future Work

  • Computational Complexity: The paper acknowledges that the NewP definition, while general, can be computationally expensive due to the need to examine many partial interpretations and use tableaux.
  • Deductive System Dependency: The current definitions rely on a complete deductive system and the requirement that theories be deductively closed. The authors suggest extending the formalism to handle incomplete deductive systems and resource-limited deducibility.
  • Syntactic Formulation: A pressing research task is to find a syntactic formulation for the NewP relation, analogous to how Nsyn matched Nsem, which could lead to more operational versions.
  • Intensional vs. Extensional: The work focuses on extensional novelty (based on referents). An intensional approach (based on descriptions) is mentioned as a potential area for future work.
  • Assertional Novelty: The paper distinguishes between "definitional" novelty (NewP, refining a concept's referent) and "assertional" novelty (providing new facts about a concept's attributes, e.g., "RDG's hair color is blond"). This latter type is not fully formalized here.

Summary updated

Abstract

A central process in any learning experience is the incorporation of a new fact into an existing theory. Despite the abundance of papers on learning, no one has yet defined rigorously what it means to be "new". This paper attempts to fill that gap by first stating, and then formalizing several intuitive ideas about novelty, focusing on what it means for a statement to be a new fact about some concept. The report also includes a brief discussion of how this result might be applied and outlines many remaining research areas.
BibTeX
@inproceedings{1983what,
  title = {{What's New? A Semantic Definition of Novelty}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1983},
}
Figure