Что такое дерево зависимости

Синтаксический компонент лингвистического процессора ея.

Модели представления синтаксической структуры предложения.

Деревья зависимостей.

Деревья зависимостей — наиболее наглядный и наиболее распростра­ненный способ представления синтаксической структуры предложения. При этом предложение представляется как линейно упорядоченное множество элементов (словоформ), на котором можно задать ориентированное дерево (узлы — элементы множества). Каждая дуга, связывающая пару узлов, интерпретируется как подчинительная связь между двумя элементами, направление которой соответствует направлению данной дуги. Множество всех узлов дерева, прямо или косвенно зависящих от какого-либо узла, включая сам этот узел, составляет группу зависимости этого узла. Проективность — важное свойство древовидных структур, отражающее связь между отношением линейного порядка и отношением подчинения. Деревья зависимостей называются проективными, если для любого узла группа зависимости этого узла является неразрывным отрезком предложения. Проективность предложения легко определяется при графическом изображении дерева зависимостей. При этом на плоскости рисунка выбирается прямоугольная система координат (ось ординат направлена сверху вниз). Узлы дерева (слова предложения) изображаются целочисленными точками плоскости: абсцисса узла — порядковый номер слова в предложении, ордината — высота слова в дереве. При таком способе изображения предложение проективно, если дуги дерева не пересекаются с вертикалями, проведенными из узлов (сверху вниз), и между собой. Различаются проективные и слабопроективные деревья зависимостей. Дерево зависимости проективно, если для любых трех его узлов a, b, c из того, что b зависит от a, и c лежит между ними, следует, что c зависит от a или от b. Дерево зависимости слобопроективно, если для любых его четырех узлов a, b, c, d из того, что b зависит от a, и d зависит от c следует, что пары a, b и c, d не разделяют друг друга (т.е. любые два интервала (при линейном изображении дерева зависимостей) либо не пересекаются, либо один из них содержится в другом). Пример непроективного предложения: «Я памятник себе воздвиг нерукотворный». Я памятник себе воздвиг нерукотворный Пример слабопроективного предложения: «Этому человеку мы будем обязаны всю жизнь». Этому человеку мы будем обязаны всю жизнь В деловой прозе деревья зависимостей подавляющего большинства предложений проективны. За исключением некоторых особых случаев непроективность предложений в деловом тексте — верный признак недостаточной грамотности автора (хотя в художественной литературе, особенно в поэзии, отклонения от проективности вполне обычны). Недостатки способа представления синтаксических структур в виде деревьев зависимостей: 1) жесткое требование рассматривать каждое формально выделенное вхождение слова в качестве отдельного элемента предложения; 2) все без исключения связи между словоформами трактуются как подчинительные.

Источник

Русские Блоги

Подробное объяснение анализатора зависимостей на основе переходов

Источник: Семинар выходного дня Лаборатории обработки естественного языка Хэйлунцзянского университета

Следующая картина принадлежит брату Ю Нань.

Что такое дерево синтаксиса зависимостей

Дерево синтаксиса зависимостей представляет отношения зависимости между словами в предложении, как показано ниже.

Дуга перед двумя словами указывает на то, что эти два слова имеют зависимую связь. Метка на дуге — это связь между ними. Начальной точкой дуги является родительский узел, а стрелка указывает на дочерний узел. Например, The и fox — это существительные фразы артикля + существительное (det).

За исключением одного слова, корневого узла (здесь произошел переход), все остальные слова имеют слова в качестве родительского узла, а родительский узел корневого узла (перемещен) является корневым.

Но обратите внимание, что дерево синтаксиса зависимостей не допускает пересечений или петель между дугами!

Представление данных дерева синтаксиса зависимостей

Формат текстового представления дерева синтаксиса зависимостей — это формат conll, как показано в таблице.

Синтаксическое дерево зависимостей может быть восстановлено на основе индекса родительского узла таблицы и соответствующей связи дуги. Где -1 означает корневой узел.

Использование дерева синтаксиса зависимостей

Обычно мы интегрируем функции синтаксиса зависимостей в другие модели задач, такие как машинный перевод, анализ мнений, анализ текста и т. Д., И, как правило, получаем лучшую производительность.

Тогда как получить синтаксическую особенность зависимости? Обычно есть два метода:

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

Что такое структура, основанная на переходе?

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

Используемое для создания дерева синтаксиса зависимостей, оно конкретно выражается как начало с пустого состояния, переход к следующему состоянию с помощью действий и пошаговое генерирование дерева синтаксиса зависимостей, а в конечном состоянии сохраняется полное дерево зависимостей. Анализ зависимостей используется для прогнозирования взаимосвязи между словами, и теперь он переходит к прогнозированию последовательности действий. В структуре на основе передачи мы определяем 4 действия (чем меньше элемент на вершине стека, тем ближе к вершине стека):

• Shift: первый элемент q0 очереди извлекается из стека и помещается в стек, чтобы стать s0.
• Левый статут (arc_left_l): два элемента s1 и s0 наверху стека являются статутами. S1 опускается, чтобы стать левым дочерним узлом s0, а l — это отношение верхней дуги.
• Правый статут (arc_right_l): два элемента s1 и s0 наверху стека являются статутами. S0 опускается, чтобы стать правым дочерним узлом s1, а l — это отношение верхней дуги.
• Pop root (pop_root): корневой узел выскакивает из стека, и анализ завершается.

