Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Пример дерева соединений

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

Алгоритм дерева соединений [ править ]

Алгоритм Хугина [ править ]

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

Алгоритм Шафера-Шеноя [ править ]

  • Вычисляется рекурсивно [3]
  • Множественные рекурсии алгоритма Шафера-Шеноя приводят к алгоритму Хугина [4]
  • Найдено с помощью уравнения передачи сообщений [4]
  • Потенциалы сепаратора не сохраняются [5]

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

Основная теория [ править ]

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

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

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

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

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

Теорема: для неориентированного графа G следующие свойства эквивалентны:

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

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

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

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

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

Алгоритмы вывода [ править ]

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

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

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

Ссылки [ править ]

  1. ^ a b c Паскин, Марк. «Краткий курс графических моделей» (PDF) . Стэнфорд .
  2. ^ «Алгоритм вывода» . www.dfki.de . Проверено 25 октября 2018 .
  3. ^ a b c d "Резюме по графическим моделям" (PDF) .
  4. ^ a b c "Алгоритмы" (PDF) . Массачусетский технологический институт . 2014 г.
  5. ^ Roweis, Сэм (2004). «Алгоритм вывода Хьюгина» (PDF) . NYU .
  6. ^ «Алгоритмы вывода» (PDF) . Массачусетский технологический институт . 2014 г.
  7. ^ a b Kłopotek, Mieczysław A. (06.06.2018). "Демпстерско-Шаферианская сеть убеждений на основе данных". arXiv : 1806.02373 [ cs.AI ].
  8. ^ a b Уэйнрайт, Мартин (31 марта 2008 г.). «Графические модели, алгоритмы передачи сообщений и вариационные методы: Часть I» (PDF) . Беркли EECS . Проверено 16 ноября +2016 .
  9. ^ "График клики" . Проверено 16 ноября +2016 .
  10. ↑ Барбер, Дэвид (28 января 2014 г.). "Вероятностное моделирование и рассуждение, алгоритм дерева соединений" (PDF) . Университет Хельсинки . Проверено 16 ноября +2016 .
  11. ^ «Диагностика неисправностей в промышленном процессе с использованием байесовских сетей: применение алгоритма дерева соединений - публикация конференции IEEE». DOI : 10,1109 / CERMA.2009.28 . S2CID 6068245 .  Цитировать журнал требует |journal=( помощь )
  12. ^ Jin, Wengong (февраль 2018). "Вариационный автоэнкодер Junction Tree для построения молекулярных графов". Корнельский университет . arXiv : 1802.04364 . Bibcode : 2018arXiv180204364J .
  13. ^ CERMA 2009: сборник: 2009 Конференция по электронике, робототехнике и автомобильной механике: 22-25 сентября 2009 г .: Куэрнавака, Морелос, Мексика . Институт инженеров по электротехнике и радиоэлектронике. Лос-Аламитос, Калифорния: Компьютерное общество IEEE. 2009. ISBN. 9780769537993. OCLC  613519385 .CS1 maint: другие ( ссылка )
  • Lauritzen, Steffen L .; Шпигельхальтер, Дэвид Дж. (1988). «Локальные вычисления с вероятностями на графических структурах и их приложение к экспертным системам». Журнал Королевского статистического общества. Серия Б (Методическая) . 50 (2): 157–224. DOI : 10.1111 / j.2517-6161.1988.tb01721.x . JSTOR  2345762 . Руководство по ремонту  0964177 .
  • Давид, AP (1992). «Приложения общего алгоритма распространения для вероятностных экспертных систем». Статистика и вычисления . 2 (1): 25–26. DOI : 10.1007 / BF01890546 . S2CID  61247712 .
  • Хуанг, Сесил; Дарвиче, Аднан (1996). «Вывод в сетях убеждений: процедурное руководство» . Международный журнал приблизительных рассуждений . 15 (3): 225–263. CiteSeerX  10.1.1.47.3279 . DOI : 10.1016 / S0888-613X (96) 00069-2 .
  • Паскин, Марк А. "Краткий курс графических моделей: 3. Алгоритмы дерева соединений" (PDF) . Архивировано 19 марта 2015 года. Цитировать журнал требует |journal=( помощь )CS1 maint: неподходящий URL ( ссылка )
  • Лепар В., Шеной П. (1998). «Сравнение архитектур Lauritzen-Spiegelhalter, Hugin и Shenoy-Shafer для вычисления пределов вероятностных распределений». https://arxiv.org/ftp/arxiv/papers/1301/1301.7394.pdf