Default Reasoning
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Default Reasoning as PDF for free.
More details
- Words: 1,815
- Pages: 20
1
Default Reasoning • Defaults are statements containing words “normally, typically, as a rule”. • A large part of our education seems to consists of learning various defaults, their exceptions, and the skill of reasoning with them. • Defaults do not occur in the language of mathematics, and therefore were not studied by classical mathematical logic. They however play very important role in everyday, commonsense reasoning, and presented a considerable challenge to AI researchers.
Texas Tech University
Knowledge Representation Group
2
Example: Family Problems Let us go back to the family example. Suppose you are Sam’s teacher and you strongly believe that to pass the class Sam needs some extra help.
You convey this information to
Sam’s father, John, and expect some actions on his part.
Your reasoning probably goes
along these lines: John is Sam’s parent. NORMALLY, parents care about their children. Therefore John cares about Sam and will help him with his study. The second statement is a typical example of a default. Texas Tech University
Knowledge Representation Group
3
About Caring To model this reasoning we introduce relation cares(X, Y ) — X cares for Y . Your first inclination may be to ignore the word normally and simply expand program f ather(john, sam). mother(mary, sam). parent(X, Y ) : − f ather(X, Y ). parent(X, Y ) : − mother(X, Y ). child(X, Y ) : − parent(Y, X). by new rule (r1) cares(X, Y ) : −parent(X, Y ). The new program derives cares(john, sam). Texas Tech University
Knowledge Representation Group
4
About Caring — Non-Monotonicity Assume now that in addition to the default 1.
“normally parents care about their chil-
dren” you learn that 2. “John is an exception to this rule. He does not care about his children.” In everyday reasoning this new information does not cause contradiction. We simply withdraw our previous conclusion, cares(john, sam), and replace it by the new one, ¬cares(john, sam). Reasoning which allows removal of previously achieved conclusions when new information becomes available is called NON-MONOTONIC. Texas Tech University
Knowledge Representation Group
5
Representing Defaults in A-Prolog Classical mathematical logic is monotonic — once proven, a theorem stays proven for ever. To formalize non-monotonic reasoning AI researchers had to develop a very different type of logic. A default ’Normally elements of class C have property P ’ is often represented by a rule: p(X) ← c(X), not d(X), not ¬p(X). d is the default’s name (given by the program designer). d(X) says that default d is not applicable to X; not ¬p(X) is read as ’p(X) MAY be true’. Texas Tech University
Knowledge Representation Group
6
Example: Caring Parents The same technique can be used if X is a list of variables. For instance, the default “normally parents care about their children” will be represented by the rule (d1): cares(X, Y ) ← parent(X, Y ), not d1(X, Y ), not ¬cares(X, Y ). Let us now compare ’strict’ caring rule (r1) used in the beginning with the new rule (d1). Let F be a family knowledge base including the definition of parents, P1 = F ∪ (r1) and P2 = F ∪ (d1). You can check that both programs entail cares(john, sam).
Texas Tech University
Knowledge Representation Group
7
Uncaring John Let us see what happens when we learn that John does not care about his children. There is no way to incorporate this information into P1 — the program will become inconsistent. We can however add this new knowledge to P2 using the rule: ¬cares(john, X) ← child(X, john). The new program is consistent and entails ¬cares(john, sam), cares(mary, sam). Note that the new information about John forced the program to withdraw one of its previous conclusions and replace it by the new one. Texas Tech University
Knowledge Representation Group
8
Exceptions to Defaults in A-Prolog Let d be a default “Normally elements of c have property p”. (d) may have two types of exceptions: ’strong’ which refute the default’s conclusion, and ’weak’ which render the default inapplicable. A weak exception e(X) to d is encoded by a so called CANCELLATION axiom d(X) ← not ¬e(X). which says that d is not applicable to X if X MAY BE a weak exception to d. If e is a strong exception we need one more rule, ¬p(X) ← e(X) which will allow us to defeat d’s conclusion. Texas Tech University
Knowledge Representation Group
9
Weak Exception - an Example To illustrate the notion of weak exception let us emulate a cautious reasoner who does not want to apply default (d1) to people whose spouses do not care about their children. Such a reasoner will prefer not to make any judgment on Mary’s relation to Sam. This can be achieved by a rule: d1(P 1, C) ← parent(P 1, C), parent(P 2, C), ¬cares(P 2, C). New program answers no to query cares(john, sam) and maybe to query cares(mary, sam).
Texas Tech University
Knowledge Representation Group
10
Example: Strong Exception Uncaring John serves as an example of strong exception to (d1). According to our general methodology the fact that he does not care for his children is translated into A-Prolog by the rules: ¬cares(john, X) ← parent(john, X). d1(john, X) ← not ¬parent(john, X)). Notice however that the second rule is useless and can be safely removed from the program. (Indeed if John is a parent of X then the first rule applies and defeats the default. If no information about parent(john, x) is available the default is not applicable anyway).
Texas Tech University
Knowledge Representation Group
11
More about Uncaring Parents To better understand the need for the cancellation axioms let us consider another strong exception to the “caring parents” default. Assume the existence of a mythical country, u, whose inhabitants do not care for their children. This exception to default d1 is represented by rules ¬cares(P, X) ← parent(P, X), born in(P, u). d1(P, X)
← not ¬born in(P, u)).
Now consider an extension of our family database which contains information about national origin of most (but not all) recorded people.
Texas Tech University
Knowledge Representation Group
12
Assume, for instance, that according to our records Pit and Kathy are the father and mother of Jim, Kathy was born in Moldova, but the national origin of Pit is unknown. He could have been born in u. It is easy to see that the queries ?cares(kathy, jim) and ?cares(pit, jim) are correctly answered by yes and unknown respectively. If later we learn that Jim is indeed from u then the second answer will be replaced by the definite no.
Texas Tech University
Knowledge Representation Group
13
Mixing Exceptions — Cowardly Students Let us consider an example which has both, weak and strong exceptions. We are given • two classes of objects, student and dept containing names of all students and departments of the domain. • a (possibly incomplete) list L in(john, engl). in(mary, cs). in(bob, cs). in(pat, math). which relates students to their unique majors. • the following default with exceptions: Normally, students are afraid of math. A brave student Mary and the math majors are not. Those in CS may or may not be afraid. Texas Tech University
Knowledge Representation Group
14
Cowardly Students (continued) Let us represent the above information in AProlog. To define negative information for relations student and dept we can use the CWA. But since L maybe incomplete we need to find some other way to deal with negative information about in. The rule ¬in(S, D1) ← in(S, D2), D1 6= D2. does that by exploiting uniqueness of majors. The resulting program entails ¬in(mary, engl), etc.
Texas Tech University
Knowledge Representation Group
15
Cowardly Students (continued) The default is translated by the rule: af raid(S, math) ← student(S), not d(S), not ¬af raid(S, math). The first exception can be represented as: d(mary).
¬af raid(mary, math).
To represent weak exception in(S, cs) and strong one, in(S, math), we write: d(S) ← student(S), not ¬in(S, cs). d(S) ← student(S), not ¬in(S, math). ¬af raid(S, math) ← student(S), in(S, math). Texas Tech University
Knowledge Representation Group
16
Cowardly Students (continued) (a) Informally ’tracing’ the rules of the program check if the following answers to queries are correct: ? af raid(john, math)
Yes
? af raid(mary, math)
No
? af raid(pat, math)
No
? af raid(bob, math)
Unknown
(b) Use one of A-Prolog inference engines to answer these queries. (c) Will dropping the statement d(mary) from the program change the program’s definition of relation af raid? What about dropping the cancellation rule for math students? Texas Tech University
Knowledge Representation Group
17
Important special case The above representation of defaults and exceptions is rather general. Sometimes it can be substantially simplified. Here is an example: Let c0 be a collection of weak exceptions to default d ’Elements of c normally have property p’. If the reasoner has a complete knowledge of c0 than the cancellation axiom for d is d(X) ← c0(X). If c0 is a completely described collection of strong exceptions no cancellation axiom for c0 is needed.
Texas Tech University
Knowledge Representation Group
18
Incompleteness in Databases Consider a database table representing a tentative summer schedule of a CS department. Professor Course mike
pascal
john
c
staff
lisp
Here ’staff ’ is a special constant (called Null value) which stands for an unknown professor. It expresses the fact that Lisp will be taught by SOME professor (possibly different from Mike and John). To represent this information we introduce a relation t(P, C) which says that professor P teaches a course C. We also assume that we are given complete collections of professors and courses. Texas Tech University
Knowledge Representation Group
19
Incompleteness in Databases The positive information from the table can be represented by a collection of facts: t(mike, pascal). t(john, c). t(staf f, lisp). To represent negative information we use default d: Normally, P teaches C only if this is listed in the schedule. Notice that d is not applicable to Lisp (or any other course taught by ’staff ’). This can be represented as: ¬t(P, C) ← prof (P ), course(C), not d(P, C), not t(P, C). d(P, C) ← t(staf f, C). Check that the resulting program Π0 program produces correct answers (N o and U nknown) to queries ?t(mike, c) and ?t(mike, lisp). Texas Tech University
Knowledge Representation Group
20
Incompleteness in Databases Now consider a different type of incompleteness in database tables. Professor
Course
mike
pascal
john
c
{mike,john} prolog staff
lisp
Here {mike,john} represents the second type of nulls – “value unknown but one of the finite set of values”. To represent this information we simply expand Π0 by t(mike, prolog) or t(john, prolog). Π1’s answers to queries ?t(mike, c), ?t(mike, prolog) and ?t(mike, prolog) ∧ t(john, prolog) are N o, U nknown, and N o respectively. Texas Tech University
Knowledge Representation Group
Default Reasoning • Defaults are statements containing words “normally, typically, as a rule”. • A large part of our education seems to consists of learning various defaults, their exceptions, and the skill of reasoning with them. • Defaults do not occur in the language of mathematics, and therefore were not studied by classical mathematical logic. They however play very important role in everyday, commonsense reasoning, and presented a considerable challenge to AI researchers.
Texas Tech University
Knowledge Representation Group
2
Example: Family Problems Let us go back to the family example. Suppose you are Sam’s teacher and you strongly believe that to pass the class Sam needs some extra help.
You convey this information to
Sam’s father, John, and expect some actions on his part.
Your reasoning probably goes
along these lines: John is Sam’s parent. NORMALLY, parents care about their children. Therefore John cares about Sam and will help him with his study. The second statement is a typical example of a default. Texas Tech University
Knowledge Representation Group
3
About Caring To model this reasoning we introduce relation cares(X, Y ) — X cares for Y . Your first inclination may be to ignore the word normally and simply expand program f ather(john, sam). mother(mary, sam). parent(X, Y ) : − f ather(X, Y ). parent(X, Y ) : − mother(X, Y ). child(X, Y ) : − parent(Y, X). by new rule (r1) cares(X, Y ) : −parent(X, Y ). The new program derives cares(john, sam). Texas Tech University
Knowledge Representation Group
4
About Caring — Non-Monotonicity Assume now that in addition to the default 1.
“normally parents care about their chil-
dren” you learn that 2. “John is an exception to this rule. He does not care about his children.” In everyday reasoning this new information does not cause contradiction. We simply withdraw our previous conclusion, cares(john, sam), and replace it by the new one, ¬cares(john, sam). Reasoning which allows removal of previously achieved conclusions when new information becomes available is called NON-MONOTONIC. Texas Tech University
Knowledge Representation Group
5
Representing Defaults in A-Prolog Classical mathematical logic is monotonic — once proven, a theorem stays proven for ever. To formalize non-monotonic reasoning AI researchers had to develop a very different type of logic. A default ’Normally elements of class C have property P ’ is often represented by a rule: p(X) ← c(X), not d(X), not ¬p(X). d is the default’s name (given by the program designer). d(X) says that default d is not applicable to X; not ¬p(X) is read as ’p(X) MAY be true’. Texas Tech University
Knowledge Representation Group
6
Example: Caring Parents The same technique can be used if X is a list of variables. For instance, the default “normally parents care about their children” will be represented by the rule (d1): cares(X, Y ) ← parent(X, Y ), not d1(X, Y ), not ¬cares(X, Y ). Let us now compare ’strict’ caring rule (r1) used in the beginning with the new rule (d1). Let F be a family knowledge base including the definition of parents, P1 = F ∪ (r1) and P2 = F ∪ (d1). You can check that both programs entail cares(john, sam).
Texas Tech University
Knowledge Representation Group
7
Uncaring John Let us see what happens when we learn that John does not care about his children. There is no way to incorporate this information into P1 — the program will become inconsistent. We can however add this new knowledge to P2 using the rule: ¬cares(john, X) ← child(X, john). The new program is consistent and entails ¬cares(john, sam), cares(mary, sam). Note that the new information about John forced the program to withdraw one of its previous conclusions and replace it by the new one. Texas Tech University
Knowledge Representation Group
8
Exceptions to Defaults in A-Prolog Let d be a default “Normally elements of c have property p”. (d) may have two types of exceptions: ’strong’ which refute the default’s conclusion, and ’weak’ which render the default inapplicable. A weak exception e(X) to d is encoded by a so called CANCELLATION axiom d(X) ← not ¬e(X). which says that d is not applicable to X if X MAY BE a weak exception to d. If e is a strong exception we need one more rule, ¬p(X) ← e(X) which will allow us to defeat d’s conclusion. Texas Tech University
Knowledge Representation Group
9
Weak Exception - an Example To illustrate the notion of weak exception let us emulate a cautious reasoner who does not want to apply default (d1) to people whose spouses do not care about their children. Such a reasoner will prefer not to make any judgment on Mary’s relation to Sam. This can be achieved by a rule: d1(P 1, C) ← parent(P 1, C), parent(P 2, C), ¬cares(P 2, C). New program answers no to query cares(john, sam) and maybe to query cares(mary, sam).
Texas Tech University
Knowledge Representation Group
10
Example: Strong Exception Uncaring John serves as an example of strong exception to (d1). According to our general methodology the fact that he does not care for his children is translated into A-Prolog by the rules: ¬cares(john, X) ← parent(john, X). d1(john, X) ← not ¬parent(john, X)). Notice however that the second rule is useless and can be safely removed from the program. (Indeed if John is a parent of X then the first rule applies and defeats the default. If no information about parent(john, x) is available the default is not applicable anyway).
Texas Tech University
Knowledge Representation Group
11
More about Uncaring Parents To better understand the need for the cancellation axioms let us consider another strong exception to the “caring parents” default. Assume the existence of a mythical country, u, whose inhabitants do not care for their children. This exception to default d1 is represented by rules ¬cares(P, X) ← parent(P, X), born in(P, u). d1(P, X)
← not ¬born in(P, u)).
Now consider an extension of our family database which contains information about national origin of most (but not all) recorded people.
Texas Tech University
Knowledge Representation Group
12
Assume, for instance, that according to our records Pit and Kathy are the father and mother of Jim, Kathy was born in Moldova, but the national origin of Pit is unknown. He could have been born in u. It is easy to see that the queries ?cares(kathy, jim) and ?cares(pit, jim) are correctly answered by yes and unknown respectively. If later we learn that Jim is indeed from u then the second answer will be replaced by the definite no.
Texas Tech University
Knowledge Representation Group
13
Mixing Exceptions — Cowardly Students Let us consider an example which has both, weak and strong exceptions. We are given • two classes of objects, student and dept containing names of all students and departments of the domain. • a (possibly incomplete) list L in(john, engl). in(mary, cs). in(bob, cs). in(pat, math). which relates students to their unique majors. • the following default with exceptions: Normally, students are afraid of math. A brave student Mary and the math majors are not. Those in CS may or may not be afraid. Texas Tech University
Knowledge Representation Group
14
Cowardly Students (continued) Let us represent the above information in AProlog. To define negative information for relations student and dept we can use the CWA. But since L maybe incomplete we need to find some other way to deal with negative information about in. The rule ¬in(S, D1) ← in(S, D2), D1 6= D2. does that by exploiting uniqueness of majors. The resulting program entails ¬in(mary, engl), etc.
Texas Tech University
Knowledge Representation Group
15
Cowardly Students (continued) The default is translated by the rule: af raid(S, math) ← student(S), not d(S), not ¬af raid(S, math). The first exception can be represented as: d(mary).
¬af raid(mary, math).
To represent weak exception in(S, cs) and strong one, in(S, math), we write: d(S) ← student(S), not ¬in(S, cs). d(S) ← student(S), not ¬in(S, math). ¬af raid(S, math) ← student(S), in(S, math). Texas Tech University
Knowledge Representation Group
16
Cowardly Students (continued) (a) Informally ’tracing’ the rules of the program check if the following answers to queries are correct: ? af raid(john, math)
Yes
? af raid(mary, math)
No
? af raid(pat, math)
No
? af raid(bob, math)
Unknown
(b) Use one of A-Prolog inference engines to answer these queries. (c) Will dropping the statement d(mary) from the program change the program’s definition of relation af raid? What about dropping the cancellation rule for math students? Texas Tech University
Knowledge Representation Group
17
Important special case The above representation of defaults and exceptions is rather general. Sometimes it can be substantially simplified. Here is an example: Let c0 be a collection of weak exceptions to default d ’Elements of c normally have property p’. If the reasoner has a complete knowledge of c0 than the cancellation axiom for d is d(X) ← c0(X). If c0 is a completely described collection of strong exceptions no cancellation axiom for c0 is needed.
Texas Tech University
Knowledge Representation Group
18
Incompleteness in Databases Consider a database table representing a tentative summer schedule of a CS department. Professor Course mike
pascal
john
c
staff
lisp
Here ’staff ’ is a special constant (called Null value) which stands for an unknown professor. It expresses the fact that Lisp will be taught by SOME professor (possibly different from Mike and John). To represent this information we introduce a relation t(P, C) which says that professor P teaches a course C. We also assume that we are given complete collections of professors and courses. Texas Tech University
Knowledge Representation Group
19
Incompleteness in Databases The positive information from the table can be represented by a collection of facts: t(mike, pascal). t(john, c). t(staf f, lisp). To represent negative information we use default d: Normally, P teaches C only if this is listed in the schedule. Notice that d is not applicable to Lisp (or any other course taught by ’staff ’). This can be represented as: ¬t(P, C) ← prof (P ), course(C), not d(P, C), not t(P, C). d(P, C) ← t(staf f, C). Check that the resulting program Π0 program produces correct answers (N o and U nknown) to queries ?t(mike, c) and ?t(mike, lisp). Texas Tech University
Knowledge Representation Group
20
Incompleteness in Databases Now consider a different type of incompleteness in database tables. Professor
Course
mike
pascal
john
c
{mike,john} prolog staff
lisp
Here {mike,john} represents the second type of nulls – “value unknown but one of the finite set of values”. To represent this information we simply expand Π0 by t(mike, prolog) or t(john, prolog). Π1’s answers to queries ?t(mike, c), ?t(mike, prolog) and ?t(mike, prolog) ∧ t(john, prolog) are N o, U nknown, and N o respectively. Texas Tech University
Knowledge Representation Group
