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

Подсчитайте семь переходов и постройте прогноз для A

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

Во всей главе используем один и тот же порядок токенов:

Токен C входит в словарь, но в этих двух документах обучающей выборки не встречается. Документы обрабатываем по отдельности:

d1: BOS(0) → A(2) → A(2) → B(3) → EOS(1)
d2: BOS(0) → A(2) → B(3) → EOS(1)

Прежде чем продолжить, ответьте на четыре вопроса:

1. Сколько соседних переходов содержат оба документа вместе?
2. Какие токены встречаются сразу после A и сколько раз?
3. Какой токен должен оказаться самым вероятным продолжением A?
4. Чем случай «после A ни разу не встретился C» отличается от случая «после C не встретилось ничего»?

В первом документе четыре перехода, во втором — три:

d1: BOS→A, A→A, A→B, B→EOS
d2: BOS→A, A→B, B→EOS

После объединения результатов ненулевы только четыре счётчика: $\operatorname{BOS}\to A=2$, $A\to A=1$, $A\to B=2$ и $B\to\operatorname{EOS}=2$. Для текущего токена A расположим возможные продолжения в порядке [BOS, EOS, A, B, C]:

счётчики для A = [0, 0, 1, 2, 0]
сумма строки    = 3

Так устроена биграммная модель: текущий токен выбирает строку таблицы, а каждому возможному следующему токену соответствует столбец. Всё, что было до текущего токена, модель отбрасывает. Разделив каждый счётчик в строке A на её сумму, получаем оценку максимального правдоподобия (MLE):

Наибольшая вероятность только у B. Оценка MLE для перехода A→C определена, но равна нулю: из A наблюдалось три перехода, поэтому строку можно нормировать.

Для контекста C ситуация иная. Его строка равна [0,0,0,0,0], а сумма строки — нулю. Деление каждого счётчика на эту сумму привело бы к делению на ноль, поэтому распределение MLE для C не определено. Нулевая ячейка в существующем распределении и отсутствие всего распределения — разные случаи.

Теперь применим аддитивное сглаживание с $\alpha=1$. При вычислении вероятностей прибавим единицу к каждому счётчику. Эта единица — не новое наблюдение, а псевдочастота, которую вводит правило сглаживания. Исходная таблица счётчиков при этом не меняется. Для A получаем:

После C наблюдений нет. Пять одинаковых псевдочастот дают знаменатель $0+1\times5=5$ и равномерное распределение $[1/5,1/5,1/5,1/5,1/5]$. Это распределение задано правилом сглаживания, а не выведено из данных о C. Поэтому нельзя заключать, что в реальном языке все продолжения после C одинаково правдоподобны.

Остаётся проверить границу документов. Если склеить их в последовательность [0,2,2,3,1,0,2,3,1], получится восемь соседних пар вместо семи. Лишняя пара — EOS(1)→BOS(0): ни в одном исходном документе такого перехода нет.

Запишите подсчёт внутри документов и нормировку строк

Весь расчёт можно записать одной формулой:

Начнём с двух сумм в левой части. Внешняя сумма перебирает исходные документы обучающей выборки по одному. Во внутренней сумме позиции нумеруются с нуля, как индексы среза в Rust. Если $|d|\ge2$, индекс $t$ принимает значения от $0$ до $|d|-2$, а $t+1$ остаётся внутри того же документа. Для более короткого документа внутренняя сумма пуста. Верхний индекс $(d)$ подчёркивает, что оба токена пары принадлежат одному документу.

ID текущего токена $i$ задаёт строку, а ID возможного продолжения $j$ — столбец. Индикатор добавляет единицу, только когда соседние токены равны $i$ и $j$. Следовательно, $C_{ij}$ показывает, сколько раз встретился переход $i\to j$. Суммирование по всем столбцам $k$ даёт $N_i$ — общее число переходов, начинающихся с $i$.

Оценка MLE делит $C_{ij}$ на $N_i$, поэтому она определена только при $N_i>0$. При аддитивном сглаживании числитель каждой ячейки становится $C_{ij}+\alpha$. Поскольку в строке $|V|$ ячеек, знаменатель увеличивается на $\alpha|V|$, а не только на $\alpha$. В каждой строке сумма новых числителей совпадает со знаменателем, поэтому сумма вероятностей остаётся равной единице. При $\alpha>0$ знаменатель положителен даже у строки, в которой нет ни одного наблюдения.

Реализация на Rust хранит таблицу в одном построчном массиве: ячейка $(i,j)$ находится по смещению $i|V|+j$. Это лишь способ размещения данных в памяти; вероятностный смысл ячейки остаётся прежним: «следующим будет токен $j$, если текущий токен — $i$».

