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.

Analogical proportions are statements of the form “α is to β as γ is to δ”, noted α:β::γ:δ, and can be understood as “α differs from β as γ differs from δ” and conversely “β differs from α as δ differs from γ”. In this paper, α, β, γ, δ are supposed to be propositional logic formulas, which are appropriate for representing concepts. There exists one approach, developed over the last 15 years, where “α differs from β” is understood in terms of the negation of the material implication α → β. The paper investigates another view where “α differs from β” is interpreted in terms of transformations where some variables become false, some variables become true, and some variables become irrelevant. Both approaches satisfy the three basic postulates of analogical proportions (reflexivity, symmetry, and stability under central permutation), as well as other interesting properties such as transitivity and unicity of δ such that α:β::γ:δ. However, the two approaches depart from each other since they do not validate the same analogical proportions. In particular, when p,q,r are atoms the proportion p:(p∧r)::q:(q∧r) holds in the new approach, while it fails to do so for the other. The new approach exhibits also a good behaviour with respect to integrity constraints. It is advocated that this makes it appropriate for handling analogy between concepts, while the other approach has proved to be fruitful for Boolean features-based representations. The paper provides a thorough analysis of the differences between the two approaches.

This paper offers a unified, model-agnostic, analogy-based framework for extracting relevant attributes and building contrastive explanations for a given classification. Analogical reasoning relies on the idea of comparing items by pairs to discern their similarities and differences, based on an observable sample S of data. First, adhering to this principle, we propose a pair-based approach to extract relevant attributes via an analogical relevance index (ARI) from Boolean or nominal datasets. We prove properties establishing the behavior of ARI with respect to available samples S. When comparing ARI against established methods such as χ2, mutual information, Shapley, or Sobol indices, empirical evidence highlights the appropriateness of ARI for synthetic datasets, where the classes are generated using specific Boolean functions. ARI also demonstrates robust performance across a diverse range of functions commonly encountered in real datasets. However, some synthetic datasets created from certain functions pose challenges for all indices. Second, we use analogical classification as a surrogate for explanation provision. Analogical classifiers are rooted on analogical proportions, involving the comparison of two pairs of items (a, b) and (c, d) through statements like “a differs from b as c differs from d”, denoted as a:b::c:d. To explain the classification of an item d, we search for an item c close to d but in a different class, forming a pair (c, d). Then, the analogical classifier extracts pairs (a, b) satisfying a:b::c:d leveraging the relevant features identified earlier. Finally we explain why d belongs to a class distinct from that of c by computing the frequency of pairs (a,b), mirroring the difference between c and d, that lead to the same class change. Standard local methods typically capitalize on examples within the item’s neighborhood for explanation. In contrast, our approach operates beyond the neighborhood, broadening the scope of explanatory power. Experiments on categorical synthetic and real datasets indicate that the proposed framework provides plausible and essentially human-understandable explanations.

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.

In this paper, we consider analogical proportions which are statements of the form “ a → is to b → as c → is to d → ”, understood as a comparative formulation between vectors of items described on the same set of attributes. Analogical proportions and analogical inference have been extensively studied in the last decade, in particular by the authors of this paper. Some important remarks have been made regarding these proportions on i) the role of ordered pairs in them; ii) the large number of them associated with taxonomic trees; and more recently iii) their close relationship with multi-valued dependencies. We offer a renewed presentation of these facts together with some new insights on analogical proportions, emphasizing the role of equivalence classes of ordered pairs. Moreover, not all consequences had been drawn for a better understanding of analogical inference. This is the main purpose of this paper. In particular, it is advocated that analogical proportions whose four members are equal on some attributes are better predictors in general for classification purposes than analogical proportions for which there does not exist such attribute. This is confirmed by experimental results also reported in the paper. Thus this paper can be read both as an introductory survey on recent advances on analogical proportions and as a study on the impact of particular patterns on analogical inference, a topic never considered before.

International audience

This paper presents a survey of researches in analogical reasoning whose building block are analogical proportions which are statements of the form “a is to b as c is to d”. They have been developed in the last twenty years within an Artificial Intelligence perspective. After discussing their formal modeling with the associated inference mechanism, the paper reports the main results obtained in various AI domains ranging from computational linguistics to classification, including image processing, I.Q. tests, case based reasoning, preference learning, and formal concepts analysis. The last section discusses some new theoretical concerns, and the potential of analogical proportions in other areas such as argumentation, transfer learning, and XAI.

Analogical proportions are statements of the form “x is to y as z is to t”, where x, y, z, t are items of the same nature, or not. In this paper, we more particularly consider “relational proportions” of the form “object A has the same relationship with attribute a as object B with attribute b”. We provide a formal definition for relational proportions, and investigate how they can be extracted from a formal context, in the setting of formal concept analysis.

The paper deals with a topic little studied in artificial intelligence: the understanding of humor. In this preliminary study, we try to identify the basic mechanism at work in quips and narrative jokes. It seems that in many cases a belief revision process is operating, leading to an unexpected conclusion, through the punchline of the jest. We propose a formal modeling of jokes based on belief revision. Namely the punchline, which triggers a revision, is both surprising and explains perfectly what was reported in the beginning of the joke. This also suggests a way of ranking jokes in terms of surprise and strength of explanation, using possibilistic logic.

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.

It has been observed that a particular form of analogical inference, based on analogical proportions, yields competitive results in classification tasks. Using the algebraic normal form of Boolean functions, it has been shown that analogical prediction is always exact iff the labeling function is affine. We point out that affine functions are also meaningful when using another view of analogy. We address the accuracy of analogical inference for arbitrary Boolean functions and show that if a function is epsilon-close to an affine function, then the probability of making a wrong prediction is upper bounded by 4 epsilon. This result is confirmed by an empirical study showing that the upper bound is tight. It highlights the specificity of analogical inference, also characterized in terms of the Hamming distance.

The classification of a new item may be viewed as a matter of associating it with the class where it is the least at odds w.r.t. the elements already in the class. An oddness measure of an item with respect to a multiset, applicable to Boolean features as well as to numerical ones, has been recently proposed. It has been shown that cumulating this measure over pairs or triples (rather than larger subsets) of elements in a class could provide an accurate estimate of the global oddness of an item with respect to a class. This idea is confirmed and refined in the present paper. Rather than considering all the pairs in a class, one can only deal with the pairs whose an element is one of the nearest neighbors of the item, in the target class. The oddness evaluation computed on this basis still leads to good results in terms of accuracy. One can take a step further and choose the second element in the pair also as another nearest neighbor in the class. Although the method relies on the notion of neighbors, the resulting algorithm is far from being a variant of the classical -nearest neighbors approach. The oddness with respect to a class computed only on the basis of pairs made of two nearest neighbors leads to a low complexity algorithm. Experiments on a set of UCI benchmarks show that the classifier obtained can compete with other well-known approaches.

Training set extension is an important issue in machine learning. Indeed when the examples at hand are in a limited quantity, the performances of standard classifiers may significantly decrease and it can be helpful to build additional examples. In this paper, we consider the use of analogical reasoning, and more particularly of analogical proportions for extending training sets. Here the ground truth labels are considered to be given by a (partially known) function. We examine the conditions that are required for such functions to ensure an error-free extension in a Boolean setting. To this end, we introduce the notion of Analogy Preserving (AP) functions, and we prove that their class is the class of affine Boolean functions. This noteworthy theoretical result is complemented with an empirical investigation of approximate AP functions, which suggests that they remain suitable for training set extension.

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.

We investigate the impact of uncertainty on relational data\-base schema design. Uncertainty is modeled qualitatively by assigning to tuples a degree of possibility with which they occur, and assigning to functional dependencies a degree of certainty which says to which tuples they apply. A design theory is developed for possibilistic functional dependencies, including efficient axiomatic and algorithmic characterizations of their implication problem. Naturally, the possibility degrees of tuples result in a scale of different degrees of data redundancy. Scaled versions of the classical syntactic Boyce-Codd and Third Normal Forms are established and semantically justified in terms of avoiding data redundancy of different degrees. Classical decomposition and synthesis techniques are scaled as well. Therefore, possibilistic functional dependencies do not just enable designers to control the levels of data integrity and losslessness targeted but also to balance the classical trade-off between query and update efficiency. Extensive experiments confirm the efficiency of our framework and provide original insight into relational schema design.

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.

Classification can be viewed as a matter of associating a new item with the class where it is the least at odds w.r.t. the other elements. A recently proposed oddness index applied to pairs or triples (rather than larger subsets of elements in a class), when summed up over all such subsets, provides an accurate estimate of a global oddness of an item w.r.t. a class. Rather than considering all pairs in a class, one can only deal with pairs containing one of the nearest neighbors of the item in the target class. Taking a step further, we choose the second element in the pair as another nearest neighbor in the class. The oddness w.r.t. a class computed on the basis of pairs made of two nearest neighbors leads to low complexity classifiers, still competitive in terms of accuracy w.r.t. classical approaches.

In recent works, analogy-based classifiers have been proved quite successful. They exhibit good accuracy rates when compared with standard classification methods. Nevertheless, a theoretical study of their predictive power has not been done so far. One of the main barriers has been the lack of functional definition: analogical learners have only algorithmic definitions. The aim of our paper is to complement the empirical studies with a theoretical perspective. Using a simplified framework, we first provide a concise functional definition of the output of an analogical learner. Two versions of the definition are considered, a strict and a relaxed one. As far as we know, this is the first definition of this kind for analogical learner. Then, taking inspiration from results in k-NN studies, we examine some analytic properties such as convergence and VC-dimension, which are among the basic markers in terms of machine learning expressiveness. We then look at what could be expected in terms of theoretical accuracy from such a learner, in a Boolean setting. We examine learning curves for artificial domains, providing experimental results that illustrate our formulas, and empirically validate our functional definition of analogical classifiers.

The paper investigates the use of analogical reasoning for recommendation purposes. More particularly, we address the problem of predicting missing ratings on the basis of known ones. After discussing the differences with another recently experimented approach based on analogical proportions, a new analogical approach is proposed. It relies on the intuition that “the rating of user u for item i is to the rating of user v for item i as the rating of user u for item j is to the rating of user v for item j”. This leads to algorithms yielding results close to the ones of state-of-the art approaches, when the ratings are regarded as numerical quantities. This is due to the fact that these latter approaches embed an estimation process that is implicitly close to analogy, as discussed in this paper. An analogical approach is also outlined and briefly discussed when the ratings are supposed to have an ordinal meaning only.

The paper shows that a Boolean logic modeling of analogical proportions can serve as a basis for solving quizzes as well as a common and popular type of IQ tests, namely Raven's progressive matrices. They are nonverbal tests supposedly measuring general intelligence. A 3 × 3 Raven matrix exhibits eight geometric pictures displayed as its eight first cells: the remaining ninth cell is empty. In these tests, a set of candidate pictures is also given among which the subject is asked to identify the solution. In this paper, we investigate a general approach allowing to automatically solve Raven's progressive matrices tests. The approach is based on a logical view of analogical proportions, i.e., statements of the form “A is to B as C is to D.” We assume that analogical proportions hold between the rows and between the columns of the Raven's matrix. This view can be applied to a feature-based description of the pictures but also, in a number of cases, to a very low level representation, i.e., the pixel level. It appears that the analogical proportion reading just amounts here to a recopy of patterns of feature values that already appear in the data, after checking that there is no conflicting patterns. Implementing this principle, our algorithm builds up the ninth picture, without the help of any set of candidate solutions, and only on the basis of the eight known cells of the Raven matrices. A comparison with other approaches is provided. The ability to construct the missing picture without relying on candidate solutions is a distinctive feature of our work. Moreover, we emphasize the general principle underlying the approach that offers a simple and uniform mechanism applicable to the tests. At this step, the paper makes no claim about the cognitive validity of the approach with respect to the way humans solve such tests.

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 paper introduces possibilistic functional dependencies. These dependencies are associated with a particular possibility distribution over possible worlds of a classical database. The possibility distribution reflects a layered view of the database. The highest layer of the (classical) database consists of those tuples that certainly belong to it, while the other layers add tuples that only possibly belong to the database, with different levels of possibility. The relation between the confidence levels associated with the tuples and the possibility distribution over possible database worlds is discussed in detail in the setting of possibility theory. A possibilistic functional dependency is a classical functional dependency associated with a certainty level that reflects the highest confidence level where the functional dependency no longer holds in the layered database. Moreover, the relationship between possibilistic functional dependencies and possibilistic logic formulas is established. Related work is reviewed, and the intended use of possibilistic functional dependencies is discussed in the conclusion.

