Определение с помощью обучения вероятностей для грамматики PCFG
Головой словосочетания называется самое важное слово, например существительное в именном словосочетании.
При создании любой грамматики PCFG приходится преодолевать все сложности, связанные с формированием грамматики CFG, и наряду с этим решать проблему задания вероятностей для каждого правила. Такие обстоятельства наводят на мысль, что может оказаться более приемлемым подход, предусматривающий определение грамматики по имеющимся данным с помощью обучения, чем подход, основанный на инженерии знаний. Как и в случае «распознавания речи, могут применяться данные двух типов — прошедшие и не прошедшие синтаксический анализ. Задача намного упрощается, если данные уже преобразованы в деревья с помощью синтаксического анализа лингвистами (или по меньшей мере носителями соответствующего естественного языка, прошедшими специальное обучение). Создание подобной текстовой совокупности требует больших капиталовложений, и в настоящее время самые крупные из таких совокупностей содержат "всего лишь" около миллиона слов. А если имеется некоторая совокупность деревьев, то появляется возможность создать грамматику PCFG путем подсчета (и сглаживания). Для этого достаточно просмотреть все узлы, в которых корневым является каждый нетерминальный символ, и создать правило для каждой отдельной комбинации дочерних элементов в этих узлах. Например, если какой-то символ NP появляется 100 тысяч раз и имеется 20 тысяч экземпляров NP со списком дочерних элементов [NP, РР], то создается правило
NP —> NP РР [0.20]
Если же текст не подвергнут синтаксическому анализу, то задача значительно усложняется. Это прежде всего связано с тем, что фактически приходится сталкиваться с двумя разными проблемами — определение с помощью обучения структуры грамматических правил и определение с помощью обучения вероятностей, связанных с каждым правилом (с аналогичным различием приходится сталкиваться при определении с помощью обучения параметров нейронных или байесовских сетей).
На данный момент примем предположение, что структура правил известна и предпринимается лишь попытка определить вероятности с помощью обучения. Для этого может использоваться подход на основе алгоритма ожидания-максимизации (expectation—maximization — ЕМ), как и при обучении моделей НММ. В процессе обучения мы будем пытаться определить такие параметры, как вероятности правил. Скрытыми переменными являются деревья синтаксического анализа, поскольку неизвестно, действительно ли строка слов Wi...Wj сформирована с помощью правила X—ж. На этапе Е оценивается вероятность того, что каждая подпоследовательность сформирована с помощью каждого отдельного правила. Затем на этапе м оценивается вероятность каждого правила. Весь этот процесс вычисления может осуществляться в режиме динамического программирования с помощью алгоритма, называемого внутренним—внешним алгоритмом, по аналогии с прямым—обратным алгоритмом, применяемым для моделей НММ.
На первый взгляд причины продуктивного функционирования внутреннего-внешнего алгоритма кажутся непостижимыми, поскольку он позволяет успешно сформировать логическим путем грамматику на основании текста, не прошедшего синтаксический анализ. Но этот алгоритм имеет несколько недостатков. Во-первых, он действует медленно; этот алгоритм характеризуется временнь/ми затратами О (л313), где п — количество слов в предложении; t — количество нетерминальных символов. Во-вторых, пространство вероятностных присваиваний очень велико и практика показала, что при использовании этого алгоритма приходится сталкиваться с серьезной проблемой, связанной с тем, что он не выходит из локальных максимумов. Вместо него могут быть опробованы такие альтернативные варианты, как эмуляция отжига, за счет еще большего увеличения объема вычислений. В-третьих, варианты синтаксического анализа, присвоенные с помощью полученных в результате грамматик, часто трудно понять, а лингвисты находят их неудовлетворительными. В результате этого задача комбинирования знаний, представленных с помощью способов, приемлемых для человека, с данными, которые получены с помощью автоматизированного индуктивного логического вывода, становится затруднительной.
Определение с помощью обучения структуры правил для грамматики PCFG
Теперь предположим, что структура грамматических правил неизвестна. В таком случае сразу же возникает проблема, связанная с тем, что пространство возможных множеств правил является бесконечным, поэтому неизвестно, какое количество правил необходимо предусмотреть и какую длину должно иметь каждое правило. Один из способов решения этой проблемы состоит в том, чтобы организовать составление грамматики с помощью обучения в нормальной форме Хомского; это означает, что каждое правило должно находиться в одной из следующих двух форм:
X -> Y Z X -> t
где х, Уи Z — нетерминальные символы; t — терминальный символ. В виде грамматики в нормальной форме Хомского, которая распознает точно такой же язык, может быть представлена любая контекстно-свободная грамматика. В таком случае появляется возможность принять произвольное ограничение, согласно которому количество нетерминальных символов будет равно п, и тем самым будет получено n3+nv правил, где v— количество терминальных символов. Но практика показала, что такой подход является эффективным только применительно к небольшим грамматикам. Предложен также альтернативный подход, называемый слиянием байесовских моделей, аналогичный подходу с применением модели Sequitur (раздел 22.8). В этом подходе предусматривается формирование на первом этапе локальных моделей (грамматик) для каждого предложения, а затем использование минимальной длины описания для слияния моделей.