Combining Case-Based and Rule-Based Reasoning: A Heuristic Approach

1 Introduction

"Statutory interpretation" is the process of trying to de­ termine the meaning of a legal rule by analyzing its terms and then applying it to a particular set offacts. The diffi­ culty presented to adjudicators, advocates and adminis­ trators by this exercise is that critical terms are typically not defined completely (or at all) by a statute. Further, a rule taken as a whole may have unspoken qualifications and exceptions. Thus one must look outside a statute to other sources of knowledge for clues to its meaning and the meaning of its constituent elements. In particular, one tries to resolve interpretation problems by consider­ ing past applications of the rules and terms in question: by examining precedent cases, comparing and constrast­ ing these with the instant case, and arguing why a pre­ vious interpretation can (or cannot) be applied to the new case 1 (Levi, 1949; Llewellyn, 1960; Twining and Miers, 1982). The intepretation problem demands that one combine reasoning with cases and reasoning with rules (statutes). While the need to mix case-based rea­ soning ("CBR") and rule-based reasoning ("RBR") is a prototypical feature of statutory legal reasoning, other domains also require it. We believe our approach can be applied beyond the realm of law; in particular, to extend traditional expert system approaches to "soft" domains that lack a strong domain model.

'This work was supported in part by the Advanced Re­ search Projects Agency of the Department of Defense, mon­ itored by the Office of Naval Research under contract no. N00014-87-K-0238, the Office of Naval Research under a Uni­ versity Research Initiative Grant, contract no. N00014-86K-0764, and a grant from GTE Laboratories, Inc., Waltham, Mass.

1 Note, in the fullest sense, interpretation also requires con­ sideration of whether a term or rule "should" be applied . In

For examples of underdefined terms in a legal rule , consider a section of the statute that governs the assess­ ment of Federal income tax, the Internal Revenue Code (sometimes called just the "Code"). In stating the re­ quirements for taking a home office deduction, Section 280A(c)(l) of the Code employs such terms as "principal place of business", "convenience of the employer" and use on a "regular basis" . 2 Nowhere are these elements defined in the statute; yet some scope must be afforded them in order to apply the statute to particular cases. While the meaning of such phrases is sometimes eluci­ dated by official regulations issued thereunder by the Internal Revenue Service, a clear-cut definition (which does not itself use undefined terms) is almost never to be found. Often, the reach of the meaning of such phrases is fundamentally unclear, varies greatly according to the factual context in which they are used, and defeats pre­ cise definition by rules. For clues to their scope, prac­ titioners rely on previously litigated tax cases that have construed these terms.

1.1 The Interpretation Problem in the Law

In statutory interpretation, ambiguous terms often arise from "open-textured" concepts, and these concepts are often the focus of case-based attack. By "open­ textured" concept we mean a concept that cannot be defined by necessary and sufficient conditions: one whose boundary is not sharp. Such concepts have been much discussed in jurisprudence (Hart, 1961; Dworkin, 1977) and also in philosophical discussions of "natural kind" classes (Wittgenstein, 1958; Putnam, 1975]. Gardner's recent work (Gardner, 1987], for example, discussed how such legal open-textured concepts give rise to what are known as "hard" cases, that is, cases over whose reso­ lution experts (judges, scholars, etc.) disagree. Many concepts in domains like the law are open-textured and sometimes even familiar terms reveal a surprising open­ textured lining, such as "contract" or "income". Con­ cepts like "due care", which are used deliberately to in­ dicate a variable standard of behavior, are clearly of this sort. So are "meeting or dealing" and "exclusive use" from the home office deduction rule. Their interpreta­ tion is the subject of numerous cases. 3

this discussion, we leave aside these important normative as­ pects, which involve reasoning about legislative intent, policy and ethics[Fuller, 1958; Hart, 1958] .

2 §280A(c)(1) states that a deduction may be taken for "any item to the extent such item is allocable to a portion of the dwelling unit which is exclusively used on a regular basis - (A) [as] the principal place of business for any trade or business of the taxpayer, (B) as a place of business which is used by patients, clients, or customers in meeting or deal­ ing with the taxpayer in the normal course of his trade or business, or (C) in the case of a separate structure which is not attached to the dwelling unit, in connection with the taxpayer's trade or business. In the case of an employee, the preceding sentence shall apply only if the exclusive use re­ ferred to in the preceding sentence is for the convenience of the employer."

