Conditioning is an essential operation in knowledge representation and uncertainty modeling. It enables a priori beliefs to be adjusted in response to new information considered to be fully certain. This work focuses on the computation of Fagin and Halpern (FH-)conditioning in the context where uncertain information is represented by weighted or possibilistic logic belief bases. Weighted belief bases are extensions of classical logic belief bases where a weight or degree of belief is associated with each propositional logic formula. This paper proposes a characterization of the syntactic computation of the revision of weighted belief bases in the light of new information, which is in full agreement with the semantics of the FH-conditioning of possibility distributions. We show that the size of the revised belief base is linear with respect to the size of the initial base and that the computational complexity amounts to performing O ( log 2 ( n ) ) calls to the propositional logic satisfiability tests, where n is the number of different degrees of certainty used in the initial belief base. The last section of this paper examines both semantically and syntactically FH-conditioning under uncertain information, within the framework of possibility theory. • Reviews possibilistic logic and the use of weighted belief bases to represent uncertainty. • Introduces FH-conditioning within the framework of possibility theory. • Proposes a syntactic computation of FH-conditioning using three transformation steps. • Extends FH-conditioning to the case of uncertain observations. • Discusses complexity and interpretation of FH-conditioning as belief revision or update.

The presented work concerns the automatic detection of legend texts inside maps. After extracting the texts from the images using OCR tools, we use an iterative clustering process on the extracted texts. We consider five main criteria, with different levels of importance: text alignment, distance between text boxes, background color of the text, font color, and font size. For each criterion, we define appropriate similarity measures. We propose a method that combines, incrementally, the partitions obtained by each criterion. The experimental study reveals two important results. First, combining several criteria gives better results than considering a single distance metric (e.g., Euclidean distance) between text boxes. Secondly, the overall effectiveness of the priority relation, which we intuitively defined among the criteria for detecting caption texts, is confirmed.

This paper presents a method for the automatic extraction of the structure of wastewater networks from geographical maps, as well as their representation in the form of graphs. The approach consists first in detecting the different important elementary elements composing a wastewater network, such as the manholes, their identifiers (using optical character recognition, OCR), and the wastewater pipes that connect them. Detecting these elementary elements is a first difficult problem, despite many existing tools, mainly due to the quality of the wastewater network maps used. However, the challenge addressed in this paper is how to select the relevant elementary elements detected, and bring them together to finally extract the wastewater network. One of the main contributions of this paper is to propose an efficient algorithm to solve these selection and assignment problems (e.g., manhole identifiers to manholes represented by circles). We also deal with the situation of isolated nodes to have the most connected clusters possible. The experimental results conducted on real map data show very promising results despite the low quality of the maps.

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

The representation and combination of imprecise information is an important topic present in many applications. This paper first deals with the representation of imprecise positions of objects detected from maps and images of urban networks. In particular, it deals with the question of the combination of uncertain information, from different sources, to address the problem of inaccuracies related to the geographical coordinates of the detected objects. To illustrate the representation and the combination modes presented in this paper, we focus on wastewater networks data. More precisely, we use the manhole detection problem as an example of object detection in our study. We will use two sources of data: i) the images obtained from the google street view utility and ii) the maps of the sanitation networks. As the geographical positions of the detected objects are imprecise, we will use possibility theory to represent this uncertainty. Possibility theory is particularly suitable for representing qualitative uncertainty, where only the plausibility relation (between the different geographical positions that are candidates to be the actual position of the manholes) is important. Finally, we propose to use two aggregation modes, conjunctive and disjunctive modes, to combine the possibility distributions associated with the detected objects.

We address the problem of handling inconsistency in uncertain knowledge bases that are specified in the lightweight fragments of description logics DL-Lite. More specifically, we assume that the TBox component is coherent, stable, and fully reliable. However, the ABox component may be inconsistent with respect to the TBox, partially preordered and uncertain. Uncertainty is encoded in the framework of possibility theory. In this context, we propose an extension of standard possibilistic DL-Lite. We represent the ABox as a symbolic weighted base, where the weights attached to the assertions are ordered according to a strict partial order. We define a tractable method for computing a single possibilistic repair for a partially preordered weighted ABox. The idea is to consider the possibilistic compatible bases of such an ABox, which intuitively encode all the possible extensions of a partial order, and compute the possibilistic repair of each compatible base. We then compute the intersection of all these possibilistic repairs to obtain a single repair for the initial ABox. We also provide an equivalent characterization by introducing the notion of$\pi$-accepted assertions. This ensures that the computation of the partially preordered possibilistic repair can be achieved in polynomial time in DL-Lite.

Handling inconsistency in formal ontologies is crucial for facilitating meaningful query answering. Arguably the most popular approach for resolving inconsistency amounts to repairing the dataset in terms of the semantic knowledge encoded in the ontology. This has given rise to many inconsistency- tolerant semantics, like the well-known IAR (Intersection of ABox Repair) semantics, which produces a single consistent subset of the dataset, and that can be queried. Several frameworks additionally consider a preference relation over the data pieces (called assertions), such as the Elect method, which generalizes the IAR semantics to capture a partial preorder. Elect also computes a single consistent subset of the dataset using the notion of elected assertions. Basically, an assertion is elected if it is strictly preferred to all the assertions that conflict with it. However, Elect requires the prior computation of all the conflicts between the assertions. In this paper, we propose a new algorithm for computing the set of elected assertions, without exhibiting all the conflicts. Our algorithm is based on a new characterization of the set of elected assertions using the IAR semantics.

Abstract We focus on the problem of handling inconsistency in lightweight ontologies. We assume that the terminological knowledge base (TBox) is specified in DL-Lite and that the set of assertional facts (ABox) is partially preordered and may be inconsistent with respect to the TBox. One of the main contributions of this paper is the provision of an efficient and safe method, called Elect, to restore the consistency of the ABox with respect to the TBox. In the case where the assertional base is flat (i.e. no priorities are associated with the ABox) or totally preordered, we show that our method collapses with the well-known intersection ABox repair semantics and the non-defeated semantics, respectively. The semantic justification of the Elect method is obtained by first viewing a partially preordered ABox as a family of totally preordered ABoxes and then applying non-defeated inference to each of the totally preordered ABoxes. We introduce the notion of elected assertions which allows us to provide an equivalent characterization of the Elect method without explicitly generating all the totally preordered ABoxes. We show that computing the set of elected assertions is done in polynomial time with respect to the size of the ABox. The second part of the paper discusses how to go beyond the Elect method. In particular, we discuss to what extent the Elect method can be generalized to description logics that are more expressive than DL-Lite.

International audience

The problem of belief change is considered as a major issue in managing the dynamics of an information system. It consists in modifying an uncertainty distribution, representing agents’ beliefs, in the light of a new information. In this paper, we focus on the so-called multiple iterated belief revision or C-revision, proposed for conditioning or revising uncertain distributions under uncertain inputs. Uncertainty distributions are represented in terms of ordinal conditional functions. We will use prioritized or weighted knowledge bases as a compact representation of uncertainty distributions. The input information leading to a revision of an uncertainty distribution is also represented by a set of consistent weighted formulas. This paper shows that C-revision, defined at a semantic level using ordinal conditional functions, has a very natural representation using weighted knowledge bases. We propose simple syntactic methods for revising weighted knowledge bases, that are semantically meaningful in the frameworks of possibility theory and ordinal conditional functions. In particular, we show that the space complexity of the proposed syntactic C-revision is linear with respect to the size of initial weighted knowledge bases.

Reasoning with uncertainty in graphical models often implies great computational cost. For example, computing the most probable explanation in Bayesian networks is known to be NPPP-complete. Possibilistic networks represent an alternative powerful representation for uncertain information. This paper aims at showing that the computation complexity of MPE inference tasks in possibilistic networks are NP-complete. To that end, we provide full reduction and proof for MPE querying min-based and product-based possibilistic networks. More precisely, we provide incremental proofs based on reductions to and from three well-known NP-complete problems: SAT, 3SAT and Weighted MaxSAT decision problems.

