Формула для корейского, или распознаем хангыль быстро, легко и без ошибок

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

    Но такое решение будет обладать рядом недостатков:

    Во-первых, большое количество необходимых вычислений, что влияет на время работы или требуемую энергию (что очень актуально для мобильных устройств). Действительно, если мы хотим распознавать хотя бы 3000 символов, то это будет размер последнего слоя сети. А если вход этого слоя равен хотя бы 512-ти, то получаем 512 * 3000 умножений. Многовато.

    Во-вторых, размер. Тот же самый последний слой из предыдущего примера будет весить 512 * 3001 * 4 байт, то есть около 6-ти мегабайт. Это только один слой, вся сеть будет весить десятки мегабайт. Понятно, для настольного компьютера это проблема небольшая, но на смартфоне не все будут готовы хранить столько данных для распознавания одного языка.

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

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

    И сегодня я расскажу, как нам удалось решить эти проблемы.

    Как устроена корейская письменность


    Корейская письменность, хангыль, является чем-то средним между китайским и европейским письмом. Внешне, это квадратные символы, напоминающие иероглифы, и на одной странице текста их можно насчитать больше сотни уникальных. С другой стороны, это фонетическая письменность, то есть основанная на записывании звуков. Имеется алфавит, содержащий 24 буквы (плюс можно дополнительно посчитать дифграфы и дифтонги). Но, в отличие от латиницы или кириллицы, звуки пишутся не в линию, а объединяются в блоки. Например, если бы мы писали так же, то фразу «Привет, Хабр» можно было бы записать тремя блоками примерно так:


    Каждый блок может состоять из двух, трёх или четырёх букв. При этом первой всегда идёт согласная, затем одна или две гласных, и в конце может стоять ещё одна согласная. Существует несколько разных способов объединения букв в блоки, то есть в разных блоках вторая буква, например, будет стоять в разных местах.

    На картинке ниже изображены два блока, которые вместе образуют слово «хангыль». Первая буква каждого блока обозначается красным, гласные выделены синим, а финальная согласная – зелёным.


    Источник изображения: Википедия.

    Модифицируем блок хангыля


    То есть получается, что один блок хангыля можно описать формулой: Ci V [V] [Cf], где Ci — начальная согласная (возможно, сдвоенная), V — гласная буква, а Cf — финальная согласная (тоже может быть сдвоенной). Такое представление неудобно для распознавания, поэтому изменим его.

    Во-первых, объединим обе гласные. Получим формулу Ci V' [Cf], где V’ — все возможные варианты объединения букв, считая отсутствие второй буквы. Поскольку в языке 10 гласных, можно было бы ожидать, что в результате получим 10 * (10 + 1) вариантов, но на практике не все они возможны, получается всего 21.

    Далее, последней буквы может не быть. Добавим в множество ожидаемых букв в конце пустую. Тогда получим формулу Ci V’ Cf*. Таким образом получается, что теперь корейский символ всегда состоит из трёх «букв». Можно учить сетку.

    Конструируем сеть


    Идея в том, что вместо распознавания символов целиком, мы будем распознавать отдельные буквы в них. Таким образом вместо одного огромного софтмакса в конце у нас получится три небольших, каждый размером примерно в несколько десятков. Они соответствуют первой, второй и третьей «буквам» в слоге. В итоге, у нас получилась такая архитектура:

    картинка кликабельная


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

    Решаем проблемы


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

    Сделаем то же самое, что сделали с третьей группой букв: добавим выход для отсутствия буквы. Тогда формула символа будет иметь такой вид: Ci* V’* Cf*. А в обучающую выборку добавим всякого мусора — китайских иероглифов, неправильно порезанных символов, европейских букв, и будем учить сеть отмечать на ней три пустые буквы.

    Обучаем, тестируем. Работает, но проблемы остались. Оказывается, достаточно часто в сетку попадают, например, такие изображения:


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

    Обучили. Плохо получается у такой сетки распознавать пунктуаторы: запятую от скобки она отличает, а вот от точки уже с трудом. Можно увеличить сложность сетки, но не хочется. Распознаванием пунктуаторов займёмся потом, а пока будем просто выдавать, есть там что-то или нет. Этому сетка научилась хорошо.

    С приклеенными пунктуаторами разобрались, но что делать, если наоборот, на изображении отсутствует часть ключа? Было такое вот слово из двух символов, но мы порезали его на символы неправильно:


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

    Для решения этой задачи воспользуемся тем, что осталось от каких-то старых экспериментов многолетней давности. Идея распознавать корейские символы по буквам появилась ещё очень давно, и первые попытки были сделаны ещё до эпохи нейросетей, но практического применения эти решения не нашли. Зато с тех пор осталась интересные вещи:

    1. Разметка того, где у каждого блока какая буква стоит.
    2. Качественная, пусть и небыстрая вырезалка этих букв из символов.

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

    Всё, с разпознаванием корейских символов проблем больше нет, но жизнь снова вставляет палки в колёса.

    Дело в том, что помимо символов хангыля корейские тексты состоят ещё из большого количества других символов: пунктуаторы, европейские символы (как минимум цифры) и китайские иероглифы. Но встречаются они, естественно, значительно реже. Разделим их на две группы: иероглифы и всё остальное, и обучим для каждой из них свою сетку. И сделаем простенький классификатор, который по результатам работы сети для распознавания корейских символов и по некоторым другим признакам (геометрическим, в первую очередь) будет отвечать, нужно ли хотя бы одну из них запускать, и если да, то какую. Европейских символов нужно распознавать немного, так что сетка будет маленькой, а для иероглифов… Спасает то, что в текстах они встречаются редко, поэтому закрутим наш классификатор так, чтобы он очень редко предлагал их распознавать.

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

    Проводим эксперименты


    Первый. Есть две базы изображений, условно назовём их Real и Synthetic. Real состоит из реальных изображений, которые получены из отсканированных документов, а Synthetic — изображения, полученные из шрифтов. В первой базе присутствуют изображения для 2374-х блоков (остальные очень редкие), а из шрифтов мы достали все возможные 11172 символа. Попробуем обучить сеть на тех блоках, которые есть в Real (сами изображения будем брать из обеих баз), а протестируем на тех, которые есть только в Synthetic. Результаты:

    image

    То есть, примерно в 60% случаев сеть способна распознать те блоки, примеры которых она вообще не видела при обучении. Качество могло бы быть и выше, если бы не одна проблема: среди финальных букв присутствуют очень редкие, и при обучении сеть увидела очень мало изображений блоков в ними. Этим и объясняется низкое качество в последнем столбце. Если бы можно было выбрать 2374 блока, на которых мы обучаемся, по-другому, то качество, скорее всего, было бы заметно выше.

    Второй. Сравним нашу сеть с «обычной» сетью, у которой в конце софтмакс. Хотелось бы сделать его размером 11172, но достаточное количество реальных изображений для редких блоков нам не найти, поэтому ограничимся 2374-мя. Качество и скорость работы этой сети зависят от размера скрытых слоёв. Учить будем только на Real, тестировать на ней же (на другой части, разумеется).

    image

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

    Третий. Предположим, что мы смогли где-то достать огромную базу всех 11172-х корейских блоков. Если мы на ней обучим сеть с софтмаксом, сколько она будет работать по времени? Все эксперименты проводить затратно, поэтому рассмотрим только сеть с размерами скрытых слоёв 256:

    image

    Получаем результаты





    Без них ничего бы не получилось


    Выражаю признательность моему коллеге Юре Чулинину, первоначальному автору идеи. Она запатентована в России, и, кроме того, аналогичная заявка подана в американское патентное ведомство (USPTO). Большое спасибо разработчику Мише Зацепину, который всё это реализовал и провёл все эксперименты.

    Юрий Ватлин,
    руководитель Complex Scripts group
    ABBYY
    167,00
    Решения для интеллектуальной обработки информации
    Поделиться публикацией

    Комментарии 18

      +6
      Спасибо, интересно. Но по поводу корейского есть несколько замечаний в качестве занудства:

      В корейском слоге всё же всегда одна гласная. То, что вы подразумеваете под двумя — дифтонги типа 왜. Такое правильнее считать одной буквой ㅙ, нежели двумя — ㅗ и ㅐ. Не уверена, что это сделает решение проще и лучше, но всё же.

      Сдвоенные согласные — ㅃ, ㅉ, ㄸ, ㄲ, ㅆ — это тоже отдельные буквы (не две ㅂ, а одна ㅃ).

      а Cf — финальная согласная (тоже может быть сдвоенной)
      Из сдвоенных в конце слога может стоять только ㄲ или ㅆ. Зато есть варианты с двумя буквами — ㅄ, ㄾ, ㄺ, ㄻ и т. п. (возможны не все сочетания). И это именно две разные буквы в конце слога, а не одна сдвоенная.
        0
        Я даже задумался, а надо ли вкладывать в системы распознования текста знание языковых норм? В том смысле что распознаваемый текст это не всегда человеческий язык, а иногда это может быть например маркировка, код продукта? Не сработает ли это знание в обратную сторону?
          +4
          «Знание языковых норм» это достаточно громко сказано. Просто особенности письменности. Корейские буквы всегда формируются в слоги, даже сходу не придумать, где бы могли использоваться оторванные от слога корейские буквы или невалидные слоги. Разве что эмодзи типа ㅜ_ㅜ.
          +1
          Из сдвоенных в конце слога может стоять только ㄲ или ㅆ. Зато есть варианты с двумя буквами — ㅄ, ㄾ, ㄺ, ㄻ и т. п. (возможны не все сочетания). И это именно две разные буквы в конце слога, а не одна сдвоенная.

          Собственно, на КДПВ именно такое сочетание двух разных согласных и замыкает первый слог под зайцем, мечтающим о морковке (굶주림).
          В свете этого — очень интересно, сможет ли запатентованный авторский алгоритм распознать текст на самой этой КДПВ, раз он ожидает в конце слога только сдвоенные согласные.
            +3
            Сеть знает про все возможные замыкающие буквы слога: одинарные, сдвоенные и диграфы, поэтому это слово распознаётся без ошибок. Более того, наш алгоритм способен распознать все 11172 символа, которые могут быть в корейском языке.
          +3
          Первое, что пришло в голову: если зайки нету — это не «хангыль», но все оказалось сложнее =)
            +1

            Интересно, что именно стало объектом патентования: анализ хангыля приемами для алфавитного письма? Если да, то патент ничтожен. Потому что хангыль – это фонематическое письмо, а не иероглифическое.

              +2

              В патенте у вас явная неточность:


              Базовым изображением в CJK* языках является иероглиф (т.е. стилизованное изображение символа, фразы, слова, буквы, слога, звука и т.д.)

              • CJK – Chinese Japanese Korean (прим. Rumkin)

              Базовым символом в корейском является не иероглиф, а слог. Патент явно прошел некачественную проверку специалистами.

                +4
                Проверка качественная, если я правильно понял, то патент покрывает
                РАСПОЗНАВАНИЕ СИМВОЛОВ С ИСПОЛЬЗОВАНИЕМ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА
                Т.е. вообще практически всё, что можно к этому свести :)
                  +3

                  В такой трактовке – да. Осталось запантентовать разбиение задачи на подзадачи, ограничение предметной области и другие методы оптимизации.


                  В США пытаются бороться с патентами вида "делать что-то с помощью компьютера". И даже успешно. Хотя процесс идет достаточно медленно, говорят, что из-за нового главы ведомства. Интересно, что будет в данном случае.

                    +4
                    Поскольку ABBYY уже имеет опыт работы с патентными троллями, например www.abbyy.com/en-eu/news/abbyy-wins-patent-infringement-lawsuit-against-nuance/#sthash.YVhaHwpb.dpbs, лучше перебдеть с патентами чем недобдеть :)
                      +3

                      Согласен, что от патентных троллей лучше защищаться заранее. Но, во-первых, какова цель упоминания патента в статье? А, во-вторых, делаешь защитный патент – переводи в общественное достояние (public property), незачем ограничивать других разработчиков своим патентом, если настоящая цель – защита.

              0
              В корейском алфавите 19 гласных (включая дифтонги) и 19 согласных. Все «иероглифы» — это комбинации этих букв по правилам корейского языка. Например, один слог («иероглиф») не может содержать подряд две гласных на первой или второй позиции, количество букв в слоге — от 2 до 5 с ограничением по сочетаниям даже согласных с гласными.

              Поэтому когда вы написали про 3000 иероглфов, сложилось впечатление, что вы перепутали с китайским. Все корейские слоги (единицы записи) — из ограниченного набора. Кстати, они все перечислены в кодировке.
                +3
                Я нигде не писал про 3000 иероглифов, только про 3000 символов. В это множество могут входить блоки хангыля, европейские символы или китайские иероглифы, в зависимости от задачи.
                  –2
                  набор китайских иероглифов, который является корейской письменностью («ханча») тоже очень ограничен — и это по сути тоже алфавит, бОльший по разнообразию, но используемый исключительно для звуковой записи корейских слов (вроде транслита).

                  Что же касается _всех_ символов, составляющих сообщение в Корее (не обязательно корейский язык) — то он конечно включает почти все, что может быть написано, как числа, китайские и латинские слова, эмоджи, знаки препинания… Но это уже отдельная задача, слабо связанная с распознаванием хангыля :)
                    +3
                    используемый исключительно для звуковой записи корейских слов (вроде транслита)
                    Принцип записи слов с помощью ханча на транслит совсем не похож.

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

                      Просто фраза «проблема в количестве символов: 3000, скорее всего, хватит чтобы, например, отличить в меню ресторана стейк от жареного морского огурца, но порой встречаются и более сложные тексты» показала, что автор, кажется, не понимает самого принципа алфавитной записи. Либо понимаешь ВЕСЬ алфавит и можешь прочитать (прочитать != понять) текст любой сложности, либо знаешь НЕ ВЕСЬ алфавит и не можешь прочитать почти ничего (кроме слов, не содержащих неизвестную тебе букву)
                0
                промахнулся веткой, del

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

                Самое читаемое