General Approximate Cross Validation for Model Selection: Supervised, Semi-supervised and Pairwise Learning

Cross-validation (CV) is a ubiquitous model-agnostic tool for assessing the error of machine learning. However, it has high complexity due to the requirement of multiple times of learner training especially in multimedia tasks with huge amounts of data. In this paper, we provide a unified framework to approximate the CV error for various common multimedia tasks such as supervised, semi-supervised and pairwise learning which requires training only once. Moreover, we study the theoretical performance of the proposed approximate CV and provide an explicit finite-sample error bound. Experimental results on several datasets demonstrate that our approximate CV has no statistical discrepancy from the original CV, but can significantly improve the efficiency, which is a great advantage in model selection.