Разберите каждое обозначение

Важно понимать, к какой части таблицы относится утверждение. Фраза «C не встретился после A» описывает одну ячейку в строке A. Фраза «после C не встретился ни один токен» описывает всю строку C. Если перепутать строку и столбец, можно ошибочно решить, что распределение MLE существует или, наоборот, не существует.

Оцените возможности и ограничения классического подхода

До появления нейросетевых языковых моделей для прогноза следующего слова часто использовали n-граммные модели. Они учитывают только контекст фиксированной длины; у биграммной модели контекст состоит из одного текущего токена. Такую таблицу легко проверить, а прогноз по ней быстро вычисляется. Однако для любых двух последовательностей, которые оканчиваются одним и тем же токеном, модель выдаёт одинаковое распределение.

Чен и Гудман (1996) определяют биграммную оценку максимального правдоподобия как отношение числа наблюдений пары к числу наблюдений её контекста и объясняют, почему нулевая вероятность n-граммы, отсутствовавшей в обучающих данных, создаёт серьёзную проблему для языковой модели. В работе сравниваются несколько семейств методов сглаживания. Аддитивное сглаживание устроено просто, но далеко не является лучшим методом для практического применения: одинаковая псевдочастота не позволяет отличить друг от друга более и менее правдоподобные продолжения, которые не встречались в обучающей выборке.

Бенжио, Дюшарм и Венсан (2000) описывают традиционную n-граммную модель как таблицу условных вероятностей для коротких контекстов. В предложенной ими нейросетевой модели распределённые представления слов позволяют обобщать наблюдения на похожие последовательности. У независимых ячеек нашей таблицы такой возможности нет.

В этой главе используется сглаживание с $\alpha=1$, потому что все числители и знаменатели легко проверить вручную. Ограничение метода видно в том же примере: после сглаживания вероятность $1/8$ получает не только переход A→C, но и переход A→BOS, хотя BOS допустим только в начале документа. Одинаковая псевдочастота в каждой ячейке ничего не знает ни о роли токенов, ни о синтаксисе.

В статьях не задаются принятые в этой главе ID токенов, границы документов, значение $\alpha$, выбор только обучающей части корпуса и порядок вывода кандидатов с одинаковой вероятностью. Это учебные и инженерные решения курса. Программа на Rust вычисляет MLE и сглаженные оценки по одной и той же таблице, поэтому разницу между ними можно проверить непосредственно.

Сверьте ручной расчёт с реализацией на Rust

Демонстрационная программа использует те же два документа, что и ручной расчёт. Они передаются отдельными срезами, поэтому переход между документами не возникает. Универсальная функция, однако, принимает обычные срезы и полагается на вызывающий код: каждый срез должен содержать один документ с BOS в начале и EOS в конце, но без PAD.

pub const DOCUMENT_1: &[u32] = &[BOS, A, A, B, EOS];
pub const DOCUMENT_2: &[u32] = &[BOS, A, B, EOS];
pub const TRAINING_DOCUMENTS: [&[u32]; 2] = [DOCUMENT_1, DOCUMENT_2];

pub fn fitted_model() -> Result<BigramModel, BigramError> {
    BigramModel::fit_training_documents(VOCABULARY_SIZE, ALPHA, TRAINING_DOCUMENTS)
}

