A modified algorithm of 'forward-backward' solving the identification of automata Markov models - A.R. Nurutdinova (Учёные записки Казанского университета: Серия Физико-математические науки)
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.