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

УДК 62-50

И.С. СУВОРОВ, П.И. БИДЮК

МЕТОДИКА СТРУКТУРНОГО ОБУЧЕНИЯ ДИНАМИЧЕСКИХ БАЙЕСОВСКИХ СЕТЕЙ НА ОСНОВЕ СТАТИСТИЧЕСКИХ ДАННЫХ__________________________________________________

Анотація. Розглядаються деякі існуючі підходи й пропонується нова методика статистичного структурного навчання динамічних баєсівських мереж для випадку повних вибірок даних. Запропонована методика структурного навчання базується на спеціальній статистиці. Наведено попередні результати застосування методики, що демонструють можливість поліпшення якості результатів структурного навчання.

Ключові слова: динамічні баєсівські мережі, структурне навчання динамічних баєсівських мереж.

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

Ключевые слова: динамические байесовские сети, структурное обучение динамических байесовских сетей.

Abstract. Some known approaches to structural learning of dynamic Bayesian networks are considered and a new methodology is proposed that is based on statistical data. The methodology proposed uses special statistic for structural learning. Preliminary results of application the methodology to real data is given that demonstrate improvement of structural learning quality.

Key words: dynamic bayesian networks, structural learning of dynamic Bayesian networks.

1. Введение

Хорошо известно, что фильтры Калмана и скрытые модели Маркова, являющиеся представителями простейших вероятностных направленных графических моделей, нашли обширное практическое применение и позволяют эффективно решать определенный класс задач [1]. Например, предварительная обработка данных, оптимальное оценивание состояний, краткосрочное прогнозирование, дуальное управление. К множеству вероятностных направленных графических моделей также принадлежат байесовские сети (БС) и динамические байесовские сети (ДБС), которые являются перспективным и эффективным инструментом решения различных задач, таких как интеллектуальный анализ данных, распознавание образов, классификация, прогнозирование и т.д. Описание успешного применения ДБС для распознавания речи приведено в работе [2], результаты прогнозирования состояния пациентов отделения интенсивной терапии описаны в работе [3]. Дальнейшее успешное применение ДБС требует более подробного исследования некоторых теоретических и практических аспектов их функционирования. В частности, более эффективного формирования вероятностного вывода на известной структуре сети, определения оптимальной структуры и параметров сети в различных условиях: полная или частичная наблюдаемость переменных, необходимость получения результатов в реальном времени, возможность влияния на входные данные. БС и ДБС являются на сегодня объектом активных исследований, что находит отражение в соответствующей научной литературе [1-9].

В сущности вероятностные направленные графические модели, такие как БС и ДБС, опираются на понятие условной вероятности и предоставляют средства наглядного и компактного представления вероятностных зависимостей и совместного распределения вероятности (СРВ) случайных величин, описывающих некоторое явление или процесс.

Одним из главных компонентов БС и ДБС является направленный ациклический граф, в котором некоторая дуга от вершины A к вершине B неформально может быть ин-

© Суворов И.С., Бидюк П.И., 2010

ISSN 1028-9763. Математичні машини і системи, 2010, № 4

терпретирована как причинно-следственная связь между А и В по аналогии с классическим представлением о связи между понятиями причины и следствия.

Данная работа посвящена исследованию некоторых существующих подходов и разработке основ новых методик построения ДБС для случая полной наблюдаемости данных. Ниже будут изложены общие теоретические сведения о ДБС, рассмотрены существующие байесовские и предложены альтернативные статистические критерии качества сетевой структуры, приведены примеры использования рассмотренных методов и результаты экспериментальных исследований.

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

Рассмотреть существующие подходы к определению оптимальной, в смысле выбранного критерия, структуры ДБС на основе выборок данных, порожденных многомерным случайным стационарным марковским процессом первого порядка. Разработать и исследовать основы альтернативной статистической методики.

Формально задачу можно сформулировать следующим образом: известны многомерные временные выборки данных

Я = {(Х1у [0],..., х„у[0]),...,( х1у[Гу ],..., хт[Ту ])}, где V - номер выборки, Т - объем выборки с номером V ; множество всех выборок обозначено через Б = {Д,...,Пу}, где V - количество выборок. Выборки порождены упорядоченным множеством дискретных случайных величин х¥к = {Х^к],..., Хп [к ]}. Случайные величины Х, [к], Х, [т] для любых моментов времени к, т могут принимать значения из одного и того же множества значений Val(Х,) .

Необходимо найти оценку разложения СРВ, наиболее точно отражающую реальные зависимости, существующие в данных

Р(^+1, Чк) = Р( Х[к +1],..., Хп[к +1], Х1[к ],..., Хп [к ]), на произведение условных распределений вероятностей (УРВ):

Р('П.,, ^) = Р(Ч-к)Р(П., / ^) = Р(Ч-к )Г1Р(Х,[к +1] /Ра(Х,[к +1])),

,=1

где Ра(Х, [к +1]) с¥к и^к+1 \{Х, [к +1]} - множество случайных величин, от которых условно зависит случайная величина Х, [к +1]. Предполагается, что для любых моментов времени к и т разложение СРВ Р(Чк, х¥к_1), Р(Чт, ¥т-1) на произведение УРВ одинаково (процесс стационарен) и подчиняется одним и тем же законам распределения вероятностей, то есть

Р(^к /Ум) = 11 Р(Х,[к]/Ра(Х,[к])) = Г!Р(Х,[т]/Ра(Х,[т])) = Р(Ч>„ /Ч^).

,=1 ,=1

3. Динамическая байесовская сеть

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

Чк = { Х1[к ],...

, Хп[к ]}, в отличие от одного множества случайных величин

* = { Х1,. , Хп} , описываемого БС.

Более формально ДБС представляет собой два направленных ациклических графа G, G0, кодирующих разложения распределений вероятности Р(Чк+1 / Чк), Р(¥0) на УРВ

и заданные некоторым способом множества соответствующих УРВ 0, 00. Каждая вершина любого из указанных ациклических графов соответствует некоторой случайной величине Х, [к]. Графы G, G0 состоят из вершин, соответствующих множествам случайных величин:

^+1 и^к = {ХД +1],., Хп [к +1], Х1[к ],..., Хп[к ]},

^0 = {Х1[0],., Хп[0]}.

Если Х}.[т] е Ра(Х, [к], ^, С0}), то в графе G0 при т = к = 0 или G при

к = т +1 имеется направленная дуга Х] [т]  Х, [к]. Так как БС В представляет собой

аналогичным образом сконструированные граф G и множество 0 [1 - 3], то самым компактным определением ДБС, предложенным Мерфи, будет следующее.

Определение 2.1. ДБС представляет собой пару (В0, В), где В0 - БС, описывающая СРВ Р(¥0),

В - двухслойная БС, описывающая УРВ Р

[1].

Пример возможных графов G0, G приведен на рис. 1.

Для графов G0, G, приведенных на рис. 1, разложения СРВ Р(^0) и УРВ Р(¥к+1 / ¥к) имеют вид Р(^) = Р(Х 2 [0] / Х1[0])Р( ^[0]),

Р(^к+1 / ^ ) = Р( Х 2 [к +1]/ Х[к ], Х 2 [к ])Р( Х1 [к +1]/ Х1[к ]).

Таким образом, задачу данной работы кратко можно сформулировать следующим образом: необходимо определить структуру графа ДБС, наиболее точно отражающую фактически существующие зависимости в данных. В литературе эту задачу также называют структурным обучением ДБС [2].

4. Байесовский подход к структурному обучению ДБС

Суть байесовского подхода к структурному обучению ДБС основывается на применении правила Байеса для УРВ структур графов множества G = ^0, G} в зависимости от типа выборки данных В:

Р(в / В) = Р^ В) = .

2 P

G

Таким образом, при сравнении двух структур G1, G2 можно перейти от сравнения условных вероятностей к сравнению безусловных:

Р(^, В)/

