Author name cluster

Brandon Malone

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

AAAI Conference 2014 Conference Paper

Predicting the Hardness of Learning Bayesian Networks

Brandon Malone
Kustaa Kangas
Matti Jarvisalo
Mikko Koivisto
Petri Myllymaki

There are various algorithms for finding a Bayesian network structure (BNS) that is optimal with respect to a given scoring function. No single algorithm dominates the others in speed, and, given a problem instance, it is a priori unclear which algorithm will perform best and how fast it will solve the problem. Estimating the runtimes directly is extremely difficult as they are complicated functions of the instance. The main contribution of this paper is characterization of the empirical hardness of an instance for a given algorithm based on a novel collection of non-trivial, yet efficiently computable features. Our empirical results, based on the largest evaluation of stateof-the-art BNS learning algorithms to date, demonstrate that we can predict the runtimes to a reasonable degree of accuracy, and effectively select algorithms that perform well on a particular instance. Moreover, we also show how the results can be utilized in building a portfolio algorithm that combines several individual algorithms in an almost optimal manner.

PDF Details

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.

PDF Details

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.

PDF Details DOI

AAAI Conference 2011 Conference Paper

Memory-Efficient Dynamic Programming for Learning Optimal Bayesian Networks

Brandon Malone
Changhe Yuan
Eric Hansen

We describe a memory-efﬁcient 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 coefﬁcient. Experimental results show that the approach runs up to an order of magnitude faster and scales to datasets with more variables than previous approaches.

PDF Details