Карта → событие
Тьюринг: вес свидетельства в Блетчли-парке
Задача
Немецкий военно-морской шифр «Энигма» имел настолько большое пространство ключей, что полный перебор был безнадёжен. Но криптоаналитик не обязан быть уверен — ему достаточно отранжировать гипотезы и проверять сначала правдоподобные.
Типичная задача: даны два перехваченных сообщения. Зашифрованы ли они при одинаковой начальной установке роторов («в глубине») или нет? Прямых доказательств нет; есть слабые улики — совпадения букв в одинаковых позициях чуть чаще случайного.
Каждая улика по отдельности почти ничего не значит. Их надо накапливать, и накапливать корректно.
Решение: логарифмическое отношение правдоподобия
Байесовская формула в форме отношения шансов:
$$\underbrace{\frac{P(H_{1}\mid E)}{P(H_{0}\mid E)}}_{\text{апостериорные шансы}} = \underbrace{\frac{P(H_{1})}{P(H_{0})}}_{\text{априорные шансы}}\times\underbrace{\frac{P(E\mid H_{1})}{P(E\mid H_{0})}}_{\text{отношение правдоподобия}}.$$
Красота этой записи в том, что знаменатель БайесаТомас БайесРешил обратную задачу вероятности — как от наблюдений перейти к вероятности причины. Работу нашли в бумагах покойного и напечатали через два года после смерти; при жизни он не опубликовал по математике ничего… (полная вероятность данных) сокращается — считать его не нужно. Остаётся умножение.
А умножать неудобно. Логарифмируем:
$$\log\frac{P(H_{1}\mid E)}{P(H_{0}\mid E)} = \log\frac{P(H_{1})}{P(H_{0})} + \log\frac{P(E\mid H_{1})}{P(E\mid H_{0})}.$$
Улики стали складываться. Тьюринг назвал слагаемое весом свидетельства (weight of evidence) — величиной, которую каждое наблюдение добавляет к нашей уверенности.
Бан и децибан
Единица: бан — вес свидетельства, изменяющий шансы в 10 раз, то есть десятичный логарифм отношения правдоподобия. Название — от города Банбери, где печатали перфорированные листы для соответствующей процедуры (метод получил имя «банбуризм»).
На практике использовался децибан ($\text{db} = 0{,}1$ бана) — примерно наименьшая различимая на глаз степень правдоподобия. Работа шифровальщиков сводилась к тому, чтобы накапливать децибаны, пока сумма не перевалит порог.
Численный пример. Пусть при верной гипотезе совпадение букв случается с вероятностью $1/17$, при неверной — $1/26$. Одно совпадение даёт
$$\log_{10}\frac{1/17}{1/26} = \log_{10}\frac{26}{17} = \log_{10}1{,}529 \approx 0{,}184\ \text{бана} \approx 1{,}8\ \text{децибана}.$$
Ничтожно мало. Но двадцать совпадений дают $\approx 3{,}7$ бана, то есть изменение шансов в пять тысяч раз. Так слабые улики складываются в уверенность.
Заметим сходство: та же величина под названием $\log_{2}$ отношения — это бит информации, и Тьюринг здесь буквально в шаге от того, что через семь лет опубликует ШеннонКлод ШеннонВ магистерской работе связал булеву алгебру с электрическими схемами, а через одиннадцать лет измерил информацию в битах — и создал предмет, которого до него не было. (следующая точка). Единица «бан» и единица «бит» отличаются лишь основанием логарифма ($1$ бан $= \log_2 10 \approx 3{,}32$ бита). Оба работали над военной криптографией и, вероятно, обсуждали смежные вопросы при встрече Тьюринга с Шенноном в Bell Labs в 1943 году, хотя содержательно о своих секретных проектах говорить не могли.
Последовательная процедура
Тьюринг накапливал децибаны и останавливался, как только сумма превышала порог принятия или опускалась ниже порога отбрасывания. Это в точности последовательный критерий отношения правдоподобия — тот самый SPRT, который Абрахам ВальдАбрахам ВальдПридумал последовательный анализ — проверку, которая сама решает, когда остановиться, — и объяснил военным, почему бронировать надо те места самолётов, где пробоин нет. создаст в Нью-Йорке в 1943 году (Вальд) и который тоже немедленно засекретят.
Два человека независимо, по разные стороны Атлантики, в один и тот же период, для двух разных военных задач изобретают одну и ту же процедуру — и оба результата закрыты. Хороший сюжет о том, как война одновременно ускоряет и прячет науку.
Оценка Гуда — Тьюринга
Ещё один результат той же работы, доведённый до печати помощником Тьюринга Ирвингом Джоном Гудом (1953).
Задача. Мы видели выборку слов (или ключевых установок). Какова вероятность, что следующее наблюдение окажется чего-то, чего мы ещё ни разу не видели?
Наивный ответ «ноль» очевидно неверен. Оценка Гуда — Тьюринга:
$$P(\text{новое}) \approx \frac{N_{1}}{N},$$
где $N_1$ — число объектов, встретившихся ровно один раз, а $N$ — размер выборки. Идея: «одиночки» — свидетельство того, что хвост распределения не исчерпан.
Пример: если из 1000 перехваченных сообщений 200 использовали установку, встретившуюся лишь однажды, то вероятность встретить совсем новую установку оценивается в 20%.
Это стало базовым методом сглаживания в компьютерной лингвистике: без него языковые модели присваивают нулевую вероятность любому невиданному сочетанию слов. Прямая линия от Блетчли-парка к обработке естественного языка.
Секретность
Работа Тьюринга «The Applications of Probability to Cryptography» (около 1941 года) оставалась засекреченной и была рассекречена и передана в Национальный архив Великобритании только в 2012 году. Сопутствующая записка Гуда — тогда же.
Последствие для истории науки: байесовский подход был заново развит в практических масштабах на десять лет раньше, чем принято считать, — и это не повлияло ни на что, потому что об этом нельзя было говорить. Гуд после войны стал одним из главных пропагандистов байесовских методов, но своих источников назвать не мог.
Историческая ирония: в 1950-е байесовский подход считался маргинальным (господствовали ФишерРональд ФишерПридумал почти всё, чем статистика пользуется сегодня, — дисперсионный анализ, рандомизацию, максимум правдоподобия, p-значение, — работая на сельскохозяйственной опытной станции. и Нейман — ПирсонКарл ПирсонПревратил догадки Гальтона в дисциплину с аппаратом: хи-квадрат, стандартное отклонение, гистограмма, коэффициент корреляции — всё это его слова и его формулы. И он же двадцать пять лет заведовал кафедрой…, биометрическая школа), а «байесовский ренессанс» датируют 1960–70-ми. На деле самое масштабное байесовское предприятие первой половины XX века уже состоялось — в бараках Блетчли-парка.
Место в линии
Точка о Байесе (1761) заканчивается словами о том, что XX век устроит байесовский ренессанс. Здесь — недостающее звено между Байесом и машинным обучением: первое промышленное применение байесовского вывода, с собственной единицей измерения, с процедурой остановки и с конкретным измеримым результатом.
О масштабе результата спорят, но нижняя оценка историков (Хинсли) — что работа Блетчли-парка сократила войну примерно на два года.