Стартовая страница G l o s s a r y   C o m m a n d e r

Служба тематических толковых словарей

glossary.ru
park.glossary.ru
Служебная библиотека
 н а  п р а в а х  р е к л а м ы 

 Чтение: 1  | 2  | 3  | 4  | 5  | 6  | 7  | 8  | 9  | 10  | 11  | 12  | 13  | 14
 
МГУ имени М.В.Ломоносова

МОРОСАНОВА НАТАЛЬЯ АЛЕКСАНДРОВНА

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

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

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

Москва - 2013
Серьезное
чтение
на glossary.ru
Работа выполнена на кафедре алгоритмических языков факультета вычислительной математики и кибернетики
Московского государственного университета имени М.В.Ломоносова.
Научный руководитель:
доктор физико-математических наук, профессор Соловьев Сергей Юрьевич
Официальные оппоненты:
доктор физико-математических наук, профессор Михайлюк Михаил Васильевич
кандидат физико-математических наук, ст.н.с. Гинкул Геннадий Петрович
Ведущая организация: Вычислительный центр им.А.А.Дородницына РАН

Защита состоится 20 декабря 2013 г. в 11 часов на заседании диссертационного совета Д 501.001.44 при МГУ имени М.В. Ломоносова, расположенном по адресу: 119991, ГСП-1, Москва, Ленинские горы, МГУ, стр.52, 2-й учебный корпус, факультет ВМК, аудитория 685. С диссертацией можно ознакомиться в Фундаментальной библиотеке МГУ. С текстом автореферата можно ознакомиться на официальном сайте факультета ВМК МГУ имени М.В. Ломоносова http://www.cs.msu.su. Автореферат разослан 19 ноября 2013 г.

Ученый секретарь диссертационного совета      к.т.н. Костенко В.А.
Скачать.pdf
( 0.2 Mb )
Образец цитирования
Моросанова Н.А. Методы вычисления оценок уверенности формально построенных выводов: автореф. дис. : канд. физ.-мат. наук: 05.13.11 / Н.А.Моросанова. - Москва, 2013. - 14 с.

Общая характеристика работы
Актуальность темы
В системах искусственного интеллекта часто возникает необходимость обработки высказываний, заданных и/или полученных с некоторой неопределенностью. Источниками неопределенности могут выступать субъективные суждения экспертов, вероятностный характер и погрешности данных, а также неполнота информации.
Количественные характеристики неопределенности называются оценками уверенности (о.у.), если совокупность всевозможных о.у. образует упорядоченное множество с выделенными значениями True и, возможно, False. С содержательной точки зрения True есть о.у. истинного (точно установленного) высказывания, а False - о.у. ложного (точно опровергнутого) высказывания. Оценки уверенности приписываются исходным высказываниям и влияют на ход логического вывода, который, в конечном итоге, состоит в перевычислении некоторых о.у.
В конкретных приложениях оценки уверенности всегда сосуществуют с некоторым набором функций вычисления о.у. и правил управления вычислительным процессом. Упомянутые функции и правила существенно зависят от способа представления знаний и подхода к формализации о.у., а в совокупности они образуют самостоятельный интеллектуальный продукт - метод вычисления оценок уверенности. Диссертация посвящена изучению методов вычисления о.у. для продукционного представления знаний.
Известные в настоящее время методы вычисления о.у. подразделяются на вероятностные, логические и эвристические подвиды, отдельный подвид составляют методы, основанные на мерах неопределенности. Независимо от конкретных особенностей каждый метод идентифицируется так называемой формальной схемой. Схемой метода вычисления оценок уверенности (схемой о.у.) является тройка, состоящая из (а) множества значений оценок уверен3 ности, а также из (б) множества предикатов и (в) множества частично определенных операций над множеством (а).
Схемы о.у. позволяют теоретически сравнивать различные методы вычисления о.у., а также решать практически важные задачи совместного использования нескольких методов и выбора адекватного проблемной области метода.
Актуальность задачи совместного использования методов вычисления о.у. объясняется развитием распределенных систем и распространением различных подходов к вычислению о.у. Вариантами задачи совместного использования методов являются задача приведения методов к универсальному виду и задача согласования результатов логических выводов, построенных с использованием разных методов вычисления о.у. Общий подход к решению этих задач состоит в конструировании равноценных (в некотором смысле) преобразований схем о.у.
Интерес к задаче выбора адекватного метода вычисления о.у. вызван современной тенденцией к формализации субъективных знаний, предполагающей, в частности, построение персональной схемы о.у., которая соответствует некоторому экспертному знанию.
Цель работы
Целью работы является исследование схем о.у. и способов построения их преобразований применительно к задачам совместного использования нескольких схем о.у. и выбора схемы о.у.
Научная новизна
В диссертации разработан новый подход к исследованию методов вычисления о.у., основанный на формальном представлении методов в виде схем, допускающих преобразования посредством трансформаций. Выявлены два типа трансформаций и три производных от них бинарных отношения, позволяющие описывать известные и вновь установленные связи между методами вычисления оценок уверенности. Разработаны новые подходы к решению задач совместного использования и выбора схем о.у.
Практическая значимость
На основе разработанного подхода предложены и реализованы алгоритмы конструирования трансформаций для решения задач совместного использования схем о.у. и выбора схемы о.у. по известным примерам вывода. Реализованные алгоритмы позволяют решать задачи
  • cогласования о.у. высказываний в многоагентных системах, использующих разные схемы о.у.;
  • автоматизированного создания систем формального вывода на основе примеров вывода, в том числе ассоциативных правил, полученных методами 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 рисунков.
Краткое содержание диссертации
Во введении формулируются задачи диссертационного исследования и приводится краткий обзор работы.
В первой главе приводится определение схемы о.у.:
Известные методы вычисления о.у. и соответствующие им схемы о.у. рассматриваются по плану:
  • множество значений о.у.;
  • предикаты True(x), False(x), порядок на множестве значений о.у.;
  • логические операции: конъюнкция, дизъюнкция и отрицание;
  • операция учета о.у. продукционного правила (операция ослабления);
  • операция комбинирования.
В число рассмотренных схем о.у. входят
  • логические схемы, использующие нечеткую логику, векторную логику и логику с векторной семантикой;
  • схемы, основанные на мерах неопределенности и использующие байесовский подход, теорию свидетельств Демпстера-Шафера и теорию возможностей Дюбуа-Прада;
  • схема коэффициентов уверенности Шортлиффа.
Наличие большого числа общих черт у этих схем позволяет выдвинуть гипотезу о том, что преобразования схем о.у. пригодны для их сведения к универсальному виду. В поддержку такой гипотезы выступают известные из литературных источников исследования в области построения преобразований схем о.у. в рамках алгебраического и аксиоматического подходов, а также построенные преобразования для некоторых пар схем о.у. Аксиоматический подход1 состоит в постулировании набора желательных свойств операций. При этом соответствие операций с одинаковым набором свойств служит основой для построения преобразования. Алгебраический подход2 состоит в исследовании алгебраической системы, полученной из выбранной схемы путем сужения множества значений о.у. и выбора некоторых операций. Так, распространенным вариантом алгебраического подхода является исследование операции комбинирования как операции абелевой группы. Исследования по построению преобразований для пар схем о.у. носят фрагментарный характер и нуждаются в общем методологическом подходе.
Во второй главе приводится анализ схем о.у. и отношений между ними. Вводится понятие трансформации схем как набора отображений множества значений оценок уверенности, множеств предикатов и операций.

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

Частными случаями инъективной трансформации являются
  • расширение множества значений о.у.  XY;
  • добавление операций и предикатов  Pr1Pr2,  Op1Op2   при  X = Y.
Базовые типы трансформаций порождают три бинарных отношения - эквивалентность, обобщение и сопряжение:

Для выяснения типа отношений для пары схем о.у. необходимо построить соответствующие трансформации. С целью изучения способов построения трансформаций рассматриваются задачи:
Задача 1. Доопределение операции комбинирования.
Задача 2. Построение трансформации по заданной паре операций.
Задача 3. Построение трансформации по заданной паре схем о.у.
Задача 1  возникает при расширении множества значений о.у.:
  
использует в качестве входных данных
  – множества значений о.у. X и X ', а также
  – операцию комбинирования op на X, и
состоит в доопределении op на X '.
В диссертации описывается и обосновывается следующий конструктивный подход к решению этой задачи:
  1. предположить существование биективной трансформации
    G = < g, gpr, gop >, где S3 - подсхема некоторой известной схемы о.у.;
  2. построить трансформацию G для известной части доопределяемой операции (op на X);
  3. с помощью обратного отображения g-1 получить op ' на X '.
Задача 2  возникает при выявлении сопоставленных операций,
использует в качестве входных данных
  – множества значений о.у. X и Y и, соответственно,
  – операции f1 и f2 и
состоит в построении отображения hX → Y,
задающего биективную трансформацию

h(f1(x)) = f2(h(x)) (2)
Для решения этой задачи требуется решение уравнения (2), что в общем случае является алгоритмически неразрешимой задачей3. Поэтому построение трансформации по паре сопоставленных операций является нетривиальной задачей, требующей конструктивного доказательства существования такой трансформации в каждом конкретном случае. Построение биективных трансформаций на основе пары сопоставленных операций позволяет, во-первых, согласовать оценки уверенности высказываний в системах, использующих разные схемы о.у., во-вторых, создать основу для дальнейшего изучения вопроса существования трансформации для пары схем о.у.
Задача 3  возникает при построении биективной трансформации,
использует в качестве входных данных две схемы о.у.
   S1 = (X, Pr1, Pr1) и
   S2 = (Y, Pr2, Pr2) и
состоит в построении отображения hX → Y такого, что равенство (2) верно для всех пар операций.
В диссертации предлагается следующий подход к решению этой задачи: 1) построение трансформации для пары операций, схожих по смыслу, 2) проверка построенной трансформации для остальных пар операций. Построение таких трансформаций позволяет установить эквивалентность пары схем о.у.
Развитая в диссертации техника изучения трансформаций позволила доказать следующие утверждения:
Утверждение 1.  Схема, использующая логику с векторной семантикой, является обобщением схемы коэффициентов уверенности Шортлиффа.
Утверждение 2.  Схема, использующая логику с векторной семантикой, является обобщением схемы, использующей байесовские пары Демпстера4.
Утверждение 3.  Схема, использующая логику с векторной семантикой, сопряжена со схемой, использующей пары Демпстера4.
Последние три утверждения, а также 12 известных из литературы аналогичных результатов позволяют построить семантическую сеть, вершинами которой являются схемы о.у., а ребрами - предложенные бинарные отношения, а также дополнительное отношение заимствования операций из одной схемы другой схемой. Построенная семантическая сеть систематизирует известные схемы о.у. и позволяет заключить, что
  1. Трансформации схем перспективны для решения задачи совместного использования схем, имеющих большое число общих операций5.
  2. Систематизация схем предоставляет возможность выбора схемы о.у. с фиксированными свойствами.
  3. Для решения нетривиальной, в общем случае, задачи построения трансформации требуется вспомогательный программный инструментарий, поддерживающий частные приемы построения трансформаций.
