Алгоритм дерева соединений - Junction tree algorithm

Пример дерева соединений

В алгоритм дерева соединений (также известный как «дерево кликов») - метод, используемый в машинное обучение извлекать маргинализация в целом графики. По сути, это влечет за собой выполнение распространение веры на модифицированном графе, называемом дерево соединений. Граф называется деревом, потому что он разветвляется на разные разделы данных; узлы переменных - это ветви.[1] Основная предпосылка - исключить циклы путем кластеризации их в отдельные узлы. Несколько обширных классов запросов могут быть скомпилированы одновременно в более крупные структуры данных.[1] Они разные алгоритмы для удовлетворения конкретных потребностей и того, что необходимо рассчитать. Алгоритмы вывода собирать новые изменения в данных и рассчитывать их на основе новой предоставленной информации.[2]

Алгоритм дерева соединений

Алгоритм Хугина

Обратите внимание, что этот последний шаг неэффективен для графов больших ширина дерева. Вычисление сообщений для передачи между надузлами включает в себя точную маргинализацию переменных в обоих надузлах. Таким образом, выполнение этого алгоритма для графа с шириной дерева k будет иметь по крайней мере одно вычисление, которое требует экспоненциального времени по k. Это передача сообщений алгоритм.[3] Алгоритм Хьюгина занимает меньше вычисления найти решение по сравнению с Шафер-Шеной.

Алгоритм Шафера-Шеноя

Шафер-Шеной алгоритм это сумма продукта соединительного дерева.[6] Он используется, потому что он выполняет программы и запросы более эффективно, чем алгоритм Хугина. Алгоритм производит расчет условных выражений для функции убеждений возможный.[7] Совместные раздачи необходимы для выполнения локальных вычислений.[7]

Основная теория

Пример динамической байесовской сети

Первый шаг касается только Байесовские сети, и представляет собой процедуру превращения ориентированного графа в ненаправленный один. Мы делаем это, потому что это обеспечивает универсальную применимость алгоритма, независимо от направления.

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

Пример хордального графа

Третий шаг - убедиться, что графики построены хордовый если они еще не хордовые. Это первый важный шаг алгоритма. Он использует следующую теорему:[8]

Теорема: Для ненаправленный graph, G, следующие свойства эквивалентны:

  • График G триангулирован.
  • Граф клик группы G имеет дерево соединений.
  • Для G существует порядок исключения, который не приводит ни к каким добавленным ребрам.

Таким образом, триангуляция граф, мы убеждаемся, что соответствующее дерево соединений существует. Обычный способ сделать это - определить порядок удаления узлов, а затем запустить Исключение переменных алгоритм. В исключение переменных алгоритм утверждает, что алгоритм должен запускаться каждый раз, когда появляется другой запрос.[1] Это приведет к добавлению дополнительных ребер к исходному графу таким образом, что на выходе будет хордовый граф. Все хордовые графы имеют дерево соединений.[4] Следующим шагом будет построение дерево соединений. Для этого мы используем график из предыдущего шага и формируем соответствующий ему график. граф клики.[9] Следующая теорема дает нам способ найти дерево соединений:[8]

Теорема: Для триангулированного графа взвесьте ребра графа клик по их мощности | A∩B | пересечения смежных клик A и B. Тогда любое остовное дерево максимального веса графа клик является деревом соединений.

Итак, чтобы построить дерево соединений, нам просто нужно извлечь остовное дерево максимального веса из графа клик. Это можно эффективно сделать, например, изменив Алгоритм Краскала. Последний шаг - применить распространение веры к полученному дереву соединений.[10]

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

Алгоритмы вывода

Cutset кондиционирование

Циклическое распространение убеждений: Другой метод интерпретации сложных графиков. В шаткое распространение убеждений используется, когда требуется приближенное решение вместо точное решение.[13] Это приблизительный вывод.[3]

Кондиционирование Cutset: Используется с меньшими наборами переменных. Cutset кондиционирование позволяет создавать более простые графики, которые легче читать, но не точный.[3]

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

  1. ^ а б c Паскин, Марк. «Краткий курс графических моделей» (PDF). Стэнфорд.
  2. ^ «Алгоритм вывода». www.dfki.de. Получено 2018-10-25.
  3. ^ а б c d «Обзор графических моделей» (PDF).
  4. ^ а б c «Алгоритмы» (PDF). Массачусетский Институт Технологий. 2014.
  5. ^ Роуис, Сэм (2004). «Алгоритм вывода Хьюгина» (PDF). NYU.
  6. ^ «Алгоритмы вывода» (PDF). Массачусетский Институт Технологий. 2014.
  7. ^ а б Клопотек, Мечислав А. (06.06.2018). "Демпстерско-Шаферианская сеть убеждений на основе данных". arXiv:1806.02373 [cs.AI ].
  8. ^ а б Уэйнрайт, Мартин (31 марта 2008 г.). «Графические модели, алгоритмы передачи сообщений и вариационные методы: Часть I» (PDF). Berkeley EECS. Получено 16 ноября 2016.
  9. ^ «График кликов». Получено 16 ноября 2016.
  10. ^ Барбер, Дэвид (28 января 2014 г.). «Вероятностное моделирование и рассуждение, алгоритм дерева соединений» (PDF). Университет Хельсинки. Получено 16 ноября 2016.
  11. ^ «Диагностика неисправностей в промышленном процессе с использованием байесовских сетей: применение алгоритма дерева соединений - публикация конференции IEEE». Дои:10.1109 / CERMA.2009.28. S2CID  6068245. Цитировать журнал требует | журнал = (помощь)
  12. ^ Цзинь, Венгун (февраль 2018 г.). "Вариационный автоэнкодер Junction Tree для построения молекулярных графов". Корнелл Университет. arXiv:1802.04364. Bibcode:2018arXiv180204364J.
  13. ^ CERMA 2009: протокол: 2009 Конференция по электронике, робототехнике и автомобильной механике: 22-25 сентября 2009: Куэрнавака, Морелос, Мексика. Институт инженеров по электротехнике и радиоэлектронике. Лос-Аламитос, Калифорния: Компьютерное общество IEEE. 2009 г. ISBN  9780769537993. OCLC  613519385.CS1 maint: другие (связь)