Синтаксический анализ (компьютерная лингвистика)

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

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

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

Анализ избирательного округа

См. Также: Грамматика структуры фразы.

Синтаксический анализ округа включает в себя синтаксический анализ в соответствии с формализмами грамматики округа, такими как минимализм или формализм Penn Treebank . Это, по крайней мере, означает указание того, какие промежутки являются составляющими (например , [Человек] здесь. ) и какого типа это составляющая (например, [Человек] — именное словосочетание) на основе контекстно-свободной грамматики. (CFG), который кодирует правила формирования и слияния компонентов.

Алгоритмы обычно требуют преобразования CFG в нормальную форму Хомского (с двумя дочерними элементами на каждую составляющую), что можно сделать без потери какой-либо информации о дереве или снижения выразительности с использованием алгоритма, впервые описанного Хопкрофтом и Ульманом в 1979 году.

ККИ

Самым популярным алгоритмом анализа округов является алгоритм Кока – Касами – Янгера (CKY). это алгоритм динамического программирования, который строит синтаксический анализ в худшем случае ${\mathcal {O}}\left(n^{3}\cdot \left|G\right|\right)$ время, по приговору $n$ слова и $\left|G\right|$ — размер CFG, заданный в нормальной форме Хомского .

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

Дальнейшей модификацией является лексикализованный PCFG, который присваивает заголовок каждому компоненту и кодирует правило для каждой лексемы в этом слоте заголовка. Таким образом, если PCFG может иметь правило «NP → DT NN» (именная группа является определителем и существительным), то в то время как лексикализованный PCFG будет иметь такие правила, как «NP(собака) → DT NN(собака)» или «NP (человек)» и т. д. На практике это приводит к некоторому улучшению производительности.

В более поздних работах нейронная оценка вероятностей промежутков (которая может учитывать контекст в отличие от (P)CFG) для передачи в CKY, например, с использованием рекуррентной нейронной сети или преобразователя. поверх вложений слов .

В 2022 году Никита Китаев и др. представил инкрементный синтаксический анализатор, который сначала изучает дискретные метки (из фиксированного словаря) для каждого входного токена с учетом только левого контекста, которые затем являются единственными входными данными для анализатора диаграмм CKY с вероятностями, рассчитанными с использованием изученного средства оценки нейронного диапазона. Этот подход не только лингвистически мотивирован, но и конкурирует с предыдущими подходами к анализу избирательного округа. Их работа получила награду за лучшую бумагу на ACL 2022 .

На основе перехода

После успеха $O(n)$ синтаксический анализ грамматик зависимостей на основе переходов, началась работа по адаптации подхода к синтаксическому анализу групп. Первую подобную работу провели Кенджи Сагае и Алон Лави в 2005 году, в которых для жадного принятия решений о переходе использовался классификатор на основе признаков. За этим последовала работа Юэ Чжана и Стивена Кларка в 2009 году, которые добавили в декодер поиск луча, чтобы сделать более глобально оптимальный анализ. Первым парсером этого семейства, превзошедшим по производительности парсер на основе диаграмм, был разработан Мухуа Чжу и др. в 2013 году, который решил проблему различий в длине различных последовательностей переходов из-за правил унарного округа (несуществующая проблема для анализа зависимостей) путем добавления операции заполнения.

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

Последовательность к последовательности

См. также: Seq2seq

Другой подход к анализу избирательного округа с использованием моделей нейронных последовательностей был разработан Ориолом Виньялсом и соавт. в 2015 году. В этом подходе синтаксический анализ составляющих моделируется как машинный перевод : задача состоит в преобразовании последовательности в последовательность из предложения в синтаксический анализ избирательного округа, в исходной статье используется глубокий LSTM с механизмом внимания . Для модели такого типа золотые обучающие деревья должны быть линеаризованы, но при преобразовании не теряется никакой информации. Это происходит в $O(n)$ с декодером поиска луча шириной 10 (но они не обнаружили особой выгоды от большего размера луча и даже ограничение его жадным декодированием работает хорошо) и достигает конкурентоспособной производительности с традиционными алгоритмами контекстно-свободного анализа, такими как CKY.

Анализ зависимостей

См. также: Грамматика зависимостей.

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

В целом существует три современные парадигмы моделирования анализа зависимостей: на основе переходов, на основе грамматики и на основе графов.

На основе перехода

Многие современные подходы к анализу дерева зависимостей используют анализ на основе переходов (базовую форму этого иногда называют дуговым стандартом ), как это сформулировано Йоакимом Нивре в 2003 году: который расширяет синтаксический анализ сдвига-сокращения , сохраняя текущий стек токенов и выбирая из трех операций для следующего встреченного токена:

