Nous proposons dans cette thèse un système permettant de déterminer, à partir des données envoyées sur les microblogs, les évènements qui stimulent l’intérêt des utilisateurs durant une période donnée et les dates saillantes de chaque évènement. Étant donné son taux d’utilisation élevé et l’accessibilité de ses données, nous avons utilisé la plateforme Twitter comme source de nos données. Nous traitons dans ce travail les tweets portant sur la Tunisie dont la plupart sont écrits par des tunisiens. La première tâche de notre système consistait à extraire automatiquement les tweets d’une façon continue durant 67 jours (de 8 février au 15 avril 2012). Nous avons supposé qu’un évènement est représenté par plusieurs termes dont la fréquence augmente brusquement à un ou plusieurs moments durant la période analysée. Le manque des ressources nécessaires pour déterminer les termes (notamment les hashtags) portant sur un même sujet, nous a obligé à proposer des méthodes permettant de regrouper les termes similaires. Pour ce faire, nous avons eu recours à des méthodes phonétiques que nous avons adaptées au mode d’écriture utilisée par les tunisiens, ainsi que des méthodes statistiques. Pour déterminer la validité de nos méthodes, nous avons demandé à des experts, des locuteurs natifs du dialecte tunisien, d’évaluer les résultats retournés par nos méthodes. Ces groupes ont été utilisés pour déterminer le sujet de chaque tweet et/ou étendre les tweets par de nouveaux termes. Enfin, pour sélectionner l'ensemble des évènements (EV), nous nous sommes basés sur trois critères : fréquence, variation et TF-IDF. Les résultats que nous avons obtenus ont montré la robustesse de notre système. / In this thesis, we propose a method to highlight users’ concerns from a set of Twitter messages. In particular, we focus on major events that stimulate the user’s interest within a given period. Given its rate of use and accessibility of data, we used Twitter as a source of our data. In this work, we use tweets related to Tunisia, most of them being written by Tunisians. The first task of our system was to continuously extract tweets during 67 days (from February 8th to April 15th, 2012). We assumed that an event is represented by several terms whose frequency sharply increases one or more times during the analyzed period. Due to the lack of resources that allow determining the terms (including hashtags) referring to the same topic, we propose methods that help grouping similar terms. To do this, we used phonetic methods adapted to the way Tunisians write and statistical methods. To determine the validity of our methods, we asked the experts, who are native speakers of the Tunisian dialect, to evaluate the results returned by our methods. These clusters are used to determine the subject of each tweet and/or expand the tweets by new terms. Finally, to select the set of events (EV), we relied on three criteria: frequency, variation and TF-IDF. The results that we obtained show the robustness of our system.

Le code source de la libraire développée accompagne ce dépôt dans l'état où il était à ce moment. Il est possible de trouver une version plus à jour sur github (http://github.com/abergeron). / Le calcul scientifique sur processeurs graphiques (GPU) est en plein essor depuis un certain temps, en particulier dans le domaine de l'apprentissage machine. Cette thèse présente les efforts pour établir une structure de données de table au multidimensionnel de manière efficace sur GPU. Nous commençons par faire une revue de ce qui est actuellement similaire dans le domaine et des désavantages d'avoir une multitude d'approches. Nous nous intéresserons particulièrement aux calculs fait à partir du langage Python. Nous décrirons des techniques intéressantes telles que la réduction d'ordre et le calcul asynchrone automatique. Pour terminer nous présenterons l'utilisation du module développé dans le cadre de cette thèse. / Scientific computing on GPU (graphical processing units) is on the rise, specifically in machine learning. This thesis presents the implementation of an efficient multidimensional array on the GPU. We will begin by a review of what currently implements similar functionality and the disadvantage of a fragmented approach. We will focus on packages that have a Python interface. We will explain techniques to optimize execution such as order reduction and automatic asynchronous computations. Finally, we will present the functionality of the module developed for this thesis.

clRNG et clProbdist sont deux interfaces de programmation (APIs) que nous avons développées pour la génération de nombres aléatoires uniformes et non uniformes sur des dispositifs de calculs parallèles en utilisant l’environnement OpenCL. La première interface permet de créer au niveau d’un ordinateur central (hôte) des objets de type stream considérés comme des générateurs virtuels parallèles qui peuvent être utilisés aussi bien sur l’hôte que sur les dispositifs parallèles (unités de traitement graphique, CPU multinoyaux, etc.) pour la génération de séquences de nombres aléatoires. La seconde interface permet aussi de générer au niveau de ces unités des variables aléatoires selon différentes lois de probabilité continues et discrètes. Dans ce mémoire, nous allons rappeler des notions de base sur les générateurs de nombres aléatoires, décrire les systèmes hétérogènes ainsi que les techniques de génération parallèle de nombres aléatoires. Nous présenterons aussi les différents modèles composant l’architecture de l’environnement OpenCL et détaillerons les structures des APIs développées. Nous distinguons pour clRNG les fonctions qui permettent la création des streams, les fonctions qui génèrent les variables aléatoires uniformes ainsi que celles qui manipulent les états des streams. clProbDist contient les fonctions de génération de variables aléatoires non uniformes selon la technique d’inversion ainsi que les fonctions qui permettent de retourner différentes statistiques des lois de distribution implémentées. Nous évaluerons ces interfaces de programmation avec deux simulations qui implémentent un exemple simplifié d’un modèle d’inventaire et un exemple d’une option financière. Enfin, nous fournirons les résultats d’expérimentation sur les performances des générateurs implémentés. / clRNG and clProbdist are two application programming interfaces (APIs) that we have developed respectively for the generation of uniform and non-uniform random numbers on parallel computing devices in the OpenCL environment. The first interface is used to create at a central computer level (host) objects of type stream considered as parallel virtual generators that can be used both on the host and on parallel devices (graphics processing units, multi-core CPU, etc.) for generating sequences of random numbers. The second interface can be used also on the host or devices to generate random variables according to different continuous and discrete probability distributions. In this thesis, we will recall the basic concepts of random numbers generators, describe the heterogeneous systems and the generation techniques of parallel random number, then present the different models composing the OpenCL environment. We will detail the structures of the developed APIs, distinguish in clRNG the functions that allow creating streams from the functions that generate uniform random variables and the functions that manipulate the states of the streams.We will describe also clProbDist that allow the generation of non-uniform random variables based on the inversion technique as well as returning different statistical values related to the distributions implemented. We will evaluate these APIs with two simulations, the first one implements a simplified example of inventory model and the second one estimate the value of an Asian call option. Finally, we will provide results of experimentations on the performance of the implemented generators.

Le calcul scientifique sur processeurs graphiques (GPU) est en plein essor depuis un certain temps, en particulier dans le domaine de l'apprentissage machine. Cette thèse présente les efforts pour établir une structure de données de table au multidimensionnel de manière efficace sur GPU. Nous commençons par faire une revue de ce qui est actuellement similaire dans le domaine et des désavantages d'avoir une multitude d'approches. Nous nous intéresserons particulièrement aux calculs fait à partir du langage Python. Nous décrirons des techniques intéressantes telles que la réduction d'ordre et le calcul asynchrone automatique. Pour terminer nous présenterons l'utilisation du module développé dans le cadre de cette thèse. / Scientific computing on GPU (graphical processing units) is on the rise, specifically in machine learning. This thesis presents the implementation of an efficient multidimensional array on the GPU. We will begin by a review of what currently implements similar functionality and the disadvantage of a fragmented approach. We will focus on packages that have a Python interface. We will explain techniques to optimize execution such as order reduction and automatic asynchronous computations. Finally, we will present the functionality of the module developed for this thesis. / Le code source de la libraire développée accompagne ce dépôt dans l'état où il était à ce moment. Il est possible de trouver une version plus à jour sur github (http://github.com/abergeron).

La tâche de question-réponse (Question-Answering, QA) est bien ancrée dans la communauté de Traitement Automatique du Langage Naturel (TALN) depuis de nombreuses années. De manière générale, celle-ci consiste à répondre à des questions données à l’aide de documents (textuels ou autres) ou de conversations en faisant au besoin usage de connaissances et en mettant en oeuvre des mécanismes d’inférence. Ainsi, dépendamment du jeu de données et de la tâche lui étant associée, il faut que le système puisse détecter et comprendre les éléments utiles pour répondre correctement à chacune des questions posées. De nombreux progrès ont été réalisés depuis quelques années avec des modèles neuronaux de plus en plus complexes, ces derniers sont cependant coûteux en production, et relativement opaques. Du à leur opacité, il est difficile d’anticiper avec précision le comportement de certains modèles et d’ainsi prévoir quand ces systèmes vont retourner de mauvaises réponses. Contrairement à la très grande majorité des systèmes proposés actuellement, nous allons dans ce mémoire tenter de résoudre cette tâche avec des modèles de taille contrôlable, on s’intéressera principalement aux approches basées sur les traits (features). Le but visé en restreignant la taille des modèles est qu’ils généralisent mieux. On pourra alors mesurer ce que ces modèles capturent afin d’évaluer la granularité de leur "compréhension" de la langue. Aussi, en analysant les lacunes de modèles de taille contrôlable, on pourra mettre en valeur ce que des modèles plus complexes ont capturé. Pour réaliser notre étude, on s’évalue ici sur SQuAD: un jeu de données populaire proposé par l’Université Standford. / The Question-Answering task (QA) is a well established Natural Language Processing (NLP) task. Generally speaking, it consists in answering questions using documents (textual or otherwise) or conversations, making use of knowledge if necessary and implementing inference mechanisms. Thus, depending on the data set and the task associated with it, the system must be able to detect and understand the useful elements to correctly answer each of the questions asked. A lot of progress has been made in recent years with increasingly complex neural models. They are however expensive in production, and relatively opaque. Due to this opacity, it is diÿcult to accurately predict the behavior of some models and thus, to predict when these systems will return wrong answers. Unlike the vast majority of systems currently proposed, in this thesis we will try to solve this task with models with controllable size. We will focus mainly on feature-based approaches. The goal in restricting the size of the models is that they generalize better. So we will measure what these models capture in order to assess the granularity of their "understanding" of the language. Also, by analyzing the gaps of controllable size models, we will be able to highlight what more complex models have captured. To carry out our study, we evaluate ourselves here on SQuAD: a popular data set o˙ered by Standford University.

La documentation des programmes aide les développeurs à mieux comprendre le code source pendant les tâches de maintenance. Toutefois, la documentation n’est pas toujours disponible ou elle peut être de mauvaise qualité. Le recours à la redocumentation s’avère ainsi nécessaire. Dans ce contexte, nous proposons de faire la redocumentation en générant des commentaires par application de techniques de résumé par extraction. Pour mener à bien cette tâche, nous avons commencé par faire une étude empirique pour étudier les aspects quantitatifs et qualitatifs des commentaires. En particulier, nous nous sommes intéressés à l’étude de la distribution des commentaires par rapport aux différents types d’instructions et à la fréquence de documentation de chaque type. Aussi, nous avons proposé une taxonomie de commentaires pour classer les commentaires selon leur contenu et leur qualité. Suite aux résultats de l’étude empirique, nous avons décidé de résumer les classes Java par extraction des commentaires des méthodes/constructeurs. Nous avons défini plusieurs heuristiques pour déterminer les commentaires les plus pertinents à l’extraction. Ensuite, nous avons appliqué ces heuristiques sur les classes Java de trois projets pour en générer les résumés. Enfin, nous avons comparé les résumés produits (les commentaires produits) à des résumés références (les commentaires originaux) en utilisant la métrique ROUGE. / Programs documentation is very useful to programmers during maintenance tasks, especially for program comprehension. However, the documentation is not always available or it may be badly written. In such cases, redocumentation becomes so necessary. In this work, we propose a redocumentation technique that consists in generating comments by using extraction summary techniques. For this purpose, we conducted an empirical study to analyze the quantitave and qualitative aspects of comments. Particularly, we were interested in studying comment distribution over different types of construct and studying the frequency of documentation for each construct type. We propose a comment taxonomy to classify them according to their content and quality. Given the results of the empirical study, we decided to summarize Java classes by extracting the comments of methods and constructors. We defined several heuristics in order to determine the most relevant comments to be extracted. After that, we applied these heuristics to Java classes from three projects in order to generate summaries. Finally, we compared the generated summaries (generated comments) to the reference ones (original comments) by using the metric ROUGE.

Cette thèse traite de l'usage des Réseaux de Neurones pour modélisation de données séquentielles. La façon dont l'information a été ordonnée et structurée est cruciale pour la plupart des données. Les mots qui composent ce paragraphe en constituent un exemple. D'autres données de ce type incluent les données audio, visuelles et génomiques. La Prédiction Structurée est l'un des domaines traitant de la modélisation de ces données. Nous allons aussi présenter la Modélisation Générative, qui consiste à générer des points similaires aux données sur lesquelles le modèle a été entraîné. Dans le chapitre 1, nous utiliserons des données clients afin d'expliquer les concepts et les outils de l'Apprentissage Automatique, incluant les algorithmes standards d'apprentissage ainsi que les choix de fonction de coût et de procédure d'optimisation. Nous donnerons ensuite les composantes fondamentales d'un Réseau de Neurones. Enfin, nous introduirons des concepts plus complexes tels que le partage de paramètres, les Réseaux Convolutionnels et les Réseaux Récurrents. Le reste du document, nous décrirons de plusieurs types de Réseaux de Neurones qui seront à la fois utiles pour la prédiction et la génération et leur application à des jeux de données audio, d'écriture manuelle et d'images. Le chapitre 2 présentera le Réseau Neuronal Récurrent Variationnel (VRNN pour variational recurrent neural network). Le VRNN a été développé dans le but de générer des échantillons semblables aux exemples de la base d'apprentissage. Nous présenterons des modèles entraînées de manière non-supervisée afin de générer du texte manuscrites, des effets sonores et de la parole. Non seulement ces modèles prouvent leur capacité à apprendre les caractéristiques de chaque type de données mais établissent aussi un standard en terme de performance. Dans le chapitre 3 sera présenté ReNet, un modèle récemment développé. ReNet utilise les sorties structurées d'un Réseau Neuronal Récurrent pour classifier des objets. Ce modèle atteint des performances compétitives sur plusieurs tâches de reconnaissance d'images, tout en utilisant une architecture conçue dès le départ pour de la Prédiction Structurée. Dans ce cas-ci, les résultats du modèle sont utilisés simplement pour de la classification mais des travaux suivants (non inclus ici) ont utilisé ce modèle pour de la Prédiction Structurée. Enfin, au Chapitre 4 nous présentons les résultats récents non-publiés en génération acoustique. Dans un premier temps, nous fournissons les concepts musicaux et représentations numériques fondamentaux à la compréhension de notre approche et introduisons ensuite une base de référence et de nouveaux résultats de recherche avec notre modèle, RNN-MADE. Ensuite, nous introduirons le concept de synthèse vocale brute et discuterons de notre recherche en génération. Dans notre dernier Chapitre, nous présenterons enfin un résumé des résultats et proposerons de nouvelles pistes de recherche. / In this thesis we utilize neural networks to effectively model data with sequential structure. There are many forms of data for which both the order and the structure of the information is incredibly important. The words in this paragraph are one example of this type of data. Other examples include audio, images, and genomes. The work to effectively model this type of ordered data falls within the field of structured prediction. We also present generative models, which attempt to generate data that appears similar to the data which the model was trained on. In Chapter 1, we provide an introduction to data and machine learning. First, we motivate the need for machine learning by describing an expert system built on a customer database. This leads to a discussion of common algorithms, losses, and optimization choices in machine learning. We then progress to describe the basic building blocks of neural networks. Finally, we add complexity to the models, discussing parameter sharing and convolutional and recurrent layers. In the remainder of the document, we discuss several types of neural networks which find common use in both prediction and generative modeling and present examples of their use with audio, handwriting, and images datasets. In Chapter 2, we introduce a variational recurrent neural network (VRNN). Our VRNN is developed with to generate new sequential samples that resemble the dataset that is was trained on. We present models that learned in an unsupervised manner how to generate handwriting, sound effects, and human speech setting benchmarks in performance. Chapter 3 shows a recently developed model called ReNet. In ReNet, intermediate structured outputs from recurrent neural networks are used for object classification. This model shows competitive performance on a number of image recognition tasks, while using an architecture designed to handle structured prediction. In this case, the final model output is only used for simple classification, but follow-up work has expanded to full structured prediction. Lastly, in Chapter 4 we present recent unpublished experiments in sequential audio generation. First we provide background in musical concepts and digital representation which are fundamental to understanding our approach and then introduce a baseline and new research results using our model, RNN-MADE. Next we introduce the concept of raw speech synthesis and discuss our investigation into generation. In our final chapter, we present a brief summary of results and postulate future research directions.

En simulation de fluides, il est très difficile d'obtenir des simulations contenant un haut niveau de détails efficacement dû à la complexité des phénomènes étudiés. Beaucoup de travaux se sont attaqués à ce problème afin de développer de nouvelles techniques permettant d'augmenter la résolution apparente des fluides à plus faibles coûts de calcul. Les nouvelles méthodes adaptatives ou multi-échelles ont permis de grandement améliorer la qualité visuelle des simulations de fumée et de liquides, mais certains problèmes demeurent toujours ouverts et au centre de nombreuses recherches. L'objectif de ce mémoire est d'élaborer une méthode multi-échelles afin d'augmenter la résolution apparente d'une simulation de liquide basée sur un système de particules déjà existante, un type de simulation très populaire grâce à ses propriétés de conservation d'énergie. Une telle méthode permettrait d'obtenir des simulations de résolution apparente élevée à bien moindres coûts de calcul et permettrait ainsi aux artistes d'obtenir un aperçu de leur simulation plus rapidement, tout en ayant un résultat de haute qualité. Nous présentons une méthode permettant de reconstruire une surface d'une telle simulation qui soit encline à la simulation de dynamique de surface afin d'injecter des détails de hautes fréquences occasionnés par la tension de surface. Notre méthode détecte les endroits sous-résolus de la simulation et y injecte de la turbulence grâce à de multiples oscillateurs à différentes fréquences. Les vagues à hautes fréquences injectées sont alors propagées à l'aide d'une simulation d'onde sur la surface. Notre méthode s'applique totalement en tant que post-traitement et préserve ainsi entièrement le comportement général de la simulation d'entrée tout en augmentant nettement la résolution apparente de la surface de celle-ci. / Accurately simulating the behaviour of fluids remains a difficult problem in computer graphics, and performing these simulations at a high level of detail is particularly challenging due to the complexity of the underlying dynamics of a fluid. A recent and significant body of work targets this problem by trying to augment the apparent resolution of an underlying, lower-resolution simulation, instead of performing a more costly simulation at the full-resolution. Adaptive or multi-scale methods in this area have proven successful for simulations of smoke and liquids, but no comprehensive solution exists. The goal of this thesis is to devise a new multi-scale detail-augmentation technique suitable for application atop existing particle-based fluid simulators. Particle simulations of fluid dynamics are a popular, heavily-used alternative to grid-based simulations due to their ability to better preserve energy, and no detail-augmentation techniques have been devised for this class of simulator. As such, our work would permit digital artists to perform more efficient lower-resolution particle simulations of a liquid, and then layer-on a detailed secondary simulation at a negligible cost. To do so, we present a method for reconstructing the surface of a liquid, during the particle simulation, in a manner that is amenable to high-frequency detail injection due to higher-resolution surface tension effects. Our technique detects potentially under-resolved regions on the initial simulation and synthesizes turbulent dynamics with novel multi-frequency oscillators. These dynamics result in a high-frequency wave simulation that is propagated over the (reconstructed) liquid surface. Our algorithm can be applied as a post-process, completely independent of the underlying simulation code, and so it is trivial to integrate in an existing 3D digital content creation pipeline.

Utiliser la visualization de logiciels pour accomplir certaines tâches comme la détection de défauts de design peut être fastidieux. Les utilisateurs doivent d’abord trouver et configurer un outil de visualization qui est adéquat pour représenter les données à examiner. Souvent, ils sont forcés de naviguer à travers le logiciel manuellement pour accomplir leur tâche. Nous proposons une approche plus simple et efficace. Celle ci s’éloigne de la configuration d’un outil et la navigation manuelle d’un système et se concentre sur la définition écrite de la tâche à accomplir. Suite à cela, notre assistant génère le meilleur outil de visualization et guide les utilisateurs à travers la tâche. Notre approche est constituée de trois éléments principaux, un langage dédié à la description de la tâche d’analyse. Un langage pour définir les visualizations comme des mises en oeuvre du patron modèle-vue-contrôleur. Et un processus de génération pour passer d’une tâche d’analyse à une visualization. En enlevant le besoin de configurer un outil de visualization et en guidant la navigation du système, nous pensons que nous avons fait un outil qui plus simple et rapide à utiliser que ses homologues. / Using software visualization to accomplish certain tasks such as design defect detection can prove tedious. Users first need to find and configure a visualization tool that is adequate for representing the data they want to examine. Then all too often, they are forced to manually navigate the software system in order to complete their task. What we propose is a simpler and more efficient approach that moves the emphasis from configuring a tool and manually navigating the system to writing a definition of the work we want to accomplish. Our goal-driven assistant then generates the best visualization tool and guide us through the navigation of the task. Our approach consists of three main components. The first component is a domain specific language (DSL) to describe analysis tasks. The second component is a language to define the visualizations as customized implementations of the model-view-controller (MVC) pattern. The last component is a generation process used to go from the analysis task to the visualization. By removing the need to configure a visualization tool and guiding the navigation of the system, we believe we made a tool that is simpler and faster to use than its conventional counterparts.

La théorie de l'information quantique étudie les limites fondamentales qu'imposent les lois de la physique sur les tâches de traitement de données comme la compression et la transmission de données sur un canal bruité. Cette thèse présente des techniques générales permettant de résoudre plusieurs problèmes fondamentaux de la théorie de l'information quantique dans un seul et même cadre. Le théorème central de cette thèse énonce l'existence d'un protocole permettant de transmettre des données quantiques que le receveur connaît déjà partiellement à l'aide d'une seule utilisation d'un canal quantique bruité. Ce théorème a de plus comme corollaires immédiats plusieurs théorèmes centraux de la théorie de l'information quantique. Les chapitres suivants utilisent ce théorème pour prouver l'existence de nouveaux protocoles pour deux autres types de canaux quantiques, soit les canaux de diffusion quantiques et les canaux quantiques avec information supplémentaire fournie au transmetteur. Ces protocoles traitent aussi de la transmission de données quantiques partiellement connues du receveur à l'aide d'une seule utilisation du canal, et ont comme corollaires des versions asymptotiques avec et sans intrication auxiliaire. Les versions asymptotiques avec intrication auxiliaire peuvent, dans les deux cas, être considérées comme des versions quantiques des meilleurs théorèmes de codage connus pour les versions classiques de ces problèmes. Le dernier chapitre traite d'un phénomène purement quantique appelé verrouillage: il est possible d'encoder un message classique dans un état quantique de sorte qu'en lui enlevant un sous-système de taille logarithmique par rapport à sa taille totale, on puisse s'assurer qu'aucune mesure ne puisse avoir de corrélation significative avec le message. Le message se trouve donc «verrouillé» par une clé de taille logarithmique. Cette thèse présente le premier protocole de verrouillage dont le critère de succès est que la distance trace entre la distribution jointe du message et du résultat de la mesure et le produit de leur marginales soit suffisamment petite. / Quantum information theory studies the fundamental limits that physical laws impose on information processing tasks such as data compression and data transmission on noisy channels. This thesis presents general techniques that allow one to solve many fundamental problems of quantum information theory in a unified framework. The central theorem of this thesis proves the existence of a protocol that transmits quantum data that is partially known to the receiver through a single use of an arbitrary noisy quantum channel. In addition to the intrinsic interest of this problem, this theorem has as immediate corollaries several central theorems of quantum information theory. The following chapters use this theorem to prove the existence of new protocols for two other types of quantum channels, namely quantum broadcast channels and quantum channels with side information at the transmitter. These protocols also involve sending quantum information partially known by the receiver with a single use of the channel, and have as corollaries entanglement-assisted and unassisted asymptotic coding theorems. The entanglement-assisted asymptotic versions can, in both cases, be considered as quantum versions of the best coding theorems known for the classical versions of these problems. The last chapter deals with a purely quantum phenomenon called locking. We demonstrate that it is possible to encode a classical message into a quantum state such that, by removing a subsystem of logarithmic size with respect to its total size, no measurement can have significant correlations with the message. The message is therefore "locked" by a logarithmic-size key. This thesis presents the first locking protocol for which the success criterion is that the trace distance between the joint distribution of the message and the measurement result and the product of their marginals be sufficiently small.