Дескрипционные логики¶

Дескрипционные логики (англ. description logics, DL) — это семейство формальных языков представления знаний, предназначенных для описания понятий (концептов) и отношений между ними в некоторой предметной области. Они являются подмножеством логики первого порядка, обладающим разрешимостью (то есть для любого утверждения существует алгоритм, определяющий его истинность) и, как правило, более низкой вычислительной сложностью, чем полная логика первого порядка. Дескрипционные логики лежат в основе языков онтологий, таких как OWL (Web Ontology Language), и широко используются в семантической паутине, биоинформатике, медицине и других областях, где требуется формальное моделирование знаний.

¶История

Истоки дескрипционных логик восходят к системам представления знаний на основе фреймов и семантических сетей, разработанным в 1970-х годах. Эти системы, такие как KL-ONE (созданная в 1978 году Рональдом Брахманом и Джеймсом Шмольцем), обладали выразительностью, но не имели формальной семантики, что приводило к неоднозначности и сложности автоматического вывода. В 1980-х годах началась работа по формализации этих систем, что привело к появлению дескрипционных логик как самостоятельной области.

Ключевой вклад в развитие внесли такие исследователи, как Франц Баадер, Ульрих Зард, Бернхард Небель и другие. В 1990-х годах были разработаны основные семейства дескрипционных логик (например, ALC, SHOIQ), а также алгоритмы для решения задач вывода (например, табличные алгоритмы). В 2000-х годах дескрипционные логики стали основой для стандарта OWL, принятого Консорциумом Всемирной паутины (W3C). В 2004 году была опубликована первая версия OWL (OWL 1), а в 2009 году — OWL 2, которая базируется на дескрипционной логике SROIQ(D).

¶Основные понятия

¶Концепты и роли

В дескрипционных логиках знания представляются с помощью двух основных типов сущностей:

• Концепты (классы) — описывают множества объектов (индивидов). Например, концепт Человек обозначает множество всех людей, а концепт Студент — множество студентов.
• Роли (свойства) — описывают бинарные отношения между индивидами. Например, роль имеетРодителя связывает человека с его родителем, а роль учитсяВ — студента с учебным заведением.

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

¶Конструкторы

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

• Пересечение (⊓): C ⊓ D — концепт, обозначающий индивиды, принадлежащие как концепту C, так и концепту D. Например, Человек ⊓ Студент — это человек, который является студентом.
• Объединение (⊔): C ⊔ D — концепт, обозначающий индивиды, принадлежащие хотя бы одному из концептов C или D.
• Отрицание (¬): ¬C — концепт, обозначающий индивиды, не принадлежащие концепту C.
• Квантор существования (∃): ∃R.C — концепт, обозначающий индивиды, которые связаны ролью R хотя бы с одним индивидом, принадлежащим концепту C. Например, ∃учитсяВ.Университет — это индивид, который учится в каком-то университете.
• Квантор всеобщности (∀): ∀R.C — концепт, обозначающий индивиды, которые связаны ролью R только с индивидами, принадлежащими концепту C. Например, ∀имеетРодителя.Человек — это индивид, все родители которого являются людьми.
• Ограничения на количество (≥, ≤): ≥ n R.C — концепт, обозначающий индивиды, которые связаны ролью R по меньшей мере с n различными индивидами, принадлежащими концепту C. Например, ≥ 2 имеетРебенка.Человек — это человек, имеющий не менее двух детей.
• Номиналы ({a}): концепт, состоящий из одного индивида a. Например, {Иван} — концепт, обозначающий индивида по имени Иван.

¶Аксиомы

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

• Включение концепта (C ⊑ D): утверждает, что каждый индивид, принадлежащий концепту C, также принадлежит концепту D. Например, Студент ⊑ Человек — каждый студент является человеком.
• Эквивалентность концепта (C ≡ D): утверждает, что концепты C и D обозначают одно и то же множество индивидов. Это сокращение для двух включений: C ⊑ D и D ⊑ C.
• Включение роли (R ⊑ S): утверждает, что роль R является подролью роли S. Например, имеетБрата ⊑ имеетРодственника.
• Утверждения об индивидах: C(a) — индивид a принадлежит концепту C; R(a, b) — индивиды a и b связаны ролью R.

