Дескрипционная логика

Дескрипционные логики оперируют понятиями «концепт» и «роль», которые соответствуют в других разделах математической логики понятиям «одноместный предикат» (или множество, класс) и «двуместный предикат» (или бинарное отношение). Интуитивно, концепты используются для описания классов объектов, например, «Люди», «Женщины», «Машины». Роли описывают двуместные отношения между объектами (например, «X есть_родитель_для Y» или «X имеет_в_собственности Y»). С помощью языка дескрипционной логики можно формулировать как общие утверждения о классах (например, всякая Женщина есть Человек, всякая Машина не более чем у одного Человека), так и частные — о конкретных объектах (например, Мария есть Женщина, Иван имеет_в_собственности Машину1).

Набор общих утверждений или терминологии (англ. terminology) называется TBox, а набор утверждений (англ. assertions) частного вида — ABox; вместе они образуют базу знаний или онтологию. Онтологии на основе дескрипционных логик используются во многих областях — биоинформатика, генетика, медицина, химия, биология. Реализация логического вывода на уровне программ обеспечивают так называемые механизмы рассуждений (англ. reasoners), которые позволяют автоматически выводить знания из онтологий и выполнять другие операции. В нейросимволических системах исследуется сочетание нейросетевой обработки данных с формальным выводом средствами дескрипционных логик^[3].

В математической логике язык определяется своим синтаксисом — правилами построения выражений, и семантикой — способом приписывания этим выражениям значения.

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

Типичные конструкторы составных концептов:

• пересечение (или конъюнкция) концептов: ${\displaystyle C\sqcap D}$;
• объединение (или дизъюнкция) концептов: ${\displaystyle C\sqcup D}$;
• дополнение (отрицание) концепта: ${\displaystyle \neg C}$;
• ограничение на значения роли (квантор всеобщности): ${\displaystyle \forall R.C}$;
• экзистенциальное ограничение (квантор существования): ${\displaystyle \exists R.C}$;
• численные ограничения: ${\displaystyle ({\leq }n\,R)}$, ${\displaystyle ({\geq }n\,R.C)}$ и др.

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

Семантика дескрипционных логик задаётся интерпретацией атомарных концептов как множеств объектов (англ. individual), а ролей — как множеств пар объектов (бинарных отношений) на домене ${\displaystyle \Delta ^{\mathcal {I}}}$.

Интерпретация ${\displaystyle {\mathcal {I}}}$ состоит из:

• домена ${\displaystyle \Delta ^{\mathcal {I}}}$ (непустое множество);
• функции, сопоставляющей каждому атомарному концепту ${\displaystyle A}$ подмножество ${\displaystyle A^{\mathcal {I}}\subseteq \Delta ^{\mathcal {I}}}$, а каждой атомарной роли ${\displaystyle R}$ — подмножество ${\displaystyle R^{\mathcal {I}}\subseteq \Delta ^{\mathcal {I}}\times \Delta ^{\mathcal {I}}}$.

Правила для ${\displaystyle {\mathcal {ALC}}}$:

• ${\displaystyle \top ^{\mathcal {I}}=\Delta ^{\mathcal {I}}}$
• ${\displaystyle \bot ^{\mathcal {I}}=\varnothing }$
• ${\displaystyle (\neg C)^{\mathcal {I}}=\Delta ^{\mathcal {I}}\setminus C^{\mathcal {I}}}$
• ${\displaystyle (C\sqcap D)^{\mathcal {I}}=C^{\mathcal {I}}\cap D^{\mathcal {I}}}$
• ${\displaystyle (C\sqcup D)^{\mathcal {I}}=C^{\mathcal {I}}\cup D^{\mathcal {I}}}$
• ${\displaystyle (\forall R.C)^{\mathcal {I}}=\{\,e\in \Delta ^{\mathcal {I}}\mid \forall d\in \Delta ^{\mathcal {I}}:(e,d)\in R^{\mathcal {I}}\Rightarrow d\in C^{\mathcal {I}}\,\}}$
• ${\displaystyle (\exists R.C)^{\mathcal {I}}=\{\,e\in \Delta ^{\mathcal {I}}\mid \exists d\in \Delta ^{\mathcal {I}}:(e,d)\in R^{\mathcal {I}}\land d\in C^{\mathcal {I}}\,\}}$

Например, если ${\displaystyle M}$ — множество мужчин, ${\displaystyle R}$ — «есть родитель для», то ${\displaystyle \forall R.M}$ — множество людей, у которых все дети мужского пола; ${\displaystyle M\sqcap \exists R.\top }$ — множество отцов.

