Dans de nombreux problèmes, des modèles complexes non-Gaussiens et/ou non-linéaires sont nécessaires pour décrire précisément le système physique étudié. Dans ce contexte, les algorithmes de Monte-Carlo sont des outils flexibles et puissants permettant de résoudre de tels problèmes d’inférence. Toutefois, en présence de loi a posteriori multimodale et/ou de grande dimension, les méthodes classiques de Monte-Carlo peuvent conduire à des résultats non satisfaisants. Dans cette thèse, nous étudions une approche plus robuste et efficace: échantillonneur séquentiel de Monte-Carlo. Bien que cette approche présente de nombreux avantages par rapport aux méthodes traditionnelles de Monte-Carlo, le potentiel de cette technique est cependant très largement sous-exploité en traitement du signal. L’objectif de cette thèse est donc de proposer de nouvelles stratégies permettant d’améliorer l’efficacité de cet algorithme et ensuite de faciliter sa mise en œuvre pratique. Pour ce faire, nous proposons une approche adaptive qui sélectionne la séquence de distributions minimisant la variance asymptotique de l'estimateur de la constante de normalisation de la loi a posteriori. Deuxièmement, nous proposons un mécanisme de correction qui permet d’améliorer l’efficacité globale de la méthode en utilisant toutes les particules générées à travers toutes les itérations de l’algorithme (au lieu d’uniquement celles de la dernière itération). Enfin pour illustrer l’utilité de cette approche ainsi que des stratégies proposées, nous utilisons cet algorithme dans deux problèmes complexes: la localisation de sources multiples dans les réseaux de capteurs et la régression Bayésienne pénalisée. / In many problems, complex non-Gaussian and/or nonlinear models are required to accurately describe a physical system of interest. In such cases, Monte Carlo algorithms are remarkably flexible and extremely powerful to solve such inference problems. However, in the presence of high-dimensional and/or multimodal posterior distribution, standard Monte-Carlo techniques could lead to poor performance. In this thesis, the study is focused on Sequential Monte-Carlo Sampler, a more robust and efficient Monte Carlo algorithm. Although this approach presents many advantages over traditional Monte-Carlo methods, the potential of this emergent technique is however largely underexploited in signal processing. In this thesis, we therefore focus our study on this technique by aiming at proposing some novel strategies that will improve the efficiency and facilitate practical implementation of the SMC sampler. Firstly, we propose an automatic and adaptive strategy that selects the sequence of distributions within the SMC sampler that approximately minimizes the asymptotic variance of the estimator of the posterior normalization constant. Secondly, we present an original contribution in order to improve the global efficiency of the SMC sampler by introducing some correction mechanisms that allow the use of the particles generated through all the iterations of the algorithm (instead of only particles from the last iteration). Finally, to illustrate the usefulness of such approaches, we apply the SMC sampler integrating our proposed improvement strategies to two challenging practical problems: Multiple source localization in wireless sensor networks and Bayesian penalized regression.

Tableau d'honneur de la Faculté des études supérieures et postdoctorales, 2006-2007 / L’algèbre de Kleene est la théorie algébrique des automates finis et des expressions régulières. Récemment, Kozen a proposé un cadre de travail basé sur l’algèbre de Kleene avec tests (une variante de l’algèbre de Kleene) pour vérifier qu’un programme satisfait une politique de sécurité spécifiée par un automate de sécurité. Malheureusement, cette approche ne permet pas de vérifier des propriétés de vivacité pour les programmes réactifs (programmes qui s’exécutent à l’infini). Le but de ce mémoire est d’étendre la méthode de vérification de programmes proposée par Kozen pour enlever cette limitation. Pour y arriver, nous développons la théorie de l’oméga-algèbre (une extension de l’algèbre de Kleene qui prend en compte les exécutions infinies) qui constitue la majeure partie de ce mémoire. En particulier, nous présentons des résultats de complétude concernant la théorie de Horn de cette algèbre. / Kleene algebra is the algebraic theory of finite automata and regular expressions. Recently, Kozen has proposed a framework based on Kleene algebra with tests (a variant of Kleene algebra) for verifying that a program satisfies a security policy specified by a security automaton. Unfortunately, this approach does not allow to verify liveness properties for reactive programs (programs that execute forever). The goal of this thesis is to extend the framework proposed by Kozen for program verification to remove this limitation. For that, we develop the theory of omega algebra, an extension of Kleene algebra suitable for reasoning about nonterminating executions. The main part of this thesis is about omega algebra. In particular, we show some completeness results about the Horn theory of omega algebra.

