Модификация модели и метода "прямого-обратного хода" для идентификации автоматных марковских моделей
А.Р. Нурутдинова
Казанский национальный исследовательский технический университет им. А.Н. Туполева, г. Казань, 420111, Россия
Аннотация
Статья посвящена решению задачи идентификации дискретных стохастических процессов, порождаемых автоматными марковскими моделями. Актуальность работы обусловлена потребностью повышения эффективности распознавания автоматных марковских моделей в соответствии с выделением определенных подклассов исследуемых объектов. Эффективность идентификации автоматных марковских моделей с определенной доверительной вероятностью достигается снижением длины цепи Маркова, а также уменьшением вычислительной сложности алгоритмов распознавания и минимизацией погрешности вычисления признаков относительно эргодических стохастических матриц, задающих автоматные марковские модели. В работе предложена модификация известного алгоритма «прямого-обратного хода» для решения задачи идентификации автоматных марковских моделей, определенных с помощью эргодических стохастических матриц по порождаемым ими реализациям цепей Маркова. Исследовано применение модифицированного алгоритма «прямого-обратного хода» к решению задачи идентификации автоматных марковских моделей, определенных с помощью циклической стохастической матрицы. Рассчитаны оценки вычислительной сложности предложенных алгоритмов идентификации. Наиболее важными из полученных результатов представляются следующие моменты. Модифицированный алгоритм позволяет определить значения вероятности того, что наблюдаемая последовательность сгенерирована на основе автоматной марковской модели заданного класса, которая, в свою очередь, определяется структурой задающей ее стохастической матрицы. Особенностью предложенного алгоритма является способность распознать класс автоматной марковской модели в том случае, когда в порождаемой последовательности некоторые состояния не наблюдаемы. Полученные результаты позволяют с большей вычислительной эффективностью идентифицировать автоматную марковскую модель по выходной последовательности. Указанная задача может быть использована для решения широкого круга задач идентификации цепей Маркова, в том числе частично скрытых от наблюдения.
Ключевые слова: цепь Маркова, идентификация, стохастическая матрица, алгоритм «прямого-обратного хода»
Литература
1. Левин Б.Р. Вероятностные модели и методы в системах связи и управления. – М.: Радио и связь, 1985. – 312 с.
2. Friedman W.F., Callimahos D. Military cryptanalysis. Pt. I, V. 2. – Laguna Hills, CA: Aegean Park Press, 1985. – 242 p.
3. Rabiner L.R. A tutorial on hidden Markov models and selected applications in speech recognition // Proc. IEEE. – 1989. – V. 77, No 2. – P. 257–286. – doi: 10.1109/5.18626.
4. Тептин Г.М., Иванов К.В. Марковские модели средств защиты автоматизированных систем специального назначения // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. – 2008. – Т. 150, кн. 4. - С. 41–53.
5. Раскин Л.Г. Анализ стохастических систем и элементы теории оптимального управления. – М.: Сов. радио, 1976. – 344 с.
6. Поспелов Д.А. Вероятностные автоматы. – М.: Энергия, 1970. – 88 с.
7. Бухараев Р.Г. К задаче минимизации входа автомата, генерирующего заданную однородную цепь Маркова // Учен. зап. Казан. ун-та. – 1967. – Т. 129, кн. 4. – С. 3–11.
8. Бухараев Р. Г. О представимости событий в вероятностных автоматах // Учен. зап. Казан. ун-та. – 1967. – Т. 127, кн. 3. – С. 7–20.
9. Альпин Ю.А., Альпина В.С. О нормальной форме стохастической матрицы // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. – 2012. – Т. 154, кн. 2. – С. 60–72.
10. Бухараев Р.Г. Вероятностные автоматы. – Казань: Изд-во Казан. ун-та, 1970. – 188 с.
11. Захаров В.М., Нурмеев Н.Н., Салимов Ф.И., Шалагин С.В. Анализ стохастических матриц методами многомерной классификации // Дискретная математика и ее приложения: Материалы 7-го Междунар. семинара: в 3 ч. – М.: Моск. гос. ун-т, 2001. – Ч. II. – С. 156–159.
12. Захаров В.М., Нурмеев Н.Н., Салимов Ф.И., Шалагин С.В. Классификация стохастических эргодических матриц методами кластерного и дискриминантного анализа // Исследования по информатике. – Казань: Отечество, 2000. – Вып. 2. – С. 91–106.
13. Лоренц А.А. Надежность и быстродействие вероятностных автоматов. – Рига: Зинатне, 1976. – 112 с.
14. Романовский В.И. Дискретные цепи Маркова. – М.: Гостехиздат, 1949. – 436 с.
15. Федотов Н.Г. Методы стохастической геометрии в распознавании образов. – М.: Радио и связь, 1990. – 144 с.
16. Kemeny J.G., Snell J.L. Finite Markov Chains. – N. Y.; 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.
18. Нурутдинова А.Р., Шалагин С.В. Методика идентификации автоматных марковских моделей на основе порождаемых ими последовательностей // Вестн. КГТУ им. А.Н. Туполева. – 2010. – № 1. – С. 94–99.
19. Нурутдинова А.Р., Шалагин С.В. Многопараметрическая классификация автоматных марковских моделей на основе генерируемых ими последовательностей состояний // Прикл. дискр. матем. – 2010. – № 4. – С. 41–54.
20. Хинчин А.Я. Понятие энтропии в теории вероятностей // Усп. матем. наук. – 1953. – № 3. – С. 3–20.
21. Нурутдинова, А.Р. Модифицированный алгоритм «прямого-обратного хода» решения задачи идентификации автоматных марковских моделей // Системы управления и информационные технологии. – 2018. – № 2. – С. 36–41.
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. – V. 8, No 3. – P. 14926–14935.
23. Шалагин С.В., Нурутдинова А.Р. Идентификация последовательности измерений экономических параметров на основе скрытой марковской модели // Проблемы анализа и моделирования региональных социально-экономических процессов: Материалы докл. VII Междунар. науч.-практ. конф. – Казань: Изд-во Казан. ун-та, 2017. – С. 159–162.
Поступила в редакцию
24.04.18
Нурутдинова Алсу Рафаиловна, соискатель
Казанский национальный исследовательский технический университет им. А.Н. Туполева – КАИ
ул. К. Маркса, д. 10, г. Казань, 420111, Россия
E-mail: Nurutdinovaar@mail.ru
Для цитирования: Нурутдинова А.Р. Модификация модели и метода «прямого-обратного хода» для идентификации автоматных марковских моделей // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. – 2018. – Т. 160, кн. 3. – С. 578–589.
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)
Контент доступен под лицензией Creative Commons Attribution 4.0 License.
