Les travaux présentés dans ce mémoire s'attachent à étudier le comportement des tunnels creusés à faible profondeur à l'aide d'un tunnelier à front pressurisé, en se penchant plus particulièrement sur deux aspects fondamentaux lors de l'excavation : la stabilité du front de taille à l'effondrement et au refoulement, et l'apparition de mouvements de sol en surface. L'étude est menée sous un angle déterministe puis probabiliste. Dans un premier temps, un certain nombre de modèles analytique de détermination des pressions limites d'effondrement et de refoulement sont développés à partir d'observations effectuées sur des modèles numériques. Deux de ces modèles analytiques présentent, respectivement pour des sols frottants et non frottants, des résultats très satisfaisants à la fois en termes de pressions limites et de faciès de rupture. Par ailleurs, des modèles numériques de différents degrés de complexité sont programmés afin d'évaluer les mouvements de sol induits par l'excavation et leur propagation jusqu'à la surface. Les modèles déterministes ainsi définis sont ensuite utilisés dans un cadre probabiliste. La méthode de la surface de réponse stochastique par collocation est présentée, validée, et perfectionnée afin de rendre possible pour un faible coût calculatoire des études paramétriques sur les propriétés probabilistes des variables d'entrée des modèles. La propagation de l'incertitude au travers des modèles déterministes de stabilité et de mouvements de sol est évaluée, et des méthodes de dimensionnement fiabiliste sont proposées. Dans une dernière partie, la variabilité spatiale du sol est prise en compte par l'intermédiaire de la théorie des champs aléatoires, et appliquée à un modèle analytique 2D d'effondrement d'un front de taille. Ce modèle, développé dans le but de prendre en compte cette variabilité spatiale pour des temps de calcul inférieurs à ceux des modèles numériques, est validé numériquement et soumis à des tirages aléatoires en grand nombre. L'effet de la variabilité est évaluée, et des phénomènes nouveaux liés à cette variabilité sont mis en lumière.

L’objectif de cette thèse était de développer un cadre conceptuel et méthodologique permettant d’évaluer l’impact global de l’alimentation sur la santé des consommateurs, en prenant en compte les dimensions microbiologiques, chimiques et nutritionnelles. Cette méthodologie a été développée à l’aide d’un cas d’étude portant sur l’alimentation des nourrissons (lait maternel et formules infantiles), incluant les facteurs suivants : C. sakazakii, Cryptosporidium, arsenic, polychlorobiphényles de type dioxine et acide docosahexaénoïque. Cinq modèles mathématiques probabilistes ont été développés pour quantifier les risques / bénéfices associés à chaque facteur. Ils ont été ensuite harmonisés, quand cela a été possible, à l’aide d’un indicateur commun de santé publique, le DALY. Les résultats ont été obtenus par simulation de Monte Carlo de second ordre afin de quantifier séparément l’incertitude et la variabilité. Les techniques probabilistes ont permis de prendre en compte d’une part la variabilité inhérente à la biologie (hétérogénéité entre individus d’une même population) et d’autre part l’incertitude liée au manque de connaissances et de données. De plus, la séparation de la variabilité et de l’incertitude a consolidé l’évaluation, permettant une interprétation plus cohérente des résultats et donc fournissant des informations plus complètes aux décisionnaires. La méthode mise en oeuvre dans ce travail de thèse pourra servir de base pour d’autres cas d’études et pourra aussi être utilisée pour continuer le développement méthodologique de l’évaluation risque-bénéfice. Cette démarche s’inscrit dans une approche plus générale d’analyse multi-critères des systèmes agronomiques et alimentaires / The objective of the present PhD project was to develop a conceptual and methodological framework to assess the overall impact of food consumed on human health, including microbiological, chemical and nutritional dimensions. This methodology was developed using a case study on infant milk-based diet (breast milk and infant formulas) taking into account the following selected factors: C. sakazakii, Cryptosporidium, arsenic, dioxin like polychlorinated biphenyls and docosahexaenoic acid. Five probabilistics mathematicals models were developed to quantify risks / benefits associated with these factors. When possible, they were harmonized using a common public health indicator, the DALY. Results were obtained by second-order Monte Carlo simulations in order to quantify separately the uncertainty and the variability. Probabilistic techniques enabled to take into account on the one hand the biology related to variability (heterogeneity between individuals of the same population) and on the other hand the uncertainty linked to the lack of knowledge and data. In addition, separation of variability and uncertainty strengthened the evaluation by enabling a more accurated interpretation of results and by providing more comprehensive information for policy makers. The method used in this PhD thesis can be considered as a robust basis for other case studies and can be also used to continue methodological development in risk-benefit assessment. This approach is also part of a broader area: the multi-criteria decision analysis of agronomic and food systems

