Byte Pair Encoding

Материал из in.wiki
Перейти к навигации Перейти к поиску

В информатике кодирование пар байтов, Byte Pair Encoding (BPE)[1][2] или кодирование диграмм[3] — это алгоритм, впервые описанный в 1994 году Филиппом Гейджем для кодирования строк текста в строки меньшего размера путём создания и использования таблицы трансляции[4]. Слегка изменённая версия алгоритма используется в токенизаторах больших языковых моделей. Первоначальная версия алгоритма была ориентирована на сжатие. Она заменяет наиболее часто встречающуюся пару байтов новым байтом, отсутствующим в исходном наборе данных. Для восстановления исходного набора данных требуется таблица поиска замен.

Изменённая версия алгоритма создаёт «токены» (единицы распознавания), соответствующие различным объёмам исходного текста, от отдельных символов (включая отдельные цифры или знаки препинания) до целых слов (даже длинных составных слов)[5][6][7].

Оригинальный алгоритм[править | править код]

Оригинальный алгоритм BPE работает путем итеративной замены наиболее распространённых смежных последовательностей символов в целевом тексте неиспользуемыми байтами-«заполнителями». Итерация заканчивается, когда не удается найти ни одной последовательности, в результате чего целевой текст остаётся фактически сжатым. Декомпрессию можно выполнить, обратив этот процесс, запросив известные термины-заполнители к соответствующей им последовательности, используя таблицу поиска. В исходной статье Филипп Гейджа эта таблица поиска кодируется и хранится вместе со сжатым текстом.

Пример:

Предположим, что нужно закодировать следующие данные[8]: 

aaabdaaabac

Пара байтов «aa» встречается чаще всего, поэтому она будет заменена байтом, который не используется в данных, например, «Z». Теперь имеем следующие массив входных данных и таблицу замен: 

ZabdZabac
Z=aa

Затем процесс повторяется с парой байтов «ab», которая заменяется на «Y»: 

ZYdZYac
Y=ab
Z=aa

Единственная оставшаяся пара байтов встречается только один раз, и кодирование может на этом остановиться. В качестве альтернативы, процесс может быть продолжен с помощью рекурсивного кодирования пар байтов, заменяя «ZY» на «X»: 

XdXac
X=ZY
Y=ab
Z=aa

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

Модифицированный алгоритм[править | править код]

Вариант алгоритма BPE модифицированный для использования в языковых моделях, особенно — больших языковых моделях, не стремится к максимальному сжатию текста, а скорее к кодированию открытого текста в «токены», представляющие собой натуральные числа[9]. Все уникальные токены, найденные в корпусе, заносятся в словарь токенов, размер которого в случае GPT-3.5 и GPT-4 составляет 100256[10]. Модифицированный алгоритм токенизации изначально обрабатывает набор уникальных символов как n-граммы длиной в 1 символ (исходные токены). Затем последовательно наиболее частая пара смежных токенов объединяется в новую, более длинную n-грамму, и все вхождения пары заменяются этим новым токеном. Это повторяется до тех пор, пока не будет получен словарь заданного размера. При этом новые слова всегда можно построить из набора символов занесённых в словарь и символов исходного текста[11]. В последние годы этот модифицированный подход BPE был распространен с устной речи на язык жестов[12].

Пример

Предположим, что мы кодируем предыдущий пример «aaabdaaabac» с заданным размером словаря 6. Тогда сначала он будет закодирован как «0, 0, 0, 1, 2, 0, 0, 0, 1, 0, 3» с словарем «a=0, b=1, d=2, c=3». Затем всё продолжится, как и раньше, и получится «4, 5, 2, 4, 5, 0, 3» с словарем «a=0, b=1, d=2, c=3, aa=4, ab=5». Пока что это, по сути, то же самое, что и раньше. Однако, если бы мы указали размер словаря 5, то процесс остановился бы на слове «a=0, b=1, d=2, c=3, aa=4», так что пример был бы закодирован как «4, 0, 1, 2, 4, 0, 1, 0, 3». И наоборот, если бы мы указали размер словаря 8, то он был бы закодирован как «7, 6, 0, 3» со словарем «a=0, b=1, d=2, c=3, aa=4, ab=5, aaab=6, aaabd=7». Это не максимально эффективно с точки зрения сжатия последовательности, но модифицированный BPE не стремится к максимальному сжатию набора данных, а стремится к его эффективному[13] кодированию для обучения языковой модели[14].

BPE на уровне байтов[править | править код]

В приведённом выше примере результатом работы BPE является словарь, который можно использовать для кодирования любого текста, состоящего из букв «abcd». Он не сможет кодировать текст, содержащий другие символы, например, «no». Даже если добавить каждую из 26 букв в словарь, поскольку в мире существует множество языков с различными письменностями, некоторые символы неизбежно будут некодируемы таким словарём. Одним из решений является замена любого некодируемого символа специальным символом UNK («неизвестно»). BPE на уровне байтов решает данную проблему путём интерпретации в UTF-8 как потока байтов. Это гарантирует, что любой текст, закодированный в UTF-8, может быть закодирован BPE. Этот подход используется в моделях типа BERT, таких как RoBERTa, BART и DeBERTa, а также в моделях типа GPT, таких как GPT-2[15][16][17].

См. также[править | править код]

Примечания[править | править код]

  1. ↑ Gage, Philip (1994). "A New Algorithm for Data Compression". The C User Journal.
  2. ↑ A New Algorithm for Data Compression. Dr. Dobb's Journal (1 февраля 1994). Дата обращения: 10 августа 2020.
  3. ↑ Witten, Ian H. Managing Gigabytes / Ian H. Witten, Alistair Moffat, Timothy C. Bell. — New York : Van Nostrand Reinhold, 1994. — ISBN 978-0-442-01863-4.
  4. ↑ Byte Pair Encoding. Архивировано из оригинала 26 марта 2016 года.
  5. ↑ Sennrich, Rico; Birch, Alexandra; Haddow, Barry (2015-08-31). "Neural Machine Translation of Rare Words with Subword Units". arXiv:1508.07909 [cs.CL].
  6. ↑ Brown, Tom B.; Mann, Benjamin; Ryde r, Nick; Subbiah, Melanie; Kaplan, Jared; Dhariwal, Prafulla; Neelakantan, Arvind; Shyam, Pranav; Sastry, Girish; Askell, Amanda; Agarwal, Sandhini (2020-06-04). "Language Models are Few-Shot Learners". arXiv:2005.14165 [cs.CL].
  7. ↑ google/sentencepiece. Google (2 марта 2021). Дата обращения: 2 марта 2021.
  8. ↑ Campesato, Oswald. Large Language Models for Developers: A Prompt-based Exploration of LLMs : [англ.]. — Walter de Gruyter GmbH, 2024-12-26. — ISBN 978-1-5015-2095-2.
  9. ↑ Zhang, Xiang; Cao, Juntai; You, Chenyu (2024). "Counting Ability of Large Language Models and Impact of Tokenization". arXiv:2410.19730 [cs.CL].
  10. ↑ Raschka, Sebastian. Implementing A Byte Pair Encoding (BPE) Tokenizer From Scratch (англ.). Sebastian Raschka, PhD (17 января 2025). Дата обращения: 5 июля 2025.
  11. ↑ Paaß, Gerhard. Pre-trained Language Models // Foundation Models for Natural Language Processing / Gerhard Paaß, Sven Giesselbach. — 2022. — P. 19–78. — ISBN 9783031231902. — doi:10.1007/978-3-031-23190-2_2.
  12. ↑ Pai, Suhas. Designing Large Language Model Applications: A Holistic Approach to LLMs : [англ.]. — O'Reilly Media, 2025-03-06. — ISBN 978-1-0981-5046-4.
  13. ↑ При этом эффективность кодирования для целей обучения конкретной языковой модели определяется соображениями её разработчика о её архитектуре и доступными аппаратными средствами.
  14. ↑ Pai, Suhas. Designing Large Language Model Applications: A Holistic Approach to LLMs : [англ.]. — O'Reilly Media, 2025-03-06. — ISBN 978-1-0981-5046-4.
  15. ↑ Byte-Pair Encoding tokenization. Hugging Face NLP Course. Дата обращения: 27 января 2025.
  16. ↑ Yıldırım, Savaş. Mastering Transformers: Build state-of-the-art models from scratch with advanced natural language processing techniques : [англ.] / Savaş Yıldırım, Meysam Asgari Chenaghlu. — Packt Publishing Ltd, 2021-09-15. — ISBN 978-1-80107-889-4.
  17. ↑ Wang, Changhan; Cho, Kyunghyun (2020-04-03). "Neural Machine Translation with Byte-Level Subwords". Proceedings of the AAAI Conference on Artificial Intelligence (англ.). 34 (5): 9154–9160. arXiv:1909.03341. doi:10.1609/aaai.v34i05.6451. ISSN 2374-3468.
Источник — https://in.wiki/w/index.php?title=Byte_Pair_Encoding&oldid=1574464