No description available.

Cette thèse, organisée en deux parties indépendantes, a pour objet la sémantique distributionnelle et la sélection de variables. Dans la première partie, nous introduisons une nouvelle méthode pour l'apprentissage de représentations de mots à partir de grandes quantités de texte brut. Cette méthode repose sur un modèle probabiliste de la phrase, utilisant modèle de Markov caché et arbre de dépendance. Nous présentons un algorithme efficace pour réaliser l'inférence et l'apprentissage dans un tel modèle, fondé sur l'algorithme EM en ligne et la propagation de message approchée. Nous évaluons les modèles obtenus sur des taches intrinsèques, telles que prédire des jugements de similarité humains ou catégoriser des mots et deux taches extrinsèques~: la reconnaissance d'entités nommées et l'étiquetage en supersens. Dans la seconde partie, nous introduisons, dans le contexte des modèles linéaires, une nouvelle pénalité pour la sélection de variables en présence de prédicteurs fortement corrélés. Cette pénalité, appelée trace Lasso, utilise la norm trace des prédicteurs sélectionnés, qui est une relaxation convexe de leur rang, comme critère de complexité. Le trace Lasso interpole les normes $\ell_1$ et $\ell_2$. En particulier, lorsque tous les prédicteurs sont orthogonaux, il est égal à la norme $\ell_1$, tandis que lorsque tous les prédicteurs sont égaux, il est égal à la norme $\ell_2$. Nous proposons deux algorithmes pour calculer la solution du problème de régression aux moindres carrés regularisé par le trace Lasso et réalisons des expériences sur des données synthétiques. / This thesis, which is organized in two independent parts, presents work on distributional semantics and on variable selection. In the first part, we introduce a new method for learning good word representations using large quantities of unlabeled sentences. The method is based on a probabilistic model of sentence, using a hidden Markov model and a syntactic dependency tree. The latent variables, which correspond to the nodes of the dependency tree, aim at capturing the meanings of the words. We develop an efficient algorithm to perform inference and learning in those models, based on online EM and approximate message passing. We then evaluate our models on intrinsic tasks such as predicting human similarity judgements or word categorization, and on two extrinsic tasks: named entity recognition and supersense tagging. In the second part, we introduce, in the context of linear models, a new penalty function to perform variable selection in the case of highly correlated predictors. This penalty, called the trace Lasso, uses the trace norm of the selected predictors, which is a convex surrogate of their rank, as the criterion of model complexity. The trace Lasso interpolates between the $\ell_1$-norm and $\ell_2$-norm. In particular, it is equal to the $\ell_1$-norm if all predictors are orthogonal and to the $\ell_2$-norm if all predictors are equal. We propose two algorithms to compute the solution of least-squares regression regularized by the trace Lasso, and perform experiments on synthetic datasets to illustrate the behavior of the trace Lasso.

La popularité de la grande variété de l'utilisation d'Internet entraîne une croissance significative du trafic de données dans les réseaux de télécommunications. L'efficacité de la transmission de données sera contestée en vertu du principe de la capacité actuelle du réseau et des mécanismes de contrôle de flux de données. En plus d'augmenter l'investissement financier pour étendre la capacité du réseau, améliorer les techniques existantes est plus rationnel et éconmique.Diverses recherches de pointe pour faire face aux besoins en évolution des réseaux ont vu le jour, et l'une d'elles est appelée codage de réseau. Comme une extension naturelle dans la théorie du codage, il permet le mélange de différents flux réseau sur les noeuds intermédiaires, ce qui modifie la façon d'éviter les collisions de flux de données. Il a été appliqué pour obtenir un meilleur débit, fiabilité, sécurité et robustesse dans différents environnements et applications réseau. Cette thèse porte sur l'utilisation du réseau de codage pour le multicast dans les réseaux maillés fixes et systèmes de stockage distribués. Nous avons d'abord des modèles de différentes stratégies de routage multicast dans un cadre d'optimisation, y compris de multicast à base d'arbres et de codage de réseau; nous résolvons les modèles avec des algorithmes efficaces et comparons l'avantage de codage, en termes de gain de débit de taille moyenne graphique généré aléatoirement. Basé sur l'analyse numérique obtenue à partir des expériences précédentes, nous proposons un cadre révisé de routage multicast, appelé codage de réseau stratégique, qui combine transmission muticast standard et fonctions de codage de réseau afin d'obtenir le maximum de bénéfice de codage réseau au moindre coût lorsque ces coûts dépendent à la fois sur le nombre de noeuds à exécuter un codage et le volume de trafic qui est codé. Enfin, nous étudions le problème révisé de transport qui est capable de calculer un système de routage statique entre les serveurs et les clients dans les systèmes de stockage distribués où nous appliquons le codage pour soutenir le stockage de contenu. Nous étendons l'application à un problème d'optimisation général, nommé problème de transport avec des contraintes de degré, qui peut être largement utilisé dans divers domaines industriels, y compris les télécommunications, mais n'a pas été étudié très souvent. Pour ce problème, nous obtenons quelques résultats théoriques préliminaires et nous proposons une approche de décomposition Lagrange raisonnable / The popularity of the great variety of Internet usage brings about a significant growth of the data traffic in telecommunication network. Data transmission efficiency will be challenged under the premise of current network capacity and data flow control mechanisms. In addition to increasing financial investment to expand the network capacity, improving the existing techniques are more rational and economical. Various cutting-edge researches to cope with future network requirement have emerged, and one of them is called network coding. As a natural extension in coding theory, it allows mixing different network flows on the intermediate nodes, which changes the way of avoiding collisions of data flows. It has been applied to achieve better throughput and reliability, security, and robustness in various network environments and applications. This dissertation focuses on the use of network coding for multicast in fixed mesh networks and distributed storage systems. We first model various multicast routing strategies within an optimization framework, including tree-based multicast and network coding; we solve the models with efficient algorithms, and compare the coding advantage, in terms of throughput gain in medium size randomly generated graphs. Based on the numerical analysis obtained from previous experiments, we propose a revised multicast routing framework, called strategic network coding, which combines standard multicast forwarding and network coding features in order to obtain the most benefit from network coding at lowest cost where such costs depend both on the number of nodes performing coding and the volume of traffic that is coded. Finally, we investigate a revised transportation problem which is capable of calculating a static routing scheme between servers and clients in distributed storage systems where we apply coding to support the storage of contents. We extend the application to a general optimization problem, named transportation problem with degree constraints, which can be widely used in different industrial fields, including telecommunication, but has not been studied very often. For this problem, we derive some preliminary theoretical results and propose a reasonable Lagrangian decomposition approach

L’objet de cette thèse est d’étudier plusieurs modèles probabilistes reliant les marches aléatoires et les arbres aléatoires issus de processus de branchement critiques.Dans la première partie, nous nous intéressons au modèle de marche aléatoire à valeurs dans un réseau euclidien et indexée par un arbre de Galton–Watson critique conditionné par la taille. Sous certaines hypothèses sur la loi de reproduction critique et la loi de saut centrée, nous obtenons, dans toutes les dimensions, la vitesse de croissance asymptotique du nombre de points visités par cette marche, lorsque la taille de l’arbre tend vers l’infini. Ces résultats nous permettent aussi de décrire le comportement asymptotique du nombre de points visités par une marche aléatoire branchante, quand la taille de la population initiale tend vers l’infini. Nous traitons également en parallèle certains cas où la marche aléatoire possède une dérive constante non nulle.Dans la deuxième partie, nous nous concentrons sur les propriétés fractales de la mesure harmonique des grands arbres de Galton–Watson critiques. On comprend par mesure harmonique la distribution de sortie, hors d’une boule centrée à la racine de l’arbre, d’une marche aléatoire simple sur cet arbre. Lorsque la loi de reproduction critique appartient au domaine d’attraction d’une loi stable, nous prouvons que la masse de la mesure harmonique est asymptotiquement concentrée sur une partie de la frontière, cette partie ayant une taille négligeable par rapport à celle de la frontière. En supposant que la loi de reproduction critique a une variance finie, nous arrivons à évaluer la masse de la mesure harmonique portée par un sommet de la frontière choisi uniformément au hasard. / The aim of this Ph. D. thesis is to study several probabilistic models linking the random walks and the random trees arising from critical branching processes.In the first part, we consider the model of random walk taking values in a Euclidean lattice and indexed by a critical Galton–Watson tree conditioned by the total progeny. Under some assumptions on the critical offspring distribution and the centered jump distribution, we obtain, in all dimensions, the asymptotic growth rate of the range of this random walk, when the size of the tree tends to infinity. These results also allow us to describe the asymptotic behavior of the range of a branching random walk, when the size of the initial population goes to infinity. In parallel, we treat likewise some cases where the random walk has a non-zero constant drift.In the second part, we focus on the fractal properties of the harmonic measure on large critical Galton–Watson trees. By harmonic measure, we mean the exit distribution from a ball centered at the root of the tree by simple random walk on this tree. If the critical offspring distribution is in the domain of attraction of a stable distribution, we prove that the mass of the harmonic measure is asymptotically concentrated on a boundary subset of negligible size with respect to that of the boundary. Assuming that the critical offspring distribution has a finite variance, we are able to calculate the mass of the harmonic measure carried by a random vertex uniformly chosen from the boundary.

Le travail s'inscrit dans le domaine du traitement automatique du langage naturel et traite plus spécifiquement d'une application de ce dernier au résumé automatique de textes.<br />L'originalité de la thèse consiste à s'attaquer à une variété fort peu explorée, la compression de textes, par une technique non supervisée.<br />Ce travail propose un système incrémental et interactif d'élagage de l'arbre syntagmatique des phrases, tout en préservant la cohérence syntaxique et la conservation du contenu informationnel important.<br />Sur le plan théorique, le travail s'appuie sur la théorie du gouvernement de Noam Chomsky et plus particulièrement sur la représentation formelle de la théorie X-barre pour aboutir à un fondement théorique important pour un modèle computationnel compatible avec la compression syntaxique de phrases.<br />Le travail a donné lieu a un logiciel opérationnel, nommé COLIN, qui propose deux modalités : une compression automatique, et une aide au résumé sous forme semi-automatique, dirigée par l'interaction avec l'utilisateur.<br />Le logiciel a été évalué grâce à un protocole complexe par 25 utilisateurs bénévoles.<br />Les résultats de l'expérience montrent que 1) la notion de résumé de référence qui sert aux évaluations classiques est discutable 2) les compressions semi-automatiques ont été fortement appréciées 3) les compressions totalement automatiques ont également obtenu de bons scores de satisfaction.<br />À un taux de compression supérieur à 40% tous genres confondus, COLIN fournit un support appréciable en tant qu'aide à la compression de textes, ne dépend d'aucun corpus d'apprentissage, et présente une interface convivial.

Le test est l'une des méthodes les plus utilisées pour la validation du logiciel. L'activité de test consiste à exécuter le logiciel sur un sous-ensemble de ses entrées possibles de manière à déceler d'éventuelles erreurs. La présence d'erreurs est établie par confrontation du comportement du logiciel avec un objet de référence. Le processus de test est généralement décomposé en trois phases : la sélection du sous-ensemble des entrées sur lequel le logiciel sera exécuté, la soumission de ces entrées au logiciel en collectant les sorties (les réponses du logiciel) et la décision de l'adéquation de ces sorties avec les sorties attendues.<br /><br />La sélection des données à soumettre au logiciel peut être effectuée selon différentes approches. Lorsque la phase de sélection d'un jeu de tests est opérée à partir d'un objet de référence décrivant plus ou moins formellement le comportement du logiciel, sans connaissance de l'implantation elle-même, on parle de test « boîte noire ». Une des approches de test boîte noire pour laquelle un cadre formel a été proposé est celle qui utilise comme objet de référence une spécification logique du système sous test.<br /><br />Le cadre général de test à partir de spécifications logiques (ou axiomatiques) pose les conditions et les hypothèses sous lesquelles il est possible de tester un système. La première hypothèse consiste à considérer le système sous test comme un modèle formel implantant les opérations dont le comportement est décrit par la spécification. La seconde hypothèse a trait à l'observabilité du système sous test. Il faut fixer la forme des formules qui peuvent être interprétées par le système, c'est-à-dire qui peuvent être des tests. On se restreint généralement au moins aux formules qui ne contiennent pas de variables. Une fois ces hypothèses de test posées, on dispose d'un jeu de tests initial, celui de toutes les formules observables qui sont des conséquences logiques de la spécification. <br /><br />Le premier résultat à établir est l'exhaustivité de cet ensemble, c'est-à-dire sa capacité à prouver la correction du système s'il pouvait être soumis dans son intégralité. Le jeu de tests exhaustif étant le plus souvent infini, une phase de sélection intervient afin de choisir un jeu de tests de taille finie et raisonnable à soumettre au système. Plusieurs approches sont possibles. L'approche suivie dans ma thèse, dite par partition, consiste a diviser le jeu de tests exhaustif initial en sous-jeux de tests, selon un certain critère de sélection relatif à une fonctionnalité ou à une caractéristique du système que l'on veut tester. Une fois cette partition suffisamment fine, il suffit de choisir un cas de test dans chaque sous-jeu de test obtenu en appliquant l'hypothèse d'uniformité (tous les cas de test d'un jeu de test sont équivalents pour faire échouer le système). Le deuxième résultat à établir est que la division du jeu de tests initial n'ajoute pas (correction de la procédure) et ne fait pas perdre (complétude) de cas de test.<br /><br />Dans le cadre des spécifications algébriques, une des méthodes de partition du jeu de tests exhaustif qui a été très étudiée, appelée dépliage des axiomes, consiste à procéder à une analyse par cas de la spécification. Jusqu'à présent, cette méthode s'appuyait sur des spécifications équationnelles dont les axiomes avaient la caractéristique d'être conditionnels positifs (une conjonction d'équations implique une équation).<br /><br />Le travail de ma thèse a eu pour but d'étendre et d'adapter ce cadre de sélection de tests à des systèmes dynamiques spécifiés dans un formalisme axiomatique, la logique modale du premier ordre. La première étape a consisté à généraliser la méthode de sélection définie pour des spécifications équationnelles conditionnelles positives aux spécifications du premier ordre. Ce cadre de test a ensuite été d'adapté à des spécifications modales du premier ordre. Le premier formalisme de spécification considéré est une extension modale de la logique conditionnelle positive pour laquelle le cadre de test a été initialement défini. Une fois le cadre de test adapté aux spécifications modales conditionnelles positives, la généralisation aux spécifications modales du premier ordre a pu être effectuée. <br /><br />Dans chacun de ces formalismes nous avons effectué deux tâches. Nous avons d'une part étudié les conditions nécessaires à imposer à la spécification et au système sous test pour obtenir l'exhaustivité du jeu de tests initial. Nous avons d'autre part adapté et étendu la procédure de sélection par dépliage des axiomes à ces formalismes et montré sa correction et sa complétude. Dans les deux cadres généraux des spécifications du premier ordre et des spécifications modales du premier ordre, nous avons montré que les conditions nécessaires à l'exhausitivité du jeu de test visé étaient mineures car faciles à assurer dans la pratique, ce qui assure une généralisation satisfaisante de la sélection dans ce cadre.

Dans cette thèse, nous étudions l'enveloppe convexe des arbres binaires à racine sur n feuilles.Ce sont les arbres de Huffman dont les feuilles sont labellisées par n caractères. à chaque arbre de Huffman T de n feuilles, nous associons un point xT , appelé point de Huffman, dans l'espace Qn où xT est le nombre d'arêtes du chemin reliant la feuille du ième caractère et la racine.L'enveloppe convexe des points de Huffman est appelé Huffmanoèdre. Les points extrêmes de ce polyèdre sont obtenus dans un premier temps en utilisant l'algorithme d'optimisation qui est l'algorithme de Huffman. Ensuite, nous décrivons des constructions de voisinages pour un point de Huffman donné. En particulier, une de ces constructions est principalement basée sur la construction des sommets adjacents du Permutoèdre. Puis, nous présentons une description partielle du Huffmanoèdre contenant en particulier une famille d'inégalités définissant des facettes dont les coefficients, une fois triés, forment une suite de Fibonacci. Cette description bien que partielle nous permet d'une part d'expliquer la plupart d'inégalités définissant des facettes du Huffmanoèdre jusqu'à la dimension 8, d'autre part de caractériser les arbres de Huffman les plus profonds, i.e. une caractérisation de tous les facettes ayant au moins un plus profond arbre de Huffman comme point extrême. La contribution principale de ce travail repose essentiellement sur les liens que nous établissons entre la construction des arbres et la génération des facettes / In this thesis, we study the convex hull of full binary trees of n leaves. There are the Huffman trees, the leaves of which are labeled by n characters. To each Huffman tree T of n leaves, we associate a point xT , called Huffman point, in the space Qn where xT i is the lengths of the path from the root node to the leaf node marked by the ith character. The convex hull of the Huffman points is called Huffmanhedron. The extreme points of the Huffmanhedron are first obtained by using the optimization algorithm which is the Huffman algorithm. Then, we describe neighbour constructions given a Huffman point x. In particular, one of these constructions is mainly based on the neighbour construction of the Permutahedron. Thereafter, we present a partial description of the Huffmanhedron particularly containing a family of inequalities-defining facets whose coeficients follows in some way the law of the well-known Fibonacci sequence. This description allows us, on the one hand, to explain the most of inequalities-defining facets of the Huffmanhedron up to the dimension 8, on the other hand, to characterize the Huffman deepest trees, i.e a linear characterization of all the facets containing at least a Huffman deepest tree as its extreme point. The main contribution of this work is essentially base on the link what we establish between the Huffman tree construction and the facet generation.

L'objectif de cette thèse est d'étudier le problème de la modélisation des changements de régime dans les modèles a corrélations conditionnelles dynamiques en nous intéressant plus particulièrement a l'approche Markov-switching. A la différence de l'approche standard basée sur le modèle à chaîne de Markov caché (HMM) de base, nous utilisons des extensions du modèle HMM provenant des modèles graphiques probabilistes. Cette discipline a en effet proposé de nombreuses dérivations du modèle de base permettant de modéliser des structures complexes. Cette thèse se situe donc a l'interface de deux disciplines: l'économétrie financière et les modèles graphiques probabilistes.Le premier essai présente un modèle construit a partir d'une structure hiérarchique cachée markovienne qui permet de définir différents niveaux de granularité pour les régimes. Il peut être vu comme un cas particulier du modèle RSDC (Regime Switching for Dynamic Correlations). Basé sur le HMM hiérarchique, notre modèle permet de capter des nuances de régimes qui sont ignorées par l'approche Markov-Switching classique.La seconde contribution propose une version Markov-switching du modèle DCC construite a partir du modèle HMM factorise. Alors que l'approche Markov-switching classique suppose que les tous les éléments de la matrice de corrélation suivent la même dynamique, notre modèle permet à tous les éléments de la matrice de corrélation d'avoir leur propre dynamique de saut. Markov-switching. A la différence de l'approche standard basée sur le modèle à chaîne de Markov caché (HMM) de base, nous utilisons des extensions du modèle HMM provenant des modèles graphiques probabilistes. Cette discipline a en effet propose de nombreuses dérivations du modèle de base permettant de modéliser des structures complexes. Cette thèse se situe donc a l'interface de deux disciplines: l'économétrie financière et les modèles graphiques probabilistes.Le premier essai présente un modèle construit a partir d'une structure hiérarchique cachée markovienne qui permet de définir différents niveaux de granularité pour les régimes. Il peut ^etre vu commeun cas particulier du modele RSDC (Regime Switching for Dynamic Correlations). Base sur le HMMhierarchique, notre modele permet de capter des nuances de regimes qui sont ignorees par l'approcheMarkov-Switching classique.La seconde contribution propose une version Markov-switching du modele DCC construite a partir dumodele HMM factorise. Alors que l'approche Markov-switching classique suppose que les tous les elementsde la matrice de correlation suivent la m^eme dynamique, notre modele permet a tous les elements de lamatrice de correlation d'avoir leur propre dynamique de saut.Dans la derniere contribution, nous proposons un modele DCC construit a partir d'un arbre dedecision. L'objectif de cet arbre est de relier le niveau des volatilites individuelles avec le niveau descorrelations. Pour cela, nous utilisons un arbre de decision Markovien cache, qui est une extension de HMM. / The objective of this thesis is to study the modelling of change in regime in the dynamic conditional correlation models. We focus particularly on the Markov-switching approach. Unlike the standard approach based on the Hidden Markov Model (HMM), we use extensions of HMM coming from probabilistic graphical models theory. This discipline has in fact proposed many derivations of the basic model to model complex structures. Thus, this thesis can be view at the interface of twodisciplines: financial econometrics and probabilistic graphical models.The first essay presents a model constructed from a hierarchical hidden Markov which allows to increase the granularity of the regimes. It can be seen as a special case of RSDC model (Regime Switching for Dynamic Correlations). Based on the hierarchical HMM, our model can capture nuances of regimes that are ignored by the classical Markov-Switching approach.The second contribution proposes a Markov-switching version of the DCC model that is built from the factorial HMM. While the classical Markov-switching approach assumes that all elements of the correlation matrix follow the same switching dynamic, our model allows all elements of the correlation matrix to have their own switching dynamic.In the final contribution, we propose a model DCC constructed based on a decision tree. The objective of this tree is to link the level of volatility with the level of individual correlations. For this, we use a hidden Markov decision tree, which is an extension of HMM.

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.