Как работает Byte-Pair Encoding (BPE) в токенизаторах GPT? Решите пример на псевдокоде.

Краткий тезис

BPE — это итеративный алгоритм субсловной токенизации, который начинает с базового набора символов (байтов) и постепенно объединяет наиболее часто встречающиеся пары соседних токенов в новые составные токены. BPE лежит в основе токенизаторов моделей GPT (и их предшественников, включая GPT-2 и GPT-3) — он позволяет эффективно обрабатывать редкие и незнакомые слова, не расширяя словарь до гигантских размеров, и сохраняет возможность кодировать любую последовательность байтов.

2. Пример: «low», «lower» → слияния

Рассмотрим миниатюрный корпус, состоящий из двух слов: low и lower. Для простоты разделим на символы:

Объединим корпус в последовательность токенов: [l, o, w, l, o, w, e, r].

Итерация 1: Подсчитываем все пары соседних токенов и их частоту:

Самые частые пары — l,o и o,w (по 2). Выбираем любую, например l,o. Сливаем их в новый токен <lo>. После слияния корпус выглядит так: [<lo>, w, <lo>, w, e, r].

Итерация 2: Пары теперь:

Самая частая — <lo>,w. Сливаем её в <low>. Корпус: [<low>, <low>, e, r].

Итерация 3: Пары:

В этой точке можно остановиться, если заданный размер словаря достигнут (например, словарь = исходные 6 символов + 2 новых токена = 8 токенов). Если продолжать, на следующем шаге сольётся e,r → <er>, и т.д.

Итоговый словарь включает:

• исходные символы: l, o, w, e, r (и, возможно, <w> не появился, но все базовые)
• добавленные токены: <lo>, <low>, (и <er> если продолжать)

Обратите внимание, что слово lower после обучения будет токенизировано как <low> + e + r (или <low> + <er>), а low как <low>.

3. Псевдокод или алгоритм

Приведём псевдокод, реализующий BPE на корпусе, представленном списком строк.

# Псевдокод обучения BPE

def train_bpe(corpus: List[str], num_merges: int) -> Dict[str, int]:
    # 1. Инициализация: разбиваем каждое слово на символы
    #    Каждое слово представляем как список токенов, а также храним частоту слова
    word_freqs = counter_of_words(corpus)
    token_lists = {word: list(word) for word in word_freqs}
    
    # 2. Итеративные слияния
    vocab = set()  # множество всех токенов (базовые + новые)
    for word in token_lists:
        vocab.update(token_lists[word])
    
    merges = []
    for i in range(num_merges):
        # Подсчёт пар во всех словах с учётом частоты слов
        pair_counts = Counter()
        for word, freq in word_freqs.items():
            tokens = token_lists[word]
            for j in range(len(tokens)-1):
                pair = (tokens[j], tokens[j+1])
                pair_counts[pair] += freq
        
        if not pair_counts:
            break
        
        # Выбираем самую частую пару
        best_pair = max(pair_counts, key=pair_counts.get)
        new_token = best_pair[0] + best_pair[1]  # конкатенация
        vocab.add(new_token)
        merges.append(best_pair)
        
        # Заменяем все вхождения пары в корпусе
        # (используем специальный разделитель или сохраняем как один токен)
        for word, tokens in token_lists.items():
            i = 0
            new_tokens = []
            while i < len(tokens):
                if i < len(tokens)-1 and (tokens[i], tokens[i+1]) == best_pair:
                    new_tokens.append(new_token)
                    i += 2
                else:
                    new_tokens.append(tokens[i])
                    i += 1
            token_lists[word] = new_tokens
    
    return vocab, merges

Пояснения:

• В реальных токенизаторах (как в GPT-2) обучение происходит на огромном корпусе (до 40GB текста), а количество слияний — 40 000 – 50 000.
• Для кодирования нового текста применяются те же правила: текст разбивается на символы, затем последовательно применяются изученные слияния по порядку их обучения.

4. Словарь: base символы + merged токены

Итоговый словарь BPE состоит из двух частей:

• Базовые токены — все однобайтовые символы (байты от 0 до 255), если используется байтовый вариант. В GPT-2 это 256 базовых «байт-токенов».
• Merged токены — все составные токены, полученные на каждой итерации слияния. Их количество равно числу итераций num_merges (обычно несколько десятков тысяч). Таким образом, общий размер словаря = 256 + num_merges (плюс, возможно, специальные токены вроде <|endoftext|>).

Особенности словаря BPE:

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

Пет-проект для закрепления

Задача: Реализовать полный пайплайн обучения BPE на небольшом корпусе (например, несколько сотен слов на русском или английском), вывести все шаги слияний и итоговый словарь.

Инструменты: Python, стандартная библиотека (collections.Counter, defaultdict), никаких внешних NLP-библиотек.

Шаги:

1. Создать корпус в виде списка строк (например, взять словарь частотности слов или просто список слов с повторами).
2. Написать функцию get_initial_vocab — возвращает множество всех уникальных символов.
3. Написать функцию train_bpe, которая:
   • Принимает корпус и num_merges.
   • В цикле подсчитывает пары, выбирает лучшую, слияет.
   • Выводит номер итерации, лучшую пару и её частоту.
4. По завершению вывести итоговый словарь (как множество строк).
5. Написать функцию encode(text), которая принимает текст и использует обученные правила слияний для токенизации.

Ожидаемый результат:

• Программа выводит пошаговый лог обучения, например:

  Merge 1: 'l' + 'o' = 'lo' (freq=2)
  Merge 2: 'lo' + 'w' = 'low' (freq=2)
  ...
  

• После обучения словарь содержит как исходные символы, так и слитые токены.
• Функция encode("lower") возвращает правильную последовательность токенов (например, ['low', 'e', 'r'] или ['low', 'er'], в зависимости от числа слияний).

Связь с другими вопросами

Дополнительно: BPE является альтернативой Unigram LM токенизации и WordPiece; все они изучаются в контексте субсловной токенизации.

Навигация

• Предыдущий: 926
• Следующий: 928
• Индекс: 00. Индекс разборов zation methods overview|926]]
• Следующий: 928
• Индекс: 00. Индекс разборов