Элиминация переменной

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

Исключение переменных (VE) — это простой и общий точный алгоритм вывода в вероятностных графических моделях , таких как байесовские сети и марковские случайные поля . ^[1] Его можно использовать для вывода максимального апостериорного (MAP) состояния или оценки условных или предельных распределений по подмножеству переменных. Алгоритм имеет экспоненциальную временную сложность, но может быть эффективным на практике для графов с низкой шириной дерева , если используется правильный порядок исключения.

Факторы

Обеспечивая ключевое снижение алгоритмической сложности, фактор , также известный как потенциал, переменных, представляет собой отношение между каждым экземпляром переменных к неотрицательному числу, обычно обозначаемому как . ^[2] Фактор не обязательно имеет заданную интерпретацию. Можно выполнять операции над факторами различных представлений, такими как распределение вероятностей или условное распределение. ^[2] Совместные распределения часто становятся слишком большими для обработки, поскольку сложность этой операции экспоненциальна. Таким образом, исключение переменных становится более осуществимым при вычислении факторизованных сущностей. ${\displaystyle f}$ ${\displaystyle V}$ ${\displaystyle v}$ ${\displaystyle f}$ ${\displaystyle f(x)}$

Основные операции

Суммирование переменных

Алгоритм 1, называемый суммированием (SO) или маргинализацией, исключает одну переменную из набора факторов, ^[3] и возвращает результирующий набор факторов. Алгоритм collect-relevant просто возвращает эти факторы в включающей переменной . ${\displaystyle v}$ ${\displaystyle \phi }$ ${\displaystyle \phi }$ ${\displaystyle v}$

Алгоритм 1 сумма-выход( , ) ${\displaystyle v}$ ${\displaystyle \phi }$

${\displaystyle \Phi }$= собрать факторы, имеющие отношение к ${\displaystyle v}$

${\displaystyle \Psi }$= произведение всех факторов в ${\displaystyle \Phi }$

${\displaystyle \tau =\sum _{v}\Psi }$

возвращаться ${\displaystyle (\phi -\Phi )\cup \{\tau \}}$

Пример

Здесь мы имеем совместное распределение вероятностей . Переменная может быть просуммирована между набором конкретизаций, где набор в минимуме должен согласовываться с остальными переменными. Значение не имеет значения, когда это переменная, которая должна быть просуммирована. ^[2] ${\displaystyle v}$ ${\displaystyle V-v}$ ${\displaystyle v}$

После исключения его ссылка исключается, и у нас остается распределение только по оставшимся переменным и сумме каждого экземпляра. ${\displaystyle V_{1}}$

Полученное распределение, которое следует за операцией суммирования, помогает отвечать только на запросы, в которых не упоминается . ^[2] Также стоит отметить, что операция суммирования является коммутативной. ${\displaystyle V_{1}}$

Фактор умножения

Вычисление произведения между несколькими факторами приводит к фактору, совместимому с одной конкретизацией в каждом факторе. ^[2]

Алгоритм 2 многофакторный( , ) ^[2] ${\displaystyle v}$ ${\displaystyle \phi }$

${\displaystyle Z}$= Объединение всех переменных между произведениями факторов ${\displaystyle f_{1}(X_{1}),...,f_{m}(X_{m})}$

${\displaystyle f}$= фактор, по которому для всех ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle f}$

Для каждого экземпляра ${\displaystyle z}$

Для 1 к ${\displaystyle m}$

${\displaystyle x_{1}=}$инстанцирование переменных, соответствующих ${\displaystyle X_{1}}$ ${\displaystyle z}$

${\displaystyle f(z)=f(z)f_{i}(x_{i})}$

возвращаться ${\displaystyle f}$

Умножение множителей не только коммутативно, но и ассоциативно.

Вывод

Наиболее распространенный тип запроса имеет вид , где и являются непересекающимися подмножествами , и наблюдается принятие значения . Базовый алгоритм вычисления p(X|E = e) называется исключением переменной (VE), впервые предложенный в. ^[1] ${\displaystyle p(X|E=e)}$ ${\displaystyle X}$ ${\displaystyle E}$ ${\displaystyle U}$ ${\displaystyle E}$ ${\displaystyle e}$

Взятый из ^[1], этот алгоритм вычисляет из дискретной байесовской сети B. VE вызывает SO для исключения переменных по одной. Более конкретно, в алгоритме 2, — это набор C таблиц условной вероятности (далее «CPT») для B, — это список переменных запроса, — это список наблюдаемых переменных, — это соответствующий список наблюдаемых значений и — это порядок исключения для переменных , где обозначает . ${\displaystyle p(X|E=e)}$ ${\displaystyle \phi }$ ${\displaystyle X}$ ${\displaystyle E}$ ${\displaystyle e}$ ${\displaystyle \sigma }$ ${\displaystyle U-XE}$ ${\displaystyle XE}$ ${\displaystyle X\cup E}$

Алгоритм исключения переменных VE( ) ${\displaystyle \phi ,X,E,e,\sigma }$

Умножить факторы на соответствующие CPT, пока σ не пусто

Удалить первую переменную из ${\displaystyle v}$ ${\displaystyle \sigma }$

${\displaystyle \phi }$= сумма-выход ${\displaystyle (v,\phi )}$

${\displaystyle p(X,E=e)}$= произведение всех факторов ${\displaystyle \Psi \in \phi }$

возвращаться ${\displaystyle p(X,E=e)/\sum _{X}p(X,E=e)}$

Заказ

Поиск оптимального порядка, в котором следует исключать переменные, является NP-трудной задачей. Таким образом, существуют эвристики, которым можно следовать, чтобы лучше оптимизировать производительность по порядку:

1. Минимальная степень : Исключить переменную, что приведет к построению наименьшего возможного фактора. ^[2]
2. Минимальное заполнение: путем построения неориентированного графа, показывающего переменные связи, выраженные всеми CPT, исключите переменную, которая приведет к наименьшему количеству ребер, которые будут добавлены после исключения. ^[2]

Ссылки

1. Zhang, NL, Poole, D.: Простой подход к вычислениям байесовских сетей. В: 7-я Канадская конференция по искусственному интеллекту, стр. 171--178. Springer, Нью-Йорк (1994)
2. Дарвич, Аднан (2009-01-01). Моделирование и рассуждения с использованием байесовских сетей . doi :10.1017/cbo9780511811357. ISBN 9780511811357.
3. Коллер, Д., Фридман, Н.: Вероятностные графические модели: принципы и методы. MIT Press, Кембридж, Массачусетс (2009)