Dans cette thèse on s'intéresse au problème de la localisation d'un robot sous-marin et de la cartographie en simultané d'un jeu de balises acoustiques installées sur le fond marin, en utilisant un distance-mètre acoustique et une centrale inertielle. Nous nous focalisons sur les deux approches principales utilisées pour résoudre ce type de problème: le filtrage de Kalman et le filtrage ensembliste basé sur l'analyse par intervalles. Le filtre de Kalman est optimal quand les équations d'état du robot sont linéaires et les bruits sont additifs, Gaussiens. Le filtrage par intervalles ne modélise pas les incertitudes dans un cadre probabiliste, et ne fait qu'une seule hypothèse sur leur nature: elles sont bornées. De plus, l'approche utilisant les intervalles permet la propagation rigoureuse des incertitudes, même quand les équations sont non linéaires. Cela résulte en une estimation hautement fiable, au prix d'une précision réduite. Nous montrons que dans un contexte sous-marin, quand le robot est équipé avec une centrale inertielle de haute précision, une partie des équations du SLAM peut raisonnablement être considérée comme linéaire avec un bruit Gaussien additif, en faisant le terrain de jeu idéal d'un filtre de Kalman. De l'autre côté, les équations liées aux observations du distance-mètre acoustique sont bien plus problématiques: le système n'est pas observable, les équations sont non linéaires, et les outliers sont fréquents. Ces conditions sont idéales pour une approche à erreur bornées basée sur l'analyse par intervalles. En prenant avantage des propriétés des bruits Gaussiens, cette thèse réconcilie le traitement probabiliste et ensembliste des incertitudes pour les systèmes aussi bien linéaires que non linéaires sujets à des bruits Gaussiens additifs. En raisonnant de manière géométrique, nous sommes capables d'exprimer la partie des équations du filtre de Kalman modélisant la dynamique du véhicule dans un cadre ensembliste. De la même manière, un traitement plus rigoureux et précis des incertitudes est décrit pour la partie des équations du filtre de Kalman liée aux mesures de distances. Ces outils peuvent ensuite être combinés pour obtenir un algorithme de SLAM qui est fiable, précis et robuste. Certaines des méthodes développées dans cette thèse sont illustrées sur des données réelles. / In this thesis, we work on the problem of simultaneously localizing an underwater robot while mapping a set of acoustic beacons lying on the seafloor, using an acoustic range-meter and an inertial navigation system. We focus on the two main approaches classically used to solve this type of problem: Kalman filtering and set-membership filtering using interval analysis. The Kalman filter is optimal when the state equations of the robot are linear, and the noises are additive, white and Gaussian. The interval-based filter do not model uncertainties in a probabilistic framework, and makes only one assumption about their nature: they are bounded. Moreover, the interval-based approach allows to rigorously propagate the uncertainties, even when the equations are non-linear. This results in a high reliability in the set estimate, at the cost of a reduced precision.We show that in a subsea context, when the robot is equipped with a high precision inertial navigation system, a part of the SLAM equations can reasonably be seen as linear with additive Gaussian noise, making it the ideal playground of a Kalman filter. On the other hand, the equations related to the acoustic range-meter are much more problematic: the system is not observable, the equations are non-linear, and the outliers are frequent. These conditions are ideal for a set-based approach using interval analysis.By taking advantage of the properties of Gaussian noises, this thesis reconciles the probabilistic and set-membership processing of uncertainties for both linear and non-linear systems with additive Gaussian noises. By reasoning geometrically, we are able to express the part of the Kalman filter equations linked to the dynamics of the vehicle in a set-membership context. In the same way, a more rigorous and precise treatment of uncertainties is described for the part of the Kalman filter linked to the range-measurements. These two tools can then be combined to obtain a SLAM algorithm that is reliable, precise and robust. Some of the methods developed during this thesis are demonstrated on real data.

L'utilisation d'aspects aléatoires a contribué de façon majeure aux dernières avancées dans le domaine de l'optimisation numérique; cela est dû en partie à la recrudescence de problèmes issus de l'apprentissage automatique (machine learning). Dans un tel contexte, les algorithmes classiques d'optimisation non linéaire, reposant sur des principes déterministes, se révèlent en effet bien moins performants que des variantes incorporant de l'aléatoire. Le coût de ces dernières est souvent inférieur à celui de leurs équivalents déterministes; en revanche, il peut s'avérer difficile de maintenir les propriétés théoriques d'un algorithme déterministe lorsque de l'aléatoire y est introduit. Effectuer une analyse de complexité d'une telle méthode est un procédé très répandu dans ce contexte. Cette technique permet déstimer la vitesse de convergence du schéma considéré et par là même d'établir une forme de convergence de celui-ci. Les récents travaux sur ce sujet, en particulier pour des problèmes d'optimisation non convexes, ont également contribué au développement de ces aspects dans le cadre déterministe, ceux-ci apportant en effet un éclairage nouveau sur le comportement des algorithmes. Dans cette thèse, on s'intéresse à l'amélioration pratique d'algorithmes d'optimisation sans dérivées à travers l'introduction d'aléatoire, ainsi qu'à l'impact numérique des analyses de complexité. L'étude se concentre essentiellement sur les méthodes de recherche directe, qui comptent parmi les principales catégories d'algorithmes sans dérivées; cependant, l'analyse sous-jacente est applicable à un large éventail de ces classes de méthodes. On propose des variantes probabilistes des propriétés requises pour assurer la convergence des algorithmes étudiés, en mettant en avant le gain en efficacité induit par ces variantes: un tel gain séxplique principalement par leur coût très faible en évaluations de fonction. Le cadre de base de notre analyse est celui de méthodes convergentes au premier ordre, que nous appliquons à des problèmes sans ou avec contraintes linéaires. Les bonnes performances obtenues dans ce contexte nous incitent par la suite à prendre en compte des aspects d'ordre deux. A partir des propriétés de complexité des algorithmes sans dérivées, on développe de nouvelles méthodes qui exploitent de l'information du second ordre. L'analyse de ces procédures peut être réalisée sur un plan déterministe ou probabiliste: la deuxième solution nous permet d'étudier de nouveaux aspects aléatoires ainsi que leurs conséquences sur l'éfficacité et la robustesse des algorithmes considérés. / Randomization has had a major impact on the latest developments in the field of numerical optimization, partly due to the outbreak of machine learning applications. In this increasingly popular context, classical nonlinear programming algorithms have indeed been outperformed by variants relying on randomness. The cost of these variants is usually lower than for the traditional schemes, however theoretical guarantees may not be straightforward to carry out from the deterministic to the randomized setting. Complexity analysis is a useful tool in the latter case, as it helps in providing estimates on the convergence speed of a given scheme, which implies some form of convergence. Such a technique has also gained attention from the deterministic optimization community thanks to recent findings in the nonconvex case, as it brings supplementary indicators on the behavior of an algorithm. In this thesis, we investigate the practical enhancement of deterministic optimization algorithms through the introduction of random elements within those frameworks, as well as the numerical impact of their complexity results. We focus on direct-search methods, one of the main classes of derivative-free algorithms, yet our analysis applies to a wide range of derivative-free methods. We propose probabilistic variants on classical properties required to ensure convergence of the studied methods, then enlighten their practical efficiency induced by their lower consumption of function evaluations. Firstorder concerns form the basis of our analysis, which we apply to address unconstrained and linearly-constrained problems. The observed gains incite us to additionally take second-order considerations into account. Using complexity properties of derivative-free schemes, we develop several frameworks in which information of order two is exploited. Both a deterministic and a probabilistic analysis can be performed on these schemes. The latter is an opportunity to introduce supplementary probabilistic properties, together with their impact on numerical efficiency and robustness.

Les structures en béton armé exposées à des environnements agressifs subissent des dégradations qui affectent leur intégrité. La corrosion des armatures est l’un des mécanismes de dégradation les plus répandus et les coûteux en terme de maintenance et de réparation. Ce processus est dû à la pénétration des agents agressifs dans le béton, notamment les ions chlorures et le gaz carbonique. Les chlorures induisent une corrosion localisée ou par piqûre, alors que le gaz carbonique engendre une corrosion généralisée ou uniforme. Le déclenchement et la propagation de la corrosion dépendent de plusieurs facteurs liés aux matériaux, aux chargements, à la géométrie et à l’environnement. Ces facteurs présentent de grandes incertitudes qui doivent être prise en comptes à travers une approche probabiliste. Dans ce travail de recherche, nous nous intéressons au mécanisme de corrosion en général. Un intérêt particulier est porté à la prise en compte de l’impact des facteurs climatiques sur ce processus, notamment dans le contexte libanais. Ainsi, nous proposons une modélisation physique de la corrosion des aciers dans les poutres en béton armé qui se déroule en deux phases : - une phase d’initiation durant laquelle les agents agressifs (chlorures et gaz carbonique) pénètrent dans le béton et atteignent des concentrations critiques provoquant la dépassivation de l’acier ; - une phase de propagation durant laquelle il y a corrosion active des aciers et diminution de la résistance de la poutre jusqu’à la défaillance. Les facteurs présentant des incertitudes sont traités comme des variables aléatoires. Pour les modéliser, nous avons étudié, pour les différentes variables aléatoires, de nombreux modèles probabilistes proposés dans la littérature. Nous avons vérifié leur compatibilité vis-à-vis de notre problématique et la possibilité d’assurer les données nécessaires à leur bonne utilisation (notamment la cohérence entre les hypothèses). Ensuite, nous avons retenu les modèles probabilistes les plus adaptés à notre cas. Par ailleurs, l’application des principes fiabilistes nous permet d’évaluer la fiabilité des poutres sujettes à la corrosion vis-à-vis des deux états-limites (ELU et ELS). En effet, la perte de la section d’acier due à la corrosion induit d’une part, une diminution de la capacité portante de la poutre, et d’autre part une augmentation de la contrainte au niveau du béton tendu (provoquant un accroissement des ouvertures des fissures). Ainsi, pour l’état limite de service, la marge de sûreté s’annule lorsque l’ouverture des fissures dépasse la valeur limite préconisée par l’Eurocode 2. Quant à l’état limite ultime, la fonction d’état limite est la résistance en flexion : la défaillance a lieu lorsque le moment résistant équivaut au moment sollicitant. Le calcul fiabiliste est effectué au moyen de simulations de Monte-Carlo. Finalement, nous avons réalisé plusieurs applications aux modèles de corrosions proposées dans ce travail. La première application porte sur l’analyse des sensibilités des modèles de corrosion aux différents paramètres. L’effet des moyennes des paramètres aléatoires ainsi que leurs variabilités sur la réponse du modèle est examiné. Une attention particulière est accordée à l’impact des facteurs climatiques. Ainsi une application du modèle de corrosion induite par les chlorures avec des données réelles de température et d’humidité relatives à trois villes côtières ayant des caractéristiques climatiques différentes est présentée. Ensuite une étude comparative de l’effet du choix des diamètres des armatures et des épaisseurs des enrobages sur la fiabilité à l’état limite ultime et à l’état limite de service est effectuée. Les résultats obtenus ont permis de mettre en évidence l’aspect agressif des facteurs climatiques : un climat chaud et humide est très agressif vis-à-vis de la corrosion induite par les chlorures alors qu’un climat à humidité relative variable favorise la corrosion par carbonatation. (...) / When exposed to aggressive environment, reinforced concrete structures are subject to a degradation mechanism that affects their integrity. Among various environmental attacks, the corrosion of RC structures is considered the most dangerous. The process is launched by the penetration of aggressive agents, precisely the chlorides and carbon dioxide into the concrete. The chlorides induce a localized corrosion, also called pitting corrosion, while on the other hand the carbon dioxide leads to a general corrosion called uniform corrosion. This corrosion phenomenon depends on several factors such as the materials characteristics,loadings, geometry and the environment. All these components include different levels of uncertainties that are taken into account throughout a probabilistic approach. In this work, we propose two models for the corrosion mechanisms induced separately by the chlorides and the carbon dioxide. These models take into account the effect of the climatic condition that is mainly described by the temperature and the relative humidity. In addition to that, as a study case we have treated in details the Lebanese climatic context. We have proposed a physical model of steel corrosion in reinforced concrete beams that occurs in two phases : - An initiation phase where aggressive agents like the chlorides and carbon dioxide penetrate into the concrete and reach a critical concentration values causing the depassivation of the steel ; - A propagation phase in which the active corrosion of steel decreases the strength of the beam leading to its failure. All the factors that have uncertainties are treated as random variables. Several probabilistic models are listed and discussed in the literature while only the models that match with our context are selected. The reliability analysis allowed us to assess the reliability of beams subjected to corrosion in ULS and SLS. The loss of steel section due to the corrosion mechanism induces a decrease of the bearing beam capacity, and an increase in the tension stress in the concrete.This causes an increase of the width of cracks openings. Thus, taking into account the serviceability limit state, the safety margin goes to zero when the width of crack opening exceeds the acceptable width as recommended by the Eurocode 2. The limit state function in ULS is the bending strength. The failure occurs when the applied moment equals or surpasses the resisting moment. The reliability calculations are carried out using Monte-Carlo simulations. Finally, several applications to the corrosion model are proposed via this work. The first application concerns the sensitivity analysis of the corrosion models for the different parameters. The effects of the mean values and the variability of the random variables on the model response are also examined. The impact of climatic factors on the corrosion phenomenon took the biggest part of this work. We have applied the chloride’s corrosion model with the real temperatures and relative humidity of three coastal cities having different climatic characteristics. Then a comparative study showing the effect of the ba rdiameters and the cover thickness on the reliability of the RC beam subjected to aggressive environment is carried out. (...)

