Incremental knowledge acquisition for search control heuristics
Ghassan Beydoun · UNSWorks (University of New South Wales, Sydney, Australia) · 2022
In recent years of development of expert systems, it has become evident that knowledge provided by the expert is always context dependent. This led to new modern incremental knowledge acquisition methodologies which aim to incrementally reconstruct experts knowledge in the context of its use. This thesis presents such a framework to model expert search processes. This by-passes the difficult, costly time-consuming task of developing effective domain specific heuristics. Adopting incremental knowledge acquisition is also justified because experts do not normally have complete introspective access to their search knowledge. They tend to give justifications of their search considerations rather than a complete explanation. We target at the implicit representation of the less clearly definable quality criteria by allowing the expert to limit their expressed knowledge to explanations of the steps in the expert search process. For the basis of our knowledge acquisition (KA) approach, we substantially extend the work done on Ripple Down Rules which allows knowledge acquisition and maintenance, without analysis or a knowledge engineer. Our extension allows the expert to enter his/her own domain terms during the KA process, thus the expert provides a knowledge level model of his/her search process. We call this framework Nested Ripple Down Rules (NRDR). Our NRDR formalism also addresses some shortcomings of RDR which have been a concern of substantial research efforts in the past few years: repetition, lack of explicit modelling and readability. The way our approach deals with these shortcomings is evaluated against recent work. Another significant contribution of this thesis is a formal framework for analysing the knowledge acquisition process RDR in general and NRDR in particular. Using this framework, we show that maintenance of an NRDR knowledge base (KB) requires similar effort to maintaining RDR for most of the KB development cycle. We show that when an NRDR KB shows an increase in maintenance requirement in comparison with RDR KB during its development, this added requirement can be automatically handled using past seen cases without the need for further interactions with the expert. Hence, because the NRDR framework avoids repetition, the number of interactions with the expert required for an NRDR knowledge base to converge is less than that for an RDR knowledge base in the same domain. Finally, we employ our approach to incrementally acquire expert chess knowledge for performing a highly pruned tree search. These experimental results in the chess domain are a clear evidence for the practicality of our approach.