Estimation of Generating Processes of Strings Represented with Patterns and Refinements

Keisuke Otaki, Akihiro Yamamoto
Proceedings of the Eleventh International Conference on Grammatical Inference, PMLR 21:177-182, 2012.

Abstract

We formalize generating processes of strings based on patterns and substitutions, and give an algorithm to estimate a probability mass function on substitutions, which is an element of processes. Patterns are non-empty sequences of characters and variables. Variables indicate unknown substrings and are replaced with other patterns by substitutions. By introducing variables and substitutions, we can deal with the difficulty of preparing production rules in generative grammar and of representing context-sensitivity with them. Our key idea is to regard sequences of substitutions as generations of strings, and to give probabilities of substitutions like PCFG. In this study, after giving a problem to estimate a probability mass function from strings based on our formalization, we solve it by the Passing algorithm that runs in an iterative manner. Our experimental results with synthetic strings show that our method estimates probability mass functions with sufficient small errors.

Cite this Paper

BibTeX
@InProceedings{pmlr-v21-otaki12a, title = {Estimation of Generating Processes of Strings Represented with Patterns and Refinements}, author = {Otaki, Keisuke and Yamamoto, Akihiro}, booktitle = {Proceedings of the Eleventh International Conference on Grammatical Inference}, pages = {177--182}, year = {2012}, editor = {Heinz, Jeffrey and Higuera, Colin and Oates, Tim}, volume = {21}, series = {Proceedings of Machine Learning Research}, address = {University of Maryland, College Park, MD, USA}, month = {05--08 Sep}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v21/otaki12a/otaki12a.pdf}, url = {https://proceedings.mlr.press/v21/otaki12a.html}, abstract = {We formalize generating processes of strings based on patterns and substitutions, and give an algorithm to estimate a probability mass function on substitutions, which is an element of processes. Patterns are non-empty sequences of characters and variables. Variables indicate unknown substrings and are replaced with other patterns by substitutions. By introducing variables and substitutions, we can deal with the difficulty of preparing production rules in generative grammar and of representing context-sensitivity with them. Our key idea is to regard sequences of substitutions as generations of strings, and to give probabilities of substitutions like PCFG. In this study, after giving a problem to estimate a probability mass function from strings based on our formalization, we solve it by the Passing algorithm that runs in an iterative manner. Our experimental results with synthetic strings show that our method estimates probability mass functions with sufficient small errors.} }
Endnote
%0 Conference Paper %T Estimation of Generating Processes of Strings Represented with Patterns and Refinements %A Keisuke Otaki %A Akihiro Yamamoto %B Proceedings of the Eleventh International Conference on Grammatical Inference %C Proceedings of Machine Learning Research %D 2012 %E Jeffrey Heinz %E Colin Higuera %E Tim Oates %F pmlr-v21-otaki12a %I PMLR %P 177--182 %U https://proceedings.mlr.press/v21/otaki12a.html %V 21 %X We formalize generating processes of strings based on patterns and substitutions, and give an algorithm to estimate a probability mass function on substitutions, which is an element of processes. Patterns are non-empty sequences of characters and variables. Variables indicate unknown substrings and are replaced with other patterns by substitutions. By introducing variables and substitutions, we can deal with the difficulty of preparing production rules in generative grammar and of representing context-sensitivity with them. Our key idea is to regard sequences of substitutions as generations of strings, and to give probabilities of substitutions like PCFG. In this study, after giving a problem to estimate a probability mass function from strings based on our formalization, we solve it by the Passing algorithm that runs in an iterative manner. Our experimental results with synthetic strings show that our method estimates probability mass functions with sufficient small errors.
RIS
TY - CPAPER TI - Estimation of Generating Processes of Strings Represented with Patterns and Refinements AU - Keisuke Otaki AU - Akihiro Yamamoto BT - Proceedings of the Eleventh International Conference on Grammatical Inference DA - 2012/08/16 ED - Jeffrey Heinz ED - Colin Higuera ED - Tim Oates ID - pmlr-v21-otaki12a PB - PMLR DP - Proceedings of Machine Learning Research VL - 21 SP - 177 EP - 182 L1 - http://proceedings.mlr.press/v21/otaki12a/otaki12a.pdf UR - https://proceedings.mlr.press/v21/otaki12a.html AB - We formalize generating processes of strings based on patterns and substitutions, and give an algorithm to estimate a probability mass function on substitutions, which is an element of processes. Patterns are non-empty sequences of characters and variables. Variables indicate unknown substrings and are replaced with other patterns by substitutions. By introducing variables and substitutions, we can deal with the difficulty of preparing production rules in generative grammar and of representing context-sensitivity with them. Our key idea is to regard sequences of substitutions as generations of strings, and to give probabilities of substitutions like PCFG. In this study, after giving a problem to estimate a probability mass function from strings based on our formalization, we solve it by the Passing algorithm that runs in an iterative manner. Our experimental results with synthetic strings show that our method estimates probability mass functions with sufficient small errors. ER -
APA
Otaki, K. & Yamamoto, A.. (2012). Estimation of Generating Processes of Strings Represented with Patterns and Refinements. Proceedings of the Eleventh International Conference on Grammatical Inference, in Proceedings of Machine Learning Research 21:177-182 Available from https://proceedings.mlr.press/v21/otaki12a.html.

Related Material