Сети зависимостей (DN) представляют собой графические модели , подобные сетям Маркова , в которых каждая вершина (узел) соответствует случайной переменной, а каждое ребро фиксирует зависимости между переменными. В отличие от байесовских сетей , DN могут содержать циклы. Каждый узел связан с таблицей условной вероятности, которая определяет реализацию случайной величины с учетом ее родителей. [1]
Марковское одеяло
В байесовской сети , то марковское узла есть множество родителей и детей этого узла, вместе с родителями детей. Значения родителей и потомков узла, очевидно, дают информацию об этом узле. Однако родители его детей также должны быть включены в марковское одеяло, потому что их можно использовать для объяснения рассматриваемого узла. В марковском случайном поле , то одеяло Маркова для узла просто прилегающие к нему (или соседним) узлы. В сети зависимостей марковское одеяло для узла - это просто набор его родителей.
Сеть зависимостей против байесовских сетей
Сети зависимостей имеют преимущества и недостатки по сравнению с байесовскими сетями. В частности, их легче параметризовать на основе данных, поскольку существуют эффективные алгоритмы для изучения как структуры, так и вероятностей сети зависимостей на основе данных. Такие алгоритмы недоступны для байесовских сетей, для которых задача определения оптимальной структуры NP-сложна. [2] Тем не менее, сеть зависимостей может быть труднее построить с использованием подхода, основанного на знаниях, основанного на экспертных знаниях.
Сети зависимостей против сетей Маркова
Согласованные сети зависимостей и сети Маркова обладают одинаковой репрезентативной силой. Тем не менее, можно построить несовместимые сети зависимостей, т. Е. Сети зависимостей, для которых не существует совместимого действительного совместного распределения вероятностей . Марковские сети, напротив, всегда непротиворечивы.
Определение
Последовательная сеть зависимостей для набора случайных величин с совместным распределением пара где - это циклический ориентированный граф, каждый из узлов которого соответствует переменной в , а также представляет собой набор условных вероятностных распределений. Родители узла, обозначенный , соответствуют этим переменным которые удовлетворяют следующим отношениям независимости
Сеть зависимостей согласована в том смысле, что каждое локальное распределение может быть получено из совместного распределения. . Сети зависимостей, изученные с использованием больших наборов данных с большими размерами выборки, почти всегда будут согласованными. Несогласованная сеть - это сеть, для которой нет совместного распределения вероятностей, совместимого с парой. В этом случае не существует совместного распределения вероятностей, которое удовлетворяет отношениям независимости, входящим в эту пару.
Структура и параметры обучения
Две важные задачи в сети зависимостей - это изучение ее структуры и вероятностей на основе данных. По сути, алгоритм обучения состоит из независимого выполнения вероятностной регрессии или классификации для каждой переменной в домене. Это происходит из наблюдения, что локальное распределение для переменной в сети зависимостей условное распределение , который можно оценить с помощью любого количества методов классификации или регрессии, таких как методы, использующие вероятностное дерево решений, нейронную сеть или машину вероятностных опорных векторов. Следовательно, для каждой переменной в домене , мы независимо оцениваем его локальное распределение на основе данных с помощью алгоритма классификации, даже если это отдельный метод для каждой переменной. Здесь мы кратко покажем, как вероятностные деревья решений используются для оценки локальных распределений. Для каждой переменной в , изучается вероятностное дерево решений, где целевая переменная и - входные переменные. Чтобы изучить древовидную структуру решений для, алгоритм поиска начинается с одноэлементного корневого узла без дочерних узлов. Затем каждый листовой узел в дереве заменяется двоичным разбиением по некоторой переменной. в , пока никакие замены не увеличат счет дерева.
Вероятностный вывод
Вероятностный вывод - это задача, в которой мы хотим ответить на вероятностные запросы вида , учитывая графическую модель для , где ("целевые" переменные) («входные» переменные) являются непересекающимися подмножествами . Одна из альтернатив для выполнения вероятностных выводов - использование выборки Гиббса . Наивный подход для этого использует упорядоченный сэмплер Гиббса, чья важная трудность заключается в том, что если либо или же мала, то для точной оценки вероятности требуется много итераций. Другой подход к оценке когда заключается в использовании модифицированного заказанного сэмплера Гиббса, где он фиксирует во время отбора проб Гиббса.
Также может случиться так, что редко, например содержит много переменных. Таким образом, закон полной вероятности вместе с зависимостями, закодированными в сети зависимостей, можно использовать для разложения задачи вывода на набор задач вывода по отдельным переменным. Этот подход имеет то преимущество, что некоторые термины могут быть получены прямым поиском, что позволяет избежать некоторой выборки Гиббса.
Ниже вы можете увидеть алгоритм, который можно использовать для получения для конкретного случая а также , где а также непересекающиеся подмножества.
- Алгоритм 1:
- (* необработанные переменные *)
- (* обрабатываемые и кондиционирующие переменные *)
- (* значения для *)
- Пока :
- Выбирать такой, что нет больше родителей в чем любая переменная в
- Если все родители находятся в
- Еще
- Используйте модифицированный заказанный сэмплер Гиббса для определения
- Возвращает произведение условных выражений.
Приложения
В дополнение к приложениям для вероятностного вывода, следующие приложения относятся к категории совместной фильтрации (CF), которая является задачей прогнозирования предпочтений. Сети зависимостей - это естественный класс модели, на котором основываются прогнозы CF, поскольку алгоритм для этой задачи требует только оценкидать рекомендации. В частности, эти оценки могут быть получены прямым поиском в сети зависимостей.
- Предсказать, какие фильмы понравятся человеку, на основе его оценок просмотренных фильмов;
- Прогнозирование того, к каким веб-страницам будет обращаться человек, на основе его или ее истории на сайте;
- Предсказание того, какие новости интересуют человека, на основе других историй, которые он или она прочитали;
- Предсказание того, какой продукт будет покупать человек, на основе продуктов, которые он или она уже купил и / или бросил в свою корзину.
Другой класс полезных приложений для сетей зависимостей связан с визуализацией данных, то есть визуализацией прогнозируемых отношений.
Смотрите также
Рекомендации
- ^ HECKERMAN, Дэвид; МАКСВЕЛЛ К., Дэвид; MEEK, Кристофер; РУНТУЭЙТ, Роберт; КАДИ, Карл (октябрь 2000 г.). «Сети зависимостей для вывода, совместной фильтрации и визуализации данных» (PDF) . Журнал исследований в области машинного обучения .
- ^ ХЕКЕРМАН, Дэвид (2012). «Изучение байесовских сетей на большой выборке - непростая задача» (PDF) . arXiv : 1212,2468 . Цитировать журнал требует
|journal=
( помощь )