Разработка и реализация методов и алгоритмов абдуктивного вывода с использованием систем поддержки истинности на основе предположений тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Хотимчук, Кирилл Юрьевич

• Хотимчук, Кирилл Юрьевич
• кандидат технических наук
• 2011

Оглавление диссертации кандидат технических наук Хотимчук, Кирилл Юрьевич

Введение.

1. Абдуктивный вывод: обзор.

1.1. Основные понятия и определения.

1.2. Подходы к организации абдуктивного вывода.

1.2.1. Подход на основе покрытия множеств.

1.2.2. Подход на основе логики.

1.2.3. Подход на уровне знаний.

1.2.4. Подход на основе вероятностных методов.

1.3. Подходы к отбору гипотез.

1.4. Организация абдуктивного вывода с применением теории аргументации.

1.4.1. Основные понятия теории аргументации.

1.4.2. Нахождение множества обоснованных гипотез.

1.5. ДСМ-метод автоматического порождения гипотез.

1.6. Выводы по главе 1.

2. Методы и алгоритмы абдуктивного вывода.

2.1. Алгоритм нахождения минимальных покрытий.

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

2.2.1. Алгоритм 1трАА.

2.2.2. Примеры работы алгоритма 1трАА.

2.2.3. Эвристический метод для алгоритма 1шрАА.

2.3. Алгоритм абдуктивного вывода с применением теории аргументации.

2.3.1. Алгоритм построения целевых деревьев.

2.3.2. Пример работы алгоритма построения целевых деревьев.

2.3.3. Использование алгоритма целевых деревьев в организации абдуктивного вывода.

2.4. Абдуктивный вывод в логике предикатов первого порядка.

2.5. Выводы по главе 2.

3. Системы поддержки истинности.

3.1. Обзор систем поддержки истинности.

3.1.1. Основные достоинства систем поддержки истинности.

3.1.2. Семейства систем поддержки истинности.

3.2. Система поддержки истинности, основанная на предположениях.

3.2.1. Архитектура систем рассуждения.

3.2.2. Основные определения.

3.2.3. Основные структуры данных.

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

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

3.5. Сравнение алгоритма абдуктивного вывода с использованием систем поддержки истинности, основанных на предположениях, и алгоритма 1шрАА.

3.6. Выводы по главе 3.

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

4.1. Задача составления расписаний в искусственном интеллекте.

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

4.3. Задача о составлении расписания технических работ.

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

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

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

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

4.6. Модификации алгоритмов 1трАА и 1трАА\Н.

4.7. Практические результаты.

4.8. Выводы по главе 4.

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

5.1. Архитектура программного комплекса.

5.2. Язык запросов программного комплекса.

5.3. Сценарии взаимодействия пользователя и программного комплекса.

5.4. Выводы по главе 5.

Введение диссертации (часть автореферата) на тему «Разработка и реализация методов и алгоритмов абдуктивного вывода с использованием систем поддержки истинности на основе предположений»

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

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

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

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

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

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

В организации абдуктивного вывода популярным является подход на уровне логики. В развитие этого подхода внесли свой вклад такие учёные, как Пол Г., Флэч П., Какас А., Габбай М., МакИлрайт Ш., Ковальски. Р., Тони Ф. [9-11,15,18]. Суть этого подхода заключается в том, что знания представляются в виде обобщённых логических теорий, в которых литера может выступать и как следствие, и как причина. Данный подход является очень гибким для реализации большинства механизмов абдуктивного вывода в современных интеллектуальных системах.

При реализации алгоритмов абдуктивного вывода в рамках подхода на основе логики могут использоваться возможности, предоставляемые системами поддержки истинности [26-40]. Значительный вклад в исследование и разработку систем поддержки истинности внесли такие учёные, как Дойл Дж. [27], разработавший одну из самых первых систем поддержки истинности, ДеКлир Дж. [33-37], который ввёл термин "основанный на предположениях" и представил соответствующую систему поддержки истинности, МакАллестер Д. [28-30], Рейтер Р. [31, 35], Мартине Дж. [32], Форбус К. [26, 36] и другие. К достоинствам данных систем относится обеспечение объяснений и сохранение произведённых и промежуточных выводов, работа с противоречиями, умолчаниями, новыми фактами и обоснованиями.

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

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

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

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

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

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

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'll (Украина, г. Гурзуф, 2011 г.), МНТК-2010 (г. Москва, 2010 г.), "Повышение эффективности электрического хозяйства потребителей в условиях ресурсных ограничений. Материалы Всероссийской научно-практической конференции с международным участием".

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

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

Заключение диссертации по теме «Теоретические основы информатики», Хотимчук, Кирилл Юрьевич

5.4. Выводы по главе 5

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

