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

Алгоритм дерева соединений (также известный как «дерево клик») — это метод, используемый в машинном обучении для извлечения маргинализации в общих графах . По сути, это влечет за собой распространение убеждений на модифицированном графе, называемом деревом соединений . Граф называется деревом, поскольку он разветвляется на разные разделы данных; узлы переменных являются ветвями. ^[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]

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

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

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

Ссылки

^ Jump up to: ^а ^б ^с Паскин, Марк. «Краткий курс графических моделей» (PDF) . Стэнфорд .
^ «Алгоритм вывода» . www.dfki.de. Проверено 25 октября 2018 г.
^ Jump up to: ^а ^б ^с ^д «Краткий обзор графических моделей» (PDF) .
^ Jump up to: ^а ^б ^с «Алгоритмы» (PDF) . Массачусетский технологический институт . 2014.
^ Роуэйс, Сэм (2004). «Алгоритм вывода Хьюгина» (PDF) . Нью-Йоркский университет .
^ «Алгоритмы вывода» (PDF) . Массачусетский технологический институт . 2014.
^ Jump up to: ^а ^б Клопотек, Мечислав А. (6 июня 2018 г.). «Демпстерианско-шаферианская сеть убеждений на основе данных». arXiv : 1806.02373 [ cs.AI ].
^ Jump up to: ^а ^б Уэйнрайт, Мартин (31 марта 2008 г.). «Графические модели, алгоритмы передачи сообщений и вариационные методы: Часть I» (PDF) . Беркли EECS . Проверено 16 ноября 2016 г.
^ «Кликовой граф» . Проверено 16 ноября 2016 г.
^ Барбер, Дэвид (28 января 2014 г.). «Вероятностное моделирование и рассуждения, алгоритм дерева соединений» (PDF) . Университет Хельсинки . Проверено 16 ноября 2016 г.
^ Рамирес, Хулио К.; Муньос, Гильермина; Гутьеррес, Людивина (сентябрь 2009 г.). «Диагностика неисправностей в промышленном процессе с использованием байесовских сетей: применение алгоритма дерева соединений». 2009 Конференция по электронике, робототехнике и автомобильной механике (CERMA) . IEEE. дои : 10.1109/cerma.2009.28 .
^ Цзинь, Вэнгун (февраль 2018 г.). «Вариационный автоэнкодер соединительного дерева для генерации молекулярных графов». Корнеллский университет . arXiv : 1802.04364 . Бибкод : 2018arXiv180204364J .
^ CERMA 2009: материалы: 2009 Конференция по электронике, робототехнике и автомобильной механике: 22-25 сентября 2009 г.: Куэрнавака, Морелос, Мексика . Институт инженеров электротехники и электроники. Лос Аламитос, Калифорния: Компьютерное общество IEEE. 2009. ISBN 9780769537993 . OCLC 613519385 . {{cite book}}: CS1 maint: другие ( ссылка )

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

Лауритцен, Штеффен Л.; Шпигельхальтер, Дэвид Дж. (1988). «Локальные вычисления с вероятностями на графических структурах и их применение в экспертных системах». Журнал Королевского статистического общества. Серия Б (Методическая) . 50 (2): 157–224. дои : 10.1111/j.2517-6161.1988.tb01721.x . JSTOR 2345762 . МР 0964177 .
Дэвид, AP (1992). «Применение общего алгоритма распространения для вероятностных экспертных систем». Статистика и вычисления . 2 (1): 25–26. дои : 10.1007/BF01890546 . S2CID 61247712 .
Хуанг, Сесил; Дарвич, Аднан (1996). «Вывод в сетях убеждений: процедурное руководство» . Международный журнал приближенного рассуждения . 15 (3): 225–263. CiteSeerX 10.1.1.47.3279 . дои : 10.1016/S0888-613X(96)00069-2 .
Лепар В., Шеной П. (1998). «Сравнение архитектур Лауритцена-Шпигельхальтера, Хугина и Шеной-Шафера для вычисления пределов вероятностных распределений». https://arxiv.org/ftp/arxiv/papers/1301/1301.7394.pdf

[:1-1] Jump up to: ^а ^б ^с Паскин, Марк. «Краткий курс графических моделей» (PDF) . Стэнфорд .

[2] «Алгоритм вывода» . www.dfki.de. Проверено 25 октября 2018 г.

[:2-3] Jump up to: ^а ^б ^с ^д «Краткий обзор графических моделей» (PDF) .

[:3-4] Jump up to: ^а ^б ^с «Алгоритмы» (PDF) . Массачусетский технологический институт . 2014.

[5] Роуэйс, Сэм (2004). «Алгоритм вывода Хьюгина» (PDF) . Нью-Йоркский университет .

[6] «Алгоритмы вывода» (PDF) . Массачусетский технологический институт . 2014.

[:02-7] Jump up to: ^а ^б Клопотек, Мечислав А. (6 июня 2018 г.). «Демпстерианско-шаферианская сеть убеждений на основе данных». arXiv : 1806.02373 [ cs.AI ].

[:0-8] Jump up to: ^а ^б Уэйнрайт, Мартин (31 марта 2008 г.). «Графические модели, алгоритмы передачи сообщений и вариационные методы: Часть I» (PDF) . Беркли EECS . Проверено 16 ноября 2016 г.

[9] «Кликовой граф» . Проверено 16 ноября 2016 г.

[10] Барбер, Дэвид (28 января 2014 г.). «Вероятностное моделирование и рассуждения, алгоритм дерева соединений» (PDF) . Университет Хельсинки . Проверено 16 ноября 2016 г.

[11] Рамирес, Хулио К.; Муньос, Гильермина; Гутьеррес, Людивина (сентябрь 2009 г.). «Диагностика неисправностей в промышленном процессе с использованием байесовских сетей: применение алгоритма дерева соединений». 2009 Конференция по электронике, робототехнике и автомобильной механике (CERMA) . IEEE. дои : 10.1109/cerma.2009.28 .

[12] Цзинь, Вэнгун (февраль 2018 г.). «Вариационный автоэнкодер соединительного дерева для генерации молекулярных графов». Корнеллский университет . arXiv : 1802.04364 . Бибкод : 2018arXiv180204364J .

[13] CERMA 2009: материалы: 2009 Конференция по электронике, робототехнике и автомобильной механике: 22-25 сентября 2009 г.: Куэрнавака, Морелос, Мексика . Институт инженеров электротехники и электроники. Лос Аламитос, Калифорния: Компьютерное общество IEEE. 2009. ISBN 9780769537993 . OCLC 613519385 . {{cite book}}: CS1 maint: другие ( ссылка )

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]