Classifier learning with a new locality regularization method

Abstract: It is well known that the generalization capability is one of the most important criterions to develop and evaluate a classifier for a given pattern classification problem. The localized generalization error model (RSM) [2, 12] recently proposed by Ng et al. provides a more intuitive look at the generalization error. Although RSM gives a brand-new method to promote the generalization performance, it is in nature equivalent to another type of regularization. In this paper, we first prove the essential relationship between RSM and regularization, and demonstrate that the stochastic sensitivity measure in RSM exactly corresponds to a regularizing term. Then, we develop a new generalization error bound from the regulation viewpoint, which is inspired by the proved relationship between RSM and regularization. Moreover, we derive a new regularization method, called as locality regularization (LR), from the bound. Different from the existing regularization methods which artificially and externally append the regularizing term in order to smooth the solution, LR is naturally and internally deduced from the defined expected risk functional and calculated by employing locality information. Through combining with spectral graph theory, LR introduces the local structure information of the samples into the regularizing term and further improves the generalization capability. In contrast with RSM, which is relativel