Національний технічний університет України КПІ ННК Інститут прикладного системного аналізу Розробка модифікованого LS-метода для побудови ймовірнісного висновку в мережах Байєса Науковий керівник: к.т.н., м.н.с. асистент каф. ММСА Терентьєв О.М. Київ Виконавець: студентка групи КА-46 Акулініна О.А.

2 Постановка задачі дослідження Аналіз існуючих методів побудови ймовірнісного висновку в мережах Байєса. Розробка модифікації LS-методу побудови ймовірнісного висновку в мережі Байєса. Поетапний опис запропонованого алгоритму та покрокова його реалізація на прикладі. Моделювання різних ситуацій в запропонованій мережі та порівняння отриманих результатів з іншими програмними продуктами на базі мереж Байєса. Порівняння запропонованого модифікованого LS-методу та інших алгоритмів кластеризації.

3 Виникнення назви Мережа Байєса Термін мережа Байєса був запропонований у 1985 році Джуді Перлом (Judea Pearl). Назва мережі Байєса повязана з використанням правила Байєса у задачі побудови ймовірнісного висновку в мережі. Теорія ймовірностіТеорія графів Мережі Байєса

4 Поняття мережі Байєса Мережа Байєса представляє собою пару, де - це направлений ациклічний граф, а - множина таблиць умовних ймовірностей вершин. Сукупний ймовірнісний розподіл в МБ обчислюється за формулою:

5 Типи структур мереж Байєса Дерево – це структура, де кожна вершина може мати не більше одного батька Однозвязна мережа (полідерево) – це структура, де кожна вершина може мати більше одного батька, але існує тільки один шлях між будь- якими двома вершинами Багатозвязна мережа – це структура, де між будь-якими двома вершинами може існувати декілька шляхів

6 Типи мереж Байєса Дискретні Неперервні Гібридні – Динамічні -

7 Застосування мереж Байєса Медичне Економічне Фінансове Космічне Військове Управління ризиками тероризму …

8 Задачі в мережах Байєса Задачі Побудова ймовірнісного висновку Побудова топології мережі Апроксимаційні алгоритми Точні алгоритми ВаріаційніПошукові Неповного висновку Стохастичної вибірки Перла Визначеного перетину Виключення змінних Кластеризації Інші Lauritzen-Spiegelhalter Shenoy-ShaferHugin

9 Ймовірнісний висновок Метою ймовірнісного висновку є знаходження - апостеріорної ймовірності шуканих вершин, при деякому значенні спостережуваних вершин Задача побудови ймовірнісного висновку є складною з обчислювальної точки зору та неоднозначною

10 LS-метод : перший етап – побудова обєднаного дерева Запропонували Lauritzen та Spiegelhalter у 1988 р. Етапи методу: I. Побудова обєднаного дерева : Моралізація графу Приведення графу до ненаправленого Триангуляція графу Побудова дерева клік Побудова обєднаного дерева Заповнення обєднаного дерева таблицями

11 II. Алгоритм пропагації: Введення спостережень в таблиці Сходження догори Сходження донизу Розрахунок ймовірностей станів вершин Суть модифікації LS-методу полягає в новому принципі заповнюванні таблиць умовних ймовірностей, що описують кліки обєднаного дерева LS-метод : другий етап – алгоритм пропагації

12 Модифікація LS-методу Заповнення починається з листів дерева і послідовно перебираються усі кліки. Розглядаються "невідмічені" вершини в необробленій кліці: Якщо серед "невідмічених" вершин є така, яка не зустрічається в інших необроблених кліках, то таблиця повинна мати вигляд - у такому разі ця вершина "відмічена" і кліка вважається обробленою. Якщо в первинній МБ такої таблиці немає або така вершина не одна, то використовується таблиця сукупного розподілу ймовірності - у такому разі усі вершини кліки "відмічені" і кліка оброблена.

13 Якщо в кліці є вже "відмічені" вершини і всього одна "невідмічена" вершина, то використовується таблиця виду з первинної МБ - у такому разі ця вершина "відмічена" і кліка вважається обробленою. Якщо в кліці є вже "відмічені" вершини, а "невідмічених" вершин декілька, то використовується таблиця сукупного розподілу ймовірності "невідмічених" вершин і тоді ці вершини "відмічені", а кліка вважається обробленою. Якщо в необробленій кліці усі вершини вже "відмічені", то кліка заповнюється таблицею виду і вважається обробленою. Модифікація LS-методу

14 Приклад використання модифікованого LS-методу для визначення кредитоспроможності фізичних осіб Вхідні дані: База даних клієнтів банку з 3347 записів Топологія мережі побудована за допомогою евристичного методу побудови мереж Байєса за навчальними даними Вершини мережі: T – Type of Contract A – Age G – Gender M – Marital Status C – Total Credit Mount P – Contact Person R – Result (creditworthiness)

15 Структура мережі T C A G M P R

16 Таблиці умовних ймовірностей мережі СтанЙмовірність T1 = Employ full time0,875 T2 = Pensioner0,061 T3 = Self Employer0,064 СтанЙмовірність A1=More then 360,45 A2=Low then 360,55 Значення умовної ймовірності вершини TЗначення умовної ймовірності вершини A БатькиСтани батьків TT1 T2 T3 AA1A2A1A2A1A2 СтанЙмовірність C1= Low then 2100 UAH0,550,60,630,80,40,46 C2= More then 2100 UAH0,450,40,370,20,60,54 Значення умовної ймовірності вершини C

17 Таблиці умовних ймовірностей мережі БатькиСтани батьків AA1A2A1A2 GFFMM СтанЙмовірність M1=Civil marriage0,03610,08410,03210,0903 M2=Divorce0,19960,07710,06810,0819 M3=Married0,58480,54550,85170,1218 M4=Single0,07920,28530,03410,706 M5=Widowed0,10030,0080,0140 СтанЙмовірність F=Female0,47 M=Male0,53 Значення умовної ймовірності вершини M Значення умовної ймовірності вершини GЗначення умовної ймовірності вершини P СтанЙмовірність No0,44 Yes0,56

18 Таблиці умовних ймовірностей мережі БатькиСтани батьків GFFFFMMMM PNo Yes No Yes CC1C2C1C2C1C2C1C2 СтанЙмовірність R1=Good0,960,910,99 0,860,760,9850,9659 R2=Bad0,040,090,01 0,140,240,0150,0341 Значення умовної ймовірності вершини R

19 I етап LS-методу – побудова обєднаного дерева Моралізація Триангуляція Приведення до ненаправленості T C A G M P R T C A G M P R T C A G M P R C A G P R C G P R

20 I етап LS-методу – побудова обєднаного дерева Дерево клік з сепараторами Обєднане дерево T,A,CT,A,C A,M,G A,C,G C,G,P,R A A,C C,G G A,G T,A,CT,A,C A,M,G A,C,G C,G,P,R A, C C,G A,G

21 I етап LS-методу – заповнення обєднаного дерева таблицями Кліка-лист 1 - "T,A,C" Кліка-лист 2 - "A,M,G" C=C1C=C2TA 0, ,177188T1A1 0,288750,1925T1A2 0, ,010157T2A1 0,026840,00671T2A2 0,011520,01728T3A1 0, ,019008T3A2 "відмічені" вершини: T, A, C M=M1M=M2M=M3M=M4M=M5AG 0,03610,19960,58480,07920,1003A1F 0,03210,06810,85170,03410,014A1M 0,08410,07710,54550,28530,008A2F 0,09030,08190,12180,7060A2M "відмічені" вершини: M

