1Foundations of Artificial IntelligenceCS101FALL 2007Learning Theory2What is learning?• “Learning denotes changes in a system that ...enable a system to do the same task moreefficiently the next time.” –Herbert Simon• “Learning is constructing or modifyingrepresentations of what is being experienced.”–Ryszard Michalski• “Learning is making useful changes in our minds.”–Marvin Minsky3Why 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 previouslyunknown 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 handand require dynamic updating to incorporate new information.– Learning new characteristics expands the domain or expertise andlessens the “brittleness” of the system• Build software agents that can adapt to their users or toother software agents4A general model of the learning process5Major paradigms of machine learning• Rote learning – One-to-one mapping from inputs to storedrepresentation. “Learning by memorization.” Association-basedstorage and retrieval.• Induction – Use specific examples to reach general conclusions• Clustering – Unsupervised identification of natural groups in data• Analogy – Determine correspondence between two differentrepresentations• Discovery – Unsupervised, specific goal not given• Genetic algorithms – “Evolutionary” search techniques, based onan analogy to “survival of the fittest”• Reinforcement – Feedback (positive or negative reward) given atthe end of a sequence of steps6The inductive learning problem• Extrapolate from a given set of examples to make accuratepredictions about future examples• Supervised versus unsupervised learning– Learn an unknown function f(X) = Y, where X is an input exampleand 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, determineif 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)7Model spacesI++--I++--I++--NearestneighborVersion spaceDecisiontree8A learning game with playing cardsI would like to show what a full house is. I give you exampleswhich are/are not full houses:6! 6" 6! 9# 9! is a full house6! 6 " 6! 6 # 9! is not a full house3 # 3! 3 # 6 ! 6 " is a full house1 # 1! 1 # 6 ! 6 " is a full houseQ # Q! Q # 6 ! 6 " is a full house1 ! 2 " 3! 4 # 5! is not a full house1 ! 1 " 3! 4 # 5! is not a full house1 ! 1 " 1! 4 # 5! is not a full house1 ! 1 " 1! 4 # 4! is a full house9A learning game with playing cardsIf you haven’t guessed already, a full house is three of a kind anda pair of another kind.6 ! 6 " 6 $ 9 # 9 $ is a full house6 ! 6 " 6 $ 6 # 9 $ is not a full house3 # 3 $ 3 # 6 ! 6 " is a full house1 # 1 $ 1 # 6 ! 6 " is a full houseQ # Q $ Q # 6 ! 6 " is a full house1 ! 2 " 3 $ 4 # 5 $ is not a full house1 ! 1 " 3 $ 4 # 5 $ is not a full house1 ! 1 " 1 $ 4 # 5 $ is not a full house1 ! 1 " 1 $ 4 # 4 $ is a full house10Intuitively,I’m asking you to describe a set. This set is theconcept I want you to learn.This is called inductive learning, i.e., learning ageneralization from a set of examples.Concept learning is a typical inductive learningproblem: given examples of some concept, such as“cat,” “soy protein milkshake,” or “good stockinvestment,” we attempt to infer a definition thatwill allow the learner to correctly recognize futureinstances of that concept.11Supervised learningThis is called supervised learning because weassume that there is a teacher who classified thetraining data: the learner is told whether aninstance is a positive or negative example of atarget concept.12Why Supervised learning?This definition might seem counter intuitive. Ifthe teacher knows the concept, why doesn’t s/hetell us directly and save us all the work?13Supervised learning – the answerThe teacher only knows the classification, thelearner has to find out what the classification is.Imagine an online store: there is a lot of dataconcerning whether a customer returns to thestore. The information is there in terms ofattributes and whether they come back or not.However, it is up to the learning system tocharacterize the concept, e.g,If a customer bought more than 4 books, s/he willreturn.If a customer spent more than $50, s/he willreturn.14Supervised concept learning• Given a training set of positive and negative examplesof a concept• Construct a description that will accurately classifywhether future examples are positive or negative• That is, learn some good estimate of function f given atraining set {(x1, y1), (x2, y2), ..., (xn, yn)} where each yiis either + (positive) or - (negative), or a probabilitydistribution over +/-15Inductive learning as search• Instance space I defines the language for the training and testinstances– 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)• Class variable C gives an instance’s class (to be predicted)• Model space M defines the possible classifiers– M: I ! C, M = {m1, … mn} (possibly infinite)– Model space is sometimes, but not always, defined in terms of thesame features as the instance space• Training data can be used to direct the search for a good(consistent, complete, simple) hypothesis in the model space16Predicate-Learning MethodsPredicate-Learning Methods• Decision tree• Version spacePutting Things TogetherPutting Things TogetherObject setGoal predicateObservable predicatesExampleset XTrainingset !TestsetBiasHypothesisspace HInducedhypothesis hLearningprocedure LEvaluationyesnoExplicit representationof hypothesis space HNeed to provide H with some “structure”17Learning a predicate Set E of objects (e.g., cards, drinking cups, writinginstruments) Goal predicate CONCEPT (X),