The need to do statutory interpretation is not neces­ sarily the result of poor legal drafting. Rather it is a per­ sistent problem that resists a legislature's best good-faith efforts at drafting tight statutes. Most generally, the per­ sistence is due to the nature of the law and its relation to society; more particularly, to factual circumstances unanticipated at the time of drafting and a changing le­ gal context (Levi, 1949; Sunstein, 1988). This was one of the points of one classic discussion of the problem of statutory interpretation known as the "Hart-Fuller de­ bate", between H.L.A. Hart and Lon Fuller in a Harvard Law Review dialogue (Hart, 1958; Fuller, 1958] . There they discussed, among other things, such deep jurispru­ dential issues as the nature and status of rules and the role of "ought" (normative considerations) in statutory interpretation. 4

3 For instance, a case involving Max Frankel, The New York Time11 Managing Editor, Ma:z: and Tobia Frankel v. Commi1111ioner, 82 USTC 318 (Filed February 28, 1984), ad­ dressed the former. Mr. Frankel maintained an office at his home in the Bronx, which he used for reading the morning papers, writing memoranda, clipping materials, and speak­ ing by telephone to his employees, prominent politicians and community leaders. The Tax Court denied that Mr. Frankel met any of the three disjunctive requirements of the statute, (A), (B) , or (C) . In particular, the use of the telephone to conduct business was held not to satisfy the meeting or deal­ ing predicate, which was construed to require the physical presence of business contacts.

4 Two famous hypothetical statutory rules from this de­ bate nicely illustrate the problems: ( 1) "No vehicles are al­ lowed in the public park." and (2) "It shall be a misdemeanor .. . to sleep in any railway station." Hart and Fuller were con­ cerned with applying such rules to "hard" cases, where the puzzle is to interpret open-textured concepts, like "sleeping" or "vehicle", in light of a statute's purposes. For instance, does a tank which is part of a war veterans memorial statue count as a vehicle? What about a motorized baby carriage or wheelchair? What about a fire engine requiring access to a fire via the park? As for "sleeping", what should we decide about a bum who has obviously bedded down for the night but still has his eyes open? Should the result be any different as to a well-dressed commuter who has clearly dozed off?

1.2 The Interpretation Problem Outside the Law Although law is the focus of this discussion of mixed CBR/RBR paradigm reasoning, lawyers are by no means the only ones to combine these two different modes of reasoning. Mathematicians regularly combine reason­ ing deductively and reasoning with examples. Although sometimes overshadowed by formal definitions and theo­ rems and their proofs, examples, that is, cases, constitute a powerful aspect of expertise [Rissland, 1978]. Polya [Polya, 1965] speaks of the importance of interleaving these two modes of reasoning in the "alternating pro­ cess" in which one switches to CBR (to find a counter­ example) when deductive reasoning stalls and vice versa. The "dialectical" process discussed by Lakatos [Lakatos, 1976) depends critically on use of exemplar cases as much as it does on proof analysis. And in AI discovery systems, such as Lenat's AM, examples are a powerful source of control and focus of attention [Lenat, 1977].

Even in medicine, where heuristic rules have formed the core of the current generation of medical expert sys­ tems (e.g., rules of diagnosis as in MYCIN), there is a rich body of specific cases of a phenomenon (e.g., partic­ ular cases in a particular practice such as "Mrs. Jones, the woman whose problem turned out to be borderline hypertension") which an expert might use, especially in cases requiring judgment calls. Equally important, even though one traditionally treats concepts like "hyperten­ sion" as well-defined in expert systems, such terms really are not so clear-cut as all that - for a large part of their meaning lies in how they were used in past cases.

2 The Legalistic Child: An Example of Interpretation

As an example of the need for statutory interpretation, consider the case of the "legalistic child" from the book by the British legal scholars Twining and Miers [Twining and Miers, 1982]

