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