Measuring and Improving the Effectiveness of Representations

1 Introduction

A principal aim of research in knowledge representation and reasoning is to design good formalisms for repre­ senting knowledge about the world. This paper gives operational criteria for evaluating the goodness of a "representation" . 1 Many areas of AI research can use these results. For example, many papers on nonmono­ tonic logic [Reiter, 1987] implicitly or explicitly make the claim that one formalism leads to better representations

*Supported by an Operating Grant from Canada's Natu­ ral Science and Engineering Research Council. Both authors would like to thank William Cohen, Dave Mitchell and the

anonymous referees for their useful comments.

tsupported by a grant from the Powell foundation. This research was performed while at the University of Toronto.

1 "Representation" is an abbreviation for "representational system", which refers to a process that answers questions; see Section 2. N.b., it is not just a data structure, but will include a reasoning process as well.

Charles Elkan t

Department of Computer Science University of California, San Diego La Jolla, California 92093-0114

elkan~cs.ucsd.edu

than the others. Similarly, the aim of an explanation­ based learning (EBL) system [Mitchell et al., 1986; DeJong and Mooney, 1986; DeJong, 1988] is to trans­ form one problem-solving representation into a better one. However these articles do not specify precisely what it means to say that one representation is better than an­ other. This paper addresses this shortcoming.

Our research has a pragmatic objective: to develop methods for deciding, for example, what type of repre­ sentation should be installed in Robbie the Robot to en­ able it to retrieve keys located several miles away. The criteria for Robbie's success are fundamentally behav­ ioral - what is critical is the correctness of Robbie's in­ teractions with the world. This paper therefore adopts an "external" perspective, in which the goodness of a representation depends on its observable outputs.

One alternative perspective is worth mentioning. The "internal" perspective asks questions about a represen­ tation, such as whether it is elegant, concise, or sim­ ple. These properties may be desirable for certain tasks, such as communicating information to another agent. 2 However, while it is possible to provide operational cri­ teria for evaluating internal properties of a representa­ tion, these properties necessarily reflect some subjective choices, and their correlation with the usefulness of a representation is usually difficult to gauge. External cri­ teria, on the other hand, can directly guide the design of useful AI systems.

So, what behavioral features do good representations exhibit? Accuracy and coverage are two: everything else held equal, a representation should state only true facts, and it should state as many true facts as possible. Time­ liness is another important property: an accurate an­ swer to a question can be worthless if the answer arrives too late. (The correct information that "stock X will go up tomorrow" is useless unless it arrives before the end of today's trading.) In general we have to settle for representations that are not both universally accurate and fast; c.J., [Nagel and Newman, 1958; Simon, 1981; Levesque and Brachman, 1985]. Any single-valued met­ ric for evaluating representations must embody decisions as to the relative importance of accuracy, coverage, and timeliness. The tradeoffs chosen will depend on the con­ text: for example, fast responses are more important when predicting future events than in most design tasks. This measure must also be relative to the anticipated set of problems. (E.g., it may be acceptable for a represen­ tation to return incorrect answers to certain questions, but only if those questions occur very rarely; hence, we need to know how often those questions will appear.)

2 Much of the work on nonmonotonic formalisms is moti­ vated by internal criteria of goodness. The notorious frame problem, in its simplest guise, is to find a formalism that ad­ mits concise representations of actions and their effects; and

conciseness is an internal criterion.

This report shows how to define measures of the ef­ fectiveness of a representation, how to score representa­ tions according to these measures, and how to transform representations in ways that increase their scores. Sec­ tion 2 discusses the dimensions of merit just mentioned and proposes combined utility measures. Sections 3 and 4 show how to use a set of observations to determine with confidence whether a representation is acceptable, and to improve a "deficient" representation, or even to find an approximately optimal representation, with high probability.

2 Framework

Our aim here is not to debate what representations re­ ally are; as a working definition, we take it that a rep­ resentation is some sort of system capable of answering questions about the world. Mathematically, a represen­ tation is a function that maps queries to answers. In practice, representations are typically combinations of a data structure encoding aspects of the outside world and an inference procedure; see Section 4 for examples.

Our concern is with the effectiveness of a representa­ tion as perceived by an external observer, who wants to use the representation to perform some task. Here, per­ forming a task involves asking the representation ques­ tions and receiving its answers. Formally, we assume that there is a set Q of all relevant questions that the representation may be asked.

In Figure 1, R is the name of a representa­ tion that takes as input a sequence of queries ij = (ql,q2, ... ,q;, . .. ) and after each query q;, produces a candidate answer R( q;) . Each q; is drawn randomly from Q according to an arbitrary, stationary probability dis­ tribution.

For simplicity we shall assume that the response to any query is one of {Yes, No, IDK}, where IDK is read as "I don't know." In order to talk about the accuracy and coverage of representations, we need a specification of when responses are correct. Formally, we posit the existence of an oracle, 0(·), that maps each query onto its unique correct answer Yes or No. 3 Finally, to discuss the speed of a representation, we need a time function r(R, q;) that returns the time required by R to respond to the query q; . 4

One example of a representation is a set of axioms in any standard logic, together with an appropriate infer­ ence procedure. If the collection of axioms is insufficient, or if the inference procedure is incomplete, then the rep­ resentation's response to some queries may be IDK. If some of the axioms in the set are false, or if the inference procedure is unsound, then some Yes or No answers way be incorrect. 5

Dimensions of merit: Criteria for the effectiveness of a representation depend on the expected use of the representation. Some tasks require complete accuracy, while others can allow some inaccuracy in exchange for increased efficiency, and so on. Nevertheless, it is pos­ sible to identify some orthogonal dimensions of merit.

3 The existence of 0(·) presupposes that queries have unique answers. This condition could be relaxed. In ad­ dition, the answers to questions could also provide extra in­ formation, such as a. witness for an existential query, or in­ formation about the derivation path used to solve a problem. See [Greiner and Elkan, 1991].

4 We could use the r function to deal with resource require­ ments in general, including space usage, power consumption, etc., as well as time.

5 If the logic used by the representation has a model­ theoretic semantics, the notional oracle that defines the cor­ rect answers of queries can be identified with an intended model.

With respect to the query q, a representation R is

accurate if it responds with either the correct answer O(q) or IDK when asked q: i.e., if R(q) E {O(q), IDK}

categorical if it responds either Yes or No hut not IDK: i.e., if R(q) E {Yes, No}

t-eflicient if, when asked q, it responds in at most t time units: i.e., if r(R, q) $ t.

These three properties are orthogonal, in the sense that a representation can possess any combination of them. As a simple example, the "ignorant" representation that immediately answers every question with IDK, is univer­ sally accurate and £-efficient for some small c, hut it is sadly uncategorical.

The three dimensions of merit listed above are not exhaustive: i.e., they do not span the space of exter­ nal criteria of merit for representations. In particular, [Segre, 1988) identifies a number of further dimensions of merit that are important if the world being modeled by the representation is uncertain. Our dimensions are still quite general; we show below that linear combina­ tions cover many standard situations.

Utility measures: A utility measure evaluates a rep­ resentation with respect to the set Q of all questions it will he asked. Taking into account the probability dis­ tribution over Q, the measure M(R) of a representation R is defined as the expected value of UM over Q, where UM is a function that returns the score of R on a single query; the arguments of UM are the query, its correct answer, the representation's answer to the query, and the time required. If ij is an infinite sequence of queries, such that each element of ij is drawn independently from Q according to the fixed probability distribution, then M(R) can also he defined by the following equation:

We shall only consider utility measures whose scoring functions are hounded above and below; i.e., in the class U >. for some .X E 'R +, where

This property is technically convenient for provi~g the results of the following sections, hut similar results hold for the class U of all utility measures.

Since a perfectly accurate, categorical, and efficient representation is usually unobtainable, and the relative importance of the three dimensions depends on the task for which the representation is to he used, we now define a class of utility measures that incorporate task-specific tradeoffs. This class consists of weighted linear combi­ nations of an accuracy value, a categoricity value, and a timeliness value; as shown below:

This equation characterizes the entire class of hounded, linearly separable utility measures, where the time penalty is linear. 6 There are several important spe­ cial cases: Setting O't = 0 indicates that efficiency is unimportant; setting ao = a_ discriminates only he­ tween correct and incorrect · answers, etc.

3 Appraising and Comparing Representations

Appraising utility: Suppose someone hands you a black-box representation and claims that the M value of this representation is above some threshold. How con­ fident should you he with that assessment? There are clearly several approaches. First, you might trust the supplier of the representation - some people really do think they are purchasing the Brooklyn Bridge. Second, you could analyze the internals of the representation. For example, imagine that the representation's answers are the result of running a sound proof procedure on a collection of true facts. You can then he completely confident that all its answers will he accurate. If you know, furthermore, that all facts have a certain syntac­ tic form (e.g., all are DATALOG definite clauses), you can know that all answers are obtainable in polynomial time. The remainder of this section presents a third approach, in which a sequence of examples of the representation's behavior is used to approximate its real utility.

Our objective is to determine the worth of a repre­ sentation for some specific application; that is, we want to know how it will perform over the particular distrihution of queries it will eventually see. The only empirical method that is guaranteed to provide this information in­ volves observing the representation perform throughout its entire lifetime; a most impractical approach. Fortu­ nately, however, we can obtain good estimates, based on a small set of samples, using "Chernoff bounds" [Cher­ noff, 1952]:

6 We assume that r(R, q) "tops off" at some upper limit. Notice this assumption holds for all of the utility measures discussed in Section 4.

Let {X;} be a set of independent, identically dis­ tributed random variables with mean p, whose val­ ues are all in the range [a, a + ~]; and let Sn = ! E;. 1 X; be the sample mean of n variables. We expect this average to tend to the population mean, p, as n - oo. Chernoff bounds tell us the prob­ able rate of convergence: the probability that "'Sn is more than p + P"' goes to 0 exponentially fast as n increases; and, for a fixed n, exponentially as P increases. Formally, [Bollobas, 1985, p. 12]

Recall now that a representation's utility is defined as the mean of its scores over its distribution of possible queries. Now suppose that the value of the scoring func­ tion is always in the range [-3, -3 + 5], say, and that the average observed score of the representation R is S10oo = 1. 7 after n = 1000 queries. Equation 1 says that the probability that the representation's real utility is greater than, say, {3 = 0.25 over the real utility is less than e- 2n(fJ/>.)~ = e- 2 xlOOOx(.ll.jA)~ ~ 0.0067.

We can therefore use the performance of a represen­ tation on a sampling of queries to approximate the rep­ resentation's true utility. The following lemma supplies the sample complexity required to estimate a representa­ tion's utility to high accuracy (within c) with high prob­ ability (at least 1- 6). 7

Lemma 1 Let £, 6 > 0 be given constants, R be a repre­ sentation, M(·) E U>. be a utility measure, and _MN 1 (R) be the approximation to M(·) obtained as the average score on Nt 4 ~ r! ( ~) 2 ln fl sample queries. Then

This means we can approximate the representation's true utility, with provably high probability to arbitrar­ ily high accuracy, by watching its behavior over enough samples. Notice the estimate .MN 1 (R), like the real M(R), depends on the distribution of queries that R

7 [Greiner and Elkan, 1991] provides the proofs for all of

the lemmas and theorems presented in this short paper.

will encounter; it therefore is more likely to provide a good indication of R's true utility than we would get by testing R on worst case queries, a set of concocted queries, a sample drawn randomly from a uniform dis­ tribution [Goldberg, 1979], or any particular collection of "benchmark challenge problems" [Keller, 1987].

Comparing representations: If we had an analytic technique for evaluating the utility of representations with respect to a distribution of queries, and knew this distribution of queries, we could directly determine which of two representations was better. In general we have neither analytic technique nor distribution, but we can fall back on an empirical technique - of "running"' both contenders; i.e., finding the "paired-t confidence"' [Law and Kelton, 1982].

Lemma 2 Let 6 > 0 be a given constant, and M(·) E U>. be a utility measure. Given any two representations, Rt and R2, let _MN (Rt) (respectively _MN (R2)) be the approximation to M(Rt) (respectively M(R2)) obtained as the average score on N E z+ samples. If

then M(R2) > M(Rt) holds with confidence 2:: 1 - 6. (Hence, we may believe that R2 isM-better than Rt)·

4 Improving a Representation

This section discusses various ways to improve a defi­ cient representation. The lemmas of the previous sec­ tion directly suggest a "generate and test" procedure for improving representations. Other approaches search the space of alternative representations more intelli­ gently. They use a set of "training examples" (perhaps ( qi, 0( qi)) query/ answer pairs) to construct a new repre­ sentation that is M-better than the original, with prov­ ably high probability.

Due to space limitations, this short paper can only summarize a few individual algorithms associated with various type of utility measures. The extended paper, [Greiner and Elkan, 1991], presents these algorithms (and others) in detail, and proves their correctness.

Improving efficiency (preserving accuracy): Sup­ pose that a representation is producing the correct an­ swers, but too slowly. As an example, consider the knowledge base shown in Figure 2, that states that we will buy a car if it is fast or cheap. Furthermore, our representation R1 searches this "inference graph" in a left-to-right order- i.e., given a query buyCar(ci) (for some constant ci), it would first use the 'RJ rule to reduce buyCar(ci) to the subgoal fast(ci), and then determine whether this proposition is in the fact set, DB1. If so (for example in the case where the top query was buyCar(c2)), R1 would return Yes and ter­ minate. If not, it would then follow the 'Re rule to the cheap(ci) subgoal, and ask if it is in the database. R1 would then return Yes or IDK, depending on the suc­ cess of that retrieval. Here, we say that R1 's strategy is (n,,n,, 'Re,De)·

Now imagine we find that R1 is relatively slow- per­ haps because the queries all dealt with c1, meaning R1 "wasted" its time on the (n,' n,) path, before finding the appropriate ('Re, De) path. One obvious proposal would be to change R1 to a new representation, R2 , that uses the different strategy, ('Re,De, n,,n,). No­ tice this R2 would be strictly better than R1, if aU of the queries were buyCar(c1). In general, we can com­ pute which the relative utilities of R1 and R2 if we know the costs of the various paths (e.g., the cost of following the ('Re, De) path), and the frequencies of the various possible queries (e.g., that 80% of the queries would be buyCar(c1), 5% would be buyCar(c2), and 15% would be buyCar(c) for some c such that buyCar(c) is not provable; see [Greiner, 1991]).

In general, we do not know this distribution informa­ tion. We can, however, use a set of samples to estimate it, and use this information to determine whether R2 would be better than R1, with high confidence. In fact, we can obtain reasonable estimates of this distribution by running R1 alone; see [Greiner and Cohen, 1991a]. That paper also shows how to extend this learning sys­ tem to handle more elaborate classes of inference graphs (with many different paths from query to retrieval, in­ volving conjunctions, etc.), and other types of modifica­ tions (besides simply rearranging the strategy). It also presents an efficient algorithm, PALO, that can "hill­ climb" in the space of representations, reaching a rep­ resentation that is, with high probability, close to a lo­ cal optimum. The PAO system [Greiner and Orponen, 1991] is another variant of this idea: it uses a set of training examples to identify a strategy that is, with high probability, arbitrarily close to the globally optimal strategy.

Increasing efficiency by decreasing accuracy: The previous subsection deals with speedup learning (per­ forming only "symbol-level" modifications [Dietterich, 1986]), whose objective is new performance systems that are as accurate and as categorical as the original sys­ tem, but (we hope) faster. This subsection removes this constraint, and considers techniques that are allowed to produce systems that are less accurate or less categori­ cal. The utility-based approach introduced in this paper allows us to quantify the tradeoffs among the various performance attributes of a representation. In particu­ lar, the relative values of a+ and a_ versus a, specify how much accuracy or categoricity we are willing to lose, in exchange for how much improvement in speed.

