Преимущества дескриптивной логики при обработке знаний

Тип работы:
Реферат
Предмет:
Информатика


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 004. 89
ПРЕИМУЩЕСТВА ДЕСКРИПТИВНОЙ ЛОГИКИ ПРИ ОБРАБОТКЕ ЗНАНИЙ
А. Р. Вахитов, В.Б. Новосельцев
Томский политехнический университет E-mail: var-sasha@tpu. ru
Обсуждаются области применения дескриптивных логик, базовые термины, а также основные их преимущества по сравнению с классическими исчислениями. Особое внимание уделяется возможности применения дескриптивной логики при обработке знаний, показаны примеры использования дескриптивной логики в этой области. Рассматриваются принципы построения логического вывода для обсуждаемой теории.
Ключевые слова:
Дескриптивная логика, обработка знаний, искусственный интеллект.
В последнее время в области инженерии знаний особой популярностью стал пользоваться формализм представления знаний, называемый дескриптивной логикой (ДЛ). Этот формализм широко применяется при построении интеллектуальных систем, основанных на знаниях, — для Интернет-приложений, в медицине, при решении задач конфигурирования оборудования, для построения электронных библиотек и т. д. Большинство таких систем относятся к классу экспертных, имитируя работу специалиста высокого уровня компетентности.
Как известно, одной из важнейших составляющих экспертных систем является механизм логического вывода, поэтому разработка эффективных алгоритмов и процедур вывода, а также связанных с ними методов представления знаний, привлекает особое внимание исследователей в области когнитивных технологий. Суть состоит в том, что размерности баз знаний практически полезных систем достаточно велики, и, если для вывода на таких объемах информации использовать неэффективные (переборные) алгоритмы, время получения требуемого от системы ответа может оказаться неприемлемо большим.
Исследования в области представления знаний обычно сосредотачивается на методах обеспечения описания высокого уровня, который может эффективно использоваться для создания интеллектуальных приложений. Под термином «интеллектуальный» подразумевается способность системы найти неявные следствия из явно представленных знаний, имитируя стиль рассуждений человека. Базовые подходы к представлению знаний были разработаны во второй половине прошлого столетия, когда эта область была на пике популярности, и разделились на два направления: логические формализмы и представления, основанные не на логике. Первые позиционировались как универсальный инструментарий для различных типов задач. В подобных системах знания представлялись специальными структурами данных (семантические сети, сети фреймов, нейроструктуры и т. д.) и дополнялись специальными, как правило, эвристическими процедурами для работы с ними. В последние годы в этой области стали весьма популярными дескриптивные логики.
Дескриптивные логики позволяют описывать конфигурацию сложных (многокомпонентных) взаимодействующих. В последнее время эта область, вследствие тесной связи с прикладными задачами, становится чрезвычайно популярной в исследованиях по представлению и обработке знаний. Так, для задач робототехники важно уметь по изображению некоторой сцены восстановить ее вербальное (формальное) описание, чтобы использовать его, например, для планирования действий робота. Обсуждаемые формализмы описывают знания о предметной области, предварительно фиксируя некоторые базовые ее понятия (терминологию), а затем используя эти понятия для точного описания свойств и связей соответствующих объектов [1].
Ключевой особенностью ДЛ, отличающей их от предшественников, таких как семантические сети и фреймы, является то, что это — именно логики, т. е. строгие теории с хорошо определенной семантикой. Другой их отличительной особенностью является упор на формальный вывод, как основной способ использования: машина вывода позволяет извлекать имплицитные знания из информации, которая явно содержится в базе системы. ДЛ поддерживают стратегии логического вывода, которые встречаются во многих вариантах интеллектуальных систем обработки информации, и давно используются людьми, для структурирования и понимания мира — классификация понятий и их представителей (экземпляров), типизация, иерархия, а также наследование свойств.
Базовыми терминами ДЛ являются концепты и роли. Концепт — это выражение, соединяющее в себе набор ранее определенных концептов и их свойств (описываемых ролями), которое строится с использованием одного из конструкторов дескриптивного языка, что позволяет моделировать более сложные объекты анализируемой предметной области. ДЛ предоставляют методы работы с такими сложными концептами, технику рассуждений об их свойствах и выводимости на них. ДЛ могут быть довольно успешно использована для построения объяснительной компоненты соответствующей экспертной системы.
Если попытаться определить место ДЛ в структуре классических логических исчислений, то просматривается некоторое противоречие. Дело в том, что в первоначальных исследованиях в области ДЛ считалось, что эти теории являются подмножеством логик первого порядка [2]. Однако в действительности ДЛ связаны с исчислением предикатов лишь синтаксически — в силу использования предикатных форм. С тех пор, как в ДЛ начали использоваться язык, включающий унарные и бинарные (ролевые) предикаты, стало ясно, что ДЛ близки к типизированным модальным языкам пропозиционального уровня, если рассматривать роли как реализацию отношения достижимости [3]. Исследования сложности выполнимости задач в модальной пропозициональной логике осуществлялись намного раньше того, как стала исследоваться проблема сложности вывода для ДЛ. Таким образом, в ДЛ оказалось возможным использование некоторых результатов в области сложности выполнимости задач модальных логик, в частности технику вывода и конструкции языка, которые ранее не использовались в ДЛ [4]. Таким образом, ДЛ можно отнести как логике исчисления высказываний, так и к логике исчислению предикатов.
На рисунке приведен пример использования ДЛ относительно предметной области, связанной с обработкой результатов НИРС в вузе. Для этой предметной области была построена модель данных, выполненная в методологии MS Access 2003.
На основе модели в системе было выделено множество базовых концептов включающих такие элементы как Студент, Преподаватель, Консультация, НИРС, РезультатНИРС и т. д. Кроме того, в качестве базовых терминов были определены такие
роли концептов, как Имеет, Обучается, Выполняет, Руководит и т. д. Наконец, на неформализованном языке были описаны отношения между концептами с помощью ролей: Студент ИМЕЕТ За-четнуюКнижку, Студент ВЫПОЛНЯЕТ НИРС, Преподаватель РУКОВОДИТ НИРС и т. д.
Далее в качестве конструктора дескриптивного языка используется синтаксис дескриптивной логики CLASSIC (CLASSification of Individuals and Concepts) [2].
В [2] представлен исчерпывающий набор не зависящих от конкретного приложения конструкторов, предложенный в обзоре. Семантика конструкторов определяется через понятие интерпретации. Интерпретация I состоит из домена Д и интерпретирующей функции (отображения) VI. Отображение V сопоставляет каждому концепту подмножество Д1 и каждой роли — бинарное отношение на Д1. Объекты отображаются в единственный элемент Д1.
Важнейшей особенностью дескриптивных логик, их визитной карточкой, является способность строить иерархии на концептах. Говорят, что концепт С является подклассом концепта D (C^D), если при любой интерпретации I, C tD'-. Аналогично, концепты C и D несвязны, если при любой интерпретации I, ClnD 1=0. И, наконец, С согласован, если существует хотя бы одна интерпретация I такая, что C '-^0.
Приведем пример типичного композиционного описания в синтаксисе логики CLASSIC:
(and
Консультация,
(at-least 7 takers),
(all takers Студент))
Рисунок. Реляционная модель данных
Смысл описания можно сформулировать так: «Консультация с не менее, чем семью слушателями, все из которых принадлежат классу Студент». ДЛ позволяют расширять набор конструкторов сверх стандартных (конъюнкции, отрицания, квантора всеобщности и т. д.), обеспечивая тем самым лаконичное описание предметной области.
Проиллюстрируем использование ДЛ в описании данных и запросов к ним на примере. Для этого опишем некоторое состояние системы в определенной ними базе знаний, связанной с НИРС. Необходимо ввести новый объект, например, НИРС1:
НИРСl: =create-ind ()
Информация о подобных объектах хранится в базе знаний двумя способами: указанием класса, к которому они принадлежат («НИРС1 есть экземпляр класса НИРС») и указанием их связей через роли («Объектом НИРС1 руководит Петров, и Иванов занимается объектом НИРС1»). Для этих целей используются операторы insert-in и fill-with, применяемые следующим образом
insert-in (НИРС1, НИРС) fill-with (НИРС1, руководит, Петров) fill-with (НИРС1, занимается, Иванов) Очевидно, что после некоторого заполнения базы данных информацию потребуется извлечь. Запрос к системе управления базой знаний, основанной на ДЛ, представляет собой описание, характеризующее искомое множество объектов. Например, если мы захотим получить данные обо всех НИРС, которыми руководит Петров, запрос должен выглядеть следующим образом: and (НИРС,
all (руководит, Петров))
ДЛ хорошо зарекомендовали себя в ситуациях, когда пользователи слабо знакомы с содержимым или структурой данных, или когда они не совсем уверены в том, какой запрос сформировать. Помимо этого они очень хорошо подходят при отслеживании последовательностей и зависимостей в больших объемах данных [5]. В последнем случае используется возможность построения иерархии запросов, с помощью которой можно:
• Определять недопустимые запросы, для которых из схемы базы знаний вытекает невозможность вернуть хотя бы одно значение, и предупреждать о неправильной формулировке запроса.
• Плавно обобщать запрос, поскольку довольно часто пустой ответ неудовлетворителен даже для правильно сформулированного запроса. В таких ситуациях запрос обобщается до тех пор, пока в ответе не будет получено непустое значение.
• Оптимизировать запросы на основе семантики данных.
Большинство работ по оптимизации запросов к базе данных (БД), как правило, концентрируются на оптимизации алгебраического представления запроса и на физическом доступе к данным. В свою очередь ДЛ позволяют строить отношение классификации между запросами и так называемыми проекциями (простыми запросами с хранимым ответом), значительно сокращая область поиска и, следовательно, время исполнения запросов. Кроме того, такие области как извлечение информации из данных (data mining) предполагают исполнение огромного количества запросов, возможно группой людей, и, иногда, в течение довольно продолжительного времени. Запросы и ответы на них могут при этом сопровождаться комментариями авторов. Построение иерархии из таких запросов помогает не только сократить общую нагрузку на сервер данных, но и позволяет согласовать работу коллектива из нескольких человек. Для всех современных систем такая операция классификации нового запроса по отношению к ранее исполненным является стандартной.
В синтаксисе логики CLASSIC есть конструктор fills, который используется для определений подобно fills (age, 40) чтобы описать класс объектов, у которых среди связей с ролью age имеется значение 40. Используя его, можно представить операцию fill-with (Crs431,takers, Иван) как insert-in (Crs431,fills (takers, Иван)). Таким образом, мы переформулируем операторы языка системы управления базы знаний (СУБЗ) в ограничения в описании объекта:
insert-in (New_НИРС, and (НИРС, at-least (7, takers), fills (тема, Нейронные сети), all (руководит, fills (ученая степень, д.т.н.)))
Такие конструкции языка, несмотря на свою кажущуюся незначительность, открывают очень широкие возможности: они позволяют СУБЗ обрабатывать неполную информацию об объектах. Например, в приведенном выше описании мы не знаем точно человека, который руководит данной темой НИРС, но кое-какую информацию все же имеем (в частности, что его ученая степень — д.т.н.). Эта информация может использоваться при построении ответа на запросы: на запрос типа «Найти все темы НИРС, которыми руководят преподаватели, являющиеся докторами технических наук», может быть возвращено значение New_НИРС, если описание объекта наследуется от запроса. Стоит обратить внимание на то, что ни одна современная система управления базами данных с такой неполной информацией о NewНИРС работать не сможет. В противовес этому, очень большую долю в приложениях систем ДЛ является как раз работа с неполной информацией. Современные системы, построенные на основе ДЛ, могут представлять данные с неограниченным количеством ««//-значений (например, «нечто, имеющее не менее 15 связей по ро-
ли») и корректно отвечать на запросы, касающиеся выражений с подобными недоопределенностями.
Наконец, когда схема БД очень велика, либо когда пользователь не знаком с семантикой БД, находят свое применение интенсиональные ответы на запросы: они показывают, какими свойствами на самом деле должен был бы обладать объект, чтобы удовлетворять запросу. Например, такая возможность бывает полезной при работе группы специалистов над одним очень большим проектом, содержащим множество ограничений на данные в схеме БД. При добавлении в команду нового разработчика интенсиональные ответы помогают ему быстро разобраться в этой скрытой структуре.
Дескриптивные языки представляют удобный инструмент для манипулирования данными, нашедший применение практически во всех областях, включая базы данных, медицину, лингвистику и языки программирования. Область их применения постоянно растет. В настоящее время, помимо ставших уже классическими ДЛ, разработаны расширения для вероятностных ДЛ, позволяющие строить и-отношения на домене, и другие, увеличивающие выразительность языка и стройность создаваемой с их помощью модели предметной области.
ДЛ предоставляет широкие возможности построения вывода. Для этого сначала необходимо строго сформулировать исчисление (построить аксиоматическую теорию).
Исчисление высказываний L — наиболее простой пример формальной аксиоматической теории в логике, использующий функционально полную систему связок, состоящую из отрицания «-» и импликации «^». Исчисление L описывает множество правильно построенных формул, среди которых выделяются тождественно истинные формулы (тавтологии). Это соответствует положению дел в математике, где теоремы, как доказуемые на базе аксиом высказывания, являются тождественно истинными утверждениями.
Язык исчисления L включает набор пропозициональных и специальных символов, а также строгие правила построения допустимых выражений (формул). Пропозициональные символы выбираются из не более чем счетного множества (алфавита), возможно, с индексами: {х, у,… }- i, j… =1,2,…
СПИСОК ЛИТЕРАТУРЫ
1. Baader F., Nutt. W. Basic description logics [Электронный ресурс] = Основы дескриптивной логики — Электронный документ -Режим доступа: http: //www. inf. unibz. it/~franconi/dl/cour-se/dlhb/dlhb-02. pdf. — Загл. с экрана.
2. Nardi D., Brachman J. An Introduction to Description Logics [Электронный ресурс] = Введение в дескриптивную логику. -Электронный документ — Режим доступа: http: //www. inf. unibz. it/~franconi/dl/course/dlhb/dlhb-01. pdf. — Загл. с экрана.
3. Тейз А., Грибомон П., Луи Ж. и др. Логический подход к искусственному интеллекту. — М.: Мир, 1990. — Т. 1. От классической логики к логическому программированию. — С. 125−134.
К специальным относятся символы логических операций отрицания «-» и импликации «^», а также вспомогательные символы скобок «(»,")».
Понятие формулы исчисления L определяется индуктивно: формулами полагаются все индивидные переменные х, у…, а затем и любые выражения вида (-A) и (A^B), где в качестве A и B могут выступать произвольные правильно построенные формулы.
Систему (предметных) аксиом исчисления L составляет бесконечное (счетное) множество формул исчисления, построенных с использованием следующих трех схем аксиом (конструкторов):
(А1) (Z^{Z^Z)) —
(А2) ((Zl^(Z1^Z))^((Zl^Z)^(Zl^Zi))) —
(A3) ((-Zl^-Z)M (-Zl^Z1)^Zl)).
Аксиомой считается любая формула, полученная согласованной подстановкой в схему аксиом допустимых формул исчисления L вместо переменных Z1, Z& gt-, Zi.
Единственным правилом вывода в исчислении L является правило modusponens, согласно которому из заданных формул, А и (A^B) с необходимостью выводится B. Для исчислений описанного класса могут быть построены эффективные и полные стратегии автоматического вывода (см., например, [6]).
В заключение отметим что, дескриптивные языки представляют удобный инструмент для манипулирования данными, нашедший применение практически во всех областях, включая базы данных, медицину, лингвистику и языки программирования. Область их применения постоянно растет. ДЛ хорошо зарекомендовали себя в ситуациях, когда пользователи слабо знакомы с содержимым или структурой данных, или когда они не совсем уверенны в том, какой запрос сформировать. Помимо этого они очень хорошо подходят при отслеживании последовательностей и зависимостей в больших объемах данных. Таким образом, с момента своего появления в конце XX в. как средство решения семантических и логических задач в семантических сетях ДЛ стала уникальным и важным механизмом в важном современном разделе информационных технологий — представлении знаний.
4. Voronkov A. Theorem proving in non-standard logics based on the inverse method // 11th Intern. Conf. on Automated Deduction, D. Kapur, Ed. Lecture Notes in Artificial Intelligence. — 1992. -P. 648−662.
5. Brachman R., Sefridge P. Knowledge representation support for data archeology // Intelligent and Cooperative Information Systems. -1993. — № 2. — P. 159−186.
6. Новосельцев В. Б. Теория функциональных моделей // Сибирский математический журнал. — 2006. — Т. 47. — № 6. -С. 1242−1354.
Поступила 12. 09. 2008 г.

ПоказатьСвернуть
Заполнить форму текущей работой