В третьей главе диссертации рассматриваются программные средства автоматизированного построения трансформаций и вопросы использования трансформаций в логическом выводе.
Автоматизированное построение трансформаций основано на решении уравнений вида (2). Поскольку в общем случае задача алгоритмически неразрешима, то рассматривается частный случай ассоциативных и коммутативных операций f1 и f2, а также используется построение численного приближения искомого отображения h. В зависимости от исходных данных рассматриваются два случая задачи автоматизированного построения трансформаций.
Первый случай заключается в совместном использовании систем с различными схемами о.у., а задача сводится к построению трансформации по паре сопоставленных операций различных схем о.у. (см. Задача 2). Заметим, что обычно речь идет об обмене и накоплении информации, поэтому выбирается пара операций комбинирования. В первом случае для решения уравнения (2) в диссертации предлагается алгоритм построения приближения отображения h.
Второй случай заключается в выборе схемы о.у., адекватной заданным примерам вывода. Исходными данными здесь выступают несколько правил вывода с конкретными значениями оценок уверенности. Считается, что данные могут быть получены от экспертов в проблемной области. Выбор схемы о.у. осуществляется среди схем о.у., эквивалентных схеме коэффициентов уверенности Шортлиффа. Во втором случае построение соответствующей биективной трансформации основано на решении уравнения (2) для пары ассоциативных и коммутативных операций ослабления.
Использование трансформаций схем о.у. в логическом выводе позволяет решать задачу согласования результатов выводов. Поскольку трансформации преобразуют, в том числе, оценки уверенности, а вывод состоит в перевычислении оценок уверенности, то трансформации позволяют сравнивать оценки уверенности выводов, полученных с помощью алгоритмов в различных схемах о.у., а также получать "образы" алгоритмов вывода. Так, в диссертации приводится и обосновывается обобщенный алгоритм вывода в системах альтернатив, использующий логическую схему с векторной семантикой.
В заключении диссертации приводятся основные результаты работы.
В приложениях излагаются особенности программной реализации алгоритмов построения трансформаций (приложение А), а также алгоритм вывода в системах альтернатив (приложение Б). Здесь же приводятся фрагменты реализации алгоритмов на языке Lisp и общая структура программного средства для решения задач построения трансформаций.

Основные результаты
  1. На основе предложенного формализма трансформаций систематизированы методы вычисления оценок уверенности и обоснованы подходы к решению задач совместного использования и выбора методов.
  2. Разработаны алгоритмы автоматизированного построения трансформаций по паре операций и по примерам вывода.
  3. Предложенные алгоритмы реализованы в виде программных средств для использования в прикладных интеллектуальных системах.
Публикации по теме диссертации
  1. Моросанова Н.А, Соловьев С.Ю. Формальные свойства схемы Шортлиффа // Управление большими системами. 2012. Т. 36. С. 5-38.
    www.park.glossary.ru/serios/read_17.php
  2. Моросанова Н.А. Нестрогий вывод в системах альтернатив // Информационные процессы. 2011. Т. 11, No. 3. С. 394-412.
    www.park.glossary.ru/serios/read_16.php
  3. Моросанова Н.А. Об одном алгоритме нестрогого вывода на основе логик с векторной семантикой // Сб. Программные системы и инструменты. 2011. No.12. С. 139-149.
  4. Моросанова Н.А. Схемы оценки уверенности в экспертных системах // Сборник статей молодых ученых факультета ВМК МГУ. 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 Conference on Intelligent Information Systems, ed. C.Gaindric, S.Cojocaru, Chisinau: Institute of Mathematics and Computer Science. 2013. С. 227-230.

1 Cheng Y., Kashyap R.L. An axiomatic approach for combining evidence from a variety of sources //Journal of Intelligent & Robotic Systems. 1988. Т. 1, No.1. С. 17-33.
2 Hajek P., Vald.es J.J. An analysis of MYCIN-like expert systems // Mathware & soft computing. 2008. Т.1, No.1. С. 45-68.
3 Brown Westrick L. Topological Conjugations are Not Constructable. 2013. http://arxiv.org/abs/1303.2244
4 Частные случаи теории Демпстера-Шафера, когда множество гипотез состоит из одной гипотезы и ее отрицания.
5 В частности, схема коэффициентов уверенности Шортлиффа связана отношениями с 9 известными схемами о.у.


П|р|о|д|о|л|ж|е|н|и|е ►



Copyright ©
2000-2014
Web-and-Press


webadmin@glossary.ru