ПОВЫШЕНИЕ БЫСТРОДЕЙСТВИЯ АЛГОРИТМА ОЦЕНКИ НАБЛЮДАЕМОЙ ПОСЛЕДОВАТЕЛЬНОСТИ В СКРЫТЫХ МАРКОВСКИХ МОДЕЛЯХ НА ОСНОВЕ АЛГЕБРАИЧЕСКИХ БАЙЕСОВСКИХ СЕТЕЙ
М.Я. Пинский, А.В. Сироткин, А.Л. Тулупьев, А.А. Фильченков
5 КОМПЬЮТЕРНЫЕ СИСТЕМЫ И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ
УДК 004.8
ПОВЫШЕНИЕ БЫСТРОДЕЙСТВИЯ АЛГОРИТМА ОЦЕНКИ НАБЛЮДАЕМОЙ ПОСЛЕДОВАТЕЛЬНОСТИ В СКРЫТЫХ МАРКОВСКИХ МОДЕЛЯХ НА ОСНОВЕ АЛГЕБРАИЧЕСКИХ
БАЙЕСОВСКИХ СЕТЕЙ
М.Я. Пинский, А.В. Сироткин, А.Л. Тулупьев, А.А. Фильченков
Скрытые марковские модели и алгебраические байесовские сети представляют собой вероятностные графические модели, а потому во многом похожи. Скрытые марковские модели получили широкое применение, в то время как алгебраические байесовские сети пока не столь распространены, однако их аппарат позволяет моделировать и решать задачи скрытых марковских моделей. Рассмотрен вопрос ускорения решения первой задачи скрытых марковских моделей на основе методов, применяющихся в алгебраических байесовских сетях. Предложен алгоритм для оценки вероятности наблюдаемой последовательности в бинарных линейных по структуре скрытых марковских моделях с помощью апостериорного вывода алгебраической байесовской сети. Ключевые слова: скрытые марковские модели, алгебраические байесовские сети, бинарные линейные по структуре скрытые марковские модели, вероятностные графические модели.
Введение
Вероятностные графические модели – скрытые марковские модели (СММ) и алгебраические байесовские сети (АБС) – используются для изучения различных процессов в таких областях, как распознавание речи, теория информации, машинный перевод, молекулярная биология [1–6]. СММ – более развитый и широко известный инструмент для моделирования временны́ х рядов. Их используют во многих современных системах распознавания речи [4], в большинстве приложений вычислительной молекулярной биологии [7], в сжатии информации [8], в системах статистического машинного перевода [5], приложениях компьютерного зрения [9].
АБС – это одна из математических моделей баз фрагментов знаний с неопределенностью. Она формализует знания (с неопределенностью) при помощи вероятностной логики. Развитие аппарата АБС осуществлялось с 1980-х г.г., и на сегодняшний день в теории АБС существуют алгоритмы для решения различных задач, однако АБС все еще редко используются для практических целей [10]. На текущий момент АБС обладают развитым аппаратом логико-вероятностного вывода [11–15] и набором средств автоматического обучения, который находится на стадии развития [16–18].
Области применения АБС и СММ схожи, поэтому возникает вопрос о возможности представления одной модели через другую. Это может быть полезно для использования разработок, полученных в одной из них, для более широкого круга задач.
Цель работы – ускорение известного алгоритма [19] решения первой задачи для СММ с помощью апостериорного вывода АБС.
Скрытые марковские модели
Определения, связанные со СММ, будут вводиться по [2, 4, 6]. СММ – модель, состоящая из следующих объектов:
1. набор возможных значений скрытых состояний S s1, s2,sN ; 2. последовательность скрытых состояний во времени Q q1, q2,qT ;
3. матрица переходных вероятностей A aij , aij P qt 1 s j qt si , 1 i, j N;
4. вектор начального распределения π πi , πi Pq1 si , 1 i N ; 5. алфавит возможных значений наблюдений V v1,v2,vM ; 6. последовательность наблюдений во времени O o1,o2,oT ;
7. матрица вероятностей наблюдений B b j k , b j (k) P vk ot s j qt , 1 j N , 1 k M ,
и обладающая следующими свойствами:
1. P qt 1 qt , qt 1, qt 2 , , q1 P qt 1 qt – марковское свойство; 2. Pot o1, oT , q1, , qT Pot qt – зависимость текущего наблюдения только от текущего состояния,
где O o1,o2,oT , Q q1, q2,qT – последовательности наблюдений и состояний соответственно.
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2011, № 5 (75)
69
ПОВЫШЕНИЕ БЫСТРОДЕЙСТВИЯ АЛГОРИТМА ОЦЕНКИ НАБЛЮДАЕМОЙ...
В расчетах, связанных со СММ, пользуются представлением СММ в виде набора матриц вероят-
ностей: μ A, B, π.
В теории СММ сформулированы три основных задачи. 1. Правдоподобие наблюдений. Дана СММ с известными матрицами вероятностей. Определить вероят-
ность поступающей последовательности наблюдений во времени относительно этой СММ.
Формальная постановка задачи: дана последовательность наблюдений O o1,o2,oT и модель μ A, B, π . PO μ ? Для данной задачи существуют различные решения, например алгоритм
«вперед-назад» [19]. 2. Декодирование скрытой последовательности. Даны СММ с оценками вероятности и поступившая
последовательность наблюдений. Требуется определить наиболее вероятную последовательность скрытых состояний. Формальная формулировка задачи: дана последовательность наблюдений
O o1,o2,oT и модель μ A, B, π. Найти наиболее вероятную последовательность скрытых состояний Q q1, q2,qT , соответствующую данной последовательности наблюдений. Данная задача
решается с помощью алгоритма Витерби [20]. 3. Обучение СММ. Изменить (настроить) матрицы вероятностей СММ таким образом, чтобы максими-
зировать вероятности поступающего набора последовательностей наблюдений. Иначе говоря, требуется обучить СММ на наборе тренировочных последовательностей наблюдений. Формальная форму-
лировка задачи: настроить параметры модели μ A, B, π так, чтобы максимизировать P O μ . Дан-
ную задачу можно решать с помощью алгоритма Баума–Вэлха [21]. Для преобразования в АБС в работе будем использовать бинарные линейные по структуре СММ.
Это такие СММ, у которых могут быть только два скрытых состояния S s1, s2 и два вида наблюде-
ний V v1, v2 . В последнем будет иметь место S V 0,1 {true, false} .
Алгебраические байесовские сети
Определения, связанные с теорией АБС, будут вводиться по [10, 22]. АБС – логико-вероятностная графическая модель баз фрагментов знаний с неопределенностью [10]. Фрагмент знаний представляется в виде идеала конъюнктов с оценками их истинности.
Пусть T – конечный набор элементарных пропозиций; S s1, s2,, sk – непустое подмножество
T ; S v1v2 vr : v1,v2 vr S, r 0k – конъюнкты (множество положительно означенных конъ-
юнкций над S ); S S e – идеал конъюнкта (множество положительно означенных конъюнктов без
пустого конъюнкта). В идеале существует один максимальный элемент (максимальная по длине конъюнкция) и множество минимальных элементов (одноатомных конъюнкций).
Квант Q ~x0~x1~xn1 – конъюнкция, которая для любой атомарной переменной из алфавита со-
держит либо ее формулу, либо отрицание. Теперь введем нумерацию на конъюнктах и квантах. Каждому конъюнкту из идеала
xi1 xi2 xik 0 i1 ik n 1, k n можно сопоставить номер вида 2i1 2i2 2ik . Обозначим че-
рез ci конъюнкт с порядковым номером i. Выделим из кванта положительную часть. Номер получивше-
гося конъюнкта будет номером кванта. Обозначим через qi квант с порядковым номером i. Далее введем вероятность на конъюнктах и квантах. Вероятности, относящиеся к фрагменту зна-
ний, удобно упорядочивать по номерам конъюнктов и квантов и представлять в виде векторов. Выделяют две структуры алгебраических байесовских сетей – первичную и вторичную. Первичная структура АБС – это база фрагментов знаний (ФЗ). Вторичная структура АБС – это связи между ФЗ. Вторичная структура АБС определяется набором вершин и набором ребер между ними. Вершины – это фрагменты знаний, они однозначно задаются глобальным индексом минимального конъюнкта. Ребра однозначно задаются двумя вершинами.
Представление бинарных линейных по структуре СММ в виде АБС
Представление вводится по [23], где приведено формальное доказательство корректности сведения бинарных линейных по структуре СММ к АБС. Отметим, что любая СММ может быть приведена к АБС серией аналогичных преобразований. Рассмотрим простейшую линейную бинарную СММ в четыре мо-
мента времени (рис. 1). Матрицы данной модели μ A, B, π будут иметь следующий вид:
A
a00 a10
a01 a11
p(xi p(xi
xi ) xi )
p(xi p(xi
xi xi
) )
,
B
b0 (v0 ) b1(v0 )
b0 (v1) b1(v1)
p(oi p(oi
xi ) xi )
p(oi p(oi
xi xi
) )
,
π
π0 π1
p(xi p(xi
) )
.
70 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2011, № 5 (75)
М.Я. Пинский, А.В. Сироткин, А.Л. Тулупьев, А.А. Фильченков
p x1 x0 p x2 x1
p x3 x2
x0 x1 x2 x3
p o0 x0
p o1 x1 p o2 x2
p o3 x3
o0 o1 o2 o3
Рис. 1. Линейная бинарная СММ в четыре момента времени
Теперь построим АБС, соответствующую рассмотренной СММ (рис. 2).
Для нумерации вершин необходимо ввести алфавит. В алфавите соответствующей АБС будем че-
редовать o i и xi , начиная с i 0 : o0, x0, o1, x1,oN 1, xN 1.
x0x1 р(x0x1)
x1x2 р(x1x2)
x2x3 р(x2x3)
x0 р(x0)
x1 р(x1)
x2 р(x2)
x3 р(x3)
р(оо00)
о1 р(о1)
ро(о2 2)
о3 р(о3)
о0x0 р(о0x0)
о1x1 р(о1x1)
о2x2 р(о2x2)
о3x3 р(о3x3)
Рис. 2. АБС, соответствующая рассмотренной СММ. (Серым отмечены узлы, соответствующие одноатомным конъюнктам, белым – соответствующие двухатомным конъюнктам)
p(e)
p x0
p x1
p(x0 x1 )
p(e)
p x1
p x2 p(x1x2
)
p(e)
p x2
p x3
p(x2 x3)
p(e)
p o0
p x0
p(o0x0 )
p(e)
p o1
p x1
p(o1 x1 )
p(e)
p o2
p x2
p(o2 x2 )
p(e)
p o3
p x3
p(o3 x3 )
Рис. 3. Соответствующая АБС, изображенная как база ФЗ; изображены узлы и векторы вероятностей в них
Данная АБС будет содержать ФЗ вида
oi
,
xi
,xi
,
xi
1
N 2 i0
,oN
1,
xN
1
(рис. 3).
Решение первой задачи для СММ через АБС
В ходе исследований удалось установить, что первая задача для СММ эквивалентна первой задаче апостериорного вывода для АБС [4].
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2011, № 5 (75)
71
ПОВЫШЕНИЕ БЫСТРОДЕЙСТВИЯ АЛГОРИТМА ОЦЕНКИ НАБЛЮДАЕМОЙ...
Первая задача СММ: Дана последовательность наблюдений O {o1, o2,...oT } и модель μ ( A, B, π) . Какова вероятность наблюдаемой последовательности при условии данной модели
P(O | μ) ?
В терминах АБС данная задача будет формулироваться следующим образом. Поступает детерминированное свидетельство, например e o~0o~1o~2...o~T , каким-то образом означенное. Требуется оценить
вероятность данного свидетельства P(e) ?
Рассмотрим какое-либо конкретно-означенное детерминированное свидетельство e o~0o~1o~2...o~T . В
теории АБС стандартный алгоритм первой задачи апостериорного вывода может пропагировать (распро-
странять влияние) только свидетельство, полностью лежащее в ФЗ. Данное принадлежит T 1 фрагмен-
ту знаний. Совершим преобразование, воспользовавшись правилом Байеса:
P(o~0o~1o~2...o~T ) P(o~0 | o~1o~2...o~T
P) (Po~0(oo~~11o~|2o~.2...o~..To~T1)|o~..T.)P (Po~(To~T1)|
... o~T )
P(o~T
).
Теперь исходная вероятность состоит из произведения вероятностей свидетельств, полностью ле-
жащих в соответствующих ФЗ. Будем пропагировать, начиная с крайнего правого подсвидетельства ( o~T ). Оно будет поступать на вход к ФЗ o~T xT . После его пропагации на соседний ФЗ, он будет иметь новые апостериорные оценки вероятностей Po~T (...) . Для этих оценок вероятностей будем пропагировать
o~T 1 , поступающее в ФЗ o~T 1xT 1 , которое снова изменит оценки вероятностей для следующего ФЗ на апостериорные Po~T o~T 1 (...) , и т.д. Каждый раз будем пропагировать на соседний ФЗ единичные подсви-
детельства, двигаясь справа налево. В конце останется только перемножить вероятности единичных подсвидетельств. Данный алгоритм эквивалентен описанному в [1], так как свидетельство достаточно пропагировать только на следующий ФЗ. Его апостериорная оценка изменит оценки следующих свидетельств так же, как если бы свидетельство пропагировали на всю сеть, потому что для любого ФЗ o~i xi справед-
ливо соотношение P(o~i | o~i1...o~T ) P(o~i | o~i1)P(o~i1 | o~i2...o~T ).
Заключение
Известно, что СММ могут быть представлены как частный случай динамических байесовских сетей доверия, которые, в свою очередь, могут быть преобразованы в АБС. Отсюда возник естественный вопрос о прямой связи между СММ и АБС, который и был частично изучен в данной работе.
В работе приведены теория СММ, в том числе первая задача СММ, теория АБС, в частности, апостериорный вывод АБС, а также представление бинарной линейной по структуре СММ в виде АБС. Доказана эквивалентность апостериорного вывода для АБС и первой задачи СММ. Дан улучшенный (ускоренный) по сравнению с [19] алгоритм решения первой задачи СММ, состоящей в оценке вероятности последовательности наблюдений, в терминах апостериорного вывода АБС. Сложность была уменьшена в
n раз, где n – количество состояний в СММ. Таким образом, приведенный алгоритм решения работает
за полиномиальное от длины входа время. Точную оценку установить не представляется возможным, так как вопрос сложности пропагации свидетельств на данный момент недостаточно изучен.
Первая задача была решена через АБС, что является примером использования АБС в теории СММ и может упростить дальнейшее развитие теории АБС в применении к СММ. Однако для этого необходимо проведение исследований. За рамками работы остаются вопросы, связанные со второй и третьей задачами СММ, которые также разрешимы в теории АБС, однако еще не было создано конкретных алгоритмов решения.
Работа выполнена при финансовой поддержке РФФИ, проект № 09-01-00861-а «Методология построения интеллектуальных систем поддержки принятия решений на основе баз фрагментов знаний с вероятностной неопределенностью».
Литература
1. Николенко С.И., Тулупьев А.Л. Самообучающиеся системы. – М.: МНЦМО, 2009. – 288 с. 2. Cowell R.G., Dawid A.P., Lauritzen S.L., Spiegelhalter D.J. Probabilistic Networks and Expert Systems. –
NY: Springer-Verlag, 1999. – 321 p. 3. Huang X., Acero A., Hsiao-Wuen Hon Spoken Language Processing. – Prentice Hall, 2001. – 1008 p. 4. Huang X., Jack M. and Y. Ariki. Hidden Markov Models for Speech Recognition. – Edinburgh University
Press, 1990. – 276 p. 5. Jurafsky D., Martin J.H. Speech and Language Processing: An Introduction to Natural Language Processing,
Speech Recognition, and Computational Linguistics. – 2-d edition. – Prentice-Hall, 2009. – 944 p.
72 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2011, № 5 (75)
М.Я. Пинский, А.В. Сироткин, А.Л. Тулупьев, А.А. Фильченков
6. Stengel M. Introduction to Graphical Models, Hidden Markov Models and Bayesian Networks. Department of Information and Computer Sciences Toyohashi University of Technology Toyohashi, 441-8580. – Japan, 2003. – 46 p.
7. da-Silva C.Q. Hidden Markov models applied to a subsequence of the Xylella fastidiosa genome // Genet. Mol. Biol. – São Paulo, Dec. 2003. – V. 26. – № 4. – Р. 529–535.
8. Li J., Gray R.M. Image Segmentation and Compression Using Hidden Markov Models. – 1-st edition. – Springer, 2000. – 141 p.
9. Bunke H., Caelli T. Hidden Markov Models Applications in Computer Vision. Series in Machine Perception and Artificial Intelligence. – World Scientific, 2001. – V. 45. – 244 p.
10. Тулупьев А.В., Николенко С.И., Сироткин А.В. Байесовские сети: логико-вероятностный подход. – СПб: Наука, 2006. – 608 с.
11. Сироткин А.В. Модели, алгоритмы и вычислительная сложность синтеза согласованных оценок истинности в алгебраических байесовских сетях // Информационно-измерительные и управляющие системы. – 2009. – № 11. – С. 32–37.
12. Тулупьев А.Л. Алгебраические байесовские сети: реализация логико-вероятностного вывода в комплексе java-программ // Труды СПИИРАН. – СПб: Наука, 2009. – Вып. 8. – С. 191–232.
13. Тулупьев А.Л. Алгебраические байесовские сети: система операций глобального логиковероятностного вывода // Информационно-измерительные и управляющие системы. – 2010. – № 11. – С. 65–72.
14. Тулупьев А.Л. Апостериорные оценки вероятностей в идеале конъюнктов // Вестник СПбГУ. – 2010. – Сер. 10. – Вып. 1. – С. 95–104.
15. Тулупьев А.Л., Сироткин А.В., Николенко С.И. Байесовские сети доверия: логико-вероятностный вывод в ациклических направленных графах. – СПб: Изд-во СПбГУ, 2009. – 400 с.
16. Опарин В.В., Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Матроидное представление семейства графов смежности над набором фрагментов знаний // Научно-технический вестник СПбГУ ИТМО. – 2010. – № 4. – C. 73–76.
17. Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Компаративный анализ клик минимальных графов смежности алгебраических байесовских сетей // Труды СПИИРАН. – СПб: Наука, 2010. – Вып. 2. – С. 87–105.
18. Тулупьев А.Л. Задача локального автоматического обучения в алгебраических байесовских сетях: логико-вероятностный подход // Труды СПИИРАН. – СПб: Наука, 2008. – Вып. 7. – С. 11–25.
19. Момзикова М.П., Великодная О.И., Пинский М.Я., Сироткин А.В., Тулупьев А.Л., Фильченков А.А. Оценка вероятности наблюдаемой последовательности в бинарных линейных по структуре скрытых марковских моделях с помощью апостериорного вывода в алгебраических байесовских сетях // Труды СПИИРАН. – СПб: Наука, 2010. – Вып. 2. – C. 122–142.
20. Forney D.G. The Viterbi Algorithm // Proceedings of the IEEE. – 1973. – V. 61. – № 3. – Р. 268–278. 21. Welch L.R. Hidden Markov Models and the Baum-Welch Algorithm // IEEE Information Theory Society
Newsletter. – 2003. –V. 53. – № 4. – Р. 10–13. 22. Тулупьев А.Л. Алгебраические байесовские сети. Логико-вероятностный подход к моделированию
баз знаний с неопределенностью. – СПб: СПИИРАН, 2000. – 292 с. 23. Момзикова М.П., Великодная О.И., Пинский М.Я., Сироткин А.В., Тулупьев А.Л., Фильченков А.А.
Представление бинарных линейных по структуре скрытых марковских моделей в виде алгебраических байесовских сетей // Труды СПИИРАН. – СПб: Наука, 2010. – Вып. 1. – C. 134–150.
Пинский Михаил Яковлевич
– Санкт-Петербургский государственный университет информацион-
ных технологий, механики и оптики, студент,
mikhailpinsky@gmail.com
Сироткин Александр Владимирович – Санкт-Петербургский институт информатики и автоматизации РАН,
мл. научный сотрудник, alexander.sirotkin@gmail.com
Тулупьев Александр Львович
– Санкт-Петербургский институт информатики и автоматизации РАН,
доктор физ.-мат. наук, доцент, зав. лабораторией,
alexander.tulupyev@gmail.com
Фильченков Андрей Александрович
– Санкт-Петербургский институт информатики и автоматизации РАН,
мл. научный сотрудник, aaafil@mail.ru
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2011, № 5 (75)
73
5 КОМПЬЮТЕРНЫЕ СИСТЕМЫ И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ
УДК 004.8
ПОВЫШЕНИЕ БЫСТРОДЕЙСТВИЯ АЛГОРИТМА ОЦЕНКИ НАБЛЮДАЕМОЙ ПОСЛЕДОВАТЕЛЬНОСТИ В СКРЫТЫХ МАРКОВСКИХ МОДЕЛЯХ НА ОСНОВЕ АЛГЕБРАИЧЕСКИХ
БАЙЕСОВСКИХ СЕТЕЙ
М.Я. Пинский, А.В. Сироткин, А.Л. Тулупьев, А.А. Фильченков
Скрытые марковские модели и алгебраические байесовские сети представляют собой вероятностные графические модели, а потому во многом похожи. Скрытые марковские модели получили широкое применение, в то время как алгебраические байесовские сети пока не столь распространены, однако их аппарат позволяет моделировать и решать задачи скрытых марковских моделей. Рассмотрен вопрос ускорения решения первой задачи скрытых марковских моделей на основе методов, применяющихся в алгебраических байесовских сетях. Предложен алгоритм для оценки вероятности наблюдаемой последовательности в бинарных линейных по структуре скрытых марковских моделях с помощью апостериорного вывода алгебраической байесовской сети. Ключевые слова: скрытые марковские модели, алгебраические байесовские сети, бинарные линейные по структуре скрытые марковские модели, вероятностные графические модели.
Введение
Вероятностные графические модели – скрытые марковские модели (СММ) и алгебраические байесовские сети (АБС) – используются для изучения различных процессов в таких областях, как распознавание речи, теория информации, машинный перевод, молекулярная биология [1–6]. СММ – более развитый и широко известный инструмент для моделирования временны́ х рядов. Их используют во многих современных системах распознавания речи [4], в большинстве приложений вычислительной молекулярной биологии [7], в сжатии информации [8], в системах статистического машинного перевода [5], приложениях компьютерного зрения [9].
АБС – это одна из математических моделей баз фрагментов знаний с неопределенностью. Она формализует знания (с неопределенностью) при помощи вероятностной логики. Развитие аппарата АБС осуществлялось с 1980-х г.г., и на сегодняшний день в теории АБС существуют алгоритмы для решения различных задач, однако АБС все еще редко используются для практических целей [10]. На текущий момент АБС обладают развитым аппаратом логико-вероятностного вывода [11–15] и набором средств автоматического обучения, который находится на стадии развития [16–18].
Области применения АБС и СММ схожи, поэтому возникает вопрос о возможности представления одной модели через другую. Это может быть полезно для использования разработок, полученных в одной из них, для более широкого круга задач.
Цель работы – ускорение известного алгоритма [19] решения первой задачи для СММ с помощью апостериорного вывода АБС.
Скрытые марковские модели
Определения, связанные со СММ, будут вводиться по [2, 4, 6]. СММ – модель, состоящая из следующих объектов:
1. набор возможных значений скрытых состояний S s1, s2,sN ; 2. последовательность скрытых состояний во времени Q q1, q2,qT ;
3. матрица переходных вероятностей A aij , aij P qt 1 s j qt si , 1 i, j N;
4. вектор начального распределения π πi , πi Pq1 si , 1 i N ; 5. алфавит возможных значений наблюдений V v1,v2,vM ; 6. последовательность наблюдений во времени O o1,o2,oT ;
7. матрица вероятностей наблюдений B b j k , b j (k) P vk ot s j qt , 1 j N , 1 k M ,
и обладающая следующими свойствами:
1. P qt 1 qt , qt 1, qt 2 , , q1 P qt 1 qt – марковское свойство; 2. Pot o1, oT , q1, , qT Pot qt – зависимость текущего наблюдения только от текущего состояния,
где O o1,o2,oT , Q q1, q2,qT – последовательности наблюдений и состояний соответственно.
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2011, № 5 (75)
69
ПОВЫШЕНИЕ БЫСТРОДЕЙСТВИЯ АЛГОРИТМА ОЦЕНКИ НАБЛЮДАЕМОЙ...
В расчетах, связанных со СММ, пользуются представлением СММ в виде набора матриц вероят-
ностей: μ A, B, π.
В теории СММ сформулированы три основных задачи. 1. Правдоподобие наблюдений. Дана СММ с известными матрицами вероятностей. Определить вероят-
ность поступающей последовательности наблюдений во времени относительно этой СММ.
Формальная постановка задачи: дана последовательность наблюдений O o1,o2,oT и модель μ A, B, π . PO μ ? Для данной задачи существуют различные решения, например алгоритм
«вперед-назад» [19]. 2. Декодирование скрытой последовательности. Даны СММ с оценками вероятности и поступившая
последовательность наблюдений. Требуется определить наиболее вероятную последовательность скрытых состояний. Формальная формулировка задачи: дана последовательность наблюдений
O o1,o2,oT и модель μ A, B, π. Найти наиболее вероятную последовательность скрытых состояний Q q1, q2,qT , соответствующую данной последовательности наблюдений. Данная задача
решается с помощью алгоритма Витерби [20]. 3. Обучение СММ. Изменить (настроить) матрицы вероятностей СММ таким образом, чтобы максими-
зировать вероятности поступающего набора последовательностей наблюдений. Иначе говоря, требуется обучить СММ на наборе тренировочных последовательностей наблюдений. Формальная форму-
лировка задачи: настроить параметры модели μ A, B, π так, чтобы максимизировать P O μ . Дан-
ную задачу можно решать с помощью алгоритма Баума–Вэлха [21]. Для преобразования в АБС в работе будем использовать бинарные линейные по структуре СММ.
Это такие СММ, у которых могут быть только два скрытых состояния S s1, s2 и два вида наблюде-
ний V v1, v2 . В последнем будет иметь место S V 0,1 {true, false} .
Алгебраические байесовские сети
Определения, связанные с теорией АБС, будут вводиться по [10, 22]. АБС – логико-вероятностная графическая модель баз фрагментов знаний с неопределенностью [10]. Фрагмент знаний представляется в виде идеала конъюнктов с оценками их истинности.
Пусть T – конечный набор элементарных пропозиций; S s1, s2,, sk – непустое подмножество
T ; S v1v2 vr : v1,v2 vr S, r 0k – конъюнкты (множество положительно означенных конъ-
юнкций над S ); S S e – идеал конъюнкта (множество положительно означенных конъюнктов без
пустого конъюнкта). В идеале существует один максимальный элемент (максимальная по длине конъюнкция) и множество минимальных элементов (одноатомных конъюнкций).
Квант Q ~x0~x1~xn1 – конъюнкция, которая для любой атомарной переменной из алфавита со-
держит либо ее формулу, либо отрицание. Теперь введем нумерацию на конъюнктах и квантах. Каждому конъюнкту из идеала
xi1 xi2 xik 0 i1 ik n 1, k n можно сопоставить номер вида 2i1 2i2 2ik . Обозначим че-
рез ci конъюнкт с порядковым номером i. Выделим из кванта положительную часть. Номер получивше-
гося конъюнкта будет номером кванта. Обозначим через qi квант с порядковым номером i. Далее введем вероятность на конъюнктах и квантах. Вероятности, относящиеся к фрагменту зна-
ний, удобно упорядочивать по номерам конъюнктов и квантов и представлять в виде векторов. Выделяют две структуры алгебраических байесовских сетей – первичную и вторичную. Первичная структура АБС – это база фрагментов знаний (ФЗ). Вторичная структура АБС – это связи между ФЗ. Вторичная структура АБС определяется набором вершин и набором ребер между ними. Вершины – это фрагменты знаний, они однозначно задаются глобальным индексом минимального конъюнкта. Ребра однозначно задаются двумя вершинами.
Представление бинарных линейных по структуре СММ в виде АБС
Представление вводится по [23], где приведено формальное доказательство корректности сведения бинарных линейных по структуре СММ к АБС. Отметим, что любая СММ может быть приведена к АБС серией аналогичных преобразований. Рассмотрим простейшую линейную бинарную СММ в четыре мо-
мента времени (рис. 1). Матрицы данной модели μ A, B, π будут иметь следующий вид:
A
a00 a10
a01 a11
p(xi p(xi
xi ) xi )
p(xi p(xi
xi xi
) )
,
B
b0 (v0 ) b1(v0 )
b0 (v1) b1(v1)
p(oi p(oi
xi ) xi )
p(oi p(oi
xi xi
) )
,
π
π0 π1
p(xi p(xi
) )
.
70 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2011, № 5 (75)
М.Я. Пинский, А.В. Сироткин, А.Л. Тулупьев, А.А. Фильченков
p x1 x0 p x2 x1
p x3 x2
x0 x1 x2 x3
p o0 x0
p o1 x1 p o2 x2
p o3 x3
o0 o1 o2 o3
Рис. 1. Линейная бинарная СММ в четыре момента времени
Теперь построим АБС, соответствующую рассмотренной СММ (рис. 2).
Для нумерации вершин необходимо ввести алфавит. В алфавите соответствующей АБС будем че-
редовать o i и xi , начиная с i 0 : o0, x0, o1, x1,oN 1, xN 1.
x0x1 р(x0x1)
x1x2 р(x1x2)
x2x3 р(x2x3)
x0 р(x0)
x1 р(x1)
x2 р(x2)
x3 р(x3)
р(оо00)
о1 р(о1)
ро(о2 2)
о3 р(о3)
о0x0 р(о0x0)
о1x1 р(о1x1)
о2x2 р(о2x2)
о3x3 р(о3x3)
Рис. 2. АБС, соответствующая рассмотренной СММ. (Серым отмечены узлы, соответствующие одноатомным конъюнктам, белым – соответствующие двухатомным конъюнктам)
p(e)
p x0
p x1
p(x0 x1 )
p(e)
p x1
p x2 p(x1x2
)
p(e)
p x2
p x3
p(x2 x3)
p(e)
p o0
p x0
p(o0x0 )
p(e)
p o1
p x1
p(o1 x1 )
p(e)
p o2
p x2
p(o2 x2 )
p(e)
p o3
p x3
p(o3 x3 )
Рис. 3. Соответствующая АБС, изображенная как база ФЗ; изображены узлы и векторы вероятностей в них
Данная АБС будет содержать ФЗ вида
oi
,
xi
,xi
,
xi
1
N 2 i0
,oN
1,
xN
1
(рис. 3).
Решение первой задачи для СММ через АБС
В ходе исследований удалось установить, что первая задача для СММ эквивалентна первой задаче апостериорного вывода для АБС [4].
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2011, № 5 (75)
71
ПОВЫШЕНИЕ БЫСТРОДЕЙСТВИЯ АЛГОРИТМА ОЦЕНКИ НАБЛЮДАЕМОЙ...
Первая задача СММ: Дана последовательность наблюдений O {o1, o2,...oT } и модель μ ( A, B, π) . Какова вероятность наблюдаемой последовательности при условии данной модели
P(O | μ) ?
В терминах АБС данная задача будет формулироваться следующим образом. Поступает детерминированное свидетельство, например e o~0o~1o~2...o~T , каким-то образом означенное. Требуется оценить
вероятность данного свидетельства P(e) ?
Рассмотрим какое-либо конкретно-означенное детерминированное свидетельство e o~0o~1o~2...o~T . В
теории АБС стандартный алгоритм первой задачи апостериорного вывода может пропагировать (распро-
странять влияние) только свидетельство, полностью лежащее в ФЗ. Данное принадлежит T 1 фрагмен-
ту знаний. Совершим преобразование, воспользовавшись правилом Байеса:
P(o~0o~1o~2...o~T ) P(o~0 | o~1o~2...o~T
P) (Po~0(oo~~11o~|2o~.2...o~..To~T1)|o~..T.)P (Po~(To~T1)|
... o~T )
P(o~T
).
Теперь исходная вероятность состоит из произведения вероятностей свидетельств, полностью ле-
жащих в соответствующих ФЗ. Будем пропагировать, начиная с крайнего правого подсвидетельства ( o~T ). Оно будет поступать на вход к ФЗ o~T xT . После его пропагации на соседний ФЗ, он будет иметь новые апостериорные оценки вероятностей Po~T (...) . Для этих оценок вероятностей будем пропагировать
o~T 1 , поступающее в ФЗ o~T 1xT 1 , которое снова изменит оценки вероятностей для следующего ФЗ на апостериорные Po~T o~T 1 (...) , и т.д. Каждый раз будем пропагировать на соседний ФЗ единичные подсви-
детельства, двигаясь справа налево. В конце останется только перемножить вероятности единичных подсвидетельств. Данный алгоритм эквивалентен описанному в [1], так как свидетельство достаточно пропагировать только на следующий ФЗ. Его апостериорная оценка изменит оценки следующих свидетельств так же, как если бы свидетельство пропагировали на всю сеть, потому что для любого ФЗ o~i xi справед-
ливо соотношение P(o~i | o~i1...o~T ) P(o~i | o~i1)P(o~i1 | o~i2...o~T ).
Заключение
Известно, что СММ могут быть представлены как частный случай динамических байесовских сетей доверия, которые, в свою очередь, могут быть преобразованы в АБС. Отсюда возник естественный вопрос о прямой связи между СММ и АБС, который и был частично изучен в данной работе.
В работе приведены теория СММ, в том числе первая задача СММ, теория АБС, в частности, апостериорный вывод АБС, а также представление бинарной линейной по структуре СММ в виде АБС. Доказана эквивалентность апостериорного вывода для АБС и первой задачи СММ. Дан улучшенный (ускоренный) по сравнению с [19] алгоритм решения первой задачи СММ, состоящей в оценке вероятности последовательности наблюдений, в терминах апостериорного вывода АБС. Сложность была уменьшена в
n раз, где n – количество состояний в СММ. Таким образом, приведенный алгоритм решения работает
за полиномиальное от длины входа время. Точную оценку установить не представляется возможным, так как вопрос сложности пропагации свидетельств на данный момент недостаточно изучен.
Первая задача была решена через АБС, что является примером использования АБС в теории СММ и может упростить дальнейшее развитие теории АБС в применении к СММ. Однако для этого необходимо проведение исследований. За рамками работы остаются вопросы, связанные со второй и третьей задачами СММ, которые также разрешимы в теории АБС, однако еще не было создано конкретных алгоритмов решения.
Работа выполнена при финансовой поддержке РФФИ, проект № 09-01-00861-а «Методология построения интеллектуальных систем поддержки принятия решений на основе баз фрагментов знаний с вероятностной неопределенностью».
Литература
1. Николенко С.И., Тулупьев А.Л. Самообучающиеся системы. – М.: МНЦМО, 2009. – 288 с. 2. Cowell R.G., Dawid A.P., Lauritzen S.L., Spiegelhalter D.J. Probabilistic Networks and Expert Systems. –
NY: Springer-Verlag, 1999. – 321 p. 3. Huang X., Acero A., Hsiao-Wuen Hon Spoken Language Processing. – Prentice Hall, 2001. – 1008 p. 4. Huang X., Jack M. and Y. Ariki. Hidden Markov Models for Speech Recognition. – Edinburgh University
Press, 1990. – 276 p. 5. Jurafsky D., Martin J.H. Speech and Language Processing: An Introduction to Natural Language Processing,
Speech Recognition, and Computational Linguistics. – 2-d edition. – Prentice-Hall, 2009. – 944 p.
72 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2011, № 5 (75)
М.Я. Пинский, А.В. Сироткин, А.Л. Тулупьев, А.А. Фильченков
6. Stengel M. Introduction to Graphical Models, Hidden Markov Models and Bayesian Networks. Department of Information and Computer Sciences Toyohashi University of Technology Toyohashi, 441-8580. – Japan, 2003. – 46 p.
7. da-Silva C.Q. Hidden Markov models applied to a subsequence of the Xylella fastidiosa genome // Genet. Mol. Biol. – São Paulo, Dec. 2003. – V. 26. – № 4. – Р. 529–535.
8. Li J., Gray R.M. Image Segmentation and Compression Using Hidden Markov Models. – 1-st edition. – Springer, 2000. – 141 p.
9. Bunke H., Caelli T. Hidden Markov Models Applications in Computer Vision. Series in Machine Perception and Artificial Intelligence. – World Scientific, 2001. – V. 45. – 244 p.
10. Тулупьев А.В., Николенко С.И., Сироткин А.В. Байесовские сети: логико-вероятностный подход. – СПб: Наука, 2006. – 608 с.
11. Сироткин А.В. Модели, алгоритмы и вычислительная сложность синтеза согласованных оценок истинности в алгебраических байесовских сетях // Информационно-измерительные и управляющие системы. – 2009. – № 11. – С. 32–37.
12. Тулупьев А.Л. Алгебраические байесовские сети: реализация логико-вероятностного вывода в комплексе java-программ // Труды СПИИРАН. – СПб: Наука, 2009. – Вып. 8. – С. 191–232.
13. Тулупьев А.Л. Алгебраические байесовские сети: система операций глобального логиковероятностного вывода // Информационно-измерительные и управляющие системы. – 2010. – № 11. – С. 65–72.
14. Тулупьев А.Л. Апостериорные оценки вероятностей в идеале конъюнктов // Вестник СПбГУ. – 2010. – Сер. 10. – Вып. 1. – С. 95–104.
15. Тулупьев А.Л., Сироткин А.В., Николенко С.И. Байесовские сети доверия: логико-вероятностный вывод в ациклических направленных графах. – СПб: Изд-во СПбГУ, 2009. – 400 с.
16. Опарин В.В., Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Матроидное представление семейства графов смежности над набором фрагментов знаний // Научно-технический вестник СПбГУ ИТМО. – 2010. – № 4. – C. 73–76.
17. Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Компаративный анализ клик минимальных графов смежности алгебраических байесовских сетей // Труды СПИИРАН. – СПб: Наука, 2010. – Вып. 2. – С. 87–105.
18. Тулупьев А.Л. Задача локального автоматического обучения в алгебраических байесовских сетях: логико-вероятностный подход // Труды СПИИРАН. – СПб: Наука, 2008. – Вып. 7. – С. 11–25.
19. Момзикова М.П., Великодная О.И., Пинский М.Я., Сироткин А.В., Тулупьев А.Л., Фильченков А.А. Оценка вероятности наблюдаемой последовательности в бинарных линейных по структуре скрытых марковских моделях с помощью апостериорного вывода в алгебраических байесовских сетях // Труды СПИИРАН. – СПб: Наука, 2010. – Вып. 2. – C. 122–142.
20. Forney D.G. The Viterbi Algorithm // Proceedings of the IEEE. – 1973. – V. 61. – № 3. – Р. 268–278. 21. Welch L.R. Hidden Markov Models and the Baum-Welch Algorithm // IEEE Information Theory Society
Newsletter. – 2003. –V. 53. – № 4. – Р. 10–13. 22. Тулупьев А.Л. Алгебраические байесовские сети. Логико-вероятностный подход к моделированию
баз знаний с неопределенностью. – СПб: СПИИРАН, 2000. – 292 с. 23. Момзикова М.П., Великодная О.И., Пинский М.Я., Сироткин А.В., Тулупьев А.Л., Фильченков А.А.
Представление бинарных линейных по структуре скрытых марковских моделей в виде алгебраических байесовских сетей // Труды СПИИРАН. – СПб: Наука, 2010. – Вып. 1. – C. 134–150.
Пинский Михаил Яковлевич
– Санкт-Петербургский государственный университет информацион-
ных технологий, механики и оптики, студент,
mikhailpinsky@gmail.com
Сироткин Александр Владимирович – Санкт-Петербургский институт информатики и автоматизации РАН,
мл. научный сотрудник, alexander.sirotkin@gmail.com
Тулупьев Александр Львович
– Санкт-Петербургский институт информатики и автоматизации РАН,
доктор физ.-мат. наук, доцент, зав. лабораторией,
alexander.tulupyev@gmail.com
Фильченков Андрей Александрович
– Санкт-Петербургский институт информатики и автоматизации РАН,
мл. научный сотрудник, aaafil@mail.ru
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2011, № 5 (75)
73