1. Voting Margin: A Scheme for Error-Tolerant k Nearest Neighbors Classifiers for Machine Learning
- Author
-
Pedro Reviriego, Fabrizio Lombardi, José Alberto Hernández, Shanshan Liu, Comunidad de Madrid, and Ministerio de Economía y Competitividad (España)
- Subjects
Scheme (programming language) ,0209 industrial biotechnology ,Majority rule ,Computer science ,media_common.quotation_subject ,02 engineering and technology ,Machine learning ,computer.software_genre ,k-nearest neighbors algorithm ,020901 industrial engineering & automation ,Margin (machine learning) ,Voting ,Classifier (linguistics) ,0202 electrical engineering, electronic engineering, information engineering ,Computer Science (miscellaneous) ,Redundancy (engineering) ,K nearest neighbors ,computer.programming_language ,media_common ,Informática ,business.industry ,Modular design ,Computer Science Applications ,Human-Computer Interaction ,020201 artificial intelligence & image processing ,Artificial intelligence ,Error tolerance ,business ,computer ,Information Systems - Abstract
Machine learning (ML) techniques such as classifiers are used in many applications, some of which are related to safety or critical systems. In this case, correct processing is a strict requirement and thus ML algorithms (such as for classification) must be error tolerant. A naive approach to implement error tolerant classifiers is to resort to general protection techniques such as modular redundancy. However, modular redundancy incurs in large overheads in many metrics such as hardware utilization and power consumption that may not be acceptable in applications that run on embedded or battery powered systems. Another option is to exploit the algorithmic properties of the classifier to provide protection and error tolerance at a lower cost. This paper explores this approach for a widely used classifier, the k Nearest Neighbors ( k NNs), and proposes an efficient scheme to protect it against errors. The proposed technique is based on a time-based modular redundancy (TBMR) scheme. The proposed scheme exploits the intrinsic redundancy of k NNs to drastically reduce the number of re-computations needed to detect errors. This is achieved by noting that when voting among the k nearest neighbors has a large majority, an error in one of the voters cannot change the result, hence voting margin (VM). This observation has been refined and extended in the proposed VM scheme to also avoid re-computations in some cases in which the majority vote is tight. The VM scheme has been implemented and evaluated with publicly available data sets that cover a wide range of applications and settings. The results show that by exploiting the intrinsic redundancy of the classifier, the proposed scheme is able to reduce the cost compared to modular redundancy by more than 60 percent in all configurations evaluated. Pedro Reviriego and Josée Alberto Hernández would like to acknowledge the support of the TEXEO project TEC2016-80339-R funded by the Spanish Ministry of Economy and Competitivity and of the Madrid Community research project TAPIR-CM Grant no. P2018/TCS-4496.
- Published
- 2021