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

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

МОРОСИН ОЛЕГ ЛЕОНИДОВИЧ

ИССЛЕДОВАНИЕ И РАЗРАБОТКА СИСТЕМЫ АРГУМЕНТАЦИИ НА ОСНОВЕ ПЕРЕСМАТРИВАЕМЫХ РАССУЖДЕНИЙ ДЛЯ ЗАДАЧИ ОБОБЩЕНИЯ

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

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

16 СЕН 2015

Москва - 2015

005562232

Работа выполнена на кафедре Прикладной математики ФГБОУ ВО НИУ «МЭИ»

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

доктор технических наук, профессор кафедры Прикладной математики ФГБОУ ВО НИУ «МЭИ»

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

Ведущая организация:

Кузнецов Сергей Олегович

доктор технических наук, профессор, руководитель департамента анализа данных и искусственного интеллекта НИУ ВШЭ.

Аверкин Алексей Николаевич

кандидат физико-математических наук, ведущий научный сотрудник Вычислительного центра.им. A.A. Дородницына РАН (ВЦ РАН).

Федеральное государственное бюджетное учреждение науки Институт проблем управления им. В. А. Трапезникова РАН.

Защита состоится «16» октября 2015 г. в 14 час. 00 мин на заседании диссертационного совета Д212.157.01 при ФГБОУ ВО НИУ «МЭИ» по адресу: 111250, Москва, Красноказарменная ул., 13, корпус М, ауд. М-704.

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВО НИУ «МЭИ» и на сайте www.mpei.ru.

Отзывы в двух экземплярах, заверенные печатью, просьба направлять по адресу: 111250, Москва, Красноказарменная ул., д. 14, Ученый совет ФГБОУ ВПО «НИУ «МЭИ».

Автореферат разослан «07» сентября 2015 г.

Ученый секретарь

диссертационного совета Д 212.157.01 к.т.н., доцент

М.В. Фомина

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

Актуальность темы исследований.

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

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

О важности наличия моделей, методов и средств способных моделировать немонотонные рассуждения и работать с неполными и противоречивыми данными и знаниями, говорится во многих работах в области ИИ (см., например, работы Д.А. Поспелова, О.М. Аншакова, В.Н. Вагина, А.П. Еремеева, О.П. Кузнецова, С.О. Кузнецова, Г.С. Осипова, В.К. Финна, И.Б. Фоминых, Ф. Беснарда, А. Бонадренко, Г. Врейсвика, Б. Гантера, П. Данга, Д.

Мак-Дермотта, А. Какаса, Д. Нута, Г. Праккена, Д. Поллака, Г. Симари, А. Хантера, и др.).

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

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

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

1. Исследование существующих методов и алгоритмов теории абстрактной аргументации.

2. Исследование немонотонных систем вывода, а именно теории пересматриваемых рассуждений.

3.Разработка методов и алгоритмов применения пересматриваемых правил вывода для логики предикатов первого порядка (ЛППП).

4. Разработка алгоритмов обнаружения конфликтов для ЛППП.

5. Разработка алгоритма вычисления степеней обоснования для аргументов.

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

7. Исследование возможности применения методов аргументации в машинном обучении.

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

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

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

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

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

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

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

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

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

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

Практическая значимость работы подтверждена использованием полученных результатов в системах электронной коммерции ООО «Зеленый квадрат» и в учебном процессе в ФГБОУ ВПО «НИУ «МЭИ» при изучении дисциплины "Математическая логика", о чём имеются акты о внедрении.

Реализация результатов.

Результаты диссертационной работы вошли в отчёты по НИР, выполняемым кафедрой ПМ и ВТ по грантам РФФИ № 11-07-00038-а "Исследование и разработка методов и инструментальных средств достоверного и правдоподобного вывода в интеллектуальных системах поддержки принятия решений", № 14-07-00862 "Методы и инструментальные средства интеллектуального анализа данных в системах поддержки принятия решений", № 15-01-05567 "Исследование и разработка методов и алгоритмов индуктивного формирования понятий в интеллектуальных системах поддержки принятия решений", в отчет по НИР в рамках проектной части государственного задания № 2.737.2014/К, а также отчёты по НИР, выполняемыми по гранту "У.М.Н.И.К.".

На разработанный в диссертационной работе программный комплекс выдано свидетельство о государственной регистрации программы для ЭВМ №2015610956 "Система аргументации на основе пересматриваемых рассуждений" от 21.01.2015г.

