Using Unsupervised Analysis to Constrain Generalization Bounds for Support Vector Classifiers

• Published in: IEEE transaction on neural networks and learning systems 2010-03, Vol.21 (3), p.424-438
• Main Authors: Decherchi, S., Ridella, S., Zunino, R., Gastaldo, P., Anguita, D.
• Format: Article
• Language: English
• Subjects: Algorithms; Applied sciences; Artificial Intelligence; Computer science; control theory; systems; Computer Simulation; Data analysis; Data processing. List processing. Character string processing; Error correction; Estimates; Exact sciences and technology; Generalization (Psychology); Humans; Inference from stochastic processes; time series analysis; Kernel; Learning; Machine learning; Mathematical models; Mathematics; Maximal discrepancy (MD); Memory organisation. Data processing; mixed unsupervised and supervised methods; Neural networks; Neural Networks (Computer); Pattern Recognition, Automated; Predictive models; Probability and statistics; Regularization; Reproducibility of Results; Sciences and techniques of general use; Semisupervised learning; Software; Statistics; Studies; support vector machine (SVM); Support vector machine classification; Support vector machines; Training data; Vector quantization; vector quantization (VQ)
• ISSN: 1045-9227; 2162-237X; 1941-0093; 2162-2388
• DOI: 10.1109/TNN.2009.2038695

A crucial issue in designing learning machines is to select the correct model parameters. When the number of available samples is small, theoretical sample-based generalization bounds can prove effective, provided that they are tight and track the validation error correctly. The maximal discrepancy (MD) approach is a very promising technique for model selection for support vector machines (SVM), and estimates a classifier's generalization performance by multiple training cycles on random labeled data. This paper presents a general method to compute the generalization bounds for SVMs, which is based on referring the SVM parameters to an unsupervised solution, and shows that such an approach yields tight bounds and attains effective model selection. When one estimates the generalization error, one uses an unsupervised reference to constrain the complexity of the learning machine, thereby possibly decreasing sharply the number of admissible hypothesis. Although the methodology has a general value, the method described in the paper adopts vector quantization (VQ) as a representation paradigm, and introduces a biased regularization approach in bound computation and learning. Experimental results validate the proposed method on complex real-world data sets.