Öz
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.
Anahtar Kelimeler
Probabilistic Context-Free Grammars Viterbi Algorithm One-Counter Grammar Hidden Markov Model Formal Languages
Kaynakça
- C. D. Manning and H. Schutze, Foundation of Statistical Natural Languages MIT Press, Cambridge, MA, USA, 1999.
- 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.
- J. Autebert, J. Berstel and L. Boasson, Context-free Languages and Pushdown Automata in: Handbook of Formal Languages, Springer,1997.
- J. C. Chappelier, and M. Rajman, “A generalized cyk algorithm for parsing stochastic cfg,” in Proc.TAPD’98, 1998, p. 133.
- A. J. Viterbi, “A personal history of the Viterbi algorithm,” IEEE Signal Process., vol. 4, pp. 120, 2006.
- 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.
- L. R. Rabiner. “A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition”, Morgan Kaufmann Publishers Inc., 1990, p. 267.
- 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.
Öz
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.
Anahtar Kelimeler
Olasılıksal Bağlamdan Bağımsız Dilbilgisi Viterbi Algoritması Tek-Sayaçlı Dilbilgisi Saklı Markov Model Biçimsel Diller
Kaynakça
- C. D. Manning and H. Schutze, Foundation of Statistical Natural Languages MIT Press, Cambridge, MA, USA, 1999.
- 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.
- J. Autebert, J. Berstel and L. Boasson, Context-free Languages and Pushdown Automata in: Handbook of Formal Languages, Springer,1997.
- J. C. Chappelier, and M. Rajman, “A generalized cyk algorithm for parsing stochastic cfg,” in Proc.TAPD’98, 1998, p. 133.
- A. J. Viterbi, “A personal history of the Viterbi algorithm,” IEEE Signal Process., vol. 4, pp. 120, 2006.
- 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.
- L. R. Rabiner. “A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition”, Morgan Kaufmann Publishers Inc., 1990, p. 267.
- 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.
Ayrıntılar
| Birincil Dil | İngilizce |
|---|---|
| Konular | Mühendislik |
| Bölüm | Makaleler |
| Yazarlar | |
| Yayımlanma Tarihi | 30 Kasım 2021 |
| Yayımlandığı Sayı | Yıl 2021 Sayı: 28 |
- Makale Dosyaları