COMP 875: Introductions• Name, year, research area/group• Why are you interested in machine learning and how does it relate to your research?does it relate to your research?• What topics would you like to see covered in this course?What is Machine Learning?• Using past experiences to improve future performance (on a particular task)•For a machine experiences come in the form of data•For a machine, experiences come in the form of data• What does it mean to improve performance?–Learning is guided by a quantitative objective,Learning is guided by a quantitative objective, associated with a particular notion of loss to be minimized (or gain to be maximized)• Why machine learning?–Often it is too difficult to design a set of rules“by hand”Often it is too difficult to design a set of rules by hand– Machine learning is about automatically extracting relevant information from data and applying it to ldtanalyze new dataSource: G. ShakhnarovichMachine Learning Steps• Data collection: Start with training data for which we know the correct outcome provided by a “teacher”• Representation: Decide how to encode the input to the learning program•Modeling:Choose ahypothesis class–a set of•Modeling:Choose a hypothesis class–a set of possible explanations for the data• Estimation: Find best hypothesis you can in the chosen class• Model selection: We may reconsider the class of hypotheses given theoutcomehypotheses given the outcome– Each of these steps can make or break the learning outcomeSource: G. ShakhnarovichLearning and Probability• There are many sources of uncertainty with which learning algorithms must cope:Variability of the data–Variability of the data– Dataset collection–Measurement noiseMeasurement noise– Labeling errors• Probability and statistics provide an appropriate framework to deal with uncertainty• Some basic statistical assumptions:Tiidt i ldf th “t ” d li–Training data is sampled from the “true” underlying data distribution–Future test data will be sampled from the same pdistributionSource: G. ShakhnarovichExample of a learning problemGiven: training images and their categoriesWhat are the categories• Possible representation: image of size n×npixels → vector Given: training images and their categoriesWhat are the categories of these test images?pgpof length n2(or 3n2if color)Source: G. ShakhnarovichThe Importance of Representation• Dimensionality• Beyond vectors: complex or heterogeneous input objectsWb–Web pages– Program traces–Images with captions or metadata–Images with captions or metadata– Video with sound–Proteins• Feature extraction and feature selection– What measurements/information about the input objects are the most useful for solving the given problem?• Successful representation requires domain knowledge!If we could find the“ideal”feature representation we–If we could find the ideal feature representation, we would not even need learning!Types of learning problems• Supervised– ClassificationRi–Regression• Unsupervised•Semi-supervised•Semi-supervised• Reinforcement learning•Active learningg•….Supervised learning• Given training examples of inputs and corresponding outputs, produce the “correct” outputs for new inputs•Two main scenarios:•Two main scenarios:– Classification: outputs are discrete variables (category labels). Learn a decision boundary that separates one class from the other– Regression: also known as “curve fitting” or “function approximation.” Learn a continuous input-output mapping from examples (possibly noisy)Regression: example 1• Suppose we want to predict gas mileage of a car based on some characteristics: number of cylinders or doors, weight, horsepower, year etc.or doors, weight, horsepower, year etc.Source: G. ShakhnarovichRegression: example 2• Training set: faces (represented as vectors of distances between keypoints) together with experimentally obtained attractiveness rankingsobtained attractiveness rankings• Learn: function to reproduce attractiveness ranking based on training inputs and outputsAttractiveness score f(v)Vector of distancesvVector of distances vT. Leyvand, D. Cohen-Or, G. Dror, and D. Lischinski, Data-driven enhancement of facial attractiveness, SIGGRAPH 2008Regression: example 3• Input: scalar (attractiveness score)• Output: vector-valued object (face)B. Davis and S. Lazebnik, “Analysis of Human Attractiveness Using Manifold Kernel Regression,” ICIP 2008Regression: example 4• Input: scalar (age)• Output: vector-valued object (3D brain image)B. C. Davis, P. T. Fletcher, E. Bullitt and S. Joshi, "Population Shape Regression From Random Design Data", ICCV, 2007.Structured PredictionImageWordSource: B. TaskarStructured PredictionStParse treeSentenceParse treeSource: B. TaskarStructured PredictionSentence in twoWord alignmentSentence in two languagesWord alignmentSource: B. TaskarStructured PredictionAmino-acid sequenceBond structureAmino-acid sequenceBond structureSource: B. TaskarStructured Prediction• Many image-based inference tasks can loosely be thought of as “structured prediction”•Data associationproblem•Data association problemmodelSource: D. RamananOther supervised learning scenarios• Learning similarity functions from relations between multiple input objectsPairwiseconstraintsSource: X. Sui, K. GraumanOther supervised learning scenarios• Learning similarity functions from relations between multiple input objectsTilt t itTriplet constraintsSource: X. Sui, K. GraumanUnsupervised Learning• Given only unlabeled data as input, learn some sort of structure•The objective is often more vague or subjective than•The objective is often more vague or subjective than in supervised learning. This is more of an exploratory/descriptive data analysisUnsupervised Learning• Clustering– Discover groups of “similar” data pointsUnsupervised Learning• Quantization– Map a continuous input to a discrete (more compact) outputcompact) output213Unsupervised Learning• Dimensionality reduction, manifold learning– Discover a lower-dimensional surface on which the data livesthe data livesUnsupervised Learning• Density estimation– Find a function that approximates the probability density of the data (i e value of the function is high fordensity of the data (i.e., value of the function is high for “typical” points and low for