A Core Method for the Weak Completion Semantics with Skeptical Abduction (Extended Abstract)

1 Introduction

In his seminal paper on the situation calculus, McCarthy 1963 formulated requirements for systems to reason about actions and causality. Besides being able to specify properties as formulas and to draw conclusions as logical consequences he suggested that the formal descriptions of states should correspond as closely as possible to what people may reasonably be presumed to know about them when deciding what to do. In order to meet this latter requirement we need to study humans and their behaviour, which is usually done within Cognitive Science.

In this extended abstract, 1 we are concerned with human reasoning tasks like, e.g., Byrne's [1989] suppression task, Wason's [1968] selection task, or syllogistic reasoning

∗Contact Author

1 This is an extended abstract of an article entitled A Core Method for the Weak Completion Semantics with Skeptical Abduction published in the Journal of Artificial Intelligence Research [Dietz Saldanha et al., 2018].

[Khemlani and Johnson-Laird, 2012]. Firstly, we are interested in finding a declarative, computational logic approach adequately modeling these tasks. Secondly, we would like to embed the computational logic approach in a plausible connectionist network.

The Weak Completion Semantics [H¨olldobler, 2015] is a new cognitive theory which has been successfully applied to various human reasoning tasks. It is rooted in the work by Stenning and van Lambalgen [2008] but corrects a technical bug by switching from three-valued Kripke-Kleene [Fitting, 1985] to three-valued Łukasiewicz [1920] logic [H¨olldobler and Kencana Ramli, 2009].

To illustrate the Weak Completion Semantics consider an example from the suppression task. Suppose we learn that if she has an essay to write then she will study late in the library. Under the Weak Completion Semantics the given conditional is represented by the logic program

where ℓ and e denote that she will study late in the library and she has an essay to write, respectively, and ab1 is an abnormality predicate. The weak completion of the program is obtained by adding the only-if halves of the defined relations, i.e., the relations which appear as conclusions in an implication. In our running example, the relations ℓ and ab1 are defined and, thus, the weak completion of P1 is the set

of equivalences. One should observe that ab1 is now mapped to false. Moreover, the undefined relation e is not mapped to false as it would be under the completion of the program [Clark, 1978].

If we observe that she will study late in the library, then according to Byrne [1989], 71% of the participants concluded that she has an essay to write. This can be computed in the Weak Completion Semantics by explaining the observation via {e ← ⊤} given P1.

Assume additionally, that if she has a textbook to read then she will study late in the library. Under the Weak Completion Semantics the two given conditionals are represented by the logic program

where t denotes that she has a textbook to read, and ab2 is another abnormality predicate, which is also assumed to be false. If we observe again that she will study late in the library, then the previously drawn conclusion is suppressed in that only 13% of the participants concluded that she has an essay to write [Byrne, 1989]. If we apply abduction under the Weak Completion Semantics then the observation can be explained by the two minimal explanations {e ← ⊤} and {t ← ⊤}. Hence, reasoning credulously we would conclude that she has an essay to write. Apparently, humans don't do this; they appear to reason skeptically.

Programs like P1 and P2 as well as their weak completions admit a least model under Łukasiewicz logic which can be computed as the least fixed point of an appropriate semantic operator [H¨olldobler and Kencana Ramli, 2009]. In this context, we are using the operator ΦP for a logic program P which was introduced by Stenning and van Lambalgen [2008].

Semantic operators for logic programs were first studied by Apt and van Emden [1982] in an attempt to capture the semantics of logic programs. In Cognitive Science, semantic operators are interesting as they allow to construct a model for a given program. This construction may be compared to other ways of generating models like, for example, in the theory of mental models [Johnson-Laird and Byrne, 1991]. Suppose we extend the program P1 with the fact e ← ⊤ representing the information that she has an essay to write. The extended program corresponds to the case of modus ponens in the suppression task [Byrne, 1989]. Starting with the empty interpretation, i.e., the interpretation where all relations are unknown, the semantic operator of the Weak Completion Semantics assigns true to e and false to ab1 in its first application because of the positive fact e ← ⊤ and the negative assumption ab1 ← ⊥, respectively. In its second application, the operator additionally assigns true to ℓ because the condition of the rule

