TL;DR
This paper introduces a "closed terminology assumption" (CTA) for Description Logics (DLs) specifically for applications like system configuration. By assuming the terminology is fixed during problem-solving, they enable new "predictive concept recognition" inferences that help guide users and configuration engines by identifying necessary, optional, and impossible concepts for a partially specified system.
What Problem Does This Paper Address?
Traditional Description Logics (DLs) treat terminologies (the set of concepts and their relationships) as "open," meaning they are assumed to be incomplete and can evolve during knowledge engineering. However, in application domains like system configuration, the set of relevant concepts (e.g., types of computer systems and components) is often fixed once the configuration task begins. Applying DLs in these scenarios has historically not distinguished between the knowledge engineering phase (where the terminology is built) and the problem-solving phase (where it's used). This paper addresses the gap by proposing a "closed terminology assumption" (CTA) that is more appropriate for the problem-solving phase of configuration. CTA allows for more powerful inferences by assuming that all relevant concepts are defined and that any individual being configured will eventually be fully specified and match at least one concrete concept. This enables a more proactive and guiding approach to configuration.
Methods
The core innovation is the Closed Terminology Assumption (CTA). Unlike the standard Open Terminology Assumption (OTA), CTA posits that the terminology is fixed during problem-solving. This assumption is crucial for enabling predictive concept recognition.
Key techniques include:
- Distinguishing Abstract and Concrete Concepts: This distinction is formalized to define when an individual's description is "finished." Concrete concepts are those that can represent a complete and specific instance for the application's purpose (e.g., a specific CPU model), while abstract concepts are more general (e.g., CPU).
- Bijective Instantiation: A formal definition of how an individual "bijectively instantiates" a concept, meaning the individual's primitives and role restrictions perfectly match those of the concept. This is used to define "finished" individuals.
- CTA-Consistency: A new inference relation that determines if two concepts or a concept and an individual are compatible under CTA. This is defined recursively and involves checking primitives, role restrictions, and cardinality constraints.
- Terminology Augmentation: A pre-processing step where auxiliary concepts representing conjunctions of existing concepts are added to the terminology. This simplifies indirect CTA-consistency checks to subsumption checks.
- Recognition via Terminology Partitioning: The core application of CTA. The taxonomy is partitioned into "necessary," "optional," and "impossible" concepts with respect to a partially specified individual. This is maintained dynamically as the individual is updated.
- Constraint Derivation: Using the least common subsumer (LCS) of optional concepts to derive new constraints that can be added to the individual's description, further guiding the configuration process.
Datasets
Not discussed in the paper. The paper uses a sample configuration terminology for illustration, which is presented in Figure 2.
Key Insights and Ideas
- The "Closed World" for Concepts Matters: Treating the terminology as fixed during problem-solving (CTA) unlocks significant reasoning power beyond what's possible with an "open" terminology (OTA). This is particularly relevant for domains with well-defined sets of options, like configuration.
- Predictive Power from Fixed Knowledge: By assuming the knowledge base is complete for the task at hand, the system can predict what must or cannot be true for a partially specified individual, rather than just what is true.
- Guiding the User Proactively: The "necessary," "optional," "impossible" partitioning of concepts provides a clear roadmap for users, highlighting valid choices and implicitly ruling out invalid ones. This is more helpful than simply checking for consistency after a choice is made.
- Formalizing "Finished": The distinction between abstract and concrete concepts, combined with bijective instantiation, provides a formal way to define when a configuration is complete and specific enough.
- CTA-Consistency as a Foundation: The novel CTA-consistency relation is the bedrock for many of the paper's inferences, allowing for robust reasoning about compatibility under the closed terminology assumption.
Key Results
The paper presents a methodology and associated algorithms for predictive concept recognition and constraint derivation in DLs under CTA. While specific quantitative results (e.g., accuracy metrics, speedups) are not detailed, the paper emphasizes the qualitative benefits:
- Efficiently tracking valid system types: The system can quickly identify which types of systems are still possible given current choices.
- Inferring implicit constraints: The LCS of optional concepts can reveal constraints not explicitly stated by the user, guiding them towards valid configurations.
- Improved user guidance: The partitioning of concepts into necessary, optional, and impossible provides a clear and actionable state for the user and configuration engine.
- Demonstrated feasibility: The methodology is implemented in the K-REP DL system and tested on a realistic configuration terminology.
Limitations and Future Work
- Monotonic Update Assumption: The methodology relies on a "monotonic update assumption," meaning individuals are updated by adding constraints or concepts. If non-monotonic updates occur, the system may need to re-expand the optional region, which is acknowledged but not fully elaborated on.
- Disjunction and Negation: The current implementation (K-REP) does not support disjunction or negation operators in DLs. The authors note it's unclear how efficiently these can be incorporated, but point to CLASSIC's success without them as a positive sign.
- Formal Semantics for CTA: The authors mention investigating a formal semantics for CTA reasoning based on circumscription, drawing an analogy to event hierarchies in plan recognition.
- Domain Independence: While the methodology is presented in the context of configuration, the authors believe it is domain-independent and could be applied to other areas.
- Performance Details: While performance is stated to be "easily fast enough for interactive applications" on a sample terminology, detailed empirical results are deferred to an appendix (Weida 1996).
Summary updated