A formal model of diagnostic inference. I. Problem formulation and decomposition. (English) Zbl 0583.68046

This paper introduces a new model of diagnostic problem solving based on a generalization of the set-covering problem. The model formalizes the concepts of (1) whether or not a set of one or more disorders is sufficient to explain a set of occurring manifestations, (2) what a solution is for a diagnostic problem, and (3) how to generate all of the alternative explanations in a problem’s solution. In addition, conditions for decomposing a diagnostic problem into independent subproblems are stated and proven. This model is of interest because it captures several intuitively plausible features of human diagnostic inference, it directly addresses the issue of multiple simultaneous causative disorders, it can serve as a theoretical basis for expert systems for diagnostic problem solving, and it provides a conceptual framework within which to view some recent AI work on diagnostic problem solving in general.


68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Full Text: DOI


[1] Barrows, H., The diagnostic (problem solving) skill of the neurologist, Arch. neurol., 26, 273-277, (1972)
[2] Ben-Bassat, M.; Carlson, R.; Puri, V.; Davenport, M.; Schriver, J.; Latif, M.; Smith, R.; Portigal, L.; Lipnick, E.; Weil, M., Pattern-based interactive diagnosis of multiple disorders: the {\scmedas} system, IEEE trans. pattern anal. and machine intelligence, 2, 148-160, (1980)
[3] Card, W., The diagnostic process, ()
[4] Christofides, N.; Korman, S., A computational survey of methods for the set covering problem, Management sci., 21, 591-599, (1975) · Zbl 0314.65029
[5] de Dombal, F., Computer assisted diagnosis of abdominal pain, (), 10-19
[6] Edwards, J., Coverings and packings in a family of sets, Bull. amer. math. soc., 68, 494-499, (1962)
[7] Elstein, A.; Shulman, L.; Sprafka, S., Medical problem solving — an analysis of clinical reasoning, (1978), Harvard U.P
[8] Karp, R., Reducibility among combinatorial problems, (), 85-103 · Zbl 0366.68041
[9] Kassirer, J.; Gorry, G., Clinical problem solving—a behavioral analysis, Ann. int. med., 89, 245-255, (1978)
[10] Kingsland, L.; Sharp, G.; Capps, R., Testing of a criteria-based consultant system in rheumatology, (), 514-517
[11] Leaper, D., Clinical diagnostic process—an analysis, British med. J., 3, 569-574, (1973)
[12] Miller, R.; Pople, H.; Myers, J., {\scinternist}-1, an experimental computer-based diagnostic consultant for general internal medicine, New england J. med., 307, 468-476, (1982)
[13] Nau, D.; Markowsky, G.; Woodbury, M.; Amos, D., A mathematical analysis of human leukocyte antigen serology, Math. biosci, 40, 243-270, (1978) · Zbl 0394.92007
[14] Nau, D.; Reggia, J.; Wang, P., Knowledge-based problem solving without production rules, (), 105-108
[15] Nilsson, N., Principles of artificial intelligence, (), 37
[16] Nilsson, N., The interplay between experimental and theoretical methods in artificial intelligence, Cognition and brain theory, 4, 69-74, (1980)
[17] Pauker, S.; Gorry, G.; Kassirer, J.; Schwartz, W., Towards the simulation of clinical cognition, Amer. J. med., 60, 981-996, (1976)
[18] Pople, H., Heuristic methods for imposing structure on ill-structured problems: the structuring of medical diagnostics, (), 119-190
[19] Reggia, J., A production rule system for neurological localization, (), 254-260
[20] Reggia, J., Computer-assisted medical decision making, (), 198-213
[21] Reggia, J.; Nau, D.S.; Wang, P.Y., Diagnostic expert systems based on a set covering model, Internat. J. man-machine stud., 19, 437-460, (1983)
[22] Reggia, J.; Tabb, D.; Price, T., Computer-aided assessment of transient ischemic attacks: A clinical evaluation, Arch. neurol., (1984)
[23] Rouse, W., Human problem solving performance in a fault diagnosis task, IEEE trans. systems man cybernet., 8, 258-271, (1978)
[24] Rouse, W., Problem solving performance of maintenance trainees in a fault diagnosis task, Human factors, 21, 195-203, (1979)
[25] Rubin, A., The role of hypotheses in medical diagnosis, (), 856-862
[26] Shortliffe, E., Computer-based medical consultations: {\scmycin}, (1976), Elsevier New York
[27] Shubin, H.; Ulrich, J., {\scidt}: an intelligent diagnostic tool, (), 290-295
[28] Woodbury, M.; Ciftan, E.; Amos, D., HLA serum screening based on an heuristic solution of the set cover problem, Comput. programs biomed., 9, 263-273, (1979)
[29] Wortman, P., Representation and strategy in diagnostic problem solving, Human factors, 8, 48-53, (1966)
[30] Yu, V.; Buchanan, B.; Shortliffe, E., Evaluating the performance of a computer-based consultant, Comput. programs biomed., 9, 95-102, (1979)
[31] Zagoria, R.; Reggia, J., Transferability of medical decision support systems based on Bayesian classification, Med. decision making, 3, 501-510, (1983)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.