Определение путем обучения структур байесовских сетей
До сих пор предполагалось, что структура байесовской сети задана, и мы просто пытаемся определить в процессе обучения ее параметры, тогда как структура самой сети представляет основные причинные знания о проблемной области, которые часто может без особых затруднений сформулировать не только специалист, но даже неопытный пользователь. Но в некоторых случаях причинная модель может оказаться недоступной или стать предметом спора (например, некоторые корпорации долгое время утверждали, что курение не является причиной рака), поэтому важно понять, как может быть определена путем обучения структура байесовской сети на основе данных. В настоящее время алгоритмы структурного обучения находятся на начальном этапе развития, поэтому в данном разделе будет приведен лишь краткий обзор основных идей.
Наиболее очевидным подходом к решению этой задачи является поиск качественной модели. Эту работу можно начать с модели, не содержащей связей, и приступить к введению родительских узлов для каждого узла, согласуя параметры с помощью только что описанных методов и измеряя точность результирующей модели. Еще один вариант состоит в том, что можно начать с исходного предположения о структуре и использовать поиск с восхождением к вершине или с эмуляцией отжига для внесения модификаций, возвращая параметры после каждого изменения в структуре. Модификации могут включать обращение, добавление или удаление дуг. В этом процессе следует избегать появления циклов, поскольку во многих алгоритмах принято предположение, что для переменных задано упорядочение и что узел может иметь родительские узлы только среди тех узлов, которые присутствуют перед ним в этом упорядочении (точно так же, как и в процессе создания сети, описанном в главе 14). Для достижения полной общности необходимо также обеспечить поиск среди возможных упорядочений.
Существуют два альтернативных метода принятия решения о том, нужно ли прекратить поиск, поскольку обнаружена приемлемая структура. Первый из них предусматривает проверку того, действительно ли в данных удовлетворяются предположения об условной независимости, неявно заданные в этой структуре. Например, сам факт использования наивной байесовской модели для задачи с рестораном равносилен предположению о том, что справедливо приведенное ниже соотношение, поэтому можно проверить по самим данным, соблюдается ли это соотношение применительно к соответствующим условным частотам.
-Р {Fri / Sat, Bar \ WillWait) = Р (Fri/Sat \ WillWait) Р (Bar | WillWait)
Итак, даже если полученная структура описывает истинный причинный характер проблемной области, наличие статистических флуктуации в наборе данных означает, что это уравнение никогда не будет выполняться точно, поэтому необходимо выполнить подходящую статистическую проверку для определения того, есть ли достаточно весомые свидетельства нарушения гипотезы о независимости. Сложность результирующей сети будет зависеть от пороговых значений, используемых для этой проверки — чем строже проверка на независимость, тем больше связей будет введено в сеть и тем выше опасность чрезмерно тщательной подгонки.
Подход, более совместимый с идеями, изложенными в этой главе, состоит в определении того, до какой степени предложенная модель объясняет данные (в вероятностном смысле). Но необходимо соблюдать осторожность при выборе способа измерения этой степени. Если будет просто предпринята попытка найти гипотезу с максимальным правдоподобием, то в конечном итоге будет получена полносвязная сеть, поскольку введение дополнительных родительских узлов для некоторого узла
не позволяет повысить его правдоподобие (см. упр. 20.9). Поэтому приходится каким-то образом вводить штраф за сложность модели. В подходе MAP (или MDL) просто вычитаются штрафные оценки из значений правдоподобия каждой структуры (после настройки параметров) до сравнения различных структур, а в байесовском подходе налагается совместное распределение априорных вероятностей на структуры и параметры. Но обычно количество структур, по которым должно быть выполнено суммирование, слишком велико (оно определяется суперэкспоненциальной зависимостью от количества переменных), поэтому большинство практиков используют алгоритм МСМС для формирования выборок по структурам.
Применение способа штрафования за сложность (с помощью либо методов MAP, либо байесовских методов) влечет за собой появление важной связи между оптимальной структурой и характером представления для распределений условных вероятностей в сети. При использовании табличных распределений значения штрафов за сложность для распределения вероятностей узла растут экспоненциально в зависимости от количества родительских узлов, а при использовании, скажем, распределений зашумленного ИЛИ они растут только линейно. Это означает, что обучение с помощью моделей зашумленного ИЛИ (или других компактно параметризованных моделей), как правило, приводит к созданию в результате обучения таких структур, в которых имеется больше родительских узлов, чем при обучении с помощью табличных распределений.