�ݺ�ߣ

Онтологии и Представление Знаний

Борис Конев

Department of Computer Science

Liverpool University

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

Комбинирование определений

Коллекция медицинских терминов SNOMED допускала порождение новых терминов путем
комбинирования известных

T-1X500 = bone
T-1X501 = long bone (kind-of)
T-1X505 = shaft of bone (part-of)
T-1X520 = cortex of bone (constituent-of)

Онтологии и представление знаний, 2010 3

Комбинирование определений

Коллекция медицинских терминов SNOMED допускала порождение новых терминов путем
комбинирования известных

T-1X500 = bone
T-1X501 = long bone (kind-of)
T-1X505 = shaft of bone (part-of)
T-1X520 = cortex of bone (constituent-of)

T-67000 + M-12000 + E-4986 + F-90000 =fracture in colon caused by donkey
together with emotional state


Что такое дескрипционные логики?

• семейство логических формализмов для представления знаний

– происходят от of семантических сетей и системы KL-ONE

– описывают домен в терминах
концептов (классов, понятий), ролей (отношений) и индивидов

– определение сложных понятий как комбинации простых

Отличаются

• наличием формальной семантики (обычно, стандартная семантика Тарского)

– более выразительны, чем пропозициональная логика

– обычно разрешимы

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

• наличие средств логического анализа

– полные и корректные процедуры

– (оптимизированные) реализации


Архитектура ДЛ

База знаний (KB)

TBox (терминология, схема)

Система анализа

Интерфейс
Man ≡ Human ⊓ Male
HappyFather ≡ Man ⊓ ∃hasChild
...

ABox (assertion box, данные)

john: Man
(john, mary): hasChild
...


Краткая история

• 1-й этап (1975-1990):
– Системы логического анализа не соответствовали формальной семантике (т.е., системы
были не полные и/или не корректные) (Back, Classic, Loom, ...)
– основаны на структурном анализе

• 2-й этап (1990-1995):
– развитие полных и корректных табличных алгоритмов Kris, Crack)
– анализ вычислительной сложности задач логического анализа
– первые реализации табличных систем систем
– развитие методов оптимизации

• 3-й этап (from 1995):
– табличные алгоритмы для ДЛ большой выразительной силы
– оптимизированные реализации, “успешно” решающие (N)EXPTIME-полные задачи
(FaCT, DLP, Racer)
– понимание связей с модальными логиками и разрешимыми фрагментами логики
первого порядка


Последние результаты

• Зрелые реализации (например, FaCT++, RacerPro, Pellet, KAON2, CEL )

• Новые задачи логического анализа (ответ на запросы, поиск объяснений, поддержка
версий)

• Полиномиальная разрешимость некоторых ДЛ (EL, DL-Lite)

• Базы данных

– доступ к данным с использование онтологий
– непротиворечивость модели данных (ER, UML, и т.п.)
– интеграция схем

• Онтологии и Семантическая Паутина

– методологии дизайна, поддержки, интеграции онтологий
– логический анализ и разметка на основе онтологий (метаданные)
– поиск и описание сервисов


Дескрипционная логика EL:
терминологическая часть

База знаний (KB)

TBox (терминология, схема)

Система анализа

Интерфейс
Man ≡ Human ⊓ Male
HappyFather ≡ Man ⊓ ∃hasChild
...

ABox (assertion box, данные)

john: Man
(john, mary): hasChild
...

Синтаксис EL

• Язык EL концептов (классов):
– имена концептов A0 , A1 , ... (e.g., Person, Female, ...)

– имена ролей r0 , r1 , ... (e.g., hasChild, loves, ...)

– концепт ⊤ (иногда называют ‘thing” или “вещь”)
– операция ⊓ (пересечение, конъюнкция, или просто “и”).
– квантор ∃ (отверждение о существовании).

Простейшая дескрипционная логика


Синтаксис EL

• Язык EL концептов (классов):
– имена концептов A0 , A1 , ... (e.g., Person, Female, ...)

– имена ролей r0 , r1 , ... (e.g., hasChild, loves, ...)

– концепт ⊤ (иногда называют ‘thing” или “вещь”)
– операция ⊓ (пересечение, конъюнкция, или просто “и”).
– квантор ∃ (отверждение о существовании).

