Extraction of Conditional Belief Bases and the System Z Ranking Model From Multilayer Perceptrons for Binary Classification Marco Wilhelm, Alexander Hahn and Gabriele Kern-Isberner Dept. of Computer Science, TU Dortmund University, Dortmund, Germany Abstract We extract propositional conditional belief bases from multilayer perceptrons, a basic type of feedforward neural networks, and investigate the relation between these two prevalent formalisms from knowledge representation and reasoning (KRR) and machine learning (ML), respectively. The ultimate goal of our work is to imitate with the extracted belief base the main information flow in the original multilayer perceptron detached from specific input data. For this, we introduce a notion of sufficient (in)activators of neurons which reflect the most relevant connections within the multilayer perceptron that lead to the (in)activation of the subsequent neurons. While focusing on the binary multi-class classification task, we show that our approach produces consistent belief bases from which principled inferences can be drawn, for instance under System Z. In particular, no inferences are invented by the System Z ranking model that are not in accordance with the initial neural network. Keywords multilayer perceptrons, binary classification, belief base extraction, conditional reasoning, system Z 1. Introduction perceptrons are arranged to at least three fully connected layers with neurons connected to the other neurons from Neural networks [1] are formal models studied in the re- the neighboring layers. The extracted belief base reflects the search field of machine learning (ML) which have con- main information flow within such a multilayer perceptron. tributed significantly to the recent success of AI. In neural The basic idea of our approach is to identify sets of pre- networks, input data is propagated through a network of decessors of a neuron ๐‘ the (in)activation of which is suf- neurons where neurons weight the received information ficient to (in)activate ๐‘ . Hereby, the (in)activation of a and process it to the subsequent neurons. Neural networks neuron means that an input of the multilayer perceptron are used in nearly every application domain with special triggers the neuron more (less) than a predefined threshold, abilities in data processing, pattern recognition, data mining, i.e., the output value of the neuron is larger (smaller) than and, what is in the focus of this paper, binary (multi-class) this threshold. Therewith, our approach is related to the classification [2]. A drawback of neural networks is that work in [10] which aims at identifying โ€œmost influentialโ€ they appear as a black box methodology. Usually, it is not neurons in neural networks, however without establishing very transparent why input data leads to a specific output. logical connections between these neurons. In contrast to neural networks, knowledge-based sys- In more detail, the main contributions of the present paper tems [3] from the field of knowledge representation and rea- are as follows: soning (KRR) typically provide a transparent and principled way of drawing inferences. A frequently used inference for- โ€ข We introduce a notion of sufficient (in)activators of malism, System Z [4], makes use of conditionals (๐ต|๐ด) in or- neurons (Definitions 6 and 7). der to represent defeasible statements of the form โ€œif ๐ด holds, โ€ข We show that sufficient (in)activators are indepen- then usually ๐ต holds, tooโ€ [5, 6]. Ranking functions ๐œ… [7] dent of the input of the multilayer perceptron (Propo- like the System Z ranking function give such conditionals sitions 2 and 3). a clear semantics by assigning (im)plausibility values to โ€ข Based on the notion of sufficient (in)activators, we sentences while postulating that the verification of a con- extract belief bases from multilayer perceptrons (Def- ditional (๐ต|๐ด) is more plausible than its falsification, in inition 9). The extracted belief bases are provably symbols ๐œ…(๐ด โˆง ๐ต) < ๐œ…(๐ด โˆง ยฌ๐ต). The ๐œ…-ranks according consistent with respect to ranking semantics (Propo- to System Z are gained by penalizing possible worlds for sition 5). falsifying conditionals, where the penalty points are the โ€ข We use the extracted belief bases and their System Z greater the more specific the falsified conditionals are. Al- ranking models for binary classification and relate ternative ranking semantics are provided by System P [8] their classification behavior to the direct classifica- and c-representations [9]. tion with the initial multilayer perceptrons (Propo- In this paper, we extract conditional belief bases from a sition 6). specific type of neural networks called multilayer percep- trons. Multilayer perceptrons are feedforward networks in With our approach we abstract from specific input data which information is always processed towards the output, and also from overlay effects of less relevant connections hence there are no cycles in the network. In contrast to in the neural networks. The most relevant connections are general feedforward networks, the neurons in multilayer formalized in form of easy to understand conditionals. Note that establishing such formal bridges between neural- and 22nd International Workshop on Nonmonotonic Reasoning, November 2-4, logic-based models is a very old enterprise and has been 2024, Hanoi, Vietnam pursued in the first papers on neural networks already [11].1 $ marco.wilhelm@tu-dortmund.de (M. Wilhelm); The rest of the paper is organized as follows. First we alexander.hahn@tu-dortmund.de (A. Hahn); gabriele.kern-isberner@tu-dortmund.de (G. Kern-Isberner) recall basics on multilayer perceptrons, in particular with  0000-0003-0266-2334 (M. Wilhelm); 0009-0008-6114-2594 (A. Hahn); respect to binary multi-class classification, and conditional 0000-0001-8689-5391 (G. Kern-Isberner) ยฉ 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribu- 1 tion 4.0 International (CC BY 4.0). We thank the anonymous referees for their valuable comments. CEUR ceur-ws.org Workshop ISSN 1613-0073 Proceedings Activation function Specification Range ๐‘1 โ–ถ ๐‘ฆ๐‘1 Identity ๐œ‘(๐‘ฅ) = {๏ธƒ ๐‘ฅ R ๐œˆ๐‘1 ,๐‘ 0, ๐‘ฅ < 0 Heaviside step ๐œ‘(๐‘ฅ) = {0, 1} ๐œˆ๐‘2 ,๐‘ 1, ๐‘ฅ โ‰ฅ 0 ๐‘2 โ–ถ ๐‘ฆ๐‘2 ๐‘ โ–ถ ๐‘ฆ๐‘ 1 Logistic function ๐œ‘(๐‘ฅ) = (0, 1) 1 + ๐‘’โˆ’๐‘ฅ ๐œˆ๐‘๐‘› ,๐‘ ๐‘’๐‘ฅ โˆ’ ๐‘’โˆ’๐‘ฅ .. Hyperbolic tangent ๐œ‘(๐‘ฅ) = ๐‘ฅ (โˆ’1, 1) . ๐‘’ + ๐‘’โˆ’๐‘ฅ ReLU ๐œ‘(๐‘ฅ) = max(0, ๐‘ฅ) Rโ‰ฅ0 ๐‘ ๐‘› โ–ถ ๐‘ฆ ๐‘๐‘› Table 1 Typical activation functions of neural networks. Figure 1: Schema of a neuron ๐‘ . reasoning based on ranking functions (Section 2). Then, we discuss related work on extracting belief bases from multi- input data for which the expected output is known. Here, we layer perceptrons within a Description Logic context and solely consider neural networks which are already trained. show that a naรฏve translation to propositional conditional belief bases works only to a limited extent (Section 3). Even- tually, we propose our novel approach on extracting belief Multilayer Perceptrons In neural networks, neurons bases based on sufficient (in)activators (Section 4) and use are usually assigned to layers with different functionalities. this approach for principled binary classification (Section 5). Neurons in the first layer, the input layer, receive the input We close the paper with a conclusion that points to future of the network, and neurons in the last layer, the output work (Section 6). layer, return the output. The layers in-between are called hidden layers. If a neural network is represented by an acyclic directed graph, it is called a feedforward network. 2. Preliminaries In feedforward networks information is always processed towards the output layer. Multilayer perceptrons constitute In this section, we recall preliminaries on multilayer percep- an important subclass of feedforward networks with edges trons with an application to binary multi-class classification only between adjacent layers and, taking this condition into first (Section 2.1). Then, we explain basics on reasoning with account, fully connected neurons. Multilayer perceptrons conditionals, in particular based on System Z (Section 2.2). have at least one hidden layer. This hidden layer (as well as a non-linear activation function) is necessary to distinguish 2.1. Multilayer Perceptrons for Binary data that is not linearly separable [12]. Multi-Class Classification Definition 1 (Multilayer Perceptron). A multilayer percep- Multilayer perceptrons (MLPs) constitute a widely used type tron โ„ณ๐œ‘ is a special neural network which is represented by of neural networks which expand single perceptrons to sev- a directed graph (๐’ฑโ„ณ๐œ‘ , โ„ฐโ„ณ๐œ‘ ) consisting of a set of vertices eral fully connected layers. We give a brief introduction to ๐’ฑโ„ณ๐œ‘ = {๐‘๐‘–,๐‘— | ๐‘– โˆˆ [๐‘š], ๐‘— โˆˆ [๐‘›๐‘– ]}, 2 neural networks in general and to MLPs in particular. Af- terwards, we discuss their application to binary multi-class the neurons in โ„ณ๐œ‘ , and a set of edges classification. โ„ฐโ„ณ๐œ‘ = {(๐‘๐‘–,๐‘— , ๐‘๐‘–+1,๐‘˜ ) Neural Networks Neural networks [1] are formal models | ๐‘– โˆˆ [๐‘š โˆ’ 1], ๐‘— โˆˆ [๐‘›๐‘– ], ๐‘˜ โˆˆ [๐‘›๐‘–+1 ]}, used to process information in form of data in modern AI systems. In the original sense, neural networks are func- where ๐‘š โˆˆ Nโ‰ฅ2 , and ๐‘›๐‘– โˆˆ N for ๐‘– โˆˆ [๐‘š]. Every edge tions ๐’ฉ : R๐‘› โ†’ R๐‘š where ๐‘› is the size of the real-valued (๐‘๐‘–,๐‘— , ๐‘๐‘–+1,๐‘˜ ) โˆˆ โ„ฐโ„ณ๐œ‘ is assigned a real-valued weight input vectors โƒ—๐‘ฅ, and where ๐‘š is the size of the real-valued ๐œˆ๐‘–,๐‘—,๐‘˜ = ๐œˆ๐‘๐‘–,๐‘— ,๐‘๐‘–+1,๐‘˜ , every neuron ๐‘0,๐‘— , ๐‘— โˆˆ [๐‘›0 ], in the output ๐’ฉ (๐‘ฅโƒ— ). The computation of ๐’ฉ (๐‘ฅ โƒ— ) is specified by a input layer is assigned the identity function ๐‘“0,๐‘— : R โ†’ R weighted directed graph the nodes of which are called neu- with ๐‘“0,๐‘— (๐‘ฅ) = ๐‘ฅ, and every further neuron ๐‘๐‘–,๐‘— with ๐‘– > 0, rons. The functionality of neurons is as follows. Neurons ๐‘ ๐‘— โˆˆ [๐‘›๐‘– ], is assigned a function ๐‘“๐‘๐‘–,๐‘— : R๐‘›๐‘–โˆ’1 +1 โ†’ R with receive information encoded as real numbers ๐‘ฆ๐‘๐‘– from their โˆ‘๏ธ ๐‘“๐‘๐‘–,๐‘— (๐‘ฅ โƒ— ) = ๐œ‘(๐›ฝ๐‘–,๐‘— + โƒ— )), (1) ๐œˆ๐‘–โˆ’1,โ„Ž,๐‘— ยท ๐‘“๐‘๐‘–โˆ’1,โ„Ž (๐‘ฅ parent nodes/neurons ๐‘๐‘– โˆˆ pa๐‘ , or the input vector โƒ—๐‘ฅ of โ„Žโˆˆ[๐‘›๐‘–โˆ’1 ] the network, process this information based on an activation function ๐œ‘๐‘ : R โ†’ R and possibly a bias ๐›ฝ๐‘ โˆˆ R, and send where ๐œ‘ is the activation function of โ„ณ๐œ‘ and ๐›ฝ๐‘–,๐‘— โˆˆ R is the processed information the bias of ๐‘๐‘–,๐‘— . The input of โ„ณ๐œ‘ is any vector โƒ—๐‘ฅ โˆˆ R๐‘›0 +1 โˆ‘๏ธ whereby the ๐‘—-th component of โƒ—๐‘ฅ is passed to the neuron ๐‘0,๐‘— , ๐‘ฆ๐‘ = ๐œ‘๐‘ (๐›ฝ๐‘ + ๐œˆ๐‘๐‘– ,๐‘ ยท ๐‘ฆ๐‘๐‘– ) and the output of โ„ณ๐œ‘ is ๐‘๐‘– โˆˆpa๐‘ โ„ณ๐œ‘ (๐‘ฅ โƒ— ) = (๐‘“๐‘๐‘š,0 (๐‘ฅ โƒ— )) โˆˆ R๐‘›๐‘š +1 . โƒ— ), . . . , ๐‘“๐‘๐‘š,๐‘›๐‘š (๐‘ฅ to their child nodes/neurons. Hereby, ๐œˆ๐‘๐‘– ,๐‘ โˆˆ R is the weight of the edge from ๐‘๐‘– to ๐‘ (cf. Figure 1). Neurons Figure 2 shows a schema of a multilayer perceptron with without child nodes return the output of the neural network. one hidden layer (๐‘š = 2). For a neuron ๐‘ โˆˆ โ„ณ๐œ‘ , we will Typical activation functions of neural networks are shown denote the set of its parent nodes by pa๐‘ which will help in Table 1. The weights of a neural network and the biases us to avoid indices. of the neurons are usually derived from training data, i.e., 2 For ๐‘š โˆˆ N, we abbreviate [๐‘š] = {0, 1, . . . , ๐‘š}. ๐‘0,0 ๐‘1,0 ๐‘2,0 ๐‘0,0 ๐‘1,0 ๐‘2,0 .. .. .. . . . ๐‘0,๐‘– ๐‘1,๐‘— ๐‘2,๐‘˜ ๐‘0,1 ๐‘1,1 ๐‘2,1 .. .. .. . . . ๐‘0,๐‘›0 ๐‘1,๐‘›1 ๐‘2,๐‘›2 ๐‘0,2 ๐‘1,2 ๐‘2,2 Figure 2: Multilayer perceptron with one hidden layer. Figure 3: Multilayer perceptron from Example 1. Edges with negative weights are dashed. Binary Multi-Class Classification A possible applica- ๐‘๐‘–,๐‘— ๐œˆ๐‘–,๐‘—,0 ๐œˆ๐‘–,๐‘—,1 ๐œˆ๐‘–,๐‘—,2 tion of neural networks in general and multilayer percep- ๐‘0,0 โˆ’1.27 0.91 โˆ’0.44 trons in particular is binary (multi-class) classification [2]. ๐‘0,1 1.23 0.81 0.27 For instance, the input โƒ—๐‘ฅ of a multilayer perceptron โ„ณ๐œ‘ ๐‘0,2 โˆ’0.91 โˆ’0.09 1.96 could represent medical patient data, and we could ask ๐‘1,0 1.62 โˆ’0.96 1.31 for therapies that are suited to cure the patient. In the ๐‘1,1 โˆ’1.19 1.15 1.46 easiest case, the neurons in the output layer of โ„ณ๐œ‘ rep- ๐‘1,2 0.14 โˆ’1.18 โˆ’0.14 resent the different therapies and are equipped with the Heaviside step function as activation function ๐œ‘ such Table 2 that โ„ณ๐œ‘ (๐‘ฅ โƒ— ) โˆˆ {0, 1}๐‘š for some ๐‘š โˆˆ N. Then, ๐‘ฆ๐‘– = 1, Weights of the multilayer perceptron from Example 1. where ๐‘ฆ๐‘– is the outcome of neuron ๐‘๐‘– in the output layer, can be interpreted as โ€œthe therapy ๐‘๐‘– is suited to cure the patient represented by โƒ—๐‘ฅ,โ€ and ๐‘ฆ1 = 0 can be understood as Example 1. We consider the multilayer perceptron โ„ณex log the opposite. from Figure 3 with the edge weights from Table 2 as a running In practice, one usually uses sigmoid functions like the lo- example. Further, we assume that the neurons in โ„ณex log are gistic function (cf. Table 1) for classification, instead, which unbiased (๐›ฝ๐‘๐‘–,๐‘— = 0), and let ๐œ = 0.3. For instance, for the range over the interval (0, 1) and, thus, allow for a grad- input vector โƒ—๐‘ฅ = (0.9, 0.8, 0.1), we obtain ual answer behavior. Furthermore, the Heaviside function cannot be used for gradient-based training because it is not ๐‘ฆ๐‘2,2 โ‰ˆ 0.844 differentiable at 0 and the derivative is 0 at all other points, while the logistics function can be differentiated any number so that โƒ—๐‘ฅ is classified as an instance of class ๐’ž๐‘2,2 when the of times which makes it particularly suited for numerical tolerance factor ๐œ is equal to or greater than 0.156. methods. In this paper, we equip multilayer perceptrons Besides the fact that sigmoid functions like the logistic with the logistic function as an activation function and de- function are common activation functions for classification note this by โ„ณlog . Our approach works with any sigmoid tasks, we will utilize in some proofs that logistic functions function, though. We consider the following three-valued are bounded between 0 and 1 (cf. the proofs of Proposi- interpretation of the output of neurons in โ„ณlog . tions 2 and 3). Definition 2 ((In)active Neurons). Let โ„ณlog be a multilayer Definition 3 (Classification Scheme). Let โ„ณlog be a multi- perceptron, let ๐‘ be a neuron in โ„ณlog , let โƒ—๐‘ฅ be an input vector layer perceptron with the logistic function as activation func- of โ„ณlog , and let ๐œ โˆˆ [0, 0.5). We call ๐œ a tolerance factor, tion, and let ๐œ be a tolerance factor. Then, we call (โ„ณlog , ๐œ ) and say that neuron ๐‘ is (cf. (1)) a classification scheme. โ€ข activated by โƒ—๐‘ฅ wrt. ๐œ , or active for short, iff Within our approach on extracting conditional belief โƒ— ) โ‰ฅ 1 โˆ’ ๐œ, ๐‘“๐‘ (๐‘ฅ bases from multilayer perceptrons, we will focus on the task of binary multi-class classification. โ€ข inactivated by โƒ—๐‘ฅ wrt. ๐œ , or inactive for short, iff โƒ— ) โ‰ค ๐œ, ๐‘“๐‘ (๐‘ฅ 2.2. Conditionals and System Z Within the field of nonmonotonic reasoning, conditionals [13] โ€ข ambiguous otherwise. constitute a widely used representation of defeasible knowl- With Definition 2, we can say that an input vector โƒ—๐‘ฅ edge resp. beliefs. Here, we consider conditionals defined of โ„ณlog is classified as an instance of class ๐’ž๐‘ , represented over a propositional language and interpret them via so- by the neuron ๐‘ in the output layer of โ„ณlog , if ๐‘ is acti- called ranking functions, in particular the System Z ranking vated by โƒ—๐‘ฅ, and โƒ—๐‘ฅ is declassified as an instance of class ๐’ž๐‘ model. if ๐‘ is inactivated by โƒ—๐‘ฅ. Otherwise, the membership to ๐’ž๐‘ is ambiguous. We give an example. Conditional Reasoning Let โ„’(ฮฃ) be a propositional lan- The resulting System Z ranking model is guage defined over a finite signature ฮฃ as usual.3 A condi- โŽง tional (๐ต|๐ด) with ๐ด, ๐ต โˆˆ โ„’(ฮฃ) is a formal representation โŽจ0, ๐œ” โˆˆ {๐‘๐‘“ ๐‘, ๐‘๐‘“ ๐‘, ๐‘๐‘“ ๐‘} โŽช of the defeasible statement: โ€œIf ๐ด holds, then usually ๐ต ๐œ…๐‘ฮ” (๐œ”) = 1, ๐œ” โˆˆ {๐‘๐‘“ ๐‘, ๐‘๐‘“ ๐‘} . holds, too.โ€ Finite sets of conditionals serve as belief bases. โŽช โŽฉ 2, ๐œ” โˆˆ {๐‘๐‘“ ๐‘, ๐‘๐‘“ ๐‘, ๐‘๐‘“ ๐‘} The semantics of conditionals is based on possible worlds. Here, possible worlds ๐œ” โˆˆ ฮฉ(ฮฃ) are the propositional inter- System Z coincides with rational closure [14]. pretations of โ„’(ฮฃ) represented as complete conjunctions of literals. That is, every atom from ฮฃ occurs in a possible world once, either positive or negated. A ranking func- 3. Related Work and Synaptic tion ๐œ… : ฮฉ(ฮฃ) โ†’ N0 โˆช {โˆž} [7] maps possible worlds to a Conditionals degree of implausibility while satisfying the normalization condition ๐œ…โˆ’1 (0) ฬธ= โˆ…. The higher the rank ๐œ…(๐œ”), the less In this section, we briefly recall the extraction of beliefs from plausible the possible world ๐œ” is. Hence, ๐œ…โˆ’1 (0) is the set neural networks as presented in [15] and provide a naรฏve of the most plausible possible words. Ranking functions are translation of this approach to propositional conditionals. extended to propositions via We also discuss why this naรฏve translation is too simple to capture the essential streams of information of a neural ๐œ…(๐ด) = min ๐œ…(๐œ”) network. ๐œ”โˆˆฮฉ(ฮฃ) : ๐œ”|=๐ด In [15], an extraction of belief bases from neural net- and accept a conditional (๐ต|๐ด) if ๐œ…(๐ด๐ต) < ๐œ…(๐ด๐ต). A works is proposed where the belief bases are defined over ranking function ๐œ… is a ranking model of a belief base ฮ” if ๐œ… defeasible subsumptions of Description Logic concepts.4 accepts all conditionals in ฮ”. If ฮ” has a ranking model, then Neurons ๐‘๐‘– are represented as atomic concepts ๐ถ๐‘– , and an it is called consistent. Ranking models ๐œ… of ฮ” yield a non- edge from a neuron ๐‘๐‘– to a neuron ๐‘๐‘— is represented as the monotonic inference relation between ฮ” and conditionals defeasible subsumption T(๐ถ๐‘– ) โŠ‘ ๐ถ๐‘— , expressing that input (๐ต|๐ด) in the following sense: vectors โƒ—๐‘ฅ that typically activate ๐‘๐‘– also activate ๐‘๐‘— . This no- tion of representing the structure of a neural network using ฮ” |โˆผ๐œ… (๐ต|๐ด) iff ๐œ…(๐ด๐ต) < ๐œ…(๐ด๐ต) or ๐œ…(๐ด) = โˆž. uncertain connections between atoms can be carried over to propositional conditional logic, utilizing atomic proposi- System Z A sophisticated ranking model of consistent tions ๐ด๐‘– to represent neurons and conditionals (๐ด๐‘– |๐ด๐‘— ) to belief bases is provided by System Z [4] which is based encode connections between them. Then, a (partial) possi- on the notion of tolerance. A conditional (๐ต|๐ด) is toler- ble world ๐œ” encodes a possible state of the neural network, ated by a belief base ฮ” if there is a possible world ๐œ” such with ๐œ” |= ๐ด๐‘– (๐œ” |= ๐ด๐‘– ) meaning that the neuron ๐‘๐‘– is ac- that ๐œ” |= ๐ด๐ต (โ€œthe conditional (๐ต|๐ด) is verified in ๐œ”โ€) tive (inactive) in the neural network. From another point of and ๐œ” |= ๐ดโ€ฒ ๐ต โ€ฒ โˆจ ๐ดโ€ฒ for all conditionals (๐ต โ€ฒ |๐ดโ€ฒ ) in ฮ” (โ€œthe view, ๐œ” can be seen as a representation of all input vectors โƒ—๐‘ฅ conditional (๐ต โ€ฒ |๐ดโ€ฒ ) is verified or not applicable in ๐œ”โ€). An that cause the same neurons to be (in)active. Together, the ordered partition (ฮ”0 , ฮ”1 , . . . , ฮ”๐‘š ) of ฮ” is called a toler- possible worlds in ฮฉ(ฮฃ) partition the set of input vectors ance partition of ฮ” if every conditional in ฮ”0 is tolerated based on their (abstracted) activation of neurons. by ฮ” and (ฮ”1 , . . . , ฮ”๐‘š ) is a tolerance partition of ฮ” โˆ– ฮ”0 . We formalize the extraction of propositional conditionals It is a well-known result that ฮ” is consistent iff ฮ” has a in analogy to the defeasible subsumptions in [15] now. For tolerance partition. If the partitioning sets are chosen in- this, and in the rest of this paper, we will use the same clusion maximally, beginning from ฮ”0 , then the resulting symbol ๐‘ to denote both a neuron in the neural network and tolerance partition ๐‘(ฮ”) = (ฮ”0 , ฮ”1 , . . . , ฮ”๐‘š ) is unique the atomic proposition representing the neuron. Moreover, and called Z-partition of ฮ”. Via the Z ranks ๐‘ฮ” (๐›ฟ) = ๐‘– of โ€ฒ conditionals ๐›ฟ โˆˆ ฮ” where ๐‘– is the index of the partitioning pa+ ๐‘ = {๐‘ โˆˆ pa๐‘ | ๐œˆ๐‘ โ€ฒ ,๐‘ > 0}, set from ๐‘(ฮ”) with ๐›ฟ โˆˆ ฮ”๐‘– , the Z-partition of ฮ” allows one paโˆ’ โ€ฒ ๐‘ = {๐‘ โˆˆ pa๐‘ | ๐œˆ๐‘ โ€ฒ ,๐‘ < 0}, to define the following System Z ranking model of consistent belief bases ฮ”: denote the sets of the parent nodes ๐‘ โ€ฒ of ๐‘ within a neu- {๏ธƒ ral network ๐’ฉ with positive and negative weights ๐œˆ๐‘ โ€ฒ ,๐‘ , 0 falฮ” (๐œ”) = โˆ… respectively. ๐œ…๐‘ฮ” (๐œ”) = , 1 + max๐›ฟโˆˆfalฮ” (๐œ”) ๐‘ฮ” (๐›ฟ) otherwise Definition 4 (Synaptic Conditionals). Let ๐’ฉ be a neural net- where ๐œ” โˆˆ ฮฉ(ฮฃ), and falฮ” (๐œ”) = {(๐ต|๐ด) โˆˆ ฮ”๐œ” |= ๐ด๐ต} work. Then we define for each neuron ๐‘ โˆˆ ๐’ฉ the backward is the set of conditionals falsified in ๐œ”. synaptic conditionals as follows: {๏ธ€ โ€ฒ โ€ฒ Example 2. A typical example to illustrate System Z is the ฮ”+โ† (๐‘ ) = (๐‘ |๐‘ ) | ๐‘ โˆˆ pa๐‘ , + }๏ธ€ Tweety example. Let ฮ” = {๐›ฟ1 , ๐›ฟ2 , ๐›ฟ3 } with ฮ”โˆ’ {๏ธ€ โ€ฒ โ€ฒ โˆ’ }๏ธ€ โ† (๐‘ ) = (๐‘ |๐‘ ) | ๐‘ โˆˆ pa๐‘ . ๐›ฟ1 = (๐‘|๐‘), ๐›ฟ2 = (๐‘“ |๐‘), ๐›ฟ3 = (๐‘“ |๐‘), Analogously, we define forward synaptic conditionals: state that penguins like Tweety are usually birds and birds ฮ”+ {๏ธ€ โ€ฒ โ€ฒ + }๏ธ€ โ†’ (๐‘ ) = (๐‘ |๐‘ ) | ๐‘ โˆˆ pa๐‘ , usually fly, but penguins usually do not fly. The System Z ฮ”โˆ’ โ€ฒ โ€ฒ โˆ’ }๏ธ€ {๏ธ€ tolerance partition of ฮ” is ๐‘(ฮ”) = (ฮ”0 , ฮ”1 ) with โ†’ (๐‘ ) = (๐‘ |๐‘ ) | ๐‘ โˆˆ pa๐‘ . ฮ”0 = {๐›ฟ2 }, ฮ”1 = {๐›ฟ1 , ๐›ฟ3 }. Note that backward synaptic conditionals are abductive 3 in nature. The idea of backward synaptic conditionals is that In order to shorten logical expressions, we use the abbreviations ๐ด๐ต 4 for conjunctions ๐ดโˆง๐ต and ๐ด for negations ยฌ๐ด where ๐ด, ๐ต โˆˆ โ„’(ฮฃ). Please see [16] for an introduction to Description Logics. if a neuron ๐‘ is active, the positive inputs of ๐‘ must have Example 3. We consider the multilayer perceptron โ„ณex log outweighed the negative inputs of ๐‘ (modulo the bias ๐›ฝ๐‘ ). from Example 1. The synaptic belief bases extracted from Therefore, it is plausible to assume that parents with positive โ„ณexlog are connections are generally active, while parents with nega- tive connections are generally inactive, even if exceptions ฮ”โ† โ„ณex log = {(๐‘0,0 |๐‘1,0 ), (๐‘0,1 |๐‘1,0 ), (๐‘0,2 |๐‘1,0 ), are possible (and likely). Forward synaptic conditionals, on (๐‘0,0 |๐‘1,1 ), (๐‘0,1 |๐‘1,1 ), (๐‘0,2 |๐‘1,1 ), the other hand, are predictive: Given that a neuron ๐‘ has an active parent with a positive connection (and without (๐‘0,0 |๐‘1,2 ), (๐‘0,1 |๐‘1,2 ), (๐‘0,2 |๐‘1,2 ), any additional information about the other parents), it is (๐‘1,0 |๐‘2,0 ), (๐‘1,1 |๐‘2,0 ), (๐‘1,2 |๐‘2,0 ), plausible to assume that this positive influence will cause ๐‘ to be active as well. (๐‘1,0 |๐‘2,1 ), (๐‘1,1 |๐‘2,1 ), (๐‘1,2 |๐‘2,1 ), We can now define belief bases containing synaptic con- (๐‘1,0 |๐‘2,2 ), (๐‘1,1 |๐‘2,2 ), (๐‘1,2 |๐‘2,2 )}, ditionals. and Definition 5 (Synaptic Belief Bases). Let ๐’ฉ be a neural network. We define the backward/forward synaptic belief ฮ”โ†’ โ„ณex log = {(๐‘1,0 |๐‘0,0 ), (๐‘1,1 |๐‘0,0 ), (๐‘1,2 |๐‘0,0 ), bases as the union of all synaptic conditionals that share the (๐‘1,0 |๐‘0,1 ), (๐‘1,1 |๐‘0,1 ), (๐‘1,2 |๐‘0,1 ), same direction, i.e., โ‹ƒ๏ธ (๏ธ€ + (๐‘1,0 |๐‘0,2 ), (๐‘1,1 |๐‘0,2 ), (๐‘1,2 |๐‘0,2 ), ฮ”โ† ฮ”โ† (๐‘ ) โˆช ฮ”โˆ’ )๏ธ€ ๐’ฉ = โ† (๐‘ ) , (๐‘2,0 |๐‘1,0 ), (๐‘2,1 |๐‘1,0 ), (๐‘2,2 |๐‘1,0 ), ๐‘ โˆˆ๐’ฉ โ‹ƒ๏ธ (๏ธ€ + (๐‘2,0 |๐‘1,1 ), (๐‘2,1 |๐‘1,1 ), (๐‘2,2 |๐‘1,1 ), ฮ”โ†’ ฮ”โ†’ (๐‘ ) โˆช ฮ”โˆ’ )๏ธ€ ๐’ฉ = โ†’ (๐‘ ) . ๐‘ โˆˆ๐’ฉ (๐‘2,0 |๐‘1,2 ), (๐‘2,1 |๐‘1,2 ), (๐‘2,2 |๐‘1,2 )}. The synaptic belief bases capture the information that In both cases (backward/forward), the Z-partition collapses: is immediately available from the structure of the neural network, namely the positive or negative influence neurons ๐‘(ฮ”โ† โ„ณex log ) = (ฮ”โ† โ„ณex log ), ๐‘(ฮ”โ†’ โ„ณex log ) = (ฮ”โ†’ โ„ณex log ), have on each other based on the trained synaptic weights. From a formal perspective, the direction of the conditionals and we have, with ๐œ“(๐‘2,2 ) = ๐‘0,0 โˆง ๐‘0,1 โˆง ๐‘0,2 , is arbitrary. As long as the two directions are not mixed, the ฮ” |ฬธ โˆผ๐œ…๐‘ (๐‘2,2 |๐œ“(๐‘2,2 )) synaptic belief base extracted from a multilayer perceptron ฮ” is consistent. regardless of whether ฮ” = ฮ”โ† โ†’ โ„ณex or ฮ” = ฮ”โ„ณex because log log Proposition 1. For every multilayer perceptron โ„ณ๐œ‘ , the synaptic belief bases ฮ”โ† โ†’ โ„ณ๐œ‘ and ฮ”โ„ณ๐œ‘ are consistent. ๐œ…๐‘ ๐‘ ฮ” (๐‘2,2 โˆง ๐œ“(๐‘2,2 )) = 1 ฬธ< 0 = ๐œ…ฮ” (๐‘2,2 โˆง ๐œ“(๐‘2,2 )) Proof. We prove the proposition for ฮ”โ† โ„ณ๐œ‘ by showing that for ฮ” = ฮ”โ† โ„ณex , and log the layers of the multilayer perceptron โ„ณ๐œ‘ induce a toler- ance partition of ฮ”โ† โ„ณ๐œ‘ . Let (๐‘š + 1) โˆˆ N be the number of ๐œ…๐‘ ๐‘ ฮ” (๐‘2,2 โˆง ๐œ“(๐‘2,2 )) = 1 ฬธ< 1 = ๐œ…ฮ” (๐‘2,2 โˆง ๐œ“(๐‘2,2 )) layers in โ„ณ๐œ‘ and let ๐’ฉ๐‘– be the set of neurons in the ๐‘–-th layer of โ„ณ๐œ‘ . Then, (ฮ”0 , . . . , ฮ”๐‘šโˆ’1 ) defined by for ฮ” = ฮ”โ†’ โ„ณex . Thus, In both cases this contradicts the log fact that the input vector โƒ—๐‘ฅ = (0.9, 0.8, 0.1) triggers the ฮ”๐‘˜ = {(๐‘ห™ โ€ฒ |๐‘ ) โˆˆ ฮ”โ† โ„ณ | ๐‘ โˆˆ ๐’ฉ๐‘˜+1 } neurons ๐‘0,0 , ๐‘0,1 , and ๐‘0,2 and is classified as an instance of ๐’ž๐‘2,2 by โ„ณex log (cf. Example 1). Hence, we come to different partitions ฮ”โ† โ„ณ๐œ‘ . Now, we show that every conditional conclusions if we either classify โƒ—๐‘ฅ = (0.9, 0.8, 0.1) by โ„ณexlog in ฮ”๐‘˜ is tolerated by ๐‘™ : ๐‘˜โ‰ค๐‘™<๐‘š ฮ”๐‘™ . Let ฮ”๐‘˜ and ๐‘ โˆˆ ๐’ฉ๐‘˜+1 โ‹ƒ๏ธ€ directly or classify โƒ—๐‘ฅ based on the synaptic belief bases. be arbitrary but fixed. We choose a possible world ๐œ” with the following properties: (1) ๐œ” |= ๐‘ , (2) ๐œ” |= ๐‘ โ€ฒ The example above shows that belief bases consisting if (๐‘ โ€ฒ |๐‘ ) โˆˆ ฮ”๐‘˜ for every ๐‘ โ€ฒ โˆˆ ๐’ฉ๐‘˜ , and (3) ๐œ” |= ๐‘ โ€ฒโ€ฒ for of synaptic conditionals (only) are too basic to give any every ๐‘ โ€ฒโ€ฒ โˆˆ ๐’ฉ๐‘ with ๐‘˜ < ๐‘ โ‰ค ๐‘š and ๐‘ ฬธ= ๐‘ โ€ฒโ€ฒ . It can be guarantees with respect to reasoning behavior when using quickly checked that all three properties concern different System Z. It is to be expected that a qualitative belief base neurons and, hence, can be satisfied by ๐œ” at the same time. cannot provide inferences on the same level of detail like The properties (1) and (2) together ensure that ๐œ” verifies all the original neural network. The example also shows that conditionals with antecedent ๐‘ ; property (3) ensures that ๐œ” the belief base introduces new inferences which cannot be is indifferent with respect to all other conditionals in all ฮ”๐‘™ obtained from the neural network. This can be considered with ๐‘˜ โ‰ค ๐‘™ < ๐‘š. Since ฮ”๐‘˜ and ๐‘ were chosen arbitrarily, undesirable. Therefore, in order to make better use of the this proves that every conditional in every ฮ”๐‘˜ is tolerated quantitative information learned by the neural network, we by all ฮ”๐‘™ (with 0 โ‰ค ๐‘˜ โ‰ค ๐‘™ < ๐‘š). make the extracted conditionals more complex to capture The proof for ฮ”โ†’ โ„ณ is analogous; only the order of the relevant influences among the neurons better in the next partition needs to be reversed. section. In contrast to [15], which makes use of fuzzy Description Logics, the synaptic belief bases are purely qualitative repre- 4. Sufficient (In)activators for Belief sentations of the connections in neural networks. Naturally, Base Extraction this means that all information about how strong individual connections between neurons are missing. The following Now, we propose a more sophisticated approach than synap- example shows that this can lead to different inferences. tic conditionals for extracting conditional belief bases from multilayer perceptrons. On the one hand, this means an ab- Proof. (โ‡) Assume that (2) and ๐‘ฆ๐‘ โ€ฒ โ‰ฅ 1 โˆ’ ๐œ for ๐‘ โ€ฒ โˆˆ ๐ด+ straction from specific input data to generalized defeasible and ๐‘ฆ๐‘ โ€ฒ โ‰ค ๐œ for ๐‘ โ€ฒ โˆˆ ๐ดโ€ฒ hold. Then, rules, here conditionals. On the other hand, the embedding โˆ‘๏ธ€ of the essential information flow of multilayer perceptrons ๐œ‘(๐›ฝ๐‘ + ๐‘ โ€ฒ โˆˆpa๐‘ ๐œˆ๐‘ โ€ฒ ,๐‘ ยท ๐‘ฆ๐‘ โ€ฒ ) โˆ‘๏ธ€ into a logical framework allows us to draw principled infer- = ๐œ‘(๐›ฝ๐‘ + ๐‘ โ€ฒ โˆˆpa+ โˆฉ๐ด+ ๐œˆ๐‘ โ€ฒ ,๐‘ ยท ๐‘ฆ๐‘ โ€ฒ ๐‘ ences of verifiable quality. โˆ‘๏ธ€ + ๐‘ โ€ฒ โˆˆpa+ โˆ–๐ด+ ๐œˆ๐‘ โ€ฒ ,๐‘ ยท ๐‘ฆ๐‘ โ€ฒ โˆ‘๏ธ€ ๐‘ + ๐‘ โ€ฒ โˆˆpaโˆ’ โˆฉ๐ดโˆ’ ๐œˆ๐‘ โ€ฒ ,๐‘ ยท ๐‘ฆ๐‘ โ€ฒ ๐‘ 4.1. Basic Idea and Preconditions โˆ‘๏ธ€ + ๐‘ โ€ฒ โˆˆpaโˆ’ โˆ–๐ดโˆ’ ๐œˆ๐‘ โ€ฒ ,๐‘ ยท ๐‘ฆ๐‘ โ€ฒ ) ๐‘โˆ‘๏ธ€ The basic idea of our method is to extract conditionals โ‰ฅ ๐œ‘(๐›ฝ๐‘ +(1 โˆ’ ๐œ ) ยท ๐‘ โ€ฒ โˆˆpa+ โˆฉ๐ด+ ๐œˆ๐‘ โ€ฒ ,๐‘ ๐‘ ๐œ,+ ๐œ,+ ) from a multilayer perceptron โ„ณlog โˆ‘๏ธ€ ๐›ฟ๐‘ = (๐‘ |๐œ“๐‘ +๐œ ยท ๐‘ โ€ฒ โˆˆpaโˆ’ โˆฉ๐ดโˆ’ ๐œˆ๐‘ โ€ฒ ,๐‘ ๐‘ where the consequence ๐‘ refers to a neuron from โ„ณlog โˆ‘๏ธ€ + ๐‘ โ€ฒ โˆˆpaโˆ’ โˆ–๐ดโˆ’ ๐œˆ๐‘ โ€ฒ ,๐‘ ) and the premise ๐œ“๐‘ ๐œ,+ to sets of parent nodes of ๐‘ which ๐‘ โ‰ฅ 1 โˆ’ ๐œ. are (in combination) โ€œmost relevantโ€ for the activation of ๐‘ . Relevance here means that the conditional (๐‘ |๐œ“๐‘ ๐œ,+ ) is ef- Hereby, we used ๐‘ โ€ฒ โˆˆpa+ โˆ–๐ด+ ๐œˆ๐‘ โ€ฒ ,๐‘ ยท ๐‘ฆ๐‘ โ€ฒ โ‰ฅ 0. Thus, โˆ‘๏ธ€ fective, i.e., ๐œ“๐‘ is true, only if it is guaranteed that the ๐œ,+ ๐‘ (๐ด+ , ๐ดโˆ’ ) is a sufficient activator of ๐‘ . neuron ๐‘ is sufficiently highly activated. Hence, it is reli- (โ‡’) We prove the contraposition. Assume that ably justified to infer ๐‘ . Analogously, we extract condition- als ๐›ฟ๐‘๐œ,โˆ’ = (๐‘ |๐œ“๐‘ ๐œ,โˆ’ ) wrt. the inactivation of ๐‘ . The โ€œmost โˆ‘๏ธ ๐œ‘(๐›ฝ๐‘ + (1 โˆ’ ๐œ ) ยท ๐œˆ๐‘ โ€ฒ ,๐‘ relevantโ€ parents nodes of neurons in โ„ณlog are identified ๐‘ โ€ฒ โˆˆpa+ โˆฉ๐ด+ based on the notion of sufficient (in)activators. ๐‘ We assume that the input of the multilayer percep- โˆ‘๏ธ โˆ‘๏ธ +๐œ ยท ๐œˆ๐‘ โ€ฒ ,๐‘ + ๐œˆ๐‘ โ€ฒ ,๐‘ ) < 1 โˆ’ ๐œ tron โ„ณlog is normalized to โƒ—๐‘ฅ โˆˆ [0, 1]๐‘› and that the activa- ๐‘ โ€ฒ โˆˆpaโˆ’ โˆฉ๐ดโˆ’ ๐‘ โ€ฒ โˆˆpaโˆ’ โˆ–๐ดโˆ’ ๐‘ ๐‘ tion function used in โ„ณlog is the logistic function which ensures that the output of all neurons in โ„ณlog is within the holds. We have to show that there is ๐‘ฆ๐‘ โ€ฒ โˆˆ [0, 1] for ๐‘ โ€ฒ โˆˆ range [0, 1] again. Given a tolerance factor ๐œ , this allows for pa๐‘ with ๐‘ฆ๐‘ โ€ฒ โ‰ฅ 1 โˆ’ ๐œ for ๐‘ โ€ฒ โˆˆ ๐ด+ and ๐‘ฆ๐‘ โ€ฒ โ‰ค ๐œ for an interpretation of the activation of all neurons in โ„ณlog ๐‘ โ€ฒ โˆˆ ๐ดโˆ’ such that as in Definition 2. โˆ‘๏ธ ๐œ‘(๐›ฝ๐‘ + ๐œˆ๐‘ โ€ฒ ,๐‘ ยท ๐‘ฆ๐‘ โ€ฒ ) < 1 โˆ’ ๐œ. ๐‘ โ€ฒ โˆˆpa๐‘ 4.2. Sufficient (In)activators With Based on the concept of active and inactive neurons, we de- โŽง fine (sets of) parent nodes of neurons in a multilayer percep- โŽช โŽช1โˆ’๐œ if ๐‘ โ€ฒ โˆˆ pa+ ๐‘ โˆฉ๐ด + tron โ„ณlog which are sufficient to activate resp. deactivate โŽช โŽจ0 if ๐‘ โ€ฒ โˆˆ pa+ ๐‘ โˆ–๐ด + โŽช โŽช โŽช the neurons, independent of the specific input vector โƒ—๐‘ฅ. ๐‘ฆ๐‘ โ€ฒ = ๐œ if ๐‘ โˆˆ pa๐‘ โˆฉ ๐ดโˆ’ โ€ฒ โˆ’ Definition 6 (Sufficient Activator). Let (โ„ณlog , ๐œ ) be a if ๐‘ โ€ฒ โˆˆ paโˆ’ โˆ’ โŽช 1 ๐‘ โˆ–๐ด โŽช โŽช โŽช โŽช classification scheme. Further, let ๐‘ be a neuron in โ„ณlog if ๐‘ โˆˆ pa๐‘ โˆ– (pa+ โ€ฒ โˆ’ โŽช ๐‘ โˆช pa๐‘ ) โŽฉ0 from a hidden layer or the output layer. We call a tuple (๐ด+ , ๐ดโˆ’ ) โŠ† pa2๐‘ with ๐ด+ โˆฉ ๐ดโˆ’ = โˆ… a sufficient acti- it follows that vator of ๐‘ wrt. ๐œ , if the activation of the neurons in ๐ด+ and โˆ‘๏ธ€ ๐œ‘(๐›ฝ๐‘ + ๐‘ โ€ฒ โˆˆpa๐‘ ๐œˆ๐‘ โ€ฒ ,๐‘ ยท ๐‘ฆ๐‘ โ€ฒ ) the inactivation of the neurons in ๐ดโˆ’ implies the activation โˆ‘๏ธ€ = ๐œ‘(๐›ฝ๐‘ + ๐‘ โ€ฒ โˆˆpa+ โˆฉ๐ด+ ๐œˆ๐‘ โ€ฒ ,๐‘ ยท ๐‘ฆ๐‘ โ€ฒ of ๐‘ ; formally, if ๐‘ฆ๐‘ โ€ฒ โ‰ฅ 1 โˆ’ ๐œ for ๐‘ โ€ฒ โˆˆ ๐ด+ and ๐‘ฆ๐‘ โ€ฒ โ‰ค ๐œ โˆ‘๏ธ€ ๐‘ for ๐‘ โ€ฒ โˆˆ ๐ดโˆ’ implies + ๐‘ โ€ฒ โˆˆpa+ โˆ–๐ด+ ๐œˆ๐‘ โ€ฒ ,๐‘ ยท ๐‘ฆ๐‘ โ€ฒ โˆ‘๏ธ€ ๐‘ + ๐‘ โ€ฒ โˆˆpaโˆ’ โˆฉ๐ดโˆ’ ๐œˆ๐‘ โ€ฒ ,๐‘ ยท ๐‘ฆ๐‘ โ€ฒ ๐‘ โˆ‘๏ธ ๐œ‘(๐›ฝ๐‘ + ๐œˆ๐‘ โ€ฒ ,๐‘ ยท ๐‘ฆ๐‘ โ€ฒ ) โ‰ฅ 1 โˆ’ ๐œ. โˆ‘๏ธ€ + ๐‘ โ€ฒ โˆˆpaโˆ’ โˆ–๐ดโˆ’ ๐œˆ๐‘ โ€ฒ ,๐‘ ยท ๐‘ฆ๐‘ โ€ฒ ) ๐‘โˆ‘๏ธ€ ๐‘ โ€ฒ โˆˆpa๐‘ = ๐œ‘(๐›ฝ๐‘ +(1 โˆ’ ๐œ ) ยท ๐‘ โ€ฒ โˆˆpa+ โˆฉ๐ด+ ๐œˆ๐‘ โ€ฒ ,๐‘ โˆ‘๏ธ€ ๐‘ We denote the set of the sufficient activators of ๐‘ wrt. ๐œ +๐œ ยท ๐‘ โ€ฒ โˆˆpaโˆ’ โˆฉ๐ดโˆ’ ๐œˆ๐‘ โ€ฒ ,๐‘ ๐‘ by ๐’ฎ๐’œ๐œ (๐‘ ). โˆ‘๏ธ€ + ๐‘ โ€ฒ โˆˆpaโˆ’ โˆ–๐ดโˆ’ ๐œˆ๐‘ โ€ฒ ,๐‘ ) ๐‘ The idea of the sufficient activators in ๐’ฎ๐’œ๐œ (๐‘ ) is that < 1 โˆ’ ๐œ, the output of the neurons ๐‘ โ€ฒ โˆˆ pa๐‘ with ๐‘ โ€ฒ โˆˆ / ๐ด+ โˆช๐ดโˆ’ is which finishes the proof. Note that the choice of ๐‘ฆ๐‘ โ€ฒ = 0 in irrelevant for the activation of ๐‘ , regardless of the concrete case of ๐‘ โ€ฒ โˆˆ pa๐‘ โˆ– (pa+๐‘ โˆช pa๐‘ ) is not mandatory because โˆ’ input of โ„ณlog , as captured in the next proposition. ๐œˆ๐‘ โ€ฒ ,๐‘ = 0 holds in this case anyway. Proposition 2. Let (โ„ณlog , ๐œ ) be a classification scheme, In this proof of Proposition 2 we have exploited that the and let ๐‘ be a neuron in โ„ณlog from a hidden layer or the logistic function is non-negative. If one wants to apply output layer. Then, (๐ด+ , ๐ดโˆ’ ) โŠ† pa2๐‘ with ๐ด+ โˆฉ ๐ดโˆ’ = โˆ… similar techniques to arbitrary sigmoid functions which are is a sufficient activator of ๐‘ iff not necessarily non-negative but bounded by (๐‘Ž, ๐‘) โŠ‚ โ„› one can rewrite ๐œ‘(๐›ฝ๐‘ + ๐‘ โ€ฒ โˆˆpa๐‘ ๐œˆ๐‘ โ€ฒ ,๐‘ ยท ๐‘ฆ๐‘ โ€ฒ ) beforehand โˆ‘๏ธ€ to โˆ‘๏ธ€ ๐œ‘(๐›ฝ๐‘ + (1 โˆ’ ๐œ ) ยท ๐‘ โ€ฒ โˆˆpa+ โˆฉ๐ด+ ๐œˆ๐‘ โ€ฒ ,๐‘ โˆ‘๏ธ ๐‘ โ€ฒ โ€ฒ ๐œ‘๐‘ ((๐‘ โˆ’ ๐‘Ž)(๐›ฝ๐‘ + ๐œˆ๐‘ โ€ฒ ,๐‘ ยท ๐‘ฆ๐‘ โ€ฒ )) (2) โˆ‘๏ธ€ + ๐œ ยท ๐‘ โ€ฒ โˆˆpaโˆ’ โˆฉ๐ดโˆ’ ๐œˆ๐‘ โ€ฒ ,๐‘ โˆ‘๏ธ€ ๐‘ ๐‘ โ€ฒ โˆˆpa๐‘ + ๐‘ โ€ฒ โˆˆpaโˆ’ โˆ–๐ดโˆ’ ๐œˆ๐‘ โ€ฒ ,๐‘ ) โ‰ฅ 1 โˆ’ ๐œ. ๐‘ with ๐›ฝ๐‘ โ€ฒ 1 ยท (๐›ฝ๐‘ + ๐‘Ž ยท ๐‘๐‘– โˆˆpa๐‘ ๐œˆ๐‘ โ€ฒ ,๐‘ ) and ๐‘ฆ๐‘ โ€ฒ โˆ‘๏ธ€ = ๐‘โˆ’๐‘Ž โ€ฒ = ๐‘ฆ๐‘ โ€ฒ โˆ’๐‘Ž ๐‘โˆ’๐‘Ž where ๐‘ฆ๐‘ โ€ฒ is bounded by (0, 1) for all ๐‘๐‘– โˆˆ pa๐‘ . โ€ฒ Note that in this case the thresholds for neurons being Example 5. Again, we consider the multilayer perceptron (in)active have to be adjusted from 1 โˆ’ ๐œ and ๐œ to ๐‘ โˆ’ ๐œ and โ„ณexlog from Example 1 (cf. Table 2) and the tolerance fac- ๐‘Ž + ๐œ as well, now with ๐œ โˆˆ [0, ๐‘โˆ’๐‘Ž2 ). tor ๐œ = 0.3. Then, ({๐‘0,0 , ๐‘0,2 }, {๐‘0,1 }) is a sufficient inactivator of ๐‘1,0 because Proposition 2 can be used to compute sufficient activators. For a neuron ๐‘ one generates each pair (๐ด+ , ๐ดโˆ’ ) with ๐œ‘(0.7 ยท (โˆ’1.27 โˆ’ 0.91) + 0.3 ยท 1.23) โ‰ˆ 0.239 โ‰ค 0.3, ๐‘ and ๐ด โˆˆ paโˆ’๐‘ and tests whether (2) holds or โˆ’ ๐ด+ โˆˆ pa+ not. where ๐œ‘ is the logistic function (cf. Table 1). Note that ({๐‘0,0 , ๐‘0,2 }, โˆ…) is not a sufficient inactivator of ๐‘1,0 be- Example 4. We consider the multilayer perceptron โ„ณex log cause from Example 1 (cf. Table 2) and the tolerance factor ๐œ = 0.3. Then, for instance, ({๐‘0,0 , ๐‘0,1 }, โˆ…) is a sufficient activator ๐œ‘(0.7 ยท (โˆ’1.27 โˆ’ 0.91) + 1.23) โ‰ˆ 0.427 > 0.3. of ๐‘1,1 because For tuples of sets (๐‘†1 , ๐‘†2 ) and (๐‘‡1 , ๐‘‡2 ) we write (๐‘†1 , ๐‘†2 ) โŠ‘ (๐‘‡1 , ๐‘‡2 ) iff ๐‘†1 โŠ† ๐‘‡1 and ๐‘†2 โŠ† ๐‘‡2 . Obvi- ๐œ‘(0.7 ยท (0.91 + 0.81) โˆ’ 0.09) โ‰ˆ 0.753 โ‰ฅ 0.7, ously, if (๐ด+ , ๐ดโˆ’ ) is a sufficient activator of ๐‘ and, for where ๐œ‘ is the logistic function (cf. Table 1). Note that (๐ดโ€ฒ+ , ๐ดโ€ฒโˆ’ ) โˆˆ pa(๐‘ )2 , (๐ด+ , ๐ดโˆ’ ) โŠ‘ (๐ดโ€ฒ+ , ๐ดโ€ฒโˆ’ ) holds, ({๐‘0,0 }, โˆ…) is not a sufficient activator of ๐‘1,1 , instead, be- then (๐ดโ€ฒ+ , ๐ดโ€ฒโˆ’ ) is a sufficient activator of ๐‘ , too. A similar cause result holds for sufficient inactivators. Proposition 4. Let (โ„ณlog , ๐œ ) be a classification scheme, ๐œ‘(0.7 ยท (0.91) โˆ’ 0.09) โ‰ˆ 0.633 < 0.7. and let ๐‘ be a neuron in โ„ณlog from a hidden layer or the Analogously to sufficient activators, we can define suffi- output layer. Then, cient inactivators. โ€ข if (๐ด+ , ๐ดโˆ’ ) is a sufficient activator of ๐‘ , then (๐ดโ€ฒ+ , ๐ดโ€ฒโˆ’ ) โˆˆ pa2๐‘ with (๐ด+ , ๐ดโˆ’ ) โŠ‘ (๐ดโ€ฒ+ , ๐ดโ€ฒโˆ’ ) Definition 7 (Sufficient Inactivator). Let (โ„ณlog , ๐œ ) be a is a sufficient activator of ๐‘ , too, classification scheme, and let ๐‘ be a neuron in โ„ณ from a hid- den layer or the output layer. We call a tuple (๐ผ + , ๐ผ โˆ’ ) โŠ† pa2๐‘ โ€ข if (๐ผ + , ๐ผ โˆ’ ) is a sufficient inactivator of ๐‘ , then with ๐ผ + โˆฉ ๐ผ โˆ’ = โˆ… a sufficient inactivator of ๐‘ wrt. ๐œ if, (๐ผ โ€ฒ+ , ๐ผ โ€ฒโˆ’ ) โˆˆ pa2๐‘ with (๐ผ + , ๐ผ โˆ’ ) โŠ‘ (๐ผ โ€ฒ+ , ๐ผ โ€ฒโˆ’ ) is the activation of the neurons in ๐ผ + and the inactivation of a sufficient inactivator of ๐‘ , too. the neurons in ๐ผ โˆ’ implies the inactivation of ๐‘ ; formally, if Proof. Let (๐ด+ , ๐ดโˆ’ ) be a sufficient activator of ๐‘ , and let ๐‘ฆ๐‘ โ€ฒ โ‰ฅ 1 โˆ’ ๐œ for ๐‘ โ€ฒ โˆˆ ๐ผ + and ๐‘ฆ๐‘ โ€ฒ โ‰ค ๐œ for ๐‘ โ€ฒ โˆˆ ๐ผ โˆ’ implies (๐ดโ€ฒ+ , ๐ดโ€ฒโˆ’ ) โˆˆ pa2๐‘ with (๐ด+ , ๐ดโˆ’ ) โŠ‘ (๐ดโ€ฒ+ , ๐ดโ€ฒโˆ’ ). Further, โˆ‘๏ธ let ๐‘ฆ๐‘ โ€ฒ โ‰ฅ 1 โˆ’ ๐œ for ๐‘ โ€ฒ โˆˆ ๐ดโ€ฒ+ and ๐‘ฆ๐‘ โ€ฒ โ‰ค ๐œ for ๐‘ โ€ฒ โˆˆ ๐ดโ€ฒโˆ’ . ๐œ‘(๐›ฝ๐‘ + ๐œˆ๐‘ โ€ฒ ,๐‘ ยท ๐‘ฆ๐‘ โ€ฒ ) โ‰ค ๐œ. From ๐ด+ โŠ† ๐ดโ€ฒ+ and ๐ดโˆ’ โŠ† ๐ดโ€ฒโˆ’ it follows that ๐‘ฆ๐‘ โ€ฒ โ‰ฅ 1โˆ’๐œ ๐‘ โ€ฒ โˆˆpa(๐‘ ) for ๐‘ โ€ฒ โˆˆ ๐ด+ and ๐‘ฆ๐‘ โ€ฒ โ‰ค ๐œ for ๐‘ โ€ฒ โˆˆ ๐ดโˆ’ holds as well. We denote the set of the sufficient inactivators of ๐‘ wrt. ๐œ Then, because (๐ด+ , ๐ดโˆ’ ) is a sufficient activator, by ๐’ฎโ„ ๐œ (๐‘ ). โˆ‘๏ธ ๐œ‘(๐›ฝ๐‘ + ๐œˆ๐‘ โ€ฒ ,๐‘ ยท ๐‘ฆ๐‘ โ€ฒ ) โ‰ฅ 1 โˆ’ ๐œ. Similar to sufficient activators, the idea of sufficient in- ๐‘ โ€ฒ โˆˆpa๐‘ activators (๐ผ + , ๐ผ โˆ’ ) of neurons ๐‘ is that the output of the The proof for sufficient inactivators is analogous. neurons ๐‘ โ€ฒ โˆˆ pa๐‘ with ๐‘ โ€ฒ โˆˆ / ๐ผ + โˆช ๐ผ โˆ’ is irrelevant for the inactivation of ๐‘ , regardless of the concrete input of โ„ณlog . Proposition 4 suggests to define minimal sufficient (in)activators. Proposition 3. Let (โ„ณlog , ๐œ ) be a classification scheme, and let ๐‘ be a neuron in โ„ณlog from a hidden layer or the Definition 8 (Minimal Sufficient (In)activators). Let output layer. Then, (๐ผ + , ๐ผ โˆ’ ) โŠ† pa2๐‘ with ๐ผ + โˆฉ ๐ผ โˆ’ = โˆ… is a (โ„ณlog , ๐œ ) be a classification scheme, and let ๐‘ be a neuron sufficient inactivator of ๐‘ iff in โ„ณlog from a hidden layer or the output layer. Then, โ€ข A sufficient activator (๐ด+ , ๐ดโˆ’ ) of ๐‘ is minimal if no โˆ‘๏ธ€ ๐œ‘(๐›ฝ๐‘ + ๐œ ยท ๐‘ โ€ฒ โˆˆpa+ โˆฉ๐ผ โˆ’ ๐œˆ๐‘ โ€ฒ ,๐‘ ๐‘ (๐ดโ€ฒ+ , ๐ดโ€ฒโˆ’ ) โˆˆ pa2๐‘ with (๐ดโ€ฒ+ , ๐ดโ€ฒโˆ’ ) โŠ‘ (๐ด+ , ๐ดโˆ’ ) (3) โˆ‘๏ธ€ + ๐‘ โ€ฒ โˆˆpa+ โˆ–๐ผ โˆ’ ๐œˆ๐‘ โ€ฒ ,๐‘ ๐‘โˆ‘๏ธ€ and (๐ดโ€ฒ+ , ๐ดโ€ฒโˆ’ ) ฬธ= (๐ด+ , ๐ดโˆ’ ) is a sufficient activator + (1 โˆ’ ๐œ ) ยท ๐‘ โ€ฒ โˆˆpaโˆ’ โˆฉ๐ผ + ๐œˆ๐‘ โ€ฒ ,๐‘ ) โ‰ค ๐œ. ๐‘ of ๐‘ , โ€ข A sufficient inactivator (๐ผ + , ๐ผ โˆ’ ) of ๐‘ is minimal if Proof. The proof is similar toโˆ‘๏ธ€the proof of Proposition 2. For no (๐ผ โ€ฒ+ , ๐ผ โ€ฒโˆ’ ) โˆˆ pa2๐‘ with (๐ผ + , ๐ผ โˆ’ ) โŠ‘ ๐ผ โ€ฒ+ , ๐ผ โ€ฒโˆ’ ) the direction (โ‡) note that ๐‘ โ€ฒ โˆˆpaโˆ’ โˆ–๐ผ + ๐œˆ๐‘ โ€ฒ ,๐‘ ยท ๐‘ฆ๐‘ โ€ฒ โ‰ค 0. ๐‘ and (๐ผ + , ๐ผ โˆ’ ) ฬธ= (๐ผ โ€ฒ+ , ๐ผ โ€ฒโˆ’ ) is a sufficient inactivator For the proof of the contraposition of (โ‡’), we select of ๐‘ . โŽง โŽช โŽช ๐œ if ๐‘ โ€ฒ โˆˆ pa+ ๐‘ โˆฉ๐ผ โˆ’ We denote the set of the minimal sufficient activators of ๐‘ wrt. ๐œ with ๐’ฎ๐’œ๐œmin (๐‘ ) and the set of the minimal sufficient โŽช โŽช1 if ๐‘ โˆˆ pa๐‘ โˆ– ๐ผ โ€ฒ + โˆ’ โŽช โŽช inactivators of ๐‘ wrt. ๐œ with ๐’ฎโ„ ๐œmin (๐‘ ). โŽจ ๐‘ฆ๐‘ โ€ฒ = 1 โˆ’ ๐œ if ๐‘ โ€ฒ โˆˆ paโˆ’ ๐‘ โˆฉ๐ผ + if ๐‘ โˆˆ pa๐‘ โˆ– ๐ผ โ€ฒ โˆ’ + We consider our running example. โŽช โŽช0 โŽช โŽช โŽช if ๐‘ โ€ฒ โˆˆ pa๐‘ โˆ– (pa+ โˆ’ โŽช ๐‘ โˆช pa๐‘ ) โŽฉ0 Example 6. The minimal sufficient (in)activators of the neu- rons in โ„ณexlog from Example 1 (cf. Table 2) with respect to Again, this proposition can be used to compute sufficient the tolerance factor ๐œ = 0.3 are shown in Table 3 resp. Ta- inactivators as the next example shows. ble 4. Minimal sufficient (in)activators allow for a graphi- cal representation (cf. Figure 4). For instance, the minimal ๐‘0,0 ๐‘1,0 ๐‘2,0 ๐‘0,1 ๐‘1,1 ๐‘2,1 ๐‘0,2 ๐‘1,2 ๐‘2,2 Figure 4: Minimal sufficient (in)activators of the neurons in โ„ณex log from Example 1. Solid lines indicate activation and dashed lines inactivation. ๐‘๐‘–,๐‘— ๐’ฎ๐’œ๐œmin (๐‘๐‘–,๐‘— ) every neuron ๐‘ in โ„ณlog its relationship to its sufficient ๐‘1,0 โˆ… (in)activators by a conditional which states that if the neu- ๐‘1,1 {({๐‘0,0 , ๐‘0,1 }, โˆ…)} rons in one of the sufficient activators (inactivators) of ๐‘ are ๐‘1,2 {({๐‘0,2 }, โˆ…)} (in)activated, then the neuron ๐‘ is usually active (inactive), ๐‘2,0 {({๐‘1,0 , ๐‘1,2 }, {๐‘1,1 })} too. ๐‘2,1 โˆ… Definition 9 (Belief Base ฮ”๐œโ„ณlog ). Let (โ„ณlog , ๐œ ) be a clas- ๐‘2,2 {({๐‘1,0 }, {๐‘1,2 }), ({๐‘1,1 }, โˆ…)} sification scheme, and let ๐‘ be a neuron from a hidden layer Table 3 or the output layer of โ„ณlog . Then, we define the conditionals ๐œ,+ ๐œ,+ ๐œ,โˆ’ ๐œ,โˆ’ Minimal sufficient activators of the neurons in the hidden resp. ๐›ฟ๐‘ = (๐‘ |๐œ“๐‘ ) and ๐›ฟ๐‘ = (๐‘ |๐œ“๐‘ ) via output layer of โ„ณex log from Example 1 wrt. ๐œ = 0.3. โŽ› โŽž โ‹๏ธ โ‹€๏ธ โ‹€๏ธ ๐œ“๐‘๐œ,+ = โŽ ๐‘โ€ฒ โˆง ๐‘ โ€ฒโŽ  , ๐‘๐‘–,๐‘— ๐’ฎโ„ ๐œmin (๐‘๐‘–,๐‘— ) (๐ด+ ,๐ดโˆ’ )โˆˆ๐’ฎ๐’œ๐œ min (๐‘ ) ๐‘ โ€ฒ โˆˆ๐ด+ ๐‘ โ€ฒ โˆˆ๐ดโˆ’ โŽ› โŽž ๐‘1,0 {({๐‘0,0 , ๐‘0,2 }, {๐‘0,1 })} โ‹๏ธ โ‹€๏ธ โ‹€๏ธ ๐œ,โˆ’ โ€ฒ ๐‘1,1 โˆ… ๐œ“๐‘ = โŽ ๐‘ โˆง ๐‘ โ€ฒโŽ  , ๐‘1,2 โˆ… (๐ผ + ,๐ผ โˆ’ )โˆˆ๐’ฎโ„ ๐œ ๐‘ โ€ฒ โˆˆ๐ผ + ๐‘ โ€ฒ โˆˆ๐ผ โˆ’ min (๐‘ ) ๐‘2,0 โˆ… ๐‘2,1 {({๐‘1,0 , ๐‘1,2 }, {๐‘1,1 })} provided that ๐‘2,2 โˆ… ๐œ,+ ๐’ฎ๐’œ๐œmin (๐‘ ) ฬธ= โˆ… in case of ๐›ฟ๐‘ , ๐œ ๐œ,โˆ’ (*) Table 4 ๐’ฎโ„ min (๐‘ ) ฬธ= โˆ… in case of ๐›ฟ๐‘ . Minimal sufficient inactivators of the neurons in the hidden resp. output layer of โ„ณex Note that the conditionals depend on the tolerance factor ๐œ log from Example 1 wrt. ๐œ = 0.3. because the sets of (minimal) sufficient (in)activators depend on ๐œ . However, the conditionals are not dependent on any input vector of โ„ณlog , since ๐œ abstracts from that. Based on that, we sufficient inactivator ({๐‘0,0 , ๐‘0,2 }, {๐‘0,1 }) of ๐‘1,0 can be define the extraction of the belief base ฮ”๐œโ„ณlog from โ„ณlog via visualized as three outgoing edges from ๐‘0,0 , ๐‘0,1 , and ๐‘0,2 , respectively, which conjointly result in ๐‘1,0 . The dashed line ฮ”๐œโ„ณlog = {๐›ฟ๐‘ ๐œ,+ | ๐‘ โˆˆ ๐’ฉ + } โˆช {๐›ฟ๐‘ ๐œ,โˆ’ | ๐‘ โˆˆ ๐’ฉ โˆ’ }, in Figure 4 after these three edges have met indicates that ({๐‘0,0 , ๐‘0,2 }, {๐‘0,1 }) is a sufficient inactivator (and not an where ๐’ฉ ๐œ,+ is the set of neurons ๐‘ for which the condi- ๐œ,+ activator) of ๐‘1,0 and the dashed line from ๐‘0,1 indicates tional ๐›ฟ๐‘ exists, and where ๐’ฉ ๐œ,โˆ’ is the set of neurons ๐‘ ๐œ,โˆ’ that ๐‘0,1 has a negative influence on the inactivation of ๐‘1,0 for which the conditional ๐›ฟ๐‘ exists, i.e., (*) applies. (because the weight ๐œˆ0,1,0 is positive). The number of conditionals in ฮ”๐œโ„ณlog is bounded by Altogether, (minimal) sufficient activators and inactiva- the number of neurons in โ„ณlog (minus the input layer) tors make it possible to abstract from the concrete input data which means a higher degree of abstraction than prevalent of a multilayer perceptron โ„ณlog and reveal the essential in synaptic belief bases (cf. Definition 5) the cardinality of streams of information within โ„ณlog . This is the motivation which is bounded by the number of edges in โ„ณlog . Fur- for our following extraction of conditional belief bases from thermore, the condition (*) in Definition 9 ensures that the multilayer perceptrons. conditionals ๐›ฟ๐‘๐œ,+ (resp. ๐›ฟ๐‘๐œ,โˆ’ ) are added to ฮ”๐œโ„ณlog only if ๐‘ has sufficient activators (inactivators). This prevents from conditionals of the form (๐‘ |โŠฅ) and (๐‘ |โŠฅ) in ฮ”๐œโ„ณlog 4.3. Belief Base Extraction which would cause inconsistencies according to our accep- Now, we describe our approach on extracting a conditional tance definition of conditionals. If there is a neuron ๐‘ with belief base ฮ”๐œโ„ณlog from a multilayer perceptron โ„ณlog based ๐›ฟ๐‘๐œ,+ ๐œ,โˆ’ , ๐›ฟ๐‘ / ฮ”๐œโ„ณlog , then one can increase ๐œ in order to โˆˆ on sufficient (in)activators. In ฮ”๐œโ„ณlog we formalize for improve the chance of obtaining such a conditional. Example 7. We consider โ„ณex log from Example 1 and the for ๐‘— = 1, . . . , ๐‘š is a partition of ฮ”๐œโ„ณlog (modulo empty tolerance factor ๐œ = 0.3. The minimal sufficient (in)activators sets). Let ๐›ฟ โˆˆ ฮ”๐‘— , providedโ‹ƒ๏ธ€hat ฮ”๐‘— ฬธ= โˆ…. We have to of the neurons in โ„ณex log are shown in Table 3 resp. Table 4 from show that ๐›ฟ is tolerated by ๐‘š ๐‘˜=๐‘— ฮ”๐‘˜ . For this, let ๐›ฟ be which we can derive the belief base ฮ”0.3 โ„ณlog . The conditionals of the form ๐›ฟ๐‘ for some ๐‘ โˆˆ ๐’ฉ๐‘— . The proof for ๐›ฟ of ๐œ,+ in ฮ”0.3 โ„ณlog are the form ๐›ฟ๐‘ ๐œ,โˆ’ is analogous. By construction of ๐›ฟ๐‘ ๐œ,+ , there is (๐ด , ๐ด ) โˆˆ ๐’ฎ๐’œmin (๐‘โ‹€๏ธ€ + โˆ’ ๐œ ) and a (partial) possible world 0.3,โˆ’ ๐›ฟ๐‘ = (๐‘1,0 |๐‘0,0 โˆง ๐‘0,2 โˆง ๐‘0,1 ), ๐œ” โˆˆ ฮฉ(๐’ฉ๐‘—โˆ’1 ) with ๐œ” |= ๐‘ โ€ฒ โˆˆ๐ด+ ๐‘ โ€ฒ โˆง ๐‘ โ€ฒ โˆˆ๐ดโˆ’ ๐‘ โ€ฒ (๐ด+ โ‹€๏ธ€ 1,0 0.3,+ ๐›ฟ๐‘ = (๐‘1,1 |๐‘0,0 โˆง ๐‘0,1 ), and ๐ดโˆ’ are disjoint). 1,1 Thanks to Lemma 1, we can extend ๐œ” to a (partial) possible 0.3,+ ๐›ฟ๐‘ 1,2 = (๐‘1,2 |๐‘0,2 ), world ๐œ” โ€ฒ โˆˆ ฮฉ(๐’ฉ๐‘—โˆ’1 โˆช ๐’ฉ๐‘— ) such that all conditionals in ฮ”๐‘— 0.3,+ are either not applicable or verified by concatenating ๐‘ โ€ฒ ๐›ฟ๐‘ = (๐‘2,0 |๐‘1,0 โˆง ๐‘1,2 โˆง ๐‘1,1 ), 2,0 to ๐œ” in case of ๐œ” |= ๐œ“๐‘ โ€ฒ or concatenating ๐‘ to ๐œ” in case ๐œ,+ โ€ฒ 0.3,โˆ’ ๐›ฟ๐‘ 2,1 = (๐‘2,1 |๐‘1,0 โˆง ๐‘1,2 โˆง ๐‘1,1 ), of ๐œ” |= ๐œ“๐‘ โ€ฒ for ๐‘ โˆˆ ๐’ฉ๐‘— . In particular, ๐œ” โ€ฒ verifies ๐›ฟ๐‘ ๐œ,โˆ’ โ€ฒ ๐œ,+ . 0.3,+ By a repeated application of this argument, we can construct ๐›ฟ๐‘ = (๐‘2,2 |๐‘1,0 โˆง ๐‘1,2 โˆจ ๐‘1,1 ). a (partial) possible world ๐œ” โ€ฒโ€ฒ โˆˆ ฮฉ( ๐‘š ๐‘˜=๐‘—โˆ’1 ๐’ฉ๐‘˜ ) which veri- 2,2 โ‹ƒ๏ธ€ fies ๐›ฟ๐‘ ๐œ,+ and falsifies no conditional from ๐‘š ๐‘˜=๐‘— ฮ”๐‘˜ . Even- โ‹ƒ๏ธ€ 0.3,+ In particular, note the disjunction in the premise of ๐›ฟ๐‘ 2,2 because of the two (different) minimal sufficient activators tually, this (partial) โ‹ƒ๏ธ€possible world can be extended to a of ๐‘2,2 . possible world in ฮฉ( ๐‘š ๐‘˜=0 ๐’ฉ๐‘˜ ) by the concatenation of the remaining ground atoms, either positive or negated which The belief base ฮ”๐œโ„ณlog is consistent. To show this, we can be chosen freely. make use of the following lemma. Note that the belief base ฮ”๐œโ„ณlog might be empty, namely Lemma 1. Let (โ„ณlog , ๐œ ) be a classification scheme. Then, if for all neurons in โ„ณlog there is no sufficient (in)activator. for every neuron ๐‘ from a hidden layer or the output layer On the contrary, if a neuron ๐‘ can be (in)activated, then of โ„ณlog it holds that (cf. Definition 9) there is a sufficient (in)activator of ๐‘ so that there is a ๐œ,+ ๐œ,โˆ’ conditional wrt. ๐‘ in ฮ”๐œโ„ณlog . Thus, ฮ”๐œโ„ณlog reflects the ๐œ“๐‘ โˆง ๐œ“๐‘ โ‰ก โŠฅ. most important information flow in โ„ณlog . Proof. Assume that ๐œ“๐‘ ๐œ,+ โˆง ๐œ“๐‘ ๐œ,โˆ’ ฬธโ‰ก โŠฅ holds. Then, there is a possible world ๐œ”, a sufficient activator (๐ด+ , ๐ดโˆ’ ) of ๐‘ 5. Binary Classification with ฮ”๐œโ„ณlog wrt. ๐œ , and a sufficient inactivator (๐ผ + , ๐ผ โˆ’ ) of ๐‘ wrt. ๐œ such that Now, we discuss how to perform binary (multi-class) clas- ๐œ” |= โ‹€๏ธ ๐‘โ€ฒ โˆง โ‹€๏ธ ๐‘โ€ฒ โˆง โ‹€๏ธ ๐‘โ€ฒ โˆง โ‹€๏ธ ๐‘ โ€ฒ. sification based on the belief base ฮ”๐œโ„ณlog which we have extracted from a multilayer perceptron โ„ณlog (cf. Defini- ๐‘ โ€ฒ โˆˆ๐ด+ ๐‘ โ€ฒ โˆˆ๐ดโˆ’ ๐‘ โ€ฒ โˆˆ๐ผ + ๐‘ โ€ฒ โˆˆ๐ผ โˆ’ tion 9). Recall that, following Definition 2, we can say that It follows that (๐ด+ โˆช ๐ผ + ) โˆฉ (๐ดโˆ’ โˆช ๐ผ โˆ’ ) = โˆ…. Otherwise, ๐œ” an input vector โƒ—๐‘ฅ of โ„ณlog is classified (resp. declassified) would mention an atom both negated and positive. From as ๐’ž๐‘ represented by the neuron ๐‘ from the output layer this and Proposition 4 it follows that (๐ด+ โˆช ๐ผ + , ๐ดโˆ’ โˆช ๐ผ โˆ’ ) of โ„ณlog if โ„ณlog (๐‘ฅ โƒ— ) โ‰ฅ 1 โˆ’ ๐œ (resp. โ„ณlog (๐‘ฅโƒ— ) โ‰ค ๐œ ) where ๐œ is both a sufficient activator and a sufficient inactivator is a tolerance factor. We denote this with of ๐‘ wrt. ๐œ because (๐ด+ , ๐ดโˆ’ ) โŠ‘ (๐ด+ โˆช ๐ผ + , ๐ดโˆ’ โˆช ๐ผ โˆ’ ) and (๐ผ + , ๐ผ โˆ’ ) โŠ‘ (๐ด+ โˆช ๐ผ + , ๐ดโˆ’ โˆช ๐ผ โˆ’ ) hold. According to โ„ณlog , โƒ—๐‘ฅ |โˆผ๐œ ๐‘ iff โ„ณlog (๐‘ฅ โƒ—) โ‰ฅ 1 โˆ’ ๐œ the definitions of sufficient (in)activators, for appropriate โ„ณlog , โƒ—๐‘ฅ |โˆผ๐œ ๐‘ iff โ„ณlog (๐‘ฅ โƒ— ) โ‰ค ๐œ. values ๐‘ฆ๐‘ โ€ฒ for ๐‘ โ€ฒ โˆˆ pa(๐‘ ), We lift this idea of classifying โƒ—๐‘ฅ from โ„ณlog to the belief base ฮ”๐œโ„ณlog . Thereby, we make use of the System Z ranking โˆ‘๏ธ 1 โˆ’ ๐œ โ‰ค ๐œ‘(๐›ฝ๐‘ + ๐œˆ๐‘ โ€ฒ ,๐‘ ยท ๐‘ฆ๐‘ โ€ฒ ) โ‰ค ๐œ ๐‘ โ€ฒ โˆˆpa๐‘ model ๐œ…๐‘ ฮ”๐œ โ„ณ of ฮ”๐œโ„ณlog . log follows. This implies 1 โˆ’ ๐œ โ‰ค ๐œ or, equivalent 0.5 โ‰ค ๐œ , Definition 10 (Z-Classification). Let (โ„ณlog , ๐œ ) be a clas- which contradicts ๐œ โˆˆ [0, 0.5). sification scheme, let ฮ”๐œโ„ณlog be the belief base extracted Lemma 1 states that there is no neuron ๐‘ in โ„ณlog for from โ„ณlog , and let ๐œ…๐‘ ๐‘ โ„ณlog ,๐œ = ๐œ…ฮ”๐œ โ„ณ be its System Z log which both ๐›ฟ๐‘๐œ,+ (supporting ๐‘ ) and ๐›ฟ๐‘ ๐œ,โˆ’ (supporting ๐‘ ) ranking model. With ๐ดโƒ—๐œ๐‘ฅ we denote the set of neurons from can be applicable at the same time. the input layer of โ„ณlog which are activated by โƒ—๐‘ฅ wrt. ๐œ , and Proposition 5. Let (โ„ณlog , ๐œ ) be a classification scheme. with ๐ผโƒ—๐‘ฅ๐œ the set of neurons which are inactivated. Then, we Then, the belief base ฮ”๐œโ„ณlog extracted from โ„ณlog is consis- say that an input vector โƒ—๐‘ฅ of โ„ณlog is tent. โ€ข Z-classified as ๐’ž๐‘ wrt. a neuron ๐‘ from the output layer of โ„ณlog , denoted by Proof. We show that ฮ”๐œโ„ณlog has a tolerance partition from which its consistency follows. Let ๐‘š + 1 be the number of ฮ”๐œโ„ณlog , โƒ—๐‘ฅ |โˆผ๐‘ ๐‘ ๐œ ๐‘, iff ๐œ…โ„ณlog ,๐œ accepts layers in โ„ณlog and, for ๐‘— = 0, 1, . . . , ๐‘š, let ๐’ฉ๐‘— be the set of neurons in the ๐‘—-th layer. Then, (ฮ”1 , . . . , ฮ”๐‘š ) with โ‹€๏ธ โ‹€๏ธ (๐‘ | ๐‘โ€ฒ โˆง ๐‘ โ€ฒ ), ๐‘ โ€ฒ โˆˆ๐’œ๐œ โƒ— ๐‘ฅ ๐‘ โ€ฒ โˆˆโ„๐‘ฅ ๐œ โƒ— ๐œ,+ ฮ”๐‘— = {๐›ฟ๐‘ โˆˆ ฮ”๐œโ„ณlog | ๐‘ โˆˆ ๐’ฉ๐‘— } ๐œ,โˆ’ โ€ข Z-declassified as ๐’ž๐‘ , denoted by โˆช {๐›ฟ๐‘ โˆˆ ฮ”๐œโ„ณlog | ๐‘ โˆˆ ๐’ฉ๐‘— } ฮ”๐œโ„ณlog , โƒ—๐‘ฅ |โˆผ๐‘ ๐‘ ๐œ ๐‘ , iff ๐œ…โ„ณlog ,๐œ accepts Further, the Z-partition of ฮ”0.3 0.3 0.3 โ„ณlog is ๐‘(ฮ”โ„ณex ) = (ฮ”โ„ณex ), log log so that, for (๐‘2,2 |๐œ’๐‘2,2 ) with ๐œ’๐‘2,2 = ๐‘0,0 โˆง ๐‘0,1 โˆง ๐‘0,2 , โ‹€๏ธ โ‹€๏ธ (๐‘ | ๐‘โ€ฒ โˆง ๐‘ โ€ฒ ). ๐‘ โ€ฒ โˆˆ๐’œ๐œ โƒ— ๐‘ฅ ๐‘ โ€ฒ โˆˆโ„๐‘ฅ ๐œ โƒ— we have, with ฮ” = ฮ”0.3 โ„ณex , log We obtain the following central result stating ๐œ…๐‘ ๐‘ ฮ” (๐‘2,2 โˆง ๐œ’๐‘2,2 ) = 0 < 1 = ๐œ…ฮ” (๐‘2,2 โˆง ๐œ’๐‘2,2 ) that ๐œ…๐‘โ„ณlog ,๐œ does not โ€œinventโ€ inferences but yields inferences that can be drawn from โ„ณlog only. Instead, Thus, we classify โƒ—๐‘ฅ as an instance of ๐’ž๐‘2,2 in accordance with inferences drawn from ๐œ…๐‘ โ„ณlog ,๐œ can be understood, in some the result from Example 1. sense, as the most reliable inferences from โ„ณlog . Our approach focuses attention on the main dependencies Proposition 6. Let (โ„ณlog , ๐œ ) be a classification scheme, among the neurons in multilayer perceptrons. In contrast let ฮ”๐œโ„ณlog be the belief base extracted from โ„ณlog , let ๐œ…๐‘ โ„ณlog ,๐œ to the synaptic conditionals in Section 3, the influence of be its System Z ranking model, and let โƒ—๐‘ฅ be an input vector several parent nodes on a neuron ๐‘ is aggregated, with of โ„ณlog . Then, the guarantee that the aggregated parent nodes are able to (in)active ๐‘ . A depiction of these aggregated influences is ฮ”๐œโ„ณlog , โƒ—๐‘ฅ |โˆผ๐‘ ๐œ ๐‘ implies โ„ณlog , โƒ— ๐‘ฅ |โˆผ๐œ ๐‘, shown in Figure 4 for our running example. Figure 4 can be understood as a visualization of the main information flow and, analogously, in โ„ณexlog . ฮ”๐œโ„ณlog , โƒ—๐‘ฅ |โˆผ๐‘ ๐œ ๐‘ implies โ„ณlog , โƒ— ๐‘ฅ |โˆผ๐œ ๐‘ . Proof. Let ๐’œโƒ—๐œ๐‘ฅ and โ„โƒ—๐‘ฅ๐œ be the sets of the neurons from the 6. Conclusions input layer of โ„ณlog which are activated resp. inactivated We proposed an approach on extracting propositional con- by the input โƒ—๐‘ฅ wrt. ๐œ (cf. Definition 10). Further, let ๐‘š + 1 ditional belief bases from multilayer perceptrons (MLPs) for be the number of layers in โ„ณlog , and, for ๐‘— = 0, 1, . . . , ๐‘š, binary multi-class classification. The conditionals relate to let ๐’ฉ๐‘— be the set of neurons in the ๐‘—-th layer of โ„ณlog . We the main information flow in the multilayer perceptron de- prove that ฮ”๐œโ„ณlog , โƒ—๐‘ฅ |โˆผ๐‘๐œ ๐‘ implies โ„ณlog , โƒ— ๐‘ฅ |โˆผ๐œ ๐‘ . The tached from specific input vectors. Therewith, our approach proof that ฮ”๐œโ„ณlog , โƒ—๐‘ฅ |โˆผ๐‘ ๐œ ๐‘ implies โ„ณlog , โƒ— ๐‘ฅ |โˆผ๐œ ๐‘ is anal- abstracts from both the input data as well as overlay effects ogous. in the network and rebuilds the backbone of the network Let ฮ”๐œโ„ณlog , โƒ—๐‘ฅ |โˆผ๐‘ ๐œ ๐‘ , i.e., by definition, ๐œ…โ„ณlog ,๐œ accepts ๐‘ within a prevalent KRR formalism. The main idea of our ap- the conditional (๐‘ |๐œ’๐‘ ) with proach is to exploit sufficient (in)activators of neurons ๐‘ the (in)activation of which guarantees that ๐‘ is (in)activated as well. The extracted conditional belief base allows for โ‹€๏ธ โ‹€๏ธ ๐œ’๐‘ = ๐‘โ€ฒ โˆง ๐‘ โ€ฒ. ๐œ ๐‘ โ€ฒ โˆˆ๐’œโƒ— ๐‘ฅ ๐œ ๐‘ โ€ฒ โˆˆโ„โƒ— ๐‘ฅ drawing inferences in a principled way, for instance, under System Z. It is guaranteed that the belief base is consistent Following the construction of possible worlds in the proof and does not invent inferences that cannot be drawn from of Proposition 5, every (partial) possible world ๐œ” โˆˆ ฮฉ(๐’ฉ0 ) the multilayer perceptron. with ๐œ” โ‹ƒ๏ธ€|= ๐œ’๐‘ can be extended to a possible world In recent work [17] it has been shown that there is a tight ๐œ” โ€ฒ โˆˆ ฮฉ( ๐‘š ๐‘—=0 ๐’ฉ๐‘— ) such that no conditional from ฮ”โ„ณlog connection between multilayer perceptrons and quantitative ๐œ is falsified. Hence, ๐œ…โ„ณlog ,๐œ (๐œ” ) = 0. Because ๐œ…โ„ณlog ,๐œ ac- ๐‘ โ€ฒ ๐‘ bipolar argumentation frameworks. Roughly speaking, MLPs cepts the conditional (๐‘ |๐œ’๐‘ ), none of these extensions ๐œ” โ€ฒ can be seen as specific argumentation frameworks under a satisfies ๐‘ . Otherwise, ๐œ…๐‘ so-called MLP-semantics. To make this connection useful โ„ณlog ,๐œ (๐‘ โˆง ๐œ’๐‘ ) = 0 would hold for explanations, some ideas on sparsification have been which contradicts the acceptance of (๐‘ |๐œ’๐‘ ). As a con- considered [18]. In future work, we want to investigate sequence, the conditional ๐›ฟ๐‘ ๐œ,+ (cf. Definition 9) must be the connections between our approach and the approaches in ฮ”๐œโ„ณlog which is the only possibility to exclude ๐‘ from from [17, 18]. Exploiting sparsified networks may simplify the extensions ๐œ” โ€ฒ (and which is also accepted in all the ex- the computation of conditional belief bases. The other way tensions ๐œ” โ€ฒ ). Otherwise, there is no reason why not to have round, the qualitative conditionals could perhaps be used to an extension ๐œ” โ€ฒ with ๐œ” โ€ฒ |= ๐‘ . construct argumentation frameworks in order to simulate In more detail, either there is an extension ๐œ” โ€ฒ of ๐œ” with the MLPs that are easier to interpret than the argumentation ๐œ” |= ๐‘ and ๐œ…๐‘ โ€ฒ โ„ณlog ,๐œ (๐œ” ) = 0 which contradicts the accep- โ€ฒ frameworks obtained from the current approaches. tance of (๐‘ |๐œ’๐‘ ), or ๐œ…โ„ณlog ,๐œ (๐œ” โ€ฒ ) > 0 for all such exten- ๐‘ Also in future work, we want to extract conditionals sion ๐œ” โ€ฒ which requires a conditional in ฮ”๐œโ„ณlog that is falsi- from multilayer perceptrons that are based on โ€œnecessary fied in ๐œ” โ€ฒ . The only candidate for such a conditional would (in)activatorsโ€ and can be used for explaining classifications be ๐›ฟ๐‘ ๐œ,+ . As a consequence of the acceptance of ๐›ฟ๐‘ ๐œ,+ , the that are made by the multilayer perceptrons. Therewith, input vector โƒ—๐‘ฅ activates at least one sufficient activator of ๐‘ . we expect to be able to bound all possible classifications From this, it follows that โƒ—๐‘ฅ also activates ๐‘ in โ„ณlog . from two directions (upper and lower bound) which, as we hope, can help to better understand the essence of binary We recall our running example to illustrate this proposi- multi-class classification based on multilayer perceptrons. tion. Further research directions could be to investigate how the choice of the tolerance factor influences the shape of the Example 8. We consider the same scenario as in Exam- conditional belief base and how different inference opera- ple 1, i.e., the multilayer perceptron โ„ณex log , the tolerance factor tors, e.g., based on System P [8], lexicographic closure [19], ๐œ = 0.3, and the input vector โƒ—๐‘ฅ = (0.9, 0.8, 0.1). Then, or c-representations [9], relate to the binary multi-class ๐’œโƒ—0.3 โ„โƒ—๐‘ฅ0.3 = {๐‘0,2 }. classification with multilayer perceptrons. ๐‘ฅ = {๐‘0,0 , ๐‘0,1 }, Acknowledgments telligence, EAAI 2021, Virtual Event, February 2-9, 2021, AAAI Press, 2021, pp. 6463โ€“6470. This work was supported by DFG Grant KE 1413/14-1 of the [18] H. Ayoobi, N. Potyka, F. Toni, Sparx: Sparse argumen- German Research Foundation (DFG) awarded to Gabriele tative explanations for neural networks, in: K. Gal, Kern-Isberner. A. Nowรฉ, G. J. Nalepa, R. Fairstein, R. Radulescu (Eds.), ECAI 2023 - 26th European Conference on Artificial Intelligence, September 30 - October 4, 2023, Krakรณw, References Poland - Including 12th Conference on Prestigious Ap- [1] K. Gurney, An Introduction to Neural Networks, UCL plications of Intelligent Systems (PAIS 2023), volume Press, 1997. 372 of Frontiers in Artificial Intelligence and Applica- [2] S. Yang, C. Zhang, W. Wu, Binary output layer of tions, IOS Press, 2023, pp. 149โ€“156. feedforward neural networks for solving multi-class [19] D. Lehmann, Another perspective on default reason- classification problems, IEEE Access 7 (2019) 5085โ€“ ing, Ann. Math. Artif. Intell. 15 (1995) 61โ€“82. 5094. [3] A. Rajendra, P. Sajja, Knowledge-Based Systems, Jones & Bartlett Learning, 2009. [4] J. Pearl, System Z: A natural ordering of defaults with tractable applications to nonmonotonic reasoning, in: R. Parikh (Ed.), Proceedings of the 3rd Conference on Theoretical Aspects of Reasoning about Knowledge, Pacific Grove, CA, USA, March 1990, Morgan Kauf- mann, 1990, pp. 121โ€“135. [5] B. d. Finetti, La logique de la probabilitรฉ, The Journal of Symbolic Logic 2 (1937) 31โ€“39. [6] E. W. Adams, The Logic of Conditionals, Springer, 1975. [7] W. Spohn, The Laws of Belief - Ranking Theory and Its Philosophical Applications, Oxford UP, 2014. [8] S. Kraus, D. Lehmann, M. Magidor, Nonmonotonic reasoning, preferential models and cumulative logics, Artif. Intell. 44 (1990) 167โ€“207. [9] G. Kern-Isberner, A thorough axiomatization of a principle of conditional preservation in belief revision, Ann. Math. Artif. Intell. 40 (2004) 127โ€“164. [10] A. Ghorbani, J. Y. Zou, Neuron shapley: Discovering the responsible neurons, in: H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, H. Lin (Eds.), Advances in Neural Information Processing Systems 33: Annual Confer- ence on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. [11] W. S. McCulloch, W. H. Pitts, A logical calculus of the ideas immanent in nervous activity, The bulletin of mathematical biophysics 5 (1943) 115โ€“133. [12] G. Cybenko, Approximation by superpositions of a sigmoidal function, Math. Control. Signals Syst. 2 (1989) 303โ€“314. [13] D. Nute, Topics in Conditional Logic, Springer, 2011. [14] M. Goldszmidt, J. Pearl, On the Relation Between Ra- tional Closure and System Z, CSD (Series), UCLA Com- puter Science Department, 1991. [15] L. Giordano, D. Theseider Duprรฉ, Weighted defeasible knowledge bases and a multipreference semantics for a deep neural network model, in: Logics in Artificial Intelligence, Springer International Publishing, 2021, pp. 225โ€“242. [16] F. Baader, I. Horrocks, C. Lutz, U. Sattler, An Introduc- tion to Description Logic, Cambridge UP, 2017. [17] N. Potyka, Interpreting neural networks as quanti- tative argumentation frameworks, in: Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applica- tions of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial In-