"Johnny, aged 7, is an only child . In recent months his mother has been mildly worried because he has developed a craving for sweet things and this has affected his appetite at meal times ... Then one af­ ternoon she finds that Johnny has gone into the larder and helped himself to half a pot of straw­ berry jam ... she does not punish Johnny but in­ stead says, 'That's naughty. In the future you are never to enter the larder without my permission.' 'What does enter mean , Mummy?' asks Johnny. 'To go into', says his mother. 'O.K.' says Johnny, relieved that he has got off so lightly. Several inci­ dents then follow . First, Johnny gets a broom and hooks the pot of jam from the larder and helps him­ self. 'I didn't enter the larder', he says. Next the cat enters the larder and attacks the salmon which mother has bought for a special occasion. Mother, upstairs, hears Johnny hooting with laughter. She comes down to see him standing outside the larder door watching the cat eating the fish . 'I may not go into the larder,' he says.''

Clearly one of the conflicts between Johnny and his mother concerns the meaning of enter; another is the scope of the rule itself (e.g., is there an unspoken excep­ tion that allows entry in dire circumstances much like that enabling fire trucks to run red lights?) . We shall re­ turn to this example to demonstrate our computational approach to interpretation.

3 Synopsis of CBR and Mixed Paradigm Approaches

Case-based reasoning ("CBR") has grown rapidly in the last few years [Kolodner, 1988; Rissland and King, 1988] . Within CBR there are two major classes of CBR that can be identified: problem-solving CBR [Hammond, 1986; Kolodner, 1987; Sycara, 1988] and precedent-based CBR [Ashley, 1988; Ashley and Rissland, 1988]. Precedent­ based CBR is distinguished by its focus on the use of past cases ("precedents") to ju:Jtify a solution and explain its rationale 5 . Anglo-American common law with its doc­ trine of the binding nature of precedent is a paradigm of precedent-based CBR. On the other hand, in problem­ solving CBR, the typical focus is on using past cases to find a a detailed problem solution (e.g., a plan, a course of action), where the new solution is generated by adapting a previous solution. Industrial design and planning are paradigmatic examples of problem-solving CBR [Barletta and Mark, 1988].

Both types of CBR follow similar steps. Once a new case has been accepted for analysis, CBR proceeds by ( 1) analysing it (e.g., by computing features, relations and indices) to retrieve a set of relevant cases from case memory; (2) from these selecting a subset of best cases from which to craft a solution or interpretation for the problem case; (3) derivation of a solution or intepreta­ tion complete with supporting arguments in the case of precedent-based CBR and with implementation details in the case of problem-solving CBR; ( 4) testing of the the interpretation (e.g., with hypotheticals) or solution (e.g., with simulations) with an eye to assessing its cor­ rectness, strengths, weaknesses, generality, etc.; and (5) storing the newly solved or interpreted case into case memory and appropriately adjusting indices and other CBR mechanisms such as similarity metrics.

Note, in assessing relevancy in Step 1, and all the other steps of CBR as well, one must view cases from the point of view of the case and task at hand. So, for instance, just because a known case was a landmark case does not necessarily make it important for the present case since the two might not share any relevant similarities. Furthermore, in statutory interpretation the CBR must address the requirements of the statute. It is not enough simply to argue about the meaning of legal concepts; one must tie the arguments to the statute. This latter remark shows why our past work on HYPO is insufficient in itself for modelling statutory interpretation [Rissland and Skalak, 1989].

6 As in previous precedent-based systems of our group, HYPO and TAX-HYPO, the key idea is to reason from cases similar to the current case in order to argue for a particu­ lar decision in the current case and to justify the reasoning in terms of the past cases. A large part of the effort is on selecting and arguing about the relevancy of cases: showing similarity with supporting cases and distinguishing contrary cases.

At this point, researchers have only recently begun to write about the integration of CBR with other reason­ ing paradigms [Goel and Chandrasekaran, 1988; Koton , 1988a; Koton, 1988b; Marques et al., 1988; Walker et al., 1988]. We feel that such mixed-paradigm approaches are natural and shed light on both the cognitive skills in­ volved in such reasoning and on questions of architecture and control of their computational models.

4 Heuristics for Mixed Paradigm Reasoning

In our study of statutory interpretation, we have gath­ ered a collection of 30 or so heuristics that we believe ex­ perts use for controlling and interleaving reasoning with rules and reasoning with cases. These heuristics can be divided into a number of categories: 6

1. Way:J to Begin Rea:Joning
2. Rule-ba:Jed Near Mi:JIJ
3. Rule-ba:Jed Near Hit
4. Way:J to Broaden a Rule
5. Way:J to Di:Jcredit a Rule
6. Way:J to Confirm a Hit
7. Way:J to Confirm a Mi:JIJ
8. Way:J to Confirm Rea:Joning: "Sanity Check:J"
9. Way:J to Deal with Re:Jult:J Oppo:Jite from that De:Jired
10. Way:J to Deal with Failure of Rea:Joning to Yield a Definite Conclu:Jion
11. Way:J to Focu:J the Rea:Joner:J
12. Open- Teztured Element:J

Some of our heuristics, like those in groups 8 and 12, are very similar to those employed by Gardner [Gardner, 1987].

We are currently exploring the use of these heuris­ tics in controlling a mixed paradigm system, combining case-based and rule-based reasoning, called CABARET (CAse-BAsed REasoning Tool). The main features of CABARET's architecture are (Figure 1):

• There are two co-reasoners (CBR and RBR ).
• Each co-reasoner is capable of running in a stand­ alone manner.
• Each co-reasoner has a dedicated reporter pro­ cess that reports the end results of a reasoner and certain aspects of its intermediate processing.
• A controlling process uses reporters' observa­ tions and its library of control heuristics to decide how the system as a whole and the individual rea­ soning processes are to proceed.
• The ultimate goal for which the system is working (an argument for a given side or a neutral explana­ tion) is specified by the user, as part of the intitial input to CABARET.

6 A hit refers to the establishment of the antecedent of a rule, on the rule-based side, or the presence of all the pre­ requisites of a dimension (index), on the case-based side. A miu is the opposite of a "hit". Near miss and near hit are discussed below.

1'iqu.<e 1.

CABARET uses an agenda-based Controller in which the heuristic control rules direct and interleave the two modes of reasoning by posting and prioritizing tasks for each to do_ The control rules are written in CABARET's Control DeiJcription Language, ("CDL"), which provides a vocabulary with which to express (i) higher level con­ trol deiJcriptoriJ that describe at a fairly high level the state or result of the case-based reasoner and the rule­ based reasoner, and (ii) taiJiciJ for the Controller to sug­ gest for each reasoner. For instance, since what an ex­ pert, or CABARET, does in a particular situation may depend on what side is being argued for, the CDL has a descriptor for point-of-view. Depending on whether the user wants the consequent of a rule to be established, point-of-view may be pro (for) or con the rule. 7 Chang­ ing the point of view enables exploration of a situation from various argumentative vantage points. Four groups ( # 4-7 above) of CABARET's heuristics concern such argumentative stances: confirming that a rule should fire, confirming that a rule should not fire, broadening the scope of a rule (enabling it to be applied even when it seems not to apply), and discrediting (limiting the scope of) a rule. These are triggered as follows:

1 In tax law, for instance, the Commissioner of Internal Revenue may argue against a statute that gives a taxpayer a deduction from his gross income, with the taxpayer arguing for it.

For instance, if Rule 1 has fired, but you don't like some consequence of Rule 1, you (and CABARET) may look for ways to discredit that rule. CABARET knows, for example, several ways to "discredit" a rule: find cases where the consequent was deemed not to have been es­ tablished, even though the rule fired; narrow the reach of the open-textured words in the rule, and so forth .

The Control Description Language also contains de­ scriptors such as: near miu, near hit, open texture, point of view, moiJt on point ca/Je/J and primitive task direc­ tives, such as forward chain, backward chain, filter caiJeiJ, confirm a hit, confirm a miiJIJ 1 broaden, diiJcredit. Typical tasks for the CBR process are analogize two cases (point out the dimensions in common and like values along such dimensions) and diiJtinguiiJh cases (point out dimensions not in common or dissimilar values along shared dimen­ sions) [Ashley, 1988] . The CDL descriptors near miiJIJ and near hit are applicable to both the RBR side and the CBR side. Generally, a near miss is had when a result (say, one that you want) is missing one compo­ nent in order to obtain. A rule-based near miss occurs when all but one conjunct of a rule can be established. A case-based near miss happens when all but one pre­ requisite of a dimension (index) are present in the case knowledge base . 8 Examples of rules in the "near miss" group are:

• If you have all but one conjunct of the antecedent of a rule, and you want the rule to fire, broaden the rule.
• If you have all but one conjunct of a rule, and you want the rule to fail, confirm the miss.

CABARET, in turn, knows a number of ways to "broaden" a rule, for example:

• Use CBR to find cases where the rule did not fire, but the consequent of the rule still held. (That is, show that the missing conjunct is not necessary to fire the rule.)
• Use CBR to find cases where the rule did fire , and point out the similarities between those cases and the present case. ( Show that effectively you have the missing conjunct .)
• Use CBR to find similar cases where the rule did not fire, but the ultimate disposition of the case was consistent with the user's point of view. (Show

· 8 A CDL "near hit" has analogous meanings for CRR and RBR. The term generally applies when there are many pos­ sible ways to establish a result, and all but one of them have failed.

that the rule firing is not necessary for the ultimate result the user wants.)

· Expand the scope of any open-textured predi­ cates in the missing conjunct .

5 A Detailed Example of Mixed Paradigm Reasoning

To illustrate the above control heuristics in action, con­ sider a further incident involving our legalistic child Johnny:

Johnny is home with his rapidly aging grand­ mother. His parents are out at the Royal Shake­ speare Company's performance of "A Midsummer Night's Dream". Grandmother forgets about din­ ner. Johnny is hungry. It's 55 minutes past the usual dinner hour. He asks his grandmother for permission to enter the larder. She turns and smiles at him. She is off in another world. Johnny goes to the larder and feasts on bread and jam. His parents return. What result?

5.1 The Case Knowledge Base

Let us assume that Johnny has been involved in sev­ eral incidents of entering the larder in addition to the "broom pole" and "salmon" cases, which he lost. Thus, assume Case Knowledge Base contains:

• The Broom Pole Ca11e: Johnny used a broom pole to hook a pot of jam. He stood outside the larder. He was punished.
• The Salmon Ca11e: Johnny did not enter the larder but watched the household cat ravage the salmon. He was scolded.
• The Baby11itter Ca11e: Johnny's parents were out and Johnny was watched by his usually iron-willed babysitter, Maggie . Johnny's parents forgot to tell Maggie anything about dinner . Supper was late and Johnny was hungry. Johnny asked permission from the babysitter to enter the larder . She said OK. Johnny feasted on scones and jam. When his parents returned, they said it was understood tha.t Maggie, in lieu of Mother, could give permission to enter the larder .
• Willful Di11obedience Ca11e: Johnny, who was peeved with his parents, went into the larder. He ate all the jam in the larder. He was not permitted to watch Dr. Who for month.
• Wea11el'11 Ca11e: Johnny convinced his pal, Weasel, to enter the larder. They ate. Mother sent Weasel home and Johnny to his room.
• Ca11e of the Gla11gow Cou11in11: Johnny's poor cousins from Glasgow passed through. Johnny was the only one home. They asked for a bite before they went on their way. Johnny sa.id OK. He asked them to hand him the jam. They did. Johnny was rewarded for his generosity to his poor relations when his Mother returned.

5.2 The Rule Base

A simple rule base- with several representative types of rules - suffices for our current illustration. The first rule is the background prohibitory rule; the second pro­ vides a "reasonable man" standard often seen in Anglo­ American tort and criminal law; the third provides a more detailed statute with a number of open-textured elements, some deliberately so; and the last rule is a bright-line sufficient condition for the statutory element "substantially late."

• May-Not-Enter-Rule: Johnny may not enter the larder.
• Rea11onable-Rule: Johnny may reasonably enter the larder.
• Late-Supper-Rule: If supper is substantially late, and Johnny is hungry, and Johnny receives permis­ sion his Mother, then Johnny may enter the larder.
• When-!6-Late-Rule: Supper is substantially late if it is more than 30 minutes late.

