Online Infix Probability Computation for Probabilistic Finite Automata

Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 5332–5337 Florence, Italy, July 28 - August 2, 2019. c⃝2019 Association for Computational Linguistics 5332 Online Infix Probability Computation for Probabilistic Finite Automata Marco Cognetta, Yo-Sub Han, and Soon Chan Kwon∗ Department of Computer Science Yonsei University, Seoul, Republic of Korea cognetta.marco@gmail.com, {emmous, soon--chan}@yonsei.ac.kr 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 algo- rithm to efficiently compute the infix probabil- ities of each prefix of a string (Cognetta et al., 2018). We develop an asymptotic improve- ment of that algorithm and solve the open problem of computing the infix probabilities of PFAs from streaming data, which is crucial when processing queries online and is the ulti- mate goal of the incremental approach. 1 Introduction Weighted automata are a popular weighted lan- guage model in natural language processing. They have found use across the discipline both alone (Mohri et al., 2002) and in conjunction with more complicated language models (Ghazvinine- jad et al., 2016; Velikovich et al., 2018). As such, finding efficient algorithms for weighted automata has become an intensely studied topic (Allauzen and Mohri, 2009; Argueta and Chiang, 2018). An important subclass of weighted automata are PFAs. Given a PFA, one important task is to calculate the probability of a phrase or pattern. Efficient algorithms exist for this problem when given a PFA or a probabilistic context-free gram- mar (PCFG) and a pattern that forms a regular lan- guage (Vidal et al., 2005a; Nederhof and Satta, 2011). One important special case of this problem ∗Now at Google Korea. is to compute the probability of all strings con- taining a given infix, which was first studied by Corazza et al. (1991). The problem was motivated by applications to phrase prediction and error cor- rection. Several partial results were established with various restrictions on the statistical model or infix (Corazza et al., 1991; Fred, 2000; Nederhof and Satta, 2011). Later, Nederhof and Satta (2011) gave a general solution for PCFGs and proposed the problem of computing the infix probabilities of each prefix of a string incrementally—using the infix probability of w1w2 . . . wk to speed up the calculation for w1w2 . . . wkwk+1. Recently, we gave an algorithm for this problem when the language model is a PFA, and suggested an open problem of online incremental infix prob- ability calculation—where one is given a stream of characters instead of knowing the entire input string ahead of time (Cognetta et al., 2018). The online problem is of special practical importance as it is …

Content truncated to 500 words