Accelerating algorithms for Bayesian network recovery. Adaptation to structures without cycles
We demonstrate a technique to improve algorithms for reconstruction of dependency structures from data. Modification proposed, not affecting performance in general case, facilitates recovering a dependency forest or poly-forest by means of first-rank tests only, thus reducing computational complexit...
Gespeichert in:
| Datum: | 2025 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
PROBLEMS IN PROGRAMMING
2025
|
| Schlagworte: | |
| Online Zugang: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/798 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Institution
Problems in programming| id |
pp_isofts_kiev_ua-article-798 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/7a/f6e2ff3f7dee1ba2dac98328bb230e7a.pdf |
| spelling |
pp_isofts_kiev_ua-article-7982025-09-02T15:47:58Z Accelerating algorithms for Bayesian network recovery. Adaptation to structures without cycles Прискорення алгоритмів відтворення байєсових мереж. Адаптація до структур без циклів Balabanov, O.S. UDC 681.3.00:007 УДК 681.3.00:007 We demonstrate a technique to improve algorithms for reconstruction of dependency structures from data. Modification proposed, not affecting performance in general case, facilitates recovering a dependency forest or poly-forest by means of first-rank tests only, thus reducing computational complexity. Prombles in programming 2011; 1: 63-69 Показано можливості вдосконалення алгоритмів відтворення структури моделі залежностей з даних. Пропонована модернізація, не погіршуючи роботу алгоритму в загальному випадку, дозволяє відтворювати структури залежностей типу ліс (дерево) чи полі-ліс на основі тестів першого рангу, що значно зменшує обчислювальну складність.Prombles in programming 2011; 1: 63-69 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2025-08-28 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/798 PROBLEMS IN PROGRAMMING; No 1 (2011); 63-69 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 1 (2011); 63-69 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 1 (2011); 63-69 1727-4907 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/798/850 Copyright (c) 2025 PROBLEMS IN PROGRAMMING |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2025-09-02T15:47:58Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
UDC 681.3.00:007 |
| spellingShingle |
UDC 681.3.00:007 Balabanov, O.S. Accelerating algorithms for Bayesian network recovery. Adaptation to structures without cycles |
| topic_facet |
UDC 681.3.00:007 УДК 681.3.00:007 |
| format |
Article |
| author |
Balabanov, O.S. |
| author_facet |
Balabanov, O.S. |
| author_sort |
Balabanov, O.S. |
| title |
Accelerating algorithms for Bayesian network recovery. Adaptation to structures without cycles |
| title_short |
Accelerating algorithms for Bayesian network recovery. Adaptation to structures without cycles |
| title_full |
Accelerating algorithms for Bayesian network recovery. Adaptation to structures without cycles |
| title_fullStr |
Accelerating algorithms for Bayesian network recovery. Adaptation to structures without cycles |
| title_full_unstemmed |
Accelerating algorithms for Bayesian network recovery. Adaptation to structures without cycles |
| title_sort |
accelerating algorithms for bayesian network recovery. adaptation to structures without cycles |
| title_alt |
Прискорення алгоритмів відтворення байєсових мереж. Адаптація до структур без циклів |
| description |
We demonstrate a technique to improve algorithms for reconstruction of dependency structures from data. Modification proposed, not affecting performance in general case, facilitates recovering a dependency forest or poly-forest by means of first-rank tests only, thus reducing computational complexity. Prombles in programming 2011; 1: 63-69 |
| publisher |
PROBLEMS IN PROGRAMMING |
| publishDate |
2025 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/798 |
| work_keys_str_mv |
AT balabanovos acceleratingalgorithmsforbayesiannetworkrecoveryadaptationtostructureswithoutcycles AT balabanovos priskorennâalgoritmívvídtvorennâbajêsovihmerežadaptacíâdostrukturbezciklív |
| first_indexed |
2025-09-17T09:23:10Z |
| last_indexed |
2025-09-17T09:23:10Z |
| _version_ |
1850413014245703681 |
| fulltext |
Експертні та інтелектуальні інформаційні системи
УДК 681.3.00:007
О.С. Балабанов
ПРИСКОРЕННЯ АЛГОРИТМІВ ВІДТВОРЕННЯ БАЙЄСОВИХ
МЕРЕЖ. АДАПТАЦІЯ ДО СТРУКТУР БЕЗ ЦИКЛІВ
Показано можливості вдосконалення алгоритмів відтворення структури моделі залежностей з даних.
Пропонована модернізація, не погіршуючи роботу алгоритму в загальному випадку, дозволяє
відтворювати структури залежностей типу ліс (дерево) чи полі-ліс на основі тестів першого рангу, що
значно зменшує обчислювальну складність.
Вступ
Байєсова мережа – це модель, що
описує систему ймовірнісних залежностей
в наочній структурованій формі. Такі
моделі звуть також каузальними
мережами, системами структуральних
рівнянь, моделями незалежності на
орієнтованих графах і т. д. [1–5]. Байєсові
мережі – зручний апарат для моделювання
неповністю спостережуваних систем і
розв'язання аналітичних задач за схемою:
«відоме значення певних змінних – знайти
значення інших змінних моделі». Байєсова
мережа може бути або сконструйована
експертом, або виведена автоматично
(зокрема, на основі фактів умовної
незалежності). Виведення можливе у
формі синтезу (коли незалежності задані
як знання) або у формі емпіричної індукції
(на основі даних спостережень за об'єктом
моделювання). Через те, що алгоритми
емпіричної індукції зазвичай розраховані
на випадок відсутності апріорних знань
про модель (і часто невідомим є навіть
темпоральний порядок змінних моделі), ці
алгоритми мають перебірний характер і є
дуже складними обчислювально [2–4].
Натомість для спеціальних простих під-
класів структур моделей розроблено низку
простих алгоритмів виведення. Проте
зрозуміло, що спеціалізовані алгоритми
нездатні відтворити адекватну модель в
загальному випадку. Водночас, аналітик не
може передбачити, чи належить адекватна
модель до спеціального підкласу структур.
У роботі показано, як можна надати уні-
версальному алгоритму адаптивних вла-
стивостей. Пропонується модифікувати
алгоритм так, що, зберігаючи здатність
працювати зі складними моделями,
алгоритм забезпечує простоту виведення у
випадку, коли структура генеративної
моделі є однозв'язною.
Відправні положення
Важливо розрізняти дві постановки
задачі індуктивного виведення моделі:
• відтворювальна (реконструкційна);
• редукційна (апроксимаційна).
Коли генеративна модель вкладається в
інструментальний клас методу виведення,
це – відтворення моделі (реконструкція);
коли ні – редукція (структурна апрок-
симація). Алгоритм редукції видає
«покриття» істинної моделі сурогатною.
Результати даної роботи спрямовані на
реконструкцію моделі.
Нагадаємо елементарні поняття.
Шлях у графі – це послідовність сусідніх
ребер ZYX −⋅⋅⋅−− будь-якої орієн-
тації, де всі проміжні вершини – різні.
Оршлях (строго орієнтований шлях) – це
шлях, на якому всі ребра орієнтовані
узгоджено, тобто в одному напрямку.
Орієнтований цикл (орцикл, «циклон») –
це оршлях, на якому початкова вершина
тотожна останній. Якщо в орграфі є дуга
, то вершина YX → X зветься «бать-
ком» вершини Y , а вершина Y – дитиною
X . Коли орієнтація дуги
невідома чи необов'язкова, позначаємо її
як ребро
YX →
X —Y . (Кажемо, що X Y та
суміжні.) Між вершинами графа та
змінними моделі встановлена взаємно-
однозначна відповідність.
Ациклічний орієнтований граф
(АОГ) – це орграф без «циклонів». АОГ-
модель залежностей – це пара ( G , ϑ ), де
– АОГ, а G – сукупність локально ϑ
63
© О.С. Балабанов, 2011
ISSN 1727-4907. Проблеми програмування. 2011. № 1
Експертні та інтелектуальні інформаційні системи
64
заданих параметрів. У байєсових мережах
змінні дискретні (номінальні), а параметри
– це локально визначені умовні розподіли
ймовірностей. АОГ-моделі з неперервними
змінними, лінійними залежностями та
нормальними дистурбаціями звуться
гауссовими мережами. Результати роботи
дійсні також для гауссових мереж (як і для
всіх форм параметризації моделі).
Визначення 1. Колізором (колай-
дером) в орграфі зветься фрагмент із двох
дуг вигляду . Ланцюг
(безколізорний шлях) в орграфі – це шлях,
який не містить жодного колізора.
ZYX ←→
Підкласи АОГ-моделей визначають
«топологічними» обмеженнями на
структуру графа моделі. Найбільш відомі
монопотокові моделі, полі-ліси й ліси. Ці
підкласи легко визначаються і
вкладаються один в інший [6, 7].
Монопотоковий граф – це орграф, у якому
кожен цикл суміжності має два чи більше
колізорів [6]. Полі-ліс – це орграф, у якому
немає циклів. Ліс – це орграф, у якому
немає ані циклів, ані колізорів. У лісі
кожна вершина має не більше одного
батька. (Зазначимо, що в літературі часто
вживаються терміни «дерево» та «полі-
дерево». Але поняття ліс є більш повним,
бо охоплює випадок, коли граф
розпадається на окремі компоненти.)
Названа ієрархія моделей – не лише
формальна. Ці підкласи різняться
експресивними можливостями, статистич-
ними властивостями і принципами
індуктивного виведення.
Визначення 2 (d-сепарація). Шлях
π в АОГ-моделі називають d-закритим за
допомогою (кондиціонування) множини
вершин , якщо і тільки якщо S
1) існує вершина X , , S∈X π∈X , і
на шляху π є дуга чи ,
або
→X X←
2) на шляху π лежить хоча б один
колізор , причому ←→ Y S∉Y й
немає жодного оршляху вигляду
, де ZY →⋅⋅⋅→ S∈Z .
Якщо при кондиціонуванні
множини існує хоча б один d-відкритий
шлях між
S
X та Y , то говорять, що
вершини є d-залежні (d-з'єднані).
У противному разі (коли немає жодного
відкритого шляху) вершини X Y та є d-
незалежні, а множина d-сепарує
вершини
S
X Y та . Будемо позначати таку
d-сепарацію предикатом , а
множину називатимемо (графовим)
сепаратором для пари ; неявно
розуміється
( )YX ;;Ds S
S
),( YX
S∉YX , . Коли множина є
пустою, факт d-сепарації записується
коротше:
S
( )YX ;;Ds .
У застосуванні до структур, які не
мають колізорів, пункт 2 критерію d-
сепарації можна відкинути і дати
спрощений критерій (forest d-separation):
шлях є d-закритим за допомогою множини
вершин , якщо і тільки якщо на цьому
шляху лежить принаймні одна вершина,
що входить до .
S
S
Факти d-сепарації зчеплені зі
структурою АОГ-моделі за принципом:
( )YX ;;Ds Z¬:Z∀⇔X —Y ) ( .
Умовну незалежність від X Y при
кондиціонуванні (фіксації) набору змінних
будемо виражати предикатом Z
( )YX ;;Pr Z Z∉, де Y, за ність
означає, що (),Z Yp= бо,
)|()|()| ZZ Ypp= .
Z веться
емпіричним сепара ром для пари ),( YX .
Для систем лінійних залежностей умовну
незалежність виражають через частний
коефіцієнт к реляції 0. =ZXY
X . Така не леж
|( ZXYp а
еквівалентно, Z XXYp
При цьому множина змінних з
то
о
)|
(
ρ .
Згідно відомої теореми від
Verma&Pearl (д ій ив. [2, 4]), критер d-
сепарації визначає марківські властивості
АОГ-моделі:
( )Y
X та Y
X ;Ds Z; . (1)
сі такі структурно-детерміно і фа
ня АОГ-моделей з
даних
щ
ія
( )YX ;;Pr Z⇒
У ван кти
умовної незалежності є дійсні за будь-якої
параметризації моделі.
Методи відтворен
базуються на припущенні каузальної
необманливості (faithfulness) розподілу
ймовірностей щодо генеративної АОГ-
моделі [2, 4, 8]. Це припу ення
виражається як імплікац , обернена
відносно (1). Але в скінченній відбірці
даних це припущення виконується тільки у
локальному сенсі, і то не завжди. Втім, для
Експертні та інтелектуальні інформаційні системи
практики можна послабити припущення
необманливості. Відомі методи constraint-
based (або «сепараційного») підходу до
виводу структури моделі, зокрема,
алгоритм PC [2, 3], спираються на таке
правило ідентифікації ребра:
( )YXYX ;;Pr:),(: ZZZ ¬∉∀( X Y )— ⇔ .
Кардинальність умови визначає ранг
тесту умовної незалежності Із
зростанням рангу збільшується перебірна
оли модель
в во ьс з бази знань про незалежності
відбірки
итму має
лі
і м их
ів.
і
т
Зауважимо, що для відтворення
АОГ-моделей відомі алгоритми з
поліноміальною кількістю тестів. Але для
повної характеристики обчислювальної
складності необхідно врахувати, що ті
алгоритми використовують тести
складного формату.
Між тим відомо, що ліси та полі-
ліси відтворюються з даних алгоритмами
квадратичної або суб-кубічної складності
[9, 10]. Але ці алгоритми спеціалізовані й
ви
яються в режимі
редукц
залежностей без
циклів
в лі
Л
Z
( )YX ;;Pr Z .
складність виведення і відбувається
«подрібнення» відбірки даних. Необхідно
уникати складних сепараторів та
екстенсивного їх пошуку.
Алгоритми сепараційного підходу
можуть бути застосовані в двох царинах
(або режимах):
• у режимі синтезу, к
и дит я ;
• у режимі виведення з даних.
Основна частина алгор два
етапи. На першому етапі ідентифікують всі
ребра моде , на другому – визначають
орієнтації (спрямування) ребер. При
виведенн оделі з дан додається третій
етап – обчислення параметр
Псевдокод основної частини
алгоритму PC (за [2]) записано на рис. 1.
Можна бачити, що алгоритм шукає
можливий сепаратор для пари,
перебираючи всі підмножини сум жних
верши н, причому цей перебір він виконує
також коли є ребро. Це призводить до
виконання тестів високого рангу
(більшіс ь з яких – непродуктивні).
при застосуванні до загального падку
АОГ-моделей опин
ії. Для монопотокових моделей теж
існують спеціалізовані алгоритми суб-
кубічної складності [7].
У наступному розділі показано, як
можна за допомогою простих засобів
надати алгоритмам, розрахованим на
відтворення АОГ-моделей, адаптивних
властивостей, які забезпечать економічне
відтворення структур
. Пропонуються такі вдосконалення,
що алгоритм, залишаючись універсальним,
зможе ідтворювати ліси та полі- си
залежностей на основі тестів першого
рангу, подібно спеціалізованим
алгоритмам.
S1 Form the complete undirect
S2 k = 0
ed gr
les X
J(U;X ;Y)\{X} has at
throu s of ADJ(U;X)\{Y}
U;Y)\{X} that
S is found con
ve the edge en nd
unt h ir of a ja iables X and Y,
an k elements
ules
aph U on the set of variables V
and Y that are adjacent in (the
)\{Y} or ADJ(U
gh the subset
Repeat
For each pair of variab
current) U such that AD
least k elements, check
and the subsets of ADJ(
variables. If a subset
Y are independent, remo
record S as Sepset(X;Y)
k = k + 1
have exactly k
ditional on which X and
X betwe and Y in U, a
il for eac ordered pa
ADJ(U;X)\{Y} has less th
d cent var
S3 Execute the orientation r
Рис. 1. Опис ал горитму РС
Основний результат
іси залежностей можна
характеризувати такою аксіомою:
( X —Y )& ( )ZY ;;Ds¬ ⇒ ( )ZX ;;Ds¬ &
&[ ( )ZYX ;;Ds або ( )ZXY ;;Ds ]. (2)
65
Експертні та інтелектуальні інформаційні системи
66
о с им
з [6
ліси залежностей можна
описат ту як
( )YXZ(Нагадаємо, щ епарація – с етрична).
Зазначимо, що аксіома (2) покриває
заборону циклонів, а аксіома
монопотокових моделей ] – ні.
Інакше,
; &;Ds ( )YZ ;;Ds¬ , то вершина Z не
є членом ніякого локально-мінімального
сепаратора для пари вершин ),( YX .
Для дерев залежностей правило
відсторонення сприймається як мало не
очевидне, довести його . А
емпірична форма правила відсторонення
випадку лісів є коректна навіть без
ущ
и нас пною аксіомою: що є дуга
YX → , то не існує такої Z ( XZ ≠ ), що є
і простіше
у
ду YZ ціє реба
дати и онів.
га → . Але до т
до заборону ц кл Крім того,
с й варіант характеризації нез
о явно не жає марко ь
власти
я
ифі я
н а
ї аксіоми
прип ень необманливості.
З правила «відсторонення» та
твердж
о танні ручний
тим, щ вира вс ких ення 1 з [11] (про «стрижень»
сепаратора) випливає наступне правило:
Твердження 2 (правило єдиної
перемички; ‘single spanning link’):
(
востей. Відсутність колізорів
означає, що в кожній зв' заній компоненті
моделі є один-єдиний корінь. (Але корінь
не ідент куєтьс відношеннями
незалежності.)
Для характеризації полі-лісів
залежностей еобхідна складніша ксіома:
( X —Y )& ( )1;;Ds ZY¬ & ( )21 ;;Ds ZZ¬ &…
…& ( )kk ZZ ;;Ds 1−¬ ⇒ або ( )kZX ;;Ds ,
або ( )kZYX ;;Ds , або ( )kZXY ;;Ds .
)Y & :},{\ YXUZ ∈∀ [ ( )X ;;Ds¬ ∨XZ ;;Ds
( )YZ ;;Ds∨ ( )YXZ ;;∨ ( )XYZ ;;Ds∨ ] ⇒
⇒
Ds
X —Y .
Тут U – множина всіх вершин моделі;
символ “∨ ” означає диз'юнкцію.
Розгорнувши аксіому (2) за допо-
могою критерію d-сепарації, легко бачити,
що к о дерева ідентифікується
правилом єдин ки. Дійсно, нехай
є ребро
(3)
ф н
еберної
залежн
ще ін й
іст
виміру за оже виявити
абкою або навіть колапсувати в
скре
ї
він
л і
л
(‘placing
aside’)). Якщо в АОГ-моделі вірне
Не ормаль ий коментарій до
аксіом. Залежність у деревах завжди
транзитивна, при цьому для нер
ожне ребр
ої перемич
X —Y . Тоді кожна вершина, d-
залежна від X таості існує одноелементний
сепаратор. У полі-деревах припускається
акший паттерн залежносте – не
транзитивна залежн ь через колізор.
Звісно, при переході до емпіричного
лежність м ся
сл
ди
Y , ідсторонюється.
При цьому множина d-залежних вершин
розпадається на ві підмножини: «ліві» та
раві». «Ліві» вершини зв'язані з
в
д
«п
Y ч ре ез
X , а «праві» вершини 'язазв ні з X через
Y . Ві івдтак, д всіх «л их» вершин ля Z
буде ( )YXZ ;;Ds , а для всіх «правих» вер-
тних моделях (порушення (1)).
З метою обґрунтування «сепа-
раційних» методів реконструкці було
введен ту я [
буде ( )Wшин WYX ;;Ds . Тож, на основі
тестів першого рангу ідентифікується таке:
а) існування ребра
X —Y (згідно
відсу р
між
правила
єдиної перемички); тність ебер
иною
о нас пне понятт 8, 11].
Визначення 3. Локально-мінімаль-
ним се
б)
Y та «лівими» вершинами верш
паратором в АОГ для пари вершин
),( YX зветься такий сепаратор Z , що
після вилучення з Z будь-якого його
члена перестає сепаратором для
),( YX . Формально: ( )YX ;;Ds Z &
& :Z∈∀W ( )YWX };{\;Ds Z¬
; вZ ) відсутність ребер між X та
«правими» вершинами W
, дерево бу
ідентифіковане тестами першого рангу.
.
Отже де цілком
Для полі-лісів правило єдиної
налогічно, тільки для
вершин замість відс
спрацьовує терм терм
бути
. перемички діє а
деяких пар торонення
або
Очевидно, у ісі та полі-ліс кожний
локально-мінімальний сепаратор є або
одноелементним, або пустим.
Для загального випадку АОГ-
моделі було доведено [11] таке правило.
Твердження 1 (прави о «відсто-
ронення» кандидатів у сепаратор
( )XZ ;;Ds
( )YZ ;;Ds . Отже, маємо такий резу тат.
вердження 3. Якщо в лісі (або
полі-лі
ль
Т
сі) існує ребро X —Y , то щодо
пари ),( YX для всіх вершин },{\ YXZ U∈
виконується умова правила єдиної
Експертні та інтелектуальні інформаційні системи
перемички, тобто
( )∨XZ ;;Ds ( )∨ YZ ;;Ds
( )∨ Z ;
о ає си
.
безперспективна
то після виконанн ршого рангу ці
ки
а
∨ YXZ ;;Ds ( )Y;Ds .
Результат формульовано у графових
термінах (щ відповід режиму нтезу
моделі), але він чинний також і для
режиму виведення з даних. Треба тільки
замінити графові предикати ( )*Ds на
ізоморфні емпіричні предикати Pr
X
( )*
Для коректного відтворення лісів та
полі-лісів залежностей з даних за
допомогою пропонованого алгоритму
достатньо самого простого припущення –
полегшеної форми реберної необ-
манливості [8]. Пропонована модифікація
гарантує виграш, допоки ліс не деградує,
тобто не перетвориться на ланцюг чи не
розпадеться на ізольовані ребра.
Спрогнозуємо роботу алгоритму PC
у випадку дерева залежностей. Ясно, що
алгоритм PC не може «знати», що
невідома структура належить до підкласу
дерев, а відтак, буде працювати як
звичайно у загальному випадку. Алгоритм
PC легко виявить відсутність ребер на
основі тестів першого рангу. Але далі
алгоритм PC буде продовжувати шукати
сепаратор для всіх тих пар вершин, які
поєднані ребрами. І ця
робота буде продовжуватися допоки
алгоритм не випробує всі підмножини
вершин, суміжних до кожної вершини,
дотичної до ребра, що розглядається. При
цьому алгоритм може дійти до тестів
високого рангу. Нагадаємо, що при
збільшенні рангу тесту ускладнюється
обчислення (з даних) інформації, потрібної
для виконання тесту.
Якщо вмонтувати в алгоритм РС
(після циклу k =1) правило «від-
сторонення» та правило єдиної перемички,
я тестів пе
два правила спрацюють, і процес
виведення лісу (полі-лісу) залежностей на
тому й завершиться. Потрібна модифікація
алгоритму зводиться до того, аби ті пари
вершин, для я х спрацювало правило
єдиної перемички, надалі не розглядалися
(для них вже не треба шукати сепаратори).
Ілюстративні приклади виведення
моделі
Аби наглядно показати, наскільки можна
поліпшити алгоритм PC, розглянемо
приклади. Нехай маємо дерево, де кожна
вершина, з виключенням кінцевих
(«листя»), має r суміжних вершин. Для
сті візьмемо дерево, показане на наочно
рис. 2. Ступ розгалуження r інь тут
дорівнює чотирьом. Кількість вершин у
цьому дереві дорівнює 29, кількість ребер
– 28. Кількість крайніх ребер (у яких одна
з вершин є «листям») дорівнює 20.
Кількість «не крайніх» ребер (у обох
кінців яких є по три сусідніх ребра)
дорівнює 8.
Кількість тестів першого рангу, які
третього рангу. Кількість тестів другого та
Рис. 2. Приклад дерева залежностей
виконає алгоритм PC при виведенні з
реальної відбірки даних, точно
спрогнозувати не можна. В цій моделі
кількість тестів першого рангу буде не
менше 6*9 = 54, якщо всі ланцюги
довжиною два ребра продукують
статистично значущі залежності. (Інакше
відпадає потреба у тестах першого рангу).
А максимальна кількість 29*28*27/2 =
= 10962 тестів досягається, коли
статистично міцними є всі ланцюги дерева
(довжиною до 6 ребер включно).
Для ідентифікації кожного «не
крайнього» ребра алгоритму PC
знадобиться виконати два тести третього
рангу і шість тестів другого рангу. Отже,
при виведенні цієї структури алгоритм PC
загалом виконає 6*8+3*20 = 108 тестів
другого рангу та 2*8+20 = 36 тестів
67
Експертні та інтелектуальні інформаційні системи
68
ої необманливості
(але в у
о з
л і и
пе ю
зміняться
несутт
ор
третього рангу може зменшитися тільки
при невиконанні реберн
таком разі алгоритм пропустить
відповідні ребра).
Якщ о броїти алгоритм правилом
єдиної перемички, то для виведення цієї
структури буде достатньо виконати тести
тільки нульового та першого рангу.
Причому кі ьк сть так х тестів залишиться
такою самою, що у РС.
Легко ренести іл страцію на
випадок полі-дерева. Взявши за основу
структуру з рис. 2, можна змінити
орієнтацію будь-яких ребер. Результатом
буде полі-дерево. При цьому показники
складності виведення моделі
єво, а саме, тільки зменшиться
кількість тестів першого рангу.
Отже, зазначена модифікація
алгоритму виведення надає радикального
прискорення у випадку, коли генеративна
модель має структуру дерева. Факт
прискорення буде зростати пропорційно
ступені r розгалуження дерева.
Недоліки алгоритму Р ще кон-
трастніше роявляют я у ипадку 1-
рівневого дерева ис. ). Така структура
відома під назвою наївний байєсівський
класифікатор. При реконструкції цієї мо-
делі з 1 -ма в инами (одна коренева
С
п ьс в
(р 3, а
0 ерш Y
та 9 її дітей) алгоритм РС буде виконувати
складні тести аж до 8-го рангу включно.
Справді, оскільки вершина Y має 9
суміжних вершин, при верифікації
кожного ребра Y — Xi алгоритм буде
випробувати (як можливі сепаратори) всі
підмножини всіх вершин, за виключенням
самих Y та Xi . У підсумку
викона -г
Су тес
потребує таку
саму к т в
г
д
Для мо
. 3, б, характеристики
будуть аналогічні. Алгоритм РС завершить
реконструкцію цього полі-дерева тестами
8-го рангу. А модифікованому алгоритму
буде достатньо тестів 1-го рангу. Єдина
відмінність випадку полі-дерева від
випадку дерева полягає у зменшенні
кількості тестів 1-го рангу (бо відсутність
ребер — ідентифікується тестами
нульового рангу).
n «
алгоритм
збереж юват
у у
ур і
а
алгоритм РС
є 9 тестів 8 о рангу, 72 тесту 7-го
рангу і т. д. купна кількість тів від 2-
го рангу до 8-го дорівнюватиме 2223. Це
може виглядати парадоксом, але для цієї
простої моделі алгоритм РС
ількіс ь тестів ище першого рангу,
як і для повно зв'язаної (насиченої) моделі
з 10-ти вершин.
Натомість модифікований (за
вказаними пропозиціями) алгоритм
завершить виведення цієї моделі відразу
після виконання тестів першого ран у і
правила є иної перемички.
делі типу полі-дерево,
показаному на рис
Xj Xi
Y
Підсумок
Показано, що за рахунок простої
корекції можна вдосконалити алгоритми
constrai t-based ( сепараційного») підходу
до виведення структури моделі. Внаслідок
пропонованого підсилення
е здатність відтвор и моделі в
загальном класі структ р (без орієн-
тованих циклів), і водночас зможе
виводити модель значно швидше, коли
структ а генеративної модел не має
ніяких циклів. Тобто алгоритм вто-
матично адаптується до моделей у підкласі
лісів та полі-лісів залежностей.
X5
X7
X6
X8
X9
X4
X3
X1
X2
a
Рис. 3. Прості структури, незручні
для алгоритму РС:
а – однорівневе дерево залежностей;
б – однорівневе полі-дерево
X6 X5 X4
X3 X7
X2 X8
Y X1 X9
б
Експертні та інтелектуальні інформаційні системи
Продемонстровані можливості
адаптації індуктивного алгоритму до
простих моделей е обмеж ються ви-
падком деревовидних стр тур залежно-
стей. Подібн
н у
ук
е скорочення пошуку
сепараторів можна забезпечити у всіх
випадках, коли структура моделі містить
час
мож
ада
1.
2.
.
3.
c
–103.
. Балабанов А.С. Формирование
минимальных d-сепараторов в системе
зависимостей // Кибернетика и системный
анализ. – 2009. – № 5. – С. 38–50.
. Chow C.K., Liu C.N. Approximating discrete
.
10. алабанов О.С. Індуктивне відтворення
деревовидних с
залежностей // П
мирования. – 2001. – № 1–2. – С. 95–108.
1. Балабанов О.С. Правила підбору
в байєсівських мережах //
ування. – 2007. – № 4. –
имано 22.09.2010
ович,
співробітник,
ститут програмних систем
АН України,
3187, Київ-187,
Академіка Глушкова, 40.
Тел.: (044) 526 3420.
e-mail: bas@isofts.kiev.ua
Б
труктур систем
роблемы програм-
1
сепараторів
Проблеми програм
С. 33–43.
принагідний фрагмент («розрізається» на
тини простими тестами). Більш того,
на озброїти алгоритм багатьма іншими
Отр
правилами, які значно розширять
птивні можливості індуктивного
виведення [8].
Pearl J. Probabilistic reasoning in intelligent
Про автора:
Балабанов Олександр Степан
старший науковий
кандидат технічниsystems: Networks of Plausible Inference. –
San Mateo: Morgan Kaufmann, 1988. –552 p.
Spirtes P., Glymour C., Scheines R. Causa-
х наук.
tion, prediction and search. 2nd Ed., New
York: MIT Press, 2001. – 496 p
Spirtes P. and C. Glymour. An algorithm for
fast recovery of sparse causal graphs // Social
Science Computer Review. – 1991. – Vol. 9. –
Місце роботи автора:
Ін
Н
0
Проспект
P. 62–72.
4. Neapolitan R.E. Learning bayesian networks.
– Upper Saddle River: Prenti e Hall, NJ,
2004. – 693 p.
к5. Андон Ф.И., Балабанов А.С. Стру турные
статистические модели: инструмент
познания и моделирования // Системні
дослідження та інформаційні технології. –
2007. – № 1. – С. 79 – 98.
О.С. теми
6. Балабанов Сис ймовірнісних
залежностей: графові та статистичні
властивості // Математичні машини та
системи. – 2009. – № 3. – С. 80–97.
7. Балабанов А.С. Реконструкция модели
вероятностных зависимостей по
статистическим данным. Инструментарий
и алгоритм // Проблемы управления и
информатики. – 2009. – № 6. – С. 90
8
9
probability distributions with dependence
trees // IEEE trans. on Information Theory. –
1968. – Vol. 14, N 3. – P. 462–467
69
ПРИСКОРЕННЯ АЛГОРИТМІВ ВІДТВОРЕННЯ БАЙЄСОВИХ МЕРЕЖ. АДАПТАЦІЯ ДО СТРУКТУР БЕЗ ЦИКЛІВ
|