On Model Complexity Reduction in Instance-Based Learners

Saulo A.f. Oliveira, Ajalmar R. Rocha Neto, João P. P. Gomes2022 · DOI

Abstract

Instance-based learners habitually adopt instance selection techniques to reduce complexity and avoid overfitting. Such learners’ most recent and well-known formulations seek to impose some sparsity in their training and prediction structure alongside regularization to meet such a result. Due to the variety of such instance-based learners, we will draw attention to the Least-Squares Support Vector Machines and Minimal Learning Machines because they embody additional information beyond the stored instances to perform predictions. Later, this thesis proposes variants constraining candidate solutions within a specific functional space where we avoid overfitting and reduce model complexity. The central core of such variants is related to penalizing samples with a specific condition during learning. For regressors, we adopted strategies based on random and observed linearity conditions related to the data. At the same time, we borrowed definitions from the computer vision field for classification tasks to derive a concept we call the classcorner relationship (in which we designed an instance selection algorithm). In the Least-Squares Support Vector Machines context, this thesis follows the pruning fashion by adopting the samples that share such a class-corner relationship. As for the Minimal Learning Machine model, this thesis introduces a new proposal called the Lightweight Minimal Learning Machine, a faster model for out-of-sample prediction due to the reduced number of computations inherent in the original proposal’s multilateration process. Another remarkable feature is that it derives a unique solution when other formulations rely on overdetermined systems.

Introduction

Instance-based learners (IBLs) are intuitive models that make predictions by comparing new data to previously seen examples stored in memory. However, they face a fundamental "scaling wall": as datasets grow, the model's complexity increases linearly. This leads to two primary challenges: overfitting, where the model memorizes noise, and high computational costs during prediction. While sparsity and regularization are standard remedies, balancing model size with generalization performance remains difficult.

This research introduces novel methods to reduce the complexity of two prominent IBLs: Least-Squares Support Vector Machines (LSSVM) and Minimal Learning Machines (MLM). By adapting "corner detection" concepts from computer vision and introducing a "Lightweight" MLM framework, we demonstrate significant reductions in model size and prediction time without sacrificing accuracy.

Methodology

Class-Corner Instance Selection (CCIS)

Borrowing from the FAST algorithm used in computer vision for edge and corner detection, we developed Class-Corner Instance Selection (CCIS). This method identifies "corners" in high-dimensional data—points located in transition regions between different classes. By focusing on these structurally informative points, the model can ignore redundant data located in the centers of class clusters. This logic is applied to create the CC-LSSVM, which uses these identified corners as primary support vectors.

Lightweight Minimal Learning Machine (LW-MLM)

For the Minimal Learning Machine, we reformulated the cost function to include a regularization term that penalizes complex coefficient matrices. Furthermore, we introduced a method to discard a vast majority of "Reference Points" (RPs) during the prediction phase (multilateration). Because the model learns the global geometric structure, many points become redundant during inference, allowing for a drastic reduction in computational overhead.

Experimental Results

Visual Analysis of Decision Boundaries

Qualitative analysis on 2D toy datasets (Two Moon, Ripley, and Banana) demonstrates that the Class-Corner (CC) approach produces smoother, more robust decision boundaries compared to other pruning variants like FSA-LSSVM and SSD-LSSVM. These smoother boundaries indicate a better resistance to noise and outliers.

Figure 6: Qualitative comparison of decision boundaries across different pruning methods (CCP, FSA, SSD, and the proposed CC) on toy datasets.

Model Sparsity and Efficiency

Quantitatively, the proposed methods achieve significant sparsity. In LW-MLM experiments, the dataset used for out-of-sample prediction was reduced to just 5% of its original size while maintaining stable Root Mean Square Error (RMSE). As shown in the figure below, the number of selected support vectors (#SV) and pruned samples (#PS) is consistently a fraction of the total dataset size (#D) across various benchmarks.

Figure 1: Comparison of original dataset size (#D), pruned set size (#PS), and support vector count (#SV) across small/medium and large-scale datasets, shown in both normalized and actual scales.

CC-LSSVM consistently ranked highest in accuracy across toy problems. This suggests that the method does not merely seek the fewest points (maximum sparsity) but identifies the most informative points required for generalization.

Conclusion

This work demonstrates that model complexity in IBLs can be drastically reduced by focusing on the geometric structure of the data. The Class-Corner metaphor effectively identifies critical boundary points, while the Lightweight MLM framework enables faster predictions by discarding redundant reference points. Future work will explore Metric Learning to improve the effectiveness of corner detection in high-dimensional spaces where Euclidean distances may become less reliable.

Summary updated

Abstract

Instance-based learners habitually adopt instance selection techniques to reduce complexity and avoid overfitting. Such learners’ most recent and well-known formulations seek to impose some sparsity in their training and prediction structure alongside regularization to meet such a result. Due to the variety of such instance-based learners, we will draw attention to the Least-Squares Support Vector Machines and Minimal Learning Machines because they embody additional information beyond the stored instances to perform predictions. Later, this thesis proposes variants constraining candidate solutions within a specific functional space where we avoid overfitting and reduce model complexity. The central core of such variants is related to penalizing samples with a specific condition during learning. For regressors, we adopted strategies based on random and observed linearity conditions related to the data. At the same time, we borrowed definitions from the computer vision field for classification tasks to derive a concept we call the classcorner relationship (in which we designed an instance selection algorithm). In the Least-Squares Support Vector Machines context, this thesis follows the pruning fashion by adopting the samples that share such a class-corner relationship. As for the Minimal Learning Machine model, this thesis introduces a new proposal called the Lightweight Minimal Learning Machine, a faster model for out-of-sample prediction due to the reduced number of computations inherent in the original proposal’s multilateration process. Another remarkable feature is that it derives a unique solution when other formulations rely on overdetermined systems.
BibTeX
@misc{oliveira2022model,
  author = {Saulo A.F. Oliveira and Ajalmar R. Rocha Neto and João P. P. Gomes},
  title = {{On Model Complexity Reduction in Instance-Based Learners}},
  year = {2022},
  doi = {10.5753/sibgrapi.est.2022.23253},
}
Figure