Using Case-Based Reasoning in Interpreting Unsupervised Inductive Learning Results

IJCAI 1997

TL;DR

This paper introduces a novel approach to interpret the results of unsupervised inductive learning by combining case-based reasoning (CBR) with concept hierarchies. This method aims to bridge the gap between understanding learned concepts and making predictions, offering a more intuitive and robust interpretation than traditional methods.

What Problem Does This Paper Address?

Interpreting the output of machine learning models, especially in unsupervised learning, is a significant challenge. While unsupervised learning excels at discovering patterns and structures in data without explicit labels, the resulting "concepts" can be abstract and difficult for humans to understand or use for prediction. Traditional inductive learning often focuses on generating these concepts, but the process of interpreting them – understanding what they represent and how to apply them to new, unseen data – has received less attention, particularly in unsupervised settings. This paper addresses this gap by proposing a method to interpret concept hierarchies learned by the OSHAM system, making the unsupervised learning process more transparent and actionable.

Methods

The core of this paper lies in the interpretive process of the OSHAM (Object-Oriented Self-Organizing Hierarchical Abstract Machine) system. OSHAM learns concept hierarchies from unlabeled data. The authors propose to interpret these learned hierarchies by combining two key ideas:

  • Concept Hierarchies: OSHAM represents concepts not just by their intent (properties) and extent (instances) but also within a hierarchical structure. This hierarchy captures relationships between concepts, allowing for a more nuanced understanding. Each concept is described by a 10-tuple of attributes, including its level, super/sub-concepts, intent, extent, dispersion, probability, and quality of splitting.
  • Case-Based Reasoning (CBR) for Interpretation: Instead of relying solely on the learned concept descriptions (intensional representation), the paper leverages CBR. Specifically, it uses the "nearest neighbor" principle. When an unknown instance needs to be classified, the system finds its nearest neighbor in the training data and uses the concept associated with that neighbor. This is combined with a heuristic function that considers various factors (level, leaf status, probabilities, dispersions) to determine the "best matched" concept for the instance. This approach aims to provide a "satisficing degree of prediction," acknowledging that perfect prediction might not always be achievable.

Datasets

The paper evaluates its approach using ten datasets from the UCI repository:

  • Wisconsin breast cancer (breast-w)
  • Congressional voting (vote)
  • Mushroom (mushroom)
  • Tic-tac-toe (tictactoe)
  • Glass identification (glass)
  • Ionosphere (ionosphere)
  • Waveform (waveform)
  • Pima diabetes (diabetes)
  • Thyroid (new) disease (thyroid)
  • Heart disease Cleveland (heart-c)

These datasets vary in the number of attributes (discrete and continuous), instances, and "natural" classes. The evaluation uses a 10-fold cross-validation strategy.

Key Insights and Ideas

  • Interpretation is Crucial: The paper strongly advocates that the interpretive process should be an intrinsic part of unsupervised learning, not an afterthought. Without interpretation, learned concepts lack meaning and practical utility.
  • CBR Complements Generalization: The authors propose that CBR, with its focus on specific cases, can effectively interpret the results of unsupervised learning, which often relies on generalization and may not always capture all nuances.
  • Hierarchical Context Matters: Using the concept hierarchy provides a richer context for interpretation than isolated concept descriptions. The relationships between concepts (super/sub-concepts) aid in deciding the best match.
  • "Satisficing" Prediction: The approach doesn't aim for perfect prediction but rather a "satisficing degree," acknowledging the inherent uncertainties in unsupervised learning, especially in boundary regions of concepts. This is achieved through a heuristic function that balances multiple factors.

Key Results

The experimental results, summarized in Table 3, show that the proposed OSHAM-NN+T interpretation method achieves competitive predictive accuracies compared to supervised learning methods like C4.5 and CART-like, as well as another unsupervised method, AUTOCLASS.

  • Predictive Accuracy: OSHAM-NN+T demonstrates comparable performance to AUTOCLASS across various datasets, with accuracies often in the high 80s and 90s for some datasets. For instance, on the "breast-w" dataset, OSHAM-NN+T achieved 92.6% accuracy, while AUTOCLASS achieved 92.1%.
  • Interpretability Advantage: A key qualitative result is that OSHAM's concept hierarchies are considered "easily understood" due to their extended classical view and graphical support, which is an advantage over methods that might produce less transparent representations.
  • Effectiveness of CBR: The comparison between OSHAM-NN (using only nearest neighbors) and OSHAM-NN+T (using nearest neighbors and the T function for interpretation) suggests that the combined approach is beneficial for interpreting unsupervised induction results.

Limitations and Future Work

  • Continuous Attributes: While OSHAM handles continuous attributes by discretizing them using k-means, the paper notes that further investigation into the effects of k-nearest neighbors and discretization strategies on interpretation is warranted.
  • Domain Expertise: The interpretation of the "satisficing degree" (Φ) values depends on user judgment or domain expert input, suggesting a potential area for further refinement or automation.
  • Further Investigation: The authors explicitly state that their future research will focus on further investigations into k-nearest neighbors and discretization, as well as experiments with a larger number of datasets. They also suggest that CBR is a promising avenue for interpreting unsupervised learning results in general.

Summary updated

BibTeX
@inproceedings{1997using,
  title = {{Using Case-Based Reasoning in Interpreting Unsupervised Inductive Learning Results}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1997},
}
Figure