Эта заметка для более продвинутых в ML (в отличие от основной массы предыдущих постов): для тех, кто постигает таинства анализа текстов, поскольку речь пойдёт о предобработке текстовых данных, которая может улучшить качество в некоторых задачах.

При обработке текста на естественном языке (NLP) одним из стандартных этапов является токенизация (часто говорят сегментация) — разбиение данных на элементарные части (например, текст на предложения или на слова). Оказывается, что разбивка на слова не всегда достаточна для обеспечения высокого качества решения задачи машинного обучения, скажем слова «сеть», «сети», «сетью» и «сетевой» являются разными словами, но имеют схожий смысл. Эту проблему классически всегда решал этап стемминга (удаление суффикса, приставки, окончания) или лемматизации (приведение слова к канонической форме). Но все проблемы эти этапы не решают, что особенно заметно в машинном переводе, поскольку многие языки являются синтетическими и словообразование в них более сложное по сравнению с аналитическим английским языком.

Например, немецкое слово «Abwasserbehandlungsanlange» означает «станция очистки сточных вод» и является конкатенацией соответствующих слов. В идеале, перед подачей в какую-нибудь рекуррентную/attention-сеть желательно разбить слово на соответствующие подслова. Даже в английском языке, например, слово «subword» напрашивается разбить на «sub» + «word». Этот приём, кстати, может помочь с проблемой OOV (out of vocabulary) — в обучающей выборке может не быть слова «subtask», но поскольку «subtask» = «sub» + «task», а эти слова (подслова), допустим, есть в обучении, мы можем надеяться, что сеть будет правильно обрабатывать / генерировать и слово «subtask».

Для решения проблемы OOV, прежде всего в машинном переводе (но затем и в распознавании речи и языковых моделях), стали использовать т.н. Subword Tokenization — токенизацию на подслова. Ниже рассмотрим популярные методы такой токенизации.

Byte Pair Encoding (BPE)

Идея похожа на коды Хафмана, собственно сам термин пошёл из работы по кодированию [Philip Gage, 1994].

Обучение BPE

1. Слово = последовательность токенов (пока символов, изначально использовались unicode-символы)
2. Словарь = все токены (на нулевой итерации — символы)
3. Повторять пока не достигли ограничения на размер словаря
   • Назначаем новым токеном объединение двух существующих токенов, которое встречается чаще других пар в корпусе (имеется в виду: встречаются вместе).

В применении BPE возможны разные варианты, один из естественных – идём по всем токенам по убыванию частоты, находим соответствующую последовательность символов в корпусе, заменяем на токен.

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

На практике:

• К словам добавляется спецсимвол «конец слова».
• Различают изолированные токены (слова) и токены-подслова. Например,

  «I</w> like</w> ke</w>» → «I</w>», «li», «##ke</w>», «ke</w>»

  здесь «ke» кодируется по-разному, в зависимости от того, изолированное это слово или часть слова «like».

• В GPT2 этот метод использован над байтами!
• В GPT2 запрещалось склеивание пар токенов разных типов (изначально каждому токену приписывался тип), например, нельзя склеивать букву и знак препинания, т.е. токен «a?» мы никогда не получим.

Метод описан в статье

• Rico Sennrich, Barry Haddow, Alexandra Birch Neural Machine Translation of Rare Words with Subword Units https://arxiv.org/abs/1508.07909

Из интересного, обратите внимание, что одна из метрик качества там CHRF3 – a character  n-gram F₃-score, которая очень хороша для оценки машинного перевода, поскольку согласуется с мнениями ассесоров.

WordPiece

Если кратко, то WordPiece – это BPE, в котором при слиянии токенов мы максимизируем правдоподобие, а не частоту. Изначально этот метод использовался в BERT, но авторы RoBERTa показали, что особых преимуществ перед BPE не видно.

Метод был предложен в работе

• Schuster, Nakajima «Japanese and Korea voice search», 2012 https://static.googleusercontent.com/media/research.google.com/ja//pubs/archive/37842.pdf

В рассматривоемой там задаче в текстах было очень мало пробелов (собственно, почему и потребовалось расщеплять цепочки символов на элементарные). Заметим, что формально метод появился до BPE (в машинном обучении).

