Combinatorial Methods in Density Estimation

by Devroye, Luc; Lugosi, Gabor

• ISBN13: 9780387951171
• ISBN10: 0387951172
• Format: Hardcover
• Copyright: 2000-12-01
• Publisher: Springer Verlag

Summary

Density estimation has evolved enormously since the days of bar plots and histograms, but researchers and users are still struggling with the problem of the selection of the bin widths. This text explores a new paradigm for the data-based or automatic selection of the free parameters of density estimates in general so that the expected error is within a given constant multiple of the best possible error. The paradigm can be used in nearly all density estimates and for most model selection problems, both parametric and nonparametric. It is the first book on this topic. The text is intended for first-year graduate students in statistics and learning theory, and offers a host of opportunities for further research and thesis topics. Each chapter corresponds roughly to one lecture, and is supplemented with many classroom exercises. A one year course in probability theory at the level of Feller's Volume 1 should be more than adequate preparation. Gabor Lugosi is Professor at Universitat Pompeu Fabra in Barcelona, and Luc Debroye is Professor at McGill University in Montreal. In 1996, the authors, together with Lászlo Györfi, published the successful text, A Probabilistic Theory of Pattern Recognition with Springer-Verlag. Both authors have made many contributions in the area of nonparametric estimation.

Table of Contents

Preface	vii
Introduction	1	(3)
References	3	(1)
Concentration Inequalities	4	(13)
Hoeffding's Inequality	4	(3)
An Inequality for the Expected Maximal Deviation	7	(1)
The Bounded Difference Inequality	7	(2)
Examples	9	(1)
Bibliographic Remarks	10	(1)
Exercises	11	(2)
References	13	(4)
Uniform Deviation Inequalities	17	(10)
The Vapnik--Chervonenkis Inequality	17	(2)
Covering Numbers and Chaining	19	(3)
Example: The Dvoretzky--Kiefer--Wolfowitz Theorem	22	(1)
Bibliographic Remarks	23	(1)
Exercises	23	(2)
References	25	(2)
Combinatorial Tools	27	(11)
Shatter Coefficients	27	(1)
Vapnik--Chervonenkis Dimension and Shatter Coefficients	28	(2)
Vapnik--Chervonenkis Dimension and Covering Numbers	30	(1)
Examples	31	(2)
Bibliographic Remarks	33	(1)
Exercises	33	(2)
References	35	(3)
Total Variation	38	(9)
Density Estimation	38	(1)
The Total Variation	39	(1)
Invariance	39	(1)
Mappings	40	(1)
Convolutions	41	(1)
Normalization	41	(1)
The Lebesgue Density Theorem	42	(1)
LeCam's Inequality	43	(1)
Bibliographic Remarks	43	(1)
Exercises	43	(3)
References	46	(1)
Choosing a Density Estimate	47	(11)
Choosing Between Two Densities	47	(2)
Examples	49	(2)
Is the Factor of Three Necessary?	51	(1)
Maximum Likelihood Does not Work	52	(1)
L2 Distances Are To Be Avoided	52	(1)
Selection from k Densities	53	(2)
Examples Continued	55	(1)
Selection from an Infinite Class	55	(1)
Bibliographic Remarks	56	(1)
Exercises	56	(1)
References	57	(1)
Skeleton Estimates	58	(12)
Kolmogorov Entropy	58	(1)
Skeleton Estimates	58	(2)
Robustness	60	(1)
Finite Mixtures	60	(1)
Monotone Densities on the Hypercube	61	(3)
How to Make Giganitic Totally Bounded Classes	64	(2)
Bibliographic Remarks	66	(1)
Exercises	66	(2)
References	68	(2)
The Minimum Distance Estimate: Examples	70	(9)
Problem Formulation	70	(1)
Series Estimates	71	(1)
Parametric Estimates: Exponential Families	72	(1)
Neural Network Estimates	73	(1)
Mixture Classes, Radial Basis Function Networks	74	(2)
Bibliographic Remarks	76	(1)
Exercises	76	(1)
References	77	(2)
The Kernel Density Estimate	79	(19)
Approximating Functions by Convolutions	79	(1)
Definition of the Kernel Estimate	80	(1)
Consistency of the Kernel Estimate	81	(1)
Concentration	82	(1)
Choosing the Bandwidth	83	(1)
Choosing the Kernel	84	(1)
Rates of Convergence	85	(1)
Uniform Rate of Convergence	86	(2)
Shrinkage, and the Combination of Density Estimates	88	(2)
Bibliographic Remarks	90	(1)
Exercises	90	(5)
References	95	(3)
Additive Estimates and Data Splitting	98	(10)
Data Splitting	98	(1)
Additive Estimates	99	(4)
Histogram Estimates	103	(2)
Bibliographic Remarks	105	(1)
Exercises	105	(2)
References	107	(1)
Bandwidth Selection for Kernel Estimates	108	(10)
The Kernel Estimate with Riemann Kernel	108	(2)
General Kernels, Kernel Complexity	110	(1)
Kernel Complexity: Univariate Examples	111	(2)
Kernel Complexity: Multivariate Kernels	113	(1)
Asymptotic Optimality	114	(1)
Bibliographic Remarks	115	(1)
Exercises	115	(1)
References	116	(2)
Multiparameter Kernel Estimates	118	(16)
Multivariate Kernel Estimates--Product Kernels	118	(3)
Multivariate Kernel Estimates--Ellipsoidal Kernels	121	(1)
Variable Kernel Estimates	122	(2)
Tree-Structured Partitions	124	(1)
Changepoints and Bump Hunting	125	(2)
Bibliographic Remarks	127	(1)
Exercises	127	(5)
References	132	(2)
Wavelet Estimates	134	(8)
Definitions	134	(1)
Smoothing	135	(1)
Thresholding	136	(2)
Soft Thresholding	138	(1)
Bibliographic Remarks	139	(1)
Exercises	139	(1)
References	140	(2)
The Transformed Kernel Estimate	142	(8)
The Transformed Kernel Estimate	142	(1)
Box--Cox Transformations	143	(3)
Piecewise Linear Transformations	146	(2)
Bibliographic Remarks	148	(1)
Exercises	148	(1)
References	149	(1)
Minimax Theory	150	(27)
Estimating a Density from One Data Point	150	(2)
The General Minimax Problem	152	(2)
Rich Classes	154	(2)
Assouad's Lemma	156	(3)
Example: The Class of Convex Densities	159	(3)
Additional Examples	162	(1)
Tuning the Parameters of Variable Kernel Estimates	163	(3)
Sufficient Statistics	166	(2)
Bibliographic Remarks	168	(1)
Exercises	169	(5)
References	174	(3)
Choosing the Kernel Order	177	(13)
Introduction	177	(2)
Standard Kernel Estimates: Riemann Kernels	179	(2)
Standard Kernel Estimates: General Kernels	181	(3)
An Infinite Family of Kernels	184	(3)
Bibliographic Remarks	187	(1)
Exercises	188	(1)
References	188	(2)
Bandwidth Choice with Superkenels	190	(9)
Superkernels	190	(2)
The Trapezoidal Kernel	192	(1)
Bandwidth Selection	193	(1)
Bibliographic Remarks	194	(1)
Exercises	194	(2)
References	196	(3)
Author Index	199	(4)
Subject Index	203