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.

Cogestion des ressources naturelles : une approche structurale pour quantifier la contribution des réseaux d'acteurs à la résilience des systèmes socio-écologiques

Alors que les activités anthropiques font basculer de nombreux écosystèmes vers des régimes fonctionnels différents, la résilience des systèmes socio-écologiques devient un problème pressant. Des acteurs locaux, impliqués dans une grande diversité de groupes — allant d’initiatives locales et indépendantes à de grandes institutions formelles — peuvent agir sur ces questions en collaborant au développement, à la promotion ou à l’implantation de pratiques plus en accord avec ce que l’environnement peut fournir. De ces collaborations répétées émergent des réseaux complexes, et il a été montré que la topologie de ces réseaux peut améliorer la résilience des systèmes socio-écologiques (SSÉ) auxquels ils participent. La topologie des réseaux d’acteurs favorisant la résilience de leur SSÉ est caractérisée par une combinaison de plusieurs facteurs : la structure doit être modulaire afin d’aider les différents groupes à développer et proposer des solutions à la fois plus innovantes (en réduisant l’homogénéisation du réseau), et plus proches de leurs intérêts propres ; elle doit être bien connectée et facilement synchronisable afin de faciliter les consensus, d’augmenter le capital social, ainsi que la capacité d’apprentissage ; enfin, elle doit être robuste, afin d’éviter que les deux premières caractéristiques ne souffrent du retrait volontaire ou de la mise à l’écart de certains acteurs. Ces caractéristiques, qui sont relativement intuitives à la fois conceptuellement et dans leur application mathématique, sont souvent employées séparément pour analyser les qualités structurales de réseaux d’acteurs empiriques. Cependant, certaines sont, par nature, incompatibles entre elles. Par exemple, le degré de modularité d’un réseau ne peut pas augmenter au même rythme que sa connectivité, et cette dernière ne peut pas être améliorée tout en améliorant sa robustesse. Cet obstacle rend difficile la création d’une mesure globale, car le niveau auquel le réseau des acteurs contribue à améliorer la résilience du SSÉ ne peut pas être la simple addition des caractéristiques citées, mais plutôt le résultat d’un compromis subtil entre celles-ci. Le travail présenté ici a pour objectifs (1), d’explorer les compromis entre ces caractéristiques ; (2) de proposer une mesure du degré auquel un réseau empirique d’acteurs contribue à la résilience de son SSÉ ; et (3) d’analyser un réseau empirique à la lumière, entre autres, de ces qualités structurales. Cette thèse s’articule autour d’une introduction et de quatre chapitres numérotés de 2 à 5. Le chapitre 2 est une revue de la littérature sur la résilience des SSÉ. Il identifie une série de caractéristiques structurales (ainsi que les mesures de réseaux qui leur correspondent) liées à l’amélioration de la résilience dans les SSÉ. Le chapitre 3 est une étude de cas sur la péninsule d’Eyre, une région rurale d’Australie-Méridionale où l’occupation du sol, ainsi que les changements climatiques, contribuent à l’érosion de la biodiversité. Pour cette étude de cas, des travaux de terrain ont été effectués en 2010 et 2011 durant lesquels une série d’entrevues a permis de créer une liste des acteurs de la cogestion de la biodiversité sur la péninsule. Les données collectées ont été utilisées pour le développement d’un questionnaire en ligne permettant de documenter les interactions entre ces acteurs. Ces deux étapes ont permis la reconstitution d’un réseau pondéré et dirigé de 129 acteurs individuels et 1180 relations. Le chapitre 4 décrit une méthodologie pour mesurer le degré auquel un réseau d’acteurs participe à la résilience du SSÉ dans lequel il est inclus. La méthode s’articule en deux étapes : premièrement, un algorithme d’optimisation (recuit simulé) est utilisé pour fabriquer un archétype semi-aléatoire correspondant à un compromis entre des niveaux élevés de modularité, de connectivité et de robustesse. Deuxièmement, un réseau empirique (comme celui de la péninsule d’Eyre) est comparé au réseau archétypique par le biais d’une mesure de distance structurelle. Plus la distance est courte, et plus le réseau empirique est proche de sa configuration optimale. La cinquième et dernier chapitre est une amélioration de l’algorithme de recuit simulé utilisé dans le chapitre 4. Comme il est d’usage pour ce genre d’algorithmes, le recuit simulé utilisé projetait les dimensions du problème multiobjectif dans une seule dimension (sous la forme d’une moyenne pondérée). Si cette technique donne de très bons résultats ponctuellement, elle n’autorise la production que d’une seule solution parmi la multitude de compromis possibles entre les différents objectifs. Afin de mieux explorer ces compromis, nous proposons un algorithme de recuit simulé multiobjectifs qui, plutôt que d’optimiser une seule solution, optimise une surface multidimensionnelle de solutions. Cette étude, qui se concentre sur la partie sociale des systèmes socio-écologiques, améliore notre compréhension des structures actorielles qui contribuent à la résilience des SSÉ. Elle montre que si certaines caractéristiques profitables à la résilience sont incompatibles (modularité et connectivité, ou — dans une moindre mesure — connectivité et robustesse), d’autres sont plus facilement conciliables (connectivité et synchronisabilité, ou — dans une moindre mesure — modularité et robustesse). Elle fournit également une méthode intuitive pour mesurer quantitativement des réseaux d’acteurs empiriques, et ouvre ainsi la voie vers, par exemple, des comparaisons d’études de cas, ou des suivis — dans le temps — de réseaux d’acteurs. De plus, cette thèse inclut une étude de cas qui fait la lumière sur l’importance de certains groupes institutionnels pour la coordination des collaborations et des échanges de connaissances entre des acteurs aux intérêts potentiellement divergents.

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.

Algorithme de branch-and-price-and-cut pour le problème de conception de réseaux avec coûts fixes, capacités et un seul produit

De nombreux problèmes liés aux domaines du transport, des télécommunications et de la logistique peuvent être modélisés comme des problèmes de conception de réseaux. Le problème classique consiste à transporter un flot (données, personnes, produits, etc.) sur un réseau sous un certain nombre de contraintes dans le but de satisfaire la demande, tout en minimisant les coûts. Dans ce mémoire, on se propose d'étudier le problème de conception de réseaux avec coûts fixes, capacités et un seul produit, qu'on transforme en un problème équivalent à plusieurs produits de façon à améliorer la valeur de la borne inférieure provenant de la relaxation continue du modèle. La méthode que nous présentons pour la résolution de ce problème est une méthode exacte de branch-and-price-and-cut avec une condition d'arrêt, dans laquelle nous exploitons à la fois la méthode de génération de colonnes, la méthode de génération de coupes et l'algorithme de branch-and-bound. Ces méthodes figurent parmi les techniques les plus utilisées en programmation linéaire en nombres entiers. Nous testons notre méthode sur deux groupes d'instances de tailles différentes (gran-des et très grandes), et nous la comparons avec les résultats donnés par CPLEX, un des meilleurs logiciels permettant de résoudre des problèmes d'optimisation mathématique, ainsi qu’avec une méthode de branch-and-cut. Il s'est avéré que notre méthode est prometteuse et peut donner de bons résultats, en particulier pour les instances de très grandes tailles.

Investigating the encoding of visual stimuli by forming neural circuits in the cat primary visual cortex

