Reasoning in Non-Probabilistic Uncertainty^††thanks: Forthcoming with DOI 10.1007/s11023-017-9428-3 in the Special Issue “Reasoning with Imperfect Information and Knowledge” of Minds and Machines (2017). The final publication will be available at http://link.springer.com.^†

LP is a formal system that has been used extensively to model reasoning in a variety of domains, as widely separated as motor control (Shanahan, 2002), and imitative learning (Varga, 2013). Its employment in cognitive modelling grew primarily out of an analysis of discourse processing, in particular of interpretation (van Lambalgen and Hamm, 2004; Stenning and van Lambalgen, 2008; Stenning and Varga, 2016). People take in sentences online, in fractions of a second, and effortlessly update their current discourse model, fully indexed for co-references of things, times and events, and their temporal and causal relations. This may require far-flung bits of background knowledge, retrieved from a huge knowledge base (KB) of semantic memory composed of conditional rules understood as licences for inference. Discourse interpretation involves constructing a preferred or intended model⁴⁴4Intended model is the psychological notion which corresponds to minimal model. Model is to be read as semantic model. Preferred model is the logical notion used by Shoham (1987). Keeping in mind the terms belonging to different fields, we use intended, minimal and preferred as synonyms.⁴ of the context. A crucial application of LP is modelling the efficient inferential retrieval from long-term memory of the relevant cues needed to construct or decide on an interpretation of the state of affairs as basis for, e.g., choosing a course of action.

Following Stenning and van Lambalgen (2008), we view reasoning to be a two-stage process. It starts with reasoning to an interpretation (the computation or retrieval of a meaningful model of the current situation), which may be followed by reasoning from the interpretation. In a typical (i.e. cooperative) conversational context this amounts to computing the model the speaker must have intended to convey. The computation of the intended or preferred model by LP complies with cooperative Gricean principles, but is much more efficient than computing directly with those principles. Imagine you are talking to a friend who is telling you her holiday stories, including an outing into the countryside by car. She says: “And then I press the brake! And then $\dots$”. LP is constructed so that it interprets this utterance online under the assumption that the speaker’s goal is to provide everything the hearer needs to know and nothing more, in order to construct a minimal model of the discourse at each point. At this point that model predicts a continuation of the story consistent with the car slowing down, though this may well be retracted at the next point. It does not consider, without positive evidence, that there might have been ice on the road, or that hers functions differently from all other cars, (or any other defeater). LP with negation-as-failure and Kleene’s strong semantics has shown to be a good candidate for a suitable logic of such cooperative intensional reasoning.

LP conditionals function as ‘licenses for inference’, rather than sentences compounded by the ‘if …then’ connective. They can be thought of as highly content-specialised rules of inference which are always applicable when a clause matches them. But it has the important consequence, already mentioned, that—like natural language conditionals—LP conditionals do not iterate, especially in the antecedent, to produce compound propositions, and do not themselves have truth-values: they are assumed applicable on an occasion unless evidence of exception arises. LP as discussed by Stenning and van Lambalgen (2008) and van Lambalgen and Hamm (2004) formalises a kind of reasoning which uses closed-world assumptions (CWAs) in order to keep the scope of reasoning to manageable dimensions by entities with limited time, storage, and computational resources, though with very large knowledge bases (KBs)—such as we are. Historically, LP is a computational logic designed and developed for automated planning (Kowalski, 1988; Doets, 1994) which is intrinsically preoccupied with relevance—making for an important qualitative difference between LP and classical logic (CL). Returning to the type of communicative situation as just introduced in the car example, discourse processing in LP is cyclical. When a new input sentence arrives, its terms are searched for in the KB. The existing minimal model of the discourse to this point is then updated with any new relevant information, according to CWAs, and the cycle repeats. CL, in contrast, assesses the validity of inferences from premises to conclusions with respect to all possible models of the premises, so the question of relevance does not even arise in CL, except outside the logic in the framing of problems. So LP is not just a poor man’s way of doing what can be done better but with more difficulty in CL—the two different types of logic simply serve different incompatible reasoning purposes, and in this sense are incommensurable.

The basic format of CWAs is the one for reasoning about abnormalities (CWA${ab}_{ab}$), which prescribes that, if there is no positive information that a certain abnormality-event must occur, it is assumed not to occur.⁵⁵5Abnormality is a technical term for exceptions and should not be taken as having any other overtones. Some terminology: in the conditional $p\wedge \neg ab\to q$, $ab$ is the schematic abnormality clause. A distinct $ab$ is indexed to each conditional, and stands for a disjunction of a list of defeaters for that conditional; CWA${ab}_{ab}$ is the CWA applied to abnormality clauses; $\neg$ is the 3-valued Kleene connective, whereas negation-as-failure is an inference pattern that results in negative conclusions by CWA reasoning from absence of positive evidence; falsum ($\perp$) and verum ($\top$) are proposition symbols which always take the values false or true respectively; turnstile ($⊢$) and semantic turnstile ($\models$) are symbols indicating syntactic and semantic consequence respectively. These abnormalities are with respect to the regularity expressed by a conditional; for example, ice on the road causing a car not to stop although the brake is pressed, is an abnormality with respect to the default functioning of brakes. Potential abnormalities are included in the LP meaning of the conditional $\to$, hence what is labeled ‘counterexample’ in CL does not invalidate a conditional inference in LP, it is merely treated as an exception. The conditional has an operational semantics as an operator that modifies truth values of atomic formulas. This is the logical mark of its use as an exception-tolerant ‘licence for inference’. It is represented as $p\wedge \neg ab\to q$; it reads as ‘If $p$ and nothing abnormal is the case, then $q$’. The antecedent $p$ is called the body of the clause, and the consequent $q$ is its head.⁶⁶6Another remark concerning terminology: while in this context the use of the terms ‘head’ and ‘body’ is commonplace in computer science, we will in the following restrict ourselves to ‘antecedent’ and ‘consequent’ in order to maintain homogeneity also with terminology in philosophy and logic.⁶ $p$ and $q$ are composed of atomic formulas, with $q$ restricted to literals (atomic formulas or their negations) and $p$ to conjunctions of literals. The only connectives that may occur in the antecedent are $\wedge$ and $\neg$.⁵

Sets of such conditional clauses constitute a general logic program $P$ (i.e. a program allowing negation in the antecedents of clauses). $P$ can be understood as a recipe for computing a unique model of the discourse it represents, on the basis of information from background knowledge inferentially selected as relevant. Negation in the antecedent requires utilisation of a three-valued semantics.⁷⁷7Cf. (Stenning and van Lambalgen, 2008, chapter 2) for the justification, or the Appendix in (Stenning et al., 2017) for a more succinct version.⁷ We opt for strong Kleene semantics for LP, where the middle truth value u means ‘currently indeterminate’; it is not a graded truth akin to a probability—as in Lukasiewicz three-valued logic—but rather a stage of computation of an algorithm which can evolve towards either 0 or 1. This gives LP the sort of semantic mobility which constitutes a crucial reason for claiming that it can capture the particular kind of nonmonotonic flexibility of reasoning required to deal efficiently with interpretational uncertainty (cf. Section 2.2). Facts $q$ can be represented in logic programs as consequents of tautologies, $\top \to q$ (for simplicity we write only $q$). The CWA${ab}_{ab}$ requires that for an initial interpretation at least, abnormalities are left ‘at the back of the reasoners’ minds’, i.e. outside of the minimal model of $P$. However conditional clauses have conjoined abnormality conditions of the kind $r_1\to a{b}_1,\dots r_n\to a{b}_n$; when evidence of $r_1,\dots r_n$ becomes available, it activates the correspondent $a{b}_k$. If we take $P$ = {If the brake is pressed, the car will slow down}, the fact ‘there is ice on the road’ is not represented in its minimal model because this model disregards all potential abnormalities without explicit evidence. The information in a minimal model includes all that is currently known to be relevant and nothing more than that; the only relevant information is explicitly mentioned or derivable. The derivation capacities of LP’s search of its KB are what achieves this computation of relevance. If new input is that there was a storm last night, then this, together with other information in the KB about local meteorology, may yield an inference that there is ice on the road. The input does not mention ice, but ice on the road is a relevant defeater for braking causing slowing, that we assume is already in the list of defeaters for the brakes conditional. Of course, the new information will lead to many other potential inferences during the sweep through the KB, but if they do not connect with anything in the current model, these inferences will not be added because there is no evidence of their relevance. Sometimes such retrieval can involve several conditional links. This is a computationally explicit example of what psychology knows as ‘spreading activation’ models of memory retrieval, but has been neurally implemented for ‘propositional LP’ as described in (Stenning and van Lambalgen, 2008, chapter 8). Spreading of activation will also be given a slightly different implementation in the neural networks used later in this paper. Such networks will adopt an answer set semantics (Gelfond and Lifschitz, 1991) allowing the use of default negation for implementing CWA explicitly, and classical (sometimes called explicit) negation, which allows for reasoning as intended here, that is, in the absence of a proof of A and its negation, the truth-value of A is ‘currently indeterminate’.

LP models embody much information about stereotypes. For a micro example, it is part of the stereotype of our braking scenario, that the car that is conjured is in motion when the brake is pressed, as developed below. Minimal models are at the intersection between the current input (be that heard language, or observations of any other form) and the reasoner’s background knowledge; they contain all the relevant information and nothing more. In logical terms, they are constructed using the two-step rule of completion ($comp$):

1. take the disjunction $\vee$ of all antecedents $p_1,\dots p_n$ with the same consequent $q$ in program $P$;

2. replace $\to$ with $\leftrightarrow$.⁸⁸8Here, $\leftrightarrow$ denotes a classical biconditional in the object language.⁸

