Оригинальная ссылка:

godweiyang.com/2019/08/15/…

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

вводить

Синтаксический анализ компонентов достиг быстрого развития в последние годы, особенно после появления глубокого обучения, эффект нейронного анализа значительно улучшился. Вообще говоря, синтаксический анализатор можно разделить на две части: модель кодирования и модель декодирования. Модель кодирования используется для получения контекстного представления каждого слова в предложении.С быстрым развитием обучения представлению модель кодирования постепенно эволюционировала от исходного LSTM до преобразователя с более сильным представлением (VaswaniSPUJGKP17). С точки зрения моделей декодирования также родилось множество различных типов алгоритмов декодирования, например, основанных насистема передачи(на основе переходов) алгоритм декодирования (WatanabeS15, CrossH16, LiuZ17a), на основединамическое программирование(на основе диаграммы) алгоритм декодирования (SternAK17, KleinK18) и на основепоследовательность за последовательностью(последовательный) алгоритм декодирования (BengioSCJLS18, Gomez-Rodriguez18)и т.д.

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

Модель синтаксического анализа, основанная на динамическом программировании, в основном рекурсивно предсказывает подфразу с наивысшим баллом каждой фразы и, наконец, восстанавливает оптимальное синтаксическое дерево путем возврата. Преимущество состоит в том, что все синтаксические деревья в пространстве поиска могут быть пронумерованы, а эффект декодирования лучше. Однако алгоритм динамического программирования требует много времени, а сложность — квадратный уровень длины предложения. Поэтому ввиду этого недостатка предлагается приближенный алгоритм жадного декодирования сверху вниз (SternAK17), поиск в соответствии с предварительным порядком обхода синтаксического дерева, что может значительно увеличить скорость декодирования без потери производительности.

Основная идея модели синтаксического анализа, основанной на последовательности-последовательности, состоит в том, чтобы отобразить синтаксическое дерево в уникальное соответствующее представление последовательности, а затем использовать аннотацию последовательности (Gomez-Rodriguez18) или генерация последовательности (VinyalsKKPSH15), чтобы предсказать последовательность. Существует также много различных вариантов модели, в зависимости от того, как определена сериализация синтаксического дерева. Преимущество этого типа модели в том, что она чрезвычайно быстра, поскольку временная сложность также является линейной, а количество параметров модели намного меньше, чем у модели, основанной на системе переноса. Недостатки также очевидны, потому что прогнозируемая последовательность должна иметь сильные ограничения, иначе она не может гарантировать восстановление полного синтаксического дерева, поэтому конечный эффект не так идеален, как в предыдущих двух моделях.

Кроме того, существует много других типов алгоритмов декодирования, таких как прямое использование нейронных сетей для прогнозирования вероятности генерирования грамматики, имитация контекстно-свободных грамматик и, наконец, использование традиционных алгоритмов CKY для декодирования (TengZ18). В итоге модель также добилась очень хороших результатов, превзойдя несколько предыдущих моделей на одной модели.

Компонентный синтаксический анализ может применяться ко многим последующим задачам.Например, в задачах анализа тональности древовидный LSTM (Tree-LSTM) можно использовать для моделирования синтаксического дерева предложения, чтобы проанализировать тональность предложения (ZhuSG15). Его можно применять и к другим базовым задачам, например, синтаксическое дерево обученного компонента можно преобразовать в синтаксическое дерево зависимостей по правилам, тем самым повысив точность синтаксического анализа зависимостей (Gildea04).

определение задачи

Синтаксический анализ компонентов является фундаментальной задачей обработки естественного языка, и его задача состоит в том, чтобы датьприговор $(w_0, w_1, \ldots, w_{n-1})$ , анализировать синтаксическое дерево структуры фразы предложения. Например, для предложения «Маленький мальчик любит красные помидоры» составляющее его синтаксическое дерево показано на рисунке 1.

图1：句子“The little boy likes red tomatoes .”对应的句法树。

Для синтаксических деревьев, существует несколько способов его представления. В настоящее время наиболее часто используемое представление основано на интервале (span) (CrossH16), то есть представить синтаксическое дерево как совокупность всех составляющих его словосочетаний. И для каждой фразы можно использовать тройку $(i, j, \ell)$ представить его, гдеиУказывает, что фраза состоит из слова w_i прибыть w_j ,и $\ell$ Нетерминальная метка, представляющая эту фразу. такое синтаксическое деревоможно представить в виде тройки $(i, j, \ell)$ Коллекция:

T = \{(i, j, \ell) | (i, j, \ell) \in T\}.

Таким образом, задача прогнозирования синтаксических деревьев может быть преобразована в прогнозирование троек. $(i, j, \ell)$ Собран.

Конечно, обычно есть две небольшие проблемы: во-первых, что если есть унарная продукция? Одно из решений состоит в том, чтобы объединить все нетерминальные символы над унарной продукцией в новый нетерминальный символ, чтобы всю унарную продукцию можно было рассматривать как нетерминальный символ. Другая проблема заключается в том, что синтаксическое дерево не обязательно должно быть двоичным деревом, поэтому декодирование усложнит многие поиски. Решение состоит в том, чтобы добавить пустой нетерминал $\varnothing$ , преобразовать все недвоичные продукты в несколько двоичных продуктов, в которых все нетерминальные символы вновь добавленного временного узла определяются как этот пустой нетерминальный символ $\varnothing$ , просто игнорируйте его при восстановлении синтаксического дерева.

модель кодирования

вынесенный приговор $(w_0, w_1, \ldots, w_{n-1})$ , целью модели кодирования является получение контекстного представления каждого слова и дальнейшее вычисление векторного представления каждой фразы. В реальной реализации это слово обычно x_i Входной вектор делится на три части. Первый — это соответствующий случайно инициализированный вектор встраивания. e_i . Затем случайно инициализированный вектор встраивания, соответствующий части речи слова p_i , как правило, его часть речи может быть получена с помощью внешнего тега части речи. И, наконец, представление слова на уровне символов c_i , который обычно можно получить с помощью CNN или LSTM на уровне символов. Наконец, вектор из трех частей склеивается, чтобы получить окончательный входной вектор. x_i :

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

LSTM-кодирование

Это наиболее часто используемый метод кодирования, прежде всего x_i Введите двунаправленный LSTM, чтобы получить прямое представление скрытого слоя для каждой позиции. $\overrightarrow h_{i}$ и обратное представление скрытого слоя $\overleftarrow h_{i}$ . тогда по фразе (i, j) , что может быть выражено как:

\boldsymbol{s}_{i j}=\left[\vec{h}_{j}-\vec{h}_{i} ; \overleftarrow h_{i}-\overleftarrow h_{j}\right]

так что вы получаете фразу (i, j) векторное представление $s_{ij}$ , затем он может вычислить свою оценку, а затем использовать модель декодирования для декодирования оптимального синтаксического дерева.

Кодировка трансформатора

Хотя кодирование LSTM используется чаще всего, но если вы хотите спросить, какая модель самая популярная в последнее время, конечно, этоTransformer(VaswaniSPUJGKP17). Он может в полной мере использовать преимущества параллельных вычислений графического процессора для ускорения вычислений. Механизм внимания также можно использовать для улучшения представления предложений.

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

{\rm Attention}(Q, K, V) = {\rm softmax}(\frac{QK^{\top}}{\sqrt{d_k}})V.

Конечно, для улучшения репрезентативности можно также добавить механизм многоголового внимания.Подробности здесь повторяться не будут.Вы можете обратиться к оригинальной статье. Наконец, умножьте результат на матрицу параметров ${\bf W}_O$ Сопоставьте обратно с желаемым выходным измерением, чтобы получить окончательную выходную матрицу., а конкретная структура показана на рисунке 2.

