Верховный алгоритм - Педро Домингос

Если состояния и наблюдения — не дискретные, а непрерывные переменные, СММ превращается в так называемый фильтр Калмана88. Экономисты используют эти фильтры, чтобы убрать шум из временных рядов таких величин, как внутренний валовой продукт (ВВП), инфляция и безработица. «Истинные» значения ВВП — это скрытые состояния. На каждом временном отрезке истинное значение должно быть схоже и с наблюдаемым, и с предыдущим истинным значением, поскольку в экономике резкие скачки встречаются нечасто. Фильтр Калмана находит компромисс между этими условиями и позво­ляет получить более гладкую, но соответствующую наблюдениям кривую. Кроме того, фильтры Калмана не дают ракетам сбиться с курса, и без них человек не побывал бы на Луне.

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

Скрытые марковские модели хорошо подходят для моделирования последовательностей всех видов, но им все еще очень далеко до гибкости символистских правил типа «если…, то…», где условием может быть все, а вывод может стать условием в любом последующем правиле. Однако если допустить такую произвольную структуру на практике, это приведет к взрывному росту количества вероятностей, которые нам надо определить. Ученые долго не могли справиться с этой квадратурой круга и прибегали к ситуативным схемам, например приписывали правилам оценочную достоверность и кое-как их соединяли. Если из 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делает свое дело. Также при условии срабатывания сигнализации звонки Боба и Клэр будут независимы друг от друга. Если бы этой структуры независимости не было, пришлось бы определить 25 = 32 вероятности, по одной для каждого возможного состояния пяти переменных. (Или 31, если вы педант, поскольку последнюю можно оставить неявной.) Если ввести условную независимость, останется определить всего 1 + 1 + 4 + 2 + 2 = 10 вероятностей, то есть экономия составит 68 процентов. И это только в этом маленьком примере. Когда переменных сотни и тысячи, экономия может приближаться к 100 процентам.

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

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

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

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

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