Удаление переменных

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

Факторы

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

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

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

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

Алгоритм 1 суммирование( $v$ , $\phi$ )

\Phi

= собрать факторы, имеющие отношение к

v

\Psi

= произведение всех факторов в

\Phi

\tau =\sum _{v}\Psi

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

Пример

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

$V_{1}$	$V_{2}$	$V_{3}$	$V_{4}$	$V_{5}$	$Pr(.)$
истинный	истинный	истинный	ЛОЖЬ	ЛОЖЬ	0.80
ЛОЖЬ	истинный	истинный	ЛОЖЬ	ЛОЖЬ	0.20

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

$V_{2}$	$V_{3}$	$V_{4}$	$V_{5}$	$Pr(.)$
истинный	истинный	ЛОЖЬ	ЛОЖЬ	1.0

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

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

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

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

Z

= Объединение всех переменных между произведением факторов

f_{1}(X_{1}),...,f_{m}(X_{m})

f

= фактор больше

f

где

f

для всех

f

Для каждого экземпляра

z

От 1 до

m

x_{1}=

создание экземпляров переменных

X_{1}

в соответствии с

z

f(z)=f(z)f_{i}(x_{i})

возвращаться

f

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

Вывод

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

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

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

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

Удалить первую переменную

v

от

\sigma

\phi

= итог

(v,\phi )

p(X,E=e)

= произведение всех факторов

\Psi \in \phi

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

Заказ

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

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

Ссылки

^ Jump up to: ^а ^б ^с Чжан, Н.Л., Пул, Д.: Простой подход к вычислениям в байесовской сети. В: 7-я Канадская конференция по искусственному интеллекту, стр. 171–178. Спрингер, Нью-Йорк (1994)
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час Дарвич, Аднан (1 января 2009 г.). Моделирование и рассуждения с помощью байесовских сетей . дои : 10.1017/cbo9780511811357 . ISBN 9780511811357 .
^ Коллер Д., Фридман Н.: Вероятностные графические модели: принципы и методы. MIT Press, Кембридж, Массачусетс (2009)

[zhang-1] Jump up to: ^а ^б ^с Чжан, Н.Л., Пул, Д.: Простой подход к вычислениям в байесовской сети. В: 7-я Канадская конференция по искусственному интеллекту, стр. 171–178. Спрингер, Нью-Йорк (1994)

[:0-2] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час Дарвич, Аднан (1 января 2009 г.). Моделирование и рассуждения с помощью байесовских сетей . дои : 10.1017/cbo9780511811357 . ISBN 9780511811357 .

[3] Коллер Д., Фридман Н.: Вероятностные графические модели: принципы и методы. MIT Press, Кембридж, Массачусетс (2009)

[1]

[2]

[3]