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

На правах рукописи 0050484ОО Ли

¡.ыуссслио (

МИХАИЛОВ Дмитрий Владимирович

ТЕОРЕТИЧЕСКИЕ ОСНОВЫ, МЕТОДЫ И АЛГОРИТМЫ ФОРМИРОВАНИЯ ЗНАНИЙ О СИНОНИМИИ ДЛЯ ЗАДАЧ АНАЛИЗА И СЖАТИЯ ТЕКСТОВОЙ ИНФОРМАЦИИ

05.13.17 — Теоретические основы информатики

1 7 ЯНВ 2013

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

Великий Новгород — 2012

005048433

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

Научный консультант -

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

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

Немирко Анатолий Павлович, доктор технических наук, профессор, ФГБОУ ВПО "Санкт-Петербургский государственный электротехнический университет "ЛЭТИ" им. В. И. Ульянова (Ленина)", профессор кафедры биотехнических систем;

Минаков Игорь Александрович, доктор технических наук, Учреждение Российской академии наук Институт проблем управления сложными системами РАН, старший научный сотрудник лаборатории анализа и моделирования сложных систем;

Чернов Владимир Михайлович, доктор физико-математических наук, ФГБОУ ВПО "Самарский государственный аэрокосмический университет имени академика С.П.Королева (национальный исследовательский университет)", профессор кафедры геоинформатики и информационной безопасности.

Ведущая организация: Научно-исследовательский институт прикладной математики и кибернетики ФГБОУ ВПО "Нижегородский государственный университет им. Н.И. Лобачевского".

Защита состоится "1_5" февраля 2013 г.вШ часов на заседании диссертационного совета Д 212.215.07, созданного на базе ФГБОУ ВПО "Самарский государственный аэрокосмический университет имени академика С.П.Королева (национальный исследовательский университет)" (СГАУ), по адресу: 443086, Самара, Московское шоссе, 34.

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

Автореферат разослан

Ученый секретарь диссертационного совета

Белоконов И.В.

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

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

Тем не менее, серьёзных попыток смоделировать на ЭВМ формирование знаний о синонимии в естественном языке (ЕЯ) во взаимосвязи с процессом накопления знаний о языке в целом и об окружающем мире не предпринималось, несмотря на многочисленные публикации, посвященные:

- синтаксису, его связи с семантикой и лексическими средствами языка, реализующими механизм синонимического перефразирования - Мельчук И.Л., Жолковский А.К., Гладкий A.B., Апресян Ю.Д., Кибрик А.Е., Тестелец Я.Г., Солганик Г.Я., Тузов В.А. и др.;

- компьютерным словарям, тезаурусу и машинному фонду русского языка - Караулов Ю.Н., Нариньяни A.C., Рубашкин В.Ш., Попов Э.В., Леонтьева H.H., Демьян-ков В.З. и др.;

- системам тестирования знаний - Аванесов B.C., Красильникова В.А., Майоров А.Н., Челышкова М.Б., Останин К.С., Якимов В.Н. и др.;

- информационному поиску - Леонтьева H.H., Осипов Г.С., Попов Э.В., Рубашкин В.Ш., Фомичёв В .А., Соснин П.И., Тихомиров И.А., Журавлёв Ю.И., Гуревич И.Б., Кузнецов С.О., Райгородский A.M., Мучник И.Б. и др.

Современные поисковые системы, анализируя ЕЯ-запрос, используют статистику встречаемости слов запроса в различных контекстах с учетом возможных синонимов с целью поиска документа, максимально релевантного запросу. Аналогичный принцип используется и в статистическом переводе. Данный подход полностью оправдывает себя в задаче информационного поиска, но он не позволяет воссоздать целостный образ самой ситуации использования естественного языка для описания фрагмента действительности. Сказанное значимо, в частности, при подготовке ТЗОФ, когда известен фрагмент реальности и разработчику теста требуется выделить все возможные формы описания этого фрагмента в заданном естественном языке.

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

Г.М. Емельяновым, Т.В. Кречетовой и Е.П. Курашовой в 1998-2000 гг. была предпринята попытка решить эту задачу с привлечением уровня глубинного синтаксиса ЕЯ в рамках модели СЭ на основе грамматик деревьев (Д-грамматик). Указанный математический аппарат, предложенный A.B. Гладким и И.А.Мельчуком и расширенный разделением преобразований узлов и ветвей, позволяет формализовать синонимические преобразования ЕЯ-высказываний на уровне универсальной (абстрактной) лексики без существенного ограничения входного ЕЯ и ПО решаемых задач. Но и данному подходу присущи серьёзные недостатки, а именно:

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

- словарная подсистема предполагается закрытой ввиду существенной сложности описываемой словарём информации;

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

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

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

Предметом исследования являются методы и алгоритмы формирования знаний о синонимии.

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

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

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

- разработка и исследование методов анализа СЭ на уровне варьирования абстрактной лексикой;

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

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

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

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

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

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

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

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

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

• метод и алгоритмы автоматизированного формирования смыслового эталона на множестве СЭ-фраз в виде решётки формальных понятий, а также метод компрессии текстовой базы знаний на основе выделенных эталонов;

• метод численной оценки семантической схожести текстов предметно-ограниченного ЕЯ с учётом разделения языковых и предметных знаний;

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

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

1. Грант РФФИ № 03-01-00055-а "Разработка математического аппарата для распознавания сверхфразовых единств в текстах", рук. Емельянов Г. М., отв. исп. Михайлов Д.В.

2. Грант РФФИ № 06-01-00028-а "Разработка методов автоматизированного пополнения тезауруса для задач распознавания смысловой эквивалентности текстов", рук. Емельянов Г. М., отв. исп. Михайлов Д.В.

3. Грант РФФИ № 10-01-00146-а "Разработка методов автоматизированного накопления и систематизации знаний о морфологии и синтаксисе естественного языка для задач семантической кластеризации текстов", рук. Емельянов Г. М., отв. исп. Михайлов Д.В., гос. per. № 0120.1 164263, 2010-2012 г.

4. Грант № ТОО-3.3-408 Минобразования РФ, отв. исп. Михайлов Д.В.

5. Контракт № И 0675 ФЦП "Интеграция", отв. исп. Михайлов Д.В., гос. per. № 0120.0 300918.

6. ГБ НИР "Разработка и исследование математических моделей многопараметрических систем", рук. Емельянов Г.М., отв. исп. Михайлов Д.В., по заданию Минобр-науки РФ, гос. per. № 0120.0 704719, 2007-2011 г.

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

Личный вклад автора. В диссертационной работе обобщены результаты, полученные лично автором. Постановка и решение задачи распознавания сверхфразовых единств в текстах на уровне глубинного синтаксиса принадлежит автору. Решение задач формирования и кластеризации знаний на основе синтаксического контекста существительного предложено автором как обобщение результатов, полученных совместно с H.A. Степановой. Теоретические основы формирования знаний о языке на основе ситуаций его употребления развиты автором совместно с А.Н. Корнышовым. Метод оценки семантической схожести текстов предметно-ограниченного ЕЯ, а также метод и алгоритмы выделения смыслового эталона на множестве эквивалентных по смыслу ЕЯ-фраз, метод компрессии текстовой базы знаний и подход к интерпретации ответа испытуемого на тестовое задание открытой формы (включая архитектуру программной системы контроля знаний) разработаны лично автором. Эксперименты на ЭВМ подготовлены и выполнены автором в рамках выпускных квалификационных работ студентов специальностей "Прикладная математика и информатика" и "Программное обеспечение вычислительной техники и автоматизированных систем".

Апробация работы. Результаты работы представлялись на 35 конференциях, семинарах и конгрессах, в том числе проводимых РАН: 10-й, 12-й, 13-й, 14-й, 15-й Всероссийских конференциях "Математические методы распознавания образов",

2001, 2005, 2007, 2009, 2011; 6-й, 7-й, 8-й, 9-й, 10-й Международных конференциях "Распознавание образов и анализ изображений: новые информационные технологии",

2002, 2004, 2007, 2008, 2010; проводимых РАН совместно с Национальными академиями наук Украины и Беларуси 4-й, 5-й, 6-й, 7-й, 8-й Международных конференциях "Интеллектуализация обработки информации", 2002,2004,2006, 2008,2010.

Публикации. Всего по теме диссертации опубликовано 75 работ, среди них одна монография, 18 статей в журналах, входящих в перечень, рекомендованный ВАК для публикации основных результатов докторских диссертаций. Имеется свидетельство о регистрации программы для ЭВМ. В трудах международных конференций представлено 28 работ, в трудах всероссийских - 7 работ.

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

На защиту выносятся следующие основные положения:

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

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

3. Принцип формирования и кластеризации семантических отношений как основы классов СЭ.

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

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

6. Метод компрессии текстовой базы знаний с применением смысловых эталонов.

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

в естественном языке; создание и исследование информационной модели указанного явления; разработку принципов и методов извлечения знаний, а также средств автоматизации построения концептуальной модели предметной области на основе классов СЭ для текстов предметно-ограниченного ЕЯ, что полностью соответствует паспорту специальности 05.13.17 - "Теоретические основы информатики".

КРАТКОЕ СОД ЕРЖАНИЕ ДИССЕРТАЦИИ

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

Первая глава посвящена общей постановке задачи автоматизированного накопления знаний о синонимии как основы кластеризации предметных и языковых знаний. Вводится понятие ситуации языкового употребления (СЯУ), рассматриваемой в качестве единицы формализованного описания семантики ЕЯ:

5 = (0,Д,75), (1.1)

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

Л с о", где п е 1,...,|0|. Отношения из множества Я, как и формы из , могут быть произвольными. В качестве элементов Тя в работе рассматриваются совокупности символьных цепочек (содержательно - семантически эквивалентные ЕЯ-фразы), причём для е П- Э7>,-: Tsi = 6>п/(7>,), где Tri есть ориентированное помеченное дерево, а Зупг - сюръекгивная функция, определяемая правилами синтаксиса языка. Тогда 0 = Л/иК, где для \/о] е М найдётся ок е V такое, что понятию

Oj соответствует дочерний узел с пометкой м>], а понятию ок - родительский узел с пометкой н>к в 7г,-. Далее будем говорить, что слово, соответствующее символьной цепочке Wj, подчинено (синтаксически) слову, отождествляемому с ык. Сама задача СЭ формулируется следующим образом.

