Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

eduscol.education.fr/ - Ministère de l’Éducation nationale et de la Jeunesse -

eduscol.education.fr/ - Ministère de l’Éducation nationale et de la Jeunesse - Juin 2019 1 Retrouvez éduscol sur : VOIE GÉNÉRALE Sciences numériques et technologie 2de Sciences numériques et technologie 2DE 1RE TLE VOIE GÉNÉRALE ENSEIGNEMENT Informer et accompagner les professionnels de l’éducation COMMUN LE WEB - MOTEUR DE RECHERCHE Note d’intention Le moteur de recherche, véritable révolution, a bouleversé de nombreux métiers. Cette activité propose de comprendre un des algorithmes qui peut se cacher derrière. Nous nous intéresserons ici au moteur de recherche du PageRank de GOOGLE. Comment un moteur de recherche classe-t-il les sites ? Position du problème Pour hiérarchiser la pertinence de site web sur un domaine, plusieurs solutions assez naturelles existent : • il est possible de faire appel à une sommité (personne ou groupe de personnes) du domaine pour classer les pages. Le classement serait certes très pertinent pour ce domaine, mais il faudrait solliciter un grand nombre de spécialistes de différents domaines pour obtenir un algorithme pouvant traiter des requêtes dans tous les domaines possibles et imaginables ; Il se pose aussi la difficulté de gérer le très grand nombre de pages évoquant une requête (plusieurs millions au minimum) ainsi que l’actualisation fréquente de ce classement. • une deuxième solution serait de demander aux internautes eux-mêmes de voter, pour chaque domaine, et de choisir le classement sur la base de ce vote, considérant que, compte tenu du grand nombre de votants, le classement obtenu serait pertinent. Ces deux modèles, pourtant intéressants et logiques (ils sont mis en œuvre par Wikipédia), font intervenir l’humain et trouvent leur limite dans le trop grand nombre de pages à gérer qui, de plus, sont évolutives. Contenus Moteurs de recherche : principes et usages Capacités attendues Mener une analyse critique des résultats fournis par un moteur de recherche. Comprendre les enjeux de la publication d’informations. eduscol.education.fr/ - Ministère de l’Éducation nationale et de la Jeunesse - Juin 2019 2 Retrouvez éduscol sur : VOIE GÉNÉRALE Sciences numériques et technologie 2de Ce qui conduit à privilégier des protocoles entièrement automatisables sous forme d’algorithme. Dans cette optique, Google a cherché un modèle de hiérarchisation qui soit exploitable dans tous les domaines, utilisable pour tous les mots clés, adaptable à un très grand nombre de données, même évolutives, tout en étant automatisable et suffisamment efficace. C’est en répondant à ce cahier des charges que ce nouveau venu à réussi l’exploit, en quelques mois et malgré l’émergence de Bing ou encore Qwant, à obtenir le quasi-monopole de la rechercher thématique sur le web. L ’idée à la base du modèle de Larry Page et Sergey Brin, fondateurs de Google, revient à attribuer à chaque page un nombre positif entre 0 et 1, appelé score (en anglais PageRank) de la page, qui caractérisera la pertinence de cette page. Ils proposent alors de déterminer ce score à partir des deux règles suivantes : R1 - Le score attribué à une page doit être d’autant plus élevé que celle-ci est référencée dans une page faisant autorité (dont le score élevé) ; R2 - Le score attribué à une page doit être d’autant moins élevé que celle-ci est référencée dans une page contenant un grand nombre de références. Leur idée : utiliser un surfeur aléatoire. Principe du surfeur aléatoire Après avoir fait la liste (sans classement) de tous les sites traitant la requête, le surfeur aléatoire en choisit un au hasard. Puis il s’intéresse aux liens hypertextes du site sur lequel il se trouve vers les autres sites qu’il a listés. Il en choisit alors un au hasard et répète cette opération sans s’arrêter en comptant pour chacun des sites combien de fois il l’a visité. Les sites sont alors affichés dans l’ordre décroissant de leur nombre de visites. Ainsi pour un certain mot clé rentré, il s’intéresse aux sites qui évoquent ce mot-clé, mais également aux liens hypertextes qui permettent de passer d’un site à l’autre. Exercices Exercice 1 - et concrètement ? Pour illustrer comment un algorithme de calcul peut être mis en place à partir de ces règles, nous allons prendre l’exemple du classement de quatre pages. Le problème de l’attribution du score peut être représenté par un graphe orienté : les quatre pages sont représentées par les quatre sommets d’un graphe dont les arêtes orientées représentent les références (liens) pouvant exister entre ces différentes pages. Matériel : un dé à six faces eduscol.education.fr/ - Ministère de l’Éducation nationale et de la Jeunesse - Juin 2019 3 Retrouvez éduscol sur : VOIE GÉNÉRALE Sciences numériques et technologie 2de Dans ce graphe, la flèche allant de 1 vers 2 signifie que la page 1 référence la page 2 et l’absence de flèche de 2 vers 4 signifie que la page 2 ne référence pas la page 4. 1. Choisissez un site parmi les 4 qui sera votre point de départ pour tout l’exercice. 2. Précisez comment avec un dé vous pouvez simuler un déplacement aléatoire de notre surfeur. 3. Simulez pendant un certain temps le surfeur aléatoire en n’oubliant pas de noter le nombre de fois où il est passé par site. Site 1 2 3 4 Nombre de visites 4. Proposez un classement de ces 4 pages. 5. Comparez votre classement avec les autres groupes. 6. Indiquez s’il est intéressant de comparer vos effectifs avec ceux des autres groupes. Proposer une solution pour remédier à ce problème. Précisez ce que l’on remarque alors. Exercice 2 - un deuxième graphe 1. Estimez le PageRank des sites représentés par le graphe ci-dessous. 2. Comparez vos scores avec les autres groupes. Il sera effectué 50 surfs aléatoires. Commentaires Ce premier exercice a pour but de faire manipuler le surfeur aléatoire aux élèves au moyen d’un dé. Il permet de réexpliquer la consigne éventuellement à des groupes qui l’auraient mal comprise. En effet, la convergence des fréquences étant assez rapide, avec une trentaine de sauts, les différents groupes devraient avoir le même classement. Un groupe qui aurait un classement divergeant est vraisemblablement un groupe qui a mal compris le principe. D’autre part, sans autres consignes, notamment sur le nombre de surfs aléatoires à exécuter, la comparaison des effectifs n’a que peu de sens (même si l’ordre de classement sera le même). L’idée est de faire émerger que la bonne quantité à comparer est la fréquence de visite de chaque site. eduscol.education.fr/ - Ministère de l’Éducation nationale et de la Jeunesse - Juin 2019 4 Retrouvez éduscol sur : VOIE GÉNÉRALE Sciences numériques et technologie 2de Exercice 3 - un premier problème La technique du surfeur aléatoire ne marche pas pour le graphe suivant : 1. Expliquez pourquoi. 2. Proposez une solution pour pallier ce problème. 3. Faites alors une proposition de classement pour ce graphe après avoir calculé le PageRank. Commentaires Après avoir pris un temps de remédiation pour les groupes qui n’avaient pas tout à fait compris le principe du surf, cet exercice, où l’on invitera les différents groupes à donner la fréquence plutôt que l’effectif, permet d’illustrer le principe de l’algorithme. Les fréquences sont très similaires, et cela indépendamment du site de départ. Cet exercice permet aussi une deuxième remédiation pour des groupes qui n’auraient toujours pas compris le principe du surf aléatoire et la modélisation proposée pour l’illustrer. Commentaires Cet exercice présenter le premier écueil de l’algorithme : que faire quand un site n’a aucun lien vers d’autres sites ? Assez spontanément, les élèves ont tendance à rajouter des flèches vers les autres sites. Cette solution : le surf équiprobable permet de résoudre cette difficulté. eduscol.education.fr/ - Ministère de l’Éducation nationale et de la Jeunesse - Juin 2019 5 Retrouvez éduscol sur : VOIE GÉNÉRALE Sciences numériques et technologie 2de Exercice 4 - puits 1. Calculez les PageRank du graphe suivant. Le comparer avec les autres groupes. 2. Indiquez le problème moral soulevé par ce graphe. 3. Proposez, si possible, une solution pour pallier ce problème. Exercice 5 - poche web 1. Estimez les PageRank des sites suivants. Comparez avec les autres groupes. 2. Précisez le problème soulevé par ce graphe. 3. Proposez, si possible, une solution pour pallier ce problème. Heureusement qu’il y a les maths ! Un théorème complexe d’algèbre linéaire qui peut s’adapter à notre cas : le théorème de Peyron-Froebenius nous dit que si de chaque sommet part un lien vers chacun des autres sommets alors les fréquences des positions au cours de notre surf aléatoire vont toujours converger vers la même valeur et cela indépendamment de la position de départ. Commentaires Ces deux exercices présentent le principal écueil de l’algorithme : le blocage dans un puits ou une poche du web. Même si les élèves peuvent avoir de nombreuses idées pour s’en sortir, la solution choisie par Google ne peut être trouvée à cause de la trop grande difficulté mathématique : les chaines de Markov et le théorème de Peyron-Froebenius se trouvant en dehors de leur connaissance. C’est le moment de leur présenter la solution mise en place par Google. eduscol.education.fr/ - Ministère de l’Éducation nationale et de la Jeunesse - uploads/Science et Technologie/ ra19-lycee-g-snt-2nd-pagerank-1156204-pdf.pdf