Max Chickering

UAI Conference 2020 Conference Paper

Statistically Efficient Greedy Equivalence Search

• Max Chickering

We establish the theoretical foundation for statistically efficient variants of the Greedy Equivalence Search algorithm. If each node in the generative structure has at most $k$ parents, we show that in the limit of large data, we can recover that structure using greedy search with operator scores that condition on at most $k$ variables. We present simple synthetic experiments that compare a backward-only variantof the new algorithm to GES using finite data, showing increasing benefit of the new algorithm as the complexity of the generative model increases.

UAI Conference 2015 Conference Paper

Selective Greedy Equivalence Search: Finding Optimal Bayesian Networks Using a Polynomial Number of Score Evaluations

• Max Chickering
• Christopher Meek

We introduce Selective Greedy Equivalence Search (SGES), a restricted version of Greedy Equivalence Search (GES). SGES retains the asymptotic correctness of GES but, unlike GES, has polynomial performance guarantees. In particular, we show that when data are sampled independently from a distribution that is perfect with respect to a DAG G defined over the observable variables then, in the limit of large data, SGES will identify the equivalence class of G after a number of score evaluations that is (1) polynomial in the number of nodes and (2) exponential in various complexity measures including maximum-number-of-parents, maximum-cliquesize, and a new measure called v-width that is at least as small as—and potentially much smaller than—the other two. More generally, we show that for any hereditary and equivalenceinvariant property Π known to hold in G, we retain the large-sample optimality guarantees of GES even if we ignore any GES deletion operator during the backward phase that results in a state for which Π does not hold in the commondescendants subgraph.

UAI Conference 2004 Conference Paper

ARMA Time-Series Modeling with Graphical Models

• Bo Thiesson
• Max Chickering
• David Heckerman
• Christopher Meek

UAI Conference 2003 Conference Paper

Large-Sample Learning of Bayesian Networks is NP-Hard

• Max Chickering
• Christopher Meek
• David Heckerman

In this paper, we provide new complexity results for algorithms that learn discrete-variable Bayesian networks from data. Our results apply whenever the learning algorithm uses a scoring criterion that favors the simplest model able to represent the generative distribution exactly. Our results therefore hold whenever the learning algorithm uses a consistent scoring criterion and is applied to a sufficiently large dataset. We show that identifying high-scoring structures is hard, even when we are given an independence oracle, an inference oracle, and/or an information oracle. Our negative results also apply to the learning of discrete-variable Bayesian networks in which each node has at most k parents, for all k > 3.

UAI Conference 2003 Conference Paper

Practically Perfect

• Christopher Meek
• Max Chickering

UAI Conference 2002 Conference Paper

Finding Optimal Bayesian Networks

• Max Chickering
• Christopher Meek

UAI Conference 2001 Conference Paper

A Bayesian Approach to Tackling Hard Computational Problems

• Eric Horvitz
• Yongshao Ruan
• Carla P. Gomes
• Henry A. Kautz
• Bart Selman
• Max Chickering

We are developing a general framework for using learned Bayesian models for decision-theoretic control of search and reasoningalgorithms. We illustrate the approach on the specific task of controlling both general and domain-specific solvers on a hard class of structured constraint satisfaction problems. A successful strategyfor reducing the high (and even infinite) variance in running time typically exhibited by backtracking search algorithms is to cut off and restart the search if a solution is not found within a certainamount of time. Previous work on restart strategies have employed fixed cut off values. We show how to create a dynamic cut off strategy by learning a Bayesian model that predicts the ultimate length of a trial based on observing the early behavior of the search algorithm. Furthermore, we describe the general conditions under which a dynamic restart strategy can outperform the theoretically optimal fixed strategy.

UAI Conference 2001 Conference Paper

Using Temporal Data for Making Recommendations

• Andrew Zimdars
• Max Chickering
• Christopher Meek

UAI Conference 2000 Conference Paper

A Decision Theoretic Approach to Targeted Advertising

• Max Chickering
• David Heckerman

A simple advertising strategy that can be used to help increase sales of a product is to mail out special offers to selected potential customers. Because there is a cost associated with sending each offer, the optimal mailing strategy depends on both the benefit obtained from a purchase and how the offer affects the buying behavior of the customers. In this paper, we describe two methods for partitioning the potential customers into groups, and show how to perform a simple cost-benefit analysis to decide which, if any, of the groups should be targeted. In particular, we consider two decision-tree learning algorithms. The first is an ``off the shelf'' algorithm used to model the probability that groups of customers will buy the product. The second is a new algorithm that is similar to the first, except that for each group, it explicitly models the probability of purchase under the two mailing scenarios: (1) the mail is sent to members of that group and (2) the mail is not sent to members of that group. Using data from a real-world advertising experiment, we compare the algorithms to each other and to a naive mail-to-all strategy.

UAI Conference 2000 Conference Paper

Dependency Networks for Collaborative Filtering and Data Visualization

• David Heckerman
• Max Chickering
• Christopher Meek
• Robert Rounthwaite
• Carl Myers Kadie

UAI Conference 1999 Conference Paper

Fast Learning from Sparse Data

• Max Chickering
• David Heckerman

We describe two techniques that significantly improve the running time of several standard machine-learning algorithms when data is sparse. The first technique is an algorithm that effeciently extracts one-way and two-way counts--either real or expected-- from discrete data. Extracting such counts is a fundamental step in learning algorithms for constructing a variety of models including decision trees, decision graphs, Bayesian networks, and naive-Bayes clustering models. The second technique is an algorithm that efficiently performs the E-step of the EM algorithm (i.e. inference) when applied to a naive-Bayes clustering model. Using real-world data sets, we demonstrate a dramatic decrease in running time for algorithms that incorporate these techniques.

UAI Conference 1998 Conference Paper

Learning Mixtures of DAG Models

• Bo Thiesson
• Christopher Meek
• Max Chickering
• David Heckerman

UAI Conference 1997 Conference Paper

A Bayesian Approach to Learning Bayesian Networks with Local Structure

• Max Chickering
• David Heckerman
• Christopher Meek

UAI Conference 1996 Conference Paper

Efficient Approximations for the Marginal Likelihood of Incomplete Data Given a Bayesian Network

• Max Chickering
• David Heckerman

We discuss Bayesian methods for learning Bayesian networks when data sets are incomplete. In particular, we examine asymptotic approximations for the marginal likelihood of incomplete data given a Bayesian network. We consider the Laplace approximation and the less accurate but more efficient BIC/MDL approximation. We also consider approximations proposed by Draper (1993) and Cheeseman and Stutz (1995). These approximations are as efficient as BIC/MDL, but their accuracy has not been studied in any depth. We compare the accuracy of these approximations under the assumption that the Laplace approximation is the most accurate. In experiments using synthetic data generated from discrete naive-Bayes models having a hidden root node, we find that the CS measure is the most accurate.

UAI Conference 1996 Conference Paper

Learning Equivalence Classes of Bayesian Network Structures

• Max Chickering

UAI Conference 1995 Conference Paper

A Transformational Characterization of Equivalent Bayesian Network Structures

• Max Chickering

We present a simple characterization of equivalent Bayesian network structures based on local transformations. The significance of the characterization is twofold. First, we are able to easily prove several new invariant properties of theoretical interest for equivalent structures. Second, we use the characterization to derive an efficient algorithm that identifies all of the compelled edges in a structure. Compelled edge identification is of particular importance for learning Bayesian network structures from data because these edges indicate causal relationships when certain assumptions hold.

UAI Conference 1994 Conference Paper

Learning Bayesian Networks: The Combination of Knowledge and Statistical Data

• David Heckerman
• Dan Geiger
• Max Chickering

We describe algorithms for learning Bayesian networks from a combination of user knowledge and statistical data. The algorithms have two components: a scoring metric and a search procedure. The scoring metric takes a network structure, statistical data, and a user's prior knowledge, and returns a score proportional to the posterior probability of the network structure given the data. The search procedure generates networks for evaluation by the scoring metric. Our contributions are threefold. First, we identify two important properties of metrics, which we call event equivalence and parameter modularity. These properties have been mostly ignored, but when combined, greatly simplify the encoding of a user's prior knowledge. In particular, a user can express her knowledge-for the most part-as a single prior Bayesian network for the domain. Second, we describe local search and annealing algorithms to be used in conjunction with scoring metrics. In the special case where each node has at most one parent, we show that heuristic search can be replaced with a polynomial algorithm to identify the networks with the highest score. Third, we describe a methodology for evaluating Bayesian-network learning algorithms. We apply this approach to a comparison of metrics and search procedures.