The Web Ontology Language has not been designed for representing abductive inference, which is often required for applications such as medical disease diagnosis. As a consequence, existing OWL ontologies have limited ability to encode knowledge for such applications. In the last 150 years, many logic frameworks for the representation of abductive inference have been developed. Among these frameworks, Parsimonious Covering Theory (PCT) has achieved wide recognition. PCT is a formal model of diagnostic reasoning in which knowledge is represented as a network of causal associations, and whose goal is to account for observed symptoms with plausible explanatory hypotheses. In this paper, we argue that OWL does provide some of the expressivity required to approximate diagnostic reasoning, and outline a suitable encoding of PCT in OWL-DL.
Abduction is often described as inference to the best explanation. Given some background knowledge and a set of observations, an abductive reasoner will compute a set of best explanations. In general, abduction is formalized as Σ ⋀ Δ ⊧ Γ where background knowledge Σ and observations Γ are given, and explanations Δ (also called abducibles) are to be computed (⊧ refers to the first-order logic consequence relation). One highly popular abductive reasoning framework is the Parsimonious Covering Theory (PCT) [1]. PCT has predominantly been used in the domain of medical disease diagnosis. Reasoning in PCT is executed by algorithms that support a hypothesize-and-test inference process, and is driven by background knowledge modeled as a bipartite graph causally linking disorders to manifestations (see Figure 1). The basic premise of PCT is that diagnostic reasoning can be divided into two parts: coverage and parsimony. The coverage criterion describes how to generate a set of explanations such that each given observation is caused by a disorder in the explanation (an observation is a manifestation that has been observed). In complicated domains, such as medical disease diagnosis, the number and size of explanations may grow to be large. In order to reduce to a more reasonable size, the parsimony criterion describes how to choose which explanations are best. Many different parsimony criteria have been advanced, including minimum cardinality criterion, subset minimality (irredundancy) criterion, etc. [1]. The single disorder assumption is a simple, yet effective, parsimony criterion that has also proved popular in the past; it states that explanations may contain only a single disorder.
While OWL [2] may not have been designed for representing abductive inference, the integration with abductive reasoning has been explored [3]; however previous approaches have required modification of OWL syntax and/or an OWL inference engine [4]. In this work we will Figure 1. Background knowledge modeled demonstrate that OWL does provide some of the as a bipartite graph with an example set of expressivity needed to approximate diagnostic observations and valid explanations. reasoning – without extension of its syntax or semantics – by outlining a suitable encoding of PCT in OWL-DL. We caution the reader, however, that the OWL representation discussed does not explicitly implement PCT, but only approximates PCT, since OWL inference does not support a hypothesize-and-test inference process. 2
The task of representing PCT in OWL involves encoding the background knowledge Σ and the set of observations Γ in an OWL ontology such that the execution of OWL reasoning results in explanations Δ that satisfy both the coverage and parsimony criteria. An explanation is a cover if, for each observation, there is a causal relation from a disorder contained in the explanation to the observation. An explanation is parsimonious, or best, if it contains only a single disorder. Thus, an explanation is a parsimonious cover if the disorders in an explanation cause all the given observations.
To better clarify our task, we first describe the process of abduction where background knowledge Σ = ⟨D,M,C⟩ and observations Γ are given, and explanations Δ are to be inferred. More specifically, an abduction problem P (in PCT) is a 4-tuple ⟨D,M,C,Γ⟩ where D is a finite set of disorders; M is a finite set of manifestations; C : D ⟶ P(M) is the causation function; and Γ ⊆ M is the set of observations. (P(S) represents the powerset of S, and C maps a disorder to the corresponding set of manifestations it causes). For any disorder d ∈ D and manifestation m ∈ M, effects(d) = C(d) and causes(m) = {d | m ∈ C(d)}. effects(D) = ∈ . The set DI ⊆ D is said to be a cover of MJ ⊆ M if MJ ⊆ effects(DI). A set Δ ⊆ D is said to be an explanation of Γ for a problem P = ⟨D,M,C,Γ⟩ if and only if Δ covers Γ and Δ satisfies a given "miminality" (parsimony) criterion. A cover DI of MJ is said to be minimal if its cardinality is smallest among all covers of MJ. A cover DI of MJ is said to be irredundant if none of its proper subsets is also a cover of MJ [5].
The next step is to translate the above representation into OWL. The translation – o(P), with PCT problem P – is summarized in Table 1. The translation of Σ into OWL is straightforward. To translate the set of disorders D, create a class Disorder, and for all d ∈ D create an individual of type Disorder by asserting Disorder(d) (1). To translate the set of manifestations M, create a class Manifestation, and for all m ∈ M create an individual of type Manifestation Table 1. PCT-to-OWL by asserting Manifestation(m) (2). Finally, PCT OWL-DL to translate the set of causal relation 1 D for all d ∈ D assert Disorder(d) instances C, create an object property 2 M for all m ∈ M assert Manifestation(m) causes, and for all disorders in the domain 3 C for all m ∈ C(d) assert causes(d,m) of C and for each m ∈ C(d), create a causes fact by asserting causes(d,m) (3). 4 Γ ∃Ecxapulasneas.t{iomnn}≡, ∃wchaeuresesm.{im∈1}Γ ⊓…⊓
The translation of the set of 5 Δ for each Δ = {d}, Explanation(d) holds observations Γ into OWL is not as straightforward. To translate Γ, first select an observation m1 ∈ Γ and create an existentially quantified property restriction for the causes relation, ∃causes.{m1}. For each additional observation mi ∈ Γ, i=2,...,n, create an additional existentially quantified property restriction for the causes relation and conjoin it to the previous restriction, ∃causes.{m1} ⊓ … ⊓ ∃causes.{mn}. Finally, create a class Explanation and define it to be equivalent to the conjunction of restrictions, Explanation ≡ ∃causes.{m1} ⊓…⊓ ∃causes.{mn} (4). To generate explanations Δ, execute a query for all individuals of type Explanation by posing the query Explanation(?x). Explanation(d) is a result of this query if {d} is a parsimonious cover (5). Note that the resulting knowledge base lies in the tractable OWL 2 EL profile of OWL 2 [2]. Theorem. Given a PCT problem P = ⟨D,M,C,Γ⟩ and its translation o(P) into OWL, Δ = {d} is a PCT explanation if and only if Explanation(d) is deduced by an OWL-DL reasoner; i.e., iff o(P) ⊧ Explanation(d).
Proof: (⟹) If {d} is a parsimonious cover of Γ = {m1,…,mn} then, by definition, Γ ⊆ C(d). By construction of causes in o(P), d : ∃causes.{m1} ⊓…⊓ ∃causes.{mn}. Hence, by definition of Explanation, o(P) ⊧ Explanation(d) holds. (⟸) To justify our claim that this OWL representation approximates PCT, we verify that all query results satisfy both the coverage and the parsimony criteria. To satisfy the coverage criterion, each binding of ?x, for the query Explanation(?x), must be a disorder that causes all the observations in Γ. This follows from the definition of Explanation ≡ ∃causes.{m1} ⊓…⊓ ∃causes.{mn}. That is, Explanation(d) implies causes(d,m1) ⊓…⊓ causes(d,mn). To satisfy the parsimony criterion, each binding of ?x must be a single disorder. This follows since each disorder that binds to ?x is a single individual. This completes the proof.
If we want to generalize the definition of Explanation to allow for covers with multiple disorders, then the parsimony criterion cannot easily be expressed in OWL, since it would require minimization of the extension of a predicate. Simulation by using multiple queries may be an option, by incrementally generating cover candidates and checking whether each constitutes an explanation. This seems hardly efficient, though, and also unsatisfactory because the parsimony criterion itself is not modeled.1 Previously, we have written a meta-interpreter for more general cases [8]. 1 In a circumscriptive version of OWL [6, 7] it could easily be modeled. Consider the following example taken from WebMD [9] which relates the disorders, flu and cold, to their manifestations. Figure 2 provides a graphical representation of the background knowledge and Table 2 shows the PCT to OWL translations for the background knowledge (1-3), a set of given observations {sneezing, sore-throat, mildcough} (4), and the explanation query results composed of the disorder cold (5). For brevity, we show only a few translations, but the remainder should be apparent. We have shown an interesting use of OWL for diagnostic reasoning. Specifically, we have shown that a restricted form of explanation, according to PCT, can be obtained through a suitable encoding of PCT in OWL. Based on the popularity of PCT, in combination with the single disorder assumption, it is apparent that many applications can benefit from a representation of PCT in OWL by taking advantage of the machinery of OWL inference and by enabling the easy reuse of data on the Web. Acknowledgements. This research was supported in part by The Dayton Area Graduate Studies Institute (DAGSI), AFRL/DAGSI Research Topic SN08-8: "Architectures for Secure Semantic Sensor Networks for Multi-Layered Sensing." Pascal Hitzler acknowledges support by the National Science Foundation under award 1017225 "III: Small: TROn – Tractable Reasoning with Ontologies."