С использованием результатов данной работы разработано программный комплекс решения задачи составления расписания (Глава 4), использующий систему поддержки истинности, основанную на предположениях (Глава 3), которая является базой для разработанного алгоритма (Глава 3) и используется последним для хранения промежуточных результатов, что сокращает повторные вычисления. Данный программный комплекс использует разработанную эвристику (Глава 4) для сокращения пространства поиска.

5. Заключение

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

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

2. Выполнено исследование и анализ систем поддержки истинности. Особое внимание уделено системам поддержки истинности, основанным на предположениях, ключевым достоинством которых является сохранение выводов, что приводит к кэшированию промежуточных результатов, в результате чего нет необходимости в повторных вычислениях. Благодаря своим характеристикам, система поддержки истинности, основанная на предположениях (ATMS), выбрана в качестве основы для построения абдуктивного алгоритма.

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Хотимчук, Кирилл Юрьевич, 2011 год

1. Peirce C.S., Philosophical'writings. N.Y.: Dover Publications, Inc, 1955. P. 386.

2. Cox P.T. andPietrzykowski T. General diagnosis by abductive inference // Proc. IEEE

3. Sympos. Logic Programming. San Francisco. 1987. P. 183-189.

4. Hobbs J., Stickel M.E., Appelt D. et al. Interpretation as abduction // Artificial Intelligence.1993.63(1 -2). P. 69-142.i

5. Eshghi K. Abductive planning with the event calculus. // Robert A. Kowalski, Kenneth A. Bowen editors: Logic Programming, Proc. of the Fifth International Conference and Symposium, Seattle, Washington, August 15-19, 1988. MIT Press, 1988, P.562-579.

6. Финн В.К. Синтез познавательных процедур и проблема индукции // Интеллектуальные системы и общество: сборник статей, изд.2-е, испр. и существ, доп., Москва: КомКнига, 2006. 352с. С. 130-219.

7. Виноградов Д.В. Формализация правдоподобных рассуждений в логике предикатов //

8. ДСМ-метод автоматического порождения гипотез: Логические и эпистемологическиеоснования, Москва: Книжный дом "ЛИБРОКОМ", 2009. 432 с. С. 287-293.

9. Рузавин Г.И. Абдукция как метод поиска и обоснования объяснительных гипотез //

10. Теория и практика аргументации. М., 2001. с. 28-48.

11. Васюков B.JI. Научное открытие и контекст абдукции // Философия науки. Вып. 9. М.:1.ИФ РАН, 2003. с. 180-205.

12. Flach P.A., Kakas А.С. On the relation between abduction and inductive learning //

13. Handbook of defeasible reasoning and uncertainty management systems: Volume 4 abductive reasoning and learning, Kluwer Academic Publishers Norwell, MA, USA, 2000, P. 1-33.

14. Bergadano F., Cutello V., Gunetti D. Abduction in machine learning // Handbook of defeasible reasoning and uncertainty management systems: Volume 4 abductive reasoningj and learning. Kluwer Academic Publishers Norwell, MA, USA, 2000, P. 197-229.

15. Dubois D., Prade H. An overview of ordinal and numerical approaches to causal diagnosticproblem solving // Handbook of defeasible reasoning and uncertainty management systems:

16. Volume 4 abductive reasoning and learning. Kluwer Academic Publishers Norwell, MA, USA, 2000, P. 231 -280.r '5 ' , 'i i

17. Kakas A.C., Kowalski R.A., Toni F. The role of abduction in logic programming // Handbook of Logic in Artificial Intelligence and Logic Programming / Ed. Gabbay D.M., Hogger C J. and Robinson J.A. Oxford, UK. Oxford University Press. 1998, P. 235-324.

18. Inoue K., Sakama C. Abductive framework for nonmonotonic theory change // Proc. 14th International Joint Conference on Artificial Intelligence, Montreal, Quebec, Canada, 1995, P. 204-210.

19. Levesque H. A knowledge-level account of abduction // Proc 11th International Joint Conference on Artificial Intelligence. San Francisco, CA, USA. 1989. P. 1061-1067.

20. Cox P., Pietrzykowski T. Causes for Events: Their Computation and Applications. // Proc. 8th International Conference on Automated Deduction, Oxford, England, 1986, P. 608-621.

21. Pople H. E. On the mechanization of abductive logic // Proc. of the 3rd international joint conference on Artificial intelligence, 1973, San Francisco, CA, USA 1973, P. 147-152.

22. Appelt D.E., Pollack M.E. Weighted Abduction for Plan Ascription // Proc. of User Modelling and User-Adapted Interaction, Volume 2(1-2) 1992, Kluwer, Netherlands, P. 1-25.

