Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-22T14:52:32.641Z Has data issue: false hasContentIssue false
  • English
  • Français

Principles and practice in verifying rule-based systems*

Published online by Cambridge University Press:  07 July 2009

Alun D. Preece ,
Rajjan Shinghal  and
Aïda Batarekh
Alun D. Preece
Affiliation:
Centre for Pattern Recognition and Machine Intelligence, Department of Computer Science, Concordia University, 1455 de Maisonneuve Boulevard West, Montreal, Canada H3G IM8
Rajjan Shinghal
Affiliation:
Centre for Pattern Recognition and Machine Intelligence, Department of Computer Science, Concordia University, 1455 de Maisonneuve Boulevard West, Montreal, Canada H3G IM8
Aïda Batarekh
Affiliation:
Centre for Pattern Recognition and Machine Intelligence, Department of Computer Science, Concordia University, 1455 de Maisonneuve Boulevard West, Montreal, Canada H3G IM8
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper surveys the verification of expert system knowledge bases by detecting anomalies. Such anomalies are highly indicative of errors in the knowledge base. The paper is in two parts. The first part describes four types of anomaly: redundancy, ambivalence, circularity, and deficiency. We consider rule bases which are based on first-order logic, and explain the anomalies in terms of the syntax and semantics of logic. The second part presents a review of five programs which have been built to detect various subsets of the anomalies. The four anomalies provide a framework for comparing the capabilities of the five tools, and we highlight the strengths and weaknesses of each approach. This paper therefore provides not only a set of underlying principles for performing knowledge base verification through anomaly detection, but also a survey of the state-of-the-art in building practical tools for carrying out such verification. The reader of this paper is expected to be familiar with first-order logic.

Type
Research Article
Information
The Knowledge Engineering Review , Volume 7 , Issue 2 , June 1992 , pp. 115 - 141
Copyright
Copyright © Cambridge University Press 1992

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Batarekh, A, Preece, AD, Bennett, A and Grogono, P, 1991, “Specifying an expert system” Expert Systems with Applications 2(4) 285–303.CrossRefGoogle Scholar
Bundy, A, 1988, “How to improve the reliability of expert systems” In: Moralee, DS (ed.), Research and Development in Expert Systems IV: Proc. Expert Systems 87, pp 3–17, Cambridge University Press.Google Scholar
Chang, CL, Combs, JB and Stachowitz, RA, 1990a, “A report on the expert systems validation associate (EVA)” Expert Systems with Applications 1(3) 217–230.CrossRefGoogle Scholar
Chang, CL, Stachowitz, RA and Combs, JB, 1990b, “Validation of nonmonotonic knowledge-based systems” In: A Dollas, WT Tsai and NG Bourbakis (eds.), Proc. 2nd International Conference on Tools for Artificial Intelligence (TAI-90), pp 776–782. IEEE.Google Scholar
Cragun, BJ and Steudel, HJ, 1987, “A decision-table-based processor for checking completeness and consistency in rule-based expert systems” International Journal of Man-Machine Studies 26(5) 633–648.CrossRefGoogle Scholar
de Kleer, J, 1986, “An assumption-based TMS” Artificial Intelligence 28(2) 127–162.CrossRefGoogle Scholar
Giarratano, J and Riley, G, 1989, Expert Systems: Principles and Programming PWS-Kent, New York.Google Scholar
Ginsberg, A, 1988 “Knowledge-base reduction: A new approach to checking knowledge bases for inconsistency & redundancy” In: Proc. 7th National Conference on Artificial Intelligence (AAAI88), volume 2, pp 585–589.Google Scholar
Ginsberg, A, 1990, “Theory reduction, theory revision, and retranslation” In: Proc. 8th National Conference on Artificial Intelligence (AAAI 90), pp 777–782, MIT Press.Google Scholar
Ginsberg, A and Williamson, K, 1989, Checking quasi-first-order-logic rule-based systems for inconsistency and redundancy Technical Report 11354–891229–02TM, AT & T Bell Laboratories, Holmdel, NJ.Google Scholar
Jackson, P, Reichgelt, H and van Harmelin, F, 1989, Logic-based Knowledge Representation MIT Press.Google Scholar
Jacob, RJK and Froscher, JN, 1990, “A software engineering methodology for rule-based systems” IEEE Transactions on Knowledge and Data Engineering 2(2) 173–189.CrossRefGoogle Scholar
Laurent, JP and Ayel, M, 1989, “Off-line coherence checking for knowledge based systems” In: IJCAI-89 Workshop on Verification, Validation and Testing of Knowledge-Based Systems. IJCAI.Google Scholar
McGuire, JG, 1990, “Uncovering redundancy and rule-inconsistency in knowledge bases via deduction” In: Proc. 5th Annual Conference on Computer Assurance: Systems Integrity, Software Safety, and Process SafetyIEEE.CrossRefGoogle Scholar
Mendelson, E, 1979, Introduction to Mathematical Logic. Van Nostrand.Google Scholar
Nazareth, DL, 1989, “Issues in the verification of knowledge in rule-based systems” International Journal of Man-Machine Studies 30(3) 255–271.CrossRefGoogle Scholar
Newell, A, 1981, “The knowledge level” AI Magazine 2(2) 1–20.Google Scholar
Nguyen, TA, 1987, “Verifying consistency of production systems” In: Proc. 3rd Conference on Artificial Intelligence Applications, pp 4–8, IEEE.Google Scholar
Nguyen, TA, Perkins, WA, Laffey, TJ and Pecora, D, 1985, “Checking an expert systems knowledge base for consistency and completeness” In: Proc. 9th International Joint Conference on Artificial Intelligence (IJCAI 85), volume 1, pp 375–378, AAAI.Google Scholar
Nguyen, TA, Perkins, WA, Laffey, TJ and Pecora, D, 1987, “Knowledge base verification” AI Magazine 8(2) 69–75.Google Scholar
Perkins, WA, Laffey, TJ, Pecora, D and Nguyen, TA, 1989, “Knowledge base verification” In: Guida, G and Tasso, C (eds.), Topics in Expert System Design, pp 353–376, North-Holland.Google Scholar
Preece, AD, 1989, “Verification of rule-based expert systems in wide domains” In: Shadbolt, N (ed.), Research and Development in Expert Systems VI: Proc. Expert Systems 89, pp 66–77, Cambridge University Press.Google Scholar
Preece, AD, 1990, “Towards a methodology for evaluating expert systems” Expert Systems 7(4) 215–223.CrossRefGoogle Scholar
Preece, AD and Shinghal, R, 1991, “Practical approach to knowledge base verification” In: Trivedi, M (ed.), Proc. Applications of Artificial Intelligence IX, pp 608–619, SPIE, Bellingham WA.Google Scholar
Preece, AD, Shinghal, R and Batarekh, A, 1992, “Verifying expert systems: a logical framework and a practical tool” Expert Systems with Applications 4(2/3).Google Scholar
Puuronen, S, 1987, “A tabular rule-checking method” In: Proc. 7th International Workshop on Expert Systems and their Applications, pp 257–268, Paris-La Défense. Agence Inf.Google Scholar
Rousset, MC, 1988, “On the consistency of knowledge bases: the COVADIS system” Computational Intelligence 4(2) 166–170. (Also in ECAI88, Proc. European Conference on AI Munich, August 1–5 1988, pp 79–84.)CrossRefGoogle Scholar
Stachowitz, RA and Combs, JB, 1987, “Validation of expert systems” In: Proc. 20th Annual Hawaii International Conference on System Sciences, volume 1, pp 686–695.Google Scholar
Stachowitz, RA, Combs, JB and Chang, CL, 1987, “Validation of knowledge-based systems” In: Proc. 2nd AIAA/NASA/USAF Symposium on Automation, Robotics and Advanced Computing for the National Space Program, pp 1–10. Report No. AIAA-87–1685.CrossRefGoogle Scholar
Suwa, M, Scott, AC and Shortliffe, EH, 1982, “An approach to verifying completeness and consistency in a rule-based expert system” AI Magazine 3(4) 16–21.Google Scholar
VALID, 1988, Validation methods and tools for knowledge-based systems. Deliverable, ESPRIT II VALID Project 2148.Google Scholar
Weilinga, B and Schreiber, G, 1989, “Future directions in knowledge acquisition” In: Shadbolt, N (ed.), Research and Development in Expert Systems VI: Proc. Expert Systems 89, pp 288–301, Cambridge University Press.Google Scholar