PaperlayerView exact revision on arXiv

Source-linked AI summary

Reasoning in Non-Probabilistic Uncertainty: Logic Programming and Neural-Symbolic Computing as Examples

Tarek R. Besold, Artur d'Avila Garcez, Keith Stenning, Leendert van der Torre, Michiel van Lambalgen

arXiv:1701.05226v2cs.AI

TL;DR

The article argues that uncertainty is not uniform: some forms are not appropriately addressed probabilistically. It examines Kleene-semantics logic programming for discourse interpretation and neural-symbolic Input/Output logic for changing normative contexts, finding that logic-based methods can support uncertain reasoning.

  • Problem

    Probability can model some kinds of uncertainty, but other kinds lie outside probabilistic approaches, motivating a distinction among qualitatively different uncertainties.

    Source: §1 · pp. 1–2

  • Method

    The article studies Kleene-semantics logic programming for discourse processing and a neural-symbolic architecture combining Input/Output logic with artificial neural networks for dynamic normative reasoning.

    Source: §1 · p. 7

  • Results

    The two examples provide evidence that logic-based methods support reasoning with uncertainty, while N-CILP computes answer-set semantics and learns previously unspecified conditional norms.

    Source: The N-CILP algorithm · p. 32, Initial Experimental Evaluation of the… · p. 37, §4 · p. 38

  • Takeaways & Limitations

    Examining the uncertainty and necessity associated with each logic offers a semi-systematic way to explore and handle different kinds of uncertainty.

    Source: §4 · p. 38

    Discourse processing with logic programming has computational properties distinct from probability, whose models require explicit propositional relations and whose critical probability computations are heavy.

    Source: §2.1 · p. 12, §2.2 · p. 16

Abstract

from arXiv · show

This article aims to achieve two goals: to show that probability is not the only way of dealing with uncertainty (and even more, that there are kinds of uncertainty which are for principled reasons not addressable with probabilistic means); and to provide evidence that logic-based methods can well support reasoning with uncertainty. For the latter claim, two paradigmatic examples are presented: Logic Programming with Kleene semantics for modelling reasoning from information in a discourse, to an interpretation of the state of affairs of the intended model, and a neural-symbolic implementation of Input/Output logic for dealing with uncertainty in dynamic normative contexts.

1 Introduction

The paper argues that probability is powerful for some uncertainties but cannot address uncertainty arising while interpretations, vocabularies, and dynamic normative contexts are being constructed. It develops Logic Programming with Kleene semantics for discourse interpretation and a neural-symbolic Input/Output logic approach for changing norms.

Contribution

  • The introduction frames the article as two case studies showing that logic-based methods can support non-probabilistic uncertainty in discourse interpretation and dynamic normative reasoning.The paper also situates these cases within broader AI uncertainty involving partial observability, noisy data, changing action outcomes, and environmental complexity.Source: §1 · pp. 2–4

Motivation

  • The paper distinguishes qualitatively different kinds of uncertainty, arguing that some lie outside probabilistic approaches while others remain suitably modelled by probability.Its focus is uncertainty during reasoning to interpretations, rather than only uncertainty over a fixed domain.Source: §1 · pp. 2, 5

Logic Programming and discourse

  • Discourse interpretation precedes probabilistic modelling because the relevant predicates, relations, and dependencies must first be established through reasoning to interpretations.The resulting structural common core can later provide a basis for a Bayes Net, but the interpretive construction itself cannot be reduced to probability.Source: §1 · pp. 3, 5

Kinds of uncertainty

  • The paper contrasts intensional LP with extensional probability: LP conditionals are contentful inference licences, not propositions with truth values or numerical parameters.In LP, conditionals need not iterate and do not become false merely because abnormality conditions prevent their application.Source: §1 · pp. 4, 6

Logic Programming and discourse

  • Logic Programming with three-valued Kleene semantics models discourse processing as sequentially constructing a unique minimal preferred interpretation.Preferred Model Semantics is selected because uniqueness supports cognitive processes such as discourse processing.Source: §1 · pp. 3, 7

Neural-symbolic normative reasoning

  • A neural-symbolic architecture combines I/O logic with artificial neural networks to reason about obligations, permissions, and contrary-to-duty relations under changing norms.The neural component supplies learning, allowing normative systems to acquire missing norms from examples as environments evolve.Source: §1 · pp. 2, 4, 7

2 Logic Programming Modelling Reasoning to an Interpretation

Logic Programming models discourse interpretation as the construction and revision of a unique minimal or preferred model, treating uncertainty about meaning and relevance rather than merely uncertain truth values. Its Kleene-based, nonmonotonic reasoning supports fast, context-sensitive interpretation and distinguishes communicative necessity from probabilistic uncertainty.

2.1 Logic Programming Modelling Reasoning

  • LP models discourse interpretation by incrementally constructing a unique preferred model from online sentences and relevant background knowledge.The model captures co-references, temporal and causal relations, and other information not explicitly stated in the discourse.Source: §2.1 · p. 8
  • LP conditionals are exception-tolerant licenses for inference: closed-world assumptions suppress unsupported abnormalities until relevant evidence activates them.A conditional such as p ∧ ¬ab → q therefore remains usable despite possible defeaters, while explicit information can revise the model.Source: §2.1 · pp. 9–10
  • Strong Kleene semantics treats the middle value u as currently indeterminate and allows interpretations to evolve toward 0 or 1 during computation.This is a computational stage rather than a graded probability, supporting the flexibility required by interpretational uncertainty.Source: §2.1 · pp. 9–10
  • Minimal-model inference uses completion, resolution, backward chaining, and negation-as-failure to retrieve relevant causes from effects while excluding irrelevant information.LP validity is truth preservation in the minimal model, making the framework less computationally complex than classical logic and suitable for fast implicit reasoning.Source: §2.1 · pp. 11–12

2.2 The Many Logical Faces of Uncertainty, or What Logic Programming Can Do for Reasoning

  • Interpretative reasoning has communicative necessity: it determines the speaker’s intended model without asserting that the model is true of the external world.Constructing interlocutors’ intended models is presented as necessary for communication, including communication involving deception.Source: §2.2 · pp. 13, 15, 16
  • Probability models require a specified and relatively complete proposition structure, whereas LP handles the evolving meanings and relations of discourse as new information arrives.The final LP model can provide a structural core to which probability information may later be attached, but probability does not model the dynamics of interpretational uncertainty itself.Source: §2.1 · pp. 12–13, §2.2 · pp. 15–16

3 Neural-Symbolic Computing Modelling Dynamic Normative Contexts

The paper combines Input/Output logic with neural-symbolic computation to represent, reason about, and learn norms in changing environments. The framework targets context-sensitive normative problems such as permissions, contrary-to-duty obligations, exceptions, and evolving rules.

3 Neural-Symbolic Computing Modelling Dynamic Normative Contexts

  • Dynamic norms create context-sensitive reasoning problems because rules may be introduced, altered, or differently interpreted over time.This issue is especially relevant to coordination in multi-agent systems.Source: §3 · pp. 16–17
  • The proposed framework encodes Input/Output logic rules in artificial neural networks and uses network learning to refine normative rules dynamically.The approach combines symbolic background knowledge and explanations with connectionist learning and computation.Source: §3 · p. 17
  • The methodology addresses permissions, contrary-to-duty obligations, and exceptions through priorities between Input/Output or LP rules.The paper presents translation of rules into networks and evaluation of learning for refining rules over time as its two main steps.Source: §3 · pp. 17–18

3.1 Neural-Symbolic Systems

Neural-symbolic systems combine symbolic knowledge representation with neural computation, allowing logic programs to be translated into trainable networks that support both reasoning and learning.

3.1 Neural-Symbolic Systems

  • Neural-symbolic systems combine connectionist networks with symbolic knowledge representation and reasoning to integrate their respective strengths.The approach targets formal norm representation, parallel computation, and adaptation through learning.Source: §3.1 · p. 18
  • CILP translates a logic program into a single-hidden-layer ANN that computes its least fixed-point and supports stable-model reasoning in parallel.The resulting network can also be trained using examples while retaining the original program as background knowledge.Source: §3.1 · p. 20
  • CILP maps each rule of a logic program to a hidden neuron and uses threshold conditions to implement rule antecedents and consequents.Hidden neurons activate when positive and negative antecedents satisfy the rule, while output neurons activate when connected rule neurons fire.Source: §3.1 · p. 20
  • The recurrent CILP network iteratively feeds outputs back as inputs and converges to a stable state identical to the program’s stable model for acceptable programs.In the example, the network converges to a state where B is true and all other literals are false.Source: §3.1 · p. 20
  • Extending CILP to normative rules requires negative hidden-to-output weights, which encode priorities and provide alternative paths for robustness.The extension aims to preserve soundness while supporting efficient computation and learning.Source: §3.1 · pp. 20–21

3.2 Input/Output Logic

Input/Output logic represents conditional norms as transformations from contextual inputs to normative outputs, without treating norms as truth-valued propositions.

3.2 Input/Output Logic

  • I/O logic represents a conditional norm as an ordered pair (a, x), where a is an input condition and x is a desirable or obligatory output.This formalization targets conditional norms arising in legal, moral, practical, and goal-directed contexts.Source: §3.2 · p. 21
  • Unlike declarative statements, norms are not assessed as true or false; they may instead be respected, in force, or evaluated from another normative standpoint.I/O logic arises partly from this tension between normative reasoning and truth-functional logical treatment.Source: §3.2 · pp. 21–22
  • Abstract normative systems model a finite universe with anti-elements, conditional norms, and contexts containing ⊤, generating obligation sets from the norms and context.The framework treats the system as a directed graph whose edges define conditional norms.Source: §3.2 · pp. 22–23
  • The deontic operations differ in how they support reasoning by cases, deontic detachment, identity, and related closure behaviors, yielding eight possible input/output operations.Simple-minded output is minimal, basic output supports reasoning by cases, reusable output supports iteration, and throughput allows identity.Source: §3.2 · p. 23
  • The framework addresses normative phenomena including dilemmas, contrary-to-duty obligations, and defeasible norms through nonmonotonic reasoning approaches.These phenomena include contradictory obligations and secondary obligations triggered by violations.Source: §3.2 · p. 23

Propositional Input/Output Logic

Propositional I/O logic extends abstract normative systems with propositional consequence while deliberately providing a relatively simple treatment that omits important deontic phenomena.

Propositional Input/Output Logic

  • Propositional I/O logic abstracts from important aspects of deontic reasoning, including contrary-to-duty reasoning and permissions.These limitations mark the scope of the propositional setting.Source: Propositional Input/Output Logic · p. 24
  • Propositional I/O logic closes inputs and outputs under propositional consequence and defines several output operations over generators and contexts.The operations include out1 through out4, differing in their treatment of complete and closed extensions.Source: Propositional Input/Output Logic · p. 24
  • In I/O logic, normative systems generate obligation sets rather than logically implying or deriving norms.Logic prepares inputs, unpacks outputs, and coordinates them; the normative code functions as a transformation device.Source: Propositional Input/Output Logic · p. 24

3.3 Overview of the Architecture

The proposed normative agent converts a symbolic norm base into a neural controller whose inputs encode world states and whose outputs encode obligations or prohibitions, enabling adaptation as norms change.

3.3 Overview of the Architecture

  • The architecture aims to let an agent learn norms and their interpretation from experience while making decisions that respect time-varying obligations and prohibitions.The agent adapts behavior using contextual information and previously identified illegal behaviors.Source: §3.3 · pp. 24–25
  • The framework transforms the agent’s symbolic knowledge base of norms into an ANN using the encoding introduced for the normative architecture.Figure 4 presents this transformation at an abstract level.Source: §3.3 · p. 25, Figure 4 · p. 25
  • Input neurons represent the state of the world, while output neurons represent the agent’s obligations or prohibitions.The ANN serves as part of the agent’s controller.Source: §3.3 · p. 26
  • Because the ANN can change through learning, the architecture is intended to provide flexibility as the normative environment changes.The proposed controller is therefore designed to adapt behavior to changing contextual rules.Source: §3.3 · pp. 25–26

3.4 Normative Problems as Priorities

The section uses priorities to manage conflicts among obligations, exceptions, and contrary-to-duty norms. Priorities modify lower-priority rule inputs with negation-as-failure so conflicting norms become inapplicable in the relevant circumstances.

3.4 Normative Problems as Priorities

  • Dilemmas, where contradictory obligations cannot be jointly fulfilled, remain outside the section's priority-based treatment and are left for future work.The discussion focuses on exceptions and contrary-to-duty obligations rather than resolving dilemmas.Source: §3.4 · p. 26
  • Priorities give a partial ordering among norms so higher-priority rules preempt lower-priority rules when both would otherwise apply.The lower-priority norm is modified by adding negation-as-failure literals from the higher-priority norm's antecedent.Source: §3.4 · p. 26
  • When A1, A2, and A3 hold in a potentially conflicting situation, N1 and N2 are applicable, but N′2 is not, thus avoiding the conflict.Source: §3.4 · p. 26
  • For exceptions, priority N4 ≻N3 prevents the general obligation β from applying when the exceptional condition α∧γ holds.The lower-priority rule becomes N′3 = (α∧∼γ, β).Source: §3.4 · pp. 26–27
  • Contrary-to-duty norms add alternative obligations after violations, while priority N6 ≻N5 prevents β from being generated when β is already unsatisfiable.N6 uses α∧¬β as its input and produces the alternative obligation γ.Source: §3.4 · p. 27
  • Permissions are not explicitly encoded in the ANN and are treated as overriding norms that forbid the permitted action.A permission is represented by a priority relation over the corresponding prohibition.Source: §3.4 · p. 27

