Agrégation externe de mathématiques, session 2008 Épreuve de modélisation, opti

Agrégation externe de mathématiques, session 2008 Épreuve de modélisation, option B : Calcul Scientifique (public 2008) Résumé : On s’intéresse à des questions de valeurs propres qui interviennent de façon cruciale dans le fonctionnement des moteurs de recherche sur Internet Mots clefs : Valeurs propres et vecteurs propres de matrice, systèmes linéaires ▶ Il est rappelé que le jury n’exige pas une compréhension exhaustive du texte. Vous êtes laissé(e) libre d’organiser votre discussion comme vous l’entendez. Des suggestions de développement, largement indépendantes les unes des autres, vous sont proposées en fin de texte. Vous n’êtes pas tenu(e) de les suivre. Il vous est conseillé de mettre en lumière vos connaissances à partir du fil conducteur constitué par le texte. Le jury appréciera que la discussion soit accompagnée d’exemples traités sur ordinateur. La recherche d’informations pertinentes sur le Web est un des problèmes les plus cruciaux pour l’utilisation de de ce dernier. Des enjeux économiques colossaux sont en jeu, et diverses multinationales se livrent à de grandes manœuvres. Le leader actuel de ce marché, Google, utilise pour déterminer la pertinence des références fournies, un certain nombre d’algorithmes dont certains sont des secrets industriels jalousement gardés, mais d’autres sont publics. On va s’intéresser ici à l’algorithme PageRank, lequel fait intervenir des valeurs propres et vecteurs propres d’une énorme matrice. 1. La matrice de Google À un moment donné, on peut considérer que le Web est une collection de N ∈N pages, avec N très, très grand (de l’ordre de 1010 en octobre 2005). La plupart de ces pages incluent des liens hypertextes vers d’autres pages. On dit qu’elles pointent vers ces autres pages. L’idée de base utilisée par les moteurs de recherche pour classer les pages par ordre de pertinence décroissante consiste à considérer que plus une page est la cible de liens venant d’autres pages, c’est-à-dire plus il y a de pages qui pointent vers elle, plus elle a de chances d’être fiable et intéressante pour l’utilisateur final, et réciproquement. Il s’agit donc de quantifier cette idée, c’est-à-dire d’attribuer un rang numérique ou score de pertinence à chaque page. On se donne donc un ordre arbitraire sur l’ensemble des pages que l’on numérote ainsi de i = 1 à i = N. La structure de connectivité du Web peut alors être représentée par une matrice C de taille N ×N telle que cij = 1 si la page j pointe sur la page i, ci j = 0 sinon. Les liens d’une page sur elle-même ne sont pas significatifs, on pose donc cii = 0. On observe que la ligne i contient tous les liens significatifs qui pointent sur la page i, alors que la colonne j contient tous les liens significatifs présents sur la page j. On souhaite attribuer à chaque page i un score ri ∈R∗ + de façon à pouvoir classer l’ensemble des pages par score décroissant et présenter à l’utilisateur une liste ainsi classée des pages Page 1/5 2008AB1X 28 (public 2008) Option B : Calcul Scientifique correspondant à sa requête. L’algorithme PageRank part du principe qu’un lien de la page j pointant sur la page i contribue positivement au score de cette dernière, avec une pondération par le score rj de la page dont est issu le lien — une page ayant un score élevé a ainsi plus de poids qu’une n’ayant qu’un score médiocre — et par le nombre total de liens présents sur ladite page Nj = ∑N k=1 ck j. On introduit donc la matrice Q définie par qi j = ci j/Nj si Nj ̸= 0, qi j = 0 sinon. La somme des coefficients des colonnes non nulles de Q vaut toujours 1. L’application des principes ci-dessus conduit donc à une équation pour le vecteur r ∈RN des scores des pages de la forme (1) ri = N ∑ j=1 qi jr j c’est-à-dire r = Qr. Le problème du classement des pages du Web se trouve ainsi ramené à la recherche d’un vecteur propre d’une énorme matrice, associé à la valeur propre 1 ! Il peut arriver que la matrice Q n’admette pas la valeur propre 1 ce qui invalide quelque peu la philosophie originale de l’algorithme. Pour remédier à ce défaut, on considère alors e = t1 1 ··· 1 ∈RN et d ∈RN tel que d j = 1 si Nj = 0, dj = 0 sinon. La matrice (2) P = Q+ 1 N e td est maintenant la transposée d’une matrice stochastique : ses coefficients sont tous positifs et la somme des coefficients de chaque colonne vaut 1 (remarquons qu’il s’agit d’une « petite » correction à Q car N est très grand). Du fait que teP = te, on voit que P admet bien la valeur propre 1. Comme cette valeur propre est en général multiple, on effectue une dernière modification en choisissant un nombre 0 < α < 1 et en posant (3) A = αP+(1−α) 1 N e te. On pourra admettre qu’une telle matrice admet 1 comme plus grande valeur propre, que cette valeur propre est simple et que l’on peut choisir un vecteur propre correspondant à composantes toutes positives (il s’agit du théorème de Perron-Frobenius). Finalement, PageRank calcule un tel vecteur propre r ∈RN, normalisé d’une façon ou d’une autre, (4) r = Ar, dont les N composantes fournissent le classement recherché des pages du Web. On sait com- bien cette stratégie s’est révélée efficace, puisque Google a totalement laminé les moteurs de recherche de première génération, comme Altavista, lesquels ont essentiellement disparu du paysage. 2. La méthode de la puissance Étant donnée la taille de la matrice A, la seule méthode numérique envisageable pour calculer le vecteur r n’est autre que la méthode de la puissance. Rappelons-en rapidement le principe. 2008AB1X 28 Page 2/5 (public 2008) Option B : Calcul Scientifique On part d’un vecteur initial r0 ̸= 0, et l’on procède à l’itération (5) qk = Ark−1, rk = qk ∥qk∥1 , avec ∥v∥1 = ∑N i=1 |vi|. Si l’on choisit le premier vecteur r0 à composantes positives, par exemple r0 = e, cette méthode converge vers le vecteur propre recherché r. La vitesse de convergence est de l’ordre de |λ2|k où λ2 est la deuxième valeur propre de A, celles-ci étant classées par ordre de module décroissant. En fait, on peut assez facilement montrer que |λ2| = α, ce qui donne un contrôle explicite sur la vitesse de convergence. En effet, soient {1,µ2,µ3,...,µN} les valeurs propres de P. On pose ˆ e = 1 √ Ne et on choisit une matrice U1 de taille N ×(N −1) telle que la matrice U = ˆ e U1  soit orthogonale. Il vient tUPU =  1 0 w T  , avec T = tU1tPU1. Manifestement, les valeurs propres de T sont {µ2,µ3,...,µN}. Un calcul analogue montre que tUAU =  1 0 αw αT  , ce qui montre que les valeurs propres de A sont {1,αµ2,αµ3,...,αµN}. En particulier, comme 1 est la valeur propre de plus grand module de P, on voit que le module de la seconde valeur propre de A est inférieur à α. 3. Aspects algorithmiques La difficulté de la méthode de la puissance dans le cas de la matrice A vient de sa taille gigantesque. La matrice de départ Q est une matrice très creuse pour laquelle des produits matrice-vecteur sont envisageables en pratique. Par contre, la matrice A est pleine, elle contient de l’ordre de 1020 éléments et il est hors de question de l’assembler explicitement et encore moins de l’utiliser pour calculer des produits matrice-vecteur ! Tout d’abord, on remarque que le vecteur q2 est tel que ∥q2∥1 = teq2 = 1. À partir de cette étape, la normalisation devient donc inutile. On peut d’ailleurs décider de partir d’un vecteur r0 tel que ∥r0∥1 = 1. Par ailleurs, on voit que y = Az peut s’écrire sous la forme y = αQz + β Ne. Si ∥z∥1 = 1, on a bien sûr ∥y∥1 = 1, d’où β = 1 −∥αQz∥1. On a ainsi ramené le calcul du produit matrice pleine-vecteur original à un produit matrice creuse-vecteur et à une évaluation de norme, effec- tivement calculables à l’échelle du Web (à condition de disposer de ressources informatiques conséquentes, quand même). On aboutit de la sorte à un algorithme simple Choisir r Tant que s ≥tolérance, faire ˆ r = αQr Page 3/5 2008AB1X 28 (public 2008) Option B : Calcul Scientifique β = 1−∥ˆ r∥1 ˜ r = ˆ r + β Ne s = ∥˜ r −r∥1 r = ˜ r Retourner r Une valeur typique de α est α = 0.85. Pour satisfaire une tolérance de 10−4, suivant l’ordre de grandeur de la constante dans l’estimation de la vitesse de convergence, on peut estimer qu’il faut quelques dizaines itérations au plus. 4. Aspect système linéaire Transformer un problème de calcul de vecteur propre (4) en une résolution de système linéaire est en règle générale une mauvaise idée. Dans notre uploads/s3/2-texte2008-google.pdf

Tags
Administrationmatrice propre vecteur valeur pages
Documents similaires
  • 55
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager