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

Московский государственный университет имени М.В. Ломоносова

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

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

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

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

Моросанова Наталья Александровна

2 8 НОЯ 2013

Москва - 2013

005539878

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

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

доктор физико-математических наук.

профессор Соловьев Сергей Юрьевич

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

доктор физика-математических наук

профессор Михайлюк Михаил Васильевич

кандидат физико-мат.ем.агпических наук

ст.н.с Гипкул Геннадий Петрович

Ведущая организация: Вычислительный центр им. А.А.Дородницына РАН

Защита состоится «20» декабря 2013 г. в И часов на заседании диссертационного совета Д 501.001.Ц при МГУ имени М.В. Ломоносова, расположенном по адресу: 119991, ГСП-1, Москва, Ленинские горы, МГУ, стр.52, 2-й учебный корпус, факультет ВМК, аудитория 685.

С диссертацией можно ознакомиться в Фундаментальной библиотеке МГУ. С текстом автореферата можно ознакомиться на официальном сайте факультета ВМК МГУ имени М.В. Ломоносова http://www.cs.msu.su. Автореферат разослан «-х£_» ШЪ^р.А, 2013 г. Отзывы и замечания по автореферату в двух экземплярах, заверенные печатью, просьба высылать но вышеуказанному адресу на имя учёного секретаря диссертационного совета.

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

к.т.н.

Костснко В.А.

Общая характеристика работы

Актуальность темы

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

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

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

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

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

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

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

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

Цель работы

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

Научная новизна

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

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

Практическая значимость

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

Реализованные алгоритмы позволяют решать задачи

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

— автоматизированного создания систем формального вывода на основе примеров вывода, в том числе ассоциативных правил, полученных методами Data Mining.

Апробация работы и публикации

Результаты, представленные в работе, докладывались на семинаре «Методы построения программных систем» кафедры Алгоритмических языков, на научно-исследовательском семинаре «Динамические интеллектуальные системы» ИСА РАН, на семинаре «Вопросы распределенной обработки информации» кафедры Автоматизации систем вычислительных комплексов, а также на пяти конференциях:

— II Международная научно-техническая конференция «Открытые семантические технологии проектирования интеллектуальных систем OSTIS-2012». 16-18 февраля 2012, Минск, Белоруссия;

— XIII Национальная конференция по искусственному интеллекту-с международным участием КИИ-2012.16-20 октября 2012, Белгород, Россия;

— III Международная научно-техническая конференция «Открытые семантические технологии проектирования интеллектуальных систем OSTIS 2013». 21-23 февраля 2012, Минск, Белоруссия;

— VII Международная научно-практическая конференция «Интегрированные модели и мягкие вычисления в искусственном интеллекте». 20-22 мая 2013, Коломна, Россия;

— International Conference on Intelligent Information Systems. August 20-23, 2013, Chisinau, Republic of Moldova.

По теме диссертации опубликовано 9 работ, в том числе одна работа [1] в рецензируемых изданиях, включенных в перечень ВАК.

Структура и объем диссертации

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

Краткое содержание диссертации

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

В первой главе приводится определение схемы о.у.:

Определение 1. Схема о.у. есть тройка (X, Рг, Ор), где:

• X — множество значений оценок уверенности,

• Рг и Ор - множества, соответственно, предикатов и операций, (частично) определенных над X.

Известные методы вычисления о.у. и.соответствующие им схемы о.у. рассматриваются по плану: — множество значений о.у.;

— предикаты True(x), False(x), порядок на множестве значений о.у.;

— логические операции: конъюнкция, дизъюнкция и отрицание;

— операция учета о.у. продукционного правила (операция ослабления);

— операция комбинирования.

В число рассмотренных схем о.у. входят

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

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

— схема коэффициентов уверенности Шортлиффа.

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

'Cheng Y., Kashyap R.L. An axiomatic approach for combining evidence from a variety of sources // Journal of Intelligent & Robotic Systems. 1988. Т. 1, №1. C. 17-33.

