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




Скачать 310.83 Kb.
НазваниеРазработка и реализация методов и алгоритмов абдуктивного вывода с использованием систем поддержки истинности на основе предположений
страница1/3
Хотимчук Кирилл Юрьевич
Дата конвертации08.11.2012
Размер310.83 Kb.
ТипАвтореферат
  1   2   3


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

Хотимчук Кирилл Юрьевич

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


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


А В Т О Р Е Ф Е Р А Т

диссертации на соискание ученой степени

кандидата технических наук

Москва – 2011

Работа выполнена на кафедре Прикладной математики Московского энергетического института (Технического университета)

Научный руководитель: лауреат премии президента РФ в области образования, доктор технических наук, профессор

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

Геннадий Семёнович Осипов;

кандидат физико-математических наук, ведущий научный сотрудник

Алексей Николаевич Аверкин
Ведущая организация: ГУ "Российский НИИ информационных технологий и систем автоматизированного проектирования", г. Москва

Защита состоится «23» июня 2011 г. в 18 час. 00 мин. на заседании диссертационного совета Д 212.157.01 при Московском энергетическом институте (Техническом университете) по адресу: 111250, Москва, Красноказарменная ул., 17 (ауд. Г-306).
С диссертацией можно ознакомиться в библиотеке Московского энергетического института (Технического университета).
Отзывы в двух экземплярах, заверенные печатью, просьба направлять по адресу: 111250, г. Москва, Красноказарменная улица, д.14, Ученый Совет МЭИ (ТУ).

Автореферат разослан «____» ___________ 2011 г.

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

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

кандидат технических наук,

доцент

М.В. Фомина

Общая характеристика работы

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

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

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

Одним из вариантов организации абдуктивного вывода, определяющим высокую скорость поиска решений, мощные средства для пересмотра решений и обеспечения непротиворечивости выводимых решений, является сохранение выводимых данных в системе поддержки истинности, основанной на предположениях (Assumption-based Truth-Maintenance System, ATMS).

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

В теорию и практику организации абдуктивного вывода большой вклад внесли отечественные учёные Финн В.К., Кузнецов С.О., Аншаков О.М., Виноградов Д.В., Рузавин Г.И., Васюков В.Л. и другие, а так же учёные Пирс Ч.С., Пол Г., Флэч П., Какас А., Габбай М., Бергадано Ф., Дюбуа Д., Прейд Х., МакИлрайт Ш., Аллемань Д., Джозефсон Дж., Конолиге К., Ковальски Р., Тони Ф., Иноу К., Сакама Ч., Левек Х., Кокс Ф., Пиетржиковски Т., Аппелт Д., Поллак М., Консоле Л., Дюпре Д., Пул Д. и другие.

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

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

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

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

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

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

Для достижения указанной цели требовалось решение следующих задач:

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

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

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

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

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

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

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

  8. Разработка и программная реализация на базе системы поддержки истинности алгоритма абдуктивного вывода.

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

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

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

Научная новизна. Новыми являются:

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

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

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

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

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

Практическая значимость работы подтверждена использованием полученных результатов в интеллектуальной системе поддержки принятия решений “СПРИНТ-РВ” и в учебном процессе в МЭИ (ТУ) при изучении дисциплины “Математическая логика”, о чём имеются акты о внедрении.

Реализация результатов. Результаты диссертационной работы Хотимчука К.Ю. вошли в отчёты по НИР, выполняемым кафедрой ПМ по грантам РФФИ № 09-01-00076а “Исследование и разработка методов анализа данных и обнаружения знаний в «зашумленных» базах данных”, № 08-07-00212 “Исследование и разработка методов и инструментальных средств индуктивного формирования понятий в интеллектуальных системах поддержки принятия решений”, в отчёты по НИР, выполняемым Хотимчуком К.Ю. по гранту “У.М.Н.И.К.”, а также были использованы в учебном процессе в курсе “Математическая логика”. На разработанный в диссертационной работе программный комплекс выдано свидетельство о государственной регистрации программы для ЭВМ №2010614887 (27 июня 2010 г.).

Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на 13-й, 16-й и 17-й научно-технических конференциях аспирантов и студентов “Радиоэлектроника, электротехника и энергетика” в МЭИ (ТУ) (г. Москва, 2007, 2010, 2011 г.), 11-й и 12-й национальных конференциях по искусственному интеллекту с международным участием КИИ-2008 (г. Дубна, 2008 г.) и КИИ-2010 (г. Тверь, 2010 г.), “Информационные технологии в науке, социологии, экономике и бизнесе” IT+S&E’11 (Украина, г. Гурзуф, 2011 г.), МНТК-2010 (г. Москва, 2010 г.), “Повышение эффективности электрического хозяйства потребителей в условиях ресурсных ограничений. Материалы Всероссийской научно-практической конференции с международным участием”.

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

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

Содержание работы

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

В первой главе рассмотрены основные понятия и определения абдуктивного вывода, приведены классические подходы к организации абдуктивного вывода, а также альтернативный способ организации вывода по абдукции с использованием теории аргументации, и описаны подходы к отбору гипотез. Также рассмотрен ДСМ-метод автоматического порождения гипотез для решения задач прогнозирования в условиях неполноты информации.

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

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

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

Пусть Ф – конъюнкция формул логики предикатов первого порядка (ЛП1П). H – конечное множество однолитеральных формул ЛП1П, называемых предположениями (гипотезами). Упорядоченная пара T = <Ф, Н> – теория, построенная на предположениях.

Пусть δ – формула ЛП1П. Конъюнкт γ=h1h2…hk, где h1,h2,…,hk  H, назовем абдуктивным объяснением δ относительно Т, если:

  • Ф γ ╞ δ;

  • Ф γ выполнимо.

Конъюнкт γ'=h1h2…hk, где h1,h2,…,hk  H, назовем минимальным абдуктивным объяснением δ относительно Т, если:

  • γ' – абдуктивное объяснение для δ относительно Т;

  • для любого абдуктивного объяснения γ'' для δ относительно Т выполняется (γ'╞ γ'')  ( γ''╞ γ').

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

Пусть L – конечное подмножество литер ЛП1П,  – некоторая формула ЛП1П, Ф – конъюнкция формул ЛП1П, а Lit(d) – множество литер дизъюнкта d.

Дизъюнкт  является -импликатой формулы , если Ф , Ф , и Lit()L.

Дизъюнкт ' является -первичной импликатой формулы , если:

  • ' -импликата формулы ;

  • для всех -импликат π'' формулы  выполняется {''╞'}{'╞''}.

В алгоритме ImpAA используются следующие понятия.

Пусть L – множество литер ЛП1П. Расширенным дизъюнктом называется упорядоченный дизъюнкт, литеры которого берутся из множества L{[r], rL}. Множество {[r], rL} – это множество так называемых обрамлённых литер. Обрамление литеры является способом запомнить, что по данной литере мы уже резольвировали. Таким образом, если дизъюнкт содержит обрамлённую литеру [r], то это означает, что один из его родительских дизъюнктов содержит r.

Структурный дизъюнкт – это упорядоченная пара <, >, где – дизъюнкт, – расширенный дизъюнкт.

Далее представлены шаги разработанного алгоритма ImpAA.
Алгоритм 1. Алгоритм ImpAA.

Исходные данные:

clauses – исходное множество дизъюнктов,

observed – наблюдаемый конъюнкт.

Выходные данные:

result – множество абдуктивных объяснений для observed (результирующее множество конъюнктов).

Начало.

Шаг 1.

Создаем дизъюнкт clause = observed,

Шаг 2.

Обращаемся к процедуре SOLSolve с параметрами clause, clauses, Lit(clause)Lit(clauses), где Lit(clause) / Lit(clauses) – множество литер, встречающихся в дизъюнкте/дизъюнктах. Результат выполнения процедуры – множество implicates.

Шаг 3.

Для каждого дизъюнкта implicate из implicates создаем конъюнкт explanation = implicate. Добавляем explanation к result.

Конец.
  1   2   3

Похожие:

Разработка и реализация методов и алгоритмов абдуктивного вывода с использованием систем поддержки истинности на основе предположений icon«Совершенствование конструкции электромеханического оборудования с использованием элементов усиления»
...
Разработка и реализация методов и алгоритмов абдуктивного вывода с использованием систем поддержки истинности на основе предположений iconСистема поддержки принятия решений в сфере управления деятельностью организации на основе процессного подхода (на примере территориальных учреждений банка россии)
Работа выполнена на кафедре информационных систем и математических методов в экономике
Разработка и реализация методов и алгоритмов абдуктивного вывода с использованием систем поддержки истинности на основе предположений iconРазработка методов и алгоритмов в задачах оптимального использования и развития сетей
Работа выполнена в Вычислительном центре им. А. А. Дородницына Российской академии наук
Разработка и реализация методов и алгоритмов абдуктивного вывода с использованием систем поддержки истинности на основе предположений iconРеферат Урок географии с использованием икт в системе дистанционной поддержки
Технология создания информационно-дидактического комплекса по географии и его реализация (система уроков географии с использованием...
Разработка и реализация методов и алгоритмов абдуктивного вывода с использованием систем поддержки истинности на основе предположений iconРазработка моделей и алгоритмов эффективного функционирования тренажерно-обучающих систем в электроэнергетике (на примере рсо-алания)
Специальность: 05. 13. 01 «Системный анализ, управление и обработка информации (промышленность)»
Разработка и реализация методов и алгоритмов абдуктивного вывода с использованием систем поддержки истинности на основе предположений iconМетодическая разработка урока физики в 7 классе по теме «Давление газа»
Данная разработка представляет опыт работы по организации урока с использованием возможностей интерактивной доски на основе материалов...
Разработка и реализация методов и алгоритмов абдуктивного вывода с использованием систем поддержки истинности на основе предположений iconПроводимых по заданию Федерального агентства по образованию в 2009 г
Развитие качественной теории управляемых и неуправляемых сложных динамических систем, разработка аналитических и численных методов...
Разработка и реализация методов и алгоритмов абдуктивного вывода с использованием систем поддержки истинности на основе предположений iconРуководство по требованиям к возможностям инженерного инструмента»; Разработка ст рк «Информационные технологии. Анализ доступности для людей с ограниченными возможностями. Часть Обзор потребностей пользователя»
Разработка ст рк «Информационные технологии. Языки программирования, их окружение и интерфейсы программного обеспечения систем. Расширения...
Разработка и реализация методов и алгоритмов абдуктивного вывода с использованием систем поддержки истинности на основе предположений iconРазработка методов дифференциальной диагностики контагиозной эктимы овец и коз на основе рестрикционного анализа и полимеразной цепной реакции 03. 00. 06 вирусология
Разработка методов дифференциальной диагностики контагиозной эктимы овец и коз на основе рестрикционного анализа и полимеразной цепной...
Разработка и реализация методов и алгоритмов абдуктивного вывода с использованием систем поддержки истинности на основе предположений iconС. В. Войцеховский, А. Д. Хомоненко
Предлагается подход к выявлению вредоносных программных воздействий на автоматизированные системы на основе нечеткого вывода решений...
Разместите кнопку на своём сайте:
kk.convdocs.org



База данных защищена авторским правом ©kk.convdocs.org 2012-2017
обратиться к администрации
kk.convdocs.org
Главная страница