Cette thèse traite de méthodes « model-based » pour résoudre des problèmes d'apprentissage par renforcement. On considère un agent confronté à une suite de décisions et un environnement dont l'état varie selon les décisions prises par l'agent. Ce dernier reçoit tout au long de l'interaction des récompenses qui dépendent à la fois de l'action prise et de l'état de l'environnement. L'agent ne connaît pas le modèle d'interaction et a pour but de maximiser la somme des récompenses reçues à long terme. Nous considérons différents modèles d'interactions : les processus de décisions markoviens, les processus de décisions markoviens partiellement observés et les modèles de bandits. Pour ces différents modèles, nous proposons des algorithmes qui consistent à construire à chaque instant un ensemble de modèles permettant d'expliquer au mieux l'interaction entre l'agent et l'environnement. Les méthodes dites « model-based » que nous élaborons se veulent performantes tant en pratique que d'un point de vue théorique. La performance théorique des algorithmes est calculée en terme de regret qui mesure la différence entre la somme des récompenses reçues par un agent qui connaîtrait à l'avance le modèle d'interaction et celle des récompenses cumulées par l'algorithme. En particulier, ces algorithmes garantissent un bon équilibre entre l'acquisition de nouvelles connaissances sur la réaction de l'environnement (exploration) et le choix d'actions qui semblent mener à de fortes récompenses (exploitation). Nous proposons deux types de méthodes différentes pour contrôler ce compromis entre exploration et exploitation. Le premier algorithme proposé dans cette thèse consiste à suivre successivement une stratégie d'exploration, durant laquelle le modèle d'interaction est estimé, puis une stratégie d'exploitation. La durée de la phase d'exploration est contrôlée de manière adaptative ce qui permet d'obtenir un regret logarithmique dans un processus de décision markovien paramétrique même si l'état de l'environnement n'est que partiellement observé. Ce type de modèle est motivé par une application d'intérêt en radio cognitive qu'est l'accès opportuniste à un réseau de communication par un utilisateur secondaire. Les deux autres algorithmes proposés suivent des stratégies optimistes : l'agent choisit les actions optimales pour le meilleur des modèles possibles parmi l'ensemble des modèles vraisemblables. Nous construisons et analysons un tel algorithme pour un modèle de bandit paramétrique dans un cas de modèles linéaires généralisés permettant ainsi de considérer des applications telles que la gestion de publicité sur internet. Nous proposons également d'utiliser la divergence de Kullback-Leibler pour la construction de l'ensemble des modèles vraisemblables dans des algorithmes optimistes pour des processus de décision markoviens à espaces d'états et d'actions finis. L'utilisation de cette métrique améliore significativement le comportement de des algorithmes optimistes en pratique. De plus, une analyse du regret de chacun des algorithmes permet de garantir des performances théoriques similaires aux meilleurs algorithmes de l'état de l'art.

Tout au long de la vie, le cerveau développe des représentations de son environnement permettant à l’individu d’en tirer meilleur profit. Comment ces représentations se développent-elles pendant la quête de récompenses demeure un mystère. Il est raisonnable de penser que le cortex est le siège de ces représentations et que les ganglions de la base jouent un rôle important dans la maximisation des récompenses. En particulier, les neurones dopaminergiques semblent coder un signal d’erreur de prédiction de récompense. Cette thèse étudie le problème en construisant, à l’aide de l’apprentissage machine, un modèle informatique intégrant de nombreuses évidences neurologiques. Après une introduction au cadre mathématique et à quelques algorithmes de l’apprentissage machine, un survol de l’apprentissage en psychologie et en neuroscience et une revue des modèles de l’apprentissage dans les ganglions de la base, la thèse comporte trois articles. Le premier montre qu’il est possible d’apprendre à maximiser ses récompenses tout en développant de meilleures représentations des entrées. Le second article porte sur l'important problème toujours non résolu de la représentation du temps. Il démontre qu’une représentation du temps peut être acquise automatiquement dans un réseau de neurones artificiels faisant office de mémoire de travail. La représentation développée par le modèle ressemble beaucoup à l’activité de neurones corticaux dans des tâches similaires. De plus, le modèle montre que l’utilisation du signal d’erreur de récompense peut accélérer la construction de ces représentations temporelles. Finalement, il montre qu’une telle représentation acquise automatiquement dans le cortex peut fournir l’information nécessaire aux ganglions de la base pour expliquer le signal dopaminergique. Enfin, le troisième article évalue le pouvoir explicatif et prédictif du modèle sur différentes situations comme la présence ou l’absence d’un stimulus (conditionnement classique ou de trace) pendant l’attente de la récompense. En plus de faire des prédictions très intéressantes en lien avec la littérature sur les intervalles de temps, l’article révèle certaines lacunes du modèle qui devront être améliorées. Bref, cette thèse étend les modèles actuels de l’apprentissage des ganglions de la base et du système dopaminergique au développement concurrent de représentations temporelles dans le cortex et aux interactions de ces deux structures. / Throughout lifetime, the brain develops abstract representations of its environment that allow the individual to maximize his benefits. How these representations are developed while trying to acquire rewards remains a mystery. It is reasonable to assume that these representations arise in the cortex and that the basal ganglia are playing an important role in reward maximization. In particular, dopaminergic neurons appear to code a reward prediction error signal. This thesis studies the problem by constructing, using machine learning tools, a computational model that incorporates a number of relevant neurophysiological findings. After an introduction to the machine learning framework and to some of its algorithms, an overview of learning in psychology and neuroscience, and a review of models of learning in the basal ganglia, the thesis comprises three papers. The first article shows that it is possible to learn a better representation of the inputs while learning to maximize reward. The second paper addresses the important and still unresolved problem of the representation of time in the brain. The paper shows that a time representation can be acquired automatically in an artificial neural network acting like a working memory. The representation learned by the model closely resembles the activity of cortical neurons in similar tasks. Moreover, the model shows that the reward prediction error signal could accelerate the development of the temporal representation. Finally, it shows that if such a learned representation exists in the cortex, it could provide the necessary information to the basal ganglia to explain the dopaminergic signal. The third article evaluates the explanatory and predictive power of the model on the effects of differences in task conditions such as the presence or absence of a stimulus (classical versus trace conditioning) while waiting for the reward. Beyond making interesting predictions relevant to the timing literature, the paper reveals some shortcomings of the model that will need to be resolved. In summary, this thesis extends current models of reinforcement learning of the basal ganglia and the dopaminergic system to the concurrent development of representation in the cortex and to the interactions between these two regions.

Les réseaux optiques à commutation de rafales (OBS) sont des candidats pour jouer un rôle important dans le cadre des réseaux optiques de nouvelle génération. Dans cette thèse, nous nous intéressons au routage adaptatif et au provisionnement de la qualité de service dans ce type de réseaux. Dans une première partie de la thèse, nous nous intéressons à la capacité du routage multi-chemins et du routage alternatif (par déflection) à améliorer les performances des réseaux OBS, pro-activement pour le premier et ré-activement pour le second. Dans ce contexte, nous proposons une approche basée sur l’apprentissage par renforcement où des agents placés dans tous les nœuds du réseau coopèrent pour apprendre, continuellement, les chemins du routage et les chemins alternatifs optimaux selon l’état actuel du réseau. Les résultats numériques montrent que cette approche améliore les performances des réseaux OBS comparativement aux solutions proposées dans la littérature. Dans la deuxième partie de cette thèse, nous nous intéressons au provisionnement absolu de la qualité de service où les performances pire-cas des classes de trafic de priorité élevée sont garanties quantitativement. Plus spécifiquement, notre objectif est de garantir la transmission sans pertes des rafales de priorité élevée à l’intérieur du réseau OBS tout en préservant le multiplexage statistique et l’utilisation efficace des ressources qui caractérisent les réseaux OBS. Aussi, nous considérons l’amélioration des performances du trafic best effort. Ainsi, nous proposons deux approches : une approche basée sur les nœuds et une approche basée sur les chemins. Dans l’approche basée sur les nœuds, un ensemble de longueurs d’onde est assigné à chaque nœud du bord du réseau OBS pour qu’il puisse envoyer son trafic garanti. Cette assignation prend en considération les distances physiques entre les nœuds du bord. En outre, nous proposons un algorithme de sélection des longueurs d’onde pour améliorer les performances des rafales best effort. Dans l’approche basée sur les chemins, le provisionnement absolu de la qualité de service est fourni au niveau des chemins entre les nœuds du bord du réseau OBS. À cette fin, nous proposons une approche de routage et d’assignation des longueurs d’onde qui a pour but la réduction du nombre requis de longueurs d’onde pour établir des chemins sans contentions. Néanmoins, si cet objectif ne peut pas être atteint à cause du nombre limité de longueurs d’onde, nous proposons de synchroniser les chemins en conflit sans le besoin pour des équipements additionnels. Là aussi, nous proposons un algorithme de sélection des longueurs d’onde pour les rafales best effort. Les résultats numériques montrent que l’approche basée sur les nœuds et l’approche basée sur les chemins fournissent le provisionnement absolu de la qualité de service pour le trafic garanti et améliorent les performances du trafic best effort. En outre, quand le nombre de longueurs d’ondes est suffisant, l’approche basée sur les chemins peut accommoder plus de trafic garanti et améliorer les performances du trafic best effort par rapport à l’approche basée sur les nœuds. / Optical Burst Switching (OBS) networks are candidates to play an important role in the context of next generation optical networks. In this thesis, we are interested in adaptive routing and quality of service provisioning for these networks. In the first part of the thesis, we study the capability of multi-path routing and alternative routing (deflection routing) to improve the performance of the OBS network proactively for the former and reactively for the latter. In this context, we propose a reinforcement learning-based approach where learning agents, placed in each OBS node, cooperate to learn, continuously, optimal routing paths and alternative paths according to the current state of the network. Numerical results show that the proposed approach improves the performance of the OBS network compared to existing solutions in the literature. In the second part of the thesis, we consider the problem of absolute quality of service provisioning for OBS networks where worst-case performance of high priority traffic is guaranteed quantitatively. Particularly, we are interested in the loss-free transmission, inside the OBS network, of high priority bursts, while preserving statistical multiplexing gain and high resources utilization of the OBS network. Also, we aim to improve the performance of best effort traffic. Hence, we propose two approaches: (a) the node-based approach; and (b) the path-based approach. In the node-based approach, we propose to assign a set of wavelengths to each OBS edge node that it can use to send its guaranteed traffic. This assignment takes into consideration physical distances between edge nodes. Furthermore, we propose a wavelength selection algorithm to improve the performance of best effort bursts. In the path-based approach, absolute quality of service provisioning is offered at end-to-end path level. To do this, we propose a routing and wavelength assignment approach which aims to reduce the number of wavelengths required to establish contention free paths. Nevertheless, if this objective cannot be reached because of the limited number of wavelengths in each fiber link, we propose an approach to synchronize overlapping paths without the need for additional equipments for synchronization. Here again, we propose a wavelength selection algorithm for best effort bursts. Numerical results show that both the node-based and the path-based approaches successfully provide absolute quality of service provisioning for guaranteed traffic and improve the performance of best effort traffic. Also, path-based approach could accommodate more guaranteed traffic and improve the performance of best effort traffic compared to node-based approach when the number of wavelengths is sufficient.

