Автоматизация иммерсивного чтения: как работает алгоритм принудительного выравнивания Storyteller

Все дети, кроме одного, вырастают. Они скоро узнают, что вырастут, и вот как узнала об этом Венди. Однажды, когда ей было два года, она играла в саду и, срезав ещё один цветок, побежала с ним к матери. Наверное, она выглядела очень мило, потому что миссис Дарлинг прижала руку к сердцу и воскликнула: «Ах, почему ты не можешь оставаться такой всегда!» Это всё, что было сказано между ними на эту тему, но с тех пор Венди знала, что ей суждено вырасти. После двух лет это знаешь всегда. Два года — это начало конца.

Питер и Венди, Дж. М. Барри

Storyteller превратился в разветвлённую экосистему программного обеспечения: полноценное веб-приложение, нативные приложения для Android и iOS, плагины для KOReader, а также готовящиеся к выходу приложения для macOS, watchOS и tvOS. Сейчас идёт альфа- и бета-тестирование третьей версии всех этих продуктов — она принесёт обновлённый интерфейс, огромный набор новых функций управления библиотекой и многое другое.

В основе Storyteller лежит алгоритм выравнивания. Storyteller принимает электронную книгу и аудиокнигу и выравнивает их — находит, в какой момент аудиокниги произносится каждое слово из текста. Это происходит автоматически, без какого-либо участия пользователя. Затем система использует встроенный в спецификацию EPUB механизм синхронизации аудио — Media Overlays, — чтобы встроить в EPUB и сам аудиофайл, и информацию о синхронизации. Благодаря этому книгу можно читать иммерсивно: приложение-читалка подсвечивает каждое предложение по мере того, как его озвучивает диктор — точно так же, как в демонстрации выше, где используются реальные данные выравнивания Storyteller.

Изначально Storyteller представлял собой всего один Python-скрипт. Он принимал на входе файл аудиокниги и файл электронной книги, а на выходе выдавал новый файл ebook с метаданными синхронизации аудио. В то время существовало совсем немного приложений для чтения (и ни одного устройства-читалки), способных воспроизводить такие файлы, использующие спецификацию EPUB Media Overlay. Скрипт запускался на компьютере, готовый EPUB копировался на телефон, а затем использовалась зачаточная поддержка Media Overlay в BookFusion, чтобы читать и слушать книги одновременно.

На тот момент область принудительного выравнивания (forced alignment), в которую пришлось погрузиться с головой, была совершенно неизвестна. Первый алгоритм выравнивания представлял собой шаткую конструкцию из громоздких вложенных циклов while. Ощущение было такое, будто идёшь наощупь в темноте, зная, что где-то впереди есть свет, но не видя его.

Сложности

Тем не менее по пути обнаружилось несколько важных наблюдений. Существующие системы принудительного выравнивания — даже те, что были специально созданы для синхронизации ebook и аудиокниг, — сталкивались с рядом типичных для книг проблем. Даже самая первая, неуклюжая попытка справлялась с ними — с разной степенью успеха.

Порядок глав

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

Отсутствие глав

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

Пропущенные фрагменты

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

Замена слов

Иногда режиссёры озвучки или сами дикторы намеренно заменяют слово или фразу, если оригинальный вариант сложно произнести гладко или он звучит неестественно при чтении вслух. Кроме того, случаются и просто ошибки.

Из перечисленных проблем даже довольно простые системы принудительного выравнивания, как правило, спокойно справляются с заменой слов. Пропущенные фрагменты сложнее — особенно когда аудио пропускает участки текста, — но результат обычно не катастрофичен, просто неидеален.

А вот пропущенные и переставленные главы способны полностью сломать работу многих систем выравнивания. Инструменты, существовавшие до Storyteller, например, весьма неплохой syncabook, требовали, чтобы пользователь заранее указал соответствие глав электронной книги главам аудиокниги. Это одновременно и очень трудоёмко, и довольно сложно технически, поскольку многие аудиокниги вообще не содержат метаданных о главах или отдельных файлов на каждую главу.

Требовалось решение получше — а значит, нужно было решить именно эту проблему. Требовался алгоритм поиска.

Предварительная задача: поиск границ

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

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

Так что простого пути нет. Но хотя полную точную транскрипцию аудио получить нельзя, можно получить какое-то текстовое представление. Для этого используется модель Massively Multilingual Speech², генерирующая CTC-эмиссии, которые затем жадно декодируются в текст.

Дальше — подробное объяснение всей этой терминологии. Придётся копнуть довольно глубоко, и будут графики.

CTC, Wav2Vec 2.0 и MMS

Connectionist Temporal Classification (CTC — звучит как что-то из «Дюны») уже больше десяти лет остаётся стандартным инструментом автоматического распознавания речи и принудительного выравнивания. По сути, это функция потерь — та функция, которую модели машинного обучения используют для оценки своего вывода и обучения. Чтобы работать с этой функцией потерь, модель должна содержать «CTC-голову» — слой, выдающий «CTC-эмиссии». Эмиссии представляют собой промежуточное представление, используемое CTC, — подробнее о них чуть позже.

