Outlier Detection Using Default Logic

1 Introduction

Default logics were developed as a tool for reasoning with in­ complete knowledge. By using default rules, we can describe how things work in general and then make some assumptions about individuals and draw conclusions about their properties and behavior.

In this paper, we suggest a somewhat different usage of default logics. The basic idea is as follows. Since default rules are used for describing regular behavior, we can exploit them for detecting individuals or elements who do not behave normally according to the default theory at hand. We call such entities outliers. An outlier is an element that shows some properties that are contrary to those that can be logically justified.

Outlier detection can be useful in several application con­ texts, e.g., to single out exceptional behaving individuals or system components. Note that according to our approach, ex­ ceptions are not explicitly listed in the theory as "abnormals," as is often done in logical-based abduction [Poole, 1989;

Luigi Palopoli

DIMET

Univ. di Reggio Calabria Loc. Feo di Vito 89100 Reggio Calabria, Italy palopoli@ in g. unirc.it

Console et a!., 1991; Eiter and Gottlob, 1995]. Rather, their "abnormality" is singled out exactly because some of the properties characterizing them do not have a justification within the theory at hand. For example, suppose that it usu­ ally takes about two seconds to download a one-megabyte file from some server. Then, one day, the system is slower - instead four seconds are needed to perform the same task. While four seconds may indicate a good performance it is helpful to find the source of the delay. Another example might be that someone's car brakes are making a strange noise. Al­ though they seem to be functioning properly, this is not nor­ mal behavior and the car should be serviced. In this case, the car brakes are outliers and the noise is their witness.

Outlier detection can also be used for examining database integrity. If an abnormal property is discovered in a database, the source who reported this observation would have to be double-checked.

Detecting abnormal properties, that is, detecting outliers, can also lead to an update of default rules. Suppose we have the rule that birds fly, and we observe a bird, say Tweety, that does not fly. We report this occurence of an outlier in the theory to the knowledge engineer The engineer investigates the case, finds out that Tweety is, for example, a penguin, and updates the knowledgebase with the default "penguins do not fly."

In this paper, we formally state the ideas briefly sketched above within the context of Reiter's default logic. For sim­ plicity, we concentrate on the propositional fragment of de­ fault logic although the generalization of such ideas to the realm of first-order defaults also worth exploring. So, when­ ever we use a default theory with variables, as in some of the following examples, we relate to it as an abbreviation of its grounded version.

The rest of the paper is organized as follows. In Section 2, we give preliminary definitions as well as a formal def­ inition of the concept of an outlier. In Section 3, we de­ scribe the complexity of finding outliers in propositional de­ fault logic. Section 4 analyzes the complexity of detecting outliers in disjunction-free propositional default logics, and section 5 describes some tractable cases. Related work is dis­ cussed in Section 6. Conclusions are given in Section 7.

Because of space limitations, throughout the paper proofs of results are sketched or omitted. Full proofs can be found in [Angiulli eta!., 2003].

2 Definitions

In this section we provide preliminary definitions for concepts we will be using throughout the paper.

2.1 Preliminaries

The following definitions will be assumed. LetT be a propo­ sitional theory. Then T* denotes its logical closure. If S is a set of literals, then ·S denotes the set of all literals that are the negation of some literal in S .

