42
но недопустимы с точки зрения семантики. Чтобы выбирать правильные
варианты разбора необходима возможность их ранжировать. С одной стороны,
это позволяет найти лучший в соответствии с некоторым критерием результат,
а с другой стороны, это может ускорить разбор, поскольку анализатор в случае
неоднозначности будет направляться в наиболее весомые ветви, и, таким
образом, скорее будет построено наиболее адекватное синтаксическое дерево.
Для ранжирования вариантов синтаксического разбора широкое применение
нашли статистические подходы. Наиболее известным статистическим
подходом к задаче построения деревьев составляющих является применение
стохастических контекстно- свободных (СКС) грамматик. СКС-грамматики
отличаются от обычных КС- грамматик тем, что каждому правилу грамматики
назначена вероятность. Задачей синтаксического анализатора в этом случае
является нахождение наиболее вероятного варианта разбора предложения.
СКС-грамматики автоматически строятся на основе банков синтаксических
деревьев – корпусов, в которых предложениям вручную или
полуавтоматически сопоставлены синтаксические деревья. Например, для
английского языка наиболее известным подобным банком является Penn
Treebank. Для разбора предложений на ЕЯ по СКС-грамматикам в основном
применяют модификации, ранее представленных в этом разделе алгоритмов,
использующих принципы динамического программирования (CYK, Эрли,
«chart-parser»). Подходы, предложенные исследователями, различаются в
основном методами моделирования вероятностей синтаксических деревьев, а
также способами решения задачи поиска дерева с максимальной
вероятностью.
Первые СКС-грамматики в основном опирались на синтаксические
правила взаимодействия частей речи. Однако эксперименты показали, что
статистической информации о сочетаемости частей речи недостаточно для
разрешения неоднозначности ЕЯ. Оценки качества подобных анализаторов
были значительно ниже, чем у анализаторов, использующих большие наборы
43
эвристик. Развитием статистического подхода стали лексикализованные
стохастические контекстно свободные грамматики. В правилах этих
грамматик помимо частей речи учитывается также лексика и статистика
встречаемости слов. Эта модификация значительно повысила качество
статистических методов синтаксического анализа.
2.2.2. Методы построения синтаксических деревьев зависимосте.
Первые методы построения деревьев зависимостей, как и методы
построения деревьев составляющих были основаны на вручную созданных
грамматиках, записанных в некотором формализме. Можно выделить
несколько классов формализмов задания грамматик зависимостей и подходов
к построению деревьев зависимостей.
К первому классу относятся формализмы, которые близки к
формальным грамматикам Хомского. Они, как правило, способны
моделировать лишь проективные языковые структуры. Для синтаксического
анализа по таким грамматикам часто используют подходы и алгоритмы
разбора, применяемые для построения деревьев составляющих – алгоритмы,
использующие динамическое программирование для решения проблемы
неоднозначности и недетерминированности грамматик, например, алгоритм
Эрли или CYK.
Другой класс формализмов предполагает задание грамматик
зависимостей в виде набора ограничений, что позволяет с помощью них
моделировать как проективные, так и непроективные языковые структуры [18,
37]. Синтаксический анализ с точки зрения таких формализмов – это задача
поиска в полном графе зависимостей дерева, которое удовлетворяет всем
ограничениям грамматики. Заметим, что подобная задача является NP-полной,
поэтому для ее решения применяют подходы, которые направленно
ограничивают зону поиска правильных с точки зрения грамматики
синтаксических деревьев.
44
Еще один класс подходов к представлению грамматик зависимостей
заключается в задании некоторой системы правил (набора булевских
функций) и детерминированного алгоритма разбора текста. Правила и
алгоритм однозначно
задают синтаксическое дерево зависимостей. Этот подход был развит в
работах Михаэля Ковингтона [38]. Он предложил простой алгоритм разбора,
со сложностью O(n
2
): начиная с первого слова в предложении, сканировать
слова слева направо и пытаться установить зависимость между текущим
словом и всеми предыдущими словами (причем текущее слово может быть как
главным, так и зависимым). М. Ковингтон показал, что этот алгоритм и набор
булевских функций
????(????
1
, ????
2
) = {
????????????????, если между ????
1
и ????
2
можно установить связь
????????????????????, если между ????
1
и ????
2
нельзя установить связь
позволяют строить корректные синтаксические деревья, которые
задаются другими более сложными формализмами грамматик зависимостей.
На сегодняшний день акцент исследований сместился с поиска
наилучшей лингвистической теории и попыток ее формализации в виде
грамматики зависимостей к поиску методов и подходов, так или иначе,
использующих методы машинного обучения, и к моделированию с их
помощью особенностей ЕЯ, присутствующих в обучающих данных.
Применение методов машинного обучения с учителем для построения
деревьев зависимостей показало ряд преимуществ по сравнению с подходами,
основанными на вручную составленных грамматиках, среди которых –
многократное снижение трудоемкости создания синтаксических анализаторов
при наличие крупного размеченного корпуса. На сегодняшний день
существует два основных подхода к построению деревьев зависимостей, в
которых используются методы машинного обучения: графовый подход (graph-
45
based dependency parsing) и синтаксический разбор на основе системы
переходов (transition-based parsing).
2.2.3. Графовы подход к построению синтаксических деревьев
зависимосте.
Графовый подход предполагает, что строится модель, которая позволяет
количественно оценивать синтаксические деревья предложения (графы
зависимостей). Как правило, модель факторизует граф зависимостей на
элементарные компоненты (в моделях первого порядка – это одинарные дуги,
в моделях второго порядка – это пара смежных дуг), которым назначаются
веса. Задача синтаксического анализа в этом случае сводится к поиску в
полном графе предложения дерева зависимостей с максимальной оценкой.
В первых работах, реализующих графовый подход, использовались
порождающие модели для оценки графа зависимостей: проводилось
моделирование совместной вероятности появления слов, дуг, и
синтаксических меток дуг, а оценка всего дерева представлялась как
произведение этих вероятностей. В более поздних работах применяются
дискриминантные модели оценки. Чаще всего используется аддитивная
модель. В этом случае в модели первого порядка оценка всего графа
складывается из весов его элементарных компонент и выражается следующим
образом:
????????????????????_???????????????? (y) = ∑ ????????????????????(????, ????). (????,????)∈????
Здесь ???? – граф зависимостей; (????, ????) – ориентированная дуга графа ????: (????, ????)
∈ ????, обозначающая синтаксическую зависимость.
Обычно вес дуги задается линейной функцией:
????????????????????(????,????)=???? ∙????(????,????).
Здесь ???? – вектор весов признаков – параметр модели; ????(????, ????) – функция
получения вектора признаков дуги (????, ????).
46
Пусть имеется предложение s и пусть Y(s) – множество всех деревьев,
которые можно построить на предложении s. Задачу синтаксического анализа
в введенных терминах можно записать следующим образом:
????????????????????(????) = argmax ????????????????????_???????????????? (????, ???? ). ????∈????(????)
Одной из первых работ, в которой описывается графовый подход к
синтаксическому анализу, является работа Джейсона Айзенера. В ней он
предложил порождающую модель оценки графа зависимостей и алгоритм
синтаксического анализа, схожий с алгоритмом CYK. Он позволяет строить
(или находить в полном графе предложения) проективные синтаксические
деревья зависимостей за время O(n
3
).
Позже было показано, что дискриминантные модели могут успешно
применяться вместе с алгоритмом Айзенера для построения проективных
деревьев. Также предложена модификация, которая в рамках графового
подхода позволила строить непроективные деревья. Вместо алгоритма
Айзенера был использован алгоритм поиска максимального остовного дерева
в графе. Этот анализатор известен в литературе как MST parser (maximum
spanning tree parser). Было обнаружено, что сложность построения
произвольного (непроективного) синтаксического дерева с помощью
алгоритма поиска максимального остового дерева составляет O(n
2
), что
меньше чем сложность алгоритма Айзенера, строящего проективные деревья.
Исследователи также показали на примере чешского языка, что эта
модификация позволяет добиваться лучшего качества синтаксического
анализа для языков со свободным порядком слов, которые допускают большое
количество непроективных связей. При этом скорость анализа выше по
сравнению с методом, в котором применяется алгоритм Айзенера. Однако
применение алгоритма поиска максимального остовного дерева в MST
анализаторе может приводить к незначительным уменьшениям качества
47
анализа для языков, в которых количество непроективных связей мало
(например, в английском).
В последующих работах, проведенных в рамках графового подхода к
синтаксическому анализу, исследовалось применение моделей оценки графа
зависимостей второго порядка. Было показано, что поиск непроективных
деревьев зависимостей в случае использования модели второго порядка
является NP-полной задачей. Поэтому исследования в этом направлении в
основном были ограничены поиском методов построения только проективных
деревьев.
2.2.4. Метод синтаксического анализа на основе системы
переходов.
В методе синтаксического анализа на основе системы переходов
строится и обучается модель для оценки переходов от одного состояния
синтаксического анализатора к другому состоянию. В общем случае алгоритм
анализа сводится к предсказанию на основе построенной модели действия
анализатора и перехода из текущего состояния в новое состояние.
Предсказания и переходы осуществляются до тех пор, пока не будет построено
синтаксическое дерево зависимостей.
Этот подход был изначально предложен в работах Куда и Ямада
Мацумото. В них использовался алгоритм типа перенос-свертка со
сложностью O(n
2
), позволявший строить проективные синтаксические
деревья зависимостей. Для предсказания переходов анализатора
использовался метод опорных векторов. Отметим, что в качестве признаков
использовались части речи и леммы связываемых слов и их контекста.
Подход на основе системы переходов был развит в работах оакима
Нивре. Он предложил алгоритм для построения проективных синтаксических
деревьев за время O(n). Анализатор . Нивре позволяет не только строить
синтаксические деревья предложений, но также определять тип связей и
назначать им метки. Это позволило включить в модель для предсказания
48
переходов признаки, которые можно извлечь из частично построенного
синтаксического дерева. Изначально в анализаторе применялись метрические
методы классификации для предсказания переходов, однако в дальнейших
исследованиях их место занял метод опорных векторов, поскольку было
показано, что он дает лучшие результаты.
Алгоритм Нивре последовательно обрабатывает слова предложения
слева направо. Слово, его контекст и частично построенное синтаксическое
дерево задают признаки, которые классификатор на основе машинного
обучения использует для предсказания следующего действия (перехода)
анализатора. В алгоритме используется стек и предусмотрены следующие
типы переходов: Left-Arc – установить зависимость между входным словом
(главное) и словом на вершине стека (подчиненное), вытолкнуть одно слово
из стека;
Right-Arc – установить зависимость между словом на вершине стека (главное)
и входным словом (подчиненное), положить входное слово в стек;
Reduce – вытолкнуть одно слово из стека (допускается только в том случае,
если слово на вершине стека имеет родителя);
Shift – положить входное слово в стек (допускается только в том случае, если
входное слово, т.е. анализатор не пришел в конец предложения).
При выполнении действия Right-Arc и Left-Arc анализатор обращается к
классификатору также для определения типа синтаксической связи. Алгоритм
гарантирует построение проективного дерева. Если допустить, что в случае,
когда анализатору необходимо выполнить действие Reduce, и слово на
вершине стека не имеет родителя, анализатор все равно выталкивает слово из
стека и делает его подчиненным вспомогательной вершине ROOT, то
построенные деревья также будут полностью связанными.
Обучение классификатора, предсказывающего переходы, проходит
аналогично синтаксическому анализу. Анализатор просматривает слова
предложения слева направо и определяет действие, которое необходимо
49
предпринять на текущем шаге, чтобы построить синтаксическое дерево из
обучающего корпуса. Это действие и набор признаков используются как
обучающий пример.
В работе [52] представлена также модификация анализатора, которая
позволяет снять ограничение на проективность синтаксического дерева. Суть
этой модификации состоит в том, что все непроективные связи преобразуются
в проективные связи со специальными метками. Затем уже полностью
проективное дерево используется для обучения. В ходе анализа метки
расшифровываются и построенное анализатором проективное дерево
преобразуется в непроективное.
Подход к синтаксическому анализу на основе системы переходов был
реализован в программном пакете MaltParser [53, 54]. Этот пакет включает в
себя различные алгоритмы синтаксического анализа, включая алгоритм Нивре
и алгоритм Ковингтона, а также реализации нескольких методов машинного
обучения для предсказателей переходов. Из-за своей эффективности и
производительности MaltParser на сегодняшний день является одним из
наиболее широко используемых синтаксических анализаторов. Исследования
по применению MaltParser проводились для многих языков, в том числе и для
русского [55, 56, 3].
2.2.5. Системы синтаксического анализа текстов на русском языке.
Большой вклад в развитие синтаксических анализаторов на русском
языке внесли работы по созданию систем машинного перевода. Поскольку для
того, чтобы добиться приемлемого качества перевода, необходим
синтаксический анализ, разработчикам подобных системы приходилось
вкладывали большие силы в создание синтаксических анализаторов текстов на
русском языке. Одна из наиболее известных систем в этой области была
создана коллективом под руководством Ю.Д. Апресяна: ЭТАП-1, ЭТАП-2,
ЭТАП-3 [57, 8]. Несмотря на долгую историю создания этих систем, проект
ЭТАП-3 продолжает развиваться, в том числе в сторону применения
50
статистических методов [58]. В системах машинного перевода Retrans и
МетаФраз, разработанных коллективном под руководством Г.Г. Белоногова,
реализован семантико-синтаксический анализатор текстов на русском языке
[59 – 61]. Стоит отметить поверхностный синтаксический анализатор
программного пакета AOT.ru, который разрабатывался для системы
машинного перевода Dialing [62].
Работы в области синтаксического анализа текстов на русском языке в
настоящий момент продолжаются коллективом под руководством Т.Ю.
Кобзаревой, Д.Г. Лахути [63, 64], а также многими другими исследователями,
например, [65, 66].
Важной вехой в области синтаксического анализа текстов на русском
языке стало создание Синтаксически размеченного корпуса русского языка
СинТагРус [67]. Это позволило успешно применить к задаче синтаксического
анализа подходы на основе машинного обучения, которые показали весьма
высокую эффективность [58, 55]. По-видимому, в будущем статистические
методы будут играть все большую роль в синтаксическом анализе текстов на
русском языке.
51
ГЛАВА 3. ИСПОЛЬЗОВАНИЕ ИНСТРУМЕНТОВ
СИНТАКСИЧЕСКОГО АНАЛИЗА, ИХ ХАРАКТЕРИСТИКА
3.1. Использование Maltparser для синтаксического анализа.
MaltParser — инструмент для работы с деревьями зависимостей.
Позволяет построить модель по размеченному корпусу и строить
деревья для новых данных основываясь на этой модели. В то время как
традиционные парсеры опираются на подаваемые на вход грамматики, данный
инструмент использует входные данные для определения способа работы
алгоритма и опирается на деревья зависимостей.
MaltParser является реализацией индуктивного анализа зависимостей
(Nivre 2005,), где синтаксический анализ предложения составляет деривацию
структуры зависимостей, и где индуктивное машинное обучение используется
для инструктирования парсера на недетерминированных точках выбора. Этот
методология анализа базируется на трех основных компонентах:
1. Детерминированные алгоритмы синтаксического анализа для
построения зависимостей
графов (Ямада и Мацумото, 2003; Nivre,2003)
2. Основанные на предыстории модели для прогнозирования
следующего действия анализатора (черный и соавт., 1992; Magerman,
1995;Ratnaparkhi, 1997; Коллинз, 1999)
3. Дискриминативное машинное обучение для соответствия
предыдущих событий действиям парсерам
Учитывая ограничения, наложенные на эти компоненты, MaltParser был
разработан, чтобы дать максимальную гибкость для варьирования
компонентов независимо друг от друга.
Любой детерминированный алгоритм анализа совместимый с
архитектурой MaltParser должен работать со следующим набором структур
данных, который также обеспечивает интерфейс для модели: