Learning to Reason: The Non-Monotonic Case

1 Introduction

Any theory aiming at understanding commonsense reason­ ing, the process that humans use to cope with the mundane but complex aspects of the world in evaluating everyday situa­ tions, should account for the flexibility, adaptability and speed of commonsense reasoning.

The major approach in AI to this problem is within the framework of the knowledge-based systems. It is assumed that the knowledge is given to the system, stored in some It is widely acknowledged today that a large part of our everyday reasoning involves arriving at conclusions that are not logically entailed by our "theory" of the world. Many conclusions are derived in the absence of sufficient infor­ mation to deduce them. This type of reasoning is naturally non-monotonic, since further evidence may force us to retract the conclusions. In light of this, many researchers, work­ ing within the above framework, have tried to augment the knowledge base and to modify the inference mechanisms so as to allow reasoning in the presence of incomplete infor­ mation. The idea is to augment the true knowledge (facts and rules) we have about the world with a set of assump­ tions that capture only "typical" cases. These assumptions are called default assumptions, or simply defaults. Within the knowledge-based systems approach, defaults are stored in the knowledge base along with the other, non-default, knowl­ edge. 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 some subset of the default assumptions, and at the same time supports our intuition about a plausible conclu­ sion. The process of reasoning with the knowledge and the defaults is called default reasoning, and numerous formalisms that attempt at acceptable reasoning behavior have been stud­ ied for it (e.g., [AI, 1980; Touretzky, 1986; Reiter, 1987; Etherington, 1988; Goldszmidtand Pearl, 1991; Pearl, 1988; Geffner, 1990]).

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

Computational considerations, however, render all the for­ malisms suggested within the knowledge-based systems ap­ proach apparently inadequate for commonsense reasoning. This is true not only for the task of deduction, but also for many other forms of reasoning which have been developed [Selman, 1990; Roth, 1993]. Of particular interest in this context are the hardness results on default reasoning tasks [Selman, 1990; Papadimitriou, 1991], where the increase in complexity (rela­ tive to corresponding deduction tasks) is clearly at odds with the intuition that reasoning with defaults should somehow reduce the complexity of reasoning. Moreover, many studies in this framework have shown that capturing what people view as plausible patterns of reasoning is not easy (e.g. , [Touret­ zky et al., 1987]). Most formalisms, in attempting to capture some aspects of "default" reasoning give up on others. Multi­ ple levels of specificity of information, irrelevant information and conflicting defaults are among the aspects that the various formalisms have found difficult to reconcile.

In [Khardon and Roth, 1994b] a new framework for the study of reasoning is introduced. The framework incorporates a role for inductive learning within efficient reasoning and ex­ hibits the importance of studying the learning and reasoning phenomena together. The Learning (in order) to Reason ap­ proach combines the interfaces to the world used by kno~n learning models with the reasoning task and a performance cn­ terion suitable for it. In this framework the intelligent agent is given access to her favorite learning interface, and is also given a grace period in which she can interact with this interface and construct her representation of the world. Her performance is measured in a way that makes explicit the dependence of the reasoning performance on the input from the environment. In this framework it is shown that, through interaction with the world, the agent truly gains additional reasoning power over what is possible in the traditional setting. In particular, rea­ soning problems that are provably intractable in the traditional approach are given efficient Learning to Reason algorithms.

Previous works in the Learning to Reason framework [Khardon and Roth, 1994b; 1995b] have considered reasoning tasks whose functionality is well defined. This paper, on the other hand, considers tasks in which, in many cases, there is no agreement on what constitutes a "plausible" outcome.

The disagreement, we believe, is justified. We argue here that commonsense reasoning, and in particular, reasoning in the presence of incomplete information, is an inductive phe­ nomenon; when the notion of consistency is at the heart of the formal reasoning system, as in most previous approaches, inductive phenomena are difficult to capture.

In this paper we extend the Learning to Reason framework to deal explicitly with reasoning in the presence of incomplete information. Inspired by the pac-learning approach [Valiant, 1984] we present the view that the world is very complicated and there is no hope of acquiring an exact representation of it; our aim should be to acquire enough information with which to cope effectively in the world. In doing so we extract certain regularities from the world, and assume that in similar circumstances we can rely on these.

Consider, for example, concluding from the knowledge that Tweety is a bird that Tweety can fly. This conclusion is use­ ful , and is clearly justified in some situations, e.g., when discussing birds in Boston during their migration season. A different conClusion will be suggested, though, by a veterinar­ ian working in a birds' hospital, or by someone raised in an ostrich nature reserve. Of course, the possible circumstances in which any "presumed" correct line of reasoning can be de­ feated astound, and we are doomed to make mistakes when our experience does not support the current situation.

The key to the approach we develop is the view that regular­ ities occur not only in what we observe (e.g., if all elephants we have seen had a trunk, we might think that all elephants have a trunk) but also in what we do not observe (e.g., if in previous experience of flying birds we were not aware of their color, when observing a red bird we would predict that it flies .). That is, missing information in the interaction of the agent and her environment may be as informative as observed information. In this paper we formalize this intuition and use it to develop a theory that supports efficient reasoning with incomplete information.

Our treatment of incomplete information follows a sugges­ tion made in [Valiant, 1994b]. While there, in an effort to formalize the notion of Rationality, a comprehensive view of the phenomena that comprise cognition is presented, here we present a more detailed account of reasoning in the pres­ ence of incomplete information focusing on presenting it as a problem of Learning to Reason.

Unlike previous theories of reasoning in the presence of incomplete information, we are not interested in providing a theory of defaults, but rather a theory of inference. We show that the representation developed here provides a richer lan­ guage for dealing with reasoning problems and consequently, many default reasoning scenarios, with which previous for­ malisms have struggled, have concise representations in our framework. Moreover, these representations can be learned efficiently from interaction with the environment, to yield ef­ ficient Learning to Reason algorithms.

Later in the paper we discuss the relation of this work to the default reasoning literature. Now we briefly mention some works that are related to the approach presented here. In [Khardon and Roth, 1995b] a Learning to Reason approach that can deal with partial information is developed and shown to support efficient deduction. The interpretation taken there, however, is not expressive enough to support non-monotonic reasoning. In [Khardon and Roth, 1995a] a solution to some restricted cases of the "traditional" default reasoning problem is suggested, using learnable model-based representations. The approach presented in [Schuurmans and Greiner, 1994] is closest to ours in that they study the problem of learning "default rules". The reasoning stage, however, is not consid­ ered, and presumably is performed by a traditional reasoner, and is thus intractable.

After presenting the framework, we illustrate, in Section 3, how various problems in reasoning with defaults are dealt with in our approach. In Section 4 we discuss some of the learning issues this framework raises and some extensions of the work presented here. We conclude by discussing the results and some theoretical and empirical questions our approach raises.

2 The Framework

We consider a set X = { x 1 , ··· , x n} of variables, each of which is associated with a world's attribute and can take the values 1 or 0 to indicate whether the associated attribute is true or false in the world. An agent interacts with the world through a set of d observed attributes v = (x;, = v; ,, X; 2 = v; 2 , ··· , x;d = v;J . (We use x; to denote attributes, v; to denote the corresponding values, and v to denote a vector in {0, 1, * }n.) Many of the unobserved attributes might not be known' to the agent and the assignment to those, and to known attributes that are unobserved, is denoted by the special symbol *· In this way, observations are vectors in {0, 1, * }n, but we write them by only specifying the observed variables. The world W imposes some distribution D over

1 E.g., the attribute has...broken_wing need not be known.

{0, 1, * }n that governs the occurrences of the observations v E {0, 1, * }n the agent sees. In general, we assume nothing about the world W, nor about D. Presumably, there are some functional dependencies in W, e.g., x 1 = x2 1\ x3, and those are respected by D, in the sense that in any observation v, drawn according to D, if v2 = v3 = 1 then v1 # 0.