.

Tous les domaines de la science et de la technologie produisent de gros volume de données hétérogènes. L'exploration de tels volumes de données reste toujours un défi. Peu de travaux ciblent l'exploration et l'analyse de données séquentielles multidimensionnelles et hétérogènes. Dans ce travail, nous proposons une contribution à la découverte de connaissances dans les données séquentielles hétérogènes. Nous étudions trois axes de recherche différents: (i) l'extraction de motifs séquentiels, (ii) la classification et (iii) le clustering des données séquentielles. Tout d'abord, nous généralisons la notion de séquence multidimensionnelle en considérant la structure complexe et hétérogène. Nous présentons une nouvelle approche MMISP pour extraire des motifs séquentiels à partir de données séquentielles multidimensionnelles et hétérogènes. MMISP génère un grand nombre de motifs séquentiels comme cela est généralement le cas pour toues les algorithmes d'énumération des motifs. Pour surmonter ce problème, nous proposons une nouvelle façon de considérer les séquences multidimensionnelles hétérogènes en les associant à des structures de patrons. Nous développons une méthode pour énumérer seulement les motifs qui respectent certaines contraintes. La deuxième direction de recherche est la classification de séquences multidimensionnelles et hétérogènes. Nous utilisons l'analyse formelle de concept (AFC) comme une méthode de classification. Nous montrons l'intérêt des treillis de concepts et de l'indice de stabilité pour classer les séquences et pour choisir quelques groupes intéressants de séquences. La troisième direction de recherche dans cette thèse est préoccupé par le regroupement des données séquentielles multidimensionnelles et hétérogènes. Nous nous basons sur la notion de sous-séquences communes pour définir une mesure de similarité permettant d'évaluer la proximité entre deux séquences formées d'une liste d'ensemble d'items. Nous utilisons cette mesure de similarité pour construire une matrice de similarité entre les séquences et pour les segmenter en plusieurs groupes. Dans ce travail, nous présentons les résultats théoriques et un algorithme de programmation dynamique permettant de compter efficacement toutes les sous-séquences communes à deux séquences sans énumérer toutes les séquences. Le système résultant de cette recherches a été appliqué pour analyser et extraire les trajectoires de soins de santé des patients en cancérologie. Les données sont issues d' une base de données médico-administrative incluant des informations sur des patients hospitalisent en France. Le système permet d'identifier et de caractériser des épisodes de soins pour des ensembles spécifiques de patients. Les résultats ont été discutés et interprétés avec les experts du domaine / All domains of science and technology produce large and heterogeneous data. Although a lot of work was done in this area, mining such data is still a challenge. No previous research work targets the mining of heterogeneous multidimensional sequential data. This thesis proposes a contribution to knowledge discovery in heterogeneous sequential data. We study three different research directions: (i) Extraction of sequential patterns, (ii) Classification and (iii) Clustering of sequential data. Firstly we generalize the notion of a multidimensional sequence by considering complex and heterogeneous sequential structure. We present a new approach called MMISP to extract sequential patterns from heterogeneous sequential data. MMISP generates a large number of sequential patterns as this is usually the case for pattern enumeration algorithms. To overcome this problem, we propose a novel way of considering heterogeneous multidimensional sequences by mapping them into pattern structures. We develop a framework for enumerating only patterns satisfying given constraints. The second research direction is in concern with the classification of heterogeneous multidimensional sequences. We use Formal Concept Analysis (FCA) as a classification method. We show interesting properties of concept lattices and of stability index to classify sequences into a concept lattice and to select some interesting groups of sequences. The third research direction in this thesis is in concern with the clustering of heterogeneous multidimensional sequential data. We focus on the notion of common subsequences to define similarity between a pair of sequences composed of a list of itemsets. We use this similarity measure to build a similarity matrix between sequences and to separate them in different groups. In this work, we present theoretical results and an efficient dynamic programming algorithm to count the number of common subsequences between two sequences without enumerating all subsequences. The system resulting from this research work was applied to analyze and mine patient healthcare trajectories in oncology. Data are taken from a medico-administrative database including all information about the hospitalizations of patients in Lorraine Region (France). The system allows to identify and characterize episodes of care for specific sets of patients. Results were discussed and validated with domain experts

