автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Моделирование процесса распознавания сверхфразовых единств в текстах при установлении их семантической эквивалентности

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ НОВГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. ЯРОСЛАВА

МУДРОГО

На правах рукописи УДК 681.3.06

МИХАЙЛОВ ДМИТРИЙ ВЛАДИМИРОВИЧ

МОДЕЛИРОВАНИЕ ПРОЦЕССА РАСПОЗНАВАНИЯ СВЕРХФРАЗОВЫХ ЕДИНСТВ В ТЕКСТАХ ПРИ УСТАНОВЛЕНИИ ИХ СЕМАНТИЧЕСКОЙ ЭКВИВАЛЕНТНОСТИ

Специальность 05.13.18 - Теоретические основы математического моделирования, численные методы и комплексы программ

Автореферат диссертации на соискание ученой степени кандидата физико - математических наук

\

Великий Новгород ^ЖЯС1 ¡Лс

2003

Диссертация выполнена на кафедре ПОВТ Новгородского государственного университета им. Ярослава Мудрого

Научный руководитель:

- доктор технических наук, профессор Емельянов Геннадий Мартинович.

Официальные оппоненты:

- доктор технических наук, профессор Немирко Анатолий Павлович;

- кандидат технических наук, доцент Исаев Владимир Александрович

Ведущая организация :

Научный совет по комплексной проблеме "Кибернетика" РАН, г. Москва.

диссертационного совета О при Новгородском государственном

университете им. Ярослава Мудрого (175003, Россия, г. Великий Новгород, ул. Б. Санкт-Петербургская, 41)

С диссертацией можно ознакомиться в библиотеке университета.

часов на заседании

Автореферат разослан "30" мал гооз г.

Ученый секретарь диссертационного совета к.ф.-м.н., доцент

Беляев К.Н.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Актуальность темы. Создание и развитие ЭВМ с расширением сфер их применения привело к потребности приближения языка общения конечного пользователя с ЭВМ к языку решаемой задачи. Появление в 60-е годы специализированных языков программирования высокого уровня для решения задач искусственного интеллекта, с одной стороны, и развитие в 90-е годы средств автоматизации программирования, с другой стороны, неизбежно ведут к потребности общения пользователя с ЭВМ на предметно-ориентированном языке, максимально приближенном к Естественному Языку (ЕЯ). Разработка таких языков требует моделирования различных аспектов языкового поведения человека в зависимости от задачи, для решения которой разрабатывается тот или иной язык.

Решаемая в настоящей диссертационной работе проблема относится к вопросам обработки ЕЯ и ориентирована на практическую реализацию в системах по установлению смысловой тождественности входной текстовой информации.

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

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

Достижение сформулированной цели предполагает решение следующих основных задач:

1) Построение концептуальной модели процесса распознавания смысловой взаимной дополняемости фраз анализируемого высказывания;

2) Исследование свойств построенной модели в аспекте проблем алгоритмической разрешимости и вычислительной сложности ;

ЮС. национальная БИ(. ПОТЕКА

юоГр-.

3) Разработка методов и алгоритмов для программной реализации полученной модели;

4) Исследование вопросов взаимодействия процессов построения образов сверхфразовых единств в анализируемом тексте и установления его эквивалентности смысловому эталону.

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

Научная новизна работы. В диссертации получены следующие результаты, являющиеся новыми:

Предложена формальная концептуальная модель процесса распознавания семантической взаимной дополняемости фраз в сравниваемом со смысловым эталоном высказывании с использованием Лексической Синонимической Конструкции (ЛСК) в качестве элемента повтора;

- Сформулированы и доказаны теоремы о свойствах языка сети Петри, моделирующей работу системы правил Д-грамматики;

- Разработан и программно реализован алгоритм поиска путей к целевым состояниям системы правил Д-грамматики;

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

- Дано формальное определение и разработаны алгоритмы установления функционального соответствия и построения суммарного образа глубинных синтаксических структур;

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

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

Достоверность полученных результатов основана на корректности формулировок основных теоретических положений работы и строгости

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

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

Реализация результатов работы. Работа выполнена в рамках проекта РФФИ №03-01-00055, при поддержке гранта № ТОО-3.3-408 Минобразования РФ, в рамках работ по контракту № И 0675 ФЦП "Интеграция".

Разработанные программные средства и методические материалы использовались в учебном процессе при проведении лабораторных и курсовых работ по дисциплинам "Системы искусственного интеллекта", "Функциональное программирование" для студентов специальностей 220400 и 010200 в Новгородском государственном университете.

Апробация работы. Полученные результаты докладывались и обсуждались на конференциях : 5-й Международной конференции "Распознавание-2001". Курск, 2001; 10-й Всероссийской конференции Математические методы распознавания образов (ММРО-Ю), Москва, 2001; VI Всероссийской конф. "Методы и средства обработки сложной графической информации", Нижний Новгород, 2001; Международном семинаре Диалог'2002 «Компьютерная лингвистика и интеллектуальные технологии", Москва, 2002, Международной научной конференции ИОИ'2002 "Интеллектуализация обработки информации", Алушта, 2002; 6-й Международной конференции "Распознавание образов и анализ изображений : новые информационные технологии" (РОАИ-6-2002), Великий Новгород, 2002.

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

Все научные и практические результаты получены соискателем самостоятельно.

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

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе формулируются требования к процессу распознавания смысловой взаимной дополняемости фраз сравниваемого с эталоном текста. Исследуются свойства ЛФ-синонимических преобразований (синонимических преобразований деревьев глубинного синтаксиса (Глубинных Синтаксических Структур, ГСС) в рамках подхода "СмыслоТекст" на основе аппарата Лексических Функций (ЛФ)), актуальные для построения модели исследуемого

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

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

Возможность применения к одному и тому же дереву ГСС нескольких правил синонимических замен позволяет говорить об относительности ЛФ-синонимии и описыавть применимость различных правил к одному и тому же дереву списком вида:

((правило С„ (/))... {правило _ к С0(к))), (1-1-1)

где /, .... к- номера лексических правил синонимических преобразований.

При выполнении необходимого (но не достаточного) условия ЛФ-синонимии ГСС установление их эквивалентности производится в два этапа: Построение последовательности лексических преобразований (с обслуживающими их синтаксическими преобразованиями) сравниваемых деревьев ГСС, приводящих их ЛСК к одинаковому виду; - Сравнение преобразованных деревьев на предмет эквивалентности.

Эквивалентность -деревьев (помеченных деревьев с пометками в узлах из множества АУ и пометками на ветвях из множества V) определена в работе как изоморфизм при равенстве пометок идентичных узлов.

Поскольку деревья верхнего и нижнего контекста, заменяемые лексическими+обслуживающими их синтаксическими правилами, остаются без изменений, то установить эквивалентность приведенных к виду с одинаковой ЛСК деревьев ГСС можно путем последовательного сравнения заменяемых деревьев, деревьев верхнего и нижнего контекста.

Показанное свойство ЛФ-синонимических преобразований позволяет рассматривать ЛФ-синонимию ГСС при задании их ЛСК относительно одного и того же ключевого слова С0 как частный случай семантического повтора на основе значений лексических функций самостоятельных лексем с использованием ЛСК в качестве элементов повтора.

Необходимое условие взаимной дополняемости ГСС формулируется как наличие последовательности ЛФ-синонимических преобразований, приводящих анализируемые ГСС к виду с одинаковой ЛСК. Сама взаимная дополняемость определяется следующим образом.

Определение 1.1.5. Считается, что приведенные к виду с одинаковой ЛСК деревья глубинного синтаксиса Т1 и Т2 взаимно дополняют друг друга, если они изоморфны таким образом, что для всякого узла а дерева Т1 его образ /(а) в дереве Т2 :

- либо содержит информацию об одной и той же характеризованной обобщенной лексеме данного ЕЯ, не являющейся нулевой (фиктивной) лексемой;

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

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

При этом суммирование взаимно дополняющих друг друга ГСС производится путем наложения при совмещении одноименных стрелок.

Замечание. Деревья 77 и Т2 имеют ложную взаимную дополняемость, если будучи приведенными к виду с одинаковой ЛСК, они не могут взаимно дополнять друг друга.

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

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

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

Учитывая возможность ложной взаимной дополняемости деревьев глубинного синтаксиса анализируемого высказывания, выдвигается требование возможности использования для решения основной задачи множеств ЛФ-синонимичных ГСС, полученных при решении задачи распознавания смысловой взаимной дополняемости ГСС анализируемого высказывания. Кроме того, общее требование к модели в целом : модель должна быть задана формально, а в качестве контрольного критерия выдвигается реализуемость модели или любого ее фрагмента на ЭВМ.

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

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

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

Для заданного ЕЯ Г вводится в рассмотрение язык смыслов У$:

У5=<1Х Г& Я 0, и>, где (1.4.1)

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

В качестве языка У$ рассматривается язык глубинного синтаксиса.

Процедура Q содержит допустимые и лексические и *

синтаксические правила преобразований эквивалентных смысловых образов друг в друга (ЛФ-синонимических преобразований глубинных синтаксических структур).

Компонента и описывает приведение связанных по смыслу (по мнению носителя языка У) в Уs фраз к формальному представлению, допускающему нахождение искомого суммарного смысла (в содержательной интерпретации - к виду с одинаковой ЛСК). Кроме того, в I! содержатся правила построения единого смыслового образа для "приведенных" фраз из Уя- Исходя из вышесказанного, представим компоненту и упорядоченной двойкой :

и=<0„, где (1.4.2)

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

Би -процедура, содержащая правила построения единого смыслового образа для "приведенных" фраз из Уу (суммарного смысла в языке У,$).

Выбранный язык Ys обладает следующими свойствами, актуальными для распознавания смысловой взаимной дополняемости фраз в сравниваемом с эталоном ЕЯ-тексте:

Если фразы ^ и ^ языка У по мнению носителя ЕЯ У взаимно дополняют друг друга по смыслу, то полученные с помощью процедуры Я образы Ф/ и Ф2 этих фраз в языке У5 процедурой ()и сводятся к виду, допускающему нахождение искомого суммарного смысла, а затем посредством процедуры 5[/ переводятся в одну фразу Ф языка Ул соответствующую образу суммарного смысла; - Если фразам ^ и ^ языка У соответствуют полученные с помощью процедуры Я фразы Ф1 и Ф2 языка У& сводимые процедурой к представлению, допускающему нахождение искомого суммарного смысла, но не сводимые с помощью процедуры в единую фразу языка Ул то

фразы Fi и F2 следует считать фразами с ложной смысловой взаимной дополняемостью.

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

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

- Описания механизма применения определенных в процедуре лексических и синтаксических преобразований фраз из {Ф};

- Описания процедуры U;

- Описания механизма взаимодействия процедуры Q с процедурой U в процессе установления эквивалентности в Ys-

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

фраз ЕЯ У к виду, допускающему нахождение единого смыслового образа в языке (компонент Qv концептуальной модели).

Для решения основной задачи главы строится инфологическая модель системы правил расширенной лексико-синтаксической Д-грамматики г". Множество {г*} входов и выходов правил хе(п'\п') произвольных элементарных преобразований в Г* составляет множество информационных элементов. \г"}={г*}и\г"\, где {/¡'} -множество "входов", {г2*} -множество "выходов" правил. Множество {г*} обладает следующим свойством : часть элементов \rt"} и {г/} связаны соотношением : выход одного правила является входом другого, что позволяет строить единую систему из совокупности моделей правил яе (п* \Я*) как объектов-примитивов.

Состоянию системы соответствует активизация входа/выхода некоторого правила.

Каждое правило же(п'\п*) (в содержательной интерпретации -правило синонимического перифразирования) моделируется элементарной » сетью Петри. При этом множество состояний правила есть множество Р

позиций (мест) : Р = {р„р2}, где />, о Т", а р2 <=> Т". Множество возможных переходов Т представлено единственным описываемым моделируемым правилом переходом из состояния Т" в состояние Т" : t = x(rn): pt —>р2. Компонент R в описании правила ле(п" \П*), отвечающий за применимость правила, представляется логической функцией :

гу=*'л*2л...л;к" (2.1.1)

Правило я может бьггь применено к дереву Т", если выполняется одно из условий гt е R : v", гj = true. Применение правила /те /7* сводится к выполнению перехода:

я(Ги ) '■ —iiä2l_> т", (2.1.2)

При представлении отдельного правила элементарной сетью Петри модель совокупности правил пе(п'\п") есть совокупность сетей Петри, построенных из моделей отдельных правил как примитивов.

Для сети N. одной отдельно взятой г'-й системы правил, / е 1,... , пяуз, множество позиций Р1 есть подмножество {г*} элементов, составляющих входы и выходы способных образовывать систему правил. Множество 7] переходов составляет множество описываемых соотношением (2.1.2) переходов между состояниями системы.

Последовательность применяемых правил моделируется

последовательностью г = ((], г].....(*) срабатываний переходов :

Т* ».(1;) _*Лъ) ->...->т*_(2.2.4)

приводящей к последовательной смене разметок:

д/0,—¡им,'—^Л/,2...-^^, (2.2.5)

где, согласно (2.2.4), М0, о Т", М) <=> Г*,..., А/,' о 7£,.

Множество достижимости л(лг) сети Ы1 зависит от задания начальной разметки М01. Функционирование системы описывается в терминах последовательностей срабатываний переходов /(',<,2,...,каждая из которых есть слово г в языке ).

Задача приведения деревьев т" и ГД, к виду с одинаковой ЛСК включает три задачи:

1). Определение достижимости А/* из м0, есть определение наличия слова г е Т'\м01 —'—>М?, где Г' - множество всех слов в алфавите Г,;

2). Задача обратимости слова т : если г е Т'\мш —>А/,* (см. (2.2.4) и (2.2.5)), то существует ли слово х = (г'',/,""",...,/,2',/,1'):

мш <-4— М) <Л- Л/2... А/;-' <Л- м*, (2.2.6)

где, согласно (2.2.4), М0, Т", м) о Т",..., А/* о ;

3). Задача определения оптимального слова г е г,"|а/ш —'—>м, . Если 3 т„т2,...,т, : М„, >А/*, Мш >А/,* и А/,„ '> >А/*, то в качестве оптимального берется обратимое слово минимальной длины.

Для решения указанных задач проводится исследование языка £(ЛГ). Как результат исследования сформулированы и доказаны две леммы и ряд теорем.

Лемма 1. Все правила ле(п" \П") в грамматике Г* различны.

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

Лемма 2. Проблема достижимости заданной разметки А/,* из начальной М01 в сети ЛГ разрешима.

Доказательство леммы следует из доказанной для ограниченных сетей Петри конечности дерева достижимости.

Теорема 2. Все символы-переходы </ е 7; сети И1 различны.

Доказательство следует из доказанной леммы 1.

Из доказанной теоремы следует, что помечающая функция Г: 7] -> Л для сети Ы1 сопоставляет каждому переходу г/ е Т, единственный символ, соответствующий обозначению правила ж е (п* \ Я*).

Теорема 3. Проблема определения обратимости слова г е Т'\м0, —'-^М* языка разрешима.

Доказательство. При известной последовательности смены разметок (см. (2.2.6)) и наличии по лемме 1 взаимно-однозначного соответствия между ней и последовательностью переходов х = (г*',«'*4',...,*,2',^1') задача сводится к определению принадлежности слова г'языку 1(лг). Префиксный язык {х(г)|г е /.(лг)} помеченной сети относится либо к классу ех, либо к

подклассу ( этого класса префиксных языков сетей Петри, для которых проблема принадлежности разрешима, что позволяет говорить о разрешимости нахождения обратного слова для т е Т'\м01 —.

Теорема 4. Проблема определения оптимального слова теТ'\мС1—(т' - множество всех слов в алфавите 7]) в языке ¿(ЛГ,) является разрешимой.

Доказательство. Для любой разметки М* в сети N¡ проблема ее достижимости из выбранной начальной М01 является разрешимой по лемме 2. Определение обратимости слова языка ¿(лг,) разрешимо по теореме 3. Определение минимального слова среди обратимых делается

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

С целью сокращения перебора при определении оптимального слова х е Т'\м0, —и учитывая требование равноудаленности целевого состояния от состояний, соответствующих м01 и м*, предложено рассматривать состояние системы одновременной активизацией не одного, а двух информационных элементов, соответствующих в предложенной модели сценарию. Множество сценариев <={г*}х{г*} разбивается на

непересекающиеся множества : = ^^ и- •■и5„ 1у1, где -

количество систем правил хеПЛ на заданном множестве |т"}, причем

П"\, 5, - множество всех сценариев внутри одной системы. Формально каждый сценарий 5/ е 5, определяется как 5/ = {г',7)'}, где Т" е{г*}, Т" е{г'}. Целевому состоянию системы (решение найдено) соответствует наличие двух фишек в некоторой позиции р/ : М,(р'1)=2 и 5/ = {т/.Г,*}: Т"=Т".

Поскольку в рамках сценария 5/ может быть разрешено несколько переходов, то для 5/ е будет справедливым следующее описание :

я* = №,'{к!\р;\, где (2.4.4)

геу/(к>)= [у,",...,- множество сценариев, связанных с 5/ через разрешенные в его рамках переходы </ е 7], Р/ е \р),р)} - множество позиций сети , активных в рамках 5/.

Далее показывается, что описание 5/ в виде (2.4.4) затрудняет обратный просмотр от 5/ к 5," для формирования пути к найденному решению. С целью устранения указанного недостатка автором настоящего исследования предлагается описание , учитывающее вытекающую из теоремы 5 единственность последовательности смены сценариев от Я? к 8/ :

= \ге/_Ьаск/,Р/\, где (2.4.8)

Р/ определяется аналогично структуре (2.4.4), ге/_Ьаск{ - ссылка на сценарий, с которым 5/ связан посредством некоторого перехода </ е 7].

При описании сценария в виде (2.4.8) поиск целевого сценария 'р! = \р] > р] }: р) = р] на основе заданного начального 5° = \riil, \р'0, р]}} организуется как генерация списка ге//(к?) каждого сценария 5/ очередного уровня с попутной проверкой условия р\ = р] для каждого создаваемого сценария и последующим объединением всех списков г*// (к/) одного уровня и повторением процедуры для полученного списка в случае отсутствия решения на созданном уровне дерева сценариев, либо запоминанием пути по дереву от 5° для каждого найденного решения.

Генерация каждого из 5/ происходит путем обработки матрицы инцидентности К В качестве исходных данных при этом берутся два массива: - массив информации о переходах - ссылок на описание определяемых соотношениями (2.1.1) и (2.1.2) условий применимости соответствующих переходам е Т, правил п е Я* \ п' рассматриваемой А-грамматики:

I ,.=и.-><Г'1} (2.4.5)

'Ещ, массив ссьшок на описание входов/выходов правил /-Й системы:

= (2.4.6)

Описывая систему правил А-грамматики парой массивов X = (Е*,,!^), можно описать динамику ее функционирования построением Т8-сети на основе задаваемой начальной разметки : Р° = \р\,р20), для у/ = 1,...,|Р,| р{ еР° если т°(р/) = 1 и р{ I Р° если т°(/?/)= О с использованием предложенных в главе алгоритмов.

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

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

- Лексическую часть, соответствующую представленному в узле элементу глубинной лексики;

- Грамматическую часть, содержащую семантические словоизменительные характеристики.

Если дерево глубинного синтаксиса фразы % представить как :

T?'r=(w;,r.r;,r), где (3.1.2)

Wx'y с W - множество узлов W/V - дерева тх'у, vx'y с V - множество ветвей W/V - дерева Тх'у, то информационное наполнение узла wz е Wz'y может быть представлено списком из двух элементов :

= (ilex_inх,gram_inz), где (3.1.4)

элемент lex_inx соответствует лексической, gram_inz - грамматической части узла wz.

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

lex_inz = (С„,fun.,...,fun,), где (3.1.6)

С0 - самостоятельная лексема, лексической производной от которой (в виде последовательно взятых значений лексических функций /ил,,...,/ил,) является соответствующая содержимому узла ГСС лексема (на поверхностно-синтаксическом уровне).

Грамматическая часть узла представляется упорядоченной двойкой : Gram inх = (part of speech, listsemant categ), где (3.1.7)

part of speech - символьный атом, обозначающий часть речи, list semant categ

- список семантически обусловленных словоизменительных категорий.

Для обозначения того факта, что рассматриваемый узел wx е W"'" (3.1.4) дерева ГСС Tz" (3.1.2) фразы х является выделенным в некотором преобразовании л, в списочное описание wz (3.1.4) вводится необязательный элемент composition Jabel - композиционная метка узла :

Wj = (lex _ inz, gram _ inx, arrow _ label, composition _ label) (3.1.11)

Подобное списочное описание позволяет :

- Формально представить функциональные требования к узлу ГСС при описании компонент заменяемого некоторым лексическим правилом дерева. При этом сам символ С0 выступает в качестве служебного : им задается местонахождение ключевого слова.

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

Задача применения правила Д-грамматики к W/V-дереву в настоящей работе рассматривается как частный случай изоморфизма подграфу с точностью до функционального соответствия. Само функциональное соответствие автором определяется следующим образом.

Определение 3.11 Два W/V дерева t[ и считаются изоморфными с точностью до функционального соответствия, если между множествами узлов этих деревьев существует взаимно-однозначное соответствие так, что в дереве t[ из узла А' в узел В' идет ветвь с некоторой пометкой тогда и только тогда, когда в дереве из узла А в узел В идет ветвь с той же пометкой и узел А' удовлетворяет требованиям, содержащимся в узле А, а узел В' удовлетворяет требованиям, содержащимся в узле В.

Показанная особенность применения правила позволяет представлять его совокупностью описания входного, выходного деревьев и условий применимости в виде требований к отдельным элементам описания входа. При этом структура входа/выхода представляется деревом, аналогичным (3.1.2), для узлов которого вводятся аналогичные (3.1.4), (3.1.6) и (3.1.7) элементы списочного описания. Существенной особенностью представления информации узлов w, e w"'r входного/выходного дерева Тправила я является отсутствие определения отдельных компонент дерева. В таком случае считается, что соответствующий компонент в описании входного дерева правила перифразирования имеет пустое или неопределенное значение (nil).

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

N, = \P„T„F„ НК,С, М"0\, в которой (3.2.1)

Множество позиций Рх соответствует множеству состояний информационного элемента, рассматриваемого как система. Каждое состояние отождествляется с очередным пройденным узлом дерева т"'г при анализе или синтезе. Каждому из переходов t[ е Т^ соответствуют вычислению значений функций lex_in„, gram_in„, arrow Jabelг для очередного узла w„. F. и Н, есть матрицы инцидентности, F, : Р, х т. {од} и Н,:Т,хРг-+{0,1}. С = {colorl,color2} -множество цветов маркера. М": Р„ {0,1} - начальная маркировка или разметка.

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

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

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

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

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

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

Теорема 11. Пусть Л^ =\р„,Т'„,К<Н],,С,М"') - сеть Петри, являющаяся сетью действий, причем с каждым из переходов t'K е Т'ж связано вычисление некоторой логической функции. Тогда, если считать матрицы инцидентности F'K и Н\ логическими функциями, то для того, чтобы V t>K 6 т'„ был достижим из начальной разметки М*, достаточно выполнения условия :

WM"W, ,г , , ,г , ,4 (3.2.5)

А V h,[i,к]л1'.)= true, где

i»J

a,v,-> - логические функции конъюнкции, дизъюнкции и импликации, соответственно, fi,[k,j]eF„, h~[i,k]eIf" - соответствующие элементы матриц инцидентности, причем расширенная матрица Н" получена из матрицы Н'„ путем дополнения строкой следующим образом :

л;|г;|+и]=1,если M'(pi)=\, л;|г;|+и]=о,если м/(р>,)=о.

Доказательство. Если считать переходы t{ е Тк безусловными, т.е. t{ = true для v _/' б 1.....|г,|, то в качестве частного случая имеем условие

Wk.M'il.

достижимости перехода для ограниченных сетей : л v \k,j\ -> true ■

Из теоремы 11 следует, что определение применимости правила л со входом, представленным в виде дерева Т*'у, сводится к задаче достижимости перехода из начальной разметки в ¿-ограниченной (А=1) сети Петри, моделирующей процесс обхода дерева.

Далее в главе исследуются вопросы построения суммарного образа для W/V-деревьев, приведенных к виду с одинаковой ЛСК. Дается формальное определение функционального соответствия узлов суммируемых ГСС с использованием предложенного в начале главы функционального описания W/V-деревьев.

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

- замененных совместной работой лексических правил и обслуживающих их синтаксических замен;

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

Как результат этого исследования сформулированы и доказаны следующие теоремы.

Теорема 12. Задача установления функционального соответствия W/V-деревьев Т"'г и г"г принадлежит классу Р комбинаторных задач с временной

оценкой п", где n = mzx\w™\\w%r§, £> = ¿>(0,), где ¥, = fa"fl2''"'fl'l- матрица,

«-1 \ni>ni''"'nk) задающая ограничения на характер ветвления и на размещение пометок на ветвях из V, где {л,,л2,с N - подмножество натуральных чисел.

Доказательство теоремы производится через сведение рассматриваемой задачи к известной NP-полной задаче "Изоморфизм подграфу".

Теорема 13. Задача поиска для каждого дерева ТЩ"Г из множества W/V-деревьев forest 1 дерева из множества W/V-деревьев forest2,

функционально соответствующего Т"", принадлежит классу Р комбинаторных задач с временной оценкой и", где множества forest 1 и forest2 пред ставимы в виде лесов (forest 1=(vr\E"), forest2=(vf\En)) и л = тах|ия|,|г/2|), а

D = 5>(Д,).

1=1

Доказательство теоремы производится через сведение задачи установления функционального соответствия W/V-деревьев к рассматриваемой задаче методом сужения (добавлением в forest 1 и forest2 по одной вершине каждый лес преобразуется в дерево).

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

позволяют решать с временной оценкой задачу установления взаимной

дополняемости W/V-деревьев анализируемой последовательности Ф1.

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

смысловому эталону в плане оперирования ЛФ-синонимическими множествами ГСС.

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

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

((правило (i) count (i) С0 (i, count (/)))... (правило (к) count (к) С0 (к, count (к)))), (4.1.2) ( (composition _ label(i,j, count(i)) count(i) правило(/)). .Л (4.1.3)

Цcomposition _ label{k, l, count(k^) counl(k) npaewio(k)) J ' где j,l - номера композиционных меток, соответственно, count(i) и count(k)-го вхождений заменяемых i-м и к-м правилами поддеревьев.

Использование списка (4.1.3) при анализе применимости правила с расстановкой композиционных меток позволяет избежать зацикливания процесса анализа на одном правиле Д-грамматики.

Формирование указанным образом представляемых элементов composition Jabel (4.1.3) списочного описания (3.1.11) выделенных в Т"" узлов согласуется с формированием списка (4.1.2) для дерева Т"'у следующим

образом : элемент списка (4.1.3), относящийся к некоторому правилу я, формируется в случае успешного завершения анализа применимости правила и занесения в поле composition_label списочных описаний (3.1.11) выделенных узлов заменяемого правилом поддерева информации в соответствии с (4.1.3).

При размещении в списке (4.1.2) информации о не применявшихся ранее к дереву правилах, с помощью приведенного в главе алгоритма можно последовательно определять наличие взаимной дополняемости деревьев глубинного синтаксиса т"'у и Т'1Г, удовлетворяющих относительно разных ЛСК необходимому условию ЛФ-синонимии, определяя по стоящим в помеченных узлах анализируемого дерева композиционным меткам (4.1.3) заменяемые правилами поддеревья.

Удаляя для каждой из сравниваемых ГСС из списка (4.1.2) информацию об уже применявшихся к дереву преобразованиях, полученный алгоритм позволяет избежать повторного поиска правил, применимых к Т"'г и T'Jr при построении оставшейся части ЛФ-синонимических множеств для Т"'у и Т"2'у в процессе установления семантической эквивалентности высказывания заданному эталону на случай ложной взаимной дополняемости Т"'у и Т"2'у.

Далее в работе проводится качественный анализ процесса построения ЛФ-синонимических множеств ГСС с учетом применения для их генерации преобразований различных типов и предложенного алгоритма. Завершает главу описание структуры базы правил и базы ГСС программного комплекса

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Емельянов Г.М., Михайлов Д.В. Вопросы моделирования семантической связанности для систем понимания текста. // Сборник материалов 5-й Международной конференции "Распознавание-2001". Курск, 2001, Часть 1, с. 56-58.

2. Емельянов Г.М., Михайлов Д.В. Вопросы моделирования семантической связанности для систем автоматизированного тестирования знаний. // Математические методы распознавания образов (ММРО-Ю) Доклады 10-й Всероссийской конференции. Москва, 2001, с. 53-56

3. Емельянов Г.М., Михайлов Д.В. Вопросы построения механизма суммирования смысла для систем распознавания текстов на естественном языке. // Методы и средства обработки сложной графической информации. VI Всероссийская конф.: Тез. Докл. Нижний Новгород, 2001, с. 83-85

4. Емельянов Г.М., Михайлов Д.В., Зайцева Е.И. Динамическая модель естественного языка в системах пользовательских интерфейсов. // «Компьютерная лингвистика и интеллектуальные технологии" Труды международного семинара Диалог'2002. Москва, 2002, т.2 с. 165-170

5. Емельянов Г.М., Зайцева Е.И., Михайлов Д.В. Построение динамической модели естественного языка применительно к разработке языковой базы знаний. // Научно-теоретический журнал "Искусственный интеллект", 2'2002. Донецк, 2002, с. 443-446

6. Емельянов Г.М., Михайлов Д.В., Зайцева Е.И. Синонимические преобразования в задаче анализа эквивалентности смысловых образов высказываний на уровне сверхфразовых единств. // 6-я Международная конференция "Распознавание образов и анализ изображений : новые информационные технологии" (РОАИ-6-2002).. Великий Новгород, 21-26 окт. 2002 г.: Тр. Конф., Т.1. с. 215-219

7. Емельянов Г.М., Зайцева Е.И., Михайлов Д.В., Курашова Е.П. К разработке распознающей системы анализа смысловых образов высказываний на естественном языке. // 6-я Международная конференция "Распознавание образов и анализ изображений : новые информационные технологии" (РОАИ-6-2002).. Великий Новгород, 21-26 окт. 2002 г.: Тр. Конф., Т.1. с. 220-223

8. G.M.Emelyanov, E.I.Zaitseva, D.V.Mikhailov, and E.P.Kurashova Development of Recognition System of Analysis of Semantic Images of Natural Language Statements //Pattern Recognition and Image Analysis.- 2003.-Vol.13, No.2.-P.251-253

9. G.M.Emelyanov, D.V.Mikhailov, and E.I.Zaitseva Synonymic Transfonnations in Analysis of Semantic Pattern Equivalence at the Superphrase Unity Level //Pattern Recognition and Image Analysis.- 2003.-Vol.13, No.l.-P.21-23 Ю.Емельянов Г.М., Михайлов Д.В. Распознавание сверхфразовых единств при установлении эквивалентности смысловых образов высказываний в общей задаче моделирования языковой деятельности // Известия СПбГЭТУ "ЛЭТИ", серия "Информатика, управление и компьютерные технологии", Выпуск 1. - Санкт-Петербург., 2003. - С.65-73

РНБ Русский фонд

2005-4 45827

Изд. лиц. JIP № 020815 от 21.09.98. Подписано в печать 23.05.2003. Бумага офсетная. Формат 60x84 1/16. Гарнитура Times New Roman. Печать офсетная. Уч.-изд. л. 1,3. Тираж 100 экз. Заказ № 75.

Издательско-поли графический центр Новгородского государственного университета им. Ярослава Мудрого. 173003, Великий Новгород, ул. Б. Санкт-Петербургская, 41.

Отпечатано в ИПЦ НовГУ им. Ярослава Муцрого.о г , 173003, Великий Новгород, ул. Б. Санкт-Петербургска4 .

ВВЕДЕНИЕ

1 МОДЕЛИРОВАНИЕ ПРОЦЕССА РАСПОЗНАВАНИЯ СВЕРХФРАЗОВЫХ ЕДИНСТВ В ТЕКСТЕ ПРИ СОПОСТАВЛЕНИИ СО СМЫСЛОВЫМ ЭТАЛОНОМ.

ПОСТАНОВКА ЗАДАЧИ

1.1 .Постановка задачи на функциональном уровне

1.2.Критерии адекватности формальной модели

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

1.4.Концептуальная модель и общая формальная постановка задачи

1.5. Выводы по главе

2. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ПРОЦЕССА ПРИВЕДЕНИЯ ГЛУБИННЫХ СИНТАКСИЧЕСКИХ СТРУКТУР К ЦЕЛЕВОМУ ВИДУ 31 2.1. Моделирование правила А-грамматики элементарной сетью Петри

2.2. Моделирование системы правил А-грамматики ограниченными сетями Петри

2.3. Исследование вопросов алгоритмической разрешимости и сложности построения целенаправленного вывода в А-грамматике

2.4. Исчисление сценариев для задачи приведения образов двух фраз к целевому виду

2.5. Выводы по главе

3. МОДЕЛИРОВАНИЕ ПОСТРОЕНИЯ ОБРАЗА СУММАРНОГО СМЫСЛА 76 3.1.Функциональная структура информационного наполнения узла дерева глубинного синтаксиса

3.2. Математическая модель входа/выхода правила Д-грамматики

3.3. Алгоритм построения образа суммарного смысла

3.4. Выводы по главе 118 4. ВЗАИМОДЕЙСТВИЕ ПРОЦЕССОВ ПОСТРОЕНИЯ ОБРАЗОВ СВЕРХФРАЗОВЫХ ЕДИНСТВ В АНАЛИЗИРУЕМОМ ТЕКСТЕ И УСТАНОВЛЕНИЯ ЕГО ЭКВИВАЛЕНТНОСТИ СМЫСЛОВОМУ ЭТАЛОНУ

4.1. Активизация информационных элементов и относительность синонимических замен

4.2. Применение результатов целевого вывода в Д-грамматике при установлении эквивалентности высказывания смысловому эталону

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

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

4.5. Выводы по главе 146 ЗАКЛЮЧЕНИЕ 148 БИБЛИОГРАФИЧЕСКИЙ СПИСОК

Создание и развитие ЭВМ с расширением сфер их применения привело к потребности приближения языка общения конечного пользователя с ЭВМ к языку решаемой задачи. Появление в 60-е годы специализированных языков программирования высокого уровня для решения задач искусственного интеллекта, с одной стороны, и развитие в 90-е годы средств автоматизации программирования, с другой стороны, неизбежно ведут к потребности общения пользователя с ЭВМ на предметно-ориентированном языке, максимально приближенном к Естественному Языку (ЕЯ). Разработка таких языков требует моделирования различных аспектов языкового поведения человека в зависимости от задачи, для решения которой разрабатывается тот или иной язык.

Интерес к разработке систем общения с ЭВМ на ЕЯ проявляется как со стороны научных дисциплин, так и со стороны технических, связанных с разработкой и программной реализацией широкого класса интеллектуальных систем. Алгоритмически разрешимые процедуры распознавания смысловых образов высказываний ЕЯ, а также способы представления этих образовТдопускающие^ор^ ректно описываемые процедуры их переработки, позволят программно реализо-вывать интеллектуальные системы распознавания и синтеза речи, текста и изображений. Разработка таких систем относится к позиции "информационные технологии и электроника" перечня критических технологий федерального уровня от 21 июля 1996 г и образует самостоятельное направление, получившее название "Обработка естественного языка" [51].

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

Сферой рассмотрения автора настоящего исследования являются задачи, требующие установления полной или частичной эквивалентности по смыслу (семантической эквивалентности) высказываний (текстов) ЕЯ [71,72]. К числу таких задач можно отнести применение заданий открытой формы в системах компьютерного дистанционного обучения и контроля знаний [1,49,67], поиск изображений и распознавание семантики сложных информационных объектов по вербальному описанию [60,72,74,75].

Настоящая диссертационная работа посвящается решению проблемы полноты смыслового описания при установлении семантической эквивалентности текстов на ЕЛ [72] в рамках подхода " Смысл <=>Текст " [2,36].

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

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

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

Для постановки общей задачи распознавания смысловой взаимной дополняемости фраз ЕЯ и определения частных задач исследования необходимо формально определить само понятие эквивалентности семантических образов текстов в рамках рассматриваемого подхода к теоретическому описанию языка, формализовть понятие применимости правила синонимического преобразования и учесть общие соображения по технике суммирования формальных образов смысла, предлагаемые самими авторами теоретического подхода к языку как преобразователю "Смысл<=>Текст". Кроме того, необходимо строго определить ряд понятий, связанных с применением подобной техники суммирования к формальным образам смысла, которыми оперирует модель семантической эквивалентности текстов в рамках указанного теоретического описания языка. Решению этих вопросов посвящено начало первой главы предлагаемого исследования. Далее показано, что ни один из известных на сегодняшний день подходов к распознаванию сверхфразовых единств в текстах ЕЯ не отражает специфики решаемой в диссертации 'задачи увеличения полноты смыслового описания сравниваемых текстов. Предложен новый подход к распознаванию сверхфразовых единств на базе системы синонимических преобразований Глубинных Синтаксических Структур (ГСС) [2,14,36].

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

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

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

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

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

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

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

Материалы работы основаны на публикациях [20-27,73,76]. Полученные результаты апробированы в докладах на конференциях : 5-й Международной конференции "Распознавание-2001". Курск, 2001; 10-й Всероссийской конференции Математические методы распознавания образов (ММРО-Ю), Москва, 2001; VI Всероссийской конф. "Методы и средства обработки сложной графической информации", Нижний Новгород, 2001; Международном семинаре Диалог'2002 «Компьютерная лингвистика и интеллектуальные технологии", Москва, 2002, Международной научной конференции ИОИ'2002 "Интеллектуализация обработки информации", Алушта, 2002; 6-й Международной конференции "Распознавание образов и анализ изображений : новые информационные технологии" (РОАИ-6-2002), Великий Новгород, 2002.

Все научные и практические результаты получены соискателем самостоятельно.

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

Основное направление исследований связано с построением самих подлежащих анализу глубинно-синтаксических структур. В [72] для решения этой задачи предлагается классический подход на основе синтаксического анализа : текст - морфологическое представление - синтаксическое (поверхностно-синтаксическое [14,36]) представление - глубинное синтаксическое представление. Но, как показано в [28], общей вычислительной проблемой всех синтаксических анализаторов является рост дерева вариантов разбора с ростом числа правил установления синтаксических отношений и количества слов в анализируемом предложении. Подобная проблема обусловлена наличием омонимов и возможностью существования ряда грамматических форм одного и того же слова. Вследствие указанного роста числа вариантов разбора производительность алгоритма синтаксического анализа падает экспоненциально с ростом числа используемых правил и количества слов в предложении. Поэтому в качестве одного из дальнейших направлений исследований автором настоящей работы выделена разработка альтернативных методов построения глубинных синтаксических структур по морфологическому описанию входного текста на основе знаний о связи синтаксиса и семантики ЕЯ. В частности, здесь полезным может быть опыт привлечения знаний о семантических классах слов для интерпретации поверхностно-синтаксических отношений [47], а также использование описываемых Толково-Комбинаторным словарем Моделей Управления [77] для распознавания типов связей слов и их групп в предложении [44].

Второе направление исследований вытекает из результатов апробации реализованного исследовательским коллективом УНЦ НовГУ морфологического анализатора текстов русского языка и формулируется автором как построение обучаемых морфологических анализаторов, в частности, на основе статистического анализа текстов [59].

Учитывая ориентацию предлагаемого в диссертации подхода на использование в системе семантического анализа текстов, актуальными являются вопросы представления знаний о языке [5], используемых в рамках рассматриваемого подхода "Смысл «Текст", прежде всего описываемых Толково-Комбинаторным словарем. Здесь также требует более детальной проработки обсуждавшийся в [3] вопрос взаимодействия комбинаторного словаря и трансформационной грамматики при переходе от поверхностной к глубинной синтаксической структуре и наоборот.

ЗАКЛЮЧЕНИЕ

В заключении сформулируем положения, определяющие научные и практические результаты работы.

Основные научные результаты состоят в следующем :

- разработана формальная концептуальная модель процесса распознавания семантической взаимной дополняемости фраз в сравниваемом со смысловым эталоном высказывании;

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

- сформулирована и доказана лемма о разрешимости проблемы достижимости целевой разметки в сети, моделирующей систему правил А-грамматики;

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

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

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

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

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

1. Аванесов B.C. Композиция тестовых заданий. Учебная книга для преподавателей вузов, учителей школ, аспирантов и студентов педвузов. — М.: Адепт, 1998.-217 с.

2. Апресян Ю.Д. Избранные труды. В двух томах. Т.1. Лексическая семантика. Синонимические средства языка. — М.: Школа "Языки русской культуры", 1995.-472 с.

3. Апресян Ю.Д. Интегральное описание языка и толковый словарь. // Вопросы языкознания. 1986, №2. С.57-70.

4. Апресян Ю.Д. Об одном правиле сложения лексических значений, в кн.: "Проблемы структурной лингвистики. 1971", М., 1972, с. 439-458

5. Апресян Ю.Д. Формальная модель языка и представление лексикографических знаний. // Вопросы языкознания. — 1990, №6. С. 123-139

6. Белич А.И. К вопросу о распределении грамматического материала по главным грамматическим дисциплинам, "Вестник МГУ", 7, 1947

7. Белошапкова В.А. Современный русский язык : Синтаксис : Учеб. Пособие для филол. специальностей ун-тов. / В.А.Белошапкова. — М.: "Высшая школа", 1977.-248 с.

8. Большакова Е.И., Васильева Н.Э. К вопросу об автоматизации литературно-научного редактирования. // «Компьютерная лингвистика и интеллектуальные технологии" Труды международного семинара Диалог'2000. Москва, 2000, т.2 с. 59-634

9. Бухбиндер В.А., Розанов Е.Д. О целостности и структуре текста // Вопросы языкознания. 1975, №6. С.73-86.

10. Ю.Вейхман Г.А. К вопросу о синтаксических единствах (На материале современного английского языка) // Вопросы языкознания. 1961, №2. С.97-105.

11. П.Гаспаров Б.М. О некоторых лингвистических аспектах изучения структуры текста, в кн. "III летняя школа по вторичным моделирующим системам. Тезисы", Тарту, 1968

12. Гиндин С.И. Внутренняя организация текста. (Элементы теории и семант. анализ). Автореф. дис. на соискание учен, степени канд. филол. наук. (681) М., 1972. 23 с. со схем.

13. Гладкий A.B. Формальные грамматики и языки. — М.: Главная ред. Физ.-матлит., 1973.-368 с.

14. Гладкий A.B., Мельчук И.А. Грамматики деревьев. I. Опыт формализации преобразований синтаксических структур естественного языка, сб. «Информационные вопросы семиотики, лингвистики и автоматического перевода", вып. 1.-М., 1971.-стр. 16-41.

15. Гладкий A.B., Мельчук И.А. Грамматики деревьев. II. К построению Д-грамматики для русского языка, сб. «Информационные вопросы семиотики, лингвистики и автоматического перевода", вып. 4. М., 1974. - стр. 4-29.

16. Градулина JI.K. Вопросы нормализации русского языка. Грамматика и варианты. М.: Наука, 1980. - 228 с.

17. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи: Пер. с англ. М., Мир, 1982. - 416 с.

18. Демидова А.К. Пособие по русскому языку. Научный стиль речи. Оформление научной работы : Для студентов-иностранцев. М., Русский язык, 1991. — 201 е.: ил.

19. Дорофеев Г.В., Мартемьянов Ю.С. Логический вывод и выявление связей между предложениями в тексте, "Машинный перевод и прикладная лингвистика", 12, М., 1969.

20. Емельянов Г.М., Зайцева Е.И., Михайлов Д.В. Построение динамической модели естественного языка применительно к разработке языковой базы знаний. //Научно-теоретический журнал "Искусственный интеллект", 2'2002. Донецк, 2002, с. 443-446

21. Емельянов Г.М., Михайлов Д.В. Вопросы моделирования семантической связанности для систем понимания текста. // Сборник материалов 5-й Международной конференции "Распознавание-2001". Курск, 2001, Часть 1, с. 56-58.

22. Емельянов Г.М., Михайлов Д.В. Вопросы моделирования семантической связанности для систем автоматизированного тестирования знаний. // Математические методы распознавания образов (ММРО-Ю) Доклады 10-й Всероссийской конференции. Москва, 2001, с. 53-56

23. Ермаков А.Е. Неполный синтаксический анализ текста в информационно-поисковых системах. // «Компьютерная лингвистика и интеллектуальные технологии" Труды международного семинара Диалог'2002. Москва, 2002, т.2 с. 180-185

24. Жигалов В.А., Соколова Е.Г. InBASE: Технология построения ЕЯ-интерфейсов к базам данных. // «Компьютерная лингвистика и интеллектуальные технологии" Труды международного семинара Диалог'2001. Москва, 2002, т.2 с. 123-135

25. Жолковский А.К. О правилах семантического анализа, МпиПЛ, вып. 8, 1964, с. 17-32

26. Иванова Т.П. О характеристике связности газетного текста экономического содержания. // «Компьютерная лингвистика и интеллектуальные технологии" Труды международного семинара Диалог'2000. Москва, 2000, т.1 с. 108-109

27. Котов В.Е. Сети Петри. М.: Наука. Главная редакция физико-математической литературы, 1984. — 160 с.

28. Кук Д., Бейз Г. Компьютерная математика : Пер. с англ. М.: Наука, Гл. ред. Физ.-мат. Лит., 1990. - 384 с.

29. Леонтьева H.H. Семантика связного текста и единицы информационного анализа, НТИ, сер.2, № 1, 1981, с. 21 -29

30. Маслов Б.А. Проблемы лингвистического анализа связного текста. (Надфра-зовый уровень). Учеб. Пособие к спецкурсу. Таллин, ГНИ., 1975. — 104 с. с черт.

31. Мельчук И.А. Опыт теории лингвистических моделей "смысл<=>текст" : Семантика, синтаксис / И.А.Мельчук.-Переизд.. // Школа "Языки русской культуры". Москва, 1999. 345 с.

32. Минский М. Фреймы для представления знаний : пер. с англ. — М.: Энергия, 1979.-152 с.

33. Москальская О.И. Семантика текста // Вопросы языкознания. 1980, №6. С.32-42.

34. Невзорова O.A. Подход к построению семантико-синтаксического анализатора текстов на основе моделей синтаксем. // «Компьютерная лингвистика и интеллектуальные технологии" Труды международного семинара Диалог'99. Москва, 1999, т.2 с. 215-219

35. Николаев A.M. Описание семантики научного текста с позиций теории речевых актов (на материале рецензии на научно-техническую работу) // НТИ. Сер. 2, 1998, №7, с. 35-41

36. Никольский В.А. Предложение и контекст. М.: Русский язык в школе, № 3, 1948. - стр. 21-31.

37. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность: Пер. с англ. М.: Мир, 1985. - 512 с.

38. Перцова H.H., Перцов Н.В. О проекте лингвистического процессора для обработки информации из сети Интернет. // «Компьютерная лингвистика и интеллектуальные технологии" Труды международного семинара Диалог'2002. Москва, 2002, т. 1 с. 339-342

39. Петерсон Дж. Теория сетей Петри и моделирование систем. М.: Мир, 1984. -298 с.

40. Попов М.Ю. Концепция системы семантического анализа текста. // «Компьютерная лингвистика и интеллектуальные технологии" Труды международного семинара Диалог'2002. Москва, 2002, т.1 с. 351-355

41. Попов Э.В. и др. Искусственный интеллект. — В 3-х кн. — М.: Радио и связь, 1990

42. Поспелов Д.А. Логико-лингвистические модели в системах управления. — М.: Энергоиздат, 1981. 233 с.

43. Поспелов Н.С. Проблема сложного синтаксического целого в современном русском языке, "Уч. Зап. МГУ.", 137. Труды Кафедры русск. Языка, 2, М., 1948, с. 41

44. Поспелов Н.С. Сложное синтаксическое целое и основные особенности его структуры, "Докл. и сообщ. Ин-та русского языка АН СССР.", 2, М., 1948, с. 53

45. Представление и использование знаний : Пер. с япон./ Под ред. X. Уэно, М. Исидзука. М.: Мир, 1989. - 220 с.

46. Севбо И.П. Сквозной анализ как шаг к структурированию текста // НТИ. Сер. 2, 1989, №2, с. 2-9

47. Севбо И.П. Структура связного текста и автоматизация реферирования. — М.: Наука, 1969.- 135 с.

48. Серкова Н.И. О некоторых вопросах функциональной перспективы предложений в терминах "Сверхфразовых единств" // Вопросы языкознания. 1967, №3. С.92-100.

49. Синельников H.H. Статистический анализ текстов как средство автоматического построения морфологической модели языка. // «Компьютерная лингвистика и интеллектуальные технологии" Труды международного семинара Диа-лог'2002. Москва, 2002, т.2 с. 497-500

50. Смирнова Е.И. Моделирование структуры состояний сложной системы для задач прогнозирования. //Искусственный интеллект-2000.-Нац.акад.Украины, Институт Проблем искуст. Интеллекта.- Украина, г.Донецк, 2000.- С.196-200.

51. Солганик Г.Я. Синтаксическая стилистика (Сложное синтаксическое целое) : Учеб. Пособие для вузов по спец. "Рус.яз и литература" и "Журналистика". — М.: Высш. Шк, 1973. 214 с.

52. Тотков Г., Танев X. Компьютеризированное извлечение значения слов с помощью анализа связного текста. // «Компьютерная лингвистика и интеллектуальные технологии" Труды международного семинара Диалог'99. Москва, 1999, т.2 с. 360-365

53. Урысон Е.В. Дизъюнкция в естественном языке : союзы или, либо, не то . не то, то ли . то ли. // «Компьютерная лингвистика и интеллектуальные технологии" Труды международного семинара Диалог'99. Москва, 1999, т.1 с. 316318

54. Фигуровский И.А. От синтаксиса отдельного предложения — к синтаксису целого текста. — М.: Русский язык в школе, № 3, 1948. cip. 21-31.

55. Филд А., Харрисон П. Функциональное программирование : Пер. с англ. М.: Мир, 1993.-637 е., ил.

56. Хомский Н. Язык и мышление. Пер. с англ. М.: Изд. Моск. ун-та, 1972. - 122

57. Челышкова М.Б. Теория и практика конструирования педагогических тестов. Учебное пособие. М.: Исследовательский центр проблем качества подготовки специалистов, 2001. - 410 с.

58. Шаляпина З.М., Канович М.И., Штернова О.А. Организация лексико-синтаксических знаний в модели русского синтеза RUMORS. // «Компьютерная лингвистика и интеллектуальные технологии" Труды международного семинара Диалог'99. Москва, 1999, т.2 с. 326-334

59. Bieber M. Automating Hypermedia for Decision Support //Hypermedia.- 1993.-Vol.4, № 2.-P. 108-115.

60. Bloomfield L. 1964. Language. N.Y., Toronto : Holt, Runehart and Winston. — Русский перевод : Блумфилд Jl. Язык. M.: Прогресс, 1968.

61. Emelyanov G.M., Krechetova T.V., Kurashova E.P. Semantic Analysis in Computer-Aided Systems of Speech Understanding. //Pattern Recognition and Image Analysis. 1998.-Vol. 8, N3.-P.408-410

62. Emelyanov G.M., Krechetova T.V., Kurashova E.P. Tree Grammars in the Problems of Searching for Images by Their Verbal Descriptions //Pattern Recognition and Image Analysis.- 2000.-Vol.10, N4.-P.520-526

63. Emelyanov G.M., Mikhailov D.V., and Zaitseva E.I. Synonymic Transformations in Analysis of Semantic Pattern Equivalence at the Superphrase Unity Level //Pattern Recognition and Image Analysis.- 2003.-Vol. 13, No.l.-P.21-23

64. Emelyanov G.M., Smirnova E.I. Logical Model Of Hypertext Image Database // Pattern Recognition and Image Analysis. 1999. Vol.9, №3. P. 458-491

65. Emelyanov G.M., Smirnova E.I. Logical Simulation Algebra of Hypertext Image Database //Pattern Recognition and Image Analysis. -2000. -Vol.10, № 1. P. 156163

66. EmeIyanov G.M., Zaitseva E.I., Mikhailov D.V., and Kurashova E.P. Development of Recognition System of Analysis of Semantic Images of Natural Language Statements //Pattern Recognition and Image Analysis.- 2003.-Vol.13, No.2.-P.251-253

67. Meyrowitz N.K. Intermedia: The Architecture and Construction of an Object-Oriented Hypermedia System and Applications Framework /OOPSLA '86 Proceedings.- 1986.

68. Meyrowitz N.K., Haan B.J., Kahn P., RileyV.A., CoombsJ.H. IRIS: Hipermedia Services //Communication of the ACM.- 1992.- Vol.36, № 1.- P.36-51.