Cette thèse considère l'apprentissage de motifs récurrents dans la perception multimodale. Elle s'attache à développer des modèles robotiques de ces facultés telles qu'observées chez l'enfant, et elle s'inscrit en cela dans le domaine de la robotique développementale. Elle s'articule plus précisément autour de deux thèmes principaux qui sont d'une part la capacité d'enfants ou de robots à imiter et à comprendre le comportement d'humains, et d'autre part l'acquisition du langage. À leur intersection, nous examinons la question de la découverte par un agent en développement d'un répertoire de motifs primitifs dans son flux perceptuel. Nous spécifions ce problème et établissons son lien avec ceux de l'indétermination de la traduction décrit par Quine et de la séparation aveugle de source tels qu'étudiés en acoustique. Nous en étudions successivement quatre sous-problèmes et formulons une définition expérimentale de chacun. Des modèles d'agents résolvant ces problèmes sont également décrits et testés. Ils s'appuient particulièrement sur des techniques dites de sacs de mots, de factorisation de matrices et d'apprentissage par renforcement inverse. Nous approfondissons séparément les trois problèmes de l'apprentissage de sons élémentaires tels les phonèmes ou les mots, de mouvements basiques de danse et d'objectifs primaires composant des tâches motrices complexes. Pour finir nous étudions le problème de l'apprentissage d'éléments primitifs multimodaux, ce qui revient à résoudre simultanément plusieurs des problèmes précédents. Nous expliquons notamment en quoi cela fournit un modèle de l'ancrage de mots acoustiques.

Cette thèse étudie les techniques de gestion intelligente du spectre et de topologie des réseaux via une approche radio intelligente dans le but d’améliorer leur capacité, leur qualité de service (QoS – Quality of Service) et leur consommation énergétique. Les techniques d’apprentissage par renforcement y sont utilisées dans le but d’améliorer les performances d’un système radio intelligent. Dans ce manuscrit, nous traitons du problème d’accès opportuniste au spectre dans le cas de réseaux intelligents sans infrastructure. Nous nous plaçons dans le cas où aucune information n’est échangée entre les utilisateurs secondaires (pour éviter les surcoûts en transmissions). Ce problème particulier est modélisé par une approche dite de bandits manchots « restless » markoviens multi-utilisateurs (multi-user restless Markov MAB -multi¬armed bandit). La contribution principale de cette thèse propose une stratégie d’apprentissage multi-joueurs qui prend en compte non seulement le critère de disponibilité des canaux (comme déjà étudié dans la littérature et une thèse précédente au laboratoire), mais aussi une métrique de qualité, comme par exemple le niveau d’interférence mesuré (sensing) dans un canal (perturbations issues des canaux adjacents ou de signaux distants). Nous prouvons que notre stratégie, RQoS-UCB distribuée (distributed restless QoS-UCB – Upper Confidence Bound), est quasi optimale car on obtient des performances au moins d’ordre logarithmique sur son regret. En outre, nous montrons par des simulations que les performances du système intelligent proposé sont améliorées significativement par l’utilisation de la solution d’apprentissage proposée permettant à l’utilisateur secondaire d’identifier plus efficacement les ressources fréquentielles les plus disponibles et de meilleure qualité. Cette thèse propose également un nouveau modèle d’apprentissage par renforcement combiné à un transfert de connaissance afin d’améliorer l’efficacité énergétique (EE) des réseaux cellulaires hétérogènes. Nous formulons et résolvons un problème de maximisation de l’EE pour le cas de stations de base (BS – Base Stations) dynamiquement éteintes et allumées (ON-OFF). Ce problème d’optimisation combinatoire peut aussi être modélisé par des bandits manchots « restless » markoviens. Par ailleurs, une gestion dynamique de la topologie des réseaux hétérogènes, utilisant l’algorithme RQoS-UCB, est proposée pour contrôler intelligemment le mode de fonctionnement ON-OFF des BS, dans un contexte de trafic et d’étude de capacité multi-cellulaires. Enfin une méthode incluant le transfert de connaissance « transfer RQoS-UCB » est proposée et validée par des simulations, pour pallier les pertes de récompense initiales et accélérer le processus d’apprentissage, grâce à la connaissance acquise à d’autres périodes temporelles correspondantes à la période courante (même heure de la journée la veille, ou même jour de la semaine par exemple). La solution proposée de gestion dynamique du mode ON-OFF des BS permet de diminuer le nombre de BS actives tout en garantissant une QoS adéquate en atténuant les fluctuations de la QoS lors des variations du trafic et en améliorant les conditions au démarrage de l’apprentissage. Ainsi, l’efficacité énergétique est grandement améliorée. Enfin des démonstrateurs en conditions radio réelles ont été développés pour valider les solutions d’apprentissage étudiées. Les algorithmes ont également été confrontés à des bases de données de mesures effectuées par un partenaire dans la gamme de fréquence HF, pour des liaisons transhorizon. Les résultats confirment la pertinence des solutions d’apprentissage proposées, aussi bien en termes d’optimisation de l’utilisation du spectre fréquentiel, qu’en termes d’efficacité énergétique. / Future cellular network technologies are targeted at delivering self-organizable and ultra-high capacity networks, while reducing their energy consumption. This thesis studies intelligent spectrum and topology management through cognitive radio techniques to improve the capacity density and Quality of Service (QoS) as well as to reduce the cooperation overhead and energy consumption. This thesis investigates how reinforcement learning can be used to improve the performance of a cognitive radio system. In this dissertation, we deal with the problem of opportunistic spectrum access in infrastructureless cognitive networks. We assume that there is no information exchange between users, and they have no knowledge of channel statistics and other user's actions. This particular problem is designed as multi-user restless Markov multi-armed bandit framework, in which multiple users collect a priori unknown reward by selecting a channel. The main contribution of the dissertation is to propose a learning policy for distributed users, that takes into account not only the availability criterion of a band but also a quality metric linked to the interference power from the neighboring cells experienced on the sensed band. We also prove that the policy, named distributed restless QoS-UCB (RQoS-UCB), achieves at most logarithmic order regret. Moreover, numerical studies show that the performance of the cognitive radio system can be significantly enhanced by utilizing proposed learning policies since the cognitive devices are able to identify the appropriate resources more efficiently. This dissertation also introduces a reinforcement learning and transfer learning frameworks to improve the energy efficiency (EE) of the heterogeneous cellular network. Specifically, we formulate and solve an energy efficiency maximization problem pertaining to dynamic base stations (BS) switching operation, which is identified as a combinatorial learning problem, with restless Markov multi-armed bandit framework. Furthermore, a dynamic topology management using the previously defined algorithm, RQoS-UCB, is introduced to intelligently control the working modes of BSs, based on traffic load and capacity in multiple cells. Moreover, to cope with initial reward loss and to speed up the learning process, a transfer RQoS-UCB policy, which benefits from the transferred knowledge observed in historical periods, is proposed and provably converges. Then, proposed dynamic BS switching operation is demonstrated to reduce the number of activated BSs while maintaining an adequate QoS. Extensive numerical simulations demonstrate that the transfer learning significantly reduces the QoS fluctuation during traffic variation, and it also contributes to a performance jump-start and presents significant EE improvement under various practical traffic load profiles. Finally, a proof-of-concept is developed to verify the performance of proposed learning policies on a real radio environment and real measurement database of HF band. Results show that proposed multi-armed bandit learning policies using dual criterion (e.g. availability and quality) optimization for opportunistic spectrum access is not only superior in terms of spectrum utilization but also energy efficient.

