Методы построения и обработки скрытых марковских моделей, представленных в виде алгебраических байесовских сетей

Методы построения и обработки скрытых марковских моделей, представленных в виде алгебраических байесовских сетей[1]

, студент кафедры информатики СПбГУ, anton. *****@

Аннотация

Вероятностные графические модели (ВГМ) ― один из способов представления знаний с неопределённостью. Они успешно применяются для решения задач машинного обучения, в том числе благодаря тому, что есть развитые методы обработки этих моделей. Все ВГМ задают вероятностные распределения; часто удобно представлять одни ВГМ в виде других.

В докладе будут представлены методы декодирования скрытых состояний и обучения бинарной скрытой марковской модели, представленной в виде алгебраической байесовской сети.

Введение

Вероятностные графические модели (ВГМ) [2] задают распределения (семейства распределений) случайных величин с разреженными вероятностными зависимостями. К их числу принадлежат скрытые марковские модели (СММ), байесовские сети доверия, условные случайные поля, марковские сети и др. Ввиду близкой вероятностной природы некоторые модели можно представлять друг в виде друга. Известны примеры представления СММ в виде байесовских сетей доверия [1], классов байесовских сетей доверия в виде алгебраических байесовских сетей (АБС; логико-вероятностные графические модели) [11], СММ в виде АБС [6–9]. Так, обучив одну модель, можно обрабатывать полученные знания методами другой.

На данный момент для бинарных скрытых марковских моделей в виде алгебраических байесовских сетей (СММ-АБС) существуют:

1.  Алгоритм построения по скрытой марковской модели.

2.  Алгоритм решения задачи оценки правдоподобия последовательности наблюдений (методами логико-вероятностного вывода в АБС).

3.  Алгоритм декодирования последовательности скрытых состояний по последовательности наблюдений.

4.  Метод обучения по корпусу вида где ― скрытое состояние в момент а ― соответствующее наблюдение.

Цель предлагаемого доклада ― изложить методы №№ 3 и 4.

Скрытые марковские модели

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

Таким образом, скрытую марковскую модель можно задать как следующую тройку:

•  вектор вероятностей для первого состояния,

•  условные вероятности «переходов» из состояния в состояние,

•  вероятности «порождения» наблюдения состоянием.

В теории скрытых марковских моделей выделяют три ключевых задачи [4]: оценка правдоподобия данной последовательности наблюдений при данной модели (вычисление вероятности «порождения» наблюдений моделью), декодирование скрытых состояний по данной цепочке наблюдений (поиск наиболее вероятной последовательности состояний, которая могла «породить» данную последовательность наблюдений), обучение данной модели (настройка параметров модели таким образом, чтобы вероятность данной последовательности наблюдений была максимальна).

Алгебраические байесовские сети

В основе теории АБС лежит вероятностная логика Н. Нильссона [3]. Для задания вероятностных оценок истинности всех формул над высказываниями потребуется задать вероятностные оценки конъюнктов (элементарных конъюнкций без отрицаний). АБС ― набор моделей фрагментов знаний (то есть таких наборов конъюнктов с оценками) над некоторыми подмножествами множества заданных высказываний. Наиболее развитый на данный момент подход к обработке знаний в модели ― представление АБС как графа, вершины которого соответствуют фрагментам знаний. Существуют методы осуществления априорного вывода (вычисления оценок вероятностей формул над высказываниями из АБС) и апостериорного (байесовского) вывода (распространение свидетельств, то есть изменений оценок вероятностей, по сети). С перечисленным можно ознакомиться в работах [10–16].

Декодирование скрытой последовательности

Рассказ о второй задаче скрытых марковских моделей редко обходится без упоминания алгоритма Витерби [5]. Предлагаемый алгоритм также основан на методе динамического программирования.

Постановка задачи: по последовательности наблюдений восстановить наиболее вероятную последовательность скрытых состояний.

Обозначения:

•   ― функция, пропагирующая детерминированное свидетельство ;

•   ― функция, возвращающая вероятностную оценку истинности формулы, заданной , в сети ;

•  ― двухмерный массив, в котором будут храниться величины, которые нам понадобятся в процессе вычислений;

•  ― коллекция-словарь наиболее вероятных «префиксных траекторий» модели;

•  ― вспомогательная коллекция-словарь.

Алгоритм:

Require

1: for do

2:

3: end for

4: for

5:

6: end for

7: for

8:

9: for

10:

11:

12:

13: end for

14:

15: end for

16:

17: return

Шаги (1–3) ― распространение свидетельств

Шаги (4–6) ― записываем в нулевую строку матрицы апостериорные вероятности того, что на первом шаге мы о соответствующем состоянии.

В цикле (7–15) для каждого шага и состояния находим состояние предыдущего шага, на котором максимальна величина

записываем её в матрицу, а траекторию процесса, оказавшегося в момент в состоянии , задаём как .

На шаге 14 находим состояние , максимизирующее величину (наиболее вероятная траектория заканчивается в состоянии ).

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

Обучение СММ-АБС

Постановка задачи:

•  и ― множества состояний модели и наблюдений соответственно;

•  ― корпус данных для обучения, то есть набор «иных» пар «состояние–наблюдение» во времени.

Требуется построить СММ-АБС, эквивалентную СММ, обученной по этим данным.

Как и в случае СММ, будем считать, что условные вероятности «перехода» из состояния в состояние и «порождения» данным состоянием данного наблюдения постоянны.

Метод: будем считать, что оценки для и , где ― множество состояний, а ― множество наблюдений, нами уже получены (посредством ; см. ниже).

Обозначения:

•  ― переменная «АБС»,

•  ― «свойство», дающее доступ к вероятности истинности формулы в ,

•  ― «свойство», дающее доступ к вероятности истинности формулы с означиваниями высказываний, заданными списком ,

•  ― метод, синтезирующий фрагмент знаний с максимальным конъюнктом, заданным ,

•  , , ― массивы с соответствующими заданными заранее оценками вероятностей,

•  ― константы, причём ― ложь, ― истина,

•  ― число шагов.

Алгоритм:

Require:

Ensure:,

1:

2:

3:

4:

5:

6:

7:

8:

9: for do

10:

11:

12:

13:

14:

15: if then

16:

17: end if

18: end for

return

Комментарий:

•  в строках 1 и 2 задаются константы;

•  в строках 3–8 АБС abn инициализируется известными нам оценками, которые задают фрагмент знаний над алфавитом ; также задаётся вероятность конъюнкта ;

•  в строках 9–18 производится оценивание новых конъюнктов.

В качестве примера оценок вероятностей , , будут приведены относительные частоты соответствующих паттернов в корпусе.

Заключение

В докладе изложены методы декодирования скрытых состояний и обучения для бинарных СММ в виде АБС. Они демонстрируют выразительную силу алгебраических байесовских сетей и позволяют говорить о будущей «интервализации» скрытых марковских моделей.

Литература

1.  Cowell R. G., Dawid A. P., Lauritzen S. L., Spiegelhalter D. J. Probabilistic Networks and Expert Systems. NY.: Springer-Verlag, 19p.

2.  Koller D., Friedman N. Probabilistic Graphical Models. Principles and Techniques. Cambridge, Massachusetts, London: MIT Press, 20 pp.

3.  Nilsson N. J. Probabilistic Logic // Artificial Intelligence. 1986. Vol. 28. P. 71–87.

4.  Rabiner L. A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition // IEEE Proceedings. 1989. Vol. 77. No. 2. Pp. 257–286.

5.  Viterbi A. J. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. // Information Theory, IEEE Transactions on. 1967. Vol. 13. No. 2. Pp. 260–269.

6.  , ,  , Фильченков вероятности наблюдаемой последовательности в бинарных линейных по структуре скрытых марковских моделях с помощью апостериорного вывода в алгебраических байесовских сетях // Труды СПИИРАН. СПб: Наука, 2010. Вып. 2. C. 122–142.

7.  , , Фильченков бинарных линейных по структуре скрытых марковских моделей в виде алгебраических байесовских сетей // Труды СПИИРАН. СПб: Наука, 2010. Вып. 1. C. 134–150.

8.  Ревзин программ для представления и обработки ациклических скрытых марковских моделей на основе алгебраических байесовских сетей: Дипломная работа. Математико-механический факультет СПбГУ. 20с. (Санкт-Петербургский государственный университет).

9.  , , Тулупьев многозначных линейных по структуре скрытых марковских моделей в виде алгебраических байесовских сетей // Труды СПИИРАН. 2012. Вып. 20. С. 186–199.

10.  , , Сироткин сети: логико-вероятностный подход. СПб.: Наука, 20с.

11.  Тулупьев ациклических байесовских сетей доверия в алгебраические байесовские сети. // Известия высших учебных заведений: Приборостроение. 2009. Вып. 3, С. 21–23.

12.  , Сироткин байесовские сети: принцип декомпозиции и логико-вероятностный вывод в условиях неопределенности // Информационно-измерительные и управляющие системы. 2008. №10, Т. 6. С. 85-87 .

13.  , , Николенко сети доверия: логико-вероятностный вывод в ациклических направленных графах. СПб.: Изд-во С.-Петерб. ун-та, 2009, 400 с.

14.  , Тулупьев анализ систем минимальных графов смежности // Труды СПИИРАН. 2009. Вып. 11. С. 104–129.

15.  , , Сироткин анализа вторичной структуры алгебраической байесовской сети // Труды СПИИРАН. 2010. ВыпC. 97–118.

16.  , , Сироткин анализ клик минимальных графов смежности // Вестн. Тверск. гос. ун-та. Сер.: Прикладная математика. 2011. №20. С. 139–151.

[1] Работа выполнена при финансовой поддержке РФФИ, гранты № -a, -мол_а.