Machine learning: lecture 1Tommi S. JaakkolaMIT [email protected] Machine learning: administrivia• Instructor: Prof. Tommi Jaakkola ([email protected])• TA: Jason Johnson ([email protected])• General info– lectures MW 2.30-4pm in 35-225– tutorials/recitations (time/location tba)– website http://www.ai.mit.edu/courses/6.867• Grading– midterm (15%), final (25%)– 6 (≈ bi-weekly) problem sets (30%)– final project (30%)Tommi Jaakkola, MIT AI Lab 2Machine learning• Statistical machine learning– principles, methods, and algorithms for learning andprediction on the basis of past experience– already everywhere: speech recognition, hand-writtencharacter recognition, information retrieval, operatingsystems, compilers, fraud detection, security, defenseapplications, ...Tommi Jaakkola, MIT AI Lab 3Learning“ye s”Tommi Jaakkola, MIT AI Lab 4Learning“ye s”“ye s”Tommi Jaakkola, MIT AI Lab 5Learning“ye s”“ye s”“no” (oops)Tommi Jaakkola, MIT AI Lab 6Learning• Steps– entertain a (biased) set of possibilities– adjust predictions based on feedback– rethink the set of possibilitiesTommi Jaakkola, MIT AI Lab 7Learning• Steps– entertain a (biased) set of possibilities– adjust predictions based on feedback– rethink the set of possibilities• Principles of learning are “universal”– society (e.g., scientific community)– animal (e.g., human)– machineTommi Jaakkola, MIT AI Lab 8Learning and prediction• We make predictions all the time but rarely invest igate theprocesses underlying our predictions• In carrying out scientific research we are also governed byhow theories are evaluated• To automate the process of making predictions we need tounderstand in addition how we searc h and refine “theories”Tommi Jaakkola, MIT AI Lab 9Learning: key steps• data and assumptions– what data is available for the learning task?– what can we assume about the problem?Tommi Jaakkola, MIT AI Lab 10Learning: key steps• data and assumptions– what data is available for the learning task?– what can we assume about the problem?• represe ntation– how should we represent the examples to be classifiedTommi Jaakkola, MIT AI Lab 11Learning: key steps• data and assumptions– what data is available for the learning task?– what can we assume about the problem?• represe ntation– how should we represent the examples to be classified• method and estimation– what are the pos sible hypotheses?– how do we adjust our predictions based on the feedback?Tommi Jaakkola, MIT AI Lab 12Learning: key steps• data and assumptions– what data is available for the learning task?– what can we assume about the problem?• represe ntation– how should we represent the examples to be classified• method and estimation– what are the pos sible hypotheses?– how do we adjust our predictions based on the feedback?• evaluation– how well are we doing?Tommi Jaakkola, MIT AI Lab 13Learning: key steps• data and assumptions– what data is available for the learning task?– what can we assume about the problem?• represe ntation– how should we represent the examples to be classified• method and estimation– what are the pos sible hypotheses?– how do we adjust our predictions based on the feedback?• evaluation– how well are we doing?• model selection– can we rethink the approach to do even better?Tommi Jaakkola, MIT AI Lab 14Data and assumptions“ye s”“ye s”. . . . . .– is this a digit/character/image classification problem?– how are the examples generated/labeled?Tommi Jaakkola, MIT AI Lab 15Representation• There are many ways of presenting the same information0111111001110010000000100000001001111110111011111001110111110001• The choice of representation may determine whether thelearning task is very easy or very difficultTommi Jaakkola, MIT AI Lab 16Representation0111111001110010000000100000001001111110111011111001110111110001 “ye s”0001111100000011000001110000011001111110111111001111111100000011 “ye s”1111111000000110000011000111111000000111100000111110001101111111 “no”Tommi Jaakkola, MIT AI Lab 17Representation0111111001110010000000100000001001111110111011111001110111110001 “ye s”0001111100000011000001110000011001111110111111001111111100000011 “ye s”1111111000000110000011000111111000000111100000111110001101111111 “no”“ye s”“ye s”“no”Tommi Jaakkola, MIT AI Lab 18Method and estimation• Examples (binary vectors of length d = 64)x = [111111100 . . . 0000110001101111111]T• Labels y ∈ {−1, 1} (“no”,”yes”)• A linear classifier (hypothese s)ˆy = sign ( θ · x ) = sign dXi=1θixi!where θ is a vector of parameters we have to learn.Tommi Jaakkola, MIT AI Lab 19Method and estimation cont’dx y0111111001110010000000100000001001111110111011111001110111110001 +10001111100000011000001110000011001111110111111001111111100000011 +11111111000000110000011000111111000000111100000111110001101111111 -1. . . . . .• How do we adjust the parameters θ based on the labels?ˆy = sign ( θ · x )Tommi Jaakkola, MIT AI Lab 20Method and estimation cont’dx y0111111001110010000000100000001001111110111011111001110111110001 +10001111100000011000001110000011001111110111111001111111100000011 +11111111000000110000011000111111000000111100000111110001101111111 -1. . . . . .• How do we adjust the parameters θ based on the labels?ˆy = sign ( θ · x )For example, we can simply refi ne/update the parameterswhenever we make a mistakeθ ← θ + yx when prediction was wrongTommi Jaakkola, MIT AI Lab 21Evaluation• How do we measure how well the method is working?Tommi Jaakkola, MIT AI Lab 22Evaluation• How do we measure how well the method is working?0 200 400 600 800 1000 1200 140000.10.20.30.40.50.60.70.80.91average errornumber of examplesFor example: average classification/predic tion error as afunction of the number of examples seen so farTommi Jaakkola, MIT AI Lab 23Model selection• Can we rethink the approach to do even better?– our classifier is limited, can we make it more flexible?– is there an entirely different type of classifier that wouldbe more suitable?Tommi Jaakkola, MIT AI Lab 24Types of learning problemsA rough classification of learning problems:• Supervised learning– explicit feedback (e.g., labels)• Unsupervised learning– no feedback, emphasis on structure and organization• Semi-supervised learning– partial feedback (e.g., a few