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

УДК 004 4'4+004 853

На правах рукописи

ХАПТАХАЕВА Наталья Баясхалановна

МОДЕЛЬ МП-ПРОЦЕССОРА, ВЫПОЛНЯЮЩЕГО ПРЕОБРАЗОВАНИЕ ЕСТЕСТВЕННО-ЯЗЫКОВОГО ПРЕДСТАВЛЕНИЯ ЯДРА ПРОДУКЦИИ В ФОРМУЛУ ЛОГИКИ ПРЕДИКАТОВ

Специальность 05.13.11- Математическое и программное

обеспечение вычислительных машин, комплексов и компьютерных сетей (технич. науки)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Красноярск - 2005

Работа выполнена в ГОУ ВПО «Восточно-Сибирский государственный технологический университет».

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

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

кандидат технических наук, доцент Найханова Лариса Владимировна

доктор физико-математических наук, профессор Журавлев Валентин Михайлович

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

доктор технических наук, профессор Доррер Георгий Алексеевич

Государственный научно-исследовательский институт информационных технологий и телекоммуникаций «Информика»

Защита диссертации состоится « 2 » февраля 2006 г. в 14 00 часов на заседании диссертационного совета Д 212.098.03 в Красноярском государственном техническом университете по адресу: 660074, г. Красноярск, ул. Киренского, 26, ауд. Г4-17, тел. (8-3912)-91-21-94, факс (8-3912)-43-06-92.

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

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

Автореферат разослан декабря 2005 ]

Ученый секретарь

диссертационного совета,

кандидат технических наук, профессор КГТУ

Вейсов Е.А.

fatëé А

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

Актуальность темы. Настоящее время характеризуется широким внедрением информационных и телекоммуникационных технологий во все сферы человеческой деятельности, что вызвано значительными успехами в области как теоретических, так и прикладных исследований в информатике. На современном этане наибольшее распространение получили системы обработки данных, построенные по технологии OLTP - OnLine Transaction Process. Вместе с тем, такие интеллектуальные информационные системы, как EIS - Executive Information System, DSS - Decision Support System, экспертные системы и другие подобные спосмы, широкою распространения не получили. Главной причиной такого относительно слабого промышленного внедрения систем, основанных на знаниях, по мнению аналитиков, является отсутствие проверенных источников знаний. Действительно, основным источником знаний является эксперт. Передача знаний выполняется в процессе длительных и пространных собеседований между инженером по знаниям и экспертом в определенной предметной области, способным досгагочно че1ко сформулировать имеющийся у него опыт. Из-за низкой скорости процесса передачи знаний многие исследователи рассматривают функцию приобретения знаний п качестве одного из главных «узких мест» технологии экспертных систем. В результате это вызвало большой интерес к методам автоматической обработки естественно-языковых научных текстов (ОЕЯТ), что обусловило необходимость создания библиотеки этих методов.

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

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

помощью ситуационного подхода.

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

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

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

Для достижения ука шиной цели в работе поставлены и решены следующие задачи:

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

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

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

Основная идея диссертации. Рассматриваемая работа строится на предположении, что предложение научного текста определяет ситуационный контекст, в котором находятся единицы предложения лексемы. Это позволяет отношения между единицами предложения, определяющие некоторую ситуацию, описывать посредством продукций. Компоненты ядра продукции А^>И представляются конъюнкцией фактов. Каждый факт есть высказывание о взаимосвязи понятий, входящих в ситуационный кон!екст. Взаимосвязь понятий определяется некоторым отношением, которое соотносится с глобальной классификацией отношений. Глобальная классификация разбивает отношения на категории, которые состоят из групп. Отношению в группе соответствует своя ментальная модель или структура, распознаваемая посредством диагностирующих конструкций. Таким образом, строится отображение «диагностирующая консфукция отношение)).

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

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

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

При определении диагностирующих конструкций использованы классификации концептуальных объектов и концептуальных отношений лингвисюв И. Дальберга, С.К. Никитиной, а также классификации отношений ведущих специалистов в области искусственного интеллекта Д.А. Поспелова, Г.С. Осииова и Д.Ш. Сулейманова. Структура продукции соответствует классической, приведенной в работах Д.А. Поспелова. За основу языка ситуационного моделирования взят язык ситуационного управления Д.А. Поспелова. Разработка граммашки базируется на методах теории формальных грамматик Н. Хомского, а, именно, на методах наиболее широкого подкласса контекстно-свободных грамматик - ЬК(£)-грамма1ик и грамматики свойств, описанных в работах Д. Кнута, А. Ахо, Д Ульмана, Б.К. Мартыненко, Ю.Г. Карпова. При построении модели МП-пронессора применены методы синтаксическою анализа для ЬЩ£)-грамматик, оптимизации анализаторов и методы реализации СУ-схемы над ЬЩ^У-грамматикой, представленные в работах Д. Кнута, А. Ахо, Д. Ульмана, Р.Сети, Ф.Л. Дс Ремера, А Дж. Кореньяка, ДжЛ. Хопкрофта, В Брауэра, Б.К Мартыненко и др.

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

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

2) модифицирована схема синтаксически управляемого перевода с входной Ь11(1)-грамматикой, которая дополнена элементами граммашки свойств, а именно таблицами свойств, что обеспечивает независимость модели МП-процессора от конкретной задачи.

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

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

Кроме того, материалы диссертации используются в учебной деятельности Восточно-Сибирского государственного технологического университета в рамках учебно-методического обеспечения дисциплин «Естественно-языковые системы» и «Теория языков программирования и методы трансляции», изучаемых студентами специальности 230105 «Программное обеспечение вычислительной техники и автоматизированных систем». В 2004 году работа была поддержана грантом Правительства Республики Бурятия для молодых ученых РБ.

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

