On a Plausible Concept-wise Multipreference Semantics and its Relations with Self-organising Maps ?

Abstract

In this paper we describe a concept-wise multi-preference semantics for description logic which has its root in the preferential approach for modeling defeasible reasoning in knowledge representation. We argue that this proposal, beside satisfying some desired properties, such as KLM postulates, and avoiding the drowning problem, also defines a plausible notion of semantics. We motivate the plausibility of the concept-wise multi-preference semantics by developing a logical semantics of self-organising maps, which have been proposed as possible candidates to explain the psychological mechanisms underlying category generalisation, in terms of multi-preference interpretations.

Introduction

Conditional logics have their roots in philosophical logic. They have been studied first by Lewis [ 25, 28 ] to formalize hypothetical and counterfactual reasoning (if A were the case then B) that cannot be captured by classical logic with its material implication. From the 80’s they have been considered in computer science and artificial intelligence and they have provided an axiomatic foundation of non-monotonic and common sense reasoning [ 12, 23 ]. In particular, preferential approaches [ 23, 24 ] to common sense reasoning have been more recently extended to description logics, to deal with inheritance with exceptions in ontologies, allowing for non-strict forms of inclusions, called typicality or defeasible inclusions (namely, conditionals), with different preferential semantics [ 15, 5 ] and closure constructions [ 7, 6, 18, 30 ].

In this paper we consider a “concept-aware” multipreference semantics [ 13 ] that has been recently introduced for a lightweight description logic of the E L? family, which takes into account preferences with respect to different concepts, and integrates them into a preferential semantics. To support the plausibility of this semantics we show that it can be used to provide a logical semantics of self-organising maps [ 22 ]. Self-organising maps (SOMs) have been proposed as possible candidates to explain the psychological mechanisms underlying category generalisation. They are psychologically and biologically plausible neural network models that can learn after limited exposure to positive category examples, without any need of contrastive information.

We show that the process of category generalization in self-organising maps produces, as a result, a multipreference model in which a preference relation is associated to each concept (each learned category) and the combination of the preferences into a global one, following the approach in [ 13 ], defines a standard KLM preferential model. The model can be exploited to learn or validate conditional knowledge from the empirical data used in the category generalization process, and the evaluation of conditionals can be done by model checking, using the information recorded in the SOM.

Based on the assumption that the abstraction process in the SOM is able to identify the most typical exemplars for a given category, in the semantic representation of a category, we will identify some specific exemplars (namely, the best matching units of the category) as the typical exemplars of the category, thus defining a preference relation among the instances of a category.

The category generalization process can then be regarded as a model building process and, in a way, as a belief revision process. Indeed, initially we have no belief about which is the category of any exemplar. During training, the current state of the SOM corresponds to a model representing the beliefs about the input exemplars considered so far (concerning their category). Each time a new input exemplar is considered, this model is revised adding the exemplar into the proper category. 2

Preliminary: the description logic E L? We consider the description logic E L? of the E L family [ 1 ]. Let NC be a set of concept names, NR a set of role names and NI a set of individual names. The set of E L? concepts can be defined as follows: C := A j > j ? j C u C j 9r:C, where a 2 NI , A 2 NC and r 2 NR. Observe that union, complement and universal restriction are not E L? constructs. A knowledge base (KB) K is a pair (T ; A), where T is a TBox and A is an ABox. The TBox T is a set of concept inclusions (or subsumptions) of the form C v D, where C; D are concepts. The ABox A is a set of assertions of the form C(a) and r(a; b) where C is a concept, r 2 NR, and a; b 2 NI .

An interpretation for E L? is a pair I = h ; I i where: is a non-empty domain—a set whose elements are denoted by x; y; z; : : : —and I is an extension function that maps each concept name C 2 NC to a set CI , each role name r 2 NR to a binary relation rI , and each individual name a 2 NI to an element aI 2 . It is extended to complex concepts as follows: >I = , ?I = ;, (C u D)I = CI \ DI and (9r:C)I = fx 2 j 9y:(x; y) 2 rI and y 2 CI g: The notions of satisfiability of a KB in an interpretation and of entailment are defined as usual: Definition 1 (Satisfiability and entailment). Given an E L? interpretation I = h ; I i: - I satisfies an inclusion C v D if CI DI ; - I satisfies an assertion C(a) if aI 2 CI and an assertion r(a; b) if (aI ; bI ) 2 rI . Given a KB K = (T ; A), an interpretation I satisfies T (resp. A) if I satisfies all inclusions in T (resp. all assertions in A); I is a model of K if I satisfies T and A.

A concept-wise multi-preference semantics

In this section we describe an extension of E L? with typicality inclusions, defined along the lines of the extension of description logics with typicality [ 15, 17 ], but we exploit a different multi-preference semantics [ 13 ]. In addition to standard E L? inclusions C v D (called strict inclusions in the following), the TBox T will also contain typicality inclusions of the form T(C) v D, where C and D are E L? concepts. A typicality inclusion T(C) v D means that “typical C’s are D’s” or “normally C’s are D’s” and corresponds to a conditional implication C j D in Kraus, Lehmann and Magidor’s (KLM) preferential approach [ 23, 24 ]. Such inclusions are defeasible, i.e., admit exceptions, while strict inclusions must be satisfied by all domain elements.

Let C = fC1; : : : ; Ckg be a set of (arbitrary) E L? concepts, called distinguished concepts. For each concept Ci 2 C, we introduce a modular preference relation <Ci which describes the preference among domain elements with respect to Ci. Each preference relation <Ci has the same properties of preference relations in KLM-style ranked interpretations [ 24 ], is a modular and well-founded strict partial order, i.e., irreflexive and transitive relation, where: <Ci is well-founded if, for all S , if S 6= ;, then min<Ci (S) 6= ;; and <Ci is modular if, for all x; y; z 2 , if x <Cj y then x <Cj z or z <Cj y.

Definition 2 (Multipreference interpretation). A multipreference interpretation is a

tuple M = h ; <C1 ; : : : ; <Ck ; I i, where: (a) is a non-empty domain; (b) <Ci is an irreflexive, transitive, well-founded and modular relation over ; (d) I is an interpretation function, drfined as in E L? interpretations (see Section 2). Observe that, given a multipreference interpretation, a triple MCi = h ; <Ci ; I i, which can be associated to each concept Ci, is a ranked interpretation as those considered for E L? plus typicality in [ 19 ]. The preference relation <Ci allows the set of prototypical Ci-elements to be defined as the set of Ci-elements which are minimal with respect to <Ci , i.e., the set min<Ci (CiI ). As a consequence, the multipreference interpretation above is able to single out the typical Ci-elements, for all distinguished concepts Ci 2 C.

The multipreference structures above are at the basis of the semantics for ranked E L? knowledge bases [ 13 ], which have been inspired to Brewka’s framework of basic preference descriptions [ 4 ]. A ranked TBox TCi is allowed for each concept Ci 2 C, and contains all the defeasible inclusions, T(Ci) v D, specifying the typical properties of Ci-elements. Ranks (non-negative integers) are assigned to such inclusions; the ones with higher ranks are considered to be more important than the ones with lower ranks.

Consider, for instance, the ranked knowledge base K = hTstrict; TEmployee; TStudent; TP hDStudent; Ai, over the set of distinguished concepts C = fEmployee; Student ; PhDStudent g, with empty ABox, and with Tstrict the set of strict inclusions:

Employee v Adult Adult v 9has SSN :> PhdStudent v Student

Young u NotYoung v ? 9hasScholarship:> u Has no Scholarship v ?; where the ranked TBox TEmployee = f(d1; 0); (d2; 0)g contains the defeasible inclusions: (d1) T(Employee) v NotYoung (d2) T(Employee) v 9has boss:Employee; the ranked TBox TStudent = f(d3; 0); (d4; 1); (d5; 1)g contains the defeasible inclusions: (d3) T(Student ) v 9has classes:> (d4) T(Student ) v Young (d5) T(Student ) v Has no Scholarship and the ranked TBox TP hDStudent = f(d6; 0); (d7; 1)g contains the inclusions: (d6) T(PhDStudent ) v 9hasScholarship:Amount (d7) T(PhDStudent ) v Bright Exploiting the fact that for an E L? knowledge base we can restrict our consideration to finite domains [ 1 ], and considering canonical models for E L? [ 13 ] which are large enough to contain a domain element for each possible consistent concept occurring in K (and its complement), the ranked knowledge base K above gives rise to canonical models, where the three preference relations <Employee , <Student , and <PhDStudent represent the preference among the elements of the domain according to concepts Employee, Student , and PhDStudent , respectively.

While we refer to [ 13 ] for the construction of the preference relations <Ci ’s from a ranked knowledge base K, in the following we will recall the notion of concept-wise multi-preference interpretation which can be obtained by combining the preference relations <Ci into a global preference relation <. This is needed for reasoning about the typicality of arbitrary E L? concepts C, which do not belong to the set of distinguished concepts C. For instance, we may want to verify whether typical employed students are young, or whether they have a boss. To answer these query both preference relations <Employee and <Student are relevant, and they might be conflicting for some pair of domain elements as, for instance, tom is more typical than bob as a student (tom <Student bob), but more exceptional as an employee ( bob <Employee tom).

To define a global preference relation, we take into account the specificity relation among concepts, such as, for instance, the fact that a concept like PhdStudent is more specific than concept Student . The idea is that, in case of conflicts, the properties of a more specific class (such as that PhD students normally have a scholarship) should override the properties of less specific class (such as that students normally do not have a scholarship).

Definition 3 (Specificity). A specificity relation among concepts in C is a binary relation

C C which is irreflexive and transitive.

For Ch; Cj 2 C, Ch Cj means that Ch is more specific than Cj . The simplest notion of specificity among concepts with respect to a knowledge base K is based on the subsumption hierarchy: Ch Cj if Tstrict j=EL? Ch v Cj and Tstrict 6j=EL? Cj v Ch. This is one of the notions of specificity considered for DLN [ 3 ]. Another one is based on the ranking of concepts in the rational closure of K.

Let us recall the notion of concept-wise multipreference interpretation [ 13 ]. Definition 4 (concept-wise multipreference interpretation). A concept-wise multipreference interpretation (or cwm-interpretation) is a tuple M = h ; <C1 ; : : : ; <Ck ; < ; I i such that: (a) is a non-empty domain; (b) for each i = 1; : : : ; k, <Ci is an irreflexive, transitive, well-founded and modular relation over ; (c) < is a (global) preference relation over defined from <C1 ; : : : ; <Ck as follows: x < y iff (i) x <Ci y; for some Ci 2 C; and (ii) for all Cj 2 C; x

Cj y or 9Ch(Ch

Cj and x <Ch y) (d) I is an interpretation function, as defined for E L? interpretations (see Section 2), with the addition that, for typicality concepts, we let:

(T(C))I = min<(CI )

Relation < is defined from <C1 ; : : : ; <Ck based on a modified Pareto condition: x < y holds if there is at least a Ci 2 C such that x <Ci y and, for all Cj 2 C, either x Cj y holds or, in case it does not, there is some Ch more specific than Cj such that x <Ch y (preference <Ch in this case overrides <Cj ). The idea is that, for two PhD students (who are also students) Bob and Mary, if mary <Student bob and bob <PhDStudent mary , we will have bob < mary , that is, Bob is regarded as being globally more typical than Mary as he satisfies more properties of typical PhD students wrt Mary although Mary may satisfy additional properties of typical students wrt Bob.

It has been proven [ 13 ] that, given a cwm-interpretation M = h ; <C1 ; : : : ; <Ck ; < ; I i, the relation < is an irreflexive, transitive and well-founded relation. Hence, the triple M0 = h ; <; I i is a KLM-style preferential interpretation, as those introduced for E L? with typicality [ 16 ] (and it is not necessarily a modular interpretation). A cwm-model of a ranked E L? knowledge base K is then defined as a specific preferential interpretation which builds over the preference relations <Ci , constructed from the ranked TBoxes TCi , and satisfying all strict inclusions and assertions in K. The notion of cwm-entailment, defined in the obvious way, satisfies the KLM postulates of a preferential consequence relation, and does not suffer from the drowning problem, a well known problem of the rational closure and System Z [ 29, 2 ], roughly speaking the problem that, if a subclass of C is exceptional for a given aspect, it is exceptional tout court and does not inherit any of the typical properties of C. We refer to [ 13 ] for a discussion on the properties of entailment through some example. In the next section we motivate the plausibility of this concept-wise multipreference semantics showing that it is well suited to provide a semantic characterization of self-organising maps [ 22 ]. 4

Self-organising maps

Self-organising maps (SOMs, introduced by Kohonen [ 22 ]) are particularly plausible neural network models that learn in a human-like manner. In particular: SOMs learn to organize stimuli into categories in an unsupervised way, without the need of a teacher providing a feedback; they can learn with just a few positive stimuli, without the need for negative examples or contrastive information; they reflect basic constraints of a plausible brain implementation in different areas of the cortex [ 27 ], and are therefore biologically plausible models of category formation; have proven to be capable of explaining experimental results.

In this section we shortly describe the architecture of SOMs and report Gliozzi and Plunkett’s similarity-based account of category generalization based on SOMs [ 20 ]. In brief, in [ 20 ] the authors judge a new stimulus as belonging to a category by comparing the distance of the stimulus from the category representation to the precision of the category representation.

SOMs consist of a set of neurons, or units, spatially organized in a grid [ 22 ], as in Figure 1. Each map unit u is associated with a weight vector wu of the same dimensionality as the input vectors. At the beginning of training, all weight vectors are initialized to random values, outside the range of values of the input stimuli. During training, the input elements are sequentially presented to all neurons of the map. After each presentation of an input x, the best-matching unit (BMUx) is selected: this is the unit i whose weight vector wi is closest to the stimulus x (i.e. i = arg minj kx wj k).

The weights of the best matching unit and of its surrounding units are updated in order to maximize the chances that the same unit (or its surrounding units) will be selected as the best matching unit for the same stimulus or for similar stimuli on subsequent presentations. In particular, it reduces the distance between the best matching unit’s weights (and its surrounding neurons’ weights) and the incoming input. Furthermore, it organizes the map topologically so that the weights of close-by neurons are updated in a similar direction, and come to react to similar inputs. We refer to [ 22 ] for a complete description.

The learning process is incremental: after the presentation of each input, the map’s representation of the input (and in particular the representation of its best-matching unit) is updated in order to take into account the new incoming stimulus. At the end of the whole process, the SOM has learned to organize the stimuli in a topologically significant way: similar inputs (with respect to Euclidean distance) are mapped to close by areas in the map, whereas inputs which are far apart from each other are mapped to distant areas of the map.

Once the SOM has learned to categorize, to assess category generalization, Gliozzi and Plunkett [ 20 ] define the map’s disposition to consider a new stimulus y as a member of a known category C as a function of the distance of y from the map’s representation of C. They take a minimalist notion of what is the map’s category representation: this is the ensemble of best-matching units corresponding to the known instances of the category. They use BM UC to refer to the map’s representation of category C and define category generalization as depending on two elements: – the distance of the new stimulus y with respect to the category representation – compared to the maximal distance from that representation of all known instances of the category This captured by the following notion of relative distance (rd for short) [ 20 ] : rd(y; C) =

minky maxx2C kx

BM UC k

BM Uxk (1) where minky BM UC k is the (minimal) Euclidean distance between y and C’s category representation, and maxx2C kx BM Uxk expresses the precision of category representation, and is the (maximal) Euclidean distance between any known member of the category and the category representation.

With this definition, a given Euclidean distance from y to C0s category representation will give rise to a higher relative distance rd if the maximal distance between C and its known examples is low (and category representation is precise) than if it is high (and category representation is coarse). As a function of the relative distance above, Gliozzi and Plunkett then define the map’s Generalization Degree of category C membership to a new stimulus y.

It was observed that the above notion of relative distance (Equation 1) requires there to be a memory of some of the known instances of the category being used (this is needed to calculate the denominator in the equation). This gives rise to a sort of hybrid model in which category representation and some exemplars coexist. An alternative way of formulating the same notion of relative distance would be to calculate online the distance between known category instance currently examined and the representation of the category being formed.

By judging a new stimulus as belonging to a category by comparing the distance of the stimulus from the category representation to the precision of the category representation, Gliozzi and Plunkett demonstrate [ 20 ] that the Numerosity and Variability effects of category generalization, described by Griffiths and Tenenbaum [ 32 ], and usually explained with Bayesian tools, can be accommodated within a simple and psychologically plausible similarity-based account, which contrasts what was previously maintained. In the next section, we show that their notion of relative distance can also be used as a basis for a logical semantics for SOMs. 5

Relating self-organising Maps and multi-preference models

We aim at showing that, once the SOM has learned to categorize, we can regard the result of the categorization as a multipreference interpretation. Let X be the set of input stimuli from different categories, C1; : : : ; Ck, which have been considered during the learning process.

For each category Ci, we let BM UCi be the ensemble of best-matching units corresponding to the input stimuli of category Ci, i.e., BM UCi = fBM Ux j x 2 X and x 2 Cig. We regard the learned categories C1; : : : ; Ck as being the concept names (atomic concepts) in the description logic and we let them constitute our set of distinguished concepts C = fC1; : : : ; Ckg.

To construct a multi-preference interpretation we proceed as follows: first, we fix the domain s to be the space of all possible stimuli; then, for each category (concept) Ci, we define a preference relation <Ci , exploiting the notion of relative distance of a stimulus y from the map’s representation of Ci. Finally, we define the interpretation of concepts.

Let s be the set of all the possible stimuli, including all input stimuli (X s) as well as the best matching units of input stimuli (i.e., fBM Ux j x 2 Xg s). For simplicity, we will assume that the space of input stimuli is finite.

Once the SOM has learned to categorize, the notion of relative distance rd(x; Ci) of a stimulus x from a category Ci introduced above can be used to build a binary preference relation <Ci among the stimuli in s w.r.t. category Ci as follows: for all x; x0 2 s, x <Ci x0 iff rd(x; Ci) < rd(x0; Ci) (2) Each preference relation <Ci is a strict partial order relation on s. The relation <Ci is also well-founded as we have assumed s to be finite.

We exploit this notion of preference to define a multipreference interpretation associated with the SOM, and than a cwm-model of the SOM. In the following we restrict the DL language to the fragment of E L? (plus typicality) not admitting roles, as in the self-organising map we do not have a representation of role names.

Definition 5 (Multipreference-model of a SOM). The multipreference-model of the

SOM is a multipreference interpretation Ms = h s; <C1 ; : : : ; <Ck ; I i such that: (i) s is the set of all the possible stimuli, as introduced above; (ii) for each Ci 2 C, <Ci is the preference relation defined by equivalence (2). (iii) the interpretation function I is defined for concept names (i.e. categories) Ci as follows:

CiI = fy 2 s j rd(y; Ci) rdmax;Ci g where rdmax;Ci is the maximal relative distance of an input stimulus x 2 Ci from category Ci, that is, rdmax;Ci = maxx2Ci frd(x; Ci)g. The interpretation function I is extended to complex concepts according to Definition 2.

Informally, we interpret as Ci-elements those stimuli whose relative distance from category Ci is not larger than the relative distance of any input exemplar belonging to category Ci. Given <Ci , we can identify the most typical Ci-elements wrt <Ci as the Ci-elements whose relative distance from category Ci is minimal, i.e., the elements in min<Ci (CiI ). Observe that the best matching unit BM Ux of an input stimulus x 2 Ci is an element of s. Hence, for y = BM Ux, the relative distance rd(y; Ci) of y from category Ci is 0, as min jj y BM UCi jj= 0. Therefore, min<Ci (CiI ) = fy 2 s j rd(y; Ci) = 0g and BM UCi min<Ci (CiI ). 5.1

Evaluation of concept inclusions by model checking

We have defined a multipreference interpretation Ms where, in the domain s of the possible stimuli, we are able to identify, for each category Ci, the Ci-elements as well as the most typical Ci-elements wrt <Ci . We can exploit Ms to verify which inclusions are satisfied by the SOM by model checking, i.e., by checking the satisfiability of inclusions over model Ms. This can be done both for strict concept inclusions of the form Ci v Cj and for defeasible inclusions of the form T(Ci) v Cj , where Ci and Cj are concept names (i.e., categories).

For the verification that a typicality inclusion T(Ci) v Cj is satisfied in Ms we have to check that the most typical Ci elements wrt <Ci are Cj elements, that is min<Ci (CiI ) CjI . Note that, besides the elements in BM UCi , min<Ci (CiI ) may contain other elements of s having relative distance 0 from Ci. As we do not know, for all the possible input stimuli in s, whether they belong to min<Ci (CiI ) or to CjI , as an approximation, we only check that all elements in BM UCi are Cj elements, that is: for all input stimuli x 2 Ci, rd(BM Ux; Cj ) rdmax;Cj (3) Let the relative distance of BM CCi from Cj be defined as

rd(BM CCi ; Cj ) = maxx2Ci frd(BM Ux; Cj )g i.e., as the maximal relative distance of any BM Ux, for x 2 Ci, and Cj . Then we can rewrite condition (3) simply as rd(BM CCi ; Cj ) rdmax;Cj : Observe that the relative distance rd(BM CCi ; Cj ) also gives a measure of plausibility of the defeasible inclusion T(Ci) v Cj : the lower is the relative distance of BM UCi from Cj , the more plausible is the defeasible inclusion T(Ci) v Cj .

Verifying that a strict inclusion Ci v Cj is satisfied, requires to check that CiI is included in CI . Exploiting the fact that the map is organized topologically, and using j the relative distance rd(BM CCi ; Cj ) of BM CCi from Cj , we verify that the relative distance of BM CCi from Cj plus the maximal relative distance of a Ci-element from Ci is not greater than the maximal relative distance of a Cj -element from Cj : rd(BM CCi ; Cj ) + rdmax;Ci rdmax;Cj (4) where rdmax;C = maxy2C frd(y; C)g. That is, the Ci-element most distant from Cj is nearer to Cj than the most distant Cj -element.

Computing conditions (3) and (4) on the SOM, may be non trivial, depending on the number of input stimuli that have been considered in the learning phase (the size of the set X of input exemplars). However, from a logical point of view, this is just model checking. Gliozzi and Plunkett have considered self-organising maps that are able to learn from a limited number of input stimuli, although this is not generally true for all self-organising maps [ 20 ]. 5.2

Combining preferences into a preferential interpretation

The multipreference interpretation Ms introduced in Definition 5 allows to determine the set of Ci-elements for all learned categories Ci and to define the most typical Cielements, exploiting the preference relation <Ci . However, we are not able to define the most typical Ci u Cj -elements just using a single preference. Starting from Ms, we construct a concept-wise multipreference interpretation Msom that combines the preferential relations in Ms into a global preference relation <, and provides an intepretation to all typicality concepts as, for instance, T(Ci u Cj u Ch). The interpretation Msom is constructed from Ms according to Definition 4.

The construction exploits a notion of specificity. Observe that the specificity relation between two concepts Ci and Cj can be determined based on the single model Ms of the SOM. Ci Cj if Ci v Cj is satisfied in Ms and Cj v Ci is not satisfied in Ms.

Definition 6 (cwm-model of a SOM). The cwm-model of a SOM is a cwm-interpretation

Msom = h s; <C1 ; : : : ; <Ck ; <; I i, such that the tuple h s; <C1 ; : : : ; <Ck ; I i is a multipreference model of the SOM according to Definition 5, and < is the global preference relation defined from <C1 ; : : : ; <Ck ; according as in Definition 4, point (c).

In particular, in Msom, as in all cwm-interpretations (see Definition 4), the interpretation of typicality concepts T(C) is defined based on the global preference relation < as (T(C))I = min<(CI ), for all concepts C. Here, we are considering concepts in the fragment of E L? language without roles, which are built from the concept names C1; : : : ; Cn (the learned categories). The model Msom can be considered a sort of (unique) canonical model for the SOM, representing what holds in that state of the SOM (e.g., after the learning phase). The logical inclusions that “follow from the SOM” are therefore the inclusions that hold in the single model Msom. The situation is similar to the case of Horn clauses, where there is a unique minimal canonical model describing all the (atomic) logical consequences of the knowledge base.

As Msom is a cwm-interpretation, the triple h s; <; I i is a KLM style preferential interpretation [ 23, 24 ]. It follows that the model Msom provides a logical semantics for the SOM which is well-defined, as Msom determines a preferential interpretation and, also, a preferential consequence relation, satisfying all KLM properties of a preferential consequence relations.

The verification of arbitrary defeasible inclusions on Msom can, in principle, be done by model checking, but it might require considering all the possibly many input stimuli, i.e., all domain elements in s, which may be unfeasible in practice. As an alternative, the identification of the set of strict and defeasible inclusions satisfied by the SOM over the learned categories C1; : : : ; Ck (as done in Section 5.1), allows to define an E L? knowledge base K and to reason on it symbolically, using for instance an approach similar to the one described in Section 3 for ranked knowledge bases. In particular, Answer Set Programming, and asprin, have been used to achieve defeasible reasoning + [ 13 ]. under the multipreference approach for the lightweight description logic E L? Ranked knowledge bases have been considered, where the rank of defeasible inclusions provides a measure of plausibility of the defeasible inclusion, and multipreference entailment has been reformulated as a problem of computing preferred answer sets. As we have seen, a measure of plausibility can as well be assigned to the defeasible inclusions satisfied by the SOM. 5.3

Category generalization process as iterated belief revision

We have seen that one can give an interpretation of a self-organising map after the learning phase, as a preferential model. However, the state of the SOM during the learning phase can as well be represented as a multipreference model (precisely in the same way). During training, the current state of the SOM corresponds to a model representing the beliefs about the input stimuli considered so far (beliefs concerning the category of the stimuli).

The category generalization process can then be regarded as a model building process and, in a way, as a belief revision process. Initially we do not know the category of the stimuli in the domain s. In the initial model, call it Ms0om (over the domain s) the som is the model of a knowledge base K0 interpretation of each concept Ci is empty. M0 containing a strict inclusion Ci v ?, for all Ci.

Each time a new input stimulus (x 2 Ci) is considered, the model is revised adding the stimulus x (and its best matching unit BM Ux) into the proper category (Ci). Not only the category interpretation is revised by the addition of x and BM Ux in CiI (so that Ci v ? does not hold any more), but also the associated preference relation <Ci is revised as the addition of BM Ux modifies the set of best matching units BM UCi for category Ci, as well as the relative distance rd(y; Ci) of a stimulus y from Ci. That is, a revision step may change the set of conditionals which are satisfied by the model.

At the end of the training process, the final state of the SOM is captured by the model Msom obtained by a sequence of revision steps which, starting from Ms0om, gives rise to a sequence of models Ms0om,Mis1om; : : :, Misrom (with Msom = Misrosmom). At each step the knowledge base is not represented explicitly, but the model Mij of the knowledge base at step j is used to determine the model at step j + 1 as a result of revision (Misjo+m1 = Misjom ? Cij (xij )). The knowledge base K (the set of all the strict and defeasible inclusions satisfied in Msom) can then be regarded as the knowledge base obtained from K0 through a sequence of revision steps, i.e., K = K0 ? Ci1(xi1) ? : : : ? Cir(xir). In fact, from any state of the SOM we can construct a corresponding model, which determines a knowledge base, the set of (strict and defeasible) inclusions satisfied in that model. For future work, it would be interesting to study the properties of this notion of revision and compare with the properties of the notions of iterated belief revision studied in the literature [ 9, 14, 21, 8 ]. 6

Conclusions

The concept-wise multipreference semantics has recently been introduced for dealing with typicality in description logics [ 13 ], based on the idea that reasoning about exceptions in ontologies requires taking into account preferences with respect to different concepts and integrating them into a preferential semantics which allows a standard, KLM style, interpretation of defeasible inclusions.

In this paper, we have explored the relationships between a concept-wise multipreference semantics and self-organising maps. On the one hand, we have seen that self-organising maps can be given a logical semantics in terms of KLM-style preferential interpretations. The model can be used to learn or to validate conditional knowledge from the empirical data used in the category generalization process based on model checking. The learning process in the self-organising map can be regarded as an iterated belief revision process. On the other hand, the plausibility of concept-wise multipreference semantics is supported by the fact that self-organising maps are considered as psychologically and biologically plausible neural network models.

Much work has been devoted, in recent years, to the combination of neural networks and symbolic reasoning. Let us mention Neural Symbolic Computing [ 11, 10 ], Logic Tensor Networks [ 31 ], and the approaches based on computational logic and logic programming DeepProbLog [ 26 ], a probabilistic logic programming language which incorporates deep learning by means of neural predicates, and NeurASP [ 33 ], a simple extension of answer set programs that embrace neural networks.

The characterization of self-organising maps in terms of multipreference interpretations, besides providing a logical interpretation to SOMs, which may be of interest from the side of explainable AI, can potentially be exploited, as described above, as a basis for an integrated use of self-organising maps and defeasible knowledge bases.

Acknowledgement: This research is partially supported by INDAM-GNCS Projects 2019 and 2020.

References

1. F. Baader , S. Brandt , and C. Lutz . Pushing the E L envelope . In L.P. Kaelbling and A . Saffiotti, editors, Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI 2005 ), pages 364 - 369 , Edinburgh, Scotland, UK , August 2005 . Professional Book Center.

2. S. Benferhat , D. Dubois , and H. Prade . Possibilistic logic: From nonmonotonicity to logic programming . In Symbolic and Quantitative Approaches to Reasoning and Uncertainty, European Conference, ECSQARU'93, Granada , Spain, November 8- 10 , 1993 , Proceedings, pages 17 - 24 , 1993 .

3. P. A. Bonatti , M. Faella , I. Petrova , and L. Sauro . A new semantics for overriding in description logics . Artif . Intell., 222 : 1 - 48 , 2015 .

4. Gerhard Brewka . A rank based description language for qualitative preferences . In Proceedings of the 16th Eureopean Conference on Artificial Intelligence, ECAI' 2004 , Valencia, Spain, August 22-27 , 2004 , pages 303 - 307 , 2004 .

5. K. Britz , J. Heidema , and T. Meyer. Semantic preferential subsumption . In G. Brewka and J. Lang, editors, Principles of Knowledge Representation and Reasoning: Proceedings of the 11th International Conference (KR 2008 ), pages 476 - 484 , Sidney, Australia, September 2008 . AAAI Press.

6. G. Casini , T. Meyer, I. J. Varzinczak , , and K. Moodley . Nonmonotonic Reasoning in Description Logics: Rational Closure for the ABox . In 26th International Workshop on Description Logics (DL 2013 ), volume 1014 of CEUR Workshop Proceedings , pages 600 - 615 , 2013 .

7. G. Casini and U. Straccia . Rational Closure for Defeasible Description Logics . In T. Janhunen and I. Niemela¨, editors, Proc. 12th European Conf. on Logics in Artificial Intelligence (JELIA 2010 ), volume 6341 of LNCS , pages 77 - 90 , Helsinki, Finland, September 2010 . Springer.

8. J. Chandler and R. Booth . Revision by conditionals: From hook to arrow . In Proc. KR 2020 , 17th International Conference on Principles of Knowledge Representation and Reasoning . AAAI Press, 2020 .

9. A. Darwiche and J. Pearl . On the logic of iterated belief revision . Artificial Intelligence , 89 : 1 - 29 , 1997 .

10. A. S. d'Avila Garcez , M. Gori , L. C. Lamb , L. Serafini , M. Spranger , and Son N. Tran . Neural-symbolic computing: An effective methodology for principled integration of machine learning and reasoning . FLAP , 6 ( 4 ): 611 - 632 , 2019 .

11. A. S. d'Avila Garcez , L. C. Lamb , and D. M. Gabbay . Neural-Symbolic Cognitive Reasoning. Cognitive Technologies . Springer, 2009 .

12. J. P. Delgrande . A first-order conditional logic for prototypical properties . Artificial Intelligence , 33 ( 1 ): 105 - 130 , 1987 .

13. L. Giordano and D. Theseider Dupre´. An ASP approach for reasoning in a concept-aware multipreferential lightweight DL. Theory and Practice of Logic programming , TPLP , 10 ( 5 ): 751 - 766 , 2020 . https://doi.org/10.1017/S1471068420000381.

14. L. Giordano , V. Gliozzi , and N. Olivetti . Iterated Belief Revision and Conditional Logic . Studia Logica , 70 : 23 - 47 , 2002 .

15. L. Giordano , V. Gliozzi , N. Olivetti , and G. L. Pozzato . Preferential Description Logics . In Nachum Dershowitz and Andrei Voronkov, editors, Proceedings of LPAR 2007 ( 14th Conference on Logic for Programming , Artificial Intelligence, and Reasoning) , volume 4790 of LNAI , pages 257 - 272 , Yerevan, Armenia, October 2007 . Springer-Verlag.

16. L. Giordano , V. Gliozzi , N. Olivetti , and G. L. Pozzato . Reasoning about typicality in low complexity DLs: the logics E L?Tmin and DL-Litec Tmin . In Proc. 22nd Int. Joint Conf. on Artificial Intelligence (IJCAI 2011 ), pages 894 - 899 , Barcelona, July 2011 . Morgan Kaufmann.

17. L. Giordano , V. Gliozzi , N. Olivetti , and G. L. Pozzato . Semantic characterization of rational closure: From propositional logic to description logics . Artificial Intelligence , 226 : 1 - 33 , 2015 .

18. L. Giordano , V. Gliozzi , N. Olivetti , and G.L. Pozzato . Minimal Model Semantics and Rational Closure in Description Logics . In 26th International Workshop on Description Logics (DL 2013 ), volume 1014 , pages 168 - 180 , 7 2013 .

19. L. Giordano and D. Theseider Dupre´. ASP for minimal entailment in a rational extension of SROEL . TPLP, 16 ( 5-6 ): 738 - 754 , 2016 . DOI: 10 .1017/S1471068416000399.

20. V. Gliozzi and K. Plunkett . Grounding bayesian accounts of numerosity and variability effects in a similarity-based framework: the case of self-organising maps . Journal of Cognitive Psychology , 31 ( 5-6 ), 2019 .

21. G. Kern-Isberner . A thorough axiomatization of a principle of conditional preservation in belief revision . Ann. Math. Artif. Intell., 40 ( 1-2 ): 127 - 164 , 2004 .

22. T. Kohonen, M.R. Schroeder , and T.S. Huang, editors. Self-Organizing Maps, Third Edition . Springer Series in Information Sciences. Springer, 2001 .

23. S. Kraus , D. Lehmann , and M. Magidor . Nonmonotonic reasoning, preferential models and cumulative logics . Artificial Intelligence , 44 ( 1-2 ): 167 - 207 , 1990 .

24. D. Lehmann and M. Magidor . What does a conditional knowledge base entail? Artificial Intelligence , 55 ( 1 ): 1 - 60 , 1992 .

25. D. Lewis . Counterfactuals. Basil Blackwell Ltd , 1973 .

26. R. Manhaeve , S. Dumancic , A. Kimmig , T. Demeester , and L. De Raedt. Deepproblog: Neural probabilistic logic programming . In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018 , NeurIPS 2018 , 3 -8 December 2018 , Montre´al, Canada, pages 3753 - 3763 , 2018 .

27. R. Miikkulainen , J. Bednar , Y. Choe , and J. Sirosh . Computational maps in the visual cortex . Springer, 2002 .

28. D. Nute . Topics in conditional logic . Reidel , Dordrecht, 1980 .

29. J. Pearl . System Z: A Natural Ordering of Defaults with Tractable Applications to Nonmonotonic Reasoning . In R. Parikh, editor, TARK (3rd Conference on Theoretical Aspects of Reasoning about Knowledge) , pages 121 - 135 , Pacific Grove, CA, USA, 1990 . Morgan Kaufmann.

30. M. Pensel and A. Turhan . Reasoning in the defeasible description logic EL? - computing standard inferences under rational and relevant semantics . Int. J. Approx. Reasoning , 103 : 28 - 70 , 2018 .

31. Luciano Serafini and Artur S. d'Avila Garcez. Learning and reasoning with logic tensor networks . In AI*IA 2016: Advances in Artificial Intelligence - XVth Int. Conf. of the Italian Association for Artificial Intelligence , Genova, Italy, November 29 - December 1 , 2016 , Proceedings, volume 10037 of LNCS , pages 334 - 348 . Springer.

32. J. B. Tenenbaum and T. L. Griffiths . Generalization, similarity, and bayesian inference . Behavioral and Brain Sciences , 24 : 629 - 641 , 2001 .

33. Z. Yang , A. Ishay , and J. Lee . Neurasp: Embracing neural networks into answer set programming . In C. Bessiere, editor, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020 , pages 1755 - 1762 . ijcai.org, 2020 .