Chapitre 4 Natural Language Processing

Unformatted text preview:

CHAPITRE 4 Natural Language Processing Ou traitement du langage naturel 95 4 1 Compl tion La compl tion 96 est un m chanisme qui permet un utilisateur de saisir les mots de sa recherche avec moins de caract res qu elle n en contient L utilisateur saisit plus rapidement Si ces outils sont appr ciables du point de vue utilisateurs ils le sont tout autant c t site web en r duisant la variabilit dans le texte saisie en particulier les fautes d orthographes L utilisateur a besoin de moins de requ tes pour trouver son produits et cela diminue d autant la charge du serveur qui lui fournit ses r sultats Ce chapitre aborde diff rentes probl matiques li es ce genre de syst mes qui sont pr sents partout sur Internet moteurs de recherches sites de ventes en ligne journaux Il existe de nombreuses librairies qui les impl mentent La 95 https fr wikipedia org wiki Traitement automatique du langage naturel 96 https fr wikipedia org wiki Compl C3 A8tement 111 Machine Learning Statistiques et Programmation Version 0 1 407 plus connue en Python est whoosh 97 Quelques l ments de codes sont disponibles dans le module completion et le notebook Compl tion page 344 Vous pouvez galement lire How to Write a Spelling Corrector 98 de Peter Norvig 99 et d couvrir le sujet avec On User Interactions with Query Auto Completion 100 de Bhaskar Mitra Milad Shokouhi Filip Radlinski Katja Hofmann 4 1 1 Formalisation Probl me d optimisation page 112 Ensemble des compl tions page 113 Gain page 113 Probl me d optimisation Je me r f re pour cela l article Sevenster2013 page voir aussi Bampoulidis2017 page qui introduit diff rentes fa ons de construire un syst me d autocomp tion et qui les compare l usage Et s il existe plusieurs fa ons de faire il faut d abord mettre au point une fa on de les comparer Je me place dans le cadre d un moteur de recherche car c est l usage principal que celui ci soit un moteur de recherche ou une recherche incluse sur un site de vente A la n de la journ e on sait quelles sont les requ tes saisies par les utilisateurs et le nombre de fois qu elles ont t saisies qi wi pour i 1 N Sans syst me de compl tion les utilisateurs saisissent donc K cid 26 N i 1 l qi wi o l qi est la longueur de la compl tion qi Avec le syst me de compl tion les utilisateurs saisissent moins de caract res c est ce chiffre l qu on cherche minimiser L unit est le charact re saisi ou keystroke en anglais M me avec le m me syst me de compl tion il n est pas dit que tous les utilisateurs saisissent la m me requ te de la m me fa on Pour simpli er on va supposer que si malgr tout et ne consid rer que la fa on minimale de saisir une requ te L exemple pr c dent illustrent deux fa ons de saisir le terme autocompl tion sur Wikip dia autocom 4 touches vers le bas ou autocomp 1 touche vers le bas soit 7 4 11 touches dans le premier cas ou 8 1 9 touches dans le second cas D nition D1 Minimum Keystroke 97 https whoosh readthedocs io en latest 98 http norvig com spell correct html 99 http norvig com 100 https www semanticscholar org paper On user interactions with query auto completion Mitra Shokouhi 71e953caa2542a61b52e684649b3569c00251021 pdf 112 Chapitre 4 Natural Language Processing Machine Learning Statistiques et Programmation Version 0 1 407 On d nit la fa on optimale de saisir une requ te sachant un syst me de compl tion S comme tant le minimum obtenu M q S min k K q k S 0 k l q 4 1 La quantit K q k S repr sente le nombre de touche vers le bas qu il faut taper pour obtenir la cha ne q avec le syst me de compl tion S et les k premi res lettres de q De fa on vidente K q l q S 0 et M q S l q et K q k S 0 si k l q On prend galement comme convention q S K q k S et q S M q S l q Certains syst mes proposent des requ tes avant de saisir quoique ce soit c est pourquoi on inclut la valeur M q 0 qui repr sente ce cas Construire un syst me de compl tion revient minimiser la quantit M S M qi S wi N cid 11 i 1 Ensemble des compl tions Il n y a pas de restriction sur la fonction K q k S mais on se limitera dans un premier temps une fonction simple On suppose que le syst me d autocompl tion dispose d un ensemble de requ tes ordonn es S si et la fonction K q k S position q S q 1 k O S q 1 k est le sous ensemble ordonn de S des compl tions qui commencent par les k premi res lettres de q et de longueur sup rieure strictement k position q S q 1 k est la position de q dans cet ensemble ordonn ou 1 sauf si k l q auquel cas elle est nulle si elle n y est pas Cette position est strictement positive K q k S Cela signi e que l utilisateur doit descendre d au moins un cran pour s lectionner une compl tion On note q la position de la compl tion q dans l ensemble S Par construction s cid 6 s2 s1 cid 11 s2 K q k S i si cid 41 q 1 k si S si q 4 2 d signe le cardinal de l ensemble Trouver le meilleur syst me de compl tion S revient trouver la meilleure fonction K q k S et dans le cas restreint l ordre sur S qui minimise cette fonction Le plus souvent on se contente de trier les compl tions par ordre d croissant de popularit On consid rera par la suite qu on est dans ce cas Gain On d nit le gain en keystroke comme tant le nombre de caract res saisis en moins Minimier M S ou maximiser G S cid 26 N G q S l s M q S i 1 G qi S wi revient au m me G S wi l s M q S wil s wiM q S K M S N cid 11 i 1 N cid 11 i 1 N cid 11 i 1 i 1 l qi wi l ensemble des caract res tap s par les utilisateurs G S K est en quelque sorte le ratio de caract res conomis s par le syst me de compl tion O K cid 26 N 4 1 2 Fausses id es re ues 4 1 Compl tion 113 Machine Learning Statistiques et Programmation Version 0 1 407 Il faut trier les …


View Full Document

Chapitre 4 Natural Language Processing

Download Chapitre 4 Natural Language Processing
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Chapitre 4 Natural Language Processing and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Chapitre 4 Natural Language Processing 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?