Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Cette thèse porte sur des problèmes d'exploration de données avec le point de vue de la recherche opérationnelle. L'exploration de données consiste en l'apprentissage de nouvelles connaissances à partir d'observations contenues dans une base de données. La nature des problèmes rencontrés dans ce domaine est proche de celle des problèmes de la recherche opérationnelle: grandes instances, objectifs complexes et difficulté algorithmique. L'exploration de données peut aussi se modéliser comme un problème d'optimisation avec un objectif partiellement connu. Cette thèse se divise en deux parties. La première est une introduction à l'exploration de données. Elle présente l'Analyse Combinatoire de Données (ACD), une méthode d'exploration de données issue de l'optimisation discrète. Cette méthode est appliquée à des données médicales originales et une extension aux problèmes d'analyse de temps de survie est proposée. L'analyse de temps de survie consiste à modéliser le temps avant un événement (typiquement un décès ou une rechute). Les heuristiques proposées utilisent des techniques classiques de recherche opérationnelle telles que la programmation linéaire en nombres entiers, la décomposition de problème, des algorithmes gloutons. La seconde partie est plus théorique et s'intéresse à deux problèmes combinatoires rencontrés dans le domaine de l'exploration de données. Le premier est un problème de partitionnement de graphes en sous-graphes denses pour l'apprentissage non supervisé. Nous montrons la complexité algorithmique de ce problème et nous proposons un algorithme polynomial basé sur la programmation dynamique lorsque le graphe est un arbre. Cet algorithme repose sur des résultats de la théorie des couplages. Le second problème est une généralisation des problèmes de couverture par les tests pour la sélection d'attributs. Les lignes d'une matrice sont coloriées en deux couleurs. L'objectif est de trouver un sous-ensemble minimum de colonnes tel que toute paire de lignes avec des couleurs différentes restent distinctes lorsque la matrice est restreinte au sous-ensemble de colonnes. Nous montrons des résultats de complexité ainsi que des bornes serrées sur la taille des solutions optimales pour différentes structures de matrices. / This thesis focuses on some data mining problems with an operations research point of view. Data mining is the process of learning new knowledge from large datasets. The problems in this field are close to the ones encountered in operations research: Large instances, complex objectives and algorithmic difficulty. Moreover, learning knowledge from a dataset can be viewed as a particular optimization problem with a partially known objective function. This thesis is divided into two main parts. The first part starts with an introduction to data mining. Then it presents a specific method from the field of discrete optimization known as Logical Analysis of Data (LAD). In this part, an original medical application and an extension of LAD to survival analysis are presented. Survival analysis is the modeling of time to event (typically death or failure). The proposed heuristics are derived from classical operations research methods such as integer programming, problem decomposition and greedy algorithms. The second part is more theoretical and focuses on two combinatorial problems encountered while solving practical data mining problems. The first one is a problem of graph partition into dense subgraphs for unsupervised learning. We emphasize the algorithmic complexity of this problem, and give a polynomial algorithm based on dynamic programming when the graph is a tree. This algorithm relies on famous combinatorial optimization results in matching theory. The second problem is a generalization of test cover for feature selection. The rows of a binary matrix are bicolored. The objective is to find a minimum subset of columns such that any pair of rows with different colors are still distinct when the matrix is restricted to the subset of columns. We give complexity results and tight bounds on the size of the optimal solutions for various matrix structures.

Cette thèse porte sur des problèmes d'exploration de données avec le point de vue de la recherche opérationnelle. L'exploration de données consiste en l'apprentissage de nouvelles connaissances à partir d'observations contenues dans une base de données. La nature des problèmes rencontrés dans ce domaine est proche de celle des problèmes de la recherche opérationnelle: grandes instances, objectifs complexes et difficulté algorithmique. L'exploration de données peut aussi se modéliser comme un problème d'optimisation avec un objectif partiellement connu. Cette thèse se divise en deux parties. La première est une introduction à l'exploration de données. Elle présente l'Analyse Combinatoire de Données (ACD), une méthode d'exploration de données issue de l'optimisation discrète. Cette méthode est appliquée à des données médicales originales et une extension aux problèmes d'analyse de temps de survie est proposée. L'analyse de temps de survie consiste à modéliser le temps avant un événement (typiquement un décès ou une rechute). Les heuristiques proposées utilisent des techniques classiques de recherche opérationnelle telles que la programmation linéaire en nombres entiers, la décomposition de problème, des algorithmes gloutons. La seconde partie est plus théorique et s'intéresse à deux problèmes combinatoires rencontrés dans le domaine de l'exploration de données. Le premier est un problème de partitionnement de graphes en sous-graphes denses pour l'apprentissage non supervisé. Nous montrons la complexité algorithmique de ce problème et nous proposons un algorithme polynomial basé sur la programmation dynamique lorsque le graphe est un arbre. Cet algorithme repose sur des résultats de la théorie des couplages. Le second problème est une généralisation des problèmes de couverture par les tests pour la sélection d'attributs. Les lignes d'une matrice sont coloriées en deux couleurs. L'objectif est de trouver un sous-ensemble minimum de colonnes tel que toute paire de lignes avec des couleurs différentes restent distinctes lorsque la matrice est restreinte au sous-ensemble de colonnes. Nous montrons des résultats de complexité ainsi que des bornes serrées sur la taille des solutions optimales pour différentes structures de matrices.

Cet élaborât veut donner un nouvel approche à l’étude du corpus jābirien, en prenant compte de la littérature et des études précédents et des problématiques inhérentes à ce particulier corpus (synonymie, polysémie, dispersion du savoir, citations d’autres auteurs, hypertextualité). Grace aux nouvelles technologies d’analyse computationnelle ce travail vise à la digitalisation de textes édités (Muḫtār Rasāʾil, Tabdīr al-iksīr al-aʿẓam, Kitāb al- ahjār), pour créer un corpus numérique annoté selon le Text Encoding Initiative (TEI), le système d’annotation le plus utilisé dans le Natural Language Processing (NLP). La première section de la thèse comprend une introduction historique, prenant compte de la figure de Jābir et de son travail, de la querelle sur son existence et de l’histoire de la science Arabe médiévale ; et méthodologique, qui explique les outils utilisés pour l’analyse. La deuxième section est opérationnelle : le travail est expliqué dans tous ses détails et où les choix de numérisation et analyse sont exposés. Les problématiques présentées dans la première section trouvent ici des réponses pour ce qui concerne leur analyse. Le noyau de ce travail est représenté cependant par les Appendices, divisées en quatre parties : Les Appendices A, B et C sont des extraits bruts de la numérisation, qui donnent une idée du processus d’annotation selon le standard TEI. Les trois textes édités sont représentés par le premier livre de l’édition. L’Appendice D est un échantillon de concordances qui se base sur la lemmatisation des deux premiers livres du Tadbīr. L’Appendice E est une liste de fréquence du même échantillon utilisé pour la création des concordances. / This work presents a novel approach to the study of the Jābirian corpus while taking into consideration the existent works and literature and the problems of this peculiar corpus (synonymy, polysemy, dispersion of the knowledge, quotes od other authors, hypertextuality). Thanks to the modern technologies of computational analysis, this thesis aims to the digitalization of edited texts (Muḫtār Rasāʾil, Tabdīr al-iksīr al-aʿẓam, Kitāb al- ahjār) in order to create a digitalized corpus tagged following the Text Encoding Initiative (TEI), the most used annotation in Natural Language Processing (NLP). Section I is an introduction on the historical setting and remarks of the subject of the texts studied, comprising also an excursus on the figure of Jābir Ibn Hayyān and the querelle on his existence; and an explanation of the methodological setting in which this work is settled. Section II is the operational part, where are shown the compromises used in the realization of the digitalized corpus, as well as the strategies used so as to render the various issues presented in Section I. Section II presents the set of choices that tried to aswer to the questions made in Section I. The core of the work is represented by the Appendices, divided in four parts: Appendix A, B and C are extracts of the digitalized corpus, it was decided to include the first section of all the three source books, in order to represent every detail of the digitalization strategies and processes. Appendix D comprise a sample of concordances based on the lemmatization of the edition of the first two books of the Tadbīr. Appendix E is the frequency list of the same sample used for the concordances.

