Machine LearningOutlineWhat is learning?Why learn?A general model of learning agentsMajor paradigms of machine learningThe inductive learning problemSupervised concept learningInductive learning frameworkInductive learning as searchModel spacesSlide 12Learning decision treesDecision tree-induced partition – exampleInductive learning and biasPreference bias: Ockham’s RazorR&N’s restaurant domainA training setA decision tree from introspectionID3Choosing the best attributeRestaurant exampleSplitting examples by testing attributesID3-induced decision treeInformation theoryInformation theory IIThe Entropy Function Relative to Boolean ClassificationHuffman codeHuffman code exampleSo what does the Huffman code have to do with information theory?Information for classificationInformation for classification IIInformation gainComputing information gainSlide 35How well does it work?Extensions of the decision tree learning algorithmUsing gain ratiosComputing gain ratioReal-valued dataNoisy data and overfittingPruning decision treesConverting decision trees to rulesEvaluation methodologySummary: Decision tree learningComputational learning theory1Machine LearningMachine LearningChapter 18.1-18.3, 19.1,skim 20.4-20.5CS 63CS 63Adapted from slides byTim Finin andMarie desJardins.Some material adopted from notes by Chuck Dyer2Outline•Machine learning–What is ML?–Inductive learning•Supervised•Unsupervised–Decision trees–Computational learning theory3What is learning?•“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 Minsky4Why 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 agents5A general model of learning agents6Major paradigms of machine learning•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 steps7The inductive learning problem•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)8Supervised concept learning•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 +/-9Inductive learning framework•Raw input data from sensors are typically preprocessed to obtain a feature vector, X, that adequately describes all of the relevant features for classifying examples•Each x is a list of (attribute, value) pairs. For example, X = [Person:Sue, EyeColor:Brown, Age:Young, Sex:Female] •The number of attributes (a.k.a. features) is fixed (positive, finite)•Each attribute has a fixed, finite number of possible values (or could be continuous)•Each example can be interpreted as a point in an n-dimensional feature space, where n is the number of attributes10Inductive learning as search•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)•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 the same features as the instance space•Training data can be used to direct the search for a good (consistent, complete, simple) hypothesis in the model space11Model spaces•Decision trees–Partition the instance space into axis-parallel regions, labeled with class value•Version spaces–Search for necessary (lower-bound) and sufficient (upper-bound) partial instance descriptions for an instance to be a member of the class•Nearest-neighbor classifiers–Partition the instance space into regions defined by the centroid instances (or cluster of k instances)•Associative rules (feature values → class)•First-order logical rules•Bayesian networks (probabilistic dependencies of class on attributes)•Neural networks12Model spacesI++--I++--I++--NearestneighborVersion spaceDecisiontree13Learning decision trees•Goal: Build a decision tree to classify examples as positive or negative instances of a concept using supervised learning from a training set•A decision