2Hajek P., Vald£s J.J. An analysis of MYCIN-like expert systems // Mathware & soft computing. 2008. T. 1, №1. C. 45-68.

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

Определение 2. Трансформацией Н =< И,р,9 > упорядоченной пары, схем о.у. Бг = (X, Ргх,Орх) и ¿>2 = (У, Ор2) называется тройка отображений И : X —> У, р : Рп -> Рг2, 9 : Ор\ -> Орг, удовлетворяющая следующим условиям

1. если хх ф Х2, то к{х{) ф Н(х2);

2. если рг\ ф рг[ £ Ргъ то р{ргх) ф р(рг[), и если рг — п-местный предикат из Ргх,

то рг' = р(рг) — также п-местный предикат из Рг2, причем рг(х1, ...,хп)= рг'{Н{х{),хп))\

3. если ор\ ф ор[ £ Ор\, то 9(орг) ф в{ор[), и если ор — п-местная операция из Ор\,

то ор' = в(ор) — также п-местная операция из Ор2, причем к(ор{х 1,..., хп)) = ор'{к{х 1),..., /г(хп)). При этом операции ор и ор' = 9{ор) называются парой сопоставленных операций. Предикаты рг и рг' = р(рг) называются парой сопоставленных предикатов.

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

Определение 3. Трансформация Н =< И,р,в > упорядоченной пары схем о.у. ^ = (X, Рг\,Ор1) и Б2 = (У,Рг2,Ор2) называется биективной (обозначается 5х -А Б2), если

1. К - взаимно однозначное отображение;

р(рг)(уъ ...,Уп)= рг{н~1{у1),..., Ьг\уп)); з. 9(ор)(уь...,Уп) = л(ор(л_1Ы....,/гЧг/п))).

8

Определение 4. Схема о.у. 5\ = (X, Ргг, Ор\) называется подсхемой схемы о.у. 5г = (У,Рг2,Ор2) (обозначается С если ХСУ,

Ург е Ргг Эрг' е Рг2 : Ух 6 Xрг(хь... ,хп) = рг'{хъ ..., х„), Уор е Ор\ Зор' еОр2: Ух еХ ор(х 1, ...,хп)= ор'(х1,..., хп). Определение 5. Трансформация упорядоченной пары схем о.у. = (X, Ргх, Орг) и 52 = (У, Рг2,Ор2) называется инъективной (обозначается А в?.), если й С 52 и вг ф 52.

Частными случаями инъективной трансформации являются в расширение множества значений о.у. X С У\

е добавление операций и предикатов Рг\ С Рг2, Ору С Ор2 при X = У.

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

— схемы ¿>1. и ¿2 эквивалентны, если существует биективная трансформация 5х -А- Б2;

— схема ¿2 является обобщением схемы ¿>1, если существует такая схема Б', что 5! А 5' и 5' 4 52;

— схемы ¿х и ¿2 сопряжены, если существуют такие схемы 5' и 5", что

5' Л 5Ь 5' А 5" и 5" 4 52. ■

Для выяснения типа отношений для пары схем о.у. необходимо построить

соответствующие трансформации. С целью изучения способов построения

трансформаций рассматриваются задачи:

Задача 1. Доопределение операции комбинирования.

Задача 2. Построение трансформации по заданной паре операций.

Задача 3. Построение трансформации по заданной паре схем о.у.

Задача 1 возникает при расширении множества значений о.у.: 5! = (X, 0, {ф}) Л 52 = (X и X', 0, {ор'})-9

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

1. предположить существование биективной трансформации G : S2 > S3, С =< 9>9рп9ор >, гДе 53 — подсхема некоторой известной схемы о.у.;

2. построить трансформацию G для известной части доопределяемой операции (ор на X);

3. с помощью обратного отображения д~1 получить ор' на X'. Задача 2 возникает при выявлении сопоставленных операций, использует в качестве входных данных множества значений о.у. X и Y и, соответственно, операции Д и /2 и состоит в построении отображения h : X -» Y, задающего биективную трансформацию Si = (X, 0, {fx}) A S2 = (У, 0, {/2}):

Hfi(x)) = h{h(x)). (2)

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

Задача 3 возникает при построении биективной трансформации, использует в качестве входных данных две схемы о.у. Si = (X, Pri,Opi) и S2 = (У, Рг2, Ор2) и состоит в построении такого отображения h : X —> Y, что (2) верно для всех пар операций. В диссертации предлагается следующий подход

3Brown Westrick L. Topological Conjugations are Not Constructable. 2013. http://arxiv.org/abs/1303.2244

10

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

Развитая в диссертации техника изучения трансформаций позволила доказать следующие утверждения:

Утверждение 1. Схема, использующая логику с векторной семантикой, является обобщением схемы коэффициентов уверенности Шортлиффа. Утверждение 2. Схема, использующая логику с векторной семантикой, является обобщением схемы, использующей байесовские пары Демпстера4. Утверждение 3. Схема, использующая логику с векторной семантикой, сопряжена со схемой, использующей пары Демпстера4.

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

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

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

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

В третьей главе диссертации рассматриваются программные средства

4,1астные случаи теории Демпстера-Шафера, когда множество гипотез состоит из одной гипотезы и ее отрицания.

5В частности, схема коэффициентов уверенности Шортлиффа связана отношениями с 9 известными схемами о.у.

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

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

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

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

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

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

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

Основные результаты

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

2. Разработаны алгоритмы автоматизированного построения трансформаций по паре операций и по примерам вывода.

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

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

1. Моросанова Н.А, Соловьев С.Ю. Формальные свойства схемы Шортлиф-фа // Управление большими системами. 2012. Т. 36. С. 5-38.

2. Моросанова H.A. Нестрогий вывод в системах альтернатив // Информационные процессы. 2011. Т. И, № 3. С. 394-412.

3. Моросанова H.A. Об одном алгоритме нестрогого вывода на основе логик с векторной семантикой // Сб. Программные системы и инструменты. 2011. № 12. С. 139-149.

4. Моросанова H.A. Схемы оценки уверенности в экспертных системах //

Сборник статей молодых ученых факультета ВМК МГУ. 2012. Т. 9. С. 122-135.

5. Моросанова Н.А. Достоверность правил в экспертных системах // Материалы II Международной научно-технической конференции «Открытые семантические технологии проектирования интеллектуальных систем OSTIS-2012», Минск: БГУИР. 2012. С. 189-192.

6. Моросанова Н.А. Трансформации схем оценки уверенности в логическом выводе // Труды XIII национальной конференции по искусственному интеллекту с международным участием КИИ-2012, Белгород: Изд-во БГТУ. Т. 1. 2012. С. 43-50.

7. Моросанова Н.А. Автоматизация поиска трансформаций схем оценки уверенности // Материалы III Международной научно-технической конференции «Открытые семантические технологии проектирования интеллектуальных систем OSTIS-2013», Минск: БГУИР. 2013. С. 281-284.

8. Моросанова Н.А. Схемы оценки уверенности и их трансформации // Сборник научных трудов VII-ой Международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте», М.: Физматлит. 2013. С. 449-457.

9. Morosanova N. Uncertain Reasoning Models Transformations For a Model Selection // Proceedings of International Conférence on Intelligent Information Systems, ed. C.Gaindric, S.Cojocaru, Chisinau: Institute of Mathematics and Computer Science. 2013. C. 227-230.

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. Подписано в печать 15.11.2013 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 100 экз. Заказ 378. Тел./факс: (495) 939-3890,939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к.

Московский государственный университет имени М.В. Ломоносова

04201365451

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

Ъ

и

Наталья Александровна Моросанова

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

построенных выводов

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов

и компьютерных сетей

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

Научный руководитель д. ф.-м. н., профессор С.Ю. Соловьев

Москва - 2013

Содержание

Глава 1. Оценки уверенности............................................................12

1.1. Терминологические соглашения......................................................13

1.2. Схема оценки уверенности............................................................14

1.3. Операция комбинирования...................'.....................16

1.4. Схема коэффициентов уверенности Шортлиффа..................................20

1.5. Логические схемы......................................................................22

1.6. Схемы, основанные на мерах неопределенности....................................30

Глава 2. Трансформации схем оценки уверенности................................39

2.1. Определение трансформации........................................................39

2.2. Типы трансформаций ................................................................40

2.3. Задачи построения трансформаций..................................................43

2.4. Трансформации схемы Шортлиффа................................................45

2.5. Трансформацихг в логическом выводе..............................................68

Глава 3. Математическое и программное обеспечение поддержки подхода

трансформаций............................................................................72

3.1. Вывод в системах альтернатив......................................................72

3.2. Алгоритмы построения трансформаций............................................85

3.3. Сценарии использования алгоритмов построения трансформаций..............93

Литература......................................................................................97

Приложение А. Автоматизированное построение трансформаций............102

А.1. Построение приближенной трансформации по паре операций комбинирования 102

А.2. Построение трансформации по примерам вывода..................................103

Приложение Б. Обобщение алгоритма вывода в системах альтернатив ... 105

Введение

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

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

1. Теория вероятностей вводит понятие вероятности гипотезы.

2. Теория свидетельств Демпстера-Шафера использует меры доверия, а также определяет понятия поддержки и правдоподобия.

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

4. Логический подход (многозначные, нечеткие логики) описывает неопределенность данных с помощью значений истинности, определяет достоверный вывод.

5. Практический подход экспертных систем (коэффициенты уверенности Шортлиффа) определяет понятие уверенности.

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

• интерпретация понятий:

1. объективные (значения истинности) и субъективные (уверенность, доверие);

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

• тип значения для количественного представления понятия:

1. числовые значения: теория вероятностей, коэффициенты уверенности, классическая логика;

2. интервальные значения: теория свидетельств, теория возможностей, логика с векторной семантикой;

3. нечеткие значения: нечеткие логики.

Обилие перечисленных понятий, имеющих близкие интерпретации в естественном языке и использующихся для описания неопределенности, позволяет предположить, что определяемые величины служат одной практической цели. Эта цель состоит в переходе от формальных выводов с ответом типа «да/нет» к некоторой степени уверенности в полученном отвею. Количественные характеристики неопределенности называются оценками уверенности (о.\.). если совокупность всевозможных о.у. образует упорядоченное множество с выделенными значениями True и, возможно, False. С содержательной точки зрения True есть о.у. истинного (точно установленного) высказывания, a False — о.у. ложного (точно опровергнутого) высказывания. Оценки уверенности приписываются исходным высказываниям и влияют на ход логического вывода, который, в конечном итоге, состоит в перевычислении некоторых о.у.

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

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

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

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

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

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

Цель работы

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

Научная новизна

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

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

Практическая значимость

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

Реализованные алгоритмы позволяют решать задачи

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

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

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

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

В первой главе приводится определение схемы о.у., которая есть тройка (X, Pr, Ор),

где:

• X — множество значений оценок уверенности,

• Рг и Ор — множества, соответственно, предикатов и операций, (частично) определенных над X.

Известные методы вычисления о.у. и соответствующие им схемы о.у. рассматриваются по плану:

— множество значений о.у.;

— предикаты True(x), False(x), порядок на множестве значений о.у.;

— логические операции: конъюнкция, дизъюнкция и отрицание;

— операция учета о.у. продукционного правила (операция ослабления);

— операция комбинирования.

В число рассмотренных схем о.у. входят

логические схемы, использующие нечеткую логику[3, 40, 47], векторную логику|33] и логику с векторной семантикой[46];

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

60], теорию свидетельств Демистера-Шафера [39] и теорию возможностей Дюб^а-Прада

