Changhe Yuan

AAAI Conference 2021 Conference Paper

Improving Causal Discovery By Optimal Bayesian Network Learning

• Ni Y Lu
• Kun Zhang
• Changhe Yuan

Many widely-used causal discovery methods such as Greedy Equivalent Search (GES), although with asymptotic correctness guarantees, have been reported to produce sub-optimal solutions on finite data, or when the causal faithfulness condition is violated. The constraint-based procedure with Boolean satisfiability (SAT) solver, and the recently proposed Sparsest Permutation (SP) algorithm have shown superb performance, but currently they do not scale well. In this work, we demonstrate that optimal score-based exhaustive search is remarkably useful for causal discovery: it requires weaker conditions to guarantee asymptotic correctness, and outperforms wellknown methods including PC, GES, GSP, and NOTEARS. In order to achieve scalability, we also develop an approximation algorithm for larger systems based on the A* method, which scales up to 60+ variables and obtains better results than existing greedy algorithms such as GES, MMHC, and GSP. Our results illustrate the risk of assuming the faithfulness assumption, the advantages of exhaustive search methods, and the limitations of greedy search methods, and shed light on the computational challenges and techniques in scaling up to larger networks and handling unfaithful data.

YNIMG Journal 2019 Journal Article

Anterior insular cortex is a bottleneck of cognitive control

• Tingting Wu
• Xingchao Wang
• Qiong Wu
• Alfredo Spagna
• Jiaqi Yang
• Changhe Yuan
• Yanhong Wu
• Zhixian Gao

Cognitive control, with a limited capacity, is a core process in human cognition for the coordination of thoughts and actions. Although the regions involved in cognitive control have been identified as the cognitive control network (CCN), it is still unclear whether a specific region of the CCN serves as a bottleneck limiting the capacity of cognitive control (CCC). Here, we used a perceptual decision-making task with conditions of high cognitive load to challenge the CCN and to assess the CCC in a functional magnetic resonance imaging study. We found that the activation of the right anterior insular cortex (AIC) of the CCN increased monotonically as a function of cognitive load, reached its plateau early, and showed a significant correlation to the CCC. In a subsequent study of patients with unilateral lesions of the AIC, we found that lesions of the AIC were associated with a significant impairment of the CCC. Simulated lesions of the AIC resulted in a reduction of the global efficiency of the CCN in a network analysis. These findings suggest that the AIC, as a critical hub in the CCN, is a bottleneck of cognitive control.

IJCAI Conference 2019 Conference Paper

Heuristic Search for Homology Localization Problem and Its Application in Cardiac Trabeculae Reconstruction

• Xudong Zhang
• Pengxiang Wu
• Changhe Yuan
• Yusu Wang
• Dimitris Metaxas
• Chao Chen

Cardiac trabeculae are fine rod-like muscles whose ends are attached to the inner walls of ventricles. Accurate extraction of trabeculae is important yet challenging, due to the background noise and limited resolution of cardiac images. Existing works proposed to handle this task by modeling the trabeculae as topological handles for better extraction. Computing optimal representation of these handles is essential yet very expensive. In this work, we formulate the problem as a heuristic search problem, and propose novel heuristic functions based on advanced topological techniques. We show in experiments that the proposed heuristic functions improve the computation in both time and memory.

AAAI Conference 2019 Conference Paper

Learning Diverse Bayesian Networks

• Cong Chen
• Changhe Yuan

Much effort has been directed at developing algorithms for learning optimal Bayesian network structures from data. When given limited or noisy data, however, the optimal Bayesian network often fails to capture the true underlying network structure. One can potentially address the problem by finding multiple most likely Bayesian networks (K-Best) in the hope that one of them recovers the true model. However, it is often the case that some of the best models come from the same peak(s) and are very similar to each other; so they tend to fail together. Moreover, many of these models are not even optimal respective to any causal ordering, thus unlikely to be useful. This paper proposes a novel method for finding a set of diverse top Bayesian networks, called modes, such that each network is guaranteed to be optimal in a local neighborhood. Such mode networks are expected to provide a much better coverage of the true model. Based on a globallocal theorem showing that a mode Bayesian network must be optimal in all local scopes, we introduce an A* search algorithm to efficiently find top M Bayesian networks which are highly probable and naturally diverse. Empirical evaluations show that our top mode models have much better diversity as well as accuracy in discovering true underlying models than those found by K-Best.

