BC/NW 2007, №1, (10) :5.3

 

ИССЛЕДОВАНИЕ МЕТОДОВ НАХОЖДЕНИЯ МИНИМАЛЬНЫХ АБДУКТИВНЫХ ОБЪЯСНЕНИЙ

 

К.Ю. Хотимчук, В.Н. Вагин

 

(Москва, Московский энергетический институт (технический университет), Россия)

 

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

В данной работе:

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

- рассматривается понятие <Ф, L>-первичной импликаты, раскрывается связь <Ф, L>-первичной импликаты с минимальным абдуктивным объяснением и описывается алгоритм SOL-резолюции для нахождения множества <Ф, L>-первичных импликат.

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

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

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

Результаты:

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

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

 

Литература

1. Достоверный и правдоподобный вывод в интеллектуальных системах  / В.Н. Вагин, Е.Ю.Головина, А.А.Загорянская, М.В.Фомина. М.: Физматлит, 2004.

2. Consequence finding algorithms / P. Marquis. Editor: J. Kohlas and S. Moral .Switzerland: University of Fribourg, 2000.

3. Inductive learning for abductive diagnosis  / C. A. Thompson (supervising professor Raymond J.Mooney). Texas : the University of Texas at Austin, 1993.