Задача 1.1. Дано множество ЕЯ-текстов в. Требуется: по результатам синтаксического разбора каждого gi е в выявить множества ) и М^^, а также тернарное отношение / сСхМхК: М = Ц-М^;), V = Ц-)■ Далее на основе I необходимо сформировать множество Д и выделить группы текстов по сходству встречаемости понятий в одних и тех же г,- ей.

Задача 1.1 наиболее естественно решается методами анализа формальных понятий (АФП). При этом для АсС и ВсМхУ вводится пара отображений: А' = {(т,\):теМ,уеГ \ ^ е = В'= У е (т,у)е В :т^) = у]. Па-

pa (А,В), где A' = В и В' ~ А, есть формальное понятие (ФП) с объемом А и содержанием В. Классам СЭ здесь будут соответствовать классы формальных понятий в решётке, а задача накопления знаний о синонимии сводится к совокупности подзадач, решаемых далее в главах:

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

- кластеризация отношений из множества R в составе тройки (1.1);

- численная оценка схожести СЯУ.

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

Для теоретического обоснования алгоритмической разрешимости построения последних вводится динамическая информационная модель (в терминологии работ Г.М. Емельянова и Е.И. Смирновой) совокупности правил Д-грамматики на основе аппарата ограниченных сетей Петри. Рассматриваемые Д-грамматики задаются четвёрками Г = (fVR,VR,tp,ll), где VR - конечное множество пометок на ветвях дерева: VR ={а1,а2.-->а*Ь WR ~ конечное множество пометок на узлах; <р - матрица ограничений на характер размещения на ветвях дерева пометок из VR: для V/ = l.....к из

любого узла дерева выходит не более )=и, ветвей с пометкой а,-; П - конечное множество правил преобразований деревьев, причём для V ruleеП задаётся множество Rap условий его применимости. Содержательно Vra/?/ е Rap выступает в роли прецедента, с которым отождествляется класс СЭ на уровне абстрактной лексики.

Определение 2.1. Лексической синонимической конструкцией (ЛСК) будем далее называть комплекс лексических единиц wrk е WR и связей vrj е VR между ними, замена которого описывается некоторым rule, еП. Каждой ЛСК соответствует свое ключевое слово Cq , при этом в общем случае произвольная wr^ в составе ЛСК есть значение некоторой лексической функции от Сq .

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

слова ЛСК и представлением результата в виде списка пар:

{(r«fey,C0(/)): j = 1,...,|п|}. (2.1)

В работе некоторого rulej еП в общем случае следует выделить два состояния: соответствующее заменяемому дереву Tiol и соответствующее заменяющему дереву Tic>2, где Tiok = {tViofc, Vio^}, Wio/, — множество узлов, Vio^ - множество ветвей. Условие rapi е Rap представляет собой формальное описание допустимости перехода из состояния 77о[ в Tio2. Правило rulej может быть применено к дереву Tio\, если

vft rapi = true, где т = \Rap\. Обозначим v™ j rapj далее как г12. При этом г12 следует интерпретировать как "определение события, разрешающего переход от Тщ к Г/о2". Применение правила rulej е П сводится к выполнению перехода:

rulej(r12): Tio\ > Tio2 . (2.7)

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

N = {P,T,F,H,M0}. (2.8)

При этом множество состояний правила есть множество позиций сети Р-\р\,р2}> где pi о Tio\, а р2 о Тю2 ■ Множество возможных переходов Т представлено единственным переходом из Гю1 в Tio2: t = ruleJ(rn):pl—!-+p2. Компоненты F и II есть отображения F : х Г -» {0,l} и Я : Г х Р {0,l}, соответственно. Для сети вида (2.8) F(pi,i)=l. F(p2,t) = Q, H(t,pi) = 0, H(t,p2)= 1, а число допустимых маркировок (разметок) сети равно двум. Начальной маркировке соответствует вектор Mq = (l,0), второй из допустимых маркировок - вектор М = (0,l).

Множество правил rulej е П, представленных сетями (2.8), есть множество объ-

екгов-примитивов для построения информационной модели системы правил некоторого подмножества П с определением структурных взаимосвязей между примитивами. При этом сама система формируется следующим образом: для каждой пары \ule\,rule2\c: П, rulei Ф rule2, в системе либо вход у rule2 является выходом для

гиЩ, либо наоборот, вход у ridex есть выход для rule2.

Пусть Ni = {PhThFhHhM0i} -сеть, построенная из примитивов (2.8). Теорема 2.1. Сеть Л7,- является безопасной в течение всего времени функционирования моделируемой системы правил.

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

т = (hi'hi'-'-^ki) срабатываний переходов:

Тщ ru!e^] ) Tio2 Ыег{г2з) >77o3 Tiok rV,ek(ri'MUTiok+,, (2.9)

где tu о rulex(rn), t2i о rule2(r23), ... , tki о rulek[rktЛ+1). При этом происходит последовательная смена разметок:

M0i ~^>M2i ->...-> Mk_h i (2.10)

где M0/ о Tioj, My « Tio2,..., Mk_Xi <=> Tiok, MH <=> Tiok+l.

Множество разметок, достижимых из начальной разметки М0; и образующих множество достижимости сети Nj, находится в зависимости от задания Mq,- . Функционирование системы описывается в терминах последовательностей срабатываний переходов t\i,t2i.....tk-\,i->hi> каждая из которых есть слово т в языке L{Nj), называемом

свободным языком сети Nj.

Задача приведения деревьев Тщ и Tiok+l к виду с одинаковой JICK фактически

включает в себя три задачи:

1) определение достижимости разметки Mki из начальной разметки M0i.

Данная задача есть поиск слова г е T*\MQi —X—+Mki, где 7} - множество всех слов в алфавите 7};

2) задача обратимости слова г: если т s Т* \М01 —Mki, то существует

ли слово - (fjtf .4-1, i > • • • > {2i' hi):

М0. +Jii—Mu М2; ... <- Mk_Vl (2.11) где M0i о Тщ, Ми » Tio2, ... , Mki<z> Tiok+l;

3) задача определения оптимального слова т е Т*\МЫ —Суть: если

существуют ц,т2,...,тГ. M0i-^Mkh .... M0i то в ка-

честве оптимального берется слово наименьшей длины, причём предпочтение всегда

отдаётся обратимому слову.

Для решения указанных задач проводится исследование языка Цл,-).

Лемма 2.2. Проблема достижимости заданной разметки Мы из начальной Мы в сети N, разрешима.

*

Обозначим множество всех слов в алфавите 7} как 7} .

Теорема 2.3. Проблема определения обратимости слова геГг|Л/0/ >МИ

языка L{Ni) разрешима.

Теорема 2.4. Проблема поиска оптимального слова re7} |в языке ) является разрешимой.

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

В третьей главе решается задача формирования и классификации отношений из множества R в составе тройки (1.1). Базовым здесь является прецедент класса СЭ, представляемый условием гу в (2.7) и (2.9). За основу его формализации берётся введённое Б.Х. Парта и В.Б. Борщевым описание семантики символьной цепочки, соответствующей ЕЯ-слову и обозначающей некоторое о, е О, совокупностью Х-выражешш, каждое из которых описывает некоторое свойство понятия о,-. Назовём далее указанную совокупность теорией лексического значения (ЛЗ) слова. Сама теория ЛЗ слова щ, заменяемого некоторым rule j е П , определяется рекурсивно посредством упорядоченной совокупности троек и пар (3.2М3.4), связывающих обозначаемое словом щ понятие о,- е О с другими понятиями множества О через отношения из множества R :

Lm{wi) = {whLM), (3-1)

при этом отдельный элемент Мр списка LM может представлять либо бинарное отношение между парой понятий {oj ,о2} с О :

Мр = {г2,оу,о2), (3-2)

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

Mp = {rn,o,LMr), (3-3)

и

Mp = {rc,LMr), (3.4)

где rc е {v,&,—>}; LM г определяется по аналогии с LM ; г2 и г„ - символы (либо символьные цепочки), обозначающие соответствующие отношения.

Для автоматизации получения знаний, представляемых формулами вида (3.1)-(3.4), в разделе 3.5 решается задача формирования множества R на основе множеств СЭ-фраз предметно-ограниченного ЕЯ. При этом отношения в рамках троек и пар (3.2)-(3.4) будут составлять подмножество множества R .

Рассмотрим 7s,- е 7s с точки зрения составляющих её символов. У каждой 7s,-выделяется неизменная часть 7с,-, общая для всех 7s,- е 7s, и флективная часть Tfh На множестве 27/ выражаются синтагматические зависимости, которые задаются синтаксическими отношениями и определяют возможность сосуществования словоформ в линейном ряду. Аналогично для слова Wy имеем Wy = Wcy »Wfy, где Wy - последовательность его символов, Wcy с 7с,- составляют символы неизменной части, именуемой далее основой, Wfi} с Tft - символы флективной части (флексии), а символом "•" обозначается конкатенация символьных последовательностей. Для формирования множества R попарным сравнением Wy различных 7s,- требуется найти:

1) Wcy и Wfy каждого Wy при \Wcij\ ->max;

2) отношение Rq, определяющее допустимость сочетания {{Vfу,Wf^), к*- j.

Введём индексное множество J для неизменных частей всех слов, употребленных во всех 7s,- е Ts . Тогда упорядоченная совокупность индексов j e J неизменных частей слов, присутствующих в 7s,- е Ts, будет моделью линейной структуры этой фразы (далее обозначается как Z,s(7s,-)). Для построения множества R необходимо найти совокупность указанных моделей, отвечающих требованиям проективности.

Пусть h(j,Ls(Tsi )) - позиция индекса j в модели Ls(Tst). Тогда множество связей для Ls(Tsj ) определяется как D : 7s,- -> {( h (j, Ls{Tsj )), h (к, Is(7s,- )) ) : j # к }.

Определение 3.3. Связь dqi =(h(j,Ls{Tsi)\ h(k,Ls(Tsj))) является допустимой для Ls(Tsj ), если Э { Ts/, Tsm } с:Ts, 1ф m, причем и Z,s(7ï/ ), и Ls(Tsm ) содержат в качестве подпоследовательности либо {j,k}, либо {&,_/'}. При этом пара (j, к) содержательно соответствует одной синтагме.

Положим, что для VTsj е Ts, i = l,...,|7s|, все dqi е D(Tsj) удовлетворяют определению 3.3.

Определение 3.4. Будем считать модель Ls(7s,-) проективной относительно множества R в (1.1), если

X Aqi <|ls(rs,-)|, где Aqi =|^,Is(rs,-))-A(*,Is(7ï,-))|.

<?=1

На основе [JjDfoi) формируется граф синтагм (Vj,Ij). Элементами множества вершин Vj являются множества пар (j,k), {/. к) с J, сгруппированных по некоторому индексу к. Множества Е\ и Е2, входящие в Vj, будут соединены ребром из

Ij, если 3{j,k,m} a J: (j,k)eEly (k,m)eE2 и j*m. Анализом (Vj,Ij) строится дерево синтаксических связей (Vjp , Ijp ). Формально

vjt = J. 1 л -

При этом к б Vjt соответствует корню дерева (3.11), если ЗЕ\ е Vj, в котором пары индексов сгруппированы по к, > 1, а к не содержится ни в одной паре индексов для V£2 £ Vj: Е\ Ф Е2.

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

Рассмотрим построение дерева (3.11) для случая расщепленного предикатного значения (РПЗ) как совокупности вспомогательного предикатного слова-связки и слова, называющего ситуацию. Пусть 7сис,- = {wy : wy где символом "• " обозначается

конкатенация, последовательно выполняемая над символами из Wfy. Положим, что 3Tpi с 7'si определяющая последовательность Репе, = {ик :ик = »{Wpk),\JkWpk =TPi)> где Wpk е Tsi - последовательность символов слова, для которого не выделены неизменная и флективная часть.

Теорема 3.1. Последовательность Pcncj содержит предикатное слово, если

3{/,0,с Ls(Tsj): {wi/-,ui,...,up,wik\c Тспс,, где Ц.....ир\= Pcnct, р = \Рспс-\.

Доказательство следует из определения корня дерева (YjtJjt) и проективности Ls(Tsi). Пусть для Pcnci выполняется условие теоремы 3.1.

Теорема 3.2. Слово ик е Pcnci принадлежит расщеплённому предикатному значению, если 3Tsj g Ts : Lsftsj)* Ls(Tsj), a uk e Pcncj, причём Pcncj также отвечает условию теоремы 3.1. При этом -i3Tsk е Ts, где Рспск с Pcnci и отвечает теореме 3.1, a Ls(Tsk)* Ls[Tsj) и Ls{Tsk)* Ls{Ts;).

Доказательство следует из доказанной теоремы 3.1 и определения множества ребер в графе (Vj,Ij).

Замечание. При выполнении условия теоремы 3.2 ик может быть в том числе и зависимым словом в составе РПЗ.

Пусть Рспс\ - последовательность слов, удовлетворяющих теореме 3.2, а

Ts'с Ts, при этом Ts' = {Ts,-:\Рспс\\max}.

Для Уик е (J ¡Pcnc'i, Tsi е Ts', его неизменная и флективная часть выделяются сравнением последовательности Wpk его символов с аналогичными последовательностями Wpj для всех uj б U¡Pcnci : Ts; е (7s \ 7s'), а Рспс1 отвечает условию

теоремы 3.1. При этом необходимо, чтобы 2\wck\>\wfk\ + \wfj\, где Wpk = Wck *Wfk, a Wpj = Wck • Wfj.

Замечание. Если Pcnc'i n Pcnct Ф 0, то V um e [Pcncj \ Pcnc\) представляется вместе со словом слева от него в Репе, (в этом случае ит рассматривается как предлог).

С учетом Pene¡ дерево (3.11) преобразуется следующим образом:

1) корень изменяется с к = 0 на значение к для ик ePcnc'¡ с максимальной встречаемостью в разных Тспсi относительно заданной СЯУ;

2) левое поддерево остается без изменений;

3) правое поддерево перевешивается на узел j для uj е Рспс\ наименьшей встречаемости;

4) в паре {u¡,um} с Репе] дочерний узел у слова с меньшей встречаемостью. Далее назовём дерево (3.11), преобразованное согласно указанным правилам,

расширенным деревом (3.11). Заметим, что расширенное дерево (3.11) является деревом-прецедентом для множества деревьев {7V; : Ts¡ = Synt(Tr¡)} из определения компонента Ts в составе тройки (1.1).

Таким образом, в третьей главе разработан принцип формирования и кластеризации семантических отношений выделением синтагматических зависимостей. Его программная реализация, представленная в приложении 1 диссертации фрагментами исходного текста на языке Visual Prolog 5.2, позволяет выделять произвольные отношения в рамках СЯУ за время, оцениваемое сверху как квадрат произведения числа СЭ-фраз и максимального числа слов во фразе.

Четвертая глава посвящена задаче минимизации оптимального слова в языке сети Петри, построенной из примитивов вида (2.8). Основу решения составляет выделение ситуаций синонимических замен на уровне абстрактной лексики (синонимов, конверсивов и расщеплённых предикатных значений) в последовательностях синтаксически соподчинённых слов:

Squ = fri.....(4Л)

где vj - предикатное слово; ты hVv; е \?2>---vn(k,i)} -существительные.

Утверждение 4.2. При true возможно установление указанного отно-

шения между Vi и Vvj б \y3,...,v„(k,i),mk¡}.

Замечание. На основании утверждения 4.2 справедливо будет утверждать, что Vv/ e{v2"">vn(í,/)} в составе последовательности (4.1) обозначает некоторое понятие, значимое в ситуации v¡, наравне с mk¡. Таким образом, если в задаче 1.1 в качестве множества G рассматривать множество Ts в составе тройки (1.1), то для любой Sqk¡

b.-.v^.Wfa-jcM^), a V(Tst) = (Jífe \ К})-

В главе рассматривается концептуальная кластеризация текстов методами АФП на основе последовательностей (4.1). Описываются алгоритмы формирования множеств M(Ts¡), V(Ts¡) и отношения I на основе синтаксического разбора исходных g¡ е G согласно постановке задачи 1.1, а также порядок замены конверсивов и расщепленных предикатных значений.

Обозначим функцию, которая ставит в соответствие каждому v б V(Ts¡) предлог для связи с зависимым словом, как prep: у -> ру; функцию, ставящую в соответствие именному т е M{Ts¡) символьное обозначение его падежа - как case су . Соответст-

вие между словом и его начальной формой зададим функцией norm. Пусть {is;,Ts2} -пара анализируемых ЕЯ-фраз. Положим, для Ts\ выделено множество последовательностей вида (4.1), обозначаемое как SQi = и : Sq к\ с: Ts ;}, к = \.....n{SQ j), аналогично для Ts2 имеем SQ2 = {Sqk2 s1k2 cTs2}, но при этом либо к = 1,...,h(s6i),

либо к = l,...,n{SQi)-l, где «(sGi)= 1-

Утверждение 4.4. Применительно к паре {SQl,SQ2\ имеет место конверсив, если для V SqkJ е SQ i найдется Sqj2 s SQ2 такая, что при этом могут иметь место следующие случаи взаимного соответствия Sqk\ и Sqj2.

1) = {vll >vk2>vk2>->vk,idx(k,\)>mkl\> s1 ]2 = {v21 >VA3.-- 'vM&(/t,l)'mAl }•

При этом norm{yn )= norm\v2\ ), norm(vk2) = norm(vk2 ], причем в общем случае

prep{v\ ] jit prep(v2i ), a case(vk2)* case{vk2 j. Функция idx(k,i) возвращает максимальное значение второго индекса при v.

2) Sqkx =jv>n ,v12 ,vk2,vk2,...,vkJdx(k^ymk^\, SqJ2 = [>2i >vk2 ,vKidx^ymkx).

Здесь norm(vfc2)= norm{vk2 j, case(yk2)Ф case{vk2 ) (в общем случае), но при этом

для Sqj2 BSqki е SQ l'■ j5*?« > Sqj2 j соответствует случаю 1, Sqkl *Sqkl, а для

Sqk\ 3Sqj2 gSQ2: ^¡qki,Sqj2 } также удовлетворяет требованию случая 1 на/

стоящего утверждения и Sq & J2 ■

Таким образом, в четвёртой главе принцип формирования и экспериментальной оценки знаний в виде классов СЭ согласно постановке задачи 1.1 развит применительно к наличию конверсивов и РПЗ в анализируемых текстах. Критерием выбора возможного варианта замены конверсива либо РПЗ здесь является минимум многозначности при максимальном числе беспредложных смысловых валентностей слова, на которое производится замена. При этом степень многозначности определяется числом СЯУ, в которых фигурирует слово.

Пятая глава посвящена совместному использованию свойств расширенного дерева (3.11) и последовательности вида (4.1) для оценки семантической схожести текстов относительно СЯУ, порождаемых независимо друг от друга.

В разделе 5.1 индексное множество J, рассмотренное в разделе 3.5, определяется для неизменных частей всех слов, употребленных в более чем одной фразе из множества Ts в (1.1), с учетом возможного присутствия слова не во всех фразах указанного множества. При этом удвоенная длина общей неизменной части пары слов всегда больше суммы длин флективных частей.

Пусть LS есть множество моделей линейных структур фраз из Ts на J.

Теорема 5.1. Пара индексов {/i,j2jc:,/ соответствует словам-синонимам, если 3{li(ri!),Ls(Ts2)}е LS :Ii(ri1)=J1 •{]{}• J2 и Ls(Ts2)=Ji •{j2}'J2,rp.c Jx <zJ, J2czJ, a " • " есть операция типа конкатенации над множеством J.

Пусть РЗ - множество пар, отвечающих теореме 5.1. Заменим индексы, вошедшие в пары из РЗ, на некоторые у" е (NN7) во всех моделях из ЬБ . Обозначим преобразованное ¿5 как 15', множество заменяемых индексов - как ЛР, а множество индексов, на которые идёт замена, - как ЗР', ЗР'г\ЗР = 0. Фактически каждая модель в 1*3' задается на множестве (3\ЗР)*иЗР'.

Пусть Ш есть множество индексов с максимальной встречаемостью в разных моделях из £5', /л ,(Г.5,)е £5', а ) - модель линейной структуры Гл,- относи-

тельно М. Обозначим множество моделей второго вида как ЬМ. Положим также, что имеется ЬБ) с 15' такое, что для всех ¿^(/з^е 15) модели ('Л,-) одинаковы

