Abstract
This report discusses what it means to claim that a representation is an effective encoding of knowledge. We first present dimensions of merit for evaluating representations, based on the view that usefulness is a behavioral property, and is necessarily relative to a specified task. We then provide methods (based on results from mathematical statistics) for reliably measuring effectiveness empirically, and hence for comparing different representations. We also discuss weak but guaranteed methods of improving inadequate representations. Our results are an application of the ideas of formal learning theory to concrete knowledge representation formalisms.
Introduction
In the field of Knowledge Representation (KR), researchers frequently claim that one formalism is superior to another. Historically, these claims have often relied on "internal" criteria such as conciseness, elegance, or simplicity. However, these metrics are inherently subjective and do not necessarily correlate with the actual performance of an AI system in a real-world environment.
Greiner and Elkan (1991) argue for a shift toward operational criteria for evaluating representations. They propose that a representation's value should be measured by its external behavior—how accurately and efficiently it answers questions relevant to a specific task. This paper establishes a rigorous, behavior-based framework for measuring utility and provides statistical methods for comparing and optimizing representations.
The Utility Framework
The core of this approach is an "external" perspective where a representation $R$ is treated as a black box. As illustrated in the diagram below, the system receives a sequence of queries $\bar{q}$ and produces corresponding answers.
The effectiveness of $R$ is quantified through a Utility Measure ($M$), which is a weighted linear combination of three primary dimensions:
- Accuracy: The degree to which the system's answers match a ground-truth "oracle."
- Categoricity: The system's ability to provide a definitive answer (Yes/No) rather than "I Don't Know" (IDK).
- Timeliness: The computational cost or time required to return an answer.
By defining utility in this way, the framework acknowledges that a system which is 100% accurate but always answers "IDK" (the "ignorant baseline") has zero practical utility. Furthermore, it allows for trade-offs, such as accepting occasional errors in exchange for significant gains in speed.
Illustrative Examples
To demonstrate the framework, the authors use several illustrative examples, such as "Robbie the Robot" (a key-retrieval task) and the "Nixon Diamond" (a classic non-monotonic logic problem). A particularly clear example involves a rule-based system for deciding whether to buy a car.
In this simple logic base, the goal buyCar(X) can be satisfied if the car is fast(X) or cheap(X). The utility of this representation depends on the distribution of queries and the facts available in the database ($DB_1$). If most cars in the environment are cheap but not fast, a search strategy that prioritizes the cheap(X) rule ($R_c$) will have higher utility due to improved timeliness.
Key Insights and Results
The paper provides several formal results for measuring and improving utility:
- Statistical Estimation: Since it is impossible to test a representation on every potential query, the authors use Chernoff bounds to determine the sample size $N$ needed to estimate utility with high confidence. They prove that for any $\epsilon, \delta > 0$, there exists an $N$ such that the estimated utility is within $\epsilon$ of the true utility with probability at least $1-\delta$.
- Task-Specificity: A central insight is that utility is not an intrinsic property of a representation but is relative to a query distribution. A representation optimized for one environment may perform poorly in another.
- Optimization via PALO: The authors introduce PALO (Probabilistic Algorithms for Locating Optima), a hill-climbing technique. PALO uses training examples to iteratively modify a representation—for instance, by reordering rules or pruning search trees—to move toward a local optimum of utility. This provides a formal bridge between symbolic AI and statistical learning.
Conclusion
This work remains a foundational contribution to AI by providing a rigorous methodology for empirical KR research. While it assumes a stationary distribution of queries and the availability of an oracle for ground truth, it successfully moves the field toward objective, performance-based evaluation. Future work in this area involves extending these metrics from "symbol-level" optimizations to more fundamental "knowledge-level" changes and addressing non-stationary environments.
Summary updated