• LeftArc (текущий токен является дочерним элементом вершины стека, не добавляется в стек)
• RightArc (текущий токен является родителем вершины стека, заменяет вершину)
• Shift (добавить текущий токен в стек)

Алгоритм можно сформулировать как сравнение двух верхних токенов стека (после добавления следующего токена в стек) или верхнего токена в стеке и следующего токена в предложении.

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

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

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

Все они пока поддерживают только проективные деревья, в которых ребра не пересекаются, учитывая порядок токенов в предложении. Для непроективных деревьев Nivre в 2009 году модифицировал анализ на основе переходов, основанный на стандарте дуги, добавив операцию Обмен (поменяйте местами два верхних жетона в стеке, предполагая формулировку, при которой следующий токен всегда добавляется в стек первым). Это увеличивает время выполнения до $O(n^{2})$ в худшем случае, но практически все еще почти линейный.

Основанный на грамматике

Подход динамического программирования на основе диаграмм к анализу проективных зависимостей был предложен Майклом Коллинзом. в 1996 году и дополнительно оптимизирован Джейсоном Эйснером. в том же году. Это адаптация CKY (ранее упомянутого для анализа округов) к зависимостям с заголовками, преимуществом которого является то, что единственным отличием от анализа округов является то, что каждый компонент возглавляется одним из своих узлов-потомков. Таким образом, можно просто указать, какой дочерний элемент обеспечивает заголовок для каждого правила округа в грамматике (например, NP возглавляет его дочерний элемент N), чтобы перейти от анализа CKY округа к анализу CKY зависимостей.

Первоначальная адаптация Макдональдса имела продолжительность $O(n^{5})$, а оптимизация динамического программирования Эйснера сократила время выполнения до $O(n^{3})$. В своей статье Эйснер предложил три различных метода оценки вероятностей промежутков.

На основе графика

Исчерпывающий поиск возможного $n^{2}$ ребра в дереве зависимостей с обратным отслеживанием в случае создания неправильно сформированного дерева дают базовую линию $O(n^{3})$ среда выполнения для анализа зависимостей на основе графов. Этот подход был впервые официально описан Майклом А. Ковингтоном в 2001 году, но он утверждал, что это «алгоритм, который в той или иной форме известен с 1960-х годов».

Задачу синтаксического анализа также можно смоделировать как поиск охватывающей древовидность с максимальной вероятностью по графу всех возможных ребер зависимостей, а затем выбор меток зависимостей для найденных ребер в дереве. Учитывая это, мы можем использовать расширение алгоритма Чу-Лю/Эдмондса с помощью средства оценки ребер и средства оценки меток. Этот алгоритм был впервые описан Райаном Макдональдом , Фернандо Перейрой , Кирилом Рыбаровым и Яном Хаичем в 2005 году. Он может обрабатывать непроективные деревья в отличие от стандартного анализатора дуговых переходов и CKY. Как и раньше, системы оценки могут быть нейронными (обученными на встраивании слов) или основанными на признаках. Это происходит в $O(n^{2})$ с расширением алгоритма Тарьяном.

Оценка

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

Анализ зависимостей также можно оценить с помощью оценки привязанности . Оценка немаркированного прикрепления (UAS) — это процент токенов с правильно назначенными заголовками, а оценка помеченного прикрепления (LAS) — это процент токенов с правильно назначенными заголовками и метками отношений зависимости.

Преобразование между синтаксическими анализами

Учитывая, что большая часть работы по синтаксическому анализу английского языка зависела от Penn Treebank , который использовал формализм округов, во многих работах по анализу зависимостей были разработаны способы детерминированного преобразования формализма Пенна в синтаксис зависимостей, чтобы использовать его в качестве обучающих данных. Одним из основных алгоритмов преобразования был Penn2Malt, который переосмыслил предыдущую работу над этой проблемой.

Работа в направлении преобразования зависимостей в группу участников выигрывает от более быстрого выполнения алгоритмов анализа зависимостей. Один из подходов заключается в использовании ограниченного синтаксического анализа CKY, игнорируя диапазоны, которые явно нарушают структуру анализа зависимостей, и, таким образом, сокращая время выполнения до $O(n^{2})$. Другой подход состоит в том, чтобы обучить классификатор находить порядок для всех зависимых элементов каждого токена, в результате чего получается структура, изоморфная анализу округа.

Дальнейшее чтение

• Юрафски, Дэн; Мартин, Джеймс Х. (2021). Обработка речи и языка (3-е изд.) . Проверено 22 октября 2021 г.

Анализ зависимостей

• Кюблер, Сандра; Макдональд, Райан; Нивре, Иоаким (2009). Грэм Херст (ред.). Анализ зависимостей . Обобщающие лекции по технологиям человеческого языка. Морган и Клейпул.