Making Decisions over Contextual Ontologies

Erman Acar, Rafael Peñaloza, Livia PredoiuDescription Logics 2019 · OpenReview

Abstract

Traditional Description Logics (DLs) excel at structured knowledge representation but often lack the capacity for active decision-making under uncertainty. This paper introduces ID-$\mathcal{EL}$, a framework that integrates the lightweight description logic $\mathcal{EL}$ with Influence Diagrams (IDs). By moving beyond passive probabilistic reasoning, ID-$\mathcal{EL}$ enables agents to make strategic choices that minimize expected costs within ontologically-defined contexts.

Introduction

Classical DLs are typically "passive"—they can infer the likelihood of a conclusion based on probabilistic dependencies (as seen in Bayesian DLs like $B\mathcal{EL}$), but they do not provide a mechanism for an agent to act. Real-world applications, such as medical diagnosis or autonomous systems, require agents to not only observe the world but also to make decisions that influence outcomes. The ID-$\mathcal{EL}$ framework addresses this by incorporating observations and contextual reasoning into a decision-theoretic model.

Methodology: The ID-$\mathcal{EL}$ Framework

The authors propose a hybrid formalism that leverages the strengths of two distinct areas: the $\mathcal{EL}$ Description Logic and Influence Diagrams (IDs). $\mathcal{EL}$ is chosen for its computational efficiency in large-scale ontologies, while IDs provide the graphical structure for decision-making.

An example of an Influence Diagram (ID) structure, incorporating chance nodes (circles), a decision node (square), and a cost node (diamond).

In this framework, every axiom in the ontology is tagged with a "context"—a propositional formula. An axiom is considered part of the knowledge base only if its context evaluates to true. This allows for reasoning that is sensitive to specific environmental conditions. The framework allows for calculating the expected cost of a strategy given an ontological observation, such as observing that one concept is a sub-concept of another.

Key Innovations

Strategy-Parameterized Models

Because an agent's choices affect the probability distribution of world states, the authors define models that are explicitly tied to a "strategy"—a set of local decision rules. This allows for the calculation of Conditional Expected Cost, where an agent updates its beliefs based on ontological observations before choosing a strategy.

Illustration of multiple interpretations consistent with different contexts and strategies.

Optimism vs. Pessimism

A single strategy might be consistent with multiple ontological models. To handle this ambiguity, the framework introduces "optimistic" and "pessimistic" expected costs, allowing agents to plan for the best-case or worst-case interpretations of their knowledge.

Complexity and Results

A significant finding of the paper is that the integration of $\mathcal{EL}$ ontologies does not increase the theoretical complexity of the decision problem. Finding an optimal strategy in ID-$\mathcal{EL}$ remains PSpace-complete, matching the complexity of standard Influence Diagrams.

Key results include:

  • Formal Semantics: A rigorous definition linking logical axioms to decision-theoretic costs.
  • Dominant Strategies: The identification of strategies that remain optimal across all possible models of the knowledge base. Finding these for pure strategies is also shown to be PSpace-complete.
  • Polynomial Space Computation: Proof that optimistic and pessimistic costs can be computed in polynomial space relative to the number of contextual variables, despite the exponential number of possible valuations.

As a theoretical work, the paper focuses on formal semantics and complexity analysis rather than empirical evaluation on specific datasets.

Conclusion

ID-$\mathcal{EL}$ represents a significant step toward bridging the gap between structured knowledge representation and active decision theory. By treating ontologies as sources of evidence and contexts for action, the framework provides a robust foundation for intelligent agents operating in uncertain environments. Future work will likely focus on extending these results to more expressive logics and developing practical, large-scale implementation heuristics.

Summary updated

BibTeX
@inproceedings{acar2019making,
  author = {Erman Acar and Rafael Peñaloza and Livia Predoiu},
  title = {{Making Decisions over Contextual Ontologies}},
  booktitle = {Description Logics},
  year = {2019},
  url = {https://openreview.net/forum?id=AbOQ8k_RaV},
}
Figure