В 1991 году^[5] было показано, что ${\displaystyle {\mathcal {ALC}}}$ эквивалентна многомодальной модальной логике ${\displaystyle \mathbf {K} _{n}}$ (n независимых модальностей): атомарные концепты переходят в пропозициональные переменные, пересечение/объединение/отрицание — в булевы связки, ${\displaystyle \forall R_{j}}$ — в ${\displaystyle \Box _{j}}$, ${\displaystyle \exists R_{j}}$ — в ${\displaystyle \Diamond _{j}}$. Фактически, это один и тот же язык в разных обозначениях, и их семантика согласуется (семантика Крипке и др.), что даёт возможность переносить результаты по разрешимости, сложности и процедурам из модальных логик. Темпоральные и эпистемические расширения дескрипционных логик изучаются, в частности, с использованием модальностей линейной темпоральной логики (LTL) и эпистемической логики S5^[6].

Дескрипционные логики (включая ${\displaystyle {\mathcal {ALC}}}$) можно рассматривать как фрагменты логики предикатов, когда концепты переводятся в формулы с одним объектным переменным. Атомарные концепты ${\displaystyle A_{i}}$ переходят в ${\displaystyle P_{i}(x)}$, роли ${\displaystyle R_{j}}$ — в ${\displaystyle S_{j}(x,y)}$. Выражения ${\displaystyle \forall R_{j}.C}$ — в ${\displaystyle \forall y(S_{j}(x,y)\Rightarrow C'(y))}$, ${\displaystyle \exists R_{j}.C}$ — в ${\displaystyle \exists y(S_{j}(x,y)\land C'(y))}$ (где ${\displaystyle C'}$ — перевод ${\displaystyle C}$). В этом переводе используются только две переменные^[7], поэтому ${\displaystyle {\mathcal {ALC}}}$ относится к разрешимому двухпеременному фрагменту логики предикатов^[8]. Логика ${\displaystyle {\mathcal {ALCQI}}}$, расширяющая ${\displaystyle {\mathcal {ALC}}}$ ограничениями количества и обратными ролями, погружается в охраняемый двухпеременный фрагмент со счётными кванторами (${\displaystyle {\mathcal {GC}}^{2}}$)^[9]. В охраняемом фрагменте логики предикатов (GF) квантификация ограничена атомарными формулами, содержащими свободные переменные; ${\displaystyle {\mathcal {GC}}^{2}}$ допускает также счётные кванторы^[10]. Аксиомы транзитивности и цепочек ролей, напротив, при стандартном переводе требуют трёх переменных; поэтому не все расширения ${\displaystyle {\mathcal {ALC}}}$ укладываются в двухпеременный фрагмент^[11].

Концепты дескрипционных логик важны как инструмент для формализации знаний об описываемой предметной области. Знания делятся на общие (интенсиональные — о понятиях и связях) и знания об объектах (экстенсиональные — о свойствах и отношениях между ними).

Выделяют:

• набор терминологических аксиом — ${\displaystyle TBox{\mathcal {T}}}$
• набор утверждений о конкретных объектах — ${\displaystyle ABox{\mathcal {A}}}$

Их объединение образует базу знаний ${\displaystyle {\mathcal {K}}={\mathcal {T}}\cup {\mathcal {A}}}$. В более выразительных логиках аксиомы, описывающие свойства и иерархии ролей, выделяют в отдельный компонент базы знаний — RBox^[12].

Существуют расширения ${\displaystyle {\mathcal {ALC}}}$ дополнительными конструкторами и аксиомами. Принято обозначать буквой добавленную возможность:

${\displaystyle {\mathcal {F}}}$	Функциональность ролей: ${\displaystyle ({\leq }1\,R)}$ — не более одного R-последователя
${\displaystyle {\mathcal {N}}}$	Ограничения кардинальности: ${\displaystyle ({\leq }n\,R)}$
${\displaystyle {\mathcal {Q}}}$	Качественные ограничения: ${\displaystyle ({\leq }n\,R.C)}$
${\displaystyle {\mathcal {I}}}$	Обратные роли: ${\displaystyle R^{-}}$
${\displaystyle {\mathcal {O}}}$	Номиналы: ${\displaystyle \{a\}}$ — одноэлементное множество
${\displaystyle {\mathcal {H}}}$	Иерархия ролей: аксиомы ${\displaystyle R\sqsubseteq S}$
${\displaystyle {\mathcal {S}}}$	Транзитивные роли: аксиомы ${\displaystyle {\mathsf {Tr}}(R)}$
${\displaystyle {\mathcal {R}}}$	Составные аксиомы вложенности ролей (${\displaystyle R\circ S\sqsubseteq R}$)
${\displaystyle {\mathcal {B}}}$	Булевы операции над ролями, например ${\displaystyle R\sqcup S}$ и ${\displaystyle \neg R}$[16]
${\displaystyle (D)}$	Расширения конкретными доменами (типами данных)

Например, ${\displaystyle {\mathcal {ALCIOQ}}}$ — логика с инверсными ролями, номиналами и качественными ограничениями. ${\displaystyle {\mathcal {SHIQ}}}$ — расширения инверсными ролями (${\displaystyle I}$), качественными ограничениями (${\displaystyle Q}$), транзитивными ролями (${\displaystyle S}$) и иерархией ролей (${\displaystyle H}$). Буква ${\displaystyle S}$ выбрана из-за исторической связи с модальной логикой ${\displaystyle \mathbf {S4} }$^[5].

Логика ${\displaystyle {\mathcal {SROIQ}}}$ включает сложные аксиомы включения ролей (в частности, цепочки ролей), квалифицированные ограничения количества и конструкцию локальной рефлексивности ${\displaystyle \exists R.{\mathsf {Self}}}$^[17].

К аксиомам ролей в ${\displaystyle {\mathcal {SROIQ}}}$ относятся также рефлексивность, иррефлексивность и непересекаемость ролей^[17].

Наряду с перечисленными конструкторами исследуются вероятностные^[18] и нечёткие^[19] расширения дескрипционных логик.

Для некоторых логик дополнительные ограничения требуются для разрешимости^[20].

Базы знаний из дескрипционных логик применяются не только для представления знаний, но и для логического анализа (англ. reasoning) — проверки непротиворечивости знаний, логического вывода, ответа на запросы.

Определения:

• концепт ${\displaystyle C}$ выполняется в интерпретации ${\displaystyle {\mathcal {I}}}$, если ${\displaystyle C^{\mathcal {I}}\neq \varnothing }$
• выполнимый концепт — существует интерпретация, где он выполняется
• вложение: ${\displaystyle C}$ вложен в ${\displaystyle D}$, если во всех интерпретациях ${\displaystyle C^{\mathcal {I}}\subseteq D^{\mathcal {I}}}$

Аналогично для TBox, ABox и базы знаний ${\displaystyle {\mathcal {K}}={\mathcal {T}}\cup {\mathcal {A}}}$.

Практически важные задачи:

• выполнимость концепта (относительно TBox)
• вложение концептов
• совместимость TBox (есть ли модель)
• совместимость базы знаний (модель для пары TBox, ABox)
• построение таксономии (иерархии) концептов
• извлечение экземпляров концепта
• наименее общий над-концепт
• наилучшее описание для объекта
• ответ на запрос к базе знаний

К нестандартным задачам логического анализа также относятся абдукция — поиск гипотез, добавление которых к базе знаний позволяет вывести заданное наблюдение^[21], и забывание — исключение символов из словаря с сохранением следствий, выразимых через оставшиеся символы^[22].

При ответе на конъюнктивный запрос уверенными ответами называют кортежи, для которых запрос истинен во всех моделях базы знаний; таким образом, учитываются и следствия терминологических аксиом, а не только явно записанные факты^[23].

Запросы вида конъюнктивных запросов похожи на методы в базах данных; для более сложных запросов вычислительная трудоёмкость высока или задача становится неразрешимой^[24][25].

Ключевые свойства:

• разрешимость основных задач
• вычислительная сложность, в том числе сложность по данным (англ. data complexity)
• свойство конечности моделей (англ. finite model property)
• свойство древовидности моделей (англ. tree model property)

Для ${\displaystyle {\mathcal {ALC}}}$ свойство древовидности означает, что выполнимый относительно TBox концепт имеет модель с древовидной структурой связей между элементами домена; это свойство используется при доказательстве разрешимости задач вывода^[26]. Для ${\displaystyle {\mathcal {ALC}}}$ свойство конечности моделей выполняется, а для ${\displaystyle {\mathcal {SHIQ}}}$ и ${\displaystyle {\mathcal {SROIQ}}}$ — нет: выполнимая база знаний в этих логиках может не иметь конечной модели. Выполнимость концепта в ${\displaystyle {\mathcal {ALC}}}$ без терминологических аксиом является PSPACE-полной^[27]. Для ${\displaystyle {\mathcal {SHIQ}}}$ выполнимость базы знаний в общей постановке является EXPTIME-полной. Если терминология фиксирована, а размер ABox меняется, то для ${\displaystyle {\mathcal {ALC}}}$ и ${\displaystyle {\mathcal {SHIQ}}}$ проверка принадлежности индивида концепту является coNP-полной по данным, а проверка выполнимости базы знаний — NP-полной по данным. Для ${\displaystyle {\mathcal {SROIQ}}}$ проверка выполнимости базы знаний в общей постановке является 2NEXPTIME-полной^[28]. Исследованы многочисленные результаты по этим характеристикам.

Язык OWL служит для формализации и публикации в сети сетевых онтологий — утверждений о концептах и объектах области знаний. Важным требованием OWL является точная семантика и разрешимость ключевых логических задач при приемлемой сложности. Дескрипционные логики были выбраны как логическая основа OWL благодаря этим свойствам.

Понятия дескрипционных логик (концепт, роль, объект, база знаний) в OWL соответствуют понятиям «класс», «свойство», «объект», «онтология».

Официальная рекомендация W3C от 10 февраля 2004 года:

• OWL-Lite — соответствует ${\displaystyle {\mathcal {SHIF}}(D)}$
• OWL-DL — соответствует ${\displaystyle {\mathcal {SHOIN}}(D)}$
• OWL-Full — не соответствует никакой разрешимой логике

Рабочий проект OWL 1.1 предусматривал логику ${\displaystyle s{\mathcal {ROIQ}}(D)}$, допуская составные аксиомы вложенности ролей (буква ${\displaystyle R}$), аксиомы непересекаемости, рефлексивности, асимметрии и др. новые конструкции^[29].

Проект OWL 2 предусматривал возможность выражать онтологии на языке ${\displaystyle {\mathcal {EL}}}$ (с полиномиальной сложностью) и расширение средств для запросов и аналитики.

В 2009 году OWL 2 получил статус рекомендации W3C.

11 декабря 2012 года W3C опубликовал второе издание рекомендации OWL 2. OWL 2 DL основан на дескрипционной логике ${\displaystyle {\mathcal {SROIQ}}(D)}$^[2]. OWL 2 Full, в отличие от OWL 2 DL, не является разрешимым языком^[30].

В OWL 2 DL ограничения количества и конструкцию локальной рефлексивности разрешено применять только к простым ролям: транзитивные роли и роли, определяемые цепочками, к ним не относятся. Для аксиом включения цепочек ролей также требуется регулярность иерархии ролей^[31]. Регулярность ограничивает циклические зависимости между ролями и позволяет применять автоматные методы для сохранения разрешимости вывода.

В OWL 2 аксиома ключа HasKey позволяет вывести тождество именованных индивидов одного класса при наличии общих значений у заданных свойств; функциональное свойство, напротив, ограничивает число значений свойства у одного индивида.

В OWL 2 также определены профили OWL 2 EL (на основе ${\displaystyle {\mathcal {EL}}^{++}}$ для больших терминологий), OWL 2 QL (на основе семейства DL-Lite для доступа к данным посредством запросов) и OWL 2 RL (связанный с DLP и pD* для вывода по правилам)^[32].

Существует множество программных систем (машин вывода), реализующих автоматические рассуждения в дескрипционных логиках: проверка непротиворечивости онтологий, построение таксономий, анализ выполнимости (табло-алгоритм, резолюция и др.), поддержка различных форматов и языков. Помимо табло и резолюции применяется вывод на основе следствий (англ. consequence-based reasoning): он выводит следствия из аксиом без явного построения модели; этот метод используется, в частности, в системе Sequoia^[33].

Некоторые известные reasoners^[34]:

• CEL — реализует ${\displaystyle {\mathcal {EL}}+}$ (полиномиальная сложность), написан на Лисп^[35]
• ELK — машина вывода, доступная в редакторе Protégé^[36]
• FaCT++ — поддержка ${\displaystyle s{\mathcal {ROIQ}}(D)}$ и OWL 2.0, реализует табло-алгоритм (C++)^[37]
• HermiT — машина вывода для OWL 2, использующая метод гипертабло (Java)
• Konclude — машина вывода для OWL 2 DL, реализованная на C++ с использованием параллельной обработки^[38]
• Kaon2 — реализует ${\displaystyle {\mathcal {SHIQ}}}$ и специальные правила, механизм резолюции (Java)^[39]
• Pellet — реализует ${\displaystyle s{\mathcal {ROIQ}}(D)}$ и OWL 1.1 (Java)^[40]
• RacerPro — реализует ${\displaystyle {\mathcal {SHIQ}}(D)}$ (Лисп)^[41]

Широко используются редакторы онтологий; например, Protégé, поддерживающий OWL 2 и подключение машин вывода для OWL DL.