Методика структурного обучения динамических байесовских сетей на основе статистических данных
Рассматриваются некоторые существующие подходы и предлагается новая методика статистического структурного обучения динамических байесовских сетей для случая полной наблюдаемости данных. Предложенная методика структурного обучения базируется на специальной статистике. Приведены предварительные резуль...
Збережено в:
| Дата: | 2010 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем математичних машин і систем НАН України
2010
|
| Назва видання: | Математичні машини і системи |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/83352 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Методика структурного обучения динамических байесовских сетей на основе статистических данных / И.С. Суворов, П.И. Бидюк // Мат. машини і системи. — 2010. — № 4. — С. 110-118. — Бібліогр.: 9 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-83352 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-833522015-06-20T10:33:33Z Методика структурного обучения динамических байесовских сетей на основе статистических данных Суворов, И.С. Бидюк, П.И. Моделювання і управління великими системами Рассматриваются некоторые существующие подходы и предлагается новая методика статистического структурного обучения динамических байесовских сетей для случая полной наблюдаемости данных. Предложенная методика структурного обучения базируется на специальной статистике. Приведены предварительные результаты применения методики, демонстрирующие возможность улучшения качества результатов структурного обучения. Розглядаються деякі існуючі підходи й пропонується нова методика статистичного структурного навчання динамічних баєсівських мереж для випадку повних вибірок даних. Запропонована методика структурного навчання базується на спеціальній статистиці. Наведено попередні результати застосування методики, що демонструють можливість поліпшення якості результатів структурного навчання. Some known approaches to structural teaching of dynamic Bayesian networks are considered and a new methodology is proposed that is based on statistical data. Proposed methodology uses the special statistic for structural learning. Preliminary results of application the methodology to real data are given, that demonstrate improvement of structural teaching quality. 2010 Article Методика структурного обучения динамических байесовских сетей на основе статистических данных / И.С. Суворов, П.И. Бидюк // Мат. машини і системи. — 2010. — № 4. — С. 110-118. — Бібліогр.: 9 назв. — рос. 1028-9763 http://dspace.nbuv.gov.ua/handle/123456789/83352 62-50 ru Математичні машини і системи Інститут проблем математичних машин і систем НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Моделювання і управління великими системами Моделювання і управління великими системами |
| spellingShingle |
Моделювання і управління великими системами Моделювання і управління великими системами Суворов, И.С. Бидюк, П.И. Методика структурного обучения динамических байесовских сетей на основе статистических данных Математичні машини і системи |
| description |
Рассматриваются некоторые существующие подходы и предлагается новая методика статистического структурного обучения динамических байесовских сетей для случая полной наблюдаемости данных. Предложенная методика структурного обучения базируется на специальной статистике. Приведены предварительные результаты применения методики, демонстрирующие возможность улучшения качества результатов структурного обучения. |
| format |
Article |
| author |
Суворов, И.С. Бидюк, П.И. |
| author_facet |
Суворов, И.С. Бидюк, П.И. |
| author_sort |
Суворов, И.С. |
| title |
Методика структурного обучения динамических байесовских сетей на основе статистических данных |
| title_short |
Методика структурного обучения динамических байесовских сетей на основе статистических данных |
| title_full |
Методика структурного обучения динамических байесовских сетей на основе статистических данных |
| title_fullStr |
Методика структурного обучения динамических байесовских сетей на основе статистических данных |
| title_full_unstemmed |
Методика структурного обучения динамических байесовских сетей на основе статистических данных |
| title_sort |
методика структурного обучения динамических байесовских сетей на основе статистических данных |
| publisher |
Інститут проблем математичних машин і систем НАН України |
| publishDate |
2010 |
| topic_facet |
Моделювання і управління великими системами |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/83352 |
| citation_txt |
Методика структурного обучения динамических байесовских сетей на основе статистических данных / И.С. Суворов, П.И. Бидюк // Мат. машини і системи. — 2010. — № 4. — С. 110-118. — Бібліогр.: 9 назв. — рос. |
| series |
Математичні машини і системи |
| work_keys_str_mv |
AT suvorovis metodikastrukturnogoobučeniâdinamičeskihbajesovskihsetejnaosnovestatističeskihdannyh AT bidûkpi metodikastrukturnogoobučeniâdinamičeskihbajesovskihsetejnaosnovestatističeskihdannyh |
| first_indexed |
2025-07-06T10:07:15Z |
| last_indexed |
2025-07-06T10:07:15Z |
| _version_ |
1836891699824033792 |
| fulltext |
110 © Суворов И.С., Бидюк П.И., 2010
ISSN 1028-9763. Математичні машини і системи, 2010, № 4
УДК 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 spe-
cial 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 неформально может быть ин-
ISSN 1028-9763. Математичні машини і системи, 2010, № 4 111
терпретирована как причинно-следственная связь между A и B по аналогии с классиче-
ским представлением о связи между понятиями причины и следствия.
Данная работа посвящена исследованию некоторых существующих подходов и раз-
работке основ новых методик построения ДБС для случая полной наблюдаемости данных.
Ниже будут изложены общие теоретические сведения о ДБС, рассмотрены существующие
байесовские и предложены альтернативные статистические критерии качества сетевой
структуры, приведены примеры использования рассмотренных методов и результаты экс-
периментальных исследований.
2. Постановка задачи
Рассмотреть существующие подходы к определению оптимальной, в смысле выбранного
критерия, структуры ДБС на основе выборок данных, порожденных многомерным случай-
ным стационарным марковским процессом первого порядка. Разработать и исследовать
основы альтернативной статистической методики.
Формально задачу можно сформулировать следующим образом: известны много-
мерные временные выборки данных
])}[,],[(,]),0[,],0[{( 11 vnvvνnvvv TxTxxxD KKK= ,
где v – номер выборки, vT – объем выборки с номером v ; множество всех выборок обо-
значено через },,{ 1 VDDD K= , где V – количество выборок. Выборки порождены упоря-
доченным множеством дискретных случайных величин ]}[,],[{ 1 kXkX nk K=Ψ . Случайные
величины ][],[ mXkX ii для любых моментов времени mk, могут принимать значения из
одного и того же множества значений )( iXVal .
Необходимо найти оценку разложения СРВ, наиболее точно отражающую реальные
зависимости, существующие в данных
])[,],[],1[,],1[(),( 111 kXkXkXkXPP nnkk KK ++=ΨΨ + ,
на произведение условных распределений вероятностей (УРВ):
∏
=
++ ++Ψ=ΨΨΨ=ΨΨ
n
i
iikkkkkk kXPakXPPPPP
1
11 ]))1[(/]1[()()/()(),( ,
где ]}1[{\])1[( 1 +Ψ∪Ψ⊆+ + kXkXPa ikki – множество случайных величин, от которых ус-
ловно зависит случайная величина ]1[ +kX i . Предполагается, что для любых моментов
времени k и m разложение СРВ ),(),,( 11 −− ΨΨΨΨ mmkk PP на произведение УРВ одинако-
во (процесс стационарен) и подчиняется одним и тем же законам распределения вероятно-
стей, то есть
∏∏
=
−
=
− ΨΨ===ΨΨ
n
i
mmii
n
i
iikk PmXPamXPkXPakXPP
1
1
1
1 )/(]))[(/][(]))[(/][()/( .
3. Динамическая байесовская сеть
ДБС – математический аппарат компактного представления сложных стохастических про-
цессов. ДБС – это расширение обычной (статической) БС, благодаря чему они позволяют
исследовать и моделировать конечные последовательности множеств случайных величин
]}[,],[{ 1 kXkX nk K=Ψ , в отличие от одного множества случайных величин
},,{ 1 nXX K=Ψ , описываемого БС.
Более формально ДБС представляет собой два направленных ациклических графа
0, GG→ , кодирующих разложения распределений вероятности )(),/( 01 ΨΨΨ + PP kk на УРВ
112 ISSN 1028-9763. Математичні машини і системи, 2010, № 4
и заданные некоторым способом множества соответствующих УРВ 0, ΘΘ→ . Каждая вер-
шина любого из указанных ациклических графов соответствует некоторой случайной ве-
личине ][kX i . Графы 0, GG→ состоят из вершин, соответствующих множествам случай-
ных величин:
]},[,],[],1[,],1[{ 111 kXkXkXkX nnkk KK ++=Ψ∪Ψ +
]}0[,],0[{ 10 nXX K=Ψ .
Если }),{],[(][ 0GGkXPamX ij →∈ , то в графе 0G при 0== km или →G при
1+= mk имеется направленная дуга ][][ kXmX ij → . Так как БС B представляет собой
аналогичным образом сконструированные граф G и множество Θ [1 – 3], то самым ком-
пактным определением ДБС, предложенным Мерфи, будет следующее.
Определение 2.1. ДБС представляет собой па-
ру ),( 0 →BB , где 0B – БС, описывающая СРВ )( 0ΨP ,
→B – двухслойная БС, описывающая УРВ )/( 1 kkP ΨΨ +
[1].
Пример возможных графов →GG ,0 приведен
на рис. 1.
Для графов →GG ,0 , приведенных на рис. 1,
разложения СРВ )( 0ΨP и УРВ )/( 1 kkP ΨΨ + имеют вид
])0[(])0[/]0[()( 1120 XPXXPP =Ψ ,
])[/]1[(])[],[/]1[()/( 112121 kXkXPkXkXkXPP kk ++=ΨΨ + .
Таким образом, задачу данной работы кратко можно сформулировать следующим
образом: необходимо определить структуру графа ДБС, наиболее точно отражающую фак-
тически существующие зависимости в данных. В литературе эту задачу также называют
структурным обучением ДБС [2].
4. Байесовский подход к структурному обучению ДБС
Суть байесовского подхода к структурному обучению ДБС основывается на применении
правила Байеса для УРВ структур графов множества },{ 0 →= GGG в зависимости от типа
выборки данных D :
)(
),(
),(
),(
)/(
DP
DGP
DGP
DGP
DGP
G
==
∑
.
Таким образом, при сравнении двух структур 21, GG можно перейти от сравнения
условных вероятностей к сравнению безусловных:
),(
),(
)(
),(
)(
),(
)/(
)/(
2
1
2
1
2
1
DGP
DGP
DP
DGP
DP
DGP
DGP
DGP == .
Для оценок величины ),( DGP Купером и Гершковичем в работе [6] предложено
аналитическое выражение, но его практическое использование часто приводит к непре-
одолимым вычислительным трудностям даже для структурного обучения БС с небольши-
ми количествами вершин. В работах [4, 7] предлагается хорошая асимптотическая оценка
),( DGL величины )),(log( DGP , пригодная не только для прикладного структурного обу-
Рис. 1. Графы →GG ,0 для ДБС
ISSN 1028-9763. Математичні машини і системи, 2010, № 4 113
чения БС, но и ДБС. ),( DGL принято называть байесовским информационным критерием,
который определяется выражением
∑
=
−Θ=
V
ν
νTGGDPDGL
1
log)(
2
1
)),ˆ/(log(),( σ ,
где Θ̂ – оценки параметров распределений вероятности для графов множества G , полу-
ченные на основе выборки D методом максимального правдоподобия; )(Gσ – функция,
характеризующая сложность зависимостей между случайными величинами на графе G .
Для ДБС справедливо равенство: )()()( 0 GGG →+= σσσ , где )(0 Gσ и )(G→σ характери-
зуют сложность зависимостей для 0G и →G соответственно. Функция )(0 Gσ имеет вид [4]
( )1])0[()()(
])0[(0 −⋅=∑∑ ∈ ii XPapar
XValparValG
i
σ .
Выражение для функции )(G→σ имеет аналогичный вид. Для ДБС ),ˆ/( GDP Θ име-
ет разложение вида
∏∏∏
= ==
×Θ===Θ=Θ
V
ν
n
i
iνiiνi
V
ν
ν rGXPaxXPGDPGDP
1 11
)ˆ],0[)],0[(/]0[]0[(),ˆ/(),ˆ/(
∏
−
=
Θ=+=+×
1
0
)ˆ],[)],[(/]1[]1[(
νT
k
iνiiνi krGkXPakxkXP ,
где ][kriν – подмножество ]}[,],[{ 1 kxkx nvv K , соответствующее реализации случайных ве-
личин в k -й момент времени, от которых условно зависит ]1[ +kX i на графе G . Введем
обозначения для упрощения дальнейших записей:
)ˆ,)],0[(/]0[()(ˆ
,, Θ=== iiiirxi rGXPaxXPG
ii
θ ,
)ˆ,)],[(/]1[()(ˆ
,, Θ′=′=+=→
′′ iiiirxi rGkXPaxkXPG
ii
θ ,
∑
=
===
V
ν
νiiiirxi DrGXPaxXIGN
ii
1
,, ))],0[(,]0[()( ,
∑∑
=
−
=
→
′′ ′=′=+=
V
ν
T
k
νiiiirxi
ν
ii
DrGkXPaxkXIGN
1
1
0
,, ))],[(,]1[()( ,
где )( νDI • – индикатор события «• » в выборке νD ; переменные ii xx ′, могут принимать
все возможные значения случайной величины ][kX i ; ii rr ′, могут принимать все возмож-
ные значения множества случайных величин )],[( GkXPa i . На основании введенных выше
обозначений и указанного разложения ),ˆ/( GDP Θ выражение для )),ˆ/(log( GDP Θ можно
переписать в более компактной и удобной для вычислений форме:
∑∑∑∑∑∑
= ′ ′
→
′′
→
′′
=
+=Θ
n
i x r
rxirxi
n
i x r
rxirxi
i i
iiii
i i
iiii
GGNGGNGDP
1
,,,,
1
,,,, )(ˆ)()(ˆ)()),ˆ/(log( θθ .
Оценка для )(ˆ
,, G
ii rxiθ вычисляется методом максимального правдоподобия:
∑
=
i
ii
ii
ii
x
rxi
rxi
rxi GN
GN
G
)(
)(
)(ˆ
,,
,,
,,θ ;
для )(ˆ
,, G
ii rxi
→
′′θ это выполняется аналогично.
Таким образом, для решения поставленной задачи необходимо найти такие струк-
туры графов множества ∗G , которые максимизируют байесовский информационный кри-
терий:
114 ISSN 1028-9763. Математичні машини і системи, 2010, № 4
}),(maxarg{ DGLG
G Γ∈
∗ = ,
где Γ – множество графов-претендентов. Особенностью байесовского информационного
критерия для ДБС является его аддитивность по отношению к свойствам БС, составляю-
щих ДБС [1, 4]. То есть, структурное обучение может быть выполнено отдельно для 0B и
→B .
Алгоритм поиска →B , максимизирующий байесовский информационный критерий
для случая, когда множество Γ содержит только такие →G , для которых выполняется ус-
ловие ki kXPa Ψ⊆+ ])1[( (то есть, связи внутри слоев →B отсутствуют), схематически
представлен на рис. 2.
for },,1{ ni K∈
for kΨ2∈Ψo
}][]1[][{ oΨ∈+→=→ kXkXkXg jij
=→→
′′ )}(ˆ{ ,, g
ii rxiθ
∑ →→
′′
→→
′′
i
i
i
x
rxi
rxi
gN
gN
)(
)(
,,
,,
if ),(),( DgLDgL i
∗→ > then →∗ = gg i
U
i
igG ∗∗
→ =
Рис. 2. Алгоритм поиска наилучшего ∗
→G
на основе ),( DGL
Рассмотрим свойства выборочной оценки УРВ )/]1[(ˆ o
ki kXP Ψ+ . Предположим, что
случайная величина ]1[ +kX i находится в вероятностной зависимости от случайных вели-
чин kki kXPa Ψ⊆Ψ=+ ∗])1[( ; тогда очевидно, что в случае oo
kkkk Ψ⊂ΨΨ≠Ψ ∗∗, оценка
)/]1[(ˆ o
ki kXP Ψ+ будет содержать повторяющуюся информацию об УРВ )/]1[( ∗Ψ+ ki kXP в
отличие от оценки )/]1[(ˆ ∗Ψ+ ki kXP . Можно утверждать, что при любых фиксированных
значениях )\( ∗ΨΨ∈′ kki Valq для случайных величин ∗ΨΨ kk \ , от которых не зависит
]1[ +kX i , будет иметь место сходимость по вероятности:
)./]1[()}\{,/]1[(ˆ, ∗∗∗ Ψ+→′=ΨΨΨ+′∀ ki
p
ikkkii kXPqkXPq
Однако, если ])1[( +≠Ψ∗ kXPa ik , сходимости не будет. Отсюда следует, что в ре-
зультате сравнения выборочных законов распределения вероятностей ),,(ˆ
iki qXF ′Ψ o и
),(ˆ oo
ki XF Ψ , полученных на основе оценок распределений вероятностей
)}\{,/]1[(ˆ
ikkki qkXP ′=ΨΨΨ+ oo и )/]1[(ˆ o
ki kXP Ψ+ для различных iq′ , можно судить о нали-
чии или отсутствии указанной сходимости для множества кандидатов kk Ψ⊂Ψo . Проверку
гипотез об одинаковости выборочных законов распределения вероятности ),,(ˆ
iki qXF ′Ψ o и
),(ˆ oo
ki XF Ψ можно осуществить на основе критерия согласия Колмогорова.
5. Статистическая методика структур-
ного обучения ДБС
В рамках классического статистического
подхода задача данной работы может
быть рассмотрена как задача проверки
гипотез Γ∈mg gH
m
, о структуре графов
G ДБС. Без существенной потери общ-
ности результатов исследования ограни-
чимся проверкой гипотез →
mg
H о структу-
ре графа →G ДБС, так как решение этой
подзадачи является основным вопросом
структурного обучения ДБС. Для провер-
ки вышеуказанных гипотез необходима
подходящим образом сконструированная
статистика S .
ISSN 1028-9763. Математичні машини і системи, 2010, № 4 115
Исходя из указанных свойств ),,(ˆ
iki qXF ′Ψ o и ),(ˆ oo
ki XF Ψ , для определения наилуч-
шего множества o
kΨ для случайной величины ]1[ +kX i в качестве подходящей статистики,
основанной на критерии согласия Колмогорова, может быть рассмотрена величина
∑ ∑∑
→Ψ ′
→→→ Ψ−′Ψ=
)(
))(,(ˆ)),(,(ˆsup
2
1
)(
mk ig q
mkiimki
Xν
νmi gXFqgXFTgS
o
ooo ,
где )( →Ψ mk go – множество вершин родителей для ]1[ +kX i в графе →
mg . Очевидно, что чем
ближе ),,(ˆ
iki qXF ′Ψ o к ),(ˆ oo
ki XF Ψ для любого iq′ и o
kΨ , тем меньше будет значение стати-
стики, и наоборот. Следовательно, решение рассматриваемой задачи на основе
∑ →→ =
i
mim gSgS )()( можно записать:
})(minarg{ →
Γ∈
∗
→ →→
= m
g
gSG
m
,
где →Γ – множество графов-претендентов, определяющих связи между слоями подсети
→B ДБС. Следует отметить, что в случае, когда →Γ содержит графы с различной степенью
связности вершин, указанная статистика )( →
mgS будет принимать минимальные значения
для самых «сложных графов», то есть для графов с максимальным количеством связей.
Однако, если →Γ содержит структуры «одинаковой сложности» с одинаковым количест-
вом связей, использование этой статистики позволит найти самый лучший в смысле по-
становки задачи граф →G . Чтобы снять указанное ограничение на множество →Γ , в реше-
нии задачи необходимо учесть величину, аналогичную второй части выражения байесов-
ского информационного критерия, «штрафующую» метод за сложность выбранного графа.
Но для данного исследования это ограничение не существенно, так как позволяет в полной
мере изучить принципиальные свойства статистики )( →
mgS .
for },,1{ ni K∈
for kΨ2∈Ψo
if RCard ≠Ψ )( o continue
}][]1[][{ oΨ∈+→=→ kXkXkXg jij
if )()( ∗→ < iii gSgS then →∗ = gg i
U
i
igG ∗∗
→ =
Рис. 3. Алгоритм поиска наилучшего ∗
→G
на основе )( →
mgS
Таблица 1. Выборочные данные
k 1 2 3 4 5 6
][1 kX 0 0 1 1 0 1
][2 kX 0 1 0 1 1 0
Алгоритм поиска сети →B , минимизи-
рующий статистику S для случая, когда
множество →Γ содержит только такие графы
→G , для которых выполняется условие
ki kXPa Ψ⊆+ ])1[( и RkXPaCard i =+ ]))1[(( ,
где R подается на вход алгоритма, схемати-
чески представлен на рис. 3.
В качестве примера рассчитаем значе-
ние )( 1.21
→gS для графа, приведенного на рис.
1 и одной временной выборки данных из
табл. 1. Оценки условных распределений
приведены в табл. 2 и 3.
116 ISSN 1028-9763. Математичні машини і системи, 2010, № 4
Таблица 2. Оценки условных распределений ])[],[/]1[(ˆ
211 kXkXkXP +
][2 kX ][1 kX ]1[1 +kX ])[],[/]1[(ˆ
211 kXkXkXP + ])[],[,(ˆ
211 kXqkXXF ik =′=Ψ o
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. Оценки условных распределений ])[/]1[(ˆ
11 kXkXP +
][1 kX ]1[1 +kX ])[/]1[(ˆ
11 kXkXP + ])[,(ˆ
11 kXXF k =Ψo
0 0 1/3 1/3
0 1 2/3 1
1 0 1/2 1/2
1 1 1/2 1
Расчет значения )( 1.21
→gS :
=
−−+
−−+
−−+
−−=→ 11,
2
1
1sup11,
3
1
0sup11,
2
1
0sup11,
3
1
1sup3)( 1.21 gS
46,3
2
1
3
1
2
1
3
2
3 =
+++= .
6. Экспериментальные исследования
Экспериментальные исследования выполнены методом имитационного моделирования. В
основу критерия качества структурного обучения положена мера Хэмминга )G,H(G ∗
→→ ,
позволяющая сравнивать граф →G исходной ДБС с графом ∗
→G обученной сети. Указанная
мера для двух графов с одинаковыми множествами вершин будет тем большей, чем боль-
ше отличий в соответствующих множествах ветвей.
В качестве ДБС для проведения исследова-
ний выбрана сеть со структурой, представленной
на рис. 4.
Эксперимент организован следующим об-
разом. На вход подавалось количество временных
выборок V и количество элементов множества
значений случайных величин Ζ ; без ограничения
общности полагалось, что Ζ=∀ ))((: iXValCardi .
Чтобы усреднить полученные значения критерия
качества структурного обучения, для каждого вы-
бранного V и Ζ выполнено 5 элементарных экс-
периментов. Каждый элементарный эксперимент состоял из следующих этапов:
Рис. 4. Граф →G ДБС для
экспериментальных исследований
ISSN 1028-9763. Математичні машини і системи, 2010, № 4 117
1. На основе равномерного распределения вероятностей генерировались случайные
табличные распределения условных вероятностей, описывающих связи между слоями вы-
бранной ДБС.
2. На основе метода Монте-Карло сгенерированы V временных выборок данных
мощностью 30=υT элементов, в каждой из которых любая случайная величина могла
принимать не больше, чем Ζ различных значений.
3. Выполнялось структурное обучение на основе байесовского информационного
критерия и статистического критерия. Для уменьшения вычислительной сложности и уче-
та ограничений статистической методики множество графов претендентов →Γ ограничено
следующим условием: 2]))1[(( =+kXPaCard i для обоих способов.
4. Вычислялось значение критерия качества ),GH(G ∗
→→ структурного обучения для
обоих способов.
Экспериментальные исследования направлены на изучение характера поведения
эмпирических функций:
( )∑
=
→→=
5
1
),,(
5
1
),(
E
BICBIC ZVE,GGHZVK ,
( )∑
=
→→=
5
1
),,(
5
1
),(
E
SS ZVE,GGHZVK ,
где ),,(),,,( ZVEGZVEG SBIC
→→ – графы
ДБС, полученные в результате струк-
турного обучения, выполненного по V
временным выборкам с Ζ элементами
множества значений случайных вели-
чин; E – номер элементарного экспе-
римента. Эти графы получены на основе
байесовского информационного крите-
рия и статистической методики соответ-
ственно.
Зависимости ),( ZVK BIC и
),( ZVK S при 5=Ζ и 13,3=V , полу-
ченные в результате проведенных экс-
периментов, отражены на рис. 5.
Из анализа полученных резуль-
татов для 5=Ζ и 13,3=V следует, что
при фиксированном Ζ структурное
обучение, основанное на предложен-
ной статистической методике, приво-
дит к существенно лучшим результа-
там при больших V . Аналогичный
характер поведения ),( ZVK BIC и
),( ZVK S получен и для других Ζ .
Зависимости ),( ZVK BIC и
),( ZVK S при 10,2=Ζ и 8=V , полу-
ченные в результате выполненных
экспериментов, отражены на рис. 6.
Рис. 5. Графики: )5,(VK BIC – штриховая
линия и )5,(VK S – сплошная линия
Рис. 6. Графики для ),8( ZK BIC – штриховая линия
и ),8( ZK S – сплошная линия
118 ISSN 1028-9763. Математичні машини і системи, 2010, № 4
Из анализа полученных результатов для 10,2=Ζ и 8=V следует, что при фиксиро-
ванном V структурное обучение, основанное на предложенной статистической методике,
приводит к более качественным результатам при меньших Ζ . Аналогичный характер по-
ведения ),( ZVK BIC и ),( ZVK S был получен и для других V .
7. Выводы
В работе подробно рассмотрена задача структурного обучения ДБС с позиций байесовско-
го подхода и теории вероятностей. Рассмотрен существующий алгоритм структурного
обучения на основе байесовского информационного критерия и разработаны основы мето-
дики структурного обучения на базе предложенной статистики.
Выполнен анализ полученных экспериментальных зависимостей, показывающий,
что при определенных соотношениях количества временных выборок V и количества
элементов множества значений случайных величин Ζ структурное обучение, основанное
на предложенной статистической методике, позволяет существенно повысить качество ре-
зультатов обучения ДБС. Отметим, что, как следует из экспериментальных данных, каче-
ство обучения на основе байесовского информационного критерия и предложенной стати-
стической методики обладает противоположными свойствами по отношению к Ζ и V .
В дальнейших исследованиях возможна доработка предложенной методики обуче-
ния с целью снятия ограничения на множество графов-претендентов →Γ путем учета в ме-
тодике штрафа за сложность графа. Также необходимо определить в общем виде условия
по Ζ и 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, 1998. – 169 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,
S. Russell // Proc. of the Fourteenth Conference on Uncertainty in Artificial Intelligence (UAI’98). –
1998. – P. 139 – 147.
5. Тулупьев А.Л. Байесовские сети: логико-вероятностный подход / Тулупьев А.Л., Николенко
С.И., Сироткин А.В. – СПб.: Наука, 2006. – 607 с.
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.
8. Згуровский М.З. Методы построения байесовских сетей на основе оценочных функций /
М.З. Згуровский, П.И. Бидюк, А.Н. Терентьев // Кибернетика и системный анализ. – 2008. – № 2. –
C. 81 – 88.
9. Терентьев А.Н. Методы построения байесовских сетей / А.Н. Терентьев, П.И. Бидюк // Межве-
домственный научно-технический сборник „Адаптивные системы автоматического управления”. –
Днепропетровск: Системные технологии, 2005. – № 8. – С. 130 – 141.
Стаття надійшла до редакції 22.01.2010
|