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

Введение к работе

Актуальность

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

Цели работы

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

Задачи, решению которых посвящены исследования:

1. разработать методы и средства автоматизации построения импликативных теорий на примерах:

свойств функций на конечных множествах;

алгебраических тождеств;

2. разработать методы и средства нахождения ошибок в бинарных данных с помощью импликативных зависимостей.

Объектом исследования являются импликативные зависимости.

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

В соответствии с паспортом специальности 05.13.17 "Теоретические основы информатики" работа включает в себя

исследования процессов создания, накопления и обработки информации; методов преобразования информации в данные и знания;

исследования методов преобразования информации в данные и знания;

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

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

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

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

2. Разработка и исследование моделей и алгоритмов анализа дан-

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация

Результаты проведенных исследований докладывались на семинаре кафедры анализа данных и искусственного интеллекта НИУ-ВШЭ (с 2010г. по 2013г., неоднократно), на семинаре института алгебры Политехнического Университета Дрездена (с 2011г. по 2013г., неоднократно) и на семинаре "Проблемы современных информационно-вычислительных систем" на механико-математическом факультете МГУ имени М.В.Ломоносова (2013г.). Результаты докладывались на следующих международных семинарах и конференциях:

1. 19-21.10.2010 Concept Lattices and Their Applications 2010,
Sevilla, Spain

http: //www. glc. us . es/cla2010/;

2. 23-25.02.2011 inFormal Concept Analysis Workshop, Dresden,
Germany

fakultaet_mathematik_und_naturwissenschaften/ fachrichtung_mathematik/institute/algebra/ conferences/2011 if ca;

3. 11-13.07.2012 European PhD Program in Computional Logic
Workshop 2012, Dresden, Germany

;

4. 1-3.07.2013 European PhD Program in Computional Logic
Workshop 2013, Dresden, Germany

5. 2.05.2013 IPID Doktorandtentreffen, Cologne, Germany internationalisierung/ipid/13303.de. html

   28.06.2013 International Seminar, Dresden Germany

   fakultaet_mathematik_und_naturwissenschaften/ fachrichtung_mathematik/institute/algebra/ veranstaltungen;

   7. 28.08.2012 What can FCA do for Artificial Intelligence? 2012,
   Montpellier, France

   http: //f ca4ai . hse . ru/2012/;

   8. 11-14.10.2012 Concept Lattices and Their Applications 2012,
   Malaga, Spain

   http: //www. matap. lima. es/cla2012/CLA2012/Welcome. html;

   9. 24.03.2013 Formal Concept Analysis meets Information Retrieval
   2013, Moscow, Russia

   http: //f cair. hse. ru/;

   10. 03.08.2013 What can FCA do for Artificial Intelligence? 2013, Beijing, China http: //f ca4ai . hse . ru/2013.

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

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

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

   Построение аппроксимации многомерных зависимостей по выборкам с факторным планомБеляев Михаил Геннадьевич

   

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

   

   Статический анализ кода для автоматизированного обнаружения ошибок при переносе программ на 64-битные платформыРыжков, Евгений Александрович

   

   Синтез и анализ алгоритмов распознавания и оценки параметров изображений групповых точечных объектов в условиях ошибок обнаружения отдельных отметок Евдокимов Алексей Олегович

   

   Математическое обеспечение оперативного обнаружения ошибок потока управления на основе обработки графов большой размерности --Рожков Максим Владимирович

   Метод обнаружения ошибок при работе с памятью на статическом этапе отладки программного обеспеченияТетерев, Михаил Александрович

   

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

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

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

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