Thus, if $P=\{p_1\to q,\dots p_n\to q\}$, $comp\left(P\right)=\{p_1\vee \dots p_n\leftrightarrow q\}$. The minimal model of $P$ is in fact a model of $comp\left(P\right)$. Such a model does not include information that is either not explicitly mentioned in $P$, or not derivable from it, and in this sense it is minimal. The CWA${ab}_{ab}$ provides the notion of valid inference in LP---an inference is valid if it is truth-preserving with respect to the minimal model of the premises. The contrast with CL is noteworthy: in CL an inference is valid if and only if the conclusion is true in all possible models of the premises. Because of this LP turns out much less computationally complex than CL, and therefore is a promising candidate framework for realistic performance models of fast, implicit, or automatic reasoning (online discourse interpretation being the paradigmatic case).⁹⁹9Basically, in LP queries can be answered in time linear with the length of the shortest inferential path in the KB.⁹

Once a minimal model is constructed, further reasoning from that model ensues according to the derivation rule of resolution, or the reduction of goals to subgoals by means of backwards chaining.¹⁰¹⁰10This direction of reasoning is from effect to cause, from goals to subgoals, or simply backwards in time. The typical backward inferences are modus tollens ($p\to q,\neg q\models \neg p$) and affirmation of the consequent ($p\to q,q\models p$), initiated by the consequent. The psychological findings that these inferences are more difficult might well be a result of the micro-scale of the tasks being used (Sloman and Lagnado, 2015), or of the slightly more complex form of the CWA${ab}_{ab}$ needed (Stenning and van Lambalgen, 2008, pp. 176–177). The syntactic manifestation of the CWA${ab}_{ab}$ is the inferential rule of negation-as-failure, which is applied restrictively to proposition letters which are consequents of falsum, i.e. to $q$ occurring in formulae like $\perp \to q$. Queries or goal clauses initiate derivations.¹⁰

“Operationally, one should think of a query $?q$ as the assumption of the formula $\neg q$, the first step in proving $q$ from $P$ using a reductio ad absurdum argument. In other words, one tries to show that $P,\neg q\models \perp$. […] one rule suffices for this, a rule which reduces a goal to subgoals.” (van Lambalgen and Hamm, 2004, p.230)

Suppose one wants to reduce the query $?q$ with respect to the program $P=\{p\wedge \neg ab\to q,\perp \to ab\}$, which contains no positive information about abnormality. Negation-as-failure allows the reduction of $q$ to $p$, because $ab$ is a consequence of falsum.

The formal parameters of LP, e.g., the semantics based on truth in unique minimal models, the nonmonotonic definition of validity, or the syntactic rules, such as negation-as-failure, recommend it for applications in the modelling of human reasoning. In the first place, individuals’ background KBs are sets of exception-tolerant regularities. Further, LP provides a ‘direct route’ to (the reasoner’s beliefs about) states of the environment which ground inferences: observations can be looked at as the effects of those (beliefs about) states, represented as literals occurring in the consequents of KB clauses. We saw above that the LP syntactic rule of resolution amounts to stepwise backward reasoning from goals (effects) to subgoals (causes), i.e. from queries to their causes represented in the bodies of conditionals. This matches conceptually with the plan-like psychological structure of reasoning strategies: starting from the goal, i.e. a particular desired state of affairs that calls for action, one attempts to derive a behaviour that presumably leads to that state. Similarly, when a certain state is observed, backwards reasoning derives as its cause the (beliefs about) states which appear in the antecedent of the clause whose consequent it is. This ‘effect to cause’ inference takes place with respect to the minimal model of $P$, after the operation of completion has been performed; further, it is made under the auspices of $CW{A}_{ab}$ in the syntactic form of negation-as-failure. Therefore the (beliefs about) states are presumably, to the best of the reasoner’s knowledge, relevant for the current inference—they are the most plausible conditions for the observed effect to occur.

Tying back into our overarching theme for this article, it should be noted that LP has some close correspondences with probabilistic models. At least in causal cases, LP produces the structural features of the models which are shared with the structural features of causal Bayes Nets (Pearl, 2000; Pinosio, in prep.). Nevertheless, the computational properties are highly distinct (Baggio et al., 2016; Stenning and van Lambalgen, 2010). Probability cannot be the basis for what LP does in discourse processing. Discourse processing at a semantic level requires extremely fast reasoning about novel arrangements of properties and goals, currently unknown by the reasoner to be relevant to the discourse, in order to identify the propositions underlying the discourse, and this without knowledge of the distributions required for probability models. Probability has the general computational feature that the heavy computation of critical probabilities has to be done when the information defining the problem is complete (i.e. the relevant propositions identified and refined), and this is not viable in on-line discourse processing. Foreshadowing the discussion in the following subsection, the relevant type of uncertainty here is uncertainty of interpretation, not uncertainty about truth values or their probabilities. We strongly suggest that this state of affairs is not limited to discourse processing, but continues into many of the situations where people must interpret novel information.