International audience

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.

Entropy gain is widely used for learning decision trees. However, as we go deeper downward the tree, the examples become rarer and the faithfulness of entropy decreases. Thus, misleading choices and over-fitting may occur and the tree has to be adjusted by using an early-stop criterion or post pruning algorithms. However, these methods still depends on the choices previously made, which may be unsatisfactory. We propose a new cumulative entropy function based on confidence intervals on frequency estimates that together considers the entropy of the probability distribution and the uncertainty around the estimation of its parameters. This function takes advantage of the ability of a possibility distribution to upper bound a family of probabilities previously estimated from a limited set of examples and of the link between possibilistic specificity order and entropy. The proposed measure has several advantages over the classical one. It performs significant choices of split and provides a statistically relevant stopping criterion that allows the learning of trees whose size is well-suited w.r.t. the available data. On the top of that, it also provides a reasonable estimator of the performances of a decision tree. Finally, we show that it can be used for designing a simple and efficient online learning algorithm.

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.

This paper considers relational databases containing uncertain attribute values when some knowledge is available about the more or less certain value (or disjunction of values) that a given attribute in a tuple may take. We propose a possibility-theory-based model suited to this context and extend the operators of relational algebra to handle such relations in a “compact,” thus efficient, way. It is shown that the model is a representation system for the whole relational algebra. An important result is that the data complexity associated with the extended operators in this context is the same as in the classical database case, which makes the approach highly scalable.

Introduced a few years ago, analogy-based classification methods are a noticeable addition to the set of lazy learning techniques. They provide amazing results (in terms of accuracy) on many classical datasets. They look for all triples of examples in the training set that are in analogical proportion with the item to be classified on a maximal number of attributes and for which the corresponding analogical proportion equation on the class has a solution. In this paper when classifying a new item, we demonstrate a new approach where we focus on a small part of the triples available. To restrict the scope of the search, we first look for examples that are as similar as possible to the new item to be classified. We then only consider the pairs of examples presenting the same dissimilarity as between the new item and one of its closest neighbors. Thus we implicitly build triples that are in analogical proportion on all attributes with the new item. Then the classification is made on the basis of a majority vote on the pairs leading to a solvable class equation. This new algorithm provides results as good as other analogical classifiers with a lower average complexity.

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.

Artificial intelligence (AI) was not born ex nihilo in the mid-fifties of the XXthcentury. Beyond its immediate roots in cybernetics and in computer science that started about two decades before, its emergence is the result of a long and slow process in the history of humanity. This can be articulated around two main questions: the formalization of reasoning and the design of machines having autonomous capabilities in terms of computation and action. The aim of this paper is to gather some insufficiently known elements about the prehistory of AI in the last 350 years that precede the official birth of AI, a time period where only a few very well-known names, such as Thomas Bayes and Georges Boole, are usually mentioned in relation with AI.

The paper provides an attempt at bridging formal concept analysis and the modeling of analogical proportions (i.e., statements of the form “a is to b as c is to d”). A suitable definition for analogical proportions in non distributive lattices is proposed and then applied to concept lattices. This enables us to compute what we call proportional analogies that establish analogies on a proportional basis between pairs (a, b) and (c, d) when a and c belong to a domain and b and d to another domain (as in “Moby Dick is to Herman Melville as Alice in Wonderland is to Lewis Carroll”).

This paper proposes the notion of experience to help situate agents in their environment, providing a link on how the continually evolving environment impacts the evolution of an agent's BDI model and vice versa. Then, using the notion of shared experience as a primitive construct, we develop a novel formal model of shared intention which we believe more adequately describes social behaviour than traditional BDI logics that focus on individual agents. Whilst many philosophers have argued that collective intentionality cannot always be equated to the collection of the individual agents' intentions, there has been no AI model that addresses this issue. We believe this is the first attempt to develop an explicit notion of shared experience from an AI perspective.

International audience

An acknowledged interpretation of possibility distributions in quantitative possibility theory is in terms of families of probabilities that are upper and lower bounded by the associated possibility and necessity measures. This paper proposes a likelihood function for possibility distributions that agrees with the above-mentioned view of possibility theory in the continuous and in the discrete cases. Especially, we show that, given a set of data following a probability distribution, the optimal possibility distribution with respect to our likelihood function is the distribution obtained as the result of the probability-possibility transformation that obeys the maximal specificity principle. It is also shown that when the optimal distribution is not available, a direct application of this possibilistic likelihood provides more faithful results than approximating the probability distribution and then applying the probability possibility transformation. We detail the particular case of triangular and trapezoidal possibility distributions and we show that any unimodal unknown probability distribution can be faithfully upper approximated by a triangular distribution obtained by optimizing the possibilistic likelihood.

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.

Reasoning deductively under incomplete information is nonmonotonic in nature since the arrival of additional information may invalidate or reverse previously obtained conclusions. It amounts to apply generic default rules in an appropriate way to a particular (partially described) situation. This type of nonmonotonic reasoning can only provide plausible conclusions. Analogical reasoning is another form of commonly used reasoning that yields brittle conclusions. It is nondeductive in nature and proceeds by putting particular situations in parallel. Analogical reasoning also exhibits nonmonotonic features, as investigated in this paper when particular situations may be incompletely stated. The paper reconsiders the pattern of plausible reasoning proposed by Polya, “a and b are analogous, a is true, then b true is more credible,'' from a nonmonotonic reasoning point of view. A representation of the statement “a and b are analogous” in terms of nonmonotonic consequences relations is presented. This representation is then related to a logical definition of analogical proportions, i.e. statements of the form “a is to b as c is to d” that has been recently proposed and extended to other types of proportions. Remarkably enough, semantic equivalence between conditional objects of the form “b given a,” which have been shown as being at the root of nonmonotonic reasoning, constitutes another type of noticeable proportions. By offering a parallel between two important forms of commonsense reasoning, this paper enriches the comparison between nonmonotonic reasoning and analogical reasoning that is not often made. © 2011 Wiley Periodicals, Inc.

Inconsistencies between different information sources may arise because of statements that are inaccurate, albeit not completely false. In such scenarios, the most natural way to restore consistency is often to interpret assertions in a more flexible way, i.e. to enlarge (or relax) their meaning. As this process inherently requires extra-logical information about the meaning of atoms, extensions of classical merging operators are needed. In this paper, we introduce syntactic merging operators, based on possibilistic logic, which employ background knowledge about the similarity of atomic propositions to appropriately relax propositional statements.

The paper shows how three different types of hierarchical queries involving qualitative preference and leading to totally ordered results, which have been recently considered in the setting of division operation, can be conveniently encoded in possibilistic logic. This enables such a handling of preference queries to be interfaced with a recently proposed approach for dealing with pieces of data associated with certainty levels represented in the framework of possibilistic logic.

In this paper we propose a method for semantic text representation and term weighting. It is based on a semantic resource, WordNet, that provides meaning information and relations between the terms of a document. The heart of the proposed method is the way the concepts (terms) of documents are clustered and weighted. More precisely, we introduce two notions: the “centrality” of a term and its specificity. The centrality of a term is given by the number of terms of the document that are directly related to it in the same conceptual cluster. The “specificity” represents the depth of a concept in WordNet. These parameters are different from the usual term frequency “tf” and inverse term frequency “idf” used in classical information retrieval. This method is based on two steps: 1) matching document terms with concepts of “WordNet” in order to obtain the most appropriate ones 2) for each concept calculating its centrality using existing semantic “WordNet” relations, and its “specificity”. The preliminary experiments undertaken on TREC collections show the effective interest of these parameters.

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.

Fuzzy formal concept analysis is concernedwith formal contexts expressing scalar-valued fuzzy relationships between objects and their properties. Existing fuzzy approaches assume that the relationship between a given object and a given property is a matter of degree in a scale L (generally [0,1]). However, the extent to which "object o has property a" may be sometimes hard to assess precisely. Then it is convenient to use a sub-interval from the scale L rather than a precise value. Such formal contexts naturally lead to interval-valued fuzzy formal concepts. The aim of the paper is twofold. We provide a sound minimal set of algebraic requirements for interval-valued implications in order to fulfill the fuzzy closure properties of the resulting Galois connection. Secondly, a new approach based on a generalization of Gödel implication is proposed for building the complete lattice of all interval-valued fuzzy formal concepts.

The paper discusses a new approach to merging conflicting propositional knowledge bases which builds on the idea that consistency can often be restored by interpreting propositions more flexibly, thus enlarging their sets of models.

The paper presents a preliminary investigation of potential methods for extracting semantic views of text contents under the form of structured sets of words, which go beyond standard statistical indexing. The aim is to build kinds of fuzzily weighted structured images of semantic contents. A preliminary step consists in identifying the different types of relations (is-a, part-of, related-to, synonymy, domain, glossary relations) that exist between the words of a text, using some general ontology such as WordNet. Then taking advantage of these relations, different types of fuzzy clusters of words can be built. Moreover, apart from its frequency of occurrence, the importance of a word may be also evaluated through some estimate of its specificity. A degree of "centrality" is also computed for each word in a cluster. The size of the clusters, the frequency, the specificity and the centrality of their words are indications that enable us to build a fuzzy set of sets of words that progressively "emerge" from a text, as being representative of its contents. The ideas advocated in the paper and their potential usefulness are illustrated on a running example and on two experiments. It is expected that obtaining a better representation of the semantic contents of texts may help in particular to give indications of what the text is about to a potential reader.

The paper proposes a new approach to the handling of preferences expressed in a compact way under the form of conditional statements. These conditional statements are translated into classical logic formulas associated with symbolic levels. Ranking two alternatives then leads to compare their respective amount of violation with respect to the set of formulas expressing the preferences. These symbolic violation amounts, which can be computed in a possibilistic logic manner, can be partially ordered lexicographically once put in a vector form. This approach is compared to the ceteris paribus-based CP-net approach, which is the main existing artificial intelligence approach to the compact processing of preferences. It is shown that the partial order obtained with the CP-net approach fully agrees with the one obtained with the proposed approach, but generally includes further strict preferences between alternatives (considered as being not comparable by the symbolic level logic-based approach). These additional strict preferences are in fact debatable, since they are not the reflection of explicit user's preferences but the result of the application of the ceteris paribus principle that implicitly, and quite arbitrarily, favors father node preferences in the graphical structure associated with conditional preferences. Adding constraints between symbolic levels for expressing that the violation of father nodes is less allowed than the one of children nodes, it is shown that it is possible to recover the CP-net-induced partial order. Due to existing results in possibilistic logic with symbolic levels, the proposed approach is computationally tractable. Key words: preference, priority, partial order, CP-net, possibilistic logic.

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.

Bipolarity appears in information processing when positive and negative sides of what is specified are clearly distinct, but not complementary from each other. This distinction, which can be made in different representation settings, has been recently emphasized in the framework of possibility theory, where what is given as being guaranteed possible, can be a strict subset of what is considered as being not impossible. This leads to an original revision mechanism when new information is received, which turns to be at work in the version space view of learning. This enables us to stress the bipolar nature of the version space approach and to propose an extension of it with layered sets of examples and counterexamples. © 2008 Wiley Periodicals, Inc.

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.

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.

Many studies on machine learning, and more specifically on regression, focus on the search for a precise model, when precise data are available. Therefore, it is well-known that the model thus found may not exactly describe the target concept, due to the existence of learning bias. In order to overcome the problem of too much illusionary precise models, this paper provides a general framework for imprecise regression from non-fuzzy input and output data. The goal of imprecise regression is to find a model that has the better tradeoff between faithfulness w.r.t. data and (meaningful) precision. We propose an algorithm based on simulated annealing for linear and non-linear imprecise regression with triangular and trapezoidal fuzzy sets. This approach is compared with the different fuzzy regression frameworks, especially with possibilistic regression. Experiments on an environmental database show promising results.

This article provides a general discussion about how flexible querying can be applied to semistructured data (SSD). We adapt flexible querying ideas, already used for classically structured databases, to XQuery-like querying of SSD for managing users' priority and preferences, but also for tackling with the variability of SSD underlying structures. Indeed flexible querying seems to be still more useful for SSD than for classical databases, because of the potential structural heterogeneity of the former. Fuzzy sets are useful for expressing flexible requirements on attribute values and for estimating the degree of similarity of tags, or attribute labels, with elements present in the request. Priorities are introduced in the request for specifying the relative importance of elementary requirements in terms of their semantic contents, but also preferences about the location of information in the structure. The evaluation of the queries uses a qualitative scale with a finite number of levels, and retrieved pieces of SSD are rank-ordered using a lexicographic vector procedure. Illustrative examples are provided. © 2007 Wiley Periodicals, Inc. Int J Int Syst 22: 723–737, 2007.

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.

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.

The paper provides a discussion of the possibilistic regression method originally proposed by H. Tanaka. This method has the advantage of allowing the learning of an imprecise model, in the form of an interval-valued function. It may lead to an imprecise model even in presence of precise data, which is satisfactory from a learning point of view. Indeed, finding a precise model that perfectly represents the concept to be learned is illusory, due to the existence of the bias caused by the choice of a modeling representation space, the limited amount of data, and the possibility of missing relevant data. However, what is obtained with possibilistic regression is more an imprecise model than a genuine fuzzy one. The paper illustrates and emphasizes this point on environmental data and suggest two different approaches for learning genuine fuzzy regression models from precise data.

The paper presents a preliminary work that investigates the interest and the questions raised by the introduction of argumentation capabilities in a flexible querying system to a database. Indeed, emphasizing the positive and the negative aspects of retrieved items, or explaining why no answers are found may be of a value for the user

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

Current logic-based handling of arguments has mainly focused on explanation or justification-oriented purposes in presence of inconsistency. So only one type of argument has been considered, and several argumentation frameworks have then been proposed for generating and evaluating such arguments. However, recent works on argumentation-based negotiation have emphasized different other types of arguments such as threats, rewards, and appeals. The purpose of this article is to provide a logical setting that encompasses the classical argumentation-based framework and handles the new types of arguments. More precisely, we give the logical definitions of these arguments and their weighting systems. These definitions take into account that negotiation dialogues involve not only agents' beliefs (of various strengths), but also their goals (having maybe different priorities), as well as the beliefs on the goals of other agents. In other words, from the different beliefs and goals bases maintained by agents, all the possible threats, rewards, explanations, and appeals that are associated with them can be generated. It may also happen that an intended threat, or reward, is not perceived as such by the addressee and thus misses its target because the addresser misrepresents the addressee's goals. The proposed approach accounts for that phenomenon. Finally, we show how to evaluate conflicting arguments of different types. © 2005 Wiley Periodicals, Inc. Int J Int Syst 20: 1195–1218, 2005.

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.

Argumentation-based decision provides a way for explaining choices which are already made, and for evaluating potential choices in terms of arguments. Each potential choice has pros and cons of various strengths, which are computed in the framework of possibilistic logic. Depending on the pessimistic, or optimistic nature of the decision-maker's attitude, arguments in favour of or against a possible choice have slightly different structures. When the available, maybe uncertain, knowledge is consistent, as well as the set of prioritized goals (which have to be fulfilled as far as possible), the method for evaluating decisions on the basis of arguments agrees with the possibility theory-based approach to decision-making under uncertainty. The proposed framework can be generalized in case of partially inconsistent knowledge or goals.

Introducing fuzzy predicates in inductive logic programming may serve two different purposes: getting more expressivity by learning fuzzy rules or allowing for more adaptability when learning classical rules. On the one hand, we can thus learn gradual and certainty rules, which have an increased expressive power and have no simple crisp counterpart. On the other hand, fuzzy predicates in rules can be used for discretization when the database contains numerical attributes. In this case the fuzzy counterparts of crisp rules allow us to check the meaningfulness and the accuracy of the crisp rules. We formally describe the computation of the confidence degrees for each type of rules with fuzzy predicates. Next, we discuss the interest and the application domain of each kind of rules with fuzzy predicates.

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 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.

