Inside-Outside Algorithm for Macro Grammars

Ryuta Kambe, Naoki Kobayashi, Ryosuke Sato, Ayumi Shinohara, Ryo Yoshinaka
Proceedings of the Fifteenth International Conference on Grammatical Inference, PMLR 153:32-46, 2021.

Abstract

We propose an inside-outside algorithm for stochastic macro grammars. Our approach is based on types, which has been inspired by type-based approaches to reasoning about functional programs and higher-order grammars. By considering type derivations instead of ordinary word derivation sequences, we can naturally extend the standard inside-outside algorithm for stochastic context-free grammars to obtain the algorithm for stochastic macro grammars. We have implemented the algorithm and confirmed its effectiveness through an application to the learning of macro grammars.

Cite this Paper

BibTeX
@InProceedings{pmlr-v153-kambe21a, title = {Inside-Outside Algorithm for Macro Grammars}, author = {Kambe, Ryuta and Kobayashi, Naoki and Sato, Ryosuke and Shinohara, Ayumi and Yoshinaka, Ryo}, booktitle = {Proceedings of the Fifteenth International Conference on Grammatical Inference}, pages = {32--46}, 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/kambe21a/kambe21a.pdf}, url = {https://proceedings.mlr.press/v153/kambe21a.html}, abstract = {We propose an inside-outside algorithm for stochastic macro grammars. Our approach is based on types, which has been inspired by type-based approaches to reasoning about functional programs and higher-order grammars. By considering type derivations instead of ordinary word derivation sequences, we can naturally extend the standard inside-outside algorithm for stochastic context-free grammars to obtain the algorithm for stochastic macro grammars. We have implemented the algorithm and confirmed its effectiveness through an application to the learning of macro grammars.} }
Endnote
%0 Conference Paper %T Inside-Outside Algorithm for Macro Grammars %A Ryuta Kambe %A Naoki Kobayashi %A Ryosuke Sato %A Ayumi Shinohara %A Ryo Yoshinaka %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-kambe21a %I PMLR %P 32--46 %U https://proceedings.mlr.press/v153/kambe21a.html %V 153 %X We propose an inside-outside algorithm for stochastic macro grammars. Our approach is based on types, which has been inspired by type-based approaches to reasoning about functional programs and higher-order grammars. By considering type derivations instead of ordinary word derivation sequences, we can naturally extend the standard inside-outside algorithm for stochastic context-free grammars to obtain the algorithm for stochastic macro grammars. We have implemented the algorithm and confirmed its effectiveness through an application to the learning of macro grammars.
APA
Kambe, R., Kobayashi, N., Sato, R., Shinohara, A. & Yoshinaka, R.. (2021). Inside-Outside Algorithm for Macro Grammars. Proceedings of the Fifteenth International Conference on Grammatical Inference, in Proceedings of Machine Learning Research 153:32-46 Available from https://proceedings.mlr.press/v153/kambe21a.html.

Related Material