Default-Reasoning with Models

1 Introduction

The generally accepted framework for studying reason­ ing in intelligent systems is the knowledge-based system approach. The idea is to store the knowledge in some representation language with a well defined meaning as­ signed to its sentences. The sentences are stored in a Knowledge Base ( J{ B) which is combined with a rea­ soning mechanism that can be used to determine what It is widely acknowledged today that a large part of our everyday reasoning involves arriving at conclu­ sions that are not entailed by our "theory" of the world. Many conclusions are derived in the absence of infor­ mation that is sufficient to imply them. This type of reasoning is naturally non-monotonic since further ev­ idence may force us to revise our conclusions. Within the knowledge-based systems approach this situation is handled by theories for reasoning with "defaults" (see e.g. [Reiter, 1987a)). The true knowledge about the world is augmented by a set of default rules that capture only "typical" cases. The quest is for a reasoning system that, given a query, responds in a way that agrees with what we know about the world and the default assump­ tions and at the same time supports our intuition about a plausible conclusion.

*Research supported by Center for Intelligent Control Sys­ tems, ARO contract DAAL03-92-G-0115.

'Research supported by NSF grant CCR-92-00884 and by DARPA AFOSR-F4962-92-J-0466.

Computational considerations, however , render this self-contained approach to reasoning inadequate for com­ monsense reasoning. This is true not only for the task of deduction, but also for many other forms of reason­ ing which have been developed . All those were shown to be even harder to compute than the original formu­ lation [Selman, 1990; Roth, 1993). Of particular inter­ est in this context are the results on default reasoning tasks [Selman and Kautz, 1990; Kautz and Selman, 1991; Papadimitriou, 1991), where the increase in complexity is clearly at odds with the intuition that reasoning with defaults should somehow reduce the complexity of rea­ soning. This remains true, even when we severely re­ strict the expressivity of the knowledge base, the default rules and the queries allowed. For example, when the knowledge base is Horn, all the default rules are positive literals, and the query is a single positive literal, the de­ fault reasoning task is NP-Hard [Selman and Levesque, 1990]. This should be contrasted with the case of deduc­ tive reasoning, where Horn theories are distinguished by the existence of linear time satisfiability algorithms.

An alternative approach to the study of common­ sense reasoning is developed in [Kautz et al. , 1995; Khardon and Roth, 1994c]. There, the knowledge base is represented as a set of models (satisfying as­ signments) of the world rather than a logical formula describing it. It is not hard to motivate a model­ based approach to reasoning from a cognitive point of view and indeed, most of the proponents of this ap­ proach to reasoning have been cognitive psychologists [Johnson-Laird, 1983; Johnson-Laird and Byrne, 1991; Kosslyn, 1983], who have alluded to the notion of "rea­ soning from examples" on a qualitative basis. In the AI community this approach can be seen as an example of Levesque's notion of "vivid" reasoning [Levesque, 1986; 1992], and is somewhat related to Minsky's frames­ theory [Minsky, 1975].

Given a model-based representation of the knowledge base K B and a query a, the deduction task K B f= a can be answered in a straightforward way: Evaluate a on all the models in the representation. If you find a model of KB which does not satisfy a, then KB ~a, otherwise conclude K B f= a. Clearly, if the model-based repre­ sentation contains all the models of K B this approach yields correct deduction, but representing K B by explic­ itly holding all the possible models is not plausible. A model-based approach becomes feasible if K B can be replaced by a small model-based representation and still support correct deduction.

The theory of model-based representations developed in [Khardon and Roth, 1994c] (generalizing the theory developed in [Kautz et al. , 1995] for the case of Horn ex­ pressions) characterizes the propositional languages for which model-based representations support efficient de­ duction and abduction. It is shown that in many cases in which the deduction and abduction tasks are NP-Hard in the formula-based setting, the model-based representa­ tion is small (polynomial in the number of propositional variables in the domain), and reasoning with it yields correct and efficient reasoning algorithms.

In this paper, we extend the work presented in [Khardon and Roth, 1994c] and present some more com­ putational advantages of reasoning with model-based representations. As a basic computational task we con­ sider the problem of reasoning within a varying con­ text. In real life situations, one normally completes a lot of missing context information when answering queries [Levesque, 1986]. We model this situation by augment­ ing the knowledge we have about the world with context­ specific information. Reasoning within context is there­ fore a deduction task, where some additional constrain­ ing information is added to the knowledge base. We show how to solve this task efficiently using a model-based representation, for a variety of propositional languages as context information.

We then consider the task of default reasoning. There, giVen a representation of the world, a set of (sometimes conflicting) default rules and an assertion q, one is trying to asses whether q can be concluded "by default" from the available information. We show that default reason­ ing is a generalization of reasoning within context, in which the reasoner has many context rules, which may be conflicting. We provide an efficient algorithm for the default reasoning task, for various classes of world knowl­ edge, default rules and queries, based on the algorithm developed for reasoning within context.

As in the case of deductive and abductive reasoning [Khardon and Roth, 1994c], we present an efficient de­ fault reasoning algorithm for cases where the formula based reasoning is hard. For example, in contrast to the hardness result mentioned above, we show that if the knowledge base is any propositional language with a polynomial size DNF 1 , the default rules are arbitrary monotone functions and the query is a Horn query, the default reasoning task can be solved correctly and effi­ ciently.

Equally important for the plausibility of model based reasoning is the view that it suggests about reasoning. While we do not consider in the paper the question of how the knowledge base is acquired, this issue is clearly an important one, and the plausibility of any theory for reasoning hinges on it. It is important therefore to mention that it has been shown, within the Learn­ ing to Reason framework [Khardon and Roth, 1994b; 1995], that model-based representations that are suitable for the reasoning tasks considered here can be learned ef­ ficiently. The model based approach to default reasoning can therefore be incorporated within an inductive set­ ting. The model based representation can be efficiently learned, context specific default rules can be acquired in various learning processes, and these can be combined to work together in a plausible and efficient way. Further­ more, we show how knowledge available within a specific context can be used to reason within this context. There­ fore, our treatment of reasoning within context supports the view that an intelligent agent constructs a represen­ tation of the world incrementally by pasting together many "narrower" views from different contexts.

The inductive nature of non-monotonic reasoning is also at the heart of the approach developed in [Valiant, 1994; Roth, 1995], where a different view on dealing with incomplete information is taken.

2 Preliminaries

We consider problems of reasoning where the "world" is modeled as a Boolean function W : {0, l}n -+ {0, 1}. We use interchangeably the terms propositional expres­ sion and Boolean function, and likewise for propositional language and a class of Boolean functions. We denote classes of Boolean functions by :F, g, and functions by f,g.

We consider a set X= {xt, . .. , xn} of variables, each of which is associated with a world's attribute and can take the value 1 or 0 to indicate whether the associated attribute is true or false in the world.

1 The size of the model-based representation of K B is re­ lated to the size of its minimal DNF. Thus, we do not assume that the DNF representation is known but only require that a polynomial size representation exists.

Assignments are mappings from X to {0, 1} , and we treat them as elements in {0, 1}n with the natural map­ ping. Assignments in {0, l}n are denoted by x, y, z, and weight( x) denotes the number of 1 bits in the assign­ ment x. A clause is a disjunction of literals , and a CNF formula is a conjunction of clauses. For exam­ ple (x1 V x2) 1\ (x3 V x1 V x4) is a CNF formula with two clauses. A term is a conjunction of literals , and a DNF formula is a disjunction of terms. For example (x1 1\ x2) V (x3 1\ X!/\ x4) is a DNF formula with two terms. A CNF formula is monotone if all the literals in it are positive (unnegated). A CNF formula is Horn if every clause in it has at most one positive literal. A CNF formula is k-quasi-Horn if there are at most k positive literals in each clause. It is a k-quasi-reversed-Horn if there are at most k negative literals in each clause. A DNF formula is k-quasi-monotone DNF if there are at most k negative literals in each term.

Every Boolean function has many possible representa­ tions, and in particular both a CNF representation and aDNF representation. By the DNF size off, denoted IDN F(f) I, we mean the number of terms in the minimal DNF representation of f. (Similarly, for ICN F(f)l.)

An assignment x E {0, l}n satisfies f if f(x) = 1. (xis also called a model of f .) Iff is a theory of the "world", a satisfying assignment of f is sometimes called a possi­ ble world. By "f implies g", denoted f I= g, we mean that every model off is also a model of g . Throughout the paper, when no confusion can arise, we identify a Boolean function f with the set of its models, namely f- 1 (1). Observe that the connective "implies" (I=) used between Boolean functions is equivalent to the connec­ tive "subset or equal" (~) used for subsets of {0 , l}n. That is, f I= g if and only iff~ g.

3 Reasoning with Models

Consider a propositional knowledge base W and let o: be a propositional query. The deduction problem W I= a can be approached using the following model-based strategy:

Algorithm MBR(r, o:):

Test Set: A set r ~ W of possible assignments.

Test: If there is an element X E r which does not satisfy o:, return "NO". Otherwise, return "YES".

Clearly, this approach solves the inference problem if r is the set of all models (satisfying assignments) of w, but this set might be too large. A model-based approach becomes useful if one can show that it is possible to use a fairly small set of models as the Test Set, and still perform reasonably good inference.

This section briefly introduces the monotone theory of Boolean functions [Bshouty, 1993], and the theory of reasoning with models 2 (see [Khardon and Roth, 1994c] for more details) .

2 We note that this direction was studied independently in the Relational Data Base community [Beeri et a/., 1984; Mannila and Raiha, 1986]. The results on model-based rea-

Definition 1 (Order) We denote by :S the usual par­ tial order on the lattice {0, l}n, the one induced by the order 0 < 1. That is, for x,y E {0, l}n, x :S y if and only if'Vi,xi :S Yi· For an assignment bE {0,1}n we define x :Sb y if and only if x EB b :S y EB b (Here EB is the bitwise addition modulo 2}. We say that x > y if and only if x 2 y and x # y.

Intuitively, if bi = 0 then the order relation on the ith bit is the normal order; if bi = 1, the order relation is reversed, that is , 1 <b, 0.

Next we define: The monotone extension of z E {0, l}n with respect to b:

The monotone extension off with respect to b:

The set of minimal assignments off with respect to b:

Definition 2 (Basis) A set B is a basis for f iff = 1\bEB Mb(f). B is a basis for a class of functions :F if it is a basis for all the functions in :F.

The importance of these definitions is that one can show that every Boolean function has a basis B, and can be represented as follows :

This representation yields a necessary and sufficient con­ dition describing when x E {0, 1}n is positive for f:

Corollary 1 Let B be a basis for f , x E {0, 1}n. Then, x E f (i .e., f(x) = 1} if and only if for every basis element bE B there exists z E minb(f) such that x 2b z .

It is known that for every b, the size of minb(f) is bounded by the size of its DNF representation. Further, a set of assignments which falsify every clause in a CNF representation of f is a basis for f . Therefore, f has a basis whose size is bounded by ICN F(f)l. Some impor­ tant function classes have a small fixed basis, irrespective of the CNF size of the function:

Horn-CNF formulas: The basis for this class is BH = {u E {0, 1}n I weight(u) 2 n-1} , since every Horn clause is falsified by an assignment in B H . Clearly, IBHI = n + 1.

k-quasi-Horn formulas:

BHk = {u E {0, l}n I weight(u) 2 n- k} is a basis. Clearly, IBHk I= O(nk) . Similarly, there is a basis for k-quasi-reversed-Horn formulas .

log nCNF formulas: CNF in which the clauses contain at most O(log n) literals . The basis for this class is derived using a combinatorial construction called an (n, k)-universal set [Alon et al., 1992]. It can be shown that IBiogn - CNF I = O(n 3 ) .

Common queries: A function is common if every clause in its CNF representation is taken from one of the above classes. The union of the bases for these classes is a basis , Be, for all common functions. We refer to this class as the class of common queries.

soning have immediate implications in this domain which are described elsewhere [Khardon et a/., 1995] .

3.1 Deduction

We can now to characterize a model-based knowledge base for which the algorithm MBR is successful.

Definition 3 For a knowledge base f E F the set r = rr of characteristic models off, is the set of all minimal assignments off with respect to the basis B. Formally,

The following are the basic theorem of the theory of rea­ soning with models, its application to common queries, and a bound on the size of the model-based representa­ tion.

Theorem 1 Let f be any Boolean function , and a E g, where B be a basis for 9. Then f f= a if and only if for every u E rf, a(u) = 1.

Theorem 2 Let f be any Boolean function. Then for any common query, model-based deduction using rJc, is correct.

Theorem 3 Let f be any Boolean function, and B a basis. Then, the size of the model-based representation off is

We note that this bound is tight in the sense that for some functions the size of the DNF is indeed needed. It does however allow for an exponential gap in other cases. Namely, there are functions with an exponential size DNF and a linear size model-based representation [Khardon and Roth, 1994c]. It is also interesting to com­ pare the size of this representation to the size of other representations for functions . Examples in [Kautz et a/., 1995] show that there are cases where the (Horn CNF) formula representation is small and the model-based rep­ resentation is exponentially large, and vice versa. For a discussion of these issues see [Khardon and Roth, 1994c].

Example: Let f have the CNF representation:

The function f has 12 (out of the 16 possible) satisfying assignments. The non-satisfying assignments off are 3 : {0000,0001,0010,1101}.

If we want to be able to answer all possible Horn queries with respect to f we need to use the Horn ba­ sis Bn = {1111,1110 , 1101 , 1011,0111}. Each of the models 1111,0111,1011,1110 satisfies f and therefore for each of these, minb(f) = b. For b = 1101, the mini­ mal elements can be found by drawing the correspond­ ing lattice and checking which of the satisfying assign­ ments of f are minimal. This yields min1101 (f) = {1100, 1111, 1001, 0101}. We therefore get that rJH = {1111, 0111, 1011, 1100, 1001, 0101, 1110}. Note that it includes only 7 out of the 12 satisfying assignments of f .

Clearly, in general rJH ~ f, and therefore model­ based deduction never makes mistakes on queries that are implied by f. Furthermore, for the Horn query Ctl = Xl A X3 -+ X2, reasoning with rJH will find the counterexample 1011 and deduce correctly that f V= a-1.

3 An element of { 0, 1} n denotes an assignment to the variables X1, ··· , Xn (i.e., 0011 means X1 = x2 = 0, and X3 =X4 = 1).

We note that in general, iff is given in its CNF repre­ sentation, solving the problem f f= a is co-NP-complete, even when a is a Horn query.

4 Reasoning within Context

It has been argued that in real life situations, one nor­ mally completes a lot of missing "context" information when answering queries [Levesque, 1986]. For example, if asked at the conference how long it takes to drive to the airport, we would probably assume (unless specified oth­ erwise) that the question refers to the city we are at now, Montreal, rather than where we live (and have been to the airport more times). This corresponds to assigning the value "true" to the attribute "here" for the purpose of answering the question. Sometimes we need a more expressive language to describe our assumptions regard­ ing the current context and assume, say, that some rule applies [Selman and Kautz, 1990]. For example, we may assume (in the "conference" context) that if someone has a car, then it is a rental car.

Let W be a Boolean function that describes our knowl­ edge about the world. A "first principle" way to for­ malize the above intuition is the following: we want to deduce a query a from W, if a can be inferred from W given that the query refers to the current context. Namely, the instances of W which are relevant to the query must also satisfy the context condition d, a con­ junction of some literals and rules. We denote this ques­ tion by W Fd a .

Notice that it is possible that W Fda but W V= a, if all the satisfying assignments of W that do not satisfy a do not satisfy d. Formalized this way, we get that the problem W Fd a is equivalent to the problem W 1\ d f= a. Thus, a theorem proving approach to reasoning does not give any computational advantage in solving this reasoning problem.

Let WE F, a E g and let B be a basis for() . From Theorem 1 it is clear that given r~ Ad I the set of charac­ teristic models for WAd, model-based reasoning can be used to solve the reasoning problem WAd f= a. How­ ever, we consider here a more general problem: given r~ we are interested in performing inference according to Fd with it, where the "context condition" d may vary.

From our model-theoretic definition of the connective Fd it is clear that if one holds all the models of W, then by filtering out all the models that do not satisfy d and then performing the model-based test one can answer WAd f= a correctly. The algorithm C-MBR does just that, with the set r:

Algorithm C-MBR(r, d, a) :

Test Set: Consider only those elements of r which satisfy d.

Test: If there is such an element which does not sat­ isfy a, return "NO". Otherwise, return "YES".

The following theorems characterize the cases in which this algorithm, C-MBR, provides correct reasoning.

Theorem 4 Given r{t I the algorithm c -MER provides an exact solution to the reasoning problem W Fd a for every d such that B is a basis for d --+ a.

Proof: Clearly, W Fda= W 1\ d F= a= W F= dV a= W I= ( d --+ a). Therefore, from Theorem 1, when B is a basis for d --+ a, r{t can be used for model-based reasoning with it. Models of W that do not satisfy d are useless as counterexamples since d --+ a always holds and therefore, using the Test Set of Algorithm C-MBR produces the correct inference. ·

Theorem 5 The following conditions on a, B and d guarantee that C -MER supports correct reasoning within context.

(i} Let a be a Horn query and B = B H 1 a basis for Horn theories. If d is a monotone Boolean function then B is a basis for d --+ a .

{ii} Let a be a k-quasi-Horn query and B = BHk+l' a basis for (k +I)-quasi-Horn theories. If d is a Boolean function that can be represented as a /-quasi-monotone DNF then B is a basis ford--+ a .

(iii) Let a be a log nCNF query and B a basis for 2log n CN F theories. If d is a conjunction of up to log n arbitrary rules (or disjunctions) then B is a basis for d-+a .

Proof: For (i), consider first the case in which d = 1\;El x; . Let a= 1\jEJ(mj --+ Xj) be a Horn query (that is, mj is a monotone conjunction). Then

which means that d--+ a is a Horn expression . In gen­ eral , if d' is a monotone function, d' = V e de where de are monotone conjunctions. Since Vf, g, h, (! V g) --+ h ;::::: (! --+ h) 1\ (g ---+ h), we get that d' --+ a = AtU\jEJ((de 1\ mj)--+ Xj)) is a Horn theory 4 . For (ii), in the same way, we get that the body of the rule might contain up to k+l non-negated literals. For (iii) , similar manipulations show that d --+ a is a 2log nCNF. ·

The approach presented in this section can be viewed as a process of augmenting a model-based representation r with a set of rules. Given a model-based representa­ tion r{t of w, any rule that holds in w cannot help in answering queries, since it does not filter out any as­ signment of W, and is thus redundant. However, the context rules do not hold in W and thus augmenting W with them modifies the set of conclusions. As we have shown, in order to reason within context, we need to maintain a model-based representation with respect to a basis that is slightly larger than in the pure deductive case.

5 Default Reasoning with Models

In the previous section we assumed that the context in­ formation is given. In general, one might have many context rules, which may be conflicting, and the goal is to derive plausible conclusions in the face of this infor­ mation.

4 We note that the size of the resulting Horn theory might be exponentially large, but it only appears in the analysis. We do not actually compute this expression in the algorithm. Rather , filtering examples according to d is sufficient. The same holds for the other cases.

This is the situation modeled in default reasoning. Given a representation of the world, a set of (sometimes conflicting) default rules, and an assertion q, one is try­ ing to asses whether q can be concluded by default from the available information. We will see that this is a gen­ eralization of the situation discussed in the previous sec­ tion, and that it can also be dealt with efficiently using model-based representations. We shall concentrate here on a special case of Reiter's Default logic [Reiter, 1980], applied to propositional logic and with some restrictions on the default rules.

In Reiter's default logic, default rules have the form a : (3/J, which should read as "if a holds and it is con­ sistent to assume f3 then conclude 1". The case with f3 = 1 is called normal defaults, and a is called a prereq­ uisite. The discussion below considers normal defaults with empty prerequisites (i.e. of the form : f3 I (3). In this case, we denote by D the set of Boolean functions (3, and say that D is the set of default rules. We sometimes treat a collection of rules as their conjunction. That is, D(x) = 1 means 1\dEDd(x) = 1.

Definition 4 A default rule is simple if it is of the form : f3 I {3 1 and f3 is a single literal. The rule is positive if (3 is any monotone function. The rule is positive simple if f3 is a positive literal.

Notice that the theory for diagnosis [Reiter, 1987b] and the closed world defaults [Reiter, 1980] can be described using simple defaults.

A default theory is a pair (D, W) where D is a set of default rules, and W is propositional expression. An ex­ tension of ( D, W) is defined as a fixed point of some oper­ ator. For our special case the following theorem gives an alternative and simpler definition: (The operator Th(R) denotes the theorem closure of R.)

Theorem 6 ([Reiter, 1987b], page 88) Let D be a set of normal defaults with empty prerequisite. E is an extension of (D, W) iff E = Th(W U {/31 : /31 (3 E S} ), and S is a maximal subset of D such that E = W U {/31 : f3 I (3 E S} is consistent.

Using this theorem as the definition for extension we can identify a maximal consistent subset S with each extension E . We denote this subset by SE. Given that SE is consistent with W, we get that an extension E includes q iff W 1\ SE F= q.

The default reasoning task DEF(D, W, q) is defined as follows: given a default theory (D, W) and a propo­ sitional expression q, decide whether there exists an ex­ tension E of (D, W) such that q E E.

Clearly, if W is consistent with the set of all rules in D, then there exists only one maximal consistent subset S of D, the one which contains all these rules. This case simply reduces to reasoning within the context D, which we discussed earlier. The main difficulty which arises in the general case is that W may not be consistent with all of D .

Next we present positive results on default reasoning. As in the deductive reasoning case, the efficient results we present hold in cases where the formula based reason­ ing is hard 5 . The following algorithm, D-MBR, is based on the abduction algorithm 6 developed in [Kautz et al., 1995] and used in [Khardon and Roth, 1994c].

Algorithm D-MBR(f, D, q):

Do for all models z E r such that q( z) = 1 LetS= {dE D : d(z) = 1} If C-MBR(r, S, q) answers "YES", return "YES". End Do Return "NO". /* No extension found * /

Assume that r = rw , a model based representation of W. The algorithm D-MBR receives r, D and a query q as input. It starts by enumerating all the models in r. When it finds a model z in which the query holds, (i.e., q(z) = 1) it sets S to be the set of all the rules in D that this model satisfies. The algorithm then tests whether W 1\ S F= q by calling the procedure C-MBR to decide whether W F=s q. If the answer is "yes" the algorithm returns "yes" (and possibly the extension S), and otherwise it continues to test the next model in r. If all the models in r have been scanned and no good extension has been found the algorithm says "no".

Theorem 7 Let W be any propositional expression, D a set of positive defaults, and Q the class of Horn queries. Then, for all q E Q, on input (D, r!H, q), the algorithm D-MBR solves the default reasoning task DEF(D, W, q) correctly.

Proof: Assume first that there exists extension E that contains q. We show that the algorithm answers "YES" . By definition, the existence of the extension implies that W 1\ SE F= q and that there exists an assignment u E W such that SE(u) = 1 and q(u) = 1. Let z E min1n(W) such that z :S1n u. Then SE(z) = 1, as SE is mono­ tone. Since W 1\ SE f= q we have q(z) = 1. Since z E r!H ' the algorithm D-MBR will use it , and set SE correctly (since SE is a maximal set of elements from D). By (i) of Theorem 5 the algorithm C-MBR answers "Yes" when called with r!H ' SE and q, and therefore D­ MBR answers "YES". Assume now that D-MBR returns "YES". Since q is Horn and S is a set of monotone func­ tions, Theorem 5 implies that C-MBR is correct, that is W 1\S F= q. By construction, Sis a maximally consistent set and therefore the corresponding extension contains q.

· 5 We note that the default reasoning task is NP-Hard [Sel­ man and Levesque, 1990] when the knowledge base is Horn, all the default rules are positive literals, and the query is a single positive literal. Our results provide an algorithm for this class of problems, which is polynomial in the size of the model based representation. The latter though may be expo­ nential in the size of the Horn expression, and in particular this happens for the problems used in the reduction in [Sel­ man and Levesque, 1990]. So strictly speaking we do not prove an advantage in this special case. Our results, how­ ever, provide efficient algorithms in cases where they were not known to exist before.

6 0ur results were inspired by the connections between ab­ duction and default reasoning developed in [Selman, 1990].

Similarly, we can show:

Theorem 8 Let W be any propositional expression, D a set of simple defaults with up to k-1 negative literals, and Q the class of Horn queries. Then, for all q E Q, on input (D, r!H·, q) , the algorithm D-MBR solves the default reasoning task DEF(D, W, q) correctly.

Proof: Let E be an extension and SE its corresponding maximal consistent subset of D. The element b, defined by: b; = 0 when x; E SE , otherwise, b; = 1, is in the basis BH,.

Note that if SE(u) = 1 and z E minb(W) such that z :Sb u, then SE(z) = 1 since the assignments to vari­ ables in SE are the same in u and z. Therefore the proof of Theorem 7 applies here as well (replacing the basis element 1 n by b, and using (ii) of Theorem 5) . ·

Using Theorem 4 we can find other instances in which correct default reasoning is possible. For example, we could answer queries that are more general than Horn queries. In particular, if D is simple and the literals in D are special (e.g., Abnormal predicates in diagnosis) and do not appear in the queries, then we can set a special basis that will handle every query which is either Horn or in log n-CNF.

The above theorems yield efficient default reasoning whenever the model-based representation r is small. (And, in particular, whenever the DNF size off is small.) This should be contrasted with the hardness of deductive and default reasoning.

6 Discussion

Reasoning with models is an intuitive paradigm, which has been shown to be theoretically sound. In this paper we presented more evidence to the utility of such rep­ resentations. In particular , these representations sup­ port efficient reasoning in the presence of varying con­ text information, as well as some restricted cases of de­ fault reasoning. The significance of these results is that they are achieved as natural extensions of exact ( deduc­ tive) reasoning, and hold in cases in which the traditional formula-based representation does not support efficient reasoning.

These results can be viewed as providing some the­ oretical support for the usefulness of case-based style reasoning, where a set of "typical cases" is used as a knowledge representation .

We have shown that a model-based representation can be used to reason correctly when some additional con­ straining context information is supplied. This informa­ tion augments the agents' knowledge and aids in deriving conclusions relevant to this context. We call this a top­ down solution. It is conceivable, though, that an agent would have only some of the models, those models that come from some specific context d. In such a case, our results show that the agent reasons correctly within this context (although not within every context). This ap­ proach can be shown to work in other scenarios in which the agent constructs a model-based knowledge represen­ tation by randomly collecting examples in the environ­ ment [Khardon and Roth, 1994a]. Thus, the approach supports the view that an intelligent agent constructs a representation of the world incrementally by pasting to­ gether many "narrower" views from different contexts ..

In default reasoning, an agent may have many (possi­ bly conflicting) default rules, acquired in different con­ texts. Default reasoning is thus a generalization of rea­ soning within context where the additional information may not be consistent, and may not be consistent with the knowledge the agent has about the world. Indeed, a query holds "by default", if there is a plausible con­ text in which it holds. As we have shown, model-based representations efficiently support default reasonin~ . .

Finally, we mention that it has been shown, w1thm the Learning to Reason framework [Khardon and Roth, 1994b] that the model based representations discussed here c~n be learned efficiently. This can be combined with context specific default rules that are acquired via rote learning or other learning processes [Schuurmans and Greiner, 1994] to work in a plausible way.