Default logic was introduced by Reiter [Reiter, 1980]. A propositional default theory 6. is a pair (D, W) consisting of a set W of propositional formulas and a set D of default rules. A default rule <5 has the form 7 (or, equivalently, ¢ : 1/J / x). where ¢, 'l/J and X are propositional formulas, called, respec­ tively, prerequisite, justification, and consequent of <5. The prerequisite could be omitted, though justification and conse­ quent are required. If 'l/J = x. the default rule is called normal. The informal meaning of a default rule <5 is the following: if ¢ is known, and if it is consistent to assume 'l/J, then we con­ clude X· An extension is a maximal set of conclusions that can be drawn from a theory. An extension E of a proposi­ tional default theory 6. = (D, W) can be finitely character­ ized through the set DE of generating defaults forE w.r.t. 6. , i.e., the set DE={¢: 'l/J /x ED I¢ E E /\ · 1/J ~ E}. Indeed, E = (W U {X I¢: 'l/J/x E DE})* .

Let 6. be a default theory and l a literal. Then 6. I= l means that l belongs to every extension of 6.. Similarly, for a set of literals S, 6. I= S means that every literal[ E S belongs to every extension of 6.. A default theory is coherent if it has at least one extension.

We review some basic definitions about complexity theory, particularly, the polynomial hierarchy. The reader is referred to [Garey and Johnson, 1979] for more on complexity the­ ory. The classes I;f and IIf are defined as follows: I;{; = II{; = P and for all k 2: 1, I;f = NPEf_ 1 , and IIf = co-I;f. ~f models computability by a nondeterministic polynomial­ time algorithm which may use an oracle, loosely speaking a subprogram that can be run with no computational cost, for solving a problem in I;f_ 1 . The class Df, k 2: 1, is de­ fined as the class of problems that consists of the conjunction of two independent problems from I;f and IIf, respectively. Note that for all k 2: 1, I;f ~ Df ~ ~f+1 . A problem A is complete for the class C iff A belongs to C and every problem in C is reducible to A by polynomial-time transfor­ mations. A well known I;f -complete problem is to decide the validity of a formula QBEk,3· that is, a formula of the form 3Xl VX2 ... QXkj(X1 , .. . , Xk) . where Q is 3 if k is odd and is v if k is even, xl' ... 'xk are disjoint set of variables, and j(X1, ... , Xk) is a propositional formula in X1 , .. . , Xk . Analogously, the validity of a formula QBEk ,'<l· that is a for­ mula of the form VX13X2 ... QXkf(X1, . . . , Xk). where Q is V if k is odd and is 3 if k is even, is complete for IIf. De­ ciding the conjunction <I>/\ 'II, where <I> is a QBEk,3 formula and 'II is a QBEk,'<l formula, is complete for Df.

2.2 Defining outliers

Next we formalize the notion of an outlier in default logic. In order to motivate the definition and make it easy to understand, we first look at an example.

Example 2.1 Consider the following default theory which represents the knowledge that birds fly and penguins are birds that do not fly, and the observations that Tweety and Pini are birds and Tweety does not fly.

This theory has two extensions. One extension is the logical closure of W U { Bird(Pini), ·Fly(Pini)} and the other is the logical closure of W U { Bird(Pini) , Fly(Pini )}.

If we look carefully at the extensions, we note that Tweety not flying is quite strange, since we know that birds fl y and Tweety is a bird. Therefore, there is no apparent jus­ tification for the fact that Tweety does not fly (other than the fact ·Fly(Tweety) belonging to W). Had we been told that Tweety is a penguin, we could have explained why Tweety does not fly. But, as the theory stands now, we are not able to explain why Tweety does not fly, and, thus, Tweety is an exception. Moreover, if we are trying to nail down what makes Tweety an exception, we notice that if we would have dropped the observation ·Fly(Tweety) from W, we would have concluded the exact opposite, namely, that Tweety does fly. Thus, ·Fly(Tweety) "in­ duces" such an exceptionality (we will call witness a literal like ·Fly(Tweety)). Furthermore, if we drop from W both ·Fly (Tweety) and Bird(Tweety), we are no longer able to conclude that Tweety flies. This implies that Fly(Tweety) is a consequence of the fact that Tweety is a bird, and thus Bird(Tweety) is the property ofTweety that behaves excep­ tionally (or the outlier).

From the above example, one could be induced to define an outlier as an individual, i.e., a constant, in our case Tweety, that possesses an exceptional property, denoted by a literal having the individual as one of its arguments, in our case Bird(Tweety) . However, for a conceptual viewpoint, it is much more general and flexible to single out a property of an individual which is exceptional, rather than simply the indi­ vidual. That assumed, we also note that within the proposi­ tional context we deal with here, we do not explicitly have individuals distinct from their properties and, therefore, the choice is immaterial.

Based on the example and considerations mentioned above, we can define the concept of an outlier as follows.

Definition 2.2 Let 6. = (D, W) be a propositional default theory such that W is consistent and l E W is a literal. If there exists a set of literals S ~ W such that:

where Ws = W \Sand Ws,z = Ws \ {l}, then we say that l is an outlier in 6. and S is an outlier witness set for l in 6..

According to this definition, a literall is an outlier if and only if there is an exceptional property, denoted by a set of literals S, holding in every extension of the theory.

The exceptional property is the outlier witness for l . Thus, according to this definition, in the default theory of Example 2.1 above we should conclude that Bird(Tweety) denotes an outlier and { -,Fly(Tweety)} is its witness. Note that we have defined an outlier witness to be a set, not necessarily a single literal since in some theories taking a single literal does not suffice to form a witness for a given outlier being that all witnesses of such an outlier have a cardinality strictly larger than one.

Example 2.3 Consider the default theory .6. = (D, W), where the set of default rules D conveys the following infor­ mation about weather and traffic in a small town in southern California:

• J Julyi\Weekend:-:Traflic Ja~II~Rain _ that is normally · ~Trall·c-Jamii~Ratn ' during a July weekend there are no traffic jams nor any rain.
• 2 JanuarrRain January:_~Rain -in January it sometimes · Ram ' ~Ratn rains and sometimes it doesn't rain.
• 3 W eekend!ITralfic Jam:AccidentVRain _If there is a traf-. AcctdentV Razn . . fie jam in the weekend then normally it must be rammg or there would have been an accident.

Suppose also that W ={July, Weekend, Traffic_Jam, Rain}. Then, the setS = {Traffic_lam, Rain} is an outlier witness for both Weekend and July. Moreover, S is a minimal outlier witness set for either Weekend or July, since deleting one of the members from S will render S not being a witness set.

Here is another example.

Example 2.4 Consider the following default theory .6.:

D _ { Income(x)IIAdult(x):Works(x)

-

Works(x)

'

FlyingS x :I nterestTakeO I I x

InterestTakeOII x

FlyingS(x) :InterestN avigate(x) }

InterestN avigate(x)

W = {Income(Johnny), Adult( Johnny),

..., W arks( Johnny), FlyingS( Johnny),

...,[ nterestTakeO f f (Johnny)}

This theory claims that normally adults who have a monthly income work, and students who take flying lessons are inter­ ested in learning how to take off and navigate. The observa­ tions are that Johnny is an adult who has a monthly income, but he does not work. He is also a student in a flying school but he is not interested in learning how to take-off. Based on the events of September 11, 2001, we'd like our system to conclude that Johnny is the argument of two outliers. Indeed, the reader can verify that the following facts are true:

1. (D, W~InterestTakeOff(Johnny)) F InterestTakeO f !(Johnny),

Hence, both -,Works(Johnny) and ...,[ nterestTakeO f f (Johnny) are outlier witnesses, while Adult(Johnny) and FlyingS(Johnny) are outliers. Note that Income(Johnny) is also an outlier, with the witness -,Works(Johnny).

2.3 Defining outlier detection problems

In order to state the computational complexity of detecting outliers, in the rest of the work we refer to the following prob­ lems (also referred to as queries) defined for an input default theory .6. = (D, W):

• QO: Given .6., does there exist an outlier in .6. ?
• Ql: Given .6. and a literal[ E W, is there any outlier witness for l in .6. ?
• Q2: Given .6. and a set of literals S ~ W, isS a witness for any outlier l in .6. ?
• Q3: Given .6., a set of literals S ~ W, and a literal[ E W, is S a witness for l in .6. ?

3 General complexity results

In this section we analyze the complexity associated with de­ tecting outliers. First, we give some preliminary definitions involving notation.

Let L be a set of literals such that i E L implies that ...,£ (j. L. Then we denote by 'h the truth assignment on the set of letters occurring in L such that, for each positive literal p E L, 7L(p) = true, and for each negative literal 'P E L, 7L(p) =false.

LetT be a truth assignment on the set x 1 , ... , Xn of letters. Then we denote by Lit(T) the set of literals {£1 , .. . ,in}. such that £; is x; if T(x;) = true and is 'Xi if T(xi) false, fori = 1, ... , n.

Theorem 3.1 QO is I:f -complete.

Proof: (Membership) Given a a theory .6. = (D, W), we must show that there exists a literal[ in W and a subset S = {s1 , ··. ,sn} ofW such that (D, Ws) f= ..,811\ ... /\ 'Sn (query q') and (D, Ws,t) ~ ..,811\ ... I\ Sn (query q"). Query q' is IIf -complete, while query q 11 is I:f -complete [ Gottlob, 1992; Stillman, 1992]. Thus, we can build a;olynomial-time nondeterministic Turing machine with a I: 2 oracle, solving query QO as follows: the machine guesses both the literal l and the set S and then solves queries q' and q 11 using two calls to the oracle.

(Hardness) Let~ = 3XW3Z f(X, Y, Z) be a quantified boolean formula, where X = X1, ... , Xn, Y = Y1, · .. , Ym. and Z are disjoint set of variables. We associate with ~ the default theory .6.(~) = (D(~), W(~)), where W(~) is the set { l, s1, 81, ... , Sn, Sn} consisting of new letters distinct from those occurring in~. and D(~) = D1 U D2 U D3 U

where also o:, (3, g, e1, ... , en are new variables distinct from those occurring in <I> . Clearly, W (<I>) is consistent and ~ (<I>) can be built in polynomial time. We next show that <I> is valid iff there exists an outlier in ~(<I>).

In the rest of the proof we denote by a(8;) (a(x;) resp.) the literal x; (8; resp.) and by a(8;) (a( ..,x;) resp.) the lit­ eral ..,x; (8; resp.), for i = 1, ... , n. Letting S be a sub­ set of {8!,81, ... ,8n,8n} ({x!,..,Xl,····Xn,..,Xn} resp.), we denote by a(S) (a(S) resp.) the set {a(8) I 8 E S} ( {0'(8) I 8 E S} resp.).

(=?) Suppose that <I> is valid. Then we can show that l is an outlier in ~ (<I>). As <I> is valid, then there exists a truth assignment Tx on the set X of variables such that Tx satisfies 'v'Y3Z f(X, Y, Z). Let S = a(Lit(Tx )). It can be shown that we can associate to each truth assignment Ty on the set Y of variables, one and only one extension Ey of (D(<I>), W(<I>)s). In particular, Ey 2 Lit(Tx) U Lit(Ty ). As <I> is valid, then -,j(X, Y, Z) '1. Ey and Ey f= ..,s. Furthermore, since there is no other extension of (D(<I>), W(<I>)s). then (D(<I>), W(<I>)s) f= ..,s.

Consider now the theory ( D (<I>), W (<I>) s 1). We note that the literal[ appears in the precondition of ruie <54 , whose con­ clusion g represents, in tum, the precondition of the rules in the set Ds, rules that allow to conclude ..,s, and that l does not appear in the conclusion of any rule of D (<I>). Thus (D(<I>) , W(<I>)s,t) ~ ..,s. Hence lis an outlier in ~(<I>).

( ¢:) Suppose that there exists an outlier in ~ (<I>). It can be sho:vn that the outlier is l. Hence, there exists a nonempty set of literals S ~ W (<I>) - { l} such that S is an outlier witness for l in ~(<I>). It can then be shown that S = { 8~, ... , 8~}. where 8~ is either 8; or 8;, fori = 1, ... , n. Now we show that 'Tu(s) satisfies 'v'Y3Z j(X, Y, Z), i.e. that <I> is valid. For each set L = {el, ... , em}. where ei is either Yi or ..,Yi· for j = 1, ... , m, there exists one extension EL of (D(<I>), W(<I>) - ~)such that EL 2 L . We note also that EL 2 a(S). Thus, m order for l to be an outlier in ~ (<I>), it must be the case that for each set L, -,j(X, Y, Z) '1. Ey i.e., that 'Tu(s)uL satisfies j(X, Y, Z). Hence, we can conclude that <I> is valid. D

Theorem 3.2 Q1 is :Ef -complete.

Proof: The proof is analogous to that used in Theorem 3.1. 0

Theorem 3.3 Q2 is Df -complete.

Proof: (Membership) Given a theory ~ = (D, W) and a subset S = { 81, ... , 8n} ~ W, we should verify that (D, Ws) f= ..,81 1\ ... 1\ ..,8n (statement q') and there exists a literal[ E W such that (D, Ws,1) ~ -,81 1\ ... 1\ ..,8n (statement q"). Solving q' is in IIf. As for statement q", it can be decided by a polynomial time nondeterministic Tur­ ing machine, with an oracle in NP, that (a) guesses both the literall E W and the set DE ~ D of generating defaults of an extension E of (D, Ws,l) together with an order of these defaults; (b) checks the necessary and sufficient conditions that DE must satisfy to be a set of generating defaults forE (see [Zhang and Marek, 1990] for a detailed description of these conditions), by multiple calls to the oracle; and (c) ver­ ifies that ..,81 1\ ... 1\ ..,8n '/. E by other calls to the oracle. It can be shown that the total number of calls to the oracle is polynomially bounded. Thus, Q2 is the conjunction of two independent problems, one in IIf (q') and the other in :Ef (q"), i.e. it is in Df.

(Hardness) Let ~1 = (D1, Wt) and ~2 = (D2, W2) be two propositional default theories such that wl and w2 are consistent, let 81, 82 be two letters, and let q be the statement (~1 F 81 1\ ~2 ~ 82). W.l.o.g, we can assume that ~1 and ~2 contain different letters, the letter 8 1 occurs in D1 but not in wl (and, from the previous condition, not in ~2). and the letter 82 occurs in D2 but not in W2 (and hence not in ~!). We associate with q the default theory ~(q) = (D(q), W(q)) defined as follows. Let D1 = {a~~· I i = 1, . .. , n} and let £1 = {el, ... ,em} ~ wl be all the literals belonging to wl. then D(q) = { 82 1\~;:,8; I i = 1, ... ,n} u {Jj = :~l;i\~yi\v I . - 1 } {J: -!::E.} v J - , ··. , m U uo - ll U D2. and W(q) = wl u w2 u { ..,8 1, 82}' where v and J.L are new letters distinct from those occurring in ~1 and ~2 · and from 8 1 and 8 2 . It can be shown that q is true iff { ..,81} is a witness for some outlier in ~(lj). We ~ote that q is the conjunction of a IIf­ hard and a :E 2 -hard mdependent problems, thus this proves the hardness part.

0

Theorem 3.4 Q3 is Df -complete.

4 Disjunction-free theories

Disjunction-free theories form a significant subset of proposi­ tional default theories because they are equivalent to extended logic programs under stable model semantics [Gelfond and Lifschitz, 1991]. A finite propositional theory~ = (D, W) is disjunction-free (DF in short), if W is a set of literals, and the precondition, justification and consequence of each de­ fault in D is a conjunction ofliterals. As we see below, outlier detection for DF theories is still quite complex.

Theorem 4.1 QO restricted to disjunction-free theories is :Ef -complete.

Proof: (Membership) The membership proof is analogous to that of Theorem 3.1. We note that when disjunction-free theories are considered, q' and q" are co-NP-complete and NP-complete, respectively.

(Hardness) Let <I> = 3X'v'Yf(X, Y) be a quantified boolean formula, where X = x1 , . .. , Xn and Y =

y1, ... , Ym are disjoint set of variables, and f(X, Y) = C1 1\ ... 1\ Cr. with Ck = tk,l v ... v tk,uk, and each tk,1, ... , tk,uk is a literal, fork= 1, ... , r. We associate to <I> the default theory ~(<I>) = (D(<I>), W(<I>)), with W(<I>) the set { l , s1 , s1 , .. . , Sn, sn} of new letters distinct from those occurring in <I>, and D(<I>) = D1 U D2 U D3 U Ds U D~ U D~, where D1, D2, D3 and D5 are the sets of defaults as in The­ orem 3.1 and D~ and D~ are the following sets of defaults:

where also a, fJ, g, e1, ... , en, c1, ... , Cr are new variables distinct from those occurring in <I> . Clearly, W (<I>) is consis­ tent and ~(<I>) can be built in polynomial time. The rest of the proof is similar to that of Theorem 3.1. 0

Theorem 4.2 Ql restricted to disjunction-free theories is ~f -complete.

Theorem 4.3 Q2 and Q3 restricted to disjunction-free theo­ ries are DP -complete.

5 Tractable Cases

In this section, we look for some classes of default theories for which outlier detection is computationally tractable.

Definition 5.1 A default theory is normal mixed unary (NMU in short) iff W is a set of literals and D is a set of defaults of the form I? where y is either missing or a literal and x is a literal.

Definition 5.2 An NMU default theory is normal unary (NU in short) iff the prerequisite of each default is either missing or positive. An NMU default theory is dual normal unary (DNU in shor_t) iff the prerequisite of each default is either missing or negative.

Thus, NMU, NU, and DNU theories have a quite simple structure. In spite of that, the complexity of detecting outliers from these theories remain often quite high, as demonstrated by the following results (proofs are omitted for the sake of brevity).

Theorem 5.3 The following hold over NMU default theo­ ries:

• QO and Ql are ~f -complete.
• Q2 and Q3 are DP -complete.

Theorem 5.4 The following hold over NU and DNU default theories:

• QO and Ql are NP-complete.
• Q2 and Q3 are in P.

Thus, restricting our attention to NMU, NU, or DNU theo­ ries does not suffice to attain tractability of the most general queries QO and Ql. Some further restriction is needed, which is considered next.

Theorem 5.5 ([Kautz and Selman, 1991] [Zohary, 2002])

Suppose ~ is a normal (dual normal) unary default theory. We can decide whether a literal belongs to every extension of ~in time O(n 2 ), where n is the length of the theory.

Definition 5.6 The atomic dependency graph of an NMU de­ fault theory ~ is a directed graph whose nodes are all atoms in the language of ~. and such that there is an arc directed from p to q iff there is a default in ~ in which p or ·p is a prerequisite and q or ·q is a consequence.

Definition 5.7 A normal (dual normal) unary default theory is acyclic iff its atomic dependency graph is acyclic.

Theorem 5.8 Queries QO, Q1, Q2 and Q3, restricted to the class of acyclic NU or acyclic DNU default theories can be solved in polynomial time in the size of the input theory.

Proof: It can be shown that for any acyclic NMU default theory~ = (D, W) such that W is consistent and for any literal[ in W, any minimal outlier witness set for l in ~ is at most 1 in size. Theorem's statement then follows from Theorem 5.5. D

6 Related Work

The research on logical-based abduction [Poole, 1989; Con­ sole et al., 1991; Eiter and Gottlob, 1995] is related to out­ lier detection. In the framework of logic-based abduction, the domain knowledge is described using a logical theory T . A subset X of hypotheses is an abduction explanation to a set of manifestations M if TUX is a consistent theory that en­ tails M. Abduction resembles outlier detection in that it deals with exceptional situations.

The work most relevant to our study is perhaps the paper by Eiter, Gottlob, and Leone on abduction from default theories [Eiter et al., 1997]. There, the authors have presented a basic model of abduction from default logic and analyzed the com­ plexity of the main abductive reasoning tasks. They presented two modes of abductions: one based on brave reasoning and the other on cautious reasoning. According to these authors, a default abduction problem (DAP) is a tuple (H, M, W, D) where H is a set of ground literals called hypotheses, M is a set of ground literals called observations, and (D, W) is a default theory. Their goal, in general, was to explain some observations from M by using various hypotheses in the con­ text of the default theory (D, W) . They suggest the following definition for an explanation:

Definition 6.1 ([Eiter et al., 1997]) Let P = (H, M, D, W) be a DAP and let E ~ H . Then, E is a skeptical explanation for P iff

1. (D, WUE) 'p= M, and
2. (D, WUE) has a consistent extension.

There is a close relationship between outliers and skeptical explanations, as the following theorem states. The theorem also holds for ordered semi-normal default theories [Ether­ ington, 1987].

Theorem 6.2 Let~ = (D, W) be a normal default theory, where W is consistent. Let l E W and S ~ W. S is an out­ lier witness set for l iff {l} is a minimal skeptical explanation for ·S in the DAP P = ({l}, ..,s, D, Ws,t)

Hence, we can say that S is an outlier witness for l if l E W, l is a skeptical explanation for S, but still ..,s holds in every extension of the theory.

Despite the close relationship between outlier detection and abduction demonstrated by the above theorem (especially for normal defaults) we believe that there is a significant dif­ ference between the two concepts. In abduction, we have to single out a set of manifestations and a set of potential expla­ nations. Outlier detection, on the other hand, has much more to do with knowledge discovery. The task in outlier detection is to learn who the exceptionals (the outliers), or the suspects, if you wish, are, and to justify the suspicion (that is, list the outlier witnesses).

It also turns out that reducing outlier detection queries to abduction and vice versa is not straightforward, and therefore, when analyzing the computational complexities involved in answering outlier detection queries we have preferred to use the classical Boolean formula satisfiability problems.

7 Conclusion

Suppose you are walking down the street and you see a blind person walking in the opposite direction. You believe he is blind because he is feeling his way with a walking stick. Sud­ denly, something falls out of his bag, and to your surprise, he finds it immediately without probing about with his fingers, as you would expect for a blind person. This kind of behavior renders the "blind" person suspicious.

The purpose of this paper has been to formally mimic this type of reasoning using default logic. We have formally de­ fined the notion of an outlier and an outlier witness, and analyzed the complexities involved, pointing out some non­ trivial tractable subsets. The complexity results are summa­ rized in Table 1, where C-c stands for C-complete. As ex­ plained in the introduction, outlier detection can also be used for maintaining database integrity and completeness.

This work can be extended in several ways. First, we can develop the concept of outliers in other frameworks of de­ fault databases, like System Z [Pearl, 1990] and Circumscrip­ tion [McCarthy, 1980]. Second, we can look for intelligent heuristics that will enable us to perform the involved heavy computational task more efficiently. Third, we can study the problem from the perspective of default theories as a "seman­ tic check toolkit" for relational databases.

Acknowledgements. The authors gratefully thank Michael Gelfond for some fruitful discussions on the subject of the paper.