Одно из решений — соединить «Сообщение в New York Times» и «Сообщение в Wall Street Journal» в одну мегапеременную с четырьмя значениями: «ДаДа», если сообщают оба источника, «ДаНет», если о приземлении сообщает New York Times, но не Wall Street Journal, и так далее. Это превратит граф в цепочку из трех переменных, и все хорошо. Однако с добавлением каждого нового источника новости число значений в мегапеременной будет удваиваться. Если вместо двух источников у вас целых 50, мегапеременная получит 250 значений. Поэтому такой метод на большее не способен, а ничего лучше не придумали.
Проблема сложнее, чем может показаться на первый взгляд, потому что у байесовских сетей появляются «невидимые» стрелки, идущие вместе с видимыми. «Взлом» и «землетрясение» априорно независимы, но сработавшая сигнализация их связывает: она заставляет подозревать ограбление. Но если вы услышите по радио, что было землетрясение, то начнете предполагать, что оно и виновато. Землетрясение оправдывает срабатывание сигнализации и делает ограбление менее вероятным, а следовательно, между ними появляется зависимость. В байесовской сети все родители той же переменной таким образом оказываются взаимозависимы, что, в свою очередь, порождает еще больше зависимостей, и результирующий граф часто получается намного плотнее, чем исходный.
Критически важный вопрос для логического вывода: можно ли сделать заполненный график «похожим на дерево», чтобы ствол при этом был не слишком толстый. Если у мегапеременной в стволе слишком много возможных значений, дерево будет расти бесконтрольно, пока не заполонит всю планету, как баобабы в «Маленьком принце». В древе жизни каждый вид — это ветвь, но внутри каждой ветви есть граф, где у каждого создания имеются двое родителей, четыре внука, какое-то количество потомков и так далее. «Толщина» ветви — это размер популяции данного вида. Если ветви слишком толстые, единственный выбор — прибегнуть к приближенному выводу.
Одно из решений, приведенное Перлом в качестве упражнения в его книге о байесовских сетях, — делать вид, что в графе нет петель, и продолжать распространять вероятности туда-сюда, пока они не сойдутся. Такой алгоритм известен как циклическое распространение доверия. Вообще говоря, идея странная, но, как оказалось, во многих случаях она довольно хорошо работает. Например, это один из современных методов беспроводной связи, где случайные переменные — хитрым образом закодированные биты сообщения. Но циклическое распространение доверия может сходиться и к неправильным ответам или бесконечно изменяться (осциллировать). Еще одно решение проблемы возникло в физике, было импортировано в машинное обучение и значительно расширено Майклом Джорданом и другими учеными. Оно заключается в том, чтобы приблизить неразрешимое распределение с помощью разрешимого, оптимизировать параметры последнего и как можно ближе приблизить его к первому.
Но самый популярный вариант — утопить наши печали в вине и бродить всю ночь пьяным. По-научному это называется метод Монте-Карло в марковских цепях, или сокращенно MCMC. «Монте-Карло» потому, что в методе есть шансы, как в казино в одноименном городе, а марковские цепи упоминаются потому, что в этот метод входит последовательность шагов, каждый из которых зависит только от предыдущего. Идея MCMC заключается в том, чтобы совершать случайные прогулки, как упомянутый пьяница, перепрыгивая из одного состояния сети в другое таким образом, чтобы в долгосрочной перспективе число посещений каждого состояния было пропорционально вероятности этого состояния. Затем мы можем оценить вероятность взлома, скажем, как долю посещений состояния, в котором происходит ограбление. Удобная для анализа цепь Маркова сводится к стабильному распределению и через какое-то время начинает давать приблизительно те же ответы. Например, если вы тасуете колоду карт, через какое-то время все порядки карт станут одинаково вероятными, независимо от исходного порядка, поэтому вы будете знать, что при n возможных вариантов вероятность каждого из них будет равна 1⁄n. Весь фокус в MCMC заключается в том, чтобы разработать цепь Маркова, которая сходится к распределению нашей байесовской сети. Простой вариант — многократно циклически проходить через переменные, делая выборку каждой в соответствии с ее условной вероятностью, исходя из состояния соседей. Люди часто говорят об MCMC как о своего рода симуляции, но это не так: цепь Маркова не имитирует какой-то реальный процесс — скорее, она придумана для того, чтобы эффективно генерировать примеры из байесовской сети, которая сама по себе не является последовательной моделью.
Истоки MCMC восходят к Манхэттенскому проекту, в котором физики оценивали вероятность столкновения нейтронов с атомами, вызывающего цепную реакцию. В последующие десятилетия метод произвел такую революцию, что его часто называют одним из самых важных алгоритмов всех времен. MCMC хорош не только для вычисления вероятностей, но и для интегрирования любых функций. Без него ученые были бы ограничены функциями, которые можно интегрировать аналитически, или низкоразмерными, удобными для анализа интегралами, которые можно приблизить методом трапеций. MCMC позволяет свободно строить сложные модели, делая всю трудную работу за вас. Байесовцы, со своей стороны, обязаны MCMC растущей популярностью своих методов, вероятно, больше, чем чему-то другому.
Отрицательный момент — то, что MCMC зачастую мучительно медленно сходится или начинает обманывать, потому что кажется, что он сошелся, а на самом деле нет. В реальных распределениях обычно очень много пиков, которые, как Эвересты, взлетают над широкой равниной крохотных вероятностей. Цепь Маркова, следовательно, будет сходиться к ближайшему пику и останется там, а оценка вероятности окажется очень пристрастной: как если бы пьяница учуял запах спиртного и завис на всю ночь в ближайшей забегаловке, вместо того чтобы бесцельно слоняться по городу, как нам нужно. С другой стороны, если вместо цепи Маркова сгенерировать независимые пробы, как в более простых методах Монте-Карло, никакого запаха не будет и, вероятно, наш пьяница даже не найдет первый кабак. Это все равно что бросать дротики в карту города, надеясь, что они попадут прямиком в паб.
Логический вывод в байесовских сетях не ограничен вычислением вероятностей. К нему относится и нахождение наиболее вероятного объяснения признаков, например заболевания, которое лучше всего объясняет симптомы, или слов, которые лучше всего объясняют звуки, услышанные Siri. Это не то же самое, что просто выбрать на каждом этапе самое вероятное слово, потому что слова, которые схожи по отдельности исходя из звуков, могут реже встречаться вместе, как в примере «Позови к позицию». Однако и в таких задачах срабатывают аналогичные виды алгоритмов (именно их использует большинство распознавателей речи). Самое главное, что вывод предусматривает принятие наилучших решений не только на основе вероятности разных исходов, но и с учетом соответствующих затрат (или, говоря научным языком, полезности). Затраты, связанные с проигнорированным письмом от начальника, который просит что-то сделать завтра, будут намного выше, чем затраты на ознакомление с ненужным рекламным письмом, поэтому часто целесообразно пропустить письма через фильтр, даже если они довольно сильно напоминают спам.
Беспилотные автомобили и другие роботы — показательный пример работы вероятностного вывода. Машина ездит туда-сюда, создает карту территории и все увереннее определяет свое положение. Согласно недавнему исследованию, у лондонских таксистов увеличиваются размеры задней части гиппокампа — области мозга, участвующей в создании карт и запоминании, — когда они учатся ориентироваться в городе. Наверное, здесь действуют аналогичные алгоритмы вероятностного вывода с той лишь важной разницей, что людям алкоголь, по-видимому, не помогает.
Учимся по-байесовски
Теперь, когда мы знаем, как (более-менее) решать проблему логического