We have introduced LP modelling of discourse interpretation in some detail because it is perhaps the extreme example of reasoning to interpretation. Once this contrast with probability models is established, it enables us to understand its kind of uncertainty as qualitatively distinct from probability. For this we resort to comparison of the logical systems that define them. In contrast to most of the proposals of kinds of uncertainty listed in the introduction, we see the necessary focus as on differences in the epistemic relations of the user of a logic to the propositions expressed, rather than in the content of the propositions themselves. To illustrate with examples of the version of LP just described, a speaker and a hearer are modelled as cooperating for the speaker to communicate to the hearer her intended preferred model by uttering a sequence of sentences. As is typical in cooperative action, this is a non-zero sum game. If the hearer doesn’t get the model, then the pair have failed (blame is another matter irrelevant here). Once this cooperative nature is captured in the semantics, it becomes evident that there is a concomitant kind of necessity: one might call it communicative necessity. If the speaker says ”Once upon a time there was a cat and a dog” the hearer can conclude with certainty that the intended model contains two distinct animals at this point. This is not certainty about the real world (whatever that is). It is certainty about the expressed intended model, where the relation of that model to the world is for the time being suspended. However complex the gyrations in the continuation are that perhaps reveal that the cat was actually mistaken for the very dog, so that the model communicated then has only one animal in it, the initial proposition that there are two animals is ‘communicatively necessary’ in this logic of interpretation. What is certain is the interpretative facts (as long as the discourse is clear, which in turn depends whether the speaker and hearer’s KBs are well aligned in their relevant parts): not any existing situation in the world. Fictional examples are extreme and therefore helpful, but in fact much of our communication starts out nearer to this kind of process than to the construction of a state of affairs that the hearer already knows how to anchor to the world. With ‘true’ stories, we also do not know what is going to happen, or even who is going to turn up, until they are done. Once the appropriate kind of necessity is grasped, it is easier to see the kind of uncertainty that is involved. The hearer is uncertain about what information will arrive, and what updating of the model will therefore be required to form the propositions that will be in the final model.

Different disciplines over the last half century or so have contributed to a greater understanding of the range of logical systems for treating uncertainty. To see the importance of a qualitative classification of kinds of uncertainty, consider CL as distinct logic also exhibiting a characteristic kind of uncertainty while reasoning toward a proof of a conjecture.¹¹¹¹11Nota bene: This stands in harsh contrast to Oaksford and Chater (2004)’s above quoted conventional characterisation of CL as ‘reasoning in certainty’. When this way of conceptualising monotonic CL in contrast to nonmonotonic logics was introduced in the mid-1970s and 1980s—for instance, in the wake of Minsky (1974)’s frames or McCarthy (1980)’s circumscription approach— the underlying concern was not with characterising kinds of uncertainty, but with contrasting two systems on the one specific property of (non)monotonicity. ¹¹ This is reasoning in uncertainty about whether the conjecture is a theorem, and it cannot be measured by probability. A proof dispels this uncertainty with a positive answer, while a counterexample resolves it with a negative answer. For another example, deontic logic defines reasoning in moral uncertainty toward moral necessity. Each logic has its own kind of uncertainty. If there were no uncertainty, the entire motivation behind reasoning would be more than questionable. Also—coming back to the remark concerning the kinds of uncertainty treated by a logic being twinned with the logic’s kind of necessity—the CL example can serve as prime example: CL’s kind of necessity is truth in all models of the premisses, which is distinctively not explicable in terms of probability.

First, a general characterisation of the problem of distinguishing kinds of uncertainty, before returning to the example. Any kind of uncertainty is a three-way relation between a person, their epistemic state, and a proposition. A probability model is one kind of specification of an epistemic state, which assigns probabilities to component propositions. This is not a point about the subjectivity or otherwise of probability. However objective the probability of an event may or may not be, it also depends on the epistemic state of the assigner—what they know or believe that is expressed in the relevant probability model. This epistemic state is also objective. Epistemic agents with different knowledge and belief about the same objective events will generally rationally assign them different probabilities on the basis of different models. Think of the players in a card game who know their own but only their own hand: each has a different probability model assigning different probabilities, to say, the next card played.

If the epistemic state of an agent does not permit them to specify a probability model by identifying the propositions relevant to their epistemic state, then their uncertainty will be of a different kind than probability. The authors cited in Section 1 as advocating varieties of uncertainty—with the exception of Mousavi and Gigerenzer (2014)— look to identify them through probability models. For example, take the most elaborated classification by Bradley and Drechsler (2014). It starts out promisingly qualitative, as demonstrated by the quote above. But the authors still end up with probabilities. The authors’ argument is only that they cannot be assigned a single probability function. But they do not consider the variety of logics that are required to characterise the epistemic states that constitute the uncertainties. It is the characterisation of epistemic states that requires the different logics; not particularly the nature of the ‘output proposition’ to which the uncertainty is assigned.

