=Paper=
{{Paper
|id=Vol-2866/ceur_392-406balabanov40
|storemode=property
|title=Відтворення каузальних моделей з даних. Проблеми адекватності структур з прихованими причинами
Causal Inference from Data. On Some Inadequacy Problems of Structures with Hidden Causes
|pdfUrl=https://ceur-ws.org/Vol-2866/ceur_392-406balabanov40.pdf
|volume=Vol-2866
|authors=Olexandr Balabanov
|dblpUrl=https://dblp.org/rec/conf/ukrprog/Balabanov20
}}
==Відтворення каузальних моделей з даних. Проблеми адекватності структур з прихованими причинами
Causal Inference from Data. On Some Inadequacy Problems of Structures with Hidden Causes==
https://ceur-ws.org/Vol-2866/ceur_392-406balabanov40.pdf
УДК 004.855:519.216
ВІДТВОРЕННЯ КАУЗАЛЬНИХ МОДЕЛЕЙ З ДАНИХ.
ПРОБЛЕМИ АДЕКВАТНОСТІ СТРУКТУР
З ПРИХОВАНИМИ ПРИЧИНАМИ
О.С. Балабанов[0000-0001-9141-9074]
Інститут програмних систем НАН України, 03187, м. Київ-187, проспект Академіка Глушкова, 40.
Аналізується надійність відтворення каузальних моделей зі статистичних даних методами, основаними на незалежності.
Показано механізми виникнення неадекватності моделі внаслідок недосконалості та неповноти емпіричних даних.
Розкрито специфічні проблеми виведення (розпізнавання) спрямованості впливів між змінними в ситуації, коли деякі
причини є прихованими. Виявлено некоректність відомого правила виведення спрямованості (орієнтації) зв'язків в умовах
прихованих змінних. Запропоновано корекцію розглянутого правила для уникнення можливих помилок.
Ключові слова: каузальна мережа, орієнтація ребер, умовна незалежність, d-сепарація, колізор, ланцюг.
Анализируется надежность восстановления каузальных моделей из статистических данных методами, основанными на
независимости. Показаны механизмы возникновения неадекватности модели вследствие несовершенства и неполноты
эмпирических данных. Раскрыты специфические проблемы вывода (распознавания) направленности влияний между
переменными в ситуации, когда некоторые причини являются скрытыми. Выявлена некорректность известного правила
вывода направленности (ориентации) связей в условиях скрытых переменных. Предложена коррекция рассмотренного
правила для исключения возможных ошибок.
Ключевые слова: каузальная сеть, ориентация ребер, условная независимость, d-сепарация, коллайдер, цепь.
We attempt to clarify some subtle issues in causal inference from empirical data by independence-based methods when hidden
causes are allowed. Specifically, some unreliability and incorrectness problems of edge orientation in causal network under causal
insufficiency are detected.
The known rule for edge orientation (named “R4”), which have been proposed for ancestral graph models, is examined.
Incorrectness of the “R4” rule is revealed. We argue that the rule may fail in the sense it sometimes produces result which means
“variable X is cause of Y”, whereas edge between X and Y has arisen due to hidden common cause of both X and Y. The correction
to the rule is suggested which allows to retain model adequacy. So far as we know, the justification of the “R4” rule has been built
upon the requirement that inferred model should fall into the class of ancestral graph. We examine why one should expect the
ancestrality of inferred model when a generative model is not ancestral. We suggest that given Markov properties plus background
knowledge of certain type as inputs, a standard algorithm can produce an model which is not ancestral.
Next we examine the reliability of standard algorithms when they are given results of independence tests which use realistic data
samples. The version of the Causal faithfulness assumption, named “stability of two-edge dependence assumption” is formulated.
This assumption is sufficient to ensure reliability of known basic rules for edge orientation (the “collider rule” and the “post-collider
rule”). In contrast, the “R4” rule as well as its corrected version appeared unreliable under the stability of two-edge dependence
assumption. In particular, we demonstrated that in the case when dependence via a chain of three edge length is statistically
insignificant, the “R4” rule (and its corrected version too) produces wrong result. Thus a strongest assumption (“stability of three-
edge dependence”) is needed. Similarly, we demonstrated that in the case of the unfaithfulness of said type, standard algorithms
(without background knowledge in the input) can infer non ancestral model.
Key words: causal network, edge orientation, conditional independence, d-separation, collider, chain.
Вступ
В широкому спектрі досліджень з глибокого аналізу даних одне з провідних місць посідає проблема
відтворення генеративних і предиктивних моделей, а також каузальних мереж. Каузальні мережі можна
вважати предиктивними і водночас генеративними моделями в сильному сенсі, оскільки вони структурно
описують процес генерації змінних і претендують на адекватне відображення процесу розгортання відповідних
характеристик у середовищі. За умов адекватності каузальна мережа придатна для прогнозування наслідків
планованих дій (наприклад, виконання рішень менеджера). Водночас ці моделі є багатоцільовими, оскільки
дозволяють оперативно обирати цільову змінну і адаптуватися до будь-якого формату запиту (без потреби
повторно виводити модель) [1–3].
Каузальна мережа – це модель залежностей між змінними (заданого набору), яка описує структуру
спрямованих впливів (зазвичай – в умовах неповної спостережуваності). Кожна змінна відображена вершиною
мережі, а кожний статистичний зв'язок відображено ребром. Каузальна мережа описується як пара ( G , ), де
G – граф, що специфікує структуру моделі, – параметри, прив'язані до G , які описують кількісний аспект
моделі. Як правило, застосовуються моделі зі структурою без орієнтованих циклів (орграф G – ациклонний).
Якщо граф G моделі є ординарним орграфом, тобто утворений з одно-орієнтованих ребер (і є ациклонним), то
модель ( G , ) називаємо оАОГ-моделлю. Параметри оАОГ-моделі – це сукупність локальних параметрів,
заданих для кожної змінної. Наприклад, для мережі, що показана на рис. 1, група параметрів, причетна до
Copyright © 2020 for this paper by its authors. Use permitted under Creative 393
Commons License Attribution 4.0 International (CC BY 4.0).
змінної Y , специфікує рівняння y f( x, z, v ) Y . (В даному разі маємо адитивний гамір Y , але це не
обов'язково.) В загальному випадку поведінка змінної описується у формі умовного розподілення p (Y | (Y )) ,
де (Y ) – це сукупність «батьків», тобто безпосередніх причин змінної Y .
Якщо модель повністю специфіковано, тобто однозначно визначено структуру G та параметри (а
терми гамору X , Y , Z , v ,.. є взаємонезалежними), задача обчислення прогнозу (в тому числі й прогнозу
ефекту втручання в об'єкт моделювання) розв'язується однозначно [1, 2]. Але строго кажучи, результатом
виведення моделі з даних (коли на вході не задано апріорних знань та обмежень) завжди є клас марковської
еквівалентності моделей [1, 2]. Це означає, що деякі (або навіть всі) ребра графу моделі не мають однозначної
орієнтації, тобто спрямування відповідних статистичних зв'язків залишається не визначеним. Припустимо, в
структурі моделі змінні X та Y поєднані ребром, але невідомо, яка з цих змінних є батьком для іншої. Тоді для
змінних X та Y неможливо однозначно обчислити локальні параметри моделі, а також неможливо однозначно
розв'язати задачу каузального прогнозу (тобто прогнозу наслідків втручання в об'єкт) для X , Y та деяких
інших змінних.
Ситуація далі ускладнюється, коли треба відтворити модель в умовах латентних (прихованих) змінних,
тобто коли в заданому наборі даних відсутні такі змінні, що кожна з них впливає одночасно на кілька
спостережуваних змінних. В такому разі постає проблема: як описати структуру моделі без явної присутності
деяких змінних? Тоді структура моделі, отримана в результаті виведення з даних, може зазнати певних
деформацій та викривлень (відбиток прихованих змінних).
Q J
R X W T
L Z Y U
C V
Рис. 1. Приклад каузальної мережі
Задача відтворення моделі з прихованими змінними в загальному випадку, наскільки відомо автору, не
ставилася. Поширені методи спираються на апріорні знання та обмеження. В доповіді не будемо розглядати
задачу відтворення зв'язків між прихованими змінними (це відволікло би від предмету дослідження). Тобто
постулюємо, що кожна прихована змінна контактує тільки з спостережуваними змінними моделі.
Часто розв'язати задачу каузального прогнозу дуже важко. В багатьох ситуаціях коректна опція –
визнати неможливість розв'язати задачу. Неприпустимо видати некоректний каузальний прогноз, а це може
статися, зокрема, внаслідок того, що ребра графу моделі орієнтовані невірно. В доповіді виявлено деякі
механізми виникнення структурної неадекватності каузальних моделей, відтворених з даних спостережень
стандартними методами. Також висвітлено неясності щодо інтерпретації результатів виведення і показано
шляхи подолання певних проблем. Зокрема, буде показано, що (у певних умовах) відомі правила визначення
орієнтації ребер дають неадекватний результат. Запропоновано варіанти корекції ненадійних правил
орієнтації ребер.
1. Базові визначення. Сепарація і незалежність
Зафіксуємо елементарні визначення. В генеративній моделі (яка описує джерело даних) та в адекватній
каузальній мережі безпосередні зв'язки відображаються (одно)орієнтованими ребрами X Y . Задній (лівий)
кінець ребра X Y називають «хвіст», а передній (біля Y ) – «вістря». Коли модель виводиться за умов
існування прихованих змінних, знадобляться також біорієнтовані (двобічно-орієнтовані) ребра X Y (з двома
вістрями). Таке ребро дозволяє відобразити вплив прихованої змінної на X та Y . (Відзначимо, що в моделях
можуть використовуватися також ребра вигляду X — Y , неорієнтовані за своєю природою, тобто ребра
симетричної залежності. В каузальних моделях симетричні ребра виникають внаслідок селекції вибірки даних
за значеннями залежної змінної. В доповіді вони не розглядаються.)
Оршлях (строго орієнтований шлях) – це шлях з ребер, орієнтованих в одному напрямку, без повторення
вершин, тобто A B C .. W . За наявності такого оршляху змінна A є предком (пращуром) змінної W ,
а змінна W є нащадком змінної A .
Фрагмент вигляду X Y Z зветься колізором (коллайдером, a collider). Цей колізор зветься
шунтованим, якщо у графі є ребро між X та Z`, інакше – не-шунтованим. При цьому вершина Y зветься
колізорною на кожному шляху, частиною якого є колізор X Y Z . Можливі чотири варіанти колізора:
X Y Z ; X Y Z ; X Y Z ; X Y Z .
394
Безколізорний шлях (або ланцюг) – це шлях без повторення вершин, на якому немає жодного колізора.
Цикл – це шлях, де перша й остання вершина тотожні. Циклон – це строго орієнтований цикл. Очевидно,
відсутність циклонів тотожна відсутності циклів без колізорів.
Каузальна мережа в першу чергу характеризується своїми марковськими властивостями. Всі марковські
властивості моделі визначаються виключно структурою моделі, тобто вони інваріантні до параметризації
моделі. Загально відома проста форма марковської властивості: якщо маємо модель зі структурою A B C ,
то чинна умовна незалежність змінних A та C` за умови B`. (Можна сказати, що змінна B` сепарує A та C.)
` Але
визначення (багатовимірних) марковських властивостей для каузальних мереж потребує витонченого апарату,
оскільки структура каузальної мережі має складну «топологію». Всі факти марковської умовної незалежності
можуть бути зчитані з графу G моделі за допомогою критерія d-сепарації (визначається далі). Позначатимемо
предикатом DS( X ; S; Y ) той факт, що множина вершин S d-сепарує вершини X та Y`. Позначатимемо факт
умовної незалежності змінних X та Y` за умови S термом Ind( X ; S; Y ) . Зокрема, коли умова порожня,
застосовуємо позначення Ind( X ;{};Y ) або просто Ind( X ; ; Y ) .
Відомо [3], що в кожній каузальній мережі виконується імплікація у вигляді
DS( X ; S; Y ) Ind( X ; S; Y ) .
Цю імплікацію іноді називають теоремою семантики каузальних мереж. Марковські властивості моделі зі
структурою G визначаються критерієм d-сепарації [1].
Визначення 1 (d-сепарація, розгорнуте формулювання).
(а) Шлях в орграфі G називають d-перекритим (d-блокованим) за допомогою (кондиціонування)
множини вершин S , якщо і тільки якщо: 1) на шляху існує фрагмент Z , з тим, що Z S , або 2) на шляху
лежить хоча б один фрагмент * Y * (колізор), причому Y S й немає жодного оршляху вигляду
Y T , де T S .
(б) Якщо всі шляхи між вершинами X та Y` d-перекриті (або немає жодного шляху між X та Y`), то
вершини X та Y` є d-сепаровані.
(в) Шлях, який не є d-перекритим, є d-відкритим.
(г) Якщо за кондиціонування множини S в орграфі G існує принаймні один d-відкритий шлях між X
та Y`, то вершини X та Y` d-з'єднані.
Коментар. Якщо чинне DS(X ; S;Y ) , то кажемо, що множина S є d-сепаратором для пари вершин X , Y`.
(Зрозуміло, що застережене X , Y S .) В описі колізора * Y * використана позначка «*», яка є
еквіпотентним символом кінця ребра, який може бути конкретизовано або як «вістря», або як «хвіст». Тим
самим враховано структури з біорієнтованими ребрами. Строго кажучи, визначення d-сепарації – це пункти (а)
та (б); саме вони є основою для строгих висновків. Пункти (в) та (г) – це трактовка випадків, коли критерій d-
сепарації не задоволено, тобто коли маємо DS( X ; S; Y ) . Наслідки невиконання d-сепарації – менш
категоричні.
Пункт «а,1» критерію d-сепарації легко зрозуміти. Якщо вершини X та Y` поєднані ланцюгом, то щоб
перекрити цей ланцюг, треба заблокувати якусь вершину на ньому. Пункт «а,2» критерію d-сепарації є
нетривіальним і витонченим. Сенс цього пункту можна прокоментувати наступним чином. Нехай шлях має
вигляд X Y Z . За порожньої умови шлях d-перекритий. Але якщо в ролі умови використати вершину
Y`, шлях перестає бути d-перекритим (тобто стає d-відкритим). Розглянемо для прикладу рис. 1. В
зображеній структурі для пари вершин X , Z чинне наступне: DS( X ; ; Z ) , DS( X ; R; Z ) , DS( X ;{R,U }; Z ) .
Неформально кажучи, блокування R зробило X та Z d-сепарованими, але введення вершини U в набір
блокованих вершин відкрило інший шлях між X та Z . Сенс такого феномену стає зрозумілим, коли від
графової сепарації переходимо до відношень умовної незалежності у розподіленні ймовірностей, яке відповідає
структурі моделі. Нехай маємо порожню умову S . Тоді наступні два факти еквівалентні: 1) вершини A та
B` є безумовно d-з'єднані ( DS( A; ; B) ); 2) між вершинами A та B` є принаймні один ланцюг.
Імплікація (1) разом з критерієм d-сепарації дозволяє описати всі марковські властивості моделі. Можна
переписати (1) в еквівалентній формі як
Ind( X ; S; Y ) DS( X ; S; Y ) ,
що читається: «якщо є залежність, то мусить бути відповідний не-перекритий шлях в структурі». Залежність
між змінними утворюється декотрим механізмом, і той механізм відображається відкритим шляхом у графі
моделі. Критерій d-сепарації та теорема семантики (1) не дають висновків з факту DS( X ; S; Y ) . Невиконання
d-сепарації є тільки необхідною умовою для виникнення ймовірнісної (статистичної) залежності.
В доповіді розглядаються методи відтворених каузальних моделей, основані на незалежності [2, 4, 5].
Для обґрунтування таких методів (втім, як й інших) необхідне додаткове припущення. Було би зручно, аби
Copyright © 2020 for this paper by its authors. Use permitted under Creative 395
Commons License Attribution 4.0 International (CC BY 4.0).
кожна умовна незалежність, знайдена в процесі виведення моделі, була марковською. Інакше кажучи, бажано,
щоб знайдену умовну незалежність можна було безпомилково трактувати як відсутність відкритого шляху
(зокрема, ребра). Таке припущення в найбільш загальній і категоричній формі виглядає як наступна імплікація
Ind( X ; S; Y ) DS( X ; S; Y ) .
Ця імплікація зветься припущенням Каузальної не-оманливості (ПКнО), в оригіналі – Causal faithfulness
assumption [2]. Можна переписати ПКнО в наступній формі
DS( X ; S; Y ) Ind( X ; S; Y ) .
Для розуміння подальшої аргументації доцільно звернутися до розподілення ймовірностей змінних, яке
відповідає структурі моделі. Якщо маємо оАОГ-модель ( G , ) з множиною змінних U , то з критерію
d-сепарації та теореми семантики (1) випливає, що сумісне розподілення ймовірностей змінних U описується
формулою
p (U ) p ( X | ( X )) .
X U
В розподіленні p ( U ) виконуються всі марковські умовні незалежності. У випадках, коли критерій
d-сепарації дає негативну відповідь, тобто коли маємо DS( X ; S; Y ) , відповідна умовна незалежність не
випливає з теореми семантики (1). Більш того, в такому випадку, навпаки, чинна умовна залежність (за
виключенням особливих ситуації). Саме ця логіка («якщо для нетривіальної події немає умов й підстав, вона не
стається») виражена припущенням Каузальної не-оманливості. Наприклад, якщо маємо шлях X Y Z , то
згідно пункту «а,2» критерію d-сепарації буде DS( X ; Y ; Z ) , а згідно ПКнО (4) буде Ind( X ; Y ; Z ) . І дійсно, в
такій ситуації в більшості практичних випадків буде спостерігатися статистична залежність між X та Z (за
умови Y ) . Це так звана індукована або провокована залежність [6]. Більш того, подібна провокована
залежність між X та Z (за умови Q ), як правило, буде спостерігатися в моделі, яка складається з фрагментів
X Y Z та Y V W Q . В даному разі провокація залежності здійснюється, так би мовити,
«дистанційно».
Але за певних обставин у розподіленні p ( U ) , побіч марковських умовних незалежностей, можуть також
виконуватися інші (не-марковські, «неочікувані») умовні незалежності. Тоді ПКнО (4) порушується. Втім, всі
порушення припущення Каузальної не-оманливості в «модельному» (теоретичному) розподіленні p ( U ) можна
вважати особливими випадками. (Такі випадки мають нульову міру Лебега.)
Відомі наступні типові різновиди порушення припущення Каузальної не-оманливості: невиконання
транзитивності на ланцюгу; взаємна анігіляція паралельних впливів; «масковані» ребра. Невиконання
транзитивності на ланцюгу означає, приміром, що маємо фрагмент моделі X Y Z W , де спостерігається
Ind(Y ; ;W ) та(або) Ind( X ; ;W ) . Феномен «маскованого» ребра [6] маємо у випадку, коли в генеративній моделі
є колізор X Y Z , причому чинне DS( X ; ; Z ) , і водночас спостерігається факт Ind(X ; ;Y ) або Ind(Z;;Y ) .
Обидва вказані випадки порушення ПКнО можливі в моделях з дискретними змінними (з відповідними
наборами параметрів). Натомість в моделях з неперервними змінними легко побудувати модель з синдромом
взаємної анігіляції паралельних впливів, коли (наприклад) в моделі присутні фрагменти X Q Y та
X Z W Y , і виконується Ind(X ; ;Y ) .
Загальна констатація: в «модельному» розподіленні ймовірностей змінних кожна незалежність, не
санкціонована структурно, є нестійкою, тобто зникає внаслідок навіть незначних змін значень параметрів.
Проте картина суттєво змінюється, коли від «модельного» розподілення ймовірностей переходимо до
вибіркових розподілень. Мається на увазі ситуація, з якою стикається алгоритм виведення моделі з вибірки
даних. Тоді синдром, який можна назвати «майже порушенням» припущення Каузальної не-оманливості,
породжує реальні проблеми. Про це – в наступному розділі.
2. Принципи відтворення каузальних структур з даних. Ризики помилок
Результати доповіді стосуються методів, основаних на незалежності. Стандартними методами й
алгоритмами цього напрямку є PC, FCI на їхні модернізовані версії [2, 4, 5, 7]. Робота типового алгоритму
використовує емпіричні дані D і здійснюється у наступні етапи:
1) відтворити сукупність ребер моделі, тобто верифікувати ребро для кожної пари змінних, відшукуючи
сепаратор.
2) ідентифікувати спрямування ребер (орієнтувати ребра), спираючись на аналіз паттернів сусідніх
зв'язків.
3) обчислити параметри моделі відповідно до виведеної структури.
396
На першому етапі алгоритм шукає емпіричний сепаратор (аналог d-сепаратора) для кожної пари змінних
X , Y`, тобто такий набір змінних S , що чинне Ind( X ; S; Y ) . Умовна незалежність Ind( X ; S; Y ) фіксується, якщо
тест відповідного формату не спростував гіпотезу незалежності. Емпіричні дані D містять вибірковий ухил.
Тому навіть якщо структура генеративної моделі санкціонує незалежність Ind( X ; S; Y ) , між X та Y` напевно
буде «слабка» (не тісна) статистична залежність завдяки вибірковому ухилу. Звісно, не виключено, що
вибірковий ухил може бути настільки великим, що його наслідком буде сильна залежність, яка суперечить
факту d-сепарації та теоремі семантики. Але шанси наразитися на таку халепу є реальними тільки в малих
вибірках, коли треба взагалі відмовитися від наміру вивести модель.
Отже, для того, щоб модель на виході алгоритму мала щонайменше помилкових ребер, здоровий глузд
диктує, щоб слабка статистична залежність трактувалася як незалежність. (Тобто треба прагматично обрати
альфа-рівень тестів незалежності [2, 8].) Але така тактика водночас призводить до ризиків помилок іншого
типу, а саме, до того, що слабка «легітимна» залежність буде трактована як незалежність. Найпростіше це
пояснити на прикладі безумовної залежності. Якщо між вершинами X та Y` є принаймні один ланцюг, то маємо
DS( X ; ; Y ) . Тоді факт Ind( X ; ; Y ) майже неможливий і суперечить припущенню Каузальної не-оманливості.
Але припущення Каузальної не-оманливості може в строгому сенсі не порушуватися, і водночас залежність між
X та Y` може виявитися настільки слабкою, що тест не відкине гіпотезу незалежності. (Таку подію можна
назвати «майже порушенням» припущення Каузальної не-оманливості.) Правдоподібність таких випадків тим
більша, чим довше ланцюг між X та Y`.
Трактування слабкої залежності як незалежності не обов'язково призводить до помилок алгоритму.
Більше того, в багатьох випадках «майже порушення» ПКнО навіть сприяє зниженню обчислювальної важкості
відтворення моделі (не створюючи помилок). Наприклад, нехай в генеративній моделі є ланцюг
R Q V W Z , і вершина R не поєднана ребром ані з V , ані з W , ані з Z , і маємо такі результати
тестування: гіпотеза безумовної незалежності R та Z утримана (не спростована), і також утримані гіпотези
безумовної незалежності R та W , R та V . Такі результати тестів санкціонують вірні висновки (що відповідних
ребер немає) і водночас дозволяють уникнути «зайвих» тестів умовної незалежності. (Втім, треба зауважити,
що в багатьох алгоритмах виведення моделі утримання (не відмітання) гіпотези незалежності R та V в такій
ситуації призведе до невірної орієнтації ребер.)
Згадаємо також явище взаємної «майже анігіляції» паралельних впливів. Припустимо, генеративна
модель містить фрагменти X Z Q Y та X V Y . Вплив X на Y` вздовж обох вказаних шляхів
може бути сильним. Але внаслідок взаємодії (накладення) цих впливів залежність між X та Y` може виявитися
слабкою. В результаті матимемо Ind(X ;;Y ) , що дозволить уникнути відповідних тестів на першому етапі
алгоритму виведення моделі. Проте якщо ситуація буде іншою, а саме, замість шляху X V Y в
генеративній моделі буде присутнє ребро X Y , то результат тесту у вигляді Ind(X ;;Y ) призведе до помилки.
Прокоментуємо також феномен «дистанційної провокації» залежності. Припустимо, генеративна модель
складається з фрагментів X Y Z та Y V W . Критерій d-сепарації дає DS( X ; Y ; Z ) , ..,
DS( X ;W ; Z ) . Втім, легко зрозуміти, що чим довшим буде шлях від Y до W , тим слабшою має стати
статистична залежність між X та Z , провокована умовою W .
Наведена аргументація дозволяє зробити висновок, що для обґрунтування методів і алгоритмів
виведення моделі (та аналізу їх надійності) потрібно, на додачу до ПКнО (3), сформулювати прагматичні
варіанти припущення Каузальної неоманливості. А саме, необхідно запропонувати припущення, яке, замість
поняття «теоретична» залежність, оперує поняттям «достатньо сильна», статистично значуща залежність. Таке
поняття потребує уточнення. Втім, можна означити це поняття «концептуально», чи радше б сказати, відносно.
Наприклад: значуща залежність – це залежність, яка виявляється тестом з надійністю того ж порядку, що і
«типова» безумовна реберна залежність. Треба домовитися, що в аналізі будемо мати на увазі «акуратні тести»
незалежності. Акуратний тест незалежності – це такий тест, що виконується над статистичною вибіркою даних
типового (достатнього) розміру, з адекватним рівнем відхилення гіпотези альфа і адекватною технікою
обчислення тестової статистики.
Акуратний тест незалежності не відмітає гіпотезу незалежності (позитивний результат тесту) майже
завжди, коли чинна теоретична незалежність. Таку домовленість можна виразити через нестрогу імплікацію:
~ Ind ( X ; S; Y ) isn’t rejected],
X , Y , S : [ Ind( X ; S; Y ) Emp
де Ind Emp (*;*;*) означає «емпіричну» незалежність, яка тестується за допомогою акуратного тесту з
використанням реалістичної (достатньої) вибірки даних. У випадках, коли імплікація не виконується, маємо
помилку першого роду. (Нагадуємо, що X , Y S .)
Водночас, акуратний тест незалежності має забезпечувати негативний результат тесту у багатьох (всіх
критичних) випадках, коли чинна теоретична залежність. Характеристика таких випадків залежності і є
предметом прагматичних варіантів припущення Каузальної неоманливості. (Реальність проблеми така, що
Copyright © 2020 for this paper by its authors. Use permitted under Creative 397
Commons License Attribution 4.0 International (CC BY 4.0).
необхідно знайти рівень тесту альфа, який забезпечить компроміс між ризиком помилкового відмітання
гіпотези незалежності та ризиком помилкового утримання незалежності.)
Імплікацію (6) можна назвати прагматичним постулатом тестування незалежності. Для практики
виведення моделі часто можна задовольнятися й послабленою формою прагматичного постулату тестування
незалежності, замінивши квантор все-загальності в (6) на іншу форму узагальнення. Зрозуміло, немає особливої
потреби розглядати такі факти незалежності, де в ролі S використовуються вочевидь надмірно складні
множини. Наприклад, прагматичний постулат тестування незалежності можна уточнити так:
~ Ind ( X ; S; Y ) isn’t rejected,
Ind( X ; S; Y ) Emp
де S – це набір змінних, сформований згідно вимог до членів локально-мінімальних сепараторів для
пари X,Y` [9, 10].
Далі фрази «.. Ind Emp ( X ; S; Y ) вірне (або виконується)..» означатимуть, що гіпотеза незалежності змінних
X та Y` за умови S не відмітається (результат тесту – позитивний).
Буквальна трактовка припущення Каузальної неоманливості в емпіричному сенсі мала б означати, що
алгоритм покладається на виконання імплікації:
X , Y S : DS( X ; S; Y ) [ Ind Emp ( X ; S; Y ) is rejected].
Таке припущення можна назвати припущенням повної практичної Каузальної неоманливості. Зрозуміло, що
таке припущення є нереалістичним. Більш того, в ньому немає необхідності. Для обґрунтування коректності
методів виведення моделі можна задовольнятися й менш жорсткими припущеннями.
Зокрема, пропонуємо дві важливі та необхідні версії прагматичного припущення Каузальної не-
оманливості. Первинне припущення можна сформулювати так:
Якщо в генеративній моделі присутнє ребро X Y , то всі тести умовної незалежності у форматі
Ind Emp ( X ; S; Y ) для всіх умов S відметуть (спростують) гіпотезу незалежності.
Це припущення можна назвати припущенням стабільності реберної залежності (ПСРЗ) й закодувати у
формі правила:
( X Y ) S( X , Y S) : Ind Emp ( X ; S; Y ) is rejected.
Зрозуміло, що в деяких випадках (коли ребро «слабке») це припущення буде порушуватися. (Подібні випадки
називають помилками другого роду.) З ризиком порушення (8) доведеться примиритися з огляду на
необхідність вищезазначеного компромісу між помилками двох родів. Можна сказати, що припущення (8) вірне
для «типових» ребер. Зрозуміло, це поняття недостатньо конкретне, але це плата за абстрагування від
кількісного аспекту моделі. Треба ж якось характеризувати загальні умови, в яких працює алгоритм аналізу
статистичних даних, отриманих з невідомої генеративної моделі.
Наступна важлива (й більш жорстка) версія прагматичного припущення Каузальної неоманливості –
припущення підсиленої стабільності двох-реберної залежності (ППС2РЗ). Воно формулюється наступним
чином: якщо в моделі присутній ланцюг X Y Z , і якщо Y S , то гіпотеза Ind Emp ( X ; S; Y ) буде
відметена. Припущення можна закодувати у формі правила:
X Y Z S(Y , X , Z S) : Ind Emp ( X ; S; Z ) is rejected.
(Конструкція X Y Z репрезентує варіанти X Y Z , X Y Z та X Y Z .) Інакше
кажучи, якщо в моделі присутній ланцюг X Y Z , то змінні X та Z будуть взаємозалежними, допоки в
умову тесту не включено змінну Y`. Характеристика «підсилена» в назві припущення означає, що в припущенні
охоплено й ланцюги вигляду X Y Z . Оскільки в дійсності за біорієнтованим ребром стоїть два ребра (що
йдуть від прихованої змінної), то в генеративній моделі ланцюг, описаний як X Y Z , має три ребра. (Крім
того, зв'язок через приховану змінну може бути не розпізнаний і описаний як ребро типу X Y або X Y .)
Записати в назві припущення «..трьох-реберної залежності..» було б неправильно, бо тоді припущення
претендувало би на ланцюги вигляду X Y Z W чи навіть A B C D . А це вже більш жорстке
припущення. А що стосується випадку X Y Z , то тут залежність між X та Y можна прирівняти до
реберної, оскільки вона де факто проявилася емпірично, тобто достатньо сильна. (Там, де залежність між двома
змінними через приховану спільну причину слабка, відповідне біорієнтоване ребро просто не з'явиться у
виведеній моделі, і не буде предмету для припущень і міркувань.)
Не знижуючи ефективності ППС2РЗ, можна зменшити ризики порушення потрібного припущення,
уточнивши формулювання наступним чином: «..причому множина S містить тільки необхідні елементи для
того, щоб d-перекрити всі шляхи між X та Z`, окрім шляху через Y`». Можна обмежити множину S у інший
398
спосіб, наприклад, застерегти, щоб S включала тільки змінні, залежні від X або Z`. Також можна обмежити
кардинальність множини S . Надійна версія припущення підсиленої стабільності двох-реберної залежності
може бути сформульована як імплікація вигляду
X Y Z & Ind(X ;Y ; Z ) Ind Emp ( X ; ; Z ) is rejected.
Але таке припущення буде достатньо корисним тільки для дуже простих моделей.
Разом з припущенням підсиленої стабільності двох-реберної залежності є необхідність прийняти й
комплементарне припущення щодо провокованої (індукованої) залежності через колізор. Оскільки
вищенаведені припущення не гарантують залежності через довгий ланцюг (довший за два ребра), то логічно
також не гарантувати «дистанційної» провокації залежності. Отже, припущення стабільності елементарної
провокованої залежності (комплементарне до (9′)) формулюється наступним чином
X Y Z & Ind(X ; ; Z ) Ind Emp ( X ;Y ; Z ) is rejected.
Як коментар до (9″), зауважимо: якщо за чинності умов X Y Z & Ind(X ; ; Z ) кондиціонувати не
саму Y , а її дитину чи нащадка Q , то гіпотеза незалежності Ind Emp ( X ; Q; Z ) може бути або утримана, або
відметена. (Припущення (9″) про це нічого не каже).
Деякі інші версії прагматичного припущення Каузальної неоманливості наведено в [8, 11]).
На другому етапі типового методу виведення моделі, основаного на незалежності, виконується
орієнтація ребер. Результат першого етапу алгоритму – це «кістяк» моделі, тобто граф із ребер невідомого
спрямування. Ребро такого типу описується як конструкція X Y , де кільце « » біля вершини означає
невизначений кінець ребра. Процес орієнтації ребер починається з розпізнавання не-шунтованих колізорів, що
виконується наступним правилом 0 .
Правило колізорної орієнтації ребер ( 0 ):
( X — Y — Z ) & S ( Y , X , Z S ): Ind Emp ( X ; S; Z ) X Y Z . (10
Після вичерпного застосування правила 0 алгоритм переходить до наступного правила орієнтації ребер.
Правило пост-колізорної орієнтації ребер ( 1 ):
( X Y Q ) & Ind Emp ( X ; S; Q ) & Y S X Y Q .
Коректність правил 0 та 1 тримається на припущенні стабільної двох-реберної залежності (9). Більш
того, можливість виявлення прихованої змінної також обґрунтовується цим припущенням.
В умовах інших відомих правил орієнтації ребер прописані ребра з «вістрями», тому ті правила можуть
працювати тільки після правила 0 . Деякі інші правила орієнтація ребер розглянемо далі. В [12] показано, що в
класі оАОГ-моделей набір з правил (10), (11) та ще двох правил є повним. Додаткове п'яте правило потрібне
тільки за наявності апріорних знань про орієнтації ребер. Для класу моделей з прихованими змінними також
встановлено повний набір правил орієнтації ребер [7]. Той набір є значно багатшим і включає (10), (11) та інші
(більш вишукані) правила. (Строго кажучи, згадані правила орієнтації призначені для класу т.зв. анцестральних
графів, про що буде сказано далі). На виході методу виведення отримуємо клас марковської еквівалентності
моделей, опис якого містить ребра з невизначеними кінцями. Відзначимо, що типові методи виведення моделі в
ході виконання першого етапу (або одночасно з виконанням правила колізорної орієнтації ребер ( 0 ))
знаходять так звані не-колізорні стики двох ребер і фіксують їх у вигляді паттернів вигляду X Y Z . Це
означає, що алгоритм знайшов такий сепаратор S , що вірне Ind Emp ( X ; S; Z ) , причому Y S . Фіксація таких
паттернів допомагає виконувати правила орієнтації ребер і дозволяє записати правила більш компактно.
(Зокрема, спрощується запис правила 1 .)
3. Особливості відтворення моделей з прихованими змінними
Як зазначено вище, прийнято обмеження, що кожна прихована змінна контактує тільки з «наявними»
змінними моделі. Отже, конфігурації вигляду Q H1 H 2 Z (де H1 та H 2 – приховані) і подібні не
розглядаються. Конфігурації вигляду X H Y розглядати немає сенсу, оскільки присутність прихованої
змінної в такій позиції не проявляє себе (принаймні не відбивається на марковських властивостях моделі). Для
спрощення викладу, надалі вважатимемо, що кожна прихована змінна впливає на дві змінні моделі. (Втім,
відомо багато спеціальних методів, які працюють в ситуації, коли прихована змінна поєднана з трьома, чотирма
чи більше спостережуваними змінними «одночасно».) Отже, будемо розглядати структури генеративних
моделей, де кожна прихована змінна H «приєднана» до моделі за допомогою фрагменту вигляду X H Y .
Copyright © 2020 for this paper by its authors. Use permitted under Creative 399
Commons License Attribution 4.0 International (CC BY 4.0).
Відтак, всі приховані змінні – взаємно незалежні [2, 5].
Особливостями відтворення моделей з прихованими змінними є наступні. По-перше, для деяких пар
змінних X , Y кожний сепаратор обов'язково мусить включати змінну, яка не є суміжною ані до X , ані до Y .
Тому процедури пошуку сепараторів (на першому етапі алгоритму виведення моделі) відрізняються від
процедур, розроблених для моделей без прихованих змінних [2, 5]. Зрозуміло, що через присутність прихованої
змінної дві поєднані нею змінні неможливо сепарувати. Але моделі, виведені стандартним алгоритмом, містять
також деякі «нетривіальні» ребра. Це ускладнює інтерпретацію моделі та аналіз коректності. Також виникають
додаткові проблеми з орієнтацією ребер, що є предметом даного дослідження.
Нехай генеративна модель має структуру, що зображена на рис. 2,а, де H – прихована змінна. Це проста
конфігурація входження прихованої змінної в модель. Стандартний алгоритм, використовуючи два правила
0 , 1 орієнтації ребер, виведе модель, що показана на рис. 2,б. В даному разі забезпечено абсолютно
адекватне і зрозуміле відображення впливу прихованої змінної. (Можна уявити, що два ребра, які йдуть від
прихованої змінної, є «зшиті» в одне, а позначка самої змінної H видалена.) Але в інших випадках впливи
прихованих змінних відображаються не так «прозоро» й можуть призводити до деформацій виведеної моделі
(відносно генеративної). На рис. 2,в показано генеративну модель з складною конфігурацією входження трьох
прихованих змінних H , L , U .
Відповідну модель, виведену стандартним алгоритмом (з використанням правил 0 , 1 орієнтація
ребер), зображено на рис. 2,г. Біорієнтовані ребра Y Z , X Z та Y W є очікуваними і зрозумілими. Але
в моделі додатково отримано ще й неочікуваний наслідок. Стандартний алгоритм дотримується принципу:
якщо для двох вершин не існує сепаратора, вони безпосередньо зв'язані. Такий алгоритм для щойно розглянутої
моделі (рис. 2,в) неодмінно виводить модель з ребром між X та W . Дійсно, змінні X та W неможливо
сепарувати, хоча вони не поєднані спільною прихованою причиною. Це явище пояснюється тим, що після того,
як за допомогою кондиціонування змінних Y , Z перекриваються три відповідні (відкриті до того) шляхи між X
та W , одночасно відкривається четвертий шлях через три приховані змінні. Той четвертий шлях перекрити
неможливо. (Четвертий шлях між X та W відкривається завдяки провокації залежності через колізори на
вершинах Y та Z .)
H
R X Y Z R X Y Z
Q V Q V
а б
R V Q T R V Q T
H
X Y Z W X Y Z W
L U
в г
Рис. 2. Репрезентація впливів прихованих змінних в виведеній моделі: а – генеративна модель М з
прихованою змінною; б – виведена модель, що репрезентує М; в – генеративна модель N; г – виведена
модель, що репрезентує N
Таким чином, аналітик стикається з незручністю: не кожне біорієнтоване (братське) ребро A B у
виведеній моделі відповідає окремій прихованій змінній (безпосередній спільній причині для A та B ). Втім,
прихована спільна причина (в широкому розумінні) для A та B завжди існує. Повертаємось до моделі, що
відображена на рис. 2,в. Змінні X та W мають три спільні «причини». Але причина H не контактує ані з X ,
ані з W (вона впливає на них за посередництва Y та Z відповідно). Дві інші спільні «причини» мають по
одному безпосередньому контакту. В даному разі «зайве» біорієнтоване ребро X W принаймні не дає
400
підстав для хибних висновків про каузальні відносити (не диктує і не виключає, що одна змінна – X чи W ,– є
причиною іншої). Натомість далі буде показано, що можливі ситуації, коли стандартні алгоритми виводять
моделі, що деформують картину каузальних відносин.
Генеративна модель, зображена на рис. 2,а, має нешунтований колізор X Q Y . Але оскільки змінна
H – прихована, у виведеній моделі (рис. 2,б) цей колізор опиняється шунтованим, і, отже, правило орієнтації
ребер 0 для нього не працює. Попри те, орієнтації ребер цього колізора все таки ідентифікуються, але «по
частинах». Спочатку правило 0 ідентифікує колізор R X Y та колізор X Y Z . Потім завдяки факту
IndR;{X ,Y };Q правило 1 орієнтує ребро X Q . Аналогічно отримуємо Q Y . (Зверніть увагу, що колізор
X Q Y вдалося орієнтувати завдяки тим самим обставинам, які дозволили орієнтувати ребро X Y .)
Можливі такі ситуації, де шунтований колізор орієнтується завдяки тому, що його ребра одночасно
входять в інші, нешунтовані колізори. Також ребра можуть бути орієнтовано згідно з вимогою ациклонності
графу. Але в моделях з біорієнтованим ребрами з'являються також ситуації, коли забезпечення марковських
властивостей потребує орієнтації певних ребер, причому ті ребра не можуть бути орієнтовані
правилами 0 та 1 .
Приклад 1. Розглянемо три генеративні модель, зображені на рис. 3, а,б,в. (Позиції прихованих змінних
очевидні.) Всі три моделі належать одному класу марковської еквівалентності, бо мають спільні властивості:
Ind(X ;;Q) та Ind X ;{Z , Q};Y . Структура моделі на рис. 3,а не містить прихованих змінних і тому попадає в клас
оАОГ-моделей. Якби цей факт (належність генеративної моделі до оАОГ-моделей) був відомий на вході задачі
відтворення моделі, то стандартний алгоритм (озброєний відповідними версіями правил орієнтація ребер
0 , 1 ) відтворив би модель вичерпно однозначно, так, як показано на рис. 3,г. Ребро Q Y входить до складу
шунтованого колізор, і тому правило 0 для нього не діє. Тим не менш, це ребро орієнтується алгоритмом, бо
єдиний альтернативний варіант орієнтації Q Y відпадає як такий, що утворює циклон. (Для таких ситуацій в
класі оАОГ-моделей призначене правило 2 [12].)
Але якщо приховані змінні – можливі, то вказана логіка не діє, і тому для всіх трьох структур
генеративної моделі алгоритм, озброєний тільки правилами 0 , 1 , виведе модель, показану на рис. 3,д.
(Завважте, що не-колізорний стик двох ребер Z Q Y позначено дужкою.) Але відомі реальні стандартні
алгоритми виведення моделі (призначені для постановки з прихованими змінними й озброєні додатковими
правилами орієнтації ребер) видадуть на виході модель у вигляді, показаному на рис. 3,е. Як бачимо, ця модель
виражає каузальне відношення, якого немає в одній з генеративних моделей (див. рис. 3,в), тобто втрачає
адекватність. Пояснення такого результату буде далі.
X Z Q X Z Q X Z Q
Y Y Y
а б в
X Z Q X Z Q X Z Q
Y Y е Y
г д
Рис. 3. Структури моделі для ілюстрації прикладу 1: а, б, в – еквівалентні
моделі; г, д, е – варіанти виведеної моделі.
4. Неоднозначність і ризики виведення моделей з прихованими змінними
Продовжуємо розгляд прикладу 1. Для того, щоб модель забезпечувала вказані марковські властивості –
в даному разі це Ind(X ;;Q) та Ind X ;{Z ,Q};Y ,– вона необхідно мусить мати чотири наступні риси: колізорний
стик X Z Q ; каузальне ребро Z Y ; не-колізорний стик Z Q Y ; колізорний стик Z Y Q . З
огляду на можливість прихованих змінних, можна припустити, що інші орієнтації ребер можуть бути
варіабельними (різними). Чому ж відомі стандартні алгоритми обирають каузальне ребро Q Y в цій ситуації?
Copyright © 2020 for this paper by its authors. Use permitted under Creative 401
Commons License Attribution 4.0 International (CC BY 4.0).
Розглянемо можливі альтернативні орієнтації цього ребра, а саме, Q Y або Q Y . Чи можна узгодити
модель, що має такі ребра, з вказаними марковськими властивостями? Якщо (перша альтернатива) прийняти
ребро Q Y , то для уникнення циклону необхідно прийняти ребро Z Q . Але тоді виникає колізор
Z Q Y . Це суперечить факту Ind X ;{Z ,Q};Y , тож варіант Q Y є неприйнятним. (Побіч того, виникає ще
одна неузгодженість: ланцюг X Z Y Q суперечить факту Ind(X ;;Q) .)
Друга альтернатива – ребро Q Y . Якщо прийняти її, то для забезпечення не-колізорного стику
Z Q Y необхідно уточнити модель, встановивши ребро Z Q . Отримана модель (рис. 4,а) є спроможною,
тобто узгоджується зі свідченнями. По-суті, ця модель збігається з одним варіантом генеративної моделі (див.
рис. 3,в). Дві спроможні моделі суголосні в тому, що вказане ребро має вістря, спрямоване до вершини Y .
Об'єднавши спроможні моделі у єдиний опис, отримаємо структуру, зображену на рис. 4,б.
Тим не менш, алгоритм, який дотримується відомих рекомендацій та принципів, відкине останній
варіант спроможної моделі й визначить єдиний варіант, показаний на рис. 3,е. Як показано вище, ідентифікація
зв'язку між змінними Q та Y як каузального може виявитися неадекватною (оскільки можлива альтернатива
Q Y ). Отже, стандартні алгоритми можуть продукувати помилку.
Помилкове рішення є наслідком одного з правил орієнтації ребер, призначених для виведення моделі з
прихованими змінними [7]. Те правило орієнтації ребер обґрунтовано вимогою, аби структура виведеної моделі
вкладалася в клас так званих анцестральних графів [13]. З'ясуємо суть питання.
Анцестральні, або предкові (пращурні) графи визначаються (крім ациклонності) спеціальним
обмеженням: якщо в структурі моделі є ребро A B , то вершини A та B не поєднані жодним оршляхом, тобто
не є предком одна для іншої. (Зокрема, це означає, що в разі існування A B заборонена присутність A B .)
Еквівалентне формулювання цього обмеження: якщо в циклі є біорієнтоване ребро, то цей цикл має не менше
двох колізорів. (Зауважимо, що анцестральні графи також передбачають використання неорієнтованих ребер.
Але моделі (фрагменти) з неорієнтованими ребрами не мають стосунку до обраного предмету дослідження і
тому зараз відкинуті. Формально можна сказати, що в доповіді розглядається важливий підклас анцестральних
моделей, або анцестральні моделі з ігноруванням неорієнтованих фрагментів.)
Вимога, щоб модель була анцестральною, мотивована, мабуть, наступним феноменом. За умов
виконання припущення повної практичної Каузальної не-оманливості (7), коректний алгоритм виведення
моделі (побудований на вищезазначених принципах), дійсно, ніколи не виведе модель поза класом
анцестральних графів. Спочатку проілюструємо цей феномен на нашому прикладі. Нехай генеративна модель
має структуру рис. 3,в (по-суті, повторену на рис. 4,а). Очевидно, ця структура виходить за межі анцестральних
графів. Алгоритм з правилами 0 , 1 виведе модель, показану на рис. 3,д. А потім, згідно вищенаведеної
аргументації, необхідно уточнить ребро як Q Y . Тож, отримаємо структура рис. 4,б. Завдяки невизначеним
кінцям деяких ребер, ця (частково орієнтована) модель не виходить за межі анцестральних графів. Навіть якщо
автентичне ребро виглядає як Q Y , на основі вказаних марковських властивостей неможливо розпізнати
друге вістря ребра Q Y .
X Z Q X Z Q
Y Y
а б
X Z Q R X Z Q R
Y Y
в г
Рис. 4. Структури моделі для ілюстрації застосування правила «R4*»: а, в – генеративні
моделі; б, г – виведені моделі
Спробуємо штучно створити ситуацію, де можна було би розпізнати вістря в подібній ситуації й
ідентифікувати ребро Q Y . Давайте розширимо модель, а саме, введемо в генеративну модель додаткове
402
ребро Q R . Тоді маємо модель, представлену на рис. 4,в. Оскільки утворився не-шунтований колізор
Y Q R , можна сподіватися, що обидва вістря біля вершини Q будуть ідентифіковані за допомогою правила
0 . Проте аналіз структури виявляє, що маємо ланцюг R Q Z Y . В ході виведення моделі стандартні
алгоритми спробують сепарувати вершини (змінні) R та Y . Для цього треба перекрити вказаний ланцюг, тобто
блокувати вершину Q або (та) Z . Але кондиціонування вершини Q або Z (чи їх обох) відкриває шлях через
колізор Y Q R (провокує залежність). Отже, сепарувати вершини (змінні) R та Y – неможливо (не маючи
доступу до прихованої змінної). Відтак, у результаті виведення отримаємо модель, показану на рис. 4,г.
Оскільки колізор Y Q R в цій структурі опинився шунтованим, правило 0 застосувати до нього не
можна. Відповідні кінці ребер залишаються не орієнтованими. Така невизначеність орієнтацій ребер маскує той
факт, що (частково орієнтована) модель виходить за межі анцестральних графів. (Відзначимо, що через не-
анцестральність генеративної моделі алгоритм видає помилкове ребро R Y , яке є p -каузальним. Для
контрасту нагадаємо, що у вищенаведеній структурі, показаній на рис. 2,г, виникло помилкове
біорієнтоване ребро).
Описане явище – той факт, що навіть коли генеративна модель не є анцестральною, стандартний
алгоритм відтворення моделі ніколи не виведе модель поза класом анцестральних графів, – можна показати в
загальному випадку. Не існує сценарію, за якого коректний алгоритм, виходячи виключно з марковських
властивостей генеративної моделі, виведе не-анцестральну структуру (тобто структуру з біорієнтованим ребром
«над» оршляхом).
Властивість 1 (маскованість не-анцестральних структур). Нехай в генеративній моделі є оршлях
X .. Z W та фрагмент X H W , де H – прихована змінна. Теоретично кажучи, біорієнтоване ребро
«над» оршляхом могло би бути виведене тільки внаслідок застосування колізорного правила. Відтак, для
орієнтації такого ребра X W в моделі має бути присутнє принаймні одне ребро R X , яке стикається своїм
«вістрям» з вістрям біорієнтованого ребра. Нехай таке R X присутнє. Але водночас ребро R X
з'єднується (конкатенація) з початком оршляху X .. W , охопленого біорієнтованим ребром. Така
конфігурація призводить до того, що «інструментальну» змінну R неможливо сепарувати від W . Дійсно,
введення (включення) будь-якої проміжної вершини оршляху X .. W в склад сепаратора провокує
залежність між R та W . Відтак, колізор, який включає біорієнтоване ребро, опиняється шунтованим (через
псевдо-ребро R W ). Колізорне правило не зможе спрацювати, а «вістря» біорієнтованого ребра біля вершини
X не буде ідентифіковане.
Отже, коректний алгоритм не виведе модель з біорієнтованим ребром над оршляхом. Але генеративна
модель може виходити за межі анцестральних моделей, як, зокрема, показує приклад 1, рис. 3,в. Тоді, як було
показано вище, стандартний алгоритм робить некоректне рішення внаслідок застосування одного з правил
орієнтації ребер.
Розглянемо правило орієнтації ребер, яке призводить до помилки у наведеному прикладі (те правило
включено в деякі сучасні алгоритми). У поданні [7] те правило позначено як 4 . Правило має доволі громіздке
формулювання з залученням поняття дискримінуючого шляху (discriminating path). Будемо використовувати
спрощений локальний аналог 4* цього правила. Формулювання правила 4* (точніше, його частини)
виглядає наступним чином:
( A B C ) & ( B D C ) & Ind(A; S; C) & D S DC .
Як показано вище, це правило є некоректним. Для уникнення можливих помилок правило (12) треба
виправити, а саме, після знаку імплікації записати більш обережний (але коректний) висновок D C .
Правило 4 (і його спрощений аналог (12) також) обґрунтоване вимогою, щоб граф моделі залишався
анцестральним. Отже, заборона виходу виведеної моделі за межі анцестральних графів є некоректною. Не
коректно орієнтувати ребро на тій підставі, що альтернативна орієнтація призведе до не-анцестральності. Не
можна примусово «заганяти» модель в клас анцестральних на тій підставі, що не-анцестральна модель не може
бути повністю ідентифікована стандартним алгоритмом на основі марковських властивостей.
Доречно дослідити можливості «повної» ідентифікації не-анцестральної моделі за допомогою апріорних
знань. Тобто потрібно з'ясувати, чи можна отримати на виході алгоритму виведення моделі, підсиленого
відповідними апріорним знаннями, структуру, де є біорієнтоване ребро X W та оршлях X .. V W .
Найбільш типовою і поширеною формою апріорних знань, корисних для виведення каузальних моделей, є
темпоральний порядок змінних. Темпоральний порядок змінних відображає взаємне розташування змінних у
часі (тобто вказує, яка змінна йде у часі раніше іншої). Зрозуміло, що темпоральний порядок змінних накладає
обмеження на можливі каузальні відносини відповідних змінних. Якщо змінна X йде у часі раніше, ніж Y , то
зв'язок X Y неможливий (неможливо, щоб майбутнє впливало на минуле). Але ребро X Y може бути
коректним в цій ситуації. Ясно, що насправді цей зв'язок має вигляд X Y , але ідентифікувати його повністю
на даний момент не вдалося. Якщо ж стає відомим той факт, що змінна X йде у часі раніше, ніж Y , то ребро
X Y треба негайно замінити на X Y .
Copyright © 2020 for this paper by its authors. Use permitted under Creative 403
Commons License Attribution 4.0 International (CC BY 4.0).
Повертаємось до проблеми ідентифікації не-анцестральної моделі, де є оршлях X .. V W і де
змінні X та W мають спільну приховану причину. Ясно, що для ребра між X та W вістря біля змінної W може
бути ідентифіковане стандартним алгоритмом. Проблемною є ідентифікація вістря біля змінної X . Легко
бачити, що знання темпорального порядок не може допомогти розв'язати цю проблему. Дійсно, наявність
оршляху X .. W однозначно свідчить, що змінна X йде у часі раніше, ніж W , і апріорна інформація може
тільки підтвердити цей факт і нічого нового додати не може у цій ситуації (а апріорне знання, що змінна W йде
у часі раніше, ніж X , була би явно абсурдним, бо суперечить ідентифікованому результату).
З огляду на вказані обставини, використання класу анцестральних моделей і відповідна логіка мають
теоретичне значення. Проте можна припустити, що аналітик (чи замовник) має апріорні знання і в інших
формах (не тільки темпоральний порядок). Зокрема, в певній предметній галузі аналітик може знати,
наприклад, що змінні X та W можуть бути поєднані тільки одним (можливо, опосередкованим) каузальним
механізмом. Відтак, коли той механізм виявлено як оршлях X .. V W , то «додаткове» ребро X W
треба орієнтувати як X W . Тоді отримаємо модель поза класом анцестральних графів.
В наступному розділі буде показано, що, навіть коли немає подібних апріорних знань, коректний
алгоритм виведення моделі з даних правдоподібно може побудувати не-анцестральну модель.
Перейдемо до розгляду іншого випадку моделей, що відрізняється від попереднього орієнтаціями деяких
ребер.
Приклад 2. Генеративна модель має структуру, зображену на рис. 5,а. Клас марковської еквівалентності
моделі характеризується властивостями Ind(X ;;Q) та Ind X ; Z;Y . (Розкриття еквіпотентної позначки «*» дасть
дві еквівалентні структури.)
Цей клас марковської еквівалентності відрізняється від прикладу 1 через те, що тут присутній колізор
Z Q Y . Тому для пари X , Y алгоритм виведення моделі знайде d-сепаратор, що складається з однієї
вершини Z . Потім спрацюють правила 0 , 1 і встановлять орієнтації ребер X Z Q та X Z Y . А
далі стандартні алгоритми, оснащені додатковими правилами орієнтації, діють за наступною логікою. Оскільки
для сепарації X та Y виявилося достатньо заблокувати тільки Z , то кондиціонування змінної Z не відкриває
«нового» шляху залежності між X та Y . Отже, провокована залежність між X та Q не «дістається» (не
дотягується) до Y . Відтак, в моделі має бути колізорний стик ребер Z Q Y . З факту Ind(X ;;Q) випливає
колізорний стик ребер Z Y Q . Констатуємо, що в трикутнику з вершин Z , Q та Y всі ребра орієнтовані
вичерпно. Вказана логіка виведення виконується іншою частиною вже згаданого правила 4 .
Формулювання цієї частини правила (точніше, спрощеного локального аналогу) виглядає наступним
чином:
( A B C ) & ( B D C ) & Ind(A; S; C) & D S B D C .
Правила орієнтації ребер (12) та (13) сформульовані в [7] як одне правило. В спрощеній локальній формі
правило записується в наступному вигляді (правило 4* ):
Let A B C & B D C & S : Ind(A; S; C) . Then
а) D S D C ;
б) D S B D C .
X Z Q X Z Q
а Y б Y
Рис. 5. Структури моделі для ілюстрації застосування правила «R4*»:
а – модель для прикладу 2; б – модель для прикладу 4
5. Аномалії виведення моделей з реальних вибірок даних (наслідки ухилів та
неточностей даних)
404
В попередньому розділі матеріал викладався в термінах «теоретичних» фактів умовної незалежності. За
замовчуванням, факт типу Ind(A;S;C) прирівнювався до факту Ind Emp ( A; S; C ) . Це виправдано для великих
вибірок точних даних. Тепер дослідимо роботу алгоритмів та правил виведення моделі, коли вони спираються
на емпіричні факти, обчислені з реалістичних даних (недостатньо точних і невеликого обсягу). Обґрунтування
подальших тверджень, прогнозів і висновків буде спиратися на наступні положення:
1) прагматичний постулат тестування незалежності (6а);
2) припущення підсиленої стабільності двох-реберної залежності (9);
3) припущення стабільності елементарної провокованої залежності (9б).
Більш жорстких припущень не приймаємо. (Не приймаємо припущення повної практичної Каузальної
не-оманливості (7)). Це означає, зокрема, що коли між змінними X та Y` існує ланцюг довжиною у три ребра,
то тест Ind Emp ( X ; ; Y ) може мати або позитивний, або негативний результат (в залежності від параметрів).
Спочатку покажемо, що модель, виведена з реалістичних даних, може опинитися поза класом
анцестральних графів. Тобто в таких умовах властивість 1 (маскованість не-анцестральних структур) часто не
виконується.
Приклад 3. Нехай генеративна модель включає оршлях R Q X Y Z W , та нехай існує
прихована змінна, яка впливає на Q та W` (що має адекватно відображатися як ребро Q W ).
Завдяки факту Ind Emp (Q;Y ; Z ) та правилу 0 буде орієнтовано колізор Z W Q . Можна
спрогнозувати принаймні два сценарія, що призводять до не-анцестральної структури на виході алгоритму
виведення моделі з даних.
Перший сценарій (певно правдоподібний). Тест Ind Emp ( R; ;W ) дає позитивний результат (незалежність
не відмітається) завдяки тому, що залежність через довгий ланцюг – слабка. Тоді «фальшивого» ребра R W
не буде в моделі, і колізор R Q W буде орієнтований. Структура вказаного фрагменту виведеної моделі
буде збігатися з генеративною, тобто модель буде не-анцестральною. (Може виникнути питання, чи немає
суперечності між фактами, що ребро Q W розпізнається, а залежність між R та W` не розпізнається.
Пояснення: шлях між R та W` довший на одне ребро.)
Другий сценарій (менш правдоподібний). Тест Ind Emp ( R; ;W ) дає негативний результат (незалежність
відмітається). Але алгоритм отримує позитивний результат тесту Ind Emp ( R; Z ;W ) . Змінна Z` перекриває оршлях
між R та W`. Водночас провокована залежність між R та W`, що санкціонується критерієм d-сепарації завдяки
колізору R Q W , не розпізнається тестом (тому що занадто слабка). Це пояснюється тим, що дистанція від
Z` до Q` доволі велика, і кондиціонування змінної Z` «затухає по дорозі» до Q`, тобто змінна Q` відчуває лише
слабке збурення. Може виникнути питання: чому безумовна залежність між R та W` вздовж відповідного
ланцюга вважається значущою, а відтинок того ланцюга від Z до Q` не зміг «дистанційно» спровокувати
значущу залежність, відкриваючи колізор R Q W ? Відповідь слід шукати в тому, що у формуванні
провокованої залежності бере участь ще одне ребро Q W , а ребро R Q виступає в іншій ролі –компонента
колізора. Одне й те саме ребро має різну «силу», коли розглядається окремо або в складі ланцюга, і коли є
компонентом колізора [6]. Взаємодія тих ребер у формуванні провокованої залежності кількісно описується
інакше, ніж взаємодія ребра R Q , оршляху Q X Y Z та ребра Z W у формуванні безумовної
залежності між R та W`. Отже, в результаті, алгоритм також видалить «фальшиве» ребро R W з моделі, і
тому колізор R Q W буде орієнтований.
Тепер покажемо, що в умовах реалістичних даних правило орієнтації ребер (12) і правило (14), пункт
«а», можуть породжувати явні помилки і суперечності. Повертаємось до моделі, показаної на рис. 4,(в). (Це
розширений варіант прикладу 1.) Модель характеризується марковськими властивостями Ind(X ;;Q) , Ind(X ; ; R) ,
IndZ ; Q; R та Ind X ;{Z , Q};Y . (Інші незалежності, які відрізняються складнішими сепараторами для тих самих
пар змінних, не змінюють результатів.) Маємо теоретичне Ind(Y ; ; R) . Але оскільки ця залежність
забезпечується ланцюгом з трьох ребер ( R Q Z Y ), то в реалістичних даних ця безумовна залежність
може виявитися слабкою, і гіпотеза Ind Emp (Y ; ; R) буде утримана. Тоді «фальшиве» ребро R Y буде
видалено. Відтак, колізор Y Q R буде орієнтований правилом 0 як Y Q R . Завдяки факту
Ind Emp ( Z ; Q; R ) правило 1 продукує каузальне ребро Z Q . У підсумку генеративна модель буде адекватно
відтворена, а вона виходить за межі анцестральних графів (присутні оршлях Q Z Y та ребро Q Y ).
Звертаємо увагу, що отриманий результат входить у суперечність з правилом орієнтації ребер (12) (воно
повторюється у пункті «а» правила (14)). Вищеописані сценарії логічно виводять ребро Q Y , а правило (12)
вимагає ребра Q Y . Отже, вказане правило потребує корекції. Замість правила (14) пропонується наступна
редакція правила. Назвемо його правилом дистанційної дискримінації колізора/конфаундера і позначимо як
4** . Правило 4** записується:
Copyright © 2020 for this paper by its authors. Use permitted under Creative 405
Commons License Attribution 4.0 International (CC BY 4.0).
Let A B C & B D C & S : Ind Emp ( A; S; C ) . Then
a) D S D C ;
б) D S B D C .
Нарешті, покажемо ще один можливий механізм виникнення помилок в ході виведення моделі
стандартними алгоритмами в реалістичних умовах. Знов розглянемо приклад 1. В моделі чинна марковська
властивість Ind X ;{Z , Q};Y . Але всупереч цій властивості, в ході аналізу реальних даних можна отримати
позитивний результат для простішого тесту Ind Emp ( X ; Z ;Y ) . Пояснення наступне. Кондиціонування змінної Z
перекриває ланцюг між X та Y , але провокує залежність між X та Q . Ця провокована залежність має бути
значущою згідно припущення стабільності елементарної провокованої залежності (9б). Але (як вже
зазначалося) така провокована залежність «за силою» може бути співвіднесена з двох-реберним ланцюгом.
Тому для всіх трьох варіантів моделі (рис. 3,а,б,в) можна вважати, що шлях між X та Y , відкритий після
кондиціонування змінної Z , складається з трьох ребер. (До того ж, для варіантів моделі рис. 3,б та рис. 3,в цей
шлях включає біорієнтоване ребро, а воно «має схильність» бути слабшим за звичайне ребро.) Прийняті в
цьому розділі припущення не санкціонують значущості залежності для такого шляху. Цей шлях емпірично
може виявитися слабким (незначущим), що пояснює факт Ind Emp ( X ; Z ;Y ) . В результаті набір емпіричних фактів
для моделі з прикладу 1 буде збігатися з набором фактів для моделі з прикладу 2. Таким чином, підриваються
підстави, на яких ґрунтується коректність правила орієнтації (14).
Приклад 4. Нехай генеративна модель має структуру, зображену на рис.5,б. Модель характеризується
одним марковським фактом Ind X ; Z;Y .
Внаслідок недосконалості даних емпірична залежність між X та Q (що формується через ланцюг з трьох
ребер X Z Y Q ) може виявитися незначущою. Тоді отримаємо не легітимний факт Ind Emp ( X ; ; Q ) . Відтак,
отримаємо той самий набір емпіричних свідчень, що й для прикладу 2. Тому і правило (14), і корегована версія
(15) дадуть невірний результат.
Отже, для обґрунтування правила дистанційної дискримінації колізора/конфаундера потрібно прийняти
відповідну версію припущення Каузальної не-оманливості. Навіть для локального варіанту 4** правила
(спрощеного порівняно з правилом 4 , що запропоноване в [7]) необхідне припущення, аналогічне до ППС2РЗ
(9), але жорсткіше за нього. Необхідному припущенню логічно дати назву «припущення підсиленої
стабільності трьох-реберної залежності».
Застосування деяких інших правил орієнтації ребер стикається з аналогічними проблемами.
Висновки
Виявлено деякі проблеми відтворення каузальних мереж (в умовах прихованих змінних) з емпіричних
даних методами, основаними на незалежності. Фокусом інтересу є забезпечення адекватності виведених
моделей. З'ясовано, що одне з відомих правил орієнтації ребер є некоректним, бо дає висновок, який може бути
неадекватним. А саме, за певних умов правило визначає зв'язок між змінними як каузальний, в той час як в
генеративній моделі цей зв'язок утворено завдяки спільній причині двох вказаних змінних (причина прихована).
Запропоновано коректний варіант правила орієнтації ребер (спрощена версія) – правило «дистанційної
дискримінації колізора/конфаундера». Некоректність відомого правила, можливо, виникла внаслідок
обмеження, що модель має належати класу анцестральних графів. Показано, що на виході стандартного
алгоритму виведення моделі з даних може бути отримана модель, що не вкладається в цей клас. По-перше,
модель поза класом анцестральних може бути виведена за допомогою апріорного знання в певній формі.
(Відзначимо, що знання у формі темпорального порядку змінних не може породити таку ситуацію.) По-друге,
модель поза класом анцестральних може бути виведена внаслідок того, що залежність, утворена довгим
ланцюгом, не розпізнається.
Відтворення моделей з реалістичних даних потребує прагматичних процедур тестування незалежності,
що ставить аналітика перед необхідністю знаходити баланс між ризиком втратити автентичне ребро моделі та
ризиком включити в модель неадекватне ребро (через вибірковий ухил в даних). Наслідком прагматичних
вимог правдоподібно можуть стати ситуації, коли залежність, яка створюється ланцюгом з трьох чи більше
ребер, буде трактуватися як незалежність. Показано, що в таких ситуаціях відповідні правила орієнтації ребер
призводять до помилкових висновків. Для обґрунтування навіть спрощеної версії правила «дистанційної
дискримінації колізора/конфаундера» потрібно прийняти версію припущення Каузальної не-оманливості,
жорсткішу за ту версію припущення, яка є достатньою для коректності базових правил орієнтації ребер
(«колізорного» та «пост-колізорного» правил).
406
Література
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. Балабанов О.С. Аналітика великих даних: принципи, напрямки і задачі (огляд). Проблеми програмування. 2019. № 2. С. 47–68.
4. Spirtes P., Zhang K. Causal discovery and inference: concepts and recent methodological advances. Applied Informatics. 2016. V.3: 3. –28 p.
5. Spirtes P., Meek C., Richardson T. An algorithm for causal inference in the presence of latent variables and selection bias. In: Computation,
Causation, and Discovery, C. Glymour, and G. Cooper (eds.), P. 211–252. – AAAI Press, Menlo Park, CA. 1999. 568 p.
6. Балабанов А.С. Индуцированная зависимость, взаимодействие факторов и дискриминация каузальных структур. Кибернетика и
системный анализ. 2016. № 1. С. 10–22.
7. Zhang J. On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias. Artificial
Intelligence. 2008. V. 172. P. 1873–1896.
8. Балабанов О.С. Каузальні мережі: аналіз, синтез та виведення з статистичних даних: Автореферат дис. … доктора фіз.-мат. наук
(01.05.01– теоретичні основи інформатики та кібернетики). – К.: Ін-т кібернетики ім. В.М. Глушкова НАНУ, 2014. – 34 с.
9. Балабанов О.С. Минимальные сепараторы в структурах зависимостей. Свойства и идентификация. Кибернетика и системный анализ.
2008. № 6. С. 17–32.
10. Балабанов А.С. Логика минимальной сепарации в каузальных сетях. Кибернетика и системный анализ. 2013. № 2. С. 36–47.
11. Балабанов О.С. Принципи та аналітичні засоби реконструкції структур ймовірнісних залежностей у спеціальному класі. Проблеми
програмування. 2017. № 1. С. 97–110.
12. Meek C. Causal inference and causal explanation with background knowledge. Proceedings of the 11th Conf. on Uncertainty in Artificial
Intelligence, P. Besnard and S. Hanks (Eds.), Morgan Kaufmann Publ., Inc., San Mateo, CA. 1995. P. 403–410.
13. Richardson T., Spirtes P. Ancestral graph Markov models. The Annals of Statistics. 2002. V. 30. N 4. P. 962–1030.
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. 543 p.
3. Balabanov O.S. (2019) Big Data Analytics: principles, trends and tasks (a survey). Problems in Programming. 2019. (3), 47–68. (ISSN 1727–
4907) [in Ukrainian]
4. Spirtes P., Zhang K. (2016) Causal discovery and inference: concepts and recent methodological advances. Applied Informatics. V.3: 3. 28 p.
5. Spirtes P., Meek C., Richardson T. (1999) An algorithm for causal inference in the presence of latent variables and selection bias. In:
Computation, Causation, and Discovery, C. Glymour, and G. Cooper (eds.), P. 211–252. – AAAI Press, Menlo Park, CA. 568 p.
6. Balabanov O.S. (2016) Induced Dependence, Factor Interaction, and Discriminating between Causal Structures. Cybernetics and Systems
Analysis. V. 52. Issue 1. – P. 8–19.
7. Zhang J. (2008) On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias. Artificial
Intelligence. V. 172. P. 1873–1896.
8. 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]
9. Balabanov A.S. (2008). Minimal separators in dependency structures: Properties and identification. Cybernetics and Systems Analysis. V. 44,
Issue 6, P. 803–815.
10. O. S. Balabanov. (2013) Logic of minimal separation in causal networks. Cybernetics and Systems Analysis. V. 49. – Issue 2, P. 191–200.
11. Balabanov O.S. (2017) Principles and analytical tools for reconstruction of probabilistic dependency structures in special class. Problems in
programming. 2017. N 1. P. 97–110. [in Ukrainian]
12. Meek C. (1995) Causal inference and causal explanation with background knowledge. Proceedings of the 11th Conf. on Uncertainty in Artificial
Intelligence, P. Besnard and S. Hanks (Eds.), Morgan Kaufmann Publ., Inc., San Mateo, CA. P. 403–410.
13. Richardson T., Spirtes P. (2002) Ancestral graph Markov models. The Annals of Statistics. V. 30. N 4. P. 962–1030.
Одержано 28.02.2020
Про автора:
Балабанов Олександр Степанович,
кандидат техн. наук, доктор фіз.-мат. наук,
провідний науковий співробітник.
Кількість наукових публікації в українських виданнях – 60.
Кількість наукових публікації в іноземних індексованих виданнях – 12.
Індекс Хірша – 7.
http://orcid.org/0000-0001-9141-9074
Місце роботи автора
Інститут програмних систем НАН України, 03187, м. Київ-187,
проспект Академіка Глушкова, 40.
Copyright © 2020 for this paper by its authors. Use permitted under Creative 407
Commons License Attribution 4.0 International (CC BY 4.0).
Тел.: (38)(044) 526-51-39.
E-mail: bas@isofts.kiev.ua
408