11.5 Анализ активных диаграмм снизу вверх

Теперь, когда мы знаем об активных краях, фундаментальном правиле и повестках дня, пришло время собрать все эти ингредиенты вместе и рассмотреть конкретный алгоритм анализа диаграмм. Алгоритм «снизу вверх», который мы будем использовать, — это, по сути, только что изученный общий алгоритм, но с добавленными деталями, чтобы заставить его работать снизу вверх. Чтобы понять это, давайте рассмотрим это шаг за шагом на примере.

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

Во-первых, мы должны инициализировать график и повестку дня (шаг 1 общего алгоритма). Инициализация диаграммы работает точно так же, как и для пассивного парсера . So, the initial chart for the sentence Mia danced looks like this:

The initial agenda looks like this:

1.
2.

Для всех слов ввода мы добавили пассивные ребра, говорящие о том, к какой категории они относятся и какова их позиция в предложении. Ребро , например, является пассивным ребром (точка в самом конце), которое говорит о том, что между позициями 0 и 1 есть . Это ребро было добавлено, потому что в нашей грамматике есть правило.

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

Затем мы пытаемся применить основное правило к новой дуге (шаг 2c). Основное правило позволяет нам комбинировать активную дугу с пассивной дугой, которая находится непосредственно справа от активной. Так как дуга, с которой мы работаем, является пассивной, мы должны найти активную дугу слева, или, точнее, мы должны найти активную дугу, которая заканчивается в позиции 0. Такой дуги нет, поэтому мы ничего не можем сделать. здесь. Переходим к шагу 2d.

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

В нашем примере мы имеем дело с пассивной дугой в данный момент (). Затем предсказание гипотез работает следующим образом. Мы ищем такие правила грамматики, что первый символ в правой части этих правил совпадает с левой частью дуги (что в нашем случае). есть такое правило, например. Затем мы строим активные ребра для всех этих правил. Эти ребра начинаются в той же позиции, что и дуга, на которую мы смотрели, заканчиваются точно в той же позиции и имеют точку сразу после стрелки. Так: . Это ребро является гипотезой о том, что мы могли бы построить начало в 0. Для этого нам все еще нужно найти , также начинающееся в 0. Поскольку мы уже нашли начало в 0, это разумная гипотеза. Если бы были более подходящие правила, мы бы построили активное ребро для каждого из них.

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

Мы добавляем все новые ребра в повестку дня и сейчас находимся в конце первого раунда повторения цикла шага 2. Диаграмма и повестка дня выглядят следующим образом:

1.
2.

. АгенDA не пуста, еще не пуста, так и дает. Первая часть этого должна быть понятна: мы просто размещаем верхнюю часть повестки, то есть активное ребро, на графике. Чтобы применить основное правило (шаг 2с), мы должны найти на диаграмме пассивное ребро, которое начинается в позиции 0 (конечная точка активного ребра). Есть один; а именно, . Поэтому мы можем создать преимущество (вернитесь к разделу 11.2, если вы не понимаете, как это работает) и добавить его в повестку дня. Поскольку шаг 2d применяется только к пассивным краям, мы его пропускаем. Текущее состояние диаграммы и повестки дня:

1.
2.

В следующем раунде будут перемещены из Агенда в график. Шаг 2c не создает новых ребер, но на шаге 2d активные ребра и будут добавлены в повестку дня. Диаграмма и повестка дня тогда выглядят следующим образом.

 

1.
2.
3.

Далее переходим от повестки дня к графику. Применение основного правила на шаге 2c дает нам новое преимущество.

1.
2.
3.

is moved to the chart. Никакой новый край не может быть построен.

1.
2.

отправляется в карту. Основное правило создает .

1.
2.

перемещается в карту. Новое ребро не создается.

1.

перемещается на график. Шаг 2d прогнозирует .

1.

перемещается на график. Основное правило дает .

1.

перемещается на график. Основное правило дает и . Шаг 2d, хотя и применим как пассивное ребро, не создает новых правил.

1.
2.

перемещен на график Ни шаг 2c, ни шаг 2d не создают никаких новых правил.

1.

перемещается на график. Опять же, новые ребра не могут быть построены.

Повестка теперь пуста, поэтому выходим из повтора. Это приводит нас к шагу 3. И да, у нас есть пассивный узел s от первого до последнего узла, поэтому нам удалось распознать предложение.

Разбор диаграммы сверху вниз – принципы обработки естественного языка

Методы разбора диаграммы сверху вниз, такие как алгоритм Эрли, начинаются с самого верхнего нетерминала, а затем расширяются вниз, предсказывая правила в грамматике, рассматривая самую правую невидимую категорию для каждого правила. По сравнению с другими алгоритмами синтаксического анализа на основе поиска синтаксический анализ сверху вниз может быть более эффективным за счет устранения многих потенциальных локальных неоднозначностей при расширении дерева вниз ^[1] . На рисунке A1 представлены правила обработки для алгоритма Эрли. На рисунке А.2 представлен псевдокод для алгоритма, реализованного в виде динамического программирования.

Рисунок A.1 Правила обработки для алгоритма Эрли

Инициализация сверху вниз : Если категория S является корневой категорией грамматики, то для каждого правила с S в левой части создайте пустое ребро в позиции [0:0] с крайне левой точкой в ​​правой части. То есть всякий раз, когда S -> A B для некоторого A добавляется ребро [0:0] S -> * A B Правило предсказания сверху вниз: Когда ожидается категория X (т. е. сразу справа от точки), то для всех правил, где X находится в левой части, добавьте новое ребро, где точка находится слева в правой части с интервалом нулевой длины в текущей конечной точке. (Это правило будет повторяться несколько раз до тех пор, пока нельзя будет сделать новые прогнозы). То есть всякий раз, когда ([i:k] A -> W * X Y) и X -> S T, для некоторого X добавляется новое ребро [k:k] X -> * S T.  (Примечание: W может быть пустым .) Основное правило : Когда новая категория просматривается или создается нетерминальная, то для всех активных правил, где категория крайняя левая справа от точки, а интервалы являются смежными, создайте новое ребро с точкой переместиться влево от этой категории и объединить диапазоны. То есть всякий раз, когда  ([i:j], A -> X * Y Z и  [j:k] Y -> S T * для некоторых j и Y, добавьте новое ребро  [i:k], A -> X Y * Z (Примечание: X и Z могут быть пустыми.)

 

Чтобы проиллюстрировать анализ диаграммы сверху вниз, мы предположим, что CFG показан на рисунке A.3.

Рисунок А.3. Небольшая CFG для разбора «собака любит мясо».

С → НП ВБД С → НП ВП НП → ДТ НН ВП → ВБЗ НН

NN → собака | мясо ВБД → короед ВБЗ → любит ДТ →

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

По мере чтения каждого слова выполняется предсказание сверху вниз, за ​​которым следует применение основного правила. После завершения ребра (например, первого NP) добавляются новые прогнозы (например, для предстоящего VP).

Рисунок А.4. Фрагмент разбора диаграммы сверху вниз предложения «Собака любит мясо».

	[0:0] С → * НП ВБД [0:0] С → * НП ВП	Для каждого правила предложения сделайте предсказание сверху вниз, чтобы создать пустое активное ребро.
	[0: 0] S → * NP VBD [0: 0] S → * NP VP [0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0] NP VP	Сделайте больше нисходящих прогнозов, чтобы создать активные ребра для каждой из неконечных категорий справа от точки.
	[0:0] S → * НП ВБД [0: 0] S → * NP VP [0: 0] NP → * DT NN [0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0: 0] . [0:1] DT →  the * [0:1] NP → DT * NN	Предскажите и используйте фундаментальное правило для создания новых ребер, где точка в правиле DT и в правиле NP перемещается вправо.
	[0: 0] S → * NP VBD [0: 0] S → * NP → * NP → * NP → * NP . DT NN [0: 0] DT → * [0: 1] DT → THE * → THE * 9 → THE * → НН [1:1] НН → * dog [1:2] NN →   dog * [0:2] NP →  DT  NN * [0:2] S → НП * ВБД [0:2] S → НП * ВП [2:2] ВП → 709 131 * 0314 * ВБЗ	Predict собака; применить фундаментальное правило, а затем сделать нисходящий прогноз для VP (используя второе правило S).
	[0: 0] S → * NP VBD [0: 0] S → * NP → * NP → * NP → * NP . DT NN [0: 0] DT → * [0: 1] DT → THE * → THE * 9 → THE * → NN [1:1] NN → * dog [1:2] NN →  dog * [0:2] NP →   DT  NN * [0:2] S → NP * VBD [0: 2] S → NP * VP [2: 2] VP → [2: 2] VP → [2: 2]. →   * нравится [2:3] ВБЗ →   нравится * [2:3] ВП → ВБЗ  * NN	Предсказать лайков;   применить основное правило для создания ВБЗ->лайки*, и снова для добавления ВП -> ВБЗ* NN
	[0: 0] S → * NP VBD [0: 0] S → * NP → * NP → * NP → * NP . ДТ НН . [1: 1] NN → * собака [1: 2] NN → DOG * [0: 2] NP [0: 2] NP [0: 2] NP [2] [2] [0:2] S →  NP * VBD [0:2] S → NP * VP [2: 2] VP → * VBZ NN [2: 2] VBZ → .  likes * [2:3] VP → VBZ  * NN [3:3] NN → * meat [3:4] NN →   мясо* [2:4] ВП → ВБЗ  NN * [0:4] С → НП ВП *	Предсказать мясо применить фундаментальное правило для мяса как существительного (NN) и снова расширить активное ребро VP, чтобы получить VP -> VBZ NN*. Добавить комментарий Отменить ответ Ваш адрес email не будет опубликован. Обязательные поля помечены * Комментарий * Имя * Email * Сайт