Графоид

Графоидные математические утверждения

Графоид — это набор утверждений вида « X нерелевантно для Y, учитывая, что мы знаем Z » , где X , Y и Z — наборы переменных. Понятия «нерелевантности» и «при условии, что мы знаем» могут получать различные интерпретации, включая вероятностные , реляционные и корреляционные, в зависимости от приложения. Эти интерпретации имеют общие свойства, которые могут быть зафиксированы путями в графах (отсюда и название «графоид»). Теория графоидов характеризует эти свойства в конечном наборе аксиом , которые являются общими для информационной нерелевантности и ее графических представлений.

История

Judea Pearl и Azaria Paz ^[1] ввели термин «графоиды» после того, как обнаружили, что набор аксиом, управляющих условной независимостью в теории вероятностей, является общим для неориентированных графов . Переменные представлены в виде узлов в графе таким образом, что наборы переменных X и Y являются независимыми, обусловленными Z в распределении, когда набор узлов Z отделяет X от Y в графе. Аксиомы для условной независимости в вероятности были выведены ранее A. Philip Dawid ^[2] и Wolfgang Spohn ^[3] Соответствие между зависимостью и графами было позже распространено на направленные ациклические графы (DAG) ^{[4] [5] [6]} и на другие модели зависимости. ^{[1] [7]}

Определение

Модель зависимости M — это подмножество триплетов ( X , Z , Y ), для которых предикат I ( X , Z , Y ): X независим от Y при заданном Z является истинным. Графоид определяется как модель зависимости, которая замкнута при следующих пяти аксиомах:

1. Симметрия: ${\displaystyle I(X,Z,Y)\Leftrightarrow I(Y,Z,X)}$
2. Разложение: ${\displaystyle I(X,Z,Y\cup W)\Rightarrow I(X,Z,Y)~\&~I(X,Z,W)}$
3. Слабый союз: ${\displaystyle I(X,Z,Y\cup W)\Rightarrow I(X,Z\cup W,Y)~\&~I(X,Z\cup Y,W)}$
4. Сокращение: ${\displaystyle I(X,Z,Y)~\&~I(X,Z\cup Y,W)\Rightarrow I(X,Z,Y\cup W)}$
5. Пересечение: ${\displaystyle I(X,Z\cup W,Y)~\&~I(X,Z\cup Y,W)\Rightarrow I(X,Z,Y\cup W)}$

Полуграфоид — это модель зависимости, закрытая относительно 1–4. Эти пять аксиом вместе известны как аксиомы графоида. ^[8] Интуитивно, свойства слабого объединения и сокращения означают, что нерелевантная информация не должна изменять статус релевантности других предложений в системе; то, что было релевантным, остается релевантным, а то, что было нерелевантным, остается нерелевантным. ^[8]

Типы графоидов

Вероятностные графоиды

Условная независимость, определяемая как

${\displaystyle I(X,Z,Y)\Leftrightarrow P(X\mid Y,Z)=P(X\mid Z)}$

является полуграфоидом, который становится полным графоидом, когда P строго положительно. ^{[1] [7]}

Корреляционные графоиды

Модель зависимости представляет собой корреляционный графоид, если в некоторой функции вероятности мы имеем:

${\displaystyle I_{c}(X,Y,Z)\Leftrightarrow \rho _{xy.z}=0{\text{ for every }}x\in X{\text{ and }}y\in Y}$

где — частная корреляция между x и y при заданном наборе Z. ${\displaystyle \rho _{xy.z}}$

Другими словами, линейная ошибка оценки переменных в X с использованием измерений Z не будет уменьшена путем добавления измерений переменных в Y , что делает Y нерелевантным для оценки X. Модели корреляционной и вероятностной зависимости совпадают для нормальных распределений. ^{[1] [7]}

Реляционные графоиды

Модель зависимости является реляционным графоидом, если она удовлетворяет

${\displaystyle P(X,Z)>0~\&~P(Y,Z)>0\implies P(X,Y,Z)>0.}$

Другими словами, диапазон значений, разрешенных для X, не ограничивается выбором Y , если Z фиксировано. Независимые утверждения, принадлежащие этой модели, аналогичны встроенным многозначным зависимостям (EMVD) в базах данных. ^{[1] [7]}

Графо-индуцированные графоиды

Если существует неориентированный граф G такой, что

${\displaystyle I(X,Z,Y)\Leftrightarrow \langle X,Z,Y\rangle _{G},}$

то графоид называется граф-индуцированным. Другими словами, существует неориентированный граф G , такой что каждое утверждение независимости в M отражается как разделение вершин в G и наоборот. Необходимым и достаточным условием для того, чтобы модель зависимости была граф-индуцированным графоидом, является то, что она удовлетворяет следующим аксиомам: симметрия, разложение, пересечение, сильное объединение и транзитивность.

Сильный профсоюз заявляет, что

