The Impossibility of PAC-learning DFAs
Bundit Laekhanukit - PhD Student, McGill SOCS
April 8, 2014, 12:10 p.m. - April 8, 2014, 12:40 p.m.
MC103
Probably approximately correct learning (PAC learning) is a learning model proposed by Leslie Valiant that introduces the concepts of computational complexity to machine learning. In particular, given positive and negative samples, the learner is expected to find a polynomial-time computable function that could approximately distinguish between positive and negative samples.
In this work, we study the PAC-learnability of DFAs, i.e., the case where positive and negative samples are drawn from an unknown DFA. We show that, unless NP=RP, DFAs are not PAC-learnable, thus, answering an open question raised 25 years ago by Pitt and Warmuth.
This is a joint work with Parinya Chalermsook and Danupon Nanongkai.