Простейшая дескрипционная логика

• Множество EL концептов определяется индуктивно:
– все имена концептов — EL концепты
– ⊤ является EL-концептом
– Если C и D являются EL-концептами, а r — имя роли, то

(C ⊓ D), ∃r.C

являются EL-концептами

Примеры

• Person ⊓ Female (женщина),

• Person ⊓ ∃hasChild.Person (человек, у которого есть ребенок),

• Person ⊓∃hasChild.Person ⊓∃hasParent.Person (человек, у которого есть ребенок
и родитель),

• Person ⊓ ∃hasChild.(Person ⊓ Female),

• Person ⊓ ∃hasChild.Person ⊓ Female,

• Person ⊓ ∃hasChild.⊤,

• Person ⊓ ∃hasChild.∃hasChild.⊤.


Определения в EL

Если A имя концепта, а C — EL-концепт, то

• A ≡ C — определениеEL-концепта. C описывает необходимое и достаточное
условие, чтобы объект принадлежал классу A. “A эквивалентен C ”.

• A ⊑ C — примитивное определение EL-концепта. C описывает необходимое
условие, чтобы объект принадлежал классу A. “A поглощен C ”.

Примеры:

• Father = Person ⊓ Male ⊓ ∃hasChild.⊤.

• Student = Person ⊓ ∃is_registered_at.University.

• Father ⊑ Person.

• Father ⊑ ∃hasChild.⊤.


EL-терминология (TBox)

EL терминология T это конечное множество определения вида

A ≡ C, A ⊑ C

таких что никакое имя концепта не определяется более одного раза.

Таким образом, в терминологиях не бывает одновременно, например,

• University ≡ Institution ⊓ ∃grants.academicdegree

• University ≡ Institution ⊓ ∃supplies.higher_education


EL-терминология (TBox)

EL терминология T это конечное множество определения вида

A ≡ C, A ⊑ C

таких что никакое имя концепта не определяется более одного раза.

Таким образом, в терминологиях не бывает одновременно, например,

• University ≡ Institution ⊓ ∃grants.academicdegree

• University ≡ Institution ⊓ ∃supplies.higher_education

Циклические определения допускаются

Human_being ≡ ∃has_parent.Human_being


Ациклические терминологии

Ациклическая EL-терминология T это EL-терминология в которой нет (явных или
неявных) циклических определений.


Ациклические терминологии

Ациклическая EL-терминология T это EL-терминология в которой нет (явных или
неявных) циклических определений.

T — терминология

• Определим отношение ≺T на парах имен концептов: A ≺T B т. и т.т., когда в T
найдется
A≡C или A⊑C т.ч. B входит в C

• Терминология T ациклична если транзитивное замыкание ≺T иррефлексивно.


Пример: SNOMED CT

• Терминология медицинских терминов насчитывающая около 400 000 определений
(400 000 имен концептов в 60 имен ролей)

• Ацикличная EL-терминология (почти)

• Принадлежит (и поддерживается) некоммерческой организации IHSTDO (International
Health terminology Standards Development Organisation).

• IHSTDO имеет 9 членов (бесплатное членство для 49 развивающихся стран).

• Цель: обеспечение обмена информацией между медиками, исследователями и пациентами
по всему миру.


Фрагмент SNOMED CT

EntireFemur ⊑ StructureOfFemur

FemurPart ⊑ StructureOfFemur ⊓

∃part_of.EntireFemur

BoneStructureOfDistalFemur ⊑ FemurPart

EntireDistalFemur ⊑ BoneStructureOfDistalFemur

DistalFemurPart ⊑ BoneStructureOfDistalFemur ⊓

∃part_of.EntireDistalFemur

StructureofDistalEpiphysisOfFemur ⊑ DistalFemurPart

EntireDistalEpiphysisOfFemur ⊑ StructureOfDistalEpiphysisOfFemur


Импликация EL-концептов (concept inclusion, CI)

C и D — произвольные EL концепты.

• C ⊑ D называется импликацией EL концептов. Означает, что каждый C является
D . Также говорят, что C поглощен D или что D поглощает C . Иногда говорят, что
C включается в D .

• C ≡ D является формой записи двух импликаций, C ⊑ D и D ⊑ C . “C и D
эквивалентны.

