An Introduction to Machine Learning - icerm.brown.edu

1 IntroductionAlgorithmsChallenges and pitfalls to avoidAn Introduction to Machine LearningTRIPODS Summer Boorcamp: Topology and Machine LearningAugust 6, 2018An Introduction to Machine LearningIntroductionAlgorithmsChallenges and pitfalls to avoidGeneral Set-upSet-up and GoalSuppose we haveX1,X2,..,Xndata samples. Can we predictproperites about any givenXn+1,Xn+2,..,XN? Machine Learning systems attempt to predict properties of unknowndata based on the attributes or features of the Introduction to Machine LearningIntroductionAlgorithmsChallenges and pitfalls to avoidSupervised learningData comes with attributes that we want our algorithm to predictMachine Learning algorithm is given data attributes and desiredoutputs and the goal is to learn a way to map inputs to outputs in ageneral way2 main types of Learning :1 Classification: Data belongs to different classes/groups and wewant to be able to predict which class/group unlabeled databelongs to2 Regression.

2 Data labeled with one or more continuous variables(parameters) and the task is to predict the value of these variablesfor unknown dataAn Introduction to Machine LearningIntroductionAlgorithmsChallenges and pitfalls to avoidImage source: Introduction to Machine LearningIntroductionAlgorithmsChallenges and pitfalls to avoidUnsupervised LearningNo labels are given to the algorithmTraining data consists of a set of input vectors{X1,X2,..,Xn}withno target outputs3 Types of goals in this setting:1 Clustering: discover groups with similar features within the data2 Density Estimation:determine distribution of data within the inputspace3 Dimensionality Reduction:project data into a lower dimensionalspace than input spaceAn Introduction to Machine LearningIntroductionAlgorithmsChallenges and pitfalls to avoidImage sources.

3 , , Introduction to Machine LearningIntroductionAlgorithmsChallenges and pitfalls to avoidApplications of Machine LearningSpam email detectionImproving weather predictionTargeted advertising and web searchesPredicting emergency room wait times using staffing levels,patient data, charts, and layout of ERIdentifying heart failure from physician s notesPredicting hospital readmissionsLearning dynamical systems models directly fromhigh-dimensional sensor data (Byron Boots, Georgia Tech)An Introduction to Machine LearningIntroductionAlgorithmsChallenges and pitfalls to avoidGoals For TodayLearn a commonly used supervised Learning algorithm (supportvector machines)Learn a commonly used unsupervised Learning algorithm(k-means clustering)Understand challenges in Machine learningApply algorithms to real dataAn Introduction to Machine LearningIntroductionAlgorithmsChallenges and pitfalls to avoidSupport Vector MachinesKmeans clusteringSupport Vector Machines: SetupA SVM constructs a hyperplane (or set of hyperplanes) in a high orinfinite dimensional space, which can be used for classification,regression or other source: Introduction to Machine LearningIntroductionAlgorithmsChallenges and pitfalls to avoidSupport Vector MachinesKmeans clusteringSVM.

4 Linear, separable caseWe want to find the hyperplane that maximizes the margin as follows:Mathematical formulationGivenX1,X2,..Xn Rp, with labelsYi [ 1,1], letH(x) = ( + Tx){>0ifYi=1<0ifYi= 1where R,|| ||=1, andH(x) =0 is the decision boundary. = iwiYiXiyields the maximum margin, and we use convexoptimixation to get and weight function:f(x) =sign(H(x))An Introduction to Machine LearningIntroductionAlgorithmsChallenges and pitfalls to avoidSupport Vector MachinesKmeans clusteringSVM: Linear, non-separable caseIn most cases there will be outliers so we need to allow for formulationGivenX1,X2,..Xn Rp, with labelsYi [ 1,1]. Now we choose , that maximimze the margin of separation (M) such thatYi( + TXi) M(1 i) iwhere i 0 for alliand i Cgives you a constraint of before, = iwiYiXiand the decision function is given asf(x) =sign( + iwiYiXTix)An Introduction to Machine LearningIntroductionAlgorithmsChallenges and pitfalls to avoidSupport Vector MachinesKmeans clusteringSVM: non-linear caseimage source: Introduction to Machine LearningIntroductionAlgorithmsChallenges and pitfalls to avoidSupport Vector MachinesKmeans clusteringSVM: Kernel TrickIn most cases we do not want a linear separation boundary.}