We assume that for every known attribute Xj the agent maintains an attribute function fi : {0, 1, * }n-l --+ {0, 1} that defines the dependence of x j on the other attributes.

An attribute function fi is represented in a way similar to the way we represent Boolean functions over {0, l}n, only that the set of values assigned to each attribute is a (non­ empty) subset of {0, 1, *}rather then a (non-empty) subset of {0, 1} as is usually the case. For example, a conjunction f that depends on the attributes x 1, x2 , X3 can be written as f = (x1 = 1) 1\ (xz = 0 or *) 1\ (x3 = *or 1). A DNF representation for f is written as f = V;"=1[(x; 1 E s; 1 ) 1\ (x;2 E s ; 2 ) 1\ . .. (x;k E s;k )], where Sk C {0, 1, *}.A CNF J J representation is written in a dual manner. Clearly, every Boolean function f over {0, 1, * }n can be represented as a DNF and as a CNF, and given v E { 0, 1, * }n it is easy to evaluate f(v).

Notice that when using attribute-function representations there is no need to make assumptions about the "world" and, in particular, to assume it is consistent.

We use oracles to model the type of interaction the agent has with the world, in the spirit ofthe formal study oflearning [Valiant, 1984] and the Learning to Reason framework. The oracles differ according to the amount and type of information they supply the agent about the world. For the purpose of this exposition we assume that all the interactions of the agent with the world are done via observations v = (v; 1 , v;2, .. . , v;d).

We view the following oracle as the main avenue of inter­ action with the world: the type of interaction which occurs in random situations. An Example Oracle with respect to the probability distribution Don {0, 1, * }n, denoted EX(D), is an oracle that when accessed, returns v E {0, 1, * }n, where v is drawn at random according to D. As discussed in [Khardon and Roth, 1994a], in situations constrained to satisfy some context condition (e.g., Q = { x 1 = we_arejn__Boston} or Q = { x 1 1\ x2 --+ X3} ), the occurrences of observations is not governed by D, but by the distribution DQ which is the distribution we see by filtering out all those observations that do not satisfy Q. (We follow here the formulation suggested in [Valiant, 1994b]). We denote this oracle by EX(DQ ).

The following oracle can be thought of as an on-line version of the example oracle, and is sometimes more suitable for the learning to reason tasks considered here: A Reasoning Query Oracle for the attribute function fi, with respect to the distribution D, denoted RQD(fi ), is an oracle that when accessed performs the following protocol with the agent A. (1) The oracle picks v E {0, 1, * }n according to D, hides the value of Xj and returns it, as a query, to A. (We denote the query by rq(v,j =?).) (2) The agent A answers "1" or "0" by evaluating fi ( v ). (3) The oracle responds by "correct" or "incorrect". A reasoning query oracle for a class F of attribute functions is denoted by RQD(F).

We denote by I the interface available to the agent in a given situation. This can be any collection of oracles that represent a reasonable interaction of the agent with the en­ vironment and might depend on the arbitrary and unknown distribution D over {0, 1, * }n or some restriction of it, DQ. (We exclude RQ from I for notational convenience.) Other oracles considered include (see [Khardon and Roth, 1994b; 1995b]) a Membership Query Oracle for the attribute func­ tion fi (which, on input v E { 0, 1, * }n-l and j, returns fi ( v )), an Equivalence Query Oracle for fi, (which, on input g : {0, 1, * }n-J --+ {0, 1 }, determines whether fi = g), a Causal Example Oracle and others.

The learning scenario most appropriate in our case is an on-line scenario (or, continuous learning) [Littlestone, 1989; Valiant, 1994a]. Every example received by the algorithm can be used to update many attribute functions in parallel. For example, if v E {0, 1, * }n is supplied by EX(D), and Vj = 1, v; = 0 than v can be used as a positive example for the attribute function fi and a negative example for J;.

The reasoning task we consider is a prediction task. Given v E {0, 1, * }n-l in which Xj is hidden (i.e, we do not receive a value for x j ), the algorithm is required to predict f i ( v ). Thus, reasoning with respect to an attribute xi is reduced to evaluating the attribute function fi on a total vector over {0, 1, * }n-l, and it depends on learning the correct attribute function. We consider a query given to the algorithm as if given by the Reasoning Query Oracle RQD(fi ). Thus, a reasoning error supplies the algorithm information which in turn can be used to improve its future reasoning behavior. In doing so, the algorithm may use other oracles from I . Notice that the queries depend on the distribution D, and thus the algorithm improves its performance "faster" in areas of the distribution in which it is queried more. For a class F of attribute functions we say that an algorithm solves the reasoning problem RQ( :F) if it can answer prediction queries with respect to all attribute functions f E :F.

As performance criteria we will use the criteria accepted in computational learning theory (which we do not define here), namely, either the pac criterion [Valiant, 1984] or the mistake-bound criterion [Littlestone, 1989]. Since reasoning is efficient given the attribute functions, we can define: An algorithm A is a Probably Approximately Correct Learning to Reason ( PAC-L2R) (Mistake-Bound Learning to Reason ( MB­ L2R)) algorithm for the reasoning problem RQ(:F), if there exists a PAC (Mistake-Bound) learning algorithm for the class F, given access to I. The algorithm is noise tolerant when it can tolerate the standard amount of classification noise 2 ·

3 Default Reasoning

The term default reasoning is used in AI for patterns of in­ ference that permit drawing conclusions suggested, but not entailed, by the knowledge available to the system. More specifically, default reasoning is a general approach, within the knowledge-based systems framework, for solving the problem of reasoning in the presence of incomplete information. This is usually done by augmenting the "true" knowledge the agent is given about the world with a set of default assumptions that capture what is "typically" the case. When presented with a query, the inference produced should agree with the true world knowledge and some subset of the default assumptions, and at the same time support our intuition about a plausible conclusion.

2 Classification noise [Angluin and Laird, 1988] occurs when there is some probability 'T/ (the error rate) that the label of an example is flipped (from 0 to I or vice versa). Most learning algo­ rithms known can tolerate classification noise with error rate 'T/ < 1/2 [Keams, 1993].

Attempts to represent and reason with defaults have en­ countered many problems (e.g., [Neufeld, 1989; Poole, 1989; Geffner, 1990]). In many cases, reasoning with "accept­ able" defaults lead to unacceptable conclusions. Problems occur whenever defaults interact, and can be characterized fre­ quently as problems of distinguishing "good" defaults from "bad" ones. But, reasons for deciding between good and bad defaults vary, and in most cases depend on the situ­ ation. No general method exists according to which one can rank defaults [Geffner, 1990]. The only way to fig­ ure out why and when certain defaults are preferred to oth­ ers is to understand what the defaults say about the world. While probabilistic and statistical approaches [Geffner, 1990; Bacchus et al., 1993] present an important step in this direc­ tion, they still suffer from some of the same problems [Geffner, 1994], and are infeasible computationally.

The approach developed here does not use defaults. Rather, it is a theory of inference. It reasons from a knowledge repre­ sentation into which the "incompleteness" is compiled via a learning process. As we show later, in Section 3.1, there is no direct mapping between the way default reasoning problems have been traditionally defined and our framework. In order to exhibit the advantages of our approach we translate default reasoning problems into Learning to Reason problems: Given a default reasoning problem (i.e., "true" world knowledge and a set of default assumptions) we suggest a scenario of interac­ tions with the world that reflects the type of observations that could have led to this view of the world. These observations are used to learn an attribute-function representation of the world, over {0, 1, * }n. Then, given a query, we argue that this representation yields the sought after response. The fol­ lowing convention is used in presenting the default reasoning examples. The traditional representation is given as a set J{ B of knowledge base rules and a set 11 of default rules. (As usual, penguin( x) --+ bird( x) means that if x is a penguin then x is a bird.) For each problem we present a set of observations about the world. The observations are elements in {0, 1, * }n but we present only a subset of the observed attributes, which is of interest to the current example. As usual, all the unobserved attributes are assigned *·

All the examples discussed below have been studied be­ fore in the literature. The examples, or versions of them, represent various aspects of the non-monotonic reasoning phenomena that have been used over the years as "bench­ marks" for various formalisms. We do not know of any "traditional" formalism that can handle in a satisfying way (efficiently, or even qualitatively) all the aspects presented by those examples. We note, though, that our first exam­ ple is a variant of an example considered in [Valiant, 1994a], and that all the examples we consider here could be con­ sidered also in the Rationality framework and be imple­ mented, in principle, on the Neuroidal Model [Valiant, 1994b; 1994a]. A (partial) list of papers that have discussed (a subset of) these examples includes [Bacchus et al., 1993; Ethering­ ton, 1988; Geffner, 1990; Reiter, 1980; Reiter and G., 1981; Selman, 1990; Touretzky et at., 1987].

Example 1 (Basic Example) Consider the case in which we know that penguins are birds, penguins do not fly, and we have the "default" assumption "birds fly". This is expressed as the set of facts J{ B = {penguin(x)--+ bird(x), penguin(x)--+ fly(x)} and the de­ fault statement 11 = {bird(x)--+ fly(x)}. Given this, it is reasonable to assume that in all observations we made so far of the world, whenever we saw an observation in which the penguin attribute was 'on' (set to 1) the bird attribute was 1 as well and the fly attribute was set to 0. Moreover; we have seen observations in which bird was 1 and fly was 1. In those observations, penguin was never 1. That is, a plausible sequence of observations could be:

(bird= 1, penguin= 1, fly= 0) (bird = 1, fly = 1) (bird= 1, fly= 1, red= 1) (bird= 1, fly= 1, red= 0) (bird = 1, penguin = 0, fly = 1, has_beak = 1) (bird = 1, fly = 1, has_beak = 1) (bird = 1, penguin = 1, fly = 0, has_beak = 1)

Given these observations the attribute function an agent would keep for fly is !fly = (bird = 1) 1\ (penguin = 0 or *) 1\ (has_beak = 1 or * ). Consider now a query re­ garding Tweety, rq((bird = 1), fly=?). In this case, all we know is that Tweety is a bird (that is, in this observation, the only observed attribute is bird), and evaluating /fly yields the prediction fly = 1.

Along with seeing many observations similar to the above, the agent could have also seen a small number of observations like (bird= 1, fly= 0) 3 . The framework supports this, even though a deterministic representation is used for the attribute functions. These cases are viewed as classification noise, where the value supplied by EX(D) for the function /fly is false. Therefore, in this model, the algorithms used to learn attribute functions should tolerate classification noise. Since in Section 4 we show that this is indeed the case, we will not incorporate misclassified observations in the next examples.

Example 2 (Specificity) Consider the observations dis­ cussed in Example 1 and assume a query about the penguin Tweety: rq( (bird= 1, penguin= 1), fly =?). In this case, evaluating !fly yields the prediction fly = 0. That is, we conclude that Tweety does not fly, even though Tweety is a bird, and birds (when no other; more specific, information is known) fly.

Example 3 (Irrelevance-I) Consider the observations dis­ cussed above and assume a query about the red bird Tweety: rq( (bird = 1, red = 1), fly =?). Clearly, the observations show that the attribute red is irrelevant to the function /fly and evaluating it therefore yields the prediction fly(Tweety) = 1.

Of course, an agent active in a green birds nature reserve might "be trained" on a different set of observations consist­ ing of (almost) only green birds. Consequently, she might believe that "greenhood" is a necessary property of flying birds, that is, she might have !fly = (bird = 1) 1\ (green = 1) as the attribute function for fly. There is no contradiction here; these are exactly the type of reasoning patterns the sought after theory should possess.

Example 4 (Irrelevance-II) Consider the observations dis­ cussed above and a query about the penguin Tweety:

3 Those observations cannot be the majority of the observations seen, since still, when all we know about Tweety is that it is a bird, we think it flies.

rq( (bird = 1, penguin = 1), has_beak =?). Here, prediction is done by evaluating !has-beak· Note that there is no relation between the attribute functions /bas_beak and /fly· These are acquired in parallel and the fact that penguins have special properties with respect to flying does not mean they need to have exceptional properties with respect to "having a beak". Clearly, the observations lead to fhas_beak = (bird = 1 ), and evaluating it yields has_beak = 1.

We note that while the conclusion above is very intuitive, it is not supported by many treatments of default reasoning (e.g., [Kraus eta!., 1990]), which encounter difficulties in trying to support both specificity and irrelevance.

Example 5 (Multiple Extensions) Consider the set of facts [{ B = {bat( x) --> mammal( x)} and default statements ~ = {mammal(x)--> fly(x), bat(x)--> fly(x), dead(x)--> fly(x)}. Given that, it is reasonable to assume that the observations made of the world had the following properties: in observa­ tions with a bat attribute set to 1, the mammal attribute was 1 as well; we have observed bats that fly but also mammals that do not fly; in the latter case, bat was not 1; also, we have not seen dead things fly. Therefore, a plausible set of observations could be:

(mammal= l,bat= 1,fly= 1) (bat = 1, fly = 1) (mammal = 1, fly = 0) (mammal= 1, bat= 0, fly= 0, red= I) (dead= 1) (mammal = 1, bat = 0, dead = 1) (bat = 1, dead = 1) (bat= 1, dead= 1, fly= 0)

Here, the attribute function an agent would keep for fly 4 is /f!y (bat = 1) 1\ (dead = 0 or * ). Con­ sider now a query regarding Dracula, presented as: rq( (bat = 1, dead = 1), fly =?). Clearly, evaluating /f!y on this observation yields the prediction fly( Dracula) = 0. In case all we know is that Dracula is a bat and we do not know that it is dead (that is, dead=*) the query is rq(bat = 1, fly =?) and evaluating !fly yields the prediction fly( Dracula) = 1.

As before, there is no contradiction here; these are exactly the type of reasoning patterns the sought after theory should pos­ sess. The traditional treatment runs in this case into problems of conflicting defaults. For example, one has to decide which of the default rules, bat( x) --> fly( x) or dead( x) --> fly( x) to apply in order to predict the value of fly(Dracula).

Example 6 (Preferences) Assume the default statements are given by~= {student(x)--> employed(x),

adult(x) --> employed(x), student(x)--> adult(x)} and the set of facts is empty. These defaults were written in this way to reflect a situation in which the agent observes the following properties: in observations in which the student aitribute was set to 1 the employed attribute was not set to 1; in observations in which the student attribute was set to 1 the adult attribute was not set to 0; in observations in which the adult attribute was set to 1, the employed attribute was not set to 0, unless some other information is given. The following observations could have been seen by the agent:

(student= 1, employed= 0)

4 We could disjunct it with the function from Example I, but will assume, for clarity, that those are different agents.

(student = 1, adult = 1) (employed = 1, adult= 1) (student = 0, employed = 1, adult = 1) (student= 1, employed= 0, adult= 1)

Given these observations, the attribute function an agent would keep for employed is !employed = (adult = I) 1\ (student = 0 or * ). On the other hand, these observations do not give us enough information to support prediction of the attribute adult in a simple way (see below).

Many other problems can be handled in a natural way, just as the problems considered above. In particular, this approach suggests a natural solution to the frame problem, which is concerned with how to indicate which aspects of the world do not change when an action takes place [Mc­ Carthy and Hayes, 1969]. While the standard non-monotonic reasoning formalisms do not capture the desirable behavior, that things stay as they are [Hanks and McDermott, 1986], our representation of incomplete information does so [Roth, 1995].

What is most striking about these examples is not only the fact that these examples, with which various default reason­ ing formalisms struggle, have a unified representation in our framework, but even more so:

Observation 1 In all the cases presented above the attribute function for the attribute of interest can be represented as a conjunction over {0, 1, * }n.

It is an empirical question whether there are naturally arising reasoning problems in which the sought after attribute cannot be represented as a simple function over {0, 1, * }n. It is ex­ pected, for example, that in situations traditionally presented by a large set of interacting defaults, the resulting attribute function might be more complicated. However, even in this case, reasoning reduces to function evaluation and is thus computationally easy. In Section 4 we show that we can actu­ ally learn to reason with function classes which are far more expressive than is needed in the examples discussed above.

3.1 Relations to Other Formalisms

There is no direct mapping between our treatment of in­ complete information and traditional formalisms for default reasoning. As an example, consider the case of preferred interpretations [McCarthy, 1980; Selman and Kautz, 1990; Papadimitriou, 1991]. There, a theory <1> and a set~ of de­ faults are given. The theory defines a set of possible models, and the default rules define a preference relation (a partial order) on those. Once a preferred model is found, inference is done by evaluating queries in this model. While this for­ malism leads to some intriguing mathematical problems, we argue that one need not solve those in order to reason in a way that agrees with the incomplete "default" information.

Consider Example 6. There, no minimal model exists that can capture the "intuitive" inference with respect to all the at­ tributes. Given the observations, the attribute function for em­ ployed is !employed = (adult = 1) 1\ (student = 0 or *). These observations, however, do not support a conjunction as an at­ tribute function for adult, but rather the following DNF-like function: !adult= ((employed= 1) 1\ (student= 0 or *)) V ( (employed = 0 or *) 1\ (student = 1)) . Therefore, in this case, using a single model in {0, l}n to characterize the sit­ uation, does not support the "intuitive" conclusion. (While making the problem harder computationally.) Instead, our ap­ proach uses the available data to learn the situations in which a specific attribute is "on". This can always be done, and the only question remains is how complex is the representation and whether it can be learned efficiently.

4 Learning to Reason

Reasoning with respect to an attribute x j is reduced in this framework to evaluating the attribute function fi on a total vector in {0, 1, *}n-l. Assume that our attribute functions are in a class :F of Boolean functions over {0, I , * }n. If we have efficient learning (to classify) algorithms for :F that can tolerate classification noise, we can Learn to Reason with :F.

It turns out that many of the existing learning algorithms for Boolean functions studied in computational learning the­ ory (see a survey in [Blum et at. , 1994]) can be extended to learning algorithms over {0, 1, * }n. Since in all the examples considered in Section 3 we used the oracle EX( D) only we start by considering learning from examples only.

We extend the standard elimination algorithm for learning conjunctions [Valiant, 1984] to work over {0, 1, * }n. In this case the values assigned to the variables are non-empty sub­ sets of { 0, l , *} ratherthan of { 0, I} , as is usually the case. In the usual elimination algorithm the convention is that when a variable x; is allowed to have any value in {0, 1 }, we omit it from the conjunctive representation. We use the same conven­ tion here. Moreover, we use this convention for variables that have never been observed. In order for variables that have not been observed yet (i .e., never appeared as 0 or 1) not to appear in the conjunctive representation, the algorithm uses the first positive example to initialize its hypothesis. From then on, it (I) adds to the conjunction only newly observed attributes, and (2) uses elimination over the set of known attributes. It can be shown that this procedure provides a mistake bound, and therefore a pac algorithm for Boolean conjunctions over {O, l , *}n.

Using the techniques introduced in [Kushilevitz and Roth, 1995] we can show how to learn kDNF and kCNF formulae over { 0, I , *} n , for any fixed k. Moreover, these algorithm are shown to tolerate noise, and thus can be used to construct L2R algorithms. To summarize (see [Roth, 1995]):

Theorem 1 Let :F be the class of conjunctions, disjunctions, kCNF and kDNF formulae over {0, 1, * }n. Then, there ex­ ists an efficient and noise tolerant PAC-L2R ( MB-L2R, resp.) algorithm for the reasoning problem RQ(:F) , that uses the example oracle EX(D) ( RQ n(fi ), resp.).

A richer class of functions can be learned when given ac­ cess to membership queries, in addition to examples [Angluin, 1988; Blum e.t at. , 1994; Bshouty, 1993]. Many of these algo­ rithms can be extended to work over {0, l , * }n. In particular, using the algorithms studied in [Bshouty, 1993] we have:

Theorem 2 There exists an efficient PAC-L2R algorithm that uses RQ D (fi) and M Q(fj ), for the reasoning problem RQ(:F) where

(i) :F is the class of Decision Trees over {0, 1, * }n. (ii) :F is the class of log nC N F n DN F over {0, 1, * }n.

We have discussed a knowledge representation that con­ sists of a collection of attribute functions. Using our inter­ pretation of incomplete information it can be shown [Roth,

1995] that other representations can support the reasoning be­ havior demonstrated in this paper. Consequently, different learning questions may arise, the reasoning algorithms might be more complicated, and one can also pose more general queries 5 . In particular, it can be shown that the algorithms used in [Khardon and Roth, 1994b] to learn model-based rep­ resentation can be extended to work over {0, I , * }n. Together with the incomplete information interpretation suggested here this yields the sought after non-monotonic behavior.

5 Discussion

We have presented a new approach to the problem of rea­ soning with incomplete information. The main premises of our approach are that (1) It views reasoning as an inductive phenomenon: by interaction with the environment the intel­ ligent agent inductively learns a representation of the world and uses it to respond to queries. The performance on the reasoning task is measured in a way that makes explicit the dependence of the reasoning performance on the input from the world. (2) Missing information in the interaction of the agent with the environment is taken to be as informative as observed information.

We have formulated the problem of reasoning with incom­ plete information as a problem of learning attribute functions over the domain {0, 1, * }n. This formulation can tolerate ob­ servations that are inconsistent; these are handled as noisy input to the learning algorithm. Moreover, multiple levels of specificity of information, irrelevant information and "con­ flicting" observations are handled in a natural way to yield conclusions that match our intuition. These issues determine the complexity of the attribute-function representation. But, efficient and noise tolerant learning algorithms exist even for function classes over {0, 1, * }n that are far more expressive than was required in the "bench-marks" examples considered.

We view the large body of research on defeasible theories of reasoning as an attempt to characteri~e the type of defeasible reasoning people do. While there is today some understand­ ing of human-like patterns of reasoning, we believe that no "definition" can be given for the type of behavior expected, given an "abstract" representation of partial knowledge as a starting point. The Learning to Reason framework suggests an "operational" approach to studying reasoning that is never­ theless rigorous and amenable to analysis. As we have argued here, it can be shown to match our expectations in cases in which the reasoning problem is well defined.

This work suggests several areas in which further theoreti­ cal study is needed, as well as some interesting questions for empirical study. Studying other forms of interaction in the learning process, extending the framework to a probabilistic domain, and efficient learning in the presence of irrelevant attributes, are some of the theoretical questions whose study will help develop and substantiate the claims made here.

As mentioned before, determining how complex the at­ tribute functions in naturally arising reasoning problems are, and whether those can indeed be represented as simple func­ tions over { 0, 1, * }n, is an important empirical question. Perhaps the major difference between the knowledge-based sys­ tem approach to reasoning and the Learning to Reason ap­ proach is that our approach suggests that in order to make theories of reasoning work in practice, we need to train them over a large number of examples. Therefore, finding good and large test beds on which to validate this theory is one of the most important next steps.

5 More "general" queries are queries with respect to more than a single attribute. Notice, however, that the reasoning tasks considered in most of the default reasoning literature are "prediction tasks", queries with respect to a single attribute, as we do here.