Из Википедии, бесплатной энциклопедии
  (Перенаправлено из Link Grammar )
Перейти к навигации Перейти к поиску

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

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

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

Обзор [ править ]

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

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

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

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

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

Алгоритм разбора [ править ]

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

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

Зависимость [ править ]

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

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

Планарность [ править ]

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

Стоимость и выбор [ править ]

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

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

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

Теория типов [ править ]

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

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

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

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

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

Примеры [ править ]

Пример 1 [ править ]

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

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

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

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

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

Пример 2 [ править ]

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

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

И простое персидское предложение man 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 ---- + | | | | | |ЛЕВАЯ СТЕНА that.jp является абстрактным понятием.

Здесь соединитель «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» - «Вчерашняя вечеринка имела большой успех» можно разобрать следующим образом: [28]

Реализации [ править ]

Синтаксис ссылка грамматики синтаксический анализатор является библиотека для обработки естественного языка , написанной в C . Доступен по лицензии LGPL . Синтаксический анализатор [30] - это постоянный проект. Последние версии включают улучшенный охват предложений, поддержку русского, персидского и арабского языков, прототипы для немецкого, иврита, литовского, вьетнамского и турецкого языков, а также программные API для Python , Java , Common LISP , AutoIt и OCaml со сторонними привязками для Perl , [31] Ruby [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] и microplanner / surreal. [48] Он также используется как часть конвейера NLP в проекте OpenCog AI.

Заметки [ править ]

  1. ^ a b Link Грамматика Библиография
  2. ^ Анси Юли-Jyrä & Матти Нюкянен (2004). «Иерархия слабо контекстно-зависимых грамматик зависимостей» (PDF) . В GP Герхард Ягер, Паола Монахези и С. Винтнер (ред.). Материалы 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. ^ a b c d e Введение в синтаксический анализатор грамматики ссылок
  11. ^ Деннис Гринберг, Джон Лафферти, Дэниел Слейтор, «Надежный алгоритм синтаксического анализа для грамматики ссылок», технический отчет Университета Карнеги-Меллона по компьютерным наукам CMU-CS-95-125 и Труды Четвертого международного семинара по технологиям синтаксического анализа, Прага (1995) [2]
  12. ^ Havelka, J. (2007). «Вне проекции: многоязычная оценка ограничений и мер на непроективные структуры». В: Материалы 45-го ежегодного собрания Ассоциации компьютерной лингвистики (ACL-07): 608-615. Прага, Чешская Республика: Ассоциация компьютерной лингвистики.
  13. ^ Р. Феррер и Канчо "Почему синтаксические ссылки не пересекаются?" EPL 76, 6 (2006), стр. 1228-1234.
  14. ^ Джон Лафферти, Дэниел Слейтор, Дэйви Темперли, «Грамматические триграммы: вероятностная модель грамматики ссылок» Труды конференции AAAI по вероятностным подходам к естественному языку (1992) [3]
  15. ^ Рамон Феррер-и-Канчо (2013) "Hubiness, длина, пересечения и их отношения в деревьях зависимости", ArXiv 1304.4086
  16. ^ D. Temperley (2008). «Минимизация длины зависимостей в естественных и искусственных языках». Журнал количественной лингвистики , 15 (3): 256-282.
  17. ^ Э. Гибсон, (2000). «Теория зависимости локальности: дистанционная теория языковой сложности». В Marantz, A., Miyashita, Y., и O'Neil, W., редакторы Image, Language, Brain. Материалы первого симпозиума проекта Mind Articulation Project . MIT Press, Кембридж, Массачусетс.
  18. ^ Хайтао Лю " Расстояние зависимости как показатель сложности понимания языка ", 2008, Journal of Cognitive Science , v 9.2, стр. 159-191.
  19. ^ Ричард Футрелл, Кайл Маховальд и Эдвард Гибсон, «Крупномасштабные доказательства минимизации длины зависимостей на 37 языках» (2015), ‹См. Tfd› doi : 10.1073 / pnas.1502134112
  20. ^ Дэниел Слейтор, Дэйви Темперли, "Анализ английского языка с помощью грамматики ссылок", Третий международный семинар по технологиям синтаксического анализа (1993) [4] ( См. Раздел 6 о категориальной грамматике. )
  21. ^ Кэрол Лю. « На пути к Link Grammar для китайского языка. » Компьютерная обработка китайских и восточных языков - Журнал китайского языка Computer Society. (2001)
  22. ^ Джон Dehdari, Deryle Lonsdale, " Ссылка Грамматика для персидской ", (2005) [5]
  23. ^ Armin Sajadi, Abdollahzadeh, A., " фарси анализ Синтаксический с помощью Link Grammar в архив 2014-04-01 на Wayback Machine " (на фарси), Письмо Научно - исследовательского центра интеллектуальной обработки сигнала , Vol 1 (9), 25-37 (На фарси), 2006.
  24. ^ Саджади, А., Хомайунпур, М. «Представление морфологических знаний фарси с использованием грамматики ссылок» (на фарси), Письмо Исследовательского центра интеллектуальной обработки сигналов, Том 1 (9), 41-55, 2006.
  25. ^ Уоррен Casbeer, Джон Dehdari и Deryle Lonsdale « Ссылка Грамматик парсер для арабского » в Перспективах на арабской лингвистике: материалы из ежегодного симпозиума по арабской лингвистике. Том XX: Каламазу, Мичиган, март 2006 г. , изд. Мустафа А. Мугхази (2006)
  26. ^ Документация по связям и по классам слов доступна.
  27. ^ Грамматика связей (Link Grammar)
  28. Nguyễn Thị Thu Hng, Nguyễn Thúc Hải, Nguyn Thanh Thủy « Комплекс синтаксического анализа - составные предложения с расширением вьетнамского синтаксического анализатора ссылок в сочетании с сегментатором дискурса » Journal of Computer Science and Cybernetics , Vol 28 , No 4 (2012)
  29. ^ www .abisource .com / downloads / link-grammar /
  30. ^ Lingua-LinkParser (интерфейсы Perl)
  31. ^ "Интерфейсы Ruby Link Parser" . Архивировано из оригинала на 2016-03-04 . Проверено 1 февраля 2019 .
  32. ^ Библиотека javaScript node.js
  33. ^ Изучение языка OpenCog
  34. ^ Изучение языка из большого (без аннотации) корпуса
  35. ^ Debian - Результаты поиска пакетов - грамматика ссылок
  36. ^ "Экстрактор отношений зависимостей RelEx" . Архивировано из оригинала на 2009-07-28 . Проверено 21 ноября 2013 .
  37. ^ The Stanford Parser: статистический анализатор
  38. ^ Пенн Treebank проекта архивации 2013-11-09 в Wayback Machine
  39. ^ Цзин Дин; Даниэль Берлеант; Цзюнь Сюй; Энди В. Фулмер (ноябрь 2003 г.). «Извлечение биохимических взаимодействий из MEDLINE с помощью синтаксического анализатора грамматики ссылок» (PDF) . Труды Пятнадцатого IEEE конференции по инструментам с искусственным интеллектом (ICTAI), 2003 . С. 467–471. ISBN  0-7695-2038-3. Архивировано из оригинального (PDF) 31 марта 2011 года . Проверено 26 сентября 2009 .
  40. ^ Сампо Пийсало, Тапио Салакоски, Софи Обин и Аделина Назаренко, « Лексическая адаптация грамматики ссылок на биомедицинский подъязык: сравнительная оценка трех подходов », BMC Bioinformatics 7 (Suppl 3): S2 (2006).
  41. ^ Харша В. Мадхьястха; Н. Балакришнан; К.Р. Рамакришнан (2003). «Извлечение информации о событиях с использованием грамматики ссылок». 13-й международный семинар по вопросам исследований в области инженерии данных: многоязычное управление информацией (RIDE'03) . п. 16. DOI : 10,1109 / RIDE.2003.1249841 .
  42. ^ Тегух Бхарата Аджи; Бахарум Бахарудин; Норшухани Замин (2008). «Применение формализма грамматики ссылок в разработке англо-индонезийской системы машинного перевода». Интеллектуальная компьютерная математика, 9-я международная конференция, AISC 2008, 15-й симпозиум, Calculemus 2008, 7-я международная конференция, Бирмингем, Великобритания, Труды . С. 17–23. DOI : 10.1007 / 978-3-540-85110-3_3 .
  43. ^ A.Sajadi и MR Боруджерди, «машинный переводпомощью Link Grammar»,представлен в журнале вычислительной лингвистики , MIT Press (февраль 2009 г.)
  44. ^ Саджади, А., Боруджерди, М. "Машинный перевод на основе грамматики унифицированных ссылок" Журнал обзора искусственного интеллекта . DOI = 10.1007 / s10462-011-9261-7, страницы 109-132, 2013.
  45. ^ Рутинг Лиан и др. , «Генерация предложений для искусственного мозга: подход сопоставления глокального сходства», Neurocomputing (Elsevier) (2009, отправлено для публикации).
  46. ^ Блейк Лемуан, NLGen2: лингвистически правдоподобная, универсальная система генерации естественного языка (2009)
  47. ^ Microplanner и реализация поверхности (SuReal)

Дальнейшее чтение [ править ]

  • Шнайдер, Герольд (1998). «Группа лингвистического сравнения, зависимости и грамматика ссылок» (PDF) . Магистерская диссертация, Цюрихский университет . Проверено 26 декабря 2007 . Cite journal requires |journal= (help)
  • Дэниел Слейтор и Дэви Темперли (1993). «Анализ английского языка с помощью грамматики ссылок» (PDF) . Третий международный семинар по технологиям парсинга .
  • Деннис Гринберг; Джон Лафферти; Дэниел Слейтор (сентябрь 1995 г.). «Надежный алгоритм синтаксического анализа грамматик ссылок» (PDF) . Материалы Четвертого международного семинара по технологиям парсинга .

Внешние ссылки [ править ]

  • Исходная домашняя страница Link Grammar (которая была заменена текущим проектом ).
    • Онлайн-демонстрация английского языка (для более старой, устаревшей версии; многие ошибки были исправлены с момента выхода этой версии).
  • BioLG , модификация Link Grammar Parser, адаптированная для биомедицинской области (многие, но не все, улучшения BioLG были возвращены в основной дистрибутив грамматики ссылок).
  • Разбор предложений с Link Grammar и Python на Джеффа Элмор на PyCon 2012

Расширения языка [ править ]

  • Расширение Arabic Link Grammar ( исходный код )
  • Расширение Persian Link Grammar
  • Онлайн-демонстрация на персидском языке
  • Демонстрация грамматики Russian Link
  • Расширение Turkish Link Grammar разработано как магистерская диссертация