Concept Learning Instance Based Learning CS4780 Machine Learning Fall 2009 Definition Acquire an operational definition of a general category g y of objects j given g positive p and negative g training examples Thorsten Joachims Cornell University Reading Mitchell Chapter 1 Sections 8 1 8 2 Concept Learning as Learning a Binary Function Concept Learning Example 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 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 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 A example l is i a pair i x y where h x is i the h input i andd y f x is the output of the target function applied to x Goal Find a function h X 1 1 that approximates f X 1 1 as well as possible Training Data S Set of instances labeled with target function K Nearest Neighbor KNN KNN Example Given Training data Attribute vectors Label Parameter Similarity function Number of nearest neighbors to consider k Prediction rule New example x K nearest neighbors k training examples with largest 1 2 3 4 correct 3 complete complete partial complete color 2 yes no yes yes original 2 yes yes no yes presentation binder A Homework 3 2 clear no yes 1 clear no yes 1 unclear no no 1 clear yes yes 1 How will new examples be classified Similarity function Value of k 1 Weighted K Nearest Neighbor Given Training data Types of Attributes Symbolic nominal Attribute vectors Target attribute EyeColor brown blue green Boolean Parameter anemic TRUE FALSE Similarity function Number of nearest neighbors to consider k Numeric Integer age 0 105 Real length Prediction rule New example x K nearest neighbors k training examples with largest Structural Natural language sentence parse tree Protein sequence of amino acids Example Effect of k Example Expensive Housing 200 sqft Hastie Tibshirani Friedman 2001 Supervised Learning Concept Learning Classification Regression etc 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 A example l is i a pair i x f x f where h x is i the h input i andd f x is the output of the function applied to x Goal Find a function h X Y that approximates 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 training examples with largest 2 Collaborative Filtering 3