1.1 Лингвистические данные и неограниченные возможности

Предыдущие главы показали вам, как обрабатывать и анализировать текстовые корпусы, и мы выделили задачи NLP в работе с огромным количеством данных электронного языка, который растет с каждым днем. Рассмотрим эти данные более тесно и выполним мысленный эксперимент, предположив, что мы имеем гигантский корпус, состоящий из всего, что было произнесено или написано на английском языке в течение, скажем, последних 50 лет. Есть ли у нас основания называть этот корпус "Современный английский язык"? Есть целый ряд причин, по которым мы могли бы ответить: "Нет". Вспомните, что в 3, мы попросили вас найти в Интернете экземпляры паттерна the of. Хотя в Интернете несложно найти примеры, содержащие эту последовательность слов, такие как New man at the of IMG (http://www.telegraph.co.uk/sport/2387900/New-man-at-the-of-IMG.html), носители английского языка скажут, что большинство таких примеров ошибочны и, следовательно, не являются частью английского языка.

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

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

(1)

a. Usain Bolt broke the 100m record b. The Jamaica Observer reported that Usain Bolt broke the 100m record c. Andre said The Jamaica Observer reported that Usain Bolt broke the 100m record d. I think Andre said the Jamaica Observer reported that Usain Bolt broke the 100m record

Если бы мы заменили целые предложения символом S, мы бы увидели такие модели, как Andre said S и I think S. Это шаблоны, с помощью которых можно взять предложение и построить большее предложение. Есть и другие шаблоны, которые мы можем использовать, как S but S и S when S. Немного изобретательности поможет нам построить некоторые действительно длинные предложения с помощью этих шаблонов. Вот впечатляющий пример из Истории Винни-Пуха А. А. Милна, в которой Пятачок полностью окружен водой:

[You can imagine Piglet's joy when at last the ship came in sight of him.] In after-years he liked to think that he had been in Very Great Danger during the Terrible Flood, but the only danger he had really been in was the last half-hour of his imprisonment, when Owl, who had just flown up, sat on a branch of his tree to comfort him, and told him a very long story about an aunt who had once laid a seagull's egg by mistake, and the story went on and on, rather like this sentence, until Piglet who was listening out of his window without much hope, went to sleep quietly and naturally, slipping slowly out of the window towards the water until he was only hanging on by his toes, at which moment, luckily, a sudden loud squawk from Owl, which was really part of the story, being what his aunt said, woke the Piglet up and just gave him time to jerk himself back into safety and say, "How interesting, and did she?" when — well, you can imagine his joy when at last he saw the good ship, Brain of Pooh (Captain, C. Robin; 1st Mate, P. Bear) coming over the sea to rescue him...

Это длинное предложение на самом деле имеет простую структуру, которая начинается с S but S when S. Мы можем увидеть из этого примера, что язык дает нам конструкции, которые, как представляется, позволяют распространять предложения бесконечно. То, что мы можем понимать предложения произвольной длины, которые мы никогда раньше не слышали, также поразительно: не трудно придумать совершенно новое предложение, которое, вероятно, никогда ранее не использовалось в истории языка, но все носители языка поймут его.

Цель грамматики дать явное описание языка. Но то, как мы мыслим грамматику, тесно переплетается с тем, что мы считаем языком. Является ли язык большим, но конечным множеством наблюдаемых высказываний и письменных текстов? Является ли он чем-то более абстрактным, как неявное знание, которым обладают компетентные носители о грамматических предложениях? Или это некоторое сочетание этих двух? Мы не будем занимать определенную позицию по этому вопросу, но вместо этого представим основные подходы.

В этой главе мы будем применять формальные рамки "порождающей грамматики", в которой "язык" считается ни чем иным, как огромной совокупностью всех грамматических предложений, а грамматика является формальной системой, которая может быть использована для "генерации" членов этого набора. Грамматики используют рекурсивные модели вида S → S and S, как мы увидим в 3. В 10. мы расширим это понимание, чтобы автоматически выстроить смысл предложения из значений его частей.

1.2 Вездесущая неоднозначность

Хорошо известный пример неоднозначности показан в (2), из фильма Граучо Маркса, Animal Crackers (1930):

(2)

While hunting in Africa, I shot an elephant in my pajamas. How he got into my pajamas, I don't know.

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

>>> groucho_grammar = nltk.CFG.fromstring("""
... S -> NP VP
... PP -> P NP
... NP -> Det N | Det N PP | 'I'
... VP -> V NP | VP PP
... Det -> 'an' | 'my'
... N -> 'elephant' | 'pajamas'
... V -> 'shot'
... P -> 'in'
... """)

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

>>> sent = ['I', 'shot', 'an', 'elephant', 'in', 'my', 'pajamas']
>>> parser = nltk.ChartParser(groucho_grammar)
>>> for tree in parser.parse(sent):
...     print(tree)
...
(S
  (NP I)
  (VP
    (VP (V shot) (NP (Det an) (N elephant)))
    (PP (P in) (NP (Det my) (N pajamas)))))
(S
  (NP I)
  (VP
    (V shot)
    (NP (Det an) (N elephant) (PP (P in) (NP (Det my) (N pajamas))))))

Программа производит две заключенные в квадратные скобки структуры, которые мы можем изобразить в виде деревьев, как показано в (3b):

(3)

a. b.

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

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

2.1 За пределами n-грамм

В 2. мы дали пример того, как использовать информацию о частоте в биграммах для генерации текста , который кажется вполне приемлемым для небольших последовательностей слов, но быстро вырождается в бессмыслицу. Вот еще пара примеров, которые мы создали путем вычисления биграмм для текста рассказа для детей, The Adventurs of Buster Brown(http://www.gutenberg.org/files/22816/22816.txt):

(4)

a. He roared with me the pail slip down his back b. The worst part and clumsy looking for whoever heard light

Вы интуитивно знаете, что эти последовательности "салат из слов", но вы, вероятно, с трудом можете сказать, что с ними случилось. Одним из преимуществ изучения грамматики является то, что она предоставляет концептуальные рамки и словарный запас для выражения этих интуиций. Давайте подробнее рассмотрим последовательность the worst part and clumsy looking. Это выглядит как сочиненная структура, в которой две фразы объединены соединительным союзом, таким как и, но или или. Вот неформальное (и упрощенный) определение того, как сочинение работает синтаксически:

Сочиненная структура:

Если v₁ и v₂ являются обе фразами грамматической категории X, то v₁ и v₂ также фраза категории X.

Вот несколько примеров. В первом из них две ИФ (именные фразы) были конъюгированы, чтобы получить ИФ, а во втором две ПФ (прилагательные фразы) были конъюгированы, чтобы получить AP.

(5)

a. The book's ending was (NP the worst part and the best part) for me. b. On land they are (AP slow and clumsy looking).

То, что мы не можем сделать, это объединить ИФ и ПФ, поэтому выражение the worst part and clumsy looking безграмотно. Прежде чем мы сможем формализовать эти идеи, нам необходимо понять концепцию конституирующей структуры.

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

(6)

The little bear saw the fine fat trout in the brook.

Тот факт, что мы можем заменить The little bear на He указывает на то, что первая последовательность является единством. В отличие от нее мы не можем заменить littel bear saw таким же образом.

4,46%

a. He saw the fine fat trout in the brook. b. *The he the fine fat trout in the brook.

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

Рисунок 2.1: Замена последовательностей слов: начиная с верхнего ряда, мы можем заменить определенные последовательности слов (например, the brook) отдельными словами (например , it); повторяя этот процесс, мы приходим к грамматическому двухсловному предложению.

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

Рисунок 2.2: Замена последовательностей слов плюс грамматические категории: Эта диаграмма воспроизводит 2.1 наряду с грамматическими категориями, соответствующими именным фразам (NP), глагольным фразам (VP), предложным фразам (PP) и номиналам (Nom).

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

(8)

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

3.1 Простая грамматика

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

grammar1 = nltk.CFG.fromstring("""
  S -> NP VP
  VP -> V NP | V NP PP
  PP -> P NP
  V -> "saw" | "ate" | "walked"
  NP -> "John" | "Mary" | "Bob" | Det N | Det N PP
  Det -> "a" | "an" | "the" | "my"
  N -> "man" | "dog" | "cat" | "telescope" | "park"
  P -> "in" | "on" | "by" | "with"
  """)

>>> sent = "Mary saw Bob".split()
>>> rd_parser = nltk.RecursiveDescentParser(grammar1)
>>> for tree in rd_parser.parse(sent):
...      print(tree)
(S (NP Mary) (VP (V saw) (NP Bob)))

Грамматика в 3.1 содержит продуцирования с участием различных синтаксических категорий, как изложено в 3.1.

Продуцирование, как VP -> V NP | V NP PP, имеет дизъюнкцию на правой стороне, показнную |, и такая запись является аббревиатурой для двух продуцирований VP -> V NP и VP -> V NP PP.

Рисунок 3.2: Recursive Descent Parser Demo: Этот инструмент позволяет следить за работой рекурсивно спускающегося синтаксического анализатора по мере того, как он создает дерево синтаксического разбора и наполняет его входными словами.

Если разобрать предложение The dog saw a man in the park с помощью грамматики, показанной в разделе 3.1, мы получим в конечном итоге два дерева похожих на те, которые мы видели для (3b):

(9)

a. b.

Так как наша грамматика допускает два дерева для этого предложения, предложение называется структурно неоднозначным. Данная неоднозначность называется неоднозначность приложения предложной фразы, как мы видели ранее в этой главе. Как вы, возможно, помните, это двусмысленность приложения, так как PP in the park необходимо приложить к одному из двух мест в дереве: либо как ребенок VP или как ребенок NP.Когда PP приложена к VP, предполагаемая интерпретация заключается в том, что событие видения произошло в парке. Однако если PP прилагается к NP, тогда в парке был человек, а агент видения (собака), возможно, сидела на балконе квартиры с видом на парк.

3.2 Написание ваших собственных грамматик

Если вы заинтересованы в экспериментировании с написанием безконтекстных грамматик (CFGs), вам будет удобно создавать и редактировать грамматики в текстовом файле, скажем, mygrammar.cfg. После этого вы можете загрузить ее в NLTK и осуществлять синтаксический разбор следующим образом:

>>> grammar1 = nltk.data.load('file:mygrammar.cfg')
>>> sent = "Mary saw Bob".split()
>>> rd_parser = nltk.RecursiveDescentParser(grammar1)
>>> for tree in rd_parser.parse(sent):
...      print(tree)

Убедитесь, что вы присоединили .cfg суффикс к имени файла и что в строке 'file:mygrammar.cfg' нет пробелов. Если команда print(tree) не производит никакого вывода, это, вероятно, потому, что ваше предложение sent не допускается вашей грамматикой. В этом случае вызовите парсер с включенным отслеживанием: rd_parser = NLTK.RecursiveDescentParser(grammar1, trace = 2). Вы также можете проверить, какие текущие продуцирования есть в грамматике с помощью команды for p in grammar1.productions(): print(р).

Когда вы пишете CFGs для разбора в NLTK, вы не можете комбинировать грамматические категории с лексическими единицами на правой стороне одного и того же продуцирования. Таким образом, продуцирование, такое как PP -> 'of' NP запрещено. Кроме того, не разрешается размещать лексические единицы, состоящие из нескольких слов, на правой части продуцирования. Поэтому вместо того, чтобы писать NP -> 'New' 'York', вы должны прибегнуть к чему-то вроде NP -> 'New_York' вместо этого.

3.3 Рекурсия в синтаксической структуре

Грамматика называется рекурсивной, если категория, возникающая на левой стороне продуцирования, также появляется и на правой его части, как показано в 3.3. Продуцирование Nom -> Adj Nom (где Nom это категория номиналов) влечет прямую рекурсию по категории Nom, тогда как непрямая рекурсия по S возникает из сочетания двух продуцирований, а именно : S -> NP VP и VP -> V S.

grammar2 = nltk.CFG.fromstring("""
  S  -> NP VP
  NP -> Det Nom | PropN
  Nom -> Adj Nom | N
  VP -> V Adj | V NP | V S | V NP PP
  PP -> P NP
  PropN -> 'Buster' | 'Chatterer' | 'Joe'
  Det -> 'the' | 'a'
  N -> 'bear' | 'squirrel' | 'tree' | 'fish' | 'log'
  Adj  -> 'angry' | 'frightened' |  'little' | 'tall'
  V ->  'chased'  | 'saw' | 'said' | 'thought' | 'was' | 'put'
  P -> 'on'
  """)

Чтобы увидеть, как возникает рекурсия из этой грамматики, рассмотрим следующие деревья. (10a) влечет вложенные именные фразы, а (10b) содержит вложенные предложения.

(10)

a. b.

Мы проиллюстрировали только два уровня рекурсии здесь, но нет никакого верхнего предела глубины. Вы можете экспериментировать с разбором предложений, которые влекут более глубоко вложенные структуры. Обратите внимание, что RecursiveDescentParser не в состоянии справиться с левыми рекурсивными продуцированиями вида X -> XY; мы вернемся к этому в 4.

4.1 Рекурсивно спускающийся синтаксический разбор

Простейший вид анализатора интерпретирует грамматику как спецификацию того, как разбить цель высокого уровня на несколько подзадач более низкого уровня. Цель верхнего уровня - найти S. Продуцирование S → NP VP позволяет анализатору заменить эту цель двумя подзадачами: найти NP, а затем найти VP. Каждая из этих подзадач может быть заменена в свою очередь подподцелями с помощью продуцирований, которые имеют на левой стороне NP и VP соответственно. В конце концов, этот процесс приводит к подзадачам, таким как: найти слово телескоп. Такие подзадачи можно сравнивать непосредственно с входной последовательностью, они являются успешными, если следующее слово найдено. Если совпадения нет анализатор должен вернуться наверх и попробовать другую альтернативу.

Метод рекурсивного спуска строит дерево разбора во время вышеописанного процесса. С первоначальной целью (найти S) создается корневой узел S. Поскольку описанный выше процесс рекурсивно расширяет свои цели, используя продуцирования грамматики, дерево разбора распространяется вниз (отсюда и название рекурсивный спуск). Мы можем увидеть это в действии с помощью графической демонстрации nltk.app.rdparser(). Шесть этапов выполнения данного синтаксического анализа приведены на 4.1.

Рисунок 4.1: Шесть этапов метода рекурсивного спуска: анализатор начинает с дерева, состоящего из узла S; на каждом этапе он обращается к грамматике, чтобы найти продуцирование, которое может быть использовано для увеличения дерева; когда встречается лексическое продуцирование, его слово сравнивается с входом; после нахождения полного синтаксического разбора, анализатор ищет другие разборы.

Во время этого процесса анализатору часто приходится выбирать между несколькими возможными продуцированиями. Например, при переходе от шага 3 к шагу 4, он пытается найти продуцирования с N на левой стороне. Первым из них является N → человек. Когда это не срабатывает, он откатывается и пробует другие продуцирования N по порядку, пока не доберется до N → собака, которое соответствует следующему слову во входном предложении. Намного позже, как показано на шаге 5, он находит полный разбор. Это дерево, которое охватывает все предложение без каких-либо оборванных краев. После того, как синтаксический разбор был найден, мы можем использовать анализатор для поиска дополнительных разборов. Опять же он будет возвращаться назад и исследовать другие варианты продуцирования на случай, если какой-нибудь из них приведет к разбору.

NLTK предоставляет метод рекурсивного спуска:

>>> rd_parser = nltk.RecursiveDescentParser(grammar1)
>>> sent = 'Mary saw a dog'.split()
>>> for tree in rd_parser.parse(sent):
...     print(tree)
(S (NP Mary) (VP (V saw) (NP (Det a) (N dog))))

Синтаксический анализа с помощью рекурсивного спуска имеет три основных недостатка. Во- первых, левые рекурсивные продуцирования, как NP -> NP PP отправляют его в бесконечный цикл. Во-вторых, анализатор тратит уйму времени, рассматирвая слова и структуры, которые не соответствуют входному предложению. В-третьих, процесс отката может сбросить уже разобранные компоненты, которые необходимо будет восстановить позже. Например, откат с VP -> V NP отбросит поддерево, созданное для NP. Если анализатор затем продолжает с VP -> V NP PP, то поддерево NP должно быть создано заново.

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

4.2 Синтаксический разбор помещения-сокращения

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

Анализатор неоднократно выталкивает следующее входное слово в стек (4.1); это операция называется помещением. Если верхние n элементов в стеке соответствуют n элементам на правой стороне какого-то продуцирования, то все они извлекаются из стека, а элемент на левой стороне продуцирования помещается в стек. Эта замена верхних n элементов одним элементом является операцией сокращения. Эта операция может быть применена только к верхней части стека; сокращение элементов, находящихся ниже в стеке, должно быть выполнено до помещения новых элементов в стек. Анализатор заканчивает работу, когда весь вход использован и остается только один элемент в стеке - дерево разбора с узлом S в качестве корневого элемента. Анализатор помещения-сокращения строит дерево разбора во время вышеописанного процесса. Каждый раз, когда она сокращает n элементов из стека, он объединяет их в частичное дерево разбора и помещает обратно в стек. Мы можем увидеть в действии алгоритм синтаксического анализа помещения-сокращения с помощью графической демонстрации nltk.app.srparser(). Шесть этапов выполнения данного синтаксического анализатора приведены на Рисунке 4.2.

Рисунок 4.2: Шесть этапов Анализатора помещения-сокращения: анализатор начинает путем помещения первого входного слова в свой стек; как только верхние элементы в стеке соответствуют правой стороне грамматического продуцирования, они могут быть заменены левой стороной того же продуцирования; синтаксический анализатор успешно завершает свою работу, как только весь вход потреблен и один элемент S остается в стеке.

NLTK предоставляет ShiftReduceParser(), простую реализацию анализатора помещения-сокращения. Этот анализатор не выполняет каких-либо откатов, так что нахождение разбора текста, даже если таковой существует, не гарантируется. Кроме того, он найдет не более одного разбора, даже если существует большее количество разборов. Мы можем предоставить дополнительный параметр trace, который управляет тем, как пространно анализатор сообщает о своих шагах, которые он препринимает в процессе разбора текста:

>>> sr_parser = nltk.ShiftReduceParser(grammar1)
>>> sent = 'Mary saw a dog'.split()
>>> for tree in sr_parser.parse(sent):
...     print(tree)
  (S (NP Mary) (VP (V saw) (NP (Det a) (N dog))))

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

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

Преимущество анализаторов помещения-сокращения над рекурсивно спускающимися анализаторами заключается в том, что они строят только структуру, которая соответствует словам на входе. Кроме того, они строят каждую подструктуру только один раз, например NP(Det(the), N(man)) строится и помещается в стек только в один раз, независимо от того, будет ли он позже использоваться сокращением VP -> V NP PP или сокращением NP -> NP PP.

4.3 Анализатор левого угла

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

Грамматика grammar1 позволяет нам производить следующий разбор John saw Mary:

(11)

Напомним, что грамматика (определенная в 3.3) имеет следующие продуцирования для расширения NP:

(12)

a. NP -> Det N b. NP -> Det N PP c. NP -> "John" | "Mary" | "Bob"

Предположим, мы просим вас сначала посмотреть на дерево (11), а затем решить, какую из NP подстановок (продуцирований) вы хотите, чтобы метод рекурсивного спуска применил первой - очевидно, (12с) является правильным выбором! Откуда вы знаете, что было бы бессмысленно применять сначала (12a) или (12b)? Потому что ни одна из этих двух подстановок (продуцирований) не выведет последовательность, первое слово которой John. То есть, мы можем легко сказать, что в успешном разборе предложения John saw Mary анализатор должен расширить NP таким образом, чтобы NP давала последовательность John α. В более общем плане мы говорим, что категория B является левым углом дерева с корнем в А , если A ⇒ *B α.

(13)

Левоугольный анализатор - это анализатор сверху вниз с фильтрацией снизу вверх. В отличие от обычного метод рекурсивного спуска, он не попадает в ловушку в левой рекурсии подстановки. Перед началом своей работы, левоугольный анализатор выполняет предварительную обработку контекстно свободной грамматики для построения таблицы, где каждая строка содержит две ячейки, первая содержит неконечную, а вторая содержит набор возможных левых углов неконечной (подстановки?). Таблица 4.1 иллюстрирует это для грамматики из grammar2.

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

4.4 Таблица хорошо сформированных подстрок

Простые анализаторы, рассмотренные выше, страдают от ограничений как полноты, так и эффективности. Для того чтобы исправить это, мы будем применять для проектирования алгоритма синтаксического анализа технику динамического программирования. Как мы видели в 4.7, динамическое программирование храниит промежуточные результаты и повторно использует их при необходимости, добиваясь значительного повышения эффективности. Этот метод может быть применен к синтаксическому разбору, позволяя нам хранить частичные решения задачи синтаксического анализа, а затем находить их по мере необходимости для того, чтобы эффективно прийти к полному решению. Такой подход к разбору известен как табличный (графический-?) синтаксический анализ. Мы познакомим вас с основной идеей в этом разделе; обратитесь к онлайн материалам для этой главы для получения более подробной информации о реализации.

Динамическое программирование позволяет строить PP in my pajamas только один раз. Первый раз, когда мы создаем его, мы сохраняем его в таблице, затем мы находим его, когда мы должны использовать его в качестве подкомпонента либо объекта NP или более высокого уровня VP. Эта таблица известна как таблица хорошо сформированных подстрок или ТХСП (WFST) для краткости. (Термин "подстроки" относится к непрерывной последовательности слов в предложении.) Мы покажем, как построить WFST снизу вверх так, чтобы систематически записывать, какие синтаксические компоненты были найдены.

Давайте используем в качестве нашего входа предложении из (2). Численно указанные пролеты WFST напоминают срез как нотацию языка Python (3.2). Еще один способ думать о структуре данных, показанной на 4.3, - это структура данных, известная как график.

Рисунок 4.3: Диаграмма структуры данных: слова являются метками ребер линейной графической структуры.

В WFST мы фиксируем положение слов путем заполнения ячеек треугольной матрицы: вертикальная ось будет обозначать начальную позицию подстроки, а горизонтальная ось будет обозначать конечное положение (таким образом shot будет отображаться в ячейке с координатами (1, 2)). Для упрощения этого изложения мы будем считать, что каждое слово имеет уникальную лексическую категорию, и мы будем хранить ее (а не слово) в матрице. Таким образом, клетка (1, 2) будет содержать запись V. В более общем плане, если наша входная строка является a₀a₁ ... a_n и наша грамматика содержит подстановку вида A → a_i, тогда мы добавляем A в ячейку (i, `i`+1).

Таким образом, для каждого слова в text, мы можем найти в нашей грамматике, к какой категории оно принадлежит.

>>> text = ['I', 'shot', 'an', 'elephant', 'in', 'my', 'pajamas']
>>> groucho_grammar.productions(rhs=text[1])
[V -> 'shot']

Для нашего WFST мы создаем матрицу (n-1)×(n-1) в виде списка списков Python и заполняем его лексическими категориями каждого токена в функции init_wfst() в 4.4. Мы также определяем утилитарную функцию display() для отображения WFST в удобном для нас виде. Как и следовало ожидать, в ячейке (1, 2) находится V.

def init_wfst(tokens, grammar):
    numtokens = len(tokens)
    wfst = [[None for i in range(numtokens+1)] for j in range(numtokens+1)]
    for i in range(numtokens):
        productions = grammar.productions(rhs=tokens[i])
        wfst[i][i+1] = productions[0].lhs()
    return wfst

def complete_wfst(wfst, tokens, grammar, trace=False):
    index = dict((p.rhs(), p.lhs()) for p in grammar.productions())
    numtokens = len(tokens)
    for span in range(2, numtokens+1):
        for start in range(numtokens+1-span):
            end = start + span
            for mid in range(start+1, end):
                nt1, nt2 = wfst[start][mid], wfst[mid][end]
                if nt1 and nt2 and (nt1,nt2) in index:
                    wfst[start][end] = index[(nt1,nt2)]
                    if trace:
                        print("[%s] %3s [%s] %3s [%s] ==> [%s] %3s [%s]" % \
                        (start, nt1, mid, nt2, end, start, index[(nt1,nt2)], end))
    return wfst

def display(wfst, tokens):
    print('\nWFST ' + ' '.join(("%-4d" % i) for i in range(1, len(wfst))))
    for i in range(len(wfst)-1):
        print("%d   " % i, end=" ")
        for j in range(1, len(wfst)):
            print("%-4s" % (wfst[i][j] or '.'), end=" ")
        print()
>>> tokens = "I shot an elephant in my pajamas".split()
>>> wfst0 = init_wfst(tokens, groucho_grammar)
>>> display(wfst0, tokens)
WFST 1    2    3    4    5    6    7
0    NP   .    .    .    .    .    .
1    .    V    .    .    .    .    .
2    .    .    Det  .    .    .    .
3    .    .    .    N    .    .    .
4    .    .    .    .    P    .    .
5    .    .    .    .    .    Det  .
6    .    .    .    .    .    .    N
>>> wfst1 = complete_wfst(wfst0, tokens, groucho_grammar)
>>> display(wfst1, tokens)
WFST 1    2    3    4    5    6    7
0    NP   .    .    S    .    .    S
1    .    V    .    VP   .    .    VP
2    .    .    Det  NP   .    .    .
3    .    .    .    N    .    .    .
4    .    .    .    .    P    .    PP
5    .    .    .    .    .    Det  NP
6    .    .    .    .    .    .    N

Возвращаясь к нашему табличному представлению, учитывая, что мы имеем Det в ячейке (2, 3) для слова an и N в ячейке (3, 4) для слова elephant, что мы должны поместить в ячейку (2, 4) для elephant? Нам нужно найти подстановку вида A → Det N. Уточнив по грамматике, мы узнаем, что мы можем ввести NP в ячейке (2, 4).

В более общем плане, мы можем ввести A в ячейку (i, j), если есть подстановка A → B C, и мы находим неконечное B в (i, k) и C в (k, j). Программа в 4.4 использует это правило для заполнения WFST. Установив значение trace - True при вызове функции complete_wfst(), мы видим вывод трассировки, который показывает, как WFST строится:

>>> wfst1 = complete_wfst(wfst0, tokens, groucho_grammar, trace=True)
[2] Det [3]   N [4] ==> [2]  NP [4]
[5] Det [6]   N [7] ==> [5]  NP [7]
[1]   V [2]  NP [4] ==> [1]  VP [4]
[4]   P [5]  NP [7] ==> [4]  PP [7]
[0]  NP [1]  VP [4] ==> [0]   S [4]
[1]  VP [4]  PP [7] ==> [1]  VP [7]
[0]  NP [1]  VP [7] ==> [0]   S [7]

Например, это говорит о том, что, поскольку мы нашли Det в wfst[2][3] и N в wfst[3][4], мы можем добавить NP к wfst[2][4].

Рисунок 4.5: Графическая структура данных: неконечные представлены как дополнительные ребра на графике.

Мы приходим к выводу, что для синтаксического анализа входной строки существует разбор, раз мы построили узел S в ячейке (0, 7), показывающий, что мы нашли предложение, которое охватывает весь вход. Конечное состояние WFST изображено на 4.5.

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

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

И, наконец, WFST не представляет структурную неоднозначность в предложении (то есть два прочтения глагольной фразы). VP в ячейке (1, 7) была фактически введена дважды, один раз для прочтения V NP и один раз для прочтения VP PP. Это разные гипотезы, а вторая переписала первую (как оказалось, это не имело значения, так как левая часть была такой же.) Графические анализаторы используют немного более богатую структуру данных и некоторые интересные алгоритмы для решения этих проблем (обратитесь к разделу Дополнительные материалы в конце этой главы для получения подробностей).

5.1 Валентность и лексикон

Давайте подробнее рассмотрим глаголы и их зависимые. Грамматика в 3.3 правильно генерирует примеры, как (15d).

(15)

a. The squirrel was frightened. b. Chatterer saw the bear. c. Chatterer thought Buster was angry. d. Joe put the fish on the log.

Эти возможности соответствуют следующим подстановкам:

То есть, was может возникнуть с последующим Adj, saw может возникнуть со последующим NP, thought может возникнуть со следующим S, а put может возникнуть с последующим NP и PP.Зависимые Adj, NP, PP и S часто называют дополнениями соответствующих глаголов, при этом существуют серьезные ограничения на то, какие глаголы могут возникнуть с какими дополнениями. В отличие от (15d), последовательности слов в (16d) плохо сформированы:

(16)

a. *The squirrel was Buster was angry. b. *Chatterer saw frightened. c. *Chatterer thought the bear. d. *Joe put on the log.

В традиции грамматики зависимостей, говорят, что глаголы в 5.1 имеют разные валентности. Ограничения валентности не только применимы к глаголам, но также и к другим классам глав.

В рамках концепций на основе грамматики фразовой структуры, различные методы были предложены для исключения неграмматических примеров в (16d). В CFG нам нужен какой-то способ ограничения подстановок грамматики, которые расширяют VP так, чтобы глаголы возникали только с правильными дополнениями. Мы можем сделать это путем деления класса глаголов на "подкатегории", каждая из которых связана с другим набором дополнений. Например, переходные глаголы, такие как chases и saw требуют следующего за ними NP объекта в качестве дополнения; то есть, они подразделены на глаголы, требующие прямых объектов NP. Если мы введем новую метку категории для переходных глаголов, а именно: TV (для переходного глагола (Transitive Verb)), то мы можем использовать ее в следующих подстановках:

VP -> TV NP
TV -> 'chased' | 'saw'

Теперь предложение *Joe thought the bear будет исключено , так как мы не включили thought как TV, но Chatterer saw the bear по-прежнему разрешено. 5.2 предоставляет дополнительные примеры меток для глагольных подкатегорий.

Валентность является свойством лексических единиц, и мы будем обсуждать ее дальше в 9. .

Дополненния часто противопоставляется модификаторам (or adjuncts?), хотя оба являются видами зависимого. Предложные фразы, прилагательные и наречия, как правило, функционируют в качестве модификаторов. В отличие от дополнений, модификаторы не являются обязательными, часто могут повторяться, и не выбираются главами таким же образом, как дополнения. Например, наречие really может быть добавлено в качестве модификатора ко всему предложению в (17d):

(17)

a. The squirrel really was frightened. b. Chatterer really saw the bear. c. Chatterer really thought Buster was angry. d. Joe really put the fish on the log.

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

5.2 Расширение масштаба

До сих пор мы рассматривали только "игрушечные грамматики", маленькие грамматики, которые иллюстрируют ключевые аспекты синтаксического анализа. Но встает очевидный вопрос, может ли подход быть расширены, чтобы покрыть большие корпусы естественных языков. Как трудно было бы построить такой набор подстановок вручную? В целом ответ такой: очень трудно. Даже если мы позволим себе использовать различные формальные устройства, которые дают гораздо более емкие представления подстановок грамматики, все равно чрезвычайно трудно держать под контролем сложные взаимодействия между многими подстановками необходимыми для покрытия основных конструкций языка. Другими словами, трудно построить грамматику модульно, чтобы одну ее часть можно было разрабатывать независимо от других ее частей. Это, в свою очередь, означает, что трудно распределить задачу написания грамматики на команду лингвистов. Другая трудность состоит в том, что по мере того, как грамматика расширяется, чтобы охватить все более широкий диапазон конструкций, увеличивается число разборов, которые допускаются для одного предложения. Другими словами, неопределенность возрастает с увеличением охвата.

Несмотря на эти проблемы, некоторые крупные совместные проекты достигли интересных и впечатляющих результатов в разработке грамматик на основе правил для нескольких языков. Примерами являются проекты Lexical Functional Grammar (LFG) Pargram, Head-Driven Phrase Structure Grammar (HPSG) LinGO Matrix и Lexicalized Tree Adjoining Grammar XTAG.

6.1 Банки деревьев и грамматики

Модуль corpus определяет ридер корпуса treebank, который содержит 10% образец корпуса Penn Treebank.

>>> from nltk.corpus import treebank
>>> t = treebank.parsed_sents('wsj_0001.mrg')[0]
>>> print(t)
(S
  (NP-SBJ
    (NP (NNP Pierre) (NNP Vinken))
    (, ,)
    (ADJP (NP (CD 61) (NNS years)) (JJ old))
    (, ,))
  (VP
    (MD will)
    (VP
      (VB join)
      (NP (DT the) (NN board))
      (PP-CLR
        (IN as)
        (NP (DT a) (JJ nonexecutive) (NN director)))
      (NP-TMP (NNP Nov.) (CD 29))))
  (. .))

Мы можем использовать эти данные, чтобы помочь нам в разработке грамматики. Например, программа в листинге 6.1 использует простой фильтр, чтобы найти глаголы, которые принимают сентенциальные дополнения. Предполагая, что у нас уже есть подстановка вида VP -> Vs S, эта информация позволяет идентифицировать конкретные глаголы, которые будут включены в расширение Vs.

def filter(tree):
    child_nodes = [child.label() for child in tree
                   if isinstance(child, nltk.Tree)]
    return  (tree.label() == 'VP') and ('S' in child_nodes)

>>> from nltk.corpus import treebank
>>> [subtree for tree in treebank.parsed_sents()
...          for subtree in tree.subtrees(filter)]
 [Tree('VP', [Tree('VBN', ['named']), Tree('S', [Tree('NP-SBJ', ...]), ...]), ...]

Корпус Prepositional Phrase Attachment, nltk.corpus.ppattach, является еще одним источником информации о валентности конкретных глаголов. Здесь мы иллюстрируем технику для копания этого корпуса. Она находит пары предложных фраз, где предлог и существительное являются фиксированными, но где выбор глагола определяет, прилагается ли предложная фраза к VP или к NP.

>>> from collections import defaultdict
>>> entries = nltk.corpus.ppattach.attachments('training')
>>> table = defaultdict(lambda: defaultdict(set))
>>> for entry in entries:
...     key = entry.noun1 + '-' + entry.prep + '-' + entry.noun2
...     table[key][entry.attachment].add(entry.verb)
...
>>> for key in sorted(table):
...     if len(table[key]) > 1:
...         print(key, 'N:', sorted(table[key]['N']), 'V:', sorted(table[key]['V']))

Среди выходных строк этой программы мы находим offer-from-group N: [ 'rejected'] V: ['received'], что свидетельствует о том, что received ожидает отдельное PP дополнение, прикрепленное к VP, в то время как rejected нет. Как и раньше, мы можем использовать эту информацию, чтобы помочь нам построить грамматику.

Коллекция NLTK включает в себя данные из распределенных задач: PE08 Cross-Framework и Cross Domain Parser Evaluation. Коллекция больших грамматик была подготовлена с целью сравнения различных анализаторов, которые могут быть получены путем загрузки пакета large_grammars (например, python -m nltk.downloader large_grammars).

Коллекция корпусов NLTK также включает в себя образец из Sinica Treebank Corpus, состоящий из 10.000 разобранных предложений, взятых из Academia Sinica Balanced Corpus of Modern Chinese. Давайте загрузим и отобразим одно из деревьев в этом корпусе.

>>> nltk.corpus.sinica_treebank.parsed_sents()[3450].draw()               

6.2 Гибельная неоднозначность

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

Давайте исследуем этот вопрос с помощью простого примера. Слово fish является как существительным, так и глаголом. Мы можем составить предложение fish fish fish, означающее fish like to fish other fish. (Попробуйте это со словом police, если вы предпочитаете что-то более осмысленное.) Вот игрушечная грамматика для "fish" предложений.

>>> grammar = nltk.CFG.fromstring("""
... S -> NP V NP
... NP -> NP Sbar
... Sbar -> NP V
... NP -> 'fish'
... V -> 'fish'
... """)

Теперь мы можем попробовать разобрать более длинную фразу, fish fish fish fish fish, которая помимо всего прочего, означает "fish that other fish fish are in the habit of fishing fish themselves". Мы используем графический парсер NLTK, о котором упоминалось ранее в этой главе. Это предложение имеет два чтения.

>>> tokens = ["fish"] * 5
>>> cp = nltk.ChartParser(grammar)
>>> for tree in cp.parse(tokens):
...     print(tree)
(S (NP fish) (V fish) (NP (NP fish) (Sbar (NP fish) (V fish))))
(S (NP (NP fish) (Sbar (NP fish) (V fish))) (V fish) (NP fish))

По мере того, как длина этого предложения идет вверх (3, 5, 7, ...) мы получаем следующие количества деревьев разбора: 1; 2; 5; 14; 42; 132; 429; 1.430; 4.862; 16.796; 58.786; 208.012; ... (Это Числа Катала́на, которые мы видели в одном из упражнений в 4). Последнее из них для предложения длиной в 23 слова, что соответствует средней длине предложений в разделе WSJ корпуса Penn Treebank. Для предложения длиной в 50 слов было бы более 10¹² разборов, а это только половина длины предложения Пяточка (1), которое маленькие дети понимают без усилий. Ни одна практическая НЛП система не может построить миллионы деревьев для предложения и выбрать подходяще в заданном контексте. Понятно, что люди также не делают этого!

Обратите внимание, что проблема не связана с нашим выбором примера. (Church & Патил, 1982) указывают, что синтаксическая двусмысленность прикрепления PP в предложениях, как (18), также растет в пропорции чисел Каталана.

(18)

Поместите блок в коробку на столе.

Так много проблем для структурной неопределенности; а что насчет лексической неоднозначности? Как только мы пытаемся построить грамматику с широким охватом, мы вынуждены сделать лексические записи в высокой степени неоднозначными с точки зрения их части речи. В игрушечной грамматике, a является только определителем, dog только существительным, а runs только глаголом. Тем не менее, в грамматике с широким охватом, a является также существительным (например, part а), dog является также глаголом (означающим следовать близко) и runs также является существительным (например, ski runs). На самом деле, со всеми словами можно установить связь как с именем: например, the verb 'ate' is spelled with three letters; в речи мы не должны ставить кавычки. Кроме того, можно превратить в глагол (to verb) большинство существительных. Поэтому синтаксический анализатор для грамматики с широким охватом будет завален двусмысленностями. Даже полная тарабарщина часто имеет прочтение, например, the a are of I. Как (Klavans & Resnik, 1996) указали, это не салат из слов, но грамматическая именная фраза, в которой are - это существительное, означающее сотую долю гектара (или 100 кв. м), а a и I существительные, обозначающие координаты, как показано на Рисунке 6.2.

Рисунок 6.2: "The a are of II": схематический чертеж 27 загонов, каждый из которых размером в один "ар" и каждый из которых определяется с помощью координат; верхняя левая ячейка - это а "ар" колонки I (вслед за Abney).

Даже если эта фраза мало вероятна, она все равно грамматична и синтаксический анализатор широкого охвата должен быть в состоянии построить дерево разбора для нее. Аналогичным образом, предложения, которые кажутся однозначными, такие как John saw Mary, оказывается, имеют другие прочтения, которые мы не предвидели (как объясняет Abney). Эта неоднозначность неизбежна и приводит к ужасающей неэффективности при разборе, казалось бы, безобидных предложений. Решение этих задач обеспечивается с помощью вероятностного синтаксического анализа, который позволяет ранжировать разборы неоднозначного предложения на основе данных из корпусов.

6.3 Взвешенная Грамматика

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

Перед их рассмотрением, мы должны понять, почему понятие грамматичности может быть градиентным. Рассмотрим глагол give. Этот глагол требует как прямой объект (вещь, которая отдается) и косвенный объект (получатель). Эти дополнения могут быть заданы в любом порядке, как показано в (19). В "предложной дательной" в форме (19а), прямой объект появляется первым, за которым следует предложная фраза, содержащая косвенный объект.

(19)

a. Kim gave a bone to the dog b. Kim gave the dog a bone

В форме "двойного объекта" в(19b) косвенный объект появляется первым, за которым следует прямой объект. В приведенном выше случае любой порядок приемлем. Тем не менее, если косвенный объект является местоимением, есть сильное предпочтение для конструкции с двойным объектом:

(20)

a. Kim gives the heebie-jeebies to me (*prepositional dative) b. Kim gives me the heebie-jeebies (double object)

Используя образец корпуса Penn Treebank, мы можем рассмотреть все экземпляры конструкций с предложным дательным и двойным объектом, включающих give, как показано на Рисунке 6.3.

def give(t):
    return t.label() == 'VP' and len(t) > 2 and t[1].label() == 'NP'\
           and (t[2].label() == 'PP-DTV' or t[2].label() == 'NP')\
           and ('give' in t[0].leaves() or 'gave' in t[0].leaves())
def sent(t):
    return ' '.join(token for token in t.leaves() if token[0] not in '*-0')
def print_node(t, width):
        output = "%s %s: %s / %s: %s" %\
            (sent(t[0]), t[1].label(), sent(t[1]), t[2].label(), sent(t[2]))
        if len(output) > width:
            output = output[:width] + "..."
        print(output)

 	
>>> for tree in nltk.corpus.treebank.parsed_sents():
...     for t in tree.subtrees(give):
...         print_node(t, 72)
gave NP: the chefs / NP: a standing ovation
give NP: advertisers / NP: discounts for maintaining or increasing ad sp...
give NP: it / PP-DTV: to the politicians
gave NP: them / NP: similar help
give NP: them / NP:
give NP: only French history questions / PP-DTV: to students in a Europe...
give NP: federal judges / NP: a raise
give NP: consumers / NP: the straight scoop on the U.S. waste crisis
gave NP: Mitsui / NP: access to a high-tech medical product
give NP: Mitsubishi / NP: a window on the U.S. glass industry
give NP: much thought / PP-DTV: to the rates she was receiving , nor to ...
give NP: your Foster Savings Institution / NP: the gift of hope and free...
give NP: market operators / NP: the authority to suspend trading in futu...
gave NP: quick approval / PP-DTV: to $ 3.18 billion in supplemental appr...
give NP: the Transportation Department / NP: up to 50 days to review any...
give NP: the president / NP: such power
give NP: me / NP: the heebie-jeebies
give NP: holders / NP: the right , but not the obligation , to buy a cal...
gave NP: Mr. Thomas / NP: only a `` qualified '' rating , rather than ``...
give NP: the president / NP: line-item veto power

Мы можем видеть сильную тенденцию более короткого дополнения стоять первым. Тем не менее, это не учитывает форму, как give NP: federal judges / NP: a raise, где одушевленность может играть определенную роль. На самом деле, там может оказаться большое количество факторов, как показано в работе (Bresnan & Hay, 2006). Такие предпочтения могут быть представлены во взвешенной грамматике.

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

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

grammar = nltk.PCFG.fromstring("""
    S    -> NP VP              [1.0]
    VP   -> TV NP              [0.4]
    VP   -> IV                 [0.3]
    VP   -> DatV NP NP         [0.3]
    TV   -> 'saw'              [1.0]
    IV   -> 'ate'              [1.0]
    DatV -> 'gave'             [1.0]
    NP   -> 'telescopes'       [0.8]
    NP   -> 'Jack'             [0.2]
    """)

>>> print(grammar)
Grammar with 9 productions (start state = S)
    S -> NP VP [1.0]
    VP -> TV NP [0.4]
    VP -> IV [0.3]
    VP -> DatV NP NP [0.3]
    TV -> 'saw' [1.0]
    IV -> 'ate' [1.0]
    DatV -> 'gave' [1.0]
    NP -> 'telescopes' [0.8]
    NP -> 'Jack' [0.2]

Иногда удобно объединить несколько подстановок в одну строку, например, VP -> TV NP [0.4] | IV [0.3] | DatV NP NP [0.3]. Для того, чтобы гарантировать, что деревья, порождаемые грамматикой образуют распределение вероятностей, PCFG грамматики накладывают ограничение, что все подстановки с заданной левой стороной должны иметь сумму вероятностей равную 1. Грамматика в 6.4 соответствует этому ограничению: для S есть только одна подстановка с вероятностью 1,0; для VP 0,3 + 0,4 + 0,3 = 1,0; и для NP 0,8 + 0,2 = 1,0. Дерево синтаксического разбора, возвращаемое методом parse() включает в себя вероятности:

>>> viterbi_parser = nltk.ViterbiParser(grammar)
>>> for tree in viterbi_parser.parse(['Jack', 'saw', 'telescopes']):
...     print(tree)
(S (NP Jack) (VP (TV saw) (NP telescopes))) (p=0.064)

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