27-28Байесовские рассуждения смыслы и машинное обу

Часть V
Приблизительный вывод
489
ГЛАВА 27
Отбор проб\ выборок
27.1 Вступление
Выборка касается получения реализаций x1 , . . . , xL переменной x из распределения p(x). Для дискретной переменной x, в пределе большого числа выборок, доля выборок в состоянии x стремится к p(x = x). То есть,

В непрерывном случае можно рассмотреть небольшую область ;, в которой вероятность того, что выборки занявшие ; будут стремиться к интегралу от p(x) над ;. Другими словами, относительная частота x ; ; стремится к ;x;; p(x). Учитывая конечный набор выборок, можно приблизить математические ожидания, используя

Это приближение справедливо как для дискретных, так и для непрерывных переменных. Если выборки действительно взяты из p(x), то среднее значение приближения равно

Дисперсия аппроксимации равна

Следовательно, среднее значение аппроксимации - это точное среднее значение f и дисперсия масштабов аппроксимации обратно пропорциональна количеству выборок. Таким образом, в принципе, при условии, что выборки получены независимо от p(x), для точной оценки этого среднего значения требуется лишь небольшое количество выборок. Важно отметить, что этот результат не зависит от величины\ размерности x. Однако основная трудность заключается в том, чтобы фактически генерировать независимые выборки из p (x). Получение выборок из многомерных распределений, как правило, является сложной задачей, и существует мало гарантий того, что в течение практического периода времени полученные выборки будут достаточно репрезентативны, чтобы можно было точно аппроксимировать ожидания. Существует множество различных алгоритмов выборки, все из которых "работают в принципе", но каждый "работает на практике" только тогда, когда распределение удовлетворяет определенным свойствам[112]. Прежде чем разрабатывать схемы для многовариантных распределений, рассмотрим одномерный случай.
491 Введение

Рисунок 27.1: Представление уравнения дискретного распределения (27.1.5). Единичный интервал от 0 до 1 разбивается на части, длина которых равна 0,6, 0,1 и 0,3.

27.1.1 Одномерная выборка
Далее мы предполагаем, что существует генератор случайных чисел, который способен генерировать значение равномерно случайным образом из единичного интервала [0, 1]. Мы будем использовать этот генератор однородных случайных чисел для получения выборок из неравномерных распределений.
Дискретный случай
Рассмотрим одномерное дискретное распределение p(x), где dom(x) = {1, 2, 3}, при
Это представляет собой разбиение единичного интервала [0, 1], в котором интервал [0, 0.6] был помечен как состояние 1, [0.6, 0.7] - как состояние 2 и [0.7, 1.0] - как состояние 3, рис.27.1. Если бы мы бросили точку ; в любом месте случайным образом, равномерно в интервале [0, 1], вероятность того, что ; попадет в интервал 1, равна 0,6, а вероятность того, что она окажется в интервале 2, равна 0,1, и аналогично, для интервала 3, равна 0,3. Таким образом, это определяет для нас правильную процедуру выборки для дискретных одномерных распределений, как описано в алгоритме(24).

В нашем примере мы имеем (c0 , c1 , c2 , c3 ) = (0, 0.6, 0.7, 1). Затем мы равномерно рисуем выборку из [0, 1], скажем u = 0,66. Тогда выбранным состоянием будет состояние 2, поскольку оно находится в интервале (c1 , c2 ).

Выборка из дискретного одномерного распределения проста, поскольку вычисление кумулянта занимает всего O (K) шагов для дискретной переменной состояния K.

Непрерывный случай

Далее мы предполагаем, что существует метод для генерации выборок из равномерного распределения U (x| [0, 1]). Интуитивно понятно, что обобщение дискретного случая на непрерывный случай является очевидным. Сначала мы вычисляем функцию кумулятивной плотности
Затем мы производим выборку u равномерно из [0, 1] и получаем соответствующую выборку x, решая C (x) = u ; x = C -1 (u). Таким образом, формально выборка непрерывной одномерной переменной проста при условии, что мы можем вычислить интеграл от соответствующей функции плотности вероятности.

Алгоритм 24 Выборка из одномерного дискретного распределения p с K состояниями.
1: Обозначьте K состояний как i = 1, . . . , K с соответствующими вероятностями pi .
2: Вычислите кумулятивную величину ci =
и установите c0 = 0.
3: Равномерно случайным образом выведите значение u из единичного интервала [0, 1].
4: Найдите i, для которого ci;1 < u ; ci .
5: Верните состояние i в качестве выборки из p.
492
ЧЕРНОВИК от 9 марта 2010 г. Введение
Рисунок 27.2: Гистограммы выборок из трех состояний распределения p(x) = {0.6, 0.1, 0.3}.
(а): 20 выборок. (b): 1000 выборок. По мере увеличения числа выборок относительная частота выборок стремится к распределению p(x).

Для специальных распределений, таких как гауссовы, существуют численно эффективные альтернативные процедуры, обычно основанные на преобразованиях координат, см. упражнение(246).
27.1.2 Многовариантная выборка

Один из способов обобщить одномерный дискретный случай на распределение с более высокой размерностью p (x1 , ... , xn ) состоит в том, чтобы преобразовать это в эквивалентное одномерное распределение. Этого можно достичь, перечислив все возможные совместные состояния (x1 , ... , xn), присвоив каждому уникальное целое число i от 1 до общего числа состояний и построив одномерное распределение с вероятностью p(i) = p(x) для i, соответствующее многомерному состоянию x. Затем это преобразует многомерное распределение в эквивалентное одномерное распределение и выборка могут быть выполнены, как и раньше. В целом, конечно, эта процедура непрактична, поскольку количество состояний будет экспоненциально расти с увеличением числа переменных x1 , . . . , xn .
Альтернативным точным подходом было бы использовать соотношение
Мы можем выполнить выборку из совместного распределения p (x1, x2), сначала выбрав состояние для x1 из одномерного p(x1 ), а затем, привязав x1 к этому состоянию, сделав выборку состояния для x2 из одномерного p(x2 |x1 ). Понятно, как обобщить это на большее количество переменных, используя каскадную декомпозицию:

Однако, чтобы применить этот метод, нам нужно знать условные выражения p(xi |xi;1 , . . . , x1 ). Если они не указаны явно, нам нужно вычислить их из совместного распределения p(x1 , . . . , xn ). Такие условия, как правило, требуют суммирования по экспоненциальному числу состояний и, за исключением малого n, которое как правило, также нецелесообразно. Однако для Сетей Убеждений при построении условия задаются таким образом, что этот метод становится практичным, как мы обсуждаем в разделе (27.2).

Таким образом, получение выборок из многовариантного распределения, как правило, является сложной задачей, и каждый стремится использовать любые структурные свойства распределения, чтобы сделать это более выполнимым с точки зрения вычислений. Распространенный подход заключается в преобразовании распределения в произведение распределений с меньшей размерностью. Классический подход примером этого является выборка из многовариантной Гауссовой функции, которая может быть сведена к выборке из набора одномерных Гауссовых функций с помощью подходящего преобразования координат, как описано в примере (112).

Пример 112 (Выборка из многовариантной гауссовой функции). Наш интерес состоит в том, чтобы получить выборку из многовариантного гауссова p (x) = N (x|m, S). Для общей ковариационной матрицы S, p (x) не преобразуется в произведение одномерных распределений. Однако рассмотрим преобразование
где C выбрано таким образом, что CCT = S. Поскольку это линейное преобразование, y также распределено по Гауссу со средним значением
Поскольку среднее значение y равно нулю, ковариация определяется как
ПРОЕКТ от 9 марта 2010 г.  493 Анестральный отбор проб\ выборок

Рисунок 27.3: Система верований предков \ Родительская, наследуемая Сеть Убеждений \ без каких-либо очевидных переменных. Чтобы выполнить выборку из этого распределения, мы берем выборку из переменной 1, а затем из переменных 2,... ,6 по порядку.
Следовательно
Следовательно, выборка из y может быть получена путем независимого составления выборки из каждого из одномерных гауссианов единичной дисперсии с нулевым средним значением. Учитывая выборку для y, выборка для x получается с использованием
Построение выборок из одномерной гауссовой функции - хорошо изученная тема, и популярным методом является Техника \метод \ Бокса-Мюллера, упражнение(246).
27.2 Выборка предков \ родительская, наследуемая\
Сети Убеждений имеют общую форму:
, где известно каждое из условных распределений p(xi |pa (xi )). При условии, что никакие переменные не являются доказательными, мы можем произвести выборку из этого распределения простым способом. Для удобства мы сначала переименуем индексы переменных, чтобы родительские переменные всегда располагались перед их дочерними переменными (например, в порядке наследования) (см. рис. 27.3).
Сначала можно выполнить выборку из тех узлов, у которых нет родительских элементов (здесь x1 и x2 ). Учитывая эти значения, затем можно выполнить выборку из x3 , затем из x4 и x5 и, наконец, из x6 . Несмотря на наличие петель на графе, такая процедура прямой выборки проста. Эта процедура применима как для дискретных, так и для непрерывных переменных.

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

Выборка предков или "прямая" выборка - это пример идеальной выборки (также называемой точной выборкой), поскольку каждая выборка действительно берется из требуемого распределения. Это противоречит разделам методов Монте-Карло с цепью Маркова (27.3,27.4), для которых выборки берутся из p(x) только в пределах большого числа итераций.
27.2.1 Работа с доказательствами
Как мы можем выполнить выборку из распределения, в котором определенные переменные xE привязаны к очевидным состояниям? Формально нам нужно выполнить выборку из

494 ЧЕРНОВИК от 9 марта 2010 г. Выборки Гиббса

Рисунок 27.4: Модель Маркова для x4. Чтобы нарисовать образец из p(x4 |x\4 ) мы фиксируем x1 , x2 , x3 , x5 , x7 в их очевидных состояниях и получаем выборку из p(x4 |x1 , x2 )p(x6 |x3 , x4 )p(x7 |x4 , x5 )/Z, где Z - константа нормализации.

Если у доказательной переменной xi нет родительских элементов, то можно просто перевести переменную в это состояние и отключить- продолжайте осуществлять прямой отбор проб, как и раньше. Например, чтобы вычислить выборку из p(x1 , x3 , x4 , x5 , x6 |x2 ), определенных в уравнении (27.2.2), нужно просто перевести x2 в его фактическое состояние и продолжить прямую выборку. Причина, по которой это просто, заключается в том, что обусловливание по x2 просто определяет новое распределение для подмножества переменных, для которых распределение известно сразу.

С другой стороны, рассмотрим выборку из p (x1 , x2 , x3 , x4 , x5 |x6 ). Используя правило Байеса, мы имеем
Обусловленность по x6 означает, что структура распределения по неявным переменным изменяется – например, x4 и x5 становятся связанными. Можно было бы попытаться разработать эквивалентную новую структуру прямой выборки (см. упражнение(247)), хотя, как правило, это будет так же сложно, как и применение метода точного логического вывода.

Альтернативой является использование прямой выборки из не подтвержденного доказательствами распределения, при этом отбросить от нее любые образцы, которые не соответствуют требованиям к очевидным состояниям. Как правило, это не рекомендуется, поскольку  вероятность того, что выборка из p(x) будет соответствовать доказательствам, примерно равна O (1/ ;i dim xei ), где dim xei - количество состояний доказательной переменной i. В принципе, можно ослабить этот эффект, отказавшись от выборки, как только какое-либо изменчивое состояние будет противоречить доказательствам. Тем не менее, количество повторных запусков, необходимых для получения достоверной выборки, в среднем будет очень большим.

27.2.2 Идеальная выборка для Марковской сети

Для сети Маркова мы можем построить точные выборки, сформировав эквивалентное направленное представление графа, см. раздел (6.8), а затем используя выборку предков на этом ориентированном графе. Это достигается путем выбора сначала корневой группы, а затем последовательного удаления ребер от этой группы.  Затем из сети Маркова можно получить точную выборку, сначала выбрав корневую клику, а затем рекурсивно выбрав дочерние элементы этой клики. Смотрите potsample.m, JTsample.m и demoJTreeSample.m.

27.3 Выборка Гиббса

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

Нет доказательств

Предположим, что у нас есть состояние объединенной выборки x1 из многомерного распределения p(x). Затем мы рассмотрим конкретную переменную xi. Используя правило Байеса, мы можем записать
Учитывая общее начальное состояние x1 , из которого мы можем вывести "родительское" состояние x11 , . . . , x1i;1 , x1i+1 , . . . , x1n , мы можем затем получить выборку x2i из

ЧЕРНОВИК от 9 марта 2010 года  Выборка Гигса 495

Рисунок 27.5: (а): Игрушечное "неразрешимое" распределение. Выборка Гиббса с учетом всех переменных, кроме одной, приводит к простому одномерному условному распределению. (b): Обработка по x3 приводит к новому распределению, которое является односвязным, для которого точная выборка является простой.

Мы предполагаем, что из этого распределения легко сделать выборку, поскольку оно является одномерным. Мы называем эту новую объединенную выборку (в который обновил только xi) x2 = (x11 , . . . , x1i;1 , x2i , x1i+1 , . . . , x1n ). Затем пользователь выбирает другую переменную xj для выборки и, продолжая эту процедуру, генерирует набор выборок x1 , . . . , xL, в котором каждый xl+1 отличается от xl только одним компонентом. Причина, по которой эта схема выборки является допустимой, описана в разделе (27.3.1).

Для Сети Убеждений условное значение p (xi |x\i ) определяется Марковским набором xi :
см., например, рис.27.4. Это означает, что для формирования выборочного обновления требуются только родительские состояния и состояния родителей дочерних состояний. Константу нормализации для этого одномерного распределения легко вычислить из требования:
В случае непрерывной переменной xi приведенное выше суммирование заменяется интегрированием.
Доказательства
С доказательствами легко работать, объединяя для всех образцов\ выборок\ доказательные переменные в их доказательную базу\ доказательные состояния. Также нет необходимости производить выборку для этих переменных, поскольку их состояния известны.
27.3.1 Выборка Гиббса в виде цепи Маркова
В выборке Гиббса мы получаем выборку объединенных переменных xl на этапе l. На основе этого мы создаем новую совместную выборку xl+1 . Это означает, что мы можем записать выборку Гиббса как процедуру, которая использует
для некоторого распределения q(xl+1 |xl ). Если мы выберем переменную xi для обновления случайным образом из распределения q(i), то выборка Гиббса соответствует построению выборок с использованием Марковского перехода
при q(i) > 0. Наш интерес состоит в том, чтобы показать, что стационарное распределение q(x0 |x) равно p(x). Мы делаем это, предполагая, что x непрерывно – дискретный случай аналогичен:
Проект от 9 марта 2010 г.  Выборки по Гиббсу

Рисунок 27.6: Двумерное распределение, для которого выборка Гиббса не удалась. Распределение имеет массу только в заштрихованных квадрантах. Выборка Гиббса исходит из l-го состояния выборки (xl1 , xl2 ), а затем производит выборку из p(x2 |xl1 ), которое мы записываем (xl+1 = xl+12) , где x1 l +1, x1 l . Затем переходим к выборке из p (x1 | x2 = x2l+1 ) и т.д. Если мы начнем с нижнего левого квадранта и продолжим таким образом, верхняя правая область никогда не будет исследована.

