Error Estimation for Pattern Recognition

Ulisses M. Braga Neto is an Associate Professor in the Department of Electrical and Computer Engineering at Texas A&M University, USA. He received his PhD in Electrical and Computer Engineering from The Johns Hopkins University. Dr. Braga Neto received an NSF CAREER Award for his work on error estimation for pattern recognition with applications in genomic signal processing. He is an IEEE Senior Member.Edward R. Dougherty is a Distinguished Professor, Robert F. Kennedy ’26 Chair, and Scientific Director at the Center for Bioinformatics and Genomic Systems Engineering at Texas A&M University, USA. He is a fellow of both the IEEE and SPIE, and he has received the SPIE Presidents Award. Dr. Dougherty has authored several books including Epistemology of the Cell: A Systems Perspective on Biological Knowledge and Random Processes for Image and Signal Processing (Wiley-IEEE Press).

• Preface xiiiAcknowledgments xixList of Symbols xxi1 Classification 11.1 Classifiers 11.2 Population-Based Discriminants 31.3 Classification Rules 81.4 Sample-Based Discriminants 131.4.1 Quadratic Discriminants 141.4.2 Linear Discriminants 151.4.3 Kernel Discriminants 161.5 Histogram Rule 161.6 Other Classification Rules 201.6.1 k-Nearest-Neighbor Rules 201.6.2 Support Vector Machines 211.6.3 Neural Networks 221.6.4 Classification Trees 231.6.5 Rank-Based Rules 241.7 Feature Selection 25Exercises 282 Error Estimation 352.1 Error Estimation Rules 352.2 Performance Metrics 382.2.1 Deviation Distribution 392.2.2 Consistency 412.2.3 Conditional Expectation 412.2.4 Linear Regression 422.2.5 Confidence Intervals 422.3 Test-Set Error Estimation 432.4 Resubstitution 462.5 Cross-Validation 482.6 Bootstrap 552.7 Convex Error Estimation 572.8 Smoothed Error Estimation 612.9 Bolstered Error Estimation 632.9.1 Gaussian-Bolstered Error Estimation 672.9.2 Choosing the Amount of Bolstering 682.9.3 Calibrating the Amount of Bolstering 71Exercises 733 Performance Analysis 773.1 Empirical Deviation Distribution 773.2 Regression 793.3 Impact on Feature Selection 823.4 Multiple-Data-Set Reporting Bias 843.5 Multiple-Rule Bias 863.6 Performance Reproducibility 92Exercises 944 Error Estimation for Discrete Classification 974.1 Error Estimators 984.1.1 Resubstitution Error 984.1.2 Leave-One-Out Error 984.1.3 Cross-Validation Error 994.1.4 Bootstrap Error 994.2 Small-Sample Performance 1014.2.1 Bias 1014.2.2 Variance 1034.2.3 Deviation Variance, RMS, and Correlation 1054.2.4 Numerical Example 1064.2.5 Complete Enumeration Approach 1084.3 Large-Sample Performance 110Exercises 1145 Distribution Theory 1155.1 Mixture Sampling Versus Separate Sampling 1155.2 Sample-Based Discriminants Revisited 1195.3 True Error 1205.4 Error Estimators 1215.4.1 Resubstitution Error 1215.4.2 Leave-One-Out Error 1225.4.3 Cross-Validation Error 1225.4.4 Bootstrap Error 1245.5 Expected Error Rates 1255.5.1 True Error 1255.5.2 Resubstitution Error 1285.5.3 Leave-One-Out Error 1305.5.4 Cross-Validation Error 1325.5.5 Bootstrap Error 1335.6 Higher-Order Moments of Error Rates 1365.6.1 True Error 1365.6.2 Resubstitution Error 1375.6.3 Leave-One-Out Error 1395.7 Sampling Distribution of Error Rates 1405.7.1 Resubstitution Error 1405.7.2 Leave-One-Out Error 141Exercises 1426 Gaussian Distribution Theory: Univariate Case 1456.1 Historical Remarks 1466.2 Univariate Discriminant 1476.3 Expected Error Rates 1486.3.1 True Error 1486.3.2 Resubstitution Error 1516.3.3 Leave-One-Out Error 1526.3.4 Bootstrap Error 1526.4 Higher-Order Moments of Error Rates 1546.4.1 True Error 1546.4.2 Resubstitution Error 1576.4.3 Leave-One-Out Error 1606.4.4 Numerical Example 1656.5 Sampling Distributions of Error Rates 1666.5.1 Marginal Distribution of Resubstitution Error 1666.5.2 Marginal Distribution of Leave-One-Out Error 1696.5.3 Joint Distribution of Estimated and True Errors 174Exercises 1767 Gaussian Distribution Theory: Multivariate Case 1797.1 Multivariate Discriminants 1797.2 Small-Sample Methods 1807.2.1 Statistical Representations 1817.2.2 Computational Methods 1947.3 Large-Sample Methods 1997.3.1 Expected Error Rates 2007.3.2 Second-Order Moments of Error Rates 207Exercises 2188 Bayesian MMSE Error Estimation 2218.1 The Bayesian MMSE Error Estimator 2228.2 Sample-Conditioned MSE 2268.3 Discrete Classification 2278.4 Linear Classification of Gaussian Distributions 2388.5 Consistency 2468.6 Calibration 2538.7 Concluding Remarks 255Exercises 257A Basic Probability Review 259A.1 Sample Spaces and Events 259A.2 Definition of Probability 260A.3 Borel-Cantelli Lemmas 261A.4 Conditional Probability 262A.5 Random Variables 263A.6 Discrete Random Variables 265A.7 Expectation 266A.8 Conditional Expectation 268A.9 Variance 269A.10 Vector Random Variables 270A.11 The Multivariate Gaussian 271A.12 Convergence of Random Sequences 273A.13 Limiting Theorems 275B Vapnik–Chervonenkis Theory 277B.1 Shatter Coefficients 277B.2 The VC Dimension 278B.3 VC Theory of Classification 279B.3.1 Linear Classification Rules 279B.3.2 kNN Classification Rule 280B.3.3 Classification Trees 280B.3.4 Nonlinear SVMs 281B.3.5 Neural Networks 281B.3.6 Histogram Rules 281B.4 Vapnik–Chervonenkis Theorem 282C Double Asymptotics 285Bibliography 291Author index 301Subject index 305