Geodesic
A modified algorithm of “forward-backward” solving the identification of automata Markov models
Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 160 (2018) no. 3, pp. 578-589

Voir la notice du chapitre de livre provenant de la source Math-Net.Ru

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.
Mots-clés : Markov chains, identification
Keywords: stochastic matrix, “forward-backward” algorithm. 
@article{UZKU_2018_160_3_a11,
     author = {A. R. Nurutdinova},
     title = {A modified algorithm of {\textquotedblleft}forward-backward{\textquotedblright} solving the identification of automata {Markov} models},
     journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
     pages = {578--589},
     publisher = {mathdoc},
     volume = {160},
     number = {3},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/UZKU_2018_160_3_a11/}
}
TY  - JOUR
AU  - A. R. Nurutdinova
TI  - A modified algorithm of “forward-backward” solving the identification of automata Markov models
JO  - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
PY  - 2018
SP  - 578
EP  - 589
VL  - 160
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/UZKU_2018_160_3_a11/
LA  - ru
ID  - UZKU_2018_160_3_a11
ER  - 
%0 Journal Article
%A A. R. Nurutdinova
%T A modified algorithm of “forward-backward” solving the identification of automata Markov models
%J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
%D 2018
%P 578-589
%V 160
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/UZKU_2018_160_3_a11/
%G ru
%F UZKU_2018_160_3_a11
A. R. Nurutdinova. A modified algorithm of “forward-backward” solving the identification of automata Markov models. Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 160 (2018) no. 3, pp. 578-589. http://geodesic.mathdoc.fr/item/UZKU_2018_160_3_a11/