Cette thèse porte sur un certain nombre de problèmes algorithmiques motivés par la planification temporelle automatisée et la vérification formelle des systèmes réactifs et finis. Nous nous sommes concentrés sur les méthodes théoriques des jeux pour obtenir de nouvelles connaissances, des limites de complexité améliorées et des algorithmes plus rapides pour les modèles suivants: réseaux temporels hyper, réseaux conditionnels Simples / Hyper temporels, jeux de mise à jour, jeux Muller McNaughton et jeux Mean Payoff / This dissertation deals with a number of algorithmic problems motivated by automated temporal planning and formal verification of reactive and finite state systems. We focused on game theoretical methods to obtain novel insights, improved complexity bounds, and faster algorithms for the following models: Hyper Temporal Networks, Conditional Simple/Hyper Temporal Networks, Update Games, Muller McNaughton Games, and Mean Payoff Games

Les approches de simulation classiques ne sont en général pas adaptées pour traiter les aspects de complexité que présentent les systèmes complexes tels que l'émergence ou l'adaptation. Dans cette thèse, l'auteur s'appuie sur ses travaux menés dans le cadre d'un projet de simulation sur l’épidémie de grippe en France associée à des interventions sur une population en considérant le phénomène étudié comme un processus diffusif sur un réseau complexe d'individus, l'originalité réside dans le fait que la population y est considérée comme un système réactif. La modélisation de tels systèmes nécessite de spécifier explicitement le comportement des individus et les réactions de ceux-cis tout en produisant un modèle informatique qui doit être à la fois flexible et réutilisable. Les diagrammes d'états sont proposés comme une approche de programmation reposant sur une modélisation validée par l'expertise. Ils correspondent également à une spécification du code informatique désormais disponibles dans les outils logiciels de programmation agent. L'approche agent de type bottom-up permet d'obtenir des simulations de scénario "what-if" où le déroulement des actions peut nécessiter que les agents s'adaptent aux changements de contexte. Cette thèse propose également l'apprentissage pour un agent par l'emploi d'arbre de décision afin d'apporter flexibilité et lisibilité pour la définition du modèle de comportement des agents et une prise de décision adaptée au cours de la simulation. Notre approche de modélisation computationnelle est complémentaire aux approches traditionnelles et peut se révéler indispensable pour garantir une approche pluridisciplinaire validable par l'expertise. / Traditional approaches are not sufficient, and sometimes impossible in dealing with complexity issues such as emergence, self-organization, evolution and adaptation of complex systems. As illustrated in this thesis by the practical work of the author in a real-life project, the spreading of infectious disease as well as interventions could be considered as difusion processes on complex networks of heterogeneous individuals in a society which is considered as a reactive system. Modeling of this system requires explicitly specifying of each individual’s behaviors and (re)actions, and transforming them into computational model which has to be flexible, reusable, and ease of coding. Statechart, typical for model-based programming, is a good solution that the thesis proposes. Bottom-up agent based simulation finds emergence episodes in what-if scenarios that change rules governing agent’s behaviors that requires agents to learn to adapt with these changes. Decision tree learning is proposed to bring more flexibility and legibility in modeling of agent’s autonomous decision making during simulation runtime. Our proposition for computational models such as agent based models are complementary to traditional ones, and in some case they are unique solutions due to legal, ethical issues.

Cette thèse examine une nouvelle façon d'étudier l'impact d'une voie de signalisation donnée sur l'évolution d'un tissu grâce à l'analyse multi-niveaux. Cette analyse est divisée en deux parties principales: La première partie considère les modèles décrivant la voie au niveau cellulaire. A l'aide de ces modèles, on peut calculer de manière résoluble la dynamique d'un groupe de cellules, en le représentant par une distribution multivariée sur des concentrations de molécules clés. La deuxième partie propose un modèle 3d de croissance tissulaire qui considère la population de cellules comme un ensemble de sous-populations, partitionnée de façon à ce que chaque sous-population partage les mêmes conditions externes. Pour chaque sous-population, le modèle résoluble présenté dans la première partie peut être utilisé. Cette thèse se concentre principalement sur la première partie, tandis qu'un chapitre couvre un projet de modèle pour la deuxième partie. / This thesis examines a new way to study the impact of a given pathway on the dynamics of a tissue through Multi-Level Analysis. The analysis is split in two main parts: The first part considers models describing the pathway at the cellular level. Using these models, one can compute in a tractable manner the dynamics of a group of cells, representing it by a multivariate distribution over concentrations of key molecules. % of the distribution of the states of this pathway through groups of cells. The second part proposes a 3d model of tissular growth that considers the population of cell as a set of subpopulations, partitionned such as each subpopulation shares the same external conditions. For each subpopulation, the tractable model presented in the first part can be used. This thesis focuses mainly on the first part, whereas a chapter covers a draft of a model for the second part.

A l'ère d'Internet, la classification informatisée des images est d'une importance cruciale pour l’utilisation efficace de l'énorme quantité de données visuelles qui sont disponibles. Mais comment les ordinateurs peuvent-ils comprendre la signification d'une image? La Recherche d’Information Multimédia (RIM) est un domaine de recherche qui vise à construire des systèmes capables de reconnaître automatiquement le contenu d’une image. D'abord, des caractéristiques de bas niveau sont extraites et regroupées en signatures visuelles compactes. Ensuite, des techniques d'apprentissage automatique construisent des modèles qui font la distinction entre les différentes catégories d'images à partir de ces signatures. Ces modèles sont finalement utilisés pour reconnaître les propriétés d'une nouvelle image. Malgré les progrès dans le domaine, ces systèmes ont des performances en général limitées. Dans cette thèse, nous concevons un ensemble de contributions originales pour chaque étape de la chaîne RIM, en explorant des techniques provenant d'une variété de domaines qui ne sont pas traditionnellement liés avec le MMIR. Par exemple, nous empruntons la notion de saillance et l'utilisons pour construire des caractéristiques de bas niveau. Nous employons la théorie des Copulae étudiée en statistique économique, pour l'agrégation des caractéristiques. Nous réutilisons la notion de pertinence graduée, populaire dans le classement des pages Web, pour la récupération visuelle. Le manuscrit détaille nos solutions novatrices et montre leur efficacité pour la catégorisation d'image et de vidéo, et l’évaluation de l'esthétique. / In the internet era, computerized classification and discovery of image properties (objects, scene, emotions generated, aesthetic traits) is of crucial importance for the automatic retrieval of the huge amount of visual data surrounding us. But how can computers see the meaning of an image? Multimedia Information Retrieval (MMIR) is a research field that helps building intelligent systems that automatically recognize the image content and its characteristics. In general, this is achieved by following a chain process: first, low-level features are extracted and pooled into compact image signatures. Then, machine learning techniques are used to build models able to distinguish between different image categories based on such signatures. Such model will be finally used to recognize the properties of a new image. Despite the advances in the field, human vision systems still substantially outperform their computer-based counterparts. In this thesis we therefore design a set of novel contributions for each step of the MMIR chain, aiming at improving the global recognition performances. In our work, we explore techniques from a variety of fields that are not traditionally related with Multimedia Retrieval, and embed them into effective MMIR frameworks. For example, we borrow the concept of image saliency from visual perception, and use it to build low-level features. We employ the Copula theory of economic statistics for feature aggregation. We re-use the notion of graded relevance, popular in web page ranking, for visual retrieval frameworks. We explain in detail our novel solutions and prove their effectiveness for image categorization, video retrieval and aesthetics assessment.

