Machine Learning Function Approximation and Version Spaces Recommended reading Mitchell Chapter 2 Machine Learning 10 701 Tom M Mitchell Center for Automated Learning and Discovery Carnegie Mellon University January 10 2005 Machine Learning Study of algorithms that improve their performance at some task with experience Learning to Predict Emergency C Sections Sims et al 2000 9714 patient records each with 215 features Object Detection Prof H Schneiderman Example training images for each orientation Text Classification Company home page vs Personal home page vs Univeristy home page vs Reading a noun vs verb Rustandi et al 2005 Growth of Machine Learning Machine learning is preferred approach to Speech recognition Natural language processing Computer vision Medical outcomes analysis Robot control This trend is accelerating Improved machine learning algorithms Improved data capture networking faster computers Software too complex to write by hand New sensors IO devices Demand for self customization to user environment C Sky Temp Humid Wind Water Forecst EnjoySpt Function Approximation Given Instances X e g x 0 1 1 0 0 1 Hypotheses H set of functions h X 0 1 e g H is the set of all boolean functions defined by conjunctions of constraints on the features of x such as 0 1 1 1 Training Examples D sequence of positive and negative examples of an unknown target function c X 0 1 x1 c x1 xm c xm Determine A hypothesis h in H such that h x c x for all x in X Function Approximation Given Instances X e g x 0 1 1 0 0 1 Hypotheses H set of functions h X 0 1 e g H is the set of all boolean functions defined by conjunctions of constraints on the features of x such as 0 1 1 1 Training Examples D sequence of positive and negative examples of an unknown target function c X 0 1 x1 c x1 xm c xm Determine A hypothesis h in H such that h x c x for all x in X A hypothesis h in H such that h x c x for all x in D What we want What we can observe Here draw instance space hypothesis space figure Instances Hypotheses and More General Than Simplifying Assumptions for today only Target function c is deterministic Target function c is contained in hypotheses H Training data is error free noise free Problems with Find S Finds just one of the many h s in H that fit the training data the most specific one Can t determine when learning has converged to the final h Version Space for our EnjoySport problem Version Space Candidate Elimination Algorithm Initialize S G to maximally specific general h s in H For each training example x c x if positive example x 1 Generalize S as much as needed to cover x in all possible ways Remove any h G for which h x 1 if negative example x 0 Specialize G as much as needed to exclude x in all possible ways Remove any h S for which h x 1 Retain only members of G that are more general than some member of S Retain only members of S that are more general than some member of G Matches NO instances Version Space after all four examples Machine Translation Example Probst et al 2003 Seeded VS Learning Probst et al 2003 Construct VS around a seed positive example Include only hypotheses at a predetermined level of generalization k levels in the partial order What you should know Well posed function approximation problem Instance space X Hypothesis space H Sample of training data D Learning as search optimization over H Various objective functions Sample complexity of learning How many examples needed to converge Depends on H how examples generated notion of convergence Biased and unbiased learners Futility of unbiased learning
View Full Document
Unlocking...