Грамматика ограничений - Constraint grammar

Грамматика ограничений ( CG ) - это методологическая парадигма обработки естественного языка (NLP). Написанные лингвистом контекстно- зависимые правила компилируются в грамматику, которая присваивает грамматические теги («чтения») словам или другим токенам в текущем тексте. Типичные теги адресуют лемматизацию ( лексема или базовая форма ), флексия , деривация , синтаксическая функция , зависимость, валентность , роли случая , семантический тип и т. Д. Каждое правило добавляет, удаляет, выбирает или заменяет тег или набор грамматических тегов в заданном контекст предложения. Условия контекста могут быть связаны с любым тегом или набором тегов любого слова в любом месте предложения, локально (определенные расстояния) или глобально (неопределенные расстояния). Условия контекста в одном и том же правиле могут быть связаны, т. Е. Обусловлены друг другом, отрицаться или блокироваться мешающими словами или тегами. Типичные компьютерные графики состоят из тысяч правил, которые применяются последовательно, поэтапно, охватывая все более сложные уровни анализа. На каждом уровне безопасные правила используются перед эвристическими правилами, и никакому правилу не разрешается удалять последнее чтение данного типа, что обеспечивает высокую степень устойчивости.

Концепция компьютерной графики была запущена Фредом Карлссоном в 1990 году (Karlsson 1990; Karlsson et al., Eds, 1995), и с тех пор CG-тегеры и синтаксические анализаторы были написаны для большого количества языков, регулярно получая F-баллы точности для части речи. (класс слов) более 99%. Ряд синтаксических систем CG сообщил о примерно 95% F-баллов для меток синтаксических функций. Системы CG могут использоваться для создания полных синтаксических деревьев в других формализмах путем добавления небольших, нетерминальных грамматик структуры фраз или грамматик зависимостей , а ряд проектов Treebank использовали CG для автоматического аннотации. Методология компьютерной графики также использовалась в ряде языковых технологических приложений, таких как средства проверки орфографии и системы машинного перевода .

Синтаксис и формат правила

Анализатор грамматики ограничений ожидает на входе поток морфологически проанализированных токенов, обычно производимых анализатором на основе преобразователя с конечным числом состояний (распространенными являются инструменты Xerox twolc / lexc / xfst, HFST или lttoolbox Apertium ). Каждый жетон может быть неоднозначным и иметь много чтений , форма поверхности со всеми его чтениями называется когортой . Ниже приведен возможный пример анализа ", а X был похож на" "в формате ввода, ожидаемом VISL CG-3:

"<,>"
	"," cm
"<and>"
	"and" conj
"<X>"
	"X" num pl
	"X" noun prop
"<was>"
	"be" verb past p1 sg
	"be" verb past p3 sg
"<like>"
	"like" adj
	"like" subj
	"like" pr
	"like" verb inf
	"like" verb pres
	"like" verb imp
"<“>"
	"“" lquot

Этот фрагмент показывает 5 когорт, каждая с одним или несколькими показаниями. Поверхностные словоформы в, в "<anglequotes>"то время как леммы / базовые формы в обычном, "quotes"за которыми следует набор тегов без кавычек , и мы видим, что некоторые когорты имеют несколько чтений, т. Е. неоднозначны ( "<like>"неоднозначны между 6 показаниями). Задача CG-синтаксического анализатора теперь состоит в том, чтобы: 1) удалить столько неверных показаний, сколько безопасно сделать с учетом контекста, 2) необязательно применить одну или несколько меток синтаксических функций к каждой когорте (или даже отношениям зависимости) и 3) устранить неоднозначность примененные метки / отношения.

Ниже приведен пример правила (опять же в формате VISL CG-3) для выбора чтения «было» от третьего лица (путем удаления чтения от первого лица), учитывая, что слева нет местоимения от первого лица:

REMOVE (verb p1) IF 
  (0C (verb))
  (NEGATE *-1 (prn p1)) ;

Вот (verb p1)набор тегов (порядок не имеет значения), которые должны соответствовать удаляемому чтению. После IFследует список из нуля или более ограничений , первый говорит, что в этой когорте (позиция 0) все показания (квалификатор Cдля Careful) имеют тег verb. Второе ограничение говорит, что если есть когорта, которая находится по крайней мере на одно слово слева (позиция *-1, *значение, которое мы можем пойти дальше, чем на одно слово, а -значение слева), и эта когорта является местоимением от первого лица, то ограничение * не * совпадение ( NEGATE).

В CG-3 правила могут также иметь имена, например SELECT:somename (…) IF, которые отображаются в выходных данных трассировки.

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

SELECT:quoting ("like" subj) IF 
  (-1 ("<was>"))
  (1 (lquot) OR (":"))  ;

В этом правиле мы видим, что можем ссылаться как на словоформы, так и на базовые формы в наборах тегов (они обрабатываются так же, как и любой другой тег, и чтение всегда будет соответствовать его форме слова). Здесь второе ограничение используется ORдля объединения двух наборов тегов. Если этот набор обычно используется, мы можем дать ему имя и использовать имя - без скобок - например:

LIST prequote = lquot ":" ; 
SELECT:quoting ("like" subj) IF 
  (-1 ("<was>"))
  (1 prequote) ;

Эквивалентное определение было бы SET prequote = (lquot) OR (":") ; .

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

"<,>"
	"," cm
"<and>"
	"and" conj
"<X>"
	"X" num pl
	"X" noun prop
"<was>"
	"be" verb past p3 sg
"<like>"
	"like" subj
"<“>"
	"“" lquot

Если бы мы использовали --trace, мы бы увидели удаленные показания с инициалом ;, а также имя и номер строки правила, где бы оно ни применялось к показанию.


Синтаксис правила для добавления меток синтаксических функций следует аналогичной схеме «сделай это, если x, y и z»:

LIST nominal = noun prn ;
ADD (@SUBJ) IF 
  (NEGATE *-1 nominal)
  (0C (prop))
  (1C finiteverb) ;

Это называется «правилом сопоставления», и мы можем получить несколько таких тегов сопоставления для каждой когорты, и в этом случае мы можем устранить неоднозначность, используя одни и те же правила SELECT / REMOVE.

Реализации

CG-1

Первой реализацией CG была CGP Фреда Карлссона в начале 1990-х годов. Он был основан исключительно на LISP , а синтаксис был основан на s-выражениях LISP (Karlsson 1990).

CG-2

Реализация mdis CG-2 Паси Тапанайнена удалила некоторые круглые скобки в формате грамматики и была реализована на C ++, интерпретируя грамматику как преобразователь конечного состояния для скорости.

Позднее CG-2 была переопределена (с использованием метода, отличного от FST) группой VISL в Сидданском университете как VISL CG с открытым исходным кодом [1] , сохранив тот же формат, что и mdis с закрытым исходным кодом Тапанайнена .


CG-3

Скриншот cg3ide VISL
Редактирование и запуск файла CG-3 в Emacs cg.el

Позднее проект VISL превратился в VISL CG-3, который внес дальнейшие изменения и дополнения в формат грамматики, например:

  • полная поддержка Unicode через международные компоненты для Unicode
  • иное толкование отрицания (НЕ)
  • именованные отношения в дополнение к простым отношениям зависимости
  • переменная установка
  • полное соответствие регулярному выражению
  • tag / set unification - LIST gen = m f; SELECT (det) + $$gen IF (1 noun) (1 $$gen);выберет определитель, имеющий тот же пол, что и следующее существительное
  • оболочки для чтения / записи форматов Apertium и HFST
  • поддержка вложенных чтений (где одно чтение состоит из нескольких «частей», используемых для многословных выражений и составных слов)
  • сканирование за исходную точку или даже за границы окна
  • использовать как библиотеку и поддерживать интеграцию с внешними процессами

Также существует простая IDE для CG-3, разработанная VISL [2], которая обеспечивает подсветку синтаксиса и позволяет вам видеть ввод и вывод, а также возможные ошибки при написании грамматики. Существует также режим Emacs cg.el[3] с аналогичными функциями и простой навигацией по коду.

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

Были экспериментальные переопределения CG-2 на основе FST с открытым исходным кодом, которые для малых грамматик достигают скорости VISL CG-3, если не mdis .

Список систем

Бесплатно программное обеспечение
Несвободное программное обеспечение

использованная литература

  1. ^ Для английского см., Например, Tapanainen and Voutilainen 1994.
  2. ^ Tapanainen, Pasi 1996: реляционная Grammar Parser CG-2. Публикации Хельсинкского университета № 27.
  3. ^ Nemeskey, DM, Tyers, FM и Hulden, M. (2014) "Почему реализации Вопросы: Оценка с открытым исходным кодом Constraint Grammar Parser". Труды 25-й Международной конференции по компьютерной лингвистике (COLING 2014) (в печати)
  • Бик, Экхард. 2000. Система синтаксического анализа "Palavras": автоматический грамматический анализ португальского языка в рамках грамматической системы ограничений . Орхус: Издательство Орхусского университета. ISBN  87-7288-910-1 .
  • Карлссон, Фред. 1990. Ограниченная грамматика как основа для анализа неограниченного текста. Х. Карлгрен, ред., Труды 13-й Международной конференции по компьютерной лингвистике , Vol. 3. Хельсинки 1990, 168–173.
  • Карлссон, Фред, Атро Воутилайнен, Юха Хейккиля и Арто Анттила, редакторы. 1995. Ограниченная грамматика: независимая от языка система для анализа неограниченного текста . Обработка естественного языка, № 4. Мутон де Грюйтер, Берлин и Нью-Йорк. ISBN  3-11-014179-5 .
  • Тапанайнен, Паси и Атро Воутилайнен 1994: Точная маркировка : не угадайте, если знаете . ANLC '94 Труды четвертой конференции по прикладной обработке естественного языка.

внешние ссылки