и соответствуют некоторой £$2 (Т^у)е ЫЫ, Tsj е 7!у .

Обозначим множество индексов /«Ж с максимальной встречаемостью в различных и I (Ts¡) е 15), как ЗА . Местоположение индекса в расширенном дереве (3.11) и флективные части для слов с индексами из ((./ \ ЗР) и ЗР')\(Ми ЗА)и {о} определяются аналогично словам из Рспс\ описанным в разделе 3.5 способом. При этом вместо индексов с ненулевым значением рассматриваются у е (Ж и ЗА).

Для численной оценки схожести СЯУ, каждая из которых описывается тройкой (1.1), в разделе 5.2 вводится представление СЯУ в виде совокупности трёх составляющих, называемой в теории АФП формальным контекстом (ФК):

К* = (5.1)

N

' N >

№к е иTsi.Tr, \3Tsi = 5уш(Т>,) /=1

, при

где Ся включает основы слов Wj е \JTsj : 3

/=1 ^

этом м>] соответствует дочернему, а \»к - родительскому узлу в 7г,- { у/к есть синтаксически главное для , Wj - синтаксически зависимое по отношению к и^ в дереве 7>.V и,- б есть символьная цепочка, понимаемая как некоторый признак некоторого gi е , сами признаки могут быть следующих видов, составляющих непересекающиеся подмножества множества Мя и обозначаемых далее посредством соответствующего нижнего индекса:

- указания на основу синтаксически главного слова (индекс 1);

- указания на флексию главного слова (индекс 2);

- связи "основа - флексия" для синтаксически главного слова (индекс 3);

- сочетания флексий зависимого и главного слова (индекс 4). После флексии главного слова через двоеточие при необходимости указывается предлог для связи главного слова с зависимым;

- указания на флексию зависимого слова (индекс 5).

Посредством йсОяхМ? отношения из множества Я в (1.1) разбиваются на классы по сходству основы главного, флексии зависимого слова, а также характеру сочетаний основ и флексий. Для численной оценки схожести СЯУ выполняется редукция ФК (5.1) исключением объектов и признаков РПЗ согласно правилу, очевидным образом вытекающему из теоремы 5.1 я утверждения 4.4.

Пусть {тх,т2,т3}с А/|. Если т^, т2 и т3 взаимно различны, то соответствует указанию на основу главного, т2 - зависимого слова РПЗ, а Щ - на основу однословного эквивалента РПЗ при выполнении трех условий:

1. 3g, eGi :Is(gl,m1)=true, Is{gx,m3)= false, m2=pbs»gl. Здесь pbs есть обозначение символьной константы "главное - основа:".

2- 3{g2,g3}с: Gs, при этом объекты g\, g2 и gj взаимно различаются, а

h(g2,m3)/\Is(g3,m3)/\

л {ls(g2,от,)д Is(g3,т2)v Is{g2,т2)л Is(g3,т1)) = true.

3. Не существует других троек объектов, для которых признак занимал бы место либо т либо т2 в вышеуказанных соотношениях.

Помимо редукции формальных контекстов (5.1) отдельных СЯУ, для численной оценки их схожести, представленной далее в разделе 5.5, вводится представление тезауруса ПО в виде формального контекста:

Kth = (Glh, Mth, Л/г), (5.2)

где множество Gth состоит из символьных пометок отдельных СЯУ. Множество Mth включает элементы множеств признаков формальных контекстов вида (5.1) всех gth с Gth . Кроме того, в составе Mth выделяются:

- множество указаний на объекты формальных контекстов вида (5.1), генерируемых для элементов Gth (обозначим далее это множество как М6 );

- множество связей "основа - флексия" для зависимого слова ( М-j);

- множество сочетаний основ зависимого и главного слова (Мg).

Пусть СЯУ Sj описывается тройкой вида (1.1) и соответствует заведомо корректному ЕЯ-описанию некоторого факта заданной ПО. Положим также, что S2 -анализируемая СЯУ. Обозначим ФК вида (5.1): для S\ - как Ке, а для S2 - как Кх, где Ke-{Ge,Me,Ie) и Kx = {Gx,Mx,Ix), Ie с Gex Me и Ix с Gxx Мх, соответственно. Введем обозначения для констант: Pj7 - для "флексия:", рь - для "основа:". Результат объединения М6, Mj, Ms, Me 4, Мх4, Ме5 и Мх5, обозначим как Мц.

Определение 5.1. Будем считать, что 5] и S2 связаны отношением схожести, если каждому объекту gx е Gx соответствует такой объект ge е Ge, что выполняется одно из следующих условий:

(1) gx = ge и любой признак те е Me объекта ge относится и к gx.

(2) gx = ge, при этом условие (1) не выполняется, но существует gth е Gth, обладающий признаком mth j е М6 : mthx = рь» ge при обязательном выполнении

следующих условий:

(Э mefl € Me5 :те^ = pfl • /е)-> (Э mthxl е М1 : mthn =ge* ":" • fe), при этом (le(ge, Ix{ge, mejj))-* Ith{gth, mth и);

(3 mebs s Mex : mebs = pbs • Ье)-> (3 mthn e Ms : mthn = ge» ":" • be), при этом Ie{ge, me bs)—> Ith{ gth ,mth\%)-,

(З mxbs е Мх\ : mxbs = phs • bx) -» (Э mth2% e M8 : = ge • ":" • èx),

при этом Ix(ge, mxbs) -> Л/г(gift,mth2s). Кроме того, для e ( Mth \ Мц ) истинно:

Ith(gth, mth)->(le(ge, mth)л Ix(ge, mth)). (5.3)

(3) gx-Ф ge, но существует объект gth e Gth, обладающий признаками mth\ s A/6 : mth\ = pb* ge и mtli2 e M6 : mi/i2 = Рь * g*, при этом для любого признака mth e ( Mth \ Мц ) справедливо:

Ith(gth, mth)-* (le(ge, mth)л Ix(gx, mth)). (5.4)

(4) gx & ge, но существует объект gth\ e Gth, обладающий признаком mth y e A/6 : mth\ = pb • ge, a для V me e (Me4 и Me$ ) верно:

( Ith( gth\, mth\ ) л Ie( ge, me)) Ith( gthi, me). При этом существуют признаки mth2 е Mg : mi/22 = Pb * и

ж e ( Mt| uJIft2 uAfe3), для которых верно:

(lth[gth\, mth2)л Ix(gx, mx)Ith(gthx, mx), где gxg ^ gx, a пара (gxg,ge) отвечает условию (3) при генерации ФК вида (5,1) для объекта gth\. В то же время существует объект gilb e Gth, относительно которого пара (gx, gxg) также будет отвечать условию (3) настоящего определения. Генерируемый при этом формальный контекст вида (5.1) для gthj обозначим как Kxg, Kxg = [Gxg, Mxg, Ixg).

Замечание. Оценка схожести ситуаций S] и S2 включает сравнение последовательностей двух и более соподчиненных слов. Выполнимость условий определения 5.1 анализируется только для главных слов. Последовательности считаются заменяемыми, если возможно их построение по формальному контексту (5.2) на наборе признаков с префиксом pbs для одной и той же СЯУ.

С учётом сопоставления согласно определению 5.1 объектов формальных контекстов Ке = (Ge, Me, le) и Kx = (Gx,Mx,Ix), из которых удалена информация РПЗ, схожесть ситуаций .S[ и S2 численно оценивается как

п

ipc(51,5'2) = A=1-, (5.5)

п

где п = | Gx I, a spck есть значение схожести объектов в паре (gxk, ge). В зависимости от выполнимости условий определения 5.1 значение spck либо равно 1,0, если для пары (sxk > £е) выполнено условие (1), либо вычисляется по формуле:

-log2 1-

ï \BLCS\

pathc

(5.6)

|ß[ \ BLCS\ +1B2 \ BLCS\ +1BLCS \'

если для пары (gxk, ge) выполнено условие (2), (3) либо (4).

Во втором случае имеем гипотетическую решетку ФП (обозначим её как ЭТхе ), в которой объемы объектных ФП (формальных понятий с одним объектом в составе

объема) есть {gxk} и {ge} (при выполнении условия (2) или (3)) либо {gxk}, {ge} и {gxg} (при выполнении условия (4)). Значение Dc равно числу сравнимых формальных понятий, составляющих цепочку с вершинным ФП решетки Э1хе в качестве максимального ФП и наименьшим общим суперпонятием (НОСП) для объекгаых формальных понятий решетки ЧЯхе - в качестве минимального ФП. Множество BLCS есть содержание (множество признаков всех объектов) этого НОСП, а число pathc равно минимальному числу ФП в цепочке, которой принадлежит вершинное ФП, наименьшее ФП решетки Шхе и формальное понятие с содержанием BLCS.

В случае выполнения любого из условий (2), (3) или (4) значение Dc = 2 . При выполнении условия (2) либо (3) pathc = 4, а в BLCS войдут признаки mth е (Mth \ Мц ), для каждого из которых справедливо либо соотношение (5.3) (при выполнении условия (2)), либо соотношение (5.4) (при выполнении условия (3)). Множества В\ и В2 в этом случае определяются следующим образом:

В\ = { те : те е (Ме\ иМе2 иМе3), Ie(ge,me) = true}, B2 = {mx:mxs {Мхх vjMx2 uMt3), Ix{gxk,mx) = true}. Доказательство выполнимости условия (4) обычно происходит в несколько итераций. При этом в ходе каждой последующей итерации число признаков, не являющихся общими для gxk и gxg, всегда меньше, чем в предыдущей. Начальное значение pathc , равное 4, в ходе каждой итерации увеличивается на 1, а

■В) = {mxg : mxg е {Mxgx v Mxg2 u Mxg3 ), Ixg( gxg, mxg) = true}, B2 = {mx: mx e (Mxg\ u Mxg2 u Mxg-$ ), Ixg{ gxk, mx) = true}, где {Mxg\ u Mxg2 ^ Mxgi) a Mxg в соответствии с показанным выше разделением множества признаков формального контекста вида (5.1), a BLCS = В\ п В2 ■

Далее в разделе 5.5 приводится пример интерпретации ТЗОФ с вычислением оценок (5.5).

Таблица 1

Сопоставление ответов правильному варианту

ответы правильный вариант анализируемый

вариант 1 1 2 | 3 | 4 1 | 2 | 3

основа флективная часть + предлог

заниженн ости ости ость ость ость ость ости

эмпирическ ого ого ого ого - - -

риск а а а а - - -

среди - - - - ей ей ей

ошибк - - - - и:на и:на и:на

обучающ _ _ - - ей ей ей

выборк _ _ _ - е е е

переобучении е _ - ем ем - е

переподгонк _ а ой - - ой -

связан - - а:с а:с а:с ах -

привод ит:к ит:к - - - - ит:к

Пусть задана четырьмя вариантами правильного ответа на вопрос о связи переобучения и эмпирического риска. Допустим, имеются три варианта (см. табл. 1),

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

Таблица 2

Факты предметной области для фрагмента тезауруса

№г/п 1 2 3 4

основа флективная часть + предлог

занижены ость ость ости ости - ость ости ость ость

оценк - - - - - и и и и

эмпирическ ого - ого - - - - -

риск а - а - - - - -

среди ошибк _ ей и:на : ей и:на : _ _ и и

распознавани обучающ выборк - ей е - ей е - - я я

переусложнени ем ем е е - - - -

модел и и и и - - - -

уменьшени обобщающ _ _ _ _ е ей ей ей — —

способност - - - - и и и - -

выбор - - - - - - ом а

решающ - - - - его - его его

дерев - - - - а - - -

правил - - - - - - а а

алгоритм - - - - - а а - -

переподгонк переобучени : : — — ой ой а ем е —

связан а:е а:с - - о:с а:с - а:с -

вызван а а - - - а — - -

обусловлен а а - - о - - -

привод - - ит:к ит:к - — ит:к - -

завис - - - - - - - ит:от

Использованные в эксперименте формальные контексты строились по результатам синтаксического разбора фраз, представленных в табл. 1, программой "Cognitive Dwarf'. Как видно из табл. 3, значение схожести будет больше у того варианта S2, признаки объектов у ФК которого разделяются большим числом объектов формального контекста ситуации относительно ФК тезауруса.

Таблица 3

_Оценка близости ответа правильному варианту

Вариант spc(SuS2) \BLCS\ \ BLCS\ \b2\blcs\

1 0,9167 7,7500 0,7500 0,0000

2 0,7917 7,0000 2,0000 0,5000

3 0,8750 7,7500 0,7500 0,7500

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

Шестая глава диссертации посвящена разделению и сжатию баз предметных и языковых знаний с применением комплексной методики формирования и кластеризации семантических отношений, изложенной в разделах 3.5, 4.1, 5.2 и 5.3. Здесь вводится понятие смыслового эталона СЯУ и рассматриваются два приближенных метода его построения с представлением формальным контекстом вида (5.1).

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

Пусть Ке = (Ое,Ме,1е) есть искомый формальный контекст эталона. Если 3{/Д}с7: О'Д)е Е в расширенном дереве (3.11), то для основ Ьу и Ьк и флексий /у и соответствующие им элементы множеств Се и Ме, а также элементы отношения 1е, будут сформированы следующим образом.

Случай 1. Индекс к соответствует родительскому узлу, индекс у - дочернему узлу в расширенном дереве (3.11), а линейная структура ЕЯ-фразы не содержит предлог между словами с индексами у и к.

При этом в состав множества признаков Ме формального контекста Ке = {ре, Ме, 1е) будут включены признаки т\ = рЬз *Ък, т2 = рь/ • Л, Щ = Р/1* /у и т4 = fj •":" • /д, основа bj войдет в множество объектов указанного ФК, а пары [ьу,ту), (/> у,т2), (ь,-,/яз)и (bj,m^) войдут в отношение /е.

Случай 2. Индекс к соответствует родительскому узлу, индекс у - дочернему узлу в расширенном дереве (3.11), линейная структура ЕЯ-фразы содержит предлог ру между словами с индексами у и к.

В этом случае признаки т\ и т3 формируются аналогично случаю 1, «2 = РЬ/9 Л Ру, пЧ = /у • * /к* "'■" * Ру пары \р],тх), [ьу ,т2), (бу,т3) и включаются в отношение /е.

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

Коэффициент сжатия информации по основам равен:

пЬя №

"bs, nmf

Z Y.nasijk

где ksj = ---; nbs —1AfJ; nmf - \M2\;

nbsj

nbs[ = | {g e Gs : Is(g,m)= true, me M\,m = pi,s • A;} |;

«в/jt :Is(gj,mk)=true,3mbf eM2, mbf = phf * fk> mk =bi *":"*Л}|;

Pbf соответствует символьной константе "главное - флексия:". Аналогично определяется коэффициент сжатия информации по флексиям:

гф

«А пт/

X Ипа1цк

у=1 *=1

¥ = (6.5)

где к/, = ' '-; и/5 = |А/5|; л/*,- = I е б*: = ¿гае, т е М5, тя = рд •/;•}[;

Ф\ 1

па/ук =| {теМ4 :3тЬу еМ2,ть/= рь/ »/к,т = Л •"■"•/к }|-

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

которой тх=рЬз*Ь, т2 =ял/*/|. от3=6«":"»/,, т4=р/!»/2, т5 = /2 •":"•/,. При

этом основе Ъ не должен соответствовать объект ФК, если есть другой объект этого же ФК, который обладает одновременно признаком ту и некоторым другим признаком т = рьз • 1ц, где ¿1 * Ъ, а основе ¿>1 не соответствует ни одного объекта этого ФК

при том, что признак т относится более чем к одному объекту.

Замечание. Последовательности трех и более соподчиненных слов, встречающиеся более чем в 49% исходных СЭ-фраз, выделяются предварительно на этапе синтаксического разбора. Для каждой такой последовательности строится свой ФК вида (5.1), который будет объединен с ФК эталона. Данный шаг предпринят в целях нежелательного занижения коэффициентов (6.4) и (6.5) при выполнении алгоритма 6.1.

Таблица 4

Ситуации языкового употребления

/ Фраза максимальной дайны из определяющих СЯУ

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

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

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

4 Ог/енка частоты ошибок на выборке, взятой в качестве контрольной, может для алгоритма оказаться заниженной по причине переподгонки.

5 Заниженность оценки ошибки распознавания зависит от выбора правила принятия решений.

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

Качественно процесс формирования смысловых эталонов характеризуется соотношением размеров тезауруса, задаваемого формальным контекстом (5.2), при построении его на основе формальных контекстов вида (5.1) для всех СЭ-фраз каждой СЯУ и на основе эталонов при заданном числе СЯУ в тезаурусе. Пример указанного соотношения приведен на рис. 1 для СЯУ из табл. 4. Часть указанных СЯУ была задействована при построении тезауруса, представленного в табл. 2.

120000"

100000-

80000-

60000-

40000

20000

1 1 1 1 " ' 1 " ' 1 1 1 1 • 1 1 1 1 Л 1 | •

1 1 1 1 1 гу^ 1 1 1 1 ' 1 1 ' 1 Гг""^ 1

1 1 1 1 ^^ 1 ■ 1 / 1 ' ГГ 1 1 1 ' X 1 " ' \ I 1

1 1 у/ У \ 1 '

1 уГ / 1 / ' ' " 1 1 | '

/ 1 ^^ / ^Го—□—а \ о—о—о размер тезауруса до выделения эталонов, байт размер тезауруса на основе эталонов, байт 4—■ I ■■■■ 1 ■■■ ■

0 1 2 3 4 5 В

Число СЯУ в тезаурусе Рис. 1. Размер тезауруса для разного числа СЯУ

Для сравнения в табл. 5 представлены значения числа СЭ-фраз, задающих ситуацию языкового употребления (М,), фраз, представляющих эталон ситуации языкового употребления (ЛГ2), исходного числа объектов (ЛГ3) и признаков ситуации языкового употребления ( М4 ), числа объектов (N5 ) и признаков эталона (ЛГ6).

Таблица 5

1 1 2 3 4 5 6

щ 56 28 29 30 6 10

N2 8 9 7 9 1 2

18 17 15 13 12 14

177 186 173 162 94 81

9 12 12 11 8 12

N6 82 90 80 69 35 53

Точность формирования эталона повышается введением согласования знаний относительно разных СЯУ, которое определятся следующим образом. Пусть Ь] - основа слова IV , - его флексия, выделенные относительно СЯУ 5} . Предположим, что V = Ъх «Л для СЯУ 51!, V/ = Ъ2 • /2 Для СЯУ Б2, причём Ьх = Ъ2 »эй/ , где зи/ содержит минимум один символ. Тогда относительно ^ основа Ъ\ будет заменена на Ъ2 , флексия /1 - на /3 = эй/ • /2 , но только в том случае, если частоты встречаемости флексий /3 и /2 в отношениях, представляемых формальным контекстом (5.2) тезауруса заданной ПО, не уменьшаются при выполнении указанных замен.

3 13.0--

после согласо*аниязнании о синоним без выполнения процедуры согласован

для всех СЯУ я знаний

3 4

Число СЯУ в тезаурусе

Рис. 2. Сокращение размеров тезауруса согласованием знаний по разным СЯУ

Э.ЧЗ-Т-

Число СЯУ в

Рис. 3. Сжатие информации тезауруса (эталоны выделены)

Диаграмма на рис. 2 иллюстрирует дополнительное сокращение размеров тезауруса в среднем на 1,5% при выполнении указанной процедуры для ситуаций языкового употребления из табл. 4. Рост специфичности формальных понятий в решётке тезауруса иллюстрируется постепенным уменьшением коэффициентов сжатия информации (рис. 3), аналогичных коэффициентам (6.4) и (6.5) для ФК вида (5.1).

Использование СЯУ в качестве единицы предварительного сжатия информации позволяет сократить резервируемый объём памяти ЭВМ для хранения текстов с учётом возможных видов синонимии. На сегодняшний день за такую оценку для отдельной фразы из п слов берётся значение уо1{п) = п\. Метод и алгоритмы выделения эталона СЯУ, представленные в диссертации, позволяют оценивать данный объём сверху как чо1\{п) = 1\ ■п и снизу как уо12(п) = 12 где - число СЭ-фраз из задающих СЯУ, из которых 12 определяют эталон. Соотношение указанных оценок для СЯУ из табл. 4 представлено в табл. 6.

Таблица б

Оценка объёма памяти для хранения ЕЯ-фразы

2 1 2 3 4 5 6

п 12 15 16 17 10 14

УО1(П) 4.790-108 1.308 ■ 1012 2.092 Ю13 3.557-Ю14 3.629-106 8.718-Ю10

Уо1\ (п) 648 795 416 442 20 42

Л>о12{п) 168 225 80 187 20 42

В разделе 6.4 приводится описание архитектуры системы контроля знаний, реализующей предложенные в работе принципы, методы и алгоритмы. На рис. 4 представлен её интерфейс, а также интерпретация ответа на вопрос о влиянии переподгонки на частоту ошибок дерева принятия решений. Демо-версия системы представлена вместе с полным текстом работы в подразделе "Участник:Вткгу.М1к1шу1оу" раздела "Страницы участников" профессионального информационно-аналитического ресурса www.machinelearning.ru. акты о результатах опытной эксплуатации приводятся в приложении 2. Были реализованы следующие компоненты: формирование эталонов и базы лексико-синтаксических связей на основе формальных контекстов (5.1) и (5.2), тезаурус, подготовка и выполнение теста. В целях более гибкой интерпретации ответа испытуемого оценки вида (5.5) вычисляются для случаев неполного ответа, орфографических ошибок, лишних слов, которые не фигурируют в лексико-синтаксических связях, представленных в базе знаний системы.

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

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

Ненулевое значение оценки (5.6) будет только для тех из упущенных слов, которые в варианте правильного ответа являются синтаксически зависимыми по отношению к некоторым другим словам, присутствующим в анализируемом ответе. Здесь мы имеем обобщение оценки (5.6) на случай, когда для одного из сравниваемых объектов (основы упущенного слова) не определены признаки из множеств М:с5 (указание на флексию зависимого слова), Мх4 (сочетание флексий зависимого и главного слова), А/й (указание на основу зависимого слова), М7 (сочетание основы и флексии зависимого слова), (сочетание основ зависимого и главного слова).

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

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

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

"«=jj Тестирование знаний и подготовка к ЕГЭ . "'' ': . . ' • ' •

база знаний Тесты Первое знакомство Window Помощь

.

' " ' ■ ■ _:____

j Численные Оценки близости правильному ответу ■:

Испшуеиые^ 1Ию>иое

Вопрос l" I.......0.8

еЕ.А.|Петров М.Н.|Сипорпв Д. Л J Зайцев Ё.А.1 Ваяков A.B.I-tj

"ПЧмГТ о! ГТаса j 0.857 _Н

ÖJ3TT Ü.868_J 0.7~

0.63 0-006

О.В51_ ä ÖTTI"

д™»—^ | 5

игг™|

' Результат по испытуемому

Испытуемый: Петров ЬШ.

Вопрос теста (вопрос №3):

" РШИ

щщ.

Как влияет переподгонка на частоту ошибок дерева принятия решений ?

Полученный ответ:

Именно с переобучение связана увеличение частоты ошибок дерева принятия решений на контрольной (= тестовой) выборке.

Id

Й

- _'

Наиболее близкий вариант правильного ответа:

Увеличение частоты ошибок

дерева принятия решений на контрольной выборке связано с переподгонкой.

Численная оценка близости правильному ответу: 0.63 Оценка за ответ: удовл.

Рис. 4. Пример интерпретации ответа на ТЗОФ

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

Заключение

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

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

Новизной решения является теоретико-решеточное представление СЯУ в качестве информационной единицы тезауруса предметной области. За счёт использования формального понятия в качестве базового элемента информационного ресурса предложенное представление тезауруса решеткой формальных понятий позволяет оперировать данными на семантическом уровне без потери или недопустимого упрощения объектов и их признаков.

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

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

3. Разработаны метод и алгоритмы автоматизированного формирования смыслового эталона в виде решётки формальных понятий, а также метод компрессии текстовой базы знаний на основе выделенных эталонов.

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

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

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

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

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

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

Список основных публикаций автора по теме диссертации Монография

1. Михайлов Д.В. Теоретические основы построения открытых вопросно-ответных систем. Семантическая эквивалентность текстов и модели их распознавания: монография / Д.В. Михайлов, Г.М. Емельянов; НовГУ им. Ярослава Мудрого. Вели-тай Новгород, 2010. 286 с.

Статьи в рецензируемых научных журналах, включенных в реестр ВАК

МОиН РФ

2. Михайлов Д.В. Распознавание сверхфразовых единств при установлении эквивалентности смысловых образов высказываний в общей задаче моделирования языковой деятельности / Г.М. Емельянов, Д.В. Михайлов // Известия СПбГЭТУ "ЛЭТИ", сер. "Информатика, управление и компьютерные технологии". СПб., 2003. Вып. 1. С. 65-73.

3. Михайлов Д.В. Информационно-логическая модель системы правил Д-грамматики / Д.В. Михайлов, Г.М. Емельянов // Известия СПбГЭТУ "ЛЭТИ", сер. "Информатика, управление и компьютерные технологии". СПб., 2003. Вып. 3. С. 96-102.

4. Михайлов Д.В. Построение модели объекта информационного пространства применительно к исследованию динамики функционирования Д-грамматик / Д.В. Михайлов, Г.М. Емельянов // Вестник Новгородского государственного университета имени Ярослава Мудрого, сер. "Технические науки". 2004. № 26. С. 131-136.

5. Михайлов Д.В. Представление смысла в задаче установления семантической эквивалентности высказываний / Д.В. Михайлов, Г.М. Емельянов // Вестник Новгородского государственного университета имени Ярослава Мудрого, сер. "Технические науки". 2004. № 28. С. 106-110.

6. Михайлов Д.В. Семантическая кластеризация текстов предметных языков (морфология и синтаксис) / Д.В. Михайлов, Г.М. Емельянов // Компьютерная оптика. 2009. Т. 33, № 4. С. 473-480.

7. Михайлов Д.В. Формирование смысловых эталонов и интерпретация результатов открытых тестов в системах контроля знаний / Д.В. Михайлов // Вестник Новгородского государственного университета имени Ярослава Мудрого, сер. "Технические науки". 2011. № 65. С. 83-87.

8. Михайлов Д.В. Смысловые эталоны в моделях распознавания и компрессии текстов / Д.В. Михайлов // Вестник Новгородского государственного университета имени Ярослава Мудрого. 2012. № 68 (в печати).

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

10. Mikhailov D. V. Recognition of Superphrase Unities in Texts while Establishing Their Semantic Equivalence / G. M. Emelyanov, D. V. Mikhailov, E. I. Zaitseva // Pattern Recognition and Image Analysis. 2003. Vol. 13, N 3. P. 447^51.

11. Mikhailov D. V. Updating the Language Knowledge Base in the Problem of Equivalence Analysis of Semantic Images of Statements / G. M. Emelyanov, D. V. Mikhailov // Pattern Recognition and Image Analysis. 2005. Vol. 15, N 2. P. 384-386.

12. Mikhailov D. V. Filling in the Government-Pattern Dictionary in the Analysis of Equivalence for Sense Images of Statements / G. M. Emel'yanov, D. V. Mikhailov // Pattern Recognition and Image Analysis. 2007. Vol. 17, N 2. P. 268-273.

13. Mikhailov D. V. Clusterization of Semantic Meanings in the Problem of Sense Equivalence Situation Recognition / G. M. Emel'yanov, D. V. Mikhailov // Pattern Recognition and Image Analysis. 2009. Vol. 19, N 1. P. 92-102.

14. Mikhailov D. V. Formation and clustering of noun contexts within the framework of Splintered Values / D. V. Mikhailov, G. M. Emelyanov, N. A. Stepanova // Pattern Recognition and Image Analysis. 2009. Vol. 19, N 4. P. 664-672.

15. Mikhailov D. V. Sense's Standards and Machine Understanding of Texts in the System for Computer-Aided Testing of Knowledge / G. M. Emelyanov, D. V. Mikhailov // Pattern Recognition and Image Analysis. 2011. Vol. 21, N 4. P. 705-719.

16. Mikhailov D. V. Semantic Clustering and Affinity Measure of Subject-Oriented Language Texts / D.V. Mikhailov, G.M. Emel'yanov // Pattern Recognition and Image Analysis. 2010. Vol. 20, N 3. P. 376-385.

17.Корнышов A.H. Концептуально-ситуационное моделирование высказываний естественного языка в задаче анализа их смысловой эквивалентности / А. Н. Корны-шов, Д.В. Михайлов // Вестник Новгородского государственного университета имени Ярослава Мудрого, сер. "Технические науки". 2005. № 34. С. 76-80.

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

19. Emelyanov G. M. Semantic Relation Analysis for Classification of the Meaning Patterns of Utterances / G. M. Emelyanov, D. V. Mikhailov, N. A. Stepanova // Pattern Recognition and Image Analysis. 2005. Vol. 15, N 2. P. 382-383.

20. Emel'yanov G. M. Analysis of Semantic Relations in Classification of Sense Images of Statements / G. M. Emel'yanov, D. V. Mikhailov, N. A. Stepanova // Pattern Recognition and Image Analysis. 2007. Vol. 17, N 2. P. 274-278.

Доклады на международных конференциях

2¡.Михайлов Д. В. Применение аппарата ограниченных сетей Петри для построения динамической модели естественного языка / Г. М. Емельянов, Е. И. Зайцева, Д. В. Михайлов // Интеллектуализация обработки информации: тезисы докладов Международной научной конференции / Крымский научный центр HAH Украины, Таврический национальный университет. Симферополь, 2002. С. 121-122.

22. Михайлов Д. В. Установление смысловой эквивалентности высказываний: на пути к решению проблемы / Г. М. Емельянов, Д. В. Михайлов // Интеллектуализация обработки информации: тезисы докладов Международной научной конференции / Крымский научный центр HAH Украины. Симферополь, 2004. С. 70.

23.Михайлов Д. В. Модель сортовой системы языка в задаче построения семантического образа высказывания на уровне глубинного синтаксиса / Д. В. Михайлов, Г. М. Емельянов // Интеллектуализация обработки информации: тезисы докладов Международной научной конференции / Крымский научный центр HAH Украины. Симферополь, 2006. С. 148-150.

24. Михайлов Д. В. Формирование и кластеризация понятий на основе множества ситуационных контекстов / Д. В. Михайлов, Г. М. Емельянов, Н. А. Степанова И Интеллектуализация обработки информации: тез. докл. Междунар. науч. конф. / Крымский научный центр HAH Украины. Симферополь, 2008. С. 168-170.

25. Михайлов Д. В. Семантическая схожесть текстов в задаче автоматизированного контроля знаний / Д. В. Михайлов, Г. М. Емельянов // 8-я Международная конференция "Интеллектуализация обработки информации" (ИОИ-2010): Сборник докладов. М., 2010. С. 516-519.

26.Mikhailov D. V. Updating of the language knowledge base in the problem of statement's semantic images's equivalence's analysis / G. M. Emelyanov, D. V. Mikhailov // 7th Int. Conf. on Pattern Recognition and Image Analysis: new Information Technologies (PRIA-7-2004). Conf. Proc. / SPbETU. St. Petersburg, 2004. Vol. II. P. 462-465.

27. Mikhailov D. V. Formalization of the word's lexical meaning in a problem of recognition of natural language's statements's synonymy's situations / G. M. Emelyanov, D. V. Mikhailov // 8th Int. Conf. "Pattern Recognition and Image Analysis: new Information Technologies" (PRIA-8-2007). Conf. Proc. / Mari State Technical University. Yoshkar-Ola, 2007. Vol. 2. P. 253-257.

28.Mikhailov D. V. Formation and clustering of Russian's nouns's contexts within the frameworks of splintered values / D. V. Mikhailov, G. M. Emelyanov // 9th Int. Conf. on Pattern Recognition and Image Analysis: New Information Technologies (PRIA-9-2008). Conf. Proc. / N.I. Lobachevsky State University of Nizhni Novgorod. Nizhni Novgorod, 2008. Vol. 2. P. 39-42.

29. Mikhailov D, V. Semantic clustering in a problem of text information's compression / D. V. Mikhailov, G. M. Emelyanov // 10th Int. Conf. on Pattern Recognition and Image Analysis: New Information Technologies (PRIA-10-2010). Conf. Proc. St. Petersburg, 2010. Vol. 2. P. 193-196.

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

31. Емельянов Г. М. Концептуально-ситуационное моделирование процесса перифразирования высказываний Естественного Языка как обучение на основе прецедентов /

Г. М. Емельянов, А. Н. Корнышов, Д. В. Михайлов // Интеллектуализация обработки информации: тезисы докладов Международной научной конференции / Крымский научный центр HAH Украины. Симферополь, 2006. С. 78-79.

32. Корнышов А. Н. Иерархизация системы предикатов семантических отношений / А. Н. Корнышов, Д. В. Михайлов // Интеллектуализация обработки информации: тезисы докладов Международной научной конференции / Крымский научный центр HAH Украины. Симферополь, 2008. С. 130-131.

33.Emelyanov G.M. Semantic relation analysis for Classification of meaning pattern of utterances / G.M. Emelyanov, D.V. Mikhailov, N.A. Stepanova // 7th Int. Conf. on Pattern Recognition and Image Analysis: new Information Technologies (PRIA-7-2004). Conf. Proc. / SPbETU. St. Petersburg, 2004. Vol. II. P. 460-461.

Доклады на всероссийских конференциях

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

35.Михайлов Д. В. Применение семантических полей словаря РОСС в задаче построения модели управления предикатного слова / Д. В. Михайлов, Г. М. Емельянов // 12-я Всероссийская конференция "Математические методы распознавания образов" (ММРО-12): сборник докладов. М., 2005. С. 382-385.

36. Михайлов Д. В. Кластеризация семантических знаний в задаче распознавания ситуаций смысловой эквивалентности / Д. В. Михайлов, Г. М. Емельянов // 13-я Всероссийская конференция "Математические методы распознавания образов" (ММРО-13). М„ 2007. С. 500-503.

37.Михайлов Д. В. Морфология и синтаксис в задаче семантической кластеризации / Д. В. Михайлов, Г. М. Емельянов // 14-я Всероссийская конференция "Математические методы распознавания образов" (ММРО-14): сборник докладов. М., 2009. С. 563-566.

38. Михайлов Д. В. Анализ формальных понятий и сжатие текстовой информации в задаче автоматизированного контроля знаний / Г. М. Емельянов, Д. В. Михайлов // 15-я Всерос. конф. "Математические методы распознавания образов" (ММРО-15): сб. докл. М., 2011. С. 581-584.

Свидетельство об официальной регистрации программы для ЭВМ

39. Свидетельство об официальной регистрации программы для ЭВМ № 2010617263. Программа формирования синтаксических отношений на множестве семантически эквивалентных фраз / Залешин М. В., Михайлов Д. В., Емельянов Г. М.; заявитель и правообладатель "Новгородский государственный университет имени Ярослава Мудрого". Заявка № 2010615398; заявл. 02.09.10.; зарег. 29.10.10.

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

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

41. Михайлов Д. В. Установление смысловой эквивалентности высказываний: на пути к решению проблемы / Г. М. Емельянов, Д. В. Михайлов // Искусственный интеллект. 2004. № 2. С. 86-90.

42. Михайлов Д. В. Построение модели управления предикатного слова на основе его лексикографического толкования / Г. М. Емельянов, Д. В. Михайлов // Таврический вестник информатики и математики. 2005. № 1. С. 35-48.

43.Михайлов Д. В. Модель сортовой системы языка в задаче построения семантического образа высказывания на уровне глубинного синтаксиса / Д. В. Михайлов, Г. М. Емельянов // Таврический вестник информатики и математики. 2006. № 1. С. 79-90.

44. Михайлов Д. В. Формирование и кластеризация понятий на основе множества ситуационных контекстов / Д. В. Михайлов, Г. М. Емельянов, Н. А. Степанова // Таврический вестник информатики и математики. 2008. № 2. С. 79-88.

45. Михайлов Д. В. Формирование и кластеризация контекстов для существительных русского языка в рамках конверсивных замен / Д. В. Михайлов, Н. А. Степанова, И. И. Юрченко // Физика и механика материалов: приложение к научно-теоретическому и прикладному журналу "Вестник Новгородского государственного университета имени Ярослава Мудрого". 2009. № 50. С. 31-34.

46. Емельянов Г. М. Кощептуально-ситуащюнное моделирование процесса перефразирования высказываний естественного языка как обучение на основе прецедентов / Г. М. Емельянов, А. Н. Корнышов, Д. В. Михайлов // Искусственный интеллект. 2006. №2. С. 72-75.

Изд. лиц. ЛР № 020815 от 21.09.98. Подписано в печать 30.11.2012. Формат 60x84 1/16. Усл. печ. л. 2,0. Тираж 100 экз. Заказ № 22

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

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Новгородский государственный университет имени Ярослава Мудрого"

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

05201350530

ТЕОРЕТИЧЕСКИЕ ОСНОВЫ, МЕТОДЫ И АЛГОРИТМЫ ФОРМИРОВАНИЯ ЗНАНИЙ О СИНОНИМИИ ДЛЯ ЗАДА Ч АНАЛИЗА И СЖАТИЯ ТЕКСТОВОЙ ИНФОРМАЦИИ

Специальность 05.13.17 — Теоретические основы информатики

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

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

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

Великий Новгород 2012

АРМ

АФП

ГСС

ЕЯ

ИГ

ЛЗ

ЛСК

ЛФ

МУ

нопп носп

РЗ

РОСС РПЗ

сг

СемП

СК

СХ

сэ

СЯУ

ткс

ФП ХФ

ПЕРЕЧЕНЬ СОКРАЩЕНИЙ

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

ПЕРЕЧЕНЬ ОСНОВНЫХ ОБОЗНАЧЕНИЙ

Г = П) А-грамматика, VR - словарь пометок на ветвях дерева,

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

Rap[rulej) условие применимости правила rulej е П

С0 ключевое слово комплекса единиц wrk eWR и связей

vf j е VR между ними, заменяемых некоторым ruleg П

Lm(wi ) теория лексического значения слова

К - (G, M, /) формальный контекст с множеством объектов G и

множеством признаков M, I çzGx M

^ отношение порядка для формальных понятий

решетка формальных понятий

Null формальный контекст с пустыми множествами объек-

тов и признаков

• операция конкатенации

norm функция, ставит в соотвествие слову начальную форму

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

словом

Spv : (vj ], v12 ) —> V21 функция, ставит в соответствие расщеплённому предикатному значению 15 vi 21 его однословное выражение V21

J индексное множество

Ls(Ts[ ) модель линейной структуры ЕЯ-фразы Tst

S = (0,R,Ts) ситуация языкового употребления, О - множество зна-

чимых в ситуации понятий, Ts — множество альтернативных форм описания ситуации в некоторой знаковой

системе; R<zOn, ne 1,...,|0|

СОДЕРЖАНИЕ

ВВЕДЕНИЕ.................................................................................................................. 7

Глава 1. СИТУАЦИЯ ЯЗЫКОВОГО УПОТРЕБЛЕНИЯ

И КЛАСТЕРИЗАЦИЯ ПРЕДМЕТНО-ЯЗЫКОВЫХ ЗНАНИЙ................................... 21

1.1. Семантическая эквивалентность и ситуация языкового употребления... 21

1.2. Концептуальная модель процесса установления

семантической эквивалентности.................................................................. 25

1.3. Уровень глубинного синтаксиса................................................................... 29

1.4. Анализ формальных понятий как инструмент

концептуальной кластеризации.................................................................... 33

Выводы............................................................................................................ 37

Глава 2. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ РАСПОЗНАВАНИЯ СВЕРХФРАЗОВЫХ ЕДИНСТВ НА УРОВНЕ ГЛУБИННОГО СИНТАКСИСА.................................. 39

2.1. Концептуальная модель процесса распознавания взаимной дополняемости фраз в сравниваемых по смыслу высказываниях естественного языка........................................................... 39

2.2. Построение системы целевых выводов в Д-грамматике............................ 49

2.3. Моделирование построения образа суммарного смысла................................... 71

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

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

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

Выводы............................................................................................................101

Глава 3. ФОРМИРОВАНИЕ И ЭКСПЕРИМЕНТАЛЬНАЯ ОЦЕНКА ЗНАНИЙ НА ОСНОВЕ СИТУАЦИЙ СМЫСЛОВОЙ ЭКВИВАЛЕНТНОСТИ............... 102

3.1. Лексическое значение слова и его формализация

на языке логики предикатов первого порядка.......................................... 102

3.2. Прецеденты семантических отношений для ситуаций

синонимии на основе стандартных лексических функций..................... 113

3.3. Семантика расщепленного значения и смысловые валентности предикатного слова......................................................................................116

3.4. Экспериментальная апробация методики формирования прецедентов смысловой эквивалентности на материале

тезауруса по анализу изображений............................................................124

3.5. Формирование отношений в естественном языке

на основе множеств семантически эквивалентных фраз.........................129

Выводы..........................................................................................................141

Глава 4. СЕМАНТИЧЕСКАЯ КЛАСТЕРИЗАЦИЯ ТЕКСТОВ ЕСТЕСТВЕННОГО ЯЗЫКА ВЫДЕЛЕНИЕМ

СИНТАКСИЧЕСКОГО КОНТЕКСТА СУЩЕСТВИТЕЛЬНОГО.....................142

4.1. Семантика синтаксиса как основа кластеризации....................................142

4.2. Концептуальная кластеризация текстов на основе

результатов синтаксического разбора предложений...............................145

4.3. Расщепленные предикатные значения и конверсивы

в составе синтаксических контекстов существительных........................149

4.4. Информативность признака и критерий полезности

решетки формальных понятий...................................................................156

Выводы..........................................................................................................165

Глава 5. МЕТОД ЧИСЛЕННОЙ ОЦЕНКИ СЕМАНТИЧЕСКОЙ СХОЖЕСТИ ТЕКСТОВ ПРЕДМЕТНОГО ЯЗЫКА.....................................................................167

5.1. Синтаксические и семантические связи в ситуации

языкового употребления.............................................................................167

5.2. Формальный контекст ситуации языкового употребления

и методы его построения.............................................................................170

5.3. Тезаурус предметной области и схожесть ситуаций

языкового употребления.............................................................................174

5.4. Интерпретация меры схожести формальных понятий

для формальных контекстов.......................................................................180

5.5. Смысловая близость фраз предметно-ограниченного

подмножества естественного языка...........................................................182

5.6. Сжатие текстовой информации на основе

теоретико-решеточного подхода: проблемы и перспективы..........................189

Выводы..........................................................................................................191

Глава 6. АНАЛИЗ ФОРМАЛЬНЫХ ПОНЯТИЙ И СЖАТИЕ ТЕКСТОВОЙ ИНФОРМАЦИИ РАЗДЕЛЕНИЕМ

ПРЕДМЕТНЫХ И ЯЗЫКОВЫХ ЗНАНИЙ..........................................................193

6.1. Постановка задачи на примере тестовых заданий открытой формы......193

6.2. Формирование смыслового эталона...........................................................199

6.3. Шаблон ситуации языкового употребления

и интерпретация текста предметно-ориентированного

подмножества естественного языка...........................................................219

6.4. Типовая архитектура системы контроля знаний

с применением тестовых заданий открытой формы................................231

Выводы..........................................................................................................239

ЗАКЛЮЧЕНИЕ.......................................................................................................241

СПИСОК ЛИТЕРАТУРЫ.......................................................................................244

ПРИЛОЖЕНИЕ 1. Программа формирования смыслового эталона ситуации языкового употребления на основе семантически эквивалентных фраз. Фрагменты исходного текста на языке Visual Prolog 5.2....................................266

ПРИЛОЖЕНИЕ 2. Акты об апробации результатов

диссертационной работы........................................................................................331

ВВЕДЕНИЕ

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

Актуальность работы. Алгоритмически разрешимые процедуры распознавания смысла высказываний естественного языка (ЕЯ), а также способы представления смысла для решения практических задач составляют основу реализации интеллектуальных систем распознавания и синтеза речи, текста и изображений. Разработка таких систем относится к позиции "технологии обработки, хранения, передачи и защиты информации" перечня критических технологий федерального уровня от 21 мая 2006 года и образует самостоятельное направление, получившее название "Обработка естественного языка" [10, с. 27-48; 11, с. 79-84; 12, с. 165-209; 39, с. 81-219; 43, кн. 1, с. 9-139, 201-261; 108, с. 335-488; 116, с. 10, 44-55; 126, с. 27-28,483-519; 133, с. 10-20].

Сферой рассмотрения автора настоящей диссертационной работы являются задачи, требующие установления полной или частичной эквивалентности по смыслу (семантической эквивалентности — СЭ) высказываний (текстов) ЕЯ [148, 151]. К числу таких задач можно отнести применение заданий открытой формы в системах компьютерного дистанционного обучения и контроля знаний [1, с. 5569; 54, с. 16-18; 60, с. 117-120; 98; 102; 105; 129, с. 181-190], поиск изображений и распознавание семантики сложных информационных объектов по вербальному

описанию [117, 144, 147, 151], анализ сходства текстовых документов [38, 42]. Представление знаний в виде классов семантической эквивалентности текстов, которыми описываются фрагменты действительности, позволяет простым и естественным путём разделять вводимые в ЭВМ знания на уровни (языковой, предметный и т.п.) с учётом основной когнитивной (гносеологической) функции языка как средства передачи знаний от человека к человеку и инструмента для формирования новых знаний [21, с. 24-61]. При этом в качестве исходных данных для формирования знаний выступют тексты на предметно-ограниченном естественном языке, которые вводятся оператором без специальной подготовки в области прикладной и математической лингвистики.

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

Предметом исследования являются методы и алгоритмы формирования знаний о синонимии.

Областью непосредственного применения теоретических результатов работы является автоматизированный контроль знаний. Важное преимущество автоматизированного обучения состоит в реализации известного педагогического принципа индивидуализации обучения [1, с. 227]. При этом наибольший интерес представляют задания открытой формы, то есть задания, требующие самостоятельного формулирования ответа на вопрос теста. В отличие от заданий закрытой формы (выбор правильного ответа из набора вариантов), заданий на соответствие, заданий на установление правильной последовательности, тесты открытой формы исключают догадку [60, с. 160] и позволяют максимально приблизить компьютерный тест к традиционному взаимодействию "Учитель-Ученик".

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

с. 55-56; 54, с. 18; 60, с. 117], либо к простому поиску среди "правильных" вариантов [102]. Причина кроется в нетехнологичности заданий открытой формы. Допуская свободное формулирование ответа, испытуемые могут использовать синонимы, а также изменять порядок следования слов, что особенно актуально для естественных языков со свободным порядком слов в предложении. Основными требованиями здесь являются способность системы анализировать СЭ высказываний с отклонениями от грамматической нормы, единообразие механизмов оперирования предметными и языковыми знаниями, а также ориентацию на автоматизированное пополение последних с минимумом трудозатрат.

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

- синтаксису, его связи с семантикой и лексическими средствами языка, реализующими механизм синонимического перифразирования. Как наиболее близкие рассматриваемой в диссертации проблеме здесь следует отметить работы Мельчука И.А. [62, 162], Гладкого A.B. [14, 15], Апресяна Ю.Д. [3], Кибрика А.Е. [45, 97], Тестельца Я.Г. [121], Солганика Г .Я. [118], Тузова В.А. [123];

- компьютерным словарям, тезаурусу и машинному фонду русского языка. Наибольший интерес в этом направлении заслуживают работы Караулова Ю.Н. [44], Нариньяни A.C. [100], Рубашкина В.Ш. [111], Попова Э.В. [106], Леонтьевой H.H. [58], Демьянкова В.З. [21,22], Гусева В.Д. [18];

- информационному поиску, где следует отметить работы Леонтьевой H.H. [56,58], Осипова Г.С. [101], Попова Э.В. [106], Фомичева В.А. [124,125,152], Соснина П.И. [119,182], Тихомирова И.А. [122], Журавлёва Ю.И. [38], Игнатова Д.И. [42], Гуревича И.Б. [155], Мучника И.Б. [5], Райгородского А.М. [16] и ряд других [17,134-138,142,160,161,180,181,187].

Г.М. Емельяновым, Т.В. Кречетовой и Е.П. Курашовой была предпринята попытка решить эту задачу с привлечением уровня глубинного синтаксиса ЕЯ на

основе модели СЭ с использованием грамматик деревьев (Д-грамматик) в качестве аппарата математического моделирования [151]. Указанный математический аппарат, предложенный A.B. Гладким и И.А.Мельчуком в [14,15] и расширенный разделением преобразований узлов и ветвей, позволил решить задачу моделирования синонимических преобразований ЕЯ-высказываний на уровне варьирования универсальной (абстрактной) лексикой без существенного ограничения входного ЕЯ и предметной области решаемых задач. Но и данному подходу в том виде, в котором он описывается в [151], присущи серьёзные недостатки:

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

- словарная подсистема предполагается замкнутой ввиду существенной сложности описываемой словарём информации;

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

- синонимические преобразования деревьев глубинного синтаксиса в теоретическом плане проработаны не до конца. Использованный в [151] набор правил был взят из работ Ю.Д. Апресяна [3] и И.А. Мельчука [62]. По оценке последнего, указанные правила не претендуют на полноту и возможно их расширение по результатам соответствующих исследований.

Современные поисковые системы, анализируя ЕЯ-запрос, используют статистику встречаемости слов запроса в различных контекстах с учётом возможных синонимов с целью поиска документа, максимально релевантного запросу [5,17]. Аналогичный принцип используется и в статистическом переводе, в частности, в составе поисковой системы Яндекс [134]. Данный подход полностью оправдывает себя в задаче информационного поиска, но он не позволяет воссоздать целостный образ самой ситуации использования ЕЯ для описания фрагмента действительности. Сказанное особенно актуально, в частности, при подготов-

ке тестовых заданий открытой формы, когда задача является принципиально обратной: известен фрагмент реальности и разработчику теста требуется выделить все возможные формы описания этого фрагмента в заданном ЕЯ. При этом также крайне необходима двусторонняя связь "носитель ЕЯ (разработчик теста) - база знаний" с поддержкой актуального (в терминологии баз данных, см. [20, с. 46]) состояния целостного образа отражения фрагмента действительности в сознании разработчика и в его языке, что позволило бы вести сравнительный анализ уровня владения заданным естественным языком и предметными знаниями у разработчиков тестов по некоторой заданной предметной области.

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

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