fit_training_documents проверяет размер словаря, параметр сглаживания, возможность выделить память под таблицу и каждый переданный ID. Внешний цикл перебирает документы, а windows(2) создаёт соседние пары только внутри текущего документа. Пустой срез и срез из одного токена не добавляют переходов; при этом все имеющиеся в них ID всё равно проверяются. Метод fit_encoded_training_partition явно запрашивает Partition::Train, поэтому валидационные и тестовые документы не попадают в подсчёт.

    /// Fits one count per adjacent pair in each caller-supplied training document.
    ///
    /// Documents remain separate: the final token of one document is never paired
    /// with the first token of the next document.
    pub fn fit_training_documents<'a, I>(
        vocabulary_size: usize,
        alpha: f64,
        training_documents: I,
    ) -> Result<Self, BigramError>
    where
        I: IntoIterator<Item = &'a [u32]>,
    {
        if vocabulary_size == 0 {
            return Err(BigramError::EmptyVocabulary);
        }
        let smoothing_mass = alpha * vocabulary_size as f64;
        if !alpha.is_finite() || alpha <= 0.0 || !smoothing_mass.is_finite() {
            return Err(BigramError::InvalidAlpha);
        }

        let cell_count = vocabulary_size
            .checked_mul(vocabulary_size)
            .ok_or(BigramError::TableTooLarge)?;
        let mut counts = Vec::new();
        counts
            .try_reserve_exact(cell_count)
            .map_err(|_| BigramError::TableTooLarge)?;
        counts.resize(cell_count, 0_u64);

        let mut model = Self {
            vocabulary_size,
            alpha,
            counts,
            fitted_documents: 0,
            fitted_transitions: 0,
        };

        for document in training_documents {
            model.fitted_documents = model
                .fitted_documents
                .checked_add(1)
                .ok_or(BigramError::TooManyDocuments)?;
            for token in document {
                model.token_index(*token)?;
            }
            for pair in document.windows(2) {
                let from = model.token_index(pair[0])?;
                let to = model.token_index(pair[1])?;
                let cell = from * vocabulary_size + to;
                model.counts[cell] = model.counts[cell]
                    .checked_add(1)
                    .ok_or(BigramError::TooManyTransitions)?;
                model.fitted_transitions = model
                    .fitted_transitions
                    .checked_add(1)
                    .ok_or(BigramError::TooManyTransitions)?;
            }
        }

        Ok(model)
    }

    /// Selects the original encoded training documents and never requests held-out data.
    pub fn fit_encoded_training_partition(
        vocabulary_size: usize,
        alpha: f64,
        partitions: &EncodedCorpusPartitions,
    ) -> Result<Self, BigramError> {
        Self::fit_training_documents(
            vocabulary_size,
            alpha,
            partitions
                .documents(Partition::Train)
                .iter()
                .map(|document| document.token_ids()),
        )
    }

Тип возвращаемого значения сохраняет важное различие. Some(0.0) означает, что строка MLE существует, но выбранный переход имеет нулевую вероятность. None означает, что сумма строки равна нулю и нормировать её нельзя. После сглаживания распределение существует для любого корректного контекста. Если максимальное значение счётчика достигается для нескольких токенов, most_likely_tokens возвращает все их ID по возрастанию. Этот порядок нужен только для воспроизводимого вывода: первый ID не становится более вероятным. Аддитивное сглаживание не меняет ранжирование токенов и сохраняет все равенства, потому что к каждой ячейке прибавляется одна и та же $\alpha$, а затем все числители делятся на общий знаменатель.

    /// Returns `None` when no outgoing transition was observed for `from`.
    pub fn maximum_likelihood_distribution(
        &self,
        from: u32,
    ) -> Result<Option<Vec<f64>>, BigramError> {
        let total = self.row_total(from)?;
        if total == 0 {
            return Ok(None);
        }
        Ok(Some(
            self.counts_row(from)?
                .iter()
                .map(|count| *count as f64 / total as f64)
                .collect(),
        ))
    }

    pub fn maximum_likelihood_probability(
        &self,
        from: u32,
        to: u32,
    ) -> Result<Option<f64>, BigramError> {
        self.token_index(to)?;
        let total = self.row_total(from)?;
        if total == 0 {
            return Ok(None);
        }
        Ok(Some(self.count(from, to)? as f64 / total as f64))
    }

    pub fn smoothing_denominator(&self, from: u32) -> Result<f64, BigramError> {
        Ok(self.row_total(from)? as f64 + self.alpha * self.vocabulary_size as f64)
    }

    pub fn smoothed_probability(&self, from: u32, to: u32) -> Result<f64, BigramError> {
        let numerator = self.count(from, to)? as f64 + self.alpha;
        Ok(numerator / self.smoothing_denominator(from)?)
    }

    pub fn smoothed_distribution(&self, from: u32) -> Result<Vec<f64>, BigramError> {
        self.token_index(from)?;
        (0..self.vocabulary_size)
            .map(|to| {
                let to = u32::try_from(to).map_err(|_| BigramError::TokenOutOfRange)?;
                self.smoothed_probability(from, to)
            })
            .collect()
    }

    /// Returns every count-maximizing successor in ascending token-ID order.
    pub fn most_likely_tokens(&self, from: u32) -> Result<Vec<u32>, BigramError> {
        let row = self.counts_row(from)?;
        let maximum = row
            .iter()
            .copied()
            .max()
            .expect("a vocabulary is non-empty");
        row.iter()
            .enumerate()
            .filter(|(_, count)| **count == maximum)
            .map(|(token, _)| u32::try_from(token).map_err(|_| BigramError::TokenOutOfRange))
            .collect()
    }

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

    println!("tokens: BOS=0 EOS=1 A=2 B=3 C=4");
    println!("alpha: {ALPHA:.1}");
    println!("training document d1: {DOCUMENT_1:?}");
    println!("training document d2: {DOCUMENT_2:?}");
    println!("counted transitions: {}", model.fitted_transitions());
    println!(
        "A counts: {} total={}",
        format_counts(model.counts_row(A).expect("A is in the vocabulary")),
        model.row_total(A).expect("A is in the vocabulary")
    );
    println!("A MLE: {}", format_probabilities(&a_mle));
    println!(
        "A add-alpha: {} denominator={:.0}",
        format_probabilities(&a_smoothed),
        model
            .smoothing_denominator(A)
            .expect("A is in the vocabulary")
    );
    println!(
        "unseen successor A->C: MLE={:.3} add-alpha={:.3}",
        model
            .maximum_likelihood_probability(A, C)
            .expect("A and C are in the vocabulary")
            .expect("A has outgoing transitions"),
        model
            .smoothed_probability(A, C)
            .expect("A and C are in the vocabulary")
    );
    println!(
        "C counts: {} total={}",
        format_counts(model.counts_row(C).expect("C is in the vocabulary")),
        model.row_total(C).expect("C is in the vocabulary")
    );
    println!("C MLE: {c_mle}");
    println!(
        "C add-alpha: {} denominator={:.0}",
        format_probabilities(&c_smoothed),
        model
            .smoothing_denominator(C)
            .expect("C is in the vocabulary")
    );
    println!("flattening would invent: EOS({EOS})->BOS(0)");

