A formal model of diagnostic inference. II. Algorithmic solution and application. (English) Zbl 0583.68047
This paper and its part I [reviewed above; see Zbl 0583.68046] present the generalized set-covering (GSC) formalization of diagnostic inference. In the current paper, the GSC model is used as the basis for algorithms modeling the ”hypothesize-and-test” nature of diagnostic problem solving. Two situations are addressed: ”concurrent” problem solving, in which all occurring manifestations are already known, and sequential problem solving, in which the manifestations are discovered one at a time. Each algorithm is explained and its correctness within the GSC framework is proven. The utility of the GSC model is illustrated by using it to describe and analyze some recent abductive expert systems for diagnostic problem solving. The limitations of the basic form of the GSC model are then discussed. A more general notion of ”parsimonious covering” that includes the GSC model as a special case is then identified, and some important directions for further research are presented.
MSC:
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
Citations:
Zbl 0583.68046References:
| [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) · Zbl 0106.24201 |
| [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), IRRE Computer Society Press), 105-108 |
| [15] | Nilsson, N., Principles of Artificial Intelligence, ((1980), Tioga), 37 · Zbl 0422.68039 |
| [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, 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) |
| [32] | Aikins, J., Prototypical knowledge for experts systems, Artificial Intelligence, 20, 163-210 (1983) |
| [33] | Fahlman, S., netl—A System for representing and using real-world knowledge (1979), MIT Press: MIT Press Cambridge, Mass · Zbl 0444.68083 |
| [34] | Nau, D.; Reggia, J., Relationships between deductive and abductive inference in knowledge-based diagnostic problem solving, (Kerschberg, L., Proceedings of the First International Workshop on Expert Database Systems. Proceedings of the First International Workshop on Expert Database Systems, Kiawah Island, S.C. (October 1984)), 500-509 |
| [35] | Peng, Y., A general theoretical model of abductive diagnostic expert systems, TR-1402 (May 1984), Dept. of Computer Science, Univ. of Maryland |
| [36] | Pople, H.; Myers, J.; Miller, R., dialog: A model of diagnostic logic for internal medicine, (Proceedings of the Fourth International Joint Conference on Artificial Intelligence (1975)), 848-855 |
| [37] | Pople, H., The formation of composite hypotheses in diagnostic problem-solving: An exercise in synthetic reasoning, (Proceedings of the Fifth International Joint Conference on Artificial Intelligence (1977)), 1030-1037 |
| [38] | Reggia, J.; Nau, D., An abductive non-monotonic logic, (Proceedings of the Workshop on Non-monotonic Reasoning. Proceedings of the Workshop on Non-monotonic Reasoning, New Paltz, N.Y. (Oct. 1984)), 385-395 |
| [39] | J. Reggia, B. Perricone, D. Nau, and Y. Peng, Answer justification in diagnostic expert systems, IEEE Trans. Biomed. Eng.; J. Reggia, B. Perricone, D. Nau, and Y. Peng, Answer justification in diagnostic expert systems, IEEE Trans. Biomed. Eng. |
| [40] | Tagamets, M.; Reggia, J., Abductive hypothesis formation and refinement during construction of natural system models, TR-1463 (Jan. 1985), Dept. of Computer Science, Univ. of Maryland |
| [41] | James A. Reggia, Dana S. Nau, and Pearl Y. Wang, A formal model of diagnostic inference. I. Problem formulation and decomposition, Inform. Sci.; James A. Reggia, Dana S. Nau, and Pearl Y. Wang, A formal model of diagnostic inference. I. Problem formulation and decomposition, Inform. Sci. · Zbl 0583.68046 |
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.
