Structure Learning of Probabilistic Graphical Models: A Comprehensive Survey (2011-11-29T00:00:00.000000Z)

TL;DR

This paper presents a comprehensive survey of the existing structure learning algorithms for graphical models, and provides additional insights into the properties of the model, including the conditional independence properties.

Abstract

Probabilistic graphical models combine the graph theory and probability theory to give a multivariate statistical modeling. They provide a unified description of uncertainty using probability and complexity using the graphical model. Especially, graphical models provide the following several useful properties: - Graphical models provide a simple and intuitive interpretation of the structures of probabilistic models. On the other hand, they can be used to design and motivate new models. - Graphical models provide additional insights into the properties of the model, including the conditional independence properties. - Complex computations which are required to perform inference and learning in sophisticated models can be expressed in terms of graphical manipulations, in which the underlying mathematical expressions are carried along implicitly. The graphical models have been applied to a large number of fields, including bioinformatics, social science, control theory, image processing, marketing analysis, among others. However, structure learning for graphical models remains an open challenge, since one must cope with a combinatorial search over the space of all possible structures. In this paper, we present a comprehensive survey of the existing structure learning algorithms.

TL;DR

Abstract

Authors

References122 items

Computational system biology

Learning with Kernels

Learning Graphical Model Structure Using L1-Regularization Paths

Incremental Bayesian networks for structure prediction

Efficient Structure Learning of Markov Networks using L1-Regularization

High-Dimensional Graphical Model Selection Using ℓ1-Regularized Logistic Regression

The max-min hill-climbing Bayesian network structure learning algorithm

Pattern Recognition and Machine Learning

Convex Structure Learning for Bayesian Networks: Polynomial Feature Selection and Approximate Ordering

Collaborative prediction using ensembles of Maximum Margin Matrix Factorizations

Convex optimization techniques for fitting sparse Gaussian graphical models

High-dimensional graphs and variable selection with the Lasso

Document clustering using nonnegative matrix factorization

Elements of Information Theory

Fast maximum margin matrix factorization for collaborative prediction

Ordering-Based Search: A Simple and Effective Algorithm for Learning Bayesian Networks

Smooth minimization of non-smooth functions

Reverse engineering of regulatory networks in human B cells

An empirical Bayes approach to inferring large-scale gene association networks

Sparse factorizations of gene expression data guided by binding data.

Exact Bayesian Structure Discovery in Bayesian Networks

Maximum-Margin Matrix Factorization

Sparse graphical Gaussian modeling of the isoprenoid gene network in Arabidopsis thaliana

Non-negative Matrix Factorization with Sparseness Constraints

Feature selection, L1 vs. L2 regularization, and rotational invariance

Performance Guarantees for Regularized Maximum Entropy Density Estimation

Evidence for dynamically organized modularity in the yeast protein–protein interaction network

Large-scale reverse engineering by the Lasso

Network component analysis: Reconstruction of regulatory signals in biological systems

Topology of gene expression networks as revealed by data mining and modeling

Optimal Reinsertion: A New Search Operator for Accelerated and More Accurate Bayesian Network Structure Learning

Causation, Prediction, and Search

Inferring Genetic Networks and Identifying Compound Mode of Action via Expression Profiling

Module networks: identifying regulatory modules and their condition-specific regulators from gene expression data

Learning Bayesian Network Model Structure from Data

Grafting: Fast, Incremental Feature Selection by Gradient Descent in Function Space

A duplication growth model of gene expression networks

Hierarchical Organization of Modularity in Metabolic Networks

Large-Sample Learning of Bayesian Networks is NP-Hard

Reverse engineering gene networks using singular value decomposition and robust regression

Inference of a genetic network by a combined approach of cluster analysis and graphical Gaussian modeling

Bayesian learning of sparse classifiers

Learning with kernels

Statistical estimation of cluster boundaries in gene expression profile data

Complex Probabilistic Modeling with Recursive Relational Bayesian Networks

Maximum likelihood bounded tree-width Markov networks

Using Graphical Models and Genomic Expression Data to Statistically Validate Models of Genetic Regulatory Networks

The large-scale organization of metabolic networks

Asymptotics for lasso-type estimators

Singular value decomposition for genome-wide expression data processing and modeling.

Model Selection Criteria for Learning Belief Nets: An Empirical Comparison

Distinct types of diffuse large B-cell lymphoma identified by gene expression profiling

Ridge Regression: Biased Estimation for Nonorthogonal Problems

Mutual information relevance networks: functional genomic clustering using pairwise entropy measurements.

Bayesian Network Induction via Local Neighborhoods

Learning Probabilistic Relational Models

Learning Bayesian Network Structure from Massive Datasets: The "Sparse Candidate" Algorithm

Parameter Priors for Directed Acyclic Graphical Models and the Characteriration of Several Probability Distributions

Systematic determination of genetic network architecture

Interpreting patterns of gene expression with self-organizing maps: methods and application to hematopoietic differentiation.

A Tutorial on Learning with Bayesian Networks

Cluster analysis and display of genome-wide expression patterns.

Linear Modeling of mRNA Expression Levels During CNS Development and Injury

Identification of Genetic Networks from a Small Number of Gene Expression Patterns Under the Boolean Network Model

Comprehensive identification of cell cycle-regulated genes of the yeast Saccharomyces cerevisiae by microarray hybridization.

Stochastic kinetic analysis of developmental pathway bifurcation in phage lambda-infected Escherichia coli cells.

Cached Sufficient Statistics for Efficient Machine Learning with Large Datasets

Relational Bayesian Networks

Structure Learning of Bayesian Networks by Genetic Algorithms: A Performance Analysis of Control Parameters

Learning Limited Dependence Bayesian Classifiers

Learning Bayesian Networks with Local Structure

Context-Specific Independence in Bayesian Networks

Learning Equivalence Classes of Bayesian Network Structures

On the Sample Complexity of Learning Bayesian Networks

Inducing Features of Random Fields

Regularization Theory and Neural Networks Architectures