Использование скрытой марковской модели при синтезе стохастического алгоритма решения задачи

Размещено на http://www.allbest.ru/

Южно-Российский государственный политехнический университет, Новочеркасск

Использование скрытой марковской модели при синтезе стохастического алгоритма решения задачи

А.А. Михайлов

С.А. Базуева

1. Постановка проблемы

В основе любой целенаправленной деятельности лежат процедуры принятия решений задачи в виде последовательности действий (алгоритмов), преобразующие исходные данные для достижения цели (искомого результата решения задачи) при минимальных затратах. Задача может быть решена различными алгоритмами, имеющими свои преимущества и недостатки при ее решении, причем синтез решений включает построение качественной модели задачи, с последующей записью ее в математической форме, построение целевой функции переменных и исследование влияния переменных на целевую функцию.

При принятии решений в условиях определенности используется критериальный подход, при котором оценивают каждую альтернативу с помощью критериев. Однако в настоящее время возросло значение решения задач, примерами которых могут быть разработка автономных сценариев (алгоритмов) для управления информационными ресурсами вычислительных систем [1] или для управления очередями заданий в кластере локальной сети с использованием Марковских процессов [2]. Характерное для данных примеров многофакторное влияние на переменные целевой функции алгоритма условий среды и управляющих воздействий ограничивает использование детерминированного подхода из-за редко встречающейся ситуации полной определенности последствий выбора, поскольку на практике чаще используются несколько различных критериев и крайне редко одна альтернатива является лучшей по каждому из них.

Для преодоления данного ограничения в настоящее время широкое распространение получили разновидности стохастических алгоритмов (вероятностные и эвристические), предоставляющие возможность управления их гибкостью и эффективностью, что определяет использование при формировании алгоритма вероятностной модели. При этом вероятностный алгоритм задает стратегию решения задачи несколькими путями или способами, приводящими к вероятному достижению результата, а для эвристических алгоритмов достижение конечного результата однозначно не предопределено, так же как не обозначена вся последовательность действий, не выявлены все действия исполнителя.

Целью статьи является исследование возможности использования при синтезе корректных алгоритмов решения задачи вероятностной модели алгоритма, которая определяет возможность управления гибкостью алгоритма для обеспечения структурной и функциональной устойчивости программы, реализующей данный алгоритм, при, например, хакерской атаке на неё.

2. Общий анализ процесса принятия решения

В соответствии с [3-7] определим задачу синтеза корректного алгоритма как процесс преобразования начальной (исходной) информации J_in={X(S)|S?у} на некотором множестве у={S}, элементы которого в виде объектов X(S) описываются для их наблюдения через I_in, так что J_in={I_in}. В зависимости от приложения, I_in может быть числом или нечисловым математическим объектом (символ в абстрактном алфавите, вектор, последовательность символов, функция одной переменной (процесс) или функция двух переменных (изображение), а также функция с более сложной областью определения).

При решении задачи используется ее модель М, которая определяет множество алгоритмов решения A_М{a|a: J_inJ_out}, т.е. на множестве алгоритмов А_М алгоритм aA_М реализует отображения из пространства начальных информаций J_in в пространство финальных информаций J_out. В результате «черный ящик» превращается в «белый», который характеризуется структурной информацией задачи I_s, корректно по полноте и правильности отображающая суть проблемы J_in. Структурная информация задачи I_s выделяет на подмножестве M допустимых отображений модель M[I_s], определяющая корректное решение задачи J_out={I_s}. Алгоритм a, реализующий допустимое отображение, которое определяется структурной информацией I_s, является корректным решением для задачи.

На множестве стохастических алгоритмов заданы не только правила в классе строгих решений (дедуктивный подход), определены также абдуктивный подход (обратная дедукция), при котором определяются наиболее вероятные исходные утверждения из некоторых заключений путем обратных преобразований, и индуктивный для выявления наиболее вероятных закономерностей, вытекающих из сопоставления исходных данных и известных результатов. При этом выбор решений может реализоваться в различных вариантах:

* Множество алгоритмов может быть дискретным или непрерывным.

* Режим выбора может быть разовым или итеративным.

* Оценка альтернатив производиться по критериям разного типа.

* Последствия каждой альтернативы выбора могут быть известны (условия определенности), неизвестны точно, но вероятность последствий можно оценить (условия статистической неопределенности), неизвестны, и вероятность последствий оценить нельзя (условия неопределенности).

3. Общий анализ байесовского подхода к решению задач

3.1 Выбор критерия оценки качества решения задачи

Широко используемый в настоящее время при решении задач разновидность параметрического подхода байесовский, основанный на знании плотности распределения всех входных переменных задачи, по которой корректный для данной задачи алгоритм можно выписать в явном аналитическом виде, воспользовавшись формализованной структурной информацией алгоритма I_s.

Байесовские задачи и основные свойства байесовских алгоритмов задаются математическими свойствами множеств входных начальных информаций J_in, состояний X и решений D_outI_out, которые определяют эффективность алгоритмов. Алгоритм определяется на конечном множестве наблюдаемых параметров yY и на конечном множестве скрытых состояний алгоритма xX, а также должен быть согласован с входными данными D_inJ_in. На множестве YX всех возможных пар наблюдений yY и состояний xX задается распределение совместной вероятности P_YX(y, x): YXR.

Для введения критерия оценки качества решения задачи определим для множества xX и возможных решений d_outD_out функцию потерь W(x, d_out): XD_outR. Для алгоритма a: YD_out, который каждому наблюдению yY присваивает решение a(y)D_out, определим риск R(a) как математическое ожидание функции потерь алгоритма a. При этом байесовская задача статистических решений состоит в том, чтобы для заданных множеств Y, X, D_out, заданных алгоритмом a: YD_out, который минимизирует байесовский риск

R(a)=.

Результатом функционирования байесовского алгоритма a^* является решение байесовской задачи с минимумом риском R(a). Причем множества состояний X и решений D_out имеет разнообразную форму. В зависимости от ограничений на математическую форму элементов множеств наблюдений Y, состояний X и решений D_out постановка байесовской задачи конкретизируется.

3.2 Обобщенная байесовская постановка решения задач

Байесовская постановка решения задач с моделью М определяет расширение множества алгоритмов A_M так, чтобы оно включало не только алгоритмы вида a: YD_out, но и все возможные распределения вероятностей P_s(d_outy), т. е. в стохастических алгоритмах для каждого значения y случайно выбирается подходящее решение d_out в соответствии с вероятностями P_s(d_outy). Среди данных стохастических алгоритмов ищется наилучший, в котором при фиксированном значении x принимается одно и то же детерминированное решение d_out=a(y), которое входит в противоречие со случайным характером состояния, в котором находится алгоритм.

Для байесовской постановке решения задачи определим на конечных множествах Y, X, D_out с распределением вероятностей P_YX: YXR и функцией потерь W: XD_outR стохастический алгоритм a_s: D_outYR, риск которого

R_s=. (1)

Теорема [3]: Для любого стохастического алгоритма существует детерминированный алгоритм a: YD_out, риск которого

R_det=

не больше, чем R_s, т. е. байесовская задача может быть сведена к поиску детерминированного алгоритма a: YD_out.

Доказательство: Перепишем равенство (1) в иной форме,

R_s=.

Равенство =1 выполняется для любого yY, а неравенство 0 выполняется для любых d_outD_out и yY, поэтому справедливо неравенство

R_s.

Обозначим a(y) любое значение d_out, для которого

.

Данный алгоритм a: YD_out является детерминированным, который не хуже, чем стохастический a_s

,

т. е. для детерминированного алгоритма a риск R_detR_s.

4. Модель алгоритма решения байесовской задачи

Концептуальная модель детерминированного алгоритма представляется последовательностью машинных команд (операторов) v_i, определенная на множестве машинных команд V={v_i}, i=, где n_mk- число машинных команд, содержащихся в выборке класса алгоритмов, под которыми понимается система команд используемого класса процессоров. Для модели стохастического алгоритма переменные определяются следующими содержательными аксиомами:

наблюдаемые (скрытые) события представляются в виде последовательности, упорядоченной по времени (свойство Маркова, обеспечивающее сходимость стратегии), так t-я скрытая переменная s_t при известной (t-1)-ой переменной s_t-₁ независима от всех предыдущих (t-1) переменных, то есть функция перехода

P(s_ts_t-1, s_t-1,..., s₁, o₁)=P(s_ts_t-1),

а t-е известное наблюдение o_t зависит только от t-го состояния

P(o_to_t, o_t-1,…, o₁)=P(o_to_t),

то есть не зависит от времени.

две последовательности S=s₁ s₂... s_T и O=o₁o₂...o_T должны быть выровнены, т.е. каждое наблюдаемое событие o_t должно соответствовать одному скрытому событию s_t, т.е. значение наблюдаемой переменной y(t) зависит только от значения скрытой переменной x(t) (обе в момент времени t).

вычисление наиболее вероятной скрытой последовательности до момента t зависит только от наблюдаемого события в момент t, и наиболее вероятной последовательности до момента t?1.

Данные аксиомы определяют использование в качестве модели алгоритма скрытой марковской модели (Hidden Markov Model) HMM [8], пример диаграммы переходов которой приведена на Рис. 1,

=(X, Y, P, P^s, П).

В данной модели

1) На множестве скрытых состояний модели X={x_i}, i=, n-число состояний модели определяется скрытое состояние модели s_tS в момент t.

2) На множестве наблюдаемых значений Y={y_i}, i=, m-число различных символов наблюдения моделью может порождаться последовательность наблюдаемых значений, представленная в виде O=o₁o₂...o_T, где o_t - символ дискретного алфавита V={v_i}, состоящий из идентификаторов машинных команд v_i, T - число символов в наблюдаемой последовательности.

3) Распределение вероятностей переходов между состояниями (матрица переходных вероятностей) P=P_ij, где P_ij=P[s_t+1=x_js_t=x_i], 1j, in - вероятность перехода модели из состояния s_t=x_i в момент времени t в состояние s_t+1=x_j в следующий момент времени t+1.

4) Распределение вероятностей появления символов наблюдения в состоянии j, P^s=P_j(k), где P_j(k)=P[v_ks_t=x_j], 1jn, 1km.

5) Начальное распределение вероятностей состояний П={_i}, _i=P[s₁=x_i], где .

Рис. 1. Диаграмма переходов в HMM

В краткой форме HMM имеет вид =(P, P^s, П) и представляет собой дважды стохастический процесс, состоящий из пары случайных переменных {o₁,..., o_t, s₁,..., s_t}, где o_t - известные дискретные наблюдения, описывающие появление символов наблюдения (машинных команд), а s_t - «скрытые» дискретные величины, определяющие изменения состояния модели, но при этом не известно, сколько состояний и какие между ними связи (неизвестные параметры модели).

5. Стратегия синтеза алгоритма решения задачи

Принятая модель алгоритма определяет итеративную стратегию синтеза алгоритмов, которая сводится к преобразованию исходной модели =(P, P^s, П), приводящему к цели в виде оптимальной модели корректного алгоритма , путем итерационного пересчета параметров модели до схождения.

Постановка задачи. Известна наблюдаемая величина y(t) в виде последовательности Y_T=y₀, y₁,..., y_Т-1 длины Т, порождаемая последовательностью O=o₁o₂...o_T. Вероятность наблюдать y(t) равна P(Y_T)=, где сумма задаётся по всем возможным скрытым переменным x(t) в виде последовательности скрытых узлов X_T=x₀, x₁,..., x_Т-1. По имеющимся данным y(t) необходимо определить скрытые параметры наиболее вероятной последовательности состояний марковской цепи S=s_i1…s_iT.

Решение сформулированной задачи может быть достигнуто за три этапа, каждый из которых реализуется известным алгоритмом.

Первый этап: За T шагов в модели =(P, P^s, П) порождается последовательность наблюдений O_1,T=o₁,...,o_T, причем в момент t для состояния s: X_i=i вероятность P(O₁,_t-₁X_t=s) того, что во время переходов образовалась последовательность наблюдений O_1,t-₁, а P(O_t,TX_t=s) - вероятность того, что после этого состояния наблюдается последовательность наблюдений O_t,T.

Ищется вероятность P(X_t=sO)=P(X_t=sO₁,_t-₁O_t,T) того, что в момент t цепь будет в состоянии s.

1. Для произвольного состояния s в произвольный шаг t вероятность P(O_1,tX_t=s_i) того, что на пути к нему была произведена последовательность O_1,t для следующих t можно вычислить рекуррентно:

P(O_1,tX_t=s_i)=

=.

Вероятность попасть в состояние s на t-ом шаге, учитывая, что после перехода произойдет событие o_t будет равна вероятности быть в состоянии j на t-ом шаге, умноженной на вероятность перейти из состояния j в s, произведя событие o_t для всех jS.

2. Вероятность того, что после произвольного состояния s будет произведена последовательность O_t+1,T определяются рекуррентно:

P(O_t,TX_t=s)=.

3. Чтобы найти вероятность того, что будет произведена цепочка событий, P(O), нужно просуммировать произведение обеих вероятностей для всех состояний при произвольном шаге t:

P(O)=(O_1,tX_t=s)P(O_t,TX_t=s),

а поскольку будущее марковской цепи не зависит от прошлого и вероятность наблюдения события O_t не зависит от прошлых наблюдений последовательности O_1,t-1, то вероятность того, что в момент t цепь будет в состоянии s:

P(X_t=sO)=P(X_t=sO₁,_t-1O_t,T)=.

Данная задача решается с помощью алгоритма "вперед-назад" [9-11], который позволяет найти в скрытой марковской модели вероятность попадания в состояние s на t-ом шаге при последовательности наблюдений O и (скрытой) последовательности состояний X.

Второй этап: По заданной HMM с пространством состояний S={s₁, s₂,..., s_K}, начальными вероятностями _i нахождения в состоянии i и вероятностями P_i,j перехода из состояния i в состояние j, по наблюдаемым y₁,..., y_T и множества исходных информаций J_in ищется “оптимальная” наиболее правдоподобная последовательность состояний скрытых узлов S=s₁...s_T (путь Витерби), наиболее точно описывающую данную модель. Тогда наиболее вероятная последовательность состояний x₁,..., x_T задается рекуррентными соотношениями:

V_1,k=P(y₁k)_k, V_t,k=P(y_tk), (2)

где V_t,k - вероятность наиболее правдоподобной последовательности состояний, ответственной за появление первых t наблюдаемых символов, завершающейся в состоянии k. Путь Витерби ищется по состояниям x, удовлетворяющих уравнению (2), т.е.

x_T=

x_t-₁=

Для решения данной задачи используют алгоритм Витерби (Andrew Viterbi, 1967 год), позволяющего на основе последовательности наблюдений получить наиболее правдоподобную последовательность скрытых состояний (путь Витерби) скрытой марковской модели [12-15].

Третий этап: По заданной выходной последовательности наблюдений O определяются неизвестные параметры HMM , максимизирующие вероятность наблюдений O

^*=.

Причем число моментов времени r, в которых осуществляются наблюдения, устанавливается заранее и состоит из следующих шагов:

1) определение всех последовательностей состояний модели S_i={s_i1,…, s_ir}, i=1,…, r проблеморазрешающей системы в заданные моменты времени;

2) оценка вероятностей P(S_i) появления для каждой последовательности S_i, i=1,…, r, выявленной на предыдущем шаге, путём вычисления произведений вероятностей переходов между состояниями модели в течение интервалов, ограниченных установленными контрольными моментами времени, а именно:

P(S_i)=,

где P_s,i,t,t+1-вероятность перехода из состояния s_it, в котором система пребывала в момент времени t, в состояние s_i,t+1, занятого в момент t+1;

3) вероятность появления наблюдаемой последовательности X={x₁,…, x_r} для последовательностей состояний S_i, i=1,…, r

P_ix=P(S_i),

где P_x,i,j-вероятность получения наблюдаемой характеристики x_j при состоянии s_ij;

4) выбор наиболее вероятной последовательности состояний S_max{S_i}_i=1,...,r, соответствующей наибольшей вероятности

{P}_x,max=P_{ix i =1,...,r}.

Данный этап стратегии реализуется алгоритмом Баума-Велша (Baum - Welch algorithm) [10, 16].

Выводы

1. Содержательные аксиомы модели рандомизированного алгоритма допускают возможность использования в качестве модели алгоритма скрытой марковской модели (Hidden Markov Model) HMM, которая применима не только к исходным типовым алгоритмам, но и к корректирующим алгоритмам, а также и для синтезируемых композиций.

2. При вероятностной модели алгоритма появляется возможность управлять связями между переменными алгоритма, задавая гибкость алгоритма для обеспечения требуемой структурной и функциональной устойчивости программы, реализующей данный алгоритм.

3. Рандомизация алгоритма, повышая его гибкость и эффективность, не улучшает его риск по сравнению с соответствующим детерминированным алгоритмом.

4. Задача синтеза алгоритма на базе HMM заключается в том, чтобы по имеющимся наблюдаемым данным определяют скрытые параметры наиболее вероятной последовательности состояний.

5. На первом этапе стратегии при заданных параметрах модели =(P, P^s, П) и последовательности скрытых S и соответствующих наблюдаемых состояний О, определяется вероятность появления данных последовательностей. Так на первом шаге для модели и множества исходных данных D_in определяется _i=P(D_in) и оценивается насколько хорошо модель согласована к исходными данными. Данная задача в такой постановке решается с помощью алгоритма "вперед-назад", который позволяет найти в HMM вероятность попадания в состояние s_i на t-ом шаге при последовательности наблюдений O и (скрытой) последовательности состояний S.

6. На втором этапе по заданной скрытой марковской модели с пространством скрытых состояний S={s₁, s₂,..., s_K}, начальными вероятностями _i нахождения в состоянии i и вероятностями P_i,j перехода из состояния i в состояние j, по наблюдаемым состояниям o₁,..., o_T ищется путь Витерби S_V=s₁...s_T, наиболее точно описывающую данную модель, для чего естественно воспользоваться алгоритмом Витерби (Viterbi algorithm).

7. На третьем этапе стратегии осуществляется корректировка скрытых марковских моделей путем оптимизации параметров модели =(P, P^s, П) так, чтобы максимизировать P(O) при наблюдаемых данных 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.

Размещено на Allbest.ru