INTRODUCTION TO MACHINE LEARNING AN EARLY DRAFT OF A PROPOSED TEXTBOOK Nils J. Nilsson Robotics Laboratory Department of Computer Science Stanford University Stanford, CA 94305 e-mail:
[email protected] September 26, 1996 c 1996 Nils J. Nilsson Copyright This material may not be copied, reproduced, or distributed without the written permission of the copyright holder. It is being made available on the world-wide web in draft form to students, faculty, and researchers solely for the purpose of preliminary evaluation. Contents 1 Preliminaries 1.1 Introduction 1.1.1 What is Machine Learning? 1.1.2 Wellsprings of Machine Learning 1.1.3 Varieties of Machine Learning 1.2 Learning Input-Output Functions 1.2.1 Types of Learning 1.2.2 Input Vectors 1.2.3 Outputs 1.2.4 Training Regimes 1.2.5 Noise 1.2.6 Performance Evaluation 1.3 Learning Requires Bias 1.4 Sample Applications 1.5 Sources 1.6 Bibliographical and Historical Remarks 1 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2 Boolean Functions 2.1 Representation 2.1.1 Boolean Algebra 2.1.2 Diagrammatic Representations 2.2 Classes of Boolean Functi