¶Семейства дескрипционных логик

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

• ALC (Attributive Language with Complement) — базовая логика, включающая конструкторы ⊓, ⊔, ¬, ∃, ∀. Она является минимальной логикой, обладающей достаточной выразительностью для многих приложений.
• SHOIQ — расширение ALC, добавляющее иерархию ролей (H), номиналы (O), обратные роли (I) и ограничения на количество (Q). Эта логика лежит в основе OWL 1 DL.
• SROIQ — дальнейшее расширение SHOIQ, добавляющее рефлексивные, иррефлексивные, симметричные, асимметричные и транзитивные роли, а также правила ролей (R). Эта логика лежит в основе OWL 2 DL.

¶Задачи вывода

Основные задачи, решаемые с помощью дескрипционных логик:

• Проверка выполнимости (satisfiability): является ли концепт C непустым? То есть существует ли модель, в которой есть хотя бы один индивид, принадлежащий C?
• Проверка вложенности (subsumption): верно ли, что C ⊑ D? То есть каждый индивид, принадлежащий C, обязательно принадлежит D?
• Проверка принадлежности (instance checking): верно ли, что индивид a принадлежит концепту C?
• Поиск (retrieval): найти все индивиды, принадлежащие заданному концепту.

Для решения этих задач разработаны различные алгоритмы, наиболее распространёнными из которых являются табличные алгоритмы (tableau algorithms). Они работают путём построения модели (или её фрагмента) и проверки непротиворечивости.

¶Применение

¶Семантическая паутина

Дескрипционные логики являются формальной основой для языка OWL, который используется для создания онтологий в семантической паутине. Онтологии на OWL позволяют описывать структуру знаний на веб-страницах, что даёт возможность автоматизировать поиск, интеграцию и анализ данных. Например, онтология FOAF (Friend of a Friend) описывает людей и их социальные связи.

¶Медицина и биоинформатика

Одним из наиболее известных примеров применения дескрипционных логик является медицинская онтология SNOMED CT (Systematized Nomenclature of Medicine — Clinical Terms). Она содержит сотни тысяч понятий, описывающих заболевания, симптомы, лекарства и медицинские процедуры, и используется для стандартизации медицинской информации. Онтология Gene Ontology (GO), описывающая функции генов, также использует формализмы, близкие к дескрипционным логикам.

¶Промышленность

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

¶Интеллектуальные системы

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

¶Критика и ограничения

Несмотря на широкое применение, дескрипционные логики имеют ряд ограничений:

• Вычислительная сложность: хотя дескрипционные логики разрешимы, некоторые из них (например, SROIQ) имеют высокую вычислительную сложность (N2EXPTIME-полнота), что может затруднять их применение для очень больших онтологий.
• Выразительность: дескрипционные логики не могут выражать некоторые типы знаний, например, мета-знания (знания о знаниях) или нечёткие и неопределённые утверждения.
• Отсутствие поддержки правил: в отличие от логического программирования, дескрипционные логики не имеют встроенной поддержки для правил вывода, таких как продукционные правила. Однако существуют расширения, такие как SWRL (Semantic Web Rule Language), которые добавляют такую возможность.

¶Источники

• Baader, F., Calvanese, D., McGuinness, D. L., Nardi, D., & Patel-Schneider, P. F. (Eds.). (2003). The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press.
• Horrocks, I., & Sattler, U. (2001). Ontology Reasoning in the SHOQ(D) Description Logic. In Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI-01).
• W3C OWL Working Group. (2009). OWL 2 Web Ontology Language: Document Overview. W3C Recommendation.
• Brachman, R. J., & Schmolze, J. G. (1985). An Overview of the KL-ONE Knowledge Representation System. Cognitive Science, 9(2), 171–216.