Instance Selection: A Bayesian Decision Theory Perspective

Qingqiang Chen, Fuyuan Cao, Ying Xing, Jiye Liang

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.
Conceptual framework of BDIS: categorizing instances into reducible, irreducible, and deleterious sets based on Bayesian decision theory.

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.

Visual comparison of BDIS against other instance selection methods (EGDIS, RIS, RS) on synthetic datasets.

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

Abstract

In this paper, we consider the problem of lacking theoretical foundation and low execution efficiency of the instance selection methods based on the k-nearest neighbour rule when processing large-scale data. We point out that the core idea of these methods can be explained from the perspective of Bayesian decision theory, that is, to find which instances are reducible, irreducible, and deleterious. Then, based on the percolation theory, we establish the relationship between these three types of instances and local homogeneous cluster (i.e., a set of instances with the same labels). Finally, we propose a method based on an accelerated k-means algorithm to construct local homogeneous clusters and remove the superfluous instances. The performance of our method is studied on extensive synthetic and benchmark data sets. Our proposed method can handle large-scale data more effectively than the state-of-the-art instance selection methods. All code and data results are available at https://github.com/CQQXY161120/Instance-Selection.
BibTeX
@inproceedings{chen2022instance,
  author = {Qingqiang Chen and Fuyuan Cao and Ying Xing and Jiye Liang},
  title = {{Instance Selection: A Bayesian Decision Theory Perspective}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i6.20578},
}
Figure