We make three novel contributions to parameter learning and inference in probabilistic sentential decision diagrams (PSDDs). First, rather than traversing the entire PSDD during parameter learning for each dataset example, we pioneer the use of determinism to focus only on the activated partition. Second, we demonstrate how to prune deterministic computation in inference, thereby eliminating the need to propagate probability over every node in the network for each query. Third, we introduce a technique that parallelizes a single circuit evaluation, rather than parallelizing individual multiplications or layer-wise inference. For both learning and inference, experimental results on benchmark PSDDs from various application domains demonstrate state-of-the-art performance.

Fast arc-reversal (FAR) was recently proposed as a new exact inference algorithm in discrete Bayesian networks (BNs), merging favourable features of Arc-reversal (AR) and Variable elimination (VE). AR constantly maintains a sub-BN structure when rendering a variable barren via arc reversals, often requiring more computational effort than VE, which sacrifices a sub-BN structure by directly eliminating a variable. It was formally established that FAR can recover a unique and sound sub-BN structure after consecutive variable eliminations. Experimental results on real-world benchmark networks empirically show an improvement in the average run-time and variance of FAR compared to AR. A novel method, called d-contraction , was suggested for graphically understanding FAR since FAR is not always the same as a sequence of arc reversals. Here, we extend this work by formally establishing that AR's sub-DAG is necessarily contained within FAR's sub-DAG. Unfortunately, neither FAR nor AR can guarantee the construction of minimal I-maps, although both methods may subsequently recover minimal I-mapness. Finally, it is shown how FAR improves Sum-Product network interpretability by relaxing a restriction on the elimination ordering used.

We give conditions under which convolutional neural networks (CNNs) define valid sum-product networks (SPNs). One subclass, called convolutional SPNs (CSPNs), can be implemented using tensors, but also can suffer from being too shallow. Fortunately, tensors can be augmented while maintaining valid SPNs. This yields a larger subclass of CNNs, which we call deep convolutional SPNs (DCSPNs), where the convolutional and sum-pooling layers form rich directed acyclic graph structures. One salient feature of DCSPNs is that they are a rigorous probabilistic model. As such, they can exploit multiple kinds of probabilistic reasoning, including marginal inference and most probable explanation (MPE) inference. This allows an alternative method for learning DCSPNs using vectorized differentiable MPE, which plays a similar role to the generator in generative adversarial networks (GANs). Image sampling is yet another application demonstrating the robustness of DCSPNs. Our preliminary results on image sampling are encouraging, since the DCSPN sampled images exhibit variability. Experiments on image completion show that DCSPNs significantly outperform competing methods by achieving several state-of-the-art mean squared error (MSE) scores in both left-completion and bottom-completion in benchmark datasets.

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.

We suggestDarwinian Networks(DNs) as a simplification of working withBayesian networks(BNs). DNs adapt a handful of well‐known concepts in biology into a single framework that is surprisingly simple yet remarkably robust. With respect to modeling, on one hand, DNs not only represent BNs but also faithfully represent the testing of independencies in a more straightforward fashion. On the other hand, with respect to three exact inference algorithms in BNs, DNs simplify each of them while unifying all of them. DNs can determine good elimination orderings using the same platform as used for modeling and inference. Finally, we demonstrate how DNs can represent two additional frameworks. Practical benefits of DNs include faster algorithms for inference and modeling.

Current join tree propagation algorithms treat all propagated messages as being of equal importance. On the contrary, it is often the case in real-world Bayesian networks that only some of the messages propagated from one join tree node to another are relevant to subsequent message construction at the receiving node. In this article, we propose the first join tree propagation algorithm that identifies and constructs the relevant messages first. Our approach assigns lower priority to the irrelevant messages as they only need to be constructed so that posterior probabilities can be computed when propagation terminates. Experimental results, involving the processing of evidence in four real-world Bayesian networks, empirically demonstrate an improvement over the state-of-the-art method for exact inference in discrete Bayesian networks. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

We propose the first join tree (JT) propagation architecture that labels the probability information passed between JT nodes in terms of conditional probability tables (CPTs) rather than potentials. By modeling the task of inference involving evidence, we can generate three work schedules that are more time-efficient for LAZY propagation. Our experimental results, involving five real-world or benchmark Bayesian networks (BNs), demonstrate a reasonable improvement over LAZY propagation. Our architecture also models inference not involving evidence. After the CPTs identified by our architecture have been physically constructed, we show that each JT node has a sound, local BN that preserves all conditional independencies of the original BN. Exploiting inference not involving evidence is used to develop an automated procedure for building multiply sectioned BNs. It also allows direct computation techniques to answer localized queries in local BNs, for which the empirical results on a real-world medical BN are promising. Screen shots of our implemented system demonstrate the improvements in semantic knowledge.

Most approaches to mining association rules implicitly consider the utilities of the itemsets to be equal. We assume that the utilities of itemsets may differ, and identify the high utility itemsets based on information in the transaction database and external information about utilities. Our theoretical analysis of the resulting problem lays the foundation for future utility mining algorithms.

Web Intelligence is a direction for scientific research that explores practical applications of Artificial Intelligence to the next generation of Web-empowered systems. In this paper, we present a Web-based intelligent tutoring system for computer programming. The decision making process conducted in our intelligent system is guided by Bayesian networks, which are a formal framework for uncertainty management in Artificial Intelligence based on probability theory. Whereas many tutoring systems are static HTML Web pages of a class textbook or lecture notes, our intelligent system can help a student navigate through the online course materials, recommend learning goals, and generate appropriate reading sequences.

WIC Canada promotes the collaboration between Canadian researchers on Web Intelligence, facilitates exchange with other WIC centers. WIC Canada researchers work on a diversity of WI related research areas: foundations of Web Intelligence, Web-based support systems, Bayesian networks, and IntelligentWeb Information Systems (IWIS). Their results have appeared in reputable journals and the annual IEEE/WIC/ACM International Conference onWeb Intelligence. In the next few years, WIC Canada will focus on promotingWeb Intelligence research, attracting new members, and forming new centres. The WIC Canada will play the role of coordinating those activities. WIC Canada needs your input for its growth. Your participation will be greatly appreciated. All questions and suggestions should be directed to our Co-ordinator, Dr. Jingtao Yao, at [email protected].

Hierarchical Markov networks (HMNs) were recently proposed as a faithful representation of Bayesian networks. We propose a query processing algorithm for HMNs. This method takes one query processing algorithm for a traditional Markov network and extends it to a hierarchy of Markov networks. Experimental results explicitly demonstrate the effectiveness of our approach. The work here will then be useful to any problem utilizing Bayesian networks, such as traditional information retrieval, Web search, user profiling, multi-agents and e-commerce.

Several researchers have suggested that Bayesian networks be used in web search and user profiling. One advantage of this approach is that Bayesian networks are more general than the probabilistic models previously used in information retrieval. In practice, experimental results demonstrate the effectiveness the modern Bayesian network approach. On the other hand, since Bayesian networks are defined solely upon the notion of probabilistic conditional independence, these encouraging results do not take advantage of the more general probabilistic independencies recently proposed. In this paper, we show how to exploit contextual independencies in both web search and user profiling. Whereas a conditional independence must hold over all contexts, a contextual independence need only hold for one particular context. For web search applications, it is shown how contextual independencies can be modeled using multiple Bayesian networks. We also point to a more general learning approach for user profiling applications.

The discovery of FDs from databases has recently become a significant research problem. In this paper, we propose a new algorithm, called FD-Mine. FD-Mine takes advantage of the rich theory of FDs to reduce both the size of the dataset and the number of FDs to be checked by using discovered equivalences. We show that the pruning does not lead to loss of information. Experiments on 15 UCI datasets show that FD-Mine can prune more candidates than previous methods.

A probabilistic network consists of a dependency structure and corresponding probability tables. The dependency structure is a graphical representation of the conditional independencies that are known to hold in the problem domain. We propose an automated process for constructing the combined dependency structure of a multiagent probabilistic network. Each domain expert supplies any known conditional independency information and not necessarily an explicit dependency structure. Our method determines a succinct representation of all the supplied independency information called a minimal cover. This process involves detecting all inconsistent information and removing all redundant information. A unique dependency structure of the multiagent probabilistic network can be constructed directly from this minimal cover. The main result is that the constructed dependency structure is a perfect-map of the minimal cover. That is, every probabilistic conditional independency logically implied by the minimal cover can be inferred from the dependency structure and every probabilistic conditional independency inferred from the dependency structure is logically implied by the minimal cover.

The implication problem is to test whether a given set of independencies logically implies another independency. This problem is crucial in the design of a probabilistic reasoning system. We advocate that Bayesian networks are a generalization of standard relational databases. On the contrary, it has been suggested that Bayesian networks are different from the relational databases because the implication problem of these two systems does not coincide for some classes of probabilistic independencies. This remark, however, does not take into consideration one important issue, namely, the solvability of the implication problem. In this comprehensive study of the implication problem for probabilistic conditional independencies, it is emphasized that Bayesian networks and relational databases coincide on solvable classes of independencies. The present study suggests that the implication problem for these two closely related systems differs only in unsolvable classes of independencies. This means there is no real difference between Bayesian networks and relational databases, in the sense that only solvable classes of independencies are useful in the design and implementation of these knowledge systems. More importantly, perhaps, these results suggest that many current attempts to generalize Bayesian networks can take full advantage of the generalizations made to standard relational databases.

Introduces a probabilistic relational data model as the basis for developing multi-agent probabilistic reasoning systems. Since our model subsumes the traditional relational data model, it immediately follows that we can take full advantage of the existing distributed and concurrency control techniques to address the undesirable characteristics exhibited by current multi-agent probabilistic reasoning systems. Thereby, our probabilistic relational data model has important theoretical and practical ramifications. One unified model allows the cross-fertilization of techniques, and serves as a basis for implementing one system for both of these similar domains.

Data dependencies are used in database schema design to enforce the correctness of a database as well as to reduce redundant data. These dependencies are usually determined from the semantics of the attributes and are then enforced upon the relations. This article describes a bottom-up procedure for discovering multivalued dependencies (MVDs) in observed data without knowing a priori the relationships among the attributes. The proposed algorithm is an application of the technique we designed for learning conditional independencies in probabilistic reasoning. A prototype system for automated database schema design has been implemented. Experiments were carried out to demonstrate both the effectiveness and efficiency of our method. © 1998 John Wiley & Sons, Inc.