Chapter / 2
EBMT Seen as Case-based Reasoning
Harold Somers* and Bróna Collins+
*Centre for Computational Linguistics, UMIST,
PO Box 88, Manchester M60 1QD, England
+formerly Trinity College,
Dublin, Ireland
Key words:Case-based Reasoning, Example-based Machine Translation, Case-Based storage, representation, retrieval, adaptation
Abstract:This paper looks at EBMT from the perspective of the Case-based Reasoning (CBR) paradigm. We attempt to describe the task of machine translation (MT) seen as a potential application of CBR, and attempt to describe MT in standard CBR terms. The aim is to see if other applications of CBR can suggest better ways to approach EBMT.
1.Introduction
Case-based reasoning (CBR) is a well-established paradigm for problem solving which emerged in the 1980s as an alternative to rule-based expert systems. Instead of rules, CBR represents expertise in the form of past “cases”, and new problems are solved by finding the most similar case in the case-base, and using this as a model for the new solution through a process of “adaptation”.
EBMT is a reasonably well-established paradigm for MT which emerged in the 1990s as an alternative to rule-based MT systems. Instead of rules, EBMT represents its linguistic knowledge in the form of “examples” of previous translations, and new translations are made by finding the most similar example in the example-base, and using this as a model for the new translation through a process of “recombination”.
The parallel between CBR and EBMT is so obvious that one would think it perhaps unnecessary to make it. But, despite the earlier establishment of CBR as a problem-solving paradigm, very few papers on EBMT make the connection explicit, and if they do, it is only as a passing comment. With one notable exception, reference to CBR pays only lip service: no attempt is made to take what has been said about CBR to see if it applies to the problem of MT. The major exception is the work of Collins and her colleagues (Collins, 1998; Collins & Cunningham, 1995, 1996, 1997; Collins et al., 1996): this work was explicitly in the paradigm of CBR, since it was carried out from within a Computer Science department specialising in CBR. As for the rest of the EBMT literature, Somers (1999) has attempted a very thorough survey of articles on EBMT: of about 130 articles collected and read, less than 10% even mentioned CBR or related paradigms, by name.
The purpose of this paper is to look at MT from the perspective of CBR, that is, to consider the CBR approach to problem solving, to see how (or whether) CBR terminology and ideas fit the particular problem of MT, and to see if we can gain any insights from this exercise. The basic assumption of this paper is that EBMT does indeed come within the general paradigm of CBR-based systems. For the purposes of discussion, however, we will use the terms “EBMT” and “CBR” distinctively: the former in its normal meaning, the latter to imply CBR seen as a generic problem-solving method.
2.CBR: the Paradigm
CBR emerged in the 1980s as an approach to problem solving which offered an alternative to the rule-based approach typical of “expert systems” up until that time. CBR offered a more intuitive approach, based on the way humans appear to solve problems, namely by finding previous similar examples as precedents, and using common-sense reasoning and extrapolation to adapt the precedent to the current problem. This mode of operation is extremely widespread, and can be applied to almost any imaginable human problem. As Leake (1996:3f) states, the CBR approach is based on two tenets about the nature of the world: first, “similar problems have similar solutions”, and second, “future problems are likely to be similar to current problems”. Psychological reality is claimed for CBR as a model of human cognition: “[E]xperts solve problems by applying their experience, whilst only novices attempt to solve problems by applying rules they have recently acquired.” (Watson & Marir, 1994:348)
Riesbeck & Schank (1989) suggest a trade-off between the rule-based and case-based approaches to problem solving: “A rule-based system will be flexible and produce nearly optimal answers, but it will be slow and prone to error. A case-based system will be restricted to variations on known situations and produce approximate answers, but it will be quick and its answers will be grounded in actual experience. In very limited domains, the tradeoffs favor the rule-based reasoner, but the balance changes as domains become more realistically complex.” (p.26)
This methodology applies to a variety of distinct areas of reasoning, and is widely acknowledged as closely modelling human reasoning strategies. In particular, it closely resembles the way human translators tend to handle a new text to be translated (Wilss, 1998), which in turn explains the huge popularity among translators of Translation Memory (TM) tools, which are of course a cousin of EBMT (in sharp contrast to the reception that other results of MT research have so far had in that community).
CBR is generally acknowledged to have its roots in Schank & Abelson’s (1977) work on scripts, along with Medin & Schaffer’s (1978) “Exemplar-based Learning”, Stanfill & Waltz’s (1986) “Memory-based Reasoning” and Carbonell’s (1986) “Derivational Analogy”, while the term itself is probably due to Kolodner & Riesbeck (1986).(1986). Other trails into the CBR field have come from the study of analogical reasoning (Gentner 1983), and – further back – from theories of concept formation, problem solving and experiential learning within philosophy and psychology (e.g. Wittgenstein 1953:31ff, Tulving 1972).
CBR is often contrasted with rule-based reasoning, in that rules are replaced by cases. By “case”
we mean a “contextualized piece of knowledge representing an experience that teaches a lesson fundamental to achieving the goals of the reasoner” (Kolodner, 1993:13). In fact, cases can be seen as very specific rules, that is, rules which apply to distinct situations. So CBR is a special kind of rule-based reasoning because the rules have to be interpreted “on the fly”, and the same rule may be used differently from one situation to another. Thus far, the same can be said of EBMT.
Typical examples of CBR are: a system which tries to find a suitable menu given some ingredients and diners’ preferences and constraints (Hammond, 1986), a medical diagnosis system (Koton, 1988), an agony aunt (Domeshek, 1991). The vocabulary of problem solving permeates the CBR literature: “Cases can be represented in a variety of forms using the full range of AI representational formalisms, including frames, objects, predicates, semantic nets and rules―the frame/object presentation currently being used by the majority of CBR software.” (Watson & Marir, 1994:331). Figure 1 shows an example.
Here already we see a difference between CBR and EBMT: many CBR systems address “problems” which have “solutions” which involve a sequence of goals to achieve, and “outcomes” or changes to the state of the “world” after the case has been invoked. In contrast, in EBMT the examples are of input–output mappings, and the means of getting from one to the other is rarely made explicit, except inasmuch as elements in the input pattern may be linked to corresponding elements in the output pattern. We will see consequences of this difference at almost every stage.
One of the claimed advantages of CBR is that it overcomes the “knowledge acquisition bottleneck” (Hayes-Roth et al., 1983) of hand-coding a great number of rules, and verifying how they interact with each other. The complexity of real-world domains, according to Riesbeck & Schank (1989:26), makes it “impossible or impractical to specify fully all the rules involved.” In CBR, when the existing “rules” don’t work (i.e. there is no suitable case in the case-base), one simply adds a new one. Such claims have been made for CBR and related “lazy learning” techniques (e.g. Watson & Marir, 1994:348) as well as for EBMT itself (e.g. Sato & Nagao, 1990). However these approaches eventually have to deal with the issue of case-base size as will be discussed below.
3.Crucial Elements of CBR
CBR thus favours learning from experience, since it is arguably easier to learn by retaining a concrete problem-solving experience than it is to generalize from it. Nevertheless, effective learning in CBR requires a well-established set of methods in order to extract the relevant knowledge from a given experience, integrate a case into the existing knowledge structure, and to index the case for later matching with similar cases. These are presented in the following sections.
The CBR paradigm covers a range of different methods for organizing, retrieving, utilizing and indexing the knowledge retained in past cases. In fact, “case-based” reasoning is just one of a set of terms used to refer to artificial reasoning systems of this nature. This has lead to some confusion, particularly since “case-based reasoning” is used both as an umbrella term (similar to analogical reasoning) for several types of approaches, as well as for one particular type of approach. Aamodt & Plaza (1994) distinguish the following types:
–Exemplar-based reasoning.
–Instance-based reasoning.
–Memory-based reasoning.
–Case-based reasoning.
–Analogy-based reasoning.
This list presents a continuum of approaches, ranging from those which attempt only to classify new examples (exemplar- and instance-based) to those approaches where previous knowledge is used to actually solve new problems (memory- and case-based reasoning) and finally to analogy-based reasoning, which could be described as a method for solving new problems based on past cases from a different domain. As we are concerned with problem solving in a single domain, we will limit the discussion to memory-based and cased-based reasoning here.
3.1Memory-based reasoning (MBR)
Characteristic of this approach is a large collection of cases in the memory, and reasoning as a data-driven process of accessing and searching in this memory rather than employment of knowledge-inference techniques. The retrieval and storage methods are often based on parallel architectures and tend to rely on purely syntactic/structural criteria, as in the MBR-Talk system (Stanfill & Waltz, 1988). Some do attempt to utilize general domain knowledge, e.g. the EBMT systems built on massively parallel processors (Kitano & Higuchi, 1991; Kitano 1993). As we will see, EBMT systems have tended to gravitate more towards MBR than CBR because of the sheer case-base sizes required in translation, and the relatively easy manner in which huge case bases can be created for EBMT from parallel corpora.
3.2Case Based Reasoning
The typically assumed features of CBR methods are, firstly, that a case has a certain degree of richness of information, and complexity in its internal organization. In contrast, a feature vector with a set of corresponding values and an associated class, as typical in classification-based techniques, would not be considered a typical case description.
Secondly, CBR methods are crucially able to modify, or adapt, a retrieved solution when applied in a different problem-solving scenario. Some case-based methods also utilize general background knowledge (see section on adaptation below) – although there is a great deal of variation in how this is done.
4.The CBR Cycle
Most texts discussing CBR are agreed on the essential elements that make up a CBR system, namely the database of “cases”, of course, and the accompanying design format consisting of the classic “CBR cycle”, as illustrated in Figure 2.
The initial description or indexing of a problem defines a new or “input” case. This new case is used to retrieve a case from the collection of previous cases. This retrieved case is then combined with the new case – through reuse or adaptation – to produce a solved case, i.e. a proposed solution to the initial problem. This solution is then feasibility tested during retain, e.g. by being applied to the real world environment or evaluated by a teacher, and repaired if failed.
During the retain phase, useful experience is retained for future reuse, perhaps after the solution is again tested and the case base is updated by a new learned case, or by modification of some existing cases. General knowledge can play a part in this cycle, by supporting the CBR processes.
This support may range from very weak (or none) to very strong, depending on the type of CBR method. General knowledge should be understood as domain-dependent knowledge, as opposed to the specific knowledge contained in the cases.
In the following sections we will take each of these elements in turn to see how they relate to EBMT.
4.1Indexing
The “indexing problem” is a central problem in CBR. It amounts to deciding what type of indices (or “indexes” as they are commonly known) to use for current and future retrieval, and also how to structure the search space of indexes. Direct indexing methods ignore the latter issue, but there is still the problem of identifying what type of indexes to use. The indexing scheme affects all the other parts of the system, since it reflects and determines the way the cases are represented, that is, the aspects of the cases which are relevant to the problem domain. This is actually a knowledge acquisition problem, and should be analysed as part of the domain knowledge analysis and modelling 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, including EBMT. In the memory-based method of CBR-Talk (Stanfill & Waltz 1986), for example, relevant features are determined by matching all cases in the case-base in parallel, and filtering out features that belong to cases that have few features in common with the problem case.
Nearly all EBMT system papers also discuss indexing. Here, the entire input sentence, or a (shallow) abstraction thereof, is used as the basis for indexing. Some use linguistic tools to perform the indexing, others use the case-base itself. One of the ironies of EBMT is that the mechanisms used to produce the indexes for the cases, and also to analyse a new case into the appropriate format, are usually the same as, or very similar to, the rules found in the rule-based systems they are supposed to replace. However, this is far from making the claim that EBMT as an entire methodology is therefore a subset of, or equivalent to, such rule-based MT systems. As we will see, there is a lot more to EBMT than the indexing problem.
5.Case Storage and Representation
The content of the cases is distinguished in the literature from the indexing scheme used to retrieve cases.
The representation problem in CBR is essentially that of
–deciding what should be stored in a case,
–finding an appropriate structure for describing case contents, and
–deciding how the case memory should be organized and indexed for effective retrieval and reuse.
An additional problem is how to integrate the case memory structure into a model of general domain knowledge, to the extent that the approach is attempting to represent such knowledge, although as we discuss below, this is almost never attempted in EBMT.
The EBMT literature has a tendency to focus on the first two points above, in particular the linguistic methods employed to create the source language (SL)–target language (TL) links and the design of the resulting template structures, whereas the equally crucial question of global memory organization, i.e. how best to store these cases in relation to each other to enable efficient retrieval and storage, is only given whatever scant room is left after the justifications for a certain level of linguistic processing have been dispensed with. By attempting to view EBMT from the broader point of view of CBR, we choose to side-step the debate of how linguistic knowledge is gathered (and whether EBMT is therefore traditional MT in disguise or not), and to focus on the issues of efficient case-storage, retrieval, reuse and case-base maintenance. Interestingly, CBR researchers never debate the “CBR-ness” of a given system simply because some first-principles knowledge engineering tools may have been employed in order to create the cases. According to Aamodt & Plaza (1994) “If cognitive plausibility is a guiding principle, an architecture for intelligence where the reuse of cases is at the centre, should also incorporate other and more general types of knowledge in one form or another”.
5.1The CBR case-base size
A striking feature, from the point of view of EBMT, is the small size of the case-base in many of the earliest reported CBR systems. As case-base sizes grew however, CBR researchers noted that system efficiency did not automatically or monotonically (Smyth & Cunningham, 1996) increase as a result. Smyth & Cunningham cite the example of a case-base size 1,000 from the housing-pricing domain that generated solutions within 90% of their optimum while the addition of a further 1,000 cases improved the accuracy by only 4%. In EBMT an example set of under 1,000 examples would be considered small, and the bigger systems might have as many as three-quarters of a million examples (cf. Somers, 1999:120). However the fact still remains that in every EBMT system also, there will be a theoretical optimum case-base size, and once this is reached, there will be a trade-off between case-base size and efficiency. This levelling off of the retrieval efficiency curve is referred to as the “Utility Problem” in AI literature. Smyth & Keane (1995b) describe a strategy of coping with the CBR utility problem, a strategy of “remembering to forget” using deletion techniques that preserve system efficiency, solution quality and target coverage. Case-base maintenance issues are rarely mentioned in the EBMT literature which is strange seeing as generalization and templatization are major issues in the design of the cases themselves.