Исключение переменных - Variable elimination - Wikipedia

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

Факторы

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

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

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

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

Пример

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

${\displaystyle V_{1}}$	${\displaystyle V_{2}}$	${\displaystyle V_{3}}$	${\displaystyle V_{4}}$	${\displaystyle V_{5}}$	${\displaystyle Pr(.)}$
истинный	истинный	истинный	ложный	ложный	0.80
ложный	истинный	истинный	ложный	ложный	0.20

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

${\displaystyle V_{2}}$	${\displaystyle V_{3}}$	${\displaystyle V_{4}}$	${\displaystyle V_{5}}$	${\displaystyle Pr(.)}$
истинный	истинный	ложный	ложный	1.0

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

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

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

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

${\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}$

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

Вывод

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

Взято из,^[1] этот алгоритм вычисляет ${\displaystyle p(X|E=e)}$ из дискретной байесовской сети B. VE вызывает SO для удаления переменных по одной. В частности, в алгоритме 2 ${\displaystyle \phi }$ множество C таблиц условной вероятности (далее "CPT") для B, ${\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. Чжан Н.Л., Пул Д.: Простой подход к вычислениям байесовских сетей // 7-я Канадская конференция по искусственному интеллекту, стр. 171-178. Спрингер, Нью-Йорк (1994)
2. Дарвиче, Аднан (01.01.2009). Моделирование и рассуждение с помощью байесовских сетей. Дои:10.1017 / cbo9780511811357. ISBN  9780511811357.
3. Коллер, Д., Фридман, Н .: Вероятностные графические модели: принципы и методы. MIT Press, Кембридж, Массачусетс (2009)