Equivalence and Splitting Techniques for Ranking Functions in Knowledge Representation and Belief Change Technische Universität Dortmund (TU Dortmund University) , August-Schmidt-Straße 1, 44227 Dortmund , Germany 7 13

My research revolves around conditionals and ordinal conditional functions (OCFs), which assign implausibility ranks to possible worlds. OCFs can be considered an implementation of total preorders (TPOs) representing epistemic states and are, therefore, relevant for knowledge representation, non-monotonic reasoning and belief revision. This paper briefly discusses the correspondence between OCFs and TPOs, as well as applications to belief change and nonmonotonic reasoning, connections to defeasible subsumptions in description logics, and neuro-symbolic applications.

 eol>conditionals ranking functions epistemic states knowledge representation belief change splitting techniques -

Alexander Hahn

 1. Introduction 2. Belief Change and Inductive Reasoning based on Epistemic States

Belief change refers to updating an agent’s beliefs in the light of new information using a revision operator * , and inductive reasoning refers to the use of inference relations |∼ Δ based on some form of background knowledge ∆ . These two fields are deeply connected through the utilization of conditional information.

2.1. Iterated Belief Revision

The popular AGM framework [ 1 ] considers three types of one-step belief changes of belief sets: expansion (new information is fully accepted), revision (new information is accepted, but some current beliefs may need to be given up), and contraction (some current beliefs are eliminated).

When considering iterated revision, i.e. allowing multiple belief revision steps in a row, paying special attention to conditional beliefs is of crucial importance to guarantee reasonable results. Therefore, revision of epistemic states, which may contain more information than just the set of propositional formulas an agent believes at a given time, is necessary. This is the core idea of the so-called DP framework of iterated belief revision [ 2 ].

Epistemic states Ψ are often represented by total preorders (TPOs) ⪯ Ψ which order a set of possible worlds Ω according to their plausibility. A possible world 1 is more plausible in Ψ than another world 2 if 1 ⪯ Ψ 2. A conditional (|) is accepted by such a TPO if at least one possible world satisfying ∧ is more plausible than all worlds satisfying ∧ ¬.

Ordinal conditional functions (OCFs), often called ranking functions, were introduced in [ 3 ]. An OCF is a function : Ω → N 0 ∪ {∞} such that −1 (0) ̸= ∅, i.e., at least one world is assigned the rank 0. The rank of a formula is determined by () := min{() | |= } , and accepts a conditional (|) (short: |= (|) ) if ( ∧ ) < ( ∧ ¬) . Hence, OCFs can be considered an implementation of epistemic states.

A c-representation is a special kind of ranking function which is based on the underlying conditional structure of a given conditional knowledge base [ 4 ]. A simplified definition is given below. Definition 1 (c-representation). Let ∆ be a set of conditionals with ∆ = {( 1|1), . . . , (|)}. An OCF is a c-representation for ∆ if it satisfies |= for every ∈ ∆, and is of the form () = 0 + ∑︁ , 1≤≤ (1) for all with () ̸= ∞, where

0, ∈ N0 with > 0 suitably chosen to ensure that |= ( |).

Closely related are c-revisions (or, more generally, c-changes), which yield high-quality revision results by adhering to a so-called principle of conditional preservation, which was axiomatized in [ 4 ] and the ideas for which go back to [ 2 ].

2.2. Intentional Forgetting

There are two main classic kinds of forgetting in the literature: AGM contraction of propositional beliefs [ 1 ] and variable elimination in logic programming [ 5 ].

For epistemic states, and ranking functions in particular, other types of forgetting can be considered as well [ 6 ]. For example, conditionalization (i.e. considering only specific models) and marginalization (i.e. restricting the signature) of ranking functions may be interpreted as forgetting operations.

In ongoing work1 [ 7 ], we define several subclasses of c-contractions (i.e. forgetting operators in the form of c-changes) based on [ 8 ] and evaluate them according to postulates adapted from both the AGM and ASP literature on forgetting [ 9, 10 ]. The goal is to provide a unifying framework for forgetting in epistemic states.

2.3. Inductive Reasoning

In [ 11 ] inductive inference operators are defined using the axioms Direct Inference (DI) and Trivial Vacuity (TV).

Definition 2 (Inductive Inference Operators conditional belief base ∆ an inference relation |∼

C). An inductive inference operator C assigns to each Δ such that the following properties are satisfied: 1First results were presented at BRAON 2023 on Madeira. 7–13

(2) (3)

Often, inductive reasoning is performed by (explicitly or implicitly) checking the conditionals accepted by an epistemic state induced by ∆ . Moreover, inductive reasoning can be seen as a special case of belief revision [ 12 ].

3. Relationship between Total Preorders and Ranking Functions

Clearly, there is a correspondence between ranking functions and total preorders. In [ 13 ], this relationship is made precise via transformations, which are defined as follows.

Definition 3 (transformation operators). The transformation operator maps each OCF to a TPO ⪯ such that for all possible worlds 1, 2 ∈ Ω holds. The transformation operator maps each TPO ⪯ Ψ to a ranking function Ψ by setting 1 ⪯ 2 if (

1) ⩽ ( 2) Ψ() = min{() | ∈ −1 (Ψ)}. (DI) (|) ∈ ∆ implies |∼

Δ . (TV) If ∆ = ∅, then |∼

Δ only if |= .

The operator is a well-defined such that Ψ(1) ≤ Ψ(2) if 1 ⪯ Ψ 2 holds, i.e., Ψ ∈ −1 (Ψ) . Moreover, it holds that ∘ = , but ∘ ̸= in general.

There are several open questions regarding the relationship between TPOs and OCFs: If one wanted to implement TPO revision using ranking functions, which OCF would be the most adequate to represent a TPO in a revision scenario? And in which cases is the chosen ranking representation irrelevant, and any ranking function representing the total preorder would yield the same revision result in the end? The diference between the possible ranking representations lies in the position of the empty layers in the OCF, i.e. the natural numbers to which no world is assigned. Do these empty layers have drawbacks or do they ofer advantages over TPOs?

In [ 14 ], first steps were taken towards answering the questions stated above by formalizing a notion of revision equivalence of ranking functions, i.e. a property of equivalent ranking functions to remain equivalent after revising them by the same information, and by providing first results for how revision equivalence can be ensured. It turns out that the DP postulates alone are not strong enough to guarantee a preservation of equivalence.

Preservation of equivalence between ranking functions is, of course, not only relevant for revision, but also for other belief change scenarios. For example, in [ 7 ], equivalence postulates are considered for forgetting operators.

4. Splitting Techniques

Splitting techniques can be used to handle epistemic states, and OCFs in particular, in a modular way. For my research, I mainly focus on two kinds of splittings: syntax splittings and case splittings.

4.1. Syntax Splitting

The concept of syntax splitting for propositional revision goes back to [ 15 ]. The idea is to take relevance into account by partitioning the propositional signature and only changing those beliefs during revision for which the new information is syntactically relevant. In order to do so, the belief set (resp. the conditional knowledge base, or even the whole epistemic state) is split based on the partition of the syntax. Afterwards, belief change or inference can be performed within the relevant local context.

Syntax splitting is useful because it allows for revisions and reasoning to be executed more eficiently (at least when only a small part of the signature should be afected), since reducing the signature means exponentially reducing the amount of possible worlds that need to be considered.

c-Revisions fulfill (a strong version of) syntax splitting [ 16 ], and inductive inference relations based on c-representations (c-inference) satisfy adopted syntax splitting postulates for inductive reasoning [ 11 ]. In ongoing research [ 17 ] building on [ 16 ], we propose merging principles and strategies for marginalized epistemic states, with a focus on preserving syntax splittings.

4.2. Kinematics

