Possibilistic logic is forty years old. Possibilistic logic is a logic that handles classical logic formulas associated with weights taking values in a linearly ordered set or more generally in a lattice. Over the decades, possibilistic logic has undergone numerous developments at both theoretical and applied levels. The ambition of this article is to review all these developments while exposing the main ideas behind them.

There have been several pioneering approaches to the extraction of attribute implications from a formal context, dating from the 1980's: the one of Guigues and Duquenne based on so-called non-redundancy nodes, another one proposed by Ganter highlighting the concept of pseudo-closed set, and the best-known one relying on the recursive computation of so-called pseudo-intents in the book by Ganter and Wille. The Guigues and Duquenne approach has never been compared in detail in the literature with the other two, although they turn out to be equivalent. This paper tries to fill this gap, proposing a unified view, hopefully more easy to grasp.

This paper proposes a tentative and original survey of meeting points between Knowledge Representation and Reasoning (KRR) and Machine Learning (ML), two areas which have been developed quite separately in the last four decades. First, some common concerns are identified and discussed such as the types of representation used, the roles of knowledge and data, the lack or the excess of information, or the need for explanations and causal understanding. Then, the survey is organised in seven sections covering most of the territory where KRR and ML meet. We start with a section dealing with prototypical approaches from the literature on learning and reasoning: Inductive Logic Programming, Statistical Relational Learning, and Neurosymbolic AI, where ideas from rule-based reasoning are combined with ML. Then we focus on the use of various forms of background knowledge in learning, ranging from additional regularisation terms in loss functions, to the problem of aligning symbolic and vector space representations, or the use of knowledge graphs for learning. Then, the next section describes how KRR notions may benefit to learning tasks. For instance, constraints can be used as in declarative data mining for influencing the learned patterns; or semantic features are exploited in low-shot learning to compensate for the lack of data; or yet we can take advantage of analogies for learning purposes. Conversely, another section investigates how ML methods may serve KRR goals. For instance, one may learn special kinds of rules such as default rules, fuzzy rules or threshold rules, or special types of information such as constraints, or preferences. The section also covers formal concept analysis and rough sets-based methods. Yet another section reviews various interactions between Automated Reasoning and ML, such as the use of ML methods in SAT solving to make reasoning faster. Then a section deals with works related to model accountability, including explainability and interpretability, fairness and robustness. Finally, a section covers works on handling imperfect or incomplete data, including the problem of learning from uncertain or coarse data, the use of belief functions for regression, a revision-based view of the EM algorithm, the use of possibility theory in statistics, or the learning of imprecise models. This paper thus aims at a better mutual understanding of research in KRR and ML, and how they can cooperate. The paper is completed by an abundant bibliography.

International audience

Possibility theory and Sugeno integrals may be viewed respectively as qualitative counterparts of probability theory and Choquet integrals, which are well-known tools for decision under uncertainty and multi-criteria evaluation. But what is the qualitative counterpart to Shafer's evidence theory for fusing uncertain pieces of information? There is not yet fully clear and definitive answer to this question, in spite of some sparse attempts at developing elements of such a theory. The paper makes a step in this direction and focuses more particularly on the problems of fusing possibilistic counterparts of the basic probability assigments of evidence theory. Making sense of this qualitative counterpart is not fully straightforward, and not just a matter of replacing the sum by the max operation and the product by the min operation. Indeed, as it turns out, any fuzzy measure can stand as a qualitative belief function and more than one possibilistic mass function can be associated to the same fuzzy measure. The particular role of qualitative support functions (whose focal sets are the universe of discourse and some subset of it, just as in the quantitative case) is emphasized in the fusion process. The practical interest of such a qualitative approach is pointed out.

In decision problems involving two dimensions (like several agents in uncertainty) the properties of expected utility ensure that the result of a two-stepped procedure evaluation does not depend on the order with which the aggregations of local evaluations are performed (e.g., agents first, uncertainty next, or the converse). We say that the aggregations on each dimension commute. In a previous conference paper, Ben Amor, Essghaier and Fargier have shown that this property holds when using pessimistic possibilistic integrals on each dimension, or optimistic ones, while it fails when using a pessimistic possibilistic integral on one dimension and an optimistic one on the other. This paper studies and completely solves this problem when more general Sugeno integrals are used in place of possibilistic integrals, leading to double Sugeno integrals. The results show that there are capacities other than possibility and necessity measures that ensure commutation of Sugeno integrals. Moreover, the relationship between two-dimensional capacities and the commutation property for their projections is investigated.

International audience

Formal concept analysis theory (FCA) classically relies on the use of the Galois powerset operator. Formal similarities between possibility theory and formal concept analysis have led to the use of possibilistic operators in FCA, which were ignored before. In this paper, an approach based on the use of asymmetric composition of the two most usual possibilistic operators is proposed. It enables us to complement the stem base, by deriving attribute implications with disjunctions on both sides of the implications. Besides, the approach is also generalized to incomplete contexts involving explicit positive and negative information. We outline the potential application of these results to the completion of TBoxes in description logic.

The use of possibilistic networks for representing conditional preference statements on discrete variables has been proposed only recently. The approach uses non-instantiated possibility weights to define conditional preference tables. Moreover, additional information about the relative strengths of these symbolic weights can be taken into account. The fact that at best we have some information about the relative values of these weights acknowledges the qualitative nature of preference specification. These conditional preference tables give birth to vectors of symbolic weights that reflect the preferences that are satisfied and those that are violated in a considered situation. The comparison of such vectors may rely on different orderings: the ones induced by the product-based, or the minimum-based chain rule underlying the possibilistic network, the discrimin, or leximin refinements of the minimum-based ordering, as well as Pareto ordering, and the symmetric Pareto ordering that refines it. A thorough study of the relations between these orderings in presence of vector components that are symbolic rather numerical is presented. In particular, we establish that the product-based ordering and the symmetric Pareto ordering coincide in presence of constraints comparing pairs of symbolic weights. This ordering agrees in the Boolean case with the inclusion between the sets of preference statements that are violated. The symmetric Pareto ordering may be itself refined by the leximin ordering. The paper highlights the merits of product-based possibilistic networks for representing preferences and provides a comparative discussion with CP-nets and OCF-networks.

This survey paper provides an overview of existing methods for building possibility distributions. We both consider the case of qualitative possibility theory, where the scale remains ordinal, and the case of quantitative possibility theory, where the scale is the real interval [0, 1]. Methods may be order-based or similarity-based for qualitative possibility distributions, whereas statistical methods apply in the quantitative case and then possibilities encode nested random epistemic sets or upper bounds of probabilities. But distance-based approaches, or expert estimates, may be also exploited in the quantitative case.

This article was commissioned by the 22ndIEEE International Conference of Fuzzy Systems (FUZZ-IEEE) to celebrate the 50thAnniversary of Lotfi Zadeh's seminal 1965 paper on fuzzy sets. In addition to Lotfi's original paper, this note itemizes 100 citations of books and papers deemed “important (significant, seminal, etc.)” by 20 of the 21 living IEEE CIS Fuzzy Systems pioneers. Each of the 20 contributors supplied 5 citations, and Lotfi's paper makes the overall list a tidy 101, as in “Fuzzy Sets 101”. This note is not a survey in any real sense of the word, but the contributors did offer short remarks to indicate the reason for inclusion (e.g., historical, topical, seminal, etc.) of each citation. Citation statistics are easy to find and notoriously erroneous, so we refrain from reporting them - almost. The exception is that according to Google scholar on April 9, 2015, Lotfi's 1965 paper has been cited 55,479 times.

Necessary and sufficient conditions for choice functions to be rational have been intensively studied in the past. However, in these attempts, a choice function is completely specified. That is, given any subset of options, called an issue, the best option over that issue is always known, whilst in real-world scenarios, it is very often that only a few choices are known instead of all. In this paper, we study partial choice functions and investigate necessary and sufficient rationality conditions for situations where only a few choices are known. We prove that our necessary and sufficient condition for partial choice functions boils down to the necessary and sufficient conditions for complete choice functions proposed in the literature. Choice functions have been instrumental in belief revision theory. That is, in most approaches to belief revision, the problem studied can simply be described as the choice of possible worlds compatible with the input information, given an agent’s prior belief state. The main effort has been to devise strategies in order to infer the agents revised belief state. Our study considers the converse problem: given a collection of input information items and their corresponding revision results (as provided by an agent), does there exist a rational revision operation used by the agent and a consistent belief state that may explain the observed results?

This article clarifies what it means to solve a system of fuzzy linear equations, relying on the fact that they are a direct extension of interval linear systems of equations, already studied in a specific interval mathematics literature. We highlight four distinct definitions of a systems of linear equations where coefficients are replaced by intervals, each of which based on a generalization of scalar equality to intervals. Each of the four extensions of interval linear systems has a corresponding solution set whose calculation can be carried out by a general unified method based on a relatively new concept of constraint intervals. We also consider the smallest multidimensional intervals containing the solution sets. We propose several extensions of the interval setting to systems of linear equations where coefficients are fuzzy intervals. This unified setting clarifies many of the anomalous or inconsistent published results in various fuzzy interval linear systems studies.

The square of opposition is as old as logic. There has been a recent renewal of interest on this topic, due to the emergence of new structures (hexagonal and cubic) extending the square. They apply to a large variety of representation frameworks, all based on the notions of sets and relations. Afte r a reminder about the structures of opposition, and an introduction to their gradual extensions (exemplified on fuzzy sets), the paper more particularly studies fuzzy rough sets and rough fuzzy sets in the setting of gradual structures of opposition.

Uncertainty and inconsistency pervade human knowledge. Possibilistic logic, where propositional logic formulas are associated with lower bounds of a necessity measure, handles uncertainty in the setting of possibility theory. Moreover, central in standard possibilistic logic is the notion of inconsistency level of a possibilistic logic base, closely related to the notion of consistency degree of two fuzzy sets introduced by L. A. Zadeh. Formulas whose weight is strictly above this inconsistency level constitute a sub-base free of any inconsistency. However, several extensions, allowing for a paraconsistent form of reasoning, or associating possibilistic logic formulas with information sources or subsets of agents, or extensions involving other possibility theory measures, provide other forms of inconsistency, while enlarging the representation capabilities of possibilistic logic. The paper offers a structured overview of the various forms of inconsistency that can be accommodated in possibilistic logic. This overview echoes the rich representation power of the possibility theory framework.

Qualitative Possibilistic Mixed-Observable MDPs (pi-MOMDPs), generalizing pi-MDPs and pi-POMDPs, are well-suited models to planning under uncertainty with mixed-observability when transition, observation and reward functions are not precisely known and can be qualitatively described. Functions defining the model as well as intermediate calculations are valued in a finite possibilistic scale L, which induces a finite belief state space under partial observability contrary to its probabilistic counterpart. In this paper, we propose the first study of factored pi-MOMDP models in order to solve large structured planning problems under qualitative uncertainty, or considered as qualitative approximations of probabilistic problems. Building upon the SPUDD algorithm for solving factored (probabilistic) MDPs, we conceived a symbolic algorithm named PPUDD for solving factored pi-MOMDPs. Whereas SPUDD's decision diagrams' leaves may be as large as the state space since their values are real numbers aggregated through additions and multiplications, PPUDD's ones always remain in the finite scale L via min and max operations only. Our experiments show that PPUDD's computation time is much lower than SPUDD, Symbolic-HSVI and APPL for possibilistic and probabilistic versions of the same benchmarks under either total or mixed observability, while still providing high-quality policies.

Generalized possibilistic logic (GPL) is a logic for reasoning about the revealed beliefs of another agent. It is a two-tier propositional logic, in which propositional formulas are encapsulated by modal operators that are interpreted in terms of uncertainty measures from possibility theory. Models of a GPL theory represent weighted epistemic states and are encoded as possibility distributions. One of the main features of GPL is that it allows us to explicitly reason about the ignorance of another agent. In this paper, we study two types of approaches for reasoning about ignorance in GPL, based on the idea of minimal specificity and on the notion of guaranteed possibility, respectively. We show how these approaches naturally lead to different flavours of the language of GPL and a number of decision problems, whose complexity ranges from the first to the third level of the polynomial hierarchy.

The problem addressed in this paper is the merging of numerical information provided by several sources. Merging conflicting pieces of information into an interpretable and useful format is a tricky task even when an information fusion method is chosen. The use of formal concept analysis and pattern structures enables us to associate subsets of sources to combination results obtainable from consistent subsets of pieces of information. This provides a lattice of arguments where the reliability of sources can be taken into account. Instead of providing a unique fusion result, the method yields a structured view of partial results labelled by subsets of sources and allows us to argue about the most appropriate evaluation. The approach is illustrated with an experiment on a real-world application to decision aid in agricultural practices.

Rough sets are often induced by descriptions of objects based on the precise observations of an insufficient number of attributes. In this paper, we study generalizations of rough sets to incomplete information systems, involving imprecise observatio

Combination rules proposed so far in the Dempster-Shafer theory of evidence, especially Dempster rule, rely on a basic assumption, that is, pieces of evidence being combined are considered to be on a par, i.e. play the same role. When a source of evidence is less reliable than another, it is possible to discount it and then a symmetric combination operation is still used. In the case of revision, the idea is to let prior knowledge of an agent be altered by some input information. The change problem is thus intrinsically asymmetric. Assuming the input information is reliable, it should be retained whilst the prior information should be changed minimally to that effect. Although belief revision is already an important subfield of artificial intelligence, so far, it has been little addressed in evidence theory. In this paper, we define the notion of revision for the theory of evidence and propose several different revision rules, called the inner and outer revisions, and a modified adaptive outer revision, which better corresponds to the idea of revision. Properties of these revision rules are also investigated.

Intelligent agents require methods to revise their epistemic state as they acquire new information. Jeffrey's rule, which extends conditioning to probabilistic inputs, is appropriate for revising probabilistic epistemic states when new information comes in the form of a partition of events with new probabilities and has priority over prior beliefs. This paper analyses the expressive power of two possibilistic counterparts to Jeffrey's rule for modeling belief revision in intelligent agents. We show that this rule can be used to recover several existing approaches proposed in knowledge base revision, such as adjustment, natural belief revision, drastic belief revision, and the revision of an epistemic state by another epistemic state. In addition, we also show that some recent forms of revision, called improvement operators, can also be recovered in our framework.

The belief structure resulting from the combination of consonant and independent marginal random sets is not, in general, consonant. Also, the complexity of such a structure grows exponentially with the number of combined random sets, making it quickly intractable for computations. In this paper, we propose a simple guaranteed consonant outer approximation of this structure. The complexity of this outer approximation does not increase with the number of marginal random sets (i.e., of dimensions), making it easier to handle in uncertainty propagation. Features and advantages of this outer approximation are then discussed, with the help of some illustrative examples.

Fuzzy random variables possess several interpretations. Historically, they were proposed either as a tool for handling linguistic label information in statistics or to represent uncertainty about classical random variables. Accordingly, there are two different approaches to the definition of the variance of a fuzzy random variable. In the first one, the variance of the fuzzy random variable is defined as a crisp number, which makes it easier to handle in further processing. In the second case, the variance is defined as a fuzzy interval, thus offering a gradual description of our incomplete knowledge about the variance of an underlying, imprecisely observed, classical random variable. In this paper, we also discuss another view of fuzzy random variables, which comes down to a set of random variables induced by a fuzzy relation describing an ill-known conditional probability. This view leads to yet another definition of the variance of a fuzzy random variable in the context of the theory of imprecise probabilities. The new variance is a real interval, which achieves a compromise between both previous definitions in terms of representation simplicity. Our main objective is to demonstrate, with the help of simple examples, the practical significance of these definitions of variance induced by various existing views of fuzzy random variables.

When multiple sources provide information about the same unknown quantity, their fusion into a synthetic interpretable message is often a tricky problem, especially when sources are conflicting. In this paper, we propose to use possibility theory and the notion of maximal coherent subsets (MCSs), often used in logic-based representations, to build a fuzzy belief structure that will be instrumental both for extracting useful insight about various features of the information conveyed by the sources and for compressing this information into a unique possibility distribution. Extentions and properties of the basic fusion rule are also studied.

A general approach to practical inference with gradual implicative rules and fuzzy inputs is presented. Gradual rules represent constraints restricting outputs of a fuzzy system for each input. They are tailored for interpolative reasoning. Our approach to inference relies on the use of inferential independence. It is based on fuzzy output computation under an interval-valued input. A double decomposition of fuzzy inputs is done in terms of alpha-cuts and in terms of a partitioning of these cuts according to areas where only a few rules apply. The case of 1-D and 2-D inputs is considered, as well as higher dimensional cases. An application to a cheese-making process illustrates the approach.

From a knowledge representation point of view, it may be interesting to distinguish between (i) what is potentially possible because it is not inconsistent with the available knowledge on the one hand, and (ii) what is actually possible because it is reported from observations on the other hand. Such a distinction also makes sense when expressing preferences, to point out positively desired choices among merely tolerated ones. Possibility theory provides a representation framework where this distinction can be made in a graded way. The two types of information can be encoded by two types of constraints expressed in terms of necessity measures and in terms of so-called guaranteed possibility functions. These two set-functions are min-decomposable with respect to conjunction and disjunction, respectively. This gives birth to two forms of possibilistic logic bases, where clauses (resp., phrases) are weighted in terms of a necessity measure (resp., a guaranteed possibility function). By application of a minimal commitment principle, the two bases induce a pair of possibility distributions at the semantic level, for which a consistency condition should hold to ensure that what is claimed to be actually possible is indeed not impossible. The paper provides a survey of this bipolar representation framework, including the use of conditional measures, or the handling of comparative context-dependent constraints. The interest of the framework is stressed for expressing preferences, as well as in the representation of “if–then” rules in terms of examples and counterexamples. © 2008 Wiley Periodicals, Inc.

Bipolarity seems to pervade human understanding of information and preference, and bipolar representations look very useful in the development of intelligent technologies. Bipolarity refers to an explicit handling of positive and negative sides of information. Basic notions and background on bipolar representations are provided. Three forms of bipolarity are laid bare: symmetric univariate, dual bivariate, and asymmetric (or heterogeneous) bipolarity. They can be instrumental in the logical handling of incompleteness and inconsistency, rule representation and extraction, argumentation, learning, and decision analysis. © 2008 Wiley Periodicals, Inc.

Making a decision is often a matter of listing and comparing positive and negative arguments. In such cases, the evaluation scale for decisions should be considered bipolar, that is, negative and positive values should be explicitly distinguished. That is what is done, for example, in Cumulative Prospect Theory. However, contraryto the latter framework that presupposes genuine numerical assessments, human agents often decide on the basis of an ordinal ranking of the pros and the cons, and by focusing on the most salient arguments. In other terms, the decision process is qualitative as well as bipolar. In this article, based on a bipolar extension of possibility theory, we define and axiomatically characterize several decision rules tailored for the joint handling of positive and negative arguments in an ordinal setting. The simplest rules can be viewed as extensions of the maximin and maximax criteria to the bipolar case, and consequently suffer from poor decisive power. More decisive rules that refine the former are also proposed. These refinements agree both with principles of efficiency and with the spirit of order-of-magnitude reasoning, that prevails in qualitative decision theory. The most refined decision rule uses leximin rankings of the pros and the cons, and the ideas of counting arguments of equal strength and cancelling pros by cons. It is shown to come down to a special case of Cumulative Prospect Theory, and to subsume the ``Take the Best'' heuristic studied by cognitive psychologists.

This position paper discusses the difficulty of interpreting the iterated belief revision problem. Axioms of iterated belief revision are often presented as extensions of the AGM axioms, upon receiving a sequence of inputs, likely to alter not only the belief set, but also the epistemic entrenchment relation underlying the revision operator. Iterated belief revision presupposes that more recent inputs have priority over less recent ones. We argue that this view of iterated revision is at odds with the suggestion of Gärdenfors and Makinson, that belief revision and non-monotonic reasoning are two sides of the same coin. It is not clear that non-monotonic reasoning modifies the ranking of possible worlds implicit in default rules. We lay bare three different paradigms of revision based on specific interpretations of the epistemic entrenchment implicitly at work and of the input information. If the epistemic entrenchment stems from default rules and the input is a specific piece of evidence, then AGM revision is a matter of changing plausible conclusions, and iterated revision makes no sense. However, if the epistemic entrenchment encodes uncertain factual evidence and the input information as well, then iterated revision reduces to prioritized merging. A third problem where iteration makes sense corresponds to the revision, by the addition of new default rules, of a conditional knowledge base describing background information. The three scenarios are compared with similar problems in the framework of probabilistic reasoning.

In this paper, we introduce a new way of looking at fuzzy intervals. Instead of considering them as fuzzy sets, we see them as crisp sets of entities we call gradual (real) numbers. They are a gradual extension of real numbers, not of intervals. Such a concept is apparently missing in fuzzy set theory. Gradual numbers basically have the same algebraic properties as real numbers, but they are functions. A fuzzy interval is then viewed as a pair of fuzzy thresholds, which are monotonic gradual real numbers. This view enables interval analysis to be directly extended to fuzzy intervals, without resorting to alpha-cuts, in agreement with Zadeh's extension principle. Several results show that interval analysis methods can be directly adapted to fuzzy interval computation where end- points of intervals are changed into left and right fuzzy bounds. Our approach is illustrated on two known problems: computing fuzzy weighted averages and determining fuzzy floats and latest starting times in activity network scheduling.

Fuzzy modifiers are unary operators on fuzzy sets aiming at transforming a fuzzy set into another. In this paper, we propose a new approach to construct representation for fuzzy modifiers. The approach relies on a tolerance relation modeled by a suitable parameterized proximity relation. The newly introduced fuzzy modifiers are not only endowed with clear semantics, but they result in significant changes on the constituent parts of a fuzzy set. We also show how this class of fuzzy modifiers can be applied for modeling weakening and intensifying linguistic hedges.

When multiple sources provide information about the same unknown quantity, their fusion into a synthetic interpretable message is often a tedious problem, especially when sources are conflicting. In this paper, we propose to use possibility theory and the notion of maximal coherent subsets, often used in logic-based representations, to build a fuzzy belief structure that will be instrumental both for extracting useful information about various features of the information conveyed by the sources and for compressing this information into a unique possibility distribution.

Possibilistic logic is essentially a formalism for handling qualitative uncertainty with an inference machinery that remains close to the one of classical logic. It is capable of handling graded modal information under the form of certainty levels attached to classical logic formulas. Such lower bounds of necessity measures are associated to the corresponding pieces of belief. This paper proposes extensions of the possibilistic logic calculus where such weighted formulas can be attached to a set of agents or which can be embedded inside another weighted formula, for the expression of mutual beliefs. It is possible to express that all the agents in a subset have some beliefs, or that there is at least one agent in a subset that has a particular belief. The case of all-or-nothing beliefs is first dealt with before presenting the inference rules for handling graded beliefs held by multiple agents. Illustrative examples are provided. The proposed framework offers a reasonable compromise between expressive power and a computational cost close to the one of classical logic.

A general approach to practical inference with gradual implicative rules and fuzzy inputs is presented. Gradual rules represent constraints restricting outputs of a fuzzy system for each input. They are tailored for interpolative reasoning. Our approach to inference relies on the use of inferential independence. It is based on fuzzy output computation under an interval-valued input. A double decomposition of fuzzy inputs is done in terms of α-cuts and in terms of a partitioning of these cuts according to areas where only a few rules apply. The case of one and two dimensional inputs is considered.

Uncertain relations between temporal points are represented by means of possibility distributions over the three basic relations precedes, equals, and follows. Operations for computing inverse relation, for composing relations, for combining relations coming from different sources and pertaining to the same temporal points, or for representing negative information are defined. An illustrative example of representation and reasoning with uncertain temporal relations is provided. This article shows how possibilistic temporal uncertainty can be handled in the setting of point algebra. Moreover, the article emphasizes the advantages of the possibilistic approach over a probabilistic approach previously proposed. This work does for the temporal point algebra what the authors previously did for the temporal interval algebra. © 2007 Wiley Periodicals, Inc. Int J Int Syst 22: 157–179, 2007.

Aggregation operators are often needed when building preference relations in multicriteria decision making problems. Most existing approaches have limitations due to incomparability between decisions or ties due to the use of some aggregation operations that produce a ranking. The natural way of overcoming the lack of discrimination power is to refine the obtained ranking. We bring an overview of methods that enable aggregation-based rankings to be refined, generalizing concepts like discrimin (max), leximin (max), and Lorentz orderings that refine such aggregation operations like the minimum (the maximum) and the sum.

Commuting is an important property in any two-step information merging procedure where the results should not depend on the order in which the single steps are performed. We investigate the property of commuting for aggregation operators in connection with their relationship to bisymmetry. In case of bisymmetric aggregation operators we show a sufficient condition ensuring that two operators commute, while for bisymmetric aggregation operators with neutral element we even provide a full characterization of commuting n-ary operators by means of unary distributive functions. The case of associative operations, especially uninorms, is considered in detail.

This paper proposes a first comparative study of the expressive power of two approaches to the representation of preferences: conditional preferences networks (CP-nets) and a logical preference representation framework, namely possibilistic logic. It is shown that possibilistic logic, using a method for handling symbolic priority weights, can always provide complete preorders compatible with the partial CP-net order. Although CP-nets provide an intuitive appealing setting for expressing preferences, possibilistic logic appears to be somewhat more flexible for that purpose.

Random variability and imprecision are two distinct facets of the uncertainty affecting parameters that influence the assessment of risk. While random variability can be represented by probability distribution functions, imprecision (or partial ignorance) is better accounted for by possibility distributions (or families of probability distributions). Because practical situations of risk computation often involve both types of uncertainty, methods are needed to combine these two modes of uncertainty representation in the propagation step. A hybrid method is presented here, which jointly propagates probabilistic and possibilistic uncertainty. It produces results in the form of a random fuzzy interval. This paper focuses on how to properly summarize this kind of information; and how to address questions pertaining to the potential violation of some tolerance threshold. While exploitation procedures proposed previously entertain a confusion between variability and imprecision, thus yielding overly conservative results, a new approach is proposed, based on the theory of evidence, and is illustrated using synthetic examples.

The profile method gives a tool to perform fuzzy interval computation under a condition of local monotony of considered functions. This is a plain extension of interval analysis to fuzzy intervals, viewed as pairs of fuzzy bounds. This method yields exact results without applying interval analysis to alpha-cuts. After a refresher on the notion of profile and its use in fuzzy interval analysis, we adapt the profile method to the computation of the empirical variance of a tuple of fuzzy intervals. To this end, we first reconsider results obtained by Ferson et al. on computation of the empirical variance of a set of intervals. Finally we apply our results to the definition of the variance of a single fuzzy interval, viewed as a family of its alpha-cuts, and compare this definition to previous ones

Inductive logic programming (ILP) is a generic tool aiming at learning rules from relational databases. Introducing fuzzy sets arid fuzzy implication connectives in this framework allows us to increase the expressive power of the induced rules while keeping the readability of the rules. Moreover, fuzzy sets facilitate the handling of numerical attributes by avoiding crisp and arbitrary transitions between classes. In this paper, the meaning of a fuzzy rule is encoded by its implication operator, which is to be determined in the learning process. An algorithm is proposed for inducing first order rules having fuzzy predicates, together with the most appropriate implication operator. The benefits of introducing fuzzy logic in ILP and the validation process of what has been learnt are discussed and illustrated on a benchmark

The use of fuzzy sets to describe associations between data extends the types of relationships that may be represented, facilitates the interpretation of rules in linguistic terms, and avoids unnatural boundaries in the partitioning of the attribute domains. In addition, the partial membership values provide a method for incorporating the distribution of the data into the assessment of a rule. This paper investigates techniques to identify and evaluate associations in a relational database that are expressible by fuzzy if-then rules. Extensions of the classical confidence measure based on the /spl alpha/-cut decompositions of the fuzzy sets are proposed to incorporate the distribution of the data into the assessment of a relationship and identify robustness in an association. A rule learning strategy that discovers both the presence and the type of an association is presented.

We introduce a new method for computing functions of fuzzy intervals under various monotonicity assumptions on the concerned functions. Our method makes exact computation for all possibility degrees, without resorting to /spl alpha/-cuts. We formally present the notion of left and right profiles of fuzzy intervals as a tool for fuzzy interval computation. Several results show that interval analysis methods can be directly adapted to fuzzy interval computation where end point of intervals are changed into left and right profiles. Our approach is illustrated by numerous simple examples all along the paper, and a special section is devoted to the application of these concepts to different known problems.

Uncertain relations between temporal points are represented by means of possibility distributions over the three basic relations "smaller than", "equal to", and "greater than". Operations for computing inverse relations, for composing relations, for combining relations coming from different sources and pertaining to the same temporal points, or for representing negative information, are defined. An illustrative example of representing and reasoning with uncertain temporal relations is given. This paper shows how possibilistic temporal uncertainty can be handled in the setting of point algebra. Moreover, the paper emphasizes the advantages of the possibilistic approach over a probabilistic approach previously proposed. This work does for the temporal point algebra what the authors previously did for the temporal interval algebra.

An accepted belief is a proposition considered likely enough by an agent, to be inferred from as if it were true. This paper bridges the gap between probabilistic and logical representations of accepted beliefs. To this end, natural properties of relations on propositions, describing relative strength of belief are augmented with some conditions ensuring that accepted beliefs form a deductively closed set. This requirement turns out to be very restrictive. In particular, it is shown that the sets of accepted belief of an agent can always be derived from a family of possibility rankings of states. An agent accepts a proposition in a given context if this proposition is considered more possible than its negation in this context, for all possibility rankings in the family. These results are closely connected to the non-monotonic 'preferential' inference system of Kraus, Lehmann and Magidor and the so-called plausibility functions of Friedman and Halpern. The extent to which probability theory is compatible with acceptance relations is laid bare. A solution to the lottery paradox, which is considered as a major impediment to the use of non-monotonic inference is proposed using a special kind of probabilities (called lexicographic, or big-stepped). The setting of acceptance relations also proposes another way of approaching the theory of belief change after the works of Gärdenfors and colleagues. Our view considers the acceptance relation as a primitive object from which belief sets are derived in various contexts.

This paper provides an overview of possibility theory, emphasizing its historical roots and its recent developments. Possibility theory lies at the crossroads between fuzzy sets, probability and nonmonotonic reasoning. Possibility theory can be cast either in an ordinal or in a numerical setting. Qualitative possibility theory is closely related to belief revision theory, and commonsense reasoning with exception-tainted knowledge in Artificial Intelligence. It has been axiomatically justified in a decision-theoretic framework in the style of Savage, thus providing a foundation for qualitative decision theory. Quantitative possibility theory is the simplest framework for statistical reasoning with imprecise probabilities. As such it has close connections with random set theory and confidence intervals, and can provide a tool for uncertainty propagation with limited statistical or subjective information.

This article proposes a principled approach to multicriteria decision making (MCDM) where the worth of decisions along attributes is not supposed to be quantified, as in multiattribute utility theory, or even measured on a unique scale. This approach actually generalizes additive concordance rules a la Electre and is rigorously justified in an axiomatic way by representation theorems. We indeed show that the use of a generalized concordance (GC) rule is the only possible approach when in a purely ordinal framework and that the satisfaction of very simple principles forces the use of possibility theory as the unique way of expressing the importance of coalitions of criteria. © 2003 Wiley Periodicals, Inc.

This article expresses the idea that information encoded on a computer may have a negative or positive emphasis. Negative information corresponds to the statement that some situations are impossible. Often, it is the case for pieces of background knowledge expressed in a logical format. Positive information corresponds to observed cases. It is encountered often in data-driven mathematical models, learning, etc. The notion of an “if …, then …” rule is examined in the context of positive and negative information. It is shown that it leads to the three-valued representation of a rule, after De Finetti, according to which a given state of the world is an example of the rule, a counterexample to the rule, or is irrelevant for the rule. This view also sheds light on the typology of fuzzy rules. It explains the difference between a fuzzy rule modeled by a many-valued implication and expressing negative information and a fuzzy rule modeled by a conjunction (a la Mamdani) and expressing positive information. A new compositional rule of inference adapted to conjunctive rules, specific to positive information, is proposed. Consequences of this framework on interpolation between sparse rules are also presented. © 2003 Wiley Periodicals, Inc.

This paper deals with the extraction of default rules from a database of examples. The proposed approach is based on a special kind of probability distributions, called "big-stepped probabilities", which are known to provide a semantics for non-monotonic reasoning. The rules which are learnt are genuine default rules, which could be used (under some conditions) in a non-monotonic reasoning system and can be encoded in possibilistic logic.

Queries to a database can be made more powerful by allowing flexibility in the specification of what has to be retrieved, and by referring to cases either for expressing the request, or for computing the answer. In this paper, we present an implemented information system (applied to a database describing houses to let), based on an approach developed in the fuzzy set and possibility theory setting. This provides a unified framework for expressing users' preferences about what they are looking for, for weighting the importance of requirements, for referring to examples that they like and/or counter-examples that they dislike, and for making case-based predictions. Thus information querying goes beyond the retrieving of items from a database, and involves associated tools which help the user to figure out the actual contents of the database.

This paper proposes a fuzzy set-based approach for handling relative orders of magnitude stated in terms of closeness and negligibility relations. At the semantic level, these relations are represented by means of fuzzy relations controlled by tolerance parameters. A set of sound inference rules, involving the tolerance parameters, is provided, in full accordance with the combination/projection principle underlying the approximate reasoning method of Zadeh. These rules ensure a local propagation of fuzzy closeness and negligibility relations. A numerical semantics is then attached to the symbolic computation process. Required properties of the tolerance parameter are investigated, in order to preserve the validity of the produced conclusions. The effect of the chaining of rules in the inference process can be controlled through the gradual deterioration of closeness and negligibility relations involved in the produced conclusions. Finally, qualitative reasoning based on fuzzy closeness and negligibility relations is used for simplifying equations and solving them in an approximate way, as often done by engineers who reason about a mathematical model. The problem of handling qualitative probabilities in reasoning under uncertainty is also investigated in this perspective.

Queries to a database can be made more powerful and user friendly by referring to cases, either for expressing the request, or for computing the answer. This requires some similarity-based reasoning facilities. In this paper, we present an implemented information system (applied to a database describing house renting), based on an approach developed in the fuzzy set and possibility theory setting. This provides a unified framework for: expressing user's preferences about what he is looking for; weighting the importance of requirements; expressing similarity relations; referring to examples that he/she likes and/or counter-examples that he/she dislikes; and for making case-based predictions.

The notion of independence is central in many information processing areas, such as multiple criteria decision making, databases, or uncertain reasoning. This is especially true in the later case, where the success of Bayesian networks is basically due to the graphical representation of independence they provide. This paper first studies qualitative independence relations when uncertainty is encoded by a complete pre-order between states of the world. While a lot of work has focused on the formulation of suitable definitions of independence in uncertainty theories our interest in this paper is rather to formulate a general definition of independence based on purely ordinal considerations, and that applies to all weakly ordered settings. The second part of the paper investigates the impact of the embedding of qualitative independence relations into the scale-based possibility theory. The absolute scale used in this setting enforces the commensurateness between local pre-orders (since they share the same scale). This leads to an easy decomposability property of the joint distributions into more elementary relations on the basis of the independence relations. Lastly we provide a comparative study between already known definitions of possibilistic independence and the ones proposed here.

This paper investigates to what extent a purely symbolic approach to decision making under uncertainty is possible, in the scope of artificial intelligence. Contrary to classical approaches to decision theory, we try to rank acts without resorting to any numerical representation of utility or uncertainty, and without using any scale on which both uncertainty and preference could be mapped. Our approach is a variant of Savage's where the setting is finite, and the strict preference on acts is a partial order. It is shown that although many axioms of Savage theory are preserved and despite the intuitive appeal of the ordinal method for constructing a preference over acts, the approach is inconsistent with a probabilistic representation of uncertainty. The latter leads to the kind of paradoxes encountered in the theory of voting. It is shown that the assumption of ordinal invariance enforces a qualitative decision procedure that presupposes a comparative possibility representation of uncertainty, originally due to Lewis, and usual in nonmonotonic reasoning. Our axiomatic investigation thus provides decision-theoretic foundations to the preferential inference of Lehmann and colleagues. However, the obtained decision rules are sometimes either not very decisive or may lead to overconfident decisions, although their basic principles look sound. This paper points out some limitations of purely ordinal approaches to Savage-like decision making under uncertainty, in perfect analogy with similar difficulties in voting theory.

A formal framework of instance-based prediction is presented in which the generalization beyond experience is founded on the concepts of similarity and possibility. The underlying extrapolation principle is formalized within the framework of fuzzy rules. Thus, instance-based reasoning can be realized as fuzzy set-based approximate reasoning. More precisely, our model makes use of so-called possibility rules. These rules establish a relation between the concepts of similarity and possibility, which takes the uncertain character of similarity-based inference into account: inductive inference is possibilistic in the sense that predictions take the form of possibility distributions on the set of outcomes, rather than precise (deterministic) estimations. The basic model is extended by means of fuzzy set-based modeling techniques. This extension provides the basis for incorporating domain-specific (expert) knowledge. Thus, our approach favors a view of instance-based reasoning according to which the user interacts closely with the system.

This paper extends the possibilistic approach to instance-based reasoning that has recently been developed in a companion paper. Within the framework of this approach, the similarity-guided extrapolation principle underlying instance-based learning is formalized by means of so-called possibility rules, a special type of fuzzy rules. Proceeding from this idea, a methodology has been outlined, which allows a human expert to specify a model of the inference mechanism in a linguistic way. In this paper, a method for adapting a linguistic model automatically to observed data is proposed. This extension frees the expert from specifying mathematical concepts such as similarity measures and membership functions of fuzzy sets precisely. Rather, the expert determines only the qualitative structure of the model, which is then "calibrated" bit using the cases stored in memory.

The notion of the necessary criticality (both with respect to path and to activity) of a network with imprecisely defined (by means of intervals or fuzzy intervals) activity duration times is introduced and analyzed. It is shown, in the interval case, that both the problem of asserting whether a given path is necessarily critical and the problem of determining an arbitrary necessarily critical path (more exactly, a subnetwork covering all the necessarily critical paths) are easy. The corresponding solution algorithms are proposed. However, the problem of evaluating whether a given activity is necessarily critical does not seem to be so easy. Certain conditions are formulated which, in some situations (but not in all possible situations), allow the necessary criticality of activities to be evaluated. The results obtained for networks with interval activity duration times are generalized to the case of networks with fuzzy activity duration times. Two effective algorithms for calculating the degree of necessary criticality of a fixed path, as well as an algorithm for determining the paths that are necessarily critical to the maximum degree, are proposed.

The paper discusses the benefit of using fuzzy sets in data summaries based on generalized association rules. Fuzzy sets provide a convenient interface between labels and data and allow for partial belonging to connex but distinct classes. They thus offer a robust reading of the data. Starting with fuzzy partitions of attribute domains which are meaningful for a user, a procedure is described which enables data summaries involving fuzzy quantifiers to be built, by computing fuzzy cardinalities. The difference between this new type of fuzzy summary and previous proposals is also pointed out.

The issue of understanding and modelling vagueness has been addressed by many authors, especially in the second half of the 20th Century. They were mainly philosophers, logicians, psychologists and computer scientists. Often, these authors have preferred one type or one view of vagueness, and have tried to provide some representation scheme for this view using some formalism at hand. In this paper, we provide an organized discussion of different categories of vagueness, pointing out in what circumstances they appear, with a unified view of the formalisms which can be used. Basic representation frameworks are proposed for each case. However, what they have in common leads to a trichotomy of the universe of discourse, which seems to be the common feature of the different forms of vagueness. In each situation, we examine how a fuzzy set-based representation can take place, which gives birth to a different type of fuzzy set-based construction in each case.

This paper proposes a general approach to diagnosis based on fuzzy pattern matching, making use of consistency and inclusion-based indices in the setting of possibility theory. The approach was first developed for binary attributes and single faults. It was then generalized to any kind of attributes (including multidimensional ones). The paper presents a refined representation (where a distinction is made between effects that are possible for sure and effects that are just not impossible, and where information about (ab)normal values is used). Moreover, an extension to multiple-fault diagnosis and to "cascading faults" is outlined.

The problem of combining pieces of information issued from several sources can be encountered in various fields of application. This paper aims at presenting the different aspects of information fusion in different domains, such as databases, regulations, preferences, sensor fusion, etc., at a quite general level. We first present different types of information encountered in fusion problems, and different aims of the fusion process. Then we focus on representation issues which are relevant when discussing fusion problems. An important issue is then addressed, the handling of conflicting information. We briefly review different domains where fusion is involved, and describe how the fusion problems are stated in each domain. Since the term fusion can have different, more or less broad, meanings, we specify later some terminology with respect to related problems, that might be included in a broad meaning of fusion. Finally we briefly discuss the difficult aspects of validation and evaluation. © 2001 John Wiley & Sons, Inc.

The problem of assessing the value of a candidate is viewed here as a multiple combination problem. On the one hand, a candidate can be evaluated according to different criteria, and on the other hand, several experts are supposed to assess the value of candidates according to each criterion. Criteria are not equally important, experts are not equally competent or reliable. Moreover, levels of satisfaction of criteria, or levels of confidence are only assumed to take their values in linearly ordered scales, whose nature is rather qualitative. The problem is discussed within two frameworks, the transferable belief model (TBM) and the qualitative possibility theory (QPT). They respectively offer a quantitative and a qualitative setting for handling the problem, thus providing a way to emphasize what are the underlying assumptions in each approach. © 2001 John Wiley & Sons, Inc.

Fuzzy logic is known for providing a convenient tool for interfacing linguistic categories with numerical data and for expressing user's preference in a gradual and qualitative way. Fuzzy set methods have been already applied to the representation of flexible queries and to the modeling of uncertain pieces of information in databases systems, as well as in information retrieval. This methodology seems to be even more promising in multimedia databases which have a complex structure and from which documents have to be retrieved and selected not only from their contents, but also from "the idea" the user has of their appearance, through queries specified in terms of user's criteria. This paper provides a preliminary investigation of the potential applications of fuzzy logic in multimedia databases. The problem of comparing semistructured documents is first discussed. Querying issues are then more particularly emphasized. We distinguish two types of request, namely, those which can be handled within some extended version of an SQL-like language and those for which one has to elicit user's preference through examples.

Deals with relative orders of magnitude reasoning that handles notions such as closeness (Cl) and negligibility (Ne), by means of fuzzy relations. A set of inference rules describes how these relations can be composed and how they behave with respect to addition and product. Fuzzy numbers play the role of parameters underlying the semantics of Cl and Ne. Some of rules lead to conclusions involving closeness relations which are no longer symmetric. We propose symmetric variants of these rules. The results provided by these variants are sound but not complete; although the symbolic reasoning is made easier. We show that this type of reasoning can be used for proving the incoherence of set of equations or finding approximate solutions thereof.

This paper deals with the fuzzy project scheduling approach, where fuzzy intervals model uncertain durations of tasks. While it is easy to compute fuzzy earliest starting dates of tasks in the critical path method, the problem of determining latest starting dates and slack times is much more tricky and has never been solved in a fully satisfactory manner in the past. Here, we propose a rigorous treatment of this problem in series-parallel graphs, in the framework of possibility theory. The main difficulty lies in the fact that the variation of latest starting dates and slack times, as a function of task durations, is not straightforward to predict for general graph topologies. However, it is easier in the case of series-parallel graphs. The case of interval-valued durations is first addressed, and then extended to fuzzy intervals.

Causal diagnosis deals with the search for plausible causes which may have produced observed effects. Knowledge about possible effects of a malfunction on a given attribute is represented by a possibility distribution, as well as the possible values of an observed attribute (giving the imprecision of the observation). Any kind of attributes (binary, numerical, etc.) is allowed. In this paper, we restrict to single-fault diagnosis. Two main indices, respectively based on consistency and on abduction, enable one to discriminate the malfunctions. The case where one deals with imprecise information only is first discussed and exemplified. The extension to information pervaded with uncertainty is then studied. Refinements of indices are also considered.

This paper proposes an approach to the interpolation between sparse fuzzy rules, founded on a unique principle which supplements the classical approximate reasoning machinery. The case of rules of the form A/spl rarr/B, where A and B are intervals is first discussed, and then extended to fuzzy sets.

This short overview paper points out the striking similarity between decision under uncertainty and multicriteria decision making problems, two areas which have been developed in an almost completely independent way until now. This pertains both to additive and non-additive (including qualitative) approaches existing for the two decision paradigms. This leads to an emphasis on the remarkable formal equivalence between postulates underlying these approaches (like between the “sure-thing principle” and mutual preferential independence of criteria). This analogy is exploited by surveying classical results as well as very recent advances. This unified view should be fruitful for a better understanding of the postulates underlying the approaches, for cross-fertilization, and for adapting artificial intelligence uncertainty representation frameworks to preference modelling. © 2000 John Wiley & Sons, Inc.

This paper investigates simple syntactic methods to revise prioritized belief bases, that are semantically meaningful in the frameworks of possibility theory and of Spohn's (1988) ordinal conditional functions. Here, revising prioritized belief bases amounts to conditioning a distribution function on interpretations. Different types of scales for priorities are discussed: finite vs. infinite, numerical vs. ordinal. Syntactic revision is envisaged as a process which transforms prioritized belief bases into a new prioritized belief base, and thus allows for the subsequent iteration.

This paper describes a logical machinery for computing decisions, where the available knowledge on the state of the world is described by a possibilistic propositional logic base (i.e., a collection of logical statements associated with qualitative c

This paper provides a brief survey and an introduction to the modeling capabilities of qualitative possibility theory in decision analysis for the representation and the aggregation of preferences, for the treatment of uncertainty and for the handling of situations similar to previously encountered ones. “Qualitative” here means that we restrict ourselves to linearly ordered valuation sets (only the ordering of the grades is meaningful) for the assessment of preferences, uncertainty and similarity. Moreover, all the evaluations refer to the same valuation set (commensurability assumption). Such a qualitative structure is poor but not very demanding from an elicitation point of view; however, it is sufficient for giving birth to a valuable set of modeling tools. ©1999 John Wiley & Sons, Inc.

This paper improves a previously proposed axiomatic setting for qualitative decision under uncertainty in the von Neumann and Morgenstern' style, where only ordinal linear scales are required for assessing uncertainty and utility. Two qualitative criteria are axiomatized in a finite setting: a pessimistic one and an optimistic one, respectively obeying an uncertainty aversion axiom and an uncertainty-attraction axiom. These criteria generalize the well-known maximin and maximax criteria, making them more realistic. They are suited to one-shot decisions and they are not based on the notion of mean value, but take the form of medians. Elements for a qualitative case-based decision methodology are also proposed, with pessimistic and optimistic evaluations formally similar to the expressions which cope with uncertainty, up to modifying factors which cope with the lack of normalization of similarity evaluations. Finally two extensions of the model are analysed: (i) the case of generalized possibilistic mixtures, using a t-norm instead of min, and (ii) the case of evaluating either preferences or uncertainty on Cartesian products of ordinal scales.

Default pieces of information of the form, 'generally, if α then β' can be modelled by constraints expressing that, when α is true, β is more plausible than its negation. In previous works, the authors have cast this view in the framework of comparative possibility theory, showing that a set of default rules is equivalent to a set of comparative possibility distributions, each encoding an epistemic state. A representation theorem in terms of this semantics, for default reasoning obeying the System P of postulates proposed by Kraus, Lehmann and Magidor, has been obtained. This paper offers a detailed analysis of the structure of comparative possibility distributions representing default knowledge, by laying bare two different relations between epistemic states: the specificity ordering and the informativeness ordering. It is shown that the representation theorem still holds when restricting to linear comparative possibility distributions. They correspond to all the possible completions of the default knowledge by means of a so-called completion rule of inference. As a consequence of this result we provide a standard probabilistic semantics to System P, without referring to infinitesimals (used in Adams' semantics, revisited by Pearl). It relies on a special family of probability measures, that we call big-stepped probabilities, recently considered by Snow.

This paper presents the possibilistic Petri net model which combines possibility logic with Petri nets with objects. The main feature of this model is to allow one to reason about the aspects of uncertainty and change in dynamic discrete event systems. The paper presents relevant concepts of Petri nets with objects and possibility logic and how imprecision and vagueness are introduced in the marking of a Petri net with objects. The marking of a net is imprecise, or in a more general way, fuzzy, in order to represent an ill-known knowledge about a system state. A new marking updating according to the fuzzy marking such defined is also discussed. An example of shop door monitoring is presented that illustrates our approach.

This paper is an attempt at providing a fuzzy set formalization of case-based reasoning and decision. Learning aspects are not considered here. The proposed approach assumes a principle stating that “the more similar are the problem description attributes, the more similar are the outcome attributes.” A weaker form of this principle concluding only on the graded possibility of the similarity of the outcome attributes, is also considered. These two forms of the case-based reasoning principle are modelled in terms of fuzzy rules. Then an approximate reasoning machinery taking advantage of this principle enables us to apply the information stored in the memory of previous cases to the current problem. A particular instance of case-based reasoning, named case-based decision, is especially investigated. A logical formalization of the basic case-based reasoning inference is also proposed. Extensions of the proposed approach in order to handle imprecise or fuzzy descriptions or to manage more general forms of the principle underlying case-based reasoning are briefly discussed in the conclusion. © 1998 John Wiley & Sons, Inc.

In this paper, a careful analysis of interval-valued possibilistic knowledge bases indicates that there exists a natural probability distribution over the set of orderings of formulae compatible with the weights given in the knowledge base. We propose a new view, by which a possibilistic knowledge base can be considered in term of such probability distribution. It reveals some interconnections between probabilistic and possibilistic logics. We show that the principle of minimum specificity, widely used in possibilistic logic, is a special case of the principle of maximum likehood (at least, from the standpoint of nonmonotonic reasoning). We propose a formula to calculate probability for a defeasible conclusion. Moreover, the proposed view seems to be useful for other practical purposes. As an example, we apply it to a traditional problem of fusion of possibilistic knowledge from many sources and derive a new solution.

In the context of regular relational databases, functional dependencies have received a lot of attention, since they capture some semantics about the data related to redundancy. Functional dependencies lead to an appropriate design of a database in terms of a set of relations and can make the checking process of integrity constraints significantly easier. For about 10 years, several proposals to deal with ill-known information in database management systems have been made, and extensions of the relational data model have been proposed accordingly. In this context, the idea of fuzzy functional dependency has emerged to extend the classical functional dependency, and several definitions have been proposed. In this article, an overview of these different proposals is provided, and the connection between fuzzy functional dependencies and database design is discussed. In addition, some semantics and use of fuzzy functional dependencies are suggested. © 1998 John Wiley & Sons, Inc.

Checking the coherence of a set of rules is an important step in knowledge base validation. Coherence is also needed in the field of fuzzy systems. Indeed, rules are often used regardless of their semantics, and it sometimes leads to sets of rules that make no sense. Avoiding redundancy is also of interest in real-time systems for which the inference engine is time consuming. A knowledge base is potentially inconsistent or incoherent if there exists a piece of input data that respects integrity constraints and that leads to logical inconsistency when added to the knowledge base. We more particularly consider knowledge bases composed of parallel fuzzy rules. Then, coherence means that the projection on the input variables of the conjunctive combination of the possibility distributions representing the fuzzy rules leaves these variables completely unrestricted (i.e., any value for these variables is possible) or, at least, not more restrictive than integrity constraints. Fuzzy rule representations can be implication-based or conjunction-based; we show that only implication-based models may lead to coherence problems. However, unlike conjunction-based models, they allow to design coherence checking processes. Some conditions that a set of parallel rules has to satisfy in order to avoid inconsistency problems are given for certainty or gradual rules. The problem of redundancy, which is also of interest for fuzzy knowledge bases validation, is addressed for these two kinds of rules.

The fault mode effects and criticality analyses (FMECA) describe the impact of identified faults. They form an important category of knowledge gathered during the design phase of a satellite and are used also for diagnosis activities. This paper proposes their extension, allowing a finer representation of the available knowledge, at approximately the same cost, through the introduction of an appropriate representation of uncertainty and incompleteness based on Zadeh's possibility theory and fuzzy sets. The main benefit of the approach is to provide a qualitative treatment of uncertainty where we can for instance distinguish manifestations which are more or less certainly present (or absent) and manifestations which are more or less possibly present (or absent) when a given fault is present. In a second step, the proposed approach is extended to handle fault impacts expressed as event chronologies. Efficient, real-time compatible discrimination techniques exploiting uncertain observations are introduced, and an example of satellite fault diagnosis illustrates the method. A brief rationale for the choice of possibility theory and fuzzy sets is provided.

This paper advocates the use of nonpurely probabilistic approaches to higher-order uncertainty. One of the major arguments of Bayesian probability proponents is that representing uncertainty is always decision-driven and as a consequence, uncertainty should be represented by probability. Here we argue that representing partial ignorance is not always decision-driven. Other reasoning tasks such as belief revision for instance are more naturally carried out at the purely cognitive level. Conceiving knowledge representation and decision-making as separate concerns opens the way to nonpurely probabilistic representations of incomplete knowledge. It is pointed out that within a numerical framework, two numbers are needed to account for partial ignorance about events, because on top of truth and falsity, the state of total ignorance must be encoded independently of the number of underlying alternatives. The paper also points out that it is consistent to accept a Bayesian view of decision-making and a non-Bayesian view of knowledge representation because it is possible to map nonprobabilistic degrees of belief to betting probabilities when needed. Conditioning rules in non-Bayesian settings are reviewed, and the difference between focusing on a reference class and revising due to the arrival of new information is pointed out. A comparison of Bayesian and non-Bayesian revision modes is discussed on a classical example.

The specification of appropriate procedures for making inferences in the context of uncertain, incomplete or imprecise information is a key research issue in a variety of disciplines. Within and among these disciplines, great debates have occurred about the meaning and appropriateness of various proposals for reasoning under uncertainty. At the core of many of these debates are disagreements as to the appropriate meaning of the term "uncertainty", the related term "probability", and what it means to be unsure of one's own uncertainties. This latter issue, uncertainty about one's uncertainty, is commonly referred to as higher order uncertainty. This paper provides a brief overview of various perspectives in higher order uncertainty.

The problem of modeling expert knowledge about numerical parameters in the field of reliability is reconsidered in the framework of possibility theory. Usually expert opinions about quantities such as failure rates are modeled, assessed, and pooled in the setting of probability theory. This approach does not seem to always be natural since probabilistic information looks too rich to be currently supplied by individuals. Indeed, information supplied by individuals is often incomplete, imprecise rather than tainted with randomness. Moreover, the probabilistic framework looks somewhat restrictive to express the variety of possible pooling modes. In this paper, the authors formulate a model of expert opinion by means of possibility distributions that are thought to better reflect the imprecision pervading expert judgments. They are weak substitutes to unreachable subjective probabilities. Assessment evaluation is carried out in terms of calibration and level of precision, respectively, measured by membership grades and fuzzy cardinality indexes. Finally, drawing from previous works on data fusion using possibility theory, the authors present various pooling modes with their formal model under various assumptions concerning the experts. A comparative experiment between two computerized systems for expert opinion analysis has been carried out, and its results are presented in this paper.>

The paper proposes a parallel survey of revision and updating operations available in the probability theory and in the possibility theory frameworks. In these two formalisms the current state of knowledge is generally represented by a [0,1]-valued function whose domain is an exhaustive set of mutually exclusive possible states of the world. However, in possibility theory, the unit-interval can be viewed as a purely ordinal scale. Two general kinds of operations can be defined on this assignment function: conditioning, and imaging (or “projection”). the difference between these two operations is analogous to the one made between belief revision à la Gärdenfors and updating à la Katsuno and Mendelzon in the logical framework. In the probabilistic framework these two operations are respectively Bayesian conditioning and Lewis' imaging. Counterparts to these operations are presented for the possibilistic framework including the case of conditioning upon uncertain observations, and justifications are given which parallel the ones existing for the probabilistic operations. More particularly, it is recalled that possibilistic conditioning satisfies all the postulates proposed by Alchourrón, Gärdenfors and Makinson for belief revision (stated in possibilistic terms), and it is proved that possibilistic imaging satisfies all the postulates proposed by Katsuno and Mendelzon. the situation where our current knowledge is stated in terms of weighted logical propositions is discussed in connection to possibility theory. Revision in other more complex numerical formalisms, namely belief and plausibility functions, and upper and lower probabilities is also surveyed. Recent results on the revision of conditional knowledge bases are also reviewed. the frameworks of belief functions, upper and lower probabilities and conditional bases are more sophisticated than the previous ones because they enable to distinguish between factual evidence and generic knowledge in a cognitive state. This, framework leads to two forms of belief revision respectively taking care of the revision of evidence and the revision of knowledge. © 1994 John Wiley & Sons, Inc.

This paper is a reply to Laviolette and Seaman's critical discussion of fuzzy set theory. Rather than questioning the interest of the Bayesian approach to uncertainty, some reasons why Bayesian find the idea of a fuzzy set not palatable are laid bare. Some links between fuzzy sets and probability that Laviolette and Seaman seem not to be aware of are pointed out. These links suggest that, contrary to the claim sometimes found in the literature, probability theory is not a special case of fuzzy set theory. The major objection to Laviolette and Seaman is that they found their critique on as very limited view of fuzzy sets, including debatable papers, while they fail to account for significant works pertaining to axiomatic derivation of fuzzy set connectives, possibility theory, fuzzy random variables, among others.>

An approach to automated deduction under uncertainty, based on possibilistic logic, is described; for that purpose we deal with clauses weighted by a degree that is a lower bound of a necessity or a possibility measure, according to the nature of the uncertainty. Two resolution rules are used for coping with the different situations, and the classical refutation method can be generalized with these rules. Also, the lower bounds are allowed to be functions of variables involved in the clauses, which results in hypothetical reasoning capabilities. In cases where only lower bounds of necessity measures are involved, a semantics is proposed in which the completeness of the extended resolution principle is proved. The relation between our approach and the idea of minimizing abnormality is briefly discussed. Moreover, deduction from a partially inconsistent knowledge base can be managed in this approach and captures a form of nonmonotonicity.>

This paper investigates the relationship between conditional objects obtained as a qualitative counterpart to conditional probabilities, and nonmonotonic reasoning. Viewed as an inference rule expressing a contextual belief, the conditional object is shown to possess all properties of a well-behaved nonmonotonic consequence relation when a suitable choice of connectives and deduction operation is made. Using previous results from Adams' conditional probabilistic logic, a logic of conditional objects is proposed. Its axioms and inference rules are those of preferential reasoning logic of Lehmann and colleagues. But the semantics relies on a three-valued truth valuation first suggested by De Finetti. It is more elementary and intuitive than the preferential semantics of Lehmann and colleagues and does not require probabilistic semantics. The analysis of a notion of consistency of a set of conditional objects is studied in the light of such a three-valued semantics and higher level counterparts of deduction theorem, modus ponens, resolution and refutation are suggested. Limitations of this logic are discussed.>

An extension of Shannon entropy to the theory or belief and evidence is analyzed. Expressed as the weighed sum of logarithms of beliefs, it is termed an index of confusion. It is shown to exhibit a pathological behavior when reaching its maximum. The alternative, linear version of this index is shown to behave properly, reaching its extremum for a natural extension of the uniform distribution. Lastly, the consonant case of nested supports of evidence, is studied thoroughly, both in the finite setting, and when the frame of discernment is a real line.

L.A. Zadeh's (1975) possibility theory is used as a general framework for modeling temporal knowledge pervaded with imprecision or uncertainty. Ill-known dates, time intervals with fuzzy boundaries, fuzzy durations, and uncertain precedence relations between events can be dealt with in this approach. An explicit representation (in terms of possibility distributions) of the available information, which may be neither precise nor certain, is maintained. Deductive patterns of reasoning involving fuzzy and/or uncertain temporal knowledge are established, and the combination of fuzzy partial pieces of information is considered. A scheduled example with fuzzy temporal windows is discussed.>

International audience

This paper provides a systematic treatment of possibly imprecisely or vaguely specified numerical quantifiers in default syllogisms, following an approach initiated by Zadeh. The obtained propagation rules are derived from simple properties of relative cardinality or, equivalently, conditional probability. Uncertainty in the description of numerical quantifiers is handled using possibility theory and, particularly, fuzzy arithmetic. The advantages of this default reasoning method are its ability to model any kind of quantifier and to build new defaults by chaining existing ones, in a rigorous manner. This approach also emphasizes the difference between two types of uncertain pieces of knowledge, i.e., conjectures versus general rules.

The theory of evidence proposed by G. Shafer is gaining more and more acceptance in the field of artificial intelligence, for the purpose of managing uncertainty in knowledge bases. One of the crucial problems is combining uncertain pieces of evidence stemming from several sources, whether rules or physical sensors. This paper examines the framework of belief functions in terms of expressive power for knowledge representation. It is recalled that probability theory and Zadeh's theory of possibility are mathematically encompassed by the theory of evidence, as far as the evaluation of belief is concerned. Empirical and axiomatic foundations of belief functions and possibility measures are investigated. Then the general problem of combining uncertain evidence is addressed, with focus on Dempster rule of combination. It is pointed out that this rule is not very well adapted to the pooling of conflicting information. Alternative rules are proposed to cope with this problem and deal with specific cases such as nonreliable sources, nonexhaustive sources, inconsistent sources, and dependent sources. It is also indicated that combination rules issued from fuzzy set and possibility theory look more flexible than Dempster rule because many variants exist, and their numerical stability seems to be better.

Knowledge representation issues related to the modelling of imprecision and uncertainty are discussed in the framework of possibility theory. Differences and relations between possibility theory, fuzzy sets, probability theory and Shafer evidence theory are presented. Then, patterns of reasoning and inference and control procedures are studied in presence of uncertainty and imprecision using a possibilistic approach. the basic ideas and the main trends are emphasized rather than the mathematical and logical foundations or the technical details of implementation which can be found in the references.

A careful distinction is made between fuzzy propositions (i.e., propositions involving vague predicates) that may have intermediary degrees of truth, and uncertain propositions (with nonvague predicates) the truth or falsity of which cannot definitely be established due to the incompleteness of the available information. Then the resolution principle is extended in the case of uncertain propositions where the uncertainty is modeled in terms of necessity measures. The alternative use of probability measures or of Shafer's belief functions is also discussed.

The first part of this paper is devoted to the presentation of a software system for jobshop scheduling of batches under due date constraints and time-table constraints on work-stations. It is based on a heuristic technique for sequencing the jobs. It is actually run in a real workshop. The second part of the parper deals with an expert system methodology currently under development for the same kind of problems. The idea is to be able to integrate two kinds of knowledge about the production process : theoretical knowledge (issued from scheduling theory) which achieves the management of time, and practical knowledge (provided by the shop-floor manager) about specific technological constraints which must be satisfied by the actual production process. These constraints are usually not taken into account at the theoretical level. The knowledge representation and processing techniques of Artificial Intelligence enable realistic schedules to be obtained by simultaneous use of both sources of information.

ks

Dempster has proposed a rule for the combination of uncertain items of information issued from several sources. This note proves the unicity of this rule under an independence assumption. the existence of alternative rules is stressed, some corresponding to different assumptions, others pertaining to different types of combination.