О логике независимости каузальных диаграмм
Анализируются свойства рекурсивных каузальных диаграмм (АОГ-моделей). Показано, что множество парных безусловных независимостей влечет ограничения на допустимые условные независимости и определяет некоторые фрагменты структуры диаграммы. Аналізуються властивості рекурсивних каузальних діаграм (АОГ-м...
Збережено в:
| Опубліковано в: : | Компьютерная математика |
|---|---|
| Дата: | 2009 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84553 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | О логике независимости каузальных диаграмм / А.С. Балабанов // Компьютерная математика. — 2009. — № 2. — С. 109-115. — Бібліогр.: 7 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859823218581307392 |
|---|---|
| author | Балабанов, А.С. |
| author_facet | Балабанов, А.С. |
| citation_txt | О логике независимости каузальных диаграмм / А.С. Балабанов // Компьютерная математика. — 2009. — № 2. — С. 109-115. — Бібліогр.: 7 назв. — рос. |
| collection | DSpace DC |
| container_title | Компьютерная математика |
| description | Анализируются свойства рекурсивных каузальных диаграмм (АОГ-моделей). Показано, что множество парных безусловных независимостей влечет ограничения на допустимые условные независимости и определяет некоторые фрагменты структуры диаграммы.
Аналізуються властивості рекурсивних каузальних діаграм (АОГ-моделей). Показано, що множина парних безумовних незалежностей тягне обмеження на припустимі умовні незалежності та визначає деякі фрагменти структури діаграми.
Some properties of recursive causal diagrams (DAG models) are analyzed. We show that fully specified set of pairwise unconditional independencies entails certain restrictions on set of conditional independencies in the model and determines certain fragments of the model.
|
| first_indexed | 2025-12-07T15:27:17Z |
| format | Article |
| fulltext |
Ýêñïåðòíûå ñèñòåìû,
ìåòîäû èíäóêòèâíîãî
âûâîäà
Анализируются свойства рекур-
сивных каузальных диаграмм
(АОГ-моделей). Показано, что
множество парных безусловных
независимостей влечет ограниче-
ния на допустимые условные неза-
висимости и определяет некото-
рые фрагменты структуры диа-
граммы.
© А.С. Балабанов, 2009
ÓÄÊ 007:681.3.00
À.Ñ. ÁÀËÀÁÀÍÎÂ
Î ËÎÃÈÊÅ ÍÅÇÀÂÈÑÈÌÎÑÒÈ
ÊÀÓÇÀËÜÍÛÕ ÄÈÀÃÐÀÌÌ
Введение. Графовые модели вероятностных
зависимостей – строгий язык представления
знаний о зависимостях в условиях неопреде-
ленности, использующий многомерный ста-
тистический анализ, аппарат графов, теорию
информации и логику. Наиболее популярным
классом графовых моделей стали модели,
структурированные ациклическими ориенти-
рованными графами (АОГ-модели). Досто-
инства АОГ-моделей – компактное представ-
ление систем зависимостей и вычислитель-
ная эффективность вероятностного вывода
от свидетельств. АОГ-модели привлекают
своей способностью отображать причинно-
следственные связи, поэтому они также из-
вестны как каузальные диаграммы [1–3].
Иногда в каузальных диаграммах допускают
латентные переменные. Здесь рассматрива-
ются модели без латентных переменных, т.е.
рекурсивные каузальные диаграммы. В таких
диаграммах нет двунаправленных дуг. Инте-
рес представляют независимости только для
пар переменных. Как только специфициро-
вано множество парных фактов безусловной
независимости, для существования непроти-
воречивой диаграммы необходимо, чтобы
выполнялись (или не выполнялись) соответ-
ствующие условные независимости. Некото-
рые импликации отношений независимости
можно получить с помощью полуграфоид-
ных аксиом [2–5]. Однако эти аксиомы ис-
пользуют информацию фрагментарно и ни-
как не учитывают специфику каузальных
диаграмм – ориентированность связей, от-
сутствие ориентированных циклов и скры-
тых переменных. Будем опираться на топо-
логические свойства каузальных диаграмм и
системно использовать множество безуслов-
ных независимостей двух переменных.
Компьютерная математика. 2009, № 2 109
А.С. БАЛАБАНОВ
Постановка задачи. Пусть специфицировано все множество безусловных
независимостей пар переменных. Требуется построить такую каузальную диа-
грамму (или предсказать ее необходимые фрагменты), чтобы совершенно ото-
бразить все Марковские свойства (согласно критерию d-сепарации). Требуется
вывести условные независимости и структурные фрагменты диаграммы, кото-
рые должны присутствовать в любой диаграмме, удовлетворяющей заданным
условиям. То есть необходимо выявить нетривиальные импликации заданного
множества безусловных независимостей и общих конструктивных ограничений
каузальных диаграмм.
Базовые определения. Если в графе G есть дуга yx → , то вершина x на-
зывается “родителем” вершины y, а вершина y – ребенком x. Ребро – это дуга,
ориентация которой неизвестна или игнорируется. Ребро обозначается x—y ,
а отсутствие ребра – как (x—y ) . Путь в орграфе – это последовательность
инцидентных ребер без повторения вершин. Как исключение, первая и послед-
няя вершины пути (из трех или более ребер) могут совпадать, и такой путь на-
зывают циклом. Орпуть (униориентированный путь) – это путь, на котором все
ребра ориентированы в одном направлении (
¬
yx →⋅⋅⋅→ ). Ациклический ориен-
тированный граф (АОГ) – это орграф без униориентированных циклов. Далее
под графом подразумеваем АОГ. Ввиду ацикличности графа и униориентиро-
ванности каждого ребра любой АОГ содержит корни. Корень орграфа – это
вершина, не имеющая ни одной входящей дуги. Вершина x называется предком
вершины y в орграфе, если есть орпуть из x в y (в частности, путь нулевой дли-
ны). Отношение предок-потомок является рефлексивным транзитивным замы-
канием отношения родитель-ребенок. Обозначим F(x) множество родителей x.
Ввиду взаимно однозначного соответствия термины переменная (модели) и
вершина (графа) употребляются как взаимозаменяемые. АОГ-модель определя-
ется как (D, ), где D – АОГ, а θ θ – совокупность локально заданных параметров
( )(xFxp ) . АОГ-модель определяет совместное распределение вероятностей пе-
ременных согласно правилу Байеса [1–3].
Определение 1. Коллайдером в графе называется фрагмент вида
zyx ←→ . Коллайдер zyx ←→ называется шунтированным (экранирован-
ным), если в графе есть ребро x—z . Цепь (бесколлайдерный путь) – это путь,
не содержащий ни одного коллайдера.
Ключевую роль в теории АОГ-моделей играет критерий d-сепарации. Этот
критерий объединяет каузальное Марковское предположение и полуграфо-
идные аксиомы независимости [1–5].
Определение 2. Путь в АОГ-модели называют d-закрытым с помощью
(кондиционирования) множества вершин S, если и только если
π
a) существует вершина x, S∈x , x ∈π , причем на пути π есть дуга →x
или дуга x← , или
б) на пути π есть хотя бы один коллайдер ←→ y , причем и не су-
ществует никакой вершины
S∉y
S∈z , такой, что есть орпуть из y в z .
110 Компьютерная математика. 2009, № 2
О ЛОГИКЕ НЕЗАВИСИМОСТИ КАУЗАЛЬНЫХ ДИАГРАММ
Множество вершин Z d-сепарирует вершины x и y, если и только если все
пути между вершинами x и y являются d-закрытыми с помощью множества
вершин Z . Будем обозначать такую d-сепарацию предикатом ( )Ds x y⊥ ⊥Z .
Когда Z={} , будем писать такой предикат как ( )yx ⊥⊥Ds . Если хотя бы один
путь между x и y не является d-закрытым с помощью Z , то говорят, что вер-
шины x и y d-соединены (d-зависимы), т. е. ( )yx ⊥⊥¬ ZDs .
Если в АОГ предикат ( )yx ⊥⊥ ZDs истинен, то множество вершин Z на-
зывают сепаратором, или d-сепаратором, для пары (x, y). Первичное свойство
сепарации в АОГ связывает идентификацию ребер и независимостей:
(x—y ) ( )yxyx ⊥⊥¬∉∀⇔ ZZZ Ds:),( . (1)
Условную независимость переменной x от переменной y при кондициониро-
вании множества переменных Z (x,y∉Z) будем обозначать .
Для дискретных переменных условная независимость означает
( )yx ⊥⊥ ZPr
( )p xy =Z
( )) (p x p y= ⋅Z Z для всех значений. Безусловную независимость будем записы-
вать в форме ( )yx ⊥⊥Pr .
Известно [1–3, 5], что критерий d-сепарации определяет Марковские свой-
ства АОГ-модели (т. е. условные независимости, выполняющиеся при любой
параметризации модели):
( ) ⇒⊥⊥∉∀ yxyx ZZZ Ds:,, ( )yx ⊥⊥ ZPr . (2)
Предположение каузальной необманчивости распределения вероятностей
переменных модели относительно АОГ выражается как обратная импликация
по сравнению с (2). Объединяя это предположение с (2), получаем
( ) ⇔⊥⊥∉∀ yxyx ZZ)Z( Ds:, ( )yx ⊥⊥ ZPr . (3)
При этом говорят, что АОГ-модель совершенно отображает парные Марковские
свойства. В данной работе рассматриваются именно совершенные АОГ-модели.
То есть принимается, что множество фактов (условной) независимости точно и
полно определяется критерием d-сепарации. В частности, две вершины без-
условно независимы тогда и только тогда, когда между ними существует цепь.
Пусть задано множество безусловных независимостей, выполняющихся
в модели. Тогда можно установить некоторые рамки для множества более слож-
ных (условных) независимостей, которым должна удовлетворять АОГ-модель,
чтобы совершенно отображать Марковские свойства.
Аппарат генотипов переменных. Поскольку множество безусловно зави-
симых переменных может быть большим, предлагается использовать более эко-
номное (компактное) их представление через понятие генотипа переменной.
Каждая корневая переменная является предком для всех своих потомков, поэто-
му естественно назвать ее «геном» (или приписать ей ген).
Компьютерная математика. 2009, № 2 111
А.С. БАЛАБАНОВ
Определение 3. Генотип G(x) переменной (вершины) x – это множество
всех корневых предков переменной x. (Каждая переменная является предком, в
частности, и самой себя.) Популяция переменных – это множество переменных,
которые имеют одинаковый генотип. Две переменные x и y называются родст-
венными, если они имеют хотя бы один общий ген, т.е. {})()( ≠∩ yGxG Легко
убедиться, что справедлива эквивалентность
⇔=∩ {})()( yGxG ( )yx ⊥⊥Ds ( )yx ⊥⊥⇔ Pr . (4)
Таким образом, генотипы точно отображают все безусловные независимости.
Набором безусловных независимостей переменной x назовем множество
( ){ yxyxI ⊥⊥= Ds)( }
)
. Генотипы переменных легко вывести из отношения без-
условной независимости. Нижеследующая процедура является уточнением про-
цедуры “Геном-1” из [6]. На входе полностью специфицировано множество фак-
тов безусловной независимости вершин (переменных) модели.
1. Для каждой переменной x сформировать ее набор безусловных независи-
мостей ) . При этом x назовем порождающей переменной для . (xI (xI
2. Упорядочить множество наборов ) по кардинальности. (xI
3. Выявить все совпадающие наборы. Взять по одному набору (представите-
лю) из каждого подмножества равных наборов. Составить список L из наборов-
представителей и упорядочить L по кардинальности.
4. В списке наборов L найти все отношения поглощения (включения).
5. Выбрать из списка L все те наборы, которые не поглощаются другими,
и образовать из них список L*. Для каждого набора из списка L* приписать
порождающей переменной уникальное имя гена. (Таким именем можно объя-
вить имя самой порождающей переменной.) Получаем набор генов R.
6. Порождающим переменным всех наборов из списка L, которые совпадают
с наборами из L*, приписать те же имена генов. Таким образом, получаем все
одногенные популяции переменных.
7. Определить генотипы остальных переменных. Множество отсутствую-
щих генов определяется как =)(xAG ( ){ }yxRy ⊥⊥∈ Ds . Тогда
)(\)( xAGRxG = .
Согласно определению, в роли генов выступают корневые вершины графа.
Однако не всегда можно точно определить корневую вершину. Известно, что
если одногенная популяция имеет структуру дерева, то корень в ее составе не
распознается фактами независимости. Но когда в составе одногенной популяции
есть не шунтированный коллайдер, выясняется, что ни коллайдерная перемен-
ная, ни ее потомок не могут быть корнем. Ввиду этого можно уточнить корни
(и гены), выданные процедурой “Геном-1”. Например, пусть модель (рисунок),
содержит одногенную популяцию {x, y, z, w, v}. Процедура “Геном-1” могла бы
выдать в качестве гена переменную w или v. Но ввиду того, что и
других фактов выясняется, что ни w, ни v не могут быть корнями. Тогда можно
( )yzx ⊥⊥Ds
112 Компьютерная математика. 2009, № 2
О ЛОГИКЕ НЕЗАВИСИМОСТИ КАУЗАЛЬНЫХ ДИАГРАММ
скорректировать имена и объявить геном пере-
менную x или y, или z. (Для дальнейших выкла-
док эта коррекция не существенна. Для всех вер-
шин за пределами данной одногенной популяции
не имеет значения, какая из вершин популяции –
корень.)
z
y x
w
Легко видеть, что в АОГ с k корнями выполня-
ется не менее парных безусловных
независимостей, где – кардинальность i-й од-
ногенной популяции. В АОГ с двумя корнями
будет точно безусловных независимостей.
В частном случае, когда АОГ имеет только один
корень, нет ни одной безусловной независимости.
∑ ∑
= +=
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛k k
ij
ji rr
1 1 v i
1 2r r
ir
РИСУНОК
Генотипом множества переменных (вершин) назовем объединение геноти-
пов всех элементов множества.
Импликации отношения родственности. В аргументации неявно приме-
няется операция вида «бесколлайдерная стыковка». Если существует цепь меж-
ду вершинами x и y и орпуть вида zy →⋅⋅⋅→ , то существует цепь между вер-
шинами x и z . Это следует прямо из критерия d-сепарации. (Если при таком
соединении образуется цикл на промежуточной вершине, цикл следует выбро-
сить из итоговой цепи.) Установим простые, но полезные факты для генотипов.
Факт 1. По дуге (в направлении стрелки) наследуются все гены. Если есть
дуга yx → , то ) . Следовательно, по униориентированному пути
наследуются все гены, т. е. если есть
()( yGxG ⊆
yx →⋅⋅⋅→ , то ) , и для всех
промежуточных вершин z на этом пути .
()( yGxG ⊆
)()()( yGzGxG ⊆⊆
На любой цепи есть старшая вершина x, т. е. такая вершина, что на этой це-
пи нет ни дуги x→ , ни дуги ←x . В случае униориентированного пути старшей
является начальная вершина. В других случаях цепи старшей является промежу-
точная вершина, имеющая на этой цепи дуги →← x .
Факт 2. Если на цепи старшей является вершина x, то для всех других
вершин y на этой цепи верно . )
)
()( yGxG ⊆
Следствия из фактов 1 и 2:
если вершина z лежит на некоторой цепи между x и y, то или
;
()( xGzG ⊆
)()( yGzG ⊆
если ) , то невозможны ни дуга ()( yGxG ⊆¬ yx → , ни орпуть yx →⋅⋅⋅→ ;
если и ))()( yGxG ⊆¬ ()( yGxG ⊇¬ , то невозможно ребро x—y и не-
возможен никакой орпуть между x и y.
Компьютерная математика. 2009, № 2 113
А.С. БАЛАБАНОВ
Факт 3. Если в модели есть только одна двухгенная переменная y с геноти-
пом , а одногенные популяции с генотипами { zxyG ,)( = } { }x и соответст-
венно состоят из единственных переменных x и z , то существует коллайдер
{ }z
zyx ←→ .
Действительно, в этих условиях не существует никаких промежуточных
переменных, через которые мог бы пройти орпуть из x в y и орпуть из z в y .
Обобщая эту аргументацию, получаем.
Факт 4. Пусть задана многогенная переменная y , причем .
Если в модели среди всех переменных z с числом генов
)(yGa ∈
)()(2 yGzG ≤≤
нет ни одной такой, что и ))()( yGzG ⊆ (zGa ∈ , то существует дуга вида
yx → , выходящая из одногенной популяции с генотипом { }axG =)( .
Среди множества фактов условной независимости аналитику прежде всего
интересны более простые, «компактные» отношения. Это формализовано поня-
тием локально-минимального сепаратора [7]. Известно [2, 7], что из каждой
вершины каждого локально-минимального сепаратора для пары (x, y) существу-
ет орпуть в вершину x или в вершину y . Следовательно, согласно факту 1,
справедливы такие правила для независимостей.
Правило 1. Если существует некоторое множество Z , такое, что
, т. е. отсутствует ребро x—y , то также существует некоторое
множество Z* , такое, что
( yx ⊥⊥ ZDs )
( )yx ⊥⊥ Z*Ds , причем или
.
)
()( yGwG ⊆¬
)
()( xGG ⊆Z*
)()( yGG ⊆Z*
Следствие из правила 1. Если отсутствует ребро x—y и для вершины w вы-
полняется и ) , то существует некоторое множество
, такое, что , причем
)()( xGwG ⊆¬
Z ( yx ⊥⊥ ZDs Z∉w .
Правило 2. Если нет ребра x—y , то существует некоторое множество Z ,
такое, что ( yx ⊥ )⊥ ZDs , причем для любого такого Z : )()()( yGxGG ∩⊇Z .
Покажем, что иногда можно вывести существование сепаратора с более
жестким ограничением на генотип.
Правило 3. Если и ))()( yGxG ⊆¬ ()( yGxG ⊇¬ , то существует некоторое
множество Z , такое, что ( yx )⊥⊥ ZDs , причем )()()( yGxGG ∩=Z .
Из условия следует, что невозможно ребро x—y и невозможен никакой
орпуть между x и y . Очевидно, что )()( yGxG ∩ – наименьший генотип любого
сепаратора для пары вершин (x ,y ) . Существование такого сепаратора можно
показать так. Старшая вершина на каждой цепи между x и y является промежу-
точной. Объединение всех этих старших вершин даст искомый сепаратор Z .
Заключение. Предложены новые правила вывода, позволяющие получать
некоторые условные независимости и некоторые обязательные фрагменты или
характеристики каузальной диаграммы, имплицируемые заданным множеством
парных безусловных независимостей. Предложенный аппарат генотипов и пра-
вила помогают на основе спецификации безусловных независимостей синтези-
ровать структуру модели, совершенно представляющую Марковские свойства.
114 Компьютерная математика. 2009, № 2
О ЛОГИКЕ НЕЗАВИСИМОСТИ КАУЗАЛЬНЫХ ДИАГРАММ
О.С. Балабанов
ПРО ЛОГІКУ НЕЗАЛЕЖНОСТІ КАУЗАЛЬНИХ ДІАГРАМ
Аналізуються властивості рекурсивних каузальних діаграм (АОГ-моделей). Показано, що
множина парних безумовних незалежностей тягне обмеження на припустимі умовні неза-
лежності та визначає деякі фрагменти структури діаграми.
O.S. Balabanov
ON INDEPENDENCY LOGIC OF CAUSAL DIAGRAMS
Some properties of recursive causal diagrams (DAG models) are analyzed. We show that fully
specified set of pairwise unconditional independencies entails certain restrictions on set of condi-
tional independencies in the model and determines certain fragments of the model.
1. Pearl J. Causality: Models, Reasoning, and Inference. – Cambridge Univ. Press, 2000. – 526 p.
2. Lauritzen S.L. Causal inference from graphical models / O.E. Barndorff-Nielsen, D.R. Cox and
C. Klüppelberg (eds.). // Complex Stochastic Systems / London: Chapman and Hall, 2000. –
P. 63–107.
3. Verma T. Causal networks: semantics and expressiveness / Technical Report R-65-I. – Cognitive
Systems Laboratory, UCLA, Los Angeles, CA. – June 1987. – 10 p.
4. Dawid A. P. Conditional independence / S. Kotz, C. B. Read and D. L. Banks. (eds.) // Encyclope-
dia of Statistical Sciences. – 1998. – 2. – P.146–155.
5. Pearl J., T. Verma. The Logic of Representing Dependencies by Directed Graphs // Proc. of 6th
National Conf. on Artificial Intelligence (AAAI-87), July 13–17, 1987. – Seattle, WA: AAAI
Press, 1987. – P. 374–379.
6. Балабанов A.C. Восстановление структур систем вероятностных зависимостей из данных.
Аппарат генотипов переменных // Проблемы управления и информатики. – 2003. – № 2.
– C. 91 – 99.
7. Балабанов А.С. Минимальные сепараторы в структурах зависимостей. Свойства и иденти-
фикация // Кибернетика и системный анализ. – 2008. – № 6. – С. 17–32.
Получено 09.05.2009
Oá àâòîðå:
Балабанов Александр Степанович,
кандидат технических наук, старший научный сотрудник
Института программных систем НАН Украины.
Компьютерная математика. 2009, № 2 115
О.С. Балабанов
O.S. Balabanov
|
| id | nasplib_isofts_kiev_ua-123456789-84553 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | ХХХХ-0003 |
| language | Russian |
| last_indexed | 2025-12-07T15:27:17Z |
| publishDate | 2009 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Балабанов, А.С. 2015-07-10T11:35:32Z 2015-07-10T11:35:32Z 2009 О логике независимости каузальных диаграмм / А.С. Балабанов // Компьютерная математика. — 2009. — № 2. — С. 109-115. — Бібліогр.: 7 назв. — рос. ХХХХ-0003 https://nasplib.isofts.kiev.ua/handle/123456789/84553 007:681.3.00 Анализируются свойства рекурсивных каузальных диаграмм (АОГ-моделей). Показано, что множество парных безусловных независимостей влечет ограничения на допустимые условные независимости и определяет некоторые фрагменты структуры диаграммы. Аналізуються властивості рекурсивних каузальних діаграм (АОГ-моделей). Показано, що множина парних безумовних незалежностей тягне обмеження на припустимі умовні незалежності та визначає деякі фрагменти структури діаграми. Some properties of recursive causal diagrams (DAG models) are analyzed. We show that fully specified set of pairwise unconditional independencies entails certain restrictions on set of conditional independencies in the model and determines certain fragments of the model. ru Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Экспертные системы, методы индуктивного вывода О логике независимости каузальных диаграмм Про логіку незалежності каузальних діаграм On independency logic of causal diagrams Article published earlier |
| spellingShingle | О логике независимости каузальных диаграмм Балабанов, А.С. Экспертные системы, методы индуктивного вывода |
| title | О логике независимости каузальных диаграмм |
| title_alt | Про логіку незалежності каузальних діаграм On independency logic of causal diagrams |
| title_full | О логике независимости каузальных диаграмм |
| title_fullStr | О логике независимости каузальных диаграмм |
| title_full_unstemmed | О логике независимости каузальных диаграмм |
| title_short | О логике независимости каузальных диаграмм |
| title_sort | о логике независимости каузальных диаграмм |
| topic | Экспертные системы, методы индуктивного вывода |
| topic_facet | Экспертные системы, методы индуктивного вывода |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84553 |
| work_keys_str_mv | AT balabanovas ologikenezavisimostikauzalʹnyhdiagramm AT balabanovas prologíkunezaležnostíkauzalʹnihdíagram AT balabanovas onindependencylogicofcausaldiagrams |