The Ghost in the Machine: Inferring Machine-Based Strategies from Observed Behavior

We introduce a procedure to infer the repeated-game strategies that generate actions in experimental choice data. We apply the technique to set of experiments where human subjects play a repeated Prisoner's Dilemma. The technique suggests that two types of strategies underly the data.

Bundling under the Threat of Parallel Trade

This paper examines the use of bundling by a firm that sells in two national markets and faces entry by parallel traders. The firm can bundle its main product, - a tradable good- with a non-traded service. It chooses between the strategies of pure bundling, mixed bundling and no bundling. The paper shows that in the low-price country the threat of grey trade elicits a move from mixed bundling, or no bundling, towards pure bundling. It encourages a move from pure bundling towards mixes bundling or no bundling in the high-price country. The set of parameter values for which the profit maximizing strategy is not to supply the low price country is smaller than in the absence of bundling. The welfare effects of deterrence of grey trade are not those found in conventional models of price arbitrage. Some consumers in the low-price country may gain from the threat of entry by parallel traders although they pay a higher price. This is due to the fact that the firm responds to the threat of arbitrageurs by increasing the amount of services it puts in the bundle targeted at consumers in that country. Similarly, the threat of parallel trade may affect some consumers in the hight-price country adversely.

Sequential Machine learning Approaches for Portfolio Management

Cette thèse envisage un ensemble de méthodes permettant aux algorithmes d'apprentissage statistique de mieux traiter la nature séquentielle des problèmes de gestion de portefeuilles financiers. Nous débutons par une considération du problème général de la composition d'algorithmes d'apprentissage devant gérer des tâches séquentielles, en particulier celui de la mise-à-jour efficace des ensembles d'apprentissage dans un cadre de validation séquentielle. Nous énumérons les desiderata que des primitives de composition doivent satisfaire, et faisons ressortir la difficulté de les atteindre de façon rigoureuse et efficace. Nous poursuivons en présentant un ensemble d'algorithmes qui atteignent ces objectifs et présentons une étude de cas d'un système complexe de prise de décision financière utilisant ces techniques. Nous décrivons ensuite une méthode générale permettant de transformer un problème de décision séquentielle non-Markovien en un problème d'apprentissage supervisé en employant un algorithme de recherche basé sur les K meilleurs chemins. Nous traitons d'une application en gestion de portefeuille où nous entraînons un algorithme d'apprentissage à optimiser directement un ratio de Sharpe (ou autre critère non-additif incorporant une aversion au risque). Nous illustrons l'approche par une étude expérimentale approfondie, proposant une architecture de réseaux de neurones spécialisée à la gestion de portefeuille et la comparant à plusieurs alternatives. Finalement, nous introduisons une représentation fonctionnelle de séries chronologiques permettant à des prévisions d'être effectuées sur un horizon variable, tout en utilisant un ensemble informationnel révélé de manière progressive. L'approche est basée sur l'utilisation des processus Gaussiens, lesquels fournissent une matrice de covariance complète entre tous les points pour lesquels une prévision est demandée. Cette information est utilisée à bon escient par un algorithme qui transige activement des écarts de cours (price spreads) entre des contrats à terme sur commodités. L'approche proposée produit, hors échantillon, un rendement ajusté pour le risque significatif, après frais de transactions, sur un portefeuille de 30 actifs.

Multi-Prover and parallel repetition in non-classical interactive games

