Верховный алгоритм

Во всем этом есть, к сожалению, большая загвоздка. Само то, что байесовская сеть позволяет компактно представлять вероятностное распределение, еще не означает, что с ее помощью можно эффективно рассуждать. Представьте, что вы хотите вычислить 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, мегапеременная получит 2⁵⁰ значений. Поэтому такой метод на большее не способен, а ничего лучше не придумали.