Knowledge discovery in data and causal models in analytical informatics

The methodology of inductive inference of causal models is briefly overviewed. We argue that causal networks, being recovered from data, are able to describe adequately a structure of influences in environment (object) at hand. It’s a causal model that is required when predicting the effect of inter...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2018
Автор:	Balabanov, O.S.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Інститут програмних систем НАН України 2018
Теми:	causal network model inference from data Markov properties conditional independence structure of dependencies causal effect edge orientation d-separation UDC 004.855:519.216
Онлайн доступ:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/299
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Problems in programming
Завантажити файл:

Репозитарії

Problems in programming

id	pp_isofts_kiev_ua-article-299
record_format	ojs
resource_txt_mv	ppisoftskievua/df/c4ab0dbf3a097c49174fcc846cd2d2df.pdf
spelling	pp_isofts_kiev_ua-article-2992024-04-28T11:48:08Z Knowledge discovery in data and causal models in analytical informatics Открытие знаний в данных и каузальные модели в аналитических информационных технологиях Відкриття знань у даних та каузальні моделі в аналітичних інформаційних технологіях Balabanov, O.S. causal network; model inference from data; Markov properties; conditional independence; structure of dependencies; causal effect; edge orientation; d-separation UDC 004.855:519.216 каузальная сеть; вывод модели из данных; марковские свойства; условная независимость; структура зависимостей; каузальный эффект; ориентация дуг; d-сепарация УДК 004.855:519.216 каузальна мережа; виведення моделі з даних; марковські властивості; умовна незалежність; структура залежностей; каузальний ефект; орієнтація дуг; d-сепарація УДК 004.855:519.216 The methodology of inductive inference of causal models is briefly overviewed. We argue that causal networks, being recovered from data, are able to describe adequately a structure of influences in environment (object) at hand. It’s a causal model that is required when predicting the effect of intervention in object. We outlined the preconditions and requirements on data collection process in aiming to reach an adequate causal network. A multivariate statistical data sample (measured under unified scheme) is needed in the input of inference method. We consider an independence-based approach to causal inference. Methods of this approach are correct, and can perform well in presence of hidden variables. The method’s output usually contains some edges not exactly oriented. Uncertainty of such kind is predetermined by problem setting and allows retaining model adequacy. We suggest a way to enforce an inference algorithm due to set of resolutions which reduce a space for searching separating sets (so focusing a process of edge verification). The modification proposed is based on systematic utilization of concept of locally–minimal separating set and Markov properties. An efficiency of developed algorithms (‘Razor’ series) is demonstrated by control experiments and case study. A distinction between a prediction of causal effect (i.e. effect of active experiment) and traditional prediction in data analysis is illuminated. Some problems of parameter estimation are presented. Some opportunities to predict causal effect when model is incompletely identified are illustrated. We point out a few ideas and new research trends which can enrich analyst’s ability to verify or identify a model. Problems in programming 2017; 3: 96-112 Описана методология индуктивного вывода каузальных моделей. Аргументировано, что каузальные сети, восстановленные из данных наблюдений (без априорных знаний), адекватно отображают структуры связей и влияний в среде. Очерчены предпосылки и требования к статистическим данным и процессу их сбору для успешного вывода адекватной каузальной сети. Рассмотрен подход к выводу каузальных сетей, основанный на независимости. Подход поддерживает разработку быстрых и асимптотически-корректных методов, которые способны работать в условиях скрытых факторов. Аргументировано, что модель, выведенная из данных, обычно имеет некоторые связи с неопределенной направленностью. Такая неопределенность объективно предопределена и позволяет сохранять адекватность модели. Показаны способы повышения эффективности вывода модели за счет оснащения алгоритмов набором резолюций, которые обеспечивают усечение пространства поиска сепараторов (фокусируют процесс верификации связей). Предложная модернизация методов базируется на систематическом использовании понятия локально-минимального сепаратора и марковських свойств моделей. Эффективность новых алгоритмов «Razor» продемонстрирована контрольными экспериментами и предметным примером. Разъясняется отличие каузального прогноза (который оценивает последствия планированного вмешательства) от традиционного «пассивного» прогноза. Показаны возможности оценивания каузального эффекта на основе неполно идентифицированной модели. Problems in programming 2017; 3: 96-112 Оглянуто методологію індуктивного виведення каузальних моделей. Аргументовано, що каузальні мережі, відтворені з даних спостережень (без апріорних знань), адекватно відображають структури зв’язків та впливів у середовищі і придатні для прогнозування наслідків керування. Окреслено передумови та вимоги до статистичних даних і процесу їх збору для успішного виведення адекватної каузальної мережі. Розглянуто підхід до виведення каузальних мереж, базований на незалежності. Підхід підтримує розробку швидких та асимптотично-коректних методів, які здатні працювати в умовах прихованих факторів. Аргументовано, що модель, виведена з даних, зазвичай має деякі зв’язки з невизначеною спрямованістю. Така невизначеність об’єктивно зумовлена й дозволяє зберігати адекватність моделі. Показано засоби підвищення ефективності виведення моделі за рахунок озброєння алгоритмів набором резолюцій, які забезпечують усікання простору пошуку сепараторів (фокусуючи процес верифікації зв’язків). Пропонована модернізація методів ґрунтується на систематичному застосуванні концепції локально-мінімального сепаратора та марковських властивостей моделей. Ефективність нових алгоритмів «Razor» продемонстрована контрольними експериментами та предметним прикладом. Роз’яснюється відмінність каузального прогнозу (що оцінює наслідки планованого втручання) від традиційного «пасивного» прогнозу. Показано можливості оцінювати каузальний ефект на основі неповно ідентифікованої моделі.Problems in programming 2017; 3: 96-112 Інститут програмних систем НАН України 2018-11-12 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/299 10.15407/pp2017.03.096 PROBLEMS IN PROGRAMMING; No 3 (2017); 96-112 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 3 (2017); 96-112 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 3 (2017); 96-112 1727-4907 10.15407/pp2017.03 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/299/293 Copyright (c) 2018 PROBLEMS OF PROGRAMMING
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2024-04-28T11:48:08Z
collection	OJS
language	Ukrainian
topic	causal network model inference from data Markov properties conditional independence structure of dependencies causal effect edge orientation d-separation UDC 004.855:519.216
spellingShingle	causal network model inference from data Markov properties conditional independence structure of dependencies causal effect edge orientation d-separation UDC 004.855:519.216 Balabanov, O.S. Knowledge discovery in data and causal models in analytical informatics
topic_facet	causal network model inference from data Markov properties conditional independence structure of dependencies causal effect edge orientation d-separation UDC 004.855:519.216 каузальная сеть вывод модели из данных марковские свойства условная независимость структура зависимостей каузальный эффект ориентация дуг d-сепарация УДК 004.855:519.216 каузальна мережа виведення моделі з даних марковські властивості умовна незалежність структура залежностей каузальний ефект орієнтація дуг d-сепарація УДК 004.855:519.216
format	Article
author	Balabanov, O.S.
author_facet	Balabanov, O.S.
author_sort	Balabanov, O.S.
title	Knowledge discovery in data and causal models in analytical informatics
title_short	Knowledge discovery in data and causal models in analytical informatics
title_full	Knowledge discovery in data and causal models in analytical informatics
title_fullStr	Knowledge discovery in data and causal models in analytical informatics
title_full_unstemmed	Knowledge discovery in data and causal models in analytical informatics
title_sort	knowledge discovery in data and causal models in analytical informatics
title_alt	Открытие знаний в данных и каузальные модели в аналитических информационных технологиях Відкриття знань у даних та каузальні моделі в аналітичних інформаційних технологіях
description	The methodology of inductive inference of causal models is briefly overviewed. We argue that causal networks, being recovered from data, are able to describe adequately a structure of influences in environment (object) at hand. It’s a causal model that is required when predicting the effect of intervention in object. We outlined the preconditions and requirements on data collection process in aiming to reach an adequate causal network. A multivariate statistical data sample (measured under unified scheme) is needed in the input of inference method. We consider an independence-based approach to causal inference. Methods of this approach are correct, and can perform well in presence of hidden variables. The method’s output usually contains some edges not exactly oriented. Uncertainty of such kind is predetermined by problem setting and allows retaining model adequacy. We suggest a way to enforce an inference algorithm due to set of resolutions which reduce a space for searching separating sets (so focusing a process of edge verification). The modification proposed is based on systematic utilization of concept of locally–minimal separating set and Markov properties. An efficiency of developed algorithms (‘Razor’ series) is demonstrated by control experiments and case study. A distinction between a prediction of causal effect (i.e. effect of active experiment) and traditional prediction in data analysis is illuminated. Some problems of parameter estimation are presented. Some opportunities to predict causal effect when model is incompletely identified are illustrated. We point out a few ideas and new research trends which can enrich analyst’s ability to verify or identify a model. Problems in programming 2017; 3: 96-112
publisher	Інститут програмних систем НАН України
publishDate	2018
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/299
work_keys_str_mv	AT balabanovos knowledgediscoveryindataandcausalmodelsinanalyticalinformatics AT balabanovos otkrytieznanijvdannyhikauzalʹnyemodelivanalitičeskihinformacionnyhtehnologiâh AT balabanovos vídkrittâznanʹudanihtakauzalʹnímodelívanalítičnihínformacíjnihtehnologíâh
first_indexed	2024-09-16T04:08:29Z
last_indexed	2024-09-16T04:08:29Z
_version_	1818568438944104448
fulltext	Інтелектуальні інформаційні технології © О.С. Балабанов, 2017 96 ISSN 1727-4907. Проблеми програмування. 2017. № 3 УДК 004.855:519.216 О.С. Балабанов ВІДКРИТТЯ ЗНАНЬ У ДАНИХ ТА КАУЗАЛЬНІ МОДЕЛІ В АНАЛІТИЧНИХ ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЯХ Оглянуто методологію індуктивного виведення каузальних моделей. Аргументовано, що каузальні мережі, відтворені з даних спостережень (без апріорних знань), адекватно відображають структури зв’язків та впливів у середовищі і придатні для прогнозування наслідків керування. Окреслено пере- думови та вимоги до статистичних даних і процесу їх збору для успішного виведення адекватної кау- зальної мережі. Розглянуто підхід до виведення каузальних мереж, базований на незалежності. Під- хід підтримує розробку швидких та асимптотично-коректних методів, які здатні працювати в умовах прихованих факторів. Аргументовано, що модель, виведена з даних, зазвичай має деякі зв’язки з не- визначеною спрямованістю. Така невизначеність об’єктивно зумовлена й дозволяє зберігати адекват- ність моделі. Показано засоби підвищення ефективності виведення моделі за рахунок озброєння ал- горитмів набором резолюцій, які забезпечують усікання простору пошуку сепараторів (фокусуючи процес верифікації зв’язків). Пропонована модернізація методів ґрунтується на систематичному за- стосуванні концепції локально-мінімального сепаратора та марковських властивостей моделей. Ефе- ктивність нових алгоритмів «Razor» продемонстрована контрольними експериментами та предмет- ним прикладом. Роз’яснюється відмінність каузального прогнозу (що оцінює наслідки планованого втручання) від традиційного «пасивного» прогнозу. Показано можливості оцінювати каузальний ефект на основі неповно ідентифікованої моделі. Ключові слова: каузальна мережа, виведення моделі з даних, марковські властивості, умовна незалеж- ність, структура залежностей, каузальний ефект, орієнтація дуг, d-сепарація. Каузальні моделі – відповідь на потреби аналізу та прогнозу ефектів рішень В багатьох організаціях та відомст- вах доволі часто збір статистичних даних та їх аналіз слабо пов’язані з підготовкою й вибором планів та рішень. Доволі типо- вою є ситуація, коли організація (орган управління) має у своєму розпорядженні великі зібрання даних, але ці дані дуже вибірково та обмежено залучаються до предметних досліджень, підготовки пла- нів та прогнозування наслідків пропоно- ваних управлінських рішень. Вибір і об- ґрунтування рішень робиться на основі експертних суджень і оцінок, адекватність яких важко контролювати. А коли аналі- тики все ж вдаються до побудови матема- тичних або інформаційних моделей, то в основу цих моделей знов лягають експер- тні міркування та суб’єктивні уявлення. Необхідно позбуватися суб’єктивізму й консерватизму в механізмах підготовки й обґрунтування важливих рішень. Те, що інформаційні технології глибокого аналі- зу даних та математичного моделювання відіграють незначну роль в аналітичній роботі штабів та органів управління, пев- ною мірою можна пояснити тим, що тра- диційні, давно відомі методи та моделі спираються на ідеалізовані припущення, неадекватно відображають зовнішні (при- ховані) фактори, а також не забезпечені ефективними процедурами контролю аде- кватності. У провідних країнах стало норма- льною практикою управління використо- вувати моделі, виведені науковими мето- дами на основі даних спостережень за об’єктом моделювання. Користувачеві потрібна модель об’єкта, яка допомагає зрозуміти реальні процеси та взаємо- залежності між різними субпроцесами й характеристиками. В практичних пробле- мних ситуаціях фундаментальні науки не дають потрібної моделі через те, що пре- дметна галузь лежить на перетині різних дисциплін і характеризується взаємодією великої кількості різнорідних факторів. Зазвичай адекватна модель є невідома, а знання про об’єкт існують як сукупність розрізнених відомостей та уявлень вузь- ких спеціалістів, а також усталених (упе- реджених) переконань практиків. Таку «скирту інформації» важко узгодити, ве- Інтелектуальні інформаційні технології 97 рифікувати та звести у робочу модель. Отже, шукана адекватна модель прирече- на бути емпіричною (за витоками) та фе- номенологічною й конгломеративною (за рівнем репрезентації). Актуальна задача – ідентифікація моделі «об’єктивними» ме- тодами на основі зібраних даних спосте- режень (рис. 1). Аналіз, осмислення, прогнозу і по- яснення треба виконувати в термінах по- казників та індексів, які можна виміряти на реальному об’єкті. Названі види пізна- вальної діяльності потребують єдиної мо- ви відображення процесів через реальні характеристики в їх природному об'єкти- вному зв’язку та взаємодії. Найбільш уні- версальною і зрозумілою мовою відобра- ження зв’язків, взаємодій та впливів є причино-наслідкові відношення (в їх су- часному розумінні). Отже, спільною ос- новою розв’язання всіх названих задач має бути каузальна модель об’єкта в сере- довищі. Виявлення каузальних відносин на основі даних спирається на статистичні залежності. Але перехід від статистичних залежностей до каузальних зв’язків – кри- тичний і фундаментальний крок, що пот- ребує ґрунтовної методологічної аргумен- тації. Для підтримки управління об’єктом (процесом) необхідна саме каузальна мо- дель (а не просто модель залежностей). Відмінність каузального зв’язку від стати- стичної залежності можна проілюструвати на наступному прикладі. Уявіть, що аналіз даних про населення району (чи міста) по- казав, що відсоток захворювань на грип – значно вищий серед тих, хто за кілька днів перед тим придбав в аптеці та вживав ан- ти-грипозні препарати. Наївний «аналітик» має підстави для висновку, що вживання препаратів є серед причин захворювання. Насправді до покупки анти-грипозних препаратів людину спонукало погіршення самопочуття, а також знання, що вона схи- льна до захворювання (генетично або че- рез умови праці). Саме названі фактори є причинами як захворювання, так і покупки препаратів. Для з’ясування істини потріб- но відтворити каузальну модель. (Повер- немося до цього прикладу, коли розгляда- тимемо каузальний ефект). Принципову відмінність каузальних та некаузальних моделей можна пояснити через різницю задач «пасивного» прогнозу та «активного» (каузального) прогнозу [1, 2]. Задача першого типу може формулюва- тися так: «яким правдоподібно було зна- чення характеристики Y об’єкта у тих ви- падках, коли характеристики X та Z мали значення zx, . (Власне кажучи, це не про- гноз, а реконструкція стану, тобто запов- нення пропущених значень атрибутів, ви- ходячи із значень інших атрибутів об’єкта). Задача каузального прогнозу формулюється у формі: «якою правдопо- дібно має бути значення характеристики Y об’єкта, якщо ми надамо характеристи- кам X та Z значення zx, відповідно. Це є прогноз наслідків (ефекту) втручання в об’єкт. Адекватність моделі означає пра- Рис. 1. Цикл інформаційних технологій з індуктивним моделюванням Підготовка даних Дані Виведення моделі Модель S W Y X Q Z R Об’єкт у середовищі Прогноз Інтелектуальні інформаційні технології 98 вильне відображення системи впливів та зв’язків у середовищі (світі), точний опис причинно-наслідкових відношень у зада- ному середовищі (за умов «відкритого світу»). Традиційні методи часто не здатні знайти адекватну модель і задовольнити вищевказані потреби. Наприклад, регре- сійний аналіз не озброєний систематич- ними засобами контролю, які б забезпе- чили відтворення виключно автентичних зв’язків та каузальних відношень. (Регре- сія рідше відтворює асоціації безвідносно до їх характеру, в тому числі й «фальшиві асоціації»). Інші відомі методи теж або не забезпечують системності підходу, або надто спеціалізовані, або ґрунтуються на нереалістичних припущеннях, або неефе- ктивні у реалізації. Багато методів потре- бують апріорних знань, яких може й не бути. Принциповий крок від «просто ста- тистичних» моделей до каузальних моде- лей було зроблено завдяки новому типу каузальних моделей і новим ефективним методам їх виведення [1–3]. Як відомо, марковський процес адекватно відображає поведінку окремого реального процесу. Якщо спробувати по- ширити подібне відображення на систему впливів та взаємодій між багатьма проце- сами й змінними (показниками), то поста- не потреба описувати багатовимірні мар- ковські властивості. Знадобиться перейти від простої послідовності до графової (мережевої) структури. Але модель має описувати не епізодичний фрагмент кон- кретних подій, а типову узагальнену за- кономірну поведінку процесів. Таким чи- ном, з’ясовуються засадничі принципи шуканих моделей. Перелічимо ці принци- пи: структуру зв’язків – граф (вершини відповідають змінним); ребра (дуги) гра- фа – орієнтовані для відображення напря- му впливу; принцип «зборки» моделі – умовна незалежність змінних; кількісний опис залежностей – локальний та ймовір- нісний. Кількісний аспект каузальної ме- режі описується фрагментами у формі умовних розподілів ймовірностей ~ ( \| , ,..)Y p Y x z , де ,...,zx – значення змінних ,...,ZX , які безпосередньо впли- вають на Y . Тобто компоненти розподілів ймовірностей залежної змінної є функці- ями безпосередніх причин ( )ip y  ( , ,..)if x z . В певних класах моделей ло- кальні описи мають окрему детерміністи- чну частину та адитивний випадковий га- мір: :y ( , ,..) Yf x z  . В цьому структу- ральному рівнянні свідомо застосовано знак присвоєння, а не звичайна алгебраїч- на рівність, для передання семантики впливу. (В спеціальній літературі викори- стовується звичайний знак рівності, проте треба пам’ятати вказану відмінність. Не можна переносити якийсь член на інший бік структурального рівняння.) Отже, ма- ємо систему локальних описів, інтегрова- них в єдину модель без «швів». Ймовірні- сний характер моделі дозволяє зберігати адекватність, незважаючи на те, що багато релевантних факторів залишилося поза аналізом і що були відхилення від схеми вимірювання даних. Відтворення структур зв’язків та закономірностей, які неявно відбиті в ба- гатовимірних масивах статистичних да- них – одна з центральних проблем глибо- кого аналізу даних та відкриття знань в базах даних [4, 5]. Каузальне моделюван- ня – передовий фронт досліджень у цій галузі. Марковський характер каузальних мереж сприяє тому, що ці моделі можна виводити індуктивно (рис. 1), тобто відт- ворювати на основі обробки емпіричних даних спостережень (зокрема, за відсут- ності апріорних знань). За відповідних передумов виведена модель буде адекват- но відображати причинно-наслідкові від- ношення в об’єкті й середовищі. Той факт, що задачу ідентифікації каузальної моделі (за яку навіть не брався традицій- ний статистичний аналіз) відносять до на- прямків галузі відкриття знань у даних, пояснюється наступним. Рандомізовані експерименти на об’єкті моделювання можуть бути непри- пустимими або недоступними з огляду на етичні міркування, економічні чинники, або через тимчасову недосяжність об’єкта. Наприклад, не можна проводити експерименти з населенням та економі- кою країни. Водночас для того, щоб «до- копатися» до каузальних відносин, аналі- Інтелектуальні інформаційні технології 99 зуючи дані «пасивних» спостережень, тих спостережень має бути багато, і вони ма- ють охоплювати досить широкий спектр характеристик. Сучасна методологія відт- ворення каузальних мереж на основі ем- піричних даних об'єднує потужні можли- вості технологій відкриття знань в даних з сучасними статистичними методами, і за- вдяки цьому дозволяє в одному циклі об- робки здійснити те, що раніше розділяло- ся на експлоративний аналіз даних та конфірмативний аналіз даних (включаючи перевірку гіпотез). Виведення каузальних моделей з емпіричних даних призначене для пізна- вальних задач і підтримки керування об’єктами та процесами у недостатньо до- сліджених галузях і середовищах [2, 4–8]. Каузальні мережі є багатоцільовими (на відміну, скажімо, від регресійних моде- лей). Вони дозволяють давати відповіді на запити у будь-якому форматі, тобто мож- на задавати різні цільові змінні, різні спо- лучення умов та ще задавати керування обраними змінними. У підсумку, клас ймовірнісних орієнтованих моделей зале- жностей та притаманні їм методи дозво- ляють втілити як комп’ютерну технологію закінчений цикл робіт (рис. 1) за схемою {вимірювання, спостереження}  дані  модель  {аналіз рішень, прогноз}. Відомо декілька класів та різнови- дів каузальних мереж, які відрізняються типом зв’язків, структурними обмежен- нями та формами параметризації локаль- них залежностей. Більшість аналітиків працює з моделями на основі ациклонних орієнтованих графів (АОГ); в цих графах заборонені структури вигляду XZX  (тобто циклони). Клас «ординарних» АОГ-моделей (оАОГ- моделей) утворюється з використанням виключно одно-орієнтованих дуг YX  . Серед оАОГ-моделей найбільш відомі байєсові та гауссові мережі [1–7]. Байєсо- ві мережі побудовані на дискретних змін- них, а залежності описуються у формі таблиць умовних розподілів ( \| , ,..)p Y x z . Гауссові мережі побудовані на лінійних залежностях та нормально-розподілених змінних. Також гауссові мережі звуться системами лінійних структуральних рів- нянь. Приклад одного рівняння: :y ...a x b z    Y , ( 2~ ( , )Y Y YN m  ). Узагальнені класи моделей струк- туруються графами, які додатково містять біорієнтовані дуги YX  . Така дуга відображає вплив прихованої змінної. До моделей з біорієнтованими дугами нале- жать нерекурсивні каузальні мережі, моделі на основі анцестральних («предко- вих») графів та каузальні діаграми Дж. Перла [1, 2]. Передумови та запорука успішного виведення та застосування каузальних моделей Поштовхом для розробки нових методів виведення каузальних моделей з даних стало розповсюдження технологій збору емпіричних даних, накопичення ве- ликих масивів даних та відкриття доступу до них через Інтернет. Оскільки мета по- лягає у виведенні каузальних зв’язків з даних пасивних спостережень, висува- ються жорсткі вимоги до обсягів залуче- них даних. Для реконструкції адекватної моделі необхідно мати великі вибірки да- них (особливо у випадках складних та не- лінійних форм залежностей). Для того, щоб виведена модель ві- дображала певні причинно-наслідкові зв’язки, необхідно, щоб дані, подані на вхід методу, містили причини та наслідки. Методам виведення каузальних мереж необхідні дані з характеристиками відпо- відного рівня, організовані у певних форматах. Підготовлені дані становлять статистичну вибірку, тобто складаються з багатьох «випадків», кожний з яких містить фіксований набір характеристик, виміряних за єдиною схемою. Елемента- ми запису виступають значення виміря- них величин у відповідні («характерні») моменти (інтервали) часу (але астрономі- чно різні). Дані мають відображати стати- стику поведінки об’єкта впродовж бага- торазового проходження об’єктом типо- вого циклу функціонування (з варіацією умов і факторів, частина яких може зали- шатися поза спостереженнями). Вибірка Інтелектуальні інформаційні технології 100 даних передбачає повторюваність механі- змів поведінки, і ця повторюваність може бути просторовою чи темпоральною. Ко- жний «випадок» може відповідати або окремому екземпляру популяції (індиві- ду), або окремій транзакції чи періоду (циклу) життя. В одних БД записи даних відносяться до різних індивідів, членів популяції, екземплярів однотипних об’єктів. В інших БД всі записи характе- ризують один і той самий реальний об’єкт, але в різні періоди життя, в різні цикли функціонування. (Такі об’єкти функціонують з багаторазовим пере- запуском.) В останньому разі формування вибірки може потребувати розбиття («нарізку») серії вимірювань за періода- ми. В процесі підготовки даних потрібно- го змісту і формату неприпустимі «викри- влення» (втручання у значення), усеред- нення або підміна вимірювання довіль- ною інтерпретацією. Дані треба вимірю- вати якомога точніше і не допускати до- давання якихось величин. Кожний еле- мент даних має бути виміряний точно і відображати «миттєвий» стан процесу. Можлива проблемна ситуація, коли на структуру моделі апріорі не накладено обмежень й нічого не відомо про цю структуру. Зазвичай застережене єдине обмеження – в структурі немає орієнто- ваних циклів (циклонів). Відсутність циклонів можна вважати вимогою корек- тного збору даних. Тобто в процесі генерації одного запису даних кожна змінна X вимірюється досить швидко, так що «сигнал» від X , поширюючись до інших змінних, не встигає «оббігти коло» й вплинути на X в цьому запису. Звичайно, якщо є достовірні апріо- рні знання, їх треба використати. Це до- зволить прискорити виведення та уточни- ти модель. Типова форма апріорних знань – темпоральний порядок змінних моделі. Оскільки оперувати занадто вели- кою номенклатурою даних важко й недо- цільно, доведеться обмежитися прийнят- ним набором взаємозв’язаних релевантних характеристик. Деякі змінні можуть бути недоступні для вимірювання. Практично обраний формат даних майже завжди буде неповно описувати предмет. (Тобто це бу- де «вікно», «кадр», вирізаний з реальнос- ті). Багато факторів залишаться поза ме- жами обраного «вікна». Відтак, аналітик приречений працювати з моделлю у «відк- ритому світі». Але це не буде перепоною для виведення адекватних каузальних ме- реж, зокрема, завдяки ймовірнісному хара- ктеру опису. Прихованість деяких факто- рів впливу не заважає тестувати марковсь- кі властивості серед наявних змінних. Далі розглядається один з перспек- тивних підходів до виведення каузальних мереж з даних, базований на незалежнос- ті. Процес виведення за цим підходом ро- згортається через три послідовні фази (рис. 2). Рис. 2. Схема виведення каузальної мережі з даних Дані Об'єкт Експертні знання (необов'язково) Встановлення безпосередніх зв'язків структурних ро- збіжностей Виявлення напрямків впливів Обчислення параметрів Інтелектуальні інформаційні технології 101 Припустимо, генеративна модель, тобто модель, яка вичерпно адекватно і однозначно відображає розгортання про- цесів та формування змінних об’єкта, складається виключно із звичайних одно- спрямованих дуг вигляду BA . Тобто нехай «повна» (уявна) модель є однознач- ною і точною; але вона невідома. В ре- зультаті виведення буде отримана інша модель, яка зазвичай не буде вичерпно однозначною. Це випливає з того, що різ- ні варіанти спрямованості (орієнтації) де- яких дуг не змінюють марковських влас- тивостей моделі. Додаткова неоднознач- ність породжується тим, що у форматі да- них не репрезентовано деякі важливі змінні. Навіть якщо прийняти постулат, що в моделі не існує жодної прихованої змінної, яка впливає рівночасно на дві (чи більше) спостережувані змінні, виведена структура має залучати дуги двох типів – неорієнтовані та каузальні. Якщо ж існу- вання таких прихованих змінних не ви- ключено, то для збереження адекватності виведеної моделі можуть знадобитися дуги принаймні чотирьох типів. Для відображення безпосередніх зв’язків мо- дель залучає дуги наступних типів. Дуга вигляду YX  відображає каузальний вплив X на Y . Дуга WU  позначає існування прихованої (латентної) змінної, що впливає рівночасно («паралельно») на U та W . Дуга V Z резервує два можливих варіанти: каузальний вплив або існування прихованої змінної («посе- редника»). Дуга Q — R означає, що спрямованість цього зв’язку зовсім не визначена. (Деякі методи виведення мо- делі видають спеціальні позначки для заборони сполучень орієнтації деяких сусідніх ребер [2]). Отже, коли в результаті виведення (серед іншого) отримали дугу вигляду Z Q , прихована змінна між Z та Q можлива. Коли на виході отримуємо бі- орієнтовану дугу QZ  , це треба розумі- ти, що метод однозначно виявив прихова- ну змінну. Біорієнтовані дуги (вигляду QZ  ) ідентифікуються відомими мето- дами тільки на основі відповідного спеціа- льного сполучення марковських властиво- стей, який виникає внаслідок дії прихова- ної змінної у певному оточенні. Тому таку приховану змінну між Z та Q називають латентною і відрізняють від змінної- «посередника» [2, 9]. Розплутати систему залежностей буде особливо важко, коли пропущено «вузлові» змінні. Невизначеність у проблемній ситу- ації робить однозначне рішення недосяж- ним. Виведена модель буде, по-перше, нечіткою («розмитою») у статистично- ймовірнісному сенсі, а, по-друге, на вихо- ді отримаємо лише клас еквівалентності моделей (де не визначені напрямки де- яких зв'язків). Невизначеність у виведеній моделі об'єктивно зумовлена і застерігає аналітика від необґрунтованих висновків. Відзначимо, що вимушена невизначеність структури моделі не знаходить адекватної репрезентації у традиційному регресійно- му аналізі. До речі, клас каузальних ме- реж на основі оАОГ можна назвати сис- темою регресійних моделей, поданих в інтегрованому вигляді. До цього треба додати, що в процесі виведення каузаль- ної мережі метод знаходить коректну пос- тановку (формат) задач регресії. Виведення каузальної моделі з да- них у форматі часових рядів має свої осо- бливості (висока автокореляція, не виді- лено «випадки», невідома глибина лагу залежностей тощо). Тому процес виве- дення потребує додаткової підготовки та спеціальних процедур. Умовна незалеж- ність використовувалась у виведенні мо- делей з часовий рядів ще у працях нобе- левського лауреата К. Грейнджера. Зро- зуміло, для того, щоб розплутати систему тісних взаємодій в багатовимірних рядах, потрібна досить висока частота вимірю- вань. Сучасний апарат каузальних мереж підносить можливості моделювання в економетриці на вищий рівень. Коли (через невизначеність) ре- зультати не задовольняють аналітика, постає необхідність «перезавантажити» (оновити) завдання, включивши в номен- клатуру даних додаткові змінні (сподіва- ючись, що деякі з них гратимуть роль «вузлових» або прокаузальних). Вирі- шення деяких проблем може потребува- Інтелектуальні інформаційні технології 102 ти даних, виміряних з більшою частотою (але це – повернення до етапу збору да- них). Відтворення структури каузальної мережі з даних Найбільш поширені два підходи до виведення моделей з даних: 1) оснований на незалежності («constraint-based», «се- параційний»); 2) «оптимізаційний», або апроксимаційний. Оптимізаційний підхід полягає у максимізації критерію якості моделі в процесі підбору структури моде- лі. Оснований на незалежності підхід ба- зується на виявленні паттернів, які свід- чать про відсутність дуг у структурі мо- делі (факти умовної незалежності). Цей підхід своєю ідеологією забезпечує деко- мпозицію задачі. По-перше, замість опе- рування цілою моделлю (або її великими фрагментами, «родинами») метод на кож- ному кроці розглядає «вирізку» з моделі, достатню для вирішення питання про іс- нування відповідної дуги. По-друге, про- цес виведення моделі розпадається на три фази, де перебірний характер має тільки перша фаза (рис. 2). Хоча два вказані підходи вигляда- ють дуже відмінними, в їх фундаменті за- кладено єдиний принцип. Мета обох – ви- вести найпростішу модель, узгоджену з даними (це – сучасне розуміння принципу «Лезо Оккама»). У першому підході це «лезо» закладено у критерій якості моде- лі, який містить штраф за складність. У другому підході «лезо» проявляється в намаганні видалити якомога більше зв’язків, шукаючи для цього свідчення у формі умовних незалежностей. (Відзна- чимо, що оптимізаційний підхід потерпає від існування прихованих змінних). Най- більш відомі алгоритми сепараційного підходу – ‘PC’ та ‘FCI’. Перший працює в класі оАОГ-моделей, другий дозволяє латентні змінні і використовує дуги чоти- рьох вказаних типів. Отже, протягом першої фази для кожної пари змінних вирішується питан- ня, чи існує між ними безпосередній зв’язок (дуга). Оскільки про орієнтацію дуги в цій фазі не йдеться, часто замість «дуга» кажуть ребро і позначають A — B . Теоретичним підґрунтям виведення моде- лі є ізоморфізм структури моделі та її марковських властивостей. Всі марковські властивості строго верифікуються суто графовим критерієм d-сепарації [1, 2, 7, 10–12]. Втім, для ідентифікації ребер моделі достатньо залучити простий наслі- док з d-сепарації. (Він чинний не для всіх класів моделей). Наслідок такий: для пари вершин YX , d-сепаратор існує- тоді й тільки тоді, коли між X та Y немає дуги. Але виведення моделі з да- них потребує емпіричної версії цього принципу. Якщо змінні X та Y безпосе- редньо не зв’язані (немає дуги), то існує такий набір змінних, що застосування його як умови робить змінні X та Y умовно незалежними. (Зрозуміло, що са- мі змінні X та Y не можуть входити до умови, коли тестується їх умовна не- залежність). Для обґрунтування коректності виведення моделі з даних треба «транс- лювати» властивості d-сепарації (з гра- фовій термінології) в емпіричну форму. Тобто необхідне припущення каузальної неоманливості, яке в загальній формі можна сформулювати наступним чином. В розподілі ймовірностей змінних, генерованому з АОГ-моделі, для кожної пари змінних X,Y умовна незалежність (з умовою S ) чинна тільки тоді, коли S d- сепарує X та Y в графі моделі. У модельному розподілі ймовірно- стей це припущення виконується за ви- ключенням особливих випадків. У вибір- ковому розподілі ймовірностей воно ви- конується асимптотично. Проте методи обраного підходу потерпають навіть при наближенні до порушення припущення каузальної неоманливості, що стається доволі часто. (Неможливо відрізнити сла- бку залежність від прояву вибіркового ухилу). Зазначимо, що в практиці не потрі- бно тотального виконання сформульова- ного вище припущення. Достатньо, щоб воно виконувалося в секторі пошуку се- паратора в процесі виведення. Тобто до- статньо не наштовхнутися на «обманну» незалежність в процесі виконання першої фази виведення. З цієї точки зору розроб- Інтелектуальні інформаційні технології 103 лені засоби звуження секторів пошуку се- параторів (див. далі) дуже корисні. Перша фаза виведення полягає у пошуку сепараторів. Коли змінних багато і на структуру залежностей не накладено обмежень (апріорі нічого не відомо про цю структуру), пошук сепараторів стає комбі- наторно важкою задачею [2, 6–8, 13]. Перебірний характер пошуку сепараторів- не створює обчислювальних проблем тіль- ки коли залежності лінійні. (Частинні ко- реляції швидко обчислюються з матриці парних кореляцій). Але лінійність моделі не усуває загальну проблему – ненадій- ність рішень щодо дуг через ризик обман- них результатів тестування умовної неза- лежності. Обчислювальна складність зрос- тає для нелінійних залежностей й особливо для залежностей невідомої форми. Тоді виконання кожного тесту потребує нового сканування вибірки даних (для обчислення статистики). Важливі евристики для скорочення перебору в ході пошуку сепараторів було втілено в алгоритмі PC. Перша евристика: сепаратори підбираються і випробову- ються в порядку зростання їх розміру і в циклічному обході пар змінних. Друга ев- ристика: сепаратор для пари X,Y підби- рається серед множин вершин, які вважа- ються (гіпотетично) суміжними відповід- но до X та Y на поточний момент виве- дення моделі. Було знайдено нові можливості оп- тимізації першої фази виведення за раху- нок подальшого фокусування пошуку се- параторів. Сутність новацій зводиться до того, що знайдення одних сепараторів дає підказку для пошуку сепараторів для ін- ших (сусідніх) пар змінних. Такі засоби й процедури прискорення пошуку сепара- торів стали доступними через осягнення двох ідей. Перша – для кожної пари змін- них достатньо знайти один «простий» се- паратор. Друга ідея – прості сепаратори для «сусідніх» пар змінних якось пов'яза- ні один з одним, і «перетин» форматів се- парації треба використати разом з факта- ми залежності. Теоретичним підґрунтям шуканої техніки стала концепція локально- мінімального d-сепаратора в каузальній мережі [10–12, 15, 16] та необхідні вимоги до кожного члена локально-мінімального d-сепаратора. Сепаратор S для пари вершин ,X Y зветься локально-мінімаль- ним, якщо після вилучення з S будь- якого його члена (елемента) Z «залишко- вий» набір }{\ ZS не буде сепаратором для ,X Y . Виходячи з властивостей структур залежностей та з необхідних вимог до члена локально-мінімального сепаратора, було виведено набір правил (резолюцій) мінімальної сепарації [7, 11–13, 15, 16]. Мабуть, найпростішим з цих правил є на- ступне. Правило «відсторонення» кандида- та у сепаратор (‘placing aside’): якщо в орграфі G вершина X d-сепарує Z та Y , то вершина Z не є членом жодного локально-мінімального сепаратора для пари ,X Y . Виведено також правила, які вста- новлюють вимоги до сепаратора у цілому. До складу кожного локально-міні- мального d-сепаратора для пари вершин ,X Y (якщо він не порожній) обов’язково входить щонайменше одна вершина, яка лежить на деякому ланцюгу між X та Y . Кожна така вершина Z задовольняє набір вимог: Z безумовно залежна від X та Y ; Z не відсторонюється від ,X Y . Вершина Z , що задовольняє цим вимо- гам, зветься потенційним стрижнем сепа- ратора для ,X Y . Правило обов’язковості потенційного стрижня змушує включати в кожний пробний сепаратор принаймні один потенційний стрижень. Зазначимо, що це правило (рівно як й інші) залишається коректним в ситу- ації, коли не існує жодного сепаратора для ,X Y . Більш того, в таких ситуаціях правила ще корисніше. Усі виведені правила (резолюції) мінімальної сепарації згідно їх ролі (хара- ктеру дії) можна розподілити на чотири наступні групи («родини»). 1. Родина правил суміжності (або встановлення ребра). 2. Родина правил заборони ребра (або не-суміжності). Інтелектуальні інформаційні технології 104 3. Родина правил фільтрації (від- кидання) кандидатів у сепаратор. 4. Родина правил стрижня і пра- вил необхідного кандидата. Правила суміжності негайно вста- новлюють ребра графу моделі. Правила- заборони ребра негайно видаляють ребра з моделі (тим самим завершуючи відга- луження пошуку). Правила фільтрації (відкидання) кандидатів видаляють певні вершини (змінні) зі списку можливих членів сепаратора для відповідної пари. Нарешті, правила необхідного кандидата фіксують обов’язкового члена сепаратора (який ще не знайдений, але можливий). Емпіричні версії описаних правил – сепараційні резолюції, застосовують факти умовної незалежності (замість d- сепарації). Коректність емпіричних сепа- раційних резолюцій обґрунтовується при- пущенням, аналогічним до вищевказаного припущення каузальної неоманливості. Сепараційні резолюції, імплантовані в алгоритм виведення структури моделі, прискорюють виведення і навіть можуть підвищити надійність. Для випадку, коли є апріорі відо- мий темпоральний порядок змінних, не- обхідно зробити певні корекції правил локально-мінімальної сепарації. В ситуа- ції заданого темпорального порядку ефек- тивність правил локально-мінімальної сепарації дещо знижується, але не ніве- люється. Певні правила, згідно оцінки, забезпечують прискорення пошуку сепа- раторів приблизно на 67 % або 50 % від- носно ситуацій з невідомим темпораль- ним порядком. Для пояснення принципів розпі- знавання спрямованості дуг (рис. 2) зна- добляться деякі поняття. Колізор (collider) – це шлях вигля- ду ZYX  (або X Y  Z ). Цей колізор зветься нешунтованим, якщо від- сутня дуга X — Z . В разі нешунтованого колізора змінні X та Z або є безумовно незалежні, або їх залежність опосередко- вується деякими «третіми» змінними і може бути заблокована (зруйнована). Ланцюг – це шлях, на якому немає жодно- го колізора. Процес орієнтації дуг стартує з за- стосування колізорного правила [2]. Це правило знаходить пари сусідніх дуг, які претендують стати нешунтованими колі- зорами. Якщо є відповідна умовна незале- жність, ідентифікується колізор, тобто ста- вляться «вістря» дуг колізора. Потім вико- нується пост-колізорне правило орієнтації, яке встановлює «хвости» дуг, а далі – іден- тифікує каузальні дуги [2, 9]. По-суті, для ідентифікації каузальної дуги потрібно знайти щонайменше одну прокаузальну змінну та одну квазіпрокаузальну змінну. (В [9] такі змінні неточно названі інстру- ментальними). На рис. 3, а показано приклад ге- неративної моделі, а на рис. 3, б – ре- зультат виведення після фази орієнтації дуг. Процес орієнтації дуг розпочинаєть- ся з розпізнання нешунтованого колізора R Q Z . Далі працює пост-колізорне правило орієнтації, яке встановлює інші «вістря», а також «хвости» дуг. У наведе- ній структурі для ідентифікації дуг XQ  та YX  як каузальних роль прокаузальної змінної зіграла Z , а квазі- прокаузальної – змінна R . Відзначимо, що орієнтація дуги R  X (рис. 3, б) не підтримується стан- дартними процедурами і потребує додат- кового обґрунтування та пояснення. Ви- значення «стрілки» цієї дуги біля змінної X (на рис. 3, б обведено штриховим кі- льцем) аргументується наступним чином. Аналіз даних показав безумовну незалеж- ність змінних R та Z (статистично не- значущу залежність). Якщо прийняти ва- ріант орієнтації XR  , то виникає шлях QXR  Z , який мусить забезпечувати залежність змінних R та Z . Тому для узгодження з даними треба прийняти саме стрілку до X на дузі R  X . Проте можна не погоджуватися з цією аргументацією, і не відкидати варі- ант QXR  Z . Тоді той факт, що залежність між R та Z – незначуща, можна пояснити тим, що ця залежність є «дистанційна», тобто передається через шлях (ланцюг) з трьох послідовних дуг, і тому вона слабка. (Насправді той шлях Інтелектуальні інформаційні технології 105 утворений з чотирьох дуг – див. рис. 3, а). Втім, в аргументації такого штибу краще спиратися на силу (величину, тісноту) залежності, а не на довжину ланцюга зв’язку. Сила залежності – об’єктивна; довжина ланцюгу – похідна від формату завдання. Втім, необхідно мати на увазі, що в багатьох ситуаціях силу впливу некоректно оцінювати залежністю у фор- маті «одна від одної» [14]. В подібних ситуаціях внести ясність (і підвищити на- дійність ідентифікації кінцівок типу «віс- тря») може допомогти техніка провокова- ної залежності [14]. Треба звернути увагу, що невизна- ченість орієнтацій дуг у моделі не пояс- нюється невідомим темпоральним по- рядком змінних. В ситуаціях, де припус- кається існування прихованих змінних, навіть якщо точно й повністю задати темпоральний порядок змінних, це не усуває проблему невизначеності спрямо- ваності деяких дуг. Наприклад, якщо відомо, що у темпоральному порядку змінна W стоїть раніше Y , то дуга між ними негайно уточнюється до вигля- ду W Y (без використання колізорного правила). Але кінцівка дуги, дотична до W , залишається невизначеною. Тоді, можна лише сказати, що Y не є причи- ною для W , і що всі шляхи залежності між W та Y закінчуються дугою Y . Пропоновані засоби оптимізації пошуку сепараторів було реалізовано в алгоритмах серії “Razor”. Алгоритми Razor є асимптотично-коректними [7]. Робота розроблених алгоритмів була випробувана на широкому наборі струк- тур низької, середньої та помірно високої складності. Методологія оцінювання ефе- ктивності методів виведення каузальних моделей з даних викладена в [6, 7]. Результати випробувань показали пере- вагу алгоритмів Razor над базовим анало- гом PC за швидкодією (кількістю тестів) і за адекватністю відтворення каузальних зв’язків [6–8]. Перевага у швидкодії – очікувана (звуження секторів пошуку сепараторів тягне зменшення кількості тестів). А перевагу у точності (адекватно- сті) можна пояснити наступним. Фокусу- вання пошуку сепараторів відсікає ареали високого ризику помилок тестів. Тобто зазвичай відсікаються частини простору пошуку, де ризик помилкового прийняття незалежності – високий, а ризик втрати сепаратора – малий. Наведемо деякі результати випро- бування алгоритму версії Razor-1.2 на структурах байєсових мереж помірної складності. Генеративні моделі мали по 30 змінних, а кількість дуг варіювала від 60 до 120. Використані вибірки даних розміром 20000 записів. Показники кіль- кості тестів, виконаних у ході виведення деяких моделей, показано на рис. 4. Рис. 3. Каузальна мережа: а – генеративна модель; б – виведена модель б W Y X Q Z R а W Y X Q Z R U U Інтелектуальні інформаційні технології 106 Рис. 4. Порівняння Razor-1.2 та РС за кількістю тестів. Моделі з 30-ма дискретними змінними; кількість ребер – 90 та 120 Найскладнішою виявилася модель, імено- вана “BB55”. Для виведення її структури алгоритму РС знадобилося 27650 тестів, а алгоритму Razor-1.2 – 16950 тестів. У ході роботи алгоритма Razor-1.2 пра- вило «відсторонення» кандидата у сепа- ратор продуктивно спрацювало 132 рази. В середньому, Razor-1.2 працює у півтори рази швидше (за часом й за кількістю тестів). Важливо, що алгоритми серії Razor зменшують кількість тестів висо- кого рангу. Міру адекватності, забезпечувану алгоритмом, можна оцінити акуратністю алгоритму, тобто кількістю структурних помилок. Можна виділити різні типи помилок. Візьмемо тільки три з них: втрата ребра (в генеративній моделі є ре- бро, а у виведеній – немає); зайве ребро (навпаки); реверс ребра (орієнтація у зворотному напрямку). Реверс ребра є дуже небажаним, оскільки така структу- рна помилка не компенсується підбором- параметрів. Результати експериментів підсумовані у таблиці. Кількість помилок дана на одну модель. Групи моделей виділено згідно кількості дуг. Алгоритм Razor-1.2, на відміну від аналога, не при- пустив жодного реверсу ребра. Адекватність результатів роботи алгоритму в цілому можна оцінити «інте- гральним» показником. Каузальна про- дуктивність [7] визначена як пропорція кількості правильно відтворених кауза- льних дуг відносно суми кількості по- милкових дуг та кількості автентичних каузальних дуг у генеративній моделі. Ефективність алгоритмів за каузальною продуктивністю показано на рис. 5. У підсумку, алгоритм Razor-1.2 продемонс- трував втричі вищу каузальну проду- ктивність, ніж аналог. Отже, розроб- лений алгоритм перевершив аналог за обома основними показниками. Ці алго- ритми та втілені у них принципи є внес- ком у розвиток методів, базованих на не- залежності. B B 3 1 B B 3 2 B B 3 3 B B 3 4 B B 3 5 B B 3 6 B B 5 1 B B 5 2 B B 5 3 B B 5 4 B B 5 5 B B 5 6 Р1 0 5000 10000 15000 20000 25000 30000 Інтелектуальні інформаційні технології 107 Таблиця Оцінка параметрів та прогнозування каузального ефекту У байєсових мережах (та в неади- тивних моделях) роль параметрів вико- нують компоненти розподілу ймовірнос- тей ,..),\|( zxYp . В такому разі неясно, як виокремити вплив однієї змінної (окре- мого «батька»). Параметри характеризу- ють усю «родину» цілком. Така ж ситуа- ція виникає, коли форма залежності неві- дома й аналітик неспроможний ідентифі- кувати її. Якщо значення залежної змінної формується як сума впливів її причин (батьків), то «родина» описується як ади- тивна модель. В адитивних моделях кож- ній дузі приписується свій параметр. Найпоширенішим класом адитивних мо- делей є лінійні. Зрозуміло, якщо не вдається визна- чити орієнтацію дуги, то стає неможливим однозначно оцінити параметри відповідно- Група моделей PC Razor-1.2 Втрата ребра Зайве ребро Реверс ребра Втрата ребра Зайве ребро Реверс ребра 60 5,8 0,33 0,33 4 2,3 0 75 16,5 0,5 0 13 2,7 0 90 24,5 0,67 0 17,8 0,8 0 120 56,8 1,0 1,17 47,7 2,5 0 Рис. 5. Каузальна продуктивність алгоритмів; моделі з 30-ма дискретними змінними, впорядковані за тривалістю виведення Каузальна Продуктив. 0 5 10 15 20 25 30 35 40 45 50 B B 2 B B 4 B B 3 B B 5 B B 6 B B 1 B B 2 4 B B 2 2 B B 2 6 B B 2 1 B B 2 3 B B 2 5 B B 3 2 B B 3 4 B B 3 1 B B 3 5 B B 3 6 B B 3 3 B B 5 3 B B 5 2 B B 5 1 B B 5 4 B B 5 6 B B 5 5 * моделі П р о д ук ти в .( % ) Razor-1.2 PC Експертні та інтелектуальні інформаційні системи 108 го фрагмента моделі (список «батьків» не- відомий). У структурах, перенасичених зв’язками, неможливо навіть розпочати процес орієнтацій ребер. В разі латентної змінної задача оцінки відповідних параме- трів моделі стає ще більш проблематич- ною. У випадку лінійних моделей з’явля- ються додаткові можливості ідентифікації параметрів [1]. Коли і структура, і параметри іден- тифіковані, задачу прогнозу втручання на певну змінну можна розв'язати однознач- но. Будемо розглядати так званий «тоталь- ний» каузальний ефект. Відрізняють ще так званий «прямий» (безпосередній) кау- зальний ефект, який описує вплив виклю- чно через вказану дугу. Для оцінки кауза- льного ефекту, який справляє одна змінна на іншу, спеціалісти розробили техніку перерахунку ймовірностей в каузальній мережі [1, 2]. Повертаючись до ілюстративного прикладу з захворюванням на грип, пояс- німо відмінність прогнозу каузального ефекту від «пасивного прогнозу». Нехай у тому самому районі (місті) з наближенням несприятливого періоду в організаціях та фірмах проведено наступну профілактику серед працівників. На зібраннях перед працівниками виступили представники епідеміологічної служби, а потім було роз- повсюджено оплачені анти-грипозні пре- парати. В даній ситуації втручання (керу- вання) не є ідеальним, бо працівники не змушені вживати препарати, і кожна лю- дина враховує свої особисті обставини. І все ж таки внаслідок зазначених заходів буде частково розірвано (чи послаблено) зв'язок між застосуванням анти-грипозних препаратів де-факто та звичкою це робити. Тому за таким сценарієм, напевно, відсо- ток захворювань буде вже нижче серед тих, хто вживав препарати (а не вище). Отже, для заданої пари змінних каузаль- ний ефект та кореляція (до втручання) ма- ють протилежні знаки. Технічно, оцінка каузального ефек- ту змінної X на змінну Y відрізняється від «пасивного прогнозу» тим, що перед перерахунком ймовірностей треба видали- ти з моделі дуги, вістря яких дотичне до X , і які лежать на безколізорному шляху до Y в обхід дуги X Y . Замість перера- хунку ймовірностей на моделі можна ви- конати регресію, але до набору коваріат треба включити змінні, які блокують вка- зані безколізорні шляхи до Y в обхід дуги X Y [1, 2]. Іноді каузальний ефект втручання можна оцінити навіть там, де залишається невизначеність моделі. Буває, що попри невизначену орієнтацію дуги та неповну ідентифікацію параметрів можна спрогно- зувати каузальний («тотальний») ефект на основі даних. Наприклад, нехай, маючи модель рис. 3, б, потрібно визначити, як відіб’ється керування змінною X на змінній Y (ефект Y від маніпуляції на X ). В цій моделі орієнтації дуги Y —W невідома. Але достатньо знати, що W не є батьком для X . Несуттєво, чи тота- льний ефект формується виключно дугою YX  , чи в цей ефект робить внесок ланцюг через W . Оцінка )\|( xYp , обчи- слена з даних, дає адекватне значення ефекту для обох випадків. (Істинна орієн- тація дуги Y —W «автоматично» корек- тно врахована в сумісному розподілі ймо- вірностей змінних X , Y ). Сказане зали- шається правильним й у тому випадку, якщо асоціація між Y та W виникла як результат дії спільної прихованої причи- ни. Натомість для обчислення «прямо- го» (безпосереднього) каузального ефекту змінної X на змінну Y необхідно знати орієнтацію ребра Y —W . Все вищесказа- не рівною мірою чинне також для прогно- зування каузального ефекту X на W . Припустимо, що модель лінійна. Розглянемо задачу обчислення структур- ного коефіцієнту для каузального зв'язку XQ  та каузального ефекту, який спра- вляє Q на X . На шляху через R маємо невизначені кінцівки дуг, дотичні до змінної R . Але це не повинно зупинити аналітика. В ході виконання першої фази виведення (якщо відкинути можливість надзвичайних обставин) алгоритм знайде сепаратор }{Q,R для пари змінних XZ, . Це означає, що варіант колізора Експертні та інтелектуальні інформаційні системи 109 X  R Q треба виключити, цей шлях є ланцюгом. Так, каузальний зв’язок XQ  є конфаундований (сплутаний). Тому для оцінки структурного коефіцієн- ту та каузального ефекту для цієї дуги не- обхідно блокувати ланцюг через R . (Тре- ба виконувати регресію X на пару RQ, ). Отже, попри те, що модель залишає три можливі варіанти орієнтації дуг, дотичних до R , каузальний ефект Q на X (і відпо- відний параметр) однозначно ідентифіку- ється. Але якщо модель не є адитивною, то постають питання, як оцінити структу- рні параметри для каузального зв’язку XQ  (бо невідомий другий «батько» для змінної X ), і як розуміти каузальний ефект Q на X . Приклад виведення моделі з реальних даних Для аналізу причин та наслідків бідності й темпів народжуваності в краї- нах, що розвиваються, о зібрано й підго- товлено соціально-економічні дані [17]. Використовувалися дані Світового банку щодо 80-ти країн що розвиваються (включаючи Україну). Виходячи з при- пущення про лінійність залежностей, спо- чатку було обчислено матрицю парних коваріацій, а потім застосовано найбільш відомий алгоритм PC [2, 17]. Виведення моделі з тих самих даних було повторено [7] з використанням розроблений нами алгоритму Razor-1.2. Оскільки вибірка даних дуже мала (80 випадків), виведення було повторене кілька разів з різними рівнями значущості тестів незалежності («альфа» – від 0,05 до 0,1). Виведена структура показана на рис. 6. Стабільні зв’язки (ті, що присутні за всіх рівнів «альфа»), показані неперервними лініями. Зв’язки, присутні у результатах більшості експериментів, показані пункти- рно. Виявлено два каузальних зв’язки: (GDP$2) та ($2RU). У моделі присутні три стабільні суб-каузальні зв’язки: (AIGDP), (ILBR), (CMBR). Зв’язок $2 з BR виявився нестабільним щодо напрямку. Отже, згідно нашої моде- – + GI IT FA LE FR AI GDP RU UN $2 CM IL BR Рис. 6. Виведена модель факторів народжуваності й бідності Позначення показників: $2 – бідність_за_витратами (частка населення з витратами до двох дола- рів/день); GI – коефіцієнт Джині (індекс концентрації доходів); FR – індекс несвободи; AI – доходи сільського господарства; LE – тривалість життя; RU – частка міського населення; CM – дитяча смертність; IL – рівень неписьменності; GDP – величина прибутку сімейного господарства на душу населення; BR – народжуваність; UN – недоїдання; IT – міжнародна торгівля. FA – допомога ззовні; Експертні та інтелектуальні інформаційні системи 110 лі, GDP впливає на бідність за витратами, а через посередництво бідності, можливо, впливає на народжуваність. Згідно моделі, коефіцієнт Джині може впливати на GDP, але тільки через індекс несвободи. Коефі- цієнт кореляції для впливу GDP$2 дорі- внює -0,61. Тобто зростання GDP призво- дить до зменшення бідності (за витрата- ми). Коефіцієнт кореляції для зв'язку ($2RU) дорівнює +0,61. Цей коефіцієнт оцінює прямий каузальний вплив, бо гіпо- тетичний шлях між $2 та RU через GDP та UN напевно є колізорним. Отже, зростання бідності (за витратами) призводить до зро- стання частки міського населення. Згідно моделі, обидва вказані коефіцієнти адеква- тно оцінюють каузальний ефект. Оскільки в роботі [17] модель була виведена за допомогою алгоритму PC (який не відображає неповні орієнтації), отримані там результати відрізняються від наших. Але суперечностей немає. Обидві моделі згодні у тому, що GDP впливає на $2, і що безпосередніми факторами наро- джуваності, правдоподібно, є неписьмен- ність та дитяча смертність. Допоміжні та комплементарні засоби виведення та уточнення моделі Останніми роками сформувалися нові напрямки досліджень, що розширю- ють можливості відтворення моделей но- вими засобами, використовуючи інші ти- пи властивостей (не тільки марковські). Тим самим долається неспроможність традиційних методів розрізнити моделі в одному класі марковської еквівалентнос- ті. Забезпечується можливість розпізнати орієнтацію зв’язку, виходячи з характеру розподілення гамору [3]. Можна сказати, що використовується несиметрія сумісно- го розподілу пари змінних. (Зазначимо, що оригінальний спосіб використання не- симетрії розподілу двох дискретних змін- них для визначення напрямку впливу ра- ніше був запропонований у [18]. Хоча не було дано обґрунтування того способу). Співвідношення залежностей (не- рівності або рівності), характерні для пев- них структур моделей, дають нові засоби верифікації та уточнення моделі. Викори- стання співвідношень парних показників залежності, як більш надійний інстру- мент, може замінити тестування умовної незалежності. Особливо важливо, що ви- ведені обмеження можуть допомогти в ситуації з прихованими змінними, коли стандартні методи не працюють. Напри- клад, певні рівності підтримують вияв- лення прихованої спільної причини трьох, чотирьох чи більше змінних [19]. У роботі [20] знайдено нерівності для кореляцій в моделі; ці нерівності іноді можуть допо- могти розпізнати присутність певного зв’язку в моделі в ситуації неповної спос- тережуваності. Висновки Каузальні мережі та методи їх ви- ведення з емпіричних даних є відповіддю на потреби аналізу рішень та прогнозу наслідків керування в процесі плануван- ня. Такі моделі – гнучкі й зручні для застосування. Методи виведення структур залежностей та відкриття каузальних зв’язків знаходяться на передовому фрон- ті досліджень, розробок і технологій інформатики. Індукцію каузальної моделі можна застосувати для виявлення статистичних зв’язків у будь-якому середовищі (безвід- носно до фізичної чи матеріальної приро- ди виникнення тих зв’язків). Треба тільки ретельно зібрати достатньо даних. Мето- ди виведення каузальних мереж здатні ідентифікувати систему зв’язків настільки повно й точно, наскільки це дозволяють зібрані дані. Глибокий аналіз даних, вті- лений в розглянутих методах, за сприят- ливих обставин здатен відкривати при- чинно-наслідкові відношення без апріор- них знань про об’єкт дослідження. Розро- блені нами засоби підсилюють відомі ме- тоди і забезпечують підвищення адекват- ності каузальних моделей. Для каузаль- них мереж доступна техніка й процедури міркувань, що забезпечують практичне застосування моделей. Адекватність про- гнозу каузального ефекту (за допомогою моделі) пояснюється тим, що каузальна мережа акумулює вміст оброблених даних у формі знань, які надають механізм шви- дкої мобілізації потрібного «зрізу» («про- Експертні та інтелектуальні інформаційні системи 111 екції») даних для потенційно всіх запитів аналітика. Побіч того, каузальна мережа приваблює своєю наочністю, що стиму- лює візуальний «інсайт» аналітика і дос- лідника проблеми. 1. Pearl J. Causality: models, reasoning, and inference. Cambridge: Cambridge Univ. Press, 2000. 526 p. 2. Spirtes P., Glymour C., Scheines R. Causation, prediction and search. New York: MIT Press, 2001. 543 p. 3. Spirtes P., Zhang K. Causal discovery and inference: concepts and recent methodological advances. Applied Informatics. 2016. Vol. 3: 3. 28 p. 4. Андон Ф.И., Балабанов А.С. Выявление знаний и изыскания в базах данных: под- ходы, модели, методы и системы (обзор). Проблемы программирования. 2000. № 1–2. С. 513–526. 5. Андон Ф.И., Балабанов А.С. Структурные статистические модели: инструмент поз- нания и моделирования. Системні дослі- дження та інформаційні технології. 2007. № 1. С. 79–98. 6. Балабанов О.С. Відтворення каузальних мереж на основі аналізу марковських влас- тивостей. Математичні машини та сис- теми. 2016. № 1. С. 16–26. 7. Балабанов О.С. Каузальні мережі: аналіз, синтез та виведення з статистичних даних: Автореферат дис. … доктора фіз.-мат. наук. К.: Ін-т кібернетики ім. В.М. Глуш- кова НАНУ, 2014. 8. Balabanov O. S. On perspectives of causal networks reconstruction by independence- based methods. Proceedings of the 4th Intern. Conf. on Inductive Modelling (ICIM’2013). Kyiv, September 16–20, 2013. Kyiv, Ukraine. P. 139–142. 9. Балабанов О.С. Від коваріацій до каузаль- ності. Відкриття структур залежностей в даних. Системні дослідження та інфор- маційні технології. 2011. № 4 . С. 104–118. 10. Балабанов А.С. Логика минимальной сепа- рации в каузальных сетях. Кибернетика и системный анализ. 2013. № 2. С. 36–47. 11. Балабанов О.С. Правила підбору сепарато- рів в баєсівських мережах. Проблеми про- грамування. 2007. № 4. С. 33–43. 12. Балабанов А.С. Минимальные сепараторы в структурах зависимостей. Свойства и идентификация. Кибернетика и систем- ный анализ. 2008. № 6. С. 17–32. 13. Балабанов А.С., Гапеев А.С., Гупал А.М., Ржепецкий С.С. Быстрый алгоритм вывода структур байесовых сетей из данных. Про- блемы управления и информатики. 2011. № 5. С. 73–80. 14. Балабанов А.С. Индуцированная зависи- мость, взаимодействие факторов и дис- криминация каузальных структур. Кибер- нетика и системный анализ. 2016. № 1. С. 10–22. 15. Балабанов А.С. Формирование минималь- ных d-сепараторов в системе зависимо- стей. Кибернетика и системный анализ. 2009. № 5. С. 38–50. 16. Балабанов О.С. Прискорення алгоритмів відтворення баєсових мереж. Адаптація до структур без циклів. Проблеми програму- вання. 2011. № 1. С. 63–69. 17. Bessler D. A. On world poverty: its causes and effects. Food and Agricultural Organization (FAO) of the United Nations. – Research Bulletin. Rome. 2003. 50 p. 18. Балабанов О.С. Індуктивне відтворення деревовидних структур систем залежнос- тей. Проблемы программирования. 2001. № 1–2. С. 95–108. 19. Андон П.І., Балабанов О.С. До відкриття латентного бінарного фактора в статисти- чних даних категорного типа. Доповіді НАН України. 2008. № 9. С. 37–43. 20. Балабанов О.С. Про характерні співвідно- шення кореляцій в деяких системах ліній- них структуральних рівнянь. Доповіді НАН України. 2016. № 12. С. 17–21. References 1. Pearl J. (2000). Causality: models, reasoning, and inference. Cambridge: Cambridge Univ. Press. 526 p. 2. Spirtes P., Glymour C., Scheines R. (2001). Causation, prediction and search. New York: MIT Press. 543p. 3. Spirtes P., Zhang K. (2016). Causal discovery and inference: concepts and recent methodological advances // Applied Informatics. 3, (3). 28 p. 4. Andon P.I., and Balabanov O.S. (2000). Vyjavlenie znanij i izyskanija v bazah dannyh. Podhody, modeli, metjdy i sistemy. Експертні та інтелектуальні інформаційні системи 112 Problems in programming. 2000, (1–2). P. 513–526. [In Russian]. 5. Andon P.I., and Balabanov O.S. (2006). Structured statistical models: a tool for cognition and modeling. System Research and Information Technologies. 2006, (1). P. 79–98. [In Russian]. 6. 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. (2016). (1). P. 16–26. [In Ukraini- an]. 7. 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]. 8. Balabanov O.S. (2013). On perspectives of causal networks reconstruction by independence-based methods. Proc. of 4th Intern. Conf. on Inductive Modelling (ICIM’2013). Kyiv, September 16–20. Kyiv, Ukraine. P. 139–142. 9. Balabanov O.S. (2011). From covariation to causation. Discovery of structures of dependency in data. System Research and Information Technologies. (2011). (4). P. 104–118. [In Ukrainian]. 10. Balabanov O.S. (2013). Logic of minimal separation in causal networks. Cybernetics and Systems Analysis. 49. (2). P. 191–200. 11. Balabanov O.S. (2007). Rules for picking up separators in Bayesian networks. Problems in programming. (4). P. 33–43. [In Ukrainian]. 12. Balabanov A.S. (2008). Minimal separators in dependency structures: Properties and identification. Cybernetics and Systems Analysis. 44. (6). P. 803–815. 13. Fast algorithm for learning the Bayesian networks from data / A.S. Balabanov, A.S. Gapyeyev, A.M. Gupal, S.S. Rzhepetskiy. J. Automation and Information Sciences. (2011). 43. (10). P. 1–9. 14. Balabanov O.S. (2016). Induced dependence, factor interaction, and discriminating between causal structures. Cybernetics and Systems Analysis. 52 (1). P. 8–19. 15. Balabanov A.S. (2009). Construction of minimal d-separators in a dependency system. Cybernetics and Systems Analysis. 45. (5). P. 703–713. 16. Balabanov O.S. (2011). Accelerating algorithms for Bayesian networks recovery. Adaptation to structures without cycles. Problems in programming. (1). P. 63–69. [In Ukrainian]. 17. Bessler D.A. (2003). On world poverty: its causes and effects. Food and Agricultural Organization (FAO) of the United Nations. Research Bulletin. Rome, 2003. 50 p. 18. Balabanov O.S. (2001). Inductive recovery of structures of dependency trees. Problems in programming. (2001). (1–2). P. 95–108. [In Ukrainian]. 19. Andon P.I., and Balabanov O.S. (2008). On revealing a latent binary factor in categorical data. Reports of Nat. Acad. of Sciences of Ukraine. (9). P. 37–43. 20. Balabanov O.S. (2016). On the intrinsic relations of correlations in some systems of linear structural equations. Dopov. Nac. akad. nauk Ukr. [Reports of Nat. Acad. of Sciences of Ukraine]. (12). P. 17–21. Одержано 30.06.2017 Про автора: Балабанов Олександр Степанович, доктор фізико-математичних наук, провідний науковий співробітник. Кількість наукових публікацій в українських виданнях – 50. Кількість наукових публікацій в зарубіжних виданнях – 9. http://orcid.org/0000-0001-9141-9074. Місце роботи автора: Інститут програмних систем НАН України, 03187, м. Київ-187, проспект Академіка Глушкова, 40. Тел.: (044) 5263420. Е-mail: bas@isofts.kiev.ua

Knowledge discovery in data and causal models in analytical informatics

Репозитарії

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