Join tree propagation utilizing both arc reversal and variable elimination

In this paper, we put forth the first join tree propagation algorithm that selectively applies either arc reversal (AR) or variable elimination (VE) to build the propagated messages. Our approach utilizes a recent method for identifying the propagated join tree messages à priori. When it is determined that a join tree node will construct a single distribution to be sent to a neighbouring node, VE is utilized as it builds a single distribution in the most direct fashion; otherwise, AR is applied as it maintains a factorization of distributions allowing for barren variables to be exploited during propagation later on in the join tree. Experimental results, involving evidence processing in four benchmark Bayesian networks, empirically demonstrate that selectively applying VE and AR is faster than applying one of these methods exclusively on the entire network.     

<Emphasis Type="Italic">Graph_sampler</Emphasis>: a simple tool for fully Bayesian analyses of DAG-models

Bayesian networks (BNs) are widely used graphical models usable to draw statistical inference about directed acyclic graphs. We presented here Graph_sampler a fast free C language software for structural inference on BNs. Graph_sampler uses a fully Bayesian approach in which the marginal likelihood of the data and prior information about the network structure are considered. This new software can handle both the continuous as well as discrete data and based on the data type two different models are formulated. The software also provides a wide variety of structure prior which can depict either the global or local properties of the graph structure. Now based on the type of structure prior selected, we considered a wide range of possible values for the prior making it either informative or uninformative. We proposed a new and much faster jumping kernel strategy in the Metropolis–Hastings algorithm. The source C code distributed is very compact, fast, uses low memory and disk storage. We performed out several analyses based on different simulated data sets and synthetic as well as real networks to discuss the performance of Graph_sampler.     

Inference in hybrid Bayesian networks using mixtures of polynomials

The main goal of this paper is to describe inference in hybrid Bayesian networks (BNs) using mixture of polynomials (MOP) approximations of probability density functions (PDFs). Hybrid BNs contain a mix of discrete, continuous, and conditionally deterministic random variables. The conditionals for continuous variables are typically described by conditional PDFs. A major hurdle in making inference in hybrid BNs is marginalization of continuous variables, which involves integrating combinations of conditional PDFs. In this paper, we suggest the use of MOP approximations of PDFs, which are similar in spirit to using mixtures of truncated exponentials (MTEs) approximations. MOP functions can be easily integrated, and are closed under combination and marginalization. This enables us to propagate MOP potentials in the extended Shenoy-Shafer architecture for inference in hybrid BNs that can include deterministic variables. MOP approximations have several advantages over MTE approximations of PDFs. They are easier to find, even for multi-dimensional conditional PDFs, and are applicable for a larger class of deterministic functions in hybrid BNs.     

Improvements to message computation in lazy propagation

Even though existing algorithms for belief update in Bayesian networks (BNs) have exponential time and space complexity, belief update in many real-world BNs is feasible. However, in some cases the efficiency of belief update may be insufficient. In such cases minor improvements in efficiency may be important or even necessary to make a task tractable. This paper introduces two improvements to the message computation in Lazy propagation (LP): (1) we introduce myopic methods for sorting the operations involved in a variable elimination using arc-reversal and (2) extend LP with the any-space property. The performance impacts of the methods are assessed empirically.     

On a problem in quantum summation

We consider the computation of the mean of sequences in the quantum model of computation. We determine the query complexity in the case of sequences which satisfy a p-summability condition for 1⩽p<2. This settles a problem left open in Heinrich (J. Complexity 18 (2002) 1).     

Non-impeding noisy-AND tree causal models over multi-valued variables

To specify a Bayesian network (BN), a conditional probability table (CPT), often of an effect conditioned on its n causes, must be assessed for each node. Its complexity is generally exponential in n. Noisy-OR and a number of extensions reduce the complexity to linear, but can only represent reinforcing causal interactions. Non-impeding noisy-AND (NIN-AND) trees are the first causal models that explicitly express reinforcement, undermining, and their mixture. Their acquisition has a linear complexity, in terms of both the number of parameters and the size of the tree topology. As originally proposed, however, they allow only binary effects and causes. This work generalizes binary NIN-AND tree models to multi-valued effects and causes. It is shown that the generalized NIN-AND tree models express reinforcement, undermining, and their mixture at multiple levels, relative to each active value of the effect. The model acquisition is still efficient. For binary variables, they degenerate into binary NIN-AND tree models. Hence, this contribution enables CPTs of discrete BNs of arbitrary variables (binary or multi-valued) to be specified efficiently through the intuitive concepts of reinforcement and undermining.     

Structured probabilistic inference