Unigram Language Model (ULM)

В отличие от описанных выше методов, здесь получается целое распределение над сегментациями (из которого можно сэмплировать). Предполагается, что все подслова независимые, поэтому вероятность p(x) слова x равна произведению вероятностей входящих слов p(x_i), ищется подходящая сегментация. Метод применяется так:

1. Создать большой словарь (любой эвристикой – например, буквы + наиболее частые подслова, или Enhanced Suffix Array algorithm [Nong et al., 2009], можно также использовать BPE).

2. Повторять, пока размер словаря не достигнет порога:
   • Зафиксировав словарь, максимизировать p(x) с помощью EM-алгоритма
   • Для каждого подслова w вычислить loss_w – насколько уменьшится правдоподобие при удалении слова из словаря
   • Оставить 80% слов с максимальным loss_w (символы оставлять всегда, чтобы не было OOV)

Подробное описание лучше смотреть в оригинальной статье:

• Taku Kudo « Subword Regularization: Improving Neural Network Translation Modelswith Multiple Subword Candidates» // Google, 2018, https://arxiv.org/pdf/1804.10959.pdf

Sentencepiece

По сути это не метод, а библиотека с открытым кодом, которая описана в работе

• Taku Kudo, John Richardson «SentencePiece: A simple and language independent subword tokenizerand detokenizer for Neural Text Processing» // https://www.aclweb.org/anthology/D18-2012.pdf

в ней, собственно, реализованы наработки автора ULM из компании Google. Из некоторых фишек:

• есть возможность рассматривать пробелы как отдельные символы и не схлопывать при токенизации

Использовать библиотеку в своих проектах очень просто, ниже пример кода:

# загружаем библиотеку
import sentencepiece as spm
# обучение из файла text.txt
spm.SentencePieceTrainer.Train('--input=test/text.txt --model_prefix=m --vocab_size=1000')
# загружаем обученную модель
sp = spm.SentencePieceProcessor()
sp.Load("m.model")
# теперь кодируем текст
sp.EncodeAsIds("I like ke")

BPE-Dropout

Это метод от ребят из Яндекса, опубликованный месяц назад:

• Ivan Provilkov, Dmitrii Emelianenko, Elena Voita «BPE-Dropout: Simple and Effective Subword Regularization» // https://arxiv.org/pdf/1910.13267.pdf

Статья получилась очень хорошая. Во-первых, интересна сама идея, которая, скорее всего, была позаимствована из работ автора ULM (он писал о связи своего метода с Dropout). Во-вторых, в ней сделан большой объём экспериментов (очень качественно продуманных).

Метод пытается бороться со следующими недостатками BPE:

• каждое слово имеет однозначную сегментацию,
• подслова редких слов не очень интерпретируемы.

Для этого предлагается следующее: использовать словарь и таблицу слияний BPE, но на каждом шаге слияния случайно его пропускать («дропать»).  Это показано на рис. из статьи:

Слева — результат слияний в BPE, справа — три варианта результата при пропуске некоторых слияний. Если задаться вероятностью пропуска p (кстати, в экспериментах авторов оптимальное значение p=0.1), то при p=0 получаем BPE, а при p=1 — сегментацию по буквам. На практике BPE-Dropout показал себя лучше BPE и ULM.

В заключение можно привести иллюстрацию из статьи

• Benjamin Heinzerling and Michael Strube «BPEmb: Tokenization-free Pre-trained Subword Embeddingsin 275 Languages» // https://arxiv.org/pdf/1710.02187.pdf

в которой вложения (embeddings), полученные с помощью BPE, сравнивались с вложениями токенов (word2vec), посимвольным (character) и FastText-ом при использовании разных типов нейронных сетей.

Другие ссылки

• 3 subword algorithms help to improve your NLP model performance

• A Deep Dive into the Wonderful World of Preprocessing in NLP

• Пример токенизации на русском языке при разной длине словаря (есть красивые картинки)
• Эта заметка частично основана на лекции курса автора «Deep Learning» и докладе Дмитрия Обухова на семинаре компании Dasha.ai