6 ВВЕДЕНИЕ
Актуальность темы исследования. В настоящее время интеллектуальные системы получили широкое распространение. В наибольшей степени это утверждение справедливо для экспертных систем, систем поддержки принятия решений, интеллектуальных баз данных, систем распознавания образов. Лучшим подтверждением успешности интеллектуальных систем может служить тот факт, что многие подобные системы перешли в разряд повседневных программ.
Но, несмотря на имеющиеся успехи, остаются и проблемы в разработке интеллектуальных систем. В частности, если система претендует на «интеллектуальность», то она должна обладать развитыми способностями к обучению. В современных интеллектуальных системах наибольшие успехи в обучении достигнуты при использовании нейронных сетей.
Процесс обучения с применением нейросетевых технологий начинается с предъявления системе набора обучающих примеров, состоящих из входных и выходных сигналов. Затем нейронная сеть автоматически подстраивает свои синаптические веса таким образом, что при последующем предъявлении входных сигналов на выходе получаются требуемые сигналы. Недостатком данного подхода являются трудности, возникающие при попытках семантической интерпретации механизмов работы нейронной сети. Кроме того, малоисследованным остается вопрос, каким образом представляются знания в нейронных сетях.
Указанные недостатки отсутствуют в системах на основе баз знаний, использующих для обучения логический вывод (ЛВ). При этом под способностью к обучению понимается возможность создания базы знаний, а также пополнение и модификация правил в базе знаний под влиянием вновь полученной информации.
Большинство современных интеллектуальных систем, использующих ЛВ, позволяет модифицировать базу знаний только в ручном режиме. Поль-
зователь может вносить новые правила и удалять старые, при этом система осуществляет только контроль непротиворечивости информации, а существующая информация никак не учитывается. Возможны ситуации, когда вместо добавления пяти новых правил, без учета уже существующих, требуется добавить всего одно, которое дополняет имеющуюся информацию.
Известные методы формирования знаний (или методы машинного обучения), позволяющие автоматически изменять базу знаний, основаны на применении индуктивного ЛВ. Индукция подразумевает наличие достаточно представительной выборки обучающих примеров, которая обобщается посредством сгенерированных правил.
В связи с этим представляет интерес машинное обучение на основе абдукции, которое позволяет ограничиться небольшим числом наблюдений (от одного) и дает возможность максимального учета существующей в базе знаний информации.
Кроме того, использование абдуктивного вывода позволяет интеллектуальным системам приобрести некоторые свойства, ранее доступные лишь на основе нейросетевого подхода, например, возможность автоматической модификации («настройки») базы знаний под воздействием небольшого набора обучающих заключений, которые должны выводиться (или не выводиться) из посылок этой базы знаний.
Однако в настоящее время абдуктивный вывод в методах формирования знаний либо не применяется, либо используется в качестве вспомогательного.
Таким образом, является актуальной задача разработки методов и средств, основанных на абдуктивном ЛВ, для формирования баз знаний в интеллектуальных системах.
Значительный вклад в разработку и исследование методов обучения интеллектуальных систем внесли М. Л. Цетлин, М. М. Бонгард, Я. 3. Цыпкин, Д. А. Поспелов, В. К. Финн, Г. С. Осипов, В. Н. Вагин, Т. А. Гаврилова, В. Ф. Хорошевский, П. Гаек, Т. Гавранек, С. Осуга (S. Osuga), Ю. Саэки
(U. Saeki), А. Сэмюэль (A. Samuel), Э. Хант (E. Hunt), Д. Марин (J. Marin), Ф. Стоун (P. Stone), P. Михальски (R. Michalski), Д. Карбонелл (J. Carbonell), Т. Митчелл (Т. Mitchell), Д. Куинлан (J. Quintan).
Абдуктивный ЛВ исследовался в работах Ч. С. Пирса (С. S. Pierce), В. К. Финна, В. Н. Вагина, Е. Ю. Головиной, Д. А. Страбыкина, М. Л. Долженковой, Д. Габбая (D. Gabbay), П. Сметса (P. Smets), К. Бутилье (С. Boutilier), П. Флеча (P. Flach), А. Какаса (A. Kakas), К. Иноуэ (К. Inoue), Ч. Сакама (С. Sakama), Дж. Джозефсона (J. Josephson), С. МакИлрайта (S. Mcllraith), Дж. Пола (G. Paul) и др.
Целью исследования является разработка абдуктивных методов модификации посылок в исчислении высказываний и построение на основе этих методов модуля формирования знаний для интеллектуальных систем.
Для достижения указанной цели необходимо разработать:
- метод добавления посылок;
- метод удаления посылок;
- абдуктивный метод модификации посылок;
- структуру, принципы функционирования и критерии эффективности модуля формирования знаний;
- программные реализации абдуктивных методов модификации посылок и интеллектуальных систем с модулем формирования знаний.
Методы исследования. Для достижения поставленной в работе цели использовались методы научного анализа и синтеза, теории множеств, теории графов, математической логики, теории логического и объектно-ориентированного программирования.
Научная новизна исследования состоит в следующем:
- разработан метод добавления посылок в исчислении высказываний, позволяющий находить такие посылки, при добавлении которых в базу знаний требуемое заключение становится выводимым, и отличающийся от известных абдуктивных методов тем, что находится не единственная посылка,
а семейство множеств дополнительных посылок, определяющее различные варианты пополнения базы знаний;
- разработан метод удаления посылок в исчислении высказываний, позволяющий находить такие посылки, при удалении которых из базы знаний требуемое заключение становится невыводимым, и отличающийся от известных методов тем, что находится не единственная посылка, а семейство множеств удаляемых посылок, определяющее различные варианты исключения посылок;
- разработан абдуктивный метод модификации посылок в исчислении высказываний, отличающийся процедурой комбинированного добавления и удаления посылок базы знаний с использованием трех методов ЛВ - дедуктивного вывода, метода добавления посылок и метода удаления посылок, и позволяющий автоматически модифицировать посылки с учетом существующей информации;
- введены операции над семействами множеств дизъюнктов - произведения семейств, дизъюнктивного добавления дизъюнкта к семейству дизъюнктов, конъюнктивного умножения семейства на логическую переменную, позволяющие в результате логического вывода получать не отдельную посылку или множество посылок, а семейство множеств посылок;
- предложены критерии эффективности модуля формирования знаний на основе абдуктивного метода модификации посылок - время обучения при модификации посылок и степень модификации базы знаний, позволяющие проводить сравнение различных реализаций модуля и оценивать степень использования существующей информации при модификации базы знаний.
Практическая ценность исследования состоит в следующих результатах:
- разработаны структура и алгоритм функционирования модуля формирования знаний на основе абдуктивного метода модификации посылок;
- выделены особенности построения и предложены алгоритмы функционирования интеллектуальных систем с модулем формирования знаний;
10
- разработаны программные реализации методов добавления, удаления и модификации посылок;
- разработана программная модель системы поддержки принятия решений с возможностью обучения при помощи модуля формирования знаний;
- разработана программная модель системы обработки знаний для распознавания символов с возможностью обучения посредством модуля формирования знаний.
Внедрение результатов исследования. Полученные теоретические и практические результаты использованы в НИР, выполняемых в рамках гранта РФФИ проект № 06-01-00089-а по тематике «Адаптивные системы логического вывода», а также в учебном процессе Вятского государственного университета и Вятского государственного гуманитарного университета в рамках дисциплин «Теория логического вывода», «Системы искусственного интеллекта», «Основы искусственного интеллекта», «Базы знаний и экспертные системы», что подтверждается соответствующими актами о внедрении.
Апробация работы. Основные положения и результаты исследования докладывались и обсуждались на Всероссийской ежегодной научно-технической конференции ВятГУ «Наука-производство-технологии-экология», г. Киров (2004, 2005, 2006 гг.), на Всероссийской научно-практической конференции «Актуальные проблемы гуманитарных и экономических наук», г. Киров (2004 г.).
Публикации. По теме исследования опубликовано 9 работ, из них 5 статей, 4 тезисов докладов.
Структура и объем исследования. Диссертационная работа состоит из введения, четырех глав, заключения, библиографического списка (включающего 167 наименований) и списка сокращений. Основная часть работы изложена на 203 страницах и содержит 43 рисунка и 3 таблицы.
11
Глава 1. Анализ методов логического вывода и систем обработки знаний
1.1 Методы логического вывода 1.1.1 Формальные системы
Формальная система (ФС) [42, 80] - это четверка вида Ф=<Т, L, Q, R>.
Множество Т - это множество элементов (символов), образующих алфавит. Оно может быть конечным или бесконечным.
Множество L - это множество синтаксически правильных образований из символов алфавита. Такие образования называются формулами. Множество формул обычно задается индуктивным определением, например, с помощью формальной грамматики.
Множество Q состоит из выделенных на основе некоторых соображений формул. Формулы, входящие во множество Q, называются аксиомами. Множество аксиом может быть конечным или бесконечным..
Множество R - это совокупность процедур, позволяющих из одного набора формул получать другой набор. Процедуры называются правилами вывода. Множество правил вывода чаще всего конечно.
1.1.2 Формальная система исчисления высказываний
Рассмотрим ФС ИВ I [97]. Зададим её следующим образом. 1) Алфавит. Символами ИВ I являются:
- символы высказываний (переменные) А, В, С,..., А], В], Сь...;
- значения истинности (константы) 1 - истина (true) и 0 - ложь (false);
- логические связки л (конъюнкция), v (дизъюнкция), -> (отрицание), ь-> (импликация), ¦*-*¦ (эквивалентность), => (знак логического вывода);
12
- служебные символы «(» и «)».
2) Формулы. Формулы ИВ I строятся по следующим правилам:
- любая переменная или константа есть формула;
- если А и В - формулы, то каждое из выражений -iA (А), АлВ, AvB, Аь->В, А+-+В есть формула;
- других правил образования формул нет.
3) Аксиомы. В качестве аксиом используются следующие схемы формул (X, Y, Z - любые формулы):
- Xf->X;
- XaYh>YaX;
- (XvY)aZh>XaZvYaZ.
4) Правила вывода.
. , . X,XH>Y
- Modus ponens—-----;
- Modus toilens--=-*—;
X
- Правило переноса.
а) В выражении рлХн-^Y конъюнктивный сомножитель р может быть перенесен через знак «ь-»>. При этом он инвертируется и дизъюнктивно складывается с формулой Y:
р aXi-^Y=>Xh»Yv р.
б) В выражении Xf-»Yvq дизъюнктивное слагаемое q может быть перенесено через знак «ь-»>. При этом оно инвертируется и конъ-юнктивно умножается на формулу Y;
Правило разъединения-соединения, а) Для конъюнктивных сомножителей:
б) Для дизъюнктивных слагаемых:
13
Для упрощения записи формул введем некоторые соглашения.
- Будем всегда опускать внешние скобки.
- В целях сокращения числа внутренних скобок в формулах воспользуемся правилами силы операций. Перечислим введенные логические связки в порядке убывания их силы: —¦, л, v, ь->, «->.
- Если запись формулы не вызывает разночтений, то не будем указывать знак конъюнкции, записывая соединяемые им формулы рядом без интервала.
Введем ряд определений.
Переменную или её отрицание будем называть литералом.
Формулу вида Xb>Y назовем секвенцией. Причем X - тело, или антецедент секвенции, a Y — голова, или консеквент.
Аксиомы и правила вывода предложенного исчисления позволяют преобразовать любую формулу исчисления в секвенцию, в антецеденте которой содержится конъюнкция, а в консеквенте - дизъюнкция переменных.
Секвенцией-дизъюнктом называется секвенция, в теле которой находится константа «1», а голову составляет дизъюнкция литералов.
Доказательством в ФС ИВ I называется конечная последовательность секвенций, каждая из которых или является аксиомой исчисления, или получена из предыдущей секвенции по одному из правил вывода ФС. Заключительная секвенция такой последовательности называется доказуемой секвенцией, или теоремой. Формула X называется доказуемой в исчислении I, если доказуема секвенция 1н>Х.
Выводом секвенции SN из множества Н секвенций в исчислении I называется последовательность секвенций Si, S2, ...Sj, ..., Sn, в которой каждая секвенция S; либо является аксиомой исчисления I, либо принадлежит множеству Н, либо получена из предыдущих секвенций по одному из правил вывода исчисления I.
14
При этом секвенции множества Н называется посылками (исходными посылками, исходными секвенциями), секвенция Sh называется логическим следствием секвенций множества Н.
Схемой вывода логического следствия называется ориентированный граф, вершинами которого являются номера секвенций посылок, причем входящие дуги помечены переменными или константами из левых, а исходящие - из правых частей секвенций, и вершины соединены между собой (рис. 1.1).
G
К
Рис. 1.1. Схема вывода 1.1.3 Классификация методов логического вывода
Существует множество способов классификации методов ЛВ, например по форме представления данных, направленности, используемым логическим законам, принципам доказательств теорем и т. д. [97]. Для целей настоящего исследования представляется полезным следующий способ классификации методов ЛВ (см. рис. 1.2).
15
Методы логического вывода
Достоверный
Дедуктивный вывод
Метод резолюции
Процедура Эрбрана
Вывод на графах
Метод деления дизъюнктов
Правдоподобный
Индуктивный вывод
CrpyKTypI 10-
логнческне методы
Признаковые методы
Вывод по аналогии
Вывод, основанный на прецедентах
Структурная аналогия
Абдуктивный вывод
Подход на основе покрытия множеств
Подход на основе логики
Подход на уровне знаний
Вероятностный подход
Рис. 1.2. Классификация методов логического вывода
Все методы ЛВ делятся на два вида - достоверный и правдоподобный. Достоверный ЛВ - это ЛВ в традиционном понимании математической логики. В достоверном ЛВ применяются только такие правила вывода, которые позволяют из набора исходных истинных формул получить лишь истинные формулы-заключения [46]. К достоверному выводу относится дедуктивный логический вывод (ДЛВ), представленный множеством.методов. Самый распространенный на сегодняшний день - метод резолюции. Также можно назвать метод Эрбрана, различные виды методов вывода на графах, метод деления дизъюнктов (ДД) и т. д. [18, 97].
В разделе 1.1.4 будет рассмотрен один из методов достоверного ЛВ, применяемый в данной работе, а именно, метод ДД.
Термин «правдоподобное рассуждение» введен Д. Пойа [74]. В правдоподобном ЛВ используются такие правила вывода, которые позволяют из набора исходных истинных формул получить формулы, об истинности которых можно говорить лишь с некоторой долей уверенности. Такой тип рассуждений свойствен человеку и моделирует, например, здравый смысл, рассужде-
16
ния в условиях неопределенности или противоречивости информации. Основными формами правдоподобного ЛВ считаются индуктивный логический вывод (ИЛВ), вывод на основе аналогии и абдуктивный логический вывод (АЛВ). При необходимости можно дополнить этот список такими видами рассуждений, как вероятностный вывод, рассуждения с учетом необходимых условий, рассуждения с учетом возможностей и др. [74, 80].
Индукция обеспечивает возможность перехода от единичных фактов к общим положениям, законам [18]. ИЛВ включает структурно-логические методы, признаковые методы и т. д. Эти и некоторые другие методы индукции будут рассмотрены в разделе 1.3.2.
Рассуждение на основе аналогии можно определить как метод, позволяющий понять некоторую сложившуюся ситуацию в сравнении с другой подобной ситуацией [105]. Вывод на основе аналогий включает методы, основанные на прецедентах (Case-Based Reasoning, CBR), структурной аналогии и т. д. [74, 80,138,155].
АЛВ позволяет сгенерировать гипотезы относительно неизвестных фактов исходя из набора исходных фактов и правил. В абдукции могут применяться следующие подходы: на основе покрытия множеств, на основе логики, на уровне знаний, а также вероятностные подходы. АЛВ подробно рассматривается в разделе 1.1.5.
1.1.4 Метод деления дизъюнктов
В данной работе в качестве базового метода ЛВ выбран дедуктивный метод ДД [97]. Выбор обусловлен следующими причинами:
1) метод ДД является двунаправленным, что позволяет применять его при решении задачи абдукции;
2) метод ДД уменьшает время вывода по сравнению с другими методами, например, резолюционными;
3) метод ДД легко поддается распараллеливанию;
17
4) существует несколько работ, посвященных применению данного метода для решения задач ЛВ, в том числе абдукции, например [38, 95]. Однако в этом направлении остается ряд нерешенных проблем.
Метод вывода ДЦ предназначен для решения следующей задачи: установить, существует ли для заданного множества посылок M={DbD2,...,Di,...,D[}, представленных выражениями ИВ I, логический вывод заключения d, также представленного выражением исчисления I.
В методе ДД посылки и заключения представлены в виде секвенций-дизъюнктов. В левой части таких секвенций находится константа 1, а в правой - дизъюнкция литералов. Исходные выражения приводятся к требуемому виду с помощью правил переноса и разъединения-соединения (см. раздел 1.1.2). Основу метода составляют операция ДД и процедура вывода.
Операция деления дизъюнктов
Обозначим множества литералов, входящих соответственно в дизъюнкты Di и d, через 5(={ЬИ, Li2,..., Ly, ...Lu}, d={Lb L2,..., Lk,..., LK}.
Операция деления дизъюнкта D на дизъюнкт d, результатом которой является остаток Ь, записывается так: D-rd=b. Операция представляет собой исключение из дизъюнкта D литералов, содержащихся в дизъюнкте d. Результат операции - остаток b - определяется по следующим правилам:
1) Если D n d =0 (дизъюнкты не имеют одинаковых литералов), то Ь=1.
2) Если Dc d (дизъюнкт D совпадает с дизъюнктом d или является его частью), то Ь=0.
3) Если Dnd Ф 0 и D-d=b', bV0, то b=L1vL2v...vLsv...vLs, где
Lseb'(s=l,...,S)Hb'={LbL2,...,Ls}.
Процедура вывода
Введем ряд обозначений.
V - <М, d, q, Мь m> - процедура ДД, в которой
М = {Di, D2,..., Dj,..., Dj} - множество дизъюнктов исходных секвенций;

Получить работу