графоид

Эта статья об использовании в логике и вероятности. Чтобы узнать об использовании в теории матроидов, см. Matroid .

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

История

Джудея Перл и Азария Пас ввел термин «графоиды» после того, как обнаружил, что набор аксиом, управляющих условной независимостью в теории вероятностей, является общим для неориентированных графов . Переменные представлены в виде узлов на графе таким образом, что наборы переменных X и Y независимы от Z в распределении всякий раз, когда набор узлов Z отделяет X от Y в графе. Аксиомы условной независимости по вероятности были выведены ранее А. Филипом Давидом. и Вольфганг Шпон . Позднее соответствие между зависимостью и графами было расширено до ориентированных ациклических графов (DAG). и к другим моделям зависимости.

Определение

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

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

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

Виды графоидов

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

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

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

является полуграфоидом, который становится полным графоидом, когда P строго положительно.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$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)$

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

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

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

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

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

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

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, будет действительной условной независимостью в графоиде, используемом при построении.