Knowledge-Based Nonlinear Kernel Classifiers

Glenn Fung, Olvi L. Mangasarian, Jude W. ShavlikCOLT 2003 · DOI

TL;DR

This paper introduces a novel method for incorporating prior knowledge, in the form of polyhedral sets, into nonlinear kernel Support Vector Machines (SVMs). By reformulating the problem as a linear program, they enable the creation of highly accurate, sharp nonlinear classifiers that can be driven primarily or entirely by this prior knowledge, even with limited or no traditional training data.

What Problem Does This Paper Address?

Traditional Support Vector Machines (SVMs) are powerful tools for classification, but they primarily learn from data. While some work has explored incorporating prior knowledge into linear SVMs, extending this to nonlinear kernel SVMs has been challenging. The core difficulty lies in translating geometric constraints (polyhedral sets) into the high-dimensional feature spaces induced by nonlinear kernels without creating complex, non-convex optimization problems. This paper aims to bridge this gap, enabling the creation of more informed and potentially more robust nonlinear classifiers by effectively integrating expert knowledge.

Methods

The authors build upon previous work on linear SVMs and knowledge incorporation. Their key innovation is a clever reformulation that leverages theorems of the alternative for linear inequalities. Instead of directly kernelizing the implication of a knowledge set lying in a specific half-space, they transform it into a system of homogeneous linear inequalities. This system is then shown to be equivalent to a set of linear equality constraints involving the kernel function, the data representation, and the classifier parameters.

This leads to a linear programming (LP) formulation for the nonlinear kernel SVM. The standard LP formulation for a nonlinear kernel SVM is augmented with constraints derived from the prior knowledge sets. These constraints ensure that the polyhedral knowledge sets are correctly classified. To handle potential misclassifications or imperfect knowledge, the formulation also includes slack variables, similar to standard SVMs, which are minimized to drive the classifier towards satisfying the prior knowledge.

Datasets

The paper uses synthetic datasets for evaluation:

  • Exclusive-Or (XOR) Knowledge Sets: This classic problem is used to demonstrate how the knowledge-based classifier can generate sharp nonlinear boundaries. Two variations are presented: one where data points are symmetrically placed and another where they are not, highlighting the influence of knowledge sets.
  • Checkerboard Dataset: This benchmark, typically requiring 1000 points for a reasonable classification, is used to show the power of prior knowledge. The authors demonstrate that by using only 16 points (one from each square) and incorporating prior knowledge in the form of 8 linear inequalities for two specific subsquares, they achieve a significantly sharper and more accurate classifier (98.5% correctness) compared to a standard 16-point Gaussian kernel SVM (89.66% correctness).

Key Insights and Ideas

  • Bridging Geometry and High-Dimensional Kernels: The paper provides a principled way to translate geometric prior knowledge (polyhedra) into the abstract feature spaces of nonlinear kernels, a significant challenge previously.
  • Linear Programming for Nonlinearity: By cleverly reformulating the problem, the authors manage to solve a nonlinear classification problem using a linear programming framework, which is computationally efficient.
  • Knowledge-Driven Classification: The method allows for classifiers that are heavily or even entirely driven by prior knowledge, making it valuable in scenarios where labeled data is scarce but expert knowledge is abundant.
  • Sharp Classifiers from Limited Data: The checkerboard example vividly illustrates how incorporating prior knowledge can lead to much sharper and more accurate decision boundaries, even with a very small number of training points.

Key Results

  • The proposed knowledge-based nonlinear kernel SVM formulation can generate sharp nonlinear classifiers.
  • For the checkerboard problem, using only 16 points and prior knowledge about 2 out of 16 squares resulted in a classifier with 98.5% correctness on a large test set, significantly outperforming a standard 16-point Gaussian kernel SVM (89.66% correctness).
  • The formulation can be made entirely knowledge-based by using representative points from knowledge sets in place of traditional training data, which is useful when labeled data is unavailable.

Limitations and Future Work

  • Tuning Parameters: The paper mentions that the weights for the empirical error term and the knowledge incorporation (ν and μ) are chosen via a tuning set, which implies that some labeled data might still be beneficial for parameter selection.
  • Sampling Knowledge Sets: When no conventional datasets are available, the paper suggests using representative points from knowledge sets. The issues and best practices associated with sampling these knowledge sets are identified as an interesting topic for future research.
  • Future Applications: The authors plan to apply this framework to medical problems, computer vision, microarray gene classification, and drug efficacy studies, all areas where prior knowledge is often available.

Summary updated

BibTeX
@inproceedings{fung2003knowledge,
  author = {Glenn Fung and Olvi L. Mangasarian and Jude W. Shavlik},
  title = {{Knowledge-Based Nonlinear Kernel Classifiers}},
  booktitle = {Conference on Learning Theory},
  year = {2003},
  doi = {10.1007/978-3-540-45167-9\_9},
}

Loading related content...

Figure