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

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

Концепция CG была предложена Фредом Карлссоном в 1990 году (Karlsson 1990; Karlsson et al., eds, 1995), и с тех пор тэггеры и анализаторы CG были написаны для большого количества языков, регулярно достигая F-показателей точности для части речи. (класс слов) более 99%. ^[1] Ряд синтаксических систем CG сообщили о F-оценке около 95% для меток синтаксических функций. Системы 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) для выбора чтения слова «was» от третьего лица (путем удаления чтения от первого лица), учитывая, что слева нет местоимения от первого лица:

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

Здесь (verb p1) представляет собой набор тегов (порядок не имеет значения), которые должны соответствовать удаляемому чтению. После IF следует список из нуля или более ограничений , первое из которых говорит о том, что в этой когорте (позиция 0) все показания (квалификатор C, для осторожности) имеют тег 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.

Реализации

КГ-1

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

КГ-2

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

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

КГ-3

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

полная поддержка Unicode через международные компоненты для Unicode
другая интерпретация отрицания (НЕ)
именованные отношения в дополнение к простым отношениям зависимости
переменная установка
полное совпадение регулярных выражений
унификация тегов/наборов – 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 . ^[3]

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

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

VISL CG-3 Компилятор/парсер CGrammar
Северо- и луле -саамы, фарерцы , коми и гренландцы из Университета Тромсё ( дополнительная информация , документация по северным саамам )
- FinCG Фреда Карлссона Оригинальный финский также доступен в Университете Тромсё под лицензией GPL, как в исходной версии CG1 , так и в преобразованной версии CG3 .
Эстонский [4]
Норвежский нюнорск и букмол онлайн , теги Осло-Берген ( исходный код )
Бретонский , валлийский , ирландский гэльский и норвежский (преобразованные из приведенных выше) в Apertium (см. CG в Apertium )

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

Баскский [5]
Каталонский CATCG
Датский DanGram
Английский ENGCG , ENGCG-2 , VISL-ENGCG
Эсперанто EspGram
Французский ФРАГ
немецкий GerGram
Ирландский онлайн
Итальянский ItaGram
испанская больница
Шведская SWECG. Архивировано 5 февраля 2007 г. в Wayback Machine.
суахили
Португальские СЛОВА

Ссылки

У Scholia есть тематический профиль по грамматике ограничений .

^ На английском языке см., например, Tapanainen and Voutilainen 1994.
^ Тапанайнен, Паси 1996: Анализатор грамматики ограничений CG-2. Публикации Хельсинкского университета No. 27.
^ Немески, Д.М., Тайерс, Ф.М. и Халден, М. (2014) «Почему реализация имеет значение: оценка анализатора грамматики ограничений с открытым исходным кодом». Материалы 25-й Международной конференции по компьютерной лингвистике (COLING 2014) (будут опубликованы)

Бик, Экхард. 2000. Система синтаксического анализа «Палаврас»: автоматический грамматический анализ португальского языка в рамках грамматики с ограничениями . Орхус: Издательство Орхусского университета. ISBN 87-7288-910-1 .
Карлссон, Фред. 1990. Ограничительная грамматика как основа для анализа неограниченного текста. Х. Карлгрен, изд., Материалы 13-й Международной конференции по компьютерной лингвистике , Vol. 3. Хельсинки 1990, 168-173.
Карлссон, Фред, Атро Вотилайнен, Юха Хейккиля и Арто Анттила, редакторы. 1995. Грамматика ограничений: независимая от языка система синтаксического анализа неограниченного текста . Обработка естественного языка, № 4. Мутон де Грюйтер, Берлин и Нью-Йорк. ISBN 3-11-014179-5 .
Тапанайнен, Паси и Атро Воутилайнен, 1994: Точная маркировка: не угадывайте, если знаете . ANLC '94 Материалы четвертой конференции по прикладной обработке естественного языка.

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

Учебник по компьютерной графике от Кевина Доннелли
VISL CG-3 , компилятор/парсер грамматики
Список некоторых публикаций по грамматике ограничений (по крайней мере, до 2010 г.)

[1] На английском языке см., например, Tapanainen and Voutilainen 1994.

[2] Тапанайнен, Паси 1996: Анализатор грамматики ограничений CG-2. Публикации Хельсинкского университета No. 27.

[3] Немески, Д.М., Тайерс, Ф.М. и Халден, М. (2014) «Почему реализация имеет значение: оценка анализатора грамматики ограничений с открытым исходным кодом». Материалы 25-й Международной конференции по компьютерной лингвистике (COLING 2014) (будут опубликованы)

[1]

[2]

[3]