Probabilistic inference is among the main topics with reasoning in uncertainty in AI. For this purpose, Bayesian Networks (BNs) is one of the most successful and efficient Probabilistic Graphical Model (PGM) so far. Since the mid-90s, a growing number of BNs extensions have been proposed. Object-oriented, entity-relationship and first-order logic are the main representation paradigms used to extend BNs. While entity-relationship and first-order models have been successfully used for machine learning in defining lifted probabilistic inference, object-oriented models have been mostly underused. Structured inference, which exploits the structural knowledge encoded in an object-oriented PGM, is a surprisingly unstudied technique. In this paper we propose a full object-oriented framework for PRM and propose two extensions of the state-of-the-art structured inference algorithm: SPI which removes the major flaws of existing algorithms and SPISBB which largely enhances SPI by using d-separation.     

Optimization approach for data allocation in multidisk database

In the last decade, many parallel process mechanisms have been developed in information systems for enhancing their performance. But I/O throughput rates are still the bottleneck for data processing in the systems. In particular, relational database systems encounter this performance problem dealing with expensive operations such as the join operation. To treat a class of two-way join problems in database, Rotem et al. proposed a linearization method for finding the optimal allocation of relations to multidisk database such that the expected query cost is minimized. For the multidisk allocation problem with N relations and M disks, their model needs MN+N(N−1)/2+MN(N−1)/2 0–1 variables. This paper proposes a concise method to reformulate the same problem, which requires only MN+N(N−1)/2 0–1 variables. The problem can hence be more efficiently solved by the concise method. The analytical superiority of the concise method in terms of the number of iterations and execution times can be seen, through a computational experiment conducted on a set of generated test examples.     

Gated Bayesian networks for algorithmic trading

This paper introduces a new probabilistic graphical model called gated Bayesian network (GBN). This model evolved from the need to represent processes that include several distinct phases. In essence, a GBN is a model that combines several Bayesian networks (BNs) in such a manner that they may be active or inactive during queries to the model. We use objects called gates to combine BNs, and to activate and deactivate them when predefined logical statements are satisfied. In this paper we also present an algorithm for semi-automatic learning of GBNs. We use the algorithm to learn GBNs that output buy and sell decisions for use in algorithmic trading systems. We show how the learnt GBNs can substantially lower risk towards invested capital, while they at the same time generate similar or better rewards, compared to the benchmark investment strategy buy-and-hold. We also explore some differences and similarities between GBNs and other related formalisms.     

Inference in hybrid Bayesian networks with mixtures of truncated exponentials

Mixtures of truncated exponentials (MTE) potentials are an alternative to discretization for solving hybrid Bayesian networks. Any probability density function (PDF) can be approximated with an MTE potential, which can always be marginalized in closed form. This allows propagation to be done exactly using the Shenoy–Shafer architecture for computing marginals, with no restrictions on the construction of a join tree. This paper presents MTE potentials that approximate an arbitrary normal PDF with any mean and a positive variance. The properties of these MTE potentials are presented, along with examples that demonstrate their use in solving hybrid Bayesian networks. Assuming that the joint density exists, MTE potentials can be used for inference in hybrid Bayesian networks that do not fit the restrictive assumptions of the conditional linear Gaussian (CLG) model, such as networks containing discrete nodes with continuous parents.     

An architecture independent study of parallel segment trees

We study the computation, communication and synchronization requirements related to the construction and search of parallel segment trees in an architecture independent way. Our proposed parallel algorithms are optimal in space and time compared to the corresponding sequential algorithms utilized to solve the introduced problems and are described in the context of the bulk-synchronous parallel (BSP) model of computation. Our methods are more scalable and can thus be made to work for larger values of processor size p relative to problem size n than other segment tree related algorithms that have been described on other realistic distributed-memory parallel models and also provide a natural way to approach searching problems on latency-tolerant models of computation that maintains a balanced query load among the processors.     

The complexity of partial match retrieval in a dynamic setting

The partial match retrieval problem analyzed in this paper is described as follows. Given a positive integer d, a record having d binary attributes consists of a d dimensional binary vector, referred to as the record's key, and a quantity which lies in a commutative semigroup, referred to as the value of the record. Given a set of such records having distinct keys, a partial match query is a request for the sum of the values of all records in the set whose keys lie in a hyperrectangle specified by the query. We consider the problem of designing data structures which permit insertions and deletions of records, and partial match queries. Among our results is the following. There exist data structures which accommodate arbitrary sequences of N manipulations (insertions, deletions, and queries) in (worst case) time approximately (1.226)^dN. Moreover, relative to an appropriate model of computation, this complexity is best possible.     

On the range maximum-sum segment query problem

The range minimum query problem, RMQ for short, is to preprocess a sequence of real numbers A[1…n] for subsequent queries of the form: “Given indices i, j, what is the index of the minimum value of A[i…j]?” This problem has been shown to be linearly equivalent to the LCA problem in which a tree is preprocessed for answering the lowest common ancestor of two nodes. It has also been shown that both the RMQ and LCA problems can be solved in linear preprocessing time and constant query time under the unit-cost RAM model. This paper studies a new query problem arising from the analysis of biological sequences. Specifically, we wish to answer queries of the form: “Given indices i and j, what is the maximum-sum segment of A[i…j]?” We establish the linear equivalence relation between RMQ and this new problem. As a consequence, we can solve the new query problem in linear preprocessing time and constant query time under the unit-cost RAM model. We then present alternative linear-time solutions for two other biological sequence analysis problems to demonstrate the utilities of the techniques developed in this paper.     

A Graphical Approach to Diagnosing the Validity of the Conditional Independence Assumptions of a Bayesian Network Given Data

Bayesian networks (BNs) have attained widespread use in data analysis and decision making. Well-studied topics include efficient inference, evidence propagation, parameter learning from data for complete and incomplete data scenarios, expert elicitation for calibrating BN probabilities, and structure learning. It is common for the researcher to assume the structure of the BN or to glean the structure from expert elicitation or domain knowledge. In this scenario, the model may be calibrated through learning the parameters from relevant data. There is a lack of work on model diagnostics for fitted BNs; this is the contribution of this article. We key on the definition of (conditional) independence to develop a graphical diagnostic that indicates whether the conditional independence assumptions imposed, when one assumes the structure of the BN, are supported by the data. We develop the approach theoretically and describe a Monte Carlo method to generate uncertainty measures for the consistency of the data with conditional independence assumptions under the model structure. We describe how this theoretical information and the data are presented in a graphical diagnostic tool. We demonstrate the approach through data simulated from BNs under different conditional independence assumptions. We also apply the diagnostic to a real-world dataset. The results presented in this article show that this approach is most feasible for smaller BNs—this is not peculiar to the proposed diagnostic graphic, but rather is related to the general difficulty of combining large BNs with data in any manner (such as through parameter estimation). It is the authors’ hope that this article helps highlight the need for more research into BN model diagnostics. This article has supplementary materials online.     

Permutability of rules in lattice theory

Lattice theory with the meet and join operations is formulated as a system of rules of inference. The order of application of these rules can be permuted so that a subterm property follows: If an atomic formula is derivable from given atomic formulas by the rules, it has a derivation all terms of which are terms in the given formulas or the conclusion. A direct decision method for universal formulas in lattice theory with the meet and join operations follows.     

Parallel Construction and Query of Index Data Structures for Pattern Matching on Square Matrices

We describe fast parallel algorithms for building index data structures that can be used to gather various statistics on square matrices. The main data structure is the Lsuffix tree, which is a generalization of the classical suffix tree for strings. Given ann×ntext matrixA, we build our data structures inO(log n) time withn²processors on a CRCW PRAM, so that we can quickly processAin parallel as follows: (i) report some statistical information aboutA, e.g., find the largest repeated square submatrices that appear at least twice inAor determine, for each position inA, the smallest submatrix that occurs only there; (ii) given, on-line, anm×mpattern matrixPAT, check whether it occurs inA. We refer to the above two kinds of operations as queries and point out that they have applications to visual databases and two-dimensional data compression. Query (i) takesO(log n) time withn²/log nprocessors and query (ii) takesO(log m) time withm²/log mprocessors. The query algorithms are work optimal while the construction algorithm is work optimal only for arbitrary and large alphabets.     

Computational Aspects of Optional Pólya Tree

Optional Pólya tree (OPT) is a flexible nonparametric Bayesian prior for density estimation. Despite its merits, the computation for OPT inference is challenging. In this article, we present time complexity analysis for OPT inference and propose two algorithmic improvements. The first improvement, named limited-lookahead optional Pólya tree (LL-OPT), aims at accelerating the computation for OPT inference. The second improvement modifies the output of OPT or LL-OPT and produces a continuous piecewise linear density estimate. We demonstrate the performance of these two improvements using simulated and real date examples.     

A methodology for developing Bayesian networks: An application to information technology (IT) implementation

Bayesian Networks (BNs) are probabilistic inference engines that support reasoning under uncertainty. This article presents a methodology for building an information technology (IT) implementation BN from client–server survey data. The article also demonstrates how to use the BN to predict the attainment of IT benefits, given specific implementation characteristics (e.g., application complexity) and activities (e.g., reengineering). The BN is an outcome of a machine learning process that finds the network’s structure and its associated parameters, which best fit the data. The article will be of interest to academicians who want to learn more about building BNs from real data and practitioners who are interested in IT implementation models that make probabilistic statements about certain implementation decisions.     

Hill-climbing and branch-and-bound algorithms for exact and approximate inference in credal networks

This paper proposes two new algorithms for inference in credal networks. These algorithms enable probability intervals to be obtained for the states of a given query variable. The first algorithm is approximate and uses the hill-climbing technique in the Shenoy–Shafer architecture to propagate in join trees; the second is exact and is a modification of Rocha and Cozman’s branch-and-bound algorithm, but applied to general directed acyclic graphs.