Contexte La connectomique, ou la cartographie des connexions neuronales, est un champ de recherche des neurosciences évoluant rapidement, promettant des avancées majeures en ce qui concerne la compréhension du fonctionnement cérébral. La formation de circuits neuronaux en réponse à des stimuli environnementaux est une propriété émergente du cerveau. Cependant, la connaissance que nous avons de la nature précise de ces réseaux est encore limitée. Au niveau du cortex visuel, qui est l’aire cérébrale la plus étudiée, la manière dont les informations se transmettent de neurone en neurone est une question qui reste encore inexplorée. Cela nous invite à étudier l’émergence des microcircuits en réponse aux stimuli visuels. Autrement dit, comment l’interaction entre un stimulus et une assemblée cellulaire est-elle mise en place et modulée? Méthodes En réponse à la présentation de grilles sinusoïdales en mouvement, des ensembles neuronaux ont été enregistrés dans la couche II/III (aire 17) du cortex visuel primaire de chats anesthésiés, à l’aide de multi-électrodes en tungstène. Des corrélations croisées ont été effectuées entre l’activité de chacun des neurones enregistrés simultanément pour mettre en évidence les liens fonctionnels de quasi-synchronie (fenêtre de ± 5 ms sur les corrélogrammes croisés corrigés). Ces liens fonctionnels dévoilés indiquent des connexions synaptiques putatives entre les neurones. Par la suite, les histogrammes peri-stimulus (PSTH) des neurones ont été comparés afin de mettre en évidence la collaboration synergique temporelle dans les réseaux fonctionnels révélés. Enfin, des spectrogrammes dépendants du taux de décharges entre neurones ou stimulus-dépendants ont été calculés pour observer les oscillations gamma dans les microcircuits émergents. Un indice de corrélation (Rsc) a également été calculé pour les neurones connectés et non connectés. Résultats Les neurones liés fonctionnellement ont une activité accrue durant une période de 50 ms contrairement aux neurones fonctionnellement non connectés. Cela suggère que les connexions entre neurones mènent à une synergie de leur inter-excitabilité. En outre, l’analyse du spectrogramme dépendant du taux de décharge entre neurones révèle que les neurones connectés ont une plus forte activité gamma que les neurones non connectés durant une fenêtre d’opportunité de 50ms. L’activité gamma de basse-fréquence (20-40 Hz) a été associée aux neurones à décharge régulière (RS) et l’activité de haute fréquence (60-80 Hz) aux neurones à décharge rapide (FS). Aussi, les neurones fonctionnellement connectés ont systématiquement un Rsc plus élevé que les neurones non connectés. Finalement, l’analyse des corrélogrammes croisés révèle que dans une assemblée neuronale, le réseau fonctionnel change selon l’orientation de la grille. Nous démontrons ainsi que l’intensité des relations fonctionnelles dépend de l’orientation de la grille sinusoïdale. Cette relation nous a amené à proposer l’hypothèse suivante : outre la sélectivité des neurones aux caractères spécifiques du stimulus, il y a aussi une sélectivité du connectome. En bref, les réseaux fonctionnels «signature » sont activés dans une assemblée qui est strictement associée à l’orientation présentée et plus généralement aux propriétés des stimuli. Conclusion Cette étude souligne le fait que l’assemblée cellulaire, plutôt que le neurone, est l'unité fonctionnelle fondamentale du cerveau. Cela dilue l'importance du travail isolé de chaque neurone, c’est à dire le paradigme classique du taux de décharge qui a été traditionnellement utilisé pour étudier l'encodage des stimuli. Cette étude contribue aussi à faire avancer le débat sur les oscillations gamma, en ce qu'elles surviennent systématiquement entre neurones connectés dans les assemblées, en conséquence d’un ajout de cohérence. Bien que la taille des assemblées enregistrées soit relativement faible, cette étude suggère néanmoins une intrigante spécificité fonctionnelle entre neurones interagissant dans une assemblée en réponse à une stimulation visuelle. Cette étude peut être considérée comme une prémisse à la modélisation informatique à grande échelle de connectomes fonctionnels.

Identification des grands utilisateurs de soins de santé chez les patients souffrant de la douleur chronique non cancéreuse et suivis en soins de première ligne

Contexte: La douleur chronique non cancéreuse (DCNC) génère des retombées économiques et sociétales importantes. L’identification des patients à risque élevé d’être de grands utilisateurs de soins de santé pourrait être d’une grande utilité; en améliorant leur prise en charge, il serait éventuellement possible de réduire leurs coûts de soins de santé. Objectif: Identifier les facteurs prédictifs bio-psycho-sociaux des grands utilisateurs de soins de santé chez les patients souffrant de DCNC et suivis en soins de première ligne. Méthodologie: Des patients souffrant d’une DCNC modérée à sévère depuis au moins six mois et bénéficiant une ordonnance valide d’un analgésique par un médecin de famille ont été recrutés dans des pharmacies communautaires du territoire du Réseau universitaire intégré de santé (RUIS), de l’Université de Montréal entre Mai 2009 et Janvier 2010. Ce dernier est composé des six régions suivantes : Mauricie et centre du Québec, Laval, Montréal, Laurentides, Lanaudière et Montérégie. Les caractéristiques bio-psycho-sociales des participants ont été documentées à l’aide d’un questionnaire écrit et d’une entrevue téléphonique au moment du recrutement. Les coûts directs de santé ont été estimés à partir des soins et des services de santé reçus au cours de l’année précédant et suivant le recrutement et identifiés à partir de la base de données de la Régie d’Assurance maladie du Québec, RAMQ (assureur publique de la province du Québec). Ces coûts incluaient ceux des hospitalisations reliées à la douleur, des visites à l’urgence, des soins ambulatoires et de la médication prescrite pour le traitement de la douleur et la gestion des effets secondaires des analgésiques. Les grands utilisateurs des soins de santé ont été définis comme étant ceux faisant partie du quartile le plus élevé de coûts directs annuels en soins de santé dans l’année suivant le recrutement. Des modèles de régression logistique multivariés et le critère d’information d’Akaike ont permis d’identifier les facteurs prédictifs des coûts directs élevés en soins de santé. Résultats: Le coût direct annuel médian en soins de santé chez les grands utilisateurs de soins de santé (63 patients) était de 7 627 CAD et de 1 554 CAD pour les utilisateurs réguliers (188 patients). Le modèle prédictif final du risque d’être un grand utilisateur de soins de santé incluait la douleur localisée au niveau des membres inférieurs (OR = 3,03; 95% CI: 1,20 - 7,65), la réduction de la capacité fonctionnelle liée à la douleur (OR = 1,24; 95% CI: 1,03 - 1,48) et les coûts directs en soins de santé dans l’année précédente (OR = 17,67; 95% CI: 7,90 - 39,48). Les variables «sexe», «comorbidité», «dépression» et «attitude envers la guérison médicale» étaient également retenues dans le modèle prédictif final. Conclusion: Les patients souffrant d’une DCNC au niveau des membres inférieurs et présentant une détérioration de la capacité fonctionnelle liée à la douleur comptent parmi ceux les plus susceptibles d’être de grands utilisateurs de soins et de services. Le coût direct en soins de santé dans l’année précédente était également un facteur prédictif important. Améliorer la prise en charge chez cette catégorie de patients pourrait influencer favorablement leur état de santé et par conséquent les coûts assumés par le système de santé.

Processus de traduction et institutionnalisation d’outils de régulation basés sur les connaissances dans l’enseignement primaire en Belgique.

Depuis une quinzaine d’années, on assiste en Belgique francophone au développement d’une politique d’évaluation externe des écoles. Notre étude analyse la réception de cette politique par les acteurs locaux (directeurs et enseignants d’écoles primaires) et intermédiaires (inspecteurs) et montre comment les outils de régulation basés sur les connaissances mis en place par ces acteurs affectent la réception et la légitimité de la politique d’évaluation dans son ensemble. À l’aide de la sociologie de la traduction (Callon & Latour) et de la théorie néoinstitutionnaliste, nous comparons deux modes de construction et de mise en oeuvre de cette politique dans deux zones d’inspection. Dans la première, le dispositif repose pour l’essentiel sur la bureaucratie, tandis que dans la seconde la politique est construite par un réseau d’acteurs locaux et intermédiaires. Nous montrons que 1) les rôles et les stratégies des acteurs intermédiaires diffèrent considérablement ; 2) les différences constatées dans la construction de la politique d’évaluation (co-construction des outils par un réseau d’acteurs intermédiaires d’un côté, mise en oeuvre hiérarchique et bureaucratique de l’autre) sont liées aux différents effets des outils de régulation sur les pratiques des enseignants et sur la légitimité de cette politique.

Weighted finite-state transducers in speech recognition : a compaction algorithm for non-determinizable transducers

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

Routing and dimensioning of 3G multi-service networks

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

Understanding retargeting compilation techniques for network processors

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

Les groupes simples de Conway

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

The practice of memory in hypertext wor(l)ds

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

L'herbier du souffleur : critique phonostylistique de la prolation dramatique

Un document accompagne la thèse et est disponible pour consultation au Centre de conservation des bibliothèques de l'Université de Montréal (http://www.bib.umontreal.ca/conservation/).

Au-delà de la textualité : l'hyper[texte] comme médium

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

La santé mentale des adolescents québécois : quel rôle pour les omnipraticiens ?

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