Запустите пример:

./course run cargo run --quiet --locked -p ch06-bigram-baseline

В реализации можно проверить все пять строк таблицы, общее число семи переходов, отсутствие EOS→BOS, нормировку обоих распределений, устойчивый порядок равновероятных кандидатов и явную обработку ошибок. Построение по закодированной обучающей выборке даёт ту же таблицу, что и прямая передача тех же документов с маркерами границ.

Сопоставьте исходные документы с двумя строками таблицы

Перед просмотром таблиц попробуйте предсказать ответы:

1. К каким ячейкам будет добавлена псевдочастота $\alpha$?
2. Изменится ли самое вероятное продолжение A после сглаживания?
3. Появится ли единственный максимум в сглаженном распределении после C?
4. Какой маркер, допустимый только в начале документа, всё же получит ненулевую вероятность после A?

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

Теперь проверьте ответы по полным таблицам. Псевдочастота $\alpha$ добавляется к каждой ячейке. После A единственным максимумом остаётся B. После C все токены имеют одинаковую сглаженную вероятность. Даже структурно недопустимый здесь переход A→BOS получает ненулевую вероятность.

Сначала решите задачи, затем проверьте расчёты

Во всех заданиях документы остаются раздельными, а столбцы идут в порядке [BOS, EOS, A, B, C]. Сначала запишите ответы и только потом запускайте пример.

1. Перечислите семь переходов и укажите исходный документ для каждого из них.
2. Для контекста A вычислите строку счётчиков, строку MLE и сглаженную строку при $\alpha=1$.
3. Объясните, почему $\operatorname{MLE}(A\to C)=0$, а распределение MLE для контекста C не определено.
4. Мысленно склейте документы. Какой искусственный переход появится и сколько соседних пар окажется в общей последовательности?
5. Почему подсчёт по перекрывающимся окнам главы 5 с $T=3$ и $S=1$ привёл бы к повторному учёту некоторых переходов в документе d1?
6. Пересчитайте сглаженную строку A для $\alpha=1/2$.
7. Проверьте, что обе сглаженные строки из примера дают сумму вероятностей, равную единице.
8. Назовите все токены с максимальной вероятностью в сглаженном распределении после A и после C.
9. Допустим, в валидационной выборке часто встречается A→C. Нужно ли менять таблицу перед оцениванием в главе 7?

Проверка понимания: фраза «C не встретился после A, поэтому строка C не определена» смешивает столбец и строку. Отсутствие перехода A→C относится к одной ячейке существующей строки A. Распределения MLE для C нет по другой причине: в обучающих данных ни один переход не начинается с C.

Зафиксируйте первую модель, которая возвращает полное распределение вероятностей

Теперь в курсе есть модель, которая принимает ID текущего токена $i$ и возвращает вероятность для каждого возможного следующего токена $j$. Она учитывает только один токен контекста и не умеет переносить наблюдения из одного контекста на похожие контексты. Тем не менее результат уже имеет ту же форму, что и выход декодера: распределение вероятностей по всему словарю.

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