«Разработка и исследование метода релевантного обратного вывода ...»

Воронежский государственный университет

На правах рукописи

БОЛОТОВА Светлана Юрьевна

Разработка и исследование метода релевантного

обратного вывода

специальность 05.13.17 –

теоретические основы информатики

ДИССЕРТАЦИЯ

на соискание ученой степени

кандидата физико-математических наук

Научный руководитель – доктор физико-математических наук, доцент С.Д. Махортов Воронеж – 2013 2 Оглавление Введение

Глава 1. Основы теории LP-структур

1.1. Базовые сведения о бинарных отношениях и решетках......... 1.2. Понятие LP-структуры. Логические отношения

1.3. Логическое замыкание и эквивалентные преобразования..... 1.4. Структура логических связей

1.5. Логическая редукция

1.6. Продукционно-логические уравнения

Глава 2. Релевантный обратный вывод

2.1. Продукционная система и ее представление LP-структурой 2.2. Обратный вывод на основе решения уравнений

2.3. Алгоритмы релевантного вывода

2.4. Стратегии подсчета релевантности

2.5. Использование параллельных вычислений

Глава 3. Компьютерная реализация

3.1. Общие принципы реализации

3.2. Кодирование LP-структур

3.3. Архитектура класса ParallelLPStructure

3.4. Основная функциональность LP-структуры

3.5. LPExpert – новая версия IDE

Глава 4. Статистический анализ

4.1. Основные теоретические сведения

4.2. Исследование алгоритма релевантного LP-вывода.............. 4.2.1. Сравнение дисперсий генеральных совокупностей........ 4.2.2. Сравнение средних генеральных совокупностей............ 4.2.3. Исследования в пакете Statistica 6

4.3. Исследование кластерно-релевантного LP-вывода.............. 4.4. Применение пропорционального подсчета релевантности. 4.5. Исследование выполнения параллельных алгоритмов........ 4.5.1. Сравнение дисперсий генеральных совокупностей........ 4.5.2. Сравнение средних генеральных совокупностей............ 4.5.3. Исследования в пакете Statistica 6

4.6. Выводы

Заключение

Приложение A. Таблицы результатов тестов

A.1. Тесты релевантного вывода

A.2. Тесты кластерно-релевантного вывода

A.3. Тесты пропорционального подсчета релевантности........... A.4. Тесты параллельных алгоритмов

Приложение B. Некоторые тексты программ

B.1. Модули класса ParallelLPStructure

B.2. Подсчет релевантности

Литература

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

Указанное обстоятельство порождает неуклонно возрастающую зависимость общества от уровня эффективности и надежности информационных систем, обеспечивающих процессы его жизнедеятельности. Информационные системы становятся глобальными, эволюционирующими, социокритическими, экологически опасными [109]. Соответственно возрастают риски чрезвычайных ситуаций, экологических катастроф, материальных и других потерь национальных масштабов [75–76].

Ответом на подобные вызовы современности служат применяемые в процессах разработки инновационные решения, повышающие эффективность, надежность и безопасность. К таким решениям вполне могут быть отнесены методы интеллектуализации информационных систем [108].

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

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

Подобные системы характеризуются, в частности, способностью «логически мыслить», то есть осуществлять логический вывод (прямой или обратный) некоторых фактов или решений на основе формальной логики [73].

Однако формальные логики и соответствующие им процессы логического вывода нередко обладают весьма ресурсоемкой архитектурой, как правило, имеющей экспоненциальный или NP-полный характер [77, 106], как с точки зрения требуемого объема памяти, так и сложности вычислений [7–8].

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

Интеллектуальные системы продукционнoго типа представляют важное направление исследований в области искусственного интеллекта. Они используются в теории обучающих систем, систем принятия решений, а также при разработке практических экспертных систем, охватывающих различные прикладные области, такие как медицина, проектирование, геологоразведка и другие [16]. Уже прошедшие пик интереса со стороны исследователей в 80–90 годах, они все же остаются достаточно актуальными, что подтверждается значительным числом публикаций последних лет, посвященных как их теоретическим исследованиям, так и решению прикладных задач [4–6, 24–25, 28, 29, 31, 39, 45, 53, 65, 68, 72, 89].

Роль аппарата продукционно-логических систем как актуального предмета исследований повышается и другими факторами. В работе [94] Д.А Поспелов рассматривает системы продукций в широком смысле, как основу для моделирования рассуждений в архитектуре ЭВМ, роботах, экспертных системах и т.д. В последние годы в ряде публикаций [83, 85] был показан и изучен продукционный характер многих различных моделей в информатике, в том числе – непосредственно не относящихся к области искусственного интеллекта. Кроме того, имея относительно несложную структуру, системы продукционного типа могут привлекаться в качестве стартового «полигона» для создания и изучения методов управления формальными знаниями, которые в дальнейшем могут быть применены и для построения более сложных интеллектуальных систем.

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

Эффективным средством формального построения и исследования компьютерных программ, основанных на различных парадигмах, являются алгебраические системы [67, 90, 93]. Это положение в полной мере относится к логическому программированию, особенно в части представления знаний [88]. Алгебраическим методам представления знаний посвящены статьи [38, 43], а также монографии [54, 104].

Математическую основу для создания и исследования моделей знаний предоставляет алгебраическая логика. Ее начала были заложены в работах монографиях [20, 95]. Теория Линденбаума-Тарского рассматривает логику соответствуют логическим связкам пропозиционального языка. Примеры алгебраического представления предикатов первого порядка представляют полиадические алгебры Халмоша [19] и цилиндрические алгебры ХенкинаТарского [22]. Обзор методов алгебраизации кванторов содержится в монографии [36].

практического применения. В силу своей универсальности она не решает важных частных проблем, связанных с упомянутыми выше логическими системами продукционного типа. На это обстоятельство, в частности, указывается в книгах [91, 105]. К задачам такого рода относятся вопросы эквивалентных преобразований, верификации продукционных и подобных им систем, рассматривавшиеся частными методами в работах [1, 14, 26, 30, 37]. Общие обзоры имеющихся подходов к верификации знаний содержатся в [17, 100].

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

Возможности алгебраического исследования продукционно-логических систем содержит теория ультраоператоров А.В.Чечкина [107]. В приложении к математической логике она предлагает рассматривать импликации в виде отдельного соответствия. Однако в печати не представлены исследования ультраоператоров, связанные со свойством транзитивности логического вывода.

В работах С.Д. Махортова [80–81] была сформулирована основанная на решетках новая алгебраическая теория (LP-структур). Она представляет общую модель продукционно-логических систем широкого спектра. Данная теория позволяет с единых позиций рассматривать и успешно решать перечисленные выше задачи. Одно из направлений ее применения – оптимизация обратного продукционно-логического вывода и связанная с ним верификация знаний. В частности, в работе [86] высказана принципиально новая идея о минимизации числа обращений к внешним устройствам в процессе обратного вывода и указан способ ее реализации (релевантный LPвывод). Поскольку время обмена данными с внешними устройствами и, тем более, интерактивным пользователем, на порядки превышает время выполнения команд процессором, отмеченное направление оптимизации способно принести качественно новые результаты.

Данная идея не пересекается с известными методами быстрого вывода в продукционных системах, а дополняет их. Алгоритмы RETE [13] и TREAT [32] разработаны для стратегии прямого вывода и использовались в продукционных системах с прямым выводом (например, OPS5 [12], CLIPS [23]). Алгоритм LEAPS [33] компилирует множество правил продукционной системы OPS5 в язык C. В последующих модификациях наиболее (двунаправленного) вывода [23, 27]. Предложенная в статье [81] и развиваемая в настоящей диссертации концепция использования уравнений в LP-структурах предназначена для оптимизации исключительно обратного вывода с точки зрения минимизации обращений к внешним устройствам.

Она не требует для своей реализации громоздких структур данных, потребности в прямом (либо смешанном) выводе. Кроме того, можно адаптировать имеющиеся ускоренные алгоритмы обратного вывода (например, [60, 68]) для решения рассматриваемых в работе продукционнологических уравнений. Такой подход может оказаться интересным направлением дальнейшего развития теории LP-структур и ее приложений.

Далее отметим, что в упомянутых выше работах С.Д. Махортова релевантный LP-вывод остался практически на уровне общей идеи. В этих статьях, в частности, не были рассмотрены и сопоставлены различные стратегии выбора параметров релевантности. Не было проведено ни достаточного количества тестов, ни, тем более, каких-либо статистических исследований, которые могли бы действительно обосновать и оценить эффективность LP-вывода. Наконец, в представленной ранее его реализации не использовались параллельные вычисления, которые, безусловно, могли еще более повысить быстродействие нового метода.

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

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

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

Данные положения непосредственно отражены в формуле и паспорте научной специальности 05.13.17 – Теоретические основы информатики (пп.

4, 8, 14).

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

Объектом исследования являются продукционно-логические системы.

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

Научная новизна диссертации заключается в следующих положениях.

Сформулирована и исследована обобщенная модель LP-структуры, усовершенствована схема процесса решения продукционно-логического уравнения.

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

Предложены и апробированы различные способы выбора параметров релевантности для процессов релевантного и кластерно-релевантного LPвывода.

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

Проведено подробное исследование полученных результатов методами математической статистики. Таким образом формально обоснованы модификациях.

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

практического применения установленных в ней теоретических результатов.

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

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

Результаты диссертации докладывались на следующих научных конференциях и семинарах:

IV Международной научной конференции «Современные проблемы прикладной математики, теории управления и математического моделирования» (ПМТУММ-2011) (Воронеж, 2011);

III Всероссийской конференции с международным участием «Знания – Онтологии – Теории» (ЗОНТ-2011) (Новосибирск, 2011);

X Всероссийской научной конференции «Нейрокомпьютеры и их применение» (НКП-2012) (Москва, 2012);

Международной молодежной конференции-школе «Современные проблемы прикладной математики и информатики» (MPAMCS’2012) (Дубна, 2012);

V Международной научной конференции «Современные проблемы прикладной математики, теории управления и математического моделирования» (ПМТУММ-2012) (Воронеж, 2012);

Международной конференции «Актуальные проблемы прикладной математики, информатики и механики» (Воронеж, 2012);

XI Всероссийской научной конференции «Нейрокомпьютеры и их применение» (НКП-2013) (Москва, 2013);

International Conference “Distributed Intelligent Systems and Technologies (DIST’2013)” (St. Petersburg, July 1–4, 2013);

International Conference “Mathematical Modeling and Computational Physics” (MMCP’2013) (Dubna, July 8–12, 2013);

Всероссийской конференции с международным участием «Знания – Онтологии – Теории» (ЗОНТ-2013) (Новосибирск, 2013);

научном семинаре «Проблемы современных вычислительных систем»

механико-математического факультета МГУ имени М.В. Ломоносова, рук. В.А. Васенин (Москва, 2013);

а также научных сессиях Воронежского госуниверситета (2011–2013).

По теме диссертации опубликовано 14 научных работ, список которых приведен в ее заключительной части. Статьи [1–4] соответствуют Перечню ВАК РФ. Опубликованные работы вполне отражают содержание диссертации.

Получено свидетельство о регистрации компьютерной программы [15].

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

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

В первой главе излагаются базовые положения общей теории LP-структур.

Первоначально они были введены и обоснованы в работах С.Д. Махортова. В этой главе они получили уточнение и развитие. Представленные здесь результаты основаны на более слабых по сравнению с работой [80] условиях LP-структуру.

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

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

Далее описаны алгоритмы параллельного решения указанных задач.

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

В третьей главе описана компьютерная реализация методов релевантного и кластерно-релевантного обратного вывода. Обсуждаются принципы кодирования решеток и LP-структур, используемые для эффективной программной реализации. Представлена архитектура объектно-ориентированного класса ParallelLPStructure, инкапсулирующего свойства и методы описанной в главах 1– теории LP-структур, включая нахождение логической редукции и решение продукционно-логических уравнений с параллельным вычислением прообразов.

Описывается созданная автором новая версия интегрированной среды разработки и эксплуатации продукционных систем LPExpert, использующая класс ParallelLPStructure. Основные расширения возможностей LPExpert таковы:

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

Четвертая глава содержит описание проведенных массированных экспериментов, в том числе со случайно генерируемыми базами знаний. Они призваны создать достаточный объем данных для исследования методами математической статистики. Таким образом, формально обосновываются преимущества новой методологии обратного вывода в различных ее модификациях.

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

Глава 1. Основы теории LP-структур Последующие главы диссертации будут посвящены моделированию и исследованию продукционно-логических систем, в части обратного вывода и верификации знаний, с применением специального класса алгебраических LP-структур. Понятие LP-структуры представляет собой абстрактное описание теоретико-множественной модели продукционной системы. Такое обобщение достигается использованием математических решеток в качестве основы алгебраической системы. На решетке задается бинарное отношение, содержащее семантику продукционно-логического вывода.

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

Махортова [80–81]. Теория была названа общей, поскольку дальнейшие исследования в области LP-структур [82, 85, 87] основаны на тех же положениях, продолжая их в том или ином специальном направлении.

В настоящей главе указанные положения получили уточнение и развитие.

Представленные здесь результаты основаны на более слабых по сравнению с работами [80–81] условиях на LP-структуру. Основное изменение связано с использованием в формулируемых построениях вместо решеточного отношения частичного порядка, отношения вида R, содержащего лишь необходимое для исследования отношения R подмножество в основных определениях, формулировках теорем и доказательствах.

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

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

Пусть R – бинарное отношение на некотором множестве F. Для каждой упорядоченной пары (a, b) R элемент a будем называть ее левой частью, а элемент b – правой частью. Бинарное отношение R на произвольном множестве F называется:

рефлексивным, если для любого a F справедливо (a, a) R ;

транзитивным, если для любых a, b, c F из (a, b),(b, c) R следует Напомним, что для частично упорядоченных множеств различаются понятия минимального элемента (для него нет меньшего элемента) и наименьшего элемента (он меньше всех) [55].

Как известно, существует замыкание R* произвольного отношения R относительно свойства транзитивности – транзитивное замыкание.

Транзитивная редукция отношения R означает минимальное отношение R' такое, что его транзитивное замыкание совпадает с транзитивным замыканием R.

ориентированных графов. Доказано, что эта задача вычислительно эквивалентна построению транзитивного замыкания, а также установлена единственность транзитивной редукции ациклического графа. Как показано в [40], построение наименьшей транзитивной редукции произвольного графа является NP-полной задачей.

Решеткой больше», «содержится»), на котором для любой пары элементов определены операции («пересечение») и точная нижняя грань элементов a, b, то есть наибольший элемент решетки, удовлетворяющий неравенствам c a и c b. Соответственно d a b – точная верхняя грань a, b, то есть наименьший элемент решетки, для которого выполнено a d и b d. Таким образом, при любых a, b справедливо:

Пример решетки – множество ( F ) всех конечных подмножеств некоторого универсума F.

Решетка называется ограниченной, если она содержит общие нижнюю и верхнюю грани, а именно – такие два элемента O, I, что O a I для любого a. Пример ограниченной решетки – булеан 2 F (множество всех подмножеств) на некотором универсуме F.

Атомом ограниченной (снизу) решетки называется минимальный элемент ее подмножества \ {O}. Решетка называется атомно порожденной, если каждый ее элемент представим в виде объединения атомов. Например, в булеане атомы – это все подмножества, состоящие ровно из одного элемента универсума. Таким образом, булеан является атомно порожденной решеткой.

Для атома a элемента A будем также использовать обозначение a A (наряду с a A ).

Решетка называется дистрибутивной, если в ней при любых a, b, c выполняются следующие равенства:

Можно показать, что каждое из этих тождеств следует из другого [102].

Под дополнением элемента a в ограниченной решетке подразумевают элемент a ' такой, что a a ' O и a a' I. Ограниченная решетка, в которой любой элемент имеет дополнение, называется решеткой с дополнениями. Решетка, в которой каждый замкнутый интервал является решеткой с дополнениями, называется решеткой с относительными дополнениями.

Дистрибутивная решетка с дополнениями называется булевой. В булевой решетке каждый элемент имеет единственное дополнение, причем справедливы тождества (законы де Моргана):

Приведем одно полезное утверждение, относящееся к общей теории решеток и отношений. Пусть дана решетка. Пусть c – некоторое свойство, сформулированное для элементов. Произвольный элемент A может обладать или не обладать этим свойством.

Замыканием элемента A относительно свойства c называется элемент c( A), являющийся наименьшим в подмножестве элементов решетки, которые содержат A и обладают свойством c.

Замыкание произвольного элемента A в приведенной формулировке существует не для любого свойства c. В качестве отрицательного примера можно привести свойство на булеане «множество содержит не менее n элементов» при мощности A, меньшей n. Если такое замыкание существует, то в силу определения оно должно быть единственным.

Лемма 1.1.1. [80] Пусть A1, A2 и существуют их замыкания c( A1 ), c( A2 ) относительно некоторого свойства c. Пусть также выполнены условия:

1.2. Понятие LP-структуры. Логические отношения Под LP-структурой [82] подразумевается алгебраическая система, представляющая решетку, на которой задано дополнительное бинарное отношение, обладающее некоторыми продукционно-логическими свойствами. Решетка в контексте данного определения рассматривается в широком смысле, и ее тип может уточняться в конкретных моделях.

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

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

-дистрибутивным, если из (a, b1 ),(a, b2 ) R следует (a, b1 b2 ) R ;

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

В настоящей работе в качестве основы LP-структур рассматриваются подмножеств F ) или булеан 2 F (множество всех подмножеств F ).

обозначаются, как правило, большими буквами. Под дистрибутивностью отношения подразумевается лишь второе из двух указанных выше свойств. В такой нотации -дистрибутивность трактуется в следующем смысле: из ( A, B1 ),( A, B2 ) R следует ( A, B1 B2 ) R. Именно это свойство в контексте диссертации называется дистрибутивностью отношения R.

Совокупность всех атомов решетки, содержащихся в элементах пар отношения R, будем называть множеством атомов, которыми оперирует отношение R. Построенное на объединениях этих атомов подмножество Для заданного R введем бинарное отношение R – такое подмножество решеточного частичного порядка, что элементы всех пар R принадлежат. Обозначим также R подмножество R, не содержащее рефлексивных пар (вида ( A, A) ).

Итак, в рамках настоящей работы действует следующее определение.

Определение 1.2.1. Бинарное отношение R на решетке называется продукционно-логическим (или просто логическим), если оно содержит R, дистрибутивно и транзитивно.

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

монотонным отношениям. Аналогично [80] можно показать, что при определении логического отношения условие дистрибутивности можно заменить условием монотонности:

Под LP-структурой подразумевается решетка с заданным на ней логическим отношением.

1.3. Логическое замыкание и эквивалентные преобразования Подобно транзитивным замыканию и редукции отношения на обычном множестве, в теории LP-структур рассматриваются и решаются более сложные задачи нахождения логического замыкания и логической редукции отношений на иерархических множествах – различных видах решеток.

Логическим замыканием заданного на решетке произвольного бинарного отношения R называется наименьшее продукционно-логическое отношение, содержащее R.

В работе [80] решен вопрос о существовании логического замыкания произвольного отношения в терминах той работы. Здесь рассматривается аналогичная задача в менее строгой постановке (в смысле определения 1.2.1).

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

говорить, что упорядоченная пара A,B логически связана отношением R (обозначим этот факт A B ), если выполнено одно из следующих условий:

Определение 1.3.1 по заданному R формулирует еще одно бинарное отношение на решетке логическая связь A B образуется на основе некоторого конечного подмножества пар отношения R. Важно также отметить, что отношения R и оперируют общим множеством атомов решетки.

Условия 1)–4) определения 1.3.1 будем также называть правилами вывода в LP-структуре. При выводе логической связи A B шагом вывода будем называть применение ровно одного правила, возможно, одновременно к некоторому конечному множеству элементов решетки. Например:

если Ai Bi1, Ai Bi2, i =1,..., n, то Ai Bi Уровнем рекурсии в соотношении A B будем называть количество шагов вывода, необходимое для получения этой связи. При этом учитываются лишь применения правил 3)–4) определения 1.3.1. Для связи по правилу 1) или 2) уровень рекурсии считается равным нулю.

Поскольку в общем случае связь A B может быть получена не единственным набором правил, обычно будем лишь оценивать сверху ее уровень рекурсии, не указывая его точного значения.

употреблять слова «начальный», «последний», а также «предыдущий», «следующий» и т.д. При этом имеется в виду продвижение в направлении прямого логического вывода, то есть от пар исходного отношения ( R R ) к выводимой паре отношения. Заметим, что рекурсивное определение 1.3.1 сформулировано в контексте обратного вывода.

Лемма 1.3.1. Пусть R – логическое отношение на решетке и A, B.

Тогда, если справедливо A B, то ( A, B) R.

Доказательство. Проведем его с помощью индукции по m – верхней оценке уровня рекурсии в соотношении A B. При m 0 имеет место одно из условий 1)–2) определения 1.2.1. Случай 1) непосредственно означает требуемое утверждение. Если же справедливо 2), то и тогда ( A, B) R, поскольку логическое отношение R по определению содержит такие пары.

Предположим далее, что лемма верна при некотором m 0, и докажем ее утверждение при уровне m 1. В этом случае новые для рассмотрения варианты могут дать правила 3)–4).

Если имеет место 3), то по предположению индукции уровень рекурсии в соответствующих соотношениях A B1, A B2 не превосходит m, поэтому ( A, B1 ) R,( A, B2 ) R. Тогда, в силу свойства дистрибутивности логического отношения R, получим ( A, B) R. Вариант происхождения связи A B из условия 4) рассматривается аналогично.

Теорема 1.3.1. Для произвольного бинарного отношения R на решетке логическое замыкание существует и совпадает с множеством всех упорядоченных пар, логически связанных отношением R.

Доказательство. Покажем, что при произвольном отношении R соответствующее отношение является логическим. Действительно, в силу п.2) определения 1.3.1 оно содержит вложения, из п.3) следует его дистрибутивность, а п.4) означает транзитивность данного отношения. Далее, в силу п.1) определения 1.3.1, отношение R доказательства теоремы осталось показать, что это – наименьшее из таковых отношений.

Пусть R' – другое логическое отношение, содержащее R. Тогда очевидно, что если A B, то A B. Отсюда по лемме 1.3.1 имеем (a, b) R '.

Следовательно, отношение содержится в произвольно выбранном R', и поэтому является наименьшим логическим отношением, содержащим R.

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

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

Два отношения R1, R2 называются эквивалентными, если их логические замыкания совпадают. Для таких отношений используется обозначение R1 ~ R2. Эквивалентным преобразованием данного отношения называется некоторая замена подмножества его пар, приводящая к эквивалентному отношению.

эквивалентно R.

Доказательство. Заметим вначале, что отношения R и R' оперируют общим множеством атомов решетки, отсюда R R '. Далее, по определению любое логическое отношение является собственным же логическим замыканием. Такой вывод в силу теоремы 1.3.1 относится и к отношению. Далее, из определения 1.3.1 следует, что для любых R1 R справедливо В нашем случае по построению отношения R' выполнены включения R R '. Переходя к логическим замыканиям и учитывая сказанное выше, получаем, что отношения R и R' имеют общее логическое замыкание.

Теорема 1.3.2. Пусть R1, R2, R3, R4 – отношения на общей решетке. Если Доказательство. Из условия теоремы нетрудно заметить, что отношения соотношение двух множеств. Пусть A B. Докажем, что при этом справедливо A B. Для этого вновь применим метод индукции по m – верхней оценке уровня рекурсии в соотношении A B.

При m 0 имеет место одно из условий 1)–2) определения 1.3.1. Если справедливо 2), то тогда A B, поскольку логическое отношение содержит необходимые включения. Если выполнено условие 1), то R2 R ( A, B ) R3 симметричен). В этом случае имеет место A B, откуда в утверждение доказано.

Предположим далее, что оно верно для некоторого m 0, и докажем его при уровне рекурсии не превосходящем m 1. В этом случае новые для определения 1.3.1.

Если имеет место 3), то по предположению индукции уровень рекурсии в соответствующих соотношениях A B1, A B2 не превосходит m, поэтому ( A, B1 ) R,( A, B2 ) R. Тогда, в силу свойства дистрибутивности логического отношения R, получим ( A, B) R. Аналогично рассматривается случай применения правила 4).

Следствие 1.3.2. Пусть R1, R2, R – отношения на общей решетке. Если при Следствие 1.3.2 обосновывает принцип локальности эквивалентных преобразований логических отношений: если часть данного отношения заменить эквивалентной частью, то и в целом новое отношение будет автоматических преобразований баз знаний.

Лемма 1.3.2. Пусть R – отношение на решетке отношение R, полученное из R заменой пары ( A, B) совокупностью всех пар ( A, Bi ), эквивалентно R.

Доказательство. Из условия леммы следует, что оба сравниваемых отношения ( R и R ) оперируют общим множеством атомов решетки, т.е.

замыкания и отношений R1 и R2 соответственно. Нетрудно также увидеть, что R1 = R2. Поскольку по определению содержит отношение R1, то в силу своей транзитивности оно включает и R2, то есть R2. С другой стороны, отношение из-за дистрибутивности включает R1. Таким образом, R1 и R2 как элементы решетки отношений удовлетворяют лемме 1.1.1. По этой лемме имеем =. Последний факт означает, что отношения R1 и R2 эквивалентны. Применяя теперь к R1, R2, R следствие 1.3.2, получим, что R заменить совокупностью пар {( A, B1 ),...,( A, Bn )}, то полученное отношение R будет эквивалентно исходному R.

Доказательство. По-прежнему важно заметить, что оба сравниваемых отношения ( R и R ) оперируют общим множеством атомов решетки, т.е.

. Согласно лемме 1.3.2, описанная замена одной пары или конечного их числа приводит к эквивалентному отношению. В этой связи сомнения может вызывать лишь замена в R бесконечного подмножества пар. Для прояснения этого случая рассмотрим логические замыкания и отношений R и R. Пусть A B. Согласно определению 1.3.1, любая подобная логическая связь формируется на основе некоторого конечного числа пар ( Ai, Bi ) R, i 1,..., n. Эту совокупность пар можно рассматривать Проведем для R1 все описанные в условии теоремы замены. Так как рассматриваются лишь конечные объединения, то получим некоторое конечное отношение R2. Как замечено в начале доказательства, R1 R2, отсюда следует A B. Поскольку при этом, очевидно, R R2, то имеем A B. Таким образом,.

Для доказательства обратного включения ( ) рассмотрим упорядоченную пару A B. По определению 1.3.1 данная логическая связь реализуется посредством некоторого конечного числа пар ( Aj, B j ) R, j 1,..., m. Множество пар {( Aj, B j )} может быть получено применением описанной в условии теоремы процедуры к некоторому конечному R1 R, состоящему не более чем из m пар. При этом оно содержится в соответствующем конечном множестве R2 R, полученном из R1. Остальные рассуждения аналогичны первой части доказательства.

В качестве применения перечисленных выше результатов рассмотрим важный частный случай эквивалентного преобразования. Отношение R на атомно-порожденной решетке называется каноническим, если оно задано множеством пар вида ( A, a), где A, a – атом в.

Следствие 1.3.3. Согласно теореме 1.3.3, для любого отношения на атомно-порожденной решетке существует эквивалентное ему каноническое отношение.

1.4. Структура логических связей В следующем подразделе будет выясняться вопрос о возможности в позволит свести изучение некоторых важных вопросов, касающихся логических отношений, к соответствующим проблемам транзитивных отношений. В частности, построение логического замыкания или редукции можно будет осуществлять с помощью быстрых алгоритмов (типа Уоршолла [2, 46–47]).

С указанной целью исследуем ряд свойств продукционно-логических связей на решетке.

Лемма 1.4.1. Пусть R – отношение на решетке и Ai Bi, i 1,..., n.

A Ai, i 1,..., n, то в силу Ai Bi и условия 4) определения 1.3. справедливо A Bi, i 1,..., n. Применяя к последнему соотношению правило 3), получим A B.

Следствие 1.4.1. На основе леммы 1.4.1 можно ввести обобщенное если выполнено следующее условие:

Очевидно, что правило 3) определения 1.3.1 является частным случаем правила 3 ' ).

любой логической связи A B все применения правила 3 ' ) могут быть произведены без участия правила 2) определения 1.3.1 со строгим вложением R. Роль последнего можно свести к присутствию лишь в качестве компонента для транзитивного правила 4).

Доказательство. Предположим, что при получении вывода A B {( Ai, Bi ) | i 1,..., n} на 2 подмножества. В первое из них войдут такие пары подмножеству отнесем все остальные пары ( Aj, B j ), j 1,..., n2. Тогда, вводя обозначения по условию 3 ' ) имеет место A2 B2. Очевидно, что указанное выше применение правила 3 ' ) для {( Ai, Bi ) | i 1,..., n} можно заменить аналогичным правилом для ( A1, B1 ),( A2, B 2 ).

Если при этом окажется, что n1 0, то для данного вывода A B выполнено сразу. Если же n2 0 либо A2 R B 2, то применение правила 3 ' ) не требуется вовсе. Рассмотрим оставшийся нетривиальный случай ( n1 0, n2 0 и не выполнено a 2 R b2 ), в котором поступим следующим образом. Применим правило 3 ' ) к соотношениям B1 B1, A2 B 2, B 2 транзитивное правило 4), приходим к соотношению применяемом правиле 3 ' ) строгих вложений вида Aj R B j. Таким образом, утверждение леммы доказано.

Лемма 1.4.3. Пусть R – бинарное отношение на решетке. Тогда при выводе любой логической связи A B все применения транзитивного правила 4) могут быть исключены либо перенесены в заключительную стадию данного процесса.

Доказательство. Докажем сформулированное утверждение с помощью индукции по m – оценке уровня рекурсии в соотношении A B. При m 0 для A, B имеет место одно из условий 1)–2) определения 1.3.1. В этом случае вывод A B не содержит транзитивных связей. Как следствие, утверждение леммы выполнено.

Предположим далее, что оно верно для некоторого m 0, и докажем это утверждение при уровне рекурсии m 1. По предположению индукции, первые m шагов вывода можно организовать так, что транзитивное правило 4) будет применяться лишь в конце процесса. В этом случае все зависит от того, какое правило вывода применено на последнем ( m 1)-м шаге – 3 ' ) или 4). Если последним применено правило 4), то утверждение леммы сразу оказывается выполненным, так как все транзитивные связи использованы в заключительной стадии вывода. Таким образом, остается исследовать случай, когда на ( m 1)-м шаге применено правило вывода 3 ' ).

Пусть связь A B в конечном счете получена из условия 3 ' ). Каждое базовое соотношение Ai Bi, i 1,..., n при этом имеет уровень рекурсии m и, по предположению индукции, все свои транзитивные связи использует лишь в конце вывода. Другими словами, при каждом i 1,..., n существует цепочка элементов Ai Ci0, Ci1,..., Cini Bi такая, что выполнены соотношения Cik 1 Cik, k 1,..., ni, при выводе которых не используется транзитивное правило 4). По причине конечности n величины ni ограничены в совокупности, что означает ni N, i 1,..., n. В связи с этим фактом будем считать все указанные выше цепочки элементов равными по длине N, дополнив каждую из них в случае необходимости справа повторяющимся элементом построим элементы Ck Кроме того, поскольку Cik 1 Cik, i 1,..., n, то к этим парам можно применить правило 3 ' ), то есть получаем Ck 1 Ck, k 1,..., N.

Таким образом, удалось показать, что в рассматриваемом случае все Ai Bi, i 1,..., n можно заменить его применением на заключительной стадии вывода к построенным элементам Ck, k 0,..., N.

1.5. Логическая редукция В любой парадигме программирования действует правило хорошего тона – избегать неоправданного дублирования кода или данных. В приложениях логических систем также естественным образом возникает вопрос об их эквивалентной минимизации. В общей математической логике минимальная система аксиом называется базисом. Проблемы существования базисов правил для различных логик рассматривались В.В. Рыбаковым [97–99].

Однако системы продукционного типа имеют особенности, дающие дополнительные возможности минимизации.

LP-структура представляет собой алгебраическую модель продукционной системы. Поэтому очевидное решение задачи минимизации дает такой способ представления бинарного отношения, когда в памяти компьютера хранится лишь уникальная часть информации о данном отношении, а остальная информация может быть получена из общих свойств логических отношений. Под уникальной частью подразумевается подобранное по определенным критериям отношение R0 R, из которого R получается построением логического замыкания.

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

В работе [80] при более сильном условии на LP-структуру показано, что замыканием некоторого другого отношения R R. Данный результат полезен для разработки эффективных алгоритмов построения логического замыкания и редукции. Он позволяет свести исследование вопросов о нахождении логического замыкания и редукции отношений к рассмотрению соответствующих свойств транзитивных отношений. Здесь аналогичный вопрос рассматривается и решается на основе определения 1.2.1, то есть для более общей LP-структуры.

следующих действий (шагов):

новое отношение R1 ;

объединить полученное отношение с отношением включения R.

Замечание 1.5.1. Из предыдущих теорем следует, что отношение R эквивалентно R.

Лемма 1.5.1. Пусть R – бинарное отношение на решетке. Тогда, если A B, и это соотношение может быть получено без использования транзитивного правила 4) определения 1.3.1, то ( A, B) R.

Доказательство. Пусть имеет место A B, полученное без правила 4). Если указанное соотношение произошло непосредственно из условия 1) или 2) определения 1.3.1, то сразу имеем ( A, B) R.

Остается рассмотреть случай применения правила 3 ' ). Все необходимые для этого рефлексивные пары могут быть подготовлены в самом начале процесса вывода. При этом в силу леммы 1.4.2 пары вида A R B не потребуются. Следовательно, правило 3 ' ) может лишь завершать этот процесс.

Если сопоставить указанные 2 этапа вывода с последовательностью построения отношения R, то выяснится, что вывод A B соответствует построению некоторого подмножества R, что и доказывает включение Теорема 1.5.1. Для произвольного отношения R на решетке логическое соответствующего отношения R.

Доказательство. Как было отмечено выше, отношение R эквивалентно R. Следовательно, по определению логического замыкания, имеем R. Отсюда, поскольку отношение транзитивно, получаем Докажем обратное включение. Предположим, что A B. По лемме 1.4.3, при получении этого вывода все применения транзитивного правила 4) определения 1.3.1 могут быть перенесены в заключительную стадию процесса. Данное утверждение означает, что существует цепочка элементов k 1,..., N, при выводе которых правило 4) не используется. Тогда по лемме 1.5.1 имеем Следствие 1.5.1. Если R1 R2, то Доказательство. Во-первых, из описания процесса построения R легко заметить, что если R1 R2, то R1 R2. Аналогичное вложение имеет место и для транзитивных замыканий этих отношений, что в силу теоремы 1.5. означает доказываемый факт.

Далее для произвольного отношения R рассмотрим отношение R, построенное по данному последовательным выполнением шагов, обратных построению R, а именно:

исключить из R содержащиеся в нем пары вида A R B и обозначить новое отношение R1 ;

исключить из R1 всевозможные пары ( A, B) с элементами вида исключить из полученного отношения все рефлексивные пары.

Замечание 1.5.2. Отношение R эквивалентно R.

Заметим, что подобный подход к построению транзитивной редукции («удалить все транзитивные пары») был бы ошибочным. Причина в том, что в некоторых ситуациях (наличие в отношении циклов) транзитивная редукция не единственна [2], и одновременное удаление всех имеющихся транзитивных пар может привести к потере связей. Однако, поскольку сама решетка ациклична, удаление всех указанных выше «объединенных» пар ( A, B) приводит к одному и тому же результату, независимо от порядка удаления. По этой причине можно говорить об одновременном удалении всех таких пар.

Лемма 1.5.2. Пусть R – бинарное отношение на решетке. Для того чтобы R являлось логической редукцией, необходимо и достаточно, чтобы R не содержало ни одной такой пары ( A, B), что выполнено соотношение Доказательство. Пусть отношение R представляет собой логическую редукцию, то есть является минимальным логически эквивалентным себе отношением. Если бы существовала пара ( A, B) R, логически связанная отношением R \ {( A, B)}, то в силу следствия 1.3.1 ее можно было бы исключить из R, получив при этом меньшее эквивалентное отношение.

Таким образом, при наличии указанной пары отношение R не может быть логической редукцией.

Для доказательства обратного утверждения предположим, что не A B. Необходимо доказать, что в этом случае R есть логическая редукция. Предположим противное – пусть существует отношение R0 R, эквивалентное R, причем ( A, B) R \ R0. Тогда, поскольку ( A, B) R, в силу эквивалентности рассматриваемых отношений справедливо A B. Так как отношение R0 не содержит пару ( A, B), то R0 R \ {( A, B)}, и логическая связь A B противоречит сделанному предположению – таких пар утверждение.

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

Теорема 1.5.2. Пусть для бинарного отношения R, заданного на решетке, построено соответствующее отношение R. Тогда, если для R существует представляет собой логическую редукцию исходного отношения R.

Доказательство. Из построения R и R (замечания 1.5.1–1.5.2) следует, что указанное в теореме отношение R 0 логически эквивалентно R. Осталось показать, что R 0 является логической редукцией. Для этого достаточно проверить выполнение для R 0 условия леммы 1.5.2.

Пусть ( A, B) – произвольная пара отношения R 0. Необходимо показать, что логическая связь A B невозможна. Предположим противное, а именно, что эта связь существует. Тогда в силу следствия 1.3.1 отношение R0 \ {( A, B)} эквивалентно R 0. Заметим, что применение правила 1) определения 1.3.1 для вывода A B невозможно, поскольку пара ( A, B) не содержится в множестве R0 \ {( A, B)}.

По лемме 1.4.3 любая логическая связь может быть построена таким образом, что все применения транзитивного правила будут осуществляться лишь в завершающей стадии ее вывода. Этот факт означает, что существует цепочка элементов A C0, C1,..., CN B такая, что выполнены соотношения Ck 1 Ck, k 1,..., N, при выводе каждого из которых правило 4) не применяется. Отсюда по лемме 1.5.1 имеем (Ck 1, Ck ) R. Таким образом, при N 1 пара ( A, B) оказывается транзитивной в R. Следовательно, она не может содержаться в R 0, являющемся подмножеством транзитивной редукции отношения R. В результате получено противоречие исходному предположению ( A, B) R0.

Остается исследовать случай N 1. В этой ситуации существует вывод логической связи A B, который может содержать применения правила 3 ' ) лишь в заключительной стадии. Полученная таким образом пара ( A, B) Соответственно при нахождении (обратный процесс) она будет исключена. Таким образом, снова приходим к противоречию исходному предположению ( A, B) R0.

Таким образом, исследованы потенциально возможные ситуации для установлено, что в каждом таком случае наличие связи A B противоречит факту ( A, B) R0. Следовательно, отношение R 0 представляет собой логическую редукцию.

Замечание 1.5.3. Полученные в настоящем разделе результаты содержат существенное усиление по сравнению с аналогичными теоремами работы [80], основанными на использовании в определении логических отношений операции. Дело в том, что требование существования транзитивной редукции отношения R при определенных условиях может оказаться избыточным для существования логической редукции исходного отношения R. Очевидно, что при конечном множестве R из него всегда можно последовательно удалить «лишние» пары, получив в результате логическую редукцию. Однако, если при этом сама решетка бесконечна и имеет соответствующую структуру, то, объединяя R с отношением, можно получить не имеющее транзитивной редукции отношение R. Таким образом, использование отношения R способно исправить ситуацию.

Что касается оценок сложности алгоритмов построения логической редукции, то здесь результаты не оптимистичны. Как показано в [21], задача минимизации функций Хорна является NP-полной. В настоящей работе используется процедура нахождения не наименьшего, а минимального множества правил. При этом применение быстрого алгоритма построения транзитивной редукции [2] дает сложность O( N 3 ), если удастся эффективно реализовать построение отношений R и R. Однако при этом само число N элементов решетки может оказаться сопоставимым с мощностью булеана 2n, где n – количество атомов решетки.

1.6. Продукционно-логические уравнения В данном разделе вводится связанный с LP-структурами класс логических уравнений. Приводятся результаты о разрешимости и количестве решений этих уравнений, а также излагаются методы их решения. Нахождение решения продукционно-логического уравнения соответствует обратному логическому выводу на решетке. Терминология, концепция уравнений и механизмы их решения лежат в основе методов полного релевантного LPвывода, составляющих основной предмет настоящего диссертационного исследования. Изложенные в данном разделе результаты были ранее получены в работе [81] для более частной LP-структуры. Их доказательства в нашем случае существенно не изменились, поэтому здесь не приводятся.

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

Ранее интересные классы логических уравнений рассматривались в работах [58-59, 66, 79, 101], однако исследуемые в них уравнения имеют отличную от систем продукций природу. На нечетких бинарных отношениях основаны реляционные уравнения, рассматривавшиеся в [10] и ряде других работ. Основные трудности исследования здесь порождаются нечеткостью отношений, и процесс решения соответствует всего лишь единственному шагу обратного вывода.

справедливо A B. Тогда, как известно [74], B называется образом A, а A – прообразом B при отношении. Каждый элемент из иметь много образов и прообразов. Более того, в рассматриваемой ситуации в силу определения логического отношения любой элемент B1 B будет образом A и каждый A1 A окажется прообразом B. По этой причине, для исключения неоднозначности, при изучении образов и прообразов логических отношений необходимо уточнение рассматриваемых понятий.

Для данного элемента B минимальным прообразом при отношении называется такой элемент A, что A B и A является минимальным, то есть не содержит никакого другого A1, для которого В оставшейся части этого раздела рассматриваются лишь атомнопорожденные решетки.

Определение 1.6.1. Атом x решетки называется начальным при отношении R, если в R нет ни одной такой пары ( A, B), что x содержится в B и не содержится в A. Элемент X решетки называется начальным, если все его атомы являются начальными при отношении R. Подмножество ( R) (будем обозначать, если это не вызовет неоднозначностей) решетки, состоящее из всех начальных элементов, называется начальным множеством решетки (при отношении R ).

