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 medas system, IEEE Trans. Pattern Anal. and Machine Intelligence, 2, 148-160 (1980)
[3] Card, W., The diagnostic process, (Abrams, Medical Computing (1970), American Elsevier)
[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, (Rose, J.; Mitchell, J., Advances in Medical Computing (1975), Churchill-Livingston: Churchill-Livingston New York), 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, (Miller, R.; Thatcher, J., Complexity of Computer Computations (1972), Plenum: Plenum New York), 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, (van Bemmel, J.; Ball, M.; Wigertz, O., Proceedings of MEDINFO-83 (1983), North Holland), 514-517
[11] Leaper, D., Clinical diagnostic process—an analysis, British Med. J., 3, 569-574 (1973)
[12] Miller, R.; Pople, H.; Myers, J., internist-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, (Proceedings of the 1983 Trends and Applications Conference (1983), IEEE Computer Society Press), 105-108
[15] Nilsson, N., Principles of Artificial Intelligence, ((1980), Tioga), 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, (Szolovits, P., Artificial Intelligence in Medicine (1982), Westview Press: Westview Press Boulder, Colo), 119-190
[19] Reggia, J., A production rule system for neurological localization, (Proceedings of the Second Annual Symposium on Computer Applications in Medical Care (1978), IEEE Press), 254-260
[20] Reggia, J., Computer-assisted medical decision making, (Schwartz, M., Applications of Computers in Medicine (1982), IEEE Press), 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, (Fourth International Joint Conference on Artificial Intelligence (1975)), 856-862
[26] Shortliffe, E., Computer-Based Medical Consultations: mycin (1976), Elsevier: Elsevier New York
[27] Shubin, H.; Ulrich, J., idt: An intelligent diagnostic tool, (Proceedings of the National Conference on Artificial Intelligence. Proceedings of the National Conference on Artificial Intelligence, AAAI (1982)), 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.