Transcription of Foundations of Machine Learning
1 Foundations of Machine LearningAdaptive Computation and Machine LearningThomas Dietterich, EditorChristopher Bishop, David Heckerman, Michael Jordan, and Michael Kearns,Associate EditorsA complete list of books published in The Adaptive Computations and MachineLearning series appears at the back of this of Machine LearningMehryar Mohri, Afshin Rostamizadeh, and Ameet TalwalkarThe MIT PressCambridge, MassachusettsLondon, Englandc 2012 Massachusetts Institute of TechnologyAll rights reserved. No part of this book may be reproduced in any form by anyelectronic or mechanical means (including photocopying, recording, or informationstorage and retrieval) without permission in writing from the Press books may be purchased at special quantity discounts for business orsales promotional use.
2 For information, please email write to Special Sales Department, The MIT Press, 55 Hayward Street, Cam-bridge, MA book was set in LATEX by the authors. Printed and bound in the United Statesof of Congress Cataloging-in-Publication DataMohri, of Machine Learning / Mehryar Mohri, Afshin Rostamizadeh, andAmeet cm. - (Adaptive computation and Machine Learning series)Includes bibliographical references and 978-0-262-01825-8 (hardcover : alk. paper) 1. Machine Learning . 2. Computeralgorithms. I. Rostamizadeh, Afshin. II. Talwalkar, Ameet. III.
3 1-dc23201200724910987654321 ContentsPrefacexi1 Learningscenarios .. Outline .. 82 The PAC Learning Guaranteesforfinitehypothesissets Guaranteesforfinitehypothesissets Generalities .. Bayeserrorandnoise .. Exercises .. 293 Rademacher Complexity and Rademachercomplexity .. Growthfunction .. Exercises .. 554 Support Vector SVMs separablecase .. Primaloptimizationproblem .. Dualoptimizationproblem .. SVMs Primaloptimizationproblem.
4 Dualoptimizationproblem .. Exercises .. 845 Kernel Positivedefinitesymmetrickernels .. Definitions .. Kernel-basedalgorithms .. Learningguarantees .. Sequencekernels .. Weightedtransducers .. Rationalkernels .. Exercises .. 1166 AdaBoost .. Boundontheempiricalerror .. Relationshipwithlogisticregression .. Theoreticalresults .. VC-dimension-basedanalysis .. Margin-basedanalysis .. Marginmaximization .. Exercises.
5 1427 On-Line MistakeboundsandHalvingalgorithm .. Weightedmajorityalgorithm .. Randomizedweightedmajorityalgorithm .. Winnowalgorithm .. On-linetobatchconversion .. Exercises .. 1768 Multi-Class Multi-classclassificationproblem .. Generalizationbounds .. Aggregated multi-class One-versus-one .. Error-correctioncodes .. Structuredpredictionalgorithms .. Exercises .. 2079 Theproblemofranking .. Generalizationbound .. RankingwithSVMs.
6 RankBoost .. Boundontheempiricalerror .. Marginboundforensemblemethodsinranking .. Boostinginbipartiteranking .. AreaundertheROCcurve .. Preference-basedsetting .. Deterministicalgorithm .. Extensiontootherlossfunctions .. Exercises .. 23410 .. Finitehypothesissets .. Linearregression .. Supportvectorregression .. Lasso .. Groupnormregressionalgorithms .. On-lineregressionalgorithms .. 26311 Algorithmic .. Application to regression algorithms: SVR and KRR .. Applicationtoclassificationalgorithms:SV Ms.
7 27712 Dimensionality .. (KPCA) .. Isomap .. Locallylinearembedding(LLE) .. 29013 Learning Automata and .. Passivelearning .. Learningwithqueries .. Learningautomatawithqueries .. Learningreversibleautomata .. 31014 Reinforcement .. Optimalpolicy .. Valueiteration .. Linearprogramming .. Stochasticapproximation .. TD(0)algorithm .. SARSA .. TD( )algorithm .. 337xConclusion339A Linear Algebra Vectorsandnorms .. Singularvaluedecomposition .. Symmetricpositivesemidefinite(SPSD) 346B Convex Differentiationandunconstrainedoptimizat ion.
8 Convexity .. Constrainedoptimization .. 357C Probability Conditionalprobabilityandindependence .. Expectation, Markov s inequality, and moment-generating VarianceandChebyshev sinequality .. 365D Concentration Hoeffding sinequality .. McDiarmid sinequality .. Binomialdistribution:Slud sinequality .. Exercises .. 377E book is a general introduction to Machine Learning that can serve as a textbookfor students and researchers in the field. It covers fundamental modern topics inmachine Learning while providing the theoretical basis and conceptual tools neededfor the discussion and justification of algorithms.
9 It also describes several key aspectsof the application of these have aimed to present the most novel theoretical tools and concepts whilegiving concise proofs, even for relatively advanced results. In general, wheneverpossible, we have chosen to favor succinctness. Nevertheless, we discuss some crucialcomplex topics arising in Machine Learning and highlight several open researchquestions. Certain topics often merged with others or treated with insufficientattention are discussed separately here and with more emphasis: for example, adifferent chapter is reserved for multi-class classification, ranking, and we cover a very wide variety of important topics in Machine Learning , wehave chosen to omit a few important ones, including graphical models and neuralnetworks, both for the sake of brevity and because of the current lack of solidtheoretical guarantees for some book is intended for students and researchers in Machine Learning , statisticsand other related areas.
10 It can be used as a textbook for both graduate and advancedundergraduate classes in Machine Learning or as a reference text for a researchseminar. The first three chapters of the book lay the theoretical foundation for thesubsequent material. Other chapters are mostly self-contained, with the exceptionof chapter 5 which introduces some concepts that are extensively used in laterones. Each chapter concludes with a series of exercises, with full solutions reader is assumed to be familiar with basic concepts in linear algebra,probability, and analysis of algorithms.