Очевидно, начальное множество образует подрешетку в.

Обозначим R L – логическое замыкание отношения R и рассмотрим уравнение Определение 1.6.2. Частным решением X уравнения (1) называется Приближенным (частным) решением X уравнения (1) называется любой прообраз элемента B, содержащийся в. Общим решением уравнения (1) называется совокупность всех его частных решений { X s }, s S.

По определению точное решение будет и приближенным. Приближенное решение всегда содержит хотя бы одно точное решение [81].

Уравнения вида (1) будем называть продукционно-логическими (или просто логическими) уравнениями на решетках.

В рамках настоящей диссертационной работы рассматриваются в основном практические аспекты решения логических уравнений, влияющие на эффективность обратного логического вывода в реальных компьютерных системах. Поэтому далее в этом разделе предполагается, что R – конечное каноническое отношение на атомно-порожденной решетке, не содержащее пар отношения R, а правая часть B уравнения (1) представляет собой конечное объединение атомов.

Введем понятие структурного расслоения исходного отношения R на виртуальные слои (частичные отношения) {Rt | t T }. Оно упрощает изучение свойств отношения, а также облегчает построение и исследование ряда алгоритмов, связанных с решением соответствующих логических уравнений. Кроме того, концепция слоев лежит в основе распараллеливания процесса нахождения решений.

подмножества, каждое из которых образовано парами вида ( A, x p ) с одним и тем же атомом x p в качестве правой части. Такое разбиение имеет смысл благодаря тому, что R является каноническим. Обозначим эти подмножества R p соответственно их элементу x p, p P.

Определение 1.6.3. Слоем Rt в отношении R называется подмножество R, образованное упорядоченными парами, взятыми по одной из каждого непустого R p, p P. Два слоя, отличающиеся хотя бы одной парой, считаются различными.

Замечание 1.6.1. Каждый слой содержит максимально возможное подмножество пар из R с уникальными правыми частями. Добавление к слою еще одной пары нарушило бы это условие.

Замечание 1.6.2. Любое подмножество пар в R с уникальными правыми частями принадлежит некоторому слою.

Замечание 1.6.3. В общем случае слои имеют непустые пересечения.

Объединение всех слоев равно R.

Замечание 1.6.4. Нетрудно заметить, что общее количество слоев N определяется равенством N N p, где N p – мощность подмножества пар отношения R с правой частью x p.

приближенное) порождается в R некоторым слоем Rt, если X B.

Замечание 1.6.5. Аналогично [81] можно показать, что любое частное решение уравнения (1) порождается в R некоторым слоем Rt.

Замечание 1.6.6. Для нахождения решения уравнения (1) в некотором слое Rt достаточно вместо (1) решить аналогичное уравнение с отношением Последние замечания не гарантируют, что два различных слоя не могут порождать одного и того же решения. Кроме того, могут существовать слои, дающие частное решение для Rt, но приближенное для R. Некоторые слои могут вообще не давать решений. Однако, справедливо утверждение о том, что один слой не может порождать более одного точного решения (см. [81]).

Лемма 1.6.1. Ни один слой Rt не может содержать двух различных частных решений уравнения (1).

Объединяя перечисленные выше результаты, можно сформулировать следующее утверждение.

Теорема 1.6.1. Для нахождения общего решения уравнения (1) достаточно найти частное решение X t в каждом слое Rt, если оно существует. Далее из содержащие другие элементы этого же множества.

Следствие 1.6.1. Количество частных решений уравнения (1) оценивается отношения R с правой частью x p, а P определяет все такие подмножества (см. замечание 1.6.4).

Теорема 1.6.1 и замечание 1.6.6 позволяют свести вопрос о решении уравнения (1) к задаче нахождения частного решения уравнения D( ft ). Для него выполнены некоторые важные свойства.

ft ( B Следствие 1.6.2. Отображение f t является изотонным [55]. Это означает, Таким образом, основываясь на лемме 1.6.2, для решения уравнения (2) достаточно решить уравнение с каждым атомом элемента B в качестве правой части. Принимая во внимание это обстоятельство, рассмотрим задачу нахождения частного решения следующего уравнения:

Рассмотрим методы решения этой задачи. В [81] для соответствующей LPструктуры показано, что она эквивалентна задаче на ориентированном графе перечисления всех входных вершин, из которых достижима данная вершина.

отношении R, сопоставим вершину графа. Далее для каждой пары ( A, a) рассматриваемого слоя Rt построим дуги, ведущие из всех вершин, соответствующих атомам A, в вершину, соответствующую данной a. Для вершины в графе.

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

Следующий факт завершает описание пошагового процесса решения исходного логического уравнения (1).

Теорема 1.6.2. Уравнение (3) имеет не более одного решения. Если граф GRt,b не содержит циклов, то единственное решение уравнения состоит из всех точек, соответствующих входным вершинам графа. Если GRt,b содержит хотя бы один цикл, то уравнение решений не имеет.

Итак, в настоящей главе были изложены основные элементы общей теории LP-структур. Эта теория создает эффективную алгебраическую модель для продукционно-логических систем. Последующие главы работы основываются на ее положениях, применяя их к задачам, связанным с разработкой, исследованием и компьютерной реализацией нового метода релевантного LP-вывода.

Следующая глава посвящена методологии LP-вывода. Обоснованы и апробированы различные способы выбора параметров релевантности. Дано описание алгоритмов решения логических уравнений в слоях, а также алгоритмов исследования начальных прообразов на предмет истинности.

Описаны алгоритмы параллельного решения указанных задач.

Глава 2. Релевантный обратный вывод Настоящая глава посвящена моделированию и исследованию процессов обратного вывода в продукционно-логических системах на основе специального класса алгебраических систем – LP-структур. Как уже отмечалось, понятие LP-структуры представляет абстрактное описание теоретико-множественной модели различных классов продукционных систем. В качестве конкретной предметной области здесь рассматривается известный тип продукционных экспертных систем [44]. Он выбран в силу своей простоты и широкой известности, что позволяет непосредственно сосредоточиться на изложении основных идей и методов релевантного вывода. Однако рассматриваемые подходы могут быть применены к системам с более сложной логикой, в том числе неклассическим [82].

2.1. Продукционная система и ее представление LP-структурой Последующие разделы главы посвящены возможным применениям LPструктур к моделированию логического вывода в системах продукционного типа. С этой целью введем терминологию, связанную с экспертными продукционными системами. Рассматриваемая ниже модель и ее практическая реализация описаны в [44]. Данная книга носит в большей мере учебный характер, однако ее идеи оказались удачными и в дальнейшем использовались и развивались в ряде работ по экспертным системам, в первую очередь – обучающим (например, [15, 48]).

Продукционные экспертные системы манипулируют множествами фактов и правил (продукций). Факт представляет собой единицу декларативной информации – некоторое суждение о внешнем мире или состоянии системы.

Стандартным представлением факта является триплет вида «объект.атрибут = значение» [11] (например, «термометр.температура = высокая»). В книге [44] триплет редуцируется к паре «параметр = значение». Это означает, что объект и атрибут интегрируются в единый параметр. В этой связи «термометр.температура» и «термометр.изготовитель» считаются разными параметрами.

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

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

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

Правило (продукция) состоит из предпосылки и заключения. Предпосылка обычно представляет собой выражение над фактами (например, их конъюнкцию или дизъюнкцию). Предпосылка может быть выполненной (истинной) или невыполненной (ложной) при текущем состоянии рабочей памяти. Если предпосылка верна, то правило может быть применено.

Заключение – это действие, которое можно осуществить, если верна предпосылка (например, добавить к рабочей памяти некоторый новый факт).

Применение правила состоит в выполнении действия заключения. В контексте настоящей работы рассматриваются приложения, в которых заключение, как и предпосылка, является выражением над фактами, и соответствующее заключению действие интерпретируется как «считать истинным». Таким образом, в данном случае применение правила означает некоторую модификацию рабочей памяти, обычно – запись в нее тех фактов, справедливость которых вытекает из истинности выражения в заключении правила. Совокупность правил называется базой знаний.

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

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

Алгебраический метод исследования продукционной системы сводится к изучению бинарного отношения R на множестве фактов F. В силу особенностей продукционной системы, является рефлексивным и транзитивным. Действительно, для любого a F можно констатировать, что «если верно a, то верно a ». Также при наличии в R двух правил a b и b c при выводе фактически действует и правило a c. Например, по правилам «если температура высокая, то заболел» и «если заболел, то на работу не ходить» можно сформировать правило «если температура высокая, то на работу не ходить». Соответствующую данной модели алгебраическую систему можно считать вырожденным случаем LPструктуры с пустым базовым отношением частичного порядка.

Однако нельзя назвать исчерпывающим знанием правило «если заболел, то на работу не ходить». Ближе к истине были бы следующие высказывания:

«если заболел, сегодня рабочий день, время утреннее, то на работу не ходить, лечиться», «если заболел, сегодня рабочий день, время вечернее, то лечиться», «если заболел, сегодня выходной день, то лечиться».

Поэтому возникает более сложная, называемая стандартной, модель базы знаний [80], правила которой в качестве предпосылки и заключения могут содержать наборы элементарных фактов ({a}, {a, b}, {a, b, c}, …). Общий вид продукции в данном случае таков: {a1,..., an } {b1,..., bm }, где ai и b j – атомарные факты. Смысл такого правила состоит в следующем: если верны все ai, i 1,..., n, то верны и все b j, j 1,..., m.

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

Состоящая из таких объектов математическая структура представляет собой частный случай решетки В данной главе с учетом происхождения рассматриваемой модели используются обозначения, принятые в теории множеств, а не в теории решеток. Чтобы не путать с объектами простейшей логики – элементарными фактами, элементы будем, как правило, обозначать большими латинскими буквами. Для любых A, B в определены (теоретико-множественные) операции пересечения ( A B ) и объединения ( A B ). Кроме того, в задан частичный порядок – отношение включения.

Таким образом, на множестве структуру решетки, и дополнительное отношение отражающее логические связи знаний конкретной предметной области.

Ввиду усложнения модели, логические отношения в данной LP-структуре, кроме упомянутых выше свойств рефлексивности и транзитивности, должны также обладать дополнительными свойствами. Свойство рефлексивности является теперь частным случаем свойства тавтологии включения: при A B имеет место A B. Действительно, если справедливо некоторое множество фактов A, то верно и любое его подмножество B. Кроме того, любую совокупность фактов можно выводить по частям: если A B и A C, то дистрибутивностью. Из него формально следует монотонность такой логики:

поскольку A A, то из A B по свойству дистрибутивности получаем A A B. Это свойство означает монотонное накопление знаний при применении правил.

2.2. Обратный вывод на основе решения уравнений Рассмотрим возможности, которые предоставляет аппарат логических уравнений (п. 1.4) для организации обратного вывода в продукционной системе.

Как известно [77], при исследовании алгоритмов принято анализировать их вычислительную сложность путем получения оценок относительно мощности множества исходных данных. Однако в случае продукционных систем (и логического вывода вообще) процесс нахождения подобных оценок обычно приводит к неудовлетворительным результатам.

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

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

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

Предлагаемый метод вывода на основе решения уравнений начинается с построения всех минимальных начальных прообразов в LP-структуре для атомов, соответствующих значениям объекта экспертизы. Далее в построенном множестве достаточно найти тот прообраз, который содержит лишь истинные факты, после чего сразу можно сделать заключение о соответствующем значении объекта экспертизы. Наиболее простой путь в этом плане – просматривать прообразы последовательно, задавая пользователю вопросы о соответствующих начальных фактах (или обращаясь к базе данных за этими фактами). Такой способ уже дает определенные преимущества – исследуются лишь минимальные прообразы.

Также предварительно можно исключить из процесса «противоречивые»

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

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

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

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

1) если тучи и идти_пешком и выходишь_надолго то взять_зонтик;

2) если прогноз_плохой и идти_пешком и выходишь_надолго то взять_зонтик;

3) если идет_дождик и идти_пешком то взять_зонтик.

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

В рассматриваемом примере это элементарно, поскольку они совпадают с предпосылками правил. Итак, гипотеза взять_зонтик имеет три начальных прообраза:

1) {тучи, идти_пешком, выходишь_надолго};

2) {прогноз_плохой, идти_пешком, выходишь_надолго};

3) {идет_дождик, идти_пешком}.

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

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

Присвоив всем фактам нулевой приоритет, будем затем повышать его на 1, если факт содержится в максимальном (по сравнению с другими фактами) количестве прообразов. Поскольку факт идти_пешком встречается везде, его приоритет станет равным 1. Далее учитываем присутствие фактов в прообразах минимальной мощности (в данном случае – в прообразе №3). В идти_пешком (до 2). Таким образом, релевантным признается факт идти_пешком. Именно его истинность целесообразно проверить в первую очередь, обращаясь к внешнему источнику.

При отрицательном ответе на запрос о факте необходимо исключить из рассмотрения все содержащие его прообразы. В нашем случае это сразу решает «проблему зонтика» – все имеющиеся прообразы окажутся ложными («зонтик не брать!»). Если же ответ положителен, вычисляем следующий релевантный факт из еще непроверенных. Им окажется идет_дождик.

Положительный ответ на запрос о данном факте также решает поставленную задачу – истинным будет прообраз №3 («зонтик брать!»), в противном случае процесс продолжается.

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

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

Во-первых, с помощью теоремы о логической редукции продукционная база знаний может быть минимизирована. Таким образом, в ней могут быть выявлены все избыточные правила. Во-вторых, множество правил можно исследовать на противоречивость. Сформулируем семантически противоречивую гипотезу, например, составленную из пары альтернативных значений объекта экспертизы. Решим далее продукционно-логическое уравнение с данной гипотезой в качестве правой части. Если в результате будет найдено решение, состоящее из непротиворечивых (совместимых) фактов, можно сделать вывод о некорректности рассматриваемой базы знаний. Данный процесс можно автоматизировать, запрограммировав процесс перебора пар противоречивых значений.

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

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

Не ограничивая общности, можно считать (см. главу 1), что R является каноническим отношением на атомно-порожденной решетке, а правая часть уравнения (1) представляет собой конечное объединение атомов. Тогда, в силу теорем п.1.4, вместо (1) достаточно рассмотреть уравнения с атомами в правой части:

Пусть выбран атом b, которому соответствует общее решение уравнения (4) – множество { X } всех его минимальных начальных прообразов. На множестве атомов решетки введем частично определенную доопределять путем обращения к внешнему источнику информации. В моделируемой продукционной системе интерпретация данной функции такова:

True( x) 1, если соответствующий факт x содержится в рабочей памяти;

True( x) 0, если достоверно известно, что x не может содержаться в рабочей памяти;

True( x) null, если проверка x еще не производилась.

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

Последнее требование лежит в основе метода релевантного вывода. Метод состоит из двух стадий: 1) решение уравнения – вычисление множества начальных прообразов и 2) нахождение среди них истинного прообраза.

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

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

// Обычный обратный вывод X 0 = null X getCurrPreImage (b) while X 0 = null and X != null do is_True = true foreach x X do else is_True = x T if not is_True then break if is_True then X 0 X else X getCurrPreImage (b) end Используемая здесь функция Ask ( x) запрашивает внешний источник об истинности атома x и в соответствии с ответом модифицирует множества T и F (то есть доопределяет функцию True). Функция getCurrPreImage (b) находит очередной начальный прообраз для гипотезы b. Этот прообраз не обязательно минимален, поскольку не сравнивается с другими существующими начальными прообразами. Заметим также, что при обычном обратном выводе проверка истинности каждого факта может производиться непосредственно перед его добавлением к формируемому прообразу, поэтому в представленном выше алгоритме не предусмотрены тесты вида В следующем алгоритме, напротив, проверке на истинность подвергаются сразу целые прообразы.

// Релевантный LP-вывод X 0 = null { X } getPreImages (b) while X 0 = null and { X } do k getRelevantIndex ({X }, T ) foreach X j { X } do end В последнем алгоритме функция getPreImages (b) решает уравнение (4) с правой частью b, то есть строит множество { X } всех минимальных начальных прообразов для атома b.

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

Разобьем R на непересекающиеся подмножества, каждое из которых образовано парами вида ( A, x p ) с одним и тем же атомарным элементом ( x p ) в качестве правой части. Обозначим эти подмножества R p соответственно их элементу x p, p P. При реализации канонического отношения для каждого x p достаточно хранить лишь совокупность левых частей пар с правой частью x p. Каждому из подмножеств R p сопоставим итератор – индексную переменную jp, способную перебирать собственное подмножество, останавливаясь на каждой паре ровно один раз. Таким образом, любой слой в отношении R получается соответствующим набором значений итераторов. Нахождение решения в отдельном слое сводится к получению списка начальных вершин графа, из которых достижима данная вершина (она соответствует атому правой части уравнения).

