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.

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.

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.

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.

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.

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.

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.