Investigating Exploratory Capabilities of Uncertainty Sampling using SVMs in Active Learning

Dominik Lang, Daniel Kottke, Georg Krempl, Myra SpiliopoulouAL@iKNOW 2016 · OpenReview

TL;DR

This paper investigates whether uncertainty sampling, a common active learning strategy, can effectively explore data space when combined with Support Vector Machines (SVMs). The authors propose an evaluation framework to measure this exploratory capability and find that while SVMs can make uncertainty sampling appear exploratory in the kernel space, it doesn't replace the need for dedicated exploration strategies, especially when SVM hyperparameters are not optimally tuned.

What Problem Does This Paper Address?

Active learning aims to reduce the cost of data annotation by intelligently selecting the most informative unlabeled instances for an expert to label. A popular strategy is "uncertainty sampling" (US), which picks instances the current model is most unsure about, typically those near the decision boundary. This is often seen as "exploitation" – refining the existing decision boundary. However, some argue that US lacks "exploration" – discovering new, potentially important regions of the data space. This deficiency is thought to explain US's inferiority to purely exploratory methods like random sampling in some scenarios.

This paper questions whether combining US with Support Vector Machines (SVMs), particularly due to their use of the "kernel trick" to map data into a higher-dimensional space, might inherently provide exploration. The core problem is to determine if US, when paired with SVMs, can adequately cover the data space and if this coverage impacts classification performance.

Methods

The authors propose an evaluation framework to assess the exploratory capabilities of uncertainty sampling with SVMs. Their approach involves:

  • Uncertainty Sampling (US): They use the "simple margin" (sm) implementation, which selects instances closest to the SVM's decision boundary.
  • SVMs with Various Kernels: They experiment with polynomial, Radial Basis Function (RBF), Sigmoid, and Laplacian kernels.
  • Hyperparameter Tuning: For each kernel, they perform a grid search on a separate tuning set to find both the "best" performing parameter settings and "middle" (non-optimal) settings. This is crucial because SVM performance and behavior are highly sensitive to hyperparameters.
  • Exploration Metric: They introduce an "average minimum distance" score. This measures the average Euclidean distance from each test instance to its nearest labeled instance. A lower score indicates better coverage of the data space (higher exploration).
  • Comparison: They compare US with SVMs against a random sampling strategy using the same SVM configurations.
  • Evaluation: They track classification accuracy (hold-out accuracy on a test set) and the exploration score over the course of active learning (up to 50 label acquisitions).

Datasets

The paper uses a combination of synthetic and real-world datasets:

  • Synthetic Datasets:
    • Three Cluster Dataset: Designed to test if US can discover an unknown cluster.
  • 'Classification' Dataset: Provided by scikit-learn.
  • 'Quantiles' Dataset: Provided by scikit-learn.
  • 'Moons' Dataset: Provided by scikit-learn.
  • Gaussian 2D Datasets (presets 0, 1, 2): Used to investigate the influence of cluster separation and overlap.
  • Real-world Datasets:
    • 'Abalone'
    • 'Haberman'
    • 'Mammo'
    • 'Vertebral' These datasets are from the UCI Machine Learning Repository.

Key Insights and Ideas

  • Kernel Trick Illusion: While SVMs with kernels can map data into a space where US might appear to explore (by sampling instances that are far apart in the original feature space but close in the kernel space), this is not true exploration of the original data space. It's more about exploiting the structure of the kernel-induced space.
  • Hyperparameter Sensitivity: The choice of SVM hyperparameters significantly impacts both the performance and the perceived exploratory behavior of US. Non-optimal parameters can lead to US exhibiting more "exploratory" characteristics, but this is often a sign of the classifier failing to accurately fit the decision boundary rather than genuine data space exploration.
  • Exploration is Still Beneficial: The results consistently show that an initial phase of exploration (like random sampling) is beneficial for classification performance, especially in the early stages of active learning. US, even with SVMs, often lags behind random sampling initially.
  • No One-Size-Fits-All: The "best" SVM kernel and active learning strategy combination varies greatly across different datasets, highlighting the need for careful selection and tuning.

Key Results

  • Three Cluster Dataset: With "best" hyperparameters, RBF and Laplacian kernels with US reliably discover the unknown cluster (100% rate). Polynomial and Sigmoid kernels perform poorly (<25%). With "middle" (non-optimal) parameters, the discovery rate for RBF decreases, but Polynomial and Sigmoid SVMs show increased discovery rates (up to 50% and 80% respectively), suggesting a trade-off between exploration and accurate boundary fitting.
  • Synthetic Datasets: For 'Quantiles', 'Classification', and 'Moons' datasets, random sampling often outperforms US in the early stages, but US catches up or surpasses it later. The best SVM+AL combination varied, with Laplacian SVM + US winning on 'Classification' and 'Moons', and Polynomial SVM + US on 'Quantiles'.
  • Real-world Datasets: The winning kernel varied significantly: Laplacian for 'Abalone', Polynomial for 'Mammo', and RBF for 'Haberman' and 'Vertebral'. In several cases, random sampling outperformed US in the early learning stages.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that the "exploratory" behavior observed with non-optimal SVM parameters is more of a "misbehavior of the exploitation" rather than true data space exploration.
  • The study focuses on a specific type of uncertainty sampling (simple margin) and SVMs.
  • Future Work:
    • The authors suggest that hyperparameter tuning is critical and propose validating multiple hyperparameter settings in active learning evaluations to reduce bias.
  • The findings imply that dedicated exploratory components might still be necessary for robust active learning, even when using powerful classifiers like SVMs.

Summary updated

BibTeX
@inproceedings{lang2016investigating,
  author = {Dominik Lang and Daniel Kottke and Georg Krempl and Myra Spiliopoulou},
  title = {{Investigating Exploratory Capabilities of Uncertainty Sampling using SVMs in Active Learning}},
  booktitle = {AL@iKNOW},
  year = {2016},
  url = {https://openreview.net/forum?id=b5M2unVdF_},
}
Figure