Heuristic Ranking in Tightly Coupled Probabilistic Description Logics

Thomas Lukasiewicz, Maria Vanina Martinez, Giorgio Orsi, Gerardo I. Simari
Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, PMLR R10:552-561, 2012.

Abstract

The Semantic Web effort has steadily been gaining traction in the recent years. In particular,Web search companies are recently realizing that their products need to evolve towards having richer semantic search capabilities. Description logics (DLs) have been adopted as the formal underpinnings for Semantic Web languages used in describing ontologies. Reasoning under uncertainty has recently taken a leading role in this arena, given the nature of data found on theWeb. In this paper, we present a probabilistic extension of the DL EL++ (which underlies the OWL2 EL profile) using Markov logic networks (MLNs) as probabilistic semantics. This extension is tightly coupled, meaning that probabilistic annotations in formulas can refer to objects in the ontology. We show that, even though the tightly coupled nature of our language means that many basic operations are data-intractable, we can leverage a sublanguage of MLNs that allows to rank the atomic consequences of an ontology relative to their probability values (called ranking queries) even when these values are not fully computed. We present an anytime algorithm to answer ranking queries, and provide an upper bound on the error that it incurs, as well as a criterion to decide when results are guaranteed to be correct.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR10-lukasiewicz12a, title = {Heuristic Ranking in Tightly Coupled Probabilistic Description Logics}, author = {Lukasiewicz, Thomas and Martinez, Maria Vanina and Orsi, Giorgio and Simari, Gerardo I.}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {552--561}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/lukasiewicz12a/lukasiewicz12a.pdf}, url = {https://proceedings.mlr.press/r10/lukasiewicz12a.html}, abstract = {The Semantic Web effort has steadily been gaining traction in the recent years. In particular,Web search companies are recently realizing that their products need to evolve towards having richer semantic search capabilities. Description logics (DLs) have been adopted as the formal underpinnings for Semantic Web languages used in describing ontologies. Reasoning under uncertainty has recently taken a leading role in this arena, given the nature of data found on theWeb. In this paper, we present a probabilistic extension of the DL EL++ (which underlies the OWL2 EL profile) using Markov logic networks (MLNs) as probabilistic semantics. This extension is tightly coupled, meaning that probabilistic annotations in formulas can refer to objects in the ontology. We show that, even though the tightly coupled nature of our language means that many basic operations are data-intractable, we can leverage a sublanguage of MLNs that allows to rank the atomic consequences of an ontology relative to their probability values (called ranking queries) even when these values are not fully computed. We present an anytime algorithm to answer ranking queries, and provide an upper bound on the error that it incurs, as well as a criterion to decide when results are guaranteed to be correct.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Heuristic Ranking in Tightly Coupled Probabilistic Description Logics %A Thomas Lukasiewicz %A Maria Vanina Martinez %A Giorgio Orsi %A Gerardo I. Simari %B Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2012 %E Nando de Freitas %E Kevin Murphy %F pmlr-vR10-lukasiewicz12a %I PMLR %P 552--561 %U https://proceedings.mlr.press/r10/lukasiewicz12a.html %V R10 %X The Semantic Web effort has steadily been gaining traction in the recent years. In particular,Web search companies are recently realizing that their products need to evolve towards having richer semantic search capabilities. Description logics (DLs) have been adopted as the formal underpinnings for Semantic Web languages used in describing ontologies. Reasoning under uncertainty has recently taken a leading role in this arena, given the nature of data found on theWeb. In this paper, we present a probabilistic extension of the DL EL++ (which underlies the OWL2 EL profile) using Markov logic networks (MLNs) as probabilistic semantics. This extension is tightly coupled, meaning that probabilistic annotations in formulas can refer to objects in the ontology. We show that, even though the tightly coupled nature of our language means that many basic operations are data-intractable, we can leverage a sublanguage of MLNs that allows to rank the atomic consequences of an ontology relative to their probability values (called ranking queries) even when these values are not fully computed. We present an anytime algorithm to answer ranking queries, and provide an upper bound on the error that it incurs, as well as a criterion to decide when results are guaranteed to be correct. %Z Reissued by PMLR on 04 October 2026.
APA
Lukasiewicz, T., Martinez, M.V., Orsi, G. & Simari, G.I.. (2012). Heuristic Ranking in Tightly Coupled Probabilistic Description Logics. Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R10:552-561 Available from https://proceedings.mlr.press/r10/lukasiewicz12a.html. Reissued by PMLR on 04 October 2026.

Related Material