Все связано, но не напрямую

Скрытые марковские модели хорошо подходят для моделирования последовательностей всех видов, но им все еще очень далеко до гибкости символистских правил типа «если…, то…», где условием может быть все, а вывод может стать условием в любом последующем правиле. Однако если допустить такую произвольную структуру на практике, это приведет к взрывному росту количества вероятностей, которые нам надо определить. Ученые долго не могли справиться с этой квадратурой круга и прибегали к ситуативным схемам, например приписывали правилам оценочную достоверность и кое-как их соединяли. Если из A с достоверностью 0,8 следует B, а из B с достоверностью 0,7 вытекает C, то, наверное, C следует из A с достоверностью 0,8 ? 0,7.

Проблема таких схем в том, что они могут приводить к сильным искажениям. Из двух совершенно разумных правил «если ороситель включен, трава будет мокрая» и «если трава мокрая, значит шел дождь» я могу вывести бессмысленное правило «если ороситель включен, значит шел дождь». Еще более коварная проблема заключается в том, что при применении правил с оценками достоверности одни и те же доказательства могут засчитываться дважды. Представьте, что вы читаете в New York Times сообщение о приземлении инопланетян. Не исключено, что это розыгрыш, хотя сегодня не первое апреля. Потом вы видите подобные заголовки в Wall Street Journal, USA Today и Washington Post и начинаете паниковать, как слушатели печально известной передачи Орсона Уэллса, которые приняли радиоспектакль «Война миров» за чистую монету[89]. Если, однако, вы обратите внимание на мелкий шрифт и поймете, что все четыре газеты получили новость от Associated Press, можно снова заподозрить розыгрыш, на этот раз со стороны репортера новостного агентства. Системы правил неспособны справиться с этой проблемой, равно как и наивный байесовский алгоритм: если в качестве предикторов того, что новость правдива, используются такие свойства, как «сообщила New York Times», он может только добавить «сообщило агентство Associated Press», а это лишь испортит дело.

Прорыв был сделан в начале 1980-х годов, когда Джуда Перл, профессор информатики в Калифорнийском университете в Лос-Анджелесе, изобрел новое представление — байесовские сети. Перл — один из самых заслуженных авторитетов в компьютерных науках, и его методы оставили отпечаток в машинном обучении, искусственном интеллекте и многих других дисциплинах. В 2012 году ему была присуждена премия Тьюринга.

Перл понял, что вполне допустимо иметь сложную сеть зависимостей между случайными переменными при условии, что каждая переменная прямо зависит только от нескольких других. Эти зависимости можно представить в виде графика, аналогичного тому, который мы видели при обсуждении цепей Маркова и СММ, однако теперь он может иметь любую структуру, если только стрелки не образуют замкнутые петли. Один из любимых примеров Перла — охранная сигнализация. Она должна сработать, если в дом пытается влезть грабитель, но может включиться и при землетрясении. (В Лос-Анджелесе, где живет Перл, землетрясения почти так же часты, как кражи со взломом.) Представьте, что вы засиделись на работе и вам позвонил сосед Боб, чтобы предупредить, что у вас сработала сигнализация. Соседка Клэр не звонит. Надо ли звонить в полицию? Вот график зависимостей:

Если на этом графике есть стрелка от одного узла к другому, мы говорим, что первый узел — родительский для второго. Следовательно, родители узла «Сигнализация» — «Взлом» и «Землетрясение», а «Сигнализация» будет единственным родителем узлов «Звонок Боба» и «Звонок Клэр». Байесовская сеть — это аналогичный график зависимостей, но каждой переменной присвоена табличка с ее вероятностью при всех сочетаниях ее родителей. У узлов «Взлом» и «Землетрясение» родителей нет, поэтому вероятность у них будет только одна. У «Сигнализации» их будет уже четыре: вероятность срабатывания, если нет ни взлома, ни землетрясения; вероятность срабатывания при взломе, но без землетрясения, и так далее. У узла «Звонок Боба» будут две вероятности (при наличии и отсутствии срабатывания сигнализации), и то же самое для звонка Клэр.

Это ключевой момент. Звонок Боба зависит от узлов «Взлом» и «Землетрясение», но только посредством узла «Сигнализация», то есть условно независим от взлома и землетрясения при условии срабатывания сигнализации, и то же самое с Клэр. Если сигнализация не сработала, соседи будут крепко спать и грабитель спокойно cделает свое дело. Также при условии срабатывания сигнализации звонки Боба и Клэр будут независимы друг от друга. Если бы этой структуры независимости не было, пришлось бы определить 2⁵ = 32 вероятности, по одной для каждого возможного состояния пяти переменных. (Или 31, если вы педант, поскольку последнюю можно оставить неявной.) Если ввести условную независимость, останется определить всего 1 + 1 + 4 + 2 + 2 = 10 вероятностей, то есть экономия составит 68 процентов. И это только в этом маленьком примере. Когда переменных сотни и тысячи, экономия может приближаться к 100 процентам.

Первый закон экологии, согласно биологу Барри Коммонеру, заключается в том, что все взаимосвязано. Может быть, это действительно так, но в таком случае мир был бы непостижим, если бы не спасительная условная независимость: все связано, но лишь косвенно. Если что-то происходит на расстоянии километра, повлиять на меня это может только посредством чего-нибудь в моем соседстве, пусть даже это будут световые лучи. Как заметил один шутник, благодаря пространству с нами происходит не все сразу. Иначе говоря, структура пространства — это частный случай условной независимости.

