Exact Cross-Validation for kNN : application to passive and active learning in classification
vendredi 23 mars 2012, 9h45 - 11h00
In the binary classification framework, a closed form expression of the cross-validation Leave-p-Out (LpO)
risk estimator for the k Nearest Neighbor algorithm (kNN) is derived. It is first used to study the LpO risk minimization
strategy for choosing k in the passive learning setting. The impact of p on the choice of k and the LpO estimation of
the risk are inferred. In the active learning setting, a procedure is proposed that selects new examples using a LpO
committee of kNN classifiers. The influence of p on the choice of new examples and the tuning of k at each step is
investigated. The behavior of k chosen by LpO is shown to be different from what is observed in passive learning.