О свойствах обобщенных категориальных грамматик зависимостей

Размещено на http://www.allbest.ru

О СВОЙСТВАХ ОБОБЩЁННЫХ КАТЕГОРИАЛЬНЫХ ГРАММАТИК ЗАВИСИМОСТЕЙ

Б.Н. Карлов (bnkarlov@gmail.com)

Тверской государственный университет,

Тверь

В работе рассматриваются обобщённые категориальные грамматики зависимостей (оКГЗ), введённые в [Dekhtyar et al., 2008]. Для них определяется нормальная форма. Доказывается, что множество оКГЗ-языков является абстрактным семейством языков. Устанавливается существование неполулинейных оКГЗ-языков. Доказывается, что проблема принадлежности предложения оКГЗ-языку является NP-полной. Рассматривается расширение синтаксиса и алгоритм анализа.

Введение

Формальные способы описания синтаксической структуры предложения имеют первостепенную важность для большинства задач информатики, связанных с обработкой информации на естественном языке. После основополагающих работ Н. Хомского, определившего четыре базовых класса порождающих грамматик, был определен ещё целый ряд типов грамматик, позволяющих получить ту или иную информацию о синтаксической структуре предложения. В частности, специальный тип грамматик, грамматики зависимостей, присваивают структуры зависимостей (структуры подчинения) предложениям языка, который они определяют (см. [Гладкий и др., 1969; Gaifman, 1965]).

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

Для большинства «типичных» предложений их деревья зависимостей являются проективными: для любых трех слов v, w и u из того, что v > u и w лежит между v и u, следует, что w зависит от v. С другой стороны, в естественных языках достаточно распространены (особенно в художественной литературе) и непроективные конструкции, когда подчинённое слово стоит вне синтаксической группы своего хозяина. В качестве примера приведём оригинальную строчку А.С. Пушкина:

Непроективность всегда связана с разрывными зависимостями. В нашем примере такая зависимость показана штриховой линией.

Классические кс-грамматики, как и обычные категориальные грамматики неспособны обнаруживать в подобных предложениях разрывные составляющие. М.И. Дехтярь и А.Я. Диковский в работах [Dekhtyar et al., 2004; Dekhtyar et al., 2008] определили новые виды грамматик - категориальные грамматики зависимостей (КГЗ) и обобщенные категориальные грамматики зависимостей (оКГЗ). Эти грамматики работают как грамматики-распознаватели и структуру предложения раскрывают подобно грамматикам зависимостей. Их особенностью является то, что они способны обнаруживать дальние связи (как в приведённом примере из Пушкина). Подобные ситуации обрабатываются в них с помощью так называемых поляризованных валентностей: положительных, отвечающих за слово-хозяин, и отрицательных, отвечающих за подчинённое слово.

Настоящая работа продолжает исследование свойств оКГЗ. В ней определена нормальная форма оКГЗ и установлено, что класс оКГЗ-языков образует абстрактное семейство языков. Показано существование неполулинейных оКГЗ-языков. Кроме того, доказано, что проблема принадлежности предложения оКГЗ-языку является NP-полной.

1. Основные определения

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

Для описания дальних связей в [Dekhtyar et al., 2004] вводятся понятия полярности и поляризованной валентности. Полярностью v называется элемент множества . Поляризованная валентность в - это выражение вида vC, где C. Пары двойственных валентностей и назовём правильными (являются соответствующими «скобками»). Последовательность поляризованных валентностей называется потенциалом. Множество всех возможных потенциалов обозначается Pot(C). Потенциал называется сбалансированным, если его проекция на каждую пару двойственных поляризованных валентностей является правильным скобочным словом.

Определение 1. Множество локальных категорий LCat(C) - это минимальное множество такое, что:

1) , где е - пустой символ;

2) если , то .

Из локальных категорий и потенциалов строятся категории.

Определение 2. Категорией г называется выражение вида , где б - локальная категория, и - потенциал. Множество всех категорий обозначается Cat(C). грамматика зависимость категориальный обобщенный

Пример 1. В приведённом выше предложении глагол «воздвиг» имеет категорию [доп*\подл\Пр], а существительное «памятник» - .

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

Определение 3. Обобщённой категориальной грамматикой зависимостей (оКГЗ) называется система , где:

W - конечное множество слов,

C - конечное множество элементарных категорий,

S - выделенная в C главная категория,

д - лексикон, функция на W такая, что для каждого слова w из W (мы будем задавать его в виде ),

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

Для строки категорий определены следующие правила сокращения.

Определение 4. Пусть дана строка категорий .

Правила локальной зависимости:

,

,

где .

Правила итеративной зависимости:

,

,

,

,

где .

Правило дальней зависимости:

где образуют правильную пару, и₂ не содержит , а также для всех , где A - тип валентности в.

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

Определение 5. Предложение принадлежит языку L(G), если существует строка категорий Г такая, что:

1) , где для i=1,…,n;

2) .

Класс всех языков, порождаемых обобщёнными категориальными грамматиками зависимостей, обозначим L(gCDG).

Пример 2. В качестве примера рассмотрим язык . Известно, что он не является контекстно-свободным. Однако его можно задать при помощи следующей оКГЗ .

Несложно видеть, что локальные правила сокращения действуют только на локальную часть категории, тогда как правило сокращения потенциала D затрагивает только потенциал. Это даёт возможность разделить анализ предложения в оКГЗ на два независимых теста: первый - в терминах локальных категорий и локальных правил сокращения, а второй - в терминах сбалансированности потенциала. Имеет место теорема об анализе для оКГЗ.

Теорема 1. Предложение принадлежит языку L(G), задаваемому оКГЗ , тогда и только тогда, когда существует строка категорий , где , такая, что:

1) ,

2) сбалансирован.

2. Нормальная форма оКГЗ

Известно, что для кс-грамматик существуют различные специальные формы (нормальная форма Хомского, нормальная форма Грейбах (см. [Гладкий, 1973])), упрощающие анализ порождаемых ими языков. В этом разделе мы определяем нормальную форму для оКГЗ, аналогичную нормальной форме Грейбах.

Определение 7. Будем называть оКГЗ грамматикой в нормальной форме, если все её категории имеют один из следующих видов:, , , где X, Y, Z - элементарные категории, и - потенциал.

Теорема 2. Для любой оКГЗ существует оКГЗ в нормальной форме такая, что .

Доказательство этой теоремы для оКГЗ аналогично доказательству о нормальной форме из [Карлов, 2008].

3. Свойства замкнутости

Ряд свойств замкнутости был ранее установлен для класса языков, задаваемых КГЗ (см. [Dekhtyar et al., 2008; Карлов, 2008]). Вопрос о замкнутости этого класса языков относительно итерации до сих пор остаётся открытым. Оказалось, что класс оКГЗ-языков замкнут относительно этой операции.

Теорема 3. Если L является оКГЗ-языком, то L* также является оКГЗ-языком.

Набросок доказательства. Пусть язык L задаётся грамматикой . Приведём основную конструкцию для грамматики , задающей язык L*. Будем считать, что G - грамматика в нормальной форме, не содержащая S в списках зависимостей. Построим индукцией по i последовательность грамматик .

Базис индукции.

. Если в G у слова w есть категория , то в G₁ добавим этому слову категорию .

Индукционный шаг.

Пусть в грамматике G_i есть новые категории . Если в G_i у слова w была категория , то в G_i+1 добавим для w категорию . После этого для каждой категории добавим категорию . Этот процесс остановится не более чем через |C| шагов. Пусть последняя грамматика - . Пусть - новая категория. Построим грамматику следующим образом. Категории вида заменим на , категории вида заменим на . Если в G_m есть категории вида , то их заменим на . Наконец, для всех . Теперь можно построить грамматику, задающую итерацию исходного языка: . Если в есть категория , то в добавим .

Утверждение. .

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

Теорема 4. Класс L(gCDG) является абстрактным семейством языков.

4. Неполулинейность

Как известно, кс-языки обладают свойством полулинейности. В частности, длины входящих в них слов содержат бесконечные арифметические прогрессии. В этом разделе мы показываем, что класс оКГЗ-языков содержит неполулинейные языки. Примером такого языка является . Язык L задаётся следующей грамматикой.

Идея конструкции состоит в том, что каждый блок нулей ловит слева стрелки, а направо выпускает их в два раза больше. Чтобы блок не поймал свои же стрелки, используется чередование стрелок A и B. Чтобы стрелки не прошли дальше своего блока, добавлены зависимости X и Y.

Теорема 5. Класс оКГЗ-языков не является полулинейным.

5. Сложность проблемы принадлежности

В работе [Dekhtyar et al., 2004] было показано, что проблема определения по КГЗ G и слову w, принадлежит ли w языку L(G), является NP-полной. Для класса оКГЗ-языков этот результат может быть усилен.

Теорема 6. Существует оКГЗ G такая, что проблема принадлежности является NP-полной.

Набросок доказательства. Построим оКГЗ следующим образом. Пусть , . Далее определим ограничения на стрелки: , . Теперь опишем словарь д.

Покажем, как проблема выполнимости КНФ сводится к проблеме принадлежности для грамматики G. Пусть - КНФ, содержащая переменные x₁,…,x_n. Каждому дизъюнкту C_i сопоставим предложение , где , если x_j входит в C_i, , если входит в C_i и , если x_j не входит в C_i. Определим для Ф предложение.

Утверждение. Ф выполнима тогда и только тогда, когда .

6. Алгоритм анализа для расширенного синтаксиса оКГЗ

Естественные языки содержат очень большое количество слов, а каждое слово имеет большое количество категорий. Это затрудняет их анализ и построение адекватной грамматики. Чтобы приспособить оКГЗ для анализа естественных языков А.Я. Диковский в [Dikovsky, 2009] предложил использовать в категориях плоские регулярные выражения. Например, выражение вида [(A|B)*\C/D?/{E,F,G}] задаёт категории, в которых левее C идёт произвольная последовательность категорий A и B, D может присутствовать или отсутствовать правее C, а E, F и G должны стоять правее C в произвольном порядке. Например, одной из них будет категория [B\A\B\C/G/D/E/F]. Правила сокращения для оКГЗ естественным образом расширяются на этот синтаксис. Обозначим через L(gCDG_ext) класс языков, задаваемых оКГЗ в расширенном синтаксисе. Это расширение оказывается консервативным.

Теорема 7. L(gCDG)=L(gCDG_ext).

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

Благодарности

Работа выполнена при финансовой поддержке РФФИ (проекты № 08-01-00241 и 10-01-00532а). Автор благодарен М.И. Дехтярю и А.Я. Диковскому за поддержку этой работы.

Список литературы

[Гладкий, 1973] Гладкий А.В. Формальные грамматики и языки. - М.: Наука, 1973.

[Гладкий и др., 1969] Гладкий А.В., Мельчук И.А. Элементы математической лингвистики. - М.: Наука, 1969.

[Карлов, 2008] Карлов Б.Н. Нормальные формы и автоматы для категориальных грамматик зависимостей // Вестник Тверского государственного университета, серия «Прикладная математика», 2008, №35 (95).

[Dekhtyar et al., 2004] Dekhtyar M., Dikovsky A. Categorial Dependency Grammars // Proc. of Int. Conf. on Categorial Grammars, 2004.

[Dekhtyar et al., 2008] Dekhtyar M., Dikovsky A. Generalized Categorial Dependency Grammars // Pillars of Computer Science: Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday. LNCS, v. 4800, 2008.

[Dikovsky, 2009] Dikovsky A. Towards Wide Coverage Categorial Dependency Grammars // Proc. of the ESSLLI'2009 Workshop on Parsing with Categorial Grammars, Bordeaux, France, 2009.

[Gaifman, 1965] Gaifman H. Dependency systems and phrase structure systems // Information and Control, 1965, v. 8, №3.

Размещено на Allbest.ru