Tarification logit dans un réseau

Le problème de tarification qui nous intéresse ici consiste à maximiser le revenu généré par les usagers d'un réseau de transport. Pour se rendre à leurs destinations, les usagers font un choix de route et utilisent des arcs sur lesquels nous imposons des tarifs. Chaque route est caractérisée (aux yeux de l'usager) par sa "désutilité", une mesure de longueur généralisée tenant compte à la fois des tarifs et des autres coûts associés à son utilisation. Ce problème a surtout été abordé sous une modélisation déterministe de la demande selon laquelle seules des routes de désutilité minimale se voient attribuer une mesure positive de flot. Le modèle déterministe se prête bien à une résolution globale, mais pèche par manque de réalisme. Nous considérons ici une extension probabiliste de ce modèle, selon laquelle les usagers d'un réseau sont alloués aux routes d'après un modèle de choix discret logit. Bien que le problème de tarification qui en résulte est non linéaire et non convexe, il conserve néanmoins une forte composante combinatoire que nous exploitons à des fins algorithmiques. Notre contribution se répartit en trois articles. Dans le premier, nous abordons le problème d'un point de vue théorique pour le cas avec une paire origine-destination. Nous développons une analyse de premier ordre qui exploite les propriétés analytiques de l'affectation logit et démontrons la validité de règles de simplification de la topologie du réseau qui permettent de réduire la dimension du problème sans en modifier la solution. Nous établissons ensuite l'unimodalité du problème pour une vaste gamme de topologies et nous généralisons certains de nos résultats au problème de la tarification d'une ligne de produits. Dans le deuxième article, nous abordons le problème d'un point de vue numérique pour le cas avec plusieurs paires origine-destination. Nous développons des algorithmes qui exploitent l'information locale et la parenté des formulations probabilistes et déterministes. Un des résultats de notre analyse est l'obtention de bornes sur l'erreur commise par les modèles combinatoires dans l'approximation du revenu logit. Nos essais numériques montrent qu'une approximation combinatoire rudimentaire permet souvent d'identifier des solutions quasi-optimales. Dans le troisième article, nous considérons l'extension du problème à une demande hétérogène. L'affectation de la demande y est donnée par un modèle de choix discret logit mixte où la sensibilité au prix d'un usager est aléatoire. Sous cette modélisation, l'expression du revenu n'est pas analytique et ne peut être évaluée de façon exacte. Cependant, nous démontrons que l'utilisation d'approximations non linéaires et combinatoires permet d'identifier des solutions quasi-optimales. Finalement, nous en profitons pour illustrer la richesse du modèle, par le biais d'une interprétation économique, et examinons plus particulièrement la contribution au revenu des différents groupes d'usagers.

Probabilistic Assignments of Identical Indivisible Objects and Uniform Probabilistic Rules.

We consider a probabilistic approach to the problem of assigning k indivisible identical objects to a set of agents with single-peaked preferences. Using the ordinal extension of preferences, we characterize the class of uniform probabilistic rules by Pareto efficiency, strategy-proofness, and no-envy. We also show that in this characterization no-envy cannot be replaced by anonymity. When agents are strictly risk averse von-Neumann-Morgenstern utility maximizers, then we reduce the problem of assigning k identical objects to a problem of allocating the amount k of an infinitely divisible commodity.

Automata and men : the shift towards a human ideal in the fiction of Wyndham Lewis

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

Political Influence, Economic Interests and Endogenous Tax Structure in a Computable Equilibrium Framework: with Applicatioon to the United States, 1973 and 1983

A full understanding of public affairs requires the ability to distinguish between the policies that voters would like the government to adopt, and the influence that different voters or group of voters actually exert in the democratic process. We consider the properties of a computable equilibrium model of a competitive political economy in which the economic interests of groups of voters and their effective influence on equilibrium policy outcomes can be explicitly distinguished and computed. The model incorporates an amended version of the GEMTAP tax model, and is calibrated to data for the United States for 1973 and 1983. Emphasis is placed on how the aggregation of GEMTAP households into groups within which economic and political behaviour is assumed homogeneous affects the numerical representation of interests and influence for representative members of each group. Experiments with the model suggest that the changes in both interests and influence are important parts of the story behind the evolution of U.S. tax policy in the decade after 1973.

Heterotachy and long-branch attraction in phylogenetics

Affiliation: Département de Biochimie, Faculté de médecine, Université de Montréal

Macroemesures in Computable General Equilibrium Models: a Probabilistic Treatment with an Application to Morocco.

With the help of an illustrative general equilibrium (CGE) model of the Moroccan Economy, we test for the significance of simulation results in the case where the exact macromesure is not known with certainty. This is done by computing lower and upper bounds for the simulation resukts, given a priori probabilities attached to three possible closures (Classical, Johansen, Keynesian). Our Conclusion is that, when there is uncertainty on closures several endogenous changes lack significance, which, in turn, limit the use of the model for policy prescriptions.

The roles of the somatosensory cortices in the perception of noxious and innocuous stimuli

Résumé Les premières études électrophysiologiques et anatomiques ont établi le rôle crucial du cortex somatosensoriel primaire et secondaire (SI et SII) dans le traitement de l'information somatosensorielle. Toutefois, les récentes avancées en techniques d’imagerie cérébrale ont mis en question leur rôle dans la perception somatosensorielle. La réorganisation du cortex somatosensoriel est un phénomène qui a été proposé comme cause de la douleur du membre fantôme chez les individus amputés. Comme la plupart des études se sont concentrées sur le rôle du SI, une étude plus approfondie est nécessaire. La présente série d'expériences implique une exploration du rôle des régions somatosensorielles dans la perception des stimuli douleureux et non-douleureux chez des volontaires sains et patients avec des douleurs de membre fantôme. La première étude expérimentale présentée dans le chapitre 3 est une méta-analyse des études de neuro-imagerie employant des stimuli nociceptifs chez des volontaires sains. En comparaison aux précédentes, la présente étude permet la génération de cartes quantitatives probabilistes permettant la localisation des régions activées en réponse à des stimuli nociceptifs. Le rôle du cortex somatosensoriel dans la perception consciente de stimuli chauds a été étudié dans le chapitre 4 grâce à une étude d'imagerie par résonance magnétique fonctionnelle, dans laquelle des stimuli thermiques douloureux et non-douloureux ont été administrés de manière contrebalancée. Grâce à cette procédure, la perception de la chaleur fut atténuée par les stimuli douloureux, ce qui permit la comparaison des stimuli consciemment perçus avec ceux qui ne le furent pas. Les résultats ont montrés que les stimulations chaudes perçues ont engendré l’activation de l’aire SI controlatérale, ainsi que de la région SII. Grâce à l’évaluation clinique de patients amputés présentant une altération de leurs perceptions somatosensorielles, il est également possible de dessiner un aperçu des régions corticales qui sous-tendent ces modifications perceptuelles. Dans le chapitre 5 nous avons émis l'hypothèse proposant que les sensations du membre fantôme représentent un corrélat perceptuel de la réorganisation somatotopique des représentations sensorielles corticales. En effet, la réorganisation des sensations peut donner des indices sur les régions impliquées dans la genèse des sensations référées. Ainsi, un protocole d’évaluation sensoriel a été administré à un groupe de patients affligés de douleur au niveau du membre fantôme. Les résultats ont montré que, contrairement aux études précédentes, les sensations diffèrent grandement selon le type et l'intensité des stimuli tactiles, sans évidence de la présence d’un modèle spatialement localisé. Toutefois, les résultats actuels suggèrent que les régions corticales à champs récepteurs bilatéraux présentent également des modifications en réponse à une déafférentation. Ces études présentent une nouvelle image des régions corticales impliquées dans la perception des stimuli somatosensoriels, lesquelles comprennent les aires SI et SII, ainsi que l'insula. Les résultats sont pertinents à notre compréhension des corrélats neurologiques de la perception somatosensorielle consciente.

Eye disease and mobility limitations in older adults

