Cette thèse s'inscrit dans le domaine de la prise de décision séquentielle en environnement inconnu, et plus particulièrement dans le cadre des bandits manchots (multi-armed bandits, MAB), défini par Robbins et Lai dans les années 50. Depuis les années 2000, ce cadre a fait l'objet de nombreuses recherches théoriques et algorithmiques centrées sur le compromis entre l'exploration et l'exploitation : L'exploitation consiste à répéter le plus souvent possible les choix qui se sont avérés les meilleurs jusqu'à présent. L'exploration consiste à essayer des choix qui ont rarement été essayés, pour vérifier qu'on a bien identifié les meilleurs choix. Les applications des approches MAB vont du choix des traitements médicaux à la recommandation dans le contexte du commerce électronique, en passant par la recherche de politiques optimales de l'énergie. Les contributions présentées dans ce manuscrit s'intéressent au compromis exploration vs exploitation sous deux angles spécifiques. Le premier concerne la prise en compte du risque. Toute exploration dans un contexte inconnu peut en effet aboutir à des conséquences indésirables ; par exemple l'exploration des comportements d'un robot peut aboutir à des dommages pour le robot ou pour son environnement. Dans ce contexte, l'objectif est d'obtenir un compromis entre exploration, exploitation, et prise de risque (EER). Plusieurs algorithmes originaux sont proposés dans le cadre du compromis EER. Sous des hypothèses fortes, l'algorithme MIN offre des garanties de regret logarithmique, à l'état de l'art ; il offre également une grande robustesse, contrastant avec la forte sensibilité aux valeurs des hyper-paramètres de e.g. (Auer et al. 2002). L'algorithme MARAB s'intéresse à un critère inspiré de la littérature économique(Conditional Value at Risk), et montre d'excellentes performances empiriques comparées à (Sani et al. 2012), mais sans garanties théoriques. Enfin, l'algorithme MARABOUT modifie l'estimation du critère CVaR pour obtenir des garanties théoriques, tout en obtenant un bon comportement empirique. Le second axe de recherche concerne le bandit contextuel, où l'on dispose d'informations additionnelles relatives au contexte de la décision ; par exemple, les variables d'état du patient dans un contexte médical ou de l'utilisateur dans un contexte de recommandation. L'étude se focalise sur le choix entre bras qu'on a tirés précédemment un nombre de fois différent. Le choix repose en général sur la notion d'optimisme, comparant les bornes supérieures des intervalles de confiance associés aux bras considérés. Une autre approche appelée BESA, reposant sur le sous-échantillonnage des valeurs tirées pour les bras les plus visités, et permettant ainsi de se ramener au cas où tous les bras ont été tirés un même nombre de fois, a été proposée par (Baransi et al. 2014). / This thesis focuses on sequential decision making in unknown environment, and more particularly on the Multi-Armed Bandit (MAB) setting, defined by Lai and Robbins in the 50s. During the last decade, many theoretical and algorithmic studies have been aimed at cthe exploration vs exploitation tradeoff at the core of MABs, where Exploitation is biased toward the best options visited so far while Exploration is biased toward options rarely visited, to enforce the discovery of the the true best choices. MAB applications range from medicine (the elicitation of the best prescriptions) to e-commerce (recommendations, advertisements) and optimal policies (e.g., in the energy domain). The contributions presented in this dissertation tackle the exploration vs exploitation dilemma under two angles. The first contribution is centered on risk avoidance. Exploration in unknown environments often has adverse effects: for instance exploratory trajectories of a robot can entail physical damages for the robot or its environment. We thus define the exploration vs exploitation vs safety (EES) tradeoff, and propose three new algorithms addressing the EES dilemma. Firstly and under strong assumptions, the MIN algorithm provides a robust behavior with guarantees of logarithmic regret, matching the state of the art with a high robustness w.r.t. hyper-parameter setting (as opposed to, e.g. UCB (Auer 2002)). Secondly, the MARAB algorithm aims at optimizing the cumulative 'Conditional Value at Risk' (CVar) rewards, originated from the economics domain, with excellent empirical performances compared to (Sani et al. 2012), though without any theoretical guarantees. Finally, the MARABOUT algorithm modifies the CVar estimation and yields both theoretical guarantees and a good empirical behavior. The second contribution concerns the contextual bandit setting, where additional informations are provided to support the decision making, such as the user details in the ontent recommendation domain, or the patient history in the medical domain. The study focuses on how to make a choice between two arms with different numbers of samples. Traditionally, a confidence region is derived for each arm based on the associated samples, and the 'Optimism in front of the unknown' principle implements the choice of the arm with maximal upper confidence bound. An alternative, pioneered by (Baransi et al. 2014), and called BESA, proceeds instead by subsampling without replacement the larger sample set. In this framework, we designed a contextual bandit algorithm based on sub-sampling without replacement, relaxing the (unrealistic) assumption that all arm reward distributions rely on the same parameter. The CL-BESA algorithm yields both theoretical guarantees of logarithmic regret and good empirical behavior.

