Insertion Transformer: Flexible Sequence Generation via Insertion Operations
Mitchell Stern, William Chan, Jamie Kiros, Jakob Uszkoreit
Google Brain, 2019

Статья: https://arxiv.org/abs/1902.03249

#nlp #nlg #nonautoregressive #transformer #icml #2019

Итак, раз уж мы научились сэмплировать токены в произвольном порядке, зачем делать это по одному за раз, нельзя ли в этом месте оптимизировать процесс? Авторы предлагают архитектуру Insertion Transformer, которая довольно-таки похожа на INTRUS из предыдущей статьи, но позволяет сэмплировать по нескольку токенов за шаг.

Начинаем всегда с пустой строки = единственного слота. На каждом шаге модель выдаёт на выходе совместное распределение по доступным слотам (= число уже имеющихся токенов + 1) и словарю токенов. И тут допускается одновременная вставка нескольких токенов -- максимально по числу имеющихся слотов.

Модификации по сравнению с обычным трансформером:
- Как и ранее, в декодере снимается стандартная для декодеров трансформеров casual self-attn mask, запрещающая видеть токены правее текущего.
- Пусть вход у нас из n токенов — добавляем на вход два дополнительных токена в начало и в конец, это даёт нам на выходе n+2 позиционных вектора, дальше конкатенацией каждой пары соседних выходных векторов мы получаем n+1 векторов, каждый из которых соответствует одному из возможных слотов
- Дальше из матрицы этих векторов H, соответствующих слотам, вычисляются вероятности совместного распределения (слот, токен). Тут в базовом варианте делается просто проекция+софтмакс в вероятности совместного распределения (слот, токен).
- Дополнительно рассматривают три модификации расчёта вероятностей слотов и токенов: Joint (через условную вероятность, как в INTRUS), Context (с добавлением общего для всех слотов bias, построенного max-polling-ом из H) и Mixture (Mixture-of-Softmaxes Output Layer из [arxiv:1711.03953]).

Далее эту архитектуру тренировали на нескольких фиксированных последовательностях вставок (не оптимизируя lower bound как в INTRUS, а явно задавая стратегию сэмплинга). Использовалось 4 стратегии:
- left-to-right: слева направо, имитация стандартной авторегрессионной модели, на каждом шаге таргет на угадывание крайнего правого из доступных слотов и правильного следующего токена в нём, остановка по <EOS>.
- binary-tree: сбалансированное бинарное дерево -- сначала предсказываем средний токен, потом средние в левой и правой половине, на k-ом шаге дописываем сразу 2^k токенов, т.е. в идеале число шагов ~ логарифм от длины строки. Чтобы учить такое, мы сначала на каждом шаге обучения выбираем случайную подпоследовательность токенов полного таргета (тут есть тонкости в том, чтобы сделать подпоследовательности разной длины равновероятными), а затем считаем таргет следующего шага для каждого слота как каждый отсутствующий там токен с вероятностью, взвешенной на его расстояние до центра бреши (с температурой, которая — гиперпараметр).
- uniform: равномерно случайная генерация -- с одинаковой вероятностью каждого возможного верного шага, технически это вариант binary-tree с бесконечной температурой.

Как устроено сэмплирование:
- Жадное -- выбираем 1 пару (слот, токен) с максимальной вероятностью, её вставляем, итерируем.
- Параллельное -- для каждого слота считаем вероятности токенов, если там топ1 по вероятности это end-of-slot, ничего не сэмплируем; в остальные слоты вставляем их топ1 по вероятности; итерируем (пока все не предскажут end-of-slot) + есть возможность распараллелить вычисления этих распределений для токенов в разных слотах.
- Чтобы уметь как-то останавливаться в стратегиях binary-tree и uniform, добавляем служебный токен end-of-slot, который говорит, что ничего в этот слот сейчас сэмплить не надо. Таким образом, признаков для остановки два: когда строка дописана и пришёл <EOS>, или когда все имеющиеся слоты голосуют за end-of-slot.

Экспериментировали на  WMT 2014 English-German, на тестах заметили, что модель рано начинает сэмплить end-of-slot и end-of-sequence, и быстро останавливается на коротком выхлопе. Заткнули это место костылём, вычитая везде β из логпробов обоих этих токенов, β подбирали перебором на интервале [0,7] отдельно для каждой версии модели, оптимальное значение β даёт до +4 на BLEU у слабых моделек и поменьше у сильных. Ещё 3-4 пункта BLEU дожали на дистилляции модели.

На сравнении модификаций архитектуры (Joint/Context/Mixture) показали, что хотя из них и можно выжать чуть-чуть профита, но очень мало (и при подстройке β к оптимуму уходит и этот профит). В целом, по качеству получили оптимум на варианте с бинарным деревом и температурой 2 (почти неотличимый от варианта с температурой 1).

Параллельное декодирование (что с деревом, что с uniform) действительно позволяет генерировать результат за число вставок, близкое к логарифму от числа токенов, что является оптимальным для такой схемы.

Продолжение следует.

KERMIT: Generative Insertion-Based Modeling for Sequences
William Chan, Nikita Kitaev, Kelvin Guu, Mitchell Stern, Jakob Uszkoreit
Google Research, 2019

Статья: https://arxiv.org/abs/1906.01604

#nlp #nlg #nonautoregressive #transformer

Предыдущая работа (про Insertion Transformer) показала, что можно учить достаточно эффективные неавторегрессионные модели на конкретных стратегиях, задающих последовательность сэмплинга. Авторы данной статьи хотят честно учесть все возможные последовательности сэмплирования сразу, предлагая модель KERMIT (Kontextuell Encoder Representations Made by Insertion Transformations). Упрощённо говоря, работа предлагает синтез подхода, который был в INTRUS и подхода из Insertion Transformer.

Сопоставим каждому возможному пути генерации строки перестановку индексов токенов, которая и задёт последовательность генерации. Полный явный перебор по всем возможным маршрутам по прежнему невозможен, но с помощью неравенства Йенсена и ряда преобразований можно получить удобную нижнюю оценку на log-likelihood, позволяющую использовать следующий алгоритм:
- равномерно случайно сэмплируем шаг генерации (т.е. сколько токенов уже сгенерированно),
- случайно сэмплируем частичную перестановку из всех возможных перестановок на этом шаге генерации (т.е. выбираем конкретный путь, который мы прошли на пути к этому шагу генерации),
- вычислим loss как сумму loss-ов для каждого возможного следующего шага, взвешенную на условную вероятность следующей позиции и нормированную на длину предложения.

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

На шаге генерации предлагается использовать один из двух вариантов:
- жадная стратегия -- генерация по одному наиболее вероятному следующему шагу -- в этом случае мы получаем что-то очень похожее на INTRUS.
- параллельное декодирование -- генерируем сразу во все доступные слоты, это прямой аналог подхода из Insertion Transformer.

Дальше авторы обсуждают seq2seq задачи и показывают, что если рассматривать входную строку как конкатенацию двух строк (x,y), то использование KERMIT позволяет построить совместное распределение p(x,y), маргинальные распределения p(x) и p(y) и условные распределения p(x|y), p(y|x). Действительно, если учить KERMIT генерировать (x,y) с нуля сразу как одну строку, то это будет совместное распределение, а если, например, в обучении использовать только задачу генерации x по y, то модель выучит p(x|y). Кроме того, показывается, что можно делать доводку такой модели на основании отдельных наблюдений x или y, и это помогает добрать качества.

Технически, в качестве модели как обычно трансформер без максирования декодера, в качестве задачи -- NMT, в качестве метрики BLEU. Показывают, что модель даёт примерно логарифмическое время генерации и качество выше бейзлайнов.

Дополнительно сравнивают KERMIT с GPT и BERT на задачах GLUE и на задаче Zero-Shot Cloze Question Answering; утверждают, что KERMIT это удобный вариант, почти не проигрывающий BERT на GLUE, но имеющий при этом возможность свободной генерации текста, а на Zero-Shot Cloze Question Answering он обходит оба бейзлайна.

Non-Monotonic Sequential Text Generation
Sean Welleck, Kianté Brantley, Hal Daumé III, Kyunghyun Cho
куча разных аффилиаций, 2019

Статья: https://arxiv.org/abs/1902.02192
Код: https://github.com/wellecks/nonmonotonic_text

#nlp #nlg #nonautoregressive #transformer #icml

Авторы данной работы рассматривают в целом ту же задачу, что и авторы KERMIT-а — научиться делать параллельную генерацию, не задавая явной стратегии выбора последовательности генерации, но используют принципиально другой подход — тёмную магию imitation learning. Грубо говоря, это такая смежная с RL область, где агент не знает своей функции награды в явном виде и старается вывести её из наблюдения за действиями неидеального "эксперта", предполагая, что эксперт эту функцию знает и пытается оптимизировать. Такой подход, в теории, позволяет не просто научиться копировать действия эксперта, но и превзойти его по объективным метрикам.

Давайте предположим, что мы хотим генерировать текст рекурсивно по бинарному дереву, примерно как в binary-tree варианте модели Insertion Transformer. Начинаем с пустой строки и сэмплируем первый токен, затем для каждого токена на каждом шаге сэмплируем по одному токену слева и справа от него. Каждый из таких слотов может выбрать токен <end>. Закончив, расплющиваем дерево в последовательность и удаляем токены <end>, получая, таким образом, итоговую последовательность. Проблема в том, что разных возможных деревьев много, а мы не хотим фиксировать конкретную стратегию выбора, т.е. мы хотим, чтобы модель сама выбрала оптимальную.

Пусть состояние это <текущее дерево>+<рассматриваемый для следующего шага генерации узел в нём>, действие — выбор следующего токена для этого узла. Зафиксируем, что current policy π — это модель, которую мы учим, и oracle policy π* — эксперт, поставляющий нам образцы для обучения.

Если упрощать, то предлагаемое обучение с помощью oracle policy устроено так так:
- На первом шаге (когда текущая строка пуста) оракул выбирает случайный правильный токен из целевой последовательности (он потому и оракул, что знает, что должно получиться в итоге).
- Далее, рекурсивно выбираем правильные токены слева и справа от текущих, под правильным понимается любой возможный в текущей бреши, т.е. любой из токенов, отсутствующих между текущим и следующим уже сгенерированным, а для разрешения неоднозначностей будем использовать оценку качества из current policy, т.е. брать наиболее вероятный токен по мнению текущей модели. Если брешь уже закрыта, т.е. ничего здесь вставлять не нужно, будем предсказывать специальный токен <end>.
- Затем, для заданного таргета Y будем случайно сэмплировать состояния из состояний оракула по дороге к Y.
- На выбранных состояниях будем считать loss как разницу между предсказанным действием нашей модели и фактического действия оракула, по этому loss будем оптимизировать модель.

Теперь чуть подробнее:
- Для оценки цены предсказания (cost-to-go) в заданном состоянии будем использовать KLD между моделью и оракулом по доступным actions. Для того, чтобы определить loss модели, надо задать, по какому множеству состояний мы будем усреднять этот cost-to-go.
- Для этого, по науке, в imitation learning используются специальные roll-in policies, в качестве которых часто используют взвешенную стохастическую смесь current policy и oracle policy, это делается для того, чтобы сначала модель училась в основном на состояниях, поставляемых оракулом (они надёжнее, пока модель неразумна), а затем постепенно переходила к оценке собственных маршрутов. На практике, пишут авторы, часто надёжнее и успешнее работает использование распределения состояний только из oracle policy до конца обучения.

Далее, авторы рассматривают несколько вариантов oracle policy (в рамках заданных выше условий):
- Uniform Oracle — выбираем любой из доступных в бреши токенов равномерно случайно,
- Coaching Oracle — используем распределение по доступным токенам, взвешенное на текущую оценку вероятности токена от обучаемой модели,
- Annealed Coaching Oracle — вариант линейной комбинации Uniform Oracle и Coaching Oracle, меняющейся во времени: начинает как Uniform Oracle, но по ходу обучения постепенно смещается к Coaching Oracle, это делается для того, чтобы пока обучаемая модель глупая, случайный сигнал от неё не ломал нам подсказки оракула.
- Deterministic Left-to-Right Oracle — всегда предсказываем первый справа отсутствующий токен, по сути, это такая имитация бейзлайна (обычной авторегрессионной генерации).

В качестве моделей рассматривали LSTM и Transformer, экспериментировали на задачах LM, MNT и прочее. Как и в работе про INTRUS, изучали предлагаемые последовательности генерации, например, с помощью POS-разметки.

Примерно везде Annealed Coaching Oracle оказался оптимальным, при этом POS анализ показывает, что он тоже начинает генерацию с пунктуации и простых слов, как указывалось в ряде предыдущих статей.