Урок 68. Практикум MCMC: шифр Диакониса

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

Ключ как перестановка

Пусть алфавит содержит $m$ символов. Ключ $k$ — перестановка: каждую букву открытого текста он заменяет ровно одной буквой шифротекста. Число возможных ключей равно $m!$ . Для 33 русских букв

33!\approx8{,}68\cdot10^{36}.

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

Для учебного опыта удобно привести текст к фиксированному алфавиту: строчные русские буквы плюс пробел, удалить редкие знаки, а ё либо сохранить отдельно, либо заранее заменить на е. Правило должно быть одинаковым для обучающего корпуса и шифротекста. Это не мелкая чистка: она определяет модель языка.

Открытая фраза, таблица ключа и шифротекст с соединёнными повторяющимися буквами — Рис. 68.1. Подстановка сохраняет рисунок повторов
Верхняя строка — фрагмент открытого текста, средняя — таблица замен букв, нижняя — шифротекст. Дуги соединяют одинаковые позиции до и после шифрования. Цветом отмечены биграммы: сами символы меняются, но число и взаимное расположение повторов остаются.

Язык как вероятностная цепь

Возьмём большой корпус русского текста и посчитаем частоты биграмм или триграмм. Сглаженная вероятность символа $c_t$ после контекста:

p(c_t\mid c_{t-2},c_{t-1}) =\frac{N(c_{t-2},c_{t-1},c_t)+\lambda} {N(c_{t-2},c_{t-1})+\lambda|\mathcal A|}.

Логарифмический балл расшифровки $x_1\ldots x_n$ :

L(x)=\sum_{t=3}^{n}\log p(x_t\mid x_{t-2},x_{t-1}).

Логарифм превращает произведение малых вероятностей в сумму и защищает от численного обнуления. Сглаживание $\lambda>0$ не даёт одной невиданной триграмме уничтожить весь балл.

Это маленькая языковая модель: она знает только короткий контекст, зато её балл прозрачен. Высокий $L$ не доказывает осмысленность текста, но обычно предпочитает русские сочетания случайным.

Локальные ходы в огромном пространстве

Соседний ключ получают обменом образов двух букв. Такой ход меняет лишь две строки таблицы, но может исправить много позиций текста. Предложение симметрично: вероятность поменять $а$ и $б$ такая же, как вернуть их обратно.

Целевая плотность на ключах:

\pi(k)\propto \exp\{\beta L(k^{-1}y)\}.

Коэффициент $\beta$ задаёт обратную температуру. Переход $k\to k'$ принимается с вероятностью

a(k,k')=\min\left(1, \exp\{\beta[L(k'^{-1}y)-L(k^{-1}y)]\}\right).

Нормировочная сумма по $m!$ ключам не нужна: она сокращается, как в общем алгоритме Метрополиса–Хастингса.

От жадного взбирания к выборке

Если всегда принимать только улучшения, получим hill climbing. Он быстро находит ближайший локальный максимум и застревает. MCMC иногда принимает ухудшение, пересекает «перевал» и исследует другую область ключей.

Но есть тонкость: для строгой выборки из $\pi$ температура фиксирована. Для расшифровки нас чаще интересует максимум, поэтому применяют simulated annealing: начинают с малой $\beta$ , позволяющей свободное движение, затем повышают её. Это уже оптимизационная эвристика, а не стационарная выборка.

Несколько независимых запусков обязательны. Если разные цепи приходят к почти одинаковым текстам и баллам, уверенность растёт. Если результаты расходятся, нельзя выбирать самый приятный глазами вариант и молчать об остальных.

Схема локальных максимумов балла ключей и две траектории жадного поиска и MCMC — Рис. 68.2. Энергетический рельеф перестановок
Узлы изображают ключи, рёбра — обмен двух букв, высота — языковой балл $L$ . Красная жадная траектория останавливается на локальном пике; синяя цепь принимает один шаг вниз и достигает более высокого пика. Под узлами приведены короткие фрагменты расшифровок.

Лаборатория Диакониса

Запустите цепь на коротком шифротексте и смотрите на лучший результат вместе с кривой $L_t$ . Сравните биграммную и триграммную модели. Триграммы точнее замечают локальную грамматику, однако требуют большего корпуса и сильнее страдают от нулевых частот.

