Думай «почему?». Причина и следствие как ключ к мышлению - Джудиа Перл Страница 36

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

Начнем с самого начала: когда вы говорите по телефону, он преобразует ваш прекрасный голос в последовательность нулей и единиц (которые называются биты) и трансформирует их, используя радиосигнал. К сожалению, ни один из них не принимается со 100 %-ной точностью. Пока он идет от башни сотовой связи и до телефона вашего друга, отдельные биты сменятся с нуля на единицу или наоборот.

Для исправления этих ошибок можно добавить избыточную информацию. Простейшая схема состоит в том, чтобы повторить каждый бит информации три раза: закодировать единицу как 111 и ноль как 000. Допустимые строки 111 и 000 называются кодовыми словами. Если приемник получит недопустимую строку, например 101, он будет искать наиболее вероятное допустимое кодовое слово, чтобы объяснить ее. Здесь, скорее всего, ошибка — ноль, а не две единицы, поэтому декодер интерпретирует это сообщение как 111 и, таким образом, заключит что бит был единицей.

К сожалению, это крайне неэффективное кодирование, потому что все наши сообщения становятся в три раза длиннее. Однако специалисты по телекоммуникациям 70 лет работают над кодами исправления ошибок, постоянно их улучшая.

Проблема декодирования аналогична другим проблемам с обратной вероятностью, которые мы обсудили, потому что мы снова хотим вывести вероятность гипотезы (послали сообщение Hello World!) из имеющихся данных (получили сообщение HXllo Wovld!). Кажется, пришло время применить распространение убеждений.

В 1993 году инженер «Франс телеком» по имени Клод Берру поразил мир программирования кодом для исправления ошибок, который позволял добиться почти идеальных результатов (другими словами, требуемый объем лишней информации был близок к теоретическому минимуму). Его идею под названием «турбокод» можно проиллюстрировать, представив ее с помощью байесовской сети.

На рис. 20a показано, как работает обычный код. Биты информации, которые поступают в телефон, когда вы говорите, показаны в первом ряду. Они кодируются любым способом — назовем его код A — в кодовые слова (второй ряд), которые потом принимаются с некоторыми ошибками. Это диаграмма — байесовская сеть, и мы можем использовать распространение убеждений, чтобы вывести из полученных битов, каковы были биты информации. Однако это никак не улучшит код А.

Рис. 20. Представление обычного процесса кодирования и турбокода в виде байесовской сети: а — информационные биты преобразуются в кодовые слова; они передаются и принимаются в пункте назначения с шумом (ошибками); б — информационные биты скремблируются и кодируются дважды. Декодирование происходит путем распространения убеждений в этой сети. Каждый процессор внизу использует информацию от другого процессора, чтобы улучшить предположение о скрытом кодовом слове в итеративном процессе

Блестящая идея Берру состояла в том, чтобы закодировать каждое сообщение дважды: один раз непосредственно и один раз уже после того, как сообщение скремблировано (преобразовано в случайную последовательность). Это приводит к созданию двух отдельных кодовых слов и получению двух шумных сообщений (рис. 20б). Нам неизвестна формула, которая позволяет напрямую декодировать такое двойное сообщение. Но Берру на опыте показал, что, если неоднократно примерить формулы распространения убеждений к байесовским сетям, происходят две потрясающие вещи. В большинстве случаев (и здесь я имею в виду около 99,999 % случаев) вы получаете верные информационные биты. Более того, можно использовать гораздо более короткие кодовые слова. Проще говоря, две копии кода А гораздо лучше одной.

Эта небольшая история верна, за исключением одного: Берру не знал, что работает с байесовскими сетями! Он просто сам открыл алгоритм распространения убеждений. И только пять лет спустя Дэвид Маккей из Кембриджа понял, что это тот же алгоритм, с которым он развлекался в конце 1980-х, рассматривая байесовские сети. Это поместило алгоритм Берру в знакомый теоретический контекст и позволило информатикам-теоретикам лучше понять его работу.

Вообще-то, другой инженер, Роберт Галлагер из Массачусетского технологического института, открыл код, в котором использовалось распространение убеждений (хотя его тогда не называли этим термином), еще в 1960 году, так давно, что Маккей описывает его код как «почти ясновидение». В любом случае он слишком опережал свое время. Галлагеру требовались тысячи процессоров на чипе, которые передавали туда и обратно сообщения о степени уверенности в том, что конкретный информационный бит равен единице или нулю. В 1960 году это было невозможно, и его код был практически забыт, пока Маккей не открыл его заново в 1998 году. Сегодня он есть в каждом сотовом телефоне.

Как бы то ни было, турбокоды имели ошеломляющий успех. До турбореволюции сотовые сети 2G использовали «мягкое декодирование» (т. е. вероятности), а не распространение убеждений. В сетях 3G применили турбокоды Берроу, а в 4G — турбокоды Галлагера. С точки зрения потребителя это означает, что ваш телефон потребляет меньше энергии, а аккумулятор работает дольше, потому что кодирование и декодирование — самые энергоемкие процессы. Кроме того, более совершенные коды означают, что не нужно находиться как можно ближе к вышке сотовой связи, чтобы получить высококачественную передачу. Другими словами, байесовские сети позволили производителям телефонов выполнить обещание: больше полосок в больше мест.

От байесовских сетей к диаграммам причинности

Возможно, после главы, посвященной байесовским сетям, у вас возник вопрос: как они относятся к остальному в этой книге, в частности к диаграммам причинности вроде тех, что приведены в главе 1? Конечно, я обсудил их так подробно отчасти потому, что они привели к причинности лично меня. Но, что еще важнее как с теоретической, так и с практической точки зрения, байесовские сети — ключ, который позволяет диаграммам причинности взаимодействовать с данными. Все вероятностные свойства байесовских сетей (включая связки, которые мы обсуждали выше в этой главе) и разработанные для них алгоритмы распространения убеждений подходят и для диаграмм причинности. Более того, они необходимы для понимания причинного вывода.

Основные различия между байесовскими сетями и диаграммами причинности заключаются в том, как они построены и в каких целях используются. Байесовская сеть — это всего лишь компактное представление огромной таблицы вероятностей. Стрелки означают, что вероятности дочерних узлов связаны со значениями родительских узлов определенной формулой (таблицы условных вероятностей) и что этого отношения достаточно, т. е. знание дополнительных родителей не изменит формулу. Точно так же отсутствие стрелки между любыми двумя узлами означает,