Основні етапи побудови і приклади застосування мереж Байєса
Розглянуто основні формалізми мереж Байєса (МБ), їх графотеоретичне представлення. Проаналізовано методи побудови та навчання таких мереж. На основі аналізу запропоновано та обґрунтовано методику побудови і застосування МБ для конкретних задач, яка апробована при розв’язанні економічних та фінансови...
Збережено в:
| Дата: | 2007 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
2007
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/14077 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Основні етапи побудови і приклади застосування мереж Байєса / П.І. Бідюк, Н.В. Кузнєцова // Систем. дослідж. та інформ. технології. — 2007. — № 4. — С. 26-39. — Бібліогр.: 10 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-14077 |
|---|---|
| record_format |
dspace |
| spelling |
Бідюк, П.І. Кузнєцова, Н.В. 2010-12-10T17:26:42Z 2010-12-10T17:26:42Z 2007 Основні етапи побудови і приклади застосування мереж Байєса / П.І. Бідюк, Н.В. Кузнєцова // Систем. дослідж. та інформ. технології. — 2007. — № 4. — С. 26-39. — Бібліогр.: 10 назв. — укр. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/14077 62-50 Розглянуто основні формалізми мереж Байєса (МБ), їх графотеоретичне представлення. Проаналізовано методи побудови та навчання таких мереж. На основі аналізу запропоновано та обґрунтовано методику побудови і застосування МБ для конкретних задач, яка апробована при розв’язанні економічних та фінансових задач (кредитування, аналізу причин повернення товарів) з використанням різних програмних засобів. The basic formalism, graph-theoretical presentation as well as methods of building and training of the Bayesian networks are discussed. The methodology of building and using them for specific problems is proposed and tested in solving economy and finance problems (such as crediting and purchase returning) using different tools of software. Рассмотрены основные формализмы сетей Байеса (СБ), их графо-теоретическое представление. Проанализированы методы построения и обучения таких сетей. На основе анализа предложена и обоснована методика построения и применения СБ для конкретных задач, которая апробирована при решении экономических и финансовых задач (кредитования, анализа причин возвращения товаров) с использованием различных программных средств. uk Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах Основні етапи побудови і приклади застосування мереж Байєса The basic stages of building and examples of using Bayesian Networks Основные этапы построения и примеры использования сетей Байеса Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Основні етапи побудови і приклади застосування мереж Байєса |
| spellingShingle |
Основні етапи побудови і приклади застосування мереж Байєса Бідюк, П.І. Кузнєцова, Н.В. Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах |
| title_short |
Основні етапи побудови і приклади застосування мереж Байєса |
| title_full |
Основні етапи побудови і приклади застосування мереж Байєса |
| title_fullStr |
Основні етапи побудови і приклади застосування мереж Байєса |
| title_full_unstemmed |
Основні етапи побудови і приклади застосування мереж Байєса |
| title_sort |
основні етапи побудови і приклади застосування мереж байєса |
| author |
Бідюк, П.І. Кузнєцова, Н.В. |
| author_facet |
Бідюк, П.І. Кузнєцова, Н.В. |
| topic |
Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах |
| topic_facet |
Проблеми прийняття рішень і управління в економічних, технічних, екологічних і соціальних системах |
| publishDate |
2007 |
| language |
Ukrainian |
| publisher |
Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України |
| format |
Article |
| title_alt |
The basic stages of building and examples of using Bayesian Networks Основные этапы построения и примеры использования сетей Байеса |
| description |
Розглянуто основні формалізми мереж Байєса (МБ), їх графотеоретичне представлення. Проаналізовано методи побудови та навчання таких мереж. На основі аналізу запропоновано та обґрунтовано методику побудови і застосування МБ для конкретних задач, яка апробована при розв’язанні економічних та фінансових задач (кредитування, аналізу причин повернення товарів) з використанням різних програмних засобів.
The basic formalism, graph-theoretical presentation as well as methods of building and training of the Bayesian networks are discussed. The methodology of building and using them for specific problems is proposed and tested in solving economy and finance problems (such as crediting and purchase returning) using different tools of software.
Рассмотрены основные формализмы сетей Байеса (СБ), их графо-теоретическое представление. Проанализированы методы построения и обучения таких сетей. На основе анализа предложена и обоснована методика построения и применения СБ для конкретных задач, которая апробирована при решении экономических и финансовых задач (кредитования, анализа причин возвращения товаров) с использованием различных программных средств.
|
| issn |
1681–6048 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/14077 |
| citation_txt |
Основні етапи побудови і приклади застосування мереж Байєса / П.І. Бідюк, Н.В. Кузнєцова // Систем. дослідж. та інформ. технології. — 2007. — № 4. — С. 26-39. — Бібліогр.: 10 назв. — укр. |
| work_keys_str_mv |
AT bídûkpí osnovníetapipobudoviíprikladizastosuvannâmerežbaiêsa AT kuznêcovanv osnovníetapipobudoviíprikladizastosuvannâmerežbaiêsa AT bídûkpí thebasicstagesofbuildingandexamplesofusingbayesiannetworks AT kuznêcovanv thebasicstagesofbuildingandexamplesofusingbayesiannetworks AT bídûkpí osnovnyeétapypostroeniâiprimeryispolʹzovaniâseteibaiesa AT kuznêcovanv osnovnyeétapypostroeniâiprimeryispolʹzovaniâseteibaiesa |
| first_indexed |
2025-11-25T15:59:26Z |
| last_indexed |
2025-11-25T15:59:26Z |
| _version_ |
1850517403740405760 |
| fulltext |
П.І. Бідюк, Н.В. Кузнєцова, 2007
26 ISSN 1681–6048 System Research & Information Technologies, 2007, № 4
УДК 62-50
ОСНОВНІ ЕТАПИ ПОБУДОВИ І ПРИКЛАДИ
ЗАСТОСУВАННЯ МЕРЕЖ БАЙЄСА
П.І. БІДЮК, Н.В. КУЗНЄЦОВА
Розглянуто основні формалізми мереж Байєса (МБ), їх графотеоретичне пред-
ставлення. Проаналізовано методи побудови та навчання таких мереж. На ос-
нові аналізу запропоновано та обґрунтовано методику побудови і застосування
МБ для конкретних задач, яка апробована при розв’язанні економічних та фі-
нансових задач (кредитування, аналізу причин повернення товарів) з викорис-
танням різних програмних засобів.
ВСТУП
Розвиток систем підтримки прийняття рішень (СППР) і впровадження їх у
багатьох сферах діяльності постійно вимагає розробки нових математичних,
технологічних і програмних засобів. Одним із актуальних питань є прийнят-
тя рішень з урахуванням невизначеності.
Відомо, що більшість з систем прийняття рішень у реальному часі ба-
зується на правилах. Введення у такі системи ймовірнісних оцінок та мето-
дів відображення причинно-наслідкової залежності дозволяє розширити об-
ласть застосування СППР та покращити якість запропонованих рішень.
Математичний апарат мереж Байєса (МБ) дозволяє поєднати досить просте
графічне представлення деякого процесу з його ймовірнісним характером,
проаналізувати можливі варіанти розвитку ситуації, відслідкувати правиль-
ність встановлення причинно-наслідкового зв’язку між окремими подіями і
завдяки цьому підвищити обґрунтованість рішень при аналізі складних про-
блемних ситуацій.
Мета даного дослідження — розробка практичної методики побудови
МБ на основі статистичних даних, що описують модельований процес, та
ілюстрація можливостей їх застосування.
Побудова МБ
Одним з основних етапів побудови МБ для вирішення конкретної приклад-
ної задачі є формування графо-теоретичної моделі.
Нехай ),( BiVG = — деякий граф, в якому V — скінченна множина
змінних; Bi — нерефлексивне бінарне відношення на V . Якщо дуги цього
графу спрямовані, то його називають спрямованим ациклічним графом
(САГ). Якщо спрямований граф містить хоча б один замкнений цикл, то йо-
го називають спрямованим циклічним графом (СЦГ).
Деякі змінні МБ мають спеціальні імена. Змінну (вузол) називають на-
щадком, якщо вона залежить від однієї або більше інших змінних. Батьків-
ська змінна має одну або більше змінних-нащадків. До множини нащадків
відносять змінні-нащадки, які є нащадками однієї і тієї ж батьківської змін-
Основні етапи побудови і приклади застосування мереж Байєса
Системні дослідження та інформаційні технології, 2007, № 4 27
ної, а також змінні-нащадки змінних-нащадків вищого рівня. Одна і та ж
змінна може бути батьківською змінною і нащадком одночасно. Якщо змін-
на не має жодної батьківської, то її називають кореневою. Кореневі змінні —
найважливіші змінні мережі. Це саме те, що нас цікавить. Змінну називають
листком, якщо вона не має змінних-нащадків.
Формально МБ — це трійка >=< JGVN ,, , першою компонентою
якої є множина змінних V ; другою — САГ G , вузли якого відповідають
випадковим змінним модельованого процесу; J — спільний розподіл
ймовірностей змінних },...,,{ 21 nXXXV = . При цьому виконується мар-
ковська умова: кожна змінна мережі не залежить від усіх інших, за винятком
батьківських попередників цієї змінної.
Визначення апріорних ймовірностей подій і формула Байєса
Розглянемо приклад мережі [4], у якій ймовірність перебування вершини e
у різних станах )( ke залежить від станів ),( ji dc вершин c та d і визнача-
ється виразом ,),(),|()( ∑∑ ×=
i j
jijikk dcpdcepep де ),|( jik dcep —
ймовірність перебування в стані ke у зале-
жності від станів ji dc , ( рис.1). Оскільки
події, що представлені вершинами c і d
незалежні, то )()(),|( jijik dpcpdcep = .
Розглянемо приклад більш складної мережі (рис. 2).
Рис. 2 ілюструє умовну незалежність подій. Для оцінки вершин c і d
використовуються ті самі вирази, що й для обчислення ймовірності )( kep ,
тоді
∑∑ ××=
m n
nmnmii BpApBAcpcp ),()(),|()( 1111
∑∑ ××=
m n
nmnmjj BpApBAdpdp ).()(),|()( 2222
З цих виразів видно, що вершина e умовно не залежить від вершин
2121 ,,, BBAA , оскільки не має стрілок, що безпосередньо поєднують ці
c d
e
Рис. 1. Приклад найпростішої
мережі довіри Байєса
B2 A1 B1
c
A2
d
e
Рис. 2. Дворівнева мережа довіри Байєса
П.І. Бідюк, Н.В. Кузнєцова
ISSN 1681–6048 System Research & Information Technologies, 2007, № 4 28
вершини. Саме процес обчислення ймовірностей стає основою для форму-
вання рішень в умовах невизначеності на основі МБ. Основу байєсівського
підходу складає поняття умовної ймовірності xBAP =)( . Це означає, що
при умові виникнення B (і всього іншого, що не має відношення до B ),
ймовірність виникнення A дорівнює x . Спільна ймовірність появи по-
дій A і B визначається за формулою повної ймовірності =),( BAP
)()()()|( APABPBPBAP == .
Це рівняння є фундаментальним правилом для обчислення ймовірнос-
тей і основою для теореми Байєса
)(
)()(
)(
AP
BPBAP
ABP = . З формулою пов-
ної ймовірності тісно пов’язана формула Байєса. Якщо до виконання експе-
рименту ймовірності гіпотез були )(),...,(),( 21 nHPHPHP , а в результаті
експерименту з’явилась подія A , то з урахуванням цієї події «нові», тобто
умовні ймовірності гіпотез, обчислюються за формулою Байєса
),...,2,1(
)(
)/()(
)/( nk
AP
HAPHP
AHP kk
k == ,
де )/()()(
1
i
n
i
i HAPHPAP ∑
=
= .
Умовна ймовірність )/( AHP k може бути визначена як відношення ва-
ги дуги, що проходить через вершину, яка відповідає гіпотезі kH , до ваги
всього ймовірнісного графа. Теорема Байєса застосовується у випадках, ко-
ли існує інформація про залежні змінні (свідоцтва), а суть дослідження по-
лягає у визначенні ймовірностей вихідних змінних (причин). Так, за умови
наявності умовної ймовірності )( ABP виникнення деякої події B при умо-
ві, що має місце подія A , теорема Байєса дає розв’язок оберненої задачі,
якою є ймовірність виникнення події A , якщо подія B відбулася.
Для МБ введені такі базові поняття.
• Ланцюгове правило — це засіб обчислення повної ймовірності у
байєсових мережах. Якщо МБ визначена на множині вершин =U
},...,,{ 21 nAAA= , то спільний розподіл ймовірностей є добутком усіх умов-
них ймовірностей, визначених у МБ.
∏=
i
ii AparAPUP ))(()( ,
де )( iApar — множина (станів) батьківських вершин для iA .
• Умовна незалежність вершин МБ — блокування впливу між цими
вершинами. Змінні (множини змінних) A і C є незалежними при відомому
стані змінної B , якщо ),()( CBAPBAP = . Коли стан вершини B відомий,
то ніяка інформація про C не змінює ймовірностей A .
• Маржиналізація — підсумовування ймовірностей на реалізаціях
усіх змінних, окрім вибраних. Вона використовується для обчислення ймо-
Основні етапи побудови і приклади застосування мереж Байєса
Системні дослідження та інформаційні технології, 2007, № 4 29
вірностей змінних, які нас цікавлять, на основі повної ймовірності
∑=
B
BAPAP ),()( .
• Ймовірність Байєса для деякої події x — міра упевненості деякого
експерта, що дана подія відбудеться [3]. У той час як класична ймовір-
ність — це фізична властивість реального світу, ймовірність Байєса — це
більше атрибут експерта, що її визначає.
• Логічний висновок у мережах Байєса — обчислення умовних ймовір-
ностей деяких змінних на основі наданої інформації про інші змінні.
• Розповсюдження в МБ — процес обчислення апостеріорних ймовір-
ностей для тих вузлів мережі, які не спостерігаються, на основі значень спо-
стережуваних вузлів (тобто свідоцтв).
Логічний висновок у МБ
Ключовим поняттям обчислення ймовірностей у МБ є процес оновлення
ймовірностей, або зміна міри довіри. Алгоритм цього процесу визначає спо-
сіб отримання апостеріорних ймовірностей вершин мережі на основі отри-
маної інформації. Оновлення міри довіри вершин може розглядатися як си-
нонім логічного висновку в МБ, а довіра по відношенню до них — це
розподіл ймовірностей, обумовлений усіма свідоцтвами, що поступили у
мережу.
Нехай МБ є мережею на множині змінних U , і нехай e — множина
тверджень вигляду змінна A знаходиться у стані a . Таким чином, e пред-
ставляє собою твердження спільна конфігурація вершин BA ,..., задана як
ba ,..., . При розв’язанні задач ми прагнемо знайти апостеріорний розподіл
ймовірностей )( eXP для усіх змінних UX ∈ .
Математично ця задача може бути розв’язана наступним чином:
• використати ланцюгове правило для обчислення )(UP ;
• відокремити ),( eUP — частину )(UP , яка відповідає конфігурації
),...,( ba ;
• отримати ),( eXP шляхом маржиналізації ),( eUP для кожного
UX ∈ (тобто для кожного стану Xx∈ підсумувати усі елементи ),( eUP ,
для яких X знаходиться у стані x );
• обчислити )( eXP як результат нормалізації )( eXP , тобто розділи-
ти )( eXP на суму всіх його членів.
Однак зазвичай )(UP настільки об’ємна, що її неможливо зберігати,
або необхідні обчислення можуть виявитися неприйнятно об’ємними. Від-
мовитися від використання повної ймовірності )(UP вдається при послідо-
вному застосуванні теореми Байєса.
Дійсно, задача знаходження ймовірностей )( eXP на основі множини
свідоцтв e відносно МБ може бути представлена як задача оновлення ймо-
вірностей на (під)мережі, до складу якої входить лише певна підмножина
вузлів графу. Зменшення мережі до цієї підмножини відбувається шляхом
П.І. Бідюк, Н.В. Кузнєцова
ISSN 1681–6048 System Research & Information Technologies, 2007, № 4 30
послідовного виключення вузлів (маржиналізації) і механізму інверсії ребер
графу на основі теореми Байєса. На рис. 3 показано отримання розподілу
)(CP шляхом послідовної редукції графа виключенням вершин (кроки
1, 2, 4, 5) та інверсії ребер (крок 3).
Необхідно зазначити: наслідком теореми Байєса є підтримка нею оці-
нювання ймовірностей на графі в обох напрямах. Процес формування ви-
сновку в мережі супроводжується розповсюдженням по мережі свідчень, що
надійшли. При цьому процес розповсюдження ймовірностей у МБ грунту-
ється на механізмі їх перерахунку [4]. Для спрощення обчислювального
процесу використовується метод зашумленого вентиля АБО (noisy or gate)
[5, 6]. Його суть полягає у тому, що в деяких прикладах вершина y може
бути умовно незалежною від цілого ряду вершин rx , де nr ,...,2,1= . Цей
метод використовують для обчислення n2 ймовірностей, які необхідні при
використанні таблиць умовних ймовірностей. Згідно із цим методом ймові-
рність y в залежності від n вершин rx оцінюється як =),...,,|( 21 nxxxyp
∏
=
−−=
n
i
ixyp
1
))|(1(1 , що дозволяє оцінити лише тільки ймовірності
)|(,...),|(),|( 21 nxypxypxyp і на їх основі визначити ).,...,|( 21 nxxxyp
Слід зазначити, що для визначення наступного вузла, який виключа-
ється, необхідно розглянути усю мережу повністю. Вплив свідоцтва про-
стежується лише на окремий вузол, а для виключених вузлів він невідомий.
І, нарешті, наведений алгоритм концептуально послідовний, хоча для побу-
дови життєздатних моделей людських міркувань паралелізм видається
більш адекватним.
У 1986 р. опубліковано алгоритм формування логічного висновку в МБ,
що дозволяє уникнути цих недоліків [9]. Його сутність полягає у викорис-
танні поняття повідомлення, згідно з яким оновлення ймовірностей вершин
A
E
B C D
1
A
E
B C
2
A
B C
3
A
B C
4
4
B C
5
C
Рис. 3. Приклад ймовірнісного висновку
2
Основні етапи побудови і приклади застосування мереж Байєса
Системні дослідження та інформаційні технології, 2007, № 4 31
мережі здійснюється шляхом розсилання кожною вершиною мережі двох
типів повідомлень про свій стан:
1) батьківським вершинам — π -повідомлення;
2) дочірнім — λ -повідомлення.
Міра довіри для події xX = розраховується як нормований добуток
числового еквіваленту повідомлень )(xλ і )(xπ . Не наводячи повного ма-
тематичного опису цього алгоритму, розглянемо деякі аспекти процесу об-
міну повідомленнями для обчислення апостеріорних ймовірностей.
Якщо отримано новий розподіл )(* AP для вершини A , то для обчис-
лення нового B розподілу ∑=
A
APABPBP )()()( ** можна скористатися
фундаментальним правилом обчислення ймовірностей і маржиналізацією.
Розповсюдження в напрямі зв’язків досить просте: це повідомлення,
надіслане від A до B . Це ж повідомлення і є розподілом A , і на цій основі
відбувається оновлення розподілу B . Оновлення довіри відбувається і в
протилежному напрямі: інформація щодо B може бути використана для
зміни міри довіри A . Інструментом розповсюдження ймовірностей у зворо-
тному напрямі є теорема Байєса.
Розглянемо МБ, граф якої є деревом. Повідомлення можуть надсилати-
ся в обох напрямах, тобто вершина дерева X може надіслати повідомлення
до будь-якої сусідньої вершини Y . Повідомлення, що надсилається, є пото-
чним розподілом X , і вершина Y використовує це повідомлення для онов-
лення власного розподілу.
Якщо вершини надсилають повідомлення неупорядковано, переходячи
у деякий момент часу в режим очікування, то можна довести, що у такому
разі існує стан рівноваги (стійкий стан), коли жодне подальше повідомлен-
ня не змінює жодного розподілу. Усталений стан досягається після скінчен-
ного числа пересилань, і у цьому стані кожна вершина зберігає коректний
розподіл ймовірностей.
Пересилання повідомлень упорядковується за допомогою такого пра-
вила: вершина X може надіслати повідомлення своєму сусіду Y , якщо X
отримала повідомлення від усіх своїх інших сусідів. У цьому разі листки
дерева розпочинають надсилати повідомлення і хоча б одна вершина буде
мати можливість надсилання повідомлень до тих пір, поки повідомлення не
буде надіслано по кожному ребру дерева уздовж обох напрямків. Якщо це
сталося, то дерево знаходиться у стійкому стані.
Отже, в алгоритмі, що грунтується на повідомленнях, вплив кожного
нового свідоцтва розглядається як збурення, що розповсюджується по ме-
режі шляхом обміну повідомленнями між сусідніми вершинами. Досягнення
стійкого стану при застосуванні цього алгоритму, як і гарантія коректності
результатів, вимагають існування деревоподібної структури мережі. МБ має
бути полідеревом, тобто САГ, в якому між будь-якими двома вершинами
існує лише один маршрут без урахування напрямку ребер. Це суттєве обме-
ження, оскільки більшість реальних предметних процесів неможливо змоде-
лювати на графі без циклів.
П.І. Бідюк, Н.В. Кузнєцова
ISSN 1681–6048 System Research & Information Technologies, 2007, № 4 32
Для того щоб обійти це обмеження запропоновано декілька методів.
Так, метод обумовлення враховує, що будь-яка мережа з циклом може бути
зведена до полідерева перебором станів кореневої вершини циклу (послідо-
вним обумовленням цієї вершини). Коли вершина обумовлена, тобто знахо-
диться у певному стані, можна вважати, що вона більше не є частиною ме-
режі, а замість неї розглянути стільки мереж, скільки станів ця вершина має.
Після цього теорема Байєса дозволить обчислити умовні ймовірності станів
цієї вершини при відомих розподілах ймовірностей її сусідських (дочірніх)
вершин. Необхідно обчислити стільки мереж, скільки станів має коренева
вершина кожного циклу, а тому цей метод уповільнює обчислення.
Інша ідея використовується у методі кластеризації [9], розвиненому в
роботах [7, 10]. У ролі вершин дерева у ньому виступають не окремі верши-
ни, а їх групи (кластери). За допомогою методів теорії графів аналізуються
властивості незалежності вершин мережі і формується множина кластерів,
які поєднують у дерево. Отримане дерево має властивість сполученого дере-
ва: для кожної пари ),( WV вершин дерева усі вершини маршруту між V та
W містять їх перетин WV . Сполучене дерево, отримане в результаті кла-
стеризації вершин вихідного дерева, є полідеревом, і в ньому можна засто-
сувати обмін повідомленнями. Після отримання апостеріорних ймовірнос-
тей для кластерів обчислюються ймовірності вершин вихідного дерева.
Метод кластеризації є одним з найпотужніших серед методів точного
обчислення ймовірностей на МБ. Поява і швидкий розвиток наближених
методів пояснюються тим, що в загальному випадку при зростанні кількості
змінних точне обчислення ймовірностей є вкрай складним. Задача точного
обчислення ймовірностей у МБ відноситься до класу NP-повних (причиною
нелінійної поліноміальної складності обчислень найчастіше є топологія ме-
режі, що може містити цикли). Проте встановлено [6, 7], що і наближений
ймовірнісний висновок у МБ також є NP-складним. У практичних задачах
широко використовуються саме наближені методи.
Структура мережі найчастіше визначається експертами предметної об-
ласті, хоча існують методи структурного навчання МБ на основі даних. Таб-
лиці умовних ймовірностей, навпаки, часто генеруються на основі даних за
допомогою статистичних методів. Проте слід підкреслити, що принципово
суб’єктивний байєсівський підхід не вимагає «об’єктивності» ймовірностей,
а тому дозволяє при формуванні таблиць умовних ймовірностей спиратися
на суб’єктивні оцінки експертів. Слід також зазначити, що результати логіч-
ного висновку більш чутливі до якісної структури МБ, ніж до кількісних
значень ймовірностей [10].
Навчання структури МБ
Для опису МБ необхідно визначити дві характеристики: топологію графа
(структуру) і параметри кожного умовного розподілу ймовірностей (УРЙ).
Однак навчання структури набагато складніше, ніж навчання параметрів.
У роботах [1,8] розглянуті основні чотири випадки, які мають місце при на-
вчанні мережі.
1. Відома структура, повна спостережуваність.
Основні етапи побудови і приклади застосування мереж Байєса
Системні дослідження та інформаційні технології, 2007, № 4 33
Використовується метод максимальної оцінки правдоподібності за таб-
лицею умовних ймовірностей.
2. Відома структура, часткова спостережуваність.
Використовується ЕМ-алгоритм (максимізації математичних сподівань)
для знаходження (локально) оптимальної максимальної оцінки ймовірності
параметрів.
3. Невідома структура, повна спостережуваність.
У роботі [8] для даного випадку визначається функція оцінювання, що
використовується для вибору моделі, потім обговорюються алгоритми, які
скеровані на оптимізацію цієї функції у просторі моделей, і, нарешті, дослі-
джуються їх обчислювальна і типова складність.
4. Невідома структура, часткова спостережуваність.
Розглянемо докладніше цей найскладніший випадок: структура невідо-
ма і є приховані змінні і/або втрачені дані. Для того щоб обчислити ваговий
коефіцієнт Байєса, потрібно розглянути другорядні приховані вузли і пара-
метри. Оскільки це дуже складно, то зазвичай використовують асимптотич-
не наближення до наступного критерію, названого байєсівським інформа-
ційним критерієм (БІК), який визначається таким чином:
)(dim
2
)(log))ˆ,((log))((log GNGDPDGP G −≈ θ ,
де N — кількість зразків; Gθ̂ — ML-оцінка параметрів; )(dim G — розмір-
ність моделі. Перший вираз — це лише ймовірність, а другий — штраф за
складність моделі. Хоча БІК розкладається у суму локальних виразів по од-
ному до кожного вузла локальний пошук все ж таки складний, оскільки ми
маємо виконати ЕМ-алгоритм на кожному кроці. Альтернативний підхід
полягає у тому, щоб виконати кроки локального пошуку на M -му кроці
ЕМ–алгоритму. Він називається структурованим, якщо сходиться до
локального максимуму ваги БІК.
Приклади застосування МБ
Практично, на сьогоднішній день реалізовано не так вже й багато СППР, які
включали б апарат МБ, однак їх суттєві переваги в умовах невизначеності
привели до застосування МБ при вирішенні найбільш складних задач меди-
цини, фізики, хімії, інтелектуальної обробки даних тощо. Розглянемо деякі
цікаві підходи, використані при створенні відповідних СППР.
Найбільш широко вживані МБ [8] — це, без сумніву, вбудовані у про-
дукти Microsoft, включаючи Answer Wizard of Office 95, Office Assistant of
Office 97 і більш ніж 30 аварійних програм технічної підтримки.
МБ спочатку з’явилися як спроба додати ймовірнісні змінні до експер-
тних систем, і це найбільша галузь їхнього вживання. Відомий приклад —
QMR-DT стосується переформулювання моделі Швидкої Медичної Довідки
(QMR) в теорії прийняття рішень [8].
Інше цікаве застосування МБ — система Vista, розроблена Е. Хорвіт-
цом [8], яка використовувалась у Центрі управління польотами НАСА у
Хьюстоні протягом декількох років. Система послуговується МБ для того,
щоб відображати телеметрію у реальному часі, і забезпечувати довідку
П.І. Бідюк, Н.В. Кузнєцова
ISSN 1681–6048 System Research & Information Technologies, 2007, № 4 34
щодо відносної ймовірності альтернативних відмов космічних систем. Вона
також враховує критичність часу і рекомендує дії найбільш очікуваної кори-
сності, керує представленням інформації з метою динамічного визначення
найбільш важливої інформації. Е. Хорвітц спробував використати подібну
технологію в продуктах Microsoft, зокрема, у проекті Lumiere.
Однак ці приклади застосування МБ — це лише невелика частка того,
що може бути реалізавано і вдало використано. Наприклад, доцільно спро-
бувати застосувати цей потужний інструмент для розв’язання фінансово-
економічних задач. Для цього спочатку розглянемо формалізовану методи-
ку побудови МБ.
Методика побудови і застосування МБ
При побудові МБ з метою вирішення конкретної задачі необхідно:
1. Виконати аналіз проблеми і дати формалізовану постановку задачі.
Сформулювати питання, на яке має бути отримана ймовірнісна відповідь у
результаті формування ймовірнісного висновку за допомогою побудованої
мережі.
2. Визначити множину даних, що відносяться до змінних задачі, отри-
мати їх експертні оцінки та/або статистичні дані.
3. Поставити у відповідність усім отриманим даним взаємовиключні
змінні.
4. Побудувати ациклічний граф, що відображає істотні умови незале-
жності змінних та існування причинно-наслідкових зв’язків.
5. Визначити апріорні ймовірності та оптимізувати топологію мережі
на основі наявної інформації.
6. Виконати навчання мережі і провести формування висновку по від-
ношенню до відповідних станів процесу.
7. Обробити результати: проаналізувати їх і зробити висновки щодо
ймовірності очікуваної події.
Розглянемо приклад реалізації сформульованої методики при вирішен-
ні досить простої задачі аналізу причин повернення товарів.
Іноземна компанія, яка реалізує свою продукцію в Україні, збирає ста-
тистику щодо причин повернення товарів на склад. Розглядаються можливі
варіанти: товар пошкоджений у процесі транспортування чи товар бракова-
ний. Із статистичних даних відомо, що ймовірність повернення товару через
пошкодження при транспортуванні становить 0,05, а ймовірність повернен-
ня через брак — 0,3. Необхідно встано-
вити ймовірність того, що повернений
товар був бракований.
Використовуючи цю інформацію,
будуємо мережу довіри Байєса, де
R (Reject) — повернення товару саме
через брак, D (Damaged) — повернен-
ня через пошкодження товару,
RT (Return) — повернення товару на
склад (рис. 4).
R
∨
D
∨
RT
∨
Рис. 4. Приклад мережі довіри Байє-
са для задачі повернення товарів
Основні етапи побудови і приклади застосування мереж Байєса
Системні дослідження та інформаційні технології, 2007, № 4 35
Ймовірність повернення товару для даної мережі обчислюється за фор-
мулою спільної ймовірності ),|()()()( DRRTPDPRPRTP = . Значення ймо-
вірностей вузлів R і D наведені у табл. 1, а значення умовних ймовірностей
для вузла RT — у табл. 2.
Т а б л и ц я 1 . Значення
ймовірностей вузлів
Т а б л и ц я 2 . Значення умовних
ймовірностей
Prob. TRUE FALSE ),|( DRRTP TRUE=D FALSE=D
)(DP 0,05 0,95 TRUE=R )1,0;9,0( )5,0;5,0(
)(RP 0,3 0,7 FALSE=R )8,0;2,0( )9,0;1,0(
Використовуючи теорему Байєса, можна обчислити ймовірність повер-
нення товару через брак товару.
)TRUE(
)TRUE()TRUE|TRUE()TRUE|TRUE(
=
===
===
RTP
RPRRTPRTRP .
Ймовірність події )TRUE( =RTP можна обчислити, використовуючи
усі можливі значення R і D з таблиць 1 і 2.
+====== )TRUETRUE,|()TRUE()TRUE()TRUE( RDRTPRPDPRTP
+====+ )TRUE,FALSE|()TRUE()FALSE( RDRTPRPDP
+====+ )FALSE,TRUE|()FALSE()TRUE( RDRTPRPDP
=====+ )FALSE,FALSE|()FALSE()FALSE( RDRTPRPDP
2295,01,07,095,02,07,005,05,03,095,09,03,005,0 =××+××+××+××= .
Обчислимо ймовірність того, що товар повернено тому, що він брако-
ваний.
×====== )TRUE,TRUE|TRUE()TRUE|TRUE( DRRTPRRTP
=====+=× )FALSE()FALSE,TRUE|TRUE()TRUE( DPDRRTPDP
52,095,05,005,09,0 =×+×= .
Тепер можемо обчислити ймовірність повернення товару через брак
(рис. 5).
=
=
===
===
)TRUE(
)TRUE()TRUE|TRUE()TRUE|TRUE(
RTP
RPRRTPRTRP
679739,0
2295,0
3,052,0
=
×
= .
Отже, знання про те, що товар було повернуто, спричиняє перегляд усіх
ймовірностей появи цієї події. Зміни відбулися в збільшенні ступеня упев-
неності, що повернення сталося через брак товару: від початкового значення
0,3 до 0,68.
П.І. Бідюк, Н.В. Кузнєцова
ISSN 1681–6048 System Research & Information Technologies, 2007, № 4 36
Розглянемо можливість використання нашої методики для задачі кре-
дитування фізичних осіб, яка останнім часом стає актуальною для України.
Зараз комерційні банки починають усвідомлювати можливості розширення
кредитування фізичних осіб, а для цього необхідно чітко передбачити всю
необхідну інформацію про
клієнтів. Обсяги кредиту-
вання вже почали збіль-
шуватись, але почали збі-
льшуватись і втрати банків
від неповернення кредиту.
За останні два роки прямі
збитки банків від ведення
кредитної діяльності ста-
новили біля 1,1 мільярда
гривень [2].
Нехай іноземний ко-
мерційний банк В працює
в Україні і видає кредити на купівлю побутової техніки, мобільних телефо-
нів і т.п. та збирає статистику щодо повернення кредитів. За рік банком ви-
дано 1600 кредитів. Кожний клієнт описується 18 характеристиками (рис. 6).
Задача формулюється наступним чином: 1) за наявними даними побудувати
мережу, яка покаже зв’язок між характеристиками клієнта і вершиною —
подією повернення кредиту; 2) за наявними навчальними даними визначити
ймовірність повернення кредиту новим клієнтом.
Структуру відповідної МБ у вигляді гістограм наведено на рис. 7. З ме-
режі видно, що освіта впливає на посаду клієнта, стать — на рівень його до-
ходу, бо й досі зберігається тенденція, коли чоловіки працюють на керівних
посадах та отримують більші доходи у порівнянні з жінками. Вік впливає на
стаж роботи, а той — на строк проживання, область реєстрації клієнта — на
область проживання, що вказана в паспорті. Існує також зв’язок між такими
змінними, як вік, кількість дітей, сімейний стан та стать. Строк надання кре-
диту явно впливає на кредит та у подальшому на ймовірність його повер-
нення так само, як і платіж, який необхідно сплачувати кожного місяця.
Судячи із структури побудованої мережі, безпосередній вплив на ймо-
вірність повернення кредиту мають такі характеристики, як вік та сума кре-
диту. Це зрозуміло, бо люди віком до 18 та після 60 років взагалі не можуть
отримати кредит, тому що законодавством не передбачена видача кредиту
неповнолітнім, а банки не зацікавлені у видачі кредитів пенсіонерам. Побу-
дована мережа дає ймовірність повернення кредиту лише на рівні 0,721659,
близькому до граничного, тому діяльність банку з видачі кредитів важко
вважати успішною.
Розглянемо приклад, коли до банку прийшов новий клієнт, який хоче
отримати кредит. Нехай він — молодий чоловік віком 25 років з вищою
освітою, бере кредит розміром 1000 гривень на один рік, тобто щомісяця
сплачує 125 гривень, при цьому його дохід після усіх витрат за місяць ста-
новить 1000 гривень. Клієнт мешкає і зареєстрований у м. Києві 25 років,
має власну квартиру, неодружений та не має дітей, працює на комерційному
підприємстві зі штатом 15 осіб на посаді менеджера менше одного року (це
його перша робота).
D R
Рис. 5. Визначення ймовірності повернення товару
через брак
RT
Основні етапи побудови і приклади застосування мереж Байєса
Системні дослідження та інформаційні технології, 2007, № 4 37
Ри
с
6.
С
тр
ук
ту
ра
м
ер
еж
і,
по
бу
до
ва
но
ї з
а
до
по
м
ог
ою
G
eN
ie
, д
ля
а
на
лі
зу
к
ре
ди
ті
в
П.І. Бідюк, Н.В. Кузнєцова
ISSN 1681–6048 System Research & Information Technologies, 2007, № 4 38
Р
ис
. 7
. С
тр
ук
ту
ра
м
ер
еж
і,
по
бу
до
ва
но
ї з
а
до
по
м
ог
ою
G
eN
Ie
Основні етапи побудови і приклади застосування мереж Байєса
Системні дослідження та інформаційні технології, 2007, № 4 39
Задавши всі ці дані клієнту в мережі, отримаємо, що ймовірність пове-
рнення кредиту цим клієнтом є доволі високою — 0,907407. За існуючими
правилами банку цей клієнт може отримати кредит.
Аналіз мережі в даному випадку показує, що, можливо, доцільно внес-
ти зміни у внутрішню політику банку щодо видачі кредитів, змінити перелік
відомостей, які надає клієнт про себе, започаткувати ведення кредитних іс-
торій.
ВИСНОВКИ
Проведений аналіз показав, що використання МБ стає дедалі частішим при
побудові СППР, які мають працювати в умовах невизначеності. Розширення
сфери застосування МБ сьогодні вимагає створення теоретичних основ та
напрацювання алгоритмів автоматичної побудови МБ для конкретних
випадків, накопичення даних для навчання і зменшення часу на одержання
рішень.
Доцільно застосовувати апарат МБ для вирішення фінансових та еко-
номічних задач, яким притаманні випадковість, неповнота знань, складність
предметної області.
ЛІТЕРАТУРА
1. Бидюк П.И., Терентьев А.Н. Построение и методы обучения байесовских се-
тей// Таврический вестник информатики и математики. — 2004. — № 2. —
С. 139–153.
2. Краснов С.О. Неформальний аналіз кредитоспроможності індивідуальних по-
зичальників комерційних банків // Наук. записки. — 2006. — Вип. 15. —
4 с.
3. Сорокин А.В. Сети Байеса // Сб. «Интеллектуальные технологии и системы». —
М.: Изд-во МГУП, 1999. — Вып. 2. — 304 с.
4. Хабаров С.П. Экспертные системы. Конспект лекций. — 2001. // http://firm.
trade.spb.ru/serp.
5. Aronsky D., Haug P.J. Diagnosing community-acquired pneumonia with a Bayesian
network // Proc. AMIA Symp. — 1998. — Р. 632–636.
6. Dagum P., Luby M. Appximating probabilistic inference in Bayesian belief networks
is NP-hard // Artificial Intelligence. — 1993. — 45. — P. 141–153.
7. Lauritzen S.L., Spiegelhalter D.J. Local computations with probabilities on graphical
structures and their application to expert systems // Journal of the Royal Statistic-
al Society. — Series B. — 1988. — 50, № 2. — P.157–224.
8. Murphy K. A Brief Introduction to Graphical Models and Bayesian Networks. —
1998. — 19 р. // http://www.ai.mit.edu/~murphyk/Bayes/bnintro.html.
9. Pearl J. A constrained propagation approach to probabilistic reasoning //
Kanal L.M., Lemmer J. (Eds.). — Uncertainty in Artificial Intelligence. — Ams-
terdam: North-Holland, 1986. — P. 357–370.
10. Pearl J. Probabilistic Reasoning in intelligent systems: networks of plausible infe-
rence. — San Mateo, CA (USA): Morgan Kauffmann Publishers, Inc., 1988. —
550 p.
Надійшла 22.06.2007
http://www.ncbi.nlm.nih.gov/entrez/query.fcgi?cmd=Retrieve&db=PubMed&list_uids=9929296&dopt=Abstract�
http://www.ncbi.nlm.nih.gov/entrez/query.fcgi?cmd=Retrieve&db=PubMed&list_uids=9929296&dopt=Abstract�
http://www.ai.mit.edu/~murphyk/Bayes/bnintro.html�
Основні етапи побудови і приклади застосування мереж Байєса
П.І. Бідюк, Н.В. Кузнєцова
ВСТУП
Побудова МБ
Визначення апріорних ймовірностей подій і формула Байєса
Логічний висновок у МБ
Навчання структури МБ
Приклади застосування МБ
Методика побудови і застосування МБ
ВИСНОВКИ
E
E
B
C
A
B
C
A
B
C
B
C
C
|