Salem Benferhat

LPAR Conference 2023 Conference Paper

Syntactic computation of Fagin-Halpern conditioning in possibility theory

• Omar Ettarguy
• Ahlame Begdouri
• Salem Benferhat
• Carole Delenne

Conditioning plays an important role in revising uncertain information in light of new evidence. This work focuses on the study of Fagin and Halpern (FH-)conditioning in the context where uncertain information is represented by weighted or possibilistic belief bases. Weighted belief bases are extensions of classical logic belief bases where a weight or degree of belief is associated with each propositional logic formula. This paper proposes a characterization of a syntactic computation of the revision of weighted belief bases (in the light of new information) which is in full agreement with the semantics of the FH- conditioning of possibilistic distributions. We show that the size of the revised belief base is linear with respect to the size of the initial base and that the computational complexity amounts to performing O(log2(n)) calls to the propositional logic satisfiability tests, where n is the number of different degrees of certainty used in the initial belief base.

JELIA Conference 2023 Conference Paper

Tractable Closure-Based Possibilistic Repair for Partially Ordered DL-Lite Ontologies

• Ahmed Laouar
• Sihem Belabbes
• Salem Benferhat

Abstract Inconsistency in formal ontologies is usually addressed by computing repairs for the dataset. There are several strategies for selecting the repairs used to evaluate queries, with various levels of cautiousness and classes of computational complexity. This paper deals with inconsistent partially ordered lightweight ontologies. It introduces a new method that goes beyond the cautious strategies and that is tractable in the possibilistic setting, where uncertainty concerns only the data pieces. The proposed method, called C \(\pi \) -repair, proceeds as follows. It first interprets the partially ordered dataset as a family of totally ordered datasets. Then, it computes a single data repair for every totally ordered possibilistic ontology induced from the partially ordered possibilistic ontology. Next, it deductively closes each of these repairs in order to increase their productivity, without introducing conflicts or arbitrary data pieces. Finally, it intersects the closed repairs to obtain a single data repair for the initial ontology. The main contribution of this paper is an equivalent characterization that does not enumerate all the total orders, but also does not suffer from the additional computational cost naturally incurred by the deductive closure. We establish the tractability of our method by reformulating the problem using the notions of dominance and support. Intuitively, the valid conclusions are supported against conflicts by consistent inclusion-minimal subsets of the dataset that dominate all the conflicts. We also study the rationality properties of our method in terms of unconditional and conditional query-answering.

KR Conference 2016 Short Paper

A General Modifier-based Framework for Inconsistency-Tolerant Query Answering

• Jean-Francois Baget
• Salem Benferhat
• Zied Bouraoui
• Madalina Croitoru
• Mugnier Marie-Laure
• Odile Papini
• Swan Rocher
• Karim Tabia

We propose a general framework for inconsistency-tolerant query answering within existential rule setting. This framework unifies the main semantics proposed by the state of art and introduces new ones based on cardinality and majority principles. It relies on two key notions: modifiers and inference strategies. An inconsistency-tolerant semantics is seen as a composite modifier plus an inference strategy. We compare the obtained semantics from a productivity point of view. Preliminaries We consider first-order logical languages without functional symbols, hence a term is a variable or a constant. In the following, by query, we mean a Boolean conjunctive query, i. e., an existentially quantified conjunction of atoms (note that more general kinds of queries could be considered). Given a set of facts A (atoms without variables) and a query q, the answer to q over A is yes iff A|=q, where |= denotes standard entailment. A knowledge base can be seen as a database enhanced with an ontological component. Since inconsistency-tolerant query answering has been mostly studied in the context of description logics (DLs), and especially DL-Lite, we will use some DL vocabulary, like ABox for the data and TBox for the ontology. However, our framework is not restricted to DLs, hence we define TBoxes and ABoxes in terms of firstorder logic. We assume the reader familiar with the basics of DLs and their logical translation. An ABox is a set of assertions. As a special case we have DL assertions restricted to unary and binary predicates. A positive axiom is of the form ∀x∀y(B[x, y]→∃z H[y, z]) where B and H are conjunctions of atoms (in other words, it is a positive existential rule). As a special case, we have for instance concept and role inclusions in DL-LiteR, which are respectively of the form B1 B2 and S1 S2, where Bi: =A|∃S and Si: =P |P − (with A an atomic concept, P an atomic role and P − the inverse of an atomic role). A negative axiom is of the form ∀x(B[x]→⊥) where B is a conjunction of atoms (in other words, it is a negative constraint). As a special case, we have for instance disjointness axioms in DL-LiteR, which are of the form B1 ¬B2 and S1 ¬S2. A TBox T =Tp ∪Tn is partitioned into a set Tp of positive axioms and a set Tn of negative axioms. A knowledge base (KB) is of the form K=T, A where A is an ABox and T is a TBox. K is said to be consistent if T ∪A is satisfiable, otherwise it is said to be inconsistent. We also say that A is (in)consistent (with T), which reflects the assumption that T is reliable. The answer

JELIA Conference 2016 Conference Paper

Inconsistency-Tolerant Query Answering: Rationality Properties and Computational Complexity Analysis

• Jean-François Baget
• Salem Benferhat
• Zied Bouraoui
• Madalina Croitoru
• Marie-Laure Mugnier
• Odile Papini
• Swan Rocher
• Karim Tabia

Abstract Generalising the state of the art, an inconsistency-tolerant semantics can be seen as a couple composed of a modifier operator and an inference strategy. In this paper we deepen the analysis of such general setting and focus on two aspects. First, we investigate the rationality properties of such semantics for existential rule knowledge bases. Second, we unfold the broad landscape of complexity results of inconsistency-tolerant semantics under a specific (yet expressive) subclass of existential rules.

IJCAI Conference 2016 Conference Paper

Non-Objection Inference for Inconsistency-Tolerant Query Answering

