Back to List of Publications
Enrico Coiera
Hewlett-Packard LaboratoriesFilton Rd., Stoke GiffordBristol, BS12 6QZ United Kingdom
This paper appeared in Artificial Intelligence in Medicine , 4, (1992), 431-445.
Abstract -The limitations of shallow representations have in part driven AI researchers to focus on deeper representations of knowledge. While deep representations solve some problems, they come at a computational cost. This paper focuses on the computational and representational advantages that may exist in using representations whose depth is intermediate between shallow and deep. The Roschian notion of basic level categories is used to help develop the notion of the cognitively most economic representation. For medical diagnostic systems that reason about time varying aspects of disease, it is proposed that qualitative disease histories are a good intermediate representation, lying between shallow disease patterns and deeper qualitative models. Since no single representation will provide complete coverage of a problem domain, this paper further considers how one could construct, in a principled way, a reasoning system that uses multiple representations. Measures of intra and inter-representational adequacy are proposed to define the optimal level of such a knowledge base for a given problem. These measures define the trade-offs that occur when using a particular representational level, and the conditions under which a reasoner can decide to switch representations. As an example, the formal relationships between histories and the qualitative models that produce them are shown to define conditions that can be used by a reasoning system to switch from histories to deeper models.
Key Words: knowledge representation, deep knowledge, category theory, basic level, qualitative reasoning, qualitative disease history, qualitative superposition, multilevel model.
The notion that medical knowledge can be represented at varying levels of depth is now generally accepted. It was in part the limitations of shallow representations like production systems that drove AI researchers to focus on deeper representations of knowledge. While these deep representations do seem to solve some of the problems associated with shallower ones, they come at a computational cost. This paper focuses on the computational and representational advantages that may exist in using representations whose depth is intermediate, trading off the advantages and disadvantages of shallow and deep representations. In particular, for medical diagnostic systems that reason about time varying aspects of disease, it is proposed that qualitative disease histories are a good candidate for an intermediate representation, lying between shallow disease patterns and deeper qualitative models.
It is recognised however, that no single representation will provide complete coverage of a problem domain. For many applications, a multilevel representation of knowledge will be necessary and the current interest in hybrid systems reflects this perception. This paper considers how one could construct, in a principled way, a reasoning system that uses multiple representations. It explores the trade-offs that occur when selecting a particular representational level, and explores the conditions under which a reasoner can decide to switch representations.
The `Knowledge Principle' of Feigenbaum [20] stated that the key to intelligent performance for a computer system lay in it containing large amounts of knowledge, rather than sophisticated general reasoning procedures. However, these systems only operate successfully when they are restricted to tightly defined domains. Rule based systems are brittle, their competence rapidly decaying at the edge of their expertise. In contrast, people exhibit a much more graceful decay from expertise, being cushioned by weaker but more general problem solving capabilities. This `robustness' [9] is a desirable characteristic for expert systems that have to diagnose previously unencountered situations, or events due to novel fault interactions. Deep representations of knowledge are believed to assist in providing such robustness.
Much confusion remains over the definition of a deep system [29], and capturing deep behaviour will probably require more than exploring knowledge representation alone. Nevertheless it is useful to discuss the depth of a particular knowledge representation. Deep representations pragmatically are those that have some underlying representation of physical laws or mechanisms and can thus solve problems on which shallower ones fail. Our deepest model might be a set of differential equations describing the principles that are understood to govern the behaviour of a particular system. Between such formal mathematical models of the real world and shallow representations, there lie qualitative representations that can significantly augment the reasoning capabilities of AI systems. In recent years a considerable body of work has emerged on the representation of deep knowledge in the form of qualitative models (e.g. [31]), and for many these are seen as a primary representation of the structure of deep knowledge.
Although model based representations do support enhanced reasoning over shallow systems, they are not without their problems. Yet these are often ignored when model-based reasoning is discussed. The difficulties inherent in model based representations include:
Computational Expense: Deep knowledge subsumes shallow (or as is often stated shallow knowledge is compiled from deep knowledge). For a given problem where both representations are adequate, the application of the deep one requires more computational effort. For example, one can contrast the effort of working out a diagnosis from an ECG using anatomical and physiological knowledge, compared to recognising it from past experience.
Computational Tractability: A corollary of the increase in computational expense of deeper representations is the decreased likelihood of obtaining an inference from them at all. Levesque and Brachman [21] have explored the "fundamental trade-off between tractability and expressiveness" for knowledge representations. As one increases the richness of things that can be expressed, the inferences made become more complex and less tractable. Although tractability usually refers to worst case scenarios, it is an important issue in the design of safety critical systems.
Real-time requirements: Some systems will be required to perform with constraints on the time available to produce an answer. A patient monitoring system that seeks to diagnose clinical conditions for example, will not always have time to completely identify a problem. Clinically critical situations need to be recognised immediately. There are thus practical constraints on how much effort can be devoted to computation, and how soon an answer is needed. Model based techniques on their own may thus not always be appropriate. Further, the control knowledge that guides the allocation of resources, and focuses and prioritises diagnosis or treatment may often be of an experiential nature.
Model availability: Model-based reasoning assumes that domain knowledge has been formalised beyond associational knowledge, but in medicine this is not always the case. The development of qualitative modelling languages has reduced the level of formalisation required of a domain before useful models can be constructed, but it is still not clear that such models can always be easily acquired. To remedy this difficulty in model acquisition, some work is now in progress to automate the model acquisition process using techniques from machine learning (e.g.[2], [4], [22], [28]).
One solution to these problems is to give a reasoning system access to several different representations which each capture different aspects of its problem domain. Access to deep and shallow representations of knowledge should allow a reasoning system to gain broad domain coverage as well as some robustness.
There are several dimensions with which representations can be characterised, and these can be used to select the most appropriate way of structuring and navigating multilevel systems. These include the depth of a representation but also cover ontological perspective and mode of system behaviour [7]. If we look particularly at the depth of a representation, two orthogonal axes can be used to characterise `depth' - the granularity of detail represented and the type of representation used.
The level of detail one wants to represent varies with the task at hand [25] and there is often advantage in starting problem solving at a coarse granularity of description and focusing in progressively as needed [24]. An analogy with map reading is often made, where one first localises a general area using an overview map, and then homes in with detailed maps on the area of interest. KARDIO's four level model of the heart is a good example of a hierachy that is organised around varying granularity [23].
When one progresses from detailed to general representations of knowledge, information is lost in the abstraction process. Weld [32] has explored some of the ramifications of formulating models which approximate more detailed ones based upon the requirements of a given problem. Since the type of representation used in a pure granularity hierachy does not change, neither does the inference procedures that one would use upon it. Deeper models in a granularity hierachy are larger but use the same inference procedure, and hence the cost of going deep is determined by model size. There is thus a trade-off between accuracy and model size. Further, as model size increases, there should be an increase in the time taken to compute an answer using it.
Hierarchies can be constructed in which the representation used changes between levels. Several examples of systems that use mixed hierarchies of models and rules now exist (e.g. [1], [13], [17], [19]), with the KARDIO work representing probably the most complete study to date of the utility obtained from such combinations.
In contrast to varying granularity hierarchies, accuracy need not change between representational levels. No diagnosis specific information has to be lost in compilation from model to rule. The behavioural description of a disease can be identical for a given diagnostic category, whether it comes from a model or is found in a rule. What changes is the inference procedure one uses to obtain the description. For example, simulation may be needed to generate a behavioural description from a model, whereas the description is already stored in a rule, and inference is based on pattern matching. Shallow representations like rules are however disadvantaged by requiring more space than deeper ones like qualitative models. The trade-off in a pure representation hierarchy is between the time it takes to compute an answer and the space it takes to store the representation.
The differences between hierarchies based on varying granularity of detail and varying representational type are summarised in Table 1.
As systems which incorporate multiple forms of knowledge are developed, the situations in which each is most appropriately used needs to be clearly delineated. In particular, different levels of depth require different inference procedures, each of which will have varying success when solving a given problem. Selecting too shallow a representation will result in failure on difficult tasks, while too deep a representation will be computationally uneconomic.
There are thus two important classes of selection criteria for a knowledge representation. The first is based upon the adequacy of a representation - is it capable of solving a problem in principle? The second is based upon representational economy - which of the useful representations is the most economic one to use? Some representations (rules for example) will offer computational economy but will have limited utility. Other deeper ones (such as qualitative models) will have much broader utility but be computationally expensive. Between the two extremes there may lie representations which optimise between these two broad needs. What is required is a formalisation of the criteria that may be used to select the optimal depth of representation for a given problem.
Rosch's classification theory [26] proposes that the most appropriate level of category abstraction for an object is the most cognitively economic one - which she calls the basic level. Objects in the basic level have the quality that they are prototypic of their class. Such prototypic instances contain the attributes that are most representative of items inside, and least representative of items outside a category. A classic example is the concept of a chair, which is considered a prototype. We don't get much more information by being more specific in our description e.g. a dining chair, and we lose a lot by being more abstract and classifying an object simply as furniture.
The most cognitively economic granularity when representing a pathophysiologic process must both capture the main features we need to recognise a disease, without adding unnecessary detail. Clearly however, such a specification varies with reasoning task. For example, it may be most economic to represent metabolic acidosis with a generalised description of the time varying behaviour of the disturbance, rather than with individual case examples or a more detailed model of the underlying pathophysiology. Yet with difficult cases, especially with interacting diseases, we may need to turn to the detailed model. An equally important factor affecting the choice of representational level is the state of knowledge in a domain. As we have seen, in poorly understood domains formal models might be unavailable, and individual case histories may have to define the bulk of collected knowledge.
If we make an analogy between category and knowledge hierarchies, the notion of cognitive optimality inherent in the Roschian basic level can be used to select an optimum depth of representation. In fact, the analogy extends to hierarchies of varying granularity and representational type.
Corter et al. [8] demonstrate experimentally that classification hierarchies based on varying granularity of abstraction exhibit the basic level phenomenon with human subjects. They label this explanation of basic level effects the structural theory. They also report that basic level effects have been observed in earlier work on classification hierarchies, in which category levels vary the type of feature present - the feature-type hypothesis. Here categories that group entities by their abstract functions (like vehicles or weapons) are less easily used than those that aggregate based upon perceptual concepts such as parts (like wing or engine). If the likelihood that a level is useful is determined by its feature type, then levels whose features require the least computation for a given task should be the basic one.
We can hypothesise that feature-type category hierarchies share properties with knowledge hierarchies based on varying representational type. There is thus a notion that a different computational operation is associated with each level, and that the cost of that computation assists in determining the level's utility. Some support for this comes from the `intermediate effect' in which subjects with intermediate level expertise are better able to recall cases than either experts or novices, but perform poorly on diagnosis under conditions of limited time. Schmidt et al. [27] suggest that it is the type of knowledge used that explains this phenomenon. If intermediates use deep pathophysiological models in preference to the compiled surface knowledge used by experts, they will perform well when given time to recall cases, since their representation is richer. Equally, they will perform badly when the time available to perform diagnosis is limited, since deep models require greater cognitive effort to use than compiled expert knowledge. Thus the type of representation which performs best varies with task, and with the intermediate effect, subjects with different levels of expertise are hypothesised to have preferential access to different depths of representation.
The basic level can be seen to set the `entry point' into a representational hierachy that on average is known to provide the correct level appropriate for solution. The selection of such a computationally optimal depth should also be task dependent [14][15]. Choosing basic levels in a varying granularity hierarchy will depend on developing a measure of intra-representational optimality, and in a varying representational hierarchy upon a measure of inter-representational optimality. In mixed hierarchies, one would select a model that optimises both of these measures.
In a pure granularity hierarchy, models vary only in the level of detail they express. One thus seeks a measure which will allow the selection of a level within a hierarchy that is most likely to provide an answer to a query without providing excessive detail. Several computational models of the basic level already exist, and these could be applied directly to the selection of a basic depth for such hierarchies. Gluck and Corter [14] propose two metrics for Category Utility which is a context-sensitive measure of the predictive ability of a level of categorization based upon the structure theory. The metrics are based on information theory and expected probabilities. The first sees category utility as a measure of the information transmitted between a category and its associated feature set. The second sees it as a trade-off between the number of correct predictions made and the proportion of the environment to which the predictions apply. Categories which are very accurate but apply to few individuals are not favoured, nor are those that cover a large proportion of the population but because of generality have poor accuracy. Category utility experimentally predicts the preferred or basic level observed experimentally in several psychological studies.
Greiner and Elkan [15] propose general measures for determining the utility of a knowledge representations. They suggest that the utility or merit of a representation can best be determined by external measures of its behavioural adequacy rather than by internal measures such as representational simplicity. The dimensions of merit they propose are accuracy, categorality and timeliness. Accuracy refers to the number of correct answers the representation provides, and categorality to the number of times the representation comes up with a clear answer. These first two measures are identical in spirit to the notion of category utility. A representation that always answers a question (i.e. is able to serve the population of questions) but usually answers equivocally (has poor category accuracy) is not one to be favoured. They also propose a general probabilistic mechanism to assess the utility of representations. Category utility would fit into their structure as an example of a specific metric useful for a specific kind of representation. The third measure, timeliness, can be viewed as a property that is based on computational characteristics - an inter-representational property.
Probabilistic notions of the basic level do not seem to completely capture the essence of hierarchies which vary representation type. Since for any given problem, a shallow representation (where it exists) will deal as adequately as a deeper one, the notion of category utility based upon the average success of a representation is not useful. The essence of a type varying hierachy is that different levels have different computational properties. This suggests that the basic depth for type hierarchies could be determined by computational metrics - in particular a trade-off between computational complexity and tractability, and space limitations. Although in principle a shallow level representation can always be generated from a deeper one, it is not always practical to do so because of space limitations. So there will be problems for which a shallow representation will not have answers because of its incompleteness, and for which the deeper one must be used.
This is complicated by the fact that the space of knowledge represented at any one level may be sparse because of external factors. The state of knowledge in a domain may limit the depth to which knowledge can be encoded. Such gaps in knowledge will inhibit free traversal of the knowledge represented in a hierarchy. Thus decisions to switch type depth should also be based upon information about the completeness of a level - whether incompleteness arises out of a conscious decision to optimise space or reflects a deficit in current knowledge. In other words, each type depth will have an associated set of operational specifications which specify the conditions under which it can be successfully applied given the state of knowledge at that depth and the type of problem that is being addressed. Such performance guidelines will probably be representation specific.
While there are examples in the literature of possible intra-representational measures of optimality, the situation seems less clear for inter-representational measures. If we postulate that the notion of basic depth has meaning in knowledge hierarchies structured around representation type, then there should exist examples of such intermediate or basic depth representations. In the process of exploring the computational characteristics of such representations, and their relationships to deeper and shallower types, it should be possible to develop robust inter-representational measures of optimality.
Most work to date has concerned itself with the direct transformation of deep models into surface knowledge to enhance computational efficiency. Projects like KARDIO [1] have demonstrated some of the computational trade-offs that exist between these two extreme levels. However, there has been scant attention paid to the possibility of utilising representations intermediate between model and rule based systems. It is these that may have the characteristics of a Roschian prototype, optimising the balance between computational and representational efficiency on the one hand, and problem coverage on the other.
To develop an understanding of the potential for intermediate depth representations, and of systems which utilise knowledge at various depths, a number of questions need to be addressed:
· What could intermediate representations look like?
· How do we reason with such intermediate representations?
· What is the relationship between different representation levels?
· What are the limits of utility for a particular level?
· When do we move between representation levels?
The remainder of this paper will examine these questions from the perspective of a diagnostic system that needs to reason about the time varying aspects of physiological processes. The discussion will use the notion of disease history as an example of an intermediate depth representational type, and attempt to place histories formally between models and rules.
Rosch's [26] work on representation is largely concerned with the classification of objects, rather than processes or events. She suggests however, that a good candidate for the prototypic representation of events are Schankian scripts describing individual units of action like making a cup of coffee or going to a lecture. In medicine, we are more often concerned with diagnosing the time varying behaviour of disease than representing such routine actions. Intelligent patient monitoring systems are a case in point [5]. Consequently, for such systems we would be interested in representations that allowed temporal disease processes to be inferred or represented in prototypic form.
It is traditional to discuss the temporal progression of different diseases in relation to an idealised natural history. The natural history describes the usual temporal course of a disease in an average patient, unimpeded by other factors. The history might have been obtained empirically, being refined over successive case studies. With well understood disease processes, the history could be derived from pathophysiologic models. Histories thus have some characteristics which suggest they are an important prototypic representation in medical reasoning.
There are many possible computational models of a natural history that could be used. The notion of a history is a key one in AI, since it was first proposed as an organising representational principle for naive or commonsense physics by Hayes [16]. Histories in Hayes' manifesto recorded the time varying behaviour of physical systems. An enormous effort since then has been devoted to developing techniques that generate histories from qualitative models of physical systems. The emphasis on using a qualitative representation has been motivated by the long understood need to represent knowledge of physical systems that is imprecise or uncertain. The process of qualitative history generation is now largely synonymous with qualitative simulation [18].
It is clear that the notion of a disease history has practical utility in clinical medicine. Further, we can identify techniques for generating histories from models that are considered a representation of deep knowledge.These points suggest that qualitative disease histories (QDHs) may be a valid representation in their own right, and a good candidate for an intermediate level knowledge representation. What would need to be demonstrated to support this contention would be that:
· Qualitative histories were more computationally efficient than qualitative models when used for similar problems.
· Qualitative histories allowed a reasoning system to attain greater coverage of problem types when compared to a shallower representation.
· Qualitative histories were representationally efficient when compared to shallow representations - being a compact enough representation to require less physical storage.
Clear guidelines should be formulated to suggest when a history based system would need to move to deeper or shallower representational levels.
A qualitative history describes the behaviour of a physiological system over time. It is composed of a time ordered sequence of qualitative state descriptions, with each state representing a behaviourally distinct region. Histories generated by qualitative simulation can be differentiated from causal state sequences (e.g. CASNET [30]) by the detailed structure of each state description and the nature of the interstate transitions. If we assume that our history was produced from a qualitative model consisting of several parameters, then each state of the history will have a value assigned to each model parameter. The values that are assigned to the parameters are qualitative, specifying the sign of the parameter's derivative along with it's numeric value or an interval within which we expect the value to be [18]. The transitions between states in a qualitative history do not have a necessary causal reading and reflect changes in the values of system parameters according to the constraints of the underlying qualitative model. Since they are generated from qualitative models but are more structured and information dense than associational rules, qualitative disease histories are intermediate in depth between the two (Figure 1).
Histories can be used for diagnosis or prediction, and a key requirement for both of these tasks is to be able to represent the behaviour of multiple interacting diseases. This requirement proves to be a central issue when reasoning with qualitative histories. Prediction using single disease histories is accomplished by straightforward look up once a disease is selected. Prediction when multiple diseases are present and where each disease is represented with a single history requires that an inference procedure be performed on the individual histories to generate the interaction.
Theoretical results based on the mathematical properties of qualitative histories ([5], [6]) show that qualitative superposition of individual disease histories can often directly predict interactions (Figure 2). Qualitative superposition refers to the process of qualitatively adding states from individual histories to generate interaction states. The superposition procedure is legal for all linear systems, and for many non-linear systems. Special conditions, such as the dominance of one history over another are needed in some instances to ensure that superposition will succeed. Further, superposition cannot be used to predict the behaviour of some classes of non-linear system. However, having relaxed the need to make precise quantitative predictions, qualitative superposition may be applied to many non-linear systems where quantitative superposition fails. The limits for qualitative superposition with non-linear systems are actively being researched [6]. Such superposition limits will be used here as an example computational property that can trigger a switch between representations.
In section 4.1 a number of criteria were set up to establish whether qualitative histories could be considered a useful intermediate level representation, displaying computationally optimal characteristics. These will now be explored each in turn, both to make the case for histories, and to enumerate situations in which a reasoning system would need to consider representations that were either deeper or shallower.
An alternative to computing interactions of diseases by qualitative superposition is to precompile disease interactions for some arbitrary depth of diseases. This is the approach taken in KARDIO [1] and MIMIC [11] which precompile recognition rules for disease interactions from deeper qualitative models. Using such rules will of course be more computationally efficient than reasoning from first principles with a model, or superimposing histories. The disadvantage is the large number of such rules that need to be generated, and with large applications the potential for combinatorial overload with rules may be enormous. This is one of the trade-offs between rules and histories. As we move from deep to shallow we gain computational efficiency at the price of spacial efficiency.
A shallow system will only deal with diseases that are already explicitly part of the knowledge base, including instances of disease interaction. If interactions have not been previously considered, or occur with a greater number of diseases than the system has been coded for, then the shallow representation is incomplete. Rule based systems that are not derived from deeper models also have the potential for incompleteness because of missing rules.
Reasoning with interactions becomes one of the differentiators between shallow and deeper representations. A system using qualitative histories can potentially handle an arbitrary number of disease interactions provided that the individual diseases are already represented and superposition is legal. Thus the problem coverage of the intermediate representation is broader than that of a shallow system. Equally however, a system using histories will not be able to deal with problems involving new diseases - it is incomplete for interactions not reproducible by superposition.
A deeper model based system might be able to reason where a history based system fails if the new disease can be modelled as a fault in its current pathophysiologic representation. While a history based system is limited to a subset of disease interactions which can legally be computed using superposition, model based systems do not have this particular limitation. They can compute any interaction within the scope of the model, but are incomplete for unmodelled behaviours.
A history based reasoner does have one important advantage in problem coverage over model based systems - it will be able to reason with disease histories that have no well-formed underlying pathophysiological model. Such empirically derived histories will not allow as robust reasoning as those derived directly from models [5], but the knowledge they represent is not available at all to model based systems. Interaction predictions obtained using empirical histories are however considered less reliable than those obtained from model-derived histories because we cannot be sure that superposition is legal for them.
A reasoning system involved in predicting the behaviours of a physical system using a qualitative model will need to engage in some form of simulation. In the worst case this is an exponential and possibly non-terminating task and at best a linear function of the number of model parameters [18]. For a shallow system, the task of selecting an appropriate diagnostic pattern is determined by computational complexity of the pattern recognition algorithm chosen. For a reasoning system with access to a database of pre-computed single disease histories, the prediction task is a mixture of these two extremes. For single diseases, the process is identical to the shallower system. For multiple disease interactions, the process of qualitative superposition at worst is identical to the process of simulation. One would expect that in the average case a problem solver would encounter a large number of single diseases. Thus a history based system should outperform, on average, a simulation based system on problems that they both can successfully solve.
The case for mass storage is a similar one. Shallow systems, since they must explicitly store patterns for multiple diseases interactions, will require the most storage. A history based system would be smaller, requiring only single disease histories to be stored. A simulation based system would be smaller still, storing only the model that could potentially generate the histories explicitly stored in next level. This position is supported by experimental results from KARDIO ([1], [23]) which demonstrate a 50:1 compression of space requirements between rules and the cardiac model that was used to generate them.
Only a few systems to date dynamically switch between levels based on an understanding of the problem at hand (e.g. [17], [13], [19]). Further, it is not altogether clear from these in which circumstances such switches should occur. It should however, be possible to suggest a principled set of mechanisms which can guide level selection, and interlevel navigation. The concepts of representational optimality that have been suggested here may be appropriate for this task. Other approaches, geared to selecting the levels most appropriate for different query types, have also been made (e.g. [32], [12]) and can be considered as orthogonal to the issues of optimality discussed here.
Using the axes of representational granularity and type (or compilation), a state space of potential representations is created (Figure 3). Each domain will have its own distribution of knowledge within this representational space. Some will be sparsely populated with heuristics and fragments of coarse models and others may be more formalised, composed of finer grained models. The problem now becomes, given a specific domain map of a knowledge base which shows how the space of representations is populated:
The basic depth defines the entry level for a problem solver. It is determined by choosing a level that is optimal for both intra and inter-representational measures. The measures of intra-representational optimality in general will make statements about the likelihood that the knowledge at a given level will be able to produce an adequate answer for a given query. Measures of inter-representational optimality will attempt to ensure that the computational constraints of space and time that come with the query are also met. Since in both cases, such measures may only be best guesses, there is always the possibility that the level selected is wrong.
There are thus a number of circumstances when a reasoning system needs to switch levels. The first is the failure of the current level to perform its task. Failure criteria may vary, but the basic notion here is that the level selected has been unable to produce a satisfactory answer for a given problem. While failure may be clear cut, a second condition arises when a level does not fail to produce an answer, but fails to produce a correct answer. Such an error may be hard to spot early on, and may pass unnoticed until a future failure indicates its presence. Blame assignment may be much more difficult then, and the cost of failure high.
The second set of circumstances relate to computational aspects of the query. Timeliness [15] is likely be useful in this context, and if a particular level is unable to produce an answer within a given time, then a reasoning system may be driven of necessity to seek an answer from a more shallow one.
It is likely that some decisions have already been made about the type of knowledge stored in a knowledge base, hopefully optimising the depth of compilation based upon an understanding of the queries most likely to be encountered. Thus space itself is unlikely to be a criterion used in dynamic level switching. The results of space trade-offs may however result in a level being incomplete. If one knows enough about the character of a query, and the state of completion of a particular level, then this can be used in the initial selection of an entry point. If levels are not uniformly incomplete, then a dynamic measure may be needed to suggest that the level selected is unsuitable. Uniform completeness is possible when one level is generated directly from a deeper one - a level may be not be uniformly complete if it is in some part hand constructed. Thus a rule base may have irregular gaps in it if it is built from scratch.
The limits to qualitative superposition mentioned previously are an example of a computational property that can be used to select an entry point into a hierarchy, and which can also be used to assist in level switching. They can be checked prior to commencing a diagnostic prediction, and define the conditions under which a reasoner must shift from histories to qualitative models.
Let us assume that there is a well populated (uniformly complete) representational hierarchy, and that storage has been optimised by filling shallow levels with common single diseases and interactions. For most queries that cannot be quickly dealt with at the shallow level, the intermediate history level will provide the basic depth or entry point. The deeper qualitative model will only be selected if the query related to a novel fault, or a disease interaction that cannot be computed using qualitative superposition.
If the knowledge represented is not uniform, as is most likely to be the case, then it will not always be possible to know prior to commencing a query whether a level is complete enough to serve the query, or whether inference procedures are always legal. For example, if QDHs are not derived from models, then there is no guarantee that superposition will be legal - an answer may be obtained but it may not be correct. If there is evidence that this is the case (perhaps the most difficult of switching conditions to detect) then a switch to the qualitative model level is indicated.
This paper has sought to outline the benefits of choosing optimally deep representations, and has offered the notion that intermediate depth representations are computationally optimal for many tasks. In the process of defining criteria for representational optimality, it was noted that no single depth of representation will be universally optimal. For reasoning systems that need to incorporate multiple representational levels, analysis of the trade-offs between levels can delineate conditions that identify the level best suited to deal with a given problem, and when to switch levels during problem solving. Proposals for inter and intralevel measures of optimality were made to assist in this decision.
Qualitative disease histories have been used as an example in case. For domains in which time varying disease behaviour is important, a history based system is potentially more robust and representationally efficient than shallower systems, and more computationally efficient than model based systems. Domains that do not have to contend with dynamic physiological behaviours will not need complex physiological models and qualitative histories. In such domains shallow, intermediate and deep representations may take a different form. It will be an interesting exercise to extend the present analysis to such domains.
Acknowledgments
Thanks are due to Graham Higgins who introduced me to the work of Eleanor Rosch and who, along with Tim Menzies, offered many useful comments on this paper.
References I. Bratko, I. Mozetic, N. Lavrac, Kardio - A Study in Deep and Qualitative Knowledge for Expert Systems, MIT Press, Cambridge, Ma. (1989).