The work in this thesis is separated into two parts. The first part deals with the load planning and sequencing problem for double-stack intermodal railcars, an operational problem found at many rail container terminals. In this problem, containers must be assigned to a platform on which the container will be loaded, and the loading order must be determined. These decisions are made with the objective of minimizing the costs associated with handling the containers, as well as minimizing the cost of containers left behind. The deterministic version of the problem can be cast as a shortest path problem on an ordered graph. This problem is challenging to solve because of the large size of the graph. We propose a two-stage heuristic based on the Iterative Deepening A* algorithm to compute solutions to the load planning and sequencing problem within a five-minute time budget. Next, we also illustrate how a Deep Q-learning algorithm can be used to heuristically solve the same problem.The second part of this thesis considers sequential models in deep learning. A recent strategy to circumvent the exploding and vanishing gradient problem in recurrent neural networks (RNNs) is to enforce recurrent weight matrices to be orthogonal or unitary. While this ensures stable dynamics during training, it comes at the cost of reduced expressivity due to the limited variety of orthogonal transformations. We propose a parameterization of RNNs, based on the Schur decomposition, that mitigates the exploding and vanishing gradient problem, while allowing for non-orthogonal recurrent weight matrices in the model. / Le travail de cette thèse est divisé en deux parties. La première partie traite du problème de planification et de séquencement des chargements de conteneurs sur des wagons, un problème opérationnel rencontré dans de nombreux terminaux ferroviaires intermodaux. Dans ce problème, les conteneurs doivent être affectés à une plate-forme sur laquelle un ou deux conteneurs seront chargés et l'ordre de chargement doit être déterminé. Ces décisions sont prises dans le but de minimiser les coûts associés à la manutention des conteneurs, ainsi que de minimiser le coût des conteneurs non chargés. La version déterministe du problème peut être formulé comme un problème de plus court chemin sur un graphe ordonné. Ce problème est difficile à résoudre en raison de la grande taille du graphe. Nous proposons une heuristique en deux étapes basée sur l'algorithme Iterative Deepening A* pour calculer des solutions au problème de planification et de séquencement de la charge dans un budget de cinq minutes. Ensuite, nous illustrons également comment un algorithme d'apprentissage Deep Q peut être utilisé pour résoudre heuristiquement le même problème. La deuxième partie de cette thèse examine les modèles séquentiels en apprentissage profond. Une stratégie récente pour contourner le problème de gradient qui explose et disparaît dans les réseaux de neurones récurrents (RNN) consiste à imposer des matrices de poids récurrentes orthogonales ou unitaires. Bien que cela assure une dynamique stable pendant l'entraînement, cela se fait au prix d'une expressivité réduite en raison de la variété limitée des transformations orthogonales. Nous proposons une paramétrisation des RNN, basée sur la décomposition de Schur, qui atténue les problèmes de gradient, tout en permettant des matrices de poids récurrentes non orthogonales dans le modèle.

Des études soutiennent que l’entraînement cognitif est une méthode efficace pour ralentirle déclin cognitif chez les personnes âgées. Les jeux sérieux basés sur la réalité virtuelle(RV) ont trouvé une application dans ce domaine en raison du haut niveau d’immersionet d’interactivité offert par les environnements virtuels (EV). Ce projet implémente unjeu d’orientation 3D en réalité virtuelle entièrement immersif avec un système pour guiderl’utilisateur en temps réel. Le jeu d’orientation 3D est utilisé comme exercice pour entraînerles capacités cognitives des utilisateurs. Les effets immédiats du jeu d’orientation sur lescapacités de mémoire et d’attention ont été étudiés sur quinze personnes âgées présentant undéclin cognitif subjectif (DCS). Il a été observé que bien qu’il n’y ait pas eu d’améliorationsignificative des résultats pour les exercices d’attention, les participants ont obtenu demeilleurs résultats aux exercices de mémoire spécifiques après avoir joué au jeu d’orientation. Le manque de succès dans la réalisation de l’objectif requis peut parfois augmenter lesémotions négatives chez les êtres humains, et plus particulièrement chez les personnes quisouffrent de déclin cognitif. C’est pourquoi le jeu a été équipé d’un système de guidageavec indices de localisation en temps réel pour contrôler les émotions négatives et aiderles participants à accomplir leurs tâches. Le système de guidage est basé sur des règleslogiques; chaque indice est délivré si une condition spécifique est remplie. Le changement desémotions des participants a montré que les indices sont efficaces pour réduire la frustration,étant donné qu’ils sont facilement compréhensibles et conçus pour donner un retour positif. La dernière partie du projet se concentre sur le système de guidage et met en oeuvre unmoyen pour l’activer entièrement selon les émotions d’une personne. Le problème consisteà identifier l’état des émotions qui devraient déclencher l’activation du système de guidage.Ce problème prend la forme d’un processus de décision markovien (PDM), qui peut êtrerésolu via l’apprentissage par renforcement (AR). Le réseau profond Q (RPQ) avec relectured’expérience (ER), qui est l’un des algorithmes d’apprentissage par renforcement les plusavancés pour la prédiction d’actions dans un espace d’action discret, a été utilisé dans cecontexte. L’algorithme a été formé sur des données d’émotions simulées, et testé sur les données de quinze personnes âgées acquises lors d’expériences menées dans la première partiedu projet. On observe que la méthode basée sur l’AR est plus performante que la méthodebasée sur les règles pour identifier l’état mental d’une personne afin de lui fournir des indices. / Studies support cognitive training as an efficient method to slow the cognitive declinein older adults. Virtual reality (VR) based serious games have found application in thisfield due to the high level of immersion and interactivity offered by virtual environments(VE). This project implements a fully immersive 3D virtual reality orientation game with areal-time guidance system to be used as an exercise for cognitive training. The immediateaftereffects of playing the orientation game on memory and attention abilities were studiedon fifteen older adults with subjective cognitive decline (SCD). It was observed that whilethere was no significant improvement in attention exercises, the participants performedbetter in specific memory exercises after playing the orientation game. Sometimes lack of success in achieving the required objective may increase the negativeemotions in humans and more so in people who suffer from cognitive decline. Hence, thegame was equipped with a real-time guidance system with location hints to control negativeemotions and help participants to complete the tasks. The guidance system is based onlogical rules; each hint is delivered if a specific condition is met. Change in emotions ofparticipants showed that hints are effective in reducing frustration, given that the hints areeasily comprehensible and designed to give positive feedback. The final part of the project focuses on the guidance system and implements a way toactivate it entirely based on a person’s emotions. The problem calls for identifying the stateof the emotions that should trigger the guidance system’s activation. This problem takes theform of a Markov decision process (MDP), which can be solved by setting it in a reinforcementlearning framework. Deep Q-Learning network (DQN) with experience replay (ER),which is one of the state-of-the-art reinforcement learning algorithms for predicting actionsin discrete action space, was used in this context. The algorithm was trained on simulateddata of emotions and tested on the data of fifteen older adults acquired in experimentsconducted in the first part of the project. It is observed that the RL based method performsbetter than the rule-based method in identifying the mental state of a person to provide hints.

Évaluer la vulnérabilité des réseaux est un enjeu de plus en plus critique. Dans ce mémoire, nous nous penchons sur une approche étudiant la défense d’infrastructures stratégiques contre des attaques malveillantes au travers de problèmes d'optimisations multiniveaux. Plus particulièrement, nous analysons un jeu séquentiel en trois étapes appelé le « Multilevel Critical Node problem » (MCN). Ce jeu voit deux joueurs s'opposer sur un graphe: un attaquant et un défenseur. Le défenseur commence par empêcher préventivement que certains nœuds soient attaqués durant une phase de vaccination. Ensuite, l’attaquant infecte un sous ensemble des nœuds non vaccinés. Finalement, le défenseur réagit avec une stratégie de protection. Dans ce mémoire, nous fournissons les premiers résultats de complexité pour MCN ainsi que ceux de ses sous-jeux. De plus, en considérant les différents cas de graphes unitaires, pondérés ou orientés, nous clarifions la manière dont la complexité de ces problèmes varie. Nos résultats contribuent à élargir les familles de problèmes connus pour être complets pour les classes NP, $\Sigma_2^p$ et $\Sigma_3^p$. Motivés par l’insolubilité intrinsèque de MCN, nous concevons ensuite une heuristique efficace pour le jeu. Nous nous appuyons sur les approches récentes cherchant à apprendre des heuristiques pour des problèmes d’optimisation combinatoire en utilisant l’apprentissage par renforcement et les réseaux de neurones graphiques. Contrairement aux précédents travaux, nous nous intéressons aux situations dans lesquelles de multiples joueurs prennent des décisions de manière séquentielle. En les inscrivant au sein du formalisme d’apprentissage multiagent, nous concevons un algorithme apprenant à résoudre des problèmes d’optimisation combinatoire multiniveaux budgétés opposant deux joueurs dans un jeu à somme nulle sur un graphe. Notre méthode est basée sur un simple curriculum : si un agent sait estimer la valeur d’une instance du problème ayant un budget au plus B, alors résoudre une instance avec budget B+1 peut être fait en temps polynomial quelque soit la direction d’optimisation en regardant la valeur de tous les prochains états possibles. Ainsi, dans une approche ascendante, nous entraînons notre agent sur des jeux de données d’instances résolues heuristiquement avec des budgets de plus en plus grands. Nous rapportons des résultats quasi optimaux sur des graphes de tailles au plus 100 et un temps de résolution divisé par 185 en moyenne comparé au meilleur solutionneur exact pour le MCN. / Evaluating the vulnerability of networks is a problem which has gain momentum in recent decades. In this work, we focus on a Multilevel Programming approach to study the defense of critical infrastructures against malicious attacks. We analyze a three-stage sequential game played in a graph called the Multilevel Critical Node problem (MCN). This game sees two players competing with each other: a defender and an attacker. The defender starts by preventively interdicting nodes from being attacked during what is called a vaccination phase. Then, the attacker infects a subset of non-vaccinated nodes and, finally, the defender reacts with a protection strategy. We provide the first computational complexity results associated with MCN and its subgames. Moreover, by considering unitary, weighted, undirected and directed graphs, we clarify how the theoretical tractability or intractability of those problems vary. Our findings contribute with new NP-complete, $\Sigma_2^p$-complete and $\Sigma_3^p$-complete problems. Motivated by the intrinsic intractability of the MCN, we then design efficient heuristics for the game by building upon the recent approaches seeking to learn heuristics for combinatorial optimization problems through graph neural networks and reinforcement learning. But contrary to previous work, we tackle situations with multiple players taking decisions sequentially. By framing them in a multi-agent reinforcement learning setting, we devise a value-based method to learn to solve multilevel budgeted combinatorial problems involving two players in a zero-sum game over a graph. Our framework is based on a simple curriculum: if an agent knows how to estimate the value of instances with budgets up to B, then solving instances with budget B+1 can be done in polynomial time regardless of the direction of the optimization by checking the value of every possible afterstate. Thus, in a bottom-up approach, we generate datasets of heuristically solved instances with increasingly larger budgets to train our agent. We report results close to optimality on graphs up to 100 nodes and a 185 x speedup on average compared to the quickest exact solver known for the MCN.