La capacité des robots mobiles à se localiser précisément par rapport à leur environnement est indispensable à leur autonomie. Pour ce faire, les robots exploitent les données acquises par des capteurs qui observent leur état interne, tels que centrales inertielles ou l’odométrie, et les données acquises par des capteurs qui observent l’environnement, telles que les caméras et les Lidars. L’exploitation de ces derniers capteurs a suscité le développement de solutions qui estiment conjointement la position du robot et la position des éléments dans l'environnement, appelées SLAM (Simultaneous Localization and Mapping). Pour gérer le bruit des données provenant des capteurs, les solutions pour le SLAM sont mises en œuvre dans un contexte probabiliste. Les premiers développements étaient basés sur le filtre de Kalman étendu, mais des développements plus récents utilisent des modèles graphiques probabilistes pour modéliser le problème d’estimation et de le résoudre grâce à techniques d’optimisation. Cette thèse exploite cette dernière approche et propose deux techniques distinctes pour les véhicules terrestres autonomes: une utilisant la vision monoculaire, l’autre un Lidar. L’absence d’information de profondeur dans les images obtenues par une caméra a mené à l’utilisation de paramétrisations spécifiques pour les points de repères qui isolent la profondeur inconnue dans une variable, concentrant la grande incertitude sur la profondeur dans un seul paramètre. Une de ces paramétrisations, nommé paramétrisation pour l’angle de parallaxe (ou PAP, Parallax Angle Parametrization), a été introduite dans le contexte du problème d’ajustement de faisceaux, qui traite l’ensemble des données en une seule étape d’optimisation globale. Nous présentons comment exploiter cette paramétrisation dans une approche incrémentale de SLAM à base de modèles graphiques, qui intègre également les mesures de mouvement du robot. Les Lidars peuvent être utilisés pour construire des solutions d’odométrie grâce à un recalage séquentiel des nuages de points acquis le long de la trajectoire. Nous définissons une couche basée sur les modèles graphiques au dessus d’une telle couche d’odométrie, qui utilise l’algorithme ICP (Iterative Closest Points). Des repères clefs (keyframes) sont définis le long de la trajectoire du robot, et les résultats de l’algorithme ICP sont utilisés pour construire un graphe de poses, exploité pour résoudre un problème d’optimisation qui permet la correction de l’ensemble de la trajectoire du robot et de la carte de l’environnement à suite des fermetures de boucle.Après une introduction à la théorie des modèles graphiques appliquée au problème de SLAM, le manuscrit présente ces deux approches. Des résultats simulés et expérimentaux illustrent les développements tout au long du manuscrit, en utilisant des jeux des données classiques et obtenus au laboratoire. / A strong requirement to deploy autonomous mobile robots is their capacity to localize themselves with a certain precision in relation to their environment. Localization exploits data gathered by sensors that either observe the inner states of the robot, like acceleration and speed, or the environment, like cameras and Light Detection And Ranging (LIDAR) sensors. The use of environment sensors has triggered the development of localization solutions that jointly estimate the robot position and the position of elements in the environment, referred to as Simultaneous Localization and Mapping (SLAM) approaches. To handle the noise inherent of the data coming from the sensors, SLAM solutions are implemented in a probabilistic framework. First developments were based on Extended Kalman Filters, while a more recent developments use probabilistic graphical models to model the estimation problem and solve it through optimization. This thesis exploits the latter approach to develop two distinct techniques for autonomous ground vehicles: oneusing monocular vision, the other one using LIDAR. The lack of depth information in camera images has fostered the use of specific landmark parametrizations that isolate the unknown depth in one variable, concentrating its large uncertainty into a single parameter. One of these parametrizations, named Parallax Angle Parametrization, was originally introduced in the context of the Bundle Adjustment problem, that processes all the gathered data in a single global optimization step. We present how to exploit this parametrization in an incremental graph-based SLAM approach in which robot motion measures are also incorporated. LIDAR sensors can be used to build odometry-like solutions for localization by sequentially registering the point clouds acquired along a robot trajectory. We define a graphical model layer on top of a LIDAR odometry layer, that uses the Iterative Closest Points (ICP) algorithm as registration technique. Reference frames are defined along the robot trajectory, and ICP results are used to build a pose graph, used to solve an optimization problem that enables the correction of the robot trajectory and the environment map upon loop closures. After an introduction to the theory of graphical models applied to SLAM problem, the manuscript depicts these two approaches. Simulated and experimental results illustrate the developments throughout the manuscript, using classic and in-house datasets.

