Imprimer 

Résumer un texte par extraction, c'est réussir à trouver dans ce texte des phrases qui, mises ensemble, génèrent un résumé qui à la fois retient l'essentiel et capte un maximum de cet essentiel. C'est ce qu'on appelle le le compromis centralité/diversité. Evidemment, le résumé doit valider des contraintes, souvent en nombre de mots, ce qui complexifie le problème. Alors, une fois qu'on a réussi à évaluer la centralité, donc le fait qu'une phrase véhicule des informations essentielles, comment faire pour maximiser la diversité ? Nous voyons ici la méthode MMR (Maximal Margin Relevance), définie par Golstein et Carbonell (1998).


I. MMR, un algorithme glouton

MMR est un algorithme glouton (ou greedy, en anglais). Le principe d'un algorithme glouton est de décomposer un problème en n étapes. A chaque étape, l'algorithme va faire un choix qui va suivre le principe de l'optimum local. A chaque étape, on ne s'intéresse donc qu'à une partie du problème, et on la résout d'après ces données locales. Pour résoudre certains problèmes, cette stratégie peut s'avérer gagnante. Par exemple, si on doit se rendre de Marseille à Paris, il vaut mieux suivre, si l'on a devant soi deux panneaux directionnels avec kilométrage vers Paris, le panneau indiquant le kilométrage le plus faible. En revanche, pour d'autres problèmes, comme le problème du voyageur de commerce (nous montrerons un exemple très simple un jour...), ce suivre le chemin le plus court à chaque étape peut nous faire tomber dans ce que l'on appelle un minimum local : localement, c'était le meilleur choix, mais ce n'était pas le meilleur en regardant le problème dans sa globalité.

Oui, mais voilà, regarder un problème dans sa globalité peut être extrêmement coûteux. En effet, lister toutes les solutions du problème du voyageur de commerce avec seulement 20 villes est quasiment impossible dans un temps raisonnable : il y a environ 2.5x10^18 solutions, soit 2.5 milliards de milliards de solutions. En considérant une machine de puissance moyenne aujourd'hui, qui permet de réaliser 10 milliards d'additions à la seconde, il faudrait plus de 100 millions de secondes pour calculer l'ensemble des solutions, soit plus de 3 ans. Certains problèmes sont ainsi faits que leur ajouter une donnée simple multiplie par le nombre de données total la complexité en temps de calcul, soit le temps qu'il faut pour venir à bout du problème en utilisant un algorithme "bête". On en vient à bout en utilisant des heuristiques : ce sont des méthodes de calcul qui permettent de trouver une solution en un temps convenable, sans garantir de l'optimalité de la solution.

Prenons maintenant l'exemple du résumé automatique. Si un texte comporte 100 phrases en entrée, et que l'on veut le résumer en 10 phrases. Il faudra donc choisir parmi (100! / (100-10)!) combinaisons possibles, soit plus de 60 milliards de milliards de solutions. Pour résoudre ce problème, il faut donc évidemment une heuristique. La première heuristique à avoir été popularisée afin de prendre en compte la diversité dans les résumés est donc MMR (Goldstein et Carbonell, 1998).


II. Description de MMR

MMR est donc un algorithme glouton. Il va procéder en n étapes (itérations) pour générer un résumé de n phrases. A chacune des étapes, il va sélectionner la phrase qu'il juge la meilleure. Ainsi, on réduit fortement le problème, puisqu'à l'étape i, l'algorithme va analyser m-i phrases, m étant le nombre de phrases des documents source. L'algorithme de sélection a donc une complexité en o(nxm). C'est un progrès énorme en complexité, le problème devient largement abordable pour une machine ! (mais la solution n'est pas optimale)

MMR nécessite deux fonctions : un score de centralité pour une phrase p :C(p) (dans l'article d'origine, on cherche à construire un résumé d'après la requête d'un utilisateur; la centralité est donc la similarité avec la requête) et une similarité entre deux phrases pi et pj phrases : sim (pi, pj). Disposant de ces deux fonctions, il va ajouter à un résumé R la phrase qui maximise le score suivant :

MMR (p) = λ × (C(p) - (1-λ) & times argmaxq ∈ R (sim (p, q))

Le score MMR vise donc à sélectionner à chaque étape la phrase qui maximise la centralité de la phrase moins la similarité maximum de cette phrase avec les phrases déjà sélectionnées, afin d'éviter la redondance. Le paramètre λ est appelé facteur de nouveauté. Il va permettre d'affiner la sélection selon que l'on veut plus de centralité ou plus de diversité.

Un tel algorithme est donc extrêmement rapide, mais sa rapidité a un inconvénient majeur : il ne se fonde que sur des choix locaux, et n'atteint donc pas forcément la solution optimale.