Глава 6
Алгоритм построения дерева соединений
6.1Переменные кластеризации
В главе (5) мы обсуждали эффективный логический вывод для односвязных графов, для которых подходят схемы исключения переменных и передачи сообщений. Однако в случае многосвязных графов, невозможно в общие положениях выполнить логический вывод, передавая сообщения только по существующим ссылкам в графе. Идея алгоритма дерева соединений \отбросов\ заключается в формировании нового представления графа, в котором переменные сгруппированы вместе, что приводит к односвязному графу в кластере переменных (хотя и на другом графе). Основное внимание при разработке будет уделено предельному \маржинальному, деловому\ выводу, хотя аналогичные методы применимы и для вывода различий, например, для нахождения максимального состояния распределения.
На данном этапе важно отметить, что алгоритм дерева соединений не является волшебным методом, чтобы разбирайться с трудноразрешимыми задачами, возникающими при работе с многосвязными графами; это просто способ выполнить корректный вывод на многосвязном графе путем преобразования в односвязную структуру. Выполнение вывода на результирующем дереве соединений все еще может быть трудноразрешимым с точки зрения вычислений. Например, представление дерева соединений общей двумерной модели Изинга представляет собой один суперузел, содержащий все переменные. В этом случае логический вывод экспоненциально усложняется из-за количества переменных. Тем не менее, даже в тех случаях, когда реализация JTA (или любого другого алгоритма точного вывода) может оказаться трудноразрешимой, JTA предоставляет полезную информацию о представлении распределений, которая может послужить основой для приблизительного вывода. В этом смысле JTA является ключом к пониманию проблем, связанных с представлениями и сложностью логического вывода, и занимает центральное место в разработке эффективных алгоритмов логического вывода.
6.1.1 Повторная параметризация
Рассмотрим цепочку
p(a, b, c, d) = p(a|b)p(b|c)p(c|d)p(d) (6.1.1)
Используя правило Байеса, мы можем переформулировать это как
Полезная информация заключается в том, что распределение, таким образом, может быть записано как произведение предельных распределений, деленное на произведение пересечения предельных распределений: если посмотреть на числитель p(a, b)p(b, c)p(c, d), то это не может быть распределением по a, b, c, d, поскольку мы пересчитываем значения b и c, где это пересечение значений b возникает из-за перекрытия множеств a, b и b, c, пересечение которых имеет значение b. Аналогично, перерасчет c возникает из-за перекрытия множеств b, c и c, d . Грубо говоря, нам нужно исправить этот перерасчет, разделив его на распределение по пересечениям. Учитывая преобразованное представление, предельное значение, такое как p(a, b), может быть вычислено непосредственно из коэффициентов в новом выражении.
85 Кликовы графы
Рисунок 6.1: (a) сеть Маркова ;(a, b, c);(b, c, d). (b) Эквивалентный граф клика (a).
Целью алгоритма дерева соединений является формирование представления распределения, которое явно содержит маргиналы. Мы хотим сделать это таким образом, чтобы это работало для сетей веры \уверений\ и Маркова, а также для многосвязного случая. Для этого подходящим способом параметризации распределения является использование графа клик, как описано в следующем разделе.
6.2 Графы с кликами
Определение 39 (Граф с кликами). Граф с кликами состоит из набора потенциалов, ;1 (X 1 ), . . . , ;n (X n ) каждый определенный на множестве переменных Xi . Для соседних кликов на графике, определенных на множествах переменных Xi и Xj , точка пересечения Xs = Xi ; Xj называется разделителем и имеет соответствующий потенциал ;s (Xs ). Граф клики представляет функцию
Для простоты обозначения мы обычно опускаем индекс потенциала клики c. Графически потенциалы клик представлены кружками/овалами, а потенциалы разделителей - квадратами.
Граф слева представляет собой ;(X 1 );(X 2 )/;(X 1 ; X 2 ).
Кликовые графики преобразуют марковские сети в структуры, удобные для выполнения логического вывода. Рассмотрим марковскую сеть на рис. 6.1, а
которая содержит два кликовых потенциала, разделяющих переменные b, c. Эквивалентное представление дает граф клик на рис. (6.1, б), определяемый как произведение потенциалов клик числителя, разделенное на произведение потенциалов разделителей. В этом случае потенциал сепаратора может быть установлен на нормируемую постоянную Z. Суммируя, мы получаем
Умножив эти два выражения, получим
Другими словами
86 ЧЕРНОВИК от 9 марта 2010 года Граф кликов
Важным наблюдением является то, что распределение может быть записано в терминах его предельных значений для переменных в исходных кликах и что в виде графа клик оно имеет ту же структуру, что и раньше. Все, что изменилось заключается в том, что исходные потенциалы клик были заменены предельными значениями распределения, а разделитель - предельным значением, определенным для переменных-разделителей ;(a, b, c) ; p(a, b, c), ;(b, c, d) ; p(b, c, d), Z ; p(c, b). Полезность этого представления заключается в том, что если нас интересует предельное значение p (a, b, c), то это можно определить по преобразованному потенциалу клики. Чтобы использовать это представление, нам требуется
систематический способ преобразования потенциалов графа клик таким образом, чтобы в конце преобразования новые потенциалы содержали маргиналы распределения.
Замечание 7. Обратите внимание, что, несмотря на визуальное сходство, факторный граф и Кликовый граф представляют собой разные представления. В кликовом графе узлы содержат наборы переменных, которые могут совместно использовать переменные с другими узлами.
6.2.1 Поглощение
Рассмотрим соседние клики V и W, совместно использующие переменные S. В этом случае распределение по переменным X = V U W равно
и наша цель состоит в том, чтобы найти новое представление
в котором потенциалы задаются как
В этом примере мы можем явно вычислить новые потенциалы как функцию старых потенциалов, вычислив маргиналы следующим образом:
и
В двух приведенных выше уравнениях присутствует симметрия – они одинаковы при замене V и W. Один из способов описания этих уравнений - через ‘поглощение’. Мы говорим, что кластер W "поглощает" информацию из кластера V с помощью следующей процедуры обновления. Сначала мы определяем новый разделитель
и уточняем потенциал W, используя
Преимущество этой интерпретации состоит в том, что новое представление по-прежнему является корректным представлением распределения в виде графа клик, поскольку
ПРОЕКТ от 9 марта 2010 87 Деревья сброса Деревья соединений
Рисунок 6.2: Пример расписания приема в дереве кликов. Существует множество допустимых расписаний, при условии, что сообщения могут быть переданы соседу только
после получения всех остальных сообщений.
Если после того, как W поглотит информацию из V, то ; ; (W) будет содержать предельный p(W). Аналогично, после того, как V поглотит информацию из W, то ; ; (V) будет содержать предельный p(V). После того как сепаратор S примет участие в поглощение в обоих направлениях, то потенциал разделителя будет содержать p(S) (это не так после однократного поглощения). Чтобы убедиться в этом, рассмотрим
Продолжая, у нас есть новый потенциал ; * (V) данный
Определение 40 (Поглощение).
Пусть V и W - соседи в графе клик, пусть S — их разделитель, а ; (V), ; (W) и ; (S) - их потенциалы. Поглощения от V к W через S заменяют таблицы ;; (S) и ; * (W) при
Мы говорим, что группа \клика\ W поглощает информацию из группы V.
6.2.2 График\расписание\ поглощения на деревьях кликов
Определив подход к локальному распространению сообщений, нам нужно определить порядок обновления для обработки \ поглощения. В общем, узел V может отправить ровно одно сообщение соседнему узлу W, и оно может быть отправлено только тогда, когда V получил сообщение от каждого из своих соседей. Мы продолжаем эту последовательность поглощений до тех пор, пока по каждому каналу связи было передано сообщение в обоих направлениях. См., например, рис. 6.2. Обратите внимание, что схема передачи сообщений не является уникальной.
Определение 41 (График обработки\поглощения). Клика может отправить сообщение соседу при условии, что она уже получила сообщения от всех других соседей.
6.3 Деревья соединений
Есть несколько этапов, которые нам необходимо пройти, чтобы преобразовать распределение в подходящую структуру для логического вывода. Сначала мы объясним, как это сделать для односвязных конструкций, прежде чем переходить к
88 ПРОЕКТ от 9 марта 2010 г. Деревья соединений
Рисунок 6.3: (а): Односвязная сеть Маркова. (б): Граф клик. (в): Дерево клик.
многосвязному случаю.
Рассмотрим односвязную сеть Маркова, рис.6.3а)
Граф клик этой односвязной марковской сети является многосвязным, рис.6.3, б, где все разделяющие потенциалы равны единице. Тем не менее, давайте попробуем переформулировать марковскую сеть в терминах маргиналов. Сначала у нас есть соотношения
Взяв произведение трех маргинальных чисел, получим
Это означает, что сеть Маркова может быть выражена в терминах маргиналов как
Следовательно, допустимый граф клик также представлен на рисунке (6.3c). Действительно, если переменная (здесь x4 ) встречается на каждом разделителе в цикле графа кликов, можно удалить эту переменную из произвольно выбранного разделителя в цикле. В результате остается пустой разделитель, который мы можем просто удалить. Это показывает, что в таких случаях мы можем преобразовать граф клик в дерево клик (т.е. односвязный граф клик). При условии, что исходная марковская сеть односвязна, всегда можно сформировать дерево клик таким образом.
6.3.1 Свойство текущего пересечения
Следуя приведенному выше примеру, рассмотрим дерево кликов на рис. 6.3.
ЧЕРНОВИК от 9 марта 2010 89 Деревья соединений\ пересечений
как представление распределения (6.3.1), где мы устанавливаем ;1 (x4 ) = ;2 (x4 ) = 1, чтобы получить это соответствие. Теперь выполняем поглощение в этом дереве кликов:
Мы поглощаем (x3 , x4 ) ~;(x1 , x4 ). Новый разделитель
, и новый потенциал заключается в
Теперь (x1 , x4 ) ~;(x2 , x4 ). Новый разделитель
и новый потенциал равен
Поскольку мы "исчерпали буферы" с точки зрения передачи сообщений, потенциал ;(x2 , x4 ) не может быть обновлен в дальнейшем. Давайте более внимательно рассмотрим значение этого нового потенциала,
Следовательно, новый потенциал ;; (x2 , x4 ) содержит предельное значение p(x2 , x4).
Чтобы завершить полный цикл передачи сообщений, нам нужно, чтобы сообщения передавались по действующему расписанию в обоих направлениях каждого разделителя. Для этого мы продолжим следующим образом:
Мы поглощаем (x2 , x4 ) ~;(x1 , x4 ). Новый разделитель равен
и
Заметим, что ;;; 2 (x4 ) =; x2 ;* (x2 , x4 ) = ;x2 p(x2 , x4 ) = p(x4 ), так что теперь, после поглощения через оба в этом случае разделитель содержит предельное значение p(x4 ). Читатель может показать, что ;;; (x1 , x4 ) = p(x1 , x4 ).
Наконец, мы поглощаем (x1 , x4 )~; (x3 , x4 ). Новый разделитель имеет вид
и
Следовательно, после полного цикла передачи сообщений все новые потенциалы содержат правильные поля на полях.
90 ПРОЕКТ от 9 марта 2010 г. Деревья соединений
Новое представление является последовательным \содержательным\ в том смысле, что для любых (не обязательно соседних) клик V и W с пересечением I и соответствующими потенциалами ;(V) и ; (W),
Обратите внимание, что двунаправленное поглощение гарантирует согласованность для соседних клик, как в примере выше, при условии, что мы начали с дерева клик, которое является правильным представлением распределения.
В общем, единственным возможным источником несогласованности является то, что переменная встречается в двух не соседних кликах и не присутствует во всех кликах на любом пути, соединяющем их. Крайним примером может быть, если мы удалили связь между кликами (x3 , x4 ) и (x1 , x4 ). В этом случае это все еще дерево клик; однако глобальная согласованность не может быть гарантирована, поскольку информация, необходимая для согласования клик (x3 , x4 ) с остальной частью графа, не может быть получена в этой клике.
Формально, условием для перехода от локальной согласованности к глобальной является то, что дерево кликов является соединительным деревом, как определено ниже.
Определение 42 (Дерево соединений). Дерево кликов является соединительным деревом, если для каждой пары узлов V и W, все узлы на пути между V и W содержат пересечение V ; W. Это также называется свойством текущего пересечения.
Из этого определения локальная согласованность будет передаваться всем соседним узлам, и распределение будет глобально согласованным. Доказательства этих результатов содержатся в [148].
Пример 22 (Непротиворечивое дерево соединений). Чтобы получить некоторое представление о значении непротиворечивости, рассмотрим дерево соединений на рис. 6.4, г). После полного цикла передачи сообщений по этому дереву каждая ссылка непротиворечиво, и произведение потенциалов, разделенное на произведение потенциалов-разделителей, является самим исходным распределением. Представьте, что мы заинтересованы в вычислении предельного значения для узла abc. Для этого требуется суммировать все остальные переменные, defgh. Если мы рассмотрим суммирование по h, то, поскольку связь непротиворечива \содержательна,
так, что отношение ;h ;;(e,h)/ ;;(e) равно единице, и результат суммирования по узлу h заключается в том, что связь между eh и dce может быть удалена вместе с разделителем. То же самое происходит для связи между узлом eg и dce, а также для преобразования cf в abc. Теперь остались только узлы dce и abc и их разделитель c, на которые суммирование пока не повлияло. Нам все равно нужно суммировать по d и e. Опять же, потому что связь непротиворечива,
, так что соотношение ;de ;;(d,c,e)/ ;;(c) = 1. Следовательно, результат суммирования всех переменных, не входящих в abc, дает единицу для клик и их разделителей, а суммированное представление потенциала сводится просто к потенциалу ; ; (a, b, c), который является предельным значением p(a, b, c). Понятно, что подобный эффект будет это может произойти и с другими узлами. Затем мы можем получить предельные значения для отдельных переменных P простым грубым сильным суммированием по другим переменным в этом потенциале, например, p(f ) = ;c ; ; (c, f ).
ЧЕРНОВИК от 9 марта 2010 г. 91. Построение дерева соединений для односвязных распределений
6.4 Построение дерева связей для односвязных распределений
6.4.1 Морализация
Для сетей убеждений требуется начальный шаг, который не требуется в случае неориентированных графов.
Определение 43 (Морализация). Для каждой переменной x добавьте ненаправленную связку между всеми родительскими элементами x и замените направленную связку от x к ее родительским элементам ненаправленными ссылками \связками. Это создает ‘морализированную’ марковскую сеть.
6.4.2 Формирование графа клик
Граф клик формируется путем идентификации клик в сети Маркова и добавления связки между кликами, которые имеют непустое пересечение. Добавьте разделитель между пересекающимися кликами.
6.4.3 Формирование дерева связей \промежуточных вычислений\ из графа клик
Для односвязного распределения любое остовное дерево с максимальным весом в графе клик является деревом связей \промежуточных вычислений.
Определение 44 (Дерево соединений). Дерево соединений получается путем нахождения остовного \ вонючего с мухами\ дерева с максимальным весом в графе клик. Вес дерева определяется как сумма весов всех разделителей дерева, где вес разделителя - это количество переменных в разделителе.
Если граф кликов содержит циклы, то все разделители в цикле содержат одну и ту же переменную. Продолжая удалять ссылки\ связки\ на циклы до тех пор, пока не будет обнаружено дерево, мы получим дерево соединений\ мусора, отбросов\.
Пример 23 (Формирование дерева соединений \отбросов). Рассмотрим сеть убеждений\ уверений, представленную на рис. 6.4, а). Процедура морализаторства представлена на рис.6.4, б). Идентификация групп на этом графе и их объединение дают граф групп \клик\ на рис.6.4,в). Существует несколько возможных деревьев пересечений\ отбросов\, которые можно было бы получить из этого графа клик, и одно из них приведено на рис. 6.4d).
6.4.4 Распределение потенциалов по группам
Определение 45 (Назначение Потенциалов по группам\кликам). Задано дерево соединений и функция, определенная как произведение набора потенциалов ; (X 1 ), . . . , ; (X n ), допустимое назначение потенциала клики помещающее потенциалы в JT клики, переменные которых могут содержать их, таким образом, что произведение потенциалов клик JT, деленное на потенциалы JT-разделителя, равно (этой) функции.
Простой способ выполнить это задание - составить список всех потенциалов и произвольно упорядочить JT-клики. Затем для каждого потенциала выполнить поиск по JT-кликам, пока не встретите первую, для которой переменные потенциала являются подмножеством переменных JT-клики. Затем потенциал каждой JT-клики берется как произведение всех потенциалов клики, присвоенных JT-клике. Наконец, мы присваиваем всем JT-разделителям значение единицы \юнита. Этот подход используется в jtassignpot.m.
92 ЧЕРНОВИК от 9 марта 2010 г. Деревья соединений для многосвязных распределений
Рисунок 6.4: (а): Сеть убеждений. (b): Морализированная версия (а). (c): Граф группировок (b). (d): Дерево пересечений \отбросов. Это удовлетворяет свойству текущего пересечения, согласно которому для любых двух узлов, содержащих общую переменную, любая клика на пути, соединяющем эти два узла, также содержит эту переменную.
Пример 24. Для сети убеждений, представленной на рис.6.4, а), мы хотим присвоить ее потенциалы дереву соединений, представленному на рис.6.4, d). В этом случае назначение уникально и задается формулой
Все разделительные потенциалы инициализируются единицей. Обратите внимание, что в некоторых случаях клика дерева соединений присваивается единице.
6.5 Деревья соединений для многосвязных распределений
Если распределение содержит циклы, конструкция, описанная в разделе (6.4), не приводит к созданию дерева соединений. Причина в том, что из-за циклов устранение переменной изменяет структуру оставшегося графа. Чтобы убедиться в этом, рассмотрим следующее распределение:
p(a, b, c, d) = ;(a, b);(b, c);(c, d);(d, a) (6.5.1)
как показано на рис. 6.5, а). Давайте сначала попробуем построить граф клик. У нас есть выбор, какую переменную сначала выделить. Давайте выберем d:
ПРОЕКТ от 9 марта 2010 г. 93 Деревья соединений для многосвязных распределений
Рисунок 6.5: (a): Неориентированный граф с циклом. (b): Удаление узла d добавляет связь между a и c в подграфе. (c): Индуцированное представление для графа в (a). (d): Эквивалентное индуцированное представление. (e): Дерево соединений для (a).
Следовательно, оставшийся подграф имеет дополнительную связь между a и c, см. рис. 6.5, б). Мы можем выразить это соединение в терминах полей, используя
Чтобы продолжить преобразование в маргинальную форму, давайте попробуем заменить члены числителя на вероятностные возможности \вероятности. Мы можем сделать это, рассмотрев
Подключив это к приведенному выше уравнению, мы получим
Мы понимаем, что знаменатель - это просто p(a, c), следовательно
Это означает, что допустимый граф клик для распределения, показанного на рис.6.5, а, должен содержать клики, превышающие количество клик в исходном распределении. Для формирования JT на основе произведений клик, разделенных на произведения разделителей, мы могли бы начать с индуцированного представления на рис. 6.5в). В качестве альтернативы, мы могли бы выделить переменные a и c и в итоге получить эквивалентное представление на рис.6.5d).
Как правило, результатом исключения переменных и повторного представления в терминах индуцированного графа является добавление связи между любыми двумя переменными в цикле (длиной 4 или более), который не имеет хорды. Это называется триангуляцией. Марковская сеть на триангулированном графе всегда может быть записана в терминах произведение маргиналов, разделенных на произведение разделителей. Вооружившись этим новым индуцированным представлением, мы можем сформировать дерево соединений.
Рис.6.6: (а) Петлевидной "лестницы" Сеть Маркова. (б) Индуцированное представление.
ЧЕРНОВИК от 9 марта 2010 г. Деревья соединений для многосвязных распределений
Рисунок 6.7: (а): Сеть Маркова, для которой мы ищем триангуляцию с помощью исключения жадных переменных. Мы сначала исключаем упрощенные узлы a, e, l. (b): Затем мы исключаем переменные b, d, поскольку они добавляют только одну дополнительную ссылку к индуцированному графу. (c): f и i теперь являются упрощенными и исключаются. (d): Мы исключаем g и h, поскольку это добавляет только отдельные дополнительные ссылки. (e): Остальные переменные {c, j, k} могут быть исключены в любом порядке. (f): Окончательная триангуляция. Порядок исключения переменных (частичный) таков: {a, e, l} , {b, d} , {f, i} , {g, h} , {c, j, k}, где скобки указывают на порядок, в котором переменные значения, указанные в скобках, не имеют значения. По сравнению с триангуляцией, полученной с помощью метода проверки максимальной мощности, показанного на рис. 6.9, d, эта триангуляция более экономична.
Пример 25. Несколько более сложное петлевидное распределение показано на рис. 6.6а,
где
p(a, b, c, d, e, f) = ;(a, b);(b, c);(c, d);(d, e);(e, f);(a, f);(b, e) (6.5.7)
Существуют различные индуцированные представления, зависящие от того, какие переменные мы решили исключить. Читатель может убедиться, что одно из таких индуцированных представлений представлено на рис. 6.6, б).
Определение 46 (Хорда). Это ссылка, соединяющая две непоследовательные вершины цикла.
Определение 47 (Триангулированный (декомпозируемый) граф). Неориентированный граф называется триангулированным, если каждая петля длиной 4 или более имеет хорду. Эквивалентным термином является то, что граф является разложимым или хордовым. Неориентированный граф является триангулированным тогда и только тогда, когда его кликовый граф имеет дерево соединений.
6.5.1 Алгоритмы триангуляции
Когда переменная исключается из графа, добавляются связи между всеми соседями исключенной переменной. Алгоритм триангуляции - это алгоритм, который создает граф, для которого существует порядок исключения переменной, который не приводит к появлению дополнительных связок в графе.
ЧЕРНОВИК от 9 марта 2010 г. 95 Деревья соединений для многосвязных распределений
Рисунок 6.8: Дерево пересечений \отбросов, сформированное на основе триангуляционного
рисунка(6.7)f. Необходимо убедиться, что оно удовлетворяет свойству текущего пересечения.
Для дискретных переменных сложность вывода экспоненциально возрастает в зависимости от размеров клик в триангулированном графе, поскольку поглощение требует вычисления таблиц для клик. Поэтому представляет определенный интерес найти триангулированный граф с небольшими размерами клик. Однако поиск триангулированного графа с наименьшей максимальной кликой является NP-сложной задачей для общего графа, и эвристика неизбежна. Ниже мы опишем два простых алгоритма, которые в целом приемлемы, хотя могут быть случаи, когда альтернативный алгоритм может быть значительно более эффективным [53, 28, 191].
Замечание 8 (Триангуляция не означает размещение ‘треугольников’ на исходном графике). Обратите внимание, что триангулированный граф - это не тот граф, в котором "квадраты в исходном графе имеют треугольники внутри них в триангулированном графе". Хотя это относится к рис. 6.6b, это не относится к рис. 6.9d). Термин "триангуляция" относится к тому факту, что каждый "квадрат" (т.е. цикл длиной 4) должен иметь "треугольник", ребра которого добавляются до тех пор, пока не будет удовлетворен этот критерий.
Исключение жадных переменных
Интуитивно понятный способ представить себе триангуляцию состоит в том, чтобы сначала начать с простоватых узлов, а именно с тех, которые при удалении не создают никаких дополнительных связок в оставшемся графе. Далее рассмотрим непростой узел из оставшегося графа, который имеет минимальное количество соседей. Затем добавьте связку между всеми соседями этого узла и, наконец, удалите этот узел из графа. Продолжайте, пока не будут удалены все узлы. (Эта процедура соответствует исключению Роуза-Тарьяна[233] с выбором конкретного узла для исключения). Помечая последовательно удаляемые узлы, мы получаем идеальный порядок (см. ниже) в обратном порядке. В случае, когда (дискретные) переменные имеют разное количество состояний, более усовершенствованным вариантом является выбор непростой узел i, который при удалении оставляет наименьший размер таблицы кликов (произведение размеров всех состояний соседних узлов i). Пример приведен на рис. 6.7.
Определение 48 (Исключение переменной). При исключении переменных просто выбирается любой не удаленный узел x в графе, а затем добавляются ссылки на все соседние узлы x. Затем узел x удаляется. Это повторяется до тех пор, пока не будут удалены все узлы[233].
Хотя эта процедура гарантирует получение триангулированного графа, ее эффективность в значительной степени зависит от последовательности узлов, выбранных для исключения. Для этого было предложено несколько эвристических методов, включая приведенный ниже, который соответствует выбору x в качестве узла с минимальным количеством соседей.
Проверка максимальной мощности
Алгоритм (2) завершается успешно, если граф триангулирован. Это не только достаточное условие для триангуляции графа, но и необходимое [271]. При этом обрабатывается каждый узел, а время обработки узла квадратично числу соседних узлов. Этот алгоритм проверки триангуляции также предполагает
96 ЧЕРНОВИК от 9 марта 2010 г. Алгоритм построения дерева соединений
Рисунок 6.9: Начиная с сети Маркова в (a), алгоритм проверки максимальной мощности продолжается до (b). где требуется дополнительная связка (c). Алгоритм продолжается до тех пор, пока не будет найден полностью триангулированный граф (d).
алгоритм построения триангуляции – мы просто добавляем связку между двумя соседними объектами, которые привели к сбою алгоритма, а затем перезапускаем алгоритм. Алгоритм перезапускается с самого начала, а не просто продолжается с текущего узла. Это важно, поскольку новая ссылка может изменить связку между ранее помеченными узлами. Пример приведен на рис.6.9.1
Определение 49 (Идеальный порядок исключения). Пусть n переменных в марковской сети упорядочены от 1 до n. Упорядоченность идеальна, если для каждого узла i, соседи этого i, которые находятся в более позднем порядке, и сам i образуют (максимальную) клику. Это означает, что когда мы последовательно удаляем переменные от 1 до n, в оставшемся маргинальном графе не возникает дополнительных связок. Граф, допускающий совершенный
порядок исключения является разложимым, и наоборот.
Алгоритм 2. Проверка того, является ли граф разложимым (триангулированным). Граф считается триангулированным, если после циклического прохождения всех n узлов графа критерий СБОЯ не встречается.
1: Выберите любой узел в графе и пометьте его как 1.
2: от i = 2 до n выполните
Выберите узел с наибольшим количеством помеченных соседей и пометьте его как i.
Если любые два помеченных соседа из i не находятся рядом друг с другом, выполните СБОЙ.
5: завершение цикла от \для
Там, где имеется более одного узла с наиболее помеченными соседями, связь \веревка\ может быть разорвана произвольным образом.
6.6 Алгоритм построения дерева соединений
Теперь у нас есть все шаги, необходимые для логического вывода в многосвязных графах.:
Морализация связана с родителями. Это требуется только для направленных распределений.
Триангуляция гарантирует, что каждая петля длиной 4 или более имеет хорду.
Дерево соединений\ отбросов\ Формирует дерево соединений из кликов триангулированного графа, удаляя все ненужные связки в цикле на кластерном \групповом\ графе. Алгоритмически этого можно достичь, найдя дерево с максимальным связующим \спаннинг, населённом мухами\ весом, вес которого wij определяется количеством переменных в разделителе между кликами \роями мух, пчёл и т. д., бандами\ i и j. В качестве альтернативы, учитывая порядок исключения клик (с наименьшими кликами, исключенными первыми), можно соединить каждую клику i с единственной соседней кликой j > i с наибольшим весом ребра wij .
1 Этот пример подготовлен Дэвидом Пейджем www.cs.wisc.edu/;dpage/cs731
ЧЕРНОВИК от 9 марта 2010 г. 97 Алгоритм дерева соединений
Рисунок 6.10: (а): Оригинальная замкнутая сеть убеждений \уверений. (b): Ссылки \связки\ на морализацию (пунктирная линия) расположены между узлами e и f и между узлами f и g. Другие дополнительные связки\ссылки получены в результате триангуляции. Размер клики \банды\ результирующего дерева банд\ клик (не показано) равен четырем. Из [55].
Назначение потенциала Назначьте потенциалы роям \кликам дерева соединений \отбросов, падающих листьев \ и установите значения потенциалов разделителей по единице.
Распространение сообщений выполняется до тех пор, пока обновления не будут переданы в обоих направлениях по каждой связке\ссылке в JT.
Затем из JT могут быть считаны поля \маргиналы кликов. Пример приведен на рис. 6.10.
6.6.1 Замечания по JTA
• Алгоритм предоставляет верхнюю границу вычислений, необходимых для вычисления маргиналей \выгод\ на графе. В отдельных случаях могут существовать более эффективные алгоритмы, хотя в целом считается, что не может быть намного более эффективных подходов, чем JTA, поскольку любой другой подход должен выполнить триангуляцию[147, 173]. Одним из частных случаев является маргинальный \выгодный\ вывод для бинарной переменной MRF на двумерной решетке, содержащей только чистые квадратичные взаимодействия. В этом случае сложность вычисления предельного \выгодного\ вывода равна O(n3), где n — количество переменных в распределении. Это противоречит пессимистической экспоненциальной сложности, предложенной JTA. Такие случаи являются узкоспециализированными, и маловероятно, что существует универсальный алгоритм, который мог бы стабильно превосходить JTA.
• Можно подумать, что единственным классом распределений, для которых по существу доступен алгоритм линейного времени, являются односвязные распределения. Однако существуют разложимые графы, для которых клики \рои\ имеют ограниченный размер, что означает, что логический вывод является приемлемым \ проходимым. Например, расширенная версия "лестницы" на рис.6.6а имеет простое индуцированное разложимое представление на рис.6.6б, для которого предельный \выгодный\ вывод был бы линейным по количеству ступеней в лестнице. По сути, эти структуры представляют собой гипердеревья, в которых сложность затем зависит от ширины дерева графа[81].
• В идеале мы хотели бы найти триангулированный граф с минимальным размером клики \роя. Однако можно показать, что поиск наиболее эффективной триангуляции является сложной вычислительной задачей (NР -hard \трудной). На практике большинство алгоритмов триангуляции общего назначения в некоторой степени эвристичны и выбираются для обеспечения разумной\ порождающей , но явно неоптимальной производительности.
• Проблемы с численным превышением/ занижением потока могут возникать в больших группах\ кликах, роях\, где многие значения вероятности умножаются \суммируются. Аналогично в длинных цепочках, поскольку поглощение будет иметь тенденцию к уменьшению численного размера потенциальных входов в рое \клике. Если нас интересуют только маргинальные значения \выгоды, мы можем избежать числовых трудностей, нормализуя потенциалы на каждом шаге; эти недостающие константы нормализации всегда можно найти в соответствии с ограничением нормализации. При необходимости всегда можно сохранить значения этих локальных корректировок, если, например, требуется глобальная нормализующая константа распределения, см. раздел (6.6.2).
• После закрепления переменных в доказательных состояниях, запуск JTA возвращает совместное распределение на неочевидные переменные в группе, где все очевидные переменные зафиксированы в своих очевидных состояниях. Исходя из этого, легко вычислить условные обозначения.
• Представьте, что мы запустили алгоритм JT и хотим затем найти предельное \выгоды\ значение p(X |evidence). Мы могли бы сделать это, ограничив доказательные переменные. Однако, если и X, и набор доказательных переменных
98 ЧЕРНОВИК от 9 марта 2010г. Алгоритм дерева соединений
всё содержится в одном клике JT, тогда мы можем использовать согласованные клики JT чтобы вычислить p(X | evidence). Причина в том, что, поскольку JT-клика содержит предельное значение для набора переменных, который включает в себя X и доказательные переменные, мы можем получить требуемое предельное значение, рассматривая только одну JT-клику.
• Представление предельного распределения набора переменных X, которые не содержатся в пределах одной группы, в целом является сложной вычислительной задачей. Хотя вероятность любого состояния p(X ) может быть вычислена эффективно, число таких состояний, как правило, экспоненциально. Классический пример в этом отношении имеет значение HMM, раздел (23.2) с односвязным совместным распределением p(V, H). Однако предельное распределение p(H) полностью связано. Это означает, что, например, в то время как энтропия p(V, H) легко вычисляется, энтропия предельного значения p(H) является трудноразрешимой.
6.6.2 Вычисление константы нормализации распределения
Для сети Маркова
как мы можем эффективно найти Z? Если бы мы использовали JTA для ненормализованного распределения, то получили бы эквивалентное представление:
Поскольку распределение должно нормализоваться, мы можем получить Z из
Для состоятельного JT, при суммировании сначала по переменным простой JT-группы (не включая переменные-разделители), предельная группа будет отменена соответствующим разделителем, чтобы получить член единицы, так что группа и разделитель могут быть удалены. Это формирует новый JT, для которого мы затем исключаем другую упрощенную клику. Продолжая в том же духе, мы останемся с потенциалом в одном числителе, так что
Это справедливо для любой клики C, поэтому имеет смысл выбрать одну с небольшим числом состояний, чтобы результирующее необработанное суммирование было эффективным. Следовательно, для вычисления константы нормализации распределения выполняется алгоритм JT для ненормализованного распределения, и затем глобальная нормализация задается локальной нормализацией любой клики. Обратите внимание, что если граф несвязан (есть изолированные клики), то нормализация является произведением констант нормализации связанных компонентов. A удобный с точки зрения вычислений способ найти это - вычислить произведение всех нормализаций по кликам, разделенное на произведение всех нормализаций по разделителям.
6.6.3 Предельная вероятность \ Выгодная правдоподобность
В данном случае нас интересует вычисление p(V), где V - подмножество полного набора переменных. Наивно было бы провести это вычисление, суммируя все неочевидные переменные (скрытые переменные H = X \V). явно. В тех случаях, когда это нецелесообразно с точки зрения вычислений, альтернативой является использование
Это можно рассматривать как произведение потенциалов кликов, деленное на нормировку p(V), для которой может быть непосредственно применен общий метод, описанный в разделе (6.6.2). Смотрите demoJTree.m
ПРОЕКТ от 9 марта 2010 г. 99 Алгоритм дерева соединений
Пример 26 (простой пример JTA).
Рассмотрим выполнение JTA на простом графе
Этапы морализации и триангуляции тривиальны, и JTA сразу же указывается на рисунке справа. Допустимым назначением является
Чтобы найти предельное значение p(b), мы сначала запускаем JTA:
• Поглощая от ab до b, новый разделитель ; ; (b) =;a ; (a, b) = ; a p(a|b) = 1.
• Новый потенциал на (b, c) определяется как
• Поглощая от bc до b, новый сепаратор является
• Новый потенциал на (a, b) определяется
Следовательно, это действительно равно предельному значению, поскольку ;cp(a, b, c) = p(a, b).
Новый разделитель ; ;; (b) содержит предельное значение p(b), поскольку
Пример 27 (Нахождение условного предельного значения \выгоды). Продолжая рассмотрение распределения в примере(26), мы рассмотрим, как вычислить p(b|a = 1, c = 1). Сначала мы зафиксируем фактические переменные в их состояниях. Затем мы утверждаем, что результат выполнения JTA заключается в том, что для набора переменных клики\ банды\ X создаются маргинальные значения для клик \банды\ p(X , V). Мы демонстрируем это ниже:
• В общем, новый разделитель задается как ; ; (b) =;a ; (a, b) =;a p(a|b) = 1. Однако, поскольку a находится в состоянии a = 1, тогда суммирование по a не выполняется, и вместо этого мы имеем ; ; (b) = p(a = 1|b).
• Новый потенциал на клике (b, c) определяется как
• Новый разделитель обычно задается с помощью
Однако, поскольку c находится в состоянии 1, мы имеем вместо этого
; ;; (b) = p(b|c = 1)p(c = 1)p(a = 1|b) (6.6.14)
100 ЧЕРНОВИК от 9 марта 2010 г. Определение наиболее вероятного состояния
• Новый потенциал для (a, b) задается с помощью
Результатом фиксации набора переменных V в их очевидных состояниях и запуска JTA является то, что для группы i, которая содержит набор неочевидных переменных Hi , согласованный потенциал из JTA содержит предельное значение p(Hi , V). Таким образом, определение условного предельного значения становится простым путем обеспечения нормализации.
Пример 28 (нахождение правдоподобности p(a = 1, c = 1)). В результате фиксации переменных в их очевидных состояниях и выполнения JTA получаются общие маргиналы, такие как ; ; (a, b) = p(a = 1, b, c = 1). Тогда вычислить правдоподобность легко, поскольку мы просто суммируем по неочевидным переменным любого сходящегося потенциала : p(a = 1, c = 1) = ;b ; ; (a, b) = ;bp(a = 1, b, c = 1).
6.7 Определение наиболее вероятного состояния
Интересующая величина - это наиболее вероятное совместное состояние распределения:
и естественно задаться вопросом, как это можно эффективно вычислить в случае циклического распределения. Поскольку разработка JTA основана на процедуре исключения переменных, а оператор max также влияет на распределение, исключение переменной путем максимизации по этой переменной окажет такое же влияние на структуру графа, как и суммирование. Это означает, что дерево соединений \ падалок\ снова является подходящей структурой, с которой можно выполнять max операции. Как только JT будет построен, можно будет использует процедуру максимального поглощения (см. ниже), чтобы выполнить максимизацию по переменным. После того, как будет выполнен полный цикл поглощения, клики будут содержать распределение по переменным в клике, а все остальные переменные будут приведены в оптимальное состояние. Оптимальные локальные состояния могут быть найдены путем явной оптимизации потенциала каждой клики в отдельности.
Обратите внимание, что эта процедура справедлива и для нераспределений - в этом смысле это пример более общей процедуры динамического программирования, применяемой в случае, когда базовый граф многосвязен. Это демонстрирует, как эффективно вычислить оптимум многосвязной функции, определяемой как произведение на потенциалы.
Определение 50 (Максимальное поглощение).
Пусть V и W - соседи в графе клик, пусть S — их разделитель, а ; (V), ; (W) и ; (S) - их потенциалы. В результате абсорбции таблицы ; (S) и ; (W) заменяются на
Как только сообщения были пройдены в обоих направлениях за все разделители, в соответствии с действующим графом, наиболее вероятное совместное состояние может быть определено путем максимизации состояния потенциалов кликов. Это реализовано в absorb.m и absorbtion.m, где флаг используется для переключения между суммой и максимальным поглощением.
ПРОЕКТ от 9 марта 2010 г. 101 Поглощение: Преобразование дерева соединений в направленную сеть
Рисунок 6.11: (а): Дерево соединений \ падалок\. (б): Направленное дерево соединений, в котором все ребра последовательно ориентированы от клики \банды\ (abc). (в): Заданная цепочка, сформированная из дерева соединений путем повторного поглощения каждого разделителя в свою дочернюю группу \банду.
6.8 Повторное поглощение: преобразование дерева соединений \падалок\ в направленную сеть
Иногда полезно иметь возможность преобразовать JT обратно в BN желаемой формы. Например, если кто-то хочет получить выборки из сети Маркова, это может быть достигнуто путем выборки предков на эквивалентной направленной структуре, см. раздел (27.2.2).
Возвращаясь к примеру с рис. 6.4, мы получаем JT, показанный на рис.6.11а. Чтобы найти правильное направленное представление, мы сначала последовательно ориентируем ребра JT от выбранного корневого узла (см. singleparenttree.m), таким образом, формируется направленный JT, который обладает свойством, заключающимся в том, что каждая клика имеет не более одной родительской клики.
Определение 51 (Повторное поглощение).
Пусть V и W - соседние клики в направленном JT, в котором каждая клика в дереве имеет не более одного родительского элемента. Кроме того, пусть S - их разделитель, а ; (V), ; (W) и ; (S) - потенциалы. Реабсорбция в W удаляет разделитель и формирует (заданное) условное распределение
Мы говорим, что клика W повторно поглощает разделитель S.
На рис. (6.11), где из JT сформировано одно из многих возможных направленных представлений. В частности, на рисунке (6.11a) представлено значение
Теперь у нас есть множество вариантов того, какая группа повторно использует разделитель. Один из таких вариантов дал бы
p(a, b, c, d, e, f, g, h) = p(g|e)p(d, e|c)p(a, b, c, )p(f |c)p(h|e) (6.8.3)
Это можно представить с помощью так называемой цепочки установок[170] на рис. 6.11, в (цепочки установок обобщают сети убеждений к произведению кластеров переменных, зависящих от родителей). Записывая каждую из заданных условных вероятностей в виде локальных условных значений BN, можно также записать полное значение BN. Например, одно из таких значений может быть получено из разложения
p(c|a, b)p(b|a)p(a)p(g|e)p(f |c)p(h|e)p(d|e, c)p(e|c) (6.8.4)
102 ПРОЕКТ от 9 марта 2010 г. Код
Рисунок 6.12: 5 заболеваний, вызывающих 3 симптома. Предполагая, что все симптомы представлены в виде экземпляров, триангулированный график заболеваний представляет собой 5 кликов.
6.9.Необходимость в приближениях
JTA устанавливает верхнюю границу сложности (предельного) вывода и пытается использовать структуру графа для сокращения вычислений. Однако во многих интересных приложениях использование алгоритма JTA привело бы к непомерно большим размерам клик в триангулированном графе.
Классическая ситуация, в которой это может возникнуть, - это сети "болезнь-симптом". Например, для графа на рис. 6.12 триангулированный график заболеваний полностью связан, что означает, что упрощение невозможно в общем. Такая ситуация характерна для таких двусторонних сетей, даже если у дочерних элементов есть только небольшое количество родителей. Интуитивно понятно, что при устранении каждого из родителей добавляются связи между другими родителями, опосредованные общими дочерними элементами. Если граф не является в высшей степени регулярным, что аналогично скрытой модели Маркова, этот эффект заполнения быстро приводит к образованию больших групп и трудноразрешимым вычислениям.
Работа с большими кликами в триангулированном графе является активной темой исследования, и мы обсудим стратегии аппроксимации вычислений в главе (28).
6.9.1 Деревья отбросов \с падалками, соединений, падалок\ ограниченной ширины
В некоторых приложениях мы можем свободно выбирать структуру сети Маркова. Например,
если мы хотим адаптировать сеть Маркова к данным, мы можем захотеть использовать настолько сложную сеть Маркова, насколько это возможно с точки зрения вычислений. В таких случаях мы хотим, чтобы размеры кликов результирующей триангулированной Марковской сети были меньше заданной "ширины дерева" (учитывая, что соответствующее дерево соединений является гипердеревом). Построение таких деревьев ограниченной ширины или "тонких" соединений \ падалок\ является активной темой исследования. Простой способ способ сделать это - начать с графа и включить случайно выбранное ребро при условии, что размер всех кликов в результирующем триангулированном графе меньше заданной максимальной ширины. Смотрите demoThinJT.m и makeThinJT.m, которые предполагают исходный граф G и граф возможных ребер C, итеративно расширяя G до тех пор, пока не будет достигнут максимальный предел ширины дерева. Смотрите также [11] для обсуждения обучения соответствующей Марковской структуры, основанной на данных.
6.10 Код
absorb.m: Обновление поглощения V ; S ; W
absorb.m: Полное расписание поглощения по дереву
jtree.m: Формирование дерева соединений \падалок
triangulate.m: Триангуляция, основанная на простом удалении узлов
6.10.1 Полезные процедуры \приёмы
Полезно знать, является ли неориентированный граф деревом, и полезно возвращать корректную последовательность исключений. Связный граф является деревом, если число ребер плюс 1 равно числу вершин \узлов. Однако для возможно несвязанного графа это не так. Код имеет дело с возможным несвязанным случаем, возвращая допустимую последовательность исключения, если граф односвязный. Процедура основана на наблюдении что любой односвязный граф всегда должен иметь простой \упрощённый\ узел, который можно удалить, чтобы получить меньший односвязный граф.
istree.m: Если граф односвязный вернуть 1 и последовательность исключения
elimtri.m: Исключение вершины/узла на триангулированном графе с заданным конечным узлом
demoJTree.m: Дерево соединений : Клиника грудной клетки
ЧЕРНОВИК от 9 марта 2010 103 Упражнения
6.11 Упражнения
4
Упражнение 58. Покажите, что маркировка отсева в сети Маркова для этого графа.
не является идеальным порядком отсева и дает идеальный результат
Упражнение 59. Рассмотрим следующее распределение:
1. Нарисуйте граф кликов\ дружков\, представляющий это распределение, и укажите разделители на графе.
2. Запишите альтернативную формулу для распределения p(x1 , x2 , x3 , x4 ) в терминах предельных вероятностей p(x1 , x2 ), p(x2 , x3 ), p(x3 , x4 ), p(x2 ), p(x3 ).
Упражнение 60. Рассмотрим распределение
1. Запишите дерево соединений для приведенного выше графа.
2. Выполните процедуру поглощения и продемонстрируйте, что это дает правильный результат для предельного значения p(x1).
Упражнение 61. Рассмотрим распределение
p(a, b, c, d, e, f, g, h, i) = p(a)p(b|a)p(c|a)p(d|a)p(e|b)p(f|c)p(g|d)p(h|e, f )p(i|f, g) (6.11.3)
1. Нарисуйте сеть убеждений для этого распределения.
2. Нарисуйте морализированный граф.
3. Нарисуйте триангулированный граф. Ваш триангулированный граф должен содержать группы как можно меньшего размера.
4. Нарисуйте дерево пересечений для приведенного выше графа и убедитесь, что оно удовлетворяет свойству текущего пересечения.
5. Опишите подходящую инициализацию кликовых потенциалов.
6. Опишите процедуру поглощения и запишите соответствующий граф обновления сообщений.
Упражнение 62. Этот вопрос касается распределения
p(a, b, c, d, e, f) = p(a)p(b|a)p(c|b)p(d|c)p(e|d)p(f|a, e) (6.11.4)
1. Нарисуйте сеть убеждений для этого распределения.
2. Нарисуйте морализированный граф.
3. Нарисуйте триангулированный граф. Ваш триангулированный граф должен содержать группы как можно меньшего размера.
4. Нарисуйте дерево пересечений \ падалок\ для приведенного выше графа и убедитесь, что оно удовлетворяет свойству бегущего \текущего\ пересечения.
5. Опишите подходящую инициализацию потенциалов кликов.
6. Опишите процедуру поглощения и соответствующее расписание обновления сообщений.
7. Покажите, что распределение может быть выражено в виде
p(a|f), p(b|a, c), p(c|a, d),p(d|a, e),p(e|a, f ), p(f ) (6.11.5)
104 ЧЕРНОВИК от 9 марта 2010 г.
Упражнение 63.
Для неориентированного графа на квадратной решетке, как показано на рисунке,
нарисуйте триангулированный граф с наименьшими возможными размерами клик.
Упражнение 64.
Рассмотрим бинарную переменную Марковского случайного поля p(x) = Z -1; i>j ;(xi , xj ), определенную на решетке n ; n с ;(xi , xj ) = eI[xi =xj ] для i, соседа j по решетке, и i > j. Наивный способ сделать вывод - сначала сложить все переменные в t-м столбце и вызвать эту кластерную переменную Xt , как показано на рисунке.. Результирующий граф затем является односвязным. Какова сложность вычисления константы нормализации на основе этого кластерного представления? Вычислите логарифм Z для n = 10.
Упражнение 65. Учитывая согласованное дерево соединений, по которому был выполнен полный цикл передачи сообщений, объясните, как сформировать сеть убеждений на основе дерева соединений.
Упражнение 66. Файл diseaseNet.mat содержит потенциальные возможности для создания сети убеждений, состоящей из двух частей: 20 заболеваний d1 , ... , d20 и 40 симптомов s1 , ... , s40 . Каждое заболевание и симптом являются бинарными переменными, и каждый симптом связан с тремя исходными заболеваниями.
1. Используя BRMLtoolbox, постройте дерево связей для этого распределения и используйте его для вычисления всех граничных значений симптомов, p(si = 1).
2. На большинстве стандартных компьютеров вычисление предельного значения p(si = 1) путем простого суммирования общего распределения является вычислительно неосуществимым. Объясните, как вычислить предельное значение p(si = 1) в приемлемый способ без использования формализма дерева соединений. Реализовав этот метод, сравните его с результатами алгоритма дерева соединений.
3. Рассмотрим (маловероятный) сценарий, в котором создаются экземпляры всех 40 переменных симптомов. Используя дерево соединений, оцените верхнюю границу количества секунд, которое занимает вычисление предельного значения p(d1 |s1:40), предполагая, что для таблицы с двумя кликами, содержащей S (совместных) состояний, поглощение занимает O (S;) секунд для неопределенного значения ;. Сравните эту оценку со временем, необходимым для вычисления предельного знаечния путем грубого обобщения \суммирования\ созданной сети убеждений.
ЧЕРНОВИК от 9 марта 2010 г.
105 упражнений
106
ЧЕРНОВИК главы от 9 марта 2010 года
Глава 7
Принятие решений
7.1 Ожидаемая полезность \использование
В этой главе рассматриваются ситуации, в которых необходимо принимать решения в условиях неопределенности. Рассмотрим следующий сценарий: вас спрашивают, хотите ли вы сделать ставку на результат подбрасывания честной монеты. Если вы сделаете ставку и выиграете, вы получите 100 фунтов стерлингов. Если вы сделаете ставку и проиграете, вы потеряете 200 фунтов стерлингов. Если вы не сделаете ставку, ваши затраты будут равны нулю. Мы можем настроить это, используя переменную с двумя состояниями x, где dom(x) = {win \выигрыш, lose \ проигрыш}, переменную принятия решения d с dom(d) = {bet \ ставка, no bet \ е ставка} и следующие выплаты:
U (выигрыш, ставка) = 100, U (проигрыш, ставка) = -200, U (выигрыш, не ставка) = 0, U (проигрыш, не ставка) = 0
Поскольку мы не знаем, в каком состоянии находится x, то для принятия решения о том, делать ставку или нет, возможно, лучшее, что мы можем сделать, - это рассчитать наши ожидаемые выигрыши/проигрыши в ситуациях, когда мы делаем ставки и не не делаем ставок[240]. Если мы делаем ставку, то ожидаем выигрыша
U (ставка) = p(выигрыш) ; U (выигрыш, ставка) + p(проигрыш) ; U (проигрыш, ставка) = 0.5 ; 100 ; 0.5 ; 200 = -50
Если мы не делаем ставку, ожидаемый выигрыш равен нулю, U (без ставки) = 0. На основе принятия решения, которое максимизирует ожидаемую полезность, поэтому нам не рекомендуется делать ставки.
Определение 52 (Субъективная ожидаемая полезность). Полезность решения равна
где p(x) - распределение результата x, а d - решение.
7.1.1 Полезность денег
Вы состоятельный человек, на вашем банковском счете 1 000 000 фунтов стерлингов. Вас спросят, хотите ли вы принять участие в честной игре, в которой в случае выигрыша на ваш банковский счет поступит 1 000 000 000 фунтов стерлингов. Однако, если вы проиграете, на вашем банковском счете останется только 1000 фунтов стерлингов. Предполагая, что монета честная, должны ли вы принять ставку?
Если мы примем ставку, наш ожидаемый банковский баланс составит
U (ставка) = 0.5 ; 1, 000, 000, 000 + 0.5 ; 1000 = 500, 000, 500.00 (7.1.3)
Если мы не сделаем ставку, наш банковский баланс останется на уровне 1 000 000 фунтов стерлингов. Исходя из ожидаемой полезности, нам рекомендуется принять ставку. (Обратите внимание, что если вместо этого учитывать сумму, которую вы выиграете или проиграете, то можно показать на примере
107 Деревья решений
, что разница в ожидаемой полезности между ставками и не ставками одинакова, упражнение(73)).
Хотя приведенный выше математический вывод является правильным, немногие люди, которые являются миллионерами, вероятно, будут миллионерами в будущем, готовы рискнуть потерять почти все, чтобы стать миллиардером. Это означает, что субъективная полезность денег - это не просто их количество. Чтобы лучше отразить ситуацию, полезность
денег должна быть нелинейной функцией денег, медленно увеличивающейся для больших количеств денег и быстро уменьшающейся для небольших количеств денег, см. упражнение(68).
7.2 Деревья принятия решений
Деревья решений - это способ графической организации последовательного процесса принятия решений. Дерево решений содержит узлы принятия решений, каждый из которых имеет ответвления для каждого из альтернативных решений. Узлы шанса (случайные переменные) также отображаются в дереве, причем полезность каждой ветви вычисляется в конце \ листе\ каждой ветви. Ожидаемая полезность любого решения может быть затем вычислена на основе взвешенного суммирования всех ответвлений от данного решения со всеми выходами \ листами\ от этой ветви.
Пример 29 (Вечеринка). Рассмотрим проблему принятия решения о том, стоит ли проводить вечеринку в саду по сбору средств. Если мы проведем вечеринку, а соответственно пойдет дождь, то мы потеряем деньги (поскольку придет очень немного людей); с другой стороны, если мы не будем продолжать вечеринку и не будет дождя, мы можем пойти и заняться чем-нибудь другим веселым. Чтобы охарактеризовать это численно, мы используем:
Полезность определяется как
U (вечеринка, дождь) = -100, U (вечеринка, без дождя) = 500, U (вечеринка, дождь) = 0, U (вечеринка, дождь) = 50 (7.2.2)
Мы представляем эту ситуацию на рис. 7.1. Вопрос в том, стоит ли нам продолжать вечеринку? Поскольку мы не знаем, что на самом деле произойдет с погодой, мы вычисляем ожидаемую полезность каждого решения:
Исходя из ожидаемой полезности, нам рекомендуется продолжить вечеринку. Максимальная ожидаемая полезность определяется как (см. раздел demoDecParty.m)
Пример 30 (Вечеринка с другом). Проблема, связанная с вечеринкой, заключается в том, что если мы решим отказаться от вечеринки, у нас будет возможность навестить друга. Однако мы не уверены, будет ли этот друг на вечеринке. Вопрос в том, стоит ли нам продолжать вечеринку?
Нам нужно количественно оценить все неопределенности и полезность. Если мы продолжим вечеринку, полезность останется прежней:
Выигрыш (вечеринка, дождь) = -100, Выигрыш (вечеринка, без дождя) = 500
108 ЧЕРНОВИК от 9 марта 2010 г. Деревья решений
Дождь
Вечеринка
Рисунок 7.1: Дерево решений, содержащее случайные узлы (обозначенные овалами), узлы принятия решений (обозначенные квадратами) и полезные узлы (обозначенные ромбами). Обратите внимание, что дерево решений не является графическим представлением сети убеждений с дополнительными узлами. Скорее, дерево решений - это явное перечисление возможных вариантов, которые могут быть сделаны, начиная с крайнего левого узла принятия решений, с вероятностями в связях между ‘случайными’ узлами.
, где
Если мы решим отказаться от вечеринки, мы подумаем о том, чтобы навестить друга. При принятии решения не участвовать в вечеринке у нас есть преимущества
Количество участников (без вечеринки, дождь) = 0, Количество участников (без вечеринки, без дождя) = 50
(7.2.8)
Вероятность того, что друг находится дома, зависит от погоды в соответствии с
p(friend = есть|дождь) = 0,8, p(friend = есть|нет дождя) = 0,1,
(7.2.9)
Остальные вероятности определяются путем нормализации. Кроме того, у нас есть
Количество посещений (друг пришел, навестил) = 200, количество посещений (друг ушел, навестил) = -100
(7.2.10)
при этом остальные выплаты \платежи равны нулю. Эти два набора утилит суммируются таким образом, что общая полезность любой последовательности принятия решений равна Uparty + Uvisit . Дерево решений для задачи "Участник-друг" показано на рис.7.2. Для каждого последовательность принятия решений полезность этой последовательности указана на соответствующем листе таблицы DT. Обратите внимание, что в листьях содержится общая полезность Uparty +Uvisit . Решение задачи DT соответствует нахождению для каждого узла принятия решений максимально возможной ожидаемой полезности (путем оптимизации по сравнению с будущими решениями). В любой точке дерева выбор того действия, которое приводит к дочернему элементу с наибольшей ожидаемой полезностью, приведет к оптимальной стратегии. Используя это, мы находим, что оптимальная ожидаемая полезность имеет значение 140 и определяется путем продолжения работы с вечеринкой \партией, см. demoDecPartyFriend.m.
• В DTs одни и те же узлы часто повторяются по всему дереву. Для более длинной последовательности решений количество ветвей в дереве может расти экспоненциально с увеличением количества решений, что делает такое представление непрактичным.
• В этом примере DT асимметричен, поскольку, если мы решим продолжить вечеринку, мы не навестим друга, что ограничит дальнейшие решения, представленные в нижней половине дерева.
Математически мы можем выразить оптимальную ожидаемую полезность U для примера с посещением вечеринки, суммируя нераскрытые переменные и оптимизируя будущие решения:
максимум
Дождь
Вечеринка|дождь
где термин I [party = no] приводит к сокращению срока действия DT, если сторона продолжает действовать. Чтобы ответить на вопрос о том, продолжать ли участие в партии, мы примем то состояние, которое соответствует
Проект от 9 марта 2010 года 109Деревья решений
Дождь
да
нет
Вечеринка
Друг
Рисунок 7.2: Построение дерева решений.
(а): Дерево решений для посещения вечеринки, пример(30). (б): Решение DT соответствует принятию решения с наибольшей ожидаемой пользой в будущем. Этого можно достичь, начав с конечных элементов \листьев (utilities). Для случайного \шанса родительского узла x полезность родительского узла равна ожидаемой полезности этой переменной. Например, в верхней части DT у нас есть переменная дождя возможен \способен с дочерними элементами -100 (вероятность 0,6) и 500 (вероятность 0,4). Следовательно, ожидаемая полезность дождевого узла равна -100 ; 0.6 + 500 ; 0.4 = 140. Для узла принятия решений значение узла является оптимальным из его дочерних значений. Таким образом, выполняется обратный переход от листьев к корню. Например, значение Узел вероятности дождя в нижней ветви задается следующим образом 140 ; 0.6 + 50 ; 0.4 = 104. Затем в каждом узле принятия решений определяется оптимальная последовательность принятия решений путем определения того, какой дочерний узел имеет максимальное значение. Следовательно, наилучшим решением в целом является решение двинуть после вечеринки дальше. Если мы решили не делать этого, а дождя нет, то лучшим решением, которое мы могли бы принять, было бы не посещать друга (ожидаемая полезность которого составляет 50). Более краткое описание этой проблемы приведено на диаграмме влияния, рис.7.4. Смотрите также demodec partyfriend.m.
максимальной ожидаемой полезности, указанная выше. Чтобы прочитать уравнение (7.2.11), нужно начать с последнего решения, которое необходимо принять, в данном случае Visit\ Навестить друга. Когда мы находимся на стадии Visit \Навестить друга, мы предполагаем, что у нас будет предварительно принятое нами решение о вечеринке, а также проследили, идет ли дождь. Однако мы не знаем, будет ли наш друг дома, поэтому мы вычисляем ожидаемую полезность, усредняя значение по этому неизвестному. Затем мы принимаем оптимальное решение, максимизируя значение Visit \Навестить друга. Затем мы переходим к предпоследнему решению, предполагая, что то, что мы будем делать в будущем, является оптимальным. Поскольку в будущем мы примем решение в соответствии с неопределенной конечной переменной Друг дома, текущее решение может быть принято в соответствии с неопределенностью в отношении Дождя и максимизация этой ожидаемой оптимальной полезности по Вечеринке. Обратите внимание, что последовательность максимизаций и суммирования имеет значение – изменение порядка, как правило, приведет к другой задаче с другой ожидаемой полезностью1 .
1Если имеется только последовательность суммирования, порядок суммирования не имеет значения – аналогично для случая всех максимизаций. Однако операторы суммирования и максимизации, как правило, не коммутируют.
110
ПРОЕКТ от 9 марта 2010 г., Расширяющий байесовские сети для принятия решений
Статья
Дождь
Полезность
Рисунок 7.3: Диаграмма влияния, которая содержит случайные переменные (обозначенные овалами/кружками), узлы принятия решений (обозначенные квадратами) и узлы полезности (обозначенные ромбами). В отличие от рисунка(7.1), это более компактное представление структуры задачи. На диаграмме представлено выражение p(дождь)u(вечеринка, дождь). Кроме того, на диаграмме обозначен порядок переменных с помощью party ; rain (в соответствии с соглашением, заданным уравнением (7.3.1)).
7.3.Расширение байесовских сетей для принятия решений
Диаграмма влияния представляет собой байесовскую сеть с дополнительными узлами принятия решений и узлами полезности [137, 148, 162]. Узлы принятия решений не имеют связанного распределения; узлы полезности являются детерминированными функциями своих родительских узлов. Узлы полезности и принятия решений могут быть как непрерывными, так и дискретными; для простоты в приведенных здесь примерах решения будут дискретными.
Преимущество деревьев решений заключается в том, что они являются общими и явно кодируют полезности и вероятности, связанные с каждым решением и событием. Кроме того, мы можем легко решать небольшие задачи, связанные с принятием решений, используя деревья решений. Однако, когда последовательность решений увеличивается, число листьев в дереве решений растет, и представление дерева может стать экспоненциально сложной задачей. В таких случаях может быть полезно использовать диаграмму влияния (ID). Идентификатор ID указывает, какая информация требуется для принятия каждого решения, и порядок, в котором эти решения должны приниматься. В идентификаторе не указаны подробности о вероятностях и вознаграждениях, и это может обеспечить более компактное описание проблемы принятия решения.
7.3.1 Синтаксис диаграмм влияния
Информационные ссылки Информационная ссылка от случайной величины к узлу принятия решений:
указывает, что состояние переменной X будет известно до принятия решения D. Информационные ссылки от другого узла принятия решений d к D аналогичным образом указывают на то, что решение d известно до принятия решения D. Мы используем пунктирную ссылку, чтобы обозначить, что решение D функционально не связано с его родителями.
Случайные величины Случайные величины могут зависеть от состояний родительских случайных величин (как в сетях убеждений), а также от состояний узлов принятия решений:
По мере принятия решений будут выявляться состояния некоторых случайных величин. Чтобы подчеркнуть это, мы обычно заштриховываем узел, чтобы обозначить, что его состояние будет выявлено в ходе последовательного процесса принятия решения.
Полезности Узел полезности является детерминированной функцией своих родительских элементов. Родительскими элементами могут быть как случайные величины, так и узлы принятия решений.
В примере с партией BN тривиально состоит из одного узла, а диаграмма влияния приведена на рис. 7.3. Более сложная проблема "Партия-друг" изображена на рис.7.4. Идентификатор, как правило, предоставляет более компактное представление структуры задачи, чем DT, хотя подробная информация о конкретных вероятностях и полезностях отсутствует в ID.
ПРОЕКТ от 9 марта 2010 г.
111 Расширение байесовских сетей для принятия решений
Вечеринка
Навестить друга
Дождь
Друг дома
Посещение вечеринки
Рисунок 7.4: Диаграмма влияния для задачи о посещении вечеринки, пример (30). Отдельный порядок: "Вечеринка" * "Дождь" * "Навестить друга" * "Друг дома". Пунктирная ссылка от вечеринки к навестить друга не является строго необходимой, но сохраняется, чтобы соответствовать условию о том, что существует прямой путь, соединяющий все узлы принятия решений.
Частичное упорядочение
Идентификатор определяет частичный порядок расположения узлов. Мы начинаем с записи тех переменных X0, состояния которых известны (доказательные переменные) до принятия первого решения D1 . Затем мы находим набор переменных X1, состояния которых выявлены до принятия второго решения D2 . Затем выявляется набор переменных Xt до принятия решения Dt+1 . Оставшиеся полностью ненаблюдаемые переменные помещаются в конец упорядочения:
с ХК будучи переменными выявлена между решением Dk и Dk+1 . Термин частичный ссылается на то, что порядок между переменными в наборе Xn не подразумевается. Для наглядности в нижеприведенных пунктах мы будем указывать переменные решения с помощью *, чтобы подчеркнуть, что мы максимизируем эти переменные и суммируем переменные, не отмеченные звездочками. Там, где наборы пусты, мы их не записываем. Например, на рис. 7.5, а порядок следования самый простой Тест* < Сейсмический* < Бурение* < Нефть.
Оптимальное первое решение D1 определяется путем вычисления
для каждого состояния решения D1 , заданного X0 . В приведенном выше уравнении (7.3.2) I обозначает набор индексов для случайных величин, а J - индексы для вспомогательных узлов. Для каждого состояния обусловливающих переменных оптимальное решение D1 находится с использованием
Замечание 9 (Считывание частичного порядка). Иногда может быть сложно прочитать частичный порядок по идентификатору. Метод заключается в определении первого решения D1, а затем любых переменных X0, которые необходимо определить за этим решением нужно наблюдать. Затем определите следующее решение D2 и переменные X1, которые будут выявлены после принятия решения D1 и до принятия решения D2 и т.д. Это дает частичную упорядоченность X0 ; D1 ; X1 ; D2 , . . . Поместите все нераскрытые переменные в конец порядка.
Неявные и явные информационные ссылки
Информационные ссылки являются потенциальным источником путаницы. Информационная ссылка явно указывает, какие величины известны до принятия такого решения2. Мы также неявно принимаем принцип "не забывай" что все прошлые решения и выявленные переменные доступны в текущем решении (выявленные переменные обязательно являются родительскими для всех узлов прошлых решений). Если бы мы включили все такие информационные ссылки, идентификаторы потенциально стали бы довольно запутанными. На рис. 7.5 показаны как явные, так и неявные информационные ссылки. Мы называем информационную ссылку фундаментальной, если ее удаление привело бы к изменению частичного порядка.
2 Некоторые авторы предпочитают записывать все информационные ссылки, где это возможно, а другие предпочитают оставлять их неявными. Здесь мы в значительной степени воспользуйтесь неявным подходом. Для целей вычислений все, что требуется, - это частичное упорядочение; поэтому это можно рассматривать как "базовое", а информационные ссылки - как поверхностные (см. [69]).
112 ПРОЕКТ от 9 марта 2010 г., Расширенные байесовские сети для принятия решений
Рисунок 7.5: (а): Частичный порядок - это Тест; ; Сейсморазведка ; Бурение; ; Нефть. Явные информационные ссылки от Тест к Сейсморазведке и от Сейсморазведки к Бурению являются фундаментальными в том смысле, что удаление любого из них приводит к другому частичному упорядочению. Заштрихованный узел подчеркивает, что состояние этой переменной будет выявлено в процессе принятия последовательного решения. И наоборот, незатененный узел никогда не будет наблюдаться. (b): Исходя из идентификатора в (а), существует неявная связь между Тест и Бурением, поскольку решение о Тест принимается до обнаружения Сейсморазведочных работ.
Причинно-следственная связь
Чтобы Диаграмма Вылияния была согласованной, текущее решение не может влиять на прошлое. Это означает, что любая случайная величина, являющаяся потомком решения D в идентификаторе ID, должна появиться позже в частичном порядке. Предполагая, принцип "не забывай" означает, что для любого действительного идентификатора должен существовать прямой путь, соединяющий все решения. Это может быть полезной проверкой согласованности идентификатора.
Асимметрия
Идентификаторы наиболее удобны, когда соответствующий DT симметричен. Однако с некоторыми формами асимметрии относительно просто справиться в рамках ID. В нашем примере с посещением вечеринки DT является асимметричным. Однако с этим легко справиться в ID, используя ссылку из Вечеринка на Uvisit, которая удаляет взнос из Uvisit, когда вечеринка продолжается.
Более сложные проблемы возникают, когда набор переменных, который не поддается наблюдению, зависит от последовательности принятых решений. В этом случае DT асимметричен. В целом, Диаграммы Влияния не очень хорошо подходят для моделирования таких асимметрий, хотя некоторые эффекты могут быть устранены либо путем тщательного использования дополнительных переменных, либо путем расширения обозначения ID. Более подробную информацию об этих проблемах и возможных решениях см. в [69] и [148].
Пример 31 (Должен ли Я получить Степень Доктора Философии?). Рассмотрите возможность принятия решения о том, следует ли получать степень доктора философии в рамках нашего образования (E). Получение степени доктора философии сопряжено с затратами Uc, как в плане гонораров, так и в плане потери дохода. Однако, если у нас есть Степень Доктора Философии, у нас больше шансов получить Нобелевскую Премию (P), что, безусловно, повысит наши шансы на получение Премии\ Дохода (I), что впоследствии положительно скажется на наших финансах (UB). Эта схема показана на рис. 7.6,а). Порядок таков (исключаются пустые множества)
и
dom(E) = (получил степень доктора философии, не получил степень доктора философии) , dom(I) = (низкий, средний, высокий) , dom(P ) = (премия, без премии)
Вероятности равны
(7.3.7)
p(получить Нобелевскую премию|не получить степень доктора философии) = 0,0000001
p(низкий уровень|получить степень доктора философии, без премии) = 0,1
p (низкий уровень|не получить степень доктора философии, без премии) = 0,2
p(низкий балл | степень доктора философии, премия) = 0,01
p(низкий балл|степень доктора философии, премия) = 0,01
p(получить Нобелевскую премию|степень доктора философии) = 0,001
p(среднее значение|докторантура, без премии) = 0,5
p(среднее значение|докторантура, без премии) = 0,6
p(среднее значение|докторантура, премия) = 0,04
p(среднее значение|докторантура, без премии) = 0,04
(7.3.6)
p(высокий балл| степень доктора философии, без премии) = 0,4
p(высокий балл|степень доктора философии, без премии) = 0,2
p(высокий балл | степень доктора философии, премия) = 0,95
p (высокий балл|отсутствие степени кандидата наук, премии) = 0,95
ПРОЕКТ от 9 марта 2010 г. 113 Расширение байесовских сетей для принятия решений
Рисунок 7.6: (а): Образование E сопряжено с определенными затратами, но также дает шанс выиграть престижную научную премию. Оба эти фактора- влияют на наши вероятные доходы с соответствующими долгосрочными финансовыми выгодами. (b): Сценарий
запуска.
Полезности \ утилиты являются
UC (докторантура) = -50000, UC (без докторантуры) = 0,
(7.3.8)
УБ (низкий) = 100000, УБ (средний) = 200000, УБ (высокий) = 500000
(7.3.9)
Ожидаемая полезность образования равна
, так что U (получить Степень Доктора Философии) = 260174.000, в то время как без получения Степени Доктора Философии U (не получить Степень Доктора Философии) = 240000.0244, что делает получение Степени Доктора Философии в среднем выгодным. Смотрите demoDecPhD.m.
Пример 32 (Доктора Наук и Начинающие компании). Диаграммы Влияния особенно полезны, когда принимается последовательность решений. Например, на рис. 7.6, b мы моделируем новую ситуацию, в которой кто-то впервые решает, стоит ли ему получать степень Доктора Философии. Спустя десять лет своей карьеры он решает, стоит ли создавать начинающую компанию. Это решение основано на том, получили они Нобелевскую Премию или нет. Решение о создании стартапа моделируется с помощью S с dom(S) = (tr, fa). Если мы создадим стартап, это будет стоить определенных денег с точки зрения инвестиций. Однако потенциальная выгода с точки зрения нашего дохода может быть высокой.
Мы моделируем это с помощью (другие необходимые записи в таблице взяты из примера(31)):
p (низкий уровень|запуск, без приза) = 0,1
p (низкий уровень|без запуска, без приза) = 0,2
p (низкий уровень|запуск, приз) = 0,005
p(низкий уровень|без запуска, приз) = 0,05
p(среднее значение|запуск, без приза) = 0,5
p(среднее значение|без запуска, без приза) = 0,6
p(среднее значение|запуск, приз) = 0,005
p(среднее значение|без запуска, приз) = 0,15
p(высокий|стартовый, без приза) = 0,4
p(высокий|без запуска, без приза) = 0,2
p(высокий|стартовый, приз) = 0,99
p(высокий|без запуска, приз) = 0,8
(7.3.11)
и
US (запуск) = -200000, US (без запуска) = 0 (7.3.12)
Наш интерес состоит в том, чтобы посоветовать, желательно ли (с точки зрения ожидаемой полезности) получить степень Доктора Философии прямо сейчас принимая во внимание, что позже кто-то может получить Нобелевскую премию, а может и не получить, и может создать, а может и не создать новую компанию.
Порядок такой (пустые наборы исключены)
E; ; P ; S; ; I (7.3.13)
114 ЧЕРНОВИК от 9 марта 2010 г. Диаграммы Влияния Решений
Рисунок 7.7: Марковский процесс принятия решений. Которое может быть использовано для моделирования задач планирования типа "как мне добраться туда, где я хочу быть, с наименьшими общими затратами?". Их легко решить с помощью алгоритма передачи сообщений.
Ожидаемая оптимальная полезность для любого состояния E равна
, где мы предполагаем, что оптимальные решения будут приняты в будущем. Вычисляя вышеизложенное, мы находим
Следовательно, нам лучше не писать Докторскую Диссертацию. Смотрите demoDecPhd.m.
7.4 Построение диаграмм влияния
Построение диаграммы влияния означает вычисление оптимального решения или последовательности решений. Здесь мы сосредоточимся на поиске оптимального первого решения. Прямой подход заключается в том, чтобы взять уравнение (7.3.2) и выполнить требуемую последовательность суммирования и максимизации в явном виде. Однако мы можем использовать структуру задачи для повышения эффективности вычислений. Чтобы разработать это, мы сначала создадим эффективный алгоритм для высокоструктурированного ID, марковского процесса принятия решений, который мы обсудим далее в разделе (7.5).
7.4.1 Эффективный вывод
Рассмотрим следующую функцию из ID на рис.(7.7)
где ; представляют собой условные вероятности, а u - полезности. Мы записываем это в терминах потенциалов поскольку это облегчит обобщение на другие случаи. Наша задача - принять оптимальное первое решение, основанное на ожидаемой оптимальной полезности
Хотя мы могли бы выполнить последовательность максимизаций и суммирования простым способом, наш интерес заключается в том, чтобы найти эффективный с точки зрения вычислений подход. Давайте посмотрим, как распределить эти операции ‘вручную’. Поскольку только u(x4 ) явно зависит от x4, мы можем записать
ДРАФТ от 9 марта 2010 г. 115 Диаграммы влияния решений
Начиная с первой строки и проводя суммирование по x4 и max по d3 , получаем новую функцию x3 ,
Кроме того, мы определяем сообщение (которым в нашем конкретном примере будет unity).
Используя это, мы можем записать
Теперь мы вычисляем сумму по x3 и максимальное значение по d2 для первой строки выше и определяем служебное сообщение
и вероятностное сообщение3
Оптимальное решение для d1 может быть получено из
Поскольку сообщение о вероятности ;2;3 (x2 ) представляет информацию о распределении , передаваемую в x2 через x3 , более интуитивно понятно записать
, который интерпретирует среднее значение полезности по отношению к распределению.
Интуитивно понятно, что мы можем продолжать в том же духе для более богатых структур, чем цепочки. Действительно, при условии, что мы сформировали подходящее дерево соединений, мы можем передавать потенциальные и полезные сообщения от группы к соседней группе, как описано в следующем разделе.
7.4.2 Использование дерева соединений
В сложных идентификаторах эффективность вычислений при выполнении последовательности суммирования и максимизации может быть проблемой, и поэтому необходимо использовать структуру в идентификаторе. Интуитивно понятно, что применим в какой- либо вид алгоритма в стиле дерева соединений. Сначала мы можем представить ID, используя потенциалы принятия решений, которые состоят из двух частей, как определено ниже.
Определение 53 (Потенциал принятия решений). Потенциал принятия решений в клике C содержит два потенциала: потенциал вероятности ;C и потенциал полезности µC . Совместные потенциалы для дерева соединений определяются как
с деревом соединений, представляющим член ;;.
3В нашем примере с MDP все эти вероятностные сообщения есть единица.
116 ПРОЕКТ диаграмм влияния решений от 9 марта 2010 г.
В этом случае существуют ограничения на триангуляцию, налагаемые частичным упорядочением, которое ограничивает последовательность исключения переменных. В результате получается так называемое Дерево сильных Связей \строгое Дерево Падалок. Приведенный здесь подход основан на [146]; аналогичный подход, который имеет дело с более общими цепными графами, приведен в [69]. Последовательность шагов, необходимых для построения JT для идентификатора, следующая:
Удаляются информационные ребра, родительские ссылки узлов принятия решений удаляются 4.
Морализаторство объединяет всех родителей оставшихся узлов.
Удаляются Служебные Узлы, удаляются служебные узлы и их родительские ссылки.
Строгая Триангуляция - это триангуляция, основанная на порядке исключения, который подчиняется частичному упорядочению переменных.
Дерево Сильных Связей Из сильно триангулированного графа сформируйте дерево связей и сориентируйте ребра по направлению к сильному корню (клике, которая появляется последней в последовательности исключения).
Клики упорядочиваются в соответствии с последовательностью, в которой они удаляются. Клики с вероятностью разделения инициализируются идентификатором, а утилиты разделения инициализируются нулем. Затем вероятностные группы инициализируются путем помещения коэффициентов условной вероятности в наименьшую доступную группу \клику\(в соответствии с порядком исключения), которая может их содержать, и аналогично для утилит. Оставшимся вероятностным группам присваивается значение идентичности, а полезностям - нулевое значение.
Пример 33 (Дерево соединений). Пример дерева соединений для идентификатора приведен на рис. 7.8, а. Те ссылки на морализацию и триангуляцию приведены на рис. 7.8, б). Ориентация ребер соответствует частичному упорядочению, при этом конечные клики первыми исчезают в последовательности суммирования и максимизации.
Побочным результатом описанных выше шагов является то, что клики описывают фундаментальные зависимости от предыдущих решений и наблюдений. Например, на рисунке (7.8a) информационная связь от f до D2 отсутствует ни на морализированно-триангулированном графике (7.8b), ни на связанных с ним кликах (7.8c). Это потому что как только e раскрыто, полезность U4 становится независимой от f, что приводит к двухветвевой структуре на рис. 7.8, b. Тем не менее, информационная ссылка от f к D2 является фундаментальной, поскольку она указывает, что f будет раскрыта – следовательно, удаление этой ссылки изменило бы частичный порядок.
Поглощение
По аналогии с определением сообщений в разделе(7.4.1), для двух соседних кликов C1 и C2, где C1 ближе к строгому корню JT (последней клике, определенной в порядке исключения), мы определяем
В приведенном выше примере ;;C – это операция "обобщенной маргинализации" - она суммирует по тем элементам группы C, которые являются случайными величинами, и максимизирует по переменным решения в группе. Порядок этой последовательности сумм и максимизаций соответствует частичному порядку, определяемому ;.
Затем вычисляется поглощение от листьев к корню Дерева сильных Соединений. Затем оптимальная настройка решения D1 может быть вычислена по корневой клике. Впоследствии откат назад может составлять
4 Обратите внимание, что в случае, когда домен зависит от родительских переменных, такие ссылки должны сохраняться.
ПРОЕКТ от 9 марта 2010 г. 117 Диаграмма влияния решений
Рисунок 7.8: (а): Диаграмма влияния, адаптированная из [146]. Причинно-следственная связь соблюдена, поскольку существует направленный путь, связывающий все решения в последовательности. Частичный порядок: b ; D1 ; (e, f) ; D2 ; (·) ; D3 ; g ; D4 ; (a, c, d, h, i, j, k, l). (b): Морализированный и сильно триангулированный граф. Ссылки на морализацию выделены зеленым цветом, ссылки на сильную триангуляцию - красным. (c): Дерево Сильных Связей. Поглощение передает информацию от листьев дерева к корню.
применяется для определения оптимальной траектории принятия решения. Оптимальное решение для D может быть получено путем работы с кликой, содержащей D, которая находится ближе всего к сильному корню, и приведения всех ранее принятых решений и выявленных наблюдений в состояние доказательности. Пример смотрите в demoDecAsia.m.
Пример 34 (Поглощение в цепочке). Для ID на рис.7.7 этапы морализации и триангуляции
являются тривиальными и дают JT:
, где клики индексируются в соответствии с порядком исключения. Коэффициенты вероятности и полезности инициализируются
ЧЕРНОВИК от 9 марта 2010 г. Диаграмма влияния решений
с кликами-разделителями, инициализированными для
Обновляя разделитель, мы получаем новый вероятностный потенциал
и потенциальная полезность
На следующем шаге мы обновляем вероятностный потенциал
и потенциал полезности
Следующий разделительный потенциал для принятия решения равен
Наконец, мы получаем основной потенциал для принятия решений
и
Из конечного потенциала принятия решения мы получаем выражение
который эквивалентен тому, который был бы получен простым распределением сумм и максимизаций по исходному идентификатору. Таким образом, по крайней мере, для этого особого случая мы убедились, что подход JT дает правильные потенциалы корневых клик.
ПРОЕКТ от 9 марта 2010 г. 119 Марковские процессы принятия решений
7.5 Марковские процессы принятия решений
Рассмотрим марковскую цепочку с вероятностями перехода p(xt+1 = j|xt = i). В каждый момент времени t мы рассматриваем действие (решение), которое влияет на состояние в момент времени t + 1. Мы описываем это через
p(xt+1 = i|xt = j, dt = k). (7.5.1)
С каждым состоянием xt = i связана утилита u(xt = i), схематически изображенная на рис. 7.7. Одним из применений такой модели среды может быть помощь в планировании последовательности действий (решений), необходимых для достижения целевого состояния с минимальными суммарными затратами.
В более общем плане можно рассматривать утилиты, которые зависят от переходов и решений, u(xt+1 = i, xt = j, dt =k), а также зависящие от времени версии всех этих параметров: pt (xt+1 = i|xt = j, dt = k), ut (xt+1 = i, xt = j, dt = k). Здесь мы будем придерживаться не зависящего от времени (стационарного) случая, поскольку обобщения концептуально просты за счет сложности записи.
MDP можно использовать для решения задач планирования, например, как можно быстрее достичь желаемого целевого состояния. Определяя полезность нахождения в целевом состоянии как высокую, а в нецелевом - как низкую, в каждый момент времени t мы получаем полезность u(xt ) от нахождения в состоянии xt . Для положительных полезностей общая полезность любого пути принятия решения о состоянии x1:T , d1:T определяется как (при условии, что мы знаем начальное состояние x1 )
, и вероятность, с которой это произойдет, задается через
В момент времени t = 1 мы хотим принять то решение d1, которое приведет к максимальной ожидаемой общей полезности
Наша задача - вычислить U (d1 ) для каждого состояния из d1, а затем выбрать это состояние с максимальной ожидаемой общей полезностью. Чтобы эффективно выполнять суммирование и максимизацию, мы могли бы использовать подход дерева соединений, как описано в предыдущем разделе. Однако в этом случае идентификатор достаточно прост, чтобы можно было использовать метод прямой передачи сообщений для вычисления ожидаемой полезности.
7.5.1 Максимизация ожидаемой полезности за счет передачи сообщений
Рассмотрим MDP
Для конкретного примера на рис. 7.7 совместная модель BN и утилиты имеет вид
Чтобы решить, как принять первое оптимальное решение, нам нужно вычислить
Поскольку только u(x4 ) явно зависит от x4, мы можем записать
ПРОЕКТ от 9 марта 2010 г. Марковские процессы принятия решений
Для каждой строки мы распределяем операции:
Теперь мы начинаем с первой строки и выполняем суммирование по x4 и максимизацию по d3 . Это дает новую функцию x3 ,
, которые мы можем включить в следующую строку
Аналогично, теперь мы можем выполнить суммирование по x3 и max по d2, чтобы определить новую функцию
, чтобы получить
Учитывая U (d1 ) выше, мы можем найти оптимальное решение d1 по формуле
А как насчет d;2? Имейте в виду, что когда мы придем к принятию решения d2, мы будем иметь в виду x1, x2 и d2 . Затем мы можем найти d;2 по формуле
Впоследствии мы можем вернуться назад и найти d;3. В общем случае оптимальное решение задается формулой
7.5.2 Уравнение Беллмана
В Марковском Процессе Принятия Решений, как описано выше, мы можем рекурсивно определять служебные сообщения как
Чаще всего значение нахождения в состоянии xt определяется как
и запишем затем эквивалентную рекурсию
ЧЕРНОВИК от 9 марта 2010 г. 121 Временно неограниченных MDPs
Тогда оптимальное решение d;t определяется как
Уравнение (7.5.19) называется уравнением Беллмана[30]5 .
7.6 Неограниченные во времени MDP
В предыдущем обсуждении MDPs мы предполагали заданное конечное время T, начиная с которого можно передавать сообщения обратно с конца цепочки. Случай с бесконечным T может показаться неточным, поскольку сумма полезностей
в общем, будет неограниченным. Есть простой способ избежать этой трудности. Если мы допустим, что u; = maxs u(s) - это наибольшее значение полезности, и рассмотрим сумму измененных полезностей для выбранного коэффициента дисконтирования 0<;<1
где мы использовали результат для геометрического ряда. В пределе T ; ; это означает, что суммарная модифицированная полезность ; t u(xt ) конечна. Единственное изменение, которое требуется внести в наше предыдущее обсуждение, - это включить фактор ; в определении сообщения. Предполагая, что мы находимся в состоянии конвергенции, мы определяем значение v(xt = s), зависящее только от состояния s, а не от времени. Это означает, что мы заменяем зависящее от времени уравнение рекурсии значений Беллмана (7.5.19) стационарным уравнением
Затем нам нужно решить уравнение (7.6.3) для значения v(s) для всех состояний s. Оптимальная политика принятия решений, когда человек находится в состоянии xt = s, определяется как
Для детерминированного перехода p (т.е. для каждого решения d доступно только одно состояние s`) это означает, что наилучшим решением является то, которое приводит нас к доступному состоянию с наибольшим значением.
Уравнение (7.6.3) кажется простым для решения. Однако операция max означает, что уравнения нелинейны по значению v и решение в замкнутой форме недоступно. Двумя популярными методами решения уравнения (7.6.3) являются итерация Значений и Политики, которые мы опишем ниже. Когда число состояний равно очень большой, требуются приближенные решения. Методы выборки и уменьшения размерности состояний описаны в [58].
7.6.1 Итерация значений
Наивная процедура заключается в повторении уравнения (7.6.3) до сходимости, предполагая некоторое начальное предположение о значениях (скажем, равномерное). Можно показать, что эта процедура итерации значений гарантированно приведет к уникальному оптимуму[34]. Скорость сходимости в некоторой степени зависит от скидки ; – чем меньше ;, тем быстрее происходит сходимость. Пример итерации значений приведен на рис. 7.10.
5Аналог непрерывного времени имеет долгую историю в физике и называется уравнением Гамильтона-Якоби и позволяет решать MDP путем передачи сообщений, что является частным случаем более общего подхода к дереву соединений, описанного ранее в разделе (7.4.2).
122 ПРОЕКТ от 9 марта 2010 г. Временно неограниченные MDP
Рисунок 7.9: Состояния, определенные на двумерной сетке. В каждом квадрате верхняя часть
левое значение - это номер состояния, а нижнее правое — полезность пребывания в этом состоянии. ‘Агент" может перемещаться из состояния в соседнее состояние, как указано. Задача состоит в том, чтобы решить эту проблему таким образом, чтобы для любой позиции (состояния) было известно, как оптимально двигаться, чтобы максимизировать ожидаемую полезность. Это означает, что нам нужно двигаться к целевым состояниям (состояниям с ненулевой полезностью). Смотрите демонстрацию demoMDP.
Рисунок 7.10: Итерация значений для набора из 225 состояний, соответствующего двумерной сетке размером 15 ; 15. Разрешены детерминированные переходы к соседям по сетке, {оставаться, влево, вправо, вверх, вниз}. Существует три целевых состояния, каждое из которых имеет полезность 1 – все остальные состояния имеют полезность 0. На графе показано значение v(s) для ; = 0,9 после 30 итераций обновления значения, где состояние указывает точку на сетке x ; y. Оптимальным решением для любого состояния на сетке является переход в соседнее состояние с наибольшим значением. Смотрите демонстрацию demoMDP.
7.6.2 Итерация политики
На итерации политики мы сначала предполагаем, что знаем оптимальное решение d; (s) для любого состояния s. Мы можем использовать это в уравнении (7.6.3), чтобы получить
Максимизация по d исчезла, поскольку мы предположили, что уже знаем оптимальное решение для каждого состояния s. Для фиксированного d; (s) уравнение (7.6.5) теперь линейно по значению. Определяя векторы ценности v и полезности u и матрицу переходов P,
в матричной записи, уравнение (7.6.5) становится
Эти линейные уравнения легко решаются с помощью Исключения Гаусса. Используя это, оптимальной политикой является повторно вычисленное с использованием уравнения (7.6.4). Два шага - определение значения и повторный расчет политики - повторяются до тех пор, пока не будет достигнута сходимость.
На Итерации Политики мы вычисляем начальное значение d; (s), затем решаем линейные уравнения (7.6.5) для этого значения, а затем повторно вычисляем оптимальное решение. Смотрите demoMDP.m для сравнения итераций значений и политик, а также подход в стиле EM, который мы обсудим в следующем разделе.
Пример 35 (MDP для сетевого мира). Набор состояний, определенных в сетке, утилиты для нахождения в сетевом состоянии приведены на рис. 7.9, для которой агент детерминированно переходит в соседнее состояние сетки на каждом временном шаге. После инициализации значения каждого состояния сетки по единице\ едино, приведенное значение для каждого состояния приведено на рис.7.10. Затем задается оптимальная политика путем перехода к соседнему состоянию сетки с наибольшим значением.
ЧЕРНОВИК от 9 марта 2010 г. 123 Вероятностный вывод и планирование
Рисунок 7.11: (а): Марковский процесс принятия решений . (b): Соответствующий планировщик вероятностных выводов.
7.6.3 Проклятие размерности
Рассмотрим следующую задачу о Ханойской Башне. Имеется 4 колышка a, b, c, d и 10 дисков, пронумерованных от 1 до 10. Вы можете перемещать один диск с одной привязки на другую, однако вам не разрешается класть диск с большим номером поверх диска с меньшим номером. Начиная со всех дисков на привязке a, как вы можете переместить их все на привязку d за минимальное количество ходов?
Это, по-видимому, простой марковский процесс принятия решений, в котором переходам разрешены перемещения дисков. Если мы используем x для представления состояния дисков на 4-х привязках, то получим 410 = 1048576 состояний (некоторые из них эквивалентны перестановке привязок, что уменьшает это значение в 2 раза). Такое большое количество состояний делает этот наивный подход проблематичным с точки зрения вычислений.
Многие интересные задачи реального мира страдают от этого большого количества состояний, так что наивный подход, основанный на том, что мы описали, является вычислительно неосуществимым. Поиск эффективных точных, а также приближенных представлений состояний является ключевым аспектом для решения крупномасштабных MDP, см., например, [193].
7.7 Вероятностный вывод и планирование
Альтернативой классическим методам решения MDP является использование стандартных методов обучения вероятностных моделей, таких как алгоритм Максимизации Математического Ожидания. Для этого нам сначала нужно записать задачу максимизации ожидаемой полезности в подходящей форме. Для этого мы сначала обсудим, как MDP может быть выражен как максимизация формы сети убеждений, в которой найденные параметры относятся к политике.
7.7.1 Нестационарный Марковский Процесс Принятия Решений
Рассмотрим MDP на рис.(7.11а), в котором для простоты мы предполагаем, что знаем начальное состояние x1 = x1. Затем наша задача состоит в том, чтобы найти решения, которые максимизируют ожидаемую полезность, на основе последовательного процесса принятия решений. Первое решение d1 задается путем максимизации ожидаемой полезности:
В более общем плане эту утилиту можно эффективно вычислить, используя стандартную процедуру передачи сообщений:
где
124 ПРОЕКТ от 9 марта 2010 г. Вероятностный вывод и планирование
7.7.2 Нестационарный планировщик вероятностных выводов
В качестве альтернативы приведенному выше описанию MDP рассмотрим Сеть Убеждений (рис.7.11, б), в которой у нас есть полезность, связанная с последним моментом времени[279]. Тогда ожидаемая полезность определяется как
Здесь термины p(dt |xt , nt ) - это "распределение политик", которые мы хотим изучить, а ;t — параметры из t-го распределения политик. Давайте предположим, что у нас есть по одной на каждый момент времени, так что ;t - это функция, которая отображает состояние x на распределение вероятности принятия решений. Наш интерес состоит в том, чтобы найти распределения политик ;1, ;2 , которые максимизируют ожидаемую полезность. Поскольку каждый временной шаг имеет свое собственное значение ;t и для каждого состояния x2 = x2, у нас есть отдельное неограниченное распределение p (d2 | x2 , ;2) для оптимизации, и мы можем записать
Это показывает, что при условии отсутствия ограничений на распределение политик (для каждого момента времени существует отдельная политика), нам разрешается распределять максимальные значения по отдельным политикам внутри суммирования.
В более общем плане, за конечное время T можно определить сообщения для решения задачи оптимального распределения политик
при
Для детерминированной политики допустимо только одно состояние, так что
где d;t (x) - это функция политики, которая сопоставляет состояние x с единственным решением d. Поскольку у нас есть отдельная функция политики для каждого времени t, уравнение (7.7.7) сводится к
что эквивалентно уравнению (7.7.2).
Это показывает, что решение MDP эквивалентно максимизации стандартной ожидаемой полезности, определенной в терминах Сети Убеждений, в предположении, что каждый момент времени имеет свое собственное распределение политик, и что оно является детерминированным.
7.7.3 Стационарный планировщик
Если мы пересмотрим наш простой пример, рис.7.11, б, но теперь ограничим распределение политик одинаковым на все время, p(dt |xt ,;t ) = p(dt |xt , ;) (или, более кратко, ;t = ;), то уравнение (7.7.5) примет вид
В этом случае мы не можем распределить максимизацию по политике ; на отдельные условия продукта \члены произведения\. Однако вычислить ожидаемую полезность для любой заданной политики ; просто, используя сообщение проходящие. Таким образом, можно оптимизировать ожидаемую полезность, используя стандартные процедуры численной оптимизации или, в качестве альтернативы, подход в стиле EM, который мы обсудим ниже.
ПРОЕКТ от 9 марта 2010 г. 125 Вероятностных выводов и планирования
Вариационный подход к обучению
Не теряя общности, мы предполагаем, что полезность положительна, и определяем распределение
Тогда для любого вариационного распределения q(d1 , d2 , d3 , x2 , x3 ),
Используя определение p(d1 , d2, d3 , x2 , x3) и тот факт, что знаменатель в уравнении (7.7.12) равен U (;), мы получаем оценку
Затем это дает двухэтапную процедуру в стиле EM:
На M-шаге выделяются зависимости от ;, для данного вариационного распределения qold, максимизация связанного уравнения (7.7.14) эквивалентна максимизации
Затем можно найти политику ; new, которая максимизирует E(;):
E-шаг для фиксированного ; наилучшее значение q определяется обновлением
Из этого совместного распределения, чтобы определить обновления с шагом M, нам требуются только маргинальные значения q(d1 ) и q(d2 , x2 ), которые легко получить, поскольку q - это просто первый порядок Цепочки Маркова в совместных переменных xt , dt . Например, можно записать q-распределение в виде простого графа коэффициентов цепочки, для которого можно легко выполнить предельный вывод, используя алгоритм сумм- произведения.
Эта процедура аналогична стандартной процедуре EM, описанной в разделе (11.2). Обычные гарантии переносят, таким образом что находят политики, которые увеличивает E(;), что гарантированно повысит ожидаемую полезность.
В сложных ситуациях, когда по соображениям экономии памяти оптимальное значение q не может быть использовано, может быть применена структурированная вариационная аппроксимация с ограничениями. В этом случае, как и в случае с обобщенной ЕМ, достигается только гарантированное улучшение нижней границы ожидаемой полезности. Тем не менее, это может оказаться весьма полезным в практических ситуациях, для которых могут применяться общие методы приближенного вывода.
Детерминированный случай
В частном случае, когда политика ; является детерминированной, ; просто сопоставляет каждое состояние x с единственным решением d. Запись этой карты политики в виде уравнения d; (x) (7.7.11) приводит к
Теперь мы определяем вариационное распределение только по x2 , x3 ,
126 ПРОЕКТ от 9 марта 2010 г. Вероятностный вывод и планирование
, и термин "энергия" становится
Для более общей задачи, в которой утилита находится в последний момент времени T и начальное состояние не задано, мы имеем (для стационарного перехода p(xt+1 |xt , dt ))
и
Здесь показано, как обучить стационарный MDP с использованием EM, в котором утилита определена только в последний момент времени. Ниже мы обобщим это на случай утилит в каждый момент времени как для стационарного, так и для нестационарного случаев.
7.7.4 Утилиты на каждом временном шаге
Рассмотрим обобщение, в котором у нас есть дополнительная полезность, связанная с каждым моментом времени.
Нестационарная политика
Чтобы помочь в разработке подхода, давайте рассмотрим простое включение полезностей в моменты времени t = 1, 2 для предыдущего примера. Ожидаемая полезность определяется как
Определение ценных сообщений
и
Для более общего случая, определенного за T временных интервалов, мы аналогично получаем ожидаемую полезность U (;1:T ), и наш интерес состоит в том, чтобы максимизировать эту ожидаемую полезность в отношении всех политик
Как и прежде, поскольку каждый временной интервал имеет свое собственное распределение политик для каждого состояния, мы можем распределить максимизацию, используя рекурсию
при
ДРАФТ от 9 марта 2010 127 Вероятностный вывод и планирование
Стационарная детерминированная политика
Для MDP оптимальной политикой является детерминированная[267], поэтому представляют интерес методы, которые явно стремятся к детерминированной политике. Для стационарной детерминированной политики ; мы имеем ожидаемую полезность
с учетом соглашения p(x1 |x0 , d(x0 )) = p(x1 ). Рассматриваемый как Факторный Граф, это просто цепочка, так что для любой политики d ожидаемая полезность может быть легко вычислена. В принципе, можно было бы попытаться оптимизировать U в отношении непосредственно принимаемых решений. Альтернативой является использование процедуры в стиле EM[100]. Для этого нам нужно определить (трансмерное) распределение
Константа нормализации Z(d) этого распределения равна
Если мы теперь определим вариационное распределение q (x1:t , t) и рассмотрим
это дает нижнюю границу
В терминах EM-алгоритма, для M-шага требуется зависимость только от d, которая равна
Для каждого заданного состояния s мы теперь пытаемся найти оптимальное решение d, которое соответствует максимизации
Определяя
мы видим, что для заданного s, с точностью до константы, ^;(d|s) является расхождением Кульбака-Лейблера между q(s` |s) и p(s` |s, d), так что оптимальное решение d определяется индексом распределения p(s` |s, d) наиболее близко соответствует q(s` |s):
128 ЧЕРНОВИК от 9 марта 2010 г., Другие темы
Рисунок 7.12: Пример Частично Наблюдаемый Марковский Процесс Принятия Решений (POMDP \ЧНМППР). ‘Скрытые’ переменные h никогда не наблюдаются. При решении диаграммы влияния от нас требуется сначала просуммировать по переменным, которые никогда не наблюдались; при этом будут объединены все наблюдавшиеся в прошлом переменные и решения , что означает, что любое решение в момент времени t будет зависеть от всех предыдущих решений. Обратите внимание, что принцип "не забывать " означает, что нам не нужно явно указывать, что каждое решение зависит от всех предыдущих наблюдений - это подразумевается неявно.
Шаг E касается вычисления предельных распределений, требуемых на шаге M. Оптимальное распределение q пропорционально ^p, вычисленному с помощью предыдущей функции принятия решения d:
Для постоянного коэффициента дисконтирования ; на каждом временном шаге и в остальном стационарной полезности 6
используя это
Для каждого t это простая Марковская цепочка, для которой попарные граничные значения перехода, требуемые для M-шага, уравнения (7.7.40), являются простыми. Это требует вывода в серии марковских моделей разной длины. Это может быть эффективно сделано с помощью одного прямого и обратного прохода[279]. Видеть MDPemDeterministicPolicy.m, который также рассматривает более общий случай коммунальных услуг, зависящих как от решения (действия), так и от состояния.
Обратите внимание, что этот алгоритм EM формально дает сбой в случае детерминированной среды (переход p(xt |xt;1 , dt;1 ) является детерминированным) – объяснение приведено в упражнении(75), а возможное решение - в упражнении (76) .
7.8 Дополнительные темы
7.8.1 Частично наблюдаемые MDP
В POMDP есть состояния, которые не наблюдаются. Это, казалось бы, безобидное расширение MDP однако это может привести к вычислительным трудностям. Давайте рассмотрим ситуацию на рис. 7.12 и попытаемся вычислить оптимальную ожидаемую полезность на основе последовательности суммирования и максимизации:
Сумма по скрытым переменным h1:3 объединяет все решения и наблюдения, что означает, что
у нас больше нет простой структуры цепочки для оставшихся максимизаций. Для POMDP длины t это приводит к неразрешимой проблеме, сложность которой экспоненциально возрастает в t. Альтернативный взгляд заключается в признании того, что все прошлые решения и наблюдения v1:t , d1:t;1 могут быть обобщены в терминах веры в текущее скрытое состояние p(ht |v1:t , d1:t;1 ). Это говорит о том, что вместо того, чтобы иметь фактическое состояние, как в случае с MDP, нам нужно
6В стандартной структуре MDP более распространено определение ut (xt ) = ; t;1 u(xt ), для сравнения со стандартом процедуры определения Политики/Значения, когда требуется разделить ожидаемую полезность на ;.
ПРОЕКТ от 9 марта 2010 г. Еще темы 129
чтобы использовать распределение по состояниям для представления наших текущих знаний. Таким образом, можно записать эффективный MDP, хотя для распределений по убеждениям, в отличие от конечных состояний. Для решения результирующих MDP с "бесконечным" состоянием требуются приближенные методы, и мы рекомендуем читателю ознакомиться с более специализированными текстами для изучения процедур аппроксимации. См., например, [148, 151].
7.8.2 Ограниченные служебные функции
Альтернативой решению проблем MDP является использование утилит с ограниченным доступом, которые позволяют легко найти политику. Недавно были разработаны эффективные решения для классов MDP с утилитами, ограниченными для дивергенции Кулбак-Лейблера [152, 278].
7.8.3 Обучение с подкреплением
Обучение с подкреплением в основном связано со стационарными Марковскими Процессами Принятия Решений. Дополнительная сложность заключается в том, что переход p(s` |s, d) (и, возможно, полезность) неизвестны. Первоначально "агент" начинает обучать набор состояний и полезностей (вознаграждений), связанных с принятием решений. Набор доступных состояний и связанных с ними вознаграждений заполняется по мере прохождения агентом своего окружения. Рассмотрим, например, задачу о лабиринте с задаными стартом и целью, но структура лабиринта неизвестна. Задача состоит в том, чтобы пройти от старта до цели за минимальное количество ходов по лабиринту. Очевидно, что для получения максимального ожидаемого вознаграждения требуется баланс между любопытством и действиями. Если мы проявим излишнее любопытство (не примем оптимальных решений, учитывая имеющуюся на данный момент информацию о структуре лабиринта) и продолжим исследовать возможные маршруты в лабиринте, это может плохо кончиться. С другой стороны, если мы не изучим возможные состояния лабиринта, мы можем никогда не осознаете, что существует гораздо более оптимальный путь, чем тот, который основан на наших текущих знаниях. Этот компромисс между исследованиями и эксплуатацией является центральным в трудностях RL. Подробное обсуждение обучения с подкреплением приведено в [267].
Для данного набора данных об окружающей среде X (наблюдаемые переходы и полезности) одним из аспектов проблемы RL можно считать поиск политики, которая максимизирует ожидаемое вознаграждение, учитывая только предварительные представления об окружающей среде и наблюдаемых решениях и состояниях. Если мы предположим, что знаем функцию полезности, но не знаем переход, мы можем написать
где ; представляет собой переход состояния среды,
Учитывая набор наблюдаемых состояний и решений,
где p(;) - предварительное значение для перехода. Техники, аналогичные тренировкам в стиле ЭМ, могут быть применены и в этом случае [77, 279]. Вместо того, чтобы рассматривать политику как функцию состояния и окружающей среды ;, оптимально рассматривать политику p(dt |xt , b(;)) как функцию состояния и уверений \убеждений\ в окружающей среде. Это означает, что, например, если уверение в окружающую среду имеет высокую энтропию, агент может распознать это и явно выполнить решения/действия для исследований окружающей среды. Еще одна сложность в RL заключается в том, что собранные данные X зависят от политики ;. Если мы запишем t для "эпизода", в котором соблюдается политика ;t и собираются данные Xt, то полезность политики ; с учетом всей исторической информации равна
В зависимости от обстоятельств \приоров окружающей среды\, а также от продолжительности каждого эпизода, у нас будут разные дополнительные значения для параметров среды. Если мы затем установим
это влияет на данные, которые мы собираем в следующем эпизоде Xt+1 . Таким образом, траектория политики ;1 , ;2 , . . . может сильно отличаться в зависимости от продолжительности эпизода и предшествующих событий.
130 ПРОЕКТ от 9 марта 2010 года Код
7.9 Код
7.9.1Sum/Max \Суммирование\ максимизация при частичном заказе
maxsumpot.m: Обобщенная операция исключения в соответствии с частичным заказом
sumpotID.m: Суммирование / максимальное значение идентификатора с вероятностью и возможностями принятия решения
demoDecParty.m: Демонстрация суммирования /максимального значения идентификатора
7.9.2 Деревья соединений для диаграмм влияния
Нет необходимости указывать информационные ссылки при условии, что задан частичный порядок. В коде jtreeID.m не выполняется проверка соответствия частичного порядка диаграмме влияния. В этом случае первый шаг построения дерева соединений, описанный в разделе (7.4.2), не требуется. Кроме того, морализация и удаление узлов полезности легко решается путем определения потенциалов полезности и включения их в процесс определения морализации.
Строгая триангуляция достигается с помощью простой схемы исключения переменных, которая направлена на устранение переменной с наименьшим числом соседей, при условии, что переменная может быть исключена в соответствии с указанным частичным порядком.
Дерево соединений строится только на основе последовательности исключающих клик C1 , . . . , CN ., полученной с помощью процедуры триангуляции. Затем получается дерево соединений, соединяющее клику CI с первой кликой j > i, которая связана с этой кликой. Затем клика Ci удаляется из графа. Таким образом, формируется дерево соединений связанных клик. Нам не нужны разделители для диаграммы влияния поглощения, поскольку они могут быть вычислены и отброшены "на лету".
Обратите внимание, что код вычисляет сообщения только от листьев к корню дерева соединений, чего достаточно для принятия решений в корне. Если требуется принять оптимальное решение на уровне, отличном от корневого, необходимо сгруппировать вероятности в группу\клику, которая содержит требуемое решение. Эти дополнительные сглаживания вероятности необходимы, поскольку на информацию о любых ненаблюдаемых переменных могут повлиять на решения и наблюдения в прошлом. Этот граф дополнительной прямой схемы вероятности не указан в коде и оставлен как упражнение для заинтересованного читателя.
jtreeID.m: Дерево соединений для диаграммы влияния
absorptionID.m: Поглощение на диаграмме влияния
triangulatePorder.m: Триангуляция на основе частичного упорядочения
demoDecPhD.m: Демонстрация полезности выполнения PhD и запуска
7.9.3 Пример с другом по вечеринке
Приведенный ниже код реализует пример Party-Friend в тексте. Чтобы устранить асимметрию, утилита Visit равна нулю, если Party находится в состоянии yes.
demoDecParty-Friend.m: Демонстрация для Party-Friend
7.9.4 Клиника грудной клетки с решениями
Таблица для сети клиник грудной клетки, рис.7.13, взята из упражнения(24), см. [119, 69]. Однако в таблицу p(x|e) внесены небольшие изменения. Если сделан рентгеновский снимок, то доступна информация о x . Однако, если принято решение не делать рентген, информация о x недоступна. Это форма асимметрии. Простой подход в этом случае - сделать dx родительской переменной x и
ПРОЕКТ от 9 марта 2010 г. 131 Код
s = Курение
x = Положительный рентгеновский снимок
d = Одышка (затрудненное дыхание)
e = Туберкулез или рак легких
t = Туберкулез
l = Рак легких
b = Бронхит
a= Посещал Азию
dh = Госпитализирован?
dx = Прошел рентген?
Рисунок 7.13: Диаграмма влияния для примера решения "Клиники грудной клетки".
если dx = fa, установите распределение x как неинформативное.
Эти две услуги разработаны таким образом, чтобы отражать затраты и преимущества, связанные с проведением рентгена и госпитализацией пациента:
Мы предполагаем, что знаем, бывал ли пациент в Азии, прежде чем принимать решение о проведении рентгена. Затем выполняется частичный заказ.
Демонстрационный файл demoDecAsia.m выдает результаты:
таблица полезности:
азия = да, делать рентген = да
это показывает, что оптимально делать рентген только в том случае, если пациент был в Азии.
demoDecAsia.m: Демонстрация диаграммы влияния дерева переходов
132 ЧЕРНОВИК от 9 марта 2010 года Упражнения
7.9.5 Марковские процессы принятия решений
В demoMDP.m мы рассматриваем простую двумерную сетку, в которой "агент" может перемещаться в квадрат сетки либо выше, либо ниже, либо слева, либо справа от текущего квадрата, либо оставаться в текущем квадрате. Мы определили целевые состояния (квадраты сетки), которые имеют высокую полезность, в то время как другие имеют нулевую полезность.
demoMDPclean.m: Демонстрация значения и итерации политики для простого MDP
MDPsolve.m: MDP-решатель, использующий значение или итерацию политики
MDP-решатель, использующий EM и предполагающий детерминированную политику
Следующий код7 не полностью описан в тексте, хотя метод достаточно прост и следует описанию, приведенному в разделе (7.7.3). Логический вывод выполняется с использованием простой рекурсии в стиле ;;;. Это также могло бы быть реализовано с использованием общего кода графа факторов, но было закодировано явно из соображений скорости. Код также обрабатывает более общий случай полезностей (вознаграждений) как функцию как состояния, так и действия u(xt , dt ).
MDPemDeterministicPolicy.m: MDP-решатель, использующий EM и предполагающий детерминированную политику
EMqTranMarginal.m: Предельная \прибыльная\ информация, необходимая для перехода энергетической системы на новый уровень.
EMqUtilMarginal.m: Предельная информация, необходимая для определения срока полезности энергии
EMTotalBetaMessage.m: Обратная информация, необходимая для вывода в MDP
EMminimizeKL.m: Поиск оптимального решения
EMvalueTable.m: Возвращает ожидаемое значение политики
7.10 Упражнения
Упражнение 67. Вы играете в игру, в которой вероятность вашего выигрыша равна p. Если вы выиграете игру, вы получите определенную сумму в фунтах стерлингов ;S, а если проиграете, вы потеряете определенную сумму в фунтах стерлингов ;S. Укажите, что ожидаемый выигрыш от игры составляет ;(2p ; 1)S.
Упражнение 68. Предполагается, что полезность денег зависит не от их количества, а от того, сколько их у нас по сравнению с другими людьми. Предположим распределение доходов p(i), i = 1, . . . , 10, используя гистограмму с 10 ячейками, каждая из которых представляет диапазон доходов. Используйте гистограмму, чтобы примерно отразить распределение доходов в обществе, а именно то, что большинство людей с доходами, близкими к среднему, имеют лишь несколько очень богатых и несколько крайне бедных людей. Теперь определите полезность дохода x как вероятность того, что доход x будет выше чем случайно выбранный доход y (в соответствии с определенным вами распределением) и соотнесите его с кумулятивным распределением p. Напишите программу для вычисления этой вероятности и построения графика результирующей полезности как функции дохода. Теперь повторите процедуру подбрасывания монеты, описанную в разделе (7.1.1), таким образом, чтобы в случае выигрыша ставки ваш новый доход был помещен в верхнюю ячейку гистограммы, а в случае проигрыша ваш новый доход будет помещен в нижнюю ячейку. Сравните оптимальные решения с точки зрения ожидаемой полезности в ситуациях, когда первоначальный доход человека (i) средний и (ii) намного выше среднего.
Упражнение 69.
Тест
Нефть
Сейсморазведка
Бурение
Выведите частичный порядок для идентификатора ID справа и объясните, чем этот идентификатор отличается от идентификатора ID на рис.7.5.
Упражнение 70. Этот вопрос тесно связан с demoMDP.m и представляет собой проблему, при которой пилот хочет посадить самолет.
Матрица U (x, y) в файле airplane.mat содержит утилиты для нахождения в положении x, y и представляет собой очень грубую модель взлетно-посадочной полосы и зоны руления.
7 Спасибо Тому Фермстону за написание кода.
ЧЕРНОВИК от 9 марта 2010 г. 133 Упражнения
Воздушное пространство представлено сеткой размером 18 ; 15 (Gx = 18, Gy = 15 в обозначениях, используемых в demoMDP.m). Матрица U (8, 4) = 2 показывает, что позиция (8, 4) является желаемым местом для стоянки самолета (высота самолета по вертикали не учитывается). Положительные значения в U представляют взлетно-посадочную полосу и зоны, где разрешена посадка самолета. Нулевые значения полезности представляют нейтральные позиции. Отрицательные значения представляют неблагоприятные позиции для самолета. Изучив матрицу U, вы увидите, что самолет предпочтительно не должен отклоняться от взлетно-посадочной полосы, а также должен избегать двух небольших деревень, расположенных рядом с аэропортом.
На каждом временном шаге самолет может выполнять одно из следующих действий: "Вверх", "вниз", "влево", "вправо":
Для "остаться" самолет остается в том же положении x, y".
Для "вверх" самолет перемещается в положение x, y + 1.
При нажатии кнопки "вниз" самолет перемещается в положение x, y ; 1.
При нажатии кнопки "влево" самолет перемещается в положение x ; 1, y.
При нажатии кнопки "вправо" самолет перемещается в положение x + 1, y.
Перемещение, при котором самолет покидает воздушное пространство, запрещено.
1. Полет самолета начинается в точке x = 1, y = 13. Предполагая, что действие детерминированно приводит к предполагаемому перемещению по сетке найдите оптимальную последовательность xt , yt для моментов времени t = 1, . . . , для положения самолета.
2. Пилот сообщает вам, что в самолете неисправность. Когда пилот дает команду самолету лететь вправо с вероятностью 0,1, он действительно взлетает (при условии, что остается в воздушном пространстве). Снова предположив, что полет самолета начинается в точке x = 1, y = 13, верните оптимальную последовательность xt , yt для моментов времени t = 1, ... , для положения самолета.
Упражнение 71.
Изображенная диаграмма влияния описывает первый этап игры. Решение переменная dom(d1 ) = {играть, не играть} указывает на решение о том, играть на первом этапе или нет. Если вы решите играть, стоимость c1 (играть) будет равна C1, но в противном случае стоимость не будет равна c1 (не играть) = 0. Переменная x1 описывает, выиграете вы или проиграете в игре, dom(x1 ) = {выигрыш, проигрыш}, с вероятностями:
Полезность выигрыша/проигрыша равна
Покажите, что ожидаемый выигрыш от игры в эту игру равен
Упражнение 72. В упражнении(71), приведенном выше, описан первый этап новой двухэтапной игры. Если вы выиграете первый этап x1 = победа, вы должны принять решение d2 о том, участвовать вам во втором этапе или нет: dom(d2 ) = {играть, не играть}. Если вы не выиграете первый этап, вы не сможете пройти на второй этап.
Если вы решите сыграть во втором этапе, вы выиграете с вероятностью p2 :
p(x2 = выигрыш|x1 = выигрыш, d2 = игра) = p2 (7.10.4)
Если вы решите не участвовать во втором этапе, у вас не будет шансов на победу:
p(x2 = победа|x1 = выигрыш, d2 = не сыграно) = 0 (7.10.5)
Стоимость участия во втором этапе составляет
c2 (d2 = игра) = C2 ,
134 ДРАФТ от 9 марта 2010 г. Упражнения
и коэффициент полезности выигрыша/проигрыша на втором этапе равны
u2 (x2 = выигрыш) = W2 ,u2 (x2 = проигрыш) = 0(7.10.7)
1. Нарисуйте схему влияния, описывающую эту двухэтапную игру.
2. Игроку необходимо решить, стоит ли ему вообще участвовать в первом этапе этой двухэтапной игры. Показывать что на основе принятия оптимального будущего решения d2 ожидаемая полезность, основанная на первом решении, равна:
Упражнение 73. На вашем банковском счете есть миллиард фунтов стерлингов. Вас спросят, хотите ли вы принять участие в пари, в случае выигрыша которого на ваш банковский счет поступят ;100 . Однако в случае проигрыша на вашем банковском счете останется только ;100 . Вы выиграете ставку с вероятностью pw .
1. Предполагая, что полезность определяется количеством фунтов стерлингов на вашем банковском счете, запишите формула для определения ожидаемой полезности от принятия ставки, U (bet \ставка), а также ожидаемой полезности от непринятия ставки, U (no bet \ отсутствие ставки).
2. Описанную выше ситуацию можно сформулировать по-другому. Если вы выигрываете ставку, вы получаете ;(W ; B). Если вы проиграете ставку, вы потеряете ;(B ; L). Рассчитайте ожидаемую сумму денег, которую вы выиграете, если поставите на Ugain (bet \ставка) и если не сделаете ставку на Ugain (no bet \ отсутствие ставки).
3. Покажите, что
Упражнение 74. Рассмотрим сценарий Party-Friend \"Вечеринка с друзьями", пример(30). Альтернативный вариант - заменить ссылку с Party к Uvisit \ от party к Visit\ с ограничением, что Visit может находиться в состоянии yes только в том случае, если Party находится в состоянии no.
1. Объясните, как это ограничение может быть достигнуто путем включения дополнительного аддитивного термина в утилиты, и измените demoDecPartyFriend.m соответствующим образом, чтобы продемонстрировать это.
2. Для случая, когда все полезности положительны, объясните, как можно достичь того же ограничения, используя мультипликативный коэффициент.
Упражнение 75. Рассмотрим цель
для положительной функции U (x) и что наша задача состоит в том, чтобы максимизировать F относительно ;. Ограничивающий подход в стиле Математическое ожидание- Максимизация (см. раздел(11.2)) может быть получен путем определения вспомогательного распределения
таким образом, рассматривая KL(q(x)|~p(x)) для некоторого вариационного распределения q(x), мы получаем ограничение
На M-шаге указано , что оптимальное распределение q задается формулой
На первом шаге алгоритма новые параметры ;new задаются путем максимизации "энергетического" члена
Покажем , что для детерминированного распределения
электронный шаг не выполняется, что приводит к ;new = ;old .
ЧЕРНОВИК от 9 марта 2010 г. 135 Упражнения
Упражнение 76. Рассмотрим цель
для положительной функции U (x) и
и произвольное распределение n(x). Наша задача - максимизировать F относительно ;. Как и в предыдущем упражнении показано, что если мы попытаемся использовать EM-алгоритм в пределе детерминированной модели ;= 0, то обновление не произойдет, и EM-алгоритм не сможет найти ;, который оптимизирует F0 (;).
Показать что
и, следовательно,
Покажите, что если для ; > 0 мы можем найти ;new такое , что F ; (;new ) > F; (;old ), то обязательно F0 (;new ) >F0 (;old ).
Используя этот результат, выведите алгоритм в стиле EM, который гарантирует увеличение F; (;) (если только мы уже не находимся на оптимальном значении) для ; > 0 и, следовательно, гарантирует увеличение F0 (;). Подсказка: используйте
и учтите
для некоторого вариационного распределения q(x).
Упражнение 77. Файл IDjensen.mat содержит таблицы вероятности и полезности для диаграммы влияния , представленной на рис.7.8,а. Используя BRMLtoolbox, напишите программу, которая возвращает максимальную ожидаемую полезность для этого идентификатора ID, используя строгий подход к дереву соединений, и проверьте результат путем явного суммирования и максимизации. Аналогично, ваша программа должна вывести максимальную ожидаемую полезность для обоих состояний d1 и проверить, что вычисление с использованием дерева сильных связей согласуется с результатом явного суммирования исключений и максимизации.
Упражнение 78. Для POMDP объясните структуру дерева сильных связей и соотнесите это со сложностью вывода в POMDP.
Упражнение 79.
(i) Определите частичный порядок для изображенной диаграммы идентификаторов ID. (ii) Нарисуйте (сильное) дерево соединений для этого идентификатора.
ПРОЕКТ от 9 марта 2010 г.,
6-7Байесовские рассуждения смыслы и машинное обуче
© Copyright: Джон Темплтон, 2025
Свидетельство о публикации №125110906765
Свидетельство о публикации №125110906765
Рецензии