Nous étudions dans cette thèse comment les réseaux de neurones profonds peuvent être utilisés dans différents domaines de la vision artificielle. La vision artificielle est un domaine interdisciplinaire qui traite de la compréhension d’images et de vidéos numériques. Les problèmes de ce domaine ont traditionnellement été adressés avec des méthodes ad-hoc nécessitant beaucoup de réglages manuels. En effet, ces systèmes de vision artificiels comprenaient jusqu’à récemment une série de modules optimisés indépendamment. Cette approche est très raisonnable dans la mesure où, avec peu de données, elle bénéficient autant que possible des connaissances du chercheur. Mais cette avantage peut se révéler être une limitation si certaines données d’entré n’ont pas été considérées dans la conception de l’algorithme. Avec des volumes et une diversité de données toujours plus grands, ainsi que des capacités de calcul plus rapides et économiques, les réseaux de neurones profonds optimisés d’un bout à l’autre sont devenus une alternative attrayante. Nous démontrons leur avantage avec une série d’articles de recherche, chacun d’entre eux trouvant une solution à base de réseaux de neurones profonds à un problème d’analyse ou de synthèse visuelle particulier. Dans le premier article, nous considérons un problème de vision classique: la détection de bords et de contours. Nous partons de l’approche classique et la rendons plus ‘neurale’ en combinant deux étapes, la détection et la description de motifs visuels, en un seul réseau convolutionnel. Cette méthode, qui peut ainsi s’adapter à de nouveaux ensembles de données, s’avère être au moins aussi précis que les méthodes conventionnelles quand il s’agit de domaines qui leur sont favorables, tout en étant beaucoup plus robuste dans des domaines plus générales. Dans le deuxième article, nous construisons une nouvelle architecture pour la manipulation d’images qui utilise l’idée que la majorité des pixels produits peuvent d’être copiés de l’image d’entrée. Cette technique bénéficie de plusieurs avantages majeurs par rapport à l’approche conventionnelle en apprentissage profond. En effet, elle conserve les détails de l’image d’origine, n’introduit pas d’aberrations grâce à la capacité limitée du réseau sous-jacent et simplifie l’apprentissage. Nous démontrons l’efficacité de cette architecture dans le cadre d’une tâche de correction du regard, où notre système produit d’excellents résultats. Dans le troisième article, nous nous éclipsons de la vision artificielle pour étudier le problème plus générale de l’adaptation à de nouveaux domaines. Nous développons un nouvel algorithme d’apprentissage, qui assure l’adaptation avec un objectif auxiliaire à la tâche principale. Nous cherchons ainsi à extraire des motifs qui permettent d’accomplir la tâche mais qui ne permettent pas à un réseau dédié de reconnaître le domaine. Ce réseau est optimisé de manière simultané avec les motifs en question, et a pour tâche de reconnaître le domaine de provenance des motifs. Cette technique est simple à implémenter, et conduit pourtant à l’état de l’art sur toutes les tâches de référence. Enfin, le quatrième article présente un nouveau type de modèle génératif d’images. À l’opposé des approches conventionnels à base de réseaux de neurones convolutionnels, notre système baptisé SPIRAL décrit les images en termes de programmes bas-niveau qui sont exécutés par un logiciel de graphisme ordinaire. Entre autres, ceci permet à l’algorithme de ne pas s’attarder sur les détails de l’image, et de se concentrer plutôt sur sa structure globale. L’espace latent de notre modèle est, par construction, interprétable et permet de manipuler des images de façon prévisible. Nous montrons la capacité et l’agilité de cette approche sur plusieurs bases de données de référence. / In the present thesis, we study how deep neural networks can be applied to various tasks in computer vision. Computer vision is an interdisciplinary field that deals with understanding of digital images and video. Traditionally, the problems arising in this domain were tackled using heavily hand-engineered adhoc methods. A typical computer vision system up until recently consisted of a sequence of independent modules which barely talked to each other. Such an approach is quite reasonable in the case of limited data as it takes major advantage of the researcher's domain expertise. This strength turns into a weakness if some of the input scenarios are overlooked in the algorithm design process. With the rapidly increasing volumes and varieties of data and the advent of cheaper and faster computational resources end-to-end deep neural networks have become an appealing alternative to the traditional computer vision pipelines. We demonstrate this in a series of research articles, each of which considers a particular task of either image analysis or synthesis and presenting a solution based on a ``deep'' backbone. In the first article, we deal with a classic low-level vision problem of edge detection. Inspired by a top-performing non-neural approach, we take a step towards building an end-to-end system by combining feature extraction and description in a single convolutional network. The resulting fully data-driven method matches or surpasses the detection quality of the existing conventional approaches in the settings for which they were designed while being significantly more usable in the out-of-domain situations. In our second article, we introduce a custom architecture for image manipulation based on the idea that most of the pixels in the output image can be directly copied from the input. This technique bears several significant advantages over the naive black-box neural approach. It retains the level of detail of the original images, does not introduce artifacts due to insufficient capacity of the underlying neural network and simplifies training process, to name a few. We demonstrate the efficiency of the proposed architecture on the challenging gaze correction task where our system achieves excellent results. In the third article, we slightly diverge from pure computer vision and study a more general problem of domain adaption. There, we introduce a novel training-time algorithm (\ie, adaptation is attained by using an auxilliary objective in addition to the main one). We seek to extract features that maximally confuse a dedicated network called domain classifier while being useful for the task at hand. The domain classifier is learned simultaneosly with the features and attempts to tell whether those features are coming from the source or the target domain. The proposed technique is easy to implement, yet results in superior performance in all the standard benchmarks. Finally, the fourth article presents a new kind of generative model for image data. Unlike conventional neural network based approaches our system dubbed SPIRAL describes images in terms of concise low-level programs executed by off-the-shelf rendering software used by humans to create visual content. Among other things, this allows SPIRAL not to waste its capacity on minutae of datasets and focus more on the global structure. The latent space of our model is easily interpretable by design and provides means for predictable image manipulation. We test our approach on several popular datasets and demonstrate its power and flexibility.

Dans cette thèse, nous étudions deux problèmes d'apprentissage automatique : (I) la détection des communautés et (II) l'appariement adaptatif. I) Il est bien connu que beaucoup de réseaux ont une structure en communautés. La détection de ces communautés nous aide à comprendre et exploiter des réseaux de tout genre. Cette thèse considère principalement la détection des communautés par des méthodes spectrales utilisant des vecteurs propres associés à des matrices choisiesavec soin. Nous faisons une analyse de leur performance sur des graphes artificiels. Au lieu du modèle classique connu sous le nom de « Stochastic Block Model » (dans lequel les degrés sont homogènes) nous considérons un modèle où les degrés sont plus variables : le « Degree-Corrected Stochastic Block Model » (DC-SBM). Dans ce modèle les degrés de tous les nœuds sont pondérés - ce qui permet de générer des suites des degrés hétérogènes. Nous étudions ce modèle dans deux régimes: le régime dense et le régime « épars », ou « dilué ». Dans le régime dense, nous prouvons qu'un algorithme basé sur une matrice d'adjacence normalisée réussit à classifier correctement tous les nœuds sauf une fraction négligeable. Dans le régime épars il existe un seuil en termes de paramètres du modèle en-dessous lequel n'importe quel algorithme échoue par manque d'information. En revanche, nous prouvons qu'un algorithme utilisant la matrice « non-backtracking » réussit jusqu'au seuil - cette méthode est donc très robuste. Pour montrer cela nous caractérisons le spectre des graphes qui sont générés selon un DC-SBM dans son régime épars. Nous concluons cette partie par des tests sur des réseaux sociaux. II) Les marchés d'intermédiation en ligne tels que des plateformes de Question-Réponse et des plateformes de recrutement nécessitent un appariement basé sur une information incomplète des deux parties. Nous développons un modèle de système d'appariement entre tâches et serveurs représentant le comportement de telles plateformes. Pour ce modèle nous donnons une condition nécessaire et suffisante pour que le système puisse gérer un certain flux de tâches. Nous introduisons également une politique de « back-pressure » sous lequel le débit gérable par le système est maximal. Nous prouvons que cette politique atteint un débit strictement plus grand qu'une politique naturelle « gloutonne ». Nous concluons en validant nos résultats théoriques avec des simulations entrainées par des données de la plateforme Stack-Overflow. / In this thesis, we study two problems of machine learning: (I) community detection and (II) adaptive matching. I) It is well-known that many networks exhibit a community structure. Finding those communities helps us understand and exploit general networks. In this thesis we focus on community detection using so-called spectral methods based on the eigenvectors of carefully chosen matrices. We analyse their performance on artificially generated benchmark graphs. Instead of the classical Stochastic Block Model (which does not allow for much degree-heterogeneity), we consider a Degree-Corrected Stochastic Block Model (DC-SBM) with weighted vertices, that is able to generate a wide class of degree sequences. We consider this model in both a dense and sparse regime. In the dense regime, we show that an algorithm based on a suitably normalized adjacency matrix correctly classifies all but a vanishing fraction of the nodes. In the sparse regime, we show that the availability of only a small amount of information entails the existence of an information-theoretic threshold below which no algorithm performs better than random guess. On the positive side, we show that an algorithm based on the non-backtracking matrix works all the way down to the detectability threshold in the sparse regime, showing the robustness of the algorithm. This follows after a precise characterization of the non-backtracking spectrum of sparse DC-SBM's. We further perform tests on well-known real networks. II) Online two-sided matching markets such as Q&A forums and online labour platforms critically rely on the ability to propose adequate matches based on imperfect knowledge of the two parties to be matched. We develop a model of a task / server matching system for (efficient) platform operation in the presence of such uncertainty. For this model, we give a necessary and sufficient condition for an incoming stream of tasks to be manageable by the system. We further identify a so-called back-pressure policy under which the throughput that the system can handle is optimized. We show that this policy achieves strictly larger throughput than a natural greedy policy. Finally, we validate our model and confirm our theoretical findings with experiments based on user-contributed content on an online platform.