The Automatic Training of Rule Bases that Use Numerical Uncertainty Representations

Rich CaruanaUAI 1987

TL;DR

This paper introduces a method for automatically training rule-based expert systems that use numerical representations for uncertainty. By treating rule weights as parameters to be optimized, the authors demonstrate that this approach can outperform manually tuned systems and significantly reduce the burden on human experts.

What Problem Does This Paper Address?

Knowledge-based systems often struggle to accurately model human reasoning, especially when dealing with uncertainty and imprecision. While numerical representations (like probabilities or certainty factors) offer a way to capture this, they create significant challenges for knowledge acquisition and system development. Experts find it difficult to assign and interpret these numerical weights, and ad-hoc methods make objective validation nearly impossible. Manually tuning these weights is a time-consuming, inexact, and often subjective process that can lead to unintended negative consequences for system performance. This paper aims to automate this crucial tuning process.

Methods

The core of the paper proposes treating the training of rule weights as a numerical optimization problem. The system's rule weights are viewed as parameters in a multi-dimensional space, and the goal is to find the set of weights that minimizes an "error metric" (which corresponds to maximizing system performance).

The authors employ a steepest descent minimization algorithm as a basic example. This algorithm iteratively adjusts rule weights in the direction that most rapidly reduces the error metric.

A key innovation presented is the use of truth maintenance to improve the computational efficiency of this optimization process. Instead of re-evaluating the entire rule base for each weight adjustment, truth maintenance ensures that only the affected rules and their dependents are re-fired. This significantly reduces the computational cost, especially for larger rule bases.

Datasets

The paper describes experiments performed on a small certainty-factor classification system. The training data consisted of a diverse collection of objects, with some features being irrelevant to the classification problem. The authors do not specify the exact size or source of this dataset beyond stating it was used for experiments.

Key Insights and Ideas

  • Automating Expertise: The paper argues that while experts provide the symbolic structure of rules, the "power" or influence of these rules (represented by weights) can be learned automatically. This shifts the burden from precise numerical assignment to providing a good initial structure and relevant training data.
  • Truth Maintenance as an Efficiency Booster: The integration of truth maintenance is crucial for making the optimization process computationally feasible. Without it, training even small systems becomes impractical due to the repeated re-evaluation of the rule base.
  • Performance Metric is King: The success of automatic training hinges entirely on the quality of the performance metric. This metric must be continuous and capture the nuances of "rightness" or "wrongness" of the system's conclusions, potentially incorporating domain expertise and cost functions.
  • Beyond Expert Intuition: Automatically trained systems can achieve performance levels that human experts might consider unattainable, suggesting that optimization can uncover better weightings than human intuition alone.

Key Results

  • Automatically trained expert systems, even those initialized with zero weights, outperformed the best manually generated system in terms of classification accuracy and the sharpness of classifications.
  • The tuned system that started with the best human estimates of rule weights performed the best, highlighting the value of expert input as a starting point.
  • Training without truth maintenance was impractical, requiring hours per iteration and consuming significant virtual memory. With truth maintenance, training took approximately two hours on a Symbolics 3670.
  • The performance metric used was a simple one for classification systems, taking into account both the correctness and sharpness of the classification.

Limitations and Future Work

  • Local Minima: The optimization process can get stuck in local minima, leading to suboptimal rule weights and differing results depending on the initial parameterization. The authors suggest using techniques like simulated annealing to mitigate this.
  • Overtraining: There's a risk of "overtraining," where the system performs well on the training data but poorly on unseen data. More work is needed to define good training sets and detect/minimize overtraining.
  • Scalability: While promising for small systems, the authors acknowledge that further testing is needed to determine if the technique will scale up to larger, more complex systems. They also suggest exploring the independent training of system modules.
  • Epistemological Questions: The paper raises important questions about the interpretation of automatically acquired rule weights, especially in ad-hoc formalisms. It also touches on accountability and trust when expertise is derived from automated processes rather than solely from human experts.
  • Generalizability of Performance Metric: While a simple metric was used, the authors note that more complex metrics would be needed for many domains, potentially incorporating significant domain expertise.

Summary updated

BibTeX
@inproceedings{caruana1987automatic,
  author = {Rich Caruana},
  title = {{The Automatic Training of Rule Bases that Use Numerical Uncertainty Representations}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1987},
}
Figure