Введение в графические модели описывает их как «... брак между теорией графов и теорией вероятностей».
Я получил часть теории вероятностей, но у меня возникли проблемы с пониманием того, куда именно подходит теория графов. Какие выводы из теории графов помогли углубить наше понимание распределения вероятностей и принятия решений в условиях неопределенности?
Я ищу конкретные примеры, помимо очевидного использования теоретико-графовой терминологии в PGM, таких как классификация PGM как «дерева», «двудольного» или «ненаправленного» и т. Д.
Была проведена некоторая работа по исследованию связи между простотой декодирования кодов контроля четности с низкой плотностью (что дает превосходные результаты, если вы считаете это вероятностным графом и применяете распространение Loopy Belief), и обхватом графика, образованного матрицей проверки четности , Эта связь с обхватом уходит корнями в то время, когда были изобретены LDPC [1], но в последнее десятилетие была проведена дальнейшая работа [2] [3] после того, как Mackay et al [4] раздельно открыли их, и их свойства заметили ,
Я часто вижу жемчужный комментарий о времени конвергенции распространения убеждений в зависимости от диаметра цитируемого графика. Но я не знаю какой-либо работы, рассматривающей диаметры графов в не-древовидных графах и какой эффект это имеет.
источник
Одним из успешных применений графовых алгоритмов к вероятностным графическим моделям является алгоритм Чоу-Лю . Он решает проблему нахождения оптимальной (древовидной) структуры графа и основан на алгоритме максимальных связующих деревьев (MST).
Совместная вероятность для графической модели дерева может быть записана как: Нормализованное логарифмическое правдоподобие можно записать следующим образом: где - это взаимная информация между и учетом эмпирического максимального правдоподобия (ML) распределение, которое подсчитывает, сколько раз узел находился в состоянии . Поскольку первый член не зависит от топологии
Логарифмическая правдоподобие максимизируется путем вычисления связующего дерева максимального веса, где веса ребер являются попарно взаимными информационными членами . Максимальный вес связующего дерева можно найти с помощью алгоритма Прима и алгоритм Крускала .I(xs;xt|θst)
источник