О классах категориальных грамматик зависимостей тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Карлов, Борис Николаевич

• Карлов, Борис Николаевич
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Карлов, Борис Николаевич

Введение

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

2 Категориальные грамматики зависимостей

2.1 Нормальные формы.

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

2.3 Теорема о представлении

2.4 Автоматы для распознавания КГЗ-языков

3 Мультимодальные категориальные грамматики зависимостей

3.1 Нормальные формы.

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

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

3.4 Сложность распознавания ммКГЗ-языков.

Введение диссертации (часть автореферата) на тему «О классах категориальных грамматик зависимостей»

Актуальность. Формальные способы описания синтаксической структуры предложения имеют первостепенную важность для большинства задач информатики, связанных с обработкой информации на естественном языке. После основополагающих работ Н. Хомского. определившего четыре базовых класса порождающих грамматик, был определен еще целый ряд типов грамматик, позволяющих вычислять синтаксическую структуру предложения в ходе его вывода или доказательства его правильности. В частности, грамматики зависимостей (специальный тип грамматик) присваивают структуры зависимостей (структуры подчинения) предложениям языка, который они определяют. Теории синтаксиса естественных языков, основанные на понятии зависимости, имеют давнюю традицию, восходящую к средним векам. Теньер впервые систематически описал структуру предложения в терминах именованных бинарных отношений между словами (зависимостей) [7]. Когда два слова ги 1 и связаны в предложении посредством зависимости д (обозначение и)\ -4 и^); является главным словом, а и)2 — зависимым словом. Содержательно, зависимость с1 задаёт ограничения на грамматические и лексические свойства и гиг, на их порядок, контекст и т.п., которые вместе означают, что "гг^ управляет ги2". Например, в структуре зависимостей предложения "Летом здесь играют дети", приведённой на рис. 1, отношение играют дети показывает предикатную зависимость между сказуемым играют и подлежащим дети, в котором главным словом является глагол.

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

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

I- >1 летом здесь будут играть дети

Рис. 2: Пример непроективной структуры зависимостей в русском языке

Например, использование будущего времени в предложении "Летом здесь будут играть дети" приводит к появлению двух разрывных зависиобстп-вр обстп-лок -1 0 мостеи играть -—> летом и играть —У здесь, показанных на рис. ¿. Разрывные зависимости встречаются и в других языках. На рис. 3 изображена структура зависимостей французского предложения "Il n'en avait plus besoin" ("Он больше в этом не нуждался"), а на рис. 4 — английского предложения "The person to whom you must refer is Smith" ("Человек, к которому Вы должны обратиться, — Смит"). pred cpmpos-neg clit-p-obj p-obj p" ~ * f Ь li

1 n' en avait plus besoin

Рис. 3: Пример непроективной структуры зависимостей во французском языке

Современная лингвистическая теория синтаксических зависимостей была разработана Мельчуком [37]. Первые точные определения грамматик the person to whom you must refer is Smith

Рис. 4: Пример непроективной структуры зависимостей в английском языке зависимостей появились в работах Хейса [32] и Гайфмана [28]. Они имели много общего с классическими категориальными грамматиками Бар-Хиллела [14] (которые восходят к работам Лесьневского [36] и Айдукеви-ча [12]). Они полностью лексикализованы, используют синтаксические типы вместо правил вывода и естественно подходят для функциональных семантических структур. В 1960 году Бар-Хиллел, Гайфман и Шамир доказали. что формальный язык может быть задан классической категориальной грамматикой тогда и только тогда, когда он является контекстно-свободным [15]. В 1958 году Ламбек ввёл синтаксическое исчисление, расширяющее исчисление категориальных грамматик [35]. В 1986 году Буш-ковский доказал, что грамматики Ламбека в неассоциативном варианте эквивалентны контекстно-свободным грамматикам (кс-грамматикам) [17], а в 1993 году Пентус доказал эквивалентность кс-грамматик и исходных (ассоциативных) грамматик Ламбека [38]. Однако сейчас признано, что кс-грамматики недостаточно выразительны для описания естественных языков. Например, кс-грамматики, как и классические категориальные грамматики, неспособны описывать в предложениях, подобных вышеприведённым. разрывные составляющие. В результате значительный интерес представляет разработка и изучение формальных грамматик, более выразительных, чем кс-грамматики. Например. ТАГ-грамматики Джоши [33], один из классов часто используемых для практических приложений, более выразительны. чем кс-грамматики, и позволяют выражать некоторые контекстные зависимости. Как показали Виай-Шеикер и Уэйр [39], ТАГ-грамматики эквивалентны некоторым грамматикам совершенно иной природы (линейным индексным грамматикам Ахо [11. 29], комбинаторным категориальным грамматикам Стидмана [40] и некоторым другим), разделяя с ними свойства, благодаря которым их называют слабо контекстными. Имеется несколько неэквивалентных понятий слабой контскстности класса грамматик. Одно из них состоит в том, что 1) грамматики этого класса порождают все кс-языки; 2) для них существует алгоритм синтаксического анализа за полиномиальное время; 3) эти грамматики позволяют выразить по меньшей мере некоторые пересекающиеся зависимости; 4) порождаемые ими языки обладают свойством линейного роста, т.е. если все предложения языка упорядочить по длине, то длины соседних предложений могут отличаться не более чем на заранее фиксированную константу. Первые грамматики зависимостей, выражающие неограниченные непроективные зависимости, были определены Диковским в 2001 году [22, 23]. Эти грамматики являются порождающими, а непроективпые зависимости между словами определяются в них через двойственные поляризованные валентности: одноимённые однонаправленные валентности с противоположными знаками. Принцип спаривания двойственных валентностей (РА) аналогичен правильному спариванию скобок. В 2004 году Диковский определил категориальные грамматики зависимостей (КГЗ) [24]. Подобно классическим категориальным грамматикам, КГЗ являются анализирующими, т.е. синтаксическая структура предложения — дерево зависимостей — извлекается в них из доказательства правильности приписывания типов словам. Непроективпые зависимости, как и в порождающих грамматиках зависимостей, определяются через двойственные поляризованные валентности. В последующих совместных работах с Дехтярём определение КГЗ эволюционировало. Используемое ниже окончательное определение КГЗ содержится в [20]. КГЗ хорошо зарекомендовали себя на практике. Например, в университете Нанта разработана и успешно используется для синтаксического анализа и для создания корпусов деревьев зависимостей весьма полная КГЗ французского языка (см. [13. 27]). В статье [25] Диковский определил мультимодальные категориальные грамматики зависимостей (ммКГЗ), обобщающие КГЗ. Их отличие от КГЗ состоит в том. что каждому типу валентностей соответствует своё правило спаривания.

Настоящая диссертационная работа посвящена формальной теории КГЗ и ммКГЗ.

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

Методы исследования. В диссертации использованы методы математической логики, теории формальных грамматик и языков, теории автоматов, теории алгоритмов и теории сложности вычислений.

Научная новизна и основные положения, выносимые на защиту. Все полученные в работе результаты являются новыми. На защиту выносятся следующие результаты.

1. Определена нормальная форма для классов КГЗ и ммКГЗ, аналогичная нормальной форме Грейбах для кс-грамматик, и установлена возможность эффективного приведения всякой КГЗ и ммКГЗ к этой нормальной форме.

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

3. Доказано, что любой КГЗ-язык можно представить как проекцию пересечения кс-языка и скобочног "■о языка ск, состоящего из слов, проекции которых на каждый тип скобок являются правильными скобочными словами.

4. Построено расширение автоматов с магазинной памятью (МП-автоматов) — МП-автоматы с независимыми счётчиками. Эти автоматы дополняют обычные МП-автоматы конечным числом целочисленных счётчиков. Их отличие от машин Минского состоит в отсутствии проверки счётчиков на ноль. Доказано, что МП-автоматы с независимыми счётчиками распознают в точности КГЗ-языки.

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

6. Доказано, что проблема принадлежности слова ммКГЗ-языку является КР-полиой для конкретной ммКГЗ. в отличие от КГЗ, где для каждой грамматики существует полиномиальный алгоритм.

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

Апробация работы Результаты диссертации докладывались автором на семинаре по теоретической информатике в Тверском государственном университете, на семинаре по математической логике в Петербургском отделении математического института РАН и на двенадцатой национальной конференции по искусственному интеллекту с международным участием "КИИ-2010". Некоторые результаты были представлены в совместном докладе на 15-й международной конференции по формальным грамматикам ("Formal Grammars 2010". Copenhagen. Denmark). Статья [4] была представлена в 2009 году на "Открытый конкурс на лучшую научную работу студентов по естественным, техническим и гуманитарным наукам в высших учебных заведениях Российской Федерации" и получила в этом конкурсе медаль "За лучшую научную студенческую работу". Работа поддерживалась грантами РФФИ 08-01-00241 и 10-01-00532а.

Публикации. Список публикаций по теме диссертации включает 5 работ: [4, 5, 6, 21, 34]. Работы [4, 6] опубликованы в издании, входящем в список рекомендованных ВАК ведущих рецензируемых изданий. Работы [21, 34] представляют доклады на международных конференциях и опубликованы в серии Lecture Notes in Computer Science.

Результаты совместной работы [21], вошедшие в диссертацию, принадлежат автору.

Структура и объём диссертации. Диссертация состоит из настоящего введения, трёх глав основной части, заключения и списка литературы. Общий объём работы — 103 стр. Список литературы содержит 40 наименований.

Обзор работы

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

Глава 2 посвящена исследованию свойств КГЗ. В параграфе 2.1 строится нормальная форма, аналогичная нормальной форме Грейбах для кс-языков и доказывается теорема 2.1 о том, что по любой КГЗ можно эффективно построить эквивалентную КГЗ в нормальной форме полиномиального размера по отношению к исходной КГЗ. В параграфе 2.2 исследуются свойства замкнутости. В теоремах 2.2-2.6 устанавливается замкнутость класса КГЗ-языков относительно операций объединения, конкатенации, пересечения с регулярными множествами, неукорачивающего гомоморфизма и обращения гомоморфизма. В параграфе 2.3 получен результат, аналогичный теорема Хомского-Шютцеибсрже для кс-языков. Доказана теорема 2.7 о том, что любой КГЗ-язык можно получить как гомоморфизм пересечения кс-языка с некоторым скобочным языком. В параграфе 2.4 определён класс автоматов с магазинной памятью с независимыми счётчиками. Содержательно, это обычные автоматы с магазинной памятью, дополнительно оснащённые конечным числом счётчиков, которые служат для обработки поляризованных валентностей. В теоремах 2.8 и 2.9 установлено, что класс языков, распознаваемых этими автоматами, совпадает с классом КГЗ-языков.

Глава 3 посвящена исследованию свойств ммКГЗ-языков. В параграфе 3.1 мы определяем нормальную форму ммКГЗ и доказываем теорему 3.2 о существовании нормальной формы. В параграфе 3.2 доказано, что класс ммКГЗ-языков замкнут относительно операций объединения, конкатенации, пересечения с регулярными множествами, неукорачивающего гомоморфизма, обращения гомоморфизма и усечённой итерации (теоремы 3.3-3.8). На основании этих результатов в теореме 3.9 делается вывод, что класс ммКГЗ-языков образует абстрактное семейство языков (см. [31]). Также показано, что класс ммКГЗ-языков замкнут относительно пересечения (теорема 3.10), но не замкнут относительно проекции (теорема 3.11).

Языки ряда других классов являются полулинейными, в частности, полулинейны все кс-языки. В параграфе 3.3 в теореме 3.12 мы приводим пример неполулинейного языка, порождаемого ммКГЗ. В параграфе 3.4 рассматривается проблема принадлежности для ммКГЗ: по грамматике О и слову т определить, принадлежит ли слово и) языку, порождаемому С. Для первоначального варианта КГЗ была доказана NP-IЮлнoтa этой проблемы в общем случае, когда переменными являются и грамматика, и слово (см. [19]). В теореме 3.14 мы показываем, что для ммКГЗ эта проблема является КР-полной для одной грамматики и порождаемого ей языка.

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

Заключение диссертации по теме «Математическая логика, алгебра и теория чисел», Карлов, Борис Николаевич

Заключение

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

Глава 2 была посвящена исследованию свойств КГЗ. В параграфе 2.1 была построена нормальная форма, аналогичная нормальной форме Грей-бах для кс-языков и доказана теорема 2.1 о том, что по любой КГЗ можно эффективно построить эквивалентную КГЗ в нормальной форме полиномиального размера по отношению к исходной КГЗ. В параграфе 2.2 были исследованы свойства замкнутости. В теоремах 2.2-2.С была уста-навлена замкнутость класса КГЗ-языков относительно операций объединения, конкатенации, пересечения с регулярными множествами, неукора-чивающего гомоморфизма и обращения гомоморфизма. В параграфе 2.3 был получен результат, аналогичный теорема Хомского-Шютценберже для кс-языков. Была доказана теорема 2.7 о том, что любой КГЗ-язык можно получить как гомоморфизм пересечения кс-языка с некоторым скобочным языком. В параграфе 2.4 был определён класс автоматов с магазинной памятью с независимыми счётчиками. В теоремах 2.8 и 2.9 было установлено, что класс языков, распознаваемых этими автоматами, совпадает с классом КГЗ-языков.

Глава 3 была посвящена исследованию свойств ммКГЗ-языков. В параграфе 3.1 мы определили нормальную форму ммКГЗ и доказали теорему 3.2 о существовании нормальной формы. В параграфе 3.2 доказано. что класс ммКГЗ-языков замкнут относительно операций объединения. конкатенации, пересечения с регулярными множествами, неукорачи-вающего гомоморфизма, обращения гомоморфизма и усечённой итерации (теорема 3.8). На основании этих результатов в теореме 3.9 сделан вывод, что класс КГЗ-языков образует абстрактное семейство языков. Также было показано, что класс ммКГЗ-языков замкнут относительно пересечения (теорема 3.10), но не замкнут относительно проекции (теорема 3.11). В параграфе 3.3 в теореме 3.12 мы привели пример неполулинейного языка. порождаемого ммКГЗ. В параграфе 3.4 рассмотрена проблема принадлежности для ммКГЗ. В теореме 3.14 мы показали, что для ммКГЗ эта проблема является МР-полной для одной грамматики и порождаемого ей языка.

Перечислим некоторые интересные вопросы о КГЗ и КГЗ-языках, которые остаются открытыми.

1. Справедлив ли для КГЗ-языков какой-либо вариант леммы о разрастании?

2. Является ли язык Ьсори — { ипи \ ш б Е* } КГЗ-языком? (В статье [19] авторы предположили, что он не является КГЗ-языком.)

3. Являются ли все КГЗ-языки полулинейными?

4. Замкнут ли класс КГЗ-языков относительно итерации и проекции?

5. Влияет ли количество типов валентностей на выразительную силу КГЗ? Мы предполагаем, что существует иерархия но числу типов валентностей.

6. Верно ли, что классы КГЗ- и ммКГЗ-языков не совпадают?

7. Каково соотношение классов КГЗ- и ммКГЗ-языков с другими классами, расширяющими кс-языки?

Список литературы диссертационного исследования кандидат физико-математических наук Карлов, Борис Николаевич, 2012 год

1. Гинзбург С. Математическая теория контекстно-свободных языков. М.: Мир, 1970. 326 с.

2. Гладкий A.B. Формальные грамматики и языки. М.: Наука, 1973. 368 с.

3. Гладкий A.B., Мельчук И.А. Элементы математической лингвистики. М.: Наука, 1969. 192 с.

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

5. Карлов Б.Н. О свойствах обобщённых категориальных грамматик зависимостей // Двенадцатая национальная конференция по искусственному интеллекту с международным участием. Труды конференции. Т. 1. М.: Физматлит, 2010. С. 283-290.

6. Карлов Б.Н. О свойствах языков, задаваемых мультимодальными категориальными грамматиками зависимостей // Вестник Тверского государственного университета, серия "Прикладная математика", №34, 2011. С. 91-110.

7. Теньер JI. Основы структурного синтаксиса. М.: Прогресс, 1988. 656 с.

8. Хомский Н. Три модели для описания языка // Кибернетический сборник, вып. 2, ИЛ, 1961. С. 237-266.

9. Хомский Н. Синтаксические структуры // Сб. "Новое в лингвистике", вып. 2, "Прогресс", 1962. С. 412-527.

