CS485 Lecture Notes - Lecture 7: Vc Dimension, Approximation Error, Infant

• School: University of Waterloo
• Department: Computer Science
• Course: CS485
• Professor: Shai Ben- David

Document Summary

Pac learn the sample size of all functions over. A be a pac learner that is guaranteed to. Lp i als ) ) entity ( ( hdte. Hinit be the class of initial segments of. Let ht eh be a perfect predictor and pick a t s . t. Note that if the sample s hits both intervals. , he ) ( ermhis )) e e a[#p ]b. Pr [ l ( d. he ) ( ermisd > e) { ha : a e [ 0,1 ] So every sample hs is a s hs has. But regardless of how legal output of large s. L ( d. 1) ( hs )= 1. Chorwnenkis dimension ( vc - dimension ) is a combinational parameter that reflects how learnable a class is. H say be a class of functions from some domain. Set of of all axis aligned rectangles . ten.