Machine learning refined : foundations, algorithms, and applications

Providing a unique approach to machine learning, this text contains fresh and intuitive, yet rigorous, descriptions of all fundamental concepts necessary to conduct research, build products, tinker, and play. By prioritizing geometric intuition, algorithmic thinking, and practical real world applications in disciplines including computer vision, natural language processing, economics, neuroscience, recommender systems, physics, and biology, this text provides readers with both a lucid understanding of foundational material as well as the practical tools needed to solve real-world problems. With in-depth Python and MATLAB/OCTAVE-based computational exercises and a complete treatment of cutting edge numerical optimization techniques, this is an essential resource for students and an ideal reference for researchers and practitioners working in machine learning, computer science, electrical engineering, signal processing, and numerical optimization. Contents 6 Preface 11 Acknowledgements 21 1 Introduction to Machine Learning 22 1.1 Introduction 22 1.2 Distinguishing Cats from Dogs: a Machine Learning Approach 22 1.3 The Basic Taxonomy of Machine Learning Problems 27 1.4 Mathematical Optimization 37 1.5 Conclusion 39 Part I Mathematical Optimization 40 2 Zero-Order Optimization Techniques 42 2.1 Introduction 42 2.2 The Zero-Order Optimality Condition 44 2.3 Global Optimization Methods 45 2.4 Local Optimization Methods 48 2.5 Random Search 52 2.6 Coordinate Search and Descent 60 2.7 Conclusion 61 2.8 Exercises 63 3 First-Order Optimization Techniques 66 3.1 Introduction 66 3.2 The First-Order Optimality Condition 66 3.3 The Geometry of First-Order Taylor Series 73 3.4 Computing Gradients Efficiently 76 3.5 Gradient Descent 77 3.6 Two Natural Weaknesses of Gradient Descent 86 3.7 Conclusion 92 3.8 Exercises 92 4 Second-Order Optimization Techniques 96 4.1 The Second-Order Optimality Condition 96 4.2 The Geometry of Second-Order Taylor Series 99 4.3 Newton’s Method 102 4.4 Two Natural Weaknesses of Newton’s Method 111 4.5 Conclusion 112 4.6 Exercises 113 Part II Linear Learning 118 5 Linear Regression 119 5.1 Introduction 119 5.2 Least Squares Linear Regression 119 5.3 Least Absolute Deviations 128 5.4 Regression Quality Metrics 131 5.5 Weighted Regression 133 5.6 Multi-Output Regression 136 5.7 Conclusion 140 5.8 Exercises 141 5.9 Endnotes 144 6 Linear Two-Class Classification 145 6.1 Introduction 145 6.2 Logistic Regression and the Cross Entropy Cost 145 6.3 Logistic Regression and the Softmax Cost 155 6.4 The Perceptron 160 6.5 Support Vector Machines 170 6.6 Which Approach Produces the Best Results? 177 6.7 The Categorical Cross Entropy Cost 178 6.8 Classification Quality Metrics 180 6.9 Weighted Two-Class Classification 187 6.10 Conclusion 190 6.11 Exercises 191 7 Linear Multi-Class Classification 194 7.1 Introduction 194 7.2 One-versus-All Multi-Class Classification 194 7.3 Multi-Class Classification and the Perceptron 204 7.4 Which Approach Produces the Best Results? 212 7.5 The Categorical Cross Entropy Cost Function 213 7.6 Classification Quality Metrics 218 7.7 Weighted Multi-Class Classification 222 7.8 Stochastic and Mini-Batch Learning 223 7.9 Conclusion 225 7.10 Exercises 225 8 Linear Unsupervised Learning 228 8.1 Introduction 228 8.2 Fixed Spanning Sets, Orthonormality, and Projections 228 8.3 The Linear Autoencoder and Principal Component Analysis 233 8.4 Recommender Systems 239 8.5 K-Means Clustering 241 8.6 General Matrix Factorization Techniques 247 8.7 Conclusion 250 8.8 Exercises 251 8.9 Endnotes 253 9 Feature Engineering and Selection 257 9.1 Introduction 257 9.2 Histogram Features 258 9.3 Feature Scaling via Standard Normalization 269 9.4 Imputing Missing Values in a Dataset 274 9.5 Feature Scaling via PCA-Sphering 275 9.6 Feature Selection via Boosting 278 9.7 Feature Selection via Regularization 284 9.8 Conclusion 289 9.9 Exercises 289 Part III Nonlinear Learning 293 10 Principles of Nonlinear Feature Engineering 295 10.1 Introduction 295 10.2 Nonlinear Regression 295 10.3 Nonlinear Multi-Output Regression 302 10.4 Nonlinear Two-Class Classification 306 10.5 Nonlinear Multi-Class Classification 310 10.6 Nonlinear Unsupervised Learning 314 10.7 Conclusion 318 10.8 Exercises 318 11 Principles of Feature Learning 324 11.1 Introduction 324 11.2 Universal Approximators 327 11.3 Universal Approximation of Real Data 343 11.4 Naive Cross-Validation 355 11.5 Efficient Cross-Validation via Boosting 360 11.6 Efficient Cross-Validation via Regularization 370 11.7 Testing Data 381 11.8 Which Universal Approximator Works Best in Practice? 385 11.9 Bagging Cross-Validated Models 386 11.10 K-Fold Cross-Validation 393 11.11 When Feature Learning Fails 398 11.12 Conclusion 399 11.13 Exercises 400 12 Kernel Methods 403 12.1 Introduction 403 12.2 Fixed-Shape Universal Approximators 403 12.3 The Kernel Trick 406 12.4 Kernels as Measures of Similarity 416 12.5 Optimization of Kernelized Models 417 12.6 Cross-Validating Kernelized Learners 418 12.7 Conclusion 419 12.8 Exercises 419 13 Fully Connected Neural Networks 423 13.1 Introduction 423 13.2 Fully Connected Neural Networks 423 13.3 Activation Functions 444 13.4 The Backpropagation Algorithm 447 13.5 Optimization of Neural Network Models 448 13.6 Batch Normalization 450 13.7 Cross-Validation via Early Stopping 458 13.8 Conclusion 460 13.9 Exercises 461 14 Tree-Based Learners 463 14.1 Introduction 463 14.2 From Stumps to Deep Trees 463 14.3 Regression Trees 466 14.4 Classification Trees 472 14.5 Gradient Boosting 478 14.6 Random Forests 482 14.7 Cross-Validation Techniques for Recursively Defined Trees 484 14.8 Conclusion 487 14.9 Exercises 487 Part IV Appendices 491 Appendix A Advanced First- and Second-Order Optimization Methods 493 A.1 Introduction 493 A.2 Momentum-Accelerated Gradient Descent 493 A.3 Normalized Gradient Descent 498 A.4 Advanced Gradient-Based Methods 505 A.5 Mini-Batch Optimization 507 A.6 Conservative Steplength Rules 510 A.7 Newton’s Method, Regularization, and Nonconvex Functions 519 A.8 Hessian-Free Methods 522 Appendix B Derivatives and Automatic Differentiation 531 B.1 Introduction 531 B.2 The Derivative 531 B.3 Derivative Rules for Elementary Functions and Operations 534 B.4 The Gradient 536 B.5 The Computation Graph 537 B.6 The Forward Mode of Automatic Differentiation 540 B.7 The Reverse Mode of Automatic Differentiation 546 B.8 Higher-Order Derivatives 549 B.9 Taylor Series 551 B.10 Using the autograd Library 556 Appendix C Linear Algebra 566 C.1 Introduction 566 C.2 Vectors and Vector Operations 566 C.3 Matrices and Matrix Operations 573 C.4 Eigenvalues and Eigenvectors 576 C.5 Vector and Matrix Norms 579 References 584 Index 589 With its intuitive yet rigorous approach to machine learning, this text provides students with the fundamental knowledge and practical tools needed to conduct research and build data-driven products. The authors prioritize geometric intuition and algorithmic thinking, and include detail on all the essential mathematical prerequisites, to offer a fresh and accessible way to learn. Practical applications are emphasized, with examples from disciplines including computer vision, natural language processing, economics, neuroscience, recommender systems, physics, and biology. Over 300 color illustrations are included and have been meticulously designed to enable an intuitive grasp of technical concepts, and over 100 in-depth coding exercises (in Python) provide a real understanding of crucial machine learning algorithms. A suite of online resources including sample code, data sets, interactive lecture slides, and a solutions manual are provided online, making this an ideal text both for graduate courses on machine learning and for individual reference and self-study. -- Provided by publisher "The second edition of this text is a complete revision of our first endeavor, with virtually every chapter of the original rewritten from the ground up and eight new chapters of material added, doubling the size of the first edition. Topics from the first edition, from expositions on gradient descent to those on One-versus- All classification and Principal Component Analysis have been reworked and polished. A swath of new topics have been added throughout the text, from derivative-free optimization to weighted supervised learning, feature selection, nonlinear feature engineering, boosting-based cross-validation, and more"-- Provided by publisher An intuitive approach to machine learning detailing the key concepts needed to build products and conduct research. Featuring color illustrations, real-world examples, practical coding exercises, and an online package including sample code, data sets, lecture slides, and solutions. It is ideal for graduate courses, reference, and self-study.