Machine learning Decision trees tutorial

machine learning decision tree algorithm, machine learning approaches decision tree,supervised machine learning decision tree pdf free download
Dr.BenjaminClark Profile Pic
Dr.BenjaminClark,United States,Teacher
Published Date:21-07-2017
Your Website URL(Optional)
CSE 473 CSE 473 Chapter 18 Chapter 18 M Ma ac ch hi in ne e L Le ea ar rn ni in ng g: : D De ec ci is si io on n T Tr re ee es s Why Learning? • Learning is essential for unknown environments e.g., when designer lacks omniscience • Learning is necessary in dynamic environments Agent can adapt to changes in environment not foreseen at design time • Learning is useful as a system construction method Expose the agent to reality rather than trying to approximate it through equations etc. • Learning modifies the agent's decision mechanisms to improve performance © CSE AI Faculty 2 1Types of Learning • Supervised learning: correct answers for each input is provided E.g., decision trees, backprop neural networks • Unsupervised learning: correct answers not given, must discover patterns in input data E.g., clustering, principal component analysis • Reinforcement learning: occasional rewards (or punishments) given E.g., Q learning, MDPs © CSE AI Faculty 3 Inductive learning A form of Supervised Learning: Learn a function from examples f is the target function. Examples are pairs (x, f(x)) Problem: learn a function (“hypothesis”) h such that h ≈ f (h approximates f as best as possible) given a training set of examples (This is a highly simplified model of real learning: Ignores prior knowledge Assumes examples are given) © CSE AI Faculty 4 2Inductive learning example • Construct h to agree with f on training set h is consistent if it agrees with f on all training examples • E.g., curve fitting (regression): x = Input data point (a training example) © CSE AI Faculty 5 Inductive learning example h = Straight line? © CSE AI Faculty 6 3Inductive learning example What about a quadratic function? What about this little fella? © CSE AI Faculty 7 Inductive learning example Finally, a function that satisfies all © CSE AI Faculty 8 4Inductive learning example But so does this one… © CSE AI Faculty 9 Ockham’s razor principle • Ockham’s razor: prefer the simplest hypothesis consistent with data Related to KISS principle (“keep it simple stupid”) Smooth blue function preferable over wiggly yellow one If noise known to exist in this data, even linear might be better (the lowest x might be due to noise) © CSE AI Faculty 10 5Example data for learning the concept “Good day for tennis” Day Outlook Humid Wind PlayTennis? d1 s h w n • Outlook = d2 s h s n sunny, d3 o h w y overcast, d4 r h w y rain d5 r n w y d6 r n s y d7 o n s y • Humidity = d8 s h w n high, normal d9 s n w y d10 r n w y • Wind = weak, d11 s n s y strong d12 o h s y d13 o n w y d14 r h s n © CSE AI Faculty 11 A Decision Tree for the Same Data PlayTennis? Leaves = classification Arcs = choice of value Outlook for parent attribute Sunny Rain Overcast Wind Humidity Yes Strong High Weak Normal Yes No Yes No Decision tree is equivalent to logic in disjunctive normal form PlayTennis ⇔ (Sunny ∧ Normal) ∨ Overcast ∨ (Rain ∧ Weak) © CSE AI Faculty 12 6Decision Trees Input: Description of an object or a situation through a set of attributes Output: a decision that is the predicted output value for the input Both input and output can be discrete or continuous Discrete-valued functions lead to classification problems Learning a continuous function is called regression © CSE AI Faculty 13 Example: Classification of Continuous Valued Inputs x2 3 Decision Tree 4 x1 © CSE AI Faculty 14 7Expressiveness • Decision trees can express any function of the input attributes. → • E.g., for Boolean functions, truth table row path to leaf: • Trivially, there is a consistent decision tree for any training set with one path to leaf for each example But most likely won't generalize to new examples • Prefer to find more compact decision trees © CSE AI Faculty 15 Learning Decision Trees Example: When should I wait for a table at a restaurant? Attributes (features) relevant to Wait? decision: 1. Alternate: is there an alternative restaurant nearby? 2. Bar: is there a comfortable bar area to wait in? 3. Fri/Sat: is today Friday or Saturday? 4. Hungry: are we hungry? 5. Patrons: number of people in the restaurant (None, Some, Full) 6. Price: price range (, , ) 7. Raining: is it raining outside? 8. Reservation: have we made a reservation? 9. Type: kind of restaurant (French, Italian, Thai, Burger) 10. WaitEstimate: estimated waiting time (0-10, 10-30, 30-60, 60) © CSE AI Faculty 16 8Example Decision tree A decision tree for Wait? based on personal “rules of thumb”: © CSE AI Faculty 17 Input Data for Learning • Past examples where I did/did not wait for a table: • Classification of examples is positive (T) or negative (F) © CSE AI Faculty 18 9Decision Tree Learning • Aim: find a small tree consistent with training examples • Idea: (recursively) choose "most significant" attribute as root of (sub)tree © CSE AI Faculty 19 Choosing an attribute to split on • Idea: a good attribute splits the examples into subsets that are (ideally) "all positive" or "all negative" • Patrons? is a better choice © CSE AI Faculty 20 10Next Time • How to choose attributes to split on? Using information theory and entropy • The more, the merrier (and better) – combining classifiers Ensemble learning via boosting © CSE AI Faculty 21 11

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.