Содержание к диссертации
Введение
Глава 1. Теория аргументации: обзор 13
1.1. Основные понятия и определения теории аргументации 13
1.2. Подходы к построению аргументационных систем 17
1.3 Системы абстрактной аргументации 18
1.3.1. Понятие конфликта и его свойства 20
1.3.2. Приемлемость аргументов в системах аргументации 24
1.4. Системы аргументации на основе многозначных логик 29
1.5. Системы аргументации на основе пересматриваемых рассуждений 31
1.5.1. Общий критерий адекватности для систем пересматриваемой аргументации 40
1.6 Выводы по главе 1. 40
Глава 2. Методы и алгоритмы аргументации на основе пересматриваемых рассуждений 42
2.1. Методы монотонного вывода в системах аргументации 42
2.1.1. Система монотонного вывода для логики высказываний 43
2.1.2 Расширение системы для поддержки логики предикатов первого порядка 50
2.2 Алгоритмы монотонного вывода 53
2.2.1. Алгоритм прямого вывода 53
2.2.2. Алгоритм обратного вывода 56
2.2.3. Алгоритм подтверждения интересов 58
2.3 Методы пересматриваемого вывода. Обоснование и поражение аргументов 59
2.3.1 Множественное поражение 61
2.3.2 Самопоражение 62
2.3.3 Поражение собственного базиса 63
2.3.4. Обнаружение конфликтов 65
2.3.5. Пересматриваемый вывод, основанный на системе флажков 68
2.4 Алгоритмы пересматриваемого вывода 70
2.4.1. Алгоритм применения пересматриваемых правил 70
2.4.2. Алгоритм поиска конфликтов 73
2.4.2. Алгоритм вычисления статусов поражения 75
2.5. Степени обоснования в системах аргументации 76
2.5.1. Алгоритм вычисления степеней обоснования. 81
2.6. Выводы по главе 2. 83
Глава 3. Применение системы аргументации для задачи обобщения 84
3.1. Постановка задачи обобщения 84
3.1.1. Алгоритм С4.5 88
3.1.2. Алгоритм GIRS 89
3.1.3 Модели шума 91
3.2. Применение аргументации для задачи обобщения 92
3.3. Формализация проблемы индуктивного формирования понятий в терминах
аргументации 93
3.4. Алгоритм индуктивного формирования понятий с применением аргументации 96
3.5. Выводы по главе 3. 99
Глава 4. Программная реализация системы аргументации и результаты экспериментов 101
4.1 Программная реализация системы пересматриваемых рассуждений 101
4.1.1 Структура разработанной системы 101
4.1.2. Системные требования и основные показатели 107
4.1.3 Программная реализация системы для решения задачи обобщения с применением аргументации 109
4.2. Результаты экспериментов по улучшению точности классификации для задачи обобщения с помощью реализованной системы 111
4.2.1 Методика проведения экспериментов 111
4.2.2. Тестовые наборы данных 113
4.2.3. Результаты экспериментов 115
4.2.4. Выводы по результатам проведённых экспериментов 120
4.3. Внедрение разработанной системы 121
4.3.1. Постановка задачи 121
4.3.2. Предложенное решение и реализация системы с помощью аргументации 122
4.4. Примеры моделирования и решения некоторых задач аргументации с помощью
реализованной системы 126
4.5. Выводы по главе 4 136
Заключение 138
Список литературы 141
- Системы абстрактной аргументации
- Алгоритм обратного вывода
- Алгоритм GIRS
- Структура разработанной системы
Системы абстрактной аргументации
Важным блоком современных систем поддержки принятия решений является база знаний. Такая база знаний должна содержать сведения об основных компонентах сложного технического объекта и правилах его функционирования. Очень часто база знаний, используемая в системах поддержки принятия решений содержит неточную, неполную, и даже противоречивую информацию. Классические методы логического вывода не применимы в таких ситуациях. Одним из способов обнаружения и разрешения внутренних противоречий является применение аргументации. Под аргументацией обычно понимают процесс построения предположений относительно некоторой анализируемой проблемы. Как правило этот процесс включает в себя обнаружение конфликтов и поиск путей их решения. В отличие от классической логики аргументация предполагает, что могут быть доводы как “за”, так и “против” некоего предположения.
В толковом словаре по искусственному интеллекту [32] дается следующее определение аргументации:
“Аргументация - процесс доказательства истинности утверждения с привлечением фактов, из которых следует истинность данного утверждения, или которое увеличивает уверенность в его истинности”. Заметим, что аргументация применяется не только для “доказательства истинности утверждения”, но и для анализа противоречивой ситуации и включает в себя поиск конфликтов и привлечение фактов, из которых следует ложность некоторого аргумента (так называемый поиск контраргументов [33]).
В.К. Финн использует понятие “аргументация” в трёх смыслах [21]. Согласно первому смыслу, рассматривается процесс принятия некоторого искомого предположения (или множества предположений). Этот процесс состоит в поиске высказываний и гипотез, релевантных этому предположению. С помощью найденных высказываний и гипотез определяется принимается искомое предположение или нет. Кроме того, имеется возможность установить причинно-следственные связи между найденными высказываниями. Аргументация в этом смысле есть некоторая составляющая творческого процесса, осуществляющая сбор релевантных знаний для организации рассуждений, целью которых является принятие или непринятие предположения.
Аргументация во втором смысле есть формальная процедура принятия искомого высказывания, основанная на анализе некоторого заданного множества аргументов, среди которых имеются аргументы как “за”, так и “против” данного высказывания. Целью такой процедуры является приписывание искомому высказыванию некоторой оценки достоверности или определение выводимости высказывания из множества всех аргументов. Аргументация в этом смысле имеет два аспекта: семантический и синтаксический. Семантический аспект аргументации состоит в порождении оценки высказываний, т.е. определению их допустимости. Семантика аргументации формализуется как средство порождения указанных истинностных значений специально построенной логики аргументации. Синтаксически аргументация формулируется в рамках специальной логики аргументации.
Аргументация в третьем смысле есть аргументационная теория, т.е. некоторая конструкция, содержащая как “постулаты значения”, так и семантический аппарат оценивания аргументированных высказываний. Синтаксическая часть аппарата аргументации предполагается заданной, т.е. логический вывод определён средствами логики аргументации.
Обычно выделяют четыре основные задачи неформальной аргументации [34]: постановка задачи, анализ, получение новых фактов и решение. Под постановкой задачи понимается нахождение в тексте задачи посылок и заключений, следующих из них. Задача анализа сводится к нахождению неявных связей между посылками и заключениями, а также к поиску скрытых зависимостей между аргументами. Получение новых фактов – процесс поиска дополнительной информации или вывод новых аргументов из уже имеющейся информации. Наконец, под решением обычно понимают определение достоверности аргумента (еще говорят силы аргумента), т.е. разрешение спора – что сильнее аргументы или контраргументы для некоторого предположения.
Обычно, говоря об аргументации, выделяют три типа информации [19].
1. Объективная информация – информация, полученная из надёжных источников, или которая может быть напрямую измерена или подтверждена. Например, утверждение “В центральной части России весной продолжительность светового дня увеличивается” является объективной информацией, подтверждаемой наукой и нашими наблюдениями. Такая информация, как правило, используется как неоспоримые аргументы.
2. Субъективная информация – информация, полученная из менее надёжных источников. Это могут быть некоторые предположения, суждения. Часто они формулируются с помощью фраз “как правило”, “обычно”, “скорее всего”. Такая информация и служит “источником” противоречий и конфликтов. 3. Гипотетическая информация. Применяется для построения гипотез. Очень часто является ложной информацией и, более того, бывает заведомо неверной. Однако, построенные аргументы для ее опровержения могут быть полезны для других рассуждений. Например, маловероятно, что уровень мирового океана поднимется на метр в течение следующих 10 лет. Однако, такое предположение полезно при планировании застройки прибрежных территорий с учётом возможности их затопления. Часто при недостатке информации строятся те или иные гипотезы, и производится попытка доказать или опровергнуть их.
Все приведённые типы информации используются в процессе аргументации. Объективная информация применяется для построения фактов и исходных посылок, субъективная информация является источником пересматриваемых выводов, а гипотетическая информация – помогает строить предположения.
Дадим наиболее общее определение аргументации, которое в дальнейшем будет уточняться в соответствии с рассматриваемой формализацией теории аргументации.
Под аргументацией будем понимать процесс анализа задачи, в результате которого выдвигается множество предположений, которые называются аргументами, определяются причинно-следственные связи и находятся конфликты между ними (тем самым определяются аргументы и контраргументы) и, если это возможно, определяется достоверность аргументов (т.е. определяется, является ли аргумент поражённым или нет). Данное определение является наиболее общим и некоторые его части могут терять смысл для конкретных реализаций аргументационных систем. Например, в абстрактных системах отсутствует информация о причинно-следственных связях между аргументами.
Для разных аргументационных систем понятие конфликта отличается. В наиболее общем случае под конфликтом будем понимать отношение (далее такое отношение будем называть отношением атаки), задаваемое на множестве аргументов и характеризующее наличие противоречивых выводов, получаемых в системах аргументации. Подробнее отношение атаки будет рассмотрено в 1.3.1.
Алгоритм обратного вывода
Возможно, самой большой проблемой, с которой сталкиваются разработчики систем автоматизированной пересматриваемой аргументации, является тот факт, что множество аргументов, полученное из исходных аргументов, в общем случае, не является конечным. Поэтому встаёт вопрос об адекватности такой системы, а именно насколько достоверны выводы, полученные в системе пересматриваемых рассуждений.
Д. Поллак утверждает [13], что множество заключений, выдвинутое системой пересматриваемых рассуждений, аппроксимирует множество подтверждённых высказываний, если выполняются следующие условия на рассматриваемые высказывания р: если р является подтверждённым, то система в итоге достигнет того момента, когда р станет обоснованным и будет оставаться обоснованным в дальнейших рассуждениях; если р является неподтверждённым, то система в итоге достигнет того момента, когда р станет необоснованным и будет оставаться необоснованным в дальнейших рассуждениях
В данной главе были приведены основные определения и понятия теории аргументации, рассмотрены свойства отношения атаки, критерии приемлемости аргументов. 2. Также рассмотрены основные типы аргументационных систем: абстрактные системы, системы, основанные на многозначной логике, системы, основанные на пересматриваемых рассуждениях.
Выявлены следующие проблемы и задачи, которые необходимо решить для реализации системы аргументации на основе пересматриваемых рассуждений: реализовать систему монотонного вывода с поддержкой ЛППП; разработать алгоритмы пересматриваемого вывода для ЛППП, а именно алгоритм применения правил пересматриваемого вывода и алгоритм нахождения конфликтов; определить метод количественной оценки достоверности аргументов. В данной главе рассматриваются основные методы, которые использовались при реализации системы аргументации, основанной на пересматриваемых рассуждениях. Приводятся алгоритмы монотонного и пересматриваемого вывода, алгоритмы нахождения конфликтов и противоречий. Кроме того, будет предложено расширение системы для поддержки предикатов первого порядка, а также будет рассмотрен механизм степеней обоснования для нахождения числовой оценки достоверности аргументов.
В отличие от систем абстрактной аргументации, системы пересматриваемых рассуждений предполагают наличие механизма получения новых знаний на основе имеющейся в системе информации. К таким механизмам относятся, например, методы порождения гипотез, индуктивный и дедуктивный выводы. Классическим для систем аргументации на основе пересматриваемых рассуждений является применение методов монотонного вывода. В данной работе будет рассмотрен и реализован механизм монотонного вывода на основе теории натуральной дедукции [14], [42], [43], которая является одним из методов автоматического доказательства теорем.
Натуральная дедукция относится к прямым двунаправленным методам поиска. Для единообразия описания в данном разделе будем использовать терминологию аргументации, а именно называть выводимые формулы аргументами, а формулы, общезначимость которых требуется доказать – интересами. Система работает с двумя списками - списком аргументов, и списком интересов. Изначально список аргументов состоит из посылок, а список интересов состоит из выражений, которые мы хотим вывести.
Далее происходит двунаправленный поиск. В одном направлении происходит порождение новых аргументов на основе уже имеющихся. Такой поиск будем называть прямым. В другом направлении из множества интересов порождаются новые интересы. Такой поиск будем называть обратным. Полученные с помощью правил вывода аргументы и интересы помещаются в очередь вывода.
Определение 2.1. Под очередью вывода будем понимать очередь, состоящую из еще непроанализированных аргументов и интересов. Все полученные аргументы и новые интересы также помещаются в очередь вывода. Пока очередь не окажется пустой, система продолжает работать.
Под схематическими переменными будем понимать любую правильно построенную формулу. Так, например, правило Modus Ponens будет записано в следующем виде: {p,(p q)}= q. Данное правило означает, что если есть аргументы А\.р и A-Ї.p q, то вывести аргумент АъЩ, где/? и q схематические переменные.
Алгоритм GIRS
В постановке задачи аргументации возникает вопрос о приемлемости того или иного предположения относительно заданных посылок. Ответ на такой вопрос - всегда качественный, т.е. допустим или нет. Для некоторых задач (в частности в задаче обобщения, которая будет рассмотрена в главе 3 данной работы) требуется получить не только качественный ответ, но и количественный - а именно насколько достоверен тот или иной аргумент. Для решения этой задачи предлагается использовать механизм степеней обоснования (degrees of justification) [12], [49], [50].
Степени обоснования будем обозначать функцией Jus: А [0Д]. Если степень обоснования Jus(A,) = 0, то говорят, что А, - полностью поражённый аргумент; в случае, если Jus(At) = 1 - аргумент At является полностью достоверным, в противных случаях, когда 0 Jus(Al) 1, говорят, что аргумент АІ достоверен (обоснован) с некоторой мерой уверенности. Степени обоснования могут быть двух типов: 1) степени обоснования исходных аргументов; 2) степени обоснования пересматриваемых правил. Первый тип степеней обоснования присваивается каждому исходному аргументу, и представляет собой оценку достоверности источника, из которого получен данный аргумент. Например, по прогнозу гидрометцентра вероятность осадков завтра 70%. Соответственно мы можем построить аргумент Аі:Завтра(дождь) со степенью обоснования Jus(A1:Завтра(дождь))=0.7. Конкретные механизмы получения степеней обоснования зависят прежде всего от предметной области. Например, это могут быть статистические данные (в 90% этот источник даёт верные данные) или экспертные оценки (вероятность роста акций 60%).
Второй тип степеней обоснования связан с пересматриваемыми правилами. Пересматриваемые правила вывода также могут нести в себе числовую оценку. Будем обозначать степень пересматриваемых правил аналогично - Jus: Е- [0,1]. Например, знание эксперта, что применение анальгина в 85% приводит к снижению температуры тела пациента может быть записано формально следующим образом: R1: ( Vx) прием{аналъгин,х)\ = понижениетемпературы{х)\ Jus(Ri)=0.85. Для изначально заданных аргументов и правил вывода степень обоснования считается заданной декларативно. Ставится вопрос, о том, как вычислить степень обоснования выведенных в ходе рассуждений новых аргументов. Итак, пусть задана задача аргументации А, П, Ш . Требуется задать функцию Jus{A) для вычисления любого из аргументов в графе вывода данной задачи аргументации. Напомним, что граф вывода содержит все аргументы, полученные в ходе решения задачи. Обозначим это множество аргументов, как (C=ALJIB, где Ш - полученное в ходе решения задачи множество новых аргументов. Как уже было сказано выше степень обоснования исходных аргументов считается декларативно заданной константой, т.е. для всех аргументов АІЄА степень обоснования Jus(At) = const, где сотиф,\\ Определим Jus{A) для любого аргумента є Ш.
На значение этой функции будут оказывать влияние два фактора -дерево вывода аргумента (т.е. степень обоснования аргументов, которые использовались в выводе данного аргумента) и конфликты с другими аргументами. Для удобства рассмотрим эти два фактора раздельно: Jusanc{A) -унаследованная степень обоснования и Juscon{A) - мера влияния конфликта на обоснование аргумента.
Унаследованная степень обоснования - это мера, насколько обоснованы аргументы, участвующие в выводе аргумента А. Очевидно, что если для доказательства некоторого аргумента используются “сомнительные” аргументы, то достоверность такого аргумента будет невысока. Предлагается использовать так называемый принцип “слабейшей связи” [12], который означает, что унаследованная степень обоснования некоторого аргумента А, не может быть больше, чем степень обоснования самого “слабого” аргумента, участвовавшего в выводе этого аргумента А
А. Отметим, что из формулы (2.5.1) следует, что, если производить вычисление степеней обоснования рекурсивно, начиная от исходно заданных аргументов, то можно искать минимум, не из всех аргументов в базисе, а только на предыдущем шаге. Таким образом, если у аргумента один предок, то его унаследованная степень обоснования будет равна степени обоснования его предка
Структура разработанной системы
Из приведённых результатов видно, что размер обучающей выборки сильно влияет на точность классификации. Так для малой обучающей выборки применение аргументации не целесообразно. Разбиение обучающей выборки на два подмножества приводит к тому, что обучающих примеров становится слишком мало для формирования адекватных правил методами индуктивного формирования понятий. Так после разбиения обучающей выборки в 28 объектов на два подмножества, алгоритмом GIRS было сформировано всего 5 и 7 решающих правил соответственно. Причём конфликты между этими подмножествами правил на обучающей выборке обнаруживались только для 3 правил, и применение аргументации не позволило существенно улучшить набор решающих правил .
Тем не менее, с ростом размера обучающей выборки применение аргументации становилось всё более оправданным. Так для обучающей выборки из 45 объектов точность увеличилась на 4,29%, для обучающей выборки из 114 объектов – на 5.75%.
Проведённые эксперименты показывают перспективность применения методов аргументации для задачи обобщения. В целом полученные результаты показывают, что предложенный в работе алгоритм позволяет улучшить точность классификации имеющихся алгоритмов обобщения на 5-6% (см. диаграмму 4.1) для данных без шума. Предложенный метод применим для улучшения работы любого алгоритма обобщения, который строит обобщённое понятие в виде множества решающих правил (см. 3.2), в частности были проведены эксперименты с классическим алгоритмом С4.5 [24] и алгоритмом GIRS [61].
Кроме того, были проведены эксперименты с зашумлёнными данными. Из проведённых экспериментов (см. диаграмму 4.3) можно сделать вывод, об эффективности применения аргументации для зашумлённых обучающих выборок, особенно содержащих искажённые значения в решающем атрибуте (см. 3.1.3). Так точность классификации при наличии шума для приведённых тестовых наборов данных удалось в среднем увеличить на 7—10% (см. диаграмму 4.3). Такие результаты объясняются прежде всего тем, что наличие неверно классифицированных объектов в обучающих выборках приводит к формированию неверных классификационных решающих правил. Такие правила приводят к появлению противоречий, находимых методами аргументации. Таким образом, применение методов аргументации позволяет уменьшить влияние некорректных правил вывода, тем самым нивелируя влияния шума в обучающих выборках и приводя к увеличению точности классификации тестовых наборов данных.
Существенным фактором, влияющим на точность классификации объектов является размер обучающей выборки. Зависимость точности классификации предложенного метода от размера обучающей выборки приведён на диаграмме 4.4. Отметим, что на малых обучающих выборках применение методов аргументации не оправдано. Предложенный метод базируется на разбиении обучающей выборки на два подмножества, что плохо применимо для малых обучающих выборок, так как их разбиение приводит к неспособности алгоритмов формирования понятий получить адекватный набор решающих правил из-за недостаточного количества примеров в обучающих выборках. Однако по мере роста размера обучающей выборки, применение аргументации становится всё более оправданным и эффективным.
Разработанная система была успешно применена в качестве отдельного модуля для вычисления действующих скидок в системе управления интернет-магазинами osCommerce. Акт о внедрении приведен в приложении 1.
Требовалось разработать систему, которая могла бы определять какие скидки применимы к заказу, при этом количество типов скидок и их взаимосвязь должна задаваться менеджером интернет-магазина, без привлечения программистов.
Классически такая задача решается для каждого магазина индивидуально и требует привлечения программистов для изменения исходного кода блока вычисления скидок при появлении новых акций\скидок, что приводит к временным задержкам и увеличению накладных расходов. Кроме того, разветвлённая система скидок приводит, к большому числу вложенных блоков “If … then… else”, делая код плохо читаемым и слабо сопровождаемым, что сильно затрудняет добавление новых типов скидок и вызывает большое количество ошибок.
Было предложено использовать систему аргументации на основе пересматриваемых рассуждений для расчета скидок, применимых к заказу. Пересматриваемые и подрывающие правила вывода задает администратор магазина. На основе введённых правил для каждого заказа определяется, сколько и каких скидок будет применено. Для каждого добавленного в магазин типа скидок в базу правил вывода Ж автоматически добавляются пересматриваемые правила вида: Vx Выполено словие{х, тш_скидки)\= Скидка(х, тип скидки). Например, для задания скидки по купону формируется правило: Vx Виполено словие(х, введен купон) = Скидках, введен купон). Кроме того, администратор описывает противоречия в скидках. В простейшем виде правила, описывающие, что наличие скидки С1 отменяет скидку С2 будет записываться как подрывающие правила следующего вида: Vx (Скидках, С1)= (Выполено словие(х, С2) @ Скидках, С2)). Для построения упрощённых правил отмены скидок приведённого вида был построен упрощённый интерфейс задания скидок.