Évaluation des algorithmes de filtrage collaboratif |
 |
Évaluation des algorithmes de prédiction
Pour évaluer les algorithmes de filtrage collaboratif, nous utilisons généralement une technique statistique appelée « validation croisée » (cross-validation, en anglais).
Essentiellement, la validation croisée consiste à séparer les données disponibles en sous-ensembles. La première partie sert à faire la prédiction et la deuxième, à en valider l’algorithme.
En pratique, cela se passe comme suit :
– Nous choisissons aléatoirement un certain nombre d’individus, par exemple, la moitié de ceux-ci. Ces individus sont représentés par l’algorithme 
dans les calculs. Les autres individus constituent un ensemble « test ».
– Les individus de l’ensemble « test » sont alors pris un à un. Pour chaque individu 
, nous ne fournissons à l’algorithme qu’une partie des évaluations, par exemple, toutes les évaluations sauf une. Nous notons l’individu ainsi amputé de sa note sur l’article 
par 
.
– Nous mesurons ensuite l’erreur faite en prédisant la note accordée par l’individu à l’article (en valeur absolue) : 
.
– Si nous faisons la moyenne entre tous les utilisateurs de l’ensemble « test » et tous les articles qu’ils ont notés, nous obtenons alors une mesure appelée « All-But-1 Mean Average Error » (All-But-1 MAE).
Ainsi, si nous avons 10 utilisateurs dans notre ensemble test, ayant chacun notés 5 articles, la mesure All-But-1 sera la moyenne de 
prédictions. Il y a une prédiction à faire pour chaque note accordée par un utilisateur de l’ensemble test.
Nous pouvons mettre à l’essai un algorithme sur un ensemble de données, comme Netflix.
Exemple. Dans notre ensemble « test », nous avons deux utilisateurs : Pierre et Marie. Marie a accordé des notes de 4 et de 2 aux articles 1 et 2, alors que Pierre a donné des notes de 4 et de 5 aux articles 2 et 3. Symboliquement, inscrivons Pierre=(x,4,5) et Marie=(4,2,x) où les « x » représentent des notes manquantes. Notons 
la note prédite à l’article 2 pour un utilisateur ayant donné une note de 5 pour l’article 3. La note est prédite par l’utilisation d’un ensemble d’utilisateurs excluant Pierre et Marie. Pierre et Marie forment l’ensemble test. La mesure d’erreur All-But-1 est alors (
+
+
+
)/4. En somme, c’est l’erreur moyenne commise lors de la prédiction d’une note de Pierre ou de Marie. La prédiction d’une note de Marie ou de Pierre se fait toujours en connaissante toutes les notes de Marie ou de Pierre sauf une (d’où le terme « All-But-1 »).
Les activités d’autoévaluation vous permettront de vérifier votre compréhension de la mesure All-But-1.
Le lien entre les données et les algorithmes
Il est tentant de croire que les données accumulées ne dépendent pas de l’outil de recommandation utilisé, mais ce n’est pas le cas. Les données accumulées sur un site web, par exemple, reposent en grande partie sur la structure du site et les recommandations historiques qui y sont faites. En effet, lorsqu’un algorithme recommande un article impopulaire, il recevra rapidement de mauvaises notes, ce qui aura pour effet de corriger son comportement. Par opposition, si un article populaire est souvent recommandé, il recevra davantage d’évaluations, ce qui augmentera son poids dans l’algorithme utilisé.
En d’autres termes, les données et les utilisateurs sont influencés par les algorithmes utilisés, et c’est pourquoi il n’est pas simple de comparer les algorithmes.
Des alternatives ?
La mesure All-But-1 est basée sur la moyenne des erreurs. Dans le cadre de la compétition Netflix, les organisateurs ont préféré calculer la moyenne du carré de l’erreur. Cette dernière mesure tend à pénaliser davantage les algorithmes qui font parfois des erreurs importantes puisque la mise au carré amplifie la contribution des grandes erreurs.
La mesure All-But-1 MAE suffit-elle ?
La mesure All-But-1 MAE est très pratique dans la comparaison de plusieurs algorithmes. Si on vous demande quel est le « meilleur » algorithme, vous pouvez certainement vous servir de la mesure précitée dans votre réponse.
Cependant, la mesure All-But-1 MAE est incomplète pour plusieurs raisons :
– Le temps de calcul est parfois un facteur déterminant de l’algorithme qui s’avère beaucoup plus important que sa précision.
– Il est probable que si nous demandions à des utilisateurs de noter à nouveau les mêmes articles, leur réponse changerait. Comme leurs goûts et leurs opinions sont en constante évolution, une grande précision à leur égard n’est ni utile ni possible.
– Si votre système propose à des utilisateurs les 10 meilleurs articles, il importe peu de savoir si vous pouvez prédire adéquatement les notes que leur accorderaient les utilisateurs. Il importe beaucoup plus de savoir que les 10 notes les plus importantes qui ont été prédites correspondent bien à ce que les utilisateurs souhaitaient obtenir. Par ailleurs, il existe des solutions de rechange pour mesurer la qualité d’une recommandation Top N.
– Dans la pratique, il faut savoir tenir compte de la perception des utilisateurs. Même si vous pouviez lire dans leurs pensées, il n’est pas évident que le fait de leur faire dire ce qu’ils veulent vraiment mènera à un taux de satisfaction élevé. Par exemple, si un utilisateur est un admirateur de Céline Dion, et que votre système lui suggère 10 albums de la chanteuse, il est possible que l’utilisateur se fâche parce qu’il considérera que l’algorithme ne fait que lui montrer des produits qu’il connaît déjà.
