Содержание к диссертации
Введение
1. Формальный язык. Денотативная семантика отношений языка
1) Основные определения 22
2) Семантическая интерпретация. Денотативная семантика отношений 27
2. Дедуктивная модель предметной области. Реализация логического вывода в рамках дедуктивной модели
1) Эрбрановская интерпретация конструкций языка 51
2) Алгоритм доказательства запроса к базе знаний без учета семантики отношений 58
3. Интегрированная модель предметной области
1) Семантическая память 79
2) Предварительные определения и обоснование выводимости 87
3) Общий алгоритм доказательства запроса к базе знаний 110
Выводы
- Семантическая интерпретация. Денотативная семантика отношений
- Эрбрановская интерпретация конструкций языка
- Алгоритм доказательства запроса к базе знаний без учета семантики отношений
- Предварительные определения и обоснование выводимости
Введение к работе
Модели представления знаний
Среди различных моделей, лежащих в основе современных систем представления знаний, можно выделить два класса, получившие наиболее широкое распространение: класс дедуктивных и класс концептуальных моделей.
Системы, основанные на дедуктивных моделях, обычно применяются для представления знаний дедуктивной природы, когда связи между утверждениями удобно выражать каузальными конструкциями "если-то".
В тех же случаях, когда система знаний о предметной области сводится к иерархии понятий, определению их свойств и наследованию свойств в рамках иерархии, удобно строить ее на основе концептуальных моделей данных.
На практике описание предметной области всегда содержит и иерархически связанные понятия и каузальные связи между утверждениями о понятиях.
В данной работе исследуется возможность интеграции методов этих двух моделей в общей системе представления знаний.
В основе дедуктивных моделей лежит эрбрановская интерпретация данных. В формализмах такого рода основными элементами языка являются термы (константы, переменные, функции), служащие для обозначения различных объектов, и n-местные предикаты (имеющие термы в качестве аргументов), предназначенные для фиксации отношений между объектами. В эрбрановской интерпретации любая константа представляет собой лишь цепочку символов, а интерпретация предиката отношения задается множеством значений аргументов, на которых этот предикат истинен. Истинность предиката в базе знаний задается либо фактом — явным указанием константных термов, на которых предикат истинен, либо вычисляется при помощи заданных пользователем правил (логической программы). Таким образом, множество значений аргументов, на которых предикат истинен, определяется результатом работы логической программы. Это означает, что интерпретация данных отделена от самих данных и перенесена на работающие с ними логические программы. Сами данные без соответствующих программ представляют собой не более чем набор символов, которому различные программы могут придать различную интерпретацию. Таким образом, представление знаний в системах на основе дедуктивных моделей определяется способом его обработки.
В этих условиях произвол в выборе набора отношений, связывающих данные, определения их местности и назначения каждого из мест создает серьезные технологические трудности при формировании систем знаний достаточно большого объема. В результате, разработка системы представления знаний на основе дедуктивных моделей сопровождается разработкой внесистемных соглашений о смысле занесенных в базу отношений.
Другой технологический недостаток эрбрановской интерпретации, также обусловленный ее общностью: построение описания той или иной предметной области сопряжено с необходимостью каждый раз заново описывать универсальные отношения, свойственные окружающему миру. Иными словами, дедуктивной системе изначально свойственна низкая степень автоматизации процесса построения описания.
Классическими примерами языков, в основу определения которых положена дедуктивная модель, являются язык логического программирования Пролог [40, 39, 44] и логический язык программирования баз данных Дейталог [8, 9, 53].
Важное преимущество Пролога — мощный аппарат оперирования с данными (списки, структуры, арифметические операции), обеспечивающий вычислительную полноту языка. Аппарат оформлен в виде встроенных функций, представляющих собой надстройку над инструментом логического вывода. В рамках языка интерпретация данных предметной области осуществляется в терминах исполнения встроенных функций и эрбрановской интерпретации результатов этого исполнения.
Серьезным недостатком Пролога является зависимость результата выполнения программы от порядка записи клауз. Желательно, чтобы формализм представления знаний обладал автоматическим инструментом вывода, дающим одинаковые результаты при обработке семантически эквивалентных конструкций.
Чтобы удовлетворить этому требованию, были созданы различные варианты языков логического программирования, где логика предикатов первого порядка ограничивалась неким ее подклассом (в ущерб вычислительной полноте). Дейталог, будучи примером такого языка, является первым специализированным логическим языком программирования баз данных [41, с. 12]. Создатели языка [53] ставили целью совместить возможности языка логического программирования с возможностью хранения фактов в больших базах данных. В связи с этим, накладываются ограничения на язык логики предикатов первого порядка: в языке отсутствуют функциональные выражения, т.е. возможность конструирования сложных объектов — в качестве терма может выступать только константа или переменная. В отличие от прологовского нисходящего вывода, основанного на методе резолюций, в Дейталоге используется восходящий метод вывода. За счет такого метода вывода решается проблема перестановочности клауз, т.е. в Дейталоге результат работы логической программы не зависит от порядка записи клауз.
Множество фактов в Дейталоге образует экстенсиональную базу данных, а правила— интенсиональную базу данных, вместе эти базы образуют логическую базу данных. Единицей хранения в экстенсиональной Дейталоговской базе данных является кортеж значений аргументов предиката.
Заметим, что, как в Прологе, так и в Дейталоге нет явно вводимого отрицания, т.е. невыводимость истинности предиката в данной базе знаний приравнивается к ложности этого предиката. Представляется, что недостаточная выразительность и процедурность описаний, выстраиваемых на основе дедуктивных моделей, явилась одной из побудительных причин создания специальных языков, нацеленных на описание данных [51, с.4]. В основу таких языков положены концептуальные модели данных, ориентированные, в первую очередь, на представление сложных иерархических структур.
В настоящее время одной из областей применения языков концептуального моделирования являются системы обработки текстов на естественном языке, являющиеся составной частью систем для представления знаний. Системы обработки текстов на естественном языке (NLP — natural language processing) нацелены на извлечение семантической информации, содержащейся в тексте, на основе общеязыковых представлений. Необходимые лексические сведения в такой системе обеспечивает словарь с достаточно формализованной словарной статьей. В настоящее время большинство исследователей в данной области признают необходимость построения специального концептуального словаря (вычислительной онтологии), где данные словарной статьи представляются при помощи некоторого формального языка [49, 48, 20, 21, 26, 15]. Формальный язык используется в системе NLP двояким образом: во-первых — для представления словарной статьи, во-вторых — для окончательного представления извлеченной из текста информации.
Пример описания из семантического словаря В.А. Тузова:
ВЫПУСК $1202(Тв, Род, Из, наВинЩля)— описание базового понятия в классе, имеет четыре аргумента, которые должны быть заполнены соответствующими актантами: кем осуществляется выпуск, кого (что) выпускают, откуда и для чего.
ВЫПУСКНИК Орег01_о2(ШКОЛА$1119110, ВЬІПУСК$1202(5іпд_о %2)) "Выпускник - это тот, кто является вторым актантом действующего (или действовавшего когда-то) процесса выпуска из класса $1202, осуществляемого некоторой школой из класса $1119110 ".
Здесь ВЫПУСК$1202— далее не трактуемое базовое понятие класса, т.е. концепт, а понятие ВЫПУСКНИК определяется через концепты ВЫПУСК$1202и ШКОЛА$1119110. Цифры обозначают положение класса в общей иерархии объектов.
Основная информация, представляемая в семантическом словаре — это иерархические взаимосвязи и отношения между отдельными концептами. Используя концептуальный словарь, система NLP пытается сформировать представление смысла текста, выраженное на соответствующем формальном языке. При помощи этого же формального языка эксперт в предметной области может пополнить данное представление смысла новыми сведениями, которые он желает зафиксировать в системе представления знаний.
Основными элементами языков концептуального моделирования являются классы объектов и бинарные отношения. Поскольку любой п-арный предикат может быть представлен совокупностью бинарных предикатов [43, с. 146], то эти элементы языка позволяют выразить практически любые отношения между объектами.
Семантика классов и бинарных отношений задается при помощи интерпретации I относительно некоторого множества D1 (домен интерпретации). Произвольному объекту а сопоставляется элемент d є D1, произвольному классу А — некое подмножество А1 с D1, а произвольному бинарному отношению R— подмножество RJcD D1. [1, с.6] Далее эта интерпретация распространяется на все операции, определенные для классов и бинарных отношений. Из такой интерпретации вытекает, что мы можем определить некоторое бинарное отношение между классами объектов, или задать некоторое свойство класса, и это отношение, или это свойство будет автоматически распространяться на все элементы этих классов.
Таким образом, интерпретация данных в языках концептуального моделирования связывается с самими данными. В этом случае данные приобретают семантическую значимость, одновременно выражая и факты, и способ их интерпретации [52, с. 18]. Если в прологовской базе знаний взаимосвязи между различными данными представлены отдельно от самих данных, т.е. при помощи логических программ, то в концептуальной модели языковые средства, использованные для записи самих данных, определяют виды связей между данными.
В языках концептуального моделирования также осуществляется логический вывод. Если в языках логического программирования вывод осуществляется на основе заданных пользователем правил, то в концептуальных моделях для вывода используются семантические правила, автоматически формируемые на основе семантики данных в базе знаний. При этом вычислительной полноте языков логического программирования противопоставляется логическая разрешимость, т.е. возможность получения определенного (ДА или НЕТ) ответа на запрос.
В настоящее время выделяются два вида языков, в основе которых лежат концептуальные модели данных: концептуальные графы и языки, обычно обозначаемые как "языки типа KL-ONE". "K.L-ONE" — название первой системы такого типа, реализованной Бречманом (Brachmann) и Шмульцем (Schmolze) [4].
Концептуальные графы [30, 43, 19, 27, 28, 22, 11, 2] и построенные на их основе семантические сети — наиболее полно разработанный на сегодняшний день формализм для наглядного (графического) представления знаний. Концептуальный граф содержит два типа узлов: узлы, представляющие объекты (или классы объектов), и узлы, представляющие отношения между объектами. На концептуальном графе выделяются отношения вида IS-A, которым устанавливается принадлежность объекта некоторому типу (классу) или вложение одного типа (класса) в другой. Относительно отношений вида IS-A определено наследование свойств объектов (их отношений с другими объектами) от типа к подтипу и к объекту, конкретизирующему данный тип. Это означает, что денотативная семантика остальных отношений задана относительно отношений вида IS-A. Наряду с отношениями вида IS-A, вводится отношение между множеством и элементом множества, относительно которого не определено наследование свойств. На концептуальных графах также могут быть введены кванторы существования и всеобщности, а также явное отрицание, что отличает концептуальные модели от Пролога и Дейталога.
Здесь в квадратных скобках изображаются концепты, а в круглых — отношения. На графе они заключаются соответственно в прямоугольники и окружности. Двоеточием изображено отношение принадлежности объекта некоторому типу: grey— это конкретный объект, тогда как COLOR и ELEPHANT определяют тип.
Концептуальные графы предоставляют широкие изобразительные возможности, позволяющие непосредственно обобщать концептуальные графы на модальные системы и другие формализмы, трудно представимые логикой первого порядка [43]. Однако, широкие выразительные возможности концептуальных графов, имеют и свою обратную сторону. Задача выстраивания иерархии классов в общем случае сводится к задаче: определить, является ли один концептуальный граф частью другого, а последнее не всегда разрешимо.
Ограничения, накладываемые на изобразительные возможности в языках типа KL-ONE [1, 31, 7, 23, 24, 25, 12], делают задачу выстраивания иерархии разрешимой.
После создания первой системы KL-ONE было создано большое количество систем, реализующих сходные идеи. Был разработан язык ALC, введенный в [29], который принято рассматривать как основу языков типа KL-ONE, так или иначе дополняемую в конкретных системах. [31]
Особенностью языков типа KL-ONE является разделение знаний на терминологическую часть ("Т-box"), содержащую определения концептов и ролей, и базу фактов ("А-box"). Каждому определению концепта или роли в "Т-box" может быть автоматически сопоставлено правило на языке логики предикатов, в зависимости от конструктов, использованных в определении.
Семантическая интерпретация концептов и ролей фиксируется однократно при их определении в "Т-box" и связывается С самими данными. В этом случае данные приобретают семантическую значимость, одновременно выражая и факты, и способ их интерпретации.
Для логического вывода используются правила, полученные при трансляции определений концептов и ролей на язык логики предикатов. Предикаты, употребляемые в полученных правилах, выражают конкретизацию концепта экземпляром или роли парой экземпляров. Для систем типа KL-ONE разработаны различные методы логического вывода с использованием этих правил. Поскольку набор используемых в определениях конструктов ограничен, правила трансляции определений в формулы логики предикатов могут быть однократно заданы в общем виде. Используя определения концептов, система KL-ONE может построить классификатор, автоматически определяющий место каждого из концептов в иерархии. Так, например, если в "Т-box" присутствуют следующие определения концептов: Выс_человек = (and Человек (some рост Высокий)) Выс_толст_человек = (and Человек (some рост Высокий) (some вес Большой)),
то классификатор автоматически поместит Выс_толст_человек в иерархии ниже Выс_человек, сравнив роли, использованные в определении этих концептов. Заметим, что такой классификатор для концептуальных графов отсутствует [3, с.85], и в аналогичной иерархии для концептуальных графов оба концепта Выс_человек и Выс_толст_челоеек останутся подтипами концепта Человек.
"А-Ьох" в KL-ONE состоит из фактов, фиксирующих истинность или ложность унарных и бинарных предикатов при определенных значениях аргументов. На основе рассмотренной выше семантической интерпретации, это означает факты принадлежности (или НЕ принадлежности, ввиду возможности явно указать этот факт) объектов классам или пар объектов бинарным отношениям. Таким образом, база фактов системы состоит из фактов принадлежности объектов классам. Правила, получаемые системой при трансляции определений из "Т-Ьох", позволяют вывести новые факты такого же вида. При таком подходе база фактов допускает хранение в виде таблицы, где названия столбцов есть имена классов и бинарных отношений, а в строках располагаются пометки о принадлежности (или НЕ принадлежности) этим классам или ролям объектов или пар объектов. Такая система хранения приводит к возможности использовать для логического вывода какую-либо вариацию метода семантических таблиц, введенного Э. Бетом. [34] В частности, в системах CARIN и AL-LOG, представляющих собой попытку комбинировать язык типа KL-ONE с применением хорновских правил, была использована техника систем с ограничениями (constraint systems), представляющая собой вариацию метода семантических таблиц. [16, 14]
Серьезным продвижением в развитии концепции языков типа KL-ONE, явилась система CBR (Classes and Binary Relations"), представленная Г.С. Плесневичем в [46, 47]. Предлагается совершенно иная структура входного языка: описание предметной области задается в виде предложений, содержащих утверждения об отношениях между классами, а также между классами и экземплярами. Такой язык обладает большей выразительностью по сравнению с языком систем типа KL-ONE, предназначенным в основном, для описания типов данных. Например, утверждение "любое животное питается либо растениями, либо животными, которые меньше его и питаются растениями" на языке CBR записывается в виде:
EACH Животное X (Ест EACH Растение OR
Ест EACH Животное THAT (Меньше X AND Ест SOME Растение))
Для описания предметной области определено его каноническое представление в виде конъюнкции терминальных элементов, где терминальный элемент— это выражение, содержащее единственное отношение или связку (THAT, OR, AND). Имеется ограниченный перечень конструкций терминальных элементов. Утверждения языка строятся при помощи связок AND, OR, NOT, а также префиксов SOME и EACH в качестве кванторов существования и всеобщности.
Например, можно записать утверждение о том, что все гусеницы едят некоторые растения:
EACH Гусеница Ест SOME Растение.
Совокупность утверждений языка явным образом описывает семантическую сеть, вершинами которой являются классы и экземпляры, а дугами — имена бинарных отношений.
Новые классы вводятся без определения, хотя, благодаря использованию предикатов, возможность определения классов через другие классы также присутствует. При помощи связки THAT можно определить новый класс, состоящий из элементов другого класса, удовлетворяющих условию, выраженному предикатом. Например, можно определить класс животных, которые едят некоторые растения:
Травоядное == Животное THAT Ест SOME Растение.
Здесь Ест — бинарное отношение, Гусеница, Растение, Животное, Травоядное — классы, Ест SOME Растение — предикат.
База знаний в CBR, делится на концептуальную схему, в которую вкіпочаются все предложения общего характера и базу фактов. База фактов, как и "А-box" в системах типа KL-ONE, включает в себя утверждения о принадлежности элементов классам или пар элементов бинарным отношениям.
Для всех конструкций языка определена денотативная семантика на основании теоретико-множественной интерпретации классов и отношений.
Существенной особенностью системы CBR является метод преобразования концептуальной схемы в систему продукций на основании введенной денотативной семантики отношений. Концептуальная схема на этапе трансляции преобразуется в систему продукций в соответствии с определенными правилами трансляции. Продукции представляют собой правила для получения новых фактов.
Полученная при трансляции концептуальной схемы система продукций применяется для осуществления логического вывода, основанного на методе семантических таблиц Бета. Как уже упоминалось, база фактов в CBR представляет собой таблицу с именами классов и бинарных отношений в качестве названий столбцов. Строка в таблице отражает состояние базы фактов, т.е. в нее заносятся элементы, принадлежащие или не принадлежащие соответствующим классам или бинарным отношениям. К базе фактов добавляется отрицание запроса и также заносится в таблицу. Последовательное применение системы продукций к состояниям базы фактов приводит к появлению новых элементов в таблице. Появление в одном столбце пометки о принадлежности и НЕ принадлежности ему одного и того же элемента позволяет сделать вывод о противоречивости базы фактов (т.е. подтверждает запрос). Можно заметить, что в CBR применяется восходящий метод вывода, аналогично восходящему выводу в Дейталоге.
Отметим, что в системе CBR явным образом вводится отрицание, причем теоретико-множественная интерпретация позволяет свести возможные формы отрицания в утверждениях языка к отрицанию элементарного факта принадлежности элемента классу (или пары элементов бинарному отношению). Это сведение осуществляется в процессе трансляции концептуальной схемы в систему продукций. (См. пример трансляции A ISA В.)
Сопоставляя особенности и области применения дедуктивных и концептуальных моделей в системах представления знаний, мы можем видеть, что эти модели предназначены для представления знаний различной природы и не конкурируют, а скорее, дополняют одна другую. Удобно описывать свойства данной предметной области семантической сетью понятий и отношений и столь же удобно каузальные зависимости между отдельными фрагментами сети задавать средствами дедуктивной модели. В связи с этим большой интерес представляет интеграция методов обеих моделей в рамках единой системы представления знаний. Исследованию возможных подходов к решению этой задачи и посвящена данная работа. В качестве примеров языков, комбинирующих методы дедуктивных и концептуальных моделей, можно привести языки CARIN [16] и AL-LOG [5, 6, 13, 14], в которых описание данных при помощи языков типа KL-ONE дополняется правилами в виде хорновских дизъюнктов. В обеих системах используются правила дейталоговского типа, т.е., без функциональных символов. При этом следствие правила может представлять собой только новый n-арный предикат и не может содержать описания концептов или ролей из терминологической части языка ("Т-box".). В языке CARIN посылка правила может содержать предикаты, представляющие собой концепты и роли из "Т-box", т.е. может содержать отношения принадлежности вида:
хєС или оєС, а также (хь x2)eR или (oi, o2)€R, где х — обозначения переменных, о — экземпляров, С — концепта, R — роли.
В языке AL-LOG правило содержит только предикаты, отличные от ролей и концептов терминологической части, но при этом может дополняться набором ограничений вида хєС или оєС на переменные и константы, входящие в правило. В обеих системах (CARIN и AL-LOG) для осуществления логического вывода используется техника систем с ограничениями (constraint systems).
Недостатками предложенного в языках CARIN и AL-LOG подхода к построению гибридной системы представления знаний являются:
1) правила не позволяют получить новых знаний об отношениях, представленных в дескриптивной части языка;
2) используемые в правилах переменные и константы могут быть определены только на экземплярах.
Это означает, что правила языков CARIN и AL-LOG не позволяют вывести новых сведений ни о принадлежности объектов классам или ролям, ни об отношениях между классами.
В противоположность такому подходу, в данной работе ставится задача использовать дедуктивные правила с целью получения новых сведений именно об объектах и отношениях, описываемых в языке. Предполагается, что вся необходимая информация может быть передана при помощи отношений языка (как это, кстати, изначально полагается и в языках типа KL-ONE), следовательно, не имеет смысла вводить новые предикаты только для использования в дедуктивных правилах.
Семантическая интерпретация. Денотативная семантика отношений
Модели текстов в системе MAZE представлены в концептуальной памяти в канонической форме в виде общей конъюнкции терминальных двух- или трехместных предикатов, образованных отношениями языка. Факты представляются константными предикатами. Пользовательские правила также хранятся в общей концептуальной памяти системы. Устройство и механизмы работы концептуальной памяти представлены более подробно в [35]. В общих чертах, концептуальная память организована в виде сетевой базы данных, где единицей хранения является отношение языка, т.е. запись, в которой фиксируется тип отношения и значения аргументов. Поскольку в языке только несколько фиксированных типов отношений, то на каждый тип приходится огромное количество записей. Поэтому записи организованы в наборы по константам, являющимся значениями аргументных полей, а не по типу отношения. Это накладывает определенные ограничения на поиск в концептуальной памяти, т.е. возникает понятие вычислимого предиката, которое будет рассмотрено далее. Обработка накопленной информации по заданным правилам инициализируется запросами к концептуальной памяти.
Формальное сообщение, посылаемое в базу знаний системы, записывается последовательностью предложений формального языка. Предложение может содержать утверждение об отношениях между объектами концептуальной модели, иметь форму правила, устанавливающего зависимости между отношениями, либо представлять собой запрос к базе знаний. Предложения отделяются одно от другого знаком V, что обозначает операцию конъюнкции. Предложение языка, имеющее форму утверждения, может быть представлено в канонической форме в виде общей конъюнкции терминальных предикатов отношений. В правилах языка может присутствовать дизъюнкция и конъюнкция предикатов. Будем использовать V для обозначения операции дизъюнкции.
В языке допускается определение следующих видов объектов: — понятия (классы), — экземпляры понятий, — переменные, — отношения (бинарные, трехместные и четырехместные), — числа. Вид объекта явно указывается в его обозначении. Имена классов записываются прописными буквами, а имена экземпляров — строчными. Будем обозначать Class множество всех константных классов, a Obj — множество всех константных экземпляров базы знаний. Таким образом, Class u Obj представляет собой множество всех констант концептуальной памяти. Для обозначения переменных мы зарезервируем буквы X , х, Y, у, Z, z, и в случае необходимости будем индексировать эти буквы цифрами 1,..., 9. Переменные, обозначенные прописными буквами X, Y, Z, определены на множестве понятий Class, а переменные, обозначенные строчными буквами х, у, z— на множестве экземпляров Obj. Множество всех переменных обозначим Var, и будем использовать обозначение )с/ у или у для обозначения произвольной переменной из Var (т.е. переменной, определенной либо на Class, либо на Obj). Для обозначения предопределенных в языке отношений зарегистрированы символы: Y — для обозначения бинарного отношения конкретизации; \ У — для обозначения бинарного отношения "иметь атрибут"; \.У — для обозначения трехместного отношения "иметь атрибут со значением"; Л[. У —для автонимного обозначения подкласса. Помимо предопределенных отношений в языке существует возможность задавать произвольные бинарные отношения при помощи отношений типа "связка". Для обозначения связки используется имя класса, заключенное в кавычки. Таким образом, любой класс может выступать в качестве имени бинарного отношения, являясь при этом третьим аргументом отношения типа "связка". Это значит, что предикат для отношения типа "связка" является трехместным. Таким образом, в языке допустимо использование бинарных, трехместных или четырехместных отношений. Текущее состояние объектов концептуальной памяти описывается наборами предикатов. Аргументом предиката отношения является терм— константный класс из Class, константный экземпляр из Obj, либо переменная. Предикат отношения в общем виде можно представить: P(t\,..., t ), где Р — тип отношения, Ґ\, ...,tn — термы, п принимает значения от 2 до 4. Будем называть основным предикат, не содержащий переменных. В языке также введена операция " \ применимая к отношениям и имеющая смысл отрицания. Более подробно смысл этой операции будет рассмотрен в главе, посвященной семантической интерпретации отношений. Стандартное обозначение отрицания не используется, чтобы подчеркнуть, что данная операция не является отрицанием с точки зрения логики предикатов. Поэтому обозначение P(t\,..., t ) есть по сути обозначение нового отношения, отличного от отношения P(t\,..., t ). Связь между этими двумя отношениями будет определена при рассмотрении теоретико-множественной интерпретации отношений. Литерал есть предикат P(t\,..., t ) (положительный литерал), либо отрицание предиката -if(tj,..., t ) (отрицательный литерал). Основной литерал— это литерал, не содержащий переменных. В связи с Конъюнкция предикатов вычислима, если она: 1) содержит хотя бы один вычислимый предикат и 2) допускает такую последовательность вычисления предикатов, что при вычислении очередного предиката будут означены переменные, входящие в последующие предикаты, так, чтобы в результате все предикаты могли быть вычислены. Определим теперь синтаксис пользовательских правил и запросов. Для записи пользовательского правила используется конструкция: Ри ... ;Pn —(Qi;... ;QS) v ... v(Ki;... Л), (і) где следствие представляет собой вычислимую конъюнкцию предикатов, а посылка— дизъюнкцию вычислимых конъюнкций предикатов.
Эрбрановская интерпретация конструкций языка
Так, первый аргумент отношения конкретизации класса экземпляром определен на множестве Class, а второй— на Obj, т.е. предикат этого отношения есть отображение ClassxObj - {"ложь", "истина"}.
Как мы видели, при изменении области определения аргумента с Obj на Class мы задаем уже неэлементарное отношение конкретизации между классами. При этом соблюдается общее Правило 1: если на месте аргумента элементарного отношения, определенного на Obj, записан класс, то это означает, что задано неэлементарное отношение, и истинность этого неэлементарного отношения эквивалентна выполнению соответствующего элементарного отношения для всех (либо некоторых) экземпляров указанного класса. Указать, выполняется ли соответствующее отношение для всех или некоторых экземпляров класса, можно при помощи служебных слов EACH либо SOME. При их отсутствии действуют принятые в языке умолчания. Далее зададим область определения всех элементарных отношений языка. При этом будем иметь ввиду вышеприведенное Правило 1, из которого следует, что каждый тип отношения может употребляться не только с аргументами из указанной области определения. Как уже было отмечено, элементарное отношение конкретизации есть частный случай бинарного отношения, задаваемого двухместным предикатом: Class х Obj - {"ложь", "истина"}. Элементарные бинарные отношения с указанной областью определения отнесем к типу COBin. Помимо них, в языке могут быть заданы элементарные бинарные отношения типов OCBin и OOBin: К є COBin: Class х Obj - {"ложь", "истина"}, Я є OCBin: Obj х Class - {"ложь", "истина"}, Я є OOBin: Obj x Obj - {"ложь", "истина"}. Дадим теперь интерпретацию элементарных бинарных отношений всех трех типов: 1(К) с UNIV х UNIV, где К є OOBin, \{К) с 2UNIV х UNIV, где Я є COBin, І(Я) с UNIV х 2UNIV, где К є OCBin. Семантика отношений. Рассмотрим теперь все типы отношений языка и определим их денотативную семантику. Мы уже рассматривали интерпретацию отношения конкретизации, однако, оно является бинарным отношением из COBin, и поэтому может быть интерпретировано также и следующим образом. Для произвольных класса А, экземпляра b и К из COBin: 1( А К Ъ) = 1 тогда и только тогда, когда (1(A), 1(b) )єІ(Я), 1( А К Ъ) = 1 тогда и только тогда, когда (1(A), 1(b) )І(Я), а следовательно, 1(А:Ь)=1 = (1(A), 1(b)) є 1(:), I( A:b)=l о(1(A), 1(b)) ft 1(:), что вполне согласуется с вышеприведенной интерпретацией 1(:). Кроме того, согласно вышеприведенному Правилу 1, для К из COBin допустимо употребление класса в качестве второго аргумента. При этом для произвольного класса В запись А К EACH В будет означать: 1(АКЕАСНВ) = 1 = (VxeUNIV) [х є 1(B) - (1(A), х) є I(ft); (1(A), x) є І(Я) - xg 1(B)]. Это также согласуется с приведенной ранее интерпретацией неэлементарного отношения конкретизации, и, следовательно, запись А:В по умолчанию означает, что перед В опущено служебное слово EACH. Объект-класс представляет в концептуальной памяти множество элементов, имеющих общие атрибуты. Записью а(В) мы утверждаем факт наличия атрибута В у экземпляра а, т.е., класс В выражает некоторое свойство данного экземпляра. Назначение А(В) классу А атрибута В означает, что все экземпляры класса А имеют этот атрибут, иными словами, класс В обозначает некоторое свойство, общее для всех экземпляров класса А. В качестве атрибутов могут указываться лишь классы. Из этого неформального определения видно, что элементарное отношение "атрибут" представляет собой отношение из OCBin. Для произвольных класса В, экземпляра а и Я из OCBin: 1( а К В ) = 1 тогда и только тогда, когда (1(a), 1(B) )єІ(К), 1( а К В ) = 1 тогда и только тогда, когда (1(a), 1(B) )І(К). Если же мы употребляем класс в качестве первого аргумента, то, согласно Правилу 1, для произвольного класса А запись EACH А К В будет означать: I(EACHAftB)=l« (VxeUNIV) [х є 1(A) - (х, 1(B)) є І(Я); (х, 1(B)) є І(Я) - хй 1(A)]. Тогда интерпретация элементарного отношения "атрибут": где () используется для символьного обозначения отношения "атрибут".
Алгоритм доказательства запроса к базе знаний без учета семантики отношений
В данной главе была определена теоретико-множественная интерпретация синтаксических конструкций формального языка. В связи с особенностями определения отношений рассматриваемого языка, было определено 3 типа интерпретации бинарных отношений: OOBin, OCBin и COBin.. Классы могут быть аргументами любого типа бинарных отношений, но в зависимости от типа, данное отношение либо устанавливается только с самим классом, либо распространяется на все элементы данного класса. Формальный язык также содержит трехместные отношения, которые были интерпретированы как комбинации отношений типов OCBin и COBin. Была разработана интерпретация отношений указанных типов в общем виде, что позволит в дальнейшем вводить в язык новые отношения данных типов, не определяя их интерпретацию заново.
Был определен смысл операции "отрицания" : все виды "отрицаний" отношений языка могут быть сведены к "отрицанию" элементарных отношений и проинтерпретированы через отношение НЕ принадлежности элементов множеству.
Были рассмотрены основные отношения формального языка и на основании определенной для них теоретико-множественной интерпретации была разработана их денотативная семантика. В связи с особенностями интерпретации и наличием в языке трехместных отношений, был получен существенный отличительный результат. В отличие от денотативной семантики отношений других языков концептуального моделирования, разработанная денотативная семантика определяет неэлементарные отношения не через отношение принадлежности элементов классу, а через элементарные отношения.
В главе 1 были определены основные понятия и отношения формального языка. В базе знаний реализовано совместное хранение фактов и правил, записанных с использованием отношений формального языка. Факты и пользовательские правила, т.е. все, что пользователь желает зафиксировать в базе знаний, хранятся в концептуальной памяти системы. Единицей хранения является терминал— структура, в которой хранится вся информация об одном предикате отношения: тип отношения, значения его аргументов, а также вхождение. Вхождение для предиката отношения есть его место в общей базе знаний и имеет значение, например, когда данный предикат входит в какое-либо правило. В этом случае в поле вхождения помечается правило - владелец отношения.
Ключами поиска при извлечении информации из концептуальной памяти являются константы, входящие в отношения. Это означает, что при поиске в концептуальной памяти могут быть найдены только вычислимые терминалы. Этим обусловлено требование вычислимости конъюнкций, входящих в посылку и следствие пользовательских правил.
Как уже было сказано, база знаний, сформированная при помощи конструкций языка, представляет собой совокупность предложений языка, т.е. фактов и пользовательских правил. Учитывая введенные в главе 1 определения факта и основного предиката, а также установленную эквивалентность пользовательского правила конъюнкции хорновских правил, можем рассматривать базу знаний как конъюнкцию основных предикатов и хорновских правил. Эрбрановский универсум HU есть множество всех константных термов базы знаний, т.е. в нашем случае совпадает с множеством всех констант: HU = Class u Obj. Необходимо отметить, что в отличие от эрбрановского базиса обычных дедуктивных систем, HU содержит константы двух типов: Class и Obj. Эрбрановским базисом НВ базы знаний будем называть множество всех основных предикатов, построенных при помощи имен предикатов концептуальной памяти. Отметим, что множество основных предикатов также состоит из предикатов двух типов: предикаты элементарных и неэлементарных отношений. Мы помним, что предикатам неэлементарных отношений могут быть сопоставлены совокупности правил на основании их денотативной семантики, однако, при рассмотрении эрбрановской интерпретации мы не будем учитывать этот факт, а будем одинаково рассматривать предикаты элементарных и неэлементарных отношений. Эрбрановской интерпретацией назовем произвольное множество основных предикатов из эрбрановского базиса: HI z НВ. Подстановка 9 есть произвольное отображение конечного набора переменных в термы 0: Var -» Class u Obj u Var. Основная подстановка — это подстановка, в которой используются только константные термы, т.е. 9: Var - Class u Obj. Пусть Р(ХЬ ...,Хп)— предикат, тогда QP = Р(0ХЬ ..., 9Х„) = P(t\,..., i). То есть, QP получается заменой каждого вхождения переменной в Р на соответствующий терм. Две формулы А и В унифицируются, если существует подстановка 0 такая, что QA = 9"8. При этом подстановка 9 называется унификатором выражений А и Ъ. Унификатор 9 называют наиболее общим для А и 6, если для любого другого унификатора 9i этих формул найдется подстановка 9г, такая, что 0i = 92 9. Рассмотрим некоторую эрбрановскую интерпретацию HI с НВ и определим относительно нее значения истинности для конструкций формального языка.
Предварительные определения и обоснование выводимости
Заметим, что теорема о полноте SLD-резолюции лишь утверждает, что с помощью SLD-резолюции можно сгенерировать все контрпримеры, соответствующие всем основным реализациям цели, следующим из S\JT Однако, она не определяет стратегию вычисления, позволяющую получить все контрпримеры цели. Поэтому окончательно полнота вывода, построенного на основе метода SLD-резолюции, определяется стратегией вычисления, используемой для получения всех контрпримеров. Мы будем использовать в качестве стратегии вычисления нисходящий вывод, при котором генерируются все возможные опровержения цели в соответствии с фиксированными функциями выбора У и у при использовании рекурсии и бэктрекинга. Это означает, что поиск потенциальных правил и фактов для получения резольвенты ведется сначала в глубину. Возврат происходит после того, как получено очередное решение, т.е. выведен пустой дизъюнкт, либо при отсутствии дизъюнктов, способных произвести резольвенту. При таком методе перебора дизъюнктов возможно зацикливание при вхождении в бесконечную рекурсию. Возникает проблема остановки, для решения которой нужно либо исследовать динамическое поведение программы, либо искусственно ограничивать глубину рекурсии какой-либо заранее заданной величиной. На данный момент в реализованном алгоритме принято решение об искусственном ограничении глубины рекурсии, что ведет к потере полноты. Обозначим описанный выше алгоритм нисходящего вывода на основе SLD-резолюции Query((?). Поскольку к началу вычислений набор дизъюнктов концептуальной памяти 5ир фиксирован, будем считать, что на входе алгоритма всегда находится запрос к базе знаний в виде вычислимой конъюнкции предикатов. Результатом работы алгоритма является набор подстановок {0i,...,0k} — значения переменных запроса Q, при которых истинность формулы запроса выводится из истинности фактов и пользовательских правил в концептуальной памяти; набор 9 пуст при отсутствии таких значений. Согласно теореме 1, при фиксированном множестве дизъюнктов концептуальной памяти Sup и цели Q вида -іР(ї,..., tQ, если результатом работы Query((?) является набор подстановок {0i,...,0k}, т.е. Svf -Queiy ТО,..., ї)Єь , Svf -Query ТО,.... tb)9k, то SuFhTO,..., , ..., 5uF= ТО, .,№ Т.е. утверждается корректность вывода при помощи алгоритма Query((i). Специфика реализации алгоритма Необходимо отметить, что на данный момент устройство концептуальной памяти накладывает еще одно ограничение, ведущее к потере полноты. Это ограничение вытекает из ограничения вычислимости предикатов. Как было сказано в главе 1, ограничение вычислимости естественным образом вытекает из несоизмеримости возможного количества констант языка и количества предопределенных в языке типов отношений. В связи с этим, невозможно искать нужный предикат в базе, перебирая все предикаты заданного типа (поскольку их количество может составлять десятки, а то и сотни тысяч). Поэтому ключом для поиска предиката в базе являются константы, входящие в отношение. Отсюда вытекает ограничение: при непосредственном поиске предиката в концептуальной памяти могут быть найдены только предикаты, непосредственно содержащие те константы, которые входили в предикат, являющийся запросом на поиск. Отсюда вытекает ограничение совместимости предикатов правила и цели.
Выше было введено условие применимости правила % при вычислении целевого предиката Р: наличие в конъюнкции следствия К предиката Q, унифицируемого с Р. Теперь необходимо уточнить это условие, а именно: правило К применяется для получения резольвенты с целевым предикатом Р, если конъюнкция следствия К содержит вычислимый предикат Q, совместимый с Р. Определение. Два предиката, Q и Р, совместимы, если: а) существует унифицирующая подстановка 0: Q9 = Р0; б) хотя бы одно аргументное место этих предикатов замещено общей константой. Пример. Предикаты А:В и А:Х являются совместимыми, а предикаты Х:Ь и А:у не являются совместимыми, хотя и являются унифицируемыми. Как видим, ограничение совместимости предикатов правила и цели приводит к тому, что в процессе вывода будут перебраны не все правила, производящие резольвенту с предикатами цели. Это может привести к потере некоторых решений, а значит, к потере полноты вывода. Можем утверждать, однако, что количество решений, потерянных из-за ограничения совместимости предикатов, будет невелико. Действительно, количество предопределенных в языке отношений ограничено и невелико, тогда как количество констант может быть огромно. Именно константы являются основной значимой единицей отношения, определяющей его смысл. Следовательно, невелика вероятность того, что два отношения, связанные только типом отношения и не имеющие общих констант, могут быть связаны по смыслу. Рассмотрим особенности практической реализации вызова правил, обусловленные ограничением совместимости предикатов. Для непосредственного поиска предиката в концептуальной памяти существует две функции, одна из которых ищет предикаты, соответствующие искомому предикату запроса, среди фактов, записанных в концептуальной памяти, а другая ищет их в следствиях всех правил, записанных в концептуальной памяти. Обозначим функцию непосредственного поиска предиката в следствиях правил концептуальной памяти GetRule(f). Предположим теперь, что функцией выбора У в текущей цели определен предикат V и нам необходимо найти в концептуальной памяти пользовательское правило, следствие которого содержит предикат, совместимый с V. Если предикат Р содержит только одну константу, то Get_Rule(P) найдет все предикаты, совместимые с V. Если же предикат V содержит более одной константы, то Get_Rule(P) найдет лишь те предикаты, которые содержат все константы Р на соответствующих местах. Поэтому по предикату V подготавливается несколько запросов для Get_Rule(f): каждый предикат V\ содержит одну из констант V на соответствующем месте, остальные же аргументные места заменены переменными. Затем поочередно выполняются запросы Ge1_Rule(f i) для всех і и совокупность предикатов, найденных в результате всех, запросов Get_Rule(Pi), представляет собой совокупность всех совместимых с Р предикатов, содержащихся в следствиях правил концептуальной памяти.
