Mathematical Computer Science Seminar
Hunter Chase
UIC
Model-theoretic techniques in query learning
Abstract: Several notions of combinatorial complexity of set systems correspond with
both model-theoretic dividing lines and notions of machine learning.
We extend these parallels to learning with equivalence queries.
The relevant measures are the consistency dimension and
strong consistency dimension, which roughly correspond to NFCP formulas.
We use these along with Littlestone dimension to obtain new bounds on
several variants of equivalence query learning.
Tuesday March 5, 2019 at 1:00 PM in 427 SEO