${\displaystyle I(X,Z,Y)\implies I(X,Z\cup W,Y)}$

Транзитивность утверждает, что

${\displaystyle I(X,Z,Y)\implies \left(\forall ~\gamma \notin X\cup Y\cup Z,~~I(X,Z,\gamma ){\text{ or }}I(\gamma ,Z,Y)\right)}$

Аксиомы симметрии, разложения, пересечения, сильного объединения и транзитивности составляют полную характеристику неориентированных графов. ^[9]

Графоиды, вызванные DAG

Графоид называется DAG-индуцированным, если существует направленный ациклический граф D такой, что где обозначает d - разделение в D. d -разделение ( d -обозначает «направленный») расширяет понятие разделения вершин с ненаправленных графов на направленные ациклические графы. Это позволяет считывать условные независимости из структуры байесовских сетей . Однако условные независимости в DAG не могут быть полностью охарактеризованы конечным набором аксиом. ^[10] ${\displaystyle I(X,Z,Y)\Leftrightarrow \langle X,Z,Y\rangle _{D}}$ ${\displaystyle \langle X,Z,Y\rangle _{D}}$

Включение и строительство

Графоиды, индуцированные графом и DAG, оба содержатся в вероятностных графоидах. ^[11] Это означает, что для каждого графа G существует распределение вероятностей P, такое, что каждая условная независимость в P представлена ​​в G , и наоборот. То же самое верно для DAG. Однако существуют вероятностные распределения, которые не являются графоидами, и, более того, не существует конечной аксиоматизации для вероятностных условных зависимостей. ^[12]

Томас Верма показал, что каждый полуграфоид имеет рекурсивный способ построения DAG, в котором каждое d -разделение является допустимым. ^[13] Конструкция похожа на ту, что используется в сетях Байеса , и выглядит следующим образом:

1. Расположим переменные в произвольном порядке 1, 2,...,i,..., N и, начиная с i  = 1,
2. выберем для каждого узла i набор узлов PA _i такой, что i независим от всех своих предшественников, 1, 2,..., i  − 1, обусловленных PA _i .
3. Нарисуйте стрелки от PA _i к i и продолжайте.

DAG, созданный этой конструкцией, будет представлять все условные независимости, которые следуют из тех, которые используются в конструкции. Более того, каждое d -разделение, показанное в DAG, будет действительной условной независимостью в графоиде, используемом в конструкции.

Ссылки

1. Pearl, Judea; Paz, Azaria (1985). «Графоиды: основанная на графах логика для рассуждений об отношениях релевантности» (PDF) .
2. Дэвид, А. Филип (1979). «Условная независимость в статистической теории». Журнал Королевского статистического общества, Серия B : 1–31.
3. Спон, Вольфганг (1980). «Стохастическая независимость, каузальная независимость и экранируемость». Журнал философской логики . 9 : 73–99. doi :10.1007/bf00258078.
4. Перл, Джудеа (1986). «Слияние, распространение и структурирование в сетях убеждений». Искусственный интеллект . 29 (3): 241–288. doi :10.1016/0004-3702(86)90072-x.
5. Верма, Томас; Перл, Джудеа (1988). «Причинные сети: семантика и выразительность». Труды 4-го семинара по неопределенности в искусственном интеллекте : 352–359.
6. Лауритцен, С. Л. (1996). Графические модели . Оксфорд: Clarendon Press.
7. Гейгер, Дэн (1990). «Графоиды: качественная структура для вероятностного вывода» (докторская диссертация, технический отчет R-142, кафедра компьютерных наук, Калифорнийский университет, Лос-Анджелес) .
8. Pearl, Judea (1988). Вероятностное рассуждение в интеллектуальных системах: сети правдоподобного вывода . Морган Кауфманн.
9. А. Пас, Дж. Перл и С. Ур, «Новая характеристика графов на основе отношений перехвата», Журнал теории графов, т. 22, № 2, 125-136, 1996.
10. Гейгер, Д. (1987). "Неаксиоматизируемость зависимостей в направленных ациклических графах" (PDF) . UCLA Computer Science Tech Report R-83 .
11. Гейгер, Д.; Перл, Дж. (1993). «Логические и алгоритмические свойства условной независимости и графические модели». Анналы статистики . 21 (4): 2001–2021. CiteSeerX 10.1.1.295.2043 . doi :10.1214/aos/1176349407. 
12. Studeny, M. (1992). Kubik, S.; Visek, JA (ред.). «Условные отношения независимости не имеют конечной полной характеризации». Теория информации, статистические функции принятия решений и случайные процессы. Труды 11-й Пражской конференции . B. Dordrecht: Kluwer: 377–396.
13. Verma, T.; Pearl, J. (1990). Shachter, R.; Levitt, TS; Kanal, LN (ред.). «Причинные сети: семантика и выразительность». Неопределенность в ИИ 4 . Elsevier Science Publishers: 69–76.