Графоид - Graphoid

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

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

История

Жемчужина Иудеи и Азария Пас[1] придумал термин «графоиды» после того, как обнаружил, что набор аксиом, управляющих условная независимость в теория вероятности разделяет неориентированные графы. Переменные представлены в виде узлов на графике таким образом, что переменные устанавливают Икс и Y независимы, обусловлены Z в распределении всякий раз, когда узел установлен Z отделяет Икс из Y в графике. Аксиомы условной независимости в вероятности были выведены ранее А. Филип Давид[2] и Вольфганг Шпон.[3]Позже соответствие между зависимостью и графиками было расширено на ориентированные ациклические графы (DAG)[4][5][6] и другим моделям зависимости.[1][7]

Определение

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

  1. Симметрия:
  2. Разложение:
  3. Слабый союз:
  4. Сокращение:
  5. Пересечение:

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

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

Вероятностные графоиды[1][7]

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

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

Корреляционные графоиды[1][7]

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

куда это частичная корреляция между Икс и у данный набор Z.

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

Реляционные графоиды[1][7]

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

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

Графоидный графоид

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

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

Крепкий союз утверждает, что

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

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

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

Графоид называется DAG-индуцированным, если существует ориентированный ациклический граф. D такой, что куда означает d-разделение в D. d-разделение (d-созначает «направленный») расширяет понятие разделения вершин с неориентированных графов на ориентированные ациклические графы. Это позволяет считывать условные зависимости из структуры Байесовские сети. Однако условные независимости в DAG не могут быть полностью охарактеризованы конечным набором аксиом.[10]

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

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

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

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

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

Рекомендации

  1. ^ а б c d е Перл, Иудея; Паз, Азария (1985). «Графоиды: основанная на графах логика для рассуждений об отношениях релевантности» (PDF).
  2. ^ Давид, А. Филип (1979). «Условная независимость в статистической теории». Журнал Королевского статистического общества, серия B: 1–31.
  3. ^ Шпон, Вольфганг (1980). «Стохастическая независимость, причинная независимость и защищенность». Журнал философской логики. 9: 73–99. Дои:10.1007 / bf00258078.
  4. ^ Перл, Иудея (1986). «Слияние, распространение и структурирование в сетях убеждений». Искусственный интеллект. 29 (3): 241–288. Дои:10.1016 / 0004-3702 (86) 90072-х.
  5. ^ Верма, Томас; Перл, Иудея (1988). «Причинные сети: семантика и выразительность». Труды 4-го семинара по неопределенности в искусственном интеллекте: 352–359.
  6. ^ Лауритцен, С. (1996). Графические модели. Оксфорд: Clarendon Press.
  7. ^ а б c d Гейгер, Дэн (1990). «Графоиды: качественная основа для вероятностного вывода» (Докторская диссертация, технический отчет R-142, факультет компьютерных наук, Калифорнийский университет, Лос-Анджелес).
  8. ^ а б Перл, Иудея (1988). Вероятностные рассуждения в интеллектуальных системах: сети правдоподобных выводов. Морган Кауфманн.
  9. ^ А. Пас, Дж. Перл и С. Ур, "Новая характеризация графов на основе отношений перехвата", Журнал теории графов, Vol. 22, No. 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. Дои:10.1214 / aos / 1176349407.
  12. ^ Студены, М. (1992). Кубик, С .; Висек, Я. (ред.). «Отношения условной независимости не имеют конечной полной характеристики». Теория информации, статистические функции принятия решений и случайные процессы. Труды 11-й Пражской конференции. Дордрехт: Клувер. B: 377–396.
  13. ^ Verma, T .; Перл, Дж. (1990). Shachter, R .; Левитт, Т.С.; Канал, Л. (ред.). «Причинные сети: семантика и выразительность». Неопределенность в AI 4. Издательство Elsevier Science: 69–76.