Introduction
The Semantic Web relies on Description Logics (DL) to provide a formal structure for knowledge. However, standard DLs are inherently deterministic, struggling to represent the uncertainty and probabilistic relationships common in real-world data. While various Probabilistic Description Logics (PDLs) have been proposed, they often face two significant challenges: semantics clashes and the handling of nominals.
Traditional PDLs frequently utilize "domain-based" semantics, which focus on statistical information about a population. This leads to the "direct inference" problem: if a general rule states that 30% of birds fly, it is logically ambiguous how this applies to a specific individual like "Tweety." Furthermore, many practical ontologies use nominals—references to specific individuals within concept definitions (e.g., defining "Red Wine" as a wine whose color is the specific individual red). Nominals bridge general concepts and specific data, often leading to computational complexity.
This paper extends the probabilistic description logic $cr\mathcal{ALC}$ (Credal $\mathcal{ALC}$) to support nominals. By adopting an interpretation-based semantics, the authors provide a framework capable of handling probabilistic queries over real-world ontologies while avoiding the logical paradoxes of domain-based approaches.
Methodology
The authors' approach centers on translating an ontology into a Relational Credal Network, a type of Bayesian network where probabilities may be expressed as intervals.
Interpretation-based Semantics
Unlike domain-based approaches that count individuals in a single world, interpretation-based semantics consider the probability over all possible interpretations (possible worlds). This allows for a consistent treatment of both general terminological knowledge (TBox) and assertions about specific individuals (ABox). In this framework, a query like $P(Fly(Tweety))$ is well-defined and does not conflict with population-level statistics.
Handling Nominals
Nominals are integrated by allowing them to appear in role restrictions, such as $\exists hasColor.\{red\}$. To maintain computational tractability, the authors employ a grounding strategy that only expands the probabilistic network for the specific nominals mentioned in the roles. This avoids the need for general quantification over the entire domain, preventing the "computational explosion" typically associated with nominals in DL reasoning.
Inference Algorithms
The framework supports both exact and approximate inference. For smaller or more structured ontologies, exact inference is feasible. For larger, more complex models where relationships between individuals create dense networks, the authors utilize the L2U algorithm, an approximate inference method designed for credal networks.
Experimental Evaluation
The proposed framework was evaluated using two distinct ontologies:
- The Wine Ontology: A complex, real-world ontology that uses nominals extensively to describe properties like color and region.
- The Kangaroo Ontology: A smaller, synthetic ontology designed to test the system's handling of inter-individual relationships (e.g.,
hasChild), which typically challenge scalability.
The evaluation focused on the feasibility of grounding these ontologies into credal networks and the performance of inference algorithms as the domain size increased.
Results and Discussion
The experiments yielded several key insights:
- Scalability and Relationship Types: The study revealed that scalability is driven more by the nature of relationships than the number of individuals. In the Wine ontology, nominals mostly describe properties (attributes) rather than complex links between individuals. Consequently, the grounded network size remained manageable regardless of the domain size, allowing for exact inference.
- Quadratic Growth in Inter-individual Links: In contrast, the Kangaroo ontology, which features links between individuals, saw the network size grow quadratically ($|D|^2$) with the domain size. While exact inference became impossible as the domain grew from 2 to 50 individuals, the L2U approximate algorithm provided stable probability bounds with reasonable computational overhead.
- Direct Inference Resolution: The interpretation-based semantics successfully sidestepped the philosophical hurdles of direct inference, allowing for valid probabilistic queries about specific individuals within the grounded network.
Conclusion
This work represents a significant step toward a probabilistic version of SHOIN, the logic underlying the Web Ontology Language (OWL). By extending $cr\mathcal{ALC}$ with nominals and utilizing interpretation-based semantics, the authors have created a scalable framework for reasoning under uncertainty in the Semantic Web.
Future work will aim to relax current restrictions, such as the "unique names assumption" and "domain closure," and expand support for more general nominal constructs (e.g., sets of individuals). These advancements will further bridge the gap between formal logic and the probabilistic nature of real-world knowledge.
Summary updated