Dynamic Programming Approaches for Estimating and Applying Large-scale Discrete Choice Models

People go through their life making all kinds of decisions, and some of these decisions affect their demand for transportation, for example, their choices of where to live and where to work, how and when to travel and which route to take. Transport related choices are typically time dependent and characterized by large number of alternatives that can be spatially correlated. This thesis deals with models that can be used to analyze and predict discrete choices in large-scale networks. The proposed models and methods are highly relevant for, but not limited to, transport applications. We model decisions as sequences of choices within the dynamic discrete choice framework, also known as parametric Markov decision processes. Such models are known to be difficult to estimate and to apply to make predictions because dynamic programming problems need to be solved in order to compute choice probabilities. In this thesis we show that it is possible to explore the network structure and the flexibility of dynamic programming so that the dynamic discrete choice modeling approach is not only useful to model time dependent choices, but also makes it easier to model large-scale static choices. The thesis consists of seven articles containing a number of models and methods for estimating, applying and testing large-scale discrete choice models. In the following we group the contributions under three themes: route choice modeling, large-scale multivariate extreme value (MEV) model estimation and nonlinear optimization algorithms. Five articles are related to route choice modeling. We propose different dynamic discrete choice models that allow paths to be correlated based on the MEV and mixed logit models. The resulting route choice models become expensive to estimate and we deal with this challenge by proposing innovative methods that allow to reduce the estimation cost. For example, we propose a decomposition method that not only opens up for possibility of mixing, but also speeds up the estimation for simple logit models, which has implications also for traffic simulation. Moreover, we compare the utility maximization and regret minimization decision rules, and we propose a misspecification test for logit-based route choice models. The second theme is related to the estimation of static discrete choice models with large choice sets. We establish that a class of MEV models can be reformulated as dynamic discrete choice models on the networks of correlation structures. These dynamic models can then be estimated quickly using dynamic programming techniques and an efficient nonlinear optimization algorithm. Finally, the third theme focuses on structured quasi-Newton techniques for estimating discrete choice models by maximum likelihood. We examine and adapt switching methods that can be easily integrated into usual optimization algorithms (line search and trust region) to accelerate the estimation process. The proposed dynamic discrete choice models and estimation methods can be used in various discrete choice applications. In the area of big data analytics, models that can deal with large choice sets and sequential choices are important. Our research can therefore be of interest in various demand analysis applications (predictive analytics) or can be integrated with optimization models (prescriptive analytics). Furthermore, our studies indicate the potential of dynamic programming techniques in this context, even for static models, which opens up a variety of future research directions.

L'image principale de profil, symbole de l'individu connecté

Depuis le début du XXIe siècle, un type particulier d’images a envahi l’espace public constitué par Internet : il s’agit des images principales de profil, ces images que les utilisateurs de sites de réseaux sociaux choisissent pour les représenter auprès des autres individus connectés. Comme le plus souvent il s’agit d’une image du corps de celui ou celle qui s’affiche ainsi, il est intéressant de s’intéresser à cette pratique en la rattachant à des pratiques plus anciennes. Dans un premier temps, cette étude présente donc une perspective socio-historique en notant la ressemblance de la pratique de l’image principale de profil avec celle de l’autoportrait et du portrait commandé. Cela permet de remarquer plusieurs points de rupture ou d’inflexion dans l’usage de ce type d’images, mais aussi d’en dégager les usages sociaux typiques. Ensuite, l’observation d’un lieu particulier d’Internet permet de tirer les conclusions suivantes : si l’usage principal de ces images est facile à expliquer, elles servent à symboliser une présence dans des lieux non accessibles aux corps sensibles, ces images montrent toujours des éléments qui permettent de déduire une position sociale et elles sont fondamentalement identiques aux images produites avant Internet. Ensuite, l’étude de ces images montre qu’il y a un véritable continuum dans la manière de dévoiler son intimité qui permet d’affirmer que la frontière entre public et privé n’existe pas sur Internet. Finalement, ces images montrent une absence de canon quant à leur production et une multiplicité des façons de se mettre en scène qui laissent à penser qu’elles sont devenues des symboles à part entière dans la communication qui peut s’établir entre des étrangers sur Internet.

Trajectoires migratoires et espaces de sociabilité : stratégies de migrants de France à Montréal

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Tectonique moléculaire : introduction de la géométrie trigonale et de la chiralité

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

A socio-technological approach to sharing knowledge across disciplines

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Cryptographie quantique à plusieurs participants par multiplexage en longueur d'onde

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

"L'insertion résidentielle et économique des Arméniens de Montréal : comportements d'une communauté culturelle ou d'une communauté diasporique?"

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Mécanismes de guidage des axones sérotoninergiques du raphé dorsal : études in vivo et in vitro

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Mécanismes de la transmission synaptique GABAergique des cellules pyramidales et interneurones de l'hippocampe chez le rat

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Étude de la toxicité causée par le gène C9orf72 dans la Sclérose Latérale Amyotrophique

La Sclérose Latérale Amyotrophique (SLA) est une maladie neurodégénérative qui affecte les neurones moteurs. 10% des cas sont des cas familiaux et l’étude de ces familles a mené à la découverte de plusieurs gènes pouvant causer la SLA, incluant SOD1, TARDBP et FUS. L’expansion de la répétition GGGGCC dans le gène C9orf72 est, à ce jour, la cause la plus connue de SLA. L’impact de cette expansion est encore méconnu et il reste à déterminer si la toxicité est causée par un gain de fonction, une perte de fonction ou les deux. Plusieurs gènes impliqués dans la SLA sont conservés entre le nématode Caenorhabditis elegans et l’humain. C. elegans est un vers transparent fréquemment utilisé pour des études anatomiques, comportementales et génétiques. Il possède une lignée cellulaire invariable qui inclue 302 neurones. Aussi, les mécanismes de réponse au stress ainsi que les mécanismes de vieillissement sont très bien conservés entre ce nématode et l’humain. Donc, notre groupe, et plusieurs autres, ont utilisé C. elegans pour étudier plusieurs aspects de la SLA. Pour mieux comprendre la toxicité causée par l’expansion GGGGCC de C9orf72, nous avons développé deux modèles de vers pour étudier l’impact d’une perte de fonction ainsi que d’un gain de toxicité de l’ARN. Pour voir les conséquences d’une perte de fonction, nous avons étudié l’orthologue de C9orf72 dans C. elegans, alfa-1 (ALS/FTD associated gene homolog). Les vers mutants alfa-1(ok3062) développent des problèmes moteurs causant une paralysie et une dégénérescence spécifique des neurones moteurs GABAergiques. De plus, les mutants sont sensibles au stress osmotique qui provoque une dégénérescence. D’autre part, l’expression de la séquence d’ARN contenant une répétition pathogénique GGGGCC cause aussi des problèmes moteurs et de la dégénérescence affectant les neurones moteurs. Nos résultats suggèrent donc qu’un gain de toxicité de l’ARN ainsi qu’une perte de fonction de C9orf72 sont donc toxiques pour les neurones. Puisque le mouvement du vers peut être rapidement évalué en cultivant les vers dans un milieu liquide, nous avons développé un criblage de molécules pouvant affecter le mouvement des vers mutants alfa-1 en culture liquide. Plus de 4 000 composés ont été évalués et 80 ameliore la mobilité des vers alfa-1. Onze molécules ont aussi été testées dans les vers exprimant l’expansion GGGGCC et huit diminuent aussi le phénotype moteur de ces vers. Finalement, des huit molécules qui diminent la toxicité causée par la perte de fonction de C9orf72 et la toxicité de l’ARN, deux restaurent aussi l’expression anormale de plusieurs transcrits d’ARN observée dans des cellules dérivées de patient C9orf72. Avec ce projet, nous voulons identifier des molécules pouvant affecter tous les modes de toxicité de C9orf72 et possiblement ouvrir de nouvelles avenues thérapeutiques

Mécanismes psychophysiques et neuronaux de la compensation dynamique de multiples champs de force : facilitation et anticipation liée à des indices de couleur

Dans cette thèse, nous abordons le contrôle moteur du mouvement du coude à travers deux approches expérimentales : une première étude psychophysique a été effectuée chez les sujets humains, et une seconde implique des enregistrements neurophysiologiques chez le singe. Nous avons recensé plusieurs aspects non résolus jusqu’à présent dans l’apprentissage moteur, particulièrement concernant l’interférence survenant lors de l’adaptation à deux ou plusieurs champs de force anti-corrélés. Nous avons conçu un paradigme où des stimuli de couleur aident les sujets à prédire la nature du champ de force externe actuel avant qu’ils ne l’expérimentent physiquement durant des mouvements d’atteinte. Ces connaissances contextuelles faciliteraient l’adaptation à des champs de forces en diminuant l’interférence. Selon le modèle computationnel de l’apprentissage moteur MOSAIC (MOdular Selection And Identification model for Control), les stimuli de couleur aident les sujets à former « un modèle interne » de chaque champ de forces, à s’en rappeler et à faire la transition entre deux champs de force différents, sans interférence. Dans l’expérience psychophysique, quatre groupes de sujets humains ont exécuté des mouvements de flexion/extension du coude contre deux champs de forces. Chaque force visqueuse était associée à une couleur de l’écran de l’ordinateur et les deux forces étaient anti-corrélées : une force résistante (Vr) a été associée à la couleur rouge de l’écran et l’autre, assistante (Va), à la couleur verte de l’écran. Les deux premiers groupes de sujets étaient des groupes témoins : la couleur de l’écran changeait à chaque bloc de 4 essais, tandis que le champ de force ne changeait pas. Les sujets du groupe témoin Va ne rencontraient que la force assistante Va et les sujets du groupe témoin Vr performaient leurs mouvements uniquement contre une force résistante Vr. Ainsi, dans ces deux groupes témoins, les stimuli de couleur n’étaient pas pertinents pour adapter le mouvement et les sujets ne s’adaptaient qu’à une seule force (Va ou Vr). Dans les deux groupes expérimentaux, cependant, les sujets expérimentaient deux champs de forces différents dans les différents blocs d’essais (4 par bloc), associés à ces couleurs. Dans le premier groupe expérimental (groupe « indice certain », IC), la relation entre le champ de force et le stimulus (couleur de l’écran) était constante. La couleur rouge signalait toujours la force Vr tandis que la force Va était signalée par la couleur verte. L’adaptation aux deux forces anti-corrélées pour le groupe IC s’est avérée significative au cours des 10 jours d’entraînement et leurs mouvements étaient presque aussi bien ajustés que ceux des deux groupes témoins qui n’avaient expérimenté qu’une seule des deux forces. De plus, les sujets du groupe IC ont rapidement démontré des changements adaptatifs prédictifs dans leurs sorties motrices à chaque changement de couleur de l’écran, et ceci même durant leur première journée d’entraînement. Ceci démontre qu’ils pouvaient utiliser les stimuli de couleur afin de se rappeler de la commande motrice adéquate. Dans le deuxième groupe expérimental, la couleur de l’écran changeait régulièrement de vert à rouge à chaque transition de blocs d’essais, mais le changement des champs de forces était randomisé par rapport aux changements de couleur (groupe « indice-incertain », II). Ces sujets ont pris plus de temps à s’adapter aux champs de forces que les 3 autres groupes et ne pouvaient pas utiliser les stimuli de couleurs, qui n’étaient pas fiables puisque non systématiquement reliés aux champs de forces, pour faire des changements prédictifs dans leurs sorties motrices. Toutefois, tous les sujets de ce groupe ont développé une stratégie ingénieuse leur permettant d’émettre une réponse motrice « par défaut » afin de palper ou de sentir le type de la force qu’ils allaient rencontrer dans le premier essai de chaque bloc, à chaque changement de couleur. En effet, ils utilisaient la rétroaction proprioceptive liée à la nature du champ de force afin de prédire la sortie motrice appropriée pour les essais qui suivent, jusqu’au prochain changement de couleur d’écran qui signifiait la possibilité de changement de force. Cette stratégie était efficace puisque la force demeurait la même dans chaque bloc, pendant lequel la couleur de l’écran restait inchangée. Cette étude a démontré que les sujets du groupe II étaient capables d’utiliser les stimuli de couleur pour extraire des informations implicites et explicites nécessaires à la réalisation des mouvements, et qu’ils pouvaient utiliser ces informations pour diminuer l’interférence lors de l’adaptation aux forces anti-corrélées. Les résultats de cette première étude nous ont encouragés à étudier les mécanismes permettant aux sujets de se rappeler d’habiletés motrices multiples jumelées à des stimuli contextuels de couleur. Dans le cadre de notre deuxième étude, nos expériences ont été effectuées au niveau neuronal chez le singe. Notre but était alors d’élucider à quel point les neurones du cortex moteur primaire (M1) peuvent contribuer à la compensation d’un large éventail de différentes forces externes durant un mouvement de flexion/extension du coude. Par cette étude, nous avons testé l’hypothèse liée au modèle MOSAIC, selon laquelle il existe plusieurs modules contrôleurs dans le cervelet qui peuvent prédire chaque contexte et produire un signal de sortie motrice approprié pour un nombre restreint de conditions. Selon ce modèle, les neurones de M1 recevraient des entrées de la part de plusieurs contrôleurs cérébelleux spécialisés et montreraient ensuite une modulation appropriée de la réponse pour une large variété de conditions. Nous avons entraîné deux singes à adapter leurs mouvements de flexion/extension du coude dans le cadre de 5 champs de force différents : un champ nul ne présentant aucune perturbation, deux forces visqueuses anti-corrélées (assistante et résistante) qui dépendaient de la vitesse du mouvement et qui ressemblaient à celles utilisées dans notre étude psychophysique chez l’homme, une force élastique résistante qui dépendait de la position de l’articulation du coude et, finalement, un champ viscoélastique comportant une sommation linéaire de la force élastique et de la force visqueuse. Chaque champ de force était couplé à une couleur d’écran de l’ordinateur, donc nous avions un total de 5 couleurs différentes associées chacune à un champ de force (relation fixe). Les singes étaient bien adaptés aux 5 conditions de champs de forces et utilisaient les stimuli contextuels de couleur pour se rappeler de la sortie motrice appropriée au contexte de forces associé à chaque couleur, prédisant ainsi leur sortie motrice avant de sentir les effets du champ de force. Les enregistrements d’EMG ont permis d’éliminer la possibilité de co-contractions sous-tendant ces adaptations, étant donné que le patron des EMG était approprié pour compenser chaque condition de champ de force. En parallèle, les neurones de M1 ont montré des changements systématiques dans leurs activités, sur le plan unitaire et populationnel, dans chaque condition de champ de force, signalant les changements requis dans la direction, l’amplitude et le décours temporel de la sortie de force musculaire nécessaire pour compenser les 5 conditions de champs de force. Les changements dans le patron de réponse pour chaque champ de force étaient assez cohérents entre les divers neurones de M1, ce qui suggère que la plupart des neurones de M1 contribuent à la compensation de toutes les conditions de champs de force, conformément aux prédictions du modèle MOSAIC. Aussi, cette modulation de l’activité neuronale ne supporte pas l’hypothèse d’une organisation fortement modulaire de M1.

Représentations et fusion des algèbres de Temperley-Lieb originale et diluée

Les algèbres de Temperley-Lieb originales, aussi dites régulières, apparaissent dans de nombreux modèles statistiques sur réseau en deux dimensions: les modèles d'Ising, de Potts, des dimères, celui de Fortuin-Kasteleyn, etc. L'espace d'Hilbert de l'hamiltonien quantique correspondant à chacun de ces modèles est un module pour cette algèbre et la théorie de ses représentations peut être utilisée afin de faciliter la décomposition de l'espace en blocs; la diagonalisation de l'hamiltonien s'en trouve alors grandement simplifiée. L'algèbre de Temperley-Lieb diluée joue un rôle similaire pour des modèles statistiques dilués, par exemple un modèle sur réseau où certains sites peuvent être vides; ses représentations peuvent alors être utilisées pour simplifier l'analyse du modèle comme pour le cas original. Or ceci requiert une connaissance des modules de cette algèbre et de leur structure; un premier article donne une liste complète des modules projectifs indécomposables de l'algèbre diluée et un second les utilise afin de construire une liste complète de tous les modules indécomposables des algèbres originale et diluée. La structure des modules est décrite en termes de facteurs de composition et par leurs groupes d'homomorphismes. Le produit de fusion sur l'algèbre de Temperley-Lieb originale permet de «multiplier» ensemble deux modules sur cette algèbre pour en obtenir un autre. Il a été montré que ce produit pouvait servir dans la diagonalisation d'hamiltoniens et, selon certaines conjectures, il pourrait également être utilisé pour étudier le comportement de modèles sur réseaux dans la limite continue. Un troisième article construit une généralisation du produit de fusion pour les algèbres diluées, puis présente une méthode pour le calculer. Le produit de fusion est alors calculé pour les classes de modules indécomposables les plus communes pour les deux familles, originale et diluée, ce qui vient ajouter à la liste incomplète des produits de fusion déjà calculés par d'autres chercheurs pour la famille originale. Finalement, il s'avère que les algèbres de Temperley-Lieb peuvent être associées à une catégorie monoïdale tressée, dont la structure est compatible avec le produit de fusion décrit ci-dessus. Le quatrième article calcule explicitement ce tressage, d'abord sur la catégorie des algèbres, puis sur la catégorie des modules sur ces algèbres. Il montre également comment ce tressage permet d'obtenir des solutions aux équations de Yang-Baxter, qui peuvent alors être utilisées afin de construire des modèles intégrables sur réseaux.

La face cachée de la dune : communautés fongiques du sol: dynamique, succession et interactions avec la végétation d’un écosystème dunaire côtier aux Îles de la Madeleine, Qc

Les écosystèmes dunaires remplissent plusieurs fonctions écologiques essentielles comme celle de protéger le littoral grâce à leur capacité d’amortissement face aux vents et vagues des tempêtes. Les dunes jouent aussi un rôle dans la filtration de l’eau, la recharge de la nappe phréatique, le maintien de la biodiversité, en plus de présenter un attrait culturel, récréatif et touristique. Les milieux dunaires sont très dynamiques et incluent plusieurs stades de succession végétale, passant de la plage de sable nu à la dune bordière stabilisée par l’ammophile à ligule courte, laquelle permet aussi l’établissement d’autres herbacées, d’arbustes et, éventuellement, d’arbres. Or, la survie de ces végétaux est intimement liée aux microorganismes du sol. Les champignons du sol interagissent intimement avec les racines des plantes, modifient la structure des sols, et contribuent à la décomposition de la matière organique et à la disponibilité des nutriments. Ils sont donc des acteurs clés de l’écologie des sols et contribuent à la stabilisation des dunes. Malgré cela, la diversité et la structure des communautés fongiques, ainsi que les mécanismes influençant leur dynamique écologique, demeurent relativement méconnus. Le travail présenté dans cette thèse explore la diversité des communautés fongiques à travers le gradient de succession et de conditions édaphiques d’un écosystème dunaire côtier afin d’améliorer la compréhension de la dynamique des sols en milieux dunaires. Une vaste collecte de données sur le terrain a été réalisée sur une plaine de dunes reliques se trouvant aux Îles de la Madeleine, Qc. J’ai échantillonné plus de 80 sites répartis sur l’ensemble de ce système dunaire et caractérisé les champignons du sol grâce au séquençage à haut débit. Dans un premier temps, j’ai dressé un portait d’ensemble des communautés fongiques du sol à travers les différentes zones des dunes. En plus d’une description taxonomique, les modes de vie fongiques ont été prédits afin de mieux comprendre comment les variations au niveau des communautés de champignons du sol peuvent se traduire en changements fonctionnels. J’ai observé un niveau de diversité fongique élevé (plus de 3400 unités taxonomiques opérationnelles au total) et des communautés taxonomiquement et fonctionnellement distinctes à travers un gradient de succession et de conditions édaphiques. Ces résultats ont aussi indiqué que toutes les zones des dunes, incluant la zone pionière, supportent des communautés fongiques diversifiées. Ensuite, le lien entre les communautés végétales et fongiques a été étudié à travers l’ensemble de la séquence dunaire. Ces résultats ont montré une augmentation claire de la richesse spécifique végétale, ainsi qu’une augmentation de la diversité des stratégies d’acquisition de nutriments (traits souterrains lié à la nutrition des plantes, soit mycorhizien à arbuscule, ectomycorhizien, mycorhizien éricoide, fixateur d’azote ou non spécialisé). J’ai aussi pu établir une forte corrélation entre les champignons du sol et la végétation, qui semblent tous deux réagir de façon similaire aux conditions physicochimiques du sol. Le pH du sol influençait fortement les communautés végétales et fongiques. Le lien observé entre les communautés végétales et fongiques met l’emphase sur l’importance des interactions biotiques positives au fil de la succession dans les environnements pauvres en nutriments. Finalement, j’ai comparé les communautés de champignons ectomycorhiziens associées aux principales espèces arborescentes dans les forêts dunaires. J’ai observé une richesse importante, avec un total de 200 unités taxonomiques opérationnelles ectomycorhiziennes, appartenant principalement aux Agaricomycètes. Une analyse de réseaux n’a pas permis de détecter de modules (c'est-à-dire des sous-groupes d’espèces en interaction), ce qui indique un faible niveau de spécificité des associations ectomycorhiziennes. De plus, je n’ai pas observé de différences en termes de richesse ou de structure des communautés entre les quatre espèces hôtes. En conclusion, j’ai pu observer à travers la succession dunaire des communautés diversifiées et des structures distinctes selon la zone de la dune, tant chez les champignons que chez les plantes. La succession semble toutefois moins marquée au niveau des communautés fongiques, par rapport aux patrons observés chez les plantes. Ces résultats ont alimenté une réflexion sur le potentiel et les perspectives, mais aussi sur les limitations des approches reposant sur le séquençage à haut-débit en écologie microbienne.

Implication du domaine intracellulaire du précurseur de la protéine amyloïde dans la modulation de la plasticité synaptique

Alzheimer's disease is the most common type of dementia in the elderly; it is characterized by early deficits in learning and memory formation and ultimately leads to a generalised loss of higher cognitive functions. While amyloid beta (Aβ) and tau are traditionally associated with the development of Alzheimer disease, recent studies suggest that other factors, like the intracellular domain (APP-ICD) of the amyloid precursor protein (APP), could play a role. In this study, we investigated whether APP-ICD could affect synaptic transmission and synaptic plasticity in the hippocampus, which is involved in learning and memory processes. Our results indicated that overexpression of APP-ICD in hippocampal CA1 neurons leads to a decrease in evoked AMPA-receptor and NMDA-receptor dependent synaptic transmission. Our study demonstrated that this effect is specific for APP-ICD since its closest homologue APLP2-ICD did not reproduce this effect. In addition, APP-ICD blocks the induction of long term potentiation (LTP) and leads to increased of expression and facilitated induction of long term depression (LTD), while APLP2-ICD shows neither of these effects. Our study showed that this difference observed in synaptic transmission and plasticity between the two intracellular domains resides in the difference of one alanine in the APP-ICD versus a proline in the APLP2-ICD. Exchanging this critical amino-acid through point-mutation, we observed that APP(PAV)-ICD had no longer an effect on synaptic plasticity. We also demonstrated that APLP2(AAV)-ICD mimic the effect of APP-ICD in regards of facilitated LTD. Next we showed that the full length APP-APLP2-APP (APP with a substitution of the Aβ component for its homologous APLP2 part) had no effect on synaptic transmission or synaptic plasticity when compared to the APP-ICD. However, by activating caspase cleavage prior to induction of LTD or LTP, we observed an LTD facilitation and a block of LTP with APP-APLP2-APP, effects that were not seen with the full length APLP2 protein. APP is phosphorylated at threonine 668 (Thr668), which is localized directly after the aforementioned critical alanine and the caspase cleavage site in APP-APLP2-APP. Mutating this Thr668 for an alanine abolishes the effects on LTD and restores LTP induction. Finally, we showed that the facilitation of LTD with APP-APLP2-APP involves ryanodine receptor dependent calcium release from intracellular stores. Taken together, we propose the emergence of a new APP intracellular domain, which plays a critical role in the regulation of synaptic plasticity and by extension, could play a role in the development of memory loss in Alzheimer’s disease.

Algorithmique et complexité des systèmes à compteurs

Réalisé en cotutelle avec l'École normale supérieure de Cachan – Université Paris-Saclay