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

Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на 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П, S – некоторая формула ЛП1П, Ф – конъюнкция формул ЛП1П, а Lit(d) – множество литер дизъюнкта d.

Дизъюнкт p является <L, Ф>-импликатой формулы S, если ФÙS p, Ф p, и Lit(p) Í L.

Дизъюнкт p' является <L, Ф>-первичной импликатой формулы S, если:

·  p' – <L, Ф>-импликата формулы S;

·  для всех <L, Ф>-импликат π'' формулы S выполняется {p''╞p'}®{p'╞p''}.

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

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

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

Далее представлены шаги разработанного алгоритма 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.

Конец.

Алгоритм SOLSolve.

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

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

ruleBase – имеющаяся база правил,

lit – множество литер, которые могут присутствовать в выводимых дизъюнктах.

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

result – множество <L, Ф> - первичных импликат.

Начало.

Шаг 1.	Образование начального центрального структурного дизъюнкта topClause = <<Æ>, <Lit(clause)>>. В качестве базы правил нужно взять имеющуюся базу правил, объединенную с clause.
Шаг 2.	Найти все первичные импликаты с помощью выполнения шага 4.
Шаг 3.	Выбрать из полученного на предыдущем шаге множества неповторяющиеся дизъюнкты и записать их в result. Конец.
Шаг 4.	Поиск множества первичных импликат для поступающего на вход узла (структурного дизъюнкта). Возвращается множество дизъюнктов, которые являются первичными импликатами дизъюнкта, образованного из необрамленных литер родительского структурного дизъюнкта topClause, и где резольвировать можно только по литерам из второй компоненты topClause. Для узла, в котором произошел вызов данного шага, выполнить шаг 5, получив множество дизъюнктов s1, и шаг 6, получив множество дизъюнктов s2. Возвратить s1 È s2.
Шаг 5.	Рассматриваем l – первую литеру из второй компоненты topClause. Если l Î lit, то осуществить перенос (правило Skip) литеры из второй компоненты topClause в первую, иначе Конец. Осуществить редукцию (шаг 7). Если вторая компонента topClause пуста, то возвратить дизъюнкт, полученный из литер левой компоненты topClause. Иначе: продолжить рекурсивный поиск для topClause – выполнить шаг 4.
Шаг 6.	Осуществить резолюцию (правило Resolve) первой литеры из второй компоненты со всевозможными дизъюнктами из базы правил. Пусть входной структурный дизъюнкт на данном этапе имеет вид <<a1, a2, … ak>, <l, l1, … ln>>, а подходящее правило rule = l’1, …,l’t, Øl, l’t+1, l’p, тогда резольвента примет вид <<sa1, sa2, … sak>, < sl’1, …,sl’t, sl’t+1, sl’p, [sl], sl1, … sln>>. При выборе подходящего правила нужно соблюдать условие lit(rule) Ç framed({l, l1, … ln}) = Æ. Кроме того, унификация s не должна изменить аргументы литеры l. Осуществить редукцию (шаг 7) всех полученных резольвент и с ними перейти к шагу 4.
Шаг 7.	Редукция поступающего на вход структурного дизъюнкта (правило Reduce). Если в l1, … ln литера l встречается дважды, то удаляется ее самое левое вхождение. Получаем l11, l12, … l1n1. Если какая-либо литера из a1, a2, … ak совпадает с некоторыми литерами из l11, l12, … l1n1, то удаляем из последнего множества эти литеры. Получаем l21, l22, … l2n2. Удалить все обрамленные литеры из <l21, l22, …, l2n2>, которым не предшествует обрамленная литера.

Конец.