LEARNING
FROM
DATA
The book website AMLbook. com
contains supporting material for
instructors and readers.
LEARNING FROM DATA
A SHORT COURSE
Yaser S. Abu-Mostafa
California Institute of Technology
Malik Magdon-Ismail
Rensselaer Polytechnic Institute
Hsuan-Tien Lin
National Taiwan University
AMLbook.com
Yaser S. Abu-1/fostafa
Departments of Electrical Engineering
and Computer Science
California Institute of Technology
Pasadena, CA 91125, USA
yaser©caltech.edu
Malik Magdon-Ismail
Department of Computer Science
Rensselaer Polytechnic Institute
Troy, NY 12180, USA
magdon@cs.rpi.edu
Hsuan-Tien Lin
Department of Computer Science
and Information Engineering
National Taiwan University
Taipei, 106, Taiwan
htlin©csie.ntu.edu.tw
ISBN 10: 1-60049-006-9
ISBN 13:978-1-60049-006-4
@2012 Yaser S. Abu-Mostafa, Malik Magdon-Ismail, Hsuan-Tien Lin.
1.10
All rights reserved. This work may not be translated or copied in whole or in part
without the written permission of the authors. No part of this publication may
be reproduced, stored in a retrieval system, or transmitted in any form or by any
means-electronic, mechanical, photocopying, scanning, or otherwise-without prior
written permission of the authors, except as permitted under Section 107 or 108 of
the 1976 United States Copyright Act.
Limit of Liability /Disclaimer of Warranty: While the authors have used their best
efforts in preparing this book, they make no representation or warranties with re
spect to the accuracy or completeness of the contents of this book and specifically
disclaim any implied warranties of merchantability or fitness for a particular purpose.
No warranty may be created or extended by sales representatives or written sales
materials. The advice and strategies contained herein may not be suitable for your
situation. You should consult with a professional where appropriate. The authors
shall not be liable for any loss of profit or any other commercial damages, including
but not limited to special, incidental, consequential, or other damages.
The use in this publication of tradenames, trademarks, service marks, and similar
terms, even if they are not identified as such, is not to be taken as an expression of
opinion as to whether or not they are subject to proprietary rights.
This book was typeset by the authors and was printed and bound in the United
States of America.
To our teachers) and to our students
Preface
This book is designed for a short course on machine learning. It is a short
course, not a hurried course. From over a decade of teaching this material, we
have distilled what we believe to be the core topics that every student of the
subject should know. We chose the title 'learning from data' that faithfully
describes what the subject is about, and made it a point to cover the topics in
a story-like fashion. Our hope is that the reader can learn all the fundamentals
of the subject by reading the book cover to cover.
Learning from data has distinct theoretical and practical tracks. If you
read two books that focus on one track or the other, you may feel that you
are reading about two different subjects altogether. In this book, we balance
the theoretical and the practical, the mathematical and the heuristic. Our
criterion for inclusion is relevance. Theory that establishes the conceptual
framework for learning is included, and so are heuristics that impact the per
formance of real learning systems. Strengths and weaknesses of the different
parts are spelled out. Our philosophy is to say it like it is: what we know,
what we don't know, and what we partially know.
The book can be taught in exactly the order it is presented. The notable
exception may be Chapter 2, which is the most theoretical chapter of the book.
The theory of generalization that this chapter covers is central to learning
from data, and we made an effort to make it accessible to a wide readership.
However, instructors who are more interested in the practical side may skim
over it, or delay it until after the practical methods of Chapter 3 are taught.
You will notice that we included exercises (in gray boxes) throughout the
text. The main purpose of these exercises is to engage the reader and enhance
understanding of a particular topic being covered. Our reason for separating
the exercises out is that they are not crucial to the logical flow. Nevertheless,
they contain useful information, and we strongly encourage you to read them,
even if you don't do them to completion. Instructors may find some of the
exercises appropriate as 'easy' homework problems, and we also provide ad
ditional problems of varying difficulty in the Problems section at the end of
each chapter.
To help instructors with preparing their lectures based on the book, we
provide supporting material on the book's website (AMLbook. corn). There is
also a forum that covers additional topics in learning from data. We will
vii
PREFACE
discuss these further in the Epilogue of this book.
Acknowledgment (in alphabetical order for each group): We would like to
express our gratitude to the alumni of our Learning Systems Group at Caltech
who gave us detailed expert feedback: Zehra Cataltepe, Ling Li, Amrit Pratap,
and Joseph Sill. We thank the many students and colleagues who gave us useful
feedback during the development of this book, especially Chun-Wei Liu. The
Caltech Library staff, especially Kristin Buxton and David McCaslin, have
given us excellent advice and help in our self-publishing effort. We also thank
Lucinda Acosta for her help throughout the writing of this book.
Last, but not least, we would like to thank our families for their encourage
ment, their support, and most of all their patience as they endured the time
demands that writing a book has imposed on us.
Yaser S. Abu-Mostafa, Pasadena, California.
Malik Magdon-Ismail, Troy, New York.
Hsuan-Tien Lin, Taipei, Taiwan.
March, 2012.
viii