Следовательно, до тех пор, пока мы продолжаем получать выборки в соответствии с распределением q(x` |x), в пределе большого количества выборок мы в конечном итоге будем стремиться получать выборки из p(x). Достаточно любого распределения q(i) > 0 таким образом, использование всех переменных с одинаковой частотой также является правильным выбором. Технически, мы также требуем, чтобы q(x` | x) имело p(x) в качестве равновесного распределения, так что независимо от того, с какого состояния мы начинаем, мы всегда сходимся к p(x); обсуждение этого вопроса приведено на рис. 27.6.

27.3.2 Структурированная выборка Гиббса

Можно расширить выборку Гиббса, используя кондиционирование, чтобы выявить приемлемое распределение по оставшимся переменным. Например, рассмотрим простое распределение, рис.27.5а
При выборке Гиббса на одном участке мы бы использовали три из четырех переменных и проводили выборку по оставшейся переменной. Например

Однако мы можем использовать более ограниченное кондиционирование при условии, что из кондиционированного продукта легко отбирать пробы. В случае уравнения (27.3.11) мы можем задать условие только для x3, чтобы получить

Это можно записать в виде модифицированного распределения, рис.27.5, б
Как и распределение по x1, x2, x4, это односвязная линейная цепочка, из которой можно получить точные выборки. Простой подход заключается в вычислении константы нормализации любым из стандартных методов, например, с использованием метода факторных графов. Затем можно преобразовать эту неориентированную линейную цепочку в ориентированный граф и использовать выборку предков. Эти операции линейны по количеству переменных в условном распределении. В качестве альтернативы можно сформировать дерево соединений из набора потенциалов, выбрать корень и затем сформировать заданную цепочку путем повторного использования на дереве соединений. Затем можно выполнить выборку предков на результирующем дереве ориентированных клик. Именно такой подход используется в GibbsSample.m.

В приведенном выше примере также можно выявить приемлемое распределение, обусловливающее x1 ,
, а затем нарисуйте выборку x2 , x3 , x4 из этого распределения. В этом случае допустимой процедурой отбора проб является получение выборки x1, x2, x4 из уравнения (27.3.13), а затем выборки x3 , x2, x4 из уравнения (27.3.15). Эти затем повторяются два шага. Обратите внимание, что значения x2 и x4 не обязательно должны быть равны их значениям в предыдущей выборке. Эта процедура, как правило, предпочтительнее, чем обновление Гиббса на одном сайте, поскольку выборки менее коррелируют от одной выборки к другой.

Смотрите demoGibbsSample.m для сравнения неструктурированной и структурированной выборки из набора потенциалов.
ЧЕРНОВИК от 9 марта 2010 г. Выборка Гигса 497

Рисунок 27.7: Двести выборок Гиббса для двумерной гауссовой системы. На каждом этапе обновляется только один компонент. (а): Для гауссовой системы с низкой корреляцией выборка Гиббса может эффективно перемещаться по вероятностным областям. (b): Для сильно коррелированной гауссовой выборки выборка Гиббса менее эффективна и не позволяет быстро исследовать вероятные регионы, см. demoGibbsGauss.m.

27.3.3 Замечания

Если исходная выборка x1 находится в той части пространства состояний, которая очень маловероятна, то для ее получения может потребоваться некоторое время. выборки должны стать репрезентативными, поскольку на каждой итерации обновляется только один компонент x. Это приводит к так называемому этапу повторной обработки\ сжечь внутри, на котором исходные выборки отбрасываются.

При выборке Гиббса на одном сайте будет наблюдаться высокая степень корреляции в любых двух последовательных выборках, поскольку на каждом этапе обновляется только одна переменная (в версии обновления на одном сайте). Идеальная схема "идеальной" выборки извлекала бы каждый x "случайным образом" из p(x) – очевидно, что в целом таких идеальных выборок было бы две не будут обладать такой же степенью корреляции, как в выборке Гиббса. Это мотивирует подвыборку , в которой, скажем, берется каждая десятая выборка xK , xK+10 , xK+20 , ..., а остальные отбрасываются.

Благодаря своей простоте выборка Гиббса является одним из самых популярных методов выборки и особенно удобна при применении к Сетям Убеждений благодаря свойству марковского бланкета1. Выборка Гиббса является частным случаем системы MCMC, и, как и во всех методах MCMC, следует иметь в виду, что сходимость может быть серьезной проблемой, то есть ответить на такие вопросы, как "сколько выборок необходимо, чтобы быть достаточно уверенным в точности моей выборочной оценки p(x5 )?", сложно. Несмотря на математические результаты для частных случаев, для контроля эффективности выборки требуются общие эмпирические правила и осведомленность пользователя.

Выборка Гиббса предполагает, что мы можем эффективно перемещаться по всему пространству, обновляя только одну координату. Мы также требуем, чтобы каждое состояние можно было посещать бесконечно часто. На рис. 27.6 показан случай, когда который в двумерном непрерывном распределении имеет массу только в нижней левой и верхней правой областях. В этом случае, если мы начнем с нижней левой области, мы всегда будем оставаться там и никогда не исследуем верхнюю правую область. Эта проблема возникает, когда две области не соединены "вероятным" путем Гиббса.

Выборка Гиббса становится идеальным методом выборки, когда распределение разложено на множители \ коэффициенты\, то есть переменные независимы. Это говорит о том, что в целом выборка Гиббса будет менее эффективной, когда переменные сильно зависят друг от друга\ коррелированны. Например, если мы рассмотрим выборку Гиббса из сильно коррелированного гауссовского распределения с двумя переменными, то обновления будут перемещаться в пространстве очень медленно, рис.27.7.
1Пакет BUGS www.mrc-bsu.cam.ac.uk/bugs - это программное обеспечение общего назначения для отбора проб из Сетей Убеждений.
498 ДРАФТ от 9 марта 2010 года  Цепочка Маркова методом Монте-Карло  (MCMC)
27.4 Цепочка Маркова методом Монте-Карло (MCMC)
Предположим, что у нас есть многомерное распределение в виде
где Z - константа нормализации распределения, а p; (x) — ненормированное распределение. У нас есть предположим, что мы можем вычислить p; (x = x) для любого состояния x, но не для Z, поскольку Z = ;x p; (x) является неразрешимым многомерным суммированием / интегрированием.

Идея выборки MCMC заключается в том, чтобы производить выборку не непосредственно из p(x), а из другого распределения таким образом, чтобы в пределе большого количества выборок фактически выборки были из p(x). Чтобы достичь этого, мы пересылаем выборку из марковского перехода, стационарное распределение которого равно p(x).

27.4.1 Цепи Маркова

Рассмотрим условное распределение q(xl+1 |xl ). Если нам дана начальная выборка x1 , то мы можем повторно сгенерировать выборки x1 , x2 , ... , xL . По прошествии длительного времени L » 1 (и при условии, что цепь Маркова "неприводима \несократима", что означает, что мы можем в конечном итоге перейти из любого состояния в любое другое) выборки получены из стационарного распределения q; (x), которое определяется как (для непрерывной переменной)
Условие для дискретной переменной аналогично при замене интегрирования суммированием. Идея в MCMC задача состоит в том, чтобы для заданного распределения p (x) найти переход q (x`|x), который имеет p(x) в качестве стационарного распределения. Если мы сможем это сделать, то мы сможем извлечь выборки из цепи Маркова путем прямой выборки и принять их за выборки из p (x).

Обратите внимание, что для каждого распределения p(x) будет более одного перехода q(x` |x) с p(x) в качестве стационарного распределения. Вот почему существует очень много различных методов отбора проб MCMC, каждый из которых обладает различными характеристиками и по-разному подходит для конкретного распределения.

Подробный баланс

Как нам построить переход q(x` |x) с заданным p(x) в качестве стационарного распределения? Эта задача может   быть упрощена, если мы рассмотрим специальные переходы, которые удовлетворяют условию детального равновесия. Если нам дано предельное распределение p(x), то подробное условие равновесия для перехода q равно
При этом мы видим
, так что p(x) является стационарным распределением q(x` |x). Требование детального баланса может привести к процесс построения подходящего перехода упрощается, поскольку в уравнении (27.4.3) требуется только относительное значение p(x`) к p(x), а не абсолютное значение p(x) или p(x`).
27.4.2 Выборка из Метрополиса-Гастингса
Рассмотрим следующий переход

ПРОЕКТ от 9 марта 2010 г. 499 Цепочка Маркова методом Монте-Карло (MCMC)

Алгоритм 25 Выборка MCMC из Метрополиса-Гастингса.
1: Выберите начальную точку x1 .
2: для i = 2 до L выполните
3:Нарисуйте пример\выборку\;кандидат xcand из предложения q(x0 |xl-1 ).
Пусть a = q(x
если a ; 1, то xl = xc и
6: иначе
7: равномерно выведите случайное значение u из единичного интервала [0, 1].
8:если u < a, то xl = xc и
9: иначе
11: конец, если
12: конец, если
13: конец для

, где ~q(x` |x) - так называемое распределение предложения, а 0 < f (x` , x) ; 1 - положительная функция. Это определяет допустимое распределение q(x` |x), поскольку оно неотрицательно и
Наш интерес состоит в том, чтобы установить f (x, x`) таким образом, чтобы стационарное распределение q(x`|x) было равно p(x) для любого предложения ~q (x` |x). То есть

Для того, чтобы это было верно, нам требуется (изменить интегральную переменную с x`` на x)

Теперь рассмотрим приемочную функцию Метрополиса-Гастингса
которая определена для всех x, x` и обладает свойством детального баланса
Следовательно, функция f (x` , x), определенная выше, гарантирует выполнение уравнения (27.4.9) и то, что q (x` |x) имеет p(x) в качестве стационарного распределения.

Как мы проводим выборку из q (x` |x)? Уравнение (27.4.5) можно интерпретировать как смесь двух распределений, одно из которых пропорционально ~q(x` |x)f (x` , x), а другое ;(x`, x) с коэффициентом смешивания 1 ; ;x`` ~q(x`` |x)f (x`` , x). Чтобы сделать выборку из этого, мы сделаем выборку из ~q (x` |x) и примем это с вероятностью f (x` , x). Поскольку отбор из ~q(x` |x) и принятие выполняются независимо, вероятность принятия выбранного кандидата является произведением этих вероятностей, а именно ~q(x` |x)f (x` , x). В противном случае кандидат отклоняется, и мы берем выборку x` = x. Используя свойства функции принятия, уравнение (27.4.10), следующее эквивалентно принятию решения о принятии/отклонении кандидата. Если

500 ПРОЕКТ от 9 марта 2010 г. Методы с вспомогательными переменными

Рисунок 27.8: Выборки Метрополиса- Гастингса из двухвариантного распределения p(x1, x2) с использованием предложения q(x` |x) = N (x` x, I). Мы также строим изовероятностные контуры p. Хотя p (x) является мультимодальным, размерность достаточно мала, а режимы достаточно близки, так что простое Гауссово распределение предложений способно объединить два режима. В более высоких измерениях такая мультимодальность более проблематична.  Смотрите demoMetropolis.m

мы принимаем выборку из ~q(x` |x). В противном случае мы принимаем выборку x` из q(x` |x) с вероятностью ~q(x|x` )p; (x`)/~q(x` |x)p; (x). Если мы отклоняем кандидата, мы берем x` = x.

Обратите внимание, что если кандидат x` отклонен, мы берем исходный x в качестве нового образца. Следовательно, на каждой итерации алгоритм создает выборку – либо копию текущей выборки, либо выборку-кандидата.  Общее правило состоит в том, чтобы выбрать распределение предложений, для которого уровень приемлемости составляет от 50% до 85%[105].

Гауссово распределение предложений

Обычное распределение предложений для многомерного x (записываемое явно в виде вектора)
для которого ~q(x` |x) = ~q(x|x` ) и критерием приемлемости становится
Если ненормализованная вероятность состояния-кандидата выше, чем текущее состояние, мы, следовательно, принимаем этого кандидата. В противном случае, если ненормализованная вероятность состояния-кандидата ниже текущего состояния, мы принимаем кандидата только с вероятностью p; (x`)/p; (x). Если кандидат отклоняется, берется новый образец, который является копией предыдущего образца x. Демонстрацию смотрите на рис. 27.8.

При больших размерностях маловероятно, что случайный кандидат, отобранный из гауссовой выборки, даст вероятность получения более высокой, чем текущее значение, упражнение(249). Из-за этого, вероятно, будут приняты только очень небольшие скачки (;2 мало). Это ограничивает скорость, с которой мы исследуем пространство x.

Приведенная выше приемочная функция показывает, что выборка отличается от поиска оптимума. Если вероятность x` выше, чем x, мы принимаем x`. Однако мы также принимаем (с определенной вероятностью принятия) кандидатов, вероятность которых также ниже, чем у текущей выборки.

27.5 Методы с вспомогательными переменными

Практическая задача методов MCMC заключается в обеспечении эффективного перемещения по значимым вероятностным областям распределения. Для таких методов, как Метрополис-Гастинг с локальным распределением предложений (локальным в том смысле, что они вряд ли предложат кандидата, находящегося далеко от текущей выборки), если целевое распределение содержит изолированные острова с высокой плотностью, то вероятность того, что мы сможем переместиться с одного острова на другой, равна очень маленький. Если мы попытаемся сделать предложение менее локальным, используя один при высокой дисперсии вероятность случайного приземления на острове с высокой плотностью населения невелика. Методы с вспомогательными переменными используют дополнительные измерения для исследования и, в некоторых случаях, для обеспечения связи между
ПРОЕКТ от 9 марта 2010 г. 501 Вспомогательных переменных методы

Рисунок 27.9: Гибридный метод Монте-Карло. (а): Мультимодальное распределение p(x), для которого нам нужны выборки. (b): HMC формирует совместное распределение p(x) p(y), где p (y) - гауссово. (c): Начиная с точки x, мы сначала проводим y от гауссовой точки p (y), обозначая точку (x, y) зеленой линией. Затем мы используем гамильтонову динамику (белая линия), чтобы пересечь распределение с примерно постоянной энергией за фиксированное количество шагов, что дает x` , y` . Мы принимаем эту точку, если H(x` , y` ) > H(x, y` ), и создаем новую выборку x` (красная линия). В противном случае этот кандидат принимается с вероятностью exp(H(x` , y` ) ; H(x, y` )). В случае отклонения новый образец x` берется как копия x.

изолированными островками с высокой плотностью.

Рассмотрим построение выборок из p (x), где x - многомерный вектор. Для вспомогательной переменной y мы вводим распределение p(y|x), чтобы сформировать совместное распределение
p(x, y) = p(y|x)p(x) (27.5.1)
Если мы возьмем выборки (xl , yl) из этого совместного распределения, то получим допустимый набор выборок из p (x), взяв только xl. Если мы произвели выборку x непосредственно из p(x), а затем y из p(y|x), то вводить y бессмысленно, поскольку это никак не повлияет на процедуру выборки x. Поэтому, чтобы это было полезно, вспомогательный переменная должна влиять на то, как мы проводим выборку x. Ниже мы обсудим некоторые из распространенных схем использования вспомогательных переменных.

27.5.1 Гибрид Монте-Карло

Гибридный MC - это метод для непрерывных переменных, целью которого является создание нелокальных скачков в выборках и, таким образом, потенциальный переход от одного режима к другому. Мы определяем распределение, из которого мы хотим выполнить выборку, как
для некоторого заданного "гамильтониана" Hx (x) (это всего лишь потенциал). Затем мы определяем другое, "простое" распределение, из которого мы можем легко генерировать выборки,
таким образом, совместное распределение определяется как
В стандартной форме алгоритма для вспомогательного распределения выбирается многомерный Гауссиан с dim y = dim x, так что
Алгоритм HMC сначала извлекает данные из p (y), а затем из p (x, y). Для гауссовой функции p (y) выборка из нее проста. На следующем, "динамическом" шаге, выборка берется из p(x, y) с использованием Метрополис
502 ЧЕРНОВИК от 9 марта 2010 г. Вспомогательные переменные методы
MCMC выборок. Идея состоит в том, чтобы перейти из одной точки пространства x, y в новую точку x` , y`, которая находится на нетривиальном расстоянии от x, y и которая будет принята с высокой вероятностью. Кандидат (x` , y`) будет иметь хорошие шансы быть принятым, если H(x` , y`) будет близко к H(x, y) – этого можно достичь, следуя контуру равной "энергии" H, как описано в следующем разделе.

Динамика гамильтониана

Мы хотим внести изменения в x` = x + ;x, y` = y + ;y для малых ;x и ;y, чтобы гамильтониан H(x, y) ; Hx (x) + Hy (y) сохранился,
Мы можем удовлетворить это (вплоть до первого порядка), рассмотрев разложение Тейлора
Следовательно, для сохранения с точностью до первого порядка требуется
Это единственное скалярное требование, и поэтому существует множество различных решений для ;x и ;y, удовлетворяющих этому единственному условию. Обычно используется гамильтонова динамика, которая соответствует настройке:
где ; - это небольшое значение, гарантирующее точность разложения по Тейлору. Следовательно
Для метода HMC H(x, y) = Hx (x) + Hy (y), так что ;x H(x, y) = ;x Hx (x) и ;y H(x, y) =
;y Hy (y) Для гауссова случая ;y Hy (y) = ;y, так что
Существуют конкретные способы реализации гамильтоновой динамики, называемые Cкачкообразной дискретизацией, которые являются более точными, чем простая временная дискретизация, использованная выше, и мы отсылаем читателя к [205] для получения подробной информации.

Чтобы обеспечить симметричное распределение предложений, в начале динамического шага мы выбираем равномерно ; = +;0 или ; = ;;0. Это означает, что существует такая же вероятность того, что мы вернемся к точке x, y, начиная с x` , y` , и наоборот. Затем мы следуем Гамильтоновой динамике в течение многих временных шагов (обычно порядка нескольких сотен), чтобы достичь подходящей точки x` , y` . Если динамика Гамильтониана численно точна, то H(x` , y` ) будет иметь примерно то же значение, что и H(x, y). Затем мы выполняем шаг Метрополиса и принимаем точку x` , y`, если H(x` , y` ) > H(x, y) и в противном случае принимаем ее с вероятностью exp(H(x` , y` ) ; H(x, y)). Если отклонено, мы берем начальную точку x, y в качестве выборки. В сочетании с шагом выборки p(y) мы получаем общую процедуру, описанную в алгоритме(26).

В HMC мы используем не только потенциальную величину Hx (x) для определения выборок-кандидатов, но и градиент Hx (x) . Интуитивное объяснение успеха алгоритма заключается в том, что он не столько близорук, сколько прямолинеен Метрополис, поскольку градиент позволяет алгоритму нащупывать путь в другие регионы с высокой вероятностью очерчивая контуры в расширенном пространстве. Можно также рассматривать вспомогательные переменные как переменные импульса – это как если бы образец теперь обладал импульсом, который может переносить его через x- области с низкой плотностью. При условии, что этот импульс достаточно высок, мы можем избежать локальных областей со значительной вероятностью, см. рис. 27.9.
ПРОЕКТ от 9 марта 2010 г. 503 Методы с вспомогательных переменными

Алгоритм 26 Гибридная выборка методом Монте-Карло
1: Начать с x
2: от i = 1 до L выполните
Нарисуйте новый образец y из p(y).
4: Выберите произвольное направление траектории (вперед или назад).
5: Начиная с x, y, проследите за Гамильтоновой динамикой в течение фиксированного числа шагов, получая возможные значения x0 , y0 .
6: Примите x0 , y0, если H(x0 , y0 ) > H(x, y), в противном случае примите это с вероятностью exp(H(x0 , y0 ) ; H(x, y)).
7: В случае отклонения мы берем образец в виде x, y.
8: конец для

Рисунок 27.10: Обновление по методу Свендсона-Вана для p(x) ; ;i;j exp ;I [xi = xj ]. (а): Текущая выборка состояний (здесь на решетке ближайших соседей). (b): Подобно тому, как цветные соседи связаны друг с другом вероятностью 1;e;; , образуя кластеры переменных. (c): Каждому кластеру присваивается случайный цвет, что формирует новую выборку.

27.5.2 Метод Свендсона-Ванга\ SW

Первоначально метод SW был введен для решения проблем, возникающих при отборе проб из Изинга Модели близко к критической температуре[268]. В этот момент образуются большие островки переменных с одинаковым состоянием, так что в распределении появляются сильные корреляции - сценарий, при котором, например, выборка Гиббса не очень подходит. Этот метод был обобщен на другие модели[88], хотя здесь мы обрисовываем в общих чертах процедура только для модели Изинга, отсылающая читателя к более специализированному тексту для расширений [37]. Смотрите также [198] об использовании вспомогательных переменных в идеальной выборке.

Модель Изинга без внешних полей определяется по переменным x = (x1 , ... , xn ), xi ; {0, 1} и принимает вид

, что означает, что это попарная марковская сеть с потенциальным вкладом e;, если соседние узлы i и j квадратной решетки находятся в одинаковом состоянии, и вкладом 1 в противном случае. Мы предполагаем, что ; > 0, что побуждает соседей находиться в одном и том же состоянии. Структура окрестностей, основанная на решетке, затрудняет выборку, особенно когда ; ; 0,9, что способствует образованию крупномасштабных островков переменных с одинаковыми состояниями.

Цель состоит в том, чтобы устранить проблемные члены e;I[xi =xj ] путем использования вспомогательных переменных связи, yij, по одной для каждого ребра решетки, что упрощает выборку из условного значения p (x |y). Это определяется как
Используя p(y|x), мы можем отменить условия e;I[xi =xj], установив значение
где I[0 < yij < e;I[xi =xj ] обозначает равномерное распределение между 0 и e;I[xi =xj ] ; zij - нормализация
504 ПРОЕКТ от 9 марта 2010 г. Методы определения вспомогательных переменных

Рисунок 27.11: Десять последовательных выборок из модели Изинга размером 25 ; 25 p(x) ; exp(; i~j;I[xi=xj]) при ; = 0,88, что близко к критической температуре. Используется процедура Свендсона-Вана. Начиная с произвольной начальной конфигурации, образцы быстро изменяют это начальное состояние, при этом характерные дальнодействующие корреляции переменных наблюдаются вблизи критической температуры.

постоянной zij = e;I[xi =xj ] . Следовательно
Предположим, что у нас есть выборка {yij }. Если yij > 1, то для построения выборки из p(x|y) мы должны иметь 1 < e;I[xi =xj ] , что означает, что xi и xj должны находиться в одном и том же состоянии. В противном случае, если yij < 1, то это не накладывает дополнительных ограничений на xi и xj. Следовательно, везде, где yij > 1, мы связываем xi и xj, чтобы они находились в одном и том же состоянии.

Для выборки из переменных связи p(yij |xi ,xj ) рассмотрим сначала ситуацию, когда xi и xj находятся в одинаковом состоянии. Тогда p(yij |xi = xj ) = U (yij |[ 0,e;]), т.е. Аналогично, когда xi и xj находятся в разных состояниях, p(yij |xi ; xj ) = U (yij | [0, 1]). Связь образуется, если yij > 1, что происходит с вероятностью
Следовательно, если xi = xj, мы связываем xi и xj с тем, что они находятся в одном и том же состоянии с вероятностью 1 ; e;; . С другой стороны, если xi и xj находятся в разных состояниях, yij равномерно распределяется между 0 и 1.

Проделав это для всех пар xi и xj, мы получим граф, на котором у нас будут кластеры переменных, связанных с одинаковыми состояниями. Алгоритм просто выбирает случайное состояние для каждого кластера – то есть с вероятностью 0,5 все переменные в кластере находятся в состоянии 1. Алгоритм описан ниже, см. рис.27.10:

Алгоритм 27 Выборки Свендсона-Вана
1: Начните со случайной конфигурации всех x11 , . . . , x1n .
2: для значений от l = 1 до L выполните
для i, j в наборе ребер выполнение
Если xi = xj , мы связываем переменные xi и xj с вероятностью 1 ; e;; .
5:конец для
6:Для каждого кластера, сформированного из вышеперечисленного, задайте состояние кластера равномерно случайным образом.
7:Это дает новую конфигурацию соединения xl1 , . . . , xln .
8: конец для

Этот метод нашел применение в пространственной статистике, в частности в восстановлении изображений[134].
27.5.3 Отбор проб срезов
Выборка срезов[207] - это вспомогательный метод с переменными, который направлен на преодоление некоторых трудностей в выбор подходящей "шкалы длин" в таких методах, как выборка из Метрополиса. Краткое обсуждение
ПРОЕКТ от 9 марта 2010 г.  505 Выборка из важных данных
Рисунок 27.12: Полный срез для данного y. В идеале при выборке среза можно получить x-образную выборку из любого места всего среза (зеленого). В общем случае это невозможно для сложного распределения, и вместо этого формируется локальный приблизительный срез, см. рис.27.13.

далее следует то, что представлено в [183] и [42]. Мы хотим нарисовать выборки из p(x) = 1/Z p; (x), где константа нормализации Z неизвестна. Введя вспомогательную переменную y и определив распределение

в противном случае

мы имеем
который показывает, что предельное значение p(x, y) по отношению к y равно распределению, из которого мы хотим получить выборки. Следовательно, если мы получим выборки из p(x, y), мы можем игнорировать выборки y и у нас будет действительная схема выборки для p(x).

Чтобы вывести из p (x, y), мы используем выборку Гиббса, сначала выводя из p (y|x), а затем из p(x|y). Вывести \Рисуем\ выборку из p (y|x) означает, что мы выводим значение y из равномерного распределения U (y| [0, p; (x)]).

Учитывая выборку y, затем мы выводим выборку x из p(x|y). Используя p(x|y) ; p(x, y), мы видим, что p(x|y) - это распределение по x такое, что p; (x) > y:
Для данного y мы называем x, удовлетворяющие этому условию, "срезом", рис.27.12. Вычисление нормализации этого распределения в целом нетривиально, поскольку нам в принципе нужно было бы выполнить поиск по всем x, чтобы найти их для которого p; (x) > y. В идеале мы хотели бы получить как можно больше фрагментов, поскольку это улучшит перемешивание цепочки. Если мы сосредоточимся на той части среза, которая находится очень близко к текущему x, то выборки будут перемещаться по пространству очень медленно. Если мы попытаемся случайным образом угадать точку, расположенную далеко от x, и проверить, находится ли она в срезе, это будет в основном безуспешным. Удачный компромисс, представленный в алгоритме (28)[207] и описанный на рис.(27.13), определяет соответствующий локальный срез путем регулировки левого и правильные области. Метод заключается в том, чтобы начать с текущего x и попытаться найти самый большой локальный фрагмент, постепенно расширяя потенциальный фрагмент. Как только у нас будет самый большой потенциальный фрагмент, мы попытаемся выполнить выборку из него. Если точка выборки в локальном срезе на самом деле не находится в срезе, это отклоняется, и срез сокращается.

Здесь описывается процедура выборки из одномерного распределения p; (x). Для выборки из многомерного распределения p(x) можно использовать выборку Гиббса с одной переменной для выборки из p(xj |x\j), повторно выбирая новую переменную xj для выборки.
27.6 Выборка по важности
Выборка по важности - это метод аппроксимации средних значений по отношению к трудноразрешимому распределению p(x). Термин "выборка", возможно, является неправильным, поскольку в этом методе не делается попытка получить выборки из p(x). Скорее всего, метод использует выборки из более простого распределения значимости q (x), а затем повторно взвешивает их таким образом, чтобы средние значения по отношению к p(x) можно было аппроксимировать, используя выборки из q(x). Рассмотрим p(x) = p*(x)/Z, где p; (x) может быть вычислено, но Z = ;x p; (x) является константой, не поддающейся нормализации. Среднее значение f (x) относительно p(x) определяется как

506  ЧЕРНОВИК от 9 марта 2010 г. Важная выборка

Рисунок 27.13: (а): Для текущей выборки x выбирается точка y между 0 и p; (x), в результате чего получается точка (x, y) (черный круг). Затем вокруг x, синей полосы, помещается интервал шириной w. Концы полоски указывают, находится ли точка в срезе (зеленая) или за его пределами (красная). (b): Интервал увеличивается до тех пор, пока не достигнет точки за пределами среза. (c): при заданном интервале выборка x` отбирается равномерно в течение этого интервала. Если кандидата x` нет в срезе (красный), p(x` ) < y, кандидат отклоняется, и интервал сокращается. (d): Выборка из интервала повторяется до тех пор, пока кандидат не окажется в срезе (зеленый), после чего он принимается.

Пусть x1 , . . . , xL - выборки из q(x), тогда мы можем приблизить среднее значение по формуле
, где мы определяем нормализованные веса важности
В принципе, повторное взвешивание выборок из q даст правильный результат для среднего значения по отношению к p. Поскольку вес является мерой того, насколько хорошо q соответствует p, обычно будет только один доминирующий показатель  вес. Это особенно очевидно при больших размерах, где, как правило, будет только один доминирующий вес со значением, близким к 1, а остальные будут равны нулю, особенно если выборочное распределение q плохо согласуется с p. В качестве примера этого эффекта рассмотрим D-мерный многомерный показатель x с двумя выборками x1 и x2 . Для простоты мы предполагаем, что p и q разложены на множители по своим переменным. Тогда соответствующие ненормализованные веса важности равны
Если мы предположим, что соответствие между q и p лучше на коэффициент ; ; 1 в каждом из измерений при x2, чем при x1, то
таким образом, вес важности на уровне w1 будет экспоненциально преобладать над w2. Метод, который может помочь устранить это преобладание, - это повторная выборка. Учитывая распределение веса w1 , . . . , wL , получается набор из L выборочных индексов. Этот новый набор индексов почти наверняка будет содержать повторы, поскольку ни один из исходных образцов с низким весом, скорее всего, не будет включен. Вес каждого из этих новых образцов устанавливается равным 1/L. Эта процедура помогает выбрать только "наиболее подходящие" образцы и известна как "Повторная Выборка Важности" [235].
ПРОЕКТ от 9 марта 2010 г.  Выборка важности 507

Алгоритм 28-сегментной выборки (одномерный).
1: Выберите начальную точку x1 и размер шага w.
2: от i = 1 до L выполните
Равномерно проведите вертикальную координату y из интервала 0, p; (xi ) .
4.Создайте горизонтальный интервал (xlef t , xright ), содержащий xi следующим образом:
5:Нарисуйте r ; U (r| (0, 1))
6:xlef t = xi ; rw, xright = xi + (1 ; r)w. Создайте начальный интервал
7:пока p; (xlef t ) > y, выполните
8:xlef t = xlef t ; w. Выйдите влево.
9:заканчивать, пока
10:пока p; (xright ) > y выполняет
11:xright = xright + w. Сделайте шаг вправо
12:завершите, пока
13:примите = ложь
14:пока примите = ложь сделайте
15:равномерно выведите случайное значение x0 из единичного интервала (xlef t , xright ).
16:если p; (x0 ) > y, то
17:принять = true. Найдена допустимая выборка
18:еще
19:измените интервал (xlef t , xright ) следующим образом:
20:если x0 > xi, то
21:xright = x0. Сжимается
22:еще
23:xlef t = x0
24:конец, если
25:конец, если
26:конец, пока
27:xi+1 = x0
28: конец для

27.6.1Последовательная выборка по важности

Можно применить выборку важности к временным распределениям p(x1:t ), для которых выборки распределения важности из q(x1:t ) являются путями. Во многих приложениях, таких как отслеживание, требуется обновлять свои убеждения по мере увеличения времени, и, как следствие, требуется пересчитывать и затем повторно взвешивать весь путь. Для распределений p(x1:t ) при марковской структуре можно ожидать, что локальное обновление возможно без необходимости обращения к предыдущему пути. Чтобы показать это, рассмотрим ненормализованные веса важности для выборочного пути xl1:t
Мы можем рекурсивно определить ненормализованные веса, используя
где
Это означает, что в SIS нам нужно только определить условное распределение важности q(xt |x1:t;1 ). Идеальным вариантом последовательного распределения важности является q = p и q(xt |x1:t;1 ) = p(xt |x1:t;1 ), хотя в большинстве случаев такой выбор непрактичен.
508 ЧЕРНОВИК от 9 марта 2010 г. Важная выборка

Рисунок 27.14: Динамическая Байесовская сеть. Во многих приложениях, представляющих интерес, распределение выбросов p(vt |ht) не является гауссовым, что приводит к формальной сложности фильтрации/сглаживания.

Для динамических Байесовских Сетей уравнение (27.6.8) значительно упростится. Например, рассмотрим распределения со Скрытой структурой независимости от Маркова,
где v1:t - наблюдения, а h1:t - случайные величины. Происходит отмена слагаемых в числителе и знаменателе, и остается просто
Последовательная выборка по важности также известна как фильтрация по частицам.

В частности, в тех случаях, когда переход легко поддается выборке, обычно используется распределение по важности
в этом случае, согласно уравнению (27.6.8), atl = p(vt |ht ) и ненормализованные веса рекурсивно определяются как
Недостатком этой процедуры является то, что после небольшого числа итераций только очень немногие веса частиц будут существенно отличны от нуля из-за несоответствия между распределением важности q и целевой величиной распределение p. Эту проблему можно решить с помощью повторной выборки, как описано в разделе (27.6)[82].

27.6.2 Фильтрация частиц как приблизительный прямой проход

Фильтрацию частиц можно рассматривать как приближение к точной рекурсии фильтрации. Используя ; для представления отфильтрованного распределения,
точная рекурсия фильтрации равна
PF можно рассматривать как аппроксимацию уравнения (27.6.14), в котором сообщение ;(ht;1 ) аппроксимируется суммой ;-пиков:
где wt;1 ; нормализованные веса значимости ;Ll=1 wlt;1 = 1, а h l t-1 - частицы . Другими словами, сообщение ; представлено в виде взвешенной смеси дельта-всплесков, где вес и положение всплесков являются параметрами распределения. Используя уравнение (27.6.15) в уравнении (27.6.14), мы имеем

ЧЕРНОВИК от 9 марта 2010 г. Выборка из важных данных 509
Константа Z используется для нормализации распределения ;(ht ). Хотя ;(ht;1 ) было простой суммой дельта пиков, в общем случае, ;(ht ) не будет – дельта-пики "расширяются" за счет коэффициентов "от скрытого к скрытому" и "от скрытого к наблюдаемому". Затем наша задача состоит в том, чтобы аппроксимировать ;(ht ) как новую сумму дельта-пиков. Ниже мы обсудим метод достижения этой цели, для которого не требуется точное знание нормализации Z. Это полезно, поскольку во многих приложениях отслеживания нормализация выбросов p (vt |ht) неизвестна.

Аппроксимация выборки методом Монте-Карло
Простой подход к формированию приближенного представления уравнения в виде смеси дельта-функций (27.6.16) заключается в создании набора точек выборки с использованием выборки важности. То есть мы генерируем набор выборок h1t , ... , hLt из некоторого распределения важности q(ht ), которое дает ненормализованные веса важности
Определяем нормализованные веса:
мы получаем приближение
В идеале можно было бы использовать распределение важности, при котором вес важности равен единице, а именно
Однако часто бывает трудно произвести непосредственный отбор проб из-за неизвестной нормы выбросов p(vt |ht ). Более простой альтернативой является отбор проб из переходной смеси:
Для этого сначала производится выборка компонента l; из гистограммы с весами от w1 t;1
,….,wL t;1. Используя этот выборочный индекс, скажем, l *, затем извлекается выборка из p(ht |ht;1 l*). В этом случае ненормализованные веса становятся просто
Эта процедура Прямой Выборки-Повторной Выборки используется в demoParticleFilter.m и в следующем примере  об игрушке.
Пример 113 (пример отслеживания лица игрушки). В момент времени t бинарный шаблон лица находится в местоположении ht , которое описывает верхний левый угол шаблона с помощью двумерного вектора. В момент времени t = 1 положение лица известно, см. рис.27.15а). Шаблон лица известен. В последующие моменты времени грань перемещается случайным образом в соответствии с
где ; t ~N (; t |0, I) - двумерный нулевой средний единичный ковариационный вектор шума. Кроме того, часть двоичных пикселей на всем изображении выбирается случайным образом, и их состояния меняются местами. Цель
510 ЧЕРНОВИК от 9 марта 2010 г. Oтбор проб важен

Рисунок 27.15: Отслеживание объекта с помощью фильтра частиц, содержащего 50 частиц. Маленькие кружочки — это частицы, масштабированные по их весу. Правильное угловое положение грани обозначается символом ";", а среднее значение - большим кругом ‘о’, а наиболее вероятная частица - ‘+’. (а): Исходное положение поверхности без шума и соответствующего веса частиц. (b): Поверхность с шумовым фоном и отслеживаемым угловым положением на автофокусировке.- всего 20 временных шагов. Нападающий\Прямо- Метод выборки-повторной выборки PF используется для поддержания приемлемой доли ненулевых весов. Смотрите демонстрационный файл demoParticleFilter.m

состоит в том, чтобы попытаться отследить верхний левый угол лица во времени.

Нам нужно определить распределение излучения p(vt |ht ) в двоичных пикселях с vi ; {0, 1}. Рассмотрим следующую функцию совместимости
где ~v(ht ) - вектор , представляющий изображение с чистым лицом, расположенным в позиции ht . Это измеряет перекрытие между шаблоном лица и зашумленным изображением ограничено пикселями шаблона. Функция совместимости максимальна, когда на наблюдаемом изображении vt лицо расположено в позиции ht . Поэтому мы можем предварительно определить
Тонкость заключается в том, что ht является непрерывным, и в функции совместимости мы сначала сопоставляем ht с ближайшим целочисленным пиксельным представлением. Мы не указали константу нормализации этого распределения, которая, к счастью, не требуется алгоритмом фильтрации частиц. На рис.27.15а использовано 50 частиц для отслеживания лица. Частицы отображаются на графике с указанием их соответствующих весов. Для каждого значения t > 1,5% пикселей на изображении выбираются случайным образом, и их состояния меняются местами. Используется Прямая выборка- С помощью метода -Повторной выборки мы можем успешно отслеживать лицо, несмотря на наличие помех на заднем плане.

Реальные приложения для отслеживания связаны со сложными задачами, включая отслеживание нескольких объектов, преобразования объекта (масштабирование, поворот, изменение морфологии). Тем не менее, принципы в основном те же и многие приложения для отслеживания работают, используя простые функции совместимости, часто основанные на цветовой гистограмме в шаблоне. Действительно, отслеживание объектов в сложных средах было одним из первых применений фильтров твердых частиц [140].
ПРОЕКТ от 9 марта 2010 г. 511 Упражнения
27.7 Код
potsample.m: Точная выборка из набора потенциалов
ancestralsample.m: Выборка предков из сети убеждений
JTsample.m: Выборка из согласованного дерева связей
GibbsSample.m: Выборка Гиббса из набора потенциалов
demoMetropolis.m: Демонстрация выборки Metropolis для бимодального распределения
metropolis.m: Журнал регистрации образцов
logp.m: Журнал бимодального распределения
demoParticleFilter.m: Демонстрационная фильтрация частиц (метод прямой выборки-повторной выборки)
placeobject.m: Поместить объект в сетку
compat.m: Демонстрационный образец функции совместимости
HMM.m: Наивная выборка Гиббса для HMM
27.8 Упражнения
Упражнение 246 (метод Бокса-Мюллера). Пусть x1 ; U (x1 | [0, 1]), x2 ; U (x2 | [0, 1]) и
Покажем, что
и предложите алгоритм для выборки из одномерного нормального распределения.
Упражнение 247. Рассмотрим распределение
Для x5, зафиксированного в данном состоянии x5 , запишите распределение по оставшимся переменным p`(x1 , x2 , x3 , x4 , x6) и объясните, как можно выполнить прямую (наследственную) выборку для этого нового распределения.
Упражнение 248. Рассмотрим модель Изинга на квадратной решетке M ; M с взаимодействиями ближайших соседей:
Теперь рассмотрим сетку M ; M как шахматную доску и присвоим каждому белому квадрату метку wi, а каждому черному квадрату - метку bj , чтобы каждый квадрат был связан с определенной переменной. Покажем, что
То есть, зависимые от переменных белого цвета, переменные черного цвета независимы. Верно и обратное, что зависимые от переменных черного цвета переменные белого цвета независимы. Объясните, как здесь можно использовать процедуру выборки Гиббса. Эта процедура известна как выборка в шахматном порядке или черно-белая выборка.
Упражнение 249. Рассмотрим симметричное гауссово распределение предложений
и целевое распределение
где dim x = N . Показать что
Обсудите, как этот результат соотносится с вероятностью принятия обновления Метрополиса-Гастингса в соответствии с гауссовым распределением предложений в больших измерениях.
512 ЧЕРНОВИК от 9 марта 2010 года  Упражнения
Упражнение 250. В файле demoSampleHMM.m выполняется наивная выборка по методу Гиббса для задней части p(h1:T |v1:T) для HMM. При каждом обновлении по методу Гиббса выбирается одна переменная ht, а остальные переменные h фиксируются.  Процедура начинается с момента t = 1 и продолжается по времени. По достижении конечного времени t = T в качестве образца задней поверхности берется состояние сустава h1:T. Параметр ; определяет, насколько детерминированной будет скрытая матрица переходов p(ht |ht;1 ). Настройте demoSampleHMM.m так, чтобы он запускался 100 раз, каждый раз для то же самое ;, вычисляя среднюю абсолютную ошибку за эти 100 прогонов. Затем повторите это для ; = 0,1, 1, 10, 20. Обсудите, почему производительность этой процедуры выборки Гиббса ухудшается с увеличением ;.

ЧЕРНОВИК от 9 марта 2010 г.
513 Упражнений
514
ЧЕРНОВИК главы от 9 марта 2010 года
28 Глава
Детерминированный приблизительный вывод
28.1 Вступление
Методы детерминированного приближенного вывода являются альтернативой стохастическим методам, рассмотренным в главе (27). Хотя стохастические методы являются мощными и часто широко применимыми, они, тем не менее производим выборочные оценки количества. Даже если мы сможем выполнить идеальную выборку, мы все равно получим лишь приблизительный результат из-за присущей выборке неопределенности. Кроме того, на практике получение точных выборок, как правило, является сложной вычислительной задачей, а оценка качества выборочных оценок затруднена. В этой главе мы обсудим некоторые альтернативные схемы приближенного вывода с использованием детерминированных методов. Первый метод, метод Лапласа, представляет собой простой метод вычисления возмущений. Второй класс методов - это те методы, которые позволяют получить строгие оценки интересующих величин. Такие методы интересны  тем, что они предоставляют определенные знания – например, может быть достаточно показать, что предельная вероятность превышает 0,1, чтобы принять обоснованное решение. Еще одним классом методов являются методы обеспечения согласованности, такие как циклическое распространение информации. Такие методы произвели революцию в определенных областях, включая исправление ошибок[183], обеспечивая производительность, недостижимую при использовании процедур, основанных на выборке.

Важно иметь в виду, что ни один метод аппроксимации, детерминированный или стохастический, не превзойдет все остальные во всех задачах при одинаковых вычислительных ресурсах. В этом смысле понимание свойств используемого метода аппроксимации полезно для согласования метода аппроксимации с рассматриваемой задачей.
28.2 Приближение Лапласа
Рассмотрим распределение по непрерывной переменной вида
Метод Лапласа позволяет получить Гауссову аппроксимацию p (x) на основе разложения по локальным возмущениям вокруг моды\ режима x; . Сначала мы находим моду\ режим численно, давая
, то разложение Тейлора до второго порядка вокруг этого режима дает
где H;E(x)|x; - коэффициент Гесса, вычисленный в режиме \моде. В моде ;E|x; = 0, и
приближение распределения задается Гауссовым коэффициентом.
515 Свойства вариационного вывода Кульбака-Лейблера
Рисунок 28.1: Сопоставление смеси Гауссианов p (x) (синий) с одним гауссианом. Зеленая кривая минимизирует значение KL(q|p), соответствующее подбору локальной модели. Красная кривая минимизирует значение KL(p|q), соответствующее подбору момента.

, который имеет среднее значение x; и ковариацию H;1 , где Z ; =; det (2;H;1 ). Аналогично, мы можем использовать приведенное выше разложение для оценки интеграла
Хотя приближение Лапласа соответствует Гауссову распределению, оно не обязательно является "наилучшим" Гауссовым приближением. Как мы увидим ниже, другие критерии, такие как основанные на минимальном отклонении KL между p (x) и Гауссовой аппроксимацией, могут быть более подходящими, в зависимости от контекста.  Преимуществом метода Лапласа является его относительная скорость и простота по сравнению с другими методами приближенного вывода.
28.3 Свойства вариационного вывода Кульбака-Лейблера
Вариационные методы могут быть использованы для аппроксимации сложного распределения p(x) более простым распределением q(x). Учитывая определение несоответствия между приближением q(x) и p(x), любые свободные параметры q(x) затем устанавливаются путем минимизации несоответствия.

Особенно популярной мерой расхождения между приближением q(x) и неразрешимым
распределением p(x) является дивергенция Кульбака-Лейблера
Несложно показать, что KL(q|p) ; 0 и равно нулю тогда и только тогда, когда распределения p и q идентичны, см. раздел (8.8). Обратите внимание, что, хотя расхождение KL не может быть отрицательным, верхней границы не существует для значения, которое оно потенциально может принять, так что расхождение может быть "бесконечно" большим.
28.3.1 Ограничивающая константа нормализации
Для распределения вида
у нас есть
Поскольку KL(q|p) ; 0, это сразу же дает связанный логарифм
энтропия
энергия
, которая в физическом сообществе называется границей "свободной энергии"[236]. Используя обозначение Hq для энтропии q, мы можем записать границу более компактно в виде
Таким образом, метод KL(q|p) обеспечивает нижнюю границу константы нормализации. Для некоторых моделей возможно (используя альтернативные методы, см., например, [287] и упражнение(258)) также сформировать верхнюю границу константы нормализации.

516 ЧЕРНОВИК от 9 марта 2010 г. Свойства вариационного вывода Кульбака-Лейблера

\, связанного с константой нормализации. Используя как верхнюю, так и нижнюю границу для условий нормализации, мы можем заключить маргинальные значения l ; p(xi ) ; u в квадратные скобки, см. упражнение(261). Жесткость результирующей скобки показывает, насколько жесткими являются ограничения процедуры. Даже в тех случаях, когда результирующая скобка является слабой – например, может оказаться, что результат равен 0,1 < p(рак \carcer = истина \ true) < 0,99, этого может быть достаточно для принятия решения, поскольку вероятность рака достаточно велика, чтобы заслужить принятия мер.
28.3.2 Ограничение предельной вероятности
В байесовском моделировании вероятность того, что модель M с параметрами ; сгенерирует данные D, определяется как
 вероятность , предшествующая

Эта величина является фундаментальной для сравнения моделей. Однако в случаях, когда ; является многомерным, интеграл по ; выполнить сложно. Используя правило Байеса,
и учитывая

неотрицательность дивергенции Кульбака-Лейблера дает привязанный
Эта граница справедлива для любого распределения q(;) и насыщается, когда q(;) = p(;|D, M). Поскольку использование оптимальной настройки считается вычислительно сложным, идея вариационного ограничения заключается в выборе распределения семейство для q(;), для которого граница поддается вычислению (например, факторизованная или Гауссова), а затем максимизируем границу относительно любых свободных параметров q(;). Полученная оценка затем может быть использована в качестве суррогата для точного предельного правдоподобия при сравнении моделей.
28.3.3 Гауссовы аппроксимации с использованием расходимости KL
Минимизация KL(q|p)
Использование простой аппроксимации q (x) более сложного распределения p(x) путем минимизации KL (q |p), как правило, дает решение для q (x), которое фокусируется на локальном режиме p(x), тем самым недооценивая дисперсию p(x). Чтобы показать это, рассмотрим аппроксимацию смеси двух гауссиан с равной дисперсией ;2 ,
см. рис.(28.1), с одним Гауссовым
Мы хотим найти оптимальные значения m, s2, которые минимизируют
Если мы рассмотрим случай, когда две гауссовы составляющие p (x) хорошо разделены, µ»  ;, то установив q (x) центрированным на левой моде в точке ;µ, Гауссова q (x) имеет заметную массу, близкую к ;µ, так что что вторая мода при µ вносит незначительный вклад в дивергенцию Кульбака-Лейблера. В этом смысле можно аппроксимировать p(x) ; 1/2 q(x), так что
ПРОЕКТ от 9 марта 2010 г. 517 Свойства вариационного вывода Кульбака-Лейблера
 Рисунок 28.2: Плоское попарно марковское случайное поле с набором переменных x1, . . . , x25 , представляющее собой распределение вида ;i~j ;(xi , xj ). В статистической физике к таким решетчатым моделям относится модель Изинга для бинарных ‘спиновых’ переменных xi ; {+1, -1} при ;(xi , xj ) = ewij xi xj .

С другой стороны, при установке m = 0, что является правильным средним значением распределения p(x), улавливается очень малая часть массы смеси, если только s2 не велико, что приводит к плохой подгонке и большому отклонению KL. Другой способ увидеть это - рассмотреть KL(q |p) = <log q(x)|p(x)>q(x) ; при условии, что q близко к p примерно там, где q имеет при значительной массе отношение q(x)|p(x) будет порядка 1, а расхождение KL будет небольшим. Установка m = 0 означает, что q(x)|p(x) велико, когда q имеет значительную массу, и, следовательно, плохо подходит. Оптимальным решением в этом случае является размещение гауссова сигнала вблизи одиночного режима. Однако обратите внимание, что для двух режимов, которые менее хорошо разделены, оптимальным решением не обязательно будет размещение гауссова сигнала вокруг локального режима. В общем, оптимальное соответствие по Гауссу должно быть определено численно, то есть не существует замкнутого
решения для нахождения оптимального среднего значения и (со) параметров дисперсии.

Минимизируя KL(p|q)

Для подгонки гауссова q к p на основе KL (p|q), мы имеем
Минимизируя это значение относительно m и ;2, получаем:
таким образом, оптимальная Гауссова подгонка соответствует первому и второму моментам p(x).

В случае рис.28.1 среднее значение p(x) равно нулю, а дисперсия p(x) велика.  Таким образом, это решение кардинально отличается от решения, полученного путем подгонки гауссова уравнения с использованием KL (q|p). Найденное соответствие использование KL(q|p) фокусируется на том, чтобы q хорошо соответствовал p локально, в то время как KL (p|q) фокусируется на том, чтобы q хорошо соответствовал p глобальной статистике распределения (возможно, за счет хорошего локального соответствия).
28.3.4 Момент, соответствующий свойствам минимизации KL(p|q)
Для простоты рассмотрим факторизованную аппроксимацию q(x) =;iq(xi). Тогда
Первый энтропийный член не зависит от q (x), так что с точностью до константы, независимой от q(x), приведенное выше значение равно
так что оптимально q(xi ) = p(xi ). То есть оптимальная факторизованная аппроксимация заключается в том, чтобы установить коэффициенты q(xi ) на предельные значения p(xi ), выполните упражнение(265). Для любого аппроксимирующего распределения в экспоненциальном семействе минимизация KL(p|q) соответствует согласованию моментов, см. упражнение(264). На практике, как правило, невозможно вычислить моменты p(x) (поскольку распределение p(x) считается "неразрешимым"), так что подгонка q к p на основе только KL (p|q) сама по себе не приводит к практическому алгоритму приближенного вывода. Тем не менее- менее того, как мы увидим, это полезная подпрограмма для локальных аппроксимаций, в частности для распространения математического ожидания.
518 ЧЕРНОВИК от 9 марта 2010 г. Вариационное ограничение с использованием KL(q|p)
28.4 Вариационное Ограничение с Использованием KL(q|p)

В этом разделе мы обсудим, как подогнать распределение q (x) из некоторого предполагаемого семейства к "неразрешимому" распределению p (x). Как мы видели выше, для случая подгонки гауссианов оптимальное q должно быть найдено численно. Это само по себе может быть сложной задачей (на самом деле, формально это может быть так же сложно, как выполнить логический вывод непосредственно с помощью неразрешимого p), и читатель может задаться вопросом, почему мы заменяем сложную задачу логического вывода потенциально сложной задачей оптимизации. Общая идея заключается в том, что задача оптимизации имеет некоторые свойства локальной гладкости, позволяющие быстро найти приемлемый оптимум на основе общих методов оптимизации. Чтобы сделать эти идеи более конкретными, мы обсудим частный случай подгонки q к формально неразрешимому p в разделе (28.4.1) ниже.
28.4.1 Попарное Марковское случайное поле
Каноническим ‘неразрешимым’ распределением является попарное Марковское Случайное Поле, определенное по двоичным переменным xi ; {+1, -1}, i = 1, . . . , D,
Здесь "функция распределения" Z(w, b) обеспечивает нормализацию,
Поскольку x2 = 1, члены wii x2i постоянны, и без потери общности мы можем установить значение wii равным нулю 1 . Это дает неориентированное распределение с геометрией соединения, определяемой весами w. На практике веса часто определяют локальные взаимодействия на решетке, см. рис. 28.2. Случай, для которого требуется вывод в этой модели, приведен в примере 114.

Пример 114 (Байесовское подавление шума на изображении). Рассмотрим двоичное изображение, где x описывает состояние чистых пикселей (кодировка ±1). Мы предполагаем, что процесс генерации зашумленных пикселей, который использует каждый чистый пиксель xi и изменяет его двоичное состояние:
Вероятность того, что yi и xi находятся в одном и том же состоянии, равна ey /(ey + e;; ). Нас интересует апостериорное распределение в чистых пикселях p(x|y). Для этого нам нужно сделать предположение о том, как выглядят чистые изображения. Мы делаем это с помощью MRF
для некоторых настроек wij > 0, где i ~ j указывает на то, что i и j являются соседями. Это подтверждает предположение о том, что на чистых изображениях соседние пиксели, как правило, находятся в одинаковом состоянии.  Изолированный пиксель в другом состоянии к своим соседям, что маловероятно при таком подходе. Теперь у нас есть совместное распределение
смотрите рисунок(28.3), на котором апостериорная часть задана как
Представляют интерес такие величины, как состояние МАР (наиболее апостериорно вероятное изображение), маргиналы p(xi |y) и константа нормализации.
1 В то время как вывод с использованием общего MRF формально трудноразрешим с точки зрения вычислений (известных точных методов за полиномиальное время не существует), два знаменитых результата, о которых мы упомянем мимоходом, заключаются в том, что для плоской модели MRF с чистыми взаимодействиями (b = 0) статистическая сумма вычислима за полиномиальное время[157, 95, 177, 115, 243], как и состояние МАР для привлекательных плоских моделей Изинга w > 0 [121], см. раздел(28.8).
ПРОЕКТ от 9 марта 2010 г. 519 Вариационных границ с использованием KL(q|p)

Рисунок 28.3: Распределение по пикселям. Заполненные узлы указывают на наблюдаемые зашумленные пиксели, незатененные узлы - на случайное поле Маркова для скрытых чистых пикселей. Задача состоит в том, чтобы определить чистые пиксели, учитывая зашумленные пиксели. MRF поощряет апостериорное распределение по чистым пикселям, чтобы соседние пиксели оставались в том же состоянии.

Методы, основанные на методе Кульбака-Лейблера
Для MRF мы имеем
При перезаписи это дает привязку к функции логарифмического разбиения
энтропия
энергия

Граница насыщается, когда q = p. Однако это мало помогает, поскольку мы не можем вычислить средние значения переменных относительно этого трудноразрешимого распределения <xi xj >p , <xi >p . Идея вариационного метода заключается в предположим, что существует более простое "управляемое" распределение q, для которого можно вычислить эти средние значения вместе с энтропией q. Минимизация расхождения KL по любым свободным параметрам q (x) эквивалентна  максимизации нижней границы функции логарифмического разбиения.

Факторизованное приближение
Простым ‘наивным’ предположением является полностью факторизованное распределение
Графическая модель этого приближения приведена на рис. (28.4а). В этом случае
Для факторизованного распределения и с учетом того, что xi ; {+1, -1},
Для двоичной переменной можно использовать удобную параметризацию
так что


Рисунок 28.4: (а): Аппроксимация Наивного Среднего поля q(x) = iqi (xi ). (b): Аппроксимация остовным деревом. (c): Аппроксимация с возможностью разложения (гипердерево).
ЧЕРНОВИК от 9 марта 2010 г. Вариационное ограничение с использованием KL(q|p)
Это дает следующую нижнюю границу для функции разделения логарифма:
где H(;i ) является двоичной энтропии распределения размеров по уравнению (28.4.12):
Нахождение наилучшего факторизованного приближения в смысле минимальной дивергенции Кульбака- Либлера соответствует максимизации границы B(;) по отношению к вариационным параметрам ;.

Граница B, уравнение (28.4.14), как правило, невыпукла в ; и содержит множество локальных оптимумов. Поэтому поиск глобально оптимального ; обычно является сложной вычислительной задачей. Кажется, что мы просто имеем замену сложной в вычислительном отношении задаче вычисления log Z на не менее сложную вычислительную задачу максимизации B(;). Действительно, "графическая структура" этой задачи оптимизации в точности соответствует исходной MRF. Однако мы надеемся, что, преобразовав сложное дискретное суммирование в задачу непрерывной оптимизации, мы сможем использовать методы численной оптимизации непрерывных переменных для получения хорошего приближения. Особенно простой метод оптимизации заключается в дифференциации связанного уравнения (28.4.14) и приравнивается к нулю. Простая алгебра приводит к требованию, чтобы оптимальное решение удовлетворяло уравнениям
Можно показать, что изменение любого ;i в соответствии с уравнением (28.4.16) увеличивает B(;). Это называется асинхронным обновлением и гарантированно приводит к (локальному) минимуму расхождения KL, раздел (28.4.3).

Как только будет найдено сходящееся решение, в дополнение к привязке к log , мы можем аппроксимировать
Достоверность факторизованной аппроксимации
Когда можно ожидать, что такое наивное факторизованное приближение будет хорошо работать? Очевидно, что если wij очень мало для i; j, распределение p будет эффективно разложено на множители. Однако более интересным случаем является случай, когда у каждой переменной xi много соседей. Полезно записать MRF в виде
, где локальные "поля" определяются как
Теперь мы используем циклический (но самосогласованный) аргумент: Давайте предположим, что p(x) разложено на множители. Тогда для zi , каждый из членов xj в суммировании ;j wij xj независим. При условии, что wij не сильно коррелированы, выполняются условия справедливости центральной предельной теоремы[122], и каждый zi будет распределен по Гауссу. Предполагая, что каждый wij равен O (1), среднее значение zi равно
Дисперсия равна

Проект D2 от 9 марта 2010 г. 521 Вариационное ограничение с использованием KL(q|p)

Следовательно, дисперсия поля zi намного меньше его среднего значения. С увеличением D колебания вокруг среднего значения уменьшаются, и мы можем записать
Следовательно, предположение о том, что p приблизительно разложено на множители, является самосогласованным в пределе MRF с большим числом соседей. Следовательно, факторизованное приближение представляется разумным в случае крайние пределы (i) очень слабо связанная система wij ; 0 или (ii) большая плотно связанная система.

Полностью факторизованное приближение также называется теорией Наивного Среднего Поля, поскольку для случая MRF оно предполагает, что мы можем заменить влияние соседей средним значением поля на каждом участке.
28.4.2 Общие уравнения среднего поля
Для общего неразрешимого распределения p(x) на дискретном или непрерывном x расхождение KL между факторизованным приближением q(x) и p(x) равно
Изолируя вышеуказанную зависимость от одного фактора q(xi), мы имеем
Следовательно  точностью до константы нормализации, расхождение KL между q(xi) и распределением пропорционально exp (<log p(x)> ;j;iq(xj ) таким образом, чтобы оптимальная настройка для q(xi) удовлетворяла
Они известны как уравнения среднего поля и определяют новый коэффициент аппроксимации в терминах предыдущих коэффициентов аппроксимации. Обратите внимание, что если константа нормализации p(x) неизвестна, это не представляет проблемы, поскольку эта константа просто учитывается при нормализации коэффициентов q(xi). Другими словами, можно заменить p(x) на ненормированное p; (x) в уравнении (28.4.25). Начиная с начального случайно выбранного набора распределений q(xi), уравнения среднего поля повторяются до тех пор, пока не будет достигнута сходимость. Асинхронное обновление гарантированно уменьшает расхождение KL на каждом этапе, раздел (28.4.3).
28.4.3 Асинхронное обновление гарантирует улучшение аппроксимации
Для факторизованного уравнения вариационной аппроксимации (28.4.23) мы утверждаем, что каждое обновление уравнения (28.4.25) уменьшает ошибку аппроксимации Кульбака-Лейблера. Чтобы показать это, мы записываем один обновленный дистрибутив в виде
Совместное распространение в рамках этого единственного обновления осуществляется следующим образом
Нас интересует изменение погрешности аппроксимации при этом единственном обновлении среднего поля:
С помощью
522 ЧЕРНОВИК от 9 марта 2010 г. Вариационное ограничение с использованием KL(q|p)
Рисунок 28.5: (а): Игрушечное "неразрешимое" распределение. (b): Структурированная односвязная аппроксимация.

и определение ненормированного распределения
тогда
Следовательно
таким образом, обновление одного компонента q за раз гарантированно улучшит аппроксимацию. Обратите внимание, что этот результат является довольно общим и справедлив для любого распределения p(x). В случае Марковской сети гарантированное улучшение аппроксимации эквивалентно гарантированному увеличению (строго говоря, не уменьшению) нижней границы статистической суммы.
28.4.4 Неподатливая \Непроходимая\ энергия
Хотя полностью факторизованная аппроксимация является довольно строгой, даже этого может быть недостаточно для получения среднего значения.- уравнения поля легко реализуемы. Для этого нам нужно уметь вычислять <log p* (x)>;j;i q(xj) . Для j;i некоторых представляющих интерес моделей это все еще невозможно, и требуются дополнительные приближения.
Пример 115 ("Неразрешимая" аппроксимация среднего поля). Рассмотрим апостериорное распределение из задачи классификации с помощью Векторной Машины Относительности, раздел(18.2.4):
Условия ;( cn wT xn) делают p(w | D) негауссовым. Мы можем найти гауссово приближение q(w) =N (w |µ, ;) путем минимизации расхождения Кульбака-Лейблера
Энтропийный термин понятен, поскольку это отрицательная энтропия Гауссова уравнения. Однако нам также требуется "энергия", которая включает в себя вклад
Для этого не существует выражения в замкнутом виде. Один из подходов заключается в использовании дополнительных вариационных приближений, [141, 238]. Другой подход заключается в признании того, что многовариантное среднее значение может быть сведено к однозначному среднему значению по Гауссу:
ПРОЕКТ от 9 марта 2010 г. 523 Максимизация взаимной информации: вариационный подход KL

и одномерное гауссово среднее значение могут быть получены с использованием квадратуры. Этот подход использовался в [22] чтобы аппроксимировать апостериорное распределение Байесовских Нейронных Сетей.
28.4.5 Структурированная вариационная аппроксимация
Можно расширить факторизованную вариационную аппроксимацию KL, используя нефакторизованную q (x)[239, 24]. К числу тех, для которых средние значения переменных могут быть вычислены за линейное время, относятся связующие деревья (рис.28.4б) и разложимые графы (рис.28.4в). Например, для распределения
приемлемым \проходным\ распределением q было бы, рис.28.5
В этом случае мы имеем
Поскольку q односвязен, вычисление маргиналов и энтропии несложно (поскольку для вычисления энтропии требуются только попарные маргиналы на соседних графах).

В более общем плане можно использовать любую структурную аппроксимацию с произвольной шириной гипердерева w, используя алгоритм дерева соединений в сочетании с расхождением KL. Однако вычислительные затраты экспоненциально возрастают с увеличением ширины гипердерева[294].
28.5 Взаимная Максимизация Информации: Вариационный Подход KL
Здесь мы сделаем небольшую паузу, чтобы продемонстрировать применение вариационного подхода Кульбака-Лейблера в теории информации. Основной целью является максимальная передача информации, измеряемая (см. также определение(87))
I(X, Y) ; H(X) ; H(X|Y ) (28.5.1)
где члены определены
Здесь нас интересует ситуация, в которой p(x) фиксировано, но p(y|x, ;) имеет регулируемые параметры ;, которые мы хотим установить, чтобы максимизировать I(X, Y ). В этом случае H(X) является постоянной величиной, и задача оптимизации эквивалентна минимизации условной энтропии H(X|Y). К сожалению, во многих случаях, представляющих практический
интерес, H(X|Y) является вычислительно неразрешимой. Смотрите мотивирующий пример (116) ниже. Мы обсудим в разделе (28.5.1) общую процедуру, основанную на расхождении Кульбака-Лейблера, чтобы приблизительно максимизировать взаимную информацию.

Пример 116. Рассмотрим нейронную систему передачи, в которой xi ; {0, 1} обозначает излучающий нейрон в неактивном состоянии (0) или активирующем состоянии (1), а yj ; {0, 1} - принимающий нейрон. Если каждый принимающий нейрон активируется независимо, в зависимости только от излучающих нейронов, мы имеем
524ЧЕРНОВИК от 9 марта 2010 г. Максимизация взаимной информации : вариационный подход
Рисунок 28.6: Задача передачи информации. Для фиксированного распределения p(x) = ;ip(xi) и параметризованных распределений p(yj |x) = ; (wTi x) , найдите оптимальные параметры wi, которые максимизируют взаимную информацию между переменными x и y. Такие соображения популярны в теоретической нейронауке и направлены на понимание того, как рецептивные поля wi нейрона связаны со статистикой окружающей среды p(x).

Алгоритм 29. Алгоритм IM
1: Выберите класс аппроксимирующих распределений Q (например, разложенных на множители)
2: Инициализируйте параметры ;
3: повторите
4:Для фиксированного q(x|y) найдите
;;new = argmax I(X,Y)(28.5.6)
5:Для фиксированного ;,
q новый (x|y) = argmax I(X,Y)(28.5.7)
q(x|y);Q
где Q - выбранный класс распределений.
6: до тех пор, пока не будет достигнута конвергенция


, где, например, мы могли бы использовать

Если мы сделаем простое предположение, что излучающие нейроны активируются независимо, то
тогда для p(x|y) все компоненты переменной x являются зависимыми, см. рис.28.6. Это определяет сложную многомерную величину p(x, y), для которой условная энтропия обычно является неразрешимой.
28.5.1 Алгоритм максимизации информации
Рассмотрим
Это сразу же дает оценку
Умножая с обеих сторон на p(y), получаем
Из определения следует, что слева от приведенного выше значения находится ;H(X|Y ). Следовательно
ЧЕРНОВИК от 9 марта 2010 года   распространение представлений

Рис.28.7: Классическое распространение представлений может быть получено путем рассмотрения вопроса о том, как вычислить предельное значение переменной в MRF. В этом случае предельное значение p(d) зависит от сообщений, передаваемых через соседей по d. Определяя локальные сообщения в связях графа, можно получить рекурсивный алгоритм для вычисления всех предельных значений, см. текст.

Исходя из этой нижней границы взаимной информации, мы приходим к алгоритму[20] максимизации информации (IM).  Учитывая распределение p(x) и параметризованное распределение p(y|x, ;), мы стремимся к максимальному- имитировать I(X,Y ) относительно ;. Процедура оптимизации с учетом координат представлена в алгоритме(29). Алгоритм Блахута-Аримото в теории информации (см., например, [184]) является частным случаем, в котором оптимальный декодер
q(x|y) ; p(y|x, ;)p(x) (28.5.12)
используется. В приложениях, где алгоритм Блахута-Аримото трудно реализовать, алгоритм IM может предоставить альтернативу, ограничив q приемлемым семейством распределений (приемлемым в смысле что нижняя граница может быть вычислена). Алгоритм Блахута-Аримото аналогичен алгоритму EM для обеспечения Максимального Правдоподобия и гарантирует неизменность взаимной информации на каждом этапе обновления. Аналогично, процедура обмена мгновенными сообщениями аналогична Обобщенной процедуре EM, и каждый шаг процедуры не может уменьшать нижнюю границу взаимной информации.
28.5.2 Линейный гауссовский декодер
Особым случаем IM-фреймворка является использование линейного Гауссовского декодера

Подключив это к оценке MI, уравнению (28.5.11) и оптимизировав относительно ; и U, мы получим
, где <·> ; <·>p(x,y) . Используя это в привязке MI, мы получаем
С точностью до нерелевантных констант это эквивалентно как-если-Гауссовскому приближению Линскера к взаимной информации [176]. Таким образом, подход Линскера можно рассматривать как частный случай алгоритма IM ограниченный линейно-гауссовыми декодерами. Таким образом, в принципе, метод Линскера можно усовершенствовать, рассмотрев более мощные нелинейно-гауссовы декодеры. Применение этого метода к нейронным системам обсуждается в [20].
28.6 Закольцованное Распространение Веры \ Петлевое \Циклическое\ Распространение Убеждений
Распространение веры\убеждений BP- это метод точного вывода маргиналов p(xi) для односвязных распределений p(x). Существуют различные формулы определения BP, наиболее современной из которых является алгоритм суммарного произведения на соответствующем факторном графе, как описано в разделе (5.1.2). Важным замечанием является то, что алгоритм является чисто локальным – обновления не знают о глобальной структуре графа и зависят только от структуры локальной окрестности. Это означает, что даже если граф многосвязный (он закольцован), все равно можно применить алгоритм и "посмотреть, что произойдет’. При условии, что циклы на графике относительно длинные, можно надеяться, что при использовании "зацикленного" BP результаты будут сходиться к хорошему приближению к истинным предельным значениям. В целом, это не может быть гарантировано; однако, когда метод сходится, результаты могут быть удивительно точными.

Далее мы покажем, как циклический BP также может быть мотивирован вариационной целью. Для этого наиболее естественной является связь с классическим алгоритмом BP (а не с суммой-произведением факторных графов) алгоритмом. По этой причине ниже мы кратко опишем классический подход к BP.
526 ЧЕРНОВИК от 9 марта 2010 г. Распространение по кругу убеждений

Рисунок 28.8: Распространение по кругу убеждений. Как только узел получил входящие сообщения от всех соседей (за исключением того, которому он хочет отправить сообщение), он может отправить исходящее сообщение соседу:
28.6.1 Классическое значение BP на неориентированном графе
Значение BP можно получить, рассмотрев, как вычислить ВP - предельное значение в терминах сообщений на неориентированном графе. Рассмотрим вычисление предельного значения p(d) = a,b, c, e,f p(a, b, c, d, e, f) для попарной сети Маркова- P, представленной на рис.28.7. Мы обозначаем как узел, так и его состояние одним и тем же символом, так что b ; (d, b) обозначает суммирование по состояниям переменной b. Выполнение такого суммирования приводит к "сообщению" ;b;d (d), содержащему информацию от узла b к узлу d. Чтобы эффективно вычислить суммирование, мы распределяем уммы следующим образом:
где мы определяем сообщения ;n1 ;n2 (n2), отправляющие информацию от узла n1 к узлу n2 в зависимости от состояния узла n2. В общем случае узел xi передает сообщение узлу xj через
Этот алгоритм эквивалентен алгоритму суммирования при условии, что граф односвязный.
28.6.2 Циклическое BP как вариационная процедура
Вариационная процедура, соответствующая циклическому BP, может быть получена путем рассмотрения условий стандартной вариационной аппроксимации, основанной на дивергенции Кульбака-Лейблера KL(q|p)[299]. Для попарного MRF, определенного на основе потенциалов ;(xi , xj),
и аппроксимирующем распределении q(x), граница Куллбака-Лейблера равна
где
каждый вклад в энергию зависит от q(x) только через попарные предельные значения q(xi , xj). Это предполагает что эти маргиналы должны быть естественными параметрами любого приближения. Можем ли мы тогда найти выражение для энтропийного показателя log <q(x)>q(x) в терминах этих попарных маргиналов? Рассмотрим случай, когда требуемыми маргиналами являются
q(x1 , x2 ), q(x2 , x3 ), q(x3 , x4 ) (28.6.6)
ДРАФТ от 9 марта 2010  527 Распространение петлевых убеждений
Учитывая эти предельные значения, энергетический член легко вычислить, и нам остается только запросить энтропию q. Либо обратившись к представлению дерева соединений, либо используя простую алгебру, можно показать, что мы можем однозначно выразить q в терминах маргиналов следующим образом
Интуитивно понятный способ получить этот результат - обучить числитель уравнения (28.6.7). Переменная x2 появляется дважды, как и переменная x3, и, поскольку любое совместное распределение не может иметь повторяющихся переменных слева от любого условия, мы должны компенсировать дополнительные переменные x2 и x3 путем деления на эти маргинальные значения. В этом случае энтропия q(x) может быть записана в виде
В более общем плане, в главе (6), любой разложимый граф может быть представлен в виде
где q(Xc ) - это маргиналы, определенные на кликах графа, причем Xc - это переменные клики, а q(Xs ) определены на разделителях (пересечениях соседних кликов). Затем выражение для энтропии распределения определяется как сумма предельных энтропий за вычетом энтропии предельных значений, определенных на разделителях.
Cвободная энергия Бете
Рассмотрим теперь MRF, соответствующий неразложимому графу, например, 4-цикловому
Следовательно, энергия требует, чтобы мы знали
Предполагая, что эти маргиналы заданы, можем ли мы найти выражение для энтропии совместного распределения q(x1 , x2 , x3 , x4 ) в терминах его попарных маргиналов q(xi , xj )? В общем случае это невозможно, поскольку граф, соответствующий маргиналям, содержит циклы (так что представление дерева соединений привело бы к кликам, размер которых превышает 2). Однако простой способ "не допустить пересчета" состоит в том, чтобы записать
с учетом ограничений
Таким образом, энтропийное приближение, использующее это представление, является
При таком приближении логарифмическая статистическая функция известна в статистической физике как (отрицательная) свободная энергия Бете. В этом случае наш интерес заключается в максимизации этого выражения для параметров q(xi , xj ) с учетом ограничений на предельную согласованность, ;xi q(xi , xj ) = q(xj ). Это может быть выполнено с использованием множителей Лагранжа. Свободную энергию Бете можно записать в виде
(28.6.15)
ЧЕРНОВИК от 9 марта 2010 г. Распространение дурацких убеждений
где i ~ j обозначает уникальные соседние ребра на графе (каждое ребро подсчитывается только один раз). Это больше не является ограничением для функции логарифмического разбиения, поскольку приближение энтропии не является нижней границей истинной энтропии. Теперь задача состоит в том, чтобы максимизировать эту "приблизительную границу" относительно параметров, а именно всех попарных маргиналов q(xi , xj ) и множителей Лагранжа ;.

Простая схема максимизации уравнения (28.6.15) заключается в использовании итерации с фиксированной точкой путем приравнивания производных свободной энергии Бете по параметрам q(xi , xj) к нулю, а также аналогично для множителей Лагранжа. Можно показать, что результирующий набор уравнений с фиксированной точкой при исключении q эквивалентен (ненаправленному) распространению веры \убеждений\ [299], для которого, в общем случае, узел xi передает сообщение узлу xj, используя
При сходимости предельное значение p(xi ) затем аппроксимируется формулой
, предиктор определяется путем нормализации. Для односвязного распределения p эта схема передачи сообщений сходится, и предельное значение соответствует точному результату. Для многосвязного (петлевого) распределения структуры, выполнение этого циклического Распространения Убеждений, как правило, приводит к приближению. Естественно, при желании мы можем обойтись без свободной энергии Бете и запустить соответствующий алгоритм циклического Распространения Убеждений непосредственно на неориентированном графе.

Сходимость петлевого распространения убеждений, которая может сильно зависеть от топологии графа, а также схемы обновления сообщений[291, 201]. Потенциальное преимущество концепции свободной энергии Бете заключается в том, что она дает представление о задаче, которую необходимо оптимизировать, открывая возможность применения более общих методов оптимизации, чем BP. Так называемые методы двойного цикла итеративно выделяют выпуклые вклады в Свободную энергию Бете, чередуясь с вогнутыми вкладами. На каждом этапе можно эффективно выполнять оптимизацию результатов[301, 133, 299].

Обоснованность зацикленного распространения убеждений
Для MRF, который имеет цикл, с точки зрения вычислений это означает, что возмущение переменной в цикле в конечном итоге отражается на той же переменной. Однако, если в цикле большое количество переменных, а отдельные соседние связи не все являются чрезвычайно сильными, численный эффект цикла невелик в том смысле, что влияние переменной на саму себя пренебрежимо мало. В таких случаях можно ожидать, что циклический аппроксимации BP должна быть точной. Область, пользующаяся особым успехом при построении логического вывода о Распространении Убеждений по Циклу используется для исправления ошибок, основанных на кодах проверки четности с низкой плотностью, которые разработаны с учетом этого свойства длинного цикла[183]. Однако во многих примерах, представляющих практический интерес (например, в MRF с взаимодействием ближайших соседей на решетке), циклы могут быть очень короткими. В таких случаях наивная реализация Loopy/Зацикленного BP завершится неудачей. Естественным расширением является кластеризация переменных для устранения некоторых проблем, возникающих из-за сильных локальных зависимостей; этот метод называется Кикути или методом Кластерных Вариаций [154]. Более подробная информация о способах кластеризации переменных могут быть рассмотрены с использованием региональных графов[299, 292].

Пример 117. В файле demoMFBPGibbs.m сравнивается эффективность наивной теории Преднего поля \MF,  Распространение Убеждений \BP\ и неструктурированная выборка Гиббса на основе маргинального вывода в попарной Марковской сети
в котором все переменные принимают 6 состояний. В эксперименте таблицы выбираются из однородного распределения, возведенного в степень ;. При ;, близком к нулю, все таблицы по существу являются плоскими, и поэтому переменные становятся независимая ситуация, для которой идеально подходят MF, BP и выборка Гиббса. При увеличении ; до
ЧЕРНОВИК от 9 марта 2010 г.  Распространение ожиданий 529

Исходный график
p-распределение
Факторизованный график
p-распределение
Рисунок 28.9: (а): Сеть Маркова (слева), для которой мы хотим аппроксимировать маргинальные значения p(w), p(x), p(y), p(z). Все таблицы построены на основе равномерного распределения, возведенного в степень ;. Справа показана факторизованная структура аппроксимации наивного среднего поля. (b): 64 = 1295 состояния распределения. Показано распределение с произвольной выборкой для ; = 5, которое имеет много изолированных пиков, что указывает на то, что распределение далеко не разложено на множители. В этом случае аппроксимации выборки MF и Гиббса могут оказаться неэффективными.  (c): При увеличении ; до 25, как правило, доминирует только одно состояние распределения. Смотрите демонстрацию demoMFBPGibbs.m.
Рисунок 28.10: (а): Многосвязный факторный граф, представляющий p(x). (b): Распределение математического ожидания приблизительно соответствует (а) в терминах управляемого факторного графа.   Открытые квадраты указывают на то, что факторы являются параметрами приближения. Базовая аппроксимация EP заключается в замене всех факторов в p(x) на коэффициенты произведения. (c): Древовидная структура EP.

5, зависимости между переменными увеличиваются, а методы работают хуже, особенно MF и Гиббса. При увеличении ; до 25 распределение становится резко максимальным вокруг одного состояния, так что апостериорное значение эффективно разложено на множители, см. рис. 28.9. Это говорит о том, что математическая аппроксимация (а также выборка Гиббса) должны работать хорошо. Однако вычисление этого состояния является сложной задачей, и оба метода часто застревают на локальных минимумах. Распространение убеждений, по-видимому, менее подвержено попаданию в ловушку локальных минимумов в этом режиме и, как правило, превосходит как MF, так и выборку Гиббса.
28.7 Распространение ожиданий
Сообщения в таких схемах, как распространение убеждений, не всегда могут быть представлены в компактной форме. Таким примером является Коммутационная Линейная Динамическая Система, глава (25), в которой для сообщений требуется экспоненциальный объем памяти. Это ограничивает использование BP такими случаями, как дискретные сети или, в более общем плане, демонстрационные семейные сообщения. Распространение Ожидаемого значения расширяет применимость BP к случаям, в которых сообщения не относятся к экспоненциальному семейству, путем проецирования сообщений обратно в экспоненциальное семейство на каждом этапе. Эта проекция получена с использованием меры Кульбака-Лейблера[195, 246, 197].

Рассмотрим распределение вида
В EP определяются те коэффициенты ;i (X ), которые, будучи заменены более простыми коэффициентами ~;i (X), сделали бы распределение ~p(x) приемлемым. Затем задаются любые свободные параметры ~;i (X) путем минимизации Куллбак-
530
ПРОЕКТ от 9 марта 2010 г. Распространение ожиданий
Лейблера дивергенции KL(p|~p). Например, рассмотрим попарную MRF
с помощью Факторного Графа, как показано на рис. 28.10, а). Если мы заменим все члены ;ij (xi , xj) на приближенные коэффициенты ~;ij (xi )~;ij (xj ), то результирующее совместное распределение ~p было бы разложено на множители и, следовательно, поддавалось бы корректировке. Поскольку переменная xi фигурирует более чем в одном члене p(x), нам нужно проиндексировать коэффициенты аппроксимации.  Удобным способом сделать это является
который представлен на рис. 28.10, б). Идея в EP теперь состоит в том, чтобы определить оптимальный член аппроксимации с помощью самосогласованного требования о том, что при замене его точной формой не будет никакой разницы с маргиналом ~p. Рассмотрим параметры аппроксимации ~;3;2 (x2 ) и ~;2;3 (x3 ). Чтобы установить их, мы сначала заменим вклад ~;3;2 (x2 ) ~;2;3 (x3 ) на ;(x2 , x3 ). Это дает
Теперь рассмотрим расхождение Кульбака-Лейблера между этим распределением и нашим приближением,
Поскольку наш интерес заключается в обновлении ~;3;2 (x2) и ~;2;3 (x3), мы выделяем вклад этих параметров в дивергенцию Кульбака-Лейблера, которая дает
Кроме того, поскольку ~p разложено на множители с точностью до постоянного коэффициента пропорциональности, зависимость ~Z  от  ~;3;2 (x2 ) и ~;2;3 (x3 ) равна
Дифференцируя уравнение дивергенции Кульбака-Лейблера (28.7.6) относительно ~;3;2 (x2 ) и приравнивая к нулю, получаем
Аналогично, оптимизация w.r.t. ~;2;3 (x3) дает
Эти уравнения определяют только коэффициенты аппроксимации с точностью до константы пропорциональности.  Поэтому мы можем записать оптимальные обновления в виде
и
ПРОЕКТ от 9 марта 2010 г. 531 Распространение ожиданий
, где z3;2 и z2;3 являются условиями пропорциональности. Мы можем определить пропорциональности, предъявляя требование, чтобы приближение члена ~;3;2 (x2 ) ~;2;3 (x3 ) оказывало такое же влияние на нормализацию ~p, как и на ~p; . То есть
, которые при подстановке в уравнение обновлений (28.7.10) и уравнение (28.7.11), сводящееся к
где
и
Любого выбора локальных нормировок z2;3, z3;2, удовлетворяющих уравнению (28.7.13), достаточно для обеспечения соответствия масштаба аппроксимации термина. Например, можно задать
После установки приблизительное значение глобальной константы нормализации p равно
Выше приведена процедура обновления терминов ~;3;2 (x2 ) и ~;2;3 (x3 ). Затем выбирается другой термин и заменяется его аппроксимацией до тех пор, пока параметры аппроксимации не будут сходиться.  Общая процедура описана в алгоритме(30).
Комментарии к EP
• В приведенном выше примере с MRF, EP соответствует Распространению Убеждений (форма суммарного произведения на факторном графе). Это интуитивно понятно, поскольку как в EP, так и в BP произведение сообщений, поступающих на переменную, пропорционально приближению предельного значения этой переменной. Однако разница заключается в схеме: в EP все сообщения, соответствующие приближению члена, обновляются одновременно (в приведенных выше случаях ~;3;2 (x2 ) и ~;2;3 (x3 )), тогда как в BP они обновляются в произвольном порядке.
• EP является полезным расширением BP для случаев, когда сообщения BP не могут быть легко представлены. В случае, когда аппроксимирующее распределение ~p относится к экспоненциальному семейству, минимальный критерий Кульбака-Лейблера соответствует совпадению моментов аппроксимирующего распределения с p;. Более подробное обсуждение приведено в [246].
• В общем случае нет необходимости заменять все члены в совместном распределении факторизованными приближениями. Нужно только, чтобы результирующее аппроксимирующее распределение было приемлемым \проходным; в результате получается алгоритм структурированного Распространения Математического Ожидания \EP, см. рис. (28.10в).
• EP и его расширения тесно связаны с другими вариационными процедурами, такими как древовидный перевес[287] и дробный EP[295], предназначенный для компенсации эффектов избыточного подсчета сообщений.
532 ПРОЕКТ MAP от 9 марта 2010 года для MRFs
 Алгоритм 30 Распространения математического ожидания: аппроксимация p(x) = Z1
1. Определите набор терминов ;i (Xi ) для замены на ;i (Xi ), чтобы получить приемлемое распределение
2: Инициализируем все параметры ;i (Xi ).
3: повторяем
4: Выберите параметр ;i (Xi ) из p для обновления.
5: Замените термин ;i (Xi ) на приемлемый термин ;i (Xi ), чтобы сформировать
6: Найдите параметры ;i (Xi) с помощью
где

7: Установить любые условия пропорциональности ;i (Xi ), требуя
8: пока не сходится
9: возвращает
в качестве приближения к p(x), где Z приблизительно соответствует константе нормализации
28.8 МАР для MRFs
Рассмотрим попарную MRF p(x) ;eE(x) при
, где i ~ j обозначает соседние переменные. Здесь члены f (xi , xj ) представляют попарные взаимодействия.  Термины g(xi,x0i ) представляют собой унарные взаимодействия, записанные для удобства в терминах попарного взаимодействия с фиксированным (неизменяемым) x0 . Обычно термин f (xi , xj ) используется для того, чтобы гарантировать, что соседние переменные xi и xj находятся в сходных состояниях; термин g(xi , x0i ) используется для того, чтобы приблизить xi к желаемому состоянию x0i . Такие модели имеют применение в таких областях, как компьютерное зрение и восстановление изображений, в которых требуется очистить изображение с заметными помехами x0, рис.28.3. Для этого мы ищем чистое изображение x, для которого значение каждого чистого пикселя xi близко к наблюдаемому значению зашумленного пикселя x0i, в то же время находясь в состоянии, аналогичном состоянию его чистых соседей.
28.8.1 Назначение МАР
Сопоставление набора переменных x1 , . . . , xD соответствует тому объединению x, которое максимизирует E(x). Для общей связности графа мы не можем наивно использовать интуицию динамического программирования, чтобы найти
Черновик 9 марта 2010 533MAP для MRFs

Рисунок 28.11: (a): Граф с двунаправленными весами wij = wji . (b): В разрезе графа узлы разделены на две группы S (синяя) и T (красная). Вес разреза равен сумме весов кромок от S (синий) до T (красный). Интуитивно понятно, что после присвоения узлам состояний 1 (для синего) и 0 (для красного) вес разреза соответствует суммарным весам соседних узлов в разных состояниях. Здесь мы увеличиваем эти весовые коэффициенты. Не выделенные края не влияют на вес среза. Обратите внимание, что на срез влияет только одно из направлений кромок\ разреза.

точное решение, поскольку график является закольцованным \зацикленным. Как мы увидим ниже, в особых случаях, даже если граф закольцован, это возможно. Однако в целом требуются приближенные алгоритмы.

Простое общее приближенное решение может быть найдено следующим образом: сначала произвольно инициализируем все x. Затем выбираем переменную xi и находим состояние xi, которое максимально улучшает E(x), сохраняя все остальные переменные неизменными.  Затем повторяем этот выбор и вычисление локального максимального состояния до сходимости. Это называется Итерацией Условных Режимов \Мод [36]. Из-за Марковских свойств ясно, что мы можем улучшить этот метод ICM, одновременно оптимизируя все переменные, обусловленные их соответствующими Марковскими параметрами (аналогично подходу, используемому в черно-белой выборке). Еще одним улучшением является обновление только подмножества переменных,  где подмножество имеет форму односвязной структуры. Рекурсивно фиксируя переменные, чтобы выявить односвязную структуру на несвязанных переменных, можно найти приближенное решение, решив последовательность решаемых задач.

Примечательно, что в частном случае бинарных переменных и положительного значения w, рассмотренном ниже, существует эффективный точный алгоритм для определения состояния карты независимо от топологии.
28.8.2 Привлекательные  бинарные MRFS
Рассмотрим поиск  MAP  MRF с двоичными переменными dom(xi ) = {0, 1} и положительными связями wij ; 0. В этом случае наша задача - найти задание x, которое максимизирует
, где i ~ j обозначает соседние переменные и действительный ci . Обратите внимание, что для двоичных переменных xi ; {0, 1},
Для этого конкретного случая существует эффективный алгоритм MAP для произвольной топологии w[121]. Алгоритм сначала преобразует задачу назначения MAP в эквивалентную задачу минимального s-t-разреза[39], для которой существуют эффективные алгоритмы. В минимальном разрезе нам понадобится граф с положительными весами на ребрах. Это условие, очевидно, выполняется, если wij > 0, хотя необходимо учитывать условия смещения ;i ci xi.

Работа с условиями смещения
Чтобы преобразовать задачу о назначении MAP в задачу о минимальном разрезе, нам нужно обращаться с дополнительными линейными членами ; i ci xi . Сначала рассмотрим эффект от включения нового узла x; и соединения его с каждым существующим узлом i с весом ci . Затем добавляется член
Если мы установим x; в состояние 1, то это добавит условия \члены
534 ПРОЕКТ от 9 марта 2010 года МАР для MRFs
Рисунок 28.12: (а): Граф с двунаправленными весами wij = wji, дополненный исходным узлом s и принимающим узлом t. Каждый узел имеет соответствующее смещение, знак которого указан. Узел-источник связан с узлами, соответствующими положительному смещению, а узлы с отрицательным смещением - с приемником. (b): В разрезе графа узлы разделены на две группы S (синяя) и T (красный), где S - объединение узла-источника и узлов в состоянии 1, T - объединение узла-приемника и узлов в состоянии 0. Вес разреза равен сумме вес кромок варьируется от S (синий) до T (красный). Красные линии указывают на вклад в разрез и могут рассматриваться как штрафные санкции, поскольку мы хотим найти минимальный разрез. Например, переменная a, находящаяся в состоянии 1 (синяя), не подвергается штрафу, поскольку ca > 0; с другой стороны, переменная f, находящаяся в состоянии 0 (красная), подвергается штрафу, поскольку cf > 0.

В противном случае, если мы установим x; в состояние 0, то получим
Поскольку наше требование заключается в том, что нам нужно, чтобы веса были положительными, мы видим, что можем достичь этого, определив два дополнительных узла. Мы определяем исходный узел xs , устанавливаем его в состояние 1 и соединяем его с теми xi , которые имеют положительный ci , определяя wsi = ci . Кроме того, мы определяем узел;приемник xt = 0 и соединяем все узлы с отрицательным значением ci с xt , используя вес wit = -ci (который, следовательно, является положительным).

Для узла-источника, привязанного к xs = 1, и узла-приемника к xt = 0, затем, включая источник и приемник, мы имеем
равно функции энергии, уравнение (28.8.2).
Определение 115 (Разрез графа). Для графа G с вершинами v1 , ... , vD и весами wij > 0 разрез — это разбиваем вершины на две непересекающиеся группы, называемые S и T. Вес разреза в этом случае определяется как сумма весов, которые исходят из S и попадают в T, см. рис.28.11.

Вес среза соответствует сумме весов между соседними участками, не совпадающими по размеру, см. рис. 28.11, б). То есть
срез(x) =
Поскольку I [xi ; xj ] = 1 ; I [xi = xj ], мы можем определить вес среза эквивалентно
ПРОЕКТ от 9 марта 2010 г. 535MAP для MRFs

Рисунок 28.13: (а): Чистое изображение. (b): Изображение с шумами. (c): Восстановленное изображение с помощью ICM. Смотрите демонстрацию demoMRFclean.m.

, чтобы назначение минимального вырезания соответствовало максимальному значению ;i~j wij I [xi = xj ]. В случае MRF для преобразования во взвешенный граф с положительными взаимодействиями требуется, чтобы мы обозначили источник и все другие переменные, присвоенные состоянию 1, с помощью S, а приемник и все переменные в состоянии 0 - с помощью T, см. рис.28.12. Фундаментальный результат состоит в том, что решение для минимального расхода \разреза s-t соответствует решению для максимального расхода от источника s до приемника t [39]. Существуют эффективные алгоритмы для определения максимального расхода, см., например, [47], которые требуют О( D3 ) операций или меньше. Это означает, что можно эффективно найти точное назначение МАР для привлекательного бинарного MRF за O( D3) операций. В MaxFlow.m мы реализуем метод Форда-Фалкерсона (первый вариант поиска по ширине Эдмондса-Карпдинича)[87], смотрите также упражнение(251).
Пример 118 (Анализ грязных изображений). На рис. 28.13 мы представляем зашумленное двоичное y-изображение, которое мы хотим очистить. Для этого мы используем объектив
Переменные xi , i = 1, . . . , 784 определены на сетке размером 28;28, где wij = 10, если xi и xj являются соседями в сетке. С помощью
у нас есть стандартная задача о бинарной MRF МАР с "смещением" b = 2y - 1. Затем мы можем найти точное оптимальное значение x с помощью процедуры минимального сокращения. Однако наша реализация этого происходит медленно, и вместо этого мы используем более простой алгоритм ICM с результатами, показанными на рис. 28.13.
28.8.3 Модель Поттса
Продолжение предыдущей модели является тот случай, когда переменные являются бинарными, который называется модели Поттса  :
где wij > 0 и значение x0i известны. Эта модель находит непосредственное применение при восстановлении недвоичных изображений, а также при кластеризации на основе оценки сходства. Хотя точный эффективный алгоритм неизвестен, полезным подходом является аппроксимация задачи в виде последовательности бинарных задач, как мы опишем ниже.
Перевод от Поттса к бинарному MRF
Рассмотрим представление ;-разложения
где si ; {0, 1} и для данного ; ; {0, 1, 2, . . . , N }. Это ограничивает xi либо состоянием xold i,
либо ;, в зависимости от двоичной переменной si . Таким образом, используя новую двоичную переменную s, мы можем ограничить x частью
536 ПРОЕКТ от 9 марта 2010 года  MAP для MRFs

Рисунок 28.14: (а): Изображение с помехами. (б): Восстановленное изображение. Был использован метод ;-разложения с подходящими взаимодействиями w и смещением c для обеспечения разумных результатов. Из [47].

из всего пространства и запишем новую целевую функцию только в терминах s:
для wij ` > 0. Эта новая задача имеет форму привлекательной бинарной MRF, которая может быть решена точно используя процедуру сокращения графа. Идея состоит в том, чтобы выбрать другое значение ; (случайным образом), а затем найти оптимальное значение s для нового ;. Таким образом, мы гарантированно итеративно увеличиваем E.

Для заданных значений ; и xold преобразование цели модели Поттса задается с помощью si ; {0, 1} и с учетом
при
и аналогичными определениями ai , bi . С помощью перечисления легко показать, что uij равно 0, 1 или 2. Используя математическое тождество
мы можем записать,
Следовательно, термины wij I [xi = xj ] переводятся как термины положительного взаимодействия I [si = sj ] wij uij /2. Все унарные термины легко и точно преобразуются в соответствующие унарные термины c`i si, где c`i определяется как сумма всех унарных терминов в si . Это показывает, что положительное взаимодействие wij в терминах исходных переменных x соответствует положительному взаимодействию в новых переменных s. Следовательно, мы можем найти максимальное состояние s, используя алгоритм сокращения графа. Схожая (хотя и отличающаяся) процедура описана в [48].
ПРОЕКТ от 9 марта 2010 г. 537 Упражнения
Пример 119 (модель Поттса для реконструкции изображения). Пример задачи восстановления изображения для взаимодействия ближайших соседей на пиксельной решетке и надлежащим образом выбранных w, c приведен на рис. (28.14). Изображения представлены карта является недвоичной, и, следовательно, оптимальное назначение МАР не может быть точно вычислено эффективным способом. Здесь был использован метод альфа-расширения в сочетании с эффективным методом минимального сокращения, подробности см. в [47].
28.9 Дальнейшее Чтение
Приближенный логический вывод является весьма активной исследовательской областью, и все чаще разрабатываются ссылки на выпуклую оптимизацию [46]. Общий обзор см. в [287], а недавнее применение выпуклой оптимизации для приближенного логического вывода в практическом приложении машинного обучения - в [247].
28.10 Код
LoopyBP.m: Циклическое распространение убеждений (формализм факторных графов)
demoLoopyBP.m: Демонстрация закольцованного распространения
представлений, демонстрация Гиббса.m: Сравнение среднего поля, распространения представлений и выборки
Gibbs.m: Демонстрация анализа грязной картины
MaxFlow.m: Алгоритм минимального сокращения максимального расхода (Ford-Fulkerson)
binaryMRFmap.m: Оптимизация двоичного MRF-файла
28.11 Упражнения
Упражнение 251. Для задачи максимального расхода с минимальным сокращением, в соответствии с соглашением о том, что исходный узел xs привязан к состоянию 1, а узел-приемник xt - к состоянию 0, стандартный алгоритм минимального сокращения возвращает то соединение x, которое минимизирует
Объясните, как это можно записать в форме
Упражнение 252. Используя BRMLtoolbox, напишите процедуру KLdiv(q,p), которая возвращает разницу Кульбака- Лейблера между двумя дискретными распределениями q и p, определенными как потенциалы q и p.
Упражнение 253. Файл p.mat содержит распределение p(x, y, z) по троичным переменным состояния. Используя BRML- toolbox, найдите наилучшее приближение q(x, y)q(z), которое минимизирует расхождение Кульбака-Лейблера KL(q|p). и укажите значение минимальной дивергенции Кульбака-Лейблера для оптимального q.
Упражнение 254. Рассмотрим попарную MRF, определенную на решетке 2 ; 2, как указано в pMRF.mat. С помощью ящика для инструментов BRMLtoolbox,

1. Найдите оптимальное полностью факторизованное приближение ; 4i = 1 qiBP с помощью заЦиклического Распространения Убеждений, основанного на формализме факторного графа.
Q
2. Найдите оптимальное, полностью разложенное на множители приближение ; 4i = 1 qiMF, решив уравнения вариационного среднего поля.
3. Путем простого перечисления вычислите точные предельные значения pi .
538 ЧЕРНОВИК от 9 марта 2010 года Упражнения
4. В среднем по всем 4 переменным вычислите среднее ожидаемое отклонение в предельных значениях
для аппроксимации BP и MF и прокомментируйте свои результаты.
Упражнение 255. В LoopyBP.m расписание сообщений выбирается случайным образом. Измените процедуру, чтобы выбрать расписание \схему, используя последовательность прямого и обратного исключения на случайном связующем дереве.
Упражнение 256 (Границы Двойного Интегрирования). Рассмотрим границу
Тогда для
Покажем, что:
1.
2.
где
Значимость заключается в том, что это двойное интегрирование (или суммирование в случае дискретных переменных) является общей процедурой для получения новой оценки из существующей оценки [172].
Упражнение 257. Начиная с
и, используя процедуру двойного интегрирования, покажем, что
1. Заменив x ; sT Ws на s ; {0, 1}D и a ; hT s, получим оценку статистической суммы распределения Больцмана
2. Покажите, что эта граница эквивалентна границе среднего поля для статистической функции.
3. Обсудите, как можно получить более строгие оценки статистической суммы распределения Больцмана путем дальнейшего применения процедуры двойного интегрирования.
Упражнение 258. Рассмотрим попарную MRF
для симметричного W. Рассмотрим разложение
, где 0 ; qi ; 1 и ;i qi = 1, а граф каждой матрицы Wi представляет собой дерево. Объясните, как определить верхнюю границу для нормализации Z, и обсудите наивный метод нахождения наиболее точной верхней границы.
ЧЕРНОВИК от 9 марта 2010 г. 539 Упражнения
Упражнение 259. Выведите оценку Линксера для взаимной информации, уравнение (28.5.15).
Упражнение 260. Рассмотрим среднее значение положительной функции f (x) относительно распределения p(x).
, где f (x) ; 0. Простейший вариант неравенства Дженсена гласит, что
1. Рассматривая распределение r(x) ; p(x) f (x) и KL(q|r) для некоторого вариационного распределения q(x), покажите, что
Граница насыщается, когда q(x) ;p(x)f (x). Это показывает, что если мы хотим приблизить среднее значение J, оптимальный выбор аппроксимирующего распределения зависит как от распределения p(x), так и от подынтегрального выражения f (x).
2. Кроме того, покажите, что
где H(q(x)) - энтропия q(x). Первый член указывает на то, что q близко к p. Второй указывает на то, что q близко к f, а третий указывает на то, что q резко возрастает.
Упражнение 261. Для Марковского Случайного поля с D двоичными переменными xi ; {0, 1}, i = 1, . . . , D мы определяем
покажем, что
где
и объясните, почему для оценки предельного значения p (xi ) требуются как верхняя, так и нижняя границы статистических функций.
Упражнение 262. Рассмотрим ориентированный граф, в котором пропускная способность ребра x ; y равна c(x, y) ; 0. Поток на ребре f (x, y) ; 0 не должен превышать пропускную способность ребра. Цель состоит в том, чтобы максимизировать поток от определенного узла-источника s к определенному узлу-получателю t. Кроме того, поток должен быть сохранен таким образом, чтобы для любого узла, отличного от источника или приемника (y; s, t),
Разрез определяется как разбиение узлов на два непересекающихся множества S и T таким образом, что s находится в S , а t - в T . Показывать что:
1. Чистый поток из s в t, значение val(f ) совпадает с чистым потоком из S в T :


2. val(f ) ;;x;S,y;Tf(x,y), а именно, что поток ограничен сверху пропускной способностью разреза.

ЧЕРНОВИК от 9 марта 2010 г. 540  упражнений

Теорема о максимальном расходе и минимальном разрезе также утверждает, что максимальный расход фактически равен пропускной способности разреза.
Упражнение 263 (перевод от Поттса к Изингу). Рассмотрим функцию E(x), определенную для множества переменных с несколькими состояниями dom(xi ) = {0, 1, 2, . . . , N},
, где wij > 0, известны наблюдаемые состояния пикселей x0i и ci . Наш интерес заключается в том, чтобы найти приблизительную максимизацию E(x). Используя ограниченный параметр
где si ; {0, 1} и для заданного ; ; {0, 1, 2, . . . , N } покажите, как записать E(x) как функцию двоичных переменных
для  wij`> 0. Эта новая задача имеет форму привлекательной бинарной MRF, которая может быть решена точно с помощью процедуры сокращения графа.
Упражнение 264. Рассмотрим аппроксимирующее распределение в экспоненциальном семействе,
Мы хотим использовать q(x) для аппроксимации распределения p (x) с использованием дивергенции KL
1. Покажите, что оптимально
2. Покажите, что гауссиану можно записать в экспоненциальной форме
где g1 (x) = x, g2 (x) = x2 и соответствующим образом выбранное ;.
3. Следовательно, покажем, что оптимальное гауссово соответствие q(x)=N (x| µ, ;2) любому распределению в минимальном смысле KL(p|q) соответствует моментам:

Упражнение 265. Мы хотим найти гауссово приближение q (x) = N( x |m, s2 ) к распределению p (x). Показывать что
Запишите расхождение KL в явном виде как функцию от m и s2 и подтвердите общий результат, что оптимальные m и s2, которые минимизируют KL(p|q), задаются путем приведения среднего значения и дисперсии q к значениям p.
ЧЕРНОВИК от 9 марта 2010 г. 541 Упражнения
Упражнение 266. Для попарного бинарного марковского случайного поля p с функцией разбиения
показывает, что среднее значение может быть вычислено с помощью
и что аналогично ковариация задается формулой
Упражнение 267. Теория наивного среднего поля, примененная к попарной MRF
dom(xi ) = {0, 1}, дает факторизованную аппроксимацию q(x) =;i q(xi ) , основываясь на минимизации KL(q|p). С помощью
таким образом, мы можем аппроксимировать
Чтобы получить лучшее, нефакторизованное приближение к <xi xj >p, мы могли бы использовать нефакторизованный q. Также может быть использован метод линейного отклика[153], основанный на разложении свободной энергии по возмущениям. В качестве альтернативы рассмотрим соотношение
Показывать что
Объясните, как использовать модифицированный метод наивного среднего поля для нахождения нефакторизованного приближения к <xi xj >p .
Упражнение 268. Выведите уравнение обновления EP (28.7.8) и уравнение (28.7.9).
Упражнение 269. Вам дается набор точек данных, обозначенных от 1 до N, и "показатель сходства" wij ; 0, i, j =1, ... , N, который обозначает сходство точек i и j. Вы хотите присвоить каждой точке данных кластерный индекс cn ; {1, . . . , K}. Для подмножества точек данных вы предпочитаете кластерный индекс. Объяснять как использовать модель Поттса для формулирования целевой функции для этой "полууправляемой" задачи кластеризации.
542 ЧЕРНОВИК от 9 марта 2010 г. ПРИЛОЖЕНИЕ
A