Adaptive AI Engine for RTS Games

Discussing the theory and practice

Summary of Case-Based Reasoning Foundational Issues, Methodological Variations, and System Approaches

Posted by Ogail on October 26, 2009

  • Abstract:
    • Case-based reasoning is a recent approach to problem solving and learning that has got a lot of attention over the last few years. Originating in the US, the basic idea and underlying theories have spread to other continents, and we are now within a period of highly active research in case-based reasoning in Europe, as well. This paper gives an overview of the foundational issues related to case-based reasoning, describes some of the leading methodological approaches within the field, and exemplifies the current state through pointers to some systems. Initially, a general framework is defined, to which the subsequent descriptions and discussions will refer. The framework is influenced by recent methodologies for knowledge level descriptions of intelligent systems. The methods for case retrieval reuse, solution testing, and learning are summarized, and their actual realization is discussed in the light of a few example systems that represent different CBR approaches. We also discuss the role of case-based methods as one type of reasoning and learning method within an integrated system architecture
  • Introduction:
    • CBR is able to utilize the specific knowledge of previously experienced, concrete problem situations (cases).
    • Why to read this paper (2enta 2eshm3na 2aret el papers deh?):
      • Initially specify a general descriptive framework to which the subsequent method descriptions will refer
      • We put a strong emphasis on the methodological issues of case-based reasoning, and less on a discussion of suitable application types and on the advantages of CBR over rule-based systems
      • We strive to maintain a neutral view of existing CBR approaches, unbiased by a particular ‘school’
    • What is case-based reasoning? Basically: To solve a new problem by remembering a previous similar situation and by reusing information and knowledge of that situation
    • Part of the foundation for the case-based approach, is its psychological plausibility (presentation tip)
    • Case-based reasoning and analogy are sometimes used as synonyms
    • Problem solving is not necessarily the finding of a concrete solution to an application problem, it may be any problem put forth by the user. For example, to justify or criticize a solution proposed by the user, to interpret a problem situation, to generate a set of possible solutions, or generate expectations in observable data are also problem solving situations (presentation tip: eeh 3alket PS bel CBR? PS ma3nah te7el moshkela we dah mesh by3mel kda)
    • The learning approach of case-based reasoning is sometimes referred to as case-based learning. This term is sometimes also used synonymous with example-based learning, and may therefore point to classical induction and other generalization-driven learning methods. Hence, we will here use the term case-based reasoning both for the problem solving and learning part, and explicitly state which part we talk about whenever necessary (2enta kateb 2en mashro3ak feh learning CBR dah learning ezay?)
    • When a problem is successfully solved, the experience is retained in order to solve similar problems in the future. When an attempt to solve a problem fails, the reason for the failure is identified and remembered in order to avoid the same mistake in the future
    • How the paper is structured:
      • Brief historical overview of CBR field
      • Describing CBR framework and methods
      • Section 4->8: discuss representation issues and methods related to the four main tasks of case-based reasoning
      • In chapter 9 we look at CBR in relation to integrated architectures and multistrategy problem solving and learning
  • History of CBR:
    • There are developed applications that help in CBR development
    • Read this section from paper (4-5)
  • Fundamentals of CBR Methods:
    • Central tasks that all case-based reasoning methods have to deal with are:
      • To identify the current problem situation
      • Find a past case similar to the new one
      • Use that case to suggest a solution to the current problem
      • Evaluate the proposed solution
      • Update the system by learning from this experience.
    • Classification of Terms Related to CBR:
      • Exemplar-Based Reasoning:
        • Solving a problem is a classification task, i.e. finding the right class for the unclassified exemplar. The class of the most similar past case becomes the solution to the classification problem. The set of classes constitutes the set of possible solutions. Modification of a solution found is therefore outside the scope of this method
        • Instance-Based Reasoning:
          • This is a specialization of exemplar-based reasoning into a highly syntactic CBR-approach
          • The representation of the instances are usually simple (e.g. feature vectors), since a major focus is to study automated learning with no user in the loop
          • Basically, this is a non-generalization approach to the concept learning problem addressed by classical, inductive machine learning methods
        • Memory-Based Reasoning:
          • Adds the parallel processing abilities to one of the 2 previous approaches
        • Case-Based Reasoning:
          • A typical case is usually assumed to have a certain degree of richness of information contained in it, and a certain complexity with respect to its internal organization
          • That is, a feature vector holding some values and a corresponding class is not what we would call a typical case description
          • They are able to modify, or adapt, a retrieved solution when applied in a different problem solving context
          • Paradigmatic case-based methods also utilizes general background knowledge – although its richness, degree of explicit representation
        • Analogy-Based Reasoning:
          • ABR is often used to characterize methods that solve new problems based on past cases from a different domain, while typical case-based methods focus on indexing and matching strategies for single-domain cases
          • Research on analogy reasoning is therefore a subfield concerned with mechanisms for identification and utilization of cross-domain analogies
          • Mapping problem: Finding a way to transfer, or map, the solution of an identified analogue (called source or base) to the present problem (called target)
    • Description of the Framework:
      • Process model of CBR cycle (Process Cycle View):
        • here we identifies the main subprocesses of a CBR cycle, their interdependencies and products
      • Task method structure for CBR (Task Oriented View):
        • Here where a task decomposition and related problem solving methods are described
    • CBR Cycle:
      • RETRIEVE the most similar case or cases
      • REUSE the information and knowledge in that case(s) to solve the problem
      • REVISE the proposed solution
      • RETAIN the parts of this experience likely to be useful for future problem solving

  • A Hierarchy of CBR Tasks:
    • At the knowledge level, a system is viewed as an agent which has goals, and means to achieve its goals
    • A system description can be made from three perspectives: Tasks, methods and domain knowledge models.
    • Tasks are set up by the goals of the system, and a task is performed by applying one or more methods. For a method to be able to accomplish a task, it needs knowledge about the general application domain as well as information about the current problem and its context.

  • CBR Problem Areas:
    • Knowledge representation
    • Retrieval methods
    • Reuse methods
    • Revise methods
    • Retain methods
  • Representation of Cases:
    • Problem Definition:
      • The representation problem in CBR is primarily the problem of
        • Deciding what to store in a case
        • Finding an appropriate structure for describing case contents
        • Deciding how the case memory should be organized and indexed for effective retrieval and reuse
        • How to integrate the case memory structure into a model of general domain knowledge, to the extent that such knowledge is incorporated
    • Common Case-Memory Models:
      • Dynamic Memory Model:
        • The case memory in this model is a hierarchical structure of what is called ‘episodic memory organization packets’ or generalized episodes
        • The basic idea is to organize specific cases which share similar properties under a more general structure (a generalized episode)
        • A generalized episode (GE) contains three different types of objects:
          • Norms: are features common to all cases indexed under a GE
          • Cases:
          • Indices:
            • Are features which discriminate between a GE’s cases
            • An index may point to a more specific generalized episode, or directly to a case.
            • An index is composed of two terms: An index name and an index value
            • An index value may only point to a single case or a single generalized episode
          • Similarity assessment criteria (to match a case) can in turn can be used to guide the search – for example by identifying which indexes to follow first if there is a choice to be made
          • During storing of a new case, when a feature of the new case matches a feature of an existing case, a generalized episode is created. The two cases are then discriminated by indexing them under different indices below this generalized episode (also for GE)
          • This is the reason for naming it dynamic
          • In CASEY, failure features are also stored within each case

  • Disadvantages:
    • The indexing scheme is redundant, since there are multiple paths to a particular case or GE. This is illustrated in the figure by the indexing of case1
  • Advantages:
    • The same algorithm is used for searching, retrieving and adding new case
    • Human readable
  • Category and Exemplar Model:
    • Here cases are also referred to as exemplars
    • The psychological and philosophical basis of this method is the view that ‘real world’, natural concepts should be defined extensionally. Further, different features are assigned different importances in describing a case’s membership to a category. Any attempt to generalize a set of cases should – if attempted at all – be done very cautiously
    • Structure of memory:
      • The case memory is embedded in a network structure of categories, cases, and index pointers.
      • Each case is associated with a category.
      • An index may point to a case or a category. The indices are of three kinds:
        • Remindings:
          • Feature links pointing from problem descriptors (features) to cases or categories
        • Exemplar Links:
          • case links pointing from categories to its associated cases
        • And difference links pointing from cases to the neighbor cases that only differs in one or a small number of features
      • A feature is, generally, described by a name and a value.
      • A category’s exemplars are sorted according to their degree of prototypicality in the category
      • Here the categories are inter-linked within a semantic network. Which also contains the features and intermediate states (e.g. subclasses of goal concepts) referred to by other terms

  • Advantages:
    • Supports background knowledge
  • Disadvantages:
    • Complex calculations are required to retrieve a case
  • Case Retrieval:
    • Retrieval Criteria:
      • Syntactical similarities among problem descriptors
        • Syntactic similarity assessment – sometimes referred to as a “knowledge-poor” approach – has its advantage in domains where general domain knowledge is very difficult or impossible to acquire
      • Other approach retrieves based on deeper semantical similarities
        • semantical oriented approaches – referred to as “knowledge-intensive” – are able to use the contextual meaning of a problem description in its matching, for domains where general domain knowledge is available
    • Identify Feature:
      • Knowledge model: knowledge of cases and general knowledge
    • Initially Match:
      • This task is divided into 2 subtasks:
        • An initial matching process: which retrieves a set of plausible candidates
        • A more elaborate process of selecting the best one among these
      • Similarity Assessment Techniques:
        • Trying to understand the problem more deeply, and using the goals, constraints
        • Weigh the problem descriptors according to their importance for characterizing the problem
    • Case Reuse:
      • Here we take care of two aspects:
        • Differences between past and current case
        • What part of retrieved case can be transferred to the new case
    • Adaptation:
      • Differences between transformational reuse and derivational reuse
      • Transformational reuse does not look how a problem is solved but focuses on the equivalence of solutions, and this requires a strong domain-dependent model in the form of transformational operators {T} plus a control regime to organize the operators application
      • Derivational reuse looks at how the problem was solved in the retrieved case. The retrieved case holds information about the method used for solving the retrieved problem including a justification of the operators used, subgoals considered, alternatives generated, failed search paths, etc.
    • Case Revision:
      • At the start of this task the learned case is in intermediate period and marked as non-evaluated case
      • The case should be evaluated using any type of technique stated before. A string simulator could help here
      • Any new solution is passed to repair module and it revises the solution
    • Retainment:
      • Extract:
        • Here we are concerned with extracting the new info in the solution (could be entirely an new case, could be an explanation, could be a method, etc…)
      • Indexes:
        • Determining indices is actually a knowledge acquisition problem, and should be analyzed as part of the domain knowledge analysis and modeling step
        • A trivial solution to the problem is of course to use all input features as indices. This is the approach of syntax-based methods within instance-based and memory-based reasoning. In the memory-based method of CBR-Talk [Stanfill-86], for example, relevant features are determined by matching, in parallel, all cases in the case-base, and filtering out features that belong to cases with few features in common with the problem case
        • The indices could be adapted under which features were used to extract the solution
    • Integrated Approaches:
      • Sometimes we could integrate a Model-Based method to solve problems failed by CBR system
      • BOLERO the rule-based level
        contains domain knowledge (how to deduce plausible diagnosis from patient facts) while the meta-level
        contains strategic knowledge (it plans, from all possible goals, which are likely to be successfully achieved). The case-based planner is therefore used to control the space searched by the rule-based level, achieving a form of speed-up learning
  • Conclusion:
    • The development trends of CBR methods can be grouped around four main topics:
      • Integration with other learning methods
      • Integration with other reasoning components
      • Incorporation into massive parallel processing
      • Method advances by focusing on new cognitive aspects.
  • Questions:
    • What are the differences between EBR and IBR?
    • That is, a feature vector holding some values and a corresponding class is not what we would call a typical case description!! 2omal eh heya el case?? (Page 7)

2 Responses to “Summary of Case-Based Reasoning Foundational Issues, Methodological Variations, and System Approaches”

  1. […] Summary of Case-Based Reasoning Foundational Issues … […]

  2. […] Summary of Case-Based Reasoning Foundational Issues … […]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: