Верховный алгоритм. Как машинное обучение изменит наш мир - Педро Домингос

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

Во всем этом есть, к сожалению, большая загвоздка. Само то, что байесовская сеть позволяет компактно представлять вероятностное распределение, еще не означает, что с ее помощью можно эффективно рассуждать. Представьте, что вы хотите вычислить P(взлом | звонок Боба, нет звонка Клэр). Из теоремы Байеса вы знаете, что это просто P(взлом) P(звонок Боба, нет звонка Клэр | взлом) / P(звонок Боба, нет звонка Клэр), или, эквивалентно, P(взлом, звонок Боба, нет звонка Клэр) / P(звонок Боба, нет звонка Клэр). Если бы в нашем распоряжении была полная таблица вероятностей всех состояний, можно было бы вычислить обе эти вероятности, сложив соответствующие строки в таблице. Например, P(звонок Боба, нет звонка Клэр) — это сумма вероятностей во всех линейках, где Боб звонит, а Клэр не звонит. Но байесовская сеть не дает полной таблицы. Ее всегда можно построить на основе отдельных таблиц, но необходимое для этого время и пространство растет экспоненциально. На самом деле мы хотим вычислить P(взлом | звонок Боба, нет звонка Клэр) без построения полной таблицы. К этому, в сущности, сводится проблема логического вывода в байесовских сетях.

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

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

Та же идея работает и в случае, если граф[91] представляет собой не цепь, а дерево. Если вместо взвода вы командуете целой армией, то можете спросить каждого ротного, сколько солдат за ним идет, а потом сложить их ответы. Каждый командир роты, в свою очередь, спросит своих взводных и так далее. Но если граф образует петлю, у вас появятся проблемы. Допустим, какой-то офицер-связной входит сразу в два взвода. Тогда два раза посчитают не только его самого, но и всех идущих за ним солдат. Именно это произойдет в примере с высадкой инопланетян, если вы захотите вычислить, скажем, вероятность паники:

Одно из решений — соединить «Сообщение в New York Times» и «Сообщение в Wall Street Journal» в одну мегапеременную с четырьмя значениями: «ДаДа», если сообщают оба источника, «ДаНет», если о приземлении сообщает New York Times, но не Wall Street Journal, и так далее. Это превратит граф в цепочку из трех переменных, и все хорошо. Однако с добавлением каждого нового источника новости число значений в мегапеременной будет удваиваться. Если вместо двух источников у вас целых 50, мегапеременная получит 250 значений. Поэтому такой метод на большее не способен, а ничего лучше не придумали.

Проблема сложнее, чем может показаться на первый взгляд, потому что у байесовских сетей появляются «невидимые» стрелки, идущие вместе с видимыми. «Взлом» и «землетрясение» априорно независимы, но сработавшая сигнализация их связывает: она заставляет подозревать ограбление. Но если вы услышите по радио, что было землетрясение, то начнете предполагать, что оно и виновато. Землетрясение оправдывает срабатывание сигнализации и делает ограбление менее вероятным, а следовательно, между ними появляется зависимость. В байесовской сети все родители той же переменной таким образом оказываются взаимозависимы, что, в свою очередь, порождает еще больше зависимостей, и результирующий граф часто получается намного плотнее, чем исходный.

Критически важный вопрос для логического вывода: можно ли сделать заполненный график «похожим на дерево», чтобы ствол при этом был не слишком толстый. Если у мегапеременной в стволе слишком много возможных значений, дерево будет расти бесконтрольно, пока не заполонит всю планету, как баобабы в «Маленьком принце». В древе жизни каждый вид — это ветвь, но внутри каждой ветви есть граф, где у каждого создания имеются двое родителей, четыре внука, какое-то количество потомков и так далее. «Толщина» ветви — это размер популяции данного вида. Если ветви слишком толстые, единственный выбор — прибегнуть к приближенному выводу.

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