Machine Learning Algorithms in Depth (Vadim Smolyakov) (Z-Library)

📄 File Format: PDF

💾 File Size: 25.3 MB

📖 Read Online ⬇️ Download

Registered users can read the full content for free

Register as a Gaohf Library member to read the complete e-book online for free and enjoy a better reading experience.

📄 Page 1

M A N N I N G Vadim Smolyakov

📄 Page 2

Machine Learning Algorithms in Depth

📄 Page 3

(This page has no text content)

📄 Page 4

Machine Learning Algorithms in Depth VADIM SMOLYAKOV MANN I NG SHELTER ISLAND

📄 Page 5

For online information and ordering of this and other Manning books, please visit www.manning.com. The publisher offers discounts on this book when ordered in quantity. For more information, please contact Special Sales Department Manning Publications Co. 20 Baldwin Road PO Box 761 Shelter Island, NY 11964 Email: orders@manning.com ©2024 by Manning Publications Co. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by means electronic, mechanical, photocopying, or otherwise, without prior written permission of the publisher. Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in the book, and Manning Publications was aware of a trademark claim, the designations have been printed in initial caps or all caps. Recognizing the importance of preserving what has been written, it is Manning’s policy to have the books we publish printed on acid-free paper, and we exert our best efforts to that end. Recognizing also our responsibility to conserve the resources of our planet, Manning books are printed on paper that is at least 15 percent recycled and processed without the use of elemental chlorine. The author and publisher have made every effort to ensure that the information in this book was correct at press time. The author and publisher do not assume and hereby disclaim any liability to any party for any loss, damage, or disruption caused by errors or omissions, whether such errors or omissions result from negligence, accident, or any other cause, or from any usage of the information herein. Manning Publications Co. Development editor: Elesha Hyde 20 Baldwin Road Technical editor: Junpeng Lao PO Box 761 Review editor: Aleksandar Dragosavljević Shelter Island, NY 11964 Production editor: Kathy Rossland Copy editor: Christian Berk Proofreader: Jason Everett Technical proofreader: Bin Hu Typesetter: Gordan Salinovic Cover designer: Marija Tudor ISBN 9781633439214 Printed in the United States of America

📄 Page 6

To my parents, Sergey and Valeriya, for their constant love and support. To my partner, Kelly, I love you infinitely.

📄 Page 7

vi brief contents PART 1 INTRODUCING ML ALGORITHMS......................................... 1 1 ■ Machine learning algorithms 3 2 ■ Markov chain Monte Carlo 14 3 ■ Variational inference 43 4 ■ Software implementation 58 PART 2 SUPERVISED LEARNING.................................................... 71 5 ■ Classification algorithms 73 6 ■ Regression algorithms 106 7 ■ Selected supervised learning algorithms 123 PART 3 UNSUPERVISED LEARNING...............................................163 8 ■ Fundamental unsupervised learning algorithms 165 9 ■ Selected unsupervised learning algorithms 186 PART 4 DEEP LEARNING............................................................217 10 ■ Fundamental deep learning algorithms 219 11 ■ Advanced deep learning algorithms 250

📄 Page 8

vii contents preface xii acknowledgments xiii about this book xiv about the author xviii about the cover illustration xix PART 1 INTRODUCING ML ALGORITHMS................................1 1 Machine learning algorithms 3 1.1 Types of ML algorithms 4 1.2 Why learn algorithms from scratch? 7 1.3 Mathematical background 7 1.4 Bayesian inference and deep learning 8 Two main camps of Bayesian inference: MCMC and VI 9 Modern deep learning algorithms 11 1.5 Implementing algorithms 12 Data structures 12 ■ Problem-solving paradigms 12

📄 Page 9

CONTENTSviii 2 Markov chain Monte Carlo 14 2.1 Introduction to Markov chain Monte Carlo 15 Posterior distribution of coin flips 16 ■ Markov chain for page rank 18 2.2 Estimating pi 19 2.3 Binomial tree model 21 2.4 Self-avoiding random walk 24 2.5 Gibbs sampling 28 2.6 Metropolis-Hastings sampling 32 2.7 Importance sampling 35 2.8 Exercises 41 3 Variational inference 43 3.1 KL variational inference 44 3.2 Mean-field approximation 47 3.3 Image denoising in an Ising model 49 3.4 MI maximization 56 3.5 Exercises 57 4 Software implementation 58 4.1 Data structures 58 Linear 59 ■ Nonlinear 60 ■ Probabilistic 61 4.2 Problem-solving paradigms 61 Complete search 61 ■ Greedy 62 ■ Divide and conquer 64 Dynamic programming 65 4.3 ML research: Sampling methods and variational inference 67 4.4 Exercises 68 PART 2 SUPERVISED LEARNING...........................................71 5 Classification algorithms 73 5.1 Introduction to classification 74 5.2 Perceptron 74 5.3 Support vector machine 80

📄 Page 10

CONTENTS ix 5.4 Logistic regression 86 5.5 Naive Bayes 93 5.6 Decision tree (CART) 98 5.7 Exercises 104 6 Regression algorithms 106 6.1 Introduction to regression 107 6.2 Bayesian linear regression 107 6.3 Hierarchical Bayesian regression 111 6.4 KNN regression 115 6.5 Gaussian process regression 117 6.6 Exercises 121 7 Selected supervised learning algorithms 123 7.1 Markov models 124 Page rank algorithm 125 ■ Hidden Markov models 128 7.2 Imbalanced learning 134 Undersampling strategies 134 ■ Oversampling strategies 136 7.3 Active learning 138 Query strategies 139 7.4 Model selection: Hyperparameter tuning 147 Bayesian optimization 148 7.5 Ensemble methods 150 Bagging 151 ■ Boosting 154 ■ Stacking 157 7.6 ML research: Supervised learning algorithms 160 7.7 Exercises 161 PART 3 UNSUPERVISED LEARNING.....................................163 8 Fundamental unsupervised learning algorithms 165 8.1 Dirichlet process K-means 166 8.2 Gaussian mixture models 171 Expectation maximization (EM) algorithm 171

📄 Page 11

CONTENTSx 8.3 Dimensionality reduction 179 Principal component analysis 179 ■ t-SNE manifold learning on images 182 8.4 Exercises 184 9 Selected unsupervised learning algorithms 186 9.1 Latent Dirichlet allocation 187 Variational Bayes 188 9.2 Density estimators 195 Kernel density estimator 195 ■ Tangent portfolio optimization 198 9.3 Structure learning 201 Chow-Liu algorithm 201 ■ Inverse covariance estimation 202 9.4 Simulated annealing 206 9.5 Genetic algorithm 210 9.6 ML research: Unsupervised learning 213 9.7 Exercises 214 PART 4 DEEP LEARNING ..................................................217 10 Fundamental deep learning algorithms 219 10.1 Multilayer perceptron 220 10.2 Convolutional neural nets 225 LeNet on MNIST 226 ■ ResNet image search 229 10.3 Recurrent neural nets 232 LSTM sequence classification 233 ■ Multi-input model 237 10.4 Neural network optimizers 242 10.5 Exercises 248 11 Advanced deep learning algorithms 250 11.1 Autoencoders 251 VAE anomaly detection in time series 253 11.2 Amortized variational inference 259 Mixture density networks 259 11.3 Attention and transformers 265

📄 Page 12

CONTENTS xi 11.4 Graph neural networks 273 11.5 ML research: Deep learning 279 11.6 Exercises 281 appendix A Further reading and resources 283 appendix B Answers to exercises 286 index 299

📄 Page 13

xii preface Welcome to Machine Learning Algorithms in Depth! The idea of writing this book came to me during my graduate school years. At the time, I was switching majors from wireless communications to machine learning and found that one constant during this transi- tion was my fascination with algorithms. I wanted to study this subject in depth and really understand how to derive, implement, and analyze algorithms from the first principles. I was fortunate to have found a research home in the Sensing, Learning, and Inference group at MIT CSAIL, where I was exposed to a wide variety of machine learning appli- cations centered on Bayesian inference. At the same time, the field of deep learning was rapidly evolving, and I found myself training and experimenting with a variety of neural network models for computer vision and natural language processing. I’ve always been fascinated with the complementary strengths of probabilistic graphical models and deep learning models, and pondered ways in which the two can be combined. Throughout my graduate school journey, I was exposed to a variety of applications and developed a library of algorithms I implemented from scratch. I read many machine learning texts and was a technical editor for others, which lead me to finding a gap in the existing literature: a from-scratch approach to machine learning algorithms. This was my “aha!” moment, and it fueled my dream of writing a book. Machine Learning Algorithms in Depth takes the reader on a journey from mathematical derivation to software implementation of some of the most intriguing algorithms in ML. My goal in writing this book is to distill the science of ML and present it in a way that will convey intuition and inspire the reader to self-learn, innovate, and advance the field. Thank you for your interest, and welcome to the world of ML algorithms!

📄 Page 14

xiii acknowledgments I want to thank the people at Manning who made this book possible: publisher Marjan Bace and everyone on the editorial and production teams, including Patrick Barb, Elesha Hyde, and many others who worked behind the scenes. Many thanks go to the technical peer reviewers, led by Aleksandar Dragosavljević— Abhilash Babu, Allan Makura, Ariel Gamiño, Bin Hu, Christian Sutton, Fernando García Sedano, Harsh Raval, James J. Byleckie, Japneet Singh, Johnny Hopkins, Jor- dan Samek, Kai Gellien, Khai Win, Kumar Abhishek, Madhav Ayyagari, Maria Ana, Marvin Schwarze, Maxim Volgin, Morteza Kiadi, Or Golan, Ravi Kiran Bamidi, Sad- hana Ganapathiraju, Sanket Naik, Shreyas B. G., Sleiman Salameh, Sriram Macharla, Sumit Bhattacharyya, Vatsal Desai, and Walter Alexander Mata Lopez—as well as the forum contributors. The reviewers provided section-by-section feedback on everything from contents to figures to code implementation, and they played an important role in shaping the manuscript. On the technical side, special thanks go to Junpeng Lao, who served as the book’s technical editor. Junpeng Lao is a senior data scientist at Google. He earned his PhD and worked as a postdoc in cognitive neuroscience. He developed a fondness for Bayesian statistics and generative modeling after working primarily with bootstrap- ping and permutation testing during his academic life. He is also a core contributor to Blackjax, PyMC, and TensorFlow Probability. Many thanks also to Hubin Keio, who served as the book’s technical proofreader. I was truly amazed at the level of detail and helpfulness of their feedback while writing the book. Finally, I’d like to express gratitude to my partner, Kelly, for being very supportive throughout the process of writing this book.

📄 Page 15

xiv about this book This book dives into the design of ML algorithms from scratch. Throughout the book, you will develop mathematical intuition for classic and modern ML algorithms and learn the fundamentals of Bayesian inference and deep learning as well as data struc- tures and algorithmic paradigms in ML. Understanding ML algorithms from scratch will help you choose the right algo- rithm for the task, explain the results, troubleshoot advanced problems, extend algo- rithms to new applications, and improve the performance of existing algorithms. What makes this book stand out from the crowd is its from-scratch analysis that dis- cusses how and why ML algorithms work in significant depth, a carefully selected set of algorithms that I found most useful and impactful in my experience as a PhD stu- dent in machine learning, fully worked out derivations and implementations of ML algorithms explained in the text, as well as some other topics less commonly found in other ML texts. After reading this book, you’ll have a solid mathematical intuition for classic and modern ML algorithms in the areas of supervised and unsupervised learning, and will have gained experience in the domains of core ML, natural language processing, computer vision, optimization, computational biology, and finance. Who should read this book This book was written for anyone interested in exploring machine learning algo- rithms in depth. It may prove invaluable to many different types of readers, including the following:

📄 Page 16

ABOUT THIS BOOK xv ■ Aspiring data scientists ■ Entry- to principal-level data scientists ■ Software developers seeking to transition to data science ■ Data engineers seeking to deepen their knowledge of ML models ■ Graduate students with research interests in ML ■ Undergraduate students interested in ML The prerequisites for reading this book include a basic level of programming skills in Python, and an intermediate level of understanding of linear algebra, applied proba- bility, and multivariable calculus. How this book is organized This book is structured in four parts. It is recommended that you read the chapters in sequence if the topic is new to you. However, feel free to reference a particular algo- rithm if you are more familiar with the subject. Each chapter is followed by a few exer- cises to help you practice some of the tools taught in the chapter, and you are welcome to reference appendix B for solutions to these exercises. Also, included at the end of each part is a machine learning research section with the purpose of reviewing state-of-the-art work and encouraging the reader to stay on top of a rapidly changing field. Part 1 reviews different types of ML algorithms, motivates implementation from first principles, and introduces two main camps of Bayesian inference—Markov chain Monte Carlo and variational inference: ■ Chapter 1 introduces the subject of Bayesian inference and deep learning as well as algorithmic paradigms and data structures used in the software imple- mentation of machine learning algorithms. ■ Chapter 2 introduces key Bayesian concepts and motivates Markov chain Monte Carlo via a series of examples, ranging from stock price estimation to Metropolis- Hastings sampling of a multivariate Gaussian mixture. ■ Chapter 3 focuses on variational inference and, in particular, mean-field approximation in application to image denoising in the Ising model. ■ Chapter 4 discusses linear, nonlinear, and probabilistic data structures as well as four algorithmic paradigms: complete search, greedy, divide and conquer, and dynamic programming. Part 2 reviews supervised learning algorithms. Supervised learning algorithms contain labeled examples as part of the training dataset and consist of two main classes— classification and regression: ■ Chapter 5 focuses on classification algorithms. We’ll derive several classic algo- rithms, including the perceptron, SVM, logistic regression, naive Bayes, and decision trees.

📄 Page 17

ABOUT THIS BOOKxvi ■ Chapter 6 highlights four intriguing regression algorithms: Bayesian linear regression, hierarchical Bayesian regression, KNN regression, and Gaussian process regression. ■ Chapter 7 presents a selected set of supervised learning algorithms, including Markov models, such as page rank algorithms and hidden Markov models; imbalanced learning strategies; active learning; Bayesian optimization for hyperparameter selection; and ensemble methods. Part 3 reviews unsupervised learning algorithms. Unsupervised learning takes place when no training labels are available. In the case of unsupervised learning, we are often interested in discovering patterns in data and learning data representations. ■ Chapter 8 starts by looking at the Bayesian nonparametric extension of the K-means algorithm followed by the EM algorithm for Gaussian mixture models. We will then proceed with two different dimensionality reduction techniques— namely, PCA and t-SNE—in application to learning an image manifold. ■ Chapter 9 continues the discussion of selected unsupervised learning algo- rithms. We’ll start by looking at latent Dirichlet allocation for learning topic models, followed by density estimators and structure learning algorithms, and concluding with simulated annealing and genetic algorithms. Part 4 reviews deep learning algorithms. Deep learning algorithms revolutionized the field of machine learning and enabled many research and business applications that were previously thought to be out of reach of classic ML algorithms. ■ Chapter 10 begins with deep learning algorithm fundamentals, such as multi- layer perceptron and the LeNet convolutional model for MNIST digit classifica- tion, followed by more advanced applications, such as image search based on the ResNet50 convolutional neural network. We will dive into recurrent neural networks applied to sequence classification using LSTMs and implement a multi-input model from scratch for sequence similarity. Finally, we’ll conduct a comparative study of different optimization algorithms used for training deep neural networks. ■ Chapter 11 presents more advanced deep learning algorithms. We will investi- gate generative models based on variational autoencoders and implement an anomaly detector from scratch for time-series data. We’ll study an intriguing combination of neural networks and probabilistic graphical models, and imple- ment a mixture density network from scratch. Next, we’ll describe the powerful transformer architecture and apply it to text classification. Finally, we’ll exam- ine graph neural networks and use one to classify nodes in a citation graph. About the code This book contains many examples of source code both in numbered listings and in line with normal text. In both cases, source code is formatted in a fixed-width font like this to separate it from ordinary text.

📄 Page 18

ABOUT THIS BOOK xvii In many cases, the original source code has been reformatted; we’ve added line breaks and reworked indentation to accommodate the available page space in the book. In rare cases, even this was not enough, and listings include line-continuation markers (➥). Additionally, comments in the source code have often been removed from the listings when the code is described in the text. Code annotations accompany many of the listings, highlighting important concepts. You can get executable snippets of code from the liveBook (online) version of this book at https://livebook.manning.com/book/machine-learning-algorithms-in-depth. All code examples are available for download from the book’s website: https:// www.manning.com/books/machine-learning-algorithms-in-depth and on GitHub: https://github.com/vsmolyakov/ml_algo_in_depth. liveBook discussion forum Purchase of Machine Learning Algorithms in Depth includes free access to liveBook, Manning’s online reading platform. Using liveBook’s exclusive discussion features, you can attach comments to the book globally or to specific sections or paragraphs. It’s a snap to make notes for yourself, ask and answer technical questions, and receive help from the author and other users. To access the forum, go to https://livebook .manning.com/book/machine-learning-algorithms-in-depth/discussion. You can also learn more about Manning’s forums and the rules of conduct at https://livebook .manning.com/discussion. Manning’s commitment to our readers is to provide a venue where a meaningful dialogue between individual readers and between readers and the author can take place. It is not a commitment to any specific amount of participation on the part of the author, whose contribution to the forum remains voluntary (and unpaid). We sug- gest you try asking the author some challenging questions lest his interest stray! The forum and the archives of previous discussions will be accessible from the publisher’s website as long as the book is in print.

📄 Page 19

xviii about the author VADIM SMOLYAKOV is a data scientist in the Enterprise & Security DI research and development team at Microsoft. He is a former PhD student in AI at MIT CSAIL, with research interests in Bayes- ian inference and deep learning. Prior to joining Microsoft, Vadim developed machine learning solutions in the e-commerce space. In his current role, he is interested in developing AI prod- ucts at scale and leading diverse teams.

📄 Page 20

xix about the cover illustration The figure on the cover of Machine Learning Algorithms in Depth, titled “Maraichere,” or “Vegetable Grower,” is taken from a book by Louis Curmer published in 1841. Each illustration is finely drawn and colored by hand. In those days, it was easy to identify where people lived and what their trade or sta- tion in life was just by their dress. Manning celebrates the inventiveness and initiative of the computer business with book covers based on the rich diversity of regional cul- ture centuries ago, brought back to life by pictures from collections such as this one.