Оглавление
Введение
1) Модели представления знаний 3
2) Практические предпосылки исследования.
Постановка задачи. Краткое содержание работы 16
1. Формальный язык. Денотативная семантика отношений языка
1) Основные определения 22
2) Семантическая интерпретация. Денотативная семантика отношений 27
2. Дедуктивная модель предметной области. Реализация логического вывода в рамках дедуктивной модели
1) Эрбрановская интерпретация конструкций языка 51
2) Алгоритм доказательства запроса к базе знаний без учета семантики отношений 58
3. Интегрированная модель предметной области
1) Семантическая память 79
2) Предварительные определения и обоснование выводимости 87
3) Общий алгоритм доказательства запроса к базе знаний 110 Выводы
2
Введение
Модели представления знаний
Среди различных моделей, лежащих в основе современных систем представления знаний, можно выделить два класса, получившие наиболее широкое распространение: класс дедуктивных и класс концептуальных моделей.
Системы, основанные на дедуктивных моделях, обычно применяются для представления знаний дедуктивной природы, когда связи между утверждениями удобно выражать каузальными конструкциями “если-то”.
В тех же случаях, когда система знаний о предметной области сводится к иерархии понятий, определению их свойств и наследованию свойств в рамках иерархии, удобно строить ее на основе концептуальных моделей данных.
На практике описание предметной области всегда содержит и иерархически связанные понятия и каузальные связи между утверждениями о понятиях.
В данной работе исследуется возможность интеграции методов этих двух моделей в общей системе представления знаний.
В основе дедуктивных моделей лежит эрбрановская интерпретация данных. В формализмах такого рода основными элементами языка являются термы (константы, переменные, функции), служащие для обозначения различных объектов, и п-местные предикаты (имеющие термы в качестве аргументов), предназначенные для фиксации отношений между объектами. В эрбрановской интерпретации любая константа представляет собой лишь цепочку символов, а интерпретация предиката отношения задается множеством значений аргументов, на которых этот предикат истинен. Истинность предиката в базе знаний задается либо фактом — явным указанием константных термов, на которых предикат истинен, либо вычисляется при помощи заданных пользователем правил (логической программы). Таким образом, множество значений аргументов, на которых
3
предикат истинен, определяется результатом работы логической программы. Это означает, что интерпретация данных отделена от самих данных и перенесена на работающие с ними логические программы. Сами данные без соответствующих программ представляют собой не более чем набор символов, которому различные программы могут придать различную интерпретацию. Таким образом, представление знаний в системах на основе дедуктивных моделей определяется способом его обработки.
В этих условиях произвол в выборе набора отношений, связывающих данные, определения их местности и назначения каждого из мест создает серьезные технологические трудности при формировании систем знаний достаточно большого объема. В результате, разработка системы представления знаний на основе дедуктивных моделей сопровождается разработкой внесистемных соглашений о смысле занесенных в базу отношений.
Другой технологический недостаток эрбрановской интерпретации, также обусловленный ее общностью: построение описания той или иной предметной области сопряжено с необходимостью каждый раз заново описывать универсальные отношения, свойственные окружающему миру. Иными словами, дедуктивной системе изначально свойственна низкая степень автоматизации процесса построения описания.
Классическими примерами языков, в основу определения которых положена дедуктивная модель, являются язык логического программирования Пролог [40, 39, 44] и логический язык
программирования баз данных Дейталог [8, 9, 53].
Важное преимущество Пролога — мощный аппарат оперирования с данными (списки, структуры, арифметические операции), обеспечивающий вычислительную полноту языка. Аппарат оформлен в виде встроенных функций, представляющих собой надстройку над инструментом логического вывода. В рамках языка интерпретация данных предметной
4
области осуществляется в терминах исполнения встроенных функций и эрбрановской интерпретации результатов этого исполнения.
Серьезным недостатком Пролога является зависимость результата выполнения программы от порядка записи клауз. Желательно, чтобы формализм представления знаний обладал автоматическим инструментом вывода, дающим одинаковые результаты при обработке семантически эквивалентных конструкций.
Чтобы удовлетворить этому требованию, были созданы различные варианты языков логического программирования, где логика предикатов первого порядка ограничивалась неким ее подклассом (в ущерб вычислительной полноте). Дейталог, будучи примером такого языка, является первым специализированным логическим языком программирования баз данных [41, с. 12]. Создатели языка [53] ставили цслыо совместить возможности языка логического программирования с возможностью хранения фактов в больших базах данных. В связи с этим, накладываются ограничения на язык логики предикатов первого порядка: в языке отсутствуют функциональные выражения, т.е. возможность конструирования сложных объектов — в качестве терма может выступать только константа или переменная. В отличие от прологовского нисходящего вывода, основанного на методе резолюций, в Дейталоге используется восходящий метод вывода. За счет такого метода вывода решается проблема перестановочности клауз, т.е. в Дейталоге результат работы логической программы не зависит от порядка записи клауз.
Множество фактов в Дейталоге образует экстенсиональную базу данных, а правила— интенсиональную базу данных, вместе эти базы образуют логическую базу данных. Единицей хранения в экстенсиональной Дейталоговской базе данных является кортеж значений аргументов предиката.
Заметим, что, как в Прологе, так и в Дейталоге нет явно вводимого отрицания, т.е. невыводимость истинности предиката в данной базе знаний приравнивается к ложности этого предиката.
Представляется, что недостаточная выразительность и процедурность описаний, выстраиваемых на основе дедуктивных моделей, явилась одной из побудительных причин создания специальных языков, нацеленных на описание данных [51, с.4]. В основу таких языков положены
концептуальные модели данных, ориентированные, в первую очередь, на представление сложных иерархических структур.
В настоящее время одной из областей применения языков концептуального моделирования являются системы обработки текстов на естественном языке, являющиеся составной частью систем для представления знаний. Системы обработки текстов на естественном языке (NLP — natural language processing) нацелены на извлечение семантической информации, содержащейся в тексте, на основе общеязыковых представлений. Необходимые лексические сведения в такой системе обеспечивает словарь с достаточно формализованной словарной статьей. В настоящее время большинство исследователей в данной области признают необходимость построения специального концептуального словаря (вычислительной онтологии), где данные словарной статьи представляются при помощи некоторого формального языка [49, 48, 20, 21, 26, 15]. Формальный язык используется в системе NLP двояким образом: во-первых — для представления словарной статьи, во-вторых — для окончательного представления извлеченной из текста информации.
Пример описания из семантического словаря В.А. Тузова:
ВЫПУСК $1202(Тв, Род, Из, наВинЩля)— описание базового понятия в классе, имеет четыре аргумента, которые должны быть заполнены соответствующими актантами: кем осуществляется выпуск, кого (что) выпускают, откуда и для чего.
ВЫПУСКНИК Орег01_о2(ШКОЛА$1119110, ВЫПУСК$1202(Sing_o~%2)) “Выпускник - это тот, кто является вторым актантом действующего (или действовавшего когда-то) процесса выпуска из класса $1202, осуществляемого некоторой школой из класса $1119110“.
Здесь ВЫПУСК$1202— далее не трактуемое базовое понятие класса, т.е. концепт, а понятие ВЫПУСКНИК определяется через концепты ВЫПУСК$1202и
б
ШКОЛА$11191Ю. Цифры обозначают положение класса в общей иерархии объектов.
Основная информация, представляемая в семантическом словаре — это иерархические взаимосвязи и отношения между отдельными концептами. Используя концептуальный словарь, система NLP пытается сформировать представление смысла текста, выраженное на соответствующем формальном языке. При помощи этого же формального языка эксперт в предметной области может пополнить данное представление смысла новыми сведениями, которые он желает зафиксировать в системе представления знаний.
Основными элементами языков концептуального моделирования являются классы объектов и бинарные отношения. Поскольку любой п-арный предикат может быть представлен совокупностью бинарных предикатов [43, с. 146], то эти элементы языка позволяют выразить практически любые отношения между объектами.
Семантика классов и бинарных отношений задается при помощи интерпретации I относительно некоторого множества D1 (домен интерпретации). Произвольному объекту а сопоставляется элемент а1 е D1, произвольному классу А — некое подмножество А1 с D1, а произвольному бинарному отношению R— подмножество R^cD^D1. [1, с.6] Далее эта интерпретация распространяется на все операции, определенные для классов и бинарных отношений. Из такой интерпретации вытекает, что мы можем определить некоторое бинарное отношение между классами объектов, или задать некоторое свойство класса, и это отношение, или это свойство будет автоматически распространяться на все элементы этих классов.
Таким образом, интерпретация данных в языках концептуального моделирования связывается с самими данными. В этом случае данные приобретают семантическую значимость, одновременно выражая и факты, и способ их интерпретации [52, с. 18]. Если в прологовской базе знаний взаимосвязи между различными данными представлены отдельно от самих
7
данных, т.е. при помощи логических программ, то в концептуальной модели языковые средства, использованные для записи самих данных, определяют виды связей между данными.
В языках концептуального моделирования также осуществляется логический вывод. Если в языках логического программирования вывод осуществляется на основе заданных пользователем правил, то в концептуальных моделях для вывода используются семантические правила, автоматически формируемые на основе семантики данных в базе знаний. При этом вычислительной полноте языков логического программирования противопоставляется логическая разрешимость, т.е. возможность получения определенного (ДА или НЕТ) ответа на запрос.
В настоящее время выделяются два вида языков, в основе которых лежат концептуальные модели данных: концептуальные графы и языки, обычно обозначаемые как “языки типа KL-ONE“. “K.L-ONE” — название первой системы такого типа, реализованной Бречманом (Brachmann) и Шмульцем (Schmölze) [4].
Концептуальные графы [30, 43, 19, 27, 28, 22, 11, 2] и построенные на их основе семантические сети — наиболее полно разработанный на сегодняшний день формализм для наглядного (графического) представления знаний. Концептуальный граф содержит два типа узлов: узлы, представляющие объекты (или классы объектов), и узлы, представляющие отношения между объектами. На концептуальном графе выделяются отношения вида IS-А, которым устанавливается принадлежность объекта некоторому типу (классу) или вложение одного типа (класса) в другой. Относительно отношений вида IS-А определено наследование свойств объектов (их отношений с другими объектами) от типа к подтипу и к объекту, конкретизирующему данный тип. Это означает, что денотативная семантика остальных отношений задана относительно отношений вида IS-А. Наряду с отношениями вида IS-A, вводится отношение между множеством и элементом множества, относительно которого не определено наследование свойств. На
8
концептуальных графах также могут быть введены кванторы существования и всеобщности, а также явное отрицание, что отличает концептуальные модели от Пролога и Дейталога. Например, фраза: "каждый слон — серый", может быть изображена концептуальным графом, который приведем здесь в текстовой форме: [ELEPHANT:V]->(COLR)->[COLOR:grey]
Здесь в квадратных скобках изображаются концепты, а в круглых — отношения. На графе они заключаются соответственно в прямоугольники и окружности. Двоеточием изображено отношение принадлежности объекта некоторому типу: grey— это конкретный объект, тогда как COLOR и ELEPHANT определяют тип.
Концептуальные графы предоставляют широкие изобразительные возможности, позволяющие непосредственно обобщать концептуальные графы на модальные системы и другие формализмы, трудно представимые логикой первого порядка [43]. Однако, широкие выразительные возможности концептуальных графов, имеют и свою обратную сторону. Задача выстраивания иерархии классов в общем случае сводится к задаче: определить, является ли один концептуальный граф частью другого, а последнее не всегда разрешимо.
Ограничения, накладываемые на изобразительные возможности в языках типа KL-ONE Г1. 31, 7, 23, 24, 25, 12], делают задачу выстраивания иерархии разрешимой.
После создания первой системы KL-ONE было создано большое количество систем, реализующих сходные идеи. Был разработан язык ALC, введенный в [29], который принято рассматривать как основу языков типа KL-ONE, так или иначе дополняемую в конкретных системах. [31]
Основными объектами языков типа KL-ONE являются концепты и роли. Концепты представляются унарными предикатами, а роли — бинарными. Имеется также достаточно ограниченный набор конструктов для формирования новых концептов и ролей.[1, с.5] В языке ALC для
9
определения нового концепта используются только конструкты NOT, AND, OR, а также кванторы существования и всеобщности.
Описание предметной области в языке ALC задается набором утверждений вида:
концепт = условие принадлежности элементов концепту.
Например, лягушку можно определить как животное зеленого цвета: Лягушка = (and Животное (all цвет Зеленый)).
Это определение системой автоматически транслируется в формулу логики предикатов:
(Vx) (Лягушка(х) <=> Животное(х) л (\?У)(цвет(х,у) •> Зеленый(у))).
В дальнейшем эта формула используется для осуществления логического вывода.
Особенностью языков типа KL-ONE является разделение знаний на терминологическую часть (“Т-box”), содержащую определения концептов и ролей, и базу фактов (“А-box”). Каждому определению концепта или роли в “Т-box” может быть автоматически сопоставлено правило на языке логики предикатов, в зависимости от конструктов, использованных в определении.
Семантическая интерпретация концептов и ролей фиксируется однократно при их определении в “Т-box” и связывается с самими данными. В этом случае данные приобретают семантическую значимость, одновременно выражая и факты, и способ их интерпретации.
Для логического вывода используются правила, полученные при трансляции определений концептов и ролей на язык логики предикатов. Предикаты, употребляемые в полученных правилах, выражают конкретизацию концепта экземпляром или роли парой экземпляров. Для систем типа KL-ONE разработаны различные методы логического вывода с использованием этих правил. Поскольку набор используемых в определениях конструктов ограничен, правила трансляции определений в формулы логики предикатов могут быть однократно заданы в общем виде.
10
Используя определения концептов, система KL-ONE может построить классификатор, автоматически определяющий место каждого из концептов в иерархии. Так, например, если в “Т-box” присутствуют следующие определения концептов:
Выс_человек = (and Человек (some рост Высокий))
Выс_толст_человек = (and Человек (some рост Высокий) (some вес Большой)),
то классификатор автоматически поместит Выс_толст_человек в иерархии ниже Выс_человек, сравнив роли, использованные в определении этих концептов. Заметим, что такой классификатор для концептуальных графов отсутствует [3, с.85], и в аналогичной иерархии для концептуальных графов оба концепта Выс_человек и Выс_толст_человек останутся подтипами концепта Человек.
"А-box" в KL-ONE состоит из фактов, фиксирующих истинность или ложность унарных и бинарных предикатов при определенных значениях аргументов. На основе рассмотренной выше семантической интерпретации, это означает факты принадлежности (или НЕ принадлежности, ввиду возможности явно указать этот факт) объектов классам или пар объектов бинарным отношениям. Таким образом, база фактов системы состоит из фактов принадлежности объектов классам. Правила, получаемые системой при трансляции определений из “Т-Ьох”, позволяют вывести новые факты такого же вида. При таком подходе база фактов допускает хранение в виде таблицы, где названия столбцов есть имена классов и бинарных отношений, а в строках располагаются пометки о принадлежности (или НЕ принадлежности) этим классам или ролям объектов или пар объектов. Такая система хранения приводит к возможности использовать для логического вывода какую-либо вариацию метода семантических таблиц, введенного Э. Бегом. [34] В частности, в системах CARIN и AL-LOG, представляющих собой попытку комбинировать язык типа KL-ONE с применением хорновских правил, была использована техника систем с ограничениями (constraint systems), представляющая собой вариацию метода семантических таблиц. [16, 14]
и
Серьезным продвижением в развитии концепции языков типа KL-ONE, явилась система CBR (Classes and Binary Relations), представленная Г.С. Плесневичем в [46, 47]. Предлагается совершенно иная структура входного языка: описание предметной области задается в виде
предложений, содержащих утверждения об отношениях между классами, а также между классами и экземплярами. Такой язык обладает большей выразительностью по сравнению с языком систем типа KL-ONE, предназначенным в основном, для описания типов данных. Например, утверждение “любое животное питается либо растениями, либо животными, которые меньше его и питаются растениями” на языке CBR записывается в виде:
ЕАСН Животное X (Ест ЕАСН Растение OR
Ест ЕАСН Животное ТНАТ (Меньше X AND Ест SOME Растение))
Для описания предметной области определено его каноническое представление в виде конъюнкции терминальных элементов, где терминальный элемент— это выражение, содержащее единственное отношение или связку (ТНАТ, OR, AND). Имеется ограниченный перечень конструкций терминальных элементов. Утверждения языка строятся при помощи связок AND, OR, NOT, а также префиксов SOME и ЕАСН в качестве кванторов существования и всеобщности.
Например, можно записать утверждение о том, что все гусеницы едят некоторые растения:
ЕАСН Гусеница Ест SOME Растение.
Совокупность утверждений языка явным образом описывает семантическую сеть, вершинами которой являются классы и экземпляры, а дугами — имена бинарных отношений.
Новые классы вводятся без определения, хотя, благодаря использованию предикатов, возможность определения классов через другие классы также присутствует. При помощи связки TI-IAT можно определить новый класс, состоящий из элементов другого класса, удовлетворяющих условию, выраженному предикатом.
12
Например, можно определить класс животных, которые едят некоторые растения:
Травоядное == Животное THAT Ест SOME Растение.
Здесь Ест— бинарное отношение, Гусеница, Растение, Животное, Травоядное — классы, Ест SOME Растение — предикат.
База знаний в CBR, делится на концептуальную схему, в которую включаются все предложения общего характера и базу фактов. База фактов, как и “А-box” в системах типа KL-ONE, включает в себя утверждения о принадлежности элементов классам или пар элементов бинарным отношениям.
Для всех конструкций языка определена денотативная семантика на основании теоретико-множественной интерпретации классов и отношений.
Существенной особенностью системы CBR является метод преобразования концептуальной схемы в систему продукций на основании введенной денотативной семантики отношений. Концептуальная схема на этапе трансляции преобразуется в систему продукций в соответствии с определенными правилами трансляции. Продукции представляют собой правила для получения новых фактов.
Так, например, факт принадлежности подкласса классу A ISA В транслируется в систему продукций:
XINA =>Х IN В;
X IN -В =>Х IN -А,
(X — переменная, IN отражает принадлежность элемента классу) а факту А-7 ISA В соответствует продукция:
=> g:A IN A; g:A IN-В,
где g:А — сколемовская константа из класса А, а -Б есть дополнение класса В.
Полученная при трансляции концептуальной схемы система продукций применяется для осуществления логического вывода, основанного на методе семантических таблиц Бета. Как уже упоминалось, база фактов в CBR представляет собой таблицу с именами классов и
13
бинарных отношений в качестве названий столбцов. Строка в таблице отражает состояние базы фактов, т.е. в нее заносятся элементы, принадлежащие или не принадлежащие соответствующим классам или бинарным отношениям. К базе фактов добавляется отрицание запроса и также заносится в таблицу. Последовательное применение системы продукций к состояниям базы фактов приводит к появлению новых элементов в таблице. Появление в одном столбце пометки о принадлежности и НЕ принадлежности ему одного и того же элемента позволяет сделать вывод о противоречивости базы фактов (т.е. подтверждает запрос). Можно заметить, что в СВЯ применяется восходящий метод вывода, аналогично восходящему выводу в Дейталоге.
Отметим, что в системе СВЯ явным образом вводится отрицание, причем теоретико-множественная интерпретация позволяет свести возможные формы отрицания в утверждениях языка к отрицанию элементарного факта принадлежности элемента классу (или пары элементов бинарному отношению). Это сведение осуществляется в процессе трансляции концептуальной схемы в систему продукций. (См. пример трансляции Л 18А В.)
Сопоставляя особенности и области применения дедуктивных и концептуальных моделей в системах представления знаний, мы можем видеть, что эти модели предназначены для представления знаний различной природы и не конкурируют, а скорее, дополняют одна другую. Удобно описывать свойства данной предметной области семантической сетью понятий и отношений и столь же удобно каузальные зависимости между отдельными фрагментами сети задавать средствами дедуктивной модели. В связи с этим большой интерес представляет интеграция методов обеих моделей в рамках единой системы представления знаний. Исследованию возможных подходов к решению этой задачи и посвящена данная работа.
14
- Київ+380960830922