Ce mémoire concerne la reconnaissance automatique des Actes de Dialogues (ADs) en tchéque et en français. Les ADs sont des unités au niveau de la phrase qui représentent des différents états d’un dialogue, comme par exemple les questions, les affirmations, les hésitations, etc. La première contribution de ce travail est de proposer et comparer plusieurs approches de reconnaissance des ADs qui sont basées sur trois types d’informations : lexical, prosodique et relative à la position des mots dans une phrase. Ces approches ont eté testées sur un corpus tchèque de dialogues homme-homme. Ce corpus a été transcris en mots manuellement, et avec un moteur de reconnaissance automatique afin de valider les approches dans des conditions réelles. Les résultats expérimentaux confirment que chaque type d’attributs apporte des informations pertinentes et complémentaires. Les méthodes proposées qui exploitent la position des mots sont particulièrement intéresantes, parce qu’elles utilisent une information globale sur la structure de la phrase. Une autre contribution conséquente, relative au manque de corpus étiquettés dans le domaine de la reconnaissance automatique des ADs, concerne le développement et l’étude de méthodes d’étiquetage semi-automatique de nouveaux corpus. Cette méthode est basée sur l’algorithme d’Espérance-Maximisation avec des ADs prédéfinis spécifiques à la tâche visée. Nous proposons deux mesures de confiance pour sélectionner les exemples qui ont le plus de chance d’être classifiés correctement. Les résultats expérimentaux démontrent que la méthode proposée est une approche intéressante pour la création de nouveaux corpus d’actes de dialogues à moindre coût. / This thesis deals with automatic Dialogue Act (DA) recognition in Czech and in French. Dialogue acts are sentence-level labels that represent different states of a dialogue, such as questions, statements, hesitations, etc. The first main contribution of this work is to propose and compare several approaches that recognize dialogue acts based on three types of information: lexical, prosodic and word positions. These approaches are tested on the Czech Railways corpus that contains human-human dialogues, which are transcribed both manually and with an automatic speech recognizer for comparison. The experimental results confirmed that every type of feature (lexical, prosodic and word positions) bring relevant and somewhat complementary information. The proposed methods that take into account word positions are especially interesting, as they bring global information about the structure of a sentence, at the opposite of traditional n-gram models that only capture local cues. One of the main issue in the domain of automatic dialogue act recognition concerns the design of a fast and cheap method to label new corpora. The next main contribution is to apply the general semi-supervised training approach based on the Expectation Maximization algorithm to the task of labeling a new corpus with the pre-defined DAs. We further proposed to filter out the examples that might be incorrect by two confidence measures, namely the maximum a posteriori probability and the a posteriori probability difference methods. Experimental results showed that the proposed method is an efficient approach to create new dialogue act corpora at low costs.

L’utilisation inappropriée des antimicrobiens est un problème de taille qui touche jusqu’à 50% des prescriptions chez les patients hospitalisés. Or, la surveillance de l’usage des antimicrobiens à l’échelle d’un hôpital s’avère impossible à effectuer manuellement et requiert l’utilisation d’un système d’aide à la décision. Le système d’aide à la décision APSS - Antimicrobial Prescription Surveillance System - a été développé pour assister le professionnel de la santé dans l’identification des prescriptions inappropriées d’antimicrobiens. Son utilisation a été associée à une amélioration des pratiques de prescription d’antimicrobiens. Cependant, le processus d’acquisition et modélisation de sa connaissance a été long et ardu. Pour pallier cette difficulté, cette thèse présente un module d’apprentissage automatique développé pour permettre à un système comme APSS de découvrir de nouvelles règles de classification de prescriptions à partir des rétroactions de ses utilisateurs. Ce module utilise l’algorithme TIM - Temporal Induction of Classification Models - pour découvrir des règles temporelles de classification pour catégoriser des séquences d’épisodes comme approprié ou inapproprié. Des résultats d’évaluation démontrent la capacité du module à découvrir des règles cliniquement pertinentes pour plusieurs catégories d’alertes de prescriptions inappropriées. Les règles apprises ont mené à des interventions qui ont été manquées par le système de base. Ces règles ont permis d’étendre la connaissance du système de base en identifiant des pratiques de prescription non appuyées par les experts qui n’étaient pas incluses dans sa base de connaissances. Par contre, la combinaison des règles apprises aux règles du système de base a entraîné une augmentation des faux positifs.

Cette thèse se place dans le cadre de l'apprentissage non supervisé, qui consiste à former différents groupes à partir d'un ensemble de données, de telle manière que les données considérées comme les plus similaires soient associées au même groupe et qu'au contraire les données considérées comme différentes se retrouvent dans des groupes distincts, permettant ainsi d'extraire de la connaissance à partir de ces données. Nous proposons d'abord deux nouvelles méthodes qui prennent en compte le contexte dans lequel les groupes sont créés, c'est-à-dire le fait que les caractéristiques des différents groupes peuvent être définies sur différents sous-ensembles des attributs décrivant les données. Dans la mise en oeuvre de ces méthodes, nous avons également considéré les problématiques de la minimisation du nombre de connaissances a priori requises de la part de l'utilisateur et de la présentation des résultats sous forme compréhensible et visuelle. Nous présentons ensuite plusieurs extensions possibles de ces méthodes, dans le cadre de l'apprentissage supervisé puis face à des données semi-structurées représentées sous forme arborescente. Différentes expérimentations sur données artificielles puis sur données réelles sont présentées qui mettent en avant l'intérêt de ces méthodes. Le problème de l'évaluation des résultats produits par une méthode d'apprentissage non supervisé, et de la comparaison de telles méthodes, restant aujourd'hui un problème ouvert, nous proposons enfin une nouvelle méthode d'évaluation plus objective et quantitative que celles utilisées traditionnellement, et dont la pertinence est montrée expérimentalement.

Dans la plupart des systèmes biométriques de l’état de l’art, les données biométrique sont souvent représentés par des vecteurs de grande dimensionalité. La dimensionnalité d'éléments biométriques génèrent un problème de malédiction de dimensionnalité. Dans la biométrie multimodale, différentes modalités biométriques peuvent former différents entrés des algorithmes de classification. La fusion des modalités reste un problème difficile et est généralement traitée de manière isolée à celui de dimensionalité élevée. Cette thèse aborde le problème de la dimensionnalité élevée et le problème de la fusion multimodale dans un cadre unifié. En vertu d'un paramètre biométrique multi-modale et les données non étiquetées abondantes données, nous cherchons à extraire des caractéristiques discriminatoires de multiples modalités d'une manière non supervisée. Les contributions de cette thèse sont les suivantes: Un état de l’art des algorithmes RMVD de l'état de l'art ; Un nouveau concept de RMVD: accord de la structure de données dans sous-espace; Trois nouveaux algorithmes de MVDR basée sur des définitions différentes de l’accord de la structure dans les sous-espace; L’application des algorithmes proposés à la classification semi-supervisée, la classification non supervisée, et les problèmes de récupération de données biométriques, en particulier dans un contexte de la reconnaissance de personne en audio et vidéo; L’application des algorithmes proposés à des problèmes plus larges de reconnaissance des formes pour les données non biométriques, tels que l'image et le regroupement de texte et la recherche. / Biometric data is often represented by high-dimensional feature vectors which contain significant inter-session variation. Discriminative dimensionality reduction techniques generally follow a supervised learning scheme. However, labelled training data is generally limited in quantity and often does not reliably represent the inter-session variation encountered in test data. This thesis proposes to use multi-view dimensionality reduction (MVDR) which aims to extract discriminative features in multi-modal biometric systems, where different modalities are regarded as different views of the same data. MVDR projections are trained on feature-feature pairs where label information is not required. Since unlabelled data is easier to acquire in large quantities, and because of the natural co-existence of multiple views in multi-modal biometric problems, discriminant, low-dimensional subspaces can be learnt using the proposed MVDR approaches in a largely unsupervised manner. According to different functionalities of biometric systems, namely, clustering, and retrieval, we propose three MVDR frameworks which meet the requirements for each functionality. The proposed approaches, however, share the same spirit: all methods aim to learn a projection for each view such that a certain form of agreement is attained in the subspaces across different views. The proposed MVDR frameworks can thus be unified into one general framework for multi-view dimensionality reduction through subspace agreement. We regard this novel concept of subspace agreement to be the primary contribution of this thesis.

La détection d'anomalies est une tâche critique de l'administration des réseaux. L'apparition continue de nouvelles anomalies et la nature changeante du trafic réseau compliquent de fait la détection d'anomalies. Les méthodes existantes de détection d'anomalies s'appuient sur une connaissance préalable du trafic : soit via des signatures créées à partir d'anomalies connues, soit via un profil de normalité. Ces deux approches sont limitées : la première ne peut détecter les nouvelles anomalies et la seconde requiert une constante mise à jour de son profil de normalité. Ces deux aspects limitent de façon importante l'efficacité des méthodes de détection existantes.Nous présentons une approche non-supervisée qui permet de détecter et caractériser les anomalies réseaux de façon autonome. Notre approche utilise des techniques de partitionnement afin d'identifier les flux anormaux. Nous proposons également plusieurs techniques qui permettent de traiter les anomalies extraites pour faciliter la tâche des opérateurs. Nous évaluons les performances de notre système sur des traces de trafic réel issues de la base de trace MAWI. Les résultats obtenus mettent en évidence la possibilité de mettre en place des systèmes de détection d'anomalies autonomes et fonctionnant sans connaissance préalable / Anomaly detection has become a vital component of any network in today’s Internet. Ranging from non-malicious unexpected events such as flash-crowds and failures, to network attacks such as denials-of-service and network scans, network traffic anomalies can have serious detrimental effects on the performance and integrity of the network. The continuous arising of new anomalies and attacks create a continuous challenge to cope with events that put the network integrity at risk. Moreover, the inner polymorphic nature of traffic caused, among other things, by a highly changing protocol landscape, complicates anomaly detection system's task. In fact, most network anomaly detection systems proposed so far employ knowledge-dependent techniques, using either misuse detection signature-based detection methods or anomaly detection relying on supervised-learning techniques. However, both approaches present major limitations: the former fails to detect and characterize unknown anomalies (letting the network unprotected for long periods) and the latter requires training over labeled normal traffic, which is a difficult and expensive stage that need to be updated on a regular basis to follow network traffic evolution. Such limitations impose a serious bottleneck to the previously presented problem.We introduce an unsupervised approach to detect and characterize network anomalies, without relying on signatures, statistical training, or labeled traffic, which represents a significant step towards the autonomy of networks. Unsupervised detection is accomplished by means of robust data-clustering techniques, combining Sub-Space clustering with Evidence Accumulation or Inter-Clustering Results Association, to blindly identify anomalies in traffic flows. Correlating the results of several unsupervised detections is also performed to improve detection robustness. The correlation results are further used along other anomaly characteristics to build an anomaly hierarchy in terms of dangerousness. Characterization is then achieved by building efficient filtering rules to describe a detected anomaly. The detection and characterization performances and sensitivities to parameters are evaluated over a substantial subset of the MAWI repository which contains real network traffic traces.Our work shows that unsupervised learning techniques allow anomaly detection systems to isolate anomalous traffic without any previous knowledge. We think that this contribution constitutes a great step towards autonomous network anomaly detection.This PhD thesis has been funded through the ECODE project by the European Commission under the Framework Programme 7. The goal of this project is to develop, implement, and validate experimentally a cognitive routing system that meet the challenges experienced by the Internet in terms of manageability and security, availability and accountability, as well as routing system scalability and quality. The concerned use case inside the ECODE project is network anomaly

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

La popularité des médias sociaux en ligne (Online Social Media - OSM) est fortement liée à la qualité du contenu généré par l'utilisateur (User Generated Content - UGC) et la protection de la vie privée des utilisateurs. En se basant sur la définition de la qualité de l'information, comme son aptitude à être exploitée, la facilité d'utilisation des OSM soulève de nombreux problèmes en termes de la qualité de l'information ce qui impacte les performances des applications exploitant ces OSM. Ces problèmes sont causés par des individus mal intentionnés (nommés spammeurs) qui utilisent les OSM pour disséminer des fausses informations et/ou des informations indésirables telles que les contenus commerciaux illégaux. La propagation et la diffusion de telle information, dit spam, entraînent d'énormes problèmes affectant la qualité de services proposés par les OSM. La majorité des OSM (comme Facebook, Twitter, etc.) sont quotidiennement attaquées par un énorme nombre d'utilisateurs mal intentionnés. Cependant, les techniques de filtrage adoptées par les OSM se sont avérées inefficaces dans le traitement de ce type d'information bruitée, nécessitant plusieurs semaines ou voir plusieurs mois pour filtrer l'information spam. En effet, plusieurs défis doivent être surmontées pour réaliser une méthode de filtrage de l'information bruitée . Les défis majeurs sous-jacents à cette problématique peuvent être résumés par : (i) données de masse ; (ii) vie privée et sécurité ; (iii) hétérogénéité des structures dans les réseaux sociaux ; (iv) diversité des formats du UGC ; (v) subjectivité et objectivité. Notre travail s'inscrit dans le cadre de l'amélioration de la qualité des contenus en termes de messages partagés (contenu spam) et de profils des utilisateurs (spammeurs) sur les OSM en abordant en détail les défis susmentionnés. Comme le spam social est le problème le plus récurant qui apparaît sur les OSM, nous proposons deux approches génériques pour détecter et filtrer le contenu spam : i) La première approche consiste à détecter le contenu spam (par exemple, les tweets spam) dans un flux en temps réel. ii) La seconde approche est dédiée au traitement d'un grand volume des données relatives aux profils utilisateurs des spammeurs (par exemple, les comptes Twitter). / The popularity of OSM is mainly conditioned by the integrity and the quality of UGC as well as the protection of users' privacy. Based on the definition of information quality as fitness for use, the high usability and accessibility of OSM have exposed many information quality (IQ) problems which consequently decrease the performance of OSM dependent applications. Such problems are caused by ill-intentioned individuals who misuse OSM services to spread different kinds of noisy information, including fake information, illegal commercial content, drug sales, mal- ware downloads, and phishing links. The propagation and spreading of noisy information cause enormous drawbacks related to resources consumptions, decreasing quality of service of OSM-based applications, and spending human efforts. The majority of popular social networks (e.g., Facebook, Twitter, etc) over the Web 2.0 is daily attacked by an enormous number of ill-intentioned users. However, those popular social networks are ineffective in handling the noisy information, requiring several weeks or months to detect them. Moreover, different challenges stand in front of building a complete OSM-based noisy information filtering methods that can overcome the shortcomings of OSM information filters. These challenges are summarized in: (i) big data; (ii) privacy and security; (iii) structure heterogeneity; (iv) UGC format diversity; (v) subjectivity and objectivity; (vi) and service limitations In this thesis, we focus on increasing the quality of social UGC that are published and publicly accessible in forms of posts and profiles over OSNs through addressing in-depth the stated serious challenges. As the social spam is the most common IQ problem appearing over the OSM, we introduce a design of two generic approaches for detecting and filtering out the spam content. The first approach is for detecting the spam posts (e.g., spam tweets) in a real-time stream, while the other approach is dedicated for handling a big data collection of social profiles (e.g., Twitter accounts).

De nombreuses initiatives ont été mises en places pour caractériser d'un point de vue moléculaire de grandes cohortes de cancers à partir de diverses sources biologiques dans l'espoir de comprendre les altérations majeures impliquées durant la tumorogénèse. Les données mesurées incluent l'expression des gènes, les mutations et variations de copy-number, ainsi que des signaux épigénétiques tel que la méthylation de l'ADN. De grands consortium tels que “The Cancer Genome Atlas” (TCGA) ont déjà permis de rassembler plusieurs milliers d'échantillons cancéreux mis à la disposition du public. Nous contribuons dans cette thèse à analyser d'un point de vue mathématique les relations existant entre les différentes sources biologiques, valider et/ou généraliser des phénomènes biologiques à grande échelle par une analyse intégrative de données épigénétiques et génétiques.En effet, nous avons montré dans un premier temps que la méthylation de l'ADN était un marqueur substitutif intéressant pour jauger du caractère clonal entre deux cellules et permettait ainsi de mettre en place un outil clinique des récurrences de cancer du sein plus précis et plus stable que les outils actuels, afin de permettre une meilleure prise en charge des patients.D'autre part, nous avons dans un second temps permis de quantifier d'un point de vue statistique l'impact de la méthylation sur la transcription. Nous montrons l'importance d'incorporer des hypothèses biologiques afin de pallier au faible nombre d'échantillons par rapport aux nombre de variables.Enfin, nous montrons l'existence d'un phénomène biologique lié à l'apparition d'un phénotype d'hyperméthylation dans plusieurs cancers. Pour cela, nous adaptons des méthodes de régression en utilisant la similarité entre les différentes tâches de prédictions afin d'obtenir des signatures génétiques communes prédictives du phénotypes plus précises.En conclusion, nous montrons l'importance d'une collaboration biologique et statistique afin d'établir des méthodes adaptées aux problématiques actuelles en bioinformatique. / Several initiatives have been launched recently to investigate the molecular characterisation of large cohorts of human cancers with various high-throughput technologies in order to understanding the major biological alterations related to tumorogenesis. The information measured include gene expression, mutations, copy-number variations, as well as epigenetic signals such as DNA methylation. Large consortiums such as “The Cancer Genome Atlas” (TCGA) have already gathered publicly thousands of cancerous and non-cancerous samples. We contribute in this thesis in the statistical analysis of the relationship between the different biological sources, the validation and/or large scale generalisation of biological phenomenon using an integrative analysis of genetic and epigenetic data.Firstly, we show the role of DNA methylation as a surrogate biomarker of clonality between cells which would allow for a powerful clinical tool for to elaborate appropriate treatments for specific patients with breast cancer relapses.In addition, we developed systematic statistical analyses to assess the significance of DNA methylation variations on gene expression regulation. We highlight the importance of adding prior knowledge to tackle the small number of samples in comparison with the number of variables. In return, we show the potential of bioinformatics to infer new interesting biological hypotheses.Finally, we tackle the existence of the universal biological phenomenon related to the hypermethylator phenotype. Here, we adapt regression techniques using the similarity between the different prediction tasks to obtain robust genetic predictive signatures common to all cancers and that allow for a better prediction accuracy.In conclusion, we highlight the importance of a biological and computational collaboration in order to establish appropriate methods to the current issues in bioinformatics that will in turn provide new biological insights.

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

De nombreuses applications informatiques nécessitent l’utilisation de distances. Dans le cadre de données structurées, chaînes ou arbres, nous utilisons majoritairement la distance d’édition. Celle-ci correspond au nombre minimal d’opérations d’édition (insertion, délétion et substitution) nécessaire pour transformer la première donnée en la seconde. Suivant l’application traitée, il est possible de paramétrer la distance d’édition en associant à chaque opération d’édition un poids. Dans le cadre de ce manuscrit, nous proposons une technique d’apprentissage automatique supervisée pour apprendre les poids de la distance décrite précédemment. L’algorithme utilisé, appelé Expectation-Maximisation, maximise la vraisemblance des paramètres du modèle à l’aide d’un échantillon d’apprentissage composé de paires d’exemples considérés comme similaires. La première contribution de ce manuscrit est une extension de précédents travaux sur les chaînes aux arbres sous la forme de transducteur à un unique état. Nous montrons sur une tâche de reconnaissance de caractères manuscrits, l’efficacité de l’apprentissage par rapport à l’utilisation de poids non appris. La seconde est une approche sur les chaînes sous contraintes. Le modèle est représenté par un ensemble fini d’états dans lequel les transitions sont contraintes. Une contrainte est représentée par un ensemble fini de fonctions booléennes définies sur la chaîne d’entrée et une de ses positions. Nous utilisons notre modèle pour aborder une application de recherche de sites de facteur de transcription dans des séquences génomiques / In computer science, a lot of applications use distances. In the context of structured data, strings or trees, we mainly use the edit distance. The edit distance is defined as the minimum number of edit operation (insertion, deletion and substitution) needed to transform one data into the other one. Given the application, it is possible to tune the edit distance by adding a weight to each edit operation. In this work, we use a supervised machine learning approach to learn the weight of edit operation. The exploited algorithm, called Expectation-Maximisation, is a method for finding maximum likelihood estimates of parameters in a model given a learning sample of pairs of similar examples. The first contribution is an extension of earlier works on string to trees. The model is represent by a transducer with a single state. We apply successfully our method on a handwritten character recognition task. In a last part, we introduce a new model on strings under constraints. The model is made of a finite set of states where the transitions are constrained. A constraint is a finite set of boolean functions defined over an input string and one of its position. We show the relevance of our approach on a molecular biology task. We consider the problem of detecting Transcription Factor Binding Site in DNA sequences