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.

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.

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

International audience

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.

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.

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.

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.

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.

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.

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

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.

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

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.

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

International audience