Абдуктивный метод модификации посылок в исчислении высказываний

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

Рубрика Программирование, компьютеры и кибернетика
Вид реферат
Язык русский
Дата добавления 16.01.2018
Размер файла 43,4 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Абдуктивный метод модификации посылок в исчислении высказываний** Работа выполнена при финансовой поддержке РФФИ (проект № 06-01-00089-а)

Е.В. Котельников 610000, Киров, ул. Московская, 36, ВятГУ, eug_kot@ezmail.ru, Д.А. Страбыкин 610000, Киров, ул. Московская, 36, ВятГУ, strabykin@mail.ru

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

модификация посылка абдукция выводимость

Введение

Любая система, претендующая на «интеллектуальность», должна обладать развитыми способностями к обучению. Наибольшие успехи в обучении достигнуты при использовании нейронных сетей и индуктивного логического вывода. Однако обоим подходам присущи некоторые недостатки. Например, при использовании нейронных сетей возникают трудности при попытках семантической интерпретации механизмов их работы. Кроме того, оба подхода подразумевают наличие достаточно представительной выборки обучающих примеров.

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

1. Постановка задачи

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

Задача модификации посылок включает две подзадачи: добавления посылок и удаления посылок.

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

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

Задача модификации посылок. Задано исходное множество посылок M и множество заключений m, состоящее из двух подмножеств - подмножества заключений mp, которые должны выводиться из посылок, и подмножества заключений mn, которые не должны выводиться из посылок. Требуется модифицировать исходное множество посылок M таким образом, чтобы заключения из обоих подмножеств заключений mp и mn удовлетворяли заданным условиям выводимости.

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

2. Метод модификации посылок

Абдуктивный метод модификации посылок позволяет удовлетворить требованиям выводимости для множества заключений. Метод основан на трех методах нижнего уровня: методе определения выводимости, методе добавления посылок и методе удаления посылок. Метод определения выводимости позволяет установить, выводится ли заданное заключение из набора исходных посылок, и является методом дедуктивного логического вывода. Метод добавления посылок [Котельников, 2005] позволяет для заданного заключения генерировать семейство множеств дополнительных посылок. При добавлении любого множества из найденного семейства заключение становится логическим следствием исходных посылок.

При помощи метода удаления посылок [Котельников, 2006] осуществляется поиск удаляемых посылок среди множества исходных посылок для заданного заключения. Результатом метода является семейство множеств посылок-кандидатов на удаление.

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

На первом шаге модификации посылок все заключения, принадлежащие множеству m, с помощью метода определения выводимости делятся на четыре класса:

p/p - логический вывод успешен / должен быть успешен. Заключения этого класса обозначим dppk (k=1..K);

n/p - логический вывод неудачен / должен быть успешен. Обозначим такие заключения dnpl (l=1..L);

p/n - логический вывод успешен / должен быть неудачен. Заключения обозначим dpnr (r=1..R);

n/n - логический вывод неудачен / должен быть неудачен. Заключения обозначим dnns (s=1..S).

Проверяется, имеются ли заключения в классах p/n и n/p. Если заключения в обоих классах отсутствуют, то происходит переход к шагу 5. Иначе выполняется следующий шаг.

На втором шаге находятся множества посылок, соответствующие классам n/p и p/n:

для каждого заключения dnpl класса n/p генерируется семейство множеств посылок npl. Семейство множеств npl состоит из множеств Mnpli (i=1..I). При добавлении любого множества Mnpli заключение dnpl становится выводимым. Генерация осуществляется методом добавления посылок;

метод удаления посылок применяется для нахождения семейства множеств pnr для каждого заключения dpnr класса p/n. Семейство множеств pnr состоит из множеств Mpnrj (j=1..J). При удалении любого множества Mpnrj из множества исходных посылок вывод заключения dpnr заканчивается неудачно.

На третьем шаге с помощью проверочного дедуктивного вывода определяются множества посылок из семейств множеств npl, которые можно включить во множество исходных посылок без влияния на отсутствие выводимости заключений класса n/n. Если такие множества найдены, то они добавляются во множество М исходных посылок, а соответствующие заключения из класса n/p переходят в класс p/p. Остальные заключения остаются в классе n/p до следующего цикла или до окончания решения, так как на текущем шаге добавление посылок из множества Mnp вступает в противоречие с требованием отсутствия выводимости заключений класса n/n.

На четвертом шаге находятся такие множества посылок семейств pn, которые можно удалить без влияния на выводимость заключений класса p/p. Найденные множества удаляются из множества М исходных посылок, а соответствующие заключения dpnr из класса p/n переходят в класс n/n. Остальные дизъюнкты остаются в классе p/n до следующего цикла или до окончания решения, так как на текущем шаге удаление соответствующих посылок вступает в противоречие с требованием выводимости заключений класса p/p.

На пятом шаге проверяется, имеются ли заключения в классах p/n и n/p и меньше ли счетчик заданного максимального значения: h<Hmax. Если заключения в обоих классах отсутствуют, то модификация посылок заканчивается и фиксируется положительный результат - модифицированное множество исходных посылок М. Если счетчик превысил максимальное значение и имеются заключения хотя бы в одном классе p/n или n/p, то модификация посылок заканчивается и фиксируется отрицательный результат - за отведенное число шагов метод не смог привести множество исходных посылок в соответствие с требованиями выводимости.

Иначе проверяется, имеет ли место ситуация зацикливания. Она возникает, когда множество исходных посылок на пятом шаге не отличается от того же множества на первом шаге текущего цикла. В этом случае добавление и/или удаление посылок не удовлетворяет требованиям выводимости для классов р/р и n/n.

Способом разрешения такой ситуации может служить безусловная модификация, когда некоторое множество Mnpli (Mpnrj) безусловно добавляется (удаляется) во множество исходных посылок М. При прочих равных условиях предпочтение отдается множествам Mnpli. Причем среди множеств выбираются те, которые (как было выяснено на шагах 3 и 4) оказывают минимальное влияние на классы заключений p/p и n/n.

Определим, что понимается под минимальным влиянием. Из набора множеств Mnpli минимальное влияние на класс заключений n/n оказывает такое множество, при добавлении которого во множество исходных посылок М минимальное число заключений класса n/n переходит в класс p/n. Аналогично, из набора множеств Mpnrj минимальное влияние на класс заключений р/р оказывает такое множество, при удалении которого из множества исходных посылок М минимальное число заключений класса р/р переходит в класс n/p.

Если сразу несколько множеств оказывают одинаковое минимальное влияние на классы заключений p/p и n/n, то предпочтение отдается множествам Mnpli. Если несколько множеств удовлетворяют одновременно всем перечисленным признакам, выбор осуществляется случайно. Если в классах p/n и n/p имеются заключения, то счетчик числа итераций h увеличивается на единицу, и если имеет место ситуация зацикливания, то осуществляется переход к шагу 1, иначе - переход к шагу 2.

3. Пример логического вывода

Рассмотрим пример логического вывода с модификацией посылок.

Задано исходное множество посылок M:

AB;

BC;

CE;

EN;

LD;

FG;

IJ;

G&JK;

KL.

Также задано множество выводимых заключений m, состоящее из двух подмножеств mp и mn: 1) AEmp; 2) FCmp; 3) BEmn; 4) FNmn.

Требуется модифицировать исходное множество посылок M таким образом, чтобы заключения из подмножества mp выводились из М, а заключения из подмножества mn - не выводились.

Исходные данные представлены схемой на рис. 1.

Размещено на http://www.allbest.ru/

Рис. 1. Исходные посылки для примера модификации

Исходные посылки представляются в виде дизъюнктов:

B (D1);

C (D2);

E (D3);

N (D4);

D (D5);

G (D6);

J (D7);

K (D8);

L (D9).

Аналогично представляются заключения:

1) E (d1); 2) C (d2); 3) E (d3); 4) N (d4).

Процесс модификации посылок является циклическим и состоит из ряда шагов.

Цикл 1

Шаг 1. Все заключения, принадлежащие множеству m, с помощью проверочного дедуктивного вывода делятся на четыре класса:

dpp=d1=E (логически следует из множества М и принадлежит mp);

dnp=d2=C (не выводится из исходных посылок и принадлежит mp);

dpn=d3=E (принадлежит подмножеству mn и выводится из М);

dnn=d4=N (принадлежит подмножеству mn и не выводится из М).

Шаг 2. Находятся множества посылок, соответствующие классам n/p и p/n. Для заключения d2=C, входящего в класс n/p, сгенерируем семейство множеств np добавляемых дизъюнктов. При добавлении любого из множеств этого семейства дедуктивный логический вывод заключения d2 должен оканчиваться успешно. Семейство множеств np будем генерировать с помощью метода добавления посылок.

Для заключения d2 и множества М результатом данного метода будет являться следующее семейство множеств:

np=[M*1,M*2,M*3,M*4,M*5,M*6,M*7,M*8],

где M*1={C}, M*2={B}, M*3={A,J}, M*4={A,I}, M*5={A,J}, M*6={A,I}, M*7={A,J}, M*8={A,I}.

Заключение d3=E входит в класс p/n, следовательно, нужно найти семейство таких множеств дизъюнктов, при удалении любого из которых из множества М заключение d3 перестает быть логическим следствием исходных посылок. Создавать семейство множеств pn удаляемых дизъюнктов будем при помощи метода удаления посылок. Результатом этого метода для множества М и заключения d3 будет следующее семейство множеств:

pn=[,], где ={C}, ={E}.

Шаг 3. Определяются множества посылок из семейств множеств np, которые можно включить во множество исходных посылок без влияния на отсутствие выводимости заключений класса n/n.

Чтобы найти такие множества, будем последовательно добавлять каждое множество из семейства np во множество М и выполнять проверочный дедуктивный вывод заключения, входящего в класс n/n. После неудачной проверки (то есть заключение класса n/n стало выводиться) нужно удалить включенное множество. Иначе поиск множеств заканчивается.

Последовательно включая по одному множества M*1-M*8 во множество М и производя проверочный вывод заключения d4=N, получаем, что ни одно из множеств семейства np не удовлетворяет требованиям выводимости заключения d4. Следовательно, на данном шаге ни одно из этих множеств не добавляется к множеству М. Заключение d2 остается в классе n/p.

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

Чтобы найти такие множества, будем последовательно удалять множества семейства pn из множества исходных посылок и осуществлять проверку с помощью дедуктивного логического вывода, выводится ли заключение d1=E, принадлежащее классу р/р. Если заключение перестает выводиться, то текущее множество удаляется из множества исходных посылок. Удаляя сначала множество ={C}, а затем множество ={E}, получаем, что при удалении любого из этих множеств заключение d1 перестает выводиться из множества М. То есть на данном шаге ни одно из этих множеств нельзя удалять из множества исходных посылок. Заключение d3 остается в классе p/n.

Шаг 5. Проверяется, имеются ли заключения в классах p/n и n/p. Заключения в данных классах присутствуют, следовательно, вывод продолжается. Проверяется, имеет ли место ситуация зацикливания. Действительно, множество М исходных посылок на пятом шаге не изменилось по сравнению с первым шагом данного цикла, следовательно, возникло зацикливание.

Для разрешения ситуации зацикливания применяем способ безусловной модификации. Для добавления во множество исходных посылок выбирается множество M*8={A,I}. После добавления множества M*8 множество исходных посылок М принимает вид, показанный на рис. 2.

Размещено на http://www.allbest.ru/

Рис. 2. Схема исходных посылок после первого цикла

Циклы 2 и 3

В начале второго цикла имеет место следующее разделение на классы:

классу p/p принадлежат заключения d1=E, d2=C.

классу p/n принадлежат заключения d3=E, d4=N.

В ходе выполнения второго и третьего циклов выясняется, что при удалении дизъюнктов E и N заключения класса p/n перейдут в требуемый класс n/n. Однако при этом перестанет выводиться заключение d1=E.

Множество исходных посылок М после третьего цикла принимает вид, показанный на рис. 3.

Размещено на http://www.allbest.ru/

Рис. 3. Схема исходных посылок после третьего цикла

Цикл 4

Классы заключений в начале четвертого цикла выглядят следующим образом:

1) р/р: d2=C; 2) n/p: d1=E; 3) n/n: d3=E, d4=N.

Определяется, что для перевода заключения d1 в класс р/р требуется добавить дизъюнкт E.

Таким образом, результатом метода модификации посылок является модифицированное множество исходных посылок М (рис. 4):

B (D1);

C (D2);

D (D5);

G (D6);

J (D7);

K (D8);

L (D9);

A (D10);

I (D11);

E (D12).

Размещено на http://www.allbest.ru/

Рис. 4. Схема модифицированного множества исходных посылок

Заключение

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

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

Список литературы

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

[Котельников, 2005] Котельников Е.В. Метод добавления посылок на основе абдукции // Вестник ВВО АТН РФ. Серия: Проблемы обработки информации. Вып. 1(5)/2005. - Киров, 2005. - С. 14-24.

[Котельников, 2006] Котельников Е.В. Метод удаления посылок в исчислении высказываний // Сборник Всерос. ежегодной науч.-техн. конф. ВятГУ «Наука-производство-технологии-экология» - Киров: Изд-во ВятГУ, 2006. - Т. 1. - С. 109-113.

Размещено на Allbest.ru

...

Подобные документы

  • Назначение, организационная и функциональная структура почтового отделения. Разработка автоматизированной системы распределения заявок на доставку посылок. Образцы входных и выходных документов. Выбор программного обеспечения. Пример работы программы.

    курсовая работа [2,2 M], добавлен 25.12.2014

  • Экспертные системы реального времени. Основные производители. История возникновения и развития языка ПРОЛОГ. Исчисление высказываний. Исчисление предикатов. Программирование на ПРОЛОГЕ. Принцип резолюций. Поиск доказательства в системе резолюций.

    курсовая работа [146,2 K], добавлен 15.04.2008

  • Языки логического (Пролог) и функционального (ЛИСП и РЕФАЛ) программирования. Задачи прямого и обратного вывода. Алгоритм CLS для построения деревьев. Математические основы индуктивного и дедуктивного вывода, алгебра высказываний, исчисление предикатов.

    курс лекций [319,9 K], добавлен 24.06.2009

  • Обзор методов и подходов решения поставленной задачи аппроксимации логического вывода экспертной системы. Разработка и описание метода сетевого оператора для решения данной задачи. Разработка алгоритма решения. Проведение вычислительного эксперимента.

    дипломная работа [1,5 M], добавлен 23.02.2015

  • Сущность интеллектуальных систем. Запись математического выражения в виде ориентированного графа. Особенности разработки генетического алгоритма для решения задачи аппроксимации логического вывода экспертной системы на основе метода сетевого оператора.

    дипломная работа [1,0 M], добавлен 17.09.2013

  • Нормальный алгоритм Маркова. Тезис Маркова и машина Тьюринга. Гипотеза теории алгоритмов. Алгоритмически неразрешимые проблемы. Задача эквивалентности двух слов в ассоциативном исчислении. Задача распознавания выводимости. Линейная оценка сложности.

    методичка [57,0 K], добавлен 06.07.2009

  • Логика высказываний и предикатов. Построение таблицы истинности для логической формулы. Обоснование выбора структур данных. Описание алгоритма решения задачи. Описание пользовательского интерфейса. Окно командной строки, для ввода логической формулы.

    курсовая работа [437,7 K], добавлен 10.04.2017

  • Построение систем визуализации моделей раскроя и их модификации. Анализ способов и методов создания универсального хранилища данных, на примере построения динамически формируемого информационного файла. Графические возможностей языка высокого уровня С.

    научная работа [355,5 K], добавлен 06.03.2009

  • Понятие высказывания, операции над простыми высказываниями, таблицы истинности. Примеры построения таблиц истинности сложных высказываний. Таблица истинности импликации. Закон тождества, противоречия, двойного отрицания. Решение логических задач.

    курсовая работа [507,3 K], добавлен 23.04.2013

  • Фурье и Данцига как основоположники методов математического программирования. Знакомство с теорией решения транспортных задач. Анализ способов применения симплекс-метода. Рассмотрение примера решения транспортной задачи в области электроэнергетики.

    презентация [981,0 K], добавлен 28.04.2014

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.