10. Хомский Н. О некоторых формальных свойствах грамматик // Кибернетический сборник, вып. 5, ИЛ, 1962. С. 279-311.

11. Aho А. V. Indexed grammars — An extension to context-free grammars //J. ACM, 15, 1968. P. 647-671.

12. Ajdukiewicz K. Die syntaktische Konnexität // Studia Philosophica, №1, 1935. P.l-27.

13. Bar-Hillel Y. A quasi-arithmetical notation for syntactic description // Language, 29(1), 1953. P. 47-58.

14. Buszkowski W. Generative power of non-associative Lambek calculus // Bull. Polish Acad. Sei. Math., 34, 1986. P. 507-516.

15. Cook S.A. The complexity of theorem-proving procedures // Proc. 3-th Ann ACM Symp. on Theory of Computing, 1971. P.151-158.

16. Dekhtyar M., Dikovsky A. Categorial Dependency Grammars // Proc. of Int. Conf. on Categorial Grammars, Montpellier, 2004. P. 76-91.

17. 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, Lecture Notes in Computer Science, vol. 4800, 2008. P. 230-255.

18. Dekhtyar M., Dikovsky A., Karlov B. Iterated dependencies and Kleene iteration // Proc. of the 15th Conference on Formal Grammar (FG 2010), Copenhagen, Denmark, Lecture Notes in Computer Science vol. 7395, Springer, 2012. P. 66-81.

19. Dikovsky A. Grammars for Local and Long Dependencies // Proc. of the Intern. Conf. ACL'2001, Toulouse, France, 2001. P. 156-163.

20. Dikovsky A. Polarized Non-projective Dependency Grammars // Proc. of the Fourth International Conference on Logical Aspects of Computational Linguistics (LACL). LNAI, №2099, 2001. P. 139-157.

21. Dikovsky A. Dependencies as Categories // Recent Advances in Dependency Grammars, 2004. P. 90-97.

22. Dikovsky A. Multimodal Categorial Dependency Grammars // Proc. of the 12th Conference on Formal Grammar, 2007. P. 1-12.

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

24. Dikovsky A. Categorial Dependency Grammars: from Theory to Large Scale Grammars // Proc. of the 1st Intern. Conf. on Dependency Linguistics (Depling 2011). Barcelona, Spain, 2011. http://depling.org/proceedingsDepling2011/

25. Gaifman II. Dependency systems and phrase structure systems // Information and Control, 1965, vol. 8, №. P. 304-337.

26. Gazdar G. Applicability of indexed grammras to natural languages // Proc. of Natural Language Parsing and Linguistic Theories Conference, Dordrecht, Holland, 1988. P. 69-94.

27. Ginsburg S., Greibach S.A., Harrison M.A. One-way stack automata // Journal of The ACM, vol. 14, m, 1967. P. 389-418.

28. Ginsburg S., Greibach S. Abstract families of languages // Mem. Amer. Math. Soc., 87, 1969. P. 1-32.

29. Hays D. G. Grouping and dependency theories/'/ Proc. of the National Symp. on Machine Translation, Englewood Cliffs, NY, 1961. P. 258-266.

30. Joshi A.K., Levy L.S., Takahashi M. Tree adjunct grammars // Journ. of Comput. and Syst. Sci., 10(1), 1975. P. 136-163.

31. Lambek J. The mathematics of sentence structure // American Mathematical Monthly, 1958. P. 154-170.

32. Lesniewski S. Grundziige eines neuen Systems der Grundlagen der Mathematik // Fundam. Math., vol. 14, 1929. P. 1-81.

33. Mel'cuk I. Dependency Syntax. SUNY Press, Albany, NY, 1988. 428 p.

34. Comp. Sei., Montreal, 1993. P. 429-433.

35. Vijay-Shanker K., Weir D.J. The Equivalence of Four Extensions of Context-Free Grammars // Mathematical Study Theory, vol. 27, 1994. P. 511-545.

36. Steedman M. Combinators and grammars // In R. Oehrle, E. Bach, and D. Wheeler, editors, Categorial Grammars and Natural Language Structures. Foris, Dordrecht, 1986. P. 417-442.