Concept Learning 1 Learning Concepts from Examples Concept typically means categorization based on features A Concept Learning Task Four Examples Example 1 2 3 4 AirTemp Warm Warm Cold Warm Humidity Normal High High High Wind Strong Strong Strong Strong Water Warm Warm Warm Cool Forecast EnjoySport Same Yes Same Yes Change No Change Yes Target concept 2 Sky Sunny Sunny Rainy Sunny Days on which Aldo enjoys his favorite water sport Two categories yes no A Concept Learning Task Example 1 2 3 4 Sky Sunny Sunny Rainy Sunny Humidity Normal High High High Wind Strong Strong Strong Strong Water Warm Warm Warm Cool Forecast EnjoySport Same Yes Same Yes Change No Change Yes Some possible concepts 3 AirTemp Warm Warm Cold Warm Enjoy sport when Sky Sunny Enjoy sport when Airtemp Warm Concept Learning Methodology Inducing general functions from specific training examples Concerns acquiring general concepts or categories from training examples based on symbolic or logical representations Formulated as 4 search through space of potential hypotheses What is a concept Concepts bird car situations in which I should study more in order to pass the exam Each concept describes a subset of objects subset of animals that constitute birds Each concept is a boolean valued function defined over this larger set 5 function defined over all animals whose value is true for birds and false for other animals Concept Learning 6 Automatically inferring the general definition of some concept given examples labeled as members or non members of the concept Concept Learning Inferring a boolean valued function from training examples of its input and output A Concept Learning Task Target concept Days on which Aldo enjoys his favorite water sport Example 1 2 3 4 AirTemp Warm Warm Cold Warm Humidity Normal High High High Wind Strong Strong Strong Strong Water Warm Warm Warm Cool Forecast EnjoySport Same Yes Same Yes Change No Change Yes Task is to learn to predict value of EnjoySport 7 Sky Sunny Sunny Rainy Sunny for an arbitrary day based on values of other attributes Hypothesis Representation by Learner Conjunction of constraints on attributes For each attribute 8 Sky AirTemp Humidity Wind Water Forecast indicate by a that any value is acceptable for this attribute specify a single required value for the attribute eg Warm indicate by a that no value is acceptable Three Example Hypotheses H1 Enjoy sport only on cold days with high humidity Cold High H2 Most general hypothesis every day is a positive example H3 Most specific possible hypothesis 9 no day is a positive example Hypothesis Representation 10 If x is an instance that satisfies all constraints of hypothesis h then h classifies x as a positive example h x 1 Each hypothesis defines a particular definition of a categorizer Notation 11 Set of items over which concept is defined instances denoted by X X is set of all possible days each represented by attributes Sky AirTemp Humidity Wind Water and Forecast Concept or function to be learned target concept c c can be any boolean valued function defined over the instances c X 0 1 Learner is presented a set of Training Examples c x 1 are positive examples c x 0 are negative examples Set of all possible hypotheses H each hypothesis h in H is a function h X 0 1 Goal of Learner is to find hypothesis h such that h x c x for all x in X EnjoySport Concept Learning Task Given Instances X Possible days described by attributes 12 Sky with possible values Sunny Cloudy and Rainy AirTemp with values Warm and Cold Humidity with values Normal and High Wind with values Strong and Weak Water with values Warm and Cool Forecast with values Same and Change Hypotheses H Each hypothesis is described by a conjunction of the attributes Sky AirTemp Humidity Wind Water and Forecast The constraints may be any value is acceptable no value is acceptable or a specific value Target concept c EnjoySport X 0 1 Training examples D Positive and negative examples of target function Determine A hypothesis h such that h x c x for all x in X Inductive Learning Hypothesis Although the Learning Task is to determine hypothesis h identical to the target concept c over the entire set of instances X the only information available about c is its value over the training examples Inductive Learning Hypothesis 13 Any hypothesis found to approximate the target function well over a sufficiently large set of training examples will also approximate the target function well over other unobserved samples Concept Learning As Search Concept learning is a search through a large space of hypotheses implictly defined by the hypothesis representation 14 Goal is to find hypothesis that best fits training examples Instances Hypotheses and more general than relation 15 Size of Instance Hypotheses Spaces Enjoysport learning Task sky 3 values rest 2 values instance space X 3 2 2 2 2 2 96 instances hypotheses 5 4 4 4 4 4 5120 syntactically distinct hypotheses 1 4 3 3 3 3 3 973 semantically distinct hypotheses 16 every hypothesis containing classifies instance as negative since null values classify every instance as negative extra one for all null values General to Specific Ordering of Hypotheses Algorithm can search through hypothesis space by taking advantage of ordering of hypotheses that exists not enumerating every possible hypothesis h1 Sunny Strong h2 Sunny Since h2 imposes fewer contraints on the instance it classifies more instances as positive h2 is more general than h1 17 More general than or equal to relation Definition Let hj and hk be boolean valued functions defined over X Then hj is more general than or equal to hk written hj hk if and only if x X hk x 1 h j x 1 18 Instances Hypotheses and more general than relation 19 FIND S Algorithm 20 Initialize h to the most specific hypothesis in H For each positive training instance x For each attribute constraint ai in h If the constraint ai is satisfied by x Then do nothing Else replace ai in h by the next more general constraint that is satisfied by x Output hypothesis h Hypothesis Space Search Performed by FIND S positive instance negative instance 21 FIND S Finding a Maximally Specific Hypothesis Step1 h o o o o o o Upon observing first training example current hypothesis is too specific So replace by the next more general constraint After observing second training sample h Sunny Warm Strong Warm Same Ignore third sample which is negative After fourth sample 22 h Sunny Warm Normal Strong Warm Same h Sunny Warm Strong