авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:   || 2 | 3 | 4 | 5 |   ...   | 6 |
-- [ Страница 1 ] --

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

Восточно-Сибирский государственный технологический университет

Л.В. Найханова, И.С. Евдокимова

МЕТОДЫ И АЛГОРИТМЫ

ТРАНСЛЯЦИИ

ЕСТЕСТВЕННО-ЯЗЫКОВЫХ ЗАПРОСОВ К БАЗЕ ДАННЫХ

В SQL-ЗАПРОСЫ

Издательство ВСГТУ

Улан-Удэ – 2004

УДК 004.8

ББК 32.813

Н20

Рецензенты: доктор технических наук, зав. кафедрой Прикладная математика ВСГТУ А.Д. Мижидон, кандидат технических наук, доцент, зав. кафедрой Информационные технологии Б.М. Степанов.

Найханова Л.В., Евдокимова И.С.

Н20 Методы и алгоритмы трансляции естественно-языковых запросов к базе данных в SQL-запросы: Монография. – Улан-Удэ: Изд-во ВСГТУ, 2004. – 148 с.: ил.

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

Предназначена для аспирантов и студентов старших курсов специальностей «Программное обеспечение вычислительной техники и автоматизированных систем» и 351500 «Математическое обеспечение и администрирование информационных систем».

Ключевые слова: естественно-языковой интерфейс, естетственно-языковой запрос, sql запрос, лингвистический транслятор, морфологический анализ, синтаксический анализ, система продукций, аппарат описания формальных моделей, база знаний, модель трансляции, метаописание базы данных, закономерности проблемной среды, метод линейной резолюции, методы и алгоритмы трансляции Печатается по решению редакционно-издательского совета ВСГТУ ББК 32. Найханова Л.В. и сост., 2004 г.

ВСГТУ, 2004 г.

ОГЛАВЛЕНИЕ ВВЕДЕНИЕ...................................................................................................................................... 1. ОБЗОР И АНАЛИЗ МЕТОДОВ РЕШЕНИЯ ЗАДАЧИ...................................................... 1.1. СТРУКТУРА ЛИНГВИСТИЧЕСКОГО АНАЛИЗАТОРА....................................................................... 1.2. АНАЛИЗ МЕТОДОВ И ПОДХОДОВ МОРФОЛОГИЧЕСКОГО АНАЛИЗА............................................. 1.3. АНАЛИТИЧЕСКИЙ ОБЗОР МЕТОДОВ СИНТАКСИЧЕСКОГО АНАЛИЗА........................................... 1.4. АНАЛИТИЧЕСКИЙ ОБЗОР СЕМАНТИЧЕСКИХ МОДЕЛЕЙ.............................................................. 1.5. ВЫВОДЫ ПО ПЕРВОЙ ГЛАВЕ...................................................................................................... 2. МОДЕЛЬ ЛИНГВИСТИЧЕСКОГО ТРАНСЛЯТОРА..................................................... 2.1. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ТРАНСЛЯТОРА.............................................................................. 2.2. АППАРАТ ОПИСАНИЯ ФОРМАЛЬНЫХ МОДЕЛЕЙ........................................................................ 2.2.1. Введение в системы продукций.......................................................................................... 2.2.2. Описание формального аппарата...................................................................................... 2.3. МОДЕЛЬ МОРФОЛОГИЧЕСКОГО АНАЛИЗА.................................................................................. 2.3.1. Содержательное описание модели морфологического анализа..................................... 2.3.1.1. Словари и таблицы совместимости......................................................................

........... 2.3.1.2. Алгоритм морфологического анализа............................................................................. 2.3.2. База правил морфологического анализа............................................................................. 2.3.2.1. Сорта морфологического анализа................................................................................... 2.3.2.2. Типовые предикаты условий применимости продукций морфологического анализа............................................................................................................................................. 2.3.2.3. Система продукций морфологического анализа............................................................ 2.4. МОДЕЛЬ СИНТАКСИЧЕСКОГО АНАЛИЗА.................................................................................... 2.4.1. Содержательное описание модели синтаксического анализа........................................ 2.4.1.1. Алгоритм синтаксического анализа................................................................................ 2.4.1.2. База знаний синтаксического анализа............................................................................. 2.4.2. База правил синтаксического анализа............................................................................... 2.5. ВЫВОДЫ ПО ВТОРОЙ ГЛАВЕ...................................................................................................... 3. МОДЕЛЬ ТРАНСЛЯЦИИ...................................................................................................... 3.1. ИНТЕРПРЕТАЦИОННАЯ МОДЕЛЬ ЛИНГВИСТИЧЕСКОГО ТРАНСЛЯТОРА............................. 3.1.1. Метаописание базы данных................................................................................................ 3.1.2. Описание знаний проблемной среды................................................................................... 3.2. БАЗОВЫЕ МЕХАНИЗМЫ ПРОБЛЕМНОГО АНАЛИЗА............................................................ 3.2.1. Метод построения преобразования 3............................................................................ 3.2.1.1. Построение транзитивных замыканий............................................................................ 3.2.1.2. Описание системы продукций......................................................................................... 3.2.1.3. Преобразование графа зависимостей терминов логической модели в граф зависимостей терминов физической модели – преобразование 3......................................... 3.3. ФОРМИРОВАНИЕ SQL-ЗАПРОСА ИЛИ ПОСТРОЕНИЕ ПРЕОБРАЗОВАНИЯ 4.............................. 3.3.1. Продукции по формированию SQL-запроса....................................................................... 3.3.2. Алгоритм доказательства гипотез................................................................................... 3.3.3. Формирование оператора SQL........................................................................................... 3.4. ВЫВОДЫ ПО ТРЕТЬЕЙ ГЛАВЕ..................................................................................................... ЗАКЛЮЧЕНИЕ............................................................................................................................ ЛИТЕРАТУРА.............................................................................................................................. ПРИЛОЖЕНИЕ А. ЛИНГВИСТИЧЕСКИЕ ЗНАНИЯ МОРФОЛОГИЧЕСКОГО АНАЛИЗА...................................................................................................................................... ПРИЛОЖЕНИЕ Б. ПРАВИЛА СИНТАКСИЧЕСКОГО АНАЛИЗА................................ ПРИЛОЖЕНИЕ В. ПРЕДИКАТЫ МЕТАОПИСАНИЯ БАЗЫ ДАННЫХ.................... ПРИЛОЖЕНИЕ Г. ПРЕДИКАТЫ ОПИСАНИЯ ЗНАНИЙ ПРОБЛЕМНОЙ СРЕДЫ ПРИЛОЖЕНИЕ Д. СИСТЕМА ПРОДУКЦИЙ ФОРМИРОВАНИЯ SQL-ЗАПРОСА ПРИЛОЖЕНИЕ Е. ОПИСАНИЕ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ И ВЫЧИСЛИТЕЛЬНЫХ ЭКСПЕРИМЕНТОВ...................................................................... Введение Задача интеллектуальной обработки текстов на естественном языке впервые появилась на рубеже 60-х–70-х гг.ХХ в. Работы последних лет связаны с решением проблемы анализа смысла языка в приложении к созданию систем диалога с программным обеспечением. Подходов к решению задачи понимания естественно-языковых запросов несколько. Наиболее распространенными являются подходы, основанные на синтаксическом, семантическом анализах и шаблонах. Первый подход, использующий синтаксические конструкции, - самый трудный. Синтаксическое представление запроса строится на основе подлежащего, сказуемого, прямого дополнения и т.п., которые определяются с помощью морфологических характеристик (часть речи, род, падеж, лицо и т.д.). Это представление ничего не говорит о смысле запроса.

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

Полное описание связей между смыслами слов (а одно слово часто имеет несколько смыслов) образует тезаурус, представляющий собой большую сеть со словами и их смыслами в качестве узлов. С помощью таких тезаурусов выполняется построение семантического представления запроса. Основная задача при этом — отсечь ненужные смыслы, постараться выделить с помощью синтаксических связей достоверные семантические конструкции. В больших предложениях, особенно с многозначными словами, это часто приводит к комбинаторному взрыву — перебору множества смыслов и связей между ними, а также многозначности синтаксических конструкций (одному и тому же предложению может быть сопоставлено несколько синтаксических представлений), обработка которых занимает неприемлемо большое время. Это лишь одна проблема, стоящая на пути понимания естественно-языковых запросов в традиционной синтаксически-ориентированной парадигме. Вторая сложность — типичные естественно языковые запросы, которые, как правило, не имеют правильных синтаксических конструкций. На это влияют вольное словоизменение и словообразование в виде неологизмов сетевой общественности, большой процент имен собственных и сокращений, игнорирование правил пунктуации, что приводит к тому, что от естественного языка во всем его многообразии иногда остается лишь лексика, причудливым образом исковерканная. И, наконец, необходимые в этом подходе семантические словари — очень трудоемкая составляющая, для многих предметных областей они просто отсутствуют, а их разработка требует высокой квалификации.

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

К настоящему времени существующие естественно-языковые системы используют в основном два последних подхода. Второй подход реализован в достаточно распространенной системе ЗАПСИБ, разработанной в середине 80-х годов [64]. Система позволяет вести общение на ограниченном подмножестве естественного языка. Развитием проекта является система InterBase, вышедшая в 1990 году [106]. Система основана на семантически-ориентированном анализе и продолжает ряд естественно-языковых технологий лаборатории искусственного интеллекта ВЦ АН Новосибирска, затем фирмы «Интеллектуальные технологии», а теперь РосНИИ искусственного интеллекта. В году эта система была переработана и получила название InBASE в виде коммерческого продукта. В настоящее время система представляет собой библиотеку COM-компонентов и среду настройки естественно-языковых интерфейсов. Существенным отличием от старой версии является появление промежуточного уровня запросов — Q-языка, являющегося подмножеством языка объектных запросов OQL, и уровня описания предметной области в виде диаграммы классов UML. В полном соответствии с особенностями семантически ориентированной парадигмы InBASE позволяет строить естественно-языковые интерфейсы ко многим языкам — для русского и для английского используется один и тот же Л процессор. Интересной особенностью InBASE является возможность моделирования предметной области на естественном языке: с помощью класса словарных статей «Толкование» смысл слова можно описать простой фразой. Это позволяет настраивать естественно-языковые интерфейсы людям, не обладающим навыками инженеров знаний.

Основным недостатком данной системы является то, что кортежи базы данных продублированы в словарях – отдельных файлах. В базах данных больших объемов этот недостаток может стать проблемой [112-118].

Ярким представителем третьего подхода является система English Query. Система English Query от Microsoft основана на синтаксически-ориентированных шаблонах, связываемых с моделью предметной области, и через нее - со схемой базы данных [112]. При настройке необходимо задать модель базы данных и предметной области, а затем для каждого отношения в базе данных (а отношением считается и связь между классом и его атрибутом, например, между товаром и его ценой) задать синтаксический шаблон английской грамматики, выбираемый из списка. Этот продукт позволяет строить естественно-языковые интерфейсы только для английского языка и работает только с Microsoft SQL Server, в этом смысле это лишь утилита, поставляемая с SQL-сервером, именно так она и позиционируется. В целом же этот продукт очень интересен. Например, в нем есть встроенная обучаемая база знаний, с которой можно пообщаться на английском языке, — она запоминает факты, правила и отвечает на вопросы по этой базе. К сожалению, эта замечательная способность не совмещена с пониманием запросов к базе данных.

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

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

Модуль знаний проблемной среды содержит описания понятий и терминов предметной области. Создаваемую естественно-языковую систему обработки запросов к базе данных предполагается использовать при разработке больших информационных систем. База знаний должна заполняться в процессе разработки проекта информационной системы.

Поскольку у многих информационных систем основным ядром является SQL ориентированные распределенные базы данных, то задача построения естественно языкового пользовательского интерфейса тесно связана с разработкой методов и алгоритмов трансляции естественно-языковых запросов в запросы SQL языка. Таким образом, предмет рассмотрения этой работы – методы, позволяющие осуществлять преобразование запросов на естественном языке, представленных в виде простых предложений русского языка, в SQL-запросы.

Работа состоит из введения, трех глав, заключения, литературы и 6 приложений.

В первой главе дан обзор существующих моделей лингвистического анализатора, рассмотрена структура лингвистического анализатора, проанализированы методы и алгоритмы морфологического, синтаксического и проблемного анализов, сделаны основные выводы и сформулирована постановка задачи.

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

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

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

1. Обзор и анализ методов решения задачи Попытки формализовать интеллектуальную деятельность человека привели к постановке фундаментальной лингвистической задачи [1], состоящей в моделировании его языкового поведения, т.е. в построении функциональной модели естественного языка.

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

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

Цель анализа предложения на естественном языке - перевод их на машинный язык вычислительной системы. При этом анализатор осуществляет следующие функции [2]:

- распознавание правильно построенных предложений естественного языка;

- декомпозиция («разбивка») предложения на составляющие (фрагменты) и построение соответствующей синтаксической структуры предложения;

- семантическая интерпретация фрагментов предложения естественного языка во фрагменты М-языка;

- композиция («сборка») фрагментов М-языка в структуру, описывающую ситуацию проблемной среды.

Реализация этих функций осуществляется на этапах морфологического и синтаксического анализов, семантической интерпретации и проблемного анализа. Часто два последних этапа объединяются в один этап семантического и проблемного анализов.

1.1. Структура лингвистического анализатора Со стороны своего внутреннего устройства лингвистический анализатор представляет собой многоуровневый преобразователь [3,4], состоящий из трех уровней пофразного представления текста – морфологического, синтаксического и семантического. Каждый из уровней обслуживается соответствующим компонентом модели – массивом правил и определенными словарями. На каждом из уровней предложение имеет формальный образ, именуемый в дальнейшем его структурой – морфологической, синтаксической и семантической структурами.

Под морфологической структурой понимается последовательность входящих в анализируемое предложение слов с указанием части речи и морфологических характеристик (падежа, числа, рода, одушевленности, вида и т.п.).

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

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

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

предложение на естественном языке морфологическая структура синтаксическая структура семантическая структура.

Реализация лингвистического анализатора требует разработки формальных языков для записи (образов) предложений на морфологическом, синтаксическом, семантическом уровнях представления;

формального понятия структуры предложения для каждой из этих уровней;

массивов правил для преобразования структур смежных уровней друг в друга;

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

1.2. Анализ методов и подходов морфологического анализа Стадия морфологического анализа является наиболее проработанным лингвистическим этапом процесса обработки естественного текста. За последние два десятилетия создано по крайней мере несколько десятков алгоритмов для разных языков, в том числе 10-12 для русского [4, 5, 6].

Цель морфологического анализа заключается в определении морфологической информации словоформ для использования на последующих этапах обработки текста.

Существует три основных метода реализации морфологического анализа:

декларативный, процедурный и комбинированный.

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

Процедурный морфологический анализ выполняет следующие функции: выделяет в текущей словоформе основу, идентифицирует ее и приписывает данной словоформе соответствующий комплекс морфологической информации. Процедурный метод предполагает предварительную систематизацию морфологических знаний о естественном языке и разработку алгоритмов присвоения морфологической информации отдельной словоформе [5]. Недостатком такого подхода является высокая трудоемкость составления словарей совместимости. При этом наличие в русском языке большого числа слов исключений не позволяет сколько-нибудь автоматизировать этот процесс. Для проведения анализа словоформы необходимо наличие словарей «приставка-корень», «корень – суффикс - флективный класс», «флективный класс – окончание - морфологическая информация».

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

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

В настоящее время выделилось несколько направлений в разработке морфологического анализа. Одно из них моделирует классическую схему анализа путем разделения словоформы на основу и аффиксы с последующей проверкой на совместность окончания с остающейся основой [6].

К данному направлению можно отнести модель морфологического анализа Г.Г.

Белоногова, в основе которой лежит флективный анализ слов, базирующийся на разбиении лексем (слов) русского языка на флективные классы [29-30]. Морфологический анализ начинается с поиска лексемы в словаре готовых словоформ. При успешном завершении извлекается код флективного класса, соответствующий данной лексеме и указывающий на часть речи и синтаксическую функцию словоформы, в противном случае словоформа подвергается флективному анализу, который включает в себя следующие этапы:

- идентификация морфем словоформы (последовательная проверка возможностей вложения в анализируемую словоформу корня, суффикса, окончания и приставки);

- определение флективного класса словоформы (извлечение кода флективного класса из таблиц совместимости корня со словообразующими аффиксами);

- присвоение словоформе морфологической информации.

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

Другое направление использует информацию, содержащуюся в конечных буквосочетаниях (эта информация получается в результате предварительной статистической обработки словаря). Этот путь также дает достаточно хорошие для практических целей результаты [5].

Третье направление развивается в последние годы. Оно вызвано стремлением преодолеть ограниченность существующих алгоритмов морфологического анализа.

Известно, что они ориентировались на тексты определенной тематики и поэтому не полностью учитывали все особенности морфологии. Это направление пытается построить более адекватные морфологические модели. Создаются универсальные математические модели в форме открытой системы уравнений, позволяющих путем вычисления осуществлять нормализацию словоформ, получение грамматической информации и синтез словоформ. Одной из таких моделей является модель Ю. П. Шабанова-Кушнаренко [24], моделирующая процессы русского языка посредством языка алгебры конечных предикатов, с помощью которого может быть математически описан любой аспект морфологии русского языка.

1.3. Аналитический обзор методов синтаксического анализа В отличие от морфологического анализа текста синтаксический анализ (СА) развивающаяся область прикладной лингвистики. Цель синтаксического анализа автоматическое построение функционального дерева фразы, т.е. нахождение взаимозависимостей между разноуровневыми элементами предложения [9-14]. Существует достаточно много различных способов синтаксического анализа естественно-языковых текстов, которые можно проанализировать с различных точек зрения. Общая структура классификации способов синтаксического анализа приведена в таблице 1.

Таблица 1 - Классификация способов синтаксического анализа № Основание классификации Группа методов п/п Одноцелевые 1 Тип цели Многоцелевые Построение графа зависимостей 2 Синтаксическая структура Построение дерева непосредственных составляющих Формальные теории описания Формально-грамматические методы естественного языка Вероятностно-статистические методы С точки зрения цели синтаксического анализа можно выделить два основных подхода: одноцелевой и многоцелевой. При первом подходе для фразы требуется построить одно синтаксическое представление, этот подход характерен для первых алгоритмов синтаксического анализа, когда считалось, что синтаксических средств достаточно для того, чтобы обеспечить правильный анализ фразы, хотя бы для большинства фраз. При втором подходе для фразы требуется получить все те синтаксические представления, которые удовлетворяют определенным соглашениям (все «правильно построенные» представления). Вопрос о том, какое из этих представлений является не только правильно построенным, но и правильным, т.е. соответствующим смыслу анализируемой фразы, в рамках синтаксического анализа не решается.

Одним из основных компонентов лингвистической базы знаний, осуществляющей автоматический синтаксический анализ, является описательная модель синтаксической структуры предложения [9]. Такая модель в значительной степени передает концепцию разработчиков относительно синтаксического уровня анализа: какая именно информация об элементах предложения и их взаимосвязях должна выявляться в процессе анализа, присутствовать в его результатах и какие формы представления ей адекватны. Наиболее общим для разработчиков синтаксических анализаторов является взгляд, что синтаксическое строение предложения можно представить некоторым частично упорядоченным множеством бинарных связей между элементами. Виды и свойства элементов, связей и отношения порядка варьируют в разных моделях.

Представления о бинарных синтаксических связях используются в двух известных моделях синтаксической структуры: графах зависимостей и графах непосредственных составляющих. В настоящее время эти две формы представления синтаксической структуры остаются основными. Они используются в чистом виде или – очень часто – в смешанных формах, сочетающих в себе свойства обоих графов.

Описание структур в форме классического графа зависимостей хорошо соответствует русской грамматической традиции: оно основывается на понятии бинарного словосочетания в предложении с выделенными главными и зависимыми элементами.

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

Отношение подчинения задает частичный порядок на множестве узлов. Если одному узлу подчиняется сразу несколько узлов, то среди последних порядок не определен: граф зависимостей не передает информацию об относительной степени близости подчиненного слова к главному. В некоторых случаях недостаток этой информации вполне очевиден – сравним, например, граф зависимостей для фразы «программное обеспечение вычислительной техники и автоматизированных систем» (рис. 1.1).

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

Иногда граф зависимостей одновременно с отношением подчинения задает и отношение линейного порядка следования узлов. Такой граф называется расположенным.

Один из способов изображения такого графа представлен на рисунке 1.2.

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

Особая сложность связана с представлением в древесной структуре явлений однородности. Изображение всех связей однородных членов между собой, с подчиняющими и подчиненными элементами приводит к возникновению замкнутых контуров в графах зависимостей. Чтобы избежать этого, часто используют представление, при котором сочинительная связь включается в граф зависимостей наравне с другими синтаксическими отношениями (СинО), а подчинительные связи, общие для группы однородных членов, изображаются лишь для одного члена группы (рис. 1.3). Так сделано в системе ЭТАП-2 и ряде других систем [125].

Фирма выпускает электронные машины четвертого поколения.

Рис.1.2. Расположенный граф зависимостей Вопрос о допущении недревесности синтаксических графов зависимостей возникает еще и в связи с представлением неоднозначностей синтаксической структуры. Как известно, процедура синтаксического анализа может приводить к построению нескольких вариантов синтаксической структуры предложения. Разные варианты синтаксической структуры могут описываться разными синтаксическими представлениями, в том числе в виде дерева зависимостей. Однако существует и другой подход: например, принципом синтаксического анализа является неразделение на варианты и в результате анализа может получиться недревесный граф зависимостей, в котором сохраняются все виды неоднозначности. В графе зависимостей системы ПОЭТ допускаются неоднозначные зависимости, но только внутри именных групп.

Объектное СинО Определительное Сочинительное СинО СинО Изучил дискретную математику и логику Рис. 1.3. Представление однородности Вторая классическая модель синтаксической структуры – дерево непосредственных составляющих. Основные идеи по этой модели принадлежат Блумфилду [102, 103], которые он высказал в начале 30-х годов. Конструктивное развитие модель получила в работах Уэллса, Хэрриса, Хомского [127]. В основе модели дерева составляющих лежит представление об устройстве предложения как о последовательном попарном синтагматическом сцеплении составляющих от минимальных отдельных слов, до максимальной - предложения, составляющими которого в случае полного личного предложения являются группа подлежащего и группа сказуемого.

Представление синтаксической структуры в терминах дерева составляющих хорошо согласуется с традиционным «разбором» предложения, при котором подлежащее, сказуемое и их элементы описываются категориальными характеристиками – именами частей речи или групп. Например, классическая фраза Блумфилда «Бедный Джон убежал прочь» будет представлена так, как показано на рисунке 1.4.

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

NP VP N A V Adv убежал прочь Бедный Джон Рис. 1.4.

Здесь - символ предложения, А – прилагательное, N – существительное, V – глагол, Аdv – наречие, NР – именная группа, VР - глагольная группа.

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

Следует подчеркнуть, что системы составляющих и деревья зависимостей характеризуют синтаксическую структуру предложения в разных аспектах. С помощью первых описываются в явном виде словосочетания, но игнорируется ориентация связей (т.е. не различаются “хозяин” и “слуга”);

вторые дают возможность рассматривать направленные связи, но только между отдельными словами.

B настоящее время распространенным способом описания синтаксической структуры является комбинирование приемов двух классических моделей: обозначение порядка замыкания связей в дереве составляющих систем ЛГУ (2 версия), использование нетерминальных узлов в графах зависимостей системы ПОЭТ [33].

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

Формальные грамматики работают, как правило, с синтаксическим представлением в виде дерева составляющих. Привлекательными свойствами графа зависимостей является их экономичность, удобство использования в преобразованиях, возможность представления частичных результатов анализа в виде множества подграфов. Модель данного типа используют системы групп Г.Г. Белоногова, APT, РЕЗОН, ЭТАП-2, ПОЭТ, АДАМАНТ, САГА, большинство японских систем анализа текста и ряд других [25, 33].

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

Формально-грамматические подходы заложены классификацией формальных языков и грамматик, предложенной Хомским. Для компьютерной лингвистики среди них наиболее важны грамматики конечных автоматов, контекстно-свободные и контекстно-зависимые грамматики. Для описания естественно-языковых феноменов в основном применяются КС грамматики с некоторыми расширениями.

