Модификация алгоритма обучения К2 для задачи адаптации байесовской нейронной сети
Сформулирована задача адаптации байесовской нейронной сети к новым данным. Произведен анализ задачи на соответствие с байесовским подходом с целью получения множества возможных стратегий решения. Для конкретной стратегии предложен алгоритм инкрементной адаптации сети к новым наблюдениям. В его основ...
Gespeichert in:
| Datum: | 2006 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
2006
|
| Schriftenreihe: | Системні дослідження та інформаційні технології |
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/42196 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Модификация алгоритма обучения К2 для задачи адаптации байесовской нейронной сети / С.А. Катеринич // Систем. дослідж. та інформ. технології. — 2006. — № 4. — С. 33–43. — Бібліогр.: 10 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-42196 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-421962025-02-09T13:29:32Z Модификация алгоритма обучения К2 для задачи адаптации байесовской нейронной сети Модифікація алгоритму навчання К2 для задачі адаптації байєсівської нейронної мережі Modification of K2 algorithm for adaptation of Bayesian neural network Катеринич, С.А. Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи Сформулирована задача адаптации байесовской нейронной сети к новым данным. Произведен анализ задачи на соответствие с байесовским подходом с целью получения множества возможных стратегий решения. Для конкретной стратегии предложен алгоритм инкрементной адаптации сети к новым наблюдениям. В его основу положен пакетный алгоритм К2 обучения, на базе которого разработаны критерии, используемые при адаптации. Сформульовано задачу адаптації байєсівської нейронної мережі до нових даних. Проведено аналіз задачі на відповідність до байєсівського підходу з метою отримання множини можливих стратегій розв’язання. Для конкретної стратегії запропоновано алгоритм інкрементної адаптації мережі до нових спостережень. В його основу покладено пакетний алгоритм К2 навчання, на базі якого розроблено критерії, які використовуються при адаптації. The problem of Bayesian neural network adaptation to new data was formulated and analyzed in accordance with the Bayesian approach to obtain a set of possible strategies for the problem solution. For concrete strategy, an algorithm for incremental adaptation of the Bayesian neural network to new observations was developed. The К2 network construction batch algorithm was used as a basis of the adaptation algorithm to provide necessary adaptation criteria. 2006 Article Модификация алгоритма обучения К2 для задачи адаптации байесовской нейронной сети / С.А. Катеринич // Систем. дослідж. та інформ. технології. — 2006. — № 4. — С. 33–43. — Бібліогр.: 10 назв. — рос. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/42196 62-50 ru Системні дослідження та інформаційні технології application/pdf Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи |
| spellingShingle |
Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи Катеринич, С.А. Модификация алгоритма обучения К2 для задачи адаптации байесовской нейронной сети Системні дослідження та інформаційні технології |
| description |
Сформулирована задача адаптации байесовской нейронной сети к новым данным. Произведен анализ задачи на соответствие с байесовским подходом с целью получения множества возможных стратегий решения. Для конкретной стратегии предложен алгоритм инкрементной адаптации сети к новым наблюдениям. В его основу положен пакетный алгоритм К2 обучения, на базе которого разработаны критерии, используемые при адаптации. |
| format |
Article |
| author |
Катеринич, С.А. |
| author_facet |
Катеринич, С.А. |
| author_sort |
Катеринич, С.А. |
| title |
Модификация алгоритма обучения К2 для задачи адаптации байесовской нейронной сети |
| title_short |
Модификация алгоритма обучения К2 для задачи адаптации байесовской нейронной сети |
| title_full |
Модификация алгоритма обучения К2 для задачи адаптации байесовской нейронной сети |
| title_fullStr |
Модификация алгоритма обучения К2 для задачи адаптации байесовской нейронной сети |
| title_full_unstemmed |
Модификация алгоритма обучения К2 для задачи адаптации байесовской нейронной сети |
| title_sort |
модификация алгоритма обучения к2 для задачи адаптации байесовской нейронной сети |
| publisher |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| publishDate |
2006 |
| topic_facet |
Прогресивні інформаційні технології, високопродуктивні комп’ютерні системи |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/42196 |
| citation_txt |
Модификация алгоритма обучения К2 для задачи адаптации байесовской нейронной сети / С.А. Катеринич // Систем. дослідж. та інформ. технології. — 2006. — № 4. — С. 33–43. — Бібліогр.: 10 назв. — рос. |
| series |
Системні дослідження та інформаційні технології |
| work_keys_str_mv |
AT kateriničsa modifikaciâalgoritmaobučeniâk2dlâzadačiadaptaciibajesovskojnejronnojseti AT kateriničsa modifíkacíâalgoritmunavčannâk2dlâzadačíadaptacííbajêsívsʹkoínejronnoímereží AT kateriničsa modificationofk2algorithmforadaptationofbayesianneuralnetwork |
| first_indexed |
2025-11-26T05:46:54Z |
| last_indexed |
2025-11-26T05:46:54Z |
| _version_ |
1849830686576345088 |
| fulltext |
© С.А. Катеринич, 2006
Системні дослідження та інформаційні технології, 2006, № 4 33
УДК 62-50
МОДИФИКАЦИЯ АЛГОРИТМА ОБУЧЕНИЯ К2 ДЛЯ ЗАДАЧИ
АДАПТАЦИИ БАЙЕСОВСКОЙ НЕЙРОННОЙ СЕТИ
С.А. КАТЕРИНИЧ
Сформулирована задача адаптации байесовской нейронной сети к новым дан-
ным. Произведен анализ задачи на соответствие с байесовским подходом с це-
лью получения множества возможных стратегий решения. Для конкретной
стратегии предложен алгоритм инкрементной адаптации сети к новым наблю-
дениям. В его основу положен пакетный алгоритм К2 обучения, на базе кото-
рого разработаны критерии, используемые при адаптации.
ВВЕДЕНИЕ
В современном мире информационных технологий для получения знаний
широко используется задача обработки больших баз данных (БД). Вот уже
более двух десятков лет байесовские нейронные сети (БНС) привлекают
внимание исследователей как инструмент обработки БД в решении задач
классификации и моделирования процессов, информация о которых собрана
в этих базах.
Байесовская нейронная сеть — это вероятностная непараметрическая
модель, которая состоит из двух элементов: графической структуры сети и
ее вероятностной спецификации. Именно графическая структура, обеспечи-
вающая преимущества при моделировании и визуализации его результата,
обусловила большой интерес к данному инструменту. Этот вид моделей яв-
ляется непараметрическим в том смысле, что взаимосвязь между перемен-
ными определяется без ссылки на конкретный вид распределения, т.е. кон-
фигурация модели однозначно определяет совместное распределение
вероятностей всех переменных модели.
Графическая структура задается ориентированным ациклическим гра-
фом, в котором узлы представляют интересующие нас переменные, а дуги
от родительских узлов к узлам-потомкам — вероятностные взаимосвязи
между данными узлами [1, 2]. Узел jX является родителем, или непосред-
ственным предком, узла iX , если существует дуга от jX к iX , что тракту-
ется как « jX непосредственно влечет появление iX ».
Вероятностная спецификация задается распределением условных
вероятностей для значений каждого узла iX сети относительно возможных
инициализаций множества iΠ родительских узлов (непосредственных
предшественников). Для корневых узлов, т.е. узлов без входных дуг, опре-
деляется априорное распределение вероятностей. Таким образом, неопреде-
ленность влияния родителей на потомка описывается вероятностями.
Одной из наиболее привлекательных возможностей такого подхода яв-
ляется графическая интерпретация результатов моделирования, интуитивно
С.А. Катеринич
ISSN 1681–6048 System Research & Information Technologies, 2006, № 4 34
понятная лицу, принимающему решения (ЛПР). Графическая интерпре-
тация — это визуализация причинно-следственных взаимосвязей между
элементами процесса, моделируемого с помощью БНС (см. рисунок).
Для краткости изложения некоторые условные вероятности не отраже-
ны на рисунке, однако их можно без труда получить из указанных, напри-
мер:
25,075,01)|(1)|( =−===−=== TATGPTAFGP .
Здесь вероятностная спецификация сети неявно задана с помощью таб-
лиц условного распределения вероятностей. Явный вид таблицы условного
распределения вероятностей для каждого узла может быть получен на осно-
вании выводов, аналогичных приведенному выше. Так, например, для узла
S , значения которого обусловлены значениями узлов G и C , таблица бу-
дет иметь следующий вид:
Условные вероятности событий, соответствующие рисунку:
10,0)( ==TAP ; 75,0)|( === TATGP ; 15,0)|( === FATGP ;
40,0)|( === TATCP ; 01,0)|( === FATCP ;
80,0)|( === TGTVP ; 05,0)|( === FGTVP ;
95,0),|( ==== TCTGTSP ; 40,0),|( ==== TCFGTSP ;
75,0),|( ==== FCTGTSP ; 05,0),|( ==== FCFGTSP ;
95,0)|( === FCTRP ; 25,0)|( === TCTRP .
Теоретические аспекты обучения БНС изложены в работе [3].
G C 1=S 0=S
1 1 0,95 0,05
1 0 0,75 0,25
0 1 0,40 0,60
0 0 0,05 0,95
Пациент
нуждается
в очках
A
G C
V S R
Возраст>75
Катаракта
Косоглазие Жалобы на
плохое зрение
Дефекты
сетчатки
Пример байесовской сети из области дефектов зрения
Модификация алгоритма обучения К2 для задачи адаптации …
Системні дослідження та інформаційні технології, 2006, № 4 35
Различными авторами было предложено несколько подходов к реше-
нию задачи построения БНС, каждый из которых воплотился в конкретный
алгоритм обучения БНС. Среди них алгоритм на основе принципа мини-
мальной длины описания сети (MDL) [4], алгоритмы обучения байесовских
классификаторов [5], инкрементный алгоритм [6] и пр.
Одним из алгоритмов обучения стал К2, предложенный Edward
Herskovits в работе [7]. Это пакетный (batch) алгоритм обработки БД наблю-
дений, т.е. алгоритм целостной обработки всей базы наблюдений в ходе по-
строения структуры сети. Главной особенностью К2 является реализация
байесовского подхода к задаче обучения БНС, а также предложенная
Herskovits функция оценивания (критерий, функционал качества, scoring
function) адекватности структуры БНС данным базы наблюдений. Наиболее
интересным свойством этой функции является локальность вычислений, т.е.
значение критерия адекватности состоит из значений, вычисляемых для ка-
ждого узла в отдельности.
Хотя поиск структуры БНС, используемый в алгоритме К2, реализуется
в ускоренном варианте за счет дополнительного требования к подаче вход-
ной информации об узлах сети, такой вариант все-таки относится к типу
greedy search, т.е. в конкретных случаях его вычислительная трудоемкость
может достигать экспоненциальной сложности, так как задача обучения
БНС изначально относится к NP-классу.
Таким образом, возникает объективная необходимость разработки мо-
дификации данного алгоритма, которая бы реализовывала инкрементный
подход для задачи адаптации БНС, полученной в результате пакетной обра-
ботки БД алгоритмом К2. Инкрементный подход — это стратегия корректи-
ровки структуры построенной модели при получении очередного нового
наблюдения с последующим добавлением его к исходной БД, используемой
при построении текущей структуры модели.
Среди альтернативных подходов к задаче адаптации БНС наиболее
фундаментальными являются направления, базирующиеся на принципе ми-
нимальной длины описания сети (MDL) [8] и на функционалах качества,
позволяющих сравнить модели распределений из различных по объему БД
[9], на концепции частичных и альтернативных теорий [10].
ПОСТАНОВКА ЗАДАЧИ
Необходимо разработать инкрементный алгоритм, позволяющий адаптиро-
вать байесовскую нейронную сеть, построенную по заданной базе наблюде-
ний, к новым наблюдениям.
Исходные данные задачи:
• БД наблюдений, соответствующая требованиям предположений ал-
горитма К2.
• БНС, построенная в результате пакетной обработки базы наблюде-
ний алгоритмом К2.
• База новых наблюдений, не использованных в построении БНС.
С.А. Катеринич
ISSN 1681–6048 System Research & Information Technologies, 2006, № 4 36
ОБОЗНАЧЕНИЯ
Z — множество узлов БНС. Определяется набором переменных на-
блюдения из БД.
iX — узел БНС, соответствующий одной переменной наблюдения из
БД.
Zn = — количество узлов БНС.
ir — количество значений, принимаемых узлом iX .
ikv — k -е значение переменной iX .
iΠ — множество узлов-предков узла iX .
iφ — множество возможных инициализаций iΠ .
iiq φ= — количество возможных инициализаций iΠ .
ijφ — j -я инициализация множества узлов-предков iΠ узла iX .
SB — структура БНС.
PB — вероятностная спецификация БНС, т.е. часть описания модели,
представляющая вероятностные характеристики БНС.
),|( Pijikiijk BvXP φθ == , при этом 1=∑
k
ijkθ .
),...,( 1 iijrijf θθ — функция плотности распределения вероятностей для
узла iX и инициализации ijφ .
0D — исходная база данных наблюдений.
0S — структура БНС, полученная в результате пакетной обработки ба-
зы 0D .
1D — БД новых наблюдений, не использованных при построении 0S .
1S — структура БНС, полученная после адаптации 0S к новым дан-
ным 1D .
ОБЩИЕ ПОЛОЖЕНИЯ АДАПТАЦИОННОГО ВАРИАНТА АЛГОРИТМА К2
Поскольку в методе адаптации байесовской нейронной сети используется
функционал качества, положенного в основу алгоритма K2 обучения байе-
совской нейронной сети, то необходимо рассмотреть исходные предполо-
жения алгоритма K2 [7].
1. Для построения модели используются только переменные из БД. Все
переменные дискретные, поэтому понятия «узел» и «переменная» в отноше-
нии БНС употребляются как синонимы.
2. Наблюдения, накопленные в БД, появлялись независимо друг от
друга. Структура вероятностной модели, по которой могли быть получены
эти наблюдения, является неизменной на протяжении всего промежутка на-
блюдения. В случае, когда реальные наблюдения взаимосвязаны некоторы-
ми характеристиками, можно увеличить количество характеристик наблю-
Модификация алгоритма обучения К2 для задачи адаптации …
Системні дослідження та інформаційні технології, 2006, № 4 37
дения, добавив в БД дополнительные переменные, описывающие эти взаи-
мосвязи.
3. Каждое наблюдение является полным, т.е. содержит информацию
обо всех наблюдаемых переменных. Данное требование может быть смягче-
но [2].
4. Функции плотности распределения вероятностей ),...,( 1 iijrijf θθ и
),...,(
0000 1 irjijif θθ являются независимыми для всех nii ≤≤ 0,1 , qj ≤≤1 ,
001 qj ≤≤ , 00 jiij ≠ . Это предположение представим в виде
∏∏
= =
=
n
i
q
j
ijrijSP
i
i
fBBf
1 1
1 ),...,()|( θθ .
5. ),...,( 1 iijrijf θθ — равномерное распределение, т.е. =),...,( 1 iijrijf θθ
ijC= , где const=ijC . Это интерпретируется так: мы не отдаем предпочте-
ния в выборе значений условных вероятностей
iijrij θθ ,...,1 какому-то одному
из наборов значений.
Далее определим дополнительные аспекты решения задачи адаптации,
наследуемые от алгоритма К2, которые определяют как концептуальный
подход к задаче адаптации, так и практические вопросы реализации алго-
ритма адаптации.
1. Задача адаптации байесовской нейронной сети рассматривается с
использованием байесовского подхода по аналогии с задачей обучения БНС
для алгоритма К2.
2. В роли функционала качества используется функция, положенная в
основу К2. Свойство локальности данной функции учитывается при по-
строении алгоритма адаптации.
3. В качестве требования к входной информации сохраняется задание
последовательности узлов БНС, определяющей причинно-следственные
отношения между узлами.
БАЙЕСОВСКИЙ ПОДХОД К ЗАДАЧЕ АДАПТАЦИИ БНС К НОВЫМ
ДАННЫМ
Пусть имеется некоторая база наблюдений. Необходимо предсказать сле-
дующие события, которые могли бы быть получены на основании того же
распределения, которое описывается накопленной базой наблюдений. Пусть
имеются априорные распределения по возможным структурам моделей и по
значениям параметров данных моделей. Тогда байесовский подход требует
оценки апостериорного распределения на пространстве моделей при усло-
вии наблюдения данных, накопленных в базе. В этом случае используются,
в частности, преобразования на основе формулы условной вероятности.
Рассмотрим применение такого подхода к задаче адаптации БНС.
Пусть имеется исходная БД наблюдений 0D , по результатам обработки
которой получена БНС со структурой 0S .
С.А. Катеринич
ISSN 1681–6048 System Research & Information Technologies, 2006, № 4 38
Пусть в следующий момент времени пришла информация 1D о новом
наблюдении, и необходимо адаптировать сеть 0S , т.е. получить 1S .
Исходная задача построения 0S формулируется следующим обра-
зом [1]:
S
DSP max)|( 0 → .
В свете байесовского подхода решение задачи обучения БНС имеет
вид [1]
)(
)|()(
maxarg)|(
0
0
00 DP
SDPSP
DSP
S
= .
При условии индифферентности с точки зрения предпочтений той или
иной структуры БНС задача сводится к виду [1]
)|(maxarg)|( 000 SDPDSP
S
= .
Аналогично задача адаптации БНС может быть представлена как опти-
мизационная задача
S
DSDSP max),,|( 100 → .
Используя правило цепи (chain rule) для представления совместной ве-
роятности ),,,( 100 DSDSP , можно получить в качестве одного из вариантов
следующий результат:
==
),|()|()(
),,|(),|()|()(
),,|(
001000
0100100
001 DSDPDSPDP
DSDSPDSDPDSPDP
SDDSP
),|(
),|()|(
),|()|()(
)|(),|()|()(
001
010
001000
000100
DSDP
DSDPDSP
DSDPDSPDP
DSPDSDPDSPDP
== .
Таким образом, решение оптимизационной задачи адаптации можно
получить в виде
),|(
),|()|(
maxarg),,|(
001
010
0011 DSDP
DSDPDSP
SDDSP
S
= .
Такой вид оптимизируемого выражения может быть использован для
определения стратегии адаптации БНС. Рассмотрим каждую составляющую
выражения.
Знаменатель — это значение, не зависящее от аргумента оптимизации.
Он выполняет некоторую нормирующую функцию, но как таковой для про-
цесса оптимизации интереса не представляет. Однако учтем его логический
смысл: знаменатель показывает, насколько вероятно появление наблюдений
1D при условии истории процесса 0D и наличия построенной модели этого
процесса 0S . Т.е. он может быть интерпретирован как уровень адекватности
новых данных уже имеющейся информации о процессе и как вклад новых
данных в процесс обучения БНС.
Модификация алгоритма обучения К2 для задачи адаптации …
Системні дослідження та інформаційні технології, 2006, № 4 39
Числитель оптимизируемой дроби — это произведение двух состав-
ляющих. Первая совпадает с исходной задачей построения БНС по ис-
ходной базе наблюдений. Решением этой задачи была сеть 0S , наиболее
вероятная на момент отсутствия дополнительной информации 1D . Вторая
составляющая отражает уровень адекватности новых наблюдений некото-
рой структуре сети. Если учесть ход алгоритма К2, то можно определить
возможную тактику построения сети 1S . Для этого проанализируем
функционал качества алгоритма К2.
АНАЛИЗ ФУНКЦИОНАЛА КАЧЕСТВА АЛГОРИТМА К2
Функционал качества алгоритма К2 имеет вид
∏∏ ∏
= = =−+
−
=
n
i
q
j
r
k
ijk
iij
i
P
i i
N
rN
r
BDP
1 1 1
!
)!1(
)!1(
)|( ,
где ∑
=
=
ir
k
ijkij NN
1
, ijkN — количество наблюдений из базы данных D , в
которых };{ ijiiki vX φπ == .
Рассмотрим случай получения одного нового наблюдения, т.е. 11 =D .
Пусть данное наблюдение инициализирует узел iX значением
0ikv , а мно-
жество узлов-предков iΠ — набором
0ijφ . Тогда
=
−+
−
=∏∏ ∏
= = =
n
i
q
j
r
k
ijk
iij
i
i i
N
rN
r
SDDP
1 1 1
001 !
)!1(
)!1(
)|,(
=
−+
−
−+
−
=∏ ∏ ∏
=
≠
=
≠
=
!!
)!1(
)!1(
)!1(
)!1(
00
0 0
01 1 1
kij
n
i
q
jj
j
r
kk
k
ijk
iij
i
iij
i NN
rN
r
rN
r i i
=+
+−+
−
=∏∏ ∏
= = =
)1(1!
)!1(
)!1(
00
01 1 1
kij
iij
n
i
q
j
r
k
ijk
iij
i N
rN
N
rN
ri i
∏
= +
+
=
n
i iij
kij
rN
N
SDP
1
00
0
00
1
)|( .
С другой стороны,
),|()|()|,( 00100001 SDDPSDPSDDP = .
Таким образом, получаем
∏
= +
+
=
n
i iij
kij
rN
N
SDDP
1
001
0
00
1
),|( .
С.А. Катеринич
ISSN 1681–6048 System Research & Information Technologies, 2006, № 4 40
Как указывалось ранее, данное значение может быть интерпретировано
как вклад новых данных в процесс обучения БНС.
Теперь рассмотрим одну из итераций алгоритма К2 обучения БНС.
Пусть на момент начала текущей итерации построена структура се-
ти 0S .
Пусть на момент окончания текущей итерации построена структура се-
ти 1S добавлением дуги от 1iX к 2iX . Тогда )|()|( 1000 SDPSDP < .
Значения функционала качества для этих структур сетей будут отли-
чаться значением множителя
∏ ∏
= =−+
−2 2
2
22
2
1 1
!
)!1(
)!1(i iq
j
r
k
jki
iji
i N
rN
r
При этом 1
0
2
1
2 i
S
i
S
i rqq = .
Рассмотрим влияние дополнительного наблюдения 1D на значение
данного множителя. Пусть новое наблюдение инициирует узел 2iX значе-
нием
02kiv , а множество узлов-предков
2iΠ — набором
02 jiφ . Тогда множи-
тель принимает вид
202
002
2 2
2
22
2
1
!
)!1(
)!1(
1 1 iji
kji
q
j
r
k
jki
iji
i
rN
N
N
rN
ri i
+
+
⎥
⎥
⎦
⎤
⎢
⎢
⎣
⎡
−+
−
∏ ∏
= =
.
Обозначим появившийся коэффициент изменения
202
002
1
delete
iji
kji
rN
N
K
+
+
= .
Данный коэффициент рассмотрим для ретроспективного анализа влия-
ния новых наблюдений на ход обучения БНС.
Таким образом, используя локальность функционала качества алгорит-
ма К2, получаем индикаторы необходимости адаптации той или иной дуги.
АДАПТАЦИОННЫЙ ВАРИАНТ АЛГОРИТМА К2
Адаптацию построенной сети проведем в следующем порядке.
1. Корректировка вероятностной части модели.
2. Корректировка структурной части модели:
2.1. Удаление несоответствующих дуг.
2.2. Добавление дуг.
С целью облегчения проведения корректировки вероятностной части
модели полезно хранить не таблицы распределения условных вероятностей,
а значения ijkN . Это позволит быстрее обновлять данные о распределении
условных вероятностей, а их значения вычислять, пользуясь формулой Ди-
рихле
Модификация алгоритма обучения К2 для задачи адаптации …
Системні дослідження та інформаційні технології, 2006, № 4 41
iij
ijk
ijiiki rN
N
vXP
+
+
==Π=
1
)|( φ .
При корректировке структуры БНС порядок обхода узлов определим
вкладом каждого узла в значение ∏
= +
+
=
n
i iij
kij
rN
N
SDDP
1
001
0
00
1
),|( .
Для каждого узла на этапе проверки дуг на необходимость удаления
вычисляется значение )( 0delete SK для текущей конфигурации множества
узлов-предков и )( 1delete
mSK − для конфигураций, получаемых при удалении
одной из M входящих в текущий узел дуг, Mm ≤≤1 . Если выполняется ус-
ловие )()( 0delete1delete SKSK m ≤− , то m-я дуга остается в структуре сети, так
как удаление данной дуги приводит к уменьшению локального значения
функционала качества (для текущего узла). Иначе дуга заносится в список
дуг, подлежащих проверке на удаление. Список может быть отсортирован
по возрастанию значения )( 1delete
mSK − . Дуги из списка рассматриваются
последовательно. Дальнейшая проверка заключается в вычислении локаль-
ного значения функционала качества при исходной конфигурации и конфи-
гурациях, получаемых при удалении одной из дуг, оставшихся в списке.
Если учесть вид решения оптимизационной задачи адаптации БНС, то
тактика удаления дуг должна приводить к тому, что первая составляющая
числителя )|( 0DSP будет уменьшаться, поскольку она достигает максиму-
ма при 0SS = как результат начального построения БНС. Таким образом,
для получения эффекта от адаптации необходимо потери от удаления дуги
компенсировать эффектом от добавления новой дуги.
Имея упорядоченную последовательность узлов (входное требование
алгоритма К2), поиск дуги претендента на добавление следует осуществлять
в следующем порядке. Оценка дуги производится вычислением локального
значения функционала качества. Соответственно, претендент на добавление
должен определять конфигурацию входных дуг, имеющую наибольшее ло-
кальное значение функционала качества.
После каждого удаления следует попытка добавить одну из возможных
дуг набора предков-претендентов, в который также добавляется предок уда-
ленной дуги. Если в результате такой попытки было определено, что уда-
ленная дуга максимально увеличивает локальное значение функционала ка-
чества по сравнению с прочими претендентами, то эта дуга возвращается в
структуру, и переходим к оценке удаления следующей дуги.
Если после удаления дуги, первой дугой, выбранной для добавления,
является не удаленная дуга, то итерация добавления проводится до тех пор,
пока не наступит один из исходов:
1) все претенденты добавлены, включая удаленную дугу, добавленную
последней;
2) на очередной итерации выбрана ранее удаленная дуга, которая воз-
вращается в структуру;
С.А. Катеринич
ISSN 1681–6048 System Research & Information Technologies, 2006, № 4 42
3) на очередной итерации нельзя повысить локальное значение функ-
ционала качества добавлением новой дуги из набора предков-претендентов.
Если этот исход наступает при анализе последней дуги из претендентов на
удаление, то для данного узла нет надобности проводить процедуру 2.2.
Для узлов, не имеющих дуг претендентов на удаление, производится
только проверка необходимости добавления новой дуги. В соответствии с
алгоритмом К2 процедура добавления дуг проводится по каждому узлу в
порядке его местонахождения во входящей последовательности узлов до тех
пор, пока ни одна из оставшихся дуг не будет способна увеличить локальное
значение функционала качества.
АНАЛИЗ РЕЗУЛЬТАТОВ АДАПТАЦИИ БНС
Критерием эффективности адаптации может служить соотношение величин
)|,( 001 SDDP и )|,( 101 SDDP .
Наиболее интересен такой результат адаптации, когда >)|,( 001 SDDP
)|,( 101 SDDP> , что возможно в случае нарушения исходных предположе-
ний, на которые опирается алгоритм К2. Изменение характера моделируе-
мого процесса, т.е. нестационарность потенциальной структуры вероятност-
ной модели, является наиболее значимым фактором, способным вызывать
подобный результат. В данном случае наилучшим решением будет построе-
ние модели с самого начала на основании дополненной БД.
В принципе, в качестве альтернативы адаптации БНС можно видеть пе-
риодическое переобучение БНС по обновляемой БД. Критерием необходи-
мости переобучения может служить ),|( 001 SDDP , значение которого ин-
терпретируется как вклад новых данных в процесс обучения БНС. На
практике этот вариант может применяться в случаях работы с процессами,
характеризующимися высокой интенсивностью поступления новых наблю-
дений, когда временные затраты на адаптацию несравнимо велики по отно-
шению к усредненному периоду обновления данных.
ВЫВОДЫ
Рассмотрен вариант построения алгоритма инкрементной адаптации ранее
построенных БНС к новым данным на основе анализа базовых положений
алгоритма К2 обучения БНС.
В результате применения байесовского подхода к задаче адаптации по-
лучены возможные стратегии адаптации, одна из которых применена для
разработки конкретной процедуры инкрементной адаптации.
Использование декомпозиции функционала качества с последующим
ретроспективным анализом позволяет получить критерии, необходимые для
процедуры инкрементной адаптации модели к новым данным.
На основании теоретических положений разработанного алгоритма
адаптации проведен анализ возможных результатов его работы.
Модификация алгоритма обучения К2 для задачи адаптации …
Системні дослідження та інформаційні технології, 2006, № 4 43
Дальнейшие разработки, на наш взгляд, следует проводить в таких на-
правлениях:
• Смягчение исходных требований алгоритма.
• Разработка алгоритма пакетной адаптации.
Пакетный подход подразумевает такой алгоритм адаптации, при кото-
ром принятие решения о необходимой корректировке какой-либо состав-
ляющей модели происходит на основе целостного анализа всего пакета
новых наблюдений, тогда как при инкрементной адаптации каждое наблю-
дение из нового пакета анализируется последовательно для определения
необходимости изменения структуры модели. В общем случае инкремент-
ный подход — частный случай пакетного, однако при разработке конкрет-
ных алгоритмов для конкретных предметных областей инкрементный под-
ход может оказаться предпочтительней.
ЛИТЕРАТУРА
1. Cooper G.F., Herskovits E. A Bayesian method for the introduction of probabilistic
networks from data // Technical Report KSL-91-02. Knowledge Systems Labora-
tory. — Stanford: Stanford University, 1991. — 39 p.
2. Murphy K. A Brief Introduction to Graphical Models and Bayesian Networks. —
http://www.cs.berkeley.edu/~murphyk/Papers/intel.ps.gz.
3. Heckerman D. A tutorial on learning Bayesian networks / Technical report MSN-
TR-95-06, Microsoft Research, Advanced Technology Division, 1995. — 52 p.
4. Lam W., Bacchus F. Learning Bayesian belief networks. An approach based on the
MDL principle // Computational intelligence. — 1994. — № 4 — Р. 104–127.
5. Sacha J.P. New synthesis of Bayesian network classifiers and cardiac SPECT image
interpretation. — http://jbnc.sourceforge.net/.
6. Roure J., Sanguesa R. Incremental methods for Bayesian network learning. —
http://citeseer.ist.psu.edu/.
7. Herskovits E. Computer-Based Probabilistic-Network Construction. – http://search.
microsoft.com/.
8. Lam W., Bacchus F. Using new data to refine Bayesian network // Proc. of the Tenth
Conference on Uncertainty in Artificial Intelligence. — 1994. — Р. 383–390.
9. Friedman N., Goldszmidt M. Sequential update of Bayesian network structure //
Proc. of the Thirteenth Conference on Uncertainty in Artificial Intelligence. —
1997. — Р. 273–280.
10. Buntine W. Theory refinement on Bayesian networks // Proc. of the Seventh Confer-
ence on Uncertainty in Artificial Intelligence. — 1991. — P. 52–60.
Поступила 07.04.2006
|