Simulating Human Inferences in the Light of New Information: A Formal Analysis

Introduction

In everyday life we often use conditionals: We use them to explain facts, e.g., "if it rains then the street gets wet", to state predictions about future events, e.g., "if the air pollution continues, the ozone hole increases" or to reason about counterfactuals: "if Oswald had not shot Kennedy, then someone else would have" e.g., [Byrne, 2007]. From a formal logic perspective we focus on correct inferences and from a cognitive science/psychology perspective we focus on analyzing how logically na¨ıve human reasoners actually do reason. The goal is to develop cognitive models that can predict systematic human reasoning errors. There is a plethora of examples demonstrating that human reasoning does not follow the rules of propositional or first order logic. An example that humans deviate from propositional logic is the famous Wason Selection Task [Wason, 1968]. It demonstrates, in its abstract version, that humans have difficulties with the modus tollens. However, it would be wrong to simply assume that humans make arbitrary errors and may only lack of concentration, motivation, or necessary knowledge. Actually, human, "commonsense", reasoning is very successful in solving most of the problems everybody has to face in ones daily life. Human deviations from classical logic are far from being arbitrary, experiments show systematic deviations of many humans that make similar to identical inferences on the same problems. To explain these findings some researchers turned to probabilistic approaches [Oaksford and Chater, 2007], others to heuristic approaches (for an overview, see [Manktelow, 1999]), and recently others have proposed to analyze other than classical logics [Stenning and Lambalgen, 2008]. The reason for this latter turn is that there are logics that allow for one aspect that propositional logic does certainly not: non-monotonicity. A logic is called non-monotonic if additional information can lead to retract previously drawn inferences. In psychology this ability in the human reasoning process is demonstrated with a core research paradigm: the Suppression Task [Stenning and Lambalgen, 2008]. Consider the following example taken from [Byrne, 1989] where three groups of participants received one of three types of problems: ↵δ (Group 1), ↵βδ (Group 2), and ↵γδ (Group 3):

Most participants (98%) in the study concluded: She will study late in the library. We will write in a succinct formulation for this problem e

only 38% of the participants make a modus ponens inference [Byrne, 1989] and conclude in the γ-case that: She will study late in the library and 62% concluded that: She may or may not study late in the library. This example shows that although the conclusion "she will study late in the library" is still correct, it is suppressed by the γ-conditional, but not by the β- conditional. The effect of the additional β compared to the most simple modus ponens (using ↵δ) is non existent - both groups drew the same percentage of inferences "she will study late in the library". This example demonstrates the human capability to draw non-monotonic inferences: It is not the additional conditional per se but an additional conditional that may hint a reasoner at exceptions of the ↵-conditional leading to a suppressed inference.

There are basically two approaches how a cognitive scientist may try to model the different inferences humans draw in the suppression task by a logical system: S/he can develop a new logic or s/he can investigate what already existing logics may explain. Most researchers from psychology have followed the latter and have investigated specific systems, e.g., System P [Neves et al., 2002; Pfeifer and Kleiter, 2005], weak completion semantics with Łukasiewicz-logic [Dietz et al., 2012] or Kleene-logic [Stenning and Lambalgen, 2008]. Each logic has its own properties and, to the best of our knowledge the relationships between Łukasiewicz (or Kleene) to de-facto standards as Reiter's default logic, or inference with System P, System Z, or the successful approach of c-representations remain unknown. Analyzing the most prominent non-monotonic logics on such core-examples can shed light on these systems as well from a formal perspective.

The goal of this paper is to investigate if and how the different non-monotonic logics differ inferentially between the βand the γ-problems and compare these inferences to human inferences. That is, we switch the usual normative perspective that the system defines the norm the human reasoner is tested against such that we use the human reasoner as norm the systems are tested against. The human reasoner as a norm is given by experimental results. In the following we focus on the results provided by [Byrne, 1989]. A logic that draws the same distinction as humans do is nearer to the human inference process, can be used as a cognitive model and is more cognitively-adequate. And, this can be a first step towards a better understanding of commonsense reasoning and about the human reasoning process in general. It can bring problems from Cognitive Science to Artificial Intelligence and enrich cognitive science modeling by formal techniques from knowledge representation and reasoning.

The rest of the paper is structured as follows: In the next section we introduce some technical preliminaries. Afterwards we introduce five important non-monotonic logics and investigate the inferences for the suppression task. An evaluation and discussion of different approaches with consequences about the associated knowledge bases conclude the article.

Preliminaries

For each conditional "if e then l" the 'e' is called the antecedent and 'l' is called the consequent of the conditional. [Stenning and Lambalgen, 2008] proposed two ways how a formalism can be evaluated: The so-called conceptual cognitive-adequacy and the so-called inferential cognitiveadequacy of a reasoning system. The first investigates if the formal representation of a reasoning system is similar to human mental representations. The second investigates if the inferences a reasoning system draws are similar/identical to the human inferences. Applied to our investigations, everything depends on how we can interpret the conditional (that would be the conceptual cognitive-adequacy) and the inference system that we apply (the inferential cognitive-adequacy). There are different ways how a conditional given in natural language as "if e then l" can be interpreted. The first possibility is to interpret it as material implication (e.g., propositional logic). We write shortly e ! l, whenever we refer to this monotonic interpretation. And there are at least two general ways of how we can extend this by introducing exceptions in a conditional statement. Exceptions can be represented in two ways: (1) In the antecedent, e.g., [Dietz et al., 2012; Stenning and Lambalgen, 2008] for the weak completion semantics. In this case abnormality predicates (ab) capture the exception, i.e., for the example above we write l e^≻ab1. Stenning and Lambalgen call this a "licence for implication". And, these logics use a third truth value: the classical two values like > (for true) or ? (for false), and additionally, u, for unknown. (2) In interpreting the implication; e.g., Reiter's Default logic, System P, System Z, or c-representations. Instead of using the material implication, in commonsense reasoning a conditional represents a notion of plausibility. The classical consequence relation ♣= with e ♣= l represents: if e is true, then l must be true. In contrast the non-monotonic consequence relation [Kraus et al., 1990] use ♣⇠ with e ♣⇠ l meaning: if e is true, then typically l is true as well. Applied to the suppression task e ♣⇠ l does not imply e ^ o ♣⇠ l. Most 'systems' try to characterize ♣⇠ by specific rules (see below).

Other than the material conditional with its monotonic interpretation we use conditionals (B♣A) to express rules that may have exceptions, "if A then usually B". (B♣A) is verified if both the antecedent and consequence are true and falsified if the antecedent is true and the consequent is false. If the antecedent is false, the evaluation of the conditional is undefined and the conditional is not applicable. A conditional is tolerated from a set of conditionals iff there is a world that verifies the conditional and does not falsify any conditional in the set [de Finetti, 1974; Kern-Isberner, 2001].

A knowledge base ∆ in the following is a finite set of conditionals over a language. A knowledge base ∆ is consistent iff for every nonempty subset ∆0 ✓ ∆ there is a conditional (B♣A) 2 ∆0 that is tolerated by ∆0 . This is equivalent to saying that there is a maximal (with respect to set inclusion) partitioning of the knowledge base ∆ = ∆0 ] ▷▷▷ ] ∆m such that each conditional in a partition ∆i 0  i < m is tolerated by the set Smj=i+1 ∆j [Pearl, 1990]. For the β-case of the example above it is ∆β = ¶(l♣e)↪ (l♣t)↪ (e♣>)♦. As humans may interpret the γ-conditional differently, we investigate the following three knowledge bases:

Here, ∆γ is the implementation of the γ-case from the original work of [Stenning and Lambalgen, 2008] with δ2 being the literal meaning of the premise γ. We extend this with two additional implementations, γ 0 and γ 00 , where δ4 encodes the conditional "if she is in the library, the library is/must be open" and δ5 refers to: "if the library is not open, she is not/cannot be in the library". Both are two possible alternative interpretations humans may draw if they read/hear δ2; others are as well possible but we focus exemplarically on these three.

Systems of nonmonotonic reasoning and the suppression task

In this section we briefly introduce some prominent nonmonotonic logics (for an overview of formalizations see Table 2). We test inferences regarding l of these reasoning systems for the γ, γ 0 , and γ 00 -cases. If the logics infer l for these cases then they do for the β-case as well.

We start modeling the Suppression Task with the prominent and de facto standard of inference systems, System P, proceed with logic programming and Reiter's default logic and finally model the task in systems based on ordinal conditional functions (OCF).