[141;

— схема коэффициентов уверенности Шортлиффа[б].

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

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

Для исследования отношений между схемами рассматриваются два базовых типа трансформаций, именуемых биективными и инъективными трансформациями. Трансформация Я =< Ъ. р,в > упорядоченной пары схем о.у. £1 = (X, Ргх,Орх) и в2 = (У, Рг2,Ор2) нарывается биективной (обозначается й1! +->■ ¿>2), если

1. к - взаимно однозначное отображение;

2. р(рг)(т/ь...,г/„) =рг{Н-1{ух),...,к~1{уп))\

3. в(ор)(уи. ..,уп) = к{ор{к~1{ух),... ,Ь~1(уп))).

Для определения инъективной трансформации вводится понятие подсхемы. Схема о.у. £1 = (Х,Рг

'1, Ор\) называется подсхемой схемы о.у. 52 = (У, Рг2, Ор2) (обозначаеххя 5] С ¿"г),

если

1С У,

Ург е Рп Эрг' е Рг'2 : Ух е X рг(х 1,... ,хп) = рг'(хх,...,х„),

Уор е Орх Эор' € Ор2 : Ух е X ор(х ь ...,х„) = ор'(хх,..., хп).

Трансформация упорядоченной пары схем о.у. = (X, Ргх,Орх) и52 = (У, Рт2,Ор2) назы-

вастся инъективной (обозначается ¿>1 -4 ¿>2), если 5х С 52 и 5*1 52. Частными случаями инъективной трансформации являются

• расширение множества значений о.у. X С У\

• добавление операций и предикатов Рг\ С Ргп. <9р1 С 0/;2 при X = У.

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

— схемы 3\ и £2 эквивалентны, если существует биективная трансформация А 62;

— схема 62 является обобщением схемы 5*1, если существует такая схема 5", что <-> 6" и 5" Л

— схемы и сопряжены, если существуют такие схемы Б' и 5"', что Я' Ях, Б' А 5" и Л 52.

Для выяснения типа отношений для пары схем о.у. необходимо построить соответствующие трансформации. С целью изучения способов построения трансформаций рассматриваются задачи:

Задача 1. Доопределение операции комбинирования.

Задача 2. Построение трансформации по заданной паре операций.

Задача 3. Построение трансформации по заданной паре схем о.у.

Задача 1 возникает при расширении множества значений о.у.:

5! = (X, 0, {ор}) 4 52 = (хи X', 0, {ор'}); (1)

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

1. предположить существование биективной трансформации (? : 5*2 А 8:>у. С =< д,дР,-,д0р >■, где ¿"з — подсхема некоторой известной схемы о.у.;

2. построить трансформацию С для известной части доопределяемой операции (ор на X);

3. с помощью обратного отображения д~1 получить ор' на X'.

Задача 2 возникает при выявлении сопоставленных операций, использует в качестве входных данных множества значений о.у. X и У и, соответственно, операции Д и /2 и состоит в построении отображения Н : X —>■ У, задающего биективную трансформацию 5х =

(ХЛШ) А в2 = (¥,<&, Ш>-

НШ) = М1г(х)). (2)

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

Задача 3 возникает при построении биективной трансформации, использует в качестве входных данных две схемы о.у. ^ = (X, Ргх^Орх) и 52 = (У,Рг2,Ор2) и состоит в построении такого отображения Л : X —> V, что (2) верно для всех пар операций. В диссертации предлагается следующий подход к решению этой задачи: 1) построение трансформации для пары операций, схожих по смыслу, 2) проверка построенной трансформации для остальных пар операций. Построение таких трансформаций позволяет установить эквивалентность пары схем о.у.

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

1. Схема, использующая логику с векторной семантикой [46], является обобщением схемы коэффициентов уверенности Шортлиффа.

2. Схема, использующая логику с векторной семантикой, является обобщением схемы, использующей байесовские пары Демпстера [22].

3. Схема, использующая логику с векторной семантикой, сопряжена со схемой, использующей пары Демпстера[22].

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

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

2. Систематизация схем предоставл