CS269: Machine Learning Theory Lecture 1: Course Introduction Jenn Wortman Vaughan University of California, Los Angeles September 27, 2010What is machine learning?What is machine learning? Machine learning is the study of how to use past observations or experience to automatically and efficiently learn to make better predictions or choose better actions in the futureMovie RecommendationsClick PredictionClick PredictionAutonomous Flight Helicopter rolls: Helicopter flips:Other Examples • Medical diagnosis • Handwritten character recognition • Customer segmentation (marketing) • Document segmentation (classifying news) • Spam filtering • Weather prediction and climate tracking • Gene prediction • Face recognitionSpam Prediction We are given a set of labeled email messages To:$Jenn$Wortman$Vaughan$From:$Jeff$Vaughan$Subject:$Plans$for$tonight$To:$Jenn$Wortman$Vaughan$From:$Jens$Palsberg$Subject:$Mee=ng$To:$Jenn$Wortman$Vaughan$From:$Bob$Smith$Subject:$V14GR4$4$U$✔$✔$✖$Spam Prediction We are given a set of labeled email messages Goal is to predict labels of new messages that arrive To:$Jenn$Wortman$Vaughan$From:$Jeff$Vaughan$Subject:$Plans$for$tonight$To:$Jenn$Wortman$Vaughan$From:$Jens$Palsberg$Subject:$Mee=ng$To:$Jenn$Wortman$Vaughan$From:$Bob$Smith$Subject:$V14GR4$4$U$✔$✔$✖$To:$Jenn$Wortman$Vaughan$From:$NIPS$CommiGee$Subject:$Paper$decision$?A Classification Problem First we need a way to represent the data… “Jenn” “269” “Viagra” Known Sender Spelling Bad Spam? 1$1$0$0$1$0$1$0$0$1$0$0$0$0$1$0$0$1$0$0$0$0$1$1$0$1$0$1$0$0$A Classification Problem First we need a way to represent the data… “Jenn” “269” “Viagra” Known Sender Spelling Bad Spam? 1$1$0$0$1$0$1$0$0$1$0$0$0$0$1$0$0$1$0$0$0$0$1$1$0$1$0$1$0$0$“feature vector” “label”A Classification Problem First we need a way to represent the data… Then we need a reasonable set of prediction rules… • Disjunctions (spam if not known or not “269”) • Thresholds (spam if “Jenn”+“269”+known < 2) “Jenn” “269” “Viagra” Known Sender Spelling Bad Spam? 1$1$0$0$1$0$1$0$0$1$0$0$0$0$1$0$0$1$0$0$0$0$1$1$0$1$0$1$0$0$A Classification Problem First we need a way to represent the data… Then we need a reasonable set of prediction rules… • Disjunctions (spam if not known or not “269”) • Thresholds (spam if “Jenn”+“269”+known < 2) “Jenn” “269” “Viagra” Known Sender Spelling Bad Spam? 1$1$0$0$1$0$1$0$0$1$0$0$0$0$1$0$0$1$0$0$0$0$1$1$0$1$0$1$0$0$“concept class” or “function class” or “hypothesis class”A Classification Problem First we need a way to represent the data… Then we need a reasonable set of prediction rules… • Disjunctions (spam if not known or not “269”) • Thresholds (spam if “Jenn”+“269”+known < 2) “Jenn” “269” “Viagra” Known Sender Spelling Bad Spam? 1$1$0$0$1$0$1$0$0$1$0$0$0$0$1$0$0$1$0$0$0$0$1$1$0$1$0$1$0$0$“prediction rule” or “hypothesis” or “concept”A Classification Problem First we need a way to represent the data… Then we need a reasonable set of prediction rules… • Disjunctions (spam if not known or not “269”) • Thresholds (spam if “Jenn”+“269”+known < 2) Finally, we need an algorithm… “Jenn” “269” “Viagra” Known Sender Spelling Bad Spam? 1$1$0$0$1$0$1$0$0$1$0$0$0$0$1$0$0$1$0$0$0$0$1$1$0$1$0$1$0$0$Typical Classification Problem Set$of$labeled$training$examples$(feature$vectors)$Machine$learning$algorithm$Predic=on$rule$(hypothesis)$Typical Classification Problem Set$of$labeled$training$examples$(feature$vectors)$Machine$learning$algorithm$Predic=on$rule$(hypothesis)$New$example$(test$data)$Predi cted$label$Batch Versus Online Learning What if there are no clear training and test sets?Batch Versus Online Learning What if there are no clear training and test sets? To:$Jenn$Wortman$Vaughan$From:$Jeff$Vaughan$Subject:$Plans$for$tonight$Batch Versus Online Learning What if there are no clear training and test sets? To:$Jenn$Wortman$Vaughan$From:$Jeff$Vaughan$Subject:$Plans$for$tonight$✔$Batch Versus Online Learning What if there are no clear training and test sets? To:$Jenn$Wortman$Vaughan$From:$Jeff$Vaughan$Subject:$Plans$for$tonight$To:$Jenn$Wortman$Vaughan$From:$Jens$Palsberg$Subject:$Mee=ng$✔$Batch Versus Online Learning What if there are no clear training and test sets? To:$Jenn$Wortman$Vaughan$From:$Jeff$Vaughan$Subject:$Plans$for$tonight$To:$Jenn$Wortman$Vaughan$From:$Jens$Palsberg$Subject:$Mee=ng$✔$✔$Batch Versus Online Learning What if there are no clear training and test sets? To:$Jenn$Wortman$Vaughan$From:$Jeff$Vaughan$Subject:$Plans$for$tonight$To:$Jenn$Wortman$Vaughan$From:$Jens$Palsberg$Subject:$Mee=ng$To:$Jenn$Wortman$Vaughan$From:$Bob$Smith$Subject:$V14GR4$4$U$✔$✔$Batch Versus Online Learning What if there are no clear training and test sets? To:$Jenn$Wortman$Vaughan$From:$Jeff$Vaughan$Subject:$Plans$for$tonight$To:$Jenn$Wortman$Vaughan$From:$Jens$Palsberg$Subject:$Mee=ng$To:$Jenn$Wortman$Vaughan$From:$Bob$Smith$Subject:$V14GR4$4$U$✔$✔$✔$Batch Versus Online Learning What if there are no clear training and test sets? To:$Jenn$Wortman$Vaughan$From:$Jeff$Vaughan$Subject:$Plans$for$tonight$To:$Jenn$Wortman$Vaughan$From:$Jens$Palsberg$Subject:$Mee=ng$To:$Jenn$Wortman$Vaughan$From:$Bob$Smith$Subject:$V14GR4$4$U$✔$✔$✖$✔$✗$Batch Versus Online Learning What if there are no clear training and test sets? The goal is now to update the prediction rule over time while making as few mistakes as possible To:$Jenn$Wortman$Vaughan$From:$Jeff$Vaughan$Subject:$Plans$for$tonight$To:$Jenn$Wortman$Vaughan$From:$Jens$Palsberg$Subject:$Mee=ng$To:$Jenn$Wortman$Vaughan$From:$Bob$Smith$Subject:$V14GR4$4$U$✔$✔$✖$✔$✗$Other Learning Settings • Unsupervised learning (clustering) • Semi-supervised learning • Active learning • Reinforcement learningWhat is learning theory?What is learning theory? The goal of learning theory is to develop and analyze formal models that help us understand … what concepts we can hope to learn efficiently, and how much data is necessary to learn themWhat is learning theory? The goal of learning theory is to develop and analyze formal models that help us understand … what concepts we can hope to learn efficiently, and how much data is necessary to learn them … what types of guarantees we