Грамматика конечных автоматов (Finite-State Transition Network) формально соответствует простой по возможностям грамматике третьего типа. Конечный автомат содержит набор состояний (нетерминальных символов), среди которых выделяют одно или несколько начальных и конечных, и условий перехода между состояниями. Информацией для перехода по условиям служат символы, поступающие с ленты, которую читает автомат.

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

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

Более высокий уровень грамматик составляют контекстно-свободные грамматики, которые описываются в виде продукций (правил), ставящих в соответствие нетерминальным символам в своих левых частях (до знака «=») набор терминальных и нетерминальных символов в правых частях. Пример контекстно-свободных правил (КС правил) для простой грамматики русского языка дан на рисунке 1.5. КС-правила в первой колонке описывают структуру нетерминальных символов, во второй – словарь, т.е.

соответствие между нетерминальными и терминальными символами.

Подобная грамматика описывает такие предложения, как "лис видит волка";

"молодой лис видит старого волка";

"молодой лис видит старого лежачего волка";

"лис лежит" и т.д.

Достаточно просто расширить эту грамматику, чтобы представить в словаре русскую морфологию в более полном виде. Заметим, что в данной грамматике выбор конкретного правила для построения глагольных групп (VP-правила) или именных групп (NP-правила) задан вариантами, гарантированный выбор между которыми сделать в рамках данного правила невозможно. Подобная грамматика относится к так называемым недетерминированным грамматикам.

Синтаксис КС-правил очень прост, однако для описания многих феноменов естественного языка простого аппарата КС-грамматики оказывается недостаточно. В частности, контекстно-свободными правилами неудобно описывать согласование (например, в лице и числе между подлежащим и сказуемым). КС-аппарат неудобен также для отображения разорванных зависимостей (long-distance dependencies), вызванных передвижением слов по фразе, или для описания отсутствия составляющих (deletion).

S = NPVP ADJECTIVE = молодой VP = VERB ADJECTIVE = старого VP = VERBNP ADJECTIVE = лежащего NP = NOUN NOUN = лис NP = ADJECTIVENP NOUN = волка PP = PREPOSITION NP VERB = видит VERB = лежит Рис. 1.5. Пример КС-правил (S - предложение, NP - именная группа, VP - глагольная группа, РР - предложная группа) В традиции трансформационных грамматик для представления подобных феноменов вводятся трансформации, переводящие синтаксическую структуру таких фраз в стандартную. Одним из способов отражения изменений синтаксической структуры без использования трансформаций является Node raising. В такой методологии то место, которое должно быть занято некоторой именной группой в стандартной синтаксической структуре дерева составляющих, обозначается пустым узлом и дополняется признаком slash (NP/). Такой узел располагается, как правило, справа от реальной позиции соответствующей составляющей и в более глубокой, составляющей дерева (например, Wh группа зависит от корня дерева, a NP/ - от глагольной группы). В таком описании Wh группа как бы поднимается относительно своей стандартной позиции (отсюда понятие raising).

В классических КС-грамматиках так же неестественно представляется такой феномен, как субкатегоризация, т.е. специфические свойства подкласса какой-либо категории. Например, КС-грамматика, изображенная на рисунке 1.5, не отличает переходные и непереходные глаголы, поэтому она принимает предложения, содержащие прямые дополнения у непереходных глаголов. Если же ввести два нетерминальных символа, TV и IV для переходных и непереходных глаголов соответственно, то в этом формализме невозможно будет отразить свойства, общие для обеих групп глаголов. Все эти проблемы приводят к тому, что грамматические формализмы расширяют аппарат КС правил с целью представления подобных феноменов.

Кроме отмеченных выше проблем КС-грамматики добавляют еще одну. В правиле, выражающем отношения между составляющими, не отражается естественная особенность естественных языков - поглощение одной категории другой, так что новая составляющая выступает заменителем управляющей категории. В частности, есть очевидное сходство в образовании именных групп из существительных и глагольных групп из глаголов. По этой причине синтаксис КС-правила, использующего составляющие, ограничивается описанием отношения категории X и категории, которой она управляет. Например, если существительное управляет определением, тогда именная группа может быть записана как N (иногда записывается как N’).

С другой стороны, построение именной группы завершается указанием спецификатора (артикля или местоимения), для отражения такого факта вводится комбинация надчерков: N. Число надчерков при этом означает уровень проекции данной составляющей. Существенно ограничение максимального количества штрихов двумя:

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

Многие теории (примерно с начала 80-х годов) перешли от описания грамматики в терминах правил к описанию ограничений (licensing rules), накладываемых на сформированность (well-formedness) частей выражения. При таком способе описания языка синтаксис языка не задается, различные ограничения в явном виде друг с другом не связаны. Анализ (или синтез) при этом является попыткой найти представление, одновременно удовлетворяющее всем ограничениям, причем возможные варианты конструкций строятся параллельно (или псевдо-параллельно). Представители этого направления связывают популярность таких грамматик с тем, что правила (КС или КЗ) описывают структурные свойства лингвистических конструкций, в то время как ограничения на сформированность являются более общими принципами, определяющими эти конструкции. В частности, это приводит к большей независимости правил от конкретных конструкций (нужно написать меньше правил для описания сравнимых элементов грамматики языка) и возможности описания в грамматике свойств лексических единиц.

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

В синтаксическом анализе существуют две стандартные стратегии применения правил при возможности альтернативного выбора: поиск "в ширину" и поиск "в глубину".

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

Комбинацию достоинств этих вариантов представляет анализ с помощью таблиц, содержимое которых является результатом частичного разбора. В случае, если разбор по какому-то пути зашел в тупик, происходит возврат на точку выбора последнего правила и делается попытка использовать другое правило. Однако заполнение таблицы, порожденное предыдущим способом разбора, сохраняется в таблице и может быть использовано в разборе по текущей ветке. Эта информация не запрещает проход анализа по тем веткам, которые уже были опробованы, но неудачно. Для этой цели применяется запоминание также и гипотез, выдвигаемых при разборе, и результатов их проверки. Такой подход называется анализом с помощью схем (chart-parsing). Впервые его предложил Мартин Кэй в системе Powerful Parser.

