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

Дескрипцио?нная логика [1] (описательная логика [2] , ранние наименования — терминологическая система, логика концептов) — язык представления знаний, позволяющий описывать понятия предметной области в недвусмысленном, формализованном виде, организованный по типу языков математической логики. Дескрипционные логики сочетают, с одной стороны, богатые выразительные возможности, а с другой — хорошие вычислительные свойства, такие как разрешимость и относительно невысокая вычислительная сложность основных логических проблем, что делает возможным их применение на практике, обеспечивая компромисс между выразительностью и разрешимостью. Могут быть рассмотрены как разрешимые фрагменты логики предикатов, синтаксически же они близки к модальным логикам.

Современное название семейство получило в 1980-е годы, в то же время изучались как расширения теорий фреймовых структур и семантических сетей механизмами формальной логики. В 2000-е годы дескрипционные логики получили применение в рамках концепции семантической паутины, где их предлагалось использовать при построении онтологий. Фрагменты OWL-DL и OWL-Lite языка веб-онтологий OWL также основаны на дескрпиционных логиках.

Содержание

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

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

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

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

Типичными конструкторами для построения составных концептов являются:

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

Конъюнкция и дизъюнкция в дескрипционных логиках обычно обозначаются иначе, чтобы подчеркнуть отличие от других видов логик. Существуют дескрипционные логики, в которых имеются также составные роли, строящиеся из простых ролей с помощью операций: инверсии, пересечения, объединения, дополнения, композиции ролей, транзитивного замыкания и других [4] .

ALC Править

Дескрипционная логика A L C <\displaystyle <\mathcal >> (от англ. attributive language with complement ) разработана в 1991 году [5] и является одной из базовых систем, на основе которой строятся многие другие дескрипционные логики. Пусть заданы непустые конечные множества атомарных концептов и атомарных ролей. Тогда следующее является индуктивным определением составных концептов логики A L C <\displaystyle <\mathcal >> (концепты):

  • всякий атомарный концепт является концептом;
  • выражения ? <\displaystyle \top >и ? <\displaystyle \bot >являются концептами;
  • если C <\displaystyle C>есть концепт, то его дополнение ¬ C <\displaystyle \neg C>является концептом;
  • если C <\displaystyle C>и D <\displaystyle D>есть концепты, то их пересечение C ? D <\displaystyle C\sqcap D>и объединение C ? D <\displaystyle C\sqcup D>являются концептами;
  • если C <\displaystyle C>есть концепт, а R <\displaystyle R>есть роль, то выражения ? R . C <\displaystyle \forall R.C>и ? R . C <\displaystyle \exists R.C>являются концептами.

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

Далее интерпретирующая функция распространяется на составные концепты и роли. Поскольку последние в каждой ДЛ свои, то в качестве примера рассмотрим семантику для описанной выше логики A L C <\displaystyle <\mathcal >> .

Например, для ALC интерпретирующая функция распространяется на составные концепты логики A L C <\displaystyle <\mathcal >> по следующим правилам:

  • атомарные концепты A i <\displaystyle A_> переходят в пропозициональные переменные p i <\displaystyle p_> модальной логики;
  • пересечение ? <\displaystyle \sqcap >, объединение ? <\displaystyle \sqcup >и дополнение ¬ <\displaystyle \neg >концептов переходит в булевы связки конъюнкцию ? <\displaystyle \land >, дизъюнкцию ? <\displaystyle \lor >и отрицание ¬ <\displaystyle \neg >;
  • выражение ? R j <\displaystyle \forall R_> переходит в ? j <\displaystyle \Box _> , а выражение ? R j <\displaystyle \exists R_> переходит в ? j <\displaystyle \Diamond _> .

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

  • атомарные концепты A i <\displaystyle A_> переходят в формулы P i ( x ) <\displaystyle P_(x)> ;
  • пересечение ? <\displaystyle \sqcap >, объединение ? <\displaystyle \sqcup >и дополнение ¬ <\displaystyle \neg >концептов переходит в булевы связки конъюнкцию ? <\displaystyle \land >, дизъюнкцию ? <\displaystyle \lor >и отрицание ¬ <\displaystyle \neg >;
  • выражение ? R j . C <\displaystyle \forall R_.C> переходит в ? y ( S j ( x , y ) ? C ? ( y ) ) <\displaystyle \forall y(S_(x,y)\Rightarrow C'(y))> ;
  • выражение ? R j . C <\displaystyle \exists R_.C> переходит в ? y ( S j ( x , y ) ? C ? ( y ) ) <\displaystyle \exists y(S_(x,y)\land C'(y))> .

В данном переводе можно обойтись всего двумя переменными [7] , и таким образом A L C <\displaystyle <\mathcal >> (а также многие её расширения) можно рассматривать как фрагменты логики предикатов с двумя переменными, которая, как известно, разрешима [8] . Данный перевод позволяет переносить результаты о разрешимости, вычислительной сложности, разрешающих алгоритмах и т. п. из области логики предикатов в область дескрипционных логик.

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

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

  • набор терминологических аксиом или T B o x T <\displaystyle TBox<\mathcal >> и
  • набор утверждений об индивидах или A B o x A <\displaystyle ABox<\mathcal >> .

Совокупность аксиом и утверждений вместе составляют так называемую базу знаний K = T ? A <\displaystyle <\mathcal >=<\mathcal >\cup <\mathcal >> .

Терминологические аксиомы Править

Например, следующая совокупность является терминологией (или TBox) в языке логики A L C <\displaystyle <\mathcal >> :

W o m a n ? P e r s o n ? F e m a l e <\displaystyle <\mathsf >\equiv <\mathsf >\sqcap <\mathsf >> M o t h e r ? W o m a n ? ? h a s C h i l d . ? <\displaystyle <\mathsf >\equiv <\mathsf >\sqcap \exists <\mathsf >.\top > ? h a s C h i l d . P e r s o n ? P e r s o n <\displaystyle \forall <\mathsf >.<\mathsf >\sqsubseteq <\mathsf >> D o c t o r ? P e r s o n <\displaystyle <\mathsf >\sqsubseteq <\mathsf >>

Интуитивно (то есть при «естественной» интерпретации, когда концепту P e r s o n <\displaystyle <\mathsf >> соответствует множество всех людей, роли h a s C h i l d <\displaystyle <\mathsf >> соответствует отношение «имеет_ребенка» и т. д.) эти аксиомы говорят, что быть женщиной означает в точности быть человеком и быть женского пола; быть матерью означает в точности быть женщиной и иметь ребёнка; у всякого человека всякий ребёнок есть тоже человек; всякий доктор является человеком. Первые две аксиомы вместе представляют собой пример так называемой ациклической терминологии.

Утверждения об индивидах Править

Терминологии позволяют записывать общие знания о концептах и ролях. Однако помимо этого обычно требуется также записать знания о конкретных индивидах: к какому классу (концепту) они принадлежат, какими отношениями (ролями) они связаны друг с другом. Это делается в той части базы знаний ДЛ, которая называется A B o x <\displaystyle ABox>(или набор утверждений об индивидах).

С этой целью, помимо атомарных концептов и атомарных ролей, то есть имен для классов и отношений, вводится также конечное множество имён для индивидов. Утверждения об индивидах бывают двух видов:

  • утверждение о принадлежности индивида a <\displaystyle a>концепту C <\displaystyle C>— записывается как C ( a ) <\displaystyle C(a)>или a : C <\displaystyle a\colon C>;
  • утверждение о связи двух индивидов a <\displaystyle a>и b <\displaystyle b>ролью R <\displaystyle R>— записывается как R ( a , b ) <\displaystyle R(a,b)>или ( a , b ) : R <\displaystyle (a,b)\colon R>или a R b <\displaystyle a\,R\,b>.

Наконец, набором утверждений об индивидах или A B o x <\displaystyle ABox>(от англ. assertional box ) называется конечный набор утверждений этих двух видов.

В некоторых дескрипционных логиках допускаются также утверждения вида ¬ R ( a , b ) <\displaystyle \neg R(a,b)>в A B o x <\displaystyle ABox>.

Например, следующая совокупность является набором утверждений об индивидах (или ABox) в языке логики A L C <\displaystyle <\mathcal >> :

M a r y : W o m a n ? ¬ D o c t o r <\displaystyle <\mathsf >\colon <\mathsf >\sqcap \neg <\mathsf >> M a r y : ? h a s C h i l d . F e m a l e <\displaystyle <\mathsf >\colon \exists <\mathsf >.<\mathsf >> M a r y h a s C h i l d P e t e r <\displaystyle <\mathsf >\,<\mathsf >\,<\mathsf >> P e t e r : D o c t o r ? ? h a s C h i l d . ? <\displaystyle <\mathsf >\colon <\mathsf >\sqcap \forall <\mathsf >.\bot >

Здесь Mary и Peter есть имена индивидов. Интуитивно эти утверждения означают, что Mary является женщиной, но не доктором, у неё есть ребёнок женского пола, Peter также является ребёнком Mary, причем Peter является доктором и не имеет детей.

Часто рассматриваются лишь интерпретации, которые удовлетворяют соглашению об уникальности имён [en] . Оно означает, что разным именам индивидов интерпретация обязана сопоставлять различные элементы домена. Язык OWL по умолчанию не предполагает данное соглашение, однако в нём есть конструкции, с помощью которых можно явно указать, какие имена индивидов считать равным либо различными.

Отличие от баз данных Править

Помимо того, что базы знаний формулируются в несколько другом языке, нежели базы данных, их главное отличие заключается в использовании в ДЛ при логическом выводе так называемого предположения об открытости мира, тогда как в базах данных принимается предположение о замкнутости мира. Последнее означает, что если некоторое утверждение не является истинным, то оно принимается ложным. Предположение же об открытости мира в этом случае считает такое утверждение ни истинным, ни ложным. Это кардинальным образом влияет на то, какие факты считаются логически следующими из заданной базы знаний, а значит, и на само понятие логического следования в ДЛ.

>(R)>
F <\displaystyle <\mathcal >> Функциональность ролей: концепты вида ( ? 1 R ) <\displaystyle (<\leq >1\,R)> , означающие: существует не более одного R <\displaystyle R>-последователя
N <\displaystyle <\mathcal >> Ограничения кардинальности ролей: концепты вида ( ? n R ) <\displaystyle (<\leq >n\,R)> , означающие: существует не более n <\displaystyle n>R <\displaystyle R>-последователей
Q <\displaystyle <\mathcal >> Качественные ограничения кардинальности ролей: концепты вида ( ? n R . C ) <\displaystyle (<\leq >n\,R.C)> , означающие: существует не более n <\displaystyle n>R <\displaystyle R>-последователей в C
I <\displaystyle <\mathcal >> Обратные роли: если R <\displaystyle R>есть роль, то R ? <\displaystyle R^<->> тоже является ролью, означающей обращение бинарного отношения
O <\displaystyle <\mathcal >> Номиналы: если a <\displaystyle a>есть имя индивида, то < a ><\displaystyle \> есть концепт, означающий одноэлементное множество
H <\displaystyle <\mathcal >> Иерархия ролей: в TBox допускаются аксиомы вложенности ролей R ? S

S <\displaystyle <\mathcal >> Транзитивные роли: в TBox допускаются аксиомы транзитивности вида T r ( R ) <\displaystyle <\mathsf
R <\displaystyle <\mathcal >> Составные аксиомы вложенности ролей в TBox ( R ? S ? R <\displaystyle R\circ S\sqsubseteq R>, R ? S ? S <\displaystyle R\circ S\sqsubseteq S>) с условием ацикличности, где R ? S <\displaystyle R\circ S>есть композиция ролей
( D )

Расширение языка конкретными доменами (типами данных)

Рассматриваются также дескрипционные логики, в которых можно строить составные роли с помощью операций объединения, пересечения, дополнения, инверсии, композиции, транзитивного замыкания и других. Кроме того, исследованы ДЛ, в которых имеются многоместные роли (обозначающие n-арные отношения). [4]

Базы знаний, формулируемые на языке дескрипционных логик, применяются не только для представления знаний о предметной области, но также для логического анализа (англ. reasoning ) знаний, как то проверки отсутствия в них противоречий, вывода новых знаний из уже имеющихся, обеспечения возможности делать запросы к базам знаний (по аналогии с запросами к базам данных). Благодаря тому, что базы знаний ДЛ записаны в формализованном виде, имеется возможность делать строгий логический вывод. А поскольку синтаксис и семантика дескрипционных логик построены таким образом, что основные логические проблемы являются разрешимыми, то вывод новых знаний можно осуществлять компьютерными средствами — специальными программами ( reasoners ).

Некоторые определения логического анализа:

  • концепт C <\displaystyle C>данной логики выполняется в интерпретации I <\displaystyle <\mathcal >> , если C I ? ? <\displaystyle C^<\mathcal >\neq \varnothing > ;
  • концепт C <\displaystyle C>называется выполнимым, если существует интерпретация, в которой он выполняется;
  • концепт C <\displaystyle C>вложен в концепт D <\displaystyle D>(или содержится в нём; англ. is subsumed by ), если в любой интерпретации I <\displaystyle <\mathcal >> выполняется C I ? D I <\displaystyle C^<\mathcal >\subseteq D^<\mathcal >> .
  • индивид a <\displaystyle a>является экземпляром концепта C <\displaystyle C>относительно базы знаний K <\displaystyle <\mathcal >> , если в любой модели I <\displaystyle <\mathcal >> базы знаний K <\displaystyle <\mathcal >> имеет место a I ? C I <\displaystyle a^<\mathcal >\in C^<\mathcal >> .

Следующие понятия формализуют ключевые алгоритмические проблемы, связанные с конкретной дескрипционной логикой:

  • выполнимость концепта: является ли заданный концепт выполнимым относительно заданного TBox?
  • вложенность концептов: верно ли, что один заданный концепт вложен в другой относительно заданного TBox?
  • совместимость TBox: имеет ли заданный TBox хотя бы одну модель?
  • совместимость базы знаний: имеет ли заданная пара (TBox, ABox) хотя бы одну модель?

В логиках, содержащих A L C <\displaystyle <\mathcal >> , проблема вложенности концептов сводится к выполнимости концепта. [4] Важное практическое значение имеют нестандартные алгоритмические проблемы, в частности:

  • классификация терминологии: для данной терминологии (то есть TBox) построить таксономию или иерархию концептов, то есть упорядочить все атомарные концепты по отношению вложения (отн. данного TBox) и выдать соответствующее частично упорядоченное множество;
  • извлечение экземпляров концепта: найти все экземпляры заданного концепта относительно заданной базы знаний;
  • наиболее узкий концепт для индивида: найти наименьший (по вложению) концепт, экземпляром которого является заданный индивид относительно заданной базы знаний;
  • ответ на запрос к базе знаний: выдать все наборы индивидов, которые удовлетворяют заданному запросу относительно заданной базы знаний. В настоящее время глубоко изучены так называемые конъюнктивные запросы к базам знаний дескрипционных логик (а также их дизъюнкции), которые похожи на аналогичные запросы из области баз данных; в случае же запросов более общего вида проблема быстро приобретает высокую вычислительную сложность или даже становится неразрешимой [10][11] .

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

    : обычно рассматривают разрешимость проблем выполнимости концепта (относительно TBox), совместимости базы знаний, ответа на конъюнктивные запросы; : изучается вычислительная сложность указанных выше алгоритмических проблем относительно размера входных данных (концепта, TBox, ABox). Отдельно выделяют сложность проблемы выполнимости концепта при фиксированном TBox, сложность проблемы выполнимости базы знаний или проблемы ответа на запросы при фиксированном TBox и меняющемся ABox (так называемая сложность по данным, англ. data complexity );
  • свойство конечности моделей[en] (полнота относительно конечных моделей): исследуется вопрос, всегда ли верно, что если концепт выполним (относительно TBox), то он выполним и на некоторой конечной модели (данного TBox); из наличия данного свойства у конкретной логики обычно следует, что для неё более просто строится разрешающая процедура, например, табло-алгоритм; (полнота относительно древовидных моделей, англ. tree model property ): аналогичный вопрос, но не о конечных, а о «древовидных» моделях, при этом древовидными здесь могут считаться структуры, слегка отличающиеся от традиционного понятия дерева; например, могут допускаться петли (ребра, ведущие из вершины в эту же вершину), мультирёбра (несколько ребер различных «типов», ведущих из одной вершины в другую), транзитивные деревья (структуры, являющиеся транзитивным замыканием обычных деревьев), а также их комбинации; у логик, обладающих данным свойством, обычно более низкая вычислительная сложность, в частности, более просто строится разрешающий табло-алгоритм.

Получено большое количество результатов, касающихся этих свойств различных дескрипционных логик [12] .

Язык веб-онтологий OWL разрабатывается как язык, на котором можно формулировать и публиковать в веб так называемые сетевые онтологии — формально записанные утверждения о понятиях и объектах некоторой предметной области. Одним из требований к таким онтологиям заключается в том, чтобы содержащиеся в них знания были «доступны» для машинной обработки, в частности, для автоматизированного логического вывода новых знаний из уже имеющихся. Для этого требуется, чтобы язык, на котором формулируются онтологии, имел точную семантику, а соответствующие логические проблемы были разрешимы (и имели практически допустимую вычислительную сложность). Кроме того, желательно, чтобы такой язык имел довольно большую выразительную силу, пригодную для формулировки на нём практически значимых фактов.

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

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

Официальной рекомендацией W3C от 10 февраля 2004 года является версия языка OWL 1.0. Данная спецификация языка OWL подразделяется на следующие варианты:

    — соответствует дескрипционной логике S H I F ( D ) <\displaystyle <\mathcal >(D)> ; — соответствует дескрипционной логике S H O I N ( D ) <\displaystyle <\mathcal >(D)> ; — не соответствует какой-либо дескрипционной логике, более того, является неразрешимым.

Одновременно с этим разрабатывается следующая версия языка OWL 2.0, которая, помимо перечисленного, даст возможность формулировать онтологии в языке, соответствующем дескрипционной логике E L <\displaystyle <\mathcal >> (преимущество которой в том, что она имеет полиномиальную вычислительную сложность); привнесет синтаксические улучшения, позволяющие легче составлять запросы к базам знаний и выдавать ответы на них; а также будет содержать механизмы для формулировки правил логического вывода [14] .

Имеется множество программных систем (машин вывода), позволяющих совершать логический анализ в дескрипционных логиках (проверять онтологию на непротиворечивость, строить таксономии, проверять выполнимость и вложенность концептов, делать запросы к базам знаний и др.). Подобные системы различаются по поддерживаемым ими дескрипционным логикам, по типу реализованной в них разрешающей процедуры (например, табло-алгоритм, резолюция и т. п.), по поддерживаемым форматам данных, языку программирования, на котором они реализованы, и другим параметрам. Некоторые известные можно системы [15] :

  • CEL — поддерживает логику E L + <\displaystyle <\mathcal >+> , имеющую полиномиальную сложность, написана на Лиспе[16] ;
  • FaCT++ — поддерживает логику s R O I Q ( D ) <\displaystyle s<\mathcal >(D)> , а также OWL 2.0, реализует табло-алгоритм, написана на C++[17] ;
  • Kaon2 — поддерживает логику S H I Q <\displaystyle <\mathcal >> , расширенную специальными правилами вывода, реализует алгоритм, основанный на резолюции, написан на Java[18] ;
  • Pellet — поддерживает логику s R O I Q ( D ) <\displaystyle s<\mathcal >(D)> , а также OWL 1.1, реализует табло-алгоритм, написан на Java[19] ;
  • RacerPro — поддерживает логику S H I Q ( D ) <\displaystyle <\mathcal >(D)> , реализует табло-алгоритм, написана на Лиспе [20] .

Существуют также редакторы онтологий, позволяющие создавать онтологии, сохранять их в различных форматах, некоторые позволяют подключить блок рассуждений (англ. reasoner ) и с его помощью произвести логический анализ онтологии. Одним из наиболее известных является редактор онтологий Protege, позволяющий работать с онтологиями в языке OWL Full.

Оставьте комментарий