Использование вероятностной скрытой марковской модели. Формирование алгоритма с возможностью управления его гибкостью в соответствии с содержательной ситуацией для обеспечения структурной и функциональной устойчивости программы, реализующей алгоритм.
Аннотация к работе
В основе любой целенаправленной деятельности лежат процедуры принятия решений задачи в виде последовательности действий (алгоритмов), преобразующие исходные данные для достижения цели (искомого результата решения задачи) при минимальных затратах. Задача может быть решена различными алгоритмами, имеющими свои преимущества и недостатки при ее решении, причем синтез решений включает построение качественной модели задачи, с последующей записью ее в математической форме, построение целевой функции переменных и исследование влияния переменных на целевую функцию. При решении задачи используется ее модель М, которая определяет множество алгоритмов решения АМ{а|а: Jin Jout}, т.е. на множестве алгоритмов АМ алгоритм AIAM реализует отображения из пространства начальных информаций Jin в пространство финальных информаций Jout. Широко используемый в настоящее время при решении задач разновидность параметрического подхода байесовский, основанный на знании плотности распределения всех входных переменных задачи, по которой корректный для данной задачи алгоритм можно выписать в явном аналитическом виде, воспользовавшись формализованной структурной информацией алгоритма Is. Байесовская постановка решения задач с моделью М определяет расширение множества алгоритмов AM так, чтобы оно включало не только алгоритмы вида a: Y®Dout, но и все возможные распределения вероятностей Ps(dout|y), т. е. в стохастических алгоритмах для каждого значения y случайно выбирается подходящее решение dout в соответствии с вероятностями Ps(dout|y).Содержательные аксиомы модели рандомизированного алгоритма допускают возможность использования в качестве модели алгоритма скрытой марковской модели (Hidden Markov Model) HMM, которая применима не только к исходным типовым алгоритмам, но и к корректирующим алгоритмам, а также и для синтезируемых композиций. При вероятностной модели алгоритма появляется возможность управлять связями между переменными алгоритма, задавая гибкость алгоритма для обеспечения требуемой структурной и функциональной устойчивости программы, реализующей данный алгоритм. На втором этапе по заданной скрытой марковской модели Q с пространством скрытых состояний S={s1, s2,..., SK}, начальными вероятностями pi нахождения в состоянии i и вероятностями Pi,j перехода из состояния i в состояние j, по наблюдаемым состояниям o1,..., OT ищется путь Витерби SV=s1...ST, наиболее точно описывающую данную модель, для чего естественно воспользоваться алгоритмом Витерби (Viterbi algorithm).
Вывод
1. Содержательные аксиомы модели рандомизированного алгоритма допускают возможность использования в качестве модели алгоритма скрытой марковской модели (Hidden Markov Model) HMM, которая применима не только к исходным типовым алгоритмам, но и к корректирующим алгоритмам, а также и для синтезируемых композиций.
2. При вероятностной модели алгоритма появляется возможность управлять связями между переменными алгоритма, задавая гибкость алгоритма для обеспечения требуемой структурной и функциональной устойчивости программы, реализующей данный алгоритм.
3. Рандомизация алгоритма, повышая его гибкость и эффективность, не улучшает его риск по сравнению с соответствующим детерминированным алгоритмом.
4. Задача синтеза алгоритма на базе HMM заключается в том, чтобы по имеющимся наблюдаемым данным определяют скрытые параметры наиболее вероятной последовательности состояний.
5. На первом этапе стратегии при заданных параметрах модели Q=(P, Ps, П) и последовательности скрытых S и соответствующих наблюдаемых состояний О, определяется вероятность появления данных последовательностей. Так на первом шаге для модели Q и множества исходных данных Din определяется pi=P(Din?Q) и оценивается насколько хорошо модель Q согласована к исходными данными. Данная задача в такой постановке решается с помощью алгоритма "вперед-назад", который позволяет найти в HMM вероятность попадания в состояние si на t-ом шаге при последовательности наблюдений O и (скрытой) последовательности состояний S.
6. На втором этапе по заданной скрытой марковской модели Q с пространством скрытых состояний S={s1, s2,..., SK}, начальными вероятностями pi нахождения в состоянии i и вероятностями Pi,j перехода из состояния i в состояние j, по наблюдаемым состояниям o1,..., OT ищется путь Витерби SV=s1...ST, наиболее точно описывающую данную модель, для чего естественно воспользоваться алгоритмом Витерби (Viterbi algorithm).
7. На третьем этапе стратегии осуществляется корректировка скрытых марковских моделей путем оптимизации параметров модели Q=(P, Ps, П) так, чтобы максимизировать P(O?Q) при наблюдаемых данных O. Данный этап стратегии наиболее полно реализуется алгоритмом Баума-Велша (Baum - Welch algorithm).
Список литературы
вероятностный марковский модель
1. Филатов В.А., Козырь О.Ф. Модель поведения автономного сценария в задачах управления распределенными информационными ресурсами //Инженерный вестник Дона, 2013, № 3 URL: ivdon.ru/magazine/archive/ n3y2013/1771/.
2. Аль-Хулайди А.А. Разработка нового стохастического метода управления очередями заданий с использованием Марковских процессов для параллельных вычислений на кластере//Инженерный вестник Дона, 2011, №1 URL: ivdon.ru/magazine/archive/n1y2011/332/.
3. Mikhaylov A.A., Bazuyeva S.A. Probabilistic Approach to the Synthesis of Algorithm for Solving Problems//Modern Applied Science/Canadian Center of Science and Education. 2015. V. 9, № 5. pp. 125-132.
4. Рудаков К.В. Универсальные и локальные ограничения в проблеме коррекции эвристических алгоритмов // Кибернетика. 1987. № 2. С. 30-35.
5. Рудаков К.В. Полнота и универсальные ограничения в проблеме коррекции эвристических алгоритмов классификации//Кибернетика. 1987. № 3. С. 106-109.
6. Рудаков К.В. Симметрические и функциональные ограничения в проблеме коррекции эвристических алгоритмов классификации // Кибернетика. 1987. № 4. С. 73-77.
7. Рудаков К.В. О применении универсальных ограничений при исследовании алгоритмов классификации // Кибернетика. 1988. № 1. С. 1-5.
8. Рабинер Л.Р. Скрытые марковские модели и их применение в избранных приложениях при распознавании речи: Обзор//ТИЭР М: Наука, 1989. Выпуск 2. Том 77. С. 86-102.
9. Binder J., Murphy K. and Russell S. Space-Efficient Inference in Dynamic Probabilistic Networks//Int"l, Joint Conf. on Artificial Intelligence. 1997. V. 1, №5, pp. 1292-1296.
10. Lawrence R., Rabiner A. Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition//Proceedings of the IEEE. 1989. V. 77. № 2, February. pp. 257-286.
11. Lawrence R. Rabiner, Juang B.H. An introduction to hidden Markov models//IEEE ASSP Magazine. 1986. January. pp. 4-15.
12. Forney G.D., JR. The Viterbi Algorithm//Proceedings of the IEEE. 1973. V. 61, № 3, March. pp. 268 - 277.
13. Витерби А.Д., Омура Дж.К. Принципы цифровой связи и кодирования/Пер. с англ. под ред. К.Ш. Зигангирова. М.: Радио и связь. 1982. 536 с.
14. Золотарев В.В., Овечкин Г.В. Помехоустойчивое кодирование. Методы и алгоритмы: Справочник /Под. ред. чл.-кор. РАН Ю. Б. Зубарева. М.: Горячая линия. Телеком. 2004. 126 с.
15. Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение/пер. с англ. В. Б. Афанасьева. М.: Техносфера. 2006. 320 с.
16. Baum L.E. An inequality and associated maximization technique in statistical estimation for probabilistic functions of a Markov process//Inequalities. 1972. № 3. pp. 1-8.