histograms

Possibly the simplest method for nonparametric density estimation after the empirical distribution.

We split the space $\mathcal{X}\subset {\mathbb{R}}^d$ into $N$ equal sized bins, $B_1,\dots ,B_N$. Note that the true density is

$$p(x)=\sum _i\mathbb{P}(x|x\in B_i)\mathbb{P}(x\in B_i).$$

We estimate $\mathbb{P}(x\in B_i)$ by simply counting the fraction of training points $X_i$ which landed in bin $B_i$. We estimate $\mathbb{P}(x|x\in B_i$) by placing a uniform distribution over the bin $B_i$, i.e., we assume $\mathbb{P}(x|x\in B_i)\approx \frac{1}{vol(B_i)}1(x\in B_i)$. Our estimator is therefore

$$\hat{p}(x)=\sum _{i=1}^N\frac{{\hat{\theta }}_j}{vol(B_i)}1(x\in B_i),$$

where ${\hat{\theta }}_j=\frac{1}{n}{\sum }_{i=1}^{n}1(X_i\in B_j)$. Note that $N$ is the number of bins and $n$ is the number of training points.

If $\mathcal{X}=[0,1{]}^d$, then $vol(B_i)=h^d$ and $N=(1/h^d)$. Obviously, the choice of $h$ is important and affects performance. The minimax $L_2$ risk (statistical decision theory) of the histogram in a 1-Hölder space is bounded by

$$L^2{h}^{2}d+O\left(\frac{1}{n{h}^d}\right),$$

so minimizing over $h$ we get a risk of $O(n^{-2/(d+2)})$. This rate of $2/(d+2)$ is much slower than parametric models (parametric density estimation), which are usually on the order of $(d/\sqrt{n})$, which is much better. In a $q$-Holder space the rate is $2q/(d+2q)$. Histograms are not minimax optimal, unlike kernel density estimation.

There are also high-probability guarantees. In particular, with probability $1-\delta$,

$$\Vert {\hat{p}}_h-p{\Vert }_{\infty }\le O\left({\left(\frac{\log n}{n}\right)}^{\frac{1}{2+d}}\right),$$

where $p$ is the true density and ${\hat{p}}_h$ is the histogram with bin size $h=O(n^{-1/(2+d)})$.

There have been efforts to choose the bin size adaptively. These estimators are sometimes called density trees. See:

• Density estimation trees by Ram and Gray
• Density estimation via adaptive sequential partitition Li, Yang, and Wong.
• Density estimation via adaptive partitioning, Liu and Wong.