Nonmonotonic Reasoning

notes by: Eyal Amir January 29, 1996

This summary tries to combine [Reiter 87] and [Ginsberg 94]

1 Introduction & Motivation

Reiter mentions several Reasoning patterns required for an Artificial “artifact”. These are Probabilistic Reasoning, Fuzzy Reasoning, Inductive Reasoning, Deductive Reasoning, and Nonmonotonic Reasoning.

There are several motivations mentioned in Reiter’s paper, for using Nonmonotonic Reasoning.

• Normally, A holds should be formalized (commonsense, jumping to conclusions).

• Databases - CWA(e.g., air travel).

• Diagnosis from First Principles (e.g., heater, MYCIN).

• Prototypes, Natural Kinds, and Frames (prototypical bird).

• The Frame Problem. He then emphasises formalizing and some problems issued with it:

• We need to formalize what do we mean by Normally, A holds. – Assume A by default.

– Typically A holds.

– In the absence of information to the contrary, assume A.

– Nothing is known to be inconsistent with A.

• The inference can be complicated. E.g., two default assumptions can conflict. E.g., the Nixon Example.

• We need a theory of Truth Maintenance.

• Typicality is not necessary transitive (Dropouts → adults → employed).

• The ’Problems’:

– The Frame Problem[McCarthy 69] - How to infer that nothing changes unless it should, without mentioning Frame Axioms explicitly.

– The Qualification Problem[McCarthy 77] - What things to check

in order to infer that something should happen. He finally mentions that Classical Logic is inadequate. Two reasons for

that:

1. Representation - size and generation.

2. Monotonicity.

3. Practice.

4. Flexibility.

2 Negation as Failure & the CWA (The Closed

World Assumption)

2.1 Negation as Failure (or Failure as Negation)

Negation as Failure is the rule of inference “From failure of G infer ¬G”. It identifies Procedural Negation with logical one. It is used in PROLOG, and is majorly an implementation of the CWA.

2.2 Reiter’s notion of the CWA

Definition 2.1 ([Reiter 78]) Let DB be a first-order Database.

Closure(DB) = DB∪{¬P(t) | DB |̸= P(t), tn-tuple of atomic (ground) terms}

Under the CWA, queries are evaluated with respect to Closure(DB) rather than DB itself.

2.2.1 Problems

DB Closure may be inconsistent. E.g., DB = {P ∨Q}. Even for nondeductive DBs Reiter’s notion yields incorrect results in the presence of so-called null values.

Nevertheless Reiter Showed that for Horn Databases, Closure preserves consistency.

2.3 Clark’s notion of the CWA

A different notion of CWA was proposed by Clark. His CWA takes Prolog sentences of the form A → B, and assumes that these sufficient conditions are also necessary, i.e., reverse the implication.

2.3.1 Problems

• Lacks generality. It is defined only for Prolog-like Databases (universally quantified formulas).

• Each clause must be about some predicate (and not an arbitrary formula).

• Sensitive to the syntactic form of the DB.

3 Consistency-Based Approaches

These approaches interpret “In the absence of information to the contrary, assume A” as “If A can be consistently assumed, then assume it.

3.1 Nonmonotonic Logic

Proposed by McDermott & Doyle. Uses a modal operator M. MA means “A is consistent”. That means that a formula involving M actually refers to itself because it is also a part of the database to which it refers.

Definition 3.1 If A is a nonmonotonic theory, then T is a Fixed Point of A if

T = T h(A ∪ {Mw|¬w ∉ T })

Notice that there might be separate contradictory Fixed point theories. Thus McDermott & Doyle defined their theorems of a nonmonotonic knowledge base to be the intersection of all its fixed points.

3.1.1 Problems

1. Consistency Requirement implies that neither the fixed points, nor the theorems are recursively enumerable.

2. Serious difficulties with the semantics. E.g., {MC, ¬C} is consistent.

3.2 Default Logic

