《Foundation of Machine Learning [Part02]》.pdf

Foundations of Machine Learning Lecture 2 Mehryar Mohri Courant Institute and Google Research mohri@cims.nyu.edu PAC Learning Concentration Bounds Motivation Some computational learning questions • What can be learned efficiently? • What is inherently hard to learn? • A general model of learning? Complexity • Computational complexity: time and space. • Sample complexity: amount of training data needed to learn successfully. • Mistake bounds: number of mistakes before learning successfully. Mehryar Mohri - Foundations of Machine Learning page 3 This lecture PAC Model Sample complexity - finite hypothesis space - consistent case Sample complexity - finite hypothesis space - inconsistent case Concentration bounds Mehryar Mohri - Foundations of Machine Learning page 4 Definitions X : set of all possible instances or examples, e.g., the set of all men and women characterized by their height and weight. c : X → {0, 1}: the target concept to learn, e.g., c(x)=0 for a male,c(x)=1for a female example. C : concept class, a set of target concepts c. D : target distribution, a fixed probability distribution overX. Training and test examples are drawn according toD. Mehryar Mohri - Foundations of Machine Learning page 5 Definitions S: training sample. H: set of concept hypotheses, e.g., the set of all linear classifiers. The learning algorithm receives sample S and selects a hypothesis h from H approximating c. S Mehryar Mohri - Foundations