On Cautiousness and Expressiveness in Interval-Valued Logic

Abstract

In this paper, we study how cautious conclusions should be taken when considering interval-valued propositional logic, that is logic where to each formula is associated a real-valued interval providing imprecise information about the penalty incurred for falsifying this formula. We work under the general assumption that the weights of falsified formulas are aggregated through a non-decreasing commutative function, and that an interpretation is all the more plausible as it is less penalized. We then formulate some dominance notions, as well as properties that such notions should follow if we want to draw conclusions that are at the same time informative and cautious. We then discuss the dominance notions in light of such properties.

1 Introduction

Logical frameworks have always played an important role in artificial intelligence, and adding weights to logical formulas allow one to deal with a variety of problems with which classical logic struggles [3].

Usually, such weights are assumed to be precisely given, and associated to an aggregation function, such as the maximum in possibilistic logic [4] or the sum in penalty logic [5]. These approaches can typically find applications in non-monotonic reasoning [1] or preference handling [7].

However, as providing specific weights to each formula is likely to be a cognitively demanding tasks, many authors have considered extensions of these frameworks to interval-valued weights [2, 6], where intervals are assumed to contain the true, ill-known weights. Such approaches can also be used, for instance, to check how robust conclusions obtained with precise weights are.

In this paper, we are interested in making cautious or robust inferences in such interval-valued frameworks. That is, we look for inference tools that will typically result in a partial order over the interpretations or world states, such that any preference statement made by this partial order is made in a skeptic way, i.e., it holds for any replacement of the weights by precise ones within the intervals, and should not be reversed when gaining more information. We simply assume that the weights are positive and aggregated by a quite generic function, meaning that we include for instance possibilistic and penalty logics as special cases.

We provide the necessary notations and basic material in Sect. 2. In Sect. 3, we introduce different ways to obtain partial orders over interpretations, and discuss different properties that corresponding cautious inference tools could or should satisfy. Namely, that reducing the intervals will provide more informative and non-contradictory inferences, and that if an interpretation falsify a subset of formulas falsified by another one, then it should be at least as good as this latter one. Section 4 shows which of the introduced inference tools satisfy which property.

2 Preliminaries

We consider a finite propositional language $\mathcal {L}$. We denote by ${\varOmega }$ the space of all interpretations of $\mathcal {L}$, and by ${\omega }$ an element of ${\varOmega }$. Given a formula ${\phi }$, ${\omega }$ is a model of ${\phi }$ if it satisfies it, denoted ${\omega }\models {\phi }$.

A weighted formula is a tuple ${\langle {\phi }_{}, {\alpha }_{} \rangle }$ where ${\alpha }$ represents the importance of the rule, and the penalty incurred if it is not satisfied. This weight may be understood in various ways: as a degree of certainty, as a degree of importance of an individual preference, .... We assume that ${\alpha }$ take their values on an interval of ${\mathbb {R}}^+$, possibly extended to include $\infty$ (e.g., to represent formulas that cannot be falsified). In this paper, a formula with ${\alpha }=0$ is understood as a totally unimportant formula that can be ignored, while a formula with maximal ${\alpha }$ is a formula that must be satisfied.

A (precisely) weighted knowledge base ${K}={\{{\langle {\phi }_{i}, {\alpha }_{i} \rangle }:i=1,\ldots ,n\}}$ is a set of distinct weighted formulas. Since these formulas are weighted, an interpretation can (and sometimes must, if ${K}$ without weights is inconsistent) falsify some of them, and still be considered as valid. In order to determine an ordering between different interpretations, we introduce two new notations:

• $F_{K}({\omega })={\{{\phi }_i: {\omega }\not \models {\phi }_i\}}$, the set of formulas falsified by ${\omega }$

• $F_{K}({\omega }\setminus {\omega }')={\{{\phi }_i:{\omega }\not \models {\phi }_i \wedge {\omega }' \models {\phi }_i\}}$

Let us furthermore consider an aggregation function $ag: {\mathbb {R}}^n \rightarrow {\mathbb {R}}$ that we assume to be non-decreasing, commutative, continuous and well-defined¹ for any finite number n.

