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

Длинная статья про алгоритм распространения доверия - belief propagation. Этот алгоритм используется для быстрого решения таких задач, как вероятностные выводы, декодирование сигналов, сэмплирование конфигураций спиновых стекол и т.д. Декодирование турбо-кодов, используемых в сетях 3G и 4G, разгадывание кроссвордов и судоку тоже можно рассматривать как разновидности алгоритма распространения доверия.

Например, при вероятностном выводе у нас имеется граф событий (как на картинке слева - состояния и симптомы пациента, который то ли здоров, то ли простужен - это нам нужно выяснить), соединенных друг с другом причинно-следственными связями. Эти связи задаются количественно условными вероятностями P(x_i | x_j), а вероятности некоторых событий P(x_i) уже известны из эксперимента. Задача состоит в том, чтобы вычислить маргинальные вероятности других событий по цепочкам причинно-следственных связей.

Перечисленные выше задачи могут быть сведены к задаче о неориентированной марковской сети. В этой задаче совместная вероятность всех событий p({x_i}) получается перемножением одноузельных ?_i(x_i) и парных ?_ij(x_i, x_j) факторов.

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

Для расчета вероятностей событий нужно провести маргинализацию совместного распределения, то есть P(x_k) - это сумма p({x_i}) по всем переменным кроме x_k. При большом числе узлов проведение такого расчета "в лоб" требует экспоненциально большого времени, и алгоритм распространения доверия позволяет решить ее значительно быстрее.

В алгоритме распространения доверия считается, что узлы обмениваются между собой "сообщениями" m_ij(x_j), как показано на рисунке справа внизу. Величина m_ij(x_j) определяет "веру" узла i в то, что узел j находится в состоянии x_j. Оценка искомой вероятности P(x_i) получается перемножением одноузельного фактора ?_i(x_i) и сообщений, приходящих в наш узел от всех соседних узлов.

Доверие распространяется по сети последовательно, от каждого узла к соседним, поэтому расчет величин m_ij(x_j) - очень быстрый процесс, если граф не имеет замкнутых петель. А при наличии петель возникают проблемы: можно повторять вычисления, обходя петли много раз и надеясь на сходимость, которая не обязательно достигается. В этих случаях используются разные приближения и обобщения метода.

https://www.semanticscholar.org/paper/Understanding-belief-propagation-and-its-Yedidia-Freeman/05a281df21f4cb2b01e7751c50a4cba3ae0b992f

Источник: www.semanticscholar.org

Комментарии: