Skip to content

Latest commit

 

History

History
904 lines (680 loc) · 40.5 KB

README.md

File metadata and controls

904 lines (680 loc) · 40.5 KB
Raw

Продвинутые задачи и модели NLP. Морфология

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

Структура курса

Будут рассмотрены state-of-the-art решения для следующих задач:

Основные понятия

Морфология - раздел грамматики, основными объектами которого являются слова естественных языков, их значимые части и морфологические признаки.

Морфология изучает:

  • Словоизменение
  • Словообразование
  • Части речи
  • Грамматические значения

Грамматическое значение

Значение, выражаемое словоизменительной морфемой

Морфема - наименьшая единица языка, имеющая некоторый смысл.

Морфемы подразделяются на два основных типа - корневые и аффиксальные

Корень - основная значимая часть слова.

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

Типы аффиксов

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

Граммемы и грамматические категории

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

Примеры грамматических категорий

  • Именные: падеж, род, определенность, одушевленность, личность
  • Глагольные: время, вид, лицо, наклонение, залог
  • "Оба" - число

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

Примеры граммем:

  • Единственное и множественное число
  • Мужской, женский и средний род
  • Именительный, родительный и т.д. падежи

Следовательно грамматическое значение - набор граммем всех категорий, характерных для данной части речи. Например, для “ежа”: существительное, одушевлённое, мужской род, единственное число, родительный падеж.

Грамматическое и лексическое значение

  • Грамматические значения образуют замкнутый более структурируемый класс.
  • Грамматические значения выражаются в принудительном порядке. (У существительно всегда есть категории числа, рода, падежа)
  • Лексические и грамматические значения отличаются с точки зрения способов и средств их формального выражения. (Грамматические значения выражаются с помощью реляционных морфем)
  • Грамматические значения могут не иметь полного соответствия во внеязыковой сфере. (род существительных табуретка и стул мотивированы их окончаниями)

Характерные размеры грамматических систем

Для одного языка:

  • ~30 грамматических категорий
  • До 90 граммем на категорию
  • В среднем 4-5 граммем на категорию

Для одной части речи:

  • В среднем до 4 грамматических категорий
  • До 20 грамматических категорий

Глоссарий

  • Вокабула:
    • Заголовок словарной статьи;
    • Слово иностранного языка с переводом на родной язык;
    • Графическое слово
  • Лемма - нормальная (словарная) форма слова. Для русского языка характерно:
    • для существительных - именительный падеж, единственное число
    • для прилагательных - именительные падеж, единственное число, мужской род
    • для глаголов, причастий и деепричастий - глагол в инфинитиве несовершенного вида
  • Словоформа - слово с определенной леммой и грамматическим значением. "Ворон" и "(к) ворону" - разные словофромы одной лексемы.
  • Лексема - набор всех словоформ слова. Т.е. "Ворон", "(к) ворону", "вороном", "(о) вороне", "вороны" и т.д.

Словоизменительная парадигма

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

Ед. ч. Мн. ч
И рука руки
Р руки рук
Д руке рукам
В руку руки
Т рукой руками
П руке руках
Ед. ч. Мн. ч
И тубус тубусы
Р тубуса тубусов
Д тубусу тубусам
В тубус тубусы
Т тубусом тубусами
П тубусе тубусах
читать тонуть
читала тонула
читая ?
читаемый ?
читанный ?

Парадигма определяет:

  • неизменяемое, классифицирующее грамматическое значение лексемы;
  • какие есть формы у лексемы;
  • как записываются формы лексемы.

Словообразовательная парадигма

Совокупность производных слов (дериватов) от одной основы.

  • у образованных слов своё словоизменение
  • лексемы с одинаковым словоизменением могут по-разному образовывать дериваты
слон слоник слонёнок
краб крабик крабёнок
Алёна Алёночка Алёнушка
Лена Леночка Ленушка

Классификация словоизменения

1. Изолирующие (аморфные, односложные, корневые) языки

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

Изолирующие языки распространены в Юго-Восточной Азии:

  • Вьетнамский язык
  • Классический китайский язык
  • Бирманский язык
  • Тайский язык
  • Кхмерский язык в Камбодже
  • Лаосский язык

2. Аналитические языки

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

3. Синтетические языки

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

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

4. Флективные языки

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

  • стел-ю (НВ+ЕЧ)
  • стел-ила (ПВ+ЕЧ+ЖР)
  • стел-ись (ЕЧ+Повелит)
  • стел-ющийся (Прич+НВ+ЕЧ+МР)
  • стел-ясь (Дееприч+НВ)

5. Аглютитативные языки

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

Пример (турецкий): ev(дом) + ler(МнЧ) + im(выражаает принадлежность 1Л, ЕЧ) + de(местный падеж) = evlerimde (В моих домах); evimde(В моём доме); evlerde(В домах)

Дополнительно

Аблаут (чередование гласных)

"Внутрення флексия": соб-рать - соберу - собираю

Морфема внутри корня, разрывная мофрология

Арабский язык:

  • k t b "писать" (корень)
    • +-a-a- Прош.Вр., Акт.залог (огласовки)
    • +-a 3л, Ед.ч, МР (суффикс (окончание))
    • =kataba "написал"
  • k tt b Интенсив ~«много писать» (корень)
    • +-u-i- Прош.Вр., Пассив.залог (огласовки)
    • +tu-____-u 3л, Ед.ч, ЖР., Имперф, пассив (префикс, суффикс)
    • =tukuttibu "(её) много писали"

Задачи компьютерной морфологии

  • Спеллинг - проверка слова по словарю
  • Морфологический анализ - определение грамматического значения и леммы у словоформы
  • Морфологический синтез - построение словоформы по лемме и грамматическому значению
  • Исправление опечаток - поиск наиболее близкого слова в слоаваре

Далее подробно о каждой задаче и способах её решения.

Морфологический анализ

Морфологический анализ в лингвистике — определение морфологических характеристик слова.

Задача морфологического анализа

  • Получение леммы
  • Получение грамматического значения

Существуют уже готовые морфологические анализаторы, которые справляются с этой задачей. Например, MyStem и pymorphy. Чтобы поближе с ними познакомиться, предлагается изучить morph_analyzers.ipynb

Как было показано в ноутбуке - данные анализаторы имеют свои недостатки, т.к. сильно опираются на словарь. Ралее рассмотрим нейросетевые подходы к решению подобной задачи, ограничившись только определением частей речи у слов. Данную задачу еще называют Part-of-speech tagging.

POS-tagging

Данная задача относится к типу Sequence labeling, т.е. каждому элементу последовательности (В нашем случае слова в тексте) нужно сопоставить некоторый тэг, класс (часть речи).

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

Далее мы рассмотрим решение этой же задачи, но уже на чистом pytorch.

PyTorch pipeline

Для решения большинства NLP задач на чистом торче обычно нужны следующие компоненты:

  • Словарь - хранит отображение строковых значений, например слов, в индексы.
  • Датасет - представляет собой контейнер для данных, возвращающий тензор данных по индексу или по батчу. В торче уже есть базовый класс, от которого можно отнаследоваться и пользоваться торчевыми итераторами.
  • Ридер - читает данные из файлов и возвращает список объектов (инстансов). Иногда эту роль может выполнять датасет, но тогда могут возникнуть проблемы с индексацией.
  • Индексер - строит словарь (или словари) по датасету. Опять же, если например, нам нужны только токены, то словарь можно инициализировать эмбеддингами.
  • Модель - собственно сама модель нейросети. Принимает тензоры, возвращает тензоры. Не стоит в модель пихать еще функцию ошибки.
  • Тренер - учит модель, проходя по датасету. Тут все стандартно
  • Система - обертка над моделью, которая считает лосс и метрики, декодирует и прочее.
  • Утилиты - различные функции для упрощения жизни, например, загрузка эмбеддингов, выравнивание тензоров и метрики.

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

В качестве примера приглашаю в скрипт pos_torch.py

AllenNLP

К счастью, писать каждый раз столько кода не нужно. От задачи к задаче многие сущности повторяются: словарь, индексер, тренер, утилиты и обертки. Даже больше: все это уже реализовано за нас, например в AllenNLP.

В этом фреймворке есть следующие сущности:

  • DatasetReader - читает датасет и возвращает список инстансов Instance- контейнеров для входных и выходных данных. По сути это отображение строк в поля Field, которые представляют собой данные и умеют возвращать тензор.
  • Vocabulary - словарь, хранящий отображения полей в индексы. Удобен различными способами инициализации: из инстансов или из файлов.
  • Model - в предудущих понятиях это система - считает лосси метрики, прогоняет сеть и декодирует. В методе forward возвращает Dict[str, torch.Tensot], в который обычно кладут лосс, логиты или пути, если мы используем CRF. Метод decode вызывается после forward и модифицирует Dict, например возвращая лэйблы.
  • Trainer - хорошо настареваемый тренер, которому можно указаьб кол-во эпох, валидационную метрику, по которой выбирать лучшую модель, и прочее.

Ну а теперь давайте посмотрим, насколько AllenNLP прекрасен: pos_allennlp.ipynb

AllenNLP JSON

Вы думали это все? Нет, на allennlp можно писать в JSON. Запуск примера:

allennlp train pos_config.json -s <путь до папки с результатом> --include-package src_allennlp
Бонус

Flair embeddings

Теперь разберем один из SOTA примеров: Flair embeddings. Данный подход позволяет генерировать контекстуальные "строковые" эмбеддинги.

Суть довольно проста: мы представляем текст как последовательность символов и эмбеддер (BiRNN) возвращает векторные представления для них. Эмбеддинги для каждого слов берутся как конкатенация эмбеддингов последнего символа слова при прямом проходе и первого - при обратном.

Энкодер здесь представляет собой BiLSTM-CRF.

Akbik A., Blythe D., Vollgraf R. Contextual string embeddings for sequence labeling //Proceedings of the 27th International Conference on Computational Linguistics. – 2018. – С. 1638-1649.

Исправление ошибок

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

  • Поиск ошибок (Spelling) - нахождение слов, в которых возможны опечатки. Самое простое решение - проверка наличия такого слова в словаре.
  • Собственно исправление слов или предложение вариантов исправления, например, с помощью поиском ближайших слов (по edit distance) в словаре.

Зачем всё это нужно:

  • Проверка орфографии в текстовых редакторах
  • Подсказки при наборе текста
  • Поиск. Коррекция запросов
  • Распознавание текста и речи

Типы ошибок в словах

  • Опечатки (случайный набор неверного символа):
    • Матрос -> Мартос; Матрос -> Матрас; userinfo -> user info
  • Орфографические ошибки:
    • Ошибки при записи речи на слух
    • Транслитерационные ошибки (в иноязычных словах/именах собственных)
    • Когнитивные ошибки (смешение понятий)
    • матрос -> мотрос; бодаться -> бадаться; предать -> придать
  • Ошибки распознавания:
    • layer -> 1ayer; Щупальца -> Шупальца; Макушка -> Манушка

Способы решения

Сперва рассмотрим способы решения спеллинга. Самый простой способ - поиск в словаре: для каждого слова в тексте проверяем его наличие в словаре. Однако, довольно сложно создать словарь, в котором будут все возможные слова и их формы (Имена собственные, заимствоания). Поэтому есть чуть более универсальные способы.

N-граммы

По сути это кортежи размерности N чего-угодно: символов, слов, предложений, частей речи и пр. Примеры:

  • Символьные триграммы: матрос -> ##a, #ма, мат, атр, тро, рос, ос#, c##
  • Словные биграммы: Мама мыла раму -> [BOS] Мама, мама мыла, мыла раму, раму [EOS]
  • Биграмы признаков, например, POS-тэги: Мама мыла -> OUT NOUN, NOUN VERB, VERB OUT

Как их можно использовать для спеллинга:

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

Устройство словаря

Далее рассмотрим как строить словарь и как его использовать для решения поставленной задачи.

  • Самый простой способ - линейный список, но его минусы очевидны: линейный поиск, ну или логарифм, если список отсортирован. Слов в языке: 100-200к, у каждого с десяток форм. Уже получается довольно долго.
  • Бинарное дерево поиска - не сильно лучше отсортированного массива + бин поиск
  • Хеш-таблица - уже лучше. Поиск - амортизированная константа. Но остаётся проблема с размером:
200 000 слов * 15 форм на слово * 9 символов в слове * 2 байта на символ = 50 Мб
  • Бор или префиксное дерево: вершины - символы слов, терминальные вершины - слова. Плюс такой структуры в быстром поиске( О(длина слова) ) и очень маленьком размере( О(максимальная длина слова * мощность алфавита) ). Также эта структура удобна для поиска ближайших слов, но об этом позже. Далее пример.

Входной словарь: кот, кошка, кит, пёс. Представление бором:

graph LR
    A1((#))-->B1((К))
    A1-->B2((П))
    B1-->C1((О))
    B1-->C2((И))
    B2-->C3((Ё))
    C1-->D1((T)):::red
    C1-->D2((Ш))
    C2-->D3((Т)):::red
    C3-->D4((С)):::red
    D2-->E1((К))
    E1-->F1((А)):::red
    classDef red fill:#f00;

В GitHub mermaid не работает, поэтому смотрим локально.

Особенности задачи

  • Чаще всего ошибки локальны (затрагивают один-два символа)
  • Может влиять и более широкий контекст: ться -> цца, ant -> ent
  • Исправление опечаток требует поиска близких слов в словаре

Одной из оценок близости между двумя строками является расстояние Левенштейна (или же edit distance) - минимальное число замен, вставок и удалений, необходимых, чтобы из одной строки получить другую

Рассояние Левенштейна симметрично, неотрицательно и удовлетворяет неравенству:

Итак, как с помощью расстояния Левенштейна найти ближайшее слово к данному:

  • Перебрать весь словарь, сравнивания слова с данныи - очень долго!
  • Генерируем строки, которые можно получить из данной за одну или две ошибки, ищем в словаре - уже чуть лучше, не порождаем заведомо далекие гипотезы.
  • Делаем это с помощью бора: спускаемся по нему и считаем кол-во замен, когда идем по вершине, не соответсвующую данному слову. Если на какой-то ветви ошибком много - отсекаем.

При этом как выбрать кандидатов для исправления с одинаковым количеством исправлений? Для разных задач различные исправления имеют разный вес:

  • Опечатки: близкие символы на клавиатуре и обмен символов внутри слова должны иметь больший вес
  • Орфографические ошибки: гласные не меняются на согласные, мягкий знак в конце слова, типичные случаи "f" -> "ph", "цца" -> "тся"
  • Ошибки распознавания: замены похожих символов графически Ну и, конечно, веса замен можно обучать, например, на истории изменении Википедии.

Проблемы

Даже имея большой словарь, мы не застрахованы от ложных срабатываний, например, на редких терминах и именах собственных: Эллочка -> Ёлочка

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

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

Donaudampfschiffahrtselektrizit?tenhauptbetriebswerkbauunterbeamtengesellschaft

Перевод: Общество служащих младшего звена органа по надзору за строительством при главном управлении электрического обслуживания дунайского пароходства

Ну а теперь предлагается на пройденном материале решить задачу исправлени опечаток в spelling.ipynb

Grammatical Error Correction

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

Задача GEC обычно формулируется как задача исправления предложения. Т.е. система GEC на вход принимает предложение с потенциальным ошибками и должа вернуть исправленное предложение. Пример:

Input: She see Tom is catched by policeman in park at last night.

Output: She saw Tom caught by a policeman in the park last night.

Датасеты обычно включают в себя предложения или параграфы, а также указания ошибок со спанами в тексте, типом ошибки и как нужно исправить:

...I have just recieved the letter, which lets me know that I have won the first prize. I am proud of winning it and would like to say how thankful I am...
"edits": [71, 79, "received", "S"], [195, 203, "grateful", "RJ"]
S – spelling error
R - word or phrase needs Replacing
J - AdJective

Способы решения

Эту задачу обычно решают как задачу машинного перевода (SMT - statistical machine translation). А одним из основных способов решения задачи SMT является seq2seq with attention. Т.е. входная последовательность токенов кодируется в энкодере, а затем декодер декодирует её в новую последовательность, обращая внимание только на определенные входные токены при генерации очередного выходного токена.

Этот подход для решения задачи GEC описан в статье "A Multilayer Convolutional Encoder-Decoder Neural Network for Grammatical Error Correction". Концептуально, здесь обычный seq2seq с механизмом внимания, только архитектуры энкодера и декодера весьма специфичны. Они осонованы на нескольких слоях сверткок и GLU (Gated Linear Unit), в то время как обычно в seq2seq используются рекуррентые сети.

Другой подход, который сейчас является SOTA на английском, основан не на seq2seq, а на sequence labelling, как мы смотрети в POS-tagging. Только тэги здесь - это одно из 5000 специфических правил замены, удаления, добавления или сохранения. Для этого был построен огромный словарь форм глаголов, а одни из тэгов означают "Заменить форму глагола на такую". Сама архитектура - просто энкодер берта с парой линейныйх слоёв и softmax. Более подробно подход описан в статье "GECToR – Grammatical Error Correction: Tag, Not Rewrite"

Мофрологический синтез

Наконец рассмотрим последнюю задачу мофрологии - морфологический синтез. Концептуально задача состоит в следующем: имея начальную форму и грамматическое значение, поставить слово в соответсвующую форму. Например, нужно поставить существительное на английском в множественное число:

cat + N + Pl -> cats
torch + N + Pl -> torches
ally + N + Pl -> allies
goose + N + Pl -> geese
formula + N + Pl -> formulae / formulas

Как видно из примеров, даже самая простая задача как получение у существительного множественного числа имеет множество случаев, а не только добавление "s" в конец слова. Что говорить о языках с более сложной морфологией, например о русском. Однако эту задачу в некоторой степени можно решить с помощью регулярных выражений (хотя естественный язык нерегулярный, некоторые механизмы можно подогнать под формальные языки)

Регулярные выражения

Вспомним немного теорию формальных языков.

  • Пусть $\Sigma$ - некоторый конечный алфавит
  • $\Sigma^*$ - множество всевозможных слов над алфавитом
  • Язык $L$ - некоторое подмножество $\Sigma^$: $L \subset \Sigma^$
  • $\epsilon$ - пустое слово
  • Операция конкатенаци $\cdot$ : $u \cdot v = uv; u,v \in L$
  • Конкатенация языков: $L_1 \cdot L_2 = { u \cdot v| u \in L_1, v \in L_2 }$
  • Степень: $L^k = {\prod\limits_{i=1}^k u_i | u_i \in L, i =[1,k]}, L^0 = {\epsilon}$
  • $L^*=\bigcup\limits_{k=0}^{\infty}L^k$

Регулярные выражения определяются по индукции:

  • Зафиксируем алфавит $\Sigma$
  • Пусть $\alpha$ - регулярное выражение, тогда $L(\alpha)$ - язык, порождаемый $\alpha$
  • Если $a \in \Sigma$, то $a$ - регулярное выражение; $L(a) = {a}$
  • Если $\alpha,\beta$ - регулярные выражения, то $(\alpha + \beta)$ - тоже; $L(\alpha + \beta)=L(\alpha) \cup L(\beta)$
  • Если $\alpha,\beta$ - регулярные выражения, то $(\alpha \cdot \beta)$ - тоже; $L(\alpha \cdot \beta)=L(\alpha) \cdot L(\beta)$
  • Если $\alpha$ - регулярное выражение, то $(\alpha^)$ - тоже; $L(\alpha^)=L(\alpha)^*$

Определение: язык называется регулярным, если он задаётся некоторым регулярным выражением.
Примеры $\Sigma={a,b}$:

  • $\alpha = (a+b)(a+b)$, $L(\alpha)$ - все слова их двух символов
  • $\alpha = b^*ab^ab^$, $L(\alpha)$ - слова с двумя $a$

Конечный автомат

Конечным автоматом называют кортеж $M=&lt;Q,\Sigma, \Delta, q_o, F&gt;$, где

  • $\Sigma$ - конечный алфавит.
  • $Q$ - конечное множество состояний
  • $\Delta \subseteq Q \times (\Sigma \cup {\epsilon}) \times Q$ - множество преходов: начальное состояние, по каком символу производится переход, конечное состояние.
  • $q_0 \in Q$ - начальное состояние
  • $F \subseteq Q$ - завершающие состояния

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

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

Свойства автоматных языков

Теорема. Любой автоматный язык распознаётся автоматом без $\epsilon$-переходов.

Определение. Автомат без $\epsilon$-переходов называют детерминированным, если ни из какого сотояния нет двух переходов по одной метке.

Теорема. Любой автоматный язык распознаётся детерминированным конечным автоматом.

Теорема (Клини) Классы автоматных и регулярных языков совпадают.

Посторим автоматы для резулярных выражений из примеров:

  • $(a+b)(a+b)$
graph LR
    A((q0))--a,b-->B((q1))
    B--a,b-->C((q2)):::red
    classDef red fill:#f00;
  • $b^*ab^ab^$
graph LR
    A((q0))--a-->B((q1))
    A--b-->A
    B--a-->C((q2)):::red
    B--b-->B
    C--b-->C
    classDef red fill:#f00;

Конечный преобразователь

Конечным преобразователем называют кортеж $M=&lt;Q,\Sigma, \Gamma, \Delta, q_o, F&gt;$, где

  • $\Sigma$ - конечный входной алфавит.
  • $\Gamma$ - конечный выходной алфавит.
  • $Q$ - конечное множество состояний
  • $\Delta \subseteq Q \times (\Sigma \cup {\epsilon}) \times (\Gamma \cup {\epsilon}) \times Q$ - множество преходов: начальное состояние, по каком символу производится переход, на какой символ происходит замена, конечное состояние.
  • $q_0 \in Q$ - начальное состояние
  • $F \subseteq Q$ - завершающие состояния

Конечный преобразователь распознаёт пары слов $<u,v> \in \Sigma^* \times \Gamma^$, которые являются метками путей в графе, и задаёт многозначное отображение из $\Sigma^$ в $\Gamma^*$

Конечные преобразователи замкнуты относительно:

  • Конкатенации
  • Объединения
  • Композиции
  • Приоритетного объединения $\cup_p$: $(T_1 \cup_p T_2)(u) = \begin{cases} T_1(u), & T_1(u) \ne \varnothing \ T_2(u), & иначе \end{cases}$
  • Обращения $T^{-1} = {&lt;x,y&gt;|&lt;y,x&gt; \in T}$

Контекстные замены

С помощью конечный преобразователей можно задавать контекстные замены $X\to Y || U _ V$. Например, меняем $a$ на $b$ только между $c$ и $d$: $a\to b || c _ d, (\Sigma = \Gamma = {a,b,c,d})$

graph LR
    A((q0)):::red--c:c-->B((q1)):::red
    A--a:a,b:b,d:d-->A
    B--b:b,d:d-->A
    B--c:c-->B
    B--a:b-->C((q2))
    B--a:a-->D((q3))
    C--d:d-->A
    D--a:a,b:b-->A
    D--c:c-->B    
    classDef red fill:#f00;

Использование конечного преобразователя

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

  • Входной алфавит $\Sigma={a-z, +N, +Sg, +Pl}$
  • Выходной алфавит $\Gamma={a-z}$

Итоговый преобразователь будет состоять из нескольких:

  • $T_s$ - вставляем "s" и специальную метку "@" перед "s":
    • +N+Sg -> @ || _#; (# - конец строки)
    • +N+Pl -> @s || _#
  • $T_y$ - меняем "y" на "ie" после согласных для множественного числа:
    • y -> ie || C_@s#; (C-согласный)
  • $T_{sib}$ - вставляем дополнительную "e" после шипящих:
    • $\epsilon$ -> e || [s,z,x,ch,sh]_@s#
  • $T_{cl}$ - очистка от служебных символов
    • @ -> $\epsilon$ || _
  • $T_{exc}$ - для исключений

Фрагмент $T_{exc}$ (некоторые состояния были сплющены для простоты, $\epsilon$ здесь - "_")

graph LR
    A((q0))--formula-->B((q1))
    A--m-->C((q2)) 
    C--"ouse"-->D((q3))
    D--"+N+Sg:_"-->E((q4)):::red
    C--"ou:i"-->F((q5))
    F--"s:c"-->G((q6))
    G--e-->H((q7))
    H--"+N+Pl:_"-->I((q8)):::red
    B--"+N:_"-->J((q9))
    J--"+Sg:_"-->L((q10)):::red
    J--"+Pl:e"-->M((q11)):::red
    J--"+Pl:s"-->N((q12)):::red
    classDef red fill:#f00;

Итоговый преобразователь $T=T_{exc} \cup_p (T_s \circ T_y \circ T_{sib} \circ T_{cl})$

Арабская морфология

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

  • k t b - "писать"
  • +-a-a- Прош.Вр., Акт.залог (огласовки)
  • +-a 3л, Ед.ч, МР (суффикс (окончание))
  • = kataba "(он) писал"

Аналогично предыдущей задаче зададим вход:

  • вход: основа +Type +Voice +Aspect +Person +Gender
  • Type $\in$ { I, II } - порода (базовая или интенсив)
  • Voice $\in$ {Act, Pass} - залог
  • Aspect $\in$ {Perf, Imperf} - вид
  • Person $\in$ {3} - лицо
  • Gender $\in$ {M, F} - род

Примеры:

  • ktb+I+Act+Perf+3+M -> kataba
  • ktb+II+Pass+Imperf+3+F -> tukattabu
  • zhr+I+Act+Imperf+3+M -> yazharu
  • sfr+I+Act+Imperf+3+F -> tasfiru
  • mrd+II+Pass+Perf+3+M -> murrida
  • hsn+I+Act+Perf+3+F -> hasunat

Модель словообразования

Приведем небольшую часть таблиц морфем для понимания построения примеров:

  • Порода: в интенсиве только вторая согласная дублируется.
  • Род и лицо:
Форма Окончание перфекта Префикс и окончание имперфекта
3M -a ya- -u
3F -at ta- -u
  • Парадигмы
Класс Огласовка перфекта Огласовка имперфекта Пример
1 a-a $\varnothing$-a zahara – «сиять»
2 a-a $\varnothing$-u kataba – «писать»
3 a-a $\varnothing$-i safara - «отправляться в путь»
4 a-i $\varnothing$-a marida – «быть больным»
5 a-u $\varnothing$-u hasuna – «быть красивым»

Преобразователь для арабской морфологии

  • Input - проверка корректности и вставка метки класса
  • PosInsertion - вставка маркеров позиций
  • Fill - заполнение огласовок (порода, вид, залог, класс),
  • Prefix - вставка префиксов (вид, залог, лицо, род)
  • Suffix - вставка суффиксов (вид, лицо, род)
  • Cleanup - очистка меток
  • Общий преобразователь: Input ? PosInsertion ? Fill ? Prefix ? Suffix ? Cleanup

Пример: sfr+I+Act+Imperf+3+F

  • Input: C3^sfr+I+Act+Imperf+3+F
  • PosInsertion: C3^0s1f2r3+I+Act+Imperf+3+F
  • Fill: C3^0sfir3+I+Act+Imperf+3+F
  • Prefix: C3^tasfir3+I+Act+Imperf+3+F
  • Suffix: C3^tasfiru+I+Act+Imperf+3+F
  • Cleanup: tasfiru

Компиляторы для конечных преобразователей

  • XFST (Xerox Finite-state toolkit)
  • HFST (Helsinki Finite-state toolkit)
  • FOMA
  • SFST (Stuttgart finite-state toolkit)
  • OpenFST

Более подробно предлагается ознакомиться с FOMA и выполнить пару заданий из foma.md

Лемматизация

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

graph LR
    A1((#))-->A2((К))    
    A2-->A3((О))
    A3-->A4((T)):::red
    A4-->B1((Ы)):::red
    A4-->B2((A)):::red
    A4-->B3((У)):::red
    A4-->B4((О))
    B4-->B5((M)):::red
    A4-->C1((И))
    C1-->C2((К)):::red
    C2-->C3((A))
    C2-->C4((У))
    C2-->C5((О))
    C5-->C6((М)):::red
    B1-.->A4
    B2-.->A4
    B3-.->A4
    B5-.->A4
    classDef red fill:#f00;

Словарь парадигм

Предыдущее представление имеет несколько недостатков:

  • Глубина словаря
  • Объем словаря
  • Неэфективность получения всех форм слова

Другим способом хранения словаря с формами - это отдельные словари для основ и парадигм.

graph LR
    A1((#))-->A2((К))    
    A2-->A3((О))
    A3-->A4((T)):::red  
    A2-->A5((И))
    A5-->A6((Т)):::red  
    classDef red fill:#f00;   


graph RL
    A1((#)):::red-->A2((A)):::red    
    A1-->A3((У)):::red
    A3-->A4((T)):::red    
    A1-->A5((M))
    A5-->A6((О)):::red
    classDef red fill:#f00;

При этом при поиске основы проходим слева направо, а для оконачания - справа налево: КОТОМ

Проблемы

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

  • Композиты: паровозостроение, Петропавловск-Камчатский. г.Москва
    • Можно пытаться решать с помощью итеративного разбиения на части и проверки в словаре и с помощью правил, например, две основы начинаются с загловной буквы и разделены с помощью "-"
  • Незнакомые слова - пытаемся подогнать парадигму под какое-нибудь знакомое слово. Пример: заддосить:
    • Выделяются всевозможные окончания:
      • заддосить(пустое, как у "резюме")
      • заддосить(как в "февраль")
      • заддосить(как в "закосить")
    • Подбирается набор парадигм, которые могут иметь подобные окончания
    • Пары (парадигма, окончание) сортируются с использованием N-граммной статистики
    • Оцениваем сомвестную вероятность, что у слова такая парадигма, такой суффикс и такая форма, и выбираем парадигму(и форму) с наибольшей вероятностью
  • Омонимия: Эти виды стали у многих стали пользоваться популярностью.
    • В рамках одного слова эту задачу не решить, но мы уже умеем в pos-tagging, так что с помощью него получаем часть речи и используем соответсвующую парадигму.

Далее все-таки посмотрим, как задача лемматизации решается в готовых системах

MyStem

Описание работы тут. Данный морфологический анализатор расчитан на максимальное быстродействие для использования в поисковом движке. Поэтому о каких-то серьёзных использованиях контекста речи не идет.

Словарь здесь представлен как бор инвертированных основ и дерево всевозможных суффиксов. Сам алгоритм поиска выглядит следующим образом:

  1. Слово обрабатывается справа налево, и спускаясь по дереву суффиксов получаем всевозможные точки деления основы и суффикса.
  2. Далее начиная с самой глубокой точки деления пытаемся найти словарное слово изменяя последние две буквы основы
  3. Если словарное слово находится, то возвращаем его
  4. Иначе повторяем шаг 2 запоминая точки ветвления, и их ищем среди кандидатов возможную модель слова

Также в алгоритм были встроены дополнительные эвристики:

  • полученная основа должна содержать гласную
  • основа у модель должна иметь часть речи
  • должна существовать минимальная длина основы
  • должна существовать минимальная общая часть примера и неизвестного слова
  • парадигма модели должна встретиться хотябы дважды в словаре

Segalovich I. A fast morphological algorithm with unknown word guessing induced by a dictionary for a web search engine //MLMTA. – 2003. – С. 273-280.

Edit trees

Достаточно распространенным какое-то время был подход, основанный на деревьях замен (edit trees). Ниже можно увидеть пример такого дерева:

Задача лемматизации в этом случае сводится к следующему:

  • По обучающему корпусу построить edit trees
  • Свести задачу к sequence tagging, где классы - различные деревья замен.

Примеры такого подхода можно пожно почитать тут и тут

M?ller T. et al. Joint lemmatization and morphological tagging with lemming //Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing. – 2015. – С. 2268-2274.

Chakrabarty A., Pandit O. A., Garain U. Context sensitive lemmatization using two successive bidirectional gated recurrent networks //Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). – 2017. – С. 1481-1491.

Seq2Seq

Ну и, наконец, рассмотрим seq2seq подходы. В качестве примера рассмотриму эту статью. На вход модели подаются символы слова, за которыми следуют специальный символы морфологических тэгов, полученных при предварительном анализе.

Kanerva J., Ginter F., Salakoski T. Universal Lemmatizer: A sequence-to-sequence model for lemmatizing Universal Dependencies treebanks //Natural Language Engineering. – 2019. – С. 1-30.

Lemmatus

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

... <s> м а м а <lc> м ы л а <rc> р а м у <s> ...

Здесь символы <lc> и <rc> используются для обозначения левой и правой границы рассматриваемого слова, а <s> - для разделения слов (вместо пробела).

Bergmanis T., Goldwater S. Context sensitive neural lemmatization with lematus //Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers). – 2018. – С. 1391-1400.

Корпуса для обучения лемматизаторов есть в Universal Dependencies: https://universaldependencies.org/