• Salem Benferhat
• Zied Bouraoui
• Madalina Croitoru
• Odile Papini
• Karim Tabia

Repair based techniques are a standard way of dealing with inconsistency in the context of ontology based data access. We propose a novel non-objection inference relation (along with its variants) where a query is considered as valid if it follows from at least one repair and it is consistent with all the repairs. These inferences are strictly more productive than universal inference while preserving the consistency of its set of conclusions. We study the productivity and properties of the new inferences. We also give experimental results of the proposed non-objection inference.

ECAI Conference 2016 Conference Paper

Set-Valued Conditioning in a Possibility Theory Setting

• Salem Benferhat
• Amélie Levray
• Karim Tabia
• Vladik Kreinovich

Possibilistic logic is a well-known framework for dealing with uncertainty and reasoning under inconsistent or prioritized knowledge bases. This paper deals with conditioning uncertain information where the weights associated with formulas are in the form of sets of uncertainty degrees. The first part of the paper studies set-valued possibility theory where we provide a characterization of set-valued possibilistic logic bases and set-valued possibility distributions by means of the concepts of compatible possibilistic logic bases and compatible possibility distributions respectively. The second part of the paper addresses conditioning set-valued possibility distributions. We first propose a set of three natural postulates for conditioning set-valued possibility distributions. We then show that any set-valued conditioning satisfying these three postulates is necessarily based on conditioning the set of compatible standard possibility distributions. The last part of the paper shows how one can efficiently compute set-valued conditioning over possibilistic knowledge bases.

IJCAI Conference 2015 Conference Paper

Compatible-Based Conditioning in Interval-Based Possibilistic Logic

• Salem Benferhat
• Am
• eacute; lie Levray
• Karim Tabia
• Vladik Kreinovich

Interval-based possibilistic logic is a flexible setting extending standard possibilistic logic such that each logical expression is associated with a sub-interval of [0, 1]. This paper focuses on the fundamental issue of conditioning in the interval-based possibilistic setting. The first part of the paper first proposes a set of natural properties that an interval-based conditioning operator should satisfy. We then give a natural and safe definition for conditioning an interval-based possibility distribution. This definition is based on applying standard min-based or product-based conditioning on the set of all associated compatible possibility distributions. We analyze the obtained posterior distributions and provide a precise characterization of lower and upper endpoints of the intervals associated with interpretations. The second part of the paper provides an equivalent syntactic computation of interval-based conditioning when interval-based distributions are compactly encoded by means of interval-based possibilistic knowledge bases. We show that intervalbased conditioning is achieved without extra computational cost comparing to conditioning standard possibilistic knowledge bases.

IJCAI Conference 2015 Conference Paper

How to Select One Preferred Assertional-Based Repair from Inconsistent and Prioritized DL-Lite Knowledge Bases?

• Salem Benferhat
• Zied Bouraoui
• Karim Tabia

Managing inconsistency in DL-Lite knowledge bases where the assertional base is prioritized is a crucial problem in many applications. This is especially true when the assertions are provided by multiple sources having different reliability levels. This paper first reviews existing approaches for selecting preferred repairs. It then focuses on suitable strategies for handling inconsistency in DL-Lite knowledge bases. It proposes new approaches based on the selection of only one preferred repair. These strategies have as a starting point the so-called nondefeated repair and add one of the following principles: deductive closure, consistency, cardinality and priorities. Lastly, we provide a comparative analysis followed by an experimental evaluation of the studied approaches.

JELIA Conference 2014 Conference Paper

A Prioritized Assertional-Based Revision for DL-Lite Knowledge Bases

• Salem Benferhat
• Zied Bouraoui
• Odile Papini
• Éric Würbel

Abstract DL-Lite is a powerful and tractable family of description logics. One of the fundamental issue in this area is the evolution or revision of knowledge bases. To this end, many approaches are recently developed for revising flat DL-Lite knowledge bases. This paper investigates “Prioritized Removed Sets Revision” (PRSR) in DL-Lite framework where the assertions or data are prioritized (for instance in case where the data are provided by multiple sources having different reliability levels). PRSR approach is based on inconsistency minimization in order to restore consistency where the minimality refers to the lexicographic criterion and not to the set inclusion one. We study different forms of incorporated information: an assertion, a positive inclusion axiom or a negative inclusion axiom. We show that under some conditions PRSR can be achieved in polynomial time. We give logical properties of the proposed operators in terms of satisfaction of Hansson’s postulates rephrased in DL-Lite framework. We finally show how to use the notion of hitting sets for computing prioritized removed sets.

ECAI Conference 2014 Conference Paper

Analysis of interval-based possibilistic networks

• Salem Benferhat
• Sylvain Lagrue
• Karim Tabia

This paper proposes interval-based possibilistic networks. This extension allows to compactly encode and reason with epistemic uncertainty and imprecise beliefs as well as with multiple expert knowledge. We propose a natural semantics based on compatible possibilistic networks. The paper shows finally that computing uncertainty bounds of an event can be done in interval-based networks without extra computational cost.

ECAI Conference 2014 Conference Paper

Assertional-based Prioritized Removed Sets Revision of DL-LiteR Knowledge Bases

• Salem Benferhat
• Zied Bouraoui
• Odile Papini
• Éric Würbel

The paper proposes an extension of "Prioritized Removed Sets Revision" (PRSR) to DL-LiteRstratified knowledge bases. The revision strategy is based on inconsistency minimization and consists in determining smallest subsets of assertions to be dropped from the current DL-LiteRknowledge base, taking the stratification into account, in order to restore consistency and accept the input. We consider different forms of input: membership assertion, positive inclusion axiom or negative inclusion axiom. We show that according to the form of input and under some conditions PRSR can be achieved in polynomial time.

ECAI Conference 2014 Conference Paper