The kinematics principle has its origins in probabilistic revision [ 18, 19 ] and was adapted as ranking kinematics for ranking functions in [ 20 ]. The idea behind ranking kinematics is that when revising by conditionals whose premises concern diferent exclusive cases (i.e. there exists a case splitting), one should be able to revise by each case independently from the other cases. Moreover, when revising by conditional information, the plausibility of a conditional’s premise should not afect the revision process. It was shown in [ 20 ] that c-revisions adhere to this principle.

Based on the work mentioned above, it is part of my ongoing research to explore how the ideas behind the kinematics principle can be utilized for inductive reasoning. As a first result, we propose a kinematics postulate for inductive reasoning operators in [ 21 ].

Like syntax splittings, case splittings ofer the possibility to perform revisions (and inference) more eficiently by reducing the set of possible worlds that need to be considered. The diference between the two splitting techniques is that syntax splitting can be used to focus on possible worlds over a reduced set of atoms, while case splittings can be used to focus on possible worlds satisfying a specific formula. Hence, a natural next step would be to combine these two kinds of splittings.

 5. Other Applications of OCFs

Besides investigating fundamental properties of TPO- and OCF-based operators, it is part of my ongoing research to explore possible applications of the OCF framework.

5.1. First-Order Conditional Semantics for Defeasible DL Knowledge Bases

Similar to propositional conditionals, defeasible subsumptions ⊏∼ encoding statements of the form “Usually, As are Bs” are an extension for description logics (DLs), which are (usually decidable) fragments of first-order logic. Diferent semantics for defeasible DL knowledge bases have been proposed [ 22, 23, 24 ], but their connection to OCF-based semantics remains to be explored. One notable work in this regard is [ 25 ].

In [ 26 ], first steps are taken to explore the relationship between a ranking-based first-order conditional semantics, which was proposed in [ 27 ], and DL approaches to defeasible reasoning [ 23, 24 ]. Moreover, it is proven that the OCF-based approach fulfills several rationality postulates proposed for non-monotonic reasoning in DLs by [ 23, 28 ].

A key diference is that many DL semantics rely on an orderings over domain elements, representing typicality, while OCFs represent orderings over possible worlds. Defeasible subsumptions between concepts are often evaluated by considering the most typical elements for a specific concept. For ifrst-order conditionals, however, representatives for conditionals (instead of individual predicates) are considered. The connection between typical elements (for predicates resp. concepts) and representatives (for conditionals resp. defeasible subsumptions) remains to be explored.

 5.2. Neuro-Symbolic Applications

Neuro-symbolic approaches combine neural networks and formal logics, either for the purpose of improving a neural network’s inferential capabilities or as a means to explain the inner workings of neural networks, which are often perceived as a “black box” by users.

In [ 29 ], we propose a methodology to extract propositional conditional knowledge bases from trained feed-forward neural networks. Similar to an approach by [ 30 ] for the extraction of defeasible DL knowledge bases from such networks, neurons are represented as atomic propositions, and connections between neurons are encoded as conditionals. However, our approach is purely qualitative. Our results show that the extracted knowledge bases do not invent inferences, i.e. everything inferred from those knowledge bases can be inferred from the neural network itself too. However, the converse does not necessarily hold. Thus, an interesting question is how far the accuracy of OCF-based qualitative explanations for neural networks can be pushed.

5.3. Epistemic Change Explanation

Even logic-based methods can appear as “black boxes” when the underlying mechanisms are unknown. When an epistemic state change is observed from the outside, i.e. only the prior and posterior state are known, it is not obvious whether the underlying belief change mechanism satisfies desired postulates.

In [ 31 ], we explore how TPOs and OCFs can be utilized in order to explain epistemic state changes, which correspond to changes in conditional beliefs. We investigate under which circumstances a transition from one epistemic state (represented as a TPO or OCF) to another can be modeled as a belief change process in (extensions of) the AGM/DP framework.

6. Summary and Future Work

The goal of my research is to contribute to the topics presented in this paper, with a focus on applying OCF-splitting techniques to belief revision and non-monotonic reasoning.

One part of my research is concerned with forgetting in epistemic states. In [ 7 ], a unifying framework for OCF-based forgetting operators will be presented, as well as an evaluation of postulates inspired by both the AGM and ASP literature.

Another interesting research question is how results for TPOs in the literature transfer to OCFs and vice versa, and whether qualitative versions of techniques developed for OCFs can be formulated in the style of [ 13 ]. Closely related is the investigation of limitations for the implementation of TPOs via OCFs. The paper [ 14 ] contains a first milestone in these directions by providing a formalization of revision equivalence and first results on how to ensure preservation of equivalence between ranking functions across revisions.

A proposal for a kinematics principle for inductive reasoning will be presented in [ 21 ]. While syntax splittings and case splittings already ofer a lot of flexibility when processing OCFs, the question of whether and how these two approaches can be combined is still open. The goal here is to develop methods to split OCFs in both ways, process the parts individually and then merge them back together. Some results in this direction are expected to be published in the near future [ 17 ].

As for first-order conditionals, we present some first results on properties from the DL literature satisfied by first-order OCF-based semantics in [ 26 ]. My goal is to continue working towards achieving a deeper understanding for properties of semantics for first-order conditional knowledge bases, as well as the relationship between (OCF-based semantics for) first-order conditionals and defeasible subsumptions.

Since neural networks (or statistical learning methods in general) are powerful tools yet often opaque to the user, there is a lot of potential for both explanations and improvements of their behavior based on formal logics. My goal in that respect is to continue to explore how OCFs can be utilized to that end. A first approach for how a propositional conditional knowledge base with an OCF-based semantics can be extracted from a feed-forward neural network can be found in [ 29 ].

Acknowledgments

Alexander Hahn was supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation), project number 512363537, grant KE 1413/15-1 awarded to Gabriele Kern-Isberner.

 Declaration on Generative AI

The author has not employed any Generative AI tools.

 [1] C. E. Alchourrón , P. Gärdenfors , D. Makinson , On the logic of theory change: Partial meet contraction and revision functions , J. Symb. Log . 50 ( 1985 ) 510 - 530 . doi: 10 .2307/2274239. [2] A. Darwiche , J. Pearl , On the logic of iterated belief revision , Artif. Intell . 89 ( 1997 ) 1 - 29 . doi: 10 .1016/s0004- 3702 ( 96 ) 00038 - 0 . [3] W. Spohn , Ordinal conditional functions: A dynamic theory of epistemic states , in: W. L. Harper , B. Skyrms (Eds.), Causation in Decision, Belief Change , and Statistics, Springer, 1988 , pp. 105 - 134 . doi: 10 .1007/ 978 -94-009-2865- 7 _ 6 . [4] G. Kern-Isberner , A thorough axiomatization of a principle of conditional preservation in belief revision , Ann. Math. Artif. Intell. 40 ( 2004 ) 127 - 164 . [5] F. Lin , R. Reiter , Forget it!, in: AAAI Fall Symposium on Relevance , 1994 , pp. 154 - 159 . [6] C. Beierle , G. Kern-Isberner , K. Sauerwald , T. Bock , M. Ragni , Towards a general framework for kinds of forgetting in common-sense belief management , Künstl. Intell . 33 ( 2018 ) 57 - 68 . doi: 10 .1007/s13218-018-0567-3. [7] C. Beierle , A. Hahn , D. Howey , G. Kern-Isberner , K. Sauerwald , A general framework of epistemic forgetting and its instantiation by ranking functions , 2025 . arXiv: 2508 . 21441 . [8] G. Kern-Isberner , T. Bock , K. Sauerwald , C. Beierle , Iterated contraction of propositions and conditionals under the principle of conditional preservation , in: C. Benzmüller , C. Lisetti , M. Theobald (Eds.), GCAI 2017. 3rd Global Conference on Artificial Intelligence , volume 50 of EPiC Series in Computing, EasyChair, 2017 , pp. 78 - 92 . doi: 10 .29007/3q8l. [9] G. Kern-Isberner , T. Bock , C. Beierle , K. Sauerwald , Axiomatic evaluation of epistemic forgetting operators , in: R. Barták , K. W. Brawner (Eds.), Proceedings of the Thirty-Second International Florida Artificial Intelligence Research Society Conference (FLAIRS 2019 ), AAAI Press, 2019 , pp. 470 - 475 . URL: https://aaai.org/ocs/index.php/FLAIRS/FLAIRS19/paper/view/18231. [10] G. Kern-Isberner , T. Bock , K. Sauerwald , C. Beierle , Belief change properties of forgetting operations over ranking functions , in: A. C. Nayak , A . Sharma (Eds.), PRICAI 2019: Trends in Artificial Intelligence , volume 11670 of LNCS/LNAI , Springer, Cham, 2019 , pp. 459 - 472 . doi: 10 .1007/ 978-3- 030 -29908-8_ 37 . [11] G. Kern-Isberner , C. Beierle , G. Brewka, Syntax splitting = relevance + independence: New postulates for nonmonotonic reasoning from conditional belief bases , in: Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning (KR 2020 ), Rhodes, Greece, 2020 , pp. 560 - 571 . doi: 10 .24963/kr.2020/56. [12] G. Kern-Isberner , W. Spohn , Inductive reasoning, conditionals, and belief dynamics , Journal of Applied Logics 11 ( 2024 ) 89 - 127 . [13] G. Kern-Isberner , M. Sezgin , C. Beierle , A kinematics principle for iterated revision , Artif. Intell . 314 ( 2023 ). doi: 10 .1016/j.artint. 2022 . 103827 . [14] G. Kern-Isberner , A. Hahn , J. Haldimann , C. Beierle , Total preorders vs ranking functions under belief revision - the dynamics of empty layers , in: P. Marquis, M. Ortiz , M. Pagnucco (Eds.), Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning (KR 2024 ), Hanoi, Vietnam, 2024 , pp. 498 - 508 . doi: 10 .24963/KR. 2024 /47. [15] R. Parikh , Beliefs, belief revision, and splitting languages , in: L. S. Moss, J. Ginzburg , M. de Rijke (Eds.), Logic, Language, and Computation, volume 2 , CSLI , Stanford, CA, USA, 1999 , pp. 266 - 278 . [16] G. Kern-Isberner , G. Brewka, Strong syntax splitting for iterated belief revision , in: C. Sierra (Ed.), Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI 2017 ), Melbourne, Australia, 2017 , pp. 1131 - 1137 . doi: 10 .24963/IJCAI. 2017 /157. [17] A. Hahn , G. Kern-Isberner , L.-P. Spiegel , C. Beierle , Merging marginalized total preorders, 2025 . Unpublished. Accepted to NMR 2025 . [18] R. C. Jefrey , The Logic of Decision, University of Chicago Press, 1965 . [19] J. E. Shore , R. W. Johnson, Axiomatic derivation of the principle of maximum entropy and the principle of minimum cross-entropy , IEEE Trans. Inf. Theory 26 ( 1980 ) 26 - 37 . doi: 10 .1109/TIT. 1980 . 1056144 . [20] M. Sezgin , G. Kern-Isberner , C. Beierle , Ranking kinematics for revising by contextual information , Ann. Math. Artif. Intell. 89 ( 2021 ) 1101 - 1131 . doi: 10 .1007/s10472-021-09746-2. [21] A. Hahn , G. Kern-Isberner , L.-P. Spiegel , C. Beierle , Kinematics principles for inductive reasoning from conditional belief bases , 2025 . Unpublished. Accepted to NMR 2025 . [22] G. Casini , T. Meyer, K. Moodley, R. Nortjé , Relevant closure: A new form of defeasible reasoning for description logics , in: E. Fermé, J. Leite (Eds.), Logics in Artificial Intelligence. JELIA 2014 , volume 8761 of LNCS/LNAI , Springer, 2014 , pp. 92 - 106 . doi: 10 .1007/978-3- 319 -11558- 0 _ 7 . [23] K. Britz , G. Casini, T. Meyer, K. Moodley, U. Sattler , I. Varzinczak , Principles of KLM-style defeasible description logics , ACM Trans. Comput. Log . 22 ( 2020 ) 1 - 46 . doi: 10 .1145/3420258. [24] L. Giordano , D. Theseider Dupré , An ASP approach for reasoning in a concept-aware multipreferential lightweight DL, Theory Pract . Log. Program. 20 ( 2020 ) 751 - 766 . doi: 10 .1017/ s1471068420000381. [25] J. Haldimann , C. Beierle , Characterizing multipreference closure with system W , in: F. Dupin de Saint-Cyr, M. Öztürk-Escofier , N. Potyka (Eds.), Scalable Uncertainty Management. SUM 2022 , volume 13562 of LNCS/LNAI , Springer, 2022 , pp. 79 - 91 . doi: 10 .1007/978-3- 031 -18843- 5 _ 6 . [26] A. Hahn , G. Kern-Isberner , T. Meyer, Ranking-based defeasible reasoning for restricted first-order conditionals applied to description logics , in: N. Gierasimczuk , J. Heyninck (Eds.), Proceedings of the 22nd International Workshop on Nonmonotonic Reasoning (NMR 2024 ), Hanoi, Vietnam, volume 3835 of CEUR-WS , 2024 , pp. 162 - 172 . URL: https://ceur-ws. org/ Vol- 3835 /paper17.pdf. [27] G. Kern-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. J. F. Lucas (Eds.), ECAI 2012 , volume 242 of FAIA , IOS Press, 2012 , pp. 456 - 461 . doi: 10 .3233/978-1- 61499 -098-7-456. [28] G. Casini , T. Meyer, G. Paterson-Jones , I. Varzinczak , KLM-style defeasibility for restricted firstorder logic , in: G. Governatori, A.-Y. Turhan (Eds.), Rules and Reasoning . RuleML+RR 2022 , volume 13752 of LNCS , Springer, 2022 , pp. 81 - 94 . doi: 10 .1007/978-3- 031 -21541- 4 _ 6 . [29] M. Wilhelm , A. Hahn , G. Kern-Isberner , Extraction of conditional belief bases and the system Z ranking model from multilayer perceptrons for binary classification , in: N. Gierasimczuk , J. Heyninck (Eds.), Proceedings of the 22nd International Workshop on Nonmonotonic Reasoning (NMR 2024 ), Hanoi, Vietnam, volume 3835 of CEUR-WS , 2024 , pp. 101 - 111 . URL: https://ceur-ws. org/ Vol- 3835 /paper11.pdf. [30] L. Giordano , D. Theseider Dupré , Weighted defeasible knowledge bases and a multipreference semantics for a deep neural network model , in: W. Faber, G. Friedrich, M. Gebser , M. Morak (Eds.), Logics in Artificial Intelligence. JELIA 2021 , volume 12678 of LNCS/LNAI , Springer, 2021 , pp. 225 - 242 . doi: 10 .1007/978-3- 030 -75775-5_ 16 . [31] A. Hahn , G. Kern-Isberner , L.-P. Spiegel , C. Beierle , Explaining changes in total preorders and ranking functions , in: K. Sauerwald, M. Thimm (Eds.), Symbolic and Quantitative Approaches to Reasoning with Uncertainty - 18th European Conference , ECSQARU 2025 , Hagen, Germany, September 23-26 , 2025 , Proceedings, volume 16099 of LNCS/LNAI , Springer, Cham, 2025 , pp. 285 - 300 . doi: 10 .1007/978-3- 032 -05134-9_ 20 .