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

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

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

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

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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

AB;

BC;

CE;

EN;

LD;

FG;

IJ;

G&JK;

KL.

Также задано множество выводимых заключений m, состоящее из двух подмножеств m_p и m_n: 1) AEm_p; 2) FCm_p; 3) BEm_n; 4) FNm_n.

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

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

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

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

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

B (D₁);

C (D₂);

E (D₃);

N (D₄);

D (D₅);

G (D₆);

J (D₇);

K (D₈);

L (D₉).

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

1) E (d₁); 2) C (d₂); 3) E (d₃); 4) N (d₄).

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

Цикл 1

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

d^pp=d₁=E (логически следует из множества М и принадлежит m_p);

d^np=d₂=C (не выводится из исходных посылок и принадлежит m_p);

d^pn=d₃=E (принадлежит подмножеству m_n и выводится из М);

dⁿⁿ=d₄=N (принадлежит подмножеству m_n и не выводится из М).

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

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

^np=[M^*₁,M^*₂,M^*₃,M^*₄,M^*₅,M^*₆,M^*₇,M^*₈],

где M^*₁={C}, M^*₂={B}, M^*₃={A,J}, M^*₄={A,I}, M^*₅={A,J}, M^*₆={A,I}, M^*₇={A,J}, M^*₈={A,I}.

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

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

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

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

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

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

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

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

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

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

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

Циклы 2 и 3

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

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

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

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

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

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

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

Цикл 4

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

1) р/р: d₂=C; 2) n/p: d₁=E; 3) n/n: d₃=E, d₄=N.

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

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

B (D₁);

C (D₂);

D (D₅);

G (D₆);

J (D₇);

K (D₈);

L (D₉);

A (D₁₀);

I (D₁₁);

E (D₁₂).

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

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

Заключение

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

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

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

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

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

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

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