Principles and analytical tools for reconstruction of probabilistic dependency structures in special class

Principles and analytical tools for reconstruction of probabilistic dependency structures in special class

We examine a problem of reconstruction of dependency structure from data. It is assumed that model structure belongs to class of "mono-flow" graphs, which is a subclass of acyclonic digraph (known as DAGs) and is super-class relatively to the poly-trees. Properties of the mono-flow depende...

Повний опис

Збережено в:
Бібліографічні деталі
Дата:2018
Автор: Balabanov, O.S.
Формат: Стаття
Мова:Ukrainian
Опубліковано: Інститут програмних систем НАН України 2018
Теми:
dependence structure recovery
mono-flow graph
unconditional dependence
empirical manifestation of dependence
empirical resolutions of edge identification
UDC 004.855:519.216
Онлайн доступ:https://pp.isofts.kiev.ua/index.php/ojs1/article/view/225
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Problems in programming
Завантажити файл: Pdf

Репозитарії

Problems in programming
id pp_isofts_kiev_ua-article-225
record_format ojs
resource_txt_mv ppisoftskievua/7e/1c5a90d1c4ab0d7348ca3af506bb477e.pdf
spelling pp_isofts_kiev_ua-article-2252024-04-28T11:56:41Z Principles and analytical tools for reconstruction of probabilistic dependency structures in special class Принципы и аналитические средства реконструкции структур вероятностных зависимостей в специальном классе Принципи та аналітичні засоби реконструкції структур ймовірнісних залежностей у спеціальному класі Balabanov, O.S. dependence structure recovery; mono-flow graph; unconditional dependence; empirical manifestation of dependence; empirical resolutions of edge identification UDC 004.855:519.216 восстановление структуры зависимостей; монопотоковый граф; безусловная зависимость; эмпирическое проявление зависимостей; эмпирические резолюции идентификации ребер УДК 004.855:519.216 відтворення структури залежностей; монопотоковий граф; безумовна залежність; емпіричне проявлення залежностей; емпіричні резолюції ідентифікації ребер УДК 004.855:519.216 We examine a problem of reconstruction of dependency structure from data. It is assumed that model structure belongs to class of "mono-flow" graphs, which is a subclass of acyclonic digraph (known as DAGs) and is super-class relatively to the poly-trees. Properties of the mono-flow dependency models are examined, especially in terms of patterns of unconditional dependencies and mutual information. We characterize the twin-association evolving among two variables. Specialized methods of inference of mono-flow dependency model are briefly reviewed. To justify correctness of model recovery from data we formulate an assumption of unconditional (marginal) edge-wise faithfulness, perhaps the most reliable one among all simple versions of Causal faithfulness assumption. On the basis of the assumption and the properties of mono-flow dependency models we derive several empirical resolutions for edge identification, which make use 2-placed statistics only. A lot of experiments with artificial data have demonstrated efficiency of the resolutions in that they correctly recover many edges and commit low error rate.Problems in programming 2017; 1: 97-110 Предложен и обоснован набор эмпирических резолюций, которые опираются исключительно на безусловные зависимости двух переменных и обеспечивают идентификацию непосредственных связей (ребер) в структурах зависимостей в классе монопотоковых графов. Этот класс структур является подклассом ациклонных орграфов и суперклассом для поли-лесов. Охарактеризованы свойства монопотоковых моделей. Корректность разработанных эмпирических резолюций основывается на эмпирически надежном предположении безусловной (маргинальной) реберной необманчивости.Problems in programming 2017; 1: 97-110 Запропоновано та обґрунтовано набір емпіричних резолюції, які спираються виключно на безумовні залежності двох змінних та забезпечують ідентифікацію безпосередніх зв’язків (ребер) у структурах залежностей в класі монопотокових графів. Цей клас структур є підкласом ациклонних орграфів та  суперкласом для полі-лісів. Охарактеризовано властивості монопотокових моделей. Коректність розроблених емпіричних резолюцій ґрунтується на емпірично надійному припущенні безумовної (маргінальної) реберної неоманливості.Problems in programming 2017; 1: 97-110 Інститут програмних систем НАН України 2018-11-20 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/225 10.15407/pp2017.01.097 PROBLEMS IN PROGRAMMING; No 1 (2017); 97-110 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 1 (2017); 97-110 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 1 (2017); 97-110 1727-4907 10.15407/pp2017.01 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/225/220 Copyright (c) 2018 ПРОБЛЕМИ ПРОГРАМУВАННЯ
institution Problems in programming
baseUrl_str https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date 2024-04-28T11:56:41Z
collection OJS
language Ukrainian
topic dependence structure recovery
mono-flow graph
unconditional dependence
empirical manifestation of dependence
empirical resolutions of edge identification
UDC 004.855:519.216
spellingShingle dependence structure recovery
mono-flow graph
unconditional dependence
empirical manifestation of dependence
empirical resolutions of edge identification
UDC 004.855:519.216
Balabanov, O.S.
Principles and analytical tools for reconstruction of probabilistic dependency structures in special class
topic_facet dependence structure recovery
mono-flow graph
unconditional dependence
empirical manifestation of dependence
empirical resolutions of edge identification
UDC 004.855:519.216
восстановление структуры зависимостей
монопотоковый граф
безусловная зависимость
эмпирическое проявление зависимостей
эмпирические резолюции идентификации ребер
УДК 004.855:519.216
відтворення структури залежностей
монопотоковий граф
безумовна залежність
емпіричне проявлення залежностей
емпіричні резолюції ідентифікації ребер
УДК 004.855:519.216
format Article
author Balabanov, O.S.
author_facet Balabanov, O.S.
author_sort Balabanov, O.S.
title Principles and analytical tools for reconstruction of probabilistic dependency structures in special class
title_short Principles and analytical tools for reconstruction of probabilistic dependency structures in special class
title_full Principles and analytical tools for reconstruction of probabilistic dependency structures in special class
title_fullStr Principles and analytical tools for reconstruction of probabilistic dependency structures in special class
title_full_unstemmed Principles and analytical tools for reconstruction of probabilistic dependency structures in special class
title_sort principles and analytical tools for reconstruction of probabilistic dependency structures in special class
title_alt Принципы и аналитические средства реконструкции структур вероятностных зависимостей в специальном классе
Принципи та аналітичні засоби реконструкції структур ймовірнісних залежностей у спеціальному класі
description We examine a problem of reconstruction of dependency structure from data. It is assumed that model structure belongs to class of "mono-flow" graphs, which is a subclass of acyclonic digraph (known as DAGs) and is super-class relatively to the poly-trees. Properties of the mono-flow dependency models are examined, especially in terms of patterns of unconditional dependencies and mutual information. We characterize the twin-association evolving among two variables. Specialized methods of inference of mono-flow dependency model are briefly reviewed. To justify correctness of model recovery from data we formulate an assumption of unconditional (marginal) edge-wise faithfulness, perhaps the most reliable one among all simple versions of Causal faithfulness assumption. On the basis of the assumption and the properties of mono-flow dependency models we derive several empirical resolutions for edge identification, which make use 2-placed statistics only. A lot of experiments with artificial data have demonstrated efficiency of the resolutions in that they correctly recover many edges and commit low error rate.Problems in programming 2017; 1: 97-110
publisher Інститут програмних систем НАН України
publishDate 2018
url https://pp.isofts.kiev.ua/index.php/ojs1/article/view/225
work_keys_str_mv AT balabanovos principlesandanalyticaltoolsforreconstructionofprobabilisticdependencystructuresinspecialclass
AT balabanovos principyianalitičeskiesredstvarekonstrukciistrukturveroâtnostnyhzavisimostejvspecialʹnomklasse
AT balabanovos principitaanalítičnízasobirekonstrukcíístrukturjmovírnísnihzaležnostejuspecíalʹnomuklasí
first_indexed 2024-09-16T04:08:19Z
last_indexed 2024-09-16T04:08:19Z
_version_ 1818568188273623040
fulltext Математичне моделювання об’єктів та процесів © О.С. Балабанов, 2017 ISSN 1727-4907. Проблеми програмування. 2017. № 1 97 УДК 004.855:519.216 О.С. Балабанов ПРИНЦИПИ ТА АНАЛІТИЧНІ ЗАСОБИ РЕКОНСТРУКЦІЇ СТРУКТУР ЙМОВІРНІСНИХ ЗАЛЕЖНОСТЕЙ У СПЕЦІАЛЬНОМУ КЛАСІ Запропоновано та обґрунтовано набір емпіричних резолюції, які спираються виключно на безумовні залежності двох змінних та забезпечують ідентифікацію безпосередніх зв’язків (ребер) у структурах за- лежностей в класі монопотокових графів. Цей клас структур є підкласом ациклонних орграфів та суперкласом для полі-лісів. Охарактеризовано властивості монопотокових моделей. Коректність роз- роблених емпіричних резолюцій ґрунтується на емпірично надійному припущенні безумовної (маргі- нальної) реберної неоманливості. Ключові слова: відтворення структури залежностей, монопотоковий граф, безумовна залежність, емпі- ричне проявлення залежностей, емпіричні резолюції ідентифікації ребер. Вступ Відтворення структур зв’язків та впливів між характеристиками середови- ща, які неявно відбиті в багатовимірних масивах статистичних даних – одна з цен- тральних задач глибокого аналізу даних та відкриття знань у базах даних. Хоча за останню чверть століття отримано багато результатів для розв’язання цієї важкої задачі, інтенсивні дослідження й розробки тривають [1–5]. Найбільш важка постано- вка задачі постає в ситуації, коли на стру- ктуру ймовірнісних залежностей не на- кладено жодних обмежень і зовсім нічого не відомо про цю структуру. Зазвичай пе- редбачається єдине обмеження – в струк- турі немає орієнтованих циклів (цикло- нів). Відсутність циклонів можна вважати вимогою коректного збору даних. Тобто в процесі генерації одного запису даних кожна змінна X вимірюється досить швидко, так що «сигнал» від X до інших змінних не може встигнути «оббігти ко- ло» й вплинути на X у цьому записі. Структури ймовірнісних залежностей, де заборонено циклони, об’єднуються в клас ациклонних орієнтованих графів (АОГ). Задача відтворення автентичної (генера- тивної) АОГ-структури за відсутності ап- ріорних знань у найгіршому випадку є експоненційно важкою [4, 5]. Натомість якщо відомо, що структура генеративної моделі задовольняє певним «топологіч- ним» обмеженням, то відтворення такої структури значно спрощується. Для різ- них спеціальних класів структур й моде- лей розроблено спеціалізовані методи від- творення моделі. Коли генеративна мо- дель дійсно належить обраному класу, то така задача характеризується як реконст- рукція (відтворення) моделі. Коли генера- тивна модель виходить за межі обраного класу, то задачу називають «редукція» (структурна апроксимація, «покриття») моделі. В статті розглянуто постановку, коли відомо, що структура моделі нале- жить до класу монопотокових графів за- лежностей. Строго обґрунтовано нові за- соби вдосконалення методів реконструк- ції моделей у цьому класі. Характеристика монопотокових моделей залежностей та огляд методів їх відтворення Ребро відображає безпосередній зв’язок між двома змінними (вершинами). В більшості практичних задач працюють з моделями в підкласі ациклонних орієнто- ваних графів, де всі ребра є одно- орієнтовані (тобто мають вигляд YX  ). На основі таких графів (задавши парамет- ри локальних залежностей) утворюється клас ординарних АОГ-моделей (оАОГ- моделей), у тому числі байєсові та гауссо- ві мережі [1, 3, 6, 7]. Спеціальні підкласи оАОГ-моделей визначаються певними «топологічними» обмеженнями на струк- туру (вводиться заборона циклів або шля- Математичне моделювання об’єктів та процесів 98 хів певних типів). Нагадаємо необхідні графові поняття. Ребро зображується як неорієнтова- не X — ,Y коли орієнтація цього ребра є невідома або несуттєва в даному контексті. Цикл у графі – це шлях з ребер ,XYX  де всі проміжні (некін- цеві) вершини – різні, а кінцеві вершини – тотожні. Колізор – це шлях вигляду ZYX  . Ланцюг – це шлях, на якому немає жодного колізора. Оршлях – це лан- цюг вигляду YZX  . Циклон – це оршлях, де остання вершина збігаєть- ся з першою. Мабуть найбільш відомим підкла- сом оАОГ є ліси залежностей. В лісі (де- реві) залежностей немає ані циклів, ані колізорів. Його розширенням є полі-ліси; в них заборонені цикли (а колізори – до- зволені). Ліси й полі-ліси підтримують прості паттерни залежностей, недостатні для моделювання багатьох об’єктів. Про- міжне місце між полі-лісами та загальним випадком оАОГ посідає клас так званих монопотокових графів залежностей (МПГЗ). Моделі на базі МПГЗ можуть ма- ти цикли і є значно експресивнішими за полі-ліси. (В літературі вони називалися простими або спрощеними оАОГ). Аксіо- ми та властивості МПГЗ-моделей описані в [6, 7]. Можна дати кілька еквівалентних варіантів визначення МПГЗ: 1) якщо в МПГЗ існує ланцюг YQX  або ребро X — ,Y то між вершинами X та Y не існує жодного ін- шого ланцюга; 2) між батьками однієї й тієї ж вер- шини в МПГЗ немає жодного ланцюга; 3) в МПГЗ неможливий цикл з од- ним колізором. Наслідками визначення є властиво- сті МПГЗ. Властивість 1: якщо в МПГЗ між вершинами X та Y існує більше одного ланцюга, то серед тих ланцюгів немає жо- дного оршляху, тобто всі ті ланцюги ма- ють вигляд YX  . Візьмемо довіль- но два таких ланцюга  та  . На ланцю- гах  та  є змінні відповідно Q та ,R такі, що між Q та R не існує жодного ла- нцюга. Властивість 2: якщо в МПГЗ між вершинами X та Y існують різні ланцю- ги  та  , з тим, що вони проходять че- рез спільну вершину Q , яка не тотожна ані ,X ані ,Y то тоді ланцюги  та  закінчуються спільною дугою LX  або (та) спільною дугою YR . (Можливо, що LQ  або RQ  ). Сенс цієї властивості: коли в МПГЗ кілька ланцюгів між X та Y «зійшлися», вони вже не можуть розійтися (розділити- ся), бо це породило б одноколізорний цикл. Залежність між змінними забезпе- чується неблокованим шляхом між змін- ними. Змінні X та Y є безумовно залеж- ні тоді й тільки тоді, якщо між X та Y існує хоча б один ланцюг. Марковські вла- стивості класу оАОГ-моделей визначають- ся критерієм d-сепарації [1, 3, 6, 8]. Кож- ному факту d-сепарації відповідає умовна незалежність. Процедурі перевірки факту d-сепарації можна зіставити статистичний тест незалежності. Ранг тесту незалежності визначається кількістю змінних в умові тесту. (Тест безумовної незалежності має нульовий ранг). Відомим показником тісноти (си- ли) залежності між дискретними змінни- ми X та Y є взаємна інформація (за Шенноном). Безумовну взаємну інформа- цію позначимо ),Info( YX . Елементарний наслідок марковської властивості форму- люється наступним чином. Якщо дана умовна незалежність X та Y за умови на Q , то буде ),Info( YX ),Info( QX та ),Info( YX ),Info( QY . Безумовну залежність також нази- вають асоціацією. Наступне твердження випливає з властивості 2 та критерія d-сепарації. Властивість 3. Якщо в МПГЗ- моделі всі ланцюги між змінними X та Y взаємно перетинаються на одній змінній Математичне моделювання об’єктів та процесів 99 Q , то буде ),Info( YX ),Info( QX й ),Info( YX ),Info( YQ . З властивостей 2 та 3 випливає Властивість 4. Якщо в МПГЗ- моделі для заданої пари асоційованих змінних ( X ,Y ) немає жодної змінної Q такої, що ),Info( QX ),Info( YX та ),Info( YQ ),Info( YX , то не існує такої змінної, через яку прохо- дили б усі ланцюги між X та .Y Властивість 5. Якщо в МПГЗ- моделі між змінними X та Y існує єди- ний ланцюг, то для кожного ребра Q — R на цьому ланцюзі буде ),Info( YX ),Info( RQ . Визначення 1. В МПГЗ-моделі асоціація між змінними X та Y назива- ється обманною нереберною, якщо немає ребра X —Y і якщо на кожному ланцюзі між X та Y існує щонайменше одне реб- ро R — Z таке, що ),Info( ZR ),Info( YX . Визначення 2. В МПГЗ-моделі асоціація між змінними X та Y назива- ється двійниковою, якщо вона обманна не- реберна і якщо не існує змінної Q , яка се- парує X та .Y Кожна обманна нереберна асоціація між X та Y або є двійниковою, або утво- рена конкатенацією двійникової асоціації з оршляхом. (В другому випадку всі ланцю- ги між X та Y проходять через певну спільну вершину (вершини)). Зрозуміло, що задача відтворення моделі з даних стає найпростішою, коли відомо, що генеративна модель належить класу лісів або полі-лісів. Для лісів є відомий алгоритм квадратичної складнос- ті, запропонований C. Chow та C. Liu [9, 10]. Принцип алгоритму Chow&Liu – встановлення ребер у порядку зменшення міцності залежностей. Збагативши цей алгоритм засобами орієнтації ребер, мож- на отримати завершений алгоритм відтво- рення полі-лісів залежностей з даних. (Варіант такого алгоритму – ‘SpaPolyTree’ [6]). Моделі в класі лісів або полі-лісів можна відтворювати також методами, ос- нованими на тестах незалежності. Для цього потрібні тести тільки нульового та першого рангів. (Прототипи таких алго- ритмів – процедури ‘Branch’ («Гілка») та ‘PolyForesyn’ [6]). Отже, є принциповий розрив між двома групами методів відтворення стру- ктури моделі з даних. Маємо елементарні спеціалізовані методи для однозв’язаних структур (якими є полі-ліси); і маємо уні- версальні комбінаторні методи для всього класу оАОГ-моделей. Втім, як показано в [11], можна надати універсальному мето- ду здатності автоматично розпізнавати той факт, що генеративна модель є полі- лісом, і в такому разі наближатися до спе- ціалізованих методів за обчислювальними витратами. Задача реконструкції моделі в класі монопотокових графів залежностей потре- бує нестандартних рішень. Відтворювати МПГЗ за допомогою універсальних мето- дів – вкрай нерозумно. Водночас елемен- тарні методи не працюють, бо в МПГЗ іс- нують цикли, а сепаратори можуть бути великорозмірними, як і в довільних оАОГ. Запропоновано кілька високоспеці- алізованих алгоритмів реконструкції МПГЗ, які базуються на особливостях монопотокових графів. Перший алгоритм реконструкції МПГЗ, описаний в [12], логічно простий і потребує малої кількос- ті тестів. Питання про присутність будь- якого ребра X —Y вирішується за допо- могою двох тестів. 1) тест безумовної не- залежності; 2) тест умовної незалежності X та ,Y причому в умову включено всі змінні, окрім X та .Y Це призводить до тестів умовної незалежності високого ра- нгу, які є ненадійними. Отже, і сам алго- ритм має низьку надійність. Уявимо, що змінних багато і що в генеративній моделі ребра X —Y немає, але взаємозалеж- ність змінних X та Y – сильна. Тоді (на- віть за використання вибірки даних реалі- стичного обсягу) тест умовної незалежно- сті може помилково не виявити незалеж- ність (з огляду на складний формат). Тож Математичне моделювання об’єктів та процесів 100 буде поставлене помилкове ребро. Зазна- чимо, що сильна безумовна залежність може виникати, коли змінні пов’язані ла- нцюгом з двох ребер, або коли між змін- ними є двійникова асоціація. Згодом з’ясовано, що для відтво- рення монопотокових моделей достатньо спиратися на тести нульового та першого рангу [13–15]. Методи серії «Генеалогія», зокрема, алгоритм «Генеалог-2», описа- ний в [16], та більш досконалий алгоритм «Генеалог-С» [6] – непридатні для стан- дартних обставин, бо потребують розпі- знавання слабких безумовних залежнос- тей, у тому числі тих, що утворені довги- ми ланцюгами [6, 17]. Метод CH1, описа- ний в [13], для кожної пари залежних змінних виконує всі можливі тести пер- шого рангу. Це призводить до надто вели- кої кількості тестів. Можна уникнути цьо- го недоліку, якщо змінити головний принцип методу, а саме, перейти від по- шуку сепаратора до використання прово- кації залежності [14, 15, 17]. Замість інте- нсивного пошуку спростування ребра мо- жна знаходити підтвердження присутнос- ті ребра. Феномен провокованої залежності полягає у наступному [18]. Якщо змінні X та Z – взаємонезалежні, і вони разом впливають на змінну Y , то кондиціону- вання змінної Y зазвичай породжує за- лежність між X та Z . Тобто в результаті введення умови на змінну Y виникає умовна залежність між X та Z . Згідно результатів стохастичної симуляції дис- кретних моделей, сила (рівень) провоко- ваної залежності в середньостатистично- му сенсі приблизно дорівнює силі маргі- нальної (реберної) залежності між Y та змінною X або Z . На провоковану за- лежність припадає біля 31 повної «ро- динної» інформації колізора [18]. Прово- кована залежність може колапсувати (не виникати) тільки в особливих випадках у дискретних моделях. Позначимо як )|,Ind( SYX факт умовної незалежності змінних X та Y за умови S . Факт умовної залежності ви- ражається як )|,Ind(~ SYX . Безумовна незалежність та залежність позначаються відповідно ),Ind( YX та ),Ind(~ YX . Тео- ретично провокована залежність визнача- ється як сполучення (паттерн) ),Ind( ZX & & )|,Ind(~ YZX . Оскільки в МПГЗ, згідно їх визначення, в кожному колізорі ZYX  змінні X та Z – взаємо- незалежні, то на базі кожного колізора має породжуватися провокована залеж- ність. В групі методів, що спираються на інструмент провокованих залежностей, найбільш ефективним можна вважати ал- горитм «Proliferator-D» [6, 17]. За заду- мом, цей алгоритм оминає тести сепара- ції, але виконує тести провокації. Виве- дення структури МПГЗ-моделі виконуєть- ся в два основні етапи. На першому етапі обчислюються всі парні асоціації та іден- тифікуються всі провоковані залежності. Для уникнення зайвої роботи провокація залежності виконується тільки за наявно- сті передумов – коли трійка змінних утво- рює квазі-колізорний паттерн. На другому етапі алгоритм конструює структуру мо- делі, спираючись, зокрема, на принцип Chow&Liu. При цьому (за достатніх підс- тав) відразу встановлюються орієнтовані ребра. Хоча алгоритм «Proliferator-D» пе- реважає своїх попередників, ретельний аналіз показує, що він теж недосконалий й часто виконує необов’язкові обчислен- ня. «Proliferator-D» є алгоритмом суб- кубічної складності. Але в багатьох не- тривіальних випадках МПГЗ-модель мо- жна відтворити, виконавши роботу ліній- ної складності. Потужним резервом під- силення методів відтворення структури моделі є правила мінімальної сепарації [6, 8]. Більшість цих правил виведено для всього класу оАОГ-моделей, але декілька створено спеціально для МПГЗ-моделей [6]. Правила мінімальної сепарації обґру- нтовані в апараті графів, а для обґрунту- вання емпіричних еквівалентів («зліпків») цих правил необхідні відповідні форми припущення каузальної неоманливості [6]. Ті форми припущення неоманливості можна оцінити як недостатньо надійні, тож й аргументація ефективності правил мінімальної сепарації може сприйматися як непереконлива. В даній роботі пропо- нується більш переконливий шлях гаран- Математичне моделювання об’єктів та процесів 101 тування надійності відтворення моделі з даних. Спочатку формулюються найбільш надійні припущення про емпіричні (ста- тистично-ймовірнісні) прояви залежнос- тей, а потім на базі цих припущень буду- ються емпіричні резолюції та засоби для методів відтворення МПГЗ. Базові припущення та інструментарій Статистична залежність може бути слабкою. У ході аналізу реалістичних да- них статистичний тест може відрізнити залежність від незалежності тільки якщо емпірична залежність досить міцна (вели- ка). Метод відтворення моделі з даних може спиратися тільки на статистично значущі залежності. Позначатимемо пре- дикатом ),Dep( YX факт значущої безумо- вної залежності між X та .Y (Домови- мося, що предикат ),Dep( XX завжди іс- тинний). Квазі-колізорна трійка змінних – це паттерн ),Dep( YX & ),Dep( YZ & ),Ind( ZX . Емпірична провокована залеж- ність – це сполучення ),Dep(~ ZX & )|,Dep( YZX . Обчислювальна складність алгори- тму ‘Proliferator-D’ в основному визнача- ється кількістю тестів провокації залеж- ності, а значить, кількістю квазі-колізор- них трійок. На рис. 1 показано приклади структур МПГЗ, які породжують велику кількість квазі-колізорних трійок. В пер- шій структурі на рис. 1, а теоретично ма- ємо 2/)2)(1(  nn квазі-колізорних трі- йок. В другій структурі на рис. 1, б ця кі- лькість менша. В третій структурі на рис. 1, в кількість квазі-колізорних трійок дорівнює )3)(2(  nn . І хоча теоретично кількість квазі-колізорних трійок не може бути вище за квадратичну від кількості змінних, у багатьох випадках ‘Proliferator- D’ буде виконувати зайву роботу. Дійсно, модель, показана на рис. 1, а, – дуже простий випадок полі-лісу й може бути тривіально відтворена на ос- нові тестів нульового рангу та логіки. Інші моделі, показані на цьому рисунку теж ре- конструюються просто. Бажано базувати метод відтворення моделі з даних на надійних припущеннях про емпіричні прояви залежностей [1, 3, 6]. Мабуть, найбільш надійним припущенням, яке можна сформулювати, є припущення безумовної (маргінальної) реберної неома- нливості (0-РНО): будь-які дві змінні, по- єднані ребром, є безумовно залежні. Фор- мально: якщо існує ( X —Y ), то буде ),Dep( YX . Рис. 1. Приклади МПГЗ: а, б – полі-ліси; в – МПГЗ з циклами 4 3 6 n n-1 5 а б в n n-1 1 2 1 2 Математичне моделювання об’єктів та процесів 102 Для МПГЗ-моделей це припущення – більш надійне, ніж для загального випа- дку оАОГ-моделей, тому що в оАОГ мо- жуть бути одночасно присутні ребро X —Y і ще якісь ланцюги між вершина- ми X та .Y (Тоді може статися взаємна компенсація залежностей). В МПГЗ таке виключено. Припущення 0-РНО є необхідним та може виявитися недостатнім для іден- тифікації всіх ребер. Тоді знадобиться за- лучити дещо складніший варіант. Припу- щення реберної неоманливості першого рангу (1-РНО): будь-які дві змінні, поєд- нані ребром, є умовно залежні, з умовою на довільну третю змінну. Можна передбачити, що надійність припущення 1-РНО також буде вище для МПГЗ-моделей, ніж для загального випа- дку оАОГ-моделей, бо в оАОГ існує бі- льше можливостей для контр-прикладів. Ризик порушення 1-РНО є досить висо- кий, зокрема, у трикутнику YX XZ  , де кондиціонування змінної Z створює провоковану залежність, яка мо- же анігілювати з залежністю, створеною ребром X —Y . Для обґрунтування здатності іден- тифікувати спрямування (орієнтацію) ре- бер потрібні додаткові припущення. Для класу МПГЗ-моделей таким може бути од- не з двох наступних припущень. Припущення безумовної каузальної неоманливості двох-реберних ланцюгів (0- Л2НО): якщо в моделі між змінними X та Z присутній якийсь ланцюг довжиною у два ребра, то буде безумовна залежність ),Dep( ZX . Іншими словами, якщо існує ланцюг ZYX  або ZYX  , то він забезпечує значущу транзитну залеж- ність між X та Z . Припущення елементарної прово- кації залежності на колізорі (ЕПЗК): якщо в моделі присутній колізор ZYX  , то буде умовна залежність )|,Dep( YZX . Для МПГЗ-моделей припущення ЕПЗК – більш надійне, ніж для загального випадку оАОГ-моделей, тому що для колізора ZYX  в складі МПГЗ-моделі змінні X та Z обов’язково взаємонезалежні (а в оАОГ – не обов’язково). (Зауважимо, що для орієнтації ре- бер в оАОГ-моделях цих припущень недо- статньо). Доцільно також зафіксувати варі- ант припущення, спрощений відносно 0-Л2НО. Припущення безумовної каузаль- ної неоманливості елементарних двох- реберних ланцюгів (0-ЕЛ2НО): якщо в мо- делі між змінними X та Z присутній один й тільки один ланцюг довжиною у два ребра, то буде безумовна залежність ),Dep( ZX . Можна очікувати, що це при- пущення – більш надійне, ніж 0-Л2НО, оскільки воно уникає ситуацій з певними ускладненнями. Варто зазначити, що усі методи від- творення моделі з даних постулюють (за замовчуванням) наступне припущення: будь-які дві змінні, не поєднані жодним ланцюгом (ребром), тестуються як безумо- вно незалежні. (Звісно, статистичні тести мають ризики помилок, оцінювані значен- ням p-value). Визначення 3. Набір близьких до змінної X визначається як )Clo(X  ),Dep(| YXY , тобто як множина всіх тих змінних, які безумовно залежать від X (включаючи саму X ). Тривіально }{)Clo( XX  . Згідно припущення 0-РНО, якщо існує X — ,Y то )Clo(XY  . Якщо вершина X дотична до k ребер, то )1(|)Clo(|  kX . Висока ефективність згаданих ви- ще алгоритмів відтворення лісів та полі- лісів завдячує принципу Chow&Liu (який повторює відомий алгоритм Крускала). Коректність принципу Chow&Liu для по- лі-лісів забезпечується відсутністю циклів у структурі. На жаль, цей принцип не є коректним для МПГЗ-моделей в загаль- ному випадку (бо в МПГЗ може бути кі- лька паралельних ланцюгів). Встановлен- ня ребер в МПГЗ-моделі за принципом Chow&Liu призводить до помилок у пев- них ситуаціях [6, 7]. Виконання алгорит- му Chow&Liu призведе до встановлення ребра на місці двійникової чи обманної нереберної асоціації (а певне автентичне ребро буде втрачене) [6, 7, 17]. Тому для використання принципу Chow&Liu необ- Математичне моделювання об’єктів та процесів 103 хідно озброїти метод відтворення МПГЗ- моделей засобами розпізнавання двійни- кових асоціацій. Далі буде показано, як можна ідентифікувати багато ребер у МПГЗ-моделях на основі систематичного аналізу сукупності безумовних залежнос- тей. Коректність пропонованих засобів ґрунтується на найбільш надійному при- пущенні – безумовної (маргінальної) ре- берної неоманливості (0-РНО). Для коре- ктності резолюцій, які вдаються до прин- ципу Chow&Liu, потрібне також припу- щення монотонності залежності на ма- рковському ланцюзі. Формулювання: як- що маємо ),Dep( YX , ),Dep( ZY та )|,Ind( YZX , то чинне ),Info( ZX )},Info(),,min{Info( ZYYX . Останнє припущення та припущен- ня 0-РНО не поглинають один одного. (Властивість 3 треба розуміти в асимпто- тичному сенсі). Емпіричні резолюції ідентифікації ребер в МПГЗ-моделях З визначення двійникової асоціації та властивості 4 випливає наступний факт. Факт 1. Якщо для МПГЗ-моделі асоціація між змінними X та Y – «двій- никова», то 4|)Clo(| X та 4|)Clo(| Y . З властивостей 1 та 5 випливає на- ступний факт. Факт 2. Якщо в МПГЗ-моделі асо- ціація між змінними X та Y – двійнико- ва, то між вершинами X та Y існує не менше двох ланцюгів  та  таких, що кожна некінцева змінні на ланцюзі  не- залежна від кожної некінцевої змінної на ланцюзі  . Наслідок. Якщо для МПГЗ-моделі маємо )Clo( XY  і серед змінних, що входять до )Clo( X , або серед змінних, що входять до )Clo(Y , немає принаймні двох взаємонезалежних, то асоціація між X та Y не може бути двійниковою. Якщо спиратися виключно на при- пущення 0-РНО, то серед усіх виведених [6, 8] правил мінімальної сепарації можна транслювати в емпіричну форму тільки одне. Це правило єдиного родича, або безальтернативного ребра [6] (воно чинне для всього класу оАОГ-моделей). В емпі- ричній формі воно формулюється наступ- ним чином. Резолюція єдиного близького. Якщо в оАОГ-моделі маємо },{)Clo( YXX  , то існує ребро X — .Y Для класу МПГЗ-моделей є чинним більш сильний результат. Резолюція перемички (відсутність спільної суміжної). Нехай для МПГЗ- моделі маємо )Clo(XY  та     }{\)Clo(}{\)Clo( YYXX Ø. Тоді, якщо 3|)Clo(| X або 3|)Clo(| Y , то в мо- делі присутнє ребро X — .Y Інакше (тоб- то якщо 3|)Clo(| X та 3|)Clo(| Y ) є дві можливі альтернативи: а) в моделі присутнє ребро X — ,Y або б) всі шляхи між X та Y є ланцю- гами, з тим, що кожний ланцюг між X та Y має не менше трьох ребер, і існує не менше двох таких ланцюгів. Ясно, що альтернатива «б» імплікує існування двійникової асоціації. З умови « )Clo(XY  та     }{\)Clo(}{\)Clo( YYXX Ø» випли- ває (властивість 3 та 4), що не існує такої змінної Z , що всі ланцюги між X та Y перетинаються на Z . Якщо немає ребра X — ,Y то між X та Y існує не менше двох ланцюгів (властивість 5). Якби як- ийсь ланцюг між X та Y мав два ребра YQX  , то згідно припущення 0-РНО було б )Clo(XQ та )Clo(YQ . Резолюція кінцевого двох-реберного ланцюга. Нехай для МПГЗ-моделі маємо },,{)Clo()Clo( ZYXYX  . Тоді змінні ZYX ,, поєднані в генеративній моделі двома ребрами, які утворюють ланцюг й ідентифікуються згідно принципу Chow&Liu. Доведення. Якби якісь дві змінні з трьох ZYX ,, були поєднані через лан- цюг, який проходить через якусь четверту Математичне моделювання об’єктів та процесів 104 змінну W , то було б )Clo(XW  або )Clo(YW  , що суперечить умовам. Якби змінні ZYX ,, були поєднані як колізор, то дві з них були б взаємонезалежні, що суперечить умовам. Оскільки трикутник ребер в МПГЗ неможливий, отримуємо бажаний висновок. (Вказані два ребра ідентифікуються згідно властивості 5). Зауважимо, що в такій конфігурації одна з трьох змінних (в даному разі Z ) може мати «додаткові» близькі змінні, тобто можливе 3|)Clo(| Z . Об’єднуючи властивість 3 та наслі- док з факту 2, отримуємо результат. Резолюція виключення нереберної асоціації. Нехай для МПГЗ-моделі маємо )Clo(XY  , і серед змінних, що входять до },{\)Clo( YXX , або серед змінних, що входять до },{\)Clo( YXY , немає жодної пари взаємонезалежних. Тоді, якщо серед змінних, що входять до },{\)Clo( YXY , немає хоча б одної змінної Q , такої, що );Info( QX );Info( YX та ),Info( YQ ),Info( YX , то присутнє ребро X — .Y Об’єднавши резолюцію перемички та резолюцію виключення обманної не- реберної асоціації, отримаємо більш силь- ний результат. Резолюція перемички (об’єднана). Нехай для МПГЗ-моделі маємо )Clo(XY  і виконується  }{\)Clo( XX   }{\)Clo( YY Ø. Для ідентифікації при- сутності ребра X —Y в моделі достатнім є виконання принаймні однієї з наступних умов: а) маємо 3|)Clo(| Y або 3|)Clo(| Y ; б) серед змінних, що входять до )Clo(X немає жодних двох взаємонезале- жних; в) серед змінних, що входять до )Clo(Y , немає жодних двох взаємонезале- жних. Ідея доведення. Якби асоціація між X та Y забезпечувалася єдиним лан- цюгом або була обманною нереберною (але не двійниковою) асоціацією, то іс- нував би 1-сепаратор для пари ( X ,Y ), а тоді, не виконувалася б передумова правила. Додаткові умови («а», «б, «в») резолюції виключають існування двійникової асо- ціації. Резолюція слабкої пари ребер. Якщо для МПГЗ-моделі маємо )Clo(Y },,{ ZYX й )Clo(XZ  , то в моделі присутня пара ребер X —Y — .Z Доведення. Припустимо від проти- лежного, що ребра X —Y немає. Тоді, з огляду на умову )Clo(Y },,{ ZYX , суміж- ною до змінної Y буде тільки одна змінна Z . Отже, змінні X та Y мають поєдну- ватися ланцюгами (ланцюгом), які прохо- дять через ребро Z — .Y Тоді, згідно вла- стивості 3, буде ),Info( YX ),Info( ZX . А це разом з фактом )Clo(XY  тягне )Clo(XZ  , що суперечить умовам. З огляду на симетрію, доведення для другого ребра аналогічне. Резолюцію слабкої пари ребер мо- жна узагальнити. Резолюція центральної вершини (єдиного вузла). Нехай для МПГЗ-моделі всі змінні, що входять до складу множи- ни }{\)Clo( QQ , є взаємонезалежними. Тоді, якщо 3|)Clo(| Q або серед змінних множини }{\)Clo( QQ немає жодної такої Z , що 4|)Clo(| Z , то в моделі присутні ребра Q — X для всіх змінних }{\)Clo( QQX  . Доведення. У випадку 3|)Clo(| Q отримуємо резолюцію слабкої пари ребер. Для іншого випадку припустимо від про- тилежного, що є змінна ,W }{\)Clo( QQW  несуміжна до Q . Тоді асоціація між Q та W була б двійникова (інші варіанти нереберної асоціації відпа- дають, бо потребують існування деякої спільної близької до Q та W змінної, що суперечить умовам згідно властивості 3). Але для можливості вказаної двійникової асоціації (згідно факту 1) необхідно 4|)Clo(| W . Суперечить умовам. Резолюція крайнього трикутника асоціацій. Нехай для МПГЗ-моделі маємо Математичне моделювання об’єктів та процесів 105 },,{)Clo( ZYXX  , },,{)Clo( ZYXY  та },,{)Clo( ZYXZ  (а асоціація між Y та Z може задовольняти необхідним вимо- гам обманної нереберної асоціації). Тоді чинне: а) якщо );Info( YX );Info( ZX );Info( ZY , то в моделі присутній ланцюг Y — X — Z ; б) якщо );Info( YX );Info( ZY );Info( ZX або );Info( ZY  );Info( YX );Info( ZX , то в моделі присутнє ребро X — ,Y а питання щодо другого ребра ланцюга залишається відкритим. Нагадаємо, що кліка асоційованих змінних – це така множина змінних C , що для кожних двох її елементів CYX , чинне )Clo(XY  . Ізольована кліка – це така множина змінних C , що для кожної CX чинне C)Clo(X . Резолюція ізольованої кліки. Якщо для МПГЗ-моделі деяка підмножина змін- них C утворює ізольовану кліку, то в ге- неративній моделі підмножина змінних C поєднана деревом ребер, і це дерево повні- стю відтворюється за принципом Chow&Liu. Дійсно, якби якісь три змінні утво- рювали б колізор, то була б пара взаємно незалежних змінних. МПГЗ без колізорів – це дерево (ліс). Можна розширити резолюцію ізо- льованої кліки (і охопити резолюцію кінцевого двох-реберного ланцюга як спеціальний випадок). Введемо допоміжні поняття. Граф парних асоціацій (ГПА) для даних (генерованих з моделі з набором змінних V ) – це неорієнтований граф з вершинами V , в якому встановлене ребро X —Y для кожної пари змінних ( X ,Y ), для якої чинне ),Dep( YX , й немає ребра Q — Z для кожної пари змінних (Q , Z ), якщо чинне ),Dep(~ YX . Факт 3. Якщо в МПГЗ-моделі асо- ціація між змінними X та Y – обманна нереберна, то в ГПА існує цикл, який про- ходить через X та Y і який не входить у склад жодної кліки. Нехай дві змінні X та Y поєднані в МПГЗ двома чи більше ланцюгами і вхо- дять до деякої компоненти ГПА K . Тоді ясно, що за припущення 0-РНО компонен- та K не може бути клікою. Максимальна кліка змінних – це та- ка кліка C , що не існує жодної змінної CX такої, що }{XC теж є клікою змінних. Резолюція кліки асоціацій у дерево- видному оточенні. Нехай для МПГЗ- моделі маємо в ГПА максимальну кліку C . Далі, нехай для кожної пари змінних YX , з кліки C чинне наступне: між змін- ними X та Y немає жодного шляху в ГПА поза клікою C . Тоді в генеративній моделі всі змінні кліки C з’єднані дере- вом, яке можна ідентифікувати за принци- пом Chow&Liu. Умови резолюції формалізуються так: ,..},,{ ZYXC ; для всіх CX маємо C)Clo(X ; для будь-якої пари CYX , між X та Y не існує жодної послідовнос- ті )Clo(1 XZ  , )Clo( 12 ZZ  , ... ... , )Clo( 1 kk ZZ , …, )Clo( nZY  , де CkZ . Дійсно, якби між якимись змінни- ми CYX , в генеративній моделі існу- вало б два чи більше ланцюгів, то, згідно властивості 1, ці ланцюги не входили б в жодну кліку. Тоді був би шлях в ГПА між X та Y поза клікою C . Отже, в ге- неративній моделі в рамках множини C немає циклів, тобто всі змінні кліки C поєднані в генеративній моделі деревом. (Вимога, щоб кліка C була максималь- ною, є технічною. Якщо кліка не макси- мальна, неможливо виконати решту вимог резолюції). Можна зауважити, що більшість на- ведених резолюцій автоматично викону- ється алгоритмом Chow&Liu. Проте ці ре- золюції гарантують коректну реконструк- цію ребер (а алгоритм Chow&Liu – ні). Пропоновані резолюції значно прискорюють реконструкцію моделей, структура яких показана на рис. 1. Для випадку рис. 1, а всі ребра ідентифікують- ся резолюцією єдиного близького. Ця са- Математичне моделювання об’єктів та процесів 106 ма резолюція дозволяє відтворити ребра «нижнього ярусу» в структурі рис. 1, б (крім одного ребра). Всі ребра «верхнього ярусу» цієї структури відтворюються за допомогою резолюції крайнього трикут- ника асоціацій. Припустимо, що в моделі із структурою рис. 1, в асоціація між змінними X1 та X2 – значуща. Досить, щоб для однієї трійки змінних виконалися умови п. «а» резолюції крайнього трикут- ника асоціацій, і тоді всі ребра швидко ідентифікуються. Експериментальне випробування Продемонструємо ефективність ро- боти запропонованих резолюцій на прик- ладі. Структура генеративної моделі (в класі МПГЗ) для експерименту показана на рис. 2. Модель має 32 змінні та 37 ре- бер. Всі змінні – тризначні. Для цієї стру- ктури було генеровано (стохастичним ме- ханізмом) три варіанти параметризації, і для кожної параметризації генеровано кі- лька вибірок даних обсягом 500, 1000, 2000, 3000 та 5000 записів. Тестування безумовної незалежності виконувалось за спрощеною схемою – як порівняння взає- мної інформації з пороговим значенням. Попередній експеримент проведено для перевірки надійності тестів та припущен- ня 0-РНО. Для цього фіксувалися помил- кові рішення двох типів: 1) ідентифікація залежності змін- них, які згідно генеративної моделі є вза- ємонезалежними; 2) ідентифікація незалежності змінних, поєднаних ребром в генеративній моделі. Результати цього експерименту наведено в табл. 1. Підсумуємо результати експери- менту. В середньому для вибірки розмі- ром 500 записів і величини порогу 0,01 ризик втрати ребра досяг 13 %, а кількість помилкових залежностей дорівнює 11. Аналогічні показники для величини поро- гу 0,02 становлять 28 % та 0,17 частки за- лежності. Коли вибірка має 1000 записів або більше, не з’явилося жодної помилко- вої залежності. Для вибірки розміром 24 19 20 22 21 23 29 32 31 30 27 26 28 25 11 18 5 4 9 6 8 7 10 17 16 15 13 14 12 2 3 1 Рис. 2. Структура МПГЗ (‘MF32-37’) для експерименту Математичне моделювання об’єктів та процесів 107 Таблиця 1 Емпіричні залежності для ребер моделі Варіант парамет- ризації Розмір вибірки Поріг значущості = 0,01 Поріг значущості = 0,02 Кількість втрачених ребер Кількість помилкових залежностей Кількість втрачених ребер Кількість помилкових залежностей 1-й 500 4 12 8 0 500 5 13 8 0 500 3 10 8 0 500 4 9 10 0 1000 4 0 7 0 1000 3 0 9 0 2000 3 0 8 0 3000 1 0 9 0 5000 1 0 7 0 2-й 500 3 8 6 0 500 4 2 9 0 500 5 14 10 0 500 5 10 9 0 1000 4 0 10 0 1000 5 0 11 0 2000 4 0 10 0 3000 3 0 6 0 5000 2 0 6 0 3-й 500 6 11 13 0 500 7 18 15 0 500 6 24 15 1 500 8 6 15 1 1000 7 0 13 0 1000 7 0 13 0 2000 7 0 15 0 3000 7 0 14 0 5000 6 0 13 0 1000 записів ризик втрати ребра становить 13 % (для порогу 0,01) та 28 % (для порогу 0,02). Для вибірок розміром від 2000 до 5000 записів середній ризик втрати ребра склав 10 % (для порогу 0,01) та 26 % (для порогу 0,02). Той факт, що при зростанні розміру вибірки показники втрат ребер зменшуються слабо, вказує на значну кіль- кість майже маскованих та деградованих ребер. Відомо, що завдяки співвідношен- ням параметрів моделі певне ребро гене- ративної моделі може перетворитися на Математичне моделювання об’єктів та процесів 108 масковане [18] або навіть деградувати (тобто абсолютно втратити вплив). На ко- ристь таких ситуацій у нашому експери- менті свідчить той факт, що для різних вибірок даних повторюються одні й ті са- мі пропуски ребер. Зокрема, для 2-го варі- анта параметризації в результатах виве- дення з усіх дев’яти вибірок (з обома зна- ченнями порогу значущості) пропущено ребра 7—5 та 24—19. А для третього ва- ріанту параметризації в результатах виве- дення з усіх дев’яти вибірок даних (коли використано поріг 0,02) пропущено вісім ребер. Не всі зафіксовані пропуски ребра можна вважати справжніми помилками. Пропуск деградованого ребра не є помил- кою. А що стосується синдрому маскова- них ребер, то відомі методи відтворення моделей (основані на незалежності) також не захищені від нього. Головний експеримент випробував роботу запропонованих резолюцій. Для цього експерименту використано вибірки розміром 2000 та поріг значущості 0,01. Оскільки деякі вищенаведені резолюції взаємно поглинаються, було реалізовано тільки чотири резолюції. Кожна з обраних резолюцій – єдиного близького, перемич- ки (об’єднана), центральної вершини (єдиного вузла) та кліки асоціацій у дере- вовидному оточенні, – застосовувалась автономно, як на початку процесу реконс- трукції. Тривалість застосування чотирьох резолюцій до вибірки даних складала біля третини секунди в середовищі MATLAB. (Потенційно складною задачею міг стати пошук максимальних клік, але вдалося уникнути важкості відомої абстрактної задачі через те, що процедура відразу шу- кає кліки, які задовольняють всім вимогам резолюції). Результати головного експеримен- ту наведено в табл. 2. Зафіксовані в таб- лиці помилки чотирьох резолюцій на- справді відображають одну помилку, яка сталася внаслідок того, що транзитна за- лежність двох-реберного ланцюга пере- вищила залежність одного з ребер того ланцюга. Якщо розглянути 1-й варіант параметризації, то чотири резолюції у пі- дсумку відтворили 24 ребра (без поми- лок), що становить дві третини ребер мо- делі. Для 2-го варіанта параметризації ці резолюції відтворили 18 ребер без поми- лок. Для 3-го варіанта параметризації правильно відтворено 26 ребер та встав- лено одне помилкове ребро. Таблиця 2 Ефективність застосування емпіричних резолюцій відтворення ребер Резолюція Варіант парамет- ризації Правильно відтворених ребер Помилкових ребер Р. єдиного близького 1 16 0 2 16 0 3 19 1 Р. перемички (об’єднана) 1 19 0 2 10 0 3 19 1 Р. центральної вер- шини (єдиного вузла) 1 16 0 2 7 0 3 18 1 Р. кліки асоціацій у деревовидному оточенні 1 6 0 2 5 0 3 16 1 Математичне моделювання об’єктів та процесів 109 Висновки Показано, яким чином (апріорі знаючи тільки приналежність моделі до класу монопотокових структур) можна ідентифікувати більшість ймовірнісних зв’язків (безпосередніх залежностей), спираючись виключно на безумовні зале- жності двох змінних. Ідентифікація ребер (зв’язків) виконується емпіричними резо- люціями, які строго обґрунтовані на базі припущення безумовної (маргінальної) реберної не-оманливості. Вже за своєю конструкцією це припущення є одним з найнадійнішим серед простих версій при- пущень каузальної неоманливості, відо- мих у галузі каузального виведення. Ви- сока емпірична надійність цього припу- щення та побудованих на ньому резолю- цій підтверджується результатами експе- рименту. Плануємо розвинути і перенести ідеї та принципи на загальний клас моде- лей із структурою ациклонних орграфів (байєсівських мереж). 1. Spirtes P. Introduction to causal inference. Journal of Machine Learning Research. 2010. Vol. 11, P. 1643−1662. 2. Kalisch M., Bühlmann P. Causal structure learning and inference: a selective review. Quality Technology & Quantitative Management. 2014. Vol. 11, N 1. P. 3–21. 3. The TETRAD Project: Constraint based aids to causal model specification / R. Scheines, P. Spirtes, C. Glymour et al. Multivariate Behavioral Research. 1998. Vol. 33, N 1. P. 65–118. 4. Chickering D., Heckerman D., Meek C. Large-sample learning of Bayesian networks is NP-hard. Journal of Machine Learning Research. 2004. Vol. 5. – P. 1287–1330. 5. Балабанов О.С. Відтворення каузальних мереж на основі аналізу марковських влас- тивостей. Математичні машини та систе- ми. 2016. № 1. С. 16–26. 6. Балабанов О.С. Каузальні мережі: аналіз, синтез та виведення з статистичних даних: дис. … доктора фіз.-мат. наук (01.05.01– теоретичні основи інформатики та кіберне- тики) / Балабанов Олександр Степанович. – К.: Ін-т кібернетики ім. В.М. Глушкова НАНУ, 2014. 305 с. 7. Балабанов О.С. Системи ймовірнісних за- лежностей: графові та статистичні власти- вості. Математичні машини та системи. 2009. № 3. С. 80–97. 8. Балабанов О.С. Правила підбору сепарато- рів в баєсівських мережах. Проблеми про- грамування. 2007. № 4. С. 33–43. 9. Chow C.K., Liu C.N. Approximating discrete probability distributions with dependence trees. IEEE trans. on Information Theory. 1968. Vol. 14, N 3. P.462–467. 10. Балабанов О.С. Індуктивне відтворення деревовидних структур систем залежнос- тей. Проблемы программирования. 2001. № 1–2. С. 95–108. 11. Балабанов О.С. Прискорення алгоритмів відтворення байєсівських мереж. Адапта- ція до структур без циклів. Проблеми про- грамування. 2011. № 1. С. 63–69. 12. Geiger D., Paz A., Pearl J. Learning simple causal structures. Internat. Journal of Intelligent Systems. 1993. Vol. 8, N 2. P. 231–247. 13. de Campos L.M., Huete J.F. On the use of independence relationships for learning simplified belief networks. Intern. Journal of Intelligent Systems. 1997. Vol. 12. Issue 7. P. 495–522. 14. Балабанов О.С. Ефективний метод вияв- лення структур залежностей в статистич- них даних. Проблемы программирования. 2004. № 2–3. С. 312–319. 15. Балабанов A.C. К выводу структур моде- лей вероятностных зависимостей из стати- стических данных. Кибернетика и систем- ный анализ. 2005. № 5. С. 19–31. 16. Балабанов А.С. Индуктивный метод восстановления монопотоковых вероятно- стных графовых моделей зависимостей. Проблемы управления и информатики. 2003. № 5. С.75–84. 17. Балабанов А.С. Реконструкция модели ве- роятностных зависимостей по статистиче- ским данным. Инструментарий и алгоритм. Проблемы управления и информатики. 2009. № 6. С. 90–103. 18. Балабанов А.С. Индуцированная зависи- мость, взаимодействие факторов и дис- криминация каузальных структур. Кибер- нетика и системный анализ. 2016. № 1. С. 10–22. Математичне моделювання об’єктів та процесів 110 References 1. Spirtes P. (2010). Introduction to causal inference. Journal of Machine Learning Research. 11, 1643−1662. 2. Kalisch M., Bühlmann P. (2014). Causal structure learning and inference: a selective review. Quality Technology & Quantitative Management. 11 (1), 3–21. 3. Scheines R., Spirtes P., Glymour C. et al. (1998). The TETRAD Project: Constraint based aids to causal model specification. Multivariate Behavioral Research. 33 (1), 65–118. 4. Chickering D., Heckerman D., Meek C. (2004). Large-sample learning of Bayesian networks is NP-hard. Journal of Machine Learning Research. 5, 1287–1330. 5. Balabanov O.S. (2016). Vidtvorennya kauzalnych merezh na osnovi analizu markovskich vlastyvostej [Reconstruction of causal networks via analysis of Markov properties]. Mathematical Machines and Systems. (1), 16–26. [In Ukrainian]. 6. Balabanov O.S. (2014). ‘Causal nets: analysis, synthesis and inference from statistical data’, Doctor of math. sciences thesis, V.M. Glushkov Institute of Cybernetics, Kyiv, Ukraine. [In Ukrainian]. 7. Balabanov O.S. (2009) Probabilistic dependency models: graphical and statistical properties. Mathematical Machines and Systems. (3), 80–97. [In Ukrainian]. 8. Balabanov O.S. (2007). Rules for picking up separators in Bayesian networks. Problems in programming. (4), 33–43. [In Ukrainian]. 9. Chow C.K., Liu C.N. (1968). Approximating discrete probability distributions with dependence trees. IEEE trans. on Information Theory. 14 (3), 462–467. 10. Balabanov O.S. (2001). Inductive recovery of structures of dependency trees. Problems in programming. (1–2), 95–108. [In Ukrainian]. 11. Balabanov O.S. (2011). Accelerating algorithms for Bayesian networks recovery. Adaptation to structures without cycles. Problems in programming. (1), 63–69. [In Ukrainian]. 12. Geiger D., Paz A., Pearl J. (1993). Learning simple causal structures. Internat. Journal of Intelligent Systems. 8 (2), 231–247. 13. de Campos L.M., Huete J.F. (1997). On the use of independence relationships for learning simplified belief networks. Intern. Journal of Intelligent Systems. 12 (7), 495–522. 14. Balabanov O.S. (2004). Efficient method for discovery of dependency structures in statistical data. Problems in programming. (2– 3), 312–319. [In Russian]. 15. Balabanov A.S. (2005). Inference of structures of models of probabilistic dependences from statistical data. Cybernetics and Systems Analysis. 41 (6), 808–817. – Springer, New York. 16. Balabanov A.S. (2003). Inductive reconstruction method for “mono-flow” probabilistic graphical models of Dependencies. Journal of Automation and Information Sciences. 35 (10), 1–8. – Begell House Publishers, Danbury. 17. Balabanov A.S. (2009). Reconstruction of the model of probabilistic dependences by statistical data. Tools and algorithm. J. of Automation and Information Sciences. 41 (12), 32–46. 18. Balabanov O.S. (2016). Induced dependence, factor interaction, and discriminating between causal structures. Cybernetics and Systems Analysis. 52 (1), 8–19. Одержано 20.12.2016 Про автора: Балабанов Олександр Степанович, доктор фізико-математичних наук, провідний науковий співробітник. Кількість наукових публікацій в українських виданнях – 50. Кількість наукових публікацій в зарубіжних виданнях – 9. http://orcid.org/0000-0001-9141-9074. Місце роботи автора: Інститут програмних систем НАН України, 03187, м. Київ-187, проспект Академіка Глушкова, 40. Тел.: (044) 5263420. Е-mail: bas@isofts.kiev.ua

Схожі ресурси