Miroslav Kubat An Introduction to Machine Learning An Introduction to Machine Learning Miroslav Kubat An Introduction to Machine Learning 123 Miroslav Kubat Department of Electrical and Computer Engineering University of Miami Coral Gables, FL, USA ISBN 978-3-319-20009-5 ISBN 978-3-319-20010-1 (eBook) DOI 10.1007/978-3-319-20010-1 Library of Congress Control Number: 2015941486 Springer Cham Heidelberg New York Dordrecht London © Springer International Publishing Switzerland 2015 This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use.
The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, express or implied, with respect to the material contained herein or for any errors or omissions that may have been made. Printed on acid-free paper Springer International Publishing AG Switzerland is part of Springer Science+Business Media (www.com) To my wife, Verunka Contents 1 A Simple Machine-Learning Task .1 Training Sets and Classifiers .2 Minor Digression: Hill-Climbing Search .3 Hill Climbing in Machine Learning .4 The Induced Classifier’s Performance.5 Some Difficulties with Available Data .6 Summary and Historical Remarks .7 Solidify Your Knowledge. 16 2 Probabilities: Bayesian Classifiers .1 The Single-Attribute Case .2 Vectors of Discrete Attributes .3 Probabilities of Rare Events: Exploiting the Expert’s Intuition .4 How to Handle Continuous Attributes .5 Gaussian “Bell” Function: A Standard pdf .6 Approximating PDFs with Sets of Gaussians .7 Summary and Historical Remarks .8 Solidify Your Knowledge.
40 3 Similarities: Nearest-Neighbor Classifiers .1 The k-Nearest-Neighbor Rule .3 Irrelevant Attributes and Scaling Problems .5 Weighted Nearest Neighbors .6 Removing Dangerous Examples.7 Removing Redundant Examples.8 Summary and Historical Remarks .9 Solidify Your Knowledge. 62 vii viii Contents 4 Inter-Class Boundaries: Linear and Polynomial Classifiers .2 The Additive Rule: Perceptron Learning .3 The Multiplicative Rule: WINNOW .4 Domains with More than Two Classes .6 Specific Aspects of Polynomial Classifiers .7 Numerical Domains and Support Vector Machines .8 Summary and Historical Remarks .9 Solidify Your Knowledge. 87 5 Artificial Neural Networks .1 Multilayer Perceptrons as Classifiers .2 Neural Network’s Error .3 Backpropagation of Error .4 Special Aspects of Multilayer Perceptrons.6 Radial Basis Function Networks .7 Summary and Historical Remarks .8 Solidify Your Knowledge .1 Decision Trees as Classifiers.2 Induction of Decision Trees .3 How Much Information Does an Attribute Convey? .4 Binary Split of a Numeric Attribute .6 Converting the Decision Tree into Rules .7 Summary and Historical Remarks .8 Solidify Your Knowledge. 133 7 Computational Learning Theory .2 Examples of PAC Learnability .3 Some Practical and Theoretical Consequences .4 VC-Dimension and Learnability.5 Summary and Historical Remarks .6 Exercises and Thought Experiments.
149 8 A Few Instructive Applications .2 Oil-Spill Recognition .4 Brain-Computer Interface .7 Summary and Historical Remarks .8 Exercises and Thought Experiments. 170 Contents ix 9 Induction of Voting Assemblies .3 Adaboost: Practical Version of Boosting .4 Variations on the Boosting Theme.5 Cost-Saving Benefits of the Approach .6 Summary and Historical Remarks .7 Solidify Your Knowledge. 188 10 Some Practical Aspects to Know About.2 Imbalanced Training Sets .3 Context-Dependent Domains .4 Unknown Attribute Values .7 Summary and Historical Remarks .8 Solidify Your Knowledge .1 Basic Performance Criteria .2 Precision and Recall.3 Other Ways to Measure Performance .4 Performance in Multi-label Domains.5 Learning Curves and Computational Costs .6 Methodologies of Experimental Evaluation .7 Summary and Historical Remarks .8 Solidify Your Knowledge .2 Benefiting from the Normal Distribution .4 Statistical Evaluation of a Classifier .5 Another Kind of Statistical Evaluation .6 Comparing Machine-Learning Techniques .7 Summary and Historical Remarks .8 Solidify Your Knowledge. 252 13 The Genetic Algorithm.1 The Baseline Genetic Algorithm .2 Implementing the Individual Modules .3 Why it Works .4 The Danger of Premature Degeneration.5 Other Genetic Operators .6 Some Advanced Versions .7 Selections in k-NN Classifiers .8 Summary and Historical Remarks .9 Solidify Your Knowledge .1 How to Choose the Most Rewarding Action .2 States and Actions in a Game .3 The SARSA Approach .4 Summary and Historical Remarks .5 Solidify Your Knowledge.
291 Introduction Machine learning has come of age. And just in case you might think this is a mere platitude, let me clarify. The dream that machines would one day be able to learn is as old as computers themselves, perhaps older still. For a long time, however, it remained just that: a dream.
True, Rosenblatt’s perceptron did trigger a wave of activity, but in retrospect, the excitement has to be deemed short-lived. As for the attempts that followed, these fared even worse; barely noticed, often ignored, they never made a breakthrough— no software companies, no major follow-up research, and not much support from funding agencies. Machine learning remained an underdog, condemned to live in the shadow of more successful disciplines. The grand ambition lay dormant.
And then it all changed. A group of visionaries pointed out a weak spot in the knowledge-based systems that were all the rage in the 1970s’ artificial intelligence: where was the “know- ledge” to come from? The prevailing wisdom of the day insisted that it should take the form of if-then rules put together by the joint effort of engineers and field experts. Practical experience, though, was unconvincing. Experts found it difficult to communicate what they knew to engineers.
Engineers, in turn, were at a loss as to what questions to ask, and what to make of the answers. A few widely publicized success stories notwithstanding, most attempts to create a knowledge base of, say, tens of thousands of such rules proved frustrating. The proposition made by the visionaries was both simple and audacious. If it is so hard to tell a machine exactly how to go about a certain problem, why not provide the instruction indirectly, conveying the necessary skills by way of examples from which the computer will—yes—learn! Of course, this only makes sense if we can rely on the existence of algorithms to do the learning.
This was the main difficulty. As it turned out, neither Rosenblatt’s perceptron nor the techniques developed after it were very useful. But the absence of the requisite machine-learning techniques was not an obstacle; rather, it was a challenge that inspired quite a few brilliant minds. The idea of endowing computers with learning skills opened new horizons and created a large amount of excitement.
The world was beginning to take notice. xi xii Introduction The bombshell exploded in 1983. Machine Learning: The AI Approach1 was a thick volume of research papers which proposed the most diverse ways of addressing the great mystery. Under their influence, a new scientific discipline was born—virtually overnight.
Three years later, a follow-up book appeared, then another. A soon-to-become-prestigious scientific journal was founded. Annual conferences of great repute were launched. And dozens, perhaps hundreds, of doctoral dissertations were submitted and successfully defended.
In this early stage, the question was not only how to learn but also what to learn and why. In retrospect, those were wonderful times, so creative that they deserve to be remembered with nostalgia. It is only to be regretted that so many great thoughts later came to be abandoned. Practical needs of realistic applications got the upper hand, pointing to the most promising avenues for further efforts.
After a period of enchantment, concrete research strands crystallized: induction of the if-then rules for knowledge-based systems; induction of classifiers, programs capable of improving their skills based on experience; automatic fine-tuning of Prolog programs; and some others. So many were the directions that some leading personalities felt it necessary to try to steer further development by writing monographs, some successful, others less so. An important watershed was Tom Mitchell’s legendary textbook.2 This summa- rized the state of the art of the field in a format appropriate for doctoral students and scientists alike. One by one, universities started offering graduate courses that were usually built around this book.
Meanwhile, the research methodology become more systematic, too. A rich repository of machine-leaning test-beds was created, making it possible to compare the performance or learning algorithms. Statistical methods of evaluation became widespread. Public-domain versions of most popular programs were made available.
The number of scientists dealing with this discipline grew to thousands, perhaps even more. Now we have reached the stage where a great many universities are offering machine learning as an undergraduate class. This is quite a new situation. As a rule, these classes call for a different kind of textbook.
Apart from mastering the baseline techniques, the future engineers need to develop a good grasp of the strengths and weaknesses of alternative approaches; they should be aware of the peculiarities and idiosyncrasies of different paradigms. Above all, they must understand the circumstances under which some techniques succeed and others fail. Only then will they be able to make the right choices when addressing concrete applications. A textbook that is to provide all of the above should contain less mathematics, but a lot of practical advice.
These then are the considerations that have dictated the size, structure, and style of a teaching text meant to provide the material for a one-semester introductory course. Mitchell, Machine Learning, McGraw-Hill, 1997. Introduction xiii The first problem is the choice of material. At a time when high-tech companies are establishing machine-learning groups, universities have to provide the students with such knowledge, skills, and understanding that are relevant to the current needs of the industry.
For this reason, preference has been given to Bayesian classifiers, nearest-neighbor classifiers, linear and polynomial classifiers, decision trees, the fundamentals of the neural networks, and the principle of the boosting algorithms. A significant space has been devoted to certain typical aspects of concrete engineer- ing applications. When applied to really difficult tasks, the baseline techniques are known to behave not exactly the same way they do in the toy domains employed by the instructor. One has to know what to expect.
The book consists of 14 chapters, each covering one major topic. The chapters are divided into sections, each devoted to one critical problem. The student is advised to proceed to the next section only after having answered the set of 2–4 “control questions” at the end of the previous section. These questions are here to help the student decide whether he or she has mastered the given material.
If not, it is necessary to return to the previous text. As they say, only practice makes perfect. This is why at the end of each chapter are exercises to encourage the necessary practicing. Deeper insight into the diverse aspects of the material will then be gained by going through the thought experiments that follow.
These are more difficult, but it is only through hard work that an engineer develops the right kind of understanding. The acquired knowledge is then further solidified by suggested computer projects. Programming is important, too. Nowadays, everybody is used to downloading the requisite software from the web.
This shortcut, however, is not recommended to the student of this book. It is only by being forced to flesh out all the details of a computer program that you learn to appreciate all the subtle points of the machine-learning techniques presented here. Chapter 1 A Simple Machine-Learning Task You will find it difficult to describe your mother’s face accurately enough for your friend to recognize her in a supermarket. But if you show him a few of her photos, he will immediately spot the tell-tale traits he needs.