In this paper, we examine a probabilistic intelligent system that provides posterior information, with the goal of recovering either the prior beliefs or the new data received by the system. We address this inverse problem within a general probabilistic framework and present several key contributions. Specifically, we demonstrate that when only the posterior beliefs and the data used are known, the corresponding prior beliefs form a convex set of probability distributions. We characterize this set by determining its lower and upper probability bounds. Additionally, we show that, in the general case, the minimum number of queries required to recover the prior information grows exponentially with the number of variables. We analyze this problem both when prior beliefs are represented in a non-factorized form and when they are factorized. Finally, we generalize our findings to scenarios where the available information is expressed using an alternative, non-additive theory of uncertainty.

Punctuality is a sensitive issue in large airports and hubs for passenger experience and for controlling operational costs. This paper presents a real and challenging problem of predicting and explaining flight off-block delays. We study the case of the international airport Paris Charles de Gaulle (Paris-CDG) starting from the specificities of this problem at Paris-CDG until the proposal of modelings then solutions and the analysis of the results on real data covering an entire year of activity. The proof of concept provided in this paper allows us to believe that the proposed approach could help improve the management of delays and reduce the impact of the resulting consequences.

There is a plethora of work in the literature on anomaly detection with statistical or machine learning-based approaches. Most often there are several problems and pitfalls that anomaly detection must overcome to be successful in practice. While the majority of the work is validated on general benchmarks including a lot of synthetic datasets, unfortunately there are only a few studies on real data in certain application domains. This paper aims to fill this gap in the field of sleep and physical activity monitoring of the elderly. More precisely, it provides a case study of anomaly detection in the context of monitoring the activities of elderly people. Our objective is to highlight the main problems that can be encountered in such a real context and the solutions that can be provided. Hence, we raised several questions and provided practical answers, particularly with regard to data scarcity, heterogeneity, class imbalance and lack of ground truth.

International audience

International audience

Probability intervals provide an intuitive, powerful and unifying setting for encoding and reasoning with imprecise beliefs. This paper addresses the problem of updating uncertain information specified in the form of probability intervals with new uncertain inputs also expressed as probability intervals. We place ourselves in the framework of Jeffrey's rule of conditioning and propose extensions of this conditioning for the interval-based setting. More precisely, we first extend Jeffrey's rule to credal sets then propose extensions of Jeffrey's rule to three common conditioning rules for probability intervals (robust, Dempster and geometric conditionings). While the first extension is based on conditioning the extreme points of the credal sets induced by the probability intervals, the other methods directly revise the interval bounds of the distributions to be updated. Finally, the paper discusses related issues and relates the proposed methods with respect to the state-of-the-art.

The ever increasing complexity of machine learning techniques used more and more in practice, gives rise to the need to explain the outcomes of these models, often used as black-boxes. Explainable AI approaches are either numerical feature-based aiming to quantify the contribution of each feature in a prediction or symbolic providing certain forms of symbolic explanations such ascounterfactuals. This paper proposes a generic agnostic approach named ASTERYX allowing to generate both symbolic explanations and score-based ones. Our approach is declarative and it is based on the encoding of the model to be explained in an equivalent symbolic representation. This latter serves to generate in particular two types of symbolic explanations which aresufficient reasons andcounterfactuals. We then associate scores reflecting the relevance of the explanations and the features w.r.t to some properties. Our experimental results show the feasibility of the proposed approach and its effectiveness in providing symbolic and score-based explanations.

International audience

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.

Multi-label classification is a very active research area and many real-world applications need efficient multi-label learning. During recent years, explaining machine learning predictions is also a very hot topic. A lot of approaches have been proposed for explaining multi-class classifier predictions. However, almost nothing has been proposed for multi-label and ensemble approaches. This paper brings two main contributions. It first proposes a natural framework consisting in reasoning with base classifier explanations in order to provide explanations for the multi-label predictions. The second contribution focuses on binary relevance, a widely used approach in multi-label classification, and distinguishes two kinds of explanations: common explanations shared by all base classifiers predicting positive labels and joint explanations combining explanations from each base classifier predicting a positive label. The paper proposes an efficient approach for deriving such explanations. Experimental studies show positive results that can be achieved on many multi-label datasets.

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.

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.

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.

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.

In this paper, we show how symmetries, a fundamental structural property, can be used to prune the search space in itemset mining problems. Our approach is based on a dynamic integration of symmetries in APRIORI-like algorithms to prune the set of possible candidate patterns. More precisely, for a given itemset, symmetry can be applied to deduce other itemsets while preserving their properties. We also show that our symmetry-based pruning approach can be extended to the general Mannila and Toivonen pattern mining framework. Experimental results highlight the usefulness and the efficiency of our symmetry-based pruning approach.

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.

Alert correlation plays an increasingly crucial role in nowadays computer security infrastructures. It is particularly needed for coping with the huge amounts of alerts which are daily triggered by intrusion detection systems (IDSs), fire-walls, etc. While the use of multiple IDSs, security tools a nd complementary approaches is fundamental and highly recommended in order to improve the overall detection rates, this however inevitably causes huge amounts of alerts most of which are redundant and false alarms making the manual analysis of these triggered alerts time-consuming and inefficient. This paper addresses three important issues related to predicting severe attacks (attacks with high dangerousness levels) by analyzing inoffensive and preparatory attacks. i) Firstly, we address the issue of preprocessing alerts reported by the multiple detection tools in order to eliminate the redundant and irrelevant alerts and format them so that they can be analyzed by a severe attack prediction model. ii) Then, we propose a novel prediction model based on a Bayesian network multi-net allowing on one hand to better model the severe attacks and on the other hand handle the reliability of IDSs when predicting severe attacks. iii) Finally, we provide a flexible and efficient approach especially designed to limit the false alarm rates by controlling the confidence of the prediction model. The main benefits of our approach is an integrated model guaranteeing very promising prediction/false alarm rate tradeoffs with minimum expert intervention. Our experimental studies are carried out on a real and representative alert corpus generated by the de facto network-based IDS Snort, and show very interesting performances regarding the tradeoffs between the prediction rates and the corresponding false alarm ones.

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.

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.

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.

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.