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

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

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

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

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

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

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

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

Определение

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

${\displaystyle 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}}).}$

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

Структура и параметры обучения

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

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

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

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

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

• Алгоритм 1:

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

Приложения

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

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

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

Смотрите также

• Сеть реляционных зависимостей

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

1. ХЕКЕРМАН, Дэвид; МАКСВЕЛЛ К., Дэвид; MEEK, Кристофер; РУНТУЭЙТ, Роберт; КАДИ, Карл (октябрь 2000 г.). «Сети зависимостей для вывода, совместной фильтрации и визуализации данных» (PDF). Журнал исследований в области машинного обучения.
2. ХЕКЕРМАН, Дэвид. «Изучение байесовских сетей на большой выборке - непростая задача» (PDF).