5.3 Mixed Paradigm Scenarios

How rule-based and case-based processing might pro­ ceed depends on the point of view of the itser, so posit that Johnny and his Mother are at odds for this purpose: he wants to enter the larder; she wants to keep him out. CABARET is being designed to leave processing traces like the following. 9 For convenience, we bracket the rule and italicize its category.

Reasoning from Johnny's Point of View

• The Controller begins processing on the RBR side [ Way11 to Begin Proceuing- Begin with RBR, backward chaining] · RBR begins with Rea11onable-Rule (as it would yield a con­ clusion with Johnny's point of view.)
• Con troller uses [Deliberate Open Textured Predicate - Use CBR] to find relevant cases construing "reasonably" .
• CBR finds no close relevant cases.
• Controller uses ( Way11 to Deal with Failure of Proceuing to yield a Definite Conclu11ion- Toggle] to switch back to RBR.
• RBR backchains on Late-Supper-Rule.
• RBR establishes conjunct "supper is substantially late" by application of When-!6-Late-Rule.
• RBR establishes the conjunct "Johnny is hungry" by ref­ erence to the facts of the case.
• RBR's reporter reports that it cannot establish the con­ junct "Johnny receives permission from Mothe.r" but it has established the other two.
• Controller uses [Rule-ba11ed Near-Miu- show that you ef­ fectively have the missing conjunct] to suggest CBR on cases where the Late-Supper-Rule fired and the permission conjunct was effectively established.
• CBR finds The Baby11itter permission case as a most on point case and points out similarities between it and the cur­ rent case. Also cites Gla11gow Cou11in11 case as being relevant .
• Controller reports that a conclusion has been reached: it can be argued that Johnny may enter the larder, using the Late-Supper-Rule, modulo using The Baby11itter Ca11e to show satisfaction of permission predicate.

Reasoning from Johnny's Mother's Point of View

• The Controller applies ( Way11 to Begin Proceuing- Begin with RBR, backward chaining].
• RBR looks for rules with Mother's point of view, and seizes on May-Not-Enter-Rule.
• RBR reports success on May-Not-Enter-Rule (there are no

9 For simplicity, assume here that the prioritizing mecha­ nism for the agenda. is the default one: that the agenda is a stack, and the most recently posted control task is the first one to run.

prerequisites to satisfy).

• Controller posts (Way.! to Confirm Proceuing: Sanity Check - Use CBR to confirm RBR satisfaction of top level­ goal] to the agenda.
• CBR searches for cases where (the May-Not-Enter-Rule was fired and) Johnny was not permitted to enter the larder.
• CBR reports that the Willful-Di.!obedience Ca.!e is a rel­ evant case (involving a straightforward application of May­ Not-Enter-Rule, with Mother's point of view) but that on the other hand The Baby.!itter and Gla6gow Cou.!in6 cases are also on-point and are cases against her position.
• Controller reports that a conclusion can be reached with May-Not-Enter-Rule and Willful-Di.!obedience Ca.!e as a sup­ porting case but that the conclusion is suspect because of existing contra cases.

There are several alternative ways this scenario could have proceeded. The Controller could have suggested "Try to establish an argument for Mother's point of view by showing the failure of all rules establishing Johnny's point of view." Or, noting that CABARET gives the user the option to choose the initial reasoner, the user may have started off with CBR. So, different conclusions and ways of reaching them can be unearthed, even with the same rules, case base, and control heuristics.

6 Conclusions

In the law and other domains, governing rules often have words or phrases that cannot be defined precisely. In or­ der to apply such rules one must reason with past cases in order to clarify ambiguous rule terms. We have devel­ oped a heuristic approach to combining reasoning with rules and reasoning with cases in order to solve this kind of interpretation problem. Our approach is grounded in a set of control heuristics that determines what reason­ ing tasks to perform, given the states of the co-reasoners. These heuristics are applied by the Controller module of CABARET, an architecture we are constructing to ex­ periment with heuristic approaches to the interpretation problem and to performing mixed-paradigm reasoning in general.