A modified algorithm of “forward-backward” solving the identification of automata Markov models

A. R. Nurutdinova

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

Résumé

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.

Détail

Mots-clés : Markov chains, identification
Keywords: stochastic matrix, “forward-backward” algorithm.

Bibliographie

[1] Levin B. R., Probabilistic Models and Methods in Communication and Management Systems, Radio Svyaz, M., 1985, 312 pp. (In Russian)

[2] Friedman W. F., Callimahos D., Military cryptanalysis, Pt. I, v. 2, Aegean Park Press, Laguna Hills, CA, 1985, 242 pp.

[3] Rabiner L. R., “A tutorial on hidden Markov models and selected applications in speech recognition”, Proc. IEEE, 77:2 (1989), 257–286 | DOI

[4] Teptin G. M., Ivanov K. V., “Markov models of defense means for automated special-purpose systems”, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 150, no. 4, 2008, 41–53 (In Russian)

[5] Raskin L. G., Analysis of Stochastic Systems and Elements of the Optimal Control Theory, Sov. Radio, M., 1975, 344 pp. (In Russian)

[6] Pospelov D. A., Probabilistic Automata, Energy, M., 1970, 88 pp. (In Russian)

[7] Bukharaev R. G., “On the estimation of the minimal number of input values of an automaton that generates a homogeneous Markov chain”, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 129, no. 4, 1967, 3–11 (In Russian)

[8] Bukharaev R. G., “The representability of events in probabilistic automata”, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 127, no. 3, 1967, 7–20 (In Russian) | Zbl

[9] Alpin Yu. A., Alpina V. S., “On the normal form of a stochastic matrix”, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 154, no. 2, 2012, 60–72 (In Russian) | MR

[10] Bukharaev R. G., Probabilistic Automata, Izd. Kazan. Univ., Kazan, 1970, 188 pp. (In Russian)

[11] Zakharov V. M., Nurmeev N. N., Salimov F. I., Shalagin S. V., “Analysis of stochastic matrices using multivariate classification methods”, Discrete Mathematics and Its Applications, Proc. 7th Int. Seminar, v. II, M., 2001 (In Russian)

[12] Zakharov V. M., Nurmeev N. N., Salimov F. I., Shalagin S. V., “Classification of ergodic stochastic matrices using methods of cluster and discriminant analysis”, Issled. Inf., 2, 2000, 91–106 (In Russian)

[13] Lorenc A. A., Reliability and Speed of Probabilistic Automata, Zinatne, Riga, 1976, 112 pp. (In Russian)

[14] Romanovskii V. I., Discrete Markov Chains, Gostekhizdat, M., 1949, 436 pp. (In Russian)

[15] Fedotov N. G., Methods of Stochastic Geometry in Pattern Recognition, Radio Svyaz, M., 1990, 144 pp. (In Russian)

[16] Kemeny J. G., Snell J. L., Finite Markov Chains, Springer, N. Y., 1970, 272 pp. | MR

[17] Li T., Jadg D., Zelner A, Evaluation of parameters of Markov property models by aggregated temporary rows, Statistics, M., 1977, 221 pp.

[18] Nurutdinova A. R., Shalagin S. V., “The method of identification of automaton Markov models on the basis of sequences generated by them”, Vestn. KGTU im. A.N. Tupoleva, 2010, no. 1, 94–99 (In Russian)

[19] Nurutdinova A. R., Shalagin S. V., “Multiparameter classification of automation Markov models based on their generated sequence of states”, Prikl. Diskretn. Mat., 2010, no. 4, 41–54 (In Russian)

[20] Khinchin A. Ya., “Concept of entropy in the theory of probability”, Usp. Mat. Nauk, 1953, no. 3, 3–20 (In Russian)

[21] Nurutdinova A. R., “A modification of the “forward-backward” algorithm of identification of automata Markov models”, Sist. Upr. Inf. Tekhnol., 2018, no. 2, 36–41 (In Russian)

[22] Shalagin S. V., Nurutdinova A. R., “Identification algorithms of simple homogeneous Markov chains of cyclic class and their complexity analysis”, Int. J. Pharm. Technol., 8:3 (2016), 14926–14935

[23] Shalagin S. V., Nurutdinova A. R., “Identification of a sequence of measurements of economic parameters based on a hidden Markov model”, Problems of Analysis and Modeling of Regional Social and Economic Processes, Proc. VII Int. Sci.-Pract. Conf., Izd. Kazan. Univ., Kazan, 2017, 159–162 (In Russian)