Abstract
As the Semantic Web evolves, the ability to handle uncertainty within formal knowledge representations has become a critical requirement. Traditional Description Logics (DLs), while providing the logical foundation for the Web Ontology Language (OWL), are inherently deterministic and struggle with the "messiness" of real-world data. This paper presents a comprehensive framework for integrating uncertainty into the Semantic Web by combining DLs with probabilistic "distribution semantics." We introduce a suite of tools—TRILL for efficient reasoning and EDGE/LEAP for automated learning—that allow systems to infer facts from uncertain data and discover the underlying probabilistic structure of a domain.
Introduction
Description Logics (DLs) are the formal backbone of modern knowledge representation, yet their standard implementations are strictly binary: a statement is either true or false. In reality, data is often incomplete, contradictory, or inherently probabilistic. To bridge this gap, researchers have sought to create systems capable of representing uncertainty (e.g., "There is a 60% chance that a Cat is a Pet"), performing efficient inference to calculate query probabilities, and learning these logical rules and probabilities directly from data.
This paper details the development of the DISPONTE semantics and the associated TRILL, EDGE, and LEAP systems, which together provide a robust pipeline for probabilistic reasoning and machine learning within the DL framework.
The DISPONTE Framework and TRILL Reasoner
The foundation of this work is the DISPONTE semantics, which applies "distribution semantics" to DLs. Under this approach, a probabilistic knowledge base is treated as a distribution over a set of possible "worlds." Each probabilistic axiom defines the likelihood of a world existing in which that axiom holds true.
Declarative Reasoning with TRILL
To perform inference within this framework, we developed TRILL (Tableau Reasoner for descrIption Logics in Prolog). While many DL reasoners are implemented in imperative languages like Java or C++, TRILL leverages the declarative nature of Prolog. Prolog’s native backtracking and search capabilities are naturally suited for the non-deterministic nature of tableau algorithms—the rules used to decompose complex logical expressions into simpler components.
To manage the computational complexity of probabilistic inference, TRILL utilizes Binary Decision Diagrams (BDDs). By translating logical explanations into BDDs, the system avoids exponential complexity, allowing the final probability of a query to be computed in time linear to the size of the diagram. An optimized version, TRILL$^P$, further enhances performance by using "pinpointing formulas" to bypass the need for translating explanations into Disjunctive Normal Form (DNF).
Learning Probabilistic Knowledge
Beyond reasoning, the framework addresses the challenge of knowledge acquisition through two primary learning systems: EDGE and LEAP.
Parameter Learning with EDGE
The EDGE algorithm focuses on parameter learning. Using an Expectation-Maximization (EM) approach, EDGE analyzes datasets of instances and non-instances to automatically determine the probability values of existing axioms. This reduces the reliance on human experts to manually assign weights to logical rules.
Structure Learning with LEAP
LEAP (Learning Probabilistic Subsumption Axioms) represents a more advanced step toward automated ontology engineering. It combines the parameter learning of EDGE with CELOE (Class Expression Learning for Ontology Engineering) to perform structure learning. LEAP does not just refine probabilities; it discovers new logical rules and their associated probabilities simultaneously. This capability moves the framework toward a "neuro-symbolic" paradigm, where the system autonomously discovers the logic it uses to reason.
Evaluation and Results
The proposed systems were evaluated against existing benchmarks and baselines, such as the Gold-miner system, which extracts association rules from knowledge bases using SPARQL queries. Key results include:
- Performance Parity: TRILL demonstrated performance competitive with state-of-the-art reasoners like BUNDLE, proving that a declarative Prolog-based approach is viable for large-scale Semantic Web applications.
- Superior Accuracy: The EDGE algorithm consistently learned more accurate probability parameters than the Gold-miner baseline, particularly in complex domains.
- Automated Refinement: LEAP successfully automated the process of building and refining probabilistic subsumption axioms, significantly reducing the manual labor required for ontology maintenance.
Conclusion and Future Work
The integration of distribution semantics with Description Logics provides a powerful toolset for managing uncertainty in the Semantic Web. While the TRILL/EDGE/LEAP framework shows great promise, scalability remains a primary challenge as datasets grow toward "Big Data" proportions.
Future research is focused on parallelization to overcome these bottlenecks. Current efforts include adapting the EDGE algorithm to run on cloud computing clusters using the MPI (Message Passing Interface) protocol and developing distributed BDD construction methods. By dividing the workload across multiple processors and optimizing task scheduling, we aim to enable probabilistic reasoning and learning at a truly global scale.
Summary updated