OASIS: An Active Framework for Set Inversion

Binh T. Nguyen, Duy M. H. Nguyen, Lam Si Tung Ho, Vu C. DinhSoMeT 2018 · DOI · OpenReview

TL;DR

The paper introduces OASIS, a novel active learning framework that solves the mathematical problem of "set inversion" by reframing it as a binary classification task using Support Vector Machines (SVMs). By aggressively sampling data points near the decision boundary, OASIS overcomes the curse of dimensionality that plagues traditional interval analysis methods, successfully scaling to 8-dimensional problems where state-of-the-art algorithms run out of memory.

What Problem Does This Paper Address?

The paper tackles the problem of set inversion. In mathematics and engineering, if you have a complex system defined by a function $F$ and a specific target state $U$, set inversion is the process of finding all the initial inputs (the "pre-image") that will result in that target state. This is highly relevant for finding stability domains in dynamical systems, fault detection, and robotic localization.

Conceptual mapping of the set inversion problem, showing the relationship between the input space $\Omega$ and the target set $U$.

Traditionally, this is solved using "interval analysis" algorithms like SIVIA (Set Inverter Via Interval Analysis). SIVIA works by dividing the input space into smaller and smaller boxes to approximate the boundaries of the solution. However, this approach suffers heavily from the curse of dimensionality: as the number of variables (dimensions) increases, the number of boxes required grows exponentially. Consequently, traditional methods become computationally paralyzed or run out of memory when dealing with anything beyond 3 or 4 dimensions.

Methods

The authors propose OASIS (Optimization-based Active learning for Set Inversion with Support vector machine). Instead of geometry and boxes, OASIS treats set inversion as a machine learning classification problem:

  1. Binary Labels: A point in the input space is labeled $1$ if it maps into the target set, and $-1$ if it does not.
  2. SVM Classifier: An SVM with a Gaussian Radial Basis Function (GRBF) kernel is used to learn the complex, non-linear boundary separating the classes.
  3. Active Learning: Evaluating the system function $F$ can be computationally expensive, so OASIS minimizes the number of samples needed. It generates a random point, then uses Sequential Quadratic Programming to find the closest point exactly on the current SVM decision boundary (where the model is most uncertain). It samples that specific point, gets the true label, and updates the SVM.

Because the labels in this mathematical context are absolute (no noise), OASIS can use a highly aggressive sampling strategy without worrying about the exploration-exploitation trade-offs usually required in noisy ML environments.

Key Results

OASIS was evaluated against synthetic mathematical functions and real-world physics models, demonstrating superior scalability and accuracy.

  • Accuracy: On 2D shapes, OASIS achieved an average accuracy of 99.35%, slightly outperforming the vectorized state-of-the-art VSIVIA algorithm (98.43%).
  • High-Dimensional Scaling: VSIVIA completely failed (ran out of memory) on problems larger than 4 dimensions. OASIS successfully solved up to 8D spheres, maintaining an accuracy of 99.98%.
  • Speed: While training takes longer (2–4 minutes vs 0.4 seconds for VSIVIA), OASIS's prediction time per point was ~0.008 milliseconds, significantly faster than traditional methods.
Visual comparison of set reconstruction for Circle, Ring, and Doughnut shapes across Ground Truth, OASIS, and VSIVIA.

Key Insights and Ideas

  • Classification Bypasses the Dimensionality Curse: By learning a mathematical boundary (the SVM hyperplane) rather than physically partitioning the space into boxes, the algorithm scales far more gracefully into higher dimensions.
  • Asymmetric Compute Costs: OASIS shifts the computational burden to the training phase. Once trained, predicting whether a new point is in the set is practically instantaneous. This is ideal for engineering workflows where models are trained offline but deployed for real-time inference.
  • Practical Application: OASIS successfully recovered the parameter space for the Lotka-Volterra predator-prey model with 99.56% accuracy using only 800 sampled points.

Limitations and Future Work

The primary drawback of OASIS is its training time, as the SVM must be recalibrated sequentially as new active samples are chosen. However, the authors highlight that OASIS is perfectly suited for embedded systems and control theory. Because the heavy lifting is done offline, the resulting SVM classifier can be embedded into edge devices with limited memory to make lightning-fast, real-time decisions.

Summary updated

Abstract

In this work, we introduce a novel method for solving the set inversion problem by formulating it as a binary classification problem. Aiming to develop a fast algorithm that can work effectively with high-dimensional and computationally expensive nonlinear models, we focus on active learning, a family of new and powerful techniques which can achieve the same level of accuracy with fewer data points compared to traditional learning methods. Specifically, we propose OASIS, an active learning framework using Support Vector Machine algorithms for solving the problem of set inversion. Our method works well in high dimensions and its computational cost is relatively robust to the increase of dimension. We illustrate the performance of OASIS by several simulation studies and show that our algorithm outperforms VISIA, the state-of-the-art method.
BibTeX
@inproceedings{nguyen2018oasis,
  author = {Binh T. Nguyen and Duy M. H. Nguyen and Lam Si Tung Ho and Vu C. Dinh},
  title = {{OASIS: An Active Framework for Set Inversion}},
  booktitle = {SoMeT},
  year = {2018},
  doi = {10.3233/978-1-61499-900-3-883},
}
Figure