Active Sample Selection and Correction Propagation on a Gradually-Augmented Graph∗

When data have a complex manifold structure or the characteristics of data evolve over time, it is unrealistic to expect a graph-based semi-supervised learning method to achieve flawless classification given a small number of ini-tial annotations. To address this issue with minimal human interventions, we propose (i) a sample selection criterion used for active query of informative samples by minimizing the expected prediction error, and (ii) an efficient correction propagation method that propagates human correction on selected samples over a gradually-augmented graph to un-labeled samples without rebuilding the affinity graph. Ex-perimental results conducted on three real world dataset-s validate that our active sample selection and correction propagation algorithm quickly reaches high quality classi-fication results with minimal human interventions. 1