Proposed by Ray Reiter. Differs from the nonmonotonic logic of McDermott & Doyle in that default statements are rules of inference rather than statements in the language. Defaults are represented as

\frac{α(x) : β(x)}{γ(x)}

which comes for “If α(x) holds and β(x) can be consistently assumed, then you can infer γ(x).”

The approach is to begin with a set of 1st order sentences. Default rules act as mappings from this incomplete theory to a more complete extension of the theory. As in McDermott & Doyle’s approach, the extensions are defined by a fixed-point construction.

Definition 3.2 A Default Theory is a pair (D, W) where D is a set of closed default rules and W a set of 1st order sentences. E is an extension of (D, W) iff W ⊂ E, E is closed under logical consequence and can not be expanded by use of a default rule.

3.2.1 Advantages

There is a “proof theory” in the case of default rules that are normal, i.e., of the form

\frac{α(x) : β(x)}{β(x)}

That “proof theory” actually says that Given a set of 1st order sentences W, a set of normal defaults D, and a first order sentence β, the β is in some extension of W wrt the default D iff the “proof theory” sanctions this.

3.2.2 Problems

The default logic’s extensions are not recursively enumerable. Moreover, defaults can not be reasoned about within the logic.

3.2.3 Applications

Applied to Inheritance hierarchies with exceptions, presuppositions in natural language, Diagnostic-reasoning, and the theory of speech acts.

4 Approaches Based Upon Minimal Models

These approaches treats as theorems those sentences true in all suitably distinguished models of a logical theory.

4.1 Circumscription

Definition 4.1 ([McCarthy 80],[McCarthy 86]) The circumscription of P in A(P; Z) with variable Z is defined to be the (second-order) sentence

A(P; Z) ∧ ∀P′, Z′ ¬(A(P′, Z′) ∧ P′ < P)

That actually means that a model satisfying the above formula will be minimal in P, even in the price of changing Z.

The circumscription formalization can be extended as follows:

1. Parallel Circumscription.

2. Prioritized Circumscription (two forms).

4.1.1 Problems 1. Second Order Formula (not in general recursively enumerable)

2. It can happen that the circumscription formula is not satisfiable. 4.1.2 Results Vladimir Lifschitz has found many special cases to be reducible to 1st order logic, and thus easier to handle:

• Predicate Completion

• Elimination of Varied Constants

• Positive and Negative Formulae

• Confirming Conjectures about circumscription

• Definite Formulae

Also, most formalizations proposed so far were shown to be implementable (for some restricted classes) by Circumscription(e.g., CWA, PROLOG, Normal Default Logic, inheritance hierarchies) with special predicates such as ’Ab’.

4.2 Minimality and the Frame Problem

• Situation Calculus

• Yale Shooting Problem

Two solutions were proposed (till 1987) for the Yale shooting problem. One using Different Circumscription than used by Hanks & McDermott (Lifschitz), and the other uses explicit providing of time.

5 Epistemic Approaches

The intuition here is that “Typically, birds fly” should be read “If x is a bird, and we don’t believe [know] that x can not fly, then x can fly”.

5.1 Autoepistemic Logic

Proposed by Moore. He provides a reconstruction of the logic proposed by McDermott & Doyle based on Belief rather than Consistency. He proposed a Modal Operator B corresponding (roughly) to ¬M¬.

Definition 5.1 Given some set of premises A, a set T of formulas is a stable expansion of A when

T = T h(A ∪ {Bw|w ∈ T } ∪ {¬Bw|w ∉ T })

This definition corresponds to McDermott & Doyle’s Fixed Point.

5.1.1 Problems

There are some extensions that are not desirable (e.g., the extensions of {Bp ⊃ p}).

5.1.2 Konolige’s Proposal

Konolige proposed using a ’minimal’ extension. He called these minimal stable extensions, strongly grounded expansions. These kind of expansions solve the problem mentioned above. They were also proved by konolige to be equivalent in expressiveness to default logic.

5.2 Self-Knowledge and ignorance

