Online Infix Probability Computation for Probabilistic Finite Automata

Marco Cognetta, Yo-Sub Han, Soon Chan Kwon


Abstract
Probabilistic finite automata (PFAs) are com- mon statistical language model in natural lan- guage and speech processing. A typical task for PFAs is to compute the probability of all strings that match a query pattern. An impor- tant special case of this problem is computing the probability of a string appearing as a pre- fix, suffix, or infix. These problems find use in many natural language processing tasks such word prediction and text error correction. Recently, we gave the first incremental algorithm to efficiently compute the infix probabilities of each prefix of a string (Cognetta et al., 2018). We develop an asymptotic improvement of that algorithm and solve the open problem of computing the infix probabilities of PFAs from streaming data, which is crucial when process- ing queries online and is the ultimate goal of the incremental approach.
Anthology ID:
P19-1528
Volume:
Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics
Month:
July
Year:
2019
Address:
Florence, Italy
Venue:
ACL
SIG:
Publisher:
Association for Computational Linguistics
Note:
Pages:
5332–5337
Language:
URL:
https://aclanthology.org/P19-1528
DOI:
10.18653/v1/P19-1528
Bibkey:
Cite (ACL):
Marco Cognetta, Yo-Sub Han, and Soon Chan Kwon. 2019. Online Infix Probability Computation for Probabilistic Finite Automata. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 5332–5337, Florence, Italy. Association for Computational Linguistics.
Cite (Informal):
Online Infix Probability Computation for Probabilistic Finite Automata (Cognetta et al., ACL 2019)
Copy Citation:
PDF:
https://preview.aclanthology.org/ingestion-script-update/P19-1528.pdf
Software:
 P19-1528.Software.zip