Developing industrial CaseBased Reasoning (CBR) applications has become much easier since the advent of the INRECA methodology which employs software process modelling techniques to describe the development tasks, and which uses the experience factory approach to store the experience gained during the implementation of CBR projects. But the INRECA methodology does not describe how to maintain the developed systems in detail. This paper describes how to develop maintainable CBR systems by applying the six step CBR process model of the SIAM methodology to CBR applications using empolis orenge.
Developing industrial CaseBased Reasoning (CBR) applications has become much easier since the advent of the INRECA methodology [BBG+99]. The INRECA methodology provides a data analysis framework for developing CBR solutions for successful applications in realworld industrial contexts. It employs software process modelling techniques to describe the development tasks [VR95], and it uses the experience factory approach [BCR94] to store the experience gained in the realization of CBR projects. empolis developed many applications using the INRECA methodology, and those applications are running for several years now, making structured maintenance processes like the SIAM methodology [RB02] and the maintenance manual MAMA [RBR01] a necessity. But structured maintenance processes are not enough. The maintained system must be maintainable by design. empolis orenge [Sch02a] provides such a maintainable system core, not only for commercial use but also for academic research.
This paper is structured as follows: After introducing maintenance in the next section, and a look at related work, the six step process model and the broader context of the SIAM methodology is revisited in section 4. Section 5, then, relates empolis orenge to the six step process model and maps the terminology of empolis orenge to that of SIAM. The paper closes with some concluding remarks.
The control loop is the essential metaphor for the maintenance of any system (Figure 1). An ideal system becomes faulty because of defects. In software systems, the defects are not caused by parts wearing out but by the ever changing environment. And knowledge based systems are especially sensitive to those changes.
repair
defect
Obviously, changes must be discovered before one can react to them. As soon as changes are recognized, especially those changes that have negative effects on the system, the faulty system can be repaired. It can be brought back to a desired state of functionality. Figure 2 shows just one possible sequence of CBR system states, where defects and repairs are following each other. As soon as the quality level of the system drops beyond some limit, repair operations are executed until the system reaches some satisfactory quality level. + st1 defect(s) st2 repair st3 The CBR system very well may stay unchanged during the time its quality drops, because the states are system states in relation to the environment. The repair operations change the CBR system (and, normally, not the environment). For example, in electronic commerce scenarios similarity measures often model user preferences (i.e., the more a customer prefers a product, the more similar is the product to the customer's query). Over time, the customers may change their minds on the products (i.e., their preference relation, which is part of the environment of the CBR system, may change). Assumed, there are no maintenance actions in the meantime and the similarity model also stays the same. When those customers return to the CBR system and ask the same questions they will get the same answer. But this time, they may be unsatis ed with the results and reject the answers because they do not match their preference models anymore. 3
Many single maintenance methods have been developed over the years, but a comprehensive process model was missing. A rst comprehensive work was provided by Wilson [Wil01]. In his dissertation, he focuses on the overall case base maintenance problem in CBR and describes new maintenance techniques within that paradigm. He presented a framework for describing case base maintenance techniques and classi ed existing systems according to this schema. The theoretical work is supported by new methods and experiments. Wilson generalized the framework to cover all knowledge containers, and provided an example of similarity maintenance.
The framework is analytical in nature and does not directly support one in developing better maintainable CBR systems. It is based on existing CBR process models. It also does not directly help in developing maintenance policies for particular CBR applications. Another eld, where research is conducted, is the eld of experience base maintenance [NA00a]. The experience base is a storage facility for experience packages in an organizational unit called experience factory [BCR94]. An experience base is also the basis of the INRECA methodology.
Experience packages are cases with a complex structure. Therefore, maintenance efforts focus on maintaining and improving the value of single experience packages and, following from that, maintaining and improving the value of the experience base. This is done based on the GoalQuestionMetric paradigm for goaloriented software engineering measurement [BCR94]. The Corporate Information Network (COIN) which is the Fraunhofer IESE experience factory is used to validate the maintenance efforts [JAD+01] and to develop guidelines for evaluation and improvement of experience bases [NF00, NA00b] as well as for support for acquiring new cases using already gained maintenance knowledge [NA01].
Maintaining an experience base, is maintenance of a class of CBR applications. Therefore, experience base maintenance, in principle, can be described using the SIAM methodology within a particular context.
Looking at maintenance, in general, and having the control loop metaphor in mind, one discovers that the traditional CBR process models (i.e., the CBR owchart according to Riesbeck and Bain [RB87], the CBR cycle of Kolodner [Kol93], and the four steps process model according to Aamodt and Plaza [AP94]) cannot suf ciently describe maintenance issues. Therefore, the most in uential and widely acknowledged process model of Aamodt and Plaza was enhanced by the two additional steps Review and Restore [RIRB01]. This six step process model, then, was embedded into the SIAM methodology for knowledge maintenance of CBR systems. 4.1
The process model of Aamodt and Plaza [AP94] comprises the four steps Retrieve, Reuse, Revise, and Retain, with the rst three steps grouped as problem solving phase and Retain as learning phase. The two phases are the basis for the six step process model with the two phases renamed to application phase and maintenance phase in the context of SIAM [RBI01, RIRB01].
Maintenance Phase
Application Phase Knowledge
Problem Review
Kknowledge ccoonnttaaiinneerrss''
Knowledge containers
Reuse Retain Restore
Retrieve
Revise
To collect information useful for maintenance, the existing steps were enhanced because each step provides opportunities to gather information as how often a case was retrieved, automatically adapted, or revised by users.
But the minor enhancement of the existing steps was not enough. There was no possibility to describe the necessary operations on how to assess the quality of the current system state, and to express necessary repair operations. Thus, the two new steps Review and Restore were added to the maintenance phase.
CBR system at time t
Retrieve Retain
Reuse The Review step considers the current state of a CBR system (cf. Figure 4, which shows just one possible ow of control in SIAM). It assesses its quality, and invokes Restore within the maintenance phase if necessary. The Restore step, then, changes the contents of the CBR system to bring it back to a desired level of quality. If there is no need to go to the Restore step, since the quality values are still in good shape, this step is simply skipped. But the enhanced steps and the extended process model were only a rst step. The six steps needed to be part of a broader context. 4.2
The development of CBR systems and applications has to be part of every maintenance effort. The SIAM methodology provides this broader context, comprising Setup, Initialization, Application and Maintenance of a CBR project [RBR01]. SIAM drew concepts from two already existing methodologies: the INRECA methodology [BBG+99] and the CRoss Industry Standard Process for Data Mining CRISPDM [CCK+00]. Both methodologies describe, how to develop software projects, but, of course, regarding two different elds.
SETUP
INITIALIZATION
APPLICATION
MAINTENANCE INRECA
SIAM Each of the phases is decomposed into tasks that are described on three levels of abstraction (see [RBR01] for examples): generic, speci c, and instance. The speci c level is identi ed with a maintenance manual that, in principle, describes all the necessary tasks to perform maintenance. It describes when to do what. The 'when' is decomposed into an event and a condition. An event is easy to recognize and can be a time running out, a new document coming in, or some user feedback. The event, then, triggers the evaluation of some (usually more complex or time consuming) condition such as a check for all outdated or incorrect cases of the case base. As soon as a condition is satis ed the action, described in the manual, is performed.
The generic level describes each task in an, of course, generic way. To make use of the generic task, the notion of the SIAM context was introduced that maps the generic to the speci c level. The SIAM context speci es the type of CBR system, the type of CBR application, the CBR tool used, and the most affected knowledge container. These are regarded the most important dimensions for the description of the speci c level. The instance level further specializes the speci c level. It is an instantiation of the speci c maintenance policies. This level is identi ed with particular projects where parameters of the speci c level are set to concrete values. 4.3
Obviously, the SIAM methodology would be useless without operationalizing it, but the utilization of SIAM is already contained in the structure of the methodology. SIAM is operational by design. A major driving force for the development of SIAM always was to have an immediately applicable methodology. The construction of SIAM with its three levels of abstraction was a result of reusing practical experiences with methodologies, experiences both with developing and using the INRECA methodology in CBR projects as well as with developing and using CRISPDM in data mining projects.
SIAM fully describes maintenance policies on a generic level. As soon as a maintenance manual is described on the speci c level every project developed using the INRECA methodology and performed in that particular SIAM context can be maintained easily. Additionally, computerbased maintenance support can be provided by a management system that implements SIAM (an example system is described in [Max01]). But, in general, maintenance is organized and performed by humans rather than computers. The INRECA methodology already is used at empolis to develop CBR applications and to constantly improve the quality of the CBR application development process. Consequently, the SIAM methodology (which enhances the INRECA methodology) is also being used, supporting the Total Quality Management efforts of empolis by maintaining the quality of running CBR applications. 5
empolis orenge A maintainable CBR platform empolis orenge [Sch02b] is a Structural and Textual CaseBased Reasoner.1 It implements all four steps of the traditional CaseBased Reasoning cycle [AP94]. The orenge: Controller provides the steps Retrieve, Reuse, and Revise (of the problem solving or application phase) in form of the orenge:Services Retrieval (for Retrieve and Reuse), and Adaptation (for Revise). The orenge: Controller also implements the Retain step (the only step of the learning or maintenance phase of the traditional CBR cycle). This allows for online integration of cases. But most of the time, cases are integrated of ine using the orenge: CaseBaseBuilder. The resulting new case base then replaces the older version in the productive system. 5.1
Additionally to the orenge: Controller with its xed ow of control, a new con gurable reasoner has been developed. Since empolis orenge Release 3.2, this reasoner, called orenge: ProcessManager, allows to build complex reasoning pipelines. The reasoning pipelines are a sequence of pipelets. Each pipelet provides one of the existing orenge:Services such as Retrieval and Adaptation. A uniform programming interface allows for an easy addition of customized pipelets. For instance, after retrieving cases similar to a query, the results could be checked if there are enough cases retrieved. A second retrieval (or as many retrievals as needed) can be started until enough cases are available. The cases can be adapted, altered algorithmically, or tested if they conform to any constraints. In an electronic commerce scenario, the stock could be checked if the retrieved products are available, before presenting the retrieval results to the customer. There are as many possibilities as can be programmed.
1A description of CBR approaches can be found in, e.g., [Len99] or [BBG+99] Furthermore, with the orenge: ProcessManager, empolis orenge is capable to implement appropriate support for the two steps Review and Restore. The enhancements of the original four steps, as described in [RBI01], could be implemented easily as pipelets, and according to the needs of the respective CBR project. If performance requirements do not allow for jointly collecting maintenance information and executing assessment tasks during problem solving, the queries could be sent to a second instance of the orenge: ProcessManager that is running in parallel. This reasoner could be reserved for collecting maintenance information such as performance measures or the amount of unknown concepts in queries, whereas the other instance is used for problem solving. The load balancing, in this scenario, would be handled by the orenge: RequestBroker. Review and Restore are, then, covered by the speci c level of the SIAM methodology. 5.2
In 1995, Richter [Ric95] introduced the notion of the knowledge containers that contain and structure the knowledge of a casebased reasoner. A knowledge container is a collection of knowledge that is relevant to many tasks rather than to one. Prominent knowledge containers in rulebased systems, for instance, are facts and rules. Richter identi ed the following four knowledge containers of CaseBased Reasoning systems: The vocabulary (attributes, predicates etc.) comprises the domain model. The similarity measures are used to compare cases with queries. The adaptation knowledge accommodates past solutions to current problems. The case base stores the cases. Vocabulary
Case base Similarity measures
Adaptation knowledge The knowledge for the rst three containers is described and used during development of a CBR system (i.e., at compile time), while the knowledge in the cases is utilized only during actual problem solving (i.e., at runtime).
The four knowledge containers and their relation to each other are shown in Figure 6. The arrows depict that knowledge can be transferred from one knowledge container to the other. The vocabulary knowledge obviously is the foundation of all of the other three containers.
In empolis orenge, the knowledge containers could be identi ed quite easily. The knowledge containers are mapped onto empolis orenge's XMLbased languages as shown in Table 1. The acronyms are explained in the following. The vocabulary consists of classes and concepts. They comprise the data model and are de ned using the orenge model markup language (OMML). As soon as the textmining2 capabilities of empolis orenge are used, keys as synonyms to corresponding concepts must be de ned. The keys are used to identify the concepts in queries given as free texts or during case base building. The keys comprise the analysis model and are de ned using the orenge analysis markup language (OAML).
The case base exists in three avors: as a list of cases, as an index, or as an SQL database.
The list of cases is described in the orenge object markup language (OOML). This type of case base is used by the retrieval component orenge: KnowledgeServer/Linear. This retriever is the most capable one. There are no limitations on the similarity measures. Complex calculations are possible, but, then, the performance of this retriever can be a problem if the number of cases is too big.
The index basically is a Case Retrieval Net (CRN) [Len99]. It is used by the orenge: KnowledgeServer/Index. This kind of retriever is limited regarding the similarity calculations to some degree (For more details, please, refer to the empolis orenge documentation). The index as well as the linear case base usually are created using the orenge: CaseBaseBuilder. It transforms text documents or structured data, such as data from a database or XML repository, into the appropriate representation, i.e., 2The orenge: Textminer provides information extraction capabilities for Textual CBR.
into a CRN representation or into an OOML le (where the orenge: CaseBaseBuilder is an implementation of the Retain step). In the following the terms index and case base are used interchangeably.
Whereas the rst two kinds of case bases require a transformation step to get the cases, the original data of an SQL database is used directly. Here, CBR is performed on top of the relational database [SB00b, SB00a]. This kind of retrieval is used by the orenge: KnowledgeServer/SQL.
The similarity measures (for all of the three kinds of case bases) are described by the valuation model. It is de ned using the orenge valuation markup language (OVML). The valuation model is extended with general knowledge provided by completion rules that are de ned using the orenge rule markup language (ORML). Completion rules are used to modify the query, to infer additional information from that given by the user. They also could be used during the case base building process.3 empolis orenge uses adaptation rules for the execution of the Revise step. The adaptation rules also are de ned using ORML. Usually, the completion rules and the adaptation rules are different, but in principle they could be used for both purposes, for the completion of queries and for adapting retrieved cases because cases and queries share the same structure. 6
This paper presented the SIAM methodology for knowledge maintenance of CaseBased Reasoning systems [RB02]. The paper shortly revisited the six step process model in the broader context of SIAM. It showed the relation between INRECA and SIAM, and applied the concepts of SIAM to empolis orenge.
The SIAM methodology is the basis for strong industrial CaseBased Reasoning applications at empolis, because it not only supports in developing such applications but also in maintaining them. empolis orenge is an advanced product coming from research and providing many of the features developed by the CBR community over the years. Its exibility also makes it a good starting point for further research. [AP94]
3Additional information about the completion of cases and queries using rules can be found in [Wes95]. [BCR94]
Victor R. Basili, Gianluigi Caldiera, and H. Dieter Rombach. The Experience Factory. In J. Marciniak, editor, Encyclopedia of Software Engineering, pages 469476. Wiley, New York, 1994. [CCK+00] Pete Chapman, Julian Clinton, Randy Kerber, Thomas Khabaza, Thomas Reinartz, Colin Shearer, and Ru¨diger Wirth. CRISP-DM 1.0: StepbyStep Data Mining Guide. CRISP-DM consortium: NCR Systems Engineering Copenhagen (USA and Denmark) DaimlerChrysler AG (Germany), SPSS Inc. (USA) and OHRA Verzekeringen en Bank Groep B.V (The Netherlands), 2000. [JAD+01] Andreas Jedlitschka, Klaus-Dieter Althoff, Bjo¨rn Decker, Susanne Hartkopf, and Markus Nick. Corporate Information Network (COIN): The Fraunhofer IESE Experience Factory. In Rosina Weber and Christiane Gresse von Wangenheim, editors, Proceedings of the Workshop Program at the Fourth International Conference on Case Based Reasoning, ICCBR 2001, Vancouver, Canada, pages 920, Washington, DC, 2001. Navy Center for Applied Research in Arti cial Intelligence, Naval Research Laboratory, Code 5510. [Kol93] [Len99] [Max01] [NA00a] [NA00b] [NA01] [NF00] [RB87] [RB02]
Janet Kolodner. CaseBased Reasoning. Morgan Kaufmann Publishers, Inc., 2929 Campus Drive, Suite 260, 1993.
Mario Lenz. Case Retrieval Nets as a Model for Building Flexible Information Systems. Dissertation, MathematischNaturwissenschaftliche Fakulta¨t II der Humboldt Universita¨t zu Berlin, Humboldt University, Berlin, 1999.
Rainer Maximini. Base system for Maintenance of a CaseBased Reasoning System. Diploma thesis, University of Kaiserslautern, 2001.
Markus Nick and Klaus-Dieter Althoff. The Challenge of Supporting Repository-Based Continuous Learning with Systematic Evaluation and Maintenance. IESE Report No. 017.00/E, 2000.
Markus Nick and Klaus-Dieter Althoff. Systematic Evaluation and Maintenance of Experience Bases. In Mirjam Minor, editor, ECAI Workshop Notes Flexible Strategies for Maintaining Knowledge Containers, pages 1421, Berlin, 2000. Humboldt University. Markus Nick and Klaus-Dieter Althoff. Acquiring and Using Maintenance Knowledge to Support Authoring for Experience Bases. In Rosina Weber and Christiane Gresse von Wangenheim, editors, Proceedings of the Workshop Program at the Fourth International Conference on CaseBased Reasoning, ICCBR 2001, Vancouver, Canada, pages 38 41, Washington, DC, 2001. Navy Center for Applied Research in Arti cial Intelligence, Naval Research Laboratory, Code 5510.
Markus M. Nick and Raimund L. Feldmann. Guidelines for Evaluation and Improvement of Reuse and Experience Repository Systems Through Measurement Programs. In Proceedings of the 3rd European Software Measurement Conference (FESMA-AEMES 2000), 2000.
C. Riesbeck and W. Bain. A Methodology for Implementing CaseBased Reasoning Systems. Technical report, Lockheed, 1987. [RBR01] [SB00a] [Sch02a] [VR95] [Wes95] [Wil01]