A Compiler for the dependently typed language Beluga

Les structures avec des lieurs sont très communes en informatique. Les langages de programmation et les systèmes logiques sont des exemples de structures avec des lieurs. La manipulation de lieurs est délicate, de sorte que l’écriture de programmes qui ma- nipulent ces structures tirerait profit d’un soutien spécifique pour les lieurs. L’environ- nement de programmation Beluga est un exemple d’un tel système. Nous développons et présentons ici un compilateur pour ce système. Parmi les programmes pour lesquels Beluga est spécialement bien adapté, plusieurs peuvent bénéficier d’un compilateur. Par exemple, les programmes pour valider les types (les "type-checkers"), les compilateurs et les interpréteurs tirent profit du soutien spécifique des lieurs et des types dépendants présents dans le langage. Ils nécessitent tous également une exécution efficace, que l’on propose d’obtenir par le biais d’un compilateur. Le but de ce travail est de présenter un nouveau compilateur pour Beluga, qui emploie une représentation interne polyvalente et permet de partager du code entre plusieurs back-ends. Une contribution notable est la compilation du filtrage de Beluga, qui est particulièrement puissante dans ce langage.

Génération de résumés par abstraction

Cette thèse présente le résultat de plusieurs années de recherche dans le domaine de la génération automatique de résumés. Trois contributions majeures, présentées sous la forme d'articles publiés ou soumis pour publication, en forment le coeur. Elles retracent un cheminement qui part des méthodes par extraction en résumé jusqu'aux méthodes par abstraction. L'expérience HexTac, sujet du premier article, a d'abord été menée pour évaluer le niveau de performance des êtres humains dans la rédaction de résumés par extraction de phrases. Les résultats montrent un écart important entre la performance humaine sous la contrainte d'extraire des phrases du texte source par rapport à la rédaction de résumés sans contrainte. Cette limite à la rédaction de résumés par extraction de phrases, observée empiriquement, démontre l'intérêt de développer d'autres approches automatiques pour le résumé. Nous avons ensuite développé un premier système selon l'approche Fully Abstractive Summarization, qui se situe dans la catégorie des approches semi-extractives, comme la compression de phrases et la fusion de phrases. Le développement et l'évaluation du système, décrits dans le second article, ont permis de constater le grand défi de générer un résumé facile à lire sans faire de l'extraction de phrases. Dans cette approche, le niveau de compréhension du contenu du texte source demeure insuffisant pour guider le processus de sélection du contenu pour le résumé, comme dans les approches par extraction de phrases. Enfin, l'approche par abstraction basée sur des connaissances nommée K-BABS est proposée dans un troisième article. Un repérage des éléments d'information pertinents est effectué, menant directement à la génération de phrases pour le résumé. Cette approche a été implémentée dans le système ABSUM, qui produit des résumés très courts mais riches en contenu. Ils ont été évalués selon les standards d'aujourd'hui et cette évaluation montre que des résumés hybrides formés à la fois de la sortie d'ABSUM et de phrases extraites ont un contenu informatif significativement plus élevé qu'un système provenant de l'état de l'art en extraction de phrases.

Von Neumann-Morgenstern Stable Sets in Matching Problems

The following properties of the core of a one well-known: (i) the core is non-empty; (ii) the core is a lattice; and (iii) the set of unmatched agents is identical for any two matchings belonging to the core. The literature on two-sided matching focuses almost exclusively on the core and studies extensively its properties. Our main result is the following characterization of (von Neumann-Morgenstern) stable sets in one-to-one matching problem only if it is a maximal set satisfying the following properties : (a) the core is a subset of the set; (b) the set is a lattice; (c) the set of unmatched agents is identical for any two matchings belonging to the set. Furthermore, a set is a stable set if it is the unique maximal set satisfying properties (a), (b) and (c). We also show that our main result does not extend from one-to-one matching problems to many-to-one matching problems.

Matching Markets under (In)complete Information

We are the first to introduce incomplete information to centralized many-to-one matching markets such as those to entry-level labor markets or college admissions. This is important because in real life markets (i) any agent is uncertain about the other agents' true preferences and (ii) most entry-level matching is many-to-one (and not one-to-one). We show that for stable (matching) mechanisms there is a strong and surprising link between Nash equilibria under complete information and Bayesian Nash equilibria under incomplete information. That is,given a common belief, a strategy profile is a Bayesian Nash equilibrium under incomplete information in a stable mechanism if and only if, for any true profile in the support of the common belief, the submitted profile is a Nash equilibrium under complete information at the true profile in the direct preference revelation game induced by the stable mechanism. This result may help to explain the success of stable mechanisms in these markets.

Développement logiciel par transformation de modèles

La recherche en génie logiciel a depuis longtemps tenté de mieux comprendre le processus de développement logiciel, minimalement, pour en reproduire les bonnes pratiques, et idéalement, pour pouvoir le mécaniser. On peut identifier deux approches majeures pour caractériser le processus. La première approche, dite transformationnelle, perçoit le processus comme une séquence de transformations préservant certaines propriétés des données à l’entrée. Cette idée a été récemment reprise par l’architecture dirigée par les modèles de l’OMG. La deuxième approche consiste à répertorier et à codifier des solutions éprouvées à des problèmes récurrents. Les recherches sur les styles architecturaux, les patrons de conception, ou les cadres d’applications s’inscrivent dans cette approche. Notre travail de recherche reconnaît la complémentarité des deux approches, notamment pour l’étape de conception: dans le cadre du développement dirigé par les modèles, nous percevons l’étape de conception comme l’application de patrons de solutions aux modèles reçus en entrée. Il est coutume de définir l’étape de conception en termes de conception architecturale, et conception détaillée. La conception architecturale se préoccupe d’organiser un logiciel en composants répondant à un ensemble d’exigences non-fonctionnelles, alors que la conception détaillée se préoccupe, en quelque sorte, du contenu de ces composants. La conception architecturale s’appuie sur des styles architecturaux qui sont des principes d’organisation permettant d’optimiser certaines qualités, alors que la conception détaillée s’appuie sur des patrons de conception pour attribuer les responsabilités aux classes. Les styles architecturaux et les patrons de conception sont des artefacts qui codifient des solutions éprouvées à des problèmes récurrents de conception. Alors que ces artefacts sont bien documentés, la décision de les appliquer reste essentiellement manuelle. De plus, les outils proposés n’offrent pas un support adéquat pour les appliquer à des modèles existants. Dans cette thèse, nous nous attaquons à la conception détaillée, et plus particulièrement, à la transformation de modèles par application de patrons de conception, en partie parce que les patrons de conception sont moins complexes, et en partie parce que l’implémentation des styles architecturaux passe souvent par les patrons de conception. Ainsi, nous proposons une approche pour représenter et appliquer les patrons de conception. Notre approche se base sur la représentation explicite des problèmes résolus par ces patrons. En effet, la représentation explicite du problème résolu par un patron permet : (1) de mieux comprendre le patron, (2) de reconnaître l’opportunité d’appliquer le patron en détectant une instance de la représentation du problème dans les modèles du système considéré, et (3) d’automatiser l’application du patron en la représentant, de façon déclarative, par une transformation d’une instance du problème en une instance de la solution. Pour vérifier et valider notre approche, nous l’avons utilisée pour représenter et appliquer différents patrons de conception et nous avons effectué des tests pratiques sur des modèles générés à partir de logiciels libres.

Découverte et application de nouveaux motifs d'association propres à l'hexaphénylbenzène et à ses dérivés

Les propriétés des matériaux moléculaires proviennent à la fois de la structure des composantes individuelles et de la façon dont elles s’associent. Ce dernier aspect reste difficile à contrôler, malgré de grandes avancées en science des matériaux. Pour mieux comprendre la relation structure-propriétés, nous avons entrepris une étude systématique de l'hexaphénylbenzène et de ses dérivés, qui offrent une charpente symétrique et rigide. En premier lieu, nous avons attaché six groupements diaminotriazinyles sur l’hexaphénylbenzène afin de produire des réseaux tridimensionnels hautement poreux maintenus par des ponts hydrogène. En modifiant systématiquement le coeur moléculaire, nous avons excisé près du tiers de la molécule-mère, générant des réseaux supramoléculaires dont la porosité s’est élevée graduellement jusqu’à 75%, équivalant ainsi le record pour ce type de matériaux. Ensuite, nous avons étudié le comportement de l’hexakis(4-nitrophényl)benzène. Dans les structures cristallines obtenues, des interactions non-covalentes entre groupements nitro démontrent leur potentiel en chimie supramoléculaire. Le coeur moléculaire ne joue qu’un rôle secondaire dans l’empilement des molécules : seules quelques interactions C-H•••π impliquant le cycle aromatique central de l’hexaphénylbenzène sont évidentes. Cette dernière observation nous a poussés à étudier le comportement à l’état cristallin de l’hexaphénylbenzène et ses dérivés. En scrutant attentivement neuf structures cristallines de ces composés, nous avons décerné la présence récurrente d’interactions C-H•••π impliquant le cycle aromatique central. Cette association caractéristique a été exploitée pour créer des réseaux supramoléculaires maintenus par des interactions C-H•••π sélectives entre un groupement éthynyle et le cycle aromatique central de l’hexaphénylbenzène. Finalement, nous avons joint le côté sombre de l’ingénierie cristalline en utilisant nos connaissances dans le but d’empêcher la formation d’interactions directionnelles. En protégeant le cycle aromatique central de l’hexaphénylbenzène à l’aide de groupements alkyles, les interactions C-H•••π ont été pratiquement éliminées. Ces résultats offrent la possibilité de créer de nouveaux matériaux amorphes. Dans ces études, focalisées sur le système hexaphénylbenzène, nous avons mis en relief des phénomènes qui sont obscurcis dans d'autres familles de molécules. De plus, ce système a grandement facilité l’utilisation d’une approche méthodique pour explorer la relation structure-propriétés. Nos travaux nous ont amenés à des conclusions de valeur universelle en science des matériaux moléculaires.

