Exact Cross-Validation for $k$NN : application to passive and active learning in classification

[Validation-croisée exacte pour les $k$NN : application à l’apprentissage passif et actif en classification]

Celisse, Alain  ; Mary-Huard, Tristan

Journal de la société française de statistique, Tome 152 (2011) no. 3, pp. 83-97

Abstract (VO)

In the binary classification framework, a closed form expression of the cross-validation Leave-$p$-Out (L$p$O) risk estimator for the $k$ Nearest Neighbor algorithm ($k$NN) is derived. It is first used to study the L$p$O risk minimization strategy for choosing $k$ in the passive learning setting. The impact of $p$ on the choice of $k$ and the L$p$O estimation of the risk are inferred. In the active learning setting, a procedure is proposed that selects new examples using a L$p$O committee of $k$NN 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 L$p$O is shown to be different from what is observed in passive learning.

Résumé

Pour l’algorithme de classification des $k$ plus proches voisins ($k$NN), une expression explicite de l’estimateur du taux d’erreur de classification par validation croisée Leave $p$ Out (L$p$O) est proposée. Cette expression explicite est d’abord utilisée dans le cadre de l’apprentissage passif pour étudier l’impact du choix du paramètre $p$ du L$p$O sur le choix de $k$ dans l’algorithme $k$NN. On s’intéresse ensuite au problème de l’apprentissage actif (active learning). Une procédure de sélection des exemples basée sur la recommandation du comité des classificateurs L$p$O est considérée. L’influence du paramètre $p$ sur le choix des nouveaux exemples et sur le choix du paramètre $k$ à chaque étape de l’apprentissage actif est étudiée. En particulier, il est montré que l’évolution de la valeur du paramètre $k$ choisie par L$p$O en apprentissage actif est différente de celle observée en apprentissage passif.

Détail

Keywords: Classification, Cross-validation, $k$NN algorithm Active learning
Mots-clés : Classification, Valildation-croisée, $k$NN, Apprentissage actif