On model complexity reduction in instance-based learners

Abstract

Instance-based learners habitually adopt instance selection techniques to reduce complexity and avoiding 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 so they can perform predictions. Later, in this thesis, we formulate variants that constrain candidate solutions within a specific functional space where overfitting is avoided, and model complexity is reduced. In the Least-Squares Support Vector Machines context, this thesis follows the pruning fashion by adopting the Class-Corner Instance Selection. Such an approach focuses on describing the class-corner relationship among the samples on the dataset to penalize the ones close to the corners. As for the Minimal Learning Machine model, this thesis introduces a new proposal called the Lightweight Minimal Learning Machine. It adopts regularization in the complexity term to penalize each sample’s learning, resulting in a direct method. Usually, this penalization goes in alongside the term error. This thesis describes strategies based on random and observed linearity conditions related to the data for regression tasks. And, as for classification tasks, this thesis employs the before-mentioned class-corner idea to regularize them. Thus, resulting in the ones close to the corners suffering more penalization. By adopting such a methodology, we reduced the number of computations inherent in the original proposal’s multilateration process without requiring any instance selection criterion, yielding a faster model for out-of-sample prediction. Additionally, another remarkable feature is that it derives a unique solution when other formulations rely on overdetermined systems.