Again using discourse processing as example, LP describes the sequence of epistemic states the hearer goes through as they interpret a discourse. In this view, LP—as candidate for a logic underlying cooperative discourse semantics—specifies a process which takes in new information about the current context of reasoning, and interprets it in the light of background KB of regularities into a unique minimal model which identifies the relevant propositions. Consider the case of a discourse-initial: “Max fell. John pushed him”. First it is crucial to see that the discourse model we construct is more than the set of sentences. The two sentences “Max fell” and “John pushed him” are logically unrelated, but the model we derive (perhaps unwittingly) is extensively augmented with new information. For example, the link attributed is causal—Max’s falling follows John’s pushing in time, as its effect—and there is a spatial contact between Max and John. And the model specifies that Max is not John. And so on. This extra material is derived based on our general knowledge about human-on-human pushings and fallings. The example is chosen because here the KB actually induces an interpretation where the sequence of events departs from the sequence of narration, making the reasoning more prominent. Of course, it quickly becomes obvious that here context is everything. If Max and John were fish in water, we would struggle to interpret, because falling in water is hard for a fish, and not the typical result of pushing. If, on the other hand, the next clause were to be a continuation of the second sentence: “[…], or what was left of him after hitting the ground, over the cliff.”, we would have to revise the model in the light of the new information. Now, the pushing is subsequent to the falling (whose causation is unknown), and there is a cliff in the model, near to the protagonists. The uncertainty resides in the fact that we do not know what information is going to be involved; and this information is not available until we have integrated the current input and our background knowledge into the developing model, resolving temporal, causal and referential relations, among others. We will not present an LP formalisation here (cf. (van Lambalgen and Hamm, 2004, p. 131)): our purpose is to point to the omnipresence of such inference, and the richness of the general knowledge that has to be found and applied, generally at speed, and without awareness. Electrophysiological observations on analogous materials strongly corroborate these inferences’ occurrence (Pijnacker et al., 2010).

What is also important is that—as already stated above—interpretative inferences define their own kind of necessity, namely communicative necessity. They entail nothing about how the world has to be, but they do entail what we have to take as the speaker’s intended model of her discourse. This does not mean we have to take it as truth: we may even have good reason to believe it is part of a deliberate deception. But if we need to understand that deception, we must first understand the intended model to see what pack of lies is being offered, i.e. what has been communicated. The general point is that we must construct our interlocutors’ intended models if we are to communicate.

But now, returning to our overarching question, how does this relate to the types of uncertainty probability theory can and cannot cover? As we engage in this little cliff top drama, we are uncertain at every new discourse addition what meanings are involved. Until each new sentence has been successfully incorporated into the model we do not know which sense it expresses. But the arrival of new propositions is just the tip of the iceberg. We also do not know its effect on the other bits of meanings that were there before. They may have disappeared completely, and they probably have changed, if only by the relations that are now determined between the old and the new. In contrast, a probability model has to be founded on a set of propositions where such relations are explicit. So at best, our discourse could invoke a sequence of probability models, one at each step. But there need not be any systematic relation between one and the next. The only one likely to be of much interest as the foundation of a probability model is the ‘final’ one (cf. Stenning and van Lambalgen (2010); Baggio et al. (2016)). And if one wanted a probability model of this last one, then the corresponding LP model provides exactly the common structural core on which the necessary probability information would have to be hung, perhaps even provided by estimates from the conditional frequencies available in the LP net involved (cf. Stenning et al. (2017)). In other words, while probability theory does not deal with the dynamics of uncertainty about interpretation, LP can serve as a modelling approach for this crucial part of human reasoning (remember the 3-valued Kleene semantics we use for LP, in which the $u$ truth value can evolve during computations towards $1$ or $0$).

So discourse processing provides our first example of a prevalent cognitive process which deals in uncertainties and certainties of a kind not treated by probability. And LP provides an alternative logic for this examples’ analysis.

The main purpose of neural-symbolic integration is to bridge the gap between symbolic and sub-symbolic representations. To this end, neural-symbolic systems bring together connectionist networks and symbolic knowledge representation and reasoning (Garcez et al., 2015). In this way, neural-symbolic systems seek to take advantage of the strengths of each approach whilst hopefully avoiding their drawbacks. For our current purposes, we are particularly interested in three consecutive steps: representing the norms governing a normative system formally and soundly in an ANN, using the network to achieve efficient parallel computation, and finally exploiting the instance learning capacities of ANNs to adapt the norms in the system through learning. This should give rise to a normative system capable of integrating reasoning and learning capacities in an effective way. In what follows, we introduce the basic concepts of ANNs and neural-symbolic systems used in this article, with an emphasis on an extension of the connectionist inductive learning and logic programming (CILP) system by Garcez et al. (2002).

An ANN is a directed graph with the following structure: a unit (or neurone) in the graph is characterised, at time $t,$ by its input vector $I_i\left(t\right)$, its input potential $U_i\left(t\right)$, its activation state $A_i\left(t\right)$, and its output $O_i\left(t\right)$. The units of the network are interconnected via a set of directed and weighted connections such that if there is a connection from unit $i$ to unit $j$ then $W_{ji}\in R$ denotes the weight of this connection. The input potential of neurone $i$ at time $t$ ($U_i\left(t\right)$) is obtained by computing a weighted sum for neurone $i$ such that $U_i\left(t\right)={\sum }_j{W}_{ij}{I}_i\left(t\right)$ (see Figure 1). The activation state $A_i\left(t\right)$ of neurone $i$ at time $t$—a bounded real or integer number—is then given by the neuron’s activation function $h_i$ such that $A_i\left(t\right)=h_i\left(U_i\right(t\left)\right).$ Typically, $h_i$ is either a linear function, a non-linear (step) function, or a sigmoid function (e.g.: $tanh\left(x\right)$). In addition, ${\theta }_i$ (an extra weight with input always fixed at $1$) is known as the threshold of neurone $i$. We say that neurone $i$ is active at time $t$ if $A_i\left(t\right)>{\theta }_i.$ Finally, the neurone’s output value $O_i\left(t\right)$ is given by its output function $f_i\left(A_i\right(t\left)\right)$. Usually, $f_i$ is the identity function.

