Составляющие и бесконтекстный синтаксический анализ

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

Definition

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

Scope

Охватывает синтаксический анализ с использованием бесконтекстных грамматик: алгоритмы CKY и Эрли, нормальную форму Хомского, вероятностные бесконтекстные грамматики и их лексикализованные уточнения, а также статистические парсеры, обученные на синтаксических корпусах (treebank). Рассматриваются разрешение неоднозначности и оценка парсеров. Зависимостные представления и не-бесконтекстные формализмы рассматриваются в смежных темах.

Core questions

• Как алгоритм CKY выполняет синтаксический анализ предложения за кубическое время?
• Почему грамматики часто должны быть сначала преобразованы в нормальную форму Хомского?
• Как вероятностные и лексикализованные грамматики улучшают разрешение неоднозначности?
• Как измеряется точность парсера по отношению к синтаксическому корпусу (treebank)?

Key concepts

• бесконтекстная грамматика
• алгоритм CKY
• алгоритм Эрли
• нормальная форма Хомского
• вероятностная бесконтекстная грамматика
• лексикализация
• дерево синтаксического разбора
• синтаксический корпус (treebank)

Key theories

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

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

Лексикализованный вероятностный синтаксический анализ

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

History

Алгоритм CKY (1960-е годы) и алгоритм Эрли 1970 года обеспечили эффективное бесконтекстное распознавание. С появлением Penn Treebank вероятностные, а затем лексикализованные парсеры Коллинза и Чарняка достигли высокой точности в конце 1990-х годов, определив эру статистического синтаксического анализа до появления нейронных моделей.

Debates

Насколько необходима лексикализация?

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

Key figures

• Jay Earley
• Michael Collins
• Eugene Charniak

Seminal works

• earley1970
• collins2003

Frequently asked questions

Что такое таблица (chart) в синтаксическом анализе?

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