Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 194
Текст из файла (страница 194)
Джуди Перл разработал метод передачи сообщений для осуществления вероятностного вывода в древовидных сетях [! 186) и ввел понятие полидревовидных сетей [796], а также объяснил важность составления причинных, а не диагностических вероятностных моделей, в противовес системам, основанным на использовании факторов определенности, которые были в моде в то время. Первой экспертной системой, в которой использовались байесовские сети, стала Сопу!псе [795], [797). Многие новейшие медицинские системы включают систему Мцп1п для диагностирования нейромускульных нарушений )27] и систему Ра!)зГзпс)ег для выявления патологий [640). Одними из наиболее широко используемых систем на основе байесовских сетей оказались модули диагностики и восстановления (например, модуль Рппгег %!гагс)) в операционной системе М!сгозоГг %!пс)озуз [178] и О(Гзсе Азз!агап! в пакете М!сговой Ой)се [685).
Перл [1189) разработал алгоритм кластеризации для точного вероятностного вывода в байесовских сетях общего вида, используя метод преобразования в ориентированное полидерево кластеров, в котором для достижения согласованности по переменным, разделяемым между кластерами, использовалась передача сообщений.
'с И. Дж. Гуд бьп главным статистиком в группе Тьюринга, занимавшейся раскрытием шифров во время Второй мировой войны. В книге 2001: д эрасе остуввеу !2641 выражена благодарность Гуду и Минскому за их вклад в тот научный прорыв, который привел к разработке компьютера НА) 9000. 708 Часть |/. Неопределенные знания и рассуждения в условиях неопределенности Аналогичный подход, разработанный статистиками Дэвидом Шпигельхальтером и Штеффеном Лауритценом [895], [1449], основан на преобразовании в неориентированную сеть (Маркова). Этот подход реализован в системе Ной[о, которая представляет собой эффективное и широко применяемое инструментальное средство для формирования рассуждений в условиях неопределенности [27]. Росс Шахтер, работающий в сообшестве исследователей диаграмм влияния, разработал точный метод, который основан на сокраШении сети, управляемом целями, с использованием преобразований, сохраняющих апостериорную вероятность [1383].
Метод устранения переменных, описанный в данной главе, ближе всего по замыслу к метолу Шахтера, на основе которого разработан алгоритм символического вероятностного вывода (ЯугпЬойс РгоЬаЬ111зг]с 1пГегепсе — БР!) [1385]. В алгоритме 5Р! предпринимается попытка оптимизировать вычисление деревьев выражений, подобных приведенному на рис. 14.8. Описанный в данной книге алгоритм больше всего напоминает алгоритм, разработанный Чжангом и Пулом [1643], [1644]. Критерии отсечения нерелевантных переменных были разработаны Гейгером и др.
[530], а также Лауритценом и др. [894]; приведенный в данной книге критерий представляет собой простой частный случай этих критериев. Рина Дехтер [369] показала, что идея устранения переменной по сути идентична ъ. непоследовательному динамическому программированию [1!7] — алгоритмическому подходу, который может использоваться для решения целого ряда задач вероятностного вывода в байесовских сетях, например поиска наиболее вероятного объяснения для множества наблюдений. В этом подходе алгоритмы байесовских сетей применяются в сочетании с соответствуюшими методами решения задач СВР и дается прямая оценка меры сложности точного вывода в терминах ширины гипердерева сети.
Вопрос о включении непрерывных случайных переменных в байесовские сети рассматривался Перлом [1191], а также Шахтером и Кенли [1386]; в этих статьях обсуждаются сети, солержашие только непрерывные переменные с линейными гауссовыми распределениями. Проблема включения дискретных переменных исследовалась Лауритценом и Вермутом [896], а полученные результаты реализованы в системе сН[ЗО!Х [1154]. Пробит-распределение впервые было исследовано Финнеем [469], который назвал его сигмоидальным распределением. Это распределение широко использовалось для моделирования феномена дискретного выбора и может быть дополнено, если требуется его применение в тех случаях, когда количество выборов превышает два [3!8]. В [133] приведено обоснование целесообразности использования логит-распределения в данной научной области.
Купер [29!] показал, что обшая проблема вероятностного вывода в байесовских сетях без ограничений является ХР-трудной, и Пол Дагум и Майк Луби [319] показали, что ХР-трудной является соответствующая задача аппроксимации. Одной из серьезных проблем при использовании методов кластеризации и устранения переменной является также пространственная сложность. Применение метода определения условий выбора множества разрыва цикла, который был разработан для задач СБР в главе 5, позволяет исключить необходимость построения экспоненциально больших таблиц.
В байесовской сети множеством разрыва цикла является множество вершин, позволяющих после их конкретизации свести оставшиеся вершины к поли- дереву, которое может быть решено с линейными затратами времени и пространства. Поиск ответа на запрос осуществляется путем суммирования по всем конкретизациям множества разрыва цикла, поэтому обшие требования к пространству все Глава 14. Вероятностные рассуждения 709 еще остается линейными [119!].
В [323] описан рекурсивный алгоритм обусловливания, который допускает широкий выбор компромиссных методов сокращения затрат пространства/времени. В настоящее время разработка быстрых алгоритмов аппроксимации для вероятностного вывода в байесовских сетях представляет собой очень активную научную область, которая испытывает положительное влияние со стороны статистики, компьютерных наук и физики. Способ формирования выборок с исключением представляет собой общий метод, давно известный статистикам; он был впервые применен к байесовским сетям Максом Хенрионом [648], который назвал этот метод логическим формированием выборок.
Метод взвешивания с учетом правдоподобия, который был разработан Фунтом и Чангом [512], а также Шахтером и Пеотом [1387], представляет собой пример широко известного статистического метода формирования выборок с учетом важности. Результаты крупномасштабного применения метода взвешивания с учетом правдоподобия в области медицинской диагностики опубликованы в [1407]. Ченг и Друздзель [247] описали адаптивную версию метода взвешивания с учетом правдоподобия, которая действует очень успешно, даже если свидетельства имеют крайне низкое априорное правдоподобие. Развитие алгоритмов Монте-Карло на основе цепи Маркова (Маг[гоч сйаш Моп!е Саг!о — МСМС) началось с создания алгоритма Метрополиса, впервые опубликованного в статье [1036], которая стала также первой публикацией сведений об алгоритме эмуляции отжига (см, главу 4). Формирователь выборок Гиббса был предложен в [535] для вероятностного вывода в неориентированных сетях Маркова.
Применение алгоритма МСМС к байесовским сетям было предложено Перлом [1190]. Статьи, собранные в [554], охватывают широкий диапазон направлений использования алгоритма МСМС, многие из которых были разработаны при создании широко известного пакета Вцйз [555], В этой главе не рассматривались два очень важных семейства методов аппроксимации.
Первым из них является семейство методов ~в. вариационной аппроксимации, которые могут использоваться для упрогцения сложных вычислений любых типов. Основная идея состоит в том, что должна быть предложена сокращенная версия первоначальной задачи, с которой легче работать, но которая напоминает первоначальную задачу настолько близко, насколько это возможно.
Сокращенная задача описывается с помощью некоторых Ъ. вариациониых параметров Х, которые корректируются с целью минимизации функции расстояния !э между оригинальной и сокращенной задачами, часто путем решения системы уравнений дп7ду=о. Во многих случаях могут быть получены строгие верхние и нижние границы. Вариационные методы уже лавно использовались в статистике [1333].
В статистической физике метод Ъ. поля осредненных величин (шеап бе!О) представляет собой особую вариационную аппроксимацию, в которой предполагается, что отдельные переменные, входящие в состав модели, являются полностью независимыми. Эта идея была применена для поиска решений в крупных неориентированных сетях Маркова [! !74], [!209]. В [1353] представлены результаты разработки математических основ применения вариационных методов к байесовским сетям и получения точных аппроксимаций нижней границы для сигмоидальных сетей с использованием методов поля осредненных величин. Эта методология была дополнена в [720] для получения нижней и верхней границ. Обзор вариационных подходов приведен в [748]. 710 Часть Ъ'.
Неопределенные знания и рассуждения в условиях неопределенности Второе важное семейство алгоритмов аппроксимации основано на алгоритме Перла передачи сообшений в полидереве [1186]. Как указал Перл [1 191], этот алгоритм может применяться к сетям общего типа. Иногда результаты оказываются неправильными, или же не удается добиться нормального завершения работы алгоритма, но во многих случаях полученные значения близки к истинным значениям. Так называемый подход с Ж распространением оценок степени уверенности (или с циклическим распространением) привлекал мало внимания до тех пор, пока Макэлис и др. [1027] не обнаружили, что передача сообщений в многосвязной байесовской сети полностью аналогична вычислениям, выполняемым в алгоритме 'в.турбодекодирования (!игбо десог)!п8) [1!5], который оказался крупным научным прорывом в области разработки эффективных кодов коррекции ошибок. Из этого следует вывод, что способ циклического распространения быстро и точно работает в очень крупных и тесно связанных сетях, используемых для декодирования, и поэтому может найти более широкое применение.
В [1105] представлены результаты эмпирического исследования областей использования этого алгоритма. В [1630] подробно описаны связи между методом циклического распространения и идеями статистической физики. Связь между вероятностными методами и языками первого порядка была впервые исследована Карнапом [225]. В [513] и [!373] определен язык, в котором вероятности могут быть обьединены с высказываниями первого порядка и для которого моделями являются вероятностные показатели в возможных мирах. В рамках искусственного интеллекта эта идея была разработана Нильссоном для пропозициональной логики [1144] и Халперном для логики первого порядка [607]. Результаты первого обширного исследования проблем представления знаний в таких языках были опубликованы в ]51], а в [! 577] приведен обзор первых подходов к реализации этих способов представления на основе формирования эквивалентных пропозициональных байесовских сетей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
