A modified algorithm of 'forward-backward' solving the identification of automata Markov models
The paper is devoted to solving the problem of identifying discrete stochastic processes generated on the basis of automata Markov models. This problem is relevant because of the need to increase the efficiency of automata Markov models recognition. The effectiveness of identifying automata Markov m...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Kazan Federal University
2018-09-01
|
| Series: | Учёные записки Казанского университета: Серия Физико-математические науки |
| Subjects: | |
| Online Access: | https://kpfu.ru/a-modified-algorithm-of-39forward-backward39-403862.html |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1841563301831507968 |
|---|---|
| author | A.R. Nurutdinova |
| author_facet | A.R. Nurutdinova |
| author_sort | A.R. Nurutdinova |
| collection | DOAJ |
| description | The paper is devoted to solving the problem of identifying discrete stochastic processes generated on the basis of automata Markov models. This problem is relevant because of the need to increase the efficiency of automata Markov models recognition. The effectiveness of identifying automata Markov models with a certain confidence probability is determined by the decrease in the length of Markov chains, as well as by the decrease in the computational complexity of algorithms for recognizing and minimizing the error in calculating traits relative to the ergodic stochastic matrices that define automata Markov models. The modified model allows to determine the probability values that a sequence is generated on the basis of the automata Markov model of the given class, which, in turn, is determined by the structure of the stochastic matrix. A feature of this model is the ability of the algorithm to recognize the class of the automata Markov model in the case when some states are not observable in the generated sequence. A modification of the “forward-backward” algorithm and its adaptation to the problem of identification of automata Markov models defined using ergodic stochastic matrices on the basis of the realizations of Markov chains generated by them has been proposed. In the paper, the task of modifying the “forward-backward” algorithm for automata Markov models determined on the basis of cyclic ergodic stochastic matrices has been solved. The estimates of the computational complexity of the proposed identification algorithms have been calculated. The most important of the results obtained are the following. A feature of this model is the ability of the algorithm to recognize the class of the automata Markov model in the case when some states are not observable in the generated sequence. The results obtained make it possible to better identify the automata Markov models by the output sequence. This problem can be applied to solve a wide range of problems of identification of Markov chains, including partially hidden ones. |
| format | Article |
| id | doaj-art-820bfa0a30864525a3bf30998a6327a2 |
| institution | Kabale University |
| issn | 2541-7746 2500-2198 |
| language | English |
| publishDate | 2018-09-01 |
| publisher | Kazan Federal University |
| record_format | Article |
| series | Учёные записки Казанского университета: Серия Физико-математические науки |
| spelling | doaj-art-820bfa0a30864525a3bf30998a6327a22025-01-03T00:04:51ZengKazan Federal UniversityУчёные записки Казанского университета: Серия Физико-математические науки2541-77462500-21982018-09-011603578589A modified algorithm of 'forward-backward' solving the identification of automata Markov modelsA.R. Nurutdinova0Tupolev Kazan National Research Technical University, Kazan, 420111 RussiaThe paper is devoted to solving the problem of identifying discrete stochastic processes generated on the basis of automata Markov models. This problem is relevant because of the need to increase the efficiency of automata Markov models recognition. The effectiveness of identifying automata Markov models with a certain confidence probability is determined by the decrease in the length of Markov chains, as well as by the decrease in the computational complexity of algorithms for recognizing and minimizing the error in calculating traits relative to the ergodic stochastic matrices that define automata Markov models. The modified model allows to determine the probability values that a sequence is generated on the basis of the automata Markov model of the given class, which, in turn, is determined by the structure of the stochastic matrix. A feature of this model is the ability of the algorithm to recognize the class of the automata Markov model in the case when some states are not observable in the generated sequence. A modification of the “forward-backward” algorithm and its adaptation to the problem of identification of automata Markov models defined using ergodic stochastic matrices on the basis of the realizations of Markov chains generated by them has been proposed. In the paper, the task of modifying the “forward-backward” algorithm for automata Markov models determined on the basis of cyclic ergodic stochastic matrices has been solved. The estimates of the computational complexity of the proposed identification algorithms have been calculated. The most important of the results obtained are the following. A feature of this model is the ability of the algorithm to recognize the class of the automata Markov model in the case when some states are not observable in the generated sequence. The results obtained make it possible to better identify the automata Markov models by the output sequence. This problem can be applied to solve a wide range of problems of identification of Markov chains, including partially hidden ones.https://kpfu.ru/a-modified-algorithm-of-39forward-backward39-403862.htmlmarkov chainsidentificationstochastic matrix“forward-backward” algorithm |
| spellingShingle | A.R. Nurutdinova A modified algorithm of 'forward-backward' solving the identification of automata Markov models Учёные записки Казанского университета: Серия Физико-математические науки markov chains identification stochastic matrix “forward-backward” algorithm |
| title | A modified algorithm of 'forward-backward' solving the identification of automata Markov models |
| title_full | A modified algorithm of 'forward-backward' solving the identification of automata Markov models |
| title_fullStr | A modified algorithm of 'forward-backward' solving the identification of automata Markov models |
| title_full_unstemmed | A modified algorithm of 'forward-backward' solving the identification of automata Markov models |
| title_short | A modified algorithm of 'forward-backward' solving the identification of automata Markov models |
| title_sort | modified algorithm of forward backward solving the identification of automata markov models |
| topic | markov chains identification stochastic matrix “forward-backward” algorithm |
| url | https://kpfu.ru/a-modified-algorithm-of-39forward-backward39-403862.html |
| work_keys_str_mv | AT arnurutdinova amodifiedalgorithmofforwardbackwardsolvingtheidentificationofautomatamarkovmodels AT arnurutdinova modifiedalgorithmofforwardbackwardsolvingtheidentificationofautomatamarkovmodels |