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)$.