InfOCF-Web: An Online Tool for Nonmonotonic Reasoning with Conditionals and Ranking Functions

1 Introduction

Reasoning with conditionals encoding plausible rules of the form "If A, then usually B" has been an area of interest in AI for a long time. While many different semantic approaches have been proposed for dealing with conditionals (e.g. [Lewis, 1973; Kraus et al., 1990; Benferhat et al., 1999]), the actual implementation of the resulting nonmonotonic inference relations seem to have attracted less attention. InfOCF-Web is a system that in addition to providing implementations of system P [Adams, 1975] and system Z [Pearl, 1990] inference, realizes various inference relations based on c-representations [Kern-Isberner, 2001] as models for conditional knowledge bases. It supports several modes of inference and different notions of minimality. The main objective of InfOCF-Web is to easily enable experiments regarding model computations, query answering, and comparison of inference results for small knowledge bases via a web interface. InfOCF-Web is the only currently available experimentation platform of its kind. For working with e.g. multiple or larger knowledge bases and queries, the Java library InfOCF-Lib underlying InfOCF-Web is available.

2 Background: Conditionals and OCFs

Let L be a propositional language over a finite signature Σ. We write AB for A ∧ B for formulas A,B ∈ L. We denote the set of all interpretations over L as Ω. For ω ∈ Ω, ω |= A means that A ∈ L holds in ω. We define the set (L | L) = {(B|A) | A,B ∈ L} of conditionals over L. The intuition of a conditional (B|A) is that if A holds then usually B holds, too. As semantics for conditionals, we use functions κ : Ω → N such that κ(ω) = 0 for at least one ω ∈ Ω, called ordinal conditional functions (OCF), introduced (in a more general form) in [Spohn, 1988]. They express degrees of plausibility of possible worlds where a lower degree denotes "less surprising". Each κ uniquely extends to a function mapping sentences to N ∪ {∞} given by κ(A) = min{κ(ω) | ω |= A} where min∅ = ∞. An OCF κ accepts a conditional (B|A), written κ |= (B|A), if κ(AB) < κ(AB). This can also be understood as a nonmonotonic inference relation where A κ-entails B, written A|∼ κB, if κ accepts (B|A); formally, this is given by

A finite set R ⊆ (L|L) of conditionals is called a knowledge base. An OCF κ accepts R, written κ |= R, if κ accepts all conditionals in R, and R is consistent if an OCF accepting R exists [Goldszmidt and Pearl, 1996].

3 Main Features of InfOCF-Web

(1) System P The axiom system P [Adams, 1975; Kraus et al., 1990] provides an important standard for plausible, nonmonotonic inferences. B is a system P inference from A in the context of R, written A|∼pRB, if B can be derived from the conditionals in R using the axioms of system P. This holds iff A |∼ κB for all κ |= R [Kraus et al., 1990].

(2) System Z is based on the ranking function κZ , which is the unique Pareto-minimal OCF that accepts R [Pearl, 1990]. A conditional (B|A) is tolerated by a set of conditionals R if there is a world ω ∈ Ω such that ω |= AB and ω |= ∧ni=1 (Ai ∨ Bi). The definition of κZ relies on the unique inclusion-maximal partition of R, denoted by OP(R) = (R0, . . . , Rk), which is the ordered partition of R where each Ri is the (with respect to set inclusion) maximal subset of ⋃kj=i Rj that is tolerated by ⋃kj=i Rj [Goldszmidt and Pearl, 1996]. B can be inferred from A by system Z in the context of R iff A |∼ κZ B holds.

(3) C-Representations Other than system Z, the approach of c-representations does not use the most severe falsification of a conditional, but assigns an individual impact to each conditional and generates the world ranks as a sum of impacts of falsified conditionals. For an in-depth introduction to crepresentations and their use of the principle of conditional preservation ensured by respecting conditional structures, we refer to [Kern-Isberner, 2001; Kern-Isberner, 2004].

Definition 1 (c-representation [Kern-Isberner, 2001]). A crepresentation of a knowledge base R is a ranking function κ #� η constructed from #� η = (η1 , . . . , ηn) with integer impacts ηi ∈ N0 , i ∈ {1 , . . . , n} assigned to each conditional (Bi|Ai) such that κ accepts R and is given by:

While for each consistent R, the system Z ranking function κZ is uniquely determined, there may be many different c-representations of R, denoted by Oc(R). They can be characterized as the solutions of a constraint satisfaction problem CR(R) [Kern-Isberner, 2004; Beierle et al., 2018].

Definition 2 (CR(R)). Let R = {(B1|A1), . . . , (Bn|An)}. The constraint satisfaction problem for c-representations of R, denoted by CR(R), on the constraint variables {η1, . . . , ηn} ranging over N0 is given by the the constraints, for all i ∈ {1, . . . , n}:

A solution of CR(R) is an n-tuple (η1, . . . , ηn) ∈ Nn0 . For a constraint satisfaction problem CSP, the set of solutions is Sol(CSP). It has been shown that CR(R) is sound and complete, i.e., Oc(R) = {κ#� η | #� η ∈ Sol(CR(R))} [KernIsberner, 2004], see also [Beierle et al., 2018].

(4) Modes of Inference As pointed out in [Makinson, 1994], historically there have been three different viewpoints when working with multiple plausible models for a knowledge base R: the choice perspective, focusing on a selected model, the skeptical perspective, considering the intersection of all models, and the credulous perspective, considering the union of all models. System Z represents the choice perspective by identifying a single ranking model for every consistent knowledge base. In [Beierle et al., 2016b], the notion of weakly skeptical inference is introduced. Here, we formalize these different modes of inference over any set of OCFs.

Definition 3 (inference modes over M). Let R be a knowledge base, M be a set of ranking models of R, and let A and B be formulas. Then B is a skeptical (credulous, or weakly skeptical, respectively) inference over M in the context of R from A, denoted by A |∼sk ,M R B (A|∼cr,M R B, or A|∼ws,M R B, respectively) if the following holds:

• A|∼sk,M R B, if A|∼κB for all κ ∈M.
• A|∼cr,M R B, if there is a κ ∈M such that A|∼κB.
• A|∼ws,M R B, if A ≡ ⊥, or there is a κ ∈ M such that A |∼κB and there is no κ ∈ M such that A |∼κB.

(5) C-Inference Every single c-representation induces a nonmonotonic inference relation as defined in (1). Applying the different inference modes to the set of all c-representations yields the notion of c-inference [Beierle et al., 2016a]. Then B is a skeptical (credulous, or weakly skeptical, respectively) c-inference in the context of R from A, denoted by A |∼sk ,c R B (A |∼cr ,c R B, or A |∼ws,c R B, respectively), if A|∼sk,M R B (A |∼cr ,M R B, or A|∼ws,M R B, respectively) withM = Oc(R).

(6) Minimal models While c-representations provide an excellent basis for model-based inference [Kern-Isberner, 2002; Kern-Isberner, 2001], from the point of view of minimal specificity (see e.g. [Benferhat et al., 1992]), those crepresentations yielding minimal degrees of implausibility are most interesting [Beierle et al., 2013] For a knowledge base R and #� η = (η1, . . . , ηn) and #� η ′ = (η′1 , . . . , η′n ) with #� η , #� η ′ ∈ Sol(CR(R)), we define:

We write #� η ≺· #� η ′ if #� η ≼· #� η ′ and #� η ′ ̸≼· #� η for · ∈ {+, cw,O}. A vector #� η is sum-minimal if #� η ≼+ #� η ′ for all #� η ′ ∈ Sol(CR(R)); it is componentwise minimal (or cw-minimal) if there is no vector #� η ′ ∈ Sol(CR(R)) such that #� η ′ ≺cw #� η ; and it is ind-minimal if there is no vector #� η ′ ∈ Sol(CR(R)) such that #� η ′ ≺O #� η .

Thus, while sum-minimal and cw-minimal are defined by just taking the components of the solution vectors #� η into account, ind-minimality refers to the OCF induced by #� η .

1. Minimal c-inference is obtained by combining the different inference modes with sets of minimal models. Let
2. ∈ {+, cw,O}. Then B is a skeptical (credulous, or weakly skeptical, respectively) ·-min-inference in the context of R from A, denoted by A|∼sk,· R B (A|∼cr,· R B, or A|∼ws,· R B, resp.), if A|∼sk,M· R B (A|∼cr,M· R B, or A|∼ws,M· R B, resp.) with M· = {κ#� η | #� η ∈ Sol(CR(R)) and #� η is ·-minimal}.

Each of the various c-inference relations presented above can be approximated and captured by adding ηi ⩽ MI to the underlying CSP CR(R), thus taking only those impact vectors into account whose impacts are not greater than the maximal impact MI ∈ N [Beierle and Kutsch, 2019].

4 SystemWalkthrough and Realisation

InfOCF-Web 1 provides implementations for all inference systems presented in the previous section. Its user interface is shown in Figure 1. In the top left, the user can either manually enter a conditional knowledge base, load a knowledge base from a file, or load a pre-selected demo knowledge base. The syntax is briefly described in the user interface and follows the structure illustrated by the knowledge base Rbird given in Figure 1. To the left of the knowledge base, the user can select ranking models to be calculated. Besides the finite sets of minimal c-representations, the set of all c-representations up to a selected maximal impact can be calculated. The field labelled 'Solutions' then shows the calculated impact vectors, while the top right field will show the actual ranking functions induced by the solutions. If the system Z ranking function is computed, the solutions field will show the ordered partition on which the system Z ranking model is based. The calculated ranking functions can then be downloaded in a convenient csv-format. For Rbird, there are two cw-minimal c-representations induced by the impact vectors #� η1 = (1, 1, 0, 2, 2) and #� η2 = (1, 0, 1, 2, 2). The first few possible worlds and the ranks under the c-representation κ#� η1 can be seen in the top right in Figure 1.

1 https://www.fernuni-hagen.de/wbs/research/infocf-web/

The bottom half of the interface is used for querying the inference relations induced by the loaded knowledge base. The user can select multiple sets of c-representations as well as system Z and system P inference. A selected maximal impact is used for inference over sets of c-representations employing the inference modes skeptical, weakly skeptical, and credulous. The query is entered as 'A entails B' for two formulas A and B. Since system P and system Z inference are not affected by the selected inference mode (system P inference is inherently skeptical, while in the case of system Z inference the three inference modes coincide), the query results are displayed next to the query itself. The results for the selected c-inference relations are displayed in a table underneath the query. Figure 1 shows the results for the query 'Does f ∧ b entail a?'. The answers determined by InfOCF-Web for all selected inference systems show that system P and system Z agree on this query, while there are differences among the various c-inference relations; a thorough investigation of properties and interrelationships of all inference methods provided by InfOCF-Web can be found in [Beierle et al., 2021].

InfOCF-Web is a web application based on the Java library InfOCF-Lib [Kutsch, 2019]. System P inference is implemented by computing the ordered partition and thus testing the consistency of the knowledge base augmented by the negated query. System Z inference, as well as minimal cinference relations, are implemented by calculating the necessary ranking functions and checking the minimal ranks of verification and falsification of the query. While computing OCFs induced by impact vectors for c-representations is done in Java [Kutsch, 2020], the impact vectors are computed as solutions of CR(R) by employing a CSP solver component implemented in a Prolog backend [Beierle et al., 2013]; also answering c-inferences over all c-representations is performed by a Prolog CSP solver by checking the solvability of corresponding CSPs (cf. [Beierle et al., 2018]). Whereas the objective of InfOCF-Web is to offer a convenient web interface for small scale inference experiments, InfOCF-Lib offers a broad selection of classes that allow the user to construct conditional knowledge bases, calculate various sets of ranking functions, and solve inference tasks also with respect to sets of knowledge bases and multiple queries; furthermore, sophisticated implementation features such as employing compilation techniques [Beierle et al., 2019] or additional facilities like computing complete inference closures [Kutsch, 2020; Kutsch and Beierle, 2021] are provided.

Acknowledgements

We are grateful to Martin Austen, Alexander Droßel, Fadil Kallat, Matthias Porath, Sandra Schufmann, Leon Schwarzer, Karl S¨odler, and Matthias Wirths for being involved in creating InfOCF-Web. This work was partially supported by DFG Grant BE 1700/9-1 awarded to Christoph Beierle.