Затем уменьшите текст до 80 символов. Пространство ключей прежнее, а статистических свидетельств меньше: множество расшифровок получает близкий балл. Это не поломка алгоритма, а недостаток информации в задаче.

Диагностика без известного ответа

В настоящем шифре эталонного открытого текста нет. Значит, качество приходится оценивать косвенно:

сравнивать лучшие баллы независимых запусков;
смотреть, совпадают ли наиболее частые пары ключа;
проверять правдоподобие на отложенной языковой модели;
измерять стабильность результата при изменении корпуса и сглаживания;
публиковать несколько конкурирующих расшифровок, если разрыв мал.

Можно зашифровать известные тексты и оценить долю правильно восстановленных букв. Это synthetic benchmark: он проверяет алгоритм, но может быть легче исторических шифров с опечатками, именами и необычной орфографией.

Корпус решает, какой язык «нормален»

Если обучить модель на газетах XXI века, она может плохо оценивать дореволюционное письмо, диалект или код. В открытом корпусе Taiga есть художественные тексты, новости, социальные сети и другие жанры. Их смесь задаёт prior на стиль.

Полезный эксперимент: построить две триграммные модели, например на новостях и прозе, затем расшифровать один текст. Сопоставьте число правильных букв и места расхождения ключей. Имена собственные и редкая лексика особенно чувствительны к домену.

Модель должна обучаться только на открытом корпусе, не содержащем самого исходного текста. Иначе длинные совпадения превращают расшифровку в поиск утечки.

Кривые точности восстановления букв для униграммной биграммной и триграммной моделей при разной длине текста — Рис. 68.3. Длина шифротекста и восстановимость ключа
По горизонтали длина шифротекста от 50 до 2 000 символов, по вертикали доля правильно восстановленных пар ключа среди встретившихся букв. Линии показывают медианы 30 синтетических опытов, полосы — межквартильный диапазон. Видно, когда более сложная модель начинает окупать разреженность.

От частотного анализа к современным моделям

Классический частотный анализ сопоставляет самые частые символы. MCMC обобщает его: оценивает весь ключ через совместную статистику контекста и умеет менять несколько гипотез последовательно. Пространство дискретно и комбинаторно, но локальное предложение делает его проходимым.

Современная нейросетевая модель могла бы оценивать длинный контекст лучше. Однако её score дороже вычислять, труднее калибровать и проще переоптимизировать: поиск найдёт странные строки, которым сеть случайно назначает высокий балл. Переход от триграмм к трансформеру не отменяет диагностику.

Мини-исследование: где заканчивается информация текста

Зашифруйте 30 независимых фрагментов одного корпуса при длинах 50, 100, 200, 500 и 1000 символов. Для каждого сохраните один и тот же истинный ключ, но запускайте цепь из разных случайных перестановок. Оценивайте две величины: долю верно восстановленных пар среди встретившихся букв и долю правильно расшифрованных позиций.

Эти метрики различаются. Редкая буква может иметь неверный образ, почти не влияя на текст; наоборот, обмен двух частых букв портит много позиций. Постройте uncertainty по каждой паре букв: как часто она совпала в двадцати лучших запусках. Получится не один ключ, а карта уверенности.

Теперь сравните три источника ошибки. Сначала дайте алгоритму истинную языковую модель, построенную на большом совместимом корпусе, и большой вычислительный бюджет. Затем уменьшите число итераций, не меняя текст. Наконец, смените корпус на другой жанр. Если при 50 символах даже огромный бюджет даёт разные ключи, ограничение информационное. Если при 1000 символах помогают дополнительные итерации, мешал поиск. Если меняет ответ жанр, виновата модель.

Такое разложение повторяет общую логику ошибки смещения и дисперсии: нельзя называть все неудачи «MCMC не сошёлся», когда данных недостаточно или score задаёт другой язык.

Информация, модель и поиск не взаимозаменяемы

Успех расшифровки определяется тремя отдельными вещами. Текст должен быть достаточно длинным и сохранять статистический след. Языковая модель должна быть согласована с языком и жанром. Цепь должна исследовать пространство ключей, а не застрять рядом со стартом. Нельзя лечить плохой корпус миллионом итераций или короткий шифротекст сложной диагностикой.

Следующий шаг курса переносит марковскую структуру из пассивного наблюдения в управление: у переходов появятся действия и награды.

