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

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

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

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

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

$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-разделимости. Локальная и глобальная независимость эквивалентны в Байесовской сети.

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

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

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

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

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

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

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

↑ Обоскалов В. П., Кокин С. Е., Кирпикова И. Л. Применение вероятностно-статистических методов и теории графов в электроэнергетике: учебное пособие. — 2016.
↑ Ирина Юрьевна Деева, Каринэ Артуровна Шахкян, Юрий Константинович Каминский. Моделирование многомерных данных с помощью композитных байесовских сетей // Научно-технический вестник информационных технологий, механики и оптики. — 2024. — № 4.

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
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.

[1] Обоскалов В. П., Кокин С. Е., Кирпикова И. Л. Применение вероятностно-статистических методов и теории графов в электроэнергетике: учебное пособие. — 2016.

[2] Ирина Юрьевна Деева, Каринэ Артуровна Шахкян, Юрий Константинович Каминский. Моделирование многомерных данных с помощью композитных байесовских сетей // Научно-технический вестник информационных технологий, механики и оптики. — 2024. — № 4.

[1]

[2]

Машинное обучение и data mining
Задачи	Задача классификации Обучение без учителя Обучение с частичным привлечением учителя Регрессионный анализ AutoML Ассоциативные правила Выделение признаков Обучение признакам Обучение ранжированию Грамматический вывод Онлайновое обучение
Обучение с учителем	Метод k-ближайших соседей Наивный байесовский классификатор Дерево решений Метод опорных векторов Линейная регрессия Логистическая регрессия Перцептрон Ансамблевое обучение Бэггинг Бустинг Random forest Метод релевантных векторов
Кластерный анализ	Метод k-средних Метод нечёткой кластеризации Иерархическая кластеризация EM-алгоритм BIRCH CURE DBSCAN OPTICS Mean-shift
Снижение размерности	Факторный анализ Метод главных компонент CCA ICA LDA Неотрицательное матричное разложение t-SNE
Структурное прогнозирование	Графовая вероятностная модель Байесовская сеть Скрытая марковская модель CRF
Выявление аномалий	Метод k-ближайших соседей Локальный уровень выброса
Графовые вероятностные модели	Байесовская сеть Марковская сеть Скрытая марковская модель
Нейронные сети	Ограниченная машина Больцмана Самоорганизующаяся карта Функция активации Сигмоида Softmax Радиально-базисная функция Метод обратного распространения ошибки Глубокое обучение Многослойный перцептрон Рекуррентная нейронная сеть Долгая краткосрочная память Управляемый рекуррентный блок Свёрточная нейронная сеть U-Net Автокодировщик
Обучение с подкреплением	Марковский процесс Уравнение Беллмана Жадный алгоритм Q-обучение SARSA Temporal difference (TD)
Теория	Теория Вапника — Червоненкиса Дилемма смещения–дисперсии Теория вычислительного обучения Минимизация эмпирического риска Оккамово обучение PAC learning Статистическая теория обучения
Журналы и конференции	NeurIPS ICML ML JMLR ArXiv:cs.LG
Персоналии	Ричард Саттон Эндрю Барто

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

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

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

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

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

Применение

Примечания

Литература

Дополнительно по теме

Категории