New design goal of a classifier: Global and local structural risk minimization

摘要

Structural risk consists of empirical risk (training error) and Vapnik–Chemonenkis (VC) dimension (complexity). Since minimizing empirical risk makes a classifier have a high classification accuracy on label-known patterns while minimizing complexity makes it have a low prediction error on label-unknown patterns, thus structural risk can be used to measure the effectiveness of a classifier and Structural Risk Minimization (SRM) becomes its design goal. Moreover, since a global space can be divided into several local ones, thus from the view of global space, the structural risk is named global structural risk while the one from the view of local space is named local structural risk. Traditional classifiers are designed based on global or local structural risk and their designs do not take both of them into account simultaneously. So this paper proposes a new design goal of a classifier with both global and local structural risks. Furthermore, a locality-sensitive term is introduced so as to measure the relationship between global structural risk and the local one. The new design goal is named Global and Local Structural Risk Minimization (GLSRM). Contribution of GLSRM is that it makes a classifier have a lower training error on label-known patterns and a lower prediction error on label-unknown ones in both global space and local spaces. Innovation of GLSRM is that it introduces a locality-sensitive term so as to reflect the relationship between global structural risk and the local one and then combines global structural risk, local structural risk, and their relationship together in the procedure of classifier design. Experiments on some real-world data sets show feasibility and effectiveness of GLSRM.