Задачи

4баллов

Для алфавита (а,б) заданы начальные вероятности $p_0(а)=0{,}9$ , $p_0(б)=0{,}1$ и переходы $p(б\mid а)=0{,}7$ , $p(а\mid а)=0{,}3$ , $p(а\mid б)=0{,}8$ , $p(б\mid б)=0{,}2$ . По формуле $L(x_1\ldots x_n)=\log p_0(x_1)+\sum_{t=2}^n\log p(x_t\mid x_{t-1})$ вычислите натуральные логарифмические баллы строк абаба и бабаб. Покажите, что они не равны, и найдите вероятность принятия худшей строки $\min\{1,\exp(L_{\rm new}-L_{\rm old})\}$ при $\beta=1$ . Случайности нет; ответ нужен точно через логарифмы и численно до $10^{-4}$ .

5баллов

На алфавите из $m\ge2$ символов состояние есть перестановка ключа. Предложение выбирает одну из $\binom m2$ неупорядоченных пар равновероятно и меняет местами их образы. Докажите $q(\sigma'\mid\sigma)=q(\sigma\mid\sigma')$ для соседних состояний и объясните связность графа состояний, разложив произвольную перестановку в транспозиции. Случайности, seed и единицы измерения для доказательства не нужны; зачёт требует также оценку не более $m-1$ транспозиций на один цикл.

6баллов

Возьмите русский файл warandpeace.txt из gist romaklimenko/c95f3a864828f7f034b7a33d1676e420, revision 55f9027799b5b3c67e2f7cb3d6a7154f707ff08a, raw revision 0e1f6d59ba40b257bbdda4824a77911436833b4b, SHA-256 0e309adcd1abe20c93d89ea0599ce5607bfde10d2daaeb2ece2104095774ccc3. Приведите текст к NFC и нижнему регистру, сохраните ё, каждую максимальную последовательность вне [а-яё] замените одним пробелом и обрежьте края. Первые 200 000 символов служат train; для каждой длины $L\in\{100,300,1000\}$ возьмите 20 фрагментов со стартами $250000+5000j$ , $j=0,\ldots,19$ . Обучите символьные биграммы и триграммы с add- $0{,}1$ smoothing, включая два граничных символа; score равен сумме натуральных log probability. Шифр каждого фрагмента создайте равномерной перестановкой 33 букв, не меняя пробел, с PCG64 seed $680400+100L+j$ . На каждую модель и фрагмент дайте десять цепей по 20 000 предложений перестановки пары букв, seeds $681000+100L+10j+r$ , и сохраните лучший score. Зачёт требует медиану и IQR точности восстановленных букв для шести режимов и одинаковый бюджет 200 000 предложений на режим.

7баллов

Независимо загрузите открытый файл warandpeace.txt из gist romaklimenko/c95f3a864828f7f034b7a33d1676e420, revision 55f9027799b5b3c67e2f7cb3d6a7154f707ff08a, raw revision 0e1f6d59ba40b257bbdda4824a77911436833b4b; SHA-256 файла 0e309adcd1abe20c93d89ea0599ce5607bfde10d2daaeb2ece2104095774ccc3. Нормализуйте его: NFC, нижний регистр, ё сохраняется, всё вне [а-яё] сжимается в один пробел. На первых 200 000 символах постройте символьную триграммную модель с add- $0{,}1$ smoothing и score $L=\sum_t\log p(x_t\mid x_{t-2},x_{t-1})$ с двумя начальными маркерами. Десять тестовых фрагментов длины 500 начинаются в позициях $250000+20000j$ , $j=0,\ldots,9$ ; их подстановочные ключи задают PCG64 seeds $6850+j$ . Для каждого шифра сделайте 20 общих случайных стартов с seeds $686000+20j+r$ . Жадный поиск принимает только $\Delta L>0$ ; annealing принимает с вероятностью $\min(1,e^{\Delta L/T_m})$ , где $T_m=\max(0{,}05,5\cdot0{,}99995^m)$ ; оба режима получают ровно 100 000 предложений на старт. Сравните лучший score, точность 33-буквенного ключа, число различных лучших ключей и время; зачёт требует один найденный пример с более высоким score, но меньшей точностью, либо честный отчёт, что среди 200 пар такого примера нет.