Incorporating complex cells into neural networks for pattern classification

Dans le domaine des neurosciences computationnelles, l'hypothèse a été émise que le système visuel, depuis la rétine et jusqu'au cortex visuel primaire au moins, ajuste continuellement un modèle probabiliste avec des variables latentes, à son flux de perceptions. Ni le modèle exact, ni la méthode exacte utilisée pour l'ajustement ne sont connus, mais les algorithmes existants qui permettent l'ajustement de tels modèles ont besoin de faire une estimation conditionnelle des variables latentes. Cela nous peut nous aider à comprendre pourquoi le système visuel pourrait ajuster un tel modèle; si le modèle est approprié, ces estimé conditionnels peuvent aussi former une excellente représentation, qui permettent d'analyser le contenu sémantique des images perçues. Le travail présenté ici utilise la performance en classification d'images (discrimination entre des types d'objets communs) comme base pour comparer des modèles du système visuel, et des algorithmes pour ajuster ces modèles (vus comme des densités de probabilité) à des images. Cette thèse (a) montre que des modèles basés sur les cellules complexes de l'aire visuelle V1 généralisent mieux à partir d'exemples d'entraînement étiquetés que les réseaux de neurones conventionnels, dont les unités cachées sont plus semblables aux cellules simples de V1; (b) présente une nouvelle interprétation des modèles du système visuels basés sur des cellules complexes, comme distributions de probabilités, ainsi que de nouveaux algorithmes pour les ajuster à des données; et (c) montre que ces modèles forment des représentations qui sont meilleures pour la classification d'images, après avoir été entraînés comme des modèles de probabilités. Deux innovations techniques additionnelles, qui ont rendu ce travail possible, sont également décrites : un algorithme de recherche aléatoire pour sélectionner des hyper-paramètres, et un compilateur pour des expressions mathématiques matricielles, qui peut optimiser ces expressions pour processeur central (CPU) et graphique (GPU).

Diversité fonctionnelle du facteur de transcription Tbx5 dans le coeur

Le cœur des vertébrés est un organe modulaire qui requiert le " patterning " complexe des champs morphogénétiques cardiogènes et la convergence coordonnée des diverses sous-populations de progéniteurs cardiogéniques. Au moins 7 facteurs de transcription de la famille T-box coopèrent au sein de ces nombreuses sous-populations de progéniteurs cardiogéniques afin de réguler la morphogenèse et l’agencement de multiples structures le long de l’ébauche cardiaque, ce qui explique que les mutations humaines de ces gènes engendrent diverses malformations congénitales cardiaques (MCCs). L’un de ces gènes T-box, Tbx5, dont l’haploinsuffisance génère le syndrome de Holt-Oram (SHO), intervient dans une grande variété de réseaux de régulation géniques (RRGs) qui orchestrent la morphogenèse des oreillettes, du ventricule gauche, de la valve mitrale, des septums inter-auriculaire et inter-ventriculaire, ainsi que du système de conduction cardiaque. La diversité des RRGs impliqués dans la formation de ces structures cardiaques suggère que Tbx5 détient une profusion de fonctions qui ne seront identifiables qu’en répertoriant ses activités moléculaires dans chaque lignée cardiaque examinée isolément. Afin d’aborder cette problématique, une ablation génétique de Tbx5 dans l’endocarde a été réalisée. Cette expérience a démontré le rôle crucial de Tbx5 dans la survie des cellules endocardiques bordant le septum primum et des cardiomyocytes au sein de cette structure embryonnaire qui contribuera à la morphogenèse du septum inter-auriculaire. En outre, cette étude a révélé l’existence d’une communication croisée entre la sous-population de cellules endocardiques Tbx5+ et le myocarde au niveau du septum primum, afin d’assurer la survie des cardiomyocytes, et ultimement de garantir la maturation du septum inter-auriculaire. Nos résultats confirment aussi l’importance de l’interdépendance génétique (Tbx5 et Gata4 ainsi que Tbx5 et Nos3) entre différents loci dans la morphogenèse de la cloison inter-auriculaire, et particulièrement de l’influence que peut avoir l’environnement sur la pénétrance et l’expressivité des communications inter-auriculaires (CIAs) dans le SHO. En outre, puisque les fonctions d’un gène dépendent ordinairement des différents isoformes qu’il peut générer, une deuxième étude a focalisé davantage sur l’aspect transcriptionnel de Tbx5. Cette approche a mené à la découverte de 6 transcrits alternatifs exhibant des fonctions à la fois communes et divergentes. La caractérisation de 2 de ces isoformes a révélé le rôle de l’isoforme long (Tbx5_v1) dans la régulation de la croissance des cardiomyocytes durant la cardiogénèse, tandis que l’isoforme court (Tbx5_v2), préférentiellement exprimé dans le cœur mature, réprime la croissance cellulaire. Il est donc entièrement concevable que les mutations de TBX5 entraînant une troncation de la région C-terminale accroissent la concentration d’une protéine mutée qui, à l’instar de Tbx5_v2, interfère avec la croissance de certaines structures cardiaques. En revanche, la divergence de fonctions de ces isoformes, caractérisée par les disparités de localisation subcellulaire et de d’interaction avec d’autres cofacteurs cardiaques, suggère que les mutations affectant davantage un isoforme favoriseraient l’émergence d’un type particulier de MCC. Finalement, un dernier objectif était d’identifier le ou les mécanisme(s) moléculaire(s) par le(s)quel(s) Tbx5 régule son principal gène cible, Nppa, et d’en extraire les indices qui éclairciraient sa fonction transcriptionnelle. Cet objectif nécessitait dans un premier lieu d’identifier les différents modules cis-régulateurs (MCRs) coordonnant la régulation transcriptionnelle de Nppa et Nppb, deux gènes natriurétiques dont l’organisation en tandem et le profil d’expression durant la cardiogénèse sont conservés dans la majorité des vertébrés. L’approche d’empreinte phylogénétique employée pour scanner le locus Nppb/Nppa a permis d’identifier trois MCRs conservés entre diverses espèces de mammifères, dont un (US3) est spécifique aux euthériens. Cette étude a corroboré que la régulation de l’expression du tandem génique Nppb/Nppa requérait l’activité transcriptionnelle d’enhancers en complément aux promoteurs de Nppa et Nppb. La concordance quasiment parfaite entre les profils d’expression de Tbx5 et de ces deux gènes natriurétiques chez les mammifères, suggère que le gradient d’expression ventriculaire de Tbx5 est interprété par le recrutement de ce facteur au niveau des différents enhancers identifiés. En somme, les études présentées dans cette thèse ont permis de clarifier la profusion de fonctions cardiaques que possède Tbx5. Certaines de ces fonctions émanent de l’épissage alternatif de Tbx5, qui favorise la synthèse d’isoformes dotés de propriétés spécifiques. Les diverses interactions combinatoires entre ces isoformes et d’autres facteurs cardiaques au sein des diverses sous-populations de progéniteurs cardiogènes contribuent à l’émergence de RRGs cardiaques divergents.

Identification et modélisation lexicographique des dépendances syntaxiques régies du français: le cas des dépendances nominales

Cette recherche porte sur l’interface entre la sémantique lexicale et la syntaxe, et elle s’inscrit dans le cadre du projet de base lexicale DiCo (acronyme pour Dictionnaire de combinatoire) à l’Observatoire de Linguistique Sens-Texte [OLST] de l’Université de Montréal. Le projet découle d'une volonté d'inscrire de façon concise et complète, à même le dictionnaire, le comportement syntaxique typique à chaque unité lexicale. Dans cette optique, nous encodons la cooccurrence des lexies nominales du DiCo avec leurs actants à l'intérieur d'un tableau de régime lexical (aussi connu sous le nom de schéma valenciel, structure argumentale, cadre de sous-catégorisation, structure prédicats-arguments, etc.), en notant entre autres les dépendances syntaxiques de surface impliquées. Dans ce mémoire, nous présentons les propriétés syntaxiques d'une dépendance nominale du français, celle que nous avons nommée attributive adnominale, de façon à exposer une méthodologie d'identification et de caractérisation des dépendances syntaxiques de surface. Nous donnons également la liste des dépendances nominales régies identifiées au cours de ce travail. Par la suite, nous exposons la création d'une base de données de régimes généralisés du français nommée CARNAVAL. Finalement, nous discutons des applications possibles de notre travail, particulièrement en ce qui a trait à la création d'une typologie des régimes lexicaux du français.

Is social phobia characterized by a distinct interpersonal pattern?

Traditionnellement, le construit de la phobie sociale a été défini selon une vision intrapersonnelle, en tant que trouble de l’anxiété. Une autre conception se propose de la définir d’un point de vue interpersonnel, comme un pattern global d’autoprotection. L’objectif principal de cette thèse est de tester des hypothèses tirées du modèle interpersonnel de la phobie sociale. Deux études, présentées sous forme d’articles, ont permis d’examiner si des patterns spécifiques d’autoprotection, tels que l’impuissance et la soumission, caractérisent le mode de fonctionnement des phobiques sociaux. Les études ont également évalué si l’autoprotection et l’anxiété sont interreliées. Pour la première étude, les patterns interpersonnels de 132 phobiques sociaux, évalués à l’aide d’une mesure dérivée du Circumplex interpersonnel, ont été comparés à ceux de 85 individus célibataires ayant une dysfonction sexuelle et 105 sujets normaux. La relation entre les patterns d’autoprotection, l’anxiété sociale, la détresse générale et le fonctionnement social a également été examinée chez les phobiques sociaux. La seconde étude a permis d’examiner l’évolution des patterns d’autoprotection ainsi que de l’anxiété sociale, de la détresse générale et du fonctionnement social, chez 85 phobiques sociaux à quatre moments : avant et après un traitement d’approche interpersonnelle, ainsi qu’aux relances de six mois et d’un an. L’étude a également comparé les participants en rémission et ceux satisfaisant les critères de la phobie sociale un an suivant la fin du traitement. Les résultats suggèrent que les patterns d’impuissance et de soumission sont caractéristiques de la phobie sociale. Plus précisément, ces patterns décrivent davantage les comportements des phobiques sociaux plutôt que ceux des groupes de comparaison. De plus, une réduction significative de l’autoprotection a été notée au post-traitement et maintenue jusqu’au suivi d’un an, surtout chez les participants en rémission.En outre, une relation entre l’autoprotection, l’anxiété sociale et la détresse générale a été mise en évidence chez les phobiques sociaux. Une amélioration de l’anxiété, de la détresse subjective et du fonctionnement social cohérente avec la dissolution des patterns d’autoprotection a également été obtenue au post-traitement. En conclusion, les résultats des deux études appuient une conception interpersonnelle de la phobie sociale.

Variabilité des souches de Escherichia coli provenant de divers poulaillers au Québec

La technique d’empreinte génétique par rep-PCR, qui utilise des séquences d’ADN répétitives, a été utilisée pour mettre en évidence la présence de groupes d’Escherichia coli signatures pour divers poulaillers et d’évaluer leur évolution suite au détassement. L’amorce (GTG)5 a été utilisée pour générer des empreintes d’ADN de 522 isolats provenant de 7 poulaillers échantillonnés deux fois : juste avant et 5 jours après le détassement. Les empreintes d’ADN ont été analysées selon l’algorithme de correspondance de bandes de Jaccard. Les analyses de Jackknife des coefficients de similitude ont révélé qu’entre 73% et 93% des isolats ont pu être correctement regroupés selon leur poulailler d’origine. Un dendrogramme construit à partir des coefficients de similitude de Jaccard a groupé les isolats dans 42 grappes avec près de la moitié dans une seule grappe. Environ 80% des isolats ont été groupés dans les 6 plus grosses grappes. Quatre de ces grappes été constituées majoritairement d’isolats provenant d’un seul site. Ces grappes pourraient être des grappes signatures qui permettraient d’identifier des poulaillers en particulier. La comparaison des nombres de grappes présentes avant et après le détassement a révélé une variabilité de l’impact du détassement sur les populations fécales d’E. coli. Pour certains sites, il y avait peu d’agrégats présents tant avant qu’après le détassement alors que pour d’autres sites c’était le contraire. Quoique plus de recherches soient nécessaires afin de valider les conclusions, nos résultats suggèrent la présence de sous-populations signatures d’E. coli pour certains poulaillers et une réponse variable à l’effet du détassement.