Содержание к диссертации
Введение
Глава 1. Постановка задачи и обзор литературы 13
1.1. Знания в искусственном интеллекте 13
1.1.1. Что понимается под знаниями в искусственном интеллекте 13
1.1.2. Сетевые модели представления знаний 15
1.1.3. Фреймовые модели представления знаний 16
1.1.4. Логические модели представления знаний 17
1.1.5. Анализ классификации систем представления знаний в свете создания общей теории 20
1.2. Понимание продукции в настоящей работе 21
1.2.1. Продукция как основной элемент базы знаний 21
1.2.2. Продукция в искусственном интеллекте 23
1.2.3. Понятие обобщенной продукции 24
1.3. Об использовании теории категорий в информатике 29
1.3.1. Исследования, в которых привлекается теория категорий
1.3.2. Унификация и близкие проблемы 33
Глава 2. Основные элементы алгебраической теории продукций 38
2.1. Основные понятия алгебраической теории 38
2.1.1. Строение обобщенной продукции 38
2.1.2. Образец, сопоставление и конкретизация 42
2.1.3. Продукция на языке множеств и отображений 45
2.1.4. Теоретико-категорный язык для описания продукций 47
2.2. Примеры теоретико-категорного описания продукций 51
2.2.1. Пример L 51
2.2.2. Пример E 55
2.2.3. Пример S 57
2.2.4. Системы добавлений и изъятий 58
2.2.5. Продукционная система ЗНАТОК 62
2.3. –категории 72
2.3.1. Рекурсивно организованные системы образцов 72
2.3.2. –категория 73
2.3.3. Язык универсальных алгебр 79
2.4. Примеры -категорий 84
2.4.1. ПримерЬ 84
2.4.2. Пример Е 87
2.4.3. Пример S 87
2.4.4. Задача «крепкий орешек» и семиотическая интроспекция 89
2.5. Экстенсиональное vs интенсиональное 97
2.5.1. Два взгляда на образцы и продукции 98
2.5.2. Сопоставимость образцов 100
2.5.3. Экстенсиональные и интенсиональные свойства
продукций 103
2.6. Порядок на множестве образцов 108
2.6.1. Определение предпорядка на множестве образцов 109
2.6.2. Наименьшее обобщение и наибольший частный случай 110
2.6.3. Упорядоченность образцов в -категории 124
Глава 3. Теоретико-категорные алгоритмы работы со знаниями 142
3.1. Продукционные сети 143
3.1.1. Строение продукционной сети 145
3.1.2. Прямые произведения и продукционные деревья 147
3.1.3. Продукционные сети на П-категориях 150
3.1.4 Случай Q-категорий, порожденных универсальными
алгебрами 153 3.2. Алгоритмы автоматического формирования образцов и
продукций 155
3.2.1. Метод сходства и метод различия ДСМ-метода на языке
ТК-продукций 155
3.2.2. Об автоматическом формировании продукционных баз
знаний 165
3.2.3. Пример автоматического формирования дерева образцов –
система поддержки ввода информации 169
3.2.4. Пример автоматического формирования продукционной
сети – машинный перевод 179
3.3. Изменение характера знаний в продукционной системе 186
3.3.1. Динамические продукционные системы 187
3.3.2. P-кратная категория 188
3.3.3. Порядок на множестве образцов в P-кратной категории 192
3.3.4. Варианты контекстных решеток 202
3.3.5. Другие варианты использования кратной категории 204
3.3.6. Теоретико-категорное описание нечетких данных 207
Глава 4. Технология разработки и развития продукционных систем 220
4.1. Принципы построения категорной технологии. 220
4.1.1. Верхний уровень - уровень продукций 220
4.1.2. Нижний уровень - уровень данных 225
4.1.3. Некоторые примеры применения категорной технологии 226
4.2. Программируемая оболочка экспертной системы 228
4.2.1. Что такое программируемая оболочка? 229
4.2.2. База данных системы ЗНАТОК 233
4.2.3. База знаний системы ЗНАТОК 235
4.2.4. Описание атрибутов базы знаний системы ЗНАТОК 238
4.2.5. Машина вывода системы ЗНАТОК 241 4.2.6. Использование присоединенных процедур 244
4.2.7. Некоторые замечания о реализации системы 248
4.2.8. Подсистема объяснения 251
4.2.9. Применение категорной технологии построения
продукционных систем 258
4.2.10. Работа с нечеткими данными 261
4.2.11. Работа с динамическими данными 265
4.2.12. Совместная работа нескольких экспертных систем 268
4.3. Выявление конструкций со значением обусловленности в
текстах 271
4.3.1. Конструкции со значением обусловленности 272
4.3.2. Программная реализация продукционной сети 2 4.3.3 Использование прямых произведений 279
4.3.4 Реализация продукционной системы 280
Заключение 286
Основные научные и практические результаты диссертации 286
Литература 288
- Анализ классификации систем представления знаний в свете создания общей теории
- Примеры теоретико-категорного описания продукций
- Задача «крепкий орешек» и семиотическая интроспекция
- Программируемая оболочка экспертной системы
Введение к работе
Актуальность темы исследования и степень ее разработанности
Трудности, возникающие при анализе сложных систем и управлении такими системами, связаны, в частности, с тем, что такие системы не всегда могут быть описаны математическими формулами или уравнениями. Не всегда возможно и описать алгоритм функционирования таких систем. Человек-эксперт управляет такими системами, используя большие объемы знаний. Он может делать это даже в том случае, когда эти знания не поддаются полной формализации. Одним из направлений исследований, имеющих целью описание функционирования сложных систем, способов принятия решений и управлений такими системами является создание интеллектуальных систем, основанных на знаниях, в частности – экспертных систем, подменяющих человека-эксперта.
Предлагаемая работа содержит исследование интеллектуальных систем, основанных на знаниях. В ней дается в общем виде определение продукции как основного элемента таких систем. Далее строится математическая теория для исследования таких продукций и язык для их формализации, основанный на аппарате теории категорий. Разработка такого формального математического языка является весьма актуальной проблемой, так как классические математические языки, такие, например, как язык дифференциальных уравнений или теории оптимального управления, не всегда могут быть использованы для управления сложными системами, ибо такие системы могут не описываться набором числовых параметров, удовлетворяющих некоторым уравнениям и неравенствам. Затем в работе излагается технология разработки интеллектуальных компьютерных систем, основанной на построенной теории. Это – также весьма актуальная задача, ибо разработка таких систем является в высшей степени трудоемким делом, и технология, облегчающая их разработку, может оказаться весьма востребованной.
С 70-х годов 20 века в искусственном интеллекте утвердилось понимание того, что успешное решение интеллектуальных задач требует использования больших объемов знаний. Учеными были предложены различные схемы представления знаний, разработаны различные алгоритмы работы со знаниями. Были созданы интеллектуальные системы, основанные на знаниях. К этому классу относятся наиболее известные прикладные системы искусственного интеллекта – экспертные системы. Работы во всех этих направлениях активно ведутся и в настоящее время, однако они больше связаны с решением прикладных задач, чем с развитием общей теории использования знаний в интеллектуальных системах. Между тем опыт исследования систем, основанных на знаниях, в том числе и опыт автора настоящей работы, показывает, что методы, применяемые в таких системах, идейно являются близкими, хотя могут значительно различаться в формальном отношении. Это позволяет надеяться, что общая теория таких систем может быть построена.
Работы, относящиеся к знаниям в искусственном интеллекте, можно разделить на две группы. К первой относятся работы, посвященные знаниям вообще. Эти работы написаны на языке довольно общем, неформальном, близком к философскому. Не преуменьшая значения таких работ, отметим их недостаток: они не позволяют построить формальную, в достаточной степени математизированную теорию. С другой стороны, есть математические исследования, посвященные какому-либо хорошо формализованному способу представления знаний. Достоинством таких исследований является большая глубина и строгость, недостатком – то, что они применимы лишь к конкретным структурам знаний.
Настоящая работа направлена на решение задачи создания общей теории интеллектуальных компьютерных систем, основанных на знаниях. Внимание автора было сосредоточено на исследовании основной операции в работе таких систем: узнать ситуацию, с которой столкнулась система, и найти в памяти рекомендации о том, что в этой ситуации следует предпринять. По мнению
автора, именно использование такой операции является отличительной особенностью систем, основанных на знаниях. В работе обосновывается тезис о том, что инструментом для выполнения такой операции является продукция, понимаемая в достаточно широком смысле, поэтому внимание автора сосредоточено на продукционных системах. Исследование этой основной операции является достаточно полным и завершенным: в работе введено понятие обобщенной продукции, реализующей такую операцию, предложен математический язык, формализующий такие продукции, разобраны многочисленные примеры, показаны способы использования построенной теории при решении прикладных задач.
Цели и задачи исследования
Целью работы является создание общей теории, описывающей основные операции, используемые при работе продукционных систем представления знаний, создание математического аппарата для формализации этой теории, разработка на их основе технологии создания продукционных систем.
В соответствии с поставленной целью в диссертации решены следующие задачи.
-
Введены и изучены базовые понятия создаваемой теории – образцы, сопоставление, конкретизация, и дано определение продукции как пары образцов и действия продукции как последовательное осуществление двух операций - сопоставления и конкретизации.
-
Дано понятие системы образцов. Описан формальный язык, базирующийся на аппарате теории категорий, который может быть использован для математической формализации системы образцов.
-
Разобран ряд примеров, показывающих, что предложенный язык может быть использован для формализации весьма широкого класса продукций, используемых в системах представления знаний.
-
Рассмотрен класс рекурсивно организованных систем образцов, к которому относятся многие важные для задачи представления знаний систем образцов. Определена и исследована -категория, формализующая рекурсивно-организованные системы. В частности, показана, что -категория изоморфна некоторой подкатегории категории Клейсли.
-
Изучен порядок на множестве образцов, основанный на их большей или меньшей общности. Введено понятие наименьшего обобщения пары образцов и проведено его математическое исследование. Показано, что это понятие может быть использовано для формирования базы знаний с помощью обобщения.
-
Описана так называемая продукционная сеть, реализующая более сложные алгоритмы применения продукций, чем в традиционных продукционных системах.
-
Предложена технология разработки продукционных систем, названная в работе категорной, основанная на построенной математической теории. Эта технология позволяет программировать алгоритмы работы с продукциями в общем виде. Привязка такого алгоритма к решению конкретной задачи сводится к программной реализации операций соответствующей категории. Это требует значительно меньшего объема программирования, чем создание с нуля продукционной системы, решающей эту задачу.
-
Рассмотрены примеры реальных систем, в создании которых принимал участие автор, демонстрирующие использование этой технологии.
Научная новизна исследования
Продукционные системы – одна из самых исследованных областей в искусственном интеллекте. Тем не менее, подход, использованный в настоящей работе, базирующийся на определении продукции как пары образцов и действия
продукции как последовательного осуществления двух операций – сопоставления и конкретизации - отличается от общепринятого, и целиком принадлежит автору.
Аппарат теории категорий давно и плодотворно используется в информатике, но его использование в искусственном интеллекте является довольно редким, а данное в работе теоретико-категорное определение продукции и вся вытекающая из этого определения теория являются совершенно оригинальными и также принадлежат автору. Монады и категория Клейсли использовались другими авторами для формализации конструкций, близких к встречающимся в настоящей работе, однако использование их для описания операции сопоставления также является новым.
Автору принадлежит понятие -категории, как категории, описывающей важные для практики варианты систем образцов. Автору также принадлежит определение кратной категории и идея использования этой категории для описания динамических продукционных систем.
Новым является понятие продукционной сети, реализующей более сложные алгоритмы использования продукций, чем в классических продукционных системах.
Описываемая в работе технология создания продукционных систем, основанная на теоретико-категорных концепциях, также принадлежит автору.
Теоретическая значимость работы
Теоретическая значимость работы состоит в том, что построенная теория позволяет с единых позиций описать моменты, являющиеся общими для самых разных исследований, относящихся к интеллектуальным системам, основанным на знаниях. В виде, не зависящем от конкретных структур данных, с которыми работает система, могут быть сформулированы алгоритмы вывода, алгоритмы анализа и тестирования базы знаний, алгоритмы автоматического формирования базы знаний.
Построенный автором теоретико-категорный язык позволяет формально определить операции, осуществимость которых необходима для реализации исследуемого алгоритма манипулирования знаниями, проверять осуществимость этих операций для категории, описывающей заданную структуру знаний, и, таким образом, выбрать алгоритм решения задачи, пригодный для работы в рамках этой структуры. Развитая автором теория позволяет сводить операции манипулирования знаниями к более простым теоретико-категорным операциям.
Практическая значимость работы
Практическая значимость состоит в том, что развитая в диссертации технология позволяет существенно сократить трудозатраты на создание и развитие прикладных систем.
При участии автора была создана экспертная оболочка «Знаток», которая была впоследствии переписана в соответствии с концепциями изложенного в диссертации алгебраического языка описания продукционных систем представления знаний и с категорной технологией разработки продукционных систем. Некоторые программные системы, созданные на базе системы «Знаток», содержатся в приведенном ниже списке. Другие системы из этого списка были созданы независимо от оболочки «Знаток», на различных платформах.
-
На базе экспертной оболочки «Знаток» был создан программный комплекс "СВАЯ" для оценки несущей способности свайных фундаментов. Работа была сделана в ходе выполнения научно-исследовательских работ по договору N 183/89 между кафедрой «Основания и фундаменты» Московского Института Инженеров Транспорта и МО-19 Министерства транспорта и строительства, с участием лаборатории ИППИ РАН. Использование развитой в работе технологии позволило значительно сократить трудозатраты на создание программного продукта. Система была передана заказчику.
-
Работа с нечеткими данными была реализована в системе «Мета ЭС», служащей для консультации в области самих экспертных систем. И нечеткие, и
динамические данные были реализованы в сейсмопрогностической системе «Сейсмо». Система «Сейсмо» была передана в Институт Физики Земли РАН согласно договору между ИППИ и ИФЗ, заключенному в рамках Государственной научно-технической программы N18 «Глобальные изменения природной среды и климата», направление 1 - «Глобальные изменения природной среды», проблема «Сейсмичность и связанные с ней явления», проект 3.1.1 «Построение альтернативных моделей развития сейсмического процесса и предвестников». Справка об использовании результатов диссертации приложена к работе.
-
Упрощенный вариант продукционной сети, разработанной на основе теоретико-категорного описания продукции и алгоритмов автоматического формирования сети, был применен в системе автоматизации ввода грузодокументов в ЭВМ, осуществляемого оператором морского порта в ходе погрузки судна.
-
Продукционная сеть была использована в задаче выявления конструкций со значением обусловленности. Эта система создавалась в рамках проекта РФФИ 07-07-00391-а, посвященного алгоритмам выявления отношений обусловленности в текстах директивного характера.
-
Саморазвивающаяся продукционная сеть использовалась в Российском научном центре рентгенорадиологии для сбора и анализа информации о произведенных назначениях лекарственных средств. Справка об использовании программы приложена к диссертации.
-
Саморазвивающаяся продукционная сеть была использована при разработке комплекса программ по анализу и распознаванию речи. Созданный автором модуль работает на завершающей стадии распознавания. В случае, если процесс распознавания дает несколько возможных вариантов ответа, этот модуль позволяет выбрать из них наиболее приемлемый с семантической и логической точек зрения. Акт о передаче программы ООО «Спич Драйв» приложен к диссертации.
-
Построенная автором динамическая продукционная система вошла в аппаратно-программный комплекс макета Центра мониторинга, предназначенный для обнаружения значимых событий контролируемых активностей. Продукционная система осуществляет предсказание развития соответствующей активности на основе происхождения событий с целью проверить правильность выбора значимых событий. Акт об использовании результатов работы концерном ОАО «Радиотехнические и информационные системы» приложен к диссертации.
-
Материалы диссертации позволили поставить на кафедрах Информационных технологий и Прикладной информатики Факультета физико-математических и естественных наук Российского университета дружбы народов новый цикл лекций «Теория категорий и искусственный интеллект» для студентов старших курсов. Соответствующий акт приложен к диссертации.
Методология и методы исследования
Методы исследования, на которых основана работа, могут быть разбиты на две группы: теоретические исследования и моделирование средствами программирования на компьютере. Теоретические исследования основаны на использовании разделов математики, близких к излагаемой в работе теории, таких как теория категорий, теория частично упорядоченных множеств и теория решеток, теория универсальных алгебр. Методы компьютерного моделирования связаны с многолетней работой автора над созданием экспертных систем разной степени прикладной значимости, начиная от модельных систем, иллюстрирующих работоспособность тех или иных алгоритмов, кончая прикладными системами, которые были переданы заказчику.
Положения, выносимые на защиту
На защиту выносятся следующие результаты.
- Предложена концепция обобщенной продукции как фундаментального элемента систем представления знаний и построена математическая теория таких продукций, основанная на языке теории категорий.
- Введено понятие -категории и показано, что такая категория позволяет
описать многие важные для практики системы продукций. Исследованы свойства
-категории.
- Определены на теоретико-категорном языке операции работы со
знаниями. В частности, определены понятия наименьшего обобщения и
наибольшего частного случая пары образцов и исследованы вопросы их
существования.
- Предложена методика модификации продукционной системы,
позволяющей перестроить ее для работы со знаниями нестандартного характера,
например, нечеткими или динамическими, основанная на преобразовании
категории, описывающей эти знания.
- Предложена архитектура продукционной сети, реализующая
представление сложной задачи в виде сети более простых задач. Такая сеть может
быть использована для управления большими системами, для которых
применение стандартной архитектуры приводит к очень большому числу
продукций.
- Предложена основанная на алгебраической теории технология разработки
продукционных систем, позволяющая существенно уменьшить трудоемкость их
создания и развития.
Степень достоверности и апробация результатов
Результаты диссертации докладывались и обсуждались на следующих семинарах и конференциях: Общемосковский научный семинар "Проблемы искусственного интеллекта" – 2 выступления, Научная сессия НИЯУ МИФИ-2015, секция «Интеллектуальные системы и технологии», 11th Joint Conference, JCKBSE 2014, Volgograd, Russia, Четвертая всероссийская мультиконференция по проблемам управления,т.1, Таганрог, 2011, Двенадцатая национальная конференция по искусственному интеллекту с международным участием, Тверь,
2010 г., Десятая национальная конференция по искусственному интеллекту с международным участием., Joint Conference on Knowledge-Based Software Engineering 2006, Девятая национальная конференция по искусственному интеллекту 2004 г., Восьмая национальная конференция по искусственному интеллекту. Коломна, 2002., Fifth Joint Conference on Knowledge-based Software Engineering, 2002, Международная конференция по проблемам управления. Москва, Российская академия наук, Институт проблем управления,1999, Научная сессия МИФИ-99. Москва, 1999., II Всесоюзная конференция "Искусственный интеллект - 90" г.Минск, 1990 г., Всесоюзная конференция по искусственному интеллекту,1988., ИВЕРСИ-85. - Тбилиси, 1985.
Исследования автора явились частью работ по проектам РФФИ 99-01-01152-а 1999-2001 гг., 02-01-00955-а 2002-2004 гг., 05-01-00382-а 2005-2007 гг., 07-07-00391-а 2007-2009 гг., 09-07-00233-а 2009-2011 гг., 12-07-00209-а 2012-2014 гг. и по программе фундаментальных научных исследований президиума РАН N2.24 2001-2009 гг. и N211 2010-2013 гг.
Публикации
Материалы диссертации опубликованы в 39 печатных работах, из них 14 статей в изданиях, рекомендованных ВАК (13 статей в российских журналах из перечня ВАК и 1 статья в зарубежном издании, входящем в международные индексы цитирования), 2 статьи в прочих рецензируемых журналах, 22 статьи в сборниках трудов конференций и прочих сборниках, одна монография.
Личный вклад автора
В написанных совместно статьях автору принадлежат математические результаты, связанные с алгебраической теорий продукций, основанной на аппарате теории категорий, а также части, описывающие детали программирования интеллектуальных систем.
Структура и объем работы
Анализ классификации систем представления знаний в свете создания общей теории
Исторически первыми шагами, связанными с автоматизацией рассуждений, были исследования по автоматическому доказательству теорем. Одним из наиболее заметных результатов, полученных на этом пути, была программная реализация упоминавшегося уже метода резолюции Робинсона [182]. Эти работы были сделаны раньше, чем начались исследования по представлению знаний, и, если исходить из понимания знаний, изложенного конце п. 1.1.1, их нельзя отнести к этим исследованиям. Фактически метод резолюции - это полный перебор всех возможных путей, которые могут привести к доказательству нужного утверждения. Никаких попыток выделить определенные направления движения и предпочесть их другим, там нет. Однако метод резолюции не только был первым, он впоследствии вошел как составная часть во многие системы представлений знаний. Пример - система STRIPS, основанная на правилах, но использующая резолюцию в процессе применения этих правил.
В дальнейшем методы автоматического доказательства теорем развивались, приобретая в том числе и качества, свойственные системам представления знаний. К примеру, в них активно использовались правила. Использование правил является шагом в направлении систем представления знаний. Действительно, конъюнкция A&B эквивалентна каждому из правил: -A B и -тB= A (знак -, здесь обозначает отрицание, знак = -импликацию). Обычно, однако, полезным является одно из этих двух правил, другое используется крайне редко. Замена конъюнкции правилом позволяет сосредоточиться именно на том направлении рассуждения, которое обычно бывает полезно. Язык Prolog, скажем, записывает хорновские выражения в виде правил.
Отметим также работы [12-14,21], в которых предлагается ряд языков, называемых авторами позитивно-образованными языками. По своим выразительным возможностям они эквивалентны языку исчисления предикатов первого порядка, однако имеют целый ряд особенностей, дающих большую эффективность в приложениях. Эти особенности перечислены в указанных работах.
Как уже отмечалось, идеи, появившиеся первоначально в рамках развития нелогического подхода, со временем были адаптированы логическим подходом, где они получили более развитое математическое описание. Это относится и к фреймам, и к семантическим сетям. В работах [135, 136] показано, как фреймы могут быть записаны на языке логики предикатов первого порядка. В рамках логического подхода были созданы языки, основанные на фреймовом подходе к представлению знаний, такие, как KEE [127] и Kappa [140]. Близкие идеи используются в языке KL-ONE [115] и выросшем из него языке CLASSIC [114].
Идея записать семантическую сеть в виде унарных предикатов, описывающих понятия, и бинарных предикатов, описывающие связи между ними, привела к созданию дескрипционной логики [158]. Она реализует компромисс между вычислительной сложностью и выразительностью. При переводе сетевых и фреймовых понятий на язык логики не всегда нужны в полной мере алгоритмы автоматического доказательства теорем, можно построить более простые алгоритмы вывода [113].
Наряду с дескрипционной логикой в представлении знаний полезными оказываются модальные логики [134] и немонотонные логики [128].
Вернемся к мысли, высказанной в начале этого раздела: логический и нелогический подход часто развивают одни и те же идеи, относящиеся к использованию знаний, хотя логический подход использует при этом значительно более развитый математический аппарат. В соответствии с этим, эти идеи могут быть в равной степени переведены на теоретико-категорный язык, независимо от того, были ли они сформулированы в терминологии логического или нелогического подхода. В дальнейшей части работы используется почти исключительно формулировки, свойственные нелогическому подходу. При описании на теоретико-категорном языке понятий, сформулированных в рамках логического подхода, возникают существенно более сложные категории, поэтому эта тема в работе почти не освещена и будет служить предметом дальнейших исследований.
Приведенная выше терминология – продукционные, сетевые, фреймовые системы представления знаний – многие годы является общепринятой и уже в силу этого обстоятельства определенно имеет право на существование. Тем не менее, абсолютный идеал недостижим, и описанная выше классификация также не является идеальной. На взгляд автора, в ней смешиваются разные понятия: способ записи, кодирования знаний и способ организации, структурирования этих знаний.
Рассмотрим, к примеру, фреймовые системы. Заслуга М.Минского состоит не в том, что он придумал конструкцию, состоящую из слотов, а в первую очередь в том, что он понял: знания представляют собой не множество мелких фактов, а крупные блоки информации, описывающие типичные ситуации, и чем важнее ситуация, тем больше и подробнее является описывающий ее блок. Определение «фрейм – описание стереотипной ситуации» не содержит никаких указаний на то, на каком языке сделано это описание. Оно может представлять собой и набор
Примеры теоретико-категорного описания продукций
Продукцией из S в T называется пара образцов - S-образец и Т-образец - с общей областью конкретизаторов. Иными словами, продукция из S в Т - это пара морфизмов cp:X- S и \\г\Х Т. Для записи такой продукции будем использовать обозначение (X,S,T, p,\\t) или просто (qw).
Будем также использовать диаграмму 5, —-—X— —»7. Такая продукция действует на S-ситуации, превращая их в Г-ситуации. Продукция (Х,5,Г,ср,у) считается применимой к ситуации а: A -+S, если эта ситуация сопоставима с образцом (X,S,q ), т.е. а = фР для некоторого $:А Х. Результатом применения продукции (Х,5,Г,ф,\у) к ситуации а в этом случае считается ситуация \\J$:A T (этот морфизм является ситуацией в силу условия ситуационной замкнутости). Снова отметим, что результат применения продукции к ситуации определен неоднозначно, ибо морфизм Р: А —» X не определяется однозначно равенством а = фР.
В дальнейшей работе определенная таким образом на языке теории категорий продукция будет называться ТК-продукцией.
Сразу же опишем один важный способ определения множества ситуаций, который будем многократно использовать в дальнейшем. Фиксируем некоторый объект / категории C, который будем называть источником ситуаций. Положим
Таким образом, ситуации – это в точности морфизмы с областью конкретизаторов I . Очевидно, что условие ситуационной замкнутости для так определенных ситуаций выполняется.
Большая часть теоретического материала, содержащегося в диссертации, будет иллюстрироваться на сравнительно несложных примерах систем образцов. Эти примеры описаны в первой части настоящего раздела. Основу каждого примера составляет некоторая категория. Символ, которым будет обозначаться эта категория, будет использоваться и для названия самого примера.
Во второй части описаны более сложные примеры, в значительной части взятые из реальных систем.
Фиксируем некоторое множество А, которое будем называть алфавитом. Конечную последовательность символов этого множества А будем называть строкой. Множество строк обозначим символом S. Пусть V - некоторое множество, элементы которого будем называть переменными. Потребуем выполнения условия А ел V = 0. Положим А = AVJV и пусть S - множество конечных последовательностей элементов множества А . Категорию L построим следующим образом. Объектами категории L будем считать множества Sn, /7 = 0,1,2,... . В частности, под S0 понимается некоторое одноэлементное множество. Это достаточно логично: если, к примеру, понимать под S" множество последовательностей вида (s1,...,sn), S;GS, то множество S0 должно состоять из единственной пустой последовательности (). Если последовательность s є S не содержит переменных, отличных от х1, …,хп, будем писать s = s(X1,...,xn). При этом не требуется, чтобы строка s(x1,...,xn) содержала бы все переменные х1, …,хп, важно, чтобы она не содержала никаких других переменных. Если t S, i = 1,...,n, будем обозначать через 5 (/l1,.../w) результат подстановки в s подстрок tt вместо переменных .Понятно, что если tteS, 1 = 1,...Jl, то 5(ґ1,.../и)є5, т.е. строка 5 (/l1,.../w) не содержит переменных. При этом может оказаться, что не все tt были реально использованы.
Для каждого элемента s = s(x1,...,xn) множества определим отображение q s:Sn S следующим образом: если ( 1,...;„) є S", то qs(t1,...,tn) = s(t1,...,tn). Для фиксированного множества переменных х1,...,хп и набора элементов st = si(x1,...,xn)e S , і = 1,2,...,га, зададим отображение q S1 :Sn -+Sm формулой s1,...,(h,... ) = {s1(h,...,tn),.. m(t1,...,tn)). Такие отображения и будут морфизмами нашей категории. Для того, чтобы закончить изложение примера, нужно проверить корректность введенных определений. В категории должны существовать единичные морфизмы и класс морфизмов должен быть замкнут относительно композиции. Поскольку мы строим конкретную категорию, в качестве композиции должна играть обычная композиция отображений. Стало быть, мы должны проверить, является ли композиция двух отображений вида Ф я снова отображением такого же вида и можно ли записать в таком виде тождественное единичных морфизмов должны выступать тождественные отображения, а роль отображение.
Доказательство. Рассмотрим сначала случай k = 1, тогда второе отображение примет вид ф, : Sm — S. Согласно данному определению, все строки st є S должны содержать один и тот же набор переменных. Пусть это будут переменные х1,...,хп, т.е. Sj = 5/(x1,...,xw). В свою очередь, пусть t = t(y1,...,ym). Построим теперь строку и є S , подставив в t(y1,...,ym) строки (JC1,..., ) вместо переменных yt, і = 1,...,т. В результате такой подстановки из строки t исчезнут все переменные, которые в нее входили, зато в нее попадут вместе со строками st переменные х1,...,хп, потому мы можем написать и = и(х1,...,хп) = 1(х1,...,хп),... т(х1,...,хп)). Докажем теперь, что Ф ... Ф, = Фм . Для того, чтобы в этом убедиться, рассмотрим набор строк a- eS, j = 1,2,..,п и посмотрим, что представляет собой строка ф51 ((а1,...,ап) и что - строка ц и(а1,...,ап). Первая строка получается в результате следующих двух операций: сначала в строках st переменные Xj заменяются строками а} (это - действие отображения Ф5 ), затем получившиеся строки подставляются вместо yt в строку t (это - действие отображения ф,). Вторая получается в результате тех же действий, но проделанных в обратном порядке: сначала в строку t подставляются st вместо yt, в результате чего строка t превращается в строку и, затем в этой строке переменные х заменяются на а Ясно, что результат в обоих случаях будет одинаков. Случай произвольного к рассматривается аналогично. Рассуждая, как выше, мы получаем, что ф5 ф? ( = фм и , где щ,…,ик - результат подстановки строк s ,... ) в t1(y1,...,ym),…, tk(y1,...,ym) вместо переменных yt. Мы закончили построение категории L. Теперь, зафиксировав любые два ее объекта в качестве множества ситуаций и множества конкретизаторов и выбрав некоторый морфизм между ними, мы получаем образец. Чаще всего в качестве множества ситуаций выступает множество S, тогда роль образца играет отображение ps:Sn S, где s є S . Любые два образца с совпадающим множеством конкретизаторов представляют собой продукцию. Для того, чтобы завершить построение системы образцов, нам надо определить, какие образцы следует считать ситуациями. Будем считать, что ситуация - это образец с областью конкретизаторов S0, т.е. морфизм из S0 в Sm. Согласно определению, такой морфизм имеет вид Ф 2,... :S0 Sm, где SjeS, i = 1,2,.../n, т.е. st не содержит переменных. Такое отображение ставит в соответствие единственному элементу множества S0 набор (s1,s2,...,sm)BSm. Таким образом, мы использовали способ определения ситуаций, описанный в разделе 1.5, взяв в качестве источника ситуаций объект S0.
Задача «крепкий орешек» и семиотическая интроспекция
Ниже мы остановимся на рассмотрении частного случая Q-категории, построенного с использованием понятия свободной алгебры в многообразии универсальных алгебр. Важность этого частного случая видна хотя бы из того факта, что все примеры из раздела 2.2 относятся к подобному виду Q-категорий, что будет показано в разделе 2.4 настоящей главы. В исследованиях автора приводятся другие примеры подобной категории, например, категории, реализующей систему образцов, построенную на базе мультимножеств.
Теория универсальных алгебр изложена, например, в [48, 133]. Ниже приводятся основные определения и вводятся используемые в дальнейшем обозначения.
Пусть задано множество Q, представленное в виде О = О0 О1 Q2 ..., fi,- nfiy = 0 при / у. Оно называется множеством операторов, или сигнатурой. Множество А является Q-алгеброй, если для любого roeQw определено отображение Ап А, которое принято обозначать тем же символом ю. В частности, для а є Q0 должна быть определена константа в А, которую мы будем обозначать символом а(). Гомоморфизм ц :А В Q-алгебр - это отображение, коммутирующее со всеми отображениями из Q, т.е. такое, что для любых а1, а2,...,ап є А, ю є Qw, ф(го(я1 ,a2,...,a„)) = ш(ф( ), ф2 ),...,ф„ )). Многообразие М Q-алгебр состоит из всех Q-алгебр, удовлетворяющих некоторой заданной системе тождеств. Алгебры многообразия вместе с гомоморфизмами Q-алгебр образуют категорию, которую мы будем обозначать той же буквой М.
Пусть задано многообразие М Q-алгебр. Известно, что для каждого множества X существует свободная в многообразии М алгебра SX с множеством образующих X, т.е. такая алгебра SX є М вместе с вложением т\х:Х 8Х, что любое отображение ср:Х- М, МєМ однозначно продолжается до гомоморфизма Q-алгебр у: SX - М, т.е. (2.6) ф = Лх.
Приведенные в примерах раздела 2.2 способы построения категорий L, Еи S могут быть обобщены на случай свободной алгебры в произвольном многообразии универсальных алгебр. Пусть задано многообразие М Q-алгебр. Фиксируем счетное множество X, элементы которого будем называть переменными, и рассмотрим свободную в М алгебру А с множеством образующих X. Как известно, каждый элемент А может быть представлен некоторым выражением, составленным из операторов множества из Q и переменных из множества X. При этом разные выражения могут обозначать один и тот же элемент алгебры А. Будем использовать для аєА обозначение а = а(х1,х2,...,хп), если элемент а может быть представлен выражением, не содержащим переменных, отличных от х1, х2,…, хп. Если at = йгг(х1,...,хи) є 4, і = 1,...,т, определим отображение Ц а1,...Рт :Ап -+Ат формулой
Категорию М построим аналогично тому, как это делалось в для категорий L, Еи S в примерах раздела 2.2. В качестве объектов категории возьмем множества Ап, п = 0,1,2,.... Морфизмами категорий будем считать отображения вида Фй1,... :А" Ат. Доказательство того, что определение является корректным, повторяет доказательства соответствующих лемм из раздела 2.2. Я не буду приводить это доказательство, тем более, что следующая лемма демонстрирует другой способ построения подобной категории.
Известно, что отображение S, ставящее в соответствие каждому множеству X свободную в многообразии алгебру SX с множеством образующих X, а каждому отображению ср:Х- 7 - морфизм алгебр Fcp: FX —» FY, являющийся однозначно определяемым продолжением отображения ср:Х- 7 на FX, представляет собой функтор из категории множеств в категорию алгебр многообразия М. Он является левым сопряженным к забывающему функтору 7:M Set, который ставит в соответствие каждой алгебре из М ту же алгебру, рассматриваемую как множество, а каждому морфизму алгебр - тот же морфизм, рассматриваемый как отображение множеств. Пара сопряженных функторов S и Т определяют монаду F = TS. Роль единицы монады играет система вложений цх : X —» SX. Опишем строение умножения д. в монаде. Если X множество, то элементы множества FX являются правильно построенными выражениями из операторов множества Q и элементов множества X. В свою очередь элементами множества F2X, являются выражения, построенные из операторов и выражений из множества FX. Такие выражения сами являются выражениями, построенными из операторов и элементов множества X, поэтому можно считать, что F2X = FX. Легко видеть, что умножением \ix : F2X —»FX является тождественное отображение. Таким образом, по любому многообразию М и счетному множеству X мы можем построить монаду F и, следовательно, категорию Q.F х. Теорема 2. Пусть M - описанная выше категория, построенная по многообразию М П-алгебр, Q.FX - П-категория, построенная по тому же многообразию и счетному множеству X. Категории M и ClFX эквивалентны. Доказательство. Для доказательства требуется построить полный унивалентный функтор H:M QFX такой, что каждый объект категории ClFX изоморфен одному из объектов вида НК, где К - объект категории M. Объекты категории M - это множества А", п = 0,1,2,..., где А = FX свободная в многообразии алгебра с множеством образующих X. Перенумеруем элементы множества X, полагая Х = {х1,х2,..}, и положим U0=0, U„={x1,x2,...jc„}, /7 = 1,2.... Для каждого и = 1,2,... определим отображение множеств 9W : Q.(Un ) - Ап формулой 9И(a) = (a(X1\a(x2),...,а( и)) для аєП(и). Поскольку п(с/0) и А0 одноэлементные множества, отображение 90 :O(t/0)- А0 определяется однозначно. Очевидно, что 0„, п = 0,1,... - биекции. Искомый функтор н построим следующим образом. Положим, н(Ап)=П(ип). Всякий морфизм ф: А" - Ат в категории M имеет вид ф = фя Й , Ф«1,... ( 1,.../«) = («1( 1,.../«),... ( 1,.../«), где at =аі(хи...,хп)єА, і = 1,2,...,т. Определим отображение \y:Um - FUn формулой ці(хг ) = at и положим tfcp = у : фп ) - Q( ). Отметим, что диаграмма коммутативна для всех т, п. В самом деле, если Ф = ФЯ й , а. =а;(хи...,хп)еА, i = \,2,.../n и абф„), т.е. а: 7„ , то также ф(0„(а))=ф(а(х1),..,а(х„)) = ( ,..., ), где bt - результат подстановки выражений ccfa), …, OC(JC„) вместо переменных JC1,…,JC„ в о,.. С другой стороны, Яф(а)=у (а)=}іх oFaoy, Я(tfcOfo ) = \І х (Fa jc,-))) = (Fafo)). Последнее выражение представляет собой результат замены переменных л ,…, л;и на выражения в ai, откуда и следует коммутативность диаграммы.
Можно, следовательно, заключить, что Яф = б ф и . Из этого равенства сразу видно, что #(q i/) = ЯфЯу и #1 = 1, т.е. # действительно является функтором. Из этого же равенства следует, что этот функтор является полным и унивалентным.
Программируемая оболочка экспертной системы
В ряде интересных для практики случаев отсутствие наименьшего обобщения у пары образцов может быть до некоторой степени компенсировано существованием некоторого конечного набора обобщений. Рассмотрим эту тему подробнее.
Следуя терминологии, принятой в исследованиях, посвященных унификации (см., например, [102,106]), будем называть множество М полной системой обобщений образцов ср и \\i если выполнены следующие условия: 1. Ф о, \/ о для всех аєМ; 2. Если т - образец, такой, что (р т и \/ т, то для некоторого аєМ имеем а х. Если в дополнение к этим двум условиям выполнено третье: 3. система М является минимальной, т.е. при исключении из нее любого образца условие 2 перестает выполняться, будем называть множество М минимальной полной системой обобщений этих образцов. Используется также терминология: множество м называется коинициальным по отношению к множеству {т: ф т,1/ т} [73]. Очевидно, что если полная система обобщений состоит из единственного элемента, то этот элемент является наименьшим обобщением. Пара образцов может не иметь и полной системы обобщений, однако, как мы увидим в следующей главе, во многих интересных частных случаях полная система всегда существует и, более того, является конечной. 119 Приведем некоторые факты, относящиеся к полным и минимальным полным системам обобщений. Лемма 21. Условие 3 в определении можно заменить на условие 3 . если о1бМ,о2еМио1 о2, тоо1=о2. Доказательство. Для доказательства импликации 3 3 заметим, что если O1 еМ, о2 еМ, 01 о2 и 01 =о2, то при удалении из системы образца а2 условие 2 определения по-прежнему будет выполнено, что противоречит минимальности системы.
Для доказательства обратной импликации допустим, что система не является минимальной, и пусть, например, некоторый элемент а2 может быть удален из нее без нарушения условия 2. Поскольку ф ст2 и а2, найдется 51єМ-{ 52\ такой, что 51 52, что противоречит условию 3 .
Известно, что в упорядоченном множестве точная верхняя грань, если она существует, определяется однозначно. Аналогичный факт верен и для минимальных полных систем обобщений. Он вытекает из следующего утверждения:
Лемма 22. Если М - минимальная полная система обобщений образцов ф и \/, то М совпадает с множеством N минимальных элементов множества {т: ф т, ц/ т}.
Доказательство. Пусть тєИ. Это означает, что ф т, ці х. Тогда а х для некоторого аєМ. Из минимальности т следует, что т = т, т.е. аєМ. Таким образом, N M. Обратное включение получаем следующим образом. Пусть а є М, и допустим, что ср т, \\і т, т а. По определению множества М должен существовать элемент о єМ такой, что а т. Неравенства а т а и лемма 21 дают равенство а = т = а, откуда т є М. Следствие. Если М и N - минимальные полные системы обобщений образцов ф иy, то M = N. Лемма 23. Пусть M - полная система обобщений. Если удалить из нее все элементы, не являющиеся в ней минимальными, то получившаяся система будет представлять собой минимальную полную систему обобщений.
Доказательство. При доказательстве эквивалентности условий 3 и 3 определения минимальной полной системы мы видели, что при удалении таких элементов условия 1 и 2 не нарушаются, в то же время система, состоящая только из минимальных элементов, удовлетворяет, очевидно, условию 3 , и, следовательно, является минимальной. Следствие. Пара образцов, имеющая конечную полную систему обобщений, имеет и конечную минимальную полную систему обобщений.
Приведенные леммы и их доказательства очень близки к доказательству доказательства аналогичных утверждений из работы [106]. Формально приведенные леммы не следуют из результатов этой работы, ибо автор формулирует их в терминах подстановок, но они легко могут быть повторены для морфизмов произвольной категории, что и было сделано выше.
Аналогично минимальной полной системе двух образцов можно определить минимальную полную систему обобщений произвольного множества образцов. Формальное определение таково: минимальной полной системой обобщений для некоторого множества P образцов называется множество M образцов, удовлетворяющее следующим условиям: 1. Если уєP и аєM, то ф о; 2. Если образец т таков, что (р т для всех ц єP, то а х для некоторого аєM; 3. При исключении из множества M любого элемента условие 2 перестает выполняться. Известно, что верхняя грань нескольких элементов может быть получена последовательно с помощью взятия верхних граней пар элементов: сперва определяется верхняя грань двух элементов, затем верхняя грань этой верхней грани и третьего элемента и т.д. Отсюда, в частности, следует ассоциативность операции взятия верхней грани пары элементов.
Сформулируем аналогичный результат для минимальных полных систем обобщений. Лемма 24. Пусть ф, ці, х - образцы, М - минимальная полная система обобщений для ф и \\i, La - минимальная полная система обобщений для пары аєМ и %. Тогда объединение множеств La для всех аєМ представляет собой полную систему обобщений образцов р, q и г и, следовательно, содержит их минимальную полную систему обобщений.
Доказательство. Для любого тєІс имеем т х, т а ф, т а у, т.е. выполнено условие 1 определения минимальной полной системы обобщений. Для доказательства условия 2 заметим, что если ф, Х ці, X х, то, согласно определению множества М Д с для некоторого JEM, а согласно определению множества La, X х для некоторого тєЬа. Отсюда следует некоторый аналог ассоциативности для минимальных полных систем: если М - минимальная полная система обобщений для образцов ф, у и х, а Z,;, а єМ - минимальная полная система обобщений для пары ф и а, то объединение множеств L a отличается от объединения множеств La только неминимальными элементами, после их удаления эти объединения совпадут, ибо оба превратятся в минимальную полную систему для ф, \/ и х .