Adjacent Inputs With Different Labels and Hardness in Supervised Learning
Sebastián Alberto Grillo, Julio César Mello-Román, Jorge Daniel Mello-Román, José Luis Vázquez Noguera, Miguel García-Torres, Federico Divina, Pedro Esteban Gardel Sotomayor · IEEE Access · 2021
An important aspect of the design of effective machine learning algorithms is the complexity analysis of classification problems. In this paper, we proposed a study aimed at determining the relation between the number of adjacent inputs with different labels and the required number of examples for the task of inducing a classification model. To this aim, we quantified the adjacent inputs with different labels as a property, using a measure denoted as Neighbour Input Variation (NIV). Then, we studied the relation of NIV to random data and overfitting. Second, we demonstrated that a threshold of NIV may determine if a classification model can generalize to unseen data. Third, we presented a case study analyzing threshold neural networks and the required first hidden layer size in function of NIV. Finally, we performed experiments with 5 popular algorithms analyzing the relation between NIV and the classification error on problems with few dimensions. We conclude that functions whose similar inputs have different outputs with high probability, considerably reduce the generalization capacity of classification algorithms.