Case Base Maintenance (CBM)IntroductionDefinitionStandard CBR learningKnowledge-based Systems Utility ProblemTraditional Deletion PoliciesRemembering to ForgetCoverage and ReachabilityCase Competence CategoriesCase Competence Categories (Cont.)Slide 11Slide 12Modeling Case CompetenceThe Footprint Deletion PolicyThe Footprint Deletion AlgorithmThe Footprint Utility Deletion PolicyFurther ApplicationsCBR systems Authoring ProcessCASCADE (Case Authoring Support & Development Environment)Competence GroupsThe Evolution of CompetenceThe Competence Visualization ToolCompetence RegionsThe Competence Visualization Tool – ExamplesThe Competence Visualization Tool – Examples (Cont.)ConclusionReferencesCase Base Maintenance(CBM)Fabiana PrabhakarCSE 435November 6, 2006IntroductionThe growing use of CBR applications has brought with it increased awareness of the importance of case-base maintenance (CBM).Large scale CBR systems are becoming more prevalent, with case library sizes ranging from thousands to millions of cases.Large case-bases raises concern about the utility problem for case retrieval, underlining the potential need to control case-base growth through case deletion policies.DefinitionCBM is the process of refining a CBR system’s case base to improve the system’s performance.Standard CBR learningThe system always add each new case to the case base.Domain expert adds a variable number of new cases. Indexing of the cases.Knowledge-based Systems Utility ProblemThe cost associated with searching for relevant knowledge outweighs the benefit of applying the knowledge.Traditional Deletion PoliciesA simple deletion policy is random deletion. According to this policy a random item is removed from the knowledgebase once the knowledge-base size exceeds some predefined limit. Minton’s utility metric [Minton, 1990]. Chooses a knowledge item for deletion based on an estimate of its performance benefits. Utility=(ApplicationFreq*AverageSavings)-MatchCostRemembering to Forget Competency Preserving Case Deletion Policy for CBR Systems (Smyth and Keane, 1995)Coverage and ReachabilityCoverage of a case is the set of target problems that can be solved by such case.Reachability of a target problem is the set of cases that can be used to provide a solution for the target problem.Case Competence CategoriesPivotal Cases: its deletion directly reduces the competence of the system. A case is pivotal if it is reachable by no other case but itself.Auxiliary Cases: do not effect competence at all. A case is auxiliary case if the coverage it provides is subsumed by the coverage of one of its reachable cases.Case Competence Categories (Cont.)Spanning Cases: do not directly affect the competence. Their coverage spaces link regions of the problem space that are independently covered by other cases. If cases from this linked regions are deleted, then the spanning case might be necessary. Support Cases: a special class of spanning cases. They exist in groups. The deletion of the group is analogous to removing a pivotal case.Case Competence Categories (Cont.)Case Competence Categories (Cont.)The case categories provide a means of ordering cases for deletion in terms of their competence contributions. 1. Auxiliary cases (they make no direct contribution to competence)2. Support cases3. Spanning cases4. Pivotal cases.Modeling Case CompetenceCompetence categories are computed at start-up.During future problem solving as cases are learned, the case categories must be updated:1. Re-compute the coverage and reachability sets of the appropriate cases;2. Adjust the categories accordingly.The Footprint Deletion PolicyIdeally a deletion policy should work to remove irrelevant cases guiding the case-base toward an optimal configuration of cases.Competence Footprint is this optimal case-base. It provides the same competence of the entire case-base but with fewer cases.The Footprint Deletion AlgorithmDeleteCase(Cases):If there are auxiliary cases thenSelectA uxiliary(AuxiliaryCases)ElseIf there are support cases thenWith the largest support groupSelectSupport(SuportGroup)ElseIf there are spanning cases thenSelectSpanning(SpanningCases)ElseIf there are pivotal cases thenSelectP ivot(PivotalCases)EndifThe Footprint Utility Deletion PolicyCombine Footprint and Utility Deletion:Minton’s utility metric – An item is selected based on an estimate of its performance benefits.Utility = (ApplicationFreq * AverageSavings) – MatchCostThe footprint method is used to select candidates for deletion. If there is only one such candidate then it is deleted. If, however, there a number of candidates, then rather than selecting the one with the least coverage or largest reachability set, the candidate with the lowest utility is chosen. In other words the utility metric is used within the SelectPivot, SelectSpanning, SelectSupport, and SelectAuxiliary procedures.Further ApplicationsThe competence modeling approach may be used during the initial case acquisition stage of system development. It is often undesirable to store every available case in the initial case-base.1. Utility Problem;2. Irrelevant cases may introduce noise into the retrieval stage and lead to the selection of suboptimal cases or difficulties in tuning the similarity metric.The competence modeling approach may be used during the authoring process.CBR systems Authoring ProcessCase base authoring can be a long, difficult, and tedious process, and the only advice given to the author is often of the “choose representative cases” variety. This can ultimately lead to the development of poor case bases, which offer limited coverage of the target problem space, and which include significant redundancy.CASCADE (Case Authoring Support & Development Environment)Keeps the knowledge engineer informed about how case authoring is progressing, and in particular, how case base competence is evolving.Extends the case competency model proposed by Smyth and Keane.Competence GroupsA competence group is a collection of related cases.The key idea underlying the definition of a competence group is that of shared coverage. Two cases exhibit shared coverage if their coverage or reachability sets overlap.The Evolution of CompetenceIn general as cases are added to the case base one of four things can happen:1. New groups are created;2. Existing competence groups grow in