L'algorithme de validation croisee a K blocs (K-fold cross-validation) est la base necessaire, pour estimer l'erreur de generalisation d'un algorithme A sur un ensemble de donnees D. definition de KfoldXV(A,D,K,L): Intrants: Algorithme d'apprentissage A: donnees --> fonction D = un ensemble de donnees K = nombre de blocs a l'interieur de D pour faire la validation croisee L = fonctionnelle de perte: (f,z) ---> scalaire, prend une fonction et un exemple et retourne la perte. Sortie: err = vecteur de longueur |D| dont les elements sont les erreurs de test sur les elements de D obtenues en appliquant A sur un sous-ensemble de D et en le testant sur cet element. On peut obtenir un estimateur de l'erreur de generalisation en faisant la moyenne des elements de err. Algorithme: - construire D_i, i=1 a K, K sous-ensembles disjoints de D, environ de meme taille, tels que leur union=D. - pour i=1 a K f_i = A(D \ D_i) pour j les indices dans D des elements de D_i err[j] = L(f_i,z_j), avec z_j le j-ieme element de D (et un element de D_i) - retourner err Algorithme de double validation croisee (pour faire la selection de modele ET l'evaluation des modeles): definition de DoubleKFoldXV((A_1,...A_N),D,K,L): Intrants: N algorithmes d'apprentissage A_i: donnees --> fonction, i=1 a N D = ensemble de donnees K = nombre de blocs a l'interieur de D pour faire la validation croisee L = fonctionnelle de perte: (f,z) ---> scalaire, prend une fonction et un exemple et retourne la perte. Sortie: err = vecteur de longueur |D| dont les elements sont les erreurs de test sur les elements de D obtenues en choisissant un des A_i et en le testant sur cet element. On peut obtenir un estimateur de l'erreur de generalisation en faisant la moyenne des elements de err. Algorithme: - Definir le meta-algorithme A_sel: donnees D' --> fonction f_k, ainsi: - pour i=1 a N - e_i = moyenne(KfoldXV(A_i,D',K-1,L)) [moyenne() retourne la moyenne des elements dans son argument] - retourner A_{argmin_k e_k}(D') [la fonction entrainee par l'algo qui semble le mieux marcher] - err = KfoldXV(A_sel, D, K, L) On peut faire le meme genre de chose en validation sequentielle (donnees ordonnees dans le temps), MAIS CA REVIENT MOINS CHER EN TEMPS DE CALCUL. D'abord definissons la validation sequentielle. definition de ValSeq(A, D, K, L, T): Intrants: Algorithme d'apprentissage A: donnees --> fonction D = un ensemble de donnees K = nombre de blocs a l'interieur de D pour faire la validation sequentielle L = fonctionnelle de perte: (f,z) ---> scalaire, prend une fonction et un exemple et retourne la perte. T = taille de l'ensemble d'apprentissage de depart Sortie: err = vecteur de longueur |D|-T dont les elements sont les erreurs de test sur les derniers elements de D obtenues en appliquant A sur une sous-sequence de D (commencant a 0) et en le testant sur cet element. On peut obtenir un estimateur de l'erreur de generalisation en faisant la moyenne des elements de err. Algorithme: - delta = (|D| - T)/K = taille des blocs - pour i=1 a K - train_set <-- T+(i-1)*delta premiers elements de D - D_i <-- delta elements de D qui suivent train_set - f = A(train_set) - pour j les indices dans D des elements de test_set err[j-T] = L(f,z_j), avec z_j le j-ieme element de D (et un element de D_i) - retourner err Validation sequentielle avec selection de modele: definition de ValSeqSelMod((A_1,...A_N), D, K, L, T): Intrants: N algorithmes d'apprentissage A_i: donnees --> fonction, i=1 a N D = un ensemble de donnees K = nombre de blocs a l'interieur de D pour faire la validation sequentielle L = fonctionnelle de perte: (f,z) ---> scalaire, prend une fonction et un exemple et retourne la perte. T = taille de l'ensemble d'apprentissage de depart Sortie: err = vecteur de longueur |D|-T-(|D|-T)/K dont les elements sont les erreurs de test sur les derniers elements de D obtenues en appliquant A sur une sous-sequence de D (commencant a 0) et en le testant sur cet element. On peut obtenir un estimateur de l'erreur de generalisation en faisant la moyenne des elements de err. Algorithme: - delta = (|D| - T)/K = taille des blocs - modele_choisi = 0 - pour i=1 a K - train_set <-- T+(i-1)*delta premiers elements de D - D_i <-- delta elements de D qui suivent train_set - si modele_choisi>0 - f_i = A_{modele_choisi}(train_set) - pour j les indices dans D des elements de test_set err[j-T-delta] = L(f_i,z_j), avec z_j le j-ieme element de D (et un element de D_i) - pour k=1 a N - f = A_k(train_set) - pour j les indices dans D des elements de test_set errmodele[k][j-T] = L(f,z_j), avec z_j le j-ieme element de D (et un element de D_i) - modele_choisi = argmin_k moyenne(errmodele[k]) // en faisant la moyenne sur les i*delta premiers elements - retourner err