Апробация работы.

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

1)доклад «Методы и алгоритмы нахождения степеней обоснования в системах аргументации» на международной конференции «Открытые семантические технологии проектирования интеллектуальных систем» (OSTIS-2014), Минск, Беларусь;

2)доклад "Argumentation Approach and Learning Methods in Intelligent Decision Support Systems in the Presence of Inconsistent Data" на конференции ICCS 2014, Кэрнс, Австралия;

3)доклад "Обзор методов нахождения степеней обоснования в системах аргументации" на 14-ой национальной конференции по искусственному интеллекту с международным участием КИИ-2014, Казань;

4)доклад "Modeling defeasible reasoning for argumentation" на международной конференции "BRICS-CCI'2013 - 1st BRICS Countries Congress on Computational Intelligence and CBIC'2013 - 11th Brazilian Congress on Computational Intelligence", 2013, Ресифе, Бразилия;

5)доклад на симпозиуме "SPITSE Symposium 2014. Workshops and Summerschool", Ильменау, Германия;

6)презентация на научной сессии НИЯУ МИФИ-2014, Москва.

Публикации. Основные результаты, полученные при выполнении диссертационной работы, опубликованы в 20 печатных работах, из них 4 - в журналах, относящихся к списку ВАКа.

Структура и объем работы. Диссертация состоит из введения, четырех гаав, заключения, списка использованной литературы (78 наименований) и приложений. Диссертация содержит 147 страниц машинописного текста (без приложений), 39 рисунков, 4 диаграммы.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Приводится анализ приемлемости аргументов. Под приемлемостью (acceptability) аргументов понимается механизм в системе аргументации,

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

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

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

• системы аргументации на основе модальных многозначных логик;

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

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

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

• сохраняется семантика задачи;

• обладает механизмом вывода новых аргументов из уже имеющихся;

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

Вводятся формальные определения аргументов и интересов в системах пересматриваемых рассуждений. Аргумент - пара, состоящая из заключения, являющегося правильно построенной формулой(ППФ) в Л111111, и множества посылок (тоже записанных в форме формул ЛППП). Записывать такие пары будем в следующем виде: р/Х, где р - заключение, а X - множество посылок. Под интересом понимается особый аргумент, достоверность которого необходимо обосновать в ходе монотонного и/или пересматриваемого вывода. Кроме того, определяется два типа конфликтов в системах пересматриваемых рассуждений — симметричная форма конфликта, называемая опровержением и несимметричная форма, называемая подрывом. Вводятся специальные правила вывода для формализации конфликтов типа подрыв: £=>(С @ В), которое означает, что аргумент Е подрывает пересматриваемую связь между аргументами С и И.

Определяется формальная постановка задачи аргументации, в виде кортежа <А,П Д>, где А - множество аргументов, П - множество интересов иЕ-множество правил вывода.

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

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

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

Рассматривается возможность расширения аргументационной системы для поддержки ЛППП. Обнаружение конфликтов является одной из самых важных особенностей систем аргументации на основе пересматриваемых рассуждений. Основные сложности появляются из-за необходимости поддержки ЛППП. Если говорить про логику высказываний, то конфликт типа "опровержение" — это ситуация, когда одновременно существует два аргумента противоречащие друг другу, т.е. имеется аргументы Ах\рх1Хх и А2р2/Х2, такие, чтор\=^рг и ХхоХг или Х1 £ Х\, где -1 - отрицание. Однако, для ЛППП все несколько сложнее. Автором предлагается метод, основанный на применении механизма унификации для обнаружения конфликтов. Говорят, что унификатор и={г\!х\, Ь1х2..Лп1хп), где ^ - терм, х, - переменная, унифицирует два выражения Щи Ж2, если Ж2*и, где Ж^ии \Уг-и- выражения, полученные заменой в

и Ж2 всех вхождений переменной х1 (1=1.....п) на терм Ц. Для конфликтов обоих

типов сформулированы следующие правила их обнаружения:

А) два аргумента А \:рх/Хх и Аг:р1/Хг вступают в конфликт типа "опровержение",

если существует унификатор и такой, что:

1) ~р\'и=р2*1]\

2) ХгиеХ2'иилпх2-иехги.

Б) Аргумент А\ подрывает пересматриваемую связь между аргументами А2 и Аз, если:

1) Существует пересматриваемая связь между Аг и А3.

2) Существует подрывающее правило Е=>(С @ D) и существуют унификаторы U\ и С/2 такие, что:

