Apprentissage à base de Noyaux Sémantiques pour le Traitement de Données Textuelles - Page 1 - test Tous nos livres sont imprimés dans les règles environnementales les plus strictes Il est interdit de reproduire intégralement ou partiellement la présente publication sans autorisation du Centre Français d’exploitation du droit de Copie (CFC) – 20 rue des GrandsAugustins – 75006 PARIS – Tél. : 01 44 07 47 70 / Fax : 01 46 34 67 19. © Éditions Edilivre – Collection Universitaire – 2008 ISBN : 978-2-35607-643-4 Dépôt légal : Juillet 2008 Tous droits de reproduction, d’adaptation et de traduction, intégrale ou partielle réservés pour tous pays. No d’ordre : No attribu´ par la biblioth`que : e e ´ ´ Universite Paris 13 – Institut Galilee Laboratoire d’Informatique de Paris Nord UMR 7030 du CNRS ` THESE pr´sent´e pour l’obtention du titre de e e Docteur en Sciences sp´cialit´ e e Informatique par Sujeevan ASEERVATHAM Apprentissage ` base de Noyaux S´mantiques a e pour le Traitement de Donn´es Textuelles e dirig´e par e Pr. Youn`s Bennani e Soutenue le 12 d´cembre 2007 devant le jury compos´ de : e e M. M. M. M. M. M. Mme M. Massih-Reza Amini Youn`s Bennani e Christophe Fouquer´ e Cyril Goutte Jean-Fran¸ois Marcotorchino c Alain Rakotomamonjy Mich`le Sebag e Emmanuel Viennet Maˆ de Conf´rences, LIP6 – Universit´ de Paris 6 ıtre e e Professeur, LIPN – Universit´ de Paris 13 e Professeur, LIPN – Universit´ de Paris 13 e Agent de Recherche, CNRC – Canada Directeur Scientifique, Thal`s Land & Joint e Professeur, INSA – Universit´ de Rouen e Directrice de Recherche, CNRS – LRI (Paris 11) Maˆ de Conf´rences, LIPN, Universit´ de Paris 13 ıtre e e R´sum´ e e Apprentissage ` base de Noyaux S´mantiques pour le Traitement de Donn´es a e e Textuelles. Depuis le d´but des ann´es 80, les m´thodes statistiques et, plus sp´cifiquement, les m´thodes d’ape e e e e prentissage appliqu´es au traitement de donn´es textuelles connaissent un int´rˆt grandissant. Cette e e ee tendance est principalement due au fait que la taille des corpus est en perp´tuelle croissance. Ainsi, les e m´thodes utilisant le travail d’experts sont devenues des processus coˆteux perdant peu a peu de leur e u ` popularit´ au profit des syst`mes d’apprentissage. e e Dans le cadre de cette th`se, nous nous int´ressons principalement a deux axes. Le premier axe porte e e ` sur l’´tude des probl´matiques li´es au traitement de donn´es textuelles structur´es par des approches e e e e e a ` base de noyaux. Nous pr´sentons, dans ce contexte, un noyau s´mantique pour les documents struce e tur´s en sections notamment sous le format XML. Le noyau tire ses informations s´mantiques ` partir e e a d’une source de connaissances externe, ` savoir un th´saurus. Notre noyau a ´t´ test´ sur un corpus a e ee e de documents m´dicaux avec le th´saurus m´dical UMLS. Il a ´t´ class´, lors d’un challenge internae e e ee e tional de cat´gorisation de documents m´dicaux, parmi les 10 m´thodes les plus performantes sur 44. e e e Le second axe porte sur l’´tude des concepts latents extraits par des m´thodes statistiques telles que e e l’analyse s´mantique latente (LSA). Nous pr´sentons, dans une premi`re partie, des noyaux exploitant e e e des concepts linguistiques provenant d’une source externe et des concepts statistiques issus de la LSA. Nous montrons qu’un noyau int´grant les deux types de concepts permet d’am´liorer les performances. e e Puis, dans un deuxi`me temps, nous pr´sentons un noyau utilisant des LSA locaux afin d’extraire des e e concepts latents permettant d’obtenir une repr´sentation plus fine des documents. e Abstract Semantic Kernel-based Machine Learning for Textual Data Processing. Since the early eighties, statistical methods and, more specifically, the machine learning for textual data processing have known a considerable growth of interest. This is mainly due to the fact that the number of documents to process is growing exponentially. Thus, expert-based methods have become too costly, losing the research focus to the profit of machine learning-based methods. In this thesis, we focus on two main issues. The first one is the processing of semi-structured textual data with kernel-based methods. We present, in this context, a semantic kernel for documents structured by sections under the XML format. This kernel captures the semantic information with the use of an external source of knowledge e.g., a thesaurus. Our kernel was evaluated on a medical document corpus with the UMLS thesaurus. It was ranked in the top ten of the best methods, according to the F1-score, among 44 algorithms at the 2007 CMC Medical NLP International Challenge. The second issue is the study of the use of latent concepts extracted by statistical methods such as the Latent Semantic Analysis (LSA). We present, in a first part, kernels based on linguistic concepts from external sources and on latent concepts of the LSA. We show that a kernel integrating both kinds of concepts improves the text categorization performances. Then, in a second part, we present a kernel that uses local LSAs to extract latent concepts. Local latent concepts are used to have a more finer representation of the documents. Table des mati`res e 1 Introduction 1.1 Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Organisation de la th`se et contributions . . . . . . . . . . . . . . . . . . . . . . e 2 Apprentissage num´rique e 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . 2.2 Principes g´n´raux . . . . . . . . . . . . . . . . . . ee 2.2.1 Apprentissage Supervis´ . . . . . . . . . . . e 2.2.2 Apprentissage Semi-Supervis´ . . . . . . . . e 2.2.3 Apprentissage Non-Supervis´ . . . . . . . . e 2.3 Les S´parateurs a Vaste Marge (SVM) . . . . . . . e ` 2.3.1 L’hyperplan S´parateur Optimal . . . . . . e 2.3.2 Les SVM pour le classement . . . . . . . . . 2.3.3 Les SVM pour l’estimation de densit´ . . . e 2.3.4 Les SVM pour la classification (clustering) . 2.3.5 Les SVM pour la r´gression (SVR) . . . . . e 2.3.6 Les noyaux (kernels) . . . . . . . . . . . . . 2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . 1 1 2 3 5 5 5 6 13 19 20 20 23 37 40 43 45 51 53 53 53 54 56 64 65 68 71 72 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Apprentissage ` base de noyaux pour le texte a 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Apprentissage pour donn´es textuelles . . . . . . . . . . . . . e 3.2.1 Probl´matique li´e aux textes . . . . . . . . . . . . . . e e 3.2.2 Pr´-traitement pour l’apprentissage . . . . . . . . . . e 3.2.3 Prise de d´cision pour le classement . . . . . . . . . . e 3.2.4 Les mesures des performances . . . . . . . . . . . . . . 3.2.5 M´thodes de r´f´rence pour la cat´gorisation de texte e ee e 3.3 Noyaux pour documents semi-structur´s . . . . . . . . . . . . e 3.3.1 Le noyau de convolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 4 Un 4.1 4.2 4.3 4.4 3.3.2 Les noyaux pour les s´quences de e 3.3.3 Les noyaux pour les arbres . . . 3.3.4 Les noyaux pour les graphes . . . Conclusion . . . . . . . . . . . . . . . . caract`res e ...... ...... ...... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 78 85 89 91 91 91 92 96 96 97 99 100 101 102 103 109 111 111 111 112 114 115 117 120 122 124 125 126 128 130 137 138 139 140 142 150 150 nouveau noyau s´mantique pour documents e Introduction . . . . . . . . . . . . . . . . . . . . . L’environnement UMLS . . . . . . . . . . . . . . Repr´sentation Arborescente des Documents . . e Le Noyau S´mantique . . . . . . . . . . . . . . . e 4.4.1 Le cadre g´n´ral . . . . . . . . . . . . . . ee 4.4.2 Le noyau bas´ sur l’UMLS . . . . . . . . . e 4.4.3 Le noyau de concepts . . . . . . . . . . . ´ 4.5 Evaluation exp´rimentale . . . . . . . . . . . . . e 4.5.1 Le corpus . . . . . . . . . . . . . . . . . . 4.5.2 La pr´paration des exp´riences . . . . . . e e 4.5.3 Les r´sultats exp´rimentaux . . . . . . . . e e 4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . semi-structur´s e ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Des nouveaux noyaux bas´s sur l’information s´mantique latente e e 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Information Latente . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.1 De l’espace des termes ` un espace s´mantique . . . . . . . . a e 5.2.2 Le mod`le d’espace vectoriel g´n´ralis´ (GVSM) . . . . . . . e ee e 5.2.3 L’Analyse S´mantique Latente (LSA) . . . . . . . . . . . . . e 5.2.4 L’Analyse S´mantique Latente Locale . . . . . . . . . . . . . e 5.2.5 Le mod`le d’espace vectoriel de domaine (Domain VSM) . . e 5.2.6 La LSA probabiliste . . . . . . . . . . . . . . . . . . . . . . . 5.2.7 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Un mod`le d’espace vectoriel de concepts pour noyaux s´mantiques . e e 5.3.1 Noyau lin´aire du mod`le d’espace vectoriel de concepts . . . e e 5.3.2 Le noyau CVSM latent . . . . . . . . . . . . . . . . . . . . . ´ 5.3.3 Evaluation exp´rimentale . . . . . . . . . . . . . . . . . . . . e 5.3.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Un noyau s´mantique int´grant les concepts latents locaux . . . . . . e e 5.4.1 Un espace s´mantique de concepts locaux . . . . . . . . . . . e 5.4.2 Le noyau s´mantique enrichi . . . . . . . . . . . . . . . . . . e ´ 5.4.3 Evaluation exp´rimentale . . . . . . . . . . . . . . . . . . . . e 5.4.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Autres contributions : Extraction de motifs s´quentiels e 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Probl´matique de l’extraction de motifs s´quentiels . . . . . . . . . . . e e 6.2.1 Formulation du probl`me . . . . . . . . . . . . . . . . . . . . . e 6.2.2 Famille Apriori . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.3 Algorithme GSP . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 bitSPADE : un nouvel algorithme d’extraction de s´quences fr´quentes e e 6.3.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3.3 The SPADE Algorithm . . . . . . . . . . . . . . . . . . . . . . 6.3.4 The bitSPADE Algorithm . . . . . . . . . . . . . . . . . . . . . 6.3.5 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . 6.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Conclusion et perspectives Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 153 153 154 156 165 170 171 171 172 175 177 179 183 187
Apprentissage à base de Noyaux Sémantiques pour le Traitement de Données Textuelles - Page 1
Apprentissage à base de Noyaux Sémantiques pour le Traitement de Données Textuelles - Page 2
wobook
edilivre.com