Elementary Introduction to Statistical Learning Theory

SANJEEV KULKARNI, PhD, is Professor in the Department of Electrical Engineering at Princeton University, where he is also an affiliated faculty member in the Department of Operations Research and Financial Engineering and the Department of Philosophy. Dr. Kulkarni has published widely on statistical pattern recognition, nonparametric estimation, machine learning, information theory, and other areas. A Fellow of the IEEE, he was awarded Princeton University's President's Award for Distinguished Teaching in 2007.GILBERT HARMAN, PhD, is James S. McDonnell Distinguished University Professor in the Department of Philosophy at Princeton University. A Fellow of the Cognitive Science Society, he is the author of more than fifty published articles in his areas of research interest, which include ethics, statistical learning theory, psychology of reasoning, and logic.

• Preface xiii1 Introduction: Classification Learning Features and Applications 11.1 Scope 11.2 Why Machine Learning? 21.3 Some Applications 31.3.1 Image Recognition 31.3.2 Speech Recognition 31.3.3 Medical Diagnosis 41.3.4 Statistical Arbitrage 41.4 Measurements Features and Feature Vectors 41.5 The Need for Probability 51.6 Supervised Learning 51.7 Summary 61.8 Appendix: Induction 61.9 Questions 71.10 References 82 Probability 102.1 Probability of Some Basic Events 102.2 Probabilities of Compound Events 122.3 Conditional Probability 132.4 Drawing Without Replacement 142.5 A Classic Birthday Problem 152.6 Random Variables 152.7 Expected Value 162.8 Variance 172.9 Summary 192.10 Appendix: Interpretations of Probability 192.11 Questions 202.12 References 213 Probability Densities 233.1 An Example in Two Dimensions 233.2 Random Numbers in [01] 233.3 Density Functions 243.4 Probability Densities in Higher Dimensions 273.5 Joint and Conditional Densities 273.6 Expected Value and Variance 283.7 Laws of Large Numbers 293.8 Summary 303.9 Appendix: Measurability 303.10 Questions 323.11 References 324 The Pattern Recognition Problem 344.1 A Simple Example 344.2 Decision Rules 354.3 Success Criterion 374.4 The Best Classifier: Bayes Decision Rule 374.5 Continuous Features and Densities 384.6 Summary 394.7 Appendix: Uncountably Many 394.8 Questions 404.9 References 415 The Optimal Bayes Decision Rule 435.1 Bayes Theorem 435.2 Bayes Decision Rule 445.3 Optimality and Some Comments 455.4 An Example 475.5 Bayes Theorem and Decision Rule with Densities 485.6 Summary 495.7 Appendix: Defining Conditional Probability 505.8 Questions 505.9 References 536 Learning from Examples 556.1 Lack of Knowledge of Distributions 556.2 Training Data 566.3 Assumptions on the Training Data 576.4 A Brute Force Approach to Learning 596.5 Curse of Dimensionality Inductive Bias and No Free Lunch 606.6 Summary 616.7 Appendix: What Sort of Learning? 626.8 Questions 636.9 References 647 The Nearest Neighbor Rule 657.1 The Nearest Neighbor Rule 657.2 Performance of the Nearest Neighbor Rule 667.3 Intuition and Proof Sketch of Performance 677.4 Using more Neighbors 697.5 Summary 707.6 Appendix: When People use Nearest Neighbor Reasoning 707.6.1 Who Is a Bachelor? 707.6.2 Legal Reasoning 717.6.3 Moral Reasoning 717.7 Questions 727.8 References 738 Kernel Rules 748.1 Motivation 748.2 A Variation on Nearest Neighbor Rules 758.3 Kernel Rules 768.4 Universal Consistency of Kernel Rules 798.5 Potential Functions 808.6 More General Kernels 818.7 Summary 828.8 Appendix: Kernels Similarity and Features 828.9 Questions 838.10 References 849 Neural Networks: Perceptrons 869.1 Multilayer Feedforward Networks 869.2 Neural Networks for Learning and Classification 879.3 Perceptrons 899.3.1 Threshold 909.4 Learning Rule for Perceptrons 909.5 Representational Capabilities of Perceptrons 929.6 Summary 949.7 Appendix: Models of Mind 959.8 Questions 969.9 References 9710 Multilayer Networks 9910.1 Representation Capabilities of Multilayer Networks 9910.2 Learning and Sigmoidal Outputs 10110.3 Training Error and Weight Space 10410.4 Error Minimization by Gradient Descent 10510.5 Backpropagation 10610.6 Derivation of Backpropagation Equations 10910.6.1 Derivation for a Single Unit 11010.6.2 Derivation for a Network 11110.7 Summary 11310.8 Appendix: Gradient Descent and Reasoning toward Reflective Equilibrium 11310.9 Questions 11410.10 References 11511 PAC Learning 11611.1 Class of Decision Rules 11711.2 Best Rule from a Class 11811.3 Probably Approximately Correct Criterion 11911.4 PAC Learning 12011.5 Summary 12211.6 Appendix: Identifying Indiscernibles 12211.7 Questions 12311.8 References 12312 VC Dimension 12512.1 Approximation and Estimation Errors 12512.2 Shattering 12612.3 VC Dimension 12712.4 Learning Result 12812.5 Some Examples 12912.6 Application to Neural Nets 13212.7 Summary 13312.8 Appendix: VC Dimension and Popper Dimension 13312.9 Questions 13412.10 References 13513 Infinite VC Dimension 13713.1 A Hierarchy of Classes and Modified PAC Criterion 13813.2 Misfit Versus Complexity Trade-Off 13813.3 Learning Results 13913.4 Inductive Bias and Simplicity 14013.5 Summary 14113.6 Appendix: Uniform Convergence and Universal Consistency 14113.7 Questions 14213.8 References 14314 The Function Estimation Problem 14414.1 Estimation 14414.2 Success Criterion 14514.3 Best Estimator: Regression Function 14614.4 Learning in Function Estimation 14614.5 Summary 14714.6 Appendix: Regression Toward the Mean 14714.7 Questions 14814.8 References 14915 Learning Function Estimation 15015.1 Review of the Function Estimation/Regression Problem 15015.2 Nearest Neighbor Rules 15115.3 Kernel Methods 15115.4 Neural Network Learning 15215.5 Estimation with a Fixed Class of Functions 15315.6 Shattering Pseudo-Dimension and Learning 15415.7 Conclusion 15615.8 Appendix: Accuracy Precision Bias and Variance in Estimation 15615.9 Questions 15715.10 References 15816 Simplicity 16016.1 Simplicity in Science 16016.1.1 Explicit Appeals to Simplicity 16016.1.2 Is the World Simple? 16116.1.3 Mistaken Appeals to Simplicity 16116.1.4 Implicit Appeals to Simplicity 16116.2 Ordering Hypotheses 16216.2.1 Two Kinds of Simplicity Orderings 16216.3 Two Examples 16316.3.1 Curve Fitting 16316.3.2 Enumerative Induction 16416.4 Simplicity as Simplicity of Representation 16516.4.1 Fix on a Particular System of Representation? 16616.4.2 Are Fewer Parameters Simpler? 16716.5 Pragmatic Theory of Simplicity 16716.6 Simplicity and Global Indeterminacy 16816.7 Summary 16916.8 Appendix: Basic Science and Statistical Learning Theory 16916.9 Questions 17016.10 References 17017 Support Vector Machines 17217.1 Mapping the Feature Vectors 17317.2 Maximizing the Margin 17517.3 Optimization and Support Vectors 17717.4 Implementation and Connection to Kernel Methods 17917.5 Details of the Optimization Problem 18017.5.1 Rewriting Separation Conditions 18017.5.2 Equation for Margin 18117.5.3 Slack Variables for Nonseparable Examples 18117.5.4 Reformulation and Solution of Optimization 18217.6 Summary 18317.7 Appendix: Computation 18417.8 Questions 18517.9 References 18618 Boosting 18718.1 Weak Learning Rules 18718.2 Combining Classifiers 18818.3 Distribution on the Training Examples 18918.4 The Adaboost Algorithm 19018.5 Performance on Training Data 19118.6 Generalization Performance 19218.7 Summary 19418.8 Appendix: Ensemble Methods 19418.9 Questions 19518.10 References 196Bibliography 197Author Index 203Subject Index 207

“The main focus of the book is on the ideas behind basic principles of learning theory and I can strongly recommend the book to anyone who wants to comprehend these ideas.”  (Mathematical Reviews, 1 January  2013)“It also serves as an introductory reference for researchers and practitioners in the fields of engineering, computer science, philosophy, and cognitive science that would like to further their knowledge of the topic.”  (Zentralblatt MATH, 2012)