Быстрый и эффективный алгоритм со встроенной языковой моделью для декодирования выходных данных нейронной сети в контексте распознавания текста

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

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

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

Краткое напоминание о том, как работает CTC

Прочтение статьи Интуитивное объяснение коннекционистской временной классификации поможет вам разобраться в следующем обсуждении. Здесь я дам краткое резюме.

CTC позволяет обучать системы распознавания текста с помощью пар изображений и реальных текстов. Текст кодируется в выходной матрице NN путями, которые содержат один символ для каждого временного шага, например «Ab» или «aa» - возможные пути на рис. 1. Я покажу текст в двойных кавычках «текст», а пути в одинарных кавычках «путь».

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

Вот примеры текстов с соответствующими путями:

  • «К» → ‘-t-o ---’, ‘tttttttt-ooo-’, ‘to’,…
  • «Привет» → «х-элллл-лл-ооо», «привет-ло»,…
  • “a” → ‘aa’, ‘a-’, ‘-a’, …

Как видите, тексту может соответствовать несколько путей. Когда нас интересует вероятность появления текста, мы должны просуммировать вероятности всех соответствующих путей. Вероятность одного пути - это произведение вероятностей символов на этом пути, например для пути «аа» на рис. 1 это 0,2 · 0,4 = 0,08.

Декодирование наилучшего пути

Декодирование наилучшего пути - это самый простой метод декодирования выходной матрицы:

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

Давайте посмотрим на пример: матрица показана на рис. 2. Символ с наивысшей оценкой остается пустым для обоих временных шагов t0 и t1. Итак, лучший путь - «-». Затем мы отменяем кодировку и получаем текст «». Кроме того, мы можем вычислить вероятность пути, умножив вероятности символов, которые в этом примере составляют 0,8 · 0,6 = 0,48.

Декодирование наилучшего пути выполняется быстро, нам нужно только найти символ с наивысшим баллом для каждого временного шага. Если у нас есть C символов и T временных шагов, время работы алгоритма будет O (T · C).

Почему декодирование наилучшего пути может потерпеть неудачу

Декодирование наилучшего пути одновременно быстрое и простое, что, конечно же, является хорошими качествами. Но он может не работать в определенных ситуациях, подобных показанной на рис. 2. На рис. 3 показаны все пути, соответствующие тексту «а»: «аа», «а-» и «-а». Вероятность появления текста «а» - это сумма всех вероятностей этих упомянутых путей: 0,2 · 0,4 + 0,2 · 0,6 + 0,8 · 0,4 = 0,52. Таким образом, «а» более вероятно, чем «» (0,52> 0,48). Нам нужен лучший алгоритм, чем декодирование наилучшего пути, который может справиться с такими ситуациями.

Базовая версия декодирования поиска луча

Декодирование поиска луча итеративно создает текстовые кандидаты (лучи) и оценивает их. Псевдокод для базовой версии показан на рис. 4. Список лучей инициализируется пустым лучом (строка 1) и соответствующей оценкой (2). Затем алгоритм выполняет итерацию по всем временным шагам выходной матрицы NN (3–15). На каждом временном шаге сохраняются только лучи с лучшими оценками из предыдущего временного шага (4). Ширина балки (BW) определяет количество балок, которые необходимо сохранить. Для каждого из этих лучей рассчитывается оценка на текущем временном шаге (8). Далее каждый луч расширяется всеми возможными символами алфавита (10) и снова вычисляется балл (11). После последнего временного шага в результате возвращается лучший луч (16).

Давайте визуализируем, как алгоритм декодирует наш пример вывода NN с помощью BW 2 и алфавита {«a», «b»}. На рис. 5 показаны как выход NN, который нужно декодировать, так и дерево лучей. Алгоритм начинается с пустого луча «», который соответствует корневому узлу дерева. Затем луч копируется и расширяется всеми возможными символами алфавита. Это дает нам лучи «a», «b» и «». Позже мы более подробно рассмотрим, как рассчитать баллы балки. На данный момент мы используем нашу интуицию и видим, что каждому лучу соответствует только один путь: «a» с вероятностью 0,2, «b» с 0 и «-» с 0,8.

В следующей итерации мы просто сохраняем 2 лучших луча (согласно BW) с предыдущего временного шага, то есть отбрасываем луч «b». Затем мы снова копируем и расширяем уцелевшие лучи и получаем «aa», «ab», «a», «a», «b», «». Если два луча равны, как в случае с «a», мы просто объединяем их: мы складываем баллы и оставляем только один из лучей. Мы снова используем нашу интуицию для подсчета очков. Каждый луч, содержащий букву «b», имеет вероятность 0. «aa» также имеет вероятность 0, потому что для кодирования текста с повторяющимися символами мы должны поместить пробел между ними (например, «a-a»), что невозможно. для пути длиной 2. Наконец, остались балки «а» и «». Мы уже рассчитали для них вероятности: 0,52 и 0,48.

Мы закончили последнюю итерацию, и последний шаг алгоритма - вернуть луч с наивысшим баллом, который в этом примере равен «а».

Забив балок

