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 = {Adrien Boiret and Aurélien Lemay and Joachim Niehren}, booktitle = {Proceedings of The 13th International Conference on Grammatical Inference}, pages = {54--65}, year = {2017}, editor = {Sicco Verwer and Menno van Zaanen and Rick Smetsers}, 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 %J Proceedings of Machine Learning Research %P 54--65 %U http://proceedings.mlr.press %V 57 %W PMLR %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 PY - 2017/01/16 DA - 2017/01/16 ED - Sicco Verwer ED - Menno van Zaanen ED - Rick Smetsers ID - pmlr-v57-boiret16 PB - PMLR SP - 54 DP - PMLR 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 PMLR 57:54-65

Related Material