Hesaplama Açısından Verimli HMM Kod Çözümü İçin Demet Sınırlamalı k-Adımlı İleri Bakış

Öz

Gizli Markov Modelleri (HMM'ler), zamanla ilgili bağımlılıkları modelleme yetenekleri nedeniyle birçok ardışık karar verme probleminde yaygın olarak kullanılır. Bu modellerdeki standart kod çözme yöntemleri, Viterbi algoritması gibi, yalnızca geçmiş gözlemlere olan bağımlılıklarıyla sınırlıdır. Bu nedenle, gelecekteki bilgiler mevcut olduğunda öngörülemezliğe yol açar. Bu çalışmada, gelecekteki bilgileri kullanmak için (yani kontrol teorisindeki k-adımlı ayrık kontrol sentezine benzer bir yaklaşımla) k-adım ileriyi gören Işın Sınırlı k-Adım İleriye Bakış adı verilen bir kod çözme stratejisi öneriyoruz. Önerilen yöntem, arama alanını en umut verici M yolla sınırlayarak kod çözme doğruluğu ve hesaplama karmaşıklığı arasında bir denge sağlar. Sentetik HMM verileri üzerindeki deneysel sonuçlar, yeni kod çözme stratejimizin kod çözme doğruluğunu klasik Viterbi kod çözmeye kıyasla önemli ölçüde iyileştirdiğini göstermektedir. Bulgular, bu yeni stratejinin ardışık kod çözme sistemlerinin performansını iyileştirme potansiyelini vurgulamaktadır.

Anahtar Kelimeler

• Saklı Markov Modelleri
• Kod Çözme Problemleri
• Sınırlı Işın Araması
• Ardışık Tahminleme

Beam-Limited k-Step Lookahead for Computationally Efficient HMM Decoding

Öz

Hidden Markov Models (HMMs) are widely used in many sequential decision-making problems due to their ability to model time-related dependencies. The standard decoding methods in these models, such as the Viterbi algorithm, are limited by their dependence on past observations only. Thus, this leads to unpredictability when future information is available. In this work, we propose a decoding strategy called Beam-Limited k-Step Lookahead that looks k-step ahead, drawing parallels to k-step discrete control synthesis, to make use of future information. The proposed method achieves a balance between decoding accuracy and computational complexity by constraining the search space to the top M most promising paths. Experimental results on synthetic HMM data show that our new decoding strategy significantly improves decoding accuracy over classical Viterbi decoding. The findings highlight the potential of this new strategy to improve the performance of sequential decoding systems.

Anahtar Kelimeler

• Hidden Markov Models
• Decoding Problems
• Beam Limited Search
• Sequencial Estimation

Kaynakça

1. 1. Siddalingappa, R., Hanumanthappa, P. & Reddy, M. (2018). Hidden markov model for speech recognition system - a pilot study and a naive approach for speech-to-text model. Advances in Intelligent Systems and Computing, 77-90.
2. 2. Li, J., Lee, J.Y. & Liao, L. (2021). A new algorithm to train hidden markov models for biological sequences with partial labels. BMC Bioinformatics, 22, 162.
3. 3. Brakensiek, A. & Rigoll, G. (2004). Handwritten address recognition using hidden markov models. In: Dengel, A., Junker, M., Weisbecker, A. (eds) Reading and Learning. Lecture Notes in Computer Science, 2956. Springer, Berlin, Heidelberg.
4. 4. Tataru, P., Sand, A., Hobolth, A., Mailund, T. & Pedersen, C.N. (2013). Algorithms for hidden markov models restricted to occurrences of regular expressions. Biology (Basel), 2(4), 1282-1295.
5. 5. Rabiner, L.R. (1989). A tutorial on hidden markov models and selected applications in speech recognition. Proceedings of the IEEE, 77(2), 257-286.
6. 6. Wang, Y.S., Kuo, Y.L. & Katz, B. (2020). Investigating the decoders of maximum likelihood sequence models: a look-ahead approach. arXiv preprint.
7. 7. Graves, A. (2012). Sequence transduction with recurrent neural networks. arXiv preprint. arXiv: 1211.3711.
8. 8. Hannun, A. (2017). Sequence modeling with CTC. https://distill.pub/2017/ctc.

9. 9. Chorowski, J. & Jaitly, N. (2016). Towards better decoding and language model integration in sequence to sequence models. arXiv preprint. arXiv:1612.02695.
10. 10. Doucet, A., Godsill, S. & Andrieu, C. (2000). On sequential Monte Carlo sampling methods for Bayesian filtering. Statistics and Computing, 10, 197-208.
11. 11. Graves, A., Mohamed, A.-R. & Hinton, G. (2013). Speech recognition with deep recurrent neural networks. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 6645-6649.
12. 12. Xiaomin, L., Thomas, H. & Colin, C. (2023). Estimating hidden markov models (HMMs) of the cognitive process in strategic thinking using eye-tracking. Frontiers in Behavioral Economics, 2, 1225856.
13. 13. Manouchehri, N. & Bouguila, N. (2023). Human activity recognition with an HMM-Based Generative Model. Sensors, 23(3), 1390.
14. 14. Saize, S. & Yang, X. (2024). On the definitions of hidden markov models. Applied Mathematical Modelling, 125, 617-629.
15. 15. Kurucan, M. & Wojtczak, D. (2024). The utilization of single-counter systems featuring final terminals with non-zero counter values. Cukurova University, Journal of the Faculty of Engineering, 39(4), 999-1014.
16. 16. Tüfekçi, Z. & Dişken, G. (2022). Fast computation of parameters of the random variable that is logarithm of sum of two independent log-normally distributed random variables. Çukurova Üniversitesi, Mühendislik Fakültesi Dergisi, 37(1), 261-270.