БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕТКИ
Широкое использование сетей для представления вероятностной информации началось с первых десятилетий XX столетия, когда были опубликованы работы Сьюэлла Райта по вероятностному анализу генетического наследования и показателей развития животных [1622], [1624]. Одна из его сетей показана на обложке данной книги. И.Дж. Гуд [575] в сотрудничестве с Аланом Тьюрингом разработал вероятностные представления и методы байесовского вероятностного вывода, которые могут рассматриваться как предшествующие современным байесовским сетям, хотя указанная статья не часто цитируется в данном контексте10. Та же статья является оригинальным литературным источником с описанием модели зашумленного OR.
Форма представления для задач принятия решений с помощью диаграммы влияния, которая была встроена в представление DAG для случайных переменных, использовалась в анализе принятия решений с конца 1970-х годов (глава 16), но для вычислений применялись только методы перебора. Джуди Перл разработал метод передачи сообщений для осуществления вероятностного вывода в древовидных сетях [1186] и ввел понятие полидревовидных сетей [796], а также объяснил важность составления причинных, а не диагностических вероятностных моделей, в противовес системам, основанным на использовании факторов определенности, которые были в моде в то время. Первой экспертной системой, в которой использовались байесовские сети, стала Convince [795], [797]. Многие новейшие медицинские системы включают систему Munin для диагностирования нейромускульных нарушений [27] и систему Pathfinder для выявления патологий [640]. Одними из наиболее широко используемых систем на основе байесовских сетей оказались модули диагностики и восстановления (например, модуль Printer Wizard) в операционной системе Microsoft Windows [178] и Office Assistant в пакете Microsoft Office [685].
10 И. Дж. Гуд был главным статистиком в группе Тьюринга, занимавшейся раскрытием шифров во время Второй мировой войны. В книге 2 001: A Space Odyssey [264] выражена благодарность Гуду и Минскому за их вклад в тот научный прорыв, который привел к разработке компьютера HAL 9000.
Перл [1189] разработал алгоритм кластеризации для точного вероятностного вывода в байесовских сетях общего вида, используя метод преобразования в ориентированное полидерево кластеров, в котором для достижения согласованности по переменным, разделяемым между кластерами, использовалась передача сообщений.
Аналогичный подход, разработанный статистиками Дэвидом Шпигельхальтером и Штеффеном Лауритценом [895], [1449], основан на преобразовании в неориентированную сеть (Маркова). Этот подход реализован в системе Hugin, которая представляет собой эффективное и широко применяемое инструментальное средство для формирования рассуждений в условиях неопределенности [27]. Росс Шахтер, работающий в сообществе исследователей диаграмм влияния, разработал точный метод, который основан на сокращении сети, управляемом целями, с использованием преобразований, сохраняющих апостериорную вероятность [1383].
Метод устранения переменных, описанный в данной главе, ближе всего по замыслу к методу Шахтера, на основе которого разработан алгоритм символического вероятностного вывода (Symbolic Probabilistic Inference — SPI) [1385]. В алгоритме SPI предпринимается попытка оптимизировать вычисление деревьев выражений, подобных приведенному на рис. 14.8. Описанный в данной книге алгоритм больше всего напоминает алгоритм, разработанный Чжангом и Пулом [1643], [1644]. Критерии отсечения нерелевантных переменных были разработаны Гейгером и др. [530], а также Лауритценом и др. [894]; приведенный в данной книге критерий представляет собой простой частный случай этих критериев. Рина Дехтер [369] показала, что идея устранения переменной по сути идентична непоследовательному динамическому программированию [117]— алгоритмическому подходу, который может использоваться для решения целого ряда задач вероятностного вывода в байесовских сетях, например поиска наиболее вероятного объяснения для множества наблюдений. В этом подходе алгоритмы байесовских сетей применяются в сочетании с соответствующими методами решения задач CSP и дается прямая оценка меры сложности точного вывода в терминах ширины гипердерева сети.
Вопрос о включении непрерывных случайных переменных в байесовские сети рассматривался Перлом [1191], а также Шахтером и Кенли [1386]; в этих статьях обсуждаются сети, содержащие только непрерывные переменные с линейными гауссовыми распределениями. Проблема включения дискретных переменных исследовалась Лауритценом и Вермутом [896], а полученные результаты реализованы в системе cHUGIN [1154]. Пробит-распределение впервые было исследовано Фин-неем [469], который назвал его сигмоидальным распределением. Это распределение широко использовалось для моделирования феномена дискретного выбора и может быть дополнено, если требуется его применение в тех случаях, когда количество выборов превышает два [318]. В [133] приведено обоснование целесообразности использования логит-распределения в данной научной области.
Купер [291] показал, что общая проблема вероятностного вывода в байесовских сетях без ограничений является NP-трудной, и Пол Дагум и Майк Луби [319] показали, что NP-трудной является соответствующая задача аппроксимации. Одной из серьезных проблем при использовании методов кластеризации и устранения переменной является также пространственная сложность. Применение метода определения условий выбора множества разрыва цикла, который был разработан для задач CSP в главе 5, позволяет исключить необходимость построения экспоненциально больших таблиц. В байесовской сети множеством разрыва цикла является множество вершин, позволяющих после их конкретизации свести оставшиеся вершины к полидереву, которое может быть решено с линейными затратами времени и пространства. Поиск ответа на запрос осуществляется путем суммирования по всем конкрети-зациям множества разрыва цикла, поэтому общие требования к пространству все еще остается линейными [1191]. В [323] описан рекурсивный алгоритм обусловливания, который допускает широкий выбор компромиссных методов сокращения затрат пространства/времени.
В настоящее время разработка быстрых алгоритмов аппроксимации для вероятностного вывода в байесовских сетях представляет собой очень активную научную область, которая испытывает положительное влияние со стороны статистики, компьютерных наук и физики. Способ формирования выборок с исключением представляет собой общий метод, давно известный статистикам; он был впервые применен к байесовским сетям Максом Хенрионом [648], который назвал этот метод логическим формированием выборок. Метод взвешивания с учетом правдоподобия, который был разработан Фунгом и Чангом [512], а также Шахтером и Пеотом [1387], представляет собой пример широко известного статистического метода формирования выборок с учетом важности. Результаты крупномасштабного применения метода взвешивания с учетом правдоподобия в области медицинской диагностики опубликованы в [1407]. Ченг и Друздзель [247] описали адаптивную версию метода взвешивания с учетом правдоподобия, которая действует очень успешно, даже если свидетельства имеют крайне низкое априорное правдоподобие.
Развитие алгоритмов Монте-Карло на основе цепи Маркова (Markov chain Monte Carlo — МСМС) началось с создания алгоритма Метрополиса, впервые опубликованного в статье [1036], которая стала также первой публикацией сведений об алгоритме эмуляции отжига (см. главу 4). Формирователь выборок Гиббса был предложен в [535] для вероятностного вывода в неориентированных сетях Маркова. Применение алгоритма МСМС к байесовским сетям было предложено Перлом [1190]. Статьи, собранные в [554], охватывают широкий диапазон направлений использования алгоритма МСМС, многие из которых были разработаны при создании широко известного пакета Bugs [555].
В этой главе не рассматривались два очень важных семейства методов аппроксимации. Первым из них является семейство методов вариационной аппроксимации, которые могут использоваться для упрощения сложных вычислений любых типов. Основная идея состоит в том, что должна быть предложена сокращенная версия первоначальной задачи, с которой легче работать, но которая напоминает первоначальную задачу настолько близко, насколько это возможно. Сокращенная задача описывается с помощью некоторых вариационных параметров X, которые корректируются с целью минимизации функции расстояния D между оригинальной и сокращенной задачами, часто путем решения системы уравнений dD/dX=0. Во многих случаях могут быть получены строгие верхние и нижние границы. Вариационные методы уже давно использовались в статистике [1333]. В статистической физике метод поля осредненных величин (mean field) представляет собой особую вариационную аппроксимацию, в которой предполагается, что отдельные переменные, входящие в состав модели, являются полностью независимыми. Эта идея была применена для поиска решений в крупных неориентированных сетях Маркова [1174], [1209]. В [1353] представлены результаты разработки математических основ применения вариационных методов к байесовским сетям и получения точных аппроксимаций нижней границы для сигмоидальных сетей с использованием методов поля осредненных величин. Эта методология была дополнена в [720] для получения нижней и верхней границ. Обзор вариационных подходов приведен в [748].
Второе важное семейство алгоритмов аппроксимации основано на алгоритме Перла передачи сообщений в полидереве [1186]. Как указал Перл [1191], этот алгоритм может применяться к сетям общего типа. Иногда результаты оказываются неправильными, или же не удается добиться нормального завершения работы алгоритма, но во многих случаях полученные значения близки к истинным значениям. Так называемый подход с распространением оценок степени уверенности (или с циклическим распространением) привлекал мало внимания до тех пор, пока Макэлис и др. [1027] не обнаружили, что передача сообщений в многосвязной байесовской сети полностью аналогична вычислениям, выполняемым в алгоритме турбодекодирования (turbo decoding) [115], который оказался крупным научным прорывом в области разработки эффективных кодов коррекции ошибок. Из этого следует вывод, что способ циклического распространения быстро и точно работает в очень крупных и тесно связанных сетях, используемых для декодирования, и поэтому может найти более широкое применение. В [1105] представлены результаты эмпирического исследования областей использования этого алгоритма. В [1630] подробно описаны связи между методом циклического распространения и идеями статистической физики.
Связь между вероятностными методами и языками первого порядка была впервые исследована Карнапом [225]. В [513] и [1373] определен язык, в котором вероятности могут быть объединены с высказываниями первого порядка и для которого моделями являются вероятностные показатели в возможных мирах. В рамках искусственного интеллекта эта идея была разработана Нильссоном для пропозициональной логики [1144] и Халперном для логики первого порядка [607]. Результаты первого обширного исследования проблем представления знаний в таких языках были опубликованы в [51], а в [1577] приведен обзор первых подходов к реализации этих способов представления на основе формирования эквивалентных пропозициональных байесовских сетей. В дальнейшем исследователи пришли к пониманию важности полных баз знаний, т.е. баз знаний, в которых, как и в байесовских сетях, определяется уникальное совместное распределение по всем возможным мирам. Методы осуществления этого были основаны на вероятностных версиях логического программирования [1226], [1352] или на семантических сетях [823]. Реляционные вероятностные модели такого типа, описанные в данной главе, были глубоко исследованы Пфеффером [1210]. В [1179] приведены результаты исследования проблем реляционной неопределенности и неопределенности идентичности в рамках моделей RPM, а также результаты использования вероятностного вывода с помощью алгоритма МСМС.
Как было описано в главе 13, после появления первых вероятностных систем в начале 1970-х годов интерес к ним упал и частично образовался вакуум, который стали заполнять альтернативные методы. Для использования в медицинской экспертной системе Mycin [1406] был разработан подход на основе факторов определенности, который был предназначен как для выработки проектных решений, так и для моделирования субъективных суждений, формируемых в условиях неопределенности. В сборнике статей Rule-Based Expert Systems [204] приведен полный обзор системы Mycin и других систем, разработанных на ее основе (см. также [1458]). Дэвид Хекер-ман [639] показал, что в некоторых случаях слегка модифицированная версия на основе вычислений с фактором определенности позволяет получить правильные вероятностные результаты, но в других случаях приводит к серьезной переоценке важности свидетельств. В экспертной системе Prospector [420] используется подход на основе правил, в котором правила были обоснованы с помощью предположения о глобальной независимости (которое редко оправдывается).
Теория, получившая название теории Демпстера—Шефера, была впервые опубликована в статье Артура Демпстера [382], который предложил обобщение способа представления вероятностей в виде интервальных значений и обосновал правила комбинирования для их использования. После того как в дальнейшем была опубликована работа Гленна Шефера [1388], теория Демпстера—Шефера стала рассматриваться как научный подход, способный конкурировать с вероятностным подходом. В [1319] приведены результаты анализа связи между теорией Демпстера—Шефера и стандартной теорией вероятностей. Шеной [1401] предложил метод принятия решений с помощью доверительных функций Демпстера—Шефера.
Нечеткие множества были разработаны Лотфи Задэ [1637] в целях устранения широко признанных сложностей при предоставлении точных входных данных для интеллектуальных систем. В [1649] приведено исчерпывающее введение в теорию нечетких множеств; статьи по приложениям нечетких множеств собраны в [1648]. Как уже было указано в данной книге, нечеткую логику часто трактуют неправильно, усматривая в ней прямого конкурента для теории вероятностей, тогда как в этой теории фактически рассматриваются другие вопросы. Для вычислений с учетом неопределенности в нечетких системах была предложена теория возможностей (possibility theory) [1638], которая имеет много общего с теорией вероятностей. В [419] предложен исчерпывающий обзор по проблеме связей между теорией возможностей и теорией вероятностей.
Пробуждение в последнее время интереса к вероятностным методам в основном вызвано тем открытием, что байесовские сети являются удобным средством представления и использования информации об условной независимости. Но сторонникам байесовского подхода пришлось бороться за его дальнейшее распространение; некоторое представление о том, какие дебаты они вели со своими противниками, можно получить, ознакомившись с воинственной статьей Питера Чизмена In Defense of Probability [242] и с его последующей статьей An Inquiry into Computer Understanding [243] (с комментариями). Одним из принципиальных возражений противников байесовского подхода (и последователей логицистского подхода) было то, что числовые вычисления, применяемые в теории вероятностей, не очевидны для интуитивного восприятия и претендуют на наличие нереального уровня точности в наших неопределенных знаниях. Результаты разработки Веллманом качественных вероятностных сетей [1574] привели к созданию чисто качественной абстракции байесовских сетей, в которой используется понятие положительных и отрицательных влияний между переменными. Веллман показал, что во многих случаях такая информация является достаточной для принятия оптимальных решений и не требует точного указания вероятностных значений. В работе Эднана Дарвича и Мэтта Гинсберга [324] выявлены основные свойства методов обусловливания и комбинирования свидетельств, разработанных в рамках теории вероятностей, и показано, что эти методы могут также применяться при формировании логических рассуждений и рассуждений по умолчанию.
Система диагностики сердечных заболеваний, описанная в данной главе, разработана Лукасом [962]. К другим отраслевым приложениям байесовских сетей относится выполненные в компании Microsoft работы по выявлению целей пользователя компьютера на основании анализа его действий [685] и по фильтрации нежелательной электронной почты [1344], а также работа Electric Power Research Institute по контролю над электрическими генераторами [1088] и работа NASA по выводу крайне чувствительной ко времени информации на дисплей в Центре управления полетами в Хьюстоне [684].
Некоторые важные ранние статьи по применению методов формирования рассуждений в условиях неопределенности в искусственном интеллекте собраны в антологиях Readings in Uncertain Reasoning [1389] и Uncertainty in Artificial Intelligence [768]. Наиболее важной отдельной публикацией, посвященной развитию байесовских сетей, безусловно, является книга Probabilistic Reasoning in Intelligent Systems [1191]. Более свежие материалы можно найти в нескольких превосходных книгах, включая [734], [746] и [893]. Новейшие результаты исследований в области вероятностных рассуждений публикуются и в профильных журналах по искусственному интеллекту, таких как Artificial Intelligence и Journal of AI Research, и в более специализированных журналах, таких как International Journal of Approximate Reasoning. Многие статьи по графическим моделям, к которым относятся байесовские сети, публикуются в статистических журналах. Превосходными источниками сведений о современных исследованиях являются труды конференций Uncertainty in Artificial Intelligence (UAI), Neural Information Processing Systems (NIPS) и Artificial Intelligence and Statistics (AISTATS).