Computing Least Common Subsumers in Description Logics

William W. Cohen, Alexander Borgida, Haym HirshAAAI 1992

Abstract

Description Logics (DLs) are typically used for deductive reasoning tasks like subsumption. However, inductive tasks such as learning from examples or simplifying knowledge bases require a generalization operation. This paper introduces the Least Common Subsumer (LCS), the most specific concept that generalizes a set of given descriptions. We explore the formal properties of the LCS and provide algorithms for its computation across various DL constructors, highlighting the relationship between structural subsumption and tractable generalization.

Introduction: The Need for Generalization

In the field of Description Logics, the primary reasoning task is subsumption: determining if one concept is more general than another (e.g., "Is every Man a Person?"). While deduction is well-studied, many applications require generalization. For instance, given two specific examples—"a person who sings and plays guitar" and "a person who sings and plays piano"—one might want to find the most specific category that includes both: "a person who sings and plays a musical instrument."

This "greatest common denominator" is formally defined as the Least Common Subsumer (LCS). The LCS is essential for inductive learning (deriving rules from examples) and knowledge-base "vivification" (approximating complex disjunctive information with simpler conjunctive forms).

Methodology: Computing the LCS

The authors demonstrate that the LCS can be computed efficiently for logics that rely on structural subsumption. In these systems, descriptions are normalized into a standard tree-like structure, allowing for recursive comparison.

Modular Algorithm Design

A key contribution is the modular approach to LCS computation. If a logic's individual constructors (like ALL, AT-LEAST, or PRIM) form a join-semilattice, their LCS algorithms can be combined mechanically into a complete algorithm for the entire logic.

Table of constructors and their corresponding upper bound (LCS) operations.

As shown in the table above, for each constructor $k$, the LCS operation $\sqcup_k$ is defined based on its domain and partial order. For example, the LCS of two AT-LEAST constraints is the minimum of their numeric values, while for PRIM (primitive concepts), it is the concept itself if they match, or the top concept THING if they differ.

Equality Graphs and the SAME-AS Challenge

For logics involving attribute equalities (the SAME-AS constructor), the authors utilize graph theory. Descriptions are represented as rooted directed graphs called Equality Graphs (EQGs). The LCS of two EQGs is computed using a cross-product construction, analogous to finding the intersection of two finite automata.

Visual representation of two descriptions (D1, D2) and their computed Least Common Subsumer (LCS).

Figure 3 illustrates this process. D1 represents a student loan applicant whose cosigner is their father. D2 represents a house buyer loan applicant whose cosigner is also their father. Their LCS generalizes these to a generic loan applicant whose cosigner is their father, dropping the specific "Student" or "HouseBuyer" roles while preserving the shared structural relationship.

Key Insights and Results

The paper reveals several non-intuitive properties of the LCS operation:

  • Complexity Independence: The computational difficulty of finding the LCS is not strictly tied to the difficulty of checking subsumption. There are cases where subsumption is easy but the LCS is exponentially large, and vice versa.
  • Structural Advantage: "Structural" subsumption, though sometimes viewed as less expressive than full first-order logic, is precisely what enables modular and tractable LCS computation.
  • Exponential Growth: For logics containing the SAME-AS constructor, while the LCS of two descriptions can be found in polynomial time, the size of the LCS for a large set of descriptions can grow exponentially relative to the input.

Conclusion and Future Work

This work provides a formal foundation for generalization in Description Logics. While it establishes tractable algorithms for languages like CLASSIC, challenges remain. Current methods do not yet handle recursive definitions, role hierarchies, or complex role constructors like inversion. Future research will focus on extending these techniques to more expressive logics and exploring their practical application in large-scale inductive learning systems.

Summary updated

BibTeX
@inproceedings{cohen1992computing,
  author = {William W. Cohen and Alexander Borgida and Haym Hirsh},
  title = {{Computing Least Common Subsumers in Description Logics}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1992},
}

Loading related content...

Figure