Сеть зависимостей (графическая модель)

Сети зависимостей (DN) — это графические модели , похожие на сети Маркова , в которых каждая вершина (узел) соответствует случайной величине, а каждое ребро фиксирует зависимости между переменными. В отличие от байесовских сетей , DN могут содержать циклы. Каждый узел связан с таблицей условной вероятности, которая определяет реализацию случайной величины с учетом ее родителей.

Марковское одеяло

В байесовской сети марковское одеяло узла представляет собой набор родителей и детей этого узла вместе с родителями детей. Значения родителей и детей узла, очевидно, дают информацию об этом узле. Однако родители его детей также должны быть включены в одеяло Маркова, поскольку их можно использовать для объяснения рассматриваемого узла. В марковском случайном поле марковское одеяло для узла — это просто его соседние (или соседние) узлы. В сети зависимостей марковское одеяло для узла — это просто набор его родителей.

Сеть зависимостей и байесовские сети

Сети зависимостей имеют преимущества и недостатки по сравнению с байесовскими сетями. В частности, их легче параметризовать на основе данных, поскольку существуют эффективные алгоритмы для изучения структуры и вероятностей сети зависимостей на основе данных. Такие алгоритмы недоступны для байесовских сетей, для которых задача определения оптимальной структуры является NP-трудной. Тем не менее, сеть зависимостей может быть сложнее построить, используя подход, основанный на знаниях, основанный на экспертных знаниях.

Сети зависимостей и сети Маркова

Сети согласованных зависимостей и сети Маркова обладают одинаковой репрезентативной силой. Тем не менее, можно построить непоследовательные сети зависимостей, т. е. сети зависимостей, для которых не существует совместимого действительного совместного распределения вероятностей . Марковские сети, напротив, всегда непротиворечивы.

Определение

Согласованная сеть зависимостей для набора случайных величин ${\textstyle \mathbf {X} =(X_{1},\ldots ,X_{n})}$ при совместном распределении $p(\mathbf {x} )$ это пара $(G,P)$ где $G$ представляет собой циклический ориентированный граф, каждый из его узлов соответствует переменной в $\mathbf {X}$, и $P$ представляет собой набор условных распределений вероятностей. Родители узла $X_{i}$, обозначенный $\mathbf {Pa_{i}}$, соответствуют этим переменным $\mathbf {Pa_{i}} \subseteq (X_{1},\ldots ,X_{i-1},X_{i+1},\ldots ,X_{n})$ которые удовлетворяют следующим отношениям независимости

$p(x_{i}\mid \mathbf {pa_{i}} )=p(x_{i}\mid x_{1},\ldots ,x_{i-1},x_{i+1},\ldots ,x_{n})=p(x_{i}\mid \mathbf {x} -{x_{i}}).$

Сеть зависимостей непротиворечива в том смысле, что каждый локальный дистрибутив может быть получен из совместного дистрибутива. $p(\mathbf {x} )$. Сети зависимостей, изученные с использованием больших наборов данных и больших размеров выборки, почти всегда будут согласованными. Несогласованная сеть — это сеть, для которой не существует совместного распределения вероятностей, совместимого с парой $(G,P)$. В этом случае не существует совместного распределения вероятностей, которое удовлетворяло бы отношениям независимости, входящим в состав этой пары.

Изучение структуры и параметров

Две важные задачи в сети зависимостей — изучить ее структуру и вероятности на основе данных. По сути, алгоритм обучения состоит из независимого выполнения вероятностной регрессии или классификации для каждой переменной в предметной области. Это следует из наблюдения, что локальное распределение переменной $X_{i}$ в сети зависимостей — это условное распределение $p(x_{i}|\mathbf {x} -{x_{i}})$, который можно оценить с помощью любого количества методов классификации или регрессии, таких как методы, использующие вероятностное дерево решений, нейронную сеть или вероятностную машину опорных векторов. Следовательно, для каждой переменной $X_{i}$ в домене $X$, мы независимо оцениваем его локальное распределение на основе данных, используя алгоритм классификации, хотя для каждой переменной это отдельный метод.Здесь мы кратко покажем, как вероятностные деревья решений используются для оценки локальных распределений. Для каждой переменной $X_{i}$ в $\mathbf {X}$, вероятностное дерево решений изучается, где $X_{i}$ целевая переменная и $\mathbf {X} -X_{i}$ являются входными переменными. Изучить структуру дерева решений для $X_{i}$, алгоритм поиска начинается с одноэлементного корневого узла без дочерних элементов. Затем каждый листовой узел в дереве заменяется двоичным разбиением по некоторой переменной. $X_{j}$ в $\mathbf {X} -X_{i}$, пока никакие замены не увеличат оценку дерева.