Грамматики конечных автоматов достаточно эффективны в реализации, но обладают слишком ограниченными возможностями для анализа, по этой причине одним из широко используемых механизмов анализа является формализм расширенных сетей переходов (augmented transition networks, ATN). Формализм ATN расширяет грамматику конечных автоматов, вводя аппарат рекурсивного вызова новой подсети переходов (операция PUSH) и набор регистров, в которых хранятся текущие результаты разбора фразы, а также средства работы с этими регистрами. Значения регистров могут выступать условиями для переходов по веткам, что обеспечивает частичную зависимость от контекста и выход за пределы КС-грамматик. Благодаря регистрам и операциям над значениями, которые там хранятся, ATN-формализм эквивалентен процедурному языку программирования, в котором можно описать анализ языка произвольной сложности.

1.4. Аналитический обзор семантических моделей На данный момент разработано множество моделей лингвистического анализатора, которые способны в той или иной степени выполнять анализ естественно-языкового текста, определять смысл и генерировать высказывания. При этом подходы к моделированию процесса общения весьма разнообразны. Основные отличия этих подходов заключаются в методах реализации компонента понимания смысла, используемых средствах анализа, а также в объеме и способах представления знаний, поскольку именно знания, представленные в различной форме, являются базой, от которой зависит процесс общения, глубина проникновения в смысл и, соответственно, качество самой модели лингвистического анализатора. От выполнения отдельных функциональных компонент зависит практическая реализация моделей в различных системах общения (системы общения с базами данных, системы машинного перевода и др.). Некоторые из них легли в основу конкретных систем формирования семантического представления на основе обработки текстов (например, модель Смысл-текст в системе «Поэт») [25].

Проанализируем наиболее проработанные модели лингвистического процессора с точки зрения реализации анализа и интерпретации входного высказывания и синтеза выходного высказывания.

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


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

сеть концептуализаций;

идентификация смысла по образцу;

интегральный подход.

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

В дальнейшем идея описания входного текста с помощью компонентного анализа нашла свое продолжение в модели «Семантические падежи (роли)» Ч. Филмора. Но в отличие от предыдущей модели в предикатах указывается не только аргументная структура и количество, но и их семантическое содержание (роли). Филмор выделяет следующие семантические роли: агент, контрагент, объект, адресат, пациенс, результат, инструмент, источник. В модели предложена более детальная концепция смысла высказывания.

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

Продолжением данной теории явился метод падежной грамматики (Филмор) [128].

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

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

Основой семантического представления модели «Концептуальной зависимости» (Р.

Шенк) является сеть концептуализаций [129]. Сеть концептуализаций есть квазиграф, подобный размеченному ориентированному графу, в котором, кроме бинарных отношений, есть тернарные и кварнарные, а дуги связывают не только вершины, но и другие дуги.

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

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

Другая модель - «Семантик предпочтения» относится к классу моделей, идентификация смысла в которых осуществляется по образцам. Отличительной чертой таких моделей является то, что в них отсутствуют блоки морфологического и синтаксического анализов, что является принципиальным их недостатком, так как не обеспечивается глубина анализа значений слов, необходимая для точного установления семантической связности текста.

В этой модели (Уилкс) текст характеризуется следующими сущностями: смыслами слов, сообщениями, фрагментами текста и семантической совместимостью [128].

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

Анализ фрагмента текста протекает по следующей схеме. С помощью специальных слов-маркеров выполняется фрагментация текста, затем словам приписывают из словаря все их значения. Далее на анализируемый фрагмент текста поочередно накладываются простые шаблоны, известные системе. С помощью специальных правил расширения простой образец преобразуется в полный образец путем добавления слов из текста, которые не вошли в образец. Указанная процедура осложнена тем, что может подойти не один простой образец. Используя процедуры установления семантической близости полученных образцов, формируется окончательное представление обрабатываемого текста.

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

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

Суть табличного метода состоит в идентификации смысла всего предложения на основании нескольких ключевых слов или их групп. После процесса идентификации слова предложения заменяются на их каноническую форму - коды. Замена осуществляется с помощью словаря словоформ. При этом также выделяются некоторые группы слов, несущие тематическую нагрузку. Далее производится распознавание и замена стандартных словосочетаний. Данный метод обладает рядом недостатков, преимуществом является его простота для однозначных естественно-языковых предложений, в которых не требуется полного понимания смысла предложения (например, запросы к базе данных).

Модели, в которых достаточно глубоко продуманы процедуры морфологического, синтаксического и проблемного анализов, можно отнести к моделям, основанных на интегральном подходе описания языка. Это модель «Смысл-текст» и модель контекстного фрагментирования.

Модель «Смысл-текст» (И.А. Мельчук) представляет собой многоуровневый транслятор текстов в смыслы и наоборот [7]. Выделяются четыре основных уровня – фонетический, морфологический, синтаксический и проблемный. Каждый из них, за исключением проблемного, подразделяется на два других уровня – поверхностный и глубинный.

Данная модель может быть применима в системах, где необходимо понимание текста в полном смысле (например, вопросно-ответные системы, системы принятия решений). Но для реализации полной схемы анализа и синтеза модели «Смысл-текст» придется учесть индивидуальные свойства сотен тысяч словарных, морфологических и лексических единиц и индивидуальные свойства громадного числа пар единиц. Их полное формальное описание представляет собой громадную и объемную теоретическую работу, поставленную в лингвистике в последнее время и еще далекую от решения.

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

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

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

- извлекать знания из заданного текста и строить правильные предложения естественного языка по заданным значениям смысла;

- перефразировать эти предложения;

- оценивать их с точки зрения связности и выполнять ряд других задач.

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


Анализ показал, что разработанные модели имеют достоинства, но и не лишены недостатков. Многие из них (модели «Семантик предпочтения», «Концептуальной зависимости» и др.) в основном ориентированы на анализ, в них слабо продуман процесс преобразования смысла входного высказывания на знания системы, что может привести к некорректным умозаключениям. Также выделяется класс моделей, в которых отсутствует или слабо реализован блок морфологического или синтаксического анализов, что оказывает существенное влияние на качество анализа.

1.5. Выводы по первой главе Естественно-языковый интерфейс с базами данных не предполагает использование сложных предложений естественного языка в запросе пользователя. Тем не менее для его распознавания необходимо строить лингвистический анализатор как преобразователь, состоящий из трех уровней пофразного представления текста - морфологического, синтаксического и семантического. Для каждого уровня требуется соответствующий компонент модели со своим массивом правил и словарями и построением формального образа запроса – морфологической, синтаксической и семантической структурами. Следует отметить, что для решения поставленной задачи полный семантический анализ не требуется, он необходим для классификации лексем с целью выполнения проблемного анализа. Поэтому лингвистический анализатор целесообразнее называть лингвистическим транслятором. Для описания математической модели транслятора будем использовать модель контекстного фрагментирования.

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

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

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

1. Запрос может состоять из одного или нескольких простых предложений на русском языке.

2. Если запрос содержит несколько простых предложений, то каждое последующее предложение должно содержать существительное, приведенное в одном из предыдущих предложений.

3. В запросе должна затребываться информация, релевантная рассматриваемой базе данных.

4. Затребываемая в запросе информация должна иметь четкий характер, т.е. не должны использоваться указательные местоимения я, ты (вы), он (она, оно), они, этот, тот, такой, таков, столько и т.п., частицы «ли», «либо», «то» и другие.

5. Рекомендуется начинать запрос со специальных слов: Выдать, Показать, Перечислить, Как, Когда, Где, В какое время, Какой, Куда, Откуда.

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

2. Модель лингвистического транслятора Анализ и трансляция текста осуществляются при наличии достаточно мощных средств описания и фрагментации лингвистических знаний. Схема отображения ЕЯ-текста адекватна трансляции ЕЯ-запросов на проблемную область в базе данных. Инвариантность проблемной области достаточно точно отражается в словаре базы данных. Словарь БД предполагает наличие в них всех концептов проблемной области и включает в себя, как минимум, имя концепта и его определение.

2.1. Математическая модель транслятора Основу модели контекстного фрагментирования составляет трехуровневая система:

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

Структуру системы общения с базами данных можно представить в виде тройки:

Z = M, В, K, (1.1) где М – лингвистическая модель;

В – базовые механизмы обработки предложений;

К – ассоциированные процедуры.

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

Лингвистическая модель представляется в виде:

M = M1, M2, M3, (1.2) где M1 – грамматическая модель;

M2 – интерпретационная модель;

M3 – модель трансляции, включающая семантический и проблемный анализы.

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

Грамматическая модель, в свою очередь, состоит из кортежа:

M1 = M1, M (1.3), где M1- модель морфологического анализа;

M1 - модель синтаксического анализа.

Интерпретационная модель М2 задается в виде вектора:

M 2 = M 2, M 2, (1.4) где M 2 – модель метаописания базы данных;

M 2 - модель проблемной среды.

Базовые механизмы В реализуют четыре основных отображения: 1: T X ~ (морфологический разбор);

2: ХG (синтаксический разбор);

3: G G (семантический и ~ проблемный анализы), 4: G Q (трансляция), где Т – текст естественного языка в виде множества лексем, X - множество лексем с векторами морфологической информации v, G граф зависимостей, в вершинах которого располагаются словоформы (лексемы), а дуги ~ отображают связь от вершины “предок” к вершине “потомок”, G - граф, в вершинах которого располагаются термины физической модели базы данных, Q – SQL-запрос в виде команды SELECT.

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

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

В настоящее время в качестве основных средств представления знаний в информационно-поисковых системах используются Семантические сети, Системы продукций, Фреймы и Логические модели, в последнее время стали развиваться прикладные модели [128, 43, 69, 84, 90, 2, 131]. В качестве подхода к построению модели знаний лингвистического транслятора в работе используются системы продукций. Системы продукций, на наш взгляд, являются почти единственной моделью представления знаний, на которой удобно описывать правила обработки знаний, именно это обстоятельство определило выбор аппарата для построения формальной модели предметной области.

2.2.1. Введение в системы продукций Системы продукций начали развиваться с середины 70-х годов в связи с появлением прикладных программных систем специальной архитектуры, предназначенных для решения задач в плохо формализованных областях, таких как медицина, геология, понимание естественного языка. В первых работах дается содержательное описание продукционного подхода. Наиболее полное исследование данного представления в виде формальных моделей дали А.С.Клещев [82], В.Е.Кузнецов [26], Т.М.Яхно [62,81], M.Georgeff [130]. Особенности каждой модели определялись классами решаемых задач и технологическим базисом.

Опишем концептуальные рамки понятия "системы продукций" (СП), используемого сейчас в области искусственного интеллекта, и проследим, из каких понятий оно складывалось и как эволюционировало. Формальная теория или исчисление [129] определяется как "способ задания множеств путем указания исходных элементов (аксиом) и правил вывода, каждое из которых описывает, как строить новые элементы из исходных и уже построенных". Список, каждый элемент которого является аксиомой или получен из предыдущих элементов списка по одному из правил вывода, называют выводом в исчислении. Наиболее полно изученными исчислениями в математической логике являются исчисления высказываний и исчисления предикатов первого порядка [129]. С каждой формулой в этих исчислениях связывается понятие «интерпретация»

(приписывание истинностных значений), через которое определяются такие понятия, как противоречивость, непротиворечивость и общезначимость формул. Логическое следствие определяется следующим образом. Формула G есть логическое следствие формул F1, F2,..., Fn, тогда и только тогда, когда для любой интерпретации I, если формула F1& F2&...&Fn истинна в I, то G также в ней истинна [129].

Логическое следствие получается в результате применения логических правил вывода. Такие правила вывода обладают универсальной истинностью и могут применяться либо для установления истинности некоторого утверждения, либо для порождения новых заключений. В исчислении предикатов первого порядка зафиксировано несколько правил вывода (например, modus ponens).

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

Формулировка задачи в исчислении предикатов рассматривается как теорема. Многие проблемы могут быть сформулированы как проблемы доказательства теорем. Именно это и определило стремление найти общую автоматическую процедуру доказательства теорем.

Важный прогресс в этой области достигнут с момента разработки метода резолюций, который оказался легкодоступным для реализации на ЭВМ. Именно поэтому исчисление предикатов является одним из основных исчислений, ориентированных на построение программ, обладающих интеллектуальными способностями [131].

Однако попытки автоматизации решения разнообразных классов задач в рамках классической логики иногда приводят к громоздким и неестественным формулировкам, превращая простые задачи в практически не решаемые. В частности, именно с этим обстоятельством связан некоторый скепсис в отношении применимости математической логики. Это дало толчок развитию исчислений на основе использования проблемно ориентированных правил вывода. Примером таких исчислений являются системы подстановок. К данному классу можно отнести исчисление, введенное Э.Постом, которое он назвал системами продукций [131]. Система продукций Поста задается своим алфавитом и системой подстановок каждая, из которых называется продукцией, и имеет вид aiW Wbi, (i = 1... n), где ai, bi — слова в алфавите С. Пусть некоторое слово L начинается словом аi. Выполнить над L продукцию — значит вычеркнуть из L начальный отрезок аi, и к оставшемуся слову приписать справа слово bi. Например, применяя к слову aba продукцию abW — Wc, получим слово ас. Существуют теоремы, показывающие, что любую систему подстановок можно "вложить" в систему продукций. Характерным для систем продукций Поста является ограничение на форму самих подстановок.

К этому же классу исчислений можно отнести и порождающие грамматики, введенные Н.Хомским [127]. Накладывание ограничений на левые и правые части правил привело к классификации грамматик и соответственно к классификации языков, порождаемых данными грамматики. При этом в фокусе исследований основной являлась проблема распознавания того, принадлежит ли заданное слово языку, порождаемому некоторой заданной грамматикой. Основная сфера применения данного формализма — это анализ формальных и естественных языков [127].

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

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

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

Знания о предметной области задают множество возможных преобразований в пространстве ситуаций, каждое из которых ограничено соответствующими условиями применимости данного преобразования в той или иной ситуации. Такие правила стали называть продукциями, а системы, использующие их для описания знаний, – системами продукций [131]. Такая форма представления информации была принята в некоторых психологических моделях мышления человека. Исследования процессов принятия решений человеком показали, что, рассуждая, человек использует правила вида условие действие.

А.Ньюэлл первым предложил использовать такое представление знаний для моделирования на ЭВМ процесса принятия решений.

Таким образом, в искусственном интеллекте под термином "системы продукций" понимают, с одной стороны, средство представления знаний. В этом смысле его можно отнести к классу нелогических прикладных исчислений и исследовать его свойства. К основным достоинствам систем продукций можно отнести: проблемную ориентированность, естественную модульность организации знаний в системах продукций (каждая продукция представляет собой законченный фрагмент знаний о предметной области), независимость каждой продукции от содержания других продукций (продукции не взаимодействуют друг с другом, эффект применения каждой из них определяется изменениями, которые она производит в обрабатываемой структуре);

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

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

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

В архитектуре программных систем продукций можно выделить четыре основных компонента: базу данных — память для хранения информации о решаемой задаче, базу знаний – множество правил (продукций), аппарат активации продукций - алгоритм, осуществляющий поиск по образцу, и интерпретатор, выполняющий преобразование базы данных по заданным правилам. Таким образом, аппарат активации продукций можно реализовать на основе метода линейной резолюции.

В связи с тем, что сразу представление в предикативной форме утверждения на естественном языке достаточно трудно осуществить, используем подход, предложенный в работах Т.М. Яхно, А.С. Клещева, М.Ю. Черняховской, Т.Л. Гаврилова и других [131, 62,81-82], в котором для описания системы продукций применяется аппарат многосортной алгебры.

2.2.2. Описание формального аппарата Рассмотрим аппарат, который позволит построить формальное описание лингвистических моделей. В работе [131] было предложено описание модели проблемной среды представлять посредством множества подразумеваемых ситуаций. Формальное описание ситуации удобно представлять продукционными правилами, так как продукция записывается в виде простого правила «Условие действие», что соответствует оператору ЕСЛИ-ТО. Тогда модель проблемной среды может быть формализована как система продукций. Описание продукций основано на работах [129 и 131].

Введем понятия из теории моделей в том объеме, в котором они понадобятся для дальнейшего изложения и как они описаны в работах Т.М. Яхно [129, 131].

Введем определение терма:

• всякая константа a A, где А – словарь констант, есть терм;

• всякая переменная x X, где X - исходное множество-носитель, есть терм;

• если f - функциональный символ F, а t1,..., tn – термы T, то f ( t1,..., tn) – терм.

Термы находятся как в функциональных, так и в предикатных отношениях. Фактом принято называть предложение, являющееся истинным высказыванием. В предложении элементы x1, x2, …, xh высказывания находятся в некотором отношении, которое обозначают предикатным символом Р.

Определение 1. Назовем фактом предикат вида P0(t1,...,tn), t j T, при этом существуют некоторые ti=f(t1,...,tm), f F - множеству частичных функций.

В этих обозначениях ситуацией называется конечная конъюнкция фактов, через D обозначается множество всевозможных ситуаций. Понятие ситуации соответствует понятию текущего состояния базы данных или рабочей памяти.

Если все ti (i = 1... n) в факте суть константы, то факт называется терминальным.

Поскольку среди фактов ситуации могут быть нетерминальные, то в общем случае ей соответствует неединственный набор множеств носителей.

Определенная таким образом ситуация представляет собой множество конъюнктивно-связанных фактов, и поэтому в дальнейшем будем обращаться с нею как с множеством, используя операции объединение, пересечение, разность \ и отношение включения.

Традиционным образом введем понятие подстановки и примера.

Определение 2. Подстановка – это конечное множество вида {t1/v1,…,tn/vn}, где каждая vi – переменная, а ti – терм, отличный от vi, при этом все vi различны. Подстановка, которая не содержит элементов, называется пустой и обозначается.

Определение 3. Пусть ={t1/v1,…,tn/vn} – подстановка и Е – выражение. Тогда Е – выражение, полученное из Е заменой одновременно всех вхождений переменной vi (1in) в Е на ti. Е называют примером Е.

Тогда запись d является примером d и означает результат одновременной замены каждого вхождения переменной vi, в d на соответствующий терм ti.



Pages:   || 2 | 3 | 4 | 5 |   ...   | 6 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.