Задача синтаксического анализа текста для тестирования языковых знаний
Автор:
Шулянский Д.В.
Источник: Международная научно-техническая конференция студентов и молодых учёных. — Донецк, ДонНТУ - 1015.
Шулянский Д.В. Задача синтаксического анализа текста для тестирования языковых знаний . Выполнен анализ задачи синтаксического анализа предложения. Рассмотрены методы синтаксического анализа, а так же рассмотрены их достоинства и недостатки.
Обеспечение взаимодействия с ЭВМ на естественном языке является важнейшей задачей исследований по искусственному интеллекту. Базы данных, пакеты прикладных программ и экспертные системы, основанные на искусственном интеллекте, требуют оснащения их гибким интерфейсом для многочисленных пользователей, не желающих общаться с компьютером на искусственном языке. В то время как многие фундаментальные проблемы в области обработки естественных языков еще не решены, прикладные системы могут оснащаться интерфейсом, понимающим естественные языки при определенных ограничениях.
Первой стадией решения задач понимания естественного языка является синтаксический разбор (parsing), т.е. анализ синтаксической структуры. В процессе синтаксического разбора проверяется, корректно ли сформировано предложение, и определяется его лингвистическая структура. За счет идентификации таких основных лингвистических отношений, как подлежащее-сказуемое, сказуемое-дополнение, в процессе синтаксического разбора строится базис для семантической интерпретации. Результаты анализа зачастую представляются в виде дерева разбора (parsetree). В синтаксическом анализаторе используются знания синтаксиса языка, морфологии и, частично, семантики.
Синтаксический анализ текста представляет собой исследование структуры предложения текста с целью установления синтаксических связей между членами предложения. В интеллектуальных системах такой анализ выполняется синтаксическим анализатором.
Синтаксический анализатор (парсер) — это программа или часть программы, выполняющая синтаксический анализ.
В ходе синтаксического анализа исходный текст преобразуется в структуру данных, обычно — в дерево, которое отражает синтаксическую структуру входной последовательности и хорошо подходит для дальнейшей обработки.
Как правило, результатом синтаксического анализа является синтаксическое строение предложения, представленное либо в виде дерева зависимостей, либо в виде дерева составляющих, либо в виде некоторого сочетания первого и второго способов представления.
Синтаксический анализатор должен распознать структуру предложения, а именно синтаксические зависимости слов. В результате должно быть либо построено синтаксическое дерево, либо выявлены составляющие. Обычно грамматика строится так, чтобы на выходе получалось синтаксическое дерево, позволяющее выполнять разнообразные трансформации лексического содержания с пересогласованием зависимых слов, а также легко выделять семантику, в частности - применять алгоритм взвешивания альтернативных вариантов построения дерева, о котором речь пойдет ниже.
Предложение может допускать несколько альтернативных вариантов связывания слов. В этом случае анализатор пытается применять некоторые эвристики и базу знаний, но может в конце концов вернуть несколько вариантов синтаксического дерева. Наличие нескольких итоговых вариантов разбора может означать не только недостаточный набор правил в языковой модели, но и присущую данному предложению неоднозначность, устраняемую только учетом более широкого контекста.
Пример построения синтаксического дерева приведён на рисунке 1.
Рис1. Пример построения синтаксического дерева
Основной проблемой обработки естественного языка является языковая неоднозначность. Одой из таких неоднозначностей является синтаксическая. Приведём пример такой неоднозначности: во фразе «Time flies like an arrow» для ЭВМ неясно, идет ли речь о времени, которое летит, или о насекомых, т.е. является ли слово flies глаголом или существительным. Данная проблема может быть решена пуём дальнейшего семантического анализа текста, который определяет контекст нескольких предложений, с помощью чего можно выбрать корректное синтаксическое дерево предложения.
Большинство известных методов анализа принадлежат одному из двух классов, один из которых объединяет нисходящие (top-down) алгоритмы, а другой – восходящие (bottom-up) алгоритмы. Происхождение этих терминов связано с тем, каким образом строятся узлы синтаксического дерева: либо от корня (аксиомы грамматики) к листьям (терминальным символам), либо от листьев к корню.
Нисходящие анализаторы строят вывод, начиная от аксиомы грамматики и заканчивая цепочкой терминальных символов. С нисходящими анализаторами связаны так называемые LL-грамматики, которые обладают следующими свойствами:
· Они могут быть проанализированы без возвратов
· Первая буква L означает, что мы просматриваем входную цепочку слева направо (leftto-rightscan)
· Вторая буква L означает, что строится левый вывод цепочки (leftmostderivation).
Популярность нисходящих анализаторов связана с тем, эффективный нисходящий анализатор достаточно легко может быть построен вручную, например, методом рекурсивного спуска. Кроме того, LL-грамматики легко обобщаются: грамматики, не являющиеся LL-грамматиками, обычно могут быть проанализированы методом рекурсивного спуска с возвратами.
С другой стороны, восходящие анализаторы могут анализировать большее количество грамматик, чем нисходящие, и поэтому именно для таких методов существуют программы, которые умеют автоматически строить анализаторы. С восходящими анализаторами связаны LR-грамматики. В этом обозначении буква L по-прежнему означает, что входная цепочка просматривается слева направо (left-to-rightscan), а буква R означает, что строится правый вывод цепочки (rightmostderivation).
Обоим классам присущи важные общие черты. Они недетерминированы, то есть могут выдавать множество альтернативных вариантов синтаксического разбора, хотя оба стремятся отсечь недостоверные варианты. Они управляются правилами, которые задаются вручную. Они позволяют задавать типы связей в создаваемом синтаксическом дереве. Наконец, оба алгоритма реализуют идею динамического программирования для эффективного снижения времени разбора.
Выбор между восходящим и нисходящим алгоритмом обычно происходит автоматически. Встроенный в грамматический движок планировщик анализа сначала пытается распарсить предложение самым точным нисходящим алгоритмом, а в случае неудачи переключается на более устойчивый к ошибкам восходящий анализ, который работает очень быстро и способен разобрать даже очень длинные предложения, игнорируя непонятные фрагменты. В том случае, когда восходящий анализ не может точно определить синтаксическую структуру предложения, он может вернуть несколько вариантов синтаксического дерева. Таким образом, использование двух типов анализа даёт возможность гарантированного получения возможной структуры предложения.
Восходящий и нисходящий алгоритмы воплощают "классический" подход к созданию грамматики естественного языка. Этот подход заключается в создании набора правил, которые работают со словами и грамматическими категориями слов. Правила обычно пишутся на специальном предметно-ориентированном языке (DSL), чтобы упростить изменение грамматики без перекомпиляции кода парсера и дать в руки разработчику грамматики эффективный набор средств, обычно имеющих мало общего с обычными императивными языками программирования.
Правила описывают порядок распознавания различных синтаксических конструкций естественного языка. Исходный текст правил читается компилятором словаря и преобразуется в сильно оптимизированное внутреннее представление, фактически в набор команд для виртуальной машины.
В терминах теории автоматов, набор правил реализует распознающую грамматику для предложений на естественном языке. Результатом работы анализатора является не только подтверждение того, что входное предложение с определенной достоверностью принадлежит к распознаваемому набору синтаксических конструкций и идеоматических оборотов, но и набор альтернативных синтаксических деревьев с весами в случае неоднозначности анализа.
Далее приводятся характерные особенности структурного нисходящего парсера (далее СНП), работающего в режиме “анализ через синтез”.
(+) СНП даст 100% верный разбор предложения на составляющие, если используемая грамматика адекватно описывает такие предложения. Процесс разбора структурным парсером очень похож на математически строгое доказательство.
(+) СНП найдет все возможные варианты разбора предложения, если грамматика содержит неоднозначности.
(+) СНП способен делать ослабляющие допущения и оценивать выполненный анализ с учетом таких допущений.
(+) СНП может учитывать контекст любой ширины, вплоть до всего предложения. Другими словами, учитываются не только непосредственные соседи, но также связанные синтаксически части предложения, находящиеся на любом удалении от слова.
(+/-) СНП не имеет внутреннего состояния и выполняет разбор за 1 заход. Нет естественного способа остановить выполнения разбора в промежуточной стадии и получить частичные результаты. Эта особенность имеет также важное положительное следствие. Отсутствие состояния позволяет распараллеливать выполнение анализа.
(-) СНП естественным образом реализует поиск в глубину. Это может приводить к тому, что из-за отсутствия хороших эвристик очень много времени будет уделено проверке заведомо проигрышным вариантам анализа, а выигрышный путь в пространстве состояний так и не будет найден до исчерпания лимита времени.
(-) Следствием отсутствия состояния является трудность отладки. Отладчик парсера предоставляет некоторые ограниченные возможности, включая задание точек останова в некоторых местах правил и просмотр локального состояния вывода. Однако наличие множества параллельных процессов вывода делает интерактивную отладку крайне трудной в реализации и использовании. В реальности самым удобным способом отладки является просмотр пошаговой трассировки для полученных результатов.
(-) Если структура предложения не выводится правилами грамматики в точном виде, то СНП вообще ничего не выведет, если не принимать специальные меры. Под такими специальными мерами подразумевается неполный анализ.
(-) СНП реализует в большей степени математическую концепцию, чем языковую. В сочетании с декларативным и функциональным стилем задания правил вывода это может поднять порог вхождения для незнакомого с математической лингвистикой разработчика, привыкшего к императивному стилу программирования.
(+) СНП работает с предложением в ленивом стиле. Начав с левой границы, он постепенно выводит синтаксическую структуру, запрашивая у лексера новые и новые слова. Более того, СНП очень хорошо элегантно работают с графом токенизации, который получается в ходе лексического анализа.
Так как данный алгоритм анализа в целом основан на использовании таких же правил, как рассмотренный ранее нисходящий анализ через синтез, то он в определенной степени наследует некоторые его особенности. В частности, можно упомянуть необходимость ручного описания грамматики с большим количеством абстрактных категорий и некоторая сложность с пониманием процесса сопоставления правил.
Далее перечисляются только собственные особенности данного алгоритма.
1. Недетерминированность процесса. Входная цепочка токенов может породить несколько альтернативных новых цепочек после применения правила переписывания. Выбор оптимального результата выполняется с помощью механизма задания баллов для правил переписывания, либо с использованием общих с алгоритмов анализ-через-синтез приемов - ассоциации слов, tree scorer.
2. Итерации, состояние. Автомат имеет явное состояние. Процесс применения правил переписывания имеет заранее известные точки, в которых его можно прервать и получить текущие результаты связывания. Благодаря этому можно реализовать управление анализом по таймауту - привязывания деталей будет продолжаться до тех пор, пока автомат не перейдет в конечное состояние (успех - построен синтаксический граф с одним корнем) либо пока не будет исчерпан заданный лимит времени. Более того, механизм оценки достоверности переписывания позволяет создавать планировщик итераций, который меняет приоритет того или иного варианта анализа динамически.
3. Простота отладки. Процесс переписывания можно прервать в момент применения очередного правила и увидеть весь текущий набор результатов.
4. Порядок задания правил имеет значение.
5. Работа с длинными предложениями. Можно задать такие правила, что автомат будет работать в минимальным контекстом - например, ограничить его правилами для пар слов. К примеру, связывать частицу НЕ с наречиями, прилагательными, деепричастиями и глаголами и т.д. Поэтому автомат может выполнять постепенное построение синтаксического дерева для очень длинных предложений, не пытаясь сразу охватить слишком большие фрагменты текста.
6. Правила переписывания используют весь набор возможностей для задания опорных точек контекста. Это позволяет задавать правила, которые сопоставляются с контекстом заранее неизвестной длины. Кроме того, доступны такие средства, как 1) теоретико-множественные операторы для проверки вхождения токена в именованное множество, 2) проверка с помощью регулярных выражений, 3) использование пользовательских функций, написанных на встроенном языке, 4) проверка согласования фрагментов сопоставляемого контекста.
7. Основной недостаток итерационного анализа - меньшая эффективность в равных условиях с анализом-через-синтез. В силу некоторых алгоритмических особенностей второго варианта компилятор словаря может выполнить весьма агрессивную оптимизацию, которая ускоряет процесс синтеза с проверкой. Более того, анализ-через-синтез реализует очень эффективную оптимизацию процесса во время работы. Со своей стороны, итерационный анализ очень ограничен в возможных оптимизациях. Эффективность анализа в нем приносится в жертву итеративности и возможности постепенно улучшать результат, динамически отслеживая прогресс.
8. Итерационный анализ можно начинать не просто с исходной цепочки токенов, а попытаться "прикинуть" общую структуру предложения с помощью набора специальных правил. Например, можно найти в предложении местоимение я и согласующийся с ним глагол, предположить из связь как подлежащего и сказуемого и далее уже запускать итерации, опираясь на эти ключевые токены.
Задача тестирования языковых знаний заключается в написании тестируемым определенного предложения, которое в дальнейшем будет проходить синтаксический анализ.
Синтаксический анализ написанного предложения определяет синтаксическое дерево, с помощью которого будет проверяться согласованность слов в предложении, а также правильность порядка слов. При этом важным моментом является то, что правильное решение может быть не единственным, т.е. один и тот же смысл может быть передан разной конструкцией предложения. Для определения подобности этих предложений и используются синтаксические деревья предложений, в которых будут указаны части речи, определено использованное время действия, объект, над которым это действие совершалось и прочие понятия.
1. Люгер, Джордж, Ф. «Искусственный интеллект: стратегии и методы решения сложных проблем». Вильямс, 2003 г. -864 с.
2. Синтаксический анализатор грамматического словаря [электронный ресурс] Режим доступа: http://www.solarix.ru/for_developers/docs/rules.shtml
3. Синтаксический анализ [электронный ресурс] Режим доступа: http://ict.edu.ru/ft/005128//ch6.pdf
4. Диковицкий В. В., Шишаев М. Г. «Обработка текстов естественного языка в моделях поисковых систем» 2010 г.