0 тонет, визуальный эффект можно увидеть как ребенка 1

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

Конкретные примеры перехода на основе перехода

В качестве примера возьмем приведенное выше дерево зависимостей:

Набор последовательностей действий (золотые метки, обучающие данные) для анализа зависимостей становится:

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

Поскольку в левом стеке есть элемент 0, его можно сдвинуть только в:

На данный момент в стеке 2 элемента, сейчас мы смотрим на дерево зависимостей

Между 0 и 1 нет дуги, и сокращение не может быть выполнено, поэтому мы можем только сдвигать:

Теперь посмотрите на два элемента в верхней части стека и обнаружите, что существует связь между 1 и 2 в дереве зависимостей.

А 1 является дочерним элементом 2, поэтому действие в это время — левое правило arc_left, 1 тонет и дочернее правило 2. Все дерево зависимостей может быть восстановлено согласно последовательности действий, конечно, для удобства следующей операции), на этот раз метка amod:

В это время стек равен 0, 2, снова проверьте дерево зависимостей

Было обнаружено, что существует зависимость между 0 и 2, где 0 является дочерним по отношению к 2, поэтому в это время операция остается статутной, а метка — det

Я пропускаю некоторые шаги в середине, потому что все они одинаковы, на этот раз я расскажу о шаге 9.：

В стеке теперь 3 и 4, проверьте дерево зависимостей

Согласно нормальному режиму работы в это время должен использоваться правый протокол arc_right, но если он равен 4, он утонет и исчезнет. И через некоторое время нужно положить 5 в стек, а затем я смотрю на дерево зависимостей и обнаруживаю, что 4 — это мой собственный отец, мой Бог, отец пятерых детей ушел, не может быть найден, исчез, другими словами, есть отцы, но у 5 нет отца, есть больше, чем это Несчастный? Это не будет отправлять больше операций! Следовательно, существует скрытое правило: если операция заключается в выполнении arc_right над верхним элементом стека, операция не выполняется и выбирается shift.

А вы спросите, у arc_left такая проблема? Нет, например, 3 и 4 выполняют операции arc_left, а приемники — 3. Если родительский узел в правой очереди равен 3, это означает, что в дереве зависимостей есть крест или цикл! Это невозможно, потому что дерево зависимостей не допускает пересечений или циклов! (Если не верите, попробуйте нарисовать самостоятельно)

Наконец, операция pop root pop_root может произойти только в конце

Данные в правом нижнем углу — это отношение между словами. Это отношение зависимости (отец, ребенок, отношение), созданное в соответствии с последовательностью действий. В соответствии с отношением оно может быть восстановлено до исходного дерева зависимостей.

Модель нейронной сети

Мы используем нейронную сеть для извлечения признаков, которая разделена на 2 части:

Сторона кодирования: Используется для вычисления скрытого векторного представления слов

Декодер: Используется для декодирования и вычисления оценок всех действий в текущем состоянии.

Сторона кодирования

Мы используем Bi-LSTM для кодирования предложения

, Рассчитайте соответствующее представление скрытого слоя

Среди них ei — вектор слов, pi — вектор части речи, а символ между e и p — склейка векторов.

• ei — это вложение слова, которое мы обычно используем
• пи — это часть речи, например NN, VV, VP и т. д. Операция обработки его как слова такая же, как и использование его собственного вложения (не то же самое, что вложение слова!).
• Символ между ними — это векторное сращивание, которое можно сращивать, объединять или добавлять. Попробуйте, какой эффект подойдет вам, мертвого правила нет. И здесь мы используем cat.

Декодер должен оценивать все действия для каждого состояния. Согласно опыту, три верхних элемента стека и первый элемент очереди считаются ключевыми характеристиками прогнозирования действий, поэтому три верхних элемента s0, s1, s2 (чем меньше нижний индекс, тем ближе к верху стека) и первый элемент очереди q0 соединяются. Затем используйте линейное преобразование, чтобы подсчитать оценку каждого действия:

Прогноз модели

Выполните вероятностную оценку Softmax для оценки каждого действия, а затем введите ее в кросс-энтропию в качестве целевой функции. Затем используйте Adam, чтобы обновить параметры модели, чтобы минимизировать целевую функцию:

Среди них Pag — это вероятность последовательности действий золотой метки, а theta — это параметр модели.

Рекомендовать бумагу

Transition-based Neural RST Parsing with Implicit Syntax Features

Nan Yu, Meishan Zhang and Guohong Fu

Joint POS Tagging and Dependency Parsing with Transition-based Neural Networks.

Liner Yang, Meishan Zhang, Yang Liu, Nan Yu, Maosong Sun, Guohong Fu.

Simple and Accurate Dependency Parsing Using Bidirectional LSTM Feature Representations

Eliyahu Kiperwasse, Yoav Goldberg

Integrating Graph-Based and Transition-Based Dependency Parsers

JoakimNivre, Ryan McDonald

Источник