a) E'Ui=A\'U\,

b) (с-ио -и2=л2 • и2- ■

c) (D-Ui) 'U2=A3 • U2.

Приведем разработанный алгоритм на основе указанного выше метода._

Алгоритм 1. Алгоритм нахождения конфликтов между аргументами для ЛППП. Входные данные: Граф вывода, список подрывающих следствий undercut_rules. Выходные данные: Измененный граф вывода с конфликтами. Шаг 1. Для каждого аргумента Argi = А\/Х\ проверить не существует ли Arg2 = А2/Х2, такой, что для А\ и -тА2 существует унификатор U и X\*UeX2*U или Х2*UeX\• U. Если такой унификатор существует, добавить между Arg\ и Arg2 в граф вывода конфликт типа "опровержение"

Шаг 2. Для каждого подрывающего правила вида p=>(q@r) из undercut_ruîes выполнить шаг 3.

Шаг 3. Взять левую часть правила - р. Для каждого аргумента Arg = А*/Х, проверить существует ли унификатор Uieß для выражений А* и р. Шаг 4. Для тех аргументов Arg, которые унифицируемы с левой частью подрывающего правила выполнить следующие шаги:

Шаг 4.1. Применить унификатор 1]\ф к g и г (qu=q» Uufi и ru=r» Uuß). Шаг 4.2. Составить массив X=[{Aqi^ri} ,{Aq2,^4r2}. .,{Aq„Ar„}], состоящий из пар аргументов, соединённых пересматриваемым следствием. Для каждого элемента этого массива выполнить:

Шаг 4.2.1 Проверить существует ли унификатор Urighl для qu и Aqi. Если найденный унификатор так же является унификатором для ги и Агь добавить новый конфликт в граф вывода. Шаг 5. Изменить граф вывода в соответствии с найденными конфликтами на шагах 1-4 и завершить алгоритм._

Вычислительная сложность предложенного алгоритма для фиксированного множества аргументов А, состоящего из п элементов и множества подрывающих правил undercut_rules, состоящего из к элементов: + к * п * п/2) = О (fen2).

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

В классической постановке задачи аргументации ставится вопрос о приемлемости того или иного предположения относительно заданных посылок. Ответ на такой вопрос - всегда качественный, т.е. допустим или нет. Для некоторых задач (в частности в задаче обобщения, которая будет рассмотрена в главе 3 данной работы) требуется получить не только качественный ответ, но и количественный - а именно насколько достоверен тот или иной аргумент. Для решения этой задачи предлагается использовать механизм степеней обоснования (degrees of justification). Степени обоснования будем обозначать функцией Jus: А—^>[0,1]. Если степень обоснования аргумента Jus(Al) = 0, то

говорят, что At - полностью поражённый аргумент; в случае, если Jus(Ai) - 1 -аргумент А, является полностью достоверным, в противных случаях, когда (XJus(Ai)<l, говорят, что аргумент At достоверен (обоснован) с некоторой мерой уверенности. Степени обоснования могут быть двух типов:

1) степени обоснования исходных аргументов;

2) степени обоснования пересматриваемых правил.

Первый тип степеней обоснования присваивается каждому исходному аргументу, и представляет собой оценку достоверности источника, из которого получен данный аргумент. Второй тип степеней обоснования присваивается пересматриваемыми правилами, которые также могут нести в себе числовую оценку. Будем обозначать степень пересматриваемых правил аналогично - Jus: [0,1]. На значение функции Jus (А) оказывает влияние два фактора - дерево вывода аргумента (т.е. степень обоснования аргументов, которые использовались в выводе данного аргумента) и конфликты с другими аргументами. Для удобства рассмотрим эти два фактора раздельно: Jusanc(A) -унаследованная степень обоснования и JusC0„(A) — на сколько конфликт подрывает обоснование аргумента А,-. Унаследованная степень обоснования -это мера, насколько обоснованы аргументы, участвующие в выводе аргумента А^ Очевидно, что если для доказательства некоторого аргумента используются "сомнительные" аргументы, то достоверность такого аргумента будет невысока. Предлагается использовать так называемый принцип "слабейшей связи", который означает, что унаследованная степень обоснования некоторого аргумента А/, не может быть больше, чем степень обоснования самого "слабого" аргумента, участвовавшего в выводе этого аргумента А. Приведем

предложенный алгоритм нахождения степеней обоснования._

Алгоритм 2. Алгоритм нахождения степеней обоснования._

Входные данные: Аргумент q, аргумент ех, который не учитывается при определении степени обоснования аргумента q, граф вывода. Выходные данные: Граф вывода

Шаг 1. Если q - изначально заданный аргумент, то положить Jusanc(q) равным изначально заданной степени доверия для этого аргумента. В противном случае из всех Anci, являющихся непосредственным предком q (то есть q получается из Апс/ за один шаг), найти такой Anc_min, что его степень обоснования минимальна. Положить Jusmc(q) ' Jus(Anc_min ).

Шаг 2. Если аргумент q не имеет конфликтов, тогда положить Juscon(q)—0. В противном случае составить множество {Л/}, состоящее из аргументов, имеющих конфликт с q. Если параметр ех задан, исключить его из множества {А/}. Если к моменту вычисления Jus(q) среди А\ нет аргументов с неопределенной степенью обоснования, то среди них найти тот аргумент А_тах, у которого Jus(A_max) максимален. Положить Jusco„(q) =тах (Jus (A_max), Jusmc(ex)), выполнить Jus(ex), перейти к шагу 4. В противном случае (т.е. среди {А,} есть аргументы с неопределёнными степенями обоснования) выполнить шаг 3.

Шаг 3. Для каждого А/, для которого не определена степень обоснования выполнить:

Шаг 3.1. Если А1 имеет конфликт с ц, но аргумент д не имеет с ними конфликта (несимметричная форма конфликта) выполнить В противном случае

выполнить Яа^Льд), т.е. рассчитать без учета конфликта с д. Шаг 4. Положить Лю^) = ^апс(ц)- ^соп(д), если ^апс(д) > ^соп(ч)- В противном случае Уш^) =0.

Шаг 5. Изменить степени обоснования в графе вывода, завершить процедуру.

Вычислительная сложность предложенного алгоритма для фиксированного множества аргументов А, состоящего из п элементов и содержащее к конфликтов: 0(кп). Так как количество конфликтов мало по сравнению с количеством аргументов, то сложность приведённого алгоритма будет равна 0(п). Предложенные методы и алгоритмы легли в основу разработанной в ходе выполнения диссертационной работы системы пересматриваемых рассуждений и позволили реализовать следующие возможности системы: 1) способность выводить новые аргументы на основе уже имеющихся с использованием механизма натуральной дедукции; 2) производить пересматриваемый вывод и поиск конфликтов между аргументами в .11111111; 3) давать количественную оценку достоверности аргументов за счёт применения степеней обоснования.

В третьей главе рассмотрены способы применения методов аргументации для увеличения точности классификации объектов для задачи обобщения. Приведем классическую постановку задачи обобщения. Пусть 0={о 1, 02,..., "/Л - множество объектов (также называемых примерами), которые могут быть представлены в интеллектуальной системе Б. Каждый объект в 5 характеризуется К признаками (также называемые атрибутами)-. А={а\, а2,...,ах}- Множество А будем называть множеством атрибутов объекта. Множество допустимых значений атрибутов обозначим как Иот(а¡),

Вот(а2).....Оот(ак). Каждому объекту о1 е О, где 1 <i<NсопоставляетсяХ1 -

упорядоченный набор значений признаков, характеризующих данный объект: , 2к>, гдег^е йот(ак), 1 < к < К. Такое описание объекта называется признаковым описанием. Предполагается, что все объекты, принадлежащие О, характеризуются одинаковым набором признаков А, и могут быть представлены в виде таблицы. Такое описание объекта называется признаковым описанием. В качестве признаков объектов могут использоваться количественные, качественные либо шкалированные признаки. Не умаляя общности будем считать, что все объекты можно разделить на два класса -положительных примеров и контрпримеров понятия. Пусть V - множество положительных объектов - примеров формируемого понятия, и Ж - множество отрицательных объектов (контрпримеров понятия) в некоторой системе Б. Справедливо 0=Уи№, Уп1¥=0. При решении задачи обобщения принадлежность объекта к множеству Ж или V удобно задавать значением специального атрибута. Обозначим такой атрибут й и назовем его далее решением или решающим атрибутом. Атрибуты, входящие в А, называются информационными атрибутами. Таким образом, каждый объект из

обучающего множества задан значениями информационных атрибутов и значением решающего атрибута.

Построим U - конечное непустое подмножество множества объектов О такое, что U= LT и LT, где объекты Xfc.V называем положительными объектами, а объекты II а W - отрицательными объектами. Назовем U обучающей выборкой. Каждому объекту о,е U сопоставим упорядоченный набор значений признаков Xj=<z{, z{,...,z}K, d' >, dJ eDom(d), 1 <j<n. Здесь n — число примеров, вошедших в U.

На основании обучающей выборки надо построить правило, разделяющее положительные и отрицательные объекты обучающей выборки. Алгоритмы обобщения формируют решение в виде так называемого обобщенного понятия, представимого множеством правил вида "Если <условия>, То <искомое понятие>". Множество таких правил будем обозначать Е. Решающие правила являются корректными, если они в дальнейшем успешно распознают объекты, не вошедшие первоначально в обучающую выборку.

В качестве базовых средств построения обобщенных понятий рассматривается алгоритм С4.5, разработанный Куинланом и алгоритм GIRS, предложенный В.Н. Вагиным, Куликовым A.B. и Фоминой М.В.

Исследуется возможность улучшения качества работы обозначенных выше алгоритмов обобщения за счет применения методов аргументации. Критерием качества для построенного обобщённого понятия является успешность классификации тестовых выборок, то есть объектов, не входящих первоначально в обучающее множество С/.Базовая идея предлагаемого метода заключается в разбиении обучающей выборки U на два подмножества £/, и U2 таких, что Ui и U2 = U и раздельном обучение на каждом из подмножеств с последующим объединением полученных результатов обучения с помощью методов аргументации. Считается, что способ разбиения не детерминирован, однако, Ui п С/2=0, Uxr\ C/V0, Uin U2n lf*<Z, t/2n t/V0, |f/,| = \Щ

= |U|/2, если |U| - чётно, и |U1| = |U2|-l=l([U|) /2J в противном случае.

Пусть на обучающих выборках U{ и U2 построены наборы правил Ei={Ä7i, Rl2,..., Rlp}, и E2={Ä2i, R22,..., R2q}, где p и q количество таких правил. Правила из 1| и Е2 имеют вид "Если <условия>, То <искомое понятие>". Целью предлагаемого метода является построение множества К* включающее в себя правила из Mi и М2, такого, что оно не порождает конфликтов при классификации примеров из обучающей выборки U.

Классификационные правила, можно считать пересматриваемыми правилами вывода для аргументационной системы. Требуется определить, имеются ли конфликты между правилами Mi и М2, построенными на обучающих выборках Ui и U2. Для этого, необходимо для каждого объекта of={z[,z[,..., zlK} с решающим атрибутом dit принадлежащего обучающей выборке U=UiKjU2, проверить, порождает ли он конфликты на некотором наборе решающих правил KiuK2.

Предлагается следующая процедура проверки наличия конфликта в базе решающих правил М:

1) Для каждого значения информационного атрибута zj объекта

Xr<z{,zl2.....zlK> е Uи для каждого щ е А= <аи а2, ..., ак>, где 1 <j < К, А -

множество атрибутов, К - количество таких атрибутов), построить аргумент Argj следующего вида: Arg;. (af=z}).

2) Присвоить степень обоснования, равную 1, каждому Argj.

3) Подать полученное множество аргументов A ={Argj} и пересматриваемые правила вывода из Е на вход аргументационной системы.

4) Определить, имеются ли конфликты в полученной системе аргументации <А, {}, Е>.

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

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

становятся разрешимыми.__

Алгоритм 3. Алгоритм построения улучшенного множества

классификационных правил._

Входные данные: Множества правил Еь Ег, обучающее множество U. Выходные данные: Множество правил Е*.

Шаг 1. Задать всем правилам Rl,eRlt 1 < i < |Е,| и R2j£Е2, l<j <|К2| степень обоснования равную 1. Задать все правила вывода в качестве . пересматриваемых правил аргументационной системы. Шаг 2. Для каждого примера Xf=<z[,Z2,...,zlK, dl> из обучающей выборки выполнить следующие шаги:

Шаг 2.1. Подать на вход аргументационной системы в качестве начальных аргументов со степенью обоснования равной 1 следующие аргументы: Arg,: 0]=z[, Arg2: a2=Z2,-..y4rgK: a/c=zlK. Произвести логический вывод. Шаг 2.2. Если система обнаруживает конфликты, то есть в графе вывода имеются два конфликтующих аргумента Arg* и Arg** перейти к шагу 2.3, в противном случае - к шагу 2.1.

Шаг 2.3. Определить Arg =Arg*, Arg'~Arg**, если заключение аргумента Arg* совпадает со значение решающего атрибута d, иначе Arg' =Arg*, Arg+=Arg**.

Шаг 2.4. Получить два множества правил Ес+ and Ее" такие, что правила из Ес+ поддерживают аргумент Arg*, а Ее" поддерживают Arg'. Шаг 2.5. Степень обоснования правил, относящих рассматриваемый объект к правильному классу, следует увеличить. Для этого для всех RjS Мс+, 1 <j < |Ес+| пересчитаем значение функции Jus(Rj), по формуле:

Jus{R ) = ( 1 + Л), ifJus(Rj)i 1 + А) < V

( 1, в противном случае.

Шаг 2.6.2.6. Понизить степень обоснования правил, производящих неверную классификацию. Для этого пересчитать степень обоснования всех Ее", 1<у <_|Ес"| по формуле: (1-Д

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

* Значение Д выбирается в интервале (0,1) эмпирически в зависимости от количества правил вывода в 1&1 и Д&2. В экспериментах в главе 4 Л=0.05._

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

В четвёртой главе приводятся технические детали реализации программного средства, приводится описание инструментальных сред и библиотек, применяемых при разработке. Разработанная система содержит более 13000 строк кода на языке С#, более 90 классов и 500 методов.

Рис.1. Архитектура системы.

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

Дадим краткое описание каждого из блоков. Синтаксический анализатор производит преобразование исходных данных из текстового формата во внутреннее объектное представление. Приведена грамматика записи входных данных в форме Бэкуса-Наура.

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

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

Анализатор результатов связывает две указанные выше подсистемы, управляя очередью вывода.

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

Рассматриваются результаты применения методов аргументации в системах обобщения. Для оценки эффективности предложенного метода улучшения классификационных моделей в задаче обобщения была проведена серия экспериментов на следующих наборах данных из репозитория UCI калифорнийского университета информации и компьютерных наук (UCI Repository Information and Computer Science University of California): Использовались следующие тестовые наборы: Monk-2, Monks-3, Cars Evaluation, Breast Cancer. Для каждого набора данных сравнивались следующие эксперименты: GIRS - базовая стратегия, GIRS - стратегия объединения и GIRS - аргументационная стратегия. Приведем краткое описание каждой стратегии.

1) GIRS - базовая стратегия. Классический вариант применения алгоритма построения обобщенных понятий - обучение происходит на полной обучающей выборке U с помощью алгоритма GIRS. Классификация примеров из тестовой выборки происходит на полном множестве Е.

2) GIRS - стратегия объединения. В отличии от базовой стратегии, обучающее множество U делится на два подмножества U\ и иг. Проводится независимое обучение на каждом подмножестве и получаются два множества классификационных правил Ei и Е2. Результирующее классификационное множество К получается путем простого объединения Ej и Е2. Классификация проводится на объединённом множестве R. Стратегия объединения применялась, чтобы показать, что простое разделение обучающей выборки (без

применения аргументации), как правило приводит к ухудшению точности классификации.

3) С/Л? - аргументационная стратегия. Как и в стратегии объединения, алгоритм ОЖЭ применяется независимо к подмножествам II) и 112 и получаются два множества К] и Классификация проводится на множестве М* полученном с помощью метода, предложенного в диссертационной работе методе.

Сравнение точности классификации для трёх приведённых выше стратегий приведено на рис.2.

Monk-2 Monk-3 Cars Breast Cancer

* GER.S - базовая стратегия 74,31 94,44 89,7 79,91

5 GIRS - стратегия объединения 58,1 89,81 76,56 66,78

■ GIRS - аргументационная стратегия 82,17 98,14 92,41 85,66

Рис. 2. Точность классификации тестовых наборов данных. Обучающие выборки не содержат шума. Кроме того, рассмотрено влияние шума в обучающих выборках на работу предложенного алгоритма. Были проведены эксперименты с уровнем шума равным 5%, 10%, 15%, 20% и 25%. Приведём результаты эксперимента с шумом типа "искажение значения", который вносился в решающий атрибут обучающей выборки тестового набора данных Мопк-3. Зависимость точности классификации объектов от величины вносимого шума в решающий атрибут приведена на рис 3.

100 * 95 & 90 | 85 ■§• 80 1 75 й 70 % 65 60

H без шума шум 5% шум 10% шум 15% шум 20% шум 25%

GIRS - базовая стратегия 94,44 89,81 85,65 82,18 81,02 76,97

•••■'• GIRS - стратегия объединения 89,84 87,03 80,32 78,7 62,5 63,69

* GIRS - аргументационная стратегия 98,14 93,28 90,5 89,35 87,26 84,02

