This paper proposes a model for imprecise probability information based on bounds on probability ratios, instead of bounds on events. This model is studied in the language of coherent sets of desirable gambles, which provides an elegant mathematical formulation and a more expressive power. The paper provides methods to check avoiding sure loss and coherence, and to compute the natural extension. The relationships with other formalisms such as imprecise multiplicative preferences, the constant odd ratio model, or comparative probability are analyzed.

PBN (Performance-Based Navigation) implies an increase in the automation of air operations, in the context of the current evolution of flight trajectories that are based on a flexible definition of route waypoints, to enable the implementation of TBO (Trajectory-Based Operations) and trajectory negotiation, all under the umbrella of SWIM (System-Wide Information Management). From a general perspective, automation has a positive impact on flight safety, contributing to the reduction of flight crew workload. However, in the particular case of PBN turns, there are cases where pilots are not aware of the type of turns that their aircraft perform. There is a risk of an automation bias leading to situations where the crew perceive that it is not their responsibility to start a turn or to monitor the conditions that drive the autopilot behaviour. In the context of a research line that aims to apply Bayesian networks to SA (Situation Awareness) measurement, we have designed an experiment to assess automation in a simulated PBN departure procedure, intending to collect data that are relevant to analyze the automation bias problem and rate SA using logistic regression.

This paper proposes a generalization of the imprecise probability model given by probability intervals on singleton sets. This enables us not only to represent probability intervals in a hierarchy of sets with a tree structure but also to represent other models such as possibility measures and generalized p-boxes. The paper also shows how the resulting model is always an order-2 capacity and that the basic operations of checking coherence, computing the natural extension or conditioning can be performed in an extremely efficient way.

When dealing with complex models (i.e., models with many variables, a high degree of dependency between variables, or many states per variable), the efficient representation of quantitative information in probabilistic graphical models (PGMs) is a challenging task. To address this problem, this study introduces several new structures, aptly named value-based potentials (VBPs), which are based exclusively on the values. VBPs leverage repeated values to reduce memory requirements. In the present paper, they are compared with some common structures, like standard tables or unidimensional arrays, and probability trees (PT). Like VBPs, PTs are designed to reduce the memory space, but this is achieved only if value repetitions correspond to context-specific independence patterns (i.e., repeated values are related to consecutive indices or configurations). VBPs are devised to overcome this limitation. The goal of this study is to analyze the properties of VBPs. We provide a theoretical analysis of VBPs and use them to encode the quantitative information of a set of well-known Bayesian networks, measuring the access time to their content and the computational time required to perform some inference tasks.

The Dempster-Shafer theory of evidence (DST) has been widely used to handle uncertainty-based information.It is based on the concept of basic probability assignment (BPA).Belief intervals are easier to manage than a BPA to represent uncertainty-based information.For this reason, several uncertainty measures for DST recently proposed are based on belief intervals.In this study, we carry out a study about the crucial mathematical properties and behavioral requirements that must be verified by every uncertainty measure on belief intervals.We base on the study previously carried out for uncertainty measures on BPAs.Furthermore, we analyze which of these properties are satisfied by each one of the uncertainty measures on belief intervals proposed so far.Such a comparative analysis shows that, among these measures, the maximum of entropy on the belief intervals is the most suitable one to be employed in practical applications since it is the only one that satisfies all the required mathematical properties and behaviors.

Given a set of uncertain discrete variables with a joint probability distribution and a set of observations for some of them, the most probable explanation is a set or configuration of values for non-observed variables maximizing the conditional probability of these variables given the observations. This is a hard problem which can be solved by a deletion algorithm with max marginalization, having a complexity similar to the one of computing conditional probabilities. When this approach is unfeasible, an alternative is to carry out an approximate deletion algorithm, which can be used to guide the search of the most probable explanation, by using A* or branch and bound (the approximate+search approach). The most common approximation procedure has been the mini-bucket approach. In this paper it is shown that the use of probability trees as representation of potentials with a pruning of branches with similar values can improve the performance of this procedure. This is corroborated with an experimental study in which computation times are compared using randomly generated and benchmark Bayesian networks from UAI competitions.

Within the field of supervised classification, the naïve Bayes (NB) classifier is a very simple and fast classification method that obtains good results, being even comparable with much more complex models. It has been proved that the NB model is strongly dependent on the estimation of conditional probabilities. In the literature, it had been shown that the classical and Laplace estimations of probabilities have some drawbacks and it was proposed a NB model that takes into account the a priori probabilities in order to estimate the conditional probabilities, which was called m-probability-estimation. With a very scarce experimentation, this approximation based on m-probability-estimation demonstrated to provide better results than NB with classical and Laplace estimations of probabilities. In this research, a new naïve Bayes variation is proposed, which is based on the m-probability-estimation version and takes into account imprecise probabilities in order to calculate the a priori probabilities. An exhaustive experimental research is carried out, with a large number of data sets and different levels of class noise. From this experimentation, we can conclude that the proposed NB model and the m-probability-estimation approach provide better results than NB with classical and Laplace estimation of probabilities. It will be also shown that the proposed NB implies an improvement over the m-probability-estimation model, especially when there is some class noise.

Clustering is an efficient method for handling large amounts of complex data. More specifically, k-means clustering is an optimized algorithm based on Euclidean distance measurement that has been applied to aircraft trajectory classification. In this paper we present a research line based on performing a preprocessing of trajectory coordinates and flight plan data to obtain additional variables, as adapted to the k-means clustering algorithm as possible, in order to support supervised trajectory classification.

In this work we applied Variable Mesh Optimization population metaheuristc (VMO) for Bayesian network (BN) structure learning as a score-and-search method. Our idea was to represent each node of the Mesh as a Bayesian network through a set of arcs. Then new BNs are created using (union and difference) operations among sets. For this process, three types of BNs are identified, local optima (BNs with the best score in each neighborhood), global optima (BN with the best score among local optima), and frontier solutions (most and least different in structure BNs). Finally the clearing process is applied to select the most representative BNs in the Mesh (score and structure). For determining the global score, each BN is used as a Bayesian classifier and classification accuracy is obtained using cross validation over dataset. The proposal is compared with other classifiers using UCI repository data set. Results show that our proposal obtains the best score, that proves to be a very competitive algorithm for supervised classification.

The use of graphical probabilistic models in the field of education has been considered for this research. First, classical learning algorithms, as PC or K2 are reviewed. But the problem with these general learning procedures comes from the presence of a high number of variables that measure diffe rent aspects of the same concept, as it can be the case of socio-economic indicators in a population. In this case, we have that all the variables have some degree of dependence among them, without a true causal structure. So, a new procedure is presented which makes a hierarchical clustering of the data while learning a joint probability distribution. It generalizes AutoClass EM clustering allowing more complex models. Hierarchical clustering is compared in the experiments with classical learning algorithms showing a similar performance when considering the estimation of a joint probability distribution for all the variables, but with a clear advantage: the simplicity and easiness of the interpretation of the model. The method is applied to the analysis of two datasets of the educational data: socio-economic, academic achievement and drop outs at the Engineering Faculty of Quevedo State Technical University, and student evaluation of teachers from Gazi University in Ankara (Turkey).

In the context of a PhD thesis on data mining, we have implemented a simulation environment that collects data for measurements of certain aspects of the Situational Awareness (SA) of a pilot using Bayesian networks (BN). The tool is based on a web application that emulates an Electronic Flight Bag (EFB) and is connected to a flight simulator, providing the user with basic autopilot controls and a customizable interface to access aeronautical information. Relevant data concerning to actions of the pilot, information queries and flight parameters are stored in a database. The use of System Wide Information Management (SWIM) technologies is specially applicable to this research because they provide a robust and powerful approach to the exploration of data relationships. But before analyzing the probabilistic dependencies of the dataset collected during the simulation, it is necessary to study how variables are adapted to the requirements of a Dynamic BN (DBN). This paper briefly presents some SA rating techniques and our approach to achieve a relevant measurement that relies on cockpit information management and DBN, focusing on the first experiment performed with the simulation environment, that analyzes the influence of different discretization criteria on the scores obtained by DBN that learn variable dependencies from data.

Probabilistic graphical models constitute a fundamental tool for the development of intelligent systems.They provide a sound and well-founded approach for performing inference and belief updating in complex domains endowed with uncertainty.A probabilistic graphical model is the result of the combination of a qualitative component (a graph) encoding conditional independence relationships among the variables in the system and a quantitative component consisting of a collection of local probability distributions matching the independence properties specified by the graph.The union of the two components provides a compact representation of the joint probability distribution over the domain being modeled.Bayesian networks are the most prominent type of probabilistic graphical models and have experienced a remarkable methodological development during the past two decades.This has come along with a wide variety of successful applications in different domains.Regardless of the increasing interest in the area, probabilistic graphical models are still facing a number of challenges, covering modeling, inference and learning.This special issue contains seven papers that contribute to the methodological development beyond the current state-of-the-art knowledge.Five of the papers were selected among the contributions presented at the 15th Conference of the Spanish Association of Artificial Intelligence (CAEPIA'2013, Madrid, Spain, September 17-20, 2013).These papers were substantially extended and went through a new and strict review process.The other two papers were invited contributions not presented at the conference and went through the same review process.The first three papers deal with hybrid models, where both discrete and continuous variables coexist.Lucas and Hommersom propose a framework for handling causal independence covering discrete and continuous variables simultaneously.The methodology is based on the convolution concept from probability theory, and the

Recursive probability trees (RPTs) are a data structure for representing several types of potentials involved in probabilistic graphical models. The RPT structure improves the modeling capabilities of previous structures (like probability trees or conditional probability tables). These capabilities can be exploited to gain savings in memory space and/or computation time during inference. This paper describes the modeling capabilities of RPTs as well as how the basic operations required for making inference on Bayesian networks operate on them. The performance of the inference process with RPTs is examined with some experiments using the variable elimination algorithm.

In the analysis of data, the discovery of dependence relations can play a very important role. Our principal aim in this paper is to present a new score to determine when two categorical variables are independent. It can be resumed as an interval-valued score that is based on the Heckerman, Geiger, and Chickering's score, which can be used in supervised classification task. We carry out an empirical comparison with different scores to determine when two binary variables are independent. Also, we have considered the following measures: the Bayesian score metric, the Bayesian information criterion (BIC), the p-value of the Chi-square test for independence and the upper entropy score based on imprecise probabilities. We will see that our new score has a behavior that it is more similar to statistical tests from small samples and to Bayesian procedures for large samples. We find this behavior very appropriate for some types of problems.

In this work, we study the application of Bayesian networks classifiers for gene expression data in three ways: first, we made an exhaustive state-of-art of Bayesian classifiers and Bayesian classifiers induced from microarray data. Second, we propose a preprocessing scheme for gene expression data, to induce Bayesian classifiers. Third, we evaluate different Bayesian classifiers for this kind of data, including the C-RPDAG classifier presented by the authors.

Most of learning algorithms with Bayesian networks try to minimize the number of structural errors (missing, added or inverted links in the learned graph with respect to the true one). In this paper we assume that the objective of the learning task is to approximate the joint probability distribution of the data. For this aim, some experiments have shown that learning with probability trees to represent the conditional probability distributions of each node given its parents provides better results that learning with probability tables. When approximating a joint distribution structure and parameter learning can not be seen as separated tasks and we have to evaluate the performance of combinations of procedures for inducing both structure and parameters. We carry out an experimental evaluation of several combined strategies based on trees and tables using a greedy hill climbing algorithm and compare the results with a restricted search procedure (the Max-Min hill climbing algorithm).

Previous analysis of learning data can help us to discover hidden relations among features. We can use this knowledge to select the most suitable learning methods and to achieve further improvements in the performance of classification systems. For the known Naive Bayes classifier, several studies have been conducted in an attempt to reconstruct the set of attributes in order to remove or debilitate dependence relations, which can reduce the accuracy of this classifier. These methods are included in the ones known as semi-naive Bayes classifiers. In the present research, we present a semi-Naive Bayes classifier that searches for dependent attributes using a filter approach. In order to prevent the number of cases of the compound attributes from being excessively high, a grouping procedure is always applied after the merging of two variables. This method attempts to group two or more cases of the new variable into a single one, in order to reduce the cardinality of the compound variables. As a result, the model presented is a competitive classifier with respect to the state of the art of semi-Naive Bayes classifiers, particularly in terms of quality of class probability estimates, but with a much lower memory space complexity.

Automatic learning of Bayesian networks from data is a challenging task, particularly when the data are scarce and the problem domain contains a high number of random variables. The introduction of expert knowledge is recognized as an excellent solution for reducing the inherent uncertainty of the models retrieved by automatic learning methods. Previous approaches to this problem based on Bayesian statistics introduce the expert knowledge by the elicitation of informative prior probability distributions of the graph structures. In this paper, we present a new methodology for integrating expert knowledge, based on Monte Carlo simulations and which avoids the costly elicitation of these prior distributions and only requests from the expert information about those direct probabilistic relationships between variables which cannot be reliably discerned with the help of the data.

The upper entropy of a credal set is the maximum of the entropies of the probabilities belonging to it. Although there are algorithms for computing the upper entropy for the particular cases of credal sets associated to belief functions and probability intervals, there is none for a more general model. In this paper, we shall present an algorithm to obtain the upper entropy for order-2 capacities. Our algorithm is an extension of the one presented for belief functions, and proofs of correctness are provided. By using a counterexample, we shall also prove that this algorithm is not valid for general lower probabilities as it computes a value which is strictly greater than the maximum of entropy.

We present an application of the measure of total uncertainty on convex sets of probability distributions, also called credal sets, to the construction of classification trees. In these classification trees the probabilities of the classes in each one of its leaves is estimated by using the imprecise Dirichlet model. In this way, smaller samples give rise to wider probability intervals. Branching a classification tree can decrease the entropy associated with the classes but, at the same time, as the sample is divided among the branches the nonspecificity increases. We use a total uncertainty measure (entropy + nonspecificity) as branching criterion. The stopping rule is not to increase the total uncertainty. The good behavior of this procedure for the standard classification problems is shown. It is important to remark that it does not experience of overfitting, with similar results in the training and test samples. © 2003 Wiley Periodicals, Inc.

In this article we introduce some modifications over the Penniless propagation algorithm. When a message through the join tree is approximated, the corresponding error is quantified in terms of an improved information measure, which leads to a new way of pruning several values in a probability tree (representing a message) by a single one, computed from the value stored in the tree being pruned but taking into account the message stored in the opposite direction. Also, we have considered the possibility of replacing small probability values by zero. Locally, this is not an optimal approximation strategy, but in Penniless propagation many different local approximations are carried out in order to estimate the posterior probabilities and, as we show in some experiments, replacing by zeros can improve the quality of the final approximations. © 2003 Wiley Periodicals, Inc.

Directed graphic models based on conditional independence provide a compact and concise representation of an expert's subjective belief about existing relationships between variables. Faced with the task of building a greater model, each expert must be a specialist in some subset of the whole knowledge domain. It would be desirable to aggregate the knowledge provided by those specialists under the form of graphical models into a single and more general representation. This article studies the consensus model that would be obtained by combining two graphs associated with Bayesian networks and applying the union and intersection of their independencies. © 2003 Wiley Periodicals, Inc.

In belief functions, there is a total measure of uncertainty that quantify the lack of knowledge and verifies a set of important properties. It is based on two measures: maximum of entropy and non-specificity. In this paper, we prove that the maximum of entropy verifies the same set of properties in a more general theory as credal sets and we present an algorithm that finds the probability distribution of maximum entropy for another interesting type of credal sets as probability intervals.

Abstract In this paper, we investigate the application of the ideas behind Lazy propagation to the Penniless propagation scheme. Probabilistic potentials attached to the messages and the nodes of the join tree are represented in a factorized way as a product of (approximate) probability trees, and the combination operations are postponed until they are compulsory for the deletion of a variable. We tested two variations of the basic Lazy scheme: One is based on keeping a hash table for the operations with probabilistic potentials that are carried out more than once during the propagation, to avoid repeating computations; the other uses a heuristic method to determine the order of the operations when combining a set of potentials. © 2002 Wiley Periodicals, Inc.

Abductive inference in Bayesian belief networks (BBNs) is intended as the process of generating the K most probable configurations given observed evidence. When we are interested only in a subset of the network's variables, this problem is called partial abductive inference. Both problems are NP-hard, and so exact computation is not always possible. In this paper, a genetic algorithm is used to perform partial abductive inference in BBNs. The main contribution is the introduction of new genetic operators designed specifically for this problem. By using these genetic operators, we try to take advantage of the calculations previously carried out, when a new individual is evaluated. The algorithm is tested using a widely-used Bayesian network and a randomly generated one, and then compared with a previous genetic algorithm based on classical genetic operators. From the experimental results, we conclude that the new genetic operators preserve the accuracy of the previous algorithm and also reduce the number of operations performed during the evaluation of individuals. The performance of the genetic algorithm is thus improved.

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 focuses on databases merging, which is one particular case of data fusion. Databases merging is the process which consists of integrating, physically or virtually, the data provided by several databases. With examples throughout the paper, we stress the main problems raised by databases merging and we present, not exhaustively, some solutions. The topics receiving deepest study are: cases matching, inconsistency handling and summarizing data. © 2001 John Wiley & Sons, Inc.

Abductive inference in Bayesian belief networks is intended as the process of generating the K most probable configurations given an observed evidence. These configurations are called explanations and in most of the approaches found in the literature, all the explanations have the same number of literals. In this paper we propose some criteria to simplify the explanations in such a way that the resulting configurations are still accounting for the observed facts. Computational methods to perform the simplification task are also presented. Finally the algorithms are experimentally tested using a set of experiments which involves three different Bayesian belief networks.

This paper presents non-random algorithms for approximate computation in Bayesian networks. They are based on the use of probability trees to represent probability potentials, using the Kullback-Leibler cross entropy as a measure of the error of the approximation. Different alternatives are presented and tested in several experiments with difficult propagation problems. The results show how it is possible to find good approximations in short time compared with Hugin algorithm. © 2000 John Wiley & Sons, Inc.

In belief functions, there are two types of uncertainty which are due to lack of knowledge: randomness and non-specificity. In this paper, we present a non-specificity measure for convex sets of probability distributions that generalizes Dubois and Prade's non-specificity measure in the Dempster-Shafer theory of evidence.

Resolution is an often used method for deduction in propositional logic. Here a proper organization of deduction is proposed which avoids redundant computations. It is based on a generic framework of decompositions and local computations as introduced by Shenoy and Shafer. The system contains the two basic operations with information, namely marginalization (or projection) and combination; the latter being an idempotent operation in the present case. The theory permits the conception of an architecture of distributed computing. As an important application assumption-based reasoning is discussed.

This paper presents an abstract definition of partial inconsistency and one operator used to remove it: normalization. When there is partial inconsistency in the combination of two pieces of information, this partial inconsistency is propagated to all the information in the system thereby degrading it. To avoid this effect, it is necessary to apply normalization. Four different formalisms are studied as particular cases of the axiomatic framework presented in this paper: probability theory, infinitesimal probabilities, possibility theory, and symbolic evidence theory. It is shown how, in one of these theories (probability), normalization is not an important problem: a property which is verified in this case gives rise to the equivalence of all the different normalization strategies. Things are very different for the other three theories: there are a number of different normalization procedures. The main objective of this paper will be to determine conditions based on general principles indicating how and when the normalization operator should be applied. © 1997 John Wiley & Sons, Inc.

In this article a new algorithm is presented for the propagation of probabilities in junction trees. It is based on a hybrid methodology. Given a junction tree, some of the nodes carry out an exact calculation, and the other an approximation by Monte Carlo methods. For the exact calculation we will use Shafer/Shenoy method and for the Monte Carlo estimation a general class of importance sampling algorithms is used. We briefly study how to apply this sampler on the clusters in a junction tree. The basic algorithm and some of its variations are presented, depending on the family of functions to which we apply the importance sampler: potentials or/and messages in the tree. An experimental evaluation is carried out, comparing their performance with the well-known likelihood weighting approximated algorithm. This family of methods shows a very promising performance. © John Wiley & Sons, Inc.

We study probability intervals as an interesting tool to represent uncertain information. A number of basic operations necessary to develop a calculus with probability intervals, such as combination, marginalization, conditioning and integration are studied in detail. Moreover, probability intervals are compared with other uncertainty theories, such as lower and upper probabilities, Choquet capacities of order two and belief and plausibility functions. The advantages of probability intervals with respect to these formalisms in computational efficiency are also highlighted.

In order to propagate uncertain information through a belief network, we need tools for both forward and backward propagation. In this article we propose a mechanism to propagate uncertain information represented by a very general class of fuzzy measures (namely, lower and upper probabilities) forward. Once the general solution to this problem is established, we study several interesting particular cases by considering classes of fuzzy measures more restrictive than lower and upper probabilities. Finally, in order to handle only possibility measures, some approximation techniques of the resultant measures are considered.

In this article a concept of conditional fuzzy measure is presented, which is a generalization of conditional probability measure. Its properties are studied in the general case and in some particular types of fuzzy measures as representable measures, capacities of order two, and belief-plausibility measures. In the case of capacities of order two it coincides with the concept given by Dempster for representable measures. However, it differs from the Dempster's rule for conditioning belief-plausibility measures. As it is shown, Dempster's rule of conditioning is based on the idea of combining information and our definition is based on a restriction in the set of possible worlds.