Learning MSO-definable hypotheses on strings

Martin Grohe, Christof Löding, Martin Ritzert
Proceedings of the 28th International Conference on Algorithmic Learning Theory, PMLR 76:434-451, 2017.

Abstract

We study the classification problems over string data for hypotheses specified by formulas of monadic second-order 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 first-order logic. If we allow for a linear time pre-processing of the string data to build an index data structure, then learning of MSO-definable hypotheses is possible in time polynomial in the size of the training set, independently of the size of the whole data set.

Cite this Paper

BibTeX
@InProceedings{pmlr-v76-grohe17a, title = {Learning MSO-definable hypotheses on strings}, author = {Grohe, Martin and Löding, Christof and Ritzert, Martin}, booktitle = {Proceedings of the 28th International Conference on Algorithmic Learning Theory}, pages = {434--451}, year = {2017}, editor = {Hanneke, Steve and Reyzin, Lev}, volume = {76}, series = {Proceedings of Machine Learning Research}, month = {15--17 Oct}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v76/grohe17a/grohe17a.pdf}, url = {https://proceedings.mlr.press/v76/grohe17a.html}, abstract = {We study the classification problems over string data for hypotheses specified by formulas of monadic second-order 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 first-order logic. If we allow for a linear time pre-processing of the string data to build an index data structure, then learning of MSO-definable hypotheses is possible in time polynomial in the size of the training set, independently of the size of the whole data set.} }
Endnote
%0 Conference Paper %T Learning MSO-definable hypotheses on strings %A Martin Grohe %A Christof Löding %A Martin Ritzert %B Proceedings of the 28th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2017 %E Steve Hanneke %E Lev Reyzin %F pmlr-v76-grohe17a %I PMLR %P 434--451 %U https://proceedings.mlr.press/v76/grohe17a.html %V 76 %X We study the classification problems over string data for hypotheses specified by formulas of monadic second-order 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 first-order logic. If we allow for a linear time pre-processing of the string data to build an index data structure, then learning of MSO-definable hypotheses is possible in time polynomial in the size of the training set, independently of the size of the whole data set.
APA
Grohe, M., Löding, C. & Ritzert, M.. (2017). Learning MSO-definable hypotheses on strings. Proceedings of the 28th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 76:434-451 Available from https://proceedings.mlr.press/v76/grohe17a.html.

Related Material