The Paradigm For Solving The Derivation Problem In Infinite Models

Abstract

The problem of finding the most probable derivation for probabilistic context-free grammar is expensive. The Viterbi algorithm has been adopted to one-counter grammar that is a sub-class of stochastic context-free grammar to solve this issue. However, the absence of the implementation of the adapted algorithm attracts our attention. We experimentally validate this algorithm and present the implementation part of it to monitor the performance, in this research.

Keywords

• Probabilistic Context-Free Grammars
• Viterbi Algorithm
• One-Counter Grammar
• Hidden Markov Model
• Formal Languages

Sonsuz Modellerde Türetme Problemini Çözme Uygulaması

Abstract

Olasılıksal bağlamdan bağımsız dilbilgisi için en olası türetmeyi bulma probleminin çözümü pahalıdır. Bu problemin çözümü için Viterbi algoritması, olasılıksal bağlamdan bağımsız dilbilgisinin bir alt sınıfı olan tek sayaçlı dilbilgisine uayarlanmıştır. Ancak adapte edilen algoritmanin uygulanmamış olması dikkatimizi çekmektedir. Bu araştırmada, bu algoritmayı deneysel olarak doğruladık ve uygulamada izlenilen performansı sunuyoruz.

Keywords

• Olasılıksal Bağlamdan Bağımsız Dilbilgisi
• Viterbi Algoritması
• Tek-Sayaçlı Dilbilgisi
• Saklı Markov Model
• Biçimsel Diller

References

1. C. D. Manning and H. Schutze, Foundation of Statistical Natural Languages MIT Press, Cambridge, MA, USA, 1999.
2. A. Sakharov and T. Sakharov, “The Viterbi algorithm for subsets of stochastic context-free languages”, Information Processing Letters., vol. 135, pp. 68-72, Jul. 2018.
3. J. Autebert, J. Berstel and L. Boasson, Context-free Languages and Pushdown Automata in: Handbook of Formal Languages, Springer,1997.
4. J. C. Chappelier, and M. Rajman, “A generalized cyk algorithm for parsing stochastic cfg,” in Proc.TAPD’98, 1998, p. 133.
5. A. J. Viterbi, “A personal history of the Viterbi algorithm,” IEEE Signal Process., vol. 4, pp. 120, 2006.
6. B. Brejova, D. G. Brown and T. Vinar, “Advances in hidden Markov models for sequence annotation”, Bioinformatics Algorithm: Techniques and Application, vol. 3, pp. 55-92, 2008.
7. L. R. Rabiner. “A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition”, Morgan Kaufmann Publishers Inc., 1990, p. 267.
8. K Etessami, D. Wojtczak and M. Yannakakis, “Quasi-birth-death processes, tree-like qbds, probabilistic 1-counter automata, and pushdown system,” in QEST’08, 2008, p. 243.