Depuis l’introduction de la mécanique quantique, plusieurs mystères de la nature ont trouvé leurs explications. De plus en plus, les concepts de la mécanique quantique se sont entremêlés avec d’autres de la théorie de la complexité du calcul. De nouvelles idées et solutions ont été découvertes et élaborées dans le but de résoudre ces problèmes informatiques. En particulier, la mécanique quantique a secoué plusieurs preuves de sécurité de protocoles classiques. Dans ce m´emoire, nous faisons un étalage de résultats récents de l’implication de la mécanique quantique sur la complexité du calcul, et cela plus précisément dans le cas de classes avec interaction. Nous présentons ces travaux de recherches avec la nomenclature des jeux à information imparfaite avec coopération. Nous exposons les différences entre les théories classiques, quantiques et non-signalantes et les démontrons par l’exemple du jeu à cycle impair. Nous centralisons notre attention autour de deux grands thèmes : l’effet sur un jeu de l’ajout de joueurs et de la répétition parallèle. Nous observons que l’effet de ces modifications a des conséquences très différentes en fonction de la théorie physique considérée.

Configuration et exploitation d'une machine émotionnelle

Dans ce travail, nous explorons la faisabilité de doter les machines de la capacité de prédire, dans un contexte d'interaction homme-machine (IHM), l'émotion d'un utilisateur, ainsi que son intensité, de manière instantanée pour une grande variété de situations. Plus spécifiquement, une application a été développée, appelée machine émotionnelle, capable de «comprendre» la signification d'une situation en se basant sur le modèle théorique d'évaluation de l'émotion Ortony, Clore et Collins (OCC). Cette machine est apte, également, à prédire les réactions émotionnelles des utilisateurs, en combinant des versions améliorées des k plus proches voisins et des réseaux de neurones. Une procédure empirique a été réalisée pour l'acquisition des données. Ces dernières ont fourni une connaissance consistante aux algorithmes d'apprentissage choisis et ont permis de tester la performance de la machine. Les résultats obtenus montrent que la machine émotionnelle proposée est capable de produire de bonnes prédictions. Une telle réalisation pourrait encourager son utilisation future dans des domaines exploitant la reconnaissance automatique de l'émotion.

Our Lady of Ocotlán and our Lady of Guadalupe : investigation into the origins of parallel virgins

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Interactions humain-machine et différences culturelles : l'utilisabilité Bantu comparée

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Application du concept des transactions pour la modélisation et la simulation multicoeur des systèmes sur puce

Avec la complexité croissante des systèmes sur puce, de nouveaux défis ne cessent d’émerger dans la conception de ces systèmes en matière de vérification formelle et de synthèse de haut niveau. Plusieurs travaux autour de SystemC, considéré comme la norme pour la conception au niveau système, sont en cours afin de relever ces nouveaux défis. Cependant, à cause du modèle de concurrence complexe de SystemC, relever ces défis reste toujours une tâche difficile. Ainsi, nous pensons qu’il est primordial de partir sur de meilleures bases en utilisant un modèle de concurrence plus efficace. Par conséquent, dans cette thèse, nous étudions une méthodologie de conception qui offre une meilleure abstraction pour modéliser des composants parallèles en se basant sur le concept de transaction. Nous montrons comment, grâce au raisonnement simple que procure le concept de transaction, il devient plus facile d’appliquer la vérification formelle, le raffinement incrémental et la synthèse de haut niveau. Dans le but d’évaluer l’efficacité de cette méthodologie, nous avons fixé l’objectif d’optimiser la vitesse de simulation d’un modèle transactionnel en profitant d’une machine multicoeur. Nous présentons ainsi l’environnement de modélisation et de simulation parallèle que nous avons développé. Nous étudions différentes stratégies d’ordonnancement en matière de parallélisme et de surcoût de synchronisation. Une expérimentation faite sur un modèle du transmetteur Wi-Fi 802.11a a permis d’atteindre une accélération d’environ 1.8 en utilisant deux threads. Avec 8 threads, bien que la charge de travail des différentes transactions n’était pas importante, nous avons pu atteindre une accélération d’environ 4.6, ce qui est un résultat très prometteur.

Parallel metaheuristics for stochastic capacitated multicommodity network design

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

L’extraction de phrases en relation de traduction dans Wikipédia

Afin d'enrichir les données de corpus bilingues parallèles, il peut être judicieux de travailler avec des corpus dits comparables. En effet dans ce type de corpus, même si les documents dans la langue cible ne sont pas l'exacte traduction de ceux dans la langue source, on peut y retrouver des mots ou des phrases en relation de traduction. L'encyclopédie libre Wikipédia constitue un corpus comparable multilingue de plusieurs millions de documents. Notre travail consiste à trouver une méthode générale et endogène permettant d'extraire un maximum de phrases parallèles. Nous travaillons avec le couple de langues français-anglais mais notre méthode, qui n'utilise aucune ressource bilingue extérieure, peut s'appliquer à tout autre couple de langues. Elle se décompose en deux étapes. La première consiste à détecter les paires d’articles qui ont le plus de chance de contenir des traductions. Nous utilisons pour cela un réseau de neurones entraîné sur un petit ensemble de données constitué d'articles alignés au niveau des phrases. La deuxième étape effectue la sélection des paires de phrases grâce à un autre réseau de neurones dont les sorties sont alors réinterprétées par un algorithme d'optimisation combinatoire et une heuristique d'extension. L'ajout des quelques 560~000 paires de phrases extraites de Wikipédia au corpus d'entraînement d'un système de traduction automatique statistique de référence permet d'améliorer la qualité des traductions produites. Nous mettons les données alignées et le corpus extrait à la disposition de la communauté scientifique.

Apprentissage machine efficace : théorie et pratique

Malgré des progrès constants en termes de capacité de calcul, mémoire et quantité de données disponibles, les algorithmes d'apprentissage machine doivent se montrer efficaces dans l'utilisation de ces ressources. La minimisation des coûts est évidemment un facteur important, mais une autre motivation est la recherche de mécanismes d'apprentissage capables de reproduire le comportement d'êtres intelligents. Cette thèse aborde le problème de l'efficacité à travers plusieurs articles traitant d'algorithmes d'apprentissage variés : ce problème est vu non seulement du point de vue de l'efficacité computationnelle (temps de calcul et mémoire utilisés), mais aussi de celui de l'efficacité statistique (nombre d'exemples requis pour accomplir une tâche donnée). Une première contribution apportée par cette thèse est la mise en lumière d'inefficacités statistiques dans des algorithmes existants. Nous montrons ainsi que les arbres de décision généralisent mal pour certains types de tâches (chapitre 3), de même que les algorithmes classiques d'apprentissage semi-supervisé à base de graphe (chapitre 5), chacun étant affecté par une forme particulière de la malédiction de la dimensionalité. Pour une certaine classe de réseaux de neurones, appelés réseaux sommes-produits, nous montrons qu'il peut être exponentiellement moins efficace de représenter certaines fonctions par des réseaux à une seule couche cachée, comparé à des réseaux profonds (chapitre 4). Nos analyses permettent de mieux comprendre certains problèmes intrinsèques liés à ces algorithmes, et d'orienter la recherche dans des directions qui pourraient permettre de les résoudre. Nous identifions également des inefficacités computationnelles dans les algorithmes d'apprentissage semi-supervisé à base de graphe (chapitre 5), et dans l'apprentissage de mélanges de Gaussiennes en présence de valeurs manquantes (chapitre 6). Dans les deux cas, nous proposons de nouveaux algorithmes capables de traiter des ensembles de données significativement plus grands. Les deux derniers chapitres traitent de l'efficacité computationnelle sous un angle différent. Dans le chapitre 7, nous analysons de manière théorique un algorithme existant pour l'apprentissage efficace dans les machines de Boltzmann restreintes (la divergence contrastive), afin de mieux comprendre les raisons qui expliquent le succès de cet algorithme. Finalement, dans le chapitre 8 nous présentons une application de l'apprentissage machine dans le domaine des jeux vidéo, pour laquelle le problème de l'efficacité computationnelle est relié à des considérations d'ingénierie logicielle et matérielle, souvent ignorées en recherche mais ô combien importantes en pratique.

La représentation de la machine dans la trilogie d’anticipation scientifique d’Albert Robida : du texte à l’image et de l’image au texte

Cette thèse étudie la représentation de la machine chez Robida. La partie centrale de notre recherche s’intéresse à révéler ses significations et interroge sa mise en scène littéraire et visuelle dans chacun des romans de la trilogie d’anticipation scientifique la plus connue de l’auteur-illustrateur. La quête se transforme en un voyage continu entre le lisible et le visible, le dit et le non-dit, la description littéraire et l’imagination, la réalité et la fiction. Nous nous intéressons à l’évolution de la vision de Robida : dans Le Vingtième siècle, l’image de la machine bienfaisante, facilitant la vie de l’homme, économisant du temps et de l’argent, et contribuant largement à son bonheur et à son divertissement, à part quelques accidents très limités, se traduit par une complémentarité avantageuse entre le texte d’une part et les vignettes, les tableaux et les hors-textes se trouvant dans le récit, d’autre part. Celle-ci se transforme, dans La Guerre au vingtième siècle, en une inquiétude vis-à-vis de l’instrumentalisation de la machine pour la guerre, qui s’exprime par une projection de la narration vers l’illustration in-texte, et sensibilise le lecteur en montrant le caractère violent et offensif d’appareils uniquement nommés. Celle-ci devient finalement, dans La Vie électrique, synonyme d’un pessimisme total quant à l’implication de la machine dans la société et à la puissance du savoir scientifique dans l’avenir, qui s’affiche dans des hors-textes sombres et maussades. Dans ce cadre, la machine illustrée exige une lecture iconotextuelle, une importance accordée au détail, aux éléments présents ou absents, aux modalités de passage d’un mode de présentation à l’autre, à la place anticipée ou tardive de l’illustration, au rapport entre le texte, le dessin et sa légende, aux mots qui migrent vers le dessin et surtout au reste du décor incomplet. Chez Robida, les louanges qui passent à la critique et l’humour qui se fait cynisme, sont assez représentatifs des espoirs et des craintes suscités par la découverte et la mise en application de l’électricité, par ses vertus, mais aussi par son aspect incontrôlable.

Histoire formelle du jeu d’aventure sur ordinateur (le cas de l’Amérique du Nord de 1976-1999)

Cette étude s’intéresse à l’évolution formelle du jeu d’aventure de 1976 à 1999. Elle se propose de mieux comprendre les facteurs historiques contribuant à l’apparition du genre, son institution et ses transformations. La recherche est fondée sur l’analyse du discours de la presse spécialisée en jeux d’ordinateur et d’un corpus étendu d’œuvres. L’une des thèses proposées est que l’identité générique du jeu d’aventure est fondée sur une expérience vidéoludique demeurant relativement constante malgré des variations importantes de formes. Cette expérience est assurée par la reproduction des principaux éléments d’une architecture générale de design de jeu inaugurée par Adventure en 1977. Les variations formelles ponctuelles résultent d’une négociation entre la volonté de s’adapter aux changements de contexte de l’écologie du jeu d’ordinateur et la résistance d’une architecture ludique établie. La pertinence d’une histoire d’un genre vidéoludique est justifiée au premier chapitre en fonction de l’état actuel des connaissances sur l’histoire du jeu vidéo et du jeu d’aventure. On y précise également le cadre théorique, la méthodologie et les sources étudiées. Le deuxième chapitre s’intéresse à la genèse d’Adventure de Crowther et Woods (1976; 1977) en fonction des diverses pratiques culturelles dans lesquelles l’œuvre s’inscrit. Cette analyse permet d’en dégager l’architecture ludique. Le troisième chapitre porte sur le « tournant narratif » du jeu d’aventure ayant lieu au début des années 1980. On y décrit différents facteurs historiques poussant le genre vers l’enchâssement d’histoires pré-écrites afin d’en faire un véhicule narratif. Le quatrième chapitre décrit le contexte du « tournant graphique », passage du jeu d’aventure d’une représentation textuelle à un régime visuel, ainsi que ses conséquences expérientielles. Le « tournant ergonomique » décrit au cinquième chapitre traite de l’apparition du modèle « pointer et cliquer » en fonction des avancées des connaissances concernant les interactions humain-machine ainsi que de la maturation du design de jeu comme pratique autonome. Le dernier chapitre relate l’apogée du jeu d’aventure au début de la révolution multimédia sous ses formes de film interactif et « Myst-like » puis du ralentissement – voire de l’arrêt – de son évolution formelle.

A layered JavaScript virtual machine supporting dynamic instrumentation

L’observation de l’exécution d’applications JavaScript est habituellement réalisée en instrumentant une machine virtuelle (MV) industrielle ou en effectuant une traduction source-à-source ad hoc et complexe. Ce mémoire présente une alternative basée sur la superposition de machines virtuelles. Notre approche consiste à faire une traduction source-à-source d’un programme pendant son exécution pour exposer ses opérations de bas niveau au travers d’un modèle objet flexible. Ces opérations de bas niveau peuvent ensuite être redéfinies pendant l’exécution pour pouvoir en faire l’observation. Pour limiter la pénalité en performance introduite, notre approche exploite les opérations rapides originales de la MV sous-jacente, lorsque cela est possible, et applique les techniques de compilation à-la-volée dans la MV superposée. Notre implémentation, Photon, est en moyenne 19% plus rapide qu’un interprète moderne, et entre 19× et 56× plus lente en moyenne que les compilateurs à-la-volée utilisés dans les navigateurs web populaires. Ce mémoire montre donc que la superposition de machines virtuelles est une technique alternative compétitive à la modification d’un interprète moderne pour JavaScript lorsqu’appliqué à l’observation à l’exécution des opérations sur les objets et des appels de fonction.

Un outil d’évaluation neurocognitive des interactions humain-machine

De plus en plus de recherches sur les Interactions Humain-Machine (IHM) tentent d’effectuer des analyses fines de l’interaction afin de faire ressortir ce qui influence les comportements des utilisateurs. Tant au niveau de l’évaluation de la performance que de l’expérience des utilisateurs, on note qu’une attention particulière est maintenant portée aux réactions émotionnelles et cognitives lors de l’interaction. Les approches qualitatives standards sont limitées, car elles se fondent sur l’observation et des entrevues après l’interaction, limitant ainsi la précision du diagnostic. L’expérience utilisateur et les réactions émotionnelles étant de nature hautement dynamique et contextualisée, les approches d’évaluation doivent l’être de même afin de permettre un diagnostic précis de l’interaction. Cette thèse présente une approche d’évaluation quantitative et dynamique qui permet de contextualiser les réactions des utilisateurs afin d’en identifier les antécédents dans l’interaction avec un système. Pour ce faire, ce travail s’articule autour de trois axes. 1) La reconnaissance automatique des buts et de la structure de tâches de l’utilisateur, à l’aide de mesures oculométriques et d’activité dans l’environnement par apprentissage machine. 2) L’inférence de construits psychologiques (activation, valence émotionnelle et charge cognitive) via l’analyse des signaux physiologiques. 3) Le diagnostic de l‘interaction reposant sur le couplage dynamique des deux précédentes opérations. Les idées et le développement de notre approche sont illustrés par leur application dans deux contextes expérimentaux : le commerce électronique et l’apprentissage par simulation. Nous présentons aussi l’outil informatique complet qui a été implémenté afin de permettre à des professionnels en évaluation (ex. : ergonomes, concepteurs de jeux, formateurs) d’utiliser l’approche proposée pour l’évaluation d’IHM. Celui-ci est conçu de manière à faciliter la triangulation des appareils de mesure impliqués dans ce travail et à s’intégrer aux méthodes classiques d’évaluation de l’interaction (ex. : questionnaires et codage des observations).