В примере с ограблением полная таблица из 32 вероятностей не представлена явно, но она содержится в наборе меньших таблиц и структуре графа. Чтобы получить P(взлом, землетрясение, сигнализация, звонок Боба, звонок Клэр), нужно только перемножить P(взлом), P(землетрясение), P(сигнализация | взлом, землетрясение), P(звонок Боба | сигнализация) и P(звонок Клэр | сигнализация). То же самое в любой байесовской сети: чтобы получить вероятность полного состояния, просто перемножьте вероятности соответствующих линий в таблицах отдельных переменных. Поэтому при условной независимости информация не теряется из-за перехода на более компактное представление, и можно легко вычислить вероятности крайне необычных состояний, включая те, что до этого никогда не наблюдались. Байесовские сети показывают ошибочность расхожего мнения, будто машинное обучение неспособно предсказывать очень редкие события — «черных лебедей», как их называет Нассим Талеб.

Оглядываясь назад, можно заметить, что наивный байесовский алгоритм, цепи Маркова и СММ — это частные случаи байесовских сетей. Вот структура наивного Байеса:

Цепи Маркова кодируют допущение, что будущее условно независимо от прошлого при известном настоящем, а СММ дополнительно предполагает, что каждое наблюдение зависит только от соответствующего состояния. Байесовские сети для байесовцев — то же самое, что логика для символистов: лингва франка[90], который позволяет элегантно кодировать головокружительное разнообразие ситуаций и придумывать алгоритмы, которые будут работать в каждой из них.

Байесовские сети можно воспринимать как «порождающую модель», рецепт вероятностного генерирования состояния мира: сначала надо независимо решить, что произошло — взлом и/или землетрясение, — затем, исходя из этого, понять, срабатывает ли сигнализация, а затем, на этой основе, звонят ли Боб и Клэр. Байесовская сеть как будто рассказывает историю: происходит A, которое ведет к B. Одновременно с B происходит C, и вместе они вызывают D. Чтобы вычислить вероятность конкретной истории, надо просто перемножить все вероятности в разных ее цепочках.

Одна из самых потрясающих областей применения байесовских сетей — моделирование взаимной регуляции генов в клетке. Попытки открыть парные корреляции между конкретными генами и заболеваниями стоили миллиарды долларов, но дали обидно скромные результаты. Теперь это не удивляет — ведь поведение клетки складывается из сложнейших взаимодействий между генами и средой, и единичный ген имеет ограниченную прогностическую силу. Однако благодаря байесовским сетям мы можем открыть эти взаимодействия при условии, что в нашем распоряжении имеются необходимые данные, а с распространением ДНК-микрочипов данных появляется все больше.

После новаторского применения машинного обучения для фильтрации спама Дэвид Хекерман решил попробовать использовать байесовские сети в борьбе со СПИДом. ВИЧ — сильный противник. Он очень быстро мутирует, поэтому к нему сложно подобрать вакцину и надолго сдержать его с помощью лекарств. Хекерман заметил, что это те же кошки-мышки, как между спамом и фильтрами, и решил применить аналогичный прием: атаковать самое слабое звено. В случае спама слабыми звеньями были в том числе URL, которые приходится использовать для приема платежа от клиента. В случае ВИЧ ими оказались небольшие участки вирусного белка, которые не могут меняться без ущерба для вируса. Если бы получилось натренировать иммунную систему узнавать такие области и атаковать содержащие их клетки, было бы несложно разработать вакцину от СПИДа. Хекерман и его коллеги использовали байесовскую сеть, чтобы выявить эти уязвимые области, и разработали механизм доставки вакцины, которая способна научить иммунную систему атаковать их. Система работает у мышей, и в настоящее время готовятся клинические исследования.

Часто бывает, что даже после того, как все условные независимости учтены, у некоторых узлов байесовской сети все равно остается слишком много родителей. В некоторых сетях так густо от стрелок, что, если их распечатать, страница будет черной (физик Марк Ньюман называет их «абсурдограммы»). Врачу нужно одновременно диагностировать все возможные у пациента заболевания, а не только одно, а каждая болезнь — это родительский узел многих симптомов. Высокая температура может быть вызвана не только гриппом, а любым количеством состояний, и совершенно безнадежно пытаться предсказать ее вероятность при каждом возможном их сочетании. Но не все потеряно. Вместо таблицы, в которой указаны условные вероятности узла для каждого состояния родителей, можно получить более простое распределение. Самый популярный вариант — это вероятностная версия операции «логическое ИЛИ»: любая причина сама по себе может вызвать высокую температуру, но каждая причина с определенной вероятностью этого не сделает, даже если обычно ее достаточно. Хекерман и другие обучили байесовские сети, которые диагностируют таким образом сотни инфекционных заболеваний, а Google применяет гигантские сети такого рода в AdSense — системе автоматического подбора рекламы для размещения на веб-страницах. Сети связывают миллионы относящихся к контенту переменных друг с другом и с 12 миллионами слов и фраз более чем 300 миллионами стрелок, каждая из которых получена на основе сотни миллиардов отрывков текстов и поисковых запросов.

Более веселый пример — сервис Microsoft Xbox Live, в котором байесовская сеть используется для оценки игроков и подбора игроков схожего уровня. Результат игры — вероятностная функция уровня навыков противника, и благодаря теореме Байеса можно сделать вывод о навыках игрока на основании его побед и поражений.