Une hypothèse dominant actuellement les théories sur l’évolution des capacités syntaxiques est celle d’une spécificité humaine pour le traitement des grammaires supra-régulières. Cette hypothèse est supportée par les données comparatives actuellement disponibles, qui ne fournissent pas de démonstration non ambiguë de cette capacité chez une autre espèce. Dans cette thèse, nous avons adopté une nouvelle approche consistant à examiner si ces échecs pourraient découler de la difficulté que représente l'extraction de régularités non-adjacentes. Pour tester cette hypothèse, nous avons mené une série de quatre études chez le babouin de guinée (Papio papio) et l’humain. La première étude montre que les babouins requièrent une quantité d’exposition beaucoup plus importante que l’humain pour apprendre des associations non-adjacentes. Dans une seconde étude, les babouins ont pu généraliser des patterns basés sur une répétition adjacente ou non-adjacente d’un élément, mais ils se sont montrés davantage sensibles à ces premiers. Une troisième étude, corrélationnelle, révèle que les babouins se montrant sensibles aux régularités non-adjacentes ne sont pas ceux obtenant les meilleures performances pour l’apprentissage de dépendances adjacentes. Une dernière étude suggère que les babouins sont sensibles à une structure en miroir (impliquant des dépendances centrées-emboitées), mais pas à une structure en copie (à dépendances croisées). Ces résultats mettent au jour une importante continuité des capacités syntaxiques au sein de la lignée des primates, mais révèlent également des différences inter-spécifiques importantes dans les contraintes mnésiques pesant sur celles-ci. / A current dominant hypothesis on the evolution of syntactic abilities propose that the processing of supra-regular grammars is a unique human capacity. In support of this hypothesis, artificial grammar learning studies conducted so far do not provide unambiguous demonstration of this capacity in a non-human species. In this thesis, we adopted a new approach by studying cognitive prerequisites for supra-regular grammar processing. Our hypothesis was that these previous failures could be attributed to a bias in these species towards the exploitation of local regularities and difficulties for processing more distant relationships, rather than an inability to master supra-regular grammars. We conducted a series of experiments in Guinea baboons (Papio papio) and humans to assess this hypothesis. In a first experiment, we show that baboons need much more exposure than humans to learn non-adjacent associations. In a second study, we show that baboons can generalize patterns involving an adjacent or a non-adjacent repetition of an element, but that they are more sensitive to the former. A third, correlational, study reveal that baboons succeeding to extract non-adjacent regularities are not those showing the best performance in learning local ones. A last study suggest that baboons are sensitive to a mirror structure (involving center-embedded dependencies), but not to a copy structure (crossed dependencies). Overall, our results reveal a stronger continuity in grammar processing capacities within the primate order than previously thought, but also highlight important species differences in memory constraints.

.

Cette thèse regroupe trois essais en théorie des enchères. Le chapitre 1 introduit de ladélégation dans le mécanisme d’enchère GSP. Dans un jeu impliquant des transferts monétaires et unepolitique de rémunération mise en place par une agence, un équilibre collusif efficace est atteint.Nousproposons une caractérisation du profil d’enchères collusif implémentable dans un jeu de positions `a troisjoueurs et deux positions. Le chapitre 2 considère des ventes séquentielles d’un objet `a deux acheteurs: l’unconnaît son évaluation privée tandis que l’autre non. Les acheteurs ont une demande multi-unitaire et lesévaluations privées entre unit´es sont parfaitement corrélées. Un équilibre asymétrique existe dans lequelle joueur non-informé adopte une stratégie agressive tandis que le joueur informé joue de manière prudente.Le comportement du joueur non-informé est justifié par l’opportunité d’acquérir de l’informationgratuitement. Cette dynamique induit une décroissance des prix entre les ventes. Le chapitre 3, introduitun jeu de décision séquentielle dans la première enchère. Un équilibre séparateur existe dans lequel lejoueur informé est agressif lorsqu’il est le premier `a jouer impliquant une stratégie de non-participationde la part de son concurrent non-informé. A l’inverse, ce dernier adopte une attitude plus prudentelorsqu’il est le premier `a joueur. Un équilibre mélangeant dans lequel le joueur informé cache son informationprivée ne peut exister que si le joueur non-informé adopte une stratégie de non-participation. / This thesis is a collection of three essays in theoretical auction analysis. Chapter 1 considersbid delegation in the GSP auction mechanism. In a game involving side-contracts and a compensationpolicy set by an agency, the first-best collusive outcome is achieved. We offer a characterization of the implementablebid profiles for the two-position game with three players. Chapter 2 considers the sequentialsale of an object to two buyers: one knows his private information and the other buyer does not. Buyershave a multi-unit demand and private valuations for each unit are perfectly correlated. An asymmetricequilibrium exists when the uninformed player adopts an aggressive bidding strategy. Conversely, hisinformed opponent behaves more conservatively by using bid shading. The bidding behaviour of theuninformed bidder is driven by the opportunity to learn his private valuation for free. This dynamic is atthe root of the decline in the equilibrium price across both sales. In chapter 3, information is observableduring the first-stage auction in a sequential-move game in which the first-mover bidder is observed byhis opponent. A separating equilibrium exists in which the informed bidder bids aggressively when he isthe first-mover which entails a non-participation strategy from his uninformed competitor. Conversely,the latter adopts a conservative behaviour when he is the first-mover. A pooling equilibrium in which theinformed bidder blurs his valuation can only exist if his uninformed opponent adopts a non-participatingstrategy.

Les problèmes de décision séquentielle dans l’incertain requièrent qu’un agent prenne des décisions, les unes après les autres, en fonction de l’état de l’environnement dans lequel il se trouve. Dans la plupart des travaux, l’environnement dans lequel évolue l’agent est supposé stationnaire, c’est-à-dire qu’il n’évolue pas avec le temps. Toute- fois, l’hypothèse de stationnarité peut ne pas être vérifiée quand, par exemple, des évènements exogènes au problème interviennent. Dans cette thèse, nous nous intéressons à la prise de décision séquentielle dans des environnements non-stationnaires. Nous proposons un nouveau modèle appelé HS3MDP permettant de représenter les problèmes non-stationnaires dont les dynamiques évoluent parmi un ensemble fini de contextes. Afin de résoudre efficacement ces problèmes, nous adaptons l’algorithme POMCP aux HS3MDP. Dans le but d’apprendre les dynamiques des problèmes de cette classe, nous présentons RLCD avec SCD, une méthode utilisable sans connaître à priori le nombre de contextes. Nous explorons ensuite le domaine de l’argumentation où peu de travaux se sont intéressés à la décision séquentielle. Nous étudions deux types de problèmes : les débats stochastiques (APS ) et les problèmes de médiation face à des agents non-stationnaires (DMP). Nous présentons dans ce travail un modèle formalisant les APS et permettant de les transformer en MOMDP afin d’optimiser la séquence d’arguments d’un des agents du débat. Nous étendons cette modélisation aux DMP afin de permettre à un médiateur de répartir stratégiquement la parole dans un débat. / In sequential decision-making problems under uncertainty, an agent makes decisions, one after another, considering the current state of the environment where she evolves. In most work, the environment the agent evolves in is assumed to be stationary, i.e., its dynamics do not change over time. However, the stationarity hypothesis can be invalid if, for instance, exogenous events can occur. In this document, we are interested in sequential decision-making in non-stationary environments. We propose a new model named HS3MDP, allowing us to represent non-stationary problems whose dynamics evolve among a finite set of contexts. In order to efficiently solve those problems, we adapt the POMCP algorithm to HS3MDPs. We also present RLCD with SCD, a new method to learn the dynamics of the environments, without knowing a priori the number of contexts. We then explore the field of argumentation problems, where few works consider sequential decision-making. We address two types of problems: stochastic debates (APS ) and mediation problems with non-stationary agents (DMP). In this work, we present a model formalizing APS and allowing us to transform them into an MOMDP in order to optimize the sequence of arguments of one agent in the debate. We then extend this model to DMPs to allow a mediator to strategically organize speak-turns in a debate.

Cette thèse s'intéresse à montrer l'intérêt aussi bien conceptuel qu'empirique de l'approche optionnelle de l'évaluation et du timing des projets de fusions-acquisitions. Pour ce faire, nous avons, tout d'abord, mobilisé une large littérature sur les fusions-acquisitions et les options réelles qui y sont liées. Constatant le manque de contributions empiriques au niveau de cette littérature, nous avons procédé à la réalisation de deux études empiriques. La première est une étude qualitative exploratoire réalisée auprès d'experts en fusions-acquisitions. Les résultats de cette étude nous ont permis d'étudier d'une manière approfondie les particularités de l'évaluation et du timing des fusions-acquisitions et de faire émerger de nouvelles catégories d'options réelles présentes dans les différentes phases du processus d'évaluation et dans les moments de choix de timing.Ces options ont été par la suite classées en options stratégiques de croissance et en option de flexibilité. Une fois les options identifiées, nous sommes passés à notre deuxième étude empirique qui est une étude de cas réel. Celle-ci vise, à partir d'un projet de fusion-acquisition réel, à expliciter les problématiques d'évaluation et de choix de timing lorsque l'acquéreur utilise les techniques traditionnelles d'évaluation telles que la Valeur Actuelle Nette. Les limites de ces méthodes nous amènent à proposer des solutions pour une meilleure approche de l'évaluation et du timing des fusions-acquisitions en contexte d'incertitude: la méthode par les options réelles. Pour ce faire, nous proposons d'évaluer l'opportunité d'acquisition et d'étudier le choix de timing opportun à sa conclusion à partir de la méthodologie de l'option simple. Trois méthodes d'évaluation sont alors adoptées: le modèle d'évaluation en temps continu (Black et Scholes), le modèle développé en temps discret ( arbres binomiaux) et la technique des simulations de Monte Carlo. La deuxième solution proposée est celle de l'approche de l'évaluation et du timing des fusions-acquisitions par la méthodologie de l'option composée multi-séquentielle. A ce titre, nous mobilisons le modèle binomial adapté par Mun (2010) et proposons une modélisation sur mesure sous Visual Basic des séquences d'options sur options liées au processus d'évaluation et au choix du timing / The aim of this thesis is to study the conceptual and the empirical role when valuation and timing of mergers and acquisitions are approached by real options theory. To reach this aim, we started by analyzing a huge litterature on real option approach of mergers and acquisitions. We noticed a big lack on empirical contributions of real options in the mergers and acquisitions field, specially in pre-closing phases, where the acquirer value his project and choose the optimal timing to conclude it. To more investigate on that, we led deux studies. The first one is an exploratory study, in which we interviewed professionals on mergers and acquisitions on partucularities of valuation and timing on mergers and acquisitions. Then we asked them to identify real options on valuation and timing. Identified options were divided on strategic growth options and flexibility options. After the identification, we led our second study which is a real case study of a merger and acquisition project. The aim of this study is to prove limits of traditionnal valuation methods like the Net Present Value. As solutions to these limits, we proposed to use the real option approach. First, we used the simple option methodology and then the multi-phased compound options methodology to ameliorate valuation results and the timing choice of concluding mergers and acquisitions