Апробация результатов исследования. Основные положения диссертационной работы докладывались и обсуждались на второй Всероссийской научно-технической конференции «Искусственный интеллект в XXI веке» (Пенза, 2004), шестой Всероссийской научно-технической конференции «Теоретические и прикладные вопросы современных информационных технологий» (Улан-Удэ, 2005 г.), девятой Всероссийской конференции «Проблемы информатизации региона» (Красноярск, 2005 г.). Кроме этого основные результаты работы были опубликованы в журнале «Открытое и дистанционное образование» Ассоциации образовательных и научных учреждений «Сибирский Открытый Университет» (Томск, 2005).

Публикации. Основные результаты диссертационной работы опубликованы в 5 печатных работах общим объемом 1,8 пл., получено 1 свидетельство об официальной регистрации программы для ЭВМ.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и семи приложений. Работа содержит 200 страниц машинописного текста, в том числе основной текст - 143 страницы, 14 рисунков и 21 таблица Список литературы содержит 115 наименований. Объем приложений составляет 57 страниц.

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

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

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

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

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

Термин «приобретение знаний» в контексте данной работы применяется для обозначения процесса взаимодействия эксперта со специальной программой, целью которого являются: ввод интерактивным способом знаний эксперта о предметной области в соответствии с некоторой структурой; сохранение полученных таким образом знаний в некотором промежуточном виде; преобразование знания из промежуточного представления в вид, пригодный для практического использования в программе. При этом главным свойством систем приобретения знаний вне зависимости от их функционального назначения является обязательное наличие некоторой структуры знаний, заложенной разработчиком. Это требует структуризации приобретаемых знаний на предварительном этапе разработки системы. Поэтому одним из первых вопросов, возникающих при создании таких * систем, является вопрос, какие знания будут приобретаться системой.

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

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

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

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

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

Таким образом, система должна приобретать знания о методах решения задач обработки научных естественно-языковых текстов в виде продукционных правил на ограниченном естественном языке, записывать введенное правило в промежуточном виде на языке ситуационного моделирования и преобразовывать полученное представление на язык логики предикатов первого порядка для дальнейшего использования при автомагической обработке научного текста. Для представления продукций необходимо создать язык си туационного моделирования, основанный на языке ситуационного управления. Система приобретения знаний не должна зависеть от предметом области. Это означает, во-первых, что база знаний о методах должна бьпь о1крьпого типа, во-вторых, механизм, реализующий перевод продукций с ее)ееIпенно!о языка на язык логики предикатов, должен быть универсальным, то ес!ь непривязанным к определенной предметной области.

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

классов грамматик иерархии Хомского был выбран класс кошекстно-свободных грамматик (КС-грамматики). Это связано с тем, что, во-первыч. с помошыо КС-грамматики можно определить большую часть синтаксической структуры языка. Во-вторых, КС-грамматика является основой класса грамматик, для коюрых можно построить эффективные анализаторы: 1Х-грамматики, ЬЯ-грамматики и грамма мши предшествования. И, в третьих, КС-грамматика служит базисом различных схем задания переводов.

Анализ результатов теоретических и практических исследований в облаемн построения компиляторов показал, что основным классом грамматик, для которою строятся практические производственные компиляторы, на сегодняшний день являются ЬЯ(А)-грамматики, поскольку Ь1*(Л)-анализатор обладает высоким быстродействием и хорошей способностью к обнаружению ошибок.

Известно несколько возможных формализмов, используемых для определения переводов. Один из них - «схема синтаксически управляемого перевода», которая представляет собой грамматику, снабженную механизмом, обеспечивающим выход для каждой порождаемой цепочки. В другом методе основную роль играет преобразователь, то есть распознаватель с выходом, который на каждом такте может выдавать цепочку выходных символов ограниченной длины. В результате анализа методов перевода решено использовать схемы синтаксически управляемою перевода (СУ-схемы). Схема синтаксически управляемого перевода представляет собой грамматику с входной ЬЩI )-грамматикой, в которой каждому правилу присоединяется элемент перевода. Каждый раз, когда правило участвует в выводе входной цепочки, с помощью элемента перевода вычисляется часть выходной цепочки, соответствующая части входной цепочки, порожденной этим правилом. Для реализации СУ-перевода было решено использовать МП-процессор, который был введен А. Ахо и Дж. Ульманом и является расширением детерминированною автомата с магазинной памятью (МП-автомата).

Таким образом, в соответствии с вышеизложенным для построения грамматики, порождающей язык ситуационного моделирования, необходимо использовать методы конструирования Ы1(А)-грамматик. Для реализации перевода воспользуемся возможностями СУ-схем. Преобразователь, реализующий СУ-перевод, построим на основе МП-процессора.

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

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

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

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

Определение 1. Продукцией называется семерка вида рг - </; К\ О, С\А=ьВ\ Н\ Е>, где / - уникальное имя продукции; К - сфера применения или секция продукции; О - приоритетность выполнения продукции; С - условие применимости продукции; А=>В - ядро продукции; Н - постдействие; Е - связи с другими продукциями.

Основным элементом продукции является ядро продукции А=$В, которое в общем виде может быть представлено конъюнкцией фактов: А= А1лА2 л... лАт гдеА/, А2, ... А„~факты посылки; В■= В, а В2 л... л В„, , где В,, В2,... Вт - факты заключения. Фактом принято называть предложение, являющееся истинным высказыванием. В предложении объекты высказывания находятся в некотором семантическом отношении. Факты должны отражать логос и лексис объектов предложения, участвующих в описании ситуации. Обычное прочтение ядра продукции выглядит так: ЕСЛИ А, ТО В. В соответствии с этим структура правила на естественном языке будет иметь вид:

ЕСЛИ <посылка>, ТО <заключение>, где ЕСЛИ, ТО - ключевые слова, предназначенные для выделения посылки и заключения.

На язык описания ситуаций в работе введены ограничения. Нами определены правила задания объектов предложений - в виде термов и их обозначений, и введены разделители для выделения термов и семантических отношений. Согласно введенным ограничениям правило на ограниченном естественном языке имеет вид: ЕСЛИ

<терм> А/"семантическое отношение" <терм>А2 'И'... <терм> А,,.! "семантическое отношение" <терм> А„ ТО

<терм> А„ , "семантическое отношение" <терм> Л„./И'... <терм> А„ „,_/ "семантическое отношение" <терм> А„, „,.

Здесь "семантическое отношение" - некоторое отношение, в котором находятся объекты предложения.

Для решения задачи отображения представлений продукций с естественного языка в формальный язык логики предикатов были модифицированы продукционные правила на естественном языке, описывающие методы решения задач морфологического анализа (МА), разработаны продукционные правила для препроцессорной обработки научного текста (ППО) и для способа выделения терминов научного текста (ВТ). Исследование разработанных правил позволило выявить множество диагностирующих конструкций Д которые составляют их основу. В таблице 1 представлен фрагмент множества О, где ВОшиБппо^ш

Таблица 1 - Фрагмент множества диагностирующих конструкций МА, ППО и ВТ

А

ПшЛшо, D^n.Dnno

| Левая часть Семантическое Правая часть !

1 конструкции отношение конструкции ,

Ощ ! <лексема> / * I "эквивалентен" <лексема> 1 ' 1

} <основа> Base "является частью" <лексема> / !

] <лексеча> U "заменяется" <лексема> /? '

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

Таблица 2 - Фрагмент таблицы соответствия семантических отношений диагностирующих конструкций категориям предиката

Семантические Категория и тип Категория Предикат

отношения отношения предиката

"эквивалентна" Квантитативное Реляционный PRel_kvartt(a,x,y), где

отношение предикат а - "Analogy"

тождества х - первый объект

- - _ - - у - второй объект

"имеет Квалитативное Параметри- PPar (aj,y), где

характеристику" отношение ческий а - "Char" '

объект/свойство предикат х - объект

... ---- ---- у - свойство ____

Анализ диагностирующих конструкций позволил провести унификацию диагностирующих конструкций. Левая и правая части конструкций имеют следующие структуры: <терм> обозначение терма w <терм> [значение терма]. Обозначив через Term - терм, выражающий объект предложения, Val - значение терма и Sign - обозначение терма, было определено, что все факты, составляющие ситуацию, могут быть представлены в виде: Term Sign ('И' Term Sign)' Rs Term Sign или Term Sign ('И' Term Sign) Rs Term Val, где Rs - семантическое отношение, связывающее объекты предложения. Таким образом, построено унифицированное множество диагностирующих конструкций (таблица 3).

Таблица 3 - Фрагмент унифицированного множества конструкций

Левая часть конструкции Term Sign r Семантическое отношение "имеет характеристику" Правая часть конструкции Term Sign

Term Sign "эквивалентен" Term Sign

Term Sign "является частью" Term Sign

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

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

Для описания элементов языка- определен алфавит языка, на основе которого построены словари имен, действий и отношений. Словари имен и действий целиком определяются семантикой предметной области. Словарь же отношений носит более универсальный характер. Для определения цепочек языка была построена грамматика ситуационного моделирования G = <N, S, S, P>, позволяющая проверить корректность написания правил на языке ситуационного моделирования. В ней определены два непересекающихся множества символов - множество терминальных символов X и множество нетерминальных символов N. Множество Y. представляет алфавит языка и имеет вид: S = {Si, Z2, Xî, Х-ь }, где Z,-{«ЕСЛИ»,«ТО»} -множество ключевых слов; И', "ИЛИ"} - множество символов логических

операций; Si = {<буквы латиницы и кириллицы»}; Х4 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

= {(, ), <, >, [, 1, f", "], [', '], [-, '.', ','} - множество разделителей. Из терминальных символов образуются цепочки определяемого языка, для порождения которых используются нетерминальные символы, составляющие словарь имен языка. Множество нетерминальных символов имеет вид N={S, Л, В, Л,, В/, L, R, Rs, Term, Sign, Next Term, l'ai. Idem, NextArg,' Lei, Nums, Num}. Сердцевину грамматики составляет конечное множество правил Р, которые описывают процесс порождения цепочек языка. Каждое правило этого множества имеет вид А—>а, где Л нетерминал, а а - цепочка, состоящая как из нетерминалов, так и из терминалов. Фрагмент множества Р представлен ниже.

( 1 ) S-> «[Х'ЛИ»Л«Т()»В (20) Nexn'erm->'H"<'Term'>'SigiiNcxt Term

(2)А->Л,

(3) A->A,'H'A (34) Nums->NuinNums

(4) Л~»А|"ИЛИ"Л (35) Nuvns-VNum

(5) Л->Л'И"('Л|"ИЛИ"Л-)' (36) Nums

(6) A|->LRs (37) Num->0 . .. (46) Num->9

(7)A|->LRSR (47) Let-»A ... (163) Let->z

Таким образом, в данной главе описаны формализация методов решения задач MA. ППО и ВТ, а также язык и грамматика ситуационного моделирования G - <N, Г. S, Р> с множествами терминальных, нетерминальных символов и множеством правил вывода, позволяющая проверить корректность продукционных правил, представленных на ограниченном естественном языке.

Третья глава диссертации посвящена вопросам формализации перевода ядер продукционных правил с естественного языка на язык логики предикатов, построения модифицированной схемы синтаксически управляемого перевода (МСУ-схемы) и модифицированного синтаксически управляемого перевода, определяемого этой схемой, реализации МСУ-схемы над ЬЯ(1)-грамматикой и разработке модели МП-процессора.

С целью формализации проанализировано множество ядерных конструкций xR)\ являющихся базовыми для приобретения знаний в области естественно-12

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

конструкции term Sign

Term Sign

Семантическое отношение "эквивалентен"

Правая част ь KOHC1 рукции Term Sign

Предикат PRel_kvanl(" Analogy", Sign.Sign),

Term Sign | PPar ("Char", Sign, Sign)

имеет

1 характеристику"

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

Формула логики предикатов

Правило на ограниченном естественном языке

ЕСЛИ

<лексема> I, "тождественно равна" <константе> [';'] ТО

<лексема> I, "тождественно равна" <констате> ['.'] 'И'

первого порядка '

i

I'Rel jerch ("Value", /,,';') a j | I'Rel terch ("Value",';',';') i

.l=> ! 1 I'Reljerch ("Value", /,. ") л ! ! I'Rel terch ("Value",'.','.') л |

t I

<лекссма> l, "заменяйся" -'лсксемой> l2 l'Fun(Acl,fjipci(lh /_>)) !

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

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

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

Определение 1 Модифицированной схемой синтаксически управляемого перевода продукционных правил с ограниченного естественного языка на язык логики предикатов первого порядка (МСУ-схемой) Г назовем шестерку Г =( Л', I, Д, С, Я, S), где N - конечное множество нетерминальных символов; £ -конечный входной алфавит; Л - конечный выходной алфавит; Я — конечное множество правил вида Л-*а,р, где ае(Л'и£)", а /?е(Л'иД)*; 5 - начальный символ, выделенный нетерминал из N (аксиома); с - конечное множество свойств, задаваемое таблицами свойств.

> Для нахождения свойств входной цепочки а введена и определена команда РМО(а,Р), которая осуществляет по указателю р поиск выходной цепочки р, соответствующей а, в таблице свойств. Таблица свойств объединяет в себе таблицы расстановки и данных. Таблица расстановок имеет два поля: поле имени и поле указателя. В таблице данных находятся свойства цепочки а (выходные цепочки Р). В работе используются таблицы свойств семантических отношений, термов и наименований словарей базы фактов. Введем понятие перевода, определяемого МСУ-схемой.

Определение 3. Если Т={И, I," Д, С, Л, 5) - МСУ-схема, то 1(7) называется модифицированным синтаксически управляемым переводом (МСУ-переводом). Грамматика С;=(Л',£ ,5), где р={А->а \ А^>а,р принадлежит я}, называется входной грамматикой МСУ-схемы Т. Грамматика 00=(Л,,Д,С',/>',5), где Р'={А-> р I А -> а,р принадлежит Я}, называется выходной грамматикой схемы Т.

Входная грамматика О, определена во второй главе. В данной главе описываются элементы кортежа выходной грамматики. Множество С представляет собой множество свойств семантических отношений, словарей базы фактов и термов, а множество Д имеет вид Д={Д|, А2, Дз, Д4, Д5}, где Д1={'=>', 'л' V'}, Д2={<буквы латиницы и кирилпицы>}, Д3={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, Д4={'(', ')', "),","", "','-','.',','}, Д5={р| р - выходная цепочка, результат команды РПМЭ(а, Р)}.

Множество Р' разработано на основе множеств Р, С, д и содержит правила вида А-*а,р, где правила А р составляют множество правил Р' выходной грамматики С0. Когда правило участвует в выводе входной цепочки посредством входной грамматики Оь с помощью элемента перевода выходной грамматики С0 вычисляется часть выходной цепочки, соответствующая части входной цепочки, порожденной этим правилом. Фрагмент множества правил Л имеет вид:

(1) «ЕСЛИ»А«ТО»В, А'э'В (13) Ь-У<'Тегт'>'8^п, 5^п',Ттс1(Тегт,Р)

(2)А->А„А,

(3) А-»А|'И'А, А,'л'А

(4) А->А|"ИЛИ"А, АIV'А

(35) >)ит8-»Мит, Кит

(36) Мите -»А., X

(37)1Мит->0,0 ... (46)Мит-»9, 9 (47) Ье^А, А ... (163) ->г, г

(12) В|->1Ж5К. РЬЯ')' РПЧО(Я5, Р) 14

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

Для реализации МСУ-схемы и соответственно перевода, определяемого ею, исходная входная грамматика была расщеплена на 14 грамматик-компонентов. Для каждого грамматики-компонента Gx, Xah", построена система множеств LR(I)-ситуаций Q={fi, | Ц - множество ЫЦ1)-ситуаций, где / = 1,14}. В работе показана непротиворечивость построенных множества Ы1(1)-ситуаций, это доказывает, что разработанная входная грамматика является LR(1 (-грамматикой. Далее по множествам ситуаций для грамматик-компонентов построена объединенная система множеств LR( 1)-ситуаций J¡ для исходной грамматики G¡: J(,={[.v-» vV, а]} vj А;,, J2=A¡ua,2,UA',UA!;, J}=A'2vA,', J4=A¡, ..., J:ii=A"|9,

Jii2=Ah2o, ^2п=А96- По множествам ЬЯ(1)-ситуаций ,/, построено множество LR(1)-таблиц. Построение множества выполнено согласно модифицированному определению 4, учитывающему наличие во множествах LR( 1 )-ситуаций ситуаций вида [/l-»F¡nd, v].

Определение 4. Пусть G - КС-грамматика и Q - система множеств LR(¿)-ситуаций для G. Ш-таблгщей Т(А), соответствующей множеству ситуаций А из Q, назовем пару функций (f, g), где функция / - функция действия, ag - функция перехода. Функции/и g определяются следующим образом:

1. Функция / отображает множество I*k во множество {ошибка, перенос, допуск} и {свертка /| / - номер правила из Р, />1}, причем:

a)/(г/)=перенос, если v] содержится в А, /32*А и HeEFFk(/?2v),

b)flu)=F и перенос, если [.4—>Find, v] содержится в А,

c)_Ди)=сверткя /, если [А-*р-, г/] содержится в А и .1—►/} правило с номером i,

с!).ДХ)=допуск, если [5"->5-, А] содержится в А,

s)J(u)= ошибка, в остальных случаях.

2. Функция g используется сразу после переноса и свертки и определяет очередную применяемую таблицу. Значением g(.Y) является таблица, соответствующая множеству GOTO(//,.Y), если GOTO(.l,T) пусто, то g(X)= ошибка.

Следует отметить, что если G - 1Ж(1)-грамматика и О - каноническая система множеств LR(1 )-ситуаций для G, то между действиями, определяемыми по правилам (1а)-(1с), не возникает конфликтов.

Полученное множество содержит 213 LR( 1 )-таблиц. На рисунке 1 представлен фрагмент этого множества. В таблице символ S обозначает перенос символа в магазин, F- вызов команды Find, А - допуск, i - свертку, при которой применено i-e правило, Х-ошибку.

Для оптимизации канонического множества ЬЯ(1)-таблиц использован метод слияния таблиц с помощью совместимых разбиений на основе выявления ф-недостижимого множества LR( 1 )-таблиц. В процессе применения этого метода было построено ф-недостижимое множество LR( 1 )-таблиц. По данному множеству были выявлены совместимые блоки таблиц {Т2Ь Т27}, {Т6, Tt6}, {Тг», Т|6(} и {Т2|, Тщ}, которые были заменены соответственно таблицами U|, U2, U, и U

Действие Переход

ЕСЛИ е S S 5 « < . IA 1 1 1 z X | S А А, 1 NextArg 1 если] о f- S 1 или] ■ < > я

1 2 3 4 5 6 1 29 144 145 146 147 148 161 162 163 164 165 166 167 305

Го S X X X X X . .. X X X Т. X X X т2 X X X X X X

г, X X X X X X . .. X X А X X X X 1 X X X X X X X

h X X X X X S . .. X X X X Гэ •г4 X 1 X X X X Т6 X X

Г, X X X X F X . ■•21 X X X X X X X X X X X X X

1 213 X X X X X X .. X X 20 X X X X х X X X X X X

Рисунок 1 - Фрагмент множества ЬЯ(1)-таблиц

Для реализации МСУ-перевода построена модель преобразователя, основанного на МП-процессоре А. Ахо и Дж. Ульмана, выходом которого служит помеченный ориентированный граф, представляющий собой в общем случае дерево или часть дерева, построенного процессором. Основными функциональными компонентами МП-процессора являются Ы*(1)-анализатор, МП-преобразователь и таблицы свопов. ЬЯ(1)-анализатор*является основой МП-процессора и управляет операциями разбора входной цепочки: переноса, свертки, допуска. Для определения нужного действия используются ЬЯ(1)-таблицы. На практике для этого по таблицам были определены правила перехода для состояний переноса и свертки МП-процессора. Для построения правил перехода LR( 1 )-анализатора было определено отображение 5.

Опредепение 5. Отображение 5 множества /5x(IuNu/,u{$}) в Р, где Р -множество состояний автомата, (SuNu/' u{$}) - множество возможных входных символов, определяется следующим образом:

1) 5( Т, а)= GOTO(T, а) для всех аеХ, если Те Р- состояние переноса:

2) б( I, Т')= Т", если Т - состояние свертки, вызывающее свертку по правилу А-их и Т'е GOTO"'(T, а) и GOTO(T\ А)= Т".

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

Таким образом, на основе правил перехода LR( 1 )-анализатора и алгоритма реализации МСУ-схемы над ЬИ(1)-грамматикой предложена модель МП-процессора, выполняющего преобразование естественно-языкового представления ядра продукции в формулу логики предикатов. Фрагмент модели МП-процессора представлен на рисунке 2, где символ S обозначает перенос входного символа 16

грамматики в магазин, ^ - определение цепочки а и последующий ее перенос в магазин согласно шагу 1 алгоритма, А - допуск. Символы \a~iv, 2а, 2Ь и 3 относятся к действиям процессора, определяемым соответствующими шагами алгоритма.

'А $ 1 [равило перехода ЬК(1)-анализатора

Символ, jS

грамма-| пики

Таблица

t

в верхушке магазина

S А А|

То

гГ т7

Тз Т4

2 ' 3 I 4 5 1 6 | 7

1 ' I

S 1 , I !

,2а ' ! ,

i

!

S ' S I 2aj 2а]

I s; s

! 2а!2а

2а!

34 35136,37

и4

1 !

I F i

jlaivj

s; 2b!

i x, <u 1

!Z!

50 51

52 53

S( Г0,ЕСЛИ) =

7;

A 3

8(T|, X) = допуск

й ( Г2, <) = U2

Й(Т3, ГО) = Т7 6(Т3,И) = Т8 б(Т4,И) = Т, ft(T4, ИЛИ) = Tio 8 (Т4, Т2)= Гз 8(Т4,Т9)=Т„ 8 (Т4. Т|0)= Т|9

8 (IJ4, а) = и3

Рисунок 2 - Фрагмент МП-процессора

Правильность перевода МП-процессором входной цепочки доказана индукцией по порядку /, в котором образуются указатели.

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

Разработанная программная система "InTransSit" является программной реализацией прототипа предложенной модели МП-процессора. 11а вход системы подается на естественном языке описание метода решения задач обработки естественно-языкового научною текста в виде продукционного правила. Выходными данными системы являются формулы логики предикатов первого порядка. В результате вычислительных экспериментов, выполненных с помощью системы "InTransSit", был получен перевод продукционных правил морфологического анализа, препроцессорной обработки научного текста и процедуры выделения терминов в научном тексте. Проверка корректности формул логики предикатов, построенных системой, выполнена в среде логического программирования Visual Prolog, для чего было разработано специальное программное обеспечение.

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

В приложениях приведены фрагменты базы фактов, продукционных правил, вывод множеств ЬЯ(1)-ситуаций для грамматик-компонент, процесс построения объединенной системы множеств Ы1( 1 (-ситуаций для исходной грамматики, ф-недостижимое множество ЬГ<( I )-таблиц, вывод правил перехода и свертки для ЬШI )-анализатора. фрагменты текстов для апробации корректности построенных предикатов первого порядка.

заключение:

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

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

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

3. Предложен модифицированный синтаксически управляемый перевод (МСУ-перевод) с входной ЬК( 1 (-грамматикой, который определяется МСУ-схемой. При этом входная ЬЯ(1)-грамматика была расщеплена на 14 грамматик-компонентов, для которых построено семейство множеств ЬЯ(1)-ситуаций. Их объединение во множеаво ЬК( 1 )-снтуаций для исходной грамматики позволило построить оптимальное множество 1)-таблиц.

4. Предложена модель МП-процессора, основанная на модифицированном алгоритме реализации МСУ-схемы над Ы*(1)-грамматикой. Правильность стержневых теоретических положений модели доказана методом индукции.

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

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

Результаты диссертации отражены в следующих работах:

1. Хаптахаева Н.Б. Алгоритм лексического анализа полнотекстового документа // Сб. стат. И Всерос. науч.-техн. конф. «Искусственный интеллект в XXI веке». - Пенза, 2004. - С. 79-81.

2. Хаптахаева Н.Б. Модель подсистемы препроцессорной обработки текста // Матер. VI Всерос. науч.-техн. конф. «Теоретические и прикладные вопросы современных информационных технологий». - Улан-Удэ: Изд-во ВСГТУ, 2005. - С. 147-151.

/

3. Хаптахаева Н.Б, Модель преобразователя описаний естественно-языкового представления ситуаций в предикатное // Матер. VI Всерос. науч.-техн, конф.

j «Теоретические и прикладные вопросы современных информационных

технологий». - Улан-Удэ: Изд-во ВСГТУ, 2005. - С. 143-147.

4. Хаптахаева Н.Б. Унификация диагностирующих конструкций методов

Ч естественно-языковой обработки научного текста // Матер, девятой Всерос. науч.-

прак. конф. «Проблемы информатизации региона. ПИР-2005». - Красноярск: Изд-во КГТУ, 2005.-С. 175-180.

5. Найханова JI.B., Хаптахаева Н.Б. Формирование библиотеки методов анализа научных текстов в виде систем продукций // Открытое и дистанционное образование - Томск: Изд-во ИДО ТГУ. - 2005. - №4(20). - С. 13-24.

6. Свидетельство об официальной регистрации программы для ЭВМ № 2005612856. Программа «Интеллектуальная информационная система для приобретения знаний» / Найханова Л.В., Хаптахаева Н.Б., Хомосов С.С. - М.: Федеральная служба по интеллектуальной собственности, патентам и товарным знакам, 2005.

Соискатель

Н.Б. Хаптахаева

I

¿Хо

520

I

Подписано в печать 26.12.2005 г. Формат бумаги 60x84 1/16

Усл. печ. л. 1,19. Тираж 100 экз. Заказ № 289.

Издательство ВСГТУ 670013, г. Улан-Удэ, ул. Ключевская, 40в

Введение.

1 Описание проблемы и обзор существующих решений.

1.1 Обзор систем приобретения знаний.

1.2 Описание проблем по созданию систем приобретения знаний и предлагаемых подходов к их решению.

1.3 Анализ методов построения грамматик.

1.4 Выводы по главе и содержательное описание задачи.

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

2.1 Описание формального аппарата.

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

2.2.1 Формализация методов морфологического анализа.

2.2.1.1 Правила морфологического анализа.

2.2.1.2 Диагностирующие конструкции морфологического анализа.

2.2.2 Формализация методов решения задачи препроцессориой обработки научного текста.

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

2.2.2.2 Диагностирующие конструкции препроцессорной обработки.

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

2.2.3.1 Правила выделения терминов научного текста.

2.2.3.2 Диагностирующие конструкции выделения терминов научного текста.

2.2.4 Представление знаний лингвистических словарей в виде базы фактов.

2.3 Анализ систем продукций, представленных на естественном языке.

2.4 Язык и грамматика ситуационного моделирования

2.4.1 Язык ситуационного моделирования.

2.4.2 Грамматика ситуационного моделирования.

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

3 Модель МП-процессора.

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

3.1.1 Постановка задачи.

3.1.2 Схема синтаксически управляемого перевода и грамматика свойств.

3.1.3 Модифицированный синтаксически управляемый перевод.

3.2 Реализация МСУ-схемы над Ы1(1)-грамматакой.

3.2.1 Расщепление исходной грамматики.

3.2.2 Система множеств Ы1(1)-ситуаций для грамматик-компоиент.

3.2.3 Построение множеств Ы1(1)-таблиц.

3.2.3.1 Объединенная система множеств Ы1(1)-ситуаций для исходной грамматики

3.2.3.2 Множество 1Л1(1)-таблиц по множествам 1Л1(1)-ситуаций.

3.2.3.3 Оптимизация множества ЬЯ(1)-таблиц.

3.2.4 Модель МП-процессора.

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

4 Описание программного обеспечения и вычислительных экспериментов.

4.1 Описание системы преобразования ядер продукций.

4.2 Апробация корректности построенных предикатов первого порядка.

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

Актуальность. Настоящее время характеризуется широким внедрением информационных и телекоммуникационных технологий во все сферы человеческой деятельности. Это вызвано, в первую очередь, положительными результатами как теоретических, так и прикладных исследований в области информатики, связанных с обработкой, передачей и представлением информации. При этом дальнейшее развитие данной области возможно при интеллектуализации информационных процессов. На современном этапе наибольшее распространение получили системы обработки данных, построенные по технологии OLTP — OnLine Transaction Process. Вместе с тем, такие интеллектуальные информационные системы, как EIS - Executive Information System, DSS - Decision Support System, экспертные системы и другие подобные системы, широкого распространения не получили. Главной причиной такого относительно слабого промышленного внедрения систем, основанных на знаниях, по мнению аналитиков, является отсутствие проверенных источников знаний [22, 85, 89]. Действительно, основным источником знаний является эксперт, а процесс приобретения знаний, во-первых, является трудоемким и, во-вторых, его достаточно сложно организовать. Передача знаний выполняется в процессе длительных и пространных собеседований между инженером по знаниям и экспертом в определенной предметной области, способным достаточно четко сформулировать имеющийся у него опыт. Из-за низкой скорости процесса передачи знаний многие исследователи рассматривают функцию приобретения знаний в качестве одного из главных «узких мест» технологии экспертных систем [61, 99]. В связи с этим в последнее время все больше внимания уделяется проблемам автоматической обработки естественноязыковых научных текстов (ОЕЯТ). Этому способствуют и темпы развития всемирной сети Интернет, которые обеспечивают создание единой информационной инфраструктуры, содержащей гигантские объемы информации и огромное число общедоступных сервисов [2, 19, 32, 50, 67]. Одной из основных целей автоматической обработки естественно-языкового текста является построение модели предметной области. Для получения качественных баз знаний предметной области, которые являются результатом автоматической^ обработки естественно-языкового текста, они должны утверждаться экспертом. Однако для этого необходимо разработать специальные способы и средства, обеспечивающие автоматическую обработку текста.

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

Методы обработки естественно-языковых научных текстов должны быть описаны на естественном языке. В связи с этим необходимым является анализ предложений естественного языка. Современные работы в области лингвистики [3, 48] утверждают, что единицы текста (предложение, лексема, морфема и т.д.) создают некоторый ситуационный контекст, который должен отражать форму и содержание текста в случае, если единицей текста является предложение; предложение, если единицей текста является лексема; лексему, если единицей текста является морфема. Анализ таких языковых ситуаций в научном тексте составляет одну из основ современной лингвистики. По мнению А.А. Залевской [29] ситуационный подход заключается в акцентировании внимания на том, что для человека, как пользователя языком, значение слова реализуется через включение его в некоторую более объемную единицу - пропозицию, фрейм, схему, сцену, сценарий, событие, ментальную модель и т.п. При этом подчеркивается важность функционирования значения слова не в отдельности, а в определенных связях с другими словами.

Ситуационный подход связан с понятиями репрезентации и ментальных моделей. Ментальная модель может быть определена как некоторое знание в долговременной или кратковременной памяти, структура которого соответствует структуре репрезентируемой ситуации [29]. Чаще всего для описания ситуаций используют продукционные правила [33, 66]. При этом ментальные модели являются внутренними структурами, которые отражают взаимосвязь понятий. Таким образом, необходимо проанализировать отношения между понятиями, выполнить их классификацию, определить структуру каждой категории отношений.

Множество недостатков естественного языка, которые делают его не удобным для использования с целью четкого описания постановки задачи и, в первую очередь, его неоднозначность, обуславливают необходимость определения средств формализации естественного языка. Одним из таких средств является формализм исчисления предикатов первого порядка, с помощью которого «можно описать почти все, что относится к математике и очень многое из того, что выражено на естественном языке» [49]. Вышесказанное позволяет сделать вывод о том, что ядро продукции должно описываться как формула предикатов первого порядка и включать отношения между понятиями.

Таким образом, методы решения задач обработки естественно-языкового текста могут быть представлены в виде системы продукционных правил, описанных на естественном языке. Преобразование их в формальный вид должно осуществляться на основе методов теории формальных грамматик и автоматов [4,5, 83,40,34,37, 14,21,82, 104, 90].

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

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

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

Задачи исследований. Для достижения указанной цели в работе поставлены и решены следующие задачи:

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

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

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

Основная идея диссертации. Рассматриваемая работа строится на предположении, что предложение научного текста определяет ситуационный контекст, в котором находятся единицы предложения - лексемы. Ситуации принято представлять продукциями. С другой стороны, ситуация, как правило, представляется конъюнкцией фактов, описывающей причину, из которой вытекает некоторое следствие. При этом конъюнкцию фактов можно рассматривать как ядро продукции. Каждый факт есть высказывание о взаимосвязи понятий, входящих в ситуационный контекст. Взаимосвязь понятий определяется каким-либо отношением. Существуют глобальные классификации отношений. Каждая категория отношений делится на группы. Отношению в группе соответствует своя ментальная модель или структура. Эту структуру можно выявить посредством диагностирующих конструкций. Таким образом, строится биекция «отношение <-» диагностирующая конструкция». Поэтому необходимо рассмотреть отношения, релевантные предметной области задачи для каждого рассматриваемого метода. Унификация диагностирующих конструкций позволяет определить язык ситуационного моделирования методов обработки текста. Для описания языка строится грамматика, по которой создается схема синтаксически управляемого перевода (СУ-схема). Реализация СУ-схемы является основой для построения модели преобразователя.

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

При определении диагностирующих конструкций использованы классификации концептуальных объектов и концептуальных отношений лингвистов И. Дальберга, С.Е. Никитиной, а также ведущих специалистов в области искусственного интеллекта Д.А. Поспелова, Г.С. Осипова и Д.Ш. Сулеймапова. Структура продукции соответствует классической, приведенной в работах Д.А. Поспелова. За основу языка ситуационного моделирования взят язык ситуационного управления Д.А. Поспелова. Разработка грамматики базируется на методах теории формальных грамматик Н. Хомского, а, именно, на методах наиболее широкого подкласса контекстно-свободных грамматик - Ы1(&)-грамматик и грамматики свойств, описанных в работах Д. Кнута, А. Ахо, Д. Ульмана, Б.К. 7

Мартыненко, Ю.Г. Карпова. При построении модели МП-процессора применены методы синтаксического анализа для Ы1(&)-грамматик, оптимизации LR(&)-анализаторов и методы реализации СУ-схемы над Ы1(&)-грамматикой, представленные в работах Д. Кнута, А. Ахо, Д. Ульмана, Р.Сети, Ф.Л. Де Ремера, А.Дж. Кореньяка, Дж.Э. Хопкрофта, В. Брауэра, Б.К. Мартыненко и др.

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

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

2) модифицирована СУ-схема с входной Ы1(1)-грамматикой, которая дополнена элементами грамматики свойств, а именно таблицами свойств, что обеспечивает независимость модели МП-процессора от конкретной задачи.

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

Достоверность полученных результатов. Для реализации модели МП-процессора разработано программное обеспечение "InTransSit", с помощью которого проведены вычислительные эксперименты, позволившие подтвердить жизнеспособность предложенной в работе модели. Программное обеспечение зарегистрировано в отделе регистрации программ для ЭВМ Федеральной службы по интеллектуальной собственности, патентам и товарным знакам (свидетельство об официальной регистрации программы для ЭВМ №2005612856 от 3.11.2005). Корректность предикатов, сгенерированных программным обеспечением, была проверена в среде программирования Visual Prolog. Для доказательства достоверности грамматики и правильности выполнения перевода входной цепочки в соответствии с СУ-схемой в работе использован метод индукции.

Использование результатов диссертации. Ценность полученных результатов подтверждается их использованием в Бурятском региональном центре новых информационных технологий при разработке систем приобретения знаний. Одной из функций МП-процессора является контроль корректности представления ситуаций на естественном языке. Эта возможность используется в работе Тверского регионального ресурсного центра для распознавания правильности описания ситуаций в виде набора фактов, представляющих собой высказывание на естественном языке. Также результаты используются в виде библиотеки методов Южно-Российским региональным центром информатизации (ЮГИНФО) РГУ для описания задач области знаний или деятельности при создании онтологической спецификации структуры предметных областей научных исследований ЮГИНФО.

Кроме того, материалы диссертации используются в учебной деятельности Восточно-Сибирского государственного технологического университета в рамках учебно-методического обеспечения дисциплин «Естественно-языковые системы» и «Теория языков программирования и методы трансляции», изучаемых студентами специальности 230105 «Программное обеспечение вычислительной техники и автоматизированных систем». Результаты исследований методов естественноязыковой обработки научных текстов вошли в материалы итогового отчета о научно-исследовательской работе «Исследование и разработка методов и алгоритмов семантического анализа естественно-языкового текста», выполненной в 2004 году по гранту Правительства Республики Бурятия для молодых ученых РБ.

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

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

Апробация результатов диссертации. Результаты диссертационных исследований докладывались и обсуждались на второй Всероссийской научно-технической конференции «Искусственный интеллект в XXI веке» (Пенза, 2004), шестой Всероссийской научно-технической конференции «Теоретические и прикладные вопросы современных информационных технологий» (Улан-Удэ, 2005), девятой Всероссийской конференции «Проблемы информатизации региона»

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

Публикации. По теме работы опубликовано 5 печатных работ общим объемом более 1,8 п.л.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы и семи приложений. Работа содержит 200 страниц машинописного текста, в том числе основной текст - 143 страницы, 14 рисунков и 21 таблица. Список литературы содержит 115 наименований. Объем приложений составляет 57 страниц.

4.3 Выводы по главе

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

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

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

Заключение

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

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

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

3. Создан модифицированный синтаксически управляемый перевод (МСУ-перевода) с входной 1Л(1)-грамматикой, который определяется МСУ-схемой. Входная Ы1(1)-грамматика была разбита на 14 грамматик-компонентов, для которых построено семейство множеств 1Л(1)-ситуаций. Объединение множеств Ы1(1)-ситуаций грамматик-компонент в множество Ы1(1)-ситуаций для исходной грамматики позволило построить оптимальное множество ЬЯ(1)-таблиц на основе выявления ф-недостижимого множества Ы1(1)-таблиц.

4. Модифицирован алгоритм реализации МСУ-схемы над LR(1)-грамматикой, на основе которого предложена модель МП-процессора. Правильность основополагающих теоретических положений модели доказана методом индукции.

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

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

1. Адаменко А.Н., Кучуков A.M. Логическое программирование и Visual Prolog. -СПб.: БХВ-Петербург, 2003. 992 с.

2. Айман Мохамед Мофтах Кхамес Йоунес Бериша. Исследование и разработка методов извлечения знаний для создания интеллектуальных систем поддержки принятия решений: Дис. канд. техн. наук: 05.13.11. Москва, 2005.-218 с.

3. Арутюнова Н.Д. Предложение и его смысл. Логико-семантические проблемы. -М.: Наука, 1976.-380 с.

4. Ахо А., Сети Р., Ульман Дж. Компиляторы. Принципы, технологии, инструменты.- М.: Вильяме, 2001. 135 с.

5. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т.1,2. М.: Мир, 1978. - 234 с.

6. Ахо А.В., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы: Учебное пособие: Пер. с англ. М.: Вильяме, 2000. - С. 225-257.

7. Аюшеева Н.Н. Исследование и разработка моделей и методов поиска информационных образовательных ресурсов в электронной библиотеке: Дис. . канд. техн. наук: 05.13.11 Улан-Удэ, 2004. - 214 с.

8. Башмаков А.И., Старых В.А. Систематизация информационных ресурсов для сферы образования: классификация и метаданные. М.: Мир, 2003. - 212 с.

9. Белоногов Г.Г., Котов Р.Г. Автоматические информационно-поисковые системы. -М.: Сов. Радио, 1968 г.-415 с.

10. Поляков В. Н. Синтез формальных моделей языка и смысла как проблема семантической обработки естественного языка // Новости искусственного интеллекта. 1997. -№ 1. - С. 6-63.

11. Белоногов Г.Г., Кузнецов Б.А. Языковые средства автоматизированных информационных систем. М.: Наука, 1983. - 380 с.

12. Берестова В.И., Рыбина Г.В. Технология проектирования систем, основанных на знаниях, на базе инструментальных средств ИНТЕР-ЭКСПЕРТ и LEONARDO: Лабораторный практикум. М.: МИФИ, 1992. - 86 с.