3.5 Normative Connectionist Inductive Learning and Logic Programming

This section introduces a neural-symbolic approach that embeds a fragment of Input/Output logic corresponding to extended Logic Programming into artificial neural networks. The representation preserves distinct input and output roles while accommodating normative priorities and non-identity.

3.5 Normative Connectionist Inductive Learning and Logic Programming

  • The approach codes a fragment of Input/Output logic corresponding to extended Logic Programming into artificial neural networks.It is designed to represent norms in a neural-symbolic system.Source: §3.5 · pp. 27–28
  • The article restricts its treatment of permissive norms and identifies connectionist representations for broader normative and deontic systems as future work.Three kinds of permissive norms are noted, but the article discusses only the restricted case used in its approach.Source: §3.5 · p. 27
  • Input and output layers structurally correspond to I/O logic inputs and outputs, enabling norms to be represented in the network.The connection is structural rather than an assertion that inputs must also appear as outputs.Source: §3.5 · pp. 27–28
  • The network distinguishes context-derived input activation from knowledge-base-derived output activation, so an input α produces an obligatory output only when a norm licenses it.This requires separate input and output layers and removes the assumption that every input is also an output.Source: §3.5 · p. 28
  • Normative CILP also avoids automatic input-output identity and permits selected outputs to lack corresponding input connections because normative transitivity is not always accepted.This differs from recurrent CILP connections used to represent transitivity in logical rules.Source: §3.5 · p. 28, Mapping Input/Output Logic into Neural… · p. 28

Mapping Input/Output Logic into Neural Networks

The mapping translates I/O normative codes into extended logic programs, embeds priorities through negation-as-failure, and prepares the resulting rules for neural implementation. The construction preserves the unique answer-set behavior of the translated programs.

Mapping Input/Output Logic into Neural Networks

  • An I/O normative code consists of obligation rules, permission rules, and a preference relation among them.Obligations and permissions are represented as ordered pairs of formulas, with inputs and outputs treated asymmetrically.Source: Mapping Input/Output Logic into Neural… · p. 29
  • The resulting program has a unique model because the translation is free of negation-as-failure.The embedding is restricted to an I/O fragment for which this natural translation is available.Source: Mapping Input/Output Logic into Neural… · p. 29
  • The translation decomposes disjunctive inputs and conjunctive outputs into extended-logic-program clauses using separate input and output literals.The mapping uses in/out encodings for positive and classically negated literals.Source: Mapping Input/Output Logic into Neural… · p. 29
  • The translation preserves obligation derivability: an input α yields output β in the extended program when the obligation (α, β) belongs to the normative code.The correspondence is established using the immediate consequence operator.Source: Mapping Input/Output Logic into Neural… · pp. 29–30
  • Preferences are transformed from meta-level relations into object-level rule modifications, with negation-as-failure preventing lower-priority rules from firing when higher-priority rules apply.The transformations Tro and Trp also account for permission-generated priorities.Source: Mapping Input/Output Logic into Neural… · p. 30
  • The translation yields an equivalent extended logic program, and explicit-priority programs preserve their answer sets after priority elimination.This supports subsequent neural computation of the translated program's semantics.Source: Mapping Input/Output Logic into Neural… · pp. 30–31
  • The proposed Normative-CILP algorithm differs from CILP by encoding priorities in the ANN and by not assuming identity between inputs and outputs.The construction is intended for feedforward networks with semi-linear neurons.Source: The N-CILP algorithm · p. 32

The N-CILP algorithm

The N-CILP algorithm translates normative codes into feedforward neural networks whose structure encodes rule inputs, priorities, and outputs. Its formal result is that the resulting network computes the code's answer-set semantics, while the reported simulator demonstration remains preliminary.

The N-CILP algorithm

  • N-CILP first transforms the normative code, encodes priorities, then creates input, hidden, and output neurons for each translated rule.Positive and negation-as-failure antecedents receive different connection weights.Source: The N-CILP algorithm · p. 32
  • Rule neurons connect to output neurons through positive weighted arcs, while negative outputs are represented by output labels with equivalent negative meaning.This permits the network translation to treat each rule output as a positive atom operationally.Source: The N-CILP algorithm · p. 32
  • For any normative code expressible as an extended logic program, N-CILP produces an ANN that computes its answer-set semantics.The proposition states existence of such a network for every normative code in the specified form.Source: The N-CILP algorithm · p. 32
  • Soundness follows because the program translation has a single extension and the ANN encoding converges to that unique extension from any initial input.The convergence argument relies on the extended-logic-program encoding and the established ANN construction.Source: The N-CILP algorithm · p. 32
  • A RoboCup soccer example translates three goal-stopping norms into an extended logic program and then into an ANN.The example includes obligations triggered by shooting, goalkeeper position, ball possession, and proximity conditions.Source: The N-CILP algorithm · p. 33
  • The proof-of-concept simulator's results are preliminary but indicate capabilities for neural-symbolic normative reasoning and learning under uncertainty.The reported application is limited to the example scenario described in the section.Source: The N-CILP algorithm · p. 33