Рис. 3. Зависимость точности классификации от уровня шума.

Еще одним важным фактором, влияющим на точность классификации является размер обучающей выборки. В качестве исходных данных взят набор данных Breast Cancer. Авторы этого набора данных не формировали обучающую выборку отдельно, предполагая, что в качестве такой будет использоваться некоторое подмножество всей выборки. Рассматривалась обучающая выборка размером 10%, 15%, 20% и 25% и 40% от тестовой выборки. Обучающие выборки указанного размера выбирались каждый раз случайным образом из всего множества предоставленных для классификации объектов.

Зависимость точности классификации объектов от величины обучающей выборки приведена на рис 4.

Рис. 4. Зависимость точности классификации от размера обучающей выборки.

Приведённые результаты экспериментов показывают, что применение методов аргументации позволяет улучшить точность классификации на тестовых наборах данных. Так для задачи Мопк-2 точность повысилась на 10.57% и на 3.91% для задачи Monks-З. Для задачи Cars Evaluation точность повысилась на 3.2%. На тестовом наборе данных Breast Cancer увеличение точности составило 7.19%. В целом полученные результаты показывают, что предложенный в работе алгоритм, основанный на аргументационном подходе, позволяет улучшить точность классификации имеющихся алгоритмов обобщения на 5-6%. Применение методов аргументации для улучшения классификационных моделей в случае, когда обучающие выборки содержат зашумлённые данные, ещё более оправдано. Так, точность классификации при наличии шума для приведённых тестовых наборов данных удалось в среднем увеличить на 7—10%. Кроме того, из проведённых экспериментов делается

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

4. Выполнена программная реализация системы аргументации предложенных методов и алгоритмов. На разработанное программное обеспечение получено свидетельство о государственной регистрации программы для ЭВМ №2015610956 от 21.01.2015г.

5. Выполнено исследование и анализ методов машинного обучения для решения задачи обобщения. Предложен метод применения аргументации для улучшения классификационных моделей, получаемых методами индуктивного формирования понятий. В частности, были проведены эксперименты для алгоритмов индуктивного формирования понятий СТЯБ и С4.5 на тестовых наборах, данных из репозитория иС1. Полученные результаты показали эффективность предложенного метода.

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

7. Приведены результаты моделирования различных задач аргументации, не разрешимых методами классического логического вывода.

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

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Моюосин. О.Л. Аргументация с гтименением степеней обоснования в интеллектуальных системах // Известия Южного Федерального университета. Технические науки. -2014. - №7. С. 142-152.

2. Вагин В.Н., Моросин О.Л. Аргументация в интеллектуальных системах поддержки принятия решений // Информационно-измерительные и управляющие системы. - 2013. — №6.— Т.Н.- С. 29-36.

3. Вагин В.Н., Мороспн О.Л. Применение механизма степеней обоснования в системах аргументации // Вестник ростовского государственного университета путей сообщения — 2013. — № 3. — С. 43-50.

4. Вагин В.Н., Моросин О.Л. Программная реализация системы аргументации со степенями обоснования// Программные продукты и системы. - 2015. -№ 1. - С. 21-27.

5. Vagin V.N., Fomina M.V., Morosin O.L. Argumentation Approach and Learning Methods in Intelligent Decision Support Systems in the Presence of Inconsistent Data // Procedia Computer Science. - 2014. -Australia. - Vol. 29.-P. 1569-1579.

6. Vagin V.N., Morosin O.L. Modeling defeasible reasoning for argumentation // Proceedings of BRICS-CCI'2013 - 1st BRICS Countries Congress on Computational Intelligence and CBIC'2013 - 11th Brazilian Congress on Computational Intelligence, Brasil. - 2013. - IEEE. - P. 304-309.

7. Вагин B.H., Моросин О.Л. Исследование систем аргументации для пересматриваемых рассуждений //Интеллектуальные системы. Коллективная монография. Выпуск 6. / Под ред. В.М. Курейчика. -Ростов-на-Дону: Издательство ЮФУ. - 2013. С. - 163-178.

