ЕЩЕ ОДНО ВОЗВРАЩЕНИЕ В МИР ВАМПУСА
Теперь мы можем применить многие идеи, изложенные в этой главе, для решения задач в мире вампуса, требующих использования вероятностных рассуждений (полное описание мира вампуса приведено в главе 7). Неопределенность в мире вампуса возникает из-за того, что датчики агента сообщают только частичную, локальную информацию об этом мире. Например, на рис. 13.2 показана ситуация, в которой каждый из трех достижимых квадратов ([1,3], [2,2] и [3,1]) может содержать яму. Чисто логический вывод не позволяет прийти к каким-либо заключениям о том, какой квадрат с наибольшей вероятностью окажется безопасным, поэтому логический агент может быть вынужден выбирать среди них случайным образом. В этом разделе будет показано, что вероятностный агент может действовать гораздо успешнее, чем логический агент.
В ситуации, показанной на рис. 13.2, а, свидетельство состоит из наблюдаемого ветерка (или его отсутствия) в каждом посещенном квадрате, в сочетании с тем фактом, что каждый такой квадрат не содержит ямы. Эти факты можно сокращенно представить как b=—ib1/1 л Ь1/2 a b2il и known=—\р1Л л —ip1/2 л —ip2,i. Мы заинтересованы в получении ответов на такие запросы, как Р (Р1/31 known, b): насколько велика вероятность того, что квадрат [1,3] содержит яму, если даны результаты всех наблюдений, сделанных до сих пор?
Для получения ответа на этот запрос можно воспользоваться стандартным подходом, основанном на уравнении 13.6 и реализованном в алгоритме Enumerate-Joint-Ask, а именно просуммировать элементы из таблицы полного совместного распределения. Допустим, что Unknown (Неизвестное) — составная переменная, которая состоит из переменных pif j для квадратов, отличных от квадратов Known и квадрата запроса [1,3]. В таком случае с помощью уравнения 13.6 получаем следующее:
Р (Pi, з | known, Ъ) = а * Р (Pi,з, unknown, known, Ъ) unknown
Полное совместное распределение вероятностей уже было задано, поэтому задача решена, точнее, осталось только выполнить вычисления. Количество неизвестных квадратов равно 12, поэтому требуемая сумма состоит из 212=4096 термов. Вообще говоря, количество термов в этой сумме растет экспоненциально в зависимости от количества квадратов.
Но интуиция подсказывает, что здесь есть какое-то упущение. Безусловно, напрашивается вопрос, не являются ли другие квадраты не относящимися к делу? Ведь содержимое квадрата [4,4] не влияет на то, имеется ли яма в квадрате [1,3]! И действительно, эта догадка является правильной. Пользуясь ею, предположим, что Fringe — переменные (отличные от переменной запроса), которые описывают свойства квадратов, соседних по отношению к посещенным квадратам; в данном случае таковыми являются только [2,2] и [3,1]. Кроме того, допустим, что Other — это переменные, которые относятся к другим неизвестным квадратам; в данном случае количество других квадратов равно 10, как показано на рис. 13.2, б. Ключевая идея состоит в том, что данные о наблюдаемом ветерке являются условно независимыми от других переменных, если даны условные переменные, переменные периферии и переменная запроса. После этой догадки остается лишь, так сказать, дело техники — выполнить несколько алгебраических операций.
Чтобы воспользоваться этой идеей, необходимо преобразовать формулу запроса в такую форму, в которой данные о наличии ветерка становятся условно зависимыми от всех других переменных, а затем упростить полученное выражение с использованием утверждения об условной независимости, как показано ниже.
В этом преобразовании на конечном этапе используется утверждение об условной независимости. Теперь первый терм в выражении не зависит от других переменных, поэтому можно переместить операцию суммирования внутрь выражения, следующим образом:
Р (Pi,31 known, b)
= а Р (b\ known, Pi,з, fringe) Р (Pi,3, кпown, fringe, other)
fringe other
Согласно утверждению о независимости, соответствующему приведенному в уравнении 13.15, терм априорной вероятности может быть факторизован, после чего все эти термы могут быть переупорядочены следующим образом:
Р (Pi,з | known, b)
= а V {b \ known, Pi,3, fringe) P (Pi,3) P(known) P( fringe) P{other)
fringe other
= a P{known) P (Pi,ъ) P (bI known, Pi,3, fringe) P( fringe) P( other)
fringe other
= a' P(Pi,3) P (b\ known, Pi,3, fringe) P( fringe)
fringe
В этом преобразовании на последнем этапе постоянный терм Р(known) вводится в нормализующую константу и используется тот факт, что выражение
Јotherp(°ther) Равно 1-
Теперь в сумме по периферийным переменным Р2;2 и р3#1 осталось только четыре терма. Использование свойств независимости и условной независимости позволило полностью исключить из рассмотрения другие квадраты. Обратите внимание на то, что выражение P (Ь| known, Pi,3, fringe) равно 1, если периферия совместима с данными наблюдений о наличии ветерка, а в противном случае равно 0. Поэтому для получения каждого значения Р1/3 проводится суммирование по логическим моделям для периферийных переменных, которые согласованы с известными фактами. Эти модели и связанные с ними априорные вероятности, Р{ fringe), показаны на рис. 13.3. Итак, получаем следующие значения:
V {Pll3\ known, Ь) = а1 < 0.2(0.04 + 0.16 + 0.16), 0.8(0.04 + 0.16) > « <0.31, 0.69>
Это означает, что квадрат [1,3] (а также квадрат [3,1], поскольку для него могут быть выполнены подобные вычисления) содержит яму с вероятностью приблизительно 31%. Аналогичное вычисление, которое авторы рекомендуют выполнить читателю, показывает, что квадрат [2,2] содержит яму с вероятностью приблизительно 86% Агент в мире вампуса определенно должен избегать квадрата [2,2]!
В данном разделе наглядно продемонстрировано, что даже такие задачи, которые внешне кажутся очень сложными, могут быть точно сформулированы в терминах теории вероятностей и решены с использованием простых алгоритмов. Для получения эффективных решений могут применяться соотношения, определяющие свойства независимости и условной независимости, которые позволяют упростить требуемые операции суммирования. Эти соотношения часто соответствуют нашему интуитивному пониманию того, как следует выполнять декомпозицию задачи. В следующей главе будут разработаны формальные представления для таких соотношений, а также алгоритмы, оперирующие с соответствующими представлениями и позволяющие эффективно осуществлять вероятностный вывод.
В данной главе было показано, что понятие вероятности лежит в основе правильных способов формирования рассуждений о неопределенности.
• Неопределенность возникает и по причине экономии усилий, и из-за отсутствия знаний. Неопределенности нельзя избежать в сложных, динамичных или труднодоступных мирах.
• Наличие неопределенности означает, что многие упрощения, возможные в дедуктивном логическом выводе, становятся больше не допустимыми.
• В оценках вероятности выражается неспособность агента прийти к определенному решению, касающемуся истинности высказывания. Вероятности являются выражением степени уверенности агента.
РЕЗЮМЕ
• К основным типам вероятностных утверждений относятся утверждения, касающиеся априорных вероятностей и условных вероятностей простых и сложных высказываний.
• Полное совместное распределение вероятностей задает вероятность каждого полного присваивания значений случайным переменным. Это распределение обычно слишком велико для того, чтобы его можно было создать или использовать в явной форме.
• Аксиомы вероятностей регламентируют возможные присваивания вероятностей высказываниям. Агент, не учитывающий в своих действиях эти аксиомы, ведет себя в некоторых обстоятельствах нерационально.
• Если полное совместное распределение доступно, оно может использоваться для получения ответов на запросы путем суммирования элементов с данными об атомарных событиях, соответствующих высказываниям запроса.
• Наличие свойства абсолютной независимости между подмножествами случайных переменных позволяет факторизовать полное совместное распределение на меньшие совместные распределения. Это дает возможность значительно уменьшить сложность, но редко встречается на практике.
• Правило Байеса позволяет вычислять неизвестные вероятности из известных условных вероятностей, обычно в причинном направлении. При наличии многочисленных свидетельств применение правила Байеса, как правило, приводит к возникновению таких же проблем масштабирования, которые возникают при использовании полного совместного распределения.
• Свойство условной независимости, вызванное наличием прямых причинных связей в рассматриваемой проблемной области, может обеспечить факторизацию полного совместного распределения на меньшие условные распределения. В наивной байесовской модели предполагается наличие условной независимости всех переменных действия, если задана одна переменная причины; размеры этой модели увеличиваются линейно, в зависимости от количества результатов.
• Агент в мире вампуса может рассчитывать вероятности ненаблюдаемых объектов мира и использовать их для принятия лучших решений по сравнению с теми, которые принимает простой логический агент.