Правила підбору сепараторів у баєсівських мережах

Запропоновано і обґрунтовано набір тверджень та правил, які допомагають знаходити мінімальні за розмірами сепаратори в моделях ймовірнісних залежностей, структурованих як ациклічні орієнтовані графи (тобто в баєсівських, гаусових та гібридних мережах). Правила призначені для методів виведення структ...

Full description

Saved in:

Bibliographic Details
Date:	2007
Main Author:	Балабанов, О.С.
Format:	Article
Language:	Ukrainian
Published:	Інститут програмних систем НАН України 2007
Subjects:	Моделі і засоби систем баз даних і знань
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/271
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Правила підбору сепараторів у баєсівських мережах / О.С. Балабанов // Пробл. програмув. — 2007. — N 4. — С. 21-31. — Бібліогр.: 18 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1859725525378924544
author	Балабанов, О.С.
author_facet	Балабанов, О.С.
citation_txt	Правила підбору сепараторів у баєсівських мережах / О.С. Балабанов // Пробл. програмув. — 2007. — N 4. — С. 21-31. — Бібліогр.: 18 назв. — укр.
collection	DSpace DC
description	Запропоновано і обґрунтовано набір тверджень та правил, які допомагають знаходити мінімальні за розмірами сепаратори в моделях ймовірнісних залежностей, структурованих як ациклічні орієнтовані графи (тобто в баєсівських, гаусових та гібридних мережах). Правила призначені для методів виведення структури моделі з даних за допомогою знаходження сепараторів (тобто виявлення умовної незалежності змінних). Ми сформулювали необхідні вимоги до членів мінімальних сепараторів, виходячи з критерію d-сепарації та властивостей ациклічних орграфів. Ці вимоги та правила дозволяють відсіяти деякі кандидати у сепаратор і спростити задачу пошуку сепараторів, а, також, і задачу ідентифікації структури моделі залежностей.
first_indexed	2025-12-01T11:15:07Z
format	Article
fulltext	Моделі і засоби систем баз даних і знань © О.С. Балабанов, 2007 ISSN 1727-4907. Проблеми програмування. 2007. № 4 21 УДК 007:681.3.00 О.С. Балабанов ПРАВИЛА ПІДБОРУ СЕПАРАТОРІВ У БАЄСІВСЬКИХ МЕРЕЖАХ Запропоновано і обґрунтовано набір тверджень та правил, які допомагають знаходити мінімальні за розмірами сепаратори в моделях ймовірнісних залежностей, структурованих як ациклічні орієнтовані графи (тобто в баєсівських, гаусових та гібридних мережах). Правила призначені для методів виведення структури моделі з даних за допомогою знаходження сепараторів (тобто виявлення умовної незалежності змінних). Ми сформулювали необхідні вимоги до членів мінімальних сепараторів, виходячи з критерію d-сепарації та властивостей ациклічних орграфів. Ці вимоги та правила дозволяють відсіяти деякі кандидати у сепаратор і спростити задачу пошуку сепараторів, а, також, і задачу ідентифікації структури моделі залежностей. Вступ Предметом розгляду є ймовірнісні моделі залежностей, структуровані як аци- клічні орієнтовані графи (АОГ-моделі) [1– 8]. Такі моделі звуться баєсівськими мережами, коли змінні – номінальні (дискретні), гаусовими мережами, коли змінні – неперервні, а залежності – лінійні з нормальними розподіленнями, та, відповідно, гібридними мережами, коли є змінні різних типів. АОГ-моделі стають популярним апаратом і застосовуються для моделювання стохастичних залежностей та каузальних відношень. Графові моделі залежностей забез- печують більш системну репрезентацію, ніж традиційні види моделей – логічні формули, регресійні рівняння, правила класифікації, діагностики чи розпізнавання образів і т.д. АОГ-моделі глибше відобра- жають механізми, задіяні у предметній галузі, і в принципі здатні відбивати каузальні відношення. Достоїнства АОГ- моделей – наочність, компактність, здатність відображати причинно- наслідкові зв'язки, обчислювальна ефективність ймовірнісного виведення від свідчень. Ці властивості забезпечують ефективне розв'язання задач медичної, технічної і комп’ютерної діагностики [9], розпізнавання мови [10], прогнозування наслідків рішень і дій людини або агента і т.д. АОГ-моделі становлять апарат ймо- вірнісних експертних систем. Привабливим способом застосування стало виведення (ідентифікація) АОГ- моделі системи з статистичних даних спос- тережень за системою. Виведення АОГ- моделей з даних спостережень сприяє „інсайту” щодо структури і зв’язків процесів у досліджуваній предметній області, дозволяє відтворити структурно адекватну систему впливів. Ця аналітична технологія широко застосовується у дослідженнях в медико-біологічній галузі, зокрема, для аналізу механізмів експресії генів [11]. Також така технологія дозволяє вивести з даних модель для прогнозування погоди [12] та ін. Наприклад, виходячи з даних Світового банку, проведено аналіз причин і наслідків бідності в 80 країнах, що розвиваються [13]. Результатом аналізу (за допомогою алгоритма ‘PC’) стала модель, фрагмент якої показано на рис. 1. Модель показує фактори народжуваності в бідних країнах. GDP – це величина прибутку сімейного господарства на душу населення; Gini index – коефіцієнт Джині (індекс концентрації доходів). Відомо, що проблема виведення структур баєсівських мереж з даних є NP- важка [14]. Тож відомі методи стикаються з великими труднощами вже коли кількість змінних досліджуваної системи сягає кількох десятків. Ідентифікація структури АОГ-моделі методами “constraint-based” підходу (на які тут орієнтуємося) ґрунтується на пошуку сепараторів. Оскільки при пошуку сепараторів виникають складні переборні задачі, бажано знаходити мінімальні сепаратори. Це важливо також і в задачах виведення Моделі і засоби систем баз даних і знань 22 наслідків від свідчень на АОГ-моделі, бо інформація розповсюджується у структурі моделі через сепаратори. Ми показуємо нові можливості для зменшення складності розв'язання названих задач, пропонуємо засоби для звуження області пошуку мінімальних сепараторів і даємо від- повідне граф-теоретичне обґрунтування. Матеріал викладається переважно на стро- гому формальному рівні (з графічними ілюстраціями). Наскільки відомо автору, результати є цілком оригінальними. Всі результати роботи чинні для всього класу АОГ-моделей, включаючи будь-які гібридні моделі. 1. Теоретичні основи та проблема Нагадаємо потрібні елементарні поняття. Позначатимемо дугу символом →. Ребро – це дуга, орієнтація якої може бути невідома або ігнорується. Вершини графа звуться суміжними, якщо вони поєднані ребром, що позначається x– y. Шлях суміжності (або просто шлях) у графі – це послідовність дотичних ребер (будь-якої орієнтації) без повторення вершин. Тобто кожна чергова вершина (за винятком останньої) поєднана ребром з наступною вершиною цього шляху. Як виняток, крайні вершини шляху можуть збігатися, і тоді цей шлях називають циклом. Орпуть або оршлях (тобто строго орієнтований шлях) – це шлях, на якому всі ребра є орієнтовані в напрямку одного й того самого кінця шляху (орієнтовані узгоджено). Орцикл – це оршлях, на якому початкова вершина збігається з останньою. Ациклічний орієнтований граф (АОГ) – це орграф, в якому немає орциклів. Надалі терміни граф та орграф слід розуміти як АОГ. Якщо існує дуга x→y, то вершина x зветься батьком вершини y. Якщо існує оршлях x→L→y, то вершина y зветься нащадком вершини x. АОГ-модель визначена як (G, ϑ), де G – ациклічний орієнтований граф (де кожній змінній відповідає вершина графа), а ϑ – сукупність локально заданих параметрів. З огляду на взаємно- однозначну відповідність, терміни „змінна” (моделі) та „вершина” (графа) вживаються як взаємозамінні. Визначення 1. Колізором (колайдером, collider) в орграфі зветься фрагмент із двох суміжних дуг вигляду x→y←z. Якщо колізор x→y←z є частиною шляху π в орграфі, то y називають колізорною (колайдерною) вершиною на шляху π. (Зазначимо, що вершина y одночасно може бути неколізорною на якомусь іншому шляху). Безколізорний (безколайдерний) шлях в орграфі – це шлях, який не містить жодного колізора. Заради лаконічності будемо називати безколізорний шлях ланцюгом. (При цьому слід пам'ятати, що це не збігається з поняттям Марковського ланцюга, бо може існувати декілька безколізорних шляхів між двома заданими вершинами.) Відношення між структурою моделі і фактами умовної незалежності, репрезентованими в АОГ-моделі, формалі- зовано через критерій d-сепарації [1, 2]. Визначення 2 (d-сепарація). Шлях π в АОГ-моделі зветься d-закритим (d-бло- кованим) за допомогою (кондиціонування, блокування) множини вершин S, якщо і тільки якщо • існує вершина x, x∈π, x∈S, причому на шляху π лежить дуга x→ чи ←x, або • на шляху π лежить хоча б один колізор →y←, з тим, що y∉S та не існує такої z∈S, що є оршлях y→L→z. Рис.1. Виведена модель факторів народжуваності в бідних країнах Рівень неписьменності Рівень дитячої см ер тності Індек с несвободи G ini Index Прибутк овість сільського господарства G D P Народжуван ість Моделі і засоби систем баз даних і знань 23 Множина вершин S d-сепарує вершини x та y (x,y∉S) якщо і тільки якщо всі шляхи між x та y є d-закритими за допомогою множини вершин S. Будемо позначати таку d-сепарацію предикатом Ds(x⊥S⊥y). У разі, коли S = ∅, будемо записувати такий предикат скорочено як Ds(x⊥⊥y). Якщо хоча б один шлях між x та y не є d-закритим (тобто є d-відкритим), то говорять, що вершини x та y d-з'єднані. Факт d-з'єднання будемо виражати у формі ¬Ds(x⊥S⊥y). Визначення 3. Якщо предикат Ds(x⊥S⊥y) діє в АОГ G, то S зветься сепаратором в G для пари вершин (x, y). Критерій d-сепарації дозволяє про- водити аналіз моделі чисто графовим апаратом. Зокрема, безпосередньо з критерію d-сепарації випливає Правило 1. Якщо в АОГ є лише одна вершина, d-з'єднана з x (залежна від x), тобто множина {z\|¬Ds(z⊥⊥x)}={y}, то x–y. Явно за цих умов немає альтер- нативного варіанта забезпечити відкритий шлях між вершинами x та y, як тільки з'єд- нати їх ребром. Поняття умовної незалежності відоме з теорії ймовірностей і статистики [15]. Відношення умовної незалежності змінних x та y при фіксації значень (кон- диціонуванні) набору змінних S будемо виражати формулою Pr(x⊥S⊥y), де x,y∉S. Для дискретних змінних незалежність Pr(x⊥S⊥y) означає p(y\|S,x) = p(y\|S). (1) Для частотних оцінок ймовірностей відповідна рівність виконується в асимпто- тичному сенсі. У гаусових мережах умовна незалежність проявляється як нульова (з точністю до статистичного гамору) величина коефіцієнта частної кореляції. Безумовна незалежність є просто спеціальним випадком умовної незалежно- сті з порожньою умовою, тобто Pr(x⊥∅⊥y), або коротко Pr(x⊥⊥y). Факт безумовної залежності будемо виражати як ¬Pr(x⊥⊥y). Мета аналітика – ідентифікувати структуру моделі “індуктивно”, тобто ви- вести її з даних спостережень чи вимірю- вань (спираючись на кілька методологіч- них постулатів) [3– 5, 7, 14]. Загальновідомо [1–5]: якщо в АОГ немає ребра x–y, то існує сепаратор для пари вершин (x, y). Зокрема, таким сепара- тором є об'єднання батьків вершин x та y. Отже, маємо принцип у формі правила {¬∃S: Pr(x⊥S⊥y)} ⇒ (x–y). Відомі методи і алгоритми іденти- фікації структури АОГ-моделі можна поділити на два основних підходи – “constraint-based” (або “сепараційний”) та “оптимізаційний” (апроксимаційний) [3–5, 7, 14]. Маємо на меті підсилення сепараційних методів. Робота таких мето- дів полягає у пошуку сепараторів для кожної пари змінних. Найвідоміший метод цього підходу – алгоритм ‘PC’ [3, 4]. Відома теорема АОГ-семантики [16] стверджує, що з факту d-сепарації в АОГ випливає істинність відповідного тверд- ження умовної незалежності, тобто Ds(x⊥S⊥y) ⇒ Pr(x⊥S⊥y). (2) Теорема АОГ-семантики забезпечує процедуру зчитування тверджень умовної незалежності з графа АОГ-моделі. Але процес ідентифікації моделі за статистич- ними даними має рухатись у зворотному напрямку, відштовхуючись від результатів тестування незалежності. Як методологічну базу для методів ідентифікації АОГ-моделей теоретики прийняли припущення необманливості розподілу ймовірностей для АОГ-моделі [3, 4], що можна виразити як Pr(x⊥S⊥y) ⇒ Ds(x⊥S⊥y). (3) Зіставляючи (2) та (3), отримуємо Ds(x⊥S⊥y) ⇔ Pr(x⊥S⊥y). (4) Але беззастережно покладатися на припущення необманливості в повному обсязі не можна (див., зокрема, [7]). Відомі методи й алгоритми сепараційного підходу використовують більш обережні правила висновування. Загально- прийнятим є таке правило ідентифікації відсутності ребра (∃S : Pr(x⊥S⊥y)) ⇒ ¬(x–y). (5) Кардинальність умови S визначає складність і надійність тестування умовної Моделі і засоби систем баз даних і знань 24 незалежності Pr(x⊥S⊥y). Чим більшою є множина кандидатів у члени сепаратора, тим складнішою є переборна задача пошуку сепаратора. Із зростанням кардинальності S збільшується перелік потрібних статистик і обсяг їх обчислення. Це особливо ускладнює виведення дискретних моделей. Для оптимізації пошуку сепаратора алгоритм ‘РС’ [3–5] обмежує множину кандидатів у члени сепаратора для (x, y) множиною вершин, які вважаються суміжними до x або до y на даному етапі ідентифікації (хоча часто не всі вони є насправді суміжні). Для реальних моделей така тактика не розв'я- зує всіх проблем. Мабуть найгіршим є те, що алгоритм продовжує шукати сепаратор у багатьох випадках, коли його не існує, і, як наслідок, ризикує припуститися помилки при тестуванні умовної незалежності з великою кардинальністю умови. Тому є потреба знайти нові мож- ливості вдосконалення алгоритмів пошуку. Бажано знаходити сепаратори найменшої кардинальності. Для пошуку мінімальних сепараторів ми не можемо скористатися відомими (з транспортних задач) методами пошуку розрізу мережі та мінімального потоку з огляду на те, що: • залежності блокуються маніпуляцією вершин (змінних), а не ребер; • властивості d-сепарації відмінні від “транспортних аналогів”. Не можемо скористатися і іншими методами теорії графів, бо на момент пошуку сепаратора структура графа є незавершена або цілком невідома. Проблема полягає не лише в тім, щоб знайти мінімальні сепаратори, але й досягти цього економно, тобто виконати якнайменше тестів (мінімізувати кількість невдалих тестів) та допоміжних обчислень. 2. Властивості членів сепаратора. Формування правил Доцільно ввести наступні поняття [17, 18]. Визначення 4. Локально-мінімальним сепаратором в АОГ для пари вершин (x, y) зветься такий сепаратор S, що після вилу- чення з S будь-якого його члена (елемента) він перестає бути сепаратором для (x, y). Формально це записується як Ds(x⊥S⊥y), ∀z∈S: ¬Ds(x⊥S\{z}⊥y). Визначення 5. Назвемо сепаратор S* для пари вершин (x, y) в АОГ мінімальним сепаратором, якщо для (x, y) не існує сепаратора меншої кардинальності, тобто для всіх інших сепараторів S для пари (x, y) маємо \|S\| ≥ \|S*\|. Зауважимо, що може бути декілька мінімальних сепараторів для пари вершин (x, y) в тому самому АОГ. Позначатимемо мінімальний та локально-мінімальний сепаратор для пари вершин (x, y) від- повідно як Smin(x,y) та Slom(x,y). Поняття локально-мінімального сепа- ратора важливо також для алгоритмів розмірковування на моделях (в експертних системах) [1, 5]. При виведенні від свідчення x до цільової змінної y інформація має проходити через кожну z∈Slom(x,y) кожного Slom(x,y). Зауваження 1. Зрозуміло, що кожний мінімальний сепаратор є водночас і локально-мінімальним. Тож всі необхідні вимоги до членів локально-мінімального сепаратора є також необхідними вимогами до членів мінімального сепаратора. Водночас зворотне невірне, тобто не кожний локально-мінімальний сепаратор є мінімальним. Локально-мінімальний сепа- ратор може не мати жодного спільного члена з мінімальним сепаратором. Приклад показано на рис.2, де Slom(x,y) = = {z, w}, Smin(x,y)={q}. Твердження 1. Якщо в АОГ діє ¬Ds(x⊥⊥y) і множина S є локально- мінімальним сепаратором для пари вершин Рис. 2. Приклад моделі, де мінімальний та локально-мінімальний сепаратори не перетинаються w q y z x Моделі і засоби систем баз даних і знань 25 (x, y), то у складі S існує щонайменше одна якась вершина, що лежить на якомусь ланцюгу між вершинами x та y. Це випливає з критерію d-сепарації. Тривіально зрозуміло, що між x та y існують ланцюг(и). Якби серед них було ребро x–y, то ніякого Slom(x,y) не існувало б. А оскільки такий сепаратор існує, то всі ланцюги між x та y мають довжину два чи більше ребер. Всі ті ланцюги є закриті за допомогою S. Звідси, на кожному з тих ланцюгів лежить якась вершина z∈S.  Слід додати, що це твердження не можна посилити. Тобто можливо, що всі члени Slom(x,y), за винятком одної вершини z, не лежать ні на якому ланцюгу між вершинами x та y. Твердження 2 (“подвійне 1-відсі- кання”; ‘double 1-cutting’). Якщо в АОГ існує якась вершина z, що забезпечує Ds(w⊥z⊥x) та Ds(w⊥z⊥y), то вершина w не входить до складу жодного локально-мі- німального сепаратора для пари вершин (x, y). Отже, маємо правило 2 (“подвійного 1-відсікання”): [∃z: Ds(w⊥z⊥{x,y})] ⇒ w ∉ Slom(x,y). Зауважимо, що правило 2 неявно вбудовано в алгоритм ‘РС’ (як спеціальний випадок). З огляду на тактику ‘РС’, логічно виникає питання про розширення твердження 2. Перше питання: чи можна виключити вершину w з множини кандидатів у склад сепаратора (зокрема, мінімального) для (x, y) на підставі лише “однобічного 1-відсікання”: ∃z: Ds(w⊥z⊥x) або Ds(w⊥z⊥y). Відповідь буде ні. Прикладом є модель, показана на рис. 3, де Ds(w⊥z⊥x), проте Smin(x,y) = {t, w}. Більш того, тут вершина w (як і вершина t) є обов’язковим (незамінним) членом будь- якого сепаратора для (x, y). Ще загаль- ніше: вершина w буде незамінним членом будь-якого сепаратора для (x, y), навіть якщо вбудувати показаний фрагмент графа в контекст оточуючого графа моделі (де можуть з'явитися додаткові шляхи між x та y). Отже, посилити правило 2 зазначеним чином не вдається. Посилити це правило також не можна і в іншому аспекті, а саме, послабити (роз- ширити) умову так, щоб вершина w відсі- калася від вершин x та y не одною й тою вершиною z, а різними. Такий варіант від- сіювання кандидатів до складу сепаратора потребує застережень. Аналог твердження 2 буде не вірний, що демонструється наступними прикладами. Тривіальним прикладом є модель x←q←w→z→y. Інший приклад такого випадку показано на рис. 4. Для цієї моделі виконуються сепарації Ds(w⊥q⊥x) та Ds(w⊥z⊥y), тобто розширена версія умови твердження 2. Однак вершина w входить до складу локально- мінімального сепаратора, а саме Slom(x,y) = {q, z, w}. Тому цей сепаратор не є мінімальним. Існують два мінімальних сепаратора для (x, y): {g, q} та {h, z}, які не містять вершини w. Як бачимо, розши- рення правила “подвійного 1-відсікання” до правила “двох 1-відсікань” може мати практичний сенс. Але існують інші моделі, де виключення з пошуку сепаратора вер- шини w за таких умов може призвести до втрати мінімального сепаратора. (Заува- жимо, що коли модель має приховані змінні, таке правило може призвести до Рис. 3. Модель, де “однобічно 1-відсікається” член мінімального сепаратора x t y z w Рис. 4. Модель, що ілюструє випадок двох 1-відсікань (‘pair of 1-cutting’) w z y q x g h Моделі і засоби систем баз даних і знань 26 неможливості знайти існуючий сепаратор. Але модель із прихованими змінними вже виходить за межі класу АОГ). Підсумувати ці міркування можна таким твердженням про “заміщення” члена сепаратора. Якщо в АОГ вершина w входить до складу якогось локально-мінімального сепаратора для пари вершин (x, y), та існують якісь дві вершини q, z, такі, що Ds(w⊥q⊥x) та Ds(w⊥z⊥y), то існує якийсь сепаратор для (x, y), що не містить вершини w. Довести це просто. Дійсно, триві- альним сепаратором для (x, y) є об'єднання множин батьків вершин x та y. Зрозуміло, що вершина w не входить до цього об'єднання (як несуміжна до x та y).  Більш того, це доведення збереже чинність і в разі, якщо відкинути першу частину умови і узагальнити другу частину умови так, що відсікання вершини w від x та y відбувається за допомогою довільних множин вершин. Отже ми обґрунтували Твердження 3 (правило “двох від- сікань”; ‘pair of cutting’). Якщо сепаратор для (x, y) існує й існують множини вершин S, R, такі, що Ds(w⊥S⊥x) та Ds(w⊥R⊥y), то існує якийсь сепаратор для (x, y), що не мі- стить вершини w. Виключення з пошуку сепаратора тих несуміжних вершин, які відсікаються від x чи y за допомогою якихось третіх вершин (1-сепараторами) є більш виправдане, ніж коли відсікання досягається складними сепараторами. Подаємо випадок, коли виключення вершини зі списку потенційних членів сепаратора на підставі того, як вона відсікається від x та y за допомогою 2-сепараторів, веде до втрати мінімального сепаратора. Це ілюструє модель на рис. 5, де маємо Ds(w⊥{g,h}⊥x) та Ds(w⊥{q,z}⊥y). Проте Smin(x,y)= {w, r, t}, й інших мінімальних сепараторів немає. В таких ситуаціях алгоритм ‘РС’ не знайде мінімального сепаратора для (x, y), але має знайти {g, h, r, t} або {q, z, r, t}. Та незважаючи на те, тактика алгоритма ‘РС’ в багатьох випадках виправдовується мір- куванням скорочення множини кандидатів у сепаратор (а це спрощує перебір). Твердження 4 (базова теорема про членів локально-мінімального сепаратора). Якщо в АОГ вершина z входить до складу якогось локально-мінімального сепаратора для пари вершин (x, y), то: а) існує якийсь оршлях ρ від вершини z до вершини x або y; б) якщо не існує жодного ланцюга між x та z, який не проходить через y, то мають існувати не менше як два якісь ланцюги λ1 та λ2 між z та y, які не проходять через x та закінчуються дугами →y; (відтинки ланцюгів λ1 та λ2, що прилягають до вершини y, можуть взаємно накладатися). Це уточнення твердження з [17]. Доведення. Звертаємось до (а). Поз- начимо символом S локально-мінімальний сепаратор для (x, y), членом якого є z. Вер- шина z закриває якийсь шлях τ між x та y, причому z є неколізорною вершиною на шляху τ. (Це негайно випливає з критерію d-сепарації та визначення локально-міні- мального сепаратора). Доведення буду- ється за ітеративною схемою. Якщо вер- шина z лежить на деякому ланцюгу між вершинами x та y, то негайно отримуємо бажане. (Якщо ланцюг розрізати на частини, то не менше ніж одна частина буде оршляхом). Інакше, нехай вершина z не лежить ні на якому ланцюгу між вер- шинами x та y. Розглянемо шлях τ, який закривається за допомогою z. Будемо просуватися по τ, розпочавши з дуги z→. Зрозуміло, що пройшовши певний оршлях, ми або дістанемось вершини x чи y (і тоді доведення закінчено), або дійдемо до колізора. Нехай цей найближчий до вер- шини z колізор на цій частині шляху τ буде →q1←. Оскільки z є членом локально- мінімального сепаратора S і закриває шлях Рис.5. Модель, де мінімальний сепаратор для (x, y) включає вершину, несуміжну до x та y. r t zh w yx qg Моделі і засоби систем баз даних і знань 27 τ, то колізор →q1← є d-відкритим при кондиціонуванні множини вершин S\{z}. Тож або маємо q1∈S, або S включає якогось нащадка вершини q1, скажімо t1 (це найближчий такий нащадок). Відповідно маємо оршлях z→L→q1 або z→L→q1L→t1. Тепер розглядаємо відповідно q1 або t1 як члена локально- мінімального сепаратора аналогічно тому, як ми розглядали вершину z. Повторю- ючи викладені міркування ітеративно, будемо продовжувати оршлях від z до чергового члена q2 або t2 множини вершин S і так далі. Оскільки множина S є скін- ченою, а повторне попадання в ту саму вершину неможливо (строго орієнтований цикл неможливий за визначенням), то ми неодмінно дійдемо по оршляху від z до вершини x або y. Отримали бажане (а).  Переходимо до пункту (б). Вершина z закриває якийсь шлях між x та y; якщо ми попрямуємо по цьому шляху від z в бік вершини x, то дійдемо до якогось відкри- того колізора →q←. Зрозуміло, вершина q або якийсь її нащадок входять до складу S. Тож, згідно пункту (а) твердження, існує оршлях q→L→y. (Якщо уявити оршлях q→L→x, то отримаємо ланцюг zL→q→L→x, що суперечить умові (б)). Отже, маємо перший потрібний ланцюг λ1: z–L→q→L→y. Нагадаємо, що вершина z закриває якийсь шлях між x та y, отож іс- нує шлях λzy від z в сторону вершини y, який розпочинається з іншої дуги, ніж та, яка веде в сторону вершини x. Якщо ми почнемо рухатись по цьому шляху λzy від z в сторону вершини y, то або дійдемо до y, не зустрівши колізора (що завершує дове- дення), або зустрінемо колізор →w←. Оскільки цей колізор – відкритий за кондиціонування S, то, аналогічно вище- сказаному, має бути оршлях w→L→y. Таким чином, отримуємо другий потріб- ний ланцюг λ2: z–L→w→L→y.  Зауваження 2 (до твердження 4). Якщо в АОГ маємо z,w∈Slom(x,y), то не обов'яз- ково існують оршляхи з вершин z та w до одної й тої самої вершини з пари (x, y). Наприклад, для АОГ на рис. 4 маємо Slom(x,y) = {q, z, w}, і існує оршлях q→x, але не існує оршляху від z до x. Але існує z→y. Для підвищення ефективності пошуку сепараторів треба інтенсивно скорочувати кількість кандидатів до складу сепаратора. Інтуїтивно видається, що мають бути ще якісь ознаки, за якими можна розпізнати вершини, які не є членами потрібного локально-мінімального сепаратора. Зокрема, можна висунути таку гіпо- тезу: якщо одна вершина із пари (x, y) сепарує вершину z від іншої вершини пари (x, y), то вершина z (правдоподібно) не є членом ніякого Slom(x,y). За цією гіпотезою стоїть інтуїтивна здогадка, яку можна висловити так: перша вершина “відсторонює” третю вершину від другої вершини. Тому третя вершина не лежить “поміж” першою та другою, і отже, правдоподібно не є членом локально- мінімального сепаратора для першої та другої вершини. Це можна сформулювати як таке правило “відсторонення” кандидатів у сепаратор: Ds(y⊥x⊥z) ⇒ z ∉ Slom(x,y). Отже, формулюємо наступне твердження [18]. Твердження 5 (“відсторонення” кандидатів у сепаратор; ‘placing aside’). Якщо в АОГ-моделі вірне Ds(z⊥x⊥y)&¬Ds(z⊥⊥y), то вершина z не є членом ніякого локально-мінімального се- паратора для пари вершин (x, y). Доведення. Нехай в АОГ вірне ¬Ds(x⊥⊥y), Ds(z⊥x⊥y), ¬Ds(z⊥⊥y), і припустимо z∈Slom(x,y). З огляду на Ds(z⊥x⊥y) усі шляхи між z та y, які не проходять через x, є колізорні. Тож не існує ніякого оршляху z→L→y. Звідси, згідно твердження 4 (а) та факту z∈Slom(x,y), існує оршлях z→L→x. Тому, всі ланцюги між z та x мають кінцеву дугу →x (заборона орциклів). Водночас ¬Ds(z⊥⊥y) та Ds(z⊥x⊥y) означає, що існують ланцюги між z та y, і то всі вони проходять через x. Розглянемо відтинки цих шляхів від вершини x до вершини y. Кожен такий відтинок має першу дугу x→L, бо інакше ¬Ds(z⊥⊥y) є неможливе. (Вище з’ясовано, що всі ланцюги між z та x Моделі і засоби систем баз даних і знань 28 мають дугу →x). Отож, існує оршлях (оршляхи) x→L→y. Візьмемо локально-мінімальний сепа- ратор для (x, y), до якого належить z, та позначимо його Sz. Тоді множина Sz\{z} не є локально-мінімальним сепаратором для (x, y). Тобто за блокування вершин Sz\{z} існує відкритий шлях τ між вершинами x та y, який проходить через z (згідно d- сепарації). Вище з'ясовано, що всі ланцюги між z та y проходять через x. Отож, існує колізорний шлях τ2 між z та y, який є частиною шляху τ (тобто не проходить через x) і який відкривається при кон- диціонуванні вершин Sz\{z}. Таким чином, аби був відкритий шлях τ між вершинами x та y через z за кондиціонування вершин Sz\{z}, необхідно, щоб кондиціонування вершин Sz\{z} відкривало всі колізори qi на відтинку τ2 цього шляху між z та y. Отож, (згідно d-сепарації) для кожного такого колізора qi маємо qi ∈Sz або має існувати оршлях qi→L→wi, де wi∈Sz. Візьмемо колізор q1, найближчий до вер- шини z. Оскільки цей колізор q1 є відкри- тий при кондиціонуванні вершин Sz\{z}, то існують w1∈Sz та q1→L→w1. (Зокрема, можливо q1 ≡ w1). Згідно твердження 4 (а), існує w1→L→x або w1→L→y. Проте випадок w1→L→y є неможливим з огляду на те, що тоді конкатенація шляхів z–L–q1→L→w1 та w1→L→y дає ланцюг між вершинами z та y, який не проходить через x (а неможливість цього показана вище). Отже, має бути оршлях w1→L→x. Звідси випливає, що кондиціонування вершини x відкриває колізор →q1← на шляху τ2 між z та y. Водночас за кондиціонування вершин Sz\{z} є відкритим шлях τ та його відтинок між вершинами q1 та y. Отже, на цьому відтинку зустрінемо наступний колізор →q2←, який є відкритий за конди- ціонування вершин Sz\{z}, тобто існує оршлях q2→L→w2, де w2∈Sz. Повторю- ючи викладені міркування рекурсивно, ми прийдемо в останній на шляху τ2 колізор →qk←, такий, що існує оршлях qk→L→wk, де wk∈Sz й існує оршлях wk→L→x. Таким чином, відстеживши названі шляхи, отримуємо шлях z→L→x←L←wk←L←qk←–L–y, на якому є лише один колізор →x←. Отже, має бути ¬Ds(z⊥x⊥y), що суперечить умові твердження.  Доведення пояснюється на рис. 6. Отже, твердження 5 обґрунтовує коректність правила 3 (“відсторонення”): [Ds(z⊥x⊥y)&¬Ds(z⊥⊥y)] ⇒ z∉Slom(x,y). Зрозуміло, що змінні x та y в антецеденті можна міняти місцями. Це правило здатне скоротити кількість кандидатів до складу сепаратора і, отже, створює передумови підвищення надійності та зменшення переборної і обчислювальної складності методів іден- тифікації структур АОГ-моделей. Більше того, в деяких ситуаціях воно дозволяє вичерпно ідентифікувати ребро, тобто взагалі припинити пошук сепаратора для даної пари вершин, з'ясувавши, що сепаратора не існує. Дійсно, якщо всі потенційні кандидати до сепаратора “відсторонюються”, то можна зробити висновок, що сепаратора для цієї пари не існує. Отже, з тверджень 1 та 5 випливає правило 4 (“швидкої” ідентифікації ребра), яке формально записується як ¬Ds(x⊥⊥y)&{∀z∈U\{x, y}: [Ds(z⊥⊥x)\/ \/Ds(z⊥⊥y)\/Ds(z⊥x⊥y)\/Ds(z⊥y⊥x)]} ⇒ ⇒ x–y, де U – множина всіх вершин графа; символ “\/” – означає диз’юнкцію. Твердження 6. Нехай ¬Ds(x⊥⊥y) та маємо Рис.6. Ілюстрація доведення твердження 5 (‘placing aside’) yx z q w Моделі і засоби систем баз даних і знань 29 V = {v\|¬Ds(v⊥⊥x)\/¬Ds(v⊥⊥y)}, Q = {q\| Ds(q⊥x⊥y)&¬Ds(q⊥⊥y)}, R = {r\| Ds(r⊥y⊥x)&¬Ds(r⊥⊥x)}, та множина V\(Q∪R∪{x,y}) складається з єдиного елемента z. Тоді, якщо ¬Ds(x⊥z⊥y), то існує ребро x–y. Випливає з тверджень 1, 4 та 5. Це твердження дає правило 5 (“іденти- фікації ребра за наявності єдиного не відстороненого”). (Не записуємо його окремо з огляду на громіздкість.) Твердження 7. Нехай в АОГ вірне ¬Ds(x⊥⊥y) та маємо відсторонення Ds(Q⊥x⊥y) та Ds(x⊥y⊥R). Нехай буде M = {z\|¬Ds(z⊥⊥x)&¬Ds(z⊥⊥y)}.Тоді, якщо M\[(Q∪R)∩M∪{x,y}] = ∅, то існує x–y. Випливає з тверджень 1 та 5. Це твердження дає правило 6 (“ідентифікації ребра за відсутності посередника”). Твердження 8. Нехай ¬Ds(x⊥⊥y) й існує сепаратор для пари вершин (x, y), і нехай Q – це множина всіх вершин q, для яких вірне Ds(q⊥x⊥y) \/ Ds(q⊥y⊥x) \/ Ds(q⊥⊥x) \/ \/ Ds(q⊥⊥y). Тоді, якщо множина U\(Q∪{x,y}) (де U – множина всіх вершин графа) складається з єдиного елемента z, то z є обов'язковим членом всіх сепараторів для пари вершин (x, y). Доведення. За зазначених умов має бути ланцюг x–z–y. Якби замість нього був будь-який довший ланцюг x–q–L–z–L–y, то вершина q теж була б членом множини U\(Q∪{x,y}). Якби було x→z←y, то з факту існування сепаратора для (x, y) випливає (див. твердження 1) існування якогось ланцюга з двох чи більше ребер, який не проходить через вершину z (заборона орциклів). Отож, той ланцюг проходив би через іншу вершину t, тобто має існувати x–L–t–L–y. Тоді вершина t теж була б членом множини U\(Q∪{x,y}). Отож, з заперечення існування ланцюга x–z–y випливає протиріччя умові. 3. Застосування правил у виведенні структур АОГ-моделей Деякі з наведених тверджень можуть зда- тися тривіальними. Ймовірно, може спасти на думку, що з’ясувати значення деяких (графових) предикатів в лівих частинах запропонованих правил буде складніше, ніж прямо знайти потрібний сепаратор. Проте сумніви мають розсіятись, щойно ми переходимо від аналіза графа до аналіза даних. Запропоновані правила призначені головним чином для ідентифікації моделі (коли структура графа ще невідома). При цьому графові предикати замінюються їх емпіричними “двійниками” згідно (4), та “обчислюються” за допомогою виконання тестів на відбірці даних. Наприклад, емпіричний факт ¬Pr(x⊥⊥y) беззастережно свідчить про існування ланцюга або ребра x–y. Але при малих відбірках даних багато свідчень у формі емпіричних фактів умовної незалежності є вразливими до відбіркових ухилень (і то у різній мірі для різних форматів тестів), тому мають бути застосовані з обачністю. Зокрема, емпіричний факт Pr(x⊥⊥y) можна трактувати як робастне (для реалістичних розмірів відбірки даних) свідчення відсутності ребра x–y, але не як свідчення відсутності ланцюга [7]. Робастним є свідчення у формі Pr(x⊥y⊥z)&¬Pr(x⊥⊥z), тож робастною є емпірична версія правила 3 (відсторонення). Справді, це свідчення означає, що після закриття шляху, який йде через вершину y, буде: або між змінними x та z вже немає відкритих шляхів, або такі шляхи існують, проте всі вони слабкі. Але якщо такий шлях x–L–z виявився слабким, то подовжений (протягнутий далі) шлях x–L–z–L–y буде ще слабкішим. І тому виглядає неправ- доподібним, що змінна z – необхідна для емпіричної сепарації Pr(x⊥S⊥y). Зрозуміло, що це не строге доведення, а лише еври- стичне міркування. (Треба враховувати різні умови відповідних незалежностей). Та все ж попередній аналіз підтверджує практичну надійність емпіричної версії правила відсторонення. Моделі і засоби систем баз даних і знань 30 У процесі ідентифікації моделі ви- значаються фрагменти структури графа та окремі графові факти. Деякі факти можуть бути відомі апріорі. Тому корисно засто- совувати комбінації графових та емпірич- них свідчень. Але при цьому треба дотри- муватись певних застережень. Більшість відомих алгоритмів виведення структури з даних спочатку ідентифікує всі ребра, а вже потім орієнтує їх. Наявність шляху між x та y в неорієнтованому графі не є підставою для твердження про існування ланцюга між x та y. Для вилучення корект- них графових фактів з незавершеного графа треба враховувати стратегію алгоритма виведення структури моделі. Якщо алгоритм стартує з повного графа і послідовно видаляє зайві ребра (як це робить алгоритм ‘РС’), то можна зчитувати з поточного графа свідоцтва про модель у формі Ds(x⊥⊥y), але забо- роняється зчитувати факти у формі ¬Ds(x⊥⊥y). Якщо ж алгоритм стартує з пустого графа і послідовно вставляє необхідні ребра, то все буде навпаки: зчитування фактів ¬Ds(x⊥⊥y) буде коректним для моделі, а фактів Ds(x⊥⊥y) – некоректним. Висновки Запропоновано і обґрунтовано твердження та правила, які дозволяють адаптивно оптимізувати пошук сепара- торів у процесі виведення структур АОГ- моделей (зокрема, баєсівських мереж та гібридних моделей з будь-якою формою параметризації) з статистичних даних. Ці правила: • забезпечують виявлення мінімальних сепараторів; • сприятимуть більш ранньому скоро- ченню списка кандидатів у сепаратор і зменшенню кількості необхідних тестів; • спрощують і прискорюють ідентифіка- цію деяких ребер (або їх відсутності); • підтримують використання апріорних знань про структуру. Отже, ми показали нові можливості і техніку підвищення ефективності і надійності методів та алгоритмів індук- тивного відтворення структур ймовір- нісних моделей залежностей. 1. Pearl J. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. – San Mateo: Morgan Kaufmann, 1988. 2. Pearl J. Causality: Models, Reasoning, and Inference. – Cambridge Univ. Press, 2000. – 526 p. 3. Spirtes P., Glymour C., Scheines R. Causa- tion, prediction and search. 2-nd Ed., New York: MIT Press, 2001. – 496 p. 4. Scheines R., Spirtes P., Glymour C., Meek C., Richardson T. The TETRAD Project: Con- straint Based Aids to Causal Model Specifi- cation // Multivariate Behavioral Research, 1998. – 33 (1) – P. 65 – 118. 5. Neapolitan R.E. Learning Bayesian Net- works. – Prentice Hall, 2003. – 674 p. 6. Андон Ф.И., Балабанов А.С. Структурные статистические модели: инструмент познания и моделирования // Системні дослідження та інформаційні технології. – 2007. – № 1. – С. 79 – 98. 7. Балабанов A.C. К выводу структур моде- лей вероятностных зависимостей из ста- тистических данных // Кибернетика и сис- темный анализ. – 2005. – № 5. – С. 19 – 31. 8. Балабанов А.С. Выделение знаний из баз данных: передовые компьютерные техно- логии интеллектуального анализа данных // Математические машины и системы. – 2001. – № 1/2. – С. 40 – 54. 9. Burnell L., Horvitz E. Structure and chance: melding logic and probability for software debugging // Communications of the ACM. – 1995 – 38, Issue 3. – P. 31 – 41. 10. Nefian A., Liang L., Pi X., Liu X., Murphy K. Dynamic Bayesian Networks for Audio- Visual Speech Recognition // EURASIP, J. of Applied Signal Processing. – 2002. – 11 – P. 1 – 15. 11. Using Bayesian Network to Analyze Expres- sion Data / N. Friedman, M. Linial, I. Nachman, and D. Pe'er // J. Computational Biology. – 2000. – 7 – P. 601 – 620. 12. Kennett R.J., Korb K.B., Nicholson A.E. Sea- breeze Prediction Using Bayesian Networks // Lecture Notes in Computer Science, Vol. 2035/2001. –Berlin/Heidelberg: Springer: 2001. 13. Bessler D.A. On World Poverty: Its Causes and Effects. – Food and Agricultural Organi- zation (FAO) of the United Nations. – Research Bulletin. – Rome. – 2003. – 50 p. Моделі і засоби систем баз даних і знань 31 14. Chickering D.M., Meek C., Heckerman D. Large-Sample Learning of Bayesian Networks is NP-Hard. / In: Proceedings of 19th Conf. on Uncertainty in Artificial Intelligence. Acapulco, Mexico. – Morgan Kaufmann. – 2003. – P. 124 – 133. 15. Dawid A.P. Conditional independence in sta- tistical theory (with discussion) // J. of Roy. Statist. Soc. – 1979. – 41-B. – P. 1 – 31. 16. Verma T., Pearl J. Causal Networks: Seman- tics and Expressiveness. / in: R. Shachter, T.S. Levitt, L.N. Kanal (Eds.), Uncertainty in Artificial Intelligence. – 4 – Elsevier Science Publishers, North-Holland, Amsterdam, 1990. – P. 69 – 76. 17. Балабанов A.C. Восстановление структур систем вероятностных зависимостей из данных. Аппарат генотипов переменных // Проблемы управления и информатики. – 2003. – № 2. – C. 91 – 99. 18. Балабанов O.C. Дослідження шляхів підвищення обчислювальної ефективності методів ідентифікації моделей залежно- стей. – Звіт з НДР, Шифр 3/01К.02-02. – К., Iнститут програмних систем НАН України, 2005. – 36 с. Отримано 19.09.2007 Про автора: Балабанов Олександр Степанович, старший науковий співробітник, кандидат технічних наук. Місце роботи: Інститут програмних систем НАН України, 03187, Київ-187, проспект Академіка Глушкова, 40. факс: (38044) 526 6263 ; Тел.: (044) 526 6249. Е-mail: bas@isofts.kiev.ua
id	nasplib_isofts_kiev_ua-123456789-271
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	1727-4907
language	Ukrainian
last_indexed	2025-12-01T11:15:07Z
publishDate	2007
publisher	Інститут програмних систем НАН України
record_format	dspace
spelling	Балабанов, О.С. 2008-02-19T13:32:27Z 2008-02-19T13:32:27Z 2007 Правила підбору сепараторів у баєсівських мережах / О.С. Балабанов // Пробл. програмув. — 2007. — N 4. — С. 21-31. — Бібліогр.: 18 назв. — укр. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/271 007:681.3.00 Запропоновано і обґрунтовано набір тверджень та правил, які допомагають знаходити мінімальні за розмірами сепаратори в моделях ймовірнісних залежностей, структурованих як ациклічні орієнтовані графи (тобто в баєсівських, гаусових та гібридних мережах). Правила призначені для методів виведення структури моделі з даних за допомогою знаходження сепараторів (тобто виявлення умовної незалежності змінних). Ми сформулювали необхідні вимоги до членів мінімальних сепараторів, виходячи з критерію d-сепарації та властивостей ациклічних орграфів. Ці вимоги та правила дозволяють відсіяти деякі кандидати у сепаратор і спростити задачу пошуку сепараторів, а, також, і задачу ідентифікації структури моделі залежностей. uk Інститут програмних систем НАН України Моделі і засоби систем баз даних і знань Правила підбору сепараторів у баєсівських мережах Article published earlier
spellingShingle	Правила підбору сепараторів у баєсівських мережах Балабанов, О.С. Моделі і засоби систем баз даних і знань
title	Правила підбору сепараторів у баєсівських мережах
title_full	Правила підбору сепараторів у баєсівських мережах
title_fullStr	Правила підбору сепараторів у баєсівських мережах
title_full_unstemmed	Правила підбору сепараторів у баєсівських мережах
title_short	Правила підбору сепараторів у баєсівських мережах
title_sort	правила підбору сепараторів у баєсівських мережах
topic	Моделі і засоби систем баз даних і знань
topic_facet	Моделі і засоби систем баз даних і знань
url	https://nasplib.isofts.kiev.ua/handle/123456789/271
work_keys_str_mv	AT balabanovos pravilapídboruseparatorívubaêsívsʹkihmerežah

Правила підбору сепараторів у баєсівських мережах

Institution

Similar Items