Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 186
Текст из файла (страница 186)
Требования процесса устранения переменной к времени и пространству зависят в основном от размера наибольшего фактора, сформированного в процессе работы данного алгоритма. А этот размер, в свою очередь, зависит от порядка устранения переменных и от структуры сети. Сеть с описанием взлома, приведенная на рис. 14.2, принадлежит к семейству сетей, в которых имеется самое большее один неорнентированный путь между любыми двумя вершинами в сети. Такие сети называются 'т.одиосвязными (гйп81у соппес(ег[) сетями, или Ж полидеревьями (ро!у(гее), и обладают одним особо привле- б82 Частью'. Неопределенные знания и рассуждения в условиях неопрелеленности кательным свойством: сУ временная и пространственная сложность точного вероятностного вывода в полидеревьях линейно зависят от размера сечи.
В данном случае размер определяется как количество элементов таблиц СРТ; если количество родительских вершин каждой вершины ограничено некоторой константой, то сложность также будет зависеть линейно от количества вершин. Эти результаты справедливы для любого упорядочения, совместимого с топологическим упорядочением сети (упр. 14.7). Для 'т. многосвязных (пш!(!р1у соппес(ед) сетей, подобных приведенной на рис. 14.9, а, процедура устранения переменной в наихудшем случае может иметь экспоненциальную временную и пространственную сложность, даже если количество родительских вершин в расчете на каждую вершину ограниченно. В этом нет ничего удивительного, если учесть, что ог- вероятностный вывод в байесовских сетях является 7чр-трудным, поскольку включает вывод в пропозициональной логике как частный случай.
Фактически можно показать (упр. 14.8), что эта задача является настолько трудной, насколько трулна задача вычисления количества выполняющих присваиваний для формулы пропозициональной логики. Это означает, что данная задача является нР-трудной (читается "шарп-Р-трудной", или "диез-Р-трудной"), т.е. строго труднее, чем )ч)Р-полные задачи. Существует тесная связь между сложностью вероятностного вывода в байесовской сети и сложностью задач удовлетворения ограничений (Сопмгаш( Ба(!з1ас(!оп РгоЫеш — СБР). Как было показано в главе 5, трудность решения дискретной задачи СБР зависит от того, насколько "древовидным" является ее граф ограничений.
Такие показатели, как ширина гипердерева, которые устанавливают пределы сложности решения задачи СБР, могут также применяться непосредственно к байесовским сетям. Более того, существует возможность обобщить алгоритм устранения переменной таким образом, чтобы он позволял находить решения не только в байесовских сетях, но и в задачах СБР.
Алгоритмы кластеризации Описанный выше алгоритм устранения переменной является простым и эффективным средством получения ответов на отдельные запросы. Если же возникает необходимость вычислить апостериорные вероятности для всех переменных в сети, то этот алгоритм может оказаться менее эффективным. Например, в сети с полидревовидной структурой для этого потребуется выдать 0(п) запросов со стоимостью 0(п) каждый, что в сумме составляет затраты времени 0(п') .
Использование алгоритмов 'а. кластеризации (известных также под названием алгоритмов Ъ.дерева соединения — )о!и (гее), позволяет сократить это время до 0(п) . По указанной причине данные алгоритмы широко используются в коммерческих инструментальных средствах на основе байесовских сетей.
Основная идея кластеризации состоит в том, что отдельные узлы в дереве должны быть соединены для формирования кластерных вершин таким образом, чтобы результирующая сеть стала полидеревом. Например, многосвязная сеть, показанная на рис. 14.9, а, может быть преобразована в полилерево путем объединения вершин Ярхзп)с2ех (Опрыскиватель) и )(азп (Дождь) в кластерную вершину, называемую Брхзп)с2ех+)(азп (см. рис. 14.9, б). Эти две булевы вершины заменяются мегавершиной, которая принимает четыре возможных значения: тт, тр, Гт и рк Данная 683 Глава!4.
Вероятностные рассуждения мегавершина имеет только одну родительскую вершину — булеву переменную с2оцс)у, поэтому для нее количество обусловливающих случаев равно двум. (О=0,5 Р(с) =0,5 Р(5+Я= ) 77 7 (7 (( И'Е7 беаи 0,08 0,02 0,72 0,)8 О,)0 0,40 0,)0 0,40 О) а) рис, 14.9. Пример применения кластеризации: многосвязная сеть с таблицами условных вероят- ностей (а); кластеризованный эквивалент многосвюной сети (б) После преобразования сети в форму полидерева применяется алгоритм вероятностного вывода специального назначения. По сути этот алгоритм представляет собой одну из форм алгоритма распространения ограничений (см.
главу 5), где ограничения обеспечивают согласование соседних кластеров по апостериорной вероятности любых переменных, которые являются в них общими. При наличии тщательно продуманных средств учета этот алгоритм позволяет вычислять апостериорные вероятности для всех вершин в сети, отличных от вершин свидетельства, за время 0(п), где и теперь обозначает размер модифицированной сети. Тем не менее ХР-трудность решаемой задачи не исчезает: если сеть требует экспоненциальных затрат времени и пространства при устранении переменной, то экспоненциальные затраты времени и пространства требуются и для построения таблиц СРТ в кластеризованной сети.
14.5. ПРИБЛИЖЕННЪ|Й ВЕРОЯТНОСТНЫЙ ВЫВОД В БАЙЕСОВСКИХ СЕТЯХ Исходя из того, что точный вероятностный вывод в больших многосвязных сетях является неосуществимым, важно предусмотреть методы приближенного вероятностного вывода. В настоящем разделе описаны рандомизированные алгоритмы выборки (называемые также алгоритмами 'т. Монте-Карло), обеспечивающие получение приближенных ответов, точность которых зависит от количества сформированных выборок.
В последние годы алгоритмы Монте-Карло нашли широкое распространение в компьютерных науках для получения оценочных значений величин, которые трудно вычислить точно. Например, алгоритм эмуляции отжига, описанный в главе 4, представляет собой метод Монте-Карло для задач оптимизации. В этом разделе нас интересует применение методов выборки для вычисления апо- 684 Часть У. Неопределенные знания и рассуждения в условиях неопределенности стериорных вероятностей. Здесь описаны два семейства алгоритмов: непосредственная выборка и выборка с помошью цепи Маркова.
Два других подхода (вариационные методы и метод циклического распространения) упоминаются в библиографических и исторических заметках, приведенных в конце данной главы. Методы непосредственной выборки Примитивной операцией в любом алгоритме выборки является формирование выборок из известного распределения вероятностей. Например, подлинная монета может рассматриваться как случайная переменная Со1п со значениями <Ьеас)з, са11з> и априорным распределением Р(со1п) =<О. 5, О. 5>. Операция получения выборки из этого распределения полностью аналогична подбрасыванию монеты; с вероятностью 0,5 эта операция будет возврашать значение Ьеас)з (орел) и с такой же вероятностью — значение са11з (решка).
Если имеется источник случайных чисел в диапазоне (О, 11, сформировать любые распределения по одной переменной совсем несложно (см. упр. 14.9). В процессе случайного формирования выборки простейшего типа для байесовских сетей, рассматриваемом в этом разделе, вырабатываются события, не имеющие связанных с ними свидетельств, которые могут быть зарегистрированы в сети.
Идея этого метода состоит в том, что выборка должна формироваться последовательно по каждой переменной, в топологическом порядке. Распределение вероятностей, из которого берется выборка значения, обусловливается значениями, уже присвоенными родительским переменным этой переменной. Соответствующий алгоритм приведен в листинге 14.3. Проиллюстрируем его работу на примере сети, приведенной на рис. 14.9, а, предполагая, что имеет место упорядочение (С1оцг)у, Яргуп)с1ег, пауп, )гесСгазз], как описано ниже. Листинг 14.3. Алгоритм формирования выборки, который вырабатывает события на основании байесовской сети Еипсваоп Ргтог-яащр1е(Ьп) гесигпв событие, выработанное путем применения операции формирования выборки к априорному распределению, заданному в виде сети .Ьп фирисв: Ьп, байесовская сеть, задающая совместное распределение Р(Хы.,.,Х ) х ь- событие с и элементами Рог 1 = 1 Ео и ао х, < — случайная выборка из Р(х,)рагепсз(х,)) гееигп х 1.
Выборка из распределения Р(С1оцс)у) =<О. 5, 0.5>; предположим, что она возвращает сгце. 2. Выборка из распределения Р(Брг1п)<1ег~ с1оцс)у= отце) =<О. 1, О. 9>; предположим, что она возврашает га1зе. 3. Выборка из распределения Р(ла1п ~ с1оис)у=огне) =<О. 8, О. 2>; предположим, что она возвращает Сгце. б85 Глава 14.
Вероятностные рассуждения Ярк(хи..х,) = П Р(х,)рахепее(Х,) ) Это выражение должно показаться читателю весьма знакомым, поскольку оно определяет также вероятность события в соответствии с представлением совместного распределения в байесовской сети, как указано в уравнении 14.1. Поэтому получаем слелующее: Ярк (хи,.х ) = Р(хи..х ) Благодаря такому простому факту задача получения ответов на вопросы с помощью выборок решается очень просто. В любом алгоритме формирования выборки ответы вычисляются путем подсчета фактически сформированных выборок.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