8. Моросин О.Л. Обзор основ теории пересматриваемых рассуждений. И Интеллектуальные системы и технологии: современное состояние и перспекти-вы. Сборник научных трудов Между-народной летней школы-семинара по искусственному интеллекту для студен-тов, аспирантов и молодых ученых (Тверь - Протасове, 1-6 июля 2011 г.). — Тверь: Издательство Тверского государственного технического университета. - 2011.-С. 129-136.

9. Вагин В.Н., Моросин О.Л. Пересматриваемые рассуждения в системах аргументации // Сборник научных трудов VI-й Международной научно-технической конференции по интегрированным моделям и мягким вычислениям в искусственном интеллекте (Коломна, 16-19 мая 2011). -М.: Физматлит, 2011,-Т.1. -С. 167-178.

10. Вагин В.Н., Моросин О.Л., Тихомирова И.В. Применение теории натуральной дедукции // Труды XIX международной научно-технической конференции Информационные средства и технологии. -М: Издательский дом МЭИ, 2011, - Т.2. -С. 246-253.

11. Вагин В.Н., Моросин О.Л. Система аргументации для логики предикатов первого порядка // Труды Тринадцатой национальной конференции по искусственному интеллекту с международным участием (КИИ-2012, 16-20 октября 2012 г., Белгород, Россия). -Белгород: Изд-во БГТУ, 2012. -Т.1. С. 34 - 42.

12. Вагин В.Н., Моросин O.JI. Применение теории аргументации для поиска конфликтов в базах знаний // Труды Конгресса по интеллектуальным системам и информационным технологиям. IS&IT 13 - М.: Физматлит, 2013.-Т. 1.-С. 132-140.

13. Моросин О.Л. Применение аргументации для работы с противоречивыми знаниями // Труды П-й Международной летней школы-семинара по искусственному интеллекту для студентов, аспирантов и молодых ученых (Тверь - Протасово, 1-5 июля 2013), -Тверь: Изд-во Тверского государственного технического университета, 2013. - С. 14-23.

14. Вагин В.Н., Моросин О.Л. Аргументация и поиск конфликтов в базах знаний // Труды XLI Международной конференции и XI Международной конференции молодых ученых Информационные технологии в науке, образовании, телекоммуникации и бизнесе. IT + SE'2013. Крым, Ялта-Гурзуф, 2013. - С. 151 - 154.

15. Моросин О.Л. Нахождение конфликтов в системе аргументации для логики предикатов первого порядка // Радиоэлектроника, электротехника и энергетика: Девятнадцатая междунар. науч.-техн. конф. студентов и аспирантов: Тез. докл. М.: Издательский дом МЭИ,

2013.-Т. 2.-С. 43.

16. Моросин О.Л. Методы и алгоритмы нахождения степеней обоснования в системах аргументации // Труды IV международной научно-технической конференции Открытые семантические технологии проектирования интеллектуальных систем - Open Semantic Technologies for Intelligent Systems OSTIS-2014 (Минск, 20-22 февраля 2014). - Минск: БГУИР,

2014.-С. 465-470.

17. Вагин В.Н., Моросин О.Л. Обзор методов нахождения степеней обоснования в системах аргументации / Труды Четырнадцатой национальной конференции по искусственному интеллекту с международным участием (КИИ-2014, Казань, Россия). -Казань: РИД Школа,2014.-Т.1.-С. 5-13.

18. Моросин О.Л. Вероятностные степени обоснования в системах аргументации // Нечеткие системы и мягкие вычисления (НСМВ-2014): труды Шестой всероссийской научно-практической конференции (г. Санкт-Петербург, 27-29 июня, 2014 г.). - в 2 т. СПб: Политехника-сервис, 2014. - Т. 1. - С. 465-470.

19. Деревянко А. В., Моросин О.Л. Обзор методов применения вероятностных степеней обоснования в системах абстрактной аргументации. // Труды ХХП международной научно-технической конференции Информационные средства и технологии. - М: Издательский дом МЭИ, 2014. - Т. 1. - С. 92-98.

20. Деревянко А. В., Моросин О.Л. Исследование и разработка системы абстрактной аргументации с вероятностными степенями обоснования// Труды V международной научно-технической конференции Открытые семантические технологии проектирования интеллектуальных систем -Open Semantic Technologies for Intelligent Systems OSTIS-2015 (Минск, 19-21 февраля 2015 года). - Минск: БГУИР, 2015. - С. 549-554.

Подписано в печать kOib Зак. ^¡и Тир. П. л. ^

Полиграфический центр МЭИ (ТУ)

Красноказарменная ул., д.13