International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems

Standard methods for solving influence diagrams consist in stepwise elimination of variables, and along with elimination of a variable a set of new potentials over new domains is calculated. It is well known that these methods tend to produce unnecessarily large domains resulting in excessive consumption of time and memory. The lazy evaluation method represents only a partial solution to the problem. In this paper we extend any potential with two graphs over its domain representing the dependencies of variables. When a node A is eliminated, all necessary structural information for establishing the minimal sets of domains for potentials is contained in these graphs. We push lazy evaluation a step further to avoid performing unnecessary multiplications and subsequent division with equivalent potentials.

We adopt probabilistic decision graphs developed in the field of automated verification as a tool for probabilistic model representation and inference. We show that probabilistic inference has linear time complexity in the size of the probabilistic decision graph, that the smallest probabilistic decision graph for a given distribution is at most as large as the smallest junction tree for the same distribution, and that in some cases it can in fact be much smaller. Behind these very promising features of probabilistic decision graphs lies the fact that they integrate into a single coherent framework a number of representational and algorithmic optimizations developed for Bayesian networks (use of hidden variables, context-specific independence, structured representation of conditional probability tables).

One of the most common ways of representing classes of equivalent Bayesian networks is the use of essential graphs which are also known in the literature as completed patterns or completed pdags. The name essential graph was proposed by Andersson, Madigan and Perlman who also gave a graphical characterization of essential graphs. In this paper an alternative characterization of essential graphs is presented. The main observation is that every essential graph is the largest chain graph within a special class of chain graphs. More precisely, every equivalence class of Bayesian networks is contained in an equivalence class of chain graphs without flags (= certain induced subgraphs). A special operation of legal merging of (connectivity) components for a chain graph without flags is introduced. This operation leads to an algorithm for finding the essential graph on the basis of any graph in that equivalence class of chain graphs without flags which contains the equivalence class of a Bayesian network. In particular, the algorithm may start with any Bayesian network.

This paper proposes using estimation of distribution algorithms for unsupervised learning of Bayesian networks, directly as well as within the framework of the Bayesian structural EM algorithm. Both approaches are empirically evaluated in synthetic and real data. Specifically, the evaluation in real data consists in the application of this paper's proposals to gene expression data clustering, i.e., the identification of clusters of genes with similar expression profiles across samples, for the leukemia database. The validation of the clusters of genes that are identified suggests that these may be biologically meaningful.

In this paper we discuss applications of Bayesian networks to educational testing. Namely, we deal with the diagnosis of person's skills. We show that when modeling dependence between skills we can get better diagnosis faster. We present results of experiments with basic operations that use fractions. The experiments suggest that the test design can benefit from a Bayesian network that models relations between skills, not only in the case of an adaptive test but also when designing a fixed (non-adaptive) test.