Timezone: »

 
Poster
Supervised learning through the lens of compression
Ofir David · Shay Moran · Amir Yehudayoff

Tue Dec 06 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #184
in Tuesday Posters »

This work continues the study of the relationship between sample compression schemes and statistical learning, which has been mostly investigated within the framework of binary classification. We first extend the investigation to multiclass categorization: we prove that in this case learnability is equivalent to compression of logarithmic sample size and that the uniform convergence property implies compression of constant size. We use the compressibility-learnability equivalence to show that (i) for multiclass categorization, PAC and agnostic PAC learnability are equivalent, and (ii) to derive a compactness theorem for learnability. We then consider supervised learning under general loss functions: we show that in this case, in order to maintain the compressibility-learnability equivalence, it is necessary to consider an approximate variant of compression. We use it to show that PAC and agnostic PAC are not equivalent, even when the loss function has only three values.

Keywords: Learning Theory · (Other) Classification · (Other) Regression · (Other) Machine Learning Topics
[ PDF] 

Author Information

Ofir David (Technion - Israel institute of technology)
Shay Moran (Technion - Israel institue of Technology)
Amir Yehudayoff (Technion - Israel institue of Technology)

More from the Same Authors