Forest Density Estimation

Abstract

We study graph estimation and density estimation in high dimensions, using a family of density estimators based on forest structured undirected graphical models. For density estimation, we do not assume the true distribution corresponds to a forest; rather, we form kernel density estimates of the bivariate and univariate marginals, and apply Kruskal's algorithm to estimate the optimal forest on held out data. We prove an oracle inequality on the excess risk of the resulting estimator relative to the risk of the best forest. For graph estimation, we consider the problem of estimating forests with restricted tree sizes. We prove that finding a maximum weight spanning forest with restricted tree size is NP-hard, and develop an approximation algorithm for this problem. Viewing the tree size as a complexity parameter, we then select a forest using data splitting, and prove bounds on excess risk and structure selection consistency of the procedure. Experiments with simulated data and microarray data indicate that the methods are a practical alternative to Gaussian graphical models.

Extended version of earlier paper titled "Tree density estimation"

References in corpus (2)

• Model Selection Through Sparse Maximum Likelihood Estimation
• Learning Gaussian Tree Models: Analysis of Error Exponents and Extremal Structures

Cited by in corpus (23)

• Fast community detection by SCORE
• Kernel density estimation based sampling for imbalanced class distribution
• High-dimensional structure estimation in Ising models: Local separation criterion
• A Survey on Latent Tree Models and Applications
• High-Dimensional Gaussian Graphical Model Selection: Walk Summability and Local Separation Criterion
• Transformation Autoregressive Networks
• High Dimensional Structure Learning of Ising Models on Sparse Random Graphs
• Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu
• Exponential Series Approaches for Nonparametric Graphical Models
• Predictive Learning on Hidden Tree-Structured Ising Models
• Optimal Rates for Learning Hidden Tree Structures
• Recurrent Estimation of Distributions
• Graph estimation with joint additive models
• The Cluster Graphical Lasso for improved estimation of Gaussian graphical models
• Beyond Trees: Classification with Sparse Pairwise Dependencies
• Tree density estimation
• Learning Nonparametric Forest Graphical Models with Prior Information
• Combining Smoothing Spline with Conditional Gaussian Graphical Model for Density and Graph Estimation
• Graphical Fermat's Principle and Triangle-Free Graph Estimation
• Learning by stochastic serializations
• Learning HMMs with Nonparametric Emissions via Spectral Decompositions of Continuous Matrices
• Learning Sparse Structural Changes in High-dimensional Markov Networks: A Review on Methodologies and Theories
• Forest Learning from Data and its Universal Coding