Learning Input Strictly Local Functions From Their Composition

Wenyue Hua, Adam Jardine
Proceedings of the Fifteenth International Conference on Grammatical Inference, PMLR 153:47-65, 2021.

Abstract

This paper studies the learning of two functions given positive samples of their composition, motivated by an empirical problem in natural language phonology. Empirically relevant conditions under which this is possible are identified and a provably correct algorithm is given that can semi-strongly identify the two functions in polynomial time and data. In order to clearly illustrate the learning problem and related concepts, we focus on a simple subset of input strictly 2-local functions. But we further argue that the general learning procedure we propose can be extended to more general classes of functions.

Cite this Paper

BibTeX
@InProceedings{pmlr-v153-hua21a, title = {Learning Input Strictly Local Functions From Their Composition}, author = {Hua, Wenyue and Jardine, Adam}, booktitle = {Proceedings of the Fifteenth International Conference on Grammatical Inference}, pages = {47--65}, year = {2021}, editor = {Chandlee, Jane and Eyraud, Rémi and Heinz, Jeff and Jardine, Adam and van Zaanen, Menno}, volume = {153}, series = {Proceedings of Machine Learning Research}, month = {23--27 Aug}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v153/hua21a/hua21a.pdf}, url = {https://proceedings.mlr.press/v153/hua21a.html}, abstract = {This paper studies the learning of two functions given positive samples of their composition, motivated by an empirical problem in natural language phonology. Empirically relevant conditions under which this is possible are identified and a provably correct algorithm is given that can semi-strongly identify the two functions in polynomial time and data. In order to clearly illustrate the learning problem and related concepts, we focus on a simple subset of input strictly 2-local functions. But we further argue that the general learning procedure we propose can be extended to more general classes of functions.} }
Endnote
%0 Conference Paper %T Learning Input Strictly Local Functions From Their Composition %A Wenyue Hua %A Adam Jardine %B Proceedings of the Fifteenth International Conference on Grammatical Inference %C Proceedings of Machine Learning Research %D 2021 %E Jane Chandlee %E Rémi Eyraud %E Jeff Heinz %E Adam Jardine %E Menno van Zaanen %F pmlr-v153-hua21a %I PMLR %P 47--65 %U https://proceedings.mlr.press/v153/hua21a.html %V 153 %X This paper studies the learning of two functions given positive samples of their composition, motivated by an empirical problem in natural language phonology. Empirically relevant conditions under which this is possible are identified and a provably correct algorithm is given that can semi-strongly identify the two functions in polynomial time and data. In order to clearly illustrate the learning problem and related concepts, we focus on a simple subset of input strictly 2-local functions. But we further argue that the general learning procedure we propose can be extended to more general classes of functions.
APA
Hua, W. & Jardine, A.. (2021). Learning Input Strictly Local Functions From Their Composition. Proceedings of the Fifteenth International Conference on Grammatical Inference, in Proceedings of Machine Learning Research 153:47-65 Available from https://proceedings.mlr.press/v153/hua21a.html.

Related Material