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

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

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

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

Обзор

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

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

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

    + ----> WV ---> + + - Wd - + - Ss - + - Pa - + | | | | ЛЕВАЯ СТЕНА он быстро бегает

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

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

Парсинг выполняется аналогично сборке пазл (представляющий проанализированное предложение) из кусочков головоломки (представляющих отдельные слова).[9][10] Язык представлен с помощью словаря или лексика, который состоит из слов и набора разрешенных «фигур пазла», которые может иметь каждое слово. Форма обозначена «соединителем», который является звеном, и указателем поворота. + или же - с указанием вправо или влево. Так, например, переходный глагол может иметь разъемы S- & O + указывая, что глагол может образовывать подлежащее ("S") соединение слева от него ("-") и объектное соединение ("О") справа от него ("+"). Аналогично, a имя нарицательное может иметь разъемы D- & S + указывая, что он может подключаться к определитель слева ("D-") и действовать как подлежащее при соединении с глаголом справа ("S +"). Затем выполняется анализ, чтобы определить, что S + разъем можно прикрепить к S- соединитель, образующий "S"связь между двумя словами. Анализ завершается, когда все соединители подключены.

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

Зависимость

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

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

Планарность

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

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

Разъемы могут иметь дополнительный плавающая точка наценка, так что некоторые из них «дешевле» в использовании, чем другие, что дает предпочтение определенным синтаксическим анализам перед другими.[10] То есть общая стоимость синтаксического анализа - это сумма индивидуальных затрат на использованные соединители; самый дешевый синтаксический анализ указывает наиболее вероятный синтаксический анализ. Это используется для ранжирования нескольких неоднозначных синтаксических анализов. Тот факт, что затраты являются локальными для соединителей и не являются глобальным свойством алгоритма, делает их существенно Марковский в природе.[14][15][16][17][18][19]

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

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

Теория типов

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

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

: D +; плохо: A +; мальчик: D- и A-;

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

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

Примеры

Пример 1

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

<определитель> D +; <существительное-субъект> {D−} & S +; <существительное-объект> {D−} & O−;  S− & {O +};

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

           + ----- O ----- + + -D - + - S - + + - D - + | | | | | Мальчик нарисовал картину

Подобные разборы применимы и к китайскому языку.[21]

Пример 2

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

<существительное-предмет> S +; <существительное-объект> O +;  {O−} & {S−};

И простой Персидский приговор, человек nAn xordam (من نان خوردم) «Я ел хлеб» будет выглядеть так:[22][23][24]

 + ----- S ----- + | + - O - + | | | человек nAn xordam

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

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

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

    + ------------ Wd ----------- + --------------- SIp -------- ------- + | + ------- EI ------ + + -------- Api ------- + | | + - LLCZD- + + -LLAQZ + + - LLCAO- + | | | | | | | | ЛЕВАЯ СТЕНА вверху.e плы. = = Ли.vnndpp ре. = = Дкие.api облачк. = = А.ndnpi

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

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

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

                     + --------- Ост -------- + + ------> WV ------> + + ------ Ds ** x-- --- + + ---- Wd --- + - Ss * b- + + - PHv - + ---- A ---- + | | | | | | ЛЕВАЯ СТЕНА, что j-p является абстрактным понятием. N

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

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

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

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

Реализации

Link Парсер грамматики
Разработчики)OpenCog
изначальный выпускОктябрь 1991 г.; 29 лет назад (1991-10)[1]
Стабильный выпуск
5.5.1 / 27 июля 2018 г.; 2 года назад (2018-07-27)[29]
Репозиторий
Отредактируйте это в Викиданных
Написано вC ++; изначально C
Операционная системаКроссплатформенность
ПлатформаGNU
ТипНЛП
ЛицензияLGPLv2
Интернет сайтwww.abisource.com/ проекты/ ссылка-грамматика/

Синтаксис грамматики ссылок парсер это библиотека за обработка естественного языка написано в C. Он доступен под Лицензия LGPL. Парсер[30] это текущий проект. Последние версии включают улучшенное покрытие предложений, поддержку русского, персидского и арабского языков, прототипы для немецкого, иврита, литовского, вьетнамского и турецкого языков, а также программные API для Python, Ява, Общий LISP, AutoIt и OCaml, со сторонними привязками для Perl,[31] Рубин[32] и JavaScript node.js.[33]

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

В линк-парсер программу вместе с правилами и списками слов для английского языка можно найти в стандартном Дистрибутивы Linux, например, как Debian пакет, хотя многие из них уже давно устарели.[36]

Приложения

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

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

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

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

Словарь ссылок Link Grammar используется для генерации и проверки синтаксической правильности трех различных генерация естественного языка системы: NLGen,[46] NLGen2[47] и микропланнер / сюрреалистический.[48] Он также используется как часть конвейера НЛП в OpenCog Проект AI.

Примечания

  1. ^ а б Ссылка Грамматика Библиография
  2. ^ Ансси Юли-Юра и Матти Нюкянен (2004). «Иерархия слабо контекстно-зависимых грамматик зависимостей» (PDF). В издании Г. П. Герхарда Ягера, Паолы Монахези и С. Винтнера. Материалы 9-й конференции по формальной грамматике 2004 "FGNancy". Предварительные слушания. С. 151–165.
  3. ^ Озлем Истек, "Грамматика ссылок для турецкого языка ", Диссертация, Билькентский университет, Анкара, Турция (2006 г.)
  4. ^ Lietuvi Kalbos Gramatika
  5. ^ Тип ссылки WV
  6. ^ Тип звена W
  7. ^ Тип связи S
  8. ^ Тип связи P
  9. ^ Дэниел Д. К. Слейтор, Дэви Темперли, «Анализ английского языка с помощью грамматики ссылок» Технический отчет по информатике Университета Карнеги-Меллона CMU-CS-91-196 (1991) [1] (ArXiv)
  10. ^ а б c d е Введение в синтаксический анализатор грамматики ссылок
  11. ^ Деннис Гринберг, Джон Лафферти, Дэниел Слейтор, «Надежный алгоритм синтаксического анализа для грамматики ссылок», Технический отчет по информатике Университета Карнеги-Меллона CMU-CS-95-125, и Материалы Четвертого международного семинара по технологиям парсинга, Прага (1995) [2]
  12. ^ Гавелка, Дж. (2007). «Вне проекции: многоязычная оценка ограничений и мер на непроективные структуры». В: Материалы 45-го Ежегодного собрания Ассоциации компьютерной лингвистики (ACL-07): 608-615. Прага, Чешская Республика: Ассоциация компьютерной лингвистики.
  13. ^ Р. Феррер и Канчо "Почему синтаксические ссылки не пересекаются?" EPL 76, 6 (2006), стр. 1228-1234.
  14. ^ Джон Лафферти, Дэниел Слейтор, Дэйви Темперли, «Грамматические триграммы: вероятностная модель грамматики ссылок» Труды конференции AAAI по вероятностным подходам к естественному языку (1992)[3]
  15. ^ Рамон Феррер-и-Канчо (2013 г.) «Hubiness, длина, пересечения и их отношения в деревьях зависимости», ArXiv 1304.4086
  16. ^ Д. Темперли, (2008). «Минимизация длины зависимостей в естественных и искусственных языках». Журнал количественной лингвистики, 15(3):256-282.
  17. ^ Э. Гибсон, (2000). «Теория локальности зависимости: дистанционная теория языковой сложности». В Marantz, A., Miyashita, Y., и O'Neil, W., редакторы, Изображение, язык, мозг. Материалы первого симпозиума по проекту «Артикуляция разума». MIT Press, Кембридж, Массачусетс.
  18. ^ Хайтао Лю "Расстояние зависимости как показатель сложности понимания языка ", 2008, Журнал когнитивной науки, v9.2 С. 159-191.
  19. ^ Ричард Футрелл, Кайл Маховальд и Эдвард Гибсон, «Крупномасштабные доказательства минимизации длины зависимостей на 37 языках» (2015), Дои:10.1073 / pnas.1502134112
  20. ^ Дэниел Слейтор, Дэйви Темперли, «Анализ английского языка с помощью грамматики ссылок» Третий международный семинар по технологиям парсинга (1993) [4] (См. Раздел 6 о категориальной грамматике.)
  21. ^ Кэрол Лю. "На пути к грамматике ссылок для китайского языка. " Компьютерная обработка китайских и восточных языков - Журнал компьютерного общества китайского языка. (2001)
  22. ^ Джон Дехдари, Дерил Лонсдейл "Грамматика ссылок для персидского языка ", (2005)[5]
  23. ^ Армин Саджади, Абдоллахзаде, А. "Синтаксический анализ фарси с использованием грамматики ссылок В архиве 2014-04-01 на Wayback Machine "(На фарси), Письмо Исследовательского центра интеллектуальной обработки сигналов, Об. 1(9), 25-37 (на фарси), 2006.
  24. ^ Саджади, А., Хомаюнпур, М. «Представление морфологических знаний фарси с использованием грамматики ссылок» (на фарси), Письмо Исследовательского центра интеллектуальной обработки сигналов, том 1 (9), 41-55, 2006.
  25. ^ Уоррен Касбер, Джон Дехдари и Дерил Лонсдейл " Синтаксический анализатор грамматики для арабского языка " в Перспективы арабской лингвистики: доклады ежегодного симпозиума по арабской лингвистике. Том XX: Каламазу, Мичиган, март 2006 г., Ред. Мустафа А. Мугхази (2006)
  26. ^ Документация по связям и по классам слов доступен.
  27. ^ Грамматика связей (Link Grammar)
  28. ^ Nguyn Thị Thu Hng, Nguyễn Thúc Hải, Nguyn Thanh Thủy "Комплекс синтаксического анализа - составные предложения с расширением вьетнамского парсера ссылок в сочетании с сегментером дискурса " Журнал компьютерных наук и кибернетики, Об. 28, № 4 (2012)
  29. ^ www.abisource.com/ загрузки/ ссылка-грамматика/
  30. ^ Lingua-LinkParser (интерфейсы Perl)
  31. ^ "Интерфейсы Ruby Link Parser". Архивировано из оригинал на 2016-03-04. Получено 2019-02-01.
  32. ^ библиотека javaScript node.js
  33. ^ Изучение языка OpenCog
  34. ^ Изучение языка из большого (неаннотированного) корпуса
  35. ^ Debian - Результаты поиска пакетов - грамматика ссылок
  36. ^ "Экстрактор отношений зависимостей RelEx". Архивировано из оригинал на 2009-07-28. Получено 2013-11-21.
  37. ^ Стэнфордский парсер: статистический парсер
  38. ^ Проект Penn Treebank В архиве 2013-11-09 в Wayback Machine
  39. ^ Цзин Дин; Даниэль Берлеант; Цзюнь Сюй; Энди У. Фулмер (ноябрь 2003 г.). «Извлечение биохимических взаимодействий из MEDLINE с помощью парсера грамматики ссылок» (PDF). Труды пятнадцатой конференции IEEE по инструментам с искусственным интеллектом (ICTAI), 2003 г.. С. 467–471. ISBN  0-7695-2038-3. Архивировано из оригинал (PDF) на 2011-03-31. Получено 2009-09-26.
  40. ^ Сампо Пийсало, Тапио Салакоски, Софи Обен и Аделина Назаренко "Лексическая адаптация грамматики ссылок к биомедицинскому подъязыку: сравнительная оценка трех подходов ", BMC Bioinformatics 7(Приложение 3): S2 (2006).
  41. ^ Харша В. Мадхьястха; Н. Балакришнан; К. Р. Рамакришнан (2003). «Извлечение информации о событиях с использованием грамматики ссылок». 13-й международный семинар по вопросам исследований в области инженерии данных: многоязычное управление информацией (RIDE'03). п. 16. Дои:10.1109 / RIDE.2003.1249841.
  42. ^ Тегух Бхарата Аджи; Бахарум Бахарудин; Норшухани Замин (2008). «Применение формализма грамматики ссылок в разработке англо-индонезийской системы машинного перевода». Интеллектуальная компьютерная математика, 9-я международная конференция, AISC 2008, 15-й симпозиум, Calculemus 2008, 7-я международная конференция, Бирмингем, Великобритания, Труды. С. 17–23. Дои:10.1007/978-3-540-85110-3_3.
  43. ^ A.Sajadi и M.R Borujerdi, «Машинный перевод с использованием грамматики ссылок», представленный в Журнал компьютерной лингвистики, MIT Press (февраль 2009 г.)
  44. ^ Саджади, А., Боруджерди, М. «Машинный перевод на основе грамматики Unification Link» Обзор журнала искусственного интеллекта. DOI = 10.1007 / s10462-011-9261-7, страницы 109-132, 2013.
  45. ^ Рутинг Лиан, и другие, «Генерация предложений для искусственного мозга: подход сопоставления глокального сходства», Neurocomputing (Elsevier) (2009, отправлено для публикации).
  46. ^ Блейк Лемуан, NLGen2: лингвистически правдоподобная универсальная система генерации естественного языка (2009)
  47. ^ Microplanner и Реализация поверхности (SuReal)

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

внешняя ссылка

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