в тексте,,иВсе три матрицы представляют собой матрицы, образованные путем объединения входных векторов предложений., которые умножаются на матрицу параметров соответственно ${\bf W}_Q$ , ${\bf W}_K$ и ${\bf W}_V$ принадлежит. Но следует отметить, что в предыдущем входном векторе x_i На основании необходимо склеить вектор положения каждого слова p_i , иначе матричная операция потеряет информацию о положении слова.

После получения выходной матрицы следующий метод вычисления представления фразы аналогичен кодированию LSTM.

Рекуррентное кодирование нейронной сети

Самое раннее применение рекуррентных нейронных сетей для обработки естественного языка было в (SocherBMN13) предложено в. Хотя рекуррентная нейронная сеть достигла хороших результатов в то время, в последние годы рекуррентная нейронная сеть использовалась редко, в основном из-за таких проблем, как исчезновение градиента и необходимость в синтаксических деревьях, а также ее первоначальное назначение (кодирование информации о древовидной структуре) с помощью рекуррентной нейронной сети. нейронная сеть LSTM. Основам тоже можно научиться, поэтому нет необходимости использовать такую сетевую структуру, которую нельзя распараллелить.

для фраз (i, j) , если два его потомка (i, k) и (k, j) ,Так $s_{ij}$ это можно сделать $s_{ik}$ и $s_{kj}$ Рассчитано:

s_{ij} = f({\bf W}[s_{ik};s_{kj}]+{\bf b}),

в,есть функция активации, которую обычно можно принять как ${\rm tanh}$ .

Конечно, эта структура сейчас редко используется.Более рекурсивной структурой, используемой сейчас, является дерево LSTM.Сетевая структура в основном такая же, как рекуррентная нейронная сеть.Единственное отличие состоит в том, что вычислительный блокЗаменены скрытыми слоями в LSTM, которые могут эффективно решить проблему исчезновения градиента и зависимости от расстояния.

Расчет баллов

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

\begin{aligned} s_{\rm{label}}(i, j, \ell) & = {\bf v}_{\ell}^{\top}f({\bf W}_{\ell}^2f({\bf W}_{\ell}^1s_{ij} + {\bf b}_{\ell}^1) + {\bf b}_{\ell}^2), \\\ s_{\rm{span}}(i, j) & = {\bf v}_s^{\top}f({\bf W}_{s}^2f({\bf W}_{s}^1s_{ij} + {\bf b}_{s}^1) + {\bf b}_{s}^2), \end{aligned} \tag{1}

в– функция активации, которую обычно берут здесь ${\rm ReLU}$ . Здесь мы помещаем фразу (i, j) Партитура разделена на две части, одна из которых является нетерминальной. $\ell$ счет $s_{\rm{label}}(i, j, \ell)$ , часть которого является оценкой за пролет $s_{\rm{span}}(i, j)$ .

Наконец, общая оценка синтаксического дерева определяется как сумма оценки тега и оценки диапазона всех содержащихся в нем фраз:

s_{\rm tree}(T) = \sum\limits_{(i, j, \ell) \in T}{s_{\rm{label}}(i, j, \ell) + s_{\rm{span}}(i, j)}.

Задача модели декодирования, которая будет представлена далее, состоит в том, чтобы найти синтаксическое дерево, имеющее наивысший балл.

Алгоритм декодирования на основе системы переноса

Существует три основных типа моделей декодирования, основанных на системах передачи. Первая представляет собой систему перехода «снизу вверх», вторая — систему перехода «сверху вниз», а последняя — систему перехода на основе обхода по порядку. Общим для этих систем передачи является то, что все они содержат два компонента: один — стек, который используется для хранения проанализированной синтаксической структуры, а другой — буфер, который используется для хранения анализируемых предложений. Древовидная структура прогнозирующего синтаксиса трансформируется в последовательность действий, которые система прогнозирующего переноса должна выполнять в каждый момент времени. Ниже мы вводим несколько различных систем перевода, мы используем тройки [S, B, T] представлять состояние системы передачи в каждый момент времени, представляя верхний элемент стека, первое слово в кеше и конец синтаксического анализа.

