Flexibly Exploiting Prior Knowledge in Empirical Learning

TL;DR

This paper introduces a flexible method to integrate prior knowledge from potentially imperfect domain theories into inductive learning of decision trees. By augmenting data with "model-derived features" and biasing the learning algorithm to prefer these features, the system can achieve higher accuracy, especially when training data is unrepresentative.

What Problem Does This Paper Address?

Traditional machine learning often relies solely on data or fully specified expert knowledge. However, many real-world scenarios involve a mix: some existing knowledge (a model or domain theory) that might not be perfect, and a limited or potentially skewed dataset. The challenge is to effectively leverage this imperfect prior knowledge to improve inductive learning, rather than discarding it or assuming it's completely correct. Existing methods either rigidly adhere to the model, rejecting contradictory data, or revise the model heavily based on data. This paper aims to find a middle ground, allowing the learning system to flexibly use model-derived information while still being able to override it if the data strongly suggests otherwise.

Methods

The core of the paper's method is to augment the training data with features derived from a propositional domain theory. These "model-derived features" are categorized by their "level" in the theory hierarchy, with Level 0 being the final model prediction, Level 1 being intermediate concepts, Level 2 being rule features, and Level 3 being the raw, observable features.

The authors adapt the C4.5 decision tree algorithm to incorporate a "flexible domain-theory preference bias." This bias orders features by their level, preferring features closer to the final model prediction (lower level numbers). Crucially, this preference is not absolute. C4.5 will still select a raw feature (Level 3) if its information gain ratio is statistically significantly better than a preferred model-derived feature. This statistical testing is implemented using bootstrap methods to determine significance, allowing the system to balance confidence in the model with evidence from the data.

Datasets

The experiments were conducted using the audiology dataset from the UCI Machine Learning repository. This dataset contains 226 examples with 67 discrete features and 24 classes. The authors also generated imperfect domain theories by intentionally introducing errors (omission and commission) into a perfect theory derived from the complete dataset.

Key Insights and Ideas

  • Model-derived features enhance learning: Even imperfect domain theories, when translated into features, can significantly improve classification accuracy compared to using only raw features, especially with limited or skewed data.
  • Flexibility is key: A rigid adherence to prior knowledge can be detrimental if the knowledge is flawed or the data is truly representative. The proposed method's ability to flexibly override model preferences based on statistical evidence from the data is crucial.
  • Significance testing as a bridge: Using statistical significance testing to decide when to override a preferred model-derived feature provides a principled way to balance prior knowledge and empirical evidence.
  • Data representativeness matters: The effectiveness of model-derived features is highly dependent on the quality and representativeness of the training data. Skewed data highlights the benefits of this approach.
  • Model quality influences optimal bias: The "sweet spot" for significance testing (i.e., the optimal level of strictness) depends on both the quality of the domain theory and the size/representativeness of the training data.

Key Results

  • Augmenting data with model-derived features (even from imperfect theories like f5050, which has 50% contamination) significantly improved accuracy over using raw features alone.
  • For a perfect model (f00), hypothesis testing with a preference bias allowed the system to achieve 100% accuracy with fewer training examples (80-85) compared to standard C4.5, especially with less strict significance levels (e.g., 50%).
  • With imperfect models (e.g., f1010), stricter significance levels (lower percentages) consistently improved accuracy and biased the decision trees towards using features closer to the model prediction (lower level numbers).
  • The study found a "breakeven point" for significance levels, after which stricter levels could become detrimental for larger, more representative training sets.

Limitations and Future Work

  • Computational Cost: The bootstrap-based significance testing is computationally expensive, although the authors note that it's often not needed for many feature selections.
  • Bias of Information Gain Ratio: The paper acknowledges that the information gain ratio metric can be biased against features with many values (like the model prediction feature), and while significance testing helps mitigate this, it's an inherent challenge.
  • Future Work: The authors suggest exploring more sophisticated ways to determine the optimal significance level and investigating how to automatically infer the quality of a domain theory to guide this process. They also hint at further research into how to revise the model itself when strong evidence contradicts it.

Summary updated

BibTeX
@inproceedings{1995flexibly,
  title = {{Flexibly Exploiting Prior Knowledge in Empirical Learning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1995},
}
Figure