Post-processing a classifier's predictions: Strategies and empirical evaluation

• Salem Benferhat
• Karim Tabia
• Mouaad Kezih
• Mahmoud Taibi

In this paper, we propose an approach allowing to revise the outputs of a classifier in order to take into account the available domain knowledge. This approach can be applied for any classifier be it probabilistic or not. We propose post-processing criteria and methods to encode and exploit different kinds of domain knowledge. Finally, we provide experimental studies on a set of benchmarks.

KR Conference 2014 Conference Paper

Reasoning with uncertain inputs in possibilistic networks

• Salem Benferhat
• Karim Tabia

In the possibilistic setting, the counterparts of Jeffrey’s rule are proposed in (Dubois and Prade 1997)(Dubois and Prade 1993). In (Benferhat, Tabia, and Sedki 2011), we studied the existence and the uniqueness of the solution in both the quantitative and qualitative possibilistic settings. The possibilistic counterpart of Jeffrey’s rule is investigated for belief revision in possibilistic knowledge bases in (Benferhat et al. 2010) where it is claimed that this rule can successfully recover most of the belief revision kinds such as the natural belief revision, drastic belief revision, reinforcement, etc. In (Benferhat, Da Costa Pereira, and Tettamanzi 2013), a syntactic version is proposed for the possibilistic counterpart of Jeffrey’s rule. In this paper, we address revising the beliefs encoded by means of possibilistic networks with uncertain inputs. More precisely, the paper provides • Possibilistic counterparts of Pearl’s method of virtual evidence and its generalization named the virtual evidence method in both the quantitative and qualitative settings. Unlike the probabilistic and quantitative possibilistic settings, the inputs for the qualitative counterparts of Pearl’s methods should be possibility degrees because of the definition of the qualitative conditioning. • An analysis of the existence and uniqueness of the solutions using the proposed possibilistic counterparts of Pearl’s methods. • Transformations from Jeffrey’s rule to the virtual evidence method and vice versa and comparisons of these methods in both the quantitative and qualitative settings. As in the probabilistic setting, the two methods are shown to be equivalent in the quantitative setting regarding the existence and uniqueness of the solution. However in the qualitative setting, Pearl’s method of virtual evidence is not equivalent to Jeffrey’s rule since it is impossible using this method to increase the possibility degree of an event but its generalization is shown equivalent to Jeffrey’s rule. Graphical belief models are compact and powerful tools for representing and reasoning under uncertainty. Possibilistic networks are graphical belief models based on possibility theory. In this paper, we address reasoning under uncertain inputs in both quantitative and qualitative possibilistic networks. More precisely, we first provide possibilistic counterparts of Pearl’s methods of virtual evidence then compare them with the possibilistic counterparts of Jeffrey’s rule of conditioning. As in the probabilistic setting, the two methods are shown to be equivalent in the quantitative setting regarding the existence and uniqueness of the solution. However in the qualitative setting, Pearl’s method of virtual evidence which applies directly on graphical models disagrees with Jeffrey’s rule and the virtual evidence method. The paper provides the precise situations where the methods are not equivalent. Finally, the paper addresses related issues like transformations from one method to another and commutativity.

IJCAI Conference 2013 Conference Paper

Syntactic Computation of Hybrid Possibilistic Conditioning under Uncertain Inputs

• Salem Benferhat
• Célia da Costa Pereira
• Andrea G. B. Tettamanzi

We extend hybrid possibilistic conditioning to deal with inputs consisting of a set of triplets composed of propositional formulas, the level at which the formulas should be accepted, and the way in which their models should be revised. We characterize such conditioning using elementary operations on possibility distributions. We then solve a difficult issue that concerns the syntactic computation of the revision of possibilistic knowledge bases, made of weighted formulas, using hybrid conditioning. An important result is that there is no extra computational cost in using hybrid possibilistic conditioning and in particular the size of the revised possibilistic base is polynomial with respect to the size of the initial base and the input.

ECAI Conference 2012 Conference Paper

Hybrid Possibilistic Conditioning for Revision under Weighted Inputs

• Salem Benferhat
• Célia da Costa Pereira
• Andrea G. B. Tettamanzi

We propose and investigate new operators in the possibilistic belief revision setting, obtained as different combinations of the conditioning operators on models and countermodels, as well as of how weighted inputs are interpreted. We obtain a family of eight operators that essentially obey the basic postulates of revision, with a few slight differences. These operators show an interesting variety of behaviors, making them suitable to representing changes in the beliefs of an agent in different contexts.

KR Conference 2012 Short Paper

Revising partial pre-orders with partial pre-orders: A unit-based revision framework

• Jianbing Ma
• Salem Benferhat
• Weiru Liu

(Benferhat, Lagrue, and Papini 2005)). In (Benferhat et al. 2000), the epistemic state, representing initial information, and the input, representing new information, are both total pre-orders. In (Benferhat, Lagrue, and Papini 2005), the initial epistemic state is indeed a partial pre-order, however, the input information is a propositional formula. In (Bochman 2001), different strategies have been proposed to revise an epistemic state represented by a partial pre-order on the possible worlds. However, in this book there are no revision methods for revising a partial pre-order by a partial pre-order. Our revision operations are also totally different from Lang’s works on preference (e. g. (Lang and van der Torre 2008)), and Weydert, Freund and Kern-Isberner’s revision with conditionals (e. g., (Weydert 1994; Freund 1998; Kern-Isberner 2002)). So far in the literature, there is hardly any work that studies the revision of an epistemic state (especially a partial pre-order) being revised by a partial preorder (a new input). The only work we have seen addressing this issue is a recent paper (Tamargo et al. 2011), in which revision of partial orders is studied in a standard expansion and contraction way. But it does not provide concrete revision results because of the use of certain kinds of selection functions. In this paper, we investigate revision strategies for this setting: a partial pre-order revised by another partial preorder. With this perspective, each individual ordering relation (a pair of elements with an ordering connective), which we name unit, contained in the input is itself an important piece of evidence that should be preserved (Ma, Liu, and Hunter 2011). To propose a revision framework for partial pre-orders, we investigate how a revision operator should be designed. Generally speaking, both a priori ordering set, S, and a new input SI can be seen as sets containing individual ordering relations, e. g., the units. So, revision can be carried out by (i) deriving maximal supersets of SI that contain suitable units in S which do not lead to possible contradiction; (ii) by inserting units from SI to S while removing any units that are inconsistent with this insertion; or (iii) by enlarging SI through inserting one unit from S at a time, while maintaining consistency, etc. Based on these intuitions, we propose a family of unit-based revision operators, dubbed extension revision, match revision, inner revision, and outer revision. We prove the equivalence between these operators Belief revision studies strategies about how agents revise their belief states when receiving new evidence. Both in classical belief revision and in epistemic revision, a new input is either in the form of a (weighted) propositional formula or a total pre-order (where the total pre-order is considered as a whole). However, in some real-world applications, a new input can be a partial pre-order where each unit that constitutes the partial pre-order is important and should be considered individually. To address this issue, in this paper, we study how a partial preorder representing the prior epistemic state can be revised by another partial pre-order (the new input) from a different perspective, where the revision is conducted recursively on the individual units of partial pre-orders. We propose different revision operators (rules), dubbed the extension, match, inner and outer revision operators, from different revision points of view. We also analyze several properties for these operators.

ECAI Conference 2012 Conference Paper

Three-valued possibilistic networks

• Salem Benferhat
• Karim Tabia

Possibilistic networks are graphical models that compactly encode joint possibility distributions. This paper studies a new form of possibilistic graphical models called three-valued possibilistic networks. Contrary to standard belief networks where the beliefs are encoded using belief degrees within the interval [0, 1], three-valued possibilistic networks only allow three values: 0, 1 and 0, 1. The first part of this paper addresses foundational issues of three-valued possibilistic networks. In particular, we show that the semantics that can be associated with a three-valued possibilistic network is a family of compatible boolean networks. The second part of the paper deals with inference issues where we propose an extension to the min-based chain rule for three-valued networks. Then, we show that the well-known junction tree algorithm can be directly adapted for the three-valued possibilistic setting.

IJCAI Conference 2011 Conference Paper

Interval-Based Possibilistic Logic

• Salem Benferhat
• Julien Hu
• eacute;
• Sylvain Lagrue
• Julien Rossit

Possibilistic logic is a well-known framework for dealing with uncertainty and reasoning under inconsistent knowledge bases. Standard possibilistic logic expressions are propositional logic formulas associated with positive real degrees belonging to [0, 1]. However, in practice it may be difficult for an expert to provide exact degrees associated with formulas of a knowledge base. This paper proposes a flexible representation of uncertain information where the weights associated with formulas are in the form of intervals. We first study a framework for reasoning with interval-based possibilistic knowledge bases by extending main concepts of possibilistic logic such as the ones of necessity and possibility measures. We then provide a characterization of an interval-based possibilistic logic base by means of a concept of compatible standard possibilistic logic bases. We show that interval-based possibilistic logic extends possibilistic logic in the case where all intervals are singletons. Lastly, we provide computational complexity results of deriving plausible conclusions from interval-based possibilistic bases and we show that the flexibility in representing uncertain information is handled without extra computational costs.

AAAI Conference 2010 Conference Paper

A Belief Revision Framework for Revising Epistemic States with Partial Epistemic States

• Jianbing Ma
• Weiru Liu
• Salem Benferhat

Belief revision performs belief change on an agent’s beliefs when new evidence (either of the form of a propositional formula or of the form of a total pre-order on a set of interpretations) is received. Jeffrey’s rule is commonly used for revising probabilistic epistemic states when new information is probabilistically uncertain. In this paper, we propose a general epistemic revision framework where new evidence is of the form of a partial epistemic state. Our framework extends Jeffrey’s rule with uncertain inputs and covers wellknown existing frameworks such as ordinal conditional function (OCF) or possibility theory. We then define a set of postulates that such revision operators shall satisfy and establish representation theorems to characterize those postulates. We show that these postulates reveal common characteristics of various existing revision strategies and are satisfied by OCF conditionalization, Jeffrey’s rule of conditioning and possibility conditionalization. Furthermore, when reducing to the belief revision situation, our postulates can induce most of Darwiche and Pearl’s postulates.

AIJ Journal 2010 Journal Article

Book review

• Salem Benferhat

JELIA Conference 2010 Conference Paper

Bridging Possibilistic Conditional Knowledge Bases and Partially Ordered Bases

• Salem Benferhat
• Sylvain Lagrue
• Safa Yahi

Abstract Possibilistic logic offers a unified framework for revising prioritized pieces of information and for reasoning with conditional knowledge bases. A conditional assertion of the form ”generally, if α is true then β is true” is interpreted as a constraint expressing that the possibility degree of having \(\alpha \land \beta\) being true is greater than the possibility degree of having \(\alpha \land \neg \beta\) being true. Recently, an important extension of possibilistic logic has been proposed to deal with partially pre-ordered bases in order to avoid comparing unrelated pieces of information. This paper establishes relationships between reasoning from partially pre-ordered bases and reasoning from conditional knowledge bases. It contains two important contributions. The first contribution consists in identifying conditions under which a partially ordered belief base can be encoded as a set of conditional assertions, and conversely. In particular, we provide the correspondences between the concept of compatible possibility distributions used for conditional assertions and the one of compatible prioritized bases used for partially pre-ordered bases. The second important contribution of this paper consists in providing the computational complexity of reasoning with partially pre-ordered bases using the well-known possibilistic and inclusion-based policies.

UAI Conference 2010 Conference Paper

Compiling Possibilistic Networks: Alternative Approaches to Possibilistic Inference

• Raouia Ayachi
• Nahla Ben Amor
• Salem Benferhat
• Rolf Haenni

Qualitative possibilistic networks, also known as min-based possibilistic networks, are important tools for handling uncertain information in the possibility theory framework. Despite their importance, only the junction tree adaptation has been proposed for exact reasoning with such networks. This paper explores alternative algorithms using compilation techniques. We first propose possibilistic adaptations of standard compilation-based probabilistic methods. Then, we develop a new, purely possibilistic, method based on the transformation of the initial network into a possibilistic base. A comparative study shows that this latter performs better than the possibilistic adaptations of probabilistic methods. This result is also confirmed by experimental results.

AIJ Journal 2010 Journal Article

Interventions and belief change in possibilistic graphical models

• Salem Benferhat

ECAI Conference 2010 Conference Paper

Min-based causal possibilistic networks: Handling interventions and analyzing the possibilistic counterpart of Jeffrey's rule of conditioning

• Salem Benferhat
• Karim Tabia

This paper deals with two important issues related to the handling of uncertain and causal information in a qualitative (or min-based) possibility theory framework. The first issue addresses encoding interventions using the possibilistic conditioning under uncertain inputs problem. More precisely, we analyze the min-based possibilistic counterpart of Jeffrey's rule of conditioning and point out that contrary to the probabilistic setting, this rule does not guarantee the existence of a solution satisfying the kinematics conditions. Then we show that this rule can naturally encode the concept of interventions in causal graphical models. Surprisingly enough, we show that when dealing with interventions the min-based counterpart of Jeffrey's rule provides a unique solution. The second issue deals with the efficient handling of sets of observations and interventions in min-based possibilistic networks, where we propose a solution based on a series of equivalent and efficient transformations on the initial causal graph.

KR Conference 2008 Conference Paper

A Lexicographic Inference for Partially Preordered Belief Bases

• Safa Yahi
• Salem Benferhat
• Sylvain Lagrue
• Mariette Sérayet
• Odile Papini

Coherence-based approaches are quite popular to reason under inconsistency. Most of them are defined with respect to totally preordered belief bases such as the lexicographic inference which is known to have desirable properties from theoretical, practical and psychological points of view. However, partially preordered belief bases offer much more flexibility to represent efficiently incomplete knowledge and to avoid comparing unrelated pieces of information. In this paper, we propose a lexicographic inference for partially preordered belief bases that extends the classical one. On one hand, we define a natural inference relation which consists in applying classical lexicographic inference from all compatible totally preordered belief bases. On the other hand, we propose a novel cardinality-based preorder between consistent subbases. This cardinality-based preorder can be indifferently applied on partially or totally preordered belief bases. Then, applying classical inference on the preferred consistent subbases, according to this preorder, provides another lexicographic inference relation for partially preordered belief bases. Interestingly enough, we show that these two inference relations are equivalent. Lastly, a semantic characterization of these two equivalent definitions is provided.

IJCAI Conference 2007 Conference Paper

• Salem Benferhat
• Safa Yahi
• Habiba Drias

Developing efficient approaches for reasoning under inconsistency is an important issue in many applications. Several methods have been proposed to compile, possibly inconsistent, weighted or stratified bases. This paper focuses on the well-known linear order and possibilistic logic strategies. It provides a way for compiling a stratified belief base in order to be able to process inference from it in polynomial time. The resulting extra compilation cost is very low. In particular, the number of additional variables, that are added to original stratified bases, corresponds exactly to the number of priority levels existing in the base. Moreover, our compilation approach allows an efficient computation of weighted possibilistic conclusions and possibilistic conditioning.

AAAI Conference 2007 Conference Paper

An Egalitarist Fusion of Incommensurable Ranked Belief Bases under Constraints

• Salem Benferhat

In the last decade, several approaches have been proposed for merging multiple and potentially conflicting pieces of information. Egalitarist fusion modes privilege solutions that minimize the (local) dissatisfaction of each agent (source, expert) who is involved in the fusion process. This paper proposes useful strategies for an egalitarist fusion of incommensurable ranked belief bases under constraints. We show that the fusion process can equivalently be characterized either by means of the notion of compatible ranked bases, or by means of a Pareto-like ordering on the set of possible solutions. Lastly, rational postulates for our merging operator are studied.

AAAI Conference 2007 Conference Paper

Possibilistic Causal Networks for Handling Interventions: A New Propagation Algorithm

• Salem Benferhat

This paper contains two important contributions for the development of possibilistic causal networks. The first one concerns the representation of interventions in possibilistic networks. We provide the counterpart of the ”DO” operator, recently introduced by Pearl, in possibility theory framework. We then show that interventions can equivalently be represented in different ways in possibilistic causal networks. The second main contribution is a new propagation algorithm for dealing with both observations and interventions. We show that our algorithm only needs a small extra cost for handling interventions and is more appropriate for handling sequences of observations and interventions.

ECAI Conference 2006 Conference Paper

An Alternative Inference for Qualitative Choice Logic

• Salem Benferhat
• Daniel Le Berre
• Karima Sedki

Qualitative Choice Logic adds to classical propositional logic a new connective, called ordered disjunction, used to express preferences between alternatives. We present an alternative inference relation for the QCL language that overcomes some QCL limitations.

ECAI Conference 2006 Conference Paper

Compiling Possibilistic Knowledge Bases

• Salem Benferhat
• Henri Prade

Possibilistic knowledge bases gather propositional formulas associated with degrees belonging to a linearly ordered scale. These degrees reflect certainty or priority, depending if the formulas encode pieces of beliefs or goals to be pursued. Possibilistic logic provides a simple format that turns to be useful for handling qualitative uncertainty, exceptions or preferences. The main result of the paper provides a way for compiling a possibilistic knowledge base in order to be able to process inference from it in polynomial time. The procedure is based on a symbolic treatment of the degrees under the form of sorted literals and on the idea of forgetting variables. The number of sorted literals that are added corresponds exactly to the number of priority levels existing in the base, and the number of binary clauses added in the compilation is also equal to this number of levels. The resulting extra compilation cost is very low.

ECAI Conference 2006 Conference Paper

Merging Possibilistic Networks

• Salem Benferhat

This paper deals with merging multiple-source uncertain pieces of information, which are encoded by means of possibilistic networks. We first show that the merging of possibilistic networks having the same graphical structure can be easily achieved in polynomial time. When possibilistic networks have different graphical structures we show that their fusion can also be efficiently done by extending initial possibilistic networks into a same common structure. We then address two important problems: how to deal with cycles, and how to solve the subnormalization problem which reflects conflicts between sources?

IJCAI Conference 2005 Conference Paper

Encoding formulas with partially constrained weights in a possibilistic-like many-sorted propositional logic

• Salem Benferhat
• Henri

Possibilistic logic offers a convenient tool for handling uncertain or prioritized formulas and coping with inconsistency. Propositional logic formulas are thus associated with weights belonging to a linearly ordered scale. However, especially in case of multiple source information, only partial knowledge may be available about the relative ordering between weights of formulas. In order to cope with this problem, a two-sorted counterpart of possibilistic logic is introduced. Pieces of information are encoded as clauses where special literals refer to the weights. Constraints between weights translate into logical formulas of the corresponding sort and are gathered in a distinct auxiliary knowledge base. An inference relation, which is sound and complete with respect to preferential model semantics, enables us to draw plausible conclusions from the two knowledge bases. The inference process is characterized by using ”forgetting variables” for handling the symbolic weights, and hence an inference process is obtained by means of a DNF compilation of the two knowledge bases.

AAAI Conference 2005 Conference Paper

Hybrid Possibilistic Networks

• Salem Benferhat

Possibilistic networks are important tools for dealing with uncertain pieces of information. For multiplyconnected networks, it is well known that the inference process is a hard problem. This paper studies a new representation of possibilistic networks, called hybrid possibilistic networks. The uncertainty is no longer represented by local conditional possibility distributions, but by their compact representations which are possibilistic knowledge bases. We show that the inference algorithm in hybrid networks is strictly more efficient than the ones of standard propagation algorithm.

IJCAI Conference 2005 Conference Paper

Revision of Partially Ordered Information: Axiomatization, Semantics and Iteration

• Salem Benferhat
• Sylvain Lagrue
• Odile

This paper deals with iterated revision of partially ordered information. The first part of this paper concerns the Katsuno-Mendelzon’s postulates: we first point out that these postulates are not fully satisfactory since only a class of partially ordered information can be revised. We then propose a suitable definition of faithful assignment, followed by a new set of postulates and a representation theorem. The second part of this paper investigates additional postulates dedicated to iterated revision operators of partially ordered information. Three extensions of well-known iterated belief revision operations for dealing with partially ordered information are briefly presented.

JELIA Conference 2004 Conference Paper

An Answer Set Programming Encoding of Prioritized Removed Sets Revision: Application to GIS

• Jonathan Ben-Naim
• Salem Benferhat
• Odile Papini
• Éric Würbel

Abstract Geographical information systems are one of the most important application areas of belief revision. Recently, Würbel and colleagues [32] have applied the so-called ”removed sets revision” (RSR) to the problem of assessment of water heights in a flooded valley. The application was partially satisfactory since only a small part of the valley has been handled. This paper goes one step further, and proposes an extension of (RSR) called ”Prioritized Removed Sets Revision” (PRSR). We show that (PRSR) performed using answer set programming makes possible to solve a practical revision problem provided by a real application in the framework of geographical information system (GIS). We first show how PRSR can be encoded into a logic program with answer set semantics, we then present an adaptation of the smodels system devoted to efficiently compute the answer sets in order to perform PRSR. The experimental study shows that the answer set programming approach gives better results than previous implementations of RSR and in particular it allows to handle the whole valley. Lastly, some experimental studies comparing our encoding with implementations based on SAT-solvers are also provided.

KR Conference 2004 Conference Paper

An experimental analysis of possibilistic default reasoning

• Salem Benferhat
• Jean Fran‡ois Bonnefon
• Rui Da Silva Neves

This article provides an experimental analysis of the possibilistic handling of default rules. Three different nonmonotonic consequence relations are considered: minimum specificity inference (MSP), lexicographical closure (LC), and epsilon-belief functions (LCD). The latter was initially proposed within the belief function framework; it is rephrased here within a possibility theory framework. These three consequence relations share some properties but differ on others, which allows for an experimental test of their psychological plausibility. Actual human reasoning is shown to manifest properties which are similar to those of LC but not to those of MSP or LCD.

AIJ Journal 2004 Journal Article

Editorial

• Salem Benferhat
• Enrico Giunchiglia

ECAI Conference 2004 Conference Paper

Handling Conflicts in Access Control Models

• Salem Benferhat
• Rania El Baida

AIJ Journal 2004 Journal Article

Qualitative choice logic

• Gerhard Brewka
• Salem Benferhat
• Daniel Le Berre

AIJ Journal 2004 Journal Article

Weakening conflicting information for iterated revision and knowledge integration

• Salem Benferhat
• Souhila Kaci
• Daniel Le Berre
• Mary-Anne Williams

UAI Conference 2003 Conference Paper

A possibilistic handling of partially ordered information

• Salem Benferhat
• Sylvain Lagrue
• Odile Papini

In a standard possibilistic logic, prioritized information are encoded by means of weighted knowledge base. This paper proposes an extension of possibilistic logic for dealing with partially ordered information. We Show that all basic notions of standard possibilitic logic (sumbsumption, syntactic and semantic inference, etc.) have natural couterparts when dealing with partially ordered information. We also propose an algorithm which computes possibilistic conclusions of a partial knowledge base of a partially ordered knowlege base

AIJ Journal 2003 Journal Article

Logical representation and fusion of prioritized information based on guaranteed possibility measures: Application to the distance-based merging of classical bases

• Salem Benferhat
• Souhila Kaci

UAI Conference 2002 Conference Paper

Bipolar Possibilistic Representations

• Salem Benferhat
• Didier Dubois
• Souhila Kaci
• Henri Prade

Recently, it has been emphasized that the possibility theory framework allows us to distinguish between i) what is possible because it is not ruled out by the available knowledge, and ii) what is possible for sure. This distinction may be useful when representing knowledge, for modelling values which are not impossible because they are consistent with the available knowledge on the one hand, and values guaranteed to be possible because reported from observations on the other hand. It is also of interest when expressing preferences, to point out values which are positively desired among those which are not rejected. This distinction can be encoded by two types of constraints expressed in terms of necessity measures and in terms of guaranteed possibility functions, which induce a pair of possibility distributions at the semantic level. A consistency condition should ensure that what is claimed to be guaranteed as possible is indeed not impossible. The present paper investigates the representation of this bipolar view, including the case when it is stated by means of conditional measures, or by means of comparative context-dependent constraints. The interest of this bipolar framework, which has been recently stressed for expressing preferences, is also pointed out in the representation of diagnostic knowledge.

KR Conference 2002 Conference Paper

Bipolar representation and fusion of preferences in the possibilistic logicframework

• Salem Benferhat
• Didier Dubois
• Souhila Kaci
• Henri Prade

ECAI Conference 2002 Conference Paper

Possibilistic logic representation of preferences: relating prioritized goals and satisfaction levels expressions

• Salem Benferhat
• Didier Dubois
• Souhila Kaci
• Henri Prade

KR Conference 2002 Conference Paper

Qualitative Choice Logic

• Gerhard Brewka
• Salem Benferhat
• Daniel Le Berre

NMR Workshop 2002 Conference Paper

Revising partially ordered beliefs

• Salem Benferhat
• Sylvain Lagrue
• Odile Papini

This paper deals with the revision of partially ordered beliefs. It proposes a semantic representation of epistemic states by partial preorders on interpretations and a syntactic representation by partially ordered belief bases. Two revision operations, the revision stemming from the history of observations and the possibilistic revision, defined when the epistemic state is represented by a total preorder, are generalized, at a semantic level, to the case of a partial pre-order on interpretations, and at a syntactic level, to the case of a partially ordered belief base. The equivalence between the two representations is shown for the two revision operations.

UAI Conference 2001 Conference Paper

Graphical readings of possibilistic logic bases

• Salem Benferhat
• Didier Dubois
• Souhila Kaci
• Henri Prade

Possibility theory offers either a qualitive, or a numerical framework for representing uncertainty, in terms of dual measures of possibility and necessity. This leads to the existence of two kinds of possibilistic causal graphs where the conditioning is either based on the minimum , or the product operator. Benferhat et al. (1999) have investigated the connections between min-based graphs and possibilistic logic bases (made of classical formulas weighted in terms of certainty). This paper deals with a more difficult issue : the product-based graphical representations of possibilistic bases, which provides an easy structural reading of possibilistic bases.Moreover, this paper also provides another reading of possibilistic bases in terms of comparative preferences of the form "in the context p, q is preferred to not q". This enables us to explicit preferences underlying a set of goals with different levels of priority.

UAI Conference 2000 Conference Paper

A principled analysis of merging operations in possibilistic logic

• Souhila Kaci
• Salem Benferhat
• Didier Dubois
• Henri Prade

Possibilistic logic offers a qualitative framework for representing pieces of information associated with levels of uncertainty of priority. The fusion of multiple sources information is discussed in this setting. Different classes of merging operators are considered including conjunctive, disjunctive, reinforcement, adaptive and averaging operators. Then we propose to analyse these classes in terms of postulates. This is done by first extending the postulate for merging classical bases to the case where priorites are avaialbe.

ECAI Conference 2000 Conference Paper

Encoding Information Fusion in Possibilistic Logic: A General Framework for Rational Syntactic Merging

• Salem Benferhat
• Didier Dubois
• Souhila Kaci
• Henri Prade

ECAI Conference 2000 Conference Paper

Iterated Revision by Epistemic States: Axioms, Semantics and Syntax

• Salem Benferhat
• Sébastien Konieczny
• Odile Papini
• Ramón Pino Pérez

ECAI Conference 2000 Conference Paper

Kalman-like Filtering in a possibilistic Setting

• Salem Benferhat
• Didier Dubois
• Henri Prade

AAAI Conference 1999 Conference Paper

A Sequential Reversible Belief Revision Method Based on Polynomials

• Salem Benferhat
• Didier Dubois
• IRIT
• Université Paul Sabatier; Odile Papini
• LIM
• Université de la Méditerranée

This paper deals with iterated belief changeand proposesa drastic revisionrule that modifiesa plausibility ordering of interpretations in such a waythat anyworld wherethe input observartion holds is moreplausible that any world where it does not. This change nile makessense in a dynamiccontext where observations are received, andthe newerobservations are considered more plausible than older ones. It is shownhowto encode an epistemic state using polynomials equipped with the lexicographical ordering. This encodingmakes it very easy to implement anditerate the revision rule using simple operations on these polynomials. Moreover, polynomials allowto keeptrack of the sequenceof observations. Lastly, it is shown howto efficiently compute the revision rule at the syntactical level, whenthe epistemicstate is conciselyrepresentedby a prioritized belief base. Ourrevision rule is the mostdrastic one can think of, in accordancewith Darwiche and Pearl’s principles, and thus contrasts with the minimalchange rule called natural belief revision.

UAI Conference 1999 Conference Paper

Possibilistic logic bases and possibilistic graphs

• Salem Benferhat
• Didier Dubois
• Laurent Garcia
• Henri Prade

Possibilistic logic bases and possibilistic graphs are two different frameworks of interest for representing knowledge. The former stratifies the pieces of knowledge (expressed by logical formulas) according to their level of certainty, while the latter exhibits relationships between variables. The two types of representations are semantically equivalent when they lead to the same possibility distribution (which rank-orders the possible interpretations). A possibility distribution can be decomposed using a chain rule which may be based on two different kinds of conditioning which exist in possibility theory (one based on product in a numerical setting, one based on minimum operation in a qualitative setting). These two types of conditioning induce two kinds of possibilistic graphs. In both cases, a translation of these graphs into possibilistic bases is provided. The converse translation from a possibilistic knowledge base into a min-based graph is also described.

IJCAI Conference 1999 Conference Paper

Towards a possibilistic logic handling of preferences

• Salem Benferhat
• Didier Dubois
• Henri Prade

UAI Conference 1998 Conference Paper

Merging uncertain knowledge bases in a possibilistic logic framework

• Salem Benferhat
• Claudio Sossai

This paper addresses the problem of merging uncertain information in the framework of possibilistic logic. It presents several syntactic combination rules to merge possibilistic knowledge bases, provided by different sources, into a new possibilistic knowledge base. These combination rules are first described at the meta-level outside the language of possibilistic logic. Next, an extension of possibilistic logic, where the combination rules are inside the language, is proposed. A proof system in a sequent form, which is sound and complete with respect to the possibilistic logic semantics, is given.

AIJ Journal 1997 Journal Article

Nonmonotonic reasoning, conditional objects and possibility theory

• Salem Benferhat
• Didier Dubois
• Henri Prade

AAAI Conference 1997 Conference Paper

Possibilistic and Standard Probabilistic Semantics of Conditional Knowledge

• Salem Benferhat

ECAI Conference 1996 Conference Paper

Beyond Counter-Examples to Nonmonotonic Formalisms: A Possibility-Theoretic Analysis

• Salem Benferhat
• Didier Dubois
• Henri Prade

UAI Conference 1996 Conference Paper

Coping with the Limitations of Rational Inference in the Framework of Possibility Theory

• Salem Benferhat
• Didier Dubois
• Henri Prade

Possibility theory offers a framework where both Lehmann's "preferential inference" and the more productive (but less cautious) "rational closure inference" can be represented. However, there are situations where the second inference does not provide expected results either because it cannot produce them, or even provide counter-intuitive conclusions. This state of facts is not due to the principle of selecting a unique ordering of interpretations (which can be encoded by one possibility distribution), but rather to the absence of constraints expressing pieces of knowledge we have implicitly in mind. It is advocated in this paper that constraints induced by independence information can help finding the right ordering of interpretations. In particular, independence constraints can be systematically assumed with respect to formulas composed of literals which do not appear in the conditional knowledge base, or for default rules with respect to situations which are "normal" according to the other default rules in the base. The notion of independence which is used can be easily expressed in the qualitative setting of possibility theory. Moreover, when a counter-intuitive plausible conclusion of a set of defaults, is in its rational closure, but not in its preferential closure, it is always possible to repair the set of defaults so as to produce the desired conclusion.

UAI Conference 1995 Conference Paper

Belief functions and default reasoning

• Salem Benferhat
• Alessandro Saffiotti
• Philippe Smets

We present a new approach to dealing with default information based on the theory of belief functions. Our semantic structures, inspired by Adams' epsilon-semantics, are epsilon-belief assignments, where values committed to focal elements are either close to 0 or close to 1. We define two systems based on these structures, and relate them to other non-monotonic systems presented in the literature. We show that our second system correctly addresses the well-known problems of specificity, irrelevance, blocking of inheritance, ambiguity, and redundancy.

ECAI Conference 1994 Conference Paper

Expressing Independence in a Possibilistic Framework and its Application to Default Reasoning

• Salem Benferhat
• Didier Dubois
• Henri Prade

UAI Conference 1993 Conference Paper

Argumentative inference in uncertain and inconsistent knowledge bases

• Salem Benferhat
• Didier Dubois
• Henri Prade

This paper presents and discusses several methods for reasoning from inconsistent knowledge bases. A so-called argumentative-consequence relation taking into account the existence of consistent arguments in favor of a conclusion and the absence of consistent arguments in favor of its contrary, is particularly investigated. Flat knowledge bases, i.e. without any priority between their elements, as well as prioritized ones where some elements are considered as more strongly entrenched than others are studied under different consequence relations. Lastly a paraconsistent-like treatment of prioritized knowledge bases is proposed, where both the level of entrenchment and the level of paraconsistency attached to a formula are propagated. The priority levels are handled in the framework of possibility theory.

IJCAI Conference 1993 Conference Paper

Inconsistency management and prioritized syntax-based entailment

• Salem Benferhat
• Claudette Cayrol
• Didier Dubois
• Jerome Lang
• Henri Prade

The idea of ordering plays a basic role in commonsense reasoning for addressing three interrelated tasks: inconsistency handling, belief revision and plausible inference. We study the behavior of non-monotonic inferences induced by various methods for priority-based handling of inconsistent sets of classical formulas. One of them is based on a lexicographic ordering of maximal consistent subsets, and refines Brewka's preferred sub-theories. This new approach leads to a non-monotonic inference which satisfies the "rationality" property while solving the problem of blocking of property inheritance. It differs from and improves previous equivalent approaches such as Gardenfors and Makinson's expectation-based inference, Pearl's System Z and possibilistic logic.