Evolutionary design of plan based pattern recognition systems in complex domains

Abstract

Many real-life Pattern Recognition (PR) problems do not fit into the classical PR paradigms. Such systems are currently being implemented using knowledge-based approaches. Designing such systems is an involved, evolutionary process consisting of multiple stages. This work addresses the issues involved in systematic intelligent interactive support of this process within the framework of a plan-based architecture. The main PR task can be hierarchically broken up into multiple subtasks. Subtasks at the lowest level perform various types of actions for data gathering, information processing, hypothesis management, and information communication. Thus, a PR system can be implemented in the form of plans consisting of the optimal (or near-optimal) combination of such actions which specify what to do and when. From this viewpoint, the design task becomes that of planning for appropriate sequences of actions applicable for different states of problem solving. This leads to a new architecture based on planning to implement knowledge-based PR systems. Due to incompleteness, imprecision, and uncertainty in the users' specifications and the experts' knowledge, any particular design is only a tentative solution which needs to be refined again and again until satisfactory performance is achieved. We propose a systematic approach to support this evolutionary design cycle. In this design cycle, we first gather specifications for the required system from the users. In the knowledge acquisition phase, we analyze the structure of the given problem to identify the various tasks involved. For each of these tasks, we acquire the necessary knowledge from human experts and other knowledge sources. We represent all facets of this knowledge in the form of hierarchical influence diagrams which were originally used in decision analysis. We have adapted and extended the representation to model Pattern Recognition problems with a hierarchical domain structure, Dempster-Shafer Theory (DST)-based likelihood information, and possibly hostile environments. We provide an algorithm for estimating likelihood information in the form of DST belief functions from labeled samples. In the plan generation phase, we operationalize the declarative domain knowledge given by human experts, i.e., we generate procedural knowledge in the form of plans from the declarative knowledge in the form of a domain model. We present several new techniques and heuristic measures for deterministic and nondeterministic plan generation and plan refinement. We propose a new ? cutoff for pruning in addition to the usual ? and ? used in game trees. To improve the efficiency of the plan generation process, we define a new heuristic measure called merit for each evidence-gathering action and use various node ordering strategies. Meta-level decisions are introduced in the plan to help postpone certain assumptions during plan generation. We evaluate the generated plans to get directions for further improvements. Nondeterministic plans are evaluated based on a new heuristic called the index of focusing. For deterministic plans, we perform value-of-information analysis to find out which tasks or actions need further refinement. Suggestions for changes in system specifications to improve performance while maintaining the functionality of the system are generated using value-of-control analysis. These analyses may lead to replanning with slightly altered criteria, redesign of the system by acquiring additional knowledge, or reformulation of the problem itself by modifications in the specifications. The final plans are compiled into executable LISP code to generate the classifier. Performance of this classifier is assessed with respect to various criteria such as error rate, precision, recall, total cost, etc. This evaluation may also lead to redesign or reformulation. A design environment which supports this evolutionary process has been implemented using Common Lisp and Common Lisp Object System (CLOS) on a SUN workstation. We evaluate this methodology using the following four PR problems of progressively increasing complexity:

Classification of iris flowers Identification of ethnicity from names Limited vocabulary speech recognition in a voice-operated telephone dialer Multisensor integration and situation assessment