Incremental computation of infix probabilities for probabilistic finite automata

Marco Cognetta; Yo Sub Han; Soon Chan Kwon

Incremental computation of infix probabilities for probabilistic finite automata

Marco Cognetta, Yo Sub Han, Soon Chan Kwon

College of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

2 Citations (Scopus)

Abstract

In natural language processing, a common task is to compute the probability of a given phrase appearing or to calculate the probability of all phrases matching a given pattern. For instance, one computes affix (prefix, suffix, infix, etc.) probabilities of a string or a set of strings with respect to a probability distribution of patterns. The problem of computing infix probabilities of strings when the pattern distribution is given by a probabilistic context-free grammar or by a probabilistic finite automaton is already solved, yet it was open to compute the infix probabilities in an incremental manner. The incremental computation is crucial when a new query is built from a previous query. We tackle this problem and suggest a method that computes infix probabilities incrementally for probabilistic finite automata by representing all the probabilities of matching strings as a series of transition matrix calculations. We show that the proposed approach is theoretically faster than the previous method and, using real world data, demonstrate that our approach has vastly better performance in practice.

Original language	English
Title of host publication	Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, EMNLP 2018
Editors	Ellen Riloff, David Chiang, Julia Hockenmaier, Jun'ichi Tsujii
Publisher	Association for Computational Linguistics
Pages	2732-2741
Number of pages	10
ISBN (Electronic)	9781948087841
Publication status	Published - 2018
Event	2018 Conference on Empirical Methods in Natural Language Processing, EMNLP 2018 - Brussels, Belgium Duration: 2018 Oct 31 → 2018 Nov 4

Publication series

Name	Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, EMNLP 2018

Conference

Conference	2018 Conference on Empirical Methods in Natural Language Processing, EMNLP 2018
Country/Territory	Belgium
City	Brussels
Period	18/10/31 → 18/11/4

Bibliographical note

Funding Information:
This article is adapted from the author?s PhD dissertation Constructing Global Amman: Petrodollars, Identity, and the Built Environment in the Early Twenty-First Century (University of Illinois at Urbana-Champaign, 2013). The author is grateful to professors John Stallmeyer, D. Fairchild Ruggles, Lynne Dearborn, and Kenneth Cuno for their thoughtful comments on the draft of the dissertation. The author is also thankful to the research participants in Amman for their valuable contributions.

Publisher Copyright:
© 2018 Association for Computational Linguistics

All Science Journal Classification (ASJC) codes

Computational Theory and Mathematics
Computer Science Applications
Information Systems

Cite this

Cognetta, M., Han, Y. S., & Kwon, S. C. (2018). Incremental computation of infix probabilities for probabilistic finite automata. In E. Riloff, D. Chiang, J. Hockenmaier, & J. Tsujii (Eds.), Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, EMNLP 2018 (pp. 2732-2741). (Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, EMNLP 2018). Association for Computational Linguistics.

Cognetta, Marco ; Han, Yo Sub ; Kwon, Soon Chan. / Incremental computation of infix probabilities for probabilistic finite automata. Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, EMNLP 2018. editor / Ellen Riloff ; David Chiang ; Julia Hockenmaier ; Jun'ichi Tsujii. Association for Computational Linguistics, 2018. pp. 2732-2741 (Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, EMNLP 2018).

@inproceedings{608490b7244945a8b65258ac08a804b2,

title = "Incremental computation of infix probabilities for probabilistic finite automata",

abstract = "In natural language processing, a common task is to compute the probability of a given phrase appearing or to calculate the probability of all phrases matching a given pattern. For instance, one computes affix (prefix, suffix, infix, etc.) probabilities of a string or a set of strings with respect to a probability distribution of patterns. The problem of computing infix probabilities of strings when the pattern distribution is given by a probabilistic context-free grammar or by a probabilistic finite automaton is already solved, yet it was open to compute the infix probabilities in an incremental manner. The incremental computation is crucial when a new query is built from a previous query. We tackle this problem and suggest a method that computes infix probabilities incrementally for probabilistic finite automata by representing all the probabilities of matching strings as a series of transition matrix calculations. We show that the proposed approach is theoretically faster than the previous method and, using real world data, demonstrate that our approach has vastly better performance in practice.",

author = "Marco Cognetta and Han, {Yo Sub} and Kwon, {Soon Chan}",

note = "Funding Information: This article is adapted from the author?s PhD dissertation Constructing Global Amman: Petrodollars, Identity, and the Built Environment in the Early Twenty-First Century (University of Illinois at Urbana-Champaign, 2013). The author is grateful to professors John Stallmeyer, D. Fairchild Ruggles, Lynne Dearborn, and Kenneth Cuno for their thoughtful comments on the draft of the dissertation. The author is also thankful to the research participants in Amman for their valuable contributions. Publisher Copyright: {\textcopyright} 2018 Association for Computational Linguistics; 2018 Conference on Empirical Methods in Natural Language Processing, EMNLP 2018 ; Conference date: 31-10-2018 Through 04-11-2018",

year = "2018",

language = "English",

series = "Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, EMNLP 2018",

publisher = "Association for Computational Linguistics",

pages = "2732--2741",

editor = "Ellen Riloff and David Chiang and Julia Hockenmaier and Jun'ichi Tsujii",

booktitle = "Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, EMNLP 2018",

}

Cognetta, M, Han, YS & Kwon, SC 2018, Incremental computation of infix probabilities for probabilistic finite automata. in E Riloff, D Chiang, J Hockenmaier & J Tsujii (eds), Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, EMNLP 2018. Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, EMNLP 2018, Association for Computational Linguistics, pp. 2732-2741, 2018 Conference on Empirical Methods in Natural Language Processing, EMNLP 2018, Brussels, Belgium, 18/10/31.

Incremental computation of infix probabilities for probabilistic finite automata. / Cognetta, Marco; Han, Yo Sub; Kwon, Soon Chan.
Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, EMNLP 2018. ed. / Ellen Riloff; David Chiang; Julia Hockenmaier; Jun'ichi Tsujii. Association for Computational Linguistics, 2018. p. 2732-2741 (Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, EMNLP 2018).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Incremental computation of infix probabilities for probabilistic finite automata

AU - Cognetta, Marco

AU - Han, Yo Sub

AU - Kwon, Soon Chan

N1 - Funding Information: This article is adapted from the author?s PhD dissertation Constructing Global Amman: Petrodollars, Identity, and the Built Environment in the Early Twenty-First Century (University of Illinois at Urbana-Champaign, 2013). The author is grateful to professors John Stallmeyer, D. Fairchild Ruggles, Lynne Dearborn, and Kenneth Cuno for their thoughtful comments on the draft of the dissertation. The author is also thankful to the research participants in Amman for their valuable contributions. Publisher Copyright: © 2018 Association for Computational Linguistics

PY - 2018

Y1 - 2018

N2 - In natural language processing, a common task is to compute the probability of a given phrase appearing or to calculate the probability of all phrases matching a given pattern. For instance, one computes affix (prefix, suffix, infix, etc.) probabilities of a string or a set of strings with respect to a probability distribution of patterns. The problem of computing infix probabilities of strings when the pattern distribution is given by a probabilistic context-free grammar or by a probabilistic finite automaton is already solved, yet it was open to compute the infix probabilities in an incremental manner. The incremental computation is crucial when a new query is built from a previous query. We tackle this problem and suggest a method that computes infix probabilities incrementally for probabilistic finite automata by representing all the probabilities of matching strings as a series of transition matrix calculations. We show that the proposed approach is theoretically faster than the previous method and, using real world data, demonstrate that our approach has vastly better performance in practice.

AB - In natural language processing, a common task is to compute the probability of a given phrase appearing or to calculate the probability of all phrases matching a given pattern. For instance, one computes affix (prefix, suffix, infix, etc.) probabilities of a string or a set of strings with respect to a probability distribution of patterns. The problem of computing infix probabilities of strings when the pattern distribution is given by a probabilistic context-free grammar or by a probabilistic finite automaton is already solved, yet it was open to compute the infix probabilities in an incremental manner. The incremental computation is crucial when a new query is built from a previous query. We tackle this problem and suggest a method that computes infix probabilities incrementally for probabilistic finite automata by representing all the probabilities of matching strings as a series of transition matrix calculations. We show that the proposed approach is theoretically faster than the previous method and, using real world data, demonstrate that our approach has vastly better performance in practice.

UR - http://www.scopus.com/inward/record.url?scp=85081716677&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85081716677&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85081716677

T3 - Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, EMNLP 2018

SP - 2732

EP - 2741

BT - Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, EMNLP 2018

A2 - Riloff, Ellen

A2 - Chiang, David

A2 - Hockenmaier, Julia

A2 - Tsujii, Jun'ichi

PB - Association for Computational Linguistics

T2 - 2018 Conference on Empirical Methods in Natural Language Processing, EMNLP 2018

Y2 - 31 October 2018 through 4 November 2018

ER -

Cognetta M, Han YS, Kwon SC. Incremental computation of infix probabilities for probabilistic finite automata. In Riloff E, Chiang D, Hockenmaier J, Tsujii J, editors, Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, EMNLP 2018. Association for Computational Linguistics. 2018. p. 2732-2741. (Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, EMNLP 2018).

Incremental computation of infix probabilities for probabilistic finite automata

Abstract

Publication series

Conference

Bibliographical note

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this