Learning graphical model structure using L1-regularization paths
Published 22 July 2007
Mark Schmidt, Alexandru Niculescu-Mizil, Kevin J. Murphy
Citations178
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper shows how the decomposability of the MDL score, plus the ability to quickly compute entire regularization paths, allows us to efficiently pick the optimal regularization parameter on a per-node basis.
Abstract
Sparsity-promoting L1-regularization has recently been succesfully used to learn the structure of undirected graphical models. In this paper, we apply this technique to learn the structure of directed graphical models. Specifically, we make three contributions. First, we show how the decomposability of the MDL score, plus the ability to quickly compute entire regularization paths, allows us to efficiently pick the optimal regularization parameter on a per-node basis. Second, we show how to use L1 variable selection to select the Markov blanket, before a DAG search stage. Finally, we show how L1 variable selection can be used inside of an order search algorithm. The effectiveness of these L1-based approaches are compared to current state of the art methods on 10 datasets.
Keywords
Computer ScienceDecision Sciences
Journal of the Royal Statistical Society Series B (Statistical Methodology)Regression Shrinkage and Selection Via the Lasso
51,790 Citations1996Robert Tibshirani
A new method for estimation in linear models called the lasso, which minimizes the residual sum of squares subject to the sum of the absolute value of the coefficients being less than a constant, is proposed.
The Annals of StatisticsLeast angle regression
9,493 Citations2004Bradley Efron, Trevor Hastie +2 more
Journal of the Royal Statistical Society Series B (Statistical Methodology)Model Selection and Estimation in Regression with Grouped Variables
7,467 Citations2005Ming Yuan, Yi Lin
Machine LearningLearning Bayesian Networks: The Combination of Knowledge and Statistical Data
3,242 Citations1995David Heckerman, Dan Geiger +1 more
A methodology for assessing informative priors needed for learning Bayesian networks from a combination of prior knowledge and statistical data is developed and how to compute the relative posterior probabilities of network structures given data is shown.
Machine LearningThe max-min hill-climbing Bayesian network structure learning algorithm
1,840 Citations2006Ioannis Tsamardinos, Laura E. Brown +1 more
The first empirical results simultaneously comparing most of the major Bayesian network algorithms against each other are presented, namely the PC, Sparse Candidate, Three Phase Dependency Analysis, Optimal Reinsertion, Greedy Equivalence Search, and Greedy Search.
Lecture notes in statisticsLearning Bayesian Networks is NP-Complete
980 Citations1996David Maxwell Chickering
Journal of the Royal Statistical Society Series B (Statistical Methodology)<i>L</i>1-Regularization Path Algorithm for Generalized Linear Models
862 Citations2007Mee Young Park, Trevor Hastie
A path following algorithm for L1‐regularized generalized linear models that efficiently computes solutions along the entire regularization path by using the predictor–corrector method of convex optimization.
Machine LearningBeing Bayesian About Network Structure. A Bayesian Approach to Structure Discovery in Bayesian Networks
816 Citations2003Nir Friedman, Daphne Koller
This paper shows how to efficiently compute a sum over the exponential number of networks that are consistent with a fixed order over network variables, and uses this result as the basis for an algorithm that approximates the Bayesian posterior of a feature.
arXiv (Cornell University)Learning Bayesian Network Structure from Massive Datasets: The "Sparse Candidate" Algorithm
522 Citations1999Nir Friedman, Iftach Nachman +1 more
An algorithm that achieves faster learning by restricting the search space, which restricts the parents of each variable to belong to a small subset of candidates and is evaluated both on synthetic and real-life data.
IEEE Transactions on Pattern Analysis and Machine IntelligenceStructure learning of Bayesian networks by genetic algorithms: a performance analysis of control parameters
398 Citations1996Pedro Larrañaga, M. Poza +3 more
This work tackles the problem of the search for the best Bayesian network structure, given a database of cases, using the genetic algorithm philosophy for searching among alternative structures, by assuming an ordering between the nodes of the network structures.
EfficientL 1 regularized logistic regression
287 Citations2006Sun-In Lee, Honglak Lee +2 more
Theoretical results show that the proposed efficient algorithm for L1 regularized logistic regression is guaranteed to converge to the global optimum, and experiments show that it significantly outperforms standard algorithms for solving convex optimization problems.
The MIT Press eBooksEfficient Structure Learning of Markov Networks using L1-Regularization
210 Citations2007Su-In Lee, Varun Ganapathi +1 more
This paper provides a computationally efficient method for learning Markov network structure from data based on the use of L1 regularization on the weights of the log-linear model, which achieves considerably higher generalization performance than the more standard L2-based method (a Gaussian parameter prior or pure maximum-likelihood learning).
arXiv (Cornell University)Ordering-Based Search: A Simple and Effective Algorithm for Learning\n Bayesian Networks
182 Citations2012Marc Teyssier, Daphne Koller
It is shown that ordering-based search outperforms the standard baseline, and is competitive with recent algorithms that are much harder to implement.
Convex optimization techniques for fitting sparse Gaussian graphical models
150 Citations2006Onureena Banerjee, Laurent El Ghaoui +2 more
This work considers the problem of fitting a large-scale covariance matrix to multivariate Gaussian data in such a way that the inverse is sparse, thus providing model selection, and presents two new algorithms aimed at solving problems with a thousand nodes.
Uncertainty in Artificial IntelligenceDependency Networks for Density Estimation, Collaborative Filtering, and Data Visualization
28 Citations2000David Heckerman, Max Chickering +3 more
This work describes a graphical model for probabilistic relationships – an alternative to the Bayesian network – called a dependency network and identifies several basic properties of this representation and describes a computationally efficient procedure for learning the graph and probability components from data.
National Conference on Artificial IntelligenceUsing modified Lasso regression to learn large undirected graphs in a probabilistic framework
13 Citations2005Fan Li, Yiming Yang
This paper uses graphical Gaussian model (GGM) as the underlying model and proposes a novel ARD style Wishart prior for the precision matrix of the GGM to learn genetic regulatory networks from genome-wide expression microarray data and protein-binding location analysis data.