Télécharger le fichier pdf d’un mémoire de fin d’études
Algorithmique pour l’agrégation de classements
De nombreux algorithmes existent pour répondre au problème de l’agrégation de classements. Ces algorithmes sont majoritairement conçus pour gérer les permutations mais certains peuvent parfois être adaptés pour une uti-lisation dans un spectre plus large. Nous verrons d’abord qu’une représentation des classements d’entrée par un graphe permet de faire le pont entre le problème d’agrégation de classements et un autre problème algorith-mique récurrent en théorie des graphes : le weighted feedback arc set problem. Nous présenterons ensuite des algorithmes exacts pour l’agrégation de permutations, puis nous ferons le point sur des techniques de réduction d’espace utiles pour réduire le temps nécessaire aux algorithmes exacts. Nous discuterons ensuite du lien étroit entre les techniques de réduction d’espace et deux particulièrement importants de la théorie du choix social. En-fin, nous présenterons certaines heuristiques dont l’intérêt reste entier lorsque, même couplés aux techniques de réduction d’espace, les algorithmes exacts ne permettent pas de calculer un classement consensuel en un temps raisonnable.
Représentation des permutations à l’aide de graphes
L’utilisation d’algorithmes à base de graphes est classique dans le cadre de l’agrégation de permutations [44, 58] (classements complets sans égalités). L’idée générale est de partir d’une liste de permutations et de passer du problème d’agrégation de permutations à un problème de graphes bien connu. Pour ce faire, il faut construire le graphe orienté pondéré défini ci-dessous.
Définition 2.1.1 ([58]). Soit G = (V; A) le graphe orienté pondéré tel que : V = U (autrement dit les sommets sont les éléments à classer). (x; y) 2 A si et seulement si l’élément x est avant l’élément y dans une stricte majorité de permutations.
le poids de (x; y) 2 A correspond à la différence entre le nombre de permutations telles que x est avant y et le nombre de permutations telles que y est avant x.
Remarque. Intuitivement, on peut voir le poids d’un arc comme le nombre minimal de classements qu’il faudrait ajouter pour faire disparaître cet arc. Afin d’illustrer le lien entre permutations et graphes, nous présentons une liste de 3 permutations de 4 éléments en Table 2.1 ainsi que le graphe associé en Figure 2.1.
r1 = [fAg; fBg; fCg; fDg]
r2 = [fAg; fCg; fDg; fBg]
r3 = [fAg; fDg; fBg; fCg]
Le graphe obtenu (Figure 2.1) comporte un cycle formé par les éléments B; C; D. L’existence de ce cycle est liée à la possibilité d’avoir à la fois B avant C, C avant D et D avant B dans une stricte majorité de classements. Or, il est impossible de construire un classement consensuel plaçant à la fois B avant C, C avant D et D avant B. Trouver un classement consensuel optimal revient à rendre le graphe acyclique en retirant un ensemble d’arcs dont la somme des poids est minimale. En effet, retirer un arc permet de résoudre des conflits, forçant ainsi un ordre. Le prix à payer pour retirer un arc correspond au poids de l’arc. Par exemple, retirer l’arc de D vers B dans le graphe présenté en Figure 2.1 permet de de supprimer le cycle formé par A, B, C rendant l’ensemble du graphe acyclique. Cette opération a un coût de 1 ce qui correspond au poids de l’arc (D; B).
Ce problème correspond au très célèbre weighted feedback arc set problem [44, 59, 60]. Ainsi, tous les travaux en théorie des graphes concernant le weighted feedback arc set problem sont directement utilisables dans le cadre de l’agrégation de permutations. Claire Kenyon-Mathieu et al. [60] ont par exemple présenté plusieurs schémas d’approximation en temps polynomial pour le weighted feedback arcset problem [60]. Dans [35], les graphes sont utilisés pour borner le score de Kemeny minimal. Par ailleurs, un algorithme à base de graphe a également été proposé par Betzler et al. [19] et sera discuté dans la Section 2.2.
Malheureusement, le graphe G présenté dans la Définition 2.1.1 ne permet de considérer ni les classements avec égalités, ni les classements incomplets. La prise en compte des égalités nécessite en effet de redéfinir l’en-semble des arcs du graphe afin de pouvoir représenter le cas où l’ordre relatif le moins coûteux pour une paire (x; y) dans un classement consensuel serait l’égalité. Considérons dans un premier temps une liste R de permutations de U et deux éléments x et y de U. On peut se demander s’il est plus intéressant de placer x avant y ou y avant x dans le classement consensuel (indépendamment des autres éléments). Pour ce faire, comparons le nombre de permutations plaçant x avant y, qu’on appelle ici k1, et le nombre de permutations plaçant y avant x, qu’on appelle ici k2. L’idée est donc de regarder quelle(s) valeur(s) est/sont minimale(s) parmi k1 et k2.
Puisque les classements sont ici sont des permutations, il n’y a que trois possibilités :
k1 > k2 : dans ce cas on place un arc de x vers y avec un poids de k1k2.
k1 < k2 : dans ce cas on place un arc de y vers x avec un poids de k2k1.
k1 = k2 : dans ce cas on ne place aucun arc entre x et y.
Considérons maintenant une liste de classements complets avec égalités R0 et considérons une paire (x; y) d’éléments. Appelons respectivement k1, k2 et k3 le nombre de classements de R0 tels que x est avant y, y est avant x et x est à égalité avec y dans les classements de R0. L’objectif est à nouveau de regarder quelle(s) valeur(s) est/sont minimale(s) parmi k1, k2 et k3. Dans ce cas, on ne dénombre pas moins de 7 possibilités (les valeurs minimales ont été mises en gras) :
k1 < k2 k3 k2 < k1 k3 k3 < k1 k2
k1 = k2 < k3 k2 = k3 < k1 k1 = k3 < k2 k1 = k2 = k3
Généraliser le graphe présenté en Définition 2.1.1 pour les classements avec égalités n’est pas trivial étant donné le nombre de nouveaux cas à prendre en compte. Nous apportons un élément de réponse à ce problème au Chapitre 3.
De la même manière, si les classements de R0 peuvent également être incomplets, il faut alors s’intéresser au nombre de classements tels que x est présent et y est absent, au nombre de classements tels que y est présent et x est absent, et au nombre de classements tels que x et y sont absents. Il devient difficile pour un graphe de faire ressortir l’ensemble de ces informations pourtant primordiales.
Algorithmes exacts
Nous avons vu dans la Sous-section 2.1.1 que représenter les permutations à l’aide du graphe présenté pré-cédemment (voir Définition 2.1.1) permet l’utilisation dans le contexte d’agrégation de classements d’algorithmes initialement conçus pour répondre au weighted feedback arcset problem (exacts ou non). Nous allons maintenant présenter des algorithmes exacts conçus spécifiquement pour le problème d’agrégation de classements. Deux ap-proches sont très majoritaires dans ce cadre : la programmation linéaire en nombre entiers et les algorithmes de type séparation et évaluation.
Programmation linéaire en nombre entiers (PLNE)
Une manière classique et naturelle de concevoir un algorithme exact pour calculer un classement consensuel optimal (ou plusieurs classements consensuels optimaux) est la programmation linéaire en nombres entiers. Dans le cas du problème d’agrégation de permutations, la formulation présentée à plusieurs reprises dans la littérature [5, 23, 68, 78] est rappelée en Table 2.2.
minimize P 2 f g 8 6 2 (1)
x6=y2U Qx yby;x+ Qy x bx;y
subject to bx;y 0;1 , x = y U (2)
bx;y + by;x = 1(3)
bx;y bx;z + bz;y, 8x 6= y 6= z(4)
La ligne (1) correspond à la fonction objectif à minimiser. Pour chaque paire d’éléments (x; y), on définit bx;y comme le booléen qui vaut 1 si et seulement si x est avant y dans le classement consensuel et Qx y comme le nombre de fois où x est avant y dans les classements d’entrée. La fonction objectif se décompose comme une somme sur les paires (x; y) d’éléments du coût induit par le positionnement relatif de x et y dans le classement consensuel considéré. Si dans le classement consensuel x est avant y (respectivement y est avant x), le coût induit par cette paire correspond au nombre de classements en désaccord avec cet ordre à savoir le nombre de classements tels que y est avant x (respectivement x est avant y).
La ligne (2) impose que les bx;y (à savoir « b avant y ») soient des variables binaires.
La ligne (3) impose que pour toute paire d’éléments (x; y), soit on place x avant y soit on place y avant x dans le classement consensuel.
Enfin, la ligne (4) correspond à l’inégalité triangulaire : si on a placé x avant z et z avant z, alors x est placé avant y.
A nouveau, la prise en compte des égalités et des classements incomplets n’est pas gérée par cette formulation. Il est donc important de généraliser ces équations afin de les rendre compatibles dans un cadre plus général incluant les classements avec égalités et les classements incomplets. Une tentative de généralisation a été proposée dans [25] pour gérer les classements complets avec égalités. Cependant, elle contient une erreur que nous corrigerons dans le Chapitre 4.
Algorithmes de type séparation et évaluation
Les algorithmes de type séparation et évaluation (branch and bound en anglais) sont fréquemment utilisés pour le problème d’agrégation de permutations [37, 38, 67, 69]. Ces algorithmes utilisent des connaissances sur les bornes supérieures du problème de minimisation afin d’éliminer des familles de solutions dont on sait qu’elles ne peuvent pas être optimales. Par exemple, les auteurs de [67] se servent des travaux de [35] sur le calcul de bornes pour le score de Kemeny minimal pour leur algorithme exact branch and bound.
Les auteurs de [37] ne se basent pas directement sur le score de Kemeny pour leur algorithme exact branch and bound, mais cherchent à maximiser la somme des coefficients de corrélations de Kendall [45] apès avoir montré que ce problème est équivalent à celui de minimiser le score de Kemeny.
Les algorithmes exacts ne peuvent être utilisés que sur de petites instances. Quel que soit le type d’algorithme exact considéré, leur utilisation n’est plus possible dès lors que le nombre d’éléments à trier dépasse quelques dizaines d’éléments pour des raisons de temps d’exécution 1.
Algorithmes d’approximation et heuristiques
Les algorithmes exacts étant difficilement utilisables sur des jeux de données contenant plusieurs centaines d’éléments comme c’est souvent le cas en biologie, il est alors nécessaire de se servir d’algorithmes d’approximation et d’heuristiques. Cette sous-section passe en revue les heuristiques principalement utilisées dans le cadre de l’agrégation de classements.
KwikSort : un algorithme diviser pour régner
L’algorithme KwikSort conçu par Ailon et al. [3] est une 2 approximation pour le problème d’agrégation de permutations : le score de Kemeny d’un classement consensuel renvoyé par cet algorithme est au pire deux fois plus élevé que le score de Kemeny d’un classement consensuel optimal. Cet algorithme est randomisé et son fonctionnement est inspiré du tri rapide.
Remarque. Dans le meilleur des cas, les pivots choisis ont systématiquement séparé en deux groupes de même taille les éléments restant à trier. La complexité est alors (n log2 n) où n est le nombre d’éléments de U. Dans le pire des cas, les pivots choisis ont systématiquement induit deux sous-ensembles dont l’un des deux est vide.
1. Il est possible d’aller jusqu’à une centaine d’éléments pour un algorithme de programmation linéaire en nombres entiers utilisant un solveur commercial comme Cplex ou Gurobi [19]
C’est le cas si, à chaque fois, le pivot choisi est le premier ou le dernier élément parmi ceux restant. La complexité est alors (n2).
Bien que cet algorithme soit une 2 approximation de la méthode Kemeny-Young, son ratio d’approximation devient 117 lorsqu’il est utilisé conjointement avec l’algorithme Pick a Perm également conçu par Ailon [3]. Ce dernier consiste à choisir comme classement consensuel la permutation de R qui minimise le score de Kemeny avec R.
Recherche locale
L’algorithme BioConsert présenté dans [32] est une heuristique de recherche locale. Cette heuristique a été comparée aux autres heuristiques et algorithmes d’approximation de l’état de l’art et a fourni les classements consensuels de meilleure qualité lors d’un banc d’essai effectué par Brancotte et al. [25] sur des jeux de données réels et synthétiques contenant des égalités.
Le principe de cette heuristique est le suivant : on part de chaque classement d’entrée et pour chaque élément on effectue un des deux mouvements possibles suivants si et seulement si ce mouvement améliore le score de Kemeny : déplacer l’élément dans un bucket existant déplacer l’élément dans un nouveau bucket
On effectue ces mouvements jusqu’à ce qu’on ne puisse plus effectuer de tels mouvements capables de diminuer le score de Kemeny. Le meilleur classement parcouru est ainsi retourné. L’algorithme GRASP [43] est une autre heuristique gloutonne de type recherche locale, dont le fonctionnement est très proche de BioConsert. La différence principale est que GRASP est un algorithme randomisé contrairement à BioConsert qui est déterministe.
Borda, Copeland et Schulze : des systèmes électoraux à part entière
Les méthodes Borda [39] Copeland [36] et Schulze [79] sont trois systèmes électoraux qui prennent en en-trée une liste de classements et renvoient un classement consensuel des candidats. Bien qu’étant des systèmes électoraux à part entière, les méthodes Borda et Copeland sont utilisées comme heuristiques pour l’agrégation de classements au sens de la minimisation du score de Kemeny (méthode Kemeny-Young). La méthode Schulze, introduite plus récemment, est beaucoup moins utilisée dans ce contexte mais présente l’avantage d’être axio-matiquement proche de la méthode Kemeny-Young [26] (l’ensemble des critères d’équité respectés par les deux méthodes est très proche).
Les méthodes Borda, Copeland et Schulze consistent à associer un score à chaque élément à classer. Le classement consensuel renvoyé correspond au tri par ordre décroissant de score des éléments.
Soient R = [r1; r2; :::; rm] une liste de permutations de U contenant n éléments et x 2 U. On appelle Bor(x) le score associé à x par la méthode Borda. On a : Bor(x) = i=1 n ri[x] (pour rappel, ri[x] est la position de x dans ri). En d’autres termes, Bor(x) est la somme du nombre de candidats classés après x dans chaque classement d’entrée auquel on a retiré 1.
Illustration 2.1.1. Considérons une liste R = [r1; r2; r3; r4; r5] constituée des cinq permutations suivantes :
r1 = [fAg; fBg; fCg]
r2 = [fAg; fBg; fCg]
r3 = [fAg; fBg; fCg]
r4 = [fCg; fBg; fAg]
r5 = [fCg; fBg; fAg]
On a Bor(A) = 2 + 2 + 2 + 0 + 0 = 6, Bor(B) = 1 + 1 + 1 + 2 + 2 = 7 et Bor(C) = 0 + 0 + 0 + 2 + 2 = 4. Ainsi, le classement consensuel obtenu est r = [fBg; fAg; fCg].
Soient R une liste de permutations de U et x 2 U. On appelle Cop(x) le score associé à x par la méthode Copeland. On a : Cop(x) = w(x) l(x), avec w(x) correspondant au nombre d’éléments y tels que x est avant y dans une stricte majorité de classements et l(x) correspondant au nombre d’éléments y tels que y est avant x dans une stricte majorité de classements.
Si on considère la même liste de permutations que pour la méthode Borda, on obtient Cop(A) = 2 0 = 2 puisque A est avant B dans une stricte majorité de classements et avant C dans une stricte majorité de classements tandis qu’aucun élément n’est avant A dans une stricte majorité de classements. On a également Cop(B) = 1 1 = 0 puisque B est avant C dans une stricte majorité de classements mais après A dans une stricte majorité de classements. De la même manière, on a Cop(C) = 0 2 = 2. Ainsi, le classement consensuel obtenu est r = [fAg; fBg; fCg]. Ce classement consensuel est différent de celui obtenu par la méthode Borda.
La méthode Schulze utilise la construction de graphes ainsi que des algorithmes de calcul du plus court chemin afin d’associer son score à chaque élément. Les détails de cette méthode sont présentés dans [79].
Calculer les scores associés à chaque élément de U est de complexité (n m) par la méthode Borda, (n2 m) pour la méthode Copeland et (n3 m) pour la méthode Schulze (n étant la taille de U à savoir le nombre d’éléments à classer et m la taille de R à savoir le nombre de classements).
A l’interface entre algorithmique et choix social : les techniques de partitionnement
Nous avons vu dans la section précédente que les algorithmes exacts sont trop lents s’il y a beaucoup d’éléments à classer et que les heuristiques ne permettent pas d’évaluer la qualité du classement consensuel renvoyé. Une solution classiquement utilisée pour pallier ces problèmes est de diviser le problème initial en sous-problèmes indépendants de sorte que que la simple concaténation d’un classement consensuel optimal de chaque sous-problème forme un classement consensuel optimal pour le problème de départ.
Plusieurs techniques de partitionnement présentes dans la littérature et détaillées dans cette section permettent un tel partitionnement.
Plusieurs techniques de partitionnement présentes dans la littérature et détaillées dans cette section permettent un tel partitionnement.
Truchon et le critère de Condorcet étendu
Truchon définit le Critère de Condorcet étendu dans [83] permettant de partitionner le problème de départ en sous-problèmes indépendants pour un nombre impair de classements. Comme son nom l’indique, ce critère est une extension du critère de Condorcet défini dans la Sous-section 2.2.3. Notons que Truchon permet les égalités dans les classements d’entrée et considère que le coût de rompre une égalité est égal à 1.
Définition 2.2.1. Critère de Condorcet étendu et partition de Truchon [83]
Truchon définit le critère de Condorcet étendu de la manière suivante. Soit R une liste contenant un nombre impair de classements complets de U et T = [T1; :::; Tk] une partition ordonnée de U telle que 8i < j et 8(x; y) 2 Ti Tj, x est avant y dans une majorité de classements. Alors, 8i < j et 8(x; y) 2 Ti Tj, x est avant y dans tout classement consensuel optimal 2. Une telle partition sera appelée partition de Truchon.
Reprenons nos trois permutations présentées en Table 2.1. On voit que A est avant tous les autres éléments dans une stricte majorité de classements. Ainsi, T = [fAg; fB; C; Dg] est une partition de Truchon. On peut en déduire que A est avant B, C et D dans toutes les solutions optimales.
Il est important de préciser que même si les classements de départ peuvent contenir des égalités, l’objectif de Truchon est de rompre ces égalités afin de produire une permutation de U. Il est donc intéressant de se demander si le critère de Condorcet étendu peut être utilisé dans un cadre plus large, comme par exemple la distance de Kendall- généralisée avec pénalité p (voir Définition 1.3.1 et [47]).
Les auteurs de [19] déterminent une partition de Truchon en calculant les composantes fortement connexes d’un graphe. La complexité de cet algorithme est (jRj jUj2).
Définition 2.2.1. Critère de Condorcet étendu et partition de Truchon [83]
Truchon définit le critère de Condorcet étendu de la manière suivante. Soit R une liste contenant un nombre impair de classements complets de U et T = [T1; :::; Tk] une partition ordonnée de U telle que 8i < j et 8(x; y) 2 Ti Tj, x est avant y dans une majorité de classements. Alors, 8i < j et 8(x; y) 2 Ti Tj, x est avant y dans tout classement consensuel optimal 2. Une telle partition sera appelée partition de Truchon.
Reprenons nos trois permutations présentées en Table 2.1. On voit que A est avant tous les autres éléments dans une stricte majorité de classements. Ainsi, T = [fAg; fB; C; Dg] est une partition de Truchon. On peut en déduire que A est avant B, C et D dans toutes les solutions optimales.
Il est important de préciser que même si les classements de départ peuvent contenir des égalités, l’objectif de Truchon est de rompre ces égalités afin de produire une permutation de U. Il est donc intéressant de se demander si le critère de Condorcet étendu peut être utilisé dans un cadre plus large, comme par exemple la distance de Kendall- généralisée avec pénalité p (voir Définition 1.3.1 et [47]).
Les auteurs de [19] déterminent une partition de Truchon en calculant les composantes fortement connexes d’un graphe. La complexité de cet algorithme est (jRj jUj2).
Les éléments propres
Betlzer et al. définissent dans [17] le concept d’éléments propres (non-dirty elements) en proportion q.
Définition 2.2.2. Un élément x est dit propre en proportion q si pour tout élément y 6= x, soit x est avant y dans une proportion de classements supérieure ou égale à q, soit y est avant x dans une proportion de classements supérieure ou égale à q.
Cas q = 0.75. Les auteurs montrent que si x est un élément propre en proportion 0:75, alors tous les éléments placés avant x dans au moins 75% des permutations sont placés avant x dans tous les classements consensuels optimaux et tous les éléments placés après x dans au moins 75% des permutations sont placés après x dans tous les classements consensuels optimaux. Ceci permet donc de calculer une partition ordonnée de U en trois parties [B1; B2; B3] avec B1 correspondant à l’ensemble des éléments placés avant x dans au moins 75% des permutations, B2 = fxg et B3 correspondant à l’ensemble des éléments placés après x dans au moins 75% des permutations. Intuitivement, si un élément y est avant x dans au moins 75% des permutations et qu’un élément z est après x dans au moins 75% des permutations, alors y est nécessairement avant z dans au moins la moitié des permutations.
Cas q = 2/3. Betlzer et al. ont également démontré dans [17] que si x est un élément propre en proportion 23 , alors il existe un classement consensuel optimal r tel que tous les éléments placés avant x dans au moins 23 des permutations sont placés avant x dans r et tous les éléments placés après x dans au moins 23 des permutations sont placés après x dans r .
Si l’objectif est de calculer un classement consensuel le plus rapidement possible, ce critère sera préféré au précédent. En effet, un élément propre en proportion 0.75 est nécessairement un élément propre en proportion 23 mais la réciproque n’est pas nécessairement vraie. Les éléments propres en proportion 23 sont donc susceptibles de partitionner en un plus grand nombre de parties. Cependant, il est tout à fait possible que des classements consensuels optimaux ne respectent pas le partitionnement obtenu avec les éléments propres en proportion 23 . Cette méthode de partitionnement n’est donc pas à utiliser si l’objectif est de mettre en lumière des points communs entre l’ensemble des classements consensuels optimaux.
Il est intéressant de noter que d’une part le critère de Condorcet étendu et d’autre part le critère de Betzler pour le cas q = 0:75 ont le même objectif à savoir calculer une partition ordonnée des éléments à trier telle que tout clas-sement consensuel optimal respecte cette partition. Nous montrerons dans le Chapitre 3 que ces deux critères sont complémentaires. En effet, certains jeux de données peuvent être partitionnés par le critère de Condorcet étendu mais pas par les éléments propres tandis que d’autres peuvent au contraire être partitionnés par les éléments propres mais pas par le critère de Condorcet étendu.
Ces techniques de partitionnement sont particulièrement intéressantes à coupler aux algorithmes exacts afin de réduire leur temps d’exécution lorsque le nombre d’éléments à trier est grand. Si chaque sous-problème obtenu est de taille suffisamment petite pour qu’un algorithme exact soit utilisé, un classement consensuel optimal est alors obtenu. Malheureusement, ces techniques de partitionnement souffrent de deux défauts majeurs. Nous verrons dans le Chapitre 3 que le critère de Condorcet étendu et les éléments propres en proportion 75% permettent rarement un partitionnement en de nombreux sous-problèmes sur les jeux de données réels. Par ailleurs, aucune méthode de partitionnement décrite dans cette section n’est compatible avec la distance de Kendall- généralisée pour les classements avec égalités. A notre connaissance, aucune n’a été adaptée pour les classements incomplets avec égalités.
Définition 2.2.2. Un élément x est dit propre en proportion q si pour tout élément y 6= x, soit x est avant y dans une proportion de classements supérieure ou égale à q, soit y est avant x dans une proportion de classements supérieure ou égale à q.
Cas q = 0.75. Les auteurs montrent que si x est un élément propre en proportion 0:75, alors tous les éléments placés avant x dans au moins 75% des permutations sont placés avant x dans tous les classements consensuels optimaux et tous les éléments placés après x dans au moins 75% des permutations sont placés après x dans tous les classements consensuels optimaux. Ceci permet donc de calculer une partition ordonnée de U en trois parties [B1; B2; B3] avec B1 correspondant à l’ensemble des éléments placés avant x dans au moins 75% des permutations, B2 = fxg et B3 correspondant à l’ensemble des éléments placés après x dans au moins 75% des permutations. Intuitivement, si un élément y est avant x dans au moins 75% des permutations et qu’un élément z est après x dans au moins 75% des permutations, alors y est nécessairement avant z dans au moins la moitié des permutations.
Cas q = 2/3. Betlzer et al. ont également démontré dans [17] que si x est un élément propre en proportion 23 , alors il existe un classement consensuel optimal r tel que tous les éléments placés avant x dans au moins 23 des permutations sont placés avant x dans r et tous les éléments placés après x dans au moins 23 des permutations sont placés après x dans r .
Si l’objectif est de calculer un classement consensuel le plus rapidement possible, ce critère sera préféré au précédent. En effet, un élément propre en proportion 0.75 est nécessairement un élément propre en proportion 23 mais la réciproque n’est pas nécessairement vraie. Les éléments propres en proportion 23 sont donc susceptibles de partitionner en un plus grand nombre de parties. Cependant, il est tout à fait possible que des classements consensuels optimaux ne respectent pas le partitionnement obtenu avec les éléments propres en proportion 23 . Cette méthode de partitionnement n’est donc pas à utiliser si l’objectif est de mettre en lumière des points communs entre l’ensemble des classements consensuels optimaux.
Il est intéressant de noter que d’une part le critère de Condorcet étendu et d’autre part le critère de Betzler pour le cas q = 0:75 ont le même objectif à savoir calculer une partition ordonnée des éléments à trier telle que tout clas-sement consensuel optimal respecte cette partition. Nous montrerons dans le Chapitre 3 que ces deux critères sont complémentaires. En effet, certains jeux de données peuvent être partitionnés par le critère de Condorcet étendu mais pas par les éléments propres tandis que d’autres peuvent au contraire être partitionnés par les éléments propres mais pas par le critère de Condorcet étendu.
Ces techniques de partitionnement sont particulièrement intéressantes à coupler aux algorithmes exacts afin de réduire leur temps d’exécution lorsque le nombre d’éléments à trier est grand. Si chaque sous-problème obtenu est de taille suffisamment petite pour qu’un algorithme exact soit utilisé, un classement consensuel optimal est alors obtenu. Malheureusement, ces techniques de partitionnement souffrent de deux défauts majeurs. Nous verrons dans le Chapitre 3 que le critère de Condorcet étendu et les éléments propres en proportion 75% permettent rarement un partitionnement en de nombreux sous-problèmes sur les jeux de données réels. Par ailleurs, aucune méthode de partitionnement décrite dans cette section n’est compatible avec la distance de Kendall- généralisée pour les classements avec égalités. A notre connaissance, aucune n’a été adaptée pour les classements incomplets avec égalités.
Lien entre techniques de partitionnement et critères d’équité en théorie du choix social
Nous avons vu dans la Sous-section 2.2.1 le critère de Condorcet étendu. Comme son nom l’indique, ce critère est une extension du critère de Condorcet qui est très couramment cité en théorie du choix social (au point que les systèmes électoraux sont dit de Condorcet s’ils respectent ce critère). Plus généralement, l’étude axiomatique qui intéresse la communauté théorie du choix social permet de caractériser le comportement des différentes méthodes d’agrégation de classements. Si la méthode considérée pour cette thèse est appelée méthode Kemeny-Young en théorie du choix social, il est important de préciser que d’autres méthodes d’agrégation de classements existent et correspondent à différents systèmes électoraux (méthode Copeland, règle de Borda, …). Les critères d’équité permettent alors de caractériser mathématiquement ces différentes méthodes d’agrégation de classements. Nous allons nous focaliser sur deux critères d’équité qui ont un intérêt tout particulier dans le cadre de la recherche de classement consensuel optimal au sens du score de Kemeny : le LIIA pour Local Independance of Irrelevant Alternatives [85] et le critère de Condorcet. Plus précisément, nous allons voir que le LIIA fait du critère de Condorcet une technique de partitionnement du problème de départ en sous-problèmes indépendants.
Partitionnement et « Indépendance locale des alternatives non pertinentes »
Le critère d’équité appelé Local Independence of Irrelevant Alternatives abrégé LIIA et traduit en français par In-dépendance locale des alternatives non pertinentes est un critère d’équité qui est respecté par la méthode Kemeny-Young dans le cas où les classements dont on cherche un classement consensuel sont des permutations de U [86].
Propriété 2.2.1. Soit un sous-ensemble S U de k éléments tel que les éléments de S correspondent aux k premiers ou k derniers éléments dans un classement consensuel optimal r . Soient r0 le classement r duquel seuls les éléments de S ont été conservés et R0 la liste de classements de S correspondant à la liste de classements R dont seuls les éléments de S ont été conservés. Autrement dit, r0 est la projection de r sur S et R0 est la projection de R sur S. Alors, r0 est un classement consensuel optimal pour R0.
Illustration 2.2.1. Pour illustrer le LIIA, prenons une liste R = [r1; r2; r3; r4] constituée des quatre permutations
suivantes :
r1 = [fAg; fCg; fDg; fBg]
r2 = [fBg; fAg; fCg; fDg]
r3 = [fAg; fBg; fDg; fCg]
r4 = [fBg; fDg; fCg; fAg]
Un algorithme exact nous indique que r = [fAg; fBg; fCg; fDg] est un classement consensuel optimal. Reti-rons maintenant l’élément D de ce dernier. On obtient r0 = [fAg; fBg; fCg]. Grâce au LIIA, on sait que r0 est un classement consensuel optimal pour la liste R0 = [r10; r20; r30; r40] constituée des quatre permutations suivantes (les mêmes que précédemment, mais les D ont été retirés) :
r10 = [fAg; fCg; fBg]
r20 = [fBg; fAg; fCg]
r30 = [fAg; fBg; fCg]
r40 = [fBg; fCg; fAg]
Une conséquence directe du LIIA est la suivante. Prenons S U de taille k et supposons qu’une condition suffisante permette d’établir qu’il existe un classement consensuel optimal r pour R tels que l’ensemble des k premiers éléments de r soit égal à S (on n’a pas besoin de connaître l’ordre des éléments de S dans r ). Appelons R1 la liste de classements correspondant à R dont seuls les éléments de S ont été conservés et R2 la liste de classements correspondant à R dont tous les éléments de S ont été retirés. Alors, concaténer un classement consensuel optimal de R1 et un classement consensuel optimal de R2 fournit un classement consensuel optimal pour R. Ainsi, grâce au LIIA, toute propriété garantissant qu’il existe un classement consensuel optimal commençant par un sous-ensemble de U donné permet de partitionner R en deux sous-problèmes indépendants.
Le fait que la méthode Kemeny-Young respecte le LIIA garantit également qu’il n’existe aucun algorithme polyno-mial permettant de trouver l’élément en première position d’un classement consensuel optimal sur n’importe quelle instance (à moins que P = N P ). En effet, si un tel algorithme existait, il suffirait de trouver ce premier élément, de le retirer de R, puis de recommencer récursivement à chercher le premier élément pour le « nouveau R » et ainsi de suite. Ainsi, le classement consensuel optimal se construirait pas à pas, et on obtiendrait donc un classement consensuel optimal par un algorithme polynomial.
Partitionnement et « Indépendance locale des alternatives non pertinentes »
Le critère d’équité appelé Local Independence of Irrelevant Alternatives abrégé LIIA et traduit en français par In-dépendance locale des alternatives non pertinentes est un critère d’équité qui est respecté par la méthode Kemeny-Young dans le cas où les classements dont on cherche un classement consensuel sont des permutations de U [86].
Propriété 2.2.1. Soit un sous-ensemble S U de k éléments tel que les éléments de S correspondent aux k premiers ou k derniers éléments dans un classement consensuel optimal r . Soient r0 le classement r duquel seuls les éléments de S ont été conservés et R0 la liste de classements de S correspondant à la liste de classements R dont seuls les éléments de S ont été conservés. Autrement dit, r0 est la projection de r sur S et R0 est la projection de R sur S. Alors, r0 est un classement consensuel optimal pour R0.
Illustration 2.2.1. Pour illustrer le LIIA, prenons une liste R = [r1; r2; r3; r4] constituée des quatre permutations
suivantes :
r1 = [fAg; fCg; fDg; fBg]
r2 = [fBg; fAg; fCg; fDg]
r3 = [fAg; fBg; fDg; fCg]
r4 = [fBg; fDg; fCg; fAg]
Un algorithme exact nous indique que r = [fAg; fBg; fCg; fDg] est un classement consensuel optimal. Reti-rons maintenant l’élément D de ce dernier. On obtient r0 = [fAg; fBg; fCg]. Grâce au LIIA, on sait que r0 est un classement consensuel optimal pour la liste R0 = [r10; r20; r30; r40] constituée des quatre permutations suivantes (les mêmes que précédemment, mais les D ont été retirés) :
r10 = [fAg; fCg; fBg]
r20 = [fBg; fAg; fCg]
r30 = [fAg; fBg; fCg]
r40 = [fBg; fCg; fAg]
Une conséquence directe du LIIA est la suivante. Prenons S U de taille k et supposons qu’une condition suffisante permette d’établir qu’il existe un classement consensuel optimal r pour R tels que l’ensemble des k premiers éléments de r soit égal à S (on n’a pas besoin de connaître l’ordre des éléments de S dans r ). Appelons R1 la liste de classements correspondant à R dont seuls les éléments de S ont été conservés et R2 la liste de classements correspondant à R dont tous les éléments de S ont été retirés. Alors, concaténer un classement consensuel optimal de R1 et un classement consensuel optimal de R2 fournit un classement consensuel optimal pour R. Ainsi, grâce au LIIA, toute propriété garantissant qu’il existe un classement consensuel optimal commençant par un sous-ensemble de U donné permet de partitionner R en deux sous-problèmes indépendants.
Le fait que la méthode Kemeny-Young respecte le LIIA garantit également qu’il n’existe aucun algorithme polyno-mial permettant de trouver l’élément en première position d’un classement consensuel optimal sur n’importe quelle instance (à moins que P = N P ). En effet, si un tel algorithme existait, il suffirait de trouver ce premier élément, de le retirer de R, puis de recommencer récursivement à chercher le premier élément pour le « nouveau R » et ainsi de suite. Ainsi, le classement consensuel optimal se construirait pas à pas, et on obtiendrait donc un classement consensuel optimal par un algorithme polynomial.
|
Table des matières
1 L’agrégation de classements : définition du problème
1.1 Les classements
1.1.1 Une définition générale de classement
1.1.2 Différentes caractéristiques pour les classements
1.1.3 Positions relatives des éléments dans un classement
1.2 Agrégation de permutations selon la méthode Kemeny-Young
1.2.1 Distance de Kendall-τ
1.2.2 Le score de Kemeny
1.2.3 Classement consensuel optimal
1.2.4 Complexité du problème
1.3 Adaptation pour les classements avec égalités
1.3.1 Distance de Kendall-τ généralisée avec pénalité p
1.3.2 Score de Kemeny généralisé avec pénalité p
1.3.3 Classement consensuel optimal
1.3.4 Complexité de l’agrégation de classements avec égalités
1.3.5 D’autres généralisations aux classements complets
1.4 Conclusion
Résumé du chapitre
2 L’agrégation de classements : État de l’art
2.1 Algorithmique pour l’agrégation de classements
2.1.1 Représentation des permutations à l’aide de graphes
2.1.2 Algorithmes exacts
2.1.3 Algorithmes d’approximation et heuristiques
12.1.4 Récapitulatif des différents algorithmes utilisés pour l’agrégation de classements
2.2 A l’interface entre algorithmique et choix social : les techniques de partitionnement
2.2.1 Truchon et le critère de Condorcet étendu
2.2.2 Les éléments propres
2.2.3 Lien entre techniques de partitionnement et critères d’équité en théorie du choix social
2.3 Gestion des données manquantes
2.3.1 Projection et unification
2.3.2 Généralisations de la distance de Kendall-τ et du score de Kemeny
2.4 Conclusion : enjeux pour l’agrégation de classements
Résumé du chapitre
3 Partitionnement à base de graphes et critère de robustesse
3.1 Introduction
3.1.1 Contexte biologique
3.1.2 Contributions
3.2 Exemple et intuition quant aux enjeux
3.2.1 Un exemple inspiré par les données biologiques
3.2.2 Une première intuition quant au calcul du classement consensuel
3.2.3 Intuition quant à l’évaluation de la robustesse des classements consensuels
3.3 Représentation des classements par paires d’éléments
3.3.1 Définitions préliminaires
3.3.2 Nouvelle formulation du score de Kemeny associé à la pseudo-distance
3.3.3 Matrice des coûts par paires
3.4 Un nouveau graphe pour représenter les classements
3.4.1 Ge : graphe compatible avec le score de Kemeny généralisé à la pseudo-distance
3.4.2 Gc : graphe des composantes fortement connexes de Ge
3.5 Utilisation du graphe Gc pour calculer un classement consensuel
3.5.1 Propriété fondamentale de Gc
3.5.2 Un algorithme de partitionnement pour l’agrégation de classements
3.6 Frontières et partitionnement robuste
3.6.1 Notion de frontière
3.6.2 Graphe robuste des éléments Gr et première condition suffisante pour le calcul de frontières
3.6.3 Combiner Ge et Gr pour trouver plus de frontières
3.6.4 Comparaison avec l’état de l’art
23.7 Nouvelle version de ConQuR-Bio
3.7.1 Le logiciel ConQuR-Bio
3.7.2 ConQuR-BioV2 : prise en compte des retours des biologistes
3.8 Évaluation quantitative des algorithmes ParCons et ParFront
3.8.1 Jeux de données considérés
3.8.2 Évaluation de ParCons sur des données biologiques
3.8.3 Évaluation de ParFront sur des données biologiques
3.9 Intérêt de l’agrégation de classements pour les données biologiques
3.9.1 Jeux de données considérés et gold standards
3.9.2 Résultats obtenus par ConQuR-BioV2 par rapport à Gene du NCBI
3.10 Conclusion
Résumé du chapitre
4 Modèle général pour l’agrégation de classements incomplets
4.1 Introduction
4.1.1 Plusieurs méthodes pour gérer les données manquantes
4.1.2 Comparaison des méthodes
4.1.3 Besoin d’apporter un regard qualitatif sur les données
4.1.4 Besoin d’un cadre algorithmique pour les classements incomplets
4.1.5 Contributions
4.2 Modèle pour l’agrégation de classements incomplets
4.2.1 Définition du modèle
4.2.2 Généricité du modèle
4.2.3 Classes d’équivalence et complexité
4.3 Algorithmes pour l’agrégation de classements incomplets
4.3.1 Un algorithme exact en PLNE
4.3.2 Méthodes de partitionnement
4.3.3 Adaptation des heuristiques de Kemeny pour les KCFs
4.4 Axiomatisation du modèle présenté
4.4.1 Lemmes préliminaires
4.4.2 Définitions préliminaires
4.4.3 Critère de majorité
4.4.4 Critère de Condorcet
4.4.5 Généralisation du critère de Condorcet
34.4.6 Indépendance locale des alternatives non pertinentes
4.5 CoRankCo : plateforme pour l’agrégation de classements
4.5.1 Présentation du logiciel
4.5.2 Utilisation du logiciel
4.5.3 Un package python pour l’agrégation de classements incomplets avec égalités
4.6 Évaluation du modèle : influence du choix de la KCF
4.6.1 Jeux de données considérés
4.6.2 Interprétation des éléments manquants à travers la différence B[5] – B[4]
4.6.3 Influence des vecteurs de pénalité sur la capacité à partitionner
4.6.4 Conclusions des expériences menées
4.7 Conclusion
Résumé du chapitre
Conclusion
Télécharger le rapport complet
