Abstract
In the era of "Big Data," training complex models like Support Vector Machines (SVMs) on massive datasets is computationally prohibitive. Instance selection aims to identify a representative subset of data to maintain accuracy while reducing overhead. This paper introduces BDIS (Bayesian Decision-based Instance Selection), a novel framework that leverages Bayesian decision theory and percolation theory to prune datasets. By categorizing instances as deleterious, irreducible, or reducible based on local cluster sizes, BDIS achieves extreme scalability, processing up to 60 million instances where traditional $k$-NN-based methods fail.
Introduction
The proliferation of large-scale datasets has outpaced the computational efficiency of many traditional machine learning algorithms. For instance, training an SVM on millions of samples requires significant memory and time. Instance selection techniques attempt to mitigate this by selecting a subset of the original data. However, existing methods often rely on heuristic $k$-Nearest Neighbor ($k$-NN) rules that lack a rigorous mathematical foundation and suffer from poor scalability due to $O(n^2)$ similarity matrix calculations.
Methodology
The authors propose BDIS to bridge the gap between theoretical rigor and practical scalability. The method operates on three core pillars:
1. The Bayesian Framework
BDIS categorizes every data point into three functional types based on their posterior probabilities relative to the Bayes decision boundary:
- Deleterious: Noisy or mislabeled points that negatively impact model performance.
- Irreducible: Critical points located near the decision boundary that are essential for defining class separation.
- Reducible: Redundant points located deep within class clusters that do not provide additional information about the boundary.
2. Percolation Theory and Local Homogeneous Clusters (LHCs)
To avoid the high cost of calculating exact posterior probabilities, BDIS utilizes Local Homogeneous Clusters (LHCs)—groups of adjacent points sharing the same label. Drawing from percolation theory, the authors prove that the size of an LHC is proportional to the probability that its constituent points belong to that class. This allows for efficient filtering: very small clusters are identified as deleterious noise, while massive clusters are flagged as reducible redundancy.
3. Accelerated Clustering
To maintain linear space complexity ($O(n)$), BDIS employs an iterative, accelerated $k$-means algorithm powered by the FAISS library. This approach bypasses the exhaustive neighbor searches that bottleneck traditional instance selection methods.
Experimental Evaluation
The performance of BDIS was evaluated using both synthetic and real-world benchmark datasets:
- Synthetic Data: "Circles" and "Moons" distributions were scaled up to 60 million instances to test the limits of scalability.
- UCI Benchmarks: 12 datasets, including Letter Recognition, Shuttle, and Skin Segmentation, with sizes ranging from 5,000 to 245,000 instances.
Key Results and Discussion
BDIS demonstrates significant improvements in both efficiency and pruning quality over state-of-the-art methods.
Extreme Scalability and Efficiency
On the 60-million-point synthetic dataset, BDIS completed the selection and training process in approximately one hour, whereas competing methods like RIS and EGDIS failed due to memory constraints. In the "Shuttle" dataset experiment, BDIS reduced SVM training time from over 500 seconds to just 0.001 seconds without any loss in classification accuracy (0.837).
Superior Pruning Quality
Visual analysis and quantitative metrics show that BDIS effectively preserves the decision boundary while removing noise and redundancy.
The algorithm utilizes two thresholds, $\tau_1$ and $\tau_2$, to define a "Goldilocks zone." By discarding the smallest clusters (noise) and heavily compressing the largest (redundancy), BDIS focuses the model's learning on the most informative instances near the boundary.
Limitations and Future Work
While BDIS offers a robust theoretical framework, it remains sensitive to the parameters $k_1$ and $k_2$ used to determine the $\tau$ thresholds. Although empirical defaults ($k_1=0, k_2=7$) perform well generally, specific tuning may be required for highly imbalanced or irregular distributions. Additionally, the method's performance is tied to the efficiency of the underlying clustering; extremely high-dimensional data may still challenge the initial LHC construction. Future research could extend this Bayesian perspective to active learning and outlier detection.
Summary updated