Daily Arxiv

전 세계에서 발간되는 인공지능 관련 논문을 정리하는 페이지 입니다.
본 페이지는 Google Gemini를 활용해 요약 정리하며, 비영리로 운영 됩니다.
논문에 대한 저작권은 저자 및 해당 기관에 있으며, 공유 시 출처만 명기하면 됩니다.

Fitting Description Logic Ontologies to ABox and Query Examples

Created by
  • Haebom

저자

Maurice Funk, Marvin Grosser, Carsten Lutz

개요

본 논문은 온톨로지 매개 질의에서 영감을 받은 피팅 문제를 연구합니다. 양성 및 음성 예제의 집합 $(\mathcal{A},q)$ (여기서 $\mathcal{A}$는 ABox이고 $q$는 부울 쿼리임)이 주어지면, 모든 양성 예제에 대해 $\mathcal{A} \cup \mathcal{O} \vDash q$ 를 만족하고 모든 음성 예제에 대해 $\mathcal{A} \cup \mathcal{O}\not\vDash q$ 를 만족하는 온톨로지 $\mathcal{O}$ 를 찾는 문제입니다. 온톨로지 언어로는 $\mathcal{ALC}$ 와 $\mathcal{ALCI}$ 를, 질의 언어로는 원자 쿼리(AQs), 결합 쿼리(CQs), 그리고 그들의 합집합(UCQs)을 고려합니다. 결과적으로 발생하는 모든 피팅 문제에 대해 효과적인 특성화를 제공하고 피팅 온톨로지가 존재하는지 결정하는 계산 복잡도를 결정합니다. 이 문제는 AQs와 전체 CQs에 대해 ${\scriptsize CO}NP$ 이고, CQs와 UCQs에 대해 $2E{\scriptsize XP}T{\scriptsize IME}$-완전한 것으로 나타났습니다. 이러한 결과는 $\mathcal{ALC}$ 와 $\mathcal{ALCI}$ 모두에 대해 성립합니다.

시사점, 한계점

시사점: $\mathcal{ALC}$ 와 $\mathcal{ALCI}$ 온톨로지 언어와 다양한 질의 언어(AQs, CQs, UCQs) 하에서 온톨로지 피팅 문제의 계산 복잡도를 명확히 규명했습니다. 이는 온톨로지 엔지니어링 및 지식 표현 분야에 중요한 이론적 기여를 합니다.
한계점: 실제 응용에 적용 가능한 효율적인 알고리즘 개발에 대한 논의는 부족합니다. $2E{\scriptsize XP}T{\scriptsize IME}$-완전성 결과는 실제 문제 해결에 어려움을 시사합니다. 다른 온톨로지 언어나 질의 언어에 대한 확장 연구가 필요합니다.
👍