Une plateforme de conception est une solution totale qui permet à une équipe de conception de développer un système sur puce. Une telle plateforme se compose d'un ensemble de bibliothèques et de circuits réutilisables (IPs), d'outils de CAO et de kits de conception en conformité avec les flots de conception et les méthodologies supportés. Les spécifications de ce type de plateforme offrent un large éventail d'informations, depuis des paramètres de technologie, jusqu'aux informations sur les outils. En outre, les développeurs de bibliothèque/IP ont des difficultés à obtenir les données nécessaires à partir ces spécifications en raison de leur informalité et complexité. Dans cette thèse, nous proposons des méthodologies, des flots et des outils pour formaliser les spécifications d'une plateforme de conception et les traiter. Cette description proposée vise à être utilisée comme une référence pour générer et valider les bibliothèques et les IPs. Nous proposons un langage de spécification basé sur XML (nommé LDSpecX). De plus, nous présentons une méthode basée sur des références pour créer une spécification fiable en LDSpecX et des mots-clés basés sur des tâches pour en extraire les données efficacement. A l'aide des solutions proposées, nous développons une plateforme de spécification. Nous développons une bibliothèque de cellules standard en utilisant cette plateforme de spécification. Nous montrons ainsi que notre approche permet de créer une spécification complète et cohérente avec une réduction considérable du temps. Cette proposition comble également l'écart entre les spécifications et le système automatique existant pour le développement rapide de bibliothèques/IPs. / A design platform (DP) is a total solution to build a System-On-Chip (SOC). DP consists of a set of libraries/IPs, CAD tools and design kits in conformity with the supported design flows and methodologies. The DP specifications provide a wide range of information from technology parameters like Process-Voltage-Temperature (PVT) corners to CAD tools’ information for library/IP development. However, the library/IP developers have difficulties in obtaining the desired data from the existing specifications due to their informality and complexity. In this thesis, we propose methodologies, flows and tools to formalize the DP specifications for their unification and to deal with it. The proposed description is targeting to be used as a reference to generate and validate libraries (standard cells, I/O, memory) as well as complex IPs (PLL, Serdes, etc.). First, we build a suitable data model to represent all required information for library/IP development and then propose a specification language named Library Development Specification based on XML (LDSpecX). Furthermore, we introduce a reference-based method to create a reliable specification in LDSpecX and task-based keywords to efficiently extract data from it. On the basis of the proposed solutions, we develop a specification platform. Experimentally, we develop a standard cell library from the specification creation to library validation by using the specification platform. We show that our approach enables to create a complete and consistent specification with a considerable reduction in time. It also bridges the gap between the specification and current automatic system for rapid library/IP development.

Les systèmes de traduction automatique obtiennent aujourd'hui de bons résultats sur certains couples de langues comme anglais - français, anglais - chinois, anglais - espagnol, etc. Les approches de traduction empiriques, particulièrement l'approche de traduction automatique probabiliste, nous permettent de construire rapidement un système de traduction si des corpus de données adéquats sont disponibles. En effet, la traduction automatique probabiliste est fondée sur l'apprentissage de modèles à partir de grands corpus parallèles bilingues pour les langues source et cible. Toutefois, la recherche sur la traduction automatique pour des paires de langues dites "peu dotés" doit faire face au défi du manque de données. Nous avons ainsi abordé le problème d'acquisition d'un grand corpus de textes bilingues parallèles pour construire le système de traduction automatique probabiliste. L'originalité de notre travail réside dans le fait que nous nous concentrons sur les langues peu dotées, où des corpus de textes bilingues parallèles sont inexistants dans la plupart des cas. Ce manuscrit présente notre méthodologie d'extraction d'un corpus d'apprentissage parallèle à partir d'un corpus comparable, une ressource de données plus riche et diversifiée sur l'Internet. Nous proposons trois méthodes d'extraction. La première méthode suit l'approche de recherche classique qui utilise des caractéristiques générales des documents ainsi que des informations lexicales du document pour extraire à la fois les documents comparables et les phrases parallèles. Cependant, cette méthode requiert des données supplémentaires sur la paire de langues. La deuxième méthode est une méthode entièrement non supervisée qui ne requiert aucune donnée supplémentaire à l'entrée, et peut être appliquée pour n'importe quelle paires de langues, même des paires de langues peu dotées. La dernière méthode est une extension de la deuxième méthode qui utilise une troisième langue, pour améliorer les processus d'extraction de deux paires de langues. Les méthodes proposées sont validées par des expériences appliquées sur la langue peu dotée vietnamienne et les langues française et anglaise.

Les performances des systèmes de traduction automatique statistique dépendent de la disponibilité de textes parallèles bilingues, appelés aussi bitextes. Cependant, les textes parallèles librement disponibles sont aussi des ressources rares : la taille est souvent limitée, la couverture linguistique insuffisante ou le domaine des textes n’est pas approprié. Il y a relativement peu de paires de langues pour lesquelles des corpus parallèles de tailles raisonnables sont disponibles pour certains domaines. L’une des façons pour pallier au manque de données parallèles est d’exploiter les corpus comparables qui sont plus abondants. Les travaux précédents dans ce domaine n’ont été appliqués que pour la modalité texte. La question que nous nous sommes posée durant cette thèse est de savoir si un corpus comparable multimodal permet d’apporter des solutions au manque de données parallèles dans le domaine de la traduction automatique.Dans cette thèse, nous avons étudié comment utiliser des ressources provenant de différentes modalités (texte ou parole) pour le développement d’un système de traduction automatique statistique. Une première partie des contributions consisteà proposer une technique pour l’extraction des données parallèles à partir d’un corpus comparable multimodal (audio et texte). Les enregistrements sont transcrits avec un système de reconnaissance automatique de la parole et traduits avec unsystème de traduction automatique. Ces traductions sont ensuite utilisées comme requêtes d’un système de recherche d’information pour sélectionner des phrases parallèles sans erreur et générer un bitexte. Dans la deuxième partie des contributions, nous visons l’amélioration de notre méthode en exploitant les entités sous-phrastiques créant ainsi une extension à notre système en vue de générer des segments parallèles. Nous améliorons aussi le module de filtrage. Enfin, nous présentons plusieurs manières d’aborder l’adaptation des systèmes de traduction avec les données extraites.Nos expériences ont été menées sur les données des sites web TED et Euronews qui montrent la faisabilité de nos approches. / The performance of Statistical Machine Translation Systems statistics depends on the availability of bilingual parallel texts, also known as bitexts. However, freely available parallel texts are also a sparse resource : the size is often limited, languistic coverage insufficient or the domain of texts is not appropriate. There are relatively few pairs of languages for which parallel corpora sizes are available for some domains. One way to overcome the lack of parallel data is to exploit comparable corpus that are more abundant. Previous work in this area have been applied for the text modality. The question we asked in this thesis is : can comparable multimodal corpus allows us to make solutions to the lack of parallel data in machine translation? In this thesis, we studied how to use resources from different modalities (text or speech) for the development of a Statistical machine translation System. The first part of the contributions is to provide a method for extracting parallel data from a comparable multimodal corpus (text and audio). The audio data are transcribed with an automatic speech recognition system and translated with a machine translation system. These translations are then used as queries to select parallel sentences and generate a bitext. In the second part of the contribution, we aim to improve our method to exploit the sub-sentential entities creating an extension of our system to generate parallel segments. We also improve the filtering module. Finally, we présent several approaches to adapt translation systems with the extracted data. Our experiments were conducted on data from the TED and Euronews web sites which show the feasibility of our approaches.

Les systèmes de traduction automatique obtiennent aujourd'hui de bons résultats sur certains couples de langues comme anglais – français, anglais – chinois, anglais – espagnol, etc. Les approches de traduction empiriques, particulièrement l'approche de traduction automatique probabiliste, nous permettent de construire rapidement un système de traduction si des corpus de données adéquats sont disponibles. En effet, la traduction automatique probabiliste est fondée sur l'apprentissage de modèles à partir de grands corpus parallèles bilingues pour les langues source et cible. Toutefois, la recherche sur la traduction automatique pour des paires de langues dites «peu dotés» doit faire face au défi du manque de données. Nous avons ainsi abordé le problème d'acquisition d'un grand corpus de textes bilingues parallèles pour construire le système de traduction automatique probabiliste. L'originalité de notre travail réside dans le fait que nous nous concentrons sur les langues peu dotées, où des corpus de textes bilingues parallèles sont inexistants dans la plupart des cas. Ce manuscrit présente notre méthodologie d'extraction d'un corpus d'apprentissage parallèle à partir d'un corpus comparable, une ressource de données plus riche et diversifiée sur l'Internet. Nous proposons trois méthodes d'extraction. La première méthode suit l'approche de recherche classique qui utilise des caractéristiques générales des documents ainsi que des informations lexicales du document pour extraire à la fois les documents comparables et les phrases parallèles. Cependant, cette méthode requiert des données supplémentaires sur la paire de langues. La deuxième méthode est une méthode entièrement non supervisée qui ne requiert aucune donnée supplémentaire à l'entrée, et peut être appliquée pour n'importe quelle paires de langues, même des paires de langues peu dotées. La dernière méthode est une extension de la deuxième méthode qui utilise une troisième langue, pour améliorer les processus d'extraction de deux paires de langues. Les méthodes proposées sont validées par des expériences appliquées sur la langue peu dotée vietnamienne et les langues française et anglaise. / Nowadays, machine translation has reached good results when applied to several language pairs such as English – French, English – Chinese, English – Spanish, etc. Empirical translation, particularly statistical machine translation allows us to build quickly a translation system if adequate data is available because statistical machine translation is based on models trained from large parallel bilingual corpora in source and target languages. However, research on machine translation for under-resourced language pairs always faces to the lack of training data. Thus, we have addressed the problem of retrieving a large parallel bilingual text corpus to build a statistical machine translation system. The originality of our work lies in the fact that we focus on under-resourced languages for which parallel bilingual corpora do not exist in most cases. This manuscript presents our methodology for extracting a parallel corpus from a comparable corpus, a richer and more diverse data resource over the Web. We propose three methods of extraction. The first method follows the classical approach using general characteristics of documents as well as lexical information of the document to retrieve both parallel documents and parallel sentence pairs. However, this method requires additional data of the language pair. The second method is a completely unsupervised method that does not require additional data and it can be applied to any language pairs, even under resourced language pairs. The last method deals with the extension of the second method using a third language to improve the extraction process (triangulation). The proposed methods are validated by a number of experiments applied on the under resourced Vietnamese language and the English and French languages.

No description available.