--- title: "A Methodology for Evaluating Theory Revision Systems: Results with Audrey II" authors: - "James Wogulis" - "Michael J. Pazzani" doi: "" url: "https://ijcai.org/proceedings/1993/156" pdf: "https://ijcai.org/proceedings/1993/0156.pdf" venue: "Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence" year: 1993 pages: "1128-1133" track: "Machine Learning" keywords: --- # A Methodology for Evaluating Theory Revision Systems: Results with Audrey II James Wogulis, Michael J. Pazzani *Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence*, pages 1128-1133. ## Abstract Theory revision systems are learning systems that have a goal of making small changes to an original theory to account for new data . A measure for the distance between two theories is proposed. This measure corresponds to the minimum number of edit operations at the literal level required to transform one theory into another. By computing the distance between an original theory and a revised theory, the claim that a theory revision system makes few revisions to a theory may be quantitatively evaluated. We present data using both accuracy and the distance metric on AUDREY II, a first-order theory revision system. ## Full text ## 1 Introduction Many recent learning systems are designed to take ad­ vantage of a user supplied, approximate concept defini­ tion (also called an incomplete or incorrect domain the­ ory) to guide or constrain the learning process. Paz­ zani and Kibler [1992] state that the reason for pro­ viding a domain theory is "to increase the accuracy of learned rules." A variety of systems with different learning mechanisms share this objective, e.g., M L­ SMART [Bergadano and Giordana, 1988), A-EBL [Co­ hen, 1992al, GRENDEL [Cohen, 1992b), IOE [Flann and Dietterich, 1989), IVSM [Hirsh, 1989]. These systems are typically evaluated by comparing the accuracy of the learned rules with and without an initial theory. Some learning systems, called theory revision systems, impose an additional constraint on the learner. Mooney and Richards [1992] state that the goal of theory revision systems is "to minimally modify the theory to correctly classify all of the examples." The first theory revision systems such as EITHER [Ourston and Mooney, 1990] and KBANN [Towell, 1991] were restricted to revising theories in propositional logic. More recently, several systems such as KR-FocL [Pazzani and Brunk, 1991), FORTE [Richards and Mooney, 1991; Richards, 1992) and AUDREY [Wogulis, 1991) have been introduced that revise theories expressed as Horn clauses. In spite of the Table 1: Domain theory for concepts grandparent and parent . ·This research was supported in part by grant number F49620-92-J-0430 from AFOSR. ``` grandparent(G,C) :- parent(G,P), parent(P,C). parent(X,Y):- father(X,Y). parent(X,Y):- mother(X,Y). ``` constraint that the learned theory be a minimal revision of the given theory, the only systematic evaluation of these systems has been with respect to the accuracy of the learned theory. Here, we propose a distance metric between Horn clause theories that may be used to evaluate how well theory revision systems meet their stated goals. The measure is defined as the number of edit operations (i.e., additions, deletions or replacements of literals) that are needed to transform one theory into another. The notion of edit-distance has been studied by others [Tai, 1979; Shasha and Zhang, 1990) and applied to problems in ar­ eas such as pattern matching, parsing, and comparing secondary structures of RNA. Without such an evalua­ tion, a system that ignores the initial theory and runs a purely inductive learner on the training data might also qualify as a theory revision system. In the rest of this paper, we review how Horn clauses are used to represent domain theories, we describe in detail why the minimal modification constraint is useful and we define a -measure of the distance between tw~ theories. This measure is used to define the appropriate­ ness of a revised theory with respect to the initial theory. We then present a theory revision system, AUDREY II, and show its performance on a number of domains with respect to both accuracy and appropriateness of revi­ sion. Finally, we compare AUDREY Il's performance with other theory revision systems. ## 2 Representation A common method used by first-order inductive learn­ ers such as FOIL [Quinlan, 1990), FocL [Pazzani and Kibler, 1992), GOLEM [Muggleton and Feng, 1990) and first-order theory revisers such as KR-FocL, FORTE and AUDREY is to represent domain theories as a set of first-order Horn clauses and instances as ground literals. A single concept is represented as the set of Horn clauses in the domain theory that have the same pred­ icate symbol (and arity) for the head of the clause. For example, the concept grandfather would be repre­ sented by the set containing the first of the three clauses in the domain theory in Table 1 and the concept parent would be represented by the last two. An incorrect domain theory is one that classifies a neg­ ative example as a positive example. An incomplete do­ main theory is one that classifies some positive instances as negative. Note that a domain theory may be both incomplete and incorrect . ## 3 Theory Revision Theory revision systems are given an initial domain the­ ory that is incorrect and/or incomplete, and a set of positive and negative training examples and produce a revised theory. In this paper, we propose that an ap­ propriately revised theory is one that is closest to the initial theory and one that makes the fewest errors on unseen examples drawn from the same distribution as the training examples. Using distance as one factor to measure the quality of a revised theory favors theories that preserve as much of the initial theory as possible. There are several reasons that this is desirable: - Such revisions are more likely to be understood by experts who presumably understand the initial the­ ory, because they represent minor variants of the experts' theories. An expert may be unwilling to accept a drastic change to a theory, especially if adding or removing a few training examples results in yet another drastically different theory. - The abstractions from the initial theory may be re­ tained in the revised theory. Many learning sys­ tems (e.g. , FocL and A-EBL) that use a domain theory to guide learning express the learned con­ cept in terms of the operational predicates. This results in a "flat" theory, expressed solely in terms of "observables" without intermediate conclusions. In contrast, a theory revision system should use the abstract predicates from the initial theory, provided they are useful in making classifications. - Abstractions from the initial theory that are re­ tained in the revised theory can support the gener­ ation of meaningful natural language explanations of the system's translations [Swartout, 1981]. We note that using distance favors theories that make small incremental changes rather than major re-writes of the initial theory. While we feel this is desirable in general, there are situationsj perhaps corresponding to paradigm shifts [Kuhn, 1962, in which an entire theory must be discarded and replaced by a drastically different theory. We do not consider this issue in detail, but note that it might be addressed by introducing a dimension, such as elegance or simplicity, that may be combined with accuracy and distance to evaluate revised theories. One can use the distance metric to compare different revisions of the same initial theory to determine which revision is closest to the initial theory. When used to­ gether with accuracy, distance provides a better overall measure of the quality of the revised theories. Clearly, a theory that performs better on both accuracy and dis­ tance is to be preferred. If theory A is more accurate than theory B but theory B is closer to the initial the­ ory, then the issue becomes murkier. Since these mea­ sures are orthogonal, preferring one theory over another depends on the user's trade-off between the two goals. ## 4 Theory Distance Metric Our goal is to define a metric analogous to accuracy that can be used to measure the quality of revisions made by theory revision systems. Whereas the accuracy of a revised theory measures its semantic correctness, we de­ fine a measure of the syntactic closeness between the two theories as the distance between the initial and revised theories. The distance between two theories is defined as the minimum number of revisions required to transform one theory into another. ## 4.1 The distance between two theories As defined above, a domain theory is a set of Horn clauses which is partitioned into concepts. A concept I<pred(T) for theory T is defined as the set of clauses in the theory T with the same predicate symbol pred and arity for the head of the clause: I<pred(T) = { C E T I C := pred(- · ·) +-- Lt. · · ·Ln.}. For example, the clauses append ( [] , [] , [] ) and sort ( [] , [] ) belong to different concepts. We define the distance between two theories to be the sum of the distances between corresponding concepts from each theory. This definition of distance does not compare clauses from different concepts so there is no defined distance between the clauses for append and sort given above. Since a concept is a set of clauses, there may be many ways in which one concept could be transformed into an­ other . When measuring the distance between concept A and concept B, there are two main cases to consider. A clause C A from A could be the source of many (includ­ ing zero) clauses in B: C1B, ... CnB, or similarly many clauses in A (C1A ... CnA) could be the source of a single clause CB in B . We define the distance between two concepts to be the minimum sum of clause distances for all mappings between clauses of each concept. Since there is no way to know which clauses in one theory should correspond to which clauses in another, we define the distance between two concepts to be the mini­ mum sum of distances for all possible mappings between clauses from each concept. Clauses may be mapped to the empty clause which corresponds to clause deletion. The set of mappings between clause sets A and B can be computed as follows. First, form the cartesian prod­ uct of clauses from A and B . For example if A= {a1, a2} and B = {bt. b2 } then one element of A x B would be (a1 ,b2). Next, compute the power set of Ax B. A sin­ gle mapping is formed from one element of this power set, e.g., map = {(at, bt), (a2, bt)} . For any ai E A or bj E B not appearing in map, add the elements (ai, 0) and (0, bj) to map where 0 represents the empty clause. Therefore, we would transform map above into map= {(a., b1), (a2, bt), (0, b2) }. This mapping is inter­ preted to mean B can be revised into A by transforming clause b1 into clauses at and a2 and by deleting clause b2. In general, the number of mappings between clause sets A and B is 21AI·IBI . For our present purposes this definition will be at the literal level: i.e., how many additions, deletions or re­ placements of literals are needed to transform one clause into another . 1 However, differences in the order of lit­ erals in a clause and renaming of logical variables are ignored. We define the dist( Ct , C2) to be the minimum number of additions, deletions or replacements of liter­ als needed to transform clause C1 into clause C2 modulo variable names and literal ordering in the bodies of the clauses. For example, the distance between the two fol­ lowing two clauses is 1: ``` cJ: grandfather(X,Y) :- sister(X,Y), father(X,Z). c2: grandfather(A,B) :- father(A,C), parent(C,B). ``` Without regard to the variable names or goal order­ ing, clause c1 can be transformed into c2 by replacing sister(X,Y) with parent(Z,Y) . It is important to note that our metric for measuring the distance between two theories is used during evalu­ ation and not during the learning process. As we have implemented it, the metric is exponential and somewhat costly to compute but not prohibitive on the domains we have worked with. We suspect the complexity of our problem to be polynomial since it is closely related to the assignment problem [Lawler, 1976]. We are in the process of determining the complexity of this problem. ## 4.2 Relation Between Distance and Accuracy It is important to note that the definitions of accuracy and distance are orthogonal to one another and thus complementary. That is to say that two theories may have the same accuracy, even making the same classifi­ cation of every example, and yet there may be a large syntactic difference between the two theories . An ex­ ample of this is the difference between theories 1 and 2 in Table 2, both of which represent a correct theory for positive, even integers. 2 Similarly, two theories may be close to one another 1 Another possible definition could be more detailed and include the number of changes to terms within a literal. We will ignore this complication since the theories used by theory revision systems so far do not include complex literals such as pred(f(A), [AlB]) . We note that these might be handled within this framework by breaking a complex literal into sev­ eral simpler ones [Norvig, 1992] pred(Vt,V2) 1: Vt · f(A) 1: V2 · [A I B] . 2 modulo(A, B, M) is defined such that M is the remainder of A divided by B. ``` Theory 1: poseven(X) ·- greater(X,O), even(X). Theory 2: poseven(X) ·- modulo(X,2,Y), equal(Y,O), not(greater(Y,X)). Theory 3: poseven(X) ·- less(X,O), even(X). ``` Table 2: Three theories for positive, even integers. syntactically but have entirely different semantic mean­ ing. An example of this is theories 1 and 3 in Table 2. Both theories are quite close syntactically but have very different meaning and hence accuracy. ## 4.3 Uses of the Distance Metric Our primary use of the distance metric will be to com­ pare revisions of the same initial theory by theory revi­ sion systems to determine which revision is closest to the initial theory. This will allow one to evaluate the claim that theory revision system A produces better revisions than theory revision system B. However, if the correct theory is known (e.g., if the incorrect theory were formed for evaluation purposes by introducing errors into the correct theory), then there are two additional uses of the distance metric. First, the distance between the initial theory and the correct one provides a measure of the syntactical cor­ ruptness of the initial theory. We believe that this will provide a more useful measure of the difficulty of a the­ ory revision problem than just the accuracy of the initial theory. Presumably, the more corrupt a theory is, the harder it will be to revise. Second, the distance between the revised theory and the correct one can be used in conjunction with accuracy to measure how good a learning system is at replicating human created theories. Currently, knowledge engineers perform the theory revision task manually. A prototype expert system is often built, and then it is refined to per­ form better on a set of test cases. The initial theory and test cases can serve as input to a theory revision system and the automatically derived theory can be compared to the theory produced manually. The distance between the automatically and manually revised theories mea­ sures the system's ability to find theories similar to ones built by experts. ## 4.4 Some Drawbacks Theory revision systems require evaluation beyond sim­ ply measuring the accuracy of the theories produced. A measure of the type and quality of revisions made is also needed. Although the distance metric proposed here is useful toward that end, it is not a panacea. Since dis­ tance is a syntactic measure, it does not handle some theories one would like to consider equivalent. For exam­ ple, the learner may have clauses containing literals with equivalent meaning such as less(X, Y) and geq(Y ,X) . Comparing two theories at the syntactic level will not consider these two literals equivalent. We might address this in the future by providing additional equality axioms to determine the equivalence between two literals. ## 5 The Audrey II System In this section we present AUDREY II which performs first-order theory revision. 3 The system operates in two main phases. First, the initial domain theory is special­ ized to exclude covering any negative examples. Next, the revised theory is generalized to cover all of the posi­ tive examples without covering any negatives. AUDREY II uses four operators during theory revi­ sion: delete a clause, add a literal, delete a literal, and add a clause. A blame assignment mechanism guides the application of these operators and revisions are chosen based on their improvement to the theory's accuracy. ## 5.1 Specialization Phase The specialization phase uses a hill-climbing approach to specialize the theory until no negative examples are cov­ ered. At each step a best clause to specialize is chosen, the clause is specialized and the process repeats. The best clause is the one that contributes to the most num­ ber of negative examples being incorrectly classified and is required by the fewest number of positive examples. If the clause is not needed by any of the positive ex­ amples, then it can be safely deleted. Otherwise, it is specialized using a FOIL-like operator that adds literals to the clause one at a time until none of the negatives the clause was responsible for misclassifying are covered. This could lead to the introduction of several new clauses that are more specific than the original. For example, the overly general clause: uncle(U,Ii) ·- male(U) might be specialized into the two clauses: ``` uncle(U,Ii) ·- male(U), sibling(U,P), parent(P,Ii) . uncle(U,Ii) ·- male(U), married(U,M), sibling(M,P), parent(P,Ii). ``` ## 5.2 Generalization Phase During the generalization phase; an uncovered positive example is randomly chosen and the theory is general­ ized to cover the example. The process repeats on any remaining uncovered positives until all are covered. To cover the example, AUDREY II first applies the abduc­ tive process used in AUDREY [Wogulis, 1991] to find a single literal to assume that, if true, would allow the ex­ ample to be explained. The assumption identifies where the domain theory should be repaired and AUDREY II extends the theory so that the example can be correctly classified without relying on the abductive mechanism. The assumed literal is deleted from the clauses in which it was used if the resulting theory does not de­ crease coverage of the positive examples. If deleting the literal from a clause decreases the coverage of the positive examples, then AUDREY II tries replacing the literal with a new conjunction of literals determined by FOIL. For example, the incorrect clause uncle(U,I) :­ male(U), female(l) might be transformed into the following two clauses by replacing the literal female(l) with new literals: 3 Audrey II differs from Audrey [Wogulis, 1991] primar­ ily in its use of a Foil-like component for inductive learning rather than forming ·least-general generalizations. Also, Au­ drey II can specialize clauses by adding literals which Audrey wasn't able to do. ``` uncle(U,I) ·- male(U), sibling(U,P), parent(P,I). uncle(U,I) ·- male(U), married(U,M), sibling(M,P), parent(P,I). ``` If deleting or replacing the assumed literal fails to im­ prove coverage, then AUDREY II uses its FOIL-like com­ ponent to learn a new set of clauses for proving the lit­ eral. For example, a theory only containing the clause grandfather(A,B) :- father(A,C), parent(C,B) is too specific if it contains no clauses for parent. There­ fore, positive examples of grandfather would require making an assumption about the parent relationship and could lead to learning new clauses for parent: ``` parent(P,C) ·- father(P,C). parent(P,C) :- mother(P,C). ``` ## 6 Experimental Evaluation In this section, we present some experimental results of the AUDREY II system using accuracy and theory dis­ tance as a performance measure. In the first experi­ ment we compare AUDREY II and FocL on Pazzani and Brunk's [1991] student-loan domain measuring ac­ curacy, distance of revised theory from original and dis­ tance from the correct theory each as a function of the number of examples. In the second experiment we com­ pare the results of AUDREY II and FORTE on four dif­ ferent, incorrect domain theories for the King-Rook-King problem. To conserve space, we do not show the original theories here; they can be found in Pazzani and Brunk [1991] and Richards [1992] . ## 6.1 Student Loan Domain Pazzani and Brunk [1991] presented a domain theory for determining if a student needed to make payments on a student loan. The theory contained sixteen clauses and was up to four levels deep. Four different types of errors were introduced into the theory: one clause was missing a literal, a whole clause was missing, one clause had an extra literal and one concept had an extra clause. We compare AUDREY II to FocL to emphasize the difference between revising a theory and using a theory to guide induction . The experiment we ran consisted of giving Au­ DREY II and FocL the initial incorrect theory and examples chosen from a pool of 50 students. For each different number of input examples, we measured the re­ vised theories in terms of accuracy on unseen examples, distance from the original theory and distance from the correct theory. The results are shown in Figures 1, 2 and 3 and are averaged over 20 trials. Figure 1 shows that AUDREY II performs better on accuracy than FocL up to 45 examples at which point both systems achieve 100% accuracy. In Figures 2 and 3, we can see that the distances from both the original and correct theories for FocL are much greater than for AUDREY II. If we look at the distance of the revised theory from the original as a function of the number ex­ amples (Figure 2), we see it rising for AUDREY II from 0 to around 25 examples after which it levels off. We stated earlier that a "good" revised theory should be ac­ curate and be close to the original theory. However, we see that early on the theory isn't very accurate but the distance to the original theory is small. When the the­ ory is 100% accurate (after 45 examples), we see that its distance from the original has increased. In fact, accord­ ing to our distance metric, the correct, 100% accurate theory given by Pazzani and Brunk [1991] should have a distance offour from the original theory, while the 100% correct theory learned by AUDREY II has an average distance of slightly more than five. Figure 1: Accuracy for AUDREY II and FocL on stu­ dent loan domain. ![Image](https://ijcai.org/proceedings/1993/fulltext/156/image_000000_45960c99bfb7adab8b39ab23fe9af07e67e027e6263e6dcd9a3e485b177f1d66.png) Figure 2: Distance between original and revised theory for student loan domain. ![Image](https://ijcai.org/proceedings/1993/fulltext/156/image_000001_643dfb071cdbeb025ea1a700eb88a91a0ff4632c49eb55e55c3224147ea1307b.png) The results comparing the accuracy of FocL and Au­ DREY II indicate another benefit of the bias towards minimal revisions of theories. AUDREY II does not delete any of the domain theory unless doing so improves accuracy on the training set. In contrast, FocL learns rules that discriminate positive from negative examples. When there are few training examples, it ignores those portions of the domain theory that are not needed to explain any of the positive examples in the training set. Figure 3 shows the distance between the revised and correct theory. We notice that the original theory has a distance of four from the correct theory. As learning proceeds, the distance between the revised and correct theory actually increases. One would hope that this dis-­ tance would, in fact, go to zero as accuracy approaches 100%. Unfortunately, for this problem, AUDREY Il's distance from the correct theory is approximately 5.5 when it is 100% accurate. In this case, the theory re­ vision problem is under-constrained. For example, the correct theory should contain the following clauses: Figure 3: Distance between correct and revised theory for student loan domain. ![Image](https://ijcai.org/proceedings/1993/fulltext/156/image_000002_269eecf386bc82cd48b4310718465dfabcf521fc7325b620234adf8712bd2cf5.png) continuously\_snrolled(S) :­ never~eft..school(S), part\_time..student(S). part\_time..student(S) :­ enrolled(S,School,U), school(School), U > 5. While AUDREY II typically learns continuously\_snrolled(S) :­ part\_time..student(S). part\_time..student(S) :­ enrolled(S,School,U), school(School), U > 6, never~eft..school(S). Although these two definitions are equivalent with re­ spect to accuracy, the latter definition does not reflect a proper definition of part-time student that an expert would be willing to accept . It is exactly this type of difference that the distance metric proposed here is in­ tended to capture. The problem arises in this domain be­ cause there are two places where one could add a literal to achieve the same accuracy. While both are equally distant from the original theory, one makes the revised theory closer to the known correct theory, while the other moves it further away. This problem would not occur if the syntactic differences between the theories resulted in differences in accuracy. This could be accomplished in AUDREY II by providing examples for intermediate concepts (e.g., examples of part-time students), or if the predicate part\_time\_student were used elsewhere in the theory. ## 6.2 King-Rook-King Domain The king-rook-king problem [Muggleton and Fen~, 1990; Pazzani and Kibler, 1992; Richards, 1992] reqmres the learner to recognize illegal chess board positi?ns cont?'in­ ing only a white king and rook and a bl~ck ~~~g. An tile­ gal position is one in which the black kmg 1~ m check or where two pieces occupy the same square. Rtchards used this domain to test FoRTE and provided sample revised theories for four different corrupt versions of the correct theory. In this section, we review the FORTE system and compare the performance of AUDREY II and FORTE on the four 4 KRK domains described in Richards [1992] . ## 6.2.1 FORTE FORTE is a first-order theory revision system that uses hill climbing and a larger set of more complex revision operators. Revision points in the theory are found by recording the succeeding clauses in the proof .of a neg­ ative example and the failing points in the fatled proof of a positive example. FORTE determines all the re­ vision points for all positive and negative examples and applies the various revision operators to each pomt. The revision with the best improvement in theory accuracy and simplicity is retained and the hill climbing proceeds. FORTE uses a large set of operators: delete a clause, delete a literal, delete multiple literals, add a literal, add a clause, identification, absorption [Muggleton and Bun­ tine, 1988], multiple literal deletion, and some that com­ bine several operators into more complex ones. There are a couple of major differences between AU­ DREY II and FORTE. First , AUDREY II uses an ab­ ductive process that more accurately identifies where the theory should be modified than does FORTE's re­ vision points. Second, FoRTE has a larger number of more complex operators, some of which may make ma­ jor structural changes to the theory such as identification and absorption. Finally, FORTE was evaluated on the accuracy and size of the theories it produced and n?~ on the closeness to the original theory or degree of revtswn. ## 6.2.2 Comparison We would like to compare FORTE and AUDREY II as theory revision systems which involves comparing the two on accuracy and theory distance. Unfortunately, as with most theory revision systems, the published results on FORTE don't include the distance between the orig­ inal and revised theories. However, Richards [1992] did provide revised theories for each of four corrupt . k~~g­ rook-king domains. The results reported gave the .mttlal and final theories for each of four corrupt theones af­ ter seeing 50 of 2000 randomly chosen instances. The results of only one trial for each theory were reported. To compare the two systems, we gave AUDREY II 50 randomly chosen examples for each of the .four corrupt theories and averaged the results over ten tnals. We also computed the accuracy and theory distance meas~res of FORTE's revised theories. The results are shown m Ta­ ble 3. Overall, it appears that AUDREY II is slightly more accurate than FORTE, and AUDREY Il's revised theories are closer to both the original theory and the known correct theory. However, these results must be considered tentative since they involve comparison with only a single run of FORTE. We believe the difference in distance between the two systems is accounted for by the fact that FoRTE includes more complex operators that can produce more drastic changes than AUDREY II, and that AUDREY II contains an abduction mechanism that pinpoints where to generalize a theory. . 4 There are actually five corrupt theories but the revised theory for the fourth case is incorrectly reported as the result for the fifth. Table 3: AUDREY II and FoRTE on four KRK theories. | Accuracy | Did. to | Dist. to | |------------|-----------|------------| | | I i~r=·~ | | | E | II | ~n·:.il | The difference between AUDREY II and FoRTE ts greatest for theory 1 since AuDREY II performs bet­ ter on all three measures. The initial theory has three errors: two missing literals (in different clauses) and an extra clause. FORTE's revised theory deletes one of the clauses that was missing a literal, learns a semantically equivalent clause for the other missing literal, and spe­ cializes the extra clause into two clauses. AUDREY ll's best revision of ten trials was semantically correct (100% accuracy) with distance three from the original and four from the correct theory. AUDREY Il's worst revision was 92% accurate and only fixed one of the three errors. Theory 2 had four errors: an incorrect clause, a miss­ ing clause, a clause missing two literals, and a ~la~se with an incorrect literal. FORTE only fixed the mtssmg clause by approximating it with three new clauses (this is why the distance measures are high) . In every case, AUDREY II correctly found the missing clause and in four of the ten trials it learned an extra clause to repair some of the other errors. FoRTE's revised theory out­ performed AuDREY I l's on accuracy but at the exp~nse of creating a theory that was further from the ongmal and correct theories than AUDREY II did on average. Theory 3 had a single missing literal that had little effect on accuracy (the initial theory is 99.9% accurate) . Neither FORTE nor AUDREY II repaired the theory so their performances on each dimension was the same. Theory 4 had four errors: two missing literals, an ex­ tra clause that didn't cover any negatives, and an extra literal. FORTE only revised one of the clauses with a missing literal by deleting the clause. On this problem, FoRTE and AUDREY II performed quite closely on all three measures of accuracy and distance. ## 6.3 Discussion Since AUDREY II was designed to make small changes to theories, it performs significantly better than FocL at theory revision. However, given the results of the pre­ vious section it is clear that there is room for improve­ ment of AUD 1 REY II (and FoRTE). The distance metric proposed here has shown us that although these systems make accurate revisions to theories, neither system always finds the syntactically correct concept definition when it is known. One way to address this problem, used in KR-FocL, is to allow the user to decide among changes that have the same accuracy. A user who knows that the part-time status of a student is a function of the number of credits the student is enrolled in, would not make the incorrect revision to the student loan problem reported in Section 6.1. A better approach might be to provide this knowl­ edge to a theory revision system in the form of rule mod­ els [Davis, 1978] or higher-order relationships between predicates such as those expressible in CYC [Lenat and Guha, 1990]. ## 7 Conclusion Theory revision systems have the goal of improving the accuracy of the initial theory as well as some constraints on the type and degree of revisions that are desirable. We argue that revised theories should be as close to the original as possible. Unfortunately no theory revision systems to date have been evaluated in terms of the de­ gree of revision made to the initial theory. In this paper we proposed a measure for the distance between two theories. This measure corresponds to the number of edit operations at the literal level required to transform one theory into another. This measure can be used in conjunction with accuracy to give a better overall evaluation of the quality of revised theories when comparing one theory revision system to another. The distance metric can also be a useful tool when the correct theory is known. Comparisons of the revised and correct theories give a measure of a system's ability to learn theories in a form experts would write. As further work is done in t.he area of theory revision, new techniques for evaluating and comparing systems are needed. We believe our measure of theory distance is a useful and important one and hope other researchers will adopt its use. ## References 1. Bergadano and Giordana, 1988) F . Bergadano and A. Gior- dana. A knowledge intensive approach to concept induc- tion. In Proceedings of the Fifth International Conference on Machine Learning, pages 305-317, Ann Arbor, Michi- gan, 1988. 2. Morgan Kaufmann . 3. Cohen, 1992a) W. Cohen. Abductive explanation-based learning: A solution to the multiple inconsistent expla- nation problem. Machine Learning, 8:167-219 , 1992. 4. Cohen, 1992b) W. Cohen. Compiling prior knowledge into an explicit bias. In Proceedings of the Ninth Interna- tional Conference on Machine Learning, pages 100-110, Aberdeen, Scotland, 1992. 5. Morgan Kaufmann . [Davis, 1978) 6. R. T. Davis. Model-directed learning of pro- duction rules. In D. Waterman and F. Hayes-Roth, edi- tors, Pattern-directed inference systems. Academic Press, 1978. 7. Flann and Dietterich, 1989) N. Flann and T . Dietterich. A study of explanation-based methods for inductive learning. Machine Learning, 4:187-226, 1989. 8. Hirsh, 1989) 9. H. Hirsh . Combining empirical and analytical learning with version spaces. In Proceedings of the Sixth International Workshop on Machine Learning, pages 29- 33, Ithaca, NY, 1989. 10. Morgan Kaufmann. 11. [Kuhn, 1962] T. Kuhn. The structure of scientific revolu- tions. University of Chicago Press, 1962. 12. [Lawler, 1976] E. L. Lawler. Combinatorial optimization: Networks and matroids. Holt, Rinehart and Winston, 1976. 13. [Lenat and Guha, 1990] D. Lenat and R: V. Guha. Building large knowledge-based systems: Representation and infer- ence in the CYC project. Addison-Wesley, 1990. 14. [Mooney and Richards, 1992] R. Mooney and B. Richards. Automated debugging of logic programs via theory revi- sion. In Proceedings of the International Workshop on In- ductive Logic Programming, Tokyo, Japan, 1992. 15. [Muggleton and Buntine, 1988] S. Muggleton and W . Bun- tine. Machine invention of first-order predicates by invert- ing resolution . In Proceedings of the Fifth International Workshop on Machine Learning, pages 339-352, Ann Ar- bor, Ml , 1988. 16. Morgan Kaufmann . [Muggleton and Feng, 1990] 17. S. Muggleton and C . Feng. Ef- ficient induction of logic programs. In Proceedings of the First Conference on Algorithmic Learning Theory, Tokyo, Japan , 1990. Ohmsha. 18. [Norvig, 1992] P. Norvig. Paradigms of artificial intelligence programming: Case studies in Common Lisp. Morgan Kaufmann, 1992. 19. Ourston and Mooney, 1990) D. Ourston and R. Mooney. Changing the rules: A comprehensive approach to theory refinement . In Proceedings of the Eighth National Con- ference on Artificial Intelligence, pages 815-820, Boston, MA, 1990. 20. Morgan Kaufmann. [Pazzani and Brunk, 1991] 21. M. Pazzani and C . Brunk. De- tecting and correcting errors in rule-based expert systems: An integration of empirical and explanation-based learn- ing. Knowledge Acquisition, 3:157-173, 1991. 22. [Pazzani and Kibler, 1992] M. Pazzani and D. Kibler. The utility of knowledge in inductive learning. Machine Learn- ing, 9:57-94 , 1992. 23. [Quinlan, 1990] J. R. Quinlan. Learning logical definitions from relations. Machine Learning, 5:239-266, 1990. 24. [Richards and Mooney, 1991] B. Richards and R. Mooney. First-order theory revision . In Proceedings of the Eighth International Workshop on Machine Learning, pages 447- 451 , Evanston, IL, 1991. 25. Morgan Kaufmann . 26. [Richards, 1992] B. Richards. An operator-based approach to first-order theory revision. PhD thesis, University of Texas, Austin, TX, 1992. 27. [Shasha and Zhang, 1990] D. Shasha and K. Zhang. Fast al- gorithms for the unit cost editing distance between trees. Journal of Algorithms, 11:581-621 , 1990. 28. [Swartout, 1981] W . Swartout. Explaining and justifying in expert consulting programs. In Proceedings of the Seventh International Joint Conference on Artificial Intelligence, pages 203-208, Vancouver, B.C., 1981. Morgan Kaufmann. [Tai, 1979] 29. K. C . Tai. The tree-to-tree correction problem. J. Assoc. Comput. Mach ., 26:422-433, 1979. 30. [Towell, 1991] G. Towell. Symbolic knowledge and neural net- works: Insertion, refinement and extraction. PhD thesis, University of Wisconsin, Madison, WI, 1991. 31. [Wogulis, 1991] J. Wogulis. Revising relational domain the- ories. In Proceedings of the Eighth International Workshop on Machine Learning, pages 462-466 , Evanston, IL, 1991. 32. Morgan Kaufmann.