(PPT) 1 LEARNING Adopted from slides and notes by Tim Finin, Marie desJardins andChuck Dyer - DOKUMEN.TIPS (2023)

Download PPT Report

• View
  215

• Download
  2

Tags:

• unsupervised learning

• rote learning

• supervised concept learning

• given example

• inductive learning problem

• given set of examples

• ryszard michalski learning

• herbert simon learning

• Slide 1
• 1 LEARNING Adopted from slides and notes by Tim Finin, MariedesJardins andChuck Dyer
• Slide 2
• 2 What is Learning? Learning denotes changes in a systemthat... enable a system to do the same task more efficiently thenext time. -- Herbert Simon Learning is constructing or modifyingrepresentations of what is being experienced. -- Ryszard MichalskiLearning is making useful changes in our minds. -- MarvinMinsky
• Slide 3
• 3 Why Learn? Understand and improve efficiency of humanlearning Use to improve methods for teaching and tutoring people(e.g., better computer-aided instruction.) Discover new things orstructures that are unknown to humans Example: Data mining,Knowledge Discovery in Databases Fill in skeletal or incompletespecifications about a domain Large, complex AI systems cannot becompletely derived by hand and require dynamic updating toincorporate new information. Learning new characteristics expandsthe domain or expertise and lessens the "brittleness" of the systemBuild software agents that can adapt to their users, to othersoftware agents, and to the changing environment.
• Slide 4
• 4 A General Model of Learning Agents
• Slide 5
• 5 Major Paradigms of Machine Learning Rote Learning --One-to-one mapping from inputs to stored representation. "Learningby memorization. Association-based storage and retrieval.Clustering Analogue -- Determine correspondence between twodifferent representations Induction -- Use specific examples toreach general conclusions Discovery -- Unsupervised, specific goalnot given Genetic Algorithms Neural Networks Reinforcement --Feedback (positive or negative reward) given at end of a sequenceof steps. Assign reward to steps by solving the credit assignmentproblem--which steps should receive credit or blame for a finalresult?
• Slide 6
• 6 The Inductive Learning Problem Induce rules that extrapolatefrom a given set of examples to make accurate predictions aboutfuture examples. Supervised versus Unsupervised learning Learn anunknown function f(X) = Y, where X is an input example and Y is thedesired output. Supervised learning implies we are given a trainingset of (X, Y) pairs by a "teacher." Unsupervised learning means weare only given the Xs and some (ultimate) feedback function on ourperformance. Concept learning or Classification Given a set ofexamples of some concept/class/category, determine if a givenexample 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 anegative example.
• Slide 7
• 7 Supervised Concept Learning Given a training set of positiveand negative examples of a concept Usually each example has a setof features/attributes Construct a description that will accuratelyclassify 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). f is a function of the features/attributes
• Slide 8
• 8 Inductive Learning Framework Raw input data from sensors arepreprocessed to obtain a feature vector, X, that adequatelydescribes 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 andnames of attributes (aka features) is fixed (positive, finite).Each attribute has a fixed, finite number of possible values. Eachexample can be interpreted as a point in an n- dimensional featurespace, where n is the number of attributes.
• Slide 9
• 9 Inductive Learning by Nearest-Neighbor Classification Onesimple approach to inductive learning is to save each trainingexample as a point in feature space Classify a new example bygiving it the same classification (+ or -) as its nearest neighborin Feature Space. A variation involves computing a weighted sum ofclass of a set of neighbors where the weights correspond todistances Another variation uses the center of class The problemwith this approach is that it doesn't necessarily generalize wellif the examples are not well "clustered."
• Slide 10
• 10 Learning Decision Trees Goal: Build a decision tree forclassifying examples as positive or negative instances of a conceptusing supervised learning from a training set. A decision tree is atree where each non-leaf node is associated with an attribute(feature) each leaf node is associated with a classification (+ or-) each arc is associated with one of the possible values of theattribute at the node where the arc is directed from.Generalization: allow for >2 classes e.g., {sell, hold, buy}Color ShapeSize+ +- +- + big small roundsquare red greenblue
• Slide 11
• 11 Preference Bias: Ockham's Razor Aka Occams Razor, Law ofEconomy, or Law of Parsimony Principle stated by William of Ockham(1285-1347/49), a scholastic, that non sunt multiplicanda entiapraeter necessitatem or, entities are not to be multiplied beyondnecessity. The simplest explanation that is consistent with allobservations is the best. Therefor, the smallest decision tree thatcorrectly classifies all of the training examples is best. Findingthe provably smallest decision tree is NP-Hard, so instead ofconstructing the absolute smallest tree consistent with thetraining examples, construct one that is pretty small.
• Slide 12
• 12 Inductive Learning and Bias Suppose that we want to learn afunction f(x) = y and we are given some sample (x,y) pairs, as infigure (a). There are several hypotheses we could make about thisfunction, e.g.: (b), (c) and (d). A preference for one over theothers reveals the bias of our learning technique, e.g.: preferpiece-wise functions prefer a smooth function prefer a simplefunction and treat outliers as noise
• Slide 13
• 13 R&Ns Restaurant Domain Develop a decision tree to modelthe decision a patron makes when deciding whether or not to waitfor a table at a restaurant. Two classes: wait, leave Tenattributes: alternative restaurant available?, bar in restaurant?,is it Friday?, are we hungry?, how full is the restaurant?, howexpensive?, is it raining?,do we have a reservation?, what type ofrestaurant is it?, what's the purported waiting time? Training setof 12 examples ~ 7000 possible cases
• Slide 14
• 14 A Training Set
• Slide 15
• 15 A decision Tree from Introspection
• Slide 16
• 16 ID3 Induced Decision Tree
• Slide 17
• 17 ID3 A greedy algorithm for Decision Tree Constructiondeveloped by Ross Quinlan, 1987 Consider a smaller tree a bettertree Top-down construction of the decision tree by recursivelyselecting the "best attribute" to use at the current node in thetree, based on the examples belonging to this node. Once theattribute is selected for the current node, generate childrennodes, one for each possible value of the selected attribute.Partition the examples of this node using the possible values ofthis attribute, and assign these subsets of the examples to theappropriate child node. Repeat for each child node until allexamples associated with a node are either all positive or allnegative.
• Slide 18
• 18 Choosing the Best Attribute The key problem is choosingwhich attribute to split a given set of examples. Somepossibilities are: Random: Select any attribute at randomLeast-Values: Choose the attribute with the smallest number ofpossible values (fewer branches) Most-Values: Choose the attributewith the largest number of possible values (smaller subsets)Max-Gain: Choose the attribute that has the largest expectedinformation gain, i.e. select attribute that will result in thesmallest expected size of the subtrees rooted at its children. TheID3 algorithm uses the Max-Gain method of selecting the bestattribute.
• Slide 19
• 19 Splitting Examples by Testing Attributes
• Slide 20
• 20 ID3 Induced Decision Tree
• Slide 21
• 21 Another example: tennis anyone?
• Slide 22
• 22 Choosing the first split
• Slide 23
• 23 Resulting Decision Tree
• Slide 24
• 24 Information Theory Background If there are n equallyprobable possible messages, then the probability p of each is 1/nInformation conveyed by a message is -log(p) = log(n) Eg, if thereare 16 messages, then log(16) = 4 and we need 4 bits toidentify/send each message. In general, if we are given aprobability distribution P = (p1, p2,.., pn) the informationconveyed by distribution (aka Entropy of P) is: I(P) = -(p1*log(p1)+ p2*log(p2) +.. + pn*log(pn))
• Slide 25
• 25 The entropy is the average number of bits/message needed torepresent a stream of messages. Examples: if P is (0.5, 0.5) thenI(P) is 1 if P is (0.67, 0.33) then I(P) is 0.92, if P is (1, 0)then I(P) is 0. The more uniform is the probability distribution,the greater is its information gain/entropy.
• Slide 26
• 26 Example: Huffman code In 1952 MIT student David Huffmandevised, in the course of doing a homework assignment, an elegantcoding scheme which is optimal in the case where all symbolsprobabilities are integral powers of 1/2. A Huffman code can bebuilt in the following manner: Rank all symbols in order ofprobability of occurrence. Successively combine the two symbols ofthe lowest probability to form a new composite symbol; eventuallywe will build a binary tree where each node is the probability ofall nodes beneath it. Trace a path to each leaf, noticing thedirection at each node.
• Slide 27
• 27 Huffman code example Msg.Prob. A.125 B.125 C.25 D.5.51.125.25 A C B D 0 1 0 0 1 1 If we need to send many messages(A,B,C or D) and they have this probability distribution and we usethis code, then over time, the average bits/message should approach1.75 (= 0.125*3+0.125*3+0.25*2*0.5*1)
• Slide 28
• 28 If a set T of records is partitioned into disjointexhaustive classes (C1,C2,..,Ck) on the basis of the value of thecategorical attribute, then the information needed to identify theclass of an element of T is Info(T) = I(P) where P is probabilitydistribution of partition (C1,C2,..,Ck): P = (|C1|/|T|,|C2|/|T|,..., |Ck|/|T|) If we partition T w.r.t attribute X intosets {T1,T2,..,Tn} then the information needed to identify theclass of an element of T becomes the weighted average of theinformation needed to identify the class of an element of Ti, i.e.the weighted average of Info(Ti): Info(X,T) = |Ti|/|T| * Info(Ti) =|Ti|/|T| * log |Ti|/|T|
• Slide 29
• 29 Gain Consider the quantity Gain(X,T) defined as Gain(X,T) =Info(T) - Info(X,T) This represents the difference betweeninformation needed to identify an element of T and informationneeded to identify an element of T after the value of attribute Xhas been obtained, that is, this is the gain in information due toattribute X. We can use this to rank attributes and to builddecision trees where at each node is located the attribute withgreatest gain among the attributes not yet considered in the pathfrom the root. The intent of this ordering are twofold: To createsmall decision trees so that records can be identified after only afew questions. To match a hoped for minimality of the processrepresented by the records being considered (Occam's Razor).
• Slide 30
• 30 The ID3 algorithm is used to build a decision tree, given aset of non-categorical attributes C1, C2,.., Cn, the categoricalattribute C, and a training set T of records. function ID3 (R: aset of non-categorical attributes, C: the categorical attribute, S:a training set) returns a decision tree; begin If S is empty,return a single node with value Failure; If every example in S hasthe same value for categorical attribute, return single node withthat value; If R is empty, then return a single node with mostfrequent of the values of the categorical attribute found inexamples S; [note: there will be errors, i.e., improperlyclassified records]; Let D be attribute with largest Gain(D,S)among Rs attributes; Let {dj| j=1,2,.., m} be the values ofattribute D; Let {Sj| j=1,2,.., m} be the subsets of S consistingrespectively of records with value dj for attribute D; Return atree with root labeled D and arcs labeled d1, d2,.., dm goingrespectively to the trees ID3(R-{D},C,S1), ID3(R-{D},C,S2),..,ID3(R-{D},C,Sm); end ID3;
• Slide 31
• 31 How well does it work? Many case studies have shown thatdecision trees are at least as accurate as human experts. A studyfor diagnosing breast cancer had humans correctly classifying theexamples 65% of the time, and the decision tree classified 72%correct. British Petroleum designed a decision tree for gas- oilseparation for offshore oil platforms that replaced an earlierrule-based expert system. Cessna designed an airplane flightcontroller using 90,000 examples and 20 attributes perexample.
• Slide 32
• 32 Extensions of the Decision Tree Learning Algorithm Usinggain ratios Real-valued data Noisy data and Overfitting Generationof rules Setting Parameters Cross-Validation for ExperimentalValidation of Performance C4.5 (and C5.0) is an extension of ID3that accounts for unavailable values, continuous attribute valueranges, pruning of decision trees, rule derivation, and so on.Incremental learning
• Slide 33
• 33 Using Gain Ratios The notion of Gain introduced earlierfavors attributes that have a large number of values. If we have anattribute D that has a distinct value for each record, thenInfo(D,T) is 0, thus Gain(D,T) is maximal. To compensate for thisQuinlan suggests using the following ratio instead of Gain:GainRatio(D,T) = Gain(D,T) / SplitInfo(D,T) SplitInfo(D,T) is theinformation due to the split of T on the basis of value ofcategorical attribute D. SplitInfo(D,T) = I(|T1|/|T|, |T2|/|T|,..,|Tm|/|T|) where {T1, T2,.. Tm} is the partition of T induced byvalue of D.
• Slide 34
• 34 Real-valued data Select a set of thresholds definingintervals; each interval becomes a discrete value of the attributeWe can use some simple heuristics always divide into quartiles Wecan use domain knowledge divide age into infant (0-2), toddler (3 -5), and school aged (5-8) or treat this as another learning problemtry a range of ways to discretize the continuous variable and seewhich yield better results w.r.t. some metric.
• Slide 35
• 35 Noisy data and Overfitting Many kinds of "noise" that couldoccur in the examples: Two examples have same attribute/valuepairs, but different classifications Some values of attributes areincorrect because of errors in the data acquisition process or thepreprocessing phase The classification is wrong (e.g., + instead of-) because of some error Some attributes are irrelevant to thedecision-making process, e.g., color of a die is irrelevant to itsoutcome. Irrelevant attributes can result in overfitting thetraining data. Overfitting: learning result fits data (trainingexamples) well but does not hold for unseen data (poorgeneralization) Often need to compromise fitness to data andgeneralization power Overfitting is a problem common to all methodsthat learn from data
• Slide 36
• 36 Fix overfitting/overlearning problem By cross validation(see later) By pruning lower nodes in the decision tree. Forexample, if Gain of the best attribute at a node is below athreshold, stop and make this node a leaf rather than generatingchildren nodes. (b and (c): better fit for data, poorgeneralization (d): not fit for the outlier (possibly due tonoise), but better generalization
• Slide 37
• 37 Pruning Decision Trees Pruning of the decision tree is doneby replacing a whole subtree by a leaf node. The replacement takesplace if a decision rule establishes that the expected error ratein the subtree is greater than in the single leaf. E.g., Training:eg, one training red success and one training blue Failures Test:three red failures and one blue success Consider replacing thissubtree by a single Failure node. After replacement we will haveonly two errors instead of five failures. Color 1 success 0 failure0 success 1 failure red blue Color 1 success 3 failure 1 success 1failure red blue 2 success 4 failure FAILURE
• Slide 38
• 38 Incremental Learning Incremental learning Change can be madewith each training example Non-incremental learning is also calledbatch learning Good for adaptive system (learning whileexperiencing) when environment undergoes changes Often with Highercomputational cost Lower quality of learning results ITI (by U.Mass): incremental DT learning package
• Slide 39
• 39 Evaluation Methodology Standard methodology: crossvalidation 1. Collect a large set of examples (all with correctclassifications!). 2. Randomly divide collection into two disjointsets: training and test. 3. Apply learning algorithm to trainingset giving hypothesis H 4. Measure performance of H w.r.t. test setImportant: keep the training and test sets disjoint! Learning isnot to minimize training error (wrt data) but the error fortest/cross-validation: a way to fix overfitting To study theefficiency and robustness of an algorithm, repeat steps 2-4 fordifferent training sets and sizes of training sets. If you improveyour algorithm, start again with step 1 to avoid evolving thealgorithm to work well on just this collection.
• Slide 40
• 40 Restaurant Example Learning Curve
• Slide 41
• 41 Decision Trees to Rules It is easy to derive a rule set froma decision tree: write a rule for each path in the decision treefrom the root to a leaf. In that rule the left-hand side is easilybuilt from the label of the nodes and the labels of the arcs. Theresulting rules set can be simplified: Let LHS be the left handside of a rule. Let LHS' be obtained from LHS by eliminating someconditions. We can certainly replace LHS by LHS' in this rule ifthe subsets of the training set that satisfy respectively LHS andLHS' are equal. A rule may be eliminated by using metaconditionssuch as "if no other rule applies".
• Slide 42