Compositional Instance-Based Learning

Patrick S. Broos, Karl BrantingAAAI 1994

Abstract

This paper introduces Compositional Instance-Based Learning (CIBL), an algorithm designed to capture user preference predicates by treating training instances as directed arcs within a feature space. Unlike traditional methods that struggle with non-linear or polymorphic preferences, CIBL leverages the transitivity of preferences through graph-based pathfinding. Experimental results in artificial domains and a telescope scheduling application show that CIBL significantly outperforms decision tree induction (ID3) in high-dimensional environments and complex preference landscapes.

Introduction

Developing knowledge-based systems often encounters the "knowledge acquisition bottleneck," where experts find it difficult to explicitly define the rules governing their decisions. Learning apprentice systems aim to mitigate this by automatically acquiring knowledge through observation. A critical component of this is learning preference predicates—rules that determine why one state is preferred over another (e.g., preferring Schedule A over Schedule B).

Traditional approaches, such as linear weighting or decision trees like ID3, often fail when preferences are non-linear or highly individualized. The authors propose CIBL to address these complexities, particularly in scientific domains like astronomy where decision-making is nuanced and data can be high-dimensional.

Methodology

CIBL extends standard Instance-Based Learning (IBL) by incorporating the principle of transitivity: if a user prefers state $A$ over $B$, and $B$ over $C$, it is inferred they prefer $A$ over $C$.

Representation and Pathfinding

In CIBL, training instances are represented as directed arcs in an $N$-dimensional feature space, pointing from a less-preferred state to a more-preferred state. To compare two novel states, $X$ and $Y$, the algorithm constructs a graph consisting of training arcs (known preferences) and uncertain arcs (potential transitions).

Pathfinding in CIBL using Dijkstra's algorithm to determine preference between states X and Y.

The system employs Dijkstra’s algorithm to find the lowest-cost path between the states. Training arcs have zero cost, while uncertain arcs have a cost equal to their Euclidean length. If the path from $Y$ to $X$ is less "expensive" than the path from $X$ to $Y$, the system predicts a preference for $X$. This compositional approach allows the model to follow the "contour" of a user's evaluation function more effectively than isolated instance matching.

Experimental Evaluation

The performance of CIBL was evaluated against ID3 and 1ARC (a standard 1-NN approach for arcs) across artificial domains and a real-world telescope scheduling application (The Observing Assistant).

Key Results

  • High-Dimensional Scaling: While ID3 performed well in low-dimensional spaces (2D-3D), CIBL demonstrated superior accuracy as dimensionality increased beyond 5. This scaling advantage is crucial for complex real-world feature spaces.
Comparison of error rates between ID3 and CIBL as feature space dimensionality increases.
  • Handling Non-Linearity: CIBL consistently outperformed ID3 on complex functions like sinusoids and quadratics, where the direction of preference changes across the feature space.
  • Telescope Scheduling: In live tests with astronomers, CIBL achieved a cumulative error rate of 37%, notably lower than ID3's 47%. This confirms that CIBL is better suited for the "polymorphic" nature of individual expert preferences.

Discussion and Future Work

A significant insight from this research is that composition—chaining instances together—provides a robust model for preference learning. However, CIBL remains sensitive to irrelevant features, as its Euclidean distance metric weights all dimensions equally. Future work should focus on automated feature weighting and pruning to improve noise tolerance. Additionally, while effective, the computational cost of Dijkstra’s algorithm on large datasets warrants further optimization for real-time applications.

Summary updated

BibTeX
@inproceedings{broos1994compositional,
  author = {Patrick S. Broos and Karl Branting},
  title = {{Compositional Instance-Based Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure