key: cord-0044770-lqug78es
authors: Esteva, Francesc; Godo, Lluís; Rodriguez, Ricardo Oscar; Vetterlein, Thomas
title: On Ruspini’s Models of Similarity-Based Approximate Reasoning
date: 2020-05-18
journal: Information Processing and Management of Uncertainty in Knowledge-Based Systems
DOI: 10.1007/978-3-030-50146-4_1
sha: a722478943d440f059e3c49eb9ca32c2a9a8f09d
doc_id: 44770
cord_uid: lqug78es

In his 1991 seminal paper, Enrique H. Ruspini proposed a similarity-based semantics for fuzzy sets and approximate reasoning which has been extensively used by many other authors in various contexts. This brief note, which is our humble contribution to honor Ruspini’s great legacy, describes some of the main developments in the field of logic that essentially rely on his ideas.

Similarity is a relevant notion in the context of at least three cognitive tasks: classification, case-based reasoning, and interpolation [1] . For classification tasks, objects are put together in the same class when they are indistinguishable with respect to some suitable criteria. Furthermore, case-based reasoning exploits the similarity between already solved problems and a new given problem to be solved in order to build up a solution to it. Finally, interpolation mechanisms estimate the value of a partially unknown function at a given point of a space by exploiting the proximity or closeness of this point to other points for which the value of the function is known.

It was Ruspini in [13] (cf. also [14] ) who started the task of formalising approximate reasoning underlying these and other cognitive tasks in a logical setting. He elaborated on the notion of fuzzy similarity, as suggested by Zadeh's theory of approximate reasoning [19] . According to the approach originally proposed by Ruspini to model fuzzy similarity-based reasoning, the set W of interpretations or possible worlds is, in a first step, equipped with a map S : W × W → [0, 1] supposed to fulfil the basic properties of fuzzy or graded similarity relation:

Reflexivity: S(u, u) = 1 for all u ∈ W Separability: S(u, v) = 1 iff u = v, for all u, v ∈ W Symmetry: S(u, v) = S(v, u) for all u, v ∈ W ⊗-Transivity: S(u, v) ⊗ S(v, w) ≤ S(u, w) for all u, v, w ∈ W where ⊗ is a t-norm.

Reflexive and symmetric fuzzy relations are often called closeness relations, while those further satisfying ⊗-transitivity are usually called ⊗-similarity relations, first introduced by Trillas in [15] under the name of T-indistinguishability relations. Sometimes, the name similarity relation is actually also used to denote ⊗-similarity relations where ⊗ = min. These min-similarity relations have the remarkable property that their level cuts

for any α ∈ [0, 1], are equivalence relations. See Recasens' monograph [11] for any question related to fuzzy similarity relations.

The notion of similarity can be regarded as a dual to the notion of a generalised (bounded) metric, in the sense that if S measures resemblance between possible worlds, δ = 1−S measures how distant they are. Then the ⊗-transitivity property corresponds to a generalised triangular inequality property for δ. In the particular case of ⊗ being Lukasiewicz t-norm, δ is a bounded metric, while δ becomes an ultrametric when ⊗ = min.

Given the set of possible worlds or interpretations together with a fuzzy similarity relation, Ruspini built up, in a second step, a basic framework to define possibilistic structures and concepts by quantifying proximity, closeness, or resemblance between pairs of (classical) logical statements. Since in classical logic we may identify propositions with sets of worlds, this problem reduces to the question how to extend a similarity between worlds to a measure of similarity between sets of worlds. As is well-known in the case of metric spaces, a metric between points does not univocally extend to a meaningful metric between sets of points. Ruspini defined in [13] two measures,

and

called implication and consistency, which are the lower and upper bounds, respectively, of the resemblance or proximity degree between p and q, from the perspective of q. Actually, if one defines the fuzzy set approx(p) of worlds close to those of p by the membership function

then we can write I S (p | q) = inf w|=q μ approx(p) (w) and it becomes clear that I S (p | q) is a measure of inclusion of the (crisp) set of q-worlds into the (fuzzy) set approx(p) of worlds close to p. Similarly, we can write C S (p | q) = sup w|=q μ approx(p) (w) and thus C S (p | q) is a measure of intersection between the set of q-worlds with the set of worlds close to p. Observe that, when the propositional language only contains finitely many propositional symbols and q is equivalent to a maximal consistent set of propositions, both measures coincide because there is a unique world w such that w |= q. In such a case, I S (p | q) = C S (p|q) = μ approx(p) (w). 1 With the implication measures I S , Ruspini's aim was to capture approximate inference patterns related to the so-called generalised modus ponens. The value of I S (p | q) provides the measure to what extent p is close to be true given q for granted. In particular, when the similarity relation S is separating and the set of worlds is finite then, I S (p | q) = 1 iff q |= p. Moreover, if S is ⊗-transitive, for a t-norm ⊗, then I S is ⊗-transitive as well [13] , i.e. the inequality

holds for any propositions p, q, and r. This property allows to formulate a kind of generalized resolution rule:

On the other hand, the value of C S (p | q) provides the measure to what extent p can be considered compatible with the available knowledge represented by q. In particular, in the finite case and with S satisfying the separation property,

Implication and consistency measures have quite different properties, apart from the fact that both I S and C S are reflexive, i.e., I S (p | p) = C S (p | p) = 1, and non-decreasing in the first variable: i.e., if p |= r, then I S (p | q) ≤ I S (r | q) and C S (p | q) ≤ C S (r | q). But w.r.t. to the second variable, I S is non-increasing while C S keeps being non-decreasing. Moroever, unlike I S , C S is a symmetric measure, i.e. C S (p | q) = C S (q | p), and it is not ⊗-transitive in general. On the other hand, it is easy to show that, for a fixed proposition r, the measure C S (· | r) is in fact a possibility measure [2] since the following identities hold true:

The counterpart of the last property for implication measures is the following one:

that is related to the so-called Left-Or property of consequence relations. We will return to this consideration in Sect. 2.

Note that conditional versions of the I S and C S measures were already considered by Ruspini in [13] , and then further elaborated in [6] and [3] in order to cast different forms of the generalized modus ponens inference pattern under the frame of similarity-based reasoning.

All these seminal ideas of Ruspini have been very fruitful in the foundations of approximate reasoning. In particular, one can find in the literature a number of approaches addressing the formalisation of similarity-based reasoning from a logical perspective. Due to space restrictions, in the rest of this short paper we restrict ourselves to review two main lines of developments in this area, namely, -Graded similarity-based entailments, and -Formalisations as conditional logics and as modal logics.

Let W be the set of classical interpretations (or worlds) of a propositional language. The rules of classical logic allows us to unambiguously decide whether a given proposition p is true or false in each of the worlds. We write w |= p to denote that p is true at w ∈ W (or that w satisfies p, or that w is a model of p), and w |= p to denote that p is false at w. In other words, each world partitions the set of proposition into two classes: those that are true and those that are false.

Assume now we have a ⊗-similarity relation S on the set W . This allows us to be more fine-grained when classifying propositions, since even two propositions p and q can be both false at a given world w, it may be the case that w is closer to the set of models of p than to those of q. In more precise terms, even if w |= p and w |= q, it can be the case that

In such a case one can say that, in the world w, p is closer to be true than q, or that p is more truthlike than q, in the sense of [10] .

In the rest of this section, we will overview three different ways of how this idea of having worlds more or less close to others can be used in a logical setting to introduce different kinds of graded similarity-based entailments [1, 7] .

Given a ⊗-similarity relation S on the set W of classical interpretations of a propositional language, one starts by defining for each α ∈ [0, 1] a (graded) approximate satisfaction relation |= α S , by stipulating for each w ∈ W and proposition p:

If w |= α S p we say that w is an approximate model (at level α) of p. The approximate satisfaction relation can be extended over to an approximate entailment relation in the usual way: a proposition p entails a proposition q at degree α, written p |= α S q, if each model of p is an approximate model of q at level α, that is,

Then p |= α S q stands for "q approximately follows from p" and α is a level of strength. Under this perspective p, together with the similarity relation S : W × W → [0, 1] on the set of interpretations, represents an epistemic state accounting for the factual information about the world. Then, we can know, not only what are the consequences we can infer from p using classical reasoning, but also those propositions which are approximate consequences of p, in the sense that they are close to some other proposition which is indeed a classical consequence of p.

In the case the propositional language is finitely generated, the following properties characterise these graded entailment relations |= α S , see [1] :

(1) Nestedness: i fp |= α q and β ≤ α then p |= β q; (2) ⊗-Transitivity:

if p |= α r and r |= β q then p |= α⊗β q; (3) Reflexivity:

p |= 1 p; (4) Rightweakening:

if p |= α q and q |= r then p |= α r; (5) Leftstrengthening: if p |= r and r |= α q then p |= α q; (6) Left-Or:

p ∨ r |= α q iff p |= α q and r |= α q; (7) Right-Or:

if r has a single model, r |= α p ∨ q iff r |= α p or r |= α q.

The ⊗-transitivity property is weaker than usual and the graceful degradation of the strength of entailment it expresses, when ⊗ = min, is rather natural. The fourth and fifth properties are consequences of the transitivity property (since q |= r entails q |= 1 r) and express a form of monotonicity. It must be noticed that |= α does not satisfy the Right-And property, i.e. from p |= α q and p |= α r it does not follow in general that p |= α q ∧ r. Hence the set of α-approximate consequences of p in the sense of |= α , for α < 1, will not be deductively closed in general. The Left-Or shows how disjunctive information is handled, while the Right-Or reflects the decomposability of the approximate satisfaction relation with respect to the ∨ connective only in the case the premise has a single model.

In the case where some (imprecise) background knowledge about the world is known and described under the form of some proposition K (i.e. the actual world is in the set of worlds satisfying K), then an approximate entailment relative to K can be straightforwardly defined as

See [1] for more details and properties of this derived notion of relative entailment.

The above approximate satisfaction relation w |= α S p can be also extended over another entailment relation |≡ S among propositions as follows: p |≡ α S q holds whenever each approximate model of p at a given level β is also an approximate model of q but at a possibly lower level α ⊗ β. Formally:

Now, p | ≡ α S q means "approximately-p entails approximately-q" and α is a level of strength, or in other words, when worlds in the vicinity of p-worlds are also in the vicinity (but possibly a bit farther) of q-worlds. This notion of entailment, called proximity entailment in [1] , also admits a characterization in terms of another similarity-based measure

where ⇒ is the residuum of the (left-continuous) t-norm ⊗ and I S (p | w) = sup w |=p S(w, w ). Indeed, one can easily check that p | ≡ α S q holds iff J S (q | p) ≥ α. This notion of approximate entailment relation can be easily made relative to a context or background knowldge, described by a (finite) set of propositions K, by defining

One can analogously characterize this entailment by a generalized measure J S,K , namely it holds that

The entailment |≡ α S,K satisfies similar properties to those satisfied by |= α S,K . Characterizations of both similarity-based graded entailments in terms of these properties are given in [1] . It is also shown there that |≡ α S and |= α S actually coincide, i.e. when there is no background knowledge K, or equivalently when K is a tautology. However, when K is not a tautology, |= α S,K is generally stronger than | ≡ α S,K .

Finally, the notion of graded satisfiability w |= α S p, can be also used for supporting a strong entailment relation with the following intended meaning: a proposition p strongly entails a proposition q at degree α, written p |≈ α S q, if each approximate model of p at level α is a model of q that is,

This stronger form of entailment is a sort of dual of the approximate entailment, as it denotes a notion of entailment that is robust to small (up to level α) deformations of the antecedent, while still entailing the consequent. In a similar way the approximate entailment was linked to the implication measure I S , this strong graded entailment is related to the consistency measure C S , in the following way:

by assuming the language is finitely generated and α > 0. Moreover, a characterization of this strong entailment in terms of some nice properties is given in [7] .

In a series of papers [7, [16] [17] [18] , the authors have been concerned with logics to reason about graded entailments. Graded approximate and strong entailments are taken as primitive objects of a propositional language. Let us briefly describe here the main features of the Logic of Approximate Entailment (LAE) from [7] . The basic building block of LAE are graded implications of the form

where φ, ψ are classical propositional formulas and α belongs to a suitable scale V of similarity values. The set of similarity values is endowed with a monoidal operation ⊗, which in case of the real unit interval is a t-norm. Furthermore, the language of LAE is built up from graded implications and constants ⊥, by means of the classical binary operators ∧ and ∨ and the unary operator ¬. The semantics is the expected one: models are pairs M, e , where M = (W, S) is a similarity space, e is an evaluation that maps propositional formulas into subsets of W , interpreting ∧, ∨, ¬ by set intersection, union and complementation, respectively. Given a similarity space M , the satisfaction of a formula by an evaluation e is inductively defined as follows. For graded implications, one defines: In the finitary case, i.e., when the propositional formulas are built up from a finite set of propositional variables, the logic LAE defined in [7] is the system consisting of the following axioms and rule: Here, m.e.c. means maximal elementary conjunction, i.e., a conjunction where every propositional variable appears, either in positive or negative form. It turns out that, as proved in [7] , this axiomatic system provides a sound and complete axiomatisation of the semantic |= LAE .

In [16, 17] , we have proposed a simplified proof system for a variant of LAE. Namely, we have focused on the case of ⊗-similarity relations, where ⊗ is the product t-norm. The concept of a m.e.c., which occurs in axioms (A8) and (A9) and plays an essential role in the above approach, could be dropped. The notion of an α-neighbourhood of a set A is in this context to be slightly adapted: 

A proposition Φ is valid in the logic of approximate entailment based on the product t-norm if and only if Φ is provable by means of the indicated axioms and rule.

The proof of this completeness theorem is involved and consists of two parts. In [16] , we have shown a similar statement but without the assumption that the similarity relation is symmetric, and we have represented proofs by weighted directed forests. In [17] , we have established that spaces based on a possibly non-symmetric similarity relation can, in a certain sense, be embedded into a space based on a similarity relation in the usual sense. Both results combined lead to the completeness theorem mentioned.

The logic LAE has been further developed in a different direction in [18] to account for additional nice features that the approximate entailment has when assuming the language talks about properties on (products of) linearly ordered domains.

Finally, it is worth mentioning that similar syntactical characterisations for strong and proximity entailments can be envisaged. Indeed, in [7] a logic of graded strong entailment, called LSE, is introduced by considering similar graded conditionals ϕ α ψ with the following semantics:

M, e |= ϕ α ψ if U α (e(ϕ)) ⊆ e(ψ),

As for the proximity entailment, in [8] a corresponding logic with graded conditionals ϕ α ψ is also introduced with a somewhat more involved semantics:

M, e |= ϕ α ψ if ∀β : U β (e(ϕ)) ⊆ U α⊗β (e(ψ)).

In his original work, Ruspini mentions the use of modal concepts to explain his similarity-based possibilistic structures but he never studied in detail the underlying modal logics. In fact, this was done in Rodriguez's PhD thesis [12] following his suggestion, and also reported in [4, 5, 8, 9] . In this section we want to summarise the main results which appear there. According to Ruspini's intuition, it makes sense to consider a modal approach to similarity-based reasoning based on Kripke structures of the form This defines, in fact, a multi-modal logical framework (with as many modalities as level cuts of the similarity relations). Such a multimodal logic setting is systematically developed in [5] .

Note that, if W is the set of classical interpretations of a propositional language L, then the above notion of modal satisfiability for the possibility operators ♦ α captures precisely the notion of approximate satisfiability considered in Sect. 2, in the sense that, for any non-modal proposition p, (M, w) |= ♦ α p holds iff w |= α S p holds. Moreover, as already intuitively pointed out by Ruspini in [13] , the approximate entailment p |= α S q can also be captured by the formula

in the sense that p |= α S q holds iff p → ♦ α q is valid in M = (W, S, e). Analogously, the strong entailment p | ≈ α S q can be captured by the formula ♦ α p → q.

A logical approach to interpolation based on similarity relations

Handbook of Logic in Artificial Intelligence and Logic Programming

On conditioning in similarity logic

About similarity-based logical systems

A modal account of similaritybased reasoning

On similarity logic and the generalized modus ponens

Logics for approximate and strong entailment

Logical approaches to fuzzy similarity-based reasoning: an overview

A fuzzy modal logic for similarity reasoning

Indistinguishability Operators: Modelling Fuzzy Equalities and Fuzzy Equivalence Relations

Aspectos formales en el Razonamiento basado en Relaciones de Similitud Borrosas

On the semantics of fuzzy logic

A logic-based view of similarities and preferences

Assaig sobre les relacions d'indistingibilitat. Actes del Congrés Català de Lògica

Logic of approximate entailment in quasimetric spaces

Logic of approximate entailment in quasimetric and in metric spaces

Logics for approximate entailment in ordered universes of discourse

A theory of approximate reasoning

Acknowledgments. Esteva 

As for the proximity entailments |≡ α S , recall that p |≡ α S q holds iff for all w ∈ W and for all β, w |= β S p implies w |= α⊗β S q. Therefore, it cannot be represented in the multi-modal framework unless the similarity relations are forced to have a fixed, predefined set G of finitely-many different levels, say {0, 1} ⊆ G ⊂ [0, 1]. In that case, the validity of the formulaObviously, when G is not finite, for instance when G = [0, 1], this representation is not suitable any longer. However, the underlying modal logic can still be formalised by introducing further modal operators accounting for the open cuts of the similarty relation in the models, that is considering the operators ♦ c α and ♦ o α for each rational α ∈ G ∩ Q with the following semantics:Obviously, when G is finite, ♦ c α and ♦ o α are interdefinable. In any case, different multimodal systems can be axiomatized as it is shown in [5, 8] .

This paper contains a brief summary of some developments in the research field of similarity-based approximate reasoning models and their logical formalisations, where Ruspini's inspiring ideas have been very fruitful and decisive. It is our humble homage to Enrique, an excellent researcher and even better person. The authors are very grateful to him to have had the chance to enjoy his friendship and shared with him many interesting scientific discussions.