La théorie du processus dual stipule que la cognition humaine fonctionne selon deux modes distincts : l’un pour le traitement rapide, habituel et associatif, appelé communément "système 1" et le second, ayant un traitement plus lent, délibéré et contrôlé, que l’on nomme "système 2". Cette distinction indique une caractéristique sous-jacente importante de la cognition humaine : la possibilité de passer de manière adaptative à différentes stratégies de calcul selon la situation. Cette capacité est étudiée depuis longtemps dans différents domaines et de nombreux bénéfices hypothétiques semblent y être liés. Cependant, les réseaux neuronaux profonds sont souvent construits sans cette capacité à gérer leurs ressources calculatoires de manière optimale. Cette limitation des modèles actuels est d’autant plus préoccupante que de plus en plus de travaux récents semblent montrer une relation linéaire entre la capacité de calcul utilisé et les performances du modèle lors de la phase d’évaluation. Pour résoudre ce problème, ce mémoire propose différentes approches et étudie leurs impacts sur les modèles, tout d’abord, nous étudions un agent d’apprentissage par renforcement profond qui est capable d’allouer plus de calcul aux situations plus difficiles. Notre approche permet à l’agent d’adapter ses ressources computationnelles en fonction des exigences de la situation dans laquelle il se trouve, ce qui permet en plus d’améliorer le temps de calcul, améliore le transfert entre des tâches connexes et la capacité de généralisation. L’idée centrale commune à toutes nos approches est basée sur les théories du coût de l’effort venant de la littérature sur le contrôle cognitif qui stipule qu’en rendant l’utilisation de ressource cognitive couteuse pour l’agent et en lui laissant la possibilité de les allouer lors de ses décisions il va lui-même apprendre à déployer sa capacité de calcul de façon optimale. Ensuite, nous étudions des variations de la méthode sur une tâche référence d’apprentissage profond afin d’analyser précisément le comportement du modèle et quels sont précisément les bénéfices d’adopter une telle approche. Nous créons aussi notre propre tâche "Stroop MNIST" inspiré par le test de Stroop utilisé en psychologie afin de valider certaines hypothèses sur le comportement des réseaux neuronaux employant notre méthode. Nous finissons par mettre en lumière les liens forts qui existent entre apprentissage dual et les méthodes de distillation des connaissances. Notre approche a la particularité d’économiser des ressources computationnelles lors de la phase d’inférence. Enfin, dans la partie finale, nous concluons en mettant en lumière les contributions du mémoire, nous détaillons aussi des travaux futurs, nous approchons le problème avec les modèles basés sur l’énergie, en apprenant un paysage d’énergie lors de l’entrainement, le modèle peut ensuite lors de l’inférence employer une capacité de calcul dépendant de la difficulté de l’exemple auquel il fait face plutôt qu’une simple propagation avant fixe ayant systématiquement le même coût calculatoire. Bien qu’ayant eu des résultats expérimentaux infructueux, nous analysons les promesses que peuvent tenir une telle approche et nous émettons des hypothèses sur les améliorations potentielles à effectuer. Nous espérons, avec nos contributions, ouvrir la voie vers des algorithmes faisant un meilleur usage de leurs ressources computationnelles et devenant par conséquent plus efficace en termes de coût et de performance, ainsi que permettre une compréhension plus intime des liens qui existent entre certaines méthodes en apprentissage machine et la théorie du processus dual. / The dual-process theory states that human cognition operates in two distinct modes: one for rapid, habitual and associative processing, commonly referred to as "system 1", and the second, with slower, deliberate and controlled processing, which we call "system 2". This distinction points to an important underlying feature of human cognition: the ability to switch adaptively to different computational strategies depending on the situation. This ability has long been studied in various fields, and many hypothetical benefits seem to be linked to it. However, deep neural networks are often built without this ability to optimally manage their computational resources. This limitation of current models is all the more worrying as more and more recent work seems to show a linear relationship between the computational capacity used and model performance during the evaluation phase. To solve this problem, this thesis proposes different approaches and studies their impact on models. First, we study a deep reinforcement learning agent that is able to allocate more computation to more difficult situations. Our approach allows the agent to adapt its computational resources according to the demands of the situation in which it finds itself, which in addition to improving computation time, enhances transfer between related tasks and generalization capacity. The central idea common to all our approaches is based on cost-of-effort theories from the cognitive control literature, which stipulate that by making the use of cognitive resources costly for the agent, and allowing it to allocate them when making decisions, it will itself learn to deploy its computational capacity optimally. We then study variations of the method on a reference deep learning task, to analyze precisely how the model behaves and what the benefits of adopting such an approach are. We also create our own task "Stroop MNIST" inspired by the Stroop test used in psychology to validate certain hypotheses about the behavior of neural networks employing our method. We end by highlighting the strong links between dual learning and knowledge distillation methods. Finally, we approach the problem with energy-based models, by learning an energy landscape during training, the model can then during inference employ a computational capacity dependent on the difficulty of the example it is dealing with rather than a simple fixed forward propagation having systematically the same computational cost. Despite unsuccessful experimental results, we analyze the promise of such an approach and speculate on potential improvements. With our contributions, we hope to pave the way for algorithms that make better use of their computational resources, and thus become more efficient in terms of cost and performance, as well as providing a more intimate understanding of the links that exist between certain machine learning methods and dual process theory.

Cette thèse se penche sur les modèles de choix, des distributions sur des ensembles d'alternatives. Les modèles de choix sur les processus décisionnels de Markov (MDP) peuvent décomposer de très grands espaces alternatifs en procédures étape par étape conçues pour non seulement combattre la malédiction de la dimensionnalité mais aussi pour mieux refléter la dynamique sous-jacente. La première partie est consacrée à l'estimation du temps de trajet dans le cadre de la modélisation du choix de chemin. Les modèles de choix de chemin sont des modèles de choix sur l'ensemble des chemins utilisés pour modéliser le flux de circulation. Intuitivement, le temps de trajet est l'une des caractéristiques les plus importantes lors du choix des chemins, mais les temps de trajet ne sont pas toujours connus. En revanche, le cadre classique suppose que ces deux étapes sont séquentielles, car les temps de trajet des arcs font partie de l'entrée du processus d'estimation du choix de chemin. Pourtant, les interdépendances complexes signifient que ce modèle de choix de chemin peut complémenter toute observation lors de l'estimation des temps de trajet. Nous construisons un modèle statistique pour l'estimation du temps de trajet et proposons de marginaliser les caractéristiques non observées. En utilisant ces idées, nous montrons que nous sommes capables d'apprendre des modèles de choix de chemin sans observer de chemins réels et à différentes granularités. La deuxième partie se concentre sur les échecs des MDP régularisés et comment la régularisation peut avoir des effets secondaires inattendus, tels que la divergence dans les chemins stochastiques les plus courts ou des fonctions de valeur déraisonnablement grandes. Les MDP régularisés ne sont rien d'autre qu'une application des modèles de choix aux MDP. Ils sont utilisés dans l'apprentissage par renforcement (RL) pour obtenir, entre autres choses, un modèle de choix sur les trajectoires possibles pour l'apprentissage par renforcement inverse, transférer des connaissances préalables au modèle, ou obtenir des politiques qui exploitent tous les objectifs dans l'environnement. Ces effets secondaires sont exacerbés dans les espaces d'action dépendants de l'état. Comme mesure d'atténuation, nous introduisons deux transformations potentielles, et nous évaluons leur performance sur un problème de conception de médicaments. / This thesis delves on choice models, distributions on sets of alternatives. Choice models on Markov decision processes (MDPs) can break down very large alternative spaces into step-by-step procedures designed to not only tackle the curse of dimensionality but also to reflect the underlying dynamics better. The first part is devoted to travel time estimation as part of path choice modeling. Path choice models are choice models on the set of paths used to model traffic flow. Intuitively, travel time is one of the more important features when choosing paths, yet travel times are not always known. In contrast, the classical setting assumes that these two steps are sequential, as arc travel times are part of the input of the path choice estimation process. Yet the intricate interdependences mean that that path choice model can complement any observation when estimating travel times. We build a statistical model for travel time estimation and propose marginalizing the unobserved features. Using these ideas, we show that we are able to learn path choice models without observing actual paths and at different granularity. The second part focuses on the failings of regularized MDPs and how regularization may have unexpected side effects, such as divergence in stochastic shortest paths or unreasonably large value functions. Regularized MDPs are nothing but an application of choice models to MDPs. They are used in reinforcement learning (RL) to get, among other things, a choice model on possible trajectories for inverse reinforcement learning, transfer prior knowledge to the model, or to get policies that exploit all goals in the environment. These side effects are exacerbated in state-dependent action spaces. As a mitigation, we introduce two potential transformations, and we benchmark their performance on a drug design problem.

Cette thèse s’intéresse au problème classique de tournées de véhicules avec contraintes de capacité (CVRP pour Capacitated Vehicle Routing Problem) ainsi qu’une variante beaucoup plus complexe, soit le problème de tournées de véhicules dépendant du temps avec fenêtres de temps et points de transfert défini sur un réseau routier (TDVRPTWTP-RN pour Time-Dependent Vehicle Routing Problem with Time Windows and Transfer Points on a Road Network). Dans le premier article, le TDVRPTWTP-RN est résolu en adaptant une métaheuristique qui représente l’état de l’art pour le CVRP, appelé Slack Induction for String Removals (SISR). Cette métaheuristique fait appel au principe “détruire et reconstruire” en retirant des séquences de clients consécutifs dans les routes de la solution courante et en réinsérant ensuite ces clients de façon à créer une nouvelle solution. Le problème est défini sur un réseau routier où différents chemins alternatifs peuvent être utilisés pour se déplacer d’un client à l’autre. De plus, le temps de parcours sur chacun des arcs du réseau n’est pas fixe, mais dépend du moment où le véhicule quitte le sommet origine. S’inspirant de problèmes rencontrés en logistique urbaine, nous considérons également deux types de véhicules, de petite et grande capacité, où les grands véhicules sont interdits de passage au centre-ville. Ainsi, les clients du centre-ville ne peuvent être servis que suite au transfert de leur demande d’un grand à un petit véhicule à un point de transfert. Comme un point de transfert n’a pas de capacité, une problématique de synchronisation apparaît quand un grand véhicule doit y rencontrer un ou plusieurs petits véhicules pour leur transférer une partie de son contenu. Contrairement aux problèmes stricts de tournées de véhicules à deux échelons, les grands véhicules peuvent aussi servir des clients localisés à l’extérieur du centre-ville. Comme le problème abordé est beaucoup plus complexe que le CVRP, des modifications importantes ont dû être apportées à la métaheuristique SISR originale. Pour évaluer la performance de notre algorithme, un ensemble d’instances tests a été généré à partir d’instances existantes pour le TDVRPTW-RN. Les réseaux omt été divisés en trois régions : centre-ville, frontière et extérieur. Le centre-ville et l’extérieur sont respectivemnt les royaumes des petits et grands véhicules, tandis que la frontière (où l’on retrouve les points de transfert) peut être visité par les deux types de véhicules. Les résultats numériques montrent que la métaheuristique proposée exploite les opportunités d’optimiser une solution en déplaçant autant que possible les clients neutres, soit ceux qui peuvent être servis indifféremment par un petit ou un grand véhicule, des routes des petits véhicules vers les routes des grands véhicules, réduisant ainsi les coûteuses visites aux points de transfert. Les deuxième et troisième article s’intéressent à des concepts plus fondamentaux et font appel au problème plus simple du CVRP pour les évaluer. Dans le second article, un étude expérimentale est conçue afin d’examiner l’impact de données (distances) imprécises sur la performance de différents types d’heuristiques, ainsi qu’une méthode exacte, pour le CVRP. À cette fin, différents niveaux d’imprécision ont été introduits dans des instances tests classiques pour le CVRP avec 100 à 1 000 clients. Nous avons observé que les meilleures métaheuristiques demeurent les meilleures, même en présence de hauts niveaux d’imprécision, et qu’elles ne sont pas affectées autant par les imprécisions qu’une heuristique simple. Des expériences avec des instances réelles ont mené aux mêmes conclusions. Le troisième article s’intéresse à l’intégration de l’apprentissage automatique dans la métaheuristique SISR qui représente l’état de l’art pour le CVRP. Dans ce travail, le principe “détruire et reconstruire” au coeur de SISR est hybridé avec une méthode d’apprentissage par renforcement qui s’inspire des systèmes de colonies de fourmis. L’ap- prentissage automatique a pour but d’identifier les arêtes les plus intéressantes, soit celles qui se retrouvent le plus fréquemment dans les solutions de grande qualité précédemment rencontrées au cours de la recherche. L’inclusion de telles arêtes est alors favorisé lors de la réinsertion des clients ayant été retirés de la solution par le mécanisme de destruction. Les instances utilisées pour tester notre approche hybride sont les mêmes que celles du second article. Nous avons observé que notre algorithme ne peut produire que des solutions lé- gèrement meilleures que la métaheuristique SISR originale, celle-ci étant déjà quasi-optimale. / This thesis is concerned both with the classical Capacitated Vehicle Routing Problem (CVRP) and a much more complex variant called the Time-Dependent Vehicle Routing Problem with Time Windows and Transfer Points on a Road Network (TDVRPTWTP-RN ). In the first paper, the TDVRPTWTP RN is solved by adapting a state-of-the-art metaheuris- tic for the CVRP, called Slack Induction for String Removals (SISR). This metaheuristic is based on the ruin and recreate principle and removes strings of consecutive customers in the routes of the current solution and then reinserts the removed customers to create a new solution. The problem is formulated in a full road network where different alternative paths can be used to go from one customer to the next. Also, the travel time on each arc of the road network is not fixed, but depends on the departure time from the origin node. Motivated from city logistics applications, we also consider two types of vehicles, large and small, with large vehicles being forbidden from the downtown area. Thus, downtown customers can only be served through a transfer of their goods from large to small vehicles at designated transfer points. Since transfer points have no capacity, synchronization issues arise when a large vehicle must meet one or more small vehicles to transfer goods. As opposed to strict two-echelon VRPs, large vehicles can also directly serve customers that are outside of the downtown area. Given that the TDVRPTWTP-RN is much more complex than the CVRP, important modifications to the original SISR metaheuristic were required. To evaluate the performance of our algorithm, we generated a set of test instances by extending existing instances of the TDVRPTW-RN . The road networks are divided into three regions: downtown, boundary and outside. The downtown and outside areas are the realm of small and large vehicles, respectively, while the boundary area that contains the transfer points can be visited by both small and large vehicles. The results show that the proposed metaheuristic exploits optimization opportunities by moving as much as possible neutral customers (which can be served by either small or large vehicles) from the routes of small vehicles to those of large vehicles, thus avoiding costly visits to transfer points. The second and third papers examine more fundamental issues, using the classical CVRP as a testbed. In the second paper, an experimental study is designed to examine the impact of inaccurate data (distances) on the performance of different types of heuristics, as well as one exact method, for the CVRP. For this purpose, different levels of distance inaccuracies were introduced into well-known benchmark instances for the CVRP with 100 to 1,000 customers. We observed that the best state-of-the-art metaheuristics remain the best, even in the presence of high inaccuracy levels, and that they are not as much affected by inaccuracies when compared to a simple heuristic. Some experiments performed on real-world instances led to the same conclusions. The third paper focuses on the integration of learning into the state-of-the-art SISR for the CVRP. In this work, the ruin and recreate mechanism at the core of SISR is enhanced by a reinforcement learning technique inspired from ant colony systems. The learning component is aimed at identifying promising edges, namely those that are often found in previously encountered high-quality solutions. The inclusion of these promising edges is then favored during the reinsertion of removed customers. The benchmark instances of the second paper were also used here to test the new hybrid algorithm. We observed that the latter can produce only slightly better solutions than the original SISR, due to the quasi-optimality of the original solutions.