5 Instead,we use a kernel a non-linear transformation :Rd Rd .2 Fit a linear decision boundary inRd using( (X1),Y1),( (X2),Y2),..)as the training the kernel to beK(x,x ) = (x)T (x )4 Since the classifier only relies onXTix, we get the decisionfunction:f(x) =sign( + iwiYiK(Xi,x))5 Using the kernel, we never actually have to transform the data!An Introduction to Machine LearningIntroductionAlgorithmsChallenges and pitfalls to avoidSupport Vector MachinesKmeans clusteringCommon kernel examplesPolynomial-SVM:K(X,X ) = (X X )dWhen d is large, the kernel still only requires n computations,whereas explicit representation may not fit in memoryRadial basis function:K(X,X ) =exp( ||X X ||2)An Introduction to Machine LearningIntroductionAlgorithmsChallenges and pitfalls to avoidSupport Vector MachinesKmeans clusteringPros and Cons of SVMA dvantagesEffective in high dimensional spacesCan be used for classification or regressionMemory efficient since it only uses a subset of training points inthe decision functionVersatile since we can use different kernel functions for thedecision functionDisadvantagesNon-Probabilistic.

6 SVMs do not directly provide probabilityestimatesMethod will likely not do well if the number of features issignificantly greater than the number of samplesAn Introduction to Machine LearningIntroductionAlgorithmsChallenges and pitfalls to avoidSupport Vector MachinesKmeans clusteringClustering: K-meansGoal: cluster a data set{X1,..,XN}into K clustering algorithm1 Pick K random points 1,.., Kto be centroids of the K clustersC1,..,CK2 Assign eachXito clusterjif mink [0,K]d(Xi, k) =d(Xi, j)3 Update the centroids 1,.., Kby setting j=1|Cj| Xi Cj|Xi|4 Repeat 2 and 3 until none of the cluster assignments changeAn Introduction to Machine LearningIntroductionAlgorithmsChallenges and pitfalls to avoidSupport Vector MachinesKmeans clusteringK-means clusteringImage source: ~reile/edu/TNM025/Matlab/ Introduction to Machine LearningIntroductionAlgorithmsChallenges and pitfalls to avoidSupport Vector MachinesKmeans clusteringHow do you choose K?

7 Assume you know the truth so you can compute the sum of squarederrors. Use the Elbow Method:Image source: Introduction to Machine LearningIntroductionAlgorithmsChallenges and pitfalls to avoidSupport Vector MachinesKmeans clusteringPros and Cons K-means ClusteringAdvantagesFast and easy to understandEasy to implementWorks well for convex clustersDisadvantagesWill not work well if clusters are not convexDifficult to choose KRandomness in initial step makes results difficult to reproduceAn Introduction to Machine LearningIntroductionAlgorithmsChallenges and pitfalls to avoidSupport Vector MachinesKmeans clusteringWhen does K-means clustering fail?Image source: Introduction to Machine LearningIntroductionAlgorithmsChallenges and pitfalls to avoidOverfitting Hallucinating a classifier occurs when data are not sufficient todetermine the correct classifierClassifiers will encode random features in data which are notgrounded in realityOverfitting can be decomposed into bias and variance:Bias is the learner s tendency to consistently learn the same(wrong) thingVariance is the tendency to learn random things irrespective of realsignalA more powerful algorithm is not necessarily betterAn Introduction to Machine LearningIntroductionAlgorithmsChallenges and pitfalls to avoidBias and VarianceImage source.

8 [2]An Introduction to Machine LearningIntroductionAlgorithmsChallenges and pitfalls to avoidCurse of Dimensionalityimage source: biggest problem inmachine learningGeneralizing correctly isexponentially more difficult asthe dimensionality, or numberof features, increasesGood news: usually highdimensional data areconcentrated on/near a lowerdimensional manifold so wecan use dimension reductiontechniques to avoid this curseAn Introduction to Machine LearningIntroductionAlgorithmsChallenges and pitfalls to avoidContamination of classifierGoal: General classifierProblem: Illusion of successUse cross-validation to avoid this:Randomly divide training data into multiple subsetsOnly use one subset for training at a timeTest each classifier on data not used for trainingAverage results to see how well the classifiers doAn Introduction to Machine LearningIntroductionAlgorithmsChallenges and pitfalls to avoidUseful Software PackagesPyML, pyMC, scikit-learn in PythonTensorFlow (Google)MATLAB s Statistics and Machine Learning toolboxSpider (MATLAB)Shogunmlpack in C++Torch (Lua) and PyTorch (Python)Weka (Java)Orange (Open source Machine Learning and data visualization)An Introduction to Machine LearningIntroductionAlgorithmsChallenges and pitfalls to avoidREFERENCES[1]Bishop, Christopher.

9 Pattern Recognition and Machine (2009)[2]Domingos, Pedro. A Few Useful Things to Know about MachineLearning.[3]Rudin, Cynthia and Kiri L. Wagstaff. Machine Learning for Scienceand Society. Mach Lean,Springer. (2013)[4]Wagstaff, Kiri L. Machine Learning that of the29th International Conferences on Machine Learning ,Edinburgh,Scotland. (2012)[5] [6] [7] ~kathy/cs4701/ [8] Introduction to Machine Learning