Learning MSOdefinable hypotheses on strings
[edit]
Proceedings of the 28th International Conference on Algorithmic Learning Theory, PMLR 76:434451, 2017.
Abstract
We study the classification problems over string data for hypotheses specified by formulas of monadic secondorder logic MSO. The goal is to design learning algorithms that run in time polynomial in the size of the training set, independently of or at least sublinear in the size of the whole data set. We prove negative as well as positive results. If the data set is an unprocessed string to which our algorithms have local access, then learning in sublinear time is impossible even for hypotheses definable in a small fragment of firstorder logic. If we allow for a linear time preprocessing of the string data to build an index data structure, then learning of MSOdefinable hypotheses is possible in time polynomial in the size of the training set, independently of the size of the whole data set.
Related Material


