Introduction to Machine Learning Lecture 1

1 Introduction to Machine LearningLecture 1 Mehryar MohriCourant Institute and Google Mohri - Introduction to Machine LearningLogisticsPrerequisites: basics concepts needed in probability and statistics will be : 5 homework assignments. mid-term exam, final : recommended, not mandatory. no single textbook covering material presented. Lecture slides available list: join as soon as Mohri - Introduction to Machine LearningMachine LearningDefinition: computational methods using experience to improve performance, , to make accurate : data-driven task, thus statistics, : use height and weight to predict science: need to design efficient and accurate algorithms, analysis of complexity, theoretical Mohri - Introduction to Machine LearningExamples of Learning TasksOptical character or document classification, spam analysis, part-of-speech tagging, statistical recognition, speech synthesis, speaker recognition, face Mohri - Introduction to Machine LearningExamples of Learning TasksFraud detection (credit card, telephone), network (chess, backgammon).

2 Unassisted control of a vehicle (robots, navigation).Medical systems, search engines, information extraction Mohri - Introduction to Machine LearningSome Broad Areas of MLClassification: assign a category to each object (OCR, text classification, speech recognition). note: infinite number of categories in difficult : predict a real value for each object (prices, stock values, economic variables, ratings). measure of success: closeness of : order objects according to some criterion (relevant web pages returned by a search engine).7pageMehryar Mohri - Introduction to Machine LearningSome Broad Areas of MLClustering: partition data into homogenous groups (analysis of very large data sets).Dimensionality reduction: find lower-dimensional manifold preserving some properties of the data (computer vision).Density estimation: Learning probability distribution according to which data has been sampled (distribution typically selected out of pre-selected family).

3 8pageMehryar Mohri - Introduction to Machine LearningObjectives of Machine LearningAlgorithms: design of efficient, accurate, and general Learning algorithms to deal with large-scale problems (|data| > 1-10M). make accurate predictions (unseen examples). handle a variety of different Learning questions what can be learned? Under what conditions? how well can it be learned computationally?9pageMehryar Mohri - Introduction to Machine LearningThis courseAlgorithms: covers most key Learning algorithms. nearest-neighbor algorithms. perceptron, Winnow, Halving, Weighted Majority. support vector machines, kernel methods. boosting, : illustration of the use of algorithms. software and familiarization (assignments).Theory: analysis and Introduction to Mohri - Introduction to Machine LearningTopicsBasic notions of Learning with expert advice (Weighted Majority, Exponentiated Average).On-line linear classification (Perceptron, Winnow).

4 Support Vector Machines (SVMs).11pageMehryar Mohri - Introduction to Machine LearningTopicsKernel methods (boosting, bagging).Logistic estimation (ML, Maxent models)Multi-class Mohri - Introduction to Machine LearningTopicsLinear ridge regression, Lasso. Neural networks. reductionIntroduction to reinforcement of Learning Mohri - Introduction to Machine LearningDefinitions and TerminologyExample: an object or instance in data : the set of attributes, often represented as a vector, associated to an example, , height and weight for gender : in classification, category associated to an object, , positive or negative in binary classification. in regression, real-valued Mohri - Introduction to Machine LearningDefinitions and TerminologyTraining data: data used for training data: data exclusively used for testing standard Learning scenarios: supervised Learning : labeled training data.

5 Unsupervised Learning : no labeled data. semi-supervised Learning : labeled training data + unlabeled data. transductive Learning : labeled training data + unlabeled test Mohri - Introduction to Machine LearningExample - SPAM DetectionProblem: classify each e-mail message as SPAM or non-SPAM (binary classification problem).Data: large collection of SPAM and non-SPAM messages (labeled examples).Features: define features for all examples ( , presence or absence of some sequences). critical step (should use prior knowledge).Algorithm: choose type of algorithm adapted to the problem. typically requires choice of hypothesis Mohri - Introduction to Machine LearningExample - SPAM DetectionLearning stages: divide labeled collection into training and test data. use training data and features to train Machine Learning algorithm. predict labels of examples in test data to evaluate algorithm. algorithms may require choosing a parameter (number of rounds, Learning parameter, trade--off parameter) validation set or Mohri - Introduction to Machine LearningCross-ValidationPartition data into folds (typically, or ).

6 Train on all but th fold hypothesis , .Compute -fold cross validation error:Choose value of minimizing CV (sample size) leave-one-out cross-validation and ,kkk [1,K]1KK k=1 error(h ,k,foldk).k K=mpageMehryar Mohri - Introduction to Machine LearningImportance of FeaturesFeatures: poor features, uncorrelated with labels, make Learning very difficult for all algorithms. good features, can be very effective; often knowledge of the task can :190010100111011010110001001010011101111 0111100111001001002120211000111001000011 0001111010001101001010101001100001110000 140pageMehryar Mohri - Introduction to Machine LearningGeneralizationGeneralization: not memorization. minimizing error on the training set in general does not guarantee good generalization. too complex hypotheses could overfit training sample. how much complexity vs. training sample size?20