Incremental Computation of Infix Probabilities for Probabilistic Finite Automata
In natural language processing, a common task is to compute the probability of a phrase appearing in a document 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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Online Infix Probability Computation for Probabilistic Finite Automata
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. A…
Language ModelingLanguage ModellingBounded Conditioning: Flexible Inference for Decisions under Scarce Resources
We introduce a graceful approach to probabilistic inference called bounded conditioning. Bounded conditioning monotonically refines the bounds on posterior probabilities in a belief network with computation, and converge…
Incremental Import Vector Machines for Classifying Hyperspectral Data
In this paper we propose an incremental learning strategy for import vector machines (IVM), which is a sparse kernel logistic regression approach. We use the procedure for the concept of self-training for sequential clas…
ClassificationGeneral ClassificationIncremental LearningInduction, of and by Probability
This paper examines some methods and ideas underlying the author's successful probabilistic learning systems(PLS), which have proven uniquely effective and efficient in generalization learning or induction. While the eme…
Heuristic SearchIncremental LearningManagementFrom Samples to Scenarios: A New Paradigm for Probabilistic Forecasting
Most state-of-the-art probabilistic time series forecasting models rely on sampling to represent future uncertainty. However, this paradigm suffers from inherent limitations, such as lacking explicit probabilities, inade…
Probabilistic Time Series Forecasting