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

A.R. Nurutdinova

Tupolev Kazan National Research Technical University, Kazan, 420111 Russia

E-mail:  Nurutdinovaar@mail.ru

Received April 24, 2018

Full text PDF

Abstract

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.

Keywords: Markov chains, identification, stochastic matrix, “forward-backward” algorithm

References

1. Levin B.R. Veroyatnostnye modeli i metody v sistemakh svyazi i upravleniya [Probabilistic Models and Methods in Communication and Management Systems]. Moscow, Radio Svyaz', 1985. 312 p. (In Russian)

2. Friedman W.F. Military Cryptanalis. Pt. I. Vol. 2. Laguna Hills, Calif., Aegean Park Press, 1985. 242 p.

3. Rabiner Lawrence R. A tutorial on hidden Markov models and selected applications in speech recognition. Proc. IEEE, 1989, vol. 77, no. 2, pp. 257–286. doi: 10.1109/5.18626.

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, 2008, vol. 150, no. 4, pp. 41–53. (In Russian)

5. Raskin L.G. Analiz stokhasticheskikh sistem i elementy teorii optimal'nogo upravleniya [Analysis of Stochastic Systems and Elements of the Optimal Control Theory]. Moscow, Sov. Radio, 1975, 344 p. (In Russian)

6. Pospelov D.A. Veroyatnostnye avtomaty [Probabilistic Automata]. Moscow, Energy, 1970, 88 p. (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, 1967, vol. 129, no. 4, pp. 3–11. (In Russian)

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

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

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

11. Zakharov V.M., Nurmeev N.N., Salimov F.I., Shalagin S.V. Analysis of stochastic matrices using multivariate classification methods. Diskretnaya matematika i ee prilozheniya: Materialy 7-go Mezhdunar. seminara [Discrete Mathematics and Its Applications: Proc. 7th Int. Seminar]. Moscow, 2001, pt. II, pp. 156–159. (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., 2000, no. 2, pp. 91–106. (In Russian)

13. Lorenc A.A. Nadezhnost' i bystrodeistvie veroyatnostnykh avtomatov [Reliability and Speed of Probabilistic Automata]. Riga, Zinatne, 1976. 112 p. (In Russian)

14. Romanovskii V.I. Diskretnye tsepi Markova [Discrete Markov Chains]. Moscow, Gostekhizdat, 1949. 436 p. (In Russian)

15. Fedotov N.G. Metody stokhasticheskoi geometrii v raspoznavanii obrazov [Methods of Stochastic Geometry in Pattern Recognition]. Moscow, Radio Svyaz', 1990. 144 p. (In Russian)

16. Kemeny J.G., Snell J.L. Finite Markov Chains. New York, Springer, 1970. 272 p.

17. Li T., Jadg D., Zelner A. Evaluation of Parameters of Markov Property Models by Aggregated Temporary Rows. Moscow, Statistics, 1977. 221 p. (In Russian)

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, pp. 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, pp. 41–54. (In Russian)

20. Khinchin A.Ya. Concept of entropy in the theory of probability. Usp. Mat. Nauk, 1953, no. 3, pp. 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, pp. 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., 2016, vol. 8, no. 3, pp. 14926–14935.

23. Shalagin S.V., Nurutdinova A.R. Identification of a sequence of measurements of economic parameters based on a hidden Markov model. Problemy analiza i modelirovaniya regional'nykh sotsial'no-ekonomicheskikh protsessov: Materialy dokl. VII Mezhdunar. nauch.-prakt. konf. [Problems of Analysis and Modeling of Regional Social and Economic Processes: Proc. VII Int. Sci.-Pract. Conf.]. Kazan, Izd. Kazan. Univ., 2017, pp. 159–162. (In Russian)

For citation: Nurutdinova A.R. A modified algorithm of “forward-backward” solving the identification of automata Markov models. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2018, vol. 160, no. 3, pp. 578–589. (In Russian)

The content is available under the license Creative Commons Attribution 4.0 License.