Вероятностный вывод

Вероятностный вывод — это задача, в которой мы хотим ответить на вероятностные запросы вида $p(\mathbf {y\mid z} )$, учитывая графическую модель для $\mathbf {X}$, где $\mathbf {Y}$ (целевые переменные) $\mathbf {Z}$ («входные» переменные) представляют собой непересекающиеся подмножества $\mathbf {X}$. Одной из альтернатив выполнения вероятностного вывода является использование выборки Гиббса . Наивный подход для этого использует упорядоченный сэмплер Гиббса, важная трудность которого заключается в том, что если либо $p(\mathbf {y\mid z} )$ или $p(\mathbf {z} )$ мала, то для точной оценки вероятности требуется много итераций. Другой подход к оценке $p(\mathbf {y\mid z} )$ когда $p(\mathbf {z} )$ мал, - использовать модифицированный упорядоченный пробоотборник Гиббса, где $\mathbf {Z=z}$ фиксируется во время выборки Гиббса.

Может также случиться, что $\mathbf {y}$ бывает редко, например, когда $\mathbf {Y}$ имеет много переменных. Таким образом, закон полной вероятности вместе с зависимостями, закодированными в сети зависимостей, можно использовать для разложения задачи вывода на набор задач вывода по одиночным переменным. Преимущество этого подхода заключается в том, что некоторые термины можно получить путем прямого поиска, что позволяет избежать выборки Гиббса.

Ниже вы можете увидеть алгоритм, который можно использовать для получения $p(\mathbf {y|z} )$ для конкретного экземпляра $\mathbf {y} \in \mathbf {Y}$ и $\mathbf {z} \in \mathbf {Z}$, где $\mathbf {Y}$ и $\mathbf {Z}$ являются непересекающимися подмножествами.

• Алгоритм 1:

1. $\mathbf {U:=Y}$ (*необработанные переменные *)
2. $\mathbf {P:=Z}$ (* обрабатываемые и кондиционирующие переменные *)
3. $\mathbf {p:=z}$ (* значения для $\mathbf {P}$ *)
4. Пока $\mathbf {U} \neq \emptyset$:
   1. Выбирать $X_{i}\in \mathbf {U}$ такой, что $X_{i}$ у него больше нет родителей $U$ чем любая переменная в $U$
   2. Если все родители $X$ находятся в $\mathbf {P}$
      1. $p(x_{i}|\mathbf {p} ):=p(x_{i}|\mathbf {pa_{i}} )$
   3. Еще
      1. Используйте модифицированный упорядоченный пробоотборник Гиббса, чтобы определить $p(x_{i}|\mathbf {p} )$
   4. $\mathbf {U:=U} -X_{i}$
   5. $\mathbf {P:=P} +X_{i}$
   6. $\mathbf {p:=p} +x_{i}$
5. Возвращает продукт условных операторов $p(x_{i}|\mathbf {p} )$

Приложения

Помимо приложений для вероятностного вывода, следующие приложения относятся к категории совместной фильтрации (CF), которая представляет собой задачу прогнозирования предпочтений. Сети зависимостей представляют собой естественный класс моделей, на котором можно основывать прогнозы CF, поскольку алгоритму для этой задачи требуется только оценка $p(x_{i}=1|\mathbf {x} -{x_{i}}=0)$ для выработки рекомендаций. В частности, эти оценки могут быть получены путем прямого поиска в сети зависимостей.

• Прогнозирование того, какие фильмы понравятся человеку, на основе его или ее оценок просмотренных фильмов;
• Прогнозирование того, к каким веб-страницам будет обращаться человек, на основе его истории на сайте;
• Прогнозирование того, какие новости интересуют человека, на основе других историй, которые он или она прочитал;
• Прогнозирование того, какой продукт купит человек, на основе продуктов, которые он или она уже купили и/или положили в свою корзину для покупок.

Другой класс полезных приложений для сетей зависимостей связан с визуализацией данных, то есть визуализацией прогнозирующих связей.

См. также

• Реляционная сеть зависимостей