Ranking-based Conditional Semantics for Defeasible Subsumptions (Extended Abstract)

Abstract

Defeasible subsumptions are kind of default rules aka conditionals, i.e., rules with exceptions, or rules that plausibly hold. Such rules have been explored in the area of nonmonotonic reasoning since the 80s of the past century, and a crucial insight from these studies is that semantically, it needs qualitative relations between possible worlds to provide solid logical semantics for default rules. However, most approaches here have focused on propositional logic only. In this talk, I present a semantics for first-order conditionals that mimicks commonsense reasoning well and is based on Spohn's ranking functions which are particularly popular in the fields of nonmonotonic reasoning and belief revision. So-called c-representations construct a ranking model from a ifrst-order conditional belief base that yields high-quality nonmonotonic inferences. As a special feature of this approach, the qualitative relations between possible worlds which are mandatory to implement defeasible inferences are elaborated from the conditionals in the belief base, no external relations, e.g., expressing typicality among individuals need to be specified. This approach can also be applied to defeasible subsumptions in description logics, taking information from both (defeasible) TBox and ABox into account.

1. Introduction and Overview

Rules in the form of conditional statements “If then (usually) ” (sometimes equipped with a quantitative degree) are basic to human reasoning and also to logics in Artificial Intelligence. In cognitive sciences, four inference rules have been considered in many studies to find out how humans draw inferences from a given conditional statement and a respective fact: Modus Ponens (MP), that from the statement and it follows that , and Modus Tollens (MT), that from the statement and ¬ it follows that ¬. MP and MT are classically valid, but also other, classically invalid rules can be observed frequently: Afirmation of the Consequent (AC) , stating that from the statement and it follows that and, finally, Denial of the Antecedent (DA), stating that from the statement and ¬ it follows that ¬. MP and MT are deemed to be rational, while AC and DA are interpreted as failures of rational reasoning.

In this talk, we first show that well-known approaches to commonsense (nonmonotonic) logics in the field of knowledge representation can resolve “irrational” incompatibilities with logic in most cases. More precisely, by recalling results from [ 1, 2 ] we argue that the observed “irrationality” is due to taking classical logic as a (non-fitting) standard, and that the usage of so-called preferential models [ 3, 4 ] can explain away nearly all observed inconsistencies. The basic technical methodologies for implementing (inductive) preferential models are conditionals (|) allowing for a non-classical, three-valued interpretation of conditional statements, total preorders on possible worlds, and ranking functions [ 5, 6 ]. However, preferential models have been mostly considered for propositional logics. Here, we make use of the first-order conditional logic introduced in [ 7 ] to present first steps towards an interpretation of defeasible subsumptions in description logics which is thoroughly based on conditionals and ranking functions.

This talk reports on (ongoing) joint work with Christian Eichhorn, Alexander Hahn, Marco Ragni, Lars-Phillip Spiegel, and Matthias Thimm. 2. Plausible Reasoning with Preorders and Ranking Functions First, we consider a propositional language L composed from a finite set Σ of atoms as usual, with Ω being the set of possible worlds resp. interpretations over Σ . We introduce the binary operator | to obtain the set (L|L) of conditionals written as (|). Conditionals are three-valued logical entities according to [ 8 ].

For nonmonotonic inference and the modeling of epistemic states, total preorders ≼ on possible worlds expressing plausibility are of crucial importance. If 1 ≼ 2, 1 is deemed as at least as plausible as 2. Such a preorder can be lifted to the level of formulas by stating that ≼ if for each model of , there is a model of that is at least as plausible. Nonmonotonic inference can then be easily realized as a form of preferential entailment of high logical quality [ 4 ]: |∼ ≺ if and only if ≺ , i.e., from , can be plausibly inferred if in the context of , is more plausible than . Hence total preorders provide convenient epistemic structures for plausible reasoning, and epistemic states Ψ can be represented by such a total preorder ≼Ψ. Conditionals can then be integrated smoothly into this reasoning framework by defining Ψ |= (|) if and only if |∼ ≺ , i.e., conditionals encode nonmonotonic inferences on the object level.

