A Simple and Effective Method for Incorporating Advice into Kernel Methods

Richard Maclin, Jude W. Shavlik, Trevor Walker, Lisa TorreyAAAI 2006

Abstract

This paper introduces a streamlined methodology for injecting human "advice"—expressed as IF-THEN rules—into Support Vector Machines (SVM) and Kernel Regression. By transitioning from complex symbolic constraints to an "extensional" approach, where advice is enforced on specific data points rather than the entire input space, the authors developed a method that is easier to implement, significantly faster to solve, and capable of leveraging unlabeled data to enhance learning performance.

Introduction

Standard machine learning typically relies on labeled input-output pairs. However, in many domains, human experts possess prior knowledge or "advice" that could accelerate learning, particularly when data is scarce. Previous attempts to integrate such knowledge, such as Knowledge-Based Support Vector Machines (KBSVM), utilized an "intensional" approach. This involved translating human rules into complex mathematical constraints applying to entire regions of the input space. While theoretically sound, this approach suffered from high implementation complexity (requiring transformations like Motzkin’s Theorem), computational inefficiency due to auxiliary variables, and difficulties in maintaining advice fidelity during kernelization.

The Extensional Approach

The authors propose ExtenKBKR (for regression) and ExtenKBSVM (for classification). The fundamental shift is treating advice "extensionally." Instead of mathematically constraining a continuous region of space, the algorithm identifies a set of points ($M_i$) that satisfy the "IF" condition of a rule. It then adds simple constraints to the optimization problem to ensure the model’s prediction for these specific points aligns with the "THEN" part of the rule.

Figure 1: Comparison of standard SVM (a), intensional KBSVM (b), and the proposed extensional ExtenKBSVM (c, d).

Key Innovations: * Point-Based Constraints: Constraints are applied only to training points where the rule applies. * Unlabeled Data Integration: If training data is sparse in the advice region, the method can utilize unlabeled "pseudo-examples" to anchor the advice. This allows the model to learn from advice even in areas where it has no labeled data. * Robustness via Slack Variables: The inclusion of "slack" variables allows the model to penalize and potentially ignore advice that contradicts actual data, ensuring robustness against imperfect human input.

Experimental Evaluation

The method was evaluated on two distinct tasks:

  1. Synthetic Dataset: A 10-feature environment with both linear and non-linear functions, supplemented by six rules of varying types (absolute and preference-based).
  2. RoboCup Soccer (BreakAway): A reinforcement learning task where agents learn strategies for moving, passing, and shooting based on human-provided strategic advice.

Results and Analysis

The extensional approach demonstrated significant improvements in both efficiency and accuracy. In the RoboCup experiments, ExtenKBKR required approximately half the CPU time of the older KBKR method. Furthermore, on synthetic tasks, the extensional method significantly outperformed standard Support Vector Regression (SVR) and older knowledge-based methods when training sets were small (e.g., 20–100 examples).

Figure 2: Performance metrics showing Average Absolute Error and Time Taken versus Training Set Size.

Key Insights: * Sampling over Symbolism: Sampling the input space (extensional) proves more practical than defining it perfectly with equations (intensional), bypassing complex logic-to-math translations. * Advice as Semi-Supervised Learning: Using unlabeled points to anchor advice effectively turns advice-taking into a form of semi-supervised learning, which is particularly beneficial in "cold start" scenarios where data is limited but expert knowledge is available.

Conclusion

The proposed extensional method offers a computationally efficient and implementation-friendly alternative to traditional knowledge-based kernel methods. While the method currently relies on the ability to test if data points match rule preconditions, it opens new avenues for incorporating human intuition into complex learning tasks like Reinforcement Learning. Future work will explore scaling to larger sets of overlapping rules and handling more abstract forms of advice.

Summary updated

BibTeX
@inproceedings{maclin2006simple,
  author = {Richard Maclin and Jude W. Shavlik and Trevor Walker and Lisa Torrey},
  title = {{A Simple and Effective Method for Incorporating Advice into Kernel Methods}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}

Loading related content...

Figure