La marge algérienne est un domaine complexe, bordé au sud par les zones internes des Maghrébides (AlKaPeCa) qui chevauchent les zones externes telliennes vers le sud. La partie offshore de ce système constitue un bassin d‘arrière arc où s‘est déposée une série sédimentaire mio-pliocène reposant sur un substratum de nature et d‘origine variables spatialement. L'objectif de ce travail a consisté à analyser et modéliser le fonctionnement des systèmes pétroliers et à quantifier les volumes d‘hydrocarbures accumulés. Avant de procéder aux différentes modélisations numériques, stratigraphiques et thermiques, un modèle géologique conceptuel a été élaboré sur la base des données de géologie de terrain et de sismiques. La continuité terre- mer du socle kabyle a permis une extrapolation stratigraphique entre des formations oligo-miocènes en affleurement et les unités acoustiques définies dans le bassin offshore. L‘analyse tectonique dans les deux domaines a abouti à une évolution en trois phases : (1) syn-rift où le bassin a été ouvert en transtension à partir de l‘Oligocène supérieur-Aquitanien, (2) phase post-rift durant laquelle il y a eu le développement des bassins intra-arcs, la collision AlKaPeCa- Afrique et le magmatisme, (3) phase d‘inversion où la marge devient active essentiellement à partir du Quaternaire. En définissant l‘ensemble des éléments des systèmes pétroliers avec des incertitudes variables, la simulation du fonctionnement de ces derniers par modélisation de bassin 2D/3D a montré des possibilités d‘accumulation d‘huile et de gaz majoritairement près de la marge, entre 20 et 65 km de la côte avec un maximum de portée de 70 km dans le golfe de Bejaia. / The Algerian margin is a complex domain, limited to the south by the Maghrebian internal zones (AlKaPeCa) that overthrust the external Tellian zones southward. The offshore part of this system constitutes a back-arc basin, where a mio-pliocene sedimentary series were deposited over a substratum of laterally variable origin and nature. The goal of the present work consisted in analyzing and modelling the petroleum system at work and calculating hydrocarbon volumes. Before proceeding to different numerical basin, stratigraphic and thermal modelling, a conceptual geological model is required and was performed based on field geological studies and stratigraphic and structural interpretations of the seismic profiles. The extension of the continental crust beyond the foot of the margin, allows determining a chronostratigraphic model by extrapolation of the outcroping oligo-miocene formations onshore to the acoustic pre-messinian units defined in the offshore basin. Besides, a tectonic analysis in both onshore and offshore domains gave rise to three main steps of evolution: (1) syn-rift phase where the basin was opened by transtension since Late Oligocene- Aquitanian, (2) post-rift phase in which intra-arc basins were developed, AlKaPeCa and Africa docked and magmatism activity took place, (3) inversion phase where the margin became active mainly since Quaternary times. After defining the different petroleum system elements taking into account variable uncertainties, the 2D/3D petroleum system model depicts possibilities of oil and gas accumulations mainly close to the margin, between 20 to 65 km from the coastline to the north with a maximum range of 70 km in the Bejaia Gulf.

Cette thèse s'inscrit dans le domaine de l'apprentissage statistique. Le cadre principal est celui de la prévision de suites déterministes arbitraires (ou suites individuelles), qui recouvre des problèmes d'apprentissage séquentiel où l'on ne peut ou ne veut pas faire d'hypothèses de stochasticité sur la suite des données à prévoir. Cela conduit à des méthodes très robustes. Dans ces travaux, on étudie quelques liens étroits entre la théorie de la prévision de suites individuelles et le cadre statistique classique, notamment le modèle de régression avec design aléatoire ou fixe, où les données sont modélisées de façon stochastique. Les apports entre ces deux cadres sont mutuels : certaines méthodes statistiques peuvent être adaptées au cadre séquentiel pour bénéficier de garanties déterministes ; réciproquement, des techniques de suites individuelles permettent de calibrer automatiquement des méthodes statistiques pour obtenir des bornes adaptatives en la variance du bruit. On étudie de tels liens sur plusieurs problèmes voisins : la régression linéaire séquentielle parcimonieuse en grande dimension (avec application au cadre stochastique), la régression linéaire séquentielle sur des boules L1, et l'agrégation de modèles non linéaires dans un cadre de sélection de modèles (régression avec design fixe). Enfin, des techniques stochastiques sont utilisées et développées pour déterminer les vitesses minimax de divers critères de performance séquentielle (regrets interne et swap notamment) en environnement déterministe ou stochastique. / The topics addressed in this thesis lie in statistical machine learning. Our main framework is the prediction of arbitrary deterministic sequences (or individual sequences). It includes online learning tasks for which we cannot make any stochasticity assumption on the data to be predicted, which requires robust methods. In this work, we analyze several connections between the theory of individual sequences and the classical statistical setting, e.g., the regression model with fixed or random design, where stochastic assumptions are made. These two frameworks benefit from one another: some statistical methods can be adapted to the online learning setting to satisfy deterministic performance guarantees. Conversely, some individual-sequence techniques are useful to tune the parameters of a statistical method and to get risk bounds that are adaptive to the unknown variance. We study such connections for several connected problems: high-dimensional online linear regression under a sparsity scenario (with an application to the stochastic setting), online linear regression on L1-balls, and aggregation of nonlinear models in a model selection framework (regression on a fixed design). We also use and develop stochastic techniques to compute the minimax rates of game-theoretic online measures of performance (e.g., internal and swap regrets) in a deterministic or stochastic environment.

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.