Cette thèse entend proposer un concept technologique – c’est-à-dire non-anthropocentré – de trace numérique. Il s’agit de rappeler que l’informatique exigeant des objets et des actes qu’ils passent par l’inscription pour exister, les machines computationnelles sont parties prenantes des processus de production des traces numériques, qu’une « sémiotique technologique » permettrait de décrire. L’enjeu d’un tel concept est de mettre en circulation une narration qui ne soit pas de l’ordre de ces discours de fin de monde décrits par Déborah Danowski et Eduardo Viveiros de Castro. Ces discours racontent la vie d’humains réduits à habiter un environnement ontologiquement dévitalisé et artificialisé, comme cela semble être le cas lorsque la valorisation technique et économique des traces numériques débouche sur une « délégation machinique de nos relations » (Louise Merzeau) ou encore sur une « gouvernementalité algorithmique » (Antoinette Rouvroy et Thomas Berns). À partir du moment où il y a des discours de fin de monde cependant, c’est qu’une tentative est à l’œuvre : celle qui consiste à inventer une mythologie adéquate à notre présent, celle qui essaie de dire quelque chose de la fin d’une certaine aventure anthropologique. Et c’est pour participer à cette tentative, tout en cherchant à éviter de contribuer aux discours de fin de monde, qu’une approche technologique des traces numériques à même de faire compter les machines computationnelles est proposée. / This Ph.D. thesis aims at proposing a concept that is technological – inother words, not anthropocentric – of digital traces. The point is that since computational processes require objects and actions to take the form of inscriptions as a condition of their existence, computational machines are fundamentally involved in the process of producing digital traces, which a technological semiotics could describe. What is at stake in the concept we propose is to put into circulation a narration which avoids the theme of “the end of the world” described by Déborah Danowski and Eduardo Viveiros de Castro. These “end of the world” stories evoke the life of human beings who are reduced to living in an environment that is ontologically devitalized and purely artificial, as it seems to be the case when the technical and economic valorization of digital traces has the end result of “delegating our human relations to machines” (Louise Merzeau) or yet again of leading to “algorithmic governmentality” (Antoinette Rouvroy and Berns). When the theme of “the end of the world” raises its head, it means that an attempt is being made : an attempt to invent a mythology appropriate to our present situation, a narration which tries to say something about the end of a certain anthropological adventure. And it is in order to participate in this venture, but seeking to avoid contributing to the theme of “the end of the world”, that we propose a technological approach to digital traces, enabling us to take into account computational machines as a part of the contemporary world.

L'équation intégrale du champ électrique (EFIE) et l'équation intégrale du champ combiné (CFIE) souffrent d'un mauvais conditionnement à haute discrétisation et à bassefréquence : si la taille moyenne des arrêtes du maillage est réduite ou si la fréquence est diminuée le conditionnement du système se dégrade rapidement. Cela provoque le ralentissement ou la non convergence des solveurs itératifs. Cette dissertation présente de nouveaux paradigmes permettant l'obtention de solveurs à convergence rapide pour équations intégrales; pour prévenir la dégradation du conditionnement nous avançons l'état de l'art des techniques de préconditionnement dites de Calderon et de celles reposant sur l'utilisation des bases hiérarchiques. Pour traiter l'EFIE, nous introduisons une base hiérarchique pour maillages structurés et non-structurés dérivant des pré-ondelettes primaires et duales de Haar. De plus, nous introduisons un nouveau cadre permettant de préconditionner efficacement l'EFIE dans le cas d'objets à connexion multiples. L'applicabilité à la CFIE des préconditionneurs à bases hiérarchiques fait l'objet d'une étude aboutissant à la formalisation d'une technique de préconditionnement. Nous présentons aussi un préconditionneur multiplicatif de type Calderon (RF-CMP) qui permet l'obtention d'une matrice système Hermitienne, définie positive (HDP) et bien conditionnée, sans avoir recours, contrairement aux préconditionneurs existants, au raffinement du maillage ni à l'utilisation de fonction duales. Puisque la matrice est HPD, la méthode du gradient conjugué peut servir de solveur itératif avec une convergence garantie. / The electric field integral equation (EFIE) and the combined field integral equation(CFIE) suffer from the dense-discretization and the low-frequency breakdown: if the average edgelength of the mesh is reduced, or if the frequency is decreased, then the condition number of the system matrix grows. This leads to slowly or non-converging iterative solvers. This dissertation presents new paradigms for rapidly converging integral equation solvers: to overcome the illconditioning, we advance and extend the state of the art both in hierarchical basis and in Calderón preconditioning techniques. For the EFIE, we introduce a hierarchical basis for structured and unstructured meshes based on generalized primal and dual Haar prewavelets. Furthermore, a framework is introduced which renders the hierarchical basis able to efficiently precondition the EFIE in the case that the scatterer is multiply connected. The applicability of hierarchical basis preconditioners to the CFIE is analyzed and an efficient preconditioning scheme is derived. In addition, we present a refinement-free Calderón multiplicative preconditioner (RF-CMP) that yields a system matrix which is Hermitian, positive definite (HPD), and well-conditioned. Different from existing Calderón preconditioners, no dual basis functions and thus no refinement of the mesh is required. Since the matrix is HPD—in contrast to standard discretizations of the EFIE—we can apply the conjugate gradient (CG) method as iterative solver, which guarantees convergence. Eventually, the RF-CMP is extended to the CFIE.

Dans ce travail de thèse, nous avons modélisé le rôle de la dopamine dans l'apprentissage et dans les processus de sélection de l'action en lien avec les ganglions de la base. L'activité des neurones dopaminergiques présente de nombreuses similarités avec l'erreur de prédiction de la récompense utilisée par les algorithmes d'apprentissage par renforcement. Ainsi, ces neurones sont supposés guider le processus de sélection de l'action.Dans une première partie, nous avons analysé l'information encodée par les neurones dopaminergiques dans une tâche à choix multiples en la comparant à différentes informations utilisées par les modèles d'apprentissage par renforcement. Nos résultats suggèrent que l'information encodée par les neurones dopaminergiques enregistrer dans la tâche n'est que partiellement compatible avec une erreur de prédiction et semble en partie dissociée du comportement.Dans une deuxième partie, nous avons simulé l'effet de la dopamine sur un modèle des ganglions de la base prenant en compte des connections existant chez le primate, souvent négligées dans la littérature. La plupart des modèles actuels font en effet l'hypothèse d'une séparation stricte de deux chemins dans les ganglions de la base : le chemin direct lié à la récompense et le chemin indirect lié à la punition. Cependant des études anatomiques remettent en question cette dissociation, en particulier chez le primate. Nous proposons ainsi d'étudier comment différents niveaux de dopamine, dans le contexte de la maladie de Parkinson, affectent l'apprentissage et la sélection de l'action dans ce modèle / In this thesis work, we modelled the role of dopamine in learning and in the processes of action selection through its interaction with the basal ganglia. During the 90’s, the work of Schultz and colleagues has led to major progress in understanding the neural mechanisms underlying the influence of feedback on learning. The activity of dopaminergic neurons exhibited properties of the reward prediction error signal used in so-called Temporal Difference (TD) machine learning algorithms. Thus, DA has been thought to be the neural signal that help us to adapt our behavior. In the first part of my PhD, we analyze the information encoded by dopaminergic neurons recorded during a multi-choice task. In this purpose, we modeled the task and simulated different TD learning algorithms to quantitatively compare their ability to reproduce dopamine neurons activity. Our results show that the information carried out by dopamine neurons is only partly consistent with a reward prediction error and seems to be dissociated from behavioral adaptation.In the second part of my PhD, we study the effect of different levels of dopamine in a biologically plausible model of primates basal ganglia that considers existing connections often neglected in the literature. Indeed, most of current models of basal ganglia assume the existence of two segregated pathway: the direct pathway associated with reward and the indirect pathway associated with punishment. However, anatomical studies in primates revealed that these two pathways are not dissociated. We study the ability of such a model to reproduce beta oscillations observed in Parkinsonian and the differences in reward and punishment sensitivity, with high or low-level of dopamine.

Cette thèse présente quelques idées pour l'accélération des calculs ab initio de systèmes physico-chimiques. Après une introduction générale aux modèles et aux méthodes faite au chapitre 1, le chapitre 2 est consacré à une présentation mathématique de la construction des pseudo-potentiels qui mènent à une réduction considérable de la taille du problème électronique. On s'intéresse ensuite au problème aux valeurs propres généralisé qui constitue l'étape limitante de la résolution du problème électronique. On propose dans le chapitre 3 une méthode de décomposition de domaine de complexité linéaire avec le nombre d'électrons du système en terme de temps CPU et d'encombrement mémoire. Cette méthode, adaptée au traitement des systèmes isolants, remédie à certaines insuffisances des méthodes existantes. Dans le même esprit, le chapitre 4 est dédié à une tentative d'adaptation des méthodes dites de projection pour le traitement des gros systèmes métalliques. Un autre problème est abordé au chapitre 5. Il s'agit de l'application de la méthode des bases réduites au problème électronique. Dans un premier temps, des résultats montrant la faisabilité de l'approche ont été obtenus sur les systèmes H2+ et H2 où la base de discrétisation pour la résolution du problème électronique dépend de la position des noyaux, paramètres du système. Dans un second temps, une adaptation de la méthode des bases réduites pour traiter un problème non linéaire est présentée. Le chapitre 6 présente enfin des conclusions générales sur l'ensemble des approches abordées dans la thèse, ainsi que quelques pistes pour des développements futurs.

Nous nous intéressons à l'extension des méthodes de segmentation bayésienne reposant sur le modèle de chaîne de Markov cachée, utilisé classiquement en traitement du signal. Nos travaux se sont développés selon trois axes : la remise en cause de la structure du modèle classique par l'utilisation des modèles de chaînes de Markov couple, et la recherche de familles de lois pertinentes pour les données multidimensionnelles afin de traiter les observations complexes obtenues par les radars modernes, notamment à l'aide des copules. Un troisième axe consiste en l'estimation de ces modèles. Nous proposons une méthode d'estimation des paramètres des modèles à données manquantes fondée sur les fonctions estimantes, ce qui permet de choisir des fonctions moins complexes que la vraisemblance. En exploitant la structure cachée, nous proposons un algorithme itératif généralisant EM. Nous donnons alors de nouveaux estimateurs pour les modèles décrits à l'aide de copules. Nous obtenons ainsi des algorithmes d'estimation remarquablement simples pour les modèles de Markov couples, et nous montrons leur bon comportement sur données simulées et sur données radar.

A l'ère d'Internet, la classification informatisée des images est d'une importance cruciale pour l'utilisation efficace de l'énorme quantité de données visuelles qui sont disponibles. Mais comment les ordinateurs peuvent-ils comprendre la signification d'une image? La Recherche d'Information Multimédia (RIM) est un domaine de recherche qui vise à construire des systèmes capables de reconnaître automatiquement le contenu d'une image. D'abord, des caractéristiques de bas niveau sont extraites et regroupées en signatures visuelles compactes. Ensuite, des techniques d'apprentissage automatique construisent des modèles qui font la distinction entre les différentes catégories d'images à partir de ces signatures. Ces modèles sont finalement utilisés pour reconnaître les propriétés d'une nouvelle image. Malgré les progrès dans le domaine, ces systèmes ont des performances en général limitées. Dans cette thèse, nous concevons un ensemble de contributions originales pour chaque étape de la chaîne RIM, en explorant des techniques provenant d'une variété de domaines qui ne sont pas traditionnellement liés avec le MMIR. Par exemple, nous empruntons la notion de saillance et l'utilisons pour construire des caractéristiques de bas niveau. Nous employons la théorie des Copulae étudiée en statistique économique, pour l'agrégation des caractéristiques. Nous réutilisons la notion de pertinence graduée, populaire dans le classement des pages Web, pour la récupération visuelle. Le manuscrit détaille nos solutions novatrices et montre leur efficacité pour la catégorisation d'image et de vidéo, et l'évaluation de l'esthétique.