Initial Experimental Evaluation of the N-CILP Algorithm

The evaluation compares N-CILP, which initializes neural networks from normative rules, with a purely connectionist ANN and tests incremental rule learning and CTD acquisition. N-CILP improves as the knowledge base expands and learns omitted priority-based norms with high test-set accuracy.

Evaluation measures

  • The evaluation uses tot for fully correct output vectors and part for the average number of correctly evaluated output neurons.Both measures are computed on test-set predictions using indicator-based correctness over examples and outputs.Source: Initial Experimental Evaluation of the… · p. 34

Comparison with a purely connectionist approach

  • N-CILP combines a rule-derived knowledge base with backpropagation training, while the non-symbolic ANN starts from randomly initialized weights.Both networks use the same number of hidden neurons and training examples; N-CILP sets weights from symbolic rules, giving it a rule-based head start.Source: Initial Experimental Evaluation of the… · pp. 33–34
  • The non-symbolic ANN achieves tot = 5.13% and part = 45.25%, compared with N-CILP’s tot = 5.38% and part = 49.19% on the stated test split.The comparison uses the first 20 rules to set up N-CILP and the remaining six rules for testing.Source: Initial Experimental Evaluation of the… · p. 36

Incremental evaluation

  • 98,01% part and 91,18% tot are reached in the final incremental experiments as the N-CILP network receives more rules.The first two experiments retain low accuracy, whereas performance rises considerably in the last two; with all 26 rules, training-set performance is reported because no unknown rules remain.Source: Initial Experimental Evaluation of the… · p. 36, Figure 5 · p. 36

Learning CTDs

  • N-CILP is tested on learning three robotsoccer CTDs involving minimizing impact, terminating contact, and permitting goalkeeper hand use.The experiments leave out the priority-based orderings regulating these contrary-to-duty rules and test whether the network can learn them from examples.Source: Initial Experimental Evaluation of the… · p. 37
  • The learned network reaches 95%, 93%, and 87% accuracy on the three CTD test sets and generates minimizeImpact only in the relevant suboptimal situation for the first CTD.The results support learning CTDs absent from ANN construction, reducing the need for a complete domain description because missing norms can be acquired from examples.Source: Initial Experimental Evaluation of the… · p. 37

4 Conclusion

The paper argues that probability is not the only framework for uncertainty and presents logic-based approaches as capable of handling uncertainty in discourse and dynamic normative contexts. It concludes that these examples support a semi-systematic exploration of uncertainty through the epistemic states specified by different logics, while identifying substantial directions for future development.

4 Conclusion

  • The paper presents LP with Kleene semantics and neural-symbolic I/O logic as evidence that logic-based methods can support reasoning with uncertainty.The two examples address discourse interpretation and uncertainty in dynamic normative contexts, respectively.Source: §4 · p. 38
  • Different logics can be explored for distinct kinds of uncertainty by examining the epistemic states they specify and the necessities associated with them.The paper does not claim that every logic has its own distinct uncertainty species or that every species matters for cognitive modelling or AI.Source: §4 · p. 38
  • A future neural implementation of the more expressive Constraint LP could add learning capacities to discourse processing involving time and causality.The paper notes that such an implementation is currently lacking and could bridge cognitive modelling with cognitively inspired AI applications.Source: §4 · pp. 38–39
  • The discourse-modelling approach assumes a mature knowledge base and does not address learning the knowledge-base rules.The authors identify learning as an important goal for future LP models of discourse.Source: §4 · p. 38
  • The neural-symbolic I/O system is planned to gain an explicit context mechanism that can retain past events and influence current decisions.One proposed route is adding external memory so context can persist through network computation.Source: §4 · p. 39
  • Future work also proposes combining interpretation-related reasoning with normative reasoning and clarifying how intensional and extensional systems work together.The proposed combination targets cases where relevant propositions are initially unknown while rules change dynamically.Source: §4 · pp. 39–40

Related papers

Loading 1701.05226v2…