Эксперименты показали, что при больших объемах БЗ процесс построения всех минимальных прообразов может потребовать чрезмерного объема ресурсов компьютера. В связи с данным обстоятельством метод был последовательное построение кластеров начальных прообразов (подмножеств ограниченной мощности) с их динамическим релевантным исследованием. Модифицированный LP-вывод дает достаточно эффективные (сопоставимые с LP-выводом) результаты для промышленных БЗ больших размеров. Приведем его обобщенный алгоритм.

// Кластерно-релевантный LP-вывод X 0 = null while X 0 = null do { X } getPreImagesCluster (b ) k getRelevantIndex ({X }, T ) end Функция getPreImagesCluster (b) выдает фиксированный (ограниченный по количеству элементов или времени вычислений) набор минимальных начальных прообразов атома b, которые на момент вызова функции не пересекаются с множеством F.

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

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

2.4. Стратегии подсчета релевантности getRelevantIndex ({ X }, T ) должна находить индекс k любого из наиболее релевантных и ранее не проверенных на истинность атомов, содержащихся в элементах заданного множества начальных прообразов { X }. Стратегия релевантности – общее снижение количества вызовов функции Ask ( xk ). С упомянутыми в п.2.2 показателями релевантности начальных атомов. К этим показателям относятся следующие параметры:

присутствие в максимальном количестве построенных прообразов;

присутствие в прообразах минимальной мощности.

Один из возможных вариантов функции getRelevantIndex представлен ниже. Она реализует подсчет суммарной релевантности, который может быть назван линейным.

int getRelevantIndex ({ X }, T ) // Инициализация приоритетов начальных атомов решетки // Нахождение минимальной мощности прообразов int nMin = null foreach X j { X } do if nMin = null or Length ( X j ) < nMin then nMin = Length ( X j ) // Вычисление приоритетов начальных атомов if not xk T F then // Рассматриваем лишь непроверенные атомы if Length ( X j ) = nMin then Priority[k]++ // Нахождение индекса наиболее релевантного атома int nRel = null if nRel = null or Priority[k] > Priority[nRel] then nRel = k return nRel end Рассмотрим альтернативные способы вычисления релевантности объектов. В частности, возьмем за основу пропорциональный подсчет.

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

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

Рассмотрим пример четырех прообразов для гипотезы «взять зонтик».

{тучи, идти_пешком, птицы_летают_низко, давление_падает};

{влажность_повышенная, душно};

{прогноз_плохой, идти_пешком, выходишь_надолго};

{идет_дождик}.

релевантности объектов «идет_дождик» и «идти пешком» результаты совпадают и равны 1. В этом случае порядок определения значений указанных объектов однозначно не определен и может быть произвольным.

Однако видно, что в случае положительного ответа на вопрос о том, идет ли дождик, можно найти решение за 1 шаг. Пропорциональный подсчет релевантности позволяет повысить рейтинг объекта «идет_дождик» сразу на 4, в то время как рейтинг объекта «идти_пешком» будет равен 3 (+1, так как объект присутствует в максимальном числе прообразов и +2 за мощность прообраза).

Соответствующая пропорциональному подсчету модифицированная функция getRelevantIndex представлена ниже.

int getRelevantIndex ({X }, T ) // Инициализация приоритетов начальных атомов решетки int Rating = 1 // Стартовое значение рейтинга // Нахождение максимальной мощности прообразов int nMax = null if nMax = null or Length ( X j ) > nMax then // Вычисление приоритетов начальных атомов if not xk T F then // Рассматриваем непроверенные факты if Length ( X j ) = nMax then Priority[k] += Rating foreach Rating++ // При уменьшении мощности прообразов увеличиваем рейтинг // Нахождение индекса наиболее релевантного факта int nRel = null if nRel = null or Priority[k] > Priority[nRel] then nRel = k return nRel end Для некоторых баз знаний специальной структуры, как было подчеркнуто показывают, что число внешних запросов снижается в среднем на 25%.

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

Рассмотрим еще один способ вычисления релевантности объектов – «бимаксимальный». В его основе лежит тот очевидный факт, что рассмотрение прообраза мощностью на единицу большей, чем минимальная, может тоже дать положительный результат. Другой фактор релевантности («значения объекта присутствуют в максимальном количестве прообразов») также следует учитывать.

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

Следуя указанному принципу, можно модифицировать функцию нахождения индекса наиболее релевантного объекта следующим образом.

int getRelevantIndex ({ X }, T ) // Инициализация приоритетов начальных атомов решетки // Нахождение минимальной мощности прообразов int nMin = null foreach X j { X } do if nMin = null or Length ( X j ) < nMin then nMin = Length ( X j ) // Нахождение второй по минимальности мощности прообразов int nMin2 = null foreach X j { X } do if nMin2 = null or Length ( X j ) < nMin2 and nMin2 nMin then // Вычисление приоритетов начальных атомов if not xk T F then // Рассматриваем лишь непроверенные атомы if Length ( X j ) = nMin then Priority[k]++ if Length ( X j ) = nMin2 then Priority[k]++ // Нахождение индекса наиболее релевантного атома int nRel = null if nRel = null or Priority[k] > Priority[nRel] then nRel = k return nRel end Согласно экспериментам, этот способ, как и предыдущий, позволяет уменьшить количество внешних запросов в среднем на 25%.

Кроме представленных выше модифицированных алгоритмов подсчета релевантности, рассмотрим варианты, учитывающие только один из двух факторов релевантности.

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

Примером таких прообразов могут случить следующие множества фактов:

{тучи, идти_пешком, птицы_летают_низко};

{влажность_повышенная, душно, тучи};

{прогноз_плохой, идти_пешком, выходишь_надолго};

{идет_дождик, давление_падает, тучи}.

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

Аналогично при небольших базах знаний с небольшой степенью вложенности правил исключение из рассмотрения показателя релевантности, связанного с наличием объекта в максимальном числе прообразов, не снижает эффективности алгоритма. Этот результат связан с большим разнообразием объектов в прообразах и невозможностью выделить объект, существенно чаще встречающийся в максимальном числе прообразов.

Примером могут служить следующие прообразы:

{тучи, прогноз_неблагоприятный};

{влажность_повышенная, душно};

{выходишь_надолго};

{идет_дождик}.

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

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

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

2.5. Использование параллельных вычислений При больших объемах баз знаний и их достаточно «глубокой» структуре необходимо использовать все имеющиеся в наличии возможности повышения эффективности логического вывода. Одна из подобных возможностей – применение параллельных вычислений. Подобным методам для продукционных систем было посвящено немало работ. К наиболее известным из них относится фундаментальный труд [16]. Параллельным методам в продукционных системах посвящены также работы [35, 41, 53, 57].

Эти методы могут быть использованы на более абстрактном уровне при компьютерной реализации LP-структур.

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

Метод релевантного LP-вывода был модифицирован с использованием параллельных вычислений. Параллельный релевантный LP-вывод предполагает одновременное построение набора начальных прообразов с их дальнейшим исследованием в разных потоках. Здесь и далее под «потоками»

подразумеваются threads – потоки выполнения [96].

Как уже было отмечено в п.2.3, для решения уравнения исходное каноническое отношение R представляется в виде слоев. Работа с различными слоями может быть организована независимо и параллельно.

Ниже приводятся основные положения такой организации.

Первичный поток приложения создает новые потоки (они ограничены параметром MaxThreads – максимальное количество потоков), передавая им пакет данных. Созданный поток находит решение продукционно-логического уравнения в отдельном слое. Как только вычисляется достаточное число прообразов, которое ограничено соответствующим параметром (или все прообразы) модуль LP-вывода начинает (релевантно) их исследовать на предмет истинности, обращаясь при необходимости за фактами к внешнему источнику. Если при обработке очередного кластера прообразов истинный прообраз выявить не удается, то процесс вычисления прообразов продолжается. При этом запоминается информация об установленных на предыдущем шаге ложных фактах. На ее основе перед очередным процессом вычисления прообразов сужается множество актуальных правил. Это обстоятельство также существенно ускоряет работу. По окончании работы потоки завершаются.

В случае, когда рабочих потоков бывает слишком много, в соответствии с законом Амдала, эффективность параллельных вычислений начинает снижаться [51]. Частое создание и завершение потоков с малым временем работы, а также большое количество переключений их контекстов, увеличивают объем ресурсов. Поэтому при реализации параллельного LPвывода используется заранее создаваемый пул потоков [96]. Максимальный размер пула ограничивается параметром. Его значение должно быть большим, чем число процессоров, чтобы добиться максимальной степени одновременности.

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

С целью повышения производительности процессы вычисления прообразов и их дальнейшего исследования выполняются асинхронно. Пока решение не найдено, полученный на очередном шаге кластер прообразов помещается в динамическую структуру данных Q, организованную в виде очереди.

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