UAI Conference 2019 Conference Paper

Variational Training for Large-Scale Noisy-OR Bayesian Networks

• Geng Ji 0001
• Dehua Cheng
• Huazhong Ning
• Changhe Yuan
• Hanning Zhou
• Liang Xiong
• Erik B. Sudderth

We propose a stochastic variational inference algorithm for training large-scale Bayesian networks, where noisy-OR conditional distributions are used to capture higher-order relationships. One application is to the learning of hierarchical topic models for text data. While previous work has focused on two-layer networks popular in applications like medical diagnosis, we develop scalable algorithms for deep networks that capture a multi-level hierarchy of interactions. Our key innovation is a family of constrained variational bounds that only explicitly optimize posterior probabilities for the sub-graph of topics most related to the sparse observations in a given document. These constrained bounds have comparable accuracy but dramatically reduced computational cost. Using stochastic gradient updates based on our variational bounds, we learn noisy-OR Bayesian networks orders of magnitude faster than was possible with prior Monte Carlo learning algorithms, and provide a new tool for understanding large-scale binary data.

JAIR Journal 2016 Journal Article

Exact Algorithms for MRE Inference

• Xiaoyuan Zhu
• Changhe Yuan

Most Relevant Explanation (MRE) is an inference task in Bayesian networks that finds the most relevant partial instantiation of target variables as an explanation for given evidence by maximizing the Generalized Bayes Factor (GBF). No exact MRE algorithm has been developed previously except exhaustive search. This paper fills the void by introducing two Breadth-First Branch-and-Bound (BFBnB) algorithms for solving MRE based on novel upper bounds of GBF. One upper bound is created by decomposing the computation of GBF using a target blanket decomposition of evidence variables. The other upper bound improves the first bound in two ways. One is to split the target blankets that are too large by converting auxiliary nodes into pseudo-targets so as to scale to large problems. The other is to perform summations instead of maximizations on some of the target variables in each target blanket. Our empirical evaluations show that the proposed BFBnB algorithms make exact MRE inference tractable in Bayesian networks that could not be solved previously.

IJCAI Conference 2016 Conference Paper

Solving M-Modes Using Heuristic Search

• Cong Chen
• Changhe Yuan
• Chao Chen

M-Modes for graphical models is the problem of finding top M label configurations of highest probability in their local neighborhoods. The state-of-the-art method for solving M-Modes is a dynamic programming algorithm which computes global modes by first computing local modes of each subgraph and then search through all their consistent combinations. A drawback of the algorithm is that most of its time is wasted on computing local modes that are never used in global modes. This paper introduces new algorithms that directly search the space of consistent local modes in finding the global modes, which is enabled by a novel search operator designed to search a subgraph of variables at each time. As a result, the search algorithms only need to generate and verify a small number of local modes and can hence lead to significant improvement in efficiency and scalability.

AAAI Conference 2015 Conference Paper

An Exact Algorithm for Solving Most Relevant Explanation in Bayesian Networks

• Xiaoyuan Zhu
• Changhe Yuan

Most Relevant Explanation (MRE) is a new inference task in Bayesian networks that finds the most relevant partial instantiation of target variables as an explanation for given evidence by maximizing the Generalized Bayes Factor (GBF). No exact algorithm has been developed for solving MRE previously. This paper fills the void and introduces a breadth-first branch-and-bound MRE algorithm based on a novel upper bound on GBF. The bound is calculated by decomposing the computation of the score to a set of Markov blankets of subsets of evidence variables. Our empirical evaluations show that the proposed algorithm scales up exact MRE inference significantly.

AAAI Conference 2015 Conference Paper

An Improved Lower Bound for Bayesian Network Structure Learning

• Xiannian Fan
• Changhe Yuan

Several heuristic search algorithms such as A* and breadth-first branch and bound have been developed for learning Bayesian network structures that optimize a scoring function. These algorithms rely on a lower bound function called static k-cycle conflict heuristic in guiding the search to explore the most promising search spaces. The heuristic takes as input a partition of the random variables of a data set; the importance of the partition opens up opportunities for further research. This work introduces a new partition method based on information extracted from the potentially optimal parent sets (POPS) of the variables. Empirical results show that the new partition can significantly improve the efficiency and scalability of heuristic search-based structure learning algorithms.