Markov decision processes (MDPs) are finite-state probabilistic systems with both strategic and random choices, hence well-established to model the interactions between a controller and its randomly responding environment. An MDP can be mathematically viewed as a one and half player stochastic game played in rounds when the controller chooses an action, and the environment chooses a successor according to a fixed probability distribution.<p><p>There are two incomparable views on the behavior of an MDP, when the strategic choices are fixed. In the traditional view, an MDP is a generator of sequence of states, called the state-outcome; the winning condition of the player is thus expressed as a set of desired sequences of states that are visited during the game, e.g. Borel condition such as reachability. The computational complexity of related decision problems and memory requirement of winning strategies for the state-outcome conditions are well-studied.<p><p>Recently, MDPs have been viewed as generators of sequences of probability distributions over states, called the distribution-outcome. We introduce synchronizing conditions defined on distribution-outcomes, which intuitively requires that the probability mass accumulates in some (group of) state(s), possibly in limit. A probability distribution is p-synchronizing if the probability mass is at least p in some state, and a sequence of probability distributions is always, eventually, weakly, or strongly p-synchronizing if respectively all, some, infinitely many, or all but finitely many distributions in the sequence are p-synchronizing.<p><p>For each synchronizing mode, an MDP can be (i) sure winning if there is a strategy that produces a 1-synchronizing sequence; (ii) almost-sure winning if there is a strategy that produces a sequence that is, for all epsilon > 0, a (1-epsilon)-synchronizing sequence; (iii) limit-sure winning if for all epsilon > 0, there is a strategy that produces a (1-epsilon)-synchronizing sequence.<p><p>We consider the problem of deciding whether an MDP is winning, for each synchronizing and winning mode: we establish matching upper and lower complexity bounds of the problems, as well as the memory requirement for optimal winning strategies.<p><p>As a further contribution, we study synchronization in probabilistic automata (PAs), that are kind of MDPs where controllers are restricted to use only word-strategies; i.e. no ability to observe the history of the system execution, but the number of choices made so far. The synchronizing languages of a PA is then the set of all synchronizing word-strategies: we establish the computational complexity of the emptiness and universality problems for all synchronizing languages in all winning modes.<p><p>We carry over results for synchronizing problems from MDPs and PAs to two-player turn-based games and non-deterministic finite state automata. Along with the main results, we establish new complexity results for alternating finite automata over a one-letter alphabet. In addition, we study different variants of synchronization for timed and weighted automata, as two instances of infinite-state systems. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Le chaînage d’enregistrements est la tâche qui consiste à identifier parmi différentes sources de données les enregistrements qui concernent les mêmes entités. En l'absence de clé d’identification commune, cette tâche peut être réalisée à l’aide d’autres champs contenant des informations d’identifications, mais dont malheureusement la qualité n’est pas parfaite. Pour ce faire, de nombreuses méthodes dites « de chaînage de données » ont été proposées au cours des dernières décennies.Afin d’assurer le chaînage valide et rapide des enregistrements des mêmes patients dans le cadre de GINSENG, projet qui visait à mettre en place une infrastructure de grille informatique pour le partage de données médicales distribuées, il a été nécessaire d’inventorier, d’étudier et parfois d’adapter certaines des diverses méthodes couramment utilisées pour le chaînage d’enregistrements. Citons notamment les méthodes de comparaison approximative des champs d’enregistrement selon leurs épellations et leurs prononciations, les chaînages déterministe et probabiliste d’enregistrements, ainsi que leurs extensions. Ces méthodes comptent des avantages et des inconvénients qui sont ici clairement exposés.Dans la pratique, les champs à comparer étant souvent imparfaits du fait d’erreurs typographiques, notre intérêt porte particulièrement sur les méthodes probabilistes de chaînage d’enregistrements. L’implémentation de ces méthodes probabilistes proposées par Fellegi et Sunter (PRL-FS) et par Winkler (PRL-W) est précisément décrite, ainsi que leur évaluation et comparaison. La vérité des correspondances des enregistrements étant indispensable à l’évaluation de la validité des résultats de chaînages, des jeux de données synthétiques sont générés dans ce travail et des algorithmes paramétrables proposés et détaillés.Bien qu’à notre connaissance, le PRL-W soit une des méthodes les plus performantes en termes de validité de chaînages d’enregistrements en présence d’erreurs typographiques dans les champs contenant les traits d’identification, il présente cependant quelques caractéristiques perfectibles. Le PRL-W ne permet par exemple pas de traiter de façon satisfaisante le problème de données manquantes. Notons également qu’il s’agit d’une méthode dont l’implémentation n’est pas simple et dont les temps de réponse sont difficilement compatibles avec certains usages de routine. Certaines solutions ont été proposées et évaluées pour pallier ces difficultés, notamment plusieurs approches permettant d’améliorer l’efficacité du PRL-W en présence de données manquantes et d’autres destinées à optimiser les temps de calculs de cette méthode en veillant à ce que cette réduction du temps de traitement n’entache pas la validité des décisions de chaînage issues de cette méthode. / Record linkage is the task of identifying which records from different data sources refer to the same entities. Without the common identification key among different databases, this task could be performed by comparison of corresponding fields (containing the information for identification) in records to link. To do this, many record linkage methods have been proposed in the last decades.In order to ensure a valid and fast linkage of the same patients’ records for GINSENG, a research project which aimed to implement a grid computing infrastructure for sharing medical data, we first studied various commonly used methods for record linkage. These are the methods of approximate comparison of fields in record according to their spellings and pronunciations; the deterministic and probabilistic record linkages and their extensions. The advantages and disadvantages of these methods are clearly demonstrated.In practice, as fields to compare are sometimes subject to typographical errors, we focused on probabilistic record linkage. The implementation of these probabilistic methods proposed by Fellegi and Sunter (PRL-FS) and Winkler (PRL-W) is described in details, and also their evaluation and comparison. Synthetic data sets were used in this work for knowing the truth of matches to evaluate the linkage results. A configurable algorithm for generating synthetic data was therefore proposed.To our knowledge, the PRL-W is one of the most effective methods in terms of validity of linkages in the presence of typographical errors in the field. However, the PRL-W does not satisfactorily treat the missing data problem in the fields, and the implementation of PRL-W is complex and has a computational time that impairs its opportunity in routine use. Solutions are proposed here with the objective of improving the effectiveness of PRL-W in the presence of missing data in the fields. Other solutions are tested to simplify the PRL-W algorithm and both reduce computational time and keep and optimal linkage accuracy.Keywords:

Les Environnements Informatiques pour l'Apprentissage Humain ont été utilisés pour améliorer l'apprentissage humain. Ils visent à accroître la performance des élèves en fournissant un enseignement individualisé. Il a été reconnu que l'apprentissage individualisé est plus efficace que l'apprentissage classique. L'utilisation de modèles d'étudiants pour capturer les connaissances des élèves sous-tend l'apprentissage individualisé. Différents modèles d'étudiants ont été proposés. Toutefois, une partie des informations de diagnostic issues du comportement des élèves est généralement ignorée par ces modèles. En outre, pour individualiser les parcours d'apprentissage des élèves, les modèles d'étudiants devraient capturer les structures préalables de compétences. Toutefois, l'acquisition de structures de compétences nécessite beaucoup d'efforts d'ingénierie de la connaissance. Nous améliorons les modèles d'étudiants pour l'apprentissage individualisé selon deux aspects. D'une part, afin d'améliorer la capacité de diagnostic d'un modèle de l'élève, nous introduisons les motifs d'erreur d'étudiants. Pour traiter le bruit dans les données de performance des élèves, nous étendons un modèle probabiliste en y intégrant les réponses erronées. Les résultats montrent que la fonction de diagnostic permet d'améliorer la précision de la prédiction des modèles d'étudiant. D'autre part, nous cherchons à découvrir des structures de compétences préalables à partir des données de performance de l'élève. C'est une tâche difficile, car les connaissances des élèves constituent une variable latente. Nous proposons une méthode en deux phases. Notre procédé est validé en l'appliquant à des données. / Computer-based educational environments, like Intelligent Tutoring Systems (ITSs), have been used to enhance human learning. These environments aim at increasing student achievement by providing individualized instructions. It has been recognized that individualized learning is more effective than the conventional learning. Student models which are used to capture student knowledge underlie the individualized learning. In recent decades, various competing student models have been proposed. However, some diagnostic information in student behaviors is usually ignored by these models. Furthermore, to individualize learning paths, student models should capture prerequisite structures of fine-grained skills. However, acquiring skill structures requires much knowledge engineering effort. We improve student models for individualized learning with respect to the two aspects. On one hand, in order to improve the diagnostic ability of a student model, we introduce the diagnostic feature—student error patterns. To deal with the noise in student performance data, we extend a sound probabilistic model to incorporate erroneous responses. The results show that the diagnostic feature improves the prediction accuracy of student models. On the other hand, we target on discovering prerequisite structures of skills from student performance data. It is a challenging task, since student knowledge of a skill is a latent variable. We propose a two-phase method to discover skill structure from noisy observations. Our method is validated on simulated data and real data. In addition, we verify that prerequisite structures of skills can improve the accuracy of a student model.

