On Model Complexity Reduction in Instance-Based Learners

  • Saulo A. F. Oliveira UFC
  • Ajalmar R. Rocha Neto IFCE
  • João P. P. Gomes UFC


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.


D. AHA, D. KIBLER, and M. ALBERT, "Instance-Based Learning Algorithms," MACHINE LEARNING, vol. 6, no. 1, pp. 37-66, JAN 1991.

P. Norvig and S. Russell, Inteligência Artificial: Tradução da 3a Edição. Elsevier Brasil, 2017. [Online]. Available: https://books.google.com.br/books?id=BsNeAwAAQBAJ

D. MACKAY, "Bayesian Interpolation," Neural Computation, vol. 4, no. 3, pp. 415-447, MAY 1992.

S. A. F. Oliveira, J. P. P. Gomes, and A. R. Rocha Neto, "Sparse Least-Squares Support Vector Machines via Accelerated Segmented Test: A dual approach," NEUROCOMPUTING, vol. 321, pp. 308-320, DEC 10 2018.

J. A. Florencio, V, S. A. F. Oliveira, J. P. P. Gomes, and A. R. Rocha Neto, "A new perspective for Minimal Learning Machines: A lightweight approach," NEUROCOMPUTING, vol. 401, pp. 308-319, AUG 11 2020.

E. Rosten and T. Drummond, "Machine learning for high-speed corner detection," in COMPUTER VISION - ECCV 2006 , PT 1, PROCEEDINGS, ser. LECTURE NOTES IN COMPUTER SCIENCE, Leonardis, A and Bischof, H and Pinz, A, Ed., vol. 3951, no. 1. Graz, Austria: Adv Comp Vis; Graz Univ Technol; Univ Ljubljana, 2006, pp. 430-443.

J. Demšar, "Statistical comparisons of classifiers over multiple data sets," JOURNAL OF MACHINE LEARNING RESEARCH, vol. 7, pp. 1-30, JAN 2006.

A. H. de Souza Junior, F. Corona, G. A. Barreto, Y. Miche, and A. Lendasse, "Minimal Learning Machine: A novel supervised distancebased approach for regression and classification," NEUROCOMPUTING, vol. 164, pp. 34-44, SEP 21 2015, 12th International Work-Conference on Artificial Neural Networks (IWANN), Puerto de la Cruz, SPAIN, JUN 12-14, 2013.

E. Niewiadomska-Szynkiewicz and M. Marks, "Optimization schemes for wireless sensor network localization," IntINTERNATIONAL JOURNAL OF APPLIED MATHEMATICS AND COMPUTER SCIENCE, vol. 19, no. 2, pp. 291-302, Jun. 2009. [Online]. Available: https://doi.org/10.2478/v10006-009-0025-3

A. S. C. Alencar, W. L. Caldas, J. P. P. Gomes, A. H. de Souza Junior, P. A. C. Aguilar, C. Rodrigues, W. Franco, M. F. de Castro, and R. M. C. Andrade, "MLM-Rank: A Ranking algorithm based on the Minimal Learning Machine," in 2015 BRAZILIAN CONFERENCE ON INTELLIGENT SYSTEMS (BRACIS 2015). Rio Grande do Norte: Soc Brasileira Comp SBC; Univ Federal do Rio Grande do Norte, 2015, pp. 305-309, 4th Brazilian Conference on Intelligent Systems (BRACIS), Natal, BRAZIL, NOV 04-07, 2015.

S. A. F. Oliveira, S. S. A. Alves, J. P. P. Gomes, and A. R. Rocha Neto, "A bi-directional evaluation-based approach for image retargeting quality assessment," COMPUTER VISION AND IMAGE UNDERSTANDING, vol. 168, no. SI, pp. 172-181, MAR 2018.

D. P. P. Mesquita, J. P. P. Gomes, L. R. Rodrigues, S. A. F. Oliveira, and R. K. H. Galvao, "Building selective ensembles of randomization based neural networks with the successive projections algorithm," APPLIED SOFT COMPUTING, vol. 70, pp. 1135-1145, SEP 2018.

E. d. S. Reboucas, R. C. P. Marques, A. M. Braga, S. A. F. Oliveira, V. H. C. de Albuquerque, and P. P. Reboucas Filho, "New level set approach based on parzen estimation for stroke segmentation in skull ct images," SOFT COMPUTING, vol. 23, no. 19, SI, pp. 9265-9286, OCT 2019.
OLIVEIRA, Saulo A. F.; ROCHA NETO, Ajalmar R.; GOMES, João P. P.. On Model Complexity Reduction in Instance-Based Learners. In: WORKSHOP DE TESES E DISSERTAÇÕES - CONFERENCE ON GRAPHICS, PATTERNS AND IMAGES (SIBGRAPI), 35. , 2022, Natal/RN. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2022 . p. 1-6. DOI: https://doi.org/10.5753/sibgrapi.est.2022.23253.