A local Vapnik–Chervonenkis complexity. (October 2016)

• Record Type: Journal Article
• Authors: Oneto, Luca; Anguita, Davide; Ridella, Sandro
• Is Part Of: Neural networks. Volume 82(2016)
• Page Start: 62
• Page End: 75
• Publication Date: 2016-10
• Subjects: Local Rademacher Complexity -- Local Vapnik–Chervonenkis entropy -- Generalization error bounds -- Statistical Learning Theory -- Complexity measures; Neural computers -- Periodicals; Neural networks (Computer science) -- Periodicals; Neural networks (Neurobiology) -- Periodicals; Nervous System -- Periodicals; Ordinateurs neuronaux -- Périodiques; Réseaux neuronaux (Informatique) -- Périodiques; Réseaux neuronaux (Neurobiologie) -- Périodiques; Neural computers; Neural networks (Computer science); Neural networks (Neurobiology); Periodicals; 006.32
• DOI: 10.1016/j.neunet.2016.07.002
• Languages: English
• ISSNs: 0893-6080

Abstract

Abstract: We define in this work a new localized version of a Vapnik–Chervonenkis (VC) complexity, namely the Local VC-Entropy, and, building on this new complexity, we derive a new generalization bound for binary classifiers. The Local VC-Entropy-based bound improves on the original Vapnik's results because it is able to discard those functions that, most likely, will not be selected during the learning phase. The result is achieved by applying the localization principle to the original global complexity measure, in the same spirit of the Local Rademacher Complexity. By exploiting and improving a recently developed geometrical framework, we show that it is also possible to relate the Local VC-Entropy to the Local Rademacher Complexity by finding an admissible range for one given the other. In addition, the Local VC-Entropy allows one to reduce the computational requirements that arise when dealing with the Local Rademacher Complexity in binary classification problems.