Bayesian networks for supporting query processing over incomplete autonomous databases

As the information available to naïve users through autonomous data sources continues to increase, mediators become important to ensure that the wealth of information available is tapped effectively. A key challenge that these information mediators need to handle is the varying levels of incompleteness in the underlying databases in terms of missing attribute values. Existing approaches such as QPIAD aim to mine and use Approximate Functional Dependencies (AFDs) to predict and retrieve relevant incomplete tuples. These approaches make independence assumptions about missing values—which critically hobbles their performance when there are tuples containing missing values for multiple correlated attributes. In this paper, we present a principled probabilistic alternative that views an incomplete tuple as defining a distribution over the complete tuples that it stands for. We learn this distribution in terms of Bayesian networks. Our approach involves mining/“learning” Bayesian networks from a sample of the database, and using it to do both imputation (predict a missing value) and query rewriting (retrieve relevant results with incompleteness on the query-constrained attributes, when the data sources are autonomous). We present empirical studies to demonstrate that (i) at higher levels of incompleteness, when multiple attribute values are missing, Bayesian networks do provide a significantly higher classification accuracy and (ii) the relevant possible answers retrieved by the queries reformulated using Bayesian networks provide higher precision and recall than AFDs while keeping query processing costs manageable.     

Approximating Bayesian belief networks by arc removal

I propose a general framework for approximating Bayesian belief networks through model simplification by arc removal. Given an upper bound on the absolute error allowed on the prior and posterior probability distributions of the approximated network, a subset of arcs is removed, thereby speeding up probabilistic inference     

MIS approach analyzing the controllability of switched boolean networks with higher order

Controllability of higher order switched Boolean control networks (SBCNs) is investigated in this paper. Two algebraic forms of higher order SBCNs are derived. A necessary and sufficient condition of controllability for higher order SBCNs is obtained. An algorithm is derived to calculate the corresponding control and switching-law which drive a point to a given reachable point. Then we talk about the compatibility between our main results and other systems. Finally, two illustrative examples are given to show the validity of the main results.     

Representing the behaviour of supervised classification learning algorithms by Bayesian networks

In this paper, an approach to study the nature of the classification models induced by Machine Learning algorithms is proposed. Instead of the predictive accuracy, the values of the predicted class labels are used to characterize the classification models. Over these predicted class labels Bayesian networks are induced. Using these Bayesian networks, several assertions are extracted about the nature of the classification models induced by Machine Learning algorithms.     

An average optimal control approach to the set stabilization problem for boolean control networks

This paper addresses the set stabilization problem for deterministic Boolean control networks (BCNs). An optimal control approach is investigated to solve the problems by using the semi‐tensor product of matrices, where a policy iteration algorithm for the set stabilization problem is deduced. Finally, the intervention problem of a cAMP receptor protein is addressed in the framework of the set stabilization problem. The problem is solved to validate the effectiveness of the proposed policy iteration approach for a practical application.     

Efficient inferencing for sigmoid Bayesian networks by reducing sampling space

A sigmoid Bayesian network is a Bayesian network in which a conditional probability is a sigmoid function of the weights of relevant arcs. Its application domain includes that of Boltzmann machine as well as traditional decision problems. In this paper we show that the node reduction method that is an inferencing algorithm for general Bayesian networks can also be used on sigmoid Bayesian networks, and we propose a hybrid inferencing method combining the node reduction and Gibbs sampling. The time efficiency of sampling after node reduction is demonstrated through experiments. The results of this paper bring sigmoid Bayesian networks closer to large scale applications.     

Learning Bayesian networks for clustering by means of constructive induction

The purpose of this paper is to present and evaluate a heuristic algorithm for learning Bayesian networks for clustering. Our approach is based upon improving the Naive-Bayes model by means of constructive induction. A key idea in this approach is to treat expected data as real data. This allows us to complete the database and to take advantage of factorable closed forms for the marginal likelihood. In order to get such an advantage, we search for parameter values using the EM algorithm or another alternative approach that we have developed: a hybridization of the Bound and Collapse method and the EM algorithm, which results in a method that exhibits a faster convergence rate and a more effective behaviour than the EM algorithm. Also, we consider the possibility of interleaving runnings of these two methods after each structural change. We evaluate our approach on synthetic and real-world databases.     

Modeling the forensic two-trace problem with Bayesian networks

The forensic two-trace problem is a perplexing inference problem introduced by Evett (J Forensic Sci Soc 27:375–381, 1987). Different possible ways of wording the competing pair of propositions (i.e., one proposition advanced by the prosecution and one proposition advanced by the defence) led to different quantifications of the value of the evidence (Meester and Sjerps in Biometrics 59:727–732, 2003). Here, we re-examine this scenario with the aim of clarifying the interrelationships that exist between the different solutions, and in this way, produce a global vision of the problem. We propose to investigate the different expressions for evaluating the value of the evidence by using a graphical approach, i.e. Bayesian networks, to model the rationale behind each of the proposed solutions and the assumptions made on the unknown parameters in this problem.     

Blind signal processing by complex domain adaptive spline neural networks

In this paper, neural networks based on an adaptive nonlinear function suitable for both blind complex time domain signal separation and blind frequency domain signal deconvolution, are presented. This activation function, whose shape is modified during learning, is based on a couple of spline functions, one for the real and one for the imaginary part of the input. The shape control points are adaptively changed using gradient-based techniques. B-splines are used, because they allow to impose only simple constraints on the control parameters in order to ensure a monotonously increasing characteristic. This new adaptive function is then applied to the outputs of a one-layer neural network in order to separate complex signals from mixtures by maximizing the entropy of the function outputs. We derive a simple form of the adaptation algorithm and present some experimental results that demonstrate the effectiveness of the proposed method.     

基于贝叶斯网络的态势估计方法

分析了态势估计的主要功能,提出态势估计系统以事件检测为核心和起点。分析了使用贝 叶斯网络进行态势估计知识表示问题,并对态势估计中的时空知识表示进行了探讨,提出了构建贝叶斯 网络进行态势估计的步骤,分析了态势估计系统事件的层次。给出一个具体的实例,演示了使用贝叶斯 网络进行态势估计的过程。     

Polynomial expansion of symmetric boolean functions by the table method

Conclusion The proposed method for polynomial expansion of SBF based on construction of the triangular tableT _n(π(F)) of local codes of its derivatives has the lowest computational complexity among known methods. Constructing the table only once, the method easily determines all the “residual” functions ϑ _rl ^km for various expansion parametersk andm. Another advantage of the method is its applicability for polynomial expansion of arbitrary BF and partially symmetric BF. In this case, the base of the “triangle” is the truth table of the arbitrary BF or the local code (including convolved local code) of the partially symmetric BF. The method can be successfully used for the synthesis of a wide class of digital networks. Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 59–71, November–December, 1996.     

Structural learning for Bayesian networks by testing complete separators in prime blocks

In this paper, we consider how to recover the structure of a Bayesian network from a moral graph. We present a more accurate characterization of moral edges, based on which a complete subset (i.e., a separator) contained in the neighbor set of one vertex of the putative moral edge in some prime block of the moral graph can be chosen. This results in a set of separators needing to be searched generally smaller than the sets required by some existing algorithms. A so-called structure-finder algorithm is proposed for structural learning. The complexity analysis of the proposed algorithm is discussed and compared with those for several existing algorithms. We also demonstrate how to construct the moral graph locally from, separately, the Markov blanket, domain knowledge and d-separation trees. Simulation studies are used to evaluate the performances of various strategies for structural learning. We also analyze a gene expression data set by using the structure-finder algorithm.     

On the instability in the dimension of splines spaces over T-meshes

The present paper reveals the instability in the dimension of the spline space S(d₁,d₂,d₁−1,d₂−1,T) over certain types of T-meshes T, that is, the dimension is related to not only the topological information of T but also the geometry of T. This insight suggests us to pay much attention to the structure of the T-meshes in modeling with splines over T-meshes.     

Improving the structure MCMC sampler for Bayesian networks by introducing a new edge reversal move

Applications of Bayesian networks in systems biology are computationally demanding due to the large number of model parameters. Conventional MCMC schemes based on proposal moves in structure space tend to be too slow in mixing and convergence, and have recently been superseded by proposal moves in the space of node orders. A disadvantage of the latter approach is the intrinsic inability to specify the prior probability on network structures explicitly. The relative paucity of different experimental conditions in contemporary systems biology implies a strong influence of the prior probability on the posterior probability and, hence, the outcome of inference. Consequently, the paradigm of performing MCMC proposal moves in order rather than structure space is not entirely satisfactory. In the present article, we propose a new and more extensive edge reversal move in the original structure space, and we show that this significantly improves the convergence of the classical structure MCMC scheme.     

Evaluating the difference between graph structures in Gaussian Bayesian networks

In this work, we evaluate the sensitivity of Gaussian Bayesian networks to perturbations or uncertainties in the regression coefficients of the network arcs and the conditional distributions of the variables. The Kullback–Leibler divergence measure is used to compare the original network to its perturbation. By setting the regression coefficients to zero or non-zero values, the proposed method can remove or add arcs, making it possible to compare different network structures. The methodology is implemented with some case studies.     

On the classification performance of TAN and general Bayesian networks

Over a decade ago, Friedman et al. introduced the Tree Augmented Naïve Bayes (TAN) classifier, with experiments indicating that it significantly outperformed Naïve Bayes (NB) in terms of classification accuracy, whereas general Bayesian network (GBN) classifiers performed no better than NB. This paper challenges those claims, using a careful experimental analysis to show that GBN classifiers significantly outperform NB on datasets analyzed, and are comparable to TAN performance. It is found that the poor performance reported by Friedman et al. are not attributable to the GBN per se, but rather to their use of simple empirical frequencies to estimate GBN parameters, whereas basic parameter smoothing (used in their TAN analyses but not their GBN analyses) improves GBN performance significantly. It is concluded that, while GBN classifiers may have some limitations, they deserve greater attention, particularly in domains where insight into classification decisions, as well as good accuracy, is required.     

Learning Bayesian networks by hill climbing: efficient methods based on progressive restriction of the neighborhood

Learning Bayesian networks is known to be an NP-hard problem and that is the reason why the application of a heuristic search has proven advantageous in many domains. This learning approach is computationally efficient and, even though it does not guarantee an optimal result, many previous studies have shown that it obtains very good solutions. Hill climbing algorithms are particularly popular because of their good trade-off between computational demands and the quality of the models learned. In spite of this efficiency, when it comes to dealing with high-dimensional datasets, these algorithms can be improved upon, and this is the goal of this paper. Thus, we present an approach to improve hill climbing algorithms based on dynamically restricting the candidate solutions to be evaluated during the search process. This proposal, dynamic restriction, is new because other studies available in the literature about restricted search in the literature are based on two stages rather than only one as it is presented here. In addition to the aforementioned advantages of hill climbing algorithms, we show that under certain conditions the model they return is a minimal I-map of the joint probability distribution underlying the training data, which is a nice theoretical property with practical implications. In this paper we provided theoretical results that guarantee that, under these same conditions, the proposed algorithms also output a minimal I-map. Furthermore, we experimentally test the proposed algorithms over a set of different domains, some of them quite large (up to 800 variables), in order to study their behavior in practice.