In recent year, preservation and promotion of the ICHs are one of the problems of interest. In this paper, we focus on modelling the traditional dance domain, particularly modelling traditional Vietnamese dances. To conserve significant characteristics of dances, we proposed an ontology to represent the significant movements features of Ethnic Vietnamese Thai Dances (EVTDs). Particularly, a detailed description of the movement schemas of EVTDs is presented in this paper. Additionally, we present how to build an automatic extraction tool to collect the fundamental movements data of EVTDs using machine learning. Finally, we represented explicitly how to store those extracted features from raw dance videos into prioritized Ontology-based proposed.

The aim of this paper is to highlight two important issues related to the annotation and querying of Intangible Cultural Heritage video datasets. First, we focus on ontology completion by annotating dance videos. In order to build video training sets and to enrich the proposed ontology, manual video annotation is performed based on background knowledge formalized in an ontology, representing a semantics of a traditional dance. The paper provides a case study on Malaysian Zapin dances. Second, we address the question of how can end-users efficiently query the datasets of annotated videos that are built.

Possibilistic networks are powerful graphical uncertainty representations based on possibility theory. This paper analyzes the computational complexity of querying min-based and product-based possibilistic networks. It particularly focuses on a very common kind of queries: computing maximum a posteriori explanation (MAP). The main result of the paper is to show that the decision problem of answering MAP queries in both min-based and product-based possibilistic networks is NP-complete. Such computational complexity results represent an advantage of possibilistic networks over probabilistic networks since MAP querying is NPPP-complete in probabilistic Bayesian networks. We provide the proof based on reduction from the 3SAT decision problem to MAP querying possibilistic networks decision problem. As well as reductions that are useful for implementation of MAP queries using SAT solvers.

Ontology is an essential resource to enhance the performance of information processing system as well as is an intelligent storage area served for management of largescale heterogeneous digital contents resulting.In this paper, we propose the initial steps for reconstructing a significant schema of Vietnamese traditional dances.Most of the typical dances of Vietnamese community are recorded in multimedia format, in raw videos.Accordingly, we concentrated on analyzing and collecting knowledge of the dance experts at art schools in Vietnam to classify and to determine the primary features that would be stored in the ontology.We propose an ontologybased modelling for the cultural heritage domain of Vietnamese traditional dance.

This paper focuses on belief graphical models and provides an efficient approximation of MAP inference in credal networks using probability-possibility transformations. We first present two transformations from credal networks to possibilistic ones that are suitable for MAP inference in credal networks. Then we present four criteria to evaluate our approximate MAP inference. The last part of the paper provides experimental studies that compare our approach with both standard exact and approximate MAP inference in credal networks. The paper also provides a brief analysis of MAP inference complexity using possibilistic networks and the results definitely open new perspectives for MAP inference in credal networks.

DL-Lite is one of the most important fragments of description logics that allows a flexible representation of knowledge with a tractable computational complexity of the reasoning process. This article investigates an extension of the main fragments of DL-Lite to deal with uncertainty associated with objects, concepts or relations using a possibility theory framework. Possibility theory offers a natural framework for representing uncertain and incomplete information. It is particularly useful for handling inconsistent knowledge. We first provide foundations of possibilistic DL-Lite , denoted by $$\\pi $$ - $$DL$$ - $$Lite$$ , by extending the $$DL$$ - $$Lit{e}_{core}$$ logic, the core fragment of all DL-Lite logics, within possibility theory setting. We present syntax and semantics of $$\\pi $$ - $$DL$$ - $$Lit{e}_{core}$$ , study the reasoning tasks and show how to compute the inconsistency degree of a $$\\pi $$ - $$DL$$ - $$Lit{e}_{core}$$ knowledge base. We then extend our possibilistic approach to $$DL$$ - $$Lit{e}_{F}$$ and $$DL$$ - $$Lit{e}_{R}$$ , two important fragments of DL-Lite family. Finally, we address the problem of query answering over a $$\\pi $$ - $$DL$$ - $$Lite$$ knowledge base. An important result of the article is that the extension of the expressive power of DL-Lite is done without additional extra-computational costs.

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

Access control models play a crucial role in computer security. Their aim is to restrict the access to the sensitive data to only authorized users, on the basis of a security policy. In existing access control models, security policies are often defined over a set of elementary actions and without taking into account the evolution of information systems. This paper first proposes an analysis of security policies that involves actions with different levels of granularity. We then show how to integrate complex actions in access control models. We view a complex actions as a partial pre-order of (ai,oj) where ai is an elementary action while oj is a concrete object.

Intrusion Detection Systems (IDS) are necessary and important tools for monitoring information systems. However they produce a huge quantity of alerts. Alerts correlation is a process that reduces the number of alerts reported by intrusion detection

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

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

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

Min-based (or qualitative) possibilistic networks are important tools to efficiently and compactly represent and analyze uncertain information. Inference is a crucial task in min-based networks, which consists of propagating information through the network structure to answer queries. Exact inference computes posteriori possibility distributions, given some observed evidence, in a time proportional to the number of nodes of the network when it is simply connected (without loops). On multiply connected networks (with loops), exact inference is known as a hard problem. This paper proposes an approximate algorithm for inference in min-based possibilistic networks. More precisely, we adapt the well-known approximate algorithm Loopy Belief Propagation (LBP) on qualitative possibilistic networks. We provide different experimental results that analyze the convergence of possibilistic LBP.

Weighted logics are important tools for reasoning under uncertain knowledge. A weighted knowledge base is a set of weighted formulas of the form (φi, αi) where φi is a propositional formula and αi is the certainty degree associated with φi. This paper addresses two issues in the possibility theory framework: i) how to compare two weighted knowledge bases with respect to their information contents? and ii) how to syntactically define the concept of forgetting variables? We show that comparing knowledge bases is the counterpart of the concept of the specificity relation defined between possibility distributions.

Possibilistic networks are belief graphical models based on possibility theory. This paper deals with a special kind of possibilistic networks called three-valued possibilistic networks where only three possibility levels are used to encode uncertain information. The paper analyzes different semantics of three-valued networks and provides precise relationships relating the different semantics. More precisely, the paper analyzes two categories of methods for deriving a three-valued joint possibility distribution from a three-valued possibilistic network. The first category of methods is based on viewing a three-valued possibilistic network as a family of compatible networks and defining combination rules for deriving the three-valued joint distribution. The second category is based on three-valued chain rules using three-valued operators inspired from some three-valued logics. Finally, the paper shows that the inference using the well-known junction tree algorithm can only be extended for some three-valued chain rules.

DL-Lite is one of the most important tractable fragment of DLs that provides a powerful framework to compactly encode available knowledge with a low computational complexity of the reasoning process. In semantic web area, merging different and often conflicting sources of information, has been recognized as an important problem. Pieces of information to be combined are provided with uncertainty due for instance to the reliability of sources. Possibility theory offers an important tool for representing and reasoning with uncertain, partial and inconsistent pieces of information. This paper first presents possibilistic DL-Lite, denoted by π-DL-Lite as an extension of DL-Lite within a possibility theory setting. It then focuses on the use of a minimum-based (min-based) operator, well known as idempotent conjunctive operator to combine π-DLLite possibility distributions and it shows that the semantic fusion of π-DL-Lite possibility distributions has a natural syntactic counterpart when dealing with π-DL-Lite knowledge bases. The min-based fusion operator is recommended when distinct sources that provide information are dependent.

Classifiers are well-known and efficient techniques used to predict the class of items descrided by a set of features. In many applications, it is important to take into account some extra knowledge in addition to the one encoded by the classifier. For example, in spam filtering which can be seen as a classification problem, it can make sense for a user to require that the spam filter predicts less than a given rate or number of spams. In this paper, we propose an approach allowing to combine expert knowledge with the results of a decision tree classifier. More precisely, we propose to revise the outputs of a decision tree in order to take into account the available expert knowledge. Our approach can be applied for any classifier where a probability distribution over the set of classes (or decisions) can be estimated from the output of the classification step. In this work, we analyze the advantage of adding expert knowledge to decision tree classifiers in the context of intrusion detection and alert correlation. In particular, we study how additional expert knowledge such as "it is expected that 80% of traffic will be normal" can be integrated in classification tasks. Our aim is to revise classifiers' outputs in order to fit the expert knowledge. Experimental studies on intrusion detection and alert correlation problems show that our approach improves the performances on different benchmarks.

This paper emphasizes on handling uncertain and causal information in a min-based possibility theory framework. More precisely, we focus on studying the representational point of view of interventions under a compilation framework. We propose two compilation-based inference algorithms for min-based possibilistic causal networks based on encoding the augmented network into a propositional theory and compiling this output in order to efficiently compute the effect of both observations and interventions.

Preferences play an important role in many applications. This paper focuses on the use of preferences in travel agency systems such as E-travel system. We show that adding flexible constraints and preferences allows to reach solutions that better fit users's desires. We study simple languages for expressing preferences and queries. We then provide criteria to rank-order solutions returned by a travel agency system. Lastly, we provide experimental results showing the merits of our approach.

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

The success of Bayesian networks is due to their capability to simply represent (in)dependence and to be a compact representation of a full joint distribution of the set of random variables involved in the studied system. Since belief function theory is known as a general framework to reason under uncertainty, it is expected that belief function networks with conditional beliefs are a generalization of Bayesian networks. This paper studies different forms of belief function networks. We discuss the ones defined with one conditional for all parents and the ones defined per single parent. In particular, we discuss the case when beliefs are Bayesian situations where a belief function network fails to collapse into a Bayesian network.

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

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

In cooperative intrusion detection, several intrusion detection systems (IDS), network analyzers, vulnerability analyzers and other analyzers are deployed in order to get an overview of the system under consideration. In this case, the definition of a shared vocabulary describing the different information is prominent. Since these pieces of information are structured, we first propose to use description logics which ensure the reasoning decidability. Besides, the analyzers used in cooperative intrusion detection are not totally reliable. The second contribution of this paper is to handle these inconsistencies induced by the use of several analyzers using the so-called partial lexicographic inference.

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.

Bayesian networks are very powerful tools for knowledge representation and reasoning under uncertainty. This paper shows the applicability of naive Bayesian classifiers to two major problems in intrusion detection: the detection of elementary attacks and the detection of coordinated ones. We propose two models starting with stating the problems and defining the variables necessary for model building using naive Bayesian networks. In addition to the fact that the construction of such models is simple and efficient, the performance of naive Bayesian networks on a representative data is competing with the most efficient state of the art classification tools. We show how the decision rules used in naive Bayesian classifiers can be improved to detect new attacks and new anomalous activities. We experimentally show the effectiveness of these improvements on a recent Web-based traffic. Finally, we propose a naive Bayesian network-based approach especially designed to detect coordinated attacks and provide experimental results showing the effectiveness of this approach.

In this paper, we address the problem of possibilistic network-based classification with uncertain inputs. Possibilistic networks are powerful tools for representing and reasoning with uncertain and incomplete information in the framework of possibility theory. We first consider the direct use of Jeffrey's rule in the framework of possibility theory in order to perform classification with uncertain inputs. Then we study the property of Markov-blanket in our context. Lastly, we propose an efficient algorithm for possibilistic classifiers with uncertain inputs ensuring the same classification results as using the possibilistic counterpart of Jeffrey's rule. Our algorithm performs this task in a polynomial time without assuming strong independence relations between observations.

Possibilistic networks are graphical models particularly suitable for representing and reasoning with uncertain and incomplete information. According to the underlying interpretation of possibilistic scales, possibilistic networks are either quantitative (using product-based conditioning) or qualitative (using min-based conditioning). Among the multiple tasks, possibilitic models can be used for, classification is a very important one. In this paper, we address the problem of handling uncertain inputs in binary possibilistic-based classification. More precisely, we propose an efficient algorithm for revising possibility distributions encoded by a naive possibilistic network. This algorithm is suitable for binary classification with uncertain inputs since it allows classification in polynomial time using several efficient transformations of initial naive possibilistic networks. © 2009 Wiley Periodicals, Inc.

In the last decade, several approaches have been proposed for merging multiple and potentially conflicting pieces of information. Egalitarian fusion modes pick solutions that minimize the local dissatisfaction of each source (agent, expert), which is involved in the fusion process. When pieces of information to merge are prioritized, or ranked, most existing approaches assume that these priority degrees are commensurable, namely sources are assumed to share the same meaning of uncertainty scales. This article provides useful strategies for an egalitarian fusion of incommensurable ranked belief bases under constraints. In particular, it focuses on Max-based merging operators, and proposes a merging operator that allows to aggregate a set of ranked belief bases E. This operator is based on the concept of compatible scales. We provide three equivalent characterizations of this operator. The first one shows that Max-based merging of incommensurable belief bases can also be defined in terms of a Pareto-like ordering on possible worlds, denominated SMP ordering. The second one is based on the notion of compatible rankings defined on finite scales. The third one is only based on total pre-orders induced by ranked bases to merge. The last part of the article analyses rational postulates satisfied by our merging operator and compare it with some related works.

Anomaly detection approaches are generally efficient in detecting new attacks. However, they fail in providing any further information regarding the nature of attacks. The first contribution of this paper is to equip an anomaly detection approach with a diagnosis module that classifies anomaly approach outputs in one among well known attack categories. The second contribution concerns a context-based definition of normal network traffic profiles. We provide experimental studies showing for instance that considering normal profile for each service provides better results than considering a unique global normal profile.

Alert correlation is a very useful mechanism to reduce the high volume of reported alerts and to detect complex and coordinated attacks. Existing approaches either require a large amount of expert knowledge or use simple similarity measures that prevent detecting complex attacks. They also suffer from high computational issues due, for instance, to a high number of possible scenarios. In this paper, we propose a Naive Bayes approach to alert correlation. Our modeling only needs a small part of expert knowledge. It takes advantage of available historical data, and provides efficient algorithms for detecting and predicting most plausible scenarios. Our approach is illustrated using the well known DARPA 2000 data set.

Decision trees are well known and efficient classifiers widely used as behavioral approaches. However, most works pointed out their inefficiency in detecting novel attacks. In this paper, we address the inadequacy of decision trees for behavioral anomaly detection. We first explain why decision trees fail in detecting most of novel attacks. In particular, we provide experimental results showing that minimum description length (MDL) principle used while inducing decision trees is among the main reasons in their failure in detecting novel attacks. Then we propose relaxing MDL principle in order to build compatible decision trees more suitable for novel behavior detection. The strategy of relaxing MDL principle is to exploit additional tests/features in order to discriminate between normal behaviors and intrusive ones while standard decision trees only rely on minimum subset of tests/features. Experimental studies, carried out on real and recent http traffic and several Web attacks, show the significant improvements that can be made by relaxed MDL decision trees.

This paper deals with anomaly score aggregation and thresholding in multi-model anomaly-based approaches which require multiple detection models and profiles in order to characterize the different aspects of normal activities. Most works focus on profile/model definition while critical issues related to anomaly measuring, aggregating and thresholding have not received similar attention. In this paper, we in particular address the issue of anomaly scoring and aggregating which is a recurring problem in multi-model anomaly-based approaches. We propose a two stage aggregation/thresholding scheme particularly suitable for multi-model anomaly-based approaches. The basic idea of our scheme is the fact that anomalous behaviors induce either intramodel anomalies or inter-model ones. Our scheme is designed for real-time detection of both intra-model and inter-model anomalies. More precisely, we propose local thresholding in order to detect intra-model anomalies and use a Bayesian network in order to, on one hand, extract inter-model regularities and serve, on the other hand, as an aggregating function for computing the overall anomaly score associated with each analyzed audit event. Our experimental studies, carried out on recent and realhttptraffic, show for instance that most Web-based attacks induce only intra-model anomalies and can be effectively detected in real-time. Moreover, this scheme significantly improves the detection rate of Web-based attacks involving inter-model anomalies.

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.

Recently, several approaches have been proposed to merge possibly contradictory belief bases. This paper focuses on max-based merging operators applied to incommensurable ranked belief bases. We first propose a characterization of a result of merging using Pareto-like ordering on a set of possible solutions. Then we propose two equivalent ways to recover the result of merging. The first one is based on the notion of compatible rankings defined on finite scales. The second one is only based on total pre-orders induced by ranked bases to merge.

Independence relations play an important role in uncertain reasoning based on Bayesian networks. In particular, they are useful in decomposing joint distributions into more elementary local ones. Recently, in a possibility theory framework, several qualitative independence relations have been proposed, where uncertainty is encoded by means of a complete pre-order between states of the world. This paper studies the well-known graphoid properties of these qualitative independences. Contrary to the probabilistic independence, several qualitative independence relations are not necessarily symmetric. Therefore, we also analyze the symmetric counterparts of graphoid properties (called reverse graphoid properties).

This paper presents a method for classifying objects in an uncertain context using decision trees. Uncertainty is related to attributes' values of objects to classify and is handled in a qualitative possibilistic framework. Then, an evaluation method to judge the classification efficiency, in an uncertain context, is proposed.

Modeling information security policies is an important problem in many domains. Recently, a new access control system, called OrBAC (organization-based access control) has been proposed. This model brings many solutions to the existing access control systems. However, it does not deal with conflicts due to the joint handling of permission and prohibition policies. This work deals with the problem of handling conflicts in the OrBAC system, modeled by first order logic knowledge bases. We show that the "blind" application of propositional approaches to inconsistent first order knowledge bases can lead to undesirable conclusions. A solution based on weakening first order formulas responsible of conflicts is proposed.

This paper deals with iterated belief change. Epistemic states are suitable to represent an intelligent agent's knowledge. Most of the time, when dealing with geographic information, the agent faces incomplete, uncertain, or inaccurate information and needs a mechanism for either revision, update, or fusion to handle their change in beliefs in the presence of new items of information. After some preliminaries on the representation of epistemic states by means of pre-orders, the paper presents three approaches to belief change: revision, update, and fusion. For each of these approaches, the background, postulates, representation by pre-orders, and semantic and syntactic requirements are given. In each case, the approaches are illustrated by examples.

Modeling information security policies is an important problem in many domains. This is particularly true in the health care sector, where information systems often manage sensitive and critical data. This article proposes to use nonmonotonic reasoning systems to control access to sensitive data in accordance with a security policy. In the first part of the article, we propose an access control model that overcomes several limitations of existing systems. In particular, it allows us to deal with contexts and to represent the two main kinds of privileges: permissions and prohibitions. This model will then be formally encoded using stratified (or prioritized) first-order knowledge bases. In the second part of the article, we discuss the problem of conflicts due to the joint handling of permissions and prohibitions. We show that approaches proposed for solving conflicts in propositional knowledge bases are not appropriate for handling inconsistent first-order knowledge bases. © 2004 Wiley Periodicals, Inc. Int J Int Syst 19: 817–836, 2004.

In the health care sector, access to medical information is more and more electronically achieved. Therefore, it is very important to define security policies which restrict access to pieces of information in order to guarantee security properties like confidentiality or integrity properties. These security policies are not always free of conflicts, in particular in the presence of exceptional situations.This paper proposes tools for access control, based on the notion of roles, in the possibilistic logic framework. We first show how to formalize basic concepts of security policies. Then we present two approaches for dealing with conflicts based on a stratification of security policy's rules. Finally, an example of health care is presented.

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.

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 example considers the problem of finding a suitable assignment of a set of referees to each one of a set of papers submitted to a conference, given the preferences expressed by the referees regarding the papers they are willing to review, the adequation between their areas of competence and the topics of the papers, and a set of regulations bearing on the global assignment. This example illustrates the issue of fusing heterogeneous data consisting of individual preference profiles and a set of global regulations. © 2001 John Wiley & Sons, 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.

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.

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.

The paper investigates a local approach for reasoning with conditional knowledge bases (with default rules of the form "generally, if /spl alpha/ then /spl beta/" and having possibly so,ne exceptions). The idea is that when a conflict appears (due to observing exceptional situations), one first localizes the sets of pieces of information which are responsible for conflicts. Next, using a specificity principle (subclasses must be preferred to general classes), the authors attach priorities to default rules inside each conflict. These priorities, implicitly computed from the knowledge base, reflect the hierarchical structure of the knowledge base. Lastly, they rank-order and solve conflicts in a way that only minimal sets of rules are given up from the knowledge base in order to restore its consistency. This local method of dealing with conflicts addresses correctly the well known problems of specificity, irrelevance, blocking of inheritance, etc.