We consider that $ag({\{{\alpha }_i:{\phi }_i \in F\}})$ applied to a subset F of formulas of ${K}$ measure the overall penalty corresponding to F, with $ag(\emptyset )=0$. Given this, we also assume that if ag receives two vectors $\varvec{a}$ and $\varvec{b}$ of dimensions n and $n+m$ such that $\varvec{b}$ has the same first n elements as $\varvec{a}$, i.e., $\varvec{b}=(\varvec{a},y_1,\ldots ,y_m)$, then $ag(\varvec{a}) \le ag(\varvec{b})$. The idea here is that adding (falsified) formulas to $\varvec{a}$ can only increase the global penalty. Classical options correspond to possibilistic logic (weights are in [0, 1] and $ag=\max$) or penalty logic (weights are positive reals and $ag=\sum$). Based on this aggregation function, we define a given ${K}$ the two following complete orderings between interpretations when weights are precise:

• ${\omega }\succeq ^K_{All} {\omega }'$ iff $ag({\{{\alpha }_i:{\phi }_i \in F_{K}({\omega })\}}) \le ag({\{{\alpha }_i:{\phi }_i \in F_{K}({\omega }')\}})$.

• ${\omega }\succeq ^K_{Diff} {\omega }'$ iff $ag({\{{\alpha }_i:{\phi }_i \in F_{K}({\omega }\setminus {\omega }')\}}) \le ag({\{{\alpha }_i:{\phi }_i \in F_{K}({\omega }' \setminus {\omega })\}})$.

Both orderings can be read as ${\omega }\succeq {\omega }'$ meaning that “${\omega }$ is more plausible, or preferred to ${\omega }'$, given ${K}$”.

When the weights are precise, it may be desirable for $\succeq _{All}$ and $\succeq _{Diff}$ to be consistent, that is not to have ${\omega }\succ ^{K}_{All} {\omega }'$ and ${\omega }\prec ^{K}_{Diff} {\omega }'$ for a given ${K}$. It may be hard to characterize the exact family of functions ag that will satisfy this, but we can show that adding associativity and strict increasigness² to the other mentioned properties ensure that results will be consistent.

Proposition 1

If ag is continuous, commutative, strictly increasing and associative, then given a knowledge base ${K}$, we have that

$${\omega }\succeq ^{K}_{All} {\omega }' \Leftrightarrow {\omega }\succeq ^{K}_{Diff} {\omega }' $$

Proof

Let us denote the sets ${\{{\alpha }_i:{\phi }_i \in F_{K}({\omega })\}}$ and ${\{{\alpha }_i:{\phi }_i \in F_{K}({\omega }')\}}$ as real-valued vectors $\varvec{a}=(x_1,\ldots ,x_n, y_{n+1}, \ldots , y_{n_a})$ and $\varvec{b}=(x_1,\ldots ,x_n, z_{n+1}, \ldots ,$ $z_{n_b})$, where $x_1,\ldots ,x_n$ are the weights associated to the formulas that both interpretations falsify. Showing the equivalence of Proposition 1 then comes down to show

$$ag(\varvec{a}) \ge ag(\varvec{b}) \Leftrightarrow ag((y_{n+1}, \ldots ,y_{n_a})) \ge ag((z_{n+1}, \ldots ,z_{n_b})).$$

Let us first remark that, due to associativity,

$$ag(\varvec{a})=ag(ag((x_1,\ldots ,x_n)),ag((y_{n+1}, \ldots ,y_{n_a}))):=ag(A,B),$$

$$ag(\varvec{b})=ag(ag((x_1,\ldots ,x_n)),ag((z_{n+1}, \ldots ,z_{n_b}))):=ag(A,C).$$

Under these notations, we must show that $ag(A,B) \ge ag(A,C) \Leftrightarrow B \ge C$.

That $B \ge C \Rightarrow ag(A,B) \ge ag(A,C)$ is immediate, as ag is non-decreasing. To show that $B \ge C\Leftarrow ag(A,B) \ge ag(A,C)$, we can just see that if $B < C$, we have $ag(A,B) < ag(A,C)$ due to the strict increasingness of ag.

3 Interval-Valued Logic, Dominance Notions and Properties

In practice, it is a strong requirement to ask users to provide precise weights for each formula, and they may be more comfortable in providing imprecise ones. This is one of the reason why researchers proposed to extend weighted logics to interval-valued logics, where the knowledge base is assumed to have the form ${K}={\{{\langle {\phi }_{i}, {I_{i}}\rangle }:i=1,\ldots ,n\}}$ with ${I_{i}}=[a_i,b_i]$ representing an interval of possible weights assigned to ${\phi }_i$.

In practice, this means that the result of applying ag to a set of formulas F is no longer a precise value, but an interval $[\underline{ag},\overline{ag}]$. As ag is a non-decreasing continuous function, computing this interval is quite easy as

$$\underline{ag}=\underline{ag}(\{a_i|\phi _i \in F \}), $$

$$\overline{ag}=\overline{ag}(\{b_i|\phi _i \in F \}),$$

which means that if the problem with precise weights is easy to solve, then solving it for interval-valued weights is equally easy, as it amounts to solve twice the problems for specific precise weights (i.e., the lower and upper bounds). A question is now to know how we should rank the various interpretations in a cautious way given these interval-valued formulas. In particular, this means that the resulting order between interpretations should be a partial order if we have no way to know whether one has a higher score than the other, given our imprecise information. But at the same time, we should try to not lose too much information by making things imprecise.

There are two classical ways to compare interval-valued scores that results in possible incomparabilities:

• Lattice ordering: $[a,b] \preceq _L [c,d]$ iff $a \le c$ and $b\le d$. We then have $[a,b] \prec _L [c,d]$ if one of the two inequalities is strict, and $[a,b] \simeq [c,d]$ iff $[a,b]=[c,d]$. Incomparability of [a, b] and [c, d] corresponds to one of the two set being strictly included in the other.

• Strict ordering: $[a,b] \preceq _S [c,d]$ iff $b \le c$. We then have $[a,b] \prec _S [c,d]$ if $b < c$, and indifference will only happen when $a=b=c=d$ (hence never if intervals are non-degenerate). Incomparability of [a, b] and [c, d] corresponds to the two sets overlapping.

These two orderings can then be applied either to $\succeq _{All}$ or $\succeq _{Diff}$, resulting in four different extensions: $\succeq _{All,L}, \succeq _{All,S}, \succeq _{Diff,L}, \succeq _{Diff,S}$. A first remark is that strict comparisons are stronger than lattice ones, as the former imply the latter, that is if $[a,b] \preceq _S [c,d]$, then $[a,b] \preceq _L [c,d]$. In order to decide which of these orderings are the most adequate, let us first propose some properties they should follow when one wants to perform cautious inferences.

Property 1

(Informational monotonicity). Assume that we have two knowledge bases ${K}^1={\{\langle {\phi }^1_i, {I_{i}}^1 \rangle :i=1,\ldots ,n\}}$ and ${K}^2={\{\langle {\phi }^2_i, {I_{i}}^2 \rangle :i=1,\ldots ,n\}}$ with ${\phi }_i^1={\phi }_i^2$ and ${I_{i}}^1 \subseteq {I_{i}}^2$ for all i. An aggregation method and the partial order $\succ$ it induces on interpretations is informational monotonic if

$${\omega }\succ ^{{K}_2} {\omega }' \implies {\omega }\succ ^{{K}_1} {\omega }'$$

That is, the more we gain information, the better we become at differentiating and ranking interpretations. If ${\omega }$ is strictly preferred to ${\omega }'$ before getting more precise assessments, it should remain so after the assessments become more precise³. A direct consequence of Property 1 is that we cannot have ${\omega }\succ ^{{K}_2} {\omega }'$ and ${\omega }' \succ ^{{K}_1} {\omega }$, meaning that $\succ ^{{K}_1}$ will be a refinement of $\succ ^{{K}_2}$. This makes sense if we aim for a cautious behaviour, as the conclusion we make in terms of preferred interpretations should be guaranteed, i.e., they should not be revised when we become more precise.

It should also be noted that violating this property means that the corresponding partial order is not skeptic in the sense advocated in the introduction, as a conclusion taken at an earlier step can be contradicted later on by gaining more information.

Property 2

(subset/implication monotonicity). Assume that we have a knowledge base ${K}$. An aggregation method and the partial order $\succ$ it induces on interpretations follows subset monotonicity if

$$F_{K}({\omega }) \subseteq F_{K}({\omega }') \implies {\omega }\succeq ^{K}{\omega }' \text { for any pair } {\omega },{\omega }'$$

This principle is quite intuitive: if we are sure that ${\omega }'$ falsifies the same formulas than ${\omega }$ in addition to some others, then certainly ${\omega }'$ should be less preferable/certain than ${\omega }$.

4 Discussing Dominance Notions

Let us now discuss the different partial orders in light of these properties, starting with the lattice orderings and then proceeding to interval orderings.

4.1 Lattice Orderings

Let us first show that $\succeq _{All,L}, \succeq _{Diff,L}$ do not satisfy Property 1 in general, by considering the following example:

Example 1

Consider the case where $a_i,b_i \in \mathbb {R}$ and $ag=\sum$, with the following knowledge base on the propositional variables $\{p,q\}$

$$\phi _1=p, \quad \phi _2=p\wedge q, \quad \phi _3=\lnot q $$

with the three following sets (respectively denoted ${K}^1,{K}^2,{K}^3$) of interval-valued scores

$$\begin{aligned} \begin{array}{r@{}r@{}r} I_1^{{K}_1}=[2.5,2.5], &{} I_2^{{K}_1}=[0,4], &{} I_3^{{K}_1}=[1,5], \\ I_1^{{K}_2}=[2.5,2.5], &{} I_2^{{K}_2}=[4,4], &{} I_3^{{K}_2}=[1,5],\\ I_1^{{K}_3}=[2.5,2.5], &{} I_2^{{K}_3}=[4,4], &{} I_3^{{K}_3}=[1,1], \end{array} \end{aligned}$$

that are such that $I^{{K}_3} \subseteq I^{{K}_2} \subseteq I^{{K}_1}$ for all formulas. The resulting scores using the choice $\succeq _{All}$ following on the different interpretations are summarised in Table 1.

Table 1. Interval-valued scores from Example 1

Figure 1 shows the different partial orders between the interpretations, according to $\succeq _{All,L}$. We can see that ${\omega }_2$ and ${\omega }_3$ go from comparable to incomparable when going from $\succ ^{{K}_1}_{All,L}$ to $\succ ^{{K}_2}_{All,L}$, and that the preference or ranking between them is even reversed when going from $\succ ^{{K}_1}_{All,L}$ to $\succ ^{{K}_3}_{All,L}$.

Fig. 1.

Orderings $\succ _{All,L}$ of Example 1 on interpretations.

It should be noted that what happens to ${\omega }_2,{\omega }_3$ for $\succeq _{All,L}$ is also true for $\succeq _{Diff,L}$. Indeed, $F_K({\omega }_2)=\{p \cap q\}$ and $F_K({\omega }_3)=\{\lnot q\}$, hence $F_K({\omega }_2 \setminus {\omega }_3)=F_K({\omega }_2)$ and $F_K({\omega }_3 \setminus {\omega }_2)=\emptyset$. However, we can show that the two orderings based on lattice do satisfy subset monotonicity.

Proposition 2

Given a knowledge base K, the two orderings $\succeq ^{K}_{All,L}, \succeq ^{K}_{Diff,L}$ satisfy subset monotonicity.

Proof

For $\succeq _{Diff,L}$, it is sufficient to notice that if $F_{K}({\omega }) \subseteq F_{K}({\omega }')$, then $F_{K}({\omega }\setminus {\omega }')=F_{K}(\emptyset )$. This means that $ag({\{{\alpha }_i:{\phi }_i \in F_{K}({\omega }\setminus {\omega }')\}})=[0,0]$, hence we necessarily have ${\omega }\succeq ^{K}_{Diff,L} {\omega }'$.

For $\succeq _{All,L}$, the fact that $F_{K}({\omega }) \subseteq F_{K}({\omega }')$ means that the vectors $\varvec{a}$ and $\varvec{a}'$ of lower values associated to ${\{{\alpha }_i:{\phi }_i \in F_{K}({\omega })\}}$ and ${\{{\alpha }_i:{\phi }_i \in F_{K}( {\omega }')\}}$ will be of the kind $\varvec{a'}=(\varvec{a},a_1,\ldots ,a_m),$ hence we will have $\underline{ag}(\varvec{a}) \le \underline{ag}(\varvec{a'})$. The same reasoning applied to upper bounds means that we will also have $\overline{ag}(\varvec{a}) \le \overline{ag}(\varvec{a'})$, meaning that ${\omega }\succeq ^{K}_{All,L} {\omega }'$.

From this, we deduce that lattice orderings will tend to be too informative for our purpose⁴, i.e., they will induce preferences between interpretations that should be absent if we want to make only those inferences that are guaranteed (i.e., hold whatever the value chosen within the intervals ${I_{i}}$).

4.2 Strict Orderings

In this section, we will study strict orderings, and will show in particular that while $\succeq _{All,S}$ provides orderings that are not informative enough for our purpose, $\succeq _{Diff,S}$ does satisfy our two properties.

As we did for lattice orderings, let us first focus on the notion of informational monotonicity, and show that both orderings satisfy it.

Proposition 3

Given knowledge bases $K^1,K^2$ with $\phi _i^1=\phi _i^2$ and ${I_{i}}^1 \subseteq {I_{i}}^2$ for all $i \in \{1,\ldots ,n\}$, the two orderings $\succeq _{All,S}, \succeq _{Diff,S}$ satisfy information monotonicity.

Proof

Assume that [a, b] and [c, d] are the intervals obtained from ${K}^2$ respectively for ${\omega }$ and ${\omega }'$ after aggregation has been performed, with $b \le c$, hence ${\omega }\succeq ^{{K}_2}_{\ell ,S} {\omega }'$ with $\ell \in \{All,Diff\}$.

Since ag is an increasing function, and as ${I_{i}}^1 \subseteq {I_{i}}^2$, we will have that the intervals $[a',b']$ and $[c',d']$ obtained from ${K}^1$ for ${\omega }$ and ${\omega }'$ after aggregation will be such that $[a',b'] \subseteq [a,b]$ and $[c',d'] \subseteq [c,d]$, meaning that $b' \le b \le c \le c'$, hence ${\omega }\succeq ^{{K}_1}_{\ell ,S} {\omega }'$, and this finishes the proof.

Let us now look at the property of subset monotonicity. From the knowledge base ${K}^1$ in Example 1, one can immediately see that $\succeq _{All,S}$ is not subset monotonic, as $F_{K}({\omega }_3) \subseteq F_{K}({\omega }_1)$ and $F_{K}({\omega }_2) \subseteq F_{K}({\omega }_0) \subseteq F_{K}({\omega }_1)$, yet all intervals in Table 1 overlap, meaning that all interpretations are incomparable. Hence $\succeq _{All,S}$ will usually not be as informative as we would like a cautious ranking procedure to be. This is mainly due to the presence of redundant variables, or common formulas, in the comparison of interpretations. In contrast, $\succeq _{Diff,S}$ does not suffer from the same defect, as the next proposition shows.

Proposition 4

Given a knowledge base ${K}$, the ordering $\succeq _{Diff,S}$ satisfies subset monotonicity.

Proof

As for Proposition 2, it is sufficient to notice that if $F_{K}({\omega }) \subseteq F_{K}({\omega }')$, then $F_{K}({\omega }\setminus {\omega }')=F_{K}(\emptyset )$. This means that $ag({\{{\alpha }_i:{\phi }_i \in F_{K}({\omega }\setminus {\omega }')\}})=[0,0]$, hence we necessarily have ${\omega }\succeq ^{K}_{Diff,L} {\omega }'$.

Hence, the ordering $\succeq _{Diff,S}$ satisfies all properties we have considered desirable in our framework. It does not add unwanted comparisons, while not losing information that could be deduced without knowing the weights.

Example 2

If we consider the knowledge base ${K}^1$ of Example 1, using $\succeq _{Diff,S}$ we could only deduce the rankings induced by the facts that $F_{K}({\omega }_3) \subseteq F_{K}({\omega }_1)$ and $F_{K}({\omega }_2) \subseteq F_{K}({\omega }_0) \subseteq F_{K}({\omega }_1)$, as ${\omega }_3$ does not falsify any of the formulas that ${\omega }_2$ and ${\omega }_0$ falsify, hence we can directly compare their intervals. The resulting ordering is pictured in Fig. 2.

Fig. 2.

Orderings $\succ _{Diff,S}$ of Example 2

5 Conclusions

In this paper, we have looked at the problem of making cautious inferences in weighted logics when weights are interval-valued, and have made first proposals to make such inferences. There is of course a lot that remains to be done, such as studying expressivity, representational or computational issues.

It should also be noted that our approach can easily be extended to cases where weights are given by other uncertainty models. If $\mathcal {I}_i$ is an uncertain quantity (modelled by a fuzzy set, a belief function, a probability, ...), we would then need to specify how to propagate them to obtain ag(F), and how to compare these uncertain quantities.