Inference without Chaining

1. The Problem

A serious problem confronting much work in artificial intelligence is that of identifying a limited set of inferences that a program can perform efficiently. The problem is cen­ tral to the design of a knowledge retrieval system. A retriever that accesses a knowledge base should be able to perform cer­ tain useful inferences in order to respond to a query. Since the retrieval process must be guaranteed not only to terminate but to terminate quickly, the set of inferences must be efficient to perform.

An efficient system of limited inference would also be use­ ful for reasoning by default. Many default reasoning systems allow one to jump to a conclusion provided that the conclusion is consistent with what is already known. The problem is that consistency may not be decidable, and, even if it is, it may not be easily decided . One can hardly be said to jump to a conclu­ sion if its consistency must first be established. Rather than throwing all caution to the wind, the agent should perform a limited set of efficient inferences in order to avoid jumping to conclusions that are obviously inconsistent with what is known.

A similar problem arises in reasoning about the beliefs of another agent. We may want to reason that the agent automatically . makes certain inferences- - that if he has certain beliefs then he has other beliefs. So the agent's beliefs are closed under a certain limited set of inferences: but what infer­ ences?

Underlying all these uses of limited inference is the notion of an obvious inference. This notion also pervades linguistic communication. A speaker often makes statements that are slightly stronger, and hence more informative, than the state­ ment that communicates the required information.

Inference without Chaining

Alan M. Frisch

Department of Computer Science University of Illinois 1304 West Springfield Avenue Urbana, IL 61801

Underlying this practice is the assumption that the hearer can :nake the obvious inference that is necessary. For example, in <l'>Jl<,noc to the question "Will John be here?" you may reply "He and Mary will be here late." John and Mary's being here late entails John's being here; this is obvious to you and you know that it is obvious to the listener.

Of course the solution of these problems does not merely involve picking a limited set of inferences; one must first find a criterion or guiding principle . to motivate one's choices. Until recently, little work has been done on identifying sets of infer­ ences and even less on motivating useful criteria for perform­ ing this task. Witness the dissatisfaction that Brachman, Gil­ bert and Levesque (1985) express because this state of affairs has forced them to build a complete (unlimited) inference mechanism into the KRYPTON knowledge representation sys­ tem:

We would no doubt have used a more computa­ tionally tractable inference framework than full first- order logic if an appropriate one were avail­ able... the full first-order resolution mechanism is, in a sense, too powerful for our needs.

This paper introduces the no-chaining restriction and proposes that it be used to limit inference in a systematic, principled way. The consequences of embracing the no­ chaining restriction are then investigated by designing and studying a propositional logic whose inference system does no chaining.

2. The No-Chaining Restriction

Imagine a representation divided into quanta, which I shall call "facts." Then, any inference that combines two or more facts in order to derive another is said to perform chain­ ing. The archetypal form of chaining occurs in applying the rule of modus ponens to infer Q from P and P--+ Q.

The effect of the no-chaining restriction depends criti­ cally on the granularity at which knowledge is quantized. For instance, the no-chaining restriction prohibits inferring Q from PA(P-+Q) only if PA(P-+Q) is quantized into two facts, P and P--+ Q. At one extreme, if the entire representa­ tion is considered to be a single fact , the no- chaining restric­ tion becomes vacuous; there can 't be any chaining because there aren't two facts to be chained together. At the other extreme, if each fact is merely an atomic sentence then nothing new can be inferred; the only atomic sentence entailed by an atomic sentence is the sentence itself.

It is the elimination of modus ponens that motivates the ' . development of the inference system put forward in this paper. In particular, we shall focus on the disjunctive form of modus ponens-the derivation of Q from P/\(..,PVQ). For this to be regarded as a form of chaining, P /\( ..,pyQ) must be divided into two facts: P and -,pyQ. Accordingly, a fact is defined to be a disjunction of literals. 1

Inference without chaining can be thought of as local inference; a given fact can be inferred from a corpus of facts only if it can be inferred from a single fact in the corpus. Hence, whether a target fact is inferable from a corpus of facts can be determined on a purely local basis. This is reminiscent of associative memories, which also operate locally. Each fact in the corpus can be stored with a separate process. A target fact is broadcast to all processes, each of which then deter­ mines if the target fact is inferable from the fact that it has stored. Because no chaining is performed the processes can reach their decisions independently; no communication is required between them.

