A First Encounter with Machine LearningMax WellingDonald Bren School of Information and Computer ScienceUniversity of California IrvineApril 21, 20102ContentsPreface iiiLearning and Intuition vii1 Data and Information 11.1 Data Representation . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Preprocessing the Data . . . . . . . . . . . . . . . . . . . . . . . 42 Data Visualization 73 Learning 113.1 In a Nutshell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 Types of Machine Learning 174.1 In a Nutshell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 Nearest Neighbors Classification 215.1 The Idea In a Nutshell . . . . . . . . . . . . . . . . . . . . . . . . 236 The Naive Bayesian Classifier 256.1 The Naive Bayes Model . . . . . . . . . . . . . . . . . . . . . . 256.2 Learning a Naive Bayes Classifier . . . . . . . . . . . . . . . . . 276.3 Class-Prediction for New Instances . . . . . . . . . . . . . . . . . 286.4 Regularization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306.5 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316.6 The Idea In a Nutshell . . . . . . . . . . . . . . . . . . . . . . . . 317 The Perceptron 337.1 The Perceptron Model . . . . . . . . . . . . . . . . . . . . . . . 34iiiCONTENTS7.2 A Different Cost function: Logistic Regression . . . . . . . . . . 377.3 The Idea In a Nutshell . . . . . . . . . . . . . . . . . . . . . . . . 388 Support Vector Machines 398.1 The Non-Separable case . . . . . . . . . . . . . . . . . . . . . . 439 Support Vector Regression 4710 Kernel ridge Regression 5110.1 Kernel Ridge Regression . . . . . . . . . . . . . . . . . . . . . . 5210.2 An alternative derivation . . . . . . . . . . . . . . . . . . . . . . 5311 Kernel K-means and Spectral Clustering 5512 Kernel Principal Components Analysis 5912.1 Centering Data in Feature Space . . . . . . . . . . . . . . . . . . 6113 Fisher Linear Discriminant Analysis 6313.1 Kernel Fisher LDA . . . . . . . . . . . . . . . . . . . . . . . . . 6613.2 A Constrained Convex Programming Formulation of FDA . . . . 6814 Kernel Canonical Correlation Analysis 6914.1 Kernel CCA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71A Essentials of Convex Optimization 73A.1 Lagrangians and all that . . . . . . . . . . . . . . . . . . . . . . . 73B Kernel Design 77B.1 Polynomials Kernels . . . . . . . . . . . . . . . . . . . . . . . . 77B.2 All Subsets Kernel . . . . . . . . . . . . . . . . . . . . . . . . . 78B.3 The Gaussian Kernel . . . . . . . . . . . . . . . . . . . . . . . . 79PrefaceIn winter quarter 2007 I taught an undergraduate course in machine learning atUC Irvine. While I had been teaching machine learning at a graduate level itbecame soon clear that teaching the same material to an undergraduate class wasa whole new challenge. Much of machine learning is build upon concepts frommathematics such as partial derivatives, eigenvalue decompositions, multivariateprobability densities and so on. I quickly found that these concepts could notbe taken for granted at an undergraduate level. The situation was aggravated bythe lack of a suitable textbook. Excellent textbooks do exist for this field, but Ifound all of them to be too technical for a first encounter with machine learning.This experience led me to believe there was a genuine need for a simple, intuitiveintroduction into the concepts of machine learning. A first read to wet the appetiteso to speak, a prelude to the more technical and advanced textbooks. Hence, thebook you see before you is meant for those starting out in the field who need asimple, intuitive explanation of some of the most useful algorithms that our fieldhas to offer.Machine learning is a relatively recent discipline that emerged from the gen-eral field of artificial intelligence only quite recently. To build intelligent machinesresearchers realized that these machines should learn from and adapt to their en-vironment. It is simply too costly and impractical to design intelligent systems byfirst gathering all the expert knowledge ourselves and then hard-wiring it into amachine. For instance, after many years of intense research the we can now recog-nize faces in images to a high degree accuracy. But the world has approximately30,000 visual object categories according to some estimates (Biederman). Shouldwe invest the same effort to build good classifiers for monkeys, chairs, pencils,axes etc. or should we build systems to can observe millions of training images,some with labels (e.g. in these pixels in the image correspond to a car) but mostof them without side information? Although there is currently no system whichcan recognize even in the order of 1000 object categories (the best system can getiiiivPREFACEabout 60% correct on 100 categories), the fact that we pull it off seemingly effort-lessly serves as a “proof of concept” that it can be done. But there is no doubt inmy mind that building truly intelligent machines will involve learning from data.The first reason for the recent successes of machine learning and the growth ofthe field as a whole is rooted in its multidisciplinary character. Machine learningemerged from AI but quickly incorporated ideas from fields as diverse as statis-tics, probability, computer science, information theory, convex optimization, con-trol theory, cognitive science, theoretical neuroscience, physics and more. Togive an …