Cette thèse par article se compose de quatre articles qui contribuent au domaine de l’apprentissage profond, en particulier dans la compréhension et l’apprentissage des ap- proches neuronales des systèmes de dialogue. Le premier article fait un pas vers la compréhension si les architectures de dialogue neuronal couramment utilisées capturent efficacement les informations présentes dans l’historique des conversations. Grâce à une série d’expériences de perturbation sur des ensembles de données de dialogue populaires, nous constatons que les architectures de dialogue neuronal couramment utilisées comme les modèles seq2seq récurrents et basés sur des transformateurs sont rarement sensibles à la plupart des perturbations du contexte d’entrée telles que les énoncés manquants ou réorganisés, les mots mélangés, etc. Le deuxième article propose d’améliorer la qualité de génération de réponse dans les systèmes de dialogue de domaine ouvert en modélisant conjointement les énoncés avec les attributs de dialogue de chaque énoncé. Les attributs de dialogue d’un énoncé se réfèrent à des caractéristiques ou des aspects discrets associés à un énoncé comme les actes de dialogue, le sentiment, l’émotion, l’identité du locuteur, la personnalité du locuteur, etc. Le troisième article présente un moyen simple et économique de collecter des ensembles de données à grande échelle pour modéliser des systèmes de dialogue orientés tâche. Cette approche évite l’exigence d’un schéma d’annotation d’arguments complexes. La version initiale de l’ensemble de données comprend 13 215 dialogues basés sur des tâches comprenant six domaines et environ 8 000 entités nommées uniques, presque 8 fois plus que l’ensemble de données MultiWOZ populaire. / This thesis by article consists of four articles which contribute to the field of deep learning, specifically in understanding and learning neural approaches to dialog systems. The first article takes a step towards understanding if commonly used neural dialog architectures effectively capture the information present in the conversation history. Through a series of perturbation experiments on popular dialog datasets, wefindthatcommonly used neural dialog architectures like recurrent and transformer-based seq2seq models are rarely sensitive to most input context perturbations such as missing or reordering utterances, shuffling words, etc. The second article introduces a simple and cost-effective way to collect large scale datasets for modeling task-oriented dialog systems. This approach avoids the requirement of a com-plex argument annotation schema. The initial release of the dataset includes 13,215 task-based dialogs comprising six domains and around 8k unique named entities, almost 8 times more than the popular MultiWOZ dataset. The third article proposes to improve response generation quality in open domain dialog systems by jointly modeling the utterances with the dialog attributes of each utterance. Dialog attributes of an utterance refer to discrete features or aspects associated with an utterance like dialog-acts, sentiment, emotion, speaker identity, speaker personality, etc. The final article introduces an embedding-free method to compute word representations on-the-fly. This approach significantly reduces the memory footprint which facilitates de-ployment in on-device (memory constraints) devices. Apart from being independent of the vocabulary size, we find this approach to be inherently resilient to common misspellings.