Levesque(1982,1984) concept of a Knowledge Base’s self knowledge includes knowledge about lack of knowledge. Its idea and query language actually say:

KB ⊧ φ ⇒ “φ”
KB ⊧ ¬φ ⇒ “¬φ”
KB |̸= φ ∧ KB |̸= ¬φ ⇒ “unknown”

In Levesque’s Language, ASK is nonmonotonic (question about a belief will be revised on the encounter with new data). He also shows how to translate Default Reasoning into his language with the modal operator K for ’know’.

∀xBird(x) ∧ ¬K¬F ly(x) ⊃ F ly(x)

He then shows how to translate these non-1st-order-logic formulas (in a noneffective way) into sentences of 1st order logic, to be incorporated into the KB.

5.2.1 Advantages

• Semantically precise.

• Well motivated.

• Allows one to ask the database about its state of knowledge.

• The ASK operator can be realized in terms of 1st order theoremhood (even though we require an oracle for that).

5.2.2 Disadvantages

• Because defaults are assimilated into the KB as 1st order formulas, they lose their character as defaults, and hence can not be reasoned about within the logic.

• Inconsistencies can arrise, even in situation where other formalisms did not encounter them (e.g., Bird(T weety), Bird(Opus), ¬F ly(T weety)∨ ¬F ly(Opus)).

6 Conditional Logics

These try to emphasize on the ’meaning’ rather than the ’logic’. E.g., the “If a match were to be struck, then it would light”.

These have the inherent flaw of Monotonicity.

7 Final Remarks

Definition 7.1 (McDermott) A Cautious nonmonotonic reasoning, accepts a result only if it follows in all of the associated extensions. A brave approach sanctions any conclusion that is valid in any of the extensions.

Circumscription is cautious. Reiter’s default logic is brave.

8 Current Research

Focuses on the following issues:

• Circumscription

• Default Logics

• Inheritance Networks with abnormalities.

• Logics of Context.

• Concurrency.

• Prioritized defaults/circumscription.

• Commonsense reasoning.

• Situation Calculus.

• Abnormality theories.

• Reasoning about action.

9 Conclusions

The most widely spread methods today are Circumscription, Default Reasoning and Inheritance Networks.

Formal approaches to nonmonotonic inference are in general non-semi-decidable. Circumscription was proved to be reducible to first order axioms in some cases, and is therefore semi-decidable in these cases.

As a consequence of that, any implementation of Nonmonotonic Reasoning is bound to be slow (because of the need for consistency checkings), and will make mistakes from time to time (because of the non-semi-decidability).

Nonmonotonic inferences also tend to create multiple competing models, and thus a nonmonotonic DB may admit multiple sets of competing conclusions.

References

[Reiter 87] Ray Reiter, Nonmonotonic Reasoning, Ann. Rev. Comput. Sci. 1987.2:147-86.

[Reiter 78] Ray Reiter, On closed world data bases, in Gallaire & Minker ed. Logic and Data Bases, 1978, 55-76.

[Ginsberg 94] Matt L. Ginsberg, AI and Nonmonotonic Reasoning, Handbook of Logic in AI and Logic Programming, Vol 3, 1-33, 1994.

[McCarthy 69] John McCarthy, Some Philosophical Problems from the Stanpoint of Artificial Intelligence, in John McCarthy, Formalizing Common Sense, 1990, 21-63.

[McCarthy 77] John McCarthy, Epistemological Problems of Artificial Intelligence, in John McCarthy, Formalizing Common Sense, 1990, 77-92.

[McCarthy 80] John McCarthy, Circumscription - a form of Nonmonotonic Reasoning, in John McCarthy, Formalizing Common Sense, 1990, 142-157.

[McCarthy 86] John McCarthy, Applications of Circumscription to Formalizing Common Sense Knowledge, in John McCarthy, Formalizing Common Sense, 1990, 198-225.

This is /u/eyal/ongo/quals/nmo.tex.