More Related Content
What's hot (20)
Similar to Induction and Decision Tree Learning (Part 1) (20)
More from butest (20)
Induction and Decision Tree Learning (Part 1)
- 1. COSC 4350 and 5350 Artificial Intelligence Induction and Decision Tree Learning (Part 1) Dr. Lappoon R. Tang
- 2. Overview Types of learning History of machine learning Inductive learning Decision tree learning
- 3. Readings R & N: Chapter 18 Sec 18.1 Sec 18.2 Sec 18.3, skim through “ Noise and overfitting” “ Broadening the applicability of decision trees”
- 4. What is Machine Learning? “ Any process by which a system improves performance” – Herbert Simon “ The ability of a device to improve its performance based on its past performance” – www.atis.org
- 5. What is Machine Learning? What is the task? Classification Medical diagnosis Identification of gene functions based on sequence information Recognition of speech, handwritten letters, human faces, and so on Problem solving Planning (e.g. using case based learning) Solving calculus problems (e.g. using case based learning) Playing checkers/chess/backgamon Balancing a pole (e.g. using reinforcement learning) Driving a car (e.g. using reinforcement learning)
- 6. What is Machine Learning? How is performance measured? Classification accuracy Solution correctness and quality Computational efficiency of the learning process
- 7. Why Study Learning? Automated/semi-automated development of intelligent systems Develop systems that are too difficult or impossible to construct manually because they require specific detailed knowledge or skills tuned to a particular complex task – knowledge acquisition bottleneck e.g. a machine translation program Develop systems that can automatically adapt and customize themselves to the needs of individual users through experience – coping with an unknown environment e.g. a personalized email filter
- 8. Why Study Learning? (Cont’d) Time is right Initial algorithms and theory in place Growing amounts of online data Computational power is available A more controversial reason: perhaps, we can gain insights in how human beings learn by researching in learning mechanisms
- 9. Different Types of Learning There are different kinds of learning methods – a particular type of learning is used depending on the availability of training data Training data != data A piece of training data is annotated with its class (positive example or negative example) Data are simply naturally available “raw” data (e.g. a particular example without knowing its classification)
- 10. Different Types of Learning (Cont’d) Supervised learning training data is available and is given to the learning mechanism (i.e. the learner) Unsupervised learning only data is available but not training data, and raw data is given to the learner Reinforcement learning a feedback signal from the learner’s environment is available to the learner’s decision, the learner can use the feedback signal to adjust its own behavior Example: when we didn’t behave as a kid, our parent gave us a “feedback signal” like physical discipline to help us correct our mistakes
- 11. Brief History of Machine Learning 1940’s: Perceptrons 1950’s: Samuels checker player 1960’s: Pattern recognition 1970’s: “Symbolic machine learning” – learning of rule based classifiers 1980’s: Continued progress on rule based classifiers (decision tree and rule learning); Resurgence of neural networks; Development of a formal framework of learning theory (PAC learning) 1990’s: Data mining; Reinforcement learning; New learning paradigms (Inductive Logic Programming, Ensemble learning); Learning the structure of a Bayesian network 2000’s: Continued progress on existing areas; Using unlabeled data in learning (e.g. co-training, active learning for selective sampling); Scaling up supervised learning to handle large training sets; Combining supervised and unsupervised learning methods; …
- 12. Inductive learning Simplest form: learn a function from examples Idea: Given: f : the target function Examples of f where an example is a pair ( x , f(x) ) (training data) and examples might have noise Problem: find a hypothesis h such that h ≈ f ( h is mostly consistent with f ) (This is a highly simplified model of real learning: Ignores prior knowledge Assumes that there are no missing examples)
- 13. Inductive learning method Construct/adjust h to agree with f on training set ( h is a consistent hypothesis if it agrees with f on all examples) E.g., curve fitting: Outlier / Noise
- 14. Inductive learning method (cont’d) Construct/adjust h to agree with f on training set ( h is consistent if it agrees with f on all examples) E.g., curve fitting:
- 15. Inductive learning method (cont’d) Construct/adjust h to agree with f on training set ( h is consistent if it agrees with f on all examples) E.g., curve fitting:
- 16. Inductive learning method (cont’d) Construct/adjust h to agree with f on training set ( h is consistent if it agrees with f on all examples) E.g., curve fitting:
- 17. Inductive learning method (cont’d) Construct/adjust h to agree with f on training set ( h is consistent if it agrees with f on all examples) E.g., curve fitting:
- 18. Inductive learning method: Ockham’s Razor Construct/adjust h to agree with f on training set ( h is consistent if it agrees with f on all examples) E.g., curve fitting: Ockham’s razor: simplest hypothesis has the most explanative power Hypothesis 2 is the simplest one that fits the data “reasonably” well Complexity of a hypothesis can be measure, for instance in this case, by the degree of the polynomial 1 2 3 4