Exact Cross-Validation for kNN : application to passive and active learning in classification

vendredi 23 mars 2012, 9h45 - 11h00

Salle de réunion, espace Turing

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.