Combinatorial Methods in Density Estimation

A random variable X on R ^d has a density f if, for all Borel sets A of R ^d , ∫ _A f(x)dx = P{X ∈ A}. It thus serves as a tool for computing probabilities of sets. As it is a function that reveals the local concentration of probability mass, it may be used to visualize distributions of random variables. The statistician’s problem, then, is to estimate f from an i.i.d. sample X ₁,…,X _n drawn from f. A density estimate is simply a mapping f _n : R ^d × (R ^d ) ⁿ → R ^d (we write f _n (x; X ₁,…,X _n ) or f _n (x)). It is the global closeness of f _n to f that interests us. The choice of a density estimate is governed by a number of factors, like consistency, smoothness, ease of computation, interpretability, flexibility, robustness, versatility, and optimality for certain criteria. The early work in the field approached the problem largely as a functional estimation problem: f was treated as any function, and tools from function approximation theory came to the rescue in the analysis of the performance of density estimates—Taylor series expansions played a key role, for example. The view we take in nonparametric density estimation is that f is largely unknown and that no assumptions can be made about its properties. Methods or properties that are valid for all densities are said to be universal. It is quite surprising that there are density estimates that can approximate any density f asymptotically in an appropriate sense. Simple histogram and kernel estimates have this property for example. But when people started studying rates of convergence, or error bounds for particular n, they invariably had to place conditions on the smoothness or boundedness of f. This was frustrating , because it was nearly impossible to test whether these assumptions were satisfied. Just try cooking up a test that decides whether the essestial supremum of f is bounded, for example!

Most of the methodology discussed in this book builds on elements of empirical process theory, certain concentration-of-measure inequalities, and simple combinatorial calculations. The aim of this and the following two chapters is to equip the reader with these simple tools. We keep the material at an elementary level, with additional information added in the exercises.

This chapter is devoted to some basic inequalities that bound the maximal difference between probabilities and relative frequencies over a class of events. The bounds will be key tools in our study of density estimates. Let X ₁,…,X _n be i.i.d. random variables taking values in R ^d with common distribution

Consider a class A of subsets of R ^d , and let x ₁,…,x _n ∈ R ^d be arbitrary points. Recall from the previous chapter that properties of the finite set A(x ₁ ⁿ ) ⊂ {0, 1} ⁿ defined by play an essential role in bounding uniform deviations of the empirical measure.

A random variable X has a density f on R ^d when for all Borel sets A ⊆ R ^d , P{X ∈ A} = ∫ _A f(x)dx. In other words, if A is a small ball about x, its probability is about f(x) times the volume of A. The purpose of density estimation is to estimate an unknown density f from an i.i.d. sample X ₁,…,X _n drawn from f. There are other questions one may ask, like the estimation of a functional such as ∫ f ^α (x)dx or ∫ ψ(f(x), x)dx for general ψ. These are not dealt with in the text and may indeed require a very different treatment. We are concerned with the density itself as a means of computing probabilities of all sets. A density estimate f _n (x) = f _n (x;X ₁,…,X _n ) is thus a mapping from (R ^d ) ⁿ⁺¹ to R. Its quality is measured by how well it performs the task at hand, estimating probabilities.

Consider the following simple situation: g _n and f _n are two density estimates, and we must select the best one, that is, arg min(∫ |f _n − f|, ∫ |g _n − f|). More precisely, given the sample X ₁, …, X _n distributed according to density f, we are asked to construct a density estimate φ _n such that This simple problem turns out to be surprisingly difficult, even if the estimates f _n and g _n are fixed densities, not depending on the data.

In this short chapter, we show how to pick a density estimate from a pre-specified class of densities, F. In particular, the classes we are interested in are totally bounded, that is, for every ε > 0, there exists a finite number N _ε of densities in F such that the L ₁ balls of radius ε centered at these densities cover F, that is, if these chosen densities are G _ε = {g1,…,gN _ε }, then where B _g,r = {f : ∫ |f − g| ≤ r}. The smallest such N _ε is called the complexity (or covering number) of F (and thus is a function of ε), and log₂ N _ε is the Kolmogorov entropy of F. G _ε is called a skeleton of F.

Given a class F of densities, we are to construct a density estimate such that it performs almost as well as the best density in the class. We saw that the skeleton estimate defined in the previous chapter always works when F is totally bounded. In this chapter we analyze the minimum distance estimate described in Section 6.8. Assume that the densities f _θ ∈ F are indexed by a parameter θ ∈ Θ.

In this chapter, we get our first taste of real analysis, starting with some results on the approximations of functions in L ₁. The literature on this is vast, and a lot of it is ancient. The problem is that f cannot be approximated in L ₁ by μ _n , the empirical measure, as the total variation distance between any density f and any atomic measure (like μ _n ) is 1. Thus, the approximation itself must have a density. The kernel estimate provides this: it smooths the empirical measure μ _n . This section has no combinatorial contributions, but develops just enough of the function approximation material to understand the remaining chapters.

Assume that we are given a class of density estimates parametrized by θ ∈ Θ, such that f _{n, θ} denotes the density estimate with parameter θ. Our goal is to construct a density estimate f _n whose L ₁ error is (almost) as small as that of the best estimate among the f _n,θ , θ ∈ Θ. Applying the minimum distance estimate of Chapter 5 directly to this class is often problematic because of the dependence of each estimate in the class and the empirical measure μ _n .

This chapter is about the choice of the bandwidth (or smoothing factor) h ∈ (0, ∞) of the standard kernel estimate

In this chapter we illustrate how the minimum distance estimate described in Chapter 10 may be used to select various parameters simultaneously in an almost optimal manner. The examples are all simple multiparameter versions of the kernel estimate. Once again, the methods applied here are fully combinatorial, as the only thing we need in each case is a suitable upper bound for the shatter coefficient appearing in Theorem 10.3.

In univariate curve estimation, wavelet systems have become popular. A wavelet system is a countable family of orthonormal functions (in L ₂(R)) {φ _k , ψ _jk : j ≥ 0, k = 0, ± 1, ±2 …} with the following properties:

The transformed kernel estimate on the real line was introduced in an attempt to reduce the L ₁ error in a relatively cheap manner. The data are first transformed T : R → R by a strictly monotonically increasing almost everywhere differentiable transformation T: Y ₁ = T(X ₁),…,Y _n = T(X _n ). The density of Y ₁ is where T ⁻¹ denotes the inverse of T.

Let us use an extreme example to start off this chapter. Assume that we are shown one data point X drawn from an unknown density f that belongs to a class F, which is given to us. Our estimate of f is g(x, X), where g should be such that it is best possible. As we do not know f, we naturally assume that after g is picked, our adversary picks the worst f ∊ F.

Using the notation K _h (·) to denote (1/h)K(·/h), let the univariate kernel estimate with bandwidth h > 0 and kernel K be

In the previous chapter, we looked at the saturation classes for kernels with many vanishing moments. The best rate Φ(n, K) for these kernels was n ^−s/(2s+1) with s an even positive integer. So, in theory, if we could find a kernel all of whose moments are vanishing, then we could hope for a rate Φ(n, K) that is better than n ^−1/2+ε for all ε > 0. So, is it possible to find such kernels? Can we simultaneously insure ∫ K = 1, yet ∫ x ⁱ K(x) dx = 0 for all i > 0? The answer is yes. In fact, there are many such kernels, and each of them has of course its own best rate Φ(n, K). This could lead to the introduction of yet another hierarchy of saturation classes with best rates, for example, (log n( ^s / √n. However, as these saturation classes are surely becoming rather small—all densities in them must be infinitely many times continuously differentiate—this is an almost pointless exercise. Instead, we consider the ultimate kernels, those for which Φ(n, K) = O(1/√n). Clearly, O(1/√n) is the best possible rate, as Lemma 1 shows.