INTRODUCTION MACHINE LEARNING - Stanford AI Lab

1 INTRODUCTIONTOMACHINE LEARNINGAN EARLY DRAFT OF A PROPOSEDTEXTBOOKNils J. NilssonRobotics LaboratoryDepartment of Computer ScienceStanford UniversityStanford, CA 94305e-mail: 3, 1998 Copyrightc 2005 Nils J. NilssonThis material may not be copied, reproduced, or distributed without thewritten permission of the copyright INTRODUCTION .. is MACHINE LEARNING ? .. of MACHINE LEARNING .. of MACHINE LEARNING .. LEARNING Input-Output Functions .. of LEARNING .. Vectors .. Regimes .. Evaluation .. LEARNING Requires Bias .. Sample Applications .. Sources .. Bibliographical and Historical Remarks .. 132 Boolean Representation .. Algebra .. Representations .. Classes of Boolean Functions.

2 And Clauses .. Functions .. Functions .. Lists .. and Voting Functions .. Separable Functions .. Summary .. Bibliographical and Historical Remarks .. 25iii3 Using Version Spaces for Version Spaces and Mistake Bounds .. Version Graphs .. LEARNING as Search of a Version Space .. The Candidate Elimination Method .. Bibliographical and Historical Remarks .. 344 Neural Threshold Logic Units .. and Geometry .. Cases of Linearly Separable Functions .. Training of a TLU .. Space .. Widrow-Hoff Procedure .. a TLU on Non-Linearly-Separable Training Linear Machines .. Networks of TLUs .. and Examples.

3 Linear Machines .. Networks .. Training Feedforward Networks by Backpropagation .. Backpropagation Method .. Weight Changes in the Final Layer .. Changes to the Weights in Intermediate Layers on Backprop .. Application: Steering a Van .. Synergies Between Neural Network and Knowledge-Based Methods Bibliographical and Historical Remarks .. 615 Statistical Using Statistical Decision Theory .. and General Method .. (or Normal) Distributions .. Independent Binary Components .. LEARNING Belief Networks .. Nearest-Neighbor Methods .. Bibliographical and Historical Remarks .. 72iv6 Decision Definitions .. Supervised LEARNING of Univariate Decision Trees.

4 The Type of Test .. Uncertainty Reduction to Select Tests .. Attributes .. Networks Equivalent to Decision Trees .. Overfitting and Evaluation .. Methods .. Overfitting in Decision Trees .. Length Methods .. in Data .. The Problem of Replicated Subtrees .. The Problem of Missing Attributes .. Comparisons .. Bibliographical and Historical Remarks .. 877 Inductive Logic Notation and Definitions .. A Generic ILP Algorithm .. An Example .. Inducing Recursive Programs .. Choosing Literals to Add .. Relationships Between ILP and Decision Tree Induction .. Bibliographical and Historical Remarks.

5 1048 Computational LEARNING Notation and Assumptions for PAC LEARNING Theory .. PAC LEARNING .. Fundamental Theorem .. Properly PAC-Learnable Classes .. The Vapnik-Chervonenkis Dimension .. Dichotomies .. More General Capacity Result .. Facts and Speculations About the VC Dimension . VC Dimension and PAC LEARNING .. Bibliographical and Historical Remarks .. 118v9 Unsupervised What is Unsupervised LEARNING ? .. Clustering Methods .. Method Based on Euclidean Distance .. Method Based on Probabilities .. Hierarchical Clustering Methods .. Method Based on Euclidean Distance .. Method Based on Probabilities .. Bibliographical and Historical Remarks.

6 13010 Temporal-Difference Temporal Patterns and Prediction Problems .. Supervised and Temporal-Difference Methods .. Incremental Computation of the ( W)i.. An Experiment with TD Methods .. Theoretical Results .. Intra-Sequence Weight Updating .. An Example Application: TD-gammon .. Bibliographical and Historical Remarks .. 14111 Delayed-Reinforcement The General Problem .. An Example .. Temporal Discounting and Optimal Policies .. Discussion, Limitations, and Extensions of Q- LEARNING .. An Illustrative Example .. Using Random Actions .. Generalizing Over Inputs .. Partially Observable States .. Scaling Problems .. Bibliographical and Historical Remarks.

7 155vi12 Explanation-Based Deductive LEARNING .. Domain Theories .. An Example .. Evaluable Predicates .. More General Proofs .. Utility of EBL .. Applications .. Macro-Operators in Planning .. LEARNING Search Control Knowledge .. Bibliographical and Historical Remarks .. 168viiviiiPrefaceThese notes are in the process of becoming a textbook. The process is quiteunfinished, and the author solicits corrections, criticisms, and suggestions fromstudents and other readers. Although I have tried to eliminate errors, some un-doubtedly remain caveat lector. Many typographical infelicities will no doubtpersist until the final version. More material has yet to be added. Please letSome of my plans for additions andother reminders are mentioned inmarginal have your suggestions about topics that are too important to be left hope that future versions will cover Hopfield nets, Elman nets and other re-current nets, radial basis functions, grammar and automata LEARNING , geneticalgorithms, and Bayes I am also collecting exercises and projectsuggestions which will appear in future intention is to pursue a middle ground between a theoretical textbookand one that focusses on applications.

8 The book concentrates on the importantideasin MACHINE LEARNING . I do not give proofs of many of the theorems that Istate, but I do give plausibility arguments and citations to formal proofs. And, Ido not treat many matters that would be of practical importance in applications;the book is not a handbook of MACHINE LEARNING practice. Instead, my goal isto give the reader sufficient preparation to make the extensive literature onmachine LEARNING in my Stanford courses on MACHINE LEARNING have already madeseveral useful suggestions, as have my colleague, Pat Langley, and my teachingassistants, Ron Kohavi, Karl Pfleger, Robert Allen, and Lise What is MACHINE LEARNING ? LEARNING , like intelligence, covers such a broad range of processes that it is dif-ficult to define precisely.

9 A dictionary definition includes phrases such as togain knowledge, or understanding of, or skill in, by study, instruction, or expe-rience, and modification of a behavioral tendency by experience. Zoologistsand psychologists study LEARNING in animals and humans. In this book we fo-cus on LEARNING in machines. There are several parallels between animal andmachine LEARNING . Certainly, many techniques in MACHINE LEARNING derive fromthe efforts of psychologists to make more precise their theories of animal andhuman LEARNING through computational models. It seems likely also that theconcepts and techniques being explored by researchers in MACHINE LEARNING mayilluminate certain aspects of biological regards machines, we might say, very broadly, that a MACHINE learnswhenever it changes its structure, program, or data (based on its inputs or inresponse to external information) in such a manner that its expected futureperformance improves.

10 Some of these changes, such as the addition of a recordto a data base, fall comfortably within the province of other disciplines and arenot necessarily better understood for being called LEARNING . But, for example,when the performance of a speech-recognition MACHINE improves after hearingseveral samples of a person s speech, we feel quite justified in that case to saythat the MACHINE has LEARNING usually refers to the changes in systems that perform tasksassociated withartificial intelligence (AI). Such tasks involve recognition, diag-nosis, planning, robot control, prediction, etc. The changes might be eitherenhancements to already performing systems orab initiosynthesis of new sys-tems. To be slightly more specific, we show the architecture of a typical AI12 CHAPTER 1.