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

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

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

Алгоритм программы «Hugin»

• Если граф ориентированный, то морализуем его, чтобы сделать его неориентированным
• Формируем сведения
• Триангулируем граф, чтобы получить хордальный граф
• Строим дерево сочленений из триагулированного графа (мы будем называть вершины дерева сочленений «суперузлами»)
• Осуществляем пропагацию вероятностей вдоль дерева сочленений (с помощью алгоритма распространения доверия)

Заметим, что последний шаг неэффективен для графов с большой древесной шириной. Вычисление сообщений, передаваемых между суперузлами, требует точной маргинализации в обоих суперузлах. Реализация алгоритма на графе с шириной дерева k потребует вычисления, экспоненциально зависящие по времени от значения k.

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

• Триангулируем граф, проводя исключения в произвольном порядке (если требуется).
• Находим максимальные клики в хордальном графе.
• Находим разделяющие множества для каждой пары максимальных клик и строим взвешенный граф клик.
• Находим остовное дерево максимального веса на графе клик, чтобы получить дерево сочленений.
• Определяем потенциалы на дереве сочлениний.
• Вычисляем сумму произведений на дереве сочленений. Этот способ модификации сведений (передачи сообщений). Этот шаг, собственно, и известен как Алгоритм Шафера — Шеноя.
• Вычисляем маргиналы.

Общее время работы алгоритма $O(N^{2}D+N^{2}log(N)+N\mid \chi \mid ^{D})$, где N — число вершин, D — размер наибольшей клики, $\mid \chi \mid ^{D}$ — максимальный размер алфавита в узле

Заметим, что размер наибольшей клики D зависит от порядка исключения и минимальный размер равен древесной ширине.

В сущности, алгоритм Hugin делает то же самое, но шаги 5 и 6 выполняются иначе с целью сокращения числа умножений.

Теоретические основы (для алгоритма Hugin)

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

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

На третьем шаге добиваемся, чтобы графы стали хордальными, если они уже не хордальны. Это первая существенная часть алгоритма. Для этого используется следующая теорема:

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

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

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

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

Таким образом, для построения дерева сочленений нужно выделить остовное дерево максимального веса из графа клик. Это можно эффективно сделать, например, модифицируя алгоритм Краскала. На последнем шаге применяется алгоритм распространения доверия к полученному дереву сочленений.