22 I етап LS-методу – заповнення обєднаного дерева таблицями Кліка 3 – "A,C,G" Корінь дерева – "R,C,P,G" C=C1C=C2AG 0,47 A1F 0,53 A1M 0,47 A2F 0,53 A2M "відмічені" вершини: G R=R1R=R2CPG 0, , C1NoF 0, , C1NoM 0, , C1YesF 0, , C1YesM 0, , C2NoF 0, , C2NoM 0,110220, C2YesF 0, , C2YesM "відмічені" вершини: P,R

23 II етап LS-методу – алгоритм пропагації заповнимо нулями входження P=Yes в корені заповнимо нулями входження G=F в кліці 3 - "A,C,G" Введення спостережень P=No (поручителя немає), G=M (стать - чоловіча) в таблиці R=R1R=R2CPG 0, , C1NoF 0, , C1NoM 00C1YesF 00C1YesM 0, , C2NoF 0, , C2NoM 00C2YesF 00C2YesM C=C1C=C2AG 00A1F 0,53 A1M 00A2F 0,53 A2M

24 II етап LS-методу – алгоритм пропагації Сходження догори C=C1C=C2A 0, ,204624A1 0, ,218218A2 Повідомлення кліки 1 кліці 3 Нова таблиця кліки 1 C=C1C=C2TA 0, ,865917T1A1 0,87030,882145T1A2 0, ,049635T2A1 0, ,030749T2A2 0, ,084448T3A1 0, ,087106T3A2 Повідомлення кліки 2 кліці 3 AG 1A1F 1 M 1A2F 1 M M=M1M=M2M=M3M=M4M=M5AG 0,03610,19960,58480,07920,1003A1F 0,03210,06810,85170,03410,014A1M 0,08410,07710,54550,28530,008A2F 0,09030,08190,12180,7060A2M Нова таблиця кліки 2

25 C=C1C=C2AG 00A1F 0, , A1M 00A2F 0, , A2M C=C1C=C2G 00F 0, , M C=C1C=C2AG 00A1F 0, , A1M 00A2F 0, , A2M Нова таблиця кліки 3 Повідомлення кліки 3 кореню Нова таблиця кліки 3 R=R1R=R2CPG 00C1NoF 0, , C1NoM 00C1YesF 00C1YesM 00C2NoF 0, , C2NoM 00C2YesF 00C2YesM Нова таблиця кореня II етап LS-методу – алгоритм пропагації

26 II етап LS-методу – алгоритм пропагації Сходження донизу C=C1C=C2G 0, , F 0, , M Повідомлення кореня кліці 3 Нова таблиця кліки 3 C=C1C=C2AG 00A1F 0, ,047736A1M 00A2F 0, ,050907A2M Повідомлення кліки 3 кліці 2 AG 0A1F 0,104942A1M 0A2F 0,128258A2M Нова таблиця кліки 2 M=M1M=M2M=M3M=M4M=M5AG 00000A1F 0, , , ,003580,00147A1M 00000A2F 0, , , ,090550A2M

27 C=C1C=C2A 0, , A1 0, , A2 Повідомлення кліки 3 кліці 1 Нова таблиця кліки 1 C=C1C=C2TA 0, , T1A1 0, , T1A2 0, , T2A1 0, , T2A2 0, , T3A1 0, , T3A2 II етап LS-методу – алгоритм пропагації

28 II етап LS-методу – алгоритм пропагації Нормалізовані таблиці C=C1C=C2TA 0, ,112678T1A1 0, ,130548T1A2 0, ,006459T2A1 0,037750,004551T2A2 0, ,010989T3A1 0, ,012891T3A2 Кліка-лист 1 - "T,A,C" Кліка-лист 2 - "A,M,G" M=M1M=M2M=M3M=M4M=M5AG 00000A1F 0, , , , ,00624A1M 00000A2F 0, , , , A2M

29 II етап LS-методу – алгоритм пропагації C=C1C=C2AG 00A1F 0, ,169093A1M 00A2F 0, ,180327A2M Кліка 3 - "A,C,G" Корінь дерева - " R,C,P,G" R=R1R=R2CPG 00C1NoF 0, ,091081C1NoM 00C1YesF 00C1YesM 00C2NoF 0,265560,083861C2NoM 00C2YesF 00C2YesM

