Грамматика ссылок - Link grammar

Грамматика ссылок (LG) - это теория синтаксиса Дэви Темперли и Дэниела Слейтора, которая выстраивает отношения между парами слов, а не конструирует составляющие в иерархии структуры фраз . Грамматика ссылок похожа на грамматику зависимостей , но грамматика зависимостей включает отношения, зависящие от головы, тогда как грамматика ссылок делает отношения зависимости от головы необязательными (ссылки не должны указывать направление). Colored Multiplanar Link Grammar (CMLG) - это расширение LG, позволяющее пересекать отношения между парами слов. Связь между словами указывается типами ссылок , что делает грамматику ссылок тесно связанной с определенными категориальными грамматиками .

Например, в языке субъект-глагол-объект, таком как английский, глагол будет смотреть влево, чтобы образовать ссылку на тему, и вправо, чтобы образовать ссылку на объект. Существительные будут выглядеть вправо, чтобы завершить ссылку на тему, или влево, чтобы завершить ссылку на объект.

В языке субъект-объект-глагол, таком как персидский , глагол будет смотреть влево, чтобы образовать объектную связь, и более далекую левую, чтобы образовать субъектную ссылку. Существительные будут смотреть вправо как для субъектных, так и для объектных ссылок.

Обзор

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

Грамматика ссылок также отличается от традиционных грамматик зависимостей тем, что допускает циклические отношения между словами. Так, например, могут быть ссылки, указывающие как на заглавный глагол предложения, так и на заглавное подлежащее предложения, а также связь между подлежащим и глаголом. Таким образом, эти три звена образуют цикл (в данном случае треугольник). Циклы полезны для ограничения того, что в противном случае могло бы быть неоднозначным синтаксическим анализом; циклы помогают «сжать» набор допустимых синтаксических разборов предложения.

Например, в разборе

    +---->WV--->+       
    +--Wd--+-Ss-+--Pa--+
    |      |    |      |
LEFT-WALL he  runs   fast

ЛЕВАЯ СТЕНА указывает на начало предложения или корневой узел. Направленная ссылка WV (со стрелками) указывает на главный глагол предложения; это ссылка Wall-Verb. Ссылка Wd (здесь нарисована без стрелок) указывает на заглавное существительное (подлежащее) предложения. Тип ссылки Wd указывает как на то, что она соединяется со стеной (W), так и на то, что предложение является декларативным предложением (подтип «d» в нижнем регистре). Сс ссылка указывает на отношения субъект-глагол; строчная буква «s», указывающая на то, что предмет является единственным. Обратите внимание, что ссылки WV, Wd и Ss составляют цикл. Ссылка Pa соединяет глагол с дополнением; строчная буква «а», указывающая на то, что в данном случае это предикативное прилагательное .

Алгоритм разбора

Разбор выполняется аналогично сборке головоломки (представляющей проанализированное предложение) из частей головоломки (представляющих отдельные слова). Язык представлен с помощью словаря или лексики , которая состоит из слов и набора разрешенных «фигур пазла», которые может иметь каждое слово. Форма обозначена «соединителем», который является соединительным элементом, и указателем поворота + или -, указывающим вправо или влево. Так, например, у переходного глагола могут быть соединители S- и O +, указывающие, что глагол может образовывать субъектное (« S ») соединение слева от него (« - ») и объектное соединение (« O ») справа ( « + »). Точно так же нарицательное существительное может иметь соединители D- и S +, указывающие на то, что оно может соединяться с определителем слева (« D- ») и действовать как подлежащее при соединении с глаголом справа (« S + »). Затем процесс синтаксического анализа заключается в том, чтобы определить, что разъем S + может подключаться к разъему S , образуя связь « S » между двумя словами. Разбор завершается, когда все разъемы подключены.

У данного слова могут быть десятки или даже сотни разрешенных форм-головоломок (называемых «дизъюнкциями»): например, многие глаголы могут быть необязательно транзитивными, что делает соединитель O + необязательным; такие глаголы могут также принимать наречия ( соединители E ), которые по своей сути являются необязательными. Более сложные глаголы могут иметь дополнительные соединители для косвенных объектов, частиц или предлогов . Таким образом, часть синтаксического анализа также включает выбор одного уникального дизъюнкта для слова; заключительный синтаксический анализ должен удовлетворить (соединить) все соединители для этого дизъюнкта.

Зависимость

Разъемы могут также включать индикаторы зависимости от напора h и d . В этом случае разъем, содержащий индикатор головки, разрешается подключать только к разъему, содержащему зависимый индикатор (или к соединителю без каких-либо индикаторов HD на нем). Когда используются эти индикаторы, ссылка украшается стрелками, указывающими направление ссылки.

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

Планарность

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

Стоимость и выбор

Соединители могут иметь дополнительную надбавку к стоимости с плавающей запятой , так что некоторые из них «дешевле» в использовании, чем другие, что дает предпочтение определенным синтаксическим анализам по сравнению с другими. То есть общая стоимость синтаксического анализа - это сумма индивидуальных затрат на используемые соединители; самый дешевый синтаксический анализ указывает наиболее вероятный синтаксический анализ. Это используется для ранжирования нескольких неоднозначных синтаксических анализов. Тот факт, что затраты являются локальными для соединителей и не являются глобальным свойством алгоритма, делает их по сути марковскими по своей природе.

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

Поскольку затраты являются аддитивными, они ведут себя как логарифм вероятности (поскольку логарифм правдоподобия аддитивны) или, что эквивалентно, как энтропия (поскольку энтропии аддитивны). Это делает Link Grammar совместимой с методами машинного обучения, такими как скрытые модели Маркова и алгоритм Витерби , поскольку стоимость ссылок соответствует весам ссылок в сетях Маркова или байесовских сетях .

Теория типов

Типы ссылок Link Grammar можно понимать как типы в смысле теории типов . Фактически, Link Grammar может использоваться для моделирования внутреннего языка определенных (несимметричных) компактных закрытых категорий , таких как предварительные грамматики . В этом смысле Link Grammar изоморфна или гомоморфна некоторым категориальным грамматикам . Так, например, в категориальной грамматике существительная фраза « плохой мальчик » может быть записана как

тогда как соответствующие дизъюнкты в Link Grammar будут

the: D+;
bad: A+;
boy: D- & A-;

Правила сокращения (правила вывода) исчисления Ламбека могут быть отображены на соединение соединителей в грамматике ссылок. Индикаторы направления + и - соответствуют прямой и обратной косой черте категориальной грамматики. Наконец, однобуквенные имена A и D можно понимать как метки или «легкие для чтения» мнемонические имена для более подробных типов NP / N и т. Д.

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

Примеры

Пример 1

Базовый файл правил для языка SVO может выглядеть так:

<determiner>     D+;
<noun-subject>  {D−} &  S+;
<noun-object>   {D−} &  O−;
<verb>           S−  & {O+};

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

           +-----O-----+
 +-D-+--S--+     +--D--+
 |   |     |     |     |
The boy painted  a  picture

Аналогичные разборы применимы и к китайскому языку.

Пример 2

И наоборот, файл правил для языка SOV с нулевым субъектом может состоять из следующих ссылок:

<noun-subject>   S+;
<noun-object>    O+;
<verb>          {O−} & {S−};

И простое персидское предложение man nAn xordam (من نان خوردم) «Я ел хлеб» будет выглядеть так:

 +-----S-----+
 |     +--O--+
 |     |     |
man   nAn xordam

Также возможен заказ VSO, например, для арабского языка.

Пример 3 (Морфология)

Во многих языках с конкатенативной морфологией основа не играет грамматической роли; грамматика определяется суффиксами. Таким образом, в русском языке предложение «вверху плыли редкие облачка» может иметь разбор:

    +------------Wd-----------+---------------SIp---------------+
    |         +-------EI------+              +--------Api-------+
    |         |      +--LLCZD-+       +-LLAQZ+         +--LLCAO-+
    |         |      |        |       |      |         |        |
LEFT-WALL вверху.e плы.= =ли.vnndpp ре.= =дкие.api облачк.= =а.ndnpi

Нижние индексы, такие как '.vnndpp', используются для обозначения грамматической категории. Первичные ссылки: Wd, EI, SIp и Api соединяют суффиксы вместе, так как, в принципе, здесь могут появиться и другие основы, не изменяя структуру предложения. Ссылка Api указывает на прилагательное; SIp обозначает инверсию подлежащего-глагола; EI - это модификатор. Ссылка Wd используется для обозначения заглавного существительного; в этом предложении не указывается заглавный глагол. Ссылки LLXXX служат только для прикрепления основ к суффиксам.

Пример 4 (Фонология)

Грамматика ссылок также может указывать на фонологическое соответствие между соседними словами. Например:

                     +---------Ost--------+
    +------>WV------>+   +------Ds**x-----+
    +----Wd---+-Ss*b-+   +--PHv-+----A----+
    |         |      |   |      |         |
LEFT-WALL that.j-p is.v an abstract.a concept.n

Здесь соединитель «PH» используется для ограничения определителей, которые могут появляться перед словом «абстрактный». Это эффективно блокирует (делает его дорогостоящим) использование определителя «а» в этом предложении, в то время как ссылка на «ан» становится дешевой. Остальные ссылки примерно такие же, как в предыдущих примерах: S обозначает субъект, O обозначает объект, D обозначает определитель. Ссылка «WV» указывает на заглавный глагол, а ссылка «W» - на заглавное существительное. Строчные буквы, следующие за типами ссылок в верхнем регистре, служат для уточнения типа; так, например, Ds может соединяться только с существительным в единственном числе; Ss только к единственному субъекту, Os - к единственному объекту. Строчная буква v в PHv означает «гласную»; буква d в ​​нижнем регистре Wd обозначает повествовательное предложение.

Пример 5 - Вьетнамский

Предложение на вьетнамском языке «Bữa tiệc hôm qua là một thành công lớn» - «Вчерашняя вечеринка имела большой успех» можно разобрать следующим образом:

Вьетнамцы ссылаются на грамматику example.png

Реализации

Link Парсер грамматики
Разработчики) OpenCog
Первый выпуск Октябрь 1991 г . ; 29 лет назад ( 1991-10 )
Стабильный выпуск
5.8.1 / 8 января 2021 г . ; 7 месяцев назад ( 2021-01-08 )
Репозиторий
Написано в C ++ ; изначально C
Операционная система Кроссплатформенность
Платформа GNU
Тип НЛП
Лицензия LGPLv2
Веб-сайт www .abisource .com / projects / link-grammar /

Синтаксис ссылка грамматики синтаксический анализатор является библиотека для обработки естественного языка , написанной в C . Доступен по лицензии LGPL . Парсер - это постоянный проект. Последние версии включают улучшенный охват предложений, поддержку русского, персидского и арабского языков, прототипы для немецкого, иврита, литовского, вьетнамского и турецкого языков, а также программные API для Python , Java , Common LISP , AutoIt и OCaml со сторонними привязками для Perl , Руби и JavaScript node.js .

Текущее крупное мероприятие - это проект по изучению грамматики и морфологии новых языков с использованием алгоритмов обучения без учителя.

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

Приложения

AbiWord проверяет грамматику с помощью Link Grammar

AbiWord , бесплатный текстовый процессор , использует Link Grammar для проверки грамматики на лету. Слова, которые нигде не могут быть связаны, подчеркнуты зеленым.

Средство извлечения семантических отношений RelEx, расположенное поверх библиотеки Link Grammar, генерирует выходные данные грамматики зависимостей , делая явными семантические отношения между словами в предложении. Его результат можно классифицировать как находящийся на уровне между SSyntR и DSyntR теории смыслового текста . Он также обеспечивает кадрирование / заземление, разрешение анафоры , идентификацию заглавного слова, лексическое разбиение , идентификацию части речи и теги, включая теги сущностей, даты, денег, пола и т. Д. Она включает в себя режим совместимости , чтобы генерировать выходной сигнал зависимостей , совместимый с анализатором Стэнфордского и Пенна Treebank -Совместимости POS мечения .

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

Словарь ссылок Link Grammar используется для генерации и проверки синтаксической правильности трех различных систем генерации естественного языка : NLGen, NLGen2 и microplanner / surreal. Он также используется как часть конвейера NLP в проекте OpenCog AI.

Примечания

дальнейшее чтение

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

Расширения языка