Instance Based Learning CS4780 5780 Machine Learning Fall 2011 Thorsten Joachims Cornell University Reading Mitchell Chapter 1 Sections 8 1 8 2 Concept Learning Definition Acquire an operational definition of a general category of objects given positive and negative training examples Concept Learning Example correct 3 complete complete partial complete color 2 yes no yes yes original presentation binder 2 3 2 yes clear no yes clear no no unclear no yes clear yes A Homework yes yes no yes Instance Space X Set of all possible objects described by attributes often called features Concept c Subset of objects from X c is unknown Target Function f Characteristic function indicating membership in c based on attributes i e label f is unknown Training Data S Set of instances labeled with target function Concept Learning as Learning a Binary Function Task Learn to imitate a function f X 1 1 Training Examples Learning algorithm is given the correct value of the function for particular inputs training examples An example is a pair x y where x is the input and y f x is the output of the target function applied to x Goal Find a function that approximates h X 1 1 f X 1 1 as well as possible K Nearest Neighbor KNN Given Training data x1 y1 xn yn Attribute vectors Label Parameter Similarity function Number of nearest neighbors to consider k Prediction rule New example x with K nearest neighbors k train examples with largest KNN Example 1 2 3 4 correct 3 complete complete partial complete color 2 yes no yes yes original 2 yes yes no yes presentation 3 clear clear unclear clear binder 2 no no no yes How will new examples be classified Similarity function Value of k A Homework yes yes no yes 1 1 1 1 Weighted K Nearest Neighbor Given Training data Attribute vectors Target attribute Parameter Similarity function Number of nearest neighbors to consider k Prediction rule New example x K nearest neighbors k train examples with largest Types of Attributes Symbolic nominal EyeColor brown blue green Boolean alife TRUE FALSE Numeric Integer age 0 105 Real length Structural Natural language sentence parse tree Protein sequence of amino acids Example Expensive Housing 200 sqft Example Effect of k Hastie Tibshirani Friedman 2001 Supervised Learning Task Learn to imitate a function f X Y Training Examples Learning algorithm is given the correct value of the function for particular inputs training examples An example is a pair x f x where x is the input and f x is the output of the function applied to x Goal Find a function that approximates h X Y f X Y as well as possible Weighted K Nearest Neighbor for Regression Given Training data Attribute vectors Target attribute Parameter Similarity function Number of nearest neighbors to consider k Prediction rule New example x K nearest neighbors k train examples with largest Collaborative Filtering