What's New? A Semantic Definition of Novelty

Russell Greiner, Michael R. Genesereth

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.

Introduction

In the early 1980s, as Artificial Intelligence (AI) moved toward more sophisticated knowledge representation, a fundamental question remained unanswered: What does it actually mean for a piece of information to be "new"? While humans have an intuitive grasp of novelty, Russell Greiner and Michael R. Genesereth argued that the lack of a rigorous definition hindered the development of effective learning systems. Without a formal metric, it is impossible to determine if a system has truly learned something about a specific topic or merely added a redundant string to its database.

The Failure of Syntactic Novelty

Early machine learning systems often relied on syntactic novelty. This approach checks for lexical presence—essentially asking if a specific token or word appears in a sentence. However, this method is deeply flawed for two primary reasons:

  1. Irrelevance: A sentence might mention a concept (e.g., "The cat is on the mat") without providing any new information about that concept if the system already knew its location.
  2. Inference: A sentence might provide vital information about a concept without mentioning its name directly. For instance, if a system knows that all mammals have hair, being told "A platypus is a mammal" provides novel information about the platypus's physical characteristics, even if the word "hair" is absent.

To address these issues, the authors propose a semantic definition based on the meaning and the constraints a sentence imposes on a world model.

Formalizing Novelty via Model Theory

The authors use Model Theory to formalize novelty, viewing a theory as a set of "possible worlds." A sentence is novel if it acts as a filter, removing possible worlds that are no longer consistent with our updated knowledge.

A set of interpretations (I0 to I3) for symbols A and B, illustrating the possible worlds defined by a theory.

They initially proposed the Fewer Interpretations ($New_{FI}$) conjecture: A sentence is novel if it reduces the total number of possible "real-world" referents for a symbol. While an improvement over syntactic methods, $New_{FI}$ fails to capture dependencies. For example, the statement $A \iff B$ establishes a link between two symbols. Even if it doesn't immediately restrict the possible values of $A$ in isolation, it changes the context of $A$ by tying its state to $B$. This dependency represents a form of learning that $New_{FI}$ overlooks.

The Core Contribution: Partial Interpretations ($New_{PI}$)

The paper’s primary contribution is the definition of novelty through Partial Interpretations ($New_{PI}$). This framework looks at assignments of values to only a subset of symbols in the language. A sentence $\sigma$ is considered novel about a concept $s$ if there exists some context—a partial interpretation of other symbols—where $\sigma$ reduces the possible meanings or states of $s$.

The mapping of partial interpretations used to define NewPI, showing how novelty is determined by constraints within specific contexts.

This definition captures the "Aha!" moment of dependency. By establishing that "If the light is on, the switch is up," you have provided novel information about the "light" because its state is now constrained by the "switch," even if you don't yet know the state of either.

Applications and "Aboutness"

This formal framework allows for a rigorous definition of "aboutness." The authors argue that we can determine what a fact is "about" by identifying which concepts it provides novel information for ($New_{PI}$). This has significant implications for indexing knowledge bases; if a sentence provides $New_{PI}$ information for symbol $A$, the system can formally justify indexing that sentence under $A$.

Furthermore, the authors used this framework to evaluate classic AI programs. They analyzed Winston’s ARCH (which learns structural descriptions) and Lenat’s AM (a mathematical discovery system), identifying exactly where their "novelty" originated and how they successfully constrained their respective search spaces.

Limitations and Future Directions

Despite its rigor, the $New_{PI}$ model has limitations that the authors acknowledge as areas for future research:

  • Deductive Closure: The model assumes the system already knows every possible implication of its current facts. Real-world systems have "resource-limited" reasoning and may find a fact novel simply because they haven't yet computed its implications.
  • Computational Complexity: While semantically sound, iterating through every possible interpretation is computationally expensive. The authors highlight the need for a syntactic formulation—a set of rules that can calculate $New_{PI}$ efficiently.
  • Intensional Novelty: The paper focuses on extensional novelty (what objects a symbol refers to) rather than intensional novelty (how a concept is described or defined), which remains a separate challenge in knowledge representation.

By moving from "words on a page" to "constraints on a world," Greiner and Genesereth provided a foundational tool for understanding how machines—and perhaps humans—incorporate new information into their understanding of reality.

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{greiner1983what,
  author = {Russell Greiner and Michael R. Genesereth},
  title = {{What's New? A Semantic Definition of Novelty}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1983},
}
Figure