What's New? A Semantic Definition of Novelty

1 I nt rod u ction

A central process in any learning experience is the incorporation of a new fact into an existing theory. Often the goal of that process is more specific, to learn some new fact about some concept. But what does it mean to claim that a sentence is new, and even more interesting, what qualifies as a novel fact about some concept? Despite the vast interest in learning and the abundance of related papers (cf. [Dietterich 81 a], [Buchanan 78], [Michalski 83], [Dietterich 81 b] , [Dietterich 82]), no one has rigorously defined what it means to be "new", either in general or with respect to a single concept.

This paper attempts to fill that gap. Our goal is to obtain a semantic rather than a syntactic understanding of novelty. This preference stems !rom our belief that a semantic account (one based on the possible interpretations of the theory) provides important insight into the phenomenon of novelty. It also means we may be able to generalize these results to other logics and languages.

The results of this research are relevant (and useful) to many different fields. The primary importance of this work is in providing a first stab at describing the different senses of novelty. In addition to the applications a complete arid adequate definition of newness would have as an analytic tool , there are possible applications in knowledge acquisition, representation, and discourse analysis. Many of these stem from the intimate connection between novelty and the intuitive notion of "aboutness" . (Section 4 elaborates on each of these.)

This leads to the proposal that

This same definition can be expressed syntactically (in terms of logical deducibility rather than semantic validity) using

As these are equivalent (whenever the language of the theory remains fixed; see [Enderton 72],) we will simply use N.

3 New with respect to a Concept

In many situations it is not enough to realize that an assertion is new; rather, one often wants to claim that it is a new fact about some concept . With this in mind, we define the ternary relation New(Th, s, a) to mean that the assertion a expresses a new fact about the concepts with respect to the theory Th . The "learning step" involves adding this sentence a (along with all of its deductive consequences) to the theory.

What should go into a definition of New(Th, s, a)? Clearly, a necessary condition is ·that a be a new fact with respect to the entire theory; that is, N ( Th, a). But beyond that, we want to capture the sense in which a further specifies the concept s, or enables the derivation of additional relevant conclusions about s.

This section will present a definition of New by proposing a series of "increasingly more nearly correct" descriptions. For simplicity, the examples are taken from propositional logic.

Conjecture 1: Syntactic Method. Most statements which relay information about some concept will contain the symbol that refers to that concept. This leads to the proposed syntactic solution: The sentence a conveys new information about the symbol A if the token "A" is lexically included in the siring of tokens which form a, denoted with the assertion Lexln("A",a)- e.g., Lexln("A","A/\8") . For the reasons mentioned above, we will further insist that N ( Th, a) . Formally,

Unfortunately, this syntactic condition is neither necessary nor sufficient. To see that it is not necessary, realize that we want New({A= B},"A","B") to be true, since asserting Bin this situation means that A must now be true, which had not been the case before that assertion.

To show insufficiency is a little trickier. Should New( {Av B}, "A"," A=B") be true? We argue the answer is no: In this context, asserting A=B is the same as asserting B, which we know says nothing new about A. We clearly need a more powerful method for specifying novelty.

Conjecture 2: Fewer Interpretations. Using the notion of possible interpretations discussed in Section 2, we can define the "interpretation range" of a particular symbol. Let the term IJ(s) designate the "real world" referent of the symbols, given by the interpretation I J - here, either I or E. 3 We use this to define the interpretation range of the symbol s, I Th ( s), by

As additional facts can only further restrict the range of possible interpretations for any symbol , we have 1Th' (s) ~ 1Th(s) whenever Th ~ Th ·. This leads to our second conjecture,

This i\lewFI definition seems, at first, adequate. In addition to paralleling the t1 situation, it also resonates nicely with the ideas of Shannon's Information Theory, in which information is tied to the reduction of uncertainty in the distribution of possible values of a signal. (See [Gallager 78] .) It also handles the two cases used above to discredit NewSyn·

Unfortunately, this NewFI requirement does not include all desired cases. There are some sentences that do convey new information in the informal sense outlined above but that do not satisfy this constraint: Start with an empty theory, Thl +- {}, 4 in the language L = {A, B}. The four possible interpretations are shown in Figure 1. By inspection, I Tht ("A") ={I. .E} . Now, form Th2 +- Thl + "A=B". While this leaves only two of the four original interpretations, 1 0 and 1 3 , 1Th 2 ("A") remains {I..E}, indicating that A=B said nothing ~lawfl about A.

Although NewFI rejects this A= B, we still believe it should be considered a new fact about A in this situation: If we later learn ,B, we will be able to infer that , A, a conclusion that would not

have followed without that sentence. That is, any sentence that makes A's range of interpretations dependent on some other symbol (in the sense that A=B made A dependent on B) also "feels" new.

So there are at least two ways a statement can be new:

• It directly limits the interpretation range of A, or
• It establishes (or increases) a dependency of A on some other symbols (as that may, in turn, lead to a reduction of the above type).