The elimination of all chaining is a radical approach to limiting inference. In any practical situation that calls for a limited inference system, it is reasonable to expect that it is necessary to perform some prescribed set of efficiently­ performed inferences that require chaining. An inference sys­ tem that performs no chaining forms an excellent basis to which such specialized chaining can be added. This approach of first eliminating all chaining and then introducing special~ ized chaining has been pursued by Frisch (1986) in work that is described later in this paper.

The remainder of this paper closely examines inference without chaining. The following section presents a method of adapting the tools of model theory to the task of formally specifying a limited inference system. Section 4 uses this tech­ nique to specify the most powerful inference system without chaining for propositional logic. In Section 5 the formal specification is then used to prove that the inference system has certain properties, properties that lead directly to the inference algorithm discussed in Section 6. Finally, Section 7 compares this work to a number of related logical systems.

3. An Approach to Specifying Limited Inference

A methodology that has been pursued successfully throughout computer science is that of separating what a pro­ gram computes from how it computes it. On one hand there are descriptions of a program's input/output behavior and on the other descriptions of its internal modules, processes, states and data structures.

This paper concentrates on what an inference system without chaining computes, or, in other words, on what sen­ tences can be inferred without chaining from what sets of sen­ tences. Thus the problem of specifying the inference system comes down to one of specifying an inferability relation, a binary relation that says what is inferable from what without chaining.

The inference system operates in a standard propositional language whose semantics is given by the standard Tarskian model theory, which shall be referred to as T. This model theory yields an entailment relation, written fr , that deter­ mines what can validly be inferred from what. A limited inference system, however, is incomplete; it does not make all valid inferences, only a (proper) subset of them. How then can a limited inference system be specified?

1 Recall that a literal is either an atomic sentence or its nega· tion.

The approach used here for specifying limited inference is to produce another model theory whose entailment relation is weakened 2 in such a way that the inference system is sound and complete with respect to it. In other words, the limited inference system is specified by producing a model theory whose entailment relation is taken to be the inferability rela­ tion for the limited inference system. Model theories are well-suited for use in specifications because they are precise, often have simple definitions, and abstract away from all issues of formal syntactic operations.

Many people initially find this approach quite odd. They are accustomed to thinking of a model theory as specifying what can be concluded validly from what-in some sense, as a competence theory of inference. I suggest that those who are comfortable with this viewpoint consider the weaker model theory as a performance theory of inference. Other people are accustomed to thinking of a model theory as a way of assign­ ing meaning to symbols and are skeptical of producing a new meaning assignment. But I am not. suggesting that the origi­ nal model theory be discarded; on the contrary, it is still a valuable device in the study of meaning. The new model theory can be thought of as providing an additional meaning assignment. If the inference engine is working under this alter­ native meaning then it is complete. Hence, the symbols mean one thing to us and another to the inference engine. According to our theory of meaning the inference engine is incomplete but according to its weaker theory of meaning it is complete.

How can these new, weaker model theories be produced and what is their relationship to the unweakened model theory? To answer the question consider a model theory as laying down a set of constraints on what constitutes a model. or all (mathematical) objects, only those that satisfy the con­ straints qualify as models. A model theory also associates with each model a valuation, a total function from sentences to their truth values. Hence, a model theory constrains the range of valuations that can be. generated. In a standard pro­ positional logic, for example, these constraints ensure that any valuation that assigns two sentences True, also assigns their conjunction True. The entailment relation associated with a model theory is a product solely of the range of valuations that the model theory generates. Relaxing the constraints pro­ duces a new model theory, one that may generate additional valuations. No matter how the constraints are relaxed, the new model theory must have a weaker entailment relation than the original. That is, if fi and f2 are entailment relations and fz, is obtained by relaxing the model theory for fi, then Q 12 fJ implies Q fi fl. To see this, observe that a valuation can serve only · as a counterexample to a claim that one sentence entails another; hence if none of the valuations from the relaxed model theory are counterexamples then certainly none from the original model theory are.

2 One entailment relation is weaker than another if the infer­ ences sanctioned by the first are a subset of those sanctioned by the second.

·· Defining Inferability

The no-chaining inferability relation specified in this sec­ tion is the entailment relation of RP, a model theory obtained by relaxing the Tarskian model theory, T.

Tarskian model theory places no constraints on how a model assigns truth values to the atomi~ formulas of the language; they can be assigned any combination of the two truth values. So we cannot generate additional valuations by giving the atomic: sentences more combinations of the two truth values. This leaves two options: either allow atomic: sen­ tences to be mapped to values other than True and False, or modify the way values are assigned to molecular formulas. This paper pursues the first strategy. Elsewhere (Frisch, 1985) I have specified a nearly identical inference engine using the second strategy.

Examination of why P and -.PvQ T-entails Q provides the insight used to derive the new model theory, RP. Consider this three-step argument that P, ..,py Q fr Q:

1. Assume that P and -.PvQ are both satisfied by a certain model.
2. Since P is satisfied, ..,p isn't.
3. Consequently, if the model is to satisfy -.PvQ, as assumed, it must satisfy Q.

As far as chaining is concerned, step (2) is the crucial one; it connects P and -.PvQ. The validity of the step rests on the assumption that a model satisfies only one of P and -.P-a justified assumption in T where a model assigns each sentence either True or False, but never both. RP relaxes the restric­ tion that the assignments of True and False are exclusive by allowing each sentence to be assigned a non-empty subset of :True, Falsef. Hence, RP has three truth values: iTruef, :False} and [True, False}. We will see that this modification admits models that satisfy both P and ..,p, thus eliminating modus ponens as a sound rule of inference. In comparing RP to T the difference between True and i True J and between False and :False J always will be ignored.

The exclusivity of True and False is built implicitly into the usual semantic equations that determine how T recursively assigns values to molecular formulas. Consider, for example, (1) the semantic equation for disjunction. Here, [.Pll"' is the truth value that model M assigns to formula ,P.

Notice that in these equations the assignment of False is based on the non-assignment of True. Let us now assume that formulas can be assigned a set of values-iTruel and {False} in the Tarskian case-and define the assignment of True and False independently of each other. (1) and (2) can be written equivalently as (3) and (4).

The semantic: equations for the other logical connectives can be rewritten in a similar fashion, or, equivalently, they can be defined in terms of disjunction and negation. For example. define

or, if you prefer,

Figure 1 displays the truth tables for negation, disjunc­ tion and conjunction in this three-valued logic. "T," "F," and "TF" abbreviate the names of the truth values in the obvious way.

It .

Figure 1: Truth Tables for RP

It now should be clear that these semantic equations­ (3), (4), and (5)-can be used to assign values to formulas in RP-models as well as in T-models. It also should be clear that T-models are precisely those RP-models where no atomic sentence is assigned i True, False J. Hence, as one would expect, each three-valued truth table contains the truth table for the two-valued Tarskian logic.

We say that model M satisfies sentence a if, and only if, True E [aD"'; otherwise M falsifies a. As usual, a set of sen­ tP.nces A RP-entails sentence 13 (also written as A fRp .8) iff there is no model that satisfies every sentence of A and falsifies p. In an entailment such as A fRp .3, A is called the antecedent and .8 is called the consequent.

Let us now return to the example that motivated this definition of RP and ask, "Do P and -.PvQ RP-entail Q 1 " The answer is "no", because there are RP-models that satisfy both P and ..,p. For example, consider model .IJ, which assigns ;True, False: toP and :False: to Q. According to the definitions of the connectives, ,l,f assigns :True, False: to both ..,p and -.PvQ. So, M satisfies both P and -.PvQ but falsifies Q, and therefore is a counterexample to the claim that P, -.PVQ fRp Q.

6. Properties of RP

:'>low that RP is defined, this section examines some of its properties. These results lead directly to a decision procedure for RP--entailment (i.e., the limited inference engine), which is discussed in the next section.

The No-Chaining Theorem and the Strength Theorem, which are presented below without proof, 3 together state that RP--entailment is the strongest inferability relation that does no chaining, modulo the method of quantization. (Recall that a fact is a disjunction of literals.)

3 All theorems or this section are proved in Frisch (11186).

No-Chaining Theorem

Let ~ be a set of sentences and a be a fact. Then ~ fRp a iff for some ,P E ~ ,P fRp a.

Strength Theorem

If ,P is a fact and .Pis a sentence then <b fRp tP iff ,P fr 1/J.

We have now established that RP-entailment can be decided on a fact-by-fact basis. However, the elimination of chaining does not necessarily lead to efficient inference since it may still be difficult to infer a single fact from a single fact. The following theorem assures us that this difficulty does not arise.

RP-Dec:iaion Theorem for Facta

For any facts, ,P 1 and <{> 2 , 4> 1 fRp 4> 2 iff either

1. 4> 2 has complementary literals, 4 or
2. the literals occurring in 4> 1 are a subset of those occurring in ,P 2 ·

The two syntactic conditions for RP-entailment can be easily computed. Even if facts are encoded as unordered lists, this decision can be made in O(n log n) time, where n is the sum of the lengths of the facts. This could be reduced further by a better encoding of facts.

Let us now consider some of the logical equivalences of RP. In some multi- valued logics, including RP, there are two similar, though distinct, notions that one could call "logical equivalence." In what follows, two sentences shall be con­ sidered logically equivalent (written =) just in case they have the same truth value in every model. Hence, a formula may be substituted for a logically- equivalent one.

RP-Equivalence Theorem

Formulas that are conjunctions of disjunctions of literals are traditionally said to be in conjunctive normal form (CNF). The conjunctive normal transformation (CNT) is a well- known algorithm for converting any sentence to aT-equivalent CNF sentence. The algorithm proceeds by performing a series of rewrites. Each rewrite replaces a formula with a formula that is RP-equivalent according to the RP-Equivalence Theorem. Hence, we have the following:

Conjunetive-N ormal-Transformation Theorem

Every sentence is RP-equivalent to its conjunctive normal transform.

4 An atomic sentence and its negation are said to be comple­ mentary. For example, P and ....,p are complementary literals.

8. Deciding RP-Entailment

It is now simple to see how RP-entailment can be decided. The Fact Decision Theorem for RP provides a method for deciding whether or not a single fact is inferable from a single fact. The No-Chaining Theorem extends the method to the case where the antecedent contains any finite number of facts. The semantics of conjunction, which says that an RP- model satisfies a conjunction iff it satisfies each conjunct, provides for the case where the antecedent contains conjunctions of facts and the consequent is a conjunction of facts. Finally, the CNT Theorem tells us that the CNT can be used to replace any inference problem with an equivalent one where the sentences are in CNF.

The algorithm operates by reducing all inference prob­ lems to trivial ones, as just outlined. Rather than present the algorithm, I present the trace of its execution on a sample problem. Each step of the execution is justified by a theorem of the preceding section, thus proving the correctness of the computed result.

Referring to Figure 2, consider the problem of deciding whether the entailment at node (1) holds. By the .Conjunctive Normal Transform Theorem, (1) holds iff (2) does. By the semantics of conjunction as given in equation (5), Pt\Q is satisfied by precisely the same models that satisfy both p and Q. Therefore the entailment at node (2) holds iff that at node (3) does. By the same argument, the entailment at (3) ·holds iff those at both (4) and (5) do. By the RP-Decision Theorem for Facts the entailment at {4) holds since its consequent has com­ plementary literals. By the No-Chaining Theorem node (5) holds iff either (6) or (7) does. Finally, by the RP-Decision Theorem for Facts the entailment at (6) holds since the literals in its antecedent are a subset of those in its consequent (i.e., :Pi~ : P ,R ~). So, the algorithm concludes that the entail­ ment at (1) holds and we have justification for believing that this conclusion is correct.

7. Survey of Related Work

In this section I briefly survey and compare a number of logics that disallow chaining as well as some that allow only selected forms of chaining. In addition to my own work, I review the work of Belnap, Levesque, Patel-Schneider and Lakemeyer. though none of these authors have presented t heir work from the standpoint of the elimination of chaining.

Belnap {1975; 1977) used the idea of a multi-valued logic whose truth values are subsets of l True, Falsef . His logic, which I shall call "B," differs from RP in that it admits the empty set as a fourth truth value. B uses the same semantic rules as RP to assign truth values to molecular sentences. Thus, just as the T-models are a proper subset of the RP­ models, the RP-models are a proper subset of the B- models. Consequently, B-entailment is weaker than RP-entailment. Clearly then, B is also a logic without chaining, but it is not the strongest such logic.

Let us briefly consider the inferences sanctioned by RP but not by B. Consider a model M in which the atomic sen­ tence P is assigned l :. Then ff-.PflM =:: and ffPv-.PflM =:: and therefore Pv-.P is not a tautology. Indeed, there are no tautologies in B. The model that assigns l l to every atomic formula also assigns ·l l to every molecular formula, ( l l· is a fixed point of all the logical connectives) and therefore fails to satisfy any formula.

This observation provides the insight necessary to relate the inferences sanctioned by B to those sanctioned by RP. Let t/J be an arbitrary set of formulas containing only the proposi­ tion letters P 11 ··· , P ~ and let ¢> be the sentence (P 1 v-.PtJA · · · A(P~ v-.P.). Then, a sentence is RP-entailed by t/J iff it is B-entailed by t/JU¢· This is the case because the B-models that satisfy tjJ are precisely the RP-models.

There has been considerable recent activity in extending both RP and B in various directions. Though each of the extensions discussed below was made to only one of the two logics. they apply equally well to both logics.

Levesque (1984) has proposed a propositional modal logic of explicit belief in which the possible worlds are B-models rather than the usual T- models. As a result, we are commit­ ted not to the claim that agents believe all Tarskian conse­ quences of their beliefs. but to the weaker claim that they believe all B-con, equences of their beliefs. Lakemeyer (1986) extended Levesque's propositional. logic of explicit belief to a first order logic.

The introduction of quantifiers into B under the standard interpretation results in an undecidable entailment relation. Patel-Schneider {1985) introduced a weaker, though more complex, model theory that agrees with B on propositional entailment but remains decidable when quantifiers are intro­ duced. It may appear surprising that the introduction of stan­ dard quantification into B, and also into RP, yields an unde­ cidable logic; after all, these logics allow no chaining. Frisch (1986) has shown how this introduction of quantifiers allows chaining to subtly slip in through the back door. He intro­ duced a property, called the Strong Herbrand Property, which guarantees that a propositional logic that allows no chaining will not allow any chaining when quantifiers are introduced.

As previously claimed, an inference system without chaining forms an excellent base to which certain specialized lorms of chaining can be integrated. Frisch (1981i) has demon­ strated this by extending a first- order version of RP with the ability to chain as necessary to reason completely with taxo­ nomic information, though the system remains incapable of doing any other form 'Of chaining. For example, the system can chain together "Clyde is an elephant," "All elephants are mammals" and "All mammals are warmblooded" in order to conclude that "Clyde is warmblooded." The key to this system's ability to chain lies in treating "elephant" and "mam­ mal" as special taxonomic predicates, which are distinct from the ordinary predicates. An atomic formula formed with a taxonomic predicate can only be assigned True or False by a model, never ~ True, False ~ . Thus, taxonomic information is given a Tarskian interpretation, which sanctions complete rea­ soning, while all other information is given a weakened 3valued interpretation, which disallows all chaining.

8. Conclusion

The problem of specifying, constructing, and understand­ ing specialized, limited inference systems arises in many areas of AI. The development of inference systems that do no chain­ ing is an important first step to solving t his problem. In this respect the inference system presented in this paper is of par­ ticular interest because it is the strongest such system that does no chaining, modulo the quantization method used. Furthermore, the model- theoretic specification technique employed here may prove to be an important tool in the study of limited inference; it certainly proved invaluable here in specifying the inference engine, proving that it had certain properties, and comparing it to other systems.

Acknowledgements

I thank Fran Evelyn for her assistance in editing and printing this paper .