Abstract
This paper presents a unified algorithm for automatically inducing probabilistic ontologies from relational data. By integrating Inductive Logic Programming (ILP) with probabilistic reasoning, the proposed approach simultaneously learns deterministic concept definitions and probabilistic assessments. Evaluation on standard ILP benchmarks and real-world datasets like YAGO demonstrates that the method matches the performance of specialized deterministic tools while uncovering nuanced probabilistic relationships in complex data, providing a more flexible framework for modeling uncertainty in the Semantic Web.
Introduction
Description Logics (DLs) serve as the formal foundation for the Semantic Web, enabling structured knowledge representation. However, classical DLs are inherently deterministic and struggle to represent "gray areas"—situations where rules are not absolute. While Probabilistic Description Logics (PDLs), such as $cr\mathcal{ALC}$, were developed to address this, they face a significant practical hurdle: the manual definition of probability values for thousands of complex relationships is labor-intensive and error-prone.
Previous research has largely addressed this problem in isolation, focusing either on learning logical structures ("sentences") or probability values ("assessments"). This work bridges that gap by introducing a hybrid algorithm capable of learning both components simultaneously from raw relational data.
Methodology
The authors propose a unified algorithm that blends traditional ILP techniques with probabilistic modeling. The process is structured around a search-tree approach:
- Refinement & Search: Utilizing a refinement operator from the DL-Learner system, the algorithm begins with general concepts and iteratively generates more specific candidate definitions.
- Probabilistic Scoring: Instead of binary classification, the algorithm employs a Probabilistic Score Function. This treats the relationship between a candidate definition and an example as a random variable, allowing for a more nuanced evaluation of rule coverage.
- Fallback Strategy: The system initially seeks perfect deterministic definitions. If candidate scores fall below a predefined threshold, the algorithm triggers a Probabilistic Inclusion procedure, recognizing that a perfect rule may not exist.
- TAN Classifiers: To model probabilistic inclusions, the algorithm utilizes Tree Augmented Naive Bayes (TAN) networks. It constructs a graph of candidate concepts, identifies a maximum weight spanning tree to model dependencies, and calculates conditional probabilities.
Experimental Evaluation
The approach was evaluated across two distinct environments:
- Standard ILP Benchmarks: Five classic datasets (trains, arches, moral, poker(pair), and poker(straight)) were used to verify that the probabilistic approach maintains parity with purely deterministic tools.
- YAGO Knowledge Base: To test real-world applicability, the authors extracted subsets from YAGO concerning Scientists (2,008 individuals) and Film Directors (5,589 individuals), focusing on discovering patterns in messy, large-scale data.
Results and Discussion
In the benchmark tests, the combined approach achieved 100% accuracy across all five datasets, matching the performance of the specialized DL-Learner system. As shown in the comparison below, while the accuracy is identical, the combined approach occasionally produces slightly more complex definitions (longer lengths) as it balances deterministic and probabilistic logic.
On the YAGO dataset, the algorithm successfully induced complex $cr\mathcal{ALC}$ terminologies that captured nuanced real-world probabilities. For instance, it identified that the probability of a scientist being "influential" given certain academic markers was approximately 0.85. These probabilistic inclusions significantly improved inference; for example, adding evidence of a person's "influences" could update their probability of being a scientist from 50% to 65%.
Conclusion
This research demonstrates that uncertainty in ontologies often arises from missing information, and modeling these gaps probabilistically is more effective than discarding imperfect rules. By treating deterministic rules as a special case of probabilistic ones (where $P=1.0$), the authors provide a robust, unified pipeline for ontology induction. Future work will focus on improving scalability for million-entity datasets and refining scoring functions to favor more concise definitions, adhering to the principle of Occam's Razor.
Summary updated