Dans cette thèse, nous proposons une méthode pour construire un outil d'aide à la décision pour le diagnostic de maladie rare. Nous cherchons à minimiser le nombre de tests médicaux nécessaires pour atteindre un état où l'incertitude concernant la maladie du patient est inférieure à un seuil prédéterminé. Ce faisant, nous tenons compte de la nécessité dans de nombreuses applications médicales, d'éviter autant que possible, tout diagnostic erroné. Pour résoudre cette tâche d'optimisation, nous étudions plusieurs algorithmes d'apprentissage par renforcement et les rendons opérationnels pour notre problème de très grande dimension. Pour cela nous décomposons le problème initial sous la forme de plusieurs sous-problèmes et montrons qu'il est possible de tirer partie des intersections entre ces sous-tâches pour accélérer l'apprentissage. Les stratégies apprises se révèlent bien plus performantes que des stratégies gloutonnes classiques. Nous présentons également une façon de combiner les connaissances d'experts, exprimées sous forme de probabilités conditionnelles, avec des données cliniques. Il s'agit d'un aspect crucial car la rareté des données pour les maladies rares empêche toute approche basée uniquement sur des données cliniques. Nous montrons, tant théoriquement qu'empiriquement, que l'estimateur que nous proposons est toujours plus performant que le meilleur des deux modèles (expert ou données) à une constante près. Enfin nous montrons qu'il est possible d'intégrer efficacement des raisonnements tenant compte du niveau de granularité des symptômes renseignés tout en restant dans le cadre probabiliste développé tout au long de ce travail. / In this thesis, we propose a method to build a decision support tool for the diagnosis of rare diseases. We aim to minimize the number of medical tests necessary to achieve a state where the uncertainty regarding the patient's disease is less than a predetermined threshold. In doing so, we take into account the need in many medical applications, to avoid as much as possible, any misdiagnosis. To solve this optimization task, we investigate several reinforcement learning algorithm and make them operable in our high-dimensional. To do this, we break down the initial problem into several sub-problems and show that it is possible to take advantage of the intersections between these sub-tasks to accelerate the learning phase. The strategies learned are much more effective than classic greedy strategies. We also present a way to combine expert knowledge, expressed as conditional probabilities, with clinical data. This is crucial because the scarcity of data in the field of rare diseases prevents any approach based solely on clinical data. We show, both empirically and theoretically, that our proposed estimator is always more efficient than the best of the two models (expert or data) within a constant. Finally, we show that it is possible to effectively integrate reasoning taking into account the level of granularity of the symptoms reported while remaining within the probabilistic framework developed throughout this work.

No description available.

Les nouvelles technologies de la vidéo numérique tendent vers la production, la transmission et la diffusion de contenus de très haute qualité, qu'ils soient monoscopiques ou stéréoscopiques. Ces technologies ont énormément évolué ces dernières années pour faire vivre à l'observateur l'expérience la plus réaliste possible. Pour des raisons artistiques ou techniques liées à l'acquisition et à la transmission du contenu, il est parfois nécessaire de combiner la vidéo acquise à des informations de synthèse tout en veillant à maintenir un rendu photo-réaliste accru. Pour faciliter la tâche des opérateurs de production et post-production, le traitement combiné de contenus capturés et de contenus de synthèse exige de disposer de fonctionnalités automatiques sophistiquées. Parmi celles-ci, nos travaux de recherche ont porté sur l'évaluation de qualité de la synthèse de vues et l'élaboration de stratégies d'estimation de mouvement dense et long-terme. L'obtention d'images synthétisées de bonne qualité est essentielle pour les écrans 3D auto-stéréoscopiques. En raison d'une mauvaise estimation de disparité ou interpolation, les vues synthétisées générées par DIBR font cependant parfois l'objet d'artéfacts. C'est pourquoi nous avons proposé et validé une nouvelle métrique d'évaluation objective de la qualité visuelle des images obtenues par synthèse de vues. Tout comme les techniques de segmentation ou d'analyse de scènes dynamiques, l'édition vidéo requiert une estimation dense et long-terme du mouvement pour propager des informations synthétiques à l'ensemble de la séquence. L'état de l'art dans le domaine se limitant quasi-exclusivement à des paires d'images consécutives, nous proposons plusieurs contributions visant à estimer le mouvement dense et long-terme. Ces contributions se fondent sur une manipulation robuste de vecteurs de flot optique de pas variables (multi-steps). Dans ce cadre, une méthode de fusion séquentielle ainsi qu'un filtrage multilatéral spatio-temporel basé trajectoires ont été proposés pour générer des champs de déplacement long-termes robustes aux occultations temporaires. Une méthode alternative basée intégration combinatoire et sélection statistique a également été mise en œuvre. Enfin, des stratégies à images de référence multiples ont été étudiées afin de combiner des trajectoires provenant d'images de référence sélectionnées selon des critères de qualité du mouvement. Ces différentes contributions ouvrent de larges perspectives, notamment dans le contexte de la coopération stéréo-mouvement pour lequel nous avons abordé les aspects correction de disparité à l'aide de champs de déplacement denses long-termes.