is true as soon as e is mapped to true and ab1 is mapped to false. In other words, ℓ being true is an immediate consequence of the rule given that its condition is true. Further applications of the semantic operator do not alter the findings. A least fixed point has been reached. Reasoning with respect to this least fixed point allows to conclude ℓ, which is what 96% of the subjects in the suppression task do.

The semantic operator introduced by Apt and van Emden [1982] is continuous. Funahashi [1989] has shown that continuous mappings can be approximated arbitrary well by feed-forward networks. Combining both results, H¨olldobler and Kalinke [1994] developed the idea to compute semantic operators for propositional logic programs by feed-forward networks. By connecting the output to the input layer, the feed-forward networks are turned into recurrent ones. These recurrent networks compute iterated applications of the semantic operators and, in particular, if they reach a stable state, then this state corresponds to the least fixed point of the semantic operator. In other words, the connectionist networks compute the least models of the given programs. The idea was later extended to first-order programs and called CORE method for connectionist model generation using recurrent networks with feed-forward core [Bader and H¨olldobler, 2006].

The first question to be considered in this paper is: How can the semantic operator associated with the Weak Completion Semantics be represented and computed within a fully connectionist setting? An extension of the CORE method to three-valued Łukasiewicz [1920] logic is not enough to answer this question. We additionally need to extend the network to determine

• whether it has reached a stable state,
• to consider additional facts and assumptions in order to explain a given observation,
• to check whether a given set of integrity constraints is satisfied and
• to eliminate stable coalitions of units that may have arisen from previous reasoning episodes.

However, even with such a network we cannot solve all reasoning episodes of the suppression task. As discussed before, we have to add skeptical abduction. Unfortunately, all known connectionist solutions which we are aware of handle credulous abduction in classical two-valued logic [Ray and d'Avila Garcez, 2006; d'Avila Garcez et al., 2007]. Hence, the second question to be considered in this paper is: How can skeptical abduction be integrated into the connectionist realization of the CORE method? In particular, we will use McCulloch-Pitts [1943] networks to sequentially generate all possible explanations. Possible explanations are forwarded to the CORE network. As soon as an explanation is detected, it will be stored. Once all possible explanations are tested, the skeptical conclusions will be computed.

2 A Schematic View of the Network

Given is a logic program P, its set A of abducibles consists of all facts of the form A ← ⊤ and assumptions A ← ⊥ of atoms A which are undefined in P. Let O be an observation, i.e., a set of literals, and IC be a set of integrity constraints. The goal of the network is to compute the skeptical consequences of P while explaining O and satisfying IC.

In Figure 1 a schematic view of the connectionist network for P, A, O and IC is depicted. It can be divided into four subnetworks:

• NA: a network to sequentially generate all possible explanations given the set A of abducibles.
• N ⟳ P : a recursive network to compute the least model of the semantic operator associated with the weak completion of the program P and a possible explanation.
• NS: a network to compute the skeptical consequences.
• NC: a network to control the process.

The subnetworks are sketched in the following sections. They are specified in full detail in [Dietz Saldanha et al., 2018].

3 Generating Possible Explanations

For a finite (propositional or datalog) program P the set A of abducibles is also finite. The task is to generate a sequence of all possibles explanations, i.e., all subsets of A. This can be formally specified as a finite automaton with state output (Moore machine). McCulloch and Pitts [1943] have shown that each finite automaton with state output can be turned into a connectionist network of binary threshold units receiving an input via its input units and producing an output via its output units. NA is such a network. Whenever prompted by NC it produces the next possible explanation E and forwards it to N ⟳ P . As soon as all possible explanations have been generated, NA informs NC. The network has been improved in the meantime (see Section 7).

4 Computing Least Models

For a finite (propositional or datalog) program P the semantic operator ΦP introduced by Stenning and van Lambalgen [2008] is continuous. Hence, it can be computed by a feedforward network based on the ideas originally developed in [H¨olldobler and Kalinke, 1994]. The network can also be trained via backpropagation based on ideas originally developed in [d'Avila Garcez et al., 1997].

The core of the network N ⟳ P is a feed-forward network with an input, a hidden and an output layer. It computes the semantic operator ΦP∪E for a program P together with a possible explanation E. E has been computed by NA before (see Section 3) and is submitted to N ⟳ P by clamping units occurring in N ⟳ P which are representing E. The feed-forward core is turned into a recurrent network by connecting the units of the output layer to the units of the input layer such that ΦP∪E is applied recursively until a stable state is reached. Such a stable state always exists. It corresponds to the least fixed point of ΦP∪E and the least model of the weak completion of P ∪ E.

Once a stable state has been reached, the control network NC checks whether the stable state explains the observation O and satisfies the integrity constraints IC. If this is the case, then the least model of the weak completion of P∪E is propagated from N ⟳ P toNS. At the same time, the explanation E is withdrawn. As the external clamping of units occurring in N ⟳ P may lead to stable coalitions of units which persist even if the external activation is withdrawn, stable coalitions occurring in the network N ⟳ P must be de-activated before the next possible explanation can be considered. This is achieved by inhibiting the input units of N ⟳ P for three time steps. Thereafter, all units of N ⟳ P are passive.

5 Computing Skeptical Conclusions

The network NS is a two-layer feed-forward network which combines the least models of the weak completion of P ∪ E for all explanations E for the observation O which are satisfying the integrity constraints IC. For each atom A, the network has three input units representing its possible values under Łukasiewicz logic: true, false or unknown. The units in the input layer are self-excitatory. Hence, least models generated by N ⟳ P are stored and persist. The activation of the unit representing that atom A is mapped to true is propagated to the corresponding unit in the output layer if all least models generated by N ⟳ P for the various explanations of O map A to true. Likewise, the activation of the unit representing that atom A is mapped to false is propagated to the corresponding unit in the output layer if all least models generated by N ⟳ P map A to false. Otherwise, A is mapped to unknown.

6 Control

The control network NC controls the process of computing skeptical consequences. In particular:

1. It prompts NA to generate the next possible explanation until NA signals that all possible explanations have been generated. Thereafter, the computation is terminated.
2. As soon as the next possible explanation is generated, it allows NA to propagate the possible explanation E to N ⟳ P by clamping corresponding units occurring in N ⟳ P .
3. It checks whether N ⟳ P has reached a stable state upon which it further checks whether the observation O is explained and the integrity constraints IC is satisfied.
4. If O is explained and IC is satisfied then it allows N ⟳ P to propagate the least model to NS, it withdraws the current possible explanation from N ⟳ P and it forces N ⟳ P to de-activate stable coalitions.

7 FutureWork

Recall from the introduction, that in order to meet McCarthy's 1963 requirements for systems to reason about actions and causalities, we need to study humans and their behavior. It has been previously shown that skeptical abduction is required in order to adequately model a wide range of human reasoning tasks under the Weak Completion Semantics. Motivated by this observation, the main goal of this paper was to specify a plausible connectionist realization of the Weak Completion Semantics, that provides the representation of logic programs, the computation of least models, the interpretation under three-valued Łukasiewicz logic and the derivation of consequences under skeptical abduction.

Lourˆedo Rocha [2017] has added minimality to the approach presented in this paper in that only minimal explanations are considered. Moreover, she has replaced the McCulloch-Pitts networks used to generate all possible explanations in a fixed and pre-defined sequence by Elman [1989; 1990] networks and showed that these networks can be trained to generate all possible explanations in an arbitrary order.

This is a prerequisite for the next step: We do not believe that humans test all possible explanations in a systematic way. From a complexity point of view, skeptical conclusions is exponential in the number of abducibles. If reasoning tasks and, in particular, the sets of abducibles considered in abductive reasoning tasks become larger, then it seems unlikely that humans consider all possible explanations. It appears to us that in particular reasoning episodes some possible explanations are systematically tested whereas others are not considered at all. We believe that there is a kind of attention formalism which identifies those possible explanations, which are really tested. This will lead to a kind of bounded skeptical abduction. But it remains to set up experiments that test this hypothesis and, if our hypothesis is supported, then we need to identify the mechanism which defines the bound and build it into our networks.