Imprimer 

Les années 2000 (Erkan & Radev, 2004, Mihalcea, 2004) ont vu apparaître de nouvelles méthodes de résumé automatique, fondées sur l'analyse de graphes. Ces nouvelles méthodes utilisent un algorithme semblable à celui du PageRank, développé par l'Université de Stanford et utilisé alors par Google afin d'évaluer la popularité d'une page web au sein du graphe du Web.

 


I. Le PageRank

Le PageRank est un algorithme très populaire notamment en analyse de réseaux sociaux ou en biologie. Cet algorithme simule une marche aléatoire. On peut prendre l'image d'un réseau de villes reliées par des routes plus ou moins larges allant d'une ville à une autre et d'un promeneur qui utiliserait une méthode aléatoire pour, depuis une ville donnée, déterminer vers quelle ville aller. Cette méthode aléatoire serait fondée sur une loi de probabilités qui dépend de la largeur de la route. Plus une route est large, plus il a de chances de la prendre. Si ce promeneur se promène infiniment, alors en comptant le nombre de fois qu'il est passé dans une ville, on peut avoir une idée de la centralité de cette ville au sein du réseau de villes.

Un problème subsiste alors : si ce réseau de villes comporte des sous-réseaux non connexes, c'est-à-dire des réseaux de villes plus petits à l'intérieur du réseau principal, et qui ne sont pas reliés entre eux (par exemples les cités mayas qui constituaient un sous-réseau non connexe au sous-réseau des villes européennes avant 1492), alors ce promeneur ne pourrait jamais s'y rendre, et la centralité de certaines villes ne pourrait pas être évaluée! Il existe une méthode très simple pour venir à bout de ce problème : définir une probabilité que pour chaque ville traversée, au lieu de se rendre forcément dans une ville qui lui est reliée, on saute aléatoirement vers n'importe quelle autre ville du réseau. Dans l'algorithme PageRank, c'est ce qu'on appelle le damping factor.

Appliqué au graphe du Web, le PageRank, qui tire son nom de son inventeur, Larry Page (cofondateur de Google) permet de déterminer quelle est la probabilité de chaque page qu'un visiteur tombe aléatoirement dessus en suivant au hasard les liens présents dans les pages web qu'il consulte. Ainsi, les pages dont la probabilité de visite est la plus élevée sont également les plus centrales du Web.

L'aspect important apporté par le PageRank est une preuve de convergence : les scores doivent converger à l'infini vers la solution du problème.


II. Application au résumé automatique

Quand on cherche à résumer automatiquement un texte par extraction, c'est-à-dire en choisissant dans le texte les éléments (paragraphes, phrases, sous-phrases) les plus pertinents, on travaille sur le compromis entre la centralité et la diversité. On cherche donc à extraire les éléments les plus centraux du texte, tout en essayant de couvrir au maximum les sujets du texte d'origine. Cette notion de centralité d'une phrase dans un texte renvoie immédiatement à celle plus générale de la centralité dans un réseau. En modélisant un texte sous la forme d'un graphe, on pourrait adapter le PageRank afin de trouver les phrases les plus centrales.

C'est ce qu'ont proposé, la même année, en 2004, Erkan&Radev et Mihalcea, avec deux techniques assez semblables dont nous détaillerons pas ici les différences. Ces techniques modélisent un texte dans un graphe dont les nœuds sont les phrases et les arêtes les similarités entre elles. Deux différences majeures par rapport au PageRank apparaissent alors :

Par bonheur, ces changements n'influent pas sur la preuve de convergence de l'algorithme de marche aléatoire, et l'algorithme est donc transposable au problème du résumé automatique pour évaluer la centralité d'une phrase dans un texte.


III. Oui mais la diversité dans tout ça ?

Le problème de cet algorithme, c'est qu'il permet de sélectionner les phrases centrales, mais pas d'éliminer la redondance, ni de permettre que le résumé couvre un maximum d'informations importantes du texte (la diversité). Deux phrases exactement identiques auront en effet le même score. Des phrases contenant des informations en double pourraient également être incluses dans le résumé automatique si leur score est bon.

Des méthodes sont envisageables pour résoudre ce problème. MMR (Carbonell, 98), par exemple, une stratégie de sélection itérative des phrases. Au lieu de sélectionner directement les meilleures phrases, on choisit la meilleure, puis on reclasse les phrases en leur appliquant un nouveau score : le score de centralité moins la similarité maximum avec les phrases déjà sélectionnées. La meilleure des phrases est alors sélectionnée selon ce score, et la méthode est appliquée itérativement jusqu'à ne plus pouvoir satisfaire les contraintes du résumé (par exemple nombre maximum de mots, ou nombre maximum de phrases).

La méthode CSIS proposée par Radev, 2004 est aussi une méthode itérative. Elle consiste à sélectionner à chaque itération la meilleure phrase, puis de supprimer des phrases non encore sélectionnées toutes celles qui ont une similarité supérieure à un certain seuil. Cette similarité est calculée différemment de la similarité utilisée dans le graphe, et est sensée rendre mieux compte de l'inclusion mutuelle d'information.

D'autres méthodes utilisent les algorithmes évolutionnaires. En définissant un malus lié à la redondance et un score de résumé égal à la somme des scores des phrases qui le constituent, on cherche à sélectionner le meilleur résumé, donc celui qui maximise le score moins le malus grâce à un algorithme génétique dans lequel les individus sont les résumés candidats, et les gènes les phrases des textes à résumer.


Références