система передачи снизу вверх

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

Формальное определение действия восходящей системы передачи показано на рисунке 3, где действие SHIFT заключается в перемещении первого слова из кэша в стек. Действие редукции (REDUCE-L/RX) состоит в том, чтобы извлечь два элемента из верхней части стека и свести их к их родительскому узлу X, а затем поместить родительский узел в стек, а L и R используются для различения левый сын и правый сын, который является головным узлом. Действие Unary-X состоит в извлечении верхнего элемента стека и уменьшении его до родительского узла X. Это действие используется для прогнозирования унарного производства. Действие FINISH используется для определения того, закончился ли синтаксический анализ.

Обратите внимание, что здесь есть проблема: системы передачи снизу вверх обычно заранее бинируют синтаксическое дерево. Основная причина в том, что у восходящей системы есть недостаток, то есть после перемещения внутрь и наружу вы не только должны предсказать, с какого шага начать сокращение, но и сколько элементов в верхней части стека будет сокращено. в случае сокращения Количество состояний сильно увеличивается, что приводит к большому увеличению времени обучения. После бинаризации каждому прогнозу нужно только предсказать, какой шаг сокращения, и каждое сокращение уменьшает только два элемента в верхней части стека.

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

Преимущество восходящей системы передачи состоит в том, что она может полностью использовать информацию о поддереве, которое было сгенерировано, чтобы помочь в нетерминальном предсказании родительского узла. Но очевиден и недостаток, потому что невозможно знать информацию родительского узла и родительского узла верхнего уровня, поэтому теряется много полезной глобальной информации. Другим недостатком является то, что бинаризация должна быть выполнена заранее.Хотя бинаризация добавляет информацию о головке, она оказывается очень полезной, но маркировка головных узлов требует много семантических знаний, что очень трудоемко и занимает много времени. . Более лаконичный способ — использовать пустой узел $\varnothing$ Он представляет собой узел, созданный путем временного объединения двух дочерних узлов в синтаксическом анализе, но не существующий в правильном синтаксическом дереве. Этот пустой узел игнорируется при восстановлении древовидной структуры, так что бинарная операция может выполняться неявно.

система передачи сверху вниз

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

Формальное определение действия нисходящей системы передачи показано на рисунке 5. Действие перемещения такое же, как и раньше, то есть поместить первое слово кэша в стек. Нетерминальное (NT-X) действие состоит в том, чтобы поместить нетерминал X в стек, то есть родительским узлом следующего поддерева является X. Действие редукции состоит в том, чтобы вытолкнуть некоторое количество элементов из вершины стека до родительского узла, который был перемещен в него ранее, а затем уменьшить его до узла и снова поместить в стек. Обратите внимание, что разница между восходящей системой передачи и восходящей системой передачи заключается в том, что действие не завершено.Поскольку восходящая система имеет унарные действия, последний корневой узел может бесконечно уменьшаться, поэтому анализ должен быть прекращается досрочно, завершая действие. Конечно, строгих требований к определению действия передаточной системы нет, и определения в разных работах разные, но все они одинаковы, т. системы также могут быть названы сдвигово-редуцирующими системами.

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

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

Система перехода на основе обхода по порядку

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

Формальное определение действия переходной системы, основанной на обходе по порядку, показано на рис. 7. Действие перехода такое же, как и раньше, и первое слово кэша помещается в стек. Нетерминальное действие карты (PJ-X) состоит в том, чтобы предсказать родительский узел X элемента на текущей вершине стека. Действие редукции заключается в уменьшении нескольких элементов наверху стека до предпоследнего элемента в самом внутреннем, который является их родительским узлом.

Для синтаксического дерева на рис. 1 процесс анализа системы с обходом по порядку показан на рис. 8.