While NewFI covers the first case exactly, it fails in the second.

Conjecture 3: Partial Interpretations. To define dependency requires an understanding of what it means for one symbol to depend on some other symbols. The A=B case above is clearly one instance of this. In addition to such singular dependencies (of A on one other symbol,) A may depend on a combination of symbols. (Consider the assertion A=(B=C) .

3 The underbar notation denotes the referent of the corresponding linguistic symbol.

4 The notation T <- I} means the theory T is assigned the deductive closure of the set, >jl ; and Th +a refers to the deductive closure of ThU{ a} .

Fixing any assignment to B alone, A will still be "arbitrary" ; that is, it could be either I or E. depending on C. However, if both B and C are fixed, then A is fully determined.)

We saw that a is a new fact about A if it increases A's dependency on some n-tuple of symbols <s 1 , ... , sN>' that is, if asserting a restricts the set of assignments available to A, given some assignment <S.1, .. . · S.N> to the symbols <s 1 , ... , sN>. For example, we noted that A was more dependent on B in Th2 than in Th1 . We see this by considering the assignment of B to f. In Th1, A's value could be either E or I. independent of this assignment to B. However, A can no longer be assigned I in Th2, given this assignment to B; its value is now restricted to f.

As this "<s1, ... , sN> assignment to <S. 1 , ... · S.N>" reflects an assignment of only a subset of the symbols, { s 1 } ~ L, we will call it a partial interpretation. We can associate with each partial interpretation the equivalent class of full interpretations that agree on the assignment of a set of symbols. Formally, take ::my function that maps some of the symbols of the language into the universe, U - that is, any q>: ~>-> U, where ~ ~ L. We can use this to define the equivalence class ITffJ ThD as the set of interpretations that consistently extend q> - that is, it includes each interpretation that agrees with q>'s assignment of each symbol in q>'s domain and assigns every other element of L in some consistent manner.

The assignments of s that are consistent with the partial interpretation IT q> ThTI are just

With this notation, we can state that A's dependency on the symbols ~=Domain [ q>] increases if the set of possible values of A consistent with the partial interpretation, [ q> ThD ("A"), decreases but remains non-empty. (Seeing it vanish means that there are no values of A that are consistent with this assignment, which means that no models can be derived by extending this partial interpretation.)

To test if a is new, therefore, consider all of the assignments available to A for each partial interpretation, before and after adding this purportedly new sentence a to the theory. If the number of possible referents of A decreases for any partial interpretation (and remains non-empty), we will declare that a is new.

A few notes:

1. We will say that the particular function q> whose partial interpretation IT q> ThD decreased in the above equation is a "witness" to a's novelty (with respect to A).
2. This definition subsumes the New 1 (Th,A,a) condition. This follows from the fact that ff{} 1 h](A) is equal to 1 1 h[A]. (Note this {} mapping is the "null mapping", whose domain is empty.)
3. Realize that if A E Domain [ q>], then [ q> ThD (A) would contain a single member. As there are ho non-empty proper subsets of such singleton sets, it is sufficient to use Domain[q>] ~ L-{A}, rather than Domain[q>] ~ L.
4. Consider the set of "almost complete interpretations" IT q> ThD, whose domain includes every symbol of L except A; that is, Domain[q>]=L-{A}. While it may appear that these partial interpretations are sufficient - that one of these would witness any new a - the counterexample below shows that is not the case.

A tableau helps to visualize this definition. The left tableau in Figure 2 corresponds to the theory Th3 +- {A=B} in the language L ={A, B, C}, and the one on the right to Th4 +- Th3 + "A=C". Each row is indexed by a mapping q> and each column by an assignment to A. A tableau position is tagged with a "1" if this assignment of Domain[q>]U{A} is consistent- that is, if there is any full interpretation associated with this position -and a "0" otherwise.

Finding a witness to a sentence's novelty reduces to finding a row, r, in which a "1" is flipped to "0" but which does not vanish -that is, r must retain a "1" in some position. The fifth and sixth rows below (labeled with the "{<C,.E>}" and "{<C,I>}" mappings) each satisfy this property, showing that New PI ( Th3, "A"," A=C"). Notice that none of the top four rows, which correspond to those "almost complete interpretations" has that property, demonstrating the point of Item 4 above. (These rows do form an adequate spanning set, though , as all the other rows can be derived by DRing together appropriate sets of these.)

4 Uses

Even in its current unmechanized form, this definition can be used effectively as an analytic tool with which to understand many existing learning programs. Eventually, we hope to develop a "NewP" predicate or possibly a pair of operational (multivalue) functions: "New a", which generates New PI sentences from a given theory and symbol, and "NewSYM", which returns the symbols for which a given sentence is NewPI' This section lists several ways this definition (and its operationalizations) can be used.

• Analytic Tool. An adequate definition of newness would help us identify the sources (and recipients) of novelty within learning programs. For example, the teacher · provides the ARCH program ( (Winston 75]) with the new facts that enable it to learn. LEX's problem solver and critic are the sources of novelty for the rest of the system ((Mitchell 81]) . AM ( [Lenat 82]) has no clear source of novelty .. This definition may also help us understand the distinction between compositional new terms - such as AM's definition of prime numbers- and other new terms, such as Bacon's use of intrinsic properties ( [Langley 79]) . Finally, it may lead to a definition of learning not based exclusively on performance.
• Learning and Knowledge Acquisition. An adequate (i.e., computable) definition of novelty might suggest ways of learning a topic more effectively. For example, it could focus the learner's effprts on those aspects of the domain where he has the greatest potential for acquiring something new. This information would help a knowledge-base builder decide which concepts need to be better understood, helping him to direct the dialogue. An analysis of a symbol's dependencies (defined above) might then be used to generate appropriate "probe" sentences to help understand this still vague concept.
• Representation. How should a given proposition be indexed? In general each concept should point to all the relevant facts that are about that concept. The most obvious approach, based strictly on lexical inclusion, is inadequate. For example, one would want to index "x + 1 = 0" by "x" and not by"+", whereas "x + y = y + x" should be associated with " + " and not with "x" .

So how does one determine those concepts that a given fact is really about? We claim that "aboutness" is intimately tied to "newness" in the sense that a is about a concept c whenever this a expresses something new about c with respect to the appropriate diminished theory (which excludes g[s] and all of its consequences).

• Linguistics. The basic purpose of comrr.unication is fer the speaker, S, to transmit a set of new facts, usually about some specific topic. To understand this process, we have to know what it means for a fact to be new to H and then how S (and H) can use this meta-fact when constructing (or understanding) the message.

5 Conclusion

While space does not permit an adequate discussion of the all the issues associated with this model of novelty, this paper would be incomplete. if it did not address the following topics, and point the interested reader to the longer paper [Greiner 83].

• Applicability. The New PI relation described above is applicable to any symbol in predicate calculus as well as propositional logic. In particular, the same formalism we saw work for constant symbols works adequately for relation symbols, albeit with an even larger tableau.
• o "Assertional Novelty". The novelty we discussed above, New PI' is "definitional", in that its goal is to specify more precisely the referent of a given symbol. Another source of novelty comes from specifying some attribute of the concept; we label such facts "assertion ally novel". (See [Woods 75].)

These two categories are distinct: Imagine the symbol RDG had been totally determined, in the sense that the set 1Th( "RDG") had but a single member. As such, there is nothing NewPI we can say about RDG. Despite this certainty, you still might not know what his hair color is. That is, Ha1rColor(RDG Brunette) might be true in one interpretation, whereas others might hold that Ha1 rColor(RDG Blond). Clearly Ha1 rColor(RDG Blond) is a NewPI fact about Ha1rColor; however, most people would also want this it to be a new fact about RDG as well that is, NewAssert(Th,"RDG","Ha1rColor(RDG Blond)").

• Intensional, not Extensional. This paper has dealt exclusively with extensional phenomena, where novelty was determined with respect to the extensions of the symbols. Another approach is intensional - based on descriptions.
• Deductively Closed. Probably the most serious criticism of this work is its dependency on a complete deductive system and the requirement that each theory be deductively closed . New-sounding statements can also be used to focus the hearer's attention on some facts he already knew, rather than expose him to new facts. It should be possible to extend this formalism to handle such resource-limited deducibility. Then we could address topics like monotonic novelty and information obsolence.

Each of the issues mentioned above suggests a research task - that of plugging each limitation. The two issues we find most pressing are:

• Finding an equivalent but syntactical formulation of the semantical NewPI relation, in the same manner that Nsyn matched Nsem· We hope this will lead to . one or_ more operational versions, of the types ment1oned m the beginning of Section 4.
• Expanding this NewPI definition to work with deductive systems that are incomplete. (This reiterates the last issue shown above.)

Our basic thesis is that a is a new fact about A, with respect to the theory Th, if, under some set of circumstances, a limits the number of interpretations of A. New PI achieves this by examining every partial interpretation, testing each to see if A loses a possible interpretation in that situation. This "partial interpretation" definition of context is clearly as general as possible. Furthermore, by counterexample, we have shown that this extreme generality is necessary.

Acknowledgments

we would especially like to thank Tom Dielterich for his significant contributions to this work. The following people also contributed: Professor Bruce Buchanan, Dr. Lew Creary, Jim Davidson, Dr. Johan deKieer, Dianne Kanerva,Dr. Jussi Ketonen, Jock Mackinlay, Dr. Robert Moore, Yoram Moses, and Ben Moszkowski. Many useful comments were provided by the reviewers. This basic research was funded by ARPA Contract #MDA903-80·C-0107.