Tree density estimation

Abstract

We study the problem of estimating the density $f(\mathbf{x})$ of a random vector $\mathbf{X}$ in ${\mathbb{R}}^d$. For a spanning tree $T$ defined on the vertex set $\{1,\dots ,d\}$, the tree density $f_T$ is a product of bivariate conditional densities. An optimal spanning tree minimizes the Kullback-Leibler divergence between $f$ and $f_T$. From i.i.d. data we identify an optimal tree $T^{\ast }$ and efficiently construct a tree density estimate $f_n$ such that, without any regularity conditions on the density $f$, one has ${\lim }_{n\to \infty }\int |f_n(\mathbf{x})-f_{T^{\ast }}(\mathbf{x})|d\mathbf{x}=0$ a.s. For Lipschitz $f$ with bounded support, $\mathbb{E}\left\{\int |f_n(\mathbf{x})-f_{T^{\ast }}(\mathbf{x})|d\mathbf{x}\right\}=O\left(n^{-1/4}\right)$, a dimension-free rate.

References in corpus (2)

• Forest Density Estimation
• Learning Gaussian Tree Models: Analysis of Error Exponents and Extremal Structures