Графовая вероятностная модель

Графовая вероятностная модель — это вероятностная модель, в которой в виде графа представлены зависимости между случайными величинами. Вершины графа соответствуют случайным переменным, а рёбра — непосредственным вероятностным взаимосвязям между случайными величинами. Графические модели широко используются в теории вероятностей, статистике (особенно в Байесовской статистике), а также в машинном обучении.

Виды графовых моделей

Байесовская сеть

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

По байесовской сети легко записывается совместное распределение переменных: если события (случайные величины) обозначаются как

$X_{1},\ldots ,X_{n}$

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

$P[X_{1},\ldots ,X_{n}]=\prod _{i=1}^{n}P[X_{i}|pa_{i}]$

где $pa_{i}$ множество вершин-предков вершины $X_{i}$ . Другими словами, совместное распределение представляется в виде произведения условных атомарных распределений, которые обычно известны. Любые две вершины, не соединённые ребром, условно независимы, если известно значение их предков. В общем, любые два набора вершин условно независимы при заданных значениях третьего множества вершин, если в графе выполняется условие d-разделимости. Локальная и глобальная независимость эквивалентны в Байесовской сети

Важный частный случай байесовской сети - скрытая марковская модель

Марковские случайные поля

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

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

Другие виды графовых моделей

фактор-граф — неориентированный двудольный граф, в котором рёбрами соединены факторы и случайные переменные. Каждый фактор представляет вероятностное распределения для всех переменных, которые он связывает. Графы переводят в форму фактор-графа, например, для возможности использования алгоритма распространения доверия.
цепной граф — это граф, который может содержать как направленные, так и ненаправленные рёбра, но без ориентированных циклов (то есть если мы начнём движение в какой-то вершине и будем двигаться по графу только по ориентированным рёбрам, то мы не сможем вернуться в ту вершину, из которой мы начали путь). И ориентированные и неориентированные графы являются частным случаем цепных графов, которые могут служить обобщением байесовских и марковских сетей
условное случайное поле — дискриминативная модель, заданная на неориентированном графе

Приложения

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

Ссылки

Jensen, Finn. An introduction to Bayesian networks (неопр.). — Berlin: Springer, 1996. — ISBN 0-387-91502-8.
Cowell, Robert G.; Dawid, A. Philip^[англ.]; Lauritzen, Steffen L.; Spiegelhalter, David J.^[англ.]. Probabilistic networks and expert systems (англ.). — Berlin: Springer, 1999. — ISBN 0-387-98767-3. A more advanced and statistically oriented book
Pearl, Judea. Probabilistic Reasoning in Intelligent Systems (англ.). — 2nd revised. — San Mateo, CA: Morgan Kaufmann, 1988. — ISBN 1558604790. A computational reasoning approach, where the relationships between graphs and probabilities were formally introduced.
Bishop, Christopher M.^[англ.]. Chapter 8. Graphical Models // Pattern Recognition and Machine Learning (неопр.). — Springer, 2006. — С. 359—422. — ISBN 0-387-31073-8.
A Brief Introduction to Graphical Models and Bayesian Networks Архивная копия от 12 ноября 2020 на Wayback Machine
Heckerman's Bayes Net Learning Tutorial (недоступная ссылка)
Edoardo M. Airoldi. Getting Started in Probabilistic Graphical Models (англ.) // PLoS Computational Biology : journal. — 2007. — Vol. 3, no. 12. — P. e252. — doi:10.1371/journal.pcbi.0030252.