Поскольку любая модель с CTC-головой выдаёт результат одинаковой формы (те самые CTC-эмиссии), существуют стандартные алгоритмы для дальнейшего декодирования эмиссий в текст. В данном случае важны два: «неограниченное жадное декодирование» и «принудительное выравнивание Витерби». Оба будут подробно рассмотрены далее.

Итак, есть способ превратить внутреннее представление модели в эмиссии — через CTC-декодер. Wav2Vec 2.0 работает в обратную сторону — это предобученный кодировщик, отвечающий за превращение аудиоданных во внутреннее представление, с которым может работать модель машинного обучения.

Сама модель, объединяющая кодировщик Wav2Vec 2.0 и CTC-декодер и затем дообученная на некотором корпусе данных так, чтобы «выучить» веса, минимизирующие функцию потерь CTC, называется Massively Multilingual Speech, или MMS.

Можно взять аудио, подать его в MMS порциями и получить на выходе CTC-эмиссии. Сами эмиссии представляют собой двумерную матрицу: один вектор вероятностей символов³ на каждый кадр аудио, где кадр — это 20 миллисекунд звука.

Декодирование без меток

Теперь, когда есть эмиссии, нужно решить предварительную задачу: найти, где в аудио начинается и заканчивается каждая глава. Приятная особенность эмиссий в том, что они регулярны — поскольку каждый вектор эмиссии представляет один 20-миллисекундный кадр аудио, зная, в каком кадре начинается глава, автоматически известно и в какую миллисекунду она начинается.

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

Этот алгоритм можно назвать «неограниченным жадным декодированием». Неограниченным — потому что не было базового текста, к которому нужно декодировать, а жадным — потому что на каждом шаге выбирается лучшая вероятность без пересмотра предыдущих шагов. Вот что получается, если запустить его на всём разделе из демонстрации в начале статьи:

Полученный текст довольно похож на текст электронной книги! И сходство можно усилить, «приведя» текст ebook к тому же виду: убрав пунктуацию, схлопнув пробелы и переведя все символы в нижний регистр. Числа можно даже преобразовать в написание словами, например «2000» в «две тысячи». Подробнее о том, как выполнить такое приведение текста без потери информации о его исходном расположении в XHTML, было рассказано в одной из предыдущих статей.

N-граммы с RANSAC

Заметно, что жадное декодирование не идеально совпадает с искомым текстом. И это лишь очень небольшой фрагмент — в большинстве аудиокниг встречается множество отклонений от текста ebook, как уже было сказано выше, а сам процесс жадного декодирования обычно допускает массу ошибок транскрипции. Поэтому просто просканировать документ в поисках точного совпадения с искомым текстом не получится.

Вместо этого нужно разбить документ и запрос на фрагменты, достаточно маленькие, чтобы многие из них совпадали между собой. Такие фрагменты называются «n-граммами». В данном случае «грамма» соответствует одному символу, а значение «n» — 10. И в документе, и в запросе фиксируется каждый 10-символьный участок вместе с позицией его начала. Многие такие участки встречаются в обоих текстах — эти совпадения и позволяют найти нужный фрагмент запроса внутри документа!

У этого алгоритма есть несколько по-настоящему приятных особенностей:

1. Он крайне устойчив к шумным декодированиям. Независимо от того, много ли отклонений в озвучке от текста ebook, или жадное декодирование справилось с оценкой произнесённого контента особенно плохо, — даже если совпадает лишь 10% n-грамм, это всё равно тысячи точек, по которым можно строить линию поиска.
2. Он даёт много дополнительной информации. Об этом подробнее чуть позже, но данные этого алгоритма — например, локальный темп речи и расположение известных «инлайеров» — используются на этапе непосредственного принудительного выравнивания.
3. Он действительно эффективен!

Принудительное выравнивание

Теперь, благодаря поиску границ методом «n-грамм с RANSAC», известно, где в эмиссиях аудиокниги начинается и заканчивается каждая глава. Это позволяет перейти к более прямолинейному алгоритму принудительного выравнивания — алгоритму Витерби для CTC.

Принудительное выравнивание обычно формулируется как задача глобальной оптимизации⁴. Есть некая функция потерь — например, «сумма вероятностей всех выбранных символов», — и требуется максимизировать значение этой функции по всей главе. В общем случае такие задачи глобальной оптимизации сложно вычислять эффективно: перебор всех возможных вариантов, чтобы сравнить их и найти лучший по оценке, обычно обходится очень дорого. Но здесь на помощь приходят два приёма:

Опорные точки совпадений

При вычислении совпадений ранее были найдены несколько n-грамм, встречающихся и в главе, и в аудио. Когда с помощью RANSAC были отобраны «инлайеры», остались совпадения, в реальности которых можно быть достаточно уверенным. Если добавить ещё одно условие — рассматривать только те совпадения, что глобально уникальны в своих документах, — то в их достоверности можно быть весьма уверенным. Поскольку точно известно, что глава и аудио совпадают именно в этих точках, алгоритм принудительного выравнивания достаточно запускать только на кадрах между этими опорными точками. Это значит, что главу и аудио можно разбить по опорным точкам и запускать выравнивание только на одном сегменте за раз.

Если искать такую уникальную опорную точку приблизительно каждые 2000 символов, то алгоритм принудительного выравнивания достаточно запускать порциями примерно по 2000 символов, а не на всей главе целиком, которая может содержать десятки тысяч символов и более!

Витерби

Второй «приём» — это алгоритм Витерби. Витерби — это алгоритм динамического программирования по принципу «снизу вверх»: он находит решение, сначала решая подзадачи, а затем строя итоговое решение из решений подзадач. Ключевая идея, позволяющая применить динамическое программирование к задаче выравнивания CTC, такова:

Для состояний A, B и C: если B лежит на кратчайшем пути от A к C, то участок этого кратчайшего пути от A до B сам должен быть кратчайшим путём от A до B. Если бы это было не так, этот участок можно было бы заменить более коротким путём от A до B, что сделало бы и весь путь от A до C короче.

Чтобы пояснить подробнее, возьмём первое слово главы — «All» («Все»). Как было показано выше, эмиссии содержат несколько кадров на каждый символ этого слова, и каждый вектор кадра содержит вероятности для каждого символа словаря (буквы от «a» до «z», плюс токен «пробел» для случаев, когда ничего не произносится или модель не может распознать текущий символ).

Нужно найти путь через кадры, который складывается в слово «all». Путь состоит из состояний и переходов. Состояния — это текст главы. При построении возможных состояний между каждыми двумя буквами вставляется пустой токен. Это позволяет представлять двойные буквы, как «ll» в слове «all», в виде «l → пробел → l» в пути. Так что последовательность состояний выглядит как «пробел → a → пробел → l → пробел → l → пробел».

Допустимые переходы: остаться в текущем состоянии; перейти к следующему состоянию; или пропустить следующее пустое состояние и перейти к состоянию после него. Переход с пропуском допустим только между неравными символами, поэтому можно пропустить пробел между «a» и «l», но не между двумя «l».

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

Один из способов решения — перечислить все возможные пути, посчитать их суммарные оценки и выбрать лучший. В данном примере 7 кадров и 7 состояний, а число возможных путей через кадры составляет 210. И это только для одного слова. При увеличении числа кадров и состояний с 7 до, скажем, 70 000, это число растёт экспоненциально.

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

Сначала заполняется вектор из 7 чисел, по одному на каждое состояние. Это «вектор текущих оценок». Изначально во всех позициях, кроме первых двух — возможных начальных состояний — стоит минус бесконечность: индекс 0 — начальный пробел, индекс 1 — «a». Для этих двух состояний используются оценки непосредственно из первого кадра эмиссий: у пробела -8.56, у «a» -0.00.

Далее происходит проход по кадрам. На каждом кадре анализируются оценки следующего кадра, чтобы определить, какой переход выбрать. Для начального пробела можно либо остаться на пробеле (оценка в следующем кадре -0.00), либо перейти на «a» (оценка -9.16). Лучшая оценка — -0.00, значит, лучший переход — «остаться». Записывается переход «остаться» для токена 0 в кадре 0, и в вектор текущих оценок для начального пробела заносится -8.56 + -0.00 = -8.56.

Для «a» можно остаться на «a» (оценка в следующем кадре -9.16), перейти на следующий пробел (оценка -0.00) или пропустить следующий пробел и перейти прямо к первой «l» (оценка -10.47). Лучшая оценка — переход к следующему пробелу, поэтому записывается переход «дальше» для токена 1 в кадре 0, а в вектор текущих оценок для состояния «a» заносится -0.00 + -0.00 = -0.00.

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

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

А в итоге это означает, что вместо сравнения 210 путей достаточно вычислить всего 2! Ровно один оптимальный путь заканчивается в каждом из допустимых конечных кадров — второй «l» или финальном пробеле. Лучший путь — тот, у которого лучшая оценка (в данном случае это путь ко второй «l»).

Теперь остаётся лишь пройти по кадрам и отследить, на каком кадре начинается и заканчивается каждый токен. Первая «l», например, произносится на протяжении двух кадров — третьего и четвёртого. А поскольку каждый кадр длится ровно 20 мс, это позволяет определить время начала и окончания для каждой буквы.

Если немного отступить от деталей, это позволяет определить время начала и окончания каждого слова и предложения в книге. Попробовать это можно самостоятельно с помощью нового флага --ctc в stalign, либо через новую опцию CTC aligner в бета-версии Storyteller v3. Для тех, кто пока не использует бету — не беда, скоро она станет доступна всем.

Довольно изящное решение, не правда ли?