30 Розрахунок ймовірностей станів вершин Для вершини T підсумовуються її значення в кліці 1 Для вершини A підсумовуються її значення в кліці 3: Для вершини C підсумовуються її значення в кліці 3: II етап LS-методу – алгоритм пропагації

31 Для вершини M підсумовуються її значення в кліці 2: Для вершини R підсумовуються її значення в корені: II етап LS-методу – алгоритм пропагації

32 Порівняння результатів роботи запропонованої модифікації LS-методу з іншими програмними продуктами ПрограмаМетод ймовірнісного висновку BayesNetМетод ймовірнісного висновку в байєсовских мережах за навчальними даними NeticaМетод виключення обєднаних дерев Hugin - ExpertМетод Hugin MSBNxМетод заснований на поширенні повідомлень по дереву клік GeNIeМетод кластеризації

33 Порівняння результатів роботи запропонованої модифікації LS-методу з іншими програмними продуктами LS-методBayesNetNeticaMSBNxGeNIeHugin ВершинаСтанЙмовірність TT10,87490,875 T20,06090,061 T30,064 AA10,450,450,45 A20,54990,55 MM10,0641 0,064110,0641 M20,0757 0,075690,0757 M30,4503 0,450,45030, ,4503 M40,4036 0,4040,40360, ,4036 M50,0063 CC10,5770,57720,5770,57720, ,5793 C20,4230,42280,4230,42280, ,4207 RR10,8250,81770,8180,81770, ,8179 R20,1750,18230,1820,18230, ,1821 P=No (поручителя немає) і G=M (стать – чоловіча)

34 Порівняння результатів роботи запропонованої модифікації LS-методу з іншими програмними продуктами LS-методBayesNetNeticaMSBNxGeNIeHugin ВершинаСтанЙмовірність TT10,875 T20,061 T30,064 AA10,450,450,45 A20,550,550,55 GF0,470,470,47 M0,530,530,53 MM10,0634 0, ,0634 M20,1023 0,1020,10230, ,1023 M30,5033 0,5030,50330, ,5033 M40,3044 0,3040,30440, ,3044 M50,0266 0, ,0266 CC10,5770,57720,5770,57720, ,5793 C20,4230,42280,4230,42280, ,4207 PNo0,44 Yes0,56 RR10,93650,93540,9350,93540, ,9355 R20,06350,06460,0650,06460, ,0645

35 Порівняння результатів роботи запропонованої модифікації LS-методу з іншими програмними продуктами LS-методBayesNetNeticaMSBNxGeNIeHugin ВершинаСтанЙмовірність TT10,8748 0,8750,87480, ,8747 T20,0556 0, ,0556 T30,0696 0, ,0697 AA10,4587 0,4590,45870, ,458 A20,5413 0,5410,54130, ,542 GF0,2363 0,2360,23630, ,2363 M0,7637 0,7640,76370, ,7637 MM10,0632 0, ,0633 M20,0892 0, ,0892 M30,4817 0,4820,48170, ,4813 M40,3489 0,3490,34900, ,3494 M50,0168 0, ,0168 CC10,42850,42870,4290,42870, ,4309 C20,57150,57130,5710,57130, ,5691 PNo0,85410,85330,8530,85330, ,8533 Yes0,14590,14670,1470,14670, ,1467 R=R2 (клієнт некредитоспроможний)

36 Порівняння результатів роботи запропонованої модифікації LS-методу з іншими програмними продуктами LS-методBayesNetNeticaMSBNxGeNIeHugin ВершинаСтанЙмовірність GF0,84930,864 0,86400, ,864 M0,15070,136 0,13600, ,136 CC10,47620,4 C20,52370,6 PNo0,44 Yes0,56 RR10,95560,95460,9550,95460, ,9546 R20,04440,0454 0, ,0454 T=T3 (клієнт приватний підприємець), A=A1 (вік – більше 36 років), M=M5 (вдівець)

37 Порівняння результатів роботи запропонованої модифікації LS-методу з іншими програмними продуктами LS-методBayesNetNeticaMSBNxGeNIeHugin ВершинаСтанЙмовірність GF0,24110,26380,2640,26380,2640,2638 M0,75890,73620,7360,73620,7360,7362 PNo0,44 Yes0,56 RR10,89450,89630,8960,89630,8960,8963 R20,10550,10370,1040,10370,1040,1037 T=T3 (клієнт приватний підприємець), A=A2 (вік – менше 36 років), M=M4 (неодружений), C=C2 (сума кредиту - більше 2100 грн)

38 Порівняння алгоритмів кластеризації побудови ймовірнісного висновку Графічні структури для розповсюдження повідомлення LS - обєднані дерева Hugin – обєднані дерева з сепараторами SS – двійкові звязні дерева Обчислення ймовірностей окремих змінних LS – в кліках Hugin – в кліках та сепараторах SS – в вершинах

39 Обчислювальна ефективність Hugin виконує менше операцій ділень і додавань ніж LS SS не використовує операцій ділення Ефективність використання обєму памяті LS потребує меншого обєму памяті ніж Hugin в SS двійкове звязне дерево має більше вершин, ніж відповідне обєднане дерево, але не кожна вершина в ньому потребує виділення памяті Порівняння алгоритмів кластеризації побудови ймовірнісного висновку

40 Порівняння алгоритмів кластеризації побудови ймовірнісного висновку на прикладі - максимальна кількість станів вершини - максимальне число вершин в кліці мінус 1 - кількість клік - кількість сусідів- ї кліки МетодСкладністьПамять (fpn) Кількість операцій Час (мс) LS Hugin SS

41 Висновки Виконано аналіз існуючих методів побудови ймовірнісного висновку в мережах Байєса. Розроблена модифікація LS-методу побудови ймовірнісного висновку в мережі Байєса. Запропонований поетапний опис модифікованого алгоритму та покрокова його реалізація на прикладі. Виконане моделювання різних ситуацій в запропонованій мережі та порівняння отриманих результатів з іншими програмними продуктами на базі мереж Байєса. Виконане порівняння запропонованого модифікованого LS-методу та інших алгоритмів кластеризації.

42 Рекомендації щодо подальших досліджень Розробка оригінальної архітектури та реалізація компютерної системи підтримки прийняття рішень для інтелектуального аналізу даних на основі мереж Байєса з використанням запропонованого методу для задачі побудови ймовірнісного висновку. Розширення запропонованого модифікованого LS- методу для використання в неперервних та гібридних мережах Байєса. Розробка нових методів побудови ймовірнісного висновку з меншою обчислювальною складністю на основі теорій Демпстера-Шефера і стохастичного моделювання методом Монте-Карло.

43 Акт впровадження Результати дисертаційної роботи були впроваджені на підприємстві Номінал Інжинірінг (Crane Cash Code)

44 Публікації : статті Подана для опублікування стаття в журнал Wireless Sensor Network M. Z. Zgurovskii, O.M. Terentyev, O.A. Akulinina, N.S. Guz. Methods of constructing probability inference in Bayesian networks using LS approach. Дата опублікування осінь-зима 2010 року. Подана до опублікування стаття в журнал "Вісник Університету «Україна»" Бідюк П.І., Акулініна О.А., Гуз Н.С., Свердел К.О. Побудова ймовірнісного висновку в мережах Байєса на основі LS-методу. Дата опублікування літо 2010 року.

45 Участь у ХІ Міжнародній науково-технічній конференції Системний аналіз та інформаційні технології рік Участь у ХІI Міжнародній науково-технічній конференції Системний аналіз та інформаційні технології рік Участь у Х Міжнародній науковій конференції Інтелектуальні системи прийняття рішень і проблеми обчислювального інтелекту – 2010 рік Публікації : конференції

Дякую за увагу!