Le problème généralisé des moments (PGM) est un problème d'optimisation linéaire sur des espaces de mesures. Il permet de modéliser simplement un grand nombre d'applications. En toute généralité il est impossible à résoudre mais si ses données sont des polynômes et des ensembles semi-algébriques alors on peut définir une hiérarchie de relaxations semidéfinies (SDP) - la hiérarchie moments-sommes-de-carrés (moments-SOS) - qui permet en principe d'approcher la valeur optimale avec une précision arbitraire. Le travail contenu dans cette thèse adresse deux facettes concernants le PGM et la hiérarchie moments-SOS: Une première facette concerne l'évolution des relaxations SDP pour le PGM. Le degré des poids SOS dans la hiérarchie moments-SOS augmente avec l'ordre de relaxation. Lorsque le nombre de variables n'est pas modeste, on obtient rapidement des programmes SDP de taille trop grande pour les logiciels de programmation SDP actuels, sauf si l'on peut utiliser des symétries ou une parcimonie structurée souvent présente dans beaucoup d'applications de grande taille. On présente donc un nouveau certificat de positivité sur un compact semi-algébrique qui (i) exploite la parcimonie présente dans sa description, et (ii) dont les polynômes SOS ont un degré borné à l'avance. Grâce à ce nouveau certificat on peut définir une nouvelle hiérarchie de relaxations SDP pour le PGM qui exploite la parcimonie et évite l'explosion de la taille des matrices semidéfinies positives liée au degré des poids SOS dans la hiérarchie standard. Une deuxième facette concerne (i) la modélisation de nouvelles applications comme une instance particulière du PGM, et (ii) l'application de la méthodologie moments-SOS pour leur résolution. En particulier on propose des approximations déterministes de contraintes probabilistes, un problème difficile car le domaine des solutions admissibles associées est souvent non-convexe et même parfois non connecté. Dans notre approche moments-SOS le domaine admissible est remplacé par un ensemble plus petit qui est le sous-niveau d'un polynôme dont le vecteur des coefficients est une solution optimale d'un certain SDP. La qualité de l'approximation (interne) croît avec le degré du polynôme et la taille du SDP. On illustre cette approche dans le problème du calcul du flux de puissance optimal dans les réseaux d'énergie, une application stratégique où la prise en compte des contraintes probabilistes devient de plus en plus cruciale (e.g., pour modéliser l'incertitude liée á l'énergie éolienne et solaire). En outre on propose une extension des cette procedure qui est robuste à l'incertitude sur la distribution sous-jacente. Des garanties de convergence sont fournies. Une deuxième contribution concerne l'application de la méthodologie moments-SOS pour l'approximation de solutions généralisés en commande optimale. Elle permet de capturer le comportement limite d'une suite minimisante de commandes et de la suite de trajectoires associée. On peut traiter ainsi le cas de phénomènes simultanés de concentrations de la commande et de discontinuités de la trajectoire. Une troisième contribution concerne le calcul de solutions mesures pour les lois de conservation hyperboliques scalaires dont l'exemple typique est l'équation de Burgers. Cette classe d'EDP non linéaire peut avoir des solutions discontinues difficiles à approximer numériquement avec précision. Sous certaines hypothèses, la solution mesurepeut être identifiée avec la solution classique (faible) à la loi de conservation. Notre approche moment-SOS fournit alors une méthode alternative pour approcher des solutions qui contrairement aux méthodes existantes évite une discrétisation du domaine. / The generalized moment problem (GMP) is a linear optimization problem over spaces of measures. It allows to model many challenging mathematical problems. While in general it is impossible to solve the GMP, in the case where all data are polynomial and semialgebraic sets, one can define a hierarchy of semidefinite relaxations - the moment-sums-of-squares (moment-SOS) hierachy - which in principle allows to approximate the optimal value of the GMP to arbitrary precision. The work presented in this thesis addresses two facets concerning the GMP and the moment-SOS hierarchy: One facet is concerned with the scalability of relaxations for the GMP. The degree of the SOS weights in the moment-SOS hierarchy grows when augmenting the relaxation order. When the number of variables is not small, this leads quickly to semidefinite programs (SDPs) that are out of range for state of the art SDP solvers, unless one can use symmetries or some structured sparsity which is typically present in large scale applications. We provide a new certificate of positivity which (i) is able to exploit the structured sparsity and (ii) only involves SOS polynomials of fixed degree. From this, one can define a new hierarchy of SDP relaxations for the GMP which can take into account sparsity and at the same time prevents from explosion of the size of SDP variables related to the increasing degree of the SOS weights in the standard hierarchy. The second facet focusses on (i) modelling challenging problems as a particular instance of the GMP and (ii) solving these problems by applying the moment-SOS hierarchy. In particular we propose deterministic approximations of chance constraints a difficult problem as the associated set of feasible solutions is typically non-convex and sometimes not even connected. In our approach we replace this set by a (smaller) sub-level-set of a polynomial whose vector of coefficients is a by-product of the moment-SOS hierarchy when modeling the problem as an instance of the GMP. The quality of this inner approximation improves when increasing the degree of the SDP relaxation and asymptotic convergence is guaranteed. The procedure is illustrated by approximating the feasible set of an instance of the chance-constrained AC Optimal Power Flow problem (a nonlinear problem in the management of energy networks) which nowadays becomes more and more important as we rely increasingly on uncertain energy sources such as wind and solar power. Furthermore, we propose an extension of this framework to the case where the underlying distribution itself is uncertain and provide guarantees of convergence. Another application of the moment-SOS methodology discussed in this thesis consider measure valued solutions to optimal control problems. We show how this procedure can capture the limit behavior of an optimizing sequence of control and its corresponding sequence of trajectories. In particular we address the case of concentrations of control and discontinuities of the trajectory may occur simultaneously. In a final contribution, we compute measure valued solutions to scalar hyperbolic conservation laws, such as Burgers equation. It is known that this class of nonlinear partial differential equations has potentially discontinuous solutions which are difficult to approximate numerically with accuracy. Under some conditions the measure valued solution can be identified with the classical (weak) solution to the conservation law. In this case our moment-SOS approach provides an alternative numerical scheme to compute solutions which in contrast to existing methods, does not rely on discretization of the domain.