Исключение переменных

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

Факторы [ править ]

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

Основные операции [ править ]

Суммирование переменных [ править ]

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

Сумма алгоритма 1 ( , )${\ displaystyle v}$${\ displaystyle \ phi}$

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

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

${\ Displaystyle \ тау = \ сумма _ {v} \ Psi}$

возвращаться ${\ Displaystyle (\ фи - \ фи) \ чашка \ {\ тау \}}$

Пример

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

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

Результирующее распределение, которое следует за операцией суммирования, помогает только отвечать на запросы, которые не упоминаются . ^[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]

Ссылки [ править ]