Hunter Chase : Model-theoretic techniques in query learning

Posted by Gyorgy Turan , part of the Mathematical Computer Science Seminar.

At

March 5, 2019, 1 p.m.

In

427 SEO

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.