Not the Path to Perdition: The Utility of Similarity-Based Learning

Michael LebowitzAAAI 1986

TL;DR

This paper argues that similarity-based learning (SBL), often seen as a less rigorous approach than explanation-based learning (EBL), is crucial for robust machine learning. It proposes that SBL provides essential generalizations that EBL can then refine, and that SBL is vital when causal models are too complex or impossible to construct.

What Problem Does This Paper Address?

The paper tackles a fundamental question in machine learning: why is similarity-based learning (SBL) effective? While SBL, which generalizes concepts by finding commonalities across multiple examples, has a long history and proven success, its theoretical grounding is questioned. Proponents of explanation-based learning (EBL), which derives generalizations from a single example by building a causal model, argue that their approach is more fundamentally sound. EBL's strength lies in its ability to derive valid and useful generalizations from causal analyses. However, SBL's success, despite potentially relying on mere coincidences, suggests there's more to it. The paper aims to explain why SBL is not just useful but essential for a complete learning system, especially when EBL's requirements for complete domain knowledge and computational feasibility are not met.

Methods

The paper doesn't introduce a new algorithm but rather presents a theoretical argument for the integration of SBL and EBL. It outlines four key reasons for SBL's utility:

  1. Causality is not always determinable: In complex, noisy, or novel domains, constructing a complete causal model for EBL is often impractical or impossible. SBL, by focusing on observed regularities, can still provide useful generalizations.
  2. Similarity implies causality: While coincidental similarities exist, observed similarities in data often arise from underlying causal mechanisms. SBL can detect these regularities, providing a starting point for understanding causality.
  3. Refining generalizations: SBL-generated concepts are not static. They can be refined over time by identifying and removing features that are frequently contradicted by new examples, thus mitigating the impact of coincidences.
  4. Complementary approaches: SBL and EBL work best together. SBL can generate initial, broad generalizations, and EBL can then be applied to these generalizations to build more robust causal explanations, significantly reducing the search space for EBL.

The paper uses the UNIMEM system as an example to illustrate SBL's generalization process. UNIMEM takes feature-value pairs describing entities (like universities) and builds a generalization hierarchy by retaining identical features, averaging similar ones, and discarding significantly different ones.

Datasets

The paper uses a dataset of university information collected from students in an Artificial Intelligence class at Columbia University to illustrate the concepts of SBL and EBL. This dataset is used as an example for UNIMEM's generalization process.

Key Insights and Ideas

  • SBL is not just about coincidences: While SBL might appear to rely on coincidences, the paper argues that observed similarities often point to underlying causal mechanisms, making them valuable for learning.
  • EBL has practical limitations: The assumption of complete domain knowledge and computational feasibility for EBL is often unrealistic in real-world scenarios. SBL offers a viable alternative or complementary approach in such cases.
  • Predictability as a bridge: SBL can identify "predictive" features that appear in few generalizations. These features are likely causes in an underlying explanation and help guide the direction of causality, providing a starting point for EBL.
  • Refinement is key: SBL generalizations can be improved by iteratively removing features that are contradicted by new data, making them more robust and less susceptible to coincidental patterns.
  • Integrated learning is optimal: The most powerful learning systems will likely combine SBL's ability to find broad patterns with EBL's capacity for deep causal understanding. SBL can act as a bottom-up control mechanism for EBL's top-down processing.

Key Results

The paper does not present quantitative results in terms of accuracy or performance metrics. Instead, it offers a qualitative argument for the necessity of SBL. The key "result" is the theoretical framework presented, demonstrating why SBL is a vital component of a comprehensive learning system. The UNIMEM example illustrates how SBL can produce generalizations (like GND1) from limited domain information, which can then be further processed or refined.

Limitations and Future Work

The authors acknowledge that while SBL can identify similarities and refine generalizations, it doesn't inherently provide a causal explanation. The paper suggests that the "real world" examples of weather phenomena and crime investigations illustrate how human problem solvers use integrated learning, relying on SBL to identify coincidences that then become the focus of deeper causal investigation. Future work would involve implementing and testing integrated learning systems that leverage SBL for initial generalization and EBL for deeper causal analysis. The paper also notes that the "perfect learner" paradigm, common in EBL, is a limitation that SBL can help overcome by dealing with noisy and imperfect data.

Summary updated

BibTeX
@inproceedings{lebowitz1986not,
  author = {Michael Lebowitz},
  title = {{Not the Path to Perdition: The Utility of Similarity-Based Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}

Loading related content...

Figure