As a simple example of an application of this idea, consider the G M inference graph shown in Figure 3. As above, each node represents a (sub)goal, and each arc, a rule that reduces one goal to a subgoal. Some arcs are "probabilistic", meaning that whether a representation can traverse such an arc can depend on the contents of the fact set, or the particular query posed, etc. A repre­ sentation returns Yes if it reachs any leaf node. (More details appear in [Greiner and Cohen, 1991a].)

The R1 representation answers GO queries by explor­ ing the entire G M graph. Imagine the sub graph un­ der the B node is extensive, meaning it is expensive to search, and furthermore, that R1 seldom find answers in that subgraph, over the distribution of G(·) queries.

Now consider the R2 representation, which traverses some of the arcs in G M, in the same order as R1; but R2 completely skips B and its children. Of course, this R2 will not reach any node under B, and so can produce an incorrect answer. It will, however, require less time to produce that answer. Is it better than R1? This depends on the relative values of O't versus a+ + o-0 , and on the actual cost of searching under B, versus the frequency with which solutions will appear there.

We can consider this "delete subgraph" process as an operation. As above, we can provide conditions under which it (is likely to) produce a superior new represen­ tation, and build a PALO-like learning system that hill­ climbs in this space to a representation that is, with arbitrarily high probability, close to local optimum.

Two final notes: [1] We can use this same approach to deal with SAT problems: here, the inference graph is a complete binary tree, where each node corresponds to a literal, and one descending arc indicates that this literal should be positive, and other, that is should be negative. [2] Several previous systems have implicitly dealt with this theme, of gaining efficiency at the ex­ pense of accuracy or categoricity; see [Cohen, 1990], [Subramanian and Genesereth, 1987], [Levesque, 1986; Selman and Kautz, 1988; Etherington et al., 1989; Borgida and Etherington, 1989], [Selman and Kautz, 1991]. None, however, have explicitly quantified the tradeoffs.

Improving accuracy (ignoring efficiency): One standard issue with default logic is the "multiple ex­ tension problem" [Reiter, 1987]: For example, know­ ing the facts F1 = {B(T), P(T)} and the defaults v 1 = {d 1 . B(x): F(x) d . P(x): -.F(x)} ld · F(x) · 2 · -.F(x) , one cou conclude either F(T), based on the first fact and first default, d1; or -.F(T), based on the second fact and sec­ ond default, d2· 8

One way around this problem involves prioritizing the defaults [Przymusinski, 1987; Brewka, 1989]. Here, for example, we could specify d2 ~ d1, meaning we should use the d2 default if it applies, and only if it does not should we consider d1. Hence, R1, the default-based representation that uses this ordering, would conclude -.F(T) as desired, and not F(T).

Unfortunately, there is not always an appropri­ ate order of the defaults; consider, for example, the famous "Nixon diamond", based on the facts F2 = { Q(N), R(N)} and the defaults 'D2 = { d . Q(x): P(x) . R(x): -.P(x)} . 3 · P(x) , d4 · -.P(x) . Here, one could etther use da to conclude P(N), or use d4 to conclude -.P(N). 9

8 B ="Bird"; P ="Penguin"; T = "Tweety"; F ="Fly" .

Which ordering is appropriate: d3 ~ d4 or d4 ~ d3? Our paper takes a pragmatic approach to answering this question: the proper order is the one that produces the correct answer most often. This, of course, depends on the distribution of queries. For example, imagine we knew that the only individual that mattered (i.e., the only n such that Q( n) and R( n) held, and that ap­ peared in any "P(n)?" query) was n1, and that this n1 was a pacifist- i.e., the oracle (that emulates the "real world") claims P(nt). The "pragmatically correct" or­ dering, here, is da ~ d4, as this leads to the correct answer. Similarly, if we knew that there were many rel­ evant individuals, but very few were pacifists, then we would know that d4 ~ d3 is appropriate.

In general, however, we do not know the distribution. [Greiner and Cohen, 1991b] presents a PAO-like algo­ ri thm that uses a set of samples to approximate the distribution, to obtain an estimate that is sufficiently close to guarantee that the total ordering based on it will be close to the global optimal, with high proba­ bility. It also shows this task to be NP-hard, even in the simple case when only a single default is used in any derivation. That paper then discusses a PALO-like hill-climbing system that finds a representation that is usually arbitrarily close to a local optimum.

We close with a few final comments. [1] Notice we are only concerned with the accuracy of the resulting representation, but not with its efficiency. Hence, this learning process corresponds to a utility measure with a, = 0. [2] The "accuracy" of the resulting represen­ tation is improved with respect to the 0 oracle. While we think of this oracle as an encoding of the real world, this is not necessary; this overall learning system can be viewed as a way of obtaining a increasingly more cor­ rect "simulation" of an arbitrary function. [3] There are other approaches to this challenge. One obvious one is to remove the defaults (here usually called "hypotheses", etc.) that are inconsistent with the data. Essentially all inductive inference systems fit into the framework· see ,

9 N = "Nixon"; Q = "Quaker"; R = "Republican"; P =

"Pacifist" .

5 Conclusion

The principal claim of many papers on knowledge repre­ sentation is that one proposed representation is appro­ priate, or that one is better than another: e.g., that this axiomatization of liquids is good, or that this EBL pro­ cess does produce improved problem-solvers, and so on. The work reported here provides a way for future pa­ pers to add teeth to such claims, by defining a general approach to evaluating and comparing representations. The approach is based on the position that whether a representation is appropriate, or better than another, is a behavioral property, that must be defined relative to a specified task. In this paper, tasks are modelled as distri­ butions of anticipated queries, and the desired behavior of a representation is specified using a scoring function. In the spirit of traditional scientific methodology, the no­ tion of representation usefulness is given an operational definition that has no dependence on any subjective ob­ server.

After settling on a precise definition of usefulness, this paper provides a method for reliably (but ap­ proximately) measuring usefulness, and presents several transformations capable of improving an inadequate rep­ resentation. The space of techniques for improving rep­ resentations is open-ended. We hope other researchers will formulate their mechanisms in this framework, and so contribute to the growing class of useful transforma­ tions.