1. SystemP

A de-facto standard in nonmonotonic reasoning is System P. It computes a preferential consequence relation ♣⇠ based on the KLM-rules in the table below [Kraus et al., 1990]:

A♣⇠C and B♣⇠C imply (A _ B)♣⇠C

Definition 1 [Goldszmidt and Pearl, 1991] For a given preferential structure (W↪ <) consisting of a set of worlds W and a partial order < on the worlds, we define p-entailment (φ♣⇠ P ) if holds in all <-minimal models of φ.

Whether a formula p-entails another from a knowledge base can be computed by checking whether the knowledge base can be extended consistently with the inverse of the conditional formed from both formulae, formally:

Proposition 1 [Goldszmidt and Pearl, 1996] Let ∆ be a knowledge base and A and B be formulas. Formula A pentails B in the context of ∆ iff ∆[ ¶(B♣A)♦ is inconsistent.

For all three cases, we check whether we can entail l or l from the knowledge base. We check whether ∆γ , ∆γ 0 or ∆γ 00 are inconsistent with (l♣>) or (l♣>), respectively.

In the γ-case, ∆γ [¶(l♣>)♦ is consistent, the world elo, for instance, verifies all conditionals. On the other hand, ∆γ [ ¶(l♣>)♦ is inconsistent since there is no world that verifies at least one of the conditionals and accepts all others. Therefore, in the γ-case we have >♣⇠ P∆γ l and >♣⌧ P∆γ l, and hence 'she will study late in the library'.

In the γ 0 -case, ∆γ 0 [ ¶(l♣>)♦ is consistent, the world elo, for instance, verifies all conditionals. On the other hand, ∆γ 0 [¶(l♣>)♦ is inconsistent since there is no world that verifies at least one of the conditionals and accepts all others. Therefore, in the γ 0 -case we have >♣⇠ P∆γ0 l and >♣⌧ P∆γ0 l, and hence 'she will study late in the library'.

In the γ 00 -case, ∆γ 00 [ ¶(l♣>)♦ is consistent, the knowledge base can be partitioned in the tolerance partitions ∆γ 00 0 = ¶δ1↪ δ3↪ (l♣>)♦ and ∆γ 00 1 = ¶δ5♦. On the other hand, ∆γ 00 [ ¶(l♣>)♦ is inconsistent as there is no world that verifies at least one of the conditionals and accepts all others. Therefore, in the γ 00 -case we have >♣⇠ P∆γ00 l and >♣⌧ P∆γ00 l, and hence 'she will study late in the library'.

In System P we can infer for all three cases ∆γ , ∆γ 0 , ∆γ 00 that 'she will study late in the library'. As a consequence System P does not replicate the suppression effect.

2. Logic programming approaches

Logic programming with a weak completion semantics has been recently successfully applied to the γ-problems of the Suppression Task. As outlined above Stenning and van Lambalgen [Stenning and Lambalgen, 2008] and Dietz and colleagues [Dietz et al., 2012] claim that conditionals should be encoded by "licenses for implications". For example, the conditional if she has an essay to finish, she will study late in the library or short (l e) should be encoded by the clause l e ^ ab1, where ab1 is an abnormality predicate which expresses that l holds if e holds and nothing abnormal is known. In Table 1 two logic programs are presented for the two examples of the Suppression Task [Dietz et al., 2012]. A second aspect is that despite the great success of two valued logics in artificial intelligence or cognitive science, the truth of a statement or premise cannot always be determined and so it might be cognitively plausible to introduce a third truth value, namely unknown/undefined [Łukasiewicz, 1920]. By introducing a third truth value, there are many possibilities for defining truth tables for the connectives [Kleene, 1952; Łukasiewicz, 1920; Fitting, 1985]. The Łukasiewicz logic has the model intersection property [H¨olldobler and Kencana Ramli, 2009], i.e., the intersection of two models is a model. This property entails the existence of least models. The socalled weak-completion semantics process works as follows [H¨olldobler and Kencana Ramli, 2009]:

1. Replace all clauses with the same head by a disjunction of the body elements, i.e., A B1↪ ▷ ▷ ▷ ↪A Bn by A B1 _ ▷ ▷ ▷ _Bn.
2. Replace all occurrences of by$.

The resulting set of equivalences is called the weak completion and the model intersection property holds for weakly completed programs [H¨olldobler and Kencana Ramli, 2009] guaranteeing the existence of a least model.

The abnormality predicates (e.g., ab1) represent abnormal cases: For instance, ab1 is true when the library does not stay open and ab3 is true when she does not have an essay to finish. The logic programs and the inferences can be found in Table 1. The results show that only in the γ-case the WCS does not draw the l-inference, but in the alternative cases γ 0 and γ 00 it can be inferred. The cases γ 0 and γ 00 require additional empirical data from human participants. Weak completion semantics is very sensitive to additional information.

Theorem 1 Cautious monotony does not hold in the weak completion semantics.

Cautious monotony is defined by, if ⇧ ♣= a, ⇧ ♣= b then ⇧ [ ¶a♦ ♣= b. To show that cautious monotony does not hold we adapt an idea of [Baral, 2003, p. 338]. Consider the following program. ⇧ = ¶≻b a↪ c ^ ≻a b↪ a c♦. Then we can infer by weak completion that a and c follow. For ⇧ [ ¶c♦, however, we cannot conclude a anymore. So in this respect the weak completion semantics seems to be a very cautious approach in the class of non-monotonic logics.

3. Reiter's Default Logic

Reiter's default logic [Reiter, 1980] is based on a tuple (W↪D) with a classical background theory W and a set of default rules D = ¶⇠1↪ ⇠2↪ ▷▷▷↪ ⇠n♦ where each default ⇠ = pre(⇠) : just(⇠) cons(⇠) is composed of a precondition (the formula pre(⇠)), a set of justifications just(⇠) and a set of consequences cons(⇠). A default ⇠ is applicable to a deductively closed set Cn(A) iff pre(⇠) 2 Cn(A) and ≻B 62 Cn(A) for every B 2 just(⇠). A (default) process ⇧ is a finite sequence of defaults (⇠⇧1 ↪ ▷▷▷↪ ⇠⇧m ), δ⇧i 2 D for all 1  i  m with the two sets In(⇧) = Cn(W [ ¶cons(⇠)♣⇠ 2 ⇧) and Out(⇧) = ¶≻A♣A 2 just(⇠)↪ ⇠ 2 ⇧♦ such that each default ⇠ is applicable to the In-set of the foregoing defaults. A process is successful iff In(⇧) \Out(⇧) = ; and closed iff every ⇠ 2 D that is applicable to In(⇧) is an element of ⇧. E is an extension of (W↪D) iff there is a closed and successful process ⇧ with E = In(⇧) [Antoniou, 1997]. A formula is inferred credulously from (W↪ D) under Reiter's logic iff it is element of the union of all extensions and sceptically iff it is element of the intersection of all extensions E of (W↪D).

For the suppression task W = ¶e♦ is given. We transfer the implementation for Logic programming [Stenning and Lambalgen, 2008; Dietz et al., 2012] as shown in the previous section to Reiter defaults and obtain the sets

As shown in the process tree in Figure 1, in all cases there is only one extension, hence credulous and sceptical Reiter inference is identical for this task. And l is in every extension of the default logic, and we can credulously and sceptically infer for both tasks that given Dγ , Dγ 0 , and Dγ 00 from the fact that 'she has an essay to write' we can infer that 'she will study late in the library', formally (Reiterc represents the credulous case and Reiter the sceptical case):

4. OCF based systems

An Ordinal Conditional Function (OCF) [Spohn, 2012] is a function  : ⌦ ! N10 assigning to each world ! 2 ⌦ an implausibility rank, that is, the higher (!), the less plausible the world is. Moreover, as a normalization condition, there must be at least one world ! such that (!) = 0. The rank of a formula A 2 L is the minimal rank of all worlds that satisfy A, (A) = min¶(!)♣! ♣= A♦. The rank of a conditional (B♣A) is the rank of the conjunction of premise and conclusion normalised by the rank of the premise, (B♣A) = (AB) - (A).  accepts a conditional (B♣A) (written  ♣= (B♣A)) iff its verification is more plausible than its falsification. The inference relation of OCF is defined using preferential models [Makinson, 1994], defining that B is inferred from A using the OCF , formally A♣⇠ B, iff the verification of the conditional (B♣A) is more plausible than its falsification, iff  accepts the conditional, formally

An OCF can be obtained inductively from a knowledge base. To model the suppression task we use System Z and crepresentations for inductive reasoning.

4a. SystemZ

System Z uses the partitioning of the consistency test of a knowledge base from the preliminaries as a notion of exceptionality. It rates the implausibility of each world by the most exceptional conditional falsified, that is, System Z assigns to each world the maximum partition number which contains conditionals falsified by this world (incremented by 1 because the numbering of partitions is zero-based).

In the γ-case, all conditionals in the knowledge base are put into ∆γ0 . For example, the world elo verifies every conditional in the knowledge base, hence every conditional is tolerated by ∆γ0 . Therefore we get the ranking function which is shown in Table 3. For System Z we have Z∆γ (l) = 0 < 1 = Z∆γ (l), hence it can be derived that 'she will study late in the library'.

In the γ 0 -case, we again have ∆γ 0 0 = ¶δ1↪ δ3↪ δ4♦ because, e.g., the world elo verifies every conditional in the knowledge base which gives the OCF (Table 3): Z∆γ0 (l) = 0 < 1 = Z∆γ0 (l) hence 'she will study late in the library'.

In the γ 00 -case, we have the partitions ∆γ 00 0 = ¶δ1↪ δ3♦ and ∆γ 00 1 = δ5. The OCF (Table 3) is again Z∆γ00 (l) = 0 < 1 = Z∆γ00 (l) hence 'she will study late in the library'. So the System Z does not show the suppression effect.

4b. c-representations

System Z combines conditionals in the knowledge base by their exceptionality. It is known that this approach may lead to neglecting the effect of conditionals (the so-called "Drowning Problem" [Pearl, 1990; Benferhat et al., 1993]). Other than that, the approach of c-representations [Kern-Isberner, 2001; 2004] assigns to each conditional an individual impact -i 2 N0 as abstract weight to each conditional in the knowledge baseR= ¶( 1♣φ1)↪ ▷ ▷ ▷ ↪ ( n♣φn)♦. The rank of a world is the combined impact of all falsified conditionals, so a c-representation c∆ is an OCF defined by

where the individual impacts -i 2 N0 are chosen such that c∆ is admissible with respect to ∆, which is the case if the impacts satisfy the following system of inequations [Kern- Isberner, 2001; 2004]:

Applying c-representations to the γ-case the system of inequations (2) can be solved minimally with the values -1 = 1, -2 = 0 and -3 = 1 which gives us the OCF c∆γ (!) in Table 3. We have c∆γ (l) = 0 < 1 = c∆γ (l) hence 'she will study late in the library'.

In the γ 0 -case, the system of inequations (2) can be solved with the values -1 = 1, -4 = 1 and -3 = 1 which gives us the OCF c∆γ0 (!) in Table 3. We have c∆γ0 (l) = 0 < 1 = c∆γ0 (l) hence 'she will study late in the library'.

In the γ 00 -case, the system of inequations (2) can be solved with the values -1 = 1, -5 = 1 and -3 = 1 hence the OCF is c∆γ00 (!) (cp. Table 3). We have c∆γ00 (l) = 0 < 1 = c∆γ00 (l) hence 'she will study late in the library'. A possibility is to reformulate the knowledge base as we can see in the next subsection.

4c. Mimicking weak completion semantics (WCS)

The weak completion semantics is able to make a difference between the cases β and γ resp. γ 0 . However, as can be seen from Table 1, there is a slight difference already in modelling these cases - the abnormality predicates in cases γ resp. γ 0 are linked to e and o which is not done for case β. We show that we can achieve at least very similar effects to the weak completion semantics by using System Z or c-representations when building them from conditional knowledge bases which mimick the modellings from Table 1. We consider both the modelling obtained from the logic program and the modelling induced by WCS. Instead of putting the evidential information e into the knowledge base, we compute the final results by conditioning the -function obtained from the generic knowledge base by System Z resp. c-representations on e because this simulates better the distinction between generic and evidential knowledge. However technically, in the considered cases, putting e into the knowledge base right from the beginning would not make a significant difference. The computations are very similar to the ones performed in the previous subsections: we summarize the results in Table 4.

In all cases, the most plausible beliefs are the same for System Z and c-representations (there are slight differences in the resulting -functions), so we do not distinguish between these two approaches in the table. In the end, we find that in the β-case, the agent believes el, but in the γ and γ 0 -cases, the agent believes e while no longer being certain about l. Interestingly, this effect is already obtained frommodelling the logic program (without WCS). It is only in the γ-case, that there is a minor difference at all between the belief sets of the knowledge bases with or without weak completion semantics: Here, WCS induces a stronger equivalence between l and o.

Conclusion and Discussion

A core problem in AI, many non-monotonic logics have been evaluated on, is 'Tweety' the famous commonsense reasoning problem about a penguin that is a spoiler for the often accepted statement that birds can fly. A successful AI reasoning system must handle a class/subclass inheritance problem. Another feature relevant in commonsense reasoning among humans is cautious reasoning. Hence, we investigated the suppression task, a core research paradigm in Cognitive Science/Psychology, that shows how humans deal in the light of new information. We evaluated the γ-case (and variations) to test, if humans may have interpreted the second premises differently. Our motivation was two-fold to (1) test the inferences from the different non-monotonic logics for a core problem relevant in cognitive science and, as a subsequent goal, (2) to learn more about the relationships between the logics. We analyzed many of the de-facto standards in NML, like Reiter's default logic, System P, System Z, and crepresentations with human inferences, how they deal with such cautious reasoning problems. To test the inferences (1) we could show that the weak completion semantics, crepresentations and System Z make different inferences for the β and for the γ, γ 0 , and γ 00 -cases. The other systems Reiter's default logic and System P made no distinction for the three investigated representations γ, γ 0 , and γ 00 . However, there could be additional alternative interpretations of the first and second premise. Especially the interpretation of the conclusion of the premise ↵ (Table 1), that is, whether she will stay late in the library, is intricate. By separating this sentence into "staying / working late" and "being in the library" ↵ can be interpreted to be "if she has an essay to write and she stays / works late, then she will be in the library" as well as to be "if she has an essay to write, then she will stay / work late and be in the library". By separating the knowledge in this way, it is possible to trigger hidden background knowledge that (usually) libraries are not accessible 24-hours a day, so "staying late" may trigger an exception to the library being open, if the participant is made aware that it could be otherwise by γ. By using this formalisation, c-revision, i.e., belief revision with c-representations [KernIsberner, 2001] captures the suppression effect and makes as well a difference between the β and γ-cases. The basic idea is that we need to extend the notion of a knowledge base by a temporal order of the information processed by humans. Especially the conceptual-adequacy needs to be further investigated from a formal and cognitive perspective. In the last decade System P has been regarded as a possible candidate for capturing human reasoning [Pfeifer and Kleiter, 2005; Neves et al., 2002]. But, previous empirical research showed that none of the three systems C, CL, and P could be shown to be cognitively-adequate [Kuhnm¨unch and Ragni, 2014], i.e., some inferences are rarely drawn. Additionally, System P does not make any distinction between the β and γ-case, so further research is necessary to test if System P captures human reasoning processes. The formal analysis inspires future empirical research questions and we need to thoroughly investigate the human interpretation of the premises. Regarding the second point: As the Tweety-problem shows differences between the nonmonotonic systems, the suppression task does as well. Although the weak-completion-semantics have not yet, to the best of our knowledge, been formally compared to system-based non-monotonic logics, we derive:

Theorem 2 Weak completion semantics is not contained in Reiter's default logic, System P, Z, and c-representations.

The first two follow from the difference on the suppression task. And the latter two follow from Theorem 1 and from the fact that for System Z and c-representation holds the even stronger principle of rational monotony.

The motivation of this article was to investigate to which extend de-facto standard logics are able to simulate human inference processes and could serve potentially as cognitive models. Some non-monotonic logics seem to be adequate to describe human commonsense reasoning. The investigated de-facto logics have many interesting properties that inspire further empirical research on human reasoning processes, its possible nonmonotonic properties, and allow to develop human-oriented commonsense reasoning AI-systems.

Acknowledgments

This work is supported by DFG-Grants KI1413/5-1 to G. Kern-Isberner and by RA1934 2/1 and a Heisenberg DFG fellowship RA1934 3/1 to M. Ragni. C. Eichhorn is supported by Grant KI1413/5-1.