Как правило, когда мы читаем фразу, мы обычно замечаем ее первое слово, а затем можем сделать вывод о типе фразы на основе наблюдаемых слов. Например, когда мы читаем слово «нравится», мы можем предположить, что за словом следует глагольная фраза. И следующее слово «красные помидоры» как раз является объектом этой глагольной фразы. В отличие от систем передачи сверху вниз, локальная информация в «лайках» может иметь решающее значение для распознавания того, что это глагольная фраза. Кроме того, глобальная информация в Verb Phrases (VP) также полезна для последующего прогнозирования.

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

генеративная модель

Все три системы передачи, представленные ранее, являются дискриминационными моделями, и на основе нисходящей системы передачи родилась генеративная модель——Рекуррентная грамматика нейронной сети(РНГ). Грамматики RNN - это, по сути, системы передачи сверху вниз, определения действий и главы.система передачи сверху внизВведение в основном такое же. Просто система переноса сверху вниз, представленная ранее, является дискриминационной моделью, и каждый раз, когда вставляется слово, это правильное слово, данное в кэше. Слова, перемещаемые каждый раз рекуррентной грамматикой нейронной сети, должны быть предсказаны с помощью генерации действий (GEN-X), а окончательная модель анализирует предсказанное предложение для создания синтаксического дерева.

Формальное определение состоит в том, что для предложенияи соответствующее синтаксическое дерево, дискриминантная модель – это условная вероятность p(y | x) модель, в то время как генеративные модели основаны на совместной вероятности p(x, y) модель.

Еще одним важным применением рекуррентной нейросетевой грамматики является языковая модель (language model), то есть моделирование p(x) . так как $p(x) = \sum\nolimits_{y \in \mathcal{Y}(x)} {p(x,y)}$ , так что просто перечислите все возможные синтаксические деревьяЭтого достаточно, но это экспоненциальный уровень, что явно нереально. В это время нужно использовать "Выборка по важности(выборка по важности)» (doucet2009tutorial).

сделать q(y | x) Генерация предложений для грамматик рекуррентных нейронных сетей как дискриминационных моделейУсловная вероятность , тогда p(x) можно переписать как

\begin{aligned} p(x) & = \sum\nolimits_{y \in \mathcal{Y}(x)} {p(x,y)} \\\ & = \sum\nolimits_{y \in \mathcal{Y}(x)} {q(y|x)w(x,y)} \\\ & = {\mathbb {E}_{q(y|x)}}w(x,y), \end{aligned}

в w(x,y)=p(x,y)/q(y|x) . Затем вы можете использовать метод Монте-Карло для выборки из распределения q(y | x) выборка средыобразцы:

{y^{(i)}} \sim q(y|x),i = 1,2, \ldots ,N.

Так p(x) Его можно аппроксимировать следующим образом:

\begin{aligned} p(x) & = {\mathbb{E}_{q(y|x)}}w(x,y) \\\ & \mathop \approx \limits^{\rm MC} \frac{1}{N}\sum\limits_{i = 1}^N {w(x,{y^{(i)}})}. \end{aligned}

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

Алгоритм декодирования на основе динамического программирования и его вариантов

Этот класс алгоритмов декодирования вдохновлен традиционным алгоритмом CKY (cocke1970programming). Традиционный алгоритм CKY состоит в том, чтобы передать состояние следующему дочернему узлу, перечислив продукты в каждом узле, а затем найти продукт с наибольшей вероятностью. Алгоритм декодирования, основанный на динамическом программировании, использует нейронную сеть для вычисления оценки каждой фразы, а затем перечисляет все ее подфразы для вычисления поддерева с наивысшей общей оценкой. Рисунок 9 представляет собой модельную структуру алгоритма декодирования этого типа плюс общую модель кодирования.

Декодирование динамического программирования

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

для любого диапазона (i, j) , мы используем уравнение 1 для вычисления оценок для всех его нетерминалов. Получите нетерминал с наибольшим количеством очков напрямую $\hat \ell_{ij}$ как оптимальный нетерминал.

И для подфраз нам нужно только предсказать (i, j) оптимальная точка разделения. перебрать все точки разделения, возьмите два дочерних узла (i,k) , (k,j) с узлом (i, j) Точка разделения с наибольшей суммой баллов может быть:

\begin{aligned} s_{\rm split}(i, j, k) & = s_{\rm label}(i, j, \hat \ell_{ij}) \\\ & + s_{\rm label}(i, k, \hat \ell_{ik}) + s_{\rm label}(k, j, \hat \ell_{kj}). \end{aligned}

Обратите внимание, что расчетная оценка здесь принимает оценку нетерминального символа. $s_{\rm label}(i, j, \ell)$ , и не брал оценку размаха $s_{\rm span}(i, j)$ . Поскольку в фактической реализации обнаруживается, что добавление или не добавление этой части оценки малоэффективно, поэтому для упрощения операции эта оценка удаляется.

Временная сложность алгоритма декодирования динамического программирования равна O(n^3) , поэтому для немного более длинных предложений это все еще довольно медленно. Но преимущество в том, что можно искать во всех пространствах состояний, поэтому точность относительно высока.

Жадное декодирование сверху вниз

Поскольку временная сложность алгоритма декодирования динамического программирования слишком высока, для аппроксимации оптимального синтаксического дерева можно использовать жадное декодирование. Идея состоит в том, чтобы жадно выбирать каждый диапазон сверху вниз. (i,j) Оптимальная точка разделения и оптимальный нетерминал $\hat \ell_{ij}$ , временная сложность будет снижена до O(n^2) .

Конкретная реализация выглядит следующим образом: сначала от корневого узла, который (0, n) Старт, выберите точку разделения $\hat k$ , так что два дочерних узла $(0, \hat k)$ , $(\hat k, n)$ с корневым узлом (0, n) Сумма оценок является наивысшей, а нетерминалы вычисляются непосредственно из векторного представления фразы, как и раньше. Конкретная формула:

\begin{array}{l} \hat \ell = \mathop {\arg \max }\limits_l [{s_{\rm label}}(i,j,\ell)] \\\ \hat k = \mathop {\arg \max }\limits_k [{s_{\rm split}}(i,j,k)]. \end{array}

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

Алгоритмы декодирования на основе последовательностей

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

выражения со скобками

Выражения в квадратных скобках — наиболее распространенный метод сериализации синтаксических деревьев.На рисунке 10 показаны выражения в квадратных скобках, соответствующие предложению «У Джона есть собака». Можно доказать, что существует однозначное соответствие между выражениями в скобках и синтаксическими деревьями, поэтому, пока выражения в скобках предсказаны, они могут быть однозначно сопоставлены с синтаксическим деревом. Таким образом, задача синтаксического анализа преобразуется во ввод предложения и вывод последовательности выражений в скобках, которые могут быть решены с помощью общей модели последовательности к последовательности (VinyalsKKPSH15). По аналогии с задачей машинного перевода входное предложение можно рассматривать как исходный язык, а выходное выражение в квадратных скобках можно рассматривать как целевой язык, который преобразуется в задачу перевода.

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

на основе синтаксической дистанции

图11：句子“She enjoys playing tennis .”对应的句法树及其句法距离序列。

синтаксическая дистанция(синтаксическая дистанция) определяется (ShenLHC18) является впервые предложенной новой концепцией, синтаксическое расстояние между двумя соседними словами в предложении определяется как высота их ближайшего общего предка. На рисунке 11 показана последовательность синтаксической дистанции для предложения «Ей нравится играть в теннис».предложение, длина его последовательности синтаксического расстояния равна n - 1 , и выполняются следующие условия: для любых двух соседних пар слов чем выше высота их ближайшего общего предка, тем больше синтаксическое расстояние между ними (BengioSCJLS18).

Взяв в качестве примера рисунок 11, ближайшим общим предком слов «She» и «enjoys» является «S», поэтому высота является самой высокой, и соответствующее синтаксическое расстояние также является самым большим. Ближайшим общим предком слов «наслаждается» и «играет» является «ВП», занимающее третье место по высоте, поэтому соответствующее синтаксическое расстояние также является третьим. Аналогично этому свойству удовлетворяют и остальные синтаксические дистанции. Можно показать, что существует однозначное соответствие между этой числовой последовательностью и синтаксическим деревом. Далее можно обнаружить, что эта последовательность на самом деле является «высотой узла, пройденного в порядке», что в исходном тексте называется синтаксическим расстоянием.

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

Процесс декодирования очень прост, для последовательности синтаксического расстояния $d_1, d_2, \ldots, d_n$ , сначала найдите самый большой элемент в последовательности d_i , то индекс меньшеПредложения образуют левое поддерево, большее или равноеЧасть составляет правое поддерево, то есть выражение в скобках синтаксического дерева $((x_{<i})(x_{\ge i}))$ . Для левого и правого поддеревьев необходимо только их рекурсивно декодировать.

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

Другие алгоритмы декодирования

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

Например(TengZ18) предложил две локальные модели. Один из них заключается в прямом прогнозировании каждого диапазона (i, j) Вероятность принадлежности к синтаксическому дереву затем декодируется с использованием алгоритма CKY. Другой - предиктивное производство $(i, j) \to (i, k) (k, j)$ Вероятность , а затем использовать алгоритм CKY для декодирования. Обе модели достигли очень высоких значений F1.

Другой пример(TuZZ18) предложил грамматику латентного вектора гауссовой смеси (GM-LVeGs) для изучения векторного представления продукции, и конечный эффект также лучше, чем у предыдущей грамматики комбинаторного вектора (CVG) (SocherBMN13).

несколько улучшений

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

Динамическое руководство

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

Здесь мы лишь кратко объясним определение динамического наведения в нисходящем приближенном декодировании моделей динамического программирования, которые аналогичны моделям, основанным на системах переноса.

Предположим теперь, что модель предсказывает диапазон (i, j) , то следует предсказать его нетерминал и точку разделения.

Сначала для нетерминалов, если (i, j) В стандартном синтаксическом дереве его нетерминал является стандартным нетерминалом, в противном случае он определяется как пустой набор $\varnothing$ .

Тогда для точки разделения, если (i, j) В стандартном синтаксическом дереве точкой разделения является стандартная точка разделения. В противном случае ищется стандартное синтаксическое дерево, содержащее (i, j) самый маленький промежуток (i', j') , тогда узнайСреди всех точек разделения , расположенных в (i, j) Любая точка разделения между ними может использоваться в качестве динамической направляющей. В реальной реализации возьмите самую левую точку разделения, которая удовлетворяет условию. Разные точки сегментации соответствуют разным методам бинаризации, что на самом деле не имеет значения. существует(CrossH16) для подробного процесса проверки для динамического руководства.

градиент политики

Помимо проблемы динамического наведения, жадное декодирование также имеет проблему, то есть оно оптимизирует только текущий момент, а не глобальную оптимизацию, поэтому полученное решение не является глобальным оптимальным решением. Кроме того, динамическое руководство необходимо разрабатывать отдельно для разных моделей, что более проблематично, поэтому можно использовать метод обучения с подкреплением.градиент политики(градиент политики), чтобы заменить его (FriedK18).

первое использованиефункция риска(целевой риск) как функция потерь модели:

\mathcal{R}(\theta ) = \sum\limits_{i = 1}^N {\sum\limits_y {p(y|{x^{(i)}};\theta )\Delta (y,{y^{(i)}})} },

в $(x^{(i)}, y^{(i)})$ — стандартные данные в обучающей выборке. Видно, что функция риска на самом деле представляет собой разницу между всеми возможными синтаксическими деревьями и стандартными деревьями. ${\Delta (y,{y^{(i)}})}$ Цель обучения — свести к минимуму разницу между всеми синтаксическими деревьями и стандартными деревьями, решив тем самым две проблемы, упомянутые ранее.

Но, очевидно, невозможно перечислить все возможные синтаксические деревья, что требует использованияВыборка по важностиметод (важной выборки). Однако выборка важности не может быть выполнена непосредственно для функции риска, в противном случае выборочная функция $\theta$ Если он исчезнет, его невозможно вывести, поэтому сначала необходимо вывести функцию риска, чтобы получить:

\nabla \mathcal{R}(\theta ) \approx \sum\limits_{i = 1}^N {\sum\limits_{y \in \mathcal{Y}({x^{(i)}})} {\Delta (y,{y^{(i)}})\nabla \log p(y|{x^{(i)}};\theta )} },

здесьсогласно распределению $p(y|x^{(i)})$ результаты выборки. В конкретной реализации стандартное дерево также может быть добавлено к результату выборки, что может повысить точность.

эксперимент

набор данных

Наиболее широко используемый набор данных на английском языке для анализа синтаксиса компонентов — это набор данных PTB из Wall Street Journal, в котором главы со 2 по 21 разделены на обучающие наборы, 22 главы — на проверочные и 23 — на тестовые. Китайский набор данных — это набор данных CTB.Существует несколько версий, таких как 5.0, 6.0 и 8.0, но наиболее широко используемая версия — 5.0.

Результаты экспериментов

В таблице 1 приведены результаты тестирования некоторых моделей синтаксического анализа, которые разделены на две части: одиночная модель и не одиночная модель. Единая модель — это модель, которая не использует какие-либо внешние знания и операции переупорядочивания, в то время как неединая модель использует различные методы, такие как внешний корпус, модель предварительного обучения, слияние моделей и переупорядочивание. Текущие лучшие результаты для одной модели получены из (KleinK18), они приняли Transformer в качестве энкодера, что значительно улучшило их результаты. Видно, что влияние кодировщика в области разбора компонентов намного больше, чем влияние декодера. Наилучшие результаты в области не одной модели были получены той же командой (abs-1812-11760), где использовали более мощную предварительно обученную модель BERT, доведя результаты до непреодолимой высоты.

Резюме и перспективы на будущее

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

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

использованная литература

Attention is All you Need
Transition-based Neural Constituent Parsing
Span-Based Constituency Parsing with a Structure-Label System and Provably Optimal Dynamic Oracles
In-Order Transition-based Constituent Parsing
A Minimal Span-Based Neural Constituency Parser
Constituency Parsing with a Self-Attentive Encoder
Straight to the Tree: Constituency Parsing with Neural Syntactic Distance
Constituent Parsing as Sequence Labeling
Grammar as a Foreign Language
Two Local Models for Neural Constituent Parsing
Long Short-Term Memory Over Tree Structures
Dependencies vs. Constituents for Tree-Based Alignment
A tutorial on particle filtering and smoothing: Fifteen years later
Programming languages and their compilers: Preliminary notes
Parsing with Compositional Vector Grammars
Policy Gradient as a Proxy for Dynamic Oracles in Constituency Parsing
Multilingual Constituency Parsing with Self-Attention and Pre-Training
Fast and Accurate Shift-Reduce Constituent Parsing
Shift-Reduce Constituent Parsing with Neural Lookahead Features
Linear-time Constituency Parsing with RNNs and Dynamic Programming
Recurrent Neural Network Grammars
Effective Inference for Generative Neural Parsing
Parsing as Language Modeling
Extending a Parser to Distant Domains Using a Few Dozen Partially Annotated Examples
Improving Neural Parsing by Disentangling Model Combination and Reranking Effects
Neural Language Modeling by Jointly Learning Syntax and Lexicon
Gaussian Mixture Latent Vector Grammars