Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 A Bit of History: From Rule-based to Model-based

The early medical diagnostic applications often had the form of rule-based expert systems and started to appear around the mid 1970s. Soon, it became apparent that developing reliable diagnostic systems required an understanding of the principles underlying diagnosis, which at the time were poorly understood. Thus, during the 1980s, a research effort was made on developing the conceptual and formal aspects of diagnosis. In the early systems, knowledge from human experts was encoded as empirical classification rules, probably best seen as Horn clauses with limited expressive power [16]. Later, a model-based paradigm started to gain popularity, where the idea was to use a formal language with sufficient expressive power, such as predicate logic and timed automata, to model the part of reality that was relevant for the diagnostic problem at hand [11]. Under the new model-based paradigm, knowledge of a system’s structure and function were captured using those formal languages. Notwithstanding the efforts and progress, still in the late 1980s the understanding of the diagnostic problem principles and the characterization of diagnostic systems remained challenging. At that time, diagnostic reasoning was increasingly seen as a method to reduce uncertainty and probabilistic methods, such as offered by Bayesian networks, were investigated in the hope that they would offer a model-based method of sufficient strength and generality to handle most diagnostic problems [18]. Whereas probabilistic methods have left their mark on diagnostic problem solving, at the moment there are still many different methods being used for diagnostic applications although probabilistic methods are now dominant.

2 Elements of Diagnostic Reasoning

Making a diagnosis is normally seen as the first step towards the clinical management of illness in people; it is not possible to treat a person without having a sufficiently accurate diagnosis. Whereas the diagnosis is the outcome, the steps that are taken in obtaining this outcome constitute what is called the diagnostic process. Thus, the outcome of the diagnostic process is either the absence of illness or the presence of one or more disorders at the same time. In clinical medicine, the diagnostic process takes a particular form, consisting of taking the medical history, followed by a physical examination and supplemented by laboratory investigations (biochemistry and radiology). Taking the medical history involves recording subjective findings, called ‘symptoms’, whereas the physical examination and lab tests will yield objective results, called ‘signs’. The diagnostic process tries to obtain an explanation for the symptoms and signs in terms of disease processes, and this not only involves making observations, but also to actively collect findings, often called information gathering. This way of looking at the diagnostic process is often called diagnostic reasoning.

The diagnostic conclusions drawn by the clinical professional are based on expertise, obtained after many years of training, and clinical intuition about which diagnostic test should be performed and how to interpret the test results in the context of the patient’s characteristics. From a more abstract point of view, the medical knowledge involved has a particular structure and meaning. In addition, in interpreting diagnostic test results uncertainty is explicitly taken into account. Although most researchers will probably agree that making a diagnosis is a process that inevitably involves uncertainty, there is no consensus about how important this uncertainty is and about whether this uncertainty should always be made explicit.

Diagnostic reasoning always involves at least two different aspects. First, one needs to represent in what way a conclusion is taken as being a ‘diagnosis’. This concerns the representation of what is seen as the definition of a diagnosis. It will become clear later in this chapter that there are many different definitions of the notion of diagnosis possible. Second, a diagnosis is always based on the interpretation of specific domain knowledge. Clearly, the representation of this knowledge is also an important issue. A third aspect of diagnostic reasoning, that is not always taken into account when describing diagnostic reasoning, is a strategy involving the dynamic collection of information to rule-in and rule-out particular diagnoses.

This chapter provides an overview of the first two aspects to give the reader an entrance point to this section on knowledge-based diagnosis.

3 Conceptual Basis of Diagnosis

Several formal theories have been proposed to capture the concept of diagnosis more precisely. Most of these theories have been developed with fault diagnosis and trouble shooting of technical devices, such as photo-copiers, in mind. Despite the different nature of the objects of study, technical and medical diagnostic reasoning have much in common, both in their terminology and diagnostic methods. This similarity explains why we start with ideas that mostly come from the diagnosis of technical devices. However, all of these methods have also been applied to the clinical domain.

Researchers have become aware that there are actually various conceptual models of diagnosis that underly the formal theories, determined by the kind of knowledge involved. Diagnosis always concerns the interpretation of observed findings in the context of knowledge from a problem domain. A good starting point for describing diagnosis at a conceptual level are the various types of knowledge that play a role in diagnostic applications.

The knowledge embodied in a diagnostic system may be based on one or more of the following descriptions:

  1. (1)

    A description of the normal structure and behaviour.

  2. (2)

    A description of abnormal behaviour of a system, possibly augmented with a description of abnormal structure.

  3. (3)

    An enumeration of disorders and collections of observable findings for every possible disorder concerned, without the availability of explicit knowledge concerning the (abnormal) functional behaviour of the system.

These types of knowledge may coexist in real-life diagnostic systems, but it is customary to emphasise their distinction in conceptual and formal theories of diagnosis. Similar classifications of types of knowledge appear in the literature on diagnosis, although often no clear distinction is made between the conceptual, formal and implementation aspects of diagnostic systems. For example, [6, 19] distinguish diagnostic rule-based systems, by which they mean diagnostic systems based on knowledge of the third type mentioned above, from diagnostic systems incorporating knowledge of structure and behaviour, i.e. knowledge of the first and second type mentioned above. However, rule-based systems with a sufficiently expressive rule formalism, e.g. based on predicate logic, can be used to implement any diagnostic system, including those based on knowledge of structure and behaviour.

An observed finding that has been gathered in diagnosing a problem is often said to be either a ‘normal finding’, i.e. a finding that matches the normal situation, or an ‘abnormal finding’, i.e. a finding that does not match the normal situation. Based on the three types of knowledge mentioned above, and the two sorts of findings, three different conceptual models of diagnosis are usually distinguished; they will be called:

  • Deviation-from-Normal-Structure-and-Behaviour diagnosis, abbreviated to DNSB diagnosis,

  • Matching-Abnormal-Behaviour diagnosis, abbreviated to MAB diagnosis, and

  • Abnormality-Classification diagnosis, abbreviated to AC diagnosis.

Below, we shall discuss the relationship between these three conceptual models of diagnosis and the three types of knowledge mentioned above. A formal theory of diagnosis has been proposed for each of these conceptual models of diagnosis. In the remainder of this section, each of the three conceptual models of diagnosis will be discussed, and the corresponding formal theory of diagnosis is mentioned.

DNSB diagnosis.  For diagnosis based on knowledge concerning normal structure and behaviour, little or no explicit knowledge is available about the relationships between disorders, on the one hand, and findings to be observed when certain disorders are present, on the other hand. Hence, DNSB diagnosis typically employs knowledge of the first type mentioned above. From a practical point of view, the primary motivation for investigating this approach to diagnosis is that in many domains little knowledge concerning abnormality is available, which is certainly true for new human-created artifacts. For example, for a new device that has just been released from the factory, experience with respect to the faults that may occur when the device is in operation is lacking. Thus, the only conceivable way in which initially such faults can be handled is by looking at the normal structure and functional behaviour of the device. In clinical medicine, this will normally happen when one is encountering a new disease. Here, as with the technical disciplines, the only thing one can do is make use of knowledge of normal physiology and compare predicted behaviours with those observed.

Fig. 3.1
figure 1

Deviation-from-normal-structure-and-behaviour (DNSB) diagnosis.

Full size image

For the purpose of diagnosis, the actual behaviour of an actual system, called observed behaviour, is compared with the results of a model of normal structure and behaviour of the system, which may be taken as predicted behaviour. Both types of behaviour can be characterised by findings. If there is a discrepancy between the observed and the predicted behaviour, diagnostic problem solving amounts to isolating the parts of the system that are not properly functioning, using the model of the normal structure and behaviour. In doing so, it is assumed that the model of normal structure and behaviour is sufficiently accurate and correct. Figure 3.1 depicts DNSB diagnosis in a schematic way. DNSB diagnosis is frequently erroneously called model-based diagnosis in the literature, as if it were the only instance of model-based diagnosis. It is also called consistency-based diagnosis, but here this term is reserved for the corresponding formal theory of diagnosis. DNSB diagnosis has been developed in the context of troubleshooting in electronic circuits [6]. A well-known program that supports DNSB diagnosis, and includes various strategies to do so efficiently, is the General Diagnostic Engine (GDE) [7].

The formal counterpart of DNSB diagnosis, called consistency-based diagnosis, originates from work by R. Reiter, [24]. DNSB diagnosis-like approaches have been used in medical applications on a limited scale (cf. for example [9]); there is more work in which DNSB diagnosis has been applied to solve technical problems (cf. [2]).

Fig. 3.2
figure 2

Matching-abnormal-behaviour (MAB) diagnosis.

Full size image

MAB diagnosis.  For diagnosis based on knowledge of abnormal behaviour, diagnostic problem solving amounts to simulating the abnormal behaviour using an explicit model of that behaviour. Hence, in MAB diagnosis the use of knowledge of abnormal behaviour (the second type of knowledge mentioned above) is emphasised. By assuming the presence of certain defects, some observable abnormal findings can be predicted. It can be investigated which of these assumed defects account for the observed findings by matching the predicted abnormal findings with those observed. In Fig. 3.2, MAB diagnosis is depicted schematically. In most applications of MAB diagnosis, the domain knowledge that is used for diagnosis consists of causal relationships. Two, strongly related, formal counterparts of MAB diagnosis have been proposed in the literature. The first formal theory, referred to as the set-covering theory of diagnosis, is based on set theory: causal knowledge is expressed as mathematical relations, used for diagnosis. This theory originates from work by J.A. Reggia and others [23]. The second theory is based on logic. Early work in this area has been done by Poole [19, 20], and Console and Torasso [5, 28]. Based on the type of reasoning employed to formalise MAB diagnosis, i.e. reasoning from effects to causes instead of from causes to effects, this theory of diagnosis is also referred to as abductive diagnosis. Theorist [20] and its successor AILog [21] are two systems supporting MAB diagnosis.

AC diagnosis.  Whereas DNSB and MAB diagnosis employ a model of normal or abnormal structure and behaviour for the purpose of diagnosis, the third conceptual model of diagnosis uses neither. The knowledge employed in this conceptual model of diagnosis consists of the enumeration of more or less typical evidence that can be observed, i.e. observable findings, when a particular defect or defect category is present (the third type of knowledge mentioned above). For example, sneezing is a finding that may be typically observed in a disorder like common cold. This form of knowledge has been referred to as empirical associations (the phrase ‘compiled knowledge’ is also employed) [3].

Fig. 3.3
figure 3

Abnormality-classification (AC) diagnosis.

Full size image

Diagnostic problem solving amounts to establishing which of the elements in a finite set of defects have associated findings that account for as many of the findings observed as possible, as is shown in Fig. 3.3. The enumeration of findings for the normal situation (knowledge of the fourth type mentioned above) is sometimes also used in AC diagnosis, together with knowledge of the third type; then, observed findings are classified in terms of present and absent defects. The main goal of AC diagnosis, however, remains the classification of observed findings in terms of abnormality. AC diagnosis is often referred to in the literature as heuristic classification [4], although this term is broader, since it also includes a reasoning strategy. AC diagnosis can be characterised in terms of logical deduction in a straightforward way. We shall refer to this formalisation of AC diagnosis as hypothetico-deductive diagnosis.

4 Formalisation and Implementation

Any formal system aiming to determine a valid (and perhaps most likely) diagnosis establishes a projection to hidden event sources (diseases, conditions or syndromes) and observable findings, that is symptoms and signs. However, the form of this mapping differs depending on the formalisation theory supporting the knowledge representation. A diagnostic system can be described as in Chap. 2 in terms of object knowledge, the domain knowledge that is used to determine a diagnosis, and meta knowledge, here the actual definition of what a diagnosis is.

4.1 Diagnostic Object Knowledge

The most common object knowledge representations in diagnostic systems are:

  • A causal specification of relationships between (the interaction of) causes and effects. Formally a causal specification can be represented by logical implications of the form

    $$\begin{aligned} C \rightarrow E \end{aligned}$$

    or by means of functions or relations \(E = f(C)\), and by a family of probability distributions \(P(E \mid C)\) if in addition uncertainty is represented in the specification. Causality is as central to science as it has proved elusive to define. There is no single nor agreed definition of causality, with many attempts demanding two critical elements: (i) some kind of temporal precedence or ordering, e.g. Granger’s [10] or Lamport’s [14], and (ii) context, e.g. Pearl’s [17] or Rubin-Holland’s [25]. The first demand maybe implicit, ergo the model still might be static. The second demand is perhaps even more difficult to comply and thus it is too very often neglected abusing the causal sufficiency assumption or alleviated under the close-world assumption. Here, in the context of diagnosis it just refers to a particular way to model the reality (without pretending it captures the physics of causality). Consequently throughout this chapter, we will use the words cause, effects and causality without necessarily entailing formal causality. Moreover, causal relations are not necessarily strict [22].

  • A model of structure and behaviour, often referred to as functional model or first principles, represented in logical or in algebraic form, whereas timed automata are used when temporal behaviour is being modelled, and temporal or dynamic Bayesian networks are used if the model includes uncertainty.

  • An associational specification (non-causal) incorporating empirical relations as logical rules determined from human expertise, or statistical intuition.

4.2 Diagnostic Meta Knowledge

In order to define a diagnosis for a problem, using object representations of relevant knowledge, we need diagnostic meta knowledge, as introduced in Chap. 2. Basically, for causal knowledge the meta knowledge has the form of the covering condition, i.e. abductive diagnosis:

$$\begin{aligned} \text{ KB } \cup D \vDash F \end{aligned}$$

where KB is a set of causal, local rules, F is a set of observed findings and D is the diagnostic, abductive solution.

From the above statement it may be inferred that there is a one-to-one mapping joining a formalization theory with a particular knowledge representation. While this is not a universal truth, there remains a strong benefit from using a particular type of object knowledge with a particular type of meta knowledge under a particular framework. Chapter 2 gives details about the most popular symbolic diagnostic approaches. See [15] for a detailed analysis of the relationship between object and meta knowledge in diagnostic systems.

4.3 Probabilistic Diagnosis

As mentioned at the beginning of this chapter, many people see uncertainty as an essential ingredient of a diagnostic problem [27]. Bayesian networks are a popular formalism to represent object knowledge, and often arcs in a Bayesian networks are given a causal reading. As symptoms, signs and test results in Bayesian networks are often sink nodes, i.e. have no outgoing arcs, whereas diseases act as source nodes, i.e. have no incoming arcs, reasoning with such a Bayesian network can be looked upon as abductive reasoning, very similar to purely symbolic or logical forms of diagnostic reasoning.

In probabilistic diagnostic reasoning systems the diagnostic value of specific symptoms, signs and tests are used to rule in or rule out a diagnosis [1, 8]. Probabilistic reasoning requires knowing (i) the pre-test or prior probability of the diagnosis being considered, and (ii) the degree to which a positive or negative result from a specific test adjusts the probability of that diagnosis. The pre-test probability of a sease is known as the prevalence of the disease. Interpretation of the post-test or a posteriori probability strongly depends on the prevalence (i.e. pre-test probability). The most likely diagnosis is computed by Bayes’ rule:

$$\begin{aligned} P(d \mid t) = \frac{P(t \mid d) P(d)}{P(t)} \end{aligned}$$

where \(P(t) = P(t \mid d)P(d) + P(t \mid \bar{d})P(\bar{d})\). The probability \(P(t \mid d)\) is the likelihood that the test t is positive given that the disease d is present, i.e. the true positive rate (also called sensitivity in the medical literature), and the probability \(P(\bar{t} \mid \bar{d})\) is the likelihood that the test result is negative given that that the disease is absent. It is also known as the true negative rate (specificity in the medical literature). Both rates are usually in the range [0.90, 0.99].

As an example, consider the the diagnosis of flu f based on measuring the body temperature t (equal or above \(38\,^{\circ }\text{ C }\)) and \(\bar{t}\) (below \(38\,^{\circ }\text{ C }\)) on two different occasions. The first is under conditions of a severe flu epidemic and the second is in the middle of the summer. Now, the prevalence of flu under epidemic conditions is assumed to be \(P(f) = 0.5\), whereas in midsummer it is \(P(f) = 0.05\). Using Bayes’ rule and assuming that \(P(t \mid f) = P(\bar{t} \mid \bar{f}) = 0.95\), we compute the post-test probability for those two possibilities:

  • \(P(f \mid t) = P(t \mid f) P(f) / P(t) = 0.95 \cdot 0.5 / 0.5 = 0.95\).

  • \(P(f \mid t) = P(t \mid f) P(f) / P(t) = 0.95 \cdot 0.05 / 0.095 = 0.5\)

Since the true positive and negative rates do not change, the prevalences have a major effect on how likely a diagnosis is. We also have the following observations:

  • Under low prevalence: A negative test is enough to rule out a diagnosis, but a positive test is likely to be a false positive.

  • Under medium prevalence: Tests work often at their best. With a positive test it is reasonable to assume the condition is present, and with a negative test it is reasonable to assume this is not the case.

  • Under high prevalence: A positive test is enough to confirm a diagnosis, but a negative test is likely to be a false negative.

As patient often have two or more diseases at the same time, known as multimorbidity, one actually has to compute the maximum a posteriori probability (MAP) assignment [13]

$$\begin{aligned} D^\star = \text{ argmax }_{D}P(D \mid E) \end{aligned}$$

where D is a set of instantiated disease variables and E the evidence (symptoms, signs, and lab test results). Since the computations are NP-hard, one usually resorts to computing the marginal probability \(p(d \mid E)\) for individual diseases d.

Table 3.1 Comparison conceptual and formal theories of diagnosis and their implementation.
Full size table

4.4 From Conceptual to Formalisation and Implementation

A comparison of the three conceptual and formal models of diagnosis is given in Table 3.1. Obviously, the various models of diagnosis discussed above can also be combined. To solve real-life diagnostic problems in a domain, it is likely that a mixture of conceptual models of diagnosis as distinguished above will be required. Since the resulting systems use various types of knowledge, e.g. both knowledge of structure and behaviour, and empirical associations, the result is known as diagnosis with multiple models.

Although in the literature it is emphasised that the conceptual models of diagnosis discussed embody different forms of diagnosis, they have much in common. For example, the type of knowledge used in DNSB diagnosis can be viewed as an implicit, or intensional, version of the type of knowledge used in AC diagnosis (if restricted to normality classification), which is an explicit or extensional type of knowledge; the associations between normal observable findings and the absence of defects are hidden in the specified normal behaviour in DNSB diagnosis. DNSB and MAB diagnostic problem solving are based on some kind of simulation of behaviour; such simulation of behaviour is absent in AC diagnosis. In all cases, the diagnostic problem is seen as an ordered pair \(\mathscr {P} =(K,O)\), with \(K = (C,R,E)\) in turn a tuple of causes C, association rules R, and effects or possible observations E corresponding to the description of the causal model, and O a set of actual findings or observations such that \(O\subseteq E\). The particular form, as well as the semantic, of the elements and subelements of the diagnostic problem depends on the chosen formalisation paradigm. For instance in consistency based diagnosis the system description is a finite set of first-order logic formulae R implicitly encoding the projection from system components C to observed findings E, whereas in the case of set covering diagnoses R is explicitly a subset of the Cartesian product between disorders C and manifestations E.

Finally, several programs have been developed that offer limited possibility to carry out diagnostic problem solving using multiple models; examples of such programs are GDE [12]. These programs use DNSB diagnosis as their core approach.

5 Conclusions

This chapter introduces the book section on the use of knowledge representation to solve the diagnostic problem. The chapter has briefly overviewed important formalisation theories which arise from the two reasoning frameworks dominating formal medicine; namely deductive and probabilistic. Each of these ways to explaining events are archetypical of two attitudes towards clinical diagnosis; deterministic and evidence-based diagnosis [26]. Whatever the reasoning chosen to address the diagnosis, it seems clear that our GP has now a wealth of formal approaches at her hand to reason the most solid diagnosis on the light of the signs. The different options available have different expressive capabilities and their choice depends on the type of knowledge base available to the system designer. Notwithstanding, uncertainty and meaning can be combined in a unified framework such as offered by probabilistic logics, such as AILog [21].

The rest of this book section presents two specific examples of formal diagnostic systems, each of them addressing different clinical problems and founded on different knowledge representation paradigms.