DevelopinThe Bayesian Description Logic BALC

Botha, Leonard

DevelopinThe Bayesian Description Logic BALC

Master Thesis

2018

Publisher

University of Cape Town

Department

Department of Computer Science

Faculty

Faculty of Science

Abstract

Description Logics (DLs) that support uncertainty are not as well studied as their crisp alternatives. This limits their application in many real world domains, which often require reasoning about uncertain or contradictory information. In this thesis we present the Bayesian Description Logic BALC, which takes existing work on Bayesian Description Logics and applies it to the classical Description Logic ALC. We define five reasoning problems for BALC; two versions of concept satisfiability (called total and partial respectively), knowledge base consistency, three subsumption problems (positive subsumption, p-subsumption, exact subsumption), instance checking, and the most likely context problem. Consistency, satisfiability, and instance checking have not previously been studied in the context of contextual Bayesian DLs and as such this is new work. We then go on to provide algorithms that solve all of these reasoning problems, with the exception of the most likely context problem. We found that all reasoning problems in BALC are in the same complexity class as their classical variants, provided that the size of the Bayesian Network is included in the size of the knowledge base. That is, all reasoning problems mentioned above (excluding most likely context) are exponential in the size of the knowledge base and the size of the Bayesian Network.

Keywords

computer science

Reference:

Collections

Masters

Full item page