О том, как забивать балки, мы еще не говорили. Мы разделяем оценку луча на количество путей, заканчивающихся пробелом (например, «aa-»), и путей, заканчивающихся непустым (например, «aaa»). Обозначим вероятность того, что все пути заканчиваются пробелом и соответствуют лучу b на временном шаге t, через Pb (b, t) и через Pnb (b, t) для непустого случая. Вероятность Ptot (b, t) луча b на временном шаге t тогда является просто суммой Pb и Pnb, то есть Ptot (b, t) = Pb (b, t) + Pnb (b, t).

На рис. 6 показано, что происходит, когда мы удлиняем путь. Есть три основных случая: расширение пробелом, расширение повторением последнего символа и расширение другим символом. Когда мы сворачиваем расширенные пути, мы получаем либо неизмененный (скопированный) луч («a» → «a»), либо мы получаем расширенный луч («a» → «aa» или «ab»). Мы можем использовать эту информацию и с другой стороны: если мы расширяем луч, мы знаем, какие пути мы должны учитывать, чтобы рассчитать оценку.

Давайте посмотрим, как итеративно вычислять Pb и Pnb. Обратите внимание, что мы всегда добавляем вместо присвоения вычисленных значений (+ = вместо =), это неявно реализует объединение лучей, обсуждавшееся ранее. Все значения Pb и Pnb изначально установлены на 0.

Копировать луч

Чтобы скопировать луч, мы можем расширить соответствующие пути пробелом и получить пути, заканчивающиеся пробелом: Pb (b, t) + = Ptot (b, t-1) · mat (blank, t).

Кроме того, мы можем продлить пути, заканчивающиеся непустым последним символом (если луч не пустой): Pnb (b, t) + = Pnb (b, t-1) · mat (b [-1] , t), где -1 - индекс последнего символа в луче.

Расширить балку

Есть два случая. Либо мы удлиняем луч на символ c, отличный от последнего символа, тогда нет необходимости разделять пробелы в путях: Pnb (b + c, t) + = Ptot (b, t-1) · mat (c, т).

Или повторяется последний символ b [-1], тогда мы должны убедиться, что пути заканчиваются пробелом: Pnb (b + c, t) + = Pb (b, t-1) · mat (c, t).

Нам не нужно заботиться о Pb (b + c, t), потому что мы добавили непустой символ.

Языковая модель на уровне персонажей

Модель языка на уровне символов (LM) оценивает последовательность символов. Мы ограничиваем нашу LM оценкой одиночных символов (униграмма LM) и пар символов (биграмма LM). Обозначим вероятность униграммы символа c как P (c), а вероятность биграммы символов c1, c2 как P (c2 | c1). Оценка текста «привет» - это вероятность увидеть один «h» и вероятность увидеть пару «h» и «e» рядом друг с другом, а также пару «e» и «l» рядом с друг с другом, …

Вероятность символьной последовательности c1, c2, c3,… равна: P (c1, c2, c3,…) = P (c1) · P (c2 | c1) · P (c3 | c2) ·…

Обучить такую ​​LM из большого текста легко: мы просто подсчитываем, как часто встречается символ, и делим на общее количество символов, чтобы получить вероятность униграммы. И мы подсчитываем, как часто встречается пара символов, и нормализуем это, чтобы получить вероятность биграммы.

Собираем все вместе

Алгоритм поиска лучей CTC показан на рис. 7. Он аналогичен уже показанной базовой версии, но включает код для оценки лучей: скопированные лучи (строки 7–10) и расширенные лучи оцениваются (15–19). Кроме того, LM применяется при удлинении балки b с помощью символа c (строка 14). В случае односимвольного луча мы применяем оценку униграммы P (c), в то время как для более длинных лучей мы применяем оценку биграммы P (b [-1], c). Оценка LM для балки b помещается в переменную Ptxt (b). Когда алгоритм ищет лучи с лучшими оценками, он сортирует их в соответствии с Ptot · Ptxt (строка 4), а затем выбирает лучшие из BW.

Время выполнения может быть получено из псевдокода: самый внешний цикл имеет T итераций. На каждой итерации сортируются N лучей, что составляет N · log (N). Выбираются лучшие лучи BW, и каждый из них дополняется символами C. Следовательно, у нас есть N = BW · C балок, а общее время работы составляет O (T · BW · C · log (BW · C)).

Реализация

Реализацию Python для декодирования поиска луча (и других алгоритмов декодирования) можно найти в репозитории CTCDecoder: соответствующий код находится в src / BeamSearch.py ​​и src / LanguageModel.py. TensorFlow предоставляет операцию ctc_beam_search_decoder, однако не включает LM.

Оценка

Декодирование NN в наборе данных IAM дает коэффициент символьных ошибок 5,60% при декодировании наилучшего пути и 5,35% при декодировании поиска луча. Время работы увеличивается с 12 мс до 56 мс на образец.

Вот образец из набора данных IAM (см. Рис. 8), чтобы лучше понять, как поиск лучей улучшает результаты. Декодирование выполняется с помощью декодирования наилучшего пути и поиска луча с LM и без него.

Ground truth:        "the fake friend of the family, like the"
Best path decoding:  "the fak friend of the fomly hae tC"
Beam search:         "the fak friend of the fomcly hae tC"
Beam search with LM: "the fake friend of the family, lie th"

Заключение

Декодирование с поиском луча CTC - это простой и быстрый алгоритм, который превосходит декодирование наилучшего пути. LM уровня персонажа можно легко интегрировать.

использованная литература