What is learning Foundations of Artificial Intelligence Learning denotes changes in a system that enable a system to do the same task more efficiently the next time Herbert Simon Learning is constructing or modifying representations of what is being experienced Ryszard Michalski Learning is making useful changes in our minds Marvin Minsky CS101 FALL 2007 Learning Theory 1 2 A general model of the learning process Why learn Understand and improve efficiency of human learning Use to improve methods for teaching and tutoring people e g better computer aided instruction Discover new things or structure that were previously unknown to humans Examples data mining scientific discovery Fill in skeletal or incomplete specifications about a domain Large complex AI systems cannot be completely derived by hand and require dynamic updating to incorporate new information Learning new characteristics expands the domain or expertise and lessens the brittleness of the system Build software agents that can adapt to their users or to other software agents 3 4 Major paradigms of machine learning The inductive learning problem Rote learning One to one mapping from inputs to stored representation Learning by memorization Association based storage and retrieval Induction Use specific examples to reach general conclusions Clustering Unsupervised identification of natural groups in data Analogy Determine correspondence between two different representations Discovery Unsupervised specific goal not given Genetic algorithms Evolutionary search techniques based on an analogy to survival of the fittest Reinforcement Feedback positive or negative reward given at the end of a sequence of steps Extrapolate from a given set of examples to make accurate predictions about future examples Supervised versus unsupervised learning Learn an unknown function f X Y where X is an input example and Y is the desired output Supervised learning implies we are given a training set of X Y pairs by a teacher Unsupervised learning means we are only given the Xs and some ultimate feedback function on our performance Concept learning or classification Given a set of examples of some concept class category determine if a given example is an instance of the concept or not If it is an instance we call it a positive example If it is not it is called a negative example Or we can make a probabilistic prediction e g using a Bayes net 5 A learning game with playing cards Model spaces I I Decision tree I would like to show what a full house is I give you examples which are are not full houses I 6 Nearest neighbor 6 6 6 9 9 is a full house 6 6 6 6 9 is not a full house 3 3 3 6 6 is a full house 1 1 1 6 6 is a full house Q Q Q 6 6 is a full house 1 2 3 4 5 is not a full house 1 1 3 4 5 is not a full house 1 1 1 4 5 is not a full house 1 1 1 4 4 is a full house Version space 7 8 A learning game with playing cards Intuitively If you haven t guessed already a full house is three of a kind and a pair of another kind 6 6 6 9 9 is a full house 6 6 6 6 9 is not a full house 3 3 3 6 6 is a full house 1 1 1 6 6 is a full house Q Q Q 6 6 is a full house 1 2 3 4 5 is not a full house 1 1 3 4 5 is not a full house 1 1 1 4 5 is not a full house 1 1 1 4 4 is a full house I m asking you to describe a set This set is the concept I want you to learn This is called inductive learning i e learning a generalization from a set of examples Concept learning is a typical inductive learning problem given examples of some concept such as cat soy protein milkshake or good stock investment we attempt to infer a definition that will allow the learner to correctly recognize future instances of that concept 9 Supervised learning 10 Why Supervised learning This is called supervised learning because we assume that there is a teacher who classified the training data the learner is told whether an instance is a positive or negative example of a target concept This definition might seem counter intuitive If the teacher knows the concept why doesn t s he tell us directly and save us all the work 11 12 Supervised learning the answer Supervised concept learning The teacher only knows the classification the learner has to find out what the classification is Imagine an online store there is a lot of data concerning whether a customer returns to the store The information is there in terms of attributes and whether they come back or not However it is up to the learning system to characterize the concept e g Given a training set of positive and negative examples of a concept Construct a description that will accurately classify whether future examples are positive or negative That is learn some good estimate of function f given a training set x1 y1 x2 y2 xn yn where each yi is either positive or negative or a probability distribution over If a customer bought more than 4 books s he will return If a customer spent more than 50 s he will return 13 14 Inductive learning as search Predicate Learning Methods Instance space I defines the language for the training and test instances Typically but not always each instance i I is a feature vector Features are also sometimes called attributes or variables I V1 x V2 x x Vk i v1 v2 vk Decision tree Version space Need to provide H with some structure Class variable C gives an instance s class to be predicted Model space M defines the possible classifiers Putting Things Together M I C M m1 mn possibly infinite Model space is sometimes but not always defined in terms of the same features as the instance space Explicit representation of hypothesis space H Training data can be used to direct the search for a good consistent complete simple hypothesis in the model space yes no Test set Evaluation Induced hypothesis h Training set Learning procedure L Object set Example set X Goal predicate Observable predicates Hypothesis space H Bias 15 16 How can we do this Learning a predicate Set E of objects e g cards drinking cups writing instruments Go with the most general hypothesis possible any card is a rewarded card This will cover all the positive examples but will not be able to eliminate any negative examples Goal predicate CONCEPT X where X is an object in E that takes the value True or False e g REWARD MUG PENCIL BALL Go with the most specific hypothesis possible the rewarded cards are 4 7 2 This will correctly sort all the examples in the training set but it is overly specific will not be able to sort any new examples Observable predicates A X B X e g