Home

Rinaldo José de Lima - Universidade Federal de Pernambuco

1. 44 4 2 3 2 tape d application de r gles extraction Le fichier de configuration pour l tape d extraction est le fichier CLASSIFIER CONFIG XML dans lequel lt ties config gt est l l ment principal Il est constitu de plusieurs balises d crivant les modules du TIES employ s pour l extraction classificateur strat gie d extraction tokeniseur et corpus loader Les directives de contr le d entr e et de sortie sont aussi mises dans le fichier de configuration ainsi que la m moire cache toujours essentielle pour optimiser les performances du syst me et l utilisation de la m moire Ci dessous un extrait du fichier de configuration d extraction CLASSIFIER CONFIG XML concernant le corpus CMU Seminar announcements Le manuel d utilisateur ITC IRST 2004 contient des explications sur la fa on de param trer le syst me Configuration file for the standard CMU seminar announcements extraction task lt ties config gt lt bwi gt lt classifier gt lt extract gt lt entity gt lt wrapper gt bwi sa new out0 speaker xml lt wrapper gt lt output gt bwi sa res0 speaker xml lt output gt lt entity gt lt entity gt lt wrapper gt bwi sa new out0 location xml lt wrapper gt lt output gt bwi sa res0 location xml lt output gt lt entity gt lt extract gt lt classifier gt lt corpus loader gt lt corpus loader gt lt ties config gt 4 2 4 Ex cution du syst me TIES r
2. professor NN Word Punctuation SDS NNP Word Fig 19 Exemple d une r gle tiquetage taging rule Tang 2007 Les r gles d tiquetage sont induites de la fa on suivante tout d abord une tiquette du corpus d apprentissage est s lectionn e une fen tre de w mots gauche et w droite est prise en suivant le patron initial de la r gle Ensuite toutes les r gles initiales sont g n ralis es Par exemple en utilisant TAL les deux r gles at 4 pm et at 5 pm peuvent tre g n ralis es par at DIGIT pm Chaque r gle g n ralis e est test e dans le corpus d apprentissage et un score d erreur est calcul Finalement les meilleurs k g n ralisations pour chaque r gle initiale sont conserv s dans le groupe de meilleures r gles Cet algorithme est galement utilis pour induire les deux autres types de r gles La Fig 20 indique une r gle d tiquetage g n ralis e pour l identification du d limiteur initial de Speaker Des r gles contextuelles sont appliqu es pour am liorer la performance du syst me L id e principale est qu un tag pourrait tre utilis comme un indicateur de l apparition de tagy Consid rons par exemple une r gle qui reconnait un d limiteur final entre un mot avec une majuscule initiale et un mot avec toutes les lettres minuscules Cette r gle ne fait pas partie du groupe des meilleures r gles en raison de sa faible pr cision dans
3. O centro de Inform tica Vc Fo poe E Universidade Federal de Pernambuco P s Gradua o em Ci ncia da Computa o EXTRACTION D INFORMATION ADAPTATIVE DE PAGES WEB PAR INDUCTION SUPERVISEE D EXTRACTEURS Rinaldo Jos de Lima DISSERTATION DE MASTER Vv g A Universidade Federal de Pernambuco www cin ufpe br posgraduacao RECIFE AGOSTO DE 2009 ii UNIVERSIDADE FEDERAL DE PERNAMBUCO CENTRO DE INFORM TICA P S GRADUACAO EM CI NCIA DA COMPUTACAO Rinaldo Jos de Lima EXTRACTION D INFORMATION ADAPTATIVE DE PAGES WEB PAR INDUCTION SUPERVISEE D EXTRACTEURS Ce m moire a t pr sent au Programme de Post Graduation en Sciences de l Informatique du Centro de Inform tica de P Universidade Federal de Pernambuco comme exigence partielle pour l obtention du grade Master en Sciences specialit Informatique Directeurs Prof Frederico Luiz Gongalves Freitas Phd et Prof Bernard Espinasse Phd Prof Jacques Robin PhD Membre du Jury Prof Evandro de Barros Costa PhD Membre du Jury RECIFE JUNHO 2009 iii Lima Rinaldo Jos de Extraction d information adaptative de pages web par induction supervis e d extracteurs Rinaldo Jos de Lima Recife O Autor 2009 XX 89 p il fig tab Disserta o mestrado Universidade Federal de Pernambuco Cln Ci ncia da Computa o 2009 Inclui bibliografia e ap ndice 1 Intelig ncia artificial T tulo 006
4. L valuation globale d exactitude est prise comme la moyenne des pr cisions obtenues partir de chaque it ration Dans k fold cross validation les donn es initiales sont al atoirement divis es en k sous ensembles mutuellement exclusifs ou fold S S2 S chacun d une taille approximativement gale L apprentissage et test sont effectu s k fois Dans l it ration i le sous ensemble S est r serv comme l ensemble de test et les sous ensembles restants sont collectivement employ s pour faire apprendre le classificateur On d finit alors l estimation d exactitude comme le nombre global de classifications correctes de k it rations divis par le nombre total d instances pr sentes dans les donn es initiales Kohavi Kohavi 1995 d fend ce dernier m thode d valuation comme la meilleur parce qu elle fournit des estimations plus impartiales et avec une variance minimum Les exp riences de cette section ont t men es en prenant en compte les m thodes hold out ou k fold cross validation Macroaverage et Microaverage Pour chaque slot d information des r sultats sont valu s en comptant true positives tp slots correctes false positives fp slots incorrectes false negatives fn slots absents et en etle rappel R tp fp tp fn Pour un corpus contenant plusieurs slots d information extraire il y a diverses mani res de combiner les r sultats de toutes les slots en une seule mesure parmi elles on
5. valuation comparative Les exp riences d valuation comparative ont montr que le syst me M TIES est sup rieur d autres syst mes de l tat de l art sur le corpus plus structur Seminars et qu il atteint des score comparables sur le corpus semi structur Jobs En plus les extracteurs produits par le syst me propos ont la tendance atteindre plus de pr cision que les autres syst mes tout en tenant un rappel raisonnable La raison pour cette r ussite est que le systeme M TIES qui repose sur l algorithme BWI performe l extraction avec plus de pr cision car les r gles contextuelles apprises sont fortement pr cises mais il a galement un rappel raisonnable dans de nombreux domaines tant donn que des dizaines ou de centaines de r gles suffisent pour avoir un bon rappel En revanche m me avec l aide d tiquetage POS M TIES a obtenu un score inf rieur sur le corpus CFP en langage naturel Cependant tous ces r sultats ne font que confirmer exp rimentalement ce qu il tait pr vu pour cette recherche En effet l algorithme BWI emploie un formalisme de r gles plus expressif gr ce l utilisation de wildcards qui g n ralisent mieux que l algorithme LP par exemple sur des documents plus structur s Ce formalisme de r gles inclut un certain nombre de wildcards jokers qui contribuent radicalement aux r sultats exp rimentaux de l algorithme BWI apprend des r gles simples d extraction qui sont en grande parti
6. 57 6 Influence du nombre d it rations de boosting sur le corpus Jobs ssss 60 7 Influence de diff rentes features sur le corpora r sultats exprim s en F Measure 66 8 R sultats en F measure par slots du corpus ss 67 9 R sum de configuration des syst mes valu s sur le corpus SEMINARS 70 10 R sum de configuration des syst mes valu s sur le corpus JOBS 70 11 Perfomances par slot de 5 syst mes sur le corpus Seminars esee 71 12 Perfomances par slot de 4 syst mes sur le corpus Jobs en utilisant 71 13 Perfomance des syst mes sur le corpus CFP par slot en termes de 73 14 Comparaison entre les 4 syst mes sur le corpus CFP 76 xix XX 1 INTRODUCTION Une grande quantit d informations sur divers sujets en diff rents formats num riques sont de fa on croissante publi es sur le Web chaque jour Cette croissance a t stimul e par le progr s technologique en informatique simplifiant la production le stockage et la distribution de l information sur le Web Beaucoup de ces informations stock es de facon non structur e sont parpill es sur des milliers d ordinateurs individuels hosts constituant ainsi une complexe et immense base de donn es de port e mondiale Cela limite fortement l exploitation de ces informations et des techniques de navigation ou des recherche
7. SUPERVISEE D EXTRACTEURS Dans ce chapitre nous proposerons un syst me d EI adaptatif modulaire permettant l extraction d information de documents semi structur s ou libres Ce syst me reposant sur l induction supervis e d extracteurs est compos de divers modules permettant la pr paration d un ensemble d apprentissage annot manuellement par un utilisateur ensemble pouvant aussi int grer l tiquetage morphosyntaxique permettant le traitement de la syntaxe du langage naturel et un module r alisant l induction supervis e d extracteurs Pour ce dernier module le syst me TIES mettant lui m me en ceuvre l algorithme BWI a t retenu Il sera d taill dans la section 4 2 et modifi afin de pouvoir traiter l tiquetage morphosyntaxique Pour obtenir de meilleurs r sultats sur des collections de documents moins structur s il a fallu modifier l architecture de TIES pour qu il puisse traiter des documents en texte libre annot s par tiquetage morphosyntaxique fournie par une analyse de Parties du Discours Part of Speech Ainsi dans un premier temps nous pr senterons chacun des diff rents modules ou composants du syst me d EI propos Ensuite les nouveaux modules de l architecture de notre solution seront pr sent s le module d annotation de documents XHTML le module de validation des pages de corpora qui les transforme en fichiers XML bien form s et enfin le module en charge de l tiquetage morphosyntaxique POS
8. ce la fa on de l algorithme BWI qui peut voir le contenu du champ extraire 10 Voir les commentaires de la perfomance du M TIES sur le corpus Seminars 74 Corpus CFP 1 0 0 8 0 6 c o BB Amilcare A E Yaoyong 9 EJ SE oO CL M TIES 0 4 0 2 0 0 w nam w acro w dat w hom w loc w pap w not w cam c nam c acro c hom Slots Fig 45 Scores de Pr cision des syst mes par slot sur le corpus CFP Les figures 45 et 46 pr sentent respectivement la performance des syst mes en termes de la pr cision et du rappel pour les 4 syst mes comparer Comme le montrent ces r sultats les syst mes pr f rent d avoir plus de pr cision que de rappel Ce fait est probablement d aux syst mes d IE qui en g n ral sont destin s performer une extraction qui attribuent un co t plus lev aux faux positifs En effet on constate plus de variations dans le rappel que dans la pr cision pour tous les syst mes l exception de Yaoyong qui favorise le rappel Cela nous am ne une forte indication que ces syst mes poursuivent de diff rentes strat gies en termes de mesures de performance Enfin il faut aussi noter que l on peut seulement avoir un syst me d EI avec plus de rappel en d triment de la pr cision et vice versa L explication pour le plus bas rappel du M TIES pour le slot c hom home page de la conf rence Fig 46 c est que les liens de pages sont d coup en plusieurs tokens et la taille de seulement 3 toke
9. et DeLa Wang amp Locovsky 2002 sont des exemples de syst mes qui appartiennent cette approche En g n ral parmi les informations extraites par ces syst mes celles qui sont vraiment pertinentes sont souvent soumises un post traitement 2 5 Mesures d valuation de syst mes d EI Les mesures d valuation pour le probl me d EI sont apparues lors des conf rences MUC Message Understanding Conference Hirschman 1998 L tude men e par les quatre premi res MUC a servi de base la d finition des mesures d valuation existantes Initialement ces mesures ont t d velopp es en se fondant sur des mesures de pr cision et de rappel du domaine de la Recherche d Informations RI Cette section d crit la m thodologie d valuation de r sultats d une t che d EI Avant de montrer les mesures classiques d valuation des performances il faut pr ciser comment valuer la correction d une donn e extraite Plusieurs crit res sont envisageables pour d finir la correction d une donn e extraite dans le cas d extraction single slot 2 5 1 Crit res de correction Afin d valuer la correction d une s quence extraite 3 crit res sont applicables tous les types de documents repr sent s sous la forme d une s quence tokens Le premier crit re est le plus l che une donn e extraite est correcte si elle contient une partie d une donn e extraire Le second est un peu plus strict que le premier une donn e extrait
10. gt speaker lt token gt 65 type nl start 510 len 1 nl_token true gt n lt token gt 167 type word start 512 len 11 alpha_token true capitalized_token true gt Affiliation lt token gt 168 type punct start 523 len 1 punct_token true gt lt token gt 170 type word start 525 len 10 alpha_token true capitalized token true gt Department lt token gt Nous renvoyons le lecteur au guide d utilisateur de TIES ITC IRST 2004 pour en savoir plus 4 2 2 2 Feature Ex Les exemples sont d sur les tokens Ainsi dire un exemple est traction finis en termes d attributs qui sont les r sultats des fonctions appliqu es chaque token a une image f x qui sont des valeurs discr tes C est transform en une collection d attributs produisant ainsi un vecteur N dimensionnel Chaque token est trait comme un exemple de cette fa on on peut avoir un attribut capitalized qui associe un token l ensemble true false tant donn cet attribut nous pouvons exprimer de simples propositions sur un token sp cifique capitalized Home true et capitalized work false L impl mentation par d faut du tokeniseur du TIES encapsule un simple feature extractor de 12 attributs savo ir alpha token true pour des tokens qui contiennent seulement des caract res alphab tiques num token true pour un nombre perc token true pour d
11. lt title gt MUC Data Sets lt title gt lt META name description content Listing of the various datasets available for download gt lt META name keywords content Database database Information Extraction MUC muc MUC Proceedings MUC proceedings MUC Data Sets data sets information extraction SAIC Science Applications International Corporation lt head gt BODY BGCOLOR FFFFFF TEXT 000000 link 0033FF gt IMG SRC graphics blue bar gif width 721 height 10 gt lt P gt lt H1 gt MUC Data Sets lt H1 gt IMG SRC graphics blue_bar gif width 721 height 10 gt lt P gt For each evaluation ground truth had to be established to determine the reliability of the participating systems Datasets were typically prepared by human annotators for training dry run test and formal run test usage These datasets are now being made available wherever possible on this website lt body gt lt html gt Fig 5 Exemple d un document HTML 2 2 3 Documents structur s Depuis sa cr ation en 1998 par le W3C le format XML est devenu un standard pour l change et le stockage de donn es semi structur s On trouve pr sent divers genres de documents XML RDF diffusion de m tadonn es sur le Web MATHML langage d criture de formules math matiques ODF et DOCBOOK pour l dition de document et WSDL langage de description des interfaces de services Web etc Les documents XML ont une structure
12. sont optionnelles Cette t che pr liminaire d annotation de documents peut tre faite manuellement il ne faut qu annoter chaque slot d information trouv dans les documents du corpus Cependant pour cette recherche il est envisageable d automatiser cette t che d annotation car chaque fois que l on change de corpus ou de domaine il faudra annoter tous les documents du nouveau corpus En tenant en compte cette possibilit le syst me d annotation MnN d j pr sent dans la section 4 3 1 sera en charge de rendre cette t che moins fastidieuse 5 1 2 Corpus SEMINARS 5 1 2 1 Description du corpus Le corpus Seminars est constitu par une collection d annonces de conf rences prise des panneaux d affichage lectronique de l Universit Carnegie Mellon tats Unis pendant la p riode de septembre 1982 ao t 1995 et propos e par Freitag 1997 Cette collection comporte 485 documents aux mises en forme tr s diff rentes La figure suivante en illustre un exemple Name Dr Jeffrey D Hermes Affiliation Department of Autoimmune Diseases Research amp Biophysical Chemistry Merck Research Laboratories Title MHC Class II A Target for Specific Immunomodulation of the Immune Response Host e mail Robert Murphy murphy a cfr cmu edu Date Wednesday May 3 1995 Time 3 30 p m Place Mellon Institute Conference Room Sponsor MERCK RESEARCH LABORATORIES Professor John Skvoretz U of South Carolina Columbia wi
13. 0 940 0 940 0 959 0 959 0 959 location 0 547 0 562 0 753 0 723 0 715 0 703 speaker 0 513 0 775 0 844 0 912 0 907 0 922 67 Seminars F1 RR O etime w location A speaker 0 4 T T T T T 0 20 40 60 80 100 Documents Fig 43 Courbe d apprentissage sur le corpus Seminars En analysant la courbe d apprentissage de l algorithme on s aper oit qu en g n ral la performance de l algorithme augmente progressivement au fur et mesure que de nouveaux documents sont utilis s pour l apprentissage Plus particuli rement les slots de temps stime et etime sont les plus faciles tre g n ralis que les autres vu que le syst me peut les apprendre d s le premier ensemble de 10 documents En revanche pour le slot speaker il a fallu 60 documents pour atteindre un score proche de ceux des slots de temps De plus on note que juste apr s 60 documents la courbe se stabilise pour les slots stime etime et speaker Le gain est mineur partir de ce point sur la courbe On note aussi une l g re d gradation de performance pour le slot location apr s un nombre de 40 documents Cela signifie que l algorithme pr sente un probl me de sur apprentissage overfitting une r duction de son efficacit quand plus de documents sont utilis s pour l apprentissage 5 4 valuation comparative 5 4 1 Crit res d valuation recommand s La d finition d une m thodologie d valuation et la disp
14. 0 983 0 981 0 938 0 962 F1 0 720 0 626 0 964 0 850 0 983 0 586 0 874 0 975 0 883 0 873 1 000 0 881 0 830 0 884 0 882 0 975 0 698 Corpus JOBS Bl no POS EY with Pos app area city comp count d deg dye id lang plat p dt recr r deg ry e sal stat title Slots Fig 38 Comparaisons par slot de F measure avec et sans POS sur le corpus JOBS Corpus CFP R sultats par slot avec et sans POS Comme le montrent les Fig 39 et 40 le tagage POS a apport une l g re augmentation sur la F measure pour la majorit des slots Par exemple le slot confacro conference acronym a pr sent le gain de plus de 596 Le plus bas r sultat de l algorithme en consid rant tous les slots individuellement a t celui du slot confhome conference homepage On peut expliquer ce score cause du nombre moins repr sentatif 100 d exemples dans le corpus tout entier De plus on a constat que le module responsable pour la tokenisation de documents du M TIES ne reconnais pas les adresses lectronique comme une entit Une possibilit d avoir meilleurs r sultats pour ce type de slot serait de permettre le tokeniseur pour le reconnaitre en augmentant la taille de la fen tre w par exemple 64 Slot Pr c Rappel F1 Slot Pr c Rappel F1 confacro 0 935 0 386 0 547 confacro 0 930 0 442 0 600 confhome 0 745 0 143 0 240 confhome 0 717 0 122 0 208 confname 0 969 0 683 0 801 confname 0 951 0 685 0 796 workacro 0 902 0 2
15. 2003 AKT 2009 MnmMnM Ontology Driven Semi Automatic and Automatic Support for Semantic Web Mnm Developer Guide Disponible http projects kmi open ac uk ak MnM MnM Developer Guide html dernier acc s en juin 2009 Apache 2009 JFex java Feature Extractor User Guide Disponible http tcc itc it research textec tools resources jfex quickstart html dernier acc s en juin 2009 Arasu 2003 Arasu A Garcia Molina H Extracting structured data from web pages In Proceedings of internation conference on Management of data pp 33 348 2003 Baumgartner et al 2001 Baumgartner R Flesca S Gottlob G Visual web information extraction with Lixto In 28th International Conference on VLDB pp 119 128 2001 Bray et al 2008 Bray T Paoli J Sperberg McQueen C Maler E Yergeau F Extensible Markup Language XML 1 0 Fifth Edition In W3C Recommendation November 2008 Brill 1992 Brill E A simple rule based part of speech tagger In Proceedings Of the 3th conference on Applied NLP pp 152 155 Association for Computational Linguistics 1992 Cabral 2004 Cabral D M Um framework para extra o de informa es uma abordagem baseada em XML Disserta o de Mestrado UFPE CIN Recife 2005 Califf 1998 Califf M E Relational Learning Techniques for Natural Language Information Extraction Ph D Dissertation University of Texas at Austin 1998 Califf amp Mooney 1999 Califf M E
16. CONFIG XML Dans ce fichier lt ties config gt est l l ment principal Il est constitu de plusieurs balises d crivant les modules du TIES pour tape de g n ration d un mod le strat gie de validation strat gie d extraction weak learner boosting tokeniseur et corpus loader Les directives de contr le d entr e et de sortie sont aussi mises dans ce fichier de configuration ainsi que la m moire cache essentielle pour optimiser les performances du syst me et l utilisation de la m moire Ci dessous on voit un extrait du fichier de configuration TIES CONFIG XML relatif au corpus CMU Seminar announcements Le manuel d utilisateur ITC IRST 2004 d crit en d tail la signification de tous les param tres d finis par ce fichier Configuration file for the standard CMU seminar announcements extraction task lt ties config gt lt validation strategy gt validation class gt org itc irst tcc ties validation NFoldCrossValidation lt validation class gt lt init param gt lt param name gt n lt param name gt lt param value gt 10 lt param value gt lt init param gt lt init param gt lt param name gt hypothesis file lt param name gt lt param value gt bwi sa out xml lt param value gt lt init param gt lt init param gt lt param name gt eval file lt param name gt lt param value gt bwi sa bwi eval csv lt param value gt lt init param gt lt validation strategy gt lt ties config gt
17. Classification Supervis e D apr s Mitchell Mitchell 1997 classer un objet consiste l affecter au groupe auquel il appartient Autrement dit on associe un objet une classe La classification supervis e consiste alors dans l apprentissage de cette association objet classe partir d objets dont la classe est d j connue Le mod le d apprentissage de la classification supervis e pr sume l existence d un concept cible f que l on cherche d couvrir partir d un ensemble d exemples d j class s Le concept cible f peut tre vu comme une fonction de l ensemble d exemples vers l ensemble 22 de classes Dans ce contexte l apprentissage se produit quand on s approche le plus possible de f par une fonction hypoth se h La fonction h r sultante pourra tre utilis e pour pr dire la classe d exemples dont la classe est inconnue Marty 2007 Soit le probl me de classification sur deux classes classification binaire Soit y x y un ensemble de donn es d apprentissage dans lequel x d note une instance un vecteur d attributs et y e Y 1 1 d note une tiquette de classification L ensemble X constitu par x x x est aussi nomm e de l espace de description des exemples tandis que Y est l ensemble de classes possibles chaque exemple on associe sa description xe X et sa classe ye Y Chaque couple x y est un exemple tiquet et l ensemble de tous les couples constitue l ensemble d
18. Intelligence 14 5 771 780 September 1999 Friedmann Hill 2000 Friedmann Hill E Jess The Java Expert System Shell 2000 Disponible http herzberg ca sandia gov Jess dernier acc s en juin 2009 Gilleron et al 2006 Gilleron R Marty P Tommasi M Torre F Extraction de relations from semi structured data In Revue RNTI Actes de EGC 06 pages 415 420 2006 Girardi 2007 Girardi C HtmlCleaner Extracting Relevant Text from Web Pages In Proceedings of WAC3 2007 3rd Web as Corpus Workshop Louvain la Neuve Belgium September 15 16 2007 Giuliano et al 2006 Giuliano C Lavelli A Romano L Simple Information Extraction SIE A Portable and Effective IE System In Proceedings of the EACL 06 Workshop on Adaptive Text Extraction and Mining ATEM 2006 Trento Italy 2006 Gliozzo et al 2005 Gliozzo A M Giuliano C Rinaldi R Instance pruning by filtering uninformative words an Information Extraction case study In Proceedings of the Sixth International Conference on Intelligent Text Processing and Computational Linguistics CICLing 2005 Mexico City Mexico 13 19 February 2005 Hirschman 1998 Hirschman L The evolution of evaluation Lessons from the Message Understanding Conferences Computer Speech and Language 12 pp 281 305 1998 Hsu 1998 Hsu C N Dung M Generating finite state transducers for semi structured data extraction from the web Journal of Information Systems 23 8 52
19. Mooney R J Relational learning of pattern match rules for information extraction In Proceedings of the Sixteenth National Conference on Artificial Intelligence AA AI 99 pp 328 334 1999 Callif et al 2004 Califf M E Ciravegna F Freitag D Giuliano C Kushmerick N Lavelli A Romano A critical survey of the methodology for IE evaluation In Proceedings of LREC 2004 82 Chang amp Lui 2001 Chang C H Lui S C IEPAD Information extraction based on pattern discovery Proceedings of the Tenth International Conference on World Wide Web WWW Hong Kong pp 223 231 2001 Chang amp Kuo 2004 Chang C H Kuo S C OLERA A semi supervised approach for Web data extraction with visual support IEEE Intelligent Systems 19 6 56 64 2004 Chang et al 2006 Chang C H Kayed M Girgis M R Shaalan K F A Survey of Web Information Extraction Systems IEEE Trans Knowl Data Eng 18 10 1411 1428 2006 Ciravegna 2001 Ciravegna F LP An adaptive algorithm for information extraction from web related texts In Proceedings of the IJCAI 2001 Workshop on Adaptive Text Extraction and Mining held in conjunction with the 17th International Joint Conference on Artificial Intelligence 2001 Seattle 2001 Ciravegna amp Lavelli 2001 Ciravegna F Lavelli A LearningPinocchio Adaptive information extraction for real world applications In Proceedings of 3rd Romand Workshop Frascati Italy 2001 Cirave
20. algorithme LP sur les autres r side dans l effet combin de l tape d tiquetage contextuel de l tape de correction et de l utilisation plus avanc e d information TAL Ce dernier tant le plus important d entre eux 6 2 Perspectives relatives au syst me d EI propos Plusieurs travaux pour tendre la version actuelle du syst me d EI propos dans cette recherche peuvent tre envisag s court et moyen terme En voici quelques uns 1 Extraction d information partir de documents en format PDF Le syst me M TIES ne traite que des documents en format HTML XHTML Cependant le format PDF devient de plus en plus utilis sur Web comme un format standard pour une gamme de documents Ainsi il est envisag d avoir un module capable d extraire des informations de tel type de document 2 S paration des modules tokeniseur et extracteur d attributs Il a t constat que dans M TIES les modules tokeniseur et d extraction d attributs sont fortement li s entre eux Pour avoir plus de flexibilit et cons quemment rendre ce syst me plus adaptatif l apprentissage sur de nouveaux corpus en fournissant diff rents types de tokeniseur et ou extracteur d attributs par exemple un travail de r ing nierie sur les codes source de M TIES devrait tre r alis 3 Ajoutement d un module de Normalisation Il est tr s fr quent d avoir certains type d information tels que adresses de courrier lectronique URL de home pag
21. alise deux t ches diff rentes la t che d apprentissage test et celle d extraction Les tapes suivre pour ces t ches sont pr sent es ici d une fa on algorithmique 1 Apprentissage test 1 Instancier un algorithme d EI Sp cifier un corpus d entr e Choisir une strat gie de validation Choisir une strat gie d extraction Apprendre un mod le Tester le mod le appris DNA Meo EN 2 Extraction 1 Sp cifier un nouveau corpus d entr e 2 Ex cuter un classificateur utilisant le mod le appris Pour l instant TIES ne disposant pas d une interface conviviale de param trage tous les param tres de configuration doivent tre saisis d une des fa ons suivantes invite de 45 commande configuration XML ou API Le lecteur est renvoy au ITC IRST 2004 pour savoir comment ajuster pr cis ment les param tres de configuration 4 2 5 R gles induites et information extraites 4 2 5 1 R gles induites Les r gles induites par TIES sont exprim es par des wrappers essentiellement form s par un pr fixe suivi de l information extraire et se terminant par un suffixe En fait une r gle d termine un pattern patron de tokens dans le corpus d entr e qui entoure le slot d information extraire Les wrappers appris sont stock s en format XML et ils pourront tre employ s plus tard pendant une t che d extraction La Fig 25 montre un extrait d un wrapper appris pour le slot lt speaker gt du corpus CMU Seminar a
22. arborescente traduite par l imbrication des balises qui d crit la fois la structure logique du document et son contenu Les n uds internes ou les l ments de l arbre repr sentant un document XML correspondent aux l ments de sa structure logique tandis que son contenu est stock dans les feuilles de l arbre Par exemple le document XML de la Fig 6 contient les l ments catalog cd title artist country company et year Chaque l ment est repr sent par une paire de balises ouvrante fermante Dans cette figure l l ment title est repr sent par les balises titre et lt titre gt Pour tre bien form toute balise ouverte doit tre ferm e et les balises fermantes apparaissent dans l ordre inverse des balises ouvrantes cette contrainte n est pas obligatoire dans le cas HTML A la diff rence d HTML o l ensemble des balises est d fini par une norme fix e XML permet de cr er l ensemble des balises utilis es On peut ainsi cr er sa propre variante en fonction de ses besoins en d crivant la fois les balises et la s mantique qui leur est associ e 12 l aide d un sch ma DTD Document Type Definition ou un sch ma XML qui d termine l ensemble de balisage con u et cons quemment la fa on dont elles sont structur es on peut contraindre la structure arborescence des documents XML et les types de donn es qui y figurent lt xml versionz 1 0 encoding utf 8 gt CATALOG
23. certains slots Par contre pour les autres deux corpora plus structur la 78 diff rence a t pratiquement nulle Ceci peut s expliquer par le fait que l algorithme d induction d extracteurs a d j de tr s bonnes performances sans se servir d un espace d hypoth ses plus large avec la prise en compte de l information POS quand il est employ sur de documents plus structur s corpus Seminars et Jobs En plus il y a eu le cas o un slot avait un score parfait Concernant les exp riences sur l valuation comparative elles ont montr que l architecture d velopp dans cette recherche est sup rieure d autres syst mes d EI de l tat de l art sur le corpus plus structur Seminars et qu elle atteint des scores comparables sur le corpus semi structur Jobs En plus les extracteurs produits par le syst me propos semblent atteindre plus de pr cision que les autres syst mes tout en ayant un rappel raisonnable En revanche m me avec l aide du tagage POS le syst me propos a obtenu un score inf rieur par rapport aux autres syst mes compar s notamment LP sur le corpus CFP en langage naturel Dans M TIES l algorithme BWI utilise un formalisme de r gles plus expressif gr ce l utilisation de wildcards qui g n ralise mieux que l algorithme LP par exemple sur des documents plus structur s Pour une collection de document moins structur s notamment en langage naturel on peut conclure que l avantage de l
24. des documents semi structur s et libres format XHTML Cette approche retenue n cessite la connaissance d exemples de donn es extraire et une annotation de ces exemples d apprentissage r alis e par l utilisateur Afin que la t che d annotation ne soit pas fastidieuse l apprentissage permettant l induction de l extracteur doit pouvoir tre fait partir de peu d exemples La section suivante traitera plus en d tail l induction supervis e d extracteurs 21 3 INDUCTION D EXTRACTEURS ET CLASSIFICATION SUPERVISEE Le domaine de l apprentissage artificiel qui rel ve de l intelligence artificielle propose de nombreux algorithmes dont les propri t s ont d j t bien tablies Cornu jols amp Miclet 2002 Mitchell 1997 Russel amp Norwig 2003 Parmi les diverses techniques d apprentissage artificiel appliqu es l induction d extracteurs d information ce chapitre s int resse aux techniques relevant de la Classification Supervis e CS Dans un probl me de la CS des exemples convenablement tiquet s sont fournis l lgorithme d apprentissage Les tiquettes indiquent les classes auxquelles les exemples appartiennent Pour le cas deux classes cas binaire chaque exemple peut tre soit positif soit n gatif partir de ces exemples il faut alors d apprendre un classificateur capable de pr dire la classe d un exemple On peut se servir de la CS pour concevoir un syst me d EI constitu de deux phases a
25. des slot annot s Ireson amp Ciravegna 2005 ANNOTATION TYPE CORPUS FREQUENCY ma a La La Tab 5 pr sente la distribution de fr quences des slots annot s dans le deux premiers corpus apprentissage et test comme on peut bien constater les deux distributions sont peu pr s semblables Il faut noter que comme ni tous les workshops ont une conf rence qui leurs sont associ es les slots moins repr sentatifs sont les slots relatifs aux conf rences 57 5 1 5 Comparaison et sp cificit s des Corpora Un syst me d EI adaptatif doit s adapter un nouveau domaine ou application avec un minimum d effort Du point de vue de l algorithme d apprentissage un tel syst me est n cessaire pour apprendre un premier mod le partir d un petit nombre d exemples d apprentissage Dans ce contexte afin d valuer le syst me M TIES dans un sc nario d TE adaptatif on value son algorithme d apprentissage qui sera d taill dans le chapitre suivant sur 3 corpora d j annot s avec diff rents degr s de structuration pouvant tre class s en 2 groupes partiellement structur et naturel non structur Les documents partiellement structur s des corpora Seminars et Jobs contiennent des structures au niveau de document et des r gularit s dans la mise en forme et dans les annotations Par exemple il est commun pour quelques slots d tre pr c d s d une tiquette d identification ex Speaker Dr X bien q
26. elles soient gales 1 si et seulement si ils sont des s parateurs de d but et de fin d une donn e extraire pr sent dans le document sinon elles sont gales 0 Les exemples positifs sont ainsi codifi s d une mani re tr s simple et identique pour les positions de d buts et fins Chacune de ces positions est repr sent e par deux ensembles l ensemble des tokens se trouvant sa gauche et celui se trouvant sa droite 3 1 4 2 Hypoth ses Les hypoth ses destin es caract riser les s parateurs repr sent s par les exemples positifs sont exprim es par des r gles ou des classificateurs l mentaires qui prennent en entr e un s parateur et d termine s il s agit ou non d un s parateur d but ou fin selon les tokens gt La repr sentation attribut valeur consiste d appliquer des fonctions sur les tokens et de leurs attacher les r sultats de ces fonctions les atributs avec leurs valeurs correpondantes Par exemple une fonction f appliqu au token peut renvoie symbol token true 25 pr sents gauche et droite Une r gle est alors constitu e d une s quence de tokens ou de jokers wildcards ces derniers tant la conversion d un token une cat gorie plus g n rale En fait cela rend les d tecteurs plus g n raux Ainsi au lieu de chercher des correspondances des tokens exactes des d tecteurs dans un texte les jokers correspondent plusieurs tokens en m me temps Ci apr s
27. elles sont consid r es comme semi structur es puisque les donn es incluses sont souvent r cup r es gr ce l utilisation de balises HTML La figure suivante montre un aper u de divers types de documents en consid rant les dimensions niveaux de structuration et facilit de traitement par la machine o o a 3 Database D XML 3 Cgi generated HTML 9 Hand written HTML B E Postings on newsgroup D e g apartment rentals Equipment maintenance logs g medical records Free texts E e g News articles e 3 Hard to understand by machine Easy to maintain by machine Fig 7 Structuration de documents selon Chang 2006 2 3 Concepts de base en EI Cette section discute deux concepts de bases relatifs la t che d EL a savoir la repr sentation de documents et les types de sorties 2 3 1 Repr sentation de documents A fin de pr ciser la fa on de repr senter des documents semi structur s dans le contexte d une t che d EI typique deux repr sentations sont alors possibles la repr sentation par une s quence et par un arbre 14 2 3 1 1 Repr sentation par une s quence Cette repr sentation de documents sous la forme d une s quence d unit s lexicales ou tokens est la plus courante en EI Elle est obtenue partir du code source de la page Quant l atomicit un token peut se pr senter sous un aspect seulement syntaxique ou avoir aussi un aspect s mantique dans le premier cas des tokens caract
28. en fait des s parateurs de d but ou de fin d une donn e quelconque extraire sinon ces fonctions sont gales 0 Par exemple la s quence Time 9 PM contient cinq s parateurs qui sont illustr es respectivement par so 51 52 53 54 et ss Fig 13 t Time T T 9 T PM 0 1 9 3 on e Fig 13 S quence de tokens avec des s parateurs Marty amp Torre 2004 S2 et s4 sont des s parateurs de d but et fin respectivement Supposons que l on veut extraire la donn e 9 PM de l exemple pr sent dans la figure ci dessus alors s2 et s4 seront respectivement le s parateur de d but et de fin de cette donn e et les autres des s parateurs quelconques Apr s avoir choisi la description de l ensemble d exemples il reste d finir un langage d hypoth ses et choisir un algorithme de classification supervis e permettant de trouver dans l espace d hypoth ses l hypoth se qui sera la plus coh rente avec les exemples disponibles Ensuite une hypoth se tant apprise il faut sp cifier le wrapper correspondant Enfin une tape post rieure se fait n cessaire pour que l on r associe les s parateurs de d but et de fin Dans la section suivante afin d illustrer la transformation du probl me d EI en un probl me de classification supervis e nous d crivons le syst me BWI qui r alise l extraction single slot partir de documents non structur s et qui faire l usage de s parateurs ind pendants
29. fixe speaker suivi d un token form par un seul caract re et n importe quel suffixe 4 2 5 2 Information extraites Les entit s extraites d un nouveau corpus sont aussi stock s en format XML La figure suivante montre ces entit s avec l endroit exact au millier de documents indiqu s par les balises entity et ses attributs name src lt entity list gt entity name speaker src CMUAN token start 142 len 3 gt Mr lt to token start 146 len 5 gt Okada lt entity entity name speaker src CMUAN lt token start 330 len 3 gt Dr lt to token start 334 token start 344 len 4 gt Shaw lt t entity entity name speaker src CMUAN token start 624 len 3 gt Mr lt to token start 628 len 6 gt Andrew lt token start 635 len 5 gt Gault lt entity entity name speaker src CMUAN token start 810 len 3 gt Mr lt to token start 814 len 6 gt Jessie lt token start 821 len 5 gt Ramey lt entity entity name speaker src CMUAN lt token start 880 len 3 gt Dr lt to token start 884 len 4 gt gudi lt t token start 889 len 7 gt Mancuso lt token gt entity lt entity list gt 3G DER ken gt token gt EU ACE ken gt oken gt G2 CAR ken token token G2 CAR ken token token G2 CAR ken oken gt start 142 st
30. gt lt b gt Reviewer Name lt b gt Jane lt b gt Rating lt b gt 6 lt b gt Text lt b gt lt li gt lt ol gt lt body gt lt html gt Fig 8 Rendu d une page HTML adapt de Chang et al 2006 15 html body 3 E JU S S gt 5 ANN Z i 2 S 3 AN LS 3 beh 2b4 be b6 be Al ISTE 3 Reviewer D 2 Reviewer 2 q Name Ei A Name 2 3 amp a 7 Fig 9 Repr sentation arborescente DOM Tree de la page HTML de la Fig 8 Chang et al 2006 2 3 2 Types de Sorties En ce qui concerne la sortie un syst me d EI peut tre single slot unaire multi slot n aire ou structur e Sortie single slot unaire Les syst mes d EI single slot ou unaire extraient du document d entr e seulement des donn es isol es c est dire ils ne sont pas capables de lier une instance d un champ d information slot du formulaire de sortie une instance d autre champ Sortie multi slot n aire Ceux ci sont capables d extraire du document d entr e des donn es li es les unes aux autres c est dire ils peuvent faire des relations entre les instances de diff rents slots La Fig 10 illustre ce deux types de sorties 16 Capitol Hill 1 br twnhme fplc D W W D Undrgrnd pkg incl 675 3 BR upper flr of turn of ctry HOME incl gar grt N Hill loc 995 206 999 9999 lt br gt i font size 2 gt This ad last ran on 08 03 97 lt font gt lt i gt hr Singl
31. jusqu ce qu il soit trouv e la premi re occurrence de B et extraire le nom du pays comme une cha ne qui se termine par le premier lt B gt Ensuite ignorer tous les caract res jusqu ce que soit trouv lt I gt et extraire la chaine qui se termine par lt I gt Afin d extraire des informations sur Country et Area Code la r gle est appliqu e de fa on r p t e jusqu ce 1 30 qu elle ne s applique plus De cet exemple on note qu une r gle de WIEN peut tre appliqu e avec succ s sur les deux documents D et D2 Cependant WIEM pr sente certaines limitations qui ont t soulign es par Hsu 1998 Tout d abord une premi re limitation est li e au fait que WIEN fait une hypoth se forte sur l organisation des tuples dans les documents les tuples sont cons cutifs et leurs composantes sont obligatoirement dans le m me ordre Cette hypoth se est v rifi e lorsque les donn es extraire sont pr sent es dans une table car l ordre des colonnes est naturellement fixe et identique dans toute la table Cependant elle n est plus n cessairement lorsque les n uplets sont dans une liste dans laquelle l ordre des composantes peut changer d un tuple l autre Ensuite une autre limitation est que dans WIEN les valeurs manquantes ne sont pas g r es convenablement en extraction Ainsi l induction d un extracteur est tout simplement impossible lorsque les documents contiennent des tuples dont certai
32. l efficacit d extracteurs con us avant de conclure 2 1 Traitement Automatique de la Langue TAL L objectif du Traitement Automatique des Langues TAL est la conception de logiciels capables de traiter de facon automatique des donn es exprim es dans une langue dite naturelle par opposition aux langages formels de la logique math matique Ces donn es linguistiques peuvent selon le cas tre de diff rents types textes crits ou oraux et de taille variable du texte entier au mot isol en passant par la phrase ou le syntagme Selon la nature de l application le traitement peut viser transformer des donn es linguistiques existantes des fins de correction d extraction d information de traduction etc Actuellement nous avons un r el et croissant besoin de disposer d outils et de m thodes robustes pour traiter la langue sous toutes ses formes requ tes documentaires moteurs de recherche extraction d information pr cises correction orthographiques fouille de donn es textuelles etc Les proc dures d valuation d velopp es initialement en RI dans le cadre des comp titions internationales en EI et en RI Message Understanding Conference MUC Hirschman 1998 ont t g n ralis es d autres domaines Reconnaissance d Entit s Nomm es Named Entity Recognition c est dire des noms de personnes d intuitions de lieux tiquetage morphosyntaxique POS Tagging Adda et al 1999 pour en citer que
33. la classification de s parateurs fin cy et 3 la r association de chaque s parateur class comme d but un s parateur class e comme fin l aide d un histogramme ha Les classificateurs cy et cy constitu s par des classificateurs l mentaires combin s par la technique du boosting sont appliqu s sur tous les s parateurs candidats des documents d entr e Cela correspond aux tapes 1 et 2 que l on vient de mentionner On obtient ce point de l extraction deux ensembles des s parateurs class s comme s parateurs d but et s parateurs fins not s respectivement D et F Freitag galement d finit D et F comme des ensembles de d tecteurs Freitag amp Kushmerick 2000 Un d tecteur est une paire de s quences de tokens lt p s gt Un d tecteur s assortit un s parateur dans le document si et seulement si le pr fixe de la s quence de tokens p correspond des tokens avant le s parateur et le suffixe de la s quence de tokens s correspond des tokens apr s le s parateur Par exemple le d tecteur Who Dr peut s assortir au fragment de texte Who Dr John Smith d finissant le s parateur entre et Dr Dans ce contexte soient des d tecteurs de d but et fin l extraction est r alis e en identifiant le d but et la fin d un champ et en prenant les tokens entre ces deux points La figure suivante illustre un exemple d un wrapper avec ses d tecteurs D et F appris Un exemple Deux
34. las Le n 41 422 1 TokenisatiOm iuin ee ee de b e dete edi Eae i pe n dd cede 42 22 2 Feature Extract n Ans ne uot orbes mt Quentin ondes 43 42 3 X onB guration du systeme TES inei abe D He ei 44 4 2 3 1 tape d apprentissage g n ration d un mod le 44 4 2 3 2 Etape d application de r gles extraction 45 42 4 Ex cution du Systeme sinistre e eee PUE Eee eR sponse 45 4 2 5 R gles induites et information extraites 4 46 4 250 HROSI S QUES Mn URI pam la Di Nain ins 46 AD 2 Information OX ALES shoes oti de eds sn EE ha sa 47 4 3 M TIES nouvelle version de TIES tendue l annotation morphosyntaxique 48 4 3 1 Am lioration du pr ttalte meh sense err he Par Aa QUA a 49 4 3 1 1 Module d annotation de documents MnM see 49 4 3 1 2 Module de Nettoyage de pages HTML HTML Cleaner 49 4 3 2 Extension du module de tokenisation par l ajout de tagage POS 50 4 3 2 Module d tiquetage morphosyntaxique POS tagging QTag 50 4 3 3 G n ration de diagrammes de classes 2 ees dtet deis cei passada eti od eoe qup Spo Pega SD 51 4 3 4 Decompilation de code SOUlCE x none ue tn at SR TS entr 51 43 5 Sortie de r sultats en format CSV 5256 ne A ML tie ads ede doped odas 51 Ad SCOUTS OM aod iu toto t o e ca toon ute Tan rss 52 5 EXPERIMENTA TIONS nicetttioti trae nd nm eR Oo s entr ERN ner Ne 53 S L Co
35. ou XML La deuxi me version du TIES d crite dans ce m moire utilise tagage POS section 4 3 37 La transformation d un probl me d extraction en un probl me de classification supervis e n cessite que l on sp cifie la repr sentation de documents la d finition des l ments de documents qui seront consid r s comme les exemples du probl me de classification et le codage de ces exemples En tudiant en d tail un syst me d induction d extracteurs reposant sur la classification supervis e BWT il a t illustr les diff rentes tapes l mentaires associ es une telle transformation Ensuite diff rents syst mes d EI par induction supervis e d extracteurs ont t pr sent s notamment les syst mes WIEN SoftMealy STALKER Almicare SIE et TIES Ces diff rents syst mes presque tous adoptent une repr sentation de document base de tokens font de l extraction unaire mettent en uvre diff rents algorithmes d apprentissage pour traiter des textes semi structur s voire libre pour certains de ces syst mes SIE TIES Amilcare Dans le chapitre suivant ce travail propose un syst me d EI adaptatif modulaire permettant l extraction d information de documents semi structur s ou libres reposant sur l induction supervis e d extracteurs et int grant le syst me TIES mettant lui m me en uvre l algorithme BWI 7 Bri vement pr sent dans la section 3 3 6 38 4 UN SYSTEME D EI ADAPTATIF PAR INDUCTION
36. peut mentionner les mesures micro average et macro average La mesure micro average est calcul e en additionnant les tp fp et fn pour tous les slots et en calculant ensuite P R et F Par cons quent des slots plus fr quents ont un impact plus lev sur la mesure finale que des slots rares D autre part la mesure macro average est calcul e en faisant la moyenne de toutes les valeurs P et R par slots de sorte que toutes les slots sont consid r s comme d gale importance peu important combien de fois ils se produisent Certains chercheurs soutiennent que la mesure macro average est meilleure que la micro average Yang amp Liu 1999 parce que la derni re peut tre domin e par les classes plus nombreuses de telle fa on qu elle exprime moins la performance de l algorithme sur les classes moins repr sentatives D autre part si toutes les classes sont d une taille comparable comme c est souvent le cas de corpora en EI alors la mesure macro average n est pas tr s diff rente de la micro average calculantla pr cision P 59 Dans ce chapitre la performance globale du syst me propos sur un corpus quelconque est mesur e en termes de F Measure micro et macro avec le param tre B 1 5 3 Exp riences Les r sultats exp rimentaux sur trois corpora d crits dans la section 5 sont pr sent s Toutes les exp riences ont t men es avec le syst me M TIES Pour chaque exp rience les respectifs param tres utilis s p
37. pr senter aucun En outre Eikvil 1999 d clare que les syst mes d EI n essayent pas de comprendre le texte dans les documents d entr e mais plut t d analyser des portions de chaque document qui contiennent des informations pertinentes La pertinence est d termin e par des sch mas pr d finis du domaine qui sp cifient quel type d information le syst me s attend trouver Ces d finitions sont tr s g n rales car elles ne sp cifient ni le type des documents d entr e ni la nature des l ments extraits En revanche Florescu et al 1998 propose une d finition plus pr cise et focalis e sur Web o les pages d un site Web sont consid r es comme des conteneurs de donn es Alors l EI consiste produire une repr sentation structur e de ces donn es La d finition trouv e en Cohen et al 2003 est galement sp cifique au Web et appui lEI sur l usage d extracteurs Un extracteur est d fini comme tant un programme qui permet de voir un site Web existant comme une base de donn es Cette derni re d finition est plus sp cifique que les autres tant au niveau du type des documents d entr e ici limit s aux pages Web qu au niveau du type de la sortie une base de donn es En comparant toutes les d finitions voqu es ci dessus on distingue 3 caract ristiques majeures partag es 1 l EI a comme entr e un ensemble de documents d un certain type 2 tels documents contiennent des informations ou donn es que l
38. repr sentation de tokens sous la forme attribut valeur reposant sur des informations de base et sur des ressources simples associ a un algorithme de classification supervis e classique comme le BWI permet d induire des wrappers ayant performants Les prochaines sections d tailleront l algorithme BWI en exposant sa mani re de repr senter les documents ses algorithmes d apprentissage et d extraction aussi bien que ses avantages et limitations 3 1 4 1 Repr sentation de documents et d exemples Dans BWI un document est vu comme une s quence d unit s lexicales ou tokens On distingue trois types de tokens une s quence de caract res alphanum riques un caract re de ponctuation et enfin le caract re de retour chariot Notons que pour repr senter des exemples positifs BWI emploie la notation de s parateur tudi dans la section pr c dente En effet un s parateur est soit une interposition entre deux tokens adjacents soit la position avant respectivement apr s le premier respectivement dernier token d une valeur extraire Cons quemment une donn e extraire est une sous s quence de la s quence de tokens repr sentant le document et elle est caract ris e par un couple de positions d but fin qui d limitent la s quence de tokens correspondante cette donn e De plus il faut faire apprendre deux classificateurs c est dire deux fonctions de s paration sur 0 1 On restreint ces fonctions pour qu
39. s sur les corpora Seminars et Jobs et avec k 2 4 sur le corpus CFP 62 Corpus SEMINARS R sultats par slot avec et sans POS Slot Pr c Rappel stime 0 985 0 979 etime 0 989 0 969 location 0 961 0 912 speaker 0 962 0 944 a sans POS Fig 36 R sultats sur le Corpus Seminars sans a et avec b POS F1 0 982 0 979 0 936 0 953 Slot stime etime location speaker Corpus JOBS R sultats par slot avec et sans POS Slots application area city company country des degree des y exp id language plataform post date recruiter req degree req y exp salary state title Pr c 0 903 0 848 0 993 0 943 0 998 0 922 0 942 1 000 0 934 0 957 1 000 0 976 0 915 0 932 0 920 0 995 0 855 Rappel 0 618 0 491 0 944 0 759 0 974 0 379 0 835 0 956 0 840 0 802 1 000 0 774 0 805 0 806 0 854 0 963 0 582 a F1 0 734 0 622 0 968 0 841 0 986 0 537 0 885 0 977 0 885 0 872 1 000 0 864 0 857 0 864 0 886 0 979 0 693 Slots application area city company country des degree des y exp id language plataform post date recruiter req degree req y exp salary state title Pr c 0 984 0 988 0 953 0 960 Rappel 0 983 0 974 0 924 0 965 b avec POS Pr c Rappel 0 599 0 502 0 941 0 772 0 966 0 432 0 856 0 952 0 841 0 807 1 000 0 797 0 767 0 842 0 870 0 960 0 601 Fig 37 R sultats sur le Corpus Jobs sans a et avec b POS 63 F1
40. tiqueteurs POS mais il est assez robuste en tiquetant des textes avec une pr cision lev e Il y a deux fa ons d utiliser le QTag soit en tant que logiciel lorsqu on pr pare les textes et puis on ex cute le QTAG l dessus ou int gr en tant que module travers une API dans nos propres programme 50 QTAG est impl ment en Java ce qui signifie qu il fonctionne sur plusieurs syst mes d exploitions Il est en principe ind pendant de la langue bien que la version actuelle ne vient qu avec des fichiers de ressources pour l anglais Si on a besoin de l utiliser avec d autres langues on devra avoir un ensemble pr tiquet de texte pour cr er les ressources n cessaires Le logiciel pour cr er ces ressources est aussi inclus dans le package de distribution sur le site QTag 2008 Dans cette recherche QTAG est utilis comme module d tiquetage morphosyntaxique a fin d tiqueter automatiquement des documents avec un ensemble d tiquettes POS qui est list avec leurs significations dans l appendice A 4 3 3 G n ration de diagrammes de classes Le guide utilisateur du system TIES est consid rablement r sum De plus sa documentation concernent l API Application Program Interface est tr s l g re Aussi il a t n cessaire d utiliser un outil de retro ing nierie reverse engineering pour obtenir partir du code source de TIES les diagrammes de classes de tous les package du syst me 4 3 4 D com
41. tokens et les sous s quences extraire sont marqu es t che d annotation Ce que nous am ne choisir comment repr senter pr cis ment un exemple particulier On peut le repr senter soit comme une sous s quence Kosala amp Blockeel 2000 ventuellement r duite un seul token Seymore et al 1999 Freitag amp McCallum 1999 Giuliano et al 2006 soit comme un s parateur de d but ou de fin d une donn e extraire Freitag amp Kushmerick 2000 dans ce cas l apprentissage des s parateurs de d buts et des fins sera effectu ind pendamment Dans ce qui suit on met en vidence l apprentissage de s parateurs 3 1 3 Identification de S parateurs par la Classification Supervis e CS Au lieu de performer l extraction d information comme l extraction d une sous chaine de tokens on peut la r aliser au travers de fonctions de s paration ou s parateurs Un s parateur est un espace entre deux tokens adjacents Ici un s parateur n est pas quelque chose qui fait partie effectivement du texte tel que l espace blanc mais une notion qui r sulte du processus de transformation d un document en une s quence de tokens En se servant de la CS on souhaite alors appr hender deux classificateurs autrement dit deux fonctions d extractions d finissant des s parateurs de d but ou de fin d une donn e extraire Ces fonctions sont gales 1 si et seulement si l espace entre deux tokens adjacents quelconque sont
42. un transducteur de tuples et les transitions d tat sont d termin es en assortissant les r gles contextuelles qui d crivent le contexte d limitant deux attributs adjacents Les r gles contextuelles se composent des diff rents s parateurs qui repr sentent les fronti res invisibles entre des tokens adjacents et un algorithme de g n ralisation inductif est employ pour induire ces r gles depuis les exemples d entrainement annot s Avant d extraire des donn es d un document le syst me segmente la page HTML d entr e en tokens Le transducteurs tats finis qui en r sulte prend une s quence de tokens comme entr e et assortit les s parateurs de contexte avec des r gles contextuelles pour d terminer des transitions d tat Un FST peut tre construit pour chaque type de tuples dans un document 3 2 3 STALKER STALKER est un syst me d extraction multi slot reposant sur n extracteurs single slot Il utilise un formalisme appel Embedded Catalog Tree ECT Muslea et al 1998 pour repr senter un sch ma de sortie ECT est une structure arborescente o les noeuds feuilles 3l sont des donn es extraire et les noeuds non feuilles sont des listes de tuples dont les composantes repr sentent soit un noeud feuille soit un noeud liste Cet arbre d crit l organisation logique des donn es dans le document mais galement un processus d extraction hi rarchique En plus le formalisme ECT guide le processus d extraction d i
43. 1 22 23 24 25 26 2T 28 29 30 31 32 33 34 35 36 37 38 39 40 4 42 43 44 45 46 4T Table de Figures Latehti cture g n rique d ACGATHE die en etf od ulate adil fa nee 4 Exemple d extraction d information auteurs et emails adapt de Cabral 2004 8 Un document non structur du MUC 4 sisi 10 Donn es a extraire du document de la Fig Sa annee Ep 11 Exemple d un document HM Ds s ass ieu quee Et nn escala of edite eene 12 Un exemple de document XML repr sentant un catalogue de CD 13 Structuration de documents selon Chang 2006 14 Rendu d une page HTML adapt de Chang et al 2006 esses 15 Repr sentation arborescente DOM Tree de la page HTML 16 Exemple d extractions single slot et multi slot d une sess 17 Structure arborescente d un document HTML contenant une liste 18 Sortie structur extrait du document HTML de la Fig 11 adapt de Marty 2007 18 S quence de tokens avec des s parateurs Marty amp Torre 2004 24 L algorithme d apprentissage de BWI Freitag amp Kushmerick 2000 26 L apprenant faible LearnDetector de BWI Freitag amp Kushmerick 2000 27 Deux d tecteus d but et fin pour le slot stime du corpus Seminars 28 Exemple d induction d extracteurs et extra
44. 1 2 Param tre Lookahead 1 ueniet EH eed quete 61 3o 1 3 Information POS eta eto oai a etes data otii esce DR 62 5 3 2 Diff rents ensembles dati Duss ai oes eco nm so eU GU en nl nn ne 66 5 3 3 cC DEDE apprentissage a causes en io equo paso based essct esi uiuis Da 67 5 4 valuation comparative oder ton teda en bau need odd 68 5 4 1 Crit res d valuation recommand s ass e as 68 5 4 2 Description des syst mes comparer 69 5 4 5 Comparaison sur les corpora Seminars et Jobs eese 70 5 4 4 Comparaison sur le corpus Call For Papers CFP 13 6 CONCLUSION ET PERSPECTIVES e eesesseseessesessoesossesossesossossescosoesossossesossosseseessese 78 oS ME oT LESTO E E E E E E E AE 78 6 2 Perspectives relatives au syst me d EI propos 79 6 3 Perspectives relatives l architecture MasterWeb AGATHE eene 81 REFERENCES 6 ssecdcosscetessesssodsseadscaseespoatsssyscessvesiesees ERROR BOOKMARK NOT DEFINED Appendice A L gendes d tiquettes POS du QTAG en anglais sss 89 XV xvi Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig Fig 2 IQ Ur W D 10 LT 12 13 14 15 16 17 18 19 20 2
45. 1 538 1998 Ireson amp Ciravegna 2005 Ireson N F Ciravegna Pascal Challenge The Evaluation of Machine Learning for Information Extraction Machine Learning for the Semantic Web Dagstuhl Seminar Dagstuhl DE 2005 Ireson et al 2005 Ireson N Ciravegna F Califf M E Freitag D Kushmerick N Lavelli A Evaluating machine learning for information extraction In Proceedings of the 22nd international conference on Machine learning table of contents Vol 119 pp 345 352 Bonn Germany 2005 ITC IRST 2004 TIES Trainable Information Extraction System Dot Kom project 2004 Disponible http tcc itc it research textec tools resources ties html dernier acc s en juin 2009 Kauchak et al 2002 Kauchak D Smarr J Elkan C Sources of Success for Information Extraction Methods Technical Report CS2002 0696 Department of Computer Science and Engineering University of California San Diego January 2002 85 Kohavi 1995 Kohavi R A Study of Cross Validation and Bootstrap for Accuracy Estimation and Model Selection IJCAT pp 1137 1145 1995 Kosala amp Blockeel Kosala R Blockeel H Instance based wrapper induction 2000 Kushmerick 1997 Kushmerick N Wrapper Induction for Information Extraction PhD Thesis University of Washington 1997 Kushmerick 2000 Kushmerick N Wrapper induction Efficency and expressiveness Artificial Intelligence 118 1 2 15 68 2000 Kushmerick amp Tho
46. 14 2 3 Concepts de base en Eliane nn nine nt NS pA de 14 2 3 1 Repr sentation de doc ments sssic tiennent 14 2 3 1 1 Repr sentation par une s quence dn casa saindo E aereas Beat ee hae eine 15 2 3 1 2 Repr sentation par Marbre Eua da sesta dh Sead 15 2 32 Types de SOMICS use etie ORE DU RED NIRE qe in eii pei dada 16 2 4 Conception A EXITACIEURS SE tyge rki e e a een aE Hoe ito do a ege Ul 18 241 Approche manuelle prt er UE TUUS SERO EAR Ver Ada aa Mansa S REE 19 2 4 2 Approche par specification assist e nine nine 19 2 4 3 Approche par induction supervis e d extracteurs see 19 2 4 4 Approche par induction non supervis e 20 25 Mesures d vall tion de syst mes d BI s ue Se de aua eid ORE 20 2 5 1 Crit res de Correction asino bii e ptg Feeds eed Loa ditas es died 20 2 5 2 Pr cision Rappel et F Measure acuti nn titio c ne en ee 20 2 0 Poi die et Wile ae hein lee ae 21 3 INDUCTION D EXTRACTEURS ET CLASSIFICATION SUPERVISEE 22 3 1 Mod le d Apprentissage de la Classification Supervis e 22 Sl Classification SUpervisee Sas an udo edens abge Badass 22 3 1 2 El comme un Probl me de Classification Supervis e sess 23 3 1 3 Identification de S parateurs par la Classification Supervis e CS 24 3 1 4 sBoosted Wrdpper Inductiol ouo RSR AR En Le 24 3 1 4 1 Repr se
47. 2003 Le syst me scorer Ce point concerne le logiciel qui a t utilis e pour l valuation Le seul outil publiquement disponible pour tel but est le MUC Scorer Douthat 1998 Normalement les chercheurs d IE ont mis en oeuvre leurs propres syst mes scorer en s appuyant sur un certain nombre d hypoth ses implicites qui ont une forte influence sur les r sultats de l valuation R sultats rapport s Quelques articles rapportent seulement la F measure mais pas la pr cision et le rappel alors que la diff rence entre la pr cision et le rappel est un aspect fondamental de la performance 5 4 2 Description des syst mes comparer Cette section fait une br ve pr sentation des syst mes comparer avec M TIES qui n ont pas d j t mentionn s dans la section 3 3 Rapier C est un syst me d EI single slot qui vise extraire des informations de textes libres Califf amp Mooney 1999 Son algorithme d apprentissage incorpore des techniques de la programmation logique inductive Muggleton 1994 Thomas 2005 et il apprend des patrons qui ne sont pas limit s par une fen tre fixe mais que inclut des contraints sur les mots et sur le tagage POS que entoure la donn e extraire Ces patrons consistent de trois slots distincts Pre Post et Filler Les premiers jouent le r le de d limiteurs gauche et droite tandis que le dernier d finit la structure du champ extraire GATE SVM Li et al 2004a 2004b est u
48. 3 CDD 22 ed MEI2009 070 iv Disserta o de Mestrado apresentada por Rinaldo Jos de Lima P s Gradua o em Ci ncia da Computa o do Centro de Inform tica da Universidade Federal de Pernambuco sob o t tulo Extraction d information Adaptative de Pages Web par Induction Supervis e d exfracteurs orientada pelo Prof Frederico Luiz Gon alves de Freitas e aprovada pela Banca Examinadora formada pelos professores Prof Evandro de Barros Departamento de Tecnologia da Informa o UFAL Prof Frederico Luiz Gon alves de Freitas Centro de Inform tica UFPE Visto e permitida a impress o Recife 16 de junho de 2009 C i GE jj PIA ol to d i Vita Ee 20 A Ln ips Prof FRANCISCO DE ASSIS TEN RIO DE CARVALHO Coordenador da P s Gradua o em Ci ncia da Computa o do Centro de Inform tica da Universidade Federal de Pernambuco ma m re Maria Lima et ma fille Rebeca Lima Les deux jeunes filles les plus importantes du monde pour moi vi Remerciements Cette dissertation est l aboutissement d un stage de recherche d velopp par l auteur pour conclure son projet de Master of Sciences dans le cadre des projets MasterWeb AGATHE et Click amp Go Ce dernier a financ e cette recherche qui a t men e en accord avec l Universit F d rale de Pernambuco UFPE Recife sous la co orientation des Professeurs Frederico FREITAS du Centre d Informatique de l UFPE et Bernard ESPINASSE du La
49. 83 0 431 workacro 0 904 0 280 0 428 workcame 0 869 0 392 0 541 workcame 0 855 0 425 0 559 workdate 0 930 0 725 0 815 workdate 0 919 0 731 0 814 workhome 0 718 0 729 0 724 workhome 0 718 0 739 0 728 workloca 0 988 0 906 0 945 workloca 0 990 0 917 0 952 workname 0 875 0 761 0 814 workname 0 890 0 826 0 857 worknoti 0 902 0 545 0 679 worknoti 0 927 0 572 0 708 workpaper 0 882 0 464 0 608 workpaper 0 911 0 478 0 627 a b Fig 39 R sultats sur le Corpus CFP sans a et avec b POS CFP Pascal Challenge 1 0 EE no POS 7 with POS 0 8 4 F1 0 6 0 4 4 0 2 4 0 0 cf_acro cf home cf name w_acro w_came w date w home w_loca w_name w noti w paper Slots Fig 40 Influence du POS sur le Corpus CFP sans a et avec b POS Bilan sur les corpora avec information POS La Fig 41 pr sente le bilan g n ral pour appr cier le gain effectif du tagage POS sur les corpora On constate que pour le corpus CFP on a obtenu de meilleurs r sultats avec POS En revanche pour les deux autres corpora Fig 36 37 et 38 la diff rence a t pratiquement nulle Ces derniers r sultats peuvent surprendre mais on peut les justifier on analysant la nature tr s structur des corpora Seminars et Jobs En effet l algorithme d induction d extracteurs peut d j avoir de tr s bonnes performances sans se servir d un espace d hypoth ses plus large sans la prise en compte de l information POS par exemple On pe
50. CD lt CD gt lt CD gt lt CD gt lt CD gt lt CD gt lt CD gt lt CD gt lt CD gt lt CD gt lt CATALOG gt lt TITLE gt Empire Burlesque lt TITLE gt lt ARTIST gt Bob Dylan lt ARTIST gt lt COUNTRY gt USA lt COUNTRY gt lt COMPANY gt Columbia lt COMPANY gt lt YEAR gt 1985 lt YEAR gt lt TITLE gt Hide your heart lt TITLE gt lt ARTIST gt Bonnie Tyler lt ARTIST gt lt COUNTRY gt UK lt COUNTRY gt lt COMPANY gt CBS Records lt COMPANY gt lt YEAR gt 1988 lt YEAR gt lt TITLE gt Greatest Hits lt TITLE gt lt ARTIST gt Dolly Parton lt ARTIST gt lt COUNTRY gt USA lt COUNTRY gt lt COMPANY gt RCA lt COMPANY gt lt YEAR gt 1982 lt YEAR gt lt TITLE gt Still got the blues lt TITLE gt lt ARTIST gt Gary Moore lt ARTIST gt lt COUNTRY gt UK lt COUNTRY gt lt COMPANY gt Virgin records lt COMPANY gt lt YEAR gt 1990 lt YEAR gt lt TITLE gt Eros lt TITLE gt lt ARTIST gt Eros Ramazzotti lt ARTIST gt lt COUNTRY gt EU lt COUNTRY gt lt COMPANY gt BMG lt COMPANY gt lt YEAR gt 1997 lt YEAR gt Fig 6 Un exemple de document XML repr sentant un catalogue de CD 13 2 2 4 Bilan Les documents XML sont consid r s comme structur s car il existe des sch mas DTD ou XML disponibles pour d crire les donn es Les textes libres sont non structur s puisqu ils exigent un substantiel traitement de langage naturel Pour le grand volume de pages HTML sur le Web
51. F1 comme fonction du nombre d it rations de boosting sur le corpus Jobs Comme la Fig 34 sugg re le nombre d it rations exig s par l algorithme BWI pour atteindre la performance maximal d pend de la difficult de la t che Par exemple pour les slots city et state tr s peu d it rations ont t n cessaires pour achever la performance maximale dont nous pouvons conclure que pour les slot plus r guliers tr s peu d it rations sont suffisantes D autre part quand on consid re les slots recruiter language et plataform on s aper oit qu il faut un nombre plus grand d it rations pour atteindre un niveau similaire de performance Les slots area title et application se montrent encore plus difficiles pour l algorithme BWI car on observe la tendance croissante de gain au fur et mesure que l algorithme utilise plus d it rations ce point il est important de discuter que le gain faible de performance du slot area quand on consid re le nombre d it rations entre 100 et 200 ne compense pas le double de temps qu il le faut En plus Kauchak Kauchak et al 2002 affirment que un nombre tr s lev d it rations peut amener l algorithme une situation de sur apprentissage ou des r gles redondantes Enfin la courbe correspondante du slot All vue ici comme la courbe moyenne de performance montrent qu un nombre de 100 it rations nous semble un bon compromis entre la performance et le temps d ex cution de l algorithme B
52. REPORTS DISCLOSED IN LIMA TODAY THE COCA GROWERS OPPOSE THE USE OF THE HERBICIDE CALLED SPIKE WHICH THE GOVERNMENT IS PLANNING TO USE TO DESTROY THE CLANDESTINE COCA PLANTATIONS ACCORDING TO UNOFFICIAL SOURCES A GROUP OF TERRORISTS LINKED TO DRUG TRAFFICKING REPORTEDLY WOUNDED A POLICE OFFICER IN AN ATTACK ON A POLICE HELICOPTER TERRORISTS ALSO ATTACKED A CIVIL GUARD POST IN NUEVO PROGRESO NORTH OF TINGO MARIA UCAYALI DEPARTMENT Fig 3 Un document non structur du MUC 4 10 0 MESSAGE ID TST4 MUC4 0003 1 MESSAGE TEMPLATE 1 2 INCIDENT DATE 23 AUG 88 3 INCIDENT LOCATION PERU 4 INCIDENT TYPE ATTACK 5 INCIDENT STAGE OF EXECUTION ACCOMPLISHED 6 INCIDENT INSTRUMENT ID 7 INCIDENT INSTRUMENT TYPE 8 PERP INCIDENT CATEGORY TERRORIST ACT 9 PERP INDIVIDUAL ID GROUP OF TERRORISTS 10 PERP ORGANIZATION ID 11 PERP ORGANIZATION CONFIDENCE 12 PHYS TGT ID THEIR COCA POLICE HELICOPTER 13 TRANSPORT VEHICLE POLICE HELICOPTER 14 PHYS TGT NUMBER 15 PHYS TGT FOREIGN NATION 16 PHYS TGT EFFECT OF INCIDENT 17 PHYS TGT TOTAL NUMBER 18 HUM TGT NAME POLICE OFFICER 19 HUM TGT DESCRIPTION 20 HUM TGT TYPE LAW ENFORCEMENT POLICE OFFICER 21 HUM TGT NUMBER 22 HUM TGT FOREIGN NATION 23 HUM TGT EFFECT OF INCIDENT INJURY POLICE OFFICER 24 HUM TGT TOTAL NUMBER 1 POLICE OFFICER Fig 4 Donn es a extraire du document de la Fig 3 2 2 2 Document
53. WI 5 3 1 2 Param tre Lookahead L Il a t r alis des exp riences en utilisant diff rent valeurs pour le param tre look ahead L afin d analyser son effet sur la performance La section 3 2 4 5 sur les limitations de l algorithme BWI a expliqu que trouver une extension de s parateurs est exponentiel en L parce que chaque combinaison des motifs de tokens droite et a gauche d un s parateur quelconque est num r e et valu e En revanche dans Freitag amp Kushmerik on trouve la 61 remarque que dans la grosse majorit de cas des t ches d extraction la valeur L 3 est pertinente pour avoir un bon quilibre entre la performance et le temps pris par l algorithme pour induire d extracteurs Cons quemment pour rendre les exp riences de cette section viable pour des valeurs plus lev es de L nous les avons r alis es avec les attributs d fauts du syst me c est dire sans utiliser des attributs suppl mentaires pour caract riser les tokens La Fig 35 montre les r sultats des exp riences sur le corpus CFP pour une validation crois e avec k 4 et le nombre d it rations 100 En examinant ces r sultats ils confirment l importance du contexte en EI En plus le graphique ci dessous montre que dans un m me corpus diff rents slots peuvent avoir diff rentes valeurs optimales de L Par exemple le slot workshop acronym n cessite d une fen tre de token plus large de 7 pour avoir la meilleure performance A
54. aleurs manquantes dans la table de r sultats Les honorables scores des slots speaker et location confirment l ad quation de l algorithme BWI pour les t ches d EI sur des documents plus structur s Pour l algorithme BWI si un slot cible slot extraire est tout simplement pr c d ou suivi d un ensemble de tokens ou par des tokens d un type distinct repr sent par les caract res wildcard joker disponibles dans son espace d hypoth ses les d tecteurs de s parateurs apprennent ais ment ce contexte Pour les documents fortement structur s ou partiellement structur s le cas du corpus Seminars les slots sont souvent pr c d s par l identification des tiquettes par exemple Speaker Dr X ou suivi par des l ments d information facilement identifiables Alors que d autres m thodes d EI reposant sur r gles sont principalement con ues pour identifier des contextes en dehors des slots cibles BWI apprend davantage certaines r gularit s qui se produisent l int rieur de slots cibles Cons quemment les d tecteurs de s parateurs peuvent se prolonger dans le bord du slot cible aussi bien que dans le contexte local Autrement dit les d tecteurs gauche d tecteurs fore peuvent apprendre ce que ressemblent les premiers tokens d un slot cible si les slots tendent avoir un d but r gulier et les d tecteurs droite d tecteurs aff peuvent apprendre les derniers tokens si ils ont une forme galem
55. application du mod le d extraction 39 Les syst mes d EI modernes utilisent un composant d apprentissage pour r duire la d pendance de domaines sp cifiques et pour diminuer la quantit de ressources fournies par un humain Un mod le d extraction est d fini en fonction de la d marche suivre et ses param tres sont appris optimis s par une proc dure d apprentissage Les approches statistiques apprennent par exemple les attributs de classement les plus pertinents des probabilit s des s quences d tats des approches reposant sur r gles apprennent un ensemble de r gles d extraction et les approches reposant sur connaissance acqui rent des structures pour augmenter et interpr ter leur connaissance pour l extraction Le d fi est de trouver un mod le d extraction permettant l apprentissage de tous les param tres en utilisant la m me plate forme d extraction pour chaque domaine d application 4 1 3 Post traitement de la sortie L une des possibilit s pour structurer les donn es extraites est de modeler le template en tant qu une relation de base de donn es Apr s que les informations importantes aient t trouv es par l application d un mod le d extraction les extraits identifi s des textes sont assign s aux attributs correspondants de la structure cible Corpus j d i entrainement Pre traitement dutexte d entr e Apprentissage du Mod le mod le d extraction d extraction Post traitement
56. apprentissage not S On dit alors que x est un exemple positif si y 1 et un exemple n gatif contre exemple si y 1 Par cons quent pour chaque exemple tiquet x y on a donc y f x La fonction cible f f X Y est d finie sur l ensemble X et prend ses valeurs dansY Le but de l apprentissage en classification supervis e est alors d induire d apr s un ensemble d exemples tiquet s S une hypoth se A X Y qui approche le plus possible la fonction cible f dont on ne dispose pas Ce mod le de classification supervis e consiste en deux tapes apprentissage et pr diction Dans l apprentissage on essaye de trouver un mod le partir de donn es tiquet es qui permet de s parer les donn es d apprentissage tandis que dans la pr diction les mod les appris servent identifier si un exemple non tiquet devrait tre classifi comme 1 ou 1 L espace de recherche de l algorithme d apprentissage est aussi appel de l ensemble d hypoth ses not par H L apprenant op re le processus de g n ralisation qui est vu comme une recherche dans l espace d hypoth ses H afin de trouver celle qui correspond mieux aux exemples d apprentissage Russel amp Norwig 2003 Ainsi l objectif de l apprenant est de trouveur un compromis entre l hypoth se la plus g n rale et l hypoth se la plus sp cifique C est dire quil doit bien g n raliser pour qu il puisse se d tacher des donn es d apprentissage ne p
57. art 330 len 9 gt Stephanie lt token gt start 624 start 810 start 880 end 151 gt end 348 gt end 640 gt end 826 gt end 896 gt Fig 26 Un extrait d une sortie d extraction obtenu du corpus d annonces de conf rences CMU s quences de tokens extraits pour le slot lt speaker gt Le guide du TIES explique en plus de d tail la configuration n cessaire pour ex cuter des extractions 47 4 3 M TIES nouvelle version de TIES tendue l annotation morphosyntaxique Comme nous avons d j voqu dans l introduction de ce chapitre il a fallu d tendre la version originale du syst me TIES afin de pouvoir valuer l influence de l annotation morphosyntaxique POS tagging dans l extraction d information dans un document plus ou moins structur De plus certaines limitations dans cette version du syst me ont t constat es notamment un pr traitement insuffisant de documents d entr e pour bien pr parer et valider les documents avant qu ils puissent tre trait s par le module d apprentissage Ces limitations seront corrig es dans la nouvelle version propos e par ce projet M TIES La figure suivante illustre l architecture modifi e du syst me pr sentant les nouveau modules y rajout s Nous exposerons ci apr s les t ches qui ont t n cessaires pour adapter le syst me TIES aux besoins de cette recherche Corpus d entrainement Module d induction Application des de r g
58. arty amp Torre 2003 Marty P Torre F Classer pour extraire repr sentation et m thodes Technical Report Grappa report 0103 GRAPPA 2003 Marty amp Torre 2004 Marty P Torre F Codages et connaissances en extraction d information In M Liqui re and M Sebban editors Actes de la Sixi me Conf rence d Apprentissage CAp 2004 Montpellier pp 207 222 juin 2004 Mason amp Tufis 1998 Mason O Tufis D Tagging Romanian Texts a Case Study for QTAG a Language Independent Probabilistic Tagger In Proceddings of First International Conference on Language Resources and Evaluation LREC Granada Spain 28 30 May pp 589 596 1998 86 Mitchell 1997 Michell T Machine Learning McGraw Hill 1997 MnN 2008 Ontology driven semi automatic and automatic support for semantic web d cembre 2008 Disponible http projects kmi open ac uk akt mnm dernier acc s en juin 2009 Muslea et al 1998 Muslea I Minton S Knoblock C STALKER Learning extraction rules for semistructured web based information sources In AAAI Workshop on AI and Information Integration pp 74 81 1998 Muggleton 1994 Muggleton S Raedt L D Inductive logic programming Theory and methods J Log Programming 19 20 629 679 1994 Muslea et al 2001 Muslea I Minton S Knoblock C Hierarchical wrapper induction for semistructured information sources Automomous Agents and Multi Agent Systems 4 1 2 93 114 2001 Par
59. as apprendre par c ur et viter alors overfitting Par contre il doit en m me temps ne pas sur g n raliser pour ne pas s loigner du concept cible quand il apprend une hypoth se trop g n rale 3 1 2 EI comme un Probl me de Classification Supervis e La classification supervis e a t appliqu e avec succ s pour l EI dans diff rents travaux Freitag amp McCallum 1999 Freitag amp Kushemerick 2000 Marty amp Torre 2004 Finn amp Kushmerick 2004 Gilleron et al 2006 Un probl me d EI est alors formul en tant qu un probl me de classification supervis e et l laboration d un syst me d EI se fait alors en deux tapes l apprentissage et l extraction Ces deux tapes sont pr c d es d un m me pr traitement du document permettant de le segmenter en unit s et de repr senter des exemples sur lesquels portera la classification L tape d apprentissage utilise un ensemble de documents tiquet s pour produire un mod le de classification capable d identifier les donn es extraire tandis que l tape d extraction applique le mod le appris des documents non tiquet s pour en extraire les donn es Dans certains cas les r sultats de pr diction peuvent tre des valeurs num riques compris entre 0 et 1 Alors un exemple peut tre classifi comme 1 quand la valeur de pr diction est plus grande que 0 5 par exemple 23 Une base d exemples est constitu e d un ensemble de s quence de
60. ass Ce type de fichier est compatible avec Excel 51 language platform post date recruiter req degree req years experience salary state test application area city company country desired_degree desired years experience n dp EE fn total precision T EE lag 0 94736842 0 92307692 D 93506493 34 0 96428571 0 79411764 D 87096774 39 Ho D 79487179 0 88571428 42 10 97297297 0 85714285 0 91139240 154 0 0 97115677 10 84230230 0 90215169 Fig 29 Fen tre de r sultats d une session d apprentissage de TIES 4 4 Conclusion Ce chapitre a pr sent un syst me d EI modulaire que reposant sur l induction supervis e d extracteurs permet l extraction d information partir d un corpus d apprentissage manuellement annot par l utilisateur et qui peut prendre en compte la syntaxe du langage naturel par le moyen d un nouveau module responsable pour l tiquetage morphosyntaxique sur ces documents Dans le prochain chapitre afin d valuer les performances de l architecture propos e plusieurs exp riences seront r alis es sur des corpora bien connus dans la communaut scientifique du domaine de l EI Seminars Jobs et CFP Pascal Challenge L objectif sera d valuer les performances d un syst me d induction supervis e d extracteurs M TIES sur des corpora de diff rents niveaux de structuratio
61. boratoire des Sciences de l Information et des Systemes LSIS Marseille UMR CNRS 6168 Je tiens remercier mon cotuteur br silien Prof Frederico Freitas pour toutes les le ons apprises son soutien tout au long de cette tude et l opportunit qu il m a donn pour la r alisation de ce travail Je tiens remercier vivement mon cotuteur frangais Prof Bernard Espinasse pour son soutien ses conseils clair s son suivi quotidien qui m ont t d une aide pr cieuse dans l volution de mes travaux Qu il trouve ici l expression de ma profonde gratitude Un grand merci au Prof S bastien Fournier et Shereen Bitar pour de nombreuses discussions qui n ont permis de voir plus clair le contexte de notre sujet de recherche Je remercie mon ami Luciano Cabral que j ai connu pendant le temps que nous avons durement travaill ensemble au Centre d Informatique CIN Recife et qui a beaucoup particip dans la conception de ce travail Je souhaite pr senter mes remerciements aux membres du jury qui ont accept de participer ma soutenance Je remercie galement mon ami de longues ann es Gerson Henrique qui m a encourag et soutenu tout au long de cette recherche Merci sp cial Roberta Costa pour avoir eu la patience d couter mes h sitations pour les conseils et les mots d encouragements qui m ont vraiment faire avancer Je tiens remercier Claudia Serey ma seule amie br silienne Marseille qui d s
62. cessaire pour atteindre les meilleurs r sultats 3 2 Autres syst mes d induction supervis e d extracteurs Cette section pr sente bri vement d autres syst mes d induction supervis e d extracteurs Pour une tude plus d taill e des syst mes d EI nous renvoyons le lecteur Kushmerick amp 29 Thomas 2003 Siefkes amp Siniakov 2005 Chang et al 2006 Tang et al 2007 Les syst mes examin s sont tous des syst mes d EI qui s appliquent aux documents HTML et XML I faut rappeler qu un syst me d EI supervis prend en entr e des documents dans lesquels les informations extraire sont annot es Il fournit en sortie l extracteur induit au cours d un processus d apprentissage partir d exemples positifs Les sections suivantes pr sentent les syst mes WIEN SoftMealy STALKER Amilcare SIE et TIES 3 2 1 WIEN Le syst me WIEN Kushmerick 1997 2000 d velopp par Kushemick au Departement of Computer Science de l Universit de Washington en 1997 a t le premier syst me d induction d extracteurs Ce syst me traite les documents HTML annot s comme des cha nes de caract res Il est d fini comme un vecteur lt l rj ly ri de 2K d limiteurs o chaque paire R gt correspond un type d information et par la fonction extraireLR Kushmerick 1997 Cette fonction prend en entr e un extracteur W l rj In rn et un document d et applique l extracteur W au document d L ext
63. chitecture originale du syst me TIES est illustr e par la Fig 24 On peut noter que cette architecture suit de pr s le mod le d architecture g n rique pr sent dans la section 4 1 de ce chapitre Les sections suivantes d taillent chaque module en analysant leurs aspects les plus importants 4 2 2 Repr sentation de documents 41 Dans TIES les documents d un corpus qui seront trait s doivent tre sous un format sp cifique nomm TIESIF TIES Input Format Ce format permettra la tokenisation et l extraction d information Corpus d entrainement Feature Extraction Module d induction Application des de r gles BWI regles d extration Informations extraites XML Fig 24 Architecture originale du TIES 4 2 2 1 Tokenisation partir d une s quence de caract res l objectif est d identifier les parties l mentaires du langage naturel des mots des signes de ponctuations et des s parateurs La s quence r sultante de tokens significatifs est la base pour tous les types de traitements linguistiques post rieurs Ci dessous un extrait d un fichier du corpus Seminars d j tokenis avec des balises d annotations speaker qui indique les exemples positifs et sa repr sentation en format TIESIF University of Pittsburgh Name speaker Dr Jefrey D Hermes speaker Affiliation Department lt xml version 1 0 gt lt corpus gt text path input seminar name cmu andrew org cfa cfa to
64. ction dans WIEN 30 Exemple d une r gle par conjonction Cabral 20041 22 Exemple d une r gle tiquetage taging rule Tang 2007 34 Exemple d une r gle d tiquetage g n ralis Tang 2007 34 L action d place la balise de la mauvaise position la bonne Ciravegna 2001 35 Apercu du systeme SIE os uei oet to eot nee ne Me nel Di Ru Nr des 36 Architecture d un syst me d EI adaptatif sess 40 Arveliteotureoriprale du ELES ssi e a be Sea DE 42 Un extrait d un wrapper appris en XML seseeeeeeeeeeeeeene nennen enne enne 46 Un extrait d une sortie d extraction obtenu du corpus d annonces de conf rences 47 Nouvelle architecture du TIES M TIES cccccccccccccceceesessnsecececceeceessnseaeeeeeceeneees 48 Fen tre principale de l outil d annotation MnM see 49 Fen tre de r sultats d une session d apprentissage de TIES 52 Exemple d un document correctement annot en XML sse 53 Exemple d un document du corpus Seminars Freitag 1997 54 Exemples de template d extraction compl te rempli a et 55 Exemple d une offre d emploi avec son template d extraction rempli Califf 1999 56 Performance Fl comme fonction du nombre d it rations esses 61 volution de la F measure en fonction du look ahead L sur le corpus CFP 62 R sultats sur le C
65. ctuellement sur des documents d entr e il pourrait tre d velopp un module de post traitement pour sauvegarder les r gles g n r es en utilisant une base de donn es par exemple En plus une tude post rieure plus minutieuse pourrait tre faite pour d finir d autres fa ons de repr senter ces r gles en utilisant un autre langage ou formalisme de repr sentation 9 Mod lisation d une base de donn es pour les informations extraites De fa on similaire ce qu on vient de mentionner on envisage aussi un module de post traitement pour stocker les informations extraites qui sont g n r es par le syst me en plusieurs fichiers XML En fait M TIES cr e s par ment un fichier XML pour chaque slot du sch ma d extraction Ainsi on peut r organiser les r gles extraites en les regroupant selon une structure dict e par le sch ma d extraction en question Un possible choix serait de bien mod liser une base de donn es pour atteindre cet objectif 80 10 Annotation automatique guid e par une ontologie de domaine Il a t propos dans la section 4 3 1 l usage d un syst me d annotation semi automatique pour rendre moins fastidieuse l annotation de nouveaux corpora En fait la version originale de MnN de 2004 avait un module tr s important qui guidait tout le processus de suggestions de r gles pour l annotation assist e de documents mode interactif ou m me pour les r gles d annotation sans intervention de l utilisateu
66. cuments avec donn es extraire soient annot es par l utilisateur Puis nous avons vu comment la classification supervis e sur laquelle repose la plupart des techniques d EI par induction supervis e permet de d finir un extracteur en tant qu un processus de classification le probl me d induction d extracteurs se ram ne alors un probl me d apprentissage de classification supervis e Cette transformation d un probl me d extraction en un probl me de classification supervis e n cessite que soit sp cifi la repr sentation des documents la d finition des l ments des documents qui seront consid r s comme les exemples du probl me de classification et le codage de ces exemples En analysant en d tail le syst me BWI d induction d extracteurs reposant sur la classification supervis e on a pu distinguer les diff rentes tapes l mentaires associ es une telle transformation En plus il a t pr sent diff rents syst mes d EI par induction supervis e d extracteurs qui adoptent une repr sentation de document base de tokens et r alisent l EI en mettant en oeuvre diff rents algorithmes d apprentissage pour traiter des textes semi structur s La contribution principale de cette recherche a t la proposition d un syst me d EI adaptatif facilement configurable et convivial l utilisateur par le biais d une architecture modulaire destin e l utilisation sur plusieurs types de documents Il a t constat q
67. d tecteurs ann tad 8 30 PM SA stime Fi tine lt Num gt Ai Num lt gt lt Alph gt ll Fig 16 Deux d tecteurs d but et fin pour le slot stime du corpus Seminars Freitag amp Kushmerick 2000 Le symbole y signifie une nouvelle ligne Finalement pendant l tape 3 BWI enregistre les longueurs des s quences de tokens d un champ observ es sur les donn es d apprentissage Deux d tecteurs le premier identifi comme un d but et le second comme une fin sont associ s si le nombre de tokens entre les deux a d j t observ lors de l apprentissage En fait l algorithme apprend la distribution de x la probabilit histogramme Hi de la longueur des champs extraire rencontr s dans l ensemble d apprentissage En d autres termes on peut associer chaque d tecteur de d but et fin une valeur num rique de confiance Caa et Cy respectivement Pour effectuer une extraction en utilisant un extracteur wrapper W F A H on attribue chaque d tecteur i dans le document un score fore F i 25 C F i et un score aft A p C A Le wrapper W classifie une s quence de tokens comme Ls F A H j gt t O autrement WG j Ou Test une valeur seuil qui repr sente la pr f rence entre la pr cision et le rappel 28 La raison est que W compare 7 avec l estimation de la probabilit d une classification correcte En faisant varier 7 on p
68. d degree et post date N importe quel de ces slots peut apparaitre aucune une ou plusieurs fois dans un m me document Le tableau ci dessous en pr sente des statistiques sur ce corpus Tab 4 Nombre d exemples pour chaque entit slot du corpus JOBS JOBS ao xw pss px ome 56 5 1 4 Corpus CFP CALL FOR PAPERS Pascal Challenge 2005 5 1 4 1 Description du corpus Ce corpus est constitu de 1 100 documents contenant 850 Workshop Call for Papers CFP et 250 Conference CFP tabli lors de la comp tition de syst mes d EI de l tat de l art Pascal Challenge en 2005 Ireson amp Ciravegna 2005 La grosse majorit de documents rel vent du domaine de l Informatique bien que d autres domaines biom decine et linguistique y soient repr sent s Les documents sont divis s en trois corpora un corpus d apprentissage 400 Workshop CFP un corpus de test 200 Workshop CFP et un corpus enrichi 250 Workshop CFP and 250 Conf rence CFP Ce dernier corpus a t annot par le system GATE qui fournit la tokenisation tiquetage POS NER et attributs de token de textes type de token taille etc 5 1 4 2 D finition du template d extraction Chaque document peut avoir 11 slots extraire 8 concernant des Workshops name acronym homepage location date paper submission date notification date et camera ready copy date et 3 relatifs aux Conferences name acronym et homepage Tab 5 Distribution de fr quences
69. day 19 0 gt body token id 146 type word start 438 len 10 alpha token true capitalized token true gt University lt token gt token id 148 type word start 449 len 2 alpha token true lower case token true gt of lt token gt token id 150 type word start 452 len 10 alpha token true capitalized token true gt Pittsburgh lt token gt 42 token id 1 token id 1 token id 1 token id 1 token id 1 token id 1 token id 151 type nl start 462 len 1 nl token true gt n lt token gt 153 type word start 464 len 4 alpha token true capitalized_token true gt Name lt token gt 154 type punct start 468 len 1 punct_token true gt lt token gt 156 type tag start 470 len 9 open_tag true gt speaker lt token gt 157 type abbrev start 479 len 3 abbr_token true gt Dr lt token gt 159 type word start 483 len 7 alpha_token true capitalized_token true gt Jeffrey lt token gt p Y 161 type abbrev start 491 len 2 abbr token true gt D lt token gt lt token id token id token id 1 token id token id token id body text text text lt corpus gt 163 type word start 494 en 6 alpha token true capitalized_token true gt Hermes lt token gt 164 type tag start 500 len 10 close_tag true
70. de la sortie Informations extraites Fig 23 Architecture d un syst me d EI adaptatif 40 4 2 TIES un syst me d induction supervis e d extracteurs Le syst me d induction supervis e d extracteurs propos par le pr sent travail est constitu par le syst me TIES ITC IRST 2004 vu comme un module dans l architecture g n rale de notre proposition voir section 4 3 Ce dernier consiste d un syst me d EI adaptatif reposant sur des techniques d apprentissage supervis Pour qu un syst me d EI soit consid r adaptatif il doit d apr s Ciravegna 2003a s adapter de nouveaux domaines d information en employant ou modifiant leurs bases de connaissances en concevant de nouveaux templates d extraction de sorte que les syst mes soient capables de manipuler des concepts du domaine en question s adapter aux sous langages des attributs en modifiant des grammaires et des lexiques fin de faire face aux constructions linguistiques sp cifiques qui sont typiques l application Ss adapter aux diff rents types de textes les documents Web peuvent varier des documents rigidement structur s par exemple des pages en XML et des tableaux aux textes libres Par cons quent chaque type de texte peut avoir des exigences diff rentes en termes d analyse du langage Le syst me TIES apprend automatiquement des r gles partir d un corpus annot avec un ensemble pr d fini de balises XML Ces bali
71. de moteurs de recherche comme Google et Yahoo et pour l tiquetage de partie de discours Brill Tagger Brill 1992 etc GATE accepte en entr e divers formats de texte comme le texte brut HTML XML Microsoft Word PDF ainsi que divers formats de bases de donn es comme PostgreSQL et Oracle gr ce JDBC Il utilise galement le langage JAPE Java Annotation Patterns Engine pour construire des r gles d annotation de documents On y trouve aussi un debugger et des outils de comparaison de corpus et d annotations 2 2 Types de Documents Les types de documents auxquels cette recherche s int resse sont pr sent s dans cette section On peut distinguer trois types de documents par rapport leur niveaux de structuration non structur s semi structur s et structur s 2 2 1 Documents non structur s La notion de document non structur se d finit du point de vue des bases de donn es En effet dans une base de donn es lorsque l on parle de donn es structur es on d signe les donn es qui poss dent une structure pr alablement connue par le biais d un sch ma de base qui les organisent et qui rend ais leur manipulation et leur interrogation par des requ tes Dans un document non structur un texte par exemple les informations qu il contient ont une structure a priori inconnue et tr s variable Pour ce type de document on ne dispose pas d un sch ma qui indiquerait le type des donn es et leur organisation qui puisse guide
72. de pages Web en les transformant en fichiers XHTML bien form s En plus il a fallu le d veloppement d un programme en Java pour adapter HTMLCleaner aux besoins de services de nettoyage de pages HTML et de mise en forme sous le format XML Les corpora ont t annot s selon l exemple d j pr sent dans la section 5 1 58 5 2 2 M thodes d valuation Utiliser les donn es d apprentissage pour concevoir un classificateur et puis estimer la pr cision de la classification sur ces m mes donn es peut aboutir des estimations trompeusement suroptimistes cause de la sursp cialisation de l algorithme d apprentissage Hold out et k fold cross validation sont deux techniques d valuation d exactitude de classificateurs reposant sur des partitions al atoires d chantillonnage de donn es Dans la m thode hold out les donn es sont al atoirement partitionn es en deux ensembles un ensemble d apprentissage et un autre de test Typiquement deux tiers des donn es sont attribu es l ensemble d apprentissage et le tiers restant est attribu l ensemble de test L ensemble d apprentissage est employ pour construire le classificateur dont l exactitude est estim e avec l ensemble de test L valuation ici est pessimiste puisque seulement une partie de donn es initiales est employ e pour construire le classificateur Random subsampling est une variante de la m thode holdout dans laquelle la m thode holdout est r p t e k fois
73. des jokers utilis s par BWI sont cit s avec leurs significations alph correspond aux tokens contenant des caract res de l alphabet lt ANum gt correspond aux tokens contenant des caract res alphanum riques Cap correspond aux tokens contenant des caract res en majuscule LC correspond aux tokens contenant des caract res en minuscule SChar correspond aux tokens contenant un seul caract re Num correspond aux tokens contenant des chiffres Punc correspond aux tokens de ponctuation lt gt correspond n importe quel token 3 1 4 3 Algorithme d apprentissage L algorithme d apprentissage de BWI utilise une technique de boosting nomm AdaBoost Freund amp Schapire 1996 1997 pour l induction de s parateur d but et fin des exemples positifs Dans Freund amp Schapire 1996 les auteurs affirment que la technique de boosting peut tre utile pour des probl mes d apprentissage o les exemples observ s tendent avoir diff rent niveaux de difficult s Pour ces probl mes l algorithme de boosting tend g n rer des distributions qui se concentrent sur des exemples les plus difficiles ce qui repr sente un challenge un algorithme d apprentissage faible pour avoir une bonne performance sur ces parties plus difficiles de l chantillon d exemples L algorithme d apprentissage de BWI pr sent dans la Fig 14 apprend deux classificateurs pour reconnaitre les posit
74. devenir couteux Le langage d interrogation sur les documents semi structur tel que XQUERY ou le langage XPATH peuvent galement tre utilis s pour le d veloppement d extracteurs car ils tiennent en compte la structure arborescente de documents XML Par contre cette approche pose de probl mes parce que c est une t che difficile fastidieuse qui exige des connaissances et de l expertise En fait si la structure d une page Web change cela rend difficile la maintenance d extracteurs con us de cette facon Exemples de ce type de syst mes sont W4F Sahuguet amp Azavant 2001 et XWRAP Liu et al 2000 2 4 2 Approche par sp cification assist e l aide d une interface conviviale GUD les syst mes qui se servent de cette approche tels que OLERA Chang amp Kuo 2004 IEPAD Chang amp Lui 2001 et Lixto Baumgartner et al 2001 guident l utilisateur dans la t che de conception d extracteurs Ils analysent la structure de documents et indiquent l utilisateur des l ments extraire en lui proposant en g n ral des patrons d extraction adresse lectroniques des prix des URLs valeurs num riques etc base d expressions r guli res sur les informations pertinentes Ensuite c est l utilisateur qui les choisit selon le type de donn e extraire Pendant une interaction un extracteur peut tre d fini sans que l utilisateur n ait besoin de le manipuler directement ou de connaitre le formalisme d extraction empl
75. e quivalentes aux meilleures r gles de LP Ciravegna 2001 D ailleurs au sein du BWI la technique de boosting est utilis e pour mettre l accent sur des exemples sur lesquels l apprenant a une faible performance afin d en tirer des r gles suppl mentaires contrairement l algorithme LP qui emploie une approche d apprentissage machine plus simple reposant sur un algorithme de couverture Ciravegna 2003b Enfin pour un ensemble de document moins structur s notamment en langage naturel on peut conclure que l avantage de l algorithme LP sur les autres r side dans l effet combin de l tape d tiquetage contextuel de l tape de correction et de l utilisation plus avanc e d information TAL Ce dernier tant le plus important d entre eux TJ 6 CONCLUSION ET PERSPECTIVES 6 1 Conclusion L un des objectifs vis s de cette recherche a t d tudier l utilisation de techniques d induction d extracteurs permettant l extraction d information partir de documents de diff rents niveaux de structuration documents structur s et non structur s Pour cela il a t distingu tout d abord les concepts de base comme les types de documents la repr sentation de ces documents et le types de sorties qui sont obtenues pendant une t che d EL Ensuite diff rentes approches de conception d extracteurs ont t tudi es et l approche par induction supervis e a t retenue approche n cessitant qu un ensemble d exemples de do
76. e POS tagging gazetteer lookup dictionnaires du domaine et la reconnaissance d entit s nomm es Named Entity Recognition Les r gles d Amilcare sont apprises par la g n ralisation d un ensemble d exemples trouv s dans un corpus d apprentissage annot avec des balises XML Le syst me apprend comment reproduire une telle annotation par l extraction d information Trois types de r gles sont d finis dans l Amilcare r gles d tiquetage tagging rules r gles contextuelles contextual rules et r gles de correction correction rules Une r gle d tiquetage se compose d un ensemble de conditions sur une s quence de mots reli s et d une action d terminant si la position actuelle est un d limiteur d une instance La Fig 19 montre un exemple d une telle r gle La premi re colonne repr sente une s quence de mots De la seconde la cinqui me colonne de cette figure repr sentent respectivement tiquetage POS le type de mot gazeteer lookup et la classe des entit s nomm es laquelle le token appartient La derni re colonne repr sente l action L action Speaker indique que si le texte s assortie avec le patron le token Patrick sera identifi comme un d limiteur de d but de speaker 33 Pattern Action Word POS Kind Lookup Name Entity Punctuation Patrick NNP Word Person s first name Speaker Person Stroh NNP Word Punctuation assistant NN Word Job title
77. e dates num ros de t l phone pour en citer quelques uns pr sents dans des pages d int r t Il est fort probable qu une tape pr alable celle de la tokenisation pourrait tre tr s utile puisque l on pourrait obtenir une repr sentation plus homogene de tokens appartenant ces cat gories d informations qui sont assez courantes Par cons quent cela pourrait augmenter les performances de l algorithme BWI 79 4 Enrichissement de l tape d extraction d attributs Le syst me M TIES repose sur une repr sentation de documents par s quence de tokens Ainsi pour identifier chaque token il fait l usage d un ensemble de treize attributs Un enrichissement de la repr sentation d un document pourrait tre fait en rajoutant d autres attributs pour aider le syst me lors de l apprentissage de r gles d extraction 5 Exp rimentation avec d autres algorithmes d apprentissage Dans le domaine de l apprentissage automatique il existe de nombreux algorithmes supervis s notamment SVM Support Vector Machines et C4 5 arbre de d cision etc Ces derniers devraient pouvoir tre utilis s comme des modules d apprentissage automatique ind pendants dans M TIES 6 Evaluer le processus de filtrage Instance Filtering SIE Le syst me SIE Simple Information Extraction utilise un algorithme de classification supervis e SVM pour classifier les tokens apr s un traitement de filtrage d attributs Ce filtrage est r alis par l algorith
78. e tokens qui apparaissent avant ou apr s un champ cible dans la s quence lin aire de tokens dans un document En particulier BWI ne peut repr senter ou apprendre aucune information sur les noeuds de parent les enfants de m mes parents ou la position d enfant dans l arbre d un document XML auquel les champs cible appartiennent implicitement b L apprentissage lent L apprentissage d un seul champ avec quelques centaines de documents peut prendre plusieurs heures m me sur un ordinateur performant La lenteur dans l apprentissage rend l utilisation de grandes valeurs pour le param tre lookahead L aussi prohibitif Pour Kauchak Kauchak et al 2002 cette lenteur est due la boucle la plus interne de l algorithme d apprentissage charg e de trouver des extensions pour les s parateurs Toutes les combinaisons de motifs possibles d au plus L tokens juste avant e apr s un s parateur quelconque sont consid r es jusqu ce qu aucune meilleure r gle ne puisse tre trouv e Trouver une extension de s parateurs est exponentiel en L parce que chaque combinaison de tokens est num r e et valu e m me des valeurs modestes de L sont co teuses Dans Freitag amp Kushemerick 2000 la valeur L 3 a t normalement employ e pour obtenir un quilibre entre l efficacit et la performance Les auteurs d clarent galement que L 3 est g n ralement suffisant mais pour certaines t ches une valeur jusqu L 8 peut se faire n
79. e est correcte si elle contient une donn e extraire dans son int gralit Finalement le troisi me crit re le plus strict une donn e extraite est correcte si elle correspond exactement au caract re pr s l une des s quences extraire C est ce dernier crit re qui sera adopt dans les exp rimentations de cette recherche 2 5 2 Pr cision Rappel et F Measure La Pr cision est d finie comme la quantit d informations correctement extraites sur toutes les informations extraites tandis que le Rappel est d fini comme la quantit d informations correctement extraites sur toutes les informations extraire contenues dans les documents Ainsi le rappel mesure la quantit d informations extraites correctement parmi l ensemble 20 des informations extraire Un rappel de 100 signifie que l extracteur a bien reconnu toutes les valeurs extraire La pr cision mesure la qualit des extractions tandis que le rappel met en vidence la proportion d extractions correctes Une pr cision et un rappel de 100 indique un extracteur parfait dans le sens o il ne commet aucune erreur sur le corpus consid r De ce fait pr cision P et rappel R peuvent tre d finis par les formules suivantes pu 1 N N R 2 x 2 ou N est le nombre de slots qui ont t extraits correctement par le syst me N est le nombre total de slots qui ont t extraits par le syst me et N est le nombre total d
80. e l algorithme Adaboost Fig 15 est de concevoir un classificateur final par la combinaison de classificateurs l mentaires ces derniers obtenus partir d un algorithme d apprentissage supervis appel apprenant faible Freund amp Schapire 99 Dans BWI LearnDetector joue le r le de l apprenant faible et r alise l apprentissage des classificateurs l mentaires cd cf chaque tape de boosting AdaBoost it re n fois l apprentissage en faisant varier la pond ration des exemples d apprentissage chaque tape en amenant l apprenant faible LearnDetector se concentrer sur les exemples mal class s autrement dit sur des portions de l ensemble d apprentissage o les r gles courantes n ont pas eu de bonnes performances lors de l tape pr c dente En m me temps il construit it rativement une hypoth se initialement vide par extension des motifs gauche et droite du classificateur Un motif est tendu par l ajout d au plus L tokens chaque it ration Cette valeur L aussi appel e lookahead L ou la fen tre L est fournie l algorithme en entr e Elle informe le nombre de tokens pris en compte pendant l apprentissage de chaque d tecteur Si par exemple nous avons la fen tre L 3 cela veut dire que 3 tokens avant le d tecteur de d but du champ extraire et 3 tokens apr s le d tecteur de d but du champ sont pris en compte pendant l apprentissage d un d tecteur de d but Le contexte appris comprend alo
81. e listes le syst me applique une r gle d extraction pour identifier les d limiteurs gauche et droite de la liste de fa on similaire celle pour l identification de n uds feuille Ensuite les r gles de n uds fils pour les d limiteurs gauches sont appliqu es it rativement par toute l extension de la liste de fa on trouver tous ses items La m me proc dure est effectu e vers la direction oppos e avec les d limiteurs droits 32 des n uds fils Diff remment WIEN et SoftMealy les r gles d extractions de STALKER peuvent exprimer des disjonctions La principale limitation de STALKER est de d l guer la proc dure de r association des valeurs des composantes en n uplets l utilisateur qui se voit alors charg de la construction de l arbre EC fourni l algorithme d induction L imposition de la conception de cette proc dure l utilisateur est contraire l esprit de l induction d extracteurs partir d exemples annot s Une mise en uvre du STALKER a t d velopp e en Cabral 2004 en utilisant Document Object Model DOM pour impl menter le formalisme ECT 3 2 4 Amilcare Amilcare Ciravegna 2003a est un syst me d induction de r gles d extraction d velopp par Fabio Ciravegna de l Universit de Sheffield Il repose sur l algorithme LP Learning Pattern by Language Processing un algorithme supervis qui appartient la classe de syst mes d induction d extracteurs utilisant LazyNLP Ciraveg
82. e slot Multi slot system system Location Capitol Hill Location Capitol Hill Location Capitol Hill Bedroom 1 Bedroom 1 Price 675 Bedroom 3 Price 675 Price 995 Location Capitol Hill Bedroom 3 Price 995 Fig 10 Exemple d extractions single slot et multi slot d une page HTML adapt de Soderland 99 Sortie structur Une sortie structur e apparait quand le r sultat d une t che d extraction prend la forme arborescente Par exemple soit la liste de livres illustr e par la Fig 11 obtenue du code source d un document XHTML Ici la t che d extraction consiste obtenir pour chaque livre son titre et ses auteurs ou plus pr cis ment extraire la liste des livres et pour chacun d eux la liste de couples titre liste des auteurs Le nombre d auteurs varie d un livre l autre Dans ce cas une repr sentation sous la forme d un arbre semble plus ad quate La Fig 12 illustre que certaines balises du document d entr e ont disparus html et body et les autres balises ont t renomm es Par exemple la balise h1 est renomm e en une balise titre dans le document de sortie En plus la balise li devient livre et la balise em devient auteur Par contre il existe de nouveaux l ments qui ne correspondaient pas aucune balise du document d entr e Cela est le cas que l on constate que les balises auteurs d un m me livre ont t regroup es sous une nouvelle balise auteurs De l expos par cet exemp
83. e slots qui devraient tre extraits par le syst me Ces mesures sont inversement li es en effet quand le rappel augmente la pr cision tend diminuer et vice versa Une nouvelle mesure a t tablie qui combine les mesures pr c dentes et est appel e la F Measure La F Mesure value la qualit globale d un extracteur en combinant sa pr cision et son rappel en une mesure unique Cette mesure est exprim e par la formule B D R P B R P e F Measure o le param tre J quantifie la pr f rence du rappel sur la pr cision On fixe en g n ral 8 1 dans l quation ci dessus avec l intention d valuer des syst mes d IE en quilibrant les deux mesures et alors la formule ci dessus calcule la moyenne harmonique entre la pr cision P et le rappel R 2 6 Conclusion Pour cette recherche quant la conception d extracteurs l approche manuelle ou l approche par sp cification assist e nous sont apparues lourdes mettre en uvre car elles demandent un investissement important d expertise humaine tant en ce qui concerne le syst me d extraction que le domaine d extraction L induction non supervis n est pas retenue non plus en raison de son manque de pr cision et de la n cessit d un post traitement pour filtrer ou mieux structurer les donn es extraites En cons quence nous avons retenu une conception d extracteur selon une approche par induction supervis e en nous limitant des extracteurs unaires pour
84. ecture du syst me est illustr e par la Fig 22 La t che d EI est r alis e en deux phases dans la premi re le syst me fait des hypoth ses sur un ensemble de mod les d apprentissage partir d un corpus tiquet dans la seconde ces mod les sont appliqu s pour tiqueter de nouveaux documents Dans ces deux phases le module de filtrage d instances est utilis pour enlever certains exemples fokens du corpus en question afin d acc l rer le processus entier tandis que le module d extraction d attributs Feature Extraction est utilis pour l extraction d un ensemble pr d fini d attributs partir des exemples 35 Lors de l tape de classification le module Tag Match est utilis pour combiner les pr visions du module classificateur Tous les modules sont impl ment s en langage Java l exception des composants aux tiers Pour voir une description compl te de chaque module pr sent dans la figure ci dessous nous renvoyons le lecteur Giuliano et al 2006 B TL Corpus New D ese m TEC TS Filter Model D Frans c c e a Extraction Lexicon Extraction Script AF Script B Lesniing m ssific P Algorithm 2 i Data Model Tag D Matcher Tagged Documents Fig 22 Aper u du syst me SIE 3 2 6 TIES Trainable Information Extraction System Le syst me TIES Trainable Information Extraction System ITC IRST 2004 d velopp en 2004 par le Centro per la Ricerca Scientifica e Tecnol
85. endant l apprentissage du mod le sont tablis En plus il a t d cid de reprendre les m mes protocoles exp rimentaux utilis s par d autres travaux de recherche en EI afin d avoir des comparaisons plus pertinentes 5 3 1 Influence des Param tres de l algorithme BWI et information POS 5 3 1 1 Nombre d it rations de boosting Corpus JOBS L objectif vis des exp riences de cette section dont les r sultats sont pr sent s dans la Tab 6 et la Fig 34 est de mesurer la sensibilit de l algorithme au nombre d it rations de boosting Le param tre look ahead L 3 a t fix tandis que nous faisons varier le nombre de boosting de 10 jusqu 200 Tab 6 Influence du nombre d it rations de boosting sur le corpus Jobs Seeders O 20 30 40 70 100 200 application 0 544 0 593 0 656 0 666 0 690 0 685 0 695 area 0 383 0 455 0 492 0 534 0 581 0 618 0 631 city 0 965 0 964 0 967 0 964 0 965 0 968 0 967 country 0 987 0 991 0 986 0 988 0 988 0 984 0 982 language 0 773 0 821 0 847 0 859 0 881 0 883 0 898 plataform 0 737 0 795 0 823 0 848 0 864 0 869 0 871 post date 1 1 1 1 1 1 1 recruter 0 794 0855 0 872 0 869 0 885 0 868 0 879 state 0 967 0 974 0 964 0 977 0 973 0 977 0971 title 0 479 0 604 0 630 0 672 0 706 0 690 0 703 F1 macro 0 763 0 806 0 824 0 888 0 853 0 854 0 859 60 Jobs Corpus applic area city lang plat recr state title All 10 20 30 40 70 100 200 Boosting Iterations Fig 34 Performance
86. ent principal de la r ussite de BWI Grace cette technique l algorithme d apprentissage du BWI est capable de faire la repond ration d exemples afin d apprendre des r gles sp cifiques conduisant des r sultats plus pr cis De plus Kauchak et al Kauchak et al 2002 ont valu le syst me BWI original sur des collections de documents classifi es en trois groupes non structur s en langage naturel partiellement structur s et fortement structur s Ils l ont galement exp riment sur une collection de documents obtenue de la Libraire Nationale de M dicine MEDLINE et annot s avec des indications de types de segment de phrases par exemple segment de phrases pr positionnelles phrases nominaux etc De ce fait ils sont arriv s la conclusion que m me avec des informations grammaticales limit es le syst me pourrait avoir une sensible am lioration dans les r sultats C est dans ce contexte que les objectifs et les contributions du pr sent travail consisteront e tudier l utilisation de techniques d induction d extracteurs en mettant l accent sur l algorithme d induction d extracteurs BWI afin de r aliser l extraction d information de documents de diff rents niveaux de structuration et dans diff rents domaines e analyser l influence de l information morphosyntaxique Parties du Discours en suivant l axe des tudes propos es par Kauchak et al 2002 induction d extracteurs plus informations gram
87. ent r guli re De plus pour des slots courts des d tecteurs individuels m morisent souvent des exemples du slot cible quand le contexte n est pas utile La version actuelle du tokeniseur du M TIES est optimis e pour identifier le plut t t possible des instances de dates heures et abr viations plus courantes Cela pourrait expliquer le meilleur r sultat pour le slot etime qu il a obtenu Enfin le slot stime il semble qu il faut plus de contexte pour obtenir un bon score L approche d induction d extracteurs plus orient au traitement linguistique du LP obtient alors le meilleur score b Corpus Jobs Dans la Tab 12 les meilleurs scores pour chaque slot sont en gras il faut remarquer que le score all slots de tous les syst mes sont exprim s en F measure micro sauf pour le GATE SVM qui emploie la F measure macro Li et al 2004a Ciravegna 2003b D une facon g n rale tous les syst mes ont pr sent des performances uniformes sur ce corpus M TIES a atteint les meilleurs scores en 11 slots sur 17 tandis que le syst me Amilcare a t plus performant en 6 slots Cependant ces diff rences de performance sont tr s faibles D autres slot tels que id identification du message et post date sont fortement r guliers ils font partie des m tadonn es de message ce qui explique les r sultats sup rieurs de tous les syst mes En particulier M TIES et LP ont obtenu un score parfait pour les slot post date et id r
88. es pourcentages capitalized token true pour des tokens qui commencent avec une lette en majuscule lower case token true pour des tokens qui contiennent seulement lettres en minuscules punc token true pour des signes de ponctuation 43 upper case token true pour des tokens qui contiennent seulement lettres en majuscules single char token true pour un token compos d un caract re date token true pour des dates time token true pour des heures abbr_token true pour des abr viations symb token true pour des symboles Le feature extractor g n re seulement des attributs jug s actifs true dans un exemple Tous les autres attributs sont jug inactifs ou false 4 2 3 Configuration du syst me TIES TIES est impl ment en utilisant un ensemble de modules Les modules ont un certain nombre de propri t s param trables et ils impl mentent une ou plusieurs interfaces Ces modules peuvent tre configur s de fa on flexible en employant des fichiers XML Chaque module est d crit par un l ment XML avec des sous l ments et des attributs utilis s pour d finir les propri t s de modules En sp cifiant quels modules et leurs attributs employer on atteint une grande flexibilit dans le contr le des caract ristiques d une instance de TIES 4 2 3 1 tape d apprentissage g n ration d un mod le Le fichier de configuration pour l tape d apprentissage est le fichier TIES
89. espectivement Pour M TIES le plus grand cart positif de performance a t celui du slot title Par contre le plus grand cart n gatif a t pour le slot des degree En analysant les annotations pour le premier slot on voit quil a une taille tr s variable et qui son contenu est plus 12 important que son contexte pour bien l identifier D autre part la faible repr sentation d occurrences du slot des degree 21 au total explique ce score faible Des tests de signification statistiques peuvent montrer que les syst mes compar s sur ce corpus ne sont pas nettement diff rents les uns des autres 5 44 Comparaison sur le corpus Call For Papers CFP La Tab 13 montre les r sultats obtenus par les syst mes SIE Yaoyong Amilcare et M TIES Tous les syst mes ont utilis s la validation crois e k 4 comme m thode d valuations pour la t che de template Pour les performances des syst mes compar s dans cette section on s appuie sur les r sultats donn s dans Ireson et al 2005 Le corpus CFP a subi un pr traitement par le syst me GATE qui fournit la tokenisation des attributs orthographiques taggage POS et NER Location Person Date etc Ces attributs constituent un ensemble de base en termes de traitement linguistique Les syst mes SIE et Yaoyong utilisent des classificateurs SVM chaque balise a t apprise ind pendamment et elles sont ensuite combin es Le premier emploie la technique instance filtering pou
90. eut ajuster la pr f rence entre pr cision et rappel ou T 0 d signe la configuration avec le maximum rappel possible et 7 21 le maximum de pr cision 3 1 4 5 Limitations de BWI D apr s les r sultats montr s par Kauchak et al 2002 l apprentissage de l algorithme BWI et des m thodes similaires peuvent avoir de honorables performances quand elles sont appliqu es sur diff rents types de corpora Cependant il identifie deux majeures limitations de l algorithme BWI a Expressivit limit e de s parateurs Les s parateurs sont con us pour capturer le contexte plat et voisin d un champ extraire en apprenant de courtes s quences de tokens qui les entourent BWI obtient une haute pr cision gr ce la capture de l information s quentielle et r guli re autour de la donn e extraire Toutefois pour des textes partiellement structur s et en langage naturel les s parateurs ne sont pas aussi efficaces cause de r gularit s dans le contexte qui sont moins consistant et fiables Normalement dans ces types de documents de nombreux s parateurs couvrent seulement un ou quelques exemples et collectivement les s parateurs peuvent avoir un faible rappel Une seconde limitation des s parateurs est qu ils ne peuvent pas repr senter la structure grammaticale des phrases ou la plupart des informations structurales dans les documents libre La raison de cette limitation est qu ils ne peuvent que capturer les informations sur l
91. faut rappeler que des comparaisons vraiment justes et fiables sont probl matiques en raison de crit res d valuations d j pr sent s dans la section pr c dente 5 4 3 Comparaison sur les corpora Seminars et Jobs Les corpora Seminars et Jobs ont t utilis s par plusieurs syst me d apprentissage soit ceux orient s vers l induction d extracteurs soit ceux plus orient s au traitement linguistique Les comparaisons sur ces corpora deviennent probl matiques parce que diff rents syst mes suivent diff rents protocoles exp rimentaux Pour les exp riences avec le syst me M TIES la m thode d valuation hold out avec 5096 de documents pour l apprentissage et 5096 pour le test a t utilis e puis le syst me est ex cut apprentissage et test 10 fois et le r sultat final est la moyenne de tous les ex cutions random split 50 50 10 fois De nombreux syst mes d EI valu s sur ces corpora ont employ cette m thode d valuation donc les r sultats de cette section a suivi la m me m thodologie avec l objectif d obtenir des r sultats plus fiables et justes Les tables 9 et 10 r sument la configuration des syst mes comparer sur les corpora Seminars et Jobs Tab 9 R sum de configuration des syst mes valu s sur le corpus SEMINARS Syst me M thode d valuation Attributs utilis s W LP Random split 50 50 10 fois Word capitalisation et POS 5 Word capitalisation token GATE SVM Random spli
92. formation over the Web using ontologies RECIIS Journal vol 2 no 1 pp 73 84 2008 Freitag 1997 Freitag D Using grammatical inference to improve precision in information extraction In ICML 97 Workshop on Automation Induction Grammatical Inference and Language Acquisition Morgan Kaufmann 1997 Freitag amp McCallum 1999 Freitag D McCallum A K Information Extraction with HMMs and shrinkage In Proc Of the AAAI 99 Workshop on Machine Learning for Information Extraction 1999 Freitag amp Kushemerick 2000 Freitag D Kushmerick N Boosted Wrapper Induction In Proceedings of the Seventeenth National Conference on Artificial Intelligence AAAI 2000 2000 Freund amp Schapire 1990 Freund Y Schapire R E A decision theoric generalization of on line learning and an application to boosting Proc Of the 2th European Conf on Computational Learning Theory Rochester NY ACM Press pp 202 216 1990 Freund amp Schapire 1996 Freund Y Schapire R E Experiments with a new boosting algorithm In International Conference on Machine Learning pp 148 156 1996 84 Freund amp Schapire 1997 Freund Y Schapire R E A decision theoretic generalization of on line learning and an application to boosting Journal of Computer and System Sciences 55 10 119 139 August 1997 Freund amp Schapire 1999 Freund Y Schapire R E A short introduction to boosting Journal of Japanese Society for Artificial
93. g in the preprocessing phase of the proposed IE system In order to evaluate the performance of the system several experiments were carried out on three standard corpora for the template filling task Other experiments were also conducted using various combinations of features in order to systematically study their effects on the performance of the learning algorithm Results obtained experimentally showed that the perfomance of the proposed system is comparable with other state of the art IE systems Keywords Information Extraction Wraper Induction Boosting Supervised Classification Part of Speech Tagging Machine Learning xi xil Table de Mati res 1 INTRODUCTION sitpieeiee ees ER oup PER needs sn ire tt nn entres eee 1 1 1 Contexte Syst mes de collecte d information sur des domaines restreints Master WebPACHA THE miniai nn sn eate eto tn in nt paras 4 2 Str cture qu me HOIE 655 oo ARD Re Tr nn vee eee 5 2 EXTRACTION D INFORMATION 2 iciscacessseccsesscssseossecsescsossceesosensseacessdesesoosesessascseseos 7 2 Traitement Automatique de la Langue TAL 9 2 1 1 Exemple d un syst me d EI reposant sur des techniques de TAL 9 2 2 Types de Documents ieu tan lient 10 2 2 Documents DON SIEUCIUTES cane ep aceite oie eda etui Cet estes 10 2 2 2 Documents semi sITUCtules c ce Sede I Ci sn 11 2 2 3 Documents SCUCDUFeS ooo eod sol lel cae ede oi tuu eae eee 12 2 22 BIAN s oso triti A
94. gna 2003a Ciravegna F Designing adaptive information extraction for the semantic web in Amilcare In S Handschuh and S Staab editors Annotation for the Semantic Web Frontiers in Artificial Intelligence and Applications IOS Press Amsterdam 2003 Ciravegna 2003b LP Rule Induction for Information Extraction Using Linguistic Constraints Technical Report CS 03 07 Departament of Computer Science Univ of Sheffield Sheffield September 2003 Cohen et al 2003 Cohen W Hust M Jensen L Web Document Analysis Challenge and Opportunities World Scientific 2003 Cornu jols amp Miclet 2002 Cornu jols A Miclet L Apprentissage Artificielle concepts et algorithms Eyrolles 2002 Cowie amp Lehnet 1996 Cowie J and Lehnet W Information Extraction Communication of ACM vol 39 1996 Cortes amp Vapnik 1995 Cortes C Vapnik V Support Vector Networks Machine Learning 20 3 273 297 1995 Crescenzi et al 2001 Crescenzi V Mecca G Merialdo P Roadrunner Towards automatic data extraction from large web sites In Proceedings of 27th International Conference on VLDB 2001 Crespo et al 1994 Crespo A Jannink J Neuhold E Rys M Studer R A survey of semi automatic extraction and transformation Techinical report 1994 Cunningham et al 2002 4 Cunningham H Maynard D Tablan V Ursu C Bontcheva K Developing language processing components with GATE www gate ac uk 2002 83 Cu
95. h ma d extraction et quelques statistiques pertinentes 5 1 1 Annotation de documents A fin d utiliser des algorithmes d EI supervis s du M TIES sur une collection de documents il faut disposer d un ensemble d apprentissage d exemples positifs annot s Il faut r aliser cette annotation et faire en sorte que celle ci soit compatible avec le format TIESIF le seul format d entr e accept par M TIES Par cons quent les exemples positifs qui serviront pour l apprentissage du syst me seront annot s de la facon suivante Fig 30 doc id 276 filename cmu cs proj vision 273 0 581t 0 25 4 84 12 33 15 9 0 amp gt Type cmu cs proj vision Topic Sanderson group seminar Dates 27 Apr 84 Time lt stime gt 2 30 lt stime gt PostedBy on 25 Apr 84 at 12 33 from Abstract lt speaker gt Alberto Elfes lt speaker gt will be speaking about A Wide Beam Sonar Mapping System on Friday the 27th in lt location gt WeH 4623 lt location gt at lt stime gt 2 30 lt stime gt lt doc gt Fig 30 Exemple d un document correctement annot en XML 53 La Fig 30 illustre comment il faut annoter les exemples positifs Ainsi il faut signaler chaque champs slot d information en les entourant avec des balises ouvrantes lt stime gt et celles fermantes correspondantes lt stime gt en respectant la syntaxe XML Bray et al 2008 Les balises doc et doc indiquant le d but et respectivement la fin du document
96. ies du texte non pertinent comme certains mots utilis s comme menu de navigation l en t te et le titre de bas de page commun dans toutes les pages d un site etc Il galement restructure le texte avec un codage de base de la structure de la page l aide d un ensemble minimum de symboles pour marquer le commencement d en t tes de paragraphes et d l ments de listes Cet outil peut tre tr s utile pour construire un corpus partir des pages Web Il a t valu dans la premi re comp tition CleanEval en septembre 2007 CleanEval une comp tition d valuation sur le th me de nettoyage de pages Web arbitraires avec l objectif de pr parer des donn es Web comme un corpus pour la recherche et le d veloppement de la technologie linguistique Dans ce projet HTMLCleaner a t utiliser comme outil de nettoyage de pages Web des corpora et pour v rifier et corrig s les balises HTML manquantes en les transformant donc en fichiers XHTML bien form s En plus il a fallu le d veloppement d un programme en Java pour adapter HTMLCleaner aux besoins de services de nettoyage de pages HTML et de mise en forme en suivant le standard XML 4 3 2 Extension du module de tokenisation par l ajout de tagage POS Le traitement de texte libre par TIES s est rendu possible en ajoutant un tiqueteur POS son module de pr traitement Fig 27 L outil QTAG Mason amp Tufis 1998 a t adopt pour r aliser l analyse morphosyntaxique auto
97. ine et les syst mes d IE n ont pas pour objectif de comprendre les textes trait s mais de r duire les informations textuelles ventuellement non structur es qui y figurent aux structures tabulaires de manipulation plus facile Kushmerick amp Thomas 2003 Ainsi il est possible d extraire automatiquement des informations textuelles depuis des d p ts num riques tels que les descriptions et les prix des produits dans les magasins virtuels et de les utiliser pour construire la base de donn es pour des analyses et comparaisons ult rieures Diverses recherches ont t men es pour d velopper des syst mes d IE adapt s diff rents types de textes par exemple en allant des pages HTML rigidement structur es cr es partir de bases de donn es Chang amp Lui 2001 jusqu aux des Call for Papers CFP Ireson amp Ciravegna 2005 crites en langage naturel Pour ce second type de texte en particulier de nombreux travaux ont t d velopp s qui montrent que de tels syst mes sont difficiles d velopper et exigent un investissement important de sp cialistes dans le domaine de l application et d EI Siefkes amp Siniakov 2005 De ce fait de nombreuses recherches ont t d j men es dans le d veloppement de syst mes d EI de plus en plus adaptables aux domaines les plus divers Tang et al 2007 Ces syst mes d EI adaptatifs reposent sur induction de wrappers extracteurs Un extracteur dans le contexte d EI es
98. int gr e plus pr cise et fine afin d augmenter la performance du sous syst me d extraction de l architecture MasterWeb AGATHE Espinasse et al 2007 Freitas et al 2008 voir section 1 1 Suite cette recherche il sera envisag de combiner la t che symbolique du syst me MasterWeb AGATHE qui r alise actuellement une classification des pages Web base d ontologies avec une t che d extraction d information adaptative permettant d extraire de l information sur ces pages Web class es ceci par l usage de techniques d apprentissage artificiel machine learning et traitement de langage naturel Plus pr cis ment il est attendu une am lioration de la performance des sous syst mes d extraction de ces architectures en les dotant des techniques d induction automatique d extracteurs d information et de traitement de langage naturel travers l utilisation de l architecture d EI propos e par ce travail 1 1 Contexte Syst mes de collecte d information sur des domaines restreints MasterWeb AGATHE Le syst me AGATHE Espinasse et al 2007 Freitas et al 2008 est une architecture logicielle g n rique permettant le d veloppement de syst mes de collecte d information sur le Web sur un ou plusieurs domaines restreints AGATHE met en uvre une collecte coop rative d information base d agents logiciels et d ontologies Ce syst me prend en compte des contextes de recherche en consid rant des regroupements de pages Web rela
99. ions d but pd et les positions fin pf En fait on se sert de la classification supervis e CS pour classer les exemples de d but qui jouent le r le des positifs et tous les autres exemples sont consid r s comme n gatifs Cela aboutit un classificateur qui d termine les exemples de type d but De fa on analogue la CS caract rise les exemples de type fin jouant cette fois ci le r le de positifs et tous les autres tant consid r s comme n gatifs Un classificateur qui identifie les exemples de type fin est produit Finalement l algorithme construit un histogramme H 4 f de fr quence des tailles en nombre de tokens du champ extraire permettant d associer les positions d buts et fins dans une tape post rieure En d autres termes pour chaque champ extraire l algorithme apprend la distribution de probabilit de la longueur d un champ en consignant le nombre de tokens dans chacun de ses exemples de corpus et en normalisant cet histogramme en une distribution de probabilit la fin de la phase d apprentissage procedure BWI example sets S and E F AdaBoost LearnDetector S A AdaBoost Learn Detector E H field length histogram from S and E return wrapper W F A H Fig 14 L algorithme d apprentissage de BWI Freitag amp Kushmerick 2000 L apprenant faible est celui qui fournisse une hypoth se qui fasse mieux qu un classificateur al atoire 26 Algorithme AdaBoost L id e principale d
100. junction JJ adjective JJR adjective comparative JJS adjective superlative LS list item marker MD modal NN noun singular or mass 89 90
101. le une sortie structur e r sultante d une telle t che d EI peut tre potentiellement complexe 17 hi Harry Potter N os Nouveau et les reliques Rowling D sordre Finkelkraut Bruckner dela mort tte Fig 11 Structure arborescente d un document HTML contenant une liste de livres adapt de Marty 2007 livres ue livre titre ii i titre auteurs man Puis auteur Nouveau auteur auteur poc pes D sordre e la mo Amoureux Rowln Finkelkraut Bruckner Fig 12 Sortie structur extrait du document HTML de la Fig 11 adapt de Marty 2007 2 4 Conception d extracteurs Rappelons qu un extracteur est d finit comme tant un programme qui produit automatiquement des informations structur es partir d un ensemble de documents D apr s Chang et al 2006 on peut classifier les approches pour construire un extracteur en 4 classes quant au niveau d interaction entre le syst me et l utilisateur 1 approches manuelle 2 approche par sp cification assist e 3 approche par induction supervis e d extracteurs et 4 approche par induction non supervis e 18 2 4 1 Approche manuelle Dans cette approche en employant des langages de programmation g n raux tels que Perl Java ou des expressions r guli res pour l extraction de portions de textes le d veloppeur programme manuellement un extracteur pour un site Web quelconque Ainsi une forte comp tence de programmation est requise et cela peut
102. le corpus mais elle est fiable seulement si elle est utilis e lors de la fermeture d un d limiteur speaker Pattern Action Word POS Kind Lookup Name Entity Punctuation Word Person s first name Speaker Person Word Punctuation assistant NN Word Jobtitle professor NN Word Fig 20 Exemple d une r gle d tiquetage g n ralis Tang 2007 34 Enfin les r gles de correction sont identiques aux r gles d tiquetage mais ses patrons assortissent aussi des balises ins r es par des r gles d tiquetage et ses actions tout simplement d placent les balises mal positionn es plut t que d ajouter de nouvelles r gles Un exemple d une r gle de correction initiale pour le d placement de stime dans at stime 4 lt stime gt pm est illustr par la figure suivante condition action word wrong tag move tag to lt stime gt lt stime gt Fig 21 L action d place la balise de la mauvaise position la bonne Ciravegna 2001 3 2 5 SIE Simple Information Extraction SIE Simple Information Extraction Giuliano et al 2006 est un syst me d EI fond sur une technique d apprentissage supervis o la t che d EI est trait comme un probl me de classification en appliquant des Machines Vecteurs de Support ou S parateur Vastes Marges SVM Cortes amp Vapnik 1995 pour tablir un ensemble de classificateurs qui d tectent les d
103. les BWI d extraction r gles d extration XML Informations extraites XML Fig 27 Nouvelle architecture du TIES M TIES 48 4 3 1 Am lioration du pr traitement 4 3 1 1 Module d annotation de documents MnM Bien que ce module ne soit pas vraiment int gr dans l architecture de M TIES et pour cela il ne soit pas illustr dans la Fig 27 il a t retenu pour bien s adapter aux besoins de notre recherche MnM consiste d un outil d annotation automatique de documents qui int gre un navigateur Web et un diteur d ontologie Vargas Vera 2002 En plus il fournit une API pour faire le lien avec des serveurs d ontologies et pour l int gration d outils d EI Cet outil peut tre consid r comme un exemple pr coce de la prochaine g n ration des diteurs d ontologies orient s vers l tiquetage s mantique et en plus qui fournit des m canismes pour l tiquetage automatique grande chelle de pages Web La Fig 28 montre la fen tre principale de l interface du MnN gauche il pr sente l ontologie de r f rence qui guide l utilisateur dans le processus d annotation La fen tre droite affiche les pages Web du corpus annoter avec les balises qui sont d finies par les classes de l ontologie de r f rence Des guides de l utilisateurs d veloppeur qui pr sentent l outil MnM en d tails peuvent tre trouv sur le site Internet d die a son projet MnN 2008 ll nM v2 Tool lni xj File Edi
104. limiteurs d entit s extraire Il a t congu avec le but d tre rapidement portable diff rents domaines Une s rie d exp rimentations sur plusieurs domaines ont prouv que SIE est comparable en performance aux syst mes d j introduits dans l tat de l art et plus performant que quelques syst mes qui ont t congus pour des domaines sp cifiques En outre ce syst me a t test sur diff rents domaines en utilisant la m me configuration de base sans employer aucune connaissance sp cifique telles que des gazetteers et pr post traitement ad hoc Une caract ristique majeure de SIE est de r duire l effort du traitement de tokens en exploitant une nouvelle technique nomm e nstance Pruning Gliozzo et al 2005 filtrage d instances qui permet le traitement de nombreux documents en appliquant un filtrage sur les tokens d un document Cela s est av r tr s efficace pour le traitement des donn es en bioinformatique SIE a une architecture modulaire o les composants du syst me sont combin s en pipeline o chaque module restreint les structures de donn es fournies par les modules pr c dents Cette architecture modulaire apportent des avantages significatifs elle est d abord plus simple impl menter ensuite elle permet d int grer facilement diff rents algorithmes d apprentissage enfin elle permet si n cessaire un r glage fin une t che sp cifique en sp cialisant simplement quelques modules L archit
105. ll present a seminar entitled Embedded Commitment on Thursday May 4th from 4 5 30 in PH 223D Laura Petitto Department of Psychology McGill University Thursday May 4 1995 12 00 pm Baker Hall 355 Fig 31 Exemple d un document du corpus Seminars Freitag 1997 54 5 1 2 2 D finition du Template d extraction Pour chaque document de ce corpus il faut identifier et extraire les informations suivantes location endroit de la conf rence speaker nom du conf rencier stime heure de d but etime heure de la fin de la conf rence La table suivante montre des statistiques sur le corpus Seminars Tab 3 Nombre d exemples positifs pour les slots location speaker stime etime et d exemples n gatifs non annot s non entity du corpus Seminars Location Speaker Stime Etime Non Entity 5 1 2 3 Exemples de sorties d extractions La Fig 32 illustre deux sorties d une m me t che d extraction sur un document du corpus Seminars Nous pouvons noter que certaines instances du template peuvent tre compl tement remplies et d autres sont partiellement remplies speaker Prof John Skvoretz speaker Mike Greenberg location PH 223D location stime 4 00 ou 4 stime 3 30 PM etime 5 30 etime a b Fig 32 Exemples de template d extraction compl te rempli a et partiellement rempli b la fin d une tape d extraction 5 1 3 Corpus JOBS 5 1 3 1 Description du corpus Le corpus JOBS c
106. lques unes 2 1 1 Exemple d un syst me d EI reposant sur des techniques de TAL GATE General Architecture for Text Engineering Cunningham amp Maynard 2002 a est un ensemble d outils logiciels d velopp s en Java l Universit de Sheffield partir de 1995 et largement utilis par de nombreuses communaut s scientifiques entreprises enseignants tudiants pour le traitement du langage naturel en diff rentes langues La communaut de d veloppeurs et de chercheurs autour de GATE est impliqu e dans plusieurs projets de recherche europ ens comme TAO Transitioning Applications to Ontologies et SEKT Semantically Enabled Knowledge Technology SEKT 2006 GATE offre une architecture une interface de programmation d applications API et un environnement de programmation graphique Il comporte un syst me d EI nomm ANNIE A Nearly New Information Extraction System Cunningham et al 2002 b lui m me form de plusieurs modules parmi lesquels un analyseur lexical un gazetteer dictionnaire g ographique un parseur de phrases avec d sambig isation un tiqueteur morphosyntaxique POS tagging un module d extraction d entit s nomm es et enfin un module de d tection de cor f rences GATE est d j mis en uvre en anglais espagnol et fran ais Il existe de nombreux plugins d apprentissage automatique Weka RASP MAXENT SVM light d autres pour la construction d ontologies WordNet pour l interrogation
107. m dernier acc s en juin 2009 87 Seymore et al 1999 Seymore K McCallum A Rosenfeld Learning hiddem Markov Model strutucture for Information Extraction In AAAI 99 Workshop on Machine Learning for Information Extraction Siefkes amp Siniakov 2005 Siefkes C Siniakov P An overview and classification of adaptive approaches to information extraction Journal on Data Semantics IV Berlin Germany Springer 2005 Soderland 1999 Soderland S Learning information extraction rules for semi structured and free text Machine Learning 34 1 3 233 272 1999 Tang et al 2007 Tang J Hong M Zhang D Liang B Li J Information Extraction Methodologies and Applications DCS Tsinghua University 2007 Thomas 2005 Thomas B Machine Learning of Information Extraction Procedures An ILP Approach PhD Thesis Universit t Klobentz Landau 2005 Vargas Vera 2002 Vargas vera M Motta E Domingue J Lanzoni M Ciravegna F MnM Ontology Driven Semi Automatic and Automatic Support for Semantic Markup Springer Verlag pp 379 391 2002 Yang amp Liu 1999 Yang Y Liu X A Re Examination of Text Categorization Methods In Proceedings of ACM SIGIR Conference on Research and Development in Information Retrieval pp 42 49 1999 Wang amp Locovsky 2002 Wang J Lochovsky F H Wrapper induction based on nested pattern discovery Technical Report HKUST CS 27 02 Department of Computer Science Hong Kong Univer
108. mas 2003 Kushmerick N Thomas B Adaptive Information Extraction Core Technologies for Information Agents 2003 Laporte 2000 Laporte M Mots et niveau lexical Pierrel J M ed Ing nerie des langues Informatique et systemes d information ch 1 pages 25 50 Hermes Science Paris 2000 Lavelli A et al 2004 Lavelli A Califf M E Ciravegna F Freitag D Giuliano C Kushmerick N Romano L IE Evaluation Criticisms and Recommendations In AAAI 2004 Workshop on Adaptive Text Extraction and Mining 2004 Li et al 2004a Li Y Bontcheva K Dowman M Roberts L Cunningham H D2 1 1 Ontology Based Information Extraction OBIE v 1 SEKT deliverable University of Sheffield 2004 Li et al 2004b Li Y Bontcheva K Cunningham H SVM Based Learning System for Information Extraction Deterministic and Statistical Methods in Machine Learning 2004 319 339 2004 Li et al 2003 Li Y Shawe Taylor J The SVM with uneven margins and Chinese document categorization In Proceedings of The 17th Pacific Asia Conference on Language Information and Computation PACLIC17 pages 216 227 Singapore Oct 2003 Liu et al 2000 Liu L Pu C Han W XWRAP An XML enabled wrapper construction system for web information sources In ICDE pp 611 621 2000 Marty 2007 Marty Patrick Induction d extraction n aire pour les documents semi structur s Th se Doctorat Universit Charles de Gaulle Lille 3 2007 M
109. maticales sur les extractions faites par l algorithme d induction d extracteurs BWI en utilisant une collection de documents en langage naturel pour valuer quantitativement le gain que cette information peut apporter l algorithme proposer une architecture logicielle reposant sur l induction d extracteurs supervis e pour l EI partir de pages Web Cette architecture logicielle sera pr sent e ainsi que les diff rents modules sp cialis s qui la compose dont le module central mettra en uvre l algorithme d apprentissage BWI et qui sera modifi pour la prise en compte du traitement du langage naturel annotation morphosyntaxique Cela aboutira l environnement d EI adaptatif M TIES facilement configurable et convivial l utilisateur par le biais d une architecture modulaire destin l utilisation sur plusieurs types de documents structur s et non structur s comparer l architecture d EI propos e dans cette recherche avec d autres syst mes de l tat de l art au travers diff rentes exp rimentations sur trois collections de documents de r f rence en suivant une rigoureuse m thodologie d valuation de r sultats bien tablie dans la communaut scientifique du domaine de l EI Pour cela il sera d fini un protocole exp rimental pour bien mener les exp riences afin d avoir de r sultats plus fiables et pertinents utiliser le potentiel d induction d extracteurs dans le contexte d une extraction d information
110. matique d un corpus d entr e apr s l tape de tokenisation Par d faut la tokenisation de TIES g n re un fichier en format TIESIF sans prise en compte de l annotation morphosyntaxique L id e ici est de prendre ce fichier et y ins rer les tiquettes POS de chaque token propos s par QTAG tout en respectant le format TIESIF De ce fait le module d apprentissage de TIES peut enfin exploiter un corpus enrichi avec des informations morphosyntaxiques Ci apr s nous d crivons l tiqueteur QTAG 4 3 2 1 Module d tiquetage morphosyntaxique POS tagging QTag QTag Mason amp Tufis 1998 est un tiqueteur POS tagger stochastique de parties du discours Il cr e le lexique l ensemble d tiquettes fags les probabilit s lexicales et contextuelles partir du corpus manuellement tiquet Gr ce cette base d apprentissage l tiqueteur POS peut trouver les tiquettes possibles avec leur fr quence pour les assigner chaque unit lexicale dans un nouveau corpus d j segment Enfin l tiqueteur POS effectue la t che de d sambiguisation en utilisant les distributions probabilistes apprises partir du corpus Cela signifie qu il lit le texte et pour chaque foken y pr sent il renvoie partie du discours qu il appartient par exemple nom verbe ponctuation etc Il fonctionne en utilisant des m thodes statistiques d o le stochastique vient Par cons quence il peut commettre des erreurs comme tous les
111. me nstance Filtering Gliozzo et al 2005 qui indique avec une valeur vraie ou fausse si le token doit tre consid r par l algorithme de classification Il a t d montr que cette approche donne de bons r sultats en diminuant la quantit de tokens tenir en consid ration par l algorithme d apprentissage lors de la g n ration des hypoth ses et ce qui a t le plus important que ce filtrage a tr s peu d influence sur les r sultats en les comparant avec les approches qui utilisent toute l int gralit de tokens d un corpus 7 Am liorer l tape de tokenisation Afin d am liorer la tokenisation il serait int ressant d ajouter au syst me un module tokeniseur sp cialis dans les sous t ches de lemmatisation NER et chunking en anglais et fran ais Dans l EVALITA 2007 une nouvelle initiative consacr e l valuation des outils de TAL un l outil appel TextPro Pianta et al 2008 a obtenu le deuxi me classement comme outil plus performant dans quasiment toutes les sous t ches de TAL en anglais et italien voqu ci dessus Pour le fran ais l outil TreeTagger Schmid 1994 est un bon candidat en tant qu tiqueteur POS et lemmatiseur On pourrait envisager ainsi l int gration de ces modules au M TIES afin d avoir d autres exp rimentations sur des corpora en langage naturel 8 Persistance de r gles XML dans une base de donn es Afin de faire la mise en application des r gles extraites sous format XML a
112. mentos Web Wrappers s o procedimentos para extrair dados de documentos A indu o de wrappers definida como uma t cnica de extra o de informa o que usa algoritmos de aprendizado de m quina para automaticamente construir wrappers a partir de um corpus previamente anotado e que tem mostrado bons resultados quando aplicada em textos estruturados semi estruturados e livres em linguagem natural Este trabalho prop e um sistema d EI baseado em Boosted Wrapper Induction BWI um algoritmo de indu o de wrappers supervisionado no qual um outro algoritmo o AdaBoost usado para gerar um procedimento gen rico de extra o que combina no final do processo um conjunto de wrapers espec ficos por voto ponderado Alguns autores tem estudado como as t cnicas de boosting contribuem ao sucesso do algorithmo BWI e examinado sua perfomance tomando a dire o desafiadora de us lo como um m todo de extra o de informa o para documentos n o estruturados em linguaguem natural Este fato foi a principal motiva o para se incluir Parts of Speech POS tagging na fase de pr processamento do sistema d EI ora proposto Afim de se avaliar o desempenho do sistema v rios experimentos foram executados usando se tr s corpora como testbed para a tarefa de extra o de informa o no preenchimento de esquemas de extra o template filling task Outros experimentos foram tamb m conduzidos usando se diversas combina es de atributos para
113. mon premier jour au LSIS m a aid plusieurs fois dans mon int gration la vie universitaire et son poux Mathieu Detraux pour les bons moments que nous avons tous v cus ensemble Finalement je remercie tout particuli rement la merveilleuse famille Espinasse Bernard Sabine Sabrina Vanessa et Valentin qui m ont chaleureusement accueilli vii Je ne sais pas ce que je peux para tre aux yeux du monde mais pour moi m me il me semble que je n ai t qu un enfant jouant sur le rivage et s y amusant trouver de temps en temps un galet plus lisse ou un coquillage plus beau que les autres tandis que le grand oc an de la v rit s tendait encore inconnu devant moi Isaac Newton la fin de ces jours vers 1727 viii Resumo A Extra o de Informa o EI compreende t cnicas e algoritmos que realisam duas tarefas importantes a identifica o de informa es desejadas a partir de documentos estruturados e n o estruturados e o armazenamento dessas informa es em um formato apropriado para uso futuro Este trabalho concentra se nos sistemas d EI adaptativos que podem ser customizados para novos dom nios atrav s de um processo de treinamento Machine Learning usando cole es de documentos anotados como entrada Particularmente t cnicas de indu o autom tica de wrappers s o estudadas para extra o de informa o que se baseiam na explora o de regularidades estruturais encontradas em docu
114. n avec ou non prise en compte de la syntaxe du langage naturel c est dire avec ou non tiquetage morphosyntaxique 52 S EXPERIMENTATIONS Ce chapitre r alise une s ries d exp riences avec l objectif d valuer la version modifi e du syst me TIES dor navant M TIES sur 3 corpora constitu s de documents diff rents niveaux de structuration Apr s la description de ces corpora le protocole exp rimental d fini par une m thodologie d valuation et quelques recommandations afin d avoir de r sultats plus fiables sont pr sent es Tout d abord des exp riences pour d terminer les meilleurs param tres de l algorithme BWI lors de la g n ration de mod les sont r alis es Ensuite on value les mod les appris sur ces corpora afin de v rifier le gain que l information POS peut apporter la performance du syst me Ce chapitre se termine en pr sentant une valuation comparative de syst me propos dans cette recherche avec d autres syst mes existants 5 1 Corpora choisis Cette section pr sente les corpora choisis pour valuer le syst me d EI propos sans prise en compte d analyse morphosyntaxique ou avec une telle prise en compte Pour cela trois corpora de niveaux de structuration Seminars Jobs et Call For Papers ont t retenu Dans un premier temps le processus d annotation de documents de ces corpora est d cri puis ces corpora sont examin s en d tail notamment leurs descriptions leurs templates sc
115. n syst me d EI d velopp dans le cadre du Project SEKT qui utilise l algorithme SVM pour la classification supervis e de tokens Ce syst me emploie une variante du SVM le SVM avec uneven margins qui a une meilleure performance de g n ralisation que le SVM original sur un ensemble o le nombre d exemples positifs sont beaucoup moins repr sentatifs que les n gatifs Li et al 2003 Il a t test sur plusieurs corpora Seminars Jobs CoNLL 2003 pour en citer quelque uns Il peut utiliser plusieurs combinaisons d attributs word capitalisation POS gazeteers lemmatisation etc L extraction d attributs est perform e par GATE Yaoyong Le syst me Yaoyong Ireson et al 2005 est le pr d cesseur du GATE SVM et ses classificateurs utilisent une fen tre de contexte de 10 tokens gauche et droite Cette version ci faisait l usage d attributs des tokens suivants token capitalisation tokenkind et informations des entit s Le tagage POS ne figurait pas dans cette liste Cette version a 69 particip dans las comp tition Pascal Challenge sur l valuation d apprentissage machine pour TEI Par la suite le syst me M TIES est compar e avec les syst mes SIE LP section 3 3 GATE SVM Yaoyong et Rapier sur le corpora choisis en essayant de suivre les m me protocole exp rimental r sultats rapport s m thode d valuation etc ou les plus proche possible pour que l on puisse avoir de comparaisons plus pertinentes Il
116. na 2001 LazyNLP aussi nomm Shallow NLP faire l usage de TAL pour g n raliser des r gles d extraction au del de la structure plate de mots tout en conservant l efficacit sur les textes fortement structur s Ce syst me essaie d apprendre le meilleur le plus fiable niveau d analyse linguistiques utile pour une t che sp cifique d EI en combinant des strat gies peu ou tr s profondes d analyse linguistiques L apprenant commence induire des r gles qui ne font aucune utilisation de l information linguistique comme dans les syst mes d EI classiques Puis il ajoute progressivement l information linguistique ses r gles s arr tant quand l utilisation de telles informations devient incertaine ou inefficace Les modules de TAL fournissent des informations linguistiques et de ressources d finies une fois pour toutes ils ne peuvent pas tre modifi s par l utilisateur lors de son emploie dans une application sp cifique Les apprenants LazyNLP apprennent la meilleure strat gie pour chaque information contexte s par ment Cela s est r v l tr s efficace pour l analyse de documents avec un m lange de genres par exemple les pages Web contenant la fois du mat riel structur et non structur ce qui est fr quent dans des documents Web Ciravegna amp Lavelli 2001 L architecture d Amilcare est li e avec ANNIE un syst me de TAL de l environnement GATE ANNIE effectue la tokenisation l quetage morphosyntaxiqu
117. ne Abstract Information Extraction EI comprises techniques and algorithms performing two important tasks identifying the desired relevant information from structured or non structured documents and storing it in appropriate form for future use This work is focused on adaptive IE systems that can be customized for new domains through training machine learning using annotated corpora as input Particularly automatic wrapper induction techniques are looked into for extraction that rest on the exploitation of structural regularities present in documents Wrappers are procedures to extract data from information resources Wrapper induction is defined as a technique that uses machine learning algorithms for automatically construct wrappers from a previously annotated corpus and that has shown good results when applied to structured semi structured and free natural language documents This work proposes a supervised IE system based on Boosted Wrapper Induction BWI a supervised wrapper induction algorithm in which the AdaBoost algorithm is used to generate a general extraction procedure that combines a set of specific wrappers by weighted voting Some others authors have investigated how boosting contributes to the success of the BWI algorithm and examined its performance in the challenging direction of using it as an IE method for unstructured natural language documents This fact became the rationale for including Parts of Speech POS taggin
118. nes valeurs sont manquantes 3 2 2 SoftMealy Similaire WIEN SoftMealy est un syst me d EI qui produit des r gles d extraction en utilisant un type sp cial d automates appel s Finite State Transducers transducteurs tats finis Hsu 1998 Un transducteur tats finis comporte des alphabets d entr e sortie des tats et des transitions Hsu et Dung ont pr sent l id e de transducteurs tats finis pour permettre plus de variation sur les structures d extracteurs con ues par SoftMealy Dans SoftMealy un transducteur tats finis est compos d un body transducer qui extrait la partie de la page qui contient les tuples similaire HLRT dans WIEN et de plusieurs transducteurs de tuples qui extraient it rativement les tuples partir de la portion de textes d finies par le body transducer Les transducteurs de tuples acceptent un tuple et renvoient ses attributs Ils produisent une sortie un mot de l alphabet de sortie en fonction de la lecture d un mot en entr e et de l tat dans lequel ils se trouvent L algorithme d extraction de SoftMealy est congu dans un esprit similaire celui des extracteurs HLRT de WIEN Il fait intervenir deux transducteurs un pour d terminer la zone du document qui contient les n uplets et un autre pour extraire les n uplets de ladite zone Chaque permutation distincte d attribut dans la page peut tre encod e comme un chemin partant d un tat de d but un tat final d
119. nformations multi slot reliant par le biais de sa structure hi rarchique les donn es extraites La racine contient la s quence de tokens S du document dans son int grit et chacun de ses fils une sous s quence de S Un document est vu par ce syst me comme une s quence de tokens Un token est une s quence de caract res alphanum rique non alphanum riques ou une balise HTML L algorithme d induction consiste d terminer les r gles d extraction des noeuds de l arbre EC fourni par l utilisateur Les valeurs des n uplets annot s par l utilisateur sont reli es aux feuilles ad quates de l arbre Cet apprentissage est fait partir de documents annot s Il consiste apprendre les r gles d extraction en utilisant un algorithme de couverture sp cifique Muslea et al 2001 L algorithme d extraction proc de en parcourant l arbre et en appliquant chaque n ud la r gle d extraction La s quence de tokens extraite est le point de d part de la r gle d extraction suivante Il existe pour chaque n ud de l ECT une r gle single slot sp cifique form e par une paire d automates finis non d terministes pour la localisation des d limiteurs gauche et droit des n uds du document d entr e Cette localisation se produit de mani re ind pendante de ses noeuds voisins ce qui facilite ainsi la manipulation d attributs d sordonn s et ou absents STALKER sp cifie deux types de r gles celles pour l extraction des n uds feuille e
120. nier compos de textes en langage naturel Jess Java Expert System Shell Friedmann Hill 97 est un outil pour le d veloppement de r gles de production syst mes experts fond sur un moteur d inf rence qui emploie l algorithme Rete Forgy 82 libre Ensuite un protocole exp rimental reposant sur une m thodologie d valuation rigoureuse est mis en place afin d examiner l influence des param tres sur l algorithme BWI et analyser l effet de la prise en compte de la syntaxe du langage naturelle sur trois collections de documents Finalement il est men une valuation comparative du syst me propos avec d autres syst mes d EI tudi s dans l tat de l art Enfin le chapitre 6 conclut en faisant un bilan de ce travail de recherche en pr sentant plusieurs perspectives possibles 2 EXTRACTION D INFORMATION Parmi les plusieurs d finitions de l extraction d information EI on rencontre d une part celle qui affirme que l EI consiste extraire de la connaissance de documents Crespo et al 1994 D autre part Pazienza 1997 d finit l EI en la comparant avec la recherche d information RI o la derni re consiste trouver un ensemble de documents pertinents tandis que la premi re consiste trouver dans ces documents un ensemble de faits pertinents Les documents dont on souhaite extraire de l information peuvent pr senter un certain degr dans la structuration des informations mais ils peuvent aussi n en
121. nningham et al 2002 b Cunningham H Maynard D Tablan V Ursu C Bontcheva K The GATE User Guide 2002 Disponible http gate ac uk dernier acc s en juin 2009 Douthat 1998 Douthat A The message understanding conference scoring software user s manual In Proceedings of the 7th Message Understanding Conference MUC 7 1998 Eikvil 1999 Eikvil L Information Extraction form the World Wide Web a Survey In Technical Report 945 Norweigian Computing Center 1999 Espinasse et al 2007 Espinasse B Fournier S Freitas F AGATHE une architecture g nerique base d agents et d ontologies pour la collecte d information sur domaines restreints du Web CORIA 2007 Quatri me conf rence francophone en Recherche d Information et Applications 2007 Finn amp Kushmerick 2004 Finn A Kushmerick N Multi Level boundary classification for information extraction In Proceeding of the European Conference on Machine Learning Pisa 2004 Florescu et al 1998 Florescu D Levy A Mendelzon A O Database techniques for the World Wide Web A survey SIGMOD Rec 1998 Forgy 82 Forgy C L Rete A Fast Algorithm for the Many Pattern Many Object Pattern Match Problem Artificial Intelligence 19 1982 17 37 USA 1982 Fred Freitas et al 2008 Freitas F Cabral L Lima R Espinasse B Palmeira E Fournier S Guilherme Bittencourt From MASTER Web to AGATHE the evolution of architecture for manipulating in
122. nnouncements sans traitement de POS et la Tab 2 pr sente leurs significations lt xml version 1 0 encoding IS0 8859 1 standalone no gt wrapper label speaker gt lt fore detector gt lt detector gt lt pattern type prefix gt feature name token value Who feature name single char token value true gt pattern pattern type suffix gt feature name alpha token value true gt pattern lt confidence value gt 2 7587264482323546 lt confidence value gt lt detector gt lt detector gt lt pattern type prefix gt feature name token value speaker gt feature name single char token value true gt pattern pattern type suffix gt pattern lt confidence value gt 2 2216808574759974 lt confidence value gt lt detector gt lt wrapper gt Fig 25 Un extrait d un wrapper appris en XML Tab 2 Un extrait du wrapper appris apr s l application d une transformation XSL P token Who single char token true S alpha token true 2 Pftoken speaker single char tokenz true S Ainsi la ligne 1 de la table ci dessus exprime une r gle ou le nom d un speaker peut tre trouv juste apr s les tokens Who suivi d un token constitu d un seul caract re pr fixe et juste avant un token form par des caract res alphab tiques suffixe Il en va de m me 46 pour la deuxi me ligne qui exprime une r gle qui n a qu un pr
123. ns ne se faire pas suffisante pour g n rer de bonnes r gles pour ce type d information En plus ce slot est le plus repr sentatif de tout le corpus CFP en ayant seulement 100 exemples annot s Une fa on d am liorer ce r sultat serait alors de faire le tokeniseur reconnaitre ce type information comme une entit ou en augmentant les nombres d exemples d apprentissage 75 Corpus CFP 1 0 0 8 0 6 BIB Amilcare 3 i S53 Yaoyong Q EN SIE 2 DI M TIES a 0 4 0 2 0 0 w nam w_acro w dat w hom w loc w pap w not w cam c nam c acro c hom Slots Fig 46 Scores de Rappel des syst mes par slot sur le corpus CFP La Tab 14 est illustr e par la Fig 47 qui montre que le syst me M TIES a t le plus pr cis de tous les syst mes participants cette valuation comparative mais il a eu le plus bas score de rappel En somme sa performance en terme de F measure a t comparable aux syst mes SIE et Yaoyong et un peu plus bas que le syst me Amilcare sur le corpus CFP Tab 14 Comparaison entre les 4 syst mes sur le corpus CFP Pr c Rappel F1 Amilcare 84 3 70 3 76 7 Yaoyong 70 2 71 7 70 9 SIE 75 5 65 2 70 0 M TIES 89 6 59 1 71 2 76 Comparaison de R sultats 0 8 4 o 064 o EN Amilcare E SIE EEE Yaoyong i 54 EI M TIES 0 2 4 0 0 Pr cision Rappel F1 micro Fig 47 Comparaisons des mesures de pr cision rappel et F1 measure micro entre les 4 syst mes Bilan sur l
124. ntation de documents et d exemples sese 25 SAAD Hypoth ses se ens a res ME Foe E CADA pena 25 3 1 4 3 Algorithme apprentissage aue eater epe Eee Be SURE Qe etes 26 3 1 4 4 Algorithme d extraction eee ec eeecer testen tesoros e Renee tne Pea Ee Redde 28 SAS Ciao deb NES en et itp ete eb Mur nt Ron Des 29 3 2 Autres syst mes d induction supervis e d extracteurs eee 20 EX WEN PE MEETS 30 F22 SONIA eS E LL M PE nn A 31 3297 STALKER pianga ato ieie Er oa ata pe 31 Sd AMIICAIO me UE 33 3 2 5 SIE Simple Information Extraction ss 35 3 2 6 TIES Trainable Information Extraction System seen 36 mo nA AU Ets VIM MC Se ud a E tudes lode 37 do E SO E E t E a 37 4 UN SYSTEME D EI ADAPTATIF PAR INDUCTION SUPERVISEE DEXTRACTEURS nn pe TUE SEDE ERU SECTOR PIRE EN SEI E GENS ASIE I 39 4 1 Architecture g n rale d un syst me d EI adaptatif cee ceteeeeeeeeaeees 39 4 1 1 Pretraitement des textes d entr e s uo ne nr te on ne ne oio ne 39 4 1 2 Apprentissage et application du mod le d extraction esses 39 AS Postetratement de Ig SOFIe esi o e rho Eu pn pass Piae aat aceite FU baud 40 4 0 TIES un syst me d induction supervis e d extracteurs sees 41 4 2 1 Description d taill e du syst me TIES version originale 41 42 2 Repr sentation de documents sin nan nee Eae
125. obs en utilisant un ensemble d attributs compos d information de capitalisation et POS Slot LPP GATE SVM Rapier M TIES id 100 0 97 7 97 5 98 1 title 43 9 49 6 40 5 67 4 company 71 9 77 2 69 5 78 9 salary 62 8 86 5 67 4 89 2 recruiter 80 6 78 4 68 4 86 1 state 86 7 92 8 90 2 96 9 city 93 0 95 5 90 4 96 5 country 81 0 96 2 93 2 98 8 language 91 0 86 9 80 6 88 5 plataform 80 5 80 1 72 5 86 9 application 78 4 70 2 69 3 73 1 area 66 9 46 8 42 4 51 6 req y exp 68 8 80 8 67 1 86 4 des y exp 60 4 81 9 87 5 89 9 req degree 84 7 87 5 81 5 78 6 des degree 65 1 59 2 72 2 47 6 post date 99 5 99 2 99 5 100 0 All slots 84 1 80 8 75 1 83 8 71 a Corpus Seminars En analysant les r sultats de la Tab 11 o all slot est la F measure micro on note que l valuation du M TIES a t notamment sup rieur sur trois slots tandis que pour les syst mes SIE GATE SVM qui utilisent l algorithme SVM comme leur composant d apprentissage et LP ont obtenu une performance globale similaire Giuliano et al 2006 Li et al 2004a Ciravegna 2003b On veut remarquer que le systeme GATE SVM a utilis un ensemble d attributs plus riche que les autres syst mes Li et al 2004b Avec l ensemble d attributs complet du M TIES ce atteint une performance de 96 7 De fa on similaire LP obtient 89 796 sur ce corpus en employant NER et gazeteers On n a pas de scores d taill par slots du SIE Giuliano et al 2006 ce qui explique les v
126. ogica ITC irst est un syst me d EI adaptatif Il a t d velopp en langage Java et il met en uvre l algorithme Boosted Wrapper Induction BWI propos par Dayne Freitag et Nicholas Kushmerik Freitag amp Kushemerick 2000 section 3 2 2 L algorithme d apprentissage de BWI utilise lui m me l algorithme de boosting AdaBoost pour g n rer des extracteurs qui combine un ensemble sp cifique d inducteurs d extracteurs partir de documents annot s L algorithme BWI a d montr tre tr s performant dans de nombreuses t ches d EI partir de documents structur s et semi structur s De plus d apr s Kauchak et al 2002 l utilisation de l algorithme BWI donne aussi de bons r sultats pour le traitement de documents non structur par exemple des textes en langage naturel TIES tiqu te les documents avec un ensemble de balises XML pr d finies en exploitant des r gles apprises automatiquement gr ce un corpus pr alablement annot Ces balises XML permettent d identifier les instances d entit s qui proviennent d un ensemble d l ments d finis par l utilisateur Ce syst me a t retenu dans cette recherche et sera pr sent en d tail dans la section 4 2 36 3 2 7 Tableau de synth se Un r sum des caract ristiques majeures de tous les syst mes d EI par induction supervis e d extracteurs examin s dans cette section est pr sent dans le tableau suivant Tab 1 R sum comparatif de caract risti
127. on veut extraire et 3 la sortie d une t che d EI est structur e et d finie selon un sch ma template En d autres termes l EI a pour objectif de construire des syst mes qui trouvent et combinent des informations pertinentes tandis qu ils ignorent des informations insignifiantes et inutiles Cowie amp Lehnet 1996 Ils mod lisent une fonction qui re oit un document d entr e et retourne un formulaire de sortie pr alablement d finie avec leurs champs remplis De cette facon des informations sp cifiques peuvent alors tre extraites de diff rents documents avec une repr sentation h t rog ne et peuvent tre r sum es et pr sent es en un format fix l avance Un exemple d une telle t che est illustr par la Fig 2 Dans cet exemple le document d entr e est un article scientifique et le formulaire template de sortie se compose des champs auteurs et emails Il est important de noter que des informations extraites sont d termin es par un ensemble de patrons ou de r gles d extraction sp cifiques un certain domaine La d finition de telles r gles peut tre effectu e manuellement par un sp cialiste du domaine concern ou avec diff rents degr s d automatisation supervis semi supervis ou non supervis e Ainsi l EI peut concerner une collection de documents dont on veut extraire des faits pr cis Le WWW est un bon exemple d une telle collection de documents Ici des informations sur un sujet se trouvent f
128. oncerne des offres d emploi dans le domaine de l Informatique Ce corpus est compos de 300 documents qui contiennent des informations sur des employeurs entreprises salaires et exigences d offres d emploi Plusieurs slots tel que ceux concernant les langages et les plate formes logiciels requis pour l emploi peuvent avoir plusieurs valeurs Dans les exp rimentations il a t consid r le corpus propos originalement par Califf amp Mooney 1999 La Fig 33 pr sente un document originaire de ce corpus et son template d extraction rempli 55 Posting from Newsgroup Telecommunications SOLARIS Systems Administrator 38 44K Immediate need Leading telecommunications firm in need of an energetic individual to fill the following position in the Atlanta office SOLARIS SYSTEMS ADMINISTRATOR Salary 38 44K with full benefits Location Atlanta Georgia no relocation assistance provided Filled Template computer science job title SOLARIS Systems Administrator salary 38 44K state Georgia city Atlanta platform SOLARIS area telecommunications Fig 33 Exemple d une offre d emploi avec son template d extraction rempli Califf 1999 5 1 3 2 D finition du Template d extraction Chaque document de ce corpus comporte 17 slots suivants extraire id title salary company recruiter state city country language platform application area req years experience desired years experience req degree desire
129. onibilit des corpora standards annot s ne garantissent pas que les exp riences r alis es avec de diff rentes approches et algorithmes propos s dans la litt rature soient compar es d une fa on juste et fiable Lavelli et al 2004 Voici les points les plus importantes examin es par Lavelli et al D finition exacte des partitions de corpus Il est bien connu que diff rentes partitions de corpus peut influencer les r sultats Ainsi il est crucial que l on d finisse le point de s paration exacte entre l ensemble d apprentissage et l ensemble de test vu les proportions num riques entre les deux ensembles par exemple un 68 random split de 50 50 contre un de 80 20 et la proc dure adopt e pour partitionner les documents par exemple validation crois e vs random subsampling T ches de pr traitement Certaines sous t ches de pr paration d un corpus par exemple tokenization sont souvent consid r es comme videntes et non probl matiques mais il n est pas le cas ici et cela peut influencer la performance des algorithmes d IE Cette question importante distingue un algorithme et les attributs qu il emploie dans leur contribution sa performance En EI par exemple certains algorithmes ont utilis des attributs orthographiques simples tandis que d autres emploient des attributs plus complexes tels que le tagage POS ou tiquettes s mantiques extraites de gazeteers Califf 1998 Ciravegna 2001 Peshkin amp Pfeffer
130. ores individuels et la courbe d apprentissage de l algorithme La t che d EI adaptative est requise pour concevoir un mod le initial partir d un petit nombre d exemple Dans ce cas il est attendu que la performance du syst me s am liore progressivement au fur et mesure que de plus en plus d instances soient disponibles pour l apprentissage Par exemple cela peut avoir lieu quand l utilisateur annote de nouveaux documents En fait on veut ici simuler ce sc nario avec l objectif d valuer l algorithme d apprentissage sur un nombre croissant d exemples Le param tre L 3 et le nombre d it rations en 100 ont t utilis s Ensuite les documents du corpus ont t r partis al atoirement en deux partitions gales une partition sera d sign e l ensemble de test avec un nombre invariable de documents De l autre partition l ensemble d apprentissage il est choisi un nombre croissant de documents en faisant en sorte que les documents choisis dans l tape pr c dente soient compris dans l ensemble d exemples d une tape post rieure De cette fa on il est simul le sc nario o l utilisateur qui annote des plus en plus de documents et les rajoutent au corpus A chaque tape on mesure la F mesure du syst me ce qui am ne aux r sultats suivants Tab 8 R sultats en F measure par slots du corpus Seminars en augmentant le nombre de documents Slots 10 20 40 60 80 100 stime 0 914 0 949 0 954 0 980 0 982 0 985 etime 0 940
131. orpus Seminars sans a et avec b POS sss 63 R sultats sur le Corpus Jobs sans a et avec b POS 63 Compairaisons par slot de F measure avec et sans POS sur le corpus JOBS 64 R sultats sur le Corpus CFP sans a et avec b POS 65 Influence du POS sur le Corpus CFP sans a et avec b POS 65 Perfomance g n ral d extraction de M TIES sur les corpora ees 66 L effet de diferents ensembles d attributs utilis s sur les corpora 67 Courbe d apprentissage sur le corpus Seminars eese 68 Score F Measure des syst mes par slot sur le corpus CFP 74 Scores de Precision des syst mes par slot sur le corpus CFP sssss 75 Scores de Rappel des syst mes par slot sur le corpus CFP 76 Comparaisons des mesures de pr cision rappel et F measure ssesss T11 xvii xvili Tab Tab Tab Tab Tab Tab Tab Tab Tab Tab Tab Tab Tab Tab Liste de Tableaux 1 R sum comparatif de caract ristiques des syst mes 37 2 Un extrait du wrapper appris apr s l application d une transformation XSL 46 3 Nombre d exemples positifs pour les slots location speaker stime etime 55 4 Nombre d exemples pour chaque entit slot du corpus JOBS 56 5 Distribution de fr quences des slot annot s Ireson amp Ciravegna 2005
132. oubek amp Rajman 2000 Paroubek P Rajman M Etiquetage morpho syntaxique Pierrel J M ed Ing nerie des langues Informatique et systemes d information ch 5 pages 131 150 Herm s Science Paris 2000 Pazienza 1997 Pazienza M T Information Extraction Towards scalable adaptable systems In Lecture Notes in Artificial Intelligence 1997 Peshkin 2003 Peshkin L and Pfeffer A Bayesian information extraction network In Proceedings of 18th International Joint Conference on Artificial Intelligence IJCAI 2003 2003 Pianta et al 2008 Pianta E Girardi C Zanoli R In Proceedings of LREC 6th edition of the Language Resources and Evaluation Conference 28 30 May Marrakech Morocco 2008 QTag 2008 QTag a portable POS tagger 2008 Disponible http morphix nlp berlios de manual nodel7 html dernier acc s en juin 2009 Russel amp Norwig 2003 Russell S Norwig P Artificial Intelligence A Modern Approach Pearson Education 2003 Sahuguet amp Azavant 2001 Sahuguet A Azavant F Building intelligent web applications using lightweight wrappers Data Knowledge Eng 36 3 283 316 2001 Schmid 1994 Schmid H Probabilistic Part of Speech Tagging Using Decision Trees In International Conference on New Methods in Language Processing pp 44 49 Manchester UK 1994 SEKT 2006 SEKT project Semantically Enabled Knowledge Technologies 2006 Disponible http www sekt project co
133. oy par l outil De facon analogue l approche manuelle mais dans une moindre mesure lapproche par sp cification compte sur l expertise de l utilisateur pour les t ches d extraction sans mentionner que c est lui qui doit galement faire l analyse des documents 2 4 3 Approche par induction supervis e d extracteurs Dans cette approche l induction d extracteurs Kushmerick 2000 est effectu e automatiquement par un algorithme d apprentissage machine partir de documents annot s aussi appel s exemples par l utilisateur En plus il est souhaitable de r aliser l induction d extracteurs en faisant en sorte que l utilisateur annote le moins nombre possible d exemples Les algorithmes d induction d extracteurs reposent sur l exploitation des r gularit s morphosyntaxiques et ou structurelles des documents HTML XHTML et XML qui permettent de rep rer les donn es extraire Les pages obtenus par des moteurs de recherche sur de nombreux sites Web comme des sites de e commerce ont une grande r gularit car elles sont construites la plupart du temps partir d une base de donn es Par cons quent d une grande r gularit pr sente dans ces pages les syst mes d induction supervis e d extracteurs peuvent exploiter le patron de mise en page pour l EI Un avantage de cette approche est qu on peut utiliser n importe quel algorithme d apprentissage supervis existant en tant que brique d apprentissage Ici l objectif est de
134. pilation de code source Le syst me TIES a t crit en langage Java Le code source de l un de ces packages celui responsable pour le pr traitement tokenisation et feature extraction du corpus d entr e n tait pas disponible directement Ce package se pr sentait comme un fichier JAR Un fichier JAR Java ARchive est un ensemble de code source java compil s en bytecode et group s dans un seul fichier pour distribution Il a fallu alors gr ce des outils de d compilations de bytecode java existants sur le Web d compiler ce package afin d acc der au code source et faire les modifications pertinentes aux besoins de la nouvelle version du syst me TIES D sormais le code source r vis de ce module est disponible pour qu on puisse le changer en futures versions du syst me 4 3 5 Sortie de r sultats en format CSV Les r sultats de l apprentissage exprim s par les mesures de Pr cision Rappel et F Measure sont affich s par TIES la fin d une session d apprentissage comme illustr par la Fig 29 Afin de contr ler la mise en page de la sortie du syst me et faciliter l analyse ult rieure des r sultats on a d velopp de nouvelles classes Java qui produisent des fichiers en format CVS permettant l usage de tableurs spreadsheet pour les exploiter Bytecode est cr lors de la compilation de code source java par le biais de compilateur javac de l environnement JDK Le compilateur javac produit alors un fichier cl
135. pprentissage et extraction La phase d apprentissage utilise un ensemble d exemples tiquet s pour produire un mod le de classification capable de remplir les slots extraire tandis que la phase d extraction applique ce mod le appris sur des documents non tiquet s pour en extraire les donn es Ces deux phases partagent un m me pr traitement de repr sentation de documents afin de les segmenter en unit s sur lesquelles portera la classification Cette recherche suit la m me piste prometteuse de la CS appliqu e avec succ s lEI dans plusieurs travaux Freitag amp Kushemerick 2000 Marty amp Torre 2003 Gilleron et al 2006 Finn amp Kushmerick 2004 Giuliano et al 2006 Li et al 2004 b Dans ce contexte ce chapitre pr sent tout d abord la notion de la classification supervis e et puis explique comment le probl me de l EI peut tre formul comme un probl me de classification supervis e Ensuite le syst me BWI est examin comme un syst me de r f rence qui emploie le mod le de la CS pour induire les hypoth ses d induction Diff rentes approches et algorithmes utilis es dans le domaine d EI sont abord s au travers de la pr sentation de quelques syst mes d EI existants Ce chapitre se termine en pr sentant un tableau de synth se comparant les caract ristiques majeures des syst mes d EI tudi s et en dressant quelques conclusions 3 1 Mod le d Apprentissage de la Classification Supervis e 3 1 1
136. pr s cette valeur la performance se stabilise Les slots conference homepage et conference acronym atteignent la Fl measure optimale avec L 5 tandis que la valeur optimale pour le slot workshop camera ready copy date a t L 4 Finalement il a t constat que pour la presque moiti de slots de ce corpus notamment les slots workshop date workshop location workshop home conference name workshop date L 3 donne la F1 measure optimale ou bien tr s proche d elle Le chois de corpus CPF pour la r alisation de ces exp riences a eu l objectif d valuer l influence du param tre L sur un corpus moins structur Pour les autres corpora Seminars et Jobs tant donn qu ils sont plus structur s les gains sont marginaux pour une fen tre plus large que 3 comme a t d montr par Li 2004 et Freitag amp Kushmerick 2000 Corpus CFP w date w home w location w not conf name conf acro w acro w came conf home 2 3 4 5 6 7 8 Look ahead L Fig 35 volution de la F measure en fonction du look ahead L sur le corpus CFP 5 3 1 3 Information POS Les exp riences men es dans cette section examinent l influence du tagage POS sur chaque slot de tous les corpora On a fix le nombre d it rations 100 et look ahead L 3 en suivant les suggestions de r sultats ant rieurs de ce deux param tres qu on vient d analyser Il a t utilis la validation crois e avec k 10 dans les exp riences men
137. pr sent s ci dessus 3 1 4 Boosted Wrapper Induction 24 Boosted Wrapper Induction BWT est un syst me d EI d velopp par Daniel Freitag Freitag amp Kushmerick 2000 l Universit de Pittsburgh qui induit des extracteurs single slot pour les documents structur s et non structur s Il a t un des premiers syst mes se servir de la classification supervis e comme algorithme de base pour l apprentissage d extracteurs Plus tard divers travaux notamment Kauchak et al 2002 Marty amp Torre 2004 expliquent les r sultats honorables obtenus par le syst me BWI plus pr cis ment par les algorithmes qu il met en ceuvre Dans Kauchak et al 2002 les auteurs ont analys comment les composants algorithmiques du BWI contribuent son succ s Ils ont mis en vidence que la technique de boosting Freund amp Schapire 1990 est l l ment principal de la r ussite de BWI Il a montr que cela r side dans la capacit de l algorithme de faire la repond ration des exemples afin d apprendre des r gles sp cifiques conduisant une pr cision lev e combin e avec la capacit de continuer l apprentissage des r gles m me apr s que tous les exemples positifs aient t couverts conduisant un rappel lev D autre part Marty amp Torre 2004 ont tudi l influence du langage de repr sentation choisi et de connaissances auxiliaires sur la performance du BWI De plus ils ont montr qu un codage de
138. profiter de l existant en mati re d algorithme d apprentissage et de faciliter son volution future principalement si l on souhaite avoir un syst me bien modulaire L induction d extracteurs supervis e peut tre r alis e depuis les exemples positifs donn es que l utilisateur veut extraire et les exemples n gatifs ou contre exemples donn es que l utilisateur ne veut pas extraire 19 2 4 4 Approche par induction non supervis e La conception d extracteurs par induction non supervis e contrairement l approche pr c dente se passe compl tement de l intervention de l utilisateur G n ralement ces extracteurs sont reposant sur des techniques d inf rence grammaticale Crescenzi et al 2001 ou sur des m thodes d alignement de chaines ou d arbres des documents Arasu 2003 De cette facon l induction non supervis e produit un extracteur partir des documents extraire en analysant leurs structures et r gularit s Les extracteurs induits par ces syst mes produisent en sortie des donn es structur es sous la forme d une table avec d ventuelles imbrications Cependant les extracteurs non supervis s sont moins pr cis que ceux induits par l approche supervis e Zhai amp Liu 2005 Mais les extracteurs non supervis s ont l avantage comme l utilisateur n est pas n cessaire leur fonctionnement de pouvoir tre int gr s des chaines de traitements automatiques de documents RoadRunner Crescenzi et al 2001
139. ques des syst mes Syste Type de Repr sentation Type Algorithme Faire l usage Ysreme documents de documents d extraction d apprentissage de TAL Semi WIEN structur Token unaire ee Non HTML nemi Transducteurs SoftMealy structur Token unaire tat finis Non HTML Semi Embedded Algorithme de STALKER structur Catalag n aire couverture Non HTML arborescence ad hoc Amilcare Te Token unaire moon Om Libre LazyNLP s quentiel Classification SIE Texte libre Token unaire Supervis e Non SVM Texte Classification TIES libre Token unaire supervis e Non Adaboost Ce tableau montre que la plupart de ces syst mes tudi s adoptent une repr sentation de document base de tokens sauf STALKER Except STALKER ces syst mes font de l extraction unaire single slot Ils mettent en ceuvre diff rents algorithmes d apprentissage pour traiter des textes semi structur s voire libre pour certains de ces syst mes SI TIES Amilcare 3 3 Conclusion Dans ce chapitre tout d abord il a t tudi la classification supervis e sur laquelle repose la plupart des techniques d EI par induction supervis e d extracteurs Ainsi un extracteur a t d fini comme un processus de classification o le probl me d induction d extracteurs se ram ne alors un probl me d apprentissage de classification supervis e TIES accepte des textes libres condition qu ils soient constitu s comme documents XHTML
140. r Ce scenario plus avantageux du point de vue de l utilisateur n existe plus car le module extracteur Amilcare une mise en uvre de l algorithme LP n est plus disponible cause des droits r serv s de son cr ateur Ainsi nous pourrions essayer de rajouter au MnM un algorithme d apprentissage supervis SVM ou C4 5 par exemple pour remplacer ce module manquant 6 3 Perspectives relatives l architecture Master Web AGA THE En outre les perspectives pr sent es dans la section pr c dente un autre travail envisag dans cette recherche repose sur l hypoth se d utiliser le potentiel d induction d extracteurs avec tous les avantages d j list s dans le contexte d une extraction d information int gr e plus pr cise et fine afin d augmenter la performance du sous syst me d extraction de l architecture MasterWeb AGATHE section 1 1 Dans les syst mes MasterWeb AGATHE les ontologies peuvent r unir et combiner sous un m me environnement les trois types de connaissances n cessaires l extraction d information 1 la connaissance destin e l identification des structures syntaxiques et s mantiques du texte avec l aide du tagage POS 2 la connaissance pour identifier les diff rents formats de textes trait s sans utiliser de techniques TAL comme les wrappers par exemple et enfin 3 la connaissance pour r aliser les inf rences avec un engagement ontologique c est dire en employant les faits connus sur le
141. r l interrogation directe des donn es Malgr tout un texte en langage naturel poss de une structure dite grammaticale que l on peut exhiber l aide de techniques TAL Les conf rences MUC Hirschman 1998 se sont focalis es sur la compr hension de textes en langue naturelle Cette t che d extraction d information est faisable l aide de techniques de TAL Les figures suivantes Fig 3 et 4 pr sentent respectivement l un des textes consid r s par MUC 4 et les informations extraire de ce m me texte Les informations extraites sont structur es sous la forme d un enregistrement avec plusieurs champs Les t ches consid r es dans les conf rences MUC sont l extraction depuis de r cits d attentats en Am rique du Sud d informations comme la date le lieu et le type d attentat ou encore le nom et le type de l organisation revendiquant l attentat LIMA 23 AUG 88 EFE TEXT TODAY PERUVIAN MILITARY OFFICIALS ESTABLISHED A CURFEW IN TINGO MARIA BECAUSE OF THE STRIKE BY PEASANTSAND COCA GROWERS TO PROTEST THE DESTRUCTION OF THEIR COCA FIELDS SINCE 20 AUGUST THE STRIKERS HAVE BEEN BLOCKING THE ROAD LINKING HUANUCO WITH TINGO MARIA HUANUCO DEPARTMENT IN THE NORTHERN JUNGLE WHERE THERE IS DRUG TRAFFIC ACTIVITY THE STRIKERS ALSO BLOCKED THE MARGINAL DE LA SELVA HIGHWAY ISOLATING TOCACHE UCHIZA JUANJUI AND AUCAYACU WHICH ARE WELL KNOWN CENTERS FOR DRUG TRAFFICKING THE STRIKE IS SUPPORTED BY THE SHINING PATH ACCORDING TO
142. r quemment parpill es dans de diff rents sites sous de divers formats de pr sentation et donc il serait tr s souhaitable si ces informations puissent tre extraites et int gr es de mani re structur e Dans notre recherche nous consid rons que l EI consiste produire automatiquement des informations structur es partir d un ensemble de documents La t che d EI sera r alis e par 7 des programmes nomm s extracteurs wrappers que l on peut d finir comme une fonction de l espace des documents d entr e vers l ensemble des structures de sortie Template Email Author 1 Email Author 2 Information Document Extraction System An Architecture for Knowledge Intensive CBR Systems Bel m D az and Pedro Calero Template filling Dep Sistemas Inform ticos y Programaci n Universidad Complutense de Madri Spain Pedro Calero pedro sip ucm es belen pedro sip ucm es Output belen sip ucm es Fig 2 Exemple d extraction d information auteurs et emails adapt de Cabral 2004 Dans ce chapitre nous abordons tout d abord l EI partir de documents non structur s et semi structur s gr ce au Traitement Automatique de la Langue TAL et la conception d extracteurs Puis nous examinons les diff rents types de t ches d extraction selon la repr sentation de documents et la nature de sortie d extracteurs retenues Ensuite nous pr sentons une m thodologie pour valuer
143. r le test On a fix le param tre L 3 et le nombre d it rations en 100 Comme le montrent les r sultats de la Tab 7 les attributs concernant les informations de tokenkind cat gorie de tokens ont t utiles pour am liorer le score du syst me d environ 3 pour les corpus Seminars et Jobs par rapport l information simple du mot La Fig 42 montre aussi que quand on consid re seulement le corpus CFP l information POS a t encore plus utile avec un cart de performance de plus de 5 par rapport la simple information du token Ces r sultats sont explicables en raison de la nature moins structur e du corpus CFP et cons quemment l avantage d avoir des patrons linguistiques fournis par le l tiquetage POS Par contre le corpus JOBS a obtenu le gain plus faible parmi les corpora Tab 7 Influence de diff rentes features sur le corpora r sultats exprim s en F Measure micro Features Word d iid Ein de re POS Seminars 0 933 0 938 0 963 0 967 Jobs 0 822 0 832 0 853 0 853 CPF 0 656 0 670 0 696 0 712 66 Features Influence on Corpora 1 00 0 95 NET Lu ee 0 90 0 85 os as oO O On EO Qu iL 0 80 0 75 Dm v 0 70 copi wem MeL SIUS e Seminars 0654 Y O Jobs w CFP 0 60 T T T T W WC WCT WCT4POS Features Fig 42 L effet de diff rents ensembles d attributs utilis s sur les corpora 5 3 3 Courbe d apprentissage La Tab 8 et la Fig 43 montrent respectivement les sc
144. r r duire le nombre d instance n gatives en supprimant jusqu 5096 des instances fin d all ger le d s quilibre entre les classes et acc l rer le traitement Une fen tre de 10 tokens un contexte gauche droite de 20 tokens au total a t utilis e pour ces deux syst mes En revanche Amilcare et M TIES on utilis une fen tre de 5 et 3 respectivement En consid rant les attributs utilis s Yaoyong et SIE ont utilis tous les attributs disponibles sauf l information POS Par contre M TIES se sert d informations sur word token capitalisation token types abr viation alpha num rique symboles ponctuation entit s date et l heure seulement et taggage POS Almicare utilise tous les attributs du GATE La Fig 44 r sume les r sultats de la Tab 13 en montrant la performance en F measure par slot des syst mes Amilcare LP Yaoyong et SIE Tab 13 Performance des syst mes sur le corpus CFP par slot en termes de PRE Pr cision RAP Rappel et FME F measure i WORKSHOP CONFERENCE Systeme Sen name acto ato nome loco ape not camo name are home Amilcare LP SIE M TIES Corpus CFP 1 0 0 8 0 6 Bl Amilcare i 7 Yaoyong EM SIE LL C M TIES 0 4 0 2 0 0 w nam w acro w dat w hom w loc w pap w not w cam c nam c acro c hom Slots Fig 44 Score F Measure des syst mes par slot sur le corpus CFP Tous les syst mes ont pr sent une grande
145. racteurs est vue comme un probl me de Classification Supervis e CS Il pr sente la fois les techniques de CS utilis es dans ce projet et quelques syst mes d induction d extracteurs qui utilisent des techniques semblables en se limitant au cas de l extraction unaire sur les documents non structur s avec prise en compte ou non de la syntaxe de la langue naturelle De l tude de ces syst mes existants pour cette t che sp cifique il est d gag une architecture logicielle et une d marche g n riques adapt es au probl me d extraction d information trait comme un probl me de classification Le chapitre 4 d crit la principale contribution de cette recherche qui est la proposition d un syst me d EI reposant sur l induction d extracteurs supervis pour l EI partir de pages Web L architecture logicielle de ce syst me est pr sent e ainsi que les diff rents modules sp cialis s qui la compose dont le module central TIES TIES Trainable Information Extraction System d velopp par IRST de Trento met en ceuvre l algorithme d apprentissage BWI Freitag amp Kushemerick 2000 et qui a t modifi pour la prise en compte du traitement du langage naturel annotation morphosyntaxique Le chapitre 5 pr sente les corpora utilis s pour valuer notre architecture logicielle d EI Il s agit de trois corpora de niveaux de structuration diff rents le premier corpus est structur le deuxi me est semi structur et le der
146. raction d un champ d information est r alis e en rep rant ses d limiteurs gauche et droit Un d limiteur est une s quence de caract res qui se trouve soit avant la donn e extraire dans ce cas on parle de d limiteur gauche et on le note soit apr s elle il s agit alors d un d limiteur droit not r Ainsi une donn e extraire composante est repr sent e par ses indicateurs de d but b et de fin e dans la s quence de caract res du document On trouve dans WIEN 6 classes d extracteurs base de d limiteurs o la plus simple d entre elles est la classe LR Les extracteurs de la classe LR exigent alors que tous les d limiteurs indiquent correctement les limites gauche et droite des segments extraire Les autres 5 classes d extracteurs sont HLRT OCLR HOCLRT NLR et NHLRT Nous renvoyons le lecteur Kushmerick 1997 afin de connaitre en d tail ces autres classes d extracteurs Un exemple d un extracteur d fini dans le WIEN est illustr par la Fig 17 On veut extraire Country et Area Code de deux pages HTML D1 et D2 D1 lt B gt Congo lt B gt lt I gt 242 lt I gt lt BR gt D2 lt B gt Egypt lt B gt lt I gt 20 lt I gt lt BR gt Rule B amp B amp I Output Country Code Country 1 AreaCode 22 Fig 17 Exemple d induction d extracteurs et extraction dans WIEN La r gle de la Fig 17 a la signification suivante ignorer tous les caract res
147. risent par exemple simplement des caract res individuellement consid r s ou une s quence de caract res d finie par un crit re syntaxique par exemple une expression r guli re qui puisse exprimer des dates des emails des chiffres etc Pour l aspect s mantique des tokens caract risent des unit s s mantiques plus complexes par exemple les mots d finis l aide de dictionnaires ou d outils de traitement du langage naturel lemmatiseur identificateur d entit s nomm es Dans un document un token repr sente soit une balise ouvrante fermante soit toute autre s quence de caract res comprise entre deux caract res blancs espace tabulation retour chariot 2 3 1 2 Repr sentation par un arbre L imbrication de balises comme celles pr sent es dans les Fig 8 et 9 d finissent naturellement une structure arborescente intrins que aux documents XHTML XML En fait chaque paire de balises ouvrante fermante peut d finir n sous arbres dont la racine aura comme label le non de la balise en question D autre part les portions de textes qui ne sont pas de balises sont les feuilles de l arbre Les donn es se sont trouv es dans les feuilles textes tandis que l organisation de n uds internes d termine la structure des donn es html body b Book Name b Data Mining b Reviews lt b gt ol li b Reviewer Name lt b gt Jeff b Rating lt b gt 2 b Text lt b gt lt li gt lt li
148. riture de r gles symboliques pour des t ches d extraction reste tr s difficile et fastidieuse m me si on utilise ces outils pour les crire Une autre limitation est que les architectures des syst mes MasterWEB AGATHE ne sont pas munies de techniques de traitement du langage naturel Par cons quent en outre les objectifs et contributions majeurs d j mentionn s il est envisag d int grer dans le syst me MasterWeb AGATHE de techniques symboliques d EI reposant sur l apprentissage artificiel machine learning Plus pr cis ment il est attendu une am lioration des performances du sous syst me d extraction de ces architectures en les dotant des techniques d induction automatique d extracteurs d information et de Traitement de Langage Naturel TAL 1 2 Structure du m moire Apr s ce chapitre introductif le chapitre 2 donne un aper u de la t che d extraction d information partir de diff rents types de documents Web en expliquant notamment comment repr senter ces documents pour en extraire par programme de l information en tenant compte ou non de traitement de la langue naturelle Ensuite diff rents approches pour la conception d extracteurs et une m thodologie traditionnelle d valuation de ces types de syst mes par trois mesures classiques d valuation de performance sont pr sent es Le chapitre 3 discute sur les fondements de l approche d extraction d information retenue par cette recherche o l induction d ext
149. rpora choisis se oie iii ee UE EAE XXE UN ER RINT SR EH URS A ins Ee ANM gen PUR pores 53 Sl uxnnotalonude documents oce ate nine ote pied alas 53 SL Corpus SEMINARS esos Gn top Dora dada alo nie e ans aam 54 5 1 2 1 Deseriptiom du corpus ocn e e ect doe a uto ada dpa tn 54 5 1 2 2 D finition du Template d extraction eene 55 5 1 2 3 Exemples de sorties extractions sssssseesssssseseseeesseeesstessressersseessseeessees 55 541 3 Corpus JOBS siemens 55 13d Desenphon dU CORPUS eeren a noir teens st 55 5 1 3 2 D finition du Template d extraction 56 5 1 4 Corpus CFP CALL FOR PAPERS Pascal Challenge 2005 57 5 L4 1 Description du Corpus eere t tete eret nena tare Pao eeu UU obesa PN UNE Gs 57 5 1 4 2 D finition du template d extraction 57 5 1 5 Comparaison et sp cificit s des Corpora sse 58 2 2 vProtocole Experimental esse peo tales us sane te eue 58 5 2 1 Preparations des CORDOLO ES nan RAR Mec RS A n MUN 58 5 2 2 M thodes d evaludtiOH Len mon st nee Dol oes nn UE SS a ca 59 Macroaverage et Microaverage a sainiinimniaialisnalnuninntneainsss 59 Deo JMERDERCACES O mnt rene E ni ane ans Re ac intra en 60 5 3 1 Influence des Param tres de l algorithme BWI et information POS 60 5 3 1 1 Nombre d it rations de boosting Corpus JOBS 60 5 3
150. rs les 6 tokens entourant le d but d un champ extraire Ce raisonnement est analogue pour un d tecteur de fin ce point dans l algorithme AdaBoost tous les motifs possibles gauche et droite sont num r s et celui qui am liore le plus les performances de la classification de l hypoth se est conserv Ce processus it re tant qu il soit possible d am liorer l hypoth se courante Ensuite les classificateurs appris sont combin s par vote pond r Les poids d un classificateur est d termin par l exactitude de son ensemble d apprentissage pond r Finalement BWI renvoie deux ensembles de classificateurs d tecteurs appris apr s ces it rations appel s fore detector F et aft detector A ainsi qu un histogramme H de la longueur en nombre de tokens du champ cible procedure Learn Detector example set Y prefix pattern p O suffix pattern s loop prefix pattern p BestPreExt p s Y suffix pattern d E BestSufExt p s Y if score p s gt score p s if score p s gt score p s p the last p 1 tokens of p else return detector p s else if score p s gt score p s s the first s 1 tokens of s else return detector p s Fig 15 L apprenant faible LearnDetector de BWI Freitag amp Kushmerick 2000 24 3 1 4 4 Algorithme d extraction La phase d extraction de BWI est constitu e de trois tapes 1 la classification de s parateurs d but c4 2
151. s Le syst me AGATHE Le sous syst me d extraction Le sous A Le sous teweb lt gt syst mede systeme gt y recherche d utilisation EI Fig 1 L architecture g n rique d AGATHE Cette architecture logicielle tire profit du g nie logiciel orient agents afin d assurer flexibilit et r utilisabilit Le point de d part de cette architecture est un prototype d j r alis le syst me MASTER Web Multi Agent System for Extraction and Retrieval over the Web Freitas et al 2000 2001 2003 Ce dernier propose un agent logiciel unique qui utilise des ontologies pour r aliser des t ches de classification et d EI sur le Web ceci sur un seul domaine de recherche Un des probl mes auxquels les architectures de MasterWeb AGATHE d faire face dans le d veloppement de syst mes de collecte d informations sur des domaines restreints est celui du probl me classique de la sp cification de l criture et de la mise jours des base de r gles en particulier dans l tape d extraction d information Par cons quent afin de faciliter l laboration de telles r gles en Jess un diteur intelligent qui aide l utilisateur r diger des r gles en langage Jess a t d velopp Cet diteur respect la syntaxe sp cifique de ces r gles et permet de se r f rer facilement un l ment de l ontologie pr sent dans une r gle par une op ration de glisser d poser Cependant l c
152. s entit s extraites Suite cette recherche il est envisag de combiner la t che symbolique du syst me MasterWeb AGATHE qui r alise actuellement une classification des pages Web base d ontologies avec une t che d extraction d information adaptative permettant d extraire de l information sur ces pages Web class es ceci par l usage de techniques d apprentissage artificiel machine learning utilis es dans M TIES avec l algorithme BWI Cette combinaison de techniques symboliques et de techniques d apprentissage artificiel devrait permettre d une part une am lioration significative de la performance de ces architectures en les dotant de techniques d induction automatique d extracteurs d information et de techniques TAL et d autre part de faciliter la mise en ceuvre de ces architectures sur de nouveaux domaines du Web en vitant le d veloppement fastidieux de bases de r gles symboliques d extraction d information 81 REFERENCES Adda et al 1999 Adda G M Paroubek J Leconte J Metrique et premier r sultats de l valution GRACE des tiqueteurs morphosyntaxiques pour le fran ais Amsili P ed Actes de TALN 99 pages 15 24 1999 Abiteboul 1997 Abiteboul S Querying semistructured data In ICDT pages 1 18 1997 Aldea et al 2003 Aldea A Bafiares Alc ntara R Bocio J Gramajo D Isern D Kokssis A Jim nez L Moreno A Riafio D An Ontology Based Knowledge Management Plataform In CAI IIWEb 03
153. s par mot cl s se montrent inefficaces quand l utilisateur veut trouver des informations pr cises sur le Web Ces techniques sont inefficaces car elles ram nent souvent une grande quantit de document inutiles ou dans le pire des cas des documents pertinents ne sont m mes pas trouv s Aldea et al 2003 L extraction d informations dans ces documents ramen s est r alis e actuellement essentiellement par des humains Il a t d j argument que des techniques autour du format XML et ses variantes Bray et al 2008 ne seraient pas suffisantes pour accro tre l efficacit des moteurs de recherche existants sur Web Espinasse et al 2007 Ainsi bien que XML puisse tre utilis dans la structuration de l information s mantique des informations il y a toujours l h ritage de t raoctets de documents qui ne seront probablement pas convertis ce format Kushmerick amp Thomas 2003 affirme que c est impossible de d terminer un sch ma d annotation parfait qui int gre diff rentes sources d informations et qui fonctionne correctement pour une grande vari t d applications Ces probl mes alors ont stimul la recherche de solutions qui donneraient l Internet le m me pouvoir de consultation des donn es structur es trouv es dans des bases de donn es actuelles Dans ce contexte l Extraction d Information EI consiste d un moyen d obtenir et d int grer les donn es contenues dans une collection de documents d un m me doma
154. s semi structur s Les donn es du Web ne sont pas structur es comme celles de bases de donn es Abiteboul 1997 Florescu et al 1998 Les pages Web sont en g n ral des documents semi structur s comme les documents HTML XHTML Ces documents sont d crits par les noms de balises qui sont charg es d un certain niveau de s mantique et de mise en forme Cette caract ristique rend les documents semi structur s compr hensibles par un humain Le langage HTML est le langage de mise en forme de pages Web l aide de paires de balises de mise en forme Chaque paire est constitu e d une balise ouvrante suite de caract res d limit s par les symboles et gt et d une balise fermante suite de caract res d limit s par les symboles et Tel langage permet la conception de documents plus riches que du texte plat en d crivant la fois la structure du document son contenu et sa pr sentation Par exemple dans le document HTML de la Fig 5 la balise H1 indique un titre et la balise P d limite un paragraphe de texte Les pages Web sont produites manuellement ou automatiquement par programme Dans ce cas elles int grent souvent des informations provenant d une base de donn es par exemple les pages de r sultats d un moteur de recherche ou les pages d un site e commerce Par 11 extension on peut voir l EI comme la transformation inverse mais inconnue de celle qui ont produit les pages en question html lt head gt
155. ses XML permettent d identifier les instances d entit s qui proviennent d un ensemble d l ments d finis par l utilisateur Le syst me TIES fournit un ensemble d interfaces et de classes pour l apprentissage le test et l application d un mod le d extraction aussi bien sur des textes libres que des textes fortement structur s Il incorpore l algorithme BWI pour l apprentissage L impl mentation de TIES par d faut emploie seulement des attributs orthographiques mais des attributs plus complexes par exemple des attributs morphosyntaxiques peuvent tre ajout s pour am liorer les performances en utilisant un pr processeur personnalis Un des objectifs de cette recherche sera d int grer un module traitant l tiquetage morphosyntaxique POS tagging int gr e dans l architecture originale du TIES Cette section montre comment la mise en uvre de l algorithme BWI par TIES s applique dans le cadre de notre recherche En effet il est examin en d tail comment utiliser TIES pour g n rer des r gles d extraction partir d un corpora donn Dans un premier temps l architecture originale de TIES est pr sent e en pr cisant comment les documents sont y repr sent s La proc dure suivre pour mettre en marche le syst me l aide de fichiers de configuration est ensuite expliqu e ainsi que des r gles induites et leurs correspondantes informations extraites 4 2 1 Description d taill e du syst me TIES version originale L ar
156. sistematicamente avaliar os efeitos que esses ltimos t m no desempenho do algoritmo de aprendizado Os resultados obtidos experimentalmente mostraram que o desempenho geral do sistema proposto compar vel a outros sistemas de EI do estado da arte Palavras chave Extra o de Informa o Indu o de Wrappers Boosting Classifia o Supervisionada POS Tagging Aprendizagem de M quina IX R sum Extraction d Information EI comprend des techniques et algorithmes r alisant deux t ches importantes l identification des informations d sir es pertinentes partir de documents structur s ou non structur s et le stockage de ces informations sous une forme appropri e visant l usage future Ce pr sent travail se concentre sur les syst mes d EI adaptatifs qui peuvent tre appliqu s sur de nouveaux domaines par l apprentissage artificiel machine learning en utilisant une collection de documents en entr e En particulier des techniques d induction automatique d extracteurs sont examin es pour l extraction d information qui repose sur l exploitation de r gularit s structurales pr sentes dans ces documents Wrappers extracteurs sont d finis comme des proc dures pour l extraction d informations d un document quelconque L induction d extracteurs est une technique qui utilise des algorithmes d apprentissage automatique pour la conception d extracteurs partir d un corpus pr alablement annot et qui donne de bons r s
157. sity of Science and Technology 2002 Zhai amp Liu 2005 Zhai Y Liu B Extracting web data usning instance based learning In Proceedings of Web Information Systems Engineering WISE pages 318 331 2005 88 Appendice A L gendes d tiquettes POS du QTAG en anglais Tag Meaning Tag Meaning 222 no tag assigned NNS noun plural is simple double quote NP proper noun singular pound sign NPS proper noun plural dollar sign PDT predeterminer i right single quote POS possessive ending left single quote PP personal pronoun left parenthesis round square curly or angle PP possessive pronoun right parenthesis round square curly or angle RB adverb comma RBR adverb comparative sentence final punctuation RBS adverb superlative i mid sentence punctuation RP particle BE be SYM symbol BED were TO infinitive marker to BEDZ was UH interjection BEG being VB verb base form BEM am VBD verb past tense BEN been VBG verb gerund or present participle BER are VBN verb past participle BEZ is VBP verb non 3rd person singular present CC coordinating conjunction VBZ verb 3rd person singular present CD cardinal number WDT wh determiner DO do WP wh pronoun DOD did WP possessive wh pronoun DOG doing WRB wh adverb DON done XNOT not and n t DOZ does DT determiner EX existential there FW foreign word HV have HVD had past tense HVG having HVN had past participle HVZ has IN preposition or subordinating con
158. t 50 50 10 fois type lemma et POS 5 Rapier Random split 50 50 10 fois Word POS et wordnet Word capitalisation lemma SIE 2 fold cross validation 5 fois alpha numerique et 10 ponctuation M TIES Random split 50 50 10 fois Word capitalisation et POS 3 Tab 10 R sum de configuration des syst mes valu s sur le corpus JOBS Syst me M thode d valuation Attributs utilis s W LP Random split 50 50 10 fois Word capitalisation et POS 5 Word capitalisation token GATE SVM Random split 50 50 10 fois type lemma et POS NERet 3 gazeteer Rapier 10 fold cross validation Word POS et wordnet M TIES Random split 50 50 10 fois Word capitalisation et POS 3 70 R sultats comparatifs sur les corpora Seminars et Jobs Les tables 11 et 12 pr sentent les performances des syst mes en termes de F measure sur le corpora Seminars et Jobs respectivement Les meilleurs r sultats F measure pour chaque slot sont en gras Pour les performances des syst mes SIE GATE SVM LP et Rapier on s appuie sur les r sultats donn s dans Giuliano et al 2006 Li et al 2004a Ciravegna 2003b Tab 11 Perfomances par slot de 5 syst mes sur le corpus Seminars speaker location stime etime Peas T SIE 86 6 GATE SVM 69 0 81 3 948 92 7 86 2 LP 77 6 75 0 99 0 95 5 86 0 Rapier 53 0 72 7 93 4 96 2 77 3 M TIES 86 2 88 8 93 9 96 7 91 4 Tab 12 Perfomances par slot de 4 syst mes sur le corpus J
159. t celles pour l it ration de listes pour les n uds non feuille Les bases de ces r gles d extraction sont les commandes SkipTo et SkipUntil qui d finit la transition de l automate d un tat A l tat B partir de la localisation d un landmark A gt B Un landmark est une s quence de tokens et ou classes s mantiques dans un document Parmi les classes s mantiques qui sont pr d finies par le syst me on peut citer des classes num rique alphanum rique alphab tique en majuscules des balises HTML ponctuation etc ou celles d finies par l utilisateur lui m me telles que nom email num ro de t l phone etc La r gle suivante illustr par la Fig 18 sert localiser un d limiteur gauche du slot r sum en HTML SkipTo Abstract SkipTo lt b gt Fig 18 Exemple d une r gle par conjonction Cabral 2004 Cet exemple est constitu par la combinaison de deux SkipTo commandes La premi re commande ira ignorer tous les caract res l int rieur d un n ud parent jusqu ce qu elle trouve le token Abstract en s arr tant au prochain token De ce point la seconde commande SkipTo va effectuer la m me proc dure pour trouver b Dans le cas de r gles pour des d limiteurs du c t droit l id e continue la m me en se modifiant seulement l ordre qui tokens seraient cherch s c est dire de droite gauche l int rieur d un n ud parent Dans le cas de l it ration d
160. t un programme capable d extraire des informations partir d un ensemble de documents corpus Ainsi l induction d extracteurs utilisent des algorithmes d apprentissage machine pour la g n ration de r gles d extraction partir d un ensemble de documents pr alablement tiquet s annot s une tape d apprentissage au lieu d tre apprises manuellement par un ing nieur de la connaissance Kushmerick 1997 2000 Un des pionniers dans l tude et le d veloppement de techniques d induction d extracteurs est le Prof Daniel Freitag qui en 2000 a con u un syst me d EI adaptatif reposant sur la classification supervis e comme technique de base pour l induction d extracteurs Sa technique d induction d extracteurs aussi appel Boosted Wrapper Induction BWI Freitag amp Kushmerick 2000 induisait des extracteurs d information destin es tre appliqu s sur des documents semi structur s comme XML et des pages HTML o leur syst me de balises internes leur rend un certain d gr e de structuration Plus tard divers travaux notamment Kauchak et al 2002 et Marty amp Torre 2004 expliquent les bons r sultats obtenus par le syst me BWI plus pr cis ment par les algorithmes qu il met en uvre Cependant dans le premier travail les auteurs ont analys comment les composants algorithmiques du BWI contribuaient son succ s Ils ont mis en vidence que la technique de boosting Freund amp Schapire 1990 est l l m
161. tagging 4 1 Architecture g n rale d un syst me d EI adaptatif L architecture classique d un syst me d EI adaptatif par l induction supervis e d extracteurs est illustr e par la Fig 23 C est une architecture modulaire en pipeline qui comporte un pr traitement linguistique les tapes d apprentissage et d application et pendant l tape d application un post traitement s mantique comme les trois modules les plus importants Fig 23 Un corpus de documents comprenant les textes du domaine d application et une structure cible template qui d finit les informations pertinentes extraire constituent l entr e minimale pour un syst me d IE 4 1 1 Pr traitement des textes d entr e Un corpus est souvent constitu de textes non structur es en langage naturel Une grande partie des informations pertinentes peut tre caract ris e par une certaine r gularit trouv e dans les propri t s linguistiques des textes Par cons quent l analyse linguistique peut donner des suggestions utiles et d terminer des attributs importants pour identifier le contenu pertinent Les composants linguistiques suivants se sont r v l e utiles pour EI tokenisation tiquetage morphosyntaxique POS tagging reconnaissance des entit s nomm es NER segmentation en phrases Sentence Spliting reconnaissance de structures de phrases grammaticaux Chunking et enfin r solution d anaphores Coreference Resolution 4 1 2 Apprentissage et
162. tifs des domaines sp cifiques par exemple la recherche acad mique le tourisme L objectif de l architecture AGATHE est de permettre le d veloppement de syst mes de collecte d information sur le Web sur des domaines restreints pouvant tre progressivement tendus Pour le d veloppement d AGATHE le domaine restreint de recherche de d part est celui de la recherche acad mique plus pr cis ment la tenue d v nements scientifiques conf rences ou workshops internationaux L architecture modulaire g n rale du syst me est illustr e par la Fig 1 Trois sous syst mes en interaction r alisent les diff rentes t ches Le Sous syst me de Recherche SSR Il est responsable de l interrogation des moteurs de recherche externes sur le web comme Google Il envoie les pages r cup r es vers le sous syst me d extraction qui va en extraire les informations pertinentes Le Sous syst me d Extraction SSE Il consiste en plusieurs clusters d extraction sp cialis s dans les diff rents domaines Chaque cluster r alise la validation des pages web leur classification et l extraction d informations partir de ces pages en fonction d un domaine sp cifique la recherche acad mique le tourisme etc Le Sous syst me d Utilisation SSU Il stock les informations extraites envoy es par le sous syst me d extraction et fournit une interface permettant aux utilisateurs d ex cuter les requ tes sur les donn es stock e
163. tor Settings Actions Help 4 QSearch On Oln p o example ontology KB example ont 2 fi e e E visiting a place or people i Location fileCAProgram FilesiMnM2wArchiveiDavidBrown html i University for Industry visits John Domingue Relation visitor 15 10 97 Documentation Relation visitor mat ws lis 1 University for Industry Design and Implementation Advisory Group Namespace 2 b x file AKTProject Ontologies example ontol and Chairman of Motorola visited ogy rdff 2 Domains as part of a fact visiting a place or people finding exercise prior to drafting his initial 100 Days Report to HM Ranges Government David was accompanied b person O OO Ready the Chairman of the Fig 288 Fen tre principale de l outil d annotation MnM 4 3 1 2 Module de Nettoyage de pages HTML HTMLCleaner tant donn que TIES exige des pages XHTM XML bien form s et que l on a constat des probl mes avec les pages Web dans les corpora choisis pour les exp rimentations on s est servir de l outil de nettoyage et transformations de pages HTMLCleaner Girardi 2007 pour 49 les r soudre La Fig 27 illustre que cet outil est appliqu sur les documents d entr e avant toute chose HtmlCleaner est un outil qui sert nettoyer automatiquement des fichiers en HTML XHTML Il enl ve des balises et des part
164. ue ce ne soit pas toujours le cas Les documents en langage naturel du corpus CPF contiennent peu de structuration de mise en forme Les principales raisons du choix de ce corpus sont d la connaissance du domaine et parce qu il offre une gamme raisonnable de difficult Une autre caract ristique souhaitable de ce corpus c est que leurs documents ont un certain degr de mise en forme semi structur Par cons quent les algorithmes d apprentissage devraient exploiter telle r gularit En outre il existe certaines diff rences entre les types d annotation du corpus Les dates importantes du CPF paper submission date notification date et camera ready copy date sont g n ralement bien prescrites par les textes qui les entourent tandis que les noms de workshop et conference sont plus d finis par leurs positions dans le document et ils ont une longueur plus variable De telles diff rences influenceront videmment la capacit des algorithmes d apprentissage identifier les types d annotation 5 2 Protocole Exp rimental Tout d abord les travaux de pr parations des corpora qui ont t n cessaires pour mener les exp riences sont pr sent s Les r sultats accompagn s de ses respectives discussions sont finalement expos s apr s la pr sentation de la m thodologie d valuation adopt e 5 2 1 Pr parations des corpora Dans cette recherche nous avons utilis HTMLCleaner pour v rifier et corrig s les balises HTML manquantes
165. ue tel syst me modulaire reposait sur l induction supervis e d extracteurs et qui permettait l extraction d information partir d un corpus d apprentissage manuellement annot et qui pouvait prendre en compte la syntaxe du langage naturel par le moyen d un nouveau module responsable pour l tiquetage morphosyntaxique sur ces documents Un autre objectif de ce travail tait de comparer l architecture de notre syst me d EI avec d autres syst mes de l tat de l art au travers diff rentes exp rimentations sur trois corpora de documents de r f rence en suivant une rigoureuse m thodologie d valuation de r sultats bien tablie dans la communaut scientifique du domaine de l EL Pour cela il a t alors d fini un protocole exp rimental pour bien mener les exp riences afin d avoir de r sultats plus fiables et pertinents Particuli rement ce protocole a consist 1 d finir la t che d EI sur les 3 corpora de documents ii d finir une m thodologie d valuation ii r aliser diff rentes exp riences visant d terminer les meilleurs param tres du mod le pour chaque type de corpus en prenant en compte l information POS ou non et iv finalement faire une valuation comparative parmi plusieurs syst mes d EI existants Les exp riences ont montr que par rapport au gain effectif d tiquetage POS sur les corpora le corpus CFP on a obtenu le meilleur r sultat On a obtenu une am lioration de plus de 596 pour
166. ultats lorsqu ils sont appliqu s sur des documents structur s semi structur s et en langage naturel libre Nous proposons dans ce travail un syst me d EI par induction supervis e d extracteurs reposant sur l algorithme Boosted Wrapper Induction BWT dans lequel l algorithme d AdaBoost est employ pour g n rer une proc dure d extraction g n rique qui combine un ensemble d extracteurs sp cifiques par vote pond r D autres auteurs ont tudi comment la technique de boosting contribue au succ s de l algorithme de BWI et ont examin sa performance vers la direction ambitieuse de l employer comme m thode d IE pour les documents en langage naturel Ce fait a motiv l inclusion d tiquetage POS Parties du Discours dans le pr traitement dans notre syst me des documents Afin d valuer la performance de ce syst me plusieurs exp riences ont t men es sur trois corpora d sign s pour la t che d extraction d information classique par slot D autres exp riences ont t galement r alis es en utilisant plusieurs combinaisons d attributs avec l objectif d tudier syst matiquement leurs effets sur la performance de l algorithme d apprentissage Les r sultats obtenus empiriquement ont montr que les performances de notre syst me taient comparables d autres syst mes de l tat de l art Mots cl s Extraction d information Induction d extracteurs Classification Supervis e Parties du Discours Apprentissage Machi
167. ut 65 aussi remarquer que ces r sultats sont semblables ceux obtenus par Li et al 2004 Li et al ont r alis la m me exp rience qu on vient de discuter sur les corpora Seminars et Jobs en utilisant l algorithme SVM et ils ont galement constat un gain tr s faible sur le corpus Seminars et m me un impact n gative du tagage POS sur le corpus Jobs Plus pr cis ment la baisse de performance a t de moins de 1 pour ce dernier cas De 17 slots qui constituent le sch ma d extraction pour le corpus JOBS on note que plus de la moiti des champs ont un contenu tr s structur voire r gulier C est le cas des slots post date country id state city req years experience langage salary et recruiter Le syst me a eu un score parfait de 10046 sur le premier slot de la liste post date Pr c Rappel F1 Corpus 0 974 0 953 0 963 Seminars 0 945 0 778 0 853 Jobs 0 939 0 780 0 853 0 891 0 571 0 696 CFP 0 896 0 591 0 712 a b Pr c Rappel F1 0 971 0 964 0 967 Corpus Seminars Jobs CFP Fig 41 Perfomance g n ral d extraction de M TIES sur les corpora Seminars Jobs et CFP sans a et avec b POS 5 3 2 Diff rents ensembles d attributs Un autre aspect de grande importance analyser est d tudier l influence des attributs espace d hypoth ses sur le corpora On a choisi la validation hold out en divisant chaque corpus en deux moiti s la premi re pour l apprentissage la deuxi me pou
168. variation concernant la capacit d identifier certains slots Fig 44 Amilcare atteint les meilleurs scores en 6 sur 11 slots tandis que M TIES le fait pour 4 slots Le syst me Yaoyong a obtenu la meilleur F measure juste pour 1 slot cible Lors de l examen des F measures la meilleure performance est observ e sur les 4 dates du corpus workshop date workshop papper submission date workshop camera ready copy date et worshop notification acceptance date Ces dates sont relativement faciles extraire car elles sont sous en format bien d fini et fortement prescrites par le texte qui les entoure D autre part la plus baisse performance de tous les syst mes a eu lieu pour les 3 slots relatifs aux Conferences ceux ci ont un nombre d exemples relativement bas dans le corpus Ce qui indique un nombre insuffisant d exemples baisse repr sentation pour s achever de bonnes g n ralisations Amilcare a obtenu le plus bas scores par rapport aux autres syst mes pour les slots workshop name workshop location et conference name ce qui montre d une fagon claire que leurs techniques ne garantissent pas la bonne performance sur tous les types de slots En examinant les documents on peut noter que ces slots probl matiques pour Amilcare ne sont pas sp cifi s par leurs contextes mais ils sont plut t d termin s par leurs contenus et leurs places dans le document Au contraire pour M TIES il montre un grand cart de performance pour ces slots gr

Rinaldo José de Lima - Universidade Federal de Pernambuco

Contents

Download Pdf Manuals

Related Search

Related Contents

Rinaldo Jos&eacute; de Lima - Universidade Federal de Pernambuco

Contents

Download Pdf Manuals

Related Search

Related Contents

Rinaldo José de Lima - Universidade Federal de Pernambuco