17.4.4 Inference

One of the most important desiderata given in Section 17.1 for a meaning representation language is that it should support inference—the ability to add valid new propositions to a knowledge base, or to determine the truth of propositions not explicitly contained within a knowledge base. This section briefly discusses $ \mathbf{modus ponens} $, the most important inference method provided by FOPC. Applications of modus ponens will be discussed in Ch. 21.

Modus ponens is a familiar form of inference that corresponds to what is informally known as if-then reasoning. We can abstractly define modus ponens as follows, where $ \alpha $ and $ \beta $ should be taken as FOPC formulas:

$$ \begin{array}{c}a\\\alpha\Rightarrow\beta\\\beta\end{array} $$

In general, schemas like this indicate that the formula below the line can be inferred from the formulas above the line by some form of inference. Modus ponens simply states that if the left-hand side of an implication rule is present in the knowledge

base, then the right-hand side of the rule can be inferred. In the following discussions, we will refer to the left-hand side of an implication as the antecedent, and the right-hand side as the consequent.

As an example of a typical use of modus ponens, consider the following example, which uses a rule from the last section:

$$ \frac{\underset{\forall xVegetarianRestaurant(x)\Rightarrow Serves(x,VegetarianFood)}{VegetarianRestaurant(Rudys)}}{Serves(Rudys,VegetarianFood)} $$

Here, the formula VegetarianRestaurant(Rudys) matches the antecedent of the rule, thus allowing us to use modus ponens to conclude Serves(Rudys, VegetarianFood).

Modus ponens is typically put to practical use in one of two ways: forward chaining and backward chaining. In forward chaining systems, modus ponens is used in precisely the manner just described. As individual facts are added to the knowledge base, modus ponens is used to fire all applicable implication rules. In this kind of arrangement, as soon as a new fact is added to the knowledge base, all applicable implication rules are found and applied, each resulting in the addition new facts to the knowledge base. These new propositions in turn can be used to fire implication rules applicable to them. The process continues until no further facts can be deduced.

The forward chaining approach has the advantage that facts will be present in the knowledge base when needed, since in a sense all inference is performed in advance. This can substantially reduce the time needed to answer subsequent queries since they should all amount to simple lookups. The disadvantage of this approach is that facts may be inferred and stored that will never be needed. Production systems, which are heavily used in cognitive modeling work, are forward chaining inference systems augmented with additional control knowledge that governs which rules are to be fired.

In backward chaining, modus ponens is run in reverse to prove specific propositions, called queries. The first step is to see if the query formula is true by determining if it is present in the knowledge base. If it is not, then the next step is to search for applicable implication rules present in the knowledge base. An applicable rule is one where the consequent of the rule matches the query formula. If there are any such rules, then the query can be proved if the antecedent of any one them can be shown to be true. Not surprisingly, this can be performed recursively by backward chaining on the antecedent as a new query. The Prolog programming language is a backward chaining system that implements this strategy.

To see how this works, let's assume that we have been asked to verify the truth of the proposition Serves(Rudys, VegetarianFood), assuming the facts given above the line in (17.25). Since it is not present in the knowledge base, a search for an applicable rule is initiated that results in the rule given above. After substituting, the constant Rudys for the variable x, our next task is to prove the antecedent of the rule, VegetarianRestaurant(Rudys), which of course is one of the facts we are given.

Note that it is critical to distinguish between reasoning via backward chaining from queries to known facts, and reasoning backwards from known consequences to unknown antecedents. To be specific, by reasoning backwards we mean that if the consequent of a rule is known to be true, we assume that the antecedent will be as well. For example, let's assume that we know that Serves(Rudys, VegetarianFood) is true. Since this fact matches the consequent of our rule, we might reason backwards to the conclusion that VegetarianRestaurant(Rudys).

While backward chaining is a sound method of reasoning, reasoning backwards is an invalid, though frequently useful, form of plausible reasoning. Plausible reasoning from consequences to antecedents is known as abduction, and as we will see in Ch. 21 is often useful in accounting for many of the inferences people make while analyzing extended discourses.

While forward and backward reasoning are sound, neither is complete. This means that there are valid inferences that can not be found by systems using these methods alone. Fortunately, there is an alternative inference technique called resolution that is sound and complete. Unfortunately, inference systems based on resolution are far more computationally expensive than forward or backward chaining systems. In practice, therefore, most systems use some form of chaining, and place a burden on knowledge base developers to encode the knowledge in a fashion that permits the necessary inferences to be drawn.

17.5 SOME LINGUISTICALLY RELEVANT CONCEPTS

Entire lives have been spent studying the representation of various aspects of human knowledge. These efforts have ranged from tightly focused efforts to represent individual domains such as time, to monumental efforts to encode all of our commonsense knowledge of the world (Lenat and Guha, 1991). Our focus here is considerably more modest. This section provides a brief overview of the representation of a few important topics that have clear implications for language processing. Specifically, the following sections provide introductions to the meaning representations of categories, events, time, and beliefs.