Learning Top-Down Tree Transducers with Regular Domain Inspection

Adrien Boiret, Aurélien Lemay, Joachim Niehren
Proceedings of The 13th International Conference on Grammatical Inference, PMLR 57:54-65, 2017.

Abstract

We study the problem of how to learn tree transformations on a given regular tree domain from a finite sample of input-output examples. We assume that the target tree transformation can be defined by a deterministic top-down tree transducer with regular domain inspection (DTOPIreg). An RPNI style learning algorithm that solves this problem in polynomial time and with polynomially many examples was presented at Pods’2010, but restricted to the case of path-closed regular domains. In this paper, we show that this restriction can be removed. For this, we present a new normal form for DTOPIreg by extending the Myhill-Nerode theorem for DTOP to regular domain inspections in a nontrivial manner. The RPNI style learning algorithm can also be lifted but becomes more involved too.

Cite this Paper

BibTeX
@InProceedings{pmlr-v57-boiret16, title = {Learning Top-Down Tree Transducers with Regular Domain Inspection}, author = {Boiret, Adrien and Lemay, Aurélien and Niehren, Joachim}, booktitle = {Proceedings of The 13th International Conference on Grammatical Inference}, pages = {54--65}, year = {2017}, editor = {Verwer, Sicco and Zaanen, Menno van and Smetsers, Rick}, volume = {57}, series = {Proceedings of Machine Learning Research}, address = {Delft, The Netherlands}, month = {05--07 Oct}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v57/boiret16.pdf}, url = {http://proceedings.mlr.press/v57/boiret16.html}, abstract = {We study the problem of how to learn tree transformations on a given regular tree domain from a finite sample of input-output examples. We assume that the target tree transformation can be defined by a deterministic top-down tree transducer with regular domain inspection (DTOPIreg). An RPNI style learning algorithm that solves this problem in polynomial time and with polynomially many examples was presented at Pods’2010, but restricted to the case of path-closed regular domains. In this paper, we show that this restriction can be removed. For this, we present a new normal form for DTOPIreg by extending the Myhill-Nerode theorem for DTOP to regular domain inspections in a nontrivial manner. The RPNI style learning algorithm can also be lifted but becomes more involved too.} }
Endnote
%0 Conference Paper %T Learning Top-Down Tree Transducers with Regular Domain Inspection %A Adrien Boiret %A Aurélien Lemay %A Joachim Niehren %B Proceedings of The 13th International Conference on Grammatical Inference %C Proceedings of Machine Learning Research %D 2017 %E Sicco Verwer %E Menno van Zaanen %E Rick Smetsers %F pmlr-v57-boiret16 %I PMLR %P 54--65 %U http://proceedings.mlr.press/v57/boiret16.html %V 57 %X We study the problem of how to learn tree transformations on a given regular tree domain from a finite sample of input-output examples. We assume that the target tree transformation can be defined by a deterministic top-down tree transducer with regular domain inspection (DTOPIreg). An RPNI style learning algorithm that solves this problem in polynomial time and with polynomially many examples was presented at Pods’2010, but restricted to the case of path-closed regular domains. In this paper, we show that this restriction can be removed. For this, we present a new normal form for DTOPIreg by extending the Myhill-Nerode theorem for DTOP to regular domain inspections in a nontrivial manner. The RPNI style learning algorithm can also be lifted but becomes more involved too.
RIS
TY - CPAPER TI - Learning Top-Down Tree Transducers with Regular Domain Inspection AU - Adrien Boiret AU - Aurélien Lemay AU - Joachim Niehren BT - Proceedings of The 13th International Conference on Grammatical Inference DA - 2017/01/16 ED - Sicco Verwer ED - Menno van Zaanen ED - Rick Smetsers ID - pmlr-v57-boiret16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 57 SP - 54 EP - 65 L1 - http://proceedings.mlr.press/v57/boiret16.pdf UR - http://proceedings.mlr.press/v57/boiret16.html AB - We study the problem of how to learn tree transformations on a given regular tree domain from a finite sample of input-output examples. We assume that the target tree transformation can be defined by a deterministic top-down tree transducer with regular domain inspection (DTOPIreg). An RPNI style learning algorithm that solves this problem in polynomial time and with polynomially many examples was presented at Pods’2010, but restricted to the case of path-closed regular domains. In this paper, we show that this restriction can be removed. For this, we present a new normal form for DTOPIreg by extending the Myhill-Nerode theorem for DTOP to regular domain inspections in a nontrivial manner. The RPNI style learning algorithm can also be lifted but becomes more involved too. ER -
APA
Boiret, A., Lemay, A. & Niehren, J.. (2017). Learning Top-Down Tree Transducers with Regular Domain Inspection. Proceedings of The 13th International Conference on Grammatical Inference, in Proceedings of Machine Learning Research 57:54-65 Available from http://proceedings.mlr.press/v57/boiret16.html.

Related Material