La présente thèse porte sur l'étude de prise de décisions séquentielles multi-Objectif (MOSDM). La motivation de ce travail est double. D'un côté, la prise de décision, par exemple, dans les domaines de robotique et de planification, concerne l'optimisation séquentielle. De l'autre côté, nombreuses applications dans le monde réel sont plus naturellement formulés en termes d'optimisation multi-Objectif (MOO). La méthode proposée dans la thèse adapte le cadre bien connue de recherche Monte-Carlo arborescente (MCTS) à l'optimisation multi-Objectif, dans lequel multiple séquences de décision optimales sont développées dans un seul arbre de recherche. Le principal défi est de proposer une nouvelle récompense, capable de guider l'exploration de l'arbre bien que le problème de MOO n'applique pas un ordre total entre les solutions. La contribution principale de cette thèse est de proposer et d'étudier expérimentalement ces deux récompenses : l'indicateur de hypervolume et la récompense de dominance Pareto, qui sont inspirées de la littérature de MOO et basés sur une archive de solutions antérieures (archives Pareto). L'étude montre la complémentarité de ces deux récompenses. L'indicateur de hypervolume souffre de sa complexité algorithmique. Cependant, cet indicateur fournit des informations à grains fins de la qualité des solutions à l'égard de l'archive actuelle. Bien au contraire, la complexité de la récompense de dominance Pareto est linéaire, mais cette récompense fournit des informations de plus en plus rare au long de la recherche. Les preuves de principe de l'approche sont donnés sur les problèmes articiaux et les défis internationaux, et confirment la valeur de l'approche. En particulier, MOMCTS est capable de découvrir les politiques se trouvant dans les régions non-Convexes du front Pareto, qui contraste avec l'état de l'art: les algorithmes d'apprentissage par renforcement multi-Objectif existants sont basés sur scalarization linéaire et donc ne sont pas capables de explorer ces régions non-Convexes. Enfin, MOMCTS a fait honorablement la concurrence avec l'état de l'art sur la compétition internationale de MOPTSP 2013. / This thesis is concerned with multi-Objective sequential decision making (MOSDM). The motivation is twofold. On the one hand, many decision problems in the domains of e.g., robotics, scheduling or games, involve the optimization of sequences of decisions. On the other hand, many real-World applications are most naturally formulated in terms of multi-Objective optimization (MOO). The proposed approach extends the well-Known Monte-Carlo tree search (MCTS) framework to the MOO setting, with the goal of discovering several optimal sequences of decisions through growing a single search tree. The main challenge is to propose a new reward, able to guide the exploration of the tree although the MOO setting does not enforce a total order among solutions. The main contribution of the thesis is to propose and experimentally study two such rewards, inspired from the MOO literature and assessing a solution with respect to the archive of previous solutions (Pareto archive): the hypervolume indicator and the Pareto dominance reward. The study shows the complementarity of these two criteria. The hypervolume indicator suffers from its known computational complexity; however the proposed extension thereof provides fine-Grained information about the quality of solutions with respect to the current archive. Quite the contrary, the Pareto-Dominance reward is linear but it provides increasingly rare information. Proofs of principle of the approach are given on artificial problems and challenges, and confirm the merits of the approach. In particular, MOMCTS is able to discover policies lying in non-Convex regions of the Pareto front, contrasting with the state of the art: existing Multi-Objective Reinforcement Learning algorithms are based on linear scalarization and thus fail to sample such non-Convex regions. Finally MOMCTS honorably competes with the state of the art on the 2013 MOPTSP competition.