23. Console L., Dupre D. T. Abductive Reasoning with Abstraction Axioms // Foundations of Knowledge Representation and Reasoning, (G. Lakemayer, B. Nebel eds.), Lecture Notes in Computer Science 810, Springer Verlag, 1994, P. 98-112.

24. Poole D. Probabilistic Horn abduction and Bayesian networks // Artificial Intelligence, Volume 64, Numbers 1, 1993, P. 81-129.

25. Forbus K.D., de Kleer J. Building Problem Solver, The MIT Press, Cambridge, Massachusetts, London, England, 1993.

26. Doyle J. A Truth Maintenance System // Artificial Intelligence, 1979, Vol.12. P.231-272.

27. McAllester D. A Three-valued Truth Maintenance System / S.B. Thesis, Department of Electrical Engineering, MIT, Cambridge, MA, 1978.

28. McAllester D. An Outlook on Truth Maintenance. Artificial Intelligence Laboratory, AIM-551, MIT, Cambridge, MA, 1980.

29. McAllester D. Truth Maintenance // Proc. Of AAAI-90, 1990. P. 1109-1116.

30. Reiter R. A Logic for Default Reasoning // Artificial Intelligence, 1980, Vol. 13.P.81-132.

31. Castro J.L., Zurita J.M. A Generic ATMS // International Journal of Approximate Reasoning, 1996, Vol. 14, P.259-280.

32. Dechter R., Dechter A. Structure Driven Algorithms for Truth Maintenance // Artificial Intelligence, 1996, Vol. 82, P. 1-20.

33. Thompson C.A. Inductive learning for abductive diagnosis. Texas: the University of Texas at Austin, 1993. P. 53.

34. A3. Marquis P. Consequence finding algorithms // Handbook for Defeasible Reasoning and Uncertain Management Systems, eds. D.M. Gabbay and P. Smets. 2000. V. 5. P. 41-145.

35. Вагин В.Н., Хотимчук К.Ю. Нахождение минимальных абдуктивных объяснений с помощью первичных импликат // Тр. 11й национальной конференции по искусственному интеллекту с международным участием (КИИ-2008. г. Дубна, Россия). 2008. Т. 2. Р. 345-355.

36. Вагин В.Н., Хотимчук К.Ю. Методы абдуктивного вывода в задачах планирования работы в сложных объектах // Известия РАН. Теория и системы управления, 2010, №5, с. 95-113.

37. Charniak Е., Shimony S.E. Cost-Based Abduction and MAP Explanation // Artificial Intelligence Journal, V. 66(2), 1994. P. 345-374.53 .NgH.T., MooneyRJ. On the Role of Coherence in Abductive Explanation // AAAI 1990. P. 337-342.

38. Финн B.K. Об одном варианте логики аргументации // Интеллектуальные системы и общество: сборник статей, изд.2-е, испр. и существ. Доп., Москва, : КомКнига, 2006. — 352с. 220-265.

39. Финн B.K. Правдоподобные выводы и правдоподобные рассуждения // Итоги науки и техники. Сер. Теория вероятностей. Математическая статистика. Теоретическая кибернетика. Т. 28. М. : ВИНИТИ, 1991. С. 3-84.

40. Финн В.К. Правдоподобные рассуждения в интеллектуальных системах типа ДСМ // Итоги науки и техники. Сер. Информатика. Т. 15. М.: ВИНИТИ, 1991. С. 54-101.

41. Dang P.M. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games // Artificial Intelligence Journal, V. 77(2), 1995. P.321-357.

42. Kakas A.C., Toni F. Computing argumentation in logic programming // Journal of Logic and Computation 1999. V. 9. P. 515-562.

43. Kowalski R., Kuhner D. Linear resolution with selection function // Artificial Intelligence. 1971. V. 2. P. 227-260.

44. Танаев B.C., Шкурба В.В. Введение в теорию расписаний. М.: Наука, 1975. С. 256.

45. Маппе A.S. On the Job Shop Scheduling Problem // Operations Research, 1960, 8(2): P. 219223.

46. Denecker M., Kakas A. Abduction in Logic Programming // Computational Logic: Logic Programming and Beyond, Essays in Honour of Kowalski R.A., P. I, London, UK: SpringerVerlag. 2002. V. 2407. P. 402-437.

47. Microsoft Corporation Microsoft Inductive User Interface Guidelines // RSDN Magazine #6, 2004.

48. Fikes R., Nilsson N. STRIPS: a new approach to the application of theorem proving to problem solving // Artificial Intelligence, 2: P. 189-208.ll.McDermott D. The Formal Semantics of Processes in PDDL // Proc. 1С APS Workshop on PDDL.

49. Ghallab M., Nau D.S. Automated Planning: Theory and Practice. Traverso, Paolo: Morgan Kaufmann, 2004. P.