This paper addresses the correlation problem which is central in sensor fusion, from the viewpoint of possibility theory. This problem aims at separating pieces of information pertaining to different objects and to gather those which are likely to pertain to the same object. We present two different views of the problem, one based on similarity relations, while the other discusses the problem in a logical framework. © 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.

A tuple of fuzzy constraints defined on a discrete satisfaction scale defines a lattice structure, called relaxation space, made of the tuples of level cuts of the fuzzy constraints, equipped with the partial order induced by the scale ordering. Then choosing a way of combining the fuzzy constraints has two joint effects: usually a completion of the ordering between tuples of levels, and possibly a simplification of the relaxation space (by eliminating subsumed tuples corresponding to the same level of global satisfaction). The paper investigates the possibility of specifying the ordering between tuples of level cuts constraints on a simplified relaxation space, without resorting to the use of explicit aggregation operations. The idea is to elicit the preferences between the tuples of constraints representing various relaxations of the set of fuzzy constraints, directly from the user. The way to express these preferences in a local manner is also discussed.

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 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.

This special issue gathers eight articles which illustrate various aspects of a new trend of application-oriented researches called “Fuzzy Information Engineering.” Seven of these articles are revised and expanded versions of articles presented in a series of two invited sessions, organized by the guest editors of this special issue at the Fourth European Congress on Intelligent Techniques and Soft Computing (EUFIT'96) in Aachen, Germany on September 4, 1996. We first briefly restate what Information Engineering covers and what the contribution of fuzzy set-based methods is to this research trend, before providing a short presentation of the articles in the issue. © 1997 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 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 note investigates how various ideas of "expectedness" can be captured in the framework of possibility theory. Particularly, we are interested in trying to introduce estimates of the kind of lack of surprise expressed by people when saying "I would not be surprised that…" before an event takes place, or by saying "I knew it" after its realization. In possibility theory, a possibility distribution is supposed to model the relative levels of possibility of mutually exclusive alternatives in a set, or equivalently, the alternatives are assumed to be rank-ordered according to their level of possibility to take place. Four basic set-functions associated with a possibility distribution, including standard possibility and necessity measures, are discussed from the point of view of what they estimate when applied to potential events. Extensions of these estimates based on the notions of Q-projection or OWA operators are proposed when only significant parts of the possibility distribution are retained in the evaluation. The case of partially-known possibility distributions is also considered. Some potential applications are outlined.

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.>

This article is an abridged and translated version of a mission report initially written for the Scientific Service of the French Embassy in Japan. the mission took place in Japan from the 14th to the 21st of October, 1989. an introduction gives the necessary background concerning the applications of fuzzy sets to process control and expert systems; specialized hardwares for these applications are also introduced. Section II offers an account of the visits done during the mission. Section III synthesizes the lesson of the mission. the title makes use of the expression “fuzzy boom” which is often employed in Japan for describing the present blossoming of a great number of practical applications of fuzzy sets and their important repercussion in the media of this country.

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.

Until now, the idea of a fuzzy database has been investigated along different lines: Some authors have dealt with the imprecision of attribute values by modeling, using fuzzy similarity relations, the extent to which these values could be regarded as interchangeable. Others have used possibility distributions for representing fuzzily known or incompletely known attribute values. The first approach, which cannot accommodate incomplete information, is restated in the framework of rough sets extended to fuzzy relations. Besides, in the second one, similarity measures between attribute values can be introduced and computed; then a comparison of the two approaches is provided. The proposed similarity measure, based on a fuzzy Hausdorff distance, estimates the mismatch between two possibility distributions. From storage and query-evaluation points of view, it may be interesting to gather items having similar attribute values. Thus the similarity measures previously considered can be used for the reduction of the fuzzy database. When several items have sufficiently similar values for each attribute in a relation, the reduction is performed by taking for each attribute the union of these similar values. The consequences of the reduction process on query evaluation are studied. © 1987 John Wiley & Sons, Inc.

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.