Learning Bayesian Network Structure using LP Relaxations

By Tommi S. Jaakkola, David A. Sontag, Amir Globerson, Marina Meila. 2010

236 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Graph Learning

Citations in the corpus

Gradient-Based Neural DAG Learning (2019, methodology): “There exists certain score-based approaches which uses integer linear programming (ILP) (Jaakkola et al., 2010; Cussens, 2011) which internally solve continuous linear relaxations.”
Schema Networks: Zero-shot Transfer with a Generative Causal Model of Intuitive Physics (2017, neutral): “See Jaakkola et al. (2010) for further work on applying LP relaxations to structure learning.”
DAG-GNN: DAG Structure Learning with Graph Neural Networks (2019, methodology): “Many exact and approximate algorithms for learning DAG from data have been developed, including score-based and constraint-based approaches (Spirtes et al., 2000a; Chicker-ing, 2002; Koivisto & Sood, 2004; Silander & Myllymaki, 2006; Jaakkola et al., 2010; Cussens, 2011; Yuan & Malone, 2013).”
Structure Learning in Graphical Modeling (2016, background): “More recently, authors such as Jaakkola et al. (2010), Cussens & Bartlett (2013) and Studen´y & Haws (2014) suggested integer linear programming approaches, in which the search over graph structures is formulated as a linear program over a polytope P representing DAGs.”
The Effect of Gradient Noise on the Energy Landscape of Deep Networks (2015, methodology): “In our aim to trivialize the loss function and sequentially tighten this relaxation, our work also relates to convex relaxation strategies used in machine learning, e.g., maximum-a-posteriori estimation (Jaakkola et al., 2010) and sparse principal component analysis (Wang et al., 2014).”
Machine Learning of Bayesian Networks Using Constraint Programming (2015, methodology): “Its correctness is based on the following well-known property of directed acyclic graphs that is also used in the ILP approaches [7, 8].”
Bayesian network learning with cutting planes (2011, methodology): “Thanks to Ricardo Silva for pointing me to Jaakkola et al [9].”
Efficient Structure Learning of Bayesian Networks using Constraints (2011, background): “The re-c search on this topic is active (Chickering, 2002; Teyssier and Koller, 2005; Tsamardinos et al., 2006; Silander and Myllymaki, 2006; Parviainen and Koivisto, 2009; de Campos et al., 2009; Jaakkola et al., 2010), mostly focused on complete data.”
Bayesian Networks for Variable Groups (2015, background): “Although the problem is NP-hard (Chickering, 1996), there exist plenty of exact algorithms (Jaakkola et al., 2010; Silander and Myllymäki, 2006) as well as theoretically sound heuristics (Aliferis et al., 2010; Chickering, 2002).”
On the energy landscape of deep networks (2015, methodology): “Local minima proliferate the energy landscape: there are exponentially many of them, at all energy levels.”
Learning structures of Bayesian networks for variable groups (2015, background): “Although the problem is NP-hard [4], there exist plenty of exact algorithms [7, 14, 20] as well as theoretically sound heuristics [1, 5].”
Optimization Models for Machine Learning: A Survey (2019, methodology): “Mixed-integer programming formulations of the Bayesian network structure learning have been proposed [13] and solved by using relaxations [124], cutting planes [15, 51, 77], and heuristics [100, 216].”