Р

P(G2 / В) = Р^, В)/ = Р(^, В).

/Р

Для оценок величины Р^, В) Купером и Гершковичем в работе [6] предложено аналитическое выражение, но его практическое использование часто приводит к непреодолимым вычислительным трудностям даже для структурного обучения БС с небольшими количествами вершин. В работах [4, 7] предлагается хорошая асимптотическая оценка Ь(@, В) величины 1о§(Р^, В)), пригодная не только для прикладного структурного обу-

Рис. 1. Графы G0, G для ДБС

чения БС, но и ДБС. Ь(Р, В) принято называть байесовским информационным критерием, который определяется выражением

1 V КО, В) = 1С8(Р(В / <Э, Р)) - - а(Р)1<* ^ Т,

2 У=1

где 0 - оценки параметров распределений вероятности для графов множества Р, полученные на основе выборки В методом максимального правдоподобия; а(Р) - функция, характеризующая сложность зависимостей между случайными величинами на графе Р. Для ДБС справедливо равенство: а(Р) = а0(Р) + а(Р), где а0(Р) и а(р) характеризуют сложность зависимостей для Р0 и Р соответственно. Функция а0(Р) имеет вид [4]

ао(Р)=Е, Е рагёРа (х, [0]) -ш (Раг) •(X [0]) - 1.

Выражение для функции а (Р) имеет аналогичный вид. Для ДБС Р(В / 0, Р) имеет разложение вида

Р( В / 0, Р) = ПР(ВУ / 0, Р) = П Г1Р(Х1. [0] = х* [0]/Ра(Х, [0], Р) = г* [0], (0) х

у=1 У=1 ,=1

хПР(Х[к + -] = х*[к +1]/Ра(Хг [к],Р) = тп[к],0) ,

к=0

где ггу[к] - подмножество (х1у[к],...,хпу[к]}, соответствующее реализации случайных величин в к -й момент времени, от которых условно зависит Хг [к +1] на графе Р . Введем обозначения для упрощения дальнейших записей:

3*,, (Р) = Р(Х, [0] = х, /Ра(Х, [0], Р) = Г,, Э) ,

(Р) = Р(Хг [к +1] = х /Ра(Хг [к], Р) = г' (Э) ,

Х,х,,г (Р) = Е1 (Хг [0] = х,, Ра(Хг [0], Р) = ) ,

У=1

V Т -1

^ (Р) = ЕЕ I (Х, [к +1] = х', Ра( Хг [к ], Р) = г! Ву),

у=1 к =0

где I(*|Ву) - индикатор события « • » в выборке Ву; переменные х,, х' могут принимать все возможные значения случайной величины Х, [к]; г,, г' могут принимать все возможные значения множества случайных величин Ра(Х, [к], Р) . На основании введенных выше

обозначений и указанного разложения Р( В / 0, Р) выражение для 1о§(Р( В / 0, Р)) можно переписать в более компактной и удобной для вычислений форме:

1ов(Р(В / <0, р))=е ЕЕ ^,*,,(Р)4х,,(Р)+Е ЕЕ ^йгг (Р)'^,;,,- (Р).

,=1 х, г, ,=1 х, гГ

Оценка для в, х г (Р) вычисляется методом максимального правдоподобия:

Х,*,,

вх,г (Р):

Е Х,х,,г, (р)’

для в, ,(Р) это выполняется аналогично.

г,х, ,г, \ /

Таким образом, для решения поставленной задачи необходимо найти такие структуры графов множества Р*, которые максимизируют байесовский информационный критерий:

х

Р* = аг§{шах Ь(Р, В)},

РеГ

где Г - множество графов-претендентов. Особенностью байесовского информационного критерия для ДБС является его аддитивность по отношению к свойствам БС, составляющих ДБС [1, 4]. То есть, структурное обучение может быть выполнено отдельно для В0 и

В.

Алгоритм поиска В, максимизирующий байесовский информационный критерий для случая, когда множество Г содержит только такие Р , для которых выполняется условие Ра(Х, [к +1]) с¥к (то есть, связи внутри слоев В отсутствуют), схематически представлен на рис. 2.

5. Статистическая методика структурного обучения ДБС

В рамках классического статистического подхода задача данной работы может быть рассмотрена как задача проверки гипотез Н % , gm е Г о структуре графов

Р ДБС. Без существенной потери общности результатов исследования ограничимся проверкой гипотез Н  о структу-

gm

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

* ки вышеуказанных гипотез необходима

Рис. 2. Алгоритм шжка наилучшего р подходящим образом сконструированная

на основе Ь(Р, В) статистика £ .

Рассмотрим свойства выборочной оценки УРВ Р(Х, [к +1]/ Ук°). Предположим, что случайная величина Х ,[к +1] находится в вероятностной зависимости от случайных величин Ра(Х { [к +1]) = Тк*с¥к ; тогда очевидно, что в случае Ук° Ф Ук*, оценка

Р( Х, [к +1]/ Ук°) будет содержать повторяющуюся информацию об УРВ Р( Х, [к +1]/ Ук*) в отличие от оценки Р(Х, [к +1]/ Ук*). Можно утверждать, что при любых фиксированных значениях ц! е—а1 (Ук \ У*) для случайных величин Ук \ Ук* , от которых не зависит Х, [к +1], будет иметь место сходимость по вероятности:

"ц;, Р( х, [к+1]/у; ,{у \ у;}=ц) — Р( х, [к+1]/у;).

Однако, если Ук* Ф Ра(Х, [к +1]), сходимости не будет. Отсюда следует, что в результате сравнения выборочных законов распределения вероятностей 17 (Х, Ук°, Ц) и Р ° (Х, Ук°), полученных на основе оценок распределений вероятностей Р(Х, [к +1]/ Ук° ,{Ук \ Ук°} = ц!) и Р(Х, [к +1]/ Ук°) для различных ц!, можно судить о наличии или отсутствии указанной сходимости для множества кандидатов Ук с Ук . Проверку гипотез об одинаковости выборочных законов распределения вероятности I7, (Х, х¥°к, ц ) и 1° (Х, ) можно осуществить на основе критерия согласия Колмогорова.

Рог 1 е {1, к, п}

Гог у0 е 2Тк

g= {Х;[к]  Х,[к +1]Х;.[к]еУ0}

{в^

Е N,;,г

1Г Ь(Е, В) > ОД, В) Леп g* =g

Р= и ^ 2

Исходя из указанных свойств 1 (X, х¥°к, д') и Е° (X, х¥°к ), для определения наилучшего множества для случайной величины X] [к +1] в качестве подходящей статистики, основанной на критерии согласия Колмогорова, может быть рассмотрена величина

Si

\

2 £ T £ £ sup|І

2 V Yk (g) q; X

где ¥к° ) - множество вершин родителей для Х{ [к +1] в графе gm . Очевидно, что чем

ближе 1 (X, ¥к°, д') к 17° (X, ¥к°) для любого д' и ¥к°, тем меньше будет значение статистики, и наоборот. Следовательно, решение рассматриваемой задачи на основе

^ (Е ) = Е £ ) можно записать:

г

° = аг§{ гшп £^ ^

gm еГ

где Г - множество графов-претендентов, определяющих связи между слоями подсети В ДБС. Следует отметить, что в случае, когда Г содержит графы с различной степенью

связности вершин, указанная статистика £(g) будет принимать минимальные значения для самых «сложных графов», то есть для графов с максимальным количеством связей. Однако, если Г содержит структуры «одинаковой сложности» с одинаковым количеством связей, использование этой статистики позволит найти самый лучший в смысле постановки задачи граф О . Чтобы снять указанное ограничение на множество Г, в решении задачи необходимо учесть величину, аналогичную второй части выражения байесовского информационного критерия, «штрафующую» метод за сложность выбранного графа. Но для данного исследования это ограничение не существенно, так как позволяет в полной

мере изучить принципиальные свойства статистики £(g) .

for i е {1,..., n} for Yo е 2¥k

if Card(Yo ) Ф R continue g = {X; [k]  Xt [k + 1]|Xj [k] eY } if St (g) < St (g*) then g* = g

g = U g*

Рис. 3. Алгоритм поиска наилучшего G_ на основе S

Алгоритм поиска сети B, минимизирующий статистику S для случая, когда множество Г содержит только такие графы G, для которых выполняется условие

Pa(Xt [k +1]) cYk и Card(Pa(Xt [k +1])) = R, где R подается на вход алгоритма, схематически представлен на рис. 3.

В качестве примера рассчитаем значение S1(g2.1) для графа, приведенного на рис. 1 и одной временной выборки данных из табл. 1. Оценки условных распределений приведены в табл. 2 и 3.

Таблица 1. Выборочные данные

к 1 2 3 4 5 6

X1[k ] 0 0 1 1 0 1

X 2 [k ] 0 1 0 1 1 0

Таблица 2. Оценки условных распределений P

X 2 [k ] X1[k ] X1[k +1] P

0 0 0 1 1

0 0 1 0 1

0 1 0 0 0

0 1 1 1 1

1 0 0 0 0

1 0 1 1 1

1 1 0 1 1

1 1 1 0 1

Таблица 3. Оценки условных распределений P

X1[k ] X1[k +1] P

0 0 1/3 1/3

0 1 2/3 1

1 0 1/2 1/2

1 1 1/2 1

Расчет значения S1 (g ):

sup

1 -1

3

Л

+ sup

= V3

о -1 2

11 -11

+ sup

/

о -1

3

2 1 1 1

-1-1-1-

3232

V

= 3,46.

11 -11

+ sup

11 -11

6. Экспериментальные исследования

Экспериментальные исследования выполнены методом имитационного моделирования. В основу критерия качества структурного обучения положена мера Хэмминга H(G, G),

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

В качестве ДБС для проведения исследований выбрана сеть со структурой, представленной на рис. 4.

Эксперимент организован следующим образом. На вход подавалось количество временных выборок V и количество элементов множества значений случайных величин Z; без ограничения общности полагалось, что Vi: Card(Val(Xi)) = Z. Чтобы усреднить полученные значения критерия качества структурного обучения, для каждого выбранного V и Z выполнено 5 элементарных экспериментов. Каждый элементарный эксперимент состоял из следующих этапов:

Рис. 4. Граф G ДБС для экспериментальных исследований

1. На основе равномерного распределения вероятностей генерировались случайные табличные распределения условных вероятностей, описывающих связи между слоями выбранной ДБС.

2. На основе метода Монте-Карло сгенерированы V временных выборок данных мощностью Tv = 30 элементов, в каждой из которых любая случайная величина могла принимать не больше, чем Z различных значений.

3. Выполнялось структурное обучение на основе байесовского информационного критерия и статистического критерия. Для уменьшения вычислительной сложности и учета ограничений статистической методики множество графов претендентов Г ограничено следующим условием: Card (Pa( Xt [к +1])) = 2 для обоих способов.

4. Вычислялось значение критерия качества H(G,G) структурного обучения для обоих способов.

Экспериментальные исследования направлены на изучение характера поведения эмпирических функций:

KB1C (V, Z) = - H (g , GC (E,V, Z)),

5

E=1

5

KS (V, Z) =1 ]T H (<G,GBB (E,V, Z)),

5 E =1

12

10

KS

f^lcl

V,5) Ъ I \4 1 V ^ 0 “ шm _ _ _

10

12

13

Рис. 5. Графики: KB1C (V,5) - штриховая линия и KS (V ,5) - сплошная линия

где ОС (Е,У, Z), О (Е,¥, Z) - графы ДБС, полученные в результате структурного обучения, выполненного по V временным выборкам с Z элементами множества значений случайных величин; Е - номер элементарного эксперимента. Эти графы получены на основе байесовского информационного критерия и статистической методики соответственно.

Зависимости КВІС (V, Z ) и

12

10

**^

KB,C(S,Z 4 ✓ У 4 У ✓ f • • •

\ \ \ V.

Ks

10

К (V, Z) при Z = 5 и V = 3,13, полученные в результате проведенных экспериментов, отражены на рис. 5.

Из анализа полученных результатов для Z = 5 и V = 3,13 следует, что при фиксированном Z структурное обучение, основанное на предложенной статистической методике, приводит к существенно лучшим результатам при больших V. Аналогичный характер поведения КВ1С (V, Z) и К5 (V, 2) получен и для других Z .

Зависимости КВ1С (V, 2 ) и

Рис. 6. Графики для КВ1С (8,2) - штриховая линия и К5 (8,2) - сплошная линия

К (V, 2) при Z = 2,10 и V = 8, полученные в результате выполненных экспериментов, отражены на рис. 6.

Из анализа полученных результатов для Z = 2,10 и V = В следует, что при фиксированном V структурное обучение, основанное на предложенной статистической методике, приводит к более качественным результатам при меньших Z . Аналогичный характер поведения KBIC (V, Z) и KS (V, Z) был получен и для других V .

7. Выводы

В работе подробно рассмотрена задача структурного обучения ДБС с позиций байесовского подхода и теории вероятностей. Рассмотрен существующий алгоритм структурного обучения на основе байесовского информационного критерия и разработаны основы методики структурного обучения на базе предложенной статистики.

Выполнен анализ полученных экспериментальных зависимостей, показывающий, что при определенных соотношениях количества временных выборок V и количества элементов множества значений случайных величин Z структурное обучение, основанное на предложенной статистической методике, позволяет существенно повысить качество результатов обучения ДБС. Отметим, что, как следует из экспериментальных данных, качество обучения на основе байесовского информационного критерия и предложенной статистической методики обладает противоположными свойствами по отношению к Z и V .

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

СПИСОК ЛИТЕРАТУРЫ

1. Murphy K.P. Dynamic Bayesian networks: representation, inference and learning: а PhD dissertation / Murphy K.P. - University of California, Berkeley, 2002. - 225 p.

2. Zweig G.G. Speech Recognition with Dynamic Bayesian Networks: а PhD dissertation / Zweig G.G. -University of California, Berkeley, 199В. - 1б9 p.

3. Kayaalp M№. Learning Dynamic Bayesian Network Structures from Data: Ph.D. Dissertation / M№. Kayaalp, G.F. Cooper. - University of Pittsburgh, 2003. - 203 p.

4. Friedman F.N. Learning Structure of Dynamic Probabilistic Networks / F.N. Friedman, K. Murphy,

5. Russell // Proc. of the Fourteenth Conference on Uncertainty in Artificial Intelligence (UAI^). -199В. - P. 139 - 147.

5. Тулупьев А.Л. Байесовские сети: логико-вероятностный подход / Тулупьев А.Л., Николенко С.И., Сироткин А.В. - СПб.: Наука, 200б. - б07 с.

6. Cooper G. A Bayesian method for the induction of probabilistic networks from data / G. Cooper, E. Herskovits // Machine Learning. - 1992. - N 9. - P. 309 - 347.

7. Heckerman D. Bayesian Networks for Data Mining / D. Heckerman // Data Mining and Knowledge Discovery. - 1997. - N 1. - P. 79 - 119.

B. Згуровский М.З. Методы построения байесовских сетей на основе оценочных функций / М.З. Згуровский, П.И. Бидюк, А.Н. Терентьев // Кибернетика и системный анализ. - 200В. - № 2. -

C. В1 - ВВ.

9. Терентьев А.Н. Методы построения байесовских сетей / А.Н. Терентьев, П.И. Бидюк // Межведомственный научно-технический сборник „Адаптивные системы автоматического управления”. -Днепропетровск: Системные технологии, 2005. - № В. - С. 130 - 141.

Стаття надійшла до редакції 22.01.2010