Оглядываясь назад, можно заметить, что наивный байесовский алгоритм, цепи Маркова и СММ — это частные случаи байесовских сетей. Вот структура наивного Байеса:
Цепи Маркова кодируют допущение, что будущее условно независимо от прошлого при известном настоящем, а СММ дополнительно предполагает, что каждое наблюдение зависит только от соответствующего состояния. Байесовские сети для байесовцев — то же самое, что логика для символистов: лингва франка[90], который позволяет элегантно кодировать головокружительное разнообразие ситуаций и придумывать алгоритмы, которые будут работать в каждой из них.
Байесовские сети можно воспринимать как «порождающую модель», рецепт вероятностного генерирования состояния мира: сначала надо независимо решить, что произошло — взлом и/или землетрясение, — затем, исходя из этого, понять, срабатывает ли сигнализация, а затем, на этой основе, звонят ли Боб и Клэр. Байесовская сеть как будто рассказывает историю: происходит A, которое ведет к B. Одновременно с B происходит C, и вместе они вызывают D. Чтобы вычислить вероятность конкретной истории, надо просто перемножить все вероятности в разных ее цепочках.
Одна из самых потрясающих областей применения байесовских сетей — моделирование взаимной регуляции генов в клетке. Попытки открыть парные корреляции между конкретными генами и заболеваниями стоили миллиарды долларов, но дали обидно скромные результаты. Теперь это не удивляет — ведь поведение клетки складывается из сложнейших взаимодействий между генами и средой, и единичный ген имеет ограниченную прогностическую силу. Однако благодаря байесовским сетям мы можем открыть эти взаимодействия при условии, что в нашем распоряжении имеются необходимые данные, а с распространением ДНК-микрочипов данных появляется все больше.
После новаторского применения машинного обучения для фильтрации спама Дэвид Хекерман решил попробовать использовать байесовские сети в борьбе со СПИДом. ВИЧ — сильный противник. Он очень быстро мутирует, поэтому к нему сложно подобрать вакцину и надолго сдержать его с помощью лекарств. Хекерман заметил, что это те же кошки-мышки, как между спамом и фильтрами, и решил применить аналогичный прием: атаковать самое слабое звено. В случае спама слабыми звеньями были в том числе URL, которые приходится использовать для приема платежа от клиента. В случае ВИЧ ими оказались небольшие участки вирусного белка, которые не могут меняться без ущерба для вируса. Если бы получилось натренировать иммунную систему узнавать такие области и атаковать содержащие их клетки, было бы несложно разработать вакцину от СПИДа. Хекерман и его коллеги использовали байесовскую сеть, чтобы выявить эти уязвимые области, и разработали механизм доставки вакцины, которая способна научить иммунную систему атаковать их. Система работает у мышей, и в настоящее время готовятся клинические исследования.
Часто бывает, что даже после того, как все условные независимости учтены, у некоторых узлов байесовской сети все равно остается слишком много родителей. В некоторых сетях так густо от стрелок, что, если их распечатать, страница будет черной (физик Марк Ньюман называет их «абсурдограммы»). Врачу нужно одновременно диагностировать все возможные у пациента заболевания, а не только одно, а каждая болезнь — это родительский узел многих симптомов. Высокая температура может быть вызвана не только гриппом, а любым количеством состояний, и совершенно безнадежно пытаться предсказать ее вероятность при каждом возможном их сочетании. Но не все потеряно. Вместо таблицы, в которой указаны условные вероятности узла для каждого состояния родителей, можно получить более простое распределение. Самый популярный вариант — это вероятностная версия операции «логическое ИЛИ»: любая причина сама по себе может вызвать высокую температуру, но каждая причина с определенной вероятностью этого не сделает, даже если обычно ее достаточно. Хекерман и другие обучили байесовские сети, которые диагностируют таким образом сотни инфекционных заболеваний, а Google применяет гигантские сети такого рода в AdSense — системе автоматического подбора рекламы для размещения на веб-страницах. Сети связывают миллионы относящихся к контенту переменных друг с другом и с 12 миллионами слов и фраз более чем 300 миллионами стрелок, каждая из которых получена на основе сотни миллиардов отрывков текстов и поисковых запросов.
Более веселый пример — сервис Microsoft Xbox Live, в котором байесовская сеть используется для оценки игроков и подбора игроков схожего уровня. Результат игры — вероятностная функция уровня навыков противника, и благодаря теореме Байеса можно сделать вывод о навыках игрока на основании его побед и поражений.
Проблема логического вывода
Во всем этом есть, к сожалению, большая загвоздка. Само то, что байесовская сеть позволяет компактно представлять вероятностное распределение, еще не означает, что с ее помощью можно эффективно рассуждать. Представьте, что вы хотите вычислить P(взлом | звонок Боба, нет звонка Клэр). Из теоремы Байеса вы знаете, что это просто P(взлом) P(звонок Боба, нет звонка Клэр | взлом) / P(звонок Боба, нет звонка Клэр), или, эквивалентно, P(взлом, звонок Боба, нет звонка Клэр) / P(звонок Боба, нет звонка Клэр). Если бы в нашем распоряжении была полная таблица вероятностей всех состояний, можно было бы вычислить обе эти вероятности, сложив соответствующие строки в таблице. Например, P(звонок Боба, нет звонка Клэр) — это сумма вероятностей во всех линейках, где Боб звонит, а Клэр не звонит. Но байесовская сеть не дает полной таблицы. Ее всегда можно построить на основе отдельных таблиц, но необходимое для этого время и пространство растет экспоненциально. На самом деле мы хотим вычислить P(взлом | звонок Боба, нет звонка Клэр) без построения полной таблицы. К этому, в сущности, сводится проблема логического вывода в байесовских сетях.
Во многих случаях удается это сделать и без экспоненциального взрыва. Представьте, что вы командир отряда, который колонной по одному глубокой ночью пробирается по вражеским тылам. Надо убедиться, что никто не отстал и не потерялся. Можно остановиться и всех пересчитать, но нет времени. Более разумное решение — спросить идущего за вами солдата, сколько за ним человек. Солдаты будут задавать тот же самый вопрос по цепочке друг другу, пока последний не скажет: «Никого нет». Теперь предпоследний солдат может сказать: «один», — и так далее обратно к голове колонны, и каждый солдат будет добавлять единицу к количеству за ним. Так вы узнаете, сколько солдат за вами идет, и останавливаться не придется.
В Siri та же самая идея используется, чтобы по звукам, которые она улавливает микрофоном, вычислить вероятность, что вы сказали, например, «позвони в полицию». Эту фразу можно считать отрядом слов, марширующих друг за другом по странице. Слово «полиция» хочет знать вероятность своего появления, но для этого ему надо определить вероятность «в», а предлог, в свою очередь, должен узнать вероятность слова «позвони». Поэтому «позвони» вычисляет собственную вероятность и передает ее предлогу «в», который делает то же самое и передает результат слову «полиция». Теперь «полиция» знает свою вероятность, на которую повлияли все слова в предложении, и при этом не надо составлять полную таблицу из восьми вероятностей (первое слово «позвони» или нет, второе слово «в» или нет, третье слово «полиция» или нет). В реальности Siri учитывает все слова, которые могли бы появиться в каждой позиции, а не просто стоит ли первым слово «позвони» и так далее, однако алгоритм тот же самый. Наверное, Siri слышит звуки и предполагает, что первое слово либо «позвони», либо «позови», второе либо «в», либо «к», а третье — либо «полицию», либо «позицию». Может быть, по отдельности самые вероятные слова — это «позови», «к» и «позицию». Но тогда получится бессмысленное предложение: «Позови к позицию». Поэтому, принимая во внимание другие слова, Siri делает вывод, что на самом деле предложение — «Позвони в полицию». Программа звонит, и, к счастью, полицейские успевают вовремя и ловят забравшегося к вам вора.
Та же
