Very efficient learning of structured classes of subsequential functions from positive data

Adam Jardine, Jane Chandlee, Rémi Eyraud, Jeffrey Heinz
The 12th International Conference on Grammatical Inference, PMLR 34:94-108, 2014.

Abstract

In this paper, we present a new algorithm that can identify in polynomial time and data using positive examples any class of subsequential functions that share a particular finite-state structure. While this structure is given to the learner \textita priori, it allows for the exact learning of partial functions, and both the time and data complexity of the algorithm are linear. We demonstrate the algorithm on examples from natural language phonology and morphology in which the needed structure has been argued to be plausibly known in advance. A procedure for making any subsequential transducer onward without changing its structure is also presented.

Cite this Paper

BibTeX
@InProceedings{pmlr-v34-jardine14a, title = {Very efficient learning of structured classes of subsequential functions from positive data}, author = {Jardine, Adam and Chandlee, Jane and Eyraud, Rémi and Heinz, Jeffrey}, booktitle = {The 12th International Conference on Grammatical Inference}, pages = {94--108}, year = {2014}, editor = {Clark, Alexander and Kanazawa, Makoto and Yoshinaka, Ryo}, volume = {34}, series = {Proceedings of Machine Learning Research}, address = {Kyoto, Japan}, month = {17--19 Sep}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v34/jardine14a.pdf}, url = {https://proceedings.mlr.press/v34/jardine14a.html}, abstract = {In this paper, we present a new algorithm that can identify in polynomial time and data using positive examples any class of subsequential functions that share a particular finite-state structure. While this structure is given to the learner \textita priori, it allows for the exact learning of partial functions, and both the time and data complexity of the algorithm are linear. We demonstrate the algorithm on examples from natural language phonology and morphology in which the needed structure has been argued to be plausibly known in advance. A procedure for making any subsequential transducer onward without changing its structure is also presented.} }
Endnote
%0 Conference Paper %T Very efficient learning of structured classes of subsequential functions from positive data %A Adam Jardine %A Jane Chandlee %A Rémi Eyraud %A Jeffrey Heinz %B The 12th International Conference on Grammatical Inference %C Proceedings of Machine Learning Research %D 2014 %E Alexander Clark %E Makoto Kanazawa %E Ryo Yoshinaka %F pmlr-v34-jardine14a %I PMLR %P 94--108 %U https://proceedings.mlr.press/v34/jardine14a.html %V 34 %X In this paper, we present a new algorithm that can identify in polynomial time and data using positive examples any class of subsequential functions that share a particular finite-state structure. While this structure is given to the learner \textita priori, it allows for the exact learning of partial functions, and both the time and data complexity of the algorithm are linear. We demonstrate the algorithm on examples from natural language phonology and morphology in which the needed structure has been argued to be plausibly known in advance. A procedure for making any subsequential transducer onward without changing its structure is also presented.
RIS
TY - CPAPER TI - Very efficient learning of structured classes of subsequential functions from positive data AU - Adam Jardine AU - Jane Chandlee AU - Rémi Eyraud AU - Jeffrey Heinz BT - The 12th International Conference on Grammatical Inference DA - 2014/08/30 ED - Alexander Clark ED - Makoto Kanazawa ED - Ryo Yoshinaka ID - pmlr-v34-jardine14a PB - PMLR DP - Proceedings of Machine Learning Research VL - 34 SP - 94 EP - 108 L1 - http://proceedings.mlr.press/v34/jardine14a.pdf UR - https://proceedings.mlr.press/v34/jardine14a.html AB - In this paper, we present a new algorithm that can identify in polynomial time and data using positive examples any class of subsequential functions that share a particular finite-state structure. While this structure is given to the learner \textita priori, it allows for the exact learning of partial functions, and both the time and data complexity of the algorithm are linear. We demonstrate the algorithm on examples from natural language phonology and morphology in which the needed structure has been argued to be plausibly known in advance. A procedure for making any subsequential transducer onward without changing its structure is also presented. ER -
APA
Jardine, A., Chandlee, J., Eyraud, R. & Heinz, J.. (2014). Very efficient learning of structured classes of subsequential functions from positive data. The 12th International Conference on Grammatical Inference, in Proceedings of Machine Learning Research 34:94-108 Available from https://proceedings.mlr.press/v34/jardine14a.html.

Related Material