Методы вычисления оценок уверенности формально построенных выводов тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Моросанова, Наталья Александровна

• Моросанова, Наталья Александровна
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Моросанова, Наталья Александровна

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

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

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

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

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

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

Введение

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

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

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. Систематизация схем предоставляет возможность выбора схемы о.у. с фиксированными свойствами.

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

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

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

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

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

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

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

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

В приложениях излагаются особенности программной реализации алгоритмов постро-

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

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

При разработке и использовании интеллектуальных систем возникает задача представления неопределенности данных. Чаще всего в качестве источников неопределенности указывают [21, 25]:

1. вероятностный характер данных;

2. субъективизм экспертной оценки данных;

3. экспериментальную погрешность данных;

4. наличие противоречивости в данных.

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

Одним из способов построения такого представления является использование оценок уверенности — значений, которые описывают степень неопределенности данных. Множество значений, которые может принимать оценка уверенности, как правило, упорядочено. Множество значений зависит от выбора способа описания уверенности. Их можно разделить на две основные группы: количественные и неколичественные способы. В нсколичсствсиных способах уверенность описывается с помощью значений из некоторого множества, например, слов-терминов. В количественных способах уверенность представляется некоторым числовым значением, либо набором числовых значений. Количественные способы более многочисленны и распространены [21]. Часто в качестве такого множества значений выступает множество чисел, например: [0,1], { — 1,0,1}.

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

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

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

Далее вводятся терминологические соглашения, используемые в работе (1.1), более подробно рассматривается понятие «схема оценки уверенности»(1.2) и роль операции комбинирования (1.3), рассматриваются различные схемы: схема Шортлиффа (1.4). логические схемы (1-5) и схемы, основанные на мерах неопределенности (1.6).

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

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

1. В работе под оценкой уверенности (о.у.) понимается количественная оценка уверенности. Другими словами, оценка уверенности является конечным множеством чисел, например: число, пара чисел, числовой вектор.

2. Множество значений, которые может принимать оценка уверенности, называется множеством оценок уверенности (множеством о.у.).

3. В работе исследуются схемы оценки уверенности (схемы о.у.), которые для простоты именуются просто схемами.

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

Название схемы Сокращение Обозн Ссылка

схема оценки уверенности, основанная на многозначной логике многозначная логическая схема МЬ [19]

схема оценки уверенности, основанная па векторной логике векторная логическая схема УЬ [33]

схема оценки уверенности, основанная на двумерной логике с векторной семантикой логиеская схема с векторной семантикой AL [46]

схема оценки уверенности, основанная на нечеткой логике нечеткая логическая схема FL [40. 47]

схема оценки уверенности, основанная на формуле Байеса схема Байеса ВО, BP [42]

схема оценки уверенности, основанная на теории Демнстера-Шафера схема Демпстера-Шафера DS [39]

схема оценки уверенности, основанная на парах Демпстера схема пар Демпстера DP [22]

схема оценки уверенности, основанная на байесовских парах Демпстера схема байесовских пар Демпстера DB [22]

схема оценки уверенности системы Prospector схема системы Prospector РР [15]

схема оценки уверенности системы MYCIN схема Шортлиффа SH [6]

схема оценки уверенности, основанная на теории возможностей Дюбуа-Прада схема Дюбуа NP [12]

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

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

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

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

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

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

• выделения некоторых значений: «истина» (предикат Тгие(х)), «ложь» (предикат False(x)).

«отсутствие информации» и др.;

• сравнения с введенными заранее пороговыми значениями;

• введения порядка на множестве о.у.

Поскольку схема о. у. включает упорядоченное множество значений и операции, определенные над этим множеством, то она может рассматриваться как некоторая алгебраическая система [48]. Следует оговорить, что операции схемы могут быть частично определенными на множестве о.у. Поэтому схема не является алгебраической системой в строгом смысле, однако, путем сужения множества о.у. можно порождать алгебраические системы на основе схем [7, 22].

Схема о. у. является в некотором смысле уточнением схемы правдоподобного умозаключения [57]:

Из А следует В

В истинно (1-1)

Следовательно, А более правдоподобно. Будем рассматривать схемы в применении к выводу, основанному на правилах:

if A then В with г,

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

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

tmx(a, г) = Ь,

(1.2)

True(i) tmx(a, г) = а,

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

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

Правило вывода (1.1) соответствует продукционному правилу if В then A with i = более правдоподобно. Таким образом, определение операции учета влияния i на о.у. следствия правила и операции комбинирования приводит к получению схемы о.у. в рамках схемы правдоподобного умозаключения.

Список литературы диссертационного исследования кандидат наук Моросанова, Наталья Александровна, 2013 год

Литература

1. Abidi M. A., Gonzalez R. C. Data fusion in robotics and machine intelligence. San Diego, CA, USA: Academic Press Professional, Inc., 1992.

2. Baroni P., Vicig P. An uncertainty interchange format with imprecise probabilities // International journal of approximate reasoning. 2005. T. 40, № 3. C. 147-180.

3. Bcrgmann M. An introduction to many-valued and fuzzy logic: semantics, algebras, and derivation systems. Cambridge University Press, 2008.

4. Bloch I. Information combination operators for data fusion: A comparative review with classification // Systems, Man and Cybernetics, Part A: Systems and Humans. IEEE Tiansactions on. 1996. T. 26, C. 52-67.

5. Brown W. L. Topological conjugations are not constructable // ArXiv e-prints. 2013.

6. Buchanan B.G., Shortliffe E.H. Rule Based Expert Systems: The Mycin Experiments of the Stanford Heuristic Programming Project (The Addison-Wesley series in artificial intelligence). Addison-Wesley Longman Publishing Co., Inc., 1984.

7. 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.

8. Clifford A. II. Totally ordered commutative semigroups // Bulletin of the American Mathematical Society. 1958. T. 64, № 6. C. 305 316.

9. Cobb B.R., Shenoy P.P. On the plausibility transformation method for translating belief function models to probability models // International Journal of Approximate Reasoning. 2006. T. 41, X» 3. C. 314 330.

10. Cordón O., Herrera F., Peregrin A. Characterisation of Implication Operators in Fuzzy Rule Based Systems from Basic Properties // Proc. of the 9th Congr. sobre Tecnologías y Lógica Fuzzy. 1999. С. 163-166.

11. Destercke S., Dubois D. Idempotent merging of belief functions: Extending the minimum rule of possibility theory /7 Workshop on the Theory on Belief Functions (WTBF 2010). 2010.

12. Dubois D. Uncertainty theories: a unified view // IEEE Cybernetic Systems Conference, Dublin, Ireland. 2007. C. 4 9.

13. Probability-possibility transformations, triangular fuzzy sets and probabilistic inequalities / D. Dubois, L. Foulloy, G. Mauris [и др.] // Reliable Computing. 2004. T. 10. c. 2004.

14. Dubois D., Prade H. On the combination of uncertain or imprecise pieces of information in rule-based systems—A discussion in the framework of possibility theory // International Journal of approximate Reasoning. 1988. T. 2, N5 1. C. 65-87.

15. Duda R., Gaschnig J., Hart P. Model design in the Prospector consultant system for mineral exploration // Expert systems in the microelectronic age. 1979. C. 153-167.

16. Subjective Bayesian methods for rule-based inference systems / R.O. Duda, Ilart, P.E [и др.] // Proceedings of the June 7-10, 1976, national computer conference and exposition / ACM. 1976. C. 1075-1082.

17. Fu L. M., Shortliffc E.H. The application of certainty factors to neural computing for rule discovery // Neural Networks, IEEE Transactions on. 2000. T. 11, № 3. C. 647-657.

18. Geer J.F., Klir G.J. A mathematical analysis of information-preserving transformations between probabilistic and possibilistic formulations of uncertainty // International Journal of General System. 1992. T. 20, JV* 2. C. 143-176.

19. Gottwald Siegfried. Many-Valued Logic // The Stanford Encyclopedia of Philosophy / под ред. Edward N. Zalta. 2010.

20. Grosof B. Evidential confirmation as transformed probability // Uncertainty in Artificial Intelligence. 1986. C. 153-166.

21. Grzymala-Busse J.W. Managing uncertainty in expert systems. Springer, 1991. T. 143.

22. Hajek P., Valdes J.J. An analysis of MYCIN-like expert systems // Mathware к soft computing. 2008. Т. 1, № 1. C. 45-68.

23. Hatzilygeroudis I., Kovas K. A Tool for Automatic Creation of Rule-Based Expert Systems with CFs // Artificial Intelligence Applications and Innovations. Springer, 2010. C. 195-202.

24. Heckerrnan D. Readings in uncertain reasoning / под ред. G. Shafer, J. Pearl. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1990. C. 298-312.

25. Hendler J.A. Expert systems: the user interface. Ablex Pub, 1988.

26. Jafari Sh., Shabaninia F., Xava P.A. Xeural network algorithms for tuning of fuzzy certainty factor expert systems // Automation Congress, 2002 Proceedings of the 5th Biannual World 7 IEEE. T. 13. 2002. C. 95-100.

27. Johnson X.L., Kotz S. Axiomatic approaches to formulas for combining likelihoods or evidence // Journal of Statistical Computation and Simulation. 1989. T. 31, JVL> 1. C. 49 54.

28. Karabatak M., Ince M.C. An expert system for detection of breast cancer based on association rules and neural network // Expert Systems with Applications. 2009. T. 36, № 2. C. 3465-3469.

29. Klir G.J. On fuzzy-set interpretation of possibility theory // Fuzzy sets and systems. 1999. T. 108, № 3. C. 263-273.

30. Lucas C., Araabi B.X. Generalization of the Dempster-Shafer theory: a fuzzy-valued measure // Fuzzy Systems, IEEE Transactions on. 1999. T. 7, JV° 3. C. 255-270.

31. Luo X., Zhang C., Leung H. Information sharing between heterogeneous uncertain reasoning models in a multi-agent environment: a case study // International journal of approximate reasoning. 2001. T. 27, № 1. C. 27-59.

32. Mendel J.M. Fuzzy logic systems for engineering: a tutorial // Proceedings of the IEEE. 1995. T. 83, № 3. C. 345-377.

33. Mizraji E. Vector logic: a natural algebraic representation of the fundamental logical gates ' Journal of Logic and Computation. 2008. T. 18, № 1. C. 97-121.

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

35. Morris P.A. An axiomatic approach to expert resolution // Management Science. 1983. T. 29, № 1. C. 24-32.

36. Ng K.C., Abramson B. Uncertainty management in expert systems // Icee Expert. 1990. T. 5, № 2. C. 29-48.

37. Pawlak Z. Rough sets and intelligent data analysis // Information sciences. 2002. T. 147, JV® 1. C. 1-12.

38. Sentz K., Ferson S. Combination of evidence in Dempster-Shafer theory. Citeseer, 2002. T. 4015.

39. Shafer G. A mathematical theory of evidence. Princeton university press Princeton, 1976. T. 1.

40. Siler W., Buckley J.J. Fuzzy expert systems and fuzzy reasoning. Wiley-Interscience, 2004.

41. Takagi Т., Sugeno M. Fuzzy identification of systems and its applications to modeling and control // Systems, Man and Cybernetics, IEEE Transactions on. 1985. JV® 1. C. 116-132.

42. Yamauchi Y., Mukaidono M. Probabilistic inference and Bayesian theorem based on logical implication // New Directions in Rough Sets, Data Mining, and Granular-Soft Computing. 1999. C. 334-342.

43. Zadeh L.A. Fuzzy logic // Computer. 1988. T. 21, № 4. C. 83-93.

44. Zimmermann H.J. An application-oriented view of modeling uncertainty // European Journal of Operational Research. 2000. T. 122, № 2. C. 190-198.

45. Zimmermann H.J. Dynamic fuzzy data analysis and uncertainty modeling in engineering /7 Intelligent Techniques and Soft Computing for Nuclear Science and Engineering: Proceedings of the 4th International FLINS Conference, Bruges, Belgium, August 28-30, 2000 / World Scientific. 2000. c. 3.

46. Аршинский JI.В. Векторные логики: основания, концепции, модели: монография. 2007.

47. Батыршин И.З. Основные операции нечеткой логики и их обобщения. Казань: Отечество. 2001.

48. Мальцев А.И. Алгебраические системы. Издательство «Наука», 1970.

49. Махортов С.Д. Математические основы искусственного интеллекта. М.: Изд.МЦНМО, 2009.

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

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

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

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

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

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

5G. Осипов Г.С. Лекции по искусственному интеллекту. М.: Книжный дом "ЛИБРО-КОМ 2012.

57. Пойа Дж. Математика и правдоподобные рассуждения. М.:Наука, 1975.

58. Соловьев С.Ю., Соловьева Г.М. Вопросы применения метода альтернатив для представления знаний // Изв. АН СССР, Техн. кибернетика. 1987. № 5. С. 80 -82.

59. Стефанюк В.Л. Некоторые аспекты теории экспертных систем // Известия АН СССР. Техническая кибернетика. 1987. № 2. С. 85-91.

60. Тулупьев А.Л., Николенко С.И., Сироткин A.B. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006.

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

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

В данном приложении приводится реализация алгоритма построения биективной трансформации по паре операций (см. алгоритм 2 в разделе 3.2.1) и алгоритма построения трансформации схемы Шортлиффа по примерам продукций (см. алгоритм 3 в разделе 3.2.2).

Входными данными алгоритма 2 являются списки значений х = [х\... .т„) и у = (у1...г/п), где точки хг и у3 упорядочены по возрастанию, a [xi,x-„] и [y\,yri] — множества значений оценок уверенности X и У для двух схем оценки уверенности, соответственно. Также заданы две операции (ж1, ж2) и (¡(у1, у2), соответствие которых типа (2.3) задает искомую трансформацию.

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

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

Предикат is_not_plateau подсчитывает количество пар соседних точек уь у2 в списке, упорядоченном по возрастанию х, для которых модуль разности \yi — у2\ не превышает заранее заданного порога (см. в разделе 3.2.1), и отношение этого числа к числу всех точек у, которое, в свою очередь, должно быть меньше £q.

Предикат diff вычисляет значение погрешности (3.21), которое должно быть меньше заданного порога е4.

Вспомогательная функция f ind_zero служит для выбора пары точек ж* и у*, наиболее близких к нейтральным элементам операций с и d, из списков ж = (хг... хп) и у = (уг ... уп).

Результатом работы алгоритма являются два списка list_x и list_y, задающие приближение искомой трансформации. Изначально listx = (xi,x*,xn) и listy = (yi,y*,yn)-

Пополнение списков list_x и list_y происходит с помощью функций sequence и add_sequence.

Функция sequence получает в качестве параметров пару точек (жг, у3) и получает соответствующие последовательности.

Функция add_sequence добавляет полученные последовательности в списки Из1;_х и Иэ^у. При этом сохраняется порядок возрастания для точек ,т и проверяется истинность всех предикатов.

На рис.А.1 приведена схема работы алгоритма 2.

Рис. А.1. Поиск трансформации по паре операций

Вход

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

Входными данными алгоритма являются список троек значений (х.у.г), а также граничные значения х_пип и х_тах. Решение задачи строится в предположении, что функция g(x,y), для которой верно g(x,y)=z, является образом операции ослабления Ьтхзн(х,У) = ху.

КХУ) = д(Цх),Ну)), а Н(х) монотонно возрастающая функция.

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

1. Найти нейтральный элемент ж*, такой, что h(0) = х*. Для поиска нейтрального элемента используется вспомогательная функция find_zero. Для этого все пары (х,у) размечаются следующим образом:

• если г < min(x, у), то х > х* и у > х*;

• если г > тах(ж, у), то х < х* и у < х*;

• если ипп(ж,у) < 2 < тах(ж,у), то min(i, у) < х* и тах(ж,у) > х*.

Далее пусть х\ = шах ж, ж2 = min ж. Таким образом, [ж!,ж2] — отрезок, содержащий

х<х* х>х*

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

2. Добавить к тройкам значений новые тройки типа (х*,х,х*) и (х,х*,х*), (х_тах,х,х) и (х,х_тах,х).

3. Построить приближение g(x,y)=z с помощью метода наименьших квадратов по имеющимся тройкам значений.

4. Построить функцию h:

^Lxa2 — 2азж-"шж+а» х > 0 <12 0,2 ' —

g(h(—x),x_min), ж<0

5. Проверить погрешность на исходных тройках значений (x,y,z):

max z — h(hi(x) * h\(y))

где h\ определяется следующим образом: