Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Learning: Generalization and Simplification of Binary-labeled Classes
event speaker icon
Shay Moran (CS, Technion)
event date icon
Wednesday, 16.12.2015, 12:30
event location icon
Taub 201
Generalization and simplification are two basic facets of learning. Learning theory gives several mathematical manifestations of these facets. We will present two of these:

(i) A generalization model: Probably Approximately Correct learning [Vapnik-Chervonenkis ’71, Valiant ’84], and
(ii) A simplification model: Sample compression schemes [Littlestone-Warmuth ’86].

Littlestone and Warmuth have shown that for these mathematical formalizations, the ability to simplify implies the ability to generalize, and asked whether the other direction holds. We will see an affirmative answer to this question.

No knowledge in machine learning will be assumed in the talk.

Based on a joint work with Amir Yehudayoff.