Ordinal conditional functions (OCF, [ 5, 6 ], also called ranking functions, are functions : Ω → N0 ∪ {∞} with − 1(0) ̸= ∅ that assign to each world an implausibility rank (), providing specific implementations of total preorders. The rank of a formula ∈ L is defined as () = min{ ()| |= }. A ranking function accepts a conditional (|) (in symbols |= (|)) if () < (), in accordance with preferential inference as defined above.

3. Inference patterns

Previous research in cognitive sciences discussed whether each of the inference rules MP, MT (both classically valid), and AC, DA (both classically invalid) is respectively applied by investigating if participants or any (cognitive) system draw a specific inference. In [ 1 ], we go beyond that in two respects: first, we formalize what it means that it is plausible to draw conclusions according to these rules, and secondly, we focus on the combination of these inference rules in a specific experiment which reflects the global inference behavior typical for the respective experiment by introducing inference patterns.

Definition 1 (Inference Pattern). An inference pattern is a 4-tuple of inference rules that for each inference rule MP, MT, AC, and DA indicates whether the rule is used (positive rule, e.g., MP) or not used (negated rule, e.g., ¬MP) in an inference scenario. The set of all 16 inference patterns is called ℛ.

To draw plausible inferences with respect to an inference rule, a plausibility preorder ≼ has to be defined on the set of worlds. Each inference pattern ∈ ℛ imposes a set of plausibility constraints which is called (). () is satisfiable if and only if there is a total preorder ≼ that satisfies all constraints in (). In this case, we call the inference pattern rational. Otherwise, the inference pattern is irrational. Inspecting all ∈ ℛ we obtain that only two patterns, namely (MP, ¬MT, ¬AC, DA) and (¬MP, MT, AC, ¬DA), are irrational because the imposed constraints result in cyclic relations. In over 60 empirical studies investigated so far [ 2 ], hardly any irrational patterns could be found (less than 2%). 4. Ranking-Based Semantics of First-Order Conditionals Now we briefly sketch how the ranking-based semantics for propositional conditionals can be lifted to first-order conditionals according to [ 7 ]. From this, ranking-based interpretations of defeasible subsumptions as open conditionals can be easily obtained.

Let Σ be a first-order signature consisting of a finite set of predicates Σ and a finite set of constant symbols = Σ but without function symbols of arity > 0. Let ℒΣ be the first-order language that allows no nested quantification, i.e., all quantified formulas are either universal or existential formulas. ℒΣ is extended by a conditional operator “ | ” to a conditional language (ℒΣ | ℒΣ) containing first-order conditionals ( | ) with , ∈ ℒΣ, and (universally or existentially) quantified conditionals ∀⃗( | ), ∃⃗( | ). When writing ((⃗) | (⃗)), we assume ⃗ to contain all free variables occurring in either or . Conditionals cannot be nested.

A first-order knowledge base ℬ = ⟨ℱ , ℛ⟩ consists of a first-order conditional knowledge base ℛ, together with a set ℱ of closed formulas from ℒΣ, called facts. For an open conditional ((⃗) | (⃗)) ∈ (ℒΣ | ℒΣ) let ℋ((⃗) | (⃗)) denote the set of all constant vectors ⃗ used for proper groundings of ((⃗) | (⃗)) from the Herbrand universe ℋΣ, i. e. ℋ((⃗) | (⃗)) = Σ|⃗| where |⃗| is the length of ⃗.

Just as in the propositional case, a ranking function on Ω Σ is a function : Ω Σ → N ∪ {∞} with − 1(0) ̸= ∅. The ranks of closed formulas are defined as in the propositional case, while the ranks of open formulas are defined as the ranks as their most plausible instances: ((⃗)) = min ((⃗)).

⃗∈ℋ(⃗)

Generalizing the notion of acceptance of a first-order formula or conditional is straightforward for closed formulas and conditionals. The treatment of acceptance of open formulas is more intricate. The basic idea here is that such (conditional) open statements hold if there are individuals called representatives that provide most convincing instances of the respective conditional. For first-order knowledge bases ℬ = ⟨ℱ , ℛ⟩, we say that a ranking function accepts ℛ, denoted by |= ℛ, if |= for all ∈ ℛ. Furthermore, accepts ℬ, denoted by |= ℬ, if () = ∞ for all ̸|= ℱ , and |= ℛ.

To reason from a first-order knowledge base ℬ = ⟨ℱ , ℛ⟩, we need to define inductively specific ranking functions which are models of ℬ. For conditional knowledge bases ℛ, we carry over the idea of (propositional) c-representations [ 9 ] to the first-order case. All c-representations of ℛ share similarly good properties for yielding high-quality inferences from ℛ resp. ℬ. So basically, all c-representations can be used as inductive models, or one might consider the skeptical inference over all c-representations. For further details, please see [ 7 ].

References

[1] C. Eichhorn , G. Kern-Isberner , M. Ragni , Rational Inference Patterns Based on Conditional Logic , in: S. McIlraith , K. Weinberger (Eds.), Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence , (AAAI-18) , AAAI Press, 1827 - 1834 , URL https://www. aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/16834, 2018 .

[2] L.-P. Spiegel , G. Kern-Isberner , M. Ragni , Rational Inference Patterns, in: A. Nayak , A . Sharma (Eds.), Proceedings of the 16th Pacific Rim International Conference on Artificial Intelligence PRICAI 2019 , no. 11670 in Lecture Notes in Artificial Intelligence , Springer, Switzerland, ISBN 978-3-030-29907-1 , 405 - 417 , 2019 .

[3] S. Kraus , D. Lehmann , M. Magidor , Nonmonotonic reasoning, preferential models and cumulative logics , Artificial Intelligence 44 ( 1990 ) 167 - 207 .

[4] D. Makinson , General Patterns in Nonmonotonic Reasoning , in: D. M. Gabbay , C. J. Hogger , J. A. Robinson (Eds.), Handbook of Logic in Artificial Intelligence and Logic Programming , vol. 3 , Oxford University Press, New York, NY, USA, 35 - 110 , 1994 .

[5] W. Spohn , Ordinal Conditional Functions: A Dynamic Theory of Epistemic States , in: Causation in Decision, Belief Change and Statistics: Proceedings of the Irvine Conference on Probability and Causation , vol. 42 of The Western Ontario Series in Philosophy of Science, Springer Science+Business Media, Dordrecht, NL, 105 - 134 , 1988 .

[6] W. Spohn , The Laws of Belief: Ranking Theory and Its Philosophical Applications , Oxford University Press, Oxford, UK, 2012 .

[7] GabrieleKern-Isberner , M. Thimm , A Ranking Semantics for First-Order Conditionals , in: L. De Raedt , C. Bessiere , D. Dubois , P. Doherty , P. Frasconi , F. Heintz , P. Lucas (Eds.), Proceedings 20th European Conference on Artificial Intelligence, ECAI-2012 , no. 242 in Frontiers in Artificial Intelligence and Applications , IOS Press, ISBN 978-1-61499-097-0 , 456 - 461 , 2012 .

[8] B. de Finetti , Theory of Probability , vol. 1 , 2 , John Wiley and Sons, New York, NY, USA, 1974 .

[9] G. Kern-Isberner , A thorough axiomatization of a principle of conditional preservation in belief revision , Annals of Mathematics and Artificial Intelligence 40 ( 1-2 ) ( 2004 ) 127 - 164 .