stringtranslate.com

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

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

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

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

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

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

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

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

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

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

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

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

Пример хордового графа

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

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

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

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

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

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

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

Кондиционирование среза

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

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

Ссылки

  1. ^ abc Паскин, Марк. «Краткий курс по графическим моделям» (PDF) . Стэнфорд .
  2. ^ "Алгоритм вывода". www.dfki.de . Получено 25.10.2018 .
  3. ^ abcd «Обзор графических моделей» (PDF) .
  4. ^ abc "Алгоритмы" (PDF) . Массачусетский технологический институт . 2014.
  5. ^ Роуайс, Сэм (2004). «Алгоритм вывода Хьюгина» (PDF) . Нью-Йоркский университет .
  6. ^ "Алгоритмы вывода" (PDF) . Массачусетский технологический институт . 2014.
  7. ^ аб Клопотек, Мечислав А. (6 июня 2018 г.). «Демпстерианско-шаферианская сеть убеждений на основе данных». arXiv : 1806.02373 [cs.AI].
  8. ^ ab Wainwright, Martin (31 марта 2008 г.). "Графические модели, алгоритмы передачи сообщений и вариационные методы: Часть I" (PDF) . Berkeley EECS . Получено 16 ноября 2016 г.
  9. ^ "Clique Graph" . Получено 16 ноября 2016 г.
  10. ^ Барбер, Дэвид (28 января 2014 г.). «Вероятностное моделирование и рассуждение, алгоритм дерева соединений» (PDF) . Университет Хельсинки . Получено 16 ноября 2016 г. .
  11. ^ Рамирес, Хулио К.; Муньос, Гильермина; Гутьеррес, Людивина (сентябрь 2009 г.). «Диагностика неисправностей в промышленном процессе с использованием байесовских сетей: применение алгоритма дерева соединений». Конференция по электронике, робототехнике и автомобильной механике 2009 г. (CERMA) . IEEE. doi :10.1109/cerma.2009.28.
  12. ^ Jin, Wengong (февраль 2018 г.). «Вариационный автокодировщик дерева соединений для генерации молекулярных графов». Корнельский университет . arXiv : 1802.04364 . Bibcode : 2018arXiv180204364J.
  13. ^ CERMA 2009 : труды : 2009 Electronics, Robotics and Automotive Mechanics Conference : 22-25 сентября 2009 : Куэрнавака, Морелос, Мексика . Institute of Electrical and Electronic Engineers. Los Alamitos, Calif.: IEEE Computer Society. 2009. ISBN 9780769537993. OCLC  613519385.{{cite book}}: CS1 maint: другие ( ссылка )

Дальнейшее чтение