EFFICIENT DATA-DRIVEN THEORY REVISION SYSTEM

A computer system takes as input an initial fault hierarchy KB.sub.0 and a set of annotated session transcripts C={<.pi..sub.j,r.sub.j >} and is given a specified set of revision operators T={.theta..sub.i } where each .theta..sub.i .epsilon. T maps a fault hierarchy KB to a slightly different hierarchy .theta..sub.i (KB). The computer system uses T to hill climb from the initial fault hierarchy KB.sub.0, through successive hierarchies, KB.sub.1 . . . KB.sub.m, with successively higher empirical accuracies over C. At each stage, to go from a fault hierarchy KB.sub.k to its neighbor KB.sub.k+1, the computer system must evaluate KB.sub.k 's accuracy over C, as well as the accuracy of each KB' .epsilon. N(KB.sub.k). The computer system provides an efficient way of evaluating the accuracy of KB.sub.k, and each .theta..sub.i (KB.sub.k), towards determining which, if any, .theta..sub.i (KB.sub.k) is more accurate than KB.sub.k. It exploits a few key observations. First, as each transformation used to map one hierarchy to a related one performs only local changes to the hierarchy, it will have only minor and easily computed effects on any instance. Second, most transformations will have no effect on many instances. Finally, one can bound how much the accuracy score for a knowledge base can change based on any instance, which means branch-and-bound techniques can be used to avoid computing the accuracy scores for various hierarchies that cannot be optimal.