Objectif: Évaluer les défis de la mobilité chez les personnes âgées atteintes de dégénérescence maculaire reliée à l’âge (DMLA), de glaucome ou de dystrophie cornéenne de Fuchs et les comparer avec les personnes âgées n’ayant pas de maladie oculaire. Devis: Étude transversale de population hospitalière Participants: 253 participants (61 avec la DMLA, 45 avec la dystrophie cornéenne de Fuchs, 79 avec le glaucome et 68 contrôles) Méthodes: Nous avons recruté les patients parmi ceux qui se font soigner dans les cliniques d’ophtalmologie de l’Hôpital Maisonneuve-Rosemont (Montréal, Canada) de septembre 2009 à octobre 2010. Les patients atteints de la DMLA ou de la maladie de Fuchs ont une acuité visuelle inférieure à 20/40 dans les deux yeux, tandis que les patients avec du glaucome ont un champ visuel dans le pire oeil inférieur ou égal à -4dB. Les patients contrôles, qui ont été recrutés à partir des mêmes cliniques, ont une acuité visuelle et un champ visuel normaux. Nous avons colligé des données concernant la mobilité à partir des questionnaires (aire de mobilité et chutes) et des tests (test de l’équilibre monopodal, timed Up and Go (TUG) test). Pour mesurer la fonction visuelle nous avons mesuré l’acuité visuelle, la sensibilité au contraste et le champ visuel. Nous avons également révisé le dossier médical. Pour les analyses statistiques nous avons utilisé les régressions linéaire et logistique. Critères de jugement principaux: aire de mobilité, équilibre, test timed Up and Go, chutes Résultats: Les trois maladies oculaires ont été associées à des patrons différents de limitation de la mobilité. Les patients atteints de glaucome ont eu le type le plus sévère de restriction de mobilité; ils ont une aire de mobilité plus réduite, des scores plus bas au test TUG et ils sont plus enclins à avoir un équilibre faible et à faire plus de chutes que les contrôles (p < 0.05). De plus, comparativement aux contrôles, les patients ayant de la DMLA ou la dystrophie cornéenne de Fuchs ont eu une aire de mobilité réduite (p < 0.05). Les chutes n’ont pas été associées aux maladies oculaires dans cette étude. Conclusions: Nos résultats suggèrent que les maladies oculaires, et surtout le glaucome, limitent la mobilité chez les personnes âgées. De futures études sont nécessaires pour évaluer l’impact d’une mobilité restreinte chez cette population pour pouvoir envisager des interventions ciblées qui pourraient les aider à maintenir leur indépendance le plus longtemps possible.

David Hume on probability and the Gambler’s fallacy

Cette présentation examinera le degré de certitude qui peut être atteint dans le domaine scientifique. Le paradigme scientifique est composé de deux extrêmes; causalité et déterminisme d'un côté et probabilité et indéterminisme de l'autre. En faisant appel aux notions de Hume de la ressemblance et la contiguïté, on peut rejeter la causalité ou le hasard objectif comme étant sans fondement et non empirique. Le problème de l'induction et le sophisme du parieur proviennent d’une même source cognitif / heuristique. Hume décrit ces tendances mentales dans ses essais « Of Probability » et « Of the Idea of Necessary Connexion ». Une discussion sur la conception de la probabilité de Hume ainsi que d'autres interprétations de probabilité sera nécessaire. Même si la science glorifie et idéalise la causalité, la probabilité peut être comprise comme étant tout aussi cohérente. Une attitude probabiliste, même si elle est également non empirique, pourrait être plus avantageuse que le vieux paradigme de la causalité.

Automates à contraintes semilinéaires = Automata with a semilinear constraint

Cette thèse présente une étude dans divers domaines de l'informatique théorique de modèles de calculs combinant automates finis et contraintes arithmétiques. Nous nous intéressons aux questions de décidabilité, d'expressivité et de clôture, tout en ouvrant l'étude à la complexité, la logique, l'algèbre et aux applications. Cette étude est présentée au travers de quatre articles de recherche. Le premier article, Affine Parikh Automata, poursuit l'étude de Klaedtke et Ruess des automates de Parikh et en définit des généralisations et restrictions. L'automate de Parikh est un point de départ de cette thèse; nous montrons que ce modèle de calcul est équivalent à l'automate contraint que nous définissons comme un automate qui n'accepte un mot que si le nombre de fois que chaque transition est empruntée répond à une contrainte arithmétique. Ce modèle est naturellement étendu à l'automate de Parikh affine qui effectue une opération affine sur un ensemble de registres lors du franchissement d'une transition. Nous étudions aussi l'automate de Parikh sur lettres: un automate qui n'accepte un mot que si le nombre de fois que chaque lettre y apparaît répond à une contrainte arithmétique. Le deuxième article, Bounded Parikh Automata, étudie les langages bornés des automates de Parikh. Un langage est borné s'il existe des mots w_1, w_2, ..., w_k tels que chaque mot du langage peut s'écrire w_1...w_1w_2...w_2...w_k...w_k. Ces langages sont importants dans des domaines applicatifs et présentent usuellement de bonnes propriétés théoriques. Nous montrons que dans le contexte des langages bornés, le déterminisme n'influence pas l'expressivité des automates de Parikh. Le troisième article, Unambiguous Constrained Automata, introduit les automates contraints non ambigus, c'est-à-dire pour lesquels il n'existe qu'un chemin acceptant par mot reconnu par l'automate. Nous montrons qu'il s'agit d'un modèle combinant une meilleure expressivité et de meilleures propriétés de clôture que l'automate contraint déterministe. Le problème de déterminer si le langage d'un automate contraint non ambigu est régulier est montré décidable. Le quatrième article, Algebra and Complexity Meet Contrained Automata, présente une étude des représentations algébriques qu'admettent les automates contraints et les automates de Parikh affines. Nous déduisons de ces caractérisations des résultats d'expressivité et de complexité. Nous montrons aussi que certaines hypothèses classiques en complexité computationelle sont reliées à des résultats de séparation et de non clôture dans les automates de Parikh affines. La thèse est conclue par une ouverture à un possible approfondissement, au travers d'un certain nombre de problèmes ouverts.

Does Chance hide Necessity? : a reevaluation of the debate ‘determinism - indeterminism’ in the light of quantum mechanics and probability theory

Dans cette thèse l’ancienne question philosophique “tout événement a-t-il une cause ?” sera examinée à la lumière de la mécanique quantique et de la théorie des probabilités. Aussi bien en physique qu’en philosophie des sciences la position orthodoxe maintient que le monde physique est indéterministe. Au niveau fondamental de la réalité physique – au niveau quantique – les événements se passeraient sans causes, mais par chance, par hasard ‘irréductible’. Le théorème physique le plus précis qui mène à cette conclusion est le théorème de Bell. Ici les prémisses de ce théorème seront réexaminées. Il sera rappelé que d’autres solutions au théorème que l’indéterminisme sont envisageables, dont certaines sont connues mais négligées, comme le ‘superdéterminisme’. Mais il sera argué que d’autres solutions compatibles avec le déterminisme existent, notamment en étudiant des systèmes physiques modèles. Une des conclusions générales de cette thèse est que l’interprétation du théorème de Bell et de la mécanique quantique dépend crucialement des prémisses philosophiques desquelles on part. Par exemple, au sein de la vision d’un Spinoza, le monde quantique peut bien être compris comme étant déterministe. Mais il est argué qu’aussi un déterminisme nettement moins radical que celui de Spinoza n’est pas éliminé par les expériences physiques. Si cela est vrai, le débat ‘déterminisme – indéterminisme’ n’est pas décidé au laboratoire : il reste philosophique et ouvert – contrairement à ce que l’on pense souvent. Dans la deuxième partie de cette thèse un modèle pour l’interprétation de la probabilité sera proposé. Une étude conceptuelle de la notion de probabilité indique que l’hypothèse du déterminisme aide à mieux comprendre ce que c’est qu’un ‘système probabiliste’. Il semble que le déterminisme peut répondre à certaines questions pour lesquelles l’indéterminisme n’a pas de réponses. Pour cette raison nous conclurons que la conjecture de Laplace – à savoir que la théorie des probabilités présuppose une réalité déterministe sous-jacente – garde toute sa légitimité. Dans cette thèse aussi bien les méthodes de la philosophie que de la physique seront utilisées. Il apparaît que les deux domaines sont ici solidement reliés, et qu’ils offrent un vaste potentiel de fertilisation croisée – donc bidirectionnelle.

Improving sampling, optimization and feature extraction in Boltzmann machines

L’apprentissage supervisé de réseaux hiérarchiques à grande échelle connaît présentement un succès fulgurant. Malgré cette effervescence, l’apprentissage non-supervisé représente toujours, selon plusieurs chercheurs, un élément clé de l’Intelligence Artificielle, où les agents doivent apprendre à partir d’un nombre potentiellement limité de données. Cette thèse s’inscrit dans cette pensée et aborde divers sujets de recherche liés au problème d’estimation de densité par l’entremise des machines de Boltzmann (BM), modèles graphiques probabilistes au coeur de l’apprentissage profond. Nos contributions touchent les domaines de l’échantillonnage, l’estimation de fonctions de partition, l’optimisation ainsi que l’apprentissage de représentations invariantes. Cette thèse débute par l’exposition d’un nouvel algorithme d'échantillonnage adaptatif, qui ajuste (de fa ̧con automatique) la température des chaînes de Markov sous simulation, afin de maintenir une vitesse de convergence élevée tout au long de l’apprentissage. Lorsqu’utilisé dans le contexte de l’apprentissage par maximum de vraisemblance stochastique (SML), notre algorithme engendre une robustesse accrue face à la sélection du taux d’apprentissage, ainsi qu’une meilleure vitesse de convergence. Nos résultats sont présent ́es dans le domaine des BMs, mais la méthode est générale et applicable à l’apprentissage de tout modèle probabiliste exploitant l’échantillonnage par chaînes de Markov. Tandis que le gradient du maximum de vraisemblance peut-être approximé par échantillonnage, l’évaluation de la log-vraisemblance nécessite un estimé de la fonction de partition. Contrairement aux approches traditionnelles qui considèrent un modèle donné comme une boîte noire, nous proposons plutôt d’exploiter la dynamique de l’apprentissage en estimant les changements successifs de log-partition encourus à chaque mise à jour des paramètres. Le problème d’estimation est reformulé comme un problème d’inférence similaire au filtre de Kalman, mais sur un graphe bi-dimensionnel, où les dimensions correspondent aux axes du temps et au paramètre de température. Sur le thème de l’optimisation, nous présentons également un algorithme permettant d’appliquer, de manière efficace, le gradient naturel à des machines de Boltzmann comportant des milliers d’unités. Jusqu’à présent, son adoption était limitée par son haut coût computationel ainsi que sa demande en mémoire. Notre algorithme, Metric-Free Natural Gradient (MFNG), permet d’éviter le calcul explicite de la matrice d’information de Fisher (et son inverse) en exploitant un solveur linéaire combiné à un produit matrice-vecteur efficace. L’algorithme est prometteur: en terme du nombre d’évaluations de fonctions, MFNG converge plus rapidement que SML. Son implémentation demeure malheureusement inefficace en temps de calcul. Ces travaux explorent également les mécanismes sous-jacents à l’apprentissage de représentations invariantes. À cette fin, nous utilisons la famille de machines de Boltzmann restreintes “spike & slab” (ssRBM), que nous modifions afin de pouvoir modéliser des distributions binaires et parcimonieuses. Les variables latentes binaires de la ssRBM peuvent être rendues invariantes à un sous-espace vectoriel, en associant à chacune d’elles, un vecteur de variables latentes continues (dénommées “slabs”). Ceci se traduit par une invariance accrue au niveau de la représentation et un meilleur taux de classification lorsque peu de données étiquetées sont disponibles. Nous terminons cette thèse sur un sujet ambitieux: l’apprentissage de représentations pouvant séparer les facteurs de variations présents dans le signal d’entrée. Nous proposons une solution à base de ssRBM bilinéaire (avec deux groupes de facteurs latents) et formulons le problème comme l’un de “pooling” dans des sous-espaces vectoriels complémentaires.