NCube/papyrus huggingface dataset:
Étude combinatoire et algorithmique de la médiane de permutations sous la distance de Kendall-Tau

Une permutation peut être vue comme un classement qui ordonne des éléments ou des candidats en fonction d’une préférence ou d’un critère. Ce classement peut être le vote d’un électeur qui doit classer tous les candidats en ordre de préférence, le résultat d’une compétition sportive avec plusieurs athlètes ou encore une liste des meilleurs films de 2018. Cependant, il se peut, dans les exemples ci-dessus, que les électeurs n’aient pas les mêmes préférences ou encore qu’une compétition sportive soit divisée en plusieurs épreuves dont les classements diffèrent les uns des autres. C’est pourquoi il existe des règles pour générer une permutation "consensus", c’est-à-dire qui est le meilleur compromis entre les différents classements. L’un de ces consensus est la médiane de permutation, appelée aussi consensus de Kemeny. Cette dernière méthode respecte un ensemble de propriétés qui justifient son utilisation. Le calcul du consensus de Kemeny est toutefois un problème NP-difficile. Conséquemment, de nombreux travaux de recherche ont été effectués sur le sujet. Ce mémoire étudie principalement des classes spéciales du problème, c’est-à-dire le calcul du consensus de Kemeny d’un ensemble de permutations présentant des caractéristiques spécifiques. A permutation can be seen as a ranking which orders elements or candidates by a criteria or a preference. This ranking can be an elector’s vote to rank candidates in order of preference, athletes in a sports competition or a list of the best movies of 2018. However, in these examples, the electors may not all have the same preferences and the athletes might be judged on more than one challenge in which rankings differ. This is why "consensus" rules of permutation exist as the best compromise for the different rankings. One of these consensus is the median permutation, or the Kemeny consensus. This method respects some properties which justify its use, but is NP-hard to compute. Consequently, numerous researchers have devoted time to study this problem. This master’s thesis aims to study the calculation of the Kemeny consensus in special cases of the problem, which are set of permutations with specific characteristics.

Keyphrases: Méthode de Kemeny, Médiane de permutations, Règle de Kemeny, Consensus de Kemeny, Permutations, Kemeny Rule, Distance de Kendall-τ, Permutations, Kemeny method, Median of permutations, Kendall-τ distance, Kemeny consensus
Improved training of energy-based models

L'estimation du maximum de vraisemblance des modèles basés sur l'énergie est un problème difficile à résoudre en raison de l'insolubilité du gradient du logarithmique de la vraisemblance. Dans ce travail, nous proposons d'apprendre à la fois la fonction d'énergie et un mécanisme d'échantillonnage approximatif amorti à l'aide d'un réseau de générateurs neuronaux, qui fournit une approximation efficace du gradient de la log-vraisemblance. L'objectif qui en résulte exige la maximisation de l'entropie des échantillons générés, que nous réalisons en utilisant des estimateurs d'information mutuelle non paramétriques récemment proposés. Enfin, pour stabiliser le jeu antagoniste qui en résulte, nous utilisons une pénalité du gradient, centrée en zéro, dérivée comme condition nécessaire issue de la littérature sur l'alignement des scores. La technique proposée peut générer des images nettes avec des scores d'Inception et de FID compétitifs par rapport aux techniques récentes de GAN, ne souffrant pas d'effondrement de mode, et compétitive par rapport aux techniques de détection d'anomalies les plus récentes.   Le chapitre 1 introduit les concepts essentiels à la compréhension des travaux présentés dans cette thèse, tels que les modèles graphiques fondés sur l'énergie, les méthodes de Monte-Carlo par chaînes de Markov, les réseaux antagonistes génératifs et l'estimation de l'information mutuelle. Le chapitre 2 contient un article détaillant notre travail sur l'amélioration de l'entraînement des fonctions d'énergie. Enfin, le chapitre 3 présente quelques conclusions tirées de ce travail de thèse, la portée des travaux futurs, ainsi que des questions ouvertes qui restent sans réponse. Maximum likelihood estimation of energy-based models is a challenging problem due to the intractability of the log-likelihood gradient. In this work, we propose learning both the energy function and an amortized approximate sampling mechanism using a neural generator network, which provides an efficient approximation of the log-likelihood gradient. The resulting objective requires maximizing entropy of the generated samples, which we perform using recently proposed nonparametric mutual information estimators. Finally, to stabilize the resulting adversarial game, we use a zero-centered gradient penalty derived as a necessary condition from the score matching literature. The proposed technique can generate sharp images with Inception and FID scores competitive with recent GAN techniques, does not suffer from mode collapse, and is competitive with state-of-the-art anomaly detection techniques.

Keyphrases: apprentissage profond, apprentissage non supervisé, modèles génératifs, modèles basés sur l'énergie, deep learning, unsupervised learning, generative models, energy-based models
Framework for Real-time collaboration on extensive Data Types using Strong Eventual Consistency

La collaboration en temps réel est un cas spécial de collaboration où les utilisateurs travaillent sur le même élément simultanément et sont au courant des modifications des autres utilisateurs en temps réel. Les données distribuées doivent rester disponibles et consistant tout en étant répartis sur plusieurs systèmes physiques. "Strong Consistency" est une approche qui crée un ordre total des opérations en utilisant des mécanismes tel que le "locking". Cependant, cela introduit un "bottleneck". Ces dix dernières années, les algorithmes de concurrence ont été étudiés dans le but de garder la convergence de tous les replicas sans utiliser de "locking" ni de synchronisation. "Operational Trans- formation" et "Conflict-free Replicated Data Types (CRDT)" sont utilisés dans ce but. Cependant, la complexité de ces stratégies les rend compliquées à intégrer dans des logicielles conséquents, comme les éditeurs de modèles, spécialement pour des data structures complexes comme les graphes. Les implémentations actuelles intègrent seulement des data linéaires tel que le texte. Dans ce mémoire, nous présentons CollabServer, un framework pour construire des environnements de collaboration. Il a une implémentation de CRDTs pour des data structures complexes tel que les graphes et donne la possibilité de construire ses propres data structures. Real-time collaboration is a special case of collaboration where users work on the same artefact simultaneously and are aware of each other’s changes in real-time. Shared data should remain available and consistent while dealing with its physically distributed aspect. Strong Consistency is one approach that enforces a total order of operations using mechanisms, such as locking. This however introduces a bottleneck. In the last decade, algorithms for concurrency control have been studied to keep convergence of all replicas without locking or synchronization. Operational Transformation and Conflict free Replicated Data Types (CRDT) are widely used to achieve this purpose. However, the complexity of these strategies makes it hard to integrate in large software, such as modeling editors, especially for complex data types like graphs. Current implementations only integrate linear data, such as text. In this thesis, we present CollabServer, a framework to build collaborative environments. It features a CRDTs implementation for complex data types such as graphs and gives possibility to build other data structures.

Keyphrases: Algorithme de concurrence, Data distribuée, Génie logiciel, Système distribués, Concurrency Control, Concurrent Algorithms, Distributed Systems, Optimistic concurrency control, Software Engineering, Shared Data, Strong Eventual Consistency, Gestion de concurrence, Strong Eventual Consistency
Emploi des anglicismes par les adolescents et les jeunes adultes dans les SMS : comparaison entre le Québec et la Suisse

This research project is based on a sociolinguistic approach and presents a comparison between Quebec French and Swiss French of anglicisms in SMS messages made by teenagers and young adults. Using two sub-corpora, one Quebecer sub-corpora and one Swiss sub-corpora, both provided by the sms4science project, we selected the 12 to 25 year old group. In order to identify the anglicisms, we chose the Office québécois de la langue française (OQLF) categorization: lexical borrowing (anglicisme intégral), hybrid borrowing (anglicisme hybride), semantic borrowing (anglicisme sémantique), syntactic borrowing (anglicisme syntaxique), morphological borrowing (anglicisme morphologique) and phraseological borrowing (anglicisme phraséologique). The results reveal that, of all six categories of anglicisms, the lexical borrowing is the most used by both Quebecers and Swiss and that the 18 year olds and the 21 year olds are most prone to use anglicisms. La présente étude s’inscrit dans le champ de la sociolinguistique et a comme objectif de comparer l’emploi des anglicismes, entre le français du Québec et le français de la Suisse, par les adolescents et les jeunes adultes dans les messages SMS. Pour ce faire, nous utilisons deux sous-corpus, un sous-corpus québécois et un sous-corpus suisse provenant du projet sms4science. Nous retenons le groupe d’âge des 12 à 25 ans pour les deux sous-corpus. Nous utilisons la grille des anglicismes proposée par l’Office québécois de la langue française (OQLF) composée de six catégories : les anglicismes intégraux, les anglicismes hybrides, les anglicismes sémantiques, les anglicismes syntaxiques, les anglicismes morphologiques et les anglicismes phraséologiques. Les résultats montrent que des six catégories d’anglicismes, ce sont les anglicismes intégraux qui sont les plus répandus tant chez les Québécois que chez les Suisses et que ce sont les jeunes de 18 et de 21 ans qui ont le plus recours aux anglicismes.

Keyphrases: SMS, Anglicism, Quebec French, Swiss French, Teenager, Young adult, Anglicismes, SMS, Français québécois, Français suisse, Adolescent, Jeune adulte, Anglicism
Comparaison d'estimateurs de la variance du TMLE

Dans un contexte d'inférence causale où l'on cherche à estimer l'effet causal moyen d'une exposition dichotomique sur une variable issue, le TMLE de M. Van der Laan et D. Rubin est une technique qui applique à une estimation initiale de l'espérance conditionnelle de l'issue une modification ayant pour but de réduire le biais dans l'estimation correspondante de l'effet causal moyen. L'étalon-or en ce qui concerne l'estimation de la variance du TMLE est un estimateur de type sandwich. Divers estimateurs alternatifs sont identifiés et comparés à l'étalon-or lorsque la taille échantillonnale est petite, lorsque les scores de propension sont grands ou petits et lorsque les estimations initiales pour le score de propension ou pour l'espérance conditionnelle de l'issue sont mauvais. À chacun des estimateurs de la variance, un intervalle de confiance pour le TMLE est construit. On trouve que l'estimateur Jackknife donne des taux de couverture équivalents ou supérieurs aux autres estimateurs dans toutes ces situations. In the context of causal inference where we seek to estimate the average causal effect of a binary exposure on an outcome variable, the TMLE of M. Van der Laan and D. Rubin is a technique which applies to an initial estimate of the conditional expectation of the outcome a modification whose purpose is to reduce bias in the corresponding estimation of the average causal effect. The gold standard for estimation of the variance of the TMLE is a sandwich-type estimator. Various alternative estimators are identified and compared to the gold standard when the sample size is small, when the propensity scores are high or low and when the initial estimate of the propensity score or of the conditional expectation of the outcome is bad. for each of the variance estimator, a confidence interval for the TMLE is constructed. We find that the Jackknife estimator yields coverage rates equivalent or better than all the other estimators in all these situations.

Keyphrases: Inférence causale, TMLE, estimation de la variance, estimateur sandwich, Jackknife, Causal inference, TMLE, variance estimation, sandwich estimator, Jackknife
Fonctions entières complexes ayant des propriétés prescrites sur la droite réelle

Ce mémoire traite successivement de prolongements-interpolations et d’approximations de certaines classes de fonctions définies sur des ensembles particuliers. Nous avons ainsi construit des prolongements de classe C m(m fini ou non) pour des fonctions définies sur certains sous-ensembles de R n (demi-espace, quart-espace, slab, ...) Aussi avons-nous prolongé une fonction analytique qui envoie un intervalle ouvert I ⊂ R sur un intervalle ouvert J ⊂ R en une fonction holomorphe envoyant un voisinage ouvert U de I sur un voisinage ouvert V de J. Relativement au volet approximation nous avons considéré avec intérêt le théorème de Burke. Il constitue une généralisation du Lemme de Walsh. Ce dernier est luimême une généralisation du théorème d’approximation de Weierstrass. Nous avons cherché, non sans difficultés, à en mettre au point une preuve plus simple que celle qui a été présentée par l’auteur. Nous avons eu recours au théorème d’approximation de Whitney après l’avoir généralisé du cas des fonctions lisses au cas des fonctions de classe C m où m est fini. Il nous a permis de prouver certaines approximations qui nous permis à la fin de terminer la preuve du théorème de Burke. This thesis is successively devoted to interpolation-extrapolation and approximation in certain classes of functions defined on particular sets. Thus, we construct extensions of class C m (m finite or not) for functions defined on certain subsets (half-space, quarter-space, slabs, ...) of R n . Also, given a real-analytic function mapping an open interval I onto an interval J, we extend this function to a holomorphic function mapping a neighbourhood U of I in C into a given neighbourhood V of J. With regards to approximation, the Weierstrass approximation theorem was generalized by Walsh. A further generalization was given recently by Burke. We have attempted (with difficulty) to fashion a simpler proof than that given by Burke. As a tool we have invoked the Whitney approximation theorem for C ∞-functions, afte giving a version for C m-functions, where m is finite. Finally, this allowed us to complete the proof of Burke’s theorem.

Keyphrases: Approximation, Interpolation, Universalité, Holomorphe, Prolongement, Variété, Approximation, Interpolation, Holomorphic, Manifold, Extension, Dense, Universality
Comparaison empirique des méthodes bootstrap dans un contexte d'échantillonnage en population finie

Dans ce travail, nous comparons par simulation diverses méthodes bootstrap d’évaluation de la précision d’une estimation d’enquête pour trois plans d’échantillonnage: le plan aléatoire simple sans remise, le plan de Poisson et le plan de Poisson conditionnel. La plupart des méthodes bootstrap ont été dérivées de manière à reproduire l’estimation habituelle de la variance dans le cas d’un paramètre linéaire comme la moyenne ou le total d’une population. Nous évaluons la méthode d’une part pour estimer la variance et d’autre part pour construire des intervalles de confiance bootstrap en utilisant quatre techniques différentes, à savoir la technique asymptotique, percentile, bootstrap de base et t-bootstrap pour un total, mais aussi un ratio, un coefficient de corrélation, une médiane et un indice de Gini. La manière de mettre en oeuvre le t-bootstrap pour plusieurs méthodes bootstrap est une contribution originale de ce mémoire. In this thesis, we compare by simulation various bootstrap methods for evaluating the accuracy of a survey estimate for three sampling designs: simple random sampling, Poisson sampling and conditional Poisson sampling. Most bootstrap methods have been derived to reproduce the usual variance estimate for a linear parameter such as the average or the total of a population. We evaluate the method on their capacity to estimate the variance of survey estimates and to build bootstrap confidence intervals using four different techniques, namely asymptotic intervals, bootstrap percentile, basic bootstrap and t-bootstrap intervals for totals, but also ratios, correlation coefficients, medians, and Gini indices. The implementation of t-bootstrap intervals for several bootstrap methods is an original contribution of this dissertation.

Keyphrases: Estimation de la variance, Intervalles de confiance, t-bootstrap, Plan d'échantillonnage, Échantillonnage à probabilité inégale, t-bootstrap, Poids bootstrap, Pseudo-population, Variance estimation, Confidence intervals, Bootstrap weights, Sampling design, Unequal probability sampling
MCMC adaptatifs à essais multiples

Ce mémoire a pour but d'intégrer une composante adaptative au sein des algorithmes Metropolis à essais multiples (MTM) qui sont un cas particulier des méthodes de Monte Carlo par chaîne de Markov (MCMC). Les méthodes MCMC ainsi que leurs extensions adaptatives et à essais multiples sont explorées en profondeur (tant au niveau des variations possibles que de leurs propriétés théoriques) afin de bien ancrer l'étude de l'algorithme Metropolis à essais multiples adaptatif (aMTM) proposé. De plus, certains résultats dans la littérature sur les méthodes à essais multiples sont généralisés permettant alors l'obtention de résultats plus généraux à propos de l'algorithme aMTM. L'ergodicité de l'algorithme est ensuite démontrée en utilisant des résultats bien connus tirés de Roberts et Rosenthal (2007), d'Andrieu et Moulines (2006) et de Craiu et collab. (2015) et sa performance empirique est étudiée à travers une série d'expériences de simulation. L'algorithme aMTM arrive notamment à surpasser substantiellement des échantillonneurs plus simples (sans adaptation ou à un seul essai) pour des distributions cibles multimodales ou à géométrie complexe. Enfin, différentes variantes de l'algorithme sont proposées et comparées afin d'identifier des réglages particulièrement plus efficaces. Une implémentation de l'algorithme aMTM est fournie dans un progiciel R appelé aMTM disponible au https://github.com/fontaine618/aMTM. This memoir aims at introducing adaptation within the Multiple-Try Metropolis (MTM) algorithms which are a special case of the Markov chain Monte Carlo (MCMC) methods. The MCMC methods, along with their adaptive and multiple-try extensions, are thoroughly explored (both in their possible variations and in their theoretical properties) in order to firmly anchor  the study of the proposed adaptive Multiple-Try Metropolis (aMTM) algorithm. Moreover, some existing results on the properties of MTM algorithms are generalized to enable more general results about the aMTM algorithm. The ergodicity of the algorithm is then established using well known results of Roberts and Rosenthal (2007), Andrieu and Moulines (2006) and Craiu et al. (2015) and its empirical performance is studied through a series of simulation experiments. The aMTM algorithm achieves notably better performance than simpler samplers (non-adaptive or single-try) when applied to distributions that are multimodal or that exhibit complex geometry. Finally, many variations of the algorithm are proposed and compared to identify settings that are particularly more efficient. An implementation of the algorithm is provided in a R package called aMTM available at https://github.com/fontaine618/aMTM.

Keyphrases: Monte Carlo par chaînes de Markov, Monte Carlo par chaînes de Markov adaptatif, Metropolis à essais multiples, Ergodicité, Markov chain Monte Carlo, Adaptive Markov chain Monte Carlo, Multiple-Try Metropolis, Ergodicity
La mesure de Mahler d’une forme de Weierstrass

Ce mémoire a pour but de donner une introduction simple et brève à la mesure de Mahler et ses liens avec les fonctions-L de courbes elliptiques. Le point culminant de cette théorie se cache dans les conjectures de Bloch-Beı̆linson que nous tentons d’expliquer à la fin du chapitre 2, les deux premiers chapitres servant principalement à développer la matière nécessaire à leur compréhension et à introduire le problème principal de ce mémoire qui est de trouver une relation entre la mesure de Mahler de y 2 + 4xy + 2y − x 3 et la fonction-L de la courbe elliptique associée.  À cet effet, nous remarquons que la relation conjecturée par D. Boyd [1] est en fait fausse mais étudions tout de même les cycles d’homologie et les chemins d’intégration associés aux courbes elliptiques y 2 + 4xy + 2y − x 3 = 0 et (1 + x)(1 + y)(x + y) + 2xy = 0. This master’s thesis goal is to give a simple and brief introduction about Mahler measure and its connections with elliptic curves L-functions. This theory culminates with the Bloch-Beı̆linson conjectures which we try to explain at the end of chapter 2, the first two chapters serving to introduce the necessary requirements to understand them and as a stepping stone to this master’s main question which is to find a link between the Mahler measure of y 2 + 4xy + 2y − x 3 and the L-function associated to it.  For this purpose, we see that the conjectured relation given by D. Boyd [1] is false but we still study the homology cycles and integration paths associated to the elliptic curves y 2 + 4xy + 2y − x 3 = 0 and (1 + x)(1 + y)(x + y) + 2xy = 0.

Keyphrases: Mesure de Mahler, Courbes elliptiques, Valeurs spéciales de fonctions-L, Polynôme tempéré, Polygone de Newton, Régulateur elliptique, Mahler measure, Elliptic curve, Special values of L-functions, Tempered polynomial, Newton polygon, Elliptic regulator