Например:

• Disease ⊓ ∃has_location.Heart ⊑ NeedsTreatment

• ∃student_of.ComputerScience ⊑ Human_being⊓∃knows.Programming_Language


EL-TBox

EL-TBox это конечное множество импликаций EL-концептов вида C ⊑ D (также используем
сокращение C ≡ D ).
Пример:

Pericardium ⊑ Tissue ⊓ ∃cont_in.Heart

Pericarditis ⊑ Inflammation ⊓ ∃has_loc.Pericardium

Inflammation ⊑ Disease ⊓ ∃acts_on.Tissue

Disease ⊓ ∃has_loc.∃cont_in.Heart ⊑ Heartdisease ⊓ NeedsTreatment


EL-TBox

EL-TBox это конечное множество импликаций EL-концептов вида C ⊑ D (также используем
сокращение C ≡ D ).
Пример:





Т.о.,
ациклические терминологии ⇒ терминологии ⇒ TBox


Как используют TBox?

Иерархия концептов задаваемая T определяется как

{A ⊑ B | A, B имена концептов в T и T влечет A ⊑ B}
например, рассмотренный фрагмент SNOMED CT влечет
EntireDistalEpiphysisOfFemur

⊑

StructureOfDistalEpiphysisOfFemur

⊑

DistalFemurPart

⊑

BoneStructureOfDistalFemur

⊑

FemurPart


Стандартное использование SNOMED CT на основе иерархии

• SNOMED CT используется, чтобы породить иерархию медицинских терминов. Каждый
термин ассоциирован с числовым кодом и определением.

• Врачи используют иерархию чтобы

– порождать,

– обрабатывать, и

– хранить

электронные медицинские карточки пациента, содержащие диагноз, рекомендованное
лечение, назначенные лекарства, результаты исследований и т.п.


Семантика EL

• интерпретация это структура I = (∆I ·I ) в которой
,
– ∆I это носитель, домен (непустое множество)

– интерпретация ·I отображает:

* имя концепта A в AI , подмножество ∆I (AI ⊆ ∆I )
* имя роли r в бинарное отношение rI на ∆I (r I ⊆ ∆I × ∆I )

• Интерпретация CI произвольного концепта C i определяется индуктивно:

– (⊤)I = ∆I
– (C ⊓ D)I = C I ∩ D I
– (∃r.C)I = {x ∈ ∆I | существует y ∈ ∆I т.ч. (x, y) ∈ r I and y ∈ CI}


Пример

Пусть I = (∆I , ·I ), where

• ∆I = {a, b, c, d, e, f };

• PersonI = {a, b, c, d, f }; FemaleI = {a, b, c, e};

• hasChildI = {(a, b), (b, c), (d, e), (f, f )}.

Вычислить

• (Person ⊓ Female)I ,
• (Person ⊓ ∃hasChild.Person)I ,
• (Person ⊓ ∃hasChild.(Person ⊓ Female)I ,
• (Person ⊓ ∃hasChild.Person ⊓ Female)I ,
• (Person ⊓ ∃hasChild.⊤)I ,
• (Person ⊓ ∃hasChild.∃hasChild.⊤)I .


Интерпретация импликаций концептов

I интерпретация, C⊑D импликация концептов, и T — TBox.

• I |= C ⊑ D т. и т.т, когда C I ⊑ DI . Говорят, что

– I выполняет C⊑D или

– C⊑D истинна в I или

– I является моделью для C ⊑ D.

• I |= C ≡ D т. и т.т., когда C I = DI

• I |= T т. и т.т., когда I |= E ⊑ F для всех E⊑F в T.

– I выполняет T или

– I является моделью для T.


TBox и импликации концептов

T — TBox и C ⊑D — импликация концептов. T влечет C ⊑D т. и т.т., когда каждая
модель T является моделью C ⊑ D.

• T |= C ⊑ D или

• C ⊑T D .

Пример: пусть MED является следующим EL-TBox’ом





Можно убедится что Percarditis ⊑MED NeedsTreatment.


�ݺ�ߣ

20100925 ontology konev_lecture02

Recommended

More Related Content

Similar to 20100925 ontology konev_lecture02 (20)

More from Computer Science Club (20)

20100925 ontology konev_lecture02