The units of an ANN can be organised in layers. A n-layer feedforward network is an acyclic graph. It consists of a sequence of layers and connections between successive layers, containing one input layer, $n-2$ hidden layers, and one output layer, where $n\ge 2$. When $n=3$, we say that the network is a single hidden layer network. When each unit occurring in the $i$-$th$ layer is connected to each unit occurring in the $i+1$-$st$ layer, we say that the network is fully-connected.

A multilayer feedforward network computes a function $\phi :R^r\to R^s$, where $r$ and $s$ are the number of units occurring, respectively, in the input and output layers of the network. In the case of single hidden layer networks, the computation of $\phi$ occurs as follows: at time $t_1$, the input vector is presented to the input layer. At time $t_2$, the input vector is propagated through to the hidden layer, and the units in the hidden layer update their input potential and activation state. At time $t_3$, the hidden layer activation state is propagated to the output layer, and the units in the output layer update their input potential and activation state. At time $t_4$, the output vector is read off the output layer. In addition, most neural models have a learning rule, responsible for changing the weights of the network progressively so that it learns to approximate $\phi$ given a number of training examples (input vectors and their respective target output vectors).

In the case of backpropagation—probably the most commonly applied neural learning algorithm (Rumelhart et al., 1986)—an error is calculated as the difference between the network’s actual output vector and the target vector, for each input vector in the set of examples. This error $E$ is then propagated back through the network, and used to calculate the variation of the weights $△W$. This calculation is such that the weights vary according to the gradient of the error, i.e. $△W=-\eta \nabla E,$ where $0<\eta <1$ is called the learning rate. The process is repeated a number of times in an attempt to minimise the error, and thus approximate the network’s actual output to the target output, for each example. In order to try and avoid shallow local minima in the error surface, a common extension of the learning algorithm above takes into account, at any time $t$, not only the gradient of the error function, but also the variation of the weights at time $t-1$, so that $△W_t=-\eta \nabla E+\mu △W_{t-1}$, where $0<\mu <1$ is called the term of momentum. Typically, a subset of the set of examples available for training is left out of the learning process so that it can be used for checking the network’s generalisation ability, i.e. its ability to respond well to examples not seen during training.

CILP now is a neural-symbolic system based on an ANN that integrates inductive learning and deductive reasoning. In CILP, a translation algorithm maps a logic program $P$ into a single hidden layer ANN $N$ such that $N$ computes the least fixed-point of $P$ (Lloyd, 1987). This provides a massively parallel model for computing the stable model semantics of $P$ (Gelfond and Lifschitz, 1988). In addition, $N$ can be trained with examples using a neural learning algorithm, having $P$ as background knowledge. The knowledge acquired by training can then be extracted (Garcez et al., 2001), closing the learning cycle, as advocated by Towell and Shavlik (1994).

Let us exemplify how CILP’s translation algorithm works. Each rule ($r_l$) of $P$ is mapped from the input layer to the output layer of $N$ through one neurone ($N_l$) in the single hidden layer of $N$. Intuitively, the translation algorithm from $P$ to $N$ has to implement the following conditions: (c$1_1$) the input potential of a hidden neurone $N_l$ can only exceed its threshold ${\theta }_l$, activating $N_l$, when all the positive antecedents of $r_l$ are assigned truth-value $true$ while all the negative antecedents of $r_l$ are assigned $false$; and (c$2_2$) the input potential of an output neurone $A$ can only exceed its threshold (${\theta }_A$), activating $A$, when at least one hidden neurone $N_l$ that is connected to $A$ is activated.

CILP thereby provides a (provably sound) translation from a symbolic representation into an ANN that can be trained with examples as part of a knowledge evolution process, whereby the original symbolic representation is seen as background knowledge to the network. In what follows, we extend CILP to handle a range of normative rules and prove soundness. Notice how in the standard CILP translation, the weights of the connections linking the hidden and output layers of the network are always positive. As will become clearer in what follows, normative rules require the use of negative weights from the hidden to the output layer of the CILP network as well. This implements priorities in the rules (Garcez et al., 2002) and is responsible for adding alternative paths that enable robustness in the networks also. As we study such different forms of representation in different applications, such as CTD, we are interested in proving soundness, but also in efficient computation and learning, as exemplified later in this article.

As explained by Makinson and van der Torre (2003b), I/O logic takes its origin in the study of conditional norms which, either in imperative or indicative form, express obligations under some legal, moral, or practical code, goals, contingency plans, advice, etc. Putting this overall notion in formal terms, Makinson and van der Torre (2000) represent rules by ordered pairs $(a,x)$, where the antecedent $a$ is thought of as an input, representing some condition or situation, and the consequent $x$ is thought of as an output, representing what the rule tells us to be desirable, obligatory, or whatever else in that situation.

Concerning the overall motivation behind the development of I/O logic, in philosophy—but also significant in our current context—norms are commonly distinguished from declarative statements. The latter may bear truth-values, while describing norms as true or false is meaningless. Instead, norms may be respected (or not), can be in force in the current context (or not), or can be assessed from the standpoint of other norms (e.g., when judging a law from a moral point of view). Still, much work addressing deontic formalisms in the study of logic and AI seem to ignore this distinction: most presentations of deontic logic—whether axiomatic or semantic—treat norms as if they could be subjected to an assessment in terms of truth-values. In particular, the truth-functional connectives ‘and’, ‘or’, and ‘not’ are routinely applied to norms, forming compound norms out of elementary ones. Semantic constructions using possible worlds go further by offering rules to determine, in a model, the truth-value of a norm. I/O logic has its source in precisely this tension between philosophy and studies in formal logic (the reader may identify a similar tension between human reasoning and formal classical logic, as discussed earlier in the case of discourse processing).

In the following, we first present abstract normative systems as a general descriptive framework for formal approaches to normative reasoning and basis for the subsequent introduction of propositional I/O logic, both of which then are applied to modelling the three types of permissions commonly encountered in normative context.

Our goal is to allow the agent to learn about norms and their interpretation from experience, and to take decisions which respect the norms she is subject to at the respective point in time. Thus, the agent needs to know what is obligatory and forbidden according to norms (conditional rules) in any situation in real time: what is obligatory can eventually become an action of the agent, while what is forbidden inhibits such actions. Also, rules may change as the normative environment changes over time. The agent should be flexible enough to adapt her behaviour to the context using as information the instances of behaviours which have been considered illegal.

To allow an intelligent agent to have a internal representation of a normative code, we follow the process visualised in Figure 3. The encoding process is a single and unique task, and we just decompose it in subtasks to give a more detailed explanation. The first step involves encoding a list of normative aspects in terms of priorities and will be described in the next subsection. The second step translates a normative code in I/O logic into an extended logic program (i.e. LP extended with classical negation, a.k.a. explicit negation, which leads to the answer set semantics of LP mentioned earlier in the context of three-valued logics. The third step applies a translation algorithm to convert the logic program into a neural network. The last two steps will be analysed in detail in Section 3.5.

Figure 4 describes our approach from a more abstract perspective. Note that the encoding of a normative code in an ANN is lumped to a single step. Our framework starts from the symbolic KB of norms contained in the agent, transforming it into an ANN using the encoding introduced in Figure 3 and described below. The ANN is structured as follows: input neurones of the network represent the state of the world, while the output neurones represent the obligations of the agent, or the prohibitions. The ANN is used as part of the controller for the agent and, given its ability to change (i.e. learn from examples), it is expected to give the agent the required flexibility.

Recall, as discussed, that normative reasoning requires agents to deal with specific problems such as dilemmas, exceptions, and CTDs. In what follows, a norm N will be expressed as labelled generators $N=(I,O)$, read ‘if input $I$ then output $O$’. In general, $I$ in $(I,O)$ is any propositional formulae, which will be restricted later to conjunctions of literals.

Dilemmas: two obligations are said to be contradictory when they cannot be accomplished together. A possible example of contradictory norms is the dilemma. This usually happens when an agent is subject to different normative codes (i.e. when an agent has to follow the moral and the legal code). How to overcome dilemmas is left as future work, as we are focusing on how to use priorities to regulate exceptions and CTDs.

Priorities are used to give a partial ordering between norms. This is useful when, given two applicable norms, we always want one to preempt the other, for instance when dealing with exceptions. We encode priorities among the norms by using negation by failure ($\sim$). Given two norms $N_1=(A_1\wedge A_3,{\beta }_1)$ and $N_2=(A_2\wedge A_3,{\beta }_2)$ and a priority relation $N_1\succ N_2$ between the norms (such that the first norm has priority), we encode the priority relation by modifying the antecedent of the norm with lower priority. Specifically, we include in the antecedent of the norm with the lower priority the negation-as-failure of the literals in the antecedent of the higher priority norm that does not appear in the antecedent of the lower priority norm. We do so in order to ensure that, in a situation where both (unmodified) norms would be applicable, the newly inserted negation-as-failure atoms in the antecedent of the modified lower-priority norm evaluate to $false$ and make the norm not applicable. Considering for example the two norms given above, we have to modify $N_2$. The only atom appearing in $N_1$’s input and not in $N_2$’s input is $A_1$, and therefore we introduce $\sim A_1$ as a conjunct in $N_2$’s input. After embedding the priority, the second norm becomes $N_2^{\prime }=(A_2\wedge \sim A_1\wedge A_3,{\beta }_2)$. Note that in a potentially conflicting situation when $A_1$, $A_2$ and $A_3$ hold, $N_1$ and $N_2$ are applicable, but $N_2^{\prime }$ is not, thus avoiding the conflict.

Exceptions occur when, due to particular circumstances, a norm should be followed instead of another. Suppose that a norm $N_3=(\alpha ,\beta )$ should be applied in all the situations containing $\alpha$. For exceptional situations we consider an additional norm $N_4=(\alpha \wedge \gamma ,\neg \beta )$. The latter norm should be applied in a subset of situations w.r.t. $N_3$: specifically all those when, in addition to $\alpha$, also $\gamma$ holds. We can call situations where both $\alpha$ and $\gamma$ hold exceptional situations. In these exceptional situations both norms could be applied. This would produce two contrasting obligations: $\beta$ and $\neg \beta$. To avoid this we add the following priority relation: $N_4\succ N_3$. Therefore we modify the input of the norm with lower priority as described earlier. The result is a new norm $N_3^{\prime }=(\alpha \wedge \sim \gamma ,\beta )$, that would not be applied in the exceptional situations, avoiding the problem of contrasting obligations.

CTDs: An important property of norms is that they are soft constraints and, accordingly, can be violated. CTDs provide additional obligations to be fulfilled when a violation occurs. For example, consider a norm $N_5=(\alpha ,\beta )$ that should be applied in all situations containing $\alpha$ and producing the obligation $\beta$. As mentioned, norms can be violated, therefore we can also define a norm that produces alternative obligations to be followed in case of a violation. Let this new norm be $N_6=(\alpha \wedge \neg \beta ,\gamma )$. The latter norm contains in its input both the input of $N_5$ and the negation of its output. In this way it describes which should be the alternative obligation to $\beta$ in the case that it cannot be achieved, in this example $\gamma$. We use a priority relation between the two norms in order to avoid the generation of the obligation $\beta$ in case it is already known that it is not satisfiable. We add then the following priority relation $N_6\succ N_5$ that modifies the first norm as follows: $N_5^{\prime }=(\alpha \wedge \sim \neg \beta ,\beta )$.

Permissions: An important distinction between obligations and permissions is that the latter will not be explicitly encoded in the ANN. In our approach we consider that something is permitted to the agent if not explicitly forbidden (note that we consider the ought of a negative literal as a prohibition). Due to this, we assume that norms with a permission in their output implicitly have priority over the norms that forbid the same course of action¹⁶¹⁶16Makinson and van der Torre (2003a) consider three kinds of permissive norms, namely negative, positive, and static positive permission. In this article, we restrict discussions to the above, and should note that much future work is left to be done when it comes to the provision of connectionist representations for normative and deontic reasoning systems¹⁶. For example, using $P$ in the output of a norm to denote a permission, consider two norms $N_7=(A_1,P({\beta }_1\left)\right)$, $N_8=(A_2,\neg {\beta }_1)$. The first norm permits ${\beta }_1$ and the second forbids it. In this case, we use the following priority relation: $N_7\succ N_8$.

In this section we introduce a new approach for coding a fragment of I/O logic which corresponds to extended LP into ANNs. The main intuition is that, although logic programs in general do not explicitly capture the concepts of inputs and outputs, a neural-symbolic system based on extended logic programming does - on a purely structural level: inputs and outputs in I/O logic correspond to the input and output layers of the ANN - and allows the representation of norms in ANNs.

As described above, in I/O logic norms are represented as ordered pairs of formulas like $(\alpha ,\beta )$. A peculiarity of I/O logic is that it does not have $(\alpha ,\alpha )$ for any $\alpha$ (i.e. identity is not an axiom). In normative reasoning, the input does not necessarily become an output: the reason is that the output is interpreted as what is obligatory, thus, just because $a$ is in the input, it is not necessarily the case that $a$ is obligatory as well. This I/O perspective corresponds straightforwardly to the general intuition behind an ANN. Activating input neurone $A$ in Figure 2 does not necessarily activate output neurone $A$ also; this is true for any neurone, and it allows a subtle but important distinction between the activation of an input neurone which is derived from the context, that is, the input values provided to the network, and the activation of an output neurone, which is derived from the KB. For example, in Figure 2, the truth-value of $B$ in the input is, at first, obtained from the input to the network (its context), whilst the truth-value of $B$ in the output is $true$ ($B$ is a fact in the KB). Modifying the original CILP algorithm, we first translate I/O logic into an extended logic program to be processed by CILP without requiring inputs to be always translated into outputs as well, so that the ANN is allowed different input and output layers. The input $\alpha$ of an I/O norm $(\alpha ,\beta )$ is subsequently passed as an input vector to the network, producing an output representing what is obligatory (e.g. $\beta$, if the translation to the ANN is proved correct). Only some input appears in the output, if it is made obligatory by a norm. In CILP, output nodes are always connected to input nodes creating a recurrent network, to represent the transitivity of logical rules when computing minimal or stable models. In normative reasoning, transitivity is not always accepted (since if you are obliged to do $a$ and, if $a$ then you are obliged to do $b$ does not imply that you are obliged to do $b$). Thus, the normative CILP extends CILP also to allow that certain outputs might not be connected to their corresponding inputs (or will not even have a corresponding input as a result of the first change made to CILP earlier).