UAI Conference 2014 Conference Paper

Finding Optimal Bayesian Network Structures with Constraints Learned from Data

• Xiannian Fan
• Brandon M. Malone
• Changhe Yuan

Several recent algorithms for learning Bayesian network structures first calculate potentially optimal parent sets (POPS) for all variables and then use various optimization techniques to find a set of POPS, one for each variable, that constitutes an optimal network structure. This paper makes the observation that there is useful information implicit in the POPS. Specifically, the POPS of a variable constrain its parent candidates. Moreover, the parent candidates of all variables together give a directed cyclic graph, which often decomposes into a set of strongly connected components (SCCs). Each SCC corresponds to a smaller subproblem which can be solved independently of the others. Our results show that solving the constrained subproblems significantly improves the efficiency and scalability of heuristic search-based structure learning algorithms. Further, we show that by considering only the top p POPS of each variable, we quickly find provably very high quality networks for large datasets.

AAAI Conference 2014 Conference Paper

Tightening Bounds for Bayesian Network Structure Learning

• Xiannian Fan
• Changhe Yuan
• Brandon Malone

A recent breadth-first branch and bound algorithm (BF- BnB) for learning Bayesian network structures (Malone et al. 2011) uses two bounds to prune the search space for better efficiency; one is a lower bound calculated from pattern database heuristics, and the other is an upper bound obtained by a hill climbing search. Whenever the lower bound of a search path exceeds the upper bound, the path is guaranteed to lead to suboptimal solutions and is discarded immediately. This paper introduces methods for tightening the bounds. The lower bound is tightened by using more informed variable groupings when creating the pattern databases, and the upper bound is tightened using an anytime learning algorithm. Empirical results show that these bounds improve the efficiency of Bayesian network learning by two to three orders of magnitude.

UAI Conference 2013 Conference Paper

Evaluating Anytime Algorithms for Learning Optimal Bayesian Networks

• Brandon M. Malone
• Changhe Yuan

Exact algorithms for learning Bayesian networks guarantee to find provably optimal networks. However, they may fail in difficult learning tasks due to limited time or memory. In this research we adapt several anytime heuristic search-based algorithms to learn Bayesian networks. These algorithms find high-quality solutions quickly, and continually improve the incumbent solution or prove its optimality before resources are exhausted. Empirical results show that the anytime window A* algorithm usually finds higherquality, often optimal, networks more quickly than other approaches. The results also show that, surprisingly, while generating networks with few parents per variable are structurally simpler, they are harder to learn than complex generating networks with more parents per variable.

UAI Conference 2013 Conference Paper

Solving Limited-Memory Influence Diagrams Using Branch-and-Bound Search

• Arindam Khaled
• Eric A. Hansen
• Changhe Yuan

A limited-memory influence diagram (LIMID) generalizes a traditional influence diagram by relaxing the assumptions of regularity and noforgetting, allowing a wider range of decision problems to be modeled. Algorithms for solving traditional influence diagrams are not easily generalized to solve LIMIDs, however, and only recently have exact algorithms for solving LIMIDs been developed. In this paper, we introduce an exact algorithm for solving LIMIDs that is based on branch-and-bound search. Our approach is related to the approach of solving an influence diagram by converting it to an equivalent decision tree, with the difference that the LIMID is converted to a much smaller decision graph that can be searched more efficiently.

UAI Conference 2012 Conference Paper

An Improved Admissible Heuristic for Learning Optimal Bayesian Networks

• Changhe Yuan
• Brandon M. Malone

Recently two search algorithms, A* and breadthfirst branch and bound (BFBnB), were developed based on a simple admissible heuristic for learning Bayesian network structures that optimize a scoring function. The heuristic represents a relaxation of the learning problem such that each variable chooses optimal parents independently. As a result, the heuristic may contain many directed cycles and result in a loose bound. This paper introduces an improved admissible heuristic that tries to avoid directed cycles within small groups of variables. A sparse representation is also introduced to store only the unique optimal parent choices. Empirical results show that the new techniques significantly improved the efficiency and scalability of A* and BFBnB on most of datasets tested in this paper.

UAI Conference 2011 Conference Paper

Improving the Scalability of Optimal Bayesian Network Learning with External-Memory Frontier Breadth-First Branch and Bound Search

• Brandon M. Malone
• Changhe Yuan
• Eric A. Hansen
• Susan Bridges

IJCAI Conference 2011 Conference Paper

Learning Optimal Bayesian Networks Using A* Search

• Changhe Yuan
• Brandon Malone
• Xiaojian Wu

This paper formulates learning optimal Bayesian network as a shortest path finding problem. An A* search algorithm is introduced to solve the problem. With the guidance of a consistent heuristic, the algorithm learns an optimal Bayesian networkby only searching the most promising parts of the solution space. Empirical results show that the A*search algorithm significantly improves the time and space efficiency of existing methods on a set of benchmark datasets.

AAAI Conference 2011 Conference Paper

Memory-Efficient Dynamic Programming for Learning Optimal Bayesian Networks

• Brandon Malone
• Changhe Yuan
• Eric Hansen

We describe a memory-efficient implementation of a dynamic programming algorithm for learning the optimal structure of a Bayesian network from training data. The algorithm leverages the layered structure of the dynamic programming graphs representing the recursive decomposition of the problem to reduce the memory requirements of the algorithm from O(n2n ) to O(C(n, n/2)), where C(n, n/2) is the binomial coefficient. Experimental results show that the approach runs up to an order of magnitude faster and scales to datasets with more variables than previous approaches.

UAI Conference 2010 Conference Paper

Solving Multistage Influence Diagrams using Branch-and-Bound Search

• Changhe Yuan
• Xiaojian Wu
• Eric A. Hansen

A branch-and-bound approach to solving influence diagrams has been previously proposed in the literature, but appears to have never been implemented and evaluated – apparently due to the difficulties of computing effective bounds for the branch-and-bound search. In this paper, we describe how to efficiently compute effective bounds, and we develop a practical implementation of depth-first branch-and-bound search for influence diagram evaluation that outperforms existing methods for solving influence diagrams with multiple stages.

IJCAI Conference 2009 Conference Paper

• Changhe Yuan
• Eric A. Hansen

The MAP (maximum a posteriori assignment) problem in Bayesian networks is the problem of finding the most probable instantiation of a set of variables given partial evidence for the remaining variables. The state-of-the-art exact solution method is depth-first branch-and-bound search using dynamic variable ordering and a jointree upper bound proposed by Park and Darwiche [2003]. Since almost all search time is spent computing the jointree bounds, we introduce an efficient method for computing these bounds incrementally. We point out that, using a static variable ordering, it is only necessary to compute relevant upper bounds at each search step, and it is also possible to cache potentials of the jointree for efficient backtracking. Since the jointree computation typically produces bounds for joint configurations of groups of variables, our method also instantiates multiple variables at each search step, instead of a single variable, in order to reduce the number of times that upper bounds need to be computed. Experiments show that this approach leads to orders of magnitude reduction in search time.

UAI Conference 2009 Conference Paper

Most Relevant Explanation: Properties, Algorithms, and Evaluations

• Changhe Yuan
• Xiaolu Liu
• Tsai-Ching Lu
• Heejin Lim

nostic system. Given that so many variables are involved, even the best solution by MAP or MPE may have an ex- −6 Most Relevant Explanation (MRE) is a method for nding multivariate explanations for given evidence in Bayesian networks [12]. tremely low probability, say in the order of 10. It is hard to make any decision based on such hypotheses. This pa- In real-world problems, it is observed that usually only a per studies the theoretical properties of MRE few target variables are most relevant in explaining any and develops an algorithm for nding multiple given evidence. For example, there are many possible dis- top MRE solutions. Our study shows that MRE eases in a medical domain, but a patient can have at most relies on an implicit soft relevance measure in a few diseases at one time, as long as he or she does not automatically identifying the most relevant tar- delay treatments for too long. It is desirable to nd diag- get variables and pruning less relevant variables nostic hypotheses containing only those relevant diseases. from an explanation. The soft measure also en- Other diseases should be excluded from further tests or ables MRE to capture the intuitive phenomenon treatments. In a recent work, Yuan and Lu [12] propose of explaining away encoded in Bayesian net- an approach called Most Relevant Explanation (MRE) to works. Furthermore, our study shows that the generate explanations containing only the most relevant tar- solution space of MRE has a special lattice struc- get variables for given evidence in Bayesian networks. Its ture which yields interesting dominance relations main idea is to traverse a trans-dimensional space contain- among the solutions. A K-MRE algorithm based ing all the partial instantiations of the target variables and on these dominance relations is developed for nd one instantiation that maximizes a relevance measure generating a set of top solutions that are more called generalized Bayes factor [3]. representative. Our empirical results show that shown in [12] to be able to nd precise and concise ex- MRE methods are promising approaches for ex- planations. This paper provides a study of the theoretical planation in Bayesian networks. properties of MRE and offers further evidence for its valid- The approach was ity. The study shows that MRE relies on an implicit soft relevance measure that enables the automatic identi cation

AAAI Conference 2008 Conference Paper

A General Framework for Generating Multivariate Explanations in Bayesian Networks

• Changhe Yuan

Many existing explanation methods in Bayesian networks, such as Maximum a Posteriori (MAP) assignment and Most Probable Explanation (MPE), generate complete assignments for target variables. A priori, the set of target variables is often large, but only a few of them may be most relevant in explaining given evidence. Generating explanations with all the target variables is hence not always desirable. This paper addresses the problem by proposing a new framework called Most Relevant Explanation (MRE), which aims to automatically identify the most relevant target variables. We will also discuss in detail a specific instance of the framework that uses generalized Bayes factor as the relevance measure. Finally we will propose an approximate algorithm based on Reversible Jump MCMC and simulated annealing to solve MRE. Empirical results show that the new approach typically finds much more concise explanations than existing methods.

IJCAI Conference 2007 Conference Paper

• Xiaoxun Sun
• Marek J. Druzdzel
• Changhe Yuan

In this paper we propose the Dynamic Weighting A* (DWA*) search algorithm for solving MAP problems in Bayesian networks. By exploiting asymmetries in the distribution of MAP variables, the algorithm is able to greatly reduce the search space and offer excellent performance both in terms of accuracy and efficiency.

AAAI Conference 2007 Conference Paper

Generalized Evidence Pre-propagated Importance Sampling for Hybrid Bayesian Networks

• Changhe Yuan

In this paper, we first provide a new theoretical understanding of the Evidence Pre-propagated Importance Sampling algorithm (EPIS-BN) (Yuan & Druzdzel 2003; 2006b) and show that its importance function minimizes the KL-divergence between the function itself and the exact posterior probability distribution in Polytrees. We then generalize the method to deal with inference in general hybrid Bayesian networks consisting of deterministic equations and arbitrary probability distributions. Using a novel technique called soft arc reversal, the new algorithm can also handle evidential reasoning with observed deterministic variables.

UAI Conference 2004 Conference Paper

Annealed MAP

• Changhe Yuan
• Tsai-Ching Lu
• Marek J. Druzdzel

Maximum a Posteriori assignment (MAP) is the problem of finding the most probable instantiation of a set of variables given the partial evidence on the other variables in a Bayesian network. MAP has been shown to be a NP-hard problem [22], even for constrained networks, such as polytrees [18]. Hence, previous approaches often fail to yield any results for MAP problems in large complex Bayesian networks. To address this problem, we propose AnnealedMAP algorithm, a simulated annealing-based MAP algorithm. The AnnealedMAP algorithm simulates a non-homogeneous Markov chain whose invariant function is a probability density that concentrates itself on the modes of the target density. We tested this algorithm on several real Bayesian networks. The results show that, while maintaining good quality of the MAP solutions, the AnnealedMAP algorithm is also able to solve many problems that are beyond the reach of previous approaches.

UAI Conference 2003 Conference Paper

An Importance Sampling Algorithm Based on Evidence Pre-propagation

• Changhe Yuan
• Marek J. Druzdzel

Precision achieved by stochastic sampling algorithms for Bayesian networks typically deteriorates in face of extremely unlikely evidence. To address this problem, we propose the Evidence Pre-propagation Importance Sampling algorithm (EPIS-BN), an importance sampling algorithm that computes an approximate importance function by the heuristic methods: loopy belief Propagation and e-cutoff. We tested the performance of e-cutoff on three large real Bayesian networks: ANDES, CPCS, and PATHFINDER. We observed that on each of these networks the EPIS-BN algorithm gives us a considerable improvement over the current state of the art algorithm, the AIS-BN algorithm. In addition, it avoids the costly learning stage of the AIS-BN algorithm.