Цепи Маркова: предсказание без понимания

Фрагмент лекции: «Все что нужно знать про ИИ айтишнику», 05:00 — отсюда взято содержание этой главы.

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

От скороговорки к графу переходов

Возьмём короткий текст, который все знают наизусть:

Ехал Грека через реку, видит Грека — в реке рак. Сунул Грека руку в реку, рак за руку Греку цап.

Приведём к нижнему регистру, выбросим знаки препинания и порежем по пробелам. Получается 19 токенов и 13 различных слов:

ехал грека через реку видит грека в реке рак сунул грека руку в реку рак за руку греку цап

Теперь выпишем все пары «слово → следующее слово». Каждая пара — ребро графа. У большинства слов продолжение единственное, но у четырёх — несколько, и именно они делают текст интересным:

Все числа в этой таблице посчитаны по конкретному корпусу из 19 токенов выше — это учебный пример, а не статистика русского языка. Это важная оговорка: любая цепь Маркова знает ровно то, что было в её корпусе, и ни слова больше.

Обратите внимание на цикл грека → через → реку → видит → грека. В исходной скороговорке его нет — там текст идёт слева направо и заканчивается. Цикл возник потому, что модель склеила разные позиции одного и того же слова в одно состояние. Это не побочный эффект, а суть конструкции: цепь Маркова забывает, где именно в тексте она находится, и помнит только, какое слово произнесла последним. Заодно видна честная проблема разметки: переход реку → видит перепрыгивает через запятую, а рак → сунул — через точку, то есть мы склеили конец одного предложения с началом другого. В настоящих n-граммных моделях границы размечают служебными токенами, иначе модель уверенно порождает фразы из чужих кусков.

Конечный автомат и цепь Маркова: где проходит граница

Пока мы рисовали стрелки без чисел, у нас был конечный автомат. Как только на рёбрах появились вероятности, получилась цепь Маркова. Разница не косметическая.

Из этого следует практическое замечание, которое стоит проговорить, потому что путаница здесь встречается часто. Детерминированный поиск по индексу — не цепь Маркова. Лончер, который по горячей клавише ищет статью в локальном индексе, не имеет ни состояний с распределениями, ни случайного выбора: одинаковый запрос даёт одинаковый список результатов. Это ранжирование по заранее посчитанной релевантности. Формальное родство с цепями Маркова появилось бы, только если бы следующий шаг выбирался случайно по вероятностям, зависящим от текущего состояния, — а ранжированный поиск устроен иначе.

Марковское свойство, сформулированное строго

Обозначим последовательность состояний как X_0, X_1, X_2, .... Процесс обладает марковским свойством, если для любого момента времени t и любого состояния s выполняется:

P(X_{t+1} = s | X_t, X_{t-1}, ..., X_0)  =  P(X_{t+1} = s | X_t)

Читается так: распределение следующего состояния полностью определяется текущим состоянием; вся предыдущая история не добавляет к прогнозу ничего. Не «история не важна вообще» — она уже учтена в том, что процесс пришёл именно сюда. А именно: зная текущее состояние, вы не выиграете от знания пути, которым в него попали.

Что теряется, видно на нашем же графе. Мы стоим в состоянии в. У него два продолжения — реке и реку, по 1/2. Но в исходном тексте выбор был жёстко предопределён предыдущим словом: после грека в шло реке, после руку в шло реку. Информация была в истории, а модель первого порядка её выбросила. Отсюда и рождаются фразы вроде «сунул грека руку в реке» — грамматически невозможные, но для модели совершенно законные, потому что каждый отдельный переход в корпусе действительно встречался.

Обобщая, марковское свойство первого порядка выбрасывает:

• согласование на расстоянии — род, число, падеж, вид глагола;
• парность — открытая скобка, кавычка или условие if не помнятся до момента закрытия;
• отрицание — частица «не» через три слова уже не влияет ни на что;
• тему текста — модель не знает, о чём абзац, она знает только последнее слово.

Именно эти четыре пункта и есть содержательное определение фразы «модель ничего не понимает».

Немного истории, потому что она проясняет суть

Цепи ввёл А. А. Марков-старший в 1906 году, и мотив был чисто математический: показать, что закон больших чисел работает не только для независимых испытаний, но и для зависимых, если зависимость устроена «по цепочке». Иллюстрацию он взял из литературы: в работе «Пример статистического исследования над текстом „Евгения Онегина“, иллюстрирующий связь испытаний в цепь» (1913) он вручную разметил двадцать тысяч букв пушкинского текста как гласные и согласные и посчитал частоты переходов между двумя этими состояниями.

То есть первая в истории цепь Маркова была моделью текста с двумя состояниями, построенной без единого вычислительного устройства. Через 35 лет Клод Шеннон в работе «A Mathematical Theory of Communication» (1948) сделал ровно то же самое с английским языком, но на нескольких уровнях сразу — от случайных букв до n-грамм по словам — и показал, что с ростом порядка приближения текст становится всё более похожим на настоящий, не становясь при этом осмысленным. Это ключевое наблюдение всей главы, и оно старше любого компьютера в вашем доме.

Матрица переходов и оценка по частотам

Формально цепь задаётся квадратной матрицей переходов размера |V| × |V|, где |V| — размер словаря. В ячейке (i, j) стоит вероятность перейти из состояния i в состояние j. Каждая строка суммируется в единицу — это стохастическая матрица.

Откуда берутся числа? Простейший способ — оценка максимального правдоподобия по частотам: посчитать, сколько раз в корпусе за словом i шло слово j, и поделить на общее число вхождений слова i:

P(j | i)  =  count(i, j) / count(i)

Ровно это мы и делали руками в таблице выше. Более общий взгляд на оценивание вероятностей по данным — в главе «Математический фундамент» трека по машинному обучению.

Важная деталь про хранение. Плотная матрица |V| × |V| для словаря в 50 000 слов — это 2,5 миллиарда ячеек, из которых заполнена ничтожная доля: подавляющее большинство пар слов в корпусе просто не встречается. Поэтому в реальности матрицу никто не материализует — хранят разреженную структуру «состояние → словарь продолжений с их счётчиками». Это первое место, где теоретическая формулировка и рабочая реализация расходятся, и не последнее.

Порядок цепи и n-граммы

Модель первого порядка склеивает «грека в» и «руку в» в одно состояние. Очевидное лекарство — расширить состояние: пусть состоянием будет не последнее слово, а последние n слов. Такая модель называется цепью порядка n, а сами последовательности из n + 1 слова — n-граммами.

На нашем корпусе из 19 токенов цепь второго порядка даёт 17 состояний — и все они различны, у каждого ровно одно продолжение. Это значит, что модель второго порядка на таком корпусе не порождает ничего нового: она дословно воспроизводит скороговорку. Мы получили идеальное качество и нулевую пользу — модель просто запомнила данные. Это переобучение в чистейшем виде, до всякого машинного обучения.

За расширение состояния платят экспоненциально. Число теоретически возможных состояний равно |V|^n:

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

Отсюда — целое семейство приёмов сглаживания:

• аддитивное сглаживание (Лапласа) — прибавить ко всем счётчикам небольшую константу, чтобы ни одна вероятность не была нулевой; грубо, но работает;
• откат (backoff) — не нашли 4-грамму, спросили у модели 3-го порядка, потом 2-го, потом просто частоту слова;
• интерполяция — не переключаться между порядками, а смешивать их оценки с весами;
• Kneser–Ney — практический стандарт n-граммных языковых моделей до эпохи нейросетей; учитывает не только частоту слова, но и разнообразие контекстов, в которых оно встречается.

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

Рабочая реализация

Двадцать строк, которые делают всё описанное выше.

import random
from bisect import bisect_right
from collections import Counter, defaultdict


def tokenize(text: str) -> list[str]:
    """Грубая токенизация: нижний регистр, знаки препинания — в пробелы.
    В настоящем корпусе границы предложений размечают служебными токенами,
    иначе модель склеит конец одной фразы с началом следующей.
    """
    cleaned = "".join(c.lower() if (c.isalpha() or c.isspace()) else " " for c in text)
    return cleaned.split()


