Causal Bayesian networks (CBN) are popular graphical probabilistic models that encode causal relations among variables. Learning their graphical structure from observational data has received a lot of attention in the literature. When there exists no latent (unobserved) confounder, i.e., no unobserved direct common cause of some observed variables, learning algorithms can be divided essentially into two classes: constraint-based and score-based approaches. The latter are often thought to be more robust than the former and to produce better results. However, to the best of our knowledge, when variables are discrete, no score-based algorithm is capable of dealing with latent confounders. This paper introduces the first fully score-based structure learning algorithm searching the space of DAGs (directed acyclic graphs) that is capable of identifying the presence of some latent confounders. It is justified mathematically and experiments highlight its effectiveness.

Abstract Testing independencies is a fundamental task in reasoning withBayesian networks(BNs). In practice,d‐separationis often used for this task, since it has linear‐time complexity. However, many have had difficulties understanding d‐separation in BNs. An equivalent method that is easier to understand, calledm‐separation, transforms the problem from directed separation in BNs into classical separation in undirected graphs. Two main steps of this transformation are pruning the BN and adding undirected edges. In this paper, we proposeu‐separationas an even simpler method for testing independencies in a BN. Our approach also converts the problem into classical separation in an undirected graph. However, our method is based upon the novel concepts of inaugural variables and rationalization. Thereby, the primary advantage of u‐separation over m‐separation is that m‐separation can prune unnecessarily and add superfluous edges. Our experiment results show that u‐separation performs 73% fewer modifications on average than m‐separation.

Faithfulness is one of the main hypotheses on which rely most Bayesian network (BN) structure learning algorithms. When some random variables are deterministically determined by others, faithfulness is ruled out and classical learning algorithms fail to discover many dependences between variables, hence producing incorrect BNs. Even state-of-the-art algorithms dedicated to learning with deterministic variables prove to be inefficient to discover many dependences/independences. For critical applications, e.g., in nuclear safety, such failure is a serious issue. This paper introduces a new hybrid algorithm, combining a constraint-based approach with a greedy search, that includes specific rules dedicated to deterministic nodes that significantly reduce the incorrect learning. Experiments show that our method significantly outperforms state-of-the-art algorithms.

We propose an original particle filtering-based approach combining optimization and decomposition techniques for sequential non-parametric density estimation defined in high-dimensional state spaces. Our method relies on Annealing to focus on the correct distributions and on probabilistic conditional independences defined by Dynamic Bayesian Networks to focus samples on their modes. After proving its theoretical correctness and showing its complexity, we highlight its ability to track single and multiple articulated objects both on synthetic and real video sequences. We show that our approach is particularly effective, both in terms of estimation errors and computation times.

In this paper, we propose a novel approach to speed-up the computation of the histograms of multiple overlapping non rotating regions of a single image. The idea is to exploit the overlaps between regions to minimize the number of redundant computations. More precisely, once the histogram of a region has been computed, this one can be used to compute part of the histogram of another overlapping region. For this purpose, an optimal computation order of the regions needs to be determined and we show how this can be obtained as the solution of a minimum spanning tree of a graph modeling the overlaps between regions. This tree is computed using Kruskal's algorithm and parsing it in a depth-first search manner determines precisely how the histogram of a region can be computed efficiently from that of its parent in the tree. We show that, in practical situations, this approach can outperform the well-known integral histogram both in terms of computation times and in terms of memory consumption.