def build_chain(tokens: list[str], order: int = 1) -> dict:
    """Таблица переходов: состояние (кортеж из `order` слов) -> счётчики продолжений.

    Время:  O(N * order). Один проход по корпусу; на каждом шаге собирается
            и хешируется кортеж-ключ длиной `order`.
    Память: O(T), где T — число различных наблюдённых пар
            (состояние, продолжение). Сверху T ограничено и N, и |V|^(order+1),
            но на практике всегда N: корпус не породит больше n-грамм,
            чем в нём токенов. Плотную матрицу |V| x |V| мы не строим никогда.
    """
    chain = defaultdict(Counter)
    for i in range(len(tokens) - order):
        state = tuple(tokens[i:i + order])
        chain[state][tokens[i + order]] += 1
    return dict(chain)


def compile_chain(chain: dict) -> dict:
    """Подготовка к быстрому сэмплированию: для каждого состояния — список
    продолжений и накопленные суммы частот (префиксные суммы).

    Время:  O(T) — один проход по таблице.
    Память: O(T).
    """
    compiled = {}
    for state, counter in chain.items():
        words, cumulative, total = [], [], 0
        for word, count in counter.items():
            total += count
            words.append(word)
            cumulative.append(total)
        compiled[state] = (words, cumulative, total)
    return compiled


def generate(compiled: dict, start, length: int = 20, rng=None) -> str:
    """Порождение текста сэмплированием по цепи.

    Время:  O(L * log k) — L шагов, на каждом двоичный поиск по k продолжениям
            текущего состояния. Наивный линейный перебор дал бы O(L * k),
            метод alias с предподсчётом — O(1) на шаг ценой ещё O(T) памяти.
    Память: O(L) на результат; сама таблица переходов не растёт.
    """
    rng = rng or random.Random()
    state = tuple(start)
    out = list(state)
    for _ in range(length):
        entry = compiled.get(state)
        if entry is None:          # тупик: такого состояния в корпусе не было
            break
        words, cumulative, total = entry
        # Тянем целое из [0, total) и ищем, в чей интервал частот оно попало.
        # Важно: это НЕ равновероятный выбор одного из вариантов.
        # Равномерный выбор среди продолжений стирает частоты и превращает
        # цепь Маркова обратно в недетерминированный автомат.
        r = rng.randrange(total)
        out.append(words[bisect_right(cumulative, r)])
        state = (*state[1:], out[-1])   # сдвигаем окно на один токен
    return " ".join(out)

Проверим на скороговорке:

TEXT = ("Ехал Грека через реку, видит Грека — в реке рак. "
        "Сунул Грека руку в реку, рак за руку Греку цап.")

tokens = tokenize(TEXT)                 # 19 токенов, 13 различных слов
chain = build_chain(tokens, order=1)    # 12 состояний (у 'цап' продолжений нет)
compiled = compile_chain(chain)

chain[("грека",)]   # Counter({'через': 1, 'в': 1, 'руку': 1})
chain[("реку",)]    # Counter({'видит': 1, 'рак': 1})
generate(compiled, ["ехал"], length=12, rng=random.Random(1))
  # -> 'ехал грека руку в реку видит грека в реку рак сунул грека в'

Результат стоит перечитать. Каждая пара слов в нём законна — все они есть в исходном тексте. Фраза целиком — бессмыслица. Это и есть предсказание без понимания в чистом виде: локальная правдоподобность без глобальной связности. Ровно тот же дефект в тысячу раз более мягкой форме вы видите, когда большая модель уверенно пишет абзац, который разваливается при внимательном чтении.

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

Где цепи Маркова живут сегодня

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

Генерация текста-заглушки. Марковский генератор по корпусу даёт текст с правильной статистикой языка и нулевым смыслом — идеальная рыба для вёрстки и нагрузочных тестов. Это единственная задача, где отсутствие смысла является требованием, а не дефектом.

MCMC — методы Монте-Карло по марковским цепям. Здесь цепь используется не для порождения текста, а как инструмент интегрирования: строится цепь, чьё стационарное распределение совпадает с нужным, и по ней долго блуждают, накапливая выборку. Так считают апостериорные распределения в байесовской статистике, когда взять интеграл аналитически невозможно.

PageRank. Самый известный прикладной пример, и связь здесь строгая, а не по аналогии. В работе Сергея Брина и Лоуренса Пейджа «The Anatomy of a Large-Scale Hypertextual Web Search Engine» (1998) веб описан как граф: страницы — вершины, ссылки — рёбра. По этому графу гуляет случайный сёрфер: с вероятностью, задаваемой коэффициентом затухания, он переходит по случайной ссылке с текущей страницы, иначе прыгает на случайную страницу целиком. Это в точности цепь Маркова на графе ссылок, а PageRank страницы — её стационарное распределение, то есть доля времени, которую сёрфер проводит на этой странице при бесконечном блуждании.

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

Что важно для остальной части трека: во всех четырёх случаях модель одинакова, а меняется только вопрос, который ей задают. Порождение текста читает траекторию цепи, PageRank и MCMC — её стационарное распределение. Одна конструкция, разные способы её эксплуатировать.

Чем цепь Маркова принципиально хуже языковой модели

Здесь важно быть точным, потому что расхожая формулировка «нейросеть — это те же цепи Маркова» и верна, и вводит в заблуждение одновременно.

Формально верно вот что: авторегрессионная языковая модель с контекстным окном длины K — это цепь Маркова порядка K над токенами. Никакой другой математики в определении не появляется. Различий, которые всё меняют, ровно два.

Первое — размер состояния. У марковской цепи n — это два-три слова, потому что таблица переходов растёт как |V|^n. У современной модели окно — десятки и сотни тысяч токенов, то есть весь диалог, вся статья, весь файл целиком. При такой длине разница между «помнит несколько слов» и «помнит всё» перестаёт быть количественной.

Второе — способ задать распределение. Цепь Маркова хранит распределения в таблице: не видел точную n-грамму — не знаешь ничего. Языковая модель вычисляет распределение функцией с обученными параметрами, и похожие контексты дают похожие ответы, даже если конкретное сочетание слов не встречалось никогда. Слова для неё не различные символы, а точки в пространстве, где «кот» и «кошка» рядом. Об этом — глава «Представления».

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

Три вехи, о которых говорит лекция

Лекция вводит рамку из трёх подходов к «умным» задачам. Это авторская классификация, а не общепринятая таксономия, но как карта местности она полезна.

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

Отдельно про SBSE: исправление

В лекции цепи Маркова связываются с аббревиатурой SBSE, а её расшифровка называется предположительно. И то, и другое неверно, поэтому зафиксируем корректно.

SBSE — Search-Based Software Engineering, поисковая инженерия программного обеспечения. Это применение метаэвристической поисковой оптимизации — генетических алгоритмов, локального поиска, роевых методов — к задачам разработки: генерации тестов, автоматическому исправлению программ, рефакторингу, планированию релизов. Термин ввели Марк Харман и Брайан Джонс в 2001 году.

К цепям Маркова SBSE отношения не имеет: там оптимизация по функции приспособленности в заданном пространстве решений, здесь вероятностная модель последовательности. Это первая из трёх вех, отдельная ветка со своим треком на портале — SBSE. Пересказывать её здесь смысла нет.

Мини-итог

• Цепь Маркова — это конечный автомат, у которого на рёбрах стоят вероятности; переход выбирается сэмплированием, поэтому два запуска на одном входе дают разные результаты.
• Марковское свойство означает, что распределение следующего состояния зависит только от текущего состояния; вместе с историей теряются согласование, парность, отрицание и тема текста — это и есть техническое содержание фразы «модель не понимает».
• Вероятности оцениваются частотами по корпусу; плотную матрицу переходов никто не строит — только разреженную таблицу, потому что заполнена в ней ничтожная доля ячеек.
• Порядок цепи — ручка с двумя плохими концами: низкий порядок даёт бессвязный текст, высокий — дословное цитирование корпуса и провал на любой невиданной n-грамме; отсюда всё семейство методов сглаживания.
• Построение таблицы — O(N · n) по времени и O(T) по памяти, генерация — O(L · log k) при префиксных суммах; типичная ошибка реализации — равновероятный выбор среди продолжений вместо выбора по частотам.
• PageRank — честная цепь Маркова: случайное блуждание по графу ссылок, а ранг страницы есть стационарное распределение этой цепи (Brin & Page, 1998).
• Языковая модель формально остаётся марковской, но её состояние — весь